PS04--ECC.md

---

title: |
 ProblemSet 4 -- Finite fields and codes
author: George McNinch
date: due 2024-03-01

---

\newcommand{\F}{\mathbb{F}} \newcommand{\trivial}{\mathbf{1}}

\newcommand{\GL}{\operatorname{GL}}

\newcommand{\PP}{\mathbb{P}}

1. Find the irreducible factors of the polynomial $T^9 - 1$ in ParseError: KaTeX parse error: Undefined control sequence: \F at position 1: \̲F̲_7[T].

   (You should include proofs that the factors you describe are irreducible).

2. Let $0 < k,m \in \mathbb{N}$, put $n =mk$, and consider the subspace ParseError: KaTeX parse error: Undefined control sequence: \F at position 11: C \subset \̲F̲_q^n defined by ParseError: KaTeX parse error: Undefined control sequence: \F at position 35: …v ) \mid v \in \̲F̲_q^k\} \subset … Find the minimal distance $d$ of this code.

   For example, if $n = 6$, $k=3$ and $m = 2$ then ParseError: KaTeX parse error: Undefined control sequence: \F at position 46: …) \mid a_i \in \̲F̲_q\} \subset \F…

   (Corrected)

3. By an $[n,k,d]_q$-system we mean a pair $(V,\mathcal{P})$, where $V$ is a finite dimensional vector space over ParseError: KaTeX parse error: Undefined control sequence: \F at position 1: \̲F̲_q and $\mathcal{P}$ is an ordered finite family $$\mathcal{P} = (P_1,P_2,\cdots,P_n)$$ of points in $V$ (in general, points of $\mathcal{P}$ need not be distinct -- you should view $\mathcal{P}$ as a list of points which may contain repetitions) such that $\mathcal{P}$ spans $V$ as a vector space. Evidently $|\mathcal{P}| \ge \dim V$.

   The parameters $[n,k,d]$ are defined by $$n = |\mathcal{P}|, \quad k = \dim V, \quad d = n - \max_H |\mathcal{P} \cap H|.$$ where the maximum defining $d$ is taken over all linear hyperplanes $H \subset V$ and where points are counted with their multiplicity -- i.e. $|\mathcal{P} \cap H| = |\{i \mid P_i \in H \}|$.

   Gjven a $[n,k,d]_q$-system $(V,\mathcal{P})$, let $V^*$ denote the dual space to $V$ and consider the linear mapping ParseError: KaTeX parse error: Undefined control sequence: \F at position 14: \Phi:V^* \to \̲F̲_q^n defined by $$\Phi(\psi) = (\psi(P_1),\cdots,\psi(P_n)).$$

   a. Show that $\Phi$ is injective.

   b. Write $C = \Phi(V^*)$ for the image of $\Phi$, so that $C$ is an $[n,k]_q$-code. Show that the minimal distance of the code $C$ is given by $d$.

   c. Conversely, let ParseError: KaTeX parse error: Undefined control sequence: \F at position 11: C \subset \̲F̲_q^n be an $[n,k,d]_q$-code, and put $V = C^*$. Let ParseError: KaTeX parse error: Undefined control sequence: \F at position 21: …cdots,e^n \in (\̲F̲_q^n)^* be the dual basis to the standard basis. The restriction of $e^i$ to the subspace $C$ determines an element $P_i$ of $C^* = V$. Write $\mathcal{P} = (P_1,P_2,\cdots,P_n)$ for the resulting list of vectors in $V$..

   Prove that the minimum distance $d$ of the code $C$ satisfies $$d = n - \max_H | \mathcal{P} \cap H |.$$

4. Let $C$ be the linear code over ParseError: KaTeX parse error: Undefined control sequence: \F at position 1: \̲F̲_5 generated by the matrix $$G = \begin{pmatrix} 1 & 0 & 0 & 1 & 1 & 2 \\ 0 & 1 & 0 & 1 & 2 & 1 \\ 0 & 0 & 1 & 2 & 1 & 1 \end{pmatrix}.$$

   a. Find a check matrix $H$ for $C$.

   b. Find the minimum distance of $C$.

   c. Decode the received vectors $(0,2,3,4,3,2)$ and $(0,1,2,0,4,0)$ using syndrome decoding.