Skip to the Main Content

Note:These pages make extensive use of the latest XHTML and CSS Standards. They ought to look great in any standards-compliant modern browser. Unfortunately, they will probably look horrible in older browsers, like Netscape 4.x and IE 4.x. Moreover, many posts use MathML, which is, currently only supported in Mozilla. My best suggestion (and you will thank me when surfing an ever-increasing number of sites on the web which have been crafted to use the new standards) is to upgrade to the latest version of your browser. If that's not possible, consider moving to the Standards-compliant and open-source Mozilla browser.

March 24, 2016

E8 Is the Best

Posted by John Baez

As you may have heard, Maryna Viazovska recently proved that if you center spheres at the points of the E 8\mathrm{E}_8 lattice, you get the densest packing of spheres in 8 dimensions:

• Maryna S. Viazovska, The sphere packing problem in dimension 8, 14 March 2016.

The E 8\mathrm{E}_8 lattice is

E 8={x∈ℤ 8∪(ℤ+12) 8:∑ i=1 8x i∈2ℤ} \mathrm{E}_8 = \left\{x \in \mathbb{Z}^8 \cup (\mathbb{Z}+ \frac{1}{2})^8 \; : \;\, \sum_{i = 1}^8 x_i \in 2 \mathbb{Z} \right\}

and the density of the packing you get from it is

π 42 4⋅4!≈0.25367 \frac{\pi^4}{2^4 \cdot 4!} \approx 0.25367

Using ideas in her paper, Viazovska teamed up with some other experts and proved that the Leech lattice gives the densest packing of spheres in 24 dimensions:

• Henry Cohn, Abhinav Kumar, Stephen D. Miller, Danylo Radchenko and Maryna Viazovska, The sphere packing problem in dimension 24, 21 March 2016.

The densest packings of spheres are only known in dimensions 0, 1, 2, 3, and now 8 and 24. Good candidates are known in many other low dimensions: the problem is proving things, and in particular ruling out the huge unruly mob of non-lattice packings.

For example, in 3 dimensions there are uncountably many non-periodic packings of spheres that are just as dense as the densest lattice packing! There are also infinitely many periodic but non-lattice packings that are just as dense.

In 9 dimensions, the densest known packings form a continuous family! Only one comes from a lattice. The others are obtained by moving half the spheres relative to the other half. They’re called the ‘fluid diamond packings’.

In high dimensions, some believe the densest packings will be periodic but non-lattice.

For a friendly introduction to Viazovska’s discoveries, see:

• Gil Kalai, A breakthrough by Maryna Viazovska leading to the long awaited solutions for the densest packing problem in dimensions 8 and 24, Combinatorics and More, 23 March 2016.

I’m no expert on this stuff, but I’ll try to get into a tiny bit more detail of how the proofs work.

In 2001, Henry Cohn and Noam Elkies proved that the densest packing in 8 dimensions could be no more 1.000001 times as dense as that coming from the E 8\mathrm{E}_8 lattice. They showed that you could prove this kind of bound by finding a function

f:ℝ 8→ℝf : \mathbb{R}^8 \to \mathbb{R}

whose Fourier transform has certain nice properties. This is the avenue of attack that Viazovska pursued. She improved the bound from 1.000001 to 1.

To actually find her function ff, she needs to take the Laplace transforms of some modular forms and prove some fancy estimates about them. There are deep connections between lattices and modular forms, which I imagine are relevant here. I don’t understand this stuff very well.

However, the properties she needs her function ff to have are remarkably simple! Thanks to the work of Cohn and Elkies, it suffices to find a function with these properties:

  1. ff is radial: f(x)f(x) depends only on ‖x‖\|x\|, the distance from xx to the origin.

  2. ff is a Schwartz function: it and all its derivatives decrease faster than the reciprocal of any polynomial.

  3. f(0)=f^(0)=1f(0) = \hat{f}(0) = 1, where f^\hat{f} is the Fourier transform of ff.

  4. f^(x)≥0\hat{f}(x) \ge 0 for all x∈ℝ 8x \in \mathbb{R}^8.

  5. f(x)≤0f(x) \le 0 for all xx with ‖x‖≥2\|x\!\| \ge \sqrt{2} .

Getting 1-4 would be easy: do you see how to do it? But getting 5 as well makes it hard. If we flipped the inequality in 5, the whole thing would be easy: do you see why?

