# parametric solution for a system of polynomial equations

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])
I.variety()

edit retag close merge delete

Sort by » oldest newest most voted

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()
1


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$.

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
and
Q2=1 + y + x
y + z + xz + xyz,
I can find the resultant as
y^2
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?

( 2019-04-09 23:42:55 -0600 )edit