A construction of the finite fields (with exercises)
The following is intended as an introduction to finite fields for those with already some familiarity with algebraic constructions. It is based on a talk given at our local seminar.
A finite field is simply a field with a finite number of elements. An example of a finite field that should already be familiar is , the integers modulo a prime , which in the context of field theory is more commonly denoted . But what other finite fields exist? In this post, we’ll construct a finite field of size for any prime and positive integer , and additionally prove that, up to isomorphism, these are all the finite fields.
(Note that another common notation for is – the “GF” stands for “Galois field”).
is a field
Firstly, let’s take a moment to show why is a field. It is clearly is a commutative ring with 1, so it remains to see why every non-zero element has an inverse. We need to find an element such that . The Extended Euclidean Algorithm provides a way to find such a . The algorithm takes two positive integers and returns integer coefficients that linearly combine and to yield their GCD, i.e. such that . Take . Since is prime and is not zero, . The Euclidean algorithm therefore yields and such that , which means . Hence, is the multiplicative inverse of .
This same argument will be recycled below in our construction of extension fields.
The characteristic of a field
The characteristic of a field is the smallest positive integer such that ( times) equals in . In other words, it is the order of the additive group generated by the element .
If is finite, then it is clear that such a must exist. Moreover, must be prime. For supposing that factorized, as say with , it would follow that while at the same time, by minimality of the characteristic, we’d have that neither of the multiplicands , were themselves zero. To arrive at a contradiction, either note that you’ve constructed zero divisors in a field, or instead use that fact that (being non-zero) has an inverse, multiply both sides of by that inverse and note that this would force , a contradiction.
(A similar argument shows that is not a field if is not prime).
If no positive integer exists such that , the characteristic is defined to be zero (this is the case for , for example).
The prime subfield
A subfield of a field is simply a subset which is itself a field (with the same and ). The prime subfield of a field is the subfield generated by and is the smallest subfield contained in . If the characteristic of is a prime number , then the prime subfield is (a copy of) the field . If the characteristic of is zero, then the prime subfield is isomorphic to the field of rational numbers .
Of course, the prime subfield could be the entire field!
Any finite field has size a prime power, and that prime is its characteristic
Let be a finite field of characteristic , and identify with the prime subfield of . Now let’s forget some of the structure of and just consider as a vector space over the field . The vector space axioms are indeed satisfied, since elements of can be added together, and multiplied by scalars (i.e. elements of ) in a way that is distributive and associative – all of this just follows from the field axioms.
Now let be the dimension of as a vector space over . If you chose a basis for , it would have length , and every element of would have a unique expression as a linear combination of the basis with coefficients in . Moreover, every such expression would be an element of . There are such expressions, so .
Example: there is precisely one field with four elements
While we will indeed construct for every prime and , let’s first do the simplest possible example beyond the more familiar fields : let’s “manually” construct a field with four elements. Indeed, we’ll see that there is only one such field, up to isomorphism.
Firstly, note that has characteristic 2 (by the preceding section), and hence has as its prime subfield. So there are only two “new” field elements. Call them , so that . Note that the four elements must all be pairwise non-equal, or the field is too small. Now, try to fill in the multiplication table for this new field, using the fact that the non-zero elements of a field (in our case: ) must form a group under multiplication. This implies that each element can appear at most once in each row and column. You’ll see that there is only one way to do this!
Similarly, try filling in the addition table, this time using the fact that the field is a group under addition, as well as (similarly for ). There is only one possible addition table!
Below, we’ll construct this same finite field (and many others) but in a more sophisticated manner.
Polynomial prerequisites
Polynomial division
Given two polynomials , , we can perform polynomial division to write for some unique such that . Call the quotient and the remainder. This is analogous to the division algorithm for integers.
Roots correspond to linear factors
A polynomial has a root if and only if it is divisible by the linear polynomial . This can be seen using polynomial division: for if is divided by , then the remainder is . Hence, if and only if the remainder is zero, which means is divisible by .
Aside: a finite field is never algebraically closed
While this subsection has no relevance to the construction below, it is too nice to omit! Recall that a field is said to be algebraically closed if every non-constant polynomial has a root in . For example, is algebraically closed, while is not. Now if is a finite field, form the polynomial and notice that for any . Thus can not be algebraically closed.
Irreducible polynomials
An irreducible polynomial over a field is a non-constant polynomial that cannot be factored into the product of two non-constant polynomials over . Irreducibles of degree three or lower are easy to find: any factorization must involve a linear factor, and these can be detected by evaluating the polynomial (as discussed above).
Exercise 1: Verify that, over , the polynomial is the unique quadratic irreducible.
Exercise 2: (Again over ) show that and are the unique cubic irreducibles.
A stepping stone: constructing new fields from old
Let be any field (not necessarily finite) and let an irreducible polynomial of degree . Write for the quotient of the ring by the ideal generated by . Then is itself a ring with . Let be the surjection of rings that comes from the quotient construction, i.e. that maps any polynomial to its coset .
Just as the elements of are enumerated by remainders after integer division by , the elements of can be enumerated by remainders of polynomial division of by : if , then . If is indeed finite, this immediately tell us that , since there are possibilities for each of the coefficients of .
There is moreover an extended Euclidean algorithm for polynomials, and (analogous to our argument for ) this can be used to demonstrate that every non-zero element of has an inverse. For if is such an element, than there exists a with , and we have that is not divisible by , since . Thus, the greatest common divisor of and (which is defined to be the monic polynomial of maximal degree dividing both and ), in view of the irreducibility of , must be . The extended Euclidean algorithm therefore yields polynomials such that , and applying to both sides of this equation shows that , i.e. is the inverse of .
We’ve thus shown that is a field. Indeed, it has as a subfield, and so is a field extension. It is, in fact, quite a special field extension – the polynomial , which was irreducible over , has a root , namely . To see this, first note that is a -linear map. Then:
In summary, given a field and an irreducible of degree , we’ve constructed an extension field of in which has a root!
Note that we’d have achieved our goal of constructing a field with elements if we knew that there was an irreducible polynomial of degree over . But we don’t know this at this stage. Nonetheless, the above construction is the crucial ingredient, as we’ll see below.
Exercise 3: Verify that the complex numbers can be constructed from the real numbers in this way, using the irreducible quadratic . In particular, you should recover the familiar formulae for the real and complex parts of the multiplication of two complex numbers from multiplication in . (For a worked solution, see here).
Exercise 4: Carry out the above construction for and the irreducible , and check that you obtain the field with four elements (which we constructed earlier in manual fashion).
Exercise 5: (continuing the example of the previous exercise) Show that both roots of are obtained ( is one of them, which is the other?). Though we won’t use (or show) this here, it turns out that this is always true if is finite, then will factor completely into linear factors over the extension field . You can cycle through the roots by applying the Frobenius automorphism.
Existence of a splitting field
Suppose is a field (not necessarily finite) and a non-constant polynomial. A splitting field for is a field extending (so ) over which splits as a product of linear factors, and that is minimal with the property, i.e. if with is another such field, then .
We show here that splitting fields exist (a special case of which will be the last ingredient in our construction of the finite fields).
We proceed iteratively. has a unique expression as a product of irreducibles over . If this expression consists only of linear factors, then stop. If not, choose a non-linear (i.e. degree > 1) irreducible factor , and construct the field as above. Considering , we see that has at least one more linear factor than before. Repeat this process, each time replacing by where is one of the remaining non-linear irreducible factors of . Since polynomials have finite degree, this process which terminate with a field over which factors linearly. Now take the smallest subfield over which factors linearly (such a field is uniquely determined, since the intersection of any two subfields with this property will again be a subfield with this property). Then we have constructed a splitting field for .
Construction of a field with elements
Finally! Using the construction of the previous section, let be a splitting field of . So . Now let . It remains to show that is a field and .
To see that is a field, first note that are both roots of , so . Now simply show that is closed under addition, multiplication, and inversion. Only addition is not immediate: for this, you need to use that the binomial coefficients vanish in characteristic whenever (which follows from the definition of the binomial coefficient in terms of factorials, c.f. here). Thus is a field.
Finally, note that is equal to the number of distinct roots of . The polynomial has degree , but perhaps there are repeated roots? There are not. If a root was repeated, then would divide . But if this were the case, then would divide its derivative (this follows immediately from the product rule for differentiation). But direct calculation shows that (in characteristic ), and so can have no repeated roots. Hence , and we have constructed a field with elements!
Extension: these are all the finite fields
In the previous section, we constructed a splitting field for the polynomial and showed that it had elements. But could there be multiple, non-isomorphic fields of size ? There can not, as we see below. We need this uniqueness up to isomorphism in order to be able to sensibly speak of “the field with elements”!
Suppose that is some other field with , so . Then the set of all non-zero elements of is a multiplicative group of size . Thus for any non-zero , we have that , or, put differently, that , i.e. ! Note that this holds also for , so we’ve shown that every element of is a root of . Since , it follows that factors linearly over , and that is a minimal extension of with this property since has no repeated factors (as seen in the previous section). Thus is a splitting field for as well, i.e. all fields of size are splitting fields for .
Splitting fields are unique up to isomorphism in the sense detailed below. This statement is trivial if, as some authors do, you chose to consider only fields inside of a fixed algebraic closure of . If, like me, you would prefer not to do this, you might proceed as follows.