and that there is a ring homomorphism „ : F ’ E, and because F is a

¬eld, either „ is injective or E is trivial. Also, recall that ρ being an F -

algebra homomorphism simply means that ρ is a ring homomorphism and

ρ(„ (a)) = „ (a) for all a ∈ F .

Now, if E is trivial, there is nothing to prove. Otherwise, as E contains a

copy of F , it must have characteristic p. Since q is a power of the character-

istic, the fact that ρ is a ring homomorphism follows from the discussion in

Example 9.42. Moreover, by Theorem 20.5, we have „ (a)q = „ (aq ) = „ (a)

for all a ∈ F . 2

Theorem 20.8. Let E be a ¬nite extension of F , and consider the map σ :

E ’ E that sends ± ∈ E to ±q ∈ E. Then σ is an F -algebra automorphism

on E. Moreover, if ± ∈ E is such that σ(±) = ±, then ± ∈ F .

Proof. The fact that σ is an F -algebra homomorphism follows from the pre-

vious theorem. Any ring homomorphism from a ¬eld into a ¬eld is injective

(see Exercise 9.38). Surjectivity follows from injectivity and ¬niteness.

For the second statement, observe that σ(±) = ± if and only if ± is a root

of the polynomial Xq ’ X, and since all q elements of F are already roots of

this polynomial, there can be no other roots. 2

The map σ de¬ned in Theorem 20.8 is called the Frobenius map on E

over F . As it plays a fundamental role in the study of ¬nite ¬elds, let us

develop a few simple properties right away.

Since the composition of two F -algebra automorphisms is also an F -

algebra automorphism, for any i ≥ 0, the i-fold composition σ i that sends

i

± ∈ E to ±q is also an F -algebra automorphism.

452 Finite ¬elds

Since σ is an F -algebra automorphism, the inverse function σ ’1 is also

an F -algebra automorphism. Hence, σ i is an F -algebra automorphism for

all i ∈ Z. If E has degree over F , then applying Theorem 20.5 to the ¬eld

E, we see that σ is the identity map, from which it follows that σ ’1 =

σ ’1 . More generally, we see that for any i ∈ Z, we have σ i = σ j , where

j = i mod .

Thus, in considering integer powers of σ, we need only consider the powers

σ 0 , σ 1 , . . . , σ ’1 . Furthermore, the powers σ 0 , σ 1 , . . . , σ ’1 are all distinct

maps. To see this, assume that σ i = σ j for some i, j with 0 ¤ i < j < .

Then σ j’i would be the identity map, which would imply that all of the q

j’i

elements of E were roots of the polynomial Xq ’ X, which is a non-zero

polynomial of degree less that q , and this yields a contradiction.

The following theorem generalizes Theorem 20.6:

Theorem 20.9. For k ≥ 1, let Pk denote the product of all the monic

irreducible polynomials in F [X] of degree k. For all positive integers , we

have

Xq ’ X = Pk ,

k|

where the product is over all positive divisors k of .

Proof. First, we claim that the polynomial Xq ’X is square-free. This follows

immediately from Theorem 20.4, since D(Xq ’ X) = q Xq ’1 ’ 1 = ’1.

So we have reduced the proof to showing that if f is a monic irreducible

polynomial of degree k, then f divides Xq ’ X if and only if k | . Let

E := F [X]/(f ), and let · := [X]f ∈ E, which is a root of f .

For the ¬rst implication, assume that f divides Xq ’ X. We want to show

that k | . Now, if Xq ’ X = f g, then · q ’ · = f (·)g(·) = 0, so · q = ·.

Therefore, if σ is the Frobenius map on E over F , then we have σ (·) = ·.

We claim that σ (±) = ± for all ± ∈ E. To see this, recall from Theorem 17.1

that for all h ∈ F [X] and β ∈ E, we have σ (h(β)) = h(σ (β)). Moreover,

any ± ∈ E can be expressed as h(·) for some h ∈ F [X], and so

σ (±) = σ (h(·)) = h(σ (·)) = h(·) = ±.

That proves the claim.

From the claim, it follows that every element of E is a root of Xq ’ X.

That is, ±∈E (X ’ ±) divides Xq ’ X. Applying Theorem 20.6 to the ¬eld

k k

E, we see that ±∈E (X ’ ±) = Xq ’ X, and hence Xq ’ X divides Xq ’ X.

By Theorem 20.3, this implies k divides .

20.2 The existence of ¬nite ¬elds 453

For the second implication, suppose that k | . We want to show that

f | Xq ’ X. Since f is the minimal polynomial of ·, and since · is a root

k k

of Xq ’ X, we must have that f divides Xq ’ X. Since k | , and applying

k

Theorem 20.3 once more, we see that Xq ’ X divides Xq ’ X. That proves

the second implication, and hence, the theorem. 2

For ≥ 1, let Π( ) denote the number of monic irreducible polynomials

of degree in F [X].

≥ 1, we have

Theorem 20.10. For all

q= kΠ(k). (20.1)

k|

Proof. Just equate the degrees of both sides of the identity in Theorem 20.9.

2

From Theorem 20.10 it is easy to deduce that Π( ) > 0 for all , and in

fact, one can prove a density result”essentially a “prime number theorem”

for polynomials over ¬nite ¬elds:

≥ 1, we have

Theorem 20.11. For all

q q

¤ Π( ) ¤ , (20.2)

2

and

/2

q q

Π( ) = +O . (20.3)

Proof. First, since all the terms in the sum on the right hand side of (20.1)

are non-negative, and Π( ) is one of these terms, we may deduce that

Π( ) ¤ q , which proves the second inequality in (20.2). Since this holds

for all , we have

/2

qk ≥ q ’ qk .

Π( ) = q ’ kΠ(k) ≥ q ’

k=1

k| k|

k< k<

Let us set

/2

q

qk = /2

’ 1),

S(q, ) := (q

q’1

k=1

so that Π( ) ≥ q ’ S(q, ). It is easy to see that S(q, ) = O(q /2 ), which

proves (20.3). For the ¬rst inequality of (20.2), it su¬ces to show that

454 Finite ¬elds

S(q, ) ¤ q /2. One can check this directly for ∈ {1, 2, 3} (verify), and for

≥ 4, we have

’1

¤ q /2. 2

/2+1

S(q, ) ¤ q ¤q

We note that the inequalities in (20.2) are tight, in the sense that Π( ) =

q /2 when q = 2 and = 2, and Π( ) = q when = 1. The ¬rst inequality

in (20.2) implies not only that Π( ) > 0, but that the fraction of all monic

degree polynomials that are irreducible is at least 1/2 , while (20.3) says

that this fraction gets arbitrarily close to 1/ as either q or are su¬ciently

large.

Exercise 20.1. Starting from Theorem 20.10, show that

’1 /k

Π( ) = µ(k)q ,

k|

where µ is the M¨bius function (see §2.6).

o

Exercise 20.2. How many irreducible polynomials of degree 30 over Z2 are

there?