40.06.07 · combinatorics / design-coding-theory

Perfect Codes: the Hamming and Golay Codes

shipped3 tiersLean: none

Anchor (Master): van Lint 1999 *Introduction to Coding Theory* 3e Ch. 3-4, 6 (the binary [23,12,7] and ternary [11,6,5] Golay codes, weight enumerators, Lloyd's theorem, the van Lint-Tietäväinen classification); MacWilliams-Sloane 1977 *The Theory of Error-Correcting Codes* Ch. 6, 16, 20 (the Golay codes, the Mathieu groups, the 5-designs); Conway-Sloane 1988 *Sphere Packings, Lattices and Groups* (Springer) Ch. 10-11 (the Golay code, the Leech lattice, the Mathieu groups); Hamming 1950 *Bell System Tech. J.* 29; Golay 1949 *Proc. IRE* 37; Tietäväinen 1973 *SIAM J. Appl. Math.* 24; van Lint 1975 (the classification)

Intuition Beginner

A code spreads its messages out as a scattered handful of allowed strings, and decoding means snapping a corrupted string back to the nearest allowed one. Around each allowed string, picture a ball: all the strings you reach by flipping at most a fixed number of symbols. If the balls never overlap, decoding is unambiguous — a lightly damaged string lands in exactly one ball and you read off its centre. But the balls might leave gaps: strings that sit too far from every codeword to be repaired with confidence.

A perfect code is the case with no gaps and no overlaps. The balls fit together so snugly that they fill the whole space of strings, each string belonging to one ball and no string left over. Every possible received string is within the correcting radius of exactly one codeword. Nothing is wasted: the code packs the maximum number of messages that the correcting power allows, with the error-balls tiling the space the way identical tiles cover a floor.

Such flawless packings are rare. You might guess that for every length and every correcting radius there is some clever perfect code, but the truth is the opposite. Apart from a few unavoidable boring cases, only two families exist: the Hamming codes, which fix one error, and two lonely Golay codes discovered by Marcel Golay in a half-page note. These few are the only ways to tile string-space exactly. This unit builds them and explains why the list stops there.

Visual Beginner

Think of the space of all strings as a floor, and the error-ball around each codeword as a tile. A perfect code is a set of tiles that covers the floor with no gaps and no overlaps. A non-perfect code leaves bare patches between the tiles: strings the code cannot confidently repair.

code	error-balls	leftover strings	perfect?
repetition ${000, 111}$ , radius $1$	$2 \times 4 = 8$	$8 - 8 = 0$	yes
Hamming length $7$ , radius $1$	$16 \times 8 = 128$	$128 - 128 = 0$	yes
a random length- $7$ code, radius $1$	fewer than $128$	some left over	no

The table counts strings. The space of length- $7$ binary strings holds $128$ points; a radius- $1$ ball holds $8$ points; and $16$ balls times $8$ points each is exactly $128$ . The fit is perfect — no point is missed, none is double-covered.

Worked example Beginner

Take the binary repetition code that sends each bit three times: the codewords are $000$ and $111$ , living among the $8$ strings of length $3$ . Check by counting that this code is perfect with correcting radius $1$ .

Step 1. Count the strings. Length- $3$ binary strings number $2 \times 2 \times 2 = 8$ . List them: $000, 001, 010, 011, 100, 101, 110, 111$ .

Step 2. Count one error-ball. The ball of radius $1$ around $000$ holds $000$ itself plus the three strings one flip away: $100, 010, 001$ . That is $1 + 3 = 4$ strings. The ball around $111$ likewise holds $111, 011, 101, 110$ — another $4$ .

Step 3. Check the tiling. The two balls together list $000, 100, 010, 001$ and $111, 011, 101, 110$ — all $8$ strings, each appearing once. The balls do not overlap and leave nothing out.

Step 4. Confirm the count. Two codewords times four strings per ball is $2 \times 4 = 8$ , exactly the number of strings. The sphere-packing count comes out equal, which is the signature of a perfect code.

What this tells us: the repetition code wastes nothing — every length- $3$ string is one flip from exactly one of the two codewords, so every single error is repaired and no string is ever ambiguous. This same balance, scaled up, defines the Hamming and Golay codes.

Check your understanding Beginner

Formal definition Intermediate+

Throughout, $F_{q}$ is the finite field with $q$ elements (its structure is developed in 21.02.01; here it is applied), $q$ a prime power, and $F_{q}^{n}$ the space of length- $n$ words with the Hamming metric of 40.06.06. A code $C \subseteq F_{q}^{n}$ has minimum distance $d$ and corrects $e = ⌊(d - 1) /2 ⌋$ errors. The volume of a Hamming ball of radius $r$ is $V_{q} (n, r) = \sum_{i = 0}^{r} (i n) (q - 1)^{i}$ .

Definition (perfect code). A code $C \subseteq F_{q}^{n}$ of minimum distance $d = 2 e + 1$ is perfect if the closed Hamming balls of radius $e$ about its codewords partition $F_{q}^{n}$ ; equivalently, it meets the sphere-packing bound with equality, $$ |C| \cdot V_q(n, e) = q^n. $$ The elementary perfect codes are the whole-space codes ( $d = 1$ ), the codes with a single codeword, and the binary repetition codes ${0 \dots 0, 1 \dots 1}$ of odd length $n = 2 e + 1$ . A perfect code that is none of these is called a genuine (nonelementary) perfect code.

Definition (Hamming code). Fix $m \geq 2$ and let $n = (q^{m} - 1) / (q - 1)$ , the number of one-dimensional subspaces of $F_{q}^{m}$ . The $q$ -ary Hamming code $Ham (m, q)$ is the $[n, n - m]_{q}$ code whose parity-check matrix $H$ has columns one nonzero representative from each one-dimensional subspace, so that no two columns are scalar multiples of one another. For $q = 2$ this lists all $2^{m} - 1$ nonzero binary columns of length $m$ , giving the $[2^{m} - 1, 2^{m} - 1 - m, 3]_{2}$ code.

Definition (simplex / dual code). The dual $Ham (m, q)^{⊥}$ is the simplex code $S (m, q)$ , an $[n, m]_{q}$ code whose every nonzero codeword has weight $q^{m - 1}$ ; it is equidistant, all nonzero codewords pairwise at distance $q^{m - 1}$ . Its generator matrix is the parity-check matrix $H$ of the Hamming code.

Definition (Golay codes). The binary Golay code $G_{23}$ is the $[23, 12, 7]_{2}$ cyclic code generated by a degree- $11$ factor of $x^{23} - 1$ over $F_{2}$ (the construction is shared with the cyclic-code theory co-produced in 40.06.08). Its extension $G_{24}$ , adjoining an overall parity check, is the self-dual $[24, 12, 8]_{2}$ code. The ternary Golay code $G_{11}$ is the $[11, 6, 5]_{3}$ cyclic code from a factor of $x^{11} - 1$ over $F_{3}$ , with extension $G_{12}$ , the self-dual $[12, 6, 6]_{3}$ code.

Counterexamples to common slips Intermediate+

Perfect is not the same as MDS. A perfect code meets the sphere-packing (volume) bound; an MDS code meets the Singleton (rank) bound. The $[7, 4, 3]_{2}$ Hamming code is perfect but not MDS, and a Reed-Solomon code is MDS but rarely perfect. The two extremal conditions are independent.
Hamming codes are defined by the columns of $H$ , not by a fixed generator. Any matrix with one nonzero representative per one-dimensional subspace gives a Hamming code; different choices yield permutation-equivalent codes with the same parameters. Listing all nonzero columns (not up to scalars) is correct only over $F_{2}$ , where each one-dimensional subspace has a unique nonzero vector.
The Golay code length is $23$ , not $24$ . The perfect code is $G_{23}$ with $d = 7$ , correcting $3$ errors. Its extension $G_{24}$ has $d = 8$ and is not perfect — it is even-weight and self-dual, valued for its automorphism group and design, not for tiling.
" $11$ is the only ternary perfect length." Only the ternary Golay code $[11, 6, 5]_{3}$ and the elementary ternary codes are perfect over $F_{3}$ . Length alone does not make a code perfect; the parameters must solve the sphere-packing equation, and over $F_{3}$ only $11$ does so nonelementarily.

Key theorem with proof Intermediate+

The defining fact about the Hamming code is that it tiles the space: every word is within distance one of a unique codeword. This follows from the column structure of the parity-check matrix.

Theorem (Hamming codes are perfect single-error-correcting codes). For $m \geq 2$ and $n = (q^{m} - 1) / (q - 1)$ , the code $Ham (m, q)$ has parameters $[n, n - m, 3]_{q}$ , corrects one error, and is perfect: $$ q^{n-m} \cdot \big(1 + n(q-1)\big) = q^n. $$

Proof. The parity-check matrix $H$ is $m \times n$ , its columns the $n = (q^{m} - 1) / (q - 1)$ representatives of the one-dimensional subspaces of $F_{q}^{m}$ , no two scalar-proportional. By the parity-check distance criterion of 40.06.06, the minimum distance is the least number of linearly dependent columns. No single column is zero, so $d \geq 2$ . No two columns are dependent, since dependence of two columns means one is a scalar multiple of the other, excluded by construction; so $d \geq 3$ . But some three columns are dependent: pick distinct one-dimensional subspaces and find a dependence — for instance over $F_{2}$ three columns $h_{i}, h_{j}, h_{k}$ with $h_{i} + h_{j} = h_{k}$ exist because the sum of two distinct nonzero vectors is a third nonzero vector, present as a column. Hence $d = 3$ and $e = 1$ .

The dimension is $k = n - rank (H) = n - m$ , since $H$ has rank $m$ (its columns span $F_{q}^{m}$ ). For perfection, the radius- $1$ ball has volume $V_{q} (n, 1) = 1 + n (q - 1)$ , and $$ |C| \cdot V_q(n,1) = q^{n-m}\big(1 + n(q-1)\big) = q^{n-m}\big(1 + (q^m - 1)\big) = q^{n-m}\cdot q^m = q^n, $$ using $n (q - 1) = q^{m} - 1$ . Equality in the sphere-packing bound is perfection. Concretely, decoding is immediate: a received word $y$ has syndrome $H y^{T}$ , which is either $0$ (then $y \in C$ ) or a nonzero vector equal to a scalar multiple $α h_{j}$ of exactly one column; subtracting $α$ in coordinate $j$ corrects the single error. $□$

Bridge. This theorem builds toward the whole classification by pinning down the smallest genuine perfect codes — the single-error-correcting Hamming family — and it appears again in the master tier as the $e = 1$ case of Lloyd's theorem, where the Lloyd polynomial has its one root at $x = q^{m - 1}$ , exactly the weight of every simplex codeword. The foundational reason the count is exact is that the nonzero syndromes biject with the one-dimensional error patterns: $q^{m} - 1$ nonzero syndromes match $n (q - 1)$ weight-one errors, and this is exactly the equality $n (q - 1) = q^{m} - 1$ . This is dual to the simplex code, whose equidistance $q^{m - 1}$ is the MacWilliams transform of the Hamming weight enumerator; the central insight — that perfection is a bijection between syndromes and correctable error patterns — generalises to the Golay codes, where the radius- $3$ balls biject with the $2^{11}$ binary syndromes. Putting these together, a perfect code is precisely a code whose syndrome map is a bijection from cosets to correctable errors, and the classification asks for which parameters such a bijection can exist.

Exercises Intermediate+

Exercise 5 (medium, symbolic).

Prove that every nonzero codeword of the binary simplex code $S (m, 2) = Ham (m, 2)^{⊥}$ has weight exactly $2^{m - 1}$ .

Hint

A simplex codeword is $u H$ for $u \in F_{2}^{m}$ nonzero, where the columns of $H$ are all nonzero vectors of $F_{2}^{m}$ . The $j$ -th coordinate of $u H$ is $⟨ u, h_{j} ⟩$ . Count the columns $h_{j}$ with $⟨ u, h_{j} ⟩ = 1$ .

Answer

The simplex code has generator matrix $H$ whose columns $h_{1}, \dots, h_{2^{m} - 1}$ are all nonzero vectors of $F_{2}^{m}$ . A nonzero codeword is $c = u H$ for some $u \neq = 0$ , with $c_{j} = ⟨ u, h_{j} ⟩$ . The weight of $c$ is the number of nonzero $h_{j}$ with $⟨ u, h_{j} ⟩ = 1$ . For fixed $u \neq = 0$ , the linear functional $x \mapsto ⟨ u, x ⟩$ on $F_{2}^{m}$ is onto $F_{2}$ , so exactly half of all $2^{m}$ vectors $x$ satisfy $⟨ u, x ⟩ = 1$ , namely $2^{m - 1}$ of them. The vector $x = 0$ gives $⟨ u, 0 ⟩ = 0$ , so all $2^{m - 1}$ solutions are among the nonzero columns. Hence $wt (c) = 2^{m - 1}$ for every nonzero $u$ . Rubric: full credit for identifying the coordinate as a linear functional, the half-space count $2^{m - 1}$ , and noting $0$ is excluded.

Exercise 7 (hard, symbolic).

Prove the elementary direction of the sphere-packing characterisation: if $C \subseteq F_{q}^{n}$ has minimum distance $2 e + 1$ and $∣ C ∣ \cdot V_{q} (n, e) = q^{n}$ , then the radius- $e$ balls about codewords partition $F_{q}^{n}$ , and conversely.

Hint

Disjointness of the balls follows from $d \geq 2 e + 1$ and the triangle inequality. Then compare the total number of points covered with $q^{n}$ .

Answer

For distinct codewords $c, c^{'}$ , the balls $B (c, e)$ and $B (c^{'}, e)$ are disjoint: a common point $z$ gives $d (c, c^{'}) \leq d (c, z) + d (z, c^{'}) \leq 2 e < 2 e + 1 \leq d$ , contradicting the minimum distance. Each ball contains exactly $V_{q} (n, e)$ points (choose $i \leq e$ coordinates to alter, $q - 1$ values each). The $∣ C ∣$ disjoint balls cover $∣ C ∣ \cdot V_{q} (n, e)$ points, and these lie in $F_{q}^{n}$ , so $∣ C ∣ \cdot V_{q} (n, e) \leq q^{n}$ always. Equality holds iff the union of the balls is all of $F_{q}^{n}$ with no point left uncovered — i.e. the balls partition the space, every word within distance $e$ of a unique codeword. Conversely, a partition by radius- $e$ balls forces $∣ C ∣ \cdot V_{q} (n, e) = q^{n}$ by counting. Rubric: full credit for disjointness via the triangle inequality, the ball-volume count, and the equality-iff-partition equivalence.

Exercise 8 (hard, symbolic).

Show that no binary perfect $2$ -error-correcting code of length $n$ exists for which the sphere-packing equation $2^{k} (1 + n + (2 n)) = 2^{n}$ holds with $n$ in a small range, by proving that $1 + n + (2 n)$ is a power of $2$ forces strong constraints, and check $n = 5$ as the one elementary solution.

Hint

$1 + n + (2 n) = \frac{n ^{2} + n + 2}{2}$ must be a power of $2$ . Test small $n$ ; $n = 5$ gives the binary repetition pattern's relative, and large $n$ requires a Diophantine obstruction.

Answer

The radius- $2$ ball has volume $V_{2} (n, 2) = 1 + n + (2 n) = \frac{n ^{2} + n + 2}{2}$ , which must divide $2^{n}$ , hence be a power of $2$ . Write $\frac{n ^{2} + n + 2}{2} = 2^{s}$ , i.e. $n^{2} + n + 2 = 2^{s + 1}$ , so $n (n + 1) = 2^{s + 1} - 2 = 2 (2^{s} - 1)$ . Thus $\frac{n ( n + 1 )}{2} = 2^{s} - 1$ is one less than a power of $2$ ; since $(2 n + 1)$ is a triangular number, we need a triangular number of the form $2^{s} - 1$ . For $n = 5$ : $\frac{5 \cdot 6}{2} = 15 = 2^{4} - 1$ , giving $V_{2} (5, 2) = 16 = 2^{4}$ and $2^{n - 4} \cdot 16 = 2^{n}$ , a valid packing — realised only by the degenerate whole-pair structure (and consistent with the fact that the only binary perfect $2$ -error-correcting parameters are degenerate, no genuine code existing). For other small $n$ ( $n = 2, 3, 4, 6, 7, \dots$ ) the quantity $\frac{n ( n + 1 )}{2}$ is not of the form $2^{s} - 1$ , so the ball volume is not a power of $2$ and no perfect code can exist. The full statement — that no genuine binary perfect $2$ -error-correcting code exists — is part of the Lloyd-theorem analysis. Rubric: full credit for reducing to $\frac{n ( n + 1 )}{2} = 2^{s} - 1$ , checking $n = 5$ , and noting the obstruction for other small $n$ .

Advanced results Master

The Hamming codes settle the single-error case; the Golay codes are the only further genuine perfect codes, and their internal structure — weight enumerators, automorphism groups, and the designs they hold — places them at the centre of finite group theory. The results below trace those threads and close with the classification.

Theorem 1 (the binary Golay code and its weight enumerator). The binary Golay code $G_{23}$ is the $[23, 12, 7]_{2}$ cyclic code generated by either irreducible factor of $x^{23} - 1 = (x - 1) g_{1} (x) g_{2} (x)$ over $F_{2}$ , each $g_{i}$ of degree $11$ ; equivalently it is the quadratic-residue code of length $23$ . Its extension $G_{24}$ is the $[24, 12, 8]_{2}$ self-dual doubly-even code with weight enumerator $$ W_{\mathcal{G}{24}}(x,y) = x^{24} + 759, x^{16}y^8 + 2576, x^{12}y^{12} + 759, x^8 y^{16} + y^{24}, $$ the unique self-dual doubly-even $[24, 12, 8]_{2}$ code. Puncturing one coordinate returns $G_{23}$ , whose weight distribution has $A_{0} = 1$ , $A_{7} = 253$ , $A_{8} = 506$ , $A{11} = 1288 $,$ A_{12} = 1288 $,$ A_{15} = 506 $,$ A_{16} = 253 $,$ A_{23} = 1$ ^{[MacWilliams-Sloane Ch. 6]}.

