Universal optimality and Fourier interpolation

Energy minimization

Let $\mathcal{C}$ be a discrete closed subset of the Euclidean space $\mathbb{R}^d$ (we will call such sets configurations) and let $p\colon (0,\infty)\to\mathbb{R}$ be a function that describes pairwise interactions between the points of $\mathcal{C}$ (called potential or potential function). We say that $\mathcal{C}$ has density $\rho$ ($0\le \rho \le +\infty$) if one has $\lim_{R\to\infty}\frac{|\mathcal{C}\cap B_R|}{\operatorname{Vol}(B_R)}=\rho$, where $B_R$ denotes the ball of radius $R$ centered at the origin. We denote the density of $\mathcal{C}$ simply by $\rho(\mathcal{C})$. We define the (lower) $p$-energy of a configuration $\mathcal{C}$ by \[E(\mathcal{C},p) = \liminf_{R\to\infty}\frac{1}{|\mathcal{C}_R|} \sum_{\substack{x,y\in \mathcal{C}_R\\ x\ne y}}p(|x-y|) ,\qquad \mathcal{C}_R := \mathcal{C}\cap B_R,\]
where $|\cdot|$ denotes the standard Euclidean norm. Roughly speaking, $E(\mathcal{C},p)$ is a renormalization, better suited for infinite configurations $\mathcal{C}$, of the more naive definition of potential energy $\sum_{x,y\in\mathcal{C},\,x\ne y}p(|x-y|)$.

The energy minimization problem in $d$-dimensional Euclidean space asks to find the minimum of the energy $E(\mathcal{C},p)$ over all configurations $\mathcal{C}\subset\mathbb{R}^d$ of given density $\rho\in(0,\infty)$, and to describe the minimizers (the so-called "ground states"). Energy minimization is directly related to an important and largely unsolved problem in physics and materials, the so-called crystallization problem (see [1], [26]), that asks why at low temperature materials tend to acquire periodic structure. In general, the problem of rigorously determining the minimizers of $E(\mathcal{C},p)$, even for some restricted classes of potentials $p$, is very difficult and few results are known. Nevertheless, in certain dimensions the answer is known for large classes of potentials, and in a few other cases there are interesting conjectures about what the answer should be.

A closely related problem is the famous sphere packing problem that asks to find the maximal possible density of an arrangement of non-overlapping unit balls in $\mathbb{R}^d$. One way to see the relation between the two problems is to consider the potential
    \[p_{SP}(r) = \begin{cases}1,\quad r<2,\\0,\quad r \ge2.\end{cases}\]
Then a periodic set $\mathcal{C}$ is a sphere packing if and only if $E(\mathcal{C},p_{SP})=0$, so that for periodic configurations sphere packing problem follows from the energy minimization problem for $p_{SP}$. The sphere packing problem has been solved for $d=2$ (Thue [32]; Fejes Tóth [31]), $d=3$ (the Kepler conjecture, solved by Hales [17]), $d=8$ (Viazovska [34]), and $d=24$ (Cohn-Kumar-Miller-Radchenko-Viazovska [7]). In each of these cases an optimal configuration is given by a lattice: the triangular lattice $A_2$ for $d=2$, the face-centered cubic lattice for $d=3$, the $E_8$ root lattice for $d=8$ and the Leech lattice for $d=24$. It is also widely believed (see [11]) that for $4\le d\le 7$ an optimal arrangement of spheres is given by the points of a root lattice, of type $D_4$, $D_5$, $E_6$, and $E_7$ respectively (these are known to be best among lattice packings by the works of Korkine-Zolotarev [21], [22], and Blichfeldt [2]).

Other important classes of potentials for the energy minimization problem are the Riesz potentials $p(r)=r^{-s}$ and the Gaussian potentials $p(r)=e^{-\alpha r^2}$. They are of importance in physics, but arise naturally also in number theory (see [22], [28]): given a full-dimensional lattice $\Lambda\subset \mathbb{R}^d$ the value of the $p$-energy $E(\Lambda,p)$ for $p(r)=r^{-s}$ is
\[E(\Lambda,p) = \zeta_{\Lambda}(s) = \sum_{0\ne
    x\in\Lambda}\frac{1}{|x|^{s}},\]
