Sphere Packing Solved in Higher Dimensions

In a pair of papers posted online this month, a Ukrainian mathematician has solved two high-dimensional versions of the centuries-old “sphere packing” problem. In dimensions eight and 24 (the latter dimension in collaboration with other researchers), she has proved that two highly symmetrical arrangements pack spheres together in the densest possible way.

Mathematicians have been studying sphere packings since at least 1611, when Johannes Kepler conjectured that the densest way to pack together equal-sized spheres in space is the familiar pyramidal piling of oranges seen in grocery stores. Despite the problem’s seeming simplicity, it was not settled until 1998, when Thomas Hales, now of the University of Pittsburgh, finally proved Kepler’s conjecture in 250 pages of mathematical arguments combined with mammoth computer calculations.

Higher-dimensional sphere packings are hard to visualize, but they are eminently practical objects: Dense sphere packings are intimately related to the error-correcting codes used by cell phones, space probes and the Internet to send signals through noisy channels. A high-dimensional sphere is easy to define — it’s simply the set of points in the high-dimensional space that are a fixed distance away from a given center point.

Finding the best packing of equal-sized spheres in a high-dimensional space should be even more complicated than the three-dimensional case Hales solved, since each added dimension means more possible packings to consider. Yet mathematicians have long known that two dimensions are special: In dimensions eight and 24, there exist dazzlingly symmetric sphere packings called E₈ and the Leech lattice, respectively, that pack spheres better than the best candidates known to mathematicians in other dimensions.

“Somehow everything just fits perfectly together, and it’s sort of a miracle,” said Henry Cohn, a mathematician at Microsoft Research New England in Cambridge, Mass. “I don’t have a simple, gut-level explanation of what it is about.”

For reasons that mathematicians don’t fully understand, E₈ and the Leech lattice have connections to a wide range of mathematical subjects, including number theory, combinatorics, hyperbolic geometry and even areas of physics such as string theory. They form “a nexus where lots of different areas of mathematics come together,” Cohn said. “Something wonderful is happening, and I’d like to understand what it is.”

Mathematicians have amassed compelling numerical evidence that E₈ and the Leech lattice are the best sphere packings in their respective dimensions. But until now, that evidence came just short of a proof. Researchers have known for more than a decade what the missing ingredient in the proof should be — an “auxiliary” function that can calculate the largest allowable sphere density — but they couldn’t find the right function.

Now, in a paper posted online on March 14, Maryna Viazovska, a postdoctoral researcher at the Berlin Mathematical School and the Humboldt University of Berlin, has come up with the missing function in dimension 8. Her work uses the theory of modular forms, powerful mathematical functions that, when they can be brought to bear upon a problem, seem to unlock huge amounts of information. In this case, finding the right modular form allowed Viazovska to prove, in a mere 23 pages, that E₈ is the best eight-dimensional packing.

“It’s stunningly simple, as all great things are,” said Peter Sarnak, of Princeton University and the Institute for Advanced Study. “You just start reading the paper and you know this is correct.”

Within a week, Viazovska, along with Cohn and three other mathematicians, successfully extended her method to cover the Leech lattice too.

“I think some of us have been hoping for this for a very long time,” Hales said.

Filling the Gaps

It’s possible to build an analogue of the pyramidal orange stacking in every dimension, but as the dimensions get higher, the gaps between the high-dimensional oranges grow. By dimension eight, these gaps are large enough to hold new oranges, and in this dimension only, the added oranges lock tightly into place. The resulting eight-dimensional sphere packing, known as E₈, has a much more uniform structure than its two-stage construction might suggest. “Part of the mystery here is this object turns out to be vastly more beautiful and symmetric than it sounds,” Cohn said. “There are tons of extra symmetries.”

The Leech lattice is similarly constructed by adding spheres to a less dense packing, and it was discovered almost as an afterthought. In the 1960s, the British mathematician John Leech was studying a 24-dimensional packing that can be constructed from the “Golay” code, an error-correcting code that was later used to transmit the historic photos of Jupiter and Saturn taken by the Voyager probes. Shortly after Leech’s article about this packing went to press, he noticed that there was room to fit additional spheres into the holes in the packing, and that doing so would double the packing density.

In the resulting Leech lattice, each sphere is surrounded by 196,560 other spheres, in such a unique arrangement that the mathematician John Conway, of Princeton University, discovered three entirely new types of symmetry by probing the lattice’s structure. The Leech lattice is “one of the few most exciting mathematical objects,” said Gil Kalai, a mathematician at the Hebrew University of Jerusalem.

In 2003, Cohn and Noam Elkies of Harvard University developed a way to estimate just how well E₈ and the Leech lattice perform compared to other sphere packings in their respective dimensions. In every dimension, Cohn and Elkies showed, there is an infinite sequence of “auxiliary” functions that can be used to compute upper limits on how dense sphere packings are allowed to be in that dimension.

In most dimensions, the best sphere packings discovered to date didn’t even come close to the density limits this method generated. But Cohn and Elkies found that in dimensions eight and 24, the best packings — E₈ and the Leech lattice — seemed to practically bump their heads against the ceiling. When Cohn and Abhinav Kumar of Stony Brook University carried out extensive numerical calculations on the sequences of auxiliary functions, they found that the best possible sphere packings in dimensions eight and 24 could be at most 0.0000000000000000000000000001 percent denser than E₈ and the Leech lattice.

Given this ridiculously close estimate, it seemed clear that E₈ and the Leech lattice must be the best sphere packings in their respective dimensions. Cohn and Elkies suspected that for each of these two dimensions, there should be some auxiliary function that would give an exact answer that matched the density of E₈ and the Leech lattice. “We gave many talks and even convened a conference or two to disseminate the problem in the hope that such [a function] was known or could easily be found if we only know in which mathematical field to look, but found nothing,” Elkies wrote in an email.

Hales said he has believed for years that the right function should exist, but he had no idea how to pin it down. “I felt that it would take a Ramanujan to find it,” he said, referring to the early 20th-century mathematician Srinivasa Ramanujan, who was famous for pulling deep mathematical ideas out of thin air.

Now, Viazovska has found the elusive auxiliary functions for E₈ and the Leech lattice, using a type of mathematical object that Ramanujan also studied extensively: modular forms. “She’s pulled a Ramanujan,” Hales said.

Mining for Gold

Modular forms are functions that possess special symmetries like those in M.C. Escher’s circular tilings of angels and devils. These functions possess a startling power to illuminate different areas of mathematics — for instance, they were instrumental in the proof of Fermat’s Last Theorem in 1994. And although modular forms have been studied for centuries, mathematicians are still unlocking the deep secrets hidden inside their coefficients. Sarnak calls them a gold mine. “I’m waiting for someone to write a paper one day, ‘The Unreasonable Effectiveness of Modular Forms,’” he said.

Unfortunately, though, there’s only a limited supply of modular forms, and they are highly constrained objects. “You can’t just write down a modular form that does whatever you want,” Cohn said. “So it’s a matter of whether one actually exists that does what you need it to.”

Viazovska’s 2013 doctoral dissertation was on modular forms, and she also has expertise in discrete optimization, one of the fields that are central to the sphere-packing problem. So when, three years ago, Viazovska’s friend Andrii Bondarenko, of the Norwegian University of Science and Technology in Trondheim, suggested that they work together on the eight-dimensional sphere-packing problem, Viazovska agreed.

They worked on the problem off and on along with Danylo Radchenko of the Max Planck Institute for Mathematics in Germany. Eventually, Bondarenko and Radchenko moved on to other problems, but Viazovska pressed on alone. “I felt like it’s my problem,” she said.

After two years of intense effort, she succeeded in coming up with the right auxiliary function for E₈ and proving that it is correct. It’s difficult, she said, to explain just how she knew which modular form to use, and she’s currently writing a paper to try to describe her “philosophical reason” for searching for it where she did. There’s “a whole new mathematical story behind it,” she said.

After Viazovska posted her paper on March 14, she was startled by the surge of excitement it created among sphere-packing researchers. “I thought people would be interested in the result, but I did not know there would be that much attention,” she said.

That night, Cohn emailed to congratulate her, and as the two exchanged emails he asked if it might be possible to extend her method to the Leech lattice. “I felt like, ‘I am already tired and I deserve some rest,’” Viazovska said. “But I tried still to be useful.”

The two of them threw together a collaboration with Kumar, Radchenko and Stephen Miller of Rutgers University, and with the benefit of Viazovska’s earlier work, they quickly found a way to construct the right auxiliary function for the Leech lattice. The team posted its 12-page paper online just a week after Viazovska had posted her first paper.

The new results don’t have practical implications for error-correcting codes, since knowing that E₈ and the Leech lattice were close to perfect had already been sufficient for all real-world applications. But the two proofs offer mathematicians both a sense of closure and a powerful new tool. A natural next question, Cohn said, is whether these methods can be adapted to show that E₈ and the Leech lattice have “universal optimality.” This would mean that they provide not just the best sphere packings but also the lowest-energy ones, if, for example, the centers of the spheres are regarded as electrons repelling one another.

And because E₈ and the Leech lattice are connected to so many areas of mathematics and physics, Viazovska’s new approach may well ultimately lead to many more discoveries, said Akshay Venkatesh, of Stanford University. “It seems to me much more likely than not that this function is also part of some richer story.”

This article was reprinted on Wired.com.