From sphere packing to Fourier interpolation

By Henry Cohn

Abstract

Viazovska’s solution of the sphere packing problem in eight dimensions is based on a remarkable construction of certain special functions using modular forms. Great mathematics has consequences far beyond the problems that originally inspired it, and Viazovska’s work is no exception. In this article, we’ll examine how it has led to new interpolation theorems in Fourier analysis, specifically a theorem of Radchenko and Viazovska.

1. Sphere packing

The sphere packing problem asks how densely congruent spheres can be packed in Euclidean space. In other words, what fraction of space can be filled with congruent balls if their interiors are required to be disjoint?⁠Footnote1 Everyone can pack spheres intuitively in low dimensions: the optimal two-dimensional packing is a hexagonal arrangement, and optimal three-dimensional packings are stacks of optimal two-dimensional layers, nestled together as closely as possible into the gaps in the layers (see Figure 1.1).

1

To make this question precise, we could take the limit as of the density for packing unit spheres in a sphere of radius , or a cube of side length . We would obtain the same limit for any reasonable container (see, for example, Reference 7).

In fact, these packings are known to be optimal. The two-dimensional problem was solved by Thue Reference 42Reference 43, with a more modern proof by Fejes Tóth Reference 21, and the three-dimensional problem was solved by Hales Reference 23. The two-dimensional proof is not so complicated, but the three-dimensional proof is difficult to check, because it relies on both enormous machine calculations and lengthy human arguments in a sequence of papers. To give a definitive demonstration of its correctness, Hales and a team of collaborators have produced a formally verified proof Reference 24, i.e., a proof that has been algorithmically verified using formal logic.

On the one hand, the solution of the three-dimensional sphere packing problem is a triumph of modern mathematics, a demonstration of humanity’s ability to overcome even tremendously challenging obstacles. On the other hand, to a general audience it can sound like a parody of pure mathematics, in which mathematicians devote immense efforts to proving an intuitively obvious assertion. It’s natural to feel discouraged about the future of a subfield in which it’s easy to guess the answer and almost impossible to prove it. For comparison, a rigorous solution of the four-dimensional sphere packing problem remains far out of reach. If the difficulty increases as much from three to four dimensions as it did from two to three, then humanity may never see a proof.

One noteworthy change as we move to higher dimensions is that we lose much of our intuition, and the answer is no longer easy to guess. For example, it is not always true that we can obtain an optimal packing in by stacking optimal -dimensional layers (see Reference 16 for details). In sufficiently high dimensions, there are no conjectures for optimal packings, the best upper and lower bounds known for the packing density differ by an exponential factor in the dimension, and we cannot even predict whether the densest packings should be crystalline or disordered. In short, we know shockingly little about how spherical particles behave in high dimensions. Of course this means there are plenty of intriguing phenomena to explore.

Certain dimensions stand out in the midst of this ignorance as having exceptionally dense packings. The most amazing of all are eight and twenty-four dimensions, which feature the root lattice and the Leech lattice . (We will not construct these lattices here; see Reference 17Reference 20Reference 41 for constructions.) Recall that a lattice in is just a discrete subgroup of rank ; in other words, for each basis , …, of , the set

is a lattice. Every lattice leads to a sphere packing by centering congruent spheres at the lattice points, with the radius chosen as large as possible without overlap. Lattice packings are common in low dimensions, but there is no reason to expect an optimal packing to have this sort of algebraic structure in general. For example, in the best packing known, the aptly named Best packing Reference 5, has density more than 8% greater than any known lattice packing in . By contrast, the and Leech lattices yield impressively dense packings with extraordinary symmetry groups, and their density and symmetry are so far out of the ordinary that it is difficult to imagine how they could be improved.

In 2016 Maryna Viazovska Reference 44 solved the sphere packing problem in with an innovative use of modular forms, which was soon extended to as well Reference 13; both and the Leech lattice do indeed turn out to be optimal sphere packings. These are the only cases in which the sphere packing problem has been solved above three dimensions. Although the proofs require more machinery than those in two or three dimensions, most notably the theory of modular forms, they are much shorter and simpler than one might fear. Viazovska’s proof dispelled the gloomy possibility that higher-dimensional sphere packing could be beyond human understanding, and she was awarded a Fields Medal in 2022 for this line of work.