the value of the Epstein zeta function of $\Lambda$ at $s/2$. Similarly, for $p(r)=e^{-\pi t r^2}$ the $p$-energy of $\Lambda$ equals
\[E(\Lambda,p) = \Theta_{\Lambda}(it)-1,\]
where $\Theta_{\Lambda}(\tau) = \sum_{x\in\Lambda}e^{\pi i\tau|x|^{2}}$ is the theta series of $\Lambda$.

Even when restricted to the space of lattices $\mathcal{C}=\Lambda$ of covolume 1 energy minimization remains a very difficult problem. Until recently the only cases when the answer was known for all $p(r)=r^{-s}$ and $p(r)=e^{-\alpha r^2}$ were $d=1$ and $d=2$ (this is now also known for $d=8$ and $d=24$, see below). For $d=2$ and Riesz potentials this result was established in the works of Rankin [24], Cassels [3], Diananda [13] and Ennola [15], while for Gaussian potentials this is a result due to Montgomery [22]. For Riesz energy $p(r)=r^{-s}$ Ryshkov [27] has proved that the optimal value of $E(\Lambda,p)$ over lattices is attained on any lattice that gives the best sphere packing among lattices), provided that $s$ is sufficiently large. There are some local optimality results, for instance, Sarnak and Strömbergsson [28] have proved that in dimensions 4, 8, and 24 the lattices $D_4$, $E_8$, and the Leech lattice are locally optimal for Riesz potential energy for all values of $s$.

In general, optimal configurations for the energy minimization problem may strongly depend on the potential. This happens in the three-dimensional case for $p(r)=e^{-\alpha r^2}$ for density $\rho=1$, as was investigated by Stillinger [30]: for large values of $\alpha$ the face-centered cubic lattice appears to be optimal, for small positive values of $\alpha$ the body-centered cubic lattice seems to be optimal, but when $\alpha\approx \pi$ there are non-periodic configurations that are better than both of these lattices. On the other hand, there is a lot of evidence that in dimension 2 the triangular lattice (the $A_2$ root lattice) minimizes the $p$-energy for all Gaussian and Riesz potentials. In [5] Cohn and Kumar have introduced the following notion generalizing this expected property of the triangular lattice.

Definition (Universal optimality). A configuration $\mathcal{C}\subset\mathbb{R}^d$ is called universally optimal if it minimizes potential energy among all configurations having the same density as $\mathcal{C}$ for all potentials~$p$ that are completely monotonic functions of squared distance.

Here a function $p$ is called a completely monotonic function of squared distance if $p(r)=g(r^2)$ for some function $g$ that is completely monotone, i.e., satisfies $(-1)^kg^{(k)}(r)>0$ for all $k\ge0$. By a theorem of Bernstein, the positive linear span of exponentials $t\mapsto e^{-\alpha t}$, $\alpha>0$ is dense in the space of all compltely monotone functions, and hence to check that a configuration is universally optimal, it is necessary and sufficient to check that it is optimal for all Gaussian potentials. Cohn and Kumar [5] have proved that in 1 dimension the integer lattice $\mathcal{C}=\mathbb{Z}\subset\mathbb{R}$ is universally optimal and proposed the following conjecture.

Conjecture (Cohn, Kumar). In dimensions 2, 8, and 24 the configurations given by the triangular lattice, the $E_8$ root lattice, and the Leech lattice respectively are universally optimal.

Universally optimal configurations are expected to be extremely rare, and little is known about them, even conjecturally. In [6] Cohn, Kumar, and Schürmann gave some numerical evidence that the $D_4$ root lattice should be universally optimal in $\mathbb{R}^4$, and somewhat weaker evidence hinting at universal optimality of a certain 9-dimensional configuration previously described by Conway and Sloane [11], but unlike the cases in the Cohn-Kumar conjecture no viable strategy is known for how one can prove the universal optimality of these configurations. On the other hand, knowing that a configuration is universally optimal has several important consequences: in particular, it solves the crystallization problem in the corresponding dimension, and gives an explicit formula for the leading term in the asymptotic expansion of minimal Riesz energy on compact surfaces (for these and related results see [29], [23], [16]).

Linear programming bounds

Cohn and Kumar have in fact formulated a stronger conjecture: a certain linear programming bound for energy should be tight in dimensions 2, 8, and 24. We now describe this bound.

We use the following normalization for the Fourier transform in $\mathbb{R}^d$:
\[\widehat{f}(\xi) = \int_{\mathbb{R}^{d}}f(x)e^{-2\pi i \langle x,\xi\rangle}dx,
\qquad\qquad \langle x,\xi\rangle := x_1\xi_1+\dots+x_d\xi_d.\]
Recall that $f\colon\mathbb{R}^d\to\mathbb{R}$ is a Schwartz function if it is smooth and all of its partial derivatives are rapidly decaying, i.e, $\sup_{x\in\mathbb{R}^d} |x|^k|D^{\alpha}f(x)| < +\infty$ for all $k\ge 0$ and all multi-indices $\alpha\ge0$.

The linear programming bound of Cohn and Kumar is based on the following result for sphere packing densities from [9].

Theorem (Cohn, Elkies). Let $f\colon\mathbb{R}^d\to\mathbb{R}$ be a Schwartz function such that $f(0)=\widehat{f}(0)=1$, $\widehat{f}\ge 0$, and $f(x)\le 0$ for $|x|\ge r$. Then the density of any sphere packing configuration $\mathcal{C}$ satisfies \[\rho(\mathcal{C}) \le (r/2)^{d}.\]

Using this result Cohn and Elkies have obtained new upper bounds for the best packing density in low dimensions improving on previously known bounds (see Table 3 in [9]). It is now also known [10] that the Cohn-Elkies bound can be used to match the best known asymptotic upper bound of Kabatiansky and Levenshtein [18]. Based on numerical experimentation Cohn and Elkies have conjectured that their bound is tight in dimensions 2, 8, and 24, that is, they conjectured that there exists an auxiliary function $f$ (sometimes referred to as a magic function) for which their upper bound on $\rho(\mathcal{C})$ would be achieved for some configuration $\mathcal{C}$. In a breakthrough work [34] Viazovska found a construction of such a magic function $f$ in 8 dimensions and shortly after that, in [7] a construction was found also for the 24-dimensional case. Note that the question about existence of magic functions for $d=2$ (corresponding to $r=(4/3)^{1/4}$ in the Cohn-Elkies bound) remains open.

In [5] Cohn and Kumar have extended the Cohn-Elkies linear programming bound to the energy minimization problem. (As formulated in [5], the following theorem dealt only with periodic configurations; the general case is due to Cohn and de Courcy-Ireland [4].)

Theorem (Cohn, Kumar). Let $f\colon\mathbb{R}^d\to\mathbb{R}$ be a Schwartz function such that
        \begin{cases}
            f(x) &\le\;\; p(|x|),\quad x\ne 0,\\
            \widehat{f}(\xi) &\ge\;\; 0, \;\;\quad\quad \xi\in\mathbb{R}^d.
        \end{cases}
Then any discrete configuration $\mathcal{C}\subset\mathbb{R}^d$ of density $\rho$ satisfies
\[E(\mathcal{C},p) \;\ge\; \rho \widehat{f}(0) - f(0).\]
Moreover, if for a lattice $\Lambda$ the function $f$ additionally satisfies
        \begin{cases}
            f(x) &=\quad p(|x|),\quad\;\; x\in \Lambda\smallsetminus\{0\},\\
            \widehat{f}(\xi) &=\quad 0, \;\quad\quad\quad \xi\in \Lambda^{*}
            \smallsetminus\{0\},
        \end{cases}
then $\mathcal{C}=\Lambda$ has optimal $p$-energy among all configurations of the same density as $\Lambda$.

Similarly to the sphere packing problem, Cohn and Kumar have observed that in dimensions 2, 8, and 24 their lower bound for potential energy could be made very close to the energy of existing configurations. They conjectured that in these dimensions for any Gaussian potential $p(r)=e^{-\alpha r^2}$, $\alpha>0$ one could find a function $f$ for which their lower bound would be tight, or equivalently, that $f$ would satisfy both inequalities and equalities in the above theorem. Such functions are also sometimes called magic functions.

In dimensions 8 and 24 such magic functions were recently constructed by Cohn, Kumar, Miller, Radchenko, and Viazovska in [8], thus proving the following result.

Theorem. The $E_8$ root lattice and the Leech lattice are universally optimal.

Next we will outline the key ideas used in the proof of this theorem.

Fourier interpolation

Cohn and Kumar [5] proved the universal optimality of the integer lattice in dimension 1 by constructing magic functions $f$ satisfying the tightness conditions of their linear programming bound. Their construction crucially relied on the Whittaker-Shannon sampling formula (more precisely, a variant of the Whittaker-Shannon formula described in [33], Eq.(2.22)). The proof of universal optimality in dimensions 8 and 24 also crucially relies on a certain interpolation formula but of a quite different kind.

The magic functions $f$ constructed in [8] are radial. (In general there is no loss of generality in restricting to radial functions, since one can show that averaging over $O(d)$-orbit of any optimal
function $f$ preserves all conditions in the Cohn-Kumar Theorem.) An important observation is that (using the fact that any even unimodular lattice has vectors of all lengths $\sqrt{2n}$ for $n\ge
n_0$) the optimality conditions in the Cohn-Kumar theorem together imply that $f$ must satisfy
\begin{align*}\label{eq:eqs2}
    \begin{split}
        &f(\sqrt{2n})=p(\sqrt{2n}),\qquad  f'(\sqrt{2n})=p'(\sqrt{2n}), \\
        &\widehat{f}(\sqrt{2n})=0, \qquad\qquad\;\;\; \widehat{f}{\,}'(\sqrt{2n})=0
    \end{split}
\end{align*}
for all $n\ge2$ if $d=24$ and for all $n\ge1$ if $d=8$ (for radial function $f$ we abuse notation and write $f'(x)$ to denote the radial derivative of $f$). Somewhat miraculously, these necessary conditions in fact determine the function $f$ uniquely since one has the following result.

Theorem (Fourier interpolation formula [8]). For $d\in\{8,24\}$ there exist two sequences of radial Schwartz functions $a_n, b_n\colon\mathbb{R}^d\to\mathbb{R}$, $n\ge 0$ such that for any radial Schwartz function $f$ one has
      $$  f(x) = \sum_{n\ge n_0} a_n(x)f(\sqrt{2n}) + \sum_{n\ge n_0} b_n(x)f'(\sqrt{2n}) + \sum_{n\ge n_0}\widehat{a_n}(x)\widehat{f}(\sqrt{2n}) + \sum_{n\ge n_0}\widehat{b_n}(x)\widehat{f}{\,}'(\sqrt{2n}),$$

    where $n_0=1$ for $d=8$ and $n_0=2$ for $d=24$.

An important feature of this interpolation formula is that it is free: for any assignment of the values $\alpha_n$, $\beta_n$, $\gamma_n$, $\delta_n$ in place of $f(\sqrt{2n})$, $f'(\sqrt{2n})$, $\widehat{f}(\sqrt{2n})$, and $\widehat{f}\,'(\sqrt{2n})$, as long as the sequences $\alpha_n$, $\beta_n$, $\gamma_n$, and $\delta_n$ are rapidly decaying, the right-hand-side of the above formula defines a Schwartz function $f$ with the expected interpolatory properties (see [8], Theorem 1.9).

Let us briefly outline how the above interpolation formula is used to construct magic functions for the proof of universal optimality in dimensions 8 and 24. An important feature of the above interpolation formula is that it can be made completely explicit: the functions $a_n$ and $b_n$ are constructed from Laplace transforms of certain weakly holomorphic quasi-modular forms (for the notion of quasi-modularity see [19]) and more general Eichler integrals for the group $PSL_2(\mathbb{Z})$. Moreover, the sequence of these quasi-modular forms (and more general objects) that appear under the Laplace transform has a generating series that is also completely explicit. Using all these explicit formulas one can write down a candidate for the magic function $f$ for the Gaussian potential $p(r)=e^{-\pi \alpha r^2}$ in the form
\[f(x) = e^{-\pi \alpha |x|^2} +
\sin^2\Big(\frac{\pi |x|^2}{2}\Big)
\int_{0}^{\infty}K(i\alpha,it)e^{-\pi t |x|^2}dt\,.\]
Here $K(\tau,z)$ is a component in a Green-like modular kernel arising from a certain representation of $PSL_2(\mathbb{Z})$. It turns out that both inequalities $f(x)\le e^{-\pi\alpha|x|^2}$ and $\widehat{f}(\xi)\ge0$ follow from the inequality $K(i\alpha,it)<0$ (for all $\alpha,t>0$) for the kernel function (for $d=8$ this observation suffices but for $d=24$ the argument becomes more complicated because $f$ needs to be defined using analytic continuation). The inequality $K(i\alpha,it)<0$ after an appropriate change of variables reduces to an elementary (although quite complicated, involving polynomials, logarithms, and elliptic integrals) two-variable inequality on the unit square that is then proved with computer assistance.

Connection to modular forms

The precise details of the construction of $a_n$ and $b_n$ are rather involved, but let us explain how modular forms appear in the proof. First, we note that the linear span of complex Gaussians $e^{\pi i \tau |x|^2}$ is dense in the space of all radial Schwartz functions (see, e.g., [8], Lemma 2.2]). Hence it suffices to verify the interpolation formula only for $f(x)=e^{\pi i \tau|x|^2}$. If we then introduce the following notation (where we suppress $x$)
\begin{align*} \label{eq:fgdef}
    F(\tau) =& \sum_{n=n_0}^{\infty} a_n(x)e^{2\pi i n\tau }+
    (2\pi i \tau)\sum_{n=n_0}^{\infty} \sqrt{2n}b_n(x)e^{2\pi i n\tau },\\
    G(\tau) =& \sum_{n=n_0}^{\infty} \widehat{a_n}(x)e^{2\pi i n\tau }+
    (2\pi i \tau)\sum_{n=n_0}^{\infty} \sqrt{2n}\,\widehat{b_n}(x)e^{2\pi i n\tau },
