Quick (trivial) Groebner basis but too long lift of one
I have two (equivalent) sub-systems of polynomial equations of 10 variables and 12 equations, linked with one extra equations (so a total of 20 variable and 25 equations).
I can very quicky compute the Groebner basis of each sub-system. Then I can put them together, with the extra equation, and then I can quicky get the Groebner basis of the full system, which turns out to be trivial (total computation time: less than 3 minutes). See all the details in Appendix.
A direct computation of the Groebner basis of the full system is too long (I stopped after 1 day). The problem is that I need to compute the lift of 1 of the original full system (i.e. express 1 as a linear combination (with polynomial coefficients) of the original generators, by using the lift command list(R.one().lift(Id))
), but it is also too long...
Now I expect that the application of a strategy involving the two sub-systems (as above) should exist to quickly get the lift of 1, but how?
I tried to compute this lift in two times, using the Groebner basis of the sub-systems, but it is also too long...
Appendix
First sub-system (10 variables and 12 equations)
sage: R.<u0,u1,u2,v0,v1,v2,v3,v4,v5,v6>=PolynomialRing(QQ,10)
sage: A1=[u0 + 7/5*u1 + 7/5*u2 - 4/125,
....: 5*v0 + 5*v1 + 7*v3 + 7*v5 + 1/5,
....: 25*v0^2 + 25*v1^2 + 35*v3^2 + 35*v5^2 - 4/5,
....: 5*v0^3 + 5*v1^3 + 7*v3^3 + 7*v5^3 - v0^2 + 1/125,
....: 5*v0*v1^2 + 5*v1*v2^2 + 7*v3*v4^2 + 7*v5*v6^2 + 1/125,
....: 5*u0*v1 - v1^2 + 7*u1*v3 + 7*u2*v5 + 1/125,
....: 5*v1 + 5*v2 + 7*v4 + 7*v6 + 1/5,
....: 25*v0*v1 + 25*v1*v2 + 35*v3*v4 + 35*v5*v6 + 1/5,
....: 5*v0^2*v1 + 5*v1^2*v2 + 7*v3^2*v4 + 7*v5^2*v6 - v1^2 + 1/125,
....: 25*v1^2 + 25*v2^2 + 35*v4^2 + 35*v6^2 - 4/5,
....: 5*v1^3 + 5*v2^3 + 7*v4^3 + 7*v6^3 - u0 + 1/125,
....: 5*u0*v2 - v2^2 + 7*u1*v4 + 7*u2*v6 + 1/125]
sage: Id=R.ideal(A1)
sage: %time G1=Id.groebner_basis()
CPU times: user 1.33 s, sys: 0 ns, total: 1.33 s
Wall time: 1.33 s
sage: C1=[g for g in G1]
Second (equivalent) sub-system:
sage: R.<y0,y1,y2,z0,z1,z2,z3,z4,z5,z6>=PolynomialRing(QQ,10)
sage: A2=[y0 + 7/5*y1 + 7/5*y2 - 4/125,
....: 5*z0 + 5*z1 + 7*z3 + 7*z5 + 1/5,
....: 25*z0^2 + 25*z1^2 + 35*z3^2 + 35*z5^2 - 4/5,
....: 5*z0^3 + 5*z1^3 + 7*z3^3 + 7*z5^3 - y0 + 1/125,
....: 5*y0*z0 - z0^2 + 7*y1*z3 + 7*y2*z5 + 1/125,
....: 5*z0*z1^2 + 5*z1*z2^2 + 7*z3*z4^2 + 7*z5*z6^2 - z1^2 + 1/125,
....: 5*z1 + 5*z2 + 7*z4 + 7*z6 + 1/5,
....: 25*z0*z1 + 25*z1*z2 + 35*z3*z4 + 35*z5*z6 + 1/5,
....: 5*z0^2*z1 + 5*z1^2*z2 + 7*z3^2*z4 + 7*z5^2*z6 + 1/125,
....: 5*y0*z1 - z1^2 + 7*y1*z4 + 7*y2*z6 + 1/125,
....: 25*z1^2 + 25*z2^2 + 35*z4^2 + 35*z6^2 - 4/5,
....: 5*z1^3 + 5*z2^3 + 7*z4^3 + 7*z6^3 - z2^2 + 1/125]
sage: Id=R.ideal(A2)
sage: %time G2=Id.groebner_basis()
CPU times: user 2.08 s, sys: 0 ns, total: 2.08 s
Wall time: 2.08 s
sage: C2=[g for g in G2]
The full system:
sage: R.<u0,u1,u2,v0,v1,v2,v3,v4,v5,v6,y0,y1,y2,z0,z1,z2,z3,z4,z5,z6>=PolynomialRing(QQ,20)
sage: C=C1+C2+[5*u0*z2 + 5*u1*z4 + 7*u2*z6 - u0 + 1/125] # the last one is the extra one
sage: Id=R.ideal(C)
sage: %time G=Id.groebner_basis()
CPU times: user 2min 29s, sys: 16 ms, total: 2min 29s
Wall time: 2min 29s
sage: G
[1]
It's not what you asked, and probably suboptimal, but: since the two individual ideals are zero-dimensional, and the respective varieties each contain 14 points over $\bar{\mathbb{Q}}$, you could also loop through all 196 pairs of points and substitute them into the extra polynomial, and check that you never get zero.
A simpler variant of that idea (using linear algebra over $\mathbb{Q}$ instead of arithmetic over $\bar{\mathbb{Q}}$) is to use that
C1 + C2
is a Groebner basis of the ideal $I$ generated byC1 + C2
; hence there is a normal basis (basis of the quotient $R/I$ as a $\mathbb{Q}$-vector space) consisting of 196 monomials, and multiplication byf = 5*u0*z2 + 5*u1*z4 + 7*u2*z6 - u0 + 1/125
can be written as a 196x196 matrix over $\mathbb{Q}$, and the values off
on $V(I)$ are the eigenvalues of this matrix, so it suffices to show that the matrix does not have 0 as an eigenvalue, or that it has full rank, or that its determinant is nonzero (which is easy).@rburing What you wrote in your first comment was done firstly, but that requires to use numerical solutions... The computation with Groebner bases only is cleaner (in my opinion) and still very quick in this case. Anyway, my problem is that I need the lift of 1, because the Groebner basis must be also trivial in char p>0, except for finitely many p, contained in the set of prime divisors of the denominators in the lift of 1, but I need to classify all p for which the Groebner basis is non-trivial: for p<1000000, there are exactly six one: 11, 29, 41, 467, 1423, 242057. With a lift of 1, I can easily classify all such p.
Interesting problem. The numerator of the determinant of the aforementioned matrix has 785 digits and its factorization is 11 × 467 × 1423 × 242057 × 1477913 × 2673859 × 9528289 × 3869785541 × 715114922077295989 × 75154031037086343317 × 652748578372455171701 × (to be determined).
@rburing Very interesting!! If I am not mistaken, the primes that I am looking for are exactly the prime divisors of the determinant of this 196x196 matrix, right? If so, 29 and 41 should also be divisors. Did you miss them, or am I mistaken? Can you write the numerator of the determinant (with its 785 digits)?