Error-Correcting Codes

I’M SORRY, DID YOU SAY “BOFAB”?

The Fano plane tells you how to play the seven-number Transylvanian lottery without taking on any risk, but what about the Massachusetts lottery? There are lots of finite geometries with more than seven points, but none, unfortunately, that precisely meet the requirements of Cash WinFall. Something more general is needed. The answer doesn’t come directly from Renaissance painting or Euclidean geometry, but from another unlikely source—the theory of digital signal processing.

Suppose I want to send an important message to a satellite, like “Turn on right thruster.” Satellites don’t speak English, so what I’m actually sending is a sequence of 1s and 0s, what computer scientists call bits:

1110101 . . .

This message seems crisp and unambiguous. But in real life, communication channels are noisy. Maybe a cosmic ray strikes the satellite just as it’s receiving your transmission and garbles one bit of the message, so that the satellite receives

1010101 . . .

That message doesn’t seem very different; but if the changing of the bit switches the instruction from “right thruster” to “left thruster,” the satellite might be in for serious trouble.

Satellites are expensive, so this is trouble you really want to avoid. If you were trying to talk to a friend at a noisy party, you might have to repeat yourself to keep the noise from drowning out your message. The same trick works with the satellite; in our original message, we can repeat each bit twice, sending 00 instead of 0 and 11 instead of 1:

11 11 11 00 11 00 11 . . .

Now, when the cosmic ray strikes the second bit of the message, the satellite sees

10 11 11 00 11 00 11 . . .

The satellite knows that each two-bit segment is supposed to be either 00 or 11, so that initial “10” is a red flag; something has gone wrong. But what? That’s tough for the satellite to figure out: since it doesn’t know exactly where the noise corrupted the signal, there’s no way to tell whether the original message started with 00 or 11.

This problem, too, can be fixed. Just repeat three times instead of twice:

111 111 111 000 111 000 111 . . .

The message comes through corrupted, like this:

101 111 111 000 111 000 111 . . .

But now the satellite is in good shape. That first three-bit segment, it knows, is supposed to be 000 or 111, so the presence of 101 means something’s gone awry. But if the original message was 000, two bits must have been corrupted in very close proximity, an unlikely event as long as the frequency of message-zapping cosmic rays is pretty small. So the satellite has good reason to let majority rule: if two out of the three bits are 1, the odds are very good that the original message was 111.

What you’ve just witnessed is an example of an error-correcting code, a communications protocol that allows the receiver to cancel out the errors in a noisy signal.[*] The idea, like basically everything else in information theory, comes from Claude Shannon’s monumental 1948 paper, “A Mathematical Theory of Communication.”

A mathematical theory of communication! Doesn’t that sound a little grandiose? Isn’t communication a fundamentally human activity that can’t be reduced to cold numbers and formulas?

Understand this: I warmly endorse, in fact highly recommend, a bristly skepticism in the face of all claims that such-and-such an entity can be explained, or tamed, or fully understood, by mathematical means.

And yet the history of mathematics is a history of aggressive territorial expansion, as mathematical techniques get broader and richer, and mathematicians find ways to address questions previously thought of as outside their domain. “A mathematical theory of probability” sounds unexceptional now, but once it would have seemed a massive overreach; math was about the certain and the true, not the random and the maybe-so! All that changed when Pascal, Bernoulli, and others found mathematical laws that governed the workings of chance.[*] A mathematical theory of infinity? Before the work of Georg Cantor in the nineteenth century, the study of the infinite was as much theology as science; now we understand Cantor’s theory of multiple infinities, each one infinitely larger than the last, well enough to teach it to first-year math majors. (To be fair, it does kind of blow their minds.)

These mathematical formalisms don’t capture every detail of the phenomena they describe, and aren’t intended to. There are questions about randomness, for instance, about which probability theory is silent. To some people, the questions that stay outside the reach of math are the most interesting ones. But to think carefully about chance, nowadays, without having probability theory somewhere in mind is a mistake. If you don’t believe me, ask James Harvey. Or, better yet, ask the people whose money he won.

Will there be a mathematical theory of consciousness? Of society? Of aesthetics? People are trying, that’s for sure, with only limited success so far. You should distrust all such claims on instinct. But you should also keep in mind that they might end up getting some important things right.

The error-correcting code does not at first seem like revolutionary mathematics. If you’re at a noisy party, repeat yourself—problem solved! But that solution has a cost. If you repeat every bit of your message three times, your message takes three times as long to transmit. That might not be a problem at a party, but it could be a problem if you need the satellite to turn on its right thruster right this second. Shannon, in the paper that launched the theory of information, identified the basic tradeoff that engineers still grapple with today: the more resistant to noise you want your signal to be, the slower your bits are transmitted. The presence of noise places a cap on the length of a message your channel can reliably convey in a given amount of time; this limit was what Shannon called the capacity of the channel. Just as a pipe can handle only so much water, a channel can handle only so much information.

But fixing errors doesn’t require you to make your channel three times skinnier, as the “repeat three times” protocol does. You can do better—and Shannon knew this perfectly well, because one of his colleagues at Bell Labs, Richard Hamming, had already figured out how.

Hamming, a young veteran of the Manhattan Project, had low-priority access to Bell’s ten-ton Model V mechanical relay computer; he was allowed to run his programs only on the weekends. The problem was that any mechanical error could halt his computation, with no one available to start the machine running again until Monday morning. This was annoying. And annoyance, as we know, is one of the great spurs to technical progress. Wouldn’t it be better, Hamming thought, if the machine could correct its own errors and keep on plugging? And so he developed a plan. The input to the Model V can be thought of as a string of 0s and 1s, just like the transmission to the satellite—the math doesn’t care whether those digits are bits in a digital stream, the states of an electrical relay, or holes in a strip of tape (at the time, a state-of-the-art data interface).

Hamming’s first step was to break the message up into blocks of three symbols:

111 010 101 . . .

The Hamming code [*] is a rule that transforms each of these three-digit blocks into a seven-digit string. Here’s the codebook:

000 -> 0000000

001 -> 0010111

010 -> 0101011

011 -> 0111100

101 -> 1011010

110 -> 1100110

100 -> 1001101

111 -> 1110001

So the encoded message would look like

1110001 0101011 1011010. . . .

Those seven-bit blocks are called code words. The eight code words are the only blocks the code allows; if the receiver sees anything else coming over the wire, something has gone wrong for sure. Say you receive 1010001. You know this can’t be right, because 1010001 isn’t a code word. What’s more, the message you received differs in only one place from the code word 1110001. And there’s no other code word that’s so close to the messed-up transmission you actually saw. So you can feel pretty safe in guessing that the code word your correspondent meant to send was 1110001, which means that the corresponding 3-digit block in the original message was 111.

You might think we just got lucky. What if the mystery transmission had been close to two different code words? Then we wouldn’t be able to make a confident judgment. But that can’t happen, and here’s why. Look again at the lines in the Fano plane:

124

135

167

257

347

236

456

How would you describe this geometry to a computer? Computers like to be talked to in 0s and 1s, so write each line as a string of 0s and 1s, where a 0 in place n stands for “point n is on the line” and a 1 in place n means “point n is not on the line.” So that first line, 124, gets represented as

0010111

and the second line, 135, is

0101011

You’ll notice that both strings are code words in the Hamming code. In fact, the seven nonzero code words in the Hamming code match up exactly to the seven lines in the Fano plane. The Hamming code and the Fano plane (and, for that matter, the optimal ticket combo for the Transylvanian lottery) are exactly the same mathematical object in two different outfits!

This is the secret geometry of the Hamming code. A code word is a set of three points in the Fano plane that form a line. Flipping a bit in the string is the same thing as adding or deleting a point, so as long as the original code word wasn’t 0000000, the bollixed transmission you get corresponds to a set with either two or four points.[] If you receive a two-point set, you know how to figure out the missing point; it’s just the third point on the unique line that joins the two points you received. What if you receive a four-point set of the form “line plus one extra point?” Then you can infer that the correct message consists of those three points in your set that form a line. A subtlety presents itself: how do you know there’s only one way of choosing such a set of three points? It helps if we give our points names: call them A, B, C, and D. If A, B, and C all lie on a line, then A, B, and C must be the set of points your correspondent meant to send. But what if A, C, and D also lie along a line? No worries: this is impossible, because the line containing A, B, and C and the line containing A, C, and D would then have the two points A and C in common. But two lines can intersect only in one point; that’s the rule.[] In other words, thanks to the axioms of geometry, the Hamming code has the same magical error-correcting property as “repeat three times”; if a message gets modified by a single bit en route, the receiver can always figure out what message the transmitter meant to send. But instead of multiplying your transmission time by three, your new improved code sends just seven bits for every three bits of your original message, a more efficient ratio of 2.33.