\end{align*}
then $F$ and $G$ are analytic functions (of moderate growth) on upper half-plane satisfying
$$    e^{\pi i \tau |x|^2} = F(\tau) + (\tau/i)^{-d/2}G(-1/\tau)\,,\qquad \tau\in\ \mathbb{H}. $$
The key idea is now to forget about dependence on $x$ completely and to consider above equation as an identity between holomorphic functions of $\tau$.

From the definition of $F(\tau)$ and $G(\tau)$ it is easy to see that $F(\tau+2)-2F(\tau+1)+F(\tau)=0$ and a similar identity holds for $G$. In terms of the slash action of $\mathbb{Z}[PSL_2(\mathbb{Z})]$ in weight $d/2$, defined by $(f|[\gamma])(\tau)=(c\tau+d)^{-d/2}f(\gamma \tau)$ for $\gamma=$ $\in PSL_2(\mathbb{Z})$ and extended by linearity, the conditions on $F$ and $G$ can be rewritten as
\[\begin{cases}
    F|([T]-1)^2=0\,,\qquad    G|([T]-1)^2=0\,,\\
    F + G|[S] = e^{\pi i \tau |x|^2}\,,
\end{cases}\]
where as usual $S=$ and $T= $. Conversely, any solution to this system gives rise to an interpolation formula of the type considered above, as long as $F$ and $G$ are analytic functions of moderate growth in $\mathbb{H}$.

