To Pack Spheres Tightly, Mathematicians Throw Them at Random
Introduction
Mathematicians like to generalize concepts into higher dimensions. Sometimes this is easy.
If you want to efficiently pack squares in two dimensions, you arrange them like a checkerboard. To squeeze together three-dimensional cubes, you stack them like moving boxes. Mathematicians can easily extend these arrangements, packing cubes in higher-dimensional space to perfectly fill it.
Packing spheres is much harder. Mathematicians know how to pack circles or soccer balls together in a way that minimizes the empty space between them. But in four or more dimensions, the most efficient packing scheme is a complete mystery. (With the exception of dimensions 8 and 24, which were solved in 2016.)
“It sounds so simple,” said Julian Sahasrabudhe, a mathematician at the University of Cambridge. “There could be 20 different ways of approaching it. And that seems to be what’s happened — there’s lots of different ideas.”
The known optimal sphere packings in 2, 3, 8 and 24 dimensions look like lattices, full of patterns and symmetry. But in every other dimension, the best packings might be totally chaotic.
“That, I think, is a very tantalizing aspect of it. It’s really very open,” said Akshay Venkatesh, a mathematician at the Institute for Advanced Study. “We just do not know.”
Last December, Sahasrabudhe, together with his Cambridge colleague Marcelo Campos, Matthew Jenssen of King’s College London and Marcus Michelen of the University of Illinois, Chicago, provided a new recipe for how to densely pack spheres in all arbitrarily high dimensions. It’s the first significant advance on the general sphere-packing problem in 75 years.
“It’s a beautiful piece of mathematics,” said Yufei Zhao, a mathematician at the Massachusetts Institute of Technology. “There are new, groundbreaking ideas.”
Improving the Baseline
The tightest way to arrange circles on a two-dimensional plane is in a hexagonal pattern, with circles placed at the corners and center of each hexagon. Such a grid fills a bit over 90% of the plane.
Samuel Velasco/Quanta Magazine
In 1611, the physicist Johannes Kepler thought about the best way to pack three-dimensional spheres. For the base layer, he packed the spheres in a hexagonal arrangement, like the circles.
He then placed a second layer of spheres over the first, filling the gaps. But then there’s a choice to make. The third layer can go directly above the first layer:
Or it can be offset:
In both cases, the pattern then repeats. And in both cases, the spheres fill the exact same amount of space: about 74%.
In 1831, Carl Friedrich Gauss, one of the most prominent mathematicians of the 19th century, showed that Kepler’s configurations are the best possible lattices — repeating gridlike configurations — but he wasn’t able to rule out the possibility that some irregular arrangement could do better. (It was finally ruled out around the turn of the millenium.)
In higher dimensions, mathematicians were at a loss. Then, in 2016, Maryna Viazovska used the existence of symmetries particular to eight-dimensional space to prove that particular lattices are optimal. She also worked with collaborators to extend the proof to 24 dimensions. She earned the 2022 Fields Medal, the highest prize in mathematics, for this work.
“What I love about [sphere packing] is the way it’s a thread connecting lots of different areas in mathematics, in computer science and in physics,” said Henry Cohn, a mathematician at Microsoft Research who worked with Viazovska on the 24-dimensional proof.
These known optimal packings — in one, two, three, eight and 24 dimensions — don’t seem to generalize to higher dimensions. In higher dimensions, mathematicians don’t know what percentage of space an optimal arrangement would fill. Instead, they try to approximate it.
In any dimension, if you start with a very large box and successively fill it with balls — sticking one anywhere you find a large enough opening — then the spheres will occupy at least $latex \frac{1}{2^d}$ of the box, where d is the dimension of the space. So in two dimensions, they will fill at least 1/4 of the space, and in three dimensions, they will fill at least 1/8 of the space, and so forth. In relatively small dimensions, mathematicians often know of specific packings that do much better than this general bound. (For example, Kepler’s three-dimensional packing fills 74% of the space — significantly more than the minimal 12.5%.) But the $latex \frac{1}{2^d}$ baseline is useful because it applies to all dimensions.
From left: Marcus Michelen, Marcelo Campos, Julian Sahasrabudhe, and Matthew Jenssen in Sahasrabudhe’s Cambridge office on the last day of a month-long visit in which they broke a 75-year-old sphere-packing record.
Julia Wolf
“This is kind of the baseline,” Zhao said. Progress establishing a better baseline that generalizes to arbitrary dimensions has been slow.
In 1905, the mathematician Hermann Minkowski proved that in any arbitrary number of dimensions, a lattice exists that can pack in twice as many balls as the baseline through the placement of a sphere at each point on the lattice.
The next substantial improvement came in 1947, when Claude Ambrose Rogers, an English mathematician, came up with an even better lattice. Where Minkowski’s improvement over the baseline was by a constant factor, Rogers’ scheme was an “asymptotic” improvement over the baseline, meaning that as the number of dimensions grows, so too does the difference in the efficiency of the packing. In 50 dimensions, Rogers could pack some 50 times as many spheres as the baseline, but in 1,000 dimensions, his packing was roughly 1,000 times better.
In the past 75 years, a few results here and there have improved on Rogers’ packing by a constant multiple, but nobody has been able to find another asymptotic improvement that works in all dimensions until now.
Connecting the Dots
Campos, Jenssen, Michelen and Sahasrabudhe began working together early in the pandemic, meeting on Zoom for hours every day — though not, at first, on this problem. They co-authored three papers before they first met in person last fall, when Jenssen and Michelen came to Cambridge for a month-long visit. That’s when they set their sights on the sphere-packing problem.
“During that time is when we started and essentially completed the sphere-packing problem,” Michelen said. “It was definitely very fast, and in some ways, it came as a bit of a surprise.”
Maryna Viazovska used symmetries particular to 8 and 24 dimensions to prove the existence of optimal sphere packings.
2022 EPFL/Fred Merz – CC-BY-SA 4.0
The mathematicians approached the problem using graphs, which are collections of vertices (points) connected by edges (lines). Graphs are frequently used in combinatorics and probability theory, the authors’ primary research fields. Nearly all of the lower bounds to how densely spheres can be packed have come from studying latticelike structures. But the recent paper uses graph theory to create highly disordered packings — a very different approach.
“When we first started to talk about it, it seemed a little bit intimidating,” Sahasrabudhe said. “We realized we could model it as a graph. Then we started to feel more at home.”
To create their packing, they started by randomly scattering points in space. These points would eventually be the centers of the spheres in the packing. They then drew a line connecting any two points that were too close to each other — spheres centered at those two points would overlap.
From this graph, they wanted to extract an independent set, which is a collection of vertices where no two vertices are connected by an edge, like those shown in red below. If they drew spheres at all the points in an independent set, the balls would not overlap. They would form a sphere packing.
It’s easy to create a sparse independent set — just grab a few vertices from far-apart regions in a graph. But to make a dense sphere packing — with as many balls as possible — they needed a very large independent set. Their challenge was to extract an independent set using a large portion of vertices in the original graph.
To do so, they used a technique called the Rödl nibble, where one iteratively removes (or “nibbles”) pieces of the graph.
“It’s a super influential technique,” Sahasrabudhe said. “It goes back to the ’80s, but in the last 10 to 15 years, people have really been hammering on it.”
They started by going through every vertex in the graph. At each one, they (metaphorically) flipped a coin that was heavily weighted toward tails. If the flip landed tails, they did nothing. If it landed heads, they removed the vertex and added it to a new graph.
This nibbling process created an independent set using a relatively small portion of the original graph. But this independent set was not big enough. So they repeated the process, nibbling more pieces from the original graph and adding them to the new graph. In the end, they got a large independent set of the original graph, which was exactly what they were looking for.
This advance was the final ingredient in the proof. With their large independent set, they created the densest known sphere packing in higher dimensions and the first asymptotic improvement on Rogers’ bound. “What amazes me about the new paper is just what a nice, simple idea it is,” said Will Perkins, a theoretical computer scientist at the Georgia Institute of Technology.
While the new result is a significant improvement, it’s not the final answer. No one knows how close the new sphere packing is to the optimal one.
In 2010, the physicists Francesco Zamponi and Giorgio Parisi theorized that the best possible “amorphous,” or disordered, packing of spheres would be exactly twice as dense as the recent breakthrough. So mathematicians may be nearing the limit of how tightly spheres can be packed in a disordered way. But it’s possible that a sphere packing in a regular pattern could be significantly denser.
In the perennial battle between order and chaos, the new sphere packing scores a point for disorder. But mathematicians are still undecided on whether order or disorder will win out.
“In this case, I think it’s a real mystery,” Perkins said.
