📚 The CoCalc Library - books, templates and other resources

cocalc-examples / paulsen-abstract-algebra / ring13.ipynb

¹³²⁹²² views
License: OTHER

Kernel: SageMath (stable)

Abstract Algebra: An Interactive Approach, 2e

Chapter 13
Finite Division Rings

Initialization: This cell MUST be evaluated first:

In [0]:

%display latex
try:
    load('absalgtext.sage')
except IOError:
    load('/media/sf_sage/absalgtext.sage')

Entering Finite Fields in Sage
Properties of Finite Fields
Cyclotomic Polynomials
Finite Skew Fields
Sage Interactive Problems

Entering Finite Fields in Sage

In this section we will experiment with finite fields using Sage. Although we have seen how integral domains can be entered into Sage, fields have additional properties that allow for shortcuts in this process. In fact, we will find that any finite field can be defined in Sage with only 3 commands.

We have already seen several examples of finite fields. The first example was the discovery that whenever p is prime, the ring Z_p forms a field with p elements. In chapter 3 we found another example of a finite field—the "complex numbers modulo 3." This ring was defined in Sage with the commands

In [0]:

InitDomain(3)
AddFieldVar("i")
Define(i^2, -1)
K = ListField(); K

The multiplication table

In [0]:

MultTable(K)

reveals the fact that this ring is indeed a field of order 9.

EXAMPLE:
Find a connection between the field K and the polynomials in Z₃[x].

We will restart with Z₃, and form a polynomial.

In [0]:

InitDomain(3,"x")
A = (2*x^2 + x + 1)*(2*x + 1); A

Since the variable x was defined with the field definition, we can factor the polynomial A over this field:

In [0]:

factor(A)

This factorization isn't exactly the same as the original product which produced A, but we know from Corollary 12.5 that Z₃[x] is a unique factorization domain. Therefore, these factors must be associates of the original factorization. Can you see which pairs of factors are associates?

EXPERIMENT:
By replacing the polynomial A in the last command with various second degree polynomials, determine all second degree polynomials in Z₃[x] which are irreducible. For simplicity, assume that the coefficient of the x² term is 1, so there will be only 9 polynomials to check. (The polynomials beginning with 2x² will, of course, be associates of the polynomials you find.) Is there one irreducible polynomial that seems to have a relationship with the "complex numbers modulo three"?

We have hinted that the field of complex numbers modulo 3 are related to Z₃[x]. How so? Each element of K can be thought of as evaluating some polynomial in Z₃[x] at x = i. Even though i is not an element of Z₃, we can consider any polynomial in Z₃[x] as being also a polynomial in K[x].

This suggests that we should use the evaluation homomorphism

ϕ_i : K[x] → K.

However, we can restrict this homomorphism to apply only to polynomials in Z₃[x]

ϕ_i′ : Z₃[x] → K.

The image will still be all of K, since ϕ(x) = i. The kernel of this homomorphism will consist of all polynomials in Z₃[x] that yield 0 when evaluated at x = i. For example, x² + 1 is in the kernel, as are all multiples of x² + 1. In fact, if f(x) is an element of the kernel, then gcd(f(x), x² + 1) must be in the kernel, and x² + 1 is irreducible in Z₃[x], as we found in the experiment. Thus, the kernel must be precisely the multiples of x² + 1. This ideal can be described as ⟨x² + 1⟩, the ideal generated by x² + 1.

By the first ring isomorphism theorem (10.2), we now have that

K ≈ Z₃[x]/⟨x² + 1⟩

since the field K is the image of the homomorphism ϕ_i′.

EXAMPLE:
Find a field of order 25.

Recall that we tried to form a field by extending Z₅ by an element i, where i² = −1. However, we failed to produce a field, since the ring had zero divisors. We succeeded in producing the ring

K ≈ Z₅[x]/⟨x² + 1⟩

but x² + 1 factors in Z₅[x]: (x + 2)·(x + 3). This factorization apparently causes the zero divisors to appear in the quotient ring. Perhaps we should try using a polynomial that is irreducible in Z₅[x]. We first define Z₅ in Sage.

In [0]:

InitDomain(5,"x")
Z5 = ListField(); Z5

Next, we find a polynomial that is irreducible in Z₅. There are several to choose from, but let us try the following:

In [0]:

factor(x^2 + 2*x + 3)

This shows that the polynomial x² + 2x + 3 is irreducible in the field Z₅.

EXPERIMENT:
Can you change the 3 in the polynomial to find another number to find a different irreducible polynomial?

Let us see if we can find a field for which x² + 2x + 3 has a root. We will denote denote one of the roots by the letter w. Then it is clear that

w² = −2 w − 3.

Let us define an element w such that w² = −2 w − 3 in Sage.

In [0]:

AddFieldVar("w")
Define(w^2, -2*w - 3)

Sage can now determine other powers of w.

In [0]:

w^3

How did Sage compute this? Note that

w³ = w·w² = w·(−2 w − 3) = −2 w² − 3 w = −2(−2 w − 3) - 3 w = (4 w + 6) − 3 w = w + 6.

This then simplifies to w + 1 in Z₅. In fact, Sage can list the elements in this ring.

In [0]:

H = ListField(); H

The length of this ring is

In [0]:

len(H)

which is still small enough for us to look at a multiplication table.

In [0]:

MultTable(H)

Look carefully. You'll see there are no zero divisors in this ring. So this ring is a field. The fact that Sage was able to construct this ring through the Define command verifies that this is indeed a field.

How would we describe this field? As in the case of Z₃[x]/⟨x² + 1⟩, we can consider every element of H as a polynomial of Z₅[x] for which x was replaced by w. That is, we consider the evaluation homomorphism

ϕ_w : H[x] → H.

However, we can restrict this homomorphism to apply only to polynomials in Z₅[x]:

ϕ_w′ : Z₅[x] → H.

The kernal of this homomorphism is ⟨x² + 2 x + 3⟩, and the image is certainly all of K. So by the first ring isomorphism theorem (10.2), we have

H ≈ Z₅[x]/⟨x² + 2 x + 3⟩.

Thus we have found a way to form fields out of polynomial rings.

