Complex Materials Theory Group

Sphere Hard Packings

Background

There has been resurgent interest in hard-sphere packings in
dimensions greater than three in both the physical and
mathematical sciences. For example, it is known that the
optimal way of sending digital signals over noisy channels
corresponds to the densest sphere packing in a high
dimensional space. These &#34error-correcting&#34 codes underlie
a variety of systems in digital communications and storage,
including compact disks, cell phones and the Internet.
Physicists have studied hard-sphere packings in high dimensions
to gain insight into ground and glassy states of matter as
well as phase behavior in lower dimensions. The determination
of the densest packings in arbitrary dimension is a problem
of long-standing interest in discrete geometry (Conway and Sloane, 1998).

A collection of congruent spheres in
$d$
-dimensional Euclidean space
$\mathbb{R}^d$
is called a sphere packing
$P$
if no two of the spheres have an interior point in common. The packing density or simply density
$\phi(P)$
of a sphere packing is the fraction of space
$\mathbb{R}^d$
covered by the spheres. We will call

\begin{displaymath} \phi_{\mbox{\scriptsize max}}= \sup_{P\subset \mathbb{R}^d} \phi(P) \end{displaymath}


the maximal density, where the supremum is taken over
all packings in
$\mathbb{R}^d$.
The sphere packing problem seeks to answer the following
question: Among all packings of congruent spheres, what is the maximal
packing density $\phi_{\mbox{\scriptsize max}}$,
i.e., largest fraction of
$\mathbb{R}^d$
covered by the spheres, and what are the corresponding arrangements of the spheres.

For arbitrary
$d$,
the sphere packing problem is notoriously difficult to solve. In the case of
packings of congruent
$d$
-dimensional spheres, the exact solution is known for the first
three space dimensions. For
$d=1$,
the answer is trivial because the spheres tile the space so that
$\phi_{\mbox{\scriptsize max}}=1$.
In two dimensions, the optimal solution is the triangular lattice
arrangement (also called the hexagonal packing) with
$\phi_{\mbox{\scriptsize max}}=\pi/\sqrt{12}$.
In three dimensions, the Kepler conjecture
that the face-centered cubic lattice arrangement
provides the densest packing with
$\phi_{\mbox{\scriptsize max}}=\pi/\sqrt{18}$
was only recently proved by Hales (2005).

For
$d \ge 4$,
the problem remains unsolved. For
$3< d <10$,
the densest known packings are Bravais lattices (one sphere
per fundamental periodic cell), but in sufficiently large dimensions
the optimal packings are likely to be non-Bravais-lattice packings.
Each dimension seems to have its own idiosyncrasies, and
it is highly unlikely that a single, simple construction will give the
best packing in every dimension. Although certain dimensions allow
for amazingly dense and symmetric Bravais lattice packings (e.g.,
$E_8$
lattice in
$\mathbb{R}^8$ and
Leech lattice in
$\mathbb{R}^{24}$),
such “miraculous” dimensions do not seem to persist in
sufficiently high dimensions. The determination of bounds on
$\phi_{\mbox{\scriptsize max}}$
are the best means of estimating it for arbitrary
$d$.
Upper and lower bounds on the density are known, but they differ by an exponential
factor as
$d \rightarrow \infty$.

Minkowski (1905) proved that the maximal density
$\phi^L_{\mbox{\scriptsize max}}$
among all Bravais lattice packings for
$d \ge 2$
satisfies the lower bound


\begin{displaymath} \phi^L_{\mbox{\scriptsize max}} \ge \frac{\zeta(d)}{2^{d-1}}, \end{displaymath}


where
$\zeta(d)=\sum_{k=1}^\infty k^{-d}$
is the Riemann zeta function. One observes that for large values of
$d$,
the asymptotic behavior of the nonconstructive
Minkowski lower bound is controlled by
$2^{-d}$.
For the last century, mathematicians have been trying to exponentially improve
Minkowski’s lower bound on the maximal density, but this
result has proved to be illusive.

Our recent work, described below, suggests that disordered
sphere arrangements might be the densest packings in sufficiently
high dimensiuons and provide the long-sought exponential improvement
of Minkowski’s bound. This would imply that disorder wins over
order in sufficiently high dimensions.


J. H. Conway and N. J. A. Sloane, Sphere Packings, Lattices and Groups (Springer-Verlag, New York, 1998).


H. Minkowski, &#34Diskontinuitätsbereich für arithmetische Äquivalenz,” J. reine angew. Math., 129,
220-274 (1905).


See also: A New Tool to Help Mathematicians Pack

Exactly Solvable Disordered Hard-Sphere Packing Model
in Arbitrary-Dimensional Euclidean Spaces


S. Torquato and F. H. Stillinger


We introduce a generalization of the well-known random
sequential addition (RSA) process for hard spheres in
$d$
-dimensional Euclidean space
$\mathbb{R}^d$.
We show that all of the
$n$
-particle correlation functions
($g_2$,
$g_3$, etc.)
of this nonequilibrium model, in a certain limit called
the &#34ghost&#34 RSA packing, can be obtained analytically for
all allowable densities and in any dimension. This
represents the first exactly solvable disordered
sphere-packing model in arbitrary dimension.
The fact that the maximal density
$\phi(\infty)=1/2^d$
of the ghost RSA packing implies that there may be
disordered sphere packings in sufficiently high
$d$
whose density exceeds Minkowski’s lower bound for
Bravais lattices, the dominant asymptotic term of which is
$1/2^d$.


Here is a link to the full paper: Physical Review E, 73, 031106 (2006).


New Conjectural Lower Bounds on the Optimal Density of Sphere Packings



S. Torquato and F. H. Stillinger


Using an optimization procedure that we introduced earlier
[Torquato and Stillinger (2002)] and a conjecture
concerning the existence of disordered sphere packings in
$\mathbb{R}^d$,
we obtain a conjectural lower bound on the density whose
asymptotic behavior is controlled by
$2^{-0.77865\ldots d}$,
thus providing the putative exponential improvement of
Minkowski’s bound. The conjecture states that a hard-core
nonnegative tempered distribution is a pair correlation function
of a translationally invariant disordered sphere packing in
$\mathbb{R}^d$
for asymptotically large
$d$
if and only if the Fourier transform of the autocovariance
function is nonnegative. The conjecture is supported by two
explicit analytically characterized disordered packings, numerical
packing constructions in low dimensions, known necessary conditions
that only have relevance in very low dimensions, the fact that we can
recover the forms of known rigorous lower bounds, and
the &#34decorrelation principle.&#34 This principle
states that unconstrained correlations in disordered sphere packings
vanish asymptotically in high dimensions and that the
n-particle correlation function
$g_n$
for any
$n \ge 3$
can be inferred entirely (up to some small error) from a knowledge
of the number density
$\rho$
and the pair correlation function
$g_2({\bf r})$.
A byproduct of our approach is an asymptotic conjectural lower
bound on the average kissing number whose behavior is
controlled by
$2^{0.22134\ldots d}$,
which is to be compared to the best known asymptotic lower
bound on the individual kissing number of
$2^{0.2075\ldots d}$.
Interestingly, our optimization procedure is precisely the
dual of a primal linear program devised by Cohn and Elkies
(2002, 2003) to obtain upper bounds on the density, and hence
has implications for linear programming bounds. This connection
proves that our density estimate can never exceed the Cohn-Elkies upper
bound, regardless of the validity of our conjecture.


Here is a link to the full paper:
Experimental Mathematics 15, 307 (2006).


Packing Hyperspheres in High-Dimensional Euclidean Spaces



M. Skoge, A. Donev, F. H. Stillinger and S. Torquato


We present the first study of disordered jammed hard-sphere packings
in four-, five- and six-dimensional Euclidean spaces. Using a
collision-driven packing generation algorithm, we obtain the first
estimates for the packing fractions of the maximally random jammed
(MRJ) states for space dimensions
$d=4$,
$5$
and
$6$ to be
$\phi_{MRJ}\simeq 0.46$,
$0.31$
and
$0.20$
, respectively. To a good approximation, the MRJ
density obeys the scaling form
$\phi_{MRJ}= c_1/2^d+(c_2 d)/2^d$,
where
$c_1=-2.72$
and
$c_2=2.56$
, which appears to be consistent with high-dimensional
asymptotic limit, albeit with different coefficients.
Calculations of the pair correlation function
$g_{2}(r)$
and structure factor
$S(k)$
for these states show that short-range ordering
appreciably decreases with increasing dimension,
consistent with a recently proposed &#34decorrelation
principle,&#34 which, among othe things, states that
unconstrained correlations diminish as the dimension
increases and vanish entirely in the limit
$d \rightarrow \infty$.
As in three dimensions (where
$\phi_{MRJ} \simeq 0.64$)
, the packings show no signs of crystallization, are
isostatic, and have a power-law divergence in
$g_{2}(r)$
at contact with power-law exponent
$\simeq 0.4$.
Across dimensions, the cumulative number of neighbors
equals the kissing number of the conjectured densest
packing close to where
$g_{2}(r)$
has its first minimum. Additionally, we obtain
estimates for the freezing and melting packing fractions
for the equilibrium hard-sphere fluid-solid
transition,
$\phi_F \simeq 0.32$
and
$\phi_M \simeq 0.39$
, respectively, for
$d=4$
, and
$\phi_F \simeq 0.19$
and
$\phi_M \simeq 0.24$
, respectively, for
$d=5$.
Although our results indicate the stable phase at high
density is a crystalline solid, nucleation appears to
be strongly suppressed with increasing dimension.


