Every error-correcting code is a sphere packing — and the Golay code builds Leech
A radio link garbles bits. A scratch takes a chip out of a disc. A cosmic ray flips a one to a zero somewhere between Jupiter and Pasadena. The engineering answer is an error-correcting code: do not send every possible string of bits, send only a carefully chosen few, and choose them so far apart that a handful of flipped bits can never carry one of them onto another.
Read that sentence again with a geometer’s ear. Chosen points, kept far apart, in a space with a distance function. Put a ball around each chosen point, big enough to contain everything a few errors could produce, and demand that the balls not overlap. That is the sphere packing problem, word for word — only the space has changed. Instead of Euclidean space we are in Hamming space: the points are binary words of length n, and the distance between two of them is the number of positions where they differ.
The dictionary between the two subjects is exact. Codewords are sphere centres. The decoding radius is the sphere radius. “The spheres do not overlap” is exactly “the code can correct that many errors.” Packing many spheres into the space is exactly sending many messages per block, so density is data rate. And a packing that leaves no gaps at all — where every point of the space lies in some sphere — is called a perfect code. Those are as rare in Hamming space as perfect packings are in Euclidean space, and one of them is about to change the story.
Three bits give eight words, and they sit at the corners of an ordinary cube: neighbours along an edge differ in one bit. Now pick a code — a subset of those eight words — and draw the ball of radius one around each chosen word, meaning the word itself and everything a single flip away. Whether the code can correct anything at all is decided entirely by whether those balls run into each other. With the minimum distance at 1 they smother the cube; at 2 a flipped bit is always noticed but never identified; at 3 they come apart cleanly and each one claims four corners, which is all eight corners split evenly with nothing to spare.
Corrects 1 · detects 2 · t = ⌊(d−1)/2⌋ = 1
Send each bit three times. Now the two codewords are three flips apart, their balls of radius one are disjoint, and every received word falls inside exactly one of them — so the nearest codeword is always the sent one. The eight words are split 4 + 4 with nothing left over, which makes this a perfect code: the same rare property that makes the Golay code the star of this lesson.
Click any corner of the cube to receive that word and watch the decoder look for the nearest codeword.
Distance here is counted in flipped bits rather than in metres, but everything else about it is ordinary geometry: it is symmetric, it obeys the triangle inequality, and a ball of radius t around a word is the set of everything within t flips. A code of minimum distance d keeps its codewords at least d apart, so balls of radius ⌊(d−1)/2⌋ can never intersect — and disjoint balls mean the nearest centre is always the one the message was sent from.
Try it: Step through the three codes and watch the coloured neighbourhoods separate. Then click corners of the cube to play the receiver: at d = 2 the odd-weight words are dashed because three different codewords are tied for nearest, and at d = 3 every corner belongs to exactly one ball — no ties, no leftovers, a perfect code.
In June 1949 the Swiss-American physicist Marcel Golay published a note in the Proceedings of the IRE. It ran to half a page, contained no proofs, and quietly presented what has been called the best single published page in coding theory. Among the codes he listed was one taking 12 bits of message to 24 bits of transmission, with the property that any two of its 4,096 codewords differ in at least 8 places. Spheres of radius 3 around those codewords are therefore disjoint, and any 3 errors in 24 bits are repairable.
Thirty years later that half page was flying past the outer planets. Voyager 1 and 2 encoded their images of Jupiter and Saturn with the Golay code, spending half of a very expensive radio budget on redundancy in exchange for pictures that survived the trip. The demo below is the genuine article: a real encoding by the generator matrix, real random bit flips, and a decoder that honestly searches all 4,096 codewords for the nearest one.
Click any bit to change the message. All 4,096 of them are legal.
The code is systematic: the first twelve bits are the message, and the last twelve are check bits built from the quadratic residues mod 11. Any two of the 4,096 codewords differ in at least 8 places.
Received word. Flipped positions: 4, 17
Nearest codeword, 2 flips away. Recovered message 100011010110 versus sent 100011010110
800 random transmissions, 800 honest nearest-codeword searches. The boundary between 3 and 4 is not a slope; it is a wall.
The decoder here is deliberately unsophisticated: it compares the received word against all 4,096 codewords and keeps the closest one, which is precisely the geometric picture of “which sphere did this land in?”. Real hardware uses syndrome tables instead and gets the same answer thousands of times faster — the geometry is what decides the outcome, not the algorithm.
Try it: Walk the noise slider up from 0. Through 3 errors the message always comes back exactly, however many times you re-roll. At 4 the decoder stops and admits defeat — that is the received word landing in the gap between spheres. At 5 something worse happens: it repairs the block confidently and hands you the wrong message, every time. Then run the 100 trials and look at the shape of the column: not a slope, a wall.
Why should such a code exist? Count the room available. A sphere of radius 3 in 24-bit Hamming space holds 1 + 24 + 276 + 2,024 = 2,325 words, and 4,096 × 2,325 = 9,523,200, while the whole space has 2²⁴ = 16,777,216 words. The spheres fit with room to spare — and the shortened [23, 12, 7] version of the code fits with no room at all, filling its space exactly. It is one of only a handful of perfect codes that exist in any dimension over any alphabet, a list so short it has been completely classified.
The structure behind the fit is startling. The 759 codewords of weight 8 — the octads — have the property that any five of the 24 coordinates lie in exactly one of them. Five points determine the remaining three with no choice left over. That is a Steiner system S(5, 8, 24), and it is the reason five errors always fool the decoder in the previous demo: the five flipped positions pick out their unique octad, and that octad is a codeword sitting exactly three flips from the received word, wearing a perfect disguise.
The 24 coordinates in the 4 × 6 arrangement Curtis called the Miracle Octad Generator — the layout in which the code’s symmetries become visible.
100000000000101000111011
Support: 0, 12, 14, 18, 19, 20, 22, 23
Every octad is a codeword of weight exactly 8, and any two of them meet in 0, 2 or 4 places — never in 1, 3, 5 or 6. That rigidity is what forces the minimum distance up to 8: the difference of two octads is another codeword, and it cannot be light.
Bars are drawn on a square-root scale so the two lonely words at weights 0 and 24 stay visible. Note what is missing: there is no codeword of weight 1 through 7, none of weight 9, 10 or 11. Every weight is a multiple of four — the code is doubly even — and that empty band below 8 is the elbow room the spheres need.
Try it: Scrub through all 759 octads in the 4 × 6 grid Robert Curtis named the Miracle Octad Generator, then switch to the Steiner mode and pick any five cells you like — including deliberately awkward ones. The demo filters all 759 octads and finds exactly one, never zero and never two. The bookkeeping is airtight: 759 × 56 = 42,504, which is precisely the number of ways to choose 5 things from 24.
In 1967 John Leech, a Glasgow mathematician who had been stacking spheres in high dimensions for years, stopped treating the Golay code as a list of bit patterns and started treating it as a list of coordinates. A codeword tells you which of 24 coordinates get a minus sign; an octad tells you which eight coordinates are occupied. Follow that instruction and a lattice falls out of the code — the Leech lattice, the densest packing in 24 dimensions, proven optimal by Maryna Viazovska and her collaborators in 2016.
Its minimal vectors — the ones touching the sphere at the origin — come in exactly three shapes, and the census is pure Golay arithmetic. There are 276 pairs of coordinates with 4 sign choices, giving 1,104. There are 759 octads with 128 admissible sign patterns, giving 97,152. And there are 4,096 codewords with 24 choices of which coordinate to stretch, giving 98,304. Add them: 196,560, the kissing number in 24 dimensions, a number Odlyzko and Sloane had already proved unbeatable in 1979.
The eight ±2 entries sit exactly on the support of a Golay octad — 0, 12, 14, 18, 19, 20, 22, 23. Eight copies of 2² make 32. Half of the 256 sign patterns are admissible, which is where the 128 comes from.
Nothing in this construction is tuned or fitted. Choose the ingredients however you like and the squared length comes out 32 every single time, because the Golay code’s weights are all multiples of four and any two codewords overlap in an even number of places. The code is not an analogy for the lattice; it is the lattice, written in bits. See also: E8 and the Leech Lattice for what this lattice looks like once it is built, and why 196,560 is provably the end of the line.
Try it: Pick a shape and assemble a minimal vector from its ingredients — a random octad and a sign pattern, or a random codeword and a coordinate to triple. The squared length lands on 32 every time, which is a squared length of 4 after the 1/√8 scaling, and it does so for all 196,560 of them. That is what it means for a code to be a packing.
The rest of the story belongs to group theory. In 1968 John Conway sat down to compute the symmetries of Leech’s lattice, and by the end of a single day’s calculation he had a group of order about 8 × 10¹⁸ and three brand-new sporadic simple groups. Twelve of the twenty-six sporadic simple groups are involved in that one symmetry group. A half-page note about radio noise became a lattice, and the lattice became some of the strangest objects in mathematics. See also: E8 and the Leech Lattice for the packings themselves, and Error-Correcting Codes for Hamming, syndromes and Reed–Solomon.