PROPOSITION 13.1
Let K be a field, and let f(x) be an irreducible polynomial of K[x]. Then K[x]/⟨f(x)⟩ is a field that contains K as a subfield.

Click here for the proof.

DEFINITION 13.1
The field formed in Proposition 13.1 is called the extension field of K through the irreducible polynomial f(x).

EXAMPLE:
Repeat the process for a third degree polynomial in Z₃[x] that is irreducible.

In [0]:

InitDomain(3,"x")
Z3 = ListField(); Z3

The only way to find such a polynomial is by trial and error. Let us try the following polynomial:

In [0]:

factor(x^3 + x^2 + x + 1)

Unfortunately, this polynomial does reduce in Z₃[x].

EXPERIMENT:
Try changing one or more of the coefficients so that the resulting polynomial is irreducible. Leave the x³ term as it is. There is more than one solution.

Once we have found an irreducible polynomial of degree three, we are ready to define a new field. We will let a be one of the zeros of the polynomial, and we will solve for a³. That is, for the polynomial

x³ + x² + x + 1,

we would let

a³ = −a² − a − 1.

EXPERIMENT:

Determine what a³ would be using your polynomial which you found from the last experiment. Fill in the space with the answer, and execute it to produce a multiplication table, and verification that your ring is a field.

In [0]:

AddFieldVar("a")
Define(a^3,         )
R = ListField()
R

In [0]:

MultTable(R)

Note that since the irreducible polynomial was a cubic, the elements of the field sometimes had to be expressed in terms of a². This is why the basis for this ring was {1, a, a²}. In general, of the degree of the polynomial is d, then the basis of the ring will be

{1, a, a², a³, … a^d−1}.

Thus, in the above example there were 3³ = 27 elements. It is not hard to prove the following generalization.

PROPOSITION 13.2
Let p be a prime number, and let A(x) be an irreducible polynomial in Z_p[x] of degree d. Then the field

K = Z_p[x]/⟨A(x)⟩

has order p^d.

Click here for the proof.

EXPERIMENT:

In the above experiment, you created a field R for which an irreducible polynomial in Z₃ now has a zero. Let us verify that this polynomial factors over the new field. Replace the polynomial in the command below with your polynomial from above, and execute.

In [0]:

factor(x^3 + x^2 + x + 1)

How many zeros does this cubic have over R?

Whenever a finite field is defined by an extension through an irreducible polynomial, the order of the field will be a power of a prime. We would like to show that all finite fields are produced in this way. So naturally we begin by showing that all finite fields have an order that is a power of a prime number.

PROPOSITION 13.3
Suppose K is a finite division ring. Then |K| = pⁿ for some prime p and some integer n.

Click here for the proof.

According to this proposition, it is impossible to find a field of order 6. However, it is still possible to find a field of order 4. Let us see if we can find one. Since a field of order 4 must have characteristic 2, let us begin by loading Z₂.

In [0]:

InitDomain(2,"x")
Z2 = ListField()
Z2

Now let us try to find a second degree irreducible polynomial in Z₂.

In [0]:

factor(x^2 + 1)

This polynomial factored, and in fact, has a double root.

EXPERIMENT:
Change the polynomial x² + 1 in the above statement to find a second degree irreducible polynomial. Once this is found, use a define command to define the element a to be a root of this polynomial. Find the ring generated by a, and display a multiplication table of this ring to verify that it is a field.

As we see from this example, it is fairly easy to enter finite groups into Sage, as long as they can be expressed as an extension field of Z_p through some irreducible polynomial of Z_p[x]. In the next section, we will show that all finite fields can be obtained in this way. In fact, our goal will be to clasify all finite fields.

Properties of Finite Fields

In the last example we starting looking at examples of finite fields. In this section we want to explore the properties that all finite fields have in common. In the process, we will discover that there aren't as many finite fields as one would expect.

We begin by observing that if F is a finite field, that the multiplicative group F must be a finite abelian group. The natural question one would ask is "which abelian group is F?" If the field is of order pⁿ, the group F^* has order pⁿ − 1. From the fundemental theroem on abelian groups, the possible groups of order pⁿ − 1 is limited. Perhaps by experimenting, we can get a clue as to which abelian group of order pⁿ − 1 is produced.

EXPERIMENT:
Reload the field of "complex numbers modulo 3".

In [0]:

InitDomain(3)
AddFieldVar("i")
Define(i^2, -1)
K = ListField()
MultTable(K)

Study the multiplication table, and determine which of the three groups

Z₈, Z₂ × Z₄, or Z₂ × Z₂ × Z₂,

is formed by K^*.

We can find the multiplicative group for some of the other finite fields that we found in the last section very easily. For example, the field of order 4 has a multiplicative group of order 3, so this group must be Z₃.

On the other hand, the field of order 27 must have a group of order 26 as its multiplicative group. By the fundemental theorem of abelian groups, there is only one such group: Z₂₆. So in all of the cases we have explored, the multiplicative group of a finite field turns out to be cyclic. Let us see if we can prove this pattern continues using the fundemental theorem of abelian groups.

PROPOSITION 13.4
If F is a finite field, then the multiplicative group F^* is a cyclic group.

Click here for the proof.

Now that the multiplicative group is completely understood for a finite field, let us turn our attention to the group of automorphisms on the field. We have previously seen examples where the group of automorphisms gave us insight into the structure of a ring, and finite fields are no exception. We begin by proving some basic lemmas in number theory.

LEMMA 13.1
If p is a prime, then n ^p ≡ n (mod p) for all integers n.

Click here for the proof.

The next lemma starts to reveal the automorphism we are looking for.

LEMMA 13.2
If F is a field of characteristic p, then for all g ∈ F, the polynomial

f(x) = (x + g)^p − x^p − g^p

is the zero polynomial in F[x].

Click here for the proof.

We are now ready to produce one automorphism on a finite field, which we will use to generate all other automorphisms.

THEOREM 13.1:The Frobenius Automorphism Theorem
If F is a finite field of characteristic p, then the mapping

ƒ : x → x^p

forms an automorphism of F to itself. Furthermore, ƒ(y) = y if, and only if, y is in the subfield Z_p. This automorphism is called the Frobenious automorphism on F.

Click here for the proof.

We can define the Frobenius automorphism in Sage. Let us begin by defining a field of order 16, using the fourth degree polynomial x⁴ + x³ + 1 in Z₂[x].

In [0]:

InitDomain(2)
AddFieldVar("a")
Define(a^4, -a^3 - 1 )
K = ListField(); K

Since a is the generator of this new field, we only have to tell Sage where this generator is mapped to.

In [0]:

F = FieldHomo()
HomoDef(F, a, a^2)

In [0]:

CheckHomo(F)

In [0]:

F(a)

We can even make a circle graph of this automorphism.

In [0]:

CircleGraph(K, F)

Once we have the one automorphism ƒ(x), we can find more. For example, ƒ(ƒ(x)), ƒ(ƒ(ƒ(x))) are automorphisms. Of course this eventually will produce the identity automorphism, and it is not hard to determine the order of ƒ(x).

COROLLARY 13.1
Let F be a finite field of order pⁿ. Then the Frobenius automorphism is of order n in the group of automorphisms.

Click here for the proof.

EXPERIMENT:

For the Frobenius automorphism ƒ(x) defined above, determine what ƒ(ƒ(a)) is. Then create the automorphism g(x) = ƒ(ƒ(x)) in Sage. Form the circle graph of the new automorphism. Which elements are fixed by g(x)? That is, which elements map to themselves in the automorphism? Show that these elements form a subfield of the field K.

One application that these automorphisms on K have is that they can be applied to polynomials in K. We first need to show some simple lemma to indicate how to apply the Frobenius automorphism to K[x].

LEMMA 13.3
Any isomorphism ƒ that maps an integral domain K to an integral domain M extends to an isomorphism mapping K[x] to M[x], with ƒ sending the polynomial x in K[x] to the polynomial x in M[x].

Click here for the proof.

We can apply Lemma 13.3 to the case where ƒ is an automorphism on K[x], such as the Frobenius automorphism. By extending the Frobenius automorphism to a polynomial, we can generate irreducible polynomials in Z_p[x]. These irreducible polynomials are important, since we can define the field in terms of these polynomials.

PROPOSITION 13.5
Let F be a finite field of characteristic p. For any y in F, let n be the smallest number such that y^pⁿ = y. If ƒ(x) is the Frobenius automorphism, then

g(x) = (x − y)·(x − ƒ(y))·(x − ƒ(ƒ(y)))· ⋯ ·(x − ƒ ⁿ⁻¹(y))

is an irreducable polynomial of degree n in Z_p[x]. Here, ƒ ⁿ⁻¹ means ƒ applied to itself n − 1 times.

Click here for the proof.

The irreducible polynomial generated by this proposition is important enough to warrent a definition.

DEFINITION 13.2

The polynomial produced by Proposition 13.5 is called the irreducible polynomial of y over Z_p. If y is in Z_p, this polynomial is simply x − y.

We can now use Proposition 13.5 to show us that every finite field can be produced as an extention of Z_p over an irreducible polynomial. While we are at it, we will prove a statement that is true for all fields, not just finite fields.

PROPOSITION 13.6
Let K be any field, and F be a subfield of K. Suppose there is an element y of K such that there are no proper subfields of K containing both F and y. Suppose that there is a polynomial f(x) in K[x] with coeffients in F such that f(y) = 0. Suppose further that f(x) is an irreducible polynomial when treated as a polynomial in F[x]. Then K is isomorphic to F[x]/(f(x)).

Click here for the proof.

One immediate application of Proposition 13.6 is to show us that every finite field can be produced as an extention of Z_p over an irreducible polynomial. We will use the polynomial derived in Proposition 13.5.

COROLLARY 13.2
For every finite field K of characteristic p, there is an irreducible polynomial f(x) of Z_p[x] such that K is isomorphic to Z_p[x]/⟨f(x)⟩.

Click here for the proof.

Because every finite field is generated by a single polynomial in Z_p[x], Sage can define any finite field. In fact, Sage is really defining Z_p[x]/⟨f(x)⟩ when we use the Define command, subtracting the two arguments to determine the polynomial. For example, we could have defined the complex numbers mod 3 this way:

In [0]:

InitDomain(3, "x")
AddFieldVar("i")
Define(x^2 + 1, 0)

This way emphasises that we are really defining Z₃[x]/⟨x² + 1⟩. We can now compute i² in our new field:

In [0]:

i^2

We can directly list the elements in the field.

In [0]:

K = ListField(); K

In [0]:

MultTable(K)

In this new field, x² + 1 will factor.

In [0]:

factor(x^2 + 1)

But there are two other irreducible second degree polynomials in Z₃[x], x² + x + 2 and x² + 2x + 2. What if we formed fields using these?

EXPERIMENT:
Do the other two polynomials factor over the field K?

Try defining Z₃[x]/⟨x² + x + 2⟩, using w as the element which satisfies the equation. Do all three polynomials x² + 1, x² + x + 2, and x² + 2x + 2 factor in this field?

What about the field Z₃[x]/⟨x² + 2x + 2⟩?

What does this tell us about the fields Z₃[x]/⟨x² + 1⟩, Z₃[x]/⟨x² + x + 2⟩, and Z₃[x]/⟨x² + 2x + 2⟩? (Hint: See Proposition 13.6.)

For small fields (such as those of order 9), we might not expect to have too many fields of the same order. So let us consider larger finite fields, to see if the same pattern persists.

EXPERIMENT:
Here are two polynomials which are irreducible in Z₃[x]:

x³ + 2x + 1, and

x³ + x² + x + 2

Define the field Z₃[x]/⟨x³ + 2x + 1⟩ in Sage, and see if the second polynomial factors in this field. Likewise, define the field Z₃[x]/⟨x³ + x² + x + 2⟩ in Sage to determine whether the first polynomial factors over this field. What do you obverse? How would you interpret the result?

To understand the significance of having the generator of one field factor completely in another field, let us look at an example where this doesn't happen. Consider two fields of characteristic 2, one of order 4, and the other of order 8. We will use the polynomials x² + x + 1 and x³ + x + 1.

