Thursday, March 31, 2016 ... Deutsch/Español/Related posts from blogosphere

Ukrainian girl proves that \(E_8\), Leech rule in sphere packing

Berlin postdoc Maryna Viazovska proves the lore in dimensions 8 and (with pals) 24

Erica Klarreich brought the readers of the Quanta Magazine some wonderful summary of three mathematical preprints on the arXiv:

Sphere Packing Solved in Higher Dimensions
The question is sort of obvious even to little kids. You have equally large \(n\)-dimensional spheres (the sphere is a set of points with a fixed Pythagorean distance \(R\) from the center). How do you arrange these non-overlapping objects in a big box so that the number of balls in the box is maximized?

You may fill the 1-dimensional space, a line, with 1-spheres, i.e. line intervals, completely. That was easy! ;-)

For 2-spheres, i.e. circles (or disks), the hexagonal packing is almost obviously the densest packing (the filled fraction is \(\pi/\sqrt{12}\approx 90.69\%\)) even though this result was only rigorously proved by Fejes Tóth in 1940. But what about other dimensions?

In three dimensions, you may ask a clerk in a fruit-and-vegetable shop to arrange oranges. But the "ground layer" is better not be hexagonal.

At least in the shop, it is better to start with the "square packing" and place the following "floor" of oranges to the centers, in the pyramidal way. About 74.048% or \(\pi/\sqrt{18}\) of the volume is occupied by the fruits at the end; a "random" packing only brings you to 64% or so. Thomas Hales proved this result – which was conjectured by Johannes Kepler in Prague in 1611 – with the help of a computer (and two proof assistant programs!) in 1998 (pictured above soon after his finding).

For even higher dimensions, the problem becomes messy as increasingly many candidate packings may compete and the winner isn't quite obvious. But there exist two dimensions, \(D=8\) and \(D=24\), where truly excellent candidates for the densest packing have always existed. It was the "default belief" of all mathematicians for very many decades that these candidates give us the densest packing in these two dimensions, indeed.

These structures are equivalent to lattices \(\Lambda\), discrete subsets of \(\RR^D\) that are closed under addition (and linear combinations with integer coefficients) – basically tilted and stretched visualizations of \(\ZZ^D\). You just place the centers of the spheres to the elements of the lattice and inflate the balls around them to the maximum radius so that they don't overlap. In this way, you may obtain a good candidate for dense packing.

