Ask Your Question

Revision history [back]

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