Abelian sandpile model

Definition (undirected finite multigraphs)

To generalize the sandpile model from the rectangular grid of the standard square lattice to an arbitrary undirected finite multigraph ${\displaystyle G=(V,E)}$, a special vertex ${\displaystyle s\in V}$ called the sink is specified that is not allowed to topple. A configuration (state) of the model is then a function ${\displaystyle z:V\setminus \{s\}\to {\mathbb{N}}_0}$ counting the non-negative number of grains on each non-sink vertex. A non-sink vertex ${\displaystyle v\in V\setminus \{s\}}$ with

${\displaystyle z(v)\ge \mathrm{deg}(v)}$

is unstable; it can be toppled, which sends one of its grains to each of its (non-sink) neighbors:

${\displaystyle z(v)\to z(v)-\mathrm{deg}(v)}$

${\displaystyle z(u)\to z(u)+1}$ for all ${\displaystyle u\sim v}$, ${\displaystyle u\ne s}$.

The cellular automaton then progresses as before, i.e. by adding, in each iteration, one particle to a randomly chosen non-sink vertex and toppling until all vertices are stable.

The definition of the sandpile model given above for finite rectangular grids ${\displaystyle \mathrm{\Gamma }\subset {\mathbb{Z}}^2}$ of the standard square lattice ${\displaystyle {\mathbb{Z}}^2}$ can then be seen as a special case of this definition: consider the graph ${\displaystyle G=(V,E)}$ which is obtained from ${\displaystyle \mathrm{\Gamma }}$ by adding an additional vertex, the sink, and by drawing additional edges from the sink to every boundary vertex of ${\displaystyle \mathrm{\Gamma }}$ such that the degree of every non-sink vertex of ${\displaystyle G}$ is four. In this manner, also sandpile models on non-rectangular grids of the standard square lattice (or of any other lattice) can be defined: Intersect some bounded subset ${\displaystyle S}$ of ${\displaystyle {\mathbb{R}}^2}$ with ${\displaystyle {\mathbb{Z}}^2}$. Contract every edge of ${\displaystyle {\mathbb{Z}}^2}$ whose two endpoints are not in ${\displaystyle S\cap {\mathbb{Z}}^2}$. The single remaining vertex outside of ${\displaystyle S\cap {\mathbb{Z}}^2}$ then constitutes the sink of the resulting sandpile graph.

Transient and recurrent configurations

In the dynamics of the sandpile automaton defined above, some stable configurations (${\displaystyle 0\le z(v)<4}$ for all ${\displaystyle v\in G\setminus \{s\}}$) appear infinitely often, while others can only appear a finite number of times (if at all). The former are referred to as recurrent configurations, while the latter are referred to as transient configurations. The recurrent configurations thereby consist of all stable non-negative configurations which can be reached from any other stable configuration by repeatedly adding grains of sand to vertices and toppling. It is easy to see that the minimally stable configuration ${\displaystyle z_m}$, where every vertex carries ${\displaystyle z_m(v)=\mathrm{deg}(v)-1}$ grains of sand, is reachable from any other stable configuration (add ${\displaystyle \mathrm{deg}(v)-z(v)-1\ge 0}$ grains to every vertex). Thus, equivalently, the recurrent configurations are exactly those configurations which can be reached from the minimally stable configuration by only adding grains of sand and stabilizing.

Not every non-negative stable configuration is recurrent. For example, in every sandpile model on a graph consisting of at least two connected non-sink vertices, every stable configuration where both vertices carry zero grains of sand is non-recurrent. To prove this, first note that the addition of grains of sand can only increase the total number of grains carried by the two vertices together. To reach a configuration where both vertices carry zero particles from a configuration where this is not the case thus necessarily involves steps where at least one of the two vertices is toppled. Consider the last one of these steps. In this step, one of the two vertices has to topple last. Since toppling transfers a grain of sand to every neighboring vertex, this implies that the total number of grains carried by both vertices together cannot be lower than one, which concludes the proof.

Sandpile group

Given a configuration ${\displaystyle z}$, ${\displaystyle z(v)\in {\mathbb{N}}_0}$ for all ${\displaystyle v\in G\setminus \{s\}}$, toppling unstable non-sink vertices on a finite connected graph until no unstable non-sink vertex remains leads to a unique stable configuration ${\displaystyle z^{\circ }}$, which is called the stabilization of ${\displaystyle z}$. Given two stable configurations ${\displaystyle z}$ and ${\displaystyle w}$, we can define the operation ${\displaystyle z\ast w:=(z+w{)}^{\circ }}$, corresponding to the vertex-wise addition of grains followed by the stabilization of the resulting sandpile.

