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 facecentered 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
facecentered 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 twodimensional
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 largescale nonlinear optimization problem to be
solved. Nonlinear optimization problems of this size can be
hopelessly difficult to solve rigorously. Fortunately, the
largescale 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.
