izak

irreducible divisors

Here is a proof I struggled with in the spring of 2024 that I wanted to come back to. To start, this proof gives nice motivation for an abstract area of math called Galois theory which is most famous for showing that there’s no “quadratic formula” or closed expression for the roots of a polynomial of degrees greater than four. But another interesting motivation is in coding theory, where finite fields and their polynomials can construct error-correcting codes. For example, Reed-Solomon codes encode data as polynomials over a finite field \(F_{2^m}\). The proof that irreducible polynomials divide \(x^{p^n} - x\) ensures that the roots of these polynomials lie within \(F_{2^m}\), making encoding and decoding efficient. This property allows Reed-Solomon codes to detect and correct errors in data transmission, such as in CDs or QR codes. By adding \(t = n - k\) check symbols to the data, Reed-Solomon codes can detect any combination of up to \(t\) erroneous symbols, or locate and correct up to \(\lfloor t/2 \rfloor\) erroneous symbols at unknown locations.

We want to show every irreducible polynomial \(g(x)\) over a finite field of prime characteristic \(F_p\) is a divisor of \(x^{p^n}-x\) for some natural number \(n\).

First, as a lemma, we’ll show every finite field \(F\) is perfect, meaning every irreducible polynomial over \(F\) has no multiple roots in any field extension over \(F\), or equivalently, every irreducible polynomial over \(F\) is separable, or its roots are distinct in an algebraic closure of \(F\), so the number of distinct roots is equal to the degree of the polynomial.

Say \(F\) is a finite field of characteristic \(p\). Say \(f\) maps \(F\) to \(F\) by \(f(x) = x^p\) for any \(x \in F\). See \(f\) is a field automorphism as \(f(ab) = (ab)^p = a^p b^p = f(a) f(b)\) and \(f(a+b) = (a+b)^p = a^p + \binom{p}{1} a^{p-1} b + \binom{p}{2} a^{p-2}b^2 + \dots + \binom{p}{p-1}ab^{p-1} + b^p = a^p + b^p\)as \(p\) divides \(\binom{p}{i}\). And, \(x \neq 0\) gives \(x^p \neq 0\), so \(\ker f = \{0\}\). Then \(f\) is injective and as \(F\) is finite, \(f\) injective gives \(f\) surjective. We see then \(F^p = F\).

Now, to show any irreducible polynomial over \(F_p\) divides \(x^{p^n}-x\), say \(g(x)\) is an irreducible polynomial of degree \(m\) in \(F_p[x]\). Let \(K\) be the finite extension of \(F_p\) obtained by adjoining all the zeros of \(g(x)\) in \(\overline{F_p}\), the algebraic closure of \(F_p\). Then \(K\) is a finite field of order \(p^n\) for some positive integer \(n\), and consists precisely of all zeros of \(x^{p^n} - x\) in \(\overline{F_p}\). Now \(g(x)\) factors into linear factors in \(K[x]\), as the linear factors of \(x^{p^n} - x\) in \(K[x]\) include these linear factors, and \(g(x)\) has no repeated roots since we showed every finite field is perfect. Thus, \(g(x)\) is a divisor of \(x^{p^n} - x\).

For example, say \(p = 5\), and consider the finite field \(F_5\). Suppose \(g(x)\) is an irreducible polynomial of degree \(m = 2\) in \(F_5[x]\), such as \(g(x) = x^2 + x + 1\).

As this is a small finite field, we can check the reducibility directly.

A polynomial of degree 2 is reducible over \(F_5\) if and only if it has at least one root in \(\{0,1,2,3,4\}\).

\(0^2 + 0 + 1 = 1 \neq 0 \pmod{5}\)

\(1^2 + 1 + 1 = 1 + 1 + 1 = 3 \neq 0 \pmod{5}\)

\(2^2 + 2 + 1 = 4 + 2 + 1 = 7 \equiv 2 \neq 0 \pmod{5}\)

\(3^2 + 3 + 1 = 9 + 3 + 1 = 13 \equiv 3 \neq 0 \pmod{5}\)

\(4^2 + 4 + 1 = 16 + 4 + 1 = 21 \equiv 1 \neq 0 \pmod{5}\)

As none of these values satisfy the equation \(x^2 + x + 1 \equiv 0 \pmod{5}\), the polynomial has no roots in \(F_5\).

Instead, the zeros of \(g(x)\) lie in an extension field \(K\) of \(F_5\). Since \(g(x)\) is irreducible of degree \(2\), \(K\) is a finite field of order \(5^2 = 25\). To see the roots of \(g(x) = x^2 + x + 1\) in \(F_{25}\), we first recognize that \(F_{25}\) is a field of order \(5^2\), meaning its elements can be written in the form \(a + by\) where \(a, b \in F_5\) and \(y\) is a root of an irreducible quadratic polynomial over \(F_5\).

To see this, say \(x_0 = y\) is a root of \(g(x)\), so \(x_0^2 + x_0 + 1 = 0\). The polynomial \(g(x) = x^2 + x + 1\) is quadratic, so if \(x_0\) is one root, the other root \(x_1\) can be found using the relationship between the roots and coefficients. For a quadratic equation \(ax^2 + bx + c = 0\), the sum of the roots is \(x_0 + x_1 = -b/a\), and the product of the roots is \(x_0 x_1 = c/a\). Here, \(b = 1\), so \(x_0 + x_1 = -1\) and \(c=1\) so \(x_0 x_1 = 1\). Solving for \(x_1\), we get \(x_1 = -x_0 - 1\) or $x_1 = 1/x_0 $. So, the other root is explicitly \(-x_0 - 1\). And, \(g(x)\) factors as \(g(x) = (x - x_0)(x - (-x_0 - 1))\) in \(F_{25}[x]\).

We can check that their product equals the constant term of \(g(x)\), or \(c=1\). Multiplying the two roots, \(y(4y + 4) = 4y^2 + 4y\). Substituting \(y^2 = 4y + 4\), we get \(4(4y + 4) + 4y = 16y + 16 + 4y\), which simplifies to \(20y + 16 \equiv 0y + 1 \equiv 1 \mod 5\). This confirms that \(x_0 x_1 = 1\), as expected.

As the roots \(x_0 = y\) and \(x_1 = 4y + 4\) satisfy \(g(x)\), we can factor the polynomial in \(F_{25}[x]\) as \(g(x) = (x - y)(x - (4y + 4))\).

Now, to see why every element in \(F_{25}\) satisfies \(x^{25} - x = 0\), see the field \(F_{25}\) has 25 elements as it is an extension of \(F_5\) of degree 2, meaning \(|F_{25}| = 5^2 = 25\). In any finite field \(F_q\), every element satisfies the equation \(x^q = x\)

which follows from the fact that the field is the splitting field of \(x^q - x\) over its prime subfield.

To prove this directly, consider the multiplicative group of nonzero elements in \(F_{25}\), which has order \(25 - 1 = 24\). This group is cyclic, meaning every nonzero element \(x\) satisfies \(x^{24} = 1.\)

Multiplying both sides by \(x\), we see \(x^{25} = x.\)

For \(x = 0\), the equation \(0^{25} - 0 = 0\) holds trivially. Hence, for every element \(x \in F_{25}\), we see that \(x^{25} - x = 0.\)

So, \(x^{25} - x\) is an identity for all elements in \(F_{25}\), proving that it holds in the whole field.

So, as every element in \(F_{25}\) satisfies \(x^{25} - x = 0\), the roots of \(g(x)\) must be among the solutions to this equation. This implies that the linear factors \((x - x_0)\) and \((x - x_1)\) divide \(x^{25} - x\), and so, \(g(x)\) divides \(x^{25} - x\).

Thus, \(g(x)\) is a divisor of \(x^{25} - x\).

This shows that \(g(x) = x^2 + x + 1\) divides \(x^{25} - x\) in \(F_5[x]\).