So if the densest packing is indeed given by a lattice, which has also been proven now, I hope, the question is which lattice \(\Lambda\) gives you the densest packing. In all dimensionalities of the form \(D=8k\), there exist the so-called "even self-dual lattices". They're subsets \(\Lambda\) of the Euclidean space \(\RR^D\) that have the property that \(\vec v\cdot \vec v\) is an even integer for every \(\vec v\in\Lambda\); and the lattice is equal to its dual lattice \(\Lambda^*\), e.g. the set of all vectors \(\vec v'\) such that \(\vec v\cdot \vec v'\in\ZZ\) for all \(\vec v\in\Lambda\).

Note that the dual lattice to the "most ordinary" lattice \(\ZZ^D\) is \(\ZZ^D\) again. But this choice isn't too good for dense packing. You want some nontrivial angles like those in the hexagonal or pyramidal packing in \(D=2\) and \(D=3\), respectively. Moreover, you may see that \(\ZZ^D\) is not an even lattice – the squared lengths may be even or odd. On the other hand, the rescaled lattice \(\sqrt{2}\ZZ^D\), if you understand me, isn't self-dual.

Even self-dual lattices are really cool and fundamental. In string theory, chiral bosons – bosonic coordinates describing an embedding of a string world sheet to a spacetime that are purely left-moving or holomorphic, \(X^i(z)\), are obliged to define a target space that is a torus \(T^D=\RR^D/ \Gamma^D\), a quotient of the real space by an even self-dual lattice.

Both conditions, "even" and "self-dual", arise from the modular invariance, i.e. the invariance of the world sheet theory under large coordinate transformations (diffeomorphisms of the toroidal world sheet that cannot be continuously connected to the identity transformation). The "even" condition has to be true because of the \(\tau\to\tau+1\) part of the modular group because it requires \(L_0-\tilde L_0\) to be integer, and not half-integer, so that the "odd" states are forbidden. The self-duality arises from the invariance under the other generator of the \(SL(2,\ZZ)\) modular group, \(\tau\to-1/\tau\). One can show it by some detailed discussion of modular functions. More physically, we may say that the lattice of winding numbers is dual to the lattice of momenta (because the vertex operators with momenta and winding have to be mutually local on the world sheet) and the "chirality" (absence of the right-moving part) means that the momentum of a string has to be equal to its winding, so the allowed lattices for these objects must be the same – and that's equivalent to the self-duality of the lattice where they belong.

In the dimension \(D=8\), the unique self-dual lattice is the root lattice of the \(E_8\) group, the largest, namely 248-dimensional, exceptional simple compact Lie group. In terms of the obvious orthonormal basis vectors \(\vec e_i\) for \(i=1,2,\dots, 8\), the \(E_8\) lattice contains all integer combinations of the vectors \(\vec e_i\pm \vec e_j\) for \(i\neq j\) and of \(\sum_{i=1}^8 \vec e_i/2\). If you want to have a more direct idea what the vectors look like, well, their coordinates are either "all integers" or "all half-integers", and the sum of the components has to be even.

The minimum \(\vec v \cdot \vec v\) of the nonzero elements of the lattice – which decides about the (squared) radius of the balls we may afford – is still two (eight times one quarter equals two) even though we were able to double the number of elements of the lattice by adding this "whole class" of lattice sites with half-integer coordinates. In some sense, we managed to increase the density of lattice sites by a factor of two – and that's surely good news for dense packing. With this virtue, the \(E_8\) lattice manages to achieve the "packed volume" of \(\pi^4/384\) or about 25.37%.

If you use Cartan's toroidal constructions of Lie groups, you will realize that there exists a 248-dimensional Lie group whose root lattice (which happens to be the same as the weight lattice, in this particular case) is the \(E_8\) lattice we described in the previous paragraph. There are \(112+128=240\) roots i.e. elements of the lattice with the squared length equal to two, namely \(112\) roots of \(SO(16)\) of the form \(\pm \vec e_i\pm \vec e_j\) with the independent plus-minus signs and \(i\neq j\), and the additional \(128\) roots \(\sum_{i=1}^8 \pm \vec e_i/2\) with an even number of pluses. Those transform as a chiral spinor under \(SO(16)\); the "even" condition is what makes the spinor chiral. In combination with the eight generators associated with the Cartan torus itself, we may construct the \(248\)-dimensional Lie algebra of \(E_8\).

The \(E_8\) lattice also gives us the most natural way to define the integral octonions.

In \(D=16\), there are two even self-dual lattices. One of them is just the weight lattice of \(E_8\times E_8\), i.e. two copies of the \(E_8\) lattice described above. The other is the weight lattice of a \(Spin(32)/ \ZZ_2\) lattice. Both corresponding Lie groups have rank 16 and dimension 496 because \(248+248=32\times 31/2 \cdot 1\), facts that are needed (but not sufficient) for the anomaly cancellation in the effective theories of the ten-dimensional superstring vacua (the anomaly cancellation was nontrivial yet true and sparked the First Superstring Revolution in 1984).

As I have explained many times, the heterotic string of string theory is a great theory – and arguably still the most promising description of Nature that science knows – that uses these two even self-dual lattices. "Heterosis" means "hybrid vigor", the ability of offspring to pick virtues from both (very different) parents.

The parents of the heterotic string are \(D=10\) superstring theory and \(D=26\) bosonic string theory. It's possible for the left-moving and right-moving bosons on the world sheet to "live" in different spacetimes. But the \(26-10=16\) directions of the spacetime that only exist in the bosonic string theory are chiral, and they must be compactified on an even self-dual torus, as argued above. There are exactly two ways to do that, corresponding to the two even self-dual lattices in \(D=16\). This is how four Princeton physicists (the Princeton string quartet, Gross, Harvey, Martinec, Rohm) discovered the two different heterotic string theories in \(D=10\) in 1985. Their low energy limits correspond to the \(D=10\) type I supergravity coupled to super Yang-Mills with the gauge group either \(E_8\times E_8\) or \(Spin(32)/ \ZZ_2\). A fermionized description was immediately found, too. Sixteen bosons may be replaced by thirty-two fermions. The consistent GSO projections allow plus/minus signs for their groups – either for the whole group of 32 fermions which gives \(Spin(32)/\ZZ_2\), or for two separate groups of 16 fermions which gives \(E_8\times E_8\) thanks to the extra massless states in the mixed periodic-antiperiodic sectors etc.

In the mid 1990s, it was realized that the strong coupling limit of the \(Spin(32)/ \ZZ_2\) theory is the type I string theory with the open and closed strings (the \(SO(32)\) charges are carried by quark/antiquark "Chan-Paton factors" or 32 different half-colors at the end points of the open strings) – people could have noticed much earlier that the same group \(SO(32)\) probably wasn't an accident – and the strong-coupling limit of the \(E_8\times E_8\) heterotic string theory is the Hořava-Witten M-theory on a "layer of 11D spacetime" with two 10D boundaries. Each of them supports one of the two \(E_8\) gauge supermultiplets, so the two \(E_8\) factors get "geometrically separated" in the direction of the new, M-theoretical, eleventh dimension of the spacetime. Similar dualities have connected all "previously separated versions of string theory" into one connected network, string theory (singular) in the new sense, and that's why the Second Superstring Revolution of the mid 1990s is sometimes referred to as the Duality Revolution.

But already in the 1980s, people realized that once we compactify one of the 9 spatial dimensions on a circle, the two heterotic string theories are equivalent to one another by T-duality. Mathematically, this results from the fact that even self-dual lattices also exist in Minkowskian mixed-signature spacetimes of dimension \((m,n)\) with \(m-n=8k\). And if \(mn\neq 0\), the even self-dual lattice is actually unique up to the "discrete Lorentz transformations". That's why all the solutions have to be T-dual to each other.

Nevertheless, in purely Euclidean spaces of dimensions \(D=8k\), the number of inequivalent even self-dual lattices may be higher. This is the case of the following multiple of eight, \(D=24\). As I happened to mention less than a week ago, there are 24 inequivalent even self-dual lattices in \(D=24\): one Leech lattice and 23 other Niemeier lattices (or do the 23 fail to be self-dual?).

The Leech lattice is really cooler. The shortest nonzero vectors of the \(E_8\) lattice had \(\vec v \cdot \vec v = 2\) but the Leech lattice succeeds in eliminating all these vectors. The shortest nonzero vectors of the Leech lattice have \(\vec v\cdot \vec v =4\). This "enhancement" has many very different consequences.

One of them is that we don't get anything such as a "continuous Lie group similar to \(E_8\)" if we use this lattice in the same way as the lattices in the heterotic string constructions discussed above. There are just no new gauge bosons! This is the reason why the spacetime spectrum is sort of "minimized" if the Leech lattice is involved. We don't get big Lie groups but we actually do get huge discrete groups.

If you repeat the heterotic-like construction but with the Leech lattice instead of the \(E_8\) and similar lattices, you will obtain a theory whose symmetry group is the monster group, the largest sporadic (analogy of "exceptional") group in the classification of finite groups. It's no coincidence: string theory compactified on the Leech lattice (well, the corresponding torus) is what explains the "monstrous moonshine", namely the appearance of the numbers \(196,883\) and \(196,884\) at two seemingly very different places of mathematics.

Also, Witten has figured out a decade ago that a precise two-dimensional conformal theory i.e. "world sheet description of string theory" is also the right boundary CFT whose "holographic dual in the bulk", according to Maldacena's AdS/CFT correspondence, is nothing else than the "pure" gravity (with no other fields) in the 3-dimensional anti de Sitter space (for the minimum radius only). The number of TRF blog posts on this Witten's monstrous stuff is a bit large, I don't want to look for the right articles separately.

In the Leech lattice, the fact that the shortest nonzero vectors have \(\vec v \cdot \vec v = 4\) has one more consequence: this number four is large which really means that all the elements of the lattice are surprisingly far from each other. That's what makes it possible to "inflate" the sphere much more (the radius may grow by a factor of the square root of two) than for other "similar" lattices you could invent. That's really the best reason to guess that in \(D=24\), the densest packing is defined by the Leech lattice.

As the Quanta Magazine reviews in some detail, people's faith that the \(E_8\) lattice and the Leech lattice define the densest packing in \(D=8\) and \(D=24\) has gradually grown due to some new results and conjectures. The latest steps were done by Maryna Viazovska – by herself and with collaborators – weeks ago. These steps were really a proof of a conjecture stated by Cohn and Elkies in 2003. Those guys (I hope that Cohn is a guy, otherwise his name should be Sarah) introduced some "linear programming" bounds and Viazovska has analyzed some modular functions to show that no one can beat the "conjectured densest packing" lattice. My understanding is that she has really added some "nearly stringy" stuff to the "mostly messy computer-science-related" methods by Cohn and Elkies.

The papers:
The sphere packing problem in dimension 8, Viazovska

The sphere packing problem in dimension 24, Cohn, Kumar, Miller, Radchenko, Viazovska

See also:
Some properties of optimal functions for sphere packing in dimensions 8 and 24, Cohn, Miller
All these papers were posted in recent three weeks. The \(D=24\) variation by many authors uses the same methods as the original Viazovska's method for \(D=8\). I believe that the "Leech is densest in \(D=24\)" result has already been previously proven by other tools, at least it's mentioned as a fact in several older TRF blog posts.

I won't try to reproduce the steps because I don't really understand the methodology of the proof at this moment (although I am sure that at a vague level, the strategy has similarities to my minimization approach to the Riemann Hypothesis). But it's clearly beautiful, with deep links to the structures in string theory.

The densest packing problem is something that most kids in the kindergarten may understand rather well. It just happens that the "by far best" solutions exist in \(D=8\) and \(D=24\). The solutions are defined by lattices. The best \(D=8\) lattice is the root lattice that heterotic string theory uses to generate \(E_8\), the largest exceptional compact Lie group, as the gauge group in the spacetime. The best \(D=24\) lattice is the Leech lattice on which compactified string theory produces a theory with the monster group symmetry, the largest sporadic group in the classification of the finite groups. Moreover, this two-dimensional string theory seems to be holographically dual to the "simplest" theory of quantum gravity in three spacetime dimensions, the pure gravity in \(AdS_3\).

All these mathematical structures are beautiful, fundamental, and connected via string theory. For example, Viazovska also discusses the "Jacobi obscure identity" which may be interpreted as a necessary condition for the equivalence of two descriptions of supersymmetry in superstring theory. The real world isn't given by string theory compactified on these "simplest and most beautiful lattices". But the compactification that produces the Universe around us is obviously a cousin of these mathematical structures.

I guess that all the deep string theorists, while they may be partially motivated by the desire to calculate the results of all experiments with arbitrary precision and no input, are also partly motivated by the desire to "understand all of mathematics that is worth understanding". All the "truly pretty" mathematics, all the mathematical structures that work and especially those that "by far" overshine all of their competitors, are sort of naturally connected via string theory. String theory is what shows why they exist at all, why they're fundamental, why they're prettier than all competitors, and why they're connected with each other.

The people who refuse to see even glimpses of these insights and the remarkable depth of all these structures and ideas are on par with (the moment to applaud would be now!) troglodytes.

And that's the memo.

Her papers are short enough and effective but given the simplicity of the original problem and the connection of the problem to deep mathematics and physics, I for one have no doubts that she deserves all the mathematics prizes she is eligible for. She was born in 1984 so be sure she's ready for a Fields Medal.

See also: John Baez, Gil Kalai,

Add to Digg this Add to reddit

snail feedback (0) :

(function(i,s,o,g,r,a,m){i['GoogleAnalyticsObject']=r;i[r]=i[r]||function(){ (i[r].q=i[r].q||[]).push(arguments)},i[r].l=1*new Date();a=s.createElement(o), m=s.getElementsByTagName(o)[0];a.async=1;a.src=g;m.parentNode.insertBefore(a,m) })(window,document,'script','//','ga'); ga('create', 'UA-1828728-1', 'auto'); ga('send', 'pageview');