On the Group of a Sandpile

Dominique Rossin

Lix, École polytechnique (France)

Algorithms Seminar

October 16, 2000

[summary by Dominique Gouyou-Beauchamps]

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 well-known 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 non-oriented and connected multi-graph with V={1,...,n} its set of vertices and E a symmetric n× n matrix whose entry ei,j is the number of edges with endpoints ij. It is assumed that for any i, ei,i=0 so that the multi-graph has no loops. Frequently, G is a graph, and hence ei,j is either 0 or 1. The degree of vertex i in G is di=åj=1nei,j. A multi-graph is rooted if one of its vertices is distinguished, it is called the sink and is numbered n.

A configuration u=(u1,...,un)ÎNn of G is a vector of non-negative integers. In the context of the sandpile model, the vertices of the graph are cells, and the number ui 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 ui=vi 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 ei,j. This is equivalent to the addition to u of the vector Di such that (Di)i=-di and (Di)j=ei,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+Di. 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 problems---earthquakes and solar flares for example---whose models are based on the sandpile one. All these models follow the Gutemberg--Richter law: logN=a-bM, logE=c+dM, and N~ E1-t (t»2) where M is the magnitude, N is the number of topplings, and E is the energy. In three dimensions, N~ E1-t (t» 2.5). A very similar automaton was introduced independently by other authors under the name of the chip-firing game [4, 11]. Biggs [3] found many algebraic and combinatorial properties of the chip-firing 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: Multi-graph 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 u
*
¾®
u^. Moreover this configuration is unique, and the number of topplings is independent of the way in which u^ is obtained from u [9].

Let uv be two configurations. Let ui (resp. vi) be the number of grains on vertex i in configuration u (resp. v). We will denote by u+v the configuration w such that wi=ui+vi. 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=(d1-1,d2-1,...,dn-1-1,0). The set of recurrent configurations is isomorphic to the set of equivalence classes defined by the symmetric closure º of
*
¾®
.

Let TG(x,y) be the Tutte polynomial of the graph G. Then TG(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=1nZ/diZ and the group structure does not depend on the sink choice in the graph G.

Let u=(u1,...,un) be a recurrent configuration. We denote u_ the recurrent configuration (d1-1-u1,d2-1-u2,...,dn-1-1-un-1,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=(u1, u2,..., un)ÎNn a monomial xu=x1u1x2u2... xnun Î Q[x1,...,xn]. To a toppling Di is associated the binomial T(xi)=xidi-Õjxjei,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 xu by xidi followed by the multiplication by Õj=1nxjei,j. We define the toppling ideal IG as the ideal generated by xn-1 and the toppling polynomials T(xi) 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
di(X)=
 
å
jÎ X
ei,j,
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 DX to u, where
( DX ) i=
ì
ï
í
ï
î
-di(
_
X
 
),
for iÎ X,
di(X), for iÎX_,
where X_ denotes V\ X.

Accordingly, the toppling polynomial of the subset X of V is defined by
T(X)=
 
Õ
iÎ X
x
di(
_
X
 
)
 
i
-
 
Õ
iÎ
_
X
 
xidi(X).

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 so-called 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=1nxia i and B=Õi=1nxib i are two monomials in the variables xi, i=1,2,...,n, then A< B if
|a |=
n
å
i=1
ai<|b|=
n
å
i=1
bi
or |a |=|b | and in (a1,...,an)-(b1,...,bn) the right-most non-zero 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 xs(1), xs(2), ..., xs(n).
Theorem 1   A Gröbner basis of the ideal IG with respect to a toppling order is given by
T= {  T(X)|XÌ{1,...,n } È{xn-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 well-connected if both subgraphs of G induced by X and X_ are connected.
Theorem 2   The set Sc of toppling polynomials corresponding to the sets XÌ {1,2,...,n-1} which are well-connected is a minimal Gröbner basis for the toppling order.

In the worst case, the minimal Gröbner basis still contains 2n-1 elements for the complete graph.

As mentioned before, the quotient Q[x1,x2,...,xn]/IG is a Q-vector space whose dimension is the order of the group of recurrent configurations. From a Gröbner basis for IG, 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)=d-u. We also denote F(M)=F(a1,a2,...,an) for a monomial M=x1a1x2a2... xnan.
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 IG associated with the toppling order.
Proposition 1   If u is a configuration then the recurrent configuration equivalent to u is
F ( r ( F ( r(u) ) ) ) .
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 well-connected 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 ni with di-ni. 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:
x13-x22x3,   x23-x12x4,   x32-x1x4,   x42-x2x3,   x4-1.

The minimal Gröbner basis for the graded reverse lexicographic order on monomials is
x32-x1,   x23-x12,   x13-x2,   x2x3-1,   x2x1-x3,   x3x12-x22,   x4-1.

Apart from the last, these polynomials correspond respectively to well-connected subgraphs with vertices
{3},   {2},   {1},   {1,2,3},   {1,2},   {1,3}.

Given a Gröbner basis G={p1,p2,...,pk}ÌK[x1,x2,...,xn] for some field K, it is usual to represent the leading monomials of the pi 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 pi generate the ideal of leading terms of polynomials in the ideal. These leading terms are thus exactly represented by È c(pi)+Nn. This removes from Nn 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,x1,x12,x2,x22,x3,x1x3}, 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 x4 is of order 24 and that any element can be expressed as a product x3ix4j where 0£ i£ 7 and 0£ j£ 23, which gives that the order of the group is 192. Also, since x1 and x2 can be expressed in terms of x3 and x4, 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. 381--384.

[2]
Bak (Per). -- How nature works. -- Copernicus, New York, 1996, xiv+212p. The science of self-organized criticality.

[3]
Biggs (N. L.). -- Chip-firing and the critical group of a graph. Journal of Algebraic Combinatorics, vol. 9, n°1, 1999, pp. 25--45.

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

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

[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. -- Springer-Verlag, 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. 198--203.

[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. 805--831.

[10]
Dhar (Deepak). -- Self-organized critical state of sandpile automaton models. Physical Review Letters, vol. 64, n°14, 1990, pp. 1613--1616.

[11]
Goles (Eric). -- Sand piles, combinatorial games and cellular automata. In Instabilities and nonequilibrium structures, III (Valparaíso, 1989), pp. 101--121. -- 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 LATEX by HEVEA.