In [0]:

InitDomain(2,"x")
AddFieldVar("a")
Define(x^2 + x + 1,0)
K = ListField(); K

In [0]:

factor(x^2 + x + 1)

In [0]:

factor(x^3 + x + 1)

This time, one of the polynomials factor, while the other did not. Let's try the other field.

In [0]:

InitDomain(2,"x")
AddFieldVar("b")
Define(x^3 + x + 1,0)
F = ListField(); F

Let us see whether x³ + x + 1 factors in K, or whether x² + x + 1 factors in F.

In [0]:

factor(x^3 + x + 1)

In [0]:

factor(x^2 + x + 1)

Thus, we see that the polynomial which defines K is irreducible in F, and vice versa. Hence, the element a cannot be expressed in terms of b, so the fields K and F are totally different.

Can we find a field containing both K and F at the same time? The natural choice would be to define both a and b using their respective polynomials.

In [0]:

InitDomain(2)
AddFieldVar("a")
Define(a^2 + a + 1, 0)

In [0]:

AddFieldVar("b")
Define(b^3 + b + 1, 0)

In [0]:

L = ListField(); L

How many elements are there in this long list? We can have Sage count them for us.

In [0]:

len(L)

It is easy to find subfields which are isomorphic to both K and F in this field.

In [0]:

Ring(a)

In [0]:

Ring(b)

Can we find a basis? Simply combining the basis for K and F, giving {1, a, b, b²} will not be enough, since there are 64 = 2⁶ elements in L, so we need 6 elements for the basis.

EXPERIMENT:
By examining the elements of L, can you find two more elements that need to be in the basis?

It should be noted that this is an extremely inefficient way of defining this finite field, since Corollary 13.2 guarantees that this field can be defined using a single generator, and a single polynomial (which would be sixth degree). In the next chapter, we will deal with a similar chain of infinite fields.

In general, we will be able to find a large field containing two different finite fields, provided that the characteristic of the two fields are the same.

LEMMA 13.4
Let F and K be two finite fields with the same characteristic p. Then there is a field that contains isomorphic copies of both F and K.

Click here for the proof.

We can now use this lemma to show that there is only one non-isomorphic field of a given order.

COROLLARY 13.3
Any two finite fields of the same order are isomorphic to each other.

Click here for the proof.

This proposition explains the strange behavior of fields that we discovered in our experiment. Whenever a finite field F is extended though an irreducible polynomial, all irreducible polynomials in F[x] of the same degree factor completely in the new field. The reason is now clear: the field

F[x]/⟨f(x)⟩

only depends on the degree of the irreducible polynomial f(x).

We have already seen fields of order 4, 9, and 27 in this chapter. We in fact can refer to them as the fields of order 4, 9, or 27. However, there is one question we have yet to answer. Given a prime number p and an integer n, is there a field of order pⁿ? It seems like all we would need to construct such a field is an irreducible polynomial f(x) in Z_p[x] of degree n, and then the field

Z_p[x]/⟨f(x)⟩

would have order pⁿ. The only problem with this argument is that we have not shown that there is an irreducible polynomial of degree n in Z_p[x]. In order to construct such irreducible polynomials, we will need to utilize a special class of polynomials—the cyclotomial polynomials. These polynomials have many different uses not only in this chapter, but also later on as we study Galois theory.

The Cyclotomic Polynomials

We now pause from our work on finite fields to discuss a special class of polynomials in ℤ[x]. These polynomials occur in the factorizations of the simple polynomial xⁿ − 1. Although these polynomials are constructed easily, they have a tendency to appear in many differnt applications.

To introduce the cyclotomic polynomials, we will begin by noticing a pattern in the following factorizations:

In [0]:

var("x")
factor(x - 1)

In [0]:

factor(x^2 - 1)

In [0]:

factor(x^3 - 1)

In [0]:

factor(x^4 - 1)

EXPERIMENT:
Continue this pattern using Sage to factor the polynomials up to x¹⁰ − 1. Notice that each time there is exactly one new polynomial appearing in the factorization that has not appeared in any previous factorization.

Our plan is to find a formula for the irreducible polynomials produced in these factorizations. A natural starting place would be to find all of the complex roots of the polynomial xⁿ − 1. But we have already seen that the primitive n^th roots of unity are of the form ω_n^k, where k is coprime to n.

How are the primitive roots of unity related to the factorizations of xⁿ − 1? It is clear that the primitive roots are precisely the complex zeros of xⁿ − 1 that are not zeros of x^m − 1 for m < n. Thus, if we wish to find the factor of xⁿ − 1 that does not appear in any previous factorizations, we should look for a polynomial whose only complex roots are the primitive n^th roots of unity.

EXAMPLE:
Find a factor of x⁸ − 1 that does not appear in any previous factorizations of xⁿ − 1.

The primitive eighth roots of unity were found to be ω₈, ω₈³, ω₈⁵ and ω₈⁷. Thus, the simpliest polynomial that has these four complex roots would be

In [0]:

w8 = (1 + I)/sqrt(2); w8

In [0]:

(x - w8)*(x - w8^3)*(x - w8^5)*(x - w8^7)

In [0]:

expand(_)

Lo and behold, this simplified into a polynomial with integer coefficients. Apparently not only did the imaginary part cancel, but also the square roots simplified. What's more, this is precisely the new irreducible factor of

In [0]:

factor(x^8 - 1)

so we have found the factor we were looking for.

EXPERIMENT:
You have already found the primitive twelvth roots of unity. Using the above example as a model, find the simpliest polynomial with the primitive twelvth roots as the complex zeros.

Compare this to the factorization of x¹² − 1:

In [0]:

factor(x^12 - 1)

What do you discover?

Let us use these examples as a model for our definition.

DEFINITION 13.3
For n > 0, we define the n^th cyclotomic polynomial to be the product

Φ_n(x) = (x − ω_n^k¹)·(x − ω_n^k²)·(x − ω_n^k³) ⋯ (x − ω_n^kⁱ),

where k₁, k₂, k₃, … k_i are the integers between 0 and n that are coprime to n.