Given an arbitrary but fixed ordering of the non-sink vertices, multiple toppling operations, which can e.g. occur during the stabilization of an unstable configuration, can be efficiently encoded by using the graph Laplacian ${\displaystyle \mathrm{\Delta }=D-A}$, where ${\displaystyle D}$ is the degree matrix and ${\displaystyle A}$ is the adjacency matrix of the graph. Deleting the row and column of ${\displaystyle \mathrm{\Delta }}$ corresponding with the sink yields the reduced graph Laplacian ${\displaystyle {\mathrm{\Delta }}^{\prime }}$. Then, when starting with a configuration ${\displaystyle z}$ and toppling each vertex ${\displaystyle v}$ a total of ${\displaystyle \mathbf{x}(v)\in {\mathbb{N}}_0}$ times yields the configuration ${\displaystyle z-{\mathrm{\Delta }}^{\prime }\mathbf{\cdot }\mathbf{x}}$, where ${\displaystyle \mathbf{\cdot }}$ is the contraction product. Furthermore, if ${\displaystyle \mathbf{x}}$ corresponds to the number of times each vertex is toppled during the stabilization of a given configuration ${\displaystyle z}$, then

${\displaystyle z^{\circ }=z-{\mathrm{\Delta }}^{\prime }\mathbf{\cdot }\mathbf{x}}$

In this case, ${\displaystyle \mathbf{x}}$ is referred to as the toppling or odometer function (of the stabilization of ${\displaystyle z}$).

Under the operation ${\displaystyle \ast }$, the set of recurrent configurations forms an abelian group isomorphic to the cokernel of the reduced graph Laplacian ${\displaystyle {\mathrm{\Delta }}^{\prime }}$, i.e. to ${\displaystyle {\mathbf{Z}}^{n-1}/{\mathbf{Z}}^{n-1}{\mathrm{\Delta }}^{\prime }}$, whereby ${\displaystyle n}$ denotes the number of vertices (including the sink). More generally, the set of stable configurations (transient and recurrent) forms a commutative monoid under the operation ${\displaystyle \ast }$. The minimal ideal of this monoid is then isomorphic to the group of recurrent configurations.

The group formed by the recurrent configurations, as well as the group ${\displaystyle {\mathbf{Z}}^{n-1}/{\mathbf{Z}}^{n-1}{\mathrm{\Delta }}^{\prime }}$ to which the former is isomorphic, is most commonly referred to as the sandpile group. Other common names for the same group are critical group, Jacobian group or (less often) Picard group. Note, however, that some authors only denote the group formed by the recurrent configurations as the sandpile group, while reserving the name Jacobian group or critical group for the (isomorphic) group defined by ${\displaystyle {\mathbf{Z}}^{n-1}/{\mathbf{Z}}^{n-1}{\mathrm{\Delta }}^{\prime }}$ (or for related isomorphic definitions). Finally, some authors use the name Picard group to refer to the direct product of the sandpile group and ${\displaystyle \mathbb{Z}}$, which naturally appears in a cellular automaton closely related to the sandpile model, referred to as the chip firing or dollar game.

Given the isomorphisms stated above, the order of the sandpile group is the determinant of ${\displaystyle {\mathrm{\Delta }}^{\prime }}$, which by the matrix tree theorem is the number of spanning trees of the graph.

Self-organized criticality

The original interest behind the model stemmed from the fact that in simulations on lattices, it is attracted to its critical state, at which point the correlation length of the system and the correlation time of the system go to infinity, without any fine tuning of a system parameter. This contrasts with earlier examples of critical phenomena, such as the phase transitions between solid and liquid, or liquid and gas, where the critical point can only be reached by precise tuning (e.g., of temperature). Hence, in the sandpile model we can say that the criticality is self-organized.

Once the sandpile model reaches its critical state there is no correlation between the system's response to a perturbation and the details of a perturbation. Generally this means that dropping another grain of sand onto the pile may cause nothing to happen, or it may cause the entire pile to collapse in a massive slide. The model also displays 1/ƒ noise, a feature common to many complex systems in nature.

This model only displays critical behaviour in two or more dimensions. The sandpile model can be expressed in 1D; however, instead of evolving to its critical state, the 1D sandpile model instead reaches a minimally stable state where every lattice site goes toward the critical slope.

For two dimensions, it has been hypothesized that the associated conformal field theory consists of symplectic fermions with a central charge c = −2.

Experimental evidence

The empirical validity of the sandpile model remains a subject of debate. However, experimental results indicate that grain morphology significantly influences a system's adherence to theoretical predictions. While traditional sandpiles often fail to exhibit ideal behavior, piles of elongated grains, such as rice, have been shown to demonstrate self-organized criticality.

Properties

Least action principle

The stabilization of chip configurations obeys a form of least action principle: each vertex topples no more than necessary in the course of the stabilization. This can be formalized as follows. Call a sequence of topples legal if it only topples unstable vertices, and stabilizing if it results in a stable configuration. The standard way of stabilizing the sandpile is to find a maximal legal sequence; i.e., by toppling so long as it is possible. Such a sequence is obviously stabilizing, and the Abelian property of the sandpile is that all such sequences are equivalent up to permutation of the toppling order; that is, for any vertex ${\displaystyle v}$, the number of times ${\displaystyle v}$ topples is the same in all legal stabilizing sequences. According to the least action principle, a minimal stabilizing sequence is also equivalent up to permutation of the toppling order to a legal (and still stabilizing) sequence. In particular, the configuration resulting from a minimal stabilizing sequence is the same as results from a maximal legal sequence.

More formally, if ${\displaystyle \mathbf{u}}$ is a vector such that ${\displaystyle \mathbf{u}(v)}$ is the number of times the vertex ${\displaystyle v}$ topples during the stabilization (via the toppling of unstable vertices) of a chip configuration ${\displaystyle z}$, and ${\displaystyle \mathbf{n}}$ is an integral vector (not necessarily non-negative) such that ${\displaystyle z-\mathbf{n}{\mathrm{\Delta }}^{\prime }}$ is stable, then ${\displaystyle \mathbf{u}(v)\le \mathbf{n}(v)}$ for all vertices ${\displaystyle v}$.

Scaling limits

The animation shows the recurrent configuration corresponding to the identity of the sandpile group on different ${\displaystyle N\times N}$ square grids of increasing sizes ${\displaystyle N\ge 1}$, whereby the configurations are rescaled to always have the same physical dimension. Visually, the identities on larger grids seem to become more and more detailed and to "converge to a continuous image". Mathematically, this suggests the existence of scaling-limits of the sandpile identity on square grids based on the notion of weak-* convergence (or some other, generalized notion of convergence). Indeed, existence of scaling limits of recurrent sandpile configurations has been proved by Wesley Pegden and Charles Smart. In further joint work with Lionel Levine, they use the scaling limit to explain the fractal structure of the sandpile on square grids. Another scaling limit, when the relaxations of a perturbation of the maximal stable state converge to a picture defined by tropical curves, is established in works of Nikita Kalinin and Mikhail Shkolnikov.

Turing completeness

Abelian sandpiles in three or more dimensions can be used to simulate a Turing machine and are therefore Turing complete.

Generalizations and related models

Sandpile models on infinite grids

There exist several generalizations of the sandpile model to infinite grids. A challenge in such generalizations is that, in general, it is not guaranteed anymore that every avalanche will eventually stop. Several of the generalization thus only consider the stabilization of configurations for which this can be guaranteed.

A rather popular model on the (infinite) square lattice with sites ${\displaystyle (x,y)\in {\mathbb{Z}}^2}$ is defined as follows:

Begin with some nonnegative configuration of values ${\displaystyle z(x,y)\in \mathbf{Z}}$ which is finite, meaning

${\displaystyle \sum _{x,y}z(x,y)<\mathrm{\infty }.}$

Any site ${\displaystyle (x,y)}$ with

${\displaystyle z(x,y)\ge 4}$

is unstable and can topple (or fire), sending one of its chips to each of its four neighbors:

${\displaystyle z(x,y)\to z(x,y)-4,}$

${\displaystyle z(x\pm 1,y)\to z(x\pm 1,y)+1,}$

${\displaystyle z(x,y\pm 1)\to z(x,y\pm 1)+1.}$

Since the initial configuration is finite, the process is guaranteed to terminate, with the grains scattering outward.

A popular special case of this model is given when the initial configuration is zero for all vertices except the origin. If the origin carries a huge number of grains of sand, the configuration after relaxation forms fractal patterns (see figure). When letting the initial number of grains at the origin go to infinity, the rescaled stabilized configurations were shown to converge to a unique limit.

Sandpile models on directed graphs

The sandpile model can be generalized to arbitrary directed multigraphs. The rules are that any vertex ${\displaystyle v}$ with

${\displaystyle z(v)\ge {\mathrm{deg}}^{+}(v)}$

is unstable; toppling again sends chips to each of its neighbors, one along each outgoing edge:

${\displaystyle z(v)\to z(v)-{\mathrm{deg}}^{+}(v)+\mathrm{deg}(v,v)}$

and, for each ${\displaystyle u\ne v}$:

${\displaystyle z(u)\to z(u)+\mathrm{deg}(v,u)}$

where ${\displaystyle \mathrm{deg}(v,u)}$ is the number of edges from ${\displaystyle v}$ to ${\displaystyle u}$.

In this case the Laplacian matrix is not symmetric. If we specify a sink ${\displaystyle s}$ such that there is a path from every other vertex to ${\displaystyle s}$, then the stabilization operation on finite graphs is well-defined and the sandpile group can be written

${\displaystyle {\mathbf{Z}}^{n-1}/{\mathbf{Z}}^{n-1}{\mathrm{\Delta }}^{\prime }}$

as before.

The order of the sandpile group is again the determinant of ${\displaystyle {\mathrm{\Delta }}^{\prime }}$, which by the general version of the matrix tree theorem is the number of oriented spanning trees rooted at the sink.

The extended sandpile model

To better understand the structure of the sandpile group for different finite convex grids ${\displaystyle \mathrm{\Gamma }\subset {\mathbb{Z}}^2}$ of the standard square lattice ${\displaystyle {\mathbb{Z}}^2}$, Lang and Shkolnikov introduced the extended sandpile model in 2019. The extended sandpile model is defined nearly exactly the same as the usual sandpile model (i.e. the original Bak–Tang–Wiesenfeld model ), except that vertices at the boundary ${\displaystyle \mathrm{\partial }\mathrm{\Gamma }}$ of the grid are now allowed to carry a non-negative real number of grains. In contrast, vertices in the interior of the grid are still only allowed to carry integer numbers of grains. The toppling rules remain unchanged, i.e. both interior and boundary vertices are assumed to become unstable and topple if the grain number reaches or exceeds four.

Also the recurrent configurations of the extended sandpile model form an abelian group, referred to as the extended sandpile group, of which the usual sandpile group is a discrete subgroup. Different to the usual sandpile group, the extended sandpile group is however a continuous Lie group. Since it is generated by only adding grains of sand to the boundary ${\displaystyle \mathrm{\partial }\mathrm{\Gamma }}$ of the grid, the extended sandpile group furthermore has the topology of a torus of dimension ${\displaystyle |\mathrm{\partial }\mathrm{\Gamma }|}$ and a volume given by the order of the usual sandpile group.

Of specific interest is the question how the recurrent configurations dynamically change along the continuous geodesics of this torus passing through the identity. This question leads to the definition of the sandpile dynamics

${\displaystyle D_H(t)=(I-t\mathrm{\Delta }H{)}^{\circ }}$ (extended sandpile model)

respectively

${\displaystyle {\tilde{D}}_H(t)=(I+\lfloor -t\mathrm{\Delta }H\rfloor {)}^{\circ }}$ (usual sandpile model)

induced by the integer-valued harmonic function ${\displaystyle H}$ at time ${\displaystyle t\in \mathbb{R}\setminus \mathbb{Z}}$, with ${\displaystyle I}$ the identity of the sandpile group and ${\displaystyle \lfloor .\rfloor }$ the floor function. For low-order polynomial harmonic functions, the sandpile dynamics are characterized by the smooth transformation and apparent conservation of the patches constituting the sandpile identity. For example, the harmonic dynamics induced by ${\displaystyle H=xy}$ resemble the "smooth stretching" of the identity along the main diagonals visualized in the animation. The configurations appearing in the dynamics induced by the same harmonic function on square grids of different sizes were furthermore conjectured to weak-* converge, meaning that there supposedly exist scaling limits for them. This proposes a natural renormalization for the extended and usual sandpile groups, meaning a mapping of recurrent configurations on a given grid to recurrent configurations on a sub-grid. Informally, this renormalization simply maps configurations appearing at a given time ${\displaystyle t}$ in the sandpile dynamics induced by some harmonic function ${\displaystyle H}$ on the larger grid to the corresponding configurations which appear at the same time in the sandpile dynamics induced by the restriction of ${\displaystyle H}$ to the respective sub-grid.

The divisible sandpile

A strongly related model is the so-called divisible sandpile model, introduced by Levine and Peres in 2008, in which, instead of a discrete number of particles in each site ${\displaystyle x}$, there is a real number ${\displaystyle s(x)}$ representing the amount of mass on the site. In case such mass is negative, one can understand it as a hole. The topple occurs whenever a site has mass larger than 1; it topples the excess evenly between its neighbors resulting in the situation that, if a site is full at time ${\displaystyle t}$, it will be full for all later times.

Cultural references

The Bak–Tang–Wiesenfeld sandpile was mentioned on the Numb3rs episode "Rampage," as mathematician Charlie Eppes explains to his colleagues a solution to a criminal investigation.

The computer game Hexplode is based around the Abelian sandpile model on a finite hexagonal grid where instead of random grain placement, grains are placed by players.