ELECTRONIC RESEARCH ANNOUNCEMENTS OF THE AMERICAN MATHEMATICAL SOCIETY Volume 10, Pages 58–67 (June 17, 2004) S 1079-6762(04)00130-1

THE DENSEST LATTICE IN TWENTY-FOUR DIMENSIONS

HENRY COHN AND ABHINAV KUMAR

(Communicated by Brian Conrey)

Abstract. In this research announcement we outline the methods used in our recent proof that the Leech lattice is the unique densest lattice in ℝ^{24}. Complete details will appear elsewhere, but here we illustrate our techniques by applying them to the case of lattice packings in ℝ^{2}, and we discuss the obstacles that arise in higher dimensions.

1. Introduction

Given any lattice Λ ⊂ ℝ^{n} (i.e., a discrete subgroup of rank n), one can form a sphere packing by centering congruent balls at the points of Λ, with radius as large as possible such that their interiors do not overlap. Which lattice maximizes the density of this packing, the fraction of ℝ^{n} covered by the balls? This question arises naturally in geometry, number theory, and information theory (sphere packings are error-correcting codes for a continuous channel, as opposed to a discrete channel).

The densest lattice is known for n ≤ 8. In each of these dimensions, it is a root lattice: A_{1}, A_{2}, A_{3}, D_{4}, D_{5}, E_{6}, E_{7}, or E_{8}. Furthermore each is unique up to scaling and isometries. The books [CS] and [M] are excellent sources of information on lattice packings. (See [Ba, Bl, G, KZ1, KZ2, V] for the original papers.)

What may be the most interesting lattices are the E_{8} root lattice in ℝ^{8} and the Leech lattice in ℝ^{24} (see [E] for a beautiful introduction). They are connected with many other branches of mathematics, and are undoubtedly the densest sphere packings in their dimensions. However, nobody has been able to prove their optimality. The Leech lattice has not even been known to be the densest lattice in its dimension, let alone the densest sphere packing (it is possible that there are sphere packings denser than any lattice packing). By contrast, Blichfeldt [Bl] proved in 1935 that E_{8} is optimal among lattices, and in 1980 Vetčinkin [V] proved its uniqueness.

In this paper we announce the following theorem:

Theorem 1.1. The Leech lattice is the unique densest lattice in ℝ^{24}, up to scaling and isometries of ℝ^{24}.

Our method also yields a new proof that E_{8} is the unique densest lattice in ℝ^{8}. The proofs for ℝ^{8} and ℝ^{24} can be found in [CK]. Here, we will apply the techniques to the case of the hexagonal lattice in ℝ^{2}. That result is of no research interest, because it is quite easy to prove using much simpler methods than ours. Our goal

\begin{matrix}c \\ ◯ \end{matrix}2004 American Mathematical Society

Reverts to public domain 28 years from publication

Received by the editors April 14, 2004.

2000 Mathematics Subject Classification. Primary 11H31, 52C15; Secondary 05B40, 11H55.

Kumar was supported by a summer internship in the Theory Group at Microsoft Research.

is simply to illustrate our approach in a case involving no technical difficulties. At the end of the paper we will outline the additional obstacles that occur in ℝ^{8} and ℝ^{24}.

Our principal technical tool will be the Poisson summation formula. Let f : ℝ^{n} → ℝ be a Schwartz function (i.e., f is smooth and all its derivatives are rapidly decreasing). We define the Fourier transform f̂ of f by

f̂(t) = ∫_{ℝ^{n}} f(x)e^{2πi⟨x,t⟩} dx.

If Λ ⊂ ℝ^{n} is a lattice, then the dual lattice Λ^{∗} is defined by

Λ^{∗} = {y ∈ ℝ^{n} : ⟨x, y⟩ ∈ ℤ for all x ∈ Λ}.

(If v_{1}, …, v_{n} is a basis of Λ, then the basis v_{1}^{∗}, …, v_{n}^{∗} of ℝ^{n} that is dual to v_{1}, …, v_{n} relative to the inner product forms a basis of Λ^{∗}.) The Poisson summation formula states that

