#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: Reported upstream. Little or
no feedback.
Reviewer: | Merged:
Work_issues: |
-----------------------------------+----------------------------------------
Description changed by SimonKing:
Old description:
> 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
> }}}
New description:
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__''' (fixed with Singular-3-1-1)
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__''' (fixed with Singular-3-1-1)
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#comment:3>
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.
