Opened 9 years ago

Closed 5 weeks ago

#12529 closed defect (fixed)

libsingular reduces polynomials incompletely

Reported by: SimonKing Owned by: malb
Priority: major Milestone: sage-9.3
Component: commutative algebra Keywords: multivariate polynomial reduction
Cc: malb Merged in:
Authors: Samuel Lelièvre Reviewers: Kiran Kedlaya
Report Upstream: N/A Work issues:
Branch: 5b3253a (Commits) Commit: 5b3253a14e46a97e783d5800cc20898bd1bb6957
Dependencies: Stopgaps: todo

Description (last modified by slelievre)

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.

Change History (14)

comment:1 Changed 9 years ago by jdemeyer

  • Priority changed from blocker to critical

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

comment:2 Changed 7 years ago by jdemeyer

  • Milestone changed from sage-5.11 to sage-5.12

comment:3 Changed 7 years ago by vbraun_spam

  • Milestone changed from sage-6.1 to sage-6.2

comment:4 Changed 7 years ago by vbraun_spam

  • Milestone changed from sage-6.2 to sage-6.3

comment:5 Changed 6 years ago by vbraun_spam

  • Milestone changed from sage-6.3 to sage-6.4

comment:6 Changed 5 years ago by jakobkroeker

  • Stopgaps set to todo

comment:7 Changed 3 months ago by kedlaya

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

comment:8 Changed 2 months ago by slelievre

  • Milestone changed from sage-6.4 to sage-9.3
  • Priority changed from critical to major

The bug exists in Sage <= 9.0 but not in Sage >= 9.1.

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

In Sage <= 9.0 we get 14 instead of 7.

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.

Version 0, edited 2 months ago by slelievre (next)

comment:9 Changed 2 months ago by kedlaya

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

comment:10 Changed 2 months ago by slelievre

  • Authors set to Samuel Lelièvre
  • Branch set to public/12529
  • Commit set to 5b3253a14e46a97e783d5800cc20898bd1bb6957
  • Description modified (diff)
  • Milestone changed from sage-9.3 to sage-9.2
  • Status changed from new to needs_review

Please review and add reviewer name.

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


New commits:

5b3253aAdd doctest for remainder in multivariate polynomial ring

comment:11 Changed 2 months ago by kedlaya

  • Reviewers set to Kiran Kedlaya
  • Status changed from needs_review to positive_review

No complaints from patchbot, nor from me.

comment:12 Changed 2 months ago by slelievre

  • Description modified (diff)

Thanks!

comment:13 Changed 6 weeks ago by mkoeppe

  • Milestone changed from sage-9.2 to sage-9.3

comment:14 Changed 5 weeks ago by vbraun

  • Branch changed from public/12529 to 5b3253a14e46a97e783d5800cc20898bd1bb6957
  • Resolution set to fixed
  • Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.