Parallel planes take a vote

The finite geometries met so far have mostly been curiosities with a few points and many coincidences. Their lines form neat patterns, and it is hard to see what they might be for. The codes in this essay are one answer. Take the simplest of all finite spaces, the coordinate space over the two-element field, and treat each subset of its points as a message. Then the flats of the space, its lines and planes and hyperplanes, turn out to be the words of a very good code, the geometry of parallel flats gives a decoder, and that decoder was used to read the first pictures sent from the orbit of another planet.

These are Reed–Muller codes, from David Muller’s and Irving Reed’s two papers of 1954. They were among the earliest multiple-error-correcting codes, they are entirely geometric, and for more than half a century they were regarded as a simple historic example that could not compete with what came later. The last section of this story arrived in 2016, when it was shown that they reach the limit that Claude Shannon set for noisy channels, and that had not been expected of them.

Words as polynomials on a space #

Let the points of the space be all strings of $m$ bits, so that there are $2^m$ of them. A function from these points to $\{0, 1\}$ can be written down as a table of $2^m$ bits, and it can also be written as a polynomial in $x_1, \ldots, x_m$ with coefficients in the field of two elements. Since $x^2 = x$ on those values, only products of distinct variables are needed. The family member $\mathrm{RM}(r, m)$ consists of the tables of all polynomials of degree at most $r$.

That has an immediate geometric meaning. A polynomial of degree one, such as $x_1 + x_3 + 1$, is the indicator of an affine hyperplane, a set defined by one linear equation. A monomial of degree $r$, such as $x_1 x_2$, is the indicator of a flat of dimension $m - r$, here the set where $x_1 = x_2 = 1$. So its generating words are flats. For $\mathrm{RM}(1, 4)$ there are $2^5 = 32$ words, drawn in full in the first figure on a 4 × 4 grid of the sixteen points. Apart from the all-nought and all-one words, all thirty have weight exactly 8.

The figure shows the most important property of these words, and it has a one-line proof. Two different hyperplanes are either parallel, and so disjoint, or they cross, and then they meet in exactly half of each. So any two words of $\mathrm{RM}(1, 4)$ differ in exactly 8 or 16 places out of 16. Half of the places can be altered before one word starts to look like another. In general, the least weight of a non-zero word in $\mathrm{RM}(r, m)$ is $2^{m-r}$, attained by the flats themselves. This is not obvious for arbitrary polynomials, and it follows by an induction on $m$ that splits the polynomial according to one variable.

These tables come from enumerating every word: $2^{16}$ of them for $\mathrm{RM}(2, 5)$. The result is odd-looking. That code has 620 words of weight 8, then 13,888 at weight 12, then 36,518 at weight 16, and then the same again in reverse, and it has no words whatever at weight 10 or 14. In $\mathrm{RM}(2, m)$ the weights are controlled by the classification of quadratic forms over the two-element field, which Leonard Dickson found in 1901: a form’s rank decides how many points it vanishes on, and the only values that can arise are $2^{m-1} \pm 2^{m-1-h}$ for integer $h$. And the 620 are the 3-flats of the five-dimensional space, exactly the geometric count. For a code with the same parameters found by chance, there would be no such pattern at all. The same structure is what makes the quadratic sums modulo primes so well behaved.

The family contains codes already met elsewhere. $\mathrm{RM}(m - 2, m)$ is the extended form of Hamming’s code, and $\mathrm{RM}(1, 3)$, with eight places and fourteen words of weight 4, is that code at its smallest: its words of weight 4 are the planes of the three-dimensional space, and deleting one point turns them into the lines and their complements of the seven-point plane. There is also a tidy duality. The space perpendicular to $\mathrm{RM}(r, m)$ is $\mathrm{RM}(m - r - 1, m)$, because the product of a polynomial of degree $r$ with one of degree $m - r - 1$ has degree below $m$, and a polynomial of degree below $m$ has an even number of ones. That single line is what allowed the largest table above to be computed from a much smaller one. So what looked like separate inventions are one family of polynomials on one space, with degree as the only dial.

The first-order code has a second name. Writing the two values as $+1$ and $-1$, its words are the rows of a Hadamard matrix, and two different rows are perpendicular except for $\pm$ copies. So the shadows of an inner product apply to it, and a word can be decoded by finding which row it has the largest inner product with.

Reed’s vote #

The decoder is the part that is purely geometric. Take $\mathrm{RM}(2, 4)$. Suppose the word sent is the table of some quadratic polynomial $f$. How can the coefficient of $x_1 x_2$ be read from the table?

