`divrem` with polynomials

SoongNoonien commented 12 months ago

Hi! As mentioned in https://github.com/Nemocas/Nemo.jl/issues/1509 and https://github.com/Nemocas/AbstractAlgebra.jl/issues/1401 there are some problems with modulo and polynomials. It seems like there is a div methods missing in AbstractAlgebra (and Nemo):

julia> using AbstractAlgebra

julia> R,(x,y)=ZZ[:x,:y]
(Multivariate polynomial ring in 2 variables over integers, AbstractAlgebra.Generic.MPoly{BigInt}[x, y])

julia> divrem(R(-1),R(2),RoundDown)
ERROR: MethodError: no method matching div(::AbstractAlgebra.Generic.MPoly{BigInt}, ::AbstractAlgebra.Generic.MPoly{BigInt}, ::RoundingMode{:Down})
Closest candidates are:
  div(::AbstractAlgebra.Generic.MPoly{T}, ::AbstractAlgebra.Generic.MPoly{T}) where T<:RingElement at ~/.julia/packages/AbstractAlgebra/YkCOC/src/generic/MPoly.jl:2788
  div(::T, ::T) where T<:RingElem at ~/.julia/packages/AbstractAlgebra/YkCOC/src/algorithms/GenericFunctions.jl:77
  div(::Any, ::Any) at div.jl:40
  ...
Stacktrace:
 [1] fld(a::AbstractAlgebra.Generic.MPoly{BigInt}, b::AbstractAlgebra.Generic.MPoly{BigInt})
   @ Base ./div.jl:121
 [2] divrem(a::AbstractAlgebra.Generic.MPoly{BigInt}, b::AbstractAlgebra.Generic.MPoly{BigInt}, r::RoundingMode{:Down})
   @ Base ./div.jl:170
 [3] top-level scope
   @ REPL[8]:1

while

julia> divrem(ZZ(-1),ZZ(2),RoundDown)
(-1, 1)

julia> rem(R(-1),R(2),RoundDown)
1

works as one would expect. I noticed this while using divrem without RoundDown, which should

Return a tuple (q,r) such that f=qg+r, where the coefficients of terms of r whose monomials are divisible by the leading monomial of g are reduced modulo the leading coefficient of g (according to the Euclidean function on the coefficients).

according to https://nemocas.github.io/AbstractAlgebra.jl/dev/mpoly_interface/. But this is not the case when RoundDown is omitted in Nemo, which seems to be the expected behaviour, at least according to plain Julia:

julia> using Nemo

Welcome to Nemo version 0.34.7

Nemo comes with absolutely no warranty whatsoever

julia> divrem(R(-1),R(2))
(0, -1)

julia> divrem(-1,2)
(0, -1)

AbstractAlgebra behaves as described in its documentation but is inconsistent with plain Julia:

julia> divrem(R(-1),R(2))
(-1, 1)

I'm not sure if Nemo or AbstractAlgebra is right in this case, what do you think?

fieker commented 11 months ago

On Fri, Jul 14, 2023 at 12:38:59PM -0700, Martin Wagner wrote:

Hi! As mentioned in https://github.com/Nemocas/Nemo.jl/issues/1509 and https://github.com/Nemocas/AbstractAlgebra.jl/issues/1401 there are some problems with modulo and polynomials. It seems like there is a div methods missing in AbstractAlgebra (and Nemo):

That is mainly due to Z[X, y] not being Euclidean: div is the Euclidean division. What would be the definition of div in this case?
julia> using AbstractAlgebra

julia> R,(x,y)=ZZ[:x,:y]
(Multivariate polynomial ring in 2 variables over integers, AbstractAlgebra.Generic.MPoly{BigInt}[x, y])

julia> divrem(R(-1),R(2),RoundDown)
ERROR: MethodError: no method matching div(::AbstractAlgebra.Generic.MPoly{BigInt}, ::AbstractAlgebra.Generic.MPoly{BigInt}, ::RoundingMode{:Down})
Closest candidates are:
  div(::AbstractAlgebra.Generic.MPoly{T}, ::AbstractAlgebra.Generic.MPoly{T}) where T<:RingElement at ~/.julia/packages/AbstractAlgebra/YkCOC/src/generic/MPoly.jl:2788
  div(::T, ::T) where T<:RingElem at ~/.julia/packages/AbstractAlgebra/YkCOC/src/algorithms/GenericFunctions.jl:77
  div(::Any, ::Any) at div.jl:40
  ...
Stacktrace:
 [1] fld(a::AbstractAlgebra.Generic.MPoly{BigInt}, b::AbstractAlgebra.Generic.MPoly{BigInt})
   @ Base ./div.jl:121
 [2] divrem(a::AbstractAlgebra.Generic.MPoly{BigInt}, b::AbstractAlgebra.Generic.MPoly{BigInt}, r::RoundingMode{:Down})
   @ Base ./div.jl:170
 [3] top-level scope
   @ REPL[8]:1
while
julia> divrem(ZZ(-1),ZZ(2),RoundDown)
(-1, 1)

julia> rem(R(-1),R(2),RoundDown)
1
works as one would expect. I noticed this while using divrem without RoundDown, which should

Return a tuple (q,r) such that f=qg+r, where the coefficients of terms of r whose monomials are divisible by the leading monomial of g are reduced modulo the leading coefficient of g (according to the Euclidean function on the coefficients).

according to https://nemocas.github.io/AbstractAlgebra.jl/dev/mpoly_interface/. But this is not the case when RoundDown is omitted in Nemo, which seems to be the expected behaviour, at least according to plain Julia:
julia> using Nemo

Welcome to Nemo version 0.34.7

Nemo comes with absolutely no warranty whatsoever

julia> divrem(R(-1),R(2))
(0, -1)

julia> divrem(-1,2)
(0, -1)
AbstractAlgebra behaves as described in its documentation but is inconsistent with plain Julia:
julia> divrem(R(-1),R(2))
(-1, 1)
I'm not sure if Nemo or AbstractAlgebra is right in this case, what do you think?

-- Reply to this email directly or view it on GitHub: https://github.com/Nemocas/AbstractAlgebra.jl/issues/1402 You are receiving this because you are subscribed to this thread.

Message ID: @.***>

SoongNoonien commented 11 months ago

Plain div is implemented:

julia> using AbstractAlgebra

julia> R,(x,y)=ZZ[:x,:y]
(Multivariate polynomial ring in 2 variables over integers, AbstractAlgebra.Generic.MPoly{BigInt}[x, y])

julia> div(R(-1),R(2))
-1

The problem is the missing div with RoundDown. I'd say the division just depends on a monomial ordering.

fieker commented 11 months ago

On Mon, Jul 17, 2023 at 08:45:01AM -0700, Martin Wagner wrote:

Plain div is implemented:
julia> using AbstractAlgebra

julia> R,(x,y)=ZZ[:x,:y]
(Multivariate polynomial ring in 2 variables over integers, AbstractAlgebra.Generic.MPoly{BigInt}[x, y])

julia> div(R(-1),R(2))
-1
The problem is the missing div with RoundDown. I'd say the division just depends on a monomial ordering.

What is the definition of div? With or without RoundDown?

Or, better, what is the expected outcome? Merely div(x, y) == div(x, y, RoundDown) or more/ other features? div was intended as a euclidean operation, thus does not really apply even to univariate over ZZ. In case the division is exact: fine. I think currently, you get a reminder depending on the monomial ordering and then a quotient matching the remainder. But, unless special cases, there is no uniqueness or well-definedness about this operation. If one divides realtive to a Groebner basis, then at least the remainder being 0 is a well defined question, otherwise, the result is algorithm dependend...

-- Reply to this email directly or view it on GitHub: https://github.com/Nemocas/AbstractAlgebra.jl/issues/1402#issuecomment-1638405316 You are receiving this because you commented.

Message ID: @.***>

SoongNoonien commented 11 months ago

Or, better, what is the expected outcome?

I'd say one would expect to get the first component of divrem, which is documented to

Return a tuple (q,r) such that f=qg+r, where the coefficients of terms of r whose monomials are divisible by the leading monomial of g are reduced modulo the leading coefficient of g (according to the Euclidean function on the coefficients).

While "reduced modulo the leading coefficient" is maybe not so ideal, because the usual div in Julia does things a bit differently:

julia> divrem(-1,2)
(0, -1)

julia> divrem(-1,2,RoundDown)
(-1, 1)

So for polynomial rings over ZZ divrem(f, g, m::RoundingMode) should return a tuple (q,r) such that f=qg+r and every coefficient c of a term c*t of r where t is divisible by the leading monomial l of g is equal to rem(c,leading_coefficient(g),m). div(f, g, m::RoundingMode) should return the q, rem(f, g, m::RoundingMode) the r and mod(f, g) should be equal to rem(f, g, RoundDown). Is this really algorithm dependent?

mgkurtz commented 11 months ago

Current state of the functions div, rem, divrem, gcd, gcdx in non-euclidean rings as of this issue, #1401, https://github.com/Nemocas/Nemo.jl/issues/1474, and https://github.com/Nemocas/Nemo.jl/issues/1509:

Originally those functions were intended for euclidean rings only, and it is mathematically not entirely clear, what and if they shall return in the non-euclidean case.
Despite that, they often do return some results, which in some cases, may even be useful for some people.
Sometimes they also give some error or do not terminate.
The behavior may depend on whether Nemo is loaded or only AbstractAlgebra.
This confuses some people, at least people as @SoongNoonien and me.

The easiest thing we could do, seems to have those functions return an explanatory error, or at least a warning for non-euclidean rings. If necessary, one can also give them a definition in special cases like (multivariate) polynomial rings over euclidean rings.

lgoettgens commented 11 months ago

Please furthermore note that AbstractAlgebra and Nemo define their own versions of div etc., different from them in Base. https://github.com/Nemocas/AbstractAlgebra.jl/blob/bfa185a7c074b20527009e039ad45be8ab1bdd7a/src/AbstractAlgebra.jl#L48-L67

Nemocas / AbstractAlgebra.jl

`divrem` with polynomials #1402