# Find the Galois group of the polynomial $x^{4} + x - 1$ over the finite field $\mathbb{F}_{3}$

Find the Galois group of the polynomial $x^{4} + x - 1$ over the finite field $\mathbb{F}_{3}$.

I'm particurly struggling with what would be the approach to finding the splitting field of this polynomial over $\mathbb{F}_{3}$.

• – André 3000 May 25 '15 at 21:50

Your first question should be: is this polynomial irreducible in $\Bbb F_3[x]$?

It's clear it has no root in $\Bbb F_3$, but this is not enough, we must check for possible quadratic factors. So, suppose (by way of contradiction) we had:

$x^4 + x - 1 = (x^2 + ax + b)(x^2 + cx + d)$ with $a,b,c,d \in \Bbb F_3$.

Then $a + c = 0$ (since our polynomial has no cubic term), and $bd = -1$. The latter equation implies either $b = 1, d = 2$, or $b = 2, d = 1$.

We also have $b + d - a^2 = 0$, and $a(d - b) = 1$. If $d = 2, b = 1$, then $a(d - b) = 1$ implies that $a = 1$ in which case $b + d - a^2 = 1 + 2 - 1 = 2 \neq 0$.

On the other hand, if $b = 2, d= 1$, then $a(d - b) = 1$ implies that $a = 2$, and thus $b + d - a^2 = 2 + 1 - 1 = 2\neq 0$. Either way, we see we can have no quadratic factors, and our polynomial is indeed irreducible.

Hence $\Bbb F_3(u)$ is a field of dimension $4$ over $\Bbb F_3$ (as a vector space), for any root $u$ of $x^4 + x - 1$. Now $\Bbb F_3$ is a perfect field, so this is a Galois extension of $\Bbb F_3$. Thus we know that: $|\text{Gal}(\Bbb F_3(u)/\Bbb F_3)| = \dim_{\Bbb F_3}(\Bbb F_3(u)) = 4$.

Furthermore, it is not hard to see that:

$\sigma: u \mapsto u^3 \in \text{Gal}(\Bbb F_3(u)/\Bbb F_3)$.

Since $\sigma^2 \neq \text{id}_{\Bbb F_3(u)}$, we see this automorphism is of order $4$ and the Galois group is cyclic.

• +1 But I do have a quibble with one part. $\mathbb{F}_3$ perfect implies $\mathbb{F}_3(u)/\mathbb{F}_3$ is separable, but that doesn't mean it's normal. Once you show that all $4$ roots are in $\mathbb{F}_3(u)$ using the Frobenius map, then it's also normal. – André 3000 May 26 '15 at 0:55

Are you familar with Kronocker? The polynomial is irreducible over the finite field. Kronocker gives you a field which contains a root of your polynomial. The quotient is generated by $\{1,x,x^2,x^3\}$ then how many elements does it have? Does this new field contain the other $3$ roots? How does the isomorphic copy look? (knowing what the basis is for the quotient)

$$\mathbb{F}_3[x]/(x^4+x-1) \cong \mathbb{F}_3(\beta)$$

• Do you have a link for your Kronecker" result? I'm not familiar with the result you mention. Also, that should be $\mathbb{F}_3[x]/(x^4 + x - 1)$, with the $[x]$. – André 3000 May 25 '15 at 21:54
• yes that was a typo – Fundamental May 25 '15 at 22:21
• Once you have the elements in the quotient, replace $x$ with $\beta$ and you will get the elements in the isomorphic copy. The use the fact that $\beta^4+\beta+1=0$ to check for the other roots. – Fundamental May 25 '15 at 22:24
• feyzioglu.boun.edu.tr/book/chapter5/ch5%2851%29.pdf, now scroll to $51.1$. – Fundamental May 25 '15 at 22:26
• Use binomial theorem to reduce the messy power to the four computations. – Fundamental May 25 '15 at 22:27

As other have pointed out the key to finding the splitting field and the Galois group is to prove that $f(x)=x^4+x-1$ is irreducible in $\Bbb{F}_3[x]$. Because this is degree four, we can no longer test this simply by checking the absence of zeros in the prime field.

David Wheeler described a good way of handling a quartic by testing the possibility of it being a product of two quadratics. The point I want to make is to add a slightly more high brow test to the repertoire. Not very deep - usually included in a first course in finite fields, but often not on a first course on algebraic structures.

Theorem. Let $p$ be a prime, and $n$ a positive integer. Then the product of all irreducible monic polynomials in $\Bbb{F}_p[x]$ of degree $d$ that is a factor of $n$ is equal to $x^{p^n}-x$.

How does that help? We want to exclude the possibility that $f(x)=p_1(x)p_2(x)$ for some unknown pair of quadratic polynomials $p_1,p_2$. A minor but important detail I want to check first is whether it is possible that $p_1=p_2$. This cannot be for then $f=p_1^2$ which implies that the derivative $f'=2p_1p_1'$. Therefore we see that $f$ and $f'$ share a factor $p_1$. But here $f'(x)=x^3+1$, so $f(x)=x(x^3+1)-1=x f'(x)-1$ implying that $\gcd(f,f')=1$. I used the first step of Euclid's algorithm in calculating the gcd of two polynomials here.

Ok, so $f(x)$ has no repeated factors. The more difficult case is that of $p_1\neq p_2$ anyway. Here's where the above theorem helps us. Namely, whatever the two factors $p_1,p_2$ may be, the theorem promises that they are both factors of $x^9-x$. So then $f(x)$ should also be a factor of $x^9-x$. This is easy to check. Clearly $$x^4\equiv-x+1\pmod{f(x)},$$ so by squaring we get that $$x^8\equiv(-x+1)^2=x^2-2x+1=x^2+x+1\pmod{f(x)}.$$ multiplying this congruence by $x$ gives $$x^9\equiv x^3+x^2+x\pmod{f(x)},$$ so $$x^9-x\equiv x^3+x^2\pmod{f(x)}.$$ We found out that $f(x)$ is not a factor of $x^9-x$ settling its irreducibility (together with the first check that $f(x)$ has no zeros in $\Bbb{F}_3$).

With irreducibility of $f(x)$ clear, it follows that the splitting field is $\Bbb{F}_{81}$. All extensions of finite fields are normal, so adjoining one root of an irreducible polynomial gives you all of them. Also the Galois groups of extensions of finite fields are always cyclic, so the Galois group is $\cong C_4$.

The method generalizes. If $f(x)$ were of degree five instead, then we could have tested for the presence of a quadratic factor by calculating $\gcd(f(x),x^9-x)$ with Euclid's algorithm. Higher up we may also need to calculate $\gcd(f(x),x^{27}-x)$. The presence of those largish exponents may look a bit scary at first. But you noticed how I calculated the remainder of $x^9-x$ modulo $f(x)$. Start with a low power of $x$ and then keep on squaring both sides of the congruence. After you have calculated the remainder of $x^{p^n}-x$ modulo $f(x)$ you are left with two low degree polynomials as inputs to Euclid.

• I'm not saying that this is the recommended way of handling your polynomial. It would not occur to me to use it to handle cubics, but this does generalize, and becomes more straightforward in larger cases. The exact break-even point (in terms of computational complexity) depends on your mileage. – Jyrki Lahtonen May 26 '15 at 5:54