Sphere Packing Solved in Higher Dimensions
quantamagazine.org
quantamagazine.org
edit: that's funny, I just realized the author of this link is quoted in the OP's article.
EDIT: Looks like I spoke too soon! There's one in the link posted by @foota in these comments (p33 of [1])
[1] http://www.ams.org/programs/students/wwtbam/cohn-slides-2014...
In case like me you're wondering just how densely you can pack spheres in the highly favorable 24th dimension: the best you can do is about 0.2% of the total volume.
In the very first lecture Huffman concluded the class with the statement "It turns out, sphere packing in 7 dimensions is easy! And this has applications to telephone routing..." (he worked for Bell Labs).
I thought it was interesting how he spent nearly an hour explaining something that seemed totally pure math and it ended up helping AT&T scale phone networks.
We both might know enough about math to know what a Lebesgue measure is, but Real Analysis wasn't a requirement for most CS majors posting on here I'd imagine. (I agree with my uncle/aunt poster, though-- this is way more accessible to the general mathematician than a Wiles on Fermat or Perelman on Poincare. It's self-contained enough to clearly define * weakly-holomorphic modular form* [which I could take a stab at, but not with too high of a confidence factor]. Spending a few minutes to throw (19) in there was kind of the author to do, so those from other disciplines of mathematics could continue reading instead of just presuming what \gamma was.)
[0] https://news.ycombinator.com/item?id=258198
The lattice is really easy to describe. It's a set of points in 8-dimensional space, so each point is specified by 8 numbers. A point is in the lattice if the following conditions hold. (1) Either all its coordinates are integers, or all are half-integers. (2) The sum of the coordinates is an even integer.
(And then the densest packing of spheres in 8-dimensional space puts the centre of a sphere at each point. The radius of the spheres is then 1/sqrt(2).)
The E8 that features in Garrett Lisi's attempted "theory of everything" is a so-called "Lie group". I'll attempt to sketch the relationship between lattices like the E8 lattice, and "Lie algebras", and Lie groups, and particle physics, but note that all of what follows is really handwavy and sometimes just plain wrong. Sometimes on purpose, probably sometimes by mistake. I'm sorry about any mistakes, but the deliberate lies and sketchiness are necessary to keep this shorter than textbook length. I hope it's at least semi-comprehensible.
(Although it's shorter than a textbook, it's also too long for a single HN comment. I'll break it into pieces and make each a reply to its predecessor. HN mods, let me know if this is considered bad form and I'll refrain from doing it in the future.)
OK, here goes.
PHYSICS AND SYMMETRY
OK, let's begin at the physics end. Here are some facts about plain old Newtonian physics. (1) The physical laws make no reference to particular positions in space; equivalently, if we e.g. replace (x,y,z) with (x+a,y+b,z+c) everywhere, for constant a,b,c, then the laws don't change. (2) If you have a system of particles interacting only with one another, the total momentum (sum of mass times velocity) is constant. It turns out that #1 and #2 are sort of equivalent: for a broad class of physical theories, symmetries (like #1, the fact that adding a constant to the coordinates changes nothing) are equivalent to conservation laws (like #2, conservation of momentum). Here's a subtler one: the laws don't pick out preferred times any more than preferred positions, and that fact is equivalent to conservation of energy.
That was all in Newtonian physics, but it works more or less the same in relativity and in quantum mechanics.
There are some much subtler kinds of symmetry present in our physical laws, and they give rise to subtler conservation laws. For instance, you may be familiar with the notion of "phase" in optics; in a classical picture this corresponds to the exact location/timing of the electromagnetic waves that make up light; in quantum mechanics everything is described by a "wavefunction" whose value at every point in the relevant configuration space is a complex number, and the optical phase of light turns out to correspond to the phase of the photons' wavefunctions. Changing all the phases by the same constant amount leaves every possible observation you could make unaltered, which means it's a symmetry of the physical laws; and this symmetry turns out to correspond to conservation of electric charge.
This picture gets more complicated when you throw in the "weak nuclear force", which turns out actually to be kinda the same thing as electricity and magnetism, and hairier still when you throw in the "strong nuclear force". You get symmetries that, e.g., describe exchanging different kinds of particle with one another (kinda), and corresponding conservation laws.
GROUPS AND LIE GROUPS
If you look at a high enough level of abstraction at what different kinds of symmetry have in common, you get the pure-mathematical notion of a group. The idea, roughly, is that if you have some thing (e.g., a block of metal or a physical theory) and some kind of symmetry (e.g., ways you can move the block of metal around and end up with it looking exactly the same as before; ways you can change some things in the laws of physics and end up with equivalent laws), then all the symmetries of the thing together have a particular kind of mathematical structure. This basically comes down to these rather obvious observations: if you have two operations that leave your thing looking the same then doing one and then the other also leaves your thing looking the same; and undoing one such operation also leaves your thing doing the same. And a mathematical structure that supports "doing one thing and then another", and "undoing a thing", is a group.
These symmetries in physics have an important feature: they don't occur in isolation but come in continuously-varying families. E.g., translation-invariance, the (x+a,y+b,z+c) thing, allows any value of a,b,c; you can vary them continuously and get the same results all the time as you do so. This means that the symmetry groups that describe them mathematically have this continuously-varying property, and the mathematical formalization of this gives you the notion of "Lie groups". (Named after a mathematician called Sophus Lie.)
Some Lie groups can be built out of other simpler ones, in something a bit like the way that some numbers can be written as the product of other smaller ones. If you break them down as far as possible, you get to the so-called "simple Lie groups", which are kinda like the prime numbers: every Lie group can be built out of simple Lie groups.
And it turns out that we can figure out what all the possible simple Lie groups are. There are four infinite families of them called A,B,C,D, and a few special ones that don't fit into the families. The most complicated of these special ones is called E8.
A BIT MORE PHYSICS
Garrett Lisi's attempted "theory of everything" was based around the idea that the pattern of symmetries of the laws of physics is that of the group E8. We don't see all those symmetries in the laws we know, but that isn't necessarily a problem because of a thing called spontaneous symmetry breaking. Imagine a big tank of water. Within that tank (at least away from its edges) no direction is different from any other -- the laws of physics don't have preferred directions, and neither does a bunch of water molecules bouncing off one another at random. This symmetry corresponds to conservation of angular momentum, so e.g. movements of water within the tank should obey that law. OK; now what if we reduce the temperature and the water freezes? Ice crystals, unlike liquid water, have a regular structure and they do have a preferred direction; so some things that happen in our tank full of ice may fail to conserve angular momentum.
(Let me be careful about this. Of course the overall laws of physics still satisfy that law, so if we consider the whole contents of the tank C of AM will still hold. But if we treat the ice in the tank as "background" and consider, I dunno, electrons moving around within the ice or something, their total angular momentum may fail to be constant, because of angle-dependent interactions with the ice.)
The same kind of thing can happen with the more "abstract" kinds of symmetry: as the universe cools -- and note that the universe now is much much cooler than shortly after the big bang -- it may settle into some less-symmetrical configuration (like our tank of ice), and the asymmetries in the universe may look to use like asymmetries in the laws, even though the real fundamental laws are symmetrical.
So, anyway, Lisi's theory is probably wrong, but the mere fact that E8 is bigger than the group of symmetries we actually observe in the universe isn't in itself good reason to disbelieve it. Now let's do (or at least gesture vaguely towards) some more mathematics, with the hope of ending up with some understanding of how the group E8 relates to the lattice E8.
LIE ALGEBRAS
To describe the relationship between the Lie group E8 and the lattice E8, I need to go via another kind of mathematical object called a Lie algebra. These are in some sense simpler cousins of the Lie groups, but they're harder to describe and harder to explain why you'd care about them. Still, here goes.
Let's look at one of the very simplest Lie groups. Take the ordinary euclidean plane -- imagine an infinitely large perfectly flat piece of paper. Fix a point in it; call it O. And consider rotations around O. These form a Lie group; it's sometimes called U(1), never mind why. We can describe it geometrically: it's a circle. (Pick some point that isn't O; call it P. Describe any rotation by saying where P goes to. That point is always on the circle through P with centre O. Conversely, if we pick such a point, there's a rotation that takes P there.)
A circle is pretty simple, but you know what's even simpler? A straight line. And if you look only at very small portions of the circle, they look a lot like very small portions of a straight line. This is the fundamental idea behind calculus: all nice things look linear if you look at a small enough scale. And linear things are easier to work with, mathematically. So: suppose we have a Lie group -- that is, a continuously-varying set of symmetries of something. Take a tiny region of it near to the origin; that is, near to the trivial symmetry that does nothing. This tiny region looks like a piece of euclidean space in some number of dimensions, but there's some extra structure on it that describes the relationships between those symmetries -- what happens when you do one followed by another.
What does that extra structure look like? It turns out that it's best described by what's called a bracket operation, meaning that given two elements x,y we have another written [x,y] which you should think of as meaning xy-yx. Imagine e.g. that x,y are actually matrices. Matrix multiplication usually doesn't commute, so generally xy-yx is not zero. Here, in some sense the multiplication operation corresponds to the "do one symmetry followed by another" operation on the original Lie group; that no longer exists in our "infinitesimal" view, but the bracket describing what changes when you switch the order of the symmetries still does. Kinda.
The bracket operation obeys a number of laws like the so-called Jacobi identity [x,[y,z]] + [y,[z,x]] + [z,[x,y]] = 0. The details aren't important right now. Anyway, the idea that we end up with when we follow this path and do attend to the details is that of a thing called a "Lie algebra", which describes what small pieces of a Lie group look like, and which in general looks like a euclidean space of some dimension together with a "bracket operation".
Corresponding to the Lie group called E8 there is, therefore, a Lie algebra also called E8.
REPRESENTATIONS, WEIGHTS, AND ROOTS
Suppose we have a Lie group and its corresponding Lie algebra which, remember, is kinda like a blown-up copy of an infinitesimally tiny bit of the original group. Then there's a natural way for the group to "act on" the algebra, which roughly speaking corresponds to the ordinary "do one symmetry and then another" operation in the group.
But the Lie algebra is, among other things, a vector space (what I've described above as a euclidean space), and it turns out that each symmetry in the group gives us a linear transformation of that space. Another way to say this is that we're taking our abstract symmetry group, and exhibiting its elements as symmetries of a particular object, namely the Lie algebra. This situation, where you have a group and you find a way to turn its elements into linear transformations of a vector space, is called a representation of the group.
We can also have the Lie algebra act on itself in a basically-equivalent way, and then what we get is a representation of the Lie algebra.
(In quantum physics, the state of the universe is described by a vector in an enormous vector space, symmetries of the laws of physics correspond to linear transformations on that vector space, and so representations arise quite naturally. If instead of asking about the whole universe we ask about some much smaller configuration of particles, we get a much smaller vector space; if the symmetries we're interested in leave that configuration of particles alone, we get a representation on the smaller vector space.)
The next bit is kinda unmotivated. I'm sorry.
So, suppose you have a representation of a Lie algebra -- a manifestation of its elements as linear transformations on a vector space. Consider what's called a "Cartan subalgebra", which is to say as large as possible a subspace of the Lie algebra with the property that within it all the brackets are zero. (Meaning that the corresponding things in the Lie group commute, meaning that it doesn't matter whether you do A then B or B then A.) Let's give names to some key objects here. G consists of the linear transformations corresponding (under our representation) to the original Lie algebra. H consists of the ones coming from the Cartan subalgebra; so it's just a portion of G, usually a lot smaller than G itself.
Now, suppose we have g in G and h in H. We can apply our bracket operation to them -- in fact, since we're doing all this via the representation, the bracket is always just gh-hg in terms of matrix (= linear transformation) multiplication. If we're lucky, the following amazing thing might happen: this might (1) always be a scalar multiple of g, where (2) the actual multiple only depends on h. That is, we might have [g,h] = f(h)g for some function f, which in fact will always have to be linear. That would be a hell of a coincidence, but perhaps a smaller coincidence might happen: the same might hold but only for some subspace of G.
The linear functions on H for which this does happen for a nontrivial subspace of G are called weights for the representation. (It's a pretty terrible name. I'm sorry.)
There's a particularly important representation called the "adjoint representation", which is the one I described above immediately under the heading "REPRESENTATIONS, WEIGHTS, AND ROOTS". The weights of the adjoint representation are called "roots", which is also a terrible name.
What happens for E8? Well, the Cartan subalgebra is pretty small; it's 8-dimensional (versus 248-dimensional, as it happens, for E8 itself). To describe a linear function that maps an 8-dimensional space onto numbers, you need 8 numbers -- e.g., the first says what number (1,0,0,0,0,0,0,0) maps to. So you can think of its roots as also living in an 8-dimensional space.
It turns out that there are exactly 240 roots for E8; they are as follows. First, there are all the 8-dimensional integer vectors of length sqrt(2); that is, the vectors of 8 integers consisting of six 0s and two +-1s. There are 112 of these. Second, there are the 8-dimensional vectors whose entries are all +1/2 or -1/2, where we have an even number of +1/2 and an even number of -1/2. There are 128 of these.
THE ROOT LATTICE
Finally: the root lattice for a Lie algebra consists of all integral combinations of its roots. So, e.g., for E8 we have the 240 roots listed above; call them r1,r2,...,r240. The root lattice consists of everything you can get by picking integers a1,a2,...,a240 and computing a1.r1 + ... + a240.r240.
And lo, the root lattice is exactly the E8 lattice I described way up above.
And you're right the power doesn't matter because continuum^n = continuum.
Perfect Shapes in Higher Dimensions: https://www.youtube.com/watch?v=2s4TqVAbfz4
In any case, that video is part of the excellent longer film "Outside In" made at the Geometry Center in the 90s:
What was once attacked with NP-hard algorithms now has a constructive one.
Reminds me a little bit of the lottery problem - one has to find the minimum sized set of tickets that guarantee a match of at least K numbers on any of the tickets. Statistics can easily get you the expected number of tickets you have to buy but finding that minimum set can be mapped to a minimum set cover (where you're trying to cover all tickets with your set so that tickets in the set match all possible tickets in at least K numbers).
Then, all of a sudden maths can put bounds and direct formulas of how many tickets your set has to have (not trivial).
Leaving you again with a constructive polynomial algorithm.
The primary observation is if you want to match k numbers on tickets where you pick n numbers, each ticket simultaneously covers n choose k different k-tuples. The Translyvanian lottery is designed so that finite projective planes give you the minimal result (no pair appears on more than one ticket).
This sort of combinatorial design is rumored to have been used by the MIT syndicate that gamed the Massachusetts lottery (notably, they manually and laboriously picked their numbers while the other two syndicates were using random quick picks).
(I've had to learn a lot about lotteries in the last two years :P)
On a side note, finding a minimal set of tickets to cover a set of outcomes is exactly analogous to testing software with pairwise testing: https://en.wikipedia.org/wiki/All-pairs_testing
It is still unsolved although maths has provided some nice bounds for large amounts of (n,k,m) triplets, and solutions to (n,k,2). Although, for the (n,k,2) a simple greedy set cover finds the optimal solution always.