The following is a linear programming bound for the sphere packing problem.
(Cohn-Elkies, 2003)
Suppose \(f: \mathbb{R}^{d} \rightarrow \mathbb{R}\) is an admissible function (i.e. Poisson summation works for \(f\)) satisfying the following three conditions.
Then the density of sphere packings in \(\mathbb{R}^{d}\) is bounded above by \(B_{d}(r/2)\), where \(B_{d}\) denotes the volume of the unit ball in \(\mathbb{R}^{d}\).
Furthermore, there is equality for a lattice \(\Lambda\), if and only if
The condition that \(\hat{f}\) is positive is equivalent to saying that the kernel \((x,y) \mapsto f(x-y)\) is positive definite.
Here is an equivalent formulation of the same theorem. The equivalence simply follows from the dilations property of Fourier transform
Suppose \(f:\mathbb{R}^{n} \rightarrow \mathbb{R}\) is an admissible function, not identically zero, and satisfies the following two conditions.
Then the sphere packing density of packing in \(n\)-dimensions is bounded above by \[\begin{align} B_{n}(1/2) \frac{f(0)}{\hat{f}(0)}, \end{align}\] where \(B_{n}\) is as in the theorem above.
Due to some limiting argument (see Appendix A in [1]), it is sufficient to consider the case when the packing is with balls of radius \(1/2\) and with centers given by \(F + \Lambda\), where \(\Lambda \subseteq \mathbb{R}^{n}\) is a lattice and \(F \subset \mathbb{R}^{n}\) is a finite subset of points, no two equivalent modulo \(\Lambda\).
So with this, we get that packing efficiency is \(B_{d}(1/2) \frac{\# F}{\mathop{\mathrm{vol}}(\mathbb{R}^{n}/\Lambda)}\),
With \(f\) being the function as described, we have from the Poisson summation formula \[\begin{align} \sum_{v \in \Lambda + F - F }^{ } f(v) = \sum_{f_1,f_2 \in F}\sum_{v \in \Lambda}^{} f(v +f_1 - f_2 ) & = \frac{1}{\mathop{\mathrm{vol}}(\mathbb{R}^{d}/\Lambda)} \sum_{t \in \Lambda^{*}}^{} \sum_{f_1,f_2 \in F}e^{2\pi i \langle f_1 - f_2, t\rangle} f(t) \\ & = \frac{1}{\mathop{\mathrm{vol}}(\mathbb{R}^{d}/\Lambda)} \sum_{t \in \Lambda^{*}}^{} \hat{f}(t) \left| \sum_{f\in F}e^{2\pi i \langle f, t\rangle} \right|^{2} \\ & \ge \frac{ ( \# F)^{2} } {\mathop{\mathrm{vol}}(\mathbb{R}^{d} / \Lambda)} \hat{f}(0). \end{align}\]
Now notice that each term \(f(v + f_1 - f_2)\) on the left is \(f\) evaluated on the diference of two centers. Since we assumed that the center distances are at least \(1\). Hence, unless \(v = f_2 - f_1\), we have that \(f(v+f_1 - f_2) \le 0\). According to our assumption, \(f_2 - f_1\) can be a lattice point if and only if \(f_1 = f_2\), so \[\begin{align} \frac{ (\# F)^{2} \hat{f}(0)}{\mathop{\mathrm{vol}}(\mathbb{R}^{d}/ \Lambda)} \le \sum_{v \in \Lambda + F-F } f(v) \le ( \# F)f(0). \end{align}\]
This gives what we require.
Cohn and Elkies conjectured that there exists a radial Schwartz function \(f: \mathbb{R}^{2} \rightarrow \mathbb{R}\) such that
This is the magic function for the \(A_{2}\) lattice in \(\mathbb{R}^{2}\), that is, the hexagonal lattice of Eisenstein integers. It follows then from the Poisson summation that for any \(n \in \mathbb{Z}_{\geq 1}\) that is the norm of an Eisenstein integer, one has \[\begin{equation} f( \sqrt{\tfrac{2n}{ \sqrt{3}}}) = f'( \sqrt{ \tfrac{2n}{ \sqrt{3}}}) = \widehat{f} ( \sqrt{ \tfrac{2n}{ \sqrt{3}}}) = 0, \end{equation}\] and for \(n \in \mathbb{Z}_{>1}\) of the same form one has \[\begin{equation} \widehat{f}'( \sqrt{ \tfrac{2n}{ \sqrt{3}}}) = 0. \end{equation}\]
See here
This page was updated on October 6, 2025.
Main Page