Magazine Cover
Download article (PDF)

This article is published open access.

MAG121pp. 4–8

Almost impossible E8E_8 and Leech lattices

  • Maryna Viazovska

    École Polytechnique Fédérale de Lausanne, Switzerland

We start this short note by introducing two remarkable mathematical objects: the E8E_{8} root lattice Λ8\Lambda_{8} in 88-dimensional Euclidean space and the Leech lattice Λ24\Lambda_{24} in 2424-dimensional space. These two lattices stand out among their lattice sisters for several reasons.

The first reason is that these both lattices are related to other unique and exceptional mathematical objects. The E8E_{8} lattice is the root lattice of the semisimple exceptional Lie algebra E8E_{8}. The quotient of Λ8\Lambda_{8} by a suitable sublattice is isomorphic to the Hamming binary code of dimension 88 and minimum distance 44, which in its turn is an optimal error-correcting binary code with these parameters. The Leech lattice is famously connected to the exceptional finite simple groups, monstrous moonshine [7] and the monster vertex algebra [1].

Another reason is that Λ8\Lambda_{8} and Λ24\Lambda_{24} are solutions to a number of optimization problems. The E8E_{8} and Leech lattice provide optimal sphere packings in their respective dimensions [23, 5]. Also both lattices are universally optimal, which means that among all point configurations of the same density, the Λ8\Lambda_{8} and Λ24\Lambda_{24} have the smallest possible Gaussian energy [6].

The third reason for our interest in these lattices is less obvious. The optimality of the E8E_{8} and Leech lattices can be proven in a rather short way, while the solutions of analogous problems in other dimensions, even dimensions much smaller than 88 and 2424, is still wide open. Finally, this last property seems to be inherited by other geometric objects obtained from Λ8\Lambda_{8} and Λ24\Lambda_{24}, such as Hamming code, Golay code and the sets of shortest vectors of both lattices.

1 E8E_{8} and Leech lattices

The E8E_{8} lattice Λ8\Lambda_{8} is the unique (up to an isomorphism) even unimodular lattice in the Euclidean space R8\mathbb{R}^{8}. We recall that a lattice ΛRd\Lambda\subset\mathbb{R}^{d} is even if for every lattice vector =(1,,d)\ell=(\ell_{1},\ldots,\ell_{d}) its Euclidean length squared 2=12++d2\lvert\ell\rvert^{2}=\ell_{1}^{2}+\cdots+\ell_{d}^{2} is an even integer. A lattice ΛRd\Lambda\subset\mathbb{R}^{d} is unimodular if the volume of the quotient Rd/Λ\mathbb{R}^{d}/\Lambda is 1. Equivalently, the average number of lattice points per unit of volume is 1.

The existence of an even unimodular lattice in R8\mathbb{R}^{8} was first proven non-constructively by H. J. S. Smith in 1867 and followed from his newly discovered mass formula for lattices. The mass formula for even unimodular lattices in dimension dd divisible by 88 states that

Λ1Aut(Λ)=Bd/2d1j<d/2B2j4j,\sum_{\Lambda}\frac{1}{\lvert\mathrm{Aut}(\Lambda)\rvert}=\frac{\lvert B_{d/2}\rvert}{d}\prod_{1\leq j<d/2}\frac{\lvert B_{2j}\rvert}{4j},

where the left-hand sum is taken over all isomorphism classes of lattices Λ\Lambda, Aut(Λ)\lvert\mathrm{Aut}(\Lambda)\rvert denotes the size of the group of orthogonal transformations acting on Λ\Lambda, and BkB_{k} are the Bernoulli numbers. Note that even unimodular lattices exist only in dimensions divisible by 8. In the smallest possible dimension 8, the right-hand side of the mass formula becomes

B48B24B48B612=1308164130814212=1696729600.\frac{\lvert B_{4}\rvert}{8}\frac{\lvert B_{2}\rvert}{4}\frac{\lvert B_{4}\rvert}{8}\frac{\lvert B_{6}\rvert}{12}=\frac{\bigl|-\frac{1}{30}\bigr|}{8}\frac{\bigl|\frac{1}{6}\bigr|}{4}\frac{\bigl|-\frac{1}{30}\bigr|}{8}\frac{\bigl|\frac{1}{42}\bigr|}{12}=\frac{1}{696729600}.

The mass is non-zero, and therefore there exists at least one even unimodular lattice in dimension 8. Moreover, the formula shows that such a lattice is highly symmetrical. The explicit Gram matrix of the E8E_{8} lattice was first given by Korkin and Zolotarev in 1873 [14 A. Korkine and G. Zolotareff, Sur les formes quadratiques. Math. Ann.6, 366–389 (1873) ].

