Printer Friendly

Chip-firing and a devil's staircase.

1 Introduction

In this extended abstract, we summarize recent work relating the Poincare rotation number of a circle map [S.sup.1] [right arrow] [S.sup.1] to the behavior of parallel chip-firing on the complete graph. We use this connection to shed light on two intriguing features of parallel chip-firing, mode locking and short period attractors. Ever since Bagnoli, Cecconi, Flammini, and Vespignani [1] found evidence of mode locking and short period attractors in numerical experiments in 2003, these two phenomena have called out for a mathematical explanation. The proofs omitted here can be found in [12].

In chip-firing on a finite graph, each vertex v starts with a pile of [sigma] (v) >[greater than or equal to] 0 chips. A vertex is unstable if it has at least as many chips as its degree, and can fire by sending one chip to each neighbor. In parallel chip-firing, at each time step, all unstable vertices fire simultaneously. If it is possible in finitely many firings to reach a stable configuration in which no vertex can fire, then this final configuration does not depend on the order of firings [5]. In this case, the parallel restriction does not affect the final outcome. However, our focus will be on chip configurations that do not stabilize.

Previous work on parallel chip-firing [3, 4, 10, 14] has focused on the periodicity of the dynamics: given a graph G, for which natural numbers q does there exist a parallel chip-firing state on G which first recurs after q time steps? We will have more to say about this question below. In the statistical physics literature, parallel chip-firing often goes by the name "fixed energy sandpile" [1, 6, 7, 15]. The term "sandpile" refers to the Bak-Tang-Wiesenfeld model of self-organized criticality [2], while "fixed energy" refers to the lack of a sink or boundary vertex where chips disappear.

We add loops to the complete graph [K.sub.n], so that a vertex with n or more chips is unstable, and fires by sending one chip to each vertex of [K.sub.n], including one chip to itself. The parallel update rule fires all unstable vertices simultaneously, yielding a new chip configuration U[sigma] given by

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (1)

Here

r([sigma]) = #{v|[sigma[(v) [greater than or equal to] n}

is the number of unstable vertices. Write [U.sup.0] [sigma] = [sigma], and [U.sup.t] [sigma] = U([U.sup.t-1] [sigma]) for t [greater than or equal to] 1.

Note that the total number of chips in the system is conserved. In particular, only finitely many different states are reachable from the initial configuration [sigma], so the sequence [([U.sup.t] [sigma]).sub.t[greater than or equal to]0] is eventually periodic: there exist integers m [greater than or equal to] 1 and [t.sub.0] [greater than or equal to] 0 such that

[U.sup.t+m] [sigma] = [U.sup.t] [sigma] [for all]t [greater than or equal to] [t.sub.0]. (2)

The activity of [sigma] is the limit

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. (3)

where

[[alpha].sub.t] = [t-1.summation over (s=0)] r([U.sup.s][sigma])

