Exercise 2.4Z: Finite and Infinite Fields
In mathematics, different sets of numbers are distinguished:
- the set of natural numbers: $\mathcal{N} = \{0, \, 1, \, 2, \hspace{0.05cm}\text{ ...} \}$,
- the set of integers: $\mathcal{Z} = \{\text{ ...}, \, -1, \, 0, \, +1, \hspace{0.05cm}\text{ ...} \}$,
- the set of rational numbers: $\mathcal{Q} = \{m/n\}$ with $m ∈ \mathcal{Z}, \ n ∈ \mathcal{Z} \, \backslash \, \{0\}$,
- the set $\mathcal{R}$ of real numbers,
- the set of complex numbers: $\mathcal{C}= \{a + {\rm j} \cdot b\}$ with $a ∈ \mathcal{R}, \ b ∈ \mathcal{R}$ and the imaginary unit "$\rm j$".
Such a set is called a "field" in the algebraic sense if (and only if) the four arithmetic operations addition, subtraction, multiplication and division are allowed in it and the results are representable in the same field.
Some related definitions can be found in the "theory section". So much up front: Not all of the sets listed here are fields.
Besides, there are also "finite fields", which in our learning tutorial are also called "Galois field" ${\rm GF}(P^m)$ where
- $P ∈ \mathcal{P}$ denotes a prime number, and
- $m ∈ \mathcal{N}$ denotes a natural number.
If the exponent $m \ge 2$, it is called an "extension field". In this exercise we restrict ourselves to extension fields to the base $P = 2$.
The first two subtasks are related to the classification of polynomials.
- A degree-m polynomial is called "reducible" in the field $\mathcal{F}$ if it is representable in the form
- $$p(x)= \prod_{i = 1}^m (x-x_i) = (x - x_1) \cdot (x - x_2) \cdot \hspace{0.05cm}\text{ ...}\hspace{0.05cm} \cdot (x - x_m) $$
and holds for all zeros $x_i ∈ \mathcal{F}$.
- If this is not possible, one speaks of an "irreducible polynomial".
Hints:
- This exercise belongs to the chapter "Extension Field".
- Above you can see illustrations of the Italian mathematicians Gerolamo Cardano and Rafael Bombelli, who first introduced imaginary numbers to solve algebraic equations, and of Évariste Galois, who established the foundations of finite fields at a very young age.
Questions
Solution
A polynomial of degree $m$ is called "reducible" in the field $\mathcal{F}$ if it is can be represented the form
- $$p(x)= \prod_{i = 1}^m (x-x_i) = (x - x_1) \cdot (x - x_2) \cdot \hspace{0.05cm}\text{ ...}\hspace{0.05cm} \cdot (x - x_m) $$
and this is valid for all zeros $x_i ∈ \mathcal{F}$. If this is not possible, one speaks of an "irreducible" polynomial.
In real number space, it hold for the $m = 2$ zeros $x_1$ and $x_2$:
- $$p_1(x) \text{:}\hspace{0.3cm}x_1 \hspace{-0.15cm} \ = \ \hspace{-0.15cm} +{\rm j}\hspace{0.05cm},\hspace{0.2cm}x_2 = -{\rm j}\hspace{0.05cm},$$
- $$p_2(x) \text{:}\hspace{0.3cm}x_1 \hspace{-0.15cm} \ = \ \hspace{-0.15cm} +1\hspace{0.05cm},\hspace{0.2cm}x_2 = -1\hspace{0.05cm},$$
- $$p_3(x) \text{:}\hspace{0.3cm}x_1 \hspace{-0.15cm} \ = \ \hspace{-0.15cm} -0.5 + {\rm j} \cdot \sqrt{3}/2 \hspace{0.05cm},\hspace{0.2cm}x_2 = -0.5 - {\rm j} \cdot \sqrt{3}/2\hspace{0.05cm},$$
- $$p_4(x) \text{:}\hspace{0.3cm}x_1 \hspace{-0.15cm} \ = \ \hspace{-0.15cm} +1\hspace{0.05cm},\hspace{0.2cm}x_2 = -2\hspace{0.05cm}.$$
Thus the proposed solutions 1 and 3 are correct:
- The two zeros of $p_2(x)$ and $p_4(x)$ are both real. Thus, these are certainly reducible polynomials.
- The other two polynomials, on the other hand, have no real zeros (rather imaginary or complex ones) and they are irreducible in the real field according to the above definition.
(2) Correct is the proposed solution 3:
$p_3 = x^2 + x + 1$ is the only irreducible polynomial in the Galois field $\rm GF(2^2)$. In the "theory section" the additions and the multiplication table were given for this.
For the other polynomials holds:
- The polynomial $p_1(x)$ is reducible in ${\rm GF}(2) = \{0, \, 1\}$ since this polynomial can be factorized:
- $$p_1(x) = x^2 + 1 = (x+1)^2\hspace{0.05cm}.$$
- Since in $\rm GF(2)$ there is no difference between sum and difference, the polynomial $p_2(x) = x^2 - 1$ is also reducible.
- The polynomial $p_4(x) = x^2 + x - 2$ is unsuitable for $\rm GF(2)$ alone, since not all polynomial coefficients are $0$ or $1$. The "$2$" would only be possible in the Galois field $\rm GF(3)$.
(3) Correct are the last three proposed solutions:
- The set $\mathcal{N}$ is not a field, since already the subtraction is not allowed for all elements, for example $2 - 3 = -1 ∉ \mathcal{N}$.
- Also the set $\mathcal{Z}$ of integers is not a field, since for example the equation $2 \cdot z = 1$ is not to be satisfied for any $z ∈ \mathcal{N}$.
(4) Correct are the answers 1 and 3:
- It is $\mathcal{Q} ⊂ \mathcal{R}$ (rational numbers are a subset of real numbers) and $\mathcal{R} ⊂ \mathcal{C}$ (real numbers are a subset of the complex numbers).
- Thus also $\mathcal{Q} ⊂ \mathcal{C}$.
- For finite fields, ${\rm GF}(2^m) ⊂ {\rm GF}(2^M)$ means that $m < M$ must hold.
(5) Correct is only the proposed solution 2:
- The set $\mathcal{C}$ of complex numbers is an extension of the real numbers $(\mathcal{R})$ into a second dimension. For this can be written:
- $$\mathcal{C} = \{k_0 + {\rm j} \cdot k_1\hspace{0.05cm}| \hspace{0.05cm}k_0 \in {\mathcal{R}}, k_1 \in \mathcal{R}\}\hspace{0.05cm}.$$
- $\rm GF(2^2)$ is an extension of the finite field $\rm GF(2) = \{0, \, 1\}$ into a second dimension:
- $${\rm GF}(2^2) = \{k_0 + \alpha \cdot k_1\hspace{0.05cm}| \hspace{0.05cm}k_0 \in {\rm GF}(2), k_1 \in {\rm GF}(2)\}\hspace{0.05cm}.$$
- The imaginary unit ${\rm j} ∉ \mathcal{C}$ results as the solution of the equation ${\rm j}^2 + 1 = 0$, while the new element of $\rm GF(2^2)$ is denoted by $\alpha ∉ \rm GF(2)$ and follows from the equation $\alpha^2 + \alpha + 1 = 0$.
