betaFeedback

WorksMathematics

Labeled Chip-Firing on Ordered Directed Graphs

Abstract

We study labeled chip-firing on rooted directed graphs where for each vertex vv, the children of vv are linearly ordered. When a vertex fires, the selected chips are sent to its children in increasing order. We show that homomorphisms preserving these child choices transport legal firing sequences. We then consider the directed lattice Z≥02\mathbb Z_{\geq0}^2 and ask which chips can reach a given vertex. We give a recurrence for the smallest reachable label when sufficiently many chips are present and show that consecutive pairing attains this minimum. Finally, we determine the largest reachable label by symmetry and prove that the reachable labels form an interval when the number of initial chips is sufficiently large.

Introduction

Unlabeled Chip-Firing Games

Chip-firing on a directed graph is a single-player game in which chips, a discrete commodity, are distributed among the vertices of a graph. A vertex of positive outdegree can fire if it contains at least as many chips as its outdegree. It then sends one chip to each of its children. Once no vertex can fire, the game stops; in this case, the resulting distribution of chips is called the stable configuration; see § 2 for formal definitions.

When the chips are indistinguishable, this game is called unlabeled chip-firing. A fundamental property of unlabeled chip-firing on directed graphs is the following global confluence result.

Theorem 1 ([1 Theorem 1.1]). Let GG be a directed graph with finitely many vertices, and let CC be an initial configuration of chips on GG. Starting from CC, continue firing vertices as long as a legal move is available. Either every such game continues forever, or every such game terminates. In the latter case, the final configuration and the number of times each vertex fires do not depend on the firing choices.

The same result holds for infinite directed graphs with finite outdegrees and finitely many initial chips. It follows from the least action principle and halting dichotomy for abelian networks; see [2 Lemmas 4.3 and 4.4], where infinite underlying graphs are allowed. For completeness, we give a proof in Lemma 2.

Labeled Chip-Firing

In labeled chip-firing, a variant of the chip-firing game, the chips are distinguishable. Here, the chips are labeled by integers. When a vertex vv fires, we pick outdeg⁡(v)\operatorname{outdeg}(v) chips and send one to each child of vv. Which chip is sent to which child depends on the chips’ labels. Labeled chip-firing was originally studied by Hopkins, McConville, and Propp [4] in the one-dimensional lattice setting. Since then, it has been studied in the context of undirected binary trees [10, 7] and also directed trees [5, 6].

In labeled chip-firing, the confluence property does not always hold, thereby opening a new field of study focused on the variety of stable configurations that can be obtained.

Example 1. Consider the directed binary tree with chips 1, 2, 3, 4 at the root. We can see in Figure 1 that if we fire pair (1, 2) at the root first and continue to stability, as opposed to firing pair (2, 3) at the root first and continuing to stability, we obtain two different stable configurations.

Example of confluence breaking

Figure 1. Example of confluence breaking

Motivation and Contribution

Two basic questions in labeled chip-firing are as follows:

  1. Which stable configurations can occur?

  1. How many possible stable configurations are there?

In [5, 9, 6], we studied these questions for directed kk-ary trees. Recursive methods are particularly useful on directed trees because once two chips follow different branches, they cannot meet again.

Another basic problem in labeled chip-firing is to understand which labels can reach which vertices. In the setting of directed kk-ary trees, we studied this question in [6].

In this paper, we extend the study to ordered directed graphs in general, where different paths may merge. As our example, we use the lattice Lk=Z≥0kL_k = \mathbb{Z}_{\ge0}^k.

Our main tool is an order-preserving homomorphism between rooted directed graphs. Such a homomorphism pushes labeled chip-firing strategies forward: if a chip can reach a vertex in the source graph, then the same chip can reach the image vertex in the target graph. We apply this principle to the natural homomorphism from the kk-ary tree TkT_k to the lattice LkL_k for k≥2k \ge2.

We then study reachability questions for L2L_2, including the dependence on the number of initial chips, an exact recursive description of the eventual smallest and largest reachable labels, an eventual interval theorem, asymptotic estimates, and bounds on the region where the elementary lower bound is sharp.

Roadmap

In Section 2, we introduce the labeled chip-firing game on rooted directed graphs, our running examples, and the tree results that we use later. Section 3 explains how homomorphisms transport firing sequences and relates the tree and line graphs to other ordered directed graphs. In Section 4, we apply these results to trees and lattices.

In Section 5, we study which labels can reach a given vertex of the two-dimensional lattice. For sufficiently many initial chips, we give a recurrence determining the smallest reachable label, obtain the largest by symmetry, and prove that every label between these extremes is reachable. We show that a strategy based on pairing chips consecutively in increasing order attains the minimum. We also derive an asymptotic formula and give bounds on where the elementary lower bound is sharp.

Definitions and Preliminaries

Chip-Firing on Ordered Directed Graphs

We first recall common terminology used to describe directed graphs. In a directed graph GG, for each directed edge vp→vv_p \to v, we say that vertex vpv_p is a parent of vv, and the vertex vv is a child of vpv_p. Our directed graphs are rooted; for each directed graph GG, we have a designated vertex rr, called the root. We say that a vertex vv is on layer ii if the shortest path that exists from rr to vv takes ii edges. In this paper, we assume that all directed graphs have a root. Also, we assume that for any directed graph GG, all vertices of GG have finite outdegree and can be reached by a path starting at the root rr of GG. We assume there are no parallel directed edges.

To define chip-firing, we formally introduce a class of directed graphs endowed with additional information about each vertex’s children. An ordered directed graph is a directed graph in which the children of each vertex vv have a linear order ≤v\le_v. A traversal string t=t1t2⋯tℓt = t_1t_2 \cdots t_\ell records a sequence of child choices starting at the root: at step jj, we move to the tjt_jth child of the current vertex. We write vtv_t for the vertex reached by these choices. The empty string corresponds to the root.

A vertex may have several traversal strings. Every vertex has exactly one traversal string if and only if the graph is a rooted directed tree. If vtv_t has mm children, then its iith child is vtiv_{ti} for 1≤i≤m1 \le i \le m, where titi denotes the string obtained by appending ii to tt.

Let GG be an ordered directed graph. A configuration is a placement of chips on the vertices of GG. In labeled chip-firing, the chips are distinguishable and are labeled by consecutive positive integers.

A vertex vv can fire if outdeg⁡(v)>0\operatorname{outdeg}(v) > 0 and it contains at least outdeg⁡(v)\operatorname{outdeg}(v) chips. To fire vv, we choose outdeg⁡(v)\operatorname{outdeg}(v) chips at vv. If these chips have labels

c1<c2<⋯<coutdeg⁡(v),c_1 < c_2 < \cdots< c_{\operatorname{outdeg}(v)},

then chip cic_i is sent to the iith child of vv. Thus, the order of the children determines where the chosen chips go. The vertices with outdegree zero do not fire. A firing sequence is a finite sequence of legal firings. Formally, a firing sequence is a finite sequence of ordered pairs ((u1,S1),…,(um,Sm))((u_1,S_1),\ldots,(u_m,S_m)) such that, for each ii, the vertex uiu_i is the iith vertex that is fired and SiS_i is the set of chips fired in the iith firing, where outdeg⁡(ui)>0\operatorname{outdeg}(u_i) > 0 and ∣Si∣=outdeg⁡(ui)|S_i| = \operatorname{outdeg}(u_i) and, after the first i−1i-1 firings, every chip in SiS_i is located at uiu_i.

A configuration is stable if no vertex can fire. A strategy is a choice, at each step, of a vertex that can fire together with the chips to be fired from that vertex. A strategy is complete if its final configuration is stable.

The labeled game has the same underlying unlabeled chip movement as ordinary chip-firing: firing a vertex sends one chip to each child. Therefore, whenever the corresponding unlabeled chip-firing game terminates, every complete strategy fires each vertex the same number of times. Unless otherwise stated, we start with chips 1,2,…,N1,2,\ldots,N at the root.

We say that chip cc reaches a vertex vv if it is at vv at some time during the game, including the initial configuration. It passes through vv if it is later fired from vv, and it lands at vv if it is at vv in the final stable configuration. On a graph with directed cycles, a chip may pass through a vertex and later land there.

We recall the following standard confluence result for unlabeled chip-firing on possibly infinite directed graphs; see [2 Theorem 4.6]. We include a direct proof for completeness.

Lemma 2. Let GG be a possibly infinite directed graph with finite outdegrees, and let η0\eta_0 be an initial configuration of finitely many unlabeled chips. If one finite legal firing sequence reaches a stable configuration, then every game continued while a legal move is available terminates. The final configuration and the number of times each vertex fires are independent of the firing choices.

Proof. Fix a finite legal firing sequence reaching a stable configuration ηh\eta_h, and let h(v)h(v) be the number of times it fires vertex vv. We claim that every finite legal firing sequence fires each vertex vv at most h(v)h(v) times.

Otherwise, consider the first firing that would exceed one of these bounds, and let vv be the vertex about to fire. Immediately before this firing, let q(w)q(w) be the number of times each vertex ww has fired. Then q(w)≤h(w)q(w) \le h(w) for every ww, and q(v)=h(v)q(v) = h(v). Writing d(v)=outdeg⁡(v)d(v) = \operatorname{outdeg}(v), the number of chips at vv is

η0(v)−d(v)q(v)+∑w→vq(w)≤η0(v)−d(v)h(v)+∑w→vh(w)=ηh(v)<d(v).\eta_0(v)-d(v)q(v)+\sum_{w\to v}q(w)\le\eta_0(v)-d(v)h(v)+\sum_{w\to v}h(w)=\eta_h(v)<d(v).

The last inequality holds because ηh\eta_h is stable and vv has positive outdegree. This contradicts the legality of the proposed firing. The sums are finite because qq and hh have finite support. Consequently, every legal firing sequence has length at most ∑vh(v)\sum_v h(v), so every game continued while a legal move is available terminates. If h′h' is the firing-count function of another complete game, the claim gives h′≤hh' \le h. Interchanging the two games gives h≤h′h \le h', so h=h′h = h'. The initial configuration and these firing counts determine the final configuration.

