Finite Fields

Size of Finite Fields

Lemma

The characteristic of any field is either zero or a prime.

Proof Assume a field $F$ has characteristic neither zero nor a prime, say $n$. Then $n\cdot 1_F=0_F$, where $1_F$ is the multiplicative identity of $F$ and $0_F$ is the additive identity of $F$. Let $p$ be the smallest prime divisor of $n$. Then, we have $p\cdot 1_F=0_F$, which contradicts the assumption that the characteristic of $F$ is neither zero nor a prime. $\square$

Lemma

A finite field must have characteristic $p$ for some prime $p$ and its order is $p^r$ for some $r\in \mathbb{N}$.

Proof Let $F$ be a finite field. The characteristic of a finite field cannot be zero, so it must be a prime $p$. Hence, $F$ contains the finite subfield ${\mathbb{F}}_p$. Note that $F$ is finite, thus a finite-dimensional vector space over ${\mathbb{F}}_p$. Let $r$ be the dimension of $F$ as a vector space over ${\mathbb{F}}_p$. Then, the order of $F$ is $p^r$. $\square$

e.g. Consider ${\text{F}}_4\cong {\text{F}}_2[x]/(x^2+x+1)=:K$. Suppose $\alpha$ is a root of $x^2+x+1$ in ${\text{F}}_4$. Then, we have ${\text{F}}_4=\{0,1,\alpha ,\alpha +1\}$. And $\alpha +1$ is also a root of $x^2+x+1$.

Warning

Do not confuse the field ${\mathbb{F}}_4$ with the ring $\mathbb{Z}/4\mathbb{Z}$, which isn’t a field. Indeed, $\mathbb{Z}/n\mathbb{Z}$ is a field if and only if $n$ is prime. (See proposition)

Properties of Finite Fields & The Frobenius Automorphism

Frobenius Automorphism

The Frobenius automorphism of a field $F$ of characteristic $p$ is the map $\varphi :F\to F$ defined by $\varphi (x)=x^p$ for all $x\in F$.

Note that this is NOT a well-defined homomorphism for rings. But it is a well-defined homomorphism for finite fields, which we will show next.

Proof First, we show that $\varphi$ is a homomorphism. Let $x,y\in F$, then we have $\varphi (x+y)=(x+y{)}^p=x^p+y^p=\varphi (x)+\varphi (y),$where the second equality follows from the binomial theorem, all coefficients in the middle are divisible by $p$, thus vanish. Multiplication is preserved trivially: $\varphi (xy)=(xy{)}^p=x^p{y}^p=\varphi (x)\varphi (y).$Thus, $\varphi$ is a homomorphism. Next, we show that $\varphi$ is bijective. Since $\varphi$ is a homomorphism, it is injective, thus automatically surjective by the proposition. $\square$

Theorem

Let $p$ be a prime integer, and let $q=p^r$ be a positive power of $p$. Then

1. The elements of a order $q$ field $K$ are exactly fixed points of ${\varphi }^r$, where $\varphi$ is the corresponding Frobenius automorphism. In other words, $r$ is the smallest integer such that ${\varphi }^r=\mathrm{id}$.
2. Any finite field of order $q$ is isomorphic to ${\text{F}}_p[x]/(f)$ for some polynomial $f\in {\text{F}}_p[x]$. Equivalently, $K$ is a finite extension of ${\text{F}}_p$, and we can write $K={\text{F}}_p[\alpha ]$, where $\alpha$ is a root of an irreducible polynomial $f\in {\text{F}}_p[x]$ of degree $r$.
3. Let $K$ be a field of order $q$. The multiplicative group $K^{\times }$ of nonzero elements of $K$ is a cyclic group of order $q-1$.
4. There exists a field of order $q$, and all fields of order $q$ are isomorphic.
5. If $F$ is a field of order $p^r$ and $K$ is a field of order $p^s$, then there is a homomorphism $F\to K$ if and only if $r\mid s$. In this case, it is an isomorphism if and only if $r=s$.

Proof We shall prove each statement one by one:

1. Let $K$ be a field of order $q$. Note that the group $K^{\times }$ has order $q-1$. Therefore the order of any element $x\in K^{\times }$ divides $q-1$ by the Lagrange’s Theorem, so $x^{q-1}=1$, which means $x^q=x$. Observe that $0$ is also a fixed point of ${\varphi }^r$, so we have ${\varphi }^r(x)=x$ for all $x\in K$. We shall show the “in other words” part in (3). $\square$
3. Since $K^{\times }$ is a finite Abelian group, by the structure theorem, we can write $K^{\times }\cong {\mathbb{Z}}_{d_1}\times {\mathbb{Z}}_{d_2}\times \cdots \times {\mathbb{Z}}_{d_k}$where $q-1=d_1{d}_2\cdots d_k$ and $d_1\mid d_2\mid \cdots \mid d_k$. So $d_k$ is the exponent of $K^{\times }$ (i.e. the smallest positive integer $e$ such that $x^e=1$), and $x^{d_k}=1$ for all $x\in K^{\times }$. That is, the polynomial $x^{d_k}-1$ has $q-1$ roots in $K$, so its degree, $d_k$ has to be greater than or equal to $q-1$. On the other hand, by (1), we know that $x^{q-1}=1$ for all $x\in K^{\times }$, so $d_k\mid q-1$ (since $d_k$ is the exponent), which means $d_k\le q-1$, thus $d_k=q-1$. Therefore, $K^{\times }\cong {\mathbb{Z}}_{q-1}$ is cyclic. $\square$
4. We know that the elements of a field of order $q$ will be roots of the polynomial $x^q-x$. There exists a field extension $L$ of ${\text{F}}_p$ in which this polynomial splits completely by the proposition. We claim that the set of all its roots in $L$ is a field of order $q$. To see this, we need to check that $x^q-x$ has no multiple roots, as well as this set is indeed a field. Note that the derivative of $x^q-x$ is $q{x}^{q-1}-1=-1$ in a field of characteristic $p$. Thus, the polynomial $x^q-x$ has no multiple roots. Moreover, clearly, $0$ and $1$ are roots of $x^q-x$. Let $\alpha$ and $\beta$ be the roots of $x^q-x$, then we have $\alpha +\beta ={\alpha }^q+{\beta }^q=(\alpha +\beta {)}^q$which means $\alpha +\beta$ is also a root of $x^q-x$. So the set of roots of $x^q-x$ is closed under addition. The same holds for multiplication clearly, so the set of roots of $x^q-x$ is indeed a field. We now show that two fields $K_1$ and $K_2$ of order $q$ must be isomorphic. Let $K_1={\text{F}}_p[\alpha ]$ and $K_2={\text{F}}_p[\beta ]$, where $\alpha$ and $\beta$ are roots of some irreducible polynomials $f,g\in {\text{F}}_p[x]$ of degree $r$ respectively. We may assume that $\alpha \ne \beta$ and both $f$ and $g$ are not linear, otherwise $K_1=K_2$ naturally. Note that $\alpha$ is also a root of $x^q-x$, so $f\mid x^q-x$. Since $x^q-x$ splits completely in $K_2$, there is some element $\theta \in K_2$ that is also a root of $f$, so the map that $\alpha \mapsto \theta$ will be an injective homomorphism. Thus it is an isomorphism since $K_1$ and $K_2$ are finite fields of the same size. $\square$
5. Based on (4), we can assume without loss of generality that $F\supset {\text{F}}_p$ and $K\supset {\text{F}}_p$ are field extensions of ${\text{F}}_p$, and it suffices to show that $F$ is a subfield of $K$ iff $r\mid s$. If $F\subset K$ is a subfield, then by multiplicative property, we have $[K:F][F:{\text{F}}_p]=[K:{\text{F}}_p]$, so $[k:F]r=s$, which means $r\mid s$. Conversely, if $r\mid s$, then we can write $s=qr$ for some integer $q$. For any element $a\in F$, $a$ is a root of $x^{p^r}-x$ in $F$, so it satisfies $a^{p^s}-a=a^{(p^r{)}^q}-a=a{a}^{(p^r{)}^{q-1}}-a=a^{p^r}-a=0$, thus $a\in K$. Therefore, $F\subset K$. $\square$