1  Packing oranges the most efficient way

The mathematical community was greatly excited in August 1998 by a dramatic email message sent from a Munich Internet Cafe and rapidly forwarded all over the world, announcing ``a solution to the Kepler Conjecture, the oldest problem in discrete geometry .... the proof relies extensively on methods from the theory of global optimization, linear programming and interval arithmetic ... well over 250 pages ... computer files require over three gigabytes of space for storage.'' In the nature of things, the proof took some years to be checked (by a panel of twelve referees) but it has survived scrutiny, and the result is now called:

Kepler's Theorem  The density of any sphere packing in 3-dimensional space is at most p/Ö[18], which is the density of Kepler's ``FCC'' packing.

Johannes Kepler had asserted in the early 1600's that no packing could improve on the Face-Centred Cubic packing. which is the one that arises from the way orange-vendors pack them in pyramids, as pictured above.

Why should such an apparently simple statement take four centuries to prove? Gauss proved in the early nineteenth century that it is the best of all ``lattice packings'' (where the centres form a nice regular lattice of dots), but packings need not be like this. There is good reason to believe that in the corresponding problem in sufficiently high dimensional spaces the best packing will not be a lattice packing. Also, there are non-lattice packings as good as FCC!

Definitions: What do we mean by ``as good as'' and ``density of sphere packing''? It will help to read the article in 6.3 on estimating pi, which talks about circle packings in 2-dim and gives the density of these two packings A & B as p/4,  p/Ö[12], respectively; packing C has much lower density:

Generally, a sphere packing of \Rⁿ is a collection of disjoint (non-overlapping) n-dimensional spheres of unit radius, and we are interested only in saturated packings, in which there is no room for adding any additional spheres. The density of a packing in a finite region of \Rⁿ is the proportion of the volume (area in \R²) occupied by spheres. The density of a packing of \Rⁿ is defined to be the limit as r® ¥ of the density of the packing in the sphere with radius r centred at the origin.

There was a major step forward in 1953, when László Fejes Tóth reduced the problem to analysing a finite number of sphere `clusters' that can arise in packing spheres, and then putting them together to fill up the whole of space. To do this Tóth suggested looking at how a given sphere packing determines a partitioning of space called the Voronoi Decomposition.

The Voronoi Cell of a sphere in the packing is the set of points closer to it than to any other sphere in the packing - they are therefore polyhedra (in 3-dim) or polygons (in 2-dim) containing unit spheres/circles. Here is a picture of the Voronoi Decomposition of a packing in 2-dim.

The density of a Voronoi Cell is the ratio of the volume of the unit sphere to the volume of the cell. The only cell that occurs in the 3-dim FCC packing is the rhombic dodecahedron; its volume is 4Ö2 and its density is [(p)/(Ö[18])]. The densest Voronoi Cell in 2-dim is the regular hexagon. But this cell is a tiling of the plane and so the best packing will be the circles fitted into each hexagonal tile, giving a proof of Thue's result in the next article. Tóth conjectured in 1943 that the densest Voronoi Cell in 3-dim would be the regular dodecahedron (density approx. 0.755), but this was finally proved only in 1998 by an undergraduate student at the University of Michigan, Sean McLaughlin. There are a number of other Voronoi Cells in 3-dim with densities higher than 0.7405. The trouble is that these all fail (like the dodecahedron) to partition space, which is why the Kepler theorem is so hard to prove.

The breakthrough came at last in the 1990's, when a mathematician at the University of Michigan called Tom Hales thought of using the dual decomposition to the Voronoi, called the Delaunay Decomposition (pictured above), and realized in November 1994 that it was much more efficient to use a combination of decompositions than to stick rigidly to one kind. The story gets highly technical from this point, so we omit the mathematical details, but should point out that high-powered computers and better methods of linear programming were crucial to the solution. Tom Hales and his doctoral student Samuel Ferguson (who actually got his doctorate in 1997 for a thesis tackling a particularly fiendish part of the proof) reached their goal in August 1998, and sent out that triumphant email message to the mathematical community. As a bonus, they also showed that HCP is the only other packing as good as the FCC both locally and globally, and also that any packing which is globally as good as FCC is locally like FCC or HCP for a sufficiently large proportion of space.

Some Related Open Problems

1.  Find the optimum packing density for other 3-dim solids. (Only a few are known: cuboids, obviously; infinitely long cylinders; chipped rhombi-dodecahedons.)
2.  Find the optimum sphere packing for dimensions > 3.
3.   In 1956 Van der Waerden and Leech proved that the maximum number of (unit) spheres that a single sphere could touch in 3-dimensions is 12. What is the maximum in 4-dimensions?
4.  What is the minimum volume that can be contained by n planes tangent to a sphere in 3 dimensions?

Further Reading:
· C.Zong, Sphere Packings, Springer-Verlag, NY 1999.
· T.Hales, Cannonballs and Honeycombs, Notices of the American Maths Soc., Vol.4 No. 4, pp 440-9.
· Various articles by T.Hales & S. Ferguson: LANL e-print archive math.MG/9811071,9811077-8;http://xxx.lanl.gov/

2  The Circle-Packing Theorem