Theorem 2 (the ternary Golay code). The ternary Golay code $G_{11}$ is the $[11, 6, 5]_{3}$ cyclic code from a degree- $5$ factor of $x^{11} - 1$ over $F_{3}$ ; its extension $G_{12}$ is the self-dual $[12, 6, 6]_{3}$ code with weight enumerator $$ W_{\mathcal{G}{12}}(x,y) = x^{12} + 264, x^6 y^6 + 440, x^3 y^9 + 24, y^{12}, $$ the codewords of weight $6$ supporting a Steiner system $S (5, 6, 12)$ ^{[van Lint 1999 Ch. 4]}. An equivalent construction borders the $5 \times 5$ circulant of quadratic residues modulo $11$ , tying $\mathcal{G}{12} $t o t h e i cos ah e d r o n, w h ose$ 12 $v er t i ces an d$ \pm 1$ adjacency pattern reproduce the same self-dual code.

Theorem 3 (Mathieu groups as automorphism groups). The automorphism group of $G_{24}$ acting on the $24$ coordinates is the Mathieu group $M_{24}$ , a sporadic simple group of order $244823040$ , $5$ -transitive on $24$ points; the stabiliser of a coordinate is $M_{23}$ , $4$ -transitive on $23$ points and equal to $Aut (G_{23})$ . The ternary $G_{12}$ has automorphism group $2. M_{12}$ , with $M_{12}$ sporadic simple of order $95040$ and $5$ -transitive on $12$ points; the coordinate stabiliser is $M_{11}$ . These four Mathieu groups $M_{11}, M_{12}, M_{23}, M_{24}$ are the first sporadic simple groups discovered (Mathieu, 1861-1873), realised here as code automorphisms ^{[MacWilliams-Sloane Ch. 16]}.

