Bugs in the computation of Groebner bases over the integers

[simon-king-jena]

A bug report on 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

Upstream: Fixed upstream, in a later stable release.

CC: @sagetrac-jakobkroeker @jpflori

Component: commutative algebra

Keywords: Groebner basis integer

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

[simon-king-jena]

comment:1

There is a new singular spkg at #8059. However, this does not solve the problem. The only difference is that now one has

sage: I.groebner_basis(algorithm='toy:buchberger2')
[2*x^2 + x*y, 3*x*y, 2*y^2]

Hence, the result is reduced (the first bug is gone), but still wrong.

[simon-king-jena]

comment:2

At least the problem with liftstd has disappeared in Singular-3-1-1.

But since the bug in slimgb persists, I reported upstream.

[simon-king-jena]

Changed upstream from Not yet reported upstream; Will do shortly. to Reported upstream. Little or no feedback.

[simon-king-jena]

Description changed:

--- 
+++ 
@@ -21,7 +21,7 @@
 [x^2*y, x*y^2, 2*x^2 + x*y, 3*x*y, 2*y^2]

-First bug +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.

@@ -60,7 +60,7 @@

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 +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.

[0a221ed2-778e-4119-9a6a-a69ef8f92850]

comment:4

Replying to @simon-king-jena:

There is a new singular spkg at #8059. However, this does not solve the problem. The only difference is that now one has sage: I.groebner_basis(algorithm='toy:buchberger2') [2*x^2 + x*y, 3*x*y, 2*y^2] Hence, the result is reduced (the first bug is gone), but still wrong.

Result is right because reduce is different in field and in ring (please read this book chapter 4).

xy!^2  is reduced to zero on [2x!^2 + xy, 3xy, 2y!^2] because xy!^2 - (y3xy-x2y!^2)=0.

So libsingular:slimgb and toy:buchberger2 are right, and singular:std and libsingular:std has bug.

[simon-king-jena]

comment:5

Replying to @sagetrac-duleorlovic:

Replying to @simon-king-jena:

There is a new singular spkg at #8059. However, this does not solve the problem. The only difference is that now one has sage: I.groebner_basis(algorithm='toy:buchberger2') [2*x^2 + x*y, 3*x*y, 2*y^2] Hence, the result is reduced (the first bug is gone), but still wrong.

Result is right because reduce is different in field and in ring (please read this book chapter 4).

xy!^2  is reduced to zero on [2x!^2 + xy, 3xy, 2y!^2] because xy!^2 - (y3xy-x2y!^2)=0.

I don't buy this and repeat that this is not a reduction. Martin, do you agree?

[simon-king-jena]

comment:6

Many thanks to Michael Brickenstein who explained here that our misunderstanding comes from the fact that Dusan expects to work with weak Gröbner bases - a notion that I was not aware of.

Singular computes a strong Gröbner basis. So, not a bug.

By the way, the remaining problem with slimgb is solved upstream: By now (i.e., with the current developer version and in the next official release), slimgb will raise an error when being called for an ideal over the integers.

[simon-king-jena]

Changed upstream from Reported upstream. Little or no feedback. to Fixed upstream, in a later stable release.

[ea1d0bf8-c27a-4548-8cb7-de0b1d02441a]

comment:12

In sage Singular was recently upgraded to 3.1.7.

1. What I do not understand, a slimgb call in standalone Singular 3.1.7 raises now an error

ring rng = integer,(x,y),dp;
option("redSB");
ideal I = 4*x^2*y^2 + 2*x*y^3 + 3*x*y, 2*x^2 + x*y, 2*y^2;
slimgb(I);
//? not implemented for rings with rings as coeffients}}}

but the slimgb call in sage

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:slimgb')

succeeds. Why is that ??

2. if there is really a difference between strong and weak groebner basis, then at least the 'toy:buchberger','toy:buchberger2' and 'groebner_basis' documentation should be updated , hoping that nobody intermixes weak and strong groebner bases by accident. (new ticket?)

3. Remark: the liftstd bug seems fixed

[kcrisman]

comment:13

See https://groups.google.com/forum/#!topic/sage-devel/U1dsVFP-2PA