The answer is to add up the values of $f$ over a plane parallel to the directions $x_1$ and $x_2$. Over such a plane, $x_3$ and $x_4$ are fixed. Adding over all four points of the plane kills every term that depends on fewer than both $x_1$ and $x_2$, because such a term appears an even number of times, and it leaves exactly the coefficient of $x_1 x_2$. So one plane gives the coefficient by a sum of four bits. And there are four such parallel planes, one for each setting of $x_3$ and $x_4$, with no point in common. Each gives an independent reading of the same bit.

An error in one place lands in exactly one plane of each family, and spoils exactly one vote. So the majority gets it right. In the figure, the coefficient of $x_1 x_2$ gets votes 1, 0, 1, 1, the coefficient of $x_3 x_4$ gets 1, 1, 0, 1, and the coefficient of $x_1 x_3$ gets 0, 1, 0, 0. All three majorities match the true values. After the top coefficients are found, subtract their contribution and repeat at the next degree, where each coefficient gets more votes because the flats are larger. Reed’s argument of 1954 shows that this corrects any pattern of fewer than $2^{m-r-1}$ errors. It was the first multiple-error-correcting decoder that did not require a search through all the words, and its simplicity made it attractive on the very limited electronics of its day.

Something striking has happened. An algebraic fact, that a sum over a flat picks out a top coefficient, has been combined with a geometric one, that parallel flats partition the space. Neither mentions errors, and together they yield an error-correcting decoder. This is a clear instance of the use of parallelism in an affine plane, and it is the sort of thing that makes finite geometry pay off in engineering.

The transform on the way back from Mars #

For the first-order codes there is a much more powerful decoder, which uses every place of the word at once. It compares the received word, written in $\pm 1$, with every one of the linear words of $\mathrm{RM}(1, m)$. Doing this directly costs $n^2$ operations for a length of $n$. But those comparisons have the structure of a discrete Fourier transform on the group of bit strings, so that they can be computed in $n \log_2 n$ additions by the fast Hadamard transform. It is the same butterfly as the fast Fourier transform, on a different group.

For $\mathrm{RM}(1, 5)$, length 32, that is 160 additions. With seven of the 32 places wrong, as in the figure, the true word reaches 18 and no other exceeds 14, and that comparison is what a minimum distance of 16 guarantees: seven errors can always be corrected. The sign of the peak gives the sixth bit, the coefficient of the constant term.

$\mathrm{RM}(1, 5)$ flew on Mariner 9, which reached Mars in November 1971 and was the first spacecraft to orbit another planet. Each pixel of its television pictures had 64 shades of grey and so six bits, and it was sent as a 32-place word. On the ground, a machine called the “Green machine”, after its designer Robert Green at the Jet Propulsion Laboratory, did the transform in hardware.

The numbers justify the choice. With a flip chance of 5%, a plain six-bit pixel is wrong 26.5% of the time. The bound for the word of 32 places, counting any eight or more flips in a word as a failure, is $1.4 \times 10^{-4}$. In 20,000 sampled words at each noise level, decoding does better even than this, at 0.00025 for 8% flips and 0.00145 for 10%, since a pattern of eight or more errors does not necessarily land nearer to another word. A code that spends more than five bits per bit carried is inefficient by any modern standard. But the limit on a spacecraft was power, not bandwidth, and a low-rate code that has a fast decoder was exactly what was wanted. The Voyager spacecraft moved on, to a Golay code and then to more advanced ones, for the better rate.

A vote that needs only a few places #

Reed’s sum over a flat has a stronger consequence, and it took until the 1990s to be seen. A polynomial of degree $r$ sums to nought over every flat of dimension $r + 1$, so whether a table has low degree can be tested by looking at only $2^{r+1}$ places chosen at random. For degree one that is three places: check that $f(x) + f(y) = f(x + y)$. Manuel Blum, Michael Luby and Ronitt Rubinfeld proved in 1990 that a table passing this test often must be close to a true linear function, which is a surprise, since the test only looks at three of its $2^m$ entries. A long message can therefore be checked without being read. Tests of this kind, for polynomials of low degree, are a central part of the theorem that a proof can be checked at a few random places, the PCP theorem of the early 1990s. The word is a proof, and the vote of a flat becomes a query. Decoding and verifying turned out to depend on the same structure, and it carries over from locating an error without reading the message to locating a false claim without reading the proof.

The second life #

The tables and the decoder belong to the 1950s and 1970s. For a long time the textbook summary was that Reed–Muller codes have poor distance at long lengths when the rate is held fixed: at rate one half the minimum distance is only about $\sqrt n$, which is nothing like the linear distance of the best codes, and no one expected them to approach Shannon’s capacity. A code with so small a distance must have some bad error patterns. What was not appreciated was how few such patterns there might be.