One remarkable property of the E8E_{8} lattice is that the corresponding sphere packing has very high density. The E8E_{8}-lattice sphere packing PE8\mathcal{P}_{E_{8}} is the union of open Euclidean balls with centers at the lattice points and radius 12\frac{1}{\sqrt{2}}. These non-intersecting congruent balls cover ΔE8π43840.25367\Delta_{E_{8}}\coloneqq\frac{\pi^{4}}{384}\approx 0.25367 of the volume of R8\mathbb{R}^{8}. In 2016 the author showed that this density cannot be improved.

Theorem 1.

No packing of unit balls in Euclidean space R8\mathbb{R}^{8} has density greater than that of the E8E_{8}-lattice packing.

The Leech lattice Λ24\Lambda_{24} was constructed by J. Leech in 1967 [15 J. Leech, Notes on sphere packings. Canadian J. Math.19, 251–267 (1967) ]. This lattice is an even unimodular lattice of rank 24. There exist 24 isomorphism classes of such lattices. Among these 24, the Leech lattice is the unique one having the shortest non-zero vector of length 22 (in the other 23 classes, the shortest vector has minimal possible for even lattices length 2\sqrt{2}). As the minimal distance between two points in Λ24\Lambda_{24} is 22, it is a good candidate for a dense sphere packing. The Λ24\Lambda_{24}-lattice sphere packing is the packing of unit balls with centers at the points of Λ24\Lambda_{24}. This packing has density ΔΛ24π1212!0.00193\Delta_{\Lambda_{24}}\coloneqq\frac{\pi^{12}}{12!}\approx 0.00193. In joint work with H. Cohn, A. Kumar, S. Miller and D. Radchenko, we proved the following.

Theorem 2.

No packing of unit balls in Euclidean space R24\mathbb{R}^{24} has density greater than that of the Λ24\Lambda_{24}-lattice packing.

In the next section, we explain how these results fit into a more general framework.

2 The sphere packing problem

The sphere packing problem asks for the maximal portion of Euclidean space that can be covered with non-overlapping congruent balls. This natural geometric question is interesting from many points of view. The sphere packing problem is a toy model for many physical systems [17 H. Löwen, Fun with hard spheres. In Statistical physics and spatial statistics (Wuppertal, 1999), Lecture Notes in Phys. 554, Springer, Berlin, 295–331 (2000) ] and a mathematical framework for error correcting codes in communication theory [20 C. E. Shannon, A mathematical theory of communication. Bell System Tech. J.27, 379–423, 623–656 (1948) ]. The known and putative solutions of the sphere packing problem are geometrically intriguing configurations, and in many cases possess other extremal properties and unexpected symmetries.

The recorded modern history of the sphere packing problem goes back to the sixteenth century and is documented in the correspondence between a statesman, Sir Walter Raleigh, and a scientist, Thomas Harriot. Harriot was asked by Raleigh to find the most efficient way to stack cannonballs on the deck of the ship. Harriot studied various stacking patterns, computed the number of cannonballs in a triangular pyramid and in a pyramid with square base, and constructed face-centered cubic and hexagonal closed packings. In 1591, he wrote a letter to Raleigh explaining some of these findings. At the beginning of the seventeenth century, Harriot exchanged letters with Johannes Kepler and shared his ideas on sphere packings. In 1611, Kepler wrote an essay “Strena Seu de Nive Sexangula”, in which he described face-centered cubic and hexagonal close packings and asserted that “the packing will be the tightest possible, so that in no other arrangement could more pellets be stuffed into the same container”. This assertion became famously known as Kepler’s conjecture.