is the total number of firings performed in the first t updates. By (2), the limit in (3) exists and equals [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. Since 0 [less than or equal to] [[alpha].sub.t] < nt, we have 0 [less than or equal to] a([sigma]) [less than or equal to] 1.

Following [1], we ask: how does the activity change when chips are added to the system? If [[sigma].sub.n] is a chip configuration on [K.sub.n], write [[sigma].sub.n] + k for the configuration obtained from [[sigma].sub.n] by adding k chips at each vertex. The function

[[??].sub.n] (k) = a([[sigma].sub.n] + k)

is called the activity phase diagram of [[sigma].sub.n]. Surprisingly, for many choices of [[sigma].sub.n], the function [[??].sub.n] looks like a staircase, with long intervals of constancy punctuated by sudden jumps (Figure 1). This phenomenon is known as mode locking: if the system is in a preferred mode, corresponding to a wide stair in the staircase, then even a relatively large perturbation in the form of adding extra chips will not change the activity. For a general discussion of mode locking in dynamical systems, including examples from astronomy and physics, see [11].

To quantify the idea of mode locking in our setting, suppose we are given an infinite family of chip configurations [[sigma].sub.2], [[sigma].sub.3],... with [[sigma].sub.n] defined on [K.sub.n]. Suppose [[sigma].sub.n] is stable, i.e.,

0 [less than or equal to] [[sigma].sub.n] (v) [less than or equal to] n - 1 (4)

for all v [member of] [n]. Moreover, suppose that there is a continuous function F : [0,1] [right arrow] [0,1], such that for all 0 [less than or equal to] x [less than or equal to] 1

1/n#{v [member of] [n] | [[sigma].sub.n] (v) < nx} [right arrow] F(x) (5)

as n [right arrow] [infinity]. Then according to Theorem 3.1, the activity phase diagrams [[??].sub.n], suitably rescaled, converge pointwise to a continuous, nondecreasing function s : [0,1] [right arrow] [0,1].

[FIGURE 1 OMITTED]

Moreover, under a mild additional hypothesis, Proposition 3.2 says that this limiting function s is a devil's staircase: it is locally constant on an open dense subset of [0,1]. For each rational number p/q [member of] [0,1] there is a stair of height p/q, that is, an interval of positive length on which s is constant and equal to p/q.

Related to mode locking, a second feature observed in simulations of parallel chip-firing is nonergodicity: in trials performed with random initial configurations on the n x n torus, the activity observed in individual trials differs markedly from the average activity observed over many trials [15]. The experiments of [1] suggested a reason: the chip-firing states in locked modes, corresponding to stairs of the devil's staircase, tend to be periodic with very small period. We study these short period attractors in Theorem 4.6. Under the same hypotheses that yield a devil's staircase in Propositon 3.2, for each q [member of] N, a constant fraction [c.sub.q] n of the states {[[sigma].sub.n] + k}.sup.n.sub.k=0] have eventual period q.

To illustrate these results, consider the chip configuration an [[sigma].sub.n] [K.sub.n] defined by

[[sigma].sub.n](v) = [n/4] + [v-1/2], v = 1, ..., n. (6)

Here [x] denotes the greatest integer [less than or equal to] x. This family of chip configurations satisfies (??) with

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. (7)

The activity phase diagrams of [[sigma].sub.n] for n = 10, 100, 1000, 10000 are graphed in Figure 1. For example, when n = 10 we have

(a([[sigma].sub.10] + k)).sup.10.sub.k=0] = (0, 0, 0, 0, 1/3, 1/2, 1/2, 2/3, 1, 1, 1)

and when n = 100, we have

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

As n grows, the denominators of these rational numbers grow remarkably slowly: the largest denominator is 11 for n = 1000, and 13 for n = 10000. Moreover, for any fixed n the very smallest denominators occur with greatest frequency. For example, when n = 10000, there are 1667 values of k for which a([[sigma].sub.n] + k) = 1/2, and 714 values of k for which a([[sigma].sub.n] + k) = 1/3; but for each p = 1,..., 12 there is just one value of k for which a([[sigma].sub.n] + k) = p/13. In Lemma 4.5, we relate these denominators to the periodicity: if a([sigma]) = p/q in lowest terms, then [sigma] has eventual period q.

The remainder of the paper is organized as follows. In section 2 we show how to construct, given a chip configuration [sigma] on [K.sub.n] , a circle map f : [S.sup.1] [right arrow] [S.sup.1] whose rotation number equals the activity of [sigma]. This construction resembles the one-dimensional particle/barrier model of [9]. In section 3 we use the circle map to prove our main results on mode locking, Theorem 3.1 and Proposition 3.2. Short period attractors are studied in section 4, where we show that all states on [K.sub.n] have eventual period at most n (Proposition 4.4). Finally, in Theorem 4.11, we find a small "window" in which all states have eventual period two.

Many questions remain concerning parallel chip-firing on graphs other than [K.sub.n] . If the underlying graph is a tree [4] or a cycle [7], then instead of a devil's staircase of infinitely many preferred modes, there are just three: activity 0, 1/2 and 1. On the other hand, the numerical experiments of [1] for parallel chip-firing on the n x n torus suggest a devil's staircase in the large n limit. Our arguments rely quite strongly on the structure of the complete graph, whereas the mode locking phenomenon seems to be widespread. It would be very interesting to relate parallel chip-firing on other graphs to iteration of a circle map (or perhaps a map on a higher-dimensional manifold) in order to explain the ubiquity of mode locking.

