# How to compute common zeros of system of polynomial equations with dimension 2?

I have some ideal of homogenous polynomials defined over some finite field: J is the ideal of interest. However I can't call J.variety() since it is not zero dimensional. The system of equations might contain 6 or 231 polynomials in four variables:

  sage: [I.gens() for I in J.minimal_associated_primes()]
[[x1 + x2, x0 + x3], [x2 + x3, x0 + x1], [x1 + x3, x0 + x2]]
sage: J.dimension()
2


Any ideas?

On request. The program computes the invariant under the group $2_{+}^{1+2\cdot2}$ homogenous polynomials of given degree. To construct the polynomials and get a list of them call: homInvar(6):

F = ZZ;
a = matrix(F, [[0,0,0,-1],[0,0,1,0],[0,-1,0,0],[1,0,0,0]])
b = matrix(F, [[1,0,0,0],[0,1,0,0],[0,0,-1,0],[0,0,0,-1]])
c = matrix(F, [[0,1,0,0],[-1,0,0,0],[0,0,0,1],[0,0,-1,0]])
d = matrix(F, [[0,1,0,0],[1,0,0,0],[0,0,0,-1],[0,0,-1,0]])

def getPart(deg):
part = []
for k in range(deg+1):
for l in range(deg+1):
for m in range(deg+1):
for n in range(deg+1):
if k+l+m+n == deg:
part.append((k,l,n,m))
return part

def p(x,part):
x = x.list()
pol = 0
for p in [part]:
mon = 1
for i in range(len(p)):
k = p[i]
mon = mon * x[i]**k
pol = pol + mon
return pol

def getGroup():
G = []
for k in range(4):
for l in range(4):
for m in range(4):
for n in range(4):
g = a**k*b**l*c**m*d**n
if G.count(g)==0:
G.append(g)
return G

def reynolds(Gr,part):
reyn = 0
n = len(part)
X = list(var('x%d' % i) for i in range(n))
x = matrix([X]).transpose()
for g in Gr:
reyn +=  p(g*x,part=part)
#print reyn
return 1/len(Gr)* reyn

def homInvar(deg,Gr=getGroup(),getPart=getPart):
parts = getPart(deg)
inv = set([])
for part in parts:
r = reynolds(Gr,part)
#print r
if r != 0:
return inv

edit retag close merge delete

You should provide the construction of the polynomials so that we can play with it and answer your question. Also, what do you want to do with the variety ? Do you want to enumerate its elements ?

( 2018-06-14 09:57:58 -0500 )edit

@tmonteil: I have added some code. Currently I am experimenting with the zeros of the variety.

( 2018-06-14 10:20:25 -0500 )edit

The "polynomials" i get are elements of the symbolic ring, not polynomials defined over finite fields, is it on purpose ?

( 2018-06-14 11:21:01 -0500 )edit

How do you define the ideal J from this code ?

( 2018-06-14 11:23:49 -0500 )edit
R.<x0,x1,x2,x3> = PolynomialRing(GF(2**7,name="a"),order="lex")
F7 = [(4*f).polynomial(GF(2**7,name="a")) for f in homInvar(6)]
J = R.ideal(F7)

( 2018-06-14 11:30:35 -0500 )edit

Sort by » oldest newest most voted

Over finite fields, formal polynomials and polynomials as functions are not the same (two different formal polynonials can lead to the same function). You can use that by artificially reducing the dimension of the ideal by adding polynomials that wanish on the finite field you are considering:

sage: J = R.ideal(F7 + [x0^(2^7) - x0, x1^(2^7) - x1, x2^(2^7) - x2, x3^(2^7) - x3])
sage: J.dimension()
0


However, it is likely that looking for J.variety() will not be faster than testing all the elements of GF(2^7)^4) by hand, which you can do as follows (not tested):

sage: from itertools import product
sage: V = []
sage: for v in product(GF(2**7,name="a"), repeat=4):
....:     if all(p(v) == 0 for p in F7):
....:         V.append(v)


Please tell us which method is faster. Note that this last code is easily parallelizable.

more

1

Thank you for your answer. Seems like calling variety() is much faster! Nice solution. Thanks again!

( 2018-06-14 12:06:34 -0500 )edit