∑_{x∈Λ} f(x) = \frac{1}{vol(ℝ^{n}/Λ)} ∑_{t∈Λ^{∗}} f̂(t).

For a review of the standard proof, see Appendix A.

The most effective way to make use of a nontrivial identity such as Poisson summation is to choose f to make the two sides as different as possible. We will apply it using a function f such that f(x) ≤ 0 for |x| sufficiently large, but f̂(t) ≥ 0 for all t. This technique was used in [CE] to prove upper bounds on the sphere packing density (see also [C]). These bounds appear to be sharp in ℝ^{8} and ℝ^{24}, which would solve the full sphere packing problem in those dimensions, but the apparent sharpness has not been proved. It appears that the only dimensions in which it is sharp are 1, 2, 8, and 24, and the one case in which it has been proved is ℝ^{1}.

Our approach to proving Theorem 1.1 is to combine the analytic methods from [CE] with geometric and combinatorial arguments that are specific to lattices. As mentioned above, we will present the details here for the two-dimensional case. We wish to show that the obvious hexagonal packing is the densest lattice packing of disks in ℝ^{2}. For simplicity we will choose the following normalization of the hexagonal lattice. Let Λ_{2} be the lattice with basis v, w, where

v = (\begin{matrix}√ & \overline{2} \\ 0 \end{matrix})

and

w = (\begin{matrix}\sqrt{2}/2 \\ \sqrt{6}/2 \end{matrix}) .

The advantage of this normalization is that Λ_{2} is an even integral lattice. In other words, all inner products of lattice points are integers, and furthermore every lattice point has even norm. Here, |v|^{2} = |w|^{2} = 2 and ⟨v, w⟩ = 1.

Let Λ ⊂ ℝ^{2} be any lattice that is at least as dense as Λ_{2}. We scale Λ so that vol(ℝ^{2}/Λ) = 1 (we refer to vol(ℝ^{2}/Λ) as the covolume of Λ). Unfortunately, vol(ℝ^{2}/Λ_{2}) = \sqrt{3}, so the scalings of Λ and Λ_{2} are not compatible. That will cause us no problems, and in fact each scaling will prove convenient at a certain point in the proof.

Our overall plan is as follows:

(1) Use Poisson summation to study the short vectors in Λ.

(2) Apply this information to see that Λ is, up to scaling, a small perturbation of Λ_{2}.

(3) Prove that Λ_{2} is a strict local optimum for the packing density.

(4) Conclude that either Λ is the same as Λ_{2} (up to scaling and isometries) or it is strictly less dense, which would contradict our assumptions.

Before beginning, it is worth noting that the density of Λ simply depends on its minimal vector length (i.e., the length of the shortest nonzero vectors in Λ). Because vol(ℝ^{2}/Λ) = 1, there is one sphere per unit volume in space, and the density of the packing equals the volume of such a sphere. More generally, the density of any lattice L ⊂ ℝ^{n} equals

\frac{vol(B_{r})}{vol(ℝ^{n}/L)},

where r denotes the packing radius and B_{r} denotes a ball of radius r. The packing radius is half of the minimal vector length, because that is the radius at which adjacent spheres are tangent. Thus, our goal becomes understanding the minimal vector length of Λ.

Because Λ is at least as dense as Λ_{2}, its minimal vectors have length at least (4/3)^{1/4}. To see why, recall that vol(ℝ^{2}/Λ_{2}) = \sqrt{3} and its minimal vectors have length \sqrt{2}. Rescaling Λ_{2} by a factor of 3^{−1/4} makes the covolume 1 and yields minimal vector length (4/3)^{1/4}.

2. Applications of Poisson summation

Define f : ℝ^{2} → ℝ by f(x) = p_{f}(2π|x|^{2})e^{−π|x|^{2}}, where

p_{f}(u) = 20812 + 756u + 1107u^{2} − 216u^{3}.

