Motivation
One of the various approaches to the perfect Golay codes is via cyclic codes. From the cyclotomic cosets, one computes the corresponding cyclotomic coset (2 possibilities each) and can use that to derive a concrete generator polynomial, for example $g_{2} = z^{11} + z^9 + z^7 + z^6 + z^5 + z + 1$ for the binary $[23,12]$ Golay code $G_2$ and $g_3 = z^5 + z^4 -z^3 + z^2 -1$ for the ternary $[11,5]$ Golay code $G_3$.
For $G_2$, the minimum distance $d(G_2)$ can be derived as follows from $g_2$:
- There is a sequence of length 4 in the corresponding cyclotomic coset. Thus $d(G_2) \geq 5$ by the BCH bound.
- $d(G_2) \leq 7$ as the codeword given by $g_2$ has weight $7$,
- Starting from $g_2$, we derive a generator matrix in the standard way and append a parity check column. It generates the extended Golay code $\bar{G}_2$. We check that the rows are pairwise orthogonal, using cyclicity to reduce the number of cases. Thus $\bar{G}_2$ is self-orthogonal. Moreover, all rows have the weight $8$ which is divisible by $4$, implying that all the weights of $\bar{G}_2$ are divisible by $4$, so $4\mid d(G_2)$.
With $d(G_2) \geq 5$, this forces $d(\bar{G}_2) \geq 8$ and then $d(G_2) \geq 7$. - So $d(G_2) = 7$.
For $G_3$, a similar reasoning almost works:
- BCH bound gives $d(G_3) \geq 3$. (EDIT. This is wrong, see the answer of Jyrki Lahtonen. The BCH bound actually yields $d(G_3) \geq 4$, making my problem disappear and resolving this question.)
- The weight of $g_3$ gives $d(G_3) \leq 5$.
- Extending $G_3$ by a parity-check symbol gives the extended code $\bar{G}_3$. It is checked to be self-orthogonal and therefore, all weights of $\bar{G}_3$ are divisible by $3$.
- If we can show $d(\bar{G}_3) \geq 6$, we would have $d(G_3) = 5$ as desired.
- The problem is that we have to exclude codewords of weight $3$ in $\bar{G}_3$. Such codewords necessarily have parity-check symbol $0$ and therefore arise from codewords in $G_3$ of weight $3$ whose non-zero entries are either all $1$ or all $2$. So the remaining problem is to exclude such codewords in $G_3$.
My question
So after this fairly long text (I hope people are still following!) my question is:
- Is there a "natural" way to derive the minimum distance $5$ of the ternary Hamming code from its cyclic representation?
- Is there a "natural" way to finish the above argument?
Of course we could enumerate all $3^6 = 729$ codewords, but that is not what I mean by "natural".
Best Answer
The relevant cyclotomic coset has three consecutive entries, so the BCH-bound actually tells us that the minimum distance is at least four. The fact that all weight are multiples of three then allow us to conclude that $d_{min}=6$.
More precisely, the generator polynomial $g(x)\in\Bbb{Z_3}[x]$ of $G_3$ has as its zero a root of unity of order eleven, $\alpha$. By Frobenius, all the powers $\alpha^i$, $i\equiv3^j\pmod{11}$ are the also roots of $g(x)$. As $3^1\equiv 3$, $3^3\equiv 5$ and $3^4\equiv4$ are three consecutive integers, the general BCH-bound (we are not in the more common narrow sense case) gives $d_{min}\ge4$.