Running Examples

We introduce our running examples: the kk-ary tree, the lattice of nonnegative integer points in kk-dimensional space, and the line graph. For the tree and lattice, we assume that k≥2k \ge2. We also assume that the root is at the top, and the children are numbered left to right.

Example 2. Consider the kk-ary tree, a directed tree where every vertex has kk children. The kk-ary tree was the setting for the chip-firing game studied in [5, 9, 6]. This kk-ary tree is an ordered directed graph, since its children are ordered left to right.

We illustrate the directed binary tree, i.e., the k=2k = 2 case of the kk-ary tree, in Figure 2, with the traversal strings of each vertex in the first 4 layers.

Traversal strings for the first 4 layers of a directed binary tree

Figure 2. Traversal strings for the first 4 layers of a directed binary tree

Example 3. Consider the kk-dimensional lattice of nonnegative integer points Z≥0k\mathbb{Z}_{\ge0}^{k}. We let LkL_k denote this lattice, rooted at the origin 0⃗\vec{0}. The vertex set is Z≥0k\mathbb{Z}_{\ge0}^{k} and the edge set is the set {(a⃗→a⃗+e⃗i):a⃗∈Z≥0k,i∈{1,…,k}}\{(\vec{a} \to\vec{a} + \vec{e}_i) : \vec{a} \in\mathbb{Z}_{\ge0}^{k}, i \in\{1, \ldots, k\}\}. In this paper, for each point a⃗\vec{a} in Z≥0k\mathbb{Z}_{\ge0}^{k}, we order the children of a⃗\vec{a} so that a⃗+e⃗i\vec{a} + \vec{e}_i is before a⃗+e⃗j\vec{a} + \vec{e}_j if and only if i<ji < j.

We illustrate the k=2k = 2 case of this lattice in Figure 3, which was the setting of the unlabeled chip-firing game in Inagaki et al. [8]. When we fire a vertex x⃗\vec{x}, we select kk labeled chips and, for each ii, send the iith smallest chip out of the selected chips to the iith child x⃗+e⃗i\vec{x} + \vec{e}_i. We repeat this game until no vertex can fire. Figure 4 illustrates this game on L2L_2, starting with chips 1,2,…,81, 2, \ldots, 8 at the origin.

Figure 3. The graph L2L_2.

Six configurations of a labeled chip-firing game on the lattice

Figure 4. (a) Initial configuration with 8 chips. (b) Configuration after firing pairs (1, 2), (3, 4), (5, 6), and (7, 8) from the root. (c) Configuration after firing pairs (1, 5), (3, 7) from the vertex (1, 0) and firing pairs (2, 6), (4, 8) from the vertex (0, 1). (d) Configuration after firing the pair of chips from vertex (2, 0), the pair of chips from vertex (0, 2), and firing pairs (2, 4) and (5, 7) from vertex (1, 1). (e) Configuration after firing the pair (2, 3) from vertex (2, 1) and firing the pair (4, 7) from vertex (1, 2). (f) Stable configuration after firing the pair (3, 4) from vertex (2, 2). Figure 4: A labeled chip-firing game on the lattice L2=Z≥02L_2 = \mathbb{Z}_{\geq0}^2 starting with 8 chips at the origin.

Throughout this subsection, we use the following visual convention for L2L_2: the first child of a vertex is drawn below on the left, and the second child is drawn below on the right. In coordinates, the first child of (x,y)(x, y) is (x+1,y)(x + 1, y), and the second child is (x,y+1)(x, y + 1), as seen in Figure 3.

Definition 1. Let PP be the ordered directed line with vertex set Z\mathbb{Z} and root 00. For each m∈Zm \in\mathbb{Z}, the vertex mm has two children: m−1m-1 and m+1m+1. We order these children so that m−1m-1 is the first child of mm, and m+1m+1 is the second child of mm.

Example 4. The ordered directed line PP is illustrated in Figure 5.

Figure 5. The line graph

Homomorphisms

We now define the notion of homomorphisms for ordered directed graphs, which are analogous to the standard notion of graph homomorphisms. For ordered directed graphs H1H_1 and H2H_2, a homomorphism from H1H_1 to H2H_2 is a function f:V(H1)→V(H2)f : V(H_1) \to V(H_2) such that:

  • For all v∈V(H1)v \in V(H_1), the outdegree of vv is equal to that of f(v)f(v).

  • If v′v' is the iith child of vv, then f(v′)f(v') is the iith child of f(v)f(v).

A homomorphism need not preserve the root. We call it root-preserving if it sends the root of the source graph to the root of the target graph.

Consider the directed binary tree from Example 2. Also consider the 2-dimensional lattice Z≥02\mathbb{Z}_{\geq0}^{2} from Example 3. Consider the map f:T2→L2f : T_2 \to L_2 that sends vtv_t to (a,b)(a,b), where aa and bb are the numbers of occurrences of 11 and 22 in tt, respectively. Appending 11 to tt increases aa by 11, and appending 22 increases bb by 11. Thus ff preserves the first and second children. Since both graphs have outdegree 22, the map ff is a homomorphism.

Example 5. Consider vertex v12v_{12} which has children v121v_{121} and v122v_{122}. These vertices correspond to (1,1)(1,1), (2,1)(2,1), and (1,2)(1,2) respectively, and (1,1)(1,1) is a parent of both (2,1)(2,1) and (1,2)(1,2). This is illustrated in Figure 6.

(a) Vertex v12v_{12} is adjacent to v121v_{121} and v122v_{122} in the binary tree

(b) Vertex (1,1)(1,1) is adjacent to vertices (1,2)(1,2) and (2,1)(2,1) in the 2D lattice

Figure 6. Example of the homomorphism between the directed binary tree and the 2D lattice

Prior Results on kk-ary Trees

We recall a result on labeled chip-firing on directed kk-ary trees.

Lemma 3 [6 Theorem 6.2]. Consider labeled chip-firing on TkT_k, starting with chips 1,2,…,kn1,2,\ldots,k^n at the root. Let t=t1t2⋯tnt=t_1t_2\cdots t_n be a traversal string of length nn. The labels that can land at vtv_t are exactly the integers in the interval

[∏j=1ntj, kn+1−∏j=1n(k+1−tj)].\left[\prod_{j=1}^{n}t_j,\ k^n+1-\prod_{j=1}^{n}(k+1-t_j)\right].

Automata and Tournaments Viewpoint

An ordered directed graph with constant outdegree kk can be viewed as a possibly infinite deterministic automaton whose alphabet is {1,2,…,k}\{1,2,\ldots,k\}. Reading the word t=t1t2⋯tℓt=t_1t_2\cdots t_\ell means starting at the root and successively following the tit_ith child. The unfolding of this automaton is the rooted tree whose vertices are finite traversal strings, with an edge from tt to titi for each i∈{1,…,k}i\in\{1,\ldots,k\}. Thus the unfolding is the kk-ary tree TkT_k. The natural map sends each traversal string to the vertex of the original graph that it reaches.

The lattice LkL_k is a quotient of TkT_k, obtained by identifying words that lead to the same vertex. For k=2k=2, the directed line PP is another quotient. The homomorphisms considered below are precisely the maps that preserve these child choices.

We can also interpret labeled chip-firing as a sequence of kk-player contests. The chips are the players, with smaller labels representing higher rankings. Whenever a vertex fires, the kk selected chips compete in one round: the iith smallest chip finishes in iith place and advances to the iith child.

Thus, in the tree TkT_k, a vertex records the complete sequence of finishing positions attained by every player that reaches it, whereas in the lattice LkL_k, a vertex (a1,…,ak)(a_1,\ldots,a_k) records only the totals: every player reaching this vertex has finished in iith place exactly aia_i times. Graph PP records the signed displacement of a chip: moving to the first child decreases the coordinate by 11, while moving to the second child increases the coordinate by 11.

In the binary case, each round is an ordinary head-to-head match, in which first place may be viewed as a win and second place as a loss. Consequently, a vertex of T2T_2 records a sequence of wins and losses, a vertex (a,b)(a,b) of L2L_2 records their totals, and the corresponding vertex b−ab-a of the line graph PP records their signed difference.

Results on Homomorphisms

Homomorphisms

Definition 2. Let NN be a positive integer, let G1G_1 and G2G_2 be ordered directed graphs, let u∈V(G1)u \in V(G_1), and let

f:G1⟶G2f:G_1 \longrightarrow G_2

be a homomorphism. Suppose

s=((u1,S1),(u2,S2),…,(um,Sm))s=((u_1,S_1),(u_2,S_2),\ldots,(u_m,S_m))

is a finite legal firing sequence on G1G_1 starting with NN chips at uu, where the iith firing selects the set SiS_i of chips at uiu_i.

We define the push-forward of ss to be the formal sequence

ϕf,N,u(s)=((f(u1),S1),(f(u2),S2),…,(f(um),Sm)).\phi_{f,N,u}(s)=((f(u_1),S_1),(f(u_2),S_2),\ldots,(f(u_m),S_m)).

Thus, at each step, we fire at f(ui)f(u_i) the same set of chips that was fired at uiu_i. The following lemma shows that every firing in this sequence is legal. The game on G2G_2 starts with the same NN chips at f(u)f(u).

Lemma 4 (Push-forward lemma). The push-forward ϕf,N,u(s)\phi_{f,N,u}(s) of every finite legal firing sequence ss on G1G_1 is a finite legal firing sequence on G2G_2.

More precisely, let Ci(v)C_i(v) be the set of chips at v∈V(G1)v \in V(G_1) after the first ii firings of ss, and let Di(w)D_i(w) be the set of chips at w∈V(G2)w \in V(G_2) after the first ii firings of ϕf,N,u(s)\phi_{f,N,u}(s). Then, for every w∈V(G2)w \in V(G_2), we have

Di(w)=⋃v∈V(G1)f(v)=wCi(v).D_i(w) = \bigcup_{\substack{v \in V(G_1) \\ f(v)=w}} C_i(v).

Consequently, if the trajectory of a chip cc under ss is

x0, x1, …, xr,x_0,\ x_1,\ \ldots,\ x_r,