It is sometimes convenient to use a special notation for a product of many terms. Just as the sigma Σ can be used to denote the sum of many terms, a large Π (the upper case π) is used to denote such a product. Thus, we could write

	n
Φ_n(x) =	∏	(x − ω_n^k).
	k = 1
gcd(k, n) = 1

In this product, the index k ranges from 1 to n, but we only consider the values of k for which gcd(k, n) = 1. It is apparent from the definition that the degree of the n^th cyclotomic polynomial is ϕ(n), where ϕ is Euler's totient function.

Although this definition uses complex numbers, we observed that the polynomials always produced integer coefficients. The next proposition shows us how to find the cyclotomic polynomials without having to work with complex numbers.

PROPOSITION 13.7
For any positive integer n, we have

xⁿ − 1 =	∏	Φ_k(x).
	k \| n

Here, the product is taken over all values of k that divide n.

Click here for the proof.

To help understand this notation, let us look at the case where n = 12. Then Proposition 13.7 states that

x¹² − 1 =	∏	Φ_k(x) = Φ₁(x)·Φ₂(x)·Φ₃(x)·Φ₄(x)·Φ₆(x)·Φ₁₂(x).
	k \| 12

This can be seen in the factorization of x¹² − 1:

In [0]:

var("x")
factor(x^12 - 1)

Proposition 13.7 at least explains our observation that the factorization of xⁿ − 1 always produces a new factor. However, we have not proven that the cyclotomic polynomials are irreducible in ℤ[x]. We have to begin by showing that Φ_n(x) is indeed in ℤ[x].

COROLLARY 13.4
The n^th cyclotomic polynomial Φ_n(x) has integer coefficients for all n > 0.

Click here for the proof.

It is actually very easy to generate the n^th cyclotomic polynomial in Sage. The commands

In [0]:

Cyclotomic(3,"x")

In [0]:

Cyclotomic(6,"x")

find the third and sixth cyclotomic polynomial. It is easy to see experimentally that Corollary 13.4 is true. In fact, is seems as though all coefficient of the cyclotomic polynomial are either 0 or ±1.

EXPERIMENT:
Use Sage to find many different cyclotomic polynomials. Are all of the coefficients 0 or ±1? (Hint: Start your search at around n = 100.)

The next corollary is another easy consequence of Corollary 13.4.

COROLLARY 13.5
If n is divisible by m, with n > m, then the polynomial xⁿ − 1 is divisible by x^m − 1 in ℤ[x]. Furthermore, Φ_n(x) divides

xⁿ − 1

x^m − 1

in ℤ[x].

Click here for the proof.

We now want to find some properties of the cyclotomic polynomials. One of the most important properties is that two different cyclotomic polynomials cannot share a root in the complex numbers. (This is obvious from the definition.) However, we will be working with other fields besides the complex numbers, so we could ask whether a cyclotomic polynomial has a multiple root in any field.

We begin by defining a multiple root of a polynomial.

DEFINITION 13.4
If r is a root of a polynomial f(x), and (x − r)² divides f(x), we say r is a multiple root of f(x).

We would like to determine when xⁿ − 1 has multiple roots. Our strategy is to discover the form of the quotient

xⁿ − 1	.
x − 1

We can use Sage to help us find a pattern. For example, ⁽^x^⁴−1)⁄₍_x₋₁₎ is given by

In [0]:

var("x")

In [0]:

Together((x^4 - 1)/(x - 1))

Here is another example:

In [0]:

Together((x^5 - 1)/(x - 1))

A pattern is starting to form. Can you find it?

EXPERIMENT:
Use Sage to simplify ⁽^x^{⁷ − 1)}⁄₍_x₋₁₎ and ⁽^x^{¹² − 1)}⁄₍_x₋₁₎. Is the pattern becoming clear?

We can use the pattern of these quotients to prove the following:

LEMMA 13.5
If F is any field, then the polynomial xⁿ − 1 has a multiple root if, and only if, n is a multiple of the characteristic of F.

Click here for the proof.

We are finally ready to show the irreducibility of Φ_n(x).

THEOREM 13.2: Gauss' Theorem on Cyclotomic Polynomials
For all n > 0, Φ_n(x) is an irreducible polynomial in ℤ[x].

Click here for the proof.

Lemma 13.5 can also be used to generate irreducible polynomials in Z_p[x] of any degree. In fact, these irreducible polynomials are the key to proving that a field of order pⁿ exists.

PROPOSITION 13.8
Let p be a prime integer, and let n > 1. Consider the cyclotomic polynomial Φ_(pₙ₋₁₎(x) of order ϕ(pⁿ − 1). Let us consider g(x) to be this polynomial modulo p in Z_p[x]. Then g(x) factors in Z_p[x] into irreducible polynomials, all of which have degree n.

Click here for the proof.

We can now prove what we had suspected was true from the experiments: that there is precisely one field of order pⁿ, where n > 0 and p is a prime number.

COROLLARY 13.6
If p is a prime number, and n is a positive integer, there exists a unique field (up to isomorphism) of order pⁿ.

Click here for the proof.

DEFINITION 13.5
If q = pⁿ, where p is prime and n > 0, then the Galois field of order q, denoted GF(q), is the unique field given in Corollary 13.6.

For example, the official name for the "complex numbers modulo 3" we have been working with is GF(9). Whenever p is prime, we can write GF(p) for the field Z_p.

When we first defined GF(9), we used the irreducible polynomial x² + 1 in Z₃[x] to make the definition. But there are two other second degree irreducible polynomials with a leading coefficient of 1 in Z₃[x], namely, x² + x + 2 and x² + 2 x + 2. We could have used either of these to define GF(9):

In [0]:

InitDomain(3)
AddFieldVar("a")
Define(a^2, - a - 2)
K = ListField(); K

In [0]:

MultTable(K)

In [0]:

InitDomain(3)
AddFieldVar("b")
Define(b^2, - 2*b - 2)
F = ListField(); F

In [0]:

MultTable(F)

We know from Corollary 13.3 that these are both isomorphic to GF(9), but the notations for these are vastly different. This begs the question as to whether there is an official way to describe the elements of GF(pⁿ).

It is clear that we must first pick an irreducible polynomial f(x) of degree n over Z_p[x], and then we let a = x + ⟨f(x)⟩ be a root of this polynomial in Z_p[x]/⟨f(x)⟩. This will allow every element of GF(pⁿ) to be expressible in terms of a.

But we also know from Proposition 13.4 that the group GF(pⁿ)^* is a cyclic group, and so we can choose the polynomial f(x) so that a will be a generator of this group.

DEFINITION 13.6
The Conway polynomial of degree n over Z_p is the polynomial of degree n in Z_p[x] with the following characteristics:

1) Primitive:
The polynomial f(x) is irreducible, has a leading coefficient of 1, and x + ⟨f(x)⟩ is a multiplicative generator of the finite field Z_p[x]/⟨f(x)⟩.
Such polynomials are called primitive polynomials.

