Reed-Solomon codes help power an enormous number of information technologies.

Kristina Armitage/Quanta Magazine

To avoid errors, you once again add extra information. Here, you send the y-value that corresponds to another predetermined x-coordinate. If the three points do not fall on the same line, there’s an error. And to figure out where the error is, you just send one more value — meaning you’ve sent four numbers total, rather than the six required by the previous method.

The advantage grows with the size of the message. Let’s say you want to send a longer message — 1,000 numbers. The less efficient code would require sending 2,000 numbers to identify an error, and 3,000 to correct it. But if you use the code that involves interpolating a polynomial through given points, you only need 1,001 numbers to find the error, and 1,002 to correct it. (You can add more points to identify and correct more potential errors.) As the length of your message increases, the difference in efficiency between the two codes grows starker.

Abstractions navigates promising ideas in science and mathematics. Journey with us and join the conversation.

---

See all Abstractions blog

The more efficient code is called a Reed-Solomon code. Since its introduction in 1960, mathematicians have made further breakthroughs, developing algorithms that can correct more errors with greater efficiency. "It’s very elegant, clean, concrete," said Swastik Kopparty, a mathematician and computer scientist at the University of Toronto. "It can be taught to a second-year undergraduate in half an hour."

Reed-Solomon codes have been particularly useful for storing and transmitting information electronically. But the same concept has also been essential in cryptography and distributed computing.

Take secret sharing: Let’s say you want to distribute a secret among several parties such that no one person can access the entire secret, but together they can. (Imagine an encryption key, for instance, or a missile launch code.) You encode the numbers in a polynomial, evaluate that polynomial at a predetermined set of points, and distribute each of the results to a different person.

Most recently, Reed-Solomon codes have been employed in areas like cloud computing and blockchain technology. Say you need to run a computation that’s too complicated for your laptop, so you have a large computational cluster run it — but now you need to verify that the computation you get back is correct. Reed-Solomon codes let you ask for additional information that the cluster likely won’t be able to produce if it hasn’t done the computation correctly. "This works magically," said Jade Nardi, a research fellow at the Mathematics Institute of Rennes in France. "This process is really wonderful, and the way it relies on [these codes] blows my mind."

In a proof-of-concept test, NASA scientists encoded the Mona Lisa onto a laser beam and sent it from Earth’s surface to a lunar spacecraft. Reed-Solomon codes were used to correct transmission errors introduced by Earth’s atmosphere.

Courtesy of Xiaoli Sun, NASA Goddard

But Reed-Solomon codes also have an important constraint. They’re constructed in such a way that you can only evaluate your polynomial at a fixed (and usually relatively small) set of values. That is, you’re limited to using a certain set of numbers to encode your message. The size of that set, or alphabet, in turn restricts the length of the messages you can send — and the bigger you try to make your alphabet, the more computational power you’ll need to decode those messages.

And so mathematicians sought an even more optimal code.

Future Codes

A more general, more powerful code would allow you to store or send longer messages without needing to increase the size of your alphabet. To do this, mathematicians devised codes that involve interpolating a function — which lives in a special space associated to a more complicated curve — through given points on that curve. These so-called algebraic geometry codes "came out of nowhere, and they’re better than any other code we know how to make [with a smaller alphabet]," Kopparty said. "This beats everything. It was a real shock."

There’s just one problem. In practice, implementing a Reed-Solomon code is much, much easier than implementing an algebraic geometry code. "This is state-of-the-art, but it’s still under investigation to really turn into something practical," said the cryptologist Simon Abelard. "It involves quite abstract mathematics, and it’s hard to handle these codes on a computer."

For now, that’s not worrisome: In real-world applications, Reed-Solomon codes and related forms of error correction are sufficient. But that might not always be the case. For instance, if powerful quantum computers become available in the future, they’ll be able to break today’s cryptography protocols. As a result, researchers have been searching for schemes that can resist quantum attacks. One top contender for such schemes would require something stronger than Reed-Solomon codes. Certain versions of algebraic geometry codes might just work. Other researchers are hopeful about the role algebraic geometry codes might play in cloud computing.

But even in the absence of such potential uses, "in the history of mathematics, sometimes you discover new things that really don’t have applications nowadays," said Elena Berardini, a researcher at Eindhoven University of Technology in the Netherlands who works on algebraic geometry codes. "But then after 50 years, you find that it might be useful for something completely unexpected" — just like the ancient problem of interpolation itself.