2 Construction of the Circle Map

We first identify a certain class of chip configurations on [K.sub.n], the confined states, with the property that for any configuration a of activity a([sigma]) < 1, we have [U.sup.t] [sigma] confined for all sufficiently large t.

Definition. A chip configuration [sigma] on [K.sub.n] is preconfined if it satisfies

(i) [sigma](v) [less than or equal to] 2n - 1 for all vertices v of [K.sub.n].

If, in addition, [sigma] satisfies

(ii) [max.sub.v] [sigma](v) - [min.sub.v] [sigma](v) [less than or equal to] n - 1

then [sigma] is confined.

Lemma 2.1. If [sigma] is preconfined, then U[sigma] is confined.

Lemma 2.2. If a([sigma]) < 1, then [U.sup.t] [sigma] is confined for all sufficiently large t.

Note that from (1)

U[sigma](v) [equivalent to] [sigma](v) + r([sigma]) (mod n).

Iterating yields the congruence

[U.sup.t] [sigma](v) [equivalent to] [sigma](v) + [[alpha].sub.t] (mod n) (8)

where

[[alpha].sub.t] = [t-1.summation over (s=0)] r([U.sup.s][sigma])

is the total number of firings before time t.

Our next lemma characterizes the vertices that fire at time t + 1.

Lemma 2.3. If [U.sup.t] [sigma] is preconfined, then [U.sub.t+1][sigma](v) [greater than or equal to] n if and only if

[sigma](v) [equivalent to] -j (mod n)

for some [[alpha].sub.t] < j [less than or equal to] [[alpha].sub.t+1].

Let

[phi](j) = # {v [member of] [n] | [sigma](v) [equivalent to] -j (mod n)}. (9)

By Lemma 2.3, if [U.sup.t] [sigma] is preconfined, then the number of unstable vertices in [U.sup.t+1] [sigma] is

[r.sub.t+1] = [phi]([[alpha].sub.t] + 1) + ... + [phi]([[alpha].sub.t+1]),

hence

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (10)

This gives a recurrence for at relating three consecutive terms [[alpha].sub.t+1], [[alpha].sub.t+1] and [[alpha].sub.t+2]. Our next lemma simplifies this to a recurrence relating just two consecutive terms.

Lemma 2.4. If [sigma] is preconfined, then for all t [greater than or equal to] 0

[[alpha].sub.t+1] = g([[alpha].sub.t]),

where g : N [right arrow] N is given by

g(k) = [[alpha].sub.1] [k.summation over (j=1)][phi](j) (11)

and [phi] is given by (9).

The function g appearing in Lemma 2.4 satisfies

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. (12)

for all k [member of] N. This suggests that a more natural domain of definition is the unit circle. First extend g to all of Z by defining

g(- k) = g( nk - k) - nk, k [member of] N.

This is the unique extension with the property that g - I d is periodic mod n. Now for x [member of] R, let

f(x) = (1 - {nx})g([??]nx[??]) + {nx}g([??]nx[??])/n (13)

where [??]y[??], [??]y[??] and {y} denote respectively the greatest integer [less than or equal to] y, the least integer [greater than or equal to] y, and the fractional part of y.

By (12) we have for all x [member of] R

f(x+1) = (1-{nx})g([??]nx[??] + n) + {nx})g([??]nx[??] + n)

= f(x) + 1.

Hence f : R [right arrow] R descends to a circle map [bar.f] : [S.sup.1] [right arrow] [S.sup.1] (viewing [S.sup.1] as R/Z). Since f is nondecreasing, it has a well-defined Poincare rotation number [8, 13]

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (14)

which does not depend on x. Here [f.sup.t] denotes the t-fold iterate [f.sup.t] (x) = f ([f.sup.t-1](x)), with [f.sup.0] = Id. The rotation number measures the rate at which the sequence of points x, [bar.f] (x), [bar.f] ([bar.f] (x)),... winds around the circle.

Theorem 2.5. If [sigma] is preconfined, then a([sigma]) = [rho](f).

