Isomorphisms, homomorphisms, automorphisms. Classification of all finite fields

The word isomorphic means in mathematics that one can identify two structures by relabeling the elements of one structure.

For example, consider the residue class field $\mathbb Z_2$, the set of one-bit integers with addition and multiplication modulo 2:

Now consider the two-element set $S = \{$ $, $ $\}$ with the following addition and multiplication operations:

$+$

$\times$

If one replaces with $0$ and with $1$ then these are the addition and multiplication tables of the residue class field $\mathbb Z_2$. Therefore it is immediately obvious that the algebraic structure $(S; +, \times)$ satisfies the field axioms. Essentially, the field $S$ is the same as $\mathbb Z_2$. It would not be exactly correct to say that $S$ is equal to $\mathbb Z_2$ as the first is a set of faces, whereas the latter is a set of residue classes. Instead one says that the field $S$ is isomorphic to $\mathbb Z_2$. The relabeling function $f : S \to \mathbb Z_2$, $f($ $) = 1$, $f($ $) = 0$ is called the isomorphism between $S$ and $Z_2$.

For a mathematician studying the properties of some algebraic structure, it is always delightful to discover that the algebraic structure is isomorphic to another one — having different viewing angles on a problem is a good thing, as some facts might be easier to notice and prove in one representation than another. For a computer scientist, an isomorphism may also provide a way to perform computations more efficiently: if two fields are isomorphic but operations are faster in one field than the other and we have to evaluate a formula in the second field, we can transform the elements to the first field, do the operations and then transform them back, getting the same result as if we had done the operations in the second field. So, from an algorithmic viewpoint, two isomorphic algebraic structures are basically two different ways to represent the same data in memory.

Now that we have intuitively understood what an isomorphism is, let us try to express this idea in a formal way. Let $\mathcal{F}$ and $\mathcal{G}$ be two rings. An isomorphism between $\mathcal{F}$ and $\mathcal{G}$, i. e. a relabeling function $\kappa:\mathcal{F}\to\mathcal{G}$, must associate each element of $\mathcal F$ with exactly one element of $\mathcal G$ and vice versa: in other words, $\kappa$ must be one-to-one (i. e., $\kappa(a) \neq \kappa(b)$ if $a \neq b$) and onto (i. e., for any $c\in\mathcal{G}$ there exists $a\in\mathcal{F}$ such that $\kappa(a) = c$). It is easy to see that a function $\kappa$ which is one-to-one and onto is an isomorphism if and only if it preserves the addition and multiplication operations, i. e. it satisfies \begin{align}\tag{#} &\begin{aligned} \kappa(a+b)&=\kappa(a)+\kappa(b),\\ \kappa(a\cdot b)&=\kappa(a)\cdot\kappa(b). \end{aligned} \end{align}

Some examples and non-examples of isomorphisms are given in the figure below.

Figure (isomorphims and non-isomorphisms). a) This is the isomorphism $f : S \to \mathbb Z_2$, $\mapsto 1$, $\mapsto 0$ considered in the example above. b) Let $\mathcal{B}_2$ be the four-elemnt field considered in lesson The general way of constructing finite fields. The map $0 \mapsto 00$, $1 \mapsto 01$ is not an isomorphism from $\mathbb Z_2$ to $\mathcal B_2$ because it is not onto. c) The map $0 \mapsto 0$, $1 \mapsto 1$, $2 \mapsto 0$, $3 \mapsto 1$ is not an isomorphism from the ring $\mathbb Z_4$ to $\mathbb Z_2$ because it is not one-to-one. d) The map $00 \mapsto 00$, $01 \mapsto 01$, $10 \mapsto 11$, $11 \mapsto 10$ turns out to be an isomorphism from $\mathcal B_2$ to $\mathcal B_2$. Such isomorphisms — isomorphisms of algebraic structure with itself — are called automorphisms. e) The map $g : 0 \mapsto 1, 1 \mapsto 0$ is a one-to-one map from $\mathbb Z_2$ to $\mathbb Z_2$ but it is not an isomorphism because it does not preserve multiplication: for example, $1 \cdot 0 = 0$ but $g(1) \cdot g(0) = 0 \cdot 1 = 0 \neq g(0)$.

Since the zero and the identity element of a field are uniquely determined by its addition and multiplication (by Lemma (uniqueness of zero and identity) in the first lesson), any isomorphism $\kappa$ also satisfies \begin{align}\tag{##} &\begin{aligned} \kappa(0)&=0,\\ \kappa(1)&=1. \end{aligned} \end{align} (Note that here the $0$ on the left hand side of the equality sign is not necessarily the same thing as the $0$ on the right hand side: the $0$ on the left denotes the zero of $\mathcal F$, and the $0$ on the right — the zero of $\mathcal G$; the same goes for the symbol $1$ in the second equality and also the symbols $+$ and $\cdot$ in the equalities (#).)

Sometimes it also turns out to be useful to talk about homomorphisms — functions which satisfies the equations (#) and (##), but are not necessarily one-to-one or onto. So the formal definition of isomorphism and homomorphism is as follows.

As any field is a ring, the above definition also applies if $\mathcal F$ and $\mathcal G$ are fields.

It is an important theorem in mathematics, stated below, but not proven in this material, that any finite field can essentially be constructed using the method of constructing finite fields we found in the lesson The general way of constructing finite fields.

Maybe you are wondering why the theorem above does not mention another family of finite fields we know — the fields $\mathbb{Z}_n$ where $n$ is a prime number. This is because they are included in the family $\mathbb{Z}_n[\alpha]/(p(\alpha))$. Indeed, one can identify (at least up to an isomorphism) $\mathbb{Z}_n[\alpha]/\alpha$ with $\mathbb{Z}_n$.

Actually it turns out (but we also do not prove here) that if $n$ is a prime number then any two irreducible polynomials with coefficients in $\mathbb Z_n$ yield isomorphic fields if their degrees are equal, and that for any positive integer $k$ there exists an irreducible polynomial over $\mathbb Z_n$ whose degree is degree $k$. Therefore, as a complement to the preceding theorem, we have the following one.

Thus,

$\mathbb{F}_{p}$ is the same as $\mathbb{Z}_{p}$ for any prime $p$.

As we saw in lesson The general way of constructing finite fields, there is only one way to construct the field $\mathbb{F}_4$ using our general method of constructing finite fields, as there is a single quadratic irreducible polynomial with binary coefficients. This is not true for most other finite fields. For example, a cubic polynomial with coefficients in $\mathbb Z_2$ is irreducible if and only if neither zero nor one are its roots. There are exactly two such polynomials¹⁾ $\alpha^3+ \alpha+ 1$ and $\beta^3+\beta^2+1$. Both of them give a rise to $8$-element fields. It is obvious to ask whether these two structures:

• $\mathcal{F}$ a set of polynomials $f(\alpha)$ with reduction rules $2=0$ and $\alpha^3+ \alpha+ 1=0$;
• $\mathcal{G}$ a set of polynomials $g(\beta)$ with reduction rules $2=0$ and $\beta^3+ \beta^2+ 1=0$

define different objects or not. Well, we know from the theorem above, that the answer should be “not”: any two fields of the same size are isomorphic. But how does the isomorphism look like in this case? Let's find all the isomorphisms from $\mathcal{F}$ to $\mathcal{G}$.

To determine an isomorphism, or, more generally, a homomorphism $\kappa$ from $\mathcal{F}$ to $\mathcal{G}$, it is sufficient to determine the value $\kappa(\alpha)$, since the equalities \begin{align}\tag{#} &\begin{aligned} \kappa(a+b)&=\kappa(a)+\kappa(b),\\ \kappa(a\cdot b)&=\kappa(a)\cdot\kappa(b) \end{aligned} \end{align} and \begin{align}\tag{##} &\begin{aligned} \kappa(0)&=0,\\ \kappa(1)&=1 \end{aligned} \end{align} allow us to determine the behavior of $\kappa$ on all other elements of $\mathcal F$.

Indeed, for example, from equalities (#) and (##) it follows that the value of $\kappa$ at the element $\alpha^2 + \alpha + 1$ is $$\kappa(\alpha^2 + \alpha + 1) = \kappa(\alpha \cdot \alpha) + \kappa(\alpha) + \kappa(1) = \kappa(\alpha) \cdot \kappa(\alpha) + \kappa(\alpha) + 1 = \kappa(\alpha)^2 + \kappa(\alpha) + 1.$$ So, if, for example, we fix $\kappa(\alpha) = \beta^2 + \beta$ then we know that $\kappa$ must map the element $\alpha^2 + \alpha + 1$ to the element $$(\beta^2 + \beta)^2 + (\beta^2 + \beta) + 1 = \beta^4 + \beta + 1 = (\beta^3+ \beta^2+ 1)(\beta + 1) + \beta^2 = \beta^2.$$ Similarly we can express $\kappa(x)$ in terms of $\kappa(\alpha)$ for all elements $x \in \mathcal F$, since every element of $\mathcal F$ can be obtained from $\alpha$ using multiplication and addition, i. e. as the value of some polynomial at $\alpha$. In other words, from the equalities (#) and (##) it follows that $$\tag{¤} \kappa(p(\alpha)) = p(\kappa(\alpha))$$ for any polynomial $p$ with coefficients in $\mathbb Z_2$ (in the example we just had, we showed that this holds for $p(X) = X^2 + X + 1$, i. e. that $\kappa(\alpha^2 + \alpha + 1) = \kappa(\alpha)^2 + \kappa(\alpha) + 1$).

So, given an element $s(\beta) \in \mathcal{G}$ (a polynomial of $\beta$), there is at most one way to extend the mapping $\alpha \mapsto s(\beta)$ into a homomorphism from $\mathcal{F}$ to $\mathcal{G}$.

If we want to extend a mapping $\alpha \mapsto s(\beta)$ to a homomorphism $\kappa : \mathcal F \to \mathcal G$ using formula (¤), we face a problem: the map $\kappa$ may be not correctly defined by (¤), since any element $x \in \mathcal F$ can be expressed as $x = p(\alpha)$ in multiple ways. For example, in our example field $\mathcal F$ we have $0=\alpha^3+ \alpha+ 1$. So on one hand, (¤) says that $\kappa(0) = 0$ (if we take $p$ to be the zero polynomial). On the other hand, it says that $$\kappa(0) = \kappa(\alpha^3+ \alpha+ 1) = \kappa(\alpha)^3 + \kappa(\alpha) + 1 = s(\beta)^3+ s(\beta)+ 1.$$ So, if the element $s(\beta)$ does not satisfy $s(\beta)^3+ s(\beta)+ 1 = 0$ (in the field $\mathcal G$), then (¤) gives a contradiction and the map $\kappa$ is not correctly defined. In other words, $s(\beta)$ must be a root of the defining polynomial of the field $\mathcal F$. As the following theorem shows, this condition is also enough for the map $\kappa$ to be correctly defined by equality (¤); even more, it tells us that the map $\kappa$ so defined is indeed a homomorphism.

Proof

Coming back to our example, note that $\beta+ 1$, $\beta^2+ 1$ and $\beta^2+\beta$ are the roots of the polynomial $X^3+X+1$ in the field $\mathcal{G}$: \[\begin{align*} (\beta+ 1)^3+ (\beta+ 1)+ 1% &=\beta^3+ \beta^2+ \beta+ 1+ \beta+ 1+ 1=0\\ (\beta^2+ 1)^3+ (\beta^2+ 1)+ 1% &=\beta^2+ \beta^2+ 1+ 1=0\\ (\beta^2+ \beta)^3+ (\beta^2+ \beta)+ 1% &=\beta^2+ \beta+ 1+ \beta^2+ \beta+ 1=0 \end{align*}\] and thus polynomials $\beta+ 1$, $\beta^2+ 1$ and $\beta^2+ \beta$ are the only candidates for $s(\beta)$ (because $X^3+X+1$ is a cubic polynomial if regarded as a polynomial with coefficients in $\mathcal{G}$, and in any field, a polynomial which is not the zero polynomial has at most $d$ roots, where $d$ is its degree).

By the theorem above, each of these three choices of $\kappa(\alpha)$ determines a homomorphism. It remains to check whether these homomorphisms are isomorphisms, i. e. whether they are one-to-one and onto. It turns out that in this example, all three maps are isomorphisms. One way to check it is to compute, for each of these homomorphisms, all its values on all elements of $\mathcal F$ to confirm that it is indeed one-to-one and onto. For example, for the third homomorphism (the one with $\kappa(\alpha) = \beta^2 + \beta$) we get the following table.

It is obvious from the table that the map $\kappa$ is indeed one-to-one and onto. Analogously one can do the check for the other two homomorphisms. However, writing out all the values is rather tedious (and even more so for larger fields). Fortunately, there is a nice result about field homomorphisms.

For the proof, we need a simple lemma.

Proof of the Lemma.

Proof of the Theorem.

From the Theorem above, we know automatically that these three homomorphisms are one-to-one. In our case we also know that the fields $\mathcal F$ and $\mathcal G$ are of equal size, both consisting of $8$ elements. It is easy to see that any one-to-one map between two finite sets of equal size is onto. Therefore, all the three homomorphisms are isomorphisms.

There is yet another curious thing to note. Note that $\alpha+ 1$ and $\alpha^2+ \alpha$ are also the roots of the polynomial $X^3+X+1$ and thus correspondences $\alpha\mapsto \alpha+ 1$ and $\alpha\mapsto \alpha^2+ 1$ define isomorphisms from $\mathcal{F}$ to $\mathcal{F}$ itself. These are the automorphisms of $\mathcal{F}$. They can be thought of as symmetries of the field $\mathcal{F}$.