Revenge of the Finite Fields

A few days ago, I posted some proofs and a construction of finite fields. It turns out there are a lot more nice constructions and proofs and problems related to finite fields, so I’ll be sharing some of them here.

Theorem: Let N_n be the number of monic irreducible polynomials in \ZZ_p[X]. Then

    \[ p^n = \sum_{d \mid n} d N_d. \]

Proof:
Consider the following zeta function.

    \[ \zeta = \sum_{f \in \ZZ_p[X]\,\textrm{monic}} X^{\deg f}. \]

There are only p^n monic polynomials of degree n so

    \[ \zeta = \sum_{n \geq 0} p^n X^n = \frac{1}{1 - pX}. \]

Monic polynomials have a unique factorization into monic polynomial factors, after some computation, we can arrive at

    \[ \zeta = \prod_h \left( 1 + X^{\deg h} + X^{2 \deg h} + \cdots \right) = \prod_h \frac{1}{1 - X^{\deg h}}, \]

where h are the monic irreducible polynomials of \ZZ_p[X]. We can then compute the equality

    \[ \log \frac{1}{1 - pX} = \sum_h \log \frac{1}{1 - X^{\deg h}} = \sum_{n \geq 0} N_n \log \frac{1}{1 - X^n}. \]

Recall that \log \frac{1}{1 - X} = \sum_{k \geq 1} \frac{X^k}{k}. Substituting, we get

    \[ \sum_{k \geq 1} \frac{p^k X^k}{k} = \sum_{n \geq 0} \left( N_n \sum_{j \geq 1} \frac{X^{jn}}{j} \right). \]

Let us examine the coefficient of X^k of the LHS. We compute

    \[ \frac{p^k}{k} = \sum_{jn = k} \frac{1}{j} N_n, \]

or

    \[ p^k = \sum_{n \mid k} n N_n, \]

as desired.

We now construct finite fields in a different way.

Theorem: Any field has an algebraic closure and its closure is unique up to isomorphism.

Proof: This is actually a fun exercise and proofs of this result can be found almost everywhere.

Theorem: Let \overline{\ZZ_p} be the algebraic closure of \ZZ_p. Let \FF_q = \lbrace x \in \overline{\ZZ_p} \mid x^q = x \rbrace, where q is a power of p. Then \FF_q is the unique field with q elements contained in \overline{\ZZ_p}.

Proof: We first verify that \FF_q is a field. Namely, x^q = x, y^q = x \implies (xy)^q = x^q y^q = xy and x^q = x, y^q = x \implies (x + y)^q = x^q + y^q = x + y. \FF_q clearly has q elements because X^q - X splits into q distinct linear factors over \overline{\ZZ_p}[X] and those factors are distinct (compute gcd with derivative).

Now let K be some other subfield of \overline{\ZZ_p} with q elements. K^* is a group with q - 1 elements so we have x^{q - 1} = 1, and we can trivially extend this to x^q = x for x \in K, so K \subseteq \FF_q. But |K| = |\FF_q|, so K = \FF_q.

We can rephrase the above theorem as follows. \FF_{p^n} is the splitting field of the polynomial X^{p^n} - X over \ZZ_p.

Theorem: Let K be an arbitrary finite field with q elements. Let f be an irreducible polynomial of degree n and let \alpha be one of its roots. Then K(\alpha) is a field with q^n elements.

Proof: This is a standard exercise with respect to field extensions.

Anyways, now for some problems.

Problem 1: (IMO Shortlist 1989) Suppose an integer sequence a_{n \geq 1} satisfies

    \[ 2^n = \sum_{d \mid n} a_d \]

for all n \in \NN. Prove that n \mid a_n for all n \in \NN.

Solution: Let us compute the Möbius inversion. We get

    \[ a_n = \sum_{d \mid n} \mu \left( \frac{n}{d} \right) 2^d. \]

Recall that elements of \FF_{2^n} satisfy the polynomial X^{2^n} - X = 0. We count the number of elements of order precisely 2^n - 1. Namely, we need to subtract off elements of orders 2^d - 1 with d \mid n (can you see why?). We can do this with PIE, which is precisely the formula above. So a_n is the number of elements in \FF_{2^n} with order 2^n - 1. Now consider the set of minimal polynomials of these elements. They must have degree n, otherwise they would also belong in \FF_{2^d} for some d \mid n, and each of these polynomials has n distinct roots in \FF_{2^n}, so we are done.

Problem 2: (IMO Shortlist) Let a_0 = 2, a_n = 2a_{n - 1}^2 - 1. If p > 2 and p \mid a_n, show that 2^{n + 3} \mid p^2 - 1.

Solution: We first obtain a formual for a_n. Check that

    \[ \frac{x^2 + x^{-2}}{2} = 2 \cdot \left( \frac{x + x^{-1}}{2} \right)^2 - 1. \]