The discovery of error-correcting codes, both Hamming’s first codes and the more powerful ones that came later, transformed the engineering of information. The goal no longer had to be building systems so heavily shielded and double-checked that no error could ever arise. After Hamming and Shannon, it sufficed to make errors rare enough that the flexibility of the error-correcting code could counteract whatever noise got through. Error-correcting codes are now found wherever data needs to be communicated quickly and reliably. The Mars orbiter Mariner 9 sent pictures of the Martian surface back to Earth using one such code, the Hadamard code. Compact discs are encoded with the Reed-Solomon code, which is why you can scratch them and they still sound perfect. (Readers born after, say, 1990 who are unfamiliar with compact discs can just think of flash drives, which use among other things the similar Bose-Chaudhuri-Hocquenghem codes to avoid data corruption.) Your bank’s routing number is encoded using a simple code called a checksum. This one is not quite an error-correcting code, but merely an error-detecting code like the “repeat each bit twice” protocol; if you type one digit wrong, the computer executing the transfer may not be able to puzzle out what number you actually meant, but it can at least figure out something’s wrong and avoid sending your money to the wrong bank.

It’s not clear whether Hamming understood the full range of applications of his new technique, but his bosses at Bell certainly had some idea, as Hamming found out when he tried to publish his work:

The Patent Department would not release the thing until they had patent coverage. . . . I didn’t believe that they could patent a bunch of mathematical formulas. I said they couldn’t. They said, “Watch us.” They were right. And since then I have known that I have a very weak understanding of patent laws because, regularly, things that you shouldn’t be able to patent—it’s outrageous—you can patent.

Math moves faster than the patent office: The Swiss mathematician and physicist Marcel Golay learned about Hamming’s ideas from Shannon, and developed many new codes of his own, not knowing that Hamming himself had worked out many of the same codes behind the patent curtain. Golay published first, leading to a confusion about credit that persists to the present day. As for the patent, Bell got it, but lost the right to charge for the license as part of an antitrust settlement in 1956.

What makes the Hamming code work? To understand this, you have to come at it from the other direction, asking: What would make it fail?

Remember, the bête noire of an error-correcting code is a block of digits that’s simultaneously close to two different code words. A recipient presented with the offending string of bits would be flummoxed, having no principled way to determine which of the near-miss code words appeared in the original transmission.

It sounds like we’re using a metaphor here: Blocks of binary digits don’t have locations, so what can we mean by saying one is “close” to another? One of Hamming’s great conceptual contributions was to insist that this wasn’t merely a metaphor, or didn’t have to be. He introduced a new notion of distance, now called the Hamming distance, which was adapted to the new mathematics of information just as the distance Euclid and Pythagoras understood was adapted to the geometry of the plane. Hamming’s definition was simple: the distance between two blocks is the number of bits you need to alter in order to change one block into the other. So the distance between the code words 0010111 and 0101011 is 4; in order to get from the former code word to the latter, you have to change the bits in the second, third, fourth, and fifth places.

Hamming’s eight code words are a good code because no block of seven bits is within Hamming distance 1 of two different code words. If it were, the two code words would be within Hamming distance 2 of each other.[*] But you can check for yourself and see that no two of those code words differ in just two places; in fact, any two different code words are at a Hamming distance of at least 4 from each other. You can think of the code words as something like electrons in a box, or antisocial people in an elevator. They’ve got a confined space to live in, and within those constraints, they try to make as much mutual distance from each other as they possibly can.

This same principle underlies all manner of communications that are robust to noise. Natural language works this way: if I write lanvuage instead of language, you can figure out what it was I meant to say, because there’s no other word in English that’s one letter substitution away from lanvuage. This breaks down, of course, when you start looking at shorter words: a dog, a cog, a bog, and a log are all perfectly good things to which one might refer in English, and a burst of noise wiping out the first phoneme makes it impossible to tell which one was meant. Even in this case, though, you can use the semantic distance between those words to help you correct errors. If it bit you, it was probably a dog; if you fell off it, it was probably a log. And so on.

