In the lead-up to the launch of the twin Voyager spacecraft in 1977, NASA’s engineers faced a tough question: When the probes arrived at Jupiter and Saturn, how would they transmit color photos back to Earth using roughly the power of a light bulb?
It was a task that called for extreme parsimony: Each image would have to be converted into a series of 24-bit binary sequences, called “codewords,” and blipped into space via radio waves that signified each 1 or 0 by the position of their peaks and troughs. But data transmission is noisy. As the codewords journeyed earthward, the engineers knew some 1s would be distorted into 0s and some 0s into 1s. To reconstruct Voyager’s iconic photos, they would have to be able to correct the code.
The Voyager probes would need to use codewords whose sequences were distinct enough to be recognizable even with a few corrupted bits. But using less distinct codewords would provide more possibilities within the 24-bit limit, enabling faster data transmission. These competing needs translated into a geometry problem in which the bits corresponded to spatial coordinates, with each codeword the center point of a sphere in 24-dimensional space. If the spheres overlapped, the associated codewords would no longer be uniquely recognizable. To optimize the amount of data that could be transmitted and then corrected, the question became: How densely could spheres be packed in 24-dimensional space?
“The problem of correcting for errors on noisy communication channels like this is exactly the sphere-packing problem,” said Henry Cohn, a mathematician at Microsoft Research New England in Cambridge, Mass.
Sphere-packing problems underlie almost all digital communications and storage, from cell phones to CDs to the Internet. But the optimal codes for these forms of transmission correspond to the densest packing of spheres in dimensions beyond the three of everyday experience, and higher-dimensional problems have proved formidable. Even more difficult to solve are the densest packings of different-size spheres or edgier shapes — two- and three-dimensional problems relevant to materials science and industrial manufacturing. Mathematicians have grappled with packing problems for centuries, attracted to their difficulty as much as their real-world applications, but each case has induced its own special kind of headache. “It’s ridiculous,” Cohn said. “We don’t even know the best way to pack pentagons in the plane.”
To read more, click here.