Note that the map g is defined in terms of [[alpha].sub.1] and [phi], both of which are easily read off from [sigma]. So given a preconfined configuration [sigma], equations (11) and (13) give an explicit recipe for writing down a circle map f whose rotation number is the activity of [sigma].

One naturally wonders how to generalize this construction to chip-firing configurations on graphs other than [K.sub.n]. A key step may involve identifying invariants of the dynamics. On [K.sub.n], these invariants take a very simple form: by (8), for any two vertices v, w [member of] [n], the difference

[U.sup.t] [sigma](v) - [U.sup.t] [sigma](w) mod n

does not depend on t. Analogous invariants for parallel chip-firing on the n x n torus are classified in [6].

3 Devil's Staircase

Let [[sigma].sub.2], [[sigma].sub.3], ... be a sequence of chip configurations, with [[sigma].sub.n] defined on [K.sub.n], satisfying the conditions (4) and (5). Extend F to all of R by setting

F(x + m) = F(x) + m, m [member of] Z. (15)

Note that (4) and (5) force F(0) = 0 and F(1) = 1, so this extension is continuous.

The rescaled activity phase diagram of [[sigma].sub.n] is the function [s.sub.n] : [0,1] [right arrow] [0,1] defined by

[S.sub.n](y) = a([[sigma].sub.n] + [ny]).

As n [right arrow] [infinity], the [s.sub.n] have a pointwise limit identified in our next result. Here and in what follows, [rho](x) denotes the rotation number (14).

Theorem 3.1. If (4) and (5) hold, then for each y [member of] [0,1] we have

[s.sub.n](y) [right arrow] s(y) := [rho]([R.sub.y] o [PHI])

as n [right arrow] [infinity], where [PHI](x) = -F(-x), and [R.sub.y](x) = x + y.

Write [[PHI].sub.y] = [R.sub.y] o [PHI], and let [[bar.PHI].sub.y] : [S.sup.1] [right arrow] [S.sup.1] be the corresponding circle map. We will call a function s : [0,1] [right arrow] [0,1] a devil's staircase if it is continuous, nondecreasing, nonconstant, and locally constant on an open dense set. Next we show that if

[([[bar.[PHI]].sub.y]).sup.q] [not equal to] Id for all y [member of] [S.sup.1] and all q [member of] N, (16)

then the limiting function s(y) in Theorem 3.1 is a devil's staircase. Examples of these staircases for different choices of F are shown in Figure 2.

[FIGURE 2 OMITTED]

Proposition 3.2. The function s(y) = [rho]([[PHI].sub.y]) continuous and nondecreasing in y. If z [member of] [0,1] is irrational, then [s.sup.-1] (z) is a point. Moreover, if (16) holds, then for every rational number p/q [member of] [0,1] the fiber [s.sup.-1](p/q) is an interval of positive length.

Our next result shows that in the interiors of the stairs, we in fact have [S.sub.n](y) = s(y) for sufficiently large n.

Proposition 3.3. Suppose that (4), (5) and (16) hold. If [s.sup.-1](p/q) = [a, b], then for any [epsilon] > 0

[a + [epsilon], b - [epsilon]] [subset] [s.sup.-1.sub.n] (p/q)

for all sufficiently large n.

The results in this section follow from Theorem 2.5 along with a few well-known properties of the rotation number [rho](f). To give a flavor of the proofs, we list here the properties we use. For more background on the rotation number, see [8, 13].

Call a map f : R [right arrow] R a monotone degree one lift if f is continuous, nondecreasing and satisfies

f (x +1) = f (x) + 1 (17)

for all x [member of] R. Let f, [f.sub.n] ,g be monotone degree one lifts, and denote by [bar.f], [bar.f.sub.n], [bar.g] the corresponding circle maps [S.sup.1] [right arrow] [S.sup.1]. Write f [less than or equal to] g if f(x)[less than or equal to] g(x) for all x [member of] R, and f < g if f (x) < g(x) for all x [member of] R.

* Monotonicity. If f [less than or equal to] g, then [rho](f) [less than or equal to] [rho](g).

