Revision history [back]

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

The function TwoParallel does not map to trivial for $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

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 = 11^4 * 17^2 * 1979 * 2767 * 5791 * 13469 * 20681 *
4151025112783 * 15929905087813 * 2628354959317319 *
21815977082618267790114673 * 253027658769045762395418314237453 *
7255303910453681802448954810627649 * 3770507507964245954661482843443342675673959607

The function TwoParallel does not map to trivial for $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

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

The function TwoParallel does not map to trivial for $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

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 for 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