A new tool to help mathematicians pack

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…

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 densestpackings 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.”

Now, a new computational technique has enabled advances in anumber of important cases that had resisted progress for decades. The mathematicians Christine Bachoc of the University of Bordeaux in France and Frank Vallentin of the University of Cologne in Germany developed the tool, called “semidefinite programming bounds,” in 2008, drawing on an earlier paper by Alexander Schrijver of the University of Amsterdam in the Netherlands. The technique provides ballpark estimates of the densest packing of objects by identifying an upper bound that can be gradually lowered toward the exact solution as the computation of the bound becomes increasingly detailed. The tool is yielding new insights into the underlying geometry of packing problems, including longstanding questions about whether symmetry is the central feature of the densest packings.