In addition to her breakthrough in sphere packing, Viazovska’s modular form techniques have led to unexpected consequences, such as interpolation theorems showing that a radial function can be reconstructed from the values of and its Fourier transform on certain discrete sets of points. Although Fourier interpolation may sound rather far afield from sphere packing, it turns out to be closely connected. In this article, we’ll explore how Viazovska’s work led to this connection and how to prove a fundamental interpolation theorem of Radchenko and Viazovska Reference 38. For comparison, Reference 32, Reference 9, Reference 45, Reference 46, and Reference 10 are expositions of her work that focus on other themes.

2. From sphere packing to Fourier analysis

The connection between packing problems and Fourier analysis originated in the work of Delsarte Reference 19 on linear programming bounds for error-correcting codes. For sphere packings in Euclidean space, a continuous analogue of Delsarte’s work was developed by Cohn and Elkies Reference 11. The quality of this bound depends on the choice of an auxiliary function satisfying certain inequalities, and Viazovska’s breakthrough amounted to figuring out how to optimize that choice.

We will normalize the Fourier transform of an integrable function by

where denotes the usual inner product on . We’ll generally restrict our attention to Schwartz functions, i.e., infinitely differentiable functions such that for all real numbers and nonnegative integers , …, ,

as . These smoothness and decay conditions can be somewhat weakened in each application below, but Schwartz functions are the best-behaved case. We’ll also frequently study radial functions, i.e., functions for which depends only on , in which case we will write for to denote the value with and for the radial derivative of . Note that the spaces of radial functions and of Schwartz functions are both preserved by the Fourier transform.

The linear programming bound is the following method for producing a density bound from a suitable auxiliary function . The name “linear programming bound” refers to the fact that optimizing this bound can be recast as an infinite-dimensional linear programming problem (i.e., linear optimization problem).

Theorem 2.1 (Cohn and Elkies Reference 11).

Let be a radial Schwartz function and let be a positive real number such that

(1)

whenever ,

(2)

for all , and

(3)

.

Then the optimal sphere packing density in is at most the volume of a ball of radius in .

It is far from obvious how to produce good auxiliary functions for use in this theorem, or how to optimize the choice of , i.e., minimize . In fact, the exact optimum is known only for , , and . However, one can perform a numerical optimization over a suitable space of functions, such as polynomials of fixed degree times a Gaussian, with the hope that it will converge to the global optimum as the degree tends to infinity. Figure 2.1 compares the resulting numerical bound with the density of the best packing known.

In most dimensions, the linear programming bound seems nowhere near sharp, but the upper and lower bounds appear to touch in eight and twenty-four dimensions. Cohn and Elkies conjectured that they were equal in those cases, and the solutions of the sphere packing problem in these dimensions come from proving this conjecture.⁠Footnote2 For comparison, it is known that the linear programming bound cannot be sharp in dimensions three through five Reference 33, six Reference 18, twelve, or sixteen Reference 15, and it is likely that the only sharp cases are dimensions one, two, eight, and twenty-four.

2

The linear programming bound also seems to be sharp in two dimensions, but no proof is known, despite the fact that the two-dimensional sphere packing problem itself can be solved by elementary means.

The optimal auxiliary functions in eight and twenty-four dimensions have come to be known as magic functions, because obtaining an exact solution in these dimensions feels like a miracle. To see how this miracle comes about, we will examine a proof of Theorem 2.1 for the special case of lattice packings. It is based on the Poisson summation formula, which states that

for every Schwartz function and lattice in . In this formula, is the volume of the quotient torus (i.e., the volume of a fundamental parallelotope for the lattice or, equivalently, the absolute value of the determinant of a basis), and is the dual lattice, which is spanned by the dual basis , …, to any basis , …, of (i.e., ). Poisson summation expresses a fundamental duality for Fourier analysis on , and we can apply it as follows.

Proof of Theorem 2.1 for lattice packings.

Suppose our sphere packing consists of spheres centered at the points of a lattice in . The sphere packing density is scaling-invariant, and so without loss of generality we can assume that the minimal nonzero vectors in have length . In other words, the sphere packing uses spheres of radius , so that neighboring spheres are tangent to each other. Then the packing density is , since there is one sphere for each fundamental cell of .

We now apply Poisson summation to the auxiliary function , to obtain

The left side of this equation is bounded above by , because whenever , and the right side is bounded below by , since every summand is nonnegative. Thus, we conclude that , and the sphere packing density satisfies , as desired.

