The zero of a sandpile

The cellular automata in eight rules and a triangle update every cell at once, by a rule that looks at its neighbours, and the interesting question about them is what the pattern does as time passes. This essay is about a cellular automaton of a different kind, in which the order of updates looks as though it should matter enormously and turns out not to matter at all — and in which that single fact turns a model of avalanches into a piece of algebra.

The model is a grid of cells, each holding some number of grains of sand. A cell holding four or more grains is unstable, and it topples: it loses four grains and gives one to each of its four neighbours. A grain given to a cell off the edge of the grid is lost. Toppling one cell can push its neighbours over four, so they topple in turn, and the process cascades until every cell holds three grains or fewer. Per Bak, Chao Tang and Kurt Wiesenfeld introduced it in 1987 as a model of how a slowly driven system — sand trickling onto a pile — can organise itself into a state where avalanches of every size occur. In 1990 Deepak Dhar noticed what makes it mathematically special, and almost everything that follows comes from his observation.

The order of toppling does not matter #

When several cells are unstable at once, which should topple first? In most cellular automata the answer would change everything. Here it changes nothing.

The two orders take the same 153 topplings, end in the same stable pile, and topple every cell the same number of times. Dhar’s argument for why is short. Toppling a cell only adds grains to other cells, so if a cell is unstable, toppling some other cell first cannot make it stable; it stays unstable until it topples itself. So any two complete sequences of topplings must topple each cell the same number of times — if one sequence toppled a cell fewer times than the other, consider the first point where that happens, and the extra grains it received before then would have forced one more toppling. The final pile is the starting pile plus the effect of each cell’s topplings, and that effect depends only on how many there were. This is the abelian property, named for the commutativity it implies, and it means “the stable pile reached from a given pile” is a well-defined thing, written $\mathrm{stab}(h)$.

The rule that grains are added and never taken by anything except a toppling is the whole of it. It is the same kind of conservation that a road where nobody overtakes found governing traffic in a one-dimensional automaton, where the number of cars is fixed and only their spacing changes; here grains are conserved inside the grid and lost only at the edge, and the counting of where they go is what pins the outcome down.

Piles that keep coming back #

Now drop grains one at a time on randomly chosen cells, stabilising after each. At first the grid fills up. After long enough it reaches a regime in which every pile it passes through is one it will pass through again: a recurrent pile. Not every stable pile is recurrent — the empty grid, for instance, is never seen again once sand has started arriving — and Dhar found a simple test that tells them apart. Add one grain to each cell for each edge it shares with the boundary, two at the corners and one along the sides, and stabilise. The pile is recurrent exactly when it comes back unchanged with every cell having toppled exactly once.

The test works for a reason that is worth seeing. If every cell of the grid topples exactly once, each cell gives away four grains and receives one from each neighbour inside the grid, so its net change is minus the number of its sides that face the boundary. Adding exactly that many grains first and then toppling every cell once therefore returns the pile to itself. Dhar showed that a recurrent pile is precisely one for which this round trip happens, with each cell toppling once and only once, and a pile that is not recurrent fails because some region of it has too few grains to pass the wave on: the toppling stops at that region’s edge, like a fire that cannot cross a firebreak. The procedure is called the burning algorithm for that reason.

Dropping grains at random visits the recurrent piles evenly in the long run. Each grain added to a cell acts on the recurrent piles as a fixed element of the group does, rearranging them without merging any two, so a random sequence of drops is a random walk on the group, and a random walk on a finite group spreads out to give every element the same share — the kind of settling how long until it forgets measured for Markov chains in general. So the steady state of the sandpile, the one Bak, Tang and Wiesenfeld cared about, is simply the group with every element equally likely.

The recurrent piles form a group. Add two recurrent piles cell by cell and stabilise, and the result is recurrent; the operation is associative and commutative because toppling order does not matter. Every group has a zero, an element that leaves everything unchanged when added, and the recurrent piles’ zero is a surprise.

The zero of a sandpile #

The obvious candidate for the zero is the empty grid, but the empty grid is not recurrent, so it is not in the group. The actual identity has to be computed, and there is a neat formula for it: take the pile $M$ with three grains on every cell, double it, stabilise, subtract the result from $2M$, and stabilise again. The outcome is a pile $e$ which, added to any recurrent pile and stabilised, gives that pile back.

On a 128 × 128 grid the zero has 1,664 empty cells, 568 with one grain, 5,368 with two and 8,784 with three, arranged in a large central square surrounded by triangles, smaller squares and finely textured regions that repeat at smaller scales towards the edges. The figure is checked rather than trusted: adding it to the full pile $M$ and stabilising gives $M$ back. Michael Creutz drew the first such pictures in 1991, and they look much the same at every grid size, scaled up, with the central square always present. The formula works because of what the zero must satisfy. Added to itself and stabilised, the zero must give itself back, and it is the only recurrent pile that does; at the same time, any pile that differs from the empty grid by a whole number of topplings of each cell is equivalent to nothing at all, and $2M - \mathrm{stab}(2M)$ is exactly such a pile, built so that stabilising it lands inside the recurrent piles. So the zero is the recurrent representative of the empty grid’s class: the pile the empty grid would become if it could be made recurrent without changing what it is worth. Why the zero of a group defined by addition and toppling should look like this is not understood in any closed form; its existence is a theorem of algebra, and its shape is a fact of computation.

As many recurrent piles as spanning trees #

How large is the group? Counting directly is possible only for tiny grids — every stable pile on an $n \times n$ grid has each cell at 0, 1, 2 or 3, so there are $4^{n^2}$ of them, and each can be put through the burning test.

The counts are 4 for a single cell, 192 for a 2 × 2 grid and 100,352 for a 3 × 3 grid, out of 4, 256 and 262,144 stable piles. Beside them is a completely different count: the number of spanning trees of the grid with every boundary edge joined to one extra vertex standing for the outside. A determinant that counts trees showed that this number is the determinant of the graph’s Laplacian with one row and column struck out — Kirchhoff’s matrix-tree theorem — and the determinant gives 4, 192 and 100,352. The counts agree because they are the same thing: Dhar proved that the order of the sandpile group is exactly that determinant. Toppling a cell subtracts the cell’s column of the Laplacian from the pile, so two piles are equivalent when they differ by whole combinations of those columns, and the number of inequivalent classes is the determinant of the matrix of columns.

For larger grids the determinant goes on counting where direct enumeration cannot: 557,568,000 recurrent piles on a 4 × 4 grid, about $3.3 \times 10^{13}$ on 5 × 5, and on an 8 × 8 grid a 34-digit number. Every one of those recurrent piles is reached by dropping sand at random, and every one is a member of a group whose zero is the picture above.

Sixty-five thousand grains on one cell #

Another experiment drops all the sand in one place. Put 65,536 grains on a single cell of a large grid and stabilise.

The toppling takes 77,107,818 steps, and none of the grains reaches the edge of the grid. The pile spreads to a radius of 94 cells, close to a disc, and inside it the cells settle into patches — regions where the grains repeat a fixed periodic pattern — separated by thin lines, with smaller patches between larger ones at every scale. Wesley Pegden and Charles Smart proved in 2013 that these piles, rescaled, converge to a definite limit as the number of grains grows, and in 2016 Lionel Levine, Pegden and Smart showed that the periodic patterns in the patches are indexed by the circles of an Apollonian packing — the configuration of mutually tangent circles that curvatures that stay whole built from four starting circles.

The shape has a cleaner description through the number of times each cell toppled, the odometer. A cell’s grains at the end are its starting grains plus the topplings of its four neighbours minus four times its own, so the odometer satisfies a discrete version of the equation that describes how heat or electric potential spreads: the value at each cell compared with the average of its neighbours, the relation every point at the average of its neighbours used to draw graphs. The sandpile’s odometer is the solution of an obstacle problem of that kind, smooth and round on the large scale, and the fractal patterns are what the requirement that grain counts be whole numbers leaves behind in the residue.

