A code built from an icosahedron

Sixteen spheres that fill a cube found that Hamming’s code of length seven is perfect: its sixteen codewords, each surrounded by the eight words within one flipped bit, fill the 128 words of length seven exactly, with no overlap and no gap. The essay then did some arithmetic. A code of length 23 correcting three errors would need balls of $1 + 23 + 253 + 1771 = 2048$ words each, and $2^{23}/2^{11} = 2^{12}$, so the arithmetic permits $4{,}096$ codewords — and Marcel Golay published such a code in 1949, in a paper of half a page. And it recorded the theorem of Aimo Tietäväinen and Jacobus van Lint that, apart from trivial cases and repetitions, the Hamming codes and this one are the only perfect binary codes there are.

That essay stated the Golay code’s existence. This one builds it, from a surprising starting point, and checks every claim about it by counting.

Twelve rows from twelve corners #

The icosahedron, the last of the five perfect solids, has twelve vertices, and each is joined by an edge to five others. Each vertex is therefore not joined to six others — and, by convention here, not joined to itself, making seven. Write a $12 \times 12$ table $B$ with a $1$ in row $i$ and column $j$ when vertices $i$ and $j$ are not joined, and put the identity table beside it. The result is twelve rows of 24 bits, each with eight ones: one in the left half, seven in the right.

The Golay code is everything those rows generate: all $2^{12} = 4096$ strings obtained by choosing some of the rows and adding them bit by bit modulo two, where $1 + 1 = 0$. This is the same construction as finding the error without reading the message used for Hamming’s code, where the generator was the identity beside a table of parity bits; here the table of parity bits is a picture of a solid.

The first thing the construction gives for free is that the Golay code is its own dual. Any two rows overlap in an even number of positions — any two vertices of the icosahedron have an even number of common non-neighbours, counting themselves, which is a fact about the solid’s symmetry that the figure checks pair by pair — and so, modulo two, every row is perpendicular to every other and to itself. Every codeword is then perpendicular to every codeword, and since a code of dimension twelve in a space of dimension 24 can be perpendicular to at most a twelve-dimensional space, the Golay code is exactly the set of strings perpendicular to it. It checks its own parities.

Five weights, and a distance of eight #

A code corrects errors according to its minimum distance, the fewest positions in which two different codewords differ. For a code closed under addition, that is the smallest number of ones in any non-zero codeword, so it can be found by counting the weight of each of the 4,096 words.

The count is striking. Of the twenty-five weights a 24-bit string can have, the Golay code uses five: one word of weight 0, 759 of weight 8, 2,576 of weight 12, 759 of weight 16, and the all-ones word of weight 24. So any two codewords differ in at least eight places, and so it can correct any three errors in a word — three flips leave the received word closer to the word sent, at distance three, than to any other, which is at least five away — and detect a fourth.

The gaps in the list have a reason that the construction makes visible. Every row has weight divisible by four, and the dual property forces any sum of rows to keep that divisibility, since the weight of a sum of two words is the sum of their weights minus twice their overlap, and the overlap is even. So every weight is a multiple of four; the Golay code is called doubly even. Weight four is then the only way the distance could be less than eight, and no codeword of weight four exists. That last fact is the one the icosahedron contributes, and it is checked here only by counting.

Deleting the last coordinate gives a code of length 23 with the same 4,096 words and weights 0, 7, 8, 11, 12, 15, 16 and 23: 253 words of weight seven, so a minimum distance of seven, still enough to correct three errors. This shorter code is the perfect one.

Every word within three flips of exactly one codeword #

The arithmetic of perfection is a count of the words near each codeword. Within distance three of a given codeword of length 23 lie the codeword itself, the 23 words with one bit flipped, the $\binom{23}{2} = 253$ with two flipped and the $\binom{23}{3} = 1771$ with three. That is $2048 = 2^{11}$ words. With $2^{12}$ codewords, the balls hold $2^{23}$ words between them, which is every word of length 23 — if no two balls overlap.

The arithmetic proves nothing about overlap, so the figure checks it directly: every one of the $2^{23} = 8{,}388{,}608$ words of length 23 was visited, and each was found to lie within distance three of exactly one codeword. None twice, none never. The balls tile the space.