2) Compatibility:
The polynomial is compatible with the way that the subfields of GF(pⁿ) are defined. To be compatible, for all divisors d of n less than n, the

pⁿ − 1	th
p^d − 1

power of the zeros of the polynomial must be zeros of the Conway polynomial of degree d over Z_p.

3) Tie breaker:
If two or more primitive polynomials satisfy the compatibility condition, let m be the highest power of x for which the coefficients differ. If n − m is even, pick the one with the smallest coeffient from the set {0, 1, … p − 1}. If n − m is odd, pick the largest, unless there is one with a coefficient of 0.

This definition at first seems counter-intuitive. Logically, a zero coefficient is always preferred over a nonzero term, but sometimes we pick the polynomial with the largest coefficient, and sometimes use the one with the smallest.

But to understand why this is so, consider the first degree Conway polynomials. Since all of the primitive polynomials are of the form x + c, with c ≠ 0, they differ only in the constant term. Hence m = 0, so n − m will be odd, and we should select the primitive polynomial with the largest c. This in turn will make the root of this polynomial be as small as possible. So for p prime, the root of the Conway polynomial of degree 1 will represent the smallest generator of the group Z_p^*. In general, the Conway polynomial is designed so that the roots will be minimized.

EXAMPLE:
Let us use this definition to find the Conway polynomial of degree 2 over Z₃.

There are three irreducible polynomials of degree 2 in Z₃[x] with a leading coefficient of 1: x² + 1, x² + x + 2, and x² + 2 x + 2. The roots of x² + 1 in Z₃[x]/⟨x² + 1⟩ have order 4, not 8. Since the multiplicative group is isomorphic to Z₈, which has 4 generators, we know that there will be 2 primitive polynomials. So x² + x + 2 and x² + 2 x + 2 pass the first test.

In order to understand the compatibility condition, we must first find the Conway polynomial of degree 1 over Z₃. Since there is only one multiplicative generator of Z₃, namely 2, there is only one primitive polynomial of degree 1,

x − 2 = x + 1.

In [0]:

ConwayPolynomial(3, 1)

Now in order for a primitive polynomial of degree 2 to be compatible, the ^{(3² − 1)}⁄₍₃₁_{− 1)}, or 4^th power of the roots must be a root of x + 1. Hence, x² + 1 does not satisfy this compatibility condition since i⁴ = 1, not 2 in GF(9). However, both x² + x + 2 and x² + 2 x + 2 will satisfy the compatibility condition, since both of the above multiplication tables show that a⁴ = 2. (If one root satisfies the compatibility condition, it is clear that the other root will too, since the Frobenius automorphism sends one root to the other.)

Of the two possible primitive polynomials remaining, we look for the largest power of x for which these differ, x¹, and since n − m = 1 is odd, and neither x¹ coefficient is 0, we pick the larger of the two possible coefficients. So the Conway polynomial is x² + 2 x + 2. We can use Sage to verify this.

In [0]:

ConwayPolynomial(3, 2)

Hence, the official notation for GF(9) is

In [0]:

InitDomain(3)
AddFieldVar("a")
Define(a^2 + 2*a + 2, 0)
F = ListField(); F

In [0]:

a^2

Note: Sage has a shortcut method for the above definition:

In [0]:

F.<a> = GF(9)

In [0]:

a^2

EXAMPLE:
Let us find the Conway polynomial of degree 4 over Z₃.

We can find all of the primitive polynomials of degree n = 4 by factoring Φ₍_pₙ₋₁₎(x) in Z₃[x]. (See Problem 15.)

In [0]:

G = Cyclotomic(80,"x"); G

In [0]:

InitDomain(3, "x")
factor(x^32 - x^24 + x^16 - x^8 + 1)

So we have 8 primitive polynomials of degree 4 over Z₃, each having n = 4 roots which are generators of GF(81). But we need the compatibity condition to be satisfied. That is, for a root r in one of these polynomials, we need the ^{(3⁴ − 1)}⁄₍₃₁_{− 1)} = 40^th power of r to satisfy x + 1 = 0, while the ^{(3⁴ − 1)}⁄₍₃₂_{− 1)} = 10^th power of r must satisfy x² + 2 x + 2 = 0. In other words, r will satisfy r⁴⁰ + 1 = 0, and r²⁰ + 2 r¹⁰ + 2 = 0.

In [0]:

factor(x^40 + 1)

In [0]:

factor(x^20 + 2*x^10 + 2)

Four polynomals are in common with all three factorizations, so these four pass the compatibility test:

x⁴ + x³ + 2, x⁴ + x³ + 2 x² + 2 x + 2, x⁴ + 2 x³ + 2, and x⁴ + 2 x³ + 2 x² + x + 2.

Since they differ in the x³ power, and none of them are missing the x³ term, we pick one with the largest coefficient. (Again, n − m = 4 − 3 is odd.) Of the 2, we pick the one with the smallest x² coefficient (n − m = 4 − 2 is even), giving us x⁴ + 2 x³ + 2. We can verify this with the ConwayPolynomial command:

In [0]:

ConwayPolynomial(3, 4)

This means we can have the official definition of GF(81) as

In [0]:

InitDomain(3)
AddFieldVar("a")
Define(a^4 + 2*a^3 + 2, 0)
F = ListField(); F

In [0]:

len(_)

