Ask Your Question
1

Groebner basis step by step

asked 2021-05-03 10:11:26 +0200

updated 2021-05-03 10:13:45 +0200

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 flag offensive close merge delete

Comments

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

Max Alekseyev gravatar imageMax Alekseyev ( 2021-05-06 16:11:09 +0200 )edit

2 Answers

Sort by » oldest newest most voted
3

answered 2021-05-05 23:07:34 +0200

rburing gravatar image

updated 2021-05-06 09:17:44 +0200

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.

edit flag offensive delete link more

Comments

Thanks for your answer, it is very useful!!

Sébastien Palcoux gravatar imageSébastien Palcoux ( 2021-05-06 08:48:55 +0200 )edit
2

answered 2021-05-03 12:40:49 +0200

tmonteil gravatar image

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

edit flag offensive delete link more

Comments

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?

Sébastien Palcoux gravatar imageSébastien Palcoux ( 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.

Sébastien Palcoux gravatar imageSébastien Palcoux ( 2021-05-05 07:42:30 +0200 )edit

Your Answer

Please start posting anonymously - your entry will be published after you log in or create a new account.

Add Answer

Question Tools

1 follower

Stats

Asked: 2021-05-03 10:11:26 +0200

Seen: 171 times

Last updated: May 06