Theorem 4 (the $5$ -designs; Assmus-Mattson). By the Assmus-Mattson theorem (proved in the co-produced cyclic-code unit 40.06.08), the supports of the weight- $8$ codewords of $G_{24}$ form a Steiner system $S (5, 8, 24)$ — the $759$ octads — a $5$ - $(24, 8, 1)$ design; the weight- $12$ codewords give a $5$ - $(24, 12, 48)$ design. The weight- $6$ codewords of $G_{12}$ form a Steiner system $S (5, 6, 12)$ , a $5$ - $(12, 6, 1)$ design of $132$ hexads. These remain among the very few known genuinely $5$ -transitive designs, and their automorphism groups are exactly the Mathieu groups of Theorem 3. The Steiner-system viewpoint connects directly to 40.06.04, where $S (5, 8, 24)$ and $S (5, 6, 12)$ are the apex examples.

Theorem 5 (Lloyd's theorem). If a perfect $e$ -error-correcting code of length $n$ over $F_{q}$ exists, then the Lloyd polynomial $$ L_e(x) = \sum_{i=0}^{e} (-1)^i (q-1)^{e-i} \binom{x-1}{i}\binom{n-x}{e-i} $$ has $e$ distinct integer roots in ${1, 2, \dots, n}$ ^{[Lloyd 1957]}. The roots are the nonzero eigenvalues' index set of the Hamming association scheme that lie in the radius- $e$ Lloyd spectrum; $L_{e}$ is, up to normalisation, the Krawtchouk polynomial $K_{e} (x)$ , so the condition says $e$ of the $n$ Krawtchouk values vanish at integer arguments — a severe arithmetic restriction.

Theorem 6 (van Lint-Tietäväinen classification). Over any finite field $F_{q}$ , a perfect $e$ -error-correcting code with $e \geq 1$ and length $n > 1$ has one of the following parameter sets: a Hamming code $[(q^{m} - 1) / (q - 1), (q^{m} - 1) / (q - 1) - m, 3]_{q}$ ; the binary Golay code $[23, 12, 7]_{2}$ ; the ternary Golay code $[11, 6, 5]_{3}$ ; or a binary repetition code $[2 e + 1, 1, 2 e + 1]_{2}$ of odd length. No other parameters admit a perfect code ^{[Tietäväinen 1973]}. The proof combines Lloyd's theorem — which forces $L_{e}$ to have $e$ integer roots — with a delicate Diophantine analysis (using lower bounds on the roots and a study of $(e n)$ ) eliminating every remaining parameter set.

Synthesis. Putting these together, perfection is a single arithmetic miracle read across three registers, and this is exactly the content of the classification. The sphere-packing equality is the foundational reason a perfect code exists at all: it demands that the ball volume $V_{q} (n, e)$ divide $q^{n}$ , and Lloyd's theorem sharpens this to the statement that the Krawtchouk polynomial $K_{e}$ must have $e$ integer roots in the admissible range — the central insight that converts a packing problem into a question about the zeros of orthogonal polynomials on the Hamming scheme. This is dual, in the precise MacWilliams sense, to the simplex and Golay weight enumerators: the equidistance $q^{m - 1}$ of the simplex code is the spectral shadow of the Hamming code's perfection, and the doubly-even self-dual enumerator of $G_{24}$ is the spectral shadow of the Golay packing. The classification is exactly the assertion that this miracle happens only at the Hamming parameters, at $n = 23$ and $n = 11$ , and at the elementary repetition lengths — the Golay arithmetic $(0 23) + (1 23) + (2 23) + (3 23) = 2^{11}$ and its ternary twin being isolated coincidences. The bridge from these finite identities to the wider mathematics is the automorphism groups: the same coordinate symmetries that preserve the packing generalise into the Mathieu sporadic simple groups and, through the $S (5, 8, 24)$ design and the Leech lattice, into the Conway groups and the monstrous moonshine that organises the largest sporadic group.

Full proof set Master

Proposition 1 (Hamming parameters and perfectness). $Ham (m, q)$ is an $[n, n - m, 3]_{q}$ perfect code with $n = (q^{m} - 1) / (q - 1)$ .

Proof. The columns of $H$ are $n$ representatives of the distinct one-dimensional subspaces of $F_{q}^{m}$ ; their number is $(q^{m} - 1) / (q - 1)$ , the count of nonzero vectors divided by the $q - 1$ scalars identifying each subspace. No column is zero and no two are proportional, so by the distance criterion of 40.06.06 $d \geq 3$ ; and three proportional-free columns satisfying a dependence exist (the span of any two distinct one-dimensional subspaces is two-dimensional and contains a third subspace, whose representative is a third column lying in that span), giving $d = 3$ . Rank $H = m$ as its columns span $F_{q}^{m}$ , so $dim C = n - m$ . Then $∣ C ∣ V_{q} (n, 1) = q^{n - m} (1 + n (q - 1)) = q^{n - m} (1 + q^{m} - 1) = q^{n}$ , the sphere-packing equality, so $C$ is perfect. $□$

Proposition 2 (simplex code is equidistant of weight $q^{m - 1}$ ). Every nonzero codeword of $S (m, q) = Ham (m, q)^{⊥}$ has weight $q^{m - 1}$ , and any two distinct codewords are at distance $q^{m - 1}$ .

Proof. A nonzero codeword is $c = u H$ with $u \in F_{q}^{m} ∖ {0}$ , coordinate $c_{j} = ⟨ u, h_{j} ⟩$ where $h_{j}$ ranges over one representative per one-dimensional subspace. The functional $x \mapsto ⟨ u, x ⟩$ is a nonzero linear form, vanishing on a hyperplane of $q^{m - 1}$ vectors. Among the $q^{m} - 1$ nonzero vectors, those in the kernel number $q^{m - 1} - 1$ , partitioned into $(q^{m - 1} - 1) / (q - 1)$ one-dimensional subspaces, each contributing a zero coordinate of $c$ . So $c$ has $(q^{m - 1} - 1) / (q - 1)$ zero coordinates and the remaining $n - (q^{m - 1} - 1) / (q - 1) = (q^{m} - q^{m - 1}) / (q - 1) = q^{m - 1}$ coordinates nonzero. Thus $wt (c) = q^{m - 1}$ for all nonzero $u$ . By linearity $d (c, c^{'}) = wt (c - c^{'}) = q^{m - 1}$ for distinct codewords, since $c - c^{'}$ is another nonzero codeword. $□$

Proposition 3 (perfect codes meet sphere-packing with equality iff balls tile). A code $C$ of minimum distance $2 e + 1$ satisfies $∣ C ∣ V_{q} (n, e) = q^{n}$ iff its radius- $e$ balls partition $F_{q}^{n}$ .

Proof. The radius- $e$ balls about distinct codewords are pairwise disjoint: a common point $z$ of $B (c, e)$ , $B (c^{'}, e)$ gives $d (c, c^{'}) \leq 2 e < d$ . Each ball has $V_{q} (n, e)$ points. Their disjoint union has $∣ C ∣ V_{q} (n, e)$ points inside $F_{q}^{n}$ , so $∣ C ∣ V_{q} (n, e) \leq q^{n}$ ; equality holds iff the union is all of $F_{q}^{n}$ , i.e. the balls partition the space. $□$

Proposition 4 (Lloyd necessary condition, $e = 1$ case). A perfect single-error-correcting code of length $n$ over $F_{q}$ has $L_{1} (x) = (q - 1) (n - x) - (x - 1) \cdot 0$ vanishing at exactly one integer $x_{0} \in {1, \dots, n}$ ; for the Hamming code $x_{0} = q^{m - 1}$ .

Proof. For $e = 1$ the Lloyd polynomial is $L_{1} (x) = (q - 1) (1 n - x) - (1 x - 1) = (q - 1) (n - x) - (x - 1)$ . Setting $L_{1} (x_{0}) = 0$ gives $(q - 1) (n - x_{0}) = x_{0} - 1$ , so $x_{0} = \frac{( q - 1 ) n + 1}{q}$ . For the Hamming code $n = (q^{m} - 1) / (q - 1)$ , hence $(q - 1) n + 1 = q^{m}$ and $x_{0} = q^{m - 1}$ , an integer in range — the common weight of the simplex codewords from Proposition 2. The single integer root certifies the parameters against Lloyd's theorem. The general- $e$ statement, that $L_{e}$ has $e$ distinct integer roots, follows from the eigenvalue structure of the Hamming association scheme: a perfect code is a completely regular code whose outer distribution is governed by the scheme's eigenvalues, and the $e$ roots are the eigenvalue indices where the dual degree vanishes ^{[Lloyd 1957]}. $□$

Proposition 5 (uniqueness of the binary Golay code from its weight enumerator). Any binary self-dual doubly-even $[24, 12, 8]_{2}$ code has the weight enumerator of $G_{24}$ , and there is exactly one such code up to equivalence.

Proof. Self-duality forces $W (x, y) = W (\frac{x + y}{2}, \frac{x - y}{2})$ (the MacWilliams identity of 40.06.06 applied with $∣ C ∣ = 2^{12}$ ), and double-evenness forces $W$ invariant under $y \mapsto i y$ . By Gleason's theorem the ring of such invariant weight enumerators of degree $24$ is spanned by $W_{H_{8}}^{3}$ and $W_{H_{8}} W_{g_{24}}$ , where $H_{8}$ is the $[8, 4, 4]$ Hamming-extended code; imposing $A_{2} = A_{4} = A_{6} = 0$ (minimum distance $8$ ) pins down the coefficients uniquely to $A_{0} = 1, A_{8} = 759, A_{12} = 2576, A_{16} = 759, A_{24} = 1$ . That a code with this enumerator exists and is unique is verified by constructing $G_{24}$ (e.g. as the extended quadratic-residue code mod $23$ ) and checking that the $759$ octads form an $S (5, 8, 24)$ , a configuration rigid enough that its automorphism group $M_{24}$ acts transitively and forces equivalence of any two realisations ^{[MacWilliams-Sloane Ch. 6, 20]}. $□$

Connections Master

The perfect-code condition is the equality case of the sphere-packing (Hamming) bound proved in 40.06.06: that unit supplies the inequality $∣ C ∣ V_{q} (n, e) \leq q^{n}$ and the parity-check distance criterion, and this unit characterises exactly when equality holds. The foundational reason the Hamming codes are perfect is the bijection between the $q^{m} - 1$ nonzero syndromes and the $n (q - 1)$ weight-one error patterns, which is the same column-counting argument that gives the distance criterion there.
The arithmetic of the alphabet rests on the finite-field theory of 21.02.01: the Hamming code's columns enumerate the projective points $P^{m - 1} (F_{q})$ , the Golay codes are built from factorisations of $x^{23} - 1$ over $F_{2}$ and $x^{11} - 1$ over $F_{3}$ (quadratic-residue codes), and the residue-class arithmetic modulo $23$ and $11$ that singles out these two lengths is finite-field number theory. This is dual to the cyclic-code structure, where the same factorisations reappear as generator polynomials.
The co-produced unit 40.06.08 on cyclic codes and the Assmus-Mattson theorem supplies the construction of both Golay codes as cyclic (quadratic-residue) codes and proves that their fixed-weight codewords hold $5$ -designs; this unit uses those designs as the bridge to the Mathieu groups. The Assmus-Mattson machinery is exactly what turns the weight enumerator computed here into the Steiner systems $S (5, 8, 24)$ and $S (5, 6, 12)$ .
The co-produced unit 40.06.04 on Steiner systems is where $S (5, 8, 24)$ and $S (5, 6, 12)$ live as design-theoretic objects: the Golay codes produce these Steiner systems (the $759$ octads and $132$ hexads), and conversely a Steiner system $S (5, 8, 24)$ reconstructs $G_{24}$ . The two units describe the same combinatorial object from the coding and the design sides, with the Mathieu groups as the common automorphism group.

Historical & philosophical context Master

The single-error-correcting codes are Richard Hamming's, published in 1950 ^{[Hamming 1950]} after his weekend frustration with relay-computer failures; the $[7, 4]$ code is the prototype, and the general $[2^{m} - 1, 2^{m} - 1 - m, 3]$ family carries his name. The sphere-packing bound he introduced makes the perfectness immediate, and the codes are the smallest genuine solutions of the packing equation.

The Golay codes appeared a year earlier, in Marcel Golay's 1949 half-page note in the Proceedings of the IRE ^{[Golay 1949]} — one of the most information-dense pages in mathematics. Golay observed that the binomial sum $(0 23) + (1 23) + (2 23) + (3 23) = 2^{11}$ permits a binary triple-error-correcting perfect code of length $23$ , and that a ternary analogue exists at length $11$ , and he exhibited both. The codes' automorphism groups turned out to be the Mathieu groups, discovered by Émile Mathieu in 1861 and 1873 as multiply-transitive permutation groups, and the first of the sporadic simple groups in the eventual classification.

The completeness of the list was conjectured early and proved in stages. Shen Pin Lloyd gave his necessary condition in 1957 ^{[Lloyd 1957]}, reducing perfect codes to an integer-root problem for a Krawtchouk polynomial. Aimo Tietäväinen, with Jacobus van Lint, closed the classification over finite fields in 1973 ^{[Tietäväinen 1973]}: the Hamming codes, the two Golay codes, and the binary repetition codes are the only perfect codes over fields. Over arbitrary alphabets the question stays open in the unequal-error-protection and mixed-alphabet settings, and the $S (5, 8, 24)$ design later seeded Conway's construction of the Leech lattice and the larger sporadic groups.

Bibliography Master

@article{hamming1950,
  author  = {Hamming, Richard W.},
  title   = {Error detecting and error correcting codes},
  journal = {Bell System Technical Journal},
  volume  = {29},
  number  = {2},
  year    = {1950},
  pages   = {147--160}
}

@article{golay1949,
  author  = {Golay, Marcel J. E.},
  title   = {Notes on digital coding},
  journal = {Proceedings of the IRE},
  volume  = {37},
  year    = {1949},
  pages   = {657}
}

@article{lloyd1957,
  author  = {Lloyd, Shen Pin},
  title   = {Binary block coding},
  journal = {Bell System Technical Journal},
  volume  = {36},
  year    = {1957},
  pages   = {517--535}
}

@article{tietavainen1973,
  author  = {Tiet\"{a}v\"{a}inen, Aimo},
  title   = {On the nonexistence of perfect codes over finite fields},
  journal = {SIAM Journal on Applied Mathematics},
  volume  = {24},
  number  = {1},
  year    = {1973},
  pages   = {88--96}
}

@article{vanlint1971survey,
  author  = {van Lint, Jacobus H.},
  title   = {Nonexistence theorems for perfect error-correcting codes},
  journal = {Computers in Algebra and Number Theory (SIAM-AMS Proceedings)},
  volume  = {4},
  year    = {1971},
  pages   = {89--95}
}

@article{mathieu1873,
  author  = {Mathieu, \'{E}mile},
  title   = {Sur la fonction cinq fois transitive de 24 quantit\'{e}s},
  journal = {Journal de Math\'{e}matiques Pures et Appliqu\'{e}es},
  volume  = {18},
  year    = {1873},
  pages   = {25--46}
}

@book{vanlint1999coding,
  author    = {van Lint, Jacobus H.},
  title     = {Introduction to Coding Theory},
  series    = {Graduate Texts in Mathematics},
  volume    = {86},
  edition   = {3rd},
  publisher = {Springer},
  year      = {1999}
}

@book{macwilliamssloane1977,
  author    = {MacWilliams, F. Jessie and Sloane, Neil J. A.},
  title     = {The Theory of Error-Correcting Codes},
  publisher = {North-Holland},
  year      = {1977}
}

@book{conwaysloane1988,
  author    = {Conway, John H. and Sloane, Neil J. A.},
  title     = {Sphere Packings, Lattices and Groups},
  publisher = {Springer},
  year      = {1988}
}

@book{vanlintwilson2001,
  author    = {van Lint, Jacobus H. and Wilson, Richard M.},
  title     = {A Course in Combinatorics},
  edition   = {2nd},
  publisher = {Cambridge University Press},
  year      = {2001}
}

Prerequisites

40.06.06

Tier anchors

beginner: van Lint-Wilson 2001 *A Course in Combinatorics* 2e (Cambridge) Ch. 20 (codes that tile the space exactly: the Hamming codes by hand, the perfect-packing picture); Hill 1986 *A First Course in Coding Theory* (Oxford) Ch. 8-9 (the Hamming codes and a first look at the Golay codes)
intermediate: van Lint 1999 *Introduction to Coding Theory* 3e (Springer GTM 86) Ch. 3-4 (the Hamming codes from the parity-check matrix of all nonzero columns, perfectness from the sphere-packing bound, the simplex dual); MacWilliams-Sloane 1977 *The Theory of Error-Correcting Codes* (North-Holland) Ch. 1-2 (Hamming and Golay codes)
master: van Lint 1999 *Introduction to Coding Theory* 3e Ch. 3-4, 6 (the binary [23,12,7] and ternary [11,6,5] Golay codes, weight enumerators, Lloyd's theorem, the van Lint-Tietäväinen classification); MacWilliams-Sloane 1977 *The Theory of Error-Correcting Codes* Ch. 6, 16, 20 (the Golay codes, the Mathieu groups, the 5-designs); Conway-Sloane 1988 *Sphere Packings, Lattices and Groups* (Springer) Ch. 10-11 (the Golay code, the Leech lattice, the Mathieu groups); Hamming 1950 *Bell System Tech. J.* 29; Golay 1949 *Proc. IRE* 37; Tietäväinen 1973 *SIAM J. Appl. Math.* 24; van Lint 1975 (the classification)

References

van Lint, J. H. — Introduction to Coding Theory · Springer Graduate Texts in Mathematics 86, 3rd edition (1999). Chapter 3 constructs the binary and q-ary Hamming codes from a parity-check matrix whose columns are a maximal set of pairwise linearly independent vectors (all nonzero columns up to scalars), proves their parameters [(q^m-1)/(q-1), (q^m-1)/(q-1)-m, 3] and their perfectness via the sphere-packing bound with equality, and identifies the dual simplex code as an equidistant code. Chapter 4 builds the binary [23,12,7] and ternary [11,6,5] Golay codes, extends them to [24,12,8] and [12,6,6], computes their weight enumerators, and states Lloyd's theorem and the van Lint-Tietaevaeinen classification: the Hamming and Golay codes are the only nonelementary perfect codes over finite fields. Chapter 6 develops the Assmus-Mattson theorem and the 5-designs held by the Golay codes.
MacWilliams, F. J. & Sloane, N. J. A. — The Theory of Error-Correcting Codes · North-Holland (1977). Chapter 6 gives the Golay codes via quadratic residues modulo 23 and modulo 11 and via the icosahedron, computes the weight enumerators (the binary [24,12,8] code has weight distribution A_0=A_24=1, A_8=A_16=759, A_12=2576), and identifies the Steiner systems S(5,8,24) and S(5,6,12). Chapter 16 treats the Mathieu groups M_23, M_24, M_11, M_12 as the automorphism groups. Chapter 20 develops the Assmus-Mattson theorem and the 5-designs from the codewords of fixed weight.
Golay, M. J. E. — Notes on digital coding · Proceedings of the IRE 37 (1949), 657. The half-page note introducing the binary [23,12,7] and ternary [11,6,5] perfect codes, exhibited as the only further solutions of the sphere-packing equation beyond the Hamming and repetition codes.
Hamming, R. W. — Error detecting and error correcting codes · Bell System Technical Journal 29 (1950), 147-160. The single-error-correcting codes whose parity-check matrix lists all nonzero binary columns of length m, the prototype perfect codes.
Tietaevaeinen, A. — On the nonexistence of perfect codes over finite fields · SIAM Journal on Applied Mathematics 24 (1973), 88-96. The completion, with van Lint, of the classification: over a finite field every perfect e-error-correcting code with e >= 1 and length n is a Hamming code, a Golay code, a binary repetition code of odd length, or elementary; the proof rests on Lloyd's theorem forcing the Lloyd polynomial to have e distinct integer roots among the admissible values and a Diophantine analysis ruling out all other parameters.
Lloyd, S. P. — Binary block coding · Bell System Technical Journal 36 (1957), 517-535. The necessary condition for a perfect e-error-correcting code: the Lloyd polynomial L_e(x) = sum_{i=0}^{e} (-1)^i (q-1)^{e-i} binom(x-1, i) binom(n-x, e-i) has e distinct integer roots in {1, ..., n}. The roots are the nonzero coordinates of the Krawtchouk-orthogonal eigenvalue spectrum of the Hamming scheme.

Estimated time

beginner: 18m
intermediate: 45m
master: 90m