The field with four elements

Arithmetic on a finite set is usually introduced by wrapping the integers around a circle. That works when the circle’s length is prime and quietly fails when it is not.

What a field is required to do #

A field is a set with addition and multiplication in which the ordinary rules hold: both operations commute and associate, multiplication distributes over addition, there is a zero and a one, every element has a negative, and every non-zero element has a reciprocal.

That last clause is the only demanding one, and it is what separates a field from a ring. It is also the clause every argument in the previous four essays used: dividing in Lagrange’s formula, inverting a matrix, and the root-counting that made the code work.

An immediate consequence: a field has no zero divisors. If $ab = 0$ with $a \ne 0$, multiplying both sides by $a$’s reciprocal gives $b = 0$. So two non-zero elements never multiply to nothing, and a polynomial of degree $d$ can never have more than $d$ roots.

Where wrapping around fails #

The integers modulo $n$ — the arithmetic of a clock face — form a ring for every $n$. They form a field exactly when $n$ is prime.

For $n$ prime it works because of Bézout: if $a$ shares no factor with $n$, whole numbers $u$ and $v$ exist with $au + nv = 1$, so $au \equiv 1$ and $u$ is $a$’s reciprocal. Every non-zero residue is coprime to a prime, so every one is invertible.

For $n$ composite, write $n = ab$ with both factors between $1$ and $n$. Then $a$ and $b$ are both non-zero modulo $n$ and their product is zero. So there is a zero divisor, and a zero divisor cannot have a reciprocal.

The generator does not take that on trust either way. For the ring it searches for a pair of non-zero elements whose product is zero and for elements with no reciprocal, and asserts that both lists are empty exactly when the modulus is prime. For the field it checks every axiom over every triple.

So four elements should be impossible #

The obvious conclusion is that fields exist only at prime sizes, and the obvious conclusion is wrong.

There is a field with four elements. It is not the integers mod $4$ and it cannot be, since that ring has a zero divisor and the property of having one is not a matter of presentation. What it is instead is an arithmetic built on a different principle entirely.

Polynomials, modulo one that will not factor #

Start with the two-element field $GF(2)$, which is the integers mod $2$ and is a field because $2$ is prime.

Consider polynomials in one variable with coefficients from it: $0$, $1$, $x$, $x+1$, $x^2$, $x^2+x$, and so on. Adding and multiplying them is ordinary polynomial arithmetic with the coefficients reduced mod $2$.

Now pick a polynomial and work modulo it, exactly as the integers are worked modulo $n$. Take $x^2 + x + 1$. The remainders on division by it are the polynomials of degree less than two, of which there are four:

$$0,\quad 1,\quad x,\quad x+1.$$

Multiplication is polynomial multiplication followed by reduction. So $x \cdot x = x^2$, and $x^2 = (x^2+x+1) + (x+1) \equiv x+1$. Writing $\alpha$ for $x$, the whole multiplication table is generated by $\alpha^2 = \alpha + 1$.

The result is a field, and the reason is the same reason the integers mod a prime are one: $x^2+x+1$ does not factor over $GF(2)$. It has no root there, since substituting $0$ gives $1$ and substituting $1$ gives $1+1+1 = 1$, and a quadratic with no root does not factor. An irreducible modulus is a prime modulus, and the argument for reciprocals goes through unchanged.

The generator finds the modulus rather than being given it: it tries every monic polynomial of the right degree and takes the first with no root in the base field. Then it verifies the result — closure, commutativity, associativity over all $q^3$ triples, distributivity, and a reciprocal for every non-zero element.

What that field looks like #

Two features of $GF(4)$ are worth noticing because they are what makes it not the integers mod $4$.

Adding anything to itself gives zero. $1+1 = 0$, and $\alpha + \alpha = 0$. The additive structure is two independent copies of $GF(2)$, not a cycle of length four. Nothing in it counts to four.

Every element satisfies $z^4 = z$. The non-zero ones satisfy $z^3 = 1$, so the multiplicative structure is a cycle of length three — which is the subject of the next essay.

The number $4$ therefore appears in this field as $2^2$ and never as four of anything. That is the general situation, and it is why the answer to “which sizes are possible?” is about prime powers rather than about primes.

Reading the tables #

The two grids in each figure repay a slow look, because the difference between a field and a ring is visible in them without any algebra.

In a field’s multiplication table, every row and every column past the zeroth is a permutation of the elements. Multiplying by a fixed non-zero $a$ is an invertible map — its inverse is multiplication by $a$’s reciprocal — so it shuffles the field without collisions. Each symbol appears exactly once in each such row. That makes the table a Latin square with its first row and column removed, and it is the visual signature of invertibility.

In the integers mod $4$, the row for $2$ reads $0, 2, 0, 2$. A symbol appears twice, another not at all, and the row is not a permutation. That is what having no reciprocal looks like: multiplication by $2$ collapses four elements onto two, so nothing can undo it.

The shaded cells in the figures mark the products of two non-zero elements coming out zero, and there is exactly one such cell for each way the modulus factors. Their presence and the failure of the permutation property are the same fact seen twice.

Why prime powers, and nothing else #

The classification is short enough to give in full, and it explains the shape of everything above.

Let $F$ be a finite field. Add $1$ to itself repeatedly: $1, 1+1, 1+1+1, \ldots$ Since $F$ is finite the sequence repeats, so some sum of $p$ ones is zero, and the smallest such $p$ is the characteristic.

That $p$ must be prime. If $p = ab$ with both factors smaller, then the sums of $a$ ones and of $b$ ones are two non-zero elements whose product is zero, which a field cannot have.

So $F$ contains a copy of $GF(p)$ — the sums of ones — and $F$ is a vector space over it, since scaling by a sum of ones is defined and behaves. A finite vector space over $GF(p)$ of dimension $k$ has exactly $p^k$ elements, because an element is a list of $k$ coordinates each with $p$ choices.

Therefore $|F| = p^k$. There is no field with six elements, or ten, or fifteen — not because nobody has found one, but because $6$ is not a prime power and the argument above admits no exceptions.

The converse is also true and needs the construction: for every prime power there is a field, built as above from an irreducible polynomial of the right degree, and irreducible polynomials of every degree exist over every $GF(p)$.

That figure is the cleanest statement of the whole essay. Nine is a prime power, so a field of that size exists; the integers modulo nine are not it; and both objects have nine elements. Size does not determine structure, and the naive construction gives the wrong object at every non-prime prime power.

Two constructions, side by side #

It is worth laying the two recipes next to each other, because they are more alike than the difference in outcome suggests.

The integers modulo $n$. Take the integers, which are closed under addition and multiplication, and quotient by the multiples of $n$. Result: a field exactly when $n$ is prime.

Polynomials modulo $f$. Take the polynomials over $GF(p)$, which are closed under addition and multiplication, and quotient by the multiples of $f$. Result: a field exactly when $f$ is irreducible.

The two are the same construction applied to two different systems, and “prime” and “irreducible” are the same word in each. Both systems have division with remainder, both therefore have a Euclidean algorithm, and both therefore have Bézout’s identity — which is what produces the reciprocal in each case.

That parallel is not decoration; it is why the polynomial construction was even attempted. Everything that makes the integers mod $p$ work is a consequence of the integers having a division algorithm and unique factorisation, and polynomials over a field have both. The objects being quotiented are unrecognisably different and the machinery does not notice.

One field per size, and what that means #

A second theorem completes the picture and is more surprising than the first.

For each prime power there is exactly one field of that size, up to renaming. Two people who choose different irreducible polynomials of the same degree build objects that look different — different tables, different labels — and there is always a relabelling carrying one onto the other.

That is why the notation $GF(q)$ names a field by its size alone and nobody has to say which construction was meant. It also means the choice made by the generator on this page, of the first irreducible polynomial found by search, costs nothing: any other choice gives the same field with the entries permuted.

Uniqueness is a stronger statement than it sounds. The integers modulo $n$ are unique for trivial reasons; here there are genuinely many constructions and they genuinely coincide. Over $GF(2)$ there are three irreducible cubics’ worth of ways to build $GF(8)$, and all three give the same field.