The quest to solve Kepler’s conjecture lasted for almost three centuries. We briefly recall the most important landmarks on the way to the solution. In 1863, Carl Friedrich Gauss [12 C. F. Gauss, Recension der “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, 188–196 (1863); available at http://gdz.sub.uni-goettingen.de] showed that the densest lattice packings in R3\mathbb{R}^{3} are the face-centered cubic and hexagonal closed lattices. For a long time, the proof of the conjecture in the general case remained beyond the reach. Even much simpler geometric questions created serious debates, for example the so-called sphere kissing problem. The sphere kissing problem asks for the maximal number of non-intersecting unit balls that can simultaneously touch one unit ball. This question can be seen as a weak local version of the sphere packing problem. The kissing number in dimension 3 is 12. Another important step was the rigorous solution of the packing problem for unit disks in dimension 2 [21 A. Thue, Über die dichteste Zusammenstellung von kongruenten Kreisen in einer Ebene, Norske Vid. Selsk. Skr.1, 1–9 (1910) , 11 L. Fejes, Über die dichteste Kugellagerung. Math. Z.48, 676–684 (1942) ]. The final solution of Kepler’s conjecture was famously given by Thomas Hales [13 T. C. Hales, A proof of the Kepler conjecture. Ann. of Math. (2)162, 1065–1185 (2005) ].

The sphere packing problem and the sphere kissing problem are easily generalized to Euclidean spaces of other dimensions. At the moment the sphere packing problem has been completely solved in dimensions 1, 2, 3, 8 and 24. Conjectural solutions to the sphere packing problem in dimensions from 4 to 10 are listed in [8 J. H. Conway and N. J. A. Sloane, What are all the best sphere packings in low dimensions? Discrete Comput. Geom.13, 383–403 (1995) ]. Analogs of the packing problem can be formulated in other metric spaces. A subset XX of a metric space (M,ρ)(\mathcal{M},\rho) is called an r0r_{0}-code if the distance between any two distinct points of XX is greater than or equal to r0r_{0}. One interesting example of a metric space is the Hamming space. The binary Hamming space of dimension dd is the vector space F2d\mathbb{F}_{2}^{d} over the finite field F2\mathbb{F}_{2} equipped with the following metric: the distance between the vectors x=(x1,,xd)x=(x_{1},\ldots,x_{d}) and y=(y1,,yd)y=(y_{1},\ldots,y_{d}) is the number of indices ii between 11 and dd such that xiyix_{i}\neq\nobreak y_{i}. A subset XF2dX\subset\mathbb{F}_{2}^{d} is a code of length dd, dimension nn and distance rr if XX is a vector subspace over F2\mathbb{F}_{2} of dimension nn and an rr-code with respect to Hamming distance. Then we say that XX is a (d,n,r)(d,n,r) code. Codes in Hamming spaces are particularly interesting for us because of their connection to the lattices in Euclidean spaces. There are several ways to produce a Euclidean lattice from a code in Hamming space; some of them are described in [9 J. H. Conway and N. J. A. Sloane, Sphere packings, lattices and groups. 3rd ed., Grundlehren Math. Wiss. 290, Springer, New York (1999) , Chapter 5]. For example, the E8E_{8} lattice can be constructed from the binary Hamming code (8,4,4)(8,4,4) by applying the so-called “construction A”, and the Leech lattice can be obtained in a more complicated way from the binary Golay code (24,12,8)(24,12,8).

3 Energy minimization

A natural generalization of the sphere packing problem is the question of minimizing the energy of pairwise interactions between points. In this case, we consider configurations with a fixed number of points on a compact metric space, or configurations with fixed point density in the non-compact case.

Let CfC_{f} be a finite subset in Rd\mathbb{R}^{d}. Fix a potential function

p ⁣:(0,)R.p\colon(0,\infty)\to\mathbb{R}.

The potential pp-energy of CfC_{f} is

1Cfx,yCfxyp(xy).\frac{1}{\lvert C_{f}\rvert}\sum_{\begin{subarray}{c}x,y\in C_{f}\\ x\neq y\end{subarray}}p(\lvert x-y\rvert).

We would like to extend this definition to infinite discrete subsets of Euclidean space.

Let CC be a discrete closed subset of Rd\mathbb{R}^{d}. We say CC has density ρ\rho if

limrCBd(0,r)vol(Bd(0,r))=ρ.\lim_{r\to\infty}\smash{\frac{\lvert C\cap B_{d}(0,r)\rvert}{\mathrm{vol}(B_{d}(0,r))}}=\rho.

The lower pp-energy of CC is

Ep(C)lim infr1CBd(0,r)x,yCBd(0,r)xyp(xy).E_{p}(C)\coloneqq\liminf_{r\to\infty}\frac{1}{\lvert C\cap B_{d}(0,r)\rvert}\sum_{\begin{subarray}{c}x,y\in C\cap B_{d}(0,r)\\ x\neq y\end{subarray}}p(\lvert x-y\rvert).

If the limit exists, we call Ep(C)E_{p}(C) the pp-energy of CC.

4 Universal optimality

We rephrase a famous saying: “An optimal configuration is optimal everywhere”. Is it possible that one configuration is optimal for all potentials? The answer is obviously no; however, some configurations provide an optimal solution for a wide family of potential functions pp.

One important family of potentials in Euclidean space are Gaussian functions pα(r)=eαr2p_{\alpha}(r)=e^{-\alpha r^{2}}, where α\alpha is a positive real number. The convex cone spanned by all real Gaussians is the cone of completely monotonic functions of squared distance. In [3 H. Cohn and A. Kumar, Universally optimal distribution of points on spheres. J. Amer. Math. Soc.20, 99–148 (2007) ], H. Cohn and A. Kumar introduced the following definition.

Definition 3. Let CC be a discrete subset of Rd\mathbb{R}^{d} with density ρ\rho, where ρ>0\rho>0. We say that CC is universally optimal if it minimizes pp-energy whenever p ⁣:(0,)Rp\colon(0,\infty)\to\mathbb{R} is a completely monotonic function of squared distance.

The following result was established in [22 W. J. Ventevogel and B. R. A. Nijboer, On the configuration of systems of interacting particle with minimum potential energy per particle. Physica98A, 274–288 (1979) ] back in 1979.

Theorem 4.

The lattice Z\mathbb{Z} is universally optimal.

This result is also proven in [3 H. Cohn and A. Kumar, Universally optimal distribution of points on spheres. J. Amer. Math. Soc.20, 99–148 (2007) ] with the help of linear programming, the proof technique which will be explained in the next section. Moreover, in the same paper, Cohn and Kumar made the following conjecture.

Conjecture 5. The lattices A2,Λ8A_{2},\Lambda_{8} and Λ24\Lambda_{24} are universally optimal.

In joint work with H. Cohn, A. Kumar, S. Miller and D. Radchenko [6 H. Cohn, A. Kumar, S. D. Miller, D. Radchenko and M. S. Viazovska, Universal optimality of the E8 and Leech lattices and interpolation formulas, preprint, arXiv:1902.05438 (2019) ], we have proved the following.

Theorem 6.

The lattices Λ8\Lambda_{8} and Λ24\Lambda_{24} are universally optimal.

Not much is known about universally optimal configurations in Euclidean space, and in particular whether the lattices in Theorem 4 and Conjecture 5 give the complete list of all universally optimal lattices. In [4 H. Cohn, A. Kumar, A. Schürmann, Ground states and formal duality relations in the Gaussian core model, Phys. Rev. E80, 061116 (2009) ], the authors provide numerical evidence that the root lattice D4D_{4} and the configuration D9+D_{9}^{+} (the definition of this configuration is given in [4 H. Cohn, A. Kumar, A. Schürmann, Ground states and formal duality relations in the Gaussian core model, Phys. Rev. E80, 061116 (2009) ]) might be universally optimal.

5 Magic functions for geometric optimization problems

In this section, we will talk about the proof techniques used in Theorems 1, 2 and 6. Curiously, similar methods were used to prove the optimality of the binary Hamming code (8,4,4)(8,4,4), the binary Golay code (24,12,8)(24,12,8), and the optimality of the shortest vectors of the E8E_{8} and Leech lattices as kissing configurations in their respective dimensions. This method is often referred to as linear programming. The key idea is to reduce a geometric optimization problem on a space M\mathcal{M} to minimizing a linear functional on a certain suitably constructed cone of functions on M\mathcal{M}.

For packing and energy minimization problems, the following two cones of functions play an important role. Let (M,ρ)(\mathcal{M},\rho) be a metric space. We denote by Spec(ρ)\mathrm{Spec}(\rho) the set of values taken by ρ ⁣:M×MR0\rho\colon\mathcal{M}\times\mathcal{M}\to\mathbb{R}_{\geq 0}. A function f ⁣:Spec(ρ)Cf\colon\mathrm{Spec}(\rho)\to\mathbb{C} is copositive if for all finite subsets XMX\subset\mathcal{M} we have

x,yXf(ρ(x,y))0.\sum_{x,y\in X}f(\rho(x,y))\geq 0.

A function f ⁣:Spec(ρ)Cf\colon\mathrm{Spec}(\rho)\to\mathbb{C} is positive definite if for all finite subsets XMX\subset\mathcal{M} and all complex weights (wx)xX(w_{x})_{x\in X} we have

x,yXwxwyf(ρ(x,y))0.\sum_{x,y\in X}w_{x}\overline{w}_{y}\,f(\rho(x,y))\geq 0.

The cone of copositive functions is extremely powerful, and the possibility of effectively optimizing over it would lead to solutions of many geometric questions. Unfortunately, this cone is very complex and to our knowledge there is no easy way to work with it directly. However, the cone of copositive functions contains a much simpler one, namely the cone of positive definite functions. This cone has a simple description in terms of harmonic analysis on M\mathcal{M}. We refer the reader to [9 J. H. Conway and N. J. A. Sloane, Sphere packings, lattices and groups. 3rd ed., Grundlehren Math. Wiss. 290, Springer, New York (1999) , Chapter 9] for details.

The following theorem is a simple yet powerful tool for bounding the size of codes in compact metric spaces.

Theorem 7.

Let (M,ρ)(\mathcal{M},\rho) be a metric space. Suppose that

f ⁣:Spec(ρ)Rf\colon\mathrm{Spec}(\rho)\to\mathbb{R}

is a copositive function such that

f(0)=1,\displaystyle f(0)=1,
f(r)1N1for rr0.\displaystyle f(r)\leq-\smash[t]{\frac{1}{N-1}}\quad\text{for}\ r\geq r_{0}.

Then an r0r_{0} code in M\mathcal{M} contains at most NN points.

Proof. The proof of this theorem is very simple. Suppose that XMX\subset\mathcal{M} is an r0r_{0} code. Then the copositivity of ff implies

x,yXf(ρ(x,y))0.\sum_{x,y\in X}f(\rho(x,y))\geq 0.

On the other hand, by conditions (1) and (2), we estimate

x,yXf(ρ(x,y))=xXf(ρ(x,x))+x,yXxyf(ρ(x,y))XX(X1)N1.\begin{split}\sum_{x,y\in X}f(\rho(x,y))&=\sum_{x\in X}f(\rho(x,x))+\sum_{\begin{subarray}{c}x,y\in X\\ x\neq y\end{subarray}}f(\rho(x,y))\\ &\leq\lvert X\rvert-\frac{\lvert X\rvert(\lvert X\rvert-1)}{N-1}.\end{split}

The two equations above imply that XN\lvert X\rvert\leq N.

We are interested in the examples when the upper bound provided by Theorem 7 is sharp, in particular, the cases when the auxiliary function ff is positive definite. We have already mentioned several configurations which are “LP-sharp”. For instance, the optimality of the Hamming binary code (8,4,4)(8,4,4) follows from the fact that the polynomial

pH8(t)130(t4)(t8)115p_{H_{8}}(t)\coloneqq\frac{1}{30}(t-4)(t-8)-\frac{1}{15}

is positive definite with respect to Hamming distance on F28\mathbb{F}_{2}^{8} , see [10 P. Delsarte, Bounds for unrestricted codes, by linear programming. Philips Res. Rep.27, 272–289 (1972) ] and [9 J. H. Conway and N. J. A. Sloane, Sphere packings, lattices and groups. 3rd ed., Grundlehren Math. Wiss. 290, Springer, New York (1999) , Chapter 9]. A positive definite auxiliary function proving the optimality of the binary Golay code (24,12,8)(24,12,8) is also given in [9 J. H. Conway and N. J. A. Sloane, Sphere packings, lattices and groups. 3rd ed., Grundlehren Math. Wiss. 290, Springer, New York (1999) , Chapter 9]. The 240 shortest vectors of the E8E_{8}-lattice and the 196 560 shortest vectors of the Leech lattice are the optimal kissing configurations in their respective dimensions. In 1979, Odlyzko and Sloane [18 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. J. Combin. Theory Ser. A26, 210–214 (1979) ] and V. Levenstein [16 V. I. Levenshtein, Boundaries for packings in n-dimensional Euclidean space. Dokl. Akad. Nauk SSSR245, 1299–1303 (1979) ] independently constructed positive definite polynomials on the sphere proving the optimality. A survey of these results and the polynomials can be found in [9 J. H. Conway and N. J. A. Sloane, Sphere packings, lattices and groups. 3rd ed., Grundlehren Math. Wiss. 290, Springer, New York (1999) , Chapter 9] and in [19 F. Pfender and G. M. Ziegler, Kissing numbers, sphere packings, and some unexpected proofs. Notices Amer. Math. Soc.51, 873–883 (2004) ]. Moreover, by similar techniques, Cohn and Kumar showed that the shortest vectors of E8E_{8} and Leech lattices are universally optimal configurations on the sphere [3 H. Cohn and A. Kumar, Universally optimal distribution of points on spheres. J. Amer. Math. Soc.20, 99–148 (2007) ].

H. Cohn and N. Elkies [2 H. Cohn and N. Elkies, New upper bounds on sphere packings. I. Ann. of Math. (2)157, 689–714 (2003) ] applied the ideas of linear programming to the sphere packing problem in Euclidean space. Before we explain their method, let us introduce some notation. The Fourier transform of an L1L^{1} function f ⁣:RdCf\colon\mathbb{R}^{d}\to\mathbb{C} is defined as

F(f)(y)=f^(y)Rdf(x)e2πixydx,yRd,\mathcal{F}(f)(y)=\hat{f}(y)\coloneqq\int_{\mathbb{R}^{d}}f(x)\,e^{-2\pi ix\cdot y}\,dx,\quad y\in\mathbb{R}^{d},

where xy=12x2+12y212xy2x\cdot y=\frac{1}{2}\lvert x\rvert^{2}+\frac{1}{2}\lvert y\rvert^{2}-\frac{1}{2}\lvert x-y\rvert^{2} is the standard scalar product in Rd\mathbb{R}^{d}. A CC^{\infty} function f ⁣:RdCf\colon\mathbb{R}^{d}\to\mathbb{C} is called a Schwartz function if it tends to zero as x\lvert x\rvert\to\infty faster than any inverse power of x\lvert x\rvert, and the same holds for all partial derivatives of ff. The following theorem is the key result of [2 H. Cohn and N. Elkies, New upper bounds on sphere packings. I. Ann. of Math. (2)157, 689–714 (2003) ].

Theorem 8.

Suppose that f ⁣:RdRf\colon\mathbb{R}^{d}\to\mathbb{R} is a Schwartz function, r0R>0r_{0}\in\nobreak\mathbb{R}_{>0}, and they satisfy

f(x)0\displaystyle f(x)\leq 0
for xr0,\displaystyle\text{for}\ \lvert x\rvert\geq r_{0},
f^(x)0\displaystyle\hat{f}(x)\geq 0
for all xRd,\displaystyle\text{for all}\ x\in\mathbb{R}^{d},
f(0)=f^(0)=1.\displaystyle f(0)=\hat{f}(0)=1.

Then the density of dd-dimensional sphere packings is bounded above by

πd2r0d2dΓ(d2+1).\frac{\smash[t]{\pi^{\frac{d}{2}}r_{0}^{d}}}{2^{d}\Gamma(\frac{d}{2}+1)}.

Note that this number is the volume of a ball of radius r02\frac{r_{0}}{2} in Rd\mathbb{R}^{d}.

This theorem produces an upper bound for the density of a sphere packing in every dimension. However, this bound is not expected to be sharp in general. A surprising discovery made by Cohn and Elkies was that they were able to obtain bounds numerically extremely close to the sharp ones in dimensions 1, 2, 8 and 24. In [23 M. S. Viazovska, The sphere packing problem in dimension 8. Ann. of Math. (2)185, 991–1015 (2017) ], the author showed that the linear programming bound is indeed sharp in dimension 8.

Theorem 9.

There exists a radial Schwartz function fE8 ⁣:R8Rf_{E_{8}}\colon\mathbb{R}^{8}\to\mathbb{R} which satisfies

fE8(x)0\displaystyle f_{E_{8}}(x)\leq 0
for x2,\displaystyle\text{for}\ \lvert x\rvert\geq\sqrt{2},
f^E8(x)0\displaystyle\hat{f}_{E_{8}}(x)\geq 0
for all xR8,\displaystyle\text{for all}\ x\in\mathbb{R}^{8},
fE8(0)=f^E8(0)=1.\displaystyle f_{E_{8}}(0)=\hat{f}_{E_{8}}(0)=1.

Furthermore, in joint work with H. Cohn, A. Kumar, S. D. Miller and D. Radchenko [5 H. Cohn, A. Kumar, S. D. Miller, D. Radchenko and M. Viazovska, The sphere packing problem in dimension 24. Ann. of Math. (2)185, 1017–1033 (2017) ], we proved the sharpness of the linear programming bound in dimension 24.

Theorem 10.

There exists a radial Schwartz function fΛ24 ⁣:R24 ⁣ ⁣Rf_{\Lambda_{24}}\colon\mathbb{R}^{24}\mkern-1.0mu \to\mkern-1.0mu \nobreak\mathbb{R} which satisfies

fΛ24(x)0\displaystyle f_{\Lambda_{24}}(x)\leq 0
for x2,\displaystyle\text{for}\ \lvert x\rvert\geq 2,
f^Λ24(x)0\displaystyle\hat{f}_{\Lambda_{24}}(x)\geq 0
for all xR24,\displaystyle\text{for all}\ x\in\mathbb{R}^{24},
fΛ24(0)=f^Λ24(0)=1.\displaystyle f_{\Lambda_{24}}(0)=\hat{f}_{\Lambda_{24}}(0)=1.

The energy minimization problem also can be addressed by linear programming. The following bound was introduced by H. Cohn and A. Kumar.

Theorem 11.

Let p ⁣:(0,)Rp\colon(0,\infty)\to\mathbb{R} be any function, and suppose f ⁣:RdRf\colon\mathbb{R}^{d}\to\mathbb{R} is a Schwartz function. If f(x)p(x)f(x)\leq p(\lvert x\rvert) for all xRd{0}x\in\mathbb{R}^{d}\setminus\{0\} and f^(y)0\hat{f}(y)\geq 0 for all yRdy\in\mathbb{R}^{d}, then every subset of Rd\mathbb{R}^{d} with density ρ\rho has lower pp-energy at least ρf^(0)f(0)\rho\hat{f}(0)-f(0).

In [5 H. Cohn, A. Kumar, S. D. Miller, D. Radchenko and M. Viazovska, The sphere packing problem in dimension 24. Ann. of Math. (2)185, 1017–1033 (2017) ], we construct functions fΛd,αf_{\Lambda_{d},\alpha} for all d8,24d\in{8,24} and real positive α\alpha such that fΛd,α(x)eαx2f_{\Lambda_{d},\alpha}(x)\leq e^{-\alpha\lvert x\rvert^{2}} for all xRd{0}x\in\mathbb{R}^{d}\setminus\{0\} and f^(y)0\hat{f}(y)\geq 0 for all yRdy\in\mathbb{R}^{d}, and also ρf^Λd,α(0)fΛd,α(0)=Ereαr2(Λd)\rho\hat{f}_{\Lambda_{d},\alpha}(0)-f_{\Lambda_{d},\alpha}(0)=E_{r\mapsto e^{-\alpha r^{2}}}(\Lambda_{d}). The construction of these functions implies Theorem 6. Informally, we call the auxiliary functions fE8f_{E_{8}}, fΛ24f_{\Lambda_{24}}, fΛd,αf_{\Lambda_{d},\alpha} the “magic functions” as they magically prove difficult geometric statements.

6 Fourier interpolation and sharp bounds

In this final section, we briefly explain the strategy for finding magic functions. Let us first consider the case of compact spaces. Suppose that XMX\subset\mathcal{M} is an optimal r0r_{0} code in the metric space (M,ρ)(\mathcal{M},\rho), and a copositive function f ⁣:Spec(M)Rf\colon\mathrm{Spec}(M)\to\mathbb{R} satisfies the conditions of Theorem 7 for N=XN=\lvert X\rvert; in other words, ff proves the sharp bound on the size of r0r_{0}-codes. In this case, inequalities (3) and (4) imply that f(ρ(x,y))=1N1f(\rho(x,y))=\frac{-1}{N-1} for all pairs of distinct points x,yXx,y\in X and x,yXf(ρ(x,y))=0\sum_{x,y\in X}f(\rho(x,y))=0. Moreover, if we represent ff as a sum of copositive functions f=f1++fkf=f_{1}+\cdots+f_{k}, then x,yXfi(ρ(x,y))=0\sum_{x,y\in X}f_{i}(\rho(x,y))=0 for i=1,,ki=1,\ldots,k. In many cases, these linear conditions are sufficient to find the function ff.

Similar ideas work in the case of Euclidean space and can be applied to magic functions for the Cohn–Elkies bound of Theorem 8 and the Cohn–Kumar bound of Theorem 11. Suppose that ΛdRd\Lambda_{d}\subset\mathbb{R}^{d} is a unimodular lattice and fΛdf_{\Lambda_{d}} is a magic function satisfying the conditions of Theorem 8 and thus proving the optimality of the Λd\Lambda_{d} lattice sphere packing. Without loss of generality, we may assume that fΛdf_{\Lambda_{d}} is radial and the value fΛd(x)f_{\Lambda_{d}}(x) depends only on the Euclidean length x\lvert x\rvert. Combining the Poisson summation formula

xΛdfΛd(x)=yΛdf^Λd(y)\sum_{x\in\Lambda_{d}}f_{\Lambda_{d}}(x)=\sum_{y\in\Lambda_{d}^{*}}\hat{f}_{\Lambda_{d}}(y)

with conditions (5)–(7) of Theorem 8, we deduce that fΛd(x)=0f_{\Lambda_{d}}(x)=0 for all xΛd{0}x\in\Lambda_{d}\setminus\{0\} and f^Λd(y)=0\hat{f}_{\Lambda_{d}}(y)=0 for all yΛd{0}y\in\Lambda_{d}^{*}\setminus\{0\} (here Λd\Lambda_{d}^{*} is the lattice dual to Λd\Lambda_{d}). Moreover, since fΛdf_{\Lambda_{d}} is smooth, these equalities hold up to second order.

It turns out that we can recover the whole function fΛdf_{\Lambda_{d}} from this information on its values at lattice points. In [6 H. Cohn, A. Kumar, S. D. Miller, D. Radchenko and M. S. Viazovska, Universal optimality of the E8 and Leech lattices and interpolation formulas, preprint, arXiv:1902.05438 (2019) ], we proved the following Fourier interpolation formula.

Theorem 12.

Let (d,n0)(d,n_{0}) be (8,1)(8,1) or (24,2)(24,2). There exists a collection of radial Schwartz functions an,bn,a~n,b~n ⁣:RdRa_{n},b_{n},\tilde{a}_{n},\tilde{b}_{n}\colon\mathbb{R}^{d}\to\mathbb{R} such that for every fSrad(Rd)f\in\mathcal{S}_{\textup{rad}}(\mathbb{R}^{d}) and xRdx\in\mathbb{R}^{d},

f(x)=n=n0f(2n)an(x)+n=n0f(2n)bn(x)+n=n0f^(2n)a~n(x)+n=n0f^(2n)b~n(x),\begin{split}f(x)&=\sum_{n=n_{0}}^{\infty}f(\sqrt{2n})a_{n}(x)+\sum_{n=n_{0}}^{\infty}f^{\prime}(\sqrt{2n})b_{n}(x)\\[-1.5pt] &\qquad+\sum_{n=n_{0}}^{\infty}\hat{f}(\sqrt{2n})\tilde{a}_{n}(x)+\sum_{n=n_{0}}^{\infty}\hat{f}^{\prime}(\sqrt{2n})\tilde{b}_{n}(x),\end{split}

and these series converge absolutely.

The above interpolation formula allowed us to find magic functions fE8f_{E_{8}}, fΛ24f_{\Lambda_{24}}, fE8,αf_{E_{8},\alpha} and fΛ24,αf_{\Lambda_{24},\alpha} as explicit contour integrals, and based on these integral representations prove the inequalities posed on these functions by Theorems 8 and 11, respectively.

Finally, the Fourier interpolation formulas of this type seem to be very intriguing objects in their own right, and it would be worth searching for more such examples and more geometric applications.

Maryna Viazovska is a full professor at the École Polytechnique Fédérale de Lausanne. In 2016, she solved the sphere-packing problem in dimension 8 and, in collaboration with others, in dimension 24. She was an EMS Prize winner in 2020. viazovska@gmail.com

    References

    1. R. E. Borcherds, Monstrous moonshine and monstrous Lie superalgebras. Invent. Math.109, 405–444 (1992)
    2. H. Cohn and N. Elkies, New upper bounds on sphere packings. I. Ann. of Math. (2)157, 689–714 (2003)
    3. H. Cohn and A. Kumar, Universally optimal distribution of points on spheres. J. Amer. Math. Soc.20, 99–148 (2007)
    4. H. Cohn, A. Kumar, A. Schürmann, Ground states and formal duality relations in the Gaussian core model, Phys. Rev. E80, 061116 (2009)
    5. H. Cohn, A. Kumar, S. D. Miller, D. Radchenko and M. Viazovska, The sphere packing problem in dimension 24. Ann. of Math. (2)185, 1017–1033 (2017)
    6. H. Cohn, A. Kumar, S. D. Miller, D. Radchenko and M. S. Viazovska, Universal optimality of the E8 and Leech lattices and interpolation formulas, preprint, arXiv:1902.05438 (2019)
    7. J. H. Conway and S. P. Norton, Monstrous moonshine. Bull. London Math. Soc.11, 308–339 (1979)
    8. J. H. Conway and N. J. A. Sloane, What are all the best sphere packings in low dimensions? Discrete Comput. Geom.13, 383–403 (1995)
    9. J. H. Conway and N. J. A. Sloane, Sphere packings, lattices and groups. 3rd ed., Grundlehren Math. Wiss. 290, Springer, New York (1999)
    10. P. Delsarte, Bounds for unrestricted codes, by linear programming. Philips Res. Rep.27, 272–289 (1972)
    11. L. Fejes, Über die dichteste Kugellagerung. Math. Z.48, 676–684 (1942)
    12. C. F. Gauss, Recension der “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, 188–196 (1863); available at http://gdz.sub.uni-goettingen.de
    13. T. C. Hales, A proof of the Kepler conjecture. Ann. of Math. (2)162, 1065–1185 (2005)
    14. A. Korkine and G. Zolotareff, Sur les formes quadratiques. Math. Ann.6, 366–389 (1873)
    15. J. Leech, Notes on sphere packings. Canadian J. Math.19, 251–267 (1967)
    16. V. I. Levenshtein, Boundaries for packings in n-dimensional Euclidean space. Dokl. Akad. Nauk SSSR245, 1299–1303 (1979)
    17. H. Löwen, Fun with hard spheres. In Statistical physics and spatial statistics (Wuppertal, 1999), Lecture Notes in Phys. 554, Springer, Berlin, 295–331 (2000)
    18. 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. J. Combin. Theory Ser. A26, 210–214 (1979)
    19. F. Pfender and G. M. Ziegler, Kissing numbers, sphere packings, and some unexpected proofs. Notices Amer. Math. Soc.51, 873–883 (2004)
    20. C. E. Shannon, A mathematical theory of communication. Bell System Tech. J.27, 379–423, 623–656 (1948)
    21. A. Thue, Über die dichteste Zusammenstellung von kongruenten Kreisen in einer Ebene, Norske Vid. Selsk. Skr.1, 1–9 (1910)
    22. W. J. Ventevogel and B. R. A. Nijboer, On the configuration of systems of interacting particle with minimum potential energy per particle. Physica98A, 274–288 (1979)
    23. M. S. Viazovska, The sphere packing problem in dimension 8. Ann. of Math. (2)185, 991–1015 (2017)

    Cite this article

    Maryna Viazovska, Almost impossible E8E_8 and Leech lattices. Eur. Math. Soc. Mag. 121 (2021), pp. 4–8

    DOI 10.4171/MAG/47
    🅭🅯
    This open access article is published by EMS Press under a CC BY 4.0 license, with the exception of logos and branding of the European Mathematical Society and EMS Press, and where otherwise noted.
    Back to Issue 121