Then one can calculate that f̂(t) = pf̂(2π|t|^{2})e^{−π|t|^{2}}, where

pf̂(u) = 20812 + 5940u − 2781u^{2} + 216u^{3} = (43 + 24u)(−22 + 3u)^{2}.

We have f(0) = f̂(0), f(x) < 0 for |x| ≥ 1.084, and f̂(t) ≥ 0 for all t. (Terminating decimal expansions such as 1.084 represent exact rational numbers, not floating point approximations.) Up to scaling, p_{f} is the unique polynomial of degree 3 such that f(0) = f̂(0) and pf̂ has a double root at 22/3, and that is how it was constructed.

Lemma 2.1. Λ contains a nonzero vector of length at most 1.084.

Note that our lower bound (4/3)^{1/4} for the minimal vector length is between 1.074 and 1.075.

Proof. By Poisson summation,

∑_{x∈Λ} f(x) = ∑_{t∈Λ^{∗}} f̂(t) ≥ f̂(0),

because f̂(t) ≥ 0 for all t. On the other hand, f(0) = f̂(0) and f(x) < 0 for |x| ≥ 1.084, so it follows that

∑_{x∈Λ, 0<|x|<1.084} f(x) > 0.

Therefore the minimal vector length of Λ is at most 1.084. □

Call a vector in Λ “nearly minimal” if it has length in [(4/3)^{1/4}, 1.114) (the reason for the upper bound of 1.114 will become clear below).

Lemma 2.2. There are at most six nearly minimal vectors in Λ.

Proof. If x and y are nearly minimal and θ ∈ [0, π] is the angle between them, then

cos θ = \frac{|x|^{2} + |y|^{2} − |x − y|^{2}}{2|x||y|} ≤ \frac{2 · 1.114^{2} − (4/3)^{1/2}}{2 · (4/3)^{1/2}} < 0.575.

Thus, θ > cos^{−1} 0.575 > 2π · 0.152. There is no room for seven vectors to be separated by such an angle: if we assign to each nearly minimal vector the arc on the unit circle consisting of all points within angle 2π · 0.076 of it, then these arcs do not overlap. Because each arc has length 2π · 0.152, if there were seven of them then the arc length of the unit circle would be at least 2π · 1.064. □

In the other direction, we can use Poisson summation to see that there are more than five nearly minimal vectors in Λ (so there must be exactly six). First we need one more lemma:

Lemma 2.3. Every nonzero vector in Λ is either nearly minimal or else has length at least 1.62.

Proof. First, note that f(x) is a decreasing function of |x| for |x| ∈ [0, 1.084]. In the inequality

∑_{x∈Λ} f(x) ≥ f̂(0),

Lemma 2.2 implies that there are at most six positive terms on the left hand side other than x = 0. Each of them is at most f((4/3)^{1/4}), where for r ∈ [0, ∞) we write f(r) to indicate the common value f(x) with |x| = r. Thus,

(2.1)  6f((4/3)^{1/4}) + ∑_{x∈Λ, f(x)<0} f(x) ≥ 0.

One can check that f(x) < −3f((4/3)^{1/4}) < 0 for |x| ∈ [1.114, 1.62], and hence there is no x ∈ Λ satisfying |x| ∈ [1.114, 1.62] (because the x and −x terms in (2.1) would combine to make the left hand side negative). □

Lemma 2.4. There are more than five nearly minimal vectors in Λ.

Proof. Define g : ℝ^{2} → ℝ by g(x) = p_{g}(2π|x|^{2})e^{−π|x|^{2}}, where

p_{g}(u) = (13 − u)(1075 + 220u + 69u^{2}).

Then ĝ(t) = pĝ(2π|t|^{2})e^{−π|t|^{2}}, where

pĝ(u) = (401 + 69u)(u − 7)^{2}.

We have g(x) ≤ 0 for |x| ≥ 1.62, and ĝ(t) ≥ 0 for all t.

