The best a code can be

A code is a set of corners of a cube, chosen far apart, and everything a code can do is decided by how far apart they are. The rungs below this one build three: the Hamming code whose balls fill the space exactly, its decoder, and Reed–Solomon’s polynomial through the gaps.

Each of those answers a question of the form does a code with these parameters exist? by producing one. None of them answers the question that decides whether a construction is worth having, which is whether anything better exists.

That question has a name — $A(n, d)$, the largest number of binary words of length $n$ with every two at distance at least $d$ — and no formula. It can be computed at small lengths, and computing it is more informative than any of the bounds that stand in for it.

What the search does #

Two words are compatible when they are at least $d$ apart. The best code is the largest set of mutually compatible words — a maximum clique in a graph whose vertices are all $2^n$ words.

That is an expensive computation in general and it is exact here, for three reasons worth stating because each is a place a shortcut could have been taken and was not.

The zero word is fixed in the code. Translating a binary code by any fixed word — adding it to every codeword — preserves every distance, so some best code contains zero, and searching only those loses nothing.

The search stops when it reaches the sphere-packing bound. Nothing can exceed that bound, so a search that attains it has finished, which is why length 7 costs almost nothing and length 6 costs the most.

And the node budget is asserted rather than trusted. The search reports whether it exhausted the space or ran out of budget, and the figure refuses to draw at all in the second case. A number that is only the best found within a budget must never be printed as the best there is.

Four bounds, and which one is working #

The four bounds in the table are usually presented as a list. Reading them against the exact answer makes them a division of labour.

Singleton. A code of distance $d$ can be recovered from any $n - d + 1$ positions, so at most $2^{n-d+1}$ words are available. It is the loosest bound here by a wide margin — at length 7 it permits 32 where the truth is 16 — and it is loose in binary for a structural reason: it is tight exactly for codes where every set of $n - d + 1$ positions determines the word, and over a two-letter alphabet almost nothing does. Reed–Solomon codes meet it exactly, which is the whole reason they are used, and they live over a large alphabet.

Hamming, or sphere-packing. Balls of radius $\lfloor (d-1)/2 \rfloor$ around the codewords are disjoint, so their total size is at most $2^n$. This is the bound that is met exactly when a perfect code exists, and in the table that happens at length 7 and nowhere else.

Plotkin. When the distance is large relative to the length, the average distance between words in a code cannot exceed a limit that depends on both, and the count collapses. It applies only for $n < 2d + 1$ at odd distances, and where it applies it is exact at every length in the table — which is the most surprising thing in the figure.

Gilbert–Varshamov. The odd one out: a lower bound. A greedy construction — take any word, discard everything within distance $d - 1$ of it, repeat — cannot stop before it has taken $2^n$ divided by the size of a ball of radius $d - 1$. It guarantees 5 words at length 7 where 16 exist, so it is weak at these lengths; asymptotically it is the best lower bound known for binary codes, and no explicit construction has beaten it.

The lengths where the bound is met #

Every length in the first figure is pinned by one bound or another, and the split is clean: Plotkin is exact wherever it applies, and the sphere-packing bound takes over at the first length where it does not.

That is not a general truth and it is worth being precise about what it is. Plotkin’s bound is exact for all $n < 2d + 1$, which is a theorem — the short-length regime is completely solved, and the search here is confirming it rather than discovering it. The sphere-packing bound is exact only at the perfect codes, which are rare: over the binary alphabet the complete list is the repetition codes of odd length, the Hamming codes, and the Golay code of length 23, and that list is a theorem of considerable difficulty.

So the whole interest of $A(n,d)$ lies between those two regimes, at lengths too long for Plotkin and not equal to a perfect code’s. Length 6 at distance 3 is the smallest such case: the search says 8, the sphere-packing bound permits 9, and the gap of one is a fact nobody has a formula for.

That last sentence is the one to carry. The sphere-packing bound counts volume and nothing else: it asks whether the balls could fit, and says nothing about whether they can be placed. At length 7 and distance 5 the volume is available for 4 words and the space cannot hold them, exactly as a box with room for six oranges by volume may take only four.

The alphabet is the hidden parameter #

Three of the four bounds have the same form over any alphabet and behave completely differently, and the reason is worth separating out because it explains why two of the rungs below use different constructions.

Over an alphabet of $q$ letters, Singleton says a code of distance $d$ has at most $q^{n-d+1}$ words. A code meeting it is called maximum distance separable, and over a large alphabet these exist in abundance: Reed–Solomon codes are exactly the codes meeting Singleton’s bound, and they exist at every length up to the alphabet size.

Over two letters they barely exist at all. The complete list of binary codes meeting Singleton’s bound is: the whole space, the repetition code, and the single-parity-check code. Nothing else. So the bound that is tight and useful for a byte-oriented code is, in binary, a bound that permits 32 words where 16 is the truth.

The sphere-packing bound goes the other way. Its balls have size $\sum \binom{n}{i}(q-1)^i$, which grows with the alphabet, so the bound weakens as the alphabet grows and the perfect codes over larger alphabets are correspondingly rarer.

So the choice of alphabet decides which bound is the binding one, and therefore which construction is worth reaching for. A designer working in bits is fighting the sphere-packing bound and will end up near a Hamming length. A designer working in bytes is fighting Singleton’s and will end up with Reed–Solomon. Neither is a preference; each is what the arithmetic in that alphabet permits.

The greedy code, and the surprise in it #

The Gilbert–Varshamov bound is proved by a construction so crude that quoting it feels like a joke: take the words in order, keep each one that is far enough from everything already kept, and stop when there is nothing left to consider.

Run that at length 7 and distance 3 and it produces 16 words, and the 16 come out closed under addition — a linear code, from a rule that never mentions linearity. Since a code of 16 words at length 7 and distance 3 is the Hamming code up to a permutation of the positions, the greedy pass has rediscovered the rung below’s construction without knowing anything about parity checks.

That greedily built binary codes taken in lexicographic order come out linear is true, is not obvious, and is what makes the crude bound better than it has any right to be at short lengths. What it does not do is scale, and the failure arrives immediately: at length 8 and distance 3 the greedy pass returns 16 words, and the exhaustive search finds 20. The greedy construction is optimal at lengths 5, 6 and 7 and suboptimal at 8, which is the first length where the sphere-packing bound is not attained — the same length at which everything else here becomes difficult.

The gap between what the construction achieves and what its own proof guarantees is wider still: the argument establishes 5 words at length 7 where 16 appear. That gap is the whole difficulty of the asymptotic problem. Sixty years of work has produced no explicit binary construction that provably beats the greedy guarantee in the limit, while the greedy construction is easy to run and hard to analyse. The bound is weak, the thing it describes is stronger, and nobody has closed the distance.

What the numbers mean at scale #

The count is the wrong quantity to compare across lengths, since a longer word carries more of everything. The right one is the rate — message bits per transmitted bit, which is $\log_2 A(n,d)$ divided by $n$.

The dips are the useful part. A code of length 4 at distance 3 holds the same 2 words as one of length 3, so the fourth bit is wasted entirely — the rate falls from a third to a quarter and nothing has been gained. Adding a fifth bit doubles the code. Length is not a smooth resource, and the good lengths are the ones where a construction exists, which is why practical codes are always at the Hamming lengths, or at a Reed–Solomon length, or at a length somebody has searched.

The general shape is nevertheless clear and is the reason the whole subject exists. At distance 3 the rate climbs from a third at length 3 to four sevenths at length 7, and it keeps climbing: the cost of correcting one error is a fixed number of check bits, roughly the logarithm of the length, so it is amortised over a longer and longer message. Error correction is nearly free at scale and expensive at small sizes, and every design decision in the subject follows from that.

Where the exact answer stops being available #

The search in these figures runs to length 7 at distance 3, and stops there for a reason worth naming rather than hiding.

At length 8 the sphere-packing bound permits 28 words and the true answer is 20. Because the bound is not attained, the search cannot stop early, and it has to prove that no 21-word code exists — which means exhausting a space of 256 words for a clique of that size. That computation is doable and it is not a computation a figure can carry, and beyond it the difficulty rises steeply: exact values of $A(n,3)$ are known for $n$ up to about 16 and unknown after.

A quantity computable in principle and unknown in practice from about length 17 is an unusual situation in mathematics and it is the ordinary one here. There is no obstruction, no undecidability, nothing deep — the space is finite and the answer exists. It is simply too large to look at, and no theory has replaced the looking.

That is what makes the bounds worth having despite every one of them being loose. A bound is a statement about all lengths at once, obtained without searching any of them, and for the lengths anybody actually transmits at, a bound is the only thing available.

A bound is a shape, not a number #

One reading of the table is worth setting out, because it is how the four bounds are actually used and it is invisible if they are read as a list of inequalities.

Each bound is a curve in the plane of length against rate, and the useful question is never its value at one length but which curve is lowest. Singleton’s curve is a straight line falling from one; the sphere-packing curve falls faster at short lengths and flattens; Plotkin’s is vertical, in the sense that it applies only up to a length and says nothing after; and Gilbert–Varshamov’s is a curve from below.

The region between the best upper curve and the lower one is where the truth lies, and the width of that region at each length is a measure of how little is known. At length 7 and distance 3 the region has collapsed to a point. At length 8 it runs from 16 to 28, and the exhaustive search puts the answer at 20 — inside a region the bounds had left three times too wide.

Asymptotically the region never collapses, and that is the central open problem of the subject: as the length grows with the distance a fixed fraction of it, the Gilbert–Varshamov curve and the best known upper curve do not meet, and neither has moved in decades. Every table like the one above is a finite window onto that gap, and every exact value computed is one more point where the gap is closed by brute force rather than by an idea.

What the pictures cannot show #

Every search here is over binary words at lengths of at most eight, and the interesting regime — where none of the bounds is exact and the exact answer is unknown — begins just past the last row of the table. The figures establish the pattern at the lengths they cover and are evidence for nothing beyond them.

The four bounds are computed and compared and none of them is proved. Each has a short argument and the arguments are different in kind — a projection for Singleton, a volume count for Hamming, an averaging argument for Plotkin, a greedy construction for Gilbert–Varshamov — and only the last is visible in a picture at all.

And the asymptotic question, which is what the subject cares about, is untouched. Whether the Gilbert–Varshamov rate can be beaten by any binary code is open, and the one setting where it has been beaten — algebraic geometry codes over large alphabets — has nothing to do with anything drawn here.

Where the ladder goes next #

Named here as debts. The perfect codes classified, which is the theorem that the list stops at the Hamming and Golay codes and is the reason the sphere-packing bound is almost never exact. And linear codes specifically, whose best sizes are a different and smaller table — every code in the figures is allowed to be arbitrary, and restricting to linear ones costs something at some lengths and nothing at others.

Sideways, the construction that meets the sphere-packing bound is the Hamming code, the one that meets Singleton’s is Reed–Solomon, the geometry the distance lives in is the cube, and the counting that makes a greedy construction work is the same first-moment argument that produces colourings nobody can exhibit.

What is worth carrying away #

A construction answers an existence question, and knowing whether it is any good is a separate computation that is usually harder.

The Hamming code is optimal and the reason is not that it is elegant; it is that the sphere-packing bound happens to be attained at its length, which a count establishes. At the length one longer, no construction is known to be optimal and the true answer was found by search.

The habit worth taking is to ask which bound a construction is meeting, and whether that bound is the binding one. A construction meeting a loose bound has proved nothing about itself, and a construction meeting a tight one needs no further defence.

The corollary is about the value of a lower bound that constructs nothing. Gilbert and Varshamov’s argument produces no code anybody would use and it has never been beaten asymptotically, which means every explicit construction in sixty years has been at best as good as picking words greedily. That is a statement about how hard the problem is, and it is the kind of statement only a non-constructive bound can make.