exact division in polynomial rings

mantepse commented 2 weeks ago

Steps To Reproduce

sage: Q.<z> = Frac(QQ['z'])
sage: R.<x,y> = Q[]
sage: r = x*y - (2*z-1)/(z^2+z+1) * x + y/z
sage: p = r * (x + z*y - 1/z^2)
sage: p // p

Expected Behavior

Should give 1.

Actual Behavior

0*x^2*y + (0*z)*x*y^2

Additional Information

No response

Environment

OS: Ubuntu 20.04
Sage Version: 10.5.beta8

Checklist

[X] I have searched the existing issues for a bug report that matches the one I want to file, without success.
[X] I have read the documentation and troubleshoot guide

vincentmacri commented 2 weeks ago

I tried responding the sage-devel post about this but I haven't posted there before so I think it needs moderator approval before going through.

I can reproduce this in Sage 10.4, and I found some additional weird behaviour:

Doing p // p a second time gives 0.
Doing p / p causes a segmentation fault and crashes Sage.

Do you get the same thing?

mantepse commented 2 weeks ago

Yes :-( also in sage cell, which has Sage 10.2

mantepse commented 2 weeks ago

Possibly related: #35428 and #35886

saraedum commented 2 weeks ago

Copying what I just wrote to sage-devel here:

Versions 9.5 - 10.4 produce the output you posted. Versions 9.0 - 9.4 take about 6 minutes and produce "1". Versions 7.0 - 8.8 do not terminate within 12 minutes.

Fwiw, you can test something like this "interactively" in bash or zsh (assuming you have a good amount of disk space):

cat - | eval `echo -n 'tee -p'; for major in $(seq 7 10); do for minor in $(seq 0 9); do echo -n " >(docker run --rm -i sagemath/sagemath:$major.$minor sage -q | sed --unbuffered s/^/\[$major.$minor\]/ )"; done; done`

mantepse commented 2 weeks ago

I inserted some print statements in MPolynomial_libsingular._floordiv_. Here is the code: https://github.com/sagemath/sage/blob/209ae4c3a438d27f552bde829cbe91edde488578/src/sage/rings/polynomial/multi_polynomial_libsingular.pyx#L4155-L4204

Apparently, the result of p_Divide in line 4190 returns something "!= NULL" (the branch in 4194 is not executed). Curiously, with the print statements I don't get a crash anymore, but always 0.

mantepse commented 2 weeks ago

Copying what I just wrote to sage-devel here:

Versions 9.5 - 10.4 produce the output you posted. Versions 9.0 - 9.4 take about 6 minutes and produce "1". Versions 7.0 - 8.8 do not terminate within 12 minutes.

Fwiw, you can test something like this "interactively" in bash or zsh (assuming you have a good amount of disk space):
cat - | eval `echo -n 'tee -p'; for major in $(seq 7 10); do for minor in $(seq 0 9); do echo -n " >(docker run --rm -i sagemath/sagemath:$major.$minor sage -q | sed --unbuffered s/^/\[$major.$minor\]/ )"; done; done`

Cool! I don't have docker (yet), but that information is extremely valuable.

I'm going to see whether floordiv was robust in 9.4 and see what changed since then. In floordiv itself I don't see much change, though. r has been replaced by r.cf in several places.

I suspect that 9.4 did not use singular for these rings.

mantepse commented 2 weeks ago

Unfortunately, I cannot build 9.4 on my computer (I'm on Ubuntu 22.04.5 LTS; cysignals-1.10.3 and linbox-1.6.3.p1 fail to build) and I'm not sure whether I can afford to get docker right now.

However, I do have a suspect, which is #16567 and was merged in 9.5.beta7.

@saraedum, could you check in 9.4:

sage: Q.<z> = Frac(QQ['z'])
sage: R.<x,y> = Q[]
sage: type(R)

@miguelmarco, can you help? I have never used singular, so I really have no idea how to fix this.

mantepse commented 2 weeks ago

More info: after p_Divide in line 4190, errorreported equals 1 and sage.libs.singular.singular.error_messages is ['conversion error: denominator!= 1'].

Does that mean that singular cannot do this division?

maxale commented 2 weeks ago

Looks like duplicate of #38555

saraedum commented 2 weeks ago

I'm not sure whether I can afford to get docker right now.

I'm on Zulip if you need any assistance with that.

On 9.4:

sage: sage: Q.<z> = Frac(QQ['z'])
....: sage: R.<x,y> = Q[]
....: sage: type(R)
....:
<class 'sage.rings.polynomial.multi_polynomial_ring.MPolynomialRing_polydict_domain_with_category'>

miguelmarco commented 1 week ago

This seems related (and might be easier to debug because it crashes and gives a trace):

sage: Q.<z> = Frac(QQ['z'])
sage: R.<x,y> = Q[]
sage: r = x*y - (2*z-1)/(z^2+z+1) * x + y/z
sage: p = r * (x + z*y - 1/z^2)
sage: p.quo_rem(p)

sagemath / sage