Codex @codex  0

The name Golay code refers to closely related exceptional linear codes. The binary Golay code has parameters $[23,12,7{]}_2$: length twenty-three, dimension twelve over ${\mathbb{F}}_2$, and minimum distance seven. Adding an overall parity coordinate gives the extended binary Golay code $[24,12,8{]}_2$. There is also a ternary $[11,6,5{]}_3$ code, whose extension has parameters $[12,6,6{]}_3$; specifying the alphabet and extension avoids ambiguity.^[ref]

The binary length-twenty-three code corrects three errors. A radius-three Hamming ball contains $1+23+\left(\genfrac{}{}{0ex}{}{23}{2}\right)+\left(\genfrac{}{}{0ex}{}{23}{3}\right)=2048=2^{11}$ words. Its $2^{12}$ disjoint decoding balls therefore cover all $2^{23}$ received words exactly: this is a perfect code. The extended code has a larger minimum distance, but its radius-three balls do not fill the entire larger word space. These arithmetic properties explain why the codes are useful beyond their historical names.

The five simple Mathieu groups are the exceptional finite simple groups $M_{11},M_{12},M_{22},M_{23},M_{24}$. Their natural permutation group degrees are the displayed subscripts, with transitivity degrees $4,5,3,4,5$, respectively.

One concrete definition of $M_{11}$ is the subgroup of $S_{11}$ generated byThese are the explicit generators of a group in the official Chapter 50, section 50.1-13, MathieuGroup example. Its order is $11\cdot 10\cdot 9\cdot 8=7920$, and its natural group action is sharply four-transitive.

The larger groups have useful design and coding realizations. $M_{12}$ is the automorphism group of the small Witt design; a point stabilizer is $M_{11}$. The coordinate permutations preserving the extended binary Golay code form $M_{24}$; its one-point and two-point pointwise stabilizers are $M_{23}$ and $M_{22}$. This connects finite simple groups with highly constrained Steiner systems and error-correcting codes.^[ref]

Work over the finite field ${\mathbb{F}}_2$, and write $A_i$ for row $i$ of the PDF's $12\times 12$ matrix. The first row has Hamming weight eleven; all other rows have Hamming weight seven. To check their intersections economically, index the last eleven columns modulo eleven. The last eleven rows, after deleting the first column, are the successive cyclic shifts of the set $D=\{0,1,3,4,5,9\}$. Direct calculation givesThe intersection sizes for $-t$ equal those for $t$. Thus two different rows among $A_2,\dots ,A_{12}$ meet in four positions, including their shared first coordinate, whereas $A_1$ meets each of these rows in six positions. All these intersection sizes are even numbers, while each row weight is an odd number. Consequently $A{A}^T=I$. The first row and column agree, and the entry of the last eleven-by-eleven block depends only on the sum of its row and column indices modulo eleven, because successive rows are left shifts. Thus $A$ is a symmetric matrix, so $A^2=I$.

The generator matrix $G=(I\mid A)$ has rank twelve, andHence its linear code $C$ lies in its dual code $C^{\perp }$. Both have dimension twelve, so $C=C^{\perp }$: it is a self-dual code. Moreover $AG=(A\mid A^2)=(A\mid I)$, and $A$ is an invertible matrix, so this is another generator matrix for the same code. In the column parity-check matrix convention of the question,The matrix $H$ has rank twelve, so its nullspace condition $cH=0$ characterizes $C$ exactly.

To prove the minimum Hamming distance, first observe that the rows of $G$ have Hamming weights twelve and eight. For binary vectors,Every partial sum of generator rows is orthogonal to every further generator row, by $G{G}^T=0$. Its intersection with that row therefore contains an even number of positions. Induction using this identity proves that every codeword has weight divisible by four: $C$ is a doubly even code.

The systematic-matrix proof of extended Golay distance now excludes weight four. Write a codeword as $(u,uA)$ and put $k=\mathrm{wt}(u)$. If its total weight were four, $1\le k\le 4$. For $k=1$, the right half is a row of $A$ and has weight seven or eleven. For $k=2$, the right half is the sum of two distinct rows; the intersection counts above give weight $11+7-2\cdot 6=6$ or $7+7-2\cdot 4=6$. For $k=3$, the right half would be a unit vector, but then $u=(uA)A$ would be a row of $A$, of weight seven or eleven. For $k=4$, the right half would vanish, contradicting invertibility of $A$. Thus no nonzero word has weight four. Every nonzero weight is consequently at least eight, and any generator row other than the first attains eight. Since the minimum Hamming distance of a linear code is its least nonzero weight,