You can make language more efficient—but when you do, you hit the same hard tradeoff Shannon discovered. Many people of a nerdy and/or mathematical persuasion [] have labored to create languages that would convey information compactly and precisely, without any of the redundancy, synonymy, and ambiguity that languages like English indulge themselves in. Ro was an artificial language created in 1906 by the Reverend Edward Powell Foster, who aimed to replace the thicket of English vocabulary with a lexicon in which the meaning of each word could be derived logically from its sound. It’s perhaps no surprise that among the Ro enthusiasts was Melvil Dewey, whose Dewey Decimal System imposed on the stacks of the public library a similarly rigid organization. Ro is indeed admirably compact; lots of long English words, like ingredient, come out much shorter in Ro, where you just say cegab. But the compactness comes at a cost; you lose the error correction English offers as a built-in feature. Small elevator, very crowded, the passengers don’t have much personal space; which is to say, each word in Ro is very close to lots of others, creating opportunities for confusion. The word for “color” in Ro is bofab. But if you change one letter, to make it bogab, you have the word for “sound.” Bokab means “electricity” and bolab means “flavor.” Worse still, the logical structure of Ro leads similar-sounding words to have similar meanings too, making it impossible to figure out what’s going on from context. Bofoc, bofof, bofog, and bofol mean “red,” “yellow,” “green,” and “blue,” respectively. It makes a certain kind of sense to have conceptual similarity represented in sound; but it also makes it very difficult to talk about color in Ro at a crowded party. “I’m sorry, was that ‘bofoc’ or ‘bofog’?”[]

Some modern constructed languages, on the other hand, go the other way, making explicit use of the principles Hamming and Shannon laid out; Lojban, one of the most successful contemporary examples,[*] has a strict rule that no two of the basic roots, or gismu, are allowed to be too phonetically close.

Hamming’s notion of “distance” follows Fano’s philosophy—a quantity that quacks like distance has the right to be called distance. But why stop there? The set of points at distance less than or equal to 1 from a given central point has a name in Euclidean geometry; it is called a circle, or, if we are in higher dimensions, a sphere.[] So we’re compelled to call the set of strings at Hamming distance at most 1[] from a code word a “Hamming sphere,” with the code word at the center. For a code to be an error-correcting code, no string—no point, if we’re to take this geometric analogy seriously—can be within distance 1 of two different code words; in other words, we ask that no two of the Hamming spheres centered at the code words share any points.

So the problem of constructing error-correcting codes has the same structure as a classical geometric problem, that of sphere packing: how do we fit a bunch of equal-sized spheres as tightly as possible into a small space, in such a way that no two spheres overlap? More succinctly, how many oranges can you stuff into a box?

The sphere-packing problem is a lot older than error-correcting codes; it goes back to the astronomer Johannes Kepler, who wrote a short booklet in 1611 called Strena Seu De Nive Sexangula, or “The Six-Cornered Snowflake.” Despite the rather specific title, Kepler’s book contemplates the general question of the origin of natural form. Why do snowflakes and the chambers of honeycombs form hexagons, while the seed chambers of an apple are more apt to come in fives? Most relevantly for us right now: why do the seeds of pomegranates tend to have twelve flat sides?

Here’s Kepler’s explanation. The pomegranate wants to fit as many seeds as possible inside its skin; in other words, it is carrying out a sphere-packing problem. If we believe nature does as good a job as can be done, then these spheres ought to be arranged in the densest possible fashion. Kepler argued that the tightest possible packing was obtained as follows. Start with a flat layer of seeds, arranged in a regular pattern like so:

The next layer is going to look just the same as this one, but cunningly placed so that each seed sits in the little triangular divot formed by three seeds below it. Then just keep adding more layers in the same way. It’s best to be a little careful here: only half the divots are going to support spheres in the next layer up, and at each stage you have a choice of which half of the divots you want to fill. The most customary choice, called the face-centered cubic lattice, has the nice property that every layer has the spheres placed directly over the spheres three layers below. According to Kepler, there is no denser way to pack spheres in space. And in the face-centered cubic lattice, each sphere touches exactly twelve others. As the pomegranate seeds grew, Kepler reasoned, each one would press against its twelve neighbors, flattening its surface near the point of contact and producing the twelve-sided figures he observed.

