Sphere Packings in High-Dimensional Euclidean Spaces

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 $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

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

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

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

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

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 ``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 $\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 ``decorrelation principle. 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 ``decorrelation principle,'' 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 ``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 $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 ``ghost" RSA packing in $\mathbb{R}^d$ and demonstrate that its distance from ``hyperuniformity" 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 ``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 $\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: arXiv:0705.1482