Finding Gemstones: on the quest for mathematical beauty and truth
< Previous Post Next Post >

A proof of the existence of finite fields of every possible order

This is our first contributed gemstone! Submitted by user Anon1.

In the following, p denotes a prime. We wish to prove that, for all positive integers n, there is a finite field of order pn. Step 1. Restating the problem.

Claim: It suffices to show that, for some power of p (call it q), there exists a finite field of order qn.

Proof. Suppose there is a field F such that |F|=qn. The claim is that the solution set to xpn=x in F is a subfield of order pn.

Since q is a power of p, we have pn1|qn1. Since qn1 is the order of the cyclic group F×, we know that F× has a unique cyclic subgroup of order pn1. This contributes pn1 solutions to xpn=x in F. But 0 is another solution, since it is not an element of F×. This gives pn solutions, so this gives all solutions.

It remains to show that these solutions form a subfield of F. Since they form a finite set, it suffices to show that they are closed under addition and, since they include 0, it suffices to show they are closed under multiplication.

Closure under multiplication is immediate: xpn=x and ypn=y implies (xy)pn=xpnypn=xy.

Closure under addition is similarly easy: Since |F|=q and q is a power of p, the field F has characteristic p. This means that, for all x,yF, (x+y)p=xp+yp. Applying this n times yields (x+y)pn=xpn+ypn. If xpn=x and ypn=y, then it follows that (x+y)pn=x+y. We are done with Step 1. Step 2. Reducing to an asymptotic problem.

Claim: There are arbitrarily large k such that there is a finite field of order q=pk.

Proof. If fFp[x] is irreducible and of degree k, then Fp[x]/(f) is a field of order pk. So we need to prove that the degrees of irreducible polynomials in Fp[x] get arbitrarily high. Since Fp[x] has only (p1)pk polynomials of degree k, it suffices to prove that Fp[x] has infinitely many irreducible polynomials.

At this point we use Euclid’s argument: if f1,,fN are all the irreducibles in Fp[x], then 1+f1fN cannot be factored into irreducibles (and isn’t constant), contradicting the fact that Fp[x] is a unique factorization domain. Therefore Fp[x] has infinitely many irreducibles and we are done. Step 3. Counting the irreducible polynomials of degree d over various Fq.

Claim: If q is a power of p for which there is a finite field of order q (here denoted Fq), then the number of irreducible monic polynomials of degree d over Fq is a polynomial (call it Id(q)) depending only on d, evaluated at q.

Proof. This proceeds by strong induction on d. The base case is d=1: any linear polynomial is irreducible, and there are q monic linear polynomials over Fq.

Now suppose d>1. There are qd monic degree d polynomials over Fq. To count how many are irreducible, we remove the ones which are reducible: If a monic polynomial is reducible, it can be written uniquely as a product of monic irreducibles of lower degree. These degrees add up to d, so they give a partition λ of d which can be any partition except (d) itself.

Specifically, for each such partition λ suppose ai is the number of parts of size i. Then Id(q)=qdλd,λ(d)i=1d(Ii(q)+ai1ai), which is a polynomial in q by the strong induction hypothesis.

Now, it suffices to show that for any given n, In(q)>0 for sufficiently large q. For, by step 2, this will give us a power of p called q for which Fq exists and such that there is a monic irreducible polynomial over Fq of degree n. By step 1 we are then done.

Since In is a polynomial, this amounts to showing that In has a positive leading coefficient for all n. This we do now: Step 4. Showing that the counting polynomial In has positive leading coefficient.

Claim: For all n, In has degree n and leading coefficient 1/n.

Proof. Again we proceed by strong induction on n. When n=1, we have In(q)=q and we are done. So suppose n>1. Then as in step 3, we have In(q)=qnλn,λ(n)Πi=1n(Ii(q)+ai1ai). Since an=0, we can restrict the products to only i<n. Then the degree of each of these products is i=1niai=n by the induction hypothesis, and so In(q) has degree at most n. Moreover, assuming by the induction hypothesis that the coefficient of qi in Ii(q) is 1/i, we have that the coefficient of qiai in (Ii(q)+ai1ai) is 1ai!iai.

Finally, it follows that the coefficient of qn in In(q) is 1λn,λ(n)Πi=1n1ai!iai. Now, notice that for a given λ, the product zλ=a1!1a1a2!2a2an!nan is the well-known demoninator of the formula n!/zλ for the size of the conjugacy class of elements of shape λ in the symmetric group Sn. Thus we have λnn!zλ=n!, and so λn1zλ=1. It follows from this and the formula for our coefficient above that the coefficient is simply λ=(n)1zλ=1/n, and the claim is proven.