The Hamming code, quadratic residue codes, and an exceptional isomorphism

Wildon's Weblog 2021-07-04

As a pleasant way to pass a Sunday afternoon — or at least, more pleasant than flat-hunting in Bristol in a wildly inflated property market — let me offer yet another way to prove the isomorphism $\mathrm{GL}_3(\mathbb{F}_2) \cong \mathrm{PSL}_2(\mathbb{F}_7)$ . An earlier post uses modular representation theory to do in about a screenful of WordPress. Here we do it using the well known result that, up to position permutation, there is a unique perfect $1$ -error correcting linear binary code of length $7$ .

The Hamming code

We define the $[7,4,3]$ –Hamming code $C$ to be the linear code of length $7$ and dimension $4$ with parity check matrix

$H = \left( \begin{matrix} 1 & 0 & 1 & 0 & 1 & 0 & 1 \\ 0 & 1 & 1 & 0 & 0 & 1 & 1 \\ 0 & 0 & 0 & 1 & 1 & 1 &o 1 \end{matrix} \right).$

Since each non-zero binary word of length $3$ appears exactly once as a column of $H$, the syndromes for the $7$ possible one bit errors, namely

$H(1,0,0,0,0,0,0)^t, \ldots, H(0,0,0,0,0,0,1)^t$

are distinct. Hence $C$ is $1$-error correcting, and therefore has minimum distance $\ge 3$ . Since the disjoint Hamming balls of radius $1$ about the codewords each contain $1 + \binom{7}{1} = 8$ binary words of length $7$ , and $8 \times 2^4 = 2^7 = |\mathbb{F}_2^7|$ , these balls partition $\mathbb{F}_2^7$ and $C$ is a perfect $1$ -error correcting linear binary code.

Lemma. The automorphism group of $C$ is a subgroup of $S_7$ containing $\mathrm{GL}_3(\mathbb{F}_2)$.

Proof. Each $g \in \mathrm{GL}_3(\mathbb{F}_2)$ permutes the $7$ non-zero elements of $\mathbb{F}_2^3$ . Let $\sigma_g \in S_7$ be the position permutation of the columns of $H$ induced by $g$ . For example,

$g = \left( \begin{matrix} 0 & 0 & 1 \\ 1 & 0 & 0 \\ 0 & 1 & 0 \end{matrix} \right) \implies gH = \left( \begin{matrix} 0 & 0 & 0 & 1 & 1 & 1 & 1 \\ 1 & 0 & 1 & 0 & 1 & 0 & 1 \\ 0 &th 1 & 1 & 0 &0 & 1 & 1 \end{matrix} \right)$

and so in this case $\sigma_g = (1,4,2)(3,5,6)$ . Observe that $v gH = 0 \iff v \sigma_g H = 0$ , where $\sigma_g$ acts on the right on $v$ by position permutation. For instance, in the example above, $(1,1,1,0,0,0,0)gH = 0$ and correspondingly, $(1,1,1,0,0,0,0)\sigma_g = (1,0,0,1,1,0,0)$ is a codeword in $C$. Since the group homomorphism $g \mapsto \sigma_g$ is injective, the lemma follows. $\Box$.

Quadratic residue codes

We may construct $\mathbb{F}_{2^3}$ as $\mathbb{F}_2(\alpha)$ where $\alpha$ has minimal polynomial $x^3 + x + 1$. The binary quadratic residue code of length $7$ is the cyclic code $D$ whose generator polynomial has as its roots the powers of $\alpha$ corresponding to the $3$ quadratic residues modulo $7$ , namely $1$ , $2$ and $4$ . That is, $g(x) = (x-\alpha)(x-\alpha^2)(x-\alpha^4)$ . Since these roots are conjugate under the Frobenius automorphism $\beta \mapsto \beta^2$ of $\mathbb{F}_{2^3}$, the generator polynomial is the minimum polynomial of $\alpha$ ; that is $g(x) = x^3 + x + 1$. Thinking of $D$ as the ideal $\langle x^3+x+1 \rangle$ of $\mathbb{F}_2[x]/\langle x^7+1 \rangle$ , we have $c(x) \in C$ if and only if $c(\alpha) = c(\alpha^2) = c(\alpha^4) = 0$ . From this it is easy to see that $D$ has minimum weight $3$ so, as before, $D$ is a perfect $1$ -error correcting binary code. (More generally, in a quadratic residue code of odd prime length $n$ , the minimum distance $d$ satisfies $d^2 \ge n$ .) The same argument holds for the cyclic code $E = \langle x^3 + x^2 + 1 \rangle$ whose generator polynomial is $(x-\alpha^3)(x-\alpha^5)(x-\alpha^6)$ , defined using the $3$ non-residues modulo $7$ .

By the uniqueness result mentioned earlier, the codes $C$ , $D$ and $E$ are all equivalent. Fix a bijection $\star : E \rightarrow D$ .

We now identify the positions of $D$ with $\mathbb{F}_7$ . Since $D$ is cyclic, the position permutation $j \mapsto j + 1$ is an automorphism of $D$ . This gives one element of $\mathrm{PSL}_2(\mathbb{F}_7)$ . To obtain the rest, we need the following two claim.

Claim. If $r \in \{1,2,4\}$ then the position permutation $j \mapsto tj$ preserves $D$.

Proof. Thinking of $D$ as an ideal, We have $v(x) \in D$ if and only if $v(\alpha) = v(\alpha^2) = v(\alpha^4) = 0$ , so if and only if $v(x^2) \in D$ . This deals with the case $r=2$ , and $r=4$ is obtained by squaring. $\Box$ .

Claim. If $s \in \{3,5,6\}$ then the position permutation $j \mapsto tj$ sends $D$ to $E$. The position permutation $0 \mapsto 0$ and $t \mapsto t^{-1}$ sends $D$ to $E$.

Proof. For the first part, use that the generator polynomial for $E$ is defined using the $3$ non-residues modulo $7$. The second part follows similarly, since $\beta$ is a root of $x^3 + x + 1$ if and only if $\beta^{-1}$ is a root of $x^3 + x^2 + 1$. $\Box$

We may therefore define an action of $\mathrm{PSL}_2(\mathbb{F}_7)$ on $D$ by identifying the positions of codewords with $\mathbb{F}_7$ and then applying the corresponding position permutation, followed by $\star$ if (according to the second claim above), we end in $E$ rather than in $D$ . Using that $\mathrm{PSL}_2(\mathbb{F}_7)$ is a simple group, we see this homomorphism is injective.

Conclusion.

We have shown that the automorphism group, $G$ say, of a perfect $1$ -error correcting linear binary code contains subgroups $S$ and $T$ isomorphic to the finite simple groups $\mathrm{GL}_3(\mathbb{F}_2)$ and $\mathrm{PSL}_2(\mathbb{F}_7)$ of order $168$ . Setting $H = S \cap T$ we have $|G| \ge 168^2 / |H|$ . Since $G \le S_7$ , and $168 = 2^3 . 3 .7$ and $7! = 2^4.3^2. 5.7$, we have $|H| \ge 2^2 . 7 = 28$ . Hence $H$ has index at most $6$ in $S$ . The coset action of $S$ on $H$ now gives a homomorphism $S \rightarrow S_6$ ; since $\mathrm{GL}_3(\mathbb{F}_2)$ is simple and has elements of order $7$ , this homomorphism must be trivial. Therefore $H = S$ . Similarly $H = T$ . Hence $S = T$ and we have the required automorphism.