Difference between revisions of "Aufgaben:Exercise 2.4Z: Finite and Infinite Fields"

From LNTwww
 
(2 intermediate revisions by the same user not shown)
Line 28: Line 28:
 
The first two subtasks are related to the classification of polynomials.  
 
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 in the form
+
*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) $$
 
:$$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) $$
  
is representable and holds for all zeros $x_i ∈ \mathcal{F}$. If this is not possible, one speaks of an ''irreducible polynomial''.
+
and holds for all zeros  $x_i ∈ \mathcal{F}$.  
 
 
  
 +
*If this is not possible,  one speaks of an  "irreducible polynomial".
  
  
Line 39: Line 39:
  
  
 +
Hints:
 +
* This exercise belongs to the chapter  [[Channel_Coding/Extension_Field|"Extension Field"]].
  
Hints:
+
* Above you can see illustrations of the Italian mathematicians  [https://en.wikipedia.org/wiki/Gerolamo_Cardano Gerolamo Cardano]  and  [https://en.wikipedia.org/wiki/Rafael_Bombelli Rafael Bombelli], who first introduced imaginary numbers to solve algebraic equations, and of  [https://en.wikipedia.org/wiki/%C3%89variste_Galois Évariste Galois], who established the foundations of finite fields at a very young age.
* This exercise belongs to the chapter  [[Channel_Coding/Extension_Field|"extension fields"]].
 
* Above you can see illustrations of the Italian mathematicians  [https://en.wikipedia.org/wiki/Gerolamo_Cardano "Gerolamo Cardano"]  and  [https://en.wikipedia.org/wiki/Rafael_Bombelli "Rafael Bombelli"], who first introduced imaginary numbers to solve algebraic equations, and of  [https://en.wikipedia.org/wiki/%C3%89variste_Galois "Évariste Galois"], who established the foundations of finite fields at a very young age.
 
  
  
Line 88: Line 88:
 
'''(1)'''  In the data section it says accordingly:
 
'''(1)'''  In the data section it says accordingly:
 
   
 
   
A polynomial of degree $m$ is called ''reducible'' in the field $\mathcal{F}$ if it is in the form
+
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) $$
 
:$$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) $$
  
can be represented and is valid for all zeros $x_i ∈ \mathcal{F}$. If this is not possible, one speaks of an ''irreducible'' polynomial.
+
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, for each  $m = 2$  zeros  $x_1$  and  $x_2$ hold:
+
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_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_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},$$
Line 99: Line 99:
 
:$$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}.$$
 
:$$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 <u>proposed solutions 1 and 3</u> are correct:
+
Thus the&nbsp; <u>proposed solutions 1 and 3</u>&nbsp; are correct:
*The two zeros of $p_2(x)$ and $p_4(x)$ are both real. Thus, these are certainly reducible polynomials.  
+
*The two zeros of&nbsp; $p_2(x)$&nbsp; and&nbsp; $p_4(x)$&nbsp; are both real.&nbsp; Thus,&nbsp; these are certainly reducible polynomials.
*The other two polynomials, on the other hand, have no real zeros (rather imaginary or complex ones) and are irreducible in the real field according to the above definition.  
+
 +
*The other two polynomials,&nbsp; on the other hand,&nbsp; have no real zeros&nbsp; (rather imaginary or complex ones)&nbsp; and they are irreducible in the real field according to the above definition.  
  
  
  
  
'''(2)'''&nbsp; Correct is the <u>proposed solution 3</u>:  
+
'''(2)'''&nbsp; Correct is the&nbsp; <u>proposed solution 3</u>:
$p_3 = x^2 + x + 1$&nbsp; is the only irreducible polynomial in the Galois field &nbsp;$\rm GF(2^2)$. In the [[Channel_Coding/Extension_Field#GF.2822.29_.E2.80.93_Example_of_an_extension_field|"theory section"]] the additions and the multiplication table were given for this.  
+
 +
$p_3 = x^2 + x + 1$&nbsp; is the only irreducible polynomial in the Galois field &nbsp;$\rm GF(2^2)$.&nbsp; In the [[Channel_Coding/Extension_Field#GF.2822.29_.E2.80.93_Example_of_an_extension_field|"theory section"]]&nbsp; the additions and the multiplication table were given for this.  
  
 
For the other polynomials holds:
 
For the other polynomials holds:
 
* The polynomial&nbsp; $p_1(x)$&nbsp; is reducible in&nbsp; ${\rm GF}(2) = \{0, \, 1\}$&nbsp; since this polynomial can be factorized:
 
* The polynomial&nbsp; $p_1(x)$&nbsp; is reducible in&nbsp; ${\rm GF}(2) = \{0, \, 1\}$&nbsp; since this polynomial can be factorized:
 
:$$p_1(x) = x^2 + 1 = (x+1)^2\hspace{0.05cm}.$$
 
:$$p_1(x) = x^2 + 1 = (x+1)^2\hspace{0.05cm}.$$
* Since in&nbsp; $\rm GF(2)$&nbsp; there is no difference between sum and difference, the polynomial&nbsp; $p_2(x) = x^2 - 1$&nbsp; is also reducible.
+
* Since in&nbsp; $\rm GF(2)$&nbsp; there is no difference between sum and difference,&nbsp; the polynomial&nbsp; $p_2(x) = x^2 - 1$&nbsp; is also reducible.
*The polynomial&nbsp; $p_4(x) = x^2 + x - 2$ is&nbsp; unsuitable for&nbsp; $\rm GF(2)$&nbsp; alone, since not all polynomial coefficients are $0$ or $1$.  
+
 
*The "$2$" would only be possible in the Galois field $\rm GF(3)$.
+
*The polynomial&nbsp; $p_4(x) = x^2 + x - 2$&nbsp; is&nbsp; unsuitable for&nbsp; $\rm GF(2)$&nbsp; alone,&nbsp; since not all polynomial coefficients are&nbsp; $0$&nbsp; or&nbsp; $1$.&nbsp; The&nbsp; "$2$"&nbsp; would only be possible in the Galois field&nbsp; $\rm GF(3)$.
 +
 
 +
 
  
  
 +
'''(3)'''&nbsp; Correct are the&nbsp; <u>last three proposed solutions</u>:
 +
* The set&nbsp; $\mathcal{N}$&nbsp; is not a field,&nbsp; since already the subtraction is not allowed for all elements,&nbsp; for example&nbsp; $2 - 3 = -1 &#8713; \mathcal{N}$.
  
 +
* Also the set&nbsp; $\mathcal{Z}$&nbsp; of integers is not a field,&nbsp; since for example the equation&nbsp; $2 \cdot z = 1$&nbsp; is not to be satisfied for any&nbsp; $z &#8712; \mathcal{N}$.
  
'''(3)'''&nbsp; Correct are the <u>last three proposed solutions</u>:
 
* The set&nbsp; $\mathcal{N}$&nbsp; is not a field, since already the subtraction is not allowed for all elements, for example&nbsp; $2 - 3 = -1 &#8713; \mathcal{N}$.
 
* Also the set&nbsp; $\mathcal{Z}$&nbsp; of integers is not a field, since for example the equation&nbsp; $2 \cdot z = 1$&nbsp; is not to be satisfied for any&nbsp; $z &#8712; \mathcal{N}$&nbsp;.
 
  
  
  
 +
'''(4)'''&nbsp; Correct are&nbsp; <u>the answers 1 and 3</u>:
 +
* It is&nbsp; $\mathcal{Q} &#8834; \mathcal{R}$&nbsp; (rational numbers are a subset of real numbers)&nbsp; and&nbsp; $\mathcal{R} &#8834; \mathcal{C}$&nbsp; (real numbers are a subset of the complex numbers).
  
'''(4)'''&nbsp; Correct are <u>answers 1 and 3</u>:
+
*Thus also&nbsp; $\mathcal{Q} &#8834; \mathcal{C}$.  
* It is $\mathcal{Q} &#8834; \mathcal{R}$ (rational numbers are a subset of real numbers) and $\mathcal{R} &#8834; \mathcal{C}$ (real numbers are a subset of the complex numbers).
+
*For finite fields,&nbsp; ${\rm GF}(2^m) &#8834; {\rm GF}(2^M)$&nbsp; means that&nbsp; $m < M$&nbsp; must hold.
*Thus also $\mathcal{Q} &#8834; \mathcal{C}$.  
 
*For finite fields, ${\rm GF}(2^m) &#8834; {\rm GF}(2^M)$ means that $m < M$ must hold.
 
  
  
  
  
'''(5)'''&nbsp; Correct is the <u>proposed solution 2</u>:
+
'''(5)'''&nbsp; Correct is only the&nbsp; <u>proposed solution 2</u>:
* The set&nbsp; $\mathcal{C}$&nbsp; of complex numbers is an extension of the real numbers&nbsp; $(\mathcal{R})$&nbsp; into a second dimension. For this can be written:
+
* The set&nbsp; $\mathcal{C}$&nbsp; of complex numbers is an extension of the real numbers&nbsp; $(\mathcal{R})$&nbsp; into a second dimension.&nbsp; 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}.$$
 
:$$\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)$&nbsp; is an extension of the finite field&nbsp; $\rm GF(2) = \{0, \, 1\}$&nbsp; into a second dimension:
 
* $\rm GF(2^2)$&nbsp; is an extension of the finite field&nbsp; $\rm GF(2) = \{0, \, 1\}$&nbsp; 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}.$$
 
:$${\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&nbsp; ${\rm j} &#8713; \mathcal{C}$&nbsp; results as the solution of the equation&nbsp; ${\rm j}^2 + 1 = 0$, while the new element of&nbsp; $\rm GF(2^2)$&nbsp; is denoted by&nbsp; $\alpha &#8713; \rm GF(2)$&nbsp; and follows from the equation&nbsp; $\alpha^2 + \alpha + 1 = 0$&nbsp;.
+
*The imaginary unit&nbsp; ${\rm j} &#8713; \mathcal{C}$&nbsp; results as the solution of the equation &nbsp; ${\rm j}^2 + 1 = 0$,&nbsp; while the new element of&nbsp; $\rm GF(2^2)$&nbsp; is denoted by&nbsp; $\alpha &#8713; \rm GF(2)$&nbsp; and follows from the equation &nbsp; $\alpha^2 + \alpha + 1 = 0$.
 
{{ML-Fuß}}
 
{{ML-Fuß}}
  

Latest revision as of 17:25, 3 October 2022

Some pioneers of mathematics

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:

  • 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

1

Which polynomials are irreducible in the real field  $\mathcal{R}$?

$p_1(x) = x^2 + 1$.
$p_2(x) = x^2 - 1$,
$p_3(x) = x^2 + x + 1$,
$p_4(x) = x^2 + x - 2$.

2

Which polynomials are irreducible in  $\rm GF(2)$?

$p_1(x) = x^2 + 1$,
$p_2(x) = x^2 - 1$,
$p_3(x) = x^2 + x + 1$,
$p_4(x) = x^2 + x - 2$.

3

Which sets are fields in the algebraic sense?

the set  $\mathcal{N}$  of natural numbers,
the set  $\mathcal{Z}$  of integers,
the set  $\mathcal{Q}$  of rational numbers,
the set  $\mathcal{R}$  of real numbers,
the set  $\mathcal{C}$  of complex numbers.

4

Which fields are subset (subspace) of another field?

$\mathcal{Q} ⊂ \mathcal{C}$,
$\mathcal{C} ⊂ \mathcal{R}$,
${\rm GF}(2) ⊂ {\rm GF}(2^2)$,
${\rm GF}(2^3) ⊂ {\rm GF}(2^2)$.

5

Which fields have certain analogies?

Set  $\mathcal{Q}$  of rational numbers and  ${\rm GF}(2^2)$,
set  $\mathcal{C}$  of complex numbers and  ${\rm GF}(2^2)$,
set  $\mathcal{C}$  of complex numbers and  ${\rm GF}(2^3)$.


Solution

(1)  In the data section it says accordingly:

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$.