An application of disc packing to statistical mechanics

I recently posted an article to the arXiv, on a problem suggested by Persi Diaconis. “Hard discs in a box” is a classical setting in statistical physics. One very simple model of matter is as n non-overlapping (or hard) discs of radius r, bouncing around inside a unit square. This is a very well studied model in computational statistical physics, although not much seems to be known so far mathematically. In particular, the statistical physicists observe experimentally that there is a phase transition of some kind when \pi r^2 n  \approx 0.70.

The details of what exactly it means that there is a phase transition will have to be left for another post. But what is relevant for us here is how they sample a uniformly random configuration of hard discs, via the Metropolis algorithm. (Please see the recent survey article by Persi Diaconis in the Bulletin of the AMS.) Basically, one starts with the discs in a reasonable starting configuration, say evenly spaced along some lattice, and then one applies Metropolis, which means the following. Choose one of the n discs uniformly randomly, and make a small perturbation of its position. If this results in overlapping discs, or going out of the square, reject the move, otherwise accept it.

Under certain hypotheses on your space, one can show that this Markov chain converges to the uniform distribution on the space of all possible configurations. But to know this, one must know that the Markov chain is irreducible, and in particular that the configuration space is path connected.

Diaconis, Lebeau, and Michel observed that there is some constant c_1 such that if r \le  c_1 / n, the discs can always be freely rearranged, and in particular that the Metropolis Markov chain is irreducible. The real point of their article was to put useful upper bounds on the mixing time of Metropolis in general, and then they applied it to the hard discs setting as a motivating example. It would be nice if the same holds even in the range of the phase transition; in other words we would like to replace n in the above statement with \sqrt{n}.

However, their result is essentially best possible. In my recent preprint, I gave examples of stable configurations (meaning that no single disc can move) with r > c_2 / n. Here is a picture that should give some feeling for the main idea behind the construction.

A stable configuration of discs

There is still quite a lot to do here. As Persi points out in his survey article, these configuration spaces of hard discs are naturally endowed with a topological structure, as well as probability measure. In his survey article, he says, “very, very little is known about the topology of these spaces.”

At a workshop on, “Topological complexity of random sets,” this past week at the American Institute of Mathematics, Yuliy Baryshnikov, Peter Bubenik, and I were able to establish a connection to classical algebraic topology. In particular, if r < \frac{1}{2 n}, then the configuration space C(n; r) is not only path connected, but it is homotopy equivalent to the classical configuration space of n labeled points in the plane. It is fairly clear that this happens for some sufficiently small radius, but as far as we know, no one had put any quantitative bounds on it yet.

In another article, in preparation, I discuss the combinatorial aspects of these configuration spaces, and give an example of what I call a “transitionary” configuration, as a first attempt to give a heuristic explanation of the phase transition near \pi r^2 n =0.70. The disc packing example illustrated above might be more interesting to discrete geometers than to probabilists, since one would like to believe that examples like this are rather rare, in a measure theoretic sense. Nevertheless, we believe that deeply understanding the various geometric and topological features of these spaces, and how they change as r varies, might be a first step in explaining the phase transition mathematically.