Groebner basis step by step

I have a system of 26 polynomial equations with 16 variables. According to the following sage computation, the Groebner basis is trivial (over the rational). The computation is very quick (less than 100ms), so I expect the absence of solution to be observable by hand. In order to obtain such an observation:

Question: Is there a way to print the computation of the Groebner basis step by step?

sage: R.<y0,y1,y2,y3,y4,y5,y6,y7,y8,x0,x1,x2,x3,x4,x5,x6>=PolynomialRing(QQ,16)
sage: Id=Ideal(x1 + 7/5*x3 + 7/5*x5 - 4/125,
....:  x0 + x2 + 7/5*x4 + 7/5*x6 - 4/125,
....:  5*y0 + 5*y1 + 7*y2 + 7*y6 + 1/5,
....:  25*y0^2 + 25*y1^2 + 35*y2^2 + 35*y6^2 - 4/5,
....:  5*y0^3 + 5*y1^3 + 7*y2^3 + 7*y6^3 - y0^2 + 1/125,
....:  5*y0*y1^2 + 5*y1*y3^2 + 7*y2*y4^2 + 7*y6*y7^2 + 1/125,
....:  5*x1*y1 - y1^2 + 7*x3*y2 + 7*x5*y6 + 1/125,
....:  5*y0*y2^2 + 5*y1*y4^2 + 7*y2*y5^2 + 7*y6*y8^2 - x0 + 1/125,
....:  5*x0*y0 + 5*x2*y1 + 7*x4*y2 - y2^2 + 7*x6*y6 + 1/125,
....:  5*y1 + 5*y3 + 7*y4 + 7*y7 + 1/5,
....:  25*y0*y1 + 25*y1*y3 + 35*y2*y4 + 35*y6*y7 + 1/5,
....:  5*y0^2*y1 + 5*y1^2*y3 + 7*y2^2*y4 + 7*y6^2*y7 - y1^2 + 1/125,
....:  25*y1^2 + 25*y3^2 + 35*y4^2 + 35*y7^2 - 4/5,
....:  5*y1^3 + 5*y3^3 + 7*y4^3 + 7*y7^3 - x1 + 1/125,
....:  5*x1*y3 - y3^2 + 7*x3*y4 + 7*x5*y7 + 1/125,
....:  5*y1*y2^2 + 5*y3*y4^2 + 7*y4*y5^2 + 7*y7*y8^2 - x2 + 1/125,
....:  5*x0*y1 + 5*x2*y3 + 7*x4*y4 - y4^2 + 7*x6*y7 + 1/125,
....:  7*y2 + 7*y4 + 49/5*y5 + 49/5*y8 + 7/25,
....:  35*y0*y2 + 35*y1*y4 + 49*y2*y5 + 49*y6*y8 + 7/25,
....:  5*y0^2*y2 + 5*y1^2*y4 + 7*y2^2*y5 + 7*y6^2*y8 - y2^2 + 1/125,
....:  35*y1*y2 + 35*y3*y4 + 49*y4*y5 + 49*y7*y8 + 7/25,
....:  5*y1^2*y2 + 5*y3^2*y4 + 7*y4^2*y5 + 7*y7^2*y8 - x3 + 1/125,
....:  5*x1*y4 - y4^2 + 7*x3*y5 + 7*x5*y8 + 1/125,
....:  35*y2^2 + 35*y4^2 + 49*y5^2 + 49*y8^2 - 18/25,
....:  5*y2^3 + 5*y4^3 + 7*y5^3 + 7*y8^3 - x4 + 1/125,
....:  5*x0*y2 + 5*x2*y4 + 7*x4*y5 - y5^2 + 7*x6*y8 + 1/125)
sage: %time G=Id.groebner_basis()
CPU times: user 78 ms, sys: 16 ms, total: 94 ms
Wall time: 78.6 ms
sage: G
[1]

edit retag close merge delete

At least 3 polynomials can be removed so that the Grobner basis will still remain trivial.

( 2021-05-06 16:11:09 +0200 )edit

Sort by » oldest newest most voted

To find out some details about what Singular is doing, you can run it with the prot option.

(To run the bundled Singular on Windows, run the SageMath Shell and enter Singular.)