then its trajectory under ϕf,N,u(s)\phi_{f,N,u}(s) is

f(x0), f(x1), …, f(xr).f(x_0),\ f(x_1),\ \ldots,\ f(x_r).

Proof. We show by induction that after each firing, every chip in G2G_2 is at the image of its position in G1G_1. This is true initially, as all chips start at f(u)f(u) in the chip-firing game on G2G_2.

Suppose the statement holds before the iith firing. The chips in SiS_i are at uiu_i in G1G_1, so they are all at f(ui)f(u_i) in G2G_2. Since uiu_i and f(ui)f(u_i) have the same outdegree, firing SiS_i at f(ui)f(u_i) is legal. If a selected chip cc moves to the jjth child of uiu_i, then, in the chip-firing game on G2G_2, chip cc moves to the jjth child of f(ui)f(u_i), which is the image of that child. The other chips do not move.

Thus the assertion holds after the iith firing. The identity

Di(w)=⋃v∈V(G1)f(v)=wCi(v)D_i(w) = \bigcup_{\substack{v \in V(G_1) \\ f(v)=w}} C_i(v)

and the statement about trajectories follow. □

Theorem 5. Let G1G_1 and G2G_2 be ordered directed graphs, let u∈V(G1)u \in V(G_1), and let f:G1⟶G2f : G_1 \longrightarrow G_2 be a homomorphism. Suppose the two games start with NN chips at uu and f(u)f(u), respectively. Then, for every v∈V(G1)v \in V(G_1), the set of chips that can reach vv in G1G_1 is a subset of the set of chips that can reach f(v)f(v) in G2G_2.

Proof. Suppose chip cc can reach vv in G1G_1. Take a finite legal firing sequence that ends immediately after chip cc first reaches vv. By Lemma 4, its push-forward is a legal firing sequence in G2G_2, and the trajectory of cc is obtained by applying ff to its trajectory in G1G_1. Hence chip cc reaches f(v)f(v) in G2G_2. □

Theorem 6. Let f:G1→G2f : G_1 \to G_2 be a homomorphism of ordered directed graphs, and let u∈V(G1)u \in V(G_1). Suppose that the unlabeled chip-firing game starting with NN chips at f(u)f(u) in G2G_2 terminates. Then the game starting with NN chips at uu in G1G_1 also terminates.

For i=1,2i = 1, 2, let Fi(v)F_i(v) be the number of times vv fires in the corresponding complete game. Then, for every w∈V(G2)w \in V(G_2), we have

F2(w)≥∑v∈V(G1)f(v)=wF1(v).F_2(w) \ge\sum_{\substack{v \in V(G_1) \\ f(v)=w}} F_1(v).

Proof. By Lemma 4, every finite legal firing sequence in G1G_1 pushes forward to a legal sequence of the same length in G2G_2. Since the latter game terminates, the proof of Lemma 2 bounds the length of every legal firing sequence by the length of a stabilizing sequence. The same bound therefore applies in G1G_1, so that game also terminates.

Choose a complete strategy in G1G_1 and push it forward. For each w∈V(G2)w \in V(G_2), the resulting sequence fires ww exactly

∑f(v)=wF1(v)\sum_{f(v)=w} F_1(v)

times. Continue this legal sequence to a stable configuration in G2G_2. The additional firings can only increase the firing count at ww, and confluence identifies the final count with F2(w)F_2(w).

Universality

We show that TkT_k is the universal unfolding for labeled chip-firing on ordered directed graphs of constant outdegree kk: every such graph is obtained from TkT_k by identifying vertices that have the same image under the unique root-preserving homomorphism. This proposition is the specialization, for the alphabet {1,2,…,k}\{1,2,\ldots,k\}, of the standard fact that the Cayley graph of the free monoid is the universal directed unfolding of a deterministic automaton [3 MRS11].

Proposition 7 (Universality of the kk-ary tree). Let k≥2k \ge2 be an integer, and let GG be an ordered directed graph such that every vertex has outdegree kk and every vertex is reachable from the root. Then there is a unique root-preserving homomorphism f:Tk⟶Gf:T_k \longrightarrow G. Moreover, this homomorphism is surjective. Consequently, graph GG is obtained from TkT_k by identifying two vertices whenever they have the same image under ff.

Proof. For a traversal string tt, let f(vt)f(v_t) be the vertex of GG reached by following the child choices in tt from the root. The empty string maps to the root.

Appending ii to tt means taking the iith child. Thus f(vti)f(v_{ti}) is the iith child of f(vt)f(v_t). Since both graphs have constant outdegree kk, the map ff is a homomorphism.

Any root-preserving homomorphism must follow these same child choices, so ff is unique. Every vertex of GG is reachable from the root and therefore equals f(vt)f(v_t) for some tt. Hence ff is surjective.

Finally, if f(vs)=f(vt)f(v_s)=f(v_t), then f(vsi)=f(vti)f(v_{si})=f(v_{ti}) for every ii. Thus, identifying vertices with the same image respects the ordered children, and the resulting graph is isomorphic to GG.

Corollary 8. Let k≥2k \ge2, let GG be an ordered directed graph such that every vertex has outdegree kk, and let f:Tk→Gf:T_k \to G be the unique root-preserving homomorphism. Fix N≥1N \ge1, and start both games with chips 1,2,…,N1,2,\ldots,N at their respective roots. Then every finite legal firing sequence on TkT_k pushes forward to a finite legal firing sequence on GG by firing, at f(v)f(v), the same kk chips that were fired at vv.

Moreover, if chip cc follows the sequence of vertices

u0, u1, …, uℓu_0,\ u_1,\ \ldots,\ u_\ell

in TkT_k, then under the pushed-forward sequence on GG, chip cc follows

f(u0), f(u1), …, f(uℓ).f(u_0),\ f(u_1),\ \ldots,\ f(u_\ell).

We close by recording the complementary fact to Proposition 7: On the tree TkT_k, changing the order of the children at each vertex gives an isomorphic game.

Definition 3. Let DD be a rooted directed graph in which every vertex has positive outdegree. An ordering of DD is a choice, for each vertex vv, of a linear order ≤v\le_v on the children of vv. Each ordering makes DD into an ordered directed graph.

Definition 4. An isomorphism of ordered directed graphs is a bijective homomorphism whose inverse is also a homomorphism.

Proposition 9. Let DD be the underlying directed graph of TkT_k, and let ≤\le and ≤′\le' be orderings of DD. Then there is a unique root-preserving isomorphism g:(D,≤′)→(D,≤)g:(D,\le')\to(D,\le).

Proof. Set g(r)=rg(\mathbf r)=\mathbf r. Suppose g(v)g(v) has been defined, let v1<′⋯<′vkv_1<'\cdots<'v_k be the children of vv, and let w1<⋯<wkw_1<\cdots<w_k be the children of g(v)g(v). Setting g(vi)=wig(v_i)=w_i is forced, and since every vertex of DD other than the root has a unique parent, this defines gg on all of DD. It restricts to a bijection between the children of vv and those of g(v)g(v) for every vv, hence is bijective, and it carries the iith child to the iith child by construction, so gg and g−1g^{-1} are homomorphisms. □

