# 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 "error-correcting" 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

-dimensional Euclidean space

is called a sphere packing

if no two of the spheres have an interior point in common. The *packing density* or simply density

of a sphere packing is the fraction of space

covered by the spheres. We will call

the *maximal density*, where the supremum is taken over

all packings in

.

The sphere packing problem seeks to answer the following

question: Among all packings of congruent spheres, what is the maximal

packing density ,

i.e., largest fraction of

covered by the spheres, and what are the corresponding arrangements of the spheres.

For arbitrary

,

the sphere packing problem is notoriously difficult to solve. In the case of

packings of congruent

-dimensional spheres, the exact solution is known for the first

three space dimensions. For

,

the answer is trivial because the spheres tile the space so that

.

In two dimensions, the optimal solution is the triangular lattice

arrangement (also called the hexagonal packing) with

.

In three dimensions, the Kepler conjecture

that the face-centered cubic lattice arrangement

provides the densest packing with

was only recently proved by Hales (2005).

For

,

the problem remains unsolved. For

,

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.,

lattice in

and

Leech lattice in

),

such “miraculous” dimensions do not seem to persist in

sufficiently high dimensions. The determination of bounds on

are the best means of estimating it for arbitrary

.

Upper and lower bounds on the density are known, but they differ by an exponential

factor as

.

Minkowski (1905) proved that the maximal density

among all Bravais lattice packings for

satisfies the lower bound

where

is the Riemann zeta function. One observes that for large values of

,

the asymptotic behavior of the *nonconstructive*

Minkowski lower bound is controlled by

.

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, "Diskontinuitä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

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

-dimensional Euclidean space

.

We show that all of the

-particle correlation functions

(,

, etc.)

of this nonequilibrium model, in a certain limit called

the "ghost" 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

of the ghost RSA packing implies that there may be

disordered sphere packings in sufficiently high

whose density exceeds Minkowski’s lower bound for

Bravais lattices, the dominant asymptotic term of which is

.

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

,

we obtain a conjectural lower bound on the density whose

asymptotic behavior is controlled by

,

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

for asymptotically large

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 "**decorrelation principle**." This principle

states that **unconstrained** correlations in disordered sphere packings

vanish asymptotically in high dimensions and that the

n-particle correlation function

for any

can be inferred entirely (up to some small error) from a knowledge

of the number density

and the pair correlation function

.

A byproduct of our approach is an asymptotic conjectural lower

bound on the average kissing number whose behavior is

controlled by

,

which is to be compared to the best known asymptotic lower

bound on the individual kissing number of

.

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

,

and

to be

,

and

, respectively. To a good approximation, the MRJ

density obeys the scaling form

,

where

and

, which appears to be consistent with high-dimensional

asymptotic limit, albeit with different coefficients.

Calculations of the pair correlation function

and structure factor

for these states show that short-range ordering

appreciably decreases with increasing dimension,

consistent with a recently proposed "decorrelation

principle," which, among othe things, states that

unconstrained correlations diminish as the dimension

increases and vanish entirely in the limit

.

As in three dimensions (where

)

, the packings show no signs of crystallization, are

isostatic, and have a power-law divergence in

at contact with power-law exponent

.

Across dimensions, the cumulative number of neighbors

equals the kissing number of the conjectured densest

packing close to where

has its first minimum. Additionally, we obtain

estimates for the freezing and melting packing fractions

for the equilibrium hard-sphere fluid-solid

transition,

and

, respectively, for

, and

and

, respectively, for

.

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

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

-dimensional Euclidean space

in the infinite-time or saturation limit for the first six

space dimensions (

). 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

, the saturation density

scales with dimension as

, where

and

.

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

given by

, where

is the structure factor at

(i.e., infinite-wavelength number variance) in the high-dimensional

limit. We demonstrate that a Palàsti-like conjecture

(the saturation density in

is equal to that of the one-dimensional problem raised to the

th power) cannot be true for RSA hyperspheres. We show that the structure

factor

must be analytic at

and that RSA packings for

are nearly "hyperuniform." Consistent with the recent

"decorrelation principle," 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

-dimensional sphere for dimensions

and compare to the maximal kissing numbers in these dimensions.

We determine the structure factor exactly for the related "ghost"

RSA packing in

and demonstrate that its distance from "hyperuniformity"

increases as the space dimension increases, approaching a constant

asymptotic value of

.

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

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

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

that is controlled asymptotically by

, where

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 "test" 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

was found with an asymptotic behavior controlled by

.

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

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).