I find it utterly wonderful that the problem of finding this function ff — a challenge that any analyst might enjoy — turned out to be the key to proving that E 8\mathrm{E}_8 is the best lattice in 8 dimensions. It hints at the unity of mathematics.

Posted at March 24, 2016 4:58 PM UTC

TrackBack URL for this Entry:   https://golem.ph.utexas.edu/cgi-bin/MT-3.0/dxy-tb.fcgi/2874



14 Comments & 0 Trackbacks

Re: E8 Is the Best

I’ll take a punt at the question why the first 4 conditions on their own is “easy”: these are satisfied by a radial Gaussian with a “scale” of π. Then both the original values and the frequency values are greater than 0 (the opposite sign to condition 5). The Gaussian is often used as an example of Schwartzness.

Posted by: Davetweed on March 26, 2016 12:36 AM | Permalink | Reply to this

Re: E8 Is the Best

Right! A Gaussian!

So, condition 5), making f(x)≤0f(x) \le 0 outside the unit ball instead of positive, is a real shocker.

I believe Cohn and Elkies almost obtained conditions 1)-5), but needed

f(0)=1.000001 f(0) = 1.000001

instead of f(0)=1f(0) = 1.

Posted by: John Baez on March 26, 2016 12:46 AM | Permalink | Reply to this

Re: E8 Is the Best

Looking at the introduction to Viazovska’s paper, she has ‖x‖≥2\|x\| \geq \sqrt{2} in John’s (5), rather than ‖x‖≥1\|x\| \geq 1 (in her Theorem 3). I think it matters because John’s (3) introduces some normalization already, so it can’t just be dilated away.

What surprises me about these conditions is that no mention is made of the E 8E_8 lattice! I decided to track down the original argument in the Cohn and Elkies paper, which again is here. It’s surprisingly simple given some facts about packings which I suppose must be standard. Cohn and Elkies show that if there is f:ℝ n→ℝf: \mathbb{R}^n \to \mathbb{R} such that (with numbering chosen to match John’s):

  1. It is not actually necessary to assume that ff is radial, but you can impose this condition by averaging if you want.

  2. ff must be nice enough for the Poisson summation formula to apply (over an arbitrary lattice).

  3. f(0)=f^(0)>0f(0) = \hat f (0) \gt 0 (with the normalization convention that f^(t)=∫f(x)e 2πi⟨x,t⟩dx\hat f(t) = \int f(x) e^{2\pi i \langle x, t \rangle} dx)

  4. f^(t)≥0\hat f (t) \geq 0 for all tt

  5. f(x)≤0f(x) \leq 0 for ‖x‖≥r\|x\| \geq r

then

  • sphere packings in ℝ n\mathbb{R}^n have center density (density divided by the volume of the nn-sphere) bounded above by (r/2) n(r/2)^n.

The argument is short and slick (Cohn and Elkies say they originally arrived at the criterion in a more complicated way): First, it suffices to consider periodic packings because the packing density of an arbitrary packing can be approximated by the packing densities of periodic packings (just take the periodic packing generated by a sufficiently large dilation of the fundamental parallelogram of the packing you started with).

A periodic packing has its spheres centered at the points of a finite number of translates of a lattice Λ\Lambda. The argument is particularly simple when the packing is actually a lattice. In this case, the theorem statement is equivalent to the claim that a lattice of volume 1 must contain a vector of length ≤r\leq r. Giving ourselves an ϵ\epsilon of room, suppose that Λ\Lambda has covolume 1−ϵ1-\epsilon. The Poisson summation formula applied to the function ff and the lattice Λ\Lambda tells us that

∑ x∈Λf(x)=11−ϵ∑ t∈Λ *f^(t)\sum_{x \in \Lambda} f(x) = \frac 1 {1-\epsilon} \sum_{t \in \Lambda^*} \hat f (t)

where Λ *\Lambda^* is the dual lattice. If Λ\Lambda has no vector of length ≤r\leq r, then the only positive term on the left hand side is at x=0x=0 by (5), while all the terms on the right hand side are positive by (4). So we can throw the extra terms away to get

f(0)≥11−ϵf^(0)f(0) \geq \frac 1 {1-\epsilon} \hat f(0)

which contradicts (3). So there is an x∈Λx \in \Lambda of length rr after all. Taking ϵ→0\epsilon \to 0 we get the claim.

Posted by: Tim Campion on March 26, 2016 2:15 PM | Permalink | Reply to this

Re: E8 Is the Best

Thanks for catching that mistake, Tim. I sort of mixed up Viazovska’s Theorems 2 and 3, and didn’t notice that the number 2 shows up in an unavoidable way. I’ll fix that.

Thanks even more for summarizing Cohn and Elkies’ argument! I hadn’t looked into it, since I assumed it would be very difficult.

Your summary is really beautiful. One thing puzzled me at first; you say:

In this case, the theorem statement is equivalent to the claim that a lattice of volume 1 must contain a vector of length≤r \leq r. Giving ourselves an ϵ\epsilon of room, suppose that Λ\Lambda has covolume 1−ϵ1-\epsilon.

I think some readers would be stumped by the sudden appearance of the word ‘covolume’ here; they’d expect that at this point you would say something like “suppose that Λ\Lambda has volume 1+ϵ1 + \epsilon.”

However, the “covolume” of a lattice is just the reciprocal of its volume–meaning the reciprocal of the volume of its unit cell. So, you’re really just saying “suppose Λ\Lambda has volume 1/(1−ϵ)1/(1 - \epsilon)”. So, this step is not so strange.

I guess it’s known to you, but E 8\mathrm{E}_8 can be characterized as the unique lattice in 8 dimensions that has volume 1 and for which ‖x‖ 2\|x\|^2 is even for all xx in the lattice. I bet we could use these features of E 8\mathrm{E}_8 to show rather directly that E 8\mathrm{E}_8 is the best, given the result you just sketched, and Viasovska’s magic function ff.

Alternatively, we know the density of E 8\mathrm{E}_8, and Cohn–Elkies–Viasovska prove that’s the maximum possible density. But I don’t think that gets to the heart of the matter; when we calculate the density of E 8\mathrm{E}_8 we’re forced into thinking about its characterization.

The Leech lattice has an identical characterization in 24 dimensions, but with one extra clause: the shortest nonzero vectors in this lattice have ‖x‖ 2\|x\|^2 =4=4.

(For E 8\mathrm{E}_8 the shortest nonzero vectors have ‖x‖ 2\|x\|^2 =2=2, and I guess we need to use this too somewhere.)

Posted by: John Baez on March 26, 2016 7:03 PM | Permalink | Reply to this

Re: E8 Is the Best

Thanks, this is is a lot of fun! I just learned the term “covolume” from the paper; another definition is that the covolume of a lattice is the volume of the dual lattice. And the volume of a lattice Λ⊆ℝ n\Lambda \subseteq \mathbb{R}^n is the volume of the torus ℝ n/Λ\mathbb{R}^n / \Lambda.

Let’s see… I’ve probably heard this characterization of E 8E_8 from you before, but had forgotten it. Thinking about this is forcing me to better understand some basic facts used in the Cohn and Elkies argument. Specifically, if Λ\Lambda is a lattice of volume 1, a key fact used in their argument is that

  • the associated spherical packing has center density (density divided by the volume of the nn-sphere) ≤(r/2) n\leq (r/2)^n

    if and only if

  • Λ\Lambda has no vectors of length ≤r\leq r.

This is because

  1. The radius ss of the balls in the sphere packing is just s=t/2s = t/2, where tt is the length of the shortest nonzero vector in the lattice. Call this vector vv.

  2. The center density of the sphere packing is just s ns^n, where ss is the radius of the balls used in the packing.

So

  1. The center density of a lattice Λ\Lambda with volume 1 is (t/2) n(t/2)^n, where tt is the length of the shortest nonzero vector Λ\Lambda.

To see (1), note that t/2t/2 is an upper bound for ss, because otherwise the ball centered at 0 and the ball centered at vv would overlap. Conversely, if there were an overlap between two balls of radius t/2t/2 centered at different points of Λ\Lambda, then those two points would have a distance between them less than tt, and after a translation, we would have a nonzero vector of length less than tt in Λ\Lambda, contradicting the definition of tt as the minimizer of this quantity.

For (2), the point is that the spheres of the packing are in 1-1 correspondence with translates of “the” fundamental parallelogram for Λ\Lambda tiling ℝ n\mathbb{R}^n, since both are in 1-1 correspondence with the points of Λ\Lambda. So the packing density should just be the volume of one of these balls divided by the volume of a fundamental parallelogram (when you actually evaluate the limit defining the packing density, you have to be a little more careful, but this is the basic idea). The former quantity is s n⋅vol(S n)s^n \cdot \mathrm{vol}(S^n) while the latter is just 1. We divide out by vol(S n)\mathrm{vol}(S^n) to get s ns^n for the center density.

