# Chip firing

Everybody has some number of coins. Every clock tick everybody
gives one coin to each of his neighbours, provided he has
sufficient coins to do so.
This 0-person game is played on a graph (so that "neighbour"
is defined). It is known under various names, like "chip firing"
and "sandpile".

## Sinks

A *sink* is a node in the graph that only receives but never gives.
(In the sandpile applet sinks are drawn black.
In particular, the outer boundary consists of sinks. In the
chipfire applet sinks are red.)
When sinks are present, every state will stabilize after finitely many
steps: money disappears into the sinks until nobody has enough left
to give one coin to each of his neighbours.
(In the sandpile applet the "single step" button does one clock tick,
the "go" button runs the time until the state has become stable.)

## Recurrent states

Let Z be the state space: the set of all vectors with nonnegative integral
entries, indexed by the nodes of the graph.
Let S be the subset of Z consisting of all stable states.
Then Z is infinite, but S is finite (assuming that the graph is finite).
We have an operation * on Z: given two vectors u and v in Z,
let u*v be the vector obtained by first taking the state u+v and
then letting that stabilize.
The set S together with the operation * is a monoid.

A state u in S is called *recurrent* if u*z = u for some
strictly positive vector z. Let R be the set of recurrent states in S.
Then (R,*) is an abelian group.

For every z in Z there is a unique r in R such that u*z = u*r
for all u in R. This r is called the *reduction* of z.
In particular, the identity of the group R is the reduction
of the zero vector. The elements of R are their own reduction,
so that "reduced" and "recurrent" are synonymous.
(In the sandpile applet, the "reduce" button computes the reduction
of a given state.)

## Exercises

Check with the sandpile applet that an all-red field is reduced. Why?
Check with the sandpile applet that doubling the identity and reducing
gives the identity again. Why?
Show that this property characterizes the identity.

Show that every finitely generated commutative semigroup
carries a group on its recurrent elements (provided there are any).
How should recurrent be defined here?

## Problems

An *avalanche* is the set of nodes that is involved in the
reduction of an arbitrary state to a stable one.
Single point changes to a recurrent state can cause both small
and large avalanches. Can something be said about the avalanche size?
Can something be said about the time needed to obtain a stable state?

The avalanche of a single point is simply connected. Why?