Bug in divrem(a::MPoly{T}, b::MPoly{T}) where {T <: RingElement}?

[heiderich]

With Nemo.QQ as a coefficient field I get:

julia> R,vR = PolynomialRing(Nemo.QQ,["x"]); x = vR[1]
x

julia> q,r = divrem(x,2*x)
(1/2, 0)

However with AbstractAlgebra.QQ I get:

julia> R,vR = PolynomialRing(AbstractAlgebra.QQ,["x"]); x = vR[1]
x

julia> q,r = divrem(x,2*x)
(0//1, x)

Is the latter intended? I would expect an output similar to the one with Nemo.QQ.

The same problem occurs with the array version:

julia> R,vR = PolynomialRing(AbstractAlgebra.QQ,["x"]); x = vR[1]
x

julia> q,r = divrem(x,[2*x])
(AbstractAlgebra.Generic.MPoly{Rational{BigInt}}[0//1], x)

[wbhart]

That certainly looks like a bug in AbstractAlgebra. I'll investigate.

By the way, you can write:

R, (x, ) = PolynomialRing(QQ, ["x"])

if you want to.

[heiderich]

Thank you very much, both for the syntax hint and for looking into this issue!

[wbhart]

It's due to a bug in Julia. divrem(BigInt(1)//1, BigInt(2)//1) returns the wrong answer.

[wbhart]

It would be possible to work around that by having a divrem inside AbstractAlgebra which defines it the right way. We do a similar thing for exp and sqrt. We probably should do the same thing for inv and det as well, and now div and divrem.

[fieker]

On Mon, Jan 28, 2019 at 08:45:43AM -0800, wbhart wrote: It's due to a bug in Julia. divrem(BigInt(2)//1, BigInt(1)//1) returns the wrong answer.

For e, it returns (2, 0) which I would regard as correct. What should happen? Its the same as I get for fmpq's

…

-- You are receiving this because you are subscribed to this thread. Reply to this email directly or view it on GitHub: #249 (comment)

[wbhart]

Sorry, I had a typo and updated the ticket, which you don't see in the email.

I was dividing 1 by 2, not the other way around. Julia returns 0 not 1/2.

[heiderich]

@wbhart: What do you expect divrem(BigInt(1)//1, BigInt(2)//1) to return?

Mathematically BigInt(1)//1 is an element of the quotient field Q of Z. Every field is an Euclidean domain with respect to the degree function g defined by g(0) = 0 and g(x) = 1 for all x!=0. With this Euclidean structure you would expect divrem(1//1,2//1) to return 1//2, 0. This seems however not to be the case. This might be considered a bug. Is this what you mean?

In the issue JuliaLang/julia#9283 @denisrosset already pointed out that divrem is not really Euclidean division.

I see two ways out of it: Julia is changes divrem or we call a function that actually does Euclidean division.

[wbhart]

@heiderich That's what I mean.

Julia considers the rationals to be a version of the reals, but that doesn't explain to me why they choose this kind of division. in fact it is more Euclidean than Euclidean division, since it is the division Euclid himself used. I prefer Euclid's definition for gcd, but it's inconvenient to have his definition for division over Q.

Of course if we want to fix this, we have to define our own divrem inside AbstractAlgebra (and not export it). You can look at how we handle sqrt and exp to see how to do this.

[heiderich]

I think #252 should fix this.