Multidimensional “Sphere Packing” Solutions Stack Up as a Major Mathematical Breakthrough

In 1611 German mathematician Johannes Kepler made a conjecture about the densest way to stack oranges or other spheres with a minimum of space between them. It seemed nothing could beat the standard produce stand configuration, but he could not prove it for sure. Four hundred years later University of Pittsburgh mathematician Thomas Hales finally showed that the grocers were right all along. But the question of how to pack spheres most tightly is not confined to our measly three dimensions—mathematicians can also imagine the problem in hypothetical spaces of any number of dimensions.

In March Ukrainian mathematician Maryna Viazovska, a postdoctoral researcher at the Berlin Mathematical School and at Humboldt University of Berlin, solved the sphere-packing problem in eight dimensions. The next week she and several co-authors extended her techniques to 24 dimensions. The solution of the problem in the seemingly arbitrary dimensions of eight and 24 highlights the fundamental weirdness of sphere packing, which has now been solved only in dimensions one, two, three, eight and 24. The breakthrough has given researchers hope that building on her techniques may be a viable way to answer questions about sphere packing in higher dimensions. “This is the beginning of understanding sphere packings rather than the end,” says Henry Cohn, a mathematician at Microsoft Research and one of Viazovska’s collaborators for the 24-dimensional case.

Although it is virtually impossible to visualize eight-dimensional space, mathematicians are comfortable working with spaces of eight, 24 or thousands of dimensions by analogy to lower-dimensional spaces. In three dimensions points are labeled using three coordinates—length, width and height, or x, y, z—so in eight dimensions points are labeled using eight coordinates.

In three dimensions a sphere is the set of points in three-dimensional space that are all equidistant from one center point. In eight dimensions it is the set of points in eight-dimensional space that are all equidistant from one center point. In any dimension the sphere-packing problem is the question of how equal-size spheres can be arranged with as little empty space between them as possible.

Whereas it would seem logical for mathematicians to solve successively higher dimensions in turn—after solving three, researchers could build on their work to solve four and then five—it is no accident that Viazovska leapfrogged over dimensions four through seven and solved sphere packing in eight dimensions or that 24 was the one to follow that. “Part of what I love about the sphere-packing problem is that every dimension has its own idiosyncrasies,” says Cohn, who has worked at sphere packing for many years. “Some dimensions just behave much better than others.”

In two dimensions sphere—or in this case circle—packing is easy because circles of the same size fit together so snugly. Each circle can be surrounded by exactly six other circles, and there is no wiggle room. In three dimensions there is no such super-snug packing. In fact, it is not until eight dimensions that there is another configuration, called the E8 lattice packing, where everything locks into place. In 24 dimensions a packing pattern called the Leech lattice has a similar property. Such patterns are what made these dimensions so amenable to attack.

A 2003 paper by Cohn and Harvard University mathematician Noam Elkies described a new technique for finding bounds for packing densities in many different dimensions. Their approach does not directly consider packings, but rather auxiliary functions—formulas with special properties. They believed their method could be extended to a complete solution of the sphere-packing problem in eight and 24 dimensions if they could find the right functions, but the functions eluded researchers for more than a dozen years. Viazovska says she almost gave up hope but then found a function that at first looked unrelated but aligned with Cohn’s and Elkies’ work perfectly. “For me, this was the moment when everything changed and I understood the problem really could be solved,” Viazovska says.

“Many other people spent a long time looking for the function that’s needed to make that approach work, and nobody had any solid clues about how to find it,” says Hales, who knows firsthand. In addition to solving the sphere-packing problem in three dimensions, he has worked on it in other dimensions as well and spent time looking for the function himself. “I think we were all quite shocked when Maryna Viazovska made the announcement of this discovery.”

Cohn says that with a problem like sphere packing the solution can provoke one of two responses: embarrassment, because the answer seems so obvious in retrospect; or awe, because the work was truly novel. Viazovska’s solution is a case of the latter. “Her definitions at first glance looked kind of ad hoc. Why on Earth would you do that? But it’s justified by the ingenious transformations she had,” he says. “It’s nice to be able to look at it and feel admiration rather than regret.”

The question of how to pack spheres most tightly into higher-dimensional spaces may seem like the kind of problem only a mathematician could ever love. It turns out, however, to be far from impractical. Higher-dimensional sphere packings form the basis for error-correcting codes that help us transmit data over cellular networks, fiber-optic cables and other places where information can be lost or altered in transit. These applications treat pieces of data as points in a higher-dimensional space.

Although Viazovska’s methods are not likely to solve the sphere-packing problem in other dimensions, at least not without another big breakthrough, they may help researchers improve their estimates of how tightly spheres can be packed in higher-dimensional spaces. Such advances are not as glamorous as solving the problem completely but could represent a significant improvement in higher-dimensional spaces where the data transmission stakes are high.

comments powered by Disqus