The Abelian sandpile model (ASM) is the more popular name of the original Bak–Tang–Wiesenfeld model (BTW). The BTW model was the first discovered example of a dynamical system displaying self-organized criticality. It was introduced by Per Bak, Chao Tang and Kurt Wiesenfeld in a 1987 paper.
Three years later Deepak Dhar discovered that the BTW sandpile model follows abelian dynamics, and therefore referred to this model as the Abelian sandpile model.
The model is a cellular automaton. In its original formulation, each site on a finite grid has an associated value that corresponds to the slope of the pile. This slope builds up as "grains of sand" (or "chips") are randomly placed onto the pile, until the slope exceeds a specific threshold value at which time that site collapses transferring sand into the adjacent sites, increasing their slope. Bak, Tang, and Wiesenfeld considered a process of successive random placement of sand grains on the grid; each such placement of sand at a particular site may have no effect, or it may cause a cascading reaction that will affect many sites.
Dhar has shown that the final stable sandpile configuration, after the avalanche has terminated, is independent of the precise sequence of topplings that is followed during the avalanche. As a direct consequence of this fact, it is shown that if two sand grains are added to the stable configuration in two different orders, e.g., first at site A and then at site B, and first at B and then at A, the final stable configuration of sand grains turns out to be exactly the same. When a sand grain is added to a stable sandpile configuration, it results in an avalanche which finally stops leading to another stable configuration. Dhar proposed that the addition of a sand grain can be looked upon as an operator; when it acts on one stable configuration, it produces another stable configuration. Dhar showed that all such addition operators form an abelian group, hence the name Abelian sandpile model.
The model has since been studied on the infinite lattice, on other (non-square) lattices, and on arbitrary graphs (including directed multigraphs). It is closely related to the dollar game, a variant of the chip-firing game introduced by Biggs.
Definition (rectangular grids) The sandpile model is a cellular automaton originally defined on an rectangular grid (checkerboard) of the standard square lattice . To each vertex (site, field) of the grid, we associate a value (grains of sand, slope, particles) , with referred to as the (initial) configuration of the sandpile.
The dynamics of the automaton at iteration are then defined as follows:
Choose a random vertex according to some probability distribution (usually uniform). Add one grain of sand to this vertex while the grain numbers for all other vertices remain unchanged, i.e. set and for all . If all vertices are stable, i.e. for all , also the configuration is said to be stable. In this case, continue with the next iteration. If at least one vertex is unstable, i.e. for some , the whole configuration is said to be unstable. In this case, choose any unstable vertex at random. Topple this vertex by reducing its grain number by four and by increasing the grain numbers of each of its (at maximum four) direct neighbors by one, i.e. set, and if .If a vertex at the boundary of the domain topples, this results in a net loss of grains (two grains at the corner of the grid, one grain otherwise). Due to the redistribution of grains, the toppling of one vertex can render other vertices unstable. Thus, repeat the toppling procedure until all vertices of eventually become stable and continue with the next iteration.
The toppling of several vertices during one iteration is referred to as an avalanche. Every avalanche is guaranteed to eventually stop, i.e. after a finite number of topplings some stable configuration is reached such that the automaton is well defined. Moreover, although there will often be many possible choices for the order in which to topple vertices, the final stable configuration does not depend on the chosen order; this is one sense in which the sandpile is abelian. Similarly, the number of times each vertex topples during each iteration is also independent of the choice of toppling order.
Definition (undirected finite multigraphs) To generalize the sandpile model from the rectangular grid of the standard square lattice to an arbitrary undirected finite multigraph , a special vertex called the sink is specified that is not allowed to topple. A configuration (state) of the model is then a function counting the non-negative number of grains on each non-sink vertex. A non-sink vertex with
is unstable; it can be toppled, which sends one of its grains to each of its (non-sink) neighbors:
for all , .
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 of the standard square lattice can then be seen as a special case of this definition: consider the graph which is obtained from by adding an additional vertex, the sink, and by drawing additional edges from the sink to every boundary vertex of such that the degree of every non-sink vertex of 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 of with . Contract every edge of whose two endpoints are not in . The single remaining vertex outside of 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 ( for all ) 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 , where every vertex carries grains of sand, is reachable from any other stable configuration (add 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 , for all , toppling unstable non-sink vertices on a finite connected graph until no unstable non-sink vertex remains leads to a unique stable configuration , which is called the stabilization of . Given two stable configurations and , we can define the operation , 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 , where is the degree matrix and is the adjacency matrix of the graph. Deleting the row and column of corresponding with the sink yields the reduced graph Laplacian . Then, when starting with a configuration and toppling each vertex a total of times yields the configuration , where is the contraction product. Furthermore, if corresponds to the number of times each vertex is toppled during the stabilization of a given configuration , then
In this case, is referred to as the toppling or odometer function (of the stabilization of ).
Under the operation , the set of recurrent configurations forms an abelian group isomorphic to the cokernel of the reduced graph Laplacian , i.e. to , whereby 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 . 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 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 (or for related isomorphic definitions). Finally, some authors use the name Picard group to refer to the direct product of the sandpile group and , 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 , 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