In 2016 Shrinivas Kudekar, Santhosh Kumar, Marco Mondelli, Henry Pfister, Eren Şaşoğlu and Rüdiger Urbanke, two groups working on it who then published together, proved that Reed–Muller codes reach capacity on the erasure channel. The proof is remarkable for its method. Each Reed–Muller code has an enormous symmetry group, since every affine map of the space preserves it. And a monotone property that is invariant under a transitive group has a sharp threshold, by a theorem of Ehud Friedgut and Gil Kalai. Being decodable from a random erasure pattern is exactly such a property. So the transition from “always recoverable” to “never recoverable” has to be sharp, and an easy counting argument then says where it is. No analysis of decoding was needed at all.

The figure measures that. A word can be recovered from erasures exactly when the surviving rows of the table of monomials have full rank, and that can be computed by elimination over two elements without any decoder. For a length of 64 and rate 0.656, the limit is an erasure share of 0.344. Recovery falls below 90% already at a share of 0.256. For length 256 and a limit of 0.363, it holds at 90% until 0.315. For length 1,024 and a limit of 0.377, it holds until 0.359. The rates differ slightly because these are the nearest available codes, so the three curves have somewhat different limits. The distance from the limit to the 90% point falls from 0.088 to 0.048 to 0.018, each time the length is multiplied by four. That is the sharpening that the theorem describes.

Then in 2021, Galen Reeves and Henry Pfister proved that the codes also reach capacity on the binary symmetric channel in the sense of bit error, and Emmanuel Abbe and Colin Sandon proved in 2023 a block-error version, using completely different tools. So polar codes, which were explicitly designed to reach capacity in 2008, and which have a closely related structure, are not the only explicit long codes that do so. A code defined by low-degree polynomials on a very simple geometry was already good enough, and nobody knew for sixty years.

The reach of these figures #

The figures cover short codes. A length of 1,024 is enough to see the erasure threshold beginning to steepen, and it says nothing about the limit itself, which is a theorem. The Hadamard figure shows one random noise pattern, and the error-correction property was stated and proved by the distance, not by that example. Above all, nothing here decodes a long Reed–Muller code from errors. Rank is an exact criterion for erasures, but for errors, the optimal decoder is a search through exponentially many words. There are algorithms that come close at moderate lengths, among them recursive projection-aggregation, introduced by Min Ye and Abbe in 2020, which uses exactly this geometry and projects a word onto its cosets. They run in time that grows quickly, and no decoder for the capacity-achieving regime is known to run in practical time at long lengths.

What was computed and what was quoted #

All words were enumerated up to $2^{16}$ for the tables, and the largest table, for $\mathrm{RM}(3, 5)$, was calculated from its small dual by the MacWilliams identity. The published values for $\mathrm{RM}(2, 5)$ were checked to match. The votes and the Hadamard example are single exact runs. The pixel-error simulation used 20,000 seeded words at each noise level, with the bound calculated exactly. The rank experiments used 200 trials at lengths 64 and 256 and 40 at length 1,024, so the 90% points are approximate to a step or two.

The attributions, the Mariner hardware, the distance theorem’s induction, the theorem of Dickson and the capacity results are quoted. In particular, the sharp-threshold proof was described only in outline. The 2021 and 2023 results were not tested here.

Still open: decoding and the weights #

Is there a polynomial-time decoder for Reed–Muller codes that reaches capacity from errors? The existence results do not construct a decoder. Polar codes have an efficient one, and it is this which made them useful in practice, in the control channels of 5G mobile standards. For a Reed–Muller code at constant rate, what the best fast decoder can do is an active question.

There are also structural questions of a pure kind. The weight distribution of $\mathrm{RM}(r, m)$ has no known formula for general $r$, beyond $r = 2$ and the words of weight below $2.5$ times the minimum, as Tadao Kasami and Nobuki Tokura found. An upper bound on how many low-weight words there are, due to Kaufman, Lovett and Porat, and improved in later work, played a part in the capacity proofs for errors. But the exact count of words for an $\mathrm{RM}(3, 8)$ or the like, which would take a very large enumeration, is known only at small sizes. The table above reaches the point where it would become infeasible to go on enumerating, and it is close to the edge of the known exact list.

Flats, votes and a threshold #

The words of a Reed–Muller code are the indicator functions of flats and their sums, parallel flats partition the space, and so a top coefficient gets many independent votes. That single picture gives the distance and the decoder, and it was good enough to bring back the first pictures from the orbit of Mars.

What the original authors could not have seen is the role of symmetry. The same affine maps that make the flats so regular also force an erasure threshold to be sharp, and the sharpness puts that threshold at Shannon’s limit, without any analysis of how the decoding works. A construction from 1954 on the simplest space there is turned out to reach a limit that its authors would have considered out of reach, for reasons that took sixty years to find.