A Stochastic Variant of the Abelian Sandpile Model

Abstract

We introduce a natural stochastic extension, called SSP, of the abelian sandpile model (ASM), which shares many mathematical properties with ASM, yet radically differs in its physical behavior, for example in terms of the shape of the steady state and of the avalanche size distribution. We establish a basic theory of SSP analogous to that of ASM, and present a brief numerical study of its behavior. Our original motivation for studying SSP stems from its connection to the LLL algorithm established in another work by Ding et al. (LLL and stochastic sandpile models, https://sites.google.com/view/seungki/). The importance of understanding how LLL works cannot be stressed more, especially from the point of view of lattice-based cryptography. We believe SSP serves as a tractable toy model of LLL that would help further our understanding of it.

1 Introduction

1.1 Overview

Let us start by recalling ASM ([3, 5], also see [6]) on a one-dimensional lattice. Let $A_L$ be the cycle graph whose vertices $V(A_L)$ consist of $L+1$ elements, say $V(A_L) = \{v_1, \ldots , v_{L+1}\}$, and the (undirected) edges are defined by $E(A_L) = \{(v_i, v_{i+1}): i = 1, \ldots , L\} \cup \{(v_{L+1}, v_1)\}$. We designate $v_{L+1}$ as the sink. Fix two positive integers T and I, preferably $T \ge 2I$.

We temporarily refer to I as the “toppling strength” and T as the threshold. That is, toppling at site $v_i$ is to subtract 2I grains from the pile on $v_i$ and add I grains to each of its neighbors. A configuration on $A_{L}$ is called stable if and only if all non-sink vertices have $< T$ grains. Fix another positive integer J coprime to I, preferably $J \approx I$. One then considers the following Markov chain on the space of the stable configurations of ASM: given a stable configuration on $A_L$, obtain the next stable configuration by first adding J grains to any randomly chosen non-sink site, and then stabilizing the resulting configuration.¹

On the other hand, consider the following simple stochastic variant of ASM, which we named SSP. SSP is exactly the same as ASM except for the toppling procedure: first one samples $\gamma$ uniformly from $\{1, 2, \ldots , 2I\}$ (so that $\gamma$ has mean $\approx I$) and then subtract $2\gamma$ grains from site $v_i$ and add $\gamma$ to each of the two neighboring sites. One can of course associate a Markov chain to SSP analogously to the above discussion: add I grains to a random site and then stabilize.

Our original motivation for studying SSP does not come from physics, but from a study of the practical behavior of the LLL algorithm [10]. The LLL algorithm is one of the fundamental tools in computational mathematics used for lattice basis reduction, with numerous applications to number theory and cryptography—see the book [13] for an extensive treatment on the subject. Despite its celebrated status, much of its behavior in practice has been shrouded in complete mystery. For example, the most well-known problem concerns the quantity called the root Hermite factor (RHF), defined as

$$\begin{aligned} \log \text{(RHF) } = \frac{1}{(L+1)^2}\sum _{i=1}^{L}(L+1-i)r_i, \end{aligned}$$

(1)

where $r_i$ is the pile height at $v_i$, in sandpile language. From the physical perspective, one could think of RHF as an average pile height, weighted in a certain way. It is a theorem from [10] that the RHF of LLL has a sharp upper bound by $(4/3)^{1/4} \approx 1.075$, but empirically one observes RHF $\approx 1.02$ most of the time—see [12] for details. This phenomenon has been well-known since the birth of LLL in 1982, yet there has been not even a vague heuristic as to why this must happen.

Recently, we argued in [7] that LLL behaves like a sandpile model, and that this idea explains much of its practical behavior all at once, in particular this RHF problem. The remaining difficulty is that LLL as a sandpile model is nonabelian, which is difficult to study analytically. This motivated us to propose SSP, as an abelian toy model for LLL.

Figure 1 compares the empirical average steady state density of LLL and SSP. The resemblance therein should come as surprising, since the two algorithms originate from very different fields of study, lattice reduction and statistical physics, respectively. We hope that the present paper helps build a bridge between them, to the benefit of both areas.

Fig. 1

The empirical steady state density profile of LLL (left) and SSP (right), with $L = 100$. x- and y-axes represent the site index and the height, respectively. It would be ideal to take a higher L, but then running LLL would become cumbersome, which has complexity $O(L^5)$

1.2 In This Paper

In the next section, we develop a basic mathematical theory of SSP. As in the case of ASM, we impose a monoid structure on the set of stable configurations, which we show is abelian (Theorem 4), and we prove the existence of the unique steady state (Theorem 5). Many of our results can be proved using the operator algebra method e.g. as in [15], but here we introduce a different idea, which is useful for picturing the “shape” of the steady state. With its help we are able to prove that the average $\log (\mathrm {RHF})$ of SSP over the steady state is strictly bounded away from the worst-case by a constant independent of system size L (Proposition 8). This is precisely what one wants to show with LLL, and hopefully our idea generalizes to this case, the only obstacle being its non-abelian toppling rule.

In Sect. 3, we provide some preliminary numerical studies on the statistical behavior of SSP, concerning its avalanche size distribution and its steady state. Though we still need a more extensive investigation, it seems that SSP has much in common with other one-dimensional stochastic models, such as the abelian Manna model and the Oslo rice-pile model. From the LLL perspective, it is especially interesting that these seemingly unrelated models exhibit the same boundary phenomenon as can be seen in Figure 1 (see [8] and [15]).

1.3 Related Works

There exists a number of stochastic extensions of ASM in the literature, each randomizing different aspects of ASM. The Oslo model [8] mentioned above topples the same as ASM, but the threshold at each site is set to random at the beginning and after toppling on that site. The sticky rice model [11] again topples the same as ASM, but with a random probability a site is regarded stable regardless of its height, hence “sticky”—one may think of this as the Oslo model in which there is a nonzero probability that the threshold is $\infty$. In the continuous conserved Manna model (CCMM) of [1], the toppling method is randomized as in SSP; however, unlike SSP, it is not the amount of sand taken from the toppled site but its distribution among its neighbors that is randomized—see [2] for another example along this line.

It seems to us that our method here can be adapted to the above-mentioned models as well, quite straightforwardly for CCMM because the thresholds are fixed, and less so for others but possible, by assigning a separate coordinate for each possible threshold value. Possibly the resulting steady state is more convenient to analyze than that of SSP.

2 Mathematical Properties of SSP

2.1 Setup

In the literature on sandpiles, there seem to exist two sets of notations, one that is physics-oriented and one that is mathematics-oriented—heights versus configurations, sites versus vertices, relaxations versus stabilizations, and so on. This paper mostly uses the latter, and there are several words that we made up ourselves. In any case, we provide the definition of every term that we use below.

Like ASM, SSP is played on a finite undirected graph $G = (V,E)$, equipped with a designated vertex called sink, which we denote here by s. Throughout this paper, we assume that the graph obtained from G by removing s is connected. In addition, let $\wp$ be a probability mass function supported on a finite subset of $\mathbb {Z}_{>0}$, and let T be an integer satisfying $T \ge \max \{i: i \in \mathrm {supp}\, \wp \}$, which we sometimes refer to as the threshold.

A pure configuration is a function $c: V \backslash \{s\} \rightarrow \mathbb {Z}$. A (mixed) configuration is a formal finite sum of pure configurations of form $\sum p_i [c_i]$, where $p_i$ are positive real numbers such that $\sum p_i = 1$, and $c_i$ are pure configurations. The role the bracket notation [.] here is to clarify that this is a formal sum. We define configurations this way, since toppling in SSP leads to multiple probabilistic results, as will be explained below.

A pure configuration c is called stable if $c(v) < T$ for all $v \in V \backslash \{s\}$, and called nonnegative if $c(v) \ge 0$ for all $v \in V \backslash \{s\}$. A configuration is called stable or nonnegative if it is a formal sum of stable or nonnegative pure configurations, respectively.

Toppling a pure configuration c at a non-sink vertex v goes as follows: (i) sample $\gamma$ according to $\wp$, (ii) subtract $\gamma \cdot \mathrm {deg}(v)$ from c(v) iii) for each $w \sim v$ add $\gamma \cdot \mathrm {deg}(v,w)$ to c(w), where $w \sim v$ means $(w,v) \in E$, and $\mathrm {deg}(v,w)$ is the number of edges connecting v and w. Denote the outcome by $T_v(c)$. If $c(v) \ge T$, we call this toppling legal. It is clear that, unless $\wp$ is supported on a singleton set, toppling a pure configuration results in a mixed configuration.

A choice algorithm is a map ${\mathcal {A}}: \{\text{ unstable } \text{ pure } \text{ configurations }\} \rightarrow V \backslash \{s\}$, such that $c({\mathcal {A}}(c)) \ge T$. Fixing a choice algorithm ${\mathcal {A}}$, we can define what it means to topple a mixed configuration $C = \sum p_i[c_i]$. For a pure configuration c, define

$$\begin{aligned} T(c) := T_{{\mathcal {A}}(c)}. \end{aligned}$$

Then we define $T(C) := \sum p_i T(c_i)$, the outcome of toppling C once. The stabilization$C^\circ$ of C is the outcome of toppling C repeatedly until it becomes stable. Later we will show that $C^\circ$ is independent of ${\mathcal {A}}$.

Remark

It is possible to extend the definition of a choice algorithm to a map into the set of probability mass functions on $V\backslash \{s\}$, so that ${\mathcal {A}}(c)(v)$, the probability that toppling occurs at v when the current configuration is c, is nonzero only if $c(v) \ge T$, and

$$\begin{aligned} T(c) := \sum _{v \in V\backslash \{s\}} {\mathcal {A}}(c)(v)T_v(c). \end{aligned}$$

All the results in this paper carry over to this generalization.

As in the case of ASM, we can define an operation $\oplus$ on the set of nonnegative stable configurations. If c and d are pure stable configurations, we define $c \oplus d = (c+d)^\circ$, where $c+d$ is defined so that $(c+d)(v) = c(v) + d(v)$. In general, if $C = \sum p_i[c_i]$ and $D = \sum q_j[d_j]$, then we define $C + D = \sum _{i,j} p_iq_j[c_i + d_j]$ and accordingly $C \oplus D = (C + D)^\circ = \sum _{i,j} p_iq_j[c_i \oplus d_j]$.

Because we assumed that $T \ge \max \{i: i \in I\}$, for any nonnegative configurations c and d, $c \oplus d = (c+d)^\circ$ is nonnegative as well. Later, we will show that $\oplus$ is abelian and associative, that the set of nonnegative stable configurations form a semigroup under this operation, whose minimal ideal consists of a single element which is the steady state.

2.2 Stabilization is Independent of Choice Algorithms

We start by defining what we temporarily call an increment stack. An increment stack consists of $|V \backslash \{s\}|$ sequences, each of which is indexed by an element of $V \backslash \{s\}$, whose entries are chosen from the elements of $\mathrm {supp}\,\wp$; thus it has the form $S = (\gamma _{v,i})_{\begin{array}{c} v \in V \backslash \{s\} \\ i \ge 1 \end{array}}$, with each $\gamma _{v,i} \in \mathrm {supp}\, \wp$. The set of all increment stacks is given a topology and a measure as follows: the cylinder sets, i.e. sets of form $Y(m, (v_k, i_k, p_k)_{k=1}^{m}) = \{(\gamma _{v,i})_{\begin{array}{c} v \in V \backslash \{s\} \\ i \ge 1 \end{array}} : \gamma _{v_k,i_k} = p_k, k = 1, \ldots , m\}$, form the base for the closed sets, and the measure $\mu$ is defined by $\mu (Y(m, (v_k, i_k, p_k)_{k=1}^{m})) = \prod _{k=1}^m \wp (p_k)$. This notion simulates the randomness in the amount being toppled during a stabilization process: SSP is equivalent to first sampling an increment stack S according to $\mu$, and if one must topple at v for the i-th time, remove $\gamma _{v,i} \cdot \mathrm {deg}(v)$ unit of sand from v and distribute it equally among the neighbors of v (respecting the multiplicities).

For a function $k: V\backslash \{s\} \rightarrow \mathbb {Z}_{\ge 0}$, a substackS(k(v)) of an increment stack $S = (\gamma _{v,i})_{\begin{array}{c} v \in V \backslash \{s\} \\ i \ge 1 \end{array}}$ is a finite-length sequence of form $(\gamma _{v,i(v)})_{\begin{array}{c} v \in V \backslash \{s\} \\ 1 \le i(v) \le k(v) \end{array}}$. We define the following partial order on the set of substacks: $S(k(v)) \le S(l(v))$ if $k(v) \le l(v)$ for $v \in V\backslash \{s\}$. Given a pure configuration c, if for every $v \in V\backslash \{s\}$

$$\begin{aligned} c(v) - \sum _{i=1}^{k(v)} \gamma _{v,i} \cdot \mathrm {deg}(v) + \sum _{w \sim v} \sum _{i=1}^{k(w)} \gamma _{w,i}\mathrm {deg}(w,v) < T, \end{aligned}$$

or equivalently, if toppling, legally or illegally, according to S(k(v)) stabilizes c—then S(k(v)) is called a stabilizing substack of c.

Lemma 1

For any given increment stack S and pure configuration c, there exists a unique minimal stabilizing substack of c.

Proof

Suppose $P := S(k(v))$ and $Q := S(l(v))$ are two distinct minimal stabilizing substacks. Define $r(v) = \min (k(v),l(v))$, and let $R := S(r(v))$ be another substack; by assumption $R < P$ and $R < Q$. Then, for every non-sink v,

$$\begin{aligned} c(v) - \sum _{i=1}^{r(v)} \gamma _{v,i} \cdot \mathrm {deg}(v) + \sum _{w \sim v} \sum _{i=1}^{r(w)} \gamma _{w,i}\mathrm {deg}(v,w) < T. \end{aligned}$$

Therefore R is a stabilizing substack, contradicting the minimality of P and Q. $\square$

Given an increment stack S and a pure configuration c, a choice algorithm ${\mathcal {A}}$ induces a stabilizing substack $S(k_{\mathcal {A}}(v))$, where $k_{\mathcal {A}}(v)$ is the number of times ${\mathcal {A}}$ would topple on v until it stabilizes c.

Proposition 2

Any choice algorithm induces the minimal stabilizing substack.

Proof

Write $M := S(m(v))$ for the minimal stabilizing substack, and $N := S(k_{\mathcal {A}}(v))$ for the substack induced by a choice algorithm ${\mathcal {A}}$. Imagine ${\mathcal {A}}$ toppling an input configuration c, one vertex at a time, and consider a situation in which ${\mathcal {A}}$ has just toppled on $v_1 \in V$ for $m(v_1)$ times, $v_1$ being the first vertex at which this occurs. Observe that, at this point, the configuration is stabilized at $v_1$. Hence ${\mathcal {A}}$ cannot topple more on $v_1$, at least not until it topples on some neighborhood w of $v_1$ more than m(w) times.

Suppose $v_2$ is the second vertex at which ${\mathcal {A}}$ topples on $v_2$ for $m(v_2)$ times. By the same argument as above, ${\mathcal {A}}$ cannot topple on $v_2$ more than $m(v_2)$ times until it topples on some $w \sim v_2$ more than m(w) times. Repeating, we see that on no vertices v can ${\mathcal {A}}$ topple more than m(v) times. This proves that $N \le M$, but since M is minimal we must have $M = N$.

$\square$

An immediate consequence of Proposition 2 is that, for any configuration C, pure or non-pure, its stabilization $C^\circ$ is independent of the choice algorithm ${\mathcal {A}}$. Indeed, $C^\circ$ is determined solely by the measure $\mu$ on the set of all increment stacks, and the minimal stabilizing substack of each increment stack. Therefore, the notion of a choice algorithm is somewhat superfluous from a theoretical viewpoint.

2.3 $\oplus$ is Abelian and Associative

It is clear by definition that $\oplus$ is abelian. We will now show that $\oplus$ is associative as well. Since $(F \oplus G) \oplus H = ((F + G)^\circ + H)^\circ$ and $F \oplus (G \oplus H) = (F + (G + H)^\circ )^\circ$, it suffices to show that

Proposition 3

For nonnegative configurations C and D,

$$\begin{aligned} (C^\circ + D)^\circ = (C + D)^\circ , \end{aligned}$$

(2)

or equivalently,

$$\begin{aligned} C^\circ \oplus D = C \oplus D. \end{aligned}$$

Proof

Assume first that C and D are pure configurations. Fix an increment stack $S = (\gamma _{v,i})_{\begin{array}{c} v \in V \backslash \{s\} \\ i \ge 1 \end{array}}$. Let S(k(v)) and S(l(v)) be the minimal stabilizing substacks for C and $C+D$, respectively. Note $S(k(v)) \le S(l(v))$—this is where we use the nonnegativity of C and D.

Consider the left-hand side of (2), namely $(C^\circ + D)^\circ$. A priori, we need two increment stacks for each of the two stabilizations: $T_1$ for the inner term $C^\circ$ and $T_2$ for the outer one. Write $S' = (\gamma _{v,i + k(v)})_{\begin{array}{c} v \in V \backslash \{s\} \\ i \ge 1 \end{array}}$. It suffices to prove that

$$\begin{aligned}&\mu (\{T_1: T_1(k(v)) = S(k(v))\}) \cdot \mu (\{T_2: T_2(l(v)-k(v)) = S'(l(v)-k(v))\}) \\&\quad = \mu (\{R: R(l(v)) = S(l(v))\}), \end{aligned}$$

or, in other words, that carrying out both stabilizations on the left-hand side of (2) using only one increment stack S induces no distortion on the measure $\mu$. But this is clear from the definition of $\mu$.

It remains to consider the case in which C and D are not necessarily pure configurations. Write $C = \sum p_i[c_i]$ and $D = \sum q_j[d_j]$. Then

$$\begin{aligned} C^\circ \oplus D = \sum p_iq_j(c_i^\circ \oplus d_j) = \sum p_iq_j(c_i \oplus d_j) = C \oplus D, \end{aligned}$$

as desired. $\square$

Remark

If the nonnegativity assumption is not present, Proposition 3 fails. In fact, it fails for ASM as well.

Thanks to our results so far, we have the following

Theorem 4

The set of all nonnegative stable configurations of a SSP forms a commutative monoid under $\oplus$.

2.4 The Existence of Unique Steady State

Denote the monoid in Theorem 4 by M. A steady state$S \in M$ is an element such that

$$\begin{aligned} S \oplus C = S \text{ for } \text{ all } C \in M\text{. } \end{aligned}$$

It is clear from this definition that a steady state, if exists, is unique.

Theorem 5

Assume the greatest common divisor of the elements of $\mathrm {supp}\, \wp$ equals 1. Then M has a steady state.

There is no loss of generality incurred by the assumption in the theorem, since if we divide all elements of $\mathrm {supp}\, \wp$ by the g.c.d. then we obtain essentially the same model.

Our proof of Theorem 5 relies almost entirely on the following lemma.

Lemma 6

Let $p: \{1, 2, \ldots , n\} \rightarrow \mathbb {R}_{\ge 0}$ such that $\sum p(i) = 1$, and such that the g.c.d. of the elements of $\mathrm {supp}\, p$ equals 1. Consider the $n \times n$ matrix

$$\begin{aligned} A = \begin{bmatrix} p(1)&1&0&0&\dots&0 \\ p(2)&0&1&0&\dots&0 \\ p(3)&0&0&1&\dots&0 \\ \vdots&\vdots&\vdots&\vdots&\ddots&\vdots \\ p(n)&0&0&\dots&\dots&0 \end{bmatrix} \end{aligned}$$

with the first column filled with p(i), the superdiagonal with 1, and 0 elsewhere. Then its (complex right) eigenvalue with the largest modulus is 1, which has multiplicity 1, with the eigenvector

$$\begin{aligned} \begin{bmatrix} r(1) \\ r(2) \\ \vdots \\ r(n) \end{bmatrix} \end{aligned}$$

(3)

where $r(k) = \sum _{i \ge k} p(i)$.

Proof

The characteristic equation of A equals

$$\begin{aligned} \chi _A(\lambda ) = \lambda ^n - p(1)\lambda ^{n-1} - \ldots - p(n-1)\lambda - p(n). \end{aligned}$$

We first show that 1 is an eigenvalue of multiplicity one. Certainly $\chi _A(1) = 0$. Also since

$$\begin{aligned} \chi '_A(\lambda ) = n\lambda ^{n-1} - (n-1)p(1)\lambda ^{n-2} - \ldots - p(n-1) \end{aligned}$$

and $n > (n-1)p(1) + \ldots p(n-1)$, $\chi '_A(1) \ne 0$. It is straightforward to check that (3) is a solution to $Ax = x$. This proves the latter two claims of the lemma.

If $|\lambda | > 1$, then $|\lambda |^n > \sum p(i)|\lambda |^{n-i}$, so it cannot be a root of $\chi _A$. Therefore it suffices to show that 1 is the only complex eigenvalue with modulus 1. Suppose $|\lambda | = 1$ and $\chi _A(\lambda ) = 0$. Then the triangle inequality implies that

$$\begin{aligned} | \chi _A(\lambda ) | \ge |\lambda ^n| - p(1)|\lambda ^{n-1}| - \ldots - p(n-1)|\lambda | - p(n) = 0, \end{aligned}$$

and that the equality holds if and only if all contributing powers of $\lambda$ point to the same direction, i.e. $\lambda ^{n-i} = \lambda ^n$ for all $i \in \mathrm {supp}\, p$. In other words, $\lambda$ is an i-th root of unity for all $i \in \mathrm {supp}\, p$. But since the g.c.d. of the elements of $\mathrm {supp}\, p$ equals 1 by assumption, $\lambda = 1$ is forced. $\square$

An immediate consequence of Lemma 6 is that, for any $x \in \mathbb {R}^n$, $A^kx$ approaches a constant multiple of (3) as $k \rightarrow \infty$. This is how we use Lemma 6 in the argument below.

Proof of Theorem 5

Write $V \backslash \{s\} = \{v_1, v_2, \ldots , v_L\}$, and let n be the smallest positive integer such that $\mathrm {supp}\, \wp \subseteq \{1, \ldots , n\}$. Define $\tau _{i}$ to be the toppling operator at $v_i$ with increment 1 (hence $\tau _i$ coincides with the toppling operator of the standard ASM on G), so that $T_{v_i} = \sum _j \wp (j)\tau _i^j,$ where $T_{v_i}$ is the toppling operator of SSP.

Define $r: \{0, \ldots , n-1\} \rightarrow \mathbb {R}$ by $r(k) = C\sum _{i > k}^{n} \wp (i)$, where the constant factor C is set so that $\sum r(k) = 1$, that is,

$$\begin{aligned} C = \left( \sum _{i=1}^n \sum _{j=i}^n \wp (j)\right) ^{-1}. \end{aligned}$$

For any pure configuration c, define

$$\begin{aligned} S(c) := \sum _{k_1 = 0}^{n-1} \cdots \sum _{k_L = 0}^{n-1} \left( \prod _{j=1}^L r(k_j)\tau _j^{k_j}\right) [c]. \end{aligned}$$

Fig. 2

The “parallelepiped”

One can think of S(c) as a distribution supported on $\prod _{i=1}^L k_i$ points on the space of (pure) configurations, which turn out to form the shape of a parallelepiped; see Fig. 2 for an illustration in case $L = 2, \mathrm {supp}\, \wp = \{1, 2, 3, 4, 5\}$. The point on the upper-right corner corresponds to [c], and other points are obtained by toppling [c] in various directions; see again Figure 2 for an illustration.

Write $I(\cdot )$ for the indicator function of the statement inside the parenthesis, i.e. if it is satisfied, $I(\cdot ) = 1$, otherwise zero. From Lemma 6, it follows that

$$\begin{aligned}&\sum _{k_1 = 0}^{n-1} \cdots \sum _{k_L = 0}^{n-1} \left( \prod _{j=1}^L r(k_j)\tau _j^{k_j}\right) T_{v_i}^{I(k_i = 0)}[c] \nonumber \\&\quad = \sum _{k_1 = 0}^{n-1} \cdots \sum _{k_L = 0}^{n-1} \left( \prod _{j=1}^L r(k_j)\tau _j^{k_j}\right) \tau _i[c] \nonumber \\&\quad = S(\tau _ic). \end{aligned}$$

(4)

This means that, if we “push” the parallelepiped-shaped distribution in the direction of $\tau _{i}$ by applying $T_{v_i}$ to the face of the parallelepiped corresponding to that direction, we obtain the same distribution on the parallepiped, except that the upper-right corner of the parallelepiped moves from [c] to $[\tau _ic]$.

We choose R to be the set of all recurrent configurations (see e.g. [5] for the definition) of ASM on G, whose threshold on each vertex is set uniformly to T, rather than the conventional $\deg v$. For convenience, let us temporarily write

$$\begin{aligned} S(R) := \frac{1}{|R|}\sum _{c \in R} S(c). \end{aligned}$$

We will show that $S(R)^\circ$ is the steady state.

By Proposition 3, it suffices to show that $(S(R) + v_i)^\circ = S(R)^\circ$ for all $i = 1, \ldots , L$. By the theory of ASM, $R + v_i = \{c + v_i: c \in R\}$ contains exactly one representative of each of the equivalence classes of configurations i.e. for each $c' \in R + v_i$, there exists exactly one $c \in R$ such that $c'$ stabilizes to c in ASM. By (4), $S(c')^\circ = S(c)^\circ$, and therefore, by Proposition 3 again,

$$\begin{aligned} (S(R) + v_i)^\circ= & {} \left( \frac{1}{|R|}\sum _{c' \in R+v_i} S(c')\right) ^\circ = \left( \frac{1}{|R|}\sum _{c' \in R+v_i} S(c')^\circ \right) ^\circ \\= & {} \left( \frac{1}{|R|}\sum _{c \in R} S(c)^\circ \right) ^\circ = S(R)^\circ , \end{aligned}$$

as desired. $\square$

The point of the following proposition is that, in a SSP, if we start from any configuration, and repeat sufficiently many times the Markov process of adding a sand grain at random—e.g. add $\frac{1}{L}\sum v_i$—and re-stabilizing, then we obtain a configuration that is arbitrarily close to the steady state. In the context of LLL, in place of the Markov chain one takes a large input, which is why the proposition below is stated the way it is.

Proposition 7

We continue with the notations of Theorem 5. In addition, below we interpret a pure configuration as an L-dimensional vector with integer entries, and a mixed configuration as a finitely supported function on the set of pure configurations. Then we impose the typical Euclidean metric on the space of pure or mixed configurations accordingly.

For any $\varepsilon > 0$, there exists $D > 0$ such that the stabilization $c^\circ$ of any non-negative pure configuration c whose distance from origin is greater than D is within an $\varepsilon$ distance of $S(c')^\circ$ with respect to the uniform norm, where $c'$ is the pure configuration that is recurrent and is equivalent to c under the ASM on G.

Proof

If c is far enough from the origin, then it must be toppled at each vertex arbitrarily many times in order for it to become stabilized. So without loss of generality, assume that c can be legally toppled at every vertex. Write $V \backslash \{s\} = \{v_1, v_2, \ldots , v_L\}$ as earlier, and consider the configuration

$$\begin{aligned} \left( \prod _{i=1}^L T_{v_i} \right) c = \sum _{k_1=0}^{n-1} \cdots \sum _{k_L=0} \left( \prod _{j=1}^L \wp (k_j)\tau _j^{k_j} \right) [c]. \end{aligned}$$

(5)

(5), like S(c), may be thought of as a distribution on a parallelepiped illustrated in Figure 2. By Lemma 6, if we “push” the parallelepiped—in the manner similar to (4)—from every direction sufficiently many times, the weight on each and every point will be arbitrarily close to $\prod _{j=1}^L r(k_j)$. Hence, if c is sufficiently far enough from the origin, the stabilization of (5) will be arbitrarily close to $S(c')$. This completes the proof. $\square$

The steady state alone forms the minimal ideal of the commutative monoid M of the nonnegative stable configurations of SSP. One may think this is disappointing, since its counterpart in ASM has a very rich theory. However, the theory of the abelian sandpile group can be extended to SSP in a straightforward way, if phrased in terms of the cosets of the “translations” $< \tau _i : i = 1, \ldots , L>$, since SSP respects this structure. Indeed, in our proof of Theorem 5, it can be seen that the underlying ASM theory plays a role. Our SSP theory is building up on top of the ASM theory, rather than replacing it.

2.5 The Shape of the Steady State on $A_L$

Ideally, we would like to prove the various quantitative properties of the steady state that we observe in Fig. 1: the middle values are almost identical to one another, but near the boundaries there is a sharp drop in pile height, et cetera. This can be interpreted as the following combinatorial problem. Consider the parallelepiped in Fig. 2, and suppose [c] is a stable configuration; it may help to think of [c] as the maximal stable configuration, i.e. has height $T-1$ on all sites. Then some configurations on the parallelepiped are stable e.g. $[\tau _1^3\tau _2^2c]$, but others may not be. Because [c] is stable, we cannot legally push the entire face of the parallelepiped as we have done in the proofs of Theorem 5 and Proposition 7. Instead, we must “fold” the parts of the parallelepiped that are outside the set of stable configurations. Understanding the steady state then amounts to understanding the resulting distribution on the “folded” parallelepiped—they are identical. In some sense, this parallelepiped-folding replaces the role of the burning algorithm (see [5], also [4]) in the study of the steady state.

The difficulty lies in describing this folded distribution in a mathematically concise manner. The best we can prove at the moment is that there exists a gap, whose size is independent of the system size L, between the average-case and the worst-case RHF (1) of SSP on $A_L$. This is in analogy with the folklore observation that there exists a gap between the average-case and the worst-case RHF of the LLL algorithm.

Proposition 8

Let C be as in the proof of Theorem 5. Then for any $\varepsilon > 0$ and L sufficiently large, the steady state of SSP on $A_L$ has the average RHF bounded from above by $T/2 - C^{-1}/e^2 + \varepsilon$.

Remark

Note that the maximum $\log (\mathrm {RHF})$ equals $(T-1)L/2(L+1) \approx T/2$. For the SSP in the introduction i.e. $\wp =$ (uniform distribution on $\{1, \ldots , 2I-1\}$), $C^{-1} \approx I$ so the proposition yields the bound $T/2 - I/e^2$, whereas experimentally we have $\approx T/2 - I/4$.

Proof of Proposition 8

As in the remark above, the greatest possible $\log (\mathrm {RHF})$ equals $M := (T-1)L/2(L+1)$. For $a > 0$, we will estimate the number of pure stable configurations whose RHF is greater than $M - a$. If c satisfies such a condition, then writing $s_i = T - c(i)$, from (1) it follows that

$$\begin{aligned} a > \frac{1}{(L+1)^2}\sum _{i=1}^L (L+1-i)s_i. \end{aligned}$$

(6)

Fig. 3

The avalanche size distribution of SSP. Gray, orange, blue graphs represent cases $L = 400, 4000, 40,000$ respectively

Moreover, this is an if-and-only-if condition. Hence it comes down to measuring the volume of the set of vectors $(s_1, \ldots , s_L)$, $s_i > 0$, such that (6) holds. This set forms a simplex, with one vertex at origin, and L other vertices given by

$$\begin{aligned} \left( 0, \ldots , \frac{a(L+1)^2}{L+1-i}, \ldots , 0\right) \end{aligned}$$

for each $i= 1, \ldots , L$, whose only non-zero entry is the i-th entry. The volume of this simplex equals

$$\begin{aligned} \frac{a^L(L+1)^{2L}}{(L!)^2}, \end{aligned}$$

which, by Stirling’s formula, is strictly bounded by $a^Le^{2L}$ for all sufficiently large L. Furthermore, the maximum possible probability mass of the steady state is given by $C^{L}$. Hence, for L large, the portion of the steady state lying on the set $(\mathrm {RHF}) > M - a$ is arbitrary small if

$$\begin{aligned} a < C^{-1}/e^2. \end{aligned}$$

This completes the proof. $\square$

3 Behavior of SSP on One-Dimensional Lattices

In this section, we present a pilot numerical study on the behavior of SSP pertaining to quantitative properties of its steady state, whose existence is established in the previous section. We restrict our attention to SSP on one-dimensional grids $A_L$ for $L = 400, 4000, 40000$, with $T = 400$ and $\wp$ the uniform distribution on $\{1, \ldots , 100\}$, adding $50(=\mathbb {E}(\wp ))$ grains to a random site for each step in the associated Markov chain.

There are many interesting ways of doing experiments with SSP, due to the flexibility in the choice of $\wp$. One could, for example, adjust the granularity, or try a different family of distributions, to observe how it affects the critical exponents or the rate of convergence to those as $L \rightarrow \infty$. We hope to be able to carry out more extensive experiments at a later time.

Fig. 4

The average steady state density of SSP

Fig. 5

Graph of i versus $\log (\tilde{h} - h(i))$, for $L = 40,000$. The auxiliary blue line is of slope $\approx -0.86$

3.1 Avalanche Size Distribution

Figure 3 presents the log-log scale graph of the avalanche size—i.e. the number of sites on which at least one toppling occurred during a stabilization—distribution of SSP. For each system size $L =400, 4000, 40,000$, we made one million trials. The x-axis represents $\log _2$ of avalanche sizes, and the y-axis represents $\log _2$ of the number of occurrences.

Figure 3 clearly suggests a power law, plus a delta distribution near $\log _2 L$. The data points for $L = 40,000$, excluding those at the tail, form a line of slope $\approx -0.98$. We conjecture that the slope will converge to $-1$ in the L limit. Our brief experiment in the continuum limit—that is, we allow real numbers for pile heights, and sample $\wp$ uniformly from an interval—also suggests the critical exponent of 1 as well.

It may be amusing to recall the behavior of one-dimensional ASM, which is well-known to behave in the totally opposite way, i.e. (avalanche size) $\propto$ (frequency). On the other hand, quite a few stochastic models in dimension 1 are known to demonstrate a power law [8, 9, 15].

3.2 Steady State Density Profile

Figure 4 presents the (empirical) steady state density profile of SSP for system sizes 400, 4000, 40,000, respectively. More precisely, the horizontal axis is the site index i, and the vertical axis is h(i), the average of the pile height at i over the steady state. The values in the middle seem to stabilize at $\approx 176.55 =: \tilde{h}$, which we take to be the approximation of the critical height, and in the extremes at $\approx 152.5$.

The finite-size scaling theory (FSS; see Section III of [8] for a concise summary of its implications) provides a satisfactory account for the curvy shape at the boundary. Figure 5 shows the graph of i versus $\log _2 (\tilde{h} - h(i))$, for $L = 40,000$. As FSS predicts, the points of the graph near the boundary show an excellent agreement with the line of slope $-0.86$, which suggests that the critical exponent $\nu$ is approximately $1/0.86 \approx 1.1628$. Again, the same value of $\nu$ is suggested in the continuum limit.