Cannonballs and Honeycombs
Thomas C. Hales

Three Dimensions

We return to three dimensions to discuss the proof of the Kepler conjecture. To avoid the unpleasant boundary effects caused by finite packings, we study sphere packings that extend to all of Euclidean space. Sphere packings are determined by a countably infinite set of parameters, which give the coordinates of the center of each sphere. It was realized in the fifties that it should be possible to prove the Kepler conjecture by looking at a finite number of balls at a time. With this in mind, we discuss finite clusters of balls.

Voronoi

Each ball in our packings should be painted one solid color, from a finite color set. These colors are needed in the details of certain constructions to resolve degeneracies, to make piecewise smooth functions smooth, and to keep domains compact. These colors will help me avoid oversimplifications in my exposition. But by going into details about colors, I would obscure the main lines of the proof of the Kepler conjecture. So now that we have established that the balls are colored, the reader is free to paint all the balls black. Let $t>1$ be a real number. We define a cluster of balls to be a set of nonoverlapping colored 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. These coordinates give a topology on the set $C=C(t)$ of all clusters, making it a compact set. Two clusters with a different number of balls or different colorings lie in different connected components of $C$. The ball at the center of the cluster is contained in a truncated 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. The truncated Voronoi cell $V_t(p)$ is the intersection of the Voronoi cell with a ball of radius $t$ at the origin. We have seen Voronoi cells already in the proof of Thue's theorem, without calling them that. The regular hexagons that appear in the proof of Thue's theorem are the Voronoi cells of the optimal packing. And the large disks, sliced at times to form isosceles triangles, are truncated Voronoi cells $(t=2/\sqrt3)$. Truncation is purely a matter of convenience, making the volumes of Voronoi cells easier to estimate.

Truncated Voronoi cells give a bound on the density of sphere packings. We place every ball of a packing inside its truncated Voronoi cell. Voronoi cells do not overlap; a point of intersection of two closed Voronoi cells, being equidistant from the center of two balls, lies on the boundary of both. The parts of space outside all truncated Voronoi cells do not meet any balls, and have density $0$. The density of the packing is no greater than its densest truncated Voronoi cell. That is, the greatest possible volume ratio of ball to truncated Voronoi cell is an upper bound on the density of a packing.

The Voronoi cells of the face-centered cubic packing are identical rhombic dodecahedra, as shown in Figure \X5. %\footnote"*"{N.B. Insert %a picture of rhombic dodecahedra.} Let $v_\fcc$ be the volume of the rhombic dodecahedron. The density of the face-centered cubic packing is the ratio of the volume of the unit ball to $v_\fcc$: \[{\frac{4\pi/3}{v_\fcc}} ={\frac{\pi}{\sqrt{18}}}\approx 0.74.\] The most distant vertices of the rhombic dodecahedron are $\sqrt{2}$ from the center. Thus, if $t\ge\sqrt{2}$, then truncation has no effect. If $t<\sqrt{2}$, then the truncation cuts into the rhombic dodecahedron and destroys the relation between its volume and our target $\pi/\sqrt{18}$. We fix the truncation at $t=\sqrt{2}$, its smallest useful value. The truncation now fixed, we drop $t$ from the notation and write $V(p) = V_t(p)$.

The minimum volume of a Voronoi cell (either untruncated or truncated at $t=\sqrt{2}$) was recently determined by Sean McLaughlin. For this result, he was awarded the AMS-MAA-SIAM Morgan Prize in January 2000. It confirms a conjecture made by L. Fejes T\'oth nearly 60 years ago.

Theorem (McLaughlin). The volume of the Voronoi cell of a sphere packing of a cluster $p$ is uniquely minimized by a regular dodecahedron of inradius 1.

The cluster of balls that gives the regular dodecahedron is a cluster with one ball at the center and 12 additional balls tangent to the one at the center, placed at the centers of the faces of the regular dodecahedron.

The ratio of the volume of the unit ball to the volume of the regular dodecahedron is an upper bound on the density of a sphere packing. This upper bound is about $0.75$. In two dimensions, the Voronoi cell of minimal volume is the regular hexagon, and it tiles the plane to form the optimal packing. In three dimensions, the Voronoi cell of minimal volume no longer tiles. The locally optimal figure, the dodecahedron, no longer corresponds to the globally optimal figure, the tiling by rhombic dodecahedra. This is the source of complications in the proof of the Kepler conjecture.

We add correction term $f$ to the minimization of the volume of Voronoi cells.

We define a continuous function $f$ on $C$, and consider the minimization problem \[\min \vol(V(p))+f(p).\] We say that $f$ is fcc-compatible if the minimum of $\vol(V(p))+f(p)$ is $v_\fcc$, the volume of the rhombic dodecahedron.

Let $\Lambda$ be the set of centers of the balls in a general packing. For $\lambda\in\Lambda$, consider the cluster of balls centered at distance at most $2t=2\sqrt{2}$ from $\lambda$. Translating the cluster to the origin, we obtain a cluster $p_\lambda$ in $C$. Let $\Lambda_R=\Lambda\cap B_R$ be the set of all centers within distance $R$ of the origin. We say that $f$ is transient if \[\sum_{\lambda\in\Lambda_R} {f(p_\lambda)} = {o(R^3)}.\]

Assume that $f$ is fcc-compatible and transient. By summing \[v_\fcc\le {\vol(V(p))} + {f(p)}\] over $\Lambda_R$, we obtain \[|\Lambda_R|v_\fcc \le {\vol(B_R)}+ {o(R^3)}.\] Divide by $R^3 v_\fcc$ to get the density of a packing inside a ball of radius $R$. \[\frac{|\Lambda_R|}{R^3}\le \frac{4\pi/3}{v_\fcc} + {o(1)} = \frac{\pi}{\sqrt{18}}+{o(1)}.\] Taking the limit as $R\to\infty$, we obtain the bound $\frac{\pi}{\sqrt{18}}$ on the density of the packing.

That shows that the whole proof of the Kepler conjecture follows if a transient fcc-compatible function $f$ can be found. To establish fcc-compatibility, an extremely difficult nonlinear optimization problem on $C$ must be solved. We select the function $f$ with transience in mind, so that it is automatically satisfied.