Anyway, the universal characterization tells us that E 8E_8 has volume 1, so we can use (3) to calculate the center density of E 8E_8 to be (2/2) n(\sqrt{2}/2)^n, since the shortest nonzero vector in E 8E_8 has length 2\sqrt{2}. (That is, we can just write down a vector of length 2\sqrt{2}, and the universal characterization tells us there are no shorter ones since the squared length must be even). Then Cohn and Elkies’ argument applied to Viazovska’s magic function tells us that this is the optimal density.

We only used the fact that E 8E_8 satisfies the properties of its characterization. Maybe using the uniqueness we could determine that E 8E_8 is the unique lattice minimizing packing density. Actually, this follows directly from (3) (without using Cohn and Elkies’ or Viazovska’s work) if we know something a little stronger – that E 8E_8 is the unique lattice of volume 1 whose shortest nonzero vector has length 2\sqrt{2}. But I guess this is well-known.

I wonder if E 8E_8 is the unique minimizer among all packings?

Posted by: Tim Campion on March 28, 2016 4:02 PM | Permalink | Reply to this

Re: E8 Is the Best

Tim wrote:

Actually, this follows directly from (3) (without using Cohn and Elkies’ or Viazovska’s work) if we know something a little stronger – that E 8E_8 is the unique lattice of volume 1 whose shortest nonzero vector has length 2\sqrt{2}. But I guess this is well-known.

Maybe it is, but I don’t know it.

I wonder if E 8\mathrm{E}_8 is the unique minimizer among all packings?

Unfortunately it’s a bit hard to make this precise in a way where it comes out to be true.

If we use the usual definition of density, which involves a limit over larger and larger regions of space, we can construct lots of different packings with the same density as E 8\mathrm{E}_8. For example, just take the E 8\mathrm{E}_8 packing and remove any finite number of balls! Or, remove a finite number of balls and then put some back in, higgledy-piggledy.

Admittedly, these examples seem silly. And I certainly had something more interesting in mind when I said:

For example, in 3 dimensions there are uncountably many non-periodic packings of spheres that are just as dense as the densest lattice packing! There are also infinitely many periodic but non-lattice packings that are just as dense.

What I meant is that you can build these packings by stacking hexagonal layers of balls, and there are two equally good ways to lay down each layer.

Unfortunately, I don’t know a precise general way to distinguish between the ‘silly’ ways to get packings of equal density and the ‘interesting’ ways. Maybe some experts know how.

However, I think all periodic packings count as ‘interesting’, since there’s no way to change them in a finite-sized region while preserving periodicity. So, one can ask if there are any periodic sphere packings in dimension 8 of density equal to the E 8\mathrm{E}_8 packing, other than rotated and/or translated versions of the E 8\mathrm{E}_8. I bet the answer is no, but I don’t know if anyone has proved this.

Posted by: John Baez on March 28, 2016 4:31 PM | Permalink | Reply to this

Re: E8 Is the Best

After a glimpse of the two papers of Viazovska and Cohn-Kumar-Miller-Radchenko-Viazovska, I think E 8E_8 should be the unique period packing that achieves the highest packing density. The latter paper quotes a paper of Cohn-Elkies on Page 9. In that paper, Cohn and Elkies proves: if the function ff and f^\hat{f} has no roots other than r=2k,k=1,2,⋯,n,⋯r=\sqrt{2k},k=1,2,\cdots,n,\cdots, then E 8E_8 is the unique optimal periodic packing. That is what Viazovska did in the last part of her paper.

Posted by: zy on August 9, 2016 5:09 AM | Permalink | Reply to this

volume / covolume

I might be confused, but I think that Cohn and Elkies (and Wikipedia) define the covolume of a lattice to be the volume of any unit cell ( = fundamental parallelotope? see the beginning of Section 2 of their paper).

What then is the volume of a lattice?

Posted by: j.c. on March 31, 2016 8:13 PM | Permalink | Reply to this

Re: volume / covolume

I think it would be insane to define the covolume of a lattice LL to be the volume of any unit cell of LL. That’s what I’d call the volume of LL.

The covolume of LL should be the volume of the dual lattice L *L^*, or equivalently, the reciprocal of the volume of LL.

In any event, that’s how Tim Campion and I are using these terms.

In certain ways of describing lattices, e.g. using quadratic forms, it can be easy to get mixed up between which one is LL and which one is L *L^*. I’m hoping that is what is happening to you.

Posted by: John Baez on March 31, 2016 9:29 PM | Permalink | Reply to this