Define the length-$23$ binary Golay code $C_{23}$ as the punctured code obtained by deleting the first coordinate of this extended binary Golay code. This puncturing is injective on $C$, because a nonzero word in its kernel would have weight one. Thus $\dim C_{23}=12$, and deleting one coordinate gives $d(C_{23})\ge 7$. The sum of the first two generator rows has weight eight and first coordinate one, so its puncture has weight seven. Therefore $d(C_{23})=7$. In fact any coordinate can be punctured: every left coordinate except the first occurs in a weight-eight generator row, the first occurs in the sum just used, and every right coordinate occurs in at least one of the weight-eight generator rows.

The radius-three Hamming balls around the $2^{12}$ words of $C_{23}$ are disjoint, since two centers in intersecting balls would have Hamming distance at most six. Each ball containswords. Their combined size is $2^{12}{2}^{11}=2^{23}$, the size of the entire binary Hamming space. Hence

For decoding in $C$, write the received word as $y=c+(p,q)$, where $(p,q)$ is the unknown error in its two halves. Its syndrome isLet $e_i$ denote the length-twelve unit vector. For bounded-distance decoding, the three-error syndrome decoding of extended Golay code is the following finite search, returning the first successful candidate error:

Every returned candidate has total Hamming weight at most three and the required syndrome. Conversely, an error of total weight at most three has a half of weight zero or one. The tests exhaust respectively $q=0$, $q=e_i$, $p=0$, and $p=e_i$, so they find every such error. Two distinct successful candidates would differ by a nonzero codeword of weight at most six, contradicting $d(C)=8$. Thus the result is unique, and the decoded word is $y+(p,q)$. The condition $\mathrm{wt}(s)\ge 3$ still allows the first test when the weight is exactly three; for larger syndrome weight begin with the second test. A large syndrome weight alone does not imply more than three errors.

The decoder corrects every error of weight at most three; failure means that the received word is outside all radius-three decoding balls. Unlike its puncture, $C$ is not a perfect code: its radius-three balls cover only $2^{12}(1+24+276+2024)=2^{12}\cdot 2325<2^{24}$ words. Without the three-error assumption, a successful test identifies a nearby codeword but need not identify the transmitted word.

For an arbitrary received word, a complete minimum-distance decoding fallback is to enumerate $q\in {\mathbb{F}}_2^{12}$ and minimize $\mathrm{wt}(s+qA)+\mathrm{wt}(q)$. Every error with the observed syndrome has exactly the form $(s+qA,q)$, so a minimizer gives a nearest codeword $y+(s+qA,q)$. Report all minimizers if there is a tie. This also decodes outside the guaranteed radius in the nearest-word sense, while making no unsupported claim that the transmitted word is determined. Thus a syndrome of weight at least three alone is insufficient for guaranteed recovery; either the three-error hypothesis or a choice among nearest words is needed.

Robert A. Wilson works on finite groups, their group representations and computational constructions, especially sporadic simple groups. His research homepage documents this specialization and work on the Monster group.^[ref]

His work on Suzuki group of Lie type and Ree group of type G2 constructs these exceptional families through automorphisms and analyzes their actions and simplicity. His lectures on sporadic groups also connect Mathieu groups with the symmetries of the extended binary Golay code, illustrating how error-correcting structures reveal exceptional finite symmetry.^[ref][ref]

A sporadic simple group is one of the twenty-six exceptional finite nonabelian simple groups that lie outside the alternating and Lie-type families in the classification of finite simple groups. “Sporadic” describes their place in that classification; it does not mean randomly chosen or lacking internal structure.^[ref]

For example, the Mathieu group $M_{24}$ acts by coordinate permutations preserving the extended binary Golay code on twenty-four positions. Thus an exceptional group can emerge as the exact symmetry of a highly organized error-correcting code. The Monster group is another sporadic example, vastly larger. In contrast, the alternating group $A_5$ is simple but belongs to an infinite family, so is not sporadic.

For a binary symmetric matrix $A$ with $A^2=I$, the syndrome of an error $(p,q)$ relative to the column parity-check matrix $(I;A)$ is $s=p+qA$. An error of total Hamming weight at most three has at most one nonzero bit in one half. Test $s$, each $s+A_i$, $sA$, and each $sA+A_i$ for weights at most three, two, three and two respectively. These identify $(s,0)$, $(s+A_i,e_i)$, $(0,sA)$ and $(e_i,sA+A_i)$. For the extended binary Golay code, minimum Hamming distance eight guarantees that at most one such error exists.