This means that x_{n + 1} = x_n^2, or x_n = x_0^{2^n}. Set \frac{x + x^{-1}}{2} = 2 to obtain x = 2 \pm \sqrt{3}, so

    \[ a_n = \frac{(2 + \sqrt{3})^{2^n} + (2 - \sqrt{3})^{2^n}}{2}. \]

Let p > 2 be a prime factor of a_n. Pick some \alpha in \overline{\ZZ_p} such that \alpha^2 = 3. Notice

    \[ \alpha^{p^2 - 1} = \left( \alpha^{p + 1} \right)^{p - 1} = \left( 3^{\frac{p + 1}{2}} \right)^{p - 1} = 1, \]

so \alpha^{p^2} = \alpha and \alpha \in \FF_{p^2}. Define a map \phi : \ZZ[\sqrt{3}] \to \FF_{p^2} given by a + b \sqrt{3} \mapsto a + b \alpha. This is a ring homomorphism. Let x = \phi(2 + \sqrt{3}), y = \phi(2 - \sqrt{3}). x, y are non-zero because xy = \phi(1) = 1. Additionally, p \mid a_n \implies x^{2^n} + y^{2^n} = 0. Now compute

    \[ \begin{aligned} x^{2^n} + y^{2^n} &= 0 \\ x^{2^{n + 1}} + y^{2^{n + 1}} &= -2, \\ x^{2^{n + 2}} + 2 + y^{2^{n + 2}} &= 4 \\ x^{2^{n + 2}} - 2 + y^{2^{n + 2}} &= 0 \\ x^{2^{n + 1}} - y^{2^{n + 1}} &= 0, \\ x^{2^{n + 1}} = y^{2^{n + 1}} &= -1. \end{aligned} \]

Therefore x^{2^n + 2} = 1 and the order of x MUST be 2^{n + 2} (otherwise x^{2^{n + 1}} = -1 is impossible), so 2^{n + 2} \mid p^2 - 1. Suppose x \in \FF_p. Then we know that 2^{n + 2} \mid p - 1 so trivially 2^{n + 3} \mid p^2 - 1. Now suppose not. Then x, y are roots of irreducible X^2 - 4X + 1 \in \FF_p[X]. Raising the equality x^p -4x + 1 = 0 to the p-th power, we get that x^{2p} - 4x^p + 1 = 0. If x^p = 1, then x^p is either x or y. If x^p = x, then x \in \FF_p so we must have the latter, x^p = y, which implies x^{p + 1} = 1. But then, 2^{n + 2} \mid p + 1, so we trivially obtain 2^{n + 3} \mid p^2 - 1.

Problem: (China TST 2008) Let x_1 = 2, x_2 = 12, x_{n + 2} = 6x_{n + 1} - x_n. Let p be an odd prime and q be a prime divisor of x_p. Prove that if q \neq 2, 3, then q \geq 2p - 1.

Solution: Compute

    \[ x_n = \frac{\left( 3 + \sqrt{8} \right)^n - \left( 3 - \sqrt{8} \right)^n}{\sqrt{8}}. \]

Like, before, we can take \alpha^2 = 2 in \overline{\ZZ_q} and define the ring homomorphism \phi. Let x = \phi(3 + 2 \sqrt{2}) and y = \phi(3 - 2 \sqrt{2}). We clearly have

    \[ x^p - y^p = 0. \]

Compute xy = \phi(1) = 1 and using a similar trick in the previous problem, compute

    \[ x^p + y^p = \pm 2, \]

so x^p = y^p = \pm 1. Let us focus on the equality x^{2p} = 1. If x \in \FF_q, then the order is either 1, p, or 2p. If the order is 1, then x = 1 and 2 = -2 \alpha, and squaring yields 4 = 8 which is only true in \FF_{2^n}, but q \neq 2. If the order is p, then p \mid q^2 - 1, so p \mid q - 1 or p \mid q + 1. If p \mid q - 1, then q \neq 2, 3 forces p \leq \frac{q - 1}{2} (p is an odd prime). Similarly, if p \mid q + 1, then p \leq \frac{q + 1}{2}. If the order is 2p, then 2p \mid q^2 - 1, or p \mid \frac{q^2 - 1}{2}, or p \mid \frac{q - 1}{2} \cdot (p + 1) or p \mid \frac{q + 1}{2} \cdot (q - 1), both which eventually give the desired inequality. Notice that this only works if 2 is not a quadratic residue mod q. However, if 2 is a quadratic residue mod q, then we get either p \mid q - 1 or 2p \mid q - 1, both of which yield the desired result.

This entry was posted in Math. Bookmark the permalink.

Leave a Reply

Your email address will not be published. Required fields are marked *