The Poisson summation formula, Minkowski's first theorem, and the density of sphere packings

I opened by accident a paper by Henry Cohn and Noam Elkies, New upper bounds on sphere packings I, Annals of Mathematics, 157 (2003), 689–714, and I had the good surprise to see a beautiful application of the Poisson summation formula to upper bounds for the density of sphere packings.

In fact, their argument is very close to a proof of the first theorem of Minkowski about lattice points in convex bodies which I had discovered in 2009. However, a final remark in their paper, appendix C, shows that this proof is not really new. Anyway, the whole story is nice enough to prompt me to discuss it in this blog.

1. The Poisson formula

I first recall the Poisson formula: let $f\colon\mathbf R^n\to \mathbf R$ be a continuous function whose Fourier transform $\hat f$ is integrable, let $L$ be a lattice in $\mathbf R^n$, and let $L'$ be the dual lattice of $L$. Then, 

$$\sum_{x\in L} f(x) = \frac1{\mu(\mathbf R^n/L)}\sum_{y\in L'} \hat f(y).$$

In fact, one needs a bit more about $f$ that the above hypotheses (but we'll ignore this in the sequel). For example, it is sufficient that $f(x)$ and $\hat f(x)$ be bounded from above by a multiple of $1/(1+\| x\|)^{n+\epsilon}$, for some strictly positive real number $\epsilon$.

2. Minkowski's first theorem

Let $B$ a closed symmetric convex neighborhood of $0$. Minkowski's first theorem bounds from below the cardinality of $B\cap L$. A natural idea would be to apply the Poisson summation formula to the indicator function $f_B$ of $B$. However, $f_B$ is not continuous, so we need to replace $f_B$ by some function $f$ which satisfies the following properties:

• $f\leq f_B$, so that $\#(B\cap L)= \sum_{x\in L} f_B(x)\geq \sum_{x\in L} f(x)$;
• $\hat f\geq 0$, so that $\sum_{y\in L'} \hat f(y) \geq \hat f(0)$.

The second condition suggest to take for $f$ a function of the form $g*\check g$, so that $\hat f=|\hat g| ^2$. Then, the first condition will hold outside of $B$ if $g$ is supported in $\frac12 B$. Let's try $g=cf_{B/2}$ for some positive real number $c$. For all $x\in\mathbf R^n$,  

$$f(x) \leq f(0) =c^2 \int_{\mathbf R^n} f_{B/2}(x) f_{B/2}(-x) = c^2 \mu(B/2) = c^2 \mu(B)/2^n.$$

It suffices to choose $c=(2^n/\mu(B))^{1/2}$.

On the other hand, 

$$\hat g(0) = \int_{\mathbf R^n} f_{B/2}(x) = \mu(B/2)=c\mu(B)/2^n=1/c.$$

Finally, the Poisson formula implies

$\displaystyle \#(B\cap L) \geq \sum_{x\in L} f(x)  = \frac1{\mu(\mathbf R^n/L)} \sum_{y\in L'}\hat f(y)  \geq \frac1{\mu(\mathbf R^n/L)} \hat f(0)$

$\displaystyle = \frac1{\mu(\mathbf R^n/L)} | \hat g(0)|^2  = \frac{\mu(B)}{2^n}\mu(\mathbf R^n/L).$

This is exactly Minkowski's first theorem!

Of course, one may consider apply this argument to other functions $f$. In the case where $B$ is an Euclidean ball, a natural choice consists in taking a Gaussian $f(x)=a\exp(-b\|x\|^2)$, since then $\hat f$ has the same form. This is what has essentially been done by Schoof and van der Geer in their paper Effectivity of Arakelov divisors and the analogue of the theta divisor of a number field, Selecta Math. New Ser. 6 (2000), 377–398, and Damian Rössler independently. Indeed, up to normalization factors, the left hand side of the Poisson summation formula is then interpreted as the exponential of the $h^0$ of a line bundle over an arithmetic curve, and the Poisson summation formula itself is the analogue of Serre's duality theorem in Arakelov geometry. As Jean-Benoît Bost explained to me, Gaussian functions provide an inequality for $\#(B\cap L)$ which is sharper than Minkowski's first theorem. The details of the computation can be found in my notes about Arakelov geometry (beware, these are mostly a work in slow progress). I have not tried to look for optimal functions beyond that case.

3. The theorem of Cohn-Elkies

We consider a sphere packing, that is a set of points in $\mathbf R^n$ with mutual distances at least 1,

and we want to bound from above its density, that is the ratio of volume occupied by balls of radius $1/2$ centered at these spheres. One may think of a lattice packing, the particular case where the centers of these spheres are exactly the points of a lattice $L$ or, more generally, of periodic packing when the centers of the spheres are finitely many translates $v_1+L,\dots,v_N+L$ of  a lattice $L$. In fact, Cohn and Elkies argue that it suffices to study such periodic packings (repeating periodically an arbitrarily large part of the sphere packing), so we shall do like them and assume that our sphere packing is periodic. 

Now, let $f$ be a real valued function on $\mathbf R^n$ satisfying the following properties:

• $f$ is continuous, integrable on $\mathbf R^n$ as well as its Fourier transform.
• $f(0)>0$ and $f(x)\leq 0$ for $\| x\|\geq 1$;
• $\hat f(x)\geq 0$ for all $x$.

Then, the density $\Delta$ of the sphere packing satisfies 

$$\Delta \leq 2^{-n} \mu(B) \frac{f(0)}{\hat f(0)},$$

where $\mu(B)$ is the volume of the unit ball.

We assume that no difference $v_i-v_j$ is a point of the lattice $L$ (otherwise, we can exclude one translate from the list). With the above notation, the fundamental parallelepiped of the lattice contains exactly $N$ balls of radius $1/2$, hence 

$$\Delta= 2^{-n}\mu(B) \frac N{\mu(\mathbf R^n/L)}.$$

For any $v\in\mathbf R^n$, the Poisson summation formula for $x\mapsto f(x+v)$ writes

$$\sum_{x\in L} f(x+v) = \frac1{\mu(L)} \sum_{y\in L'} e^{2\pi i \langle v,y\rangle} \hat f(y),$$

hence

$\displaystyle \sum_{1\leq j,k\leq N} \sum_{x\in L} f(x+v_j-v_k)  = \frac1{\mu(L)} \sum_{y\in L'}\hat f(y)  \sum_{j,k=1}^N e^{2\pi i \langle v_j-v_k,y\rangle}$ 

$\displaystyle = \frac1{\mu(L)} \sum_{y\in L'}\hat f(y) \left| \sum_{j=1}^N e^{2\pi i \langle v_j,y\rangle} \right|^2.$

All terms of the right hand side are positive or null, so that we can bound it from below by

the term for $y=0$, hence

$$\sum_{1\leq j,k\leq N} \sum_{x\in L} f(x+v_j-v_k) \geq N^2 \frac{\hat f(0)}{\mu(\mathbf R^n/L)}.$$

Now, there is a sphere of our packing centered at $x+v_j$, and another at $v_k$,

so that $\| x+v_j-v_k\|\geq 1$ unless $x+v_j=v_k$, that is $v_k-v_j=x$ hence $x=0$ and $v_j=v_k$. In the first case, the value of $f$ at $x+v_j-v_k$ is negative or null; in the latter, it equal $f(0)$. Consequently, the left hand side of the previous inequality is at most $Nf(0)$.  Finally, $\displaystyle N f(0) \geq N^2 \hat f(0)/\mu(\mathbf R^n/L)$, hence the desired inequality.