CSE5313 Coding and information theory for data science (Lecture 3)

Finite Fields

Why finite fields?

Most information systems are discrete.

• Use bits, byte etc.

Use bits/bytes to represent real numbers.

• Problems of overflow, accuracy, etc.

We wish to build “good” codes $\mathcal{C} \subset \mathbb{F}^n$:

• Large $\frac{k}{n}$
• Lage $d_H(\mathcal{C})\implies$ error detection/correction, erasure correction.

Idea: Use linear algebraic operations to encode/decode.

• $F=\mathbb{F}_q$, a finite field with $q$ elements.

Finite fields

Fields and field axioms

A field is a set $\mathbb{F}$ with two operations $+$ and $\cdot$ that satisfy the following axioms:

• Associativity: $(a+b)+c = a+(b+c)$ and $(a\cdot b)\cdot c = a\cdot (b\cdot c)$
• Commutativity: $a+b = b+a$ and $a\cdot b = b\cdot a$
• Distributivity: $a\cdot (b+c) = a\cdot b + a\cdot c$
• Existence of Identity elements: $a+0 = a$ and $a\cdot 1 = a$
• Existence of Inverse elements: $a+(-a) = 0$ and $a\cdot a^{-1} = 1$

Every set of elements which satisfies these axioms is a field.

We can “do algebra” over it (matrices, vector spaces, etc.).

Are there finite sets which satisfy the field axioms?

What are the possible sizes of such sets?

Background – Basic number theory

• For $a, b \in \mathbb{N}$,
  • Greatest Common Denominator: $\gcd(a, b) =$ the largest integer $m$ such that $m|a$ and $m|b$.
  • Lowest Common Multiplier: $\operatorname{lcm}(a, b) =$ the smallest integer $m$ such that $a|m$ and $b|m$.
• $a, b$ are coprime if $\gcd(a, b) = 1$.
• Fact: (Euclid’s lemma) Say $a \geq b$,
  • There exists a quotient $q \geq 0$ and a remainder $0 \leq r < b$ such that $a = bq + r$.
• Theorem (Euclid): If $\gcd(a, b) = 1$ then there exist $m, n \in \mathbb{Z}$ such that $am + bn = 1$.
  • Proof by repeated application of Euclid’s lemma.
  • Example:
    • If $a = 3, b = 8$,
    • then $m = -5, n = 2$,
    • satisfy $3 \cdot -5 + 8 \cdot 2 = 1$.

Modular arithmetic

Defined a set with addition $\oplus$ and multiplication $\odot$ that satisfy the field axioms.

$\mathbb{Z}_p$ is a field if $p$ is a prime number.

• Addition and multiplication are defined modulo $p$.

• $a \oplus b = (a+b) \mod p$

• $a \odot b = (a\cdot b) \mod p$

• $0$ is the additive identity.

• $1$ is the multiplicative identity.

• $a$ has an additive inverse $p-a$.

• $a$ has a multiplicative inverse $a^{-1}$ such that $a \odot a^{-1} = 1$.

Proof for existence of multiplicative inverse for $a\in \mathbb{Z}_p\setminus \{0\}$:

Polynomials over prime fields is also a field.

$(\mathbb{Z}_2,\operatorname{XOR},\operatorname{AND})$ is a field.

Polynomials over finite fields

A polynomial over a field $\mathbb{Z}_p$ is a expression of the form:

• Polynomial degree: largest index of a non-zero coefficient.
• Polynomial addition: $a(x) \oplus b(x) = \sum_{i=0}^n (a_i \oplus b_i) x^i$
• Polynomial multiplication: $a(x)\odot b(x) = \sum_{i=0}^n \sum_{j=0}^n a_i \odot b_j x^{i+j}$
• Polynomial equality: $a(x) = b(x)$ if and only if $a_i = b_i$ for all $i$.
• Polynomial division: suppose $\deg(a(x)) \geq \deg(b(x))$, then there exist unique polynomials $q(x)$ and $r(x)$ such that $a(x) = b(x)q(x) \oplus r(x)$ and $\deg(r(x)) < \deg(b(x))$. (do long division for polynomials)

