Abstractions blog
How to Use a Sphere to Talk to Mars
It’s hard to send a message from Mars.
When the Curiosity rover, currently active on the surface of the red planet, has something to tell NASA back on Earth, it formulates its communication in binary code and beams it our way. Noise inevitably creeps in during the long transmission, so that the message received by NASA is different from the one the rover sent. At that point it’s a game of telephone, as NASA engineers make their best guess about what Curiosity was trying to tell them.
The situation from Mars is an exaggerated version of what happens whenever a message is communicated through any noisy channel — be it from a flash drive to your computer or an air traffic control tower to an airplane. In each case, the receiver has to estimate what the sender meant to say. One way to ensure that the message gets through is to use a geometric way of packaging information called a “spherical code.”
A spherical code is a way of translating a message written in one form, like binary code, into a point on a high-dimensional sphere. (We think of spheres as three-dimensional objects, but in math, a sphere can exist in any number of dimensions.) Imagine, for example, that you’d like to transmit the word “Mars.” To do this, you’d need to find some way of relating each letter to a coordinate on the sphere. While the mathematics behind spherical codes is more complicated than this, you could imagine, for example, that the word “Mars” maps to the point (13, 1, 18, 19) on a sphere in four-dimensional space. Here, the coordinates are like values of latitude and longitude that direct you to a single point on a globe. The first letter in the word is represented by the coordinate value in the first dimension, the second letter is represented by the coordinate value in the second dimension, and so on, with the specific value of the coordinate determined by the letter’s position in the alphabet (so “a” has coordinate value 1 since it’s the first letter in the alphabet).
Of course, the same problem that applied to the original message still applies to the translated one: Curiosity sends one point on the sphere, but NASA receives another.
The key, however, is to use only a limited number of points for encoding messages. As long as those points are spaced far enough apart, it’s unlikely that one point will end up being mistaken for another. Over the course of a spherical code’s long Earthward journey, it will meander randomly around the intended point on the sphere. Upon arrival at NASA, the received point should be closer to the intended point than any other point that corresponds to a message. NASA engineers can then make a good guess about which point the rover was trying to communicate.
So how do you choose which points to use? One way is an approach from pure mathematics that is the subject of my new story, “A New Path to Equal-Angle Lines.” There I describe a recent breakthrough in the study of what are called “equiangular lines.”
A set of lines is considered equiangular when all the lines intersect at a point and any two lines form the same angle. In two dimensions (like on a flat sheet) the maximum number of equiangular lines is three. In three dimensions, it’s six. Mathematicians are interested in proving just how big those sets can get as you move into higher dimensions.
For the purposes of communication, though, equiangular lines have another interest. Here’s how: Draw a circle around three equiangular lines. All the points where the lines pierce the circle are going to be separated by some minimum distance, which is a useful starting place from which to construct a spherical code. As a result, over the last 70 years the study of equiangular lines and spherical codes has developed together. “It has been realized all along that these two are very much related,” said Alexander Barg, a mathematician at the University of Maryland who studies coding theory.
Constructions of equiangular lines are one way to arrive at a spherical code, but they’re not the best for the purpose of communication. Any spherical code necessarily involves tradeoffs between reliability and the amount of information you’re able to transmit. The farther apart the points are, the less likely it is that one message will get mistaken for another, but the closer together the points are, the more messages you’re able to send. Finding the sweet spot is a major preoccupation in coding theory, and in that realm spherical codes derived from equiangular lines may be playing it a little too safe.
“This requirement of having an equal angle may be too strong for the needs of error correction,” said Barg. “We may allow the worst-case separation to be smaller; that way we can transmit more messages through the same channel.”