NoteNextra-origin/content/CSE5313/CSE5313_L4.md

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) 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).
  • 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) 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:

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

Important

1. Operator \cdot is not necessarily commutative. (if so then it's called an abelian group)
2. May not be finite/infinite.
3. 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\}.