divrem with polynomials

[SoongNoonien]

Hi!
As mentioned in Nemocas/Nemo.jl#1509 and #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]

On Fri, Jul 14, 2023 at 12:38:59PM -0700, Martin Wagner wrote: Hi! As mentioned in Nemocas/Nemo.jl#1509 and #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: #1402 You are receiving this because you are subscribed to this thread. Message ID: ***@***.***>

[SoongNoonien]

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]

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: #1402 (comment) You are receiving this because you commented. Message ID: ***@***.***>

[SoongNoonien]

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]

Current state of the functions div, rem, divrem, gcd, gcdx in non-euclidean rings as of this issue, #1401, Nemocas/Nemo.jl#1474, and Nemocas/Nemo.jl#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]

Please furthermore note that AbstractAlgebra and Nemo define their own versions of div etc., different from them in Base.

AbstractAlgebra.jl/src/AbstractAlgebra.jl

Lines 48 to 67 in bfa185a

	################################################################################
	#
	# Import/export philosophy
	#
	# For certain julia Base types and Base function, e.g. BigInt and div or exp, we
	# need a different behavior. These functions are not exported.
	#
	# Take for example exp. Since exp is not imported from Base, there are two exp
	# functions, AbstractAlgebra.exp and Base.exp. Inside AbstractAlgebra, exp
	# will always refer to AbstractAlgebra.exp. When calling the function, one
	# should just use "exp" without namespace qualifcation.
	#
	# On the other hand, if an AbstractAlgebra type wants to add a method to exp,
	# it must add a method to "Base.exp".
	#
	# The rational for this is as follows: If we do "using AbstractAlgebra" in the
	# REPL, then "exp" will refer to the Base.exp. So if we want to make exp(a)
	# work in the REPL for an AbstractAlgebra type, we have to overload Base.exp.
	#
	################################################################################