It follows from Poisson summation that if M denotes the set of nearly minimal vectors in Λ, then

g(0) + ∑_{x∈M} g(x) ≥ ĝ(0).

On the other hand, g(x) is a decreasing function of |x| for |x| ∈ [(4/3)^{1/4}, 1.114), so

g(0) + |M|g((4/3)^{1/4}) ≥ ĝ(0).

Thus,

|M| ≥ \frac{ĝ(0) − g(0)}{g((4/3)^{1/4})} > 5.89,

as desired. □

3. Arrangement of the nearly minimal vectors

There are two distinct nearly minimal vectors x, y ∈ Λ within angle 2π/6 of each other, because that is the average angle between them as one moves around the circle. Then x − y must be nearly minimal as well: if θ is the angle between them, then

|x − y|^{2} = |x|^{2} + |y|^{2} − 2|x||y| cos θ ≤ |x|^{2} + |y|^{2} − |x||y|

because θ ≤ 2π/6, so

|x − y|^{2} ≤ 2 · 1.114^{2} − (4/3)^{1/2} < 1.33.

It follows that x, y, x − y, and their negatives form the full list of nearly minimal vectors.

Lemma 3.1. The vectors x and y form a basis of Λ.

Proof. The nearly minimal vectors are all in the span of x and y, so we need only prove that the nearly minimal vectors span Λ. Suppose not, and that z ∈ Λ is the smallest vector not in their span. There cannot exist a nearly minimal vector u such that |u − z| < |z|. For every nearly minimal u, the angle θ between u and z satisfies

cos θ = \frac{|u|^{2} + |z|^{2} − |u − z|^{2}}{2|u||z|} ≤ \frac{|u|}{2|z|} < \frac{1}{2} = cos \frac{2π}{6}

because |u − z| ≥ |z| and |u| < |z|. In other words, no nearly minimal vector is within angle 2π/6 of z. That is impossible, because then z together with the nearly minimal vectors would form seven vectors separated by angles of at least 2π · 0.152. □

Thus, we have shown that Λ has a basis x, y such that |x|, |y| ∈ [(4/3)^{1/4}, 1.114) and the angle between x and y is in [2π · 0.152, 2π/6].

Consider the lattice 3^{1/4}Λ, which we have rescaled so that its covolume is 3^{1/2}, the same as that of Λ_{2}. The rescaled basis vectors 3^{1/4}x, 3^{1/4}y have lengths in [\sqrt{2}, 1.467) and therefore norms in [2, 2.16). If θ denotes the angle between them then

⟨3^{1/4}x, 3^{1/4}y⟩ = 3^{1/2}|x||y| cos θ ∈ [2 cos(2π/6), 1.467^{2} cos(2π · 0.152)] ⊂ [1, 1.243].

Therefore the Gram matrix of 3^{1/4}Λ with respect to the basis 3^{1/4}x, 3^{1/4}y has entries within 0.243 of those of the Gram matrix of Λ_{2} with respect to v, w. It is in this sense that Λ is a perturbation of Λ_{2}.

4. Local optimality

In this section, we prove that Λ_{2} is a strict local optimum for density. It is more convenient to deal with quadratic forms than with lattices. Let Q be the quadratic form corresponding to Λ_{2} and its basis v, w (i.e., Q(s, t) = |sv + tw|^{2} for s, t ∈ ℝ). The Gram matrix of Λ_{2} with respect to the basis v, w is

(\begin{matrix}2 & 1 \\ 1 & 2 \end{matrix}) ,

and we have

Q(s, t) = (s t) (\begin{matrix}2 & 1 \\ 1 & 2 \end{matrix}) (\begin{matrix}s \\ t \end{matrix}) .

Note that the Gram matrix of a lattice basis determines the lattice up to isometries, so we lose no information by focusing on it.

The minimal norm M of Q is the minimum of Q(s, t) over (s, t) ∈ ℤ^{2} \ {(0, 0)} (i.e., M = 2), and the determinant D is defined by

