Devlin's Angle

September 1998

Kepler's Sphere Packing Problem Solved

A four hundred year mathematical problem posed by the famous astronomer Johannes Kepler has finally been solved. Mathematician Thomas Hales of the University of Michigan announced last month that after six years effort, he had proved that a guess Kepler made back in 1611 was correct.

The problem asks what is the most efficient way to pack equal-sized spheres together in a large crate. Should you pack them in identical layers, one on top of the other, with each sphere in one layer sitting right on top of the sphere directly beneath it? Or can you get more spheres into the box if you stagger the layers, the way greengrocers the world over stack oranges, so that the oranges in each higher layer sit in the hollows made by the four oranges beneath them? (The formal term for this orange-pile arrangement is a face-centered cubic lattice.) More generally, what is the most efficient packing of all?

For a small crate, the answer can depend on the actual dimensions of the crates and the spheres. But for a very large crate, you can show, as Kepler did, that the orange-pile arrangement is by far the more efficient of the two mentioned above, and indeed seems to be more efficient than any other possible arrangement.

The general problem as considered by Kepler and subsequent mathematicians is formulated not in terms of the number of spheres that can be packed together but the density of the packing, i.e., the total volume of the spheres divided by the total volume of the container into which they are packed. Since the main interest is in the pattern of the packing, rather than the shape or size of the container, the problem is further generalized by defining the density of a packing (pattern) as the limit of the densities of individual packings using that pattern for cubic crates, as the volume of the crates approaches infinity.

For example, the symmetrical packing gives you a density of pi/6 (about 0.52), the orange-pile packing gives you a density of pi/3sqrt(2) (approximately 0.74).

Kepler believed that the face-centered cubic lattice was the most efficient of all arrangements (in terms of the density of the packing arrangement), but was unable to prove this. So were countless succeeding generations of mathematicians.

Though it never achieved the general fame outside of mathematics as Fermat's Last Theorem, proved four years ago by British mathematician Andrew Wiles 350 years after it had been posed, Kepler's Sphere Packing Conjecture was very similar, in that it was ridiculously easy to understand the problem but seemed fiendishly difficult to solve. Moreover, both problems had subtle difficulties that led a number of mathematicians to believe they had found a solution that subsequently turned out to be false. Most recently, in 1993, a highly-respected mathematician at the University of California at Berkeley produced a complicated proof of the Kepler Conjecture which, after many months of debate, most mathematicians decided was incorrect.

Major progress on the problem was made in the 19th century, when the legendary German mathematician and physicist Karl Friedrich Gauss managed to prove that the orange-pile arrangement was the most efficient among all "lattice packings." A lattice packing is one where the centers of the spheres are all arranged in a "lattice" (a regular three-dimensional grid -- think of a three-dimensional analogue of a lattice fence).

But there are non lattice arrangements that are almost as efficient than the orange-pile, so Gauss's result did not solve the problem completely.

The next major advance came in 1953, when a Hungarian mathematician, Laszlo Toth, managed to reduce the problem to a huge calculation involving many specific cases. This opened the door to solving the problem using a computer.

In 1994, Hales worked out a five-step strategy for solving the problem along the lines Toth had suggested. Together with his graduate student Samuel Ferguson, Hales started work on his five-step program.

By 1996, Hales was giving talks at universities describing the progress he had made, and speculating that with about two more years work, he expected to have cracked the problem.

Last week, Hales announced that he had succeeded, and posted the entire proof on the Internet. You can see the proof for yourself at Hales' web site. But be warned: The proof involves 250 pages of text and about 3 gigabytes of computer programs and data. To follow Hales' argument, you will have to download his programs and run them.

As Hales himself admits, with a proof this long and complex, involving as it does a great deal of computation, it will be some time before anyone can be absolutely sure it is correct. By posting everything on the world wide web, Hales has, in effect, challenged the entire mathematical community to see if they can find anything wrong. If no one can, then eventually everyone will agree that the proof is correct. At the moment, experts who have visited the web site and looked through the material think that it looks convincing.

The situation is reminiscent of the solution in 1976 of the Four Color Problem by Kenneth Appel and Wolfgang Haken. Their proof that four colors are all you need to color any map drawn on a plane, no matter how complicated (so that countries having a common border are colored differently) also involved a mixture of ordinary mathematical reasoning and masses of computation. On that occasion, it was several months before there was general agreement that the proof was correct. But that was before we had the web. With any mathematician anywhere in the world now able to get immediate access to Hales' entire proof and all the computer programs, we can expect a consensus to emerge much quicker.

What use is the new result, you might ask? Well, the problem actually began as an applied problem. A military problem, in fact. Sir Walter Raleigh had asked a mathematician friend to give him a simple mathematical formula for calculating the number of cannonballs he had in the piles on the deck of his ship. The mathematician, Thomas Harriot, gave Raleigh his formula, but realized that he did now know whether the cannonballs were being stacked in the most efficient fashion. He passed the problem on to Kepler.

What about modern applications? Well, knowing that Kepler was correct probably has no direct applications in itself. But the whole topic of the efficient packing of spheres is a crucial part of the mathematics that lies behind the error-detecting and error-correcting codes that are widely used to store information on compact disks and to compress information for efficient transmission around the world. In today's information society, you can't get a more significant application than that. So who can say what might come out of any advance in our understanding of sphere packing.

And let's not forget that, around the world, thousands of greengrocers and supermarket assistants can now rest assured that the way they arrange the oranges has now been proved mathematically to be the most efficient.

- Keith Devlin

Devlin's Angle is updated at the beginning of each month.
Keith Devlin ( [email protected]) is Dean of Science at Saint Mary's College of California, in Moraga, California, and a Senior Researcher at Stanford University. Devlin describes Kepler's sphere packing problem in his book Mathematics: The Science of Patterns, published in paperback by W. H. Freeman in 1996.