Skip to main content
Logo image

Applied Discrete Structures

Al Doerr, Ken Levasseur

Section 16.4 Field Extensions

From high school algebra we realize that to solve a polynomial equation means to find its roots (or, equivalently, to find the zeros of the polynomials). From Example 16.3.16 and Example 16.3.19 we know that the zeros may not lie in the given ground field. Hence, to solve a polynomial really involves two steps: first, find the zeros, and second, find the field in which the zeros lie. For economy’s sake we would like this field to be the smallest field that contains all the zeros of the given polynomial. To illustrate this concept, let us reconsider the examples from the previous section..
Let \(f(x)=x^2 - 2 \in \mathbb{Q}[x]\text{.}\) It is important to remember that we are considering \(x^2-2\) over \(\mathbb{Q}\text{,}\) no other field. We would like to find all zeros of \(f(x)\) and the smallest field, call it \(S\) for now, that contains them. The zeros are \(x= \pm \sqrt{2}\text{,}\) neither of which is an element of \(\mathbb{Q}\text{.}\) The set \(S\) we are looking for must satisfy the conditions:
  1. \(S\) must be a field.
  2. \(S\) must contain \(\mathbb{Q}\) as a subfield,
  3. \(S\) must contain all zeros of \(f(x)=x^2 - 2\)
By the last condition \(\sqrt{2}\) must be an element of \(S\text{,}\) and, if \(S\) is to be a field, the sum, product, difference, and quotient of elements in \(S\) must be in \(S\text{.}\) So operations involving this number, such as \(\sqrt{2}\text{,}\) \(\left(\sqrt{2}\right)^2\text{,}\) \(\left(\sqrt{2}\right)^3\text{,}\) \(\sqrt{2}+\sqrt{2}\text{,}\) \(\sqrt{2}-\sqrt{2}\text{,}\) and \(\frac{1}{\sqrt{2}}\) must all be elements of \(S\text{.}\) Further, since \(S\) contains \(\mathbb{Q}\) as a subset, any element of \(\mathbb{Q}\) combined with \(\sqrt{2}\) under any field operation must be an element of \(S\text{.}\) Hence, every element of the form \(a + b \sqrt{2}\text{,}\) where \(a\) and \(b\) can be any elements in \(\mathbb{Q}\text{,}\) is an element of \(S\text{.}\) We leave to the reader to show that \(S =\{a + b \sqrt{2} \mid a, b \in \mathbb{Q}\}\) is a field (see Exercise 1 of this section). We note that the second zero of \(x^2 - 2\text{,}\) namely \(-\sqrt{2}\text{,}\) is an element of this set. To see this, simply take \(a = 0\) and \(b = -1\text{.}\) The field \(S\) is frequently denoted as \(\mathbb{Q}\left(\sqrt{2}\right)\text{,}\) and it is referred to as an extension field of \(\mathbb{Q}\text{.}\) Note that the polynomial \(x^2-2=\left(x-\sqrt{2}\right)\left(x+\sqrt{2}\right)\) factors into linear factors, or splits, in \(\mathbb{Q}\left(\sqrt{2}\right)[x]\text{;}\) that is, all coefficients of both factors are elements of the field \(\mathbb{Q}\left(\sqrt{2}\right)\text{.}\)
Consider the polynomial \(g(x) = x^2 + x + 1 \in \mathbb{Z}_2[x]\text{.}\) Let’s repeat the steps from the previous example to factor \(g(x)\text{.}\) First, \(g(0) = 1\) and \(g(1) = 1\text{,}\) so none of the elements of \(\mathbb{Z}_2\) are zeros of \(g(x)\text{.}\) Hence, the zeros of \(g(x)\) must lie in an extension field of \(\mathbb{Z}_2\text{.}\) By Theorem 16.3.15, \(g(x) = x^2 + x + 1\) can have at most two zeros. Let \(a\) be a zero of \(g(x)\text{.}\) Then the extension field \(S\) of \(\mathbb{Z}_2\) must contain, besides \(a\text{,}\) \(a \cdot a = a^2\text{,}\) \(a^3\text{,}\) \(a + a\text{,}\) \(a+1\text{,}\) and so on. But, since \(g(a) = 0\text{,}\) we have \(a^2 + a + 1 = 0\text{,}\) or equivalently, \(a^2= -(a+1)=a+1\) (remember, we are working in an extension of \(\mathbb{Z}_2\)). We can use this recurrence relation to reduce powers of \(a\text{.}\) So far our extension field, \(S\text{,}\) of \(\mathbb{Z}_2\) must contain the set \(\{0, 1, a, a + 1\}\text{,}\) and we claim that this the complete extension. For \(S\) to be a field, all possible sums, products, and differences of elements in \(S\) must be in \(S\text{.}\) Let’s try a few: \(a + a = a\left(1 +_2 1\right)=a\cdot 0=0\in S\) Since \(a+a=0\text{,}\) \(-a = a\text{,}\) which is in \(S\text{.}\) Adding three \(a\)’s together doesn’t give us anything new: \(a + a + a = a\in S\) In fact, \(n a\) is in \(S\) for all possible positive integers \(n\text{.}\) Next,
\begin{equation*} \begin{split} a^3 & = a^2 \cdot a \\ & = (a +1)\cdot a \\ & = a^2+ a\\ & = (a+1)+a\\ & =1 \\ \end{split} \end{equation*}
Therefore, \(a^{-1}= a+1 = a^2\) and \((a+1)^{-1}=a\text{.}\)
It is not difficult to see that \(a^n\) is in \(S\) for all positive \(n\text{.}\) Does \(S\) contain all zeros of \(x^2 + x + 1\text{?}\) Remember, \(g(x)\) can have at most two distinct zeros and we called one of them \(a\text{,}\) so if there is a second, it must be \(a + 1\text{.}\) To see if \(a + 1\) is indeed a zero of \(g(x)\text{,}\) simply compute \(f(a + 1)\text{:}\)
\begin{equation*} \begin{split} f(a+1) & = (a + 1)^2 + (a+1) + 1\\ &= a ^2 +1 + a+1+ 1 \\ & =a^2+a + 1\\ & =0\\ \end{split} \end{equation*}
Therefore, \(a + 1\) is also a zero of \(x^2 + x + 1\text{.}\) Hence, \(S = \{0, 1, a, a + 1\}\) is the smallest field that contains \(\mathbb{Z}_2 = \{0, 1\}\) as a subfield and contains all zeros of \(x^2 + x + 1\text{.}\) This extension field is denoted by \(\mathbb{Z}_2(a)\text{.}\) Note that \(x^2 + x + 1\) splits in \(\mathbb{Z}_2(a)\text{;}\) that is, it factors into linear factors in \(\mathbb{Z}_2(a)\text{.}\) We also observe that \(\mathbb{Z}_2(a)\) is a field containing exactly four elements. By Theorem 16.2.10, we expected that \(\mathbb{Z}_2(a)\) would be of order \(p^2\) for some prime \(p\) and positive integer \(n\text{.}\) Also recall that all fields of order \(p^n\) are isomorphic. Hence, we have described all fields of order \(2^2 =4\) by finding the extension field of a polynomial that is irreducible over \(\mathbb{Z}_2\text{.}\)
The reader might feel somewhat uncomfortable with the results obtained in Example 16.4.2. In particular, what is \(a\text{?}\) Can we describe it through a known quantity? All we know about \(a\) is that it is a zero of \(g(x)\) and that \(a^2= a + 1\text{.}\) We could also say that \(a(a + 1) = 1\text{,}\) but we really expected more. However, should we expect more? In Example 16.4.1, \(\sqrt{2}\) is a number we are more comfortable with, but all we really know about it is that \(\alpha =\sqrt{2}\) is the number such that \(\alpha ^2= 2\text{.}\) Similarly, the zero that the reader will obtain in Exercise 2 of this section is the imaginary number \(i\text{.}\) Here again, this is simply a symbol, and all we know about it is that \(i^2=-1\text{.}\) Hence, the result obtained in Example 16.4.2 is not really that strange.
The reader should be aware that we have just scratched the surface in the development of topics in polynomial rings. One area of significant applications is in coding theory.
An important observation regarding the previous example is that the nonzero elements of \(GF(4)\) can be represented two ways. First as a linear combination of 1 and \(a\text{.}\) There are four such linear combinations, one of which is zero. Second, as powers of \(a\text{.}\) There are three distinct powers and the each match up with a nonzero linear combination:
\begin{equation*} \begin{array}{c} a^0 = 1\cdot 1 + 0 \cdot a\\ a^1 = 0\cdot 1 + 1 \cdot a\\ a^2 = 1\cdot 1 + 1 \cdot a\\ \end{array} \end{equation*}
Next, we briefly describe the field \(GF(8)\) and how an error correcting code can be build on a the same observation about that field.
First, we start with the irreducible polynomial \(p(x)=x^3 + x + 1\) over \(\mathbb{Z}_2\text{.}\) There is another such cubic polynomial, but its choice produces essentially the same result. Just as we did in the previous example, we assume we have a zero of \(p(x)\) and call it \(\beta\text{.}\) Since we have assumed that \(p(\beta)= \beta^3+\beta + 1=0\text{,}\) we get the recurrence relation for powers \(\beta^3=\beta + 1\) that lets us reduce the seven powers \(\beta^k\text{,}\) \(0 \leq k \leq 6\text{,}\) to linear combinations of 1, \(\beta\text{,}\) and \(\beta^2\text{.}\) Higher powers will reduce to these seven, which make up the elements of a field with \(2^3=8\) elements when we add zero to the set. We leave as an exercise for you to set up a table relating powers of \(\beta\) with the linear combinations.
With this information we are now in a position to take blocks of four bits and encode them with three parity bits to create an error correcting code. If the bits are \(b_3b_4b_5b_6\text{,}\) then we reduce the expression \(B_m= b_3\cdot \beta^3 +b_4\cdot \beta^4 +b_5\cdot \beta^5 +b_6\cdot \beta^6\) using the recurrence relation to an expression \(B_p=b_0\cdot 1 +b_1\cdot \beta +b_2\cdot \beta^2\text{.}\) Since we are equating equals within \(GF(8)\text{,}\) we have \(B_p=B_m\text{,}\) or \(B_p+B_m=0\text{.}\) The encoded message is \(b_0b_1b_2b_3b_4b_5b_6\text{,}\) which is a representation of 0 in \(GF(8)\text{.}\) If the transmitted sequence of bits is received as \(c_0c_1c_2c_3c_4c_5c_6\) we reduce \(C=c_0\cdot 1 +c_1\cdot \beta +c_2\cdot \beta^2 +c_3\cdot \beta^3 +c_4\cdot \beta^4 +c_5\cdot \beta^5 +c_6\cdot \beta^6\) using the recurrence. If there was no transmission error, the result is zero. If the reduced result is zero it is most likely that the original message was \(c_3c_4c_5c_6\text{.}\) If bit \(k\) is switched in the transmission, then
\begin{equation*} C = B_p+B_m+ \beta^k= \beta^k \end{equation*}
Therefore if we reduce \(C\) with the recurrence, we get the linear combination of 1, \(\beta\text{,}\) and \(\beta^2\) that is equal to \(\beta^k\) and so we can identify the location of the error and correct it.

