Random thoughts

We tend to look for order in nature. It’s an idea that pervades all of physics. Disorder at high temperature gives way to symmetry breaking and order at low temperature. It’s an outlook that Lev Landau introduced more than half a century ago, and that several generations beautifully treated, to explain the associated phase transitions. It seems to make sense. But what can we say rigorously about order and disorder? A recent Reference Frame column by Jim Langer on the mysterious glass transition (Physics Today, February 2007, page 8 ) points out that in most cases a glass is not a thermodynamic equilibrium state. But can it ever be? Can there be an “ideal” glass, a random state that is thermodynamically stable? We believe that simple equilibrium systems have to order. It’s our prejudice, or as Daniel Fisher puts it, “It’s a religion.”

A similar and related problem is whether optimization leads to order in other problems such as the densest packing of identical objects. Every grocer for the past many millennia has known that the densest packing of oranges is the ordered array that we now know as a face-centered cubic lattice. FCC has recently been proven to be the densest packing, ¹ a result that “many mathematicians believed and all physicists knew” since the 1611 Kepler conjecture. ² There are few such nice rigorous proofs that ordered states are optimal.

Packing problems are among the most ancient, even predating the grocer’s problem. When agriculture first developed in Mesopotamia, there were no scales. Grain was sold by volume—by the basket. You wouldn’t arrange the grains in a lattice, you would pour the grain in randomly. It was even a disadvantage to have the densest packing. Pack less densely, sell more baskets, get more barter, buy your neighbor’s farm, wife, …

I have innocently slipped in the words “random” and “ordered.” Although these are simple intuitive concepts, I don’t know how to define either one of them. Ordered is a bit easier than random. Certainly, we can identify a system with broken symmetry as more ordered; a ferromagnet with its spins aligned is more ordered than an isotropic random set of spins. But the string of letters “devine apathia devine athambia devine aphasia loves us dearly with some exceptions for reasons unknown” is also ordered; its correlations are quickly interpreted by our brains and by the brain of Samuel Beckett, who ordered them for that purpose. Clearly, things can be ordered in innumerable ways. Random is intuitively opposite to ordered; it implies uncorrelated. With some care we can generate a random number sequence. But a random packing already has correlations because the particles don’t interpenetrate. So what level of correlations do we accept and still call the system random?

Random packing

The fact that random packing is ill defined ³ hasn’t prevented people from studying it. Suppose random just means the result of pouring grain or sand or spheres into a jar. Fifteen years ago Sid Nagel and Heinrich Jaeger did that experiment at the University of Chicago. ⁴ They found that when you pour the sand into a cylinder, it fills to a certain level that corresponds to about 58% solids. If you tap the cylinder, you find that the level falls—the packing becomes denser. If you tap a lot (they did about 10⁶ taps), the volume fraction (amount of solids) increases to about 64%. The fact that tapping leads to compaction, that the final density depends on the protocol, was known and recognized in the ancient world. In J. D. Bernal’s Bakerian lecture on random packing, he says, ⁵ “In closing we must not forget the commentary on Random Packing which Saint Luke attributes to Jesus, ‘Give and it shall be given unto you; good measure, pressed down, and shaken together, and running over, shall men give into your bosom. For with the same measure that ye mote withal shall be measured to you again’ (Luke 6:38).” In other words, you’d better give your grain its 10⁶ taps before you sell it or you’re cheating.

Despite random packing being ill defined, a number of different protocols will give an interesting jammed state at a volume fraction of 63.6%. The answer seems better defined than the question.

It’s a little strange that you get a random state when you throw a bunch of spheres together and shake the container. It won’t happen in one or two dimensions. Compress a line of spheres and you get a periodic array that completely fills the line. A layer of pennies that is compressed will easily give a hexagonal lattice, which is the densest circle packing. The layer fills π/2√3, which is 91% of the area. But in three dimensions, a sack of marbles has a vastly different structure from FCC. The marbles’ random arrangement is a peculiar property of the dimension we live in, maybe related to the difference between local packing and global packing. Add pennies together one at a time (with no rearrangements) to form a tight cluster and you have part of a hexagonal lattice at each step. Add spheres together and as you do, first you get a pair, then a triangle, then a tetrahedron, and when you add the sixth particle, you get a configuration that is inconsistent with a globally dense packing.

What did the previous discussion have to do with physics and order? The argument, which may have originated with Johannes van der Waals, has to do with the entropy and free volume near a jammed packing. Thermodynamics tells us we’re supposed to maximize the entropy. For an ideal gas of N particles in volume V, the entropy, S, per particle is S/N = k _Bln(V) where k _B is Boltzmann’s constant and the pressure P = Nk _B T/V. If each particle takes up a volume b then the “free volume” is V − Nb = V(1 − φ/φ_c), where φ is the volume fraction and φ_c is the highest packing fraction for the given constraints, φ_c = 0.64 for random packing, and φ_c = 0.74 for FCC packing. Near φ_c, S/N ∝ k _Bln[V(1 − φ/φ_c)] and P ∝ Nk _B T/V(1 − φ/φ_c). If you randomly fill a box with spheres to 0.64, the particles are jammed—there is no free volume. Put the same spheres in the same box and arrange them in cells on an FCC lattice, and they could fill space to 0.74; so in these cells at 0.64 filling, they are not touching, and the free volume is bigger than zero. The ordered FCC state is stable because it has higher free volume and higher entropy than the disordered state, as unintuitive as that may be.

A good deal of theoretical and experimental evidence suggests that this hard-sphere, entropy-driven transition is responsible for the liquid–solid transition in noble gases and probably for much more, generally. ⁶ But the real lesson is that for hard particles (with no interactions), the densest packed structure is the thermodynamically stable phase at high density. If we could find a hard object that packed denser randomly than in a crystal, it would be an ideal glass.

For spheres arranged in three dimensions, crystal packing is denser than random packing, and order is thermodynamically stable over disorder. What about other shapes and other dimensions? An ellipsoid is just a squashed sphere, a shortening of one or two axes. According to the mathematics literature, for small deviations from a sphere the densest packing is a squashed FCC lattice with the same packing fraction of about 74%. Aleksander Donev, Frank Stillinger, Sal Torquato, and I looked at the packing of ellipsoids, most infamously with a series of experiments on M&Ms candies, and discovered that they pack randomly ⁷ at about 70%—more densely than random spheres, which only pack at about 64%. How dense can we get with ellipsoids?

In a simulation we found that for principal axes 1.25:1:0.8, using 32 ellipsoids, they packed randomly better than 74%. A random packing denser than a crystal packing? How could that be? It would be a stable thermodynamic glass. Doesn’t our result violate some law of physics, of mathematics, of nature?

What is known about whether systems have to order? Well, the answer is that except for spheres in one, two, and three dimensions where the crystal packing has been proven to be densest, not much is known. It’s actually one of the 10 (later 23) “unsolved problems” in mathematics that David Hilbert presented in Paris in 1900. Part of the 18th problem, “Building up space from Congruent Polyhedra,” was to find and enumerate the different structures and symmetries of the densest packings in Euclidean (and hyperbolic) d-dimensional space. ⁸ It remains unsolved.

Packing in higher dimensions

What about higher dimensions? We already imagine four dimensions from relativity, and mathematicians have no problem adding more orthogonal axes and asking how to generalize the sphere packing problem. It’s actually important in optimizing data storage and transmission. ² Although our intuition is probably less reliable in higher dimensions, we might expect that order would lead to the densest packing in higher dimensions as well. But each dimension seems to have its own peculiarities. Although there are some rigorous upper and lower bounds, there are few proofs for the actual densest packing. A special case is the remarkable Leech lattice in 24 dimensions, which is proven not only to be the densest lattice, ² , ³ but if a non-lattice is denser, it will be by less than 2 × 10⁻³⁰.

Quite recently, Torquato and Stillinger, who have contributed much to the sphere and ellipsoid packing problems, have made some inroads into packing in high dimensions. In 1905 Hermann Minkowski set a lower bound of 2/2 ^d for packing in high d dimensions. Torquato and Stillinger were able to show that randomly adding particles until no more could be added without overlap gave 2d/2 ^d , a higher density than Minkowski got. This “random sequential addition” is known as the parking problem in 1D—uniform length cars randomly pull up to an unmarked curve and park until there is no longer room for an additional car to park. Random sequential addition in 1D has a mean field solution of 2/3, an exact solution of 0.747…, and yields a very low density compared to a jammed configuration in any dimension.

Using denser random structures, Torquato and Stillinger were able to show that in high dimensions they could get an exponential improvement, 1/2^(.778…)d , over Minkowski’s result. The upper bound is 1/2^(.5990)d , which is still above the random value, so nothing is wrong. We know that in up to three dimensions lattice packing is densest. So how high do you have to go for random to be densest? Although the densest packing for d dimensions is unproven, above d = 3 the densest crystal yet found is denser than the densest random packing for d < 57. For d = 56 the crystal is denser than random by a factor of 2, but at d = 60 the best packing yet found is higher for random than for crystal by a factor of 5. Of course, these are just the best answers to date, and they are still much less than the upper bound. Nonetheless, the results suggest that random packing may be denser in high dimensions and illustrate our lack of evidence that order should always triumph.

The Landau paradigm may also be faltering in the area of strongly correlated electrons. ⁹ In that case it is less a question of whether the ground state is ordered or disordered. Instead, the question is whether the traditional Landau picture with a broken symmetry order parameter can handle the phenomena associated with quantum phase transitions. The phases and transitions are more directly the results of the topological defects of the different phases than the undiscovered nature of the order.

It seems that there is not (yet) a law in physics or math that requires ground states, condensed phases, or the densest packing to be ordered. Finding a system that violates our basic intuition would lead to new insights. It would also help if we could define “order” and especially “random.” Then we could start working on the problem from the other side.

What about our 1.25:1:0.8 ellipsoids that pack randomly denser than the best crystal packing that the mathematicians had found? Old habits die hard. Not believing that random is denser than ordered, we searched for and found a crystalline packing of the ellipsoids that was a fraction of a percent denser than our random packing ⁷ (and led to ellipsoid crystal packing up to 77%). So we still don’t have an object that packs better randomly than as a crystal. But we’re still looking. Maybe tetrahedra?