# The sandpile group

## 6.5. Recurrent sandpiles

**Definition 6.15.** The *reduced Laplacian lattice* $\tilde{\mathcal{L}}$ is the subgroup formed by the image of the reduced Laplacian:
$$\tilde{\mathcal{L}} = \text{im } \tilde{L} \subseteq \mathbb{Z}\tilde{V}$$

**Corollary 6.17.** The configuration $c'$ is obtained from $c$ through a sequence of vertex firings and reverse-firings if and only if $$c = c' \mod \tilde{\mathcal{L}}$$

**Definition 6.21.** The *maximal stable configuration* on $G$ is
$$c_{\text{max}} := \sum_{v\in \tilde{V}} (\text{outdeg}(v) - 1) v$$

**Proposition 6.22.** A configuration $c$ is recurrent if and only if there exists a configuration $b \geq 0$ such that $c = (c_{\text{max}} + b)^\circ$.

---

**Definition 6.25.** The *stable addition* of sandpiles $a$ and $b$, denoted $a \circledast b$, is defined as ordinary addition of group elements followed by stabilization:
$$a \circledast b := (a + b)^\circ$$

**Proposition 6.26.** Stable addition of sandpiles is associative.

**Proof.** The result follows by uniqueness of stabilization. Let $a, b, c$ be sandpiles. Since $c \geq 0$, the firing sequence that stabilizes $a + b$ is still legal for $a + b + c$, so $$a + b + c \rightsquigarrow (a + b)^\circ + c \rightsquigarrow ((a + b)^\circ + c)^\circ = (a \circledast b) \circledast c$$ Similarly, the sequence that stabilizes $b + c$ is legal for $a + b + c$, and we have
$$a + b + c \rightsquigarrow a + (b + c)^\circ \rightsquigarrow (a + (b + c)^\circ)^\circ = a \circledast (b \circledast c)$$ By uniqueness of stabilization, it follows that
$$(a \circledast b) \circledast c = (a + b + c)^\circ = a \circledast (b \circledast c)$$

**Definition 6.27.** The *sandpile monoid* is the set of nonnegative, stable configurations $\text{Stab}(G)$, with the operation of stable addition.

We now come to a central result for the abelian sandpile model. Recall that $\tilde{\mathcal{L}}$ denotes the image of the reduced Laplacian, i.e., $\tilde{\mathcal{L}} = \text{im } \tilde{L} \subseteq \mathbb{Z}\tilde{V}$.

**Theorem 6.28.** The set of recurrents, $S(G)$, is a group under stable addition, and
\begin{split}
S(G) &\to \mathbb{Z}{\tilde{V}} / \tilde{\mathcal{L}}\\
c &\mapsto c+\tilde{\mathcal{L}}
\end{split} is an isomorphism of groups.

The proof of this theorem is approached through several lemmas. For that purpose, consider $1_{\tilde{V}} := \sum_{v\in \tilde{V}} v$, the all ones configuration, and define the two configurations
\begin{split}
&c_{\text{big}} := c_{\text{max}} + 1_{\tilde{V}} = \sum_{v\in \tilde{V}} \text{outdeg}(v) v\\
&c_{\text{null}} := c_{\text{big}} - c^\circ_{\text{big}}
\end{split}

The configuration $c_{\text{null}}$ has two useful properties: $c_{\text{null}} = 0 \mod \tilde{\mathcal{L}}$ and $c_{\text{null}} \geq 1_{\tilde{V}}$.

**Lemma 6.29.** Each element of $\mathbb{Z}{\tilde{V}} / \tilde{\mathcal{L}}$ is represented by a recurrent configuration.

**Proof.** Given any configuration $c$, take $k \gg 0$ so that
$$c + kc_{\text{null}} \geq c_{\text{max}}$$ Working modulo $\tilde{\mathcal{L}}$, $$(c + kc_{\text{null}})^\circ \equiv c + kc_{\text{null}} \equiv c$$ and $(c+kc_{\text{null}})^\circ$ is recurrent since it can be formed by adding (a nonnegative amount of) sand to $c_{\text{max}}$ and stabilizing:
$$(c + kc_{\text{null}})^\circ = (c_{\text{max}} + (c + kc_{\text{null}} - c_{\text{max}}))^\circ \quad \square$$

**Lemma 6.30.** If $c$ is recurrent, then $(c_{\text{null}} + c)^\circ = c$.

**Proof.** Let $c$ be recurrent. From Proposition 6.22, there exists a sandpile $b \geq 0$ such that $(b + c_{\text{max}})^\circ = c$. Setting $a = b - 1_{\tilde{V}}$, it follows that $(a + c_{\text{big}})^\circ = c$. Then
\begin{split}
a + c_{\text{big}} + c_{\text{null}} &\rightsquigarrow (a + c_{\text{big}})^\circ + c_{\text{null}} \\\\ &= c + c_{\text{null}} \rightsquigarrow (c + c_{\text{null}})^\circ
\end{split}

and
\begin{align*}
a + c_{\text{big}} + c_{\text{null}} &= a + c_{\text{big}} + c_{\text{big}} - c^\circ_{\text{big}} \\\\
&\rightsquigarrow a + c_{\text{big}} + c^\circ_{\text{big}} - c^\circ_{\text{big}} \\\\
&= a + c_{\text{big}} \\\\
&\rightsquigarrow (a + c_{\text{big}})^\circ = c
\end{align*}

The result follows by uniqueness of stabilization. $\quad \square$

**Lemma 6.31.** There is a unique recurrent configuration in each equivalence class of $\mathbb{Z}{\tilde{V}}$ modulo $\tilde{\mathcal{L}}$.

**Proof.** By Lemma 6.29 there exists at least one recurrent configuration in each equivalence class of $\mathbb{Z}{\tilde{V}}$ modulo $\tilde{\mathcal{L}}$. Suppose $c'$ and $c''$ are recurrents and that $c' = c'' \mod \tilde{\mathcal{L}}$. Then $$c' = c'' + \sum_{v\in \tilde{V}} n_v \tilde{L}v$$ for some $n_v \in \mathbb{Z}$. Let $J_- := \{v : n_v < 0\}$ and $J_+ := \{v : n_v > 0\}$, and define $$c := c' + \sum_{v\in J_-} (-n_v) \tilde{L}v = c'' + \sum_{v\in J_+} n_v \tilde{L}v$$ Take $k \gg 0$ so that for every $v \in \tilde{V}$, $$(c + kc_{\text{null}})(v) \geq \max_{w\in \tilde{V}} \{|n_w| \text{outdeg}(w)\}$$ Thus, each vertex $v$ of $c + kc_{\text{null}}$ can be legally fired $|n_v|$ times. Therefore, \begin{align*}
c + kc_{\text{null}} &= c' + \sum_{v\in J_-} (-n_v) \tilde{L}v + kc_{\text{null}} \\\\
&\rightsquigarrow c' + kc_{\text{null}} \\\\
&\rightsquigarrow c'
\end{align*} the last step following from repeat applications of Lemma 6.30. Similarly, we have $c + kc_{\text{null}} \rightsquigarrow c''$. By uniqueness of stabilization, $c' = c''. \quad \square$

We now prove Theorem 6.28.

**Proof.** The mapping $$\begin{split}
S(G) &\to \mathbb{Z}{\tilde{V}} / \tilde{\mathcal{L}}\\
c &\mapsto c+\tilde{\mathcal{L}}
\end{split}$$ respects addition by Proposition 6.16. It is surjective by Lemma 6.29 and injective by Lemma 6.31. $\quad \square$

**Definition 6.32.** The *sandpile group* of $G$, denoted $S(G)$, is the set of recurrent configurations with stable addition.

As a consequence of Theorem 6.28, we can determine the structure of $S(G)$ by computing the *Smith normal form* of $\tilde{L}$. Details appear in Chapter 2. The size of the sandpile group may be calculated as follows.

**Proposition 6.33.** $$|S(G)| = |\det(\tilde{L})|$$

**Proof.** The proof given for Proposition 2.37 holds equally well here, for directed graphs. $\ \square$

**Remark 6.34.** As pointed out after Proposition 2.37, $\det(\tilde{L})$ is the number of spanning trees (in this case directed, rooted spanning trees into the sink), and hence positive. Thus we actually have $$|S(G)| = \det(\tilde{L})$$

**Exercise 6.35.** Let $G$ be a triangle with an edge of multiplicity 3 to the sink, $s$.
(1) Find the number of elements in $S(G)$ using Proposition 6.33.
(2) Find all the recurrents on $G$.

**Sol.** \begin{split}&|S(G)| = |\det(\tilde{L})| = |\det(\begin{pmatrix} 4 & -1 \\ -1 & 2 \end{pmatrix})|=7\\\\
&S(G)=\{(0,1), (1, 0), (1,1), (2, 0), (2, 1), (3, 0), (3, 1)\}\\\\
&\begin{pmatrix} 4 & -1 \\ -1 & 2 \end{pmatrix} \to \begin{pmatrix} -1 & 2 \\ 4 & -1 \end{pmatrix} \to \begin{pmatrix} -1 & 2 \\ 0 & 7 \end{pmatrix} \to \begin{pmatrix} 1 & 0 \\ 0 & 7 \end{pmatrix} \Longrightarrow S(G)\cong \mathbb{Z}_7
\end{split}

---

### 6.5.1 The identity

The zero configuration is rarely recurrent. Hence, even though $(0 + c)^\circ = c$ for all configurations $c$, it is seldom the case that 0 is the identity of the sandpile group. And if the identity is not 0, then what is it? That's an unusual question to ask about a group! A glance at the images of identity elements on grid graphs in Section 6.6 indicates some of the complexity.

We at least have a way of calculating the identity:

**Proposition 6.36.** The identity of $S(G)$ is
$$(2 c_{\text{max}} - (2 c_{\text{max}})^\circ)^\circ$$

**Proof.** The displayed element is recurrent since
$$(2 c_{\text{max}} - (2 c_{\text{max}})^\circ)^\circ = (c_{\text{max}} + \underbrace{(c_{\text{max}} - (2 c_{\text{max}})^\circ)}_{\geq 0})^\circ$$ and as an element of $\mathbb{Z}{\tilde{V}} / \tilde{\mathcal{L}}$ it is equal to (the equivalence class of) 0, the identity of $\mathbb{Z}{\tilde{V}} / \tilde{\mathcal{L}}$. This completes the proof since the isomorphism $S(G) \to \mathbb{Z}{\tilde{V}} / \tilde{\mathcal{L}}$ preserves the identity. $\quad \square$

**Example 6.37.** Let $G$ be the diamond graph with vertex order $v_1, v_2, v_3, s$.
Then $c_{\text{max}} = (2, 2, 1)$. One may check that $$2 c_{\text{max}} = (4, 4, 2) \rightsquigarrow (2, 2, 0) = (2c_{\text{max}})^\circ$$ with firing script $(3, 3, 4)$, and $$2 c_{\text{max}} - (2 c_{\text{max}})^\circ = (2, 2, 2) \rightsquigarrow (2, 2, 0)$$ Hence, the sandpile identity for $G$ is $(2, 2, 0)$.

Note that the number of elements in $S(G)$ is $$\det(\begin{pmatrix} 3 & -1 &-1 \\ -1 & 3 & -1 \\ -1 & -1 & 2 \end{pmatrix})=8$$ and it is not easy see the structure of $S(G)$ directly. We may consider the smith normal form of $\tilde{L}$ :
\begin{split}
\begin{pmatrix} 3 & -1 &-1 \\ -1 & 3 & -1 \\ -1 & -1 & 2\end{pmatrix} &\to \begin{pmatrix} -1 & 3 & -1 \\ 3 & -1 &-1 \\ -1 & -1 & 2\end{pmatrix}\\\\ &\to \begin{pmatrix} 1 & 0 & 0 \\ 0 & 8 &-4 \\ 0 & -4 & 3\end{pmatrix} \\\\
&\to \begin{pmatrix} 1 & 0 & 0 \\ 0 & 1 &0 \\ 0 & 0 & 8\end{pmatrix}\\\\
&\Longrightarrow S(G)\cong \mathbb{Z}_8
\end{split}

**Example.** Compute the invariant factors for the sandpile group of the complete graph $K_n$.

**Sol.** The reduced Laplacian for $K_n$ is the $(n-1) \times (n-1)$ matrix $nI-J$ , which we partition as $$\begin{pmatrix}
n-1 & -u^t \\
-u & nI-J
\end{pmatrix}$$ where $u$ is the all-1 column vector, and $I, J$ are now $(n-2) \times (n-2)$ matrices. Let $$R_1 = \begin{pmatrix}
1 & u^t \\
u & I+J
\end{pmatrix}, \quad
R_2 = \begin{pmatrix}
1 & -u^t \\
0 & I
\end{pmatrix}.$$ Then $\det R_1 = \det R_2 = 1$. Furthermore, $$R_1 \tilde{L} R_2 = \begin{pmatrix}
1 & 0 \\
0 & nI
\end{pmatrix}$$ It follows that the invariant factors of $\tilde{L}$ are $1$ and $n$ ($n-2$ times), and so the sandpile group $S(K_n)$ is the direct sum of $n-2$ copies of $\mathbb{Z}/n\mathbb{Z}$.

---

## 6.6 Images of sandpiles on grid graphs

The $m \times n$ *sandpile grid graph* has non-sink vertices
$$\tilde{V} := \{(i, j) \in \mathbb{Z}^2 : 1 \leq i \leq m, 1 \leq j \leq n\}$$

with edges between horizontal and vertical neighbors: $(i, j), (i', j') \in \tilde{V}$ are adjacent if
$$|i - i'| + |j - j'| = 1$$

Vertices on the boundary are connected to the sink vertex $s$. So if $i \in \{1, m\}$ or $j \in \{1, n\}$, then $(i, j)$ is adjacent to the sink. Further, each of the four corner vertices, $(1, 1)$, $(1, n)$, $(m, 1)$, and $(m, n)$, is connected by an extra edge to the sink (two in total). Thus, every non-sink vertex has degree 4. Figure 9 shows the $4 \times 4$ sandpile grid graph.

* identity

* Figure 12 represents the stabilization of a sandpile initially consisting of $2^{24}$ grains of sand in the center of an enormous rectangular grid graph—large enough so that no grain falls into the sink during stabilization.

* Figure 13 displays the identity element on a hexagonal grid for which each vertex now has 6 neighbors.

---

# Burning and duality

## 7.1. Burning sandpiles

Let $G = (V, E, s)$ be a sandpile graph with sink $s$. If $W \subseteq V$ and $v \in V$, we define the *indegree of $v$ with respect to* $W$ to be
$$\text{indeg}_W(v) = |\{w \in W : (w, v) \in E\}|$$

**Definition 7.2.** A vertex $v \in \tilde{V} = V \setminus \{s\}$ is *selfish* if $\text{indeg}_{\tilde{V}}(v) > \text{outdeg}(v)$.

**Definition 7.3.** The *support* of a configuration $c$ on $G$ is
$$\text{supp}(c) := \{v \in \tilde{V} : c(v) \neq 0\}$$

The *closure of the support* of $c$, denoted $\overline{\text{supp}(c)}$, is the set of non-sink vertices accessible from $\text{supp}(c)$ via a directed path in $G$ that avoids the sink.

**Definition 7.4.** A nonnegative configuration $b$ on $G$ is a *burning sandpile* if
1. $b \equiv 0 \mod \tilde{\mathcal{L}}$
1. $\overline{\text{supp}(b)} = \tilde{V}$

If $b$ is a burning sandpile, we call $\sigma_b := \tilde{L}^{-1}b$ its *(burning) script*.

**Theorem 7.5.** Let $b$ be a burning sandpile for $G$ with burning script $\sigma_b$. Let $e$ be the identity of $S(G)$. Then
1. $(kb)^\circ = e$ for some $k \gg 0$.
:::spoiler **Proof**
By choosing $k$ large enough and selectively firing unstable vertices, property 2 of the definition of a burning sandpile says $kb \rightsquigarrow c + c_{\text{max}}$ for some sandpile $c$. Thus, $(kb)^\circ$ is recurrent since it can be obtained from $c_{\text{max}}$ by adding sand and stabilizing. The unique recurrent configuration equal to 0 modulo $\tilde{\mathcal{L}}$ is the identity element. Hence, $(kb)^\circ = e. \quad \square$
2. A sandpile $c$ is recurrent if and only if $(b + c)^\circ = c$.
:::spoiler **Proof**
($\Rightarrow$) If $c$ is recurrent, then so is $(b + c)^\circ$. However, since $c \equiv (b + c)^\circ \mod \tilde{\mathcal{L}}$, we conclude $c = (b + c)^\circ$ by uniqueness of recurrent representatives, as just above.
($\Leftarrow$) Suppose $c = (b + c)^\circ$. Using part (1), fix $k \gg 0$ so that $(kb)^\circ = e$. Then $$c = (kb + c)^\circ = (e + c)^\circ$$ Since $e$ is recurrent, so is $c. \quad \square$
3. A sandpile $c$ is recurrent if and only if the firing script for the stabilization $(b + c) \rightsquigarrow (b + c)^\circ$ is $\sigma_b.$
:::spoiler **Proof**
Let $\phi$ be the firing script for $b + c \rightsquigarrow (b + c)^\circ$. Then \begin{align*} c \text{ is recurrent} &\Leftrightarrow (b + c)^\circ = c \quad \text{ (by(2))}\\ &\Leftrightarrow b + c - \tilde{L}\phi = c \\ &\Leftrightarrow b = \tilde{L}\phi \\ &\Leftrightarrow \phi = \tilde{L}^{-1}b = \sigma_b. \quad \square \end{align*}
4. $\sigma_b \geq \chi_{\tilde{V}}$ where $\chi_{\tilde{V}}$ is the firing script corresponding to firing all non-sink vertices.
:::spoiler **Proof**
Since $c_{\text{max}}$ is recurrent, the firing script for $$(b + c_{\text{max}}) \rightsquigarrow (b + c_{\text{max}})^\circ \overset{(2)}{=} c_{\text{max}}$$ is $\sigma_b$ by part (3). Let $v \in \tilde{V}$. Since $b$ is a burning sandpile, there exists $w \in \text{supp}(b)$ and a directed path $v_1, v_2, \ldots, v_m$ in $G$ with $w = v_1$ and $v_m = v$. Then $v_1, \ldots, v_m$ is a legal firing sequence for $b + c_{\text{max}}$. Recall that the firing script is independent of any particular firing sequence. Thus, each non-sink vertex fires at least once in the stabilization of $b + c_{\text{max}}$. So $\sigma_b \geq \chi_{\tilde{V}}. \quad \square$
5. Suppose $c$ is a stable configuration and $\beta$ is the firing script for $(b+c) \rightsquigarrow (b+c)^\circ$. Then $\beta \leq \sigma_b$.
:::spoiler **Proof**
Suppose $c$ is a stable configuration and $\beta$ is the legal firing script stabilizing $b + c$. Then $c \leq c_{\max}$ so $\beta$ is also legal for $c_{\max} +b$. Since $c_{\max}$ is recurrent, by (3), we must have $\beta \leq \sigma_b. \quad \square$

---