Avalanches of every size #

Bak, Tang and Wiesenfeld’s interest was the regime of steady driving. Once the pile has filled up, each new grain either comes to rest at once or sets off an avalanche of topplings, and they asked what sizes those avalanches have.

More than half the grains — 56 per cent here — set off nothing. The rest set off avalanches whose sizes span four orders of magnitude, from a single toppling to 15,836, and between about ten and a few hundred topplings the share of avalanches of each size falls as a straight line on these axes, with slope $-1.00$: a power law, the signature of a system with no typical scale. Beyond a few hundred the edge of the grid cuts the largest avalanches off. The pile holds 2.09 grains a cell on average in this state; on an infinite grid the average is believed — and has since been shown — to be exactly $17/8 = 2.125$, a value Peter Grassberger guessed from simulations.

The striking part, and the reason the model became famous, is that nothing was tuned. Physical systems usually show power laws only at a critical point, a particular temperature or density that has to be set exactly. The traffic automaton in a jam that comes from nowhere is like that: jams appear spontaneously only once the density of cars passes a threshold, and below it traffic flows freely. The sandpile drives itself to its critical state and stays there. Bak, Tang and Wiesenfeld called it self-organised criticality and proposed it as an explanation for power laws in earthquakes, forest fires and much else. How far the explanation reaches is still argued about. What is not in doubt is that the two-dimensional sandpile itself has avalanches of all sizes, though its exact exponents are not known rigorously and careful simulations find that a single straight line is an oversimplification.

A cellular automaton with a group inside #

Most cellular automata are studied by watching them run, and their long-term behaviour is often unknowable: the column rule 30 will not explain found that even whether one column of one rule is periodic is an open problem, and the rule that computes that some rules can simulate any computer at all. The sandpile is a cellular automaton that can be understood algebraically, because the abelian property collapses all the possible histories of a pile into one outcome, and the outcomes into a group.

That algebra does real work. It turns the question “which piles recur?” into the burning test, the question “how many?” into a determinant, and the question “what is the zero?” into a formula. It does not, by itself, explain the pictures. The identity’s nested squares and the single-source pile’s patches are facts that the algebra guarantees exist and leaves completely unexplained, and they took decades of further work — the scaling limits and the Apollonian structure — to start to make sense of. A simple rule, an exact algebraic structure, and pictures that remain partly mysterious: in that combination the sandpile is a small model of a great deal of mathematics.

What the pictures cannot show #

The identity is computed for one grid size and verified there; that the picture keeps its shape as the grid grows is an observation from computing other sizes, not a theorem. The agreement between recurrent piles and spanning trees is checked by direct count only up to 3 × 3, and beyond that rests on Dhar’s theorem; the larger determinants are exact numbers, but nothing on this page lists the piles they count. The single-source pile is one size, 65,536 grains, and its convergence to a limit and the Apollonian structure of its patches are the theorems cited, not things the figure establishes.

The avalanche exponent is the most fragile number here. It is a slope fitted over about one and a half decades, on one grid, from one run of 60,000 grains, and it would shift with a larger grid or a different range of the fit. The true exponents of the two-dimensional sandpile are a long-standing open problem, and the figure shows a power law’s appearance, not its exponent.

Still open: what the zero looks like #

Is there a description of the sandpile group’s identity on an $n \times n$ grid that explains its shape — the central square, the triangles, the textured regions — as $n$ grows? The identity is defined algebraically and computed by toppling, and the pictures for different $n$ look like versions of one limiting shape. Whether they converge to a limit, as the single-source piles were proved to, and whether that limit can be described, is open. The techniques that tamed the single-source pile — obstacle problems, scaling limits and the Apollonian classification of the periodic patches — have been applied to related questions, and the identity’s central square has resisted a complete explanation.

The zero of a group is usually the least interesting element in it, the one that does nothing and is named only for completeness. For the sandpile, it is the one picture everyone draws first and nobody has fully explained.