In 1998, mathematician Thomas C. Hales made headlines by settling a nearly 400-year-old question: What is the best space-saving way to stack oranges? Johannes Kepler, the natural philosopher who first realized that planets orbit the sun in ellipses, conjectured in 1611 that fruit sellers already had it right: The best packing is the familiar pyramidal arrangement seen in markets all over the world. Despite the simplicity of this proposed solution, proving Kepler’s conjecture turned out to be elusive for centuries and, in the end, required the assistance of a computer. Hales’ 250-page paper is so complex that referees have spent 6 years poring over its details, and although they still haven’t checked every one, they recently gave the paper the thumbs-up to be published in digest form in the Annals of Mathematics.
Hales’ opus would seem to lay to rest the question of how to stack fruit. Yet for mathematicians, who are not constrained to the familiar world, Hales’ work is just the beginning. Hales, who is now at the University of Pittsburgh, figured out how to stack three-dimensional oranges. But what is the best way to stack oranges in four dimensions, five dimensions, or n dimensions?
It may be hard to visualize an n-dimensional orange, but it’s easy to write an equation to define its shape—a sphere—in any dimension. A sphere is simply the set of all points a fixed distance away from a chosen center point.
The question of how to densely pack spheres in a dimension higher than three may seem fanciful and abstruse. Sphere packings, however, are intimately connected to what are called error-correcting codes. These are central to a wide range of noisy data-transmission applications, such as sending images from space probes to Earth.
Using coding techniques, mathematicians have uncovered a surprise. Although the definitions of spheres in every dimension are analogous, the configurations of spheres that the various dimensions can contain are very different. Results from two research groups are providing new glimpses of the uniqueness of various dimensions.
In recent work, Oleg R. Musin, an independent mathematician based in Los Angeles, has used coding ideas to tackle a problem closely related to sphere packing. Called the kissing problem, it asks how many spheres can fit around, or kiss, a single central sphere. The sphere-packing problem, by contrast, asks what arrangement of spheres can fit most densely into all of space.
When it comes to three-dimensional oranges, the kissing number is 12. Musin has now proved that the kissing number in dimension four is 24. The 24 spheres that surround the central sphere trace out a highly symmetrical four-dimensional shape called the 24-cell, which has no analog in any other dimension.
Meanwhile, a trio of mathematicians has come up with compelling numerical evidence—just shy of a proof—that the best sphere packings in dimensions 8 and 24 are particularly symmetrical arrangements known as the E8 lattice and the Leech lattice, respectively. In other dimensions, even the best packings known are less symmetrical.
“It seems mysterious, but there are these special dimensions out there,” says Henry Cohn of Microsoft Research in Redmond, Wash., a member of the team that performed the second study. “I don’t know of any really good conceptual explanation of why dimensions 8 and 24 work out so nicely.”
Error-proof packing
To see the connection between n-dimensional sphere packing and error-correcting codes, imagine that Alice wants to transmit a message to Bob via radio signals. Before the message is sent, Alice and Bob must agree on a code that translates each word in their vocabulary into a unique signal.
If Alice and Bob can measure the strength of, say, 24 different frequencies of each radio signal, then each word corresponds to 24 coordinates—the strength of the signal’s corresponding frequencies. In other words, the code translates each word into a point in 24-dimensional space.
In an ideal world, Alice would send a radio signal for each word in her message, and Bob would simply measure the 24 coordinates of each signal and then look up the corresponding word. But in the real world, information channels are noisy, and errors inevitably creep in.
Thus, the point in 24-dimensional space that Bob receives will probably be slightly different from the one Alice sent out. If the received point is close to only one of the points in Bob’s codebook, it will be easy for Bob to guess which word Alice meant. But if the point is close to two different points in his codebook, the message will be ambiguous.
To avoid that problem, Alice and Bob should choose their code so that the points that correspond to words are far apart. If, for example, the transmission errors tend to move a point by at most 1 unit of distance, then Alice and Bob should choose their code points so that they are at least 2 units apart. In other words, the points should be at the centers of non-overlapping, 24-dimensional spheres of radius 1. That way, whenever Alice sends Bob a word, even if some errors creep in, Bob can still recover the original message.
This error-proofing protocol amounts to a sphere-packing configuration. The more tightly packed the spheres, the more words Alice and Bob can encode in a given region of space. So, the most-efficient codes correspond to the densest sphere packings.
When the late Claude Shannon launched the theory of error-correcting codes in the 1940s, high-dimensional sphere packing instantly became a hot topic, Cohn says. “Before that, if you told someone you were interested in
24-dimensional sphere packing, unless they were a pure mathematician, they looked at you as if you were crazy,” he says.
In 1973, Philippe Delsarte of the Catholic University of Louvain in Belgium developed a method for relating the size of the errors that a code can correct to the efficiency of the code—that is, the number of code words it can fit into a given space. Since the largest error a code can correct corresponds to the radius of the spheres, and the efficiency of a code is closely related to the density of the sphere packing, Delsarte’s method immediately became a powerful tool for studying sphere packings.
In the late 1970s, mathematicians used Delsarte’s methods to figure out the kissing numbers in dimensions 8 and 24. In dimension eight, they found, it’s possible to fit 240 spheres around a single central sphere. In dimension 24, a mind-boggling 196,560 spheres can crowd around one sphere. These results were obtained by Andrew Odlyzko of the University of Minnesota in Minneapolis and Neil J. A. Sloane of AT&T Shannon Laboratory in Florham Park, N.J., and independently by Vladimir Levenstein of the Keldysh Institute of Applied Mathematics in Moscow.
After this burst of progress, the study of higher-dimensional kissing numbers and sphere packings plunged into a dry spell for more than 2 decades, says Günter M. Ziegler, a mathematician at the Technical University of Berlin.
“What’s exciting to me is that now new things are happening,” Ziegler says. “Suddenly, from different corners of the field, there are new insights into how to get results.”
Design of four
In dimension two, the solutions to the kissing number and sphere-packing problems are easy to spot. Slide some pennies around on a table, and it quickly becomes clear that exactly six pennies can kiss a central penny, forming a hexagonal arrangement.
The hexagonal pattern can be extended to the entire tabletop. Since antiquity, mathematicians have considered this arrangement to be the densest-possible two-dimensional sphere packing, but their intuition was mathematically proved only in the early 20th century.
In dimension three, 12 billiard balls can fit around a central one. Just as the six pennies in dimension two sit at the corners of a regular hexagon, the 12 balls in dimension three also sit at the corners of a regular shape: an icosahedron, which has 20 triangular sides.
In the two-dimensional case, the six pennies lock tightly into place around the central penny. However, in dimension three, gaps exist between the 12 balls. Legend has it that this wiggle room gave rise to a famous controversy in 1694 between Isaac Newton and the mathematician David Gregory. According to this story, Newton maintained that only 12 spheres can fit around a central sphere, while Gregory believed it should be possible to squeeze in a 13th sphere. It was not until 1953 that mathematicians finally proved Newton right.
In dimension four, mathematicians have long had a prime candidate for the best kissing arrangement: the 24-cell, a perfectly symmetric shape with 24 corners and 24 three-dimensional sides that are all regular octahedra. If one four-dimensional sphere is placed at each corner, these 24 spheres all kiss the central sphere.
That means the kissing number in dimension four is at least 24. However, might it be possible to fit more than 24 spheres around a central one? In 1979, Odlyzko and Sloane tried to use Delsarte’s method for error-correcting codes to prove that the kissing number is 24. Frustratingly, all the method could tell them was that the kissing number was at most 25—tantalizingly close to proving that the kissing number is indeed 24, but not close enough.
In 2001, this problem caught the attention of Musin, a former mathematics professor at Moscow State University in Russia who had recently moved to the United States. Musin had learned about the kissing-number problem as a high school student. However, he had heard nothing about the developments in the 1970s using coding theory.
Then, 3 years ago, while working on a software-development project for Los Alamos National Laboratory in New Mexico, he came upon a book about sphere packings. “I spent maybe an hour reading the book, and I was so excited,” he says.
Musin resolved to solve the kissing-number problem in dimension four. “I thought maybe I’d spend a week or so,” he says. “Then, I spent the week, and another week, and another, and finally I quit all my projects, all my work. I became completely crazy about this problem.”
Fortunately, Musin’s wife, who was supporting the pair financially, was understanding. “She asked me only one question: ‘How long will it take you to solve this problem?'” Musin recalls. “I said, ‘One and a half, maybe 2 years,’ and she said that was OK.”
Musin’s estimate was right on target. After 18 months of nonstop work, he found a clever way to modify an inequality arising from Delsarte’s method to prove that the kissing number indeed is 24.
“I spent 16 hours a day, without weekends, to try to solve this problem,” Musin says. “When I got the solution, I was in shock.”
Mathematicians have yet to check all the details of Musin’s work, but his method seems “entirely solid,” Hales says. “It’s very good research.”
Musin says he will spend another year trying to figure out whether his method can be extended to higher dimensions. That extrapolation may prove tricky because the 24-cell is unique in the pantheon of shapes.
In dimension three, there are five perfectly regular, or platonic, solids: the cube, the tetrahedron, the octahedron, the dodecahedron, and the icosahedron. Dimensions five and higher contain just three platonic solids, analogs of the cube, tetrahedron, and octahedron. However, dimension four contains analogs of all five of the three-dimensional platonic solids, plus a sixth platonic solid: the 24-cell.
Just why dimension four has an extra platonic solid is a puzzle to mathematicians. “The 24-cell is this incredibly beautiful configuration that happens to fit perfectly in four dimensions, for reasons that are mysterious,” Cohn says.
Dimensions of elegance
Dimension four is not the only standout when it comes to sphere packings. Mathematicians have long known that dimensions 8 and 24 contain exceptionally nice, symmetric arrangements of spheres—the E8 lattice and the Leech lattice, respectively. Although mathematicians have not proved that these are the densest-possible arrangements of spheres, no one has found a denser arrangement.
In 2003, Cohn and Noam D. Elkies of Harvard University published a way to modify Delsarte’s method to produce upper limits for the density of any sphere packing in dimensions 8 and 24. Now, Cohn and Abhinav Kumar, a graduate student at Harvard, have used computer analysis to calculate these upper limits to the 27th decimal place, and the numbers they have calculated agree perfectly with the densities of the E8 lattice and the Leech lattice. In other words, if there is a denser packing than the E8 lattice or the Leech lattice, it is denser by less than one part in 1027—an almost unfathomably small amount.
“My feeling and everyone else’s is that the odds are zero that another sphere packing beats the Leech lattice or the E8 lattice,” Ziegler says. “But in math, as long as it’s not proved, there could be some miracle happening.”
In addition to being the leading candidates for best sphere packing in dimensions 8 and 24, the E8 lattice and the Leech lattice also give the best kissing arrangements in those dimensions. What’s more, the kissing spheres lock tightly into place. That means that dimensions 8 and 24 appear to share the simplicity and elegance of dimension 2, in which a single highly symmetric, tightly locked configuration—the hexagonal packing—is both the best kissing arrangement and the best sphere packing.
By contrast, in dimension three, the most symmetric kissing arrangement—the icosahedron—leaves wiggle room between the spheres and can’t be extended to all of space, since icosahedra can’t fill space without overlapping.
“It seems that dimensions 8 and 24 are much better behaved than dimension 3,” Cohn says.
The various dimensions are so individual, he notes, that the only way to tackle sphere-packing problems is to get to know each particular dimension’s quirks.