D = det (\begin{matrix}2 & 1 \\ 1 & 2 \end{matrix}) = 3.

In these terms, the density of Λ_{2} equals (π/4)D^{−1/2}M, because D^{1/2} is the covolume vol(ℝ^{2}/Λ_{2}) and M is the square of the minimal vector length of Λ_{2}.

We will show that if Q is slightly perturbed, then either the perturbation is itself proportional to Q (which corresponds to rescaling Λ_{2}) or else the density strictly decreases. We use symmetric perturbations because Gram matrices are symmetric.

Let max{|a|, |b|, |c|} = ρ > 0, and let Q_{ρ} be the perturbation of Q with matrix

(\begin{matrix}2 + a & 1 + b \\ 1 + b & 2 + c \end{matrix}) .

Let

D_{ρ} = det (\begin{matrix}2 + a & 1 + b \\ 1 + b & 2 + c \end{matrix}) = 3 + 2(a + c − b) + (ac − b^{2}),

and let M_{ρ} be the minimal norm of Q_{ρ}.

Lemma 4.1. If ρ < 12/47, then either D_{ρ}^{−1/2}M_{ρ} < D^{−1/2}M or Q_{ρ} is proportional to Q.

Proof. We begin by assuming that a + c = b. In other words, the linear terms in the expansion of D_{ρ} cancel. The minimal norm of Q occurs at (1, 0), (0, 1), (1, −1), and their negatives, and at these points Q_{ρ} takes on the values 2 + a, 2 + c, and 2 + a − 2b + c, respectively. Consider the perturbations a, c, and a − 2b + c of these values away from 2. It follows from a + c = b that a − 2b + c = −b and that these three perturbations sum to 0. Thus, at least one of them must be negative (if all three vanished then ρ would too). In fact, one of them is at most −ρ/2: if a, c, or −b equals −ρ then that is trivial, and otherwise one of them equals ρ and then one of the other two is at most −ρ/2 because they sum to 0.

Thus, if a + c = b, then M_{ρ} ≤ 2 − ρ/2. When we combine that with

D_{ρ} = 3 + (ac − b^{2}) ≥ 3 − 2ρ^{2},

we find that

D_{ρ}^{−1/2}M_{ρ} ≤ (3 − 2ρ^{2})^{−1/2}(2 − ρ/2).

When 0 < ρ < 24/35,

(3 − 2ρ^{2})^{−1/2}(2 − ρ/2) < 3^{−1/2} · 2 = D^{−1/2}M,

so the density of the perturbed lattice is strictly less than that of Λ_{2}.

In general we cannot assume a + c = b. However, Q_{ρ} is proportional to a perturbation of Q in which that equation holds. Set A = (a−2c+2b)/(3+a+c−b), B = (4b − a − c)/(3 + a + c − b), and C = (2b + c − 2a)/(3 + a + c − b). Then

(\begin{matrix}2 + a & 1 + b \\ 1 + b & 2 + c \end{matrix}) = (1 + (a + c − b)/3) (\begin{matrix}2 + A & 1 + B \\ 1 + B & 2 + C \end{matrix})

and A+C = B. Clearly, |A| ≤ 5ρ/(3−3ρ), |B| ≤ 2ρ/(1−ρ), and |C| ≤ 5ρ/(3−3ρ). If ρ < 12/47, then |A|, |B|, |C| < 24/35, and so the perturbed lattice is either itself hexagonal or else strictly less dense than Λ_{2}. □

Theorem 4.2. The hexagonal lattice Λ_{2} is the unique densest lattice in ℝ^{2}, up to scaling and isometries of ℝ^{2}.

Proof. We have seen that if the Gram matrix of Λ_{2} is perturbed by at most 12/47, then either the density strictly decreases or the lattice remains the same (up to a similarity). On the other hand, the Gram matrix of 3^{1/4}Λ with respect to 3^{1/4}x, 3^{1/4}y has entries within 0.243 of those of the Gram matrix of Λ_{2}. Observing that 0.243 < 12/47 completes the proof. □