To make connection to modular forms for $PSL_2(\mathbb{Z})$ more direct we define $\mathcal{F}\colon \mathbb{H} \to\mathbb{C}^6$ by
\[\mathcal{F}(\tau) = (F, F|[T], F|[TS], -G, -G|[T], -G|[TS]).\]
Then a direct calculation using the functional equations for $F$ and $G$ shows that for any $\gamma\in PSL_2(\mathbb{Z})$ one has
\[\mathcal{F}|[\gamma] = \mathcal{F}\cdot \rho(\gamma) + \phi_{\gamma},\]
where the homomorphism $\rho\colon\mathrm{PSL}_2(\mathbb{Z})\to GL_6(\mathbb{C})$ is defined on the generators by
\[
\rho(T)=\begin{pmatrix}
    0 & -1 & 2 & 0 & 0 & 0 \\
    1 & 2 & 0 & 0 & 0 & 0 \\
    0 & 0 & 0 & 0 & 0 & -1 \\
    0 & 0 & 0 & 0 & -1 & 2 \\
    0 & 0 & 0 & 1 & 2 & 0 \\
    0 & 0 & -1 & 0 & 0 & 0
\end{pmatrix},\quad\;
\rho(S)=\begin{pmatrix}
    0 & 0 & 0 & 1 & 0 & 0 \\
    0 & 0 & 1 & 0 & 0 & 0 \\
    0 & 1 & 0 & 0 & 0 & 0 \\
    1 & 0 & 0 & 0 & 0 & 0 \\
    0 & 0 & 0 & 0 & 0 & 1 \\
    0 & 0 & 0 & 0 & 1 & 0
\end{pmatrix},
\]
and $\gamma\mapsto\phi_{\gamma}$ is a certain vector-valued $1$-cocycle for $PSL_2(\mathbb{Z})$. (It suffices to check the above functional equation for $\mathcal{F}$ only for the generators $\gamma=T$ and $\gamma=S$ of $ PSL_2(\mathbb{Z})$.)

The resulting modular cocycle equation for $\mathcal{F}$ can then be solved by expressing  $\mathcal{F}$ as a contour integral of $\phi_{\gamma}$ against a certain matrix-valued kernel function, by analogy with the approach used by Duke, Imamoglu, and Tóth in [14]. Alternatively, if one makes a change of variable in $\mathcal{F}$ from $\tau$ to $j(\tau)$, where $j$ is the elliptic $j$-invariant function, one obtains a vector-valued Riemann-Hilbert problem (see [12]) on the quotient $X(1)$ with jump conditions on the image of the boundary of the standard fundamental domain for $PSL_2(\mathbb{Z})$. Both approaches after simplification lead to the scalar-valued kernel function $K(\tau,z)$ alluded to above, giving an explicit expression for $K$ in terms of weakly holomorphic quasi-modular forms and Eichler integrals for $\Gamma(2)$.

We note that a similar but technically simpler interpolation formula, whose construction involves scalar-valued modular forms (on $\Gamma(2)$ instead of $PSL_2(\mathbb{Z})$) was proved somewhat earlier by Radchenko and Viazovska in [25].

We end by mentioning a conjecture from [8] regarding extremal functions for the Cohn-Kumar optimization problem in all dimensions. By the Cohn-Kumar optimization problem we mean the problem of maximizing the quantity $\rho\widehat{f}(0)-f(0)$ under the conditions of the Cohn-Kumar linear programming bound for $f$.

Conjecture. (i) For $d\ge 4$ the optimal solution to the $d$-dimensional Cohn-Kumar optimization problem with $p(r)=e^{-\alpha\pi r^2}$ is unique and is given by a radial Schwartz function $f$.

(ii) The radii $r$ for which $f(r)=e^{-\alpha \pi r^2}$ form a discrete set $r_1<\dots<r_n<\dots$ with $r_n^2\sim 2n$, $n\to\infty$, the condition $\widehat{f}(r)=0$ holds for exactly the same values $r=r_n$, and the numbers $r_n$ do not depend on $\alpha$.

(iii) Moreover, there exists a linear interpolation formula recovering any radial Schwartz function $f\colon\mathbb{R}^d\to\mathbb{R}$ from the values $f(r_n)$, $f'(r_n)$, $\widehat{f}(r_n)$, $\widehat{f}'(r_n)$, $n\ge1$.

This conjecture suggests that Fourier interpolation formulas similar to the one used in the proof of universal optimality are not confined to the situation when there exists an exceptional object like the $E_8$ or the Leech lattice, but presents a more universal, if still rather mysterious, phenomenon.