Math190-Tufts University - ProblemSet 4 -- Finite field projective spaces **Solutions**

Find the irreducible factors of the polynomial $T^{9} - 1$ in $F_{7} [T]$ .

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

Note that the multiplicative group $F_{7}^{\times}$ has order 6 and hence contains an element of order 3; in fact, $2$ has order 3 since $2^{3} = 8 \equiv 1 (\mod 7)$ .

Now, $F_{7^{2}}^{\times}$ has order $49 - 1 = 48$ which is not divisible by 9. And $F_{7^{3}}^{\times}$ has order $7^{3} - 1 \equiv (- 2)^{3} - 1 \equiv - 9 \equiv 0 (\mod 9)$ . So $F_{7^{3}}^{\times}$ has an element of order $9$ .

Consider the polynomial $T^{3} - 2$ . Any root $α$ of this polynomial satisfies $α^{3} = 2$ and $α^{9} = 1$ ; this shows that the multiplicative order of $α$ is 9.

In particular, $F_{7}$ contains no roots of $f (T) = T^{3} - 2$ ; since $f (T)$ has degree 3, it is irreducible over $F_{7}$ .

If $α$ is a root of $f (T)$ , then $α^{7}$ and $α^{7^{2}} = α^{4}$ are also roots (note that $7^{2} \equiv (- 2)^{2} = 4 (\mod 9)$ ). Thus $f (T) = (T - α) (T - α^{7}) (T - α^{4})$ and $f (T) ∣ T^{9} - 1.$

Notice that $F_{7^{3}}$ is a splitting field for $f (T)$ over $F_{7}$ .

Note that $2^{2} = 4$ is also an element of $F_{7}^{\times}$ of order $3$ . Arguing as before, any root of $T^{3} - 4$ is an element of multiplicative order $9$ .

On the other hand, since $gcd (2, 9) = 1$ , $α^{2} \in F_{7^{3}}$ is also an element of order 9.

Moreover, the roots of its minimal polynomial $g (T)$ have the form $α^{2}$ , $α^{2 \cdot 7} = α^{5}$ (since $14 \equiv 5 (\mod 9)$ ), and $α^{2 \cdot 7^{2}} = α^{5 \cdot 7} = α^{3}$ (since $2 \cdot 7^{2} \equiv 8 (\mod 9)$ .

Thus $g (T) = (T - α^{2}) (T - α^{5}) (T - α^{8}) .$

Now, notice that $(α^{2})^{3} = (α^{3})^{2} = 2^{2} = 4 \in F_{7}$ . Thus the minimal polynomial $g (T)$ of $α^{2}$ divides $T^{3} - 4$ . It follows that $g (T) = T^{3} - 4 = (T - α^{2}) (T - α^{5}) (T - α^{8}) .$

Now, $g (T) ∣ T^{9} - 1$ and since $gcd (f (T), g (T)) = 1$ we see that $f (T) g (T) ∣ T^{9} - 1$ . Thus $T^{9} - 1 = f (T) \cdot g (T) \cdot (T - 1) \cdot (T - 2) \cdot (T - 4) .$
Let $0 < k, m \in N$ , put $n = m k$ , and consider the subspace $C \subset F_{q}^{n}$ defined by $C = {(v, v, \dots, v) ∣ v \in F_{q}^{k}} \subset F_{q}^{n} .$ Find the minimal distance $d$ of this code.

For example, if $n = 6$ , $k = 3$ and $m = 2$ then $C = {(a_{1}, a_{2}, a_{3}, a_{1}, a_{2}, a_{3}) ∣ a_{i} \in F_{q}} \subset F_{q}^{6} .$

(Corrected)

If $v = (v, v, \dots, v) \in C$ for $v \in F_{q}^{n}$ , note that $weight (v) = m \cdot weight (v)$ .

In particular, for a non-zero vector we see that $weight (v) \geq m$ .

On the other hand, a standard basis vector $v = e_{i} \in F_{q}^{n}$ has weight 1, so if $w = (e_{i}, e_{i}, \dots, e_{i})$ , then $weight (w) = m$ .

Thus $min {weight (v) ∣ 0 \neq v \in C} = m .$

For a linear code, the minimal distance is simply the minimal weight of a non-zero vector; thus the minimal distance of $C$ is $m$ .
By an $[n, k, d]_{q}$ -system we mean a pair $(V, P)$ , where $V$ is a finite dimensional vector space over $F_{q}$ and $P$ is an ordered finite family $P = (P_{1}, P_{2}, \dots, P_{n})$ of points in $V$ (in general, points of $P$ need not be distinct – you should view $P$ as a list of points which may contain repetitions) such that $P$ spans $V$ as a vector space. Evidently $| P | \geq \dim V$ .

The parameters $[n, k, d]$ are defined by $n = | P |, k = \dim V, d = n - max_{H} | 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. $| P \cap H | = | {i ∣ P_{i} \in H} |$ .

Gjven a $[n, k, d]_{q}$ -system $(V, P)$ , let $V^{*}$ denote the dual space to $V$ and consider the linear mapping $Φ : V^{*} \to F_{q}^{n}$ defined by $Φ (ψ) = (ψ (P_{1}), \dots, ψ (P_{n})) .$
1. Show that $Φ$ is injective.
  
  $Φ$ is a linear mapping, so we just need to show that $\ker Φ = {0}$ .
  
  Suppose that $ψ \in V^{*}$ and $Φ (ψ) = 0$ . This means that $ψ (P_{j}) = 0$ for $1 \leq j \leq n$ . Since $ψ$ is linear, it follows that $ψ$ vanishes at any linear combination of the vectors ${P_{j}}$ .
  
  Since $P$ spans $V$ by assumption, it follows that $ψ = 0$ . This proves that $Φ$ is injective.
2. Write $C = Φ (V^{*})$ for the image of $Φ$ , so that $C$ is an $[n, k]_{q}$ -code. Show that the minimal distance of the code $C$ is given by $d$ .
  
  Write $d^{'}$ for the minimal weight of $C$ ; we must argue that $d^{'} = d = n - max_{H} | P \cap H | .$
  
  Let $v = Φ (ψ) \in C$ be a non-zero vector. We have $weight (v) = | {j ∣ ψ (P_{j}) \neq 0} | .$
  
  Write $H = \ker ψ$ and note that $| P \cap H | = | {j ∣ ψ (P_{j}) = 0} | .$
  
  Thus $(*) weight (v) = n - | P \cap H | .$
  
  In $max_{H} | P \cap H |$ the hyperplanes $H$ are precisely the kernels $H = \ker ψ$ of functionals $0 \neq ψ \in V^{*}$ . Thus $(*)$ shows that $min_{v = Φ (ψ) \neq 0} weight (v) = n - max_{H = \ker ψ, ψ \neq 0} | P \cap H |;$ it follows that $d^{'} = d$ .
3. Conversely, let $C \subset F_{q}^{n}$ be an $[n, k, d]_{q}$ -code, and put $V = C^{*}$ . Let $e^{1}, \dots, 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 $P = (P_{1}, P_{2}, \dots, 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} | P \cap H | .$
  
  We have $V^{*} = (C^{*})^{*} = C$ ; the mapping $Φ : V^{*} = C \to F_{q}^{n}$ is just the given inclusion. Indeed, let $x = (x_{1}, x_{2}, \dots, x_{n}) \in C \subset F_{q}^{n}$ . The mapping $Φ : V^{*} \to F_{q}^{n}$ is given by $Φ (x) = (e^{1} (x), \dots, e^{n} (x)) = (x_{1}, \dots, x_{n}) .$
  
  Now the equality $d = n - max_{H} | P \cap H |$ follows from the result of part (b).

Let $C$ be the linear code over $F_{5}$ generated by the matrix $G = (\begin{matrix} 1 & 0 & 0 & 1 & 1 & 2 \\ 0 & 1 & 0 & 1 & 2 & 1 \\ 0 & 0 & 1 & 2 & 1 & 1 \end{matrix}) .$

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

k = GF(5)
V = VectorSpace(k,6)

C =V.subspace([ V([1,0,0,1,1,2]),
                V([0,1,0,1,2,1]),
                V([0,0,1,2,1,1])])

# generator matrix, in standard form
G = MatrixSpace(k,3,6).matrix(C.basis())
G
=> 
[1 0 0 1 1 2]
[0 1 0 1 2 1]
[0 0 1 2 1 1]

A = MatrixSpace(k,3,3).matrix([b[3:6] for b in G])

# construct the check matrix, as a block matrix
H = block_matrix([[-A.transpose(),
                   MatrixSpace(k,3,3).one()]],
               subdivide=False)        

H
=>
[4 4 3 1 0 0]
[4 3 4 0 1 0]
[3 4 4 0 0 1]

## verification:
H * G.T
=>
[0 0 0]
[0 0 0]
[0 0 0]

Find the minimum distance of $C$ .

The minimal distance of $C$ is 4.

We check the weight of a vector using the following function:

def weight(v):
    r = [x for x in v if x != 0]
    return len(r)

Now, we can just find the minimal weight of the non-zero vectors of $V$ , as follows:

min([ weight(v) for v in C if v != 0])
=>
4

Alternatively, you can investigate the columns of the check matrix $H$ .

W = VectorSpace(k,3)  # column space

# return the ith column of the 3xm matrix M
def col(M,i):
    return W([ b[i] for b in M ])

# check whether the columns of the 3xm matrix M 
# specified by the list ll of indices are lin indep
def cols_lin_indep(M,ll):
    vecs =  [ col(M,i) for i in ll ]

   # the method `linear_dependence` returns a list 
   # of *linear relations*

   # so we return True if `W.linear_dependence(vecs)` is 
   # the empty list

    return W.linear_dependence(vecs) == []

# check whether all collections of r columns of the 
# 3xm matrix M are linearly independent
def check(M,r):
    # get the number of columns of M.
    l = len(list(M.T))

   # get all lists of r-element subses of the numbers 0,...,l-1
    al = map(list,Subsets(range(l),r))

   # return True iff `cols_lin_indep(M,ll)` is true for every 
   # r-element subset ll of range(l)
    return all([ cols_lin_indep(M,ll) for ll in al])

check(H,3)
=>
True

check(H,4)
=>
False

This shows that every collection of 3 columns of H is linearly independent, while there is some collection of 4 columns of H that is linearly dependent; thus $d = 4$ .

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

The minimal distance of the code $C$ is $4$ , so we should expect to correct $⌊ (4 - 1) / 2 ⌋ = ⌊ 3 / 2 ⌋ = 1$ error.

We first make the lookup table

lookup = { tuple(H*v):v for v in V if weight(v) <= 1 }
lookup
=>
{(0, 0, 0): (0, 0, 0, 0, 0, 0),
 (4, 4, 3): (1, 0, 0, 0, 0, 0),
 (3, 3, 1): (2, 0, 0, 0, 0, 0),
 (2, 2, 4): (3, 0, 0, 0, 0, 0),
 (1, 1, 2): (4, 0, 0, 0, 0, 0),
 (4, 3, 4): (0, 1, 0, 0, 0, 0),
 (3, 1, 3): (0, 2, 0, 0, 0, 0),
 (2, 4, 2): (0, 3, 0, 0, 0, 0),
 (1, 2, 1): (0, 4, 0, 0, 0, 0),
 (3, 4, 4): (0, 0, 1, 0, 0, 0),
 (1, 3, 3): (0, 0, 2, 0, 0, 0),
 (4, 2, 2): (0, 0, 3, 0, 0, 0),
 (2, 1, 1): (0, 0, 4, 0, 0, 0),
 (1, 0, 0): (0, 0, 0, 1, 0, 0),
 (2, 0, 0): (0, 0, 0, 2, 0, 0),
 (3, 0, 0): (0, 0, 0, 3, 0, 0),
 (4, 0, 0): (0, 0, 0, 4, 0, 0),
 (0, 1, 0): (0, 0, 0, 0, 1, 0),
 (0, 2, 0): (0, 0, 0, 0, 2, 0),
 (0, 3, 0): (0, 0, 0, 0, 3, 0),
 (0, 4, 0): (0, 0, 0, 0, 4, 0),
 (0, 0, 1): (0, 0, 0, 0, 0, 1),
 (0, 0, 2): (0, 0, 0, 0, 0, 2),
 (0, 0, 3): (0, 0, 0, 0, 0, 3),
 (0, 0, 4): (0, 0, 0, 0, 0, 4)}

Now we can decode using the lookup table

def decode(v):
  return v-lookup[tuple(H*v)]

[ (decode(v), decode(v) in C) for v in [ V([0,2,3,4,3,2]),
                                         V([0,1,2,0,4,0])]]
=>
[((1, 2, 3, 4, 3, 2), True), ((0, 1, 2, 0, 4, 3), True)]