{'fraction_non_alphanumeric': 0.04105905079353055, 'fraction_numerical': 0.00901481004507405, 'mean_word_length': 4.007966616084977, 'pattern_counts': {'":': 0, '<': 0, '<?xml version=': 0, '>': 1, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 1, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Motors and Impossible Firing Patterns in the Parallel Chip-Firing Game

The parallel chip-firing game is an automaton on graphs in which vertices"fire"chips to their neighbors when they have enough chips to do so. The game is always periodic, and we concern ourselves with the firing sequences of vertices. We introduce the concepts of motorized parallel chip-firing games and motor vertices, study the effects of motors connected to a tree and show that motorized games can be transformed into ordinary games if the motors' firing sequences occur in some ordinary game. We then characterize exactly which periodic firing patterns can occur in an ordinary game and state some implications of the finding.


Introduction
Background. The parallel chip-firing game, also known as the discrete fixed-energy sandpile model, is an automaton on graphs in which vertices that have at least as many chips as incident edges "fire" chips to their neighbors. In graph theory, it has been studied in relation with the critical group of graphs [3]. In computer science, it is able to simulate any two-register machine and is thus universal [8]. As a specific case of the abelian sandpile model, which is itself a generalization of a sandpile model introduced by Bak, Tang, and Weisenfeld [1,2] in the study of self-organized criticality, it has even more links with other fields.
The Game. The parallel chip-firing game is played on a graph as follows: • At first, a nonnegative integer number of chips is placed on each vertex of the graph. • The game then proceeds in discrete turns. Each turn, a vertex checks to see if it has at least as many chips as incident edges.
-If so, that vertex fires.
-Otherwise, that vertex waits. • To fire, a vertex passes one chip along each of its edges. All vertices that fire in a particular turn do so in parallel. • Immediately after firing or waiting, every vertex receives any chips that were fired to it.
Here we will only consider games on finite, undirected, connected graphs, though the definition of the game can be easily generalized for arbitrary multidigraphs. An example game is illustrated in Figure 1. Given a parallel chip-firing game as σ, we refer to the chip configuration, also called the position, at a particular time t ∈ N as σ t . The total number of chips on all vertices of the graph is constant throughout a game, so there are finitely many possible positions in every game. Therefore, every game eventually reaches a position σ t that is identical to a later position σ t+p for some t, p ∈ N with p > 0. (We write σ t = σ t+p .) The game is deterministic, so σ t+n = σ t+n+p for all n ∈ N. Thus, every parallel chip-firing game is eventually periodic.
In this paper, we concern ourselves with both firing sequences and periodic firing patterns of vertices. Each is a binary string representing whether or not a particular vertex fires or waits each turn. The sequence covers all times from 0 to infinity, while the periodic pattern covers just one period.
Previous Work. The periodicity of the parallel chip-firing game gives rise to two questions. First, what characteristics of a game and its underlying graph determine the length of a period? It is known exactly what periods are possible on certain classes of graphs, such as trees [4], simple cycles [6], the complete graph [13], and the complete bipartite graph [10]. For these graphs, the maximum period lengths are bounded by the number of vertices, but Kiwi et al. [11] constructed graphs on which the period of games can grow exponentially with polynomial increase in the number of vertices. There are also results regarding the total number of chips in a game. Kominers and Kominers [12] showed that games with a sufficiently large density of chips must have period 1. Dall'Asta [6] and Levine [13], in their respective characterizations of periods on cycles and complete graphs, related the total number of chips to a game's activity, the fraction of turns during which a vertex fires. The denominator of the activity must divide the period.
Second, we notice that some but not all positions σ t are periodic, satisfying σ t = σ t+p for some positive p ∈ N. What characterizes periodic positions? This problem has not been as extensively studied. Dall'Asta [6] characterized the periodic positions of games on cycles.
Our Results. We hope to advance the understanding of both of these questions through the study of firing sequences and periodic firing patterns.
After precisely defining the parallel chip-firing game in Section 2, the first half of the paper develops a new tool for studying the chip-firing game: motors, vertices that fire with a regular pattern independent of normal chipfiring rules. Games with motors are called motorized games. Motors allow us to study the behavior of subgraphs in ordinary parallel chip-firing games. In Section 3 we show that vertices always "follow" a motor in periodic motorized games on trees. In Section 4, we prove that periodic motorized games can be transformed into ordinary games as long as the firing sequence of each motor occurs in an ordinary game.
The second half of the paper characterizes the possible periodic firing patterns in parallel chip-firing games. Section 5 briefly steps away from the game to study certain signed sums of periodic binary sequences. The result is an inequality applicable to edges of the graph of a parallel chip-firing game. In Section 6, we sum this inequality over all relevant edges to show that periodic firing patterns with both consecutive 0s and consecutive 1s cannot occur in a parallel chip-firing game. This, along with an already known construction, fully characterizes the periodic firing patterns possible in parallel chip-firing games. Finally, in Section 7, we examine some implications of this theorem.

Preliminaries
Definitions. A parallel chip-firing game σ on a graph G = (V (G), E(G)) is a sequence (σ t ) t∈N of ordered tuples with natural number elements indexed by V (G). Each tuple represents the chip configuration at a particular turn, where each element of the tuple is the number of chips on the corresponding vertex. We define the following for all v ∈ V (G): In a parallel chip-firing game, σ t induces σ t+1 . For all v ∈ V (G), so an initial position suffices to define a game on a given graph. When F t (v) = 0, we say v waits at t, and when F t (v) = 1, we say v fires at t. A position σ t is periodic if and only if there exists p ∈ N such that σ t = σ t+p . The minimum such p for which this occurs is the period of σ and is denoted T . Abusing notation slightly, "a period" of a game σ may also refer to a set of times {t, t + 1, . . . , t + T − 1}, where σ t is periodic. The parallel chip-firing game is deterministic and there are finitely many possible positions on a given graph with a given number of chips, so for any game σ, there exists t 0 ∈ N such that σ t is periodic for all t ≥ t 0 . If the initial position of a game is periodic, we may also call the game itself periodic.
Notation. Definitions for invented notation are given in the section indicated in the last column.

Parallel Chip-Firing
Defined in

Section 3
T σ Period of σ. Section 2 M σ Set of vertices that are motors in σ. Section 3 P σ Set of periodic firing patterns in σ.

Section 6
Q σ Set of "clumpy" periodic firing patterns in σ.
We leave out the subscript G or superscript σ if there is no ambiguity.

Motors
Let G be a graph. Suppose we wish to study the periodic behavior of games on G, focusing on a particular subgraph H ⊆ G. Consider the set of vertices "just outside" of H. Knowing the initial chip configuration on V (H) ∪ X is in general not enough to determine all subsequent configurations because vertices in X may have interactions with vertices outside of V (H) ∪ X. However, we do know that every vertex assumes a pattern of firing and waiting that repeats periodically as soon as a game reaches a periodic position. Therefore, we can simulate the presence of the rest of G by having each vertex in X fire with a regular pattern regardless of the number of chips it receives.
The firing sequence of a vertex v in game σ is the sequence (F t (v)) t∈N . A motorized parallel chip-firing game, or simply "motorized game", on G is a game σ obeying (2.1) with a non-empty set of motors M ⊆ V (G). Each motor follows a predetermined firing sequence, firing without regard for the normal rules of the parallel chip-firing game, which means, for example, that a motor may have a negative number of chips. Put another way, for each m ∈ M , F t (m) does not depend on σ t (m). The term "ordinary game" refers to a game with no motors when there is ambiguity. A motorized game is shown in Figure 2. If a motorized game σ is eventually periodic (which is the case if every motor's firing sequence is eventually periodic), then just as in an ordinary game, every vertex fires the same number of times each period. The proof is identical to the proof of this fact for ordinary games [10]: all neighbors of the vertex that fires the most times each period must also fire that maximal number of times, and by induction, so do all vertices. (Recall that we consider in this paper only connected graphs.) We define Given v ∈ V (G), we can express N as the union of max-clumps of v and times during which v alternates between firing and waiting.
The proof of Theorem 3.2 follows the same structure as the proof that ordinary games on trees have period 1 or 2 [4]. In fact, we rely on a lemma originally introduced for that proof.
Less technically, every burst of firing or waiting by a vertex must be supported by at least one of its neighbors. The lemma follows from the pigeonhole principle and Lemma 6.1, which we state and prove later.
Proof. The fact that σ is periodic means we need not worry about negative turn indices. Let . If there is a maximum i for which v i exists, that vertex must be a motor, which would mean where D is the maximum i and m = v D ∈ M . Thus, it suffices to show that the sequence {v 0 , v 1 , . . .} eventually terminates. There are finitely many vertices in the graph, so it suffices to show that the v i are all distinct.
T has no cycles, Call a firing sequence clumpy if it contains two consecutive 0s and two consecutive 1s; otherwise, call it nonclumpy. Corollary 3.3. Let σ be a periodic motorized game on tree M with a single motor m. If m has a nonclumpy firing sequence but has at least one maxclump, then F t+D (v) = F t (m) for all v ∈ V (T ) and t ∈ N, where D is the distance from v to m.

Proof.
Let v ∈ V (T ). By Theorem 3.2, v has a nonclumpy firing sequence because m does. All vertices fire the same number of times every period [10, Proposition 2.5], so v must have at least one max-clump, again because The non-max-clump intervals of v's firing sequence are alternations between 0 and 1, starting and ending with 1 − f . The same must be true of m for it to fire the same number of times each period as v.
The reason we require the games in Theorem 3.2 and Corollary 3.3 to be periodic is to consider arbitrarily many past turns. We can likely weaken this condition if we require the statements to be true only after sufficiently many turns, though exactly how many turns that is could depend on the activity (firing frequency; see [13]) of the motor, the size of the tree, and the total number of chips in the initial position.

Simulating Motors
In this section, to refer to multiple chip-firing games unambiguously, we include the subscripts and superscripts in, for example, d G (v) and F σ t (v). We call a firing sequence (f t ) t∈N possible if there exists an ordinary game σ on some graph G such that F σ t (v) = f t for all t ∈ N. Our next theorem states that we can simulate motorized games with ordinary games as long as every motor's firing sequence is possible. Figure 3 demonstrates the concept.  Figure 3. Suppose the motor in motorized game (b) has firing sequence (0, 0, 0, 0, 1, 0, 0, 0, . . . ). This occurs in ordinary game (a). By using sufficiently many copies of (a) and carefully choosing n, we construct (c). The behavior of G in (c) is identical to the behavior of G in (b).
Theorem 4.1. Let σ be a periodic motorized game on G. If every motor's firing sequence is possible, then there exists an ordinary game σ on a graph edges between vertices of G that are not also in G.) Proof. Our approach will be, for each m ∈ M σ , to attach many copies of a graph with a vertex with m's firing sequence to m. If sufficiently many copies are attached, the number of chips m has due to its neighbors in G becomes irrelevant as to whether or not it fires. For each m ∈ M σ , let A m be a graph such that there exists a game σ m and some vertex It is clear by construction that H contains no new edges between vertices of G and that Suppose that for some t ∈ N, σ t satisfies the following. ( We will show that σ t+1 satisfies the above as well. We have d H We can distribute chips in σ 0 such that it satisfies (1), (2), and (3), in which case, by induction, σ t satisfies (1), (2), and (3) Again, we may relax the condition that the game be periodic. In this case, the periodicity ensures that the number of chips on each motor is bounded. This is easily shown to be equivalent to each motor having the same activity, so that is a sufficient condition for the theorem. Of course, because all ordinary games are eventually periodic, any motorized game in which each motor has a possible firing sequence will eventually be periodic.
In Theorem 3.2, motors were primarily a convenient intuition and terminology; we could have proved a similar theorem within the context of the ordinary parallel chip-firing game, though its statement would have been messier. Theorem 4.1 demonstrates another way in which the motor concept is useful. Its constructive power makes certain conjectures easy to prove or disprove by example. For instance, motors make it easy to construct games in which the period isn't bounded by the number of vertices.

Signed Sums of Binary Sequences
Throughout this section, if b ∈ {0, 1}, we may write b = 1 − b. We take a break from the parallel chip-firing game to consider binary strings. We denote the i th element of a binary string p as p i . For simplicity, any integer equivalent to i mod n may replace i. Let a b-sector of p, where b ∈ {0, 1}, be an integer interval [x, y] such that That is, the image of a 0-sector is preceded by two 1s, starts with 0, ends with two 0s and contains no two consecutive 1s. The same statements with 0s and 1s swapped are true for 1-sectors.
It is easy to see that almost any string can be partitioned into 0-and 1-sectors in exactly one way, with exceptions only for always-alternating strings (e.g. 010101) that can be thought of as one 0-sector or one 1-sector. Figure 4 has an example. Let Our main theorem in this section concerns the sum where p, q are length-n binary sequences and S ⊆ [0, n−1]. This sum, superficially speaking, measures each sequence's "disagreement" with the other shifted back one step minus the number of sector switches. The rules of the parallel chip-firing game put a global upper bound on the total disagreement between vertices, yet the following theorem says that sector switches require disagreement. We show in Section 6 that this implies that firing sequences with sector switches are impossible once a game has become periodic. Proof. We can caculate M [0,n−1] (p, q) as n−1 i=0 M {i} (p, q), and M {i} (p, q) is determined by p i−1 , p i , s i (p), s i+1 (p), and the same data for q. The motivation for using s i+1 (p) as opposed to s i−1 (p) in δ i (p) is that a switch away from a b-sector can occur between i and i + 1 only if and let G be a weighted digraph with (The third item of each edge is its weight.) Note that not every possible tuple is a vertex. Define the weight of a path to be the sum of the weights of its member edges, and call a path negative if it has negative weight. We can calculate the M [0,n−1] (p, q) as the weight of a path induced by the sequence of vertices (µ 0 (p, q), . . . , µ n−1 (p, q), µ 0 (p, q)). Therefore, it suffices to show that G has no negative cycles. Running the Bellman-Ford algorithm [5] on G shows this to be the case. We describe G and the algorithm in a Python program in Appendix A.

Nonclumpiness of Periodic Firing Patterns
We consider parallel chip-firing game σ on undirected graph G. The periodic firing pattern (PFP) of a vertex v ∈ V (G) is the binary string where t 0 is the smallest natural number such that σ t 0 is periodic 1 . We write the PFP of v as F (v). For simplicity, we assume here that t 0 = 0 and index PFPs modulo T .
Let P be the set of all PFPs occurring in σ. Call a PFP with both consecutive 0s and consecutive 1s clumpy, and let Q be the set of all clumpy PFPs occurring in σ. (Recall that the T th and 0 th entries of a PFP are the same, so, for example, 011010 is clumpy.) It is known that, given almost any 2 nonclumpy PFP, one can construct a parallel chip-firing game on a simple cycle in which every vertex has that PFP shifted by some number of steps [6]. We prove here that clumpy PFPs cannot occur in any parallel chip-firing game.
Proof. We express σ b (v) in terms of σ a−1 (v).
such that σ t is periodic, which gives the desired inequality. 1 The reason we introduce PFPs instead of continuing to reason with firing sequences is because a PFP is aware of the period of the game it occurs in. For instance, the PFPs 01 and 0101 result in the same periodic firing sequence, but while latter might occur in the same game as the PFP 0011, the former cannot. 2 The given construction requires that the PFP not be decomposable to a repeated substring. Using Theorem 4.1, one can expand the construction to any nonclumpy PFP other than those that are 01 or 10 repeated more than once. These PFPs turn out to be impossible, though the corresponding firing sequences are possible in games of period 2.
We define for binary strings p and q. We now prove our main result: clumpy PFPs do not occur in the parallel chip-firing game.
Proof. Roughly, summing an inequality given by Lemma 6.1 over all vertices with clumpy PFPs bounds a quantity below, and summing an inequality given by the Theorem 5.1 over all edges incident with a vertex with a clumpy PFP gives an upper bound on the same quantity. The lower bound is the total number of vertices with clumpy PFPs, and the upper bound is 0. Let a, b ∈ N and v ∈ V (G). Grouping the sum in (6.1) by v's neighbors instead of time steps yields Regrouping gives us where r = ±1. Let p ∈ P . The above summed over v ∈ τ (p) is where each r v = ±1 can depend on v. (Notation: ranges for outer sums are above ranges for inner sums.) For all p ∈ P , let X (p) be the set of sectors of p. Abusing notation slightly, we may write s X (p) instead of s i (p) if i ∈ X ∈ X (p). Because each X ∈ X (p) is of the form [a, b] for some a, b ∈ N, we can sum the above inequality over X ∈ X (p) and p ∈ Q to get where each r v,X = ±1 can depend on v and X.
Let p ∈ Q and q ∈ P . If q is clumpy, then The −1 in each sum accounts for the −δ i (p) − δ i (q) term in (5.1), the definition of M . If instead q is not clumpy, then X (q) = {[0, T − 1]}, so However, m [0,T −1] (q, p) = 0 because p and q have the same length and number of 1s.
∈ Q} be the set of vertices with clumpy PFPs. Choosing r v,X = −s X (F (v)) and splitting the sum in (6.2) between neighbors with and without clumpy PFPs yields The last line follows from Theorem 5.1, and when we sum over p, q ∈ Q, we consider p and q unordered. (A sum over {p, q} ⊆ Q is one alternative notation.) Sets have nonnegative sizes, so #τ (p) = 0 for all p ∈ Q.

Implications of Nonclumpiness
It is a basic property of the parallel chip-firing game that every vertex fires the same number of times each period [10]. This means, roughly speaking, that every periodic game is either "mostly waiting" with bursts of firing or "mostly firing" with bursts of waiting. (In fact, there is a bijection between them. Each periodic game has a complement that inverts firing and waiting [10].) This is because if a vertex waits twice in a row, then because it therefore never fires twice in a row, it fires less than half the time over the course of a period. Similarly, a vertex that fires twice in a row fires more than half the time. We cannot have a vertex that waits twice in a row and a vertex that fires twice in a row in the same periodic game because each vertex fires the same number of times each period. Corollary 7.1. Once a parallel chip-firing game reaches a periodic position, either no vertex fires twice in a row or no vertex waits twice in a row.
That is, in periodic games, a firing sequence is possible if and only if it is nonclumpy.
Let the interior of a set of vertices W be I(W ) = {v ∈ W | N (v) ⊆ W }. Because a waiting (or firing) vertex with only waiting (or firing) neighbors will wait (or fire) the following turn as well, the above observation proves the following conjecture of Fey and Levine [7].
Corollary 7.2. Let σ be a periodic game on G, where a, b ∈ N. Then either I(A) or I(B) is empty.
Interestingly, Corollary 7.2 also implies Theorem 6.2. If clumpy PFPs were possible, then a leaf attached to a motor with a clumpy PFP would be in I(A) and I(B) for appropriately chosen a, b ∈ N.
In one of the first papers on the parallel chip-firing game, Bitar and Goles characterized parallel chip-firing games on trees in [4]. Corollary 3.3 and Theorem 6.2 allow us to characterize the behavior on tree-like subgraphssubgraphs such that, if an edge to a root vertex is cut, become a tree separated from the rest of the graph-by making the root vertex a motor.
where D is the distance from m to v. An analogous result holds if no vertex waits twice in a row.
In some sense, tree-like subgraphs are passive in that their vertices fire only in response to their root-side neighbor firing. In a periodic game, we can completely remove tree-like subgraphs without affecting the PFPs of the other vertices.
An analogous result holds if no vertex waits twice in a row.
Compared to σ , m has to have an extra chip to fire in σ. However, unless m fired the previous turn-which, because l is a leaf, is equivalent to saying l is firing this turn-m will have received the extra chip back from l, so removing both l and the chip has no effect on m as long as m does not fire while l has a chip. This corollary concerns a leaf, though the result generalizes to all tree-like subgraphs by repeated application, providing an alternate proof of Corollary 3.3.

Discussion and Directions for Future Work
We have introduced motors, studied motorized games on trees, and shown that motor-like behavior can be constructed in ordinary games, provided that each motor has a possible firing sequence. We then showed that periodic firing patterns are possible if and only if they are nonclumpy, which, among other things, allows classification of periodic games as "mostly waiting" or "mostly firing" and the removal of tree-like subgraphs without loss of generality.
We might expect that the space of motorized games be larger than that of ordinary games. Theorem 4.1 shows us that, as long as the firing sequences involved are possible, the parallel chip-firing game is in some sense just as "expressive" as its motorized variant. This allows, for example, the simulation of some aspects of the dollar game, a variant of the general chip-firing game discussed by Biggs [3]. In the dollar game, exactly one vertex, the "government", may have a negative number of chips and fires if and only if no other vertices can fire. We can construct a motorized parallel chip-firing game in which we replace the government with a motor that waits a sufficiently large number of steps between each firing such that it never fires in the same step as another vertex. Biggs showed that every dollar game tends towards a critical position regardless of the order of vertex firings, so this motorized parallel chip-firing game tends towards the same critical position. Theorem 4.1 may help reveal the extent to which the parallel chip-firing game can simulate additional aspects of the dollar game and other general chip-firing games.
Despite the expressiveness we get due to motors, the nonclumpiness of firing patterns tells us that the parallel chip-firing game is "easier" than its rules explicitly tell us it must be. In addition to results mentioned in Section 7, Theorem 6.2 is a step towards reducing the parallel chip-firing game to one of interacting "gliders". For example, consider the situation in Corollary 3.3. Intuitively, we can think of this corollary as stating that each firing of the motor creates a wave of gliders that travels away from the motor. In fact, the corollary, together with Theorem 6.2, implies that every periodic position on tree-like subgraphs must be the result of such gliders, providing a new test that can diagnose some positions that are never repeated. Every game on a simple cycle with period at least 3 can be described by gliders [6]. (See Figure 5.) We believe that this approach could be used to analyze periodic behavior of games on further classes of graphs, such as those in which each vertex is in at most once cycle. Nonclumpiness is essentially an unwritten rule of periods in the parallel chip-firing game, which is unusual because no local property of the firing mechanic disallows clumpiness. By contrast, in other graph automata that are more restrictive than the parallel chip-firing game, such as source reversal [9] (essentially a parallel chip-firing game with exactly one chip bound to each edge), nonclumpiness is obvious, even locally. In the other direction, motors make it simple to show that certain stronger restrictions do not apply to the parallel chip-firing game. For example, a path where the leaves are motors can yield a game in which some chips cannot be bound to a single edge, which is is a property of source reversal. We might ask which restrictions apply to which chip-firing-style games. Is the parallel chip-firing game on undirected graphs the most general game to which an analogue of Theorem 6.2 applies?
We hope that the intuition and constructive powers of motors and the reduction in the space of possible periodic games provided by nonclumpiness prove useful in further research.