A Full Characterization of Finite Fields

Soundararajan Fields

The goal of these notes are to provide a coherent argumentative flow for fully characterizing the structure of finite fields, based on Soundararajan’s Finite Fields, in the order I find most natural and complete. All the theorems presented below have full proofs in the book, although not necessarily in the same order.

Note: In most cases, $p$ means prime and any other letter (such as $q$) just denotes an arbitrary number.

Note 2: We take some basic facts about the additive and multiplicative structure of fields as a given.

Theorem 1) The characteristic of a finite field $F$ is necessarily prime (the characteristic is the order of the multiplicative identity $1_F$ in the additive group of $F$). Proof: Assume the characteristic is some composite number $ab$ where $a,b>1$. Then, $(ab)1_F=0$, where $(ab)x$ is $x+x+\dots +x$ where addition is performed $ab$ times. By the distributive property, $(a)1_F\times (b)1_F=(ab)1_F=0$, and as a field is by definition an integral domain at least one of $(a)1_F$ or $(b)1_F$ must be $0$. This contradicts the fact that $ab$ is the additive order of $1_F$, and thus the characteristic must be some prime $p$.

Theorem 2) If any finite field $F$ of size $a$ is embeddable in another finite field $K$, then $|K|=a^k$ for some $k\in \mathbb{N}$. Proof: The field $K$ can be viewed as a vector space with scalar field $F$. If we let $k$ be the size of the basis in this vector space (any vector space has a basis; this is a result from functional analysis), then $|K|=a^k$.

Theorem 3) All fields $F$ of size $p$ for some prime $p$ are isomorphic to ${\mathbb{Z}}_p$ (i.e. $F_p$ is unique up to an isomorphism). Proof: Let $F$ be an arbitrary field of size $p$. Consider the element $1_F$ and the additive subgroup $(1_F)$. By Lagrange’s Theorem, $(1_F)$ must be the whole group $F$, and thus $1_F$ additively generates the whole field $F$. This allows one to construct a mapping $\varphi :F\to {\mathbb{Z}}_p$ defined by $\varphi ((a)1_F)=(a{)}_p$, which is clearly an isomorphism. Thus, $F\cong {\mathbb{Z}}_p$.

Theorem 4) Any finite field $F$ has size $p^k$ for some prime $p$ and $k\in \mathbb{N}$. Proof: Let $F$ be an arbitrary finite field with characteristic $p$ ($p$ must be prime by Theorem 1). Consider the additive subgroup $(1_F)$ in $F$; it is not difficult to see that, in fact, $(1_F)$ has a field structure within $F$ and $(1_F)\cong F_p$. Thus, $F_p$ is embeddable in $F$, and $F=p^k$ for some $k\in \mathbb{N}$ by Theorem 2.

Theorem 5) For any prime $p$ and $k\in \mathbb{N}$, there exists a finite field $F$ of size $p^k$. Proof: Consider the polynomial ring $F_p[x]$. For any $k\in \mathbb{N}$, there must be some polynomial $f(x)\in F_p[x]$ such that $f$ has degree $k$ and such that $f$ is irreducible in $F_p[x]$ (Soundarajan Chapter 4 has a really cool proof of this using Mobius inversion). As $f$ is irreducible and $F_p[x]$ is a PID (it is a Euclidean ring), the quotient ring $F_p[x]/(f)$ is a field of size $p^k$.

We now take a small detour into polynomial rings, which are critical for understanding finite field structure.

Theorem 6) Consider some finite field $F$ of size $q$ contained in a larger finite field $K$ of size $q^l$. For any element $a\in K$, there is a unique irreducible monic polynomial $m(x)\in F[x]$ of degree $d$ such that for any polynomial $f(x)\in F[x]$ with $a$ as a root, $m(x)|f(x)$. Furthermore, $d\le l$. This polynomial $m$ is called the minimal polynomial of $a$. Proof: Let $a$ be any arbitrary element of $K$. As $K$ is a vector space of dimension $l$ over $F$, the set $\{1,a,\dots ,a^l\}$ must be linearly dependent over $F$. Thus, there must exist some nonzero $f(x)\in F[x]$ with degree at most $l$ such that $a$ is a root of $f$. Consider the set of polynomials $\mathcal{M}\subset F[x]$ containing polynomials that have $a$ as a root. Clearly, $\mathcal{M}$ is an ideal in the ring $F[x]$, and as $F[x]$ is a PID (it is a Euclidean ring), there is some unique monic $m\in F[x]$ such that $\mathcal{M}=(m)$. One can see this $m$ is our desired minimal polynomial. Note that $m$ must be irreducible as, otherwise, $m$ can be factorized as $m=m_1{m}_2$ and $a$ must be a root of either $m_1$ or $m_2$, creating an immediate contradiction.

Theorem 7) Consider some finite field $F$ of size $q$ contained in a larger finite field $K$ of size $q^l$. For any $a\in K$, let $F[a]\subset K$ be the set of elements representable in terms of some sum $a_0+a_{1}a+a_2{a}^2+\dots$ where the coefficients $a_i\in F$. If we let $m\in F[x]$ be the minimal polynomial of $a$, then $F[a]\cong F[x]/(m)$. Proof: Take the mapping $\varphi :F[a]\to F[x]/(m)$ given by $\varphi (a_0+a_{1}a+\dots )=a_0+a_{1}x+a_2{x}^2+\dots$. Some tedious algebra shows $\varphi$ must be an isomorphism preserving the ring structures of $F[a]$ and $F[x]/(m)$. Interestingly, as $F[x]/(m)$ is necessarily a field ($m$ is irreducible), this automatically shows $F[a]$ must be a field for any $a\in K$.

Theorem 8) Consider some finite field $F$ of size $q$ contained in a larger finite field $K$ of size $q^l$. For any $a\in K$, let $m$ be the minimal polynomial of $a$ over $F$. The degree of $m$ (which we denote as $d$) must divide $l$. Proof: By Theorem 7, $F[a]\cong F[x]/(m)$ is a field of size $q^d$ embeddable in $K$. By Theorem 2, $q^l=(q^d{)}^k$ for some $k\in \mathbb{N}$. Thus, $d|l$.

Theorem 9) Consider some finite field $F$ of size $q$ contained in a larger finite field $K$ of size $q^l$. Any irreducible polynomial $f\in F[x]$ of degree $d|l$ has $d$ different roots in $K$ and thus is fully reducible into linear factors. Furthermore, no two different monic irreducible polynomials $f_1\in F[x]$ of degree $d_1|l$ and $f_2\in F[x]$ of degree $d_2|l$ can share roots in $K$. Proof: By the logic in Theorems 6 and 7, for any arbitrary element $a\in K$ there exists an irreducible monic polynomial $m$ of degree $d|l$ in $F[x]$ such that $a$ is a root of $m$. Thus, every $a\in K$ is a root of the product

$$P(x)=\prod _{m\in \mathcal{M}(d),d|l}m$$

where $\mathcal{M}(d)\subset F[x]$ is the set of irreducible monics of degree $d$ in $F[x]$. Over the extension $K[x]$ of $F[x]$, the monic $P(x)$ must then satisfy

$$\prod _{a\in K}(x-a)|P(x)$$

The degree of the LHS is $|K|=q^l$, and the degree of the RHS must also be $q^l$ as $\sum d|\mathcal{M}(d)|=q^l$ (see Soundararajan Chapter 4 for more). As both sides are monic, this forces

$$\prod _{m\in \mathcal{M}(d),d|l}m=P(x)=\prod _{a\in K}(x-a)$$

Note that $K[x]$ is a unique factorization domain as it is a Euclidean ring, and all degree-1 monics are trivially irreducible over $K[x]$. Thus, for any $m\in \mathcal{M}(d)$ such that $d|l$, $m$ is fully reducible into some product $\prod (x-a_i)$. We can further say that no two irreducibles $m\in K[x]$ of degree $d|l$ share a root in $K[x]$.

Theorem 9 is a very strong statement on the structure of the field $K$ that contains subfield $F$. A direct corollary due to uniqueness is the fact that for any root $a\in K$ of an irreducible monic $m\in F[x]$ with degree $d|l$, $m$ is necessarily the minimal polynomial of $a$. This also gives us the fact that $F[a]$ is isomorphic to $F[x]/(m)$ and has size $p^d$.

Theorem 10) The finite field $F_{p^k}$ of size $p^k$ is unique up to an isomorphism. Proof: Arbitrarily choose some fixed monic irreducible polynomial $f(x)$ of degree $k$ in $F_p[x]$. For any arbitrary finite field $F$ of size $p^k$, it suffices to show $F\cong F_p[x]/(f)$.

Note the characteristic of $F$ must clearly by $p$. By constructing the additively generated group $(1_F)$, we can see $F$ necessarily contains $F_p$. Then, by Theorem 9, our fixed $f(x)\in F_p[x]$ must contain $k$ distinct roots in $F$. Let $a$ be an arbitrary root. Again by theorem 9, $f$ is the minimal polynomial of $a$, and $F_p[a]\cong F_p[x]/(f)$. Trivially by definition, $F_p[a]\subset F$, but $|F_p[a]|=p^k=|F|$ and thus $F=F_p[a]$. Thus, $F\cong F_p[x]/(f)$ and we are done.

Theorem 11) For any $d|k$, the field $F_{p^k}$ contains a unique subfield of size $p^d$. Proof: Note this theorem fully characterizes all subfields of $F_{p^k}$, as any subfield of $F_{p^k}$ must be of size $p^d$ for some $d|k$ by Theorem 2. For any $d|k$, we can easily construct a subfield of size $p^d$ by constructing $F_p$ inside $F_{p^k}$, taking a monic irreducible polynomial $f(x)\in F_p[x]$ of degree $d$, and taking $F_p[x]/(f)$ (note this is a “subfield” of $F_{p^k}$ as it is isomorphic to $F_p[a]$ where $a$ is a root of $f(x)$ in $F_{p^k}$). It now suffices to show uniqueness of such subfields.

Consider the subfield $G$ of size $p^d$ in $F_{p^k}$. All elements of $G$ must be roots of the polynomial $x^{p^d}-x=0$. However, this polynomial contains at most $p^d$ distinct roots in $F_{p^k}$. Thus, $G$ is precisely the set of roots of $x^{p^d}-x=0$ in $F_{p^k}$, which must be unique.

Theorem 12) Consider an element $a\in F_{p^k}$. Let $r$ be the multiplicative order of $a$ and $m$ be the minimal polynomial of $a$ in $F_p[x]$. Then, the degree $d$ of $m$ is precisely the order of $p$ mod $r$. Proof: Let $l$ be the order of $p$ mod $r$. Clearly, as $a$ is in the multiplicative group $F_{p^k}^{\times }$, $r|p^k-1$ and $l|k$. What is an intuitive interpretation of $l$? Note that $l$ is the first number such that $a^{p^l}=a$. Thus, $a$ is a solution of the polynomial $x^{p^l}-x=0$, and as $l|k$, $a$ is in the unique subfield $G$ of size $p^l$ in $F_{p^k}$. As $F_p$ is a subfield of $G$, $F_p[a]\cong F_p[x]/(m)$ is a subfield of $G$ as well. In fact, $F_p[x]/(m)$ must be isomorphic to the whole field $G$, as otherwise $a$ must be contained in a smaller subfield $G^{\prime }$ of $G$ and satisfy $x^{p^{l^{\prime }}}-x=0$ for some $l^{\prime }<l$, which cannot happen. Thus $F_p[x]/(m)\cong G$, and $p^d=p^l$. This gives $d=l$, as desired.

Theorem 13) Let $a\in F_{p^k}$ and $m$ be the minimal polynomial of $a$ in $F_p[x]$ with degree $d$. The roots of $m$ are precisely $a^0=a,a^p,a^{p^2},\dots ,a^{p^{d-1}}$. Proof: For any polynomial $f\in F_p[x]$, if $w\in F_{p^k}$ is a root then $w^p$ must also be a root. This is because $f(x{)}^p=f(x^p)$ in $F_p[x]$ and thus $f(w^p)=f(w{)}^p=0$. Therefore, for an arbitrary $a\in F_{p^k}$ with minimal polynomial $m$, all of the numbers $a,a^p,a^{p^2},\dots$ must be roots. In particular, by Theorem 12, this list contains precisely $d$ unique elements $a,a^p,a^{p^2},\dots ,a^{p^{d-1}}$. As $m$ contains exactly $d$ distinct roots in $F_{p^k}$, we can conclude the roots of $m$ are precisely $a,a^p,a^{p^2},\dots ,a^{p^{d-1}}$.

We can consolidate the unique subfield structure and polynomial ring structure of finite field $F_{p^k}$ via the following visualization. $F_{p^k}$ contains a semi-ordered hierarchy of unique subfields $F_{p^d}$ with $d|k$, where if $d_1|d_2$ then $F_{p^{d_1}}\subset F_{p^{d_2}}$. Each element has a “smallest” subfield $F_{p^l}$ it is contained in, with $l$ being the order $p$ over the modulus of its multiplicative order. Let $G_l$ be the elements such that their “smallest” subscribed subfield is $F_{p^l}$. $G_l$ is precisely the set of elements whose minimal polynomials in $F_p[x]$ have degree $l$. Alternatively, $G_l$ is the set of all the roots in $F_{p^k}$ of irreducible monics in $F_p[x]$ with degree $l$. Thus, the unique subfield picture and polynomial ring structure of finite fields is highly interconnected.