Whether Kepler was right about pomegranates I have no idea,[] but his claim that the face-centered cubic lattice was the densest possible sphere packing became a topic of intense mathematical interest for centuries. Kepler offered no proof of his statement; apparently it just seemed right to him that the face-centered cubic lattice couldn’t be beat. Generations of grocers, who stack oranges in a face-centered cubic configuration without any worry as to whether their method is the absolute best possible, agree with him. Mathematicians, that demanding tribe, wanted absolute confirmation. And not just about circles and spheres; once you’re in the realm of pure mathematics, nothing stops you from going beyond circles and spheres to yet higher dimensions, packing the so-called hyperspheres of dimension greater than 3. Does the geometric story of high-dimensional sphere packings give insight into the theory of error-correcting codes, as the geometric story of the projective plane did? In this case, the flow has mostly been in the other direction;[] the insights from coding theory have instigated progress in sphere packings. John Leech, in the 1960s, used one of Golay’s codes to build an incredibly dense packing of twenty-four-dimensional spheres, in a configuration now known as the Leech lattice. It’s a crowded place, the Leech lattice, where each of the twenty-four-dimensional spheres touches 196,560 of its neighbors. We still don’t know whether it’s the tightest possible twenty-four-dimensional packing, but in 2003, Henry Cohn [*] and Abhinav Kumar proved that if a denser lattice exists, it beats Leech by a factor of at most

1.00000000000000000000000000000165.

In other words: close enough.

You can be forgiven for not caring about twenty-four-dimensional spheres and how to smoosh them together, but here’s the thing: any mathematical object as startling as the Leech lattice is bound to be important. It turned out that the Leech lattice was very rich in symmetries of a truly exotic kind. The master group theorist John Conway, upon encountering the lattice in 1968, worked out all its symmetries in a twelve-hour spree of computation on a single giant roll of paper. These symmetries ended up forming some of the final pieces of the general theory of finite symmetry groups that preoccupied algebraists for much of the twentieth century.[*]

—

As for good old three-dimensional oranges, it turns out Kepler was right that his packing was the best possible—but that wasn’t proved for almost four hundred years, finally falling in 1998 to Thomas Hales, then a professor at the University of Michigan. Hales settled the matter by means of a difficult and delicate argument that reduced the problem to an analysis of a mere few thousand configurations of spheres, which he dealt with by means of a massive computer calculation. The difficult and delicate argument posed no problem for the math community; we’re used to those, and this part of Hales’s work was quickly judged and found correct. The massive computer calculation, on the other hand, was trickier. A proof can be checked down to the last detail, but a computer program is a different sort of thing. In principle, a human can check every line of code; but even having done so, how can you be sure the code ran correctly?

Mathematicians have almost universally accepted Hales’s proof, but Hales himself seems to have been stung by the initial discomfort with the proof’s reliance on computation. Since the resolution of the Kepler conjecture, he’s moved away from the geometry that made him famous and turned instead to the project of formal verification of proofs. Hales envisions, and is working to create, a future mathematics that looks very different from our own. In his view, mathematical proofs, whether computer-aided or carried out by humans with pencils, have gotten so complicated and interdependent that we can no longer reasonably have full confidence in their correctness. The classification of finite simple groups, the now-completed program of which Conway’s analysis of the Leech lattice formed a crucial part, is distributed over hundreds of papers by hundreds of authors, totaling some ten thousand pages. No human alive can be said to understand it all. So how can we be sure it’s really right?

Hales thinks we have no choice but to start over again, rebuilding the vast corpus of mathematical knowledge within a formal structure that can be verified by machine. If the code that checks the formal proofs is itself checkable (and this, Hales convincingly argues, is a feasible goal) then we can free ourselves forevermore from controversies like the one Hales endured over whether a proof is really a proof. And from there? The next step, maybe, is computers that can construct proofs, or even have ideas, without any human intervention at all.

