Groebner basis step by step

edit

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.