denoted as $\mathbb{Z}_p[x]$.

Irreducible polynomials

A polynomial $p(x)$ is irreducible if it cannot be factored into two non-constant polynomials.

If $\gcd(a(x),b(x))=1$, then there exist $m(x),n(x)\in \mathbb{Z}_p[x]$ such that $a(x)m(x)\oplus b(x)n(x)=1$.

Proved similar to euclid’s theorem.

Example in $\mathbb{Z}_2[x]$:

is reducible because $p(x) = (x\oplus 1)(x\oplus 1)$.

is irreducible.

It is not the case in $\mathbb{Z}_2[x]$, that every polynomial with no root is irreducible. (e.g consider $(x^3\oplus x\oplus 1)^2$ has no root but is reducible.)

Polynomial modular arithmetic

There exist quotient $q(x)$ and remainder $r(x)$, $\deg(r(x)) < \deg(b(x))$ such that

"$\mod b(x)$" is an operation on polynomials in $\mathbb{Z}_p[x]$ that:

• Preserves polynomial addition:
  • $a(x) \oplus c(x) \mod b(x) = a(x) \mod b(x) \oplus c(x) \mod b(x)$
• Preserves polynomial multiplication:
  • $a(x) \odot c(x) \mod b(x) = a(x) \mod b(x) \odot c(x) \mod b(x)$

Extension fields

Let $p$ be a prime number. then $(\mathbb{Z}_p[x], \oplus, \odot)$ is a field.

Fix a polynomial $f(x)\in \mathbb{Z}_p[x]$ of degree $t$.

Define a set

Elements: polynomials of degree at most $t-1$ in $\mathbb{Z}_p[x]$. (finite set, size is $p^t$.)

Define addition:

Define multiplication:

Denote this set as $\mathbb{Z}_p[x] \mod f(x)$.

This is not a field because it does not have a multiplicative inverse for every element.

To make our field extension works, we need to find a polynomial $f(x)$ that is irreducible.

Theorem: If $f(x)$ is irreducible over $\mathbb{Z}_p$, then $\mathbb{Z}_p[x] \mod f(x)$ is a field.

Corollary:

We can extend a prime field $\mathbb{Z}_p$ with irreducible polynomial

Intuitively, we add to $\mathbb{Z}_p$ a new element $x$ that satisfies $f(x)=0$.

Observation: – We only used the general field properties of $\mathbb{Z}_p$. – ⇒ any “base field” can be used instead of $\mathbb{Z}_p$. – ⇒ Any field can be “extended”.

Say we wish to build a field $F$ with $2^8$ elements.

• Option 1:

  • Take $\mathbb{Z}_2$ and $f(x)$ irreducible of degree 8.
  • $F = \mathbb{Z}_2[x] \mod f(x)$.

• Option 2:

  • Take $\mathbb{Z}_2$, and $g_1(x) \in \mathbb{Z}_2[x]$ irreducible of degree 4,
  • $F_1 = \mathbb{Z}_2[x] \mod g_1(x)$. Note $|F_1| = 2^4 = 16$.
  • Take $g_2(x) \in F_1[x]$ irreducible of degree 2.
  • $F_2 = F_1[x] \mod g_2(x)$.

Uniqueness of the finite field

Theorems:

• As long as it is irreducible, the choice of $f(x)$ does not matter.
  • If $f_1(x), f_2(x)$ are irreducible of the same degree, then $\mathbb{Z}_p[x] \mod f_1(x) \cong \mathbb{Z}_p[x] \mod f_2(x)$.
• Over every $\mathbb{Z}_p$ (𝑝 prime), there exists an irreducible polynomial of every degree.
• All finite fields of the same size are isomorphic.
• All finite fields are of size $p^d$ for prime $p$ and integer $d$.

Corollary: This is effectively the only way to construct finite fields!

Extension of fields

$\mathbb{R}[x]\mod (x^2+1)$ is a field, $\cong \mathbb{C}$.

You cannot do algebraic extension of $\mathbb{Q}$ to $\mathbb{R}$.

Transcendental extension: