Achyut BharadwajSeptember 2022
Introduction
#
A well known theorem about finite fields states the following.
$F$ is a finite field if and only if
$|F| = p^k$ for some prime $p$ and positive integer $k$.
In this write-up, we prove the first part of the above theorem, i.e. if
$F$ is a finite field, then $|F| = p^k$ using a different approach.
Introduction to Finite Fields
#
We first list down some basic definitions that will be used as we move
forward in this write-up.
Definition-1#
(Field)
A field is defined as a set of
elements, along with two operations ($+, \cdot$) that satisfies the
following, for any $a, b, c \in F$:
$a+(b+c) = (a+b)+c$ and $a\cdot(b\cdot c) = (a\cdot b)\cdot c$
$a+b = b+a$ and $a\cdot b = b\cdot a$
$a\cdot(b+c) = a\cdot b + a\cdot c$
There exists a unique element $0\in F$ such that $a+0 = 0+a = a$ and
a unique element $1\in F$ such that $1\cdot a = a\cdot1 = a$
For every $a\in F$, there exists a unique element $-a$ such that
$a+(-a)=0$ and a unique element $a^{-1}$ such that
$a\cdot a^{-1} = 1$
Definition-2#
(Finite Field)
A finite field is a field with finite
cardinality (i.e. with finitely many elements).
Some examples of finite fields are the fields
$\mathbb{Z}_p = {0, 1, 2, \dots, p-1}$ where $p$ is a prime. We can
also have finite fields such as
$\mathbb{Z}_3[i] = {0, 1, 2, i, 2i, 1+i, 1+2i, 2+i, 2+2i}$. Notice
however, that $\mathbb{Z}_2[i] = {0, 1, i, 1+i}$ is not a finite field
since we cannot find a multiplicative inverse for $1+i$. Is there any
other finite field with $4$ elements?
Note that we may write $i$ as a root of the polynomial $x^2+1$ over
$\mathbb{Z}_2$. In other words,
$\mathbb{Z}_2[i] = \mathbb{Z}_2[x]/x^2+1$ (i.e. the quotient ring
obtained modulo $x^2+1$). What if we found another polynomial
$P(x)\in\mathbb{Z}_2[x]$ to replace $x^2+1$ so that
$\mathbb{Z}_2[x]/P(x)$ has $4$ elements and is a finite field?
Consider $P(x) = x^2+x+1$. Then,
(1) $$F=\mathbb{Z}_2[x]/x^2+x+1 = \{0, 1, x, x+1\}$$
We can check that each
element of the above has an inverse. Thus $F=\mathbb{Z}_2[x]/x^2+x+1$ is
a finite field.
We can similarly check that(2) $$\mathbb{Z}_2[x]/x^3+x+1$$
is also a finite
field. Definition-3#
(Homomorphism)
A homomorphism between two fields
$(F, +, \cdot)$ and $(G, \oplus, \odot)$ is defined as a map
$\sigma \colon F \to G$ such that, for any $a, b \in F$:
$\sigma(a+b) = \sigma(a) \oplus \sigma(b)$
$\sigma(a\cdot b) = \sigma(a)\odot\sigma(b)$
Definition-4#
(Isomorphism)
An isomorphism between two fields is defined
as a homomorphism that is bijective.
Definition-5#
(Automorphism)
An automorphism on a field $F$ is defined
as an isomorphism from $F$ onto itself.
Definition-6#
(Characteristic)
The characteristic of a field $F$ is
defined as the smallest $p\in\mathbb{N}$ such that
$\sum_{j=1}^p (1) = 0$, where $1$ is the multiplicative identity and $0$
the additive identity corresponding to $F$. If there does not exist such
a positive integer $p$, then the characteristic of $F$ is defined to be
$0$.
Now, we list and prove some basic results about finite fields that
will be used going forward.
Proposition-1#
Every finite field is an integral
domain. That is, if $ab = 0$ in $F$, then $a=0$ or $b=0$.
Proposition-2#
Every homomorphism between two finite fields
is injective.
Proposition-3#
A field is finite if
and only if it has a non-zero characteristic.
Proposition-4#
Every finite field has a prime characteristic.
Proposition-5#
$\text{char}(F)$ divides $|F|$
A Combinatorial Identity
#
In this section, we prove that
(3) $$p\mid\binom{n}{k}\forall k \in [1, n-1]\cap\mathbb{Z}$$
if and only if
$n=p^\alpha$ for some positive integer $\alpha$ using elementary
methods. This will be used to prove some important properties about
automorphisms in the coming sections.
Notice that we have two directions to prove. The first being that if
$n=p^\alpha$ for some positive integer $\alpha$, then $p$ divides all of
$\binom{n}{k}$ with $k$ being an integer strictly between $0$ and $n$.
Before we proceed, we state a notation and list some properties related
to it. We will not be proving the properties in this article.
Let $v_p(m)$ denote the highest power of $p$ in the prime factorization
of $m$. In other words,(4) $$p^{v_p(m)}\mid m \text{ but } p^{v_p(m) + 1} \nmid m$$
The following
are true:(5) $$v_p(n!) = \sum_{j=1}^\infty \left\lfloor \frac{n}{p^j} \right\rfloor$$
(6) $$v_p(ab) = v_p(a) + v_p(b)$$
(7) $$v_p(a/b) = v_p(a) - v_p(b)$$
Now, let $n=p^\alpha$ since we are proving the first direction. So,
(8) $$v_p(n!) = \sum_{j=1}^\infty \left\lfloor \frac{p^\alpha}{p^j} \right\rfloor = \sum_{j=1}^\alpha \left\lfloor p^{\alpha - j} \right\rfloor = p^{\alpha-1} + p^{\alpha-2}+\cdots+1$$
Now,(9) $$\begin{aligned} v_p(k!(n-k)!) &= v_p(k!)+v_p((n-k)!) \\ &= \sum_{j=1}^\infty\left(\left\lfloor \frac{k}{p^j} \right\rfloor + \left\lfloor \frac{n-k}{p^j} \right\rfloor\right) \\ &= \sum_{j=1}^\alpha \left(\left\lfloor \frac{k}{p^j} \right\rfloor + \left\lfloor \frac{n-k}{p^j} \right\rfloor\right)\end{aligned}$$
since $k$ and $n-k$ are both less than $n$ by assumption. We can take
the term $j=\alpha$ outside the summation to get(10) $$v_p(k!(n-k)! = \sum_{j=1}^{\alpha-1}\left(\left\lfloor \frac{k}{p^j} \right\rfloor + \left\lfloor \frac{n-k}{p^j} \right\rfloor\right) + \left\lfloor \frac{k}{p^\alpha} \right\rfloor + \left\lfloor 1-\frac{k}{p^\alpha} \right\rfloor$$
Since $0<\frac{k}{p^\alpha}<1$,(11) $$\left\lfloor \frac{k}{p^\alpha} \right\rfloor + \left\lfloor 1-\frac{k}{p^\alpha} \right\rfloor = 0 + 0 = 0$$
Hence,(12) $$v_p(k!(n-k)! = \sum_{j=1}^{\alpha-1}\left(\left\lfloor \frac{k}{p^j} \right\rfloor + \left\lfloor \frac{n-k}{p^j} \right\rfloor\right)$$
Now, we use the identity that(13) $$\left\lfloor x+y \right\rfloor\geq \left\lfloor x \right\rfloor + \left\lfloor y \right\rfloor$$
in the above to get that(14) $$\left\lfloor \frac{k}{p^j} \right\rfloor + \left\lfloor \frac{n-k}{p^j} \right\rfloor\leq \left\lfloor \frac{k}{p^j}+\frac{n-k}{p^j} \right\rfloor = \left\lfloor \frac{n}{p^j} \right\rfloor$$
Since $n=p^\alpha$, $n/p^j = p^{\alpha - j} \in \mathbb{Z}$. Thus,(15) $$\left\lfloor \frac{k}{p^j} \right\rfloor + \left\lfloor \frac{n-k}{p^j} \right\rfloor\leq p^{\alpha - j}$$
Plugging this into the summation, we get(16) $$v_p(k!(n-k)!)\leq \sum_{j=1}^{\alpha - 1}p^{\alpha - j}=p^{\alpha - 1}+p^{\alpha - 2} + \cdots + p$$
The RHS of the above equation is strictly less than
$p^{\alpha-1} + p^{\alpha-2}+\cdots+1$. Thus,(17) $$v_p(k!(n-k)!) < v_p(n!)$$
Hence,(18) $$v_p(n!) - v_p(k!(n-k)!) = v_p\left(\frac{n!}{k!(n-k)!}\right)=v_p\binom{n}{k}>0$$
This implies that $p\mid \binom nk$ for all $k$ strictly between 0 and
$n$, thus completing the first direction of our proof. We now proceed to
proving the other direction of the proof. That is, given that
$p\mid \binom nk$ for all $k$ strictly between $0$ and $n$, we prove
that $n=p^\alpha$.
The most natural way to proceed is by setting up a contradiction. Assume
for the sake of contradiction, that $p\mid \binom nk$ for all $k$
strictly between $0$ and $n$ and $n=p^\alpha m$ where $m$ is an integer
such that $1<m<\alpha$. We aim to prove that there exists some value of
$k$ for which $p \nmid \binom nk$. The best strategy to do so is to
construct such a $k$.
We claim that $k=p^\alpha$ ensures that $p \nmid \binom{n}{k}$.
Similar to as in the previous part, we see that(19) $$v_p(n!) = m(p^{\alpha-1} + p^{\alpha - 2} + \cdots 1)$$
Now,(20) $$v_p(k!(n-k!)) = \sum_{j=1}^\alpha\left(\left\lfloor \frac{k}{p^j} \right\rfloor + \left\lfloor \frac{n-k}{p^j} \right\rfloor\right)$$
Since $k = p^\alpha$, we may simplify the RHS of the above equation to
get(21) $$v_p(k!(n-k)!) = \sum_{j=1}^\alpha p^{\alpha - j}m = m(p^{\alpha-1}+p^{\alpha - 2} + \cdots + 1)=v_p(n!)$$
Thus, $v_p\binom{n}{k} = 0$, which implies that $p \nmid \binom nk$. If
$m\neq1$, then $k$ is between $0$ and $n$. Contradiction. This completes
our proof.Automorphisms of a Finite Field
#
Let us take a look at the finite field that we had constructed earlier,
(22) $$F = \mathbb{Z}_2[x]/x^2+x+1$$
Note that the characteristic of $F$ is
$2$. What are the automorphisms over this field? Can we find all of
them? Let us find some of them by trying to check whether a map
$\sigma\colon F\to F$ is a homomorphism.
Firstly, note that the map $\sigma\colon y \mapsto y$ is an
automorphisms as it clearly preserves both multiplication as well as
addition. Next, notice that the map $\sigma\colon y \mapsto xy$ is also
an automorphism. More generally, we see that the map(23) $$\sigma\colon y \mapsto \epsilon y$$
is an automorphism for any
$\epsilon\in F$.
Next, we also see that the map $\sigma \colon y \mapsto y^2$ is also a
automorphism. We may prove it as follows:Proving that multiplication is preserved. Consider $a, b \in F$.
Then, $\sigma(ab) = (ab)^2$. Moreover, since $\sigma$ is an
automorphism, we have
(24) $$\sigma(ab) = \sigma(a)\sigma(b) = a^2b^2 = (ab)^2$$
Proving that addition is preserved. Consider $a,b \in F$. Then,
(25) $$\sigma(a+b) = (a+b)^2 = a^2+2ab + b^2 = a^2 + b^2 = \sigma(a) + \sigma(b)$$
However, the map $\sigma \colon y \mapsto y^3$ is not an automorphism as
can be seen with a counterexample.
(26) $$\sigma(1+x) = (1+x)^3 = x^3 + x^2 + x +1 = x+1$$
But(27) $$\sigma(1) + \sigma(x) = 1^3+x^3 = 1 + x +1 = x$$
Thus
$\sigma(y) = y^3$ is not an automorphism.
It seems that the only powers of $y$ that are automorphisms are of the
form(28) $$\sigma\colon y \mapsto y^{2^k}$$
However, we also see that the
map $\sigma\colon y\mapsto y^5$ is an automorphism (by computing the
fifth power of each element and observing that the map is the same as
the map from $y$ to $y^2$). But it still holds that the only powers of
$y$ that are automorphisms with the power of $y$ less than or equal to
$4$ are maps of the form $\sigma\colon y \mapsto y^{2^k}$.
Can we find automorphisms that don’t map to a power of $y$? Is a map
like $\sigma \colon y \mapsto y^2 + 1$ an automorphism?
With $\sigma(y) = y^2+1$, we see that(29) $$\sigma(a)\sigma(b) = (a^2+1)(b^2+1) = (ab)^2 + a^2 + b^2 + 1$$
but(30) $$\sigma(ab) = (ab)^2 + 1 \neq \sigma(a)\sigma(b)$$
Hence,
$\sigma\colon y \mapsto y^2 + 1$ is not an automorphism.
With more examples, it becomes clear that the only automorphisms over
$F$ are maps of the form(31) $$\sigma\colon y \mapsto \epsilon y^{2^k}$$
where $\epsilon\in F$ and $k\in \mathbb{N}$ given that $2^k\leq |F|$. We
may generalise this observations to all finite fields as follows:Theorem-1#
The maps from a finite field $F$
onto itself, $\sigma \colon y \mapsto \epsilon y^{p^k}$ are all the
automorphisms over $F$ with degree less than or equal to the cardinality
of $F$, where $p$ is the characteristic of $F$, $\epsilon$ is an element
of $F$ and $k$ is a positive integer.
We work on proving the above theorem throughout this section.
It would be convenient if we could first eliminate the case when
$\sigma$ is a sum of more than one distinct powers of $y$ (such as when
$\sigma = y^2+1$). Once we eliminate this case, we are only left to
prove that $\sigma$ is an automorphism if and only if the power of $y$
in $\sigma$ is a prime power.
We now state this more rigorously. Any automorphism over any finite
field $F$ can be represented as
(32) $$\sigma \colon y \mapsto \sum_{r \in S}\epsilon_r y^r$$
where $S$ is
some finite nonempty subset of integers and $\epsilon_r$ is an element
of $F$ for all $r\in S$. Our approach to prove the theorem is as
follows:To prove that $|S| = 1$ for $\sigma$ to be an automorphism. This
leaves us with all possible automorphisms being
$\sigma\colon y \mapsto \epsilon y^n$ for some integer $n$.
To prove that, given $\sigma\colon y \mapsto \epsilon y^n$, $\sigma$
is an automorphism if and only if $n = p^k$ for some positive
integer $k$.
We start with proving $(1)$ above.
We have by assumption,
(33) $$\sigma(y) = \sum_{r\in S} \epsilon_r y^r$$
Since $S$ is a finite subset of integers, $S$ is bounded below. This
implies that $S$ has a minimal element, as can be proven by the well
ordering principle. Let $m$ be the minimum element of $S$. Also, let
$S’ = S\setminus {m}$. Suppose for the sake of contradiction that
$|S| > 1$. In other words, assume for the sake of contradiction that
$S’\neq\emptyset$. Now, we take out the term with power $m$ from the
summation to get:(34) $$\sigma(y) = \epsilon_my^m + \sum_{r\in S'} \epsilon_r y^r$$
So, the
summation on the RHS will have at least one term. We may take
$\epsilon_my^m$ out common from the above to get(35) $$\sigma(y) = \epsilon_my^m\left(1 + \sum_{r\in S'} {\epsilon_r}\epsilon_m^{-1} y^{r-m}\right)$$
Since $F$ is a field, $\epsilon_m^{-1}\in F$. So, let
$\delta_{r-m} = \epsilon_r\epsilon_m^{-1} \in F$.
Now, let $T = {s=r-m\mid r\in S}$ and $T’ = T\setminus{0}$. Since
$r\leq m$ for all $r\in S$, we must have $s \geq 0$ for all $s\in T$.
Thus, $T’\subset \mathbb{N}$. Also note that $|T| = |S|$ and
$|T’|=|S’|$. So, we may rewrite Eq-35
as(36) $$\sigma(y) = \epsilon_my^m\left(1 + \sum_{s\in T'} \delta_s y^{s}\right)$$
with none of $s\in T’$ being equal to $0$.
We let $\epsilon_my^m = \phi(y)$ and
$1+\sum_{s\in T’}\epsilon_sy^s = \psi(y)$. So, we have(37) $$\sigma(y) = \phi(y)\psi(y)$$
Since $\sigma$ is an automorphism, it
must be multiplicative. It is easy check that $\phi$ is multiplicative.
Thus, for $\sigma$ to be an automorphism, $\psi$ must also be
multiplicative.
Hence, for all $y\in F$(38) $$\psi(0) = \psi(0\cdot y) = \psi(0)\cdot\psi(y)$$
For the above to
hold, we must have $\psi(0) = 0$ or $\psi(y) = 0$ for all $y\in F$. If
$\psi(y) = 0$ for all $y\in F$, then $\sigma(y) = 0$ for all $y\in F$.
This contradicts the injectivity of $\sigma$. Hence, $\psi(0) = 0$.
Since(39) $$\psi(y) = 1+\sum_{s\in T'}\epsilon_sy^s$$
plugging in $y=0$, we
get(40) $$\psi(0) = 1 + \sum_{s\in T'}\epsilon_s(0)^s$$
Since $0\notin T’$,
the RHS of the above reduces to $1$. In other words, $\psi(0) = 1$.
But $\psi(0) = 0$. Hence, $0=1$. A contradiction, since $F$ is a field.
Thus, $T’ = \emptyset$, which in turn implies that $|S| = 1$.
Thus, any automorphism $\sigma$ is of the form(41) $$\sigma\colon y \to \epsilon y^n$$
for some integer $n$ and
$\epsilon \in F$. Since the $0$ element does not have an inverse, $n$
must be non-negative in order for $\sigma(0)=0$ . We can also easily
eliminate the case when $n=0$. Therefore, any automorphism is of the
form $\sigma\colon y \mapsto \epsilon y^n$ where $n$ is a positive
integer.
We now prove that $\sigma\colon y \to \epsilon y^n$ with
$n\in \mathbb{N}$ is an automorphism if and only if $n = p^k$ for some
positive integer $k$, where $p = \text{char}(F)$. This can be restated as
proving that $\sigma$ is both multiplicative and additive if and only if
$n = p^k$ since this implies $\sigma$ is an automorphism by Proposition-2. Since
$\epsilon y^n$ is multiplicative for all values of $n$, we are only left
to prove that $\sigma$ is additive if and only if $n=p^k$.
In other words, we are to prove that(42) $$\epsilon^n(a+b)^n =\epsilon^na^n +\epsilon^nb^n$$
for all $a, b \in F$
if and only if $n=p^k$. We may cancel $\epsilon^n$ from both sides of
the above since $F$ is a field. So, we are to prove that(43) $$(a+b)^n = a^n +b^n$$
for all $a,b\in F$ if and only if $n=p^k$. We
have,(44) $$\begin{aligned} (a+b)^n = \sum_{j=0}^n \binom nj a^jb^{n-j} = a^n + b^n + \sum_{j=1}^{n-1}\binom nj a^jb^{n-j}\end{aligned}$$
Therefore,(45) $$(a+b)^n = a^n + b^n \iff \sum_{j=1}^{n-1}\binom nj a^jb^{n-j}=0\forall a,b\in F$$
If we keep $b$ constant, then(46) $$P(a) = \sum_{j=1}^{n-1}a^jb^{n-j}$$
is a
polynomial in $F[a]$. So, we have that $\sigma$ is an automorphism if
and only if $P(a) = 0$ for all $a\in F$. We assumed that the degree of
the map is less than or equal to $|F|$. So, $n\leq |F|$, or $n-1 < F$.
$P(a)$ has degree $n-1$, and hence has at most $n-1$ roots since $F$ is
a field. So, the number of roots of $P(a)$ is less than $|F|$. But all
$|F|$ elements of $F$ are roots of $P(a)$. Hence, $P(a)$ must be the
zero polynomial. Thus,(47) $$(a+b)^n = a^n + b^n \iff \binom nj = 0 \text{ in } F\forall j\in[1,n-1]\cap\mathbb{Z}$$
Since $\binom nj \in \mathbb{Z}$, the only way that it reduces to $0$ in
$F$ is for it to be a multiple of $p = \text{char}(F)$. Hence,(48) $$\sigma \text{ is an automorphism in }F \iff p \mid \binom nj\forall j\in[1,n-1]\cap\mathbb{Z}$$
The RHS of the above holds if and only if $n=p^k$ as shown in the
previous section. This completes our proof.FlT Equivalent and Proof of the Main Theorem
#
In this section, we prove the main theorem, using the work in the
previous sections, and the following theorem, that is equivalent to
Fermat’s Little Theorem for finite fields:
Given a finite field $F$, for any element
$\epsilon\in F$, we have $\epsilon^{|F|} = \epsilon$ in $F$
Let
(49) $$\sigma\colon y \mapsto \epsilon y$$
By Theorem-1
$\sigma$ is an automorphism. That is, $\sigma$ is bijective. Hence,
$\sigma(y)$ returns all elements of $F$.
Consider the products(50) $$P_1 = \prod_{y\in F^\times} y$$
and(51) $$P_2 = \prod_{y\in F^\times}\sigma(y)$$
$F^\times$ is used to denote $F\setminus{0}$.
Since $\sigma(y)$ returns
all elements of $F$ and $\sigma(0) = 0$, we must have the above two
products be equal. So,(52) $$\prod_{y\in F^\times}y=\prod_{y\in F^\times}\sigma(y)=\prod_{y\in F^\times}\epsilon y = \epsilon^{|F|-1}\prod_{y\in F^\times}y$$
Thus,(53) $$\left(\epsilon^{|F|-1}-1\right)\prod_{y\in F^\times}y=\left(\epsilon^{|F|-1}-1\right)P_1=0$$
We cannot have $P_1=0$ since $F$ is an integral domain by Proposition-1. Hence,
$\left(\epsilon^{|F|-1}-1\right) = 0$, or(54) $$\epsilon^{|F|-1} = 1$$
We
may multiply both sides of the above by $\epsilon$ to get(55) $$\epsilon^{|F|} = \epsilon$$
thus completing the proof.We now proceed to prove our main theorem. That is, every finite field
has cardinality $p^k$ for some prime $p$.
Let
(56) $$\sigma\colon y \mapsto y^{|F|}$$
be a map from $F$ onto itself. By
Theorem-2, we have
$y^{|F|} = y$. So, $\sigma(y) = y$. This implies that $\sigma$ is an
automorphism and its degree is less than or equal to $|F|$. Thus, by
Theorem-1, we must have $|F| = p^k$ where $p$ is the
characteristic of $F$. This completes our proof for the main theorem.