AbstractAlgebra.jl icon indicating copy to clipboard operation
AbstractAlgebra.jl copied to clipboard

`divrem` with polynomials

Open SoongNoonien opened this issue 11 months ago • 6 comments

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?

SoongNoonien avatar Jul 14 '23 19:07 SoongNoonien