The small case that lies #

There is a trap in this subject that the smallest examples set, and it is worth naming because it catches people who have understood everything above.

For $n = 2, 3, 5, 7$ the integers modulo $n$ are the field of that size, so the first four examples anybody meets suggest that finite fields are clock arithmetic. Then $GF(4)$ arrives and the pattern breaks, and it breaks in a way that cannot be repaired by adjusting the modulus.

The same trap operates in the other direction. Because $GF(4)$ is built from polynomials, it is tempting to think its elements are polynomials in some essential way. They are not: the polynomials are a presentation, and the uniqueness theorem says the field does not remember which one was used. The elements of $GF(4)$ are four things with an arithmetic, and every description of them is a coordinate system.

Small cases lying about the general pattern is a recurring hazard in this collection — the first few primes suggesting regularities that fail, the first few rows of a triangle suggesting the wrong rule. Here the lie is unusually well set up, because four consecutive examples support it.

There is a third version of the trap worth flagging, since it is the one that produces wrong code rather than wrong intuition. Arithmetic modulo $2^k$ is what a fixed-width integer does in a computer — a byte is the integers mod $256$ — and it is not $GF(256)$. The two have the same number of elements and different multiplication entirely: $16 \times 16 = 0$ in one and not in the other. Anything relying on division, including every argument in the previous anchor, is wrong in the first and right in the second, and nothing about the sizes gives any warning.

One further consequence of the classification deserves mention here, because it surprises people who arrive from ordinary algebra. In a field of characteristic $p$, adding any element to itself $p$ times gives zero. So in the field with four elements, whose multiplicative structure is a cycle of three and which has characteristic $2$, the identity $(a+b)^2 = a^2 + 2ab + b^2$ becomes

$$(a+b)^2 = a^2 + b^2,$$

because the middle term is $ab$ added to itself and therefore zero. Squaring is additive.

That is not a curiosity; it is one of the most useful facts in the subject. The map $z \mapsto z^p$ is a structure-preserving map of the field to itself — it respects addition by the argument just given and multiplication trivially — and it is the engine behind most of the theory of finite fields, including the reason the multiplicative group turns out to be a single cycle.

It also makes a familiar impossibility disappear. Over the real numbers, $x^2 = -1$ has no solution and adjoining one produces the complex numbers. Over $GF(4)$ every element is already a square, since squaring is an invertible map, and the notion of a square root is uninteresting. Which properties of arithmetic are essential and which are accidents of the reals is exactly what a finite field is good at exposing.

What it is for #

A classification theorem is more convincing when the objects classified are being used for something, and these are used constantly.

The codes of the previous anchor need an alphabet whose arithmetic has no zero divisors, and they need it to be large enough to supply $n$ distinct evaluation points. Both requirements point at $GF(256)$: two hundred and fifty-six elements, so a symbol is a byte, and the arithmetic is the polynomial construction of this page at degree eight over $GF(2)$.

That is not a metaphor for byte arithmetic; it is byte arithmetic, done in hardware. Addition of two bytes is the exclusive-or, which every processor has. Multiplication is a polynomial multiply followed by a reduction modulo a fixed degree-eight polynomial, which is a handful of shifts and exclusive-ors and is a single instruction on modern chips because encryption standards need it.

The same fields carry the arithmetic behind the block cipher standard, the arithmetic behind elliptic-curve cryptography over binary fields, and the arithmetic behind the checksums in storage systems. In each case the property being used is the one this essay is about: division always works, so the algebra has no exceptions to handle.

Where this anchor goes #

The additive structure of a finite field is settled: $k$ independent copies of $GF(p)$, with nothing more to say.

The multiplicative structure is not, and it turns out to be the interesting half. The non-zero elements of $GF(q)$ form a group of order $q-1$ under multiplication, and that group is always a single cycle — every non-zero element is a power of one of them. That is not obvious, it is not true for the integers modulo a composite, and it is what makes multiplication in a finite field into addition of exponents.