Exercises Exercises

1.

  1. Use the definition of a field to show that \(\mathbb{Q}(\sqrt{2})\) is a field.
  2. Use the definition of vector space to show that \(\mathbb{Q}\left(\sqrt{2}\right)\) is a vector space over \(\mathbb{Q}\text{.}\)
  3. Prove that \(\left\{1,\sqrt{2}\right\}\) is a basis for the vector space \(\mathbb{Q}\left(\sqrt{2}\right)\) over \(\mathbb{Q}\text{,}\) and, therefore, the dimension of \(\mathbb{Q}(\sqrt{2})\) over \(\mathbb{Q}\) is 2.
Answer.
If \(a_0+ a_1\sqrt{2}\in \mathbb{Q}\left[\sqrt{2}\right]\) is nonzero, then it has a multiplicative inverse:
\begin{equation*} \begin{split} \frac{1}{a_0+ a_1\sqrt{2}} &=\frac{1}{a_0+ a_1\sqrt{2}}\frac{a_0- a_1\sqrt{2}}{a_0- a_1\sqrt{2}}\quad\\ & =\frac{a_0- a_1\sqrt{2}}{a_0{}^2- 2a_1{}^2}\\ & =\frac{a_0}{a_0{}^2- 2a_1{}^2}-\frac{ a_1}{a_0{}^2- 2a_1{}^2}\sqrt{2} \end{split} \end{equation*}
The denominator, \(a_0{}^2- 2a_1{}^2\text{,}\) is nonzero since \(\sqrt{2}\) is irrational. Since \(\frac{a_0}{a_0{}^2- 2a_1{}^2}\) and\(\frac{-a_1}{a_0{}^2- 2a_1{}^2}\) are both rational numbers, \(a_0+ a_1\sqrt{2}\) is a unit of \(\mathbb{Q}\left[\sqrt{2}\right]\text{.}\) The field containing \(\mathbb{Q}\left[\sqrt{2}\right]\) is denoted \(\mathbb{Q}\left(\sqrt{2}\right)\) and so \(\mathbb{Q}\left(\sqrt{2}\right)=\mathbb{Q}\left[\sqrt{2}\right]\)

2.

  1. Determine the splitting field of \(f(x) = x^2+ 1\) over \(\mathbb{R}\text{.}\) This means consider the polynomial \(f(x) = x^2+1 \in \mathbb{R}[x]\) and find the smallest field that contains \(\mathbb{R}\) and all the zeros of \(f(x)\text{.}\) Denote this field by \(\mathbb{R}(i)\text{.}\)
  2. \(\mathbb{R}(i)\) is more commonly referred to by a different name. What is it?
  3. Show that \(\{1, i\}\) is a basis for the vector space \(\mathbb{R}(i)\) over \(\mathbb{R}\text{.}\) What is the dimension of this vector space (over \(\mathbb{R}\))?

3.

Determine the splitting field of \(x^4 - 5x^2 + 6\) over \(\mathbb{Q}\text{.}\)
Answer.
\(x^4 - 5x^2 +6 = (x^2 - 2)(x^2 - 3)\) has zeros \(\pm \sqrt{2}\) and \(\pm \sqrt{3}\text{.}\)
\(\mathbb{Q}(\sqrt{2}) = \{a + b\sqrt{2} \mid a, b \in \mathbb{Q}\}\) contains the zeros \(\pm \sqrt{2}\) but does not contain \(\pm \sqrt{3}\text{,}\) since neither are expressible in the form \(a + b\sqrt{2}\text{.}\) If we consider the set \(\{c + d\sqrt{3} \mid c,d \in \mathbb{Q}(\sqrt{2})\}\text{,}\) then this field contains \(\pm \sqrt{3}\) as well as \(\pm \sqrt{2}\text{,}\) and is denoted \(\mathbb{Q}(\sqrt{2})(\sqrt{3})= \mathbb{Q}(\sqrt{2}, \sqrt{3})\text{.}\) Taking into account the form of \(c\) and \(d\) in the description above, we can expand to
\begin{equation*} \mathbb{Q}(\sqrt{2},\sqrt{3})= \{b_0 + b_1\sqrt{2} + b_2 \sqrt{3} +b_3\sqrt{6} \mid b_i \in \mathbb{Q}\} \end{equation*}

4.

  1. Factor \(x^2 + x + 1\) into linear factors in \(\mathbb{Z}_2(a)\text{.}\)
  2. Write out the field tables for the field \(\mathbb{Z}_2(a)\) and compare the results to the tables of Example 16.2.7.
  3. Cite a theorem and use it to show why the results of part b were to be expected.

5.

  1. Show that \(x^3+ x + 1\) is irreducible over \(\mathbb{Z}_2\text{.}\)
  2. Determine the splitting field of \(x^3+ x + 1\) over \(\mathbb{Z}_2\text{.}\)
  3. By Theorem 16.2.10, you have described all fields of order \(2^3\text{.}\)
Answer.
  1. \(f(x) = x^3 + x + 1\) is reducible if and only if it has a factor of the form \(x- a\text{.}\) By Theorem 16.3.14, \(x-a\) is a factor if and only if \(a\) is a zero. Neither 0 nor 1 is a zero of \(f(x)\) over \(\mathbb{Z}_2\text{.}\)
  2. Since \(f(x)\) is irreducible over \(\mathbb{Z}_2\text{,}\) all zeros of \(f(x)\) must lie in an extension field of \(\mathbb{Z}_2\) . Let c be a zero of \(f(x)\text{.}\) \(\mathbb{Z}_2(c)\) can be described several different ways. One way is to note that since \(c \in \mathbb{Z}_2(c)\text{,}\) \(c^n\in \mathbb{Z}_2(c)\) for all n. Therefore, \(\mathbb{Z}_2(c)\) includes 0, \(c\text{,}\) \(c^2\text{,}\) \(c^3, \ldots\text{.}\) But \(c^3 = c + 1\) since \(f(c) = 0\text{.}\) Furthermore, \(c^4 = c^2+ c\text{,}\) \(c^5= c^2+ c +1\text{,}\) \(c^6= c^2+1\text{,}\) and \(c^7=1\text{.}\) Higher powers of \(c\) repeat preceding powers. Therefore,
    \begin{equation*} \begin{split} \mathbb{Z}_2(c)&= \left\{0, 1, c, c^2 , c + 1, c^2 + 1, c^2 + c + 1, c ^2 + c\right\}\\ &= \left\{a_0+ a_1c+a_2c^2 \mid a_i\in \mathbb{Z}_2\right\}\\ \end{split} \end{equation*}
    The three zeros of \(f(x)\) are \(c\text{,}\) \(c^2\) and \(c^2+ c\text{.}\)
    \begin{equation*} f(x) = (x + c)\left(x+ c ^2 \right)\left(x + c^2 + c\right) \end{equation*}
  3. Cite Theorem Theorem 16.2.10, part 3.

6.

  1. List all polynomials of degree 1, 2, 3, and 4 over \(\mathbb{Z}_2 = GF(2)\text{.}\)
  2. From your list in part a, identify all irreducible polynomials of degree 1, 2, 3, and 4.
  3. Determine the splitting fields of each of the polynomials in part b.
  4. What is the order of each of the splitting fields obtained in part c? Explain your results using Theorem 16.2.10.

7.

Is the polynomial code described in this section a linear code?
<Prev^TopNext>