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

Algebra over finite fields

$\mathbb{N}$ is the set of natural numbers.

by adding additive inverse, we can define the set of integers $\mathbb{Z}$ .

by adding multiplicative inverse, we can define the set of rational numbers $\mathbb{Q}$ .

by adding limits, we can define the set of real numbers $\mathbb{R}$ .

by adding polynomial roots, we can define the set of complex numbers $\mathbb{C}$ .

Another two extensions $\mathbb{H}$ for quaternions and $\mathbb{O}$ for octonions.

Few theorems about extension of fields

As long as it is irreducible, the choice of $f(x)$ $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$ ( $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.

Common notations

$\mathbb{F}_q$ is the finite field with $q$ elements. where $q$ is a prime power.

$\mathbb{F}_q^t$ is a vector field of dimension $t$ over $\mathbb{F}_q$ . (no notion of multiplication)

$\mathbb{F}_{q^t}$ is the finite field with $q^t$ elements. (as extension field of $\mathbb{F}_q$ )

$\mathbb{F}_{q^t}\Rightarrow \mathbb{F}_q^t$ . Every extension field of $\mathbb{F}_q$ is a vector field over $\mathbb{F}_q$ .

$\mathbb{F}_q^t\nRightarrow \mathbb{F}_{q^t}$ . Additional structure is required.

Important

From now on, we will use $+,\cdot$ to denote the modulo operations $\oplus,\odot$ .

Few exercises

Let $F$ be a field and $\alpha(x)\in F[x]$ . Prove that for $\beta\in F$ , show $\alpha(\beta)=0\iff (x-\beta)\mid \alpha(x)$ .

Proof

$\implies$ :

Suppose $x-\beta\mid \alpha(x)$ , then $\alpha(x)=(x-\beta)q(x)$ for some $q(x)\in F[x]$ .

Thus, $\alpha(\beta)=(\beta-\beta)q(\beta)=0$ .

$\impliedby$ :

We proceed by induction over $\deg(\alpha(x))$ .

Base case: $\deg(\alpha(x))=1$ , then $\alpha(x)=\alpha_0+\alpha_1x$ for some $\alpha_0,\alpha_1\in F$ . Then $\alpha(\beta)=\alpha_0+\alpha_1\beta=0\iff \alpha_1\beta$ . So $\alpha_0=-\alpha_1\beta$ .

So $\alpha(x)=\alpha_1 x-\alpha_1\beta=\alpha_1 (x-\beta)$ .

Inductive step: Suppose $\deg(\alpha(x))>1$ , and the condition holds for all polynomials $r(x)$ with $\deg(r(x))<\deg(\alpha(x))$ .

Then $a(x)=(x-\beta)q(x)+r(x)$ for some $q(x),r(x)\in F[x]$ with $\deg(r(x))<1$ (By euclid’s division algorithm).

By our inductive hypothesis, $r(x)=0\iff (x-\beta)\mid r(x)$ .

So $\alpha(x)=(x-\beta)q(x)+r(x)=0\iff (x-\beta)\mid \alpha(x)$ .

Let $F$ be a field and $a(x)\in F[x]$ . Prove that for $\beta\in F$ , show $a(\beta)=0\iff f(x)\mid a(x)$ .

Solution

$9=3^2$

We extend $\mathbb{Z}_3=\mathbb{F}_3$ to $\mathbb{F}_{3^2}$ .

We extend this by using an irreducible polynomial of degree 2.

Need to find an irreducible polynomial $f(x)=x^2+\alpha\in \mathbb{F}_3[x]$ .

Tip

In $\mathbb{F}_3$ , $\forall x\in \mathbb{F}_3$ , $x^2\neq 2$ . So $f(x)=x^2+1$ has no root in $\mathbb{F}_3$ .

Consider $f(x)=x^2-2=x^2+1$ .

Suppose for contradiction that $f(x)$ is reducible, then $f(x)=a(x)b(x)$ for some $a(x),b(x)\in \mathbb{F}_3[x]$ . And $a(x),b(x)$ are both of degree 1.

So $f(x)=(\alpha_1 x-a_2)(\beta_1 x-\beta_2)$ for some $\alpha_1,\alpha_2,\beta_1,\beta_2\in \mathbb{F}_3$ , and $\alpha_1\beta_1\neq 0$ .

So $f(\frac{a_2}{a_1})=0$

This contradicts the fact that $f(x)$ has no root in $\mathbb{F}_3$ .

Summary from last lecture

A recipe for constructing a field $\mathbb{F}$ with $p^t$ elements ( $p$ prime).

Construct $\mathbb{Z}_p$ .
Find an irreducible polynomial $f(x)$ of degree $t$ (always exists).
Let $\mathbb{F} = \mathbb{Z}_p[x] \mod f(x)$ $F = Z_{p} [x] mod f (x)$ .
- The elements: polynomials in $\mathbb{Z}_p[x]$ of degree at most $t-1$ .
- Addition and multiplication $\mod f(x)$ .

Facts:

Choice of $f(x)$ $f (x)$ does not matter.
- Always end up with isomorphic $\mathbb{F}$ (identical up to renaming of elements).
- All finite fields are of size $p^t$ for prime $p$ and some $t$ .
The above recipe is unique.
The above recipe is unique.

Algebra over finite fields

Groups

A group is a set $G$ with an operation $\cdot$ that satisfies the following axioms:

Closure: $\forall a,b\in G, a\cdot b\in G$ .
Associativity: $\forall a,b,c\in G, (a\cdot b)\cdot c=a\cdot (b\cdot c)$ .
Identity: $\exists e\in G, \forall a\in G, a\cdot e=e\cdot a=a$ .
Inverses: $\forall a\in G, \exists a^{-1}\in G, a\cdot a^{-1}=a^{-1}\cdot a=e$ .

Important

Operator $\cdot$ is not necessarily commutative. (if so then it’s called an abelian group)
May not be finite/infinite.
May represented in power notation $a^n=a^{n-1}\cdot a$ .

Examples of groups

$(\mathbb{Z},+)$ is an abelian group. $(\mathbb{Q},+)$ is an abelian group.

$(\{\mathbb{R}\setminus\{0\},\cdot\})$ is an abelian group.

Let $\mathbb{Z}_n^*=\{x\in \mathbb{Z}_n:gcd(x,n)=1\}$ .

Then $(\mathbb{Z}_n^*,\cdot)$ is a group. If $n$ is prime, then $\mathbb{Z}_n^*$ only need to remove $0$ .

Order of element in group

Let $(G,\cdot)$ be a finite group.

Then there exists $k\in\mathbb{N}$ such that $a^k=e$ .

Proof

Consider the sequence $a,a^2,a^3,\cdots$ .

Since $G$ is finite, there exists $i,j\in\mathbb{N}$ such that $a^i=a^j$ .

Then $a^i=a^j\iff a^{i-j}=e$ .

So there exists $k=i-j\in\mathbb{N}$ such that $a^k=e$ .

The order of an element $a\in G$ (denoted as $\mathcal{O}(a)$ ) is the smallest positive integer $n$ such that $a^n=e$ .

Examples:

order of $5$ in $(\mathbb{Z}_6,+)$ is $6$ .

If $a^l=e$ , then $\mathcal{O}(a)\mid l$ .

Proof

Let $\mathcal{O}(a)=m$ , then if $a^l=e$ , then by definition of order, $l\geq m$ . So $\exists q,r\in\mathbb{N}$ such that $l=qm+r$ and $r<m$ .

So $a^l=a^{qm+r}=a^r=e$ . This contradicts the definition of order. That $l$ is the smallest positive integer such that $a^l=e$ .

Cyclic groups

A group $G$ is called cyclic if there exists $a\in G$ such that $\mathcal{O}(a)=|G|$ .

$G=\{a^i|i\in\mathbb{Z}\}$

one element is a generator of the group.

Exercises for cyclic groups

Is $(\mathbb{Z}_n,+)$ cyclic? If so, find a generator.

Solution

Yes, the generator is $\{a|a\in \mathbb{Z}_n,gcd(a,n)=1\}$ .