Sphere Packing

Sphere packing is the problem of arranging non-overlapping spheres within some space, with the goal of maximizing the combined volume of the spheres. In the classical case, the spheres are all of the same sizes, and the space in question is three-dimensional space (e.g. a box), but the question can be extended to consider different-sized spheres, higher (or lower) dimensions, or different types of shapes (e.g. a tetrahedron).

The problem is famous for being very natural and seemingly simple, but very difficult to even approach in a rigorous sense. In fact, it took nearly 400 years for the problem to be solved even in the three-dimensional case, and that was only possible through the use of massive computing power; the resulting data comprises over three gigabytes.

Sphere packing has surprising application to error correcting codes, making the problem especially relevant in recent times.

The problem of sphere packing is notable for being quite visible in everyday life; many grocery stores, for instance, stack fruit (oranges in particular) in a pyramidal pattern that illustrates a possible sphere packing.

In fact, the origin of the problem is quite similar: Sir Walter Raleigh, on one of his expeditions, asked a mathematician friend what the most efficient way of stacking the cannonballs he had on the ship was. The mathematician realized he couldn't answer the question, and passed it along to Johannes Kepler (better known for his work in astronomy).

Kepler conjectured that the "obvious" packing--the orange-stacking method--was in fact the best possible, and supported this by comparing it to some other basic strategies. However, approaching the problem proved difficult, and it was not until Gauss that major progress was made.

Gauss's major result was that the orange-stacking method was the best possible amongst lattice packings, meaning intuitively packings that repeat in a highly regular way. However, there are non-lattice packings that are even optimal in some cases, so this didn't prove the orange-stacking method was the best possible amongst all packings.

A (very) irregular, but optimal, packing of 15 circles into a square

The next major breakthrough came in 1953 when Laszlo Toth reduced the problem to a (very) large number of specific cases. This meant that, like the four color theorem, it was possible to prove the theorem with dedicated use of a computer. Still, coming up with the strategy to perform the computation took another 41 years when Hales developed an algorithm that he spent four more years executing. A 250-page paper and over 3 gigabytes of data later, Kepler's conjecture was finally proved.

The problem of sphere packing is best understood in terms of density: rather than trying to determine how many spheres can fit into a specifically sized box, the more interesting question is how much of 3-D space can be filled with spheres (in terms of volume). More formally, the density of a sphere packing in some finite space is the fraction of the space that can be filled with spheres. As the last section showed, this can lead to strange optimal tilings when the space is of a specific size, so the more interesting question arises when considering how the density changes as the space gets bigger and bigger; in a formal sense, the goal is to find the limit of the densities of the optimal sphere packing of an $n \times n \times n$ box, as $n$ tends to infinity.

A natural strategy is to choose a "small" arrangement and repeat it over and over again, attempting to do something similar to tessellating the plane. More formally, a lattice arrangement (or a regular arrangement) is one where the centers of the spheres require only $n$ vectors to define completely (in the $n$-dimensional case; in the case of spheres, $n=3$). These arrangements are periodic, meaning that they repeat.

An irregular arrangement is one in which the centers of the spheres do not form a lattice; in some sense, they appear to be "randomly" spread about.

Because of the symmetry and regularity, lattice arrangements are much easier to analyze than irregular ones. However, especially as irregular arrangements are optimal for some small cases, the possibility that one is optimal in the limit case cannot be immediately ruled out.

The simplest version of the problem is the reduction to two dimensions, where the goal is to tile the plane with circles in the such a way that maximizes density.

A very natural approach is to arrange the circles in a hexagonal pattern, as shown:

where the centers of the circles essentially tessellate the plane with equilateral triangles. It is worth noting that this is an example of a lattice arrangement, as it is completely defined by the vectors $(0,1)$ and $\left(\frac{1}{2},\frac{\sqrt{3}}{2}\right)$ (this means that any linear combination of these vectors is the center of a circle).

Calculating the density of this arrangement is rather straightforward: since the hexagon shown is able to tessellate the plane, the portion of the hexagon that the circles take up is also the density of the circles in the plane. The same holds true for an equilateral triangle formed by the centers, which is perhaps easier to analyze.

The density of the hexagonal circle arrangement is

$$\frac{\pi}{2\sqrt{3}} \approx 0.9069.$$

Interestingly, this is a low number compared to other shapes; for instance, the pentagon, which does not tessellate the plane, has a packing density of at least $\frac{5-\sqrt{5}}{3} \approx 0.9213$: However, it is not the "worst" shape to tile the plane with. Though the exact worst shape is not known, the smoothed octagon is conjectured to be the worst: The smoothed octagon is formed by replacing each corner with part of a hyperbola

at a density of $$\frac{8-4\sqrt{2}-\ln{2}}{2\sqrt{2}-1} \approx 0.9024.$$

Surprisingly, this turns out to be a very difficult problem to solve as well, despite the clear intuition of which arrangement is best. It was not until 1940 that the hexagonal tiling was proved to have maximum density, though it was shown to have highest density among all lattice tilings as early as 1773.

Proving that the hexagonal tiling is optimal requires some definitions, but is not difficult in principle. Given a set of points in the plane, a triangulation is a set of triangles such that

• every pair of triangles intersect at a single point, a single edge, or not at all;
• the vertices of the triangles form exactly the original set of points.

A Delaunay triangulation is one in which no point in the set lies inside a triangle in the triangulation.

A Delaunay triangulation does not necessarily exist for all sets of points, nor is it necessarily unique. But in this case, the set of points is the set of centers of the circles in a maximal optimal packing (and thus have a pairwise distance of at least 2), and this is enough to guarantee that a Delaunay triangulation exists. Here, a maximal optimal packing means no points can be added to the set; otherwise, the density could be increased.

A Delauney triangulation, from https://en.wikipedia.org/wiki/Delaunaytriangulation

In a Delaunay triangulation of a maximal circle packing, the largest angle $\theta$ of any triangle satisfies

$$\frac{\pi}{3} \leq \theta < \frac{2\pi}{3}.$$

---

Proof: Since the angles of a triangle sum to $\pi$, the left-hand inequality is obvious; the maximum of a set must be at least its average.

Now, suppose $\theta \geq \frac{2\pi}{3}$, and let $A$ be the smallest angle. Then $\sin A<\sin\frac{\pi}{3}=\frac{1}{2}$, and since $\overline{BC} \geq 2$, this implies $$2R = \frac{BC}{\sin A} \geq \frac{2}{\ \ \frac{1}{2}\ \ }=4,$$ implying that $R \geq 2$. Here $R$ is the circumradius of $ABC$.

However, this implies that the circumcenter $O$ of $ABC$ can be added to the set, contradicting its maximality. So, $\theta<\frac{2\pi}{3}$ as desired. $_\square$

Now, consider the portion of a triangle $ABC$ that is taken up by circles. The circle at $A$ takes up $\pi \cdot \frac{\angle A}{2\pi} = \frac{1}{2}\angle A$ area, and analogously the circles at $B,C$ take up $\frac{1}{2}\angle B, \frac{1}{2}\angle C$ area. So the density of the triangle is

$$\frac{\frac{1}{2}\angle A + \frac{1}{2}\angle B + \frac{1}{2}\angle C}{[ABC]}=\frac{\frac{\pi}{2}}{[ABC]}.$$

But $[ABC]=\frac{1}{2}\overline{AB}\overline{BC}\sin\angle B \geq \frac{1}{2} \cdot 2 \cdot 2 \cdot \frac{\sqrt{3}}{2}=\sqrt{3}$, so the density of the triangle is at most $\frac{\pi}{2\sqrt{3}}$.

However, the density of the entire plane is a weighted sum of the density of the triangles, each of which is at most $\frac{\pi}{2\sqrt{3}}$. Hence the density of the entire plane is also at most $\frac{\pi}{2\sqrt{3}}$.

Furthermore, equality holds only when $\overline{AB}=\overline{BC}=2$ and $\angle B=\frac{\pi}{3}$ for all triangles, meaning that every triangle in the triangulation is equilateral. This means that the hexagonal lattice is optimal, as desired.

In the 3-D case, again the "natural" strategy wins out, but it is significantly more difficult to demonstrate. This natural strategy works as follows:

• Consider a plane with an arrangement of spheres on it, arranged in a hexagonal lattice (as in the 2-D case).
• For any collection of three touching spheres, place a sphere on top of the space between the three spheres. Repeat this "everywhere" above the first plane, forming another plane of spheres.
• Repeat this process infinitely in both directions.

At the third step, there is a choice to be made: the spheres on layer 3 can be placed in the same positions (but moved upwards, obviously) as the spheres on layer 1, or they can offset slightly so that the spheres on layer 4 will be placed in the same positions as layer 1 (or 2, potentially). This means that there are three different hexagonal planes of spheres. If they are called A, B, and C, any sequence of As, Bs, and Cs such that no adjacent letters are the same (e.g. "ABCABC...", "ABCBABCBA...", etc.) will result in an analogously tightly-packed structure, and in fact all such packings are optimal.

Again, the density is not too difficult to calculate, but the third dimension makes it somewhat more difficult to visualize. Intuitively, the density of the 3-D plane is the same as the density of a tetrahedron of side length 2, with spheres of radius 1 at all four vertices. This density is as follows:

The density of the optimal sphere packing is

$$\frac{\pi}{3\sqrt{2}}.$$

Extremely recently (as of 2016), the sphere packing problem has been solved in even higher dimensions: 8 and 24. These may seem like arbitrary numbers, but in fact they are not; precisely these dimensions allow for exactly the extra structure needed to tightly pack additional "oranges" into the extra dimensions in such a way that the fit is "tight." This sounds ambiguous largely because it is; visualization in 4 dimensions is essentially impossible, let alone 24.

Amusingly, this result improves on a prior estimate that showed the best possible sphere packings were at most $10^{-25}$ denser than the best-known bounds. That is, the error in the best-known packings was at most

$$0.0000000000000000000000000001\%,$$

which is a remarkably tight bound.

Sphere packing is also highly correlated with designing error correcting codes, as the centers of spheres with radius $t$ correspond to codewords of a $2t+1$ error correcting code. Thus, efficient sphere packing can be leveraged to discover efficient error correcting codes, and indeed lattice sphere packings correspond to linear codes, and the $G_{24}$ (or Golay code) is analogous to the Leech lattice in 24 dimensions (which, as above, was recently proved to be optimal).

• Tessellation of the Plane