{'fraction_non_alphanumeric': 0.04856507679870655, 'fraction_numerical': 0.019704931285367825, 'mean_word_length': 3.896200277063131, 'pattern_counts': {'":': 0, '<': 1, '<?xml version=': 0, '>': 3, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 1, 'word_list_counts': {'cursed_substrings.json': 2, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
On the Classification of Universal Rotor-Routers

The combinatorial theory of rotor-routers has connections with problems of statistical mechanics, graph theory, chaos theory, and computer science. A rotor-router network defines a deterministic walk on a digraph G in which a particle walks from a source vertex until it reaches one of several target vertices. Motivated by recent results due to Giacaglia et al., we study rotor-router networks in which all non-target vertices have the same type. A rotor type r is universal if every hitting sequence can be achieved by a homogeneous rotor-router network consisting entirely of rotors of type r. We give a conjecture that completely classifies universal rotor types. Then, this problem is simplified by a theorem we call the Reduction Theorem that allows us to consider only two-state rotors. A rotor-router network called the compressor, because it tends to shorten rotor periods, is introduced along with an associated algorithm that determines the universality of almost all rotors. New rotor classes, including boppy rotors, balanced rotors, and BURD rotors, are defined to study this algorithm rigorously. Using the compressor the universality of new rotor classes is proved, and empirical computer results are presented to support our conclusions. Prior to these results, less than 100 of the roughly 260,000 possible two-state rotor types of length up to 17 were known to be universal, while the compressor algorithm proves the universality of all but 272 of these rotor types.


Introduction
The rotor-router model gives a deterministic analogue to random walks on directed graphs (digraphs). It is an offshoot of the abelian sandpile, or chip-firing, model introduced by Bak, Tang, and Wiesenfield [1] to study physical phenomena collectively known as "self-organized criticality." Work by Dhar [3] and others on chip-firing gave new insights into phenomena such as the spreading of forest fires, the formation of fractal-like river networks, and other problems in statistical mechanics. Their work, notably the discovery of the sandpile group, laid the groundwork for further progress in chip-firing and rotor-routing. More recent combinatorial work on chip-firing can be found in the work of Diaconis and Fulton [2], and that of Levine [8].
Rotor-routers, first introduced by Priezzhev et al. [10] to study self-organized criticality, were then independently rediscovered several times in various connections. These include

Background and Motivation
On a finite directed graph G = (V, E), allowing self-loops and multiple edges, a rotorrouter network is imposed as follows. We choose a source vertex as well as a set of target vertices with outdegree 0. Every non-target vertex must be able to reach at least one target. At each non-target vertex, we choose a rotor pattern denoted e (1) v , e (2) v , . . . comprising an infinite periodic sequence of the directed edges emanating from v.
A particle travels through the network, beginning at the source and traveling until it reaches a target, whereupon it is returned to the source and commences a new walk. After its n-th visit to non-target vertex v, the particle leaves v along edge e (n) v . At this moment, we say that the first n terms of the rotor pattern at v have been used up, or fired. It is important to note that this scheduling policy is purely local and deterministic, and does not depend on the in-edge by which the particle enters v. The hitting sequence of the network is defined as the infinite sequence of targets successively visited by this particle. Hitting sequences are eventually periodic; in [4], it is shown that they are also periodic from the start.
Each rotor pattern can be described by a partition π of {1, 2, . . . , n} (this set is denoted [n]) where n is its period, and i, j ∈ [n] are partitioned into the same block of π iff e Each block of π is associated with a distinct natural number, which gives a representation of the rotor that we call its rotor type. There are an infinite number of such representations for every rotor pattern. For instance, if the pattern at a vertex v with two out-edges e and e is the sequence e, e , e , e, e , e , . . . with period 3, we can write its type as 1, 2, 2, or as 4, 7, 7. Typically if all the numbers are single digits, commas are omitted and we write 122 or 477 instead.
Often, we abuse these definitions and use the terms "rotor pattern," "rotor type," and "rotor" interchangeably to avoid cumbersome language.
A rotor is said to have m states if exactly m distinct natural numbers appear in its type. Two rotor types r, r are said to be equivalent if they can represent the same rotor pattern. This is denoted r ≡ r . Thus 122 ≡ 477.
Given a rotor type r, the notation |r| denotes its period length, and r (k) represents its k-th term, where k is taken modulo |r|.
Propp introduced the idea that an entire rotor-router network can be thought of as a single meta-rotor with rotor pattern equivalent to its hitting sequence, since hitting sequences are always periodic.
To formalize this concept, we say that a rotor type r can model a rotor type r if there exists a homogeneous rotor-router network, one containing only rotors of type r, with a hitting sequence equivalent to r . Working off this idea, Propp defined a universal rotor as a rotor that can model any other. Propp then raised the natural question: which rotor types r are universal?
A rotor type is called palindromic if it reads the same forwards and backwards (e.g. 121), and block-repetitive if it is the concatenation of uniform sequences of the same length m (e.g. 1122). The length m is known as the block length of such a rotor. We define: Definition 1. By a block of length m of a rotor type r, where m divides |r|, we mean a subsequence of r of the form r (km+1) , r (km+2) , ..., r (km+m) , where k ∈ N. We call this specific block the (k + 1)-th block of length m of r, denoted r (k,m) .
A block-repetitive rotor of block length m is one such that every block of length m is uniform. It is important to distinguish blocks from runs, where the two are distinct in that r (a+1) , r (a+2) , . . . , r (a+b) is always a run of r but only a block if b divides a. Uniform runs are important in Section 7.
It was proven by Giacaglia et al. [4] that a network composed entirely of palindromic rotors has a palindromic hitting sequence, and similarly that a network composed entirely of block-repetitive rotors of block length m ∈ N has a block-repetitive hitting sequence with the same block length m. From these results it follows that neither palindromic nor block-repetitive rotor types can be universal. We believe these two classes encompass all nonuniversal rotors, so the following definition is natural: A rotor type is boppy if it is palindromic or block-repetitive. Otherwise, it is unboppy.
Henceforth, all bold uppercase letters or words will stand for classes of rotors. We let ROT denote the class of all rotor types, PAL the class of all palindromic rotors, BR the class of all block-repetitive rotors, U the class of all universal rotors, and BOP = BR∪PAL the class of all boppy rotors. Also, S denotes the complement of a set S of rotors (with respect to ROT). In this notation, Giacaglia et al. [4] showed that U ⊆ BOP. We conjecture that more is true: As classes of rotor types U = BOP.
Let the notation C(p, b), where p ∈ {0, 1} and b ∈ N, define the class of rotor types that are palindromic iff p = 1 and block-repetitive with block length b (but no larger block length). The conjecture above can then be strengthened to: Conjecture 2 is only slightly stronger than Conjecture 1, since Conjecture 1 implies that any rotor of class C(0, b) is universal in that class. It would only remain to show the same for the palindromic classes C (1, b). Finally, we also present a weakening that is more directly amenable to our methods: Conjecture 3. Every rotor is universal in C(p, b) for some choice of p and b.
In this paper, Conjectures 1 through 3 will be our guiding focus, although we will make many related inquiries of independent interest.
The second half of this report focuses on the compressor configuration in Figure 3, so named because it tends to shorten the lengths of the rotors upon which it is applied. The compressor can be viewed alternatively as a rotor-router network, as a mapping from rotor types to rotor types, or simply as a mapping from binary strings to binary strings. This last viewpoint is discussed extensively in Sections 7 and 8.
A related issue put into focus by the action of the compressor is the definition of a complexity measure for periodic binary strings. With the similar process known as the differential operator, or Ducci map, the complexity of such strings can be defined in terms of the length of the end cycle when the map is applied repeatedly [7], or alternatively as the number of applications of the map before a term repeats. Since the compressor acts in an analogous way on balanced binary strings, we can also define a complexity measure of binary strings based on the compressor algorithm. This motivates our discussion of BURD and ab-ba rotors as the elements of fixed cycles of the compressor "map" on binary strings.

Examples
As a simple example of the rotor-router network, consider the directed graph in Figure  1. The underlying digraph, shown in Figure 1   1, 2, 3, 4, 5, of which vertex 1 is the source, as well as three targets 6, 7 and 8. The thin dark arrows denote the current state of the rotor at that vertex, or the direction by which the last particle left. In the other two diagrams, two walks of the particle to a target are traced by thicker dark arrows. Upon entering a new vertex, the particle shifts the rotor to the next possible exit direction (counterclockwise) and leaves along this new rotor setting. The rotor types are rather simple in this case, since the rotor patterns proceed counterclockwise; they are 1234, 12, 1, 12, and 123, at vertices 1, 2, 3, 4, 5, respectively. The hitting sequence begins 8, 6, as shown. From this example we already see some applications of rotor-routers. First, a rotor walk is the deterministic analogue of a random walk, since rotor walks hit targets with the same frequencies as their associated random walks do in expectation [6]. To be precise, rotorrouters are quasirandom in the sense that they are clearly nonrandom (unlike pseudorandom processes) and yet model random processes in some ways. Perhaps, if a randomized algorithm can be replaced with one involving rotor-routers, deterministic worst-case bounds may be given in place of probabilistic time bounds. It is not difficult to imagine how rotor-routers could be useful in load-balancing for parallel processing [11]. This "derandomization" has also been used successfully to study the IDLA problem about random walks on the plane lattice [9].
Rotor walks share another property with random walks: the particle is not responsible for knowing its destination (thanks to Yan Zhang of MIT for pointing this out). In conventional networking, each of the innumerable packets of information traveling through a network has some responsibility for finding its way to its destination. In a rotor-router network, however, particles are blindly shoved around but end up reaching targets in a predictable fashion. Thus rotor-routers could provide a robust mechanism for the distribution of information through large networks, especially if some regular pattern of delivery is required and the processing power at individual nodes is limited.
We proceed to our second example, which is of direct interest to the problem at hand. We show that 12 ∈ U. Consider the hitting sequence of a rotor network in the form of a complete binary tree of depth n with 2 n − 1 non-target nodes and 2 n targets, such that each rotor in the network is of type 12. This means that particles leave each node in an alternating fashion. The source lies at the root of the tree. Figure 2 shows such a tree of depth 3. Now, we ask, what is the sequence of targets hit?
Let us show by induction that the hitting sequence is some permutation of the 2 n targets. In the case n = 1, we have a single non-target node, the source, so the two targets are hit in an alternating fashion. Now, suppose the statement is true for some n ∈ N. Consider the binary tree of depth n + 1. It can be split into two parts: its first n layers, forming a smaller binary tree, and its deepest layer, consisting of the 2 n non-target nodes directly preceding the targets. Using the inductive hypothesis, the first set can be replaced by a single source meta-rotor of type 1, 2, 3, . . . , 2 n , emitting particles to a permutation of the last layer of rotors. Now the result follows immediately by induction; this meta-rotor must emit two entire periods worth of particles to the last layer before any target is hit twice, since the rotors are of type 12. It follows that all 2 n+1 targets are hit once before any one is hit twice.
From the argument above, it follows that 12 can make any rotor type of the form 1, 2, 3, . . . , 2 n for n ∈ N. In the spirit of Cauchy's proof of the AM-GM inequality, we modify the tree slightly to show that 12 can make any rotor type of the form 1, 2, . . . , m, for any m ∈ N. For each m ≥ 2, choose n such that m ≤ 2 n . Consider the binary tree network of depth n, with 2 n targets, as before. Now, remove 2 n − m targets, routing their predecessors directly back to the root. This modification essentially "hides" the extra targets the operation of the rest of the network is not affected (in the next section such a modification is called a destructive reduction). The remainder of the hitting sequence has type 1, 2, . . . , m, as desired.
Finally, to form an arbitrary rotor type a 1 , a 2 , . . . , a m of period m from 12, first construct the modified binary tree hitting m targets, as above. Then, merge together the targets such that two targets i, j ∈ [m] are combined iff a i = a j (in the next section such an operation is called a merging reduction). The hitting sequence is now the rotor type we want, so 12 ∈ U.
Henceforth, all of our attacks on the universality problem will be based on the fact that 12 is universal, since any rotor r that can model 12 is also universal.

The Reduction Theorem
The flexibility of the rotor-router model allows room for the generalization of results about two-state rotors to any number of states. In this section, we propose and prove a theorem regarding the reductions of multi-state rotors to two-state rotors.
A rotor type can often be thought of as a special case of another type with more states. The rotor type 12232, for instance, is a special case, or reduction, of the type 12434, since we may direct each edge in a 12434-type rotor numbered 4 in the same direction as the one numbered 2. This reduction is described informally as 4 → 2, and called a merging reduction. Along the same lines, 123 is also a special case of the type 12434, as each edge in a 12434 rotor numbered 4 can be turned into a self-loop, eliminating all the 4's. This reduction is denoted x(4) informally, and called a destructive reduction. In general we can always reduce a rotor by merging two of its states or deleting one altogether. The following lemma about reductions gets us close to our goal, Theorem 1.

Lemma 1.
If r ∈ BOP has more than two states, and all of its merging reductions are boppy, then there exist three states of r, which we assume to be 1, 2, 3, such that the reductions 3 → 1 and 3 → 2 of r are block-repetitive with coprime block lengths and 2 → 1 is palindromic.
Proof. Because r ∈ BOP, there exists some integer k such that r (k) and r (|r|+1−k) differ. Without loss of generality, call these two states 1 and 2, respectively. Consider another state, which we call 3, without loss of generality. By our assumptions, if we apply 3 → 1, the rotor becomes boppy. It cannot become palindromic, since r (k) and r (|r|+1−k) still differ, so it must become block-repetitive. Let its block size be a. Every block of 2's in r must then have length divisible by a. Similarly, if we reduce 3 → 2, the rotor becomes block-repetitive with some block size b, so the 1's must occur in blocks of length b. Now if a and b share any common factors d, both reductions are block-repetitive with block length d. Also, each block of 2's has length divisible by d, as does each block of 1's. Therefore, the remaining 3's must also be in blocks of length d, so that r is itself block-repetitive with block length d. A contradiction has been reached so a and b must be coprime.
Suppose these two merging reductions, 3 → 2 and 3 → 1 are both block-repetitive, and consider the reduction 2 → 1. First, suppose it too is block-repetitive, with block length c. It follows that the 3's occur in blocks of length c. Also, if a or b shares factors with c, then we have the same contradiction as before, that r itself is block-repetitive. We have proven that a, b, and c are pairwise coprime.
Choose any k not a multiple of abc. Then, r (k) and r (k+1) lie in the same uniform block for at least two of the three numbers a, b, c. It follows that r (k) = r (k+1) . We have immediately that r is block-repetitive with block length abc. Thus we have reached a contradiction and 2 → 1 must give a palindromic reduction instead, as desired.
For the rotor type 111333332222111111222222222233333111, five of its six possible reductions are boppy; two are block-repetitive and three are palindromic. Therefore, the following theorem may come as a surprise.
Theorem 1 (The Reduction Theorem). Every r ∈ BOP with more than two states has an unboppy reduction.
Proof. Suppose there exists r ∈ BOP such that all reductions of r lie in BOP.
Find some three states 1, 2, 3 satisfying the conditions of Lemma 1. Both reductions 3 → 1 and 3 → 2 of r are block-repetitive with some coprime block lengths a, b, and so every state not 1, 2, or 3 occurs in blocks of length ab. Therefore, we can discount them entirely; if we can show that the subsequence of r containing only 1, 2, or 3 has an unboppy reduction, then it is automatic that r itself has an unboppy reduction by the same merging or destructive reduction rule. Indeed, if the reduction of this subsequence is not palindromic the corresponding reduction of r cannot be palindromic. Similarly, if the reduction of this subsequence is not block-repetitive, then the corresponding reduction of r just has some blocks of length ab inserted, and is still not block-repetitive. Thus it suffices to assume that r has exactly three states 1, 2 and 3.
Let us prove that, in this case, the destructive reduction x(3) is unboppy. The resulting type is not palindromic; otherwise, r must have been palindromic, since 2 → 1 is also palindromic. It remains to show that this rotor is not block-repetitive. If it is, the block length must be a multiple of b, since all 1's occur in such blocks, and a multiple of a, since all 2's occur in such blocks. Hence, the resulting type must have block length ab. But then, the 3's removed must also have been in blocks of ab in order for the reductions 3 → 2 and 3 → 1 to have been block-repetitive. Hence r itself was block-repetitive, which is a contradiction. Thus, x(3) is unboppy. It follows that one of the reductions of r lies in BOP.
After the Reduction Theorem, it suffices to consider rotor types of only two states; if Conjecture 1 is proven for every two-state rotor, then it follows in general by the Reduction Theorem. To tackle this reduced problem, we introduce the compressor in the next section.

The Compressor
Here we introduce a rotor-router network of fundamental importance to the universality problem, the compressor. In one instance a special case of the compressor was used previously by Propp to prove the universality of 112, but no recognition of its general significance was made. The rotor-router network in Figure 3 is the compressor, a network that applies only to two-state rotors. It consists of three rotors of the same type r as well as two targets. The source rotor is labeled 1 and the targets are 4 and 5. By symmetry, there are four essentially different variations of this configuration, based on the order of the out-edges of rotors 2 and 3 (a type 12 rotor at rotor 2 could represent either 1, 4, 1, 4, . . . or 4, 1, 4, 1, . . .).
Each configuration can be viewed as a mapping from the set of rotors to itself. The four variations of the compressor will be called U U , U D, DU , and DD. In each case, the first letter represents whether rotor 2 points up to rotor 1 first or down to rotor 4, and the second letter represents whether rotor 3 points up to rotor 1 or down to 5 first. For each rotor r, we define the mappings U U, U D, DU, DD : ROT → ROT to take r to the hitting sequence of the corresponding compressor variation with three copies of r.
The compressor is a special case of the binary tree on three non-target vertices (with four targets), with two of the targets "hidden," in the language of Section 2. In the language of the previous section, U U (r), U D(r), DU (r), and DD(r) are all destructive reductions of BT (r), which will stand for the result of applying the binary tree to a rotor. Note that BT takes two-state rotors to four-state rotors, and that BT (r) can be formed from U U (r) and DD(r) by splitting these into smaller subsequences, and pasting these together; one of them will be given the labels 3, 4 instead of 1, 2. The same can be said of U D and DU . This idea is helpful in Sections 7 and 8.
To prepare for the next two results we define: Definition 3. A balanced rotor type is a two-state rotor type such that its two states occur with equal frequency. The class of all balanced rotors is denoted BAL.
The following result shows that U D maps two-state rotors to balanced rotors. Henceforth, we assume without loss of generality that the two states of any two-state rotor are 1 and 2, and that the first term in the rotor is 1.
Theorem 2. If r ∈ ROT has two states, then U D(r) ∈ BAL.
Proof. Suppose a period of r has a 1's and b 2's. When exactly |r| = a + b periods of the source rotor 1 have been fired in network U D, exactly a periods of rotor 2 and exactly b periods of rotor 3 will have fired, so the graph is back to its original state. Thus some number of full periods of the hitting sequence has been reached. Since ab of each target have been hit, U D(r) ∈ BAL.
The proof of Theorem 2 also yields an O(n 2 ) upper bound for the period length of U D(r), where n = |r|, better than the trivial O(n 3 ) bound. and |BT (r)| ≤ |r| 2 .
In general this argument extends to give O(n d ) bounds for the hitting sequence lengths of homogeneous acyclic digraph (DAG) networks with size m and longest chain of length d, a significant improvement over the exponential bounds for general rotor networks.
Theorem 3. Let a rotor network be imposed on a digraph G = (V, E) with m non-target vertices and all rotors of type r ∈ ROT. Suppose that every directed cycle in G contains the source of the network, and d is the largest number of non-target vertices in a simple directed path in G beginning at source. Then the hitting sequence of G has period length at most |r| d .
Proof. We can assume that G has no directed cycles. Otherwise, let the set of in-edges of the source v 0 ∈ V be E 0 ⊂ E. Modify G by adding one target vertex t 0 . For each (v, v 0 ) ∈ E 0 , we replace it with the edge (v, t 0 ). There are no directed cycles in the new graph G , and the period of the hitting sequence of G is the destructive reduction x(t 0 ), in the notation of the last section, of that of G . Hence it is sufficient to prove the bound for acyclic networks.
It is only necessary to show that after the particle has been fired from the source |r| d times, it has passed through each non-target vertex a multiple of |r| times. For each non- , it is easy to show that the number of times the particle passes through v is a multiple of |r| d−d (v) . The result follows immediately.
As an example of Theorem 2, consider the action of U D on the rotor type 112. We write out (with foresight) some periods of the rotor patterns: Since we are applying U D, the first term in rotor 2 is 1 ("Up") while the first term in rotor 3 is 5 ("Down"). Since the number of 2's in three periods of the source rotor 1 corresponds to the length of two periods of 2, and the number of 3's to the length of one period of 3, after everything displayed above is used up the rotor network has returned to its original position. Therefore the hitting sequence must contain exactly two 4's and two 5's.
Because of Theorem 2, it suffices to study balanced rotors. Proof. If two periods of rotor 1 have been fired, then exactly one period of rotor 2 and one period of rotor 3 will have fired, because r is balanced. The rotors have all returned to their original states. Therefore, since exactly |r| targets have been hit in this sequence, the period of the hitting sequence must divide |r|.
For instance, consider how U U (121221) is formed. We write out two periods of the source and one period of rotors 2 and 3: Since 232332 ∈ BAL, we see that when every term listed above is used up, the network returns to its original state. Hence the hitting sequence is of length dividing 6, just like the original rotor. In this particular instance the hitting sequence is 121212, or 12, of length 2, and the compressor has proven that 121221 ∈ U. This example also illustrates why every variation of the compressor preserves balance, Corollary 7.1, and hints at Theorem 14 in Section 8.
Repeated compressor applications never increase a balance rotor's period, since the compressor preserves balance. Many rotors can be "compressed" to rotors of short period, or even to 12, as above. Explicitly, the compressor algorithm runs as follows. Starting with an arbitrary two-state rotor r, apply U D to create balance. Thereafter, apply an arbitrary compressor variation to the result (in which we replace 4's by 1's and 5's by 2's) and repeat. In the vast majority of cases if r is unboppy this algorithm ends in 12, proving the universality of r. This is the first, and crudest, instance of the use of monovariants associated with the compressor. As will be seen in Sections 7 and 8, more monovariants further restrict the action of the compressor.
Finally, we sketch an algebraic way to study the compressor. For a given r ∈ BAL, write it as an infinite periodic sequence a 1 , a 2 , . . . of period 2n. Define f (m) to be the position of the m-th 1 in this sequence, and g(m) to be the position of the m-th 2. Also, define F (m) to be the number of 1's in the sequence up through a m , and G(m) the number of 2's up through a m . Let us find the position of the m-th 4 in U D(r) in terms of f , g, F , and G.
Proof. Consider the position of the m-th 4 in U D(r). It must come from directly the m-th 4 in rotor 2 of the compressor configuration. We count the number of 5's hit before this 4 to find its absolute position in U D(r). It came from the m-th 4 in rotor 2, at position g(m) in that rotor. This was hit by the particle coming from the g(m)-th 2 in the source rotor, which is at position f (g(m)), since 2's in rotor 1 correspond to 1's in r. Now, exactly G(f (g(m))) of the terms in the source up to this point are 3's, and they all went to rotor 3. Of these, exactly F (G (f (g(m)))) hit a 5 in that rotor. It follows that the m-th 4 in U D(r) occurs at position m + F (G(f (g(m)))).
Theorem 5 and its analogues for the other compressor variations give a number of results supporting our intuition. We give only one example here. Suppose U D(r) ∈ PAL for some r. Note that since the m-th and (n − m + 1)-th 4's in U D(r) must be symmetric (i.e. their positions must add to 2n + 1), it follows that F (G(f (g(m)))) + F (G(f (g(n − m + 1)))) = n.
(1) By the exact same manipulations on the 5's in U D(r), we can show that G (F (g(f (m)))) + G(F (g(f (n − m + 1)))) = n. ( These equations say that the original rotor r was "almost palindromic." For instance: Theorem 6. If r ∈ BAL, then U D(r) ∈ PAL only if r starts and ends with the same term.
Proof. With equations (1) and (2) in mind, suppose for the sake of contradiction that r starts with 1 and ends with 2 (without loss of generality). Find the smallest k such that a k = 2, so a i = 1 for all i < k. Then, letting m = 1 in (1), we see that Next, note that G(f (i)) = f (i) − i, since the number of 2's up to the i-th 1 is exactly the position of the i-th 1 minus i, the number of 1's up to that point. Thus equation (3) simplifies further to Furthermore, since f (2n) is the position of the 2n-th 1, it is the last 1 in the second period of r. Because a period of r has length exactly 2n, it follows that f (2n) − 2n = f (n), the position of the n-th 1. Also F (f (n)) = n, so now it remains to show that is impossible. Note that f (k) ≥ k trivially, and f (k) = k because a k = 2. Therefore, f (k) − k ≥ 1, from which it follows that F (f (k) − k) ≥ 1, since a 1 = 1. Thus (5) is impossible and a contradiction has been reached. The rotor type r must start and end with the same term.
Similar local results can be deduced from Theorem 5 for block-repetitive rotors. Both empirically and heuristically from the type of argument above, the compressor only immediately fails to prove universality for unboppy rotors when they are close to boppy rotors (a few terms away). We turn to the empirical data in the next section.

Computer Data and Universal Rotor Types
Of all nontrivial two-state rotors, it was previously known that the rotor types 1 k 2 (which denotes k 1's followed by a 2) were universal. By judicious application of the compressor, the following general classes have been proven universal: those of the form (11) k 21, and those of the form (12) k 21(12) l . A short proof of the universality of the second class is given in Section 8.
In addition to these classes, we have proven through C programs the universality of the vast majority of all unboppy two-state rotor types with period up through 17. The rotor-router model, and in particular our compressor algorithm, lends itself to computer simulation. Here is a brief sketch of the programs written to generate our data.
Based on an input parameter n, the length of the rotors to consider, all two-state rotors of that length are generated. Those that are trivial, such as 11111, or necessarily nonuniversal (i.e. boppy) such as 1221, are immediately discarded. For each of the remaining rotors, the program applies U D to the rotor to make it balanced, after which it repeatedly applies a pseudorandomly chosen compressor variation for up to 200 times. If 12 is reached within this subroutine, the loop terminates and the rotor is universal. Otherwise, up to 50 more such random sequences of applications of the compressor occur, restarting each time with the original rotor. If at the end of this loop the rotor still has not been proven universal, it is recorded in an output file as undecided. The program outputs at termination the total number of undecided rotors found. The running time is necessarily (at least) exponential and proved prohibitive for values of n greater than 17. In Table 1, we summarize these results. For each rotor length up through 17, the table gives the number of unboppy rotor types not proven universal by the compressor, and its fraction out of the total number of unboppy rotors of that length. In total, at most 272 are not universal out of roughly 260000. It seems plausible from this data that almost all unboppy rotor types can be proven universal using the compressor alone, in the sense that the fraction of undecided rotors approaches 0.
It should be stressed that these undecided rotors are not necessarily counterexamples to Conjecture 1; for instance, the 7 potential counterexamples of length 6 or 8 have been proven universal by first applying an auxilliary rotor-router network and then using the compressor algorithm. Although this method times out for longer rotors it shows that the occasional failure of the compressor algorithm is probably not due to the existence of a third class of nonuniversals.
From this data we conjecture that all unboppy rotors of prime length can be proven universal by the compressor. It is true for all the primes up through 17.
Variations on the program above produced further data supporting our conjectures. Every balanced, unboppy rotor with period less than 24 is universal, and at most 9 such rotors with period 24 are not. In addition, every ab-ba rotor of length 2 (mod 4) with period up through 42 is universal. Finally, we note that every rotor tested, up to length 17, has been shown universal in some class (p, b), strongly supporting Conjecture 3.

More on Balanced Rotors
We extend the theory of balanced rotors and prove some finer claims than those of Section 5, culminating in the definition of BURD rotors. In this section it is possible to view rotors almost entirely as binary strings upon which the compressor family of maps are applied. We start by refining the original notion of rotor balance.
Definition 4. An n-balanced rotor is a two-state rotor type with fundamental period divisible by n such that for each k ∈ N, the block r (k,n) has equal numbers of 1's and 2's. The class of n-balanced rotors is denoted n-BAL. If a rotor r is 2-balanced, we also call it an ab-ba rotor ; the class 2-BAL of 2-balanced rotors is also called ABBA.
Note that the compressor preserves n-balance. As an illustration, consider DD(12211122). In this case the compressor looks like: Because 12211122 ∈ 4-BAL, we can see that when 23322233 is fired in rotor 1, balanced blocks 4114 and 5115 are used up in rotors 2 and 3. The next block of length eight, which is again 23322233, corresponds to balanced blocks 4411 and 5511 in rotors 2 and 3. After each balanced block of eight is fired from the source, the corresponding two blocks of four are fired in rotors 2 and 3, producing the desired 4-balanced effect. Formally, we have: Theorem 7. For any n ∈ N, the class 2n-BAL is closed under U U, U D, DU, and DD.
Proof. For U D and DU , Theorem 8 gives a stronger result. We need only prove the result for U U and DD. Consider U U (r) for an 2n-balanced rotor r. We wish to show that for each k ∈ N, the k-th block of length 2n in U U (r) is balanced. When the block r (k,4n) is fired from the source, half of the particles enter rotor 2, and the other half enter 3. From 2 and 3, each fires according to the block r (k,2n) , so we hit the two targets n times each. Hence this block of 2n of the hitting sequence is balanced, as is every other by the same argument.
The two most important special cases are: For the following results it is natural to define a coarser type of equivalence, where only the frequencies of labels within blocks are taken into consideration.
Definition 5. Two r, r ∈ ROT are n-equivalent if there exists s ∈ ROT equivalent to r with the same states as r such that for each k ∈ N, as multisets r (k,n) = s (k,n) . We write r ≡ n r . In particular, if r ≡ 1 r , then r ≡ r . Now that we have the requisite definitions, we can state and prove Theorem 8.
Proof. We show U D(r) ≡ n r. Suppose by induction that this has been shown for the first k blocks of length n in U D(r) and r. Then, consider r (k,2n) . At the point that the source rotor first enters this block of its cycle, by the balanced property of the previous blocks the two other rotors have just used up their first k blocks of length n, respectively. Now, in the next 2n firings of the source, the next block of n of rotor 2 is used up. There are the same number of 4's in this block as there were 2's in r (k,n) . The corresponding block of rotor 3 also has the same number of 5's as there are 1's in r (k,n) , so a block of length n is completed and we are done by induction.
In particular, when Theorem 8 is applied to 2-balanced, or ab-ba rotors, it shows that all ab-ba rotors are fixed points of U D and DU . Corollary 8.1. If r ∈ ABBA, then U D(r) ≡ DU (r) ≡ r.
Theorem 8 exhibits a possible obstacle of the compressor algorithm. If a rotor r ∈ 4n-BAL but r ∈ 2n-BAL for some n, then U D and DU will never make it 2n-balanced; some blocks of length 4n become permanently skewed in one direction. For instance, U D(11121222) = 54554454, and the imbalanced number of 1's and 2's in the first block of length 4 is not resolved.
However, an almost exactly opposite result holds for U U and DD, showing that they distribute the states more evenly. Recall that a balanced run of a rotor r is a subsequence r (a+1) , r (a+2) , . . . , r (a+b) such that the same number of 1's appear as 2's. For the purposes of the next theorem, it is simpler to treat the rotor-router particle as multiple reincarnations, where it becomes a new, distinct particle whenever it returns to the source. Thus the particle that uses up the k-th term of rotor 1 in the compressor is the k-th particle. In U U (r) and DD(r) there are two runs that together correspond to the original run in r in the sense that the targets in those subsequences were hit by exactly those particles using up that run in the source.
Theorem 9. If r ∈ BAL is such that the runs r (1) , r (2) , . . . , r (2a) and r (2a+1) , . . . , r (2a+2b) are balanced, then the two runs in U U (r) and DD(r) corresponding to the (2a + 1)-th through (2a + 2b)-th particles to leave the source are both balanced and have lengths that add to 2b. This is true unless the run r (a+1) , . . . , r (a+b) is constant, in which case exactly one of the balanced runs exists and has length exactly 2b.
Proof. Consider first U U (r). The condition that r(1), r (2) , . . . , r (2a) is balanced simply tells us that the same number of terms, namely a, of rotors 2 and 3 have been fired. The second condition shows that exactly b particles among the next 2b enter rotor 2, and the rest enter rotor 3. Consider the number of 4's in rotor 2, which is equal to the number of 5's in rotor 3, coming from the run r (a+1) , . . . , r (a+b) ; whatever this number is, it is the number of 4's and 5's in the corresponding balanced run of U U , and 2b minus this number is the corresponding size of the balanced run in DD, by the same logic. One of these numbers is zero iff r (a+1) , . . . , r (a+b) is constant, so we are done.
Unless the exception occurs, we say that the run in r is split up between U U (r) and DD(r). Note that two periods of r correspond to one period of U U (r) and one of DD(r), so an individual run can be split up twice, independently.
For an example of Theorem 9, consider again the rotor 12211122, which has U U (12211122) = 54454455 and DD(12211122) = 45454554. We say that the first occurrence of the balanced run 1122 is split up between the 45 in positions three and four of U U and the corresponding 45 of DD. The second occurrence of 1122, meanwhile, is not split up because the run at half the position with half the length is the last 22 in the rotor, and is uniform. Instead, this balanced run corresponds to the 4455 that ends U U .
These ideas about balanced and uniform runs motivate two more notions.
Definition 6. Define a balanced run decomposition (BRD) of a balanced rotor r as a partition of the period of r into contiguous balanced runs. Define the balanced run type of this BRD as the infinite periodic sequence (b 1 , b 2 , . . .) such that 2b i is the length of the i-th balanced run, modulo the size of the partition. Let the balance coefficient of r, denoted b(r), be the maximal number of runs in any BRD of r, divided by |r|.
A rotor may have multiple BRD's if we choose to merge adjacent balanced runs. Thus 122112 can have BRD 12|21|12 or 12|2112 or 122112. Note that Theorem 9, when applied to all the balanced runs of a rotor, gives the inequality b(U U (r)) + b(DD(r)) ≥ 2b(r).
This can be seen from the fact that the balanced runs in two periods of r are split between U U (r) and DD(r). Equality occurs iff no balanced run is split up as in Theorem 9. Next we define the analogous decomposition of a rotor into uniform runs. Definition 7. Define an uniform run decomposition (URD) of a rotor r as a partition of the period of r into contiguous uniform runs. Define the uniform run type of this URD as the infinite periodic sequence (u 1 , u 2 , . . .) such that u i is the length of the i-th run in this URD, i taken modulo the number of runs in the URD.
A rotor can have multiple URD's if we choose to split up larger uniform runs. Thus 122112 can have URD 1|22|11|2 or 1|2|2|11|2 or 1|2|2|1|1|2. Based on these two definitions and inequality (6), we can conclude the following: Theorem 10. If r ∈ BAL has a BRD of type (b 1 , b 2 , . . .), then one of the following must hold: i. One of b(U U (r)) and b(DD(r)) is strictly larger than b(r).
ii. There is also a URD of r of type (b 1 , b 2 , . . .).
Proof. The theorem follows from the fact that either a split of the type given in Theorem 9 exists for U U (r) or DD(r), in which case b(U U (r)) + b(DD(r)) > 2b(r), since an extra balanced run was created, or else every balanced run of length 2b i corresponds to a uniform run of length b i at the position half its own.
We define a BURD rotor as a rotor type satisfying condition ii of Theorem 10. That is, it has a BRD and a URD of the same type. From any balanced rotor, repeated applications of the compressor must eventually lead to a BURD rotor; otherwise we could increase the balance coefficient arbitrarily often using U U or DD, and it can only take on a finite number of rational values. Naturally, the class of BURD rotors is denoted BURD. One essential property of BURD rotors is the following generalization of Corollary 8.1: Theorem 11. If r ∈ BURD, then U D(r) ≡ DU (r) ≡ r.
Proof. Assume we are looking at U D(r), without loss of generality. Let a uniform run of the URD of r that has a BRD counterpart be r (a+1) , r (a+2) , . . . , r (a+b) . The corresponding balanced run in the BRD is r (2a+1) , r (2a+2) , . . . , r (2a+2b) . Thus, when the particles numbered (2a + 1) through (2a + 2b) are emitted by the source rotor, exactly half go to rotor 2 of the compressor, hitting the uniform run corresponding to r (a+1) , . . . , r (a+b) there, and the other half go to the same uniform run in rotor 3. Only one of these runs is routed down, depending on r (a+1) , so we know that this uniform run is copied faithfully onto U D(r). Each of the uniform runs in the URD is copied in the same way into U D(r). It is now evident that U D(r) ≡ r, and the proof of DU (r) ≡ r is exactly analogous.
Note that the fixed cycles of the compressor are the only rotors necessary to consider to prove Conjecture 3. A fixed cycle of the compressor is defined formally as a set C of rotors, closed under all compressor operations, such that any element can be reached from any other by way of some sequence of compressor operations. From the preceding theorems, a standard extremal argument shows: Theorem 12. For every fixed cycle C of the compressor C ⊂ BURD.
Proof. Suppose for the sake of contradiction that some such cycle C exists, containing a rotor r ∈ BURD. We can choose r to have maximal b(r) of all rotors in C \ BURD. Also, C∩BURD is nonempty, so we can choose r ∈ C∩BURD with maximal balance coefficient in this set as well. Clearly, b(r ) > b(r) since there is a sequence of U U 's and DD's strictly increasing b(r) until it becomes BURD, by Theorem 10. But then, if r can reach r, it must also be able to reach some rotor r with b(r ) > b(r ) by inequality 6, a contradiction. Thus C ⊂ BURD always.
The obvious class of BURD rotors is ABBA, and the generalization thereof to blockrepetitive rotors (i.e. aabb-bbaa rotors and the like). However, not all BURD rotors are of this form. For instance, the rotor type 1122222111 generates a nontrivial fixed cycle of size 2 in the action of the compressor. However, when the BURD rotor also happens to be ab-ba, we have some further results.

On ab-ba rotors
Recall that a balanced rotor r is called ab-ba if it is 2-balanced, that is, if r 2k+1 and r 2k+2 are different for all k ∈ N. Intuitively, ab-ba rotors are just one step away from the universal rotor 12. This is because the compressor keeps ab-ba rotors ab-ba, and they are all fixed points of U D and DU . Also, they can't be block-repetitive. Hence, to be boppy, they need to be palindromic and thus have length 0 (mod 4) (consider the middle two terms). If our conjectures hold, then all ab-ba rotors of length 2 (mod 4) should be universal. Indeed, we verified using computer programs that all ab-ba rotors of length 2 (mod 4) up to length 42 are universal by the compressor algorithm. Now we discuss some extra tools. This function m can be made into a monovariant for ab-ba rotors under the compressor, as in the following result.
Proof. We only need the number of 21's in the first |r| terms of U U (r) and the number of 21's in the first |r| terms of DD(r) to sum to the number of 21's in the first 2|r| terms of r. Each 21 in the first two periods of r corresponds to one 21 in the first |r| terms of either U U (r) or DD(r). For instance, suppose that r (k) = 1, r (2k−1) = 2, and r (2k) = 1. Then, in configuration U U , (rotor 2) (k) and (rotor 3) (k) both go back to the source, while in DD(r), they route to targets 4 and 5. In U U (r) this block 21 will not appear in the hitting sequence, while in DD(r) it contributes a 21. Each block 21 in the 2|r| terms of r contributes a 21 to exactly one of U U (r) and DD(r).
In particular, this shows that there is some sequence of U U 's and DD's that never increase m(r). Further, the theorem shows that if m(r) is changed at all by one of U U and DD, then it must be strictly decreased by one of them. We end with two specific results based on this idea.
Theorem 14. Every r ∈ ABBA consisting of more than one block of 12 and exactly one block of 21 is universal.
Proof. Let f (r) denote the position of the 21 block in such an r ∈ ABBA. If either of m(U U (r)), m(DD(r)) is not equal to m(r), then one of them must be strictly less than m(r) and be zero, by Theorem 13. Otherwise, both U U (r) and DD(r) also have exactly one 21 block.
If |r| ≡ 0 (mod 4), then one of U U (r) and DD(r) is 12 unless f (r) = 1 or f (r) = |r| 2 . If f (r) = 1, then one of f (U U (r)), f (DD(r)) is |r| 4 + 1, and another application of U U or DD suffices. If f (r) = |r| 2 , then one of f (U U (r)), f (DD(r)) is |r| 4 , and again r is universal after another application of U U or DD.
If |r| ≡ 2 (mod 4), then one of U U (r) and DD(r) is 12 if f (r) = 1 or f (r) = |r| 2 . Otherwise, it is easy to prove that one of f (U U (r)), f (DD(r)) is f (r) 2 , so some combination of U U (r), DD(r) must move the 21 block to position 1.
The proof above shows that the ab-ba problem can be reinterpreted as follows: Given a periodic sequence A = {a i } ∞ i=0 of 0's and 1's, where 0 represents 12 and 1 represents 21, we are allowed to perform the following two transforms on the sequence. The first takes A to U U (A) = {b i } ∞ i=0 , and the second to DD(A) = {c i } ∞ i=0 , where b i = a 2i−a i and c i = a 2i−1+a i . The problem is to determine when these two transforms, applied repeatedly, can take a sequence to a constant one. In this spirit, the next theorem is immediate.
ii. For any two 21 blocks of r that are the a-th and b-th blocks of r, a and b do not satisfy a 2 ≡ b (mod |r|). iii. For every pair of 21 blocks of r, their positions as blocks have the same parity. then r ∈ U.
Proof. It is clear from the proof of Theorem 14 that one of U U (r), DD(r) is 12, since each 21 block acts independently of the others.
If we are patient we can extend these two results somewhat, but it does not seem fruitful in general to do so.

Directions for Future Research
Here we collect together some possible directions of future work on the universality problem and the related string manipulations. The algebraic perspective in Section 5 may have further implications for the compressor algorithm. In Section 6 we mentioned several conjectures inspired by empirical data. It was conjectured that the compressor directly proves the universality of all non-palindromic rotors of prime length and all ab-ba rotors of length 2 (mod 4); these are the focus of our current work. Another direction to take is the investigation of the universality of BURD rotors, which are central to the compressor algorithm. The classification of BURD strings is interesting in its own right, especially given that nontrivial examples like 1122222111 exist. Also, the fascinating self-reference of the BURD condition merits more attention.
Another problem proposed by Propp asks for the universality of rotors when cyclic shifts of the same rotor are considered equivalent. Our results point to the conjecture that all rotors are universal under this alternative definition. The universality question can also be generalized in another direction, that of determining which finite sets of rotors are universal when taken together. Resolution of the universality problem would almost completely solve this as well. We may try to quantify our results on universality; instead of asking whether or not rotor r makes rotor r , we can ask how efficiently r can make r . Such a question provides another notion of the "complexity" or "information value" of binary strings.