The perfection has a practical consequence that is easy to state wrongly. A perfect code is the most efficient possible for its length and correcting power: it wastes no words. But it also has no words that signal uncertainty, because every received word is assigned to some codeword within distance three.

With up to three errors, every received word is decoded to the codeword sent, two thousand times out of two thousand at each count. With four errors, every received word is decoded to a different codeword — always, because the received word, four from the codeword sent, lies in some other ball, three from another codeword, and there is no gap between balls for it to fall into. A code with spare words could at least report that something was wrong. The perfect code corrects three errors with certainty and turns four into a confident wrong answer. That is why practical systems use the extended code of length 24. With distance eight, a word with four errors lies four from the codeword sent and at least four from every other, so no codeword is within three of it and the decoder can report a failure instead of guessing — at the price of the perfection.

Decoding with a table of 2,048 entries #

Comparing a received word with all 4,096 codewords, as the decoding figure does, is the brute-force way to find the nearest one. The perfection makes a far cheaper way exact. The Golay code of length 23 is described by eleven parity checks — eleven sums of chosen positions that are nought for every codeword — and a received word’s syndrome is the list of which checks it fails, an eleven-bit pattern. A codeword has syndrome zero. A received word $c + e$, with $c$ the codeword and $e$ the error pattern, has the same syndrome as $e$ alone, because the checks are sums and the codeword contributes nothing to them.

So decoding needs only a table from syndromes to error patterns. There are $2^{11} = 2048$ syndromes and exactly 2,048 error patterns of weight at most three — the same 1, 23, 253 and 1,771 that filled the ball. Perfection says these patterns all have different syndromes and between them use every syndrome once: if two patterns of weight at most three had the same syndrome, their sum would be a codeword of weight at most six, and there is none. The decoder computes eleven parities, looks the answer up, and flips the bits the table names. That is the construction finding the error without reading the message used for Hamming’s code, where seven syndromes named the seven single-bit errors; here 2,047 non-zero syndromes name every pattern of up to three errors, with not one left over.

The same count explains the decoding figure’s fourth column. A pattern of four errors has some syndrome, and that syndrome belongs to some pattern of at most three errors — every syndrome does. The decoder flips those bits instead, adding three more errors to the four, and lands on a codeword seven or fewer places from the one sent, which is the nearest-codeword decoding the figure measured, arriving at the same wrong answer by a table look-up.

A second construction, from the squares modulo 23 #

The icosahedron is not the only door in. Number the 23 positions $0$ to $22$ and call a non-zero position a square if it is a square modulo 23 — one of $1, 2, 3, 4, 6, 8, 9, 12, 13, 16, 18$. Which numbers are squares modulo a prime is the subject of the first number that is not a square and the reciprocity law around it, and 23 is a prime of the form $8k - 1$, for which $-1$ is not a square and $2$ is. The Golay code generated by the word with ones at the squares, together with all its cyclic shifts, is again the Golay code of length 23: the quadratic residue code, discovered independently of Golay’s construction and equivalent to it.

The second construction explains a symmetry the first hides. A cyclic shift of a codeword is a codeword, so the Golay code is preserved by the rotation of 23 positions; and multiplying every position by a square modulo 23 permutes the squares among themselves, so it preserves the Golay code too. Neither symmetry is visible in the icosahedron, and the icosahedron’s rotations are not visible in the residues. Each construction shows a small part of $M_{24}$, from a different side, and the counts in the figures — which do not care how the Golay code was built — are the same either way, because it is the same code. That two such different recipes, a solid’s adjacency and the squares modulo a prime, produce one object is the kind of coincidence distance is a picture prepared for when it described a code as a set of points in a cube: the set is what matters, and there can be many ways to name its points.

The octads, and a design no smaller structure has #

The 759 codewords of weight eight can be read as sets: each picks eight of the 24 positions. These sets, called octads, have a property that turns the Golay code into a combinatorial object of a much rarer kind.

Any five of the 24 positions lie in exactly one octad. The check is exhaustive: each octad contains $\binom85 = 56$ sets of five, $759 \times 56 = 42{,}504 = \binom{24}{5}$, and the figure confirms that the 42,504 sets of five arising this way are all different, so each five-set occurs once. It follows that any four positions lie in exactly 5 octads, any three in 21, any two in 77, any one in 253 — the counts in the figure, each matching the formula for a design.

A collection of blocks of size $k$ from $v$ points such that every $t$ points lie in exactly one block is a Steiner system $S(t, k, v)$. A schedule where every pair meets once built the case $t = 2$, where every pair lies in one block, and seven points, seven lines drew the smallest, $S(2, 3, 7)$, the Fano plane. Systems with $t = 2$ and $t = 3$ exist in great profusion. With $t = 5$ only a handful were known for most of the twentieth century, and $S(5, 8, 24)$, built from the Golay code, is the most famous of them. Peter Keevash proved in 2014 that Steiner systems exist for every $t$ whenever the obvious divisibility conditions hold and the number of points is large enough, but his proof is not a construction one could draw; the octads are explicit.

Where the icosahedron’s symmetry goes #

The Golay code inherits symmetry from its construction and then has much more. Any rotation of the icosahedron permutes its vertices and preserves which pairs are joined, so permuting the twelve left-hand positions and the twelve right-hand positions in the same way maps the Golay code to itself. That gives sixty symmetries from rotations, a hundred and twenty with reflections.

The full symmetry group of the extended code — the permutations of the 24 positions that map codewords to codewords — is vastly larger: the Mathieu group $M_{24}$, of order $244{,}823{,}040$, discovered by Émile Mathieu in the 1860s as a group acting on 24 points long before anyone had a code to give it meaning. It is one of the twenty-six sporadic simple groups, the exceptions to the classification of finite simple groups, and it is precisely the group of symmetries of the Steiner system above. The icosahedron is a door into it, not a description of it: the construction uses an obvious sixty-fold symmetry to build an object whose hidden symmetry is four million times larger.

The Golay code also reaches outward into geometry. Sixteen spheres that fill a cube recorded that the Leech lattice, the densest packing of spheres in 24 dimensions, is built from the extended Golay code: the codewords say which sets of coordinates may be shifted together. Error correction, a combinatorial design, a sporadic group and a sphere packing are four faces of one object, and the essay’s starting point, a table of which corners of an icosahedron do not touch, is an unusually concrete way to hold it.

Voyager, and the price of a code #

The extended code went to Jupiter and Saturn on the Voyager spacecraft, encoding image data at a rate of one half: twelve bits of picture in every 24 sent, three errors corrected in each block. The rate a noisy channel allows explained what that rate costs against Shannon’s limit, and at Voyager’s error rates the Golay code was a good compromise between correcting power and the computing power available on a spacecraft in the 1970s. Its decoder is a small table: the received word’s syndrome — the pattern of parity checks a received word fails — has twelve bits, and each of the $2^{12}$ syndromes corresponds to one correctable error pattern, by the perfection the figures check.

Later missions moved to longer codes that approach Shannon’s limit more closely, as the best a code can be described for codes in general. The Golay code was not superseded because it is bad — it is perfect — but because perfection at length 23 is a small achievement against what very long codes can do, and perfection cannot be had at any longer length.

What the counts establish, and what they do not #

Every number in the figures is a count over every codeword, every word of length 23, or every set of five positions, so nothing is sampled except the decoding experiment, which is also checked against the certainty the perfection guarantees. What the counts do not establish is anything general. They verify that this particular construction yields a code with these properties; they do not show why the icosahedron works — why the complement of its adjacency gives a doubly even code with no word of weight four. That has proofs, through the Golay code’s large symmetry group or through quadratic residues modulo 23, which give a second construction of the same code: the positions are the residues modulo 23 and the generator is built from which numbers are squares.

Nor do they reach the classification of perfect codes. That only the Hamming codes, the repetition codes and the binary Golay code are perfect over two symbols is a theorem about all lengths at once, proved by showing that the arithmetic condition — a ball’s size dividing $2^n$ — and further conditions it implies have no other solutions.

Still open: Steiner systems with six #

The octads give a Steiner system with $t = 5$, and there is one with $t = 5$ on 12 points from the ternary Golay code. No Steiner system with $t = 6$ is known. Keevash’s theorem implies that they exist for large enough numbers of points satisfying the divisibility conditions, but the size it requires is not explicit, and no example has been found by construction or search. The Golay code’s octads are, in that sense, the most balanced structure of their kind that anyone can actually write down, and whether some code or geometry hides a six-fold version of the same property is one of the cleaner open questions in combinatorics.