# Differences

This shows you the differences between two versions of the page.

— |
finite_fields:08_subfields [2014/01/08 15:47] (current) marje created |
||
---|---|---|---|

Line 1: | Line 1: | ||

+ | ====== - #8 Subfields ====== | ||

+ | |||

+ | ===== - What is a subfield? ===== | ||

+ | |||

+ | A large field can contain a smaller field. For instance, $\mathbb{F}_{2^k}$ always contains as a sub-field the 2-element subset $\mathcal{S} = \left\{0,1\right\}$ consisting of constant polynomials — it is easy to check that this subset satisfies the definition of field (it is closed under addition and multiplication; it contains a zero element and an identity element; every element has an opposite element in $\mathcal{S}$ since $-0 = 0$ and $-1 = 1$ in $\mathbb{F}_{2^k}$; addition and multiplication are commutative etc.). Another way to see that this two-element subset is a field is to notice that it can be identified with $\mathbb{F}_{2} = \mathbb{Z}_{2}$, as the addition and multiplication of elements $0$ and $1$ are defined in $\mathbb{F}_{2^k}$ the same way as in $\mathbb{F}_{2}$ (so one can say that $\mathbb{F}_{2^k}$ contains $\mathbb{F}_{2}$ as a subfield). More generally: | ||

+ | <WRAP def> | ||

+ | Let $\mathcal F$ be a field. A subset $\mathcal{S} \subseteq \mathcal F$ is called a **subfield** of $\mathcal F$ if $\mathcal{S}$ is a field itself with respect to the operations of $\mathcal F$. | ||

+ | </WRAP> | ||

+ | |||

+ | By this definition, every field is a subfield of itself. But it may also contain strictly smaller subfields. Those are called the **proper subfields**. For example, as we saw, $\mathbb{F}_{2}$ is a proper subfield of $\mathbb{F}_{2^k}$ for $k > 1$. | ||

+ | |||

+ | A practical criterion for checking whether a subset of a field is a subfield is the following: | ||

+ | |||

+ | <WRAP def><BOOKMARK:subfield_criterion> | ||

+ | **Proposition (Subfield criterion).** Let $\mathcal F$ be a field. A subset $\mathcal{S} \subseteq \mathcal F$ is a subfield of $\mathcal F$ if and only if it contains the zero and identity element of $\mathcal F$, is closed under the multiplication, addition and taking opposite elements of $\mathcal F$, and $\mathcal{S}\setminus \{0\}$ (the set of non-zero elements belonging to $\mathcal{S}$) is closed under taking inverses in $\mathcal F$. | ||

+ | </WRAP> | ||

+ | ++++ Proof | | ||

+ | Let's show necessity, i. e. that every subfield $\mathcal{S} \subseteq \mathcal F$ satisfies the conditions given in the proposition. | ||

+ | |||

+ | Suppose $\mathcal{S} \subseteq \mathcal F$ is a subfield of $\mathcal F$. Any field contains exactly two elements $x$ satisfying $x \cdot x = x$, namely its zero and identity element (indeed, if $x \neq 0$ and $x \cdot x = x$ then $x = 1 \cdot x = (x^{-1} \cdot x) \cdot x = x^{-1} \cdot (x \cdot x) = x^{-1} \cdot x = 1$), and therefore $\mathcal G$ must contain the zero and the identity element of $\mathcal F$. Moreover, actually the zero element of $\mathcal G$ is the zero of $\mathcal F$ and the identity element of $\mathcal G$ is the identity of $\mathcal F$, since in any field only the zero element satisfies $x + x = x$. | ||

+ | |||

+ | Obviously $\mathcal{S}$ must be closed under multiplication and addition by the definition of field. To prove that $\mathcal{S}$ is closed under taking opposite elements in $\mathcal F$, we will show that the opposite element of every element of $\mathcal{S}$ is its opposite element in $\mathcal F$. Let $a \in \mathcal{S}$ be arbitrary. By the definition of opposite element, the opposite element of $a$ in $\mathcal S$ is an element $b \in \mathcal S$ sucht that $a + b$ is the zero element of $\mathcal S$. Since the zero element of $\mathcal S$ coincides with the zero element of $\mathcal F$, such an element is also the zero element of $a$ in $\mathcal F$. By the uniqueness of opposite element, the opposite element of $a$ in $\mathcal S$ must therefore coincide with the opposite element in $\mathcal F$. | ||

+ | |||

+ | Analogously one shows that taking inverse elements in $\mathcal S$ is the same as taking inverse elements in $\mathcal F$ and therefore $\mathcal S\setminus \{0\}$ is closed under taking inverses in $\mathcal F$. The necessity part of the proposition has thus been proven. | ||

+ | |||

+ | Sufficiency is obvious: if a subset $\mathcal{S} \subseteq \mathcal F$ satisfies the conditions given in the proposition then it is straightforward to check that it satisfies all field axioms. | ||

+ | ++++ | ||

+ | |||

+ | <WRAP task> | ||

+ | Which of the following sets of real numbers are subfields of the field $\mathbb R$? | ||

+ | - $\mathbb Q$, the set of rational numbers ++Answer|Yes, $\mathbb Q$ is a subfield of $\mathbb R$.++ | ||

+ | - $\mathbb Z$, the set of integers ++Answer|$\mathbb Z$ is not a subfield of $\mathbb R$ since it is not closed under taking inverses: e. g. $2^{-1} \not\in \mathbb Z$.++ | ||

+ | - $\{ \ldots, \frac14, \frac12, 1, 2, 4, 8, \ldots \}$, the set of integer powers of $2$ ++Answer|This is not a subfield since it is not closed under addition: e. g. $2 + 4 = 6$ which is not an integer power of $2$.++ | ||

+ | - $\mathbb R$, the set of all real numbers ++Answer|Yes, $\mathbb R$ itself is a subfield of $\mathbb R$.++ | ||

+ | - $\{0\}$, the one-element set consisting of number zero ++Answer|This is not a subfield since it does not contain the identity element $1 \in \mathbb R$.++ | ||

+ | - $\{0, 1\}$ ++Answer|Yes, this is a subfield of $\mathbb R$.++ | ||

+ | </WRAP> | ||

+ | |||

+ | ===== - Subfields in finite fields ===== | ||

+ | |||

+ | The definition and criterion above hold for both finite and infinite fields. | ||

+ | But the simplest way to find a sub-field of a finite field is to find an non-invertible | ||

+ | element that generates the entire multiplicative group of a | ||

+ | sub-field. Such an element must exist, since the multiplicative group of a finite field | ||

+ | is always generated by a single element, as we know from the previous lesson [[07_multiplicative_group]]. | ||

+ | |||

+ | For example, $\mathbb{F}_{16}$ specified by the polynomial $\alpha^4+\alpha^3+ | ||

+ | \alpha^2+\alpha+ 1$ might contain subfields of size $2$ and | ||

+ | $4$, as elements in the multiplicative group have orders $1$, $3$, $5$ | ||

+ | and field sizes must be powers of primes. For instance, let us consider the element | ||

+ | $\alpha^3+ \alpha^2$ and see whether it generates the multiplicative group of some subfield. | ||

+ | The element $\alpha^3+ \alpha^2$ has order $3$ in the multiplicative group of $\mathbb{F}_{16}$ since | ||

+ | \[\begin{align*} | ||

+ | (\alpha^3+ \alpha^2)(\alpha^3+ \alpha^2)&=\alpha^3+\alpha+ 1,\\ | ||

+ | (\alpha^3+ \alpha^2)(\alpha^3+\alpha+ 1)&=1\enspace. | ||

+ | \end{align*}\] | ||

+ | |||

+ | So it is plausible that these three powers of $\alpha^3+ \alpha^2$ together with zero could form a subfield of $\mathbb{F}_{16}$, which is a representation of the four-element field $\mathbb{F}_4$. To check that this four-element subset $\{0,\ 1,\ \alpha^3+ \alpha^2,\ \alpha^3+\alpha+ 1\}$ is indeed a subfield by using [[#subfield_criterion| Proposition (Subfield criterion)]], we need to check that it is closed under addition and taking opposite element, since closedness of the three-element subset $\{1,\ \alpha^3+ \alpha^2,\ \alpha^3+\alpha+ 1\}$ under multiplication and inverses follows from the fact that it is the fact that by construction it is a subgroup of the multiplicative group of $\mathbb{F}_{16}$ (namely the one generated by the element $\alpha^3+ \alpha^2$) and a subset of a field that is closed under multiplication obviously stays so if we add zero to it. Closedness under taking opposite element is also obvious, since in the field $\mathbb{F}_{16}$, the opposite of any element is the element itself. Closedness under addition is easy to verify by direct computation (basically by computing the 4-by-4 addition table of this four-element set and check that all the entries lie in the set — but for most entries this is trivially true, so not much actual computation is needed). Therefore the four-element subset $\{0,\ 1,\ \alpha^3+ \alpha^2,\ \alpha^3+\alpha+ 1\} \subset \mathbb{F}_{16}$ turns indeed out to be a subfield. So $\mathbb{F}_{16}$ contains $\mathbb{F}_{4}$ as a subfield. | ||

+ | |||

+ | Actually it turns out that this manual verification of closedness under addition and opposite element was unnecessary, thanks to the following result, which we will not prove here. | ||

+ | |||

+ | <WRAP def> | ||

+ | **Theorem.** Let $p$ be a prime, $k$ a positive integer and $a$ a non-zero element of $\mathbb F_{p^k}$. The set of all integer powers of $a$ together with the zero element is a subfield of $\mathcal F$ if and only if the order of $a$ in the multiplicative group of $\mathbb F_{p^k}$ is of the form $p^\ell - 1$ where $j$ is a positive integer. | ||

+ | </WRAP> | ||

+ | |||

+ | Indeed, the theorem says that since the order of $\alpha^3+ \alpha^2$ in the multiplicative group is of the form $2^\ell-1$ (because $3 = 2^2-1$), the powers of $\alpha^3+ \alpha^2$ together with $0$ must form a subfield of $\mathbb F_{16}$. | ||

+ | |||

+ | <WRAP task> | ||

+ | Prove that $\mathbb{F}_{p^\ell}$ is a sub-field of $\mathbb{F}_{p^k}$ if and only if $p^\ell-1$ divides $p^k-1$.\\ | ||

+ | |||

+ | //Hint:// Consider the orders of generators. | ||

+ | </WRAP> | ||

+ | |||

+ | <WRAP task> | ||

+ | Which of the fields $\mathbb{F}_4,\mathbb{F}_8,\mathbb{F}_{16},\ldots,\mathbb{F}_{256}$ contain proper subfields of size more than two? ++ Solution. | Answer: $\mathbb{F}_{16}$, $\mathbb{F}_{64}$ and $\mathbb{F}_{256}$. | ||

+ | |||

+ | Indeed, from the theorem above we know that all subfields of $\mathbb{F}_{2^k}$ are of the form $\mathbb{F}_{2^\ell}$ (there are no subfields $\mathbb{F}_{p^\ell}$ where $p > 2$). So we can use the statement proven in the previous exercise to determine whether a field $\mathbb{F}_{2^k}$ contains a proper subfield of size more than two: this happens if and only if $2^k-1$ is divisible by $2^\ell-1$ for some $\ell$ with $0 < \ell < k$. ++ | ||

+ | </WRAP> | ||

+ | |||

+ | Since we know that our example subfield $\{0,\ 1,\ \alpha^3+ \alpha^2,\ \alpha^3+\alpha+ 1\} \subset \mathcal F_{16}$ is the four-element field $\mathbb F_4$, we could obviously use raw encoding of these polynomials $0000$, $0001$, $1100$ and $1011$ to represent $\mathbb{F}_4$. However, this representation is wasteful: since $\mathbb{F}_4$ contains four elements, these elements can be represented by two bits instead of four. Moreover, we know that $\mathbb{F}_4$ can be constructed as a set of polynomials of first degree with coefficients in $\mathbb Z_2$; these coefficients can be stored in two bits in a natural way, so it is also convenient to make computations in the two-bit representation (in other words, packing the elements into two bits does not come at the expense of CPU usage). So we haven't found a better representation of $\mathbb{F}_4$ than we knew before, but knowing that the field $\mathbb{F}_{16}$ contains $\mathbb{F}_4$ is still a nice mathematical insight, which may be useful. For example, if we have variables with values in the field $\mathbb{F}_{16}$ and at some point we realize that the values of the variables actually only belong to the set $\{0000, 0001, 1100, 1011\}$ then we can re-encode the variables into two bits to enchance memory and CPU efficiency of the field operations. | ||

+ | |||

+ | <WRAP task> | ||

+ | Let $\mathbb{F}_4$ be specified by the polynomial $\beta^2+\beta+ 1$. Define the corresponding isomorphism from $\mathbb{F}_4$ to the subset $\{0,\ 1,\ \alpha^3+ \alpha^2,\ \alpha^3+\alpha+ 1\}$ of $\mathbb{F}_{16}$. ++++ Solution. | The multiplicative group of $\mathbb{F}_4$ is generated by the element $\beta$ since $\beta^2 \neq 1$ in $\mathbb{F}_4$. Let's try to define the isomorphism from $\mathbb{F}_4$ to $\{0,\ 1,\ \alpha^3+ \alpha^2,\ \alpha^3+\alpha+ 1\} \subset \mathcal F_{16}$ by mapping the generator $\beta$ to the generator $\alpha^3+ \alpha^2$. To prove that the mapping $\beta \mapsto \alpha^3+ \alpha^2$ can be extended to a homomorphism, it suffices to check that | ||

+ | \[(\alpha^3+ \alpha^2)^2 + (\alpha^3+ \alpha^2) + 1 = 0\] | ||

+ | in $\mathbb{F}_{16}$, i. e. modulo $\alpha^4 + \alpha^3 + \alpha^2 + \alpha + 1$. The equality holds indeed, since | ||

+ | \begin{align*} | ||

+ | (\alpha^3+ \alpha^2)^2 + (\alpha^3+ \alpha^2) + 1 &= (\alpha^6 + \alpha^4) + (\alpha^3+ \alpha^2) + 1 =\\ | ||

+ | &= (\alpha^2 + \alpha + 1)(\alpha^4 + \alpha^3 + \alpha^2 + \alpha + 1). | ||

+ | \end{align*} | ||

+ | This homomorphism is an isomorphism from $\mathbb{F}_4$ to $\{0,\ 1,\ \alpha^3+ \alpha^2,\ \alpha^3+\alpha+ 1\}$ because every homomorphism of fields is one-to-one and the two sets have the same size. ++++ | ||

+ | </WRAP> | ||