option(redTail);
option(prot);
ring r=0, (y0,y1,y2,y3,y4,y5,y6,y7,y8,x0,x1,x2,x3,x4,x5,x6), dp;
ideal i = x1 + 7/5*x3 + 7/5*x5 - 4/125,
x0 + x2 + 7/5*x4 + 7/5*x6 - 4/125,
5*y0 + 5*y1 + 7*y2 + 7*y6 + 1/5,
25*y0^2 + 25*y1^2 + 35*y2^2 + 35*y6^2 - 4/5,
5*y0^3 + 5*y1^3 + 7*y2^3 + 7*y6^3 - y0^2 + 1/125,
5*y0*y1^2 + 5*y1*y3^2 + 7*y2*y4^2 + 7*y6*y7^2 + 1/125,
5*x1*y1 - y1^2 + 7*x3*y2 + 7*x5*y6 + 1/125,
5*y0*y2^2 + 5*y1*y4^2 + 7*y2*y5^2 + 7*y6*y8^2 - x0 + 1/125,
5*x0*y0 + 5*x2*y1 + 7*x4*y2 - y2^2 + 7*x6*y6 + 1/125,
5*y1 + 5*y3 + 7*y4 + 7*y7 + 1/5,
25*y0*y1 + 25*y1*y3 + 35*y2*y4 + 35*y6*y7 + 1/5,
5*y0^2*y1 + 5*y1^2*y3 + 7*y2^2*y4 + 7*y6^2*y7 - y1^2 + 1/125,
25*y1^2 + 25*y3^2 + 35*y4^2 + 35*y7^2 - 4/5,
5*y1^3 + 5*y3^3 + 7*y4^3 + 7*y7^3 - x1 + 1/125,
5*x1*y3 - y3^2 + 7*x3*y4 + 7*x5*y7 + 1/125,
5*y1*y2^2 + 5*y3*y4^2 + 7*y4*y5^2 + 7*y7*y8^2 - x2 + 1/125,
5*x0*y1 + 5*x2*y3 + 7*x4*y4 - y4^2 + 7*x6*y7 + 1/125,
7*y2 + 7*y4 + 49/5*y5 + 49/5*y8 + 7/25,
35*y0*y2 + 35*y1*y4 + 49*y2*y5 + 49*y6*y8 + 7/25,
5*y0^2*y2 + 5*y1^2*y4 + 7*y2^2*y5 + 7*y6^2*y8 - y2^2 + 1/125,
35*y1*y2 + 35*y3*y4 + 49*y4*y5 + 49*y7*y8 + 7/25,
5*y1^2*y2 + 5*y3^2*y4 + 7*y4^2*y5 + 7*y7^2*y8 - x3 + 1/125,
5*x1*y4 - y4^2 + 7*x3*y5 + 7*x5*y8 + 1/125,
35*y2^2 + 35*y4^2 + 49*y5^2 + 49*y8^2 - 18/25,
5*y2^3 + 5*y4^3 + 7*y5^3 + 7*y8^3 - x4 + 1/125,
5*x0*y2 + 5*x2*y4 + 7*x4*y5 - y5^2 + 7*x6*y8 + 1/125;
std(i);


The output is:

[15:2]1(25)s(24)s(23)s(22)s(21)s2(20)s(19)s(18)s(17)ss(18)s(17)s(20)s(22)s(25)s(24)s(27)s3(28)s(31)s(35)s(39)s(44)s(48)s(53)s(59)s(64)s(69)s(75)s(82)s(88)s(94)s(99)s(104)--s(108)s(114)-s(73)s(34)s(31)-s(32)--s(29)s4(32)s(31)s(30)s(19)-5-----------------6-.7
product criterion:467 chain criterion:229
_[1]=1


Here the last line says that the output (the Groebner basis) is the list containing only 1, and above that is the protocol information, as explained in the documentation of option.

The implementation in Singular is fast, and we can see e.g. that applying the product criterion and the chain criterion (which give sufficient conditions for an S-polynomial to reduce to zero) allows to avoid a lot of computations. Even with this (and probably other optimizations), the algorithm still adds a polynomial to the basis 43 times (seen from the 43 occurrences of s). By setting degBound to 1, 2, or 3 before running std(i) (to stop the standard basis computation early), you see that these polynomials are quite large. So I think it is more a case of "the implementation is fast" than "it should be observable by hand". Of course I would be happy to be proven wrong.

Another way to verify the result is to express $1$ as a linear combination (with polynomial coefficients) of the original generators, by using the lift command:

sage: C = list(R.one().lift(Id))
sage: sum(c*f for c,f in zip(C,Id.gens()))
1


The size of the polynomials in C also does not give much hope for it to be easily observable by hand. This tuple of coefficients could potentially be simplified, by adding syzygies of the generators. (Because if there are two ways to express $1$, then their difference yields a syzygy.) Such syzygies can be found by Id.syzygy_module().

Edit: If you compile Singular from source using make -j 2 CXXFLAGS=-DKDEBUG=1 to set the KDEBUG flag (and comment out the single line in kernel/GBEngine/kstd1.cc that gives a compilation error), then you can use the hidden option(teach) to get debug output. Running the code above with this option generates about 20,000 lines of output, illustrating that the computation is fast but seemingly not trivial.

more

( 2021-05-06 08:48:55 +0200 )edit

If you want to simulate the steps of Buchberger algorithm, you can have a look at https://doc.sagemath.org/html/en/refe...

more

By your link, I got the (first) steps of the function buchberger and buchberger_improved, but these functions are really too long (not finished after two hours, without putting the steps) and the steps are far from being handable. On the other hand, I am not able to get the steps of the function groebner_basis() which is very quick (less than 100 ms), and so which may have handable steps. Is there a way to get the steps of the function groebner_basis() ? And if the steps of the function groebner_basis() are more or less the same as the ones of the two previous functions, how to explain the huge difference of computation time?

( 2021-05-04 07:30:40 +0200 )edit

Because the function groebner_basis() on SageMath comes from Singular, maybe I should ask poeple from Singular.

( 2021-05-05 07:42:30 +0200 )edit