The Galois fields have many applications. A code very simular to the RSA code studied in chapter 3 was developed using Galois fields of characteristic 2. For a long time the field of order 2¹²⁷ was used, since the multiplicative group is of order 2¹²⁷ − 1, which happens to be prime. (Primes of this form are called Mersenne primes.) This code had the advantage that the key was much shorter than the RSA key, and multiplication in this field could be quickly implimented in binary hardware. However, due to the special properties of finite fields, this code was recently cracked. In order to ensure safety of the encription, the size of the field had to be upped to order 2²²⁰³, which diminished the advantage over the RSA code.

But there is another type of code based on Galois fields, called the Reed-Solomon code, which is not used for security but rather for the storage or transfer of digital data. All digital information, such as the storage of a file in a computer or a song on a compact disk, is stored as a string of "bits" that are either 0 or 1. We will let K denote a finite field of characteristic 2. For example, if K = GF(256), then each element of K would correspond to a computer "byte." (Each byte is eight bits.) A string of n bytes (a₀, a₁, a₂, a₃, … a_n₋₁) is encoded as a polynomial in K:

f(x) = a₀ + a₁ x + a₂ x² + a₃ x³ + ⋯ + a_n−1 xⁿ⁻¹.

The encription of this list of elements is simply the evaluation of this polynomial at the 256 elements of K. That is, if g is a generator of the multiplicative group K^*, then

f(0), f(g), f(g²), f(g³), … f(g²⁵⁵)

is transmitted in place of the numbers a₀, a₁, a₂, a₃, … a_n−1. We know from Corollary 12.3 that we can derive the original list of elements from any n of the numbers transmitted. Thus, if there are some errors in the transmition, the original list can still be reconstructed. Using combinatorial reasoning, Reed and Solomon showed that as many as (255 − n)/2 errors could occur, and yet the original list of elements can be decoded.

For example, if n = 251, then every 251 bytes is converted to a 250 degree polynomial, which is evaluated at the 256 elements of K. Even if two of these bytes are transmitted incorrectly, the 251 original bytes can be correctly reconstructed. This is an example of what is called an error-correcting code. This code was used by the Voyager II spacecraft to transmit pictures of Uranus and Neptune back to Earth. A version of this code (using a larger field K) is used to store the digital music on a compact disk. Current CD players can cope with errors as long as 4000 consicutive bits on the CD, typically caused by a scratch on the CD surface. The Reed-Solomon code will also allow over 500 channels of digital television in the near future.

The ironic part of this code is that, when Reed and Solomon first discovered the code in 1960, it was described as "interesting, but probably not practical." It wasn't until hardware technology advanced to the point that the code could be implimented before the real value of this code was evident. As with most mathematics, the usefulness of a particular result is not seen until long after the result is published.

One final application of finite fields arises from the study of simple groups. Almost all of the simple groups besides the alternating groups are defined in terms of finite fields. For example, the simple group Aut(Z₂₄^*) can be expressed as the 3 by 3 matrices in the field Z₂ with determinant 1. This example can be generized a group G of m by m matrices over any finite field of order pⁿ. When pⁿ > 2, there may be a nontrivial center Z formed by diagonal matrices. However, we can form the quotient group G/Z. The group generated will be simple if m > 2, or if m = 2 and pⁿ > 3.

There are several other ways of forming simple groups using finite fields. In fact, besides the alternating groups, there are only 26 finite simple groups that are not expressed using finite fields. Thus, finite fields are of key importanance in the classification of all finite simple groups.

Finite Skew Fields

Since we have completely classified all finite fields, a natural question is whether we can classify all finite skew fields, and whether these can be easily entered into Sage. At first this seems like it would be a harder problem, since there are many non-abelian groups, and many non-communitive rings. However, a surprising result is that there are no finite skew fields. In other words, any finite division ring must be commutative. In this section we will prove this remarkable result, known as Wedderburn's theorem.

We begin by carrying over some ideas from group theory. One of the ways we studied non-abelian groups was to find the center of the group, since this was always a normal subgroup. We can ask whether the set of elements of a skew field that commute with all of the elements forms a special set.

DEFINITION 13.7
Let K be a skew field. Then the set of all elements x of K such that

x·y = y·x for all y ∈ K

is called the center of K.

Let us look at an example. The only skew field we have seen is the ring of quaternions, ℍ. The Sage command

In [0]:

InitQuaternions()

allows us to experiment with this skew field. What is the center of this skew field? To answer this question, let us first define two typical elements in ℍ.

In [0]:

var("u0 u1 u2 u3 v0 v1 v2 v3")

In [0]:

A = u0 + u1*i + u2*j + u3*k; A

In [0]:

B = v0 + v1*i + v2*j + v3*k; B

These will commute as long as A·B = B·A, or equivalently, A·B − B·A = 0. Let us compute this in Sage:

In [0]:

D = A*B - B*A; D

The normal expand function does not work on quaternions, so we can use Together instead.

In [0]:

Together(D)

EXPERIMENT:

Can you find a relationship between A·B − B·A and the three dimensional vectors u = ⟨u₁, u₂, u₃⟩ and v = ⟨v₁, v₂, v₃⟩. For what values of u0, u1, u2, and u3 does A·B − B·A = 0 for all possible values of B? (Hint: which variables are missing in A·B − B·A?)

It is fairly clear from this experiment that the center of ℍ is the set of quaternions for which u₁ = u₂ = u₃ = 0. Thus, the center is basically the field of real numbers. We can easily prove that the center of a skew field will always form a field.

LEMMA 13.6
The center of a skew field forms a field.

Click here for the proof.

Another concept from group theory that carries over into the study of fields is the normalizer. Recall the definition of a normalizer of a subset S of a group G. We defined

N_G(S) = { g ∈ G | g·S·g^-1 = S }.

We would like to apply the normalizer to the multiplicative group of a field. In particular, we would like to consider the normalizer of a particular element, that is, when S = {y}.

Let us find the normalizer of the element i in the nonzero quaternions. This consists of all elements A such that A·i·A^-1 = i. We can use Sage to help us find this set.

EXPERIMENT:
By examining the result of the computation

In [0]:

