Sphere-Packing

Is there a way to pack more than 4 disks of diameter 1 into a 2-by-2 square?

Obviously not. But is there a way to pack more than 4000 disks of diameter 1 into a 2-by-2000 rectangle?

Again, obviously not — except that there is a way! (See my essay “Believe It, Then Don’t” for details.) So packing problems can be tricky.

If you’re packing equal-size disks into a large region, it’s intuitive that the best way to pack them is six-around-one. This is the hexagonal packing, and László Fejes Tóth showed in 1940 that it’s the best way to pack the infinite plane. Here the word “best” needs to be unpacked (pardon the pun), since both the hexagonal packing and the square packing fit infinitely many disks into the plane.

The way in which the hexagonal packing beats the square packing is that the former fills about 91% of the plane (more precisely π sqrt(3) / 6) while the latter fills only about 79% of the plane (more precisely π/4). That is, the hexagonal packing has a larger packing fraction. To compute the packing fraction of the square packing, divide the plane into 2r-by-2r squares where r is the radius of the disks.

Each square has area (2r)² = 4r² and contains a disk of area πr², so the packing fraction in each square is (πr²) / (4r²) = π/4 (notice that the radius drops out of the formula). Likewise you can compute the packing fraction of the hexagonal packing by dividing the plane into hexagons.

What about packing spheres in three-dimensional space?

Let’s write points as triples of numbers. If we take all the points (a,b,c) for which a, b, and c are integers, no two of the points are closer than distance 1, so we can put spheres of radius 1/2 around each of them and the spheres don’t overlap. (If two points are at distance d from one another, spheres of radius d/2 centered at the two points will touch but won’t overlap.) The sphere centered at (a,b,c) is tangent to the spheres centered at the six points (a±1,b,c), (a,b±1,c), and (a,b,c±1). This gives us the cubical packing, and it covers about 52% (more precisely π/6) of 3-dimensional space.

Not bad! But it turns out that if you throw out half of the spheres and inflate the rest, you can get a bigger packing fraction.

Here’s how it works. Imagine painting those spheres red and blue, where a sphere centered at (a,b,c) is red if a+b+c is even and blue if a+b+c is odd. Each red sphere touches six blue spheres. If we cull the blue spheres, then no red sphere touches any other sphere, so there’s room for us to expand the radii of the red spheres. By how much? The nearest neighbors of the red sphere centered at (a,b,c) are now the twelve red spheres centered at (a±1,b±1,c), (a±1,b,c±1), and (a,b±1,c±1); these twelve points are all at distance sqrt(2) from the point (a,b,c), so we can expand the radii of the red spheres from 1 to sqrt(2)/2 and the red spheres still won’t overlap (though they will graze each other). This is a win because the volume of a sphere grows like the cube of radius. That is, even though the packing fraction went down by a factor of 2 when we culled the blue spheres, it went up by a factor of (sqrt(2))³ = 2 sqrt(2) > 2 when we inflated the red spheres. So our new culled-and-inflated packing has a bigger packing fraction (bigger by a factor of sqrt(2)), namely π sqrt(2) / 6, or about 74%.

Is this packing the best possible? Johannes Kepler thought it was, and for centuries, nobody could find a better packing but nobody could prove that there wasn’t one. It wasn’t until 2005 that Thomas Hales published a proof that Kepler’s packing fraction can’t be improved.

What about packing spheres in four-dimensional space? What would that even mean? If we relinquish visualization and rely on analogy, we can just define four-dimensional space as the set of quadruples (a,b,c,d) of real numbers, and define the distance between two quadruples (a,b,c,d) and (a’,b’,c’,d’) as

and so on. Then we can use the same trick that worked in three dimensions. Take a hypersphere centered at each point (a,b,c,d) where a,b,c,d are integers, and paint it red or blue according to whether a+b+c+d is even or odd. If we cull the blue hyperspheres and inflate the red hyperspheres by a factor of sqrt(2), we get a packing that’s exactly twice as dense as the 4-dimensional hypercubical packing. This is called the D₄ packing, and it’s believed to be optimal, but nobody has proved it.

You might think you can guess how the rest of the story goes: 5-dimensional packing is even harder than 4-dimensional packing, 6-dimensional packing is harder still, and so on, forever. But no! That’s the thing I find most amazing about this story. For two special values of n, mathematicians have been able to prove that the densest known way to pack n-dimensional hyperspheres is in fact the densest possible way. These exceptional dimensions are n=8 and n=24. The proof for n=8 was found by in 2016 by Maryna Viazovska, and the proof for n=24 was found a week later by Viazovska in collaboration with Henry Cohn, Abhinav Kumar, Stephen Miller, and Danylo Radchenko. Erica Klarreich’s article is a great place to look if you want to know more. Or check out Kelsey Houston-Edwards’ Infinite Series video about sphere-packing.

One thing I love about this topic is that despite the sophistication of the methods used by Viazovska and her collaborators, the subject is still in its infancy. The only dimensions we understand right now are 1, 2, 3, 8, and 24. I’m guessing that the 4-dimensional case is the one somebody will solve next, but who knows?

Next month: Guess Again: The Ehrenfeucht-Mycielski Sequence.