Retrograde Analysis for Sandpiles

A little more detail on the sandpile conjecture from the Babai–Gorodezky talk (and it turns out also from their proceedings paper) that I mentioned very briefly Monday.

A sandpile, in the problem studied by B+G, is an \(n\times n\) grid of nonnegative integers, thought of as counting grains of sand in each cell. Whenever a grid cell contains four or more sand grains, one can tip it over by moving four of its grains one unit in each of the four orthogonal directions. This usually results in adding one to the numbers stored in four neighboring cells, but if the tipped cell is on the boundary of the grid some grains fall off the grid and are removed from the problem.

For example:

   0 3 2    1 3 2    1 4 2    2 0 3
   4 3 1 => 0 4 1 => 1 0 2 => 1 1 2
   2 2 0    3 2 0    3 3 0    3 3 0

It turns out that it doesn't matter in what order cells are tipped; once no more can be tipped, the result is always the same stable configuration, which we call the stabilization of the initial configuration; the initial configuration is a predecessor of its stabilization. B+G define the rank of a stable configuration to be the minimum number of nonzeros in any predecessor of the configuration, and conjecture that almost all stable configurations have quadratic rank; it is this conjecture that I proved.

The idea is to look at small pieces of the stable configuration and analyze how they could have arisen. The first observation is in any pair of adjacent cells, once one of them becomes nonzero it always remains the case that at least one of them is nonzero. Therefore, if you see a pair of adjacent zeros in a stable configuration, they must always have been zero.

The second observation is that if a nonzero is surrounded by pairs of adjacent zeros, it must always have been nonzero. For, its nonzero value could not have been created by tipping an adjacent cell since we know all adjacent cells have always been zero.

So to prove the conjecture, consider a random stable configuration (that is, a configuration in which each cell has between \(0\) and \(3\) grains, chosen uniformly and independently at random). Partition the grid into \(3\times 3\) squares; each square has probability \(3/4^9\) of having the outer eight cells empty and the inner one nonempty, so the expected number of squares of this time is \(\Omega(n^2)\). By a standard Chernoff bound, with high probability the number of squares of this type is near its expectation. That is, for almost all stable configurations, there are quadratically many squares in which the only nonzero is in the center. But each such square contributes one to the rank, so for almost all stable configurations the rank is quadratic.

Of course, we're undercounting the rank. A slight improvement can be formed by tiling the grid by \(7\)-cell heptominoes, formed by overlapping two \(2\times 2\) squares, but better would be to count the number of islands of nonzeros among the non-isolated zeros of the configuration. Maybe the percolation theorists would have a better idea how to perform such a count more accurately.

The same analysis also seems to generalize in a straightforward way to bounded-degree graphs, showing that the rank is almost always proportional to the number of vertices...

---

Comments: