#12529: libsingular reduces polynomials incompletely
-----------------------------------+----------------------------------------
Reporter: SimonKing | Owner: malb
Type: defect | Status: new
Priority: blocker | Milestone: sage-5.0
Component: commutative algebra | Keywords: multivariate polynomial
reduction
Work_issues: | Upstream: N/A
Reviewer: | Author:
Merged: | Dependencies:
-----------------------------------+----------------------------------------
On [http://groups.google.com/group/sage-
support/browse_thread/thread/b90fbb622ddb55ab sage-support], Oleksandr
Kazymyrov reported the following:
{{{
sage: bits=3
sage:
sage: k=GF(2^bits,'a')
sage: P=PolynomialRing(k,1+bits+bits+bits-1+(1<<bits),['y'] +
['a{0}'.format(g) for g in xrange(bits)] + ['b{0}'.format(g) for g in
xrange(bits)] + ['c{0}'.format(g) for g in xrange(1,bits)] +
['p{0}'.format(g) for g in xrange(1<<bits)])
sage:
sage: A1=sum([P('(a{0})*y^{0}'.format(g)) for g in xrange(bits)])
sage: A2=sum([P('(b{0})*y^{0}'.format(g)) for g in xrange(bits)])
sage: A3=sum([P('(c{0})*y^{0}'.format(g)) for g in xrange(1,bits)])
sage: pol = sum([P('(p{0})*y^{0}'.format(g)) for g in xrange(1<<bits)])
sage: pol=pol.subs({P("y"):A2})
sage: pol=A1.subs({P("y"):pol})
sage: pol=pol+A3
sage: pol.mod(P("y^{0}+y".format(1<<bits)))
y^7*a2*b1^14*p7^2 + y^7*a2*b2^14*p7^2 + y^10*a2*b1^10*p5^2 +
y^8*a2*b0^4*b1^8*p6^2 + y^8*a2*b0^8*b2^4*p6^2 + y^14*a1*b2^7*p7 +
y^6*a2*b0^8*b1^6*p7^2 + y^6*a2*b1^8*b2^6*p7^2 + y^6*a2*b0^2*b1^4*b2^8*p7^2
+ y^6*a2*b0^4*b2^10*p7^2 + y^9*a2*b0^2*b2^8*p5^2 + y^13*a1*b1*b2^6*p7 +
y^5*a2*b0^2*b1^12*p7^2 + y^5*a2*b0^4*b1^8*b2^2*p7^2 +
y^5*a2*b0^8*b2^6*p7^2 + y^5*a2*b1^2*b2^12*p7^2 + y^12*a2*b2^6*p3^2 +
y^8*a2*b0^2*b1^8*p5^2 + y^6*a2*b1^4*b2^8*p6^2 + y^12*a1*b1^2*b2^5*p7 +
y^12*a1*b0*b2^6*p7 + y^4*a2*b0^10*b1^4*p7^2 + y^4*a2*b0^12*b2^2*p7^2 +
y^4*a2*b1^10*b2^4*p7^2 + y^4*a2*b0^4*b1^2*b2^8*p7^2 + y^9*a2*b2^8*p4^2 +
y^12*a1*b2^6*p6 + y^5*a2*b1^12*p6^2 + y^11*a1*b1^3*b2^4*p7 +
y^3*a2*b0^4*b1^10*p7^2 + y^3*a2*b0^8*b1^2*b2^4*p7^2 +
y^3*a2*b1^4*b2^10*p7^2 + y^3*a2*b0^2*b2^12*p7^2 + y^10*a2*b1^2*b2^4*p3^2 +
y^8*a2*b1^8*p4^2 + y^6*a2*b2^10*p5^2 + y^4*a2*b0^8*b1^4*p6^2 +
y^10*a1*b1^4*b2^3*p7 + y^10*a1*b0*b1^2*b2^4*p7 + y^10*a1*b0^2*b2^5*p7 +
y^2*a2*b0^12*b1^2*p7^2 + y^2*a2*b1^12*b2^2*p7^2 +
y^2*a2*b0^2*b1^8*b2^4*p7^2 + y^2*a2*b0^6*b2^8*p7^2 + y^5*a2*b1^8*b2^2*p5^2
+ y^10*a1*b1^2*b2^4*p6 + y^3*a2*b2^12*p6^2 + y^9*a1*b1^5*b2^2*p7 +
y^9*a1*b0^2*b1*b2^4*p7 + y*a2*b0^6*b1^8*p7^2 + y*a2*b0^8*b1^4*b2^2*p7^2 +
y*a2*b0^10*b2^4*p7^2 + y*a2*b1^6*b2^8*p7^2 + y^8*a2*b1^4*b2^2*p3^2 +
y^8*a2*b0^2*b2^4*p3^2 + y^10*a1*b2^5*p5 + y^4*a2*b0^8*b2^2*p5^2 +
y^4*a2*b1^2*b2^8*p5^2 + y^2*a2*b1^8*b2^4*p6^2 + y^2*a2*b0^4*b2^8*p6^2 +
y^8*a1*b1^6*b2*p7 + y^8*a1*b0*b1^4*b2^2*p7 + y^8*a1*b0^3*b2^4*p7 +
a2*b0^14*p7^2 + y^9*a1*b1*b2^4*p5 + y^8*a1*b1^4*b2^2*p6 +
y^8*a1*b0^2*b2^4*p6 + y^7*a1*b1^7*p7 + y^8*a2*b2^4*p2^2 + y^6*a2*b1^6*p3^2
+ y^8*a1*b0*b2^4*p5 + y^2*a2*b0^8*b1^2*p5^2 + a2*b0^12*p6^2 +
y^6*a1*b0*b1^6*p7 + y^6*a1*b0^2*b1^4*b2*p7 + y^6*a1*b0^4*b2^3*p7 +
y^8*a1*b2^4*p4 + y^6*a1*b1^6*p6 + y^5*a1*b0^2*b1^5*p7 +
y^5*a1*b0^4*b1*b2^2*p7 + y^4*a2*b0^2*b1^4*p3^2 + y^4*a2*b0^4*b2^2*p3^2 +
y^6*a1*b1^4*b2*p5 + a2*b0^10*p5^2 + y^4*a1*b0^3*b1^4*p7 +
y^4*a1*b0^4*b1^2*b2*p7 + y^4*a1*b0^5*b2^2*p7 + y^5*a1*b1^5*p5 +
y^4*a1*b0^2*b1^4*p6 + y^4*a1*b0^4*b2^2*p6 + y^3*a1*b0^4*b1^3*p7 +
y^4*a2*b1^4*p2^2 + y^6*a1*b2^3*p3 + y^2*a2*b0^4*b1^2*p3^2 + a2*b0^8*p4^2 +
y^4*a1*b0*b1^4*p5 + y^2*a1*b0^5*b1^2*p7 + y^2*a1*b0^6*b2*p7 +
y^5*a1*b1*b2^2*p3 + y^4*a1*b1^4*p4 + y^2*a1*b0^4*b1^2*p6 + y*a1*b0^6*b1*p7
+ y^4*a2*b2^2*p1^2 + y^4*a1*b1^2*b2*p3 + y^4*a1*b0*b2^2*p3 + a2*b0^6*p3^2
+ y^2*a1*b0^4*b2*p5 + a1*b0^7*p7 + y^4*a1*b2^2*p2 + y^3*a1*b1^3*p3 +
y*a1*b0^4*b1*p5 + a1*b0^6*p6 + y^2*a2*b1^2*p1^2 + a2*b0^4*p2^2 +
y^2*a1*b0*b1^2*p3 + y^2*a1*b0^2*b2*p3 + a1*b0^5*p5 + y^2*a1*b1^2*p2 +
y*a1*b0^2*b1*p3 + a1*b0^4*p4 + y^2*a1*b2*p1 + a2*b0^2*p1^2 + a1*b0^3*p3 +
y*a1*b1*p1 + a1*b0^2*p2 + y^2*c2 + a2*p0^2 + a1*b0*p1 + y*c1 + a1*p0 + a0
}}}
The mod operation does not reduce all terms:
{{{
sage: pol.mod(P("y^{0}+y".format(1<<bits))).monomials()[3]
y^8*a2*b0^4*b1^8*p6^2
sage: pol.mod(P("y^{0}+y".format(1<<bits))).monomials()[2]
y^10*a2*b1^10*p5^2
}}}
However, a reduction of the single terms works:
{{{
sage:
pol.mod(P("y^{0}+y".format(1<<bits))).monomials()[2].mod(P("y^{0}+y".format(1<<bits)))
y^3*a2*b1^10*p5^2
}}}
Note that Singular does the reduction right:
{{{
sage:
singular(pol).NF(singular(P.ideal(P("y^{0}+y".format(1<<bits)))).std())
y^7*a2*b1^14*p7^2+y^7*a2*b2^14*p7^2+y^6*a2*b0^8*b1^6*p7^2+y^6*a2*b1^8*b2^6*p7^2+y^6*a2*b0^2*b1^4*b2^8*p7^2+y^6*a2*b0^4*b2^10*p7^2+y^5*a2*b0^2*b1^12*p7^2+y^5*a2*b0^4*b1^8*b2^2*p7^2+y^5*a2*b0^8*b2^6*p7^2+y^5*a2*b1^2*b2^12*p7^2+y^6*a2*b1^4*b2^8*p6^2+y^4*a2*b0^10*b1^4*p7^2+y^4*a2*b0^12*b2^2*p7^2+y^4*a2*b1^10*b2^4*p7^2+y^4*a2*b0^4*b1^2*b2^8*p7^2+y^5*a2*b1^12*p6^2+y^3*a2*b0^4*b1^10*p7^2+y^3*a2*b0^8*b1^2*b2^4*p7^2+y^3*a2*b1^4*b2^10*p7^2+y^3*a2*b0^2*b2^12*p7^2+y^6*a2*b2^10*p5^2+y^4*a2*b0^8*b1^4*p6^2+y^2*a2*b0^12*b1^2*p7^2+y^2*a2*b1^12*b2^2*p7^2+y^2*a2*b0^2*b1^8*b2^4*p7^2+y^2*a2*b0^6*b2^8*p7^2+y^5*a2*b1^8*b2^2*p5^2+y^3*a2*b2^12*p6^2+y*a2*b0^6*b1^8*p7^2+y*a2*b0^8*b1^4*b2^2*p7^2+y*a2*b0^10*b2^4*p7^2+y*a2*b1^6*b2^8*p7^2+y^4*a2*b0^8*b2^2*p5^2+y^4*a2*b1^2*b2^8*p5^2+y^2*a2*b1^8*b2^4*p6^2+y^2*a2*b0^4*b2^8*p6^2+a2*b0^14*p7^2+y^3*a2*b1^10*p5^2+y*a2*b0^4*b1^8*p6^2+y*a2*b0^8*b2^4*p6^2+y^7*a1*b1^7*p7+y^7*a1*b2^7*p7+y^6*a2*b1^6*p3^2+y^2*a2*b0^8*b1^2*p5^2+y^2*a2*b0^2*b2^8*p5^2+a2*b0^12*p6^2+y^6*a1*b0*b1^6*p7+y^6*a1*b0^2*b1^4*b2*p7+y^6*a1*b0^4*b2^3*p7+y^6*a1*b1*b2^6*p7+y^5*a2*b2^6*p3^2+y*a2*b0^2*b1^8*p5^2+y^6*a1*b1^6*p6+y^5*a1*b0^2*b1^5*p7+y^5*a1*b0^4*b1*b2^2*p7+y^5*a1*b1^2*b2^5*p7+y^5*a1*b0*b2^6*p7+y^4*a2*b0^2*b1^4*p3^2+y^4*a2*b0^4*b2^2*p3^2+y^2*a2*b2^8*p4^2+y^6*a1*b1^4*b2*p5+a2*b0^10*p5^2+y^5*a1*b2^6*p6+y^4*a1*b0^3*b1^4*p7+y^4*a1*b0^4*b1^2*b2*p7+y^4*a1*b0^5*b2^2*p7+y^4*a1*b1^3*b2^4*p7+y^3*a2*b1^2*b2^4*p3^2+y*a2*b1^8*p4^2+y^5*a1*b1^5*p5+y^4*a1*b0^2*b1^4*p6+y^4*a1*b0^4*b2^2*p6+y^3*a1*b0^4*b1^3*p7+y^3*a1*b1^4*b2^3*p7+y^3*a1*b0*b1^2*b2^4*p7+y^3*a1*b0^2*b2^5*p7+y^4*a2*b1^4*p2^2+y^6*a1*b2^3*p3+y^2*a2*b0^4*b1^2*p3^2+a2*b0^8*p4^2+y^4*a1*b0*b1^4*p5+y^3*a1*b1^2*b2^4*p6+y^2*a1*b0^5*b1^2*p7+y^2*a1*b0^6*b2*p7+y^2*a1*b1^5*b2^2*p7+y^2*a1*b0^2*b1*b2^4*p7+y^5*a1*b1*b2^2*p3+y*a2*b1^4*b2^2*p3^2+y*a2*b0^2*b2^4*p3^2+y^4*a1*b1^4*p4+y^3*a1*b2^5*p5+y^2*a1*b0^4*b1^2*p6+y*a1*b0^6*b1*p7+y*a1*b1^6*b2*p7+y*a1*b0*b1^4*b2^2*p7+y*a1*b0^3*b2^4*p7+y^4*a2*b2^2*p1^2+y^4*a1*b1^2*b2*p3+y^4*a1*b0*b2^2*p3+a2*b0^6*p3^2+y^2*a1*b0^4*b2*p5+y^2*a1*b1*b2^4*p5+y*a1*b1^4*b2^2*p6+y*a1*b0^2*b2^4*p6+a1*b0^7*p7+y^4*a1*b2^2*p2+y*a2*b2^4*p2^2+y^3*a1*b1^3*p3+y*a1*b0^4*b1*p5+y*a1*b0*b2^4*p5+a1*b0^6*p6+y^2*a2*b1^2*p1^2+a2*b0^4*p2^2+y^2*a1*b0*b1^2*p3+y^2*a1*b0^2*b2*p3+y*a1*b2^4*p4+a1*b0^5*p5+y^2*a1*b1^2*p2+y*a1*b0^2*b1*p3+a1*b0^4*p4+y^2*a1*b2*p1+a2*b0^2*p1^2+a1*b0^3*p3+y*a1*b1*p1+a1*b0^2*p2+y^2*c2+a2*p0^2+a1*b0*p1+y*c1+a1*p0+a0
}}}
So, it seems to me that the problem is in libsingular, not in Singular.
I guess the reduction is supposed to reduce the tail as well - if tail
reduction is not done by default, then the doc should mention it.
I think those basic arithmetic failures generally are blockers.
--
Ticket URL: <http://trac.sagemath.org/sage_trac/ticket/12529>
Sage <http://www.sagemath.org>
Sage: Creating a Viable Open Source Alternative to Magma, Maple, Mathematica,
and MATLAB
--
You received this message because you are subscribed to the Google Groups
"sage-trac" group.
To post to this group, send email to [email protected].
To unsubscribe from this group, send email to
[email protected].
For more options, visit this group at
http://groups.google.com/group/sage-trac?hl=en.
