Polynomial system without solution in char. 0: classification of char. p with solution

Let $r$ be an integer and let $S$ be a finite set of polynomials $f \in \mathbb{Q}[x_1,\dots, x_r]$. Assume that the ideal $I(S)$ generated by $S$ is $\mathbb{Q}[x_1,\dots, x_r]$ itself, i.e. the Groebner basis is trivial (no solution in char. 0). Then we can lift $1$, i.e. for all $f \in S$ there is $k_f \in \mathbb{Q}[x_1,\dots, x_r]$ such that $\sum_{f \in S}k_ff = 1$.

For simplicity, assume that $S \subset \mathbb{Z}[x_1,\dots, x_r]$. Let $S_p \subset GF(p)[x_1,\dots, x_r]$ be the set of polynomials in $S$ modulo $p$. The problem here is how to classify all the prime numbers $p$ for which the ideal $I(S_p)$ is not $GF(p)[x_1,\dots, x_r]$, i.e. the Groebner basis is not trivial (solution in char. $p$). Let $P_S$ be the set of all such primes.

More precisely, the problem is how to get $P_S$ in practice, because in theory, we just need to check every element of the finite set of prime divisors of the denominators of the (simplified) rational coefficients of $k_f$, for all $f$ in $S$.

I am interested in the system in the function TwoParallel in Appendix (slightly different from the one in this post).

sage: %time TwoParallel(0)
CPU times: user 48.5 s, sys: 0 ns, total: 48.5 s
Wall time: 48.5 s
[1]


Here is the expected classification for $p<10^7$:

sage: P=Primes()
sage: L=[]
....: for p in range(10000000): # about 1 day of computation
....: if p in P and p!=5:
....: G=TwoParallel(p)
....: if G!=[1]:
....: L.append(p)
sage: L
[11, 17, 29, 41, 1979, 2767, 5791, 13469, 20681]


As $20681 \ll 10^7$, we could naively guess that there is no other such prime $p$, but it is not true...
The following strategy due to Ricardo Buring (see this answer, where the system is slightly different) provides other such $p>10^7$: let $M$ be the multiplication matrix on the normal basis associated to C1+C2, of the extra polynomial. The numerator of $\det(M)$ is equal to $n^2$, with the following prime factorization for $n$:

n = 11^4 * 17^2 * 1979 * 2767 * 5791 * 13469 * 20681 *
4151025112783 * 15929905087813 * 2628354959317319 *
21815977082618267790114673 * 253027658769045762395418314237453 *
7255303910453681802448954810627649 * 3770507507964245954661482843443342675673959607


TwoParallel does not map to trivial from $p$ dividing $n$, but the converse is not true (see $p = 29, 41$).

The problem is that we cannot in practice lift $1$ from A1+A2+extra, but only from C1+C2+extra (see how in the answers of the post mentioned above). It seems hard to lift C1 from A1, the coefficients may be colossal.

Appendix

def TwoParallel(p):
if p==0:
F=QQ
else:
F=GF(p)
R1.<u0,u1,u2,v0,v1,v2,v3,v4,v5,v6>=PolynomialRing(F,10)
A1=[u0+7/F(5)*u1+7/F(5)*u2-4/F(125),
5*v0+5*v1+7*v3+7*v5+1/F(5),
25*v0^2+25*v1^2+35*v3^2+35*v5^2-4/F(5),
5*v0^3+5*v1^3+7*v3^3+7*v5^3-v0^2+1/F(125),
5*v0*v1^2+5*v1*v2^2+7*v3*v4^2+7*v5*v6^2+1/F(125),
5*u0*v1-v1^2+7*u1*v3+7*u2*v5+1/F(125),
5*v1+5*v2+7*v4+7*v6+1/F(5),
25*v0*v1+25*v1*v2+35*v3*v4+35*v5*v6+1/F(5),
5*v0^2*v1+5*v1^2*v2+7*v3^2*v4+7*v5^2*v6-v1^2+1/F(125),
25*v1^2+25*v2^2+35*v4^2+35*v6^2-4/F(5),
5*v1^3+5*v2^3+7*v4^3+7*v6^3-u0+1/F(125),
5*u0*v2-v2^2+7*u1*v4+7*u2*v6+1/F(125)]
Id1=R1.ideal(A1)
G1=Id1.groebner_basis()
C1=[g for g in G1]
R2.<y0,y1,y2,z0,z1,z2,z3,z4,z5,z6>=PolynomialRing(F,10)
A2=[y0+7/F(5)*y1+7/F(5)*y2-4/F(125),
5*z0+5*z1+7*z3+7*z5+1/F(5),
25*z0^2+25*z1^2+35*z3^2+35*z5^2-4/F(5),
5*z0^3+5*z1^3+7*z3^3+7*z5^3-y0+1/F(125),
5*y0*z0-z0^2+7*y1*z3+7*y2*z5+1/F(125),
5*z0*z1^2+5*z1*z2^2+7*z3*z4^2+7*z5*z6^2-z1^2+1/F(125),
5*z1+5*z2+7*z4+7*z6+1/F(5),
25*z0*z1+25*z1*z2+35*z3*z4+35*z5*z6+1/F(5),
5*z0^2*z1+5*z1^2*z2+7*z3^2*z4+7*z5^2*z6+1/F(125),
5*y0*z1-z1^2+7*y1*z4+7*y2*z6+1/F(125),
25*z1^2+25*z2^2+35*z4^2+35*z6^2-4/F(5),
5*z1^3+5*z2^3+7*z4^3+7*z6^3-z2^2+1/F(125)]
Id2=R2.ideal(A2)
G2=Id2.groebner_basis()
C2=[g for g in G2]
R.<u0,u1,u2,v0,v1,v2,v3,v4,v5,v6,y0,y1,y2,z0,z1,z2,z3,z4,z5,z6>=PolynomialRing(F,20)
C=C1+C2+[5*u0*z2 + 7*u1*z4 + 7*u2*z6 - u0 + 1/F(125)] # extra polynomial
Id=R.ideal(C)
G=Id.groebner_basis()
return G

edit retag close merge delete

Sort by » oldest newest most voted

To lift C1 in terms of A1, we can use Singular's liftstd function to compute a Gröbner basis (standard basis) and the lift of the generators in one go. Using Singular directly would be a bit faster and maybe simpler to use, but from Sage, we could use it as follows:

def liftstd(I):
I_sing = singular(I)
singular.eval(f'matrix T; option(redSB); ideal gb = liftstd({I_sing._name}, T);')
gb = singular('gb').sage()
T = singular('T').sage()  # this conversion can take a considerable portion of time
return gb.gens(), T


With A1, Id1, C1 defined in characteristic 0 as in the question, we can call it like this, where T is the desired transformation matrix:

sage: gb1, T = liftstd(Id1)  # about 4 minutes
sage: vector(gb1) == vector(A1) * T
True


Note that gb1 is a Gröbner basis that can be slightly different from C1, but is the same up to permutation and normalization (since we have used the option redSB to obtain a reduced Gröbner basis). The result from liftstd appears to have cleared denominators.

sage: gb1.is_groebner()
True
sage: sorted(C1) == sorted([p/p.lc() for p in gb1])
True


Edit:

The analogous computation for the second ideal takes about 20 minutes. If one then constructs lift_coeffs as in rburing's answer, then (since the transformation matrices have integer coefficients) one needs to find the prime factors of the following denominators of lift_coeffs, which still seems to be a hard problem. At least, $29,41$ divide the bigger two.

sage: lift_coeffs[0].denominator()
1368162068772907277016949808911674433443731715670078907923745566842319032218023389631644934432397528696968597075170914623476410897485963409010849263214726306499970668375272723902505492542578804635528861680478467483648734003200
sage: vector(lift_coeffs[1:32]).denominator()
2656390119210841608754981370882120113205857102430722953249676393122294033997615371473773495839032085051428692642636576714436971553290801783246162299823060549828740242317911755788137610144264508412396754742245938030951437820199254946394360942826997829288275150366754644953324917102942349871485467794222357245468234719335375771845013974468884379722016669288302764503021401318107329094660657757015547239722566526215291556857883675923230114898064723775663457116378618146964780224819530957477689490646036587994768392346835107733423453361617937580695957179594637828069492591400063540349984446852397354109287671639416489429684581776657409316670201740958431886602686864924701846786356441750340245959374442420515990922774839515663958555694585632127300568279856889192867103017906517301525030007958495348777414350304294826215034862534160497984985775719719885474544475502997778096966014848477429760000000000000000000
sage: vector(lift_coeffs[32:63]).denominator()
47108403017039852783571221674633224123403184742378006164117852516715317419896099460852953970280479173495445064152315046561513175890527026365848860620372742312104503344544264661558367744946603426009345747558665739151291962751244036615056187313189013733869788074886602481231471278125817799258392099089847778745311651501638395739945446023922108866268424690254839930414268645122365586352651354440509206702928280256096557379329823521976489183272686385168593623174968362910947981039697074928697888468982696663753624433821823437211625763633904986679802394055981580171322582161049009906471089351234141032235435807255040928416436348087365390235461192661173492514589750025082542753492059612398170931200000000000000000


