Tag Archives: sandpile

The 2-adic stochastic sandpile

Now that I’ve got your attention….

Sadhu and Dhar say in the paper I linked in the last post that it remains open whether the sandpile ring A is isomorphic to R^{2^N} when N is not congruent to 3 mod 4.  I think there’s an easy argument that shows the answer is yes.  Let’s give it a go.  We will freely use the notation from this afternoon’s post.

It’s not hard to see that the only way two different length-N words in {T,T’} can yield identical homomorphisms g and g’ from A to R is if g(x_i) = g'(x_i) = 0 for some x_i.  So this amounts to showing that when N is not 3 mod 4, no x_i goes to 0.

If x_i = 0, then we must have

x_{i-1} = -x, x_i = 0, x_{i+1} = x

for some real value x, and

x_0 = x_{N+1} = 1.

The choice of x has the effect of scaling everything, so this is the same as saying

[x_{i-1},x_i,x_{i+1}] = [-1,0,1]

and then we want to get x_0 = x_{N+1}.

Here’s an example of this with N=3:


Note that we can think of this as running the random walk in SL_2(Z) starting from [0,1] (as we move rightward from i) or starting from [0,-1] (as we move leftward.)  So what we’re trying to prove amounts to the following:

Start with [0,1], and for each word w in {T,T’}, we let f(w) be the second coordinate of the pair of integers obtained by applying w to [0,1].  Write |w| for the length of w.  It suffices to show:

Claim:  If f(w) = -f(w), then |w| + |w’| = 2 mod 4.

(For instance, in the example above, f(T) = 2 and f(T’) = -2, and the summed length is 2.)

But now just look at what happens mod 8.  Why mod 8?  Because I tried 2 and 4 and they didn’t work.  Starting with [0,1], and applying either T or T’ at each stage, you get

0,1,±2,3, 4 or 0, 5, ±2, 7, 4 or 0, 1, …..

and it cycles thereafter, with period 8.  And now the claim follows by inspection:  for instance, if f(w) = 2 or -2 mod 8, then |w| is 1 or 5 mod 8.  If f(w) = 3 mod 8, then |w| is 2 mod 8, while if f(w) = -3 mod 8, then |w| is 4 mod 8.  And so on.

Sound good?



Tagged , , , ,

The stochastic sandpile

At last week’s AIM conference on chip-firing I learned about a cool stochastic process which seems very simple, but whose behavior is apparently very hard to prove anything about!

It goes like this.  You start with a graph (say a finite connected graph, for simplicity) and your states are functions from the vertices of the graph to the natural numbers, which you think of as specifying the height of a pile of chips (or sand grains, if you want to keep up that metaphor) sitting on top of that vertex.  At least one of the vertices is a sink, which means that any chip landing there disappears forever.

Now the nature of the process is that you never want to have more than one chip at a vertex.  So every time there are at least two chips at a vertex v, you can pop two of them off; each chip flips a coin and decides whether to topple left or right.  And you keep on doing this until there’s at most one chip at each spot.  (You might start with more chips than vertices, but the sink helps you slough off the surplus.)  This process was apparently first studied by Manna and is sometimes called the Manna sandpile.

More math below the fold!

Continue reading

Tagged , , , , , , ,
%d bloggers like this: