sphere packing

Out of a Magic Math Function, One Solution to Rule Them All

Mathematicians used “magic functions” to prove that two highly symmetric lattices solve a myriad of problems in eight- and 24-dimensional space.
DVDP for Quanta Magazine

Three years ago, Maryna Viazovska, of the Swiss Federal Institute of Technology in Lausanne, dazzled mathematicians by identifying the densest way to pack equal-sized spheres in eight- and 24-dimensional space (the second of these in collaboration with four co-authors). Now, she and her co-authors have proved something even more remarkable: The configurations that solve the sphere-packing problem in those two dimensions also solve an infinite number of other problems about the best arrangement for points that are trying to avoid each other.

The points could be an infinite collection of electrons, for example, repelling each other and trying to settle into the lowest-energy configuration. Or the points could represent the centers of long, twisty polymers in a solution, trying to position themselves so they won’t bump into their neighbors. There’s a host of different such problems, and it’s not obvious why they should all have the same solution. In most dimensions, mathematicians don’t believe this is remotely likely to be true.

But dimensions eight and 24 each contain a special, highly symmetric point configuration that, we now know, simultaneously solves all these different problems. In the language of mathematics, these two configurations are “universally optimal.”

The sweeping new finding vastly generalizes Viazovska and her collaborators’ previous work. “The fireworks have not stopped,” said Thomas Hales, a mathematician at the University of Pittsburgh who in 1998 proved that the familiar pyramidal stacking of oranges is the densest way to pack spheres in three-dimensional space.

Eight and 24 now join dimension one as the only dimensions known to have universally optimal configurations. In the two-dimensional plane, there’s a candidate for universal optimality — the equilateral triangle lattice — but no proof. Dimension three, meanwhile, is a zoo: Different point configurations are better in different circumstances, and for some problems, mathematicians don’t even have a good guess for what the best configuration is.

“You change the dimension or you change the problem a little bit and then things may be completely unknown,” said Richard Schwartz, a mathematician at Brown University in Providence. “I don’t know why the mathematical universe is built this way.”

Proving universal optimality is much harder than solving the sphere-packing problem. That’s partly because universal optimality encompasses infinitely many different problems at once, but also because the problems themselves are harder. In sphere packing, each sphere cares only about the location of its nearest neighbors, but for something like electrons scattered through space, every electron interacts with every other electron, no matter how far apart they are. “Even in light of the earlier work, I would not have expected this [universal optimality proof] to be possible to do,” Hales said.

“I’m very, very impressed,” said Sylvia Serfaty, a mathematician at New York University. “It’s at the level of the big 19th-century mathematics breakthroughs.”

A Magic Certificate

It might seem strange that dimensions eight and 24 should behave differently from, say, dimension seven or 18 or 25. But mathematicians have long known that packing objects into space works differently in different dimensions. For instance, consider a higher-dimensional sphere, defined simply as the collection of points some fixed distance from a center point. If you compare the sphere’s volume to that of the smallest cube that fits around it, the sphere fills up less and less of the cube as you go up in dimension. If you wanted to ship an eight-dimensional soccer ball in the smallest possible box, the ball would fill less than 2 percent of the box’s volume — the rest would be wasted space.

In each dimension higher than three, it’s possible to construct a configuration analogous to the pyramidal orange arrangement, and as the dimension increases, the gaps between the spheres grow. When you hit dimension eight, there’s suddenly enough room to fit new spheres into the gaps. Doing so produces a highly symmetric configuration called the E8 lattice. Likewise, in dimension 24, the Leech lattice arises from fitting extra spheres into the gaps in another well-understood sphere packing.

For reasons mathematicians don’t fully understand, these two lattices crop up in one area of mathematics after another, from number theory to analysis to mathematical physics. “I don’t know of a single root cause for everything,” said Henry Cohn, of Microsoft Research New England in Cambridge, Mass., one of the new paper’s five authors.

For more than a decade, mathematicians have had strong numerical evidence suggesting that E8 and the Leech lattice are universally optimal in their respective dimensions — but until recently they had no idea how to prove it. Then in 2016, Viazovska took the first step by proving that these two lattices are the best possible sphere packings (she was joined, for the Leech lattice proof, by Cohn and the other three authors of the new paper: Abhinav Kumar, Stephen Miller of Rutgers University and Danylo Radchenko of the Max Planck Institute for Mathematics in Bonn, Germany).

While Hales’ proof for the three-dimensional case filled hundreds of pages and required extensive computer calculations, Viazovska’s E8 proof came in at just 23 pages. The core of her argument involved identifying a “magic” function (as mathematicians have come to call it) that provided what Hales called a “certificate” that E8 is the best sphere packing — a proof that might be hard to come up with, but that once found carries instant conviction. For example, if someone asked you whether any real number x makes the polynomial x2 – 6x + 9 negative, you might be hard-pressed to reply. But if you realized that the polynomial equals (x – 3)2, you would immediately know that the answer is no, since squared numbers are never negative.

Viazovska’s magic function method was powerful — almost too powerful, in fact. The sphere-packing problem only cares about interactions between nearby points, but Viazovska’s approach seemed as if it might work for long-range interactions as well, like those between distant electrons.

High-Dimensional Uncertainty

To show that a configuration of points in space is universally optimal, one must first specify the universe in question. No point configuration is optimal with respect to every single goal: For instance, when an attractive force acts on the points, the lowest-energy configuration will not be some lattice but just a massive pileup, with all the points at the same spot.