The proof for more general packings is similar in spirit, but it applies Poisson summation to periodic packings given by unions of translates of a lattice. See Reference 11 or Reference 9 for the details.

Note that the proof of Theorem 2.1 does not actually require to be radial. However, the conditions on are linear and rotation-invariant, and thus we can assume is radial without loss of generality via rotational averaging.

What sort of function could show that a lattice is an optimal sphere packing? The proof given above drops the terms with and for . Thus, we obtain a sharp bound if and only if all these omitted terms vanish. Because and are radial functions, these conditions amount to saying that vanishes on all the nonzero vector lengths in , while vanishes on all the nonzero vector lengths in . Furthermore, and cannot change sign at these roots, except for a sign change in at the minimal nonzero vector length in .

It turns out that the and Leech lattices are both self-dual, and their nonzero vector lengths are simply for integers in and in . Thus, we know exactly what the roots of the magic functions should be. These roots are shown in Figure 2.2 for eight dimensions.

Now the whole problem comes down to constructing magic functions with these roots. That might not seem so difficult, but controlling the behavior of and simultaneously is a subtle problem. Of course we can obtain any roots we’d like for or in isolation, but not necessarily at the same time. This phenomenon is a form of uncertainty principle Reference 8Reference 12Reference 22, much like the Heisenberg uncertainty principle.

Viazovska gave a remarkable construction of the eight-dimensional magic function in terms of modular forms, which are a class of special functions defined on the upper half-plane and satisfying certain transformation laws. The general theory of modular forms can feel somewhat forbidding to beginners, but Poisson summation gives us a simple way to get our hands on one example. The theta function is defined by

which converges because means and thus . This function satisfies two key identities,

The first identity follows immediately from the defining series, while the second is more subtle and will be proved below. In this equation, we have to choose the branch for carefully. Throughout this paper, fractional powers such as this one will be defined to be positive on the upper imaginary axis in and continuous on .

To prove that , we will use Poisson summation for the one-dimensional lattice in . Consider the complex Gaussian defined by

with . When is purely imaginary, this function is an ordinary Gaussian, and the other points in behave much the same. In particular, one can check that

which is the complex generalization of the fact that the Fourier transform of a wide Gaussian is a narrow Gaussian, and vice versa. Now Poisson summation says that

because is self-dual. This equation amounts to

and thus .

The functions and map to itself, and they generate a group of linear fractional transformations of called , in honor of the function . One can put a metric on that turns it into the hyperbolic plane, at which point becomes a discrete group of isometries of , but we will not need this interpretation. See Figure 2.3 for a picture of a -orbit in .

Together with analyticity and some growth conditions, the identities Equation 2.1 say that is a modular form of weight for the group . Viazovska’s solution of the eight-dimensional sphere packing problem constructs the magic function using and a number of other modular forms, in a way that looks rather mysterious. What do modular forms have to do with radial Schwartz functions?

Instead of examining the details of Viazovska’s construction, let’s think about a bigger picture. We know the eight-dimensional magic function should satisfy

as in Figure 2.2. Viazovska conjectured that this data, together with the nonzero value , would be enough to determine uniquely. In fact, that turns out to be true:

Theorem 2.2 (Cohn, Kumar, Miller, Radchenko, and Viazovska Reference 14).

Let be or . Then every radial Schwartz function is uniquely determined by the values , , , and for integers . Specifically, there exists an interpolation basis of radial Schwartz functions on for such that for every and ,

where these sums converge absolutely.

In particular, up to scaling the magic function is the interpolation basis function in this theorem. One does not need this interpolation theorem to solve the sphere packing problem, but it is needed for analyzing ground states of more general particle systems in and (see Reference 14), and it provides a broader context for the magic functions.

Theorem 2.2 is similar in spirit to other interpolation theorems in mathematics. The simplest and most famous of these theorems is Lagrange interpolation, which says that a polynomial in one variable of degree less than can be reconstructed from its values at any distinct points. If the interpolation points are , …, , then we can write down an interpolation basis , …, as

so that every polynomial of degree less than is given by

Lagrange interpolation can be generalized to Hermite interpolation, which takes into account derivatives along similar lines to Theorem 2.2: a polynomial can be reconstructed from the values with and if its degree is less than .

One important relative of Lagrange interpolation is Shannon sampling, which in the case of Schwartz functions says that if vanishes outside the interval for some , then is determined by its values on via

