The Abelian sandpile model (ASM) is the more popular name of the original Bak–Tang–Wiesenfeld model (BTW). BTW model was the first discovered example of a
dynamical system
In mathematics, a dynamical system is a system in which a function describes the time dependence of a point in an ambient space. Examples include the mathematical models that describe the swinging of a clock pendulum, the flow of water i ...
displaying
self-organized criticality. It was introduced by
Per Bak,
Chao Tang
Tang Chao (; born 1958) is a Chair Professor of Physics and Systems Biology at Peking University.
Education
He had his undergraduate training at the University of Science and Technology of China, then went to the United States through the CU ...
and
Kurt Wiesenfeld in a 1987 paper.
[
]
Three years later
Deepak Dhar
Deepak Dhar (born 30 October 1951) is an Indian theoretical physicist and a distinguished professor at the department of physics of Indian Institute of Science Education and Research, Pune. He is widely respected for his research on statistical ...
discovered that the BTW sandpile model indeed follows the abelian dynamics and therefore referred to this model as the Abelian sandpile model.
[
]
The model is a
cellular automaton
A cellular automaton (pl. cellular automata, abbrev. CA) is a discrete model of computation studied in automata theory. Cellular automata are also called cellular spaces, tessellation automata, homogeneous structures, cellular structures, tesse ...
. 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 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 is 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
A cellular automaton (pl. cellular automata, abbrev. CA) is a discrete model of computation studied in automata theory. Cellular automata are also called cellular spaces, tessellation automata, homogeneous structures, cellular structures, tesse ...
originally defined on a
rectangular grid (''checkerboard'')
of the
standard square lattice .
To each vertex (''side'', ''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 letting the grain numbers for all other vertices 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
In graph theory and computer science, an adjacency matrix is a square matrix used to represent a finite graph. The elements of the matrix indicate whether pairs of vertices are adjacent or not in the graph.
In the special case of a finite simp ...
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
In mathematics, an abelian group, also called a commutative group, is a group in which the result of applying the group operation to two group elements does not depend on the order in which they are written. That is, the group operation is comm ...
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
In abstract algebra, a branch of mathematics, a monoid is a set equipped with an associative binary operation and an identity element. For example, the nonnegative integers with addition form a monoid, the identity element being 0.
Monoids ar ...
under the operation
. The minimal
ideal
Ideal may refer to:
Philosophy
* Ideal (ethics), values that one actively pursues as goals
* Platonic ideal, a philosophical idea of trueness of form, associated with Plato
Mathematics
* Ideal (ring theory), special subsets of a ring considered ...
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
In the mathematical field of graph theory, Kirchhoff's theorem or Kirchhoff's matrix tree theorem named after Gustav Kirchhoff is a theorem about the number of spanning trees in a graph, showing that this number can be computed in polynomial ti ...
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 transition
In chemistry, thermodynamics, and other related fields, a phase transition (or phase change) is the physical process of transition between one state of a medium and another. Commonly the term is used to refer to changes among the basic states ...
s 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
Self-organization, also called spontaneous order in the social sciences, is a process where some form of overall order arises from local interactions between parts of an initially disordered system. The process can be spontaneous when suff ...
.
Once the sandpile model reaches its critical state there is no correlation between the system's response to a
perturbation
Perturbation or perturb may refer to:
* Perturbation theory, mathematical methods that give approximate solutions to problems that cannot be solved exactly
* Perturbation (geology), changes in the nature of alluvial deposits over time
* Perturbatio ...
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
A conformal field theory (CFT) is a quantum field theory that is invariant under conformal transformations. In two dimensions, there is an infinite-dimensional algebra of local conformal transformations, and conformal field theories can sometimes ...
consists of
symplectic fermion
The term "symplectic" is a calque of "complex" introduced by Hermann Weyl in 1939. In mathematics it may refer to:
* Symplectic Clifford algebra, see Weyl algebra
* Symplectic geometry
* Symplectic group
* Symplectic integrator
* Symplectic mani ...
s with a
central charge
In theoretical physics, a central charge is an operator ''Z'' that commutes with all the other symmetry operators. The adjective "central" refers to the center of the symmetry group—the subgroup of elements that commute with all other element ...
''c'' = −2.
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
, the number of times
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
is a vector such that
is the number of times the vertex
topples during the stabilization (via the toppling of unstable vertices) of a chip configuration
, and
is an integral vector (not necessarily non-negative) such that
is stable, then
for all vertices
.
Scaling limits
The animation shows the recurrent configuration corresponding to the identity of the sandpile group on different
square grids of increasing sizes
, 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.
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
is defined as follows:
Begin with some nonnegative configuration of values
which is finite, meaning
:
Any site
with
:
is ''unstable'' and can ''topple'' (or ''fire''), sending one of its chips to each of its four neighbors:
:
:
:
Since the initial configuration is finite, the
process
A process is a series or set of activities that interact to produce a result; it may occur once-only or be recurrent or periodic.
Things called a process include:
Business and management
*Business process, activities that produce a specific se ...
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
with
:
is unstable; toppling again sends chips to each of its neighbors, one along each outgoing edge:
:
and, for each
:
:
where
is the number of edges from
to
.
In this case the Laplacian matrix is not symmetric. If we specify a sink
such that there is a path from every other vertex to
, then the stabilization operation on finite graphs is well-defined and the sandpile group can be written
:
as before.
The order of the sandpile group is again the determinant of
, which by the general version of the
matrix tree theorem
In the mathematical field of graph theory, Kirchhoff's theorem or Kirchhoff's matrix tree theorem named after Gustav Kirchhoff is a theorem about the number of spanning trees in a graph, showing that this number can be computed in polynomial ti ...
is the number of oriented
spanning tree
In the mathematical field of graph theory, a spanning tree ''T'' of an undirected graph ''G'' is a subgraph that is a tree which includes all of the vertices of ''G''. In general, a graph may have several spanning trees, but a graph that is not ...
s rooted at the sink.
The extended sandpile model
To better understand the structure of the sandpile group for different finite convex grids
of the standard square lattice
, 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
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
In mathematics, a topological group ''G'' is called a discrete group if there is no limit point in it (i.e., for each element in ''G'', there is a neighborhood which only contains that element). Equivalently, the group ''G'' is discrete if and o ...
. Different to the usual sandpile group, the extended sandpile group is however a continuous
Lie group
In mathematics, a Lie group (pronounced ) is a group that is also a differentiable manifold. A manifold is a space that locally resembles Euclidean space, whereas groups define the abstract concept of a binary operation along with the additio ...
. Since it is generated by only adding grains of sand to the boundary
of the grid, the extended sandpile group furthermore has the
topology
In mathematics, topology (from the Greek language, Greek words , and ) is concerned with the properties of a mathematical object, geometric object that are preserved under Continuous function, continuous Deformation theory, deformations, such ...
of a
torus
In geometry, a torus (plural tori, colloquially donut or doughnut) is a surface of revolution generated by revolving a circle in three-dimensional space about an axis that is coplanar with the circle.
If the axis of revolution does not tou ...
of dimension
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
geodesic
In geometry, a geodesic () is a curve representing in some sense the shortest path ( arc) between two points in a surface, or more generally in a Riemannian manifold. The term also has meaning in any differentiable manifold with a connection. ...
s of this torus passing through the identity. This question leads to the definition of the sandpile dynamics
:
(extended sandpile model)
respectively
:
(usual sandpile model)
induced by the integer-valued
harmonic function
In mathematics, mathematical physics and the theory of stochastic processes, a harmonic function is a twice continuously differentiable function f: U \to \mathbb R, where is an open subset of that satisfies Laplace's equation, that is,
: \f ...
at time
, with
the identity of the sandpile group and
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
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
Renormalization is a collection of techniques in quantum field theory, the statistical mechanics of fields, and the theory of self-similar geometric structures, that are used to treat infinities arising in calculated quantities by altering v ...
for the extended and usual sandpile groups, meaning a mapping of recurrent configurations on a given grid to recurrent configurations on a sub-grid. Informaly, this renormalization simply maps configurations appearing at a given time
in the sandpile dynamics induced by some harmonic function
on the larger grid to the corresponding configurations which appear at the same time in the sandpile dynamics induced by the restriction of
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
, there is a real number
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
, it will be full for all later times.
Cultural references
The Bak–Tang–Wiesenfeld sandpile was mentioned on the
Numb3rs
''Numbers'' (stylized as ''NUMB3RS'') is an American crime drama television series that was broadcast on CBS from January 23, 2005, to March 12, 2010, for six seasons and 118 episodes. The series was created by Nicolas Falacci and Cheryl Heuton ...
episode "Rampage," as mathematician Charlie Eppes explains to his colleagues a solution to a criminal investigation.
The
computer game
Video games, also known as computer games, are electronic games that involves interaction with a user interface or input device such as a joystick, game controller, controller, computer keyboard, keyboard, or motion sensing device to gener ...
Hexplode is based around the Abelian sandpile model on a finite hexagonal grid where instead of random grain placement, grains are placed by players.
References
Further reading
*
*
*
*
*
*
External links
*
*{{Cite web, last=Ellenberg, first=Jordan, author-link=Jordan Ellenberg, date=2021-10-06, title=The Math of the Amazing Sandpile, url=http://nautil.us/issue/107/the-edge/the-math-of-the-amazing-sandpile, website=
Nautilus Quarterly
''Nautilus Quarterly'' is a New York-based online and print science magazine. It publishes one issue on a selected topic each month on its website, releasing one chapter each Thursday. Issue topics have included human uniqueness, time, uncertaint ...
*Phelps, Christopher (2021-11-05)
An interactive Python implementation of square-lattice models
Self-organization
Phase transitions
Dynamical systems
Critical phenomena
Nonlinear systems
Cellular automaton rules