Corollary 10. With gg as above and both games starting with NN chips at the root, a chip cc can reach a vertex vv in the game on (D,≤′)(D,\le') if and only if cc can reach g(v)g(v) in the game on (D,≤)(D,\le). Moreover, the map gg induces a bijection between the reachable stable configurations of the two games. In particular, for k≥2k\ge2, the choice of ordering on TkT_k is made without loss of generality.

Proof. Theorem 5 applied to gg gives one inclusion, and applied to g−1g^{-1} gives the other. Lemma 4 applied to gg and to g−1g^{-1} shows that s↦ϕg,N,r(s)s\mapsto\phi_{g,N,\mathbf r}(s) is a bijection between the finite legal firing sequences of the two games, carrying stable configurations to stable configurations. □

The Line Graph

We showed a special role of the tree graph TkT_k. We now discuss the complementary quotient graph PkP_k. For k=2k=2, this graph is the line graph PP, which we defined in § 2.2.

Definition 5. Let Λk=Zk/Z(1,1,…,1)\Lambda_k=\mathbb{Z}^k/\mathbb{Z}(1,1,\ldots,1) and let π:Zk→Λk\pi:\mathbb{Z}^k\to\Lambda_k be the quotient map. Let PkP_k be the ordered directed graph with vertex set Λk\Lambda_k and root π(0⃗)\pi(\vec{0}). Each vertex ww has kk children w+π(e⃗1),…,w+π(e⃗k)w+\pi(\vec{e}_1),\ldots,w+\pi(\vec{e}_k), ordered so that w+π(e⃗i)w+\pi(\vec{e}_i) is before w+π(e⃗j)w+\pi(\vec{e}_j) if and only if i<ji<j.

The restriction of π\pi to LkL_k is a root-preserving homomorphism from LkL_k to PkP_k, since it preserves each child choice. It is surjective: adding a sufficiently large multiple of (1,…,1)(1,\ldots,1) gives a nonnegative representative of every class in Λk\Lambda_k.

Example 6. Let k=2k=2. The map π(a1,a2)↦a2−a1\pi(a_1,a_2)\mapsto a_2-a_1 identifies Λ2\Lambda_2 with Z\mathbb{Z}, sending π(e⃗1)\pi(\vec{e}_1) to −1-1 and π(e⃗2)\pi(\vec{e}_2) to +1+1. Thus P2P_2 is the line graph PP with vertex set Z\mathbb{Z} and root 00, in which each vertex mm has first child m−1m-1 and second child m+1m+1.

Example 7. Take k=3k=3. Since π(e⃗1)+π(e⃗2)+π(e⃗3)=π(1,1,1)=0\pi(\vec{e}_1)+\pi(\vec{e}_2)+\pi(\vec{e}_3)=\pi(1,1,1)=0, the underlying undirected graph of P3P_3 is the triangular lattice. If π(a⃗)=π(b⃗)\pi(\vec{a})=\pi(\vec{b}), then a⃗−b⃗=t(1,1,1)\vec{a}-\vec{b}=t(1,1,1), so λ(π(a⃗))=(a1+a2+a3) mod 3\lambda(\pi(\vec{a}))=(a_1+a_2+a_3)\bmod3 is well defined on P3P_3. Thus, we can view λ\lambda as assigning colors to the vertices of P3P_3. Every edge in P3P_3 increases λ\lambda by 1, so λ\lambda is a proper 3-coloring, and each elementary triangle {w,w+π(e⃗i),w−π(e⃗j)}\{w,w+\pi(\vec{e}_i),w-\pi(\vec{e}_j)\}, i≠ji\ne j, uses all three colors. Finally, the map π\pi is injective on each layer {a⃗:a1+a2+a3=ℓ}\{\vec{a}:a_1+a_2+a_3=\ell\} of L3L_3, so that layer embeds in P3P_3 as a triangular array inside the color class ℓ mod 3\ell\bmod3.

The characterization of maps to the line extends to PkP_k. For a traversal string tt, let

α(t)=(α1(t),…,αk(t)),\alpha(t)=(\alpha_1(t),\ldots,\alpha_k(t)),

where αi(t)\alpha_i(t) is the number of occurrences of ii in tt.

Proposition 11. Let k≥2k\ge2, and let GG be an ordered directed graph in which every vertex has outdegree kk and is reachable from the root. There exists a root-preserving homomorphism

ρG:G→Pk\rho_G:G\to P_k

if and only if, whenever traversal strings ss and tt reach the same vertex of GG, we have

α(s)−α(t)∈Z(1,…,1).\alpha(s)-\alpha(t)\in\mathbb{Z}(1,\ldots,1).

If such a homomorphism exists, it is unique and surjective.

Proof. A root-preserving homomorphism must send the endpoint of a traversal string tt to π(α(t))\pi(\alpha(t)). Thus it can exist only if this value is independent of the traversal string chosen to reach a vertex. By the definition of Λk\Lambda_k, this is exactly the stated condition. The same observation proves uniqueness.

Conversely, suppose the condition holds. If tt reaches vv, set

ρG(v)=π(α(t)).\rho_G(v)=\pi(\alpha(t)).

This is well defined and sends the root to π(0⃗)\pi(\vec{0}). Appending ii to tt adds e⃗i\vec{e}_i to α(t)\alpha(t), so the iith child of vv maps to the iith child of ρG(v)\rho_G(v). Since both outdegrees are kk, the map is a homomorphism.

Finally, every class in Λk\Lambda_k has a nonnegative representative a⃗\vec{a}. Choose a traversal string containing exactly aia_i occurrences of ii for each ii. Its endpoint in GG maps to π(a⃗)\pi(\vec{a}), proving surjectivity. □

Remark. For every k≥2k\ge2, the map π:Lk→Pk\pi:L_k\to P_k is injective on each individual layer. Indeed, if a⃗\vec{a} and b⃗\vec{b} lie in the same layer and π(a⃗)=π(b⃗)\pi(\vec{a})=\pi(\vec{b}), then a⃗−b⃗=q(1,…,1)\vec{a}-\vec{b}=q(1,\ldots,1) for some integer qq. Summing the coordinates gives kq=0kq=0, so q=0q=0 and a⃗=b⃗\vec{a}=\vec{b}.

Definition 6. Let GG be an ordered directed graph in which every vertex has outdegree 2 and every vertex is reachable from the root. For a binary string t=t1t2⋯tℓt = t_1t_2\cdots t_\ell, define its signed weight by

ω(t)=#{j:tj=2}−#{j:tj=1}.\omega(t) = \#\{j : t_j = 2\} - \#\{j : t_j = 1\}.

We say that GG is signed-rankable if, whenever two traversal strings ss and tt reach the same vertex of GG, we have

ω(s)=ω(t).\omega(s) = \omega(t).

For k=2k = 2, Proposition 11 gives the following characterization of signed-rankable graphs GG in which every vertex has outdegree 2.

Proposition 12. Let GG be an ordered directed graph in which every vertex has outdegree 2 and every vertex is reachable from the root. Then there exists a root-preserving homomorphism

ρG:G→P\rho_G : G \to P

if and only if GG is signed-rankable. Moreover, if such a homomorphism exists, then it is unique.

Proof. For k=2k = 2, the condition in Proposition 11 is equivalent to

α2(s)−α1(s)=α2(t)−α1(t),\alpha_2(s) - \alpha_1(s) = \alpha_2(t) - \alpha_1(t),

which is exactly signed-rankability. The result follows by identifying P2P_2 with PP.

Corollary 13. There are unique root-preserving homomorphisms

ρT:T2→PandρL:L2→P.\rho_T : T_2 \to P \qquad\text{and} \qquad\rho_L : L_2 \to P.

They are given by

ρT(vt)=#{j:tj=2}−#{j:tj=1}\rho_T(v_t) = \#\{j : t_j = 2\} - \#\{j : t_j = 1\}

for a binary traversal string t=t1t2⋯tℓt = t_1t_2\cdots t_\ell, and

ρL(a,b)=b−a.\rho_L(a,b) = b - a.

Proof. Every vertex of T2T_2 has a unique traversal string. Every traversal string reaching (a,b)(a,b) in L2L_2 contains exactly aa occurrences of 1 and bb occurrences of 2, so its signed weight is b−ab - a. Thus both graphs are signed-rankable, and Proposition 12 gives the stated homomorphisms and their uniqueness.

Trees and Lattices

We now apply our results from § 3 to relate the labeled chip-firing game on the kk-ary tree TkT_k to the one on the kk-dimensional lattice Lk=Z≥0kL_k = \mathbb{Z}_{\geq0}^{k}.

Consider the map f:V(Tk)→V(Lk)f : V(T_k) \to V(L_k) defined as follows. For a traversal string t=t1t2⋯tℓt = t_1t_2 \cdots t_\ell, map the tree vertex vtv_t to

f(vt)=∑j=1ℓe⃗tj.f(v_t) = \sum_{j=1}^{\ell} \vec{e}_{t_j}.

This is a homomorphism from TkT_k to LkL_k. Thus, Theorem 5 implies the following corollary.

Corollary 14. Consider the chip-firing game on the kk-ary tree TkT_k starting with knk^n chips at the root and the chip-firing game on the kk-dimensional lattice LkL_k starting with knk^n chips at the root. Let t=t1t2…tℓt = t_1t_2 \ldots t_\ell be a traversal string of length ℓ≤n\ell\leq n. Let cc be a chip with label in {1,2,…,kn}\{1,2,\ldots,k^n\}. If chip cc can reach vtv_t in the chip-firing game on TkT_k, then chip cc can reach vertex ∑j=1ℓe⃗tj\sum_{j=1}^{\ell} \vec{e}_{t_j} in the chip-firing game on LkL_k.

Here is an example showing that the converse direction in the corollary above is false.

Example 8. Consider the case k=2k=2 and n=3n=3, so that we start with chips 1,2,…,81,2,\ldots,8 at the root. Let t=122t=122. The corresponding lattice vertex is e⃗1+e⃗2+e⃗2=(1,2)\vec{e}_1+\vec{e}_2+\vec{e}_2=(1,2). We show that chip 3 can reach (1,2)(1,2) in the lattice L2L_2, but cannot reach the tree vertex v122v_{122} in T2T_2. Indeed, fire the pairs of chips (1,2)(1,2) and (3,4)(3,4) at the root, leaving the other chips unused. Then fire (1,3)(1,3) at vertex (1,0)(1,0) and (2,4)(2,4) at vertex (0,1)(0,1). Chips 2 and 3 now meet at (1,1)(1,1). Firing this pair sends chip 2 to vertex (2,1)(2,1) and chip 3 to vertex (1,2)(1,2).

On the other hand, Lemma 3 shows that the chips that can reach v122v_{122} in the binary tree are precisely

[1⋅2⋅2,23+1−(2⋅1⋅1)]=[4,7].[1 \cdot2 \cdot2, 2^3 + 1 - (2 \cdot1 \cdot1)] = [4,7].

Hence chip 3 cannot reach v122v_{122}. The same calculation applies to the strings 212 and 221. Thus chip 3 cannot reach any tree vertex that maps to (1,2)(1,2).

The number of chips reaching a vertex in LkL_k also has a simple description in the first n+1n+1 layers. The multinomial coefficient counts the tree vertices that map to the given vertex in LkL_k.

Proposition 15. Let k≥2k \geq2 and n≥0n \geq0. In any complete strategy on LkL_k starting with knk^n chips at the origin, a vertex a⃗=(a1,…,ak)\vec{a} = (a_1,\ldots,a_k) on layer ℓ=a1+⋯+ak≤n\ell= a_1+\cdots+a_k \leq n is reached by exactly

(ℓa1,…,ak)kn−ℓ\binom{\ell}{a_1,\ldots,a_k} k^{n-\ell}

chips.

If ℓ<n\ell< n, then a⃗\vec{a} fires exactly

(ℓa1,…,ak)kn−ℓ−1\binom{\ell}{a_1,\ldots,a_k} k^{n-\ell-1}

times and retains no chips in the stable configuration.

Proof. The arrival formula holds at the root. Suppose ℓ≥1\ell\ge1, and it holds on layer ℓ−1\ell-1. Each parent of a⃗\vec{a} lies on a layer less than nn and receives a multiple of kk chips. In a complete strategy, it therefore sends one kkth of its chips to each child.

Adding the contributions from all parents of a⃗\vec{a} gives

kn−ℓ∑1≤i≤kai>0(ℓ−1a1,…,ai−1,…,ak)=kn−ℓ(ℓa1,…,ak).k^{n-\ell}\sum_{\substack{1\le i\le k\\a_i>0}}\binom{\ell-1}{a_1,\ldots,a_i-1,\ldots,a_k}=k^{n-\ell}\binom{\ell}{a_1,\ldots,a_k}.

This proves the arrival formula by induction. If ℓ<n\ell<n, the number of arriving chips is divisible by kk. Since the lattice is acyclic, every arriving chip is counted only once, and the vertex fires exactly the arrival count divided by kk, leaving no chips behind.

Smallest and Largest Chips

Dependence on the Total Number of Chips

The smallest chip that can reach a vertex may depend on the total number of chips.

Example 9. Consider the following ordered directed graph. The root is rr. Its first child is aa, and its second child is vv. The vertex vv will be our target vertex. The first child of aa is again vv, and the second child of aa is some vertex ww. All remaining vertices may be completed by attaching ordinary binary trees, so that every vertex has outdegree 2 and the game terminates.

For N=2N=2, the smallest chip that can reach vv is 2. If we have 4 chips, the smallest chip that can reach vv is 1. Indeed, fire the pairs (1,2)(1,2) and (3,4)(3,4) at the root. Then aa receives chips 1, 3, and firing this pair sends chip 1 to vv.

The same is true for the lattice graph L2L_2. We wrote some programs, and here are two examples where the smallest chip that can reach a fixed vertex of L2L_2 depends on the total number of chips.

Example 10. Consider the vertex (1,4)(1,4). For N=12N=12, the smallest chip that can reach this vertex is 10, while for N=16N=16, the smallest chip is 8.

Moreover, the smallest chip that can reach a fixed vertex of L2L_2 can depend on NN even when NN is restricted to powers of 2. We also checked the following example with a program.

Example 11. Consider the vertex (3,8)(3,8). For N=32N=32, the smallest chip that can reach it is 27, while for N=64N=64 it is 24.

We now look at the smallest chip that can reach a given vertex of L2L_2 when the number of chips is relatively large.

Definition 7. For nonnegative integers aa and bb, let μ(a,b)\mu(a,b) be the smallest chip that can reach (a,b)(a,b) in some finite game starting with chips 1,2,…,N1,2,\ldots,N at the origin, where NN may vary.

Every vertex of L2L_2 is the image of a tree vertex under the homomorphism from the preceding section, so it is reachable in some finite game. Also, extra chips may always be left unused until the desired chip arrives. Consequently, once chip μ(a,b)\mu(a,b) can reach (a,b)(a,b), it can do so in every game starting with a larger number of chips. Thus μ(a,b)\mu(a,b) is also the smallest reachable label for all sufficiently large NN. This is a reachability question, not necessarily a question about the final stable configuration.

We start with a simple lower bound. Note that we do not assume here that we have sufficiently many chips.

Lemma 16. Let 1≤c≤N1 \le c \le N. If chip cc reaches vertex (a,b)(a,b), then it satisfies

b+1≤c≤N−a.b+1 \le c \le N-a.

Proof. We induct on the layer a+ba+b. The assertion holds at the root, where every chip has a label between 11 and NN. Suppose chips x<yx<y are fired at (a,b)(a,b). By the induction hypothesis, we have

b+1≤x<y≤N−a.b+1 \le x<y \le N-a.

Hence x≤N−a−1x \le N-a-1, so chip xx satisfies the required bounds at (a+1,b)(a+1,b). Similarly, we have y≥b+2y \ge b+2, so chip yy satisfies them at (a,b+1)(a,b+1). Thus every firing preserves the bounds.

These bounds also imply that every game on L2L_2 terminates. Indeed, every occupied vertex (a,b)(a,b) satisfies a+b≤N−1a+b \le N-1, so the sum of the chips’ layer numbers is at most N(N−1)N(N-1). Each firing increases this sum by 22.

Corollary 17. We have μ(a,b)≥b+1\mu(a,b) \ge b+1.

Our next goal is to calculate μ(a,b)\mu(a,b) and find where this lower bound is sharp.

Small Chips and Consecutive Pairing

Suppose we want to know whether a chip with label at most mm can reach our target. Call chips 1,2,…,m1,2,\ldots,m small and all other chips large. A small chip can move to the first child by being paired with a large chip. Moving to the second child is harder: it must be paired with another small chip.

Example 12. Suppose m=3m=3 and a vertex contains chips 1,2,3,81,2,3,8. Fire the pairs (1,2)(1,2) and (3,8)(3,8). The first child receives two small chips, 11 and 33, while the second child receives one small chip, 22. The large chip allows the last small chip to move to the first child rather than remain at the vertex.

More generally, suppose a vertex contains ss small chips and an even total number of chips. List all its chips in increasing order and pair consecutive chips. If ss is odd, the last small chip is paired with the first large chip. Thus the numbers of small chips sent to the first and second children are, respectively,

⌊s2⌋and⌈s2⌉.\left\lfloor\frac{s}{2} \right\rfloor \qquad\text{and}\qquad \left\lceil\frac{s}{2} \right\rceil.

The second number is as large as possible: every small chip sent to the second child needs another small chip as its partner.

We use this rule at every vertex. Fix a nonnegative integer DD, and start with N=2DN = 2^D chips. Process the vertices layer by layer, beginning at the root. At each vertex, wait for all incoming chips, list them in increasing order, and fire consecutive pairs. Stop after processing all vertices in layers less than DD. We call this the consecutive-pairing strategy. The pairings do not depend on the cutoff mm.

Why start with a power of 2? The following lemma shows that no chip is left unpaired before the target layer.

Lemma 18. Under consecutive pairing starting with 2D2^D chips, every vertex before layer DD receives an even number of chips. More precisely, a vertex (i,j)(i,j) with i+j≤Di+j \le D receives

(i+ji)2D−i−j chips.\binom{i+j}{i} 2^{D-i-j}\ \text{chips}.

Proof. Extend the consecutive-pairing sequence to a complete strategy, which is possible by the termination argument above. All subsequent firings occur in layers at least DD, so they do not change the arrival counts in layers at most DD. The formula follows from Proposition 15 with k=2k=2 and n=Dn=D. If i+j<Di+j<D, then the factor 2D−i−j2^{D-i-j} is even.

To study (a,b)(a,b), we may take D≥a+bD \ge a+b. If we are also tracking chips 1,2,…,m1,2,\ldots,m, choose DD large enough that 2D≥m2^D \ge m. At every processed vertex, the large chips provide the partners needed whenever the number of small chips is odd; we do not have to route auxiliary chips separately.

For each nonnegative integer bb, the vertices (0,b),(1,b),(2,b),…(0,b),(1,b),(2,b),\ldots form diagonal bb, which extends downward to the left in our drawing. The vertices on this diagonal are indexed by their first coordinate. A first-child move stays on the same diagonal and increases this index by 1. A second-child move enters the next diagonal and preserves the index.

Example 13. Let us return to the vertex (1,2)(1,2). Start with eight chips and fire consecutive pairs. The root sends chips 1, 3, 5, 7 to (1,0)(1,0) and chips 2, 4, 6, 8 to (0,1)(0,1). At these vertices, fire

(1,0):(1,3), (5,7),(0,1):(2,4), (6,8).\begin{aligned} (1,0)&:\quad(1,3),\ (5,7),\\ (0,1)&:\quad(2,4),\ (6,8). \end{aligned}

Then (1,1)(1,1) receives chips 2, 3, 6, 7. Firing (2,3)(2,3) and (6,7)(6,7) sends chip 3 to (1,2)(1,2).

For m=3m=3, two small chips enter diagonal 1: chip 2 enters at (0,1)(0,1), and chip 3 enters at (1,1)(1,1). Chip 2 then moves along diagonal 1 to (1,1)(1,1), so the two small chips meet there. Firing them together sends chip 3 to (1,2)(1,2), so one small chip enters diagonal 2. For m=2m=2, only chip 2 enters diagonal 1. It has no small partner, so these pairings send no small chip to diagonal 2.

Computing the Smallest Chip

The preceding example suggests counting the small chips entering an initial segment of a diagonal. This is easier than keeping track of all labels or all individual vertex counts.

Definition 8. Let Cm(a,b)C_m(a,b) be the number of small chips that enter diagonal bb at vertices whose first coordinate is at most aa under consecutive pairing. For b>0b>0, an entry into diagonal bb is a move from (i,b−1)(i,b-1) to (i,b)(i,b) for some ii. Subsequent moves along diagonal bb are not counted again. For b=0b=0, we count the initial placement of the mm small chips at the root.

For each count, choose D≥a+bD \ge a+b with 2D≥m2^D \ge m. The count does not depend on this choice: at every processed vertex, the numbers of small chips sent to its children depend only on the number of incoming small chips. Induction over the layers therefore gives the same small-chip counts whenever DD is large enough.

Example 14. For a=0,1a=0,1 and b=0,1,2b=0,1,2, the cumulative counts in Example 13 are

bbm=2m=2m=3m=3
C2(0,b)C_2(0,b)C2(1,b)C_2(1,b)C3(0,b)C_3(0,b)C3(1,b)C_3(1,b)
02233
11112
20001

For instance, the two small chips entering diagonal 1 at (0,1)(0,1) and (1,1)(1,1) give C3(1,1)=2C_3(1,1)=2. The entry C3(1,2)=1C_3(1,2)=1 counts the small chip entering diagonal 2 at (1,2)(1,2).

The recurrence for these counts is particularly simple: add two previous entries, divide by 2, and round down.

Lemma 19. For every positive integer mm, we have

Cm(a,0)=m(a≥0),Cm(−1,b)=0(b≥0).C_m(a,0)=m \quad(a\ge0), \qquad C_m(-1,b)=0 \quad(b\ge0).

For a≥0a\ge0 and b≥1b\ge1, we have

Cm(a,b)=⌊Cm(a,b−1)+Cm(a−1,b)2⌋.(1)C_m(a,b)=\left\lfloor\frac{C_m(a,b-1)+C_m(a-1,b)}{2}\right\rfloor. \tag*{(1)}

Proof. The initial conditions follow from the definition. To obtain the recurrence, consider the firings at (a,b−1)(a,b-1). Write

X=Cm(a,b−1),Y=Cm(a−1,b).X=C_m(a,b-1), \qquad Y=C_m(a-1,b).

Thus XX small chips have entered diagonal b−1b-1 at vertices with first coordinate at most aa, and YY of them have already moved to diagonal bb at vertices with first coordinate less than $a. No chips remain at the previously processed vertices. Consequently, the other X−YX-Y small chips reach (a,b−1)(a,b-1). Consecutive pairing sends ⌊(X−Y)/2⌋\left\lfloor(X-Y)/2 \right\rfloor of them to (a,b)(a,b). Including the YY earlier entries into diagonal bb gives

Cm(a,b)=Y+⌊X−Y2⌋=⌊X+Y2⌋.C_m(a,b)=Y+\left\lfloor\frac{X-Y}{2}\right\rfloor=\left\lfloor\frac{X+Y}{2}\right\rfloor.

The local rule sends as many small chips as possible to the second child. However, this alone does not prove that the whole strategy is optimal: sending fewer small chips to the second child leaves more available farther along the current diagonal. Cumulative counts let us compare these possibilities.

Proposition 20. In any finite legal firing sequence, the number of chips among 1,2,…,m1,2,\ldots,m entering diagonal bb at vertices with first coordinate at most aa is at most Cm(a,b)C_m(a,b). Consecutive pairing attains these bounds simultaneously in every fixed finite portion of the lattice, provided DD is large enough.

Proof. For an arbitrary finite firing sequence, let Cm′(a,b)C'_m(a,b) count the same diagonal entries. We may assume that the game starts with at least mm chips, since missing chips may be added and left unused.

Put X′=Cm′(a,b−1)X'=C'_m(a,b-1) and Y′=Cm′(a−1,b)Y'=C'_m(a-1,b). Of the X′X' small chips entering diagonal b−1b-1 at vertices with first coordinate at most aa, the Y′Y' that leave for diagonal bb at vertices with first coordinate less than aa cannot reach (a,b−1)(a,b-1). Some other chips may remain at earlier vertices. Hence at most X′−Y′X'-Y' small chips reach (a,b−1)(a,b-1).

Each small chip sent from (a,b−1)(a,b-1) to its second child needs another small chip as its partner. Also, a chip visits a lattice vertex at most once. Thus

Cm′(a,b)≤Y′+⌊X′−Y′2⌋=⌊X′+Y′2⌋.C'_m(a,b)\leq Y'+\left\lfloor\frac{X'-Y'}{2}\right\rfloor=\left\lfloor\frac{X'+Y'}{2}\right\rfloor.

The initial values of Cm′C'_m and CmC_m agree. Since the expression on the right is nondecreasing in both inputs, induction on a+ba+b gives Cm′(a,b)≤Cm(a,b)C'_m(a,b)\leq C_m(a,b). The equality for consecutive pairing is Lemma 19.

There is one more point to check. A positive value of Cm(a,b)C_m(a,b) tells us that a small chip enters diagonal bb at a vertex with first coordinate at most aa, rather than necessarily at (a,b)(a,b). But every processed vertex with s>0s>0 small chips sends ⌈s/2⌉≥1\left\lceil s/2\right\rceil\geq1 small chips to its first child. Therefore, once a small chip enters this part of diagonal bb, some small chip reaches (a,b)(a,b) under consecutive pairing. Conversely, any small chip reaching (a,b)(a,b) must have entered diagonal bb at a vertex (i,b)(i,b) with i≤ai\leq a.

We can now compute the smallest chip that can reach (a,b)(a,b) when we play the chip-firing game with sufficiently many chips.

Theorem 21. For nonnegative integers aa and bb, we have

μ(a,b)=min⁡{m≥1:Cm(a,b)>0}.(2)\mu(a,b)=\min\{m\geq1:C_m(a,b)>0\}. \tag*{(2)}

Moreover, consecutive pairing starting with 2a+b2^{a+b} chips sends chip μ(a,b)\mu(a,b) to (a,b)(a,b).

Proof. Let M=2a+bM = 2^{a+b}. By Lemma 18, the consecutive-pairing strategy starting with MM chips sends chips to (a,b)(a,b). If all MM chips are called small, then CM(a,b)>0C_M(a,b) > 0, so the minimum in Equation (2) exists and is at most MM.

Let mm be that minimum. By Proposition 20, no chip with label smaller than mm can reach (a,b)(a,b) in any game. On the other hand, consecutive pairing with MM chips sends some small chip to (a,b)(a,b), by the preceding observation. Its label is at most mm and cannot be smaller than mm. Hence it is chip mm, and m=μ(a,b)m = \mu(a,b).

A separate strategy is not needed for each target vertex. In fact, consecutive pairing realizes both extreme reachable labels at every vertex in the first D+1D+1 layers.

Corollary 22. Fix D≥0D \ge0, and start with N=2DN = 2^D chips. Under consecutive pairing, for every vertex (a,b)(a,b) with a+b≤Da+b \le D, both chips

μ(a,b)andN+1−μ(b,a)\mu(a,b) \qquad\text{and} \qquad N+1-\mu(b,a)

reach (a,b)(a,b). These are, respectively, the smallest and largest chips that can reach this vertex in the NN-chip game.

Proof. Fix (a,b)(a,b) and put m=μ(a,b)m = \mu(a,b). By Theorem 21, we have Cm(a,b)>0C_m(a,b) > 0. The small-chip counts do not depend on DD once D≥a+bD \ge a+b and 2D≥m2^D \ge m. Thus some chip among 1,…,m1,\ldots,m reaches (a,b)(a,b) under consecutive pairing. No smaller chip can ever reach this vertex, so chip mm itself reaches it. The pairings do not depend on the target vertex or on the cutoff mm, so this holds simultaneously for all vertices under consideration.

Now interchange the coordinates and replace each label jj by N+1−jN+1-j. Every vertex that is processed has an even number of chips, by Lemma 18. Reversing an even-ordered list preserves its consecutive pairs, while interchanging the smaller and larger member of each pair. The coordinate interchange also swaps the two children. Starting from the symmetric initial configuration, induction over the layers therefore shows that the sets of arriving chips are preserved by this transformation.

Since chip μ(b,a)\mu(b,a) reaches (b,a)(b,a), chip N+1−μ(b,a)N+1-\mu(b,a) reaches (a,b)(a,b) in the same strategy. Any larger reachable label would, after the same reflection, give a label smaller than μ(b,a)\mu(b,a) reaching (b,a)(b,a), which is impossible.

Example 15. Let us compute μ(1,2)\mu(1,2). From Example 14, we have C2(1,2)=0C_2(1,2) = 0 and C3(1,2)=1C_3(1,2) = 1. The counts are nondecreasing in mm, either by their definition or by the recurrence. Therefore μ(1,2)=3\mu(1,2) = 3. Similarly, the recurrence gives C7(1,4)=0C_7(1,4) = 0 and C8(1,4)=1C_8(1,4) = 1, so μ(1,4)=8\mu(1,4) = 8. This agrees with the sixteen-chip computation in Example 10.

Table 1 shows the values of μ(a,b)\mu(a,b) computed from the recurrence. The corresponding array is now recorded in the OEIS as sequence A397913 [11].

Consequences and Special Cases

The construction gives an explicit meaning to “sufficiently many chips.”

Corollary 23. If N≥2a+bN \ge2^{a+b}, then the smallest and largest chips that can reach (a,b)(a,b) are, respectively,

μ(a,b)andN+1−μ(b,a).\mu(a,b) \qquad\text{and} \qquad N+1-\mu(b,a).

Proof. Theorem 21 gives a firing sequence using chips 1,2,…,2a+b1,2,\ldots,2^{a+b} in which chip μ(a,b)\mu(a,b) reaches (a,b)(a,b). In a larger game, repeat this sequence and leave the additional chips unused until that arrival. No smaller chip can reach the vertex, by the definition of μ\mu.

For the largest chip, interchange the two coordinates and replace each label cc by N+1−cN+1-c. This identifies the smallest reachable label at (b,a)(b,a) with the largest reachable label at (a,b)(a,b).

Remark. The bound 2a+b2^{a+b} is sufficient, not necessarily the smallest possible bound. For example, the minimum μ(1,4)=8\mu(1,4)=8 is already attained with 16 chips, although the bound gives 32. For smaller NN, a vertex may be reachable even though the eventual minimum label cannot yet reach it.

The preceding corollary determines the smallest and largest chips that can reach a vertex vv. In the next proposition, we show that every label between these extremes can reach vv when the total number of chips is sufficiently large. But first, we introduce new notation. Fix nonnegative integers aa and bb, and write

M=2a+b,p=μ(a,b),q=μ(b,a).M=2^{a+b}, \qquad p=\mu(a,b), \qquad q=\mu(b,a).

Proposition 24. If

N≥max⁡{M, 2M−p−q},N \ge\max\{M,\,2M-p-q\},

then the set of labels that can reach (a,b)(a,b) in the NN-chip game is exactly

[p,N+1−q]∩Z.[p,N+1-q]\cap\mathbb{Z}.

In particular, the condition N≥2a+b+1N \ge2^{a+b+1} is sufficient.

Proof. By Corollary 23, in the MM-chip game there is a firing sequence sending chip pp to (a,b)(a,b), and there is a firing sequence sending chip M+1−qM+1-q to (a,b)(a,b). For any integer tt with 0≤t≤N−M0 \le t \le N-M, replace every label jj in either sequence by j+tj+t. All comparisons between selected chips are preserved. Therefore, the resulting sequence is legal in the NN-chip game: we use chips t+1,…,t+Mt+1,\ldots,t+M and leave the other chips unused until the desired arrival.

Applying these shifts to the first sequence shows that every label in

[p,N−M+p]∩Z[p,N-M+p]\cap\mathbb{Z}

can reach (a,b)(a,b). Applying them to the second sequence gives every label in

[M+1−q,N+1−q]∩Z.[M+1-q,N+1-q]\cap\mathbb{Z}.

These two integer intervals overlap or are adjacent whenever

M+1−q≤N−M+p+1.M+1-q\le N-M+p+1.

which is equivalent to N≥2M−p−qN\ge2M-p-q. Their union is therefore [p,N+1−q]∩Z[p,N+1-q]\cap\mathbb{Z}. By Corollary 23, all labels outside this interval cannot reach the vertex (a,b)(a,b).

The strategies used for different labels may be different. The proposition concerns reachability, not the labels in a single stable configuration.

Corollary 25. The columns in Table 1 are nonincreasing, and the rows are strictly increasing. Equivalently,

μ(a+1,b)≤μ(a,b)<μ(a,b+1).\mu(a+1,b)\le\mu(a,b)<\mu(a,b+1).
a\ba \backslash b012345678
01248163264128256
11234815244064
2123458152432
312345681524
41234567815

Table 1. The smallest chip μ(a,b)\mu(a,b) that can reach (a,b)(a,b) when sufficiently many chips are present.

Proof. By definition, we have Cm(a+1,b)≥Cm(a,b)C_m(a+1,b)\ge C_m(a,b), since the former also counts entries at (a+1,b)(a+1,b). Theorem 21 gives μ(a+1,b)≤μ(a,b)\mu(a+1,b)\le\mu(a,b).

Now suppose μ(a,b+1)=d\mu(a,b+1)=d. At some earlier time, chip dd must have moved from diagonal bb to diagonal b+1b+1. It was therefore paired with a smaller chip d′<dd'<d at some vertex (i,b)(i,b) with i≤ai\le a. Thus μ(i,b)≤d′\mu(i,b)\le d'. By the first part, we have

μ(a,b)≤μ(i,b)≤d′<μ(a,b+1).\mu(a,b)\le\mu(i,b)\le d'<\mu(a,b+1).

:::

The first two rows of Table 1, corresponding to a=0a=0 and a=1a=1, admit more explicit descriptions.

Example 16. For a=0a=0, the recurrence repeatedly halves the number of small chips:

Cm(0,b)=⌊m2b⌋.C_m(0,b)=\left\lfloor\frac{m}{2^b}\right\rfloor.

Consequently, we have μ(0,b)=2b\mu(0,b)=2^b.

To compute Cm(1,b)C_m(1,b), we count entries into diagonal bb only at (0,b)(0,b) and (1,b)(1,b). For example, when m=4m=4, the values of C4(1,b)C_4(1,b) for b=0,1,2,3,4b=0,1,2,3,4 are 4,3,2,1,04,3,2,1,0. Allowing entries at (1,b)(1,b) lets one small chip enter diagonal 33, whereas entering at (0,3)(0,3) would require eight small chips.

Recall that ν2(j)=max⁡{e:2e∣j}\nu_2(j)=\max\{e:2^e\mid j\} is the 2-adic valuation of jj.

Proposition 26. For every b≥0b \ge0, we have

μ(1,b)=min⁡{m≥1:∑j=1m2ν2(j)≥2b}.\mu(1,b)=\min\left\{m \ge1:\sum_{j=1}^{m}2^{\nu_2(j)} \ge2^b\right\}.

Proof. For b≥1b \ge1, Equation (1) gives

Cm(1,b)=⌊∣Cm(1,b−1)∣+⌊m/2b⌋2⌋.C_m(1,b)=\left\lfloor\frac{\lvert C_m(1,b-1)\rvert+\lfloor m/2^b\rfloor}{2}\right\rfloor.

Starting with Cm(1,0)=mC_m(1,0)=m and applying this identity repeatedly gives

Cm(1,b)=⌊m+∑r=1b2r−1⌊m/2r⌋2b⌋.(3)C_m(1,b)=\left\lfloor\frac{m+\sum_{r=1}^{b}2^{r-1}\lfloor m/2^r\rfloor}{2^b}\right\rfloor. \tag*{(3)}

This can also be checked by induction; the identity ⌊(⌊x⌋+k)/2⌋=⌊(x+k)/2⌋\lfloor(\lfloor x\rfloor+k)/2\rfloor=\lfloor(x+k)/2\rfloor for an integer kk allows the nested floors to be combined.

For each positive integer jj, we have

2ν2(j)=1+∑r=1ν2(j)2r−1.2^{\nu_2(j)}=1+\sum_{r=1}^{\nu_2(j)}2^{r-1}.

Summing over j=1,2,…,mj=1,2,\ldots,m gives

∑j=1m2ν2(j)=m+∑r≥12r−1⌊m2r⌋.\sum_{j=1}^{m}2^{\nu_2(j)}=m+\sum_{r\ge1}2^{r-1}\left\lfloor\frac{m}{2^r}\right\rfloor.

If m<2bm<2^b, all terms with r≥br\ge b vanish, so the sum on the left is the numerator in Equation (3). Hence Cm(1,b)>0C_m(1,b)>0 exactly when that sum is at least 2b2^b.

If m≥2bm\ge2^b, both conditions already hold: we have Cm(0,b)≥1C_m(0,b)\ge1, and the sum is at least mm. The proposition now follows from Theorem 21.

The formula in Proposition 26 also describes the growth of the smallest reachable label. For b≥2b\ge2, increasing the first coordinate from 0 to 1 strictly reduces this label.

Corollary 27. As b→∞b\to\infty, we have

μ(1,b)∼2b+1b.\mu(1,b)\sim\frac{2^{b+1}}{b}.

Proof. Put

S(m)=∑j=1m2ν2(j),S(0)=0.S(m)=\sum_{j=1}^{m}2^{\nu_2(j)},\qquad S(0)=0.

The identity in the preceding proof gives

S(m)=m+∑r=1⌊log⁡2m⌋2r−1⌊m2r⌋=m2log⁡2m+O(m).S(m)=m+\sum_{r=1}^{\lfloor\log_2 m\rfloor}2^{r-1}\left\lfloor\frac{m}{2^r}\right\rfloor=\frac{m}{2}\log_2 m+O(m).

Indeed, removing the floors changes the sum by O(m)O(m).

Let mb=μ(1,b)m_b=\mu(1,b). By Proposition 26, we have

S(mb−1)<2b≤S(mb).S(m_b-1)<2^b\leq S(m_b).

Since S(mb)−S(mb−1)=2ν2(mb)≤mbS(m_b)-S(m_b-1)=2^{\nu_2(m_b)}\leq m_b, it follows that

2b=mb2log⁡2mb+O(mb).2^b=\frac{m_b}{2}\log_2 m_b+O(m_b).

As mb→∞m_b\to\infty, taking logarithms gives b=log⁡2mb+O(log⁡log⁡mb)b=\log_2m_b+O(\log\log m_b), and hence log⁡2mb∼b\log_2m_b\sim b. Substituting back gives mb∼2b+1/bm_b\sim2^{b+1}/b.

Where the Lower Bound Is Attained

By Lemma 16, any chip that reaches (a,b)(a,b) has label at least b+1b+1. We now look at the vertices where this lower bound is sharp. For example, when a=0a=0, the bound is sharp for b=0,1b=0,1. When a=1a=1, the bound is sharp for b=0,1,2,3b=0,1,2,3.

Let g(b)g(b) be the least first coordinate aa for which μ(a,b)=b+1\mu(a,b)=b+1, and let h(a)h(a) be the greatest second coordinate bb for which this equality holds. Thus

g(b)=min⁡{a:μ(a,b)=b+1},h(a)=max⁡{b:μ(a,b)=b+1}.g(b)=\min\{a:\mu(a,b)=b+1\},\qquad h(a)=\max\{b:\mu(a,b)=b+1\}.

The proof below shows that both quantities are well defined. Since μ(a,b)\mu(a,b) is nonincreasing in aa and bounded below by b+1b+1, we also have

h(a)=max⁡{b:g(b)≤a}.h(a)=\max\{b:g(b)\leq a\}.

Thus the function gg describes the boundary for each fixed second coordinate, while the function hh describes it for each fixed first coordinate.

To study this boundary, it is useful to record the numbers of new small chips entering a diagonal at each vertex, rather than their cumulative counts. These are the successive differences Cm(i,b)−Cm(i−1,b)C_m(i,b)-C_m(i-1,b). This notation will be used only in the boundary argument.

Example 17. Start with four small chips. The lists of new entries into successive diagonals are

(4,0,0,…),(2,1,0,…),(1,1,0,…),(0,1,0,…).(4,0,0,\ldots),\qquad(2,1,0,\ldots),\qquad(1,1,0,\ldots),\qquad(0,1,0,\ldots).

At vertex (0,0)(0,0), two small chips are sent to (1,0)(1,0) and two to (0,1)(0,1). Vertex (1,0)(1,0) then sends one small chip to (1,1)(1,1). The remaining small chip continues along diagonal 0 without creating any more entries into diagonal 1.

Thus, the number of new entries drops by one at each successive diagonal. On diagonal 3, the only small chip that can appear is chip 4, and it first enters at index 1. Therefore we have g(3)=1g(3)=1.

The same drop by one occurs for any nonempty list of new entries. To see this, process the vertices of the diagonal in order of increasing first coordinate until all incoming entries have been used. Past the last incoming entry, repeated rounding up after division by 22 eventually leaves one small chip, which continues along the diagonal without producing any more entries into the next diagonal. Every other small chip enters the next diagonal.

We can determine the entries into the next diagonal in finitely many steps. Once only that last chip remains, we stop the calculation and omit it from the next diagonal’s list. Every finite part of the calculation is realized by consecutive pairing with a sufficiently large power of 22 chips.

The following result describes how the boundary moves.

Lemma 28. For every b≥0b \ge0, we have

g(b)≤g(b+1)≤g(b)+1,g(b+2)>g(b).g(b) \le g(b+1) \le g(b)+1,\qquad g(b+2)>g(b).

Consequently, for every a≥0a \ge0, we have

h(a+1)−h(a)∈{1,2}.h(a+1)-h(a)\in\{1,2\}.

Proof. For a finitely supported list x=(x0,x1,…)x=(x_0,x_1,\ldots) of new entries into a diagonal, let T(x)T(x) be the list of new entries into the next diagonal. We call this operation diagonal reduction. The entries of each list are indexed by the first coordinate. To compute the reduction, set q−1=0q_{-1}=0 and let

(Tx)i=⌊xi+qi−12⌋,qi=⌈xi+qi−12⌉.(Tx)_i=\left\lfloor\frac{x_i+q_{i-1}}{2}\right\rfloor,\qquad q_i=\left\lceil\frac{x_i+q_{i-1}}{2}\right\rceil.

Here qiq_i is the number of small chips continuing to the first child. Stop once all incoming entries have been used and the carry is 11. Also set T(0)=0T(0)=0.

Let Xm(r)X_m^{(r)} be the list of new entries into diagonal rr when there are mm small chips. Equivalently,

Xm(0)=me0,Xm(r+1)=T(Xm(r)).X_m^{(0)}=m e_0,\qquad X_m^{(r+1)}=T\left(X_m^{(r)}\right).

where eie_i denotes one small chip entering at index ii. Write ∣x∣=∑ixi|x|=\sum_i x_i for the total number of small chips in the list. As explained above, every nonempty diagonal reduction omits exactly one chip. Hence

∣Xm(r)∣=max⁡{m−r,0}.\left|X_m^{(r)}\right|=\max\{m-r,0\}.

After m−1m-1 reductions, exactly one small chip enters the diagonal. By Lemma 16, this must be chip mm. Theorem 21 shows that it enters diagonal m−1m-1 at the least first coordinate aa for which chip mm can reach (a,m−1)(a,m-1). In particular, the value g(m−1)g(m-1) is well defined, and

Xm(m−1)=eg(m−1).X_m^{(m-1)}=e_{g(m-1)}.

We record two properties of diagonal reduction. First, the operation TT is monotone: if x≤yx\le y entry by entry, then Tx≤TyTx\le Ty. This follows directly from the formulas for the outputs and carries. Second, the nonzero entries of every nonempty Xm(r)X_m^{(r)} occupy consecutive indices. This is true initially. If the occupied indices of the incoming list are consecutive, then after the first positive input, the carry stays positive through the occupied indices. The outputs there are positive, except possibly at the smallest occupied index. Beyond the last input, they stay positive until the carry becomes 1.

Adding one small chip. Compare Xm(r)X_m^{(r)} and Xm+1(r)X_{m+1}^{(r)} for 0≤r≤m−10 \le r \le m - 1. By monotonicity and the size formula, their difference is one extra chip. We claim that its index is at most one greater than the largest occupied index of Xm(r)X_m^{(r)}.

This is true initially. Suppose the claim holds before a reduction in which the smaller list contains at least two small chips. Let RR and R′R' be the largest occupied indices of the smaller list before and after reduction. Since the occupied indices are consecutive, we have R′≥RR' \ge R. Indeed, if RR is the only occupied index, the entry there is at least 2, so the reduced list has a chip at index RR. Otherwise, the positive carry from the preceding occupied index produces a chip at index RR. Thus R′≥RR' \ge R.

The extra chip therefore has index at most R′+1R' + 1. Until it produces an extra output, it continues as an extra unit of carry. If no extra output has appeared by index R′R', then the total input at index R′+1R' + 1 increases from 1 to 2, producing an extra output there. This proves the claim by induction.

Put A=g(m−1)A = g(m - 1). At diagonal m−1m - 1, we have

Xm(m−1)=eA,Xm+1(m−1)=eA+epX_m^{(m-1)} = e_A,\qquad X_{m+1}^{(m-1)} = e_A + e_p

for some p≤A+1p \le A + 1. Reducing a list with two small chips leaves one chip in the greater of their two indices. Hence g(m)=max⁡{A,p}g(m) = \max\{A,p\} is either AA or A+1A + 1, proving the first pair of inequalities.

Adding two small chips. Now compare Xm(r)X_m^{(r)} and Xm+2(r)X_{m+2}^{(r)} for 0≤r≤m−10 \le r \le m - 1. Their difference consists of two extra chips. If LL is the smallest occupied index of the smaller list, we claim that neither extra chip has an index less than L−1L - 1, and at most one has index L−1L - 1.

This is true initially. Suppose it holds before a reduction, with at least two small chips in the smaller list. If the entry at index LL is at least 2, the reduced list still begins at index LL. A single extra chip at index L−1L - 1 produces no output there, so the claim remains true.

If the entry at index LL equals 1, the reduced list begins at index L+1L + 1, since the occupied indices are consecutive. No extra output can appear at an index less than LL. At most two extra inputs can reach index LL, making its total input at most 3. Hence, at most one extra output appears at index LL. This proves the claim relative to the new smallest occupied index L+1L + 1.

Again put A=g(m−1)A = g(m - 1). On diagonal m−1m - 1, the larger list consists of the chip at AA and two extra chips, neither with index less than A−1A - 1 and at most one with index A−1A - 1. If some chip has index greater than AA, let RR be the largest occupied index.

Since the occupied indices are consecutive and there is a chip at index A<RA < R, a positive carry reaches index RR. Together with the chip already there, it produces an output at index RR. The resulting list has two chips, so its next reduction leaves one chip at the greater of their two indices, which is at least RR.

Otherwise, the three-chip list is either 3eA3e_A or eA−1+2eAe_{A-1} + 2e_A. In both cases its next reduction is eA+eA+1e_A + e_{A+1}, followed by eA+1e_{A+1}. Again g(m+1)>Ag(m + 1) > A. Substituting m=b+1m = b + 1 proves g(b+2)>g(b)g(b + 2) > g(b).

Finally, the function gg satisfies g(0)=0g(0)=0 and g(b+2)>g(b)g(b+2)>g(b), and its successive increments are 0 or 1. Therefore, the function gg is unbounded and takes every nonnegative integer value either once or twice. This shows that h(a)h(a) is finite. Replacing aa by a+1a+1 adds exactly the second coordinates bb with g(b)=a+1g(b)=a+1.

The boundary lemma gives a region where the lower bound μ(a,b)≥b+1\mu(a,b)\ge b+1 is attained.

Proposition 29. We have h(0)=1h(0)=1, and, for every a≥1a\ge1, we have

a+2≤h(a)≤2a+1.a+2\le h(a)\le2a+1.

Consequently,

μ(a,b)=b+1if a≥1 and 0≤b≤a+2,\mu(a,b)=b+1 \qquad\text{if } a\ge1 \text{ and } 0\le b\le a+2,

whereas, for every a≥0a\ge0, we have

μ(a,b)>b+1if b≥2a+2.\mu(a,b)>b+1 \qquad\text{if } b\ge2a+2.

In particular, if a,b≥1a,b\ge1, ∣a−b∣≤2|a-b|\le2, and N≥2a+bN\ge2^{a+b}, then the smallest and largest chips that can reach (a,b)(a,b) are, respectively,

b+1andN−a.b+1 \qquad\text{and} \qquad N-a.

Proof. The formula μ(0,b)=2b\mu(0,b)=2^b gives h(0)=1h(0)=1. Example 17 gives g(3)=1g(3)=1, so h(1)≥3h(1)\ge3. On the other hand, Lemma 28 gives h(1)≤h(0)+2=3h(1)\le h(0)+2=3. Thus h(1)=3h(1)=3.

Each subsequent increment of hh is at least 1 and at most 2. Therefore, for a≥1a\ge1, we have

h(a)≥h(1)+(a−1)=a+2,h(a)≤h(0)+2a=2a+1.h(a)\ge h(1)+(a-1)=a+2,\qquad h(a)\le h(0)+2a=2a+1.

Since gg is nondecreasing, we know that, for each fixed aa, the lower bound is attained exactly when 0≤b≤h(a)0\le b\le h(a). This proves the assertions about μ(a,b)\mu(a,b).

Finally, if a,b≥1a,b\ge1 and ∣a−b∣≤2|a-b|\le2, then both μ(a,b)=b+1\mu(a,b)=b+1 and μ(b,a)=a+1\mu(b,a)=a+1. Corollary 23 gives the claimed extreme labels.

Acknowledgments

The first and second authors are employed by the MIT Department of Mathematics. The third author is supported by Harvard College.

All figures in this paper were generated using TikZ via mathcha.io and exported as PDF. The writing was assisted by Claude and ChatGPT.

References

  1. [1]Anders Björner and László Lovász. Chip-firing games on directed graphs. J. Algebraic Combin., 1(4):305–328, 1992.DOI
  2. [2]Benjamin Bond and Lionel Levine. Abelian networks I. Foundations and examples. SIAM J. Discrete Math., 30(2):856–874, 2016.arxiv.org/abs/1309.3445
  3. [3]Didier Caucal. Cayley graphs of basic algebraic structures. Discrete Math. Theor. Comput. Sci., 21(1):Paper No. 16, 19, 2019.
  4. [4]Sam Hopkins, Thomas McConville, and James Propp. Sorting via chip-firing. Electron. J. Combin., 24(3):Paper No. 3.13, 20, 2017.DOI
  5. [5]Ryota Inagaki, Tanya Khovanova, and Austin Luo. Chip firing on directed k-ary trees. Enumer. Comb. Appl., 5(2):Paper No. S2R16, 14, 2025.arxiv.org/abs/2410.23265
  6. [6]Ryota Inagaki, Tanya Khovanova, and Austin Luo. Labeled Chip-Firing on Directed k-ary Trees and Where Chips Land. Preprint, arXiv:2506.20656 [math.CO] (2025), 2025.arxiv.org/abs/2506.20656
  7. [7]Ryota Inagaki, Tanya Khovanova, and Austin Luo. On chip-firing on undirected binary trees: R. inagaki et al. Annals of Combinatorics, pages 1–27, 2025.DOI
  8. [8]Ryota Inagaki, Tanya Khovanova, and Austin Luo. Chip-firing on the Lattice of Nonnegative Integer Points. Preprint, arXiv:2601.09125 [math.CO] (2026), 2026.arxiv.org/abs/2601.09125
  9. [9]Ryota Inagaki, Tanya Khovanova, and Austin Luo. Permutation-based strategies for labeled chip-firing on k-ary trees. Discrete Mathematics & Theoretical Computer Science, vol. 28:2, Jan 2026.DOI
  10. [10]Gregg Musiker and Son Nguyen. Labeled chip-firing on binary trees with 2ⁿ − 1 chips. Ann. Comb., 28(4):1167–1197, 2024.DOI
  11. [11]OEIS Foundation Inc. The On-Line Encyclopedia of Integer Sequences, 2026. Published electronically at http://oeis.org.

Paper details

vlnc:W_6t7chsae
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
CC BY 4.0
Usage

views · 10

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Mathematics

Claude, ChatGPT

View statement
Looking for related papers…
Contents