Ask Your Question

parametric solution for a system of polynomial equations

asked 2019-04-07 22:40:40 +0200

arpit gravatar image

updated 2019-04-07 22:52:54 +0200

I have the following system of equations,

1+x+y+z==0, 1+xy+yz+xz==0

which I want to solve in the extension field of GF(2) for example. There is a parametric solution of these equations in terms of the parameter s as x=1+s, y=1+$\omega$ s, z=1+$\omega^2$s where $s$ is the parameter and $\omega^2+\omega+1=0$. How can I modify the following for Sage to be able to output parametric solutions like this one?

R.<x,y,z> = PolynomialRing(GF(4))
I = R.ideal([1 + x + y + z, 1 + x*y + y*z + x*z])
edit retag flag offensive close merge delete

1 Answer

Sort by ยป oldest newest most voted

answered 2019-04-08 22:53:29 +0200

slelievre gravatar image

Define the finite field with 4 elements:

sage: F = GF(4)
sage: F
Finite Field in z2 of size 2^2

Failing any indication on how to name the generator of the finite field, Sage names it z2 to indicate the extension is of degree two. So this z2 corresponds to $\omega$ in the question.

The polynomial used in constructing F is:

sage: F.polynomial()
z2^2 + z2 + 1

Define the polynomial ring over F in three variables x, y, z:

sage: R.<x, y, z> = PolynomialRing(F)
sage: R
Multivariate Polynomial Ring in x, y, z over Finite Field in z2 of size 2^2

then the two polynomials in the question:

sage: P = 1 + x + y + z
sage: Q = 1 + x*y + y*z + x*z

and finally the ideal I:

sage: I = R.ideal([P, Q])
sage: I
Ideal (x + y + z + 1, x*y + x*z + y*z + 1) of Multivariate Polynomial Ring in x, y, z over Finite Field in z2 of size 2^2

and check its dimension:

sage: I.dimension()

For ideals of dimension zero, the common zeros form a finite set of points, obtained with I.variety().

Here the dimension is one, so we need to express solutions in terms of one parameter.

A useful tool for this is the resultant, which can help eliminate one of the variables.

Compute the resultant of P and Q with respect to the variable z:

sage: res_P_Q = P.resultant(Q, z)
sage: res_P_Q
x^2 + x*y + y^2 + x + y + 1

From there either factor:

sage: res_P_Q.factor()
((z2 + 1)*x + y + (z2)) * ((z2)*x + y + (z2 + 1))

or notice that the change of variables x = 1 + s and y = 1 + t brings the resultant to a simpler form:

sage: res_P_Q.subs({x: 1 + x, y: 1 + y})
x^2 + x*y + y^2

(where x and y in the output here stand for $s$ and $t$ from the question).

From either of these one can figure out that solutions are $t = \omega s$, with $\omega$ satisfying $\omega^2 + \omega + 1 = 0$.

This translates to $x = 1 + s$, $y = 1 + \omega s$.

Then, solving for $z$ using $P = 0$ or $Q = 0$.

sage: 1 + (1 + x) + (1 + F.gen() * x)
(z2 + 1)*x + 1

so $z = 1 + (\omega + 1) s$, that is, $z = 1 + \omega^2 s$.

edit flag offensive delete link more


@slelievre, thanks for the answer. But I want to also know how to apply it more generally i.e. can I also find the variety in the cases when I don't know the form of the parametrization? for example, if the polynomials are
P2=x + y + z + yz
Q2=1 + y + x
y + z + xz + xyz,
I can find the resultant as
z^2 + y^2 + z^2 + y + z + 1 but how do I find the one dimensional variety in this case when I don't know a suitable parametrization to begin with?

arpit gravatar imagearpit ( 2019-04-10 06:42:55 +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


Asked: 2019-04-07 22:40:40 +0200

Seen: 640 times

Last updated: Apr 08 '19