Fields

What is a field?

Rational numbers form a field. This roughly means that the set of natural numbers, along with the operations $+$ and $\times$, is a comprehensive computational system: You can add, multiply, subtract, and divide (except division by 0).

The components of a field:
 A set
 Two operations: \(+\) and \(\times\) with associative, commutative, closure, and distributive (\(\times\) over \(+\)) properties.
 Identity elements: there are elements, denoted 0 and 1, in the set such that 
$𝑎+0=𝑎$, (additive identity)
$𝑎×1=𝑎$, (multiplicative identity)
 Inverse elements: there are −𝑎 and 1/𝑎 such that
$𝑎+(−𝑎)=0$, (additive inverse)
$𝑎×(1/𝑎)=1$, ($𝑎≠0$, multiplicative inverse)

Why do you think the additive inverse is defined in terms of 0, i.e., $a+(-a)=0$, but the multiplicative inverse is defined in terms of 1, i.e., $a\times (1/a)=1$?

Subtraction and division

We can define subtraction and division as follows:

\begin{align*} b-a &=b+(-a), & b/a &= b\times (1/a), \end{align*} where for division we assume $a\neq 0$.

Exponentiation

As a shorthand, for a positive integer $n$ define

\begin{align*} x^n &= \underbrace{x\times x\times \dotsm\times x}_{n\text{ times}}, & x^{-n} &= 1/(x^n). \end{align*}

Additionally, $x^0=1$ for all $x\neq 0$.

Finite Fields

The set of rational numbers is a field but there are also fields that have a finite number of elements. We will present some examples. To clearly distinguish finite field operations, addition and multiplication in finite fields are shown by $\oplus$ and $\otimes$, respectively.

The binary field $\mathbb F_2$

The simplest field is the binary field, called $\mathbb F_2$:

The set : {0,1}
Addition: $\,0\oplus0 = 0,\quad 0\oplus1=1,\quad 1\oplus0=1,\quad 1\oplus1 = 0$.
Multiplication: $0\otimes 0 = 0, \quad 0\otimes 1 = 0, \quad 1\otimes 0 = 0, \quad 1\otimes 1 = 1.$
Subtraction is the same as addition!
Division is the same as multiplication, except that you cannot divide by 0.

We can show the operations as tables:

$\oplus$	0	1
0	0	1
1	1	0

$\otimes$	0	1
0	0	0
1	0	1

If you are familiar with logical operators, then you can see that addition/subtraction in this field are the same as XOR, and multiplication is the same as AND.

Verify that additive and multiplicative identities and inverses exist.

Can you fill the above tables in any other way and still have a field?

The ternary field, $\mathbb F_3$:

The set: {0,1,2}
Addition: $\qquad 𝑎\oplus 𝑏 = \text{ remainder of normal addition by 3}$
Multiplication: $\ 𝑎\otimes 𝑏= \text{ remainder of normal multiplication by 3}$
Define $\quad 𝑎/𝑏=𝑎\otimes(1/𝑏)\quad$ and $\quad 𝑎−𝑏=𝑎\oplus (−𝑏)$

Addition in $$GF(3)$$
$\oplus $	0	1	2
0	0	1	2
1	1	2	0
2	2	0	1

$\otimes$	1	2
0	0	0
1	1	2
2	2	1

These are also called addition and multiplication modulo 3.

Find the identity elements.

Find the inverse of each element.

$-0$ = 0 $\qquad-1$ = 2 $\qquad-2$ = 1 $\qquad$

$1/1$ = 1 $\qquad1/2$ = 2 $\qquad$

Does the set {0,1,2,3} with $+,\times$ computed modulo 4 form a field? If not, which properties are not satisfied?

Detour: finite fields and data protection

Regardless of its type, you can view the data stored on your hard drive as a number. Let’s use a toy example to see how this data could be protected. Suppose we have hard drives that can stores a number from the set {0,1,2}. We have two such numbers to store, $x_1$ and $x_2$. How can we protect against the failure of one of these drives?

Obviously, we can get two additional hard drives and keep two copies of $x_1$ and two copies of $x_2$. But can we do better, i.e., use fewer drives?

Idea: Add one new hard drive and write $x_3=x_1+x_2$ on it.

But $x_1+x_2$ could be larger than 2, which won’t fit on the third drive. Instead of looking at these numbers as integers, let’s view them as elements of $\mathbb F_3$. Then, we can write $x_3=x_1\oplus x_2$ (modulo 3).

So we have three drives with these values: $\{x_1,x_2,x_3\}$, where $x_3 = x_1\oplus x_2$. Let’s see how we can recover our data if any one drive fails.

If drive 1 fails, then $x_1=x_3\ominus x_2$.
If drive 2 fails, then $x_2 = x_3 \ominus x_1$.
If drive 3 fails, we haven’t lost any data but to protect against future failures, we should store $x_1\oplus x_2$ on a new drive.

Suppose drive 1 has failed but we know $x_2=2,x_3=1$. What was the data on drive 1?

To protect against two failures we let \begin{equation}\label{eq:4D} \begin{cases} x_{3}=x_{1}\oplus x_{2}\\ x_4 = x_{1}\ominus x_{2} \end{cases} \end{equation} Show that if any of two drives fail, we can recover our data.

Why are fields needed? It seems that we only needed the modulo arithmetic and did not really need to be concerned with fields. However, this is not true, as the situation becomes complicated if we are not working with a field.

For instance, modulo 4 operations do not form a field, and using them would fail. To see this, suppose our hard drives could store $\{0,1,2,3\}$. We would then need to do modulo 4 arithmetic. Show that if $x_3=x_4=1$, equations \eqref{eq:4D} have another set of solution in addition to $x_1=1,x_2=0$.

Write down one question that you still have about the material in this section.