libsingular reduces polynomials incompletely

[simon-king-jena]

Condensed version of a report by Oleksandr Kazymyrov on sage-support.

Define g by modding out in a multivariate polynomial ring:

sage: gens = 'y a0 a1 a2 b0 b1 b2 c1 c2 d0 d1 d2 d3 d4 d5 d6 d7'.split()
sage: R = PolynomialRing(GF(8), 17, gens)
sage: R.inject_variables(verbose=False)
sage: A, B, C = a0 + a1*y + a2*y^2, b0 + b1*y + b2*y^2, c1*y + c2*y^2
sage: D = d0 + d1*y + d2*y^2 + d3*y^3 + d4*y^4 + d5*y^5 + d6*y^6 + d7*y^7
sage: F = D.subs({y: B})
sage: G = A.subs({y: F}) + C
sage: g = G.mod(y^8 + y)

After modding out by a polynomial of degree 8 in y,
the degree of g in y should be at most 7.

Up to Sage 9.1.rc1:

sage: g.degree(y)
14

After #27508 (Force tail reduction in polynomial quotient ring),
merged in Sage 9.1.rc2:

sage: g.degree(y)
7

The problem was libsingular not doing tail reduction
when calling Singular.

This ticket adds the above example as a doctest.

CC: @malb

Component: commutative algebra

Keywords: multivariate polynomial reduction

Stopgaps: todo

Author: Samuel Lelièvre

Branch/Commit: 5b3253a

Reviewer: Kiran Kedlaya

Issue created by migration from https://trac.sagemath.org/ticket/12529

[jdemeyer]

comment:1

I don't believe all basic arithmetic failures should be blockers, and it's dubious that this issue is even about "basic" arithmetic.

[sagetrac-jakobkroeker]

Stopgaps: todo

[kedlaya]

comment:7

I just tried this and got an answer consistent with Singular. Maybe close this as a duplicate?

[slel]

comment:8

Condensed version of the initial report, as a tentative doctest:

sage: gens = 'y a0 a1 a2 b0 b1 b2 c1 c2 d0 d1 d2 d3 d4 d5 d6 d7'.split()
sage: R = PolynomialRing(GF(8), 17, gens)
sage: R.inject_variables(verbose=False)
sage: A, B, C = a0 + a1*y + a2*y^2, b0 + b1*y + b2*y^2, c1*y + c2*y^2
sage: D = d0 + d1*y + d2*y^2 + d3*y^3 + d4*y^4 + d5*y^5 + d6*y^6 + d7*y^7
sage: F = D.subs({y: B})
sage: G = A.subs({y: F}) + C
sage: g = G.mod(y^8 + y)
sage: g.degree(y)
7

This was fixed by #27508 (Force tail reduction in polynomial quotient ring).

It was merged in Sage 9.1.rc2,
from which version on we get the correct value: 7.

In Sage <= 9.1.rc1, we get an incorrect value: 14.

If someone can suggest where to locate this doctest,
I can push a branch.

Priority down from critical to major:
bug fixed, only a doctest is needed.

[kedlaya]

comment:9

I would suggest to put the doctest in sage/rings/polynomial/polynomial_element.pyx under mod or __mod__.

[slel]

Author: Samuel Lelièvre

[slel]

Commit: 5b3253a

[slel]

comment:10

Please review and add reviewer name.

Let's see if this can get in Sage 9.2.

---

New commits:

5b3253a

Add doctest for remainder in multivariate polynomial ring

[slel]

Branch: public/12529

[kedlaya]

comment:11

No complaints from patchbot, nor from me.

[kedlaya]

Reviewer: Kiran Kedlaya

[slel]

comment:12

Thanks!

[vbraun]

Changed branch from public/12529 to 5b3253a