If this actually happens, is mathematics over? Of course, if machines overtake and then surpass humans in all mental dimensions, using us as slaves or livestock or playthings, as some of the most extravagant futurists predict, then yeah, math is over, along with everything else. But short of that, I think mathematics will probably survive. After all, math has already been computer-aided for decades. Many calculations that once would have counted as “research” are now considered no more creative or praiseworthy than adding a series of ten-digit numbers; once your laptop can do it, it’s not mathematics anymore. But this hasn’t put mathematicians out of work. We’ve managed to stay just ahead of the ever-increasing sphere of computer dominance, like action heroes outracing a fireball.

And if machine intelligences of the future can take over from us much of the work we know as research now? We’ll reclassify that research as “computation.” And whatever we quantitatively minded humans are doing with our newly freed-up time, that’s what we’ll call “mathematics.”

The Hamming code is pretty good, but one might hope to do better still. After all, there’s something wasteful about Hamming’s code: even in the days of punched tape and mechanical relays, computers were reliable enough that almost all seven-bit blocks would come through unscathed. The code seems too conservative; surely we could get away with adding fewer failsafe bits to our message. And so we can; that’s what Shannon’s famous theorem proves. For example, if errors come at a rate of one per thousand bits, Shannon tells you there are codes that make each message only 1.2% longer than its unencoded form. And better yet, by making the basic blocks longer and longer, you can find codes that achieve this speed and satisfy any desired degree of reliability, however strict.

How did Shannon construct these excellent codes? Well, here’s the thing—he didn’t. When you encounter an intricate construction like Hamming’s, you’re naturally inclined to think an error-correcting code is a very special thing, designed and engineered and tweaked and retweaked until every pair of code words has been gingerly nudged apart without any other pair being forced together. Shannon’s genius was to see that this vision was totally wrong. Error-correcting codes are the opposite of special. What Shannon proved—and once he understood what to prove, it was really not so hard—was that almost all sets of code words exhibited the error-correcting property; in other words, a completely random code, with no design at all, was extremely likely to be an error-correcting code.

This was a startling development, to say the least. Imagine you were tasked with building a hovercraft; would your first approach be to throw a bunch of engine parts and rubber tubing on the ground at random, figuring the result would probably float?

Hamming, still impressed forty years later, said of Shannon’s proof in 1986:

Courage is one of the things that Shannon had supremely. You have only to think of his major theorem. He wants to create a method of coding, but he doesn’t know what to do so he makes a random code. Then he is stuck. And then he asks the impossible question, “What would the average random code do?” He then proves that the average code is arbitrarily good, and that therefore there must be at least one good code. Who but a man of infinite courage could have dared to think those thoughts? That is the characteristic of great scientists; they have courage. They will go forward under incredible circumstances; they think and continue to think.

If a random code was very likely to be an error-correcting code, what’s the point of Hamming? Why not just choose code words completely at random, secure in the knowledge that Shannon’s theorem makes it very likely your code corrects errors? Here’s one problem with that plan. It’s not enough for a code to be able to correct errors in principle; it has to be practical. If one of Shannon’s codes uses blocks of size 50, then the number of code words is the number of 0-1 strings fifty bits long, which is 2 to the 50th power, a little over a quadrillion. Big number. Your spacecraft receives a signal, which is supposed to be one of these quadrillion code words, or at least close to one. But which one? If you have to flip through the quadrillion code words one by one, you’re in big trouble. It’s the combinatorial explosion again, and in this context it forces on us another tradeoff. Codes that have a lot of structure, like the Hamming codes, tend to be easy to decode. But these very special codes, it turns out, are usually not as efficient as the completely random ones that Shannon studied! And in the decades between then and now, mathematicians have tried to ride that conceptual boundary between structure and randomness, laboring to construct codes random enough to be fast, but structured enough to be decodable.

The Hamming code is great for the Transylvanian lottery, but not so effective at Cash WinFall. The Transylvanian lottery has just seven numbers; Massachusetts offered forty-six. We’re going to need a bigger code. The best one I could find for the purpose was discovered by R. H. F. Denniston of the University of Leicester in 1976. And it’s a beauty.

Denniston wrote down a list of 285,384 six-number combinations from a choice of forty-eight numbers. The list starts like this:

1 2 48 3 4 8

2 3 48 4 5 9

1 2 48 3 6 32 . . .

The first two tickets have four numbers in common: 2, 3, 4, and 48. But—and here is the miracle of the Denniston system—you will never find any two of those 285,384 tickets that have five numbers in common. You can translate the Denniston system into a code, much as we did with the Fano plane: replace each ticket with a string of 48 1s and 0s, with a 0 in the places corresponding to the numbers on your ticket, and a 1 in the places corresponding to the numbers not on your ticket. So the first ticket above would translate into the codeword:

000011101111111111111111111111111111111111111110

Check for yourself: the fact that no two tickets agree on five out of six numbers means that this code, like the Hamming code, has no two code words separated by a Hamming distance of less than four.[*]

Another way to say this is that every five-number combination appears on at most one of Denniston’s tickets. And it gets better: in fact, every five-number combination appears on exactly one ticket.[*]

As you can imagine, a lot of care is required in choosing the tickets on Denniston’s list. Denniston includes in his paper a computer program in ALGOL that verifies that his list really does have the magical property he claims, a rather advanced gesture for the 1970s. Still, he insists that the computer’s role in the collaboration is to be understood as strictly subordinate to his own: “I should like, indeed, to make it clear that all the results announced here were found without recourse to computers, even though I suggest that computers may be used to verify them.”

Cash WinFall has only forty-six numbers, so to play it Denniston-style, you have to destroy the beautiful symmetry a bit by throwing out all the tickets in Denniston’s system containing a 47 or a 48. This still leaves you with 217,833 tickets. Suppose you get together $435,666 out of the couch cushions and decide to play these numbers. What happens?

The lottery draws six numbers—say, 4, 7, 10, 11, 34, 46. In the unlikely event these match one of your tickets exactly, you win the jackpot. But even if not, you’re still in line to win a healthy pile of money for matching five of the six numbers. Do you have a ticket with 4, 7, 10, 11, 34 on it? One of Denniston’s tickets does, so the only way you can miss out is if the Denniston ticket with those five numbers was 4, 7, 10, 11, 34, 47 or 4, 7, 10, 11, 34, 48, and thus got trashed.

But what about a different five-number combination, like 4, 7, 10, 11, 46? Maybe you had bad luck the first time, because 4, 7, 10, 11, 34, 47 was one of Denniston’s tickets. But then 4, 7, 10, 11, 46, 47 cannot be on Denniston’s list, because it would agree in five places with a ticket you already know to be there. In other words, if evil 47 makes you miss out on one five-out-of-six prize, it can’t make you miss out on any others. The same goes for 48. So of the six possible five-number wins:

4, 7, 10, 11, 34

4, 7, 10, 11, 46

4, 7, 10, 34, 46

4, 7, 11, 34, 46

4, 10, 11, 34, 46

7, 10, 11, 34, 46

you are guaranteed to have at least four of them among your tickets.

In fact, if you buy the 217,833 Denniston tickets, you have a

2% chance of hitting the jackpot

72% chance of winning six of the five-out-of-six prizes

24% chance of winning five of the five-out-of-six prizes

2% chance of winning four of the five-out-of-six prizes.

Compare this with the Selbee Quic Pic strategy of choosing tickets randomly. In that case, there’s a small chance, 0.3%, of getting shut out of the five-out-of-six prize tier entirely. Worse, there’s a 2% chance of getting just one of those prizes, a 6% chance of getting two, an 11% chance of getting three, and a 15% chance of getting four. The guaranteed returns of the Denniston strategy are replaced by risk. Naturally, that risk comes with an upside, too—team Selbee has a 32% chance of getting more than six of those prizes, impossible if you pick your tickets according to Denniston. The expected value of Selbee’s tickets is the same as that of Denniston’s, or anyone else’s. But the Denniston method shields the player from the winds of chance. In order to play the lottery without risk, it’s not enough to play hundreds of thousands of tickets; you have to play the right hundreds of thousands of tickets.

Is this strategy the reason Random Strategies spent the time to fill out hundreds of thousands of tickets by hand? Were they using Denniston’s system, developed in the spirit of utterly pure mathematics, to siphon money from the lottery at no risk to themselves? Here’s where my reporting hit a wall. I was able to get in touch with Yuran Lu, but he didn’t know exactly how those tickets had been chosen; he told me only that they had a “go-to guy” in the dorm who handled all such algorithmic matters. I can’t be sure whether the go-to guy used the Denniston system, or something like it. But if he didn’t, I think he probably should have.