Finite sphere packing

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.

• 

  Sausage packing

• 

  Pizza packing

• 

  Cluster packing

Sausage packing

An arrangement in which the midpoint of all the spheres lie on a single straight line is called a sausage packing, as the convex hull has a sausage-like shape. An approximate example in real life is the packing of tennis balls in a tube, though the ends must be rounded for the tube to coincide with the actual convex hull.

Pizza packing

If all the midpoints lie on a plane, the packing is a pizza packing. Approximate real-life examples of this kind of packing include billiard balls being packed in a triangle as they are set up. This holds for packings in three-dimensional Euclidean space.

Cluster packing

If the midpoints of the spheres are arranged throughout 3D space, the packing is termed a cluster packing. Real-life approximations include fruit being packed in multiple layers in a box.

Relationships between types of packing

By the given definitions, any sausage packing is technically also a pizza packing, and any pizza packing is technically also a cluster packing. In the more general case of [math]\displaystyle{ d }[/math] dimensions, "sausages" refer to one-dimensional arrangements, "clusters" to [math]\displaystyle{ d }[/math]-dimensional arrangements, and "pizzas" to those with an in-between number of dimensions.

One or two spheres always make a sausage. With three, a pizza packing (that is not also a sausage) becomes possible, and with four or more, clusters (that are not also pizzas) become possible.

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 [math]\displaystyle{ n }[/math] up to [math]\displaystyle{ 55 }[/math] along with [math]\displaystyle{ n=57, 58, 63, 64 }[/math]. For [math]\displaystyle{ n=56, 59, 60, 61, 62 }[/math] and [math]\displaystyle{ n \geq 65 }[/math], a cluster packing exists that is more efficient that the sausage packing, as shown in 1992 by Jörg Wills and Pier Mario Gandini. It remains unknown what these most efficient cluster packings look like. For example, in the case [math]\displaystyle{ n = 56 }[/math], 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.

The sudden transition in optimal packing shape is jokingly known by some mathematicians as the sausage catastrophe (Wills, 1985). 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 [math]\displaystyle{ d = 4 }[/math] dimensions the sudden transition is conjectured to happen around 377000 spheres.

For dimensions [math]\displaystyle{ d \leq 10 }[/math], 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 [math]\displaystyle{ d \geq 3 }[/math] there exists a convex shape for which the closest packing is a pizza.

Example of the sausage packing being non-optimal

In the following section it is shown that for 455 spheres the sausage packing is non-optimal, and that there instead exists a special cluster packing that occupies a smaller volume.

The volume of a convex hull of a sausage packing with [math]\displaystyle{ n }[/math] spheres of radius [math]\displaystyle{ r }[/math] is calculable with elementary geometry. The middle part of the hull is a cylinder with length [math]\displaystyle{ h = 2r \cdot (n-1) }[/math] while the caps at the end are half-spheres with radius [math]\displaystyle{ r }[/math]. The total volume [math]\displaystyle{ V_W }[/math] is therefore given by.

[math]\displaystyle{ \begin{align} V_W &= V_\text{cylinder} + 2 \cdot V_\text{half-sphere}\\ &= V_\text{cylinder} + V_\text{sphere}\\ &= \pi h r^2 + \frac{4}{3}\pi r^3\\ &= \pi 2r \cdot (n-1) \cdot r^2 + \frac{4}{3}\pi r^3\\ &= 2 \cdot \left( n - \frac{1}{3}\right) \pi r^3 \end{align} }[/math]

Similarly, it is possible to find the volume of the convex hull of a tetrahedral packing, in which the spheres are arranged so that they form a tetrahedral shape, which only leads to completely filled tetrahedra for specific numbers of spheres. If there are [math]\displaystyle{ x }[/math] spheres along one edge of the tetrahedron, the total number of spheres [math]\displaystyle{ n }[/math] is given by

[math]\displaystyle{ n = \sum_{i=1}^x\sum_{j=1}^i j = \sum_{i=1}^x \frac{i\cdot(i+1)}{2} = \frac{x\cdot(x+1)\cdot(x+2)}{6} }[/math].

Now the inradius [math]\displaystyle{ r }[/math] of a tetrahedral with side length [math]\displaystyle{ a }[/math] is

[math]\displaystyle{ r = \frac{\sqrt{6}}{12} \cdot a }[/math].

From this we have

[math]\displaystyle{ a = 2\sqrt{6} \cdot r }[/math].

The volume [math]\displaystyle{ V_T }[/math] of the tetrahedron is then given by the formula

[math]\displaystyle{ V_T = \frac{\sqrt{2}}{12} \cdot a^3 = \sqrt{192} \cdot r^3 }[/math]

In the case of many spheres being arranged inside a tetrahedron, the length of an edge [math]\displaystyle{ a }[/math] increases by twice the radius of a sphere for each new layer, meaning that for [math]\displaystyle{ x }[/math] layers the side length becomes

[math]\displaystyle{ a = 2 \cdot \left( x - 1 + \sqrt{6} \right) \cdot r }[/math].

Substituting this value into the volume formula for the tetrahedron, we know that the volume [math]\displaystyle{ V }[/math] of the convex hull must be smaller than the tetrahedron itself, so that

[math]\displaystyle{ V \lt \frac{2 \cdot \left( x - 1 + \sqrt{6} \right)^3 \cdot \sqrt{2} \cdot r^3}{3} }[/math].

Taking the number of spheres in a tetrahedron of [math]\displaystyle{ n }[/math] layers and substituting into the earlier expression to get the volume [math]\displaystyle{ V_\text{W} }[/math] of the convex hull of a sausage packing with the same number of spheres, we have

[math]\displaystyle{ V_\text{W} = \frac{x\cdot(x+1)\cdot(x+2)-2}{3} \cdot \pi r^3 }[/math].

For [math]\displaystyle{ x = 13 }[/math], which translates to [math]\displaystyle{ n = 455 }[/math] spheres the coefficient in front of [math]\displaystyle{ r^3 }[/math] is about 2845 for the tetrahedral packing and 2856 for the sausage packing, which implies that for this number of spheres the tetrahedron is more closely packed.

It is also possible with some more effort to derive the exact formula for the volume of the tetrahedral convex hull [math]\displaystyle{ V }[/math], which would involve subtracting the excess volume at the corners and edges of the tetrahedron. This allows the sausage packing to be proved non-optimal for smaller values of [math]\displaystyle{ x }[/math] and therefore [math]\displaystyle{ n }[/math].

Sausage conjecture

The term sausage comes from the mathematician László Fejes Tóth, who posited the sausage conjecture in 1975, which concerns a generalized version of the problem to spheres, convex hulls, and volume in higher dimensions. A generalized sphere in [math]\displaystyle{ d }[/math] dimensions is a [math]\displaystyle{ d }[/math]-dimensional body in which every boundary point lies equally far away from the midpoint. Fejes Tóth's sausage conjecture then states that from [math]\displaystyle{ d=5 }[/math] upwards it is always optimal to arrange the spheres along a straight line. That is, the sausage catastrophe no longer occurs once we go above 4 dimensions. The overall conjecture remains open. The best results so far are those of Ulrich Betke und Martin Henk, who proved the conjecture for dimensions 42 and above.

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.

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

[math]\displaystyle{ \delta (K, C_n) =\frac {n V(K)}{V (C_n +K)} }[/math]

where [math]\displaystyle{ C_n }[/math] is the convex hull of the [math]\displaystyle{ n }[/math] midpoints [math]\displaystyle{ c_i }[/math] of the spheres [math]\displaystyle{ K_i }[/math] (instead of the sphere, we can also take an arbitrary convex body for [math]\displaystyle{ K }[/math]). 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 [math]\displaystyle{ V (C_n + K) }[/math] 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 [math]\displaystyle{ \delta =1 }[/math]. However, the optimal infinite arrangement is a hexagonal arrangement with [math]\displaystyle{ \delta \approx 0.9 }[/math], 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 [math]\displaystyle{ \rho }[/math]:

[math]\displaystyle{ \delta (K, C_n) =\frac {n V(K)}{V (C_n + \rho K)} }[/math]

[math]\displaystyle{ \rho }[/math] 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 [math]\displaystyle{ d \geq 2 }[/math] there are parameter values [math]\displaystyle{ \rho_s (d) }[/math] and [math]\displaystyle{ \rho_c (d) }[/math] such that for [math]\displaystyle{ \rho \leq \rho_s (d) }[/math] the sausage is the densenst packing (for all integers [math]\displaystyle{ n }[/math]), while for [math]\displaystyle{ \rho \geq \rho_c (d) }[/math] and suffiricently large [math]\displaystyle{ n }[/math] the cluster is densest. These parameters are dimension-specific. In two dimensions, [math]\displaystyle{ \rho_c (2)=\rho_s (2)= \frac {\sqrt {3}}{2} }[/math] so that there is a transition from sausages to clusters (sausage catastrophe).

There holds an inequality:

[math]\displaystyle{ \frac {V (B^d)}{2 V (B^{d-1})} {\rho_c (d)}^{1-d} \leq \delta (B^d) \leq \frac {V (B^d)}{2 V (B^{d-1})} {\rho_s (d)}^{1-d} }[/math]

where the volume of the unit ball [math]\displaystyle{ B^d }[/math] in [math]\displaystyle{ d }[/math] dimensions is [math]\displaystyle{ V (B^d) }[/math]. For [math]\displaystyle{ d = 2 }[/math], we have [math]\displaystyle{ \rho_s (d) =\rho_c (d) }[/math] and it is predicted that this holds for all dimensions, in which case the value of [math]\displaystyle{ \rho_c (d) }[/math] can be found from that of [math]\displaystyle{ \delta (B^d) }[/math].