Even if you manage to compute the factorization, the primes might be too large to effectively compute the Gröbner bases modulo those primes, as Sage falls back to the generic (slow) toy implementation for primes larger than $2^{31}$.

more

@mwageringel Are you sure that the computation of liftstd(Id1) takes 4 minutes only? It required 2 hours on my recent laptop (intel core i7).

( 2021-07-12 10:38:42 +0100 )edit

Yes. I reran the computation and it finished in about 6 minutes. Try to run each command of the function individually. The call to singular should take only about 2 minutes. If this is the case and it is the conversion of T that takes a long time via the Pexpect interface, it might be faster (though unclean) to convert the entries of T to strings and then pass those strings to the polynomial ring in Sage. Or just use Singular stand-alone for the entire computation. I am on Sage 9.3 with its Singular version 4.2.0p1+2021-04-06+sage, built from source.

( 2021-07-12 19:36:34 +0100 )edit

On a second machine, with Sage installed from pacman, the computation takes only 2 minutes 40 seconds.

( 2021-07-12 19:43:28 +0100 )edit

As a complement, here is the full list of prime divisors of the three numbers written at the end of the answer of @mwageringel, computed by the elliptic curve factorization method (ECM):

[2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 61, 67, 139, 181, 191, 193, 211, 283, 307, 353, 373, 457, 479, 503, 557, 577, 691, 853, 1021, 1433, 1439, 1559, 1979, 1999, 2027, 2767, 3671, 3727, 5279, 5791, 13469, 15139, 15727, 20681, 27697, 45659, 47623, 70141, 80929, 82699, 280487, 342239, 369833, 463949, 616877, 1200637, 1517311, 2357573, 8415431, 11268923, 14509171, 60479933, 65298647, 67897919, 99715043, 178461007, 189174233, 197383987, 503541859, 867137519, 1619856829, 6571291357, 8443189319, 160051576453, 192799111249, 292691587957, 415335405007, 1268801507087, 2722752332269, 4151025112783, 7178330426833, 15929905087813, 179715441457711, 523993256165279, 2628354959317319, 11683752271727447, 4167327987077113147, 12667423699645143581, 46120994417042855309, 318251420834471793937, 84811287943434519026447, 5726689801216747901687833, 13203132313870698000511993, 21815977082618267790114673, 41071751508973142568684851, 1856238126342625400618917957471, 5331749387342681662942075956083, 253027658769045762395418314237453, 7255303910453681802448954810627649, 9069713450354700121170420035405086387, 3770507507964245954661482843443342675673959607, 62753130801405102309038139791793749317120547519, 906238176218892020111797032918064216314058466963, 9387623449447914403995288046182907649450006116631, 4390349429662788990935603769929698607319344201313287, 1130835035093708622998692953480164354013214604381521218840433810784491]

more

1

Nice. How long did the factorization take? This means the full list of primes for which the system A1+A2+extra has a Gröbner basis different from 1 is

[11, 17, 29, 41, 1979, 2767, 5791, 13469, 20681, 4151025112783, 15929905087813,
2628354959317319, 21815977082618267790114673,
253027658769045762395418314237453, 7255303910453681802448954810627649,
3770507507964245954661482843443342675673959607]


All the others are trivial, including 5 if you clear denominators first. The toy implementation is slow, but "only" takes somewhere between 20 minutes and 2 hours or so, for each of the larger primes.

( 2021-07-14 09:32:10 +0100 )edit
1

@mwageringel: It took few hours. I factorized every lift_coeffs[i].denominator() individually. After that I also applied TwoParallel to that list and got the same result than you: it is exactly the list of prime divisors of the numerator of $\det(M)$ together with $29$ and $41$.

( 2021-07-14 09:40:22 +0100 )edit

Congratulations!

( 2021-07-14 11:31:38 +0100 )edit