Download article (PDF)
This article is published open access.
We start this short note by introducing two remarkable mathematical objects: the root lattice in -dimensional Euclidean space and the Leech lattice in -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 lattice is the root lattice of the semisimple exceptional Lie algebra . The quotient of by a suitable sublattice is isomorphic to the Hamming binary code of dimension and minimum distance , 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  and the monster vertex algebra .
Another reason is that and are solutions to a number of optimization problems. The 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 and have the smallest possible Gaussian energy .
The third reason for our interest in these lattices is less obvious. The optimality of the 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 and , is still wide open. Finally, this last property seems to be inherited by other geometric objects obtained from and , such as Hamming code, Golay code and the sets of shortest vectors of both lattices.
1 and Leech lattices
The lattice is the unique (up to an isomorphism) even unimodular lattice in the Euclidean space . We recall that a lattice is even if for every lattice vector its Euclidean length squared is an even integer. A lattice is unimodular if the volume of the quotient is 1. Equivalently, the average number of lattice points per unit of volume is 1.
The existence of an even unimodular lattice in 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 divisible by states that
where the left-hand sum is taken over all isomorphism classes of lattices , denotes the size of the group of orthogonal transformations acting on , and 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
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 lattice was first given by Korkin and Zolotarev in 1873 .
One remarkable property of the lattice is that the corresponding sphere packing has very high density. The -lattice sphere packing is the union of open Euclidean balls with centers at the lattice points and radius . These non-intersecting congruent balls cover of the volume of . In 2016 the author showed that this density cannot be improved.
No packing of unit balls in Euclidean space has density greater than that of the -lattice packing.
The Leech lattice was constructed by J. Leech in 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 (in the other 23 classes, the shortest vector has minimal possible for even lattices length ). As the minimal distance between two points in is , it is a good candidate for a dense sphere packing. The -lattice sphere packing is the packing of unit balls with centers at the points of . This packing has density . In joint work with H. Cohn, A. Kumar, S. Miller and D. Radchenko, we proved the following.
No packing of unit balls in Euclidean space has density greater than that of the -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  and a mathematical framework for error correcting codes in communication theory . 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  showed that the densest lattice packings in 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, 11]. The final solution of Kepler’s conjecture was famously given by Thomas Hales .
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 . Analogs of the packing problem can be formulated in other metric spaces. A subset of a metric space is called an -code if the distance between any two distinct points of is greater than or equal to . One interesting example of a metric space is the Hamming space. The binary Hamming space of dimension is the vector space over the finite field equipped with the following metric: the distance between the vectors and is the number of indices between and such that . A subset is a code of length , dimension and distance if is a vector subspace over of dimension and an -code with respect to Hamming distance. Then we say that is a 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, Chapter 5]. For example, the lattice can be constructed from the binary Hamming code by applying the so-called “construction A”, and the Leech lattice can be obtained in a more complicated way from the binary Golay code .
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 be a finite subset in . Fix a potential function
The potential -energy of is
We would like to extend this definition to infinite discrete subsets of Euclidean space.
Let be a discrete closed subset of . We say has density if
The lower -energy of is
If the limit exists, we call the -energy of .
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 .
One important family of potentials in Euclidean space are Gaussian functions , where is a positive real number. The convex cone spanned by all real Gaussians is the cone of completely monotonic functions of squared distance. In , H. Cohn and A. Kumar introduced the following definition.
Definition 3. Let be a discrete subset of with density , where . We say that is universally optimal if it minimizes -energy whenever is a completely monotonic function of squared distance.
The following result was established in  back in 1979.
The lattice is universally optimal.
This result is also proven in  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 and are universally optimal.
In joint work with H. Cohn, A. Kumar, S. Miller and D. Radchenko , we have proved the following.
The lattices and 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 , the authors provide numerical evidence that the root lattice and the configuration (the definition of this configuration is given in ) 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 , the binary Golay code , and the optimality of the shortest vectors of the 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 to minimizing a linear functional on a certain suitably constructed cone of functions on .
For packing and energy minimization problems, the following two cones of functions play an important role. Let be a metric space. We denote by the set of values taken by . A function is copositive if for all finite subsets we have
A function is positive definite if for all finite subsets and all complex weights we have
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 . We refer the reader to [9, Chapter 9] for details.
The following theorem is a simple yet powerful tool for bounding the size of codes in compact metric spaces.
Let be a metric space. Suppose that
is a copositive function such that
Then an code in contains at most points.
Proof. The proof of this theorem is very simple. Suppose that is an code. Then the copositivity of implies
The two equations above imply that . ∎
We are interested in the examples when the upper bound provided by Theorem 7 is sharp, in particular, the cases when the auxiliary function is positive definite. We have already mentioned several configurations which are “LP-sharp”. For instance, the optimality of the Hamming binary code follows from the fact that the polynomial
is positive definite with respect to Hamming distance on , see  and [9, Chapter 9]. A positive definite auxiliary function proving the optimality of the binary Golay code is also given in [9, Chapter 9]. The 240 shortest vectors of the -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  and V. Levenstein  independently constructed positive definite polynomials on the sphere proving the optimality. A survey of these results and the polynomials can be found in [9, Chapter 9] and in . Moreover, by similar techniques, Cohn and Kumar showed that the shortest vectors of and Leech lattices are universally optimal configurations on the sphere .
H. Cohn and N. Elkies  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 function is defined as
where is the standard scalar product in . A function is called a Schwartz function if it tends to zero as faster than any inverse power of , and the same holds for all partial derivatives of . The following theorem is the key result of .
Suppose that is a Schwartz function, , and they satisfy
Then the density of -dimensional sphere packings is bounded above by
Note that this number is the volume of a ball of radius in .
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 , the author showed that the linear programming bound is indeed sharp in dimension 8.
There exists a radial Schwartz function which satisfies
Furthermore, in joint work with H. Cohn, A. Kumar, S. D. Miller and D. Radchenko , we proved the sharpness of the linear programming bound in dimension 24.
There exists a radial Schwartz function which satisfies
The energy minimization problem also can be addressed by linear programming. The following bound was introduced by H. Cohn and A. Kumar.
Let be any function, and suppose is a Schwartz function. If for all and for all , then every subset of with density has lower -energy at least .
In , we construct functions for all and real positive such that for all and for all , and also . The construction of these functions implies Theorem 6. Informally, we call the auxiliary functions , , 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 is an optimal code in the metric space , and a copositive function satisfies the conditions of Theorem 7 for ; in other words, proves the sharp bound on the size of -codes. In this case, inequalities (3) and (4) imply that for all pairs of distinct points and . Moreover, if we represent as a sum of copositive functions , then for . In many cases, these linear conditions are sufficient to find the function .
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 is a unimodular lattice and is a magic function satisfying the conditions of Theorem 8 and thus proving the optimality of the lattice sphere packing. Without loss of generality, we may assume that is radial and the value depends only on the Euclidean length . Combining the Poisson summation formula
It turns out that we can recover the whole function from this information on its values at lattice points. In , we proved the following Fourier interpolation formula.
Let be or . There exists a collection of radial Schwartz functions such that for every and ,
and these series converge absolutely.
The above interpolation formula allowed us to find magic functions , , and 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. email@example.com
- R. E. Borcherds, Monstrous moonshine and monstrous Lie superalgebras. Invent. Math.109, 405–444 (1992)
- H. Cohn and N. Elkies, New upper bounds on sphere packings. I. Ann. of Math. (2)157, 689–714 (2003)
- H. Cohn and A. Kumar, Universally optimal distribution of points on spheres. J. Amer. Math. Soc.20, 99–148 (2007)
- H. Cohn, A. Kumar, A. Schürmann, Ground states and formal duality relations in the Gaussian core model, Phys. Rev. E80, 061116 (2009)
- 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)
- 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)
- J. H. Conway and S. P. Norton, Monstrous moonshine. Bull. London Math. Soc.11, 308–339 (1979)
- 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)
- J. H. Conway and N. J. A. Sloane, Sphere packings, lattices and groups. 3rd ed., Grundlehren Math. Wiss. 290, Springer, New York (1999)
- P. Delsarte, Bounds for unrestricted codes, by linear programming. Philips Res. Rep.27, 272–289 (1972)
- L. Fejes, Über die dichteste Kugellagerung. Math. Z.48, 676–684 (1942)
- 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
- T. C. Hales, A proof of the Kepler conjecture. Ann. of Math. (2)162, 1065–1185 (2005)
- A. Korkine and G. Zolotareff, Sur les formes quadratiques. Math. Ann.6, 366–389 (1873)
- J. Leech, Notes on sphere packings. Canadian J. Math.19, 251–267 (1967)
- V. I. Levenshtein, Boundaries for packings in n-dimensional Euclidean space. Dokl. Akad. Nauk SSSR245, 1299–1303 (1979)
- 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)
- 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)
- F. Pfender and G. M. Ziegler, Kissing numbers, sphere packings, and some unexpected proofs. Notices Amer. Math. Soc.51, 873–883 (2004)
- C. E. Shannon, A mathematical theory of communication. Bell System Tech. J.27, 379–423, 623–656 (1948)
- A. Thue, Über die dichteste Zusammenstellung von kongruenten Kreisen in einer Ebene, Norske Vid. Selsk. Skr.1, 1–9 (1910)
- 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)
- 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 and Leech lattices. Eur. Math. Soc. Mag. 121 (2021), pp. 4–8DOI 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.