Cannonballs and Honeycombs
Thomas C. Hales with Overview by Paul Gartside

An Overview

At the turn of the last Century the famous mathematician Hilbert presented a list of 23 mathematical problems. The 18th of these problems, Kepler's Conjecture, can be phrased, Is there a better stacking of oranges than the pyramids found at the fruit stand? In pyramids, the oranges fill just over $74$% of space. Can a different packing do better?

In August 1998, nearly 400 years after Kepler first made his conjecture, Thomas Hales, with the help of his graduate student, Samuel Ferguson, confirmed the conjecture, and solved Hilbert's 18th problem.

These pages give the broad outlines of the proof of the Kepler conjecture in the most elementary possible terms. Along the way the history of the Kepler conjecture is sketched.

• Hilbert: It seems `obvious' that Kepler's conjecture is correct. Why is the gulf so large between intuition and proof? "Geometry taunts and defies us...."
• Harriot and Kepler: The genesis of Kepler's conjecture. The pyramid stacking of oranges is known to chemists as the face-centered cubic packing. It is also known as the cannonball packing, because it is commonly used for that purpose at war memorials.

  Theorem (Kepler conjecture). No packing of balls of the same radius in three dimensions has density greater than the face-centered cubic packing.

• Gauss: The first to prove anything about the Kepler conjecture, was Gauss.
• Thue - Down to 2 dimensions: A typical mathematical gambit, is to gain insight into a hard problem by first tackling a simplified version. Thue solved the 2 dimensional analog of Kepler's problem in 1890. The two-dimensional version of Kepler's conjecture asks for the densest packing of unit disks in the plane.
• Back to 3 dimensions - Voronoi: Implicit in the proof of Thue's theorem is the idea of a Voronoi cell.

  Let $t>1$ be a real number. We define a cluster of balls to be a set of nonoverlapping balls around a fixed ball at the origin, with the property that the ball centers have distance at most $2t$ from the origin. A cluster of $n$ balls is determined by the $3n$ coordinates of the centers. The ball at the center of the cluster is contained in a Voronoi cell. By definition, the Voronoi cell is the set of all points that lie closer to the origin than to any other ball center in the cluster.

  Voronoi cells give a bound on the density of sphere packings.

• Fejes Toth: The bound given by Voronoi cells is not sufficient, and a correction term must be introduced. Toth, in 1953, was the first to suggest a potential correction term. It remains unclear if his proposed correction terms have all the requisite properties. But it became clear that Kepler's problem could be solved via an optimization problem in a finite number of variables - and this optimization might be performed by computer.
• Combinatorial Structures: The space of clusters is so complicated that it is not possible to minimize the correction term directly. Instead to each cluster is assigned a planar graph that identifies the most prominent geometrical features of the cluster. There are about 5000 planar graphs that need to be dealt with.
• 5000 Cases: In most cases bounds derived just from the graph were sufficient. But in some cases, the crude combinatorial bounds were not good enough. One case turned out to be far more intricate than the others.
• Linear Programs: For each case, there is a large-scale nonlinear optimization problem to be solved. Nonlinear optimization problems of this size can be hopelessly difficult to solve rigorously. Fortunately, the large-scale structure of the problem is linear and can be solved by linear programming methods.

Honeycombs

A related problem, of even greater antiquity, is: What is the most efficient partition of the plane into equal areas? The honeycomb conjecture asserts that the answer is the regular hexagonal honeycomb.

After completing the proof of the Kepler conjecture, Thomas Hales turned his attention to the honeycomb conjecture. Somewhat to his surprise he obtained a (relatively) short solution without resort to computers.

Theorem (Honeycomb conjecture). Any partition of the plane into regions of equal area has perimeter at least that of the regular hexagonal honeycomb tiling.

• Pappus: In 36BC, in a book on agriculture, the Roman scholar Marcus Varro, presented the honeycomb conjecture not as a conjecture but as a proven fact. But the `proof', as recorded by Pappus, is incomplete.
• Kelvin and the Millenial List: The 3 dimensional version of the efficient partition problem is:

  How can space be divided into cavities of equal volume so as to minimize the surface area of the boundary?

  This is Hale's submission for a millenial `Hilbert problem list'

• References