In mathematics, the theory of finite sphere packing concerns the question of how a finite number of equally-sized spheres can be most efficiently packed. The question of packing finitely many spheres has only been investigated in detail in recent decades, with much of the groundwork being laid by László Fejes Tóth.

The similar problem for infinitely many spheres has a longer history of investigation, from which the Kepler conjecture is most well-known. Atoms in crystal structures can be simplistically viewed as closely-packed spheres and treated as infinite sphere packings thanks to their large number.

Sphere packing problems are distinguished between packings in given containers and free packings. This article primarily discusses free packings.

Packing and convex hulls

Convex hull in blue

In general, a packing refers to any arrangement of a set of spatially-connected, possibly differently-sized or differently-shaped objects in space such that none of them overlap. In the case of the finite sphere packing problem, these objects are restricted to equally-sized spheres. Such a packing of spheres determines a specific volume known as the convex hull of the packing, defined as the smallest convex set that includes all the spheres.

Packing shapes

There are many possible ways to arrange spheres, which can be classified into three basic groups: sausage, pizza, and cluster packing.^[1]

• 
  Sausage packing
• 
  Pizza packing
• 
  Cluster packing

Optimal packing

The empty space between spheres varies depending on the type of packing. The amount of empty space is measured in the packing density, which is defined as the ratio of the volume of the spheres to the volume of the total convex hull. The higher the packing density, the less empty space there is in the packing and thus the smaller the volume of the hull (in comparison to other packings with the same number and size of spheres).

To pack the spheres efficiently, it might be asked which packing has the highest possible density. It is easy to see that such a packing should have the property that the spheres lie next to each other, that is, each sphere should touch another on the surface. A more exact phrasing is to form a graph which assigns a vertex for each sphere and connects vertices with edges whenever the corresponding spheres if their surfaces touch. Then the highest-density packing must satisfy the property that the corresponding graph is connected.

Sausage catastrophe

With three or four spheres, the sausage packing is optimal. It is believed that this holds true for any ${\displaystyle n}$ up to ${\displaystyle 55}$ along with ${\displaystyle n=57,58,63,64}$.^[1][2] For ${\displaystyle n=56,59,60,61,62}$ and ${\displaystyle n\geq 65}$, a cluster packing exists that is more efficient that the sausage packing, as shown in 1992 by Jörg Wills and Pier Mario Gandini.^[2][3] It remains unknown what these most efficient cluster packings look like. For example, in the case ${\displaystyle n=56}$, it is known that the optimal packing is not a tetrahedral packing like the classical packing of cannon balls, but is likely some kind of octahedral shape.^[1]

The sudden transition in optimal packing shape is jokingly known by some mathematicians as the sausage catastrophe (Wills, 1985).^[4] The designation catastrophe comes from the fact that the optimal packing shape suddenly shifts from the orderly sausage packing to the relatively unordered cluster packing and vice versa as one goes from one number to another, without a satisfying explanation as to why this happens. Even so, the transition in three dimensions is relatively tame; in ${\displaystyle d=4}$ dimensions the sudden transition is conjectured to happen around 377000 spheres.^[1]

For dimensions ${\displaystyle d\leq 10}$, the optimal packing is always either a sausage or a cluster, and never a pizza. It is an open problem whether this holds true for all dimensions. This result only concerns spheres and not other convex bodies; in fact Gritzmann and Arhelger observed that for any dimension ${\displaystyle d\geq 3}$ there exists a convex shape for which the closest packing is a pizza.^[1]

Parametric density and related methods

While it may be proved that the sausage packing is not optimal for 56 spheres, and that there must be some other packing that is optimal, it is not known what the optimal packing looks like. It is difficult to find the optimal packing as there is no "simple" formula for the volume of an arbitrarily shaped cluster. Optimality (and non-optimality) is shown through appropriate estimates of the volume, using methods from convex geometry, such as the Brunn-Minkowski inequality, mixed Minkowski volumes and Steiner's formula. A crucial step towards a unified theory of both finite and infinite (lattice and non-lattice) sphere packings was the introduction of parametric densities by Jörg Wills in 1992. The parametric density takes into account the influence of the edges of the packing.^[7]

The definition of density used earlier concerns the volume of the convex hull of the spheres (or convex bodies) ${\displaystyle K}$:

${\displaystyle \delta (K,C_{n})={\frac {nV(K)}{V(C_{n}+K)}}}$

where ${\displaystyle C_{n}}$ is the convex hull of the ${\displaystyle n}$ midpoints ${\displaystyle c_{i}}$ of the spheres ${\displaystyle K_{i}}$ (instead of the sphere, we can also take an arbitrary convex body for ${\displaystyle K}$). For a linear arrangement (sausage), the convex hull is a line segment through all the midpoints of the spheres. The plus sign in the formula refers to Minkowski addition of sets, so that ${\displaystyle V(C_{n}+K)}$ refers to the volume of the convex hull of the spheres.

This definition works in two dimensions, where Laszlo Fejes-Toth, Claude Rogers and others used it to formulate a unified theory of finite and infinite packings. In three dimensions, Wills gives a simple argument that such a unified theory is not possible based on this definition: The densest finite arrangement of coins in three dimensions is the sausage with ${\displaystyle \delta =1}$. However, the optimal infinite arrangement is a hexagonal arrangement with ${\displaystyle \delta \approx 0.9}$, so the infinite value cannot be obtained as a limit of finite values. To solve this issue, Wills introduces a modification to the definition by adding a positive parameter ${\displaystyle \rho }$:

${\displaystyle \delta (K,C_{n})={\frac {nV(K)}{V(C_{n}+\rho K)}}}$

${\displaystyle \rho }$ allows the influence of the edges to be considered (giving the convex hull a certain thickness). This is then combined with methods from the theory of mixed volumes and geometry of numbers by Hermann Minkowski.

For each dimension ${\displaystyle d\geq 2}$ there are parameter values ${\displaystyle \rho _{s}(d)}$ and ${\displaystyle \rho _{c}(d)}$ such that for ${\displaystyle \rho \leq \rho _{s}(d)}$ the sausage is the densenst packing (for all integers ${\displaystyle n}$), while for ${\displaystyle \rho \geq \rho _{c}(d)}$ and suffiricently large ${\displaystyle n}$ the cluster is densest. These parameters are dimension-specific. In two dimensions, ${\displaystyle \rho _{c}(2)=\rho _{s}(2)={\frac {\sqrt {3}}{2}}}$ so that there is a transition from sausages to clusters (sausage catastrophe).

There holds an inequality:^[7]

${\displaystyle {\frac {V(B^{d})}{2V(B^{d-1})}}{\rho _{c}(d)}^{1-d}\leq \delta (B^{d})\leq {\frac {V(B^{d})}{2V(B^{d-1})}}{\rho _{s}(d)}^{1-d}}$

where the volume of the unit ball ${\displaystyle B^{d}}$ in ${\displaystyle d}$ dimensions is ${\displaystyle V(B^{d})}$. For ${\displaystyle d=2}$, we have ${\displaystyle \rho _{s}(d)=\rho _{c}(d)}$ and it is predicted that this holds for all dimensions, in which case the value of ${\displaystyle \rho _{c}(d)}$ can be found from that of ${\displaystyle \delta (B^{d})}$.

References