29
$\begingroup$

In a recent publication by the Ukrainian mathematician Maryna Viazovska the Kepler problem for dimension $8$ and $24$, namely the densest packing of spheres, was solved.

Admittedly it is very difficult to grasp the work for someone not involved in the field, but it would be incredibly valuable if, briefly, the methodology adopted, and the main breakthrough could be explained at a conceptual level. Such that one can have a rough idea how the solution came to be.

This is merely an attempt to get more input in order to understand some of the main ideas involved, as this is very exciting news given that the problem of densest packing of spheres in different dimensions has a long history.

$\endgroup$
  • 6
    $\begingroup$ @katz spam?! Cannot believe I'm reading this... $\endgroup$ – user88381 Apr 5 '16 at 10:54
  • 3
    $\begingroup$ “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.” I think we have to take this paper seriously, so this is not spam (or at least not for that reason). We might still ask whether the question is appropriate for this forum. $\endgroup$ – Ben McKay Apr 5 '16 at 11:12
  • $\begingroup$ endorsements: quantamagazine.org/… $\endgroup$ – Carlo Beenakker Apr 5 '16 at 11:17
  • $\begingroup$ @BenMcKay, Peter Sarnak knows what he is talking about but the information you provided was not included with the question :-) $\endgroup$ – Mikhail Katz Apr 5 '16 at 11:18
  • $\begingroup$ Even a brief inspection by a non-specialist shows that this is more conceptual proof than that of Kepler's conjecture:-) $\endgroup$ – Alexandre Eremenko Apr 5 '16 at 20:05
39
$\begingroup$

There are two things you need to understand. The first is how to prove sphere packing bounds via harmonic analysis ("linear programming bounds"). My lecture notes from PCMI 2014 give an exposition of this theory, which covers the period up to, but not including, Viazovska's paper on eight dimensions. This reduces the problem to finding radial functions in eight and twenty-four dimensions with certain roots and sign conditions, and the lecture notes discuss why everybody believed such functions exist. The functions themselves are surprisingly subtle; see this paper with Steve Miller for numerical experiments and conjectures.

Then Viazovska's breakthrough lies in how to construct the right functions. It's convenient to split them up into eigenfunctions of the Fourier transform, which have to have roots at certain locations. One way to look at it is that she brute forces those roots by including a sine squared factor that produces the roots, and then she multiplies it by something that's essentially the Laplace transform of a (quasi)modular form. To make this work, one has to answer three questions:

  1. What sort of modular forms play nice with the sine squared factor and produce radial eigenfunctions of the Fourier transform?

  2. Do there exist such modular forms that actually give the desired functions?

  3. How can we prove the inequalities these functions are supposed to satisfy?

Viazovska's methodology gives nice answers:

  1. This amounts to identifying the right level, weight, and depth (for quasimodular forms).

  2. Yes. One can reverse engineer them based on the desired properties.

  3. In the best way one could hope for, namely at the level of the modular form itself (rather than having to worry about something subtle happening in the Laplace transform).

For details, see the eight and twenty-four dimensional papers. As Peter Sarnak points out in Erica Klarreich's Quanta article, the actual construction is surprisingly simple. If you know about linear programming bounds and basic facts about modular forms, the proof itself is very down to earth.

| cite | improve this answer | |
$\endgroup$
  • 3
    $\begingroup$ Lecture 5 in the notes explains how these functions are relevant (you could actually skip Lectures 2-4, which are useful background but not really needed for this purpose). The short answer is that the functions and their Fourier transforms have opposite signs at most places, which means you get a lot of information if you plug them into Poisson summation and compare the two sides of the identity. Explaining in detail takes some space, but it's all there in Theorem 3.1 in Lecture 5. $\endgroup$ – Henry Cohn Apr 5 '16 at 15:01
  • $\begingroup$ Does it seem likely that a proof of the dimension 2 case via the linear programming bounds will follow soon? In your paper with Miller, you make the comment "We will focus on n=8 and 24, not only because these cases are more interesting, but also because they appear to be more similar to each other than either is to the n=2 case." However it was not clear what properties that was referring to. $\endgroup$ – j.c. Apr 6 '16 at 15:44
  • $\begingroup$ I guess I can answer my own question: after watching Miller's lecture at IAS here youtube.com/watch?v=8qlZjarkS_g it becomes more clear to me that the fact that the lengths of vectors in the $E_8$ and Leech lattices are square roots of integers leads to the abovementioned "sine squared factor". The lengths of vectors in the hexagonal lattice do not have this property, so some other kind of factor would be needed, if this approach were to work. $\endgroup$ – j.c. Apr 6 '16 at 21:59
  • $\begingroup$ The functions $f(r),\hat{f}(r)$ that go into the bounds must have roots (with certain multiplicities) whenever $r$ is equal to the length of a vector in the lattice. The functions constructed by Viazovska for $n=8$ (and their analogues in $n=24$) neatly address this requirement with a sine squared factor (compare Table 1 of the Cohn and Miller paper in Henry Cohn's answer to Eqs. 32 and 48 in Viazovska's paper as well as Eq. 2.5 and the equation after 3.3 in the $n=24$ paper). Stephen Miller points this out in his lecture; I didn't discover any of this. $\endgroup$ – j.c. Apr 7 '16 at 10:54
  • $\begingroup$ @HenryCohn The lecture notes are incredibly well written, thanks so much for this. Here's my attempt at a rough summary in 3 comments: I see that we start first from distribution of points on the surface of an $n$ dim sphere. The lectures first deal with the energy minimization case, where there's interaction between the points, given by the potential function $f.$ The question becomes then, which code (config of points) has the distribution $A$ (fulfilling a set of constraints) that minimizes the total energy function. Then using the Delsarte inequalities, one arrives at (...) $\endgroup$ – user88381 Apr 8 '16 at 16:53
1
$\begingroup$

The image below depicts a hypersphere inscribed in a hypercube. The number of dimensions increases from left to right (2,3,4 and 5 dim). As you can see, the higher the dimension, the higher is the number of "hypercorners" that are left uncovered by a single hypersphere sitting at the center, of diameter no greater than the side. These increase as the powers of two: 4, 8, 16 and so on.

Hypersphere inscribed in hypercube

It is easy to prove, by using the Gamma function, that the relative volume of the sphere to that of the hypercube (aka "density") decreases as the number of dimensions rises. In dimension 8, you would have 2^8=256 hypercorners around the 8-dimensional sphere.

One first trivial attempt to pack non-overlapping spheres in a fractal manner is by means of an Apollonian (Leibniz) gasket - thus observe the second picture attached. As the number of dimensions increases, so does the amount of spheres that need to be fitted in this manner, in an exponential manner.

Apollonian gasket (WP)

Of course, there are more efficient ways to pack spheres than this gasket. The simplest approximation is to think of unit hyperspheres: that is, of those having equal -unitary- volume. Or having equal surface area, in some other interpretations, as it is easy to translate from one to another (by using the pi formula).

Some more complex packing gaskets or schemes involve spheres of varying sizes, other than the classic Apollonian fractal, and their computation may involve optimization methods such as Linear Programming or meta/heuristics.

Viazovska's article does not deal with these, but only with unit balls, and benchmarks any packing method with the trivial classic lattice packing in 8 dimensions. Its conclusion is that there is none more efficient in density measures than the (E8) lattice.

| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy