On the Group of a Sandpile
Dominique Rossin
Lix, École polytechnique (France)
Algorithms Seminar
October 16, 2000
[summary by Dominique GouyouBeauchamps]
A properly typeset version of this document is available in
postscript and in
pdf.
If some fonts do not look right on your screen, this might be
fixed by configuring your browser (see the documentation here).
Abstract
The abelian sandpile model is a cellular automaton. Its rules
generalize the sandpile rules for general graphs. This model has been
introduced by Bak, Tang, and Wiesenfeld [1] in 1987.
Dhar [9] showed that the set of recurrent configurations
of this automaton has the structure of a finite abelian group.
In this talk, we describe several algorithms to determine the identity
in the group. This element presents fractal aspects that we are not
able yet to explain. These algorithms allow us to introduce
relationships between the sandpile group and wellknown algebraic or
combinatorial objects.
Details may be found in the recent works of R. Cori, D. Rossin, and
B. Salvy [6], and D. Rossin [12]. The
papers [1, 10], the book [2], and the
thesis [13] are good introductions to sandpiles.
1 Introduction
Let G=(V,E) be a nonoriented and connected multigraph
with V={1,...,n} its set of vertices and E a symmetric
n× n matrix whose entry e_{i,j} is the number of edges with
endpoints i, j. It is assumed that for any i, e_{i,i}=0 so
that the multigraph has no loops. Frequently, G is a graph, and
hence e_{i,j} is either 0 or 1. The degree of vertex i
in G is d_{i}=å_{j=1}^{n}e_{i,j}. A multigraph is rooted
if one of its vertices is distinguished, it is called the
sink and is numbered n.
A configuration u=(u_{1},...,u_{n})ÎN^{n} of G is a
vector of nonnegative integers. In the context of the sandpile
model, the vertices of the graph are cells, and the number u_{i} may
be interpreted as the height of a pile of grains of sand standing in
cell i. In the rest of this talk, the number of grains in the sink
is not taken into account. Thus two configurations u and v which
differ only in position n are considered as equal; we write u=v if
u_{i}=v_{i} for all 1£ i<n. This translates the fact that the sink
collects all grains of sand getting out of the system.
A toppling of the vertex i, 1£ i<n, in
configuration u consists in decreasing the number of grains in this
vertex by its degree while the number of those of each of its
neighbours j increases by e_{i,j}. This is equivalent to the
addition to u of the vector D_{i} such that (D_{i})_{i}=d_{i}
and (D_{i})_{j}=e_{i,j} for j¹ i. The notation
u¾® v means that v is obtained from u by
toppling a vertex, so that there exists an 1£ i<n such
that v=u+D_{i}. The transitive closure of the toppling operation
¾® is denoted :
u v if v is obtained from u by a
sequence of topplings. An avalanche is a sequence of
topplings (see Figures 1, 2
and 3).
The sandpile model has been introduced by Bak, Tang, and
Wiensenfeld [1] in 1987. In a recent book,
Bak [2] gives an overview of many physical
problemsearthquakes and solar flares for examplewhose models are
based on the sandpile one. All these models follow the
GutembergRichter law: logN=abM, logE=c+dM, and N~
E^{1t} (t»2) where M is the magnitude, N is
the number of topplings, and E is the energy. In three dimensions,
N~ E^{1t} (t» 2.5). A very similar automaton
was introduced independently by other authors under the name of the
chipfiring game [4, 11]. Biggs [3] found
many algebraic and combinatorial properties of the chipfiring game,
some of which correspond to Dhar's results on sandpiles [10].
In [5], we also showed a close relationship between
recurrent configurations of the complete graph and the parking
functions.
Figure 1: Multigraph corresponding to the 4×4 grid.
Figure 2: Topplings and avalanche on the 4×4 grid.
Figure 3: Topplings and avalanche on a graph.
2 The Sandpile Group
A vertex is stable if it contains a number of grains less
than its degree, otherwise this vertex is unstable. A
stable configuration is a configuration where all vertices
are stable. It is not difficult to prove that for every configuration
u there exists a stable configuration u^{^} such that
uu^{^}. Moreover this configuration is
unique, and the number of topplings is independent of the way in which
u^{^} is obtained from u [9].
Let u, v be two configurations. Let u_{i} (resp. v_{i}) be the
number of grains on vertex i in configuration u (resp. v). We
will denote by u+v the configuration w such that w_{i}=u_{i}+v_{i}. A
configuration u is recurrent if it is stable and if there
exists a configuration v¹0 such that u+v
u (see Figure 4). The simplest example of a
recurrent configuration is d=(d_{1}1,d_{2}1,...,d_{n1}1,0).
The set of recurrent configurations is isomorphic to the set of
equivalence classes defined by the symmetric closure º of
.
Let T_{G}(x,y) be the Tutte polynomial of the graph G. Then
T_{G}(1,y) is the the generating function (a polynomial) of the
recurrent configurations according to the number of sand grains.
We can associate to the set of recurrent configurations the operator
Å defined by uÅ v=u+v^{^} where u and v are
two recurrent configurations. The set of recurrent configurations
with the operation Å is an abelian group G [8],
this group is equal to the product
G=Õ_{i=1}^{n}Z/d_{i}Z and the group structure does not
depend on the sink choice in the graph G.
Let u=(u_{1},...,u_{n}) be a recurrent configuration. We
denote u^{_} the recurrent configuration
(d_{1}1u_{1},d_{2}1u_{2},...,d_{n1}1u_{n1},0). Then the identity
of the sandpile group is
Id=dÅ(dÅd) and the opposite of
a recurrent configuration u is IdÅ(dÅ u).
Figure 4: A recurrent configuration.
3 Toppling Ideal, Set Topplings and Minimal Gröbner Basis
Configurations and topplings are easily translated from the linear
algebra setting into polynomial operations by associating to a
configuration u=(u_{1}, u_{2},..., u_{n})ÎN^{n} a monomial
x_{u}=x_{1}^{u1}x_{2}^{u2}... x_{n}^{un} Î Q[x_{1},...,x_{n}]. To a
toppling D_{i} is associated the binomial
T(x_{i})=x_{i}^{di}Õ_{j}x_{j}^{ei,j}. The addition of two
configurations translates into the multiplication of the corresponding
monomials and toppling vertex i in u translates into the division
of x_{u} by x_{i}^{di} followed by the multiplication
by Õ_{j=1}^{n}x_{j}^{ei,j}. We define the toppling
ideal I_{G} as the ideal generated by x_{n}1 and the toppling
polynomials T(x_{i}) for iÎ{1,...,n}.
A toppling polynomial can also be associated to a subset X of the
set V of vertices as follows. For a vertex i of V, define
the number of edges with endpoints i and a vertex of X. The
set toppling of the set X in configuration u consists in
adding the vector D_{X} to u, where

( 
D_{X} 
) 
_{i}=

ì
ï
í
ï
î 

for iÎ X, 
d_{i}(X), 
for iÎX^{_}, 


where X^{_} denotes V\ X.
Accordingly, the toppling polynomial of the subset X of V
is defined by
Gröbner bases are a classical computational tool for dealing with
polynomial ideals. Given an ordering on monomials which is compatible
with the product (a socalled admissible ordering) and a set
of generators of an ideal I, one can compute a Gröbner basis for
I and from there test ideal membership and more generally compute
normal forms in the quotient of the algebra by I. The rest of
this work makes use of the notation and basic results
from [7, Chapter 2].
The graded reverse lexicographic order (grevlex) denoted
<, is defined as follows. If A=Õ_{i=1}^{n}x_{i}^{a i}
and B=Õ_{i=1}^{n}x_{i}^{b i} are two monomials in the variables
x_{i}, i=1,2,...,n, then A< B if
or a =b  and in
(a_{1},...,a_{n})(b_{1},...,b_{n}) the rightmost
nonzero entry is positive.
From there a toppling order is defined as follows: let
s be a permutation of {1,...,n} such that s (n)=n
and if the distance from vertex i to the sink is larger than the
distance from vertex j to the sink, then s (i)>s(j).
The toppling order is the graded reverse lexicographic order on
x_{s(1)}, x_{s(2)}, ..., x_{s(n)}.
Theorem 1 A Gröbner basis of the ideal I_{G} with respect to
a toppling order is given by
T= 
{ 
T(X)XÌ{1,...,n} 
} 
È{x_{n}1}. 
A Gröbner basis is minimal when its elements have leading
coefficient 1 and no leading monomial divides another leading monomial
in the basis. A subset X of vertices of the graph G=(V,E) is
wellconnected if both subgraphs of G induced by X and X^{_}
are connected.
Theorem 2 The set S_{c} of toppling polynomials corresponding to
the sets XÌ {1,2,...,n1} which are wellconnected is a
minimal Gröbner basis for the toppling order.
In the worst case, the minimal Gröbner basis still contains
2^{n1} elements for the complete graph.
As mentioned before, the quotient Q[x_{1},x_{2},...,x_{n}]/I_{G} is a
Qvector space whose dimension is the order of the group of
recurrent configurations. From a Gröbner basis for I_{G}, a basis
of this vector space is given by the set of monomials that do not
reduce to 0 by the basis. We call these reduced monomials.
Theorem 3 below gives a simple bijection between
reduced monomials for the toppling order and recurrent configurations.
Let F be the mapping from the set of stable configurations onto
itself given by F(u)=du. We also denote
F(M)=F(a_{1},a_{2},...,a_{n}) for a monomial
M=x_{1}^{a1}x_{2}^{a2}... x_{n}^{an}.
Theorem 3
The mapping F defines a bijection between the set of reduced
monomials with respect to the toppling order and the set of recurrent
configurations.
For a configuration u, let r(u) denote the reduced
configuration obtained from the monomial associated to u by
performing reductions by the Gröbner basis of I_{G} associated
with the toppling order.
Proposition 1
If u is a configuration then the recurrent configuration equivalent
to u is
The identity in the group of recurrent configurations
is F(r(d)).
Corollary 1 For two recurrent configurations u and v,
uÅ v=F 
( 
r 
( 
F(u)+F(v) 
) 
) 
. 
Figure 5: Multigraph with 4 vertices.
Figure 6: Representation of irreducible monomials.
Proposition 1 yields the following algorithm to
compute the identity on a graph G with sink s: beginning with the
configuration d, perform the set topplings for all
wellconnected subgraph of G\{s} (this is equivalent to
reducing by the Gröbner basis for the toppling order). When no
further set toppling can be performed, for each cell i replace its
number of grains n_{i} with d_{i}n_{i}. The resulting configuration is
the identity.
4 Examples
Our first example corresponds to the graph displayed on
Figure 5. The structure
of the graph is reflected by the toppling polynomials for the vertices:
x_{1}^{3}x_{2}^{2}x_{3}, x_{2}^{3}x_{1}^{2}x_{4}, x_{3}^{2}x_{1}x_{4},
x_{4}^{2}x_{2}x_{3}, x_{4}1.
The minimal Gröbner basis for the graded reverse lexicographic order
on monomials is
x_{3}^{2}x_{1}, x_{2}^{3}x_{1}^{2}, x_{1}^{3}x_{2}, x_{2}x_{3}1,
x_{2}x_{1}x_{3}, x_{3}x_{1}^{2}x_{2}^{2}, x_{4}1.
Apart from the last, these polynomials correspond respectively to
wellconnected subgraphs with vertices
{3}, {2}, {1}, {1,2,3}, {1,2},
{1,3}.
Given a Gröbner basis
G={p_{1},p_{2},...,p_{k}}ÌK[x_{1},x_{2},...,x_{n}] for some
field K, it is usual to represent the leading monomials of
the p_{i} on an integer lattice in n dimensions. Each
polynomial p is associated to a point c(p) whose coordinates are
the exponents of its leading monomial. The leading terms of the p_{i}
generate the ideal of leading terms of polynomials in the ideal.
These leading terms are thus exactly represented by È
c(p_{i})+N^{n}. This removes from N^{n} a staircase shape whose
lattice points correspond to the quotient (see
Figure 6). Their number is exactly the order of
the group of recurrent configurations. Note that in our example,
those seven monomials are {1,x_{1},x_{1}^{2},x_{2},x_{2}^{2},x_{3},x_{1}x_{3}}, none
of which correspond to a recurrent configuration. However, applying
F yields the recurrent configurations as explained above.
Our second example is the 2× 2 grid consisting of 4 cells, each
connected twice to the sink. The sandpile group of this grid, computed
for instance in [9], is the product of two cyclic group
of orders 24 and 8.
After the computation of the Gröbner basis of the ideal generated by
the toppling polynomials of vertices, it follows that x_{4} is of
order 24 and that any element can be expressed as a
product x_{3}^{i}x_{4}^{j} where 0£ i£ 7 and 0£ j£ 23, which
gives that the order of the group is 192. Also, since x_{1} and x_{2}
can be expressed in terms of x_{3} and x_{4}, it is seen that the
group has two generators.
References
 [1]

Bak (P.), Tang (C.), and Wiensenfeld (K.). 
An explanation of 1/f noise. Physical Review Letters,
vol. 59, n°4, July 1987, pp. 381384.
 [2]

Bak (Per). 
How nature works. 
Copernicus, New York, 1996, xiv+212p. The science of
selforganized criticality.
 [3]

Biggs (N. L.). 
Chipfiring and the critical group of a graph. Journal of
Algebraic Combinatorics, vol. 9, n°1, 1999, pp. 2545.
 [4]

Björner (Anders), Lovász (László), and Shor (Peter W.). 
Chipfiring games on graphs. European Journal of Combinatorics,
vol. 12, n°4, 1991, pp. 283291.
 [5]

Cori (Robert) and Rossin (Dominique). 
On the sandpile group of dual graphs. European Journal of
Combinatorics, vol. 21, n°4, 2000, pp. 447459.
 [6]

Cori (Robert), Rossin (Dominique), and Salvy (Bruno). 
Polynomial ideals for sandpiles and their Gröbner bases. 
Research Report n°3946, Institut National de Recherche en
Informatique et en Automatique, 2000. 20 pages. Submitted to
Elsevier Preprint.
 [7]

Cox (David), Little (John), and O'Shea (Donal). 
Ideals, varieties, and algorithms. 
SpringerVerlag, New York, 1997, second edition,
xiv+536p. An introduction to computational algebraic geometry and commutative
algebra.
 [8]

Creutz (M.). 
Abelian sandpile. Computers in Physics, vol. 5,
1991, pp. 198203.
 [9]

Dhar (D.), Ruelle (P.), Sen (S.), and Verma (D.N.). 
Algebraic aspects of abelian sandpile models. Journal of Physics
A, vol. 28, n°4, 1995, pp. 805831.
 [10]

Dhar (Deepak). 
Selforganized critical state of sandpile automaton models. Physical Review Letters, vol. 64, n°14, 1990,
pp. 16131616.
 [11]

Goles (Eric). 
Sand piles, combinatorial games and cellular automata. In Instabilities and nonequilibrium structures, III (Valparaíso, 1989),
pp. 101121. 
Kluwer Acad. Publ., Dordrecht, 1991. Vol. 64 in
Mathematics and its Applications.
 [12]

Rossin (D.). 
On the complexity of addition in the sandpile group of a graph. 
Submitted to Elsevier Preprint.
 [13]

Rossin (D.). 
Propriétés combinatoires de certaines familles d'automates
cellulaires. 
Thèse, École polytechnique, Palaiseau, France,
2000.
This document was translated from L^{A}T_{E}X by
H^{E}V^{E}A.