Optimal stacking of oranges.
The sphere-packing problem
The Kepler conjecture is the assertion that the simple scheme of stacking oranges typically seen in a supermarket has the highest possible average density, namely pi/(3 sqrt(2)) = 0.740480489…, for any possible arrangement, regular or irregular. It is named after 17th-century astronomer Johannes Kepler, who first proposed that planets orbited in elliptical paths around the sun.
Hales’ proof of the Kepler conjecture
In the early 1990s, Thomas Hales, following an approach first suggested by Laszlo Fejes Toth in 1953, determined that the maximum density of all possible arrangements could be obtained by minimizing a certain function with 150 variables. In 1992, assisted by his graduate student Samuel Ferguson (son of famed mathematician-sculptor Helaman Ferguson), Hales embarked on a multi-year effort to find a lower bound for the function for each of roughly 5000 different configurations of spheres, using a linear programming approach. In 1998, Hales and Ferguson announced that their project was complete, documented by 250 pages of notes and three Gbyte of computer code, data and results.
Hales’ computer-assisted proof generated some controversy — the journal Annals of Mathematics originally demurred, although ultimately accepted his paper. Thus Hales decided to embark on a collaborative effort to certify the proof via automated proof-checking (formal method) software. This project, named Flyspeck, was begun in 2003, but not completed until 2014.
Sphere packing in higher dimensions
Mathematicians have been investigating similar sphere packing problems in higher dimensions for many years. These problems naturally arise in fields such as error-correcting codes, which are used by everything from mobile phones to space probes: given a signal corrupted by noise, which is the closest signal that could have generated it, and how much noise can corrupt a signal before it can no longer be uniquely recovered, statistically speaking?
Two cases have been particularly troublesome: dimensions 8 and 24. Thus mathematicians studying the field were elated to hear, in March 2016, that the dimension 8 case had been solved by Ukrainian mathematician Maryna Viazovska, who was then a postdoctoral researcher at the Berlin Mathematical School and the Humboldt University of Berlin. Unlike Hales’ 250-page proof, Viazovska’s proof was a mere 23 pages long.
Credit: Wikimedia and Jgmoxness
The champagne was not even dry from the celebration over Viazovska’s E8 result before she, in collaboration with Henry Cohn, Abhinav Kumar, Stephen D. Miller and Danylo Radchenko, applied similar techniques to prove that the Leech lattice is the optimal structure for dimension 24.
For additional details on these results, see this well-written Quanta Magazine article by Erica Klarreich. Maryna Viazovska’s paper on the 8-dimensional problem is available here. The joint paper on the 24-dimensional problem is available here.
Magic functions
It is now three years since the E8 and Leech lattice papers. Maria Viazovska is now at the Swiss Federal Institute of Technology in Lausanne, Switzerland. Viazovska and her four colleagues Henry Cohn, Abhinav Kumar, Stephen D. Miller and Danylo Radchenko have now proven something even more significant: In a new 89-page paper they have proven that the configurations that solved the sphere-packing problem in 8 and 24 dimensions also solve an infinite number of other related problems on the optimal arrangements for points attempting to “avoid” each other.
Proving universal optimality like this in high dimensions is much more difficult than solving the sphere-packing problem. This is in part because there are literally an infinite number of optimality problems, but also because the individual problems are more difficult. In sphere packing, each sphere only interacts with its nearest neighbors, whereas in problems with electrons, for instance, each electron interacts with every other electron in the universe, no matter how far away they are.
For their latest result, Henry Cohn, Abhinav Kumar, Stephen D. Miller and Danylo Radchenko focused on “monotonic repulsive forces,” which encompass most of the known physical forces. The sphere-packing problem is merely the limiting case with the requirement that the spheres not overlap. For any of these monotonic forces, the optimality question reduces to finding the lowest-energy configuration (the “ground state”) for an infinite collection of problems. In numerical studies of the cases 8 and 24, Cohn and Kumar found bounds found that were extremely close to the energy of the E8 and Leech lattices. They were thus led to wonder whether for some given force field there would be some optimal function whose bound exactly matched the energy of the E8 or Leech lattice.
What these researchers found that such a “magic function” would have to take certain special values at certain points, and, in addition, that its Fourier transform would also have to take special values at certain other points, which is a tall order. This is reminiscent of the uncertainty principle of quantum theory — the more one tries to pin down the position, the more difficult it is to pin down its momentum (since, in quantum theory, the Fourier transform of position is momentum).
In the case of dimension 8 or 24, Viazovska conjectured that these restrictions limited any magic function to the border of possibility — any additional restrictions, and no such function could exist; any fewer, and such a function would not be unique. In the end, the researchers found a way to generate “magic functions” with exactly that property.
Thomas Hales, who proved the Kepler conjecture, was very impressed with this result, saying that even in light of the earlier work, I would not have expected this [universal optimality proof] to be possible to do. Sylvia Serfaty, a mathematician at New York University, described the work as at the level of the big 19th-century mathematics breakthroughs.
Some additional details are given in this well-written Quanta Magazine article, also by Erica Klarreich, from which some of the discussion above was adapted. The new joint paper is available here.