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 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.”
Now, a new computational technique has enabled advances in a number 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 by helping to address whether symmetry is the central feature of the densest packings.
Vallentin, who is a professor of applied mathematics and computer science, and his colleagues recently used semidefinite programming to lower the ceiling on the densest packing of pentagons in two spatial dimensions and that of spheres in four, five, six, seven and nine dimensions. “This was a real breakthrough in letting us go beyond the analytical techniques that we had previously,” said Cohn, who co-discovered the previous best bounds in those dimensions.
The incremental advances achieved thus far have few practical applications, but researchers say they could portend larger leaps. “Right now, it’s more about developing the method,” Vallentin said.
Oranges in a Crate
Packing problems are some of the oldest in geometry. Centuries of effort have shown that although these problems are easy to understand and straightforward to guess at, they are all but impossible to solve rigorously using the laws of mathematics. Johannes Kepler conjectured in 1611 that the densest arrangement of spheres in three dimensions is the way oranges are stacked in a crate, known as face-centered cubic packing. This arrangement, which fills slightly more than 74 percent of space, is obviously correct, but with an infinite number of possible sphere arrangements, the problem pushes the power of mathematical logic to its limit: Only in 1998 did mathematician Thomas Hales rigorously prove Kepler’s conjecture, and his proof involved 50,000 lines of computer code.
Semidefinite programming improves on a technique called linear programming, which has been the upper bound discovery method of choice for decades. With linear programming, researchers list constraints on the possible correlations between pairs of objects, such as the rule that two spheres cannot be less than twice their radius apart. An algorithm then searches for the highest density that satisfies the list of constraints, yielding an upper bound by ruling out a range of densities. In semidefinite programming, the list can also include constraints on triplets, quadruplets or larger collections of objects, providing a richer description of the geometry, which produces better bounds.
“The big trade-off is between the complexity of the bounds and how close we expect them to come to the truth,” Cohn explained.
The new tool has already enabled researchers to improve the optimality of binary codes similar to the one used by the Voyager spacecraft. In a pair of papers published in May 2012 and November 2013 in IEEE Transactions on Information Theory, two groups have improved the bounds on codes that range in length from 18 to 28 bits.
But apart from deep-space communication, codes of those lengths have only a few applications. Most modern digital transmission involves much larger packages of data, and the efficiency of the transmission corresponds to the packing of spheres in hundreds or thousands of spatial dimensions. In those cases, the densest known packings — conjectured in 2006 by Princeton University professors Salvatore Torquato and Frank Stillinger — are sparse, with spheres filling just a few thousandths of a percent of space. “There’s no proof in higher dimensions what the densest packing is,” Torquato said. “There is a prospect that as you increase the dimensionality of the space, that in fact disorder ends up beating order and the densest packing is a random arrangement.”
Disordered arrangements are difficult to mathematically define and use as error-correcting codes, however. Researchers have striven to find a dense, symmetric lattice of spheres in high dimensions since the American mathematician Claude Shannon revealed the problem’s relevance to data transmission in his classic 1948 paper that founded information theory. Semidefinite programming bounds could be a helpful approach in determining ballpark densities that might be achievable, Vallentin and outside researchers said.
The tool is also helping to chip away at more generalized packing problems. Vallentin and colleagues recently applied their algorithm to find some of the first-ever upper bounds on the densest packing of spheres of two different sizes — a problem relevant to the study of many crystals and to codes in which some messages are more important than others. They also showed that pentagons cannot fill more than 98 percent of two-dimensional space.
“Getting upper bounds for these kinds of problems has been extraordinarily challenging,” said Yoav Kallus, a condensed matter physicist at Princeton. Three years ago, Kallus and his collaborators proved that pyramidal objects called tetrahedra cannot fill more than 99.99999999999999999999999974 percent of space. “Obviously, we don’t expect the packing reaches that high,” he said. “It’s just so hard to get any upper bound.”
Vallentin is honing his algorithm in hopes of eventually lowering the ceiling for tetrahedra closer to the optimal density. (So far, the densest known arrangement, discovered in 2010 by Sharon Glotzer and colleagues at the University of Michigan, fills 85.63 percent of space.) The algorithm would also apply to a variety of other shapes. “The ultimate goal would be: You give the computer your shape, and the computer gives you a reasonable upper bound of how densely you can pack that,” Vallentin said.
Considering the complexity of packing problems in two and three dimensions, how were the Voyager probes able to transmit photos using 24-dimensional codewords? Luckily for NASA, among the smattering of packing problems that have been solved is the special case of lattices of spheres in 24 dimensions. “In dimension-24, there is an amazingly symmetric and dense lattice called the ‘Leech lattice,’ ” Torquato said. Discovered in the 1960s by British mathematician John Leech, this snug arrangement of spheres gave the Voyager probes a rich palette of 4,096 codewords to use during data transmission. But the Leech lattice does more than represent the densest packing of spheres in 24 dimensions. It belongs to a new class of geometric structures that are the preferred arrangements of objects that interact in a variety of ways, not only ones like spheres that cannot overlap. These “universal optima” are “the most interesting, the most beautiful, the most important structures,” said Cohn, who studies them with collaborator Abhinav Kumar, an associate professor of mathematics at the Massachusetts Institute of Technology.
Universal optima exhibit certain miraculous properties, such as one Cohn calls the “not-getting-stuck” phenomenon. Consider trying to find the densest packing of circles in a plane. You might start by drawing a circle in the middle of a piece of paper and fitting as many additional circles around it as possible. You will soon discover that six circles form a tight hexagon around the central one. There’s no reason to think this pattern should continue to hold (if you were drawing pentagons, for example, you could draw only one ring of neighbors before awkward gaps would appear), but it turns out that you can keep adding circles according to the hexagonal pattern without ever running into trouble. “It all just sort of works,” Cohn said.
This rare feature of the two-dimensional hexagonal lattice — exemplified by the continuous planes of honeycomb that bees build — is shared by the Leech lattice in 24 dimensions and a structure called the E8 lattice in eight dimensions. Though impossible to visualize, these lattices are, mathematically, just as painless to construct. “Everything just locks in place,” Cohn explained. “The pattern just continues the way you would hope. You never get stuck.”
The feature is tied to the property of universal optimality. In the Annals of Mathematics in 2009, Cohn and Kumar proved upper bounds in eight and 24 dimensions that come within a fraction of a percent of the densities of the E8 and Leech lattices, indicating that these are almost certainly the densest packings of spheres in their respective dimensions. But these lattices also appear to be the optimal configurations in general, not only for spheres but also for particles that exert forces on each other, such as two atoms pushing each other apart. For “every reasonable repulsive force between particles,” Cohn said, the particles will self-assemble into a hexagonal lattice in 2-D, an E8 lattice in 8-D and a Leech lattice in 24-D. These arrangements are not only densest; they are “universally” optimal.
Perhaps for this reason, the structures appear broadly throughout mathematics and physics. “From combinatorics and graph theory to geometry and algebraic geometry and so on, they show up all over the place,” Kumar said.
E8 plays a role in string theory, a hypothetical “theory of everything” that says that space-time is 10-dimensional and that particles such as electrons and quarks are tiny one-dimensional strings oscillating at different frequencies. In the 1980s, string theorists showed that one variant, called heterotic string theory, can be formulated using the symmetries of two copies of E8. “We can exactly produce the real world that we know, starting with the E8 heterotic string theory,” said Burt Ovrut, a string theorist at the University of Pennsylvania. When the E8 theory is reduced in a way that makes the world appear three-dimensional, it contains “the quarks, the leptons, the Higgs and all the other particles we observe.”
Universal optimality is a young idea, and researchers are still exploring its meaning and consequences. Recently, Cohn and his former intern, Jeechul Woo, used semidefinite programming bounds to discover new universal optima, including some arrangements that are much less symmetric than expected.
“Symmetry definitely plays an important role,” Kallus said, “but I think one of the interesting things that Henry Cohn has shown is that there are configurations that are universal optima that have none of this symmetry.”
Mathematicians have long approached packing problems under the assumption that, as any traveler knows, order typically trumps disorder when it comes to packing. The fact that symmetry isn’t the whole story — not in very high dimensions, where randomness reigns, nor in some newly studied lower-dimensional cases — means scientists may need some other principle to understand the underlying geometry of packing and its grand extension, universal optimality.
“At the moment, I think we don’t have a fundamental unifying principle,” Kumar said. “I think there’s all sorts of interesting things out there. We are looking for some replacement for symmetry.”
This article was reprinted on ScientificAmerican.com.