Re: volume / covolume

I’ve looked around at a few more sources (e.g. 1.3 of Pete L. Clark’s notes on the geometry of numbers and some papers on discrete subgroups of Lie groups) and I am now more confident that what I stated above is the standard terminology, that is, the covolume of Λ\Lambda is defined to be the volume of any fundamental region.

I can see how it seems “insane”, but I think the reasoning for the “co” in covolume is that we are measuring the volume of the quotient ℝ n/Λ\mathbb{R}^n/\Lambda and not that of the discrete set Λ⊂ℝ n\Lambda\subset\mathbb{R}^n directly.

Googling around I see some support for this theory on this page.

Thus even when talking about lattices and their duals, it seems it’s standard to always use the term “covolume”.

I should have added earlier that I found your post and your exchange with Tim Campion otherwise very enlightening!

Posted by: j.c. on March 31, 2016 10:09 PM | Permalink | Reply to this

Re: E8 Is the Best

Yet again, Erica Klarreich has written an article on cutting-edge math that’s interesting for experts yet also fun for non-experts, at Quanta:

I’ll quote a bit about Maryna Viazovska, who turns out to be Ukrainian:

Viazovska’s 2013 doctoral dissertation was on modular forms, and she also has expertise in discrete optimization, one of the fields that are central to the sphere-packing problem. So when, three years ago, Viazovska’s friend Andrii Bondarenko, of the Norwegian University of Science and Technology in Trondheim, suggested that they work together on the eight-dimensional sphere-packing problem, Viazovska agreed.

They worked on the problem off and on along with Danylo Radchenko of the Max Planck Institute for Mathematics in Germany. Eventually, Bondarenko and Radchenko moved on to other problems, but Viazovska pressed on alone. “I felt like it’s my problem,” she said.

After two years of intense effort, she succeeded in coming up with the right auxiliary function for E 8\mathrm{E}_8 and proving that it is correct. It’s difficult, she said, to explain just how she knew which modular form to use, and she’s currently writing a paper to try to describe her “philosophical reason” for searching for it where she did. There’s “a whole new mathematical story behind it,” she said.

After Viazovska posted her paper on March 14, she was startled by the surge of excitement it created among sphere-packing researchers. “I thought people would be interested in the result, but I did not know there would be that much attention,” she said.

That night, Cohn emailed to congratulate her, and as the two exchanged emails he asked if it might be possible to extend her method to the Leech lattice. “I felt like, ‘I am already tired and I deserve some rest,’” Viazovska said. “But I tried still to be useful.”

The two of them threw together a collaboration with Kumar, Radchenko and Stephen Miller of Rutgers University, and with the benefit of Viazovska’s earlier work, they quickly found a way to construct the right auxiliary function for the Leech lattice. The team posted its 12-page paper online just a week after Viazovska had posted her first paper.

Posted by: John Baez on March 31, 2016 5:07 PM | Permalink | Reply to this

Re: E8 Is the Best

Since the Coxeter-Todd Lattice is a sublattice of the Leech Lattice would it then have the densest packing of spheres in 12 dimensions? Its kissing number is 756.

Posted by: Mark Thomas on April 1, 2016 12:28 AM | Permalink | Reply to this

Re: E8 Is the Best

No such deduction is possible—at least, not with what we know. The only dimensions in which we know the densest sphere packings are 0, 1, 2, 3, 8 and 24.

We have candidates in many other dimensions, and I believe the Coxeter–Todd lattice is the densest known packing in 12 dimensions: see the picture in Conway and Sloane’s book. But except in dimensions 0, 1, 2, 3, 8 and 24, we don’t have proofs that these candidates are optimal.

So, we are very lucky to be alive in a month when the number of dimensions where this question is settled increased by 50%.

Posted by: John Baez on April 1, 2016 12:43 AM | Permalink | Reply to this

Re: E8 Is the Best

You wrote,

“…the problem is proving things, and in particular ruling out the huge unruly mob of non-lattice packings.

For example, in 3 dimensions there are uncountably many non-periodic packings of spheres that are just as dense as the densest lattice packing! There are also infinitely many periodic but non-lattice packings that are just as dense.”

The second sentence seems misleading in context - there’s no need to consider non-periodic packings (with the caveat that to my knowledge we don’t have a “compactness” result for the densities of periodic packings).

Posted by: Daniel Vitek on May 15, 2016 3:46 PM | Permalink | Reply to this

Post a New Comment