Here is a link to the full paper:
Physical Review E 74, 041127 (2006).


Random Sequential Addition of Hard Spheres
in High Euclidean Dimensions


S. Torquato, O. U. Uche and F. H. Stillinger


Employing numerical and theoretical methods, we investigate
the structural characteristics of random sequential
addition (RSA) of congruent spheres in
$d$
-dimensional Euclidean space
$\mathbb{R}^d$
in the infinite-time or saturation limit for the first six
space dimensions (
$1 \le d \le 6$
). Specifically, we determine the saturation density,
pair correlation function, cumulative coordination number
and the structure factor in each of these dimensions. We find that for
$2 \le d \le 6$
, the saturation density
$\phi_s$
scales with dimension as
$\phi_s= c_1/2^d+c_2 d/2^d$
, where
$c_1=0.202048$
and
$c_2=0.973872$.
We also show analytically that the same density scaling is
expected to persist in the high-dimensional limit,
albeit with different coefficients. A byproduct of this
high-dimensional analysis is a relatively sharp lower bound
on the saturation density for any
$d$
given by
$\phi_s \ge (d+2)(1-S_0)/2^{d+1}$
, where
$S_0\in [0,1]$
is the structure factor at
$k=0$
(i.e., infinite-wavelength number variance) in the high-dimensional
limit. We demonstrate that a Palàsti-like conjecture
(the saturation density in
$\mathbb{R}^d$
is equal to that of the one-dimensional problem raised to the
$d$
th power) cannot be true for RSA hyperspheres. We show that the structure
factor
$S(k)$
must be analytic at
$k=0$
and that RSA packings for
$1 \le d \le 6$
are nearly &#34hyperuniform.&#34 Consistent with the recent
&#34decorrelation principle,&#34 we find that pair
correlations markedly diminish as the space dimension increases up to six.
We also obtain kissing (contact) number statistics for
saturated RSA configurations on the surface of a
$d$-dimensional sphere for dimensions
$2 \le d \le 5$
and compare to the maximal kissing numbers in these dimensions.
We determine the structure factor exactly for the related &#34ghost&#34
RSA packing in
$\mathbb{R}^d$
and demonstrate that its distance from &#34hyperuniformity&#34
increases as the space dimension increases, approaching a constant
asymptotic value of
$1/2$.


Here is a link to the full paper:
Physical Review E 74, 061308 (2006).


Estimates of the Optimal Density and Kissing
Number of Sphere Packings in High Dimensions



A. Scardicchio, F. H. Stillinger and S. Torquato


The problem of finding the asymptotic behavior of the maximal
density
$\phi_{\mbox{\scriptsize max}}$
of sphere packings in high Euclidean dimensions is one of the
most fascinating and challenging problems in discrete geometry.
One century ago, Minkowski obtained a rigorous lower bound on
$\phi_{\mbox{\scriptsize max}}$
that is controlled asymptotically by
$1/2^d$
, where
$d$
is the Euclidean space dimension. An indication of the
difficulty of the problem can be garnered from the fact
that exponential improvement of Minkowski’s bound has
proved to be elusive, even though existing upper bounds
suggest that such improvement should be possible. Using a statistical-
mechanical procedure to optimize the density associated with
a &#34test&#34 pair correlation function and a conjecture
concerning the existence of disordered sphere packings
[S. Torquato and F. H. Stillinger, Experimental Math. 15, 307 (2006)],
the putative exponential improvement on
$\phi_{\mbox{\scriptsize max}}$
was found with an asymptotic behavior controlled by
$1/2^{(0.77865\ldots)d}$.
Using the same methods, we investigate whether this
exponential improvement can be further improved by exploring
other test pair correlation functions corresponding to disordered
packings. We demonstrate that there are simpler test functions
that lead to the same asymptotic result. More importantly, we show
that there is a wide class of test functions that lead
to precisely the same putative exponential improvement and therefore
the asymptotic form
$1/2^{(0.77865\ldots)d}$
is much more general than previously surmised. This class of
test functions leads to an optimized average kissing number
that is controlled by the same asymptotic behavior as the
one found in the aforementioned paper.


Here is a link to the full paper:
Journal of Mathematical Physics, 49, 043301 (2008).