Ask Your Question
3

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

asked 2018-06-14 12:49:21 +0100

sagemathuser gravatar image

updated 2019-08-26 20:58:34 +0100

FrédéricC gravatar image

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:
            inv.add(r)
    return inv
edit retag flag offensive close merge delete

Comments

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 ?

tmonteil gravatar imagetmonteil ( 2018-06-14 16:57:58 +0100 )edit

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

sagemathuser gravatar imagesagemathuser ( 2018-06-14 17:20:25 +0100 )edit

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

tmonteil gravatar imagetmonteil ( 2018-06-14 18:21:01 +0100 )edit

How do you define the ideal J from this code ?

tmonteil gravatar imagetmonteil ( 2018-06-14 18:23:49 +0100 )edit

@tmonteil:

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)
sagemathuser gravatar imagesagemathuser ( 2018-06-14 18:30:35 +0100 )edit

1 Answer

Sort by » oldest newest most voted
2

answered 2018-06-14 18:55:58 +0100

tmonteil gravatar image

updated 2018-06-15 10:15:18 +0100

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.

edit flag offensive delete link more

Comments

1

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

sagemathuser gravatar imagesagemathuser ( 2018-06-14 19:06:34 +0100 )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: 2018-06-14 12:49:21 +0100

Seen: 586 times

Last updated: Jun 15 '18