Ask Your Question
1

Is it hopeless to compute a Groebner basis for this big system?

asked 2021-06-17 10:40:18 +0200

I would like to compute a Groebner basis for the following polynomial system of 59 variables and 69 equations. The computation crashed on my laptop (16Go of RAM) for $p=0$ or $p=5$, because requiring too much RAM.

Question: Is there a way to compute such a Groebner basis, or is it hopeless?

I can only compute it for $p=2$:

sage: function(2)
[1]

Code

def function(p):
    if p==0:
        F=QQ
    else:
        F=GF(p)
    R.<u0,u1,u2,u3,u4,u5,u6,u7,u8,u9,u10,u11,u12,u13,u14,u15,u16,u17,u18,u19,u20,u21,u22,u23,u24,u25,u26,u27,u28,v0,v1,v2,v3,v4,v5,v6,v7,v8,v9,v10,v11,v12,v13,v14,v15,v16,v17,v18,v19,v20,v21,v22,v23,v24,v25,v26,v27,v28,v29>=PolynomialRing(F,59)
    Eq=[u0+11/F(9)*u13+11/F(9)*u17+11/F(9)*u21+11/F(9)*u25+u3+u6-8/F(729),
    u1+u10+11/F(9)*u14+11/F(9)*u18+11/F(9)*u22+11/F(9)*u26+u7-8/F(729),
    u11+11/F(9)*u15+11/F(9)*u19+11/F(9)*u23+11/F(9)*u27+u4+u8-8/F(729),
    u12+11/F(9)*u16+u2+11/F(9)*u20+11/F(9)*u24+11/F(9)*u28+u5+u9-10/F(891),
    9*v0+9*v1+11*v15+9*v2+11*v20+11*v25+9*v3+11*v4+1/F(9),
    81*v0^2+81*v1^2+99*v15^2+81*v2^2+99*v20^2+99*v25^2+81*v3^2+99*v4^2-8/F(9),
    9*v0^3+9*v1^3+11*v15^3+9*v2^3+11*v20^3+11*v25^3+9*v3^3+11*v4^3-v0^2+1/F(729),
    9*v0*v1^2+11*v15*v16^2+11*v20*v21^2+11*v25*v26^2+9*v1*v5^2+9*v2*v6^2+9*v3*v7^2+11*v4*v8^2-u0+1/F(729),
    9*u0*v0+9*u3*v1-v1^2+11*u17*v15+9*u6*v2+11*u21*v20+11*u25*v25+11*u13*v4+1/F(729),
    11*v15*v17^2+9*v0*v2^2+11*v20*v22^2+11*v25*v27^2+9*v10^2*v3+11*v11^2*v4+9*v1*v6^2+9*v2*v9^2-u1+1/F(729),
    9*u1*v0+11*u18*v15+9*u7*v2-v2^2+11*u22*v20+11*u26*v25+9*u10*v3+11*u14*v4+1/F(729),
    11*v15*v18^2+9*v10^2*v2+11*v20*v23^2+11*v25*v28^2+9*v12^2*v3+9*v0*v3^2+11*v13^2*v4+9*v1*v7^2+1/F(729),
    9*u4*v1+11*u19*v15+9*u8*v2+11*u23*v20+11*u27*v25+9*u11*v3-v3^2+11*u15*v4+1/F(729),
    11*v15*v19^2+9*v11^2*v2+11*v20*v24^2+11*v25*v29^2+9*v13^2*v3+11*v14^2*v4+9*v0*v4^2+9*v1*v8^2-u2+1/F(729),
    9*u2*v0+9*u5*v1+11*u20*v15+9*u9*v2+11*u24*v20+11*u28*v25+9*u12*v3+11*u16*v4-v4^2+1/F(891),
    9*v1+11*v16+11*v21+11*v26+9*v5+9*v6+9*v7+11*v8+1/F(9),
    81*v0*v1+99*v15*v16+99*v20*v21+99*v25*v26+81*v1*v5+81*v2*v6+81*v3*v7+99*v4*v8+1/F(9),
    9*v0^2*v1+11*v15^2*v16+11*v20^2*v21+11*v25^2*v26+9*v1^2*v5+9*v2^2*v6+9*v3^2*v7+11*v4^2*v8-v1^2+1/F(729),
    81*v1^2+99*v16^2+99*v21^2+99*v26^2+81*v5^2+81*v6^2+81*v7^2+99*v8^2-8/F(9),
    9*v1^3+11*v16^3+11*v21^3+11*v26^3+9*v5^3+9*v6^3+9*v7^3+11*v8^3-u3+1/F(729),
    9*u0*v1+11*u17*v16+11*u21*v21+11*u25*v26+9*u3*v5-v5^2+9*u6*v6+11*u13*v8+1/F(729),
    11*v16*v17^2+9*v1*v2^2+11*v21*v22^2+11*v26*v27^2+9*v5*v6^2+9*v10^2*v7+11*v11^2*v8+9*v6*v9^2+1/F(729),
    9*u1*v1+11*u18*v16+11*u22*v21+11*u26*v26+9*u7*v6-v6^2+9*u10*v7+11*u14*v8+1/F(729),
    11*v16*v18^2+11*v21*v23^2+11*v26*v28^2+9*v1*v3^2+9*v10^2*v6+9*v12^2*v7+9*v5*v7^2+11*v13^2*v8-u4+1/F(729),
    11*u19*v16+11*u23*v21+11*u27*v26+9*u4*v5+9*u8*v6+9*u11*v7-v7^2+11*u15*v8+1/F(729),
    11*v16*v19^2+11*v21*v24^2+11*v26*v29^2+9*v1*v4^2+9*v11^2*v6+9*v13^2*v7+11*v14^2*v8+9*v5*v8^2-u5+1/F(729),
    9*u2*v1+11*u20*v16+11*u24*v21+11*u28*v26+9*u5*v5+9*u9*v6+9*u12*v7+11*u16*v8-v8^2+1/F(891),
    9*v10+11*v11+11*v17+9*v2+11*v22+11*v27+9*v6+9*v9+1/F(9),
    99*v15*v17+81*v0*v2+99*v20*v22+99*v25*v27+81*v10*v3+99*v11*v4+81*v1*v6+81*v2*v9+1/F(9),
    11*v15^2*v17+9*v0^2*v2+11*v20^2*v22+11*v25^2*v27+9*v10*v3^2+11*v11*v4^2+9*v1^2*v6+9*v2^2*v9-v2^2+1/F(729),
    99*v16*v17+81*v1*v2+99*v21*v22+99*v26*v27+81*v5*v6+81*v10*v7+99*v11*v8+81*v6*v9+1/F(9),
    11*v16^2*v17+9*v1^2*v2+11*v21^2*v22+11*v26^2*v27+9*v5^2*v6+9*v10*v7^2+11*v11*v8^2+9*v6^2*v9-u6+1/F(729),
    11*u13*v11+11*u17*v17+9*u0*v2+11*u21*v22+11*u25*v27+9*u3*v6-v6^2+9*u6*v9+1/F(729),
    81*v10^2+99*v11^2+99*v17^2+81*v2^2+99*v22^2+99*v27^2+81*v6^2+81*v9^2-8/F(9),
    9*v10^3+11*v11^3+11*v17^3+9*v2^3+11*v22^3+11*v27^3+9*v6^3+9*v9^3-u7+1/F(729),
    9*u10*v10+11*u14*v11+11*u18*v17+9*u1*v2+11*u22*v22+11*u26*v27+9*u7*v9-v9^2+1/F(729),
    9*v10*v12^2+11*v11*v13^2+11*v17*v18^2+11*v22*v23^2+11*v27*v28^2+9*v2*v3^2+9*v6*v7^2+9*v10^2*v9-u8+1/F(729),
    9*u11*v10-v10^2+11*u15*v11+11*u19*v17+11*u23*v22+11*u27*v27+9*u4*v6+9*u8*v9+1/F(729),
    9*v10*v13^2+11*v11*v14^2+11*v17*v19^2+11*v22*v24^2+11*v27*v29^2+9*v2*v4^2+9*v6*v8^2+9*v11^2*v9-u9+1/F(729),
    9*u12*v10+11*u16*v11-v11^2+11*u20*v17+9*u2*v2+11*u24*v22+11*u28*v27+9*u5*v6+9*u9*v9+1/F(891),
    9*v10+9*v12+11*v13+11*v18+11*v23+11*v28+9*v3+9*v7+1/F(9),
    99*v15*v18+81*v10*v2+99*v20*v23+99*v25*v28+81*v0*v3+81*v12*v3+99*v13*v4+81*v1*v7+1/F(9),
    11*v15^2*v18+9*v10*v2^2+11*v20^2*v23+11*v25^2*v28+9*v0^2*v3+9*v12*v3^2+11*v13*v4^2+9*v1^2*v7-v3^2+1/F(729),
    99*v16*v18+99*v21*v23+99*v26*v28+81*v1*v3+81*v10*v6+81*v12*v7+81*v5*v7+99*v13*v8+1/F(9),
    11*v16^2*v18+11*v21^2*v23+11*v26^2*v28+9*v1^2*v3+9*v10*v6^2+9*v5^2*v7+9*v12*v7^2+11*v13*v8^2+1/F(729),
    9*u6*v10+11*u13*v13+11*u17*v18+11*u21*v23+11*u25*v28+9*u0*v3+9*u3*v7-v7^2+1/F(729),
    81*v10*v12+99*v11*v13+99*v17*v18+99*v22*v23+99*v27*v28+81*v2*v3+81*v6*v7+81*v10*v9+1/F(9),
    9*v10^2*v12+11*v11^2*v13+11*v17^2*v18+11*v22^2*v23+11*v27^2*v28+9*v2^2*v3+9*v6^2*v7+9*v10*v9^2-u10+1/F(729),
    9*u7*v10-v10^2+9*u10*v12+11*u14*v13+11*u18*v18+11*u22*v23+11*u26*v28+9*u1*v3+1/F(729),
    81*v10^2+81*v12^2+99*v13^2+99*v18^2+99*v23^2+99*v28^2+81*v3^2+81*v7^2-8/F(9),
    9*v10^3+9*v12^3+11*v13^3+11*v18^3+11*v23^3+11*v28^3+9*v3^3+9*v7^3-u11+1/F(729),
    9*u8*v10+9*u11*v12-v12^2+11*u15*v13+11*u19*v18+11*u23*v23+11*u27*v28+9*u4*v7+1/F(729),
    9*v10*v11^2+9*v12*v13^2+11*v13*v14^2+11*v18*v19^2+11*v23*v24^2+11*v28*v29^2+9*v3*v4^2+9*v7*v8^2-u12+1/F(729),
    9*u9*v10+9*u12*v12+11*u16*v13-v13^2+11*u20*v18+11*u24*v23+11*u28*v28+9*u2*v3+9*u5*v7+1/F(891),
    11*v11+11*v13+121/F(9)*v14+121/F(9)*v19+121/F(9)*v24+121/F(9)*v29+11*v4+11*v8+11/F(81),
    121*v15*v19+99*v11*v2+121*v20*v24+121*v25*v29+99*v13*v3+99*v0*v4+121*v14*v4+99*v1*v8+11/F(81),
    11*v15^2*v19+9*v11*v2^2+11*v20^2*v24+11*v25^2*v29+9*v13*v3^2+9*v0^2*v4+11*v14*v4^2+9*v1^2*v8-v4^2+1/F(729),
    121*v16*v19+121*v21*v24+121*v26*v29+99*v1*v4+99*v11*v6+99*v13*v7+121*v14*v8+99*v5*v8+11/F(81),
    11*v16^2*v19+11*v21^2*v24+11*v26^2*v29+9*v1^2*v4+9*v11*v6^2+9*v13*v7^2+9*v5^2*v8+11*v14*v8^2-u13+1/F(729),
    9*u6*v11+11*u13*v14+11*u17*v19+11*u21*v24+11*u25*v29+9*u0*v4+9*u3*v8-v8^2+1/F(729),
    99*v10*v13+121*v11*v14+121*v17*v19+121*v22*v24+121*v27*v29+99*v2*v4+99*v6*v8+99*v11*v9+11/F(81),
    9*v10^2*v13+11*v11^2*v14+11*v17^2*v19+11*v22^2*v24+11*v27^2*v29+9*v2^2*v4+9*v6^2*v8+9*v11*v9^2-u14+1/F(729),
    9*u7*v11-v11^2+9*u10*v13+11*u14*v14+11*u18*v19+11*u22*v24+11*u26*v29+9*u1*v4+1/F(729),
    99*v10*v11+99*v12*v13+121*v13*v14+121*v18*v19+121*v23*v24+121*v28*v29+99*v3*v4+99*v7*v8+11/F(81),
    9*v10^2*v11+9*v12^2*v13+11*v13^2*v14+11*v18^2*v19+11*v23^2*v24+11*v28^2*v29+9*v3^2*v4+9*v7^2*v8-u15+1/F(729),
    9*u8*v11+9*u11*v13-v13^2+11*u15*v14+11*u19*v19+11*u23*v24+11*u27*v29+9*u4*v8+1/F(729),
    99*v11^2+99*v13^2+121*v14^2+121*v19^2+121*v24^2+121*v29^2+99*v4^2+99*v8^2-70/F(81),
    9*v11^3+9*v13^3+11*v14^3+11*v19^3+11*v24^3+11*v29^3+9*v4^3+9*v8^3-u16+1/F(729),
    9*u9*v11+9*u12*v13+11*u16*v14-v14^2+11*u20*v19+11*u24*v24+11*u28*v29+9*u2*v4+9*u5*v8+1/F(891)]
    Id=R.ideal(Eq)
    G=Id.groebner_basis()
    return G
edit retag flag offensive close merge delete

1 Answer

Sort by » oldest newest most voted
1

answered 2021-06-24 17:16:05 +0200

FabianG gravatar image

updated 2021-06-24 17:21:22 +0200

Related question: https:// mathoverflow.net/questions/181350/fast-computation-of-a-groebner-basis-what-is-possible

In general, such a big system may easily be hopeless. There are examples with way fewer variables and equations that do not terminate in reasonable time. You may want to try different monomial orders and Groebner basis algorithms within and beyond SAGE.

And lastly, any additional mathematical knowledge you have will also increase your chance of success. Do you always suspect the ideal to be (1)? Then it might help to find out how 1 is expressed in terms of the generators over F_2.

About the solutions over the rationals: do you expect integral solutions so that knowing that there is no solution over F_2 helps?

edit flag offensive delete link more

Comments

I expect the ideal to be (1) only for finitely many prime p, and I don’t expect integral solutions over the rationals.

Sébastien Palcoux gravatar imageSébastien Palcoux ( 2021-06-24 19:30:43 +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-06-17 10:40:18 +0200

Seen: 118 times

Last updated: Jun 24