A*i*A^-1 - i

In [0]:

Together(_)

determine the values of u0, u1, u2, and u3 that allow this to be 0. (Hint: when does the i componient equal zero?) This gives us the set N_ℍ⁎({i}). Next replace both i's with j's to find the set N_ℍ⁎({j}).

We see from this experiment that the normalizer does not quite form a field, since it does not include the zero element. Yet if we added the zero element to N_ℍ⁎({i}) or N_ℍ⁎({j}), we got a field which was equivalent to the complex numbers. In fact, whenever y is not real, N_ℍ⁎({y}) ∪ {0} yields a copy of the complex numbers. Hence, there are actually an infinite number of complex number planes within the field of quaternions.

It is not hard to show that for any skew field, whenever we add the zero element to the normalizer, we will either get a field or a skew field.

LEMMA 13.7
Let K be a skew field, and let k be an element of K. Then if we let

Y_k = {0} ∪ N_K⁎({k}),

then Y_k is a division ring containing the center of K.

Click here for the proof.

We now can apply the center and normalizer to finite division rings. We first need a lemma that will help us out regarding the divisibility of the orders of finite fields.

LEMMA 13.8
Let y, n, and m be positive integers, with y > 1. Then

yⁿ − 1

y^m − 1

is an integer if, and only if, n is divisible by m. Furthermore, if n is divisible by m, with n > m, then

yⁿ − 1

y^m − 1

is divisible by the number Φ_n(y).

Click here for the proof.

This lemma reveals the possible orders of division rings within a finite division ring.

COROLLARY 13.7
Let K be a finite division ring of order pⁿ, and let F be a subring that is a division ring of order p^m. Then n is a multiple of m.

Click here for the proof.

Note that this corollary has applications in finite fields. For example, it shows that the field of order 16 cannot have a subfield of order 8.

There is one more tool that we need from group theory, which stems from the normalizer. We discovered in §7.4 that the class equation was a powerful tool in analyzing groups. In fact, all three Sylow theorems hinge on the class equation. So let us observe how this useful tool applies to skew fields. Recall that the class equation theorem (7.2) stated that when G is a finite group, then

\|G\| =	∑	\| G \|	,
		\| N_G({g}) \|
	g

where the sum runs over one g from each conjugacy class.

If K is a finite skew field, we can apply the class equation theorem to the multiplicative group K^*, and find that

\|K^*\| =	∑	\| K* \|	.
		\| N_K⁎({k}) \|
	k

We can make the obvious substitutions |K^*| = |K| − 1, and | N_K⁎({k}) | = |Y_k| − 1. The equation now looks like

\|K\| − 1=	∑	\|K\| − 1	,
		\|Y_k\| − 1
	k

where the sum runs from one k from each conjugacy class of K^*.

We are almost ready to use the class equation to prove that finite skew field cannot exist. But first we need to prove a simple inequality about the evaluation of a cyclotomic polynomial at a positive integer.

LEMMA 13.9
If n > 1, then the cyclotomic polynomial evaluated at y ≥ 2, Φ_n(y), is greater than y − 1.

Click here for the proof.

The final step is to use Lemma 13.9 to prove a contradiction in the class equation for finite skew fields.

THEOREM 13.3: Wedderburn's Theorem
There are no finite skew fields.

Click here for the proof.

In a sence, the non-existance of finite skew fields is sad, since there would be plenty of applications for skew fields in crytography and group theory if they had existed. On the other hand, this result, when combined with the classification of all finite fields, means that we have found all finite division rings.

Proofs:

Proof of Proposition 13.1:

Since K is a field, by Corollary 12.7 K[x] is a principal ideal domain. Since f(x) is an irreducible element of K[x], we have by Lemma 12.6 that the quotient H = K[x]/⟨f(x)⟩ is a field.

Finally, we need to show that the field H contains K as a subfield. Consider the mapping

ϕ : K → H

given by

ϕ(y) = y + ⟨f(x)⟩.

This is certainly a homomorphism, since it is a restriction of the natural homomorphism from K[x] to K[x]/⟨f(x)⟩. The kernel of ϕ is just {0}, so the image is isomorphic to K. Thus, K[x]/⟨f(x)⟩ contains K as a subfield.

	⎛	∞		⎞		∞
ƒ(w(x)) = ƒ	⎜	∑	a_i xⁱ	⎟	=	∑	ƒ(a_i) xⁱ.
	⎜			⎟
	⎜			⎟
	⎝	i=0		⎠		i=0

	⎛	∞		⎞		∞		∞		∞
ƒ(w(x) + v(x)) = ƒ	⎜	∑	(a_i + b_i) xⁱ	⎟	=	∑	ƒ(a_i + b_i) xⁱ =	∑	ƒ(a_i) xⁱ +	∑	ƒ(b_i) xⁱ = ƒ(w(x)) + ƒ(v(x)).
	⎜			⎟
	⎜			⎟
	⎝	i=0		⎠		i=0		i=0		i=0

	n − 1
f(x) =	∑	x^k = 1 + x + x² + x³ + ⋯ + xⁿ⁻² + xⁿ⁻¹.
	k = 0

	n − 1
f(1) =	∑	1^k = 1⁰ + 1¹ + 1² + 1³ + ⋯ + 1ⁿ⁻² + 1ⁿ⁻¹ = n.
	k = 0

(x·r)ⁿ − 1	=	xⁿ·rⁿ − 1	=	xⁿ − 1
(x·r − r)²	=	(x − 1)²·r²	=	(x − 1)²·r²

yⁿ − 1	= y^p·	y^m·k − 1	+	y^p − 1	,

y^m − 1		y^m − 1		y^m − 1

	n			n
\|Φ_n(y)\| =	∏	\|y − ω_n^k\|	>	∏	(y − 1) ≥ y − 1.
	k = 1			k = 1
gcd(k, n) = 1			gcd(k, n) = 1;

j(x) =	x^{(pⁿ −1)} − 1

	x^{(pⁱ −1)} − 1

Entering Finite Fields in Sage

Properties of Finite Fields

The Cyclotomic Polynomials

Finite Skew Fields

Proofs:

Sage Interactive Problems