This theorem plays a crucial role in information theory, since it says that a band-limited signal (i.e., one with a limited range of frequencies) is determined by periodic samples. It’s worth noting that the product formula

is analogous to the products Equation 2.3 in the Lagrange interpolation basis. Much is known about Shannon sampling and its variations; see, for example, Reference 29 and the references cited therein.

Both Lagrange interpolation and Shannon sampling rely on a notion of size. We measure the size of a polynomial by its degree, and the size of a band-limited function by its bandwidth, the smallest such that . Then the larger a function is, the more interpolation points are required to reconstruct it, with “more” referring to density in the band-limited case. Here the intuition is that size controls how many roots a function can have.⁠Footnote3

3

Furthermore, size is related to growth at infinity. For degrees of polynomials this is clear, while a band-limited function of bandwidth can be analytically continued to the entire complex plane and satisfies . In other words, it is an entire function of exponential type .

Puzzlingly, Theorem 2.2 shows no sign of a similar notion of size. It is reminiscent of Shannon sampling, in that it takes into account both and , but it treats them symmetrically. In particular, there is little hope of a product formula along the lines of Equation 2.3 or Equation 2.4, because specifying the roots of will not yield the roots of . There seems to be a fundamental difference between these interpolation formulas, and neither Lagrange interpolation nor Shannon sampling offers a clue as to how to prove Theorem 2.2.

3. First-order Fourier interpolation

How does one prove an interpolation theorem like Theorem 2.2? We’ll examine a technically simpler variant due to Radchenko and Viazovska, which is important in its own right and a beautiful illustration of Fourier interpolation. It deals with functions of one variable (so “radial” becomes “even”), and it studies interpolation to first order, without derivatives. This first-order interpolation theorem does not seem to have any applications to sphere packing, but it’s a fundamental fact about Fourier analysis, and it is remarkable that it was not known until well into the 21st century.

Theorem 3.1 (Radchenko and Viazovska Reference 38).

There exist even Schwartz functions for , , , … such that every even Schwartz function satisfies

for all , and these sums converge absolutely.

There is also a corresponding theorem about odd functions Reference 38, Theorem 7, which can be proved in almost the same way. We’ll focus on even functions here for simplicity. Note also that the root spacing has changed from to in comparison with Theorem 2.2, which reflects the change in the order of interpolation.

As a consequence of this interpolation theorem, if an even Schwartz function satisfies for , , , …, then vanishes identically. It’s not so surprising that constructing an explicit interpolation basis , , … would require special functions, such as modular forms, but it’s noteworthy that even this corollary about vanishing does not seem easy to prove directly.

In the remainder of this section, we’ll sketch a proof of Theorem 3.1. The sketch will omit a number of analytic details, but it will outline the techniques and explain where additional work is required.

The central question is where the interpolation basis , , … comes from. We need to characterize these functions and prove that they have the desired properties. A first observation is that the interpolation basis is not quite unique, because Poisson summation over implies that every even Schwartz function satisfies

In particular, is determined by the values , , , … and , , …. To account for this redundancy, we will impose the constraint , so that the interpolation formula becomes

It turns out that this formula is now irredundant, with no additional linear relations between the values and , and the interpolation basis is uniquely determined. Substituting shows that we can characterize by its values at the points with , , , …. Specifically, for , we must have

, and , while must satisfy , , and for all .

These constraints let us get a handle on , and we can use them to compute numerical approximations to . More dramatically, they allow us to use Viazovska’s modular form techniques from Reference 44 to construct explicitly. For example, we can write down as follows:

Lemma 3.2.

Let be defined by

where we integrate over a semicircle in the upper half-plane . Then is an even Schwartz function with Fourier transform , and it satisfies and for all positive integers .

We’ll use the same semicircular contour of integration in all integrals from to  below. Recall that the theta function in this integral is defined for by

and satisfies the functional equations and .

Sketch of proof.

The function is manifestly even, and we can prove that it is a Schwartz function by analyzing the behavior of as tends to . Specifically, if we remove small neighborhoods of from the contour, then we obtain a smooth function of . One can show that this function and its derivatives are rapidly decreasing as , essentially because the complex phases interfere destructively. To show that itself is a Schwartz function, we just have to check that the behavior as is not bad enough to ruin this analysis. We will omit the details here.

To show that , we can take the Fourier transform of the complex Gaussian under the integral sign using Equation 2.2 and change variables to , to obtain