Viazovska, Cohn and their collaborators restricted their attention to the universe of repulsive forces. More specifically, they considered ones that are completely monotonic, meaning (among other things) that the repulsion is stronger when points are closer to each other. This broad family includes many of the forces most common in the physical world. It includes inverse power laws — such as Coulomb’s inverse square law for electrically charged particles — and Gaussians, the bell curves that capture the behavior of entities with many essentially independent repelling parts, such as long polymers. The sphere-packing problem sits at the outer edge of this universe: The requirement that the spheres not overlap translates into an infinitely strong repulsion when their center points are closer together than the diameter of the spheres.

For any one of these completely monotonic forces, the question becomes, what is the lowest-energy configuration — the “ground state” — for an infinite collection of particles? In 2006, Cohn and Kumar developed a method for finding lower bounds on the energy of the ground state by comparing the energy function to smaller “auxiliary” functions with especially nice properties. They found an infinite supply of auxiliary functions for each dimension, but they didn’t know how to find the best auxiliary function.

Researchers in the study.

The five authors of a new paper proving universal optimality in dimensions 8 and 24, shown clockwise from top left: Henry Cohn, Abhinav Kumar, Maryna Viazovska, Stephen Miller and  Danylo Radchenko.

Bryce Vickmark (Cohn); Courtesy of Abhinav Kumar; Daniil Yevtushynsky (Viazovska); Julia Semikina (Radchenko); Olena Shmahalo/Quanta Magazine (Miller)

In most dimensions, the numerical bounds Cohn and Kumar found bore little resemblance to the energy of the best-known configurations. But in dimensions eight and 24, the bounds came astonishingly close to the energy of E8 and the Leech lattice, for every repulsive force Cohn and Kumar tried their method on. It was natural to wonder whether, for any given repulsive force, there might be some perfect auxiliary function that would give a bound exactly matching the energy of E8 or the Leech lattice. For the sphere-packing problem, that’s exactly what Viazovska did three years ago: She found the perfect, “magic” auxiliary function by looking among a class of functions called modular forms whose special symmetries have made them objects of study for centuries.

When it came to other repelling-point problems, such as the electron problem, the researchers knew what properties each magic function would need to satisfy: It would have to take on special values at certain points, and its Fourier transform — which measures the function’s natural frequencies — would need to take on special values at other points. What they didn’t know, in general, was whether such a function actually exists.

It’s usually easy to construct a function that does what you want at your favorite points, but it’s surprisingly tricky to control a function and its Fourier transform at the same time. “When you impose your will on one of them, the other one does something that’s totally different from what you wanted,” Cohn said.

In fact, this persnicketiness is none other than the famous uncertainty principle from physics in disguise. Heisenberg’s uncertainty principle — which says that the more you know about a particle’s position, the less you can know about its momentum, and vice versa — is a special case of this general principle, since a particle’s momentum wave is the Fourier transform of its position wave.

In the case of a repulsive force in dimension eight or 24, Viazovska made a daring conjecture: that the limitations the team wanted to place on their magic function and its Fourier transform lay precisely on the border between the possible and the impossible. Any more limitations, she suspected, and no such function could exist; fewer limitations, and many functions could exist. In the situation the team cared about, she proposed, there should be exactly one function that fit.

“This is, I think, one of the great things about Maryna,” Cohn said. “She’s very insightful and also very bold.”

At the time, Cohn was skeptical — Viazovska’s guess seemed too good to be true — but the team eventually proved her right. Not only did they show that there exists exactly one magic function for each repulsive force, but they gave a recipe for how to make it. As with sphere packing, this construction provided an immediate certificate of the optimality of E8 and the Leech lattice. “It’s kind of a monumental result,” Schwartz said.

The Triangle Lattice

Beyond settling the universal optimality problem, the new proof answers a burning question many mathematicians have had since Viazovska solved the sphere-packing problem three years ago: Just where did her magic function come from? “I think many people were puzzled,” Viazovska said. “They asked, ‘What is the meaning here?’”

In the new paper, Viazovska and her collaborators showed that the sphere-packing magic function is the first in a sequence of modular-form building blocks that can be used to construct magic functions for every repulsive force. “Now it has many brothers and sisters,” Viazovska said.

It still feels somewhat miraculous to Cohn that everything worked out so neatly. “There are some things in mathematics that you do by persistence and brute force,” he said. “And then there are times like this where it’s like mathematics wants something to happen.”

The natural next question is whether these methods can be adapted to prove universal optimality for the only other clear candidate out there: the equilateral triangle lattice in the two-dimensional plane. For mathematicians, the fact that no one has come up with a proof in this simple setting has been a “big embarrassment for the whole community,” said Edward Saff, a mathematician at Vanderbilt University in Nashville.

Unlike E8 and the Leech lattice, the two-dimensional triangular lattice shows up all over the place in nature, from the structure of honeycombs to the arrangement of vortices in superconductors. Physicists already assume this lattice is optimal in a wide range of contexts, based on a mountain of experiments and simulations. But, Cohn said, no one has a conceptual explanation for why the triangular lattice should be universally optimal — something a mathematical proof would hopefully provide.

Dimension two is the only dimension other than eight and 24 in which Cohn and Kumar’s numerical lower bounds work well. This strongly suggests that there should be magic functions in dimension two as well. But the team’s method for constructing magic functions is unlikely to carry over to this new domain: It relies heavily on the fact that the distances between points in E8 and the Leech lattice are especially well-behaved numbers, which is not the case in dimension two. That dimension “seems beyond humanity’s abilities right now,” Cohn said.

For the time being, mathematicians are celebrating their new insight into the strange worlds of eight- and 24-dimensional space. It is, Schwartz said, “one of the best things I’ll probably see in my lifetime.”

Comment on this article