5. Relationship with the higher-dimensional cases

The techniques we apply in [CK] are completely analogous to those we have used here, and each of the lemmas from this paper has a counterpart there. However, there are a couple of key steps in [CK] that are not apparent from the twodimensional case, as well as some technical obstacles that must be overcome.

5.1. Spherical codes. The biggest conceptual difference between this proof and the one in [CK] is in how the arrangement of nearly minimal vectors is studied. In each case, when rescaled to the unit sphere they form a spherical code, i.e., a subset of the sphere that contains no pair of points closer than some given angle. In ℝ^{2} the unit sphere is a circle, and distributing points on a circle with at least a given angle between them is trivial. In higher dimensions this problem is much more subtle.

Independently, Levenshtein [Lev] and Odlyzko and Sloane [OS] used linear programming bounds for spherical codes to solve the kissing problem in ℝ^{8} and ℝ^{24}: how many unit balls can be placed tangent to a given one, if they may not overlap except tangentially? The answers are 240 and 196560, respectively, and the arrangements come from the E_{8} and Leech lattice packings.

In [CK] we use linear programming bounds in a similar way to bound the number of nearly minimal vectors and the angles between them.

5.2. Spherical designs and association schemes. It is not enough in higher dimensions simply to compute the number of nearly minimal vectors. To determine the configuration more precisely, we apply techniques derived from [DGS]. In particular, we formulate a notion of an approximate spherical design, and prove that the nearly minimal vectors form one. We then show that if they are grouped according to the (approximate) angles between them, then they form an association scheme. Finally, we prove that the association scheme with these parameters is unique, which lets us conclude that the nearly minimal vectors form a perturbation of the desired configuration. In principle all these results have analogues in ℝ^{2}, with similar proofs, but we did not require them for Theorem 4.2, and including them would have substantially lengthened this article.

5.3. Local optimality and angle bounds. The proof of strict local optimality is analogous to that given here. We use Voronoi’s theorem characterizing locally optimal lattices (as proved in [GL, §39]). However, it is more difficult to supply numerical bounds on how large the perturbations can be without letting the density increase. Section 10 of [CK] is devoted to computing such a bound.

In the other direction, it is also more difficult to prove bounds on how close the unknown lattice is to E_{8} or the Leech lattice. Section 7 applies the uniqueness of the association scheme to this problem, in a way that has no analogue in ℝ^{2} because fewer possible angles occur between minimal vectors in Λ_{2} than in the Leech lattice.

5.4. Computer calculations. Completing the proofs in ℝ^{8} and ℝ^{24} requires much sharper estimates than in ℝ^{2}. For example, along the way we prove that no sphere packing in ℝ^{24} can exceed the Leech lattice’s density by a factor of 1 + 1.65 · 10^{−30}. Proving such bounds using these techniques requires applying Poisson summation to much more complicated functions. For example, the analogue in [CK] of the polynomial p_{f} from this paper has degree 803 and rational coefficients with denominator 10^{3000}. Checking the desired properties clearly requires a computer. We have arranged the calculations so as to run in one hour on an ordinary personal computer, and we have made our code available (see Appendix A in [CK]). All of our calculations use exact rational arithmetic and are completely rigorous.

In addition to the difficulty of checking the assertions about f, there is the issue of how to construct this function. We used a computer to search for polynomials with the desired properties, and optimized them using a high-dimensional version of Newton’s method. The whole process took our computers approximately a month, but fortunately one can check the proof simply by verifying the final answer, with no need to reconstruct it from scratch.

6. Future prospects

There is no likelihood that our techniques will work in any dimension except 1, 2, 8, or 24. They depend on using the methods of [CE] to prove nearly sharp upper bounds for the packing density, and that does not seem to happen in any other dimension. It seems counterintuitive that determining the densest lattice in ℝ^{16} appears much more difficult than in ℝ^{8} or ℝ^{24}, but that simply seems to be the case.

One might hope to solve the full sphere packing problem using our techniques. We cannot absolutely rule that out, but we do not consider it feasible. There are at least two substantial obstacles:

(1) It is not known whether E_{8} or the Leech lattice is even locally optimal when the perturbations leave the space of lattices.

(2) In a general sphere packing, different spheres can be tangent to different numbers of other spheres (unlike the case of lattices). Our method of proving lower bounds for the number of nearly minimal vectors can be used to bound the average number of near neighbors of a sphere in a dense packing. However, we cannot rule out the possibility of a small minority of spheres with few neighbors.

We do not know how to deal with the first problem, but perhaps it could be done. The second problem appears quite fundamental, and we suspect that dealing with it would require a major advance in the theory of sphere packing.

Instead, we are convinced that the right way to solve the sphere packing problem in ℝ^{8} and ℝ^{24} is to prove the following conjecture from [CE]. Call a continuous function f : ℝ^{n} → ℝ admissible if there is a constant δ > 0 such that both |f(x)| and |f̂(x)| are bounded above by a constant times (1 + |x|)^{−n−δ}. (Note that the bound on f implies that the integral defining f̂ converges.)

Conjecture 6.1. For (n, r) = (8, \sqrt{2}) or (24, 2), there is an admissible function f : ℝ^{n} → ℝ such that f(0) = f̂(0) = 1, f(x) ≤ 0 for |x| ≥ r, and f̂(t) ≥ 0 for all t.

If Conjecture 6.1 holds, then Theorem 3.2 of [CE] implies that E_{8} and the Leech lattice are the densest sphere packings in ℝ^{8} and ℝ^{24}, respectively. In [CK] we achieve r ≤ 2(1 + 6.851 · 10^{−32}) when n = 24, which is numerical evidence that r = 2 could be achieved.

Acknowledgements

We thank Amanda Beeson and James Bernhard for comments on our paper.

Appendix A. Poisson summation

To make this paper self-contained, we provide here the standard proof of the Poisson summation formula:

Theorem A.1 (Poisson summation). Let f : ℝ^{n} → ℝ be a Schwartz function and Λ ⊂ ℝ^{n} a lattice. Then

∑_{x∈Λ} f(x) = \frac{1}{vol(ℝ^{n}/Λ)} ∑_{t∈Λ^{∗}} f̂(t).

Proof. It is easier to prove a more general formula. Define F : ℝ^{n} → ℝ by

F (z) = ∑_{x∈Λ} f(x + z).

In other words, F is f made periodic modulo Λ, and we wish to compute F (0). Because f is a Schwartz function, the sum defining F converges and defines a C^{∞} function. It follows that we can expand F as a Fourier series, in particular as a linear combination of the exponential functions that are periodic modulo Λ. The function

z ↦ e^{−2πi⟨t,z⟩}

is periodic modulo Λ iff t ∈ Λ^{∗}. Thus,

F (z) = ∑_{t∈Λ^{∗}} c_{t}e^{−2πi⟨t,z⟩}

for some coefficients c_{t}. We can compute c_{t} using orthogonality: if D is a fundamental domain for Λ, then

c_{t} = \frac{1}{vol(D)} ∫_{D} F (z)e^{2πi⟨t,z⟩} dz.

When we substitute vol(D) = vol(ℝ^{n}/Λ) and the definition of F (z) into this equation, we find that

c_{t} = \frac{1}{vol(ℝ^{n}/Λ)} ∑_{x∈Λ} ∫_{D} f(x + z)e^{2πi⟨t,z⟩} dz

= \frac{1}{vol(ℝ^{n}/Λ)} ∑_{x∈Λ} ∫_{D+x} f(z)e^{2πi⟨t,z⟩} dz

= \frac{1}{vol(ℝ^{n}/Λ)} ∫_{ℝ^{n}} f(z)e^{2πi⟨t,z⟩} dz
= \frac{1}{vol(ℝ^{n}/Λ)}f̂(t).

Here D + x = {d + x : d ∈ D}, and these sets tile ℝ^{n} as x ranges over Λ. It follows that

∑_{x∈Λ} f(x + z) = \frac{1}{vol(ℝ^{n}/Λ)} ∑_{t∈Λ^{∗}} f̂(t)e^{−2πi⟨t,z⟩}.

Setting z = 0 yields the desired result. □

References

[Ba] E. S. Barnes, The complete enumeration of extreme senary forms, Phil. Transact. Royal Soc. London A 249 (1957), 461–506. MR 0086833 (19:251d)

[Bl] H. F. Blichfeldt, The minimum values of positive quadratic forms in six, seven and eight variables, Math. Z. 39 (1935), 1–15.

[C] H. Cohn, New upper bounds on sphere packings II , Geom. Topol. 6 (2002), 329–353, arXiv:math.MG/0110010. MR 1914571 (2004b:52032)

[CE] H. Cohn and N. Elkies, New upper bounds on sphere packings I , Annals of Mathematics 157 (2003), 689–714, arXiv:math.MG/0110009. MR 1973059 (2004b:11096)

[CK] H. Cohn and A. Kumar, Optimality and uniqueness of the Leech lattice among lattices,

preprint, 2003, arXiv:math.MG/0403263.

[CS] J. Conway and N. J. A. Sloane, Sphere Packings, Lattices and Groups, third edition, Springer-Verlag, 1999. MR 1662447 (2000b:11077)

[DGS] P. Delsarte, J. Goethals, and J. Seidel, Spherical codes and designs, Geometriae Dedicata 6 (1977), 363–388. MR 0485471 (58:5302)

[E] N. Elkies, Lattices, linear codes, and invariants, Notices Amer. Math. Soc. 47 (2000), 1238–1245 and 1382–1391. MR 1784239 (2001g:11110)

[G] C. F. Gauss, Untersuchungen über die Eigenschaften der positiven ternären quadratischen Formen von Ludwig August Seeber, Göttingische gelehrte Anzeigen, July 9, 1831. Reprinted in Werke, Vol. 2, Königliche Gesellschaft der Wissenschaften, Göttingen, 1863, 188–196. Available from the Göttinger Digitalisierungszentrum at http://gdz.sub.uni-goettingen.

de.

[GL] P. Gruber and C. Lekkerkerker, Geometry of Numbers, second edition, Elsevier Science Publishers, 1987. MR 0893813 (88j:11034)

[KZ1] A. Korkine and G. Zolotareff, Sur les formes quadratiques, Math. Ann. 6 (1873), 366–389.

[KZ2] A. Korkine and G. Zolotareff, Sur les formes quadratiques positives, Math. Ann. 11 (1877), 242–292.

[Lev] V. I. Levenshtein, On bounds for packings in n-dimensional Euclidean space, Soviet Mathematics Doklady 20 (1979), 417–421. MR 0529659 (80d:52017)

[M] J. Martinet, Perfect Lattices in Euclidean Space, Springer-Verlag, 2003. MR 1957723 (2003m:11099)

[OS] A. M. Odlyzko and N. J. A. Sloane, New bounds on the number of unit spheres that can touch a unit sphere in n dimensions, Journal of Combinatorial Theory A 26 (1979), 210– 214. MR 0530296 (81d:52010)

[V] N. M. Vetčinkin, Uniqueness of classes of positive quadratic forms on which values of the Hermite constant are attained for 6 ≤ n ≤ 8, in Geometry of positive quadratic forms, Trudy Math. Inst. Steklov. 152 (1980), 34–86. English translation in Proc. Steklov Inst. Math. 152 (1982), 37–95. MR 0603814 (82f:10040)

Microsoft Research, One Microsoft Way, Redmond, WA 98052-6399

E-mail address: cohn@microsoft.com

Department of Mathematics, Harvard University, Cambridge, MA 02138

E-mail address: abhinav@math.harvard.edu