#9645: Bugs in the computation of Groebner bases over the integers
-----------------------------------+----------------------------------------
Reporter: SimonKing | Owner: malb
Type: defect | Status: new
Priority: critical | Milestone: sage-5.0
Component: commutative algebra | Keywords: Groebner basis integer
Author: | Upstream: Not yet reported upstream;
Will do shortly.
Reviewer: | Merged:
Work_issues: |
-----------------------------------+----------------------------------------
A bug report on [http://groups.google.com/group/sage-
devel/browse_thread/thread/46124695d2f7469a sage-devel] made me play
around with the following example:
{{{
sage: R.<x,y>=PolynomialRing(ZZ,2)
sage: I = R*(4*x^2*y^2+2*x*y^3+3*x*y,2*x^2+x*y,2*y^2)
sage: I.groebner_basis(algorithm='libsingular:std')
[x^2*y, x*y^2, 2*x^2 + x*y, 3*x*y, 2*y^2]
sage:
(I.groebner_basis(algorithm='libsingular:std')*R).interreduced_basis()
[x^2*y, x*y^2, 2*x^2 + x*y, 3*x*y, 2*y^2]
sage: I.groebner_basis(algorithm='libsingular:slimgb')
[2*x^2 + x*y, 3*x*y, 2*y^2]
sage:
(I.groebner_basis(algorithm='libsingular:slimgb')*R).interreduced_basis()
[2*x^2 + x*y, 3*x*y, 2*y^2]
sage:
(I.groebner_basis(algorithm='toy:buchberger')*R).interreduced_basis()
[2*x^2 + x*y, 3*x*y, 2*y^2]
sage: I.groebner_basis(algorithm='toy:buchberger2')
[4*x^2*y^2 + 2*x*y^3 + 3*x*y, 2*x^2 + x*y, 2*y^2]
sage:
(I.groebner_basis(algorithm='toy:buchberger2')*R).interreduced_basis()
[2*x^2 + x*y, 3*x*y, 2*y^2]
sage: I.groebner_basis(algorithm='magma')
[x^2*y, x*y^2, 2*x^2 + x*y, 3*x*y, 2*y^2]
}}}
'''__First bug__'''
The documentation suggests that {{{toy:buchberger2}}} is supposed to
return a reduced Groebner basis, but it doesn't. So, to the very least,
the documentation is a little unclear.
'''__Second bug__'''
The five algorithms return two ''different'' reduced Groebner bases. So,
at least one of them must be wrong.
{{{libsingular:std}}} and {{{magma}}} agree on this result:
{{{
sage: G1 = I.groebner_basis(algorithm='libsingular:std'); G1
[x^2*y, x*y^2, 2*x^2 + x*y, 3*x*y, 2*y^2]
}}}
while {{{libsingular:slimgb}}}, {{{toy:buchberger}}} and
{{{toy:buchberger2}}} agree on this result:
{{{
sage: G2 = I.groebner_basis(algorithm='libsingular:slimgb'); G2
[2*x^2 + x*y, 3*x*y, 2*y^2]
}}}
The following suggests that at least answer {{{G2}}} is wrong:
{{{
sage: [g.reduce(G2) for g in G1]
[x^2*y, x*y^2, 0, 0, 0]
sage: [g.reduce(G1) for g in G2]
[0, 0, 0]
}}}
Let us check that indeed the element {{{x*y^2}}} belongs to the original
ideal:
{{{
sage: y*I.0 -2*y^3*I.1 -x*I.2
x*y^2
}}}
Conclusion: '''Under the assumption that there is no bug in reduce and the
basic arithmetic, it is proven that slimgb and toy:buchberger(2) give a
wrong answer.'''
'''__Third bug__'''
Of course, if {{{G1}}} is a Groebner basis then all of its elements must
belong to the ideal. Singular provides a command to express the Groebner
basis elements as combinations of the given ideal generators:
{{{liftstd}}}.
But {{{liftstd}}} apparently gives a wrong answer:
{{{
sage: r = singular(R)
sage: i = singular(I)
sage: singular.eval('matrix m')
'matrix m;'
sage: print singular.eval('liftstd(%s,m)'%i.name())
_[1]=2*y^2
_[2]=-3*x*y
_[3]=2*x^2+x*y
_[4]=x*y^2
_[5]=x^2*y
sage: singular('m')
0,-1, 0,y, -3*x-y,
0,2*y^2,1,-2*y^3,2*y^3+5*y,
1,0, 0,-x, -x-2*y
}}}
So, up to order and sign, the answer given by {{{liftstd}}} coincides with
{{{G1}}}. Now, the matrix {{{m}}} should transform the list of ideal
generators into the Groebner basis. But it does not for the element
{{{x^2*y}}}:
{{{
sage: print singular.eval('matrix(%s)*m'%i.name())
_[1,1]=2*y^2
_[1,2]=-3*x*y
_[1,3]=2*x^2+x*y
_[1,4]=x*y^2
_[1,5]=-12*x^3*y^2-6*x^2*y^3+x^2*y-4*y^3
}}}
So, there is a bug in {{{liftstd}}} as well. At least, it is possible to
verify that {{{x^2*y}}} (and therefore all of {{{G1}}}) belongs to the
ideal:
{{{
sage: 2*y*I.1 - x*I.0 + (2*x^3 + x^2*y - x)*I.2
x^2*y
}}}
--
Ticket URL: <http://trac.sagemath.org/sage_trac/ticket/9645>
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.
