By Jonathan Kujawa
In 1611 Johannes Kepler wrote a scientific essay entitled De Nive Sexangula; commonly translated as “On the Six-Cornered Snowflake”. It was the first investigation into the nature of snowflakes and what we'd now call crystallography. Since he was a gentleman and a scholar back when you could be such a thing without being ironic or a hipster, Kepler gave the essay as a New Year's gift. As Kepler wrote on the title page:
To the honorable Counselor at the Court of his Imperial Majesty, Lord Matthaus Wacker von Wackenfels, a Decorated Knight and Patron of Writers and Philosophers, my Lord and Benefactor.
As the title suggests, Kepler's main concern was the question of why snowflakes are almost always six-pointed. In his essay Kepler ponders the shape of honeycombs, flowers, Platonic solids, and the Fibonacci Sequence. The shape of a snowflake doesn't seem to be imposed from the outside (as a scientist, “God did it” doesn't quite cut it as an explanation). He speculates, then, that there must be an internal cause for the six points. Nowadays we'd call it an emergent property of the snowflake.
Kepler next imagines that when moisture freezes it forms little “beads of vapor”. If so, it must be how these beads are arranged which gives rise to the shape of a snowflake. Thus Kepler is led to consider how one may pack together beads. In particular, he considers the question of how they could be packed together as tightly as possible. That is, how can we pack spheres together in such a way as to minimize the volume of the space between them?
Kepler points out that for spheres to be tightly packed in three dimensions each layer should have no extra space. This is a handy observation since the two-dimensional, single layer case is easier to think about. As he illustrates in his essay [2], by being a little clever (B) you can pack the beads together more tightly than if you just do the first thing which comes to mind (A). It's not so hard to verify that (B) is the tightest packing you can do in two dimensions. A partial verification was given by Thue at the beginning of the twentieth century and a complete proof by Tóth in the 1940s.
It turns out that Kepler already had sphere packing on his mind. His friend Thomas Harriot was charged by Sir Walter Raleigh with the task of finding the most efficient way to pack cannonballs onto ships. Several years before the snowflake essay, Kepler and Harriot exchanged letters on the subject.
Giving it some thought, Kepler concludes in his snowflake essay that the most efficient packing of spheres in three dimensions is the one you'd use if you yourself wanted to make a neat pile of oranges. You would make a pyramid where each level is a square made of offset balls (as in (B)), and where one layer is stacked on the next by setting each ball in the divot made by four adjacent balls on the previous level. Kepler again provides us with an illustration of what he has in mind [2]. It's not too hard to calculate that the average density of Kepler's packing is (π√2)/6 (approximately 74%). That is, that 74% of the volume is spheres and 26% is the empty space between the spheres.
In his essay Kepler claims that this is the densest possible way to pack spheres in three dimensions. Of course it's one thing to make a claim, but it's something else entirely to prove it. You have to somehow prove that every one of the countless other possible packings is worse (or at least no better).
We had to wait 200 years for the great mathematician Gauss to make progress towards proving Kepler's conjecture. Gauss proved that Kepler's packing is the densest possible if you only consider packings which have a regular, repeating pattern. These are called regular or lattice packings.
At first glance you might think that this closes the case. After all, surely some non-repeating pattern of stacking must be full of gaps and holes? Indeed, according to Wikipedia, if you randomly pile up a bunch of cannonballs, the average density will be in the neighborhood of 65%.
But, on the other hand, assuming the arrangement is regular is awfully restrictive. After all, in two dimensions there are only 17 truly distinct regular wallpaper patterns [3]. When we allow ourselves to have non-regular arrangements in two dimensions we discover some truly wonderful new things. It turns out we use a handful of tiles to cover the entire plane without gaps yet the pattern never repeats! The most famous of these so-called aperiodic tilings are the Penrose tilings. In the 1970s Roger Penrose showed that you can create these never repeating tiling patterns using just two tiles. Notice how the pattern never quite repeats in this example of a Penrose tiling from the AMS [4]:
With aperiodic tilings in mind it comes as no surprise that even if you eliminate the obviously bad sphere packings there are still a horrifyingly large number of possible aperiodic ways to tightly pack Kepler's beads of vapor. In the 1950s Fejes Tóth showed that, while there were a staggeringly large number of aperiodic stacks to consider, it was possible to get it down to a finite number.
That's the good news. The bad news is that there were a Brobdingnagian number of possibilities. A decade ago Thomas Hales and Samuel Ferguson managed to reduce the problem enough that a computer was able to check all he possibilities. This caused quite the stir in the math community. We like it when we can understand and check an argument with our own brains. It gives us confidence the result is correct and it hopefully helps us to understand why the result is true [5]. An exhaustive computer check is hard to verify and awfully unsatisfying.
Hales and collaborators were able to take care of the first objection. In a ten year project called Flyspeck they developed a formal proof of the Kepler conjecture. As of August 10, 2014, we know beyond doubt that Kepler was right.
Kepler told us the most efficient packing of spheres in two and three dimensions. What about four and higher dimensions? This isn't just an academic exercise. String theory tells us we live in an eleven dimensional world. And as we saw here at 3QD nearly a year ago, doing Big Data means working in a high dimensional world where you not only track the x,y, and z of position, but time, temperature, cost, movie preferences, and countless other bits of data. In a recent blog post, Evelyn Lamb explains how sphere packing in high dimensions plays a role in modern error correcting codes.
Given how hard it was to verify Kepler's conjecture in three dimensions, you'd rightly guess that we don't know the best sphere packings in higher dimensions. At least until recently. In March a preprint by Maryna Viazovska was released in which she proved that the densest packing of spheres in eight dimensional space has average density π4/384 (approximately 25%). In a followup paper with Cohn, Kumar, Miller, and Radchencko they adapt her methods and determine the densest sphere packing in twenty-four dimensions.
Why 8 and 24 dimensional space? What makes them special is that there are known sphere packings (the E8 lattice and the Leech lattice, respectively) which are very dense. Even better, they have their origins in other areas of mathematics and we know more than average about their properties. In particular, they have close connections to modular forms. These are amazing functions which normally pop up in number theory. We saw them when we talked about Fermat's Last Theorem (here) and Gauss's Eureka Theorem (here). This remarkable link to number theory lets Viazovska and company prove that the E8 and Leech lattices are indeed the densest sphere packings in dimensions 8 and 24. This is beautiful mathematics.
What about dimension four, or five, or 2016? There are upper and lower bounds on the density in various cases, but it's still an open question to determine the optimal sphere packing in dimensions different that 1, 2, 3, 8, and 24. As a word of warning, the evidence suggests that in other dimensions the optimal packing won't be a nice lattice. For example, in ten dimensional space there is an example which is more dense than any known lattice packing. Dimensions 8 and 24 are probably atypical.
There is one other counterintuitive fact about spheres I can't help but mention. If you are like me, then based on our experiences in two and three dimensions, we think of circles and spheres as being nearly as large as the smallest square or cube which contains them. But this is actually wrong. A circle fit tightly into a square covers 78% of the area inside the square. A sphere inside a cube covers only 52% of the volume of the cube. In ten dimensions, 99+% of the volume of a cube is outside the biggest sphere you can fit inside the cube. And it only gets worse as the dimension climbs. John Cook has a blog post where he talks about this peculiar phenomenon. Our intuition is stunted by everyday experience. It is a dangerous guide in higher dimensions.
[1] Wilson Bentley took absolutely amazing photos of snowflakes in the late 1800s. See here for more about him and his photos.
[2] Image from the copy of De Nive Sexangula in the University of Oklahoma History of Science Collection. Original copies of Kepler's essay are incredibly rare. Only a dozen or so exist in North America. The OU history of science collection is one of the best in the country and De Nive Sexangula is only one of its many treasures.
[3] Here we are counting two wallpaper patterns the same if they have the same collection of symmetries. This collection is called a wallpaper group and there are only 17 truly distinct wallpaper groups. There is a nifty webpage called Escher Sketch which lets you use the wallpaper groups (when you click on p4g or p31m you're choosing a wallpaper group) to create cool Etch-a-Sketch style designs.
[4] See here for very nice article by the AMS on Penrose tilings. It includes a Java applet if you want to create Penrose tilings of your own!
[5] Maybe the confidence is misplaced; after all, to err is human.