* Continuity. If sup [absolute value of [f.sub.n] - f] [right arrow] 0, then [rho]([f.sub.n]) [right arrow] [rho](f).

* Conjugation Invariance. If g is strictly increasing, then [rho](g o f o [g.sup.-1]) = [rho](f).

* Instability of an irrational rotation number. If [rho](f) [not member of] Q, and [f.sub.1] < f < [f.sub.2], then [rho]([f.sub.1] < [rho](f) < [rho]([f.sub.2]).

* Stability of a rational rotation number. If [rho][(f) = p/q [member of] Q, and [[bar.f].sub.q] [not equal to] Id : [S.sup.1] [right arrow] [S.sub.1], then for sufficiently small [epsilon] > 0, either

[rho](g) = p/q whenever f [less than or equal to] g [less than or equal to] f + [epsilon],

or

[rho](g) = p/q whenever f - [epsilon] [less than or equal to] g [less than or equal to] f.

4 Short Period Attractors

For a chip configuration [sigma] on [K.sub.n] and a vertex v [member of] [n], let

[u.sub.t]([sigma], v) = #{0[less than or equal to] s < t| [U.sup.s] [sigma](v) [greater than or equal to] n}

be the number of times v fires during the first t updates. During these updates, the vertex v emits a total of n [u.sub.t] ([sigma], v) chips and receives a total of [[sigma].sub.t] = [[summation].sub.w] [u.sub.t] ([sigma], w) chips, so that

[U.sup.t] [sigma](v) - [sigma](v) = [[alpha].sub.t] - n [u.sub.t]([sigma], v). (18)

An easy consequence is the following.

Lemma 4.1. A chip configuration [sigma] on [K.sub.n] satisfies [U.sup.t][sigma] = [sigma] if and only if

[u.sub.t]([sigma],v) = [u.sub.t]([sigma],w) (19)

for all vertices v and w.

According to our next lemma, if [sigma] is confined, then [u.sub.t]([sigma], v) and [u.sub.t]([sigma], w) differ by at most one.

Lemma 4.2. If [sigma] is confined, and [sigma](v) [less than or equal to] [sigma](w), then for all t [greater than or equal to] 0

[u.sub.t]([sigma],v) [less than or equal to] [u.sub.t]([sigma],w) [less than or equal to] [u.sub.t]([sigma],v) + 1.

Lemma 4.3. If [sigma] is confined, then [U.sup.t] [sigma] = [sigma] if and only if n|[[alpha].sub.t].

Let [sigma] be a confined state on [K.sub.n]. By the pigeonhole principle, there exist times 0 [less than or equal to] s [less than or equal to] t [less than or equal to] n with

[[alpha].sub.s] [equivalent to] [[alpha].sub.s] (mod n).

By Lemma 4.3 it follows that [U.sup.s] [sigma] = [U.sup.t] [sigma], so [sigma] has eventual period at most n.

Our next result improves this bound a bit. Write m([sigma]) for the eventual period of [sigma], and

v([sigma]) = {a(v)|v e [n]}

for the number of distinct heights in [sigma].

Proposition 4.4. For any chip configuration [sigma] on [K.sub.n],

m([sigma]) [less than or equal to] v([sigma]).

Bitar [3] conjectured that any parallel chip-firing configuration on a connected graph of n vertices has eventual period at most n. A counterexample was found by Kiwi et al. [10]. It would be interesting to investigate for what classes of graphs Bitar's conjecture does hold; for example, no counterexample seems to be known on a regular graph.

Next we relate the period to the activity.

Lemma 4.5. If a([sigma]) = p/q and (p, q) = 1, then m([sigma]) = q.

The proof uses the fact that the rotation number of a circle map determines the periods of its periodic points: if f : R [right arrow] R is a monotone degree one lift (17) with [rho](f) = p/q in lowest terms, then all periodic points of [bar.f] : [S.sup.1] [right arrow] [S.sup.1] have period q; see Proposition 4.3.8 and Exercise 4.3.5 of [8].

Given 1 [less than or equal to] p < q [less than or equal to] n with (p, q) = 1 and p/q [greater than or equal to] 1/2, one can check that the chip configuration [sigma] on [K.sub.n] given by

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

has activity a([sigma]) = p/q. For a similar construction on more general graphs in the case p =1, see [14, Prop. 6.8]. In particular, m([sigma]) = q by Lemma 4.5. So for every integer q = 1,..., n there exists a chip configuration on [K.sub.n] of period q.

Despite the existence of states of period as large as n, states of smaller period are in some sense more prevalent. One way to capture this is the following.

Theorem 4.6. If [[sigma].sub.2], [[sigma].sub.3],... is a sequence of chip configurations satisfying (4), (5) and (16), then for each q [member of] N there is a constant c = [c.sub.q] > 0 such that for all sufficiently large n, at least cn of the states [{[[sigma].sub.] + k}.sup.n.sub.k=0 have eventual period q.]

The proof follows easily from Proposition 3.3, which shows that a constant fraction cn of the states [[sigma].sub.n] + k have activity 1/q. By Lemma 4.5 these states have eventual period q. The devil's staircase s(y) determines the best possible constant cq, namely, the total length of all stairs whose height has denominator q. If [s.sup.-1](p/q) = [[a.sub.p], [b.sub.p] then any constant

[c.sub.q] < [summation over [p:(p,q)=1]] ([b.sub.p] - [a.sub.p])

satisfies the conclusion of the theorem.

The rest of this section outlines the proof of Theorem 4.11, which finds a period 2 window: any chip configuration on Kn with total number of chips strictly between [n.sup.2] - n and [n.sup.2] has eventual period 2. The following lemma is a special case of [14, Prop. 6.2].

Lemma 4.7. If [sigma] and [tau] are chip configurations on [K.sub.n] with [sigma](v) + [tau](v) = 2n - 1 for all v, then a([sigma]) + a([tau]) = 1.

Given a chip configuration [sigma] on [K.sub.n], for j = 1,..., n we define conjugate configurations

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

Lemma 4.8. Let [sigma] be a chip configuration on [K.sub.n], and fix j [member of] [n]. For all t [greater than or equal to] 0, we have for v [less than or equal to] j

[u.sub.t]([sigma],v) - 1 [less than or equal to] [u.sub.t]([c.sup.j] [sigma], v)[less than or equal to] [u.sub.t] ([sigma],v),

while for v > j

[u.sub.t]([sigma],v) [less than or equal to] [u.sub.t]([c.sup.j] [sigma], v) [less than or equal to] [u.sub.t] ([sigma],v) + 1.

Corollary 4.9. For any chip configuration [sigma] on [K.sub.n] and any j [member of] [n],

a([c.sup.j] [sigma]) = a([sigma]).

It turns out that the circle maps corresponding to [sigma] and [c.sup.j] [sigma] are conjugate to one another by a rotation. This gives an alternative proof of the corollary, in the case when both [sigma] and [c.sup.j][sigma] are preconfined.

Lemma 4.10. Let [sigma] be a chip configuration on [K.sub.n]. If [u.sub.2]([sigma], v) [greater than or equal to] 1 for all v, then [u.sub.2t]([sigma], v) [greater than or equal to] t for all v and all t [greater than or equal to] 1.

Write

[absolute value of [sigma]] = [n.summation over (v=1)][sigma] (v)

for the total number of chips in the system.

Theorem 4.11. Every chip configuration [sigma] on [K.sub.n] with [n.sup.2] - n < [absolute value of [sigma]] < [n.sup.2] has eventual period 2.

The outline of the proof runs as follows. Writing

l([sigma]) = min{[sigma](1), ..., a(n)}

and

r([sigma]) = #{v [member of] [n] : [sigma](v) [greater than or equal to] n},

a straightforward calculation shows that if [sigma](1) [greater than or equal to] [sigma](2) [greater than or equal to] ... [greater than or equal to] [sigma](n) and [n.sup.2] - n < [absolute value of [sigma]] < [n.sup.2], then

[n.summation over (j=1)](l([c.sup.j][sigma]) + r([c.sup.j][sigma])) > [n.sup.2] - n.

Since each term in the sum on the left is a nonnegative integer, we must have

l([c.sup.j][sigma]) + r([c.sup.j][sigma]) [less than or equal to] n.

for some j [member of] [absolute value of n]. Thus every vertex v fires at least once during the first two updates of [c.sup.j] [sigma]. By Corollary 4.9 and Lemma 4.10, this implies

a([sigma]) = a([c.sup.j][sigma]) [greater than or equal to] 1/2.

The chip configuration [tau](v) := 2n - 1 - [sigma](v) also satisfies [n.sup.2] - n < [absolute value of [tau]] < [n.sup.2], so a([tau]) [greater than or equal to] 1/2 as well. By Lemma 4.7 we have a([sigma]) + ([tau]) = 1, so a([sigma]) = a([tau]) = 1/2. Finally, from Lemma 4.5 we conclude that m([sigma]) = 2.

Acknowledgement

The author thanks Anne Fey for many helpful conversations.

References

[1] F. Bagnoli, F. Cecconi, A. Flammini, and A. Vespignani, Short-period attractors and non-ergodic behavior in the deterministic fixed-energy sandpile model, Europhys. Lett. 63 (2003), 512-518.

[2] P. Bak, C. Tang and K. Wiesenfeld, Self-organized criticality: an explanation of the 1/f noise, Phys. Rev. Lett. 59, no. 4 (1987), 381-384.

[3] J. Bitar, Juegos Combinatoriales en Redes de Autoomatas, Tesis Ingeniero Matematico, Dept. Ingenieria Matematica, U. de Chile, 1989.

[4] J. Bitar and E. Goles, Parallel chip firing games on graphs, Theoretical Comp. Sci. 92, no. 2 (1992), 291-300.

[5] A. Bjorner, L. Lovasz and P. Shor, Chip-firing games on graphs, European J. Combin. 12 (1991), no. 4, 283-291.

[6] M. Casartelli, L. Dall'Asta, A. Vezzani and P. Vivo, Dynamical invariants in the deterministic fixed-energy sandpile, European Phys. J. B 52 (2006), no. 1, 91-105.

[7] L. Dall'Asta, Exact solution of the one-dimensional deterministic fixed-energy sandpile, Phys. Rev. Lett. 96 (2006).

[8] B. Hasselblatt and A. Katok, A First Course in Dynamics, With a Panorama of Recent Developments, Cambridge University Press, 2003.

[9] S. A. Janowsky and C. A. Laberge, Exact solutions for a mean-field abelian sandpile, J. Phys. A 26 (1993) L973-L980.

[10] M. A. Kiwi, R. Ndoundam, M. Tchuente and E. Goles, No polynomial bound for the period of the parallel chip firing game on graphs, Theoretical Comp. Sci. 136, no. 2 (1994), 527-532.

[11] J. C. Lagarias, Number theory and dynamical systems, Proc. Symp. Applied Math. 46 (1992), 35-72.

[12] L. Levine, Parallel chip-firing on the complete graph: devil's staircase and Poincare rotation number, http://arxiv.org/abs/0811.2800.

[13] W. de Melo and S. van Strien, One-Dimensional Dynamics, Springer-Verlag, 1991.

[14] E. Prisner, Parallel chip-firing on digraphs, Complex Systems 8 (1994), 367-383.

[15] A. Vespignani, R. Dickman, M. A. Munoz, and S. Zapperi, Absorbing-state phase transitions in fixed-energy sandpiles, Phys. Rev. E 62 (2000), 4564-4582.

Lionel Levine

Department of Mathematics, Massachusetts Institute of Technology, Cambridge, MA 02139
COPYRIGHT 2009 DMTCS
No portion of this article can be reproduced without the express written permission from the copyright holder.
Copyright 2009 Gale, Cengage Learning. All rights reserved.

Article Details
Printer friendly Cite/link Email Feedback
Author:Levine, Lionel
Publication:DMTCS Proceedings
Article Type:Report
Geographic Code:1USA
Date:Jan 1, 2009
Words:4876
Previous Article:On the 2-adic order of Stirling numbers of the second kind and their differences.
Next Article:Macdonald polynomials at t = [q.sup.k].
Topics:

Terms of use | Privacy policy | Copyright © 2020 Farlex, Inc. | Feedback | For webmasters