arXiv:1801.01965v1 [] 6 Jan 2018

RESTRICTIONS ON POTENTIAL AUTOMATIC STRUCTURES ON
THOMPSON’S GROUP F

BY
JEREMY DAVID HAUZE
BA, King’s College, 2009
MA, Binghamton University, 2011

DISSERTATION
Submitted in partial fulfillment of the requirements for
the degree of Doctor of Philosophy in Mathematical Sciences
in the Graduate School of
Binghamton University
State University of New York
2017

©Copyright by Jeremy David Hauze 2017
All Rights Reserved

Accepted in partial fulfillment of the requirements for
the degree of Doctor of Philosophy in Mathematical Sciences
in the Graduate School of
Binghamton University
State University of New York
2017
December 1, 2017
Matthew Brin, Chair
Department of Mathematical Sciences, Binghamton University
Ross Geoghegan, Member
Department of Mathematical Sciences, Binghamton University
Fernando Guzman, Member
Department of Mathematical Sciences, Binghamton University
Leslie Lander, Outside Examiner
Department of Computer Sciences, Binghamton University
iii

Abstract
We show that a large class of languages in the standard finite generating set
−1
X = {x0 , x1 , x−1
0 , x1 } cannot be part of an automatic structure for Thompson’s

Group F . These languages are ones that accept at least one representative of
each element of F of word length that is within a fixed constant of a geodesic
representative of the element. To accomplish this, we look at a specific element
of F and trace two different paths through the Cayley graph to that element. We
show that staying within the length restrictions along these two paths would force
that element to have contradictory properties.

iv

Acknowledgments
My deepest appreciation goes to my adviser Matt Brin for his guidance, support, and above all else, patience. Without his aid and encouragement, I would
not be in the position I am today.
I would like to thank the faculty and staff of the Binghamton University
Department of Mathematical Sciences. Special thanks go to the members of my
committee: Ross Geoghegan, Fernando Guzman, and Leslie Lander.
I would also like to thank my wife, Kylynn Hauze. She has been a constant
source of understanding and support throughout my work.
Finally, I would like to thank my parents, David and Mary Hauze, for their encouragement; my professors at Kings College, especially Joseph Evan, Ryo Ohashi,
and David Kyle Johnson, for putting me on this path; and my family and friends
who each played their part in bringing me to this day.

v

Table of Contents
List of Figures . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

vii

Chapter 1: Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . .

1

Chapter 2: Automatic Groups . . . . . . . . . . . . . . . . . . . . . . .

4

2.1 Geometric Characterization of Automatic Structures . . . . . . .

4

2.2 Properties of Automaticity . . . . . . . . . . . . . . . . . . . . .

5

Chapter 3: Thompson’s Group F . . . . . . . . . . . . . . . . . . . . . .

7

3.1 Defining F . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

7

3.2 Tree Pair Diagrams . . . . . . . . . . . . . . . . . . . . . . . . .

8

3.3 The Action of F on T and the Infix Ordering . . . . . . . . . . .

11

3.4 Other Notes on F . . . . . . . . . . . . . . . . . . . . . . . . . .

13

Chapter 4: Minimal Length Plus a Constant . . . . . . . . . . . . . . .

15

4.1 Conventions

. . . . . . . . . . . . . . . . . . . . . . . . . . . . .

16

4.2 Proving Theorem 1.1 . . . . . . . . . . . . . . . . . . . . . . . . .

17

4.3 The Path for fk : . . . . . . . . . . . . . . . . . . . . . . . . . . .

18

4.4 The Claim for fk : . . . . . . . . . . . . . . . . . . . . . . . . . .

46

4.5 The Path for gk : . . . . . . . . . . . . . . . . . . . . . . . . . . .

47

4.6 The Claim for gk : . . . . . . . . . . . . . . . . . . . . . . . . . .

79

4.7 Conclusion of Theorem 1.1 . . . . . . . . . . . . . . . . . . . . .

80

Bibliography . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

81

vi

List of Figures
Figure 1

x0 and x1 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

8

Figure 2

T with Standard Dyadic Intervals Labels . . . . . . . . . . . . .

9

Figure 3

Reduced Tree Pair for x0 with Dyadic Interval Labels . . . . . .

10

Figure 4

Reduced Tree Pair for x1 with Dyadic Interval Labels . . . . . .

10

Figure 5

Tree Pair for fk . . . . . . . . . . . . . . . . . . . . . . . . . . .

15

vii

Chapter 1: Introduction
Groups that admit an automatic structure enjoy a number of beneficial properties. The machines in an automatic structure provide a way to algorithmically
understand the algebra and geometry of their related group. Thompson’s group F
is a particularly interesting group of piecewise-linear homeomorphisms of the unit
interval. Guba and Sapir posed the question of whether F is automatic. While
we do not answer their question, we show a restriction on any potential automatic
structure that could F could possess.
An automatic structure on a group G consists of language and a finite set of
finite state automata or FSAs. A language is a subset of all possible finite words
over an alphabet. For an automatic structure on G, the alphabet must be a finite,
symmetric (closed under inverse) generating set S for G. An FSA can be thought of
as a computer with finite memory. See Chapter 2 for further details on FSAs. The
language of an automatic structure on a group G must be such that each element
of G is represented by at least one word in the language and the associated FSAs
must (a) recognize which words are in the language and (b) tell when two words
u and v in the language satisfy u = vs in G for some s ∈ S. These machines are
referred to as the word acceptor and multiplier automata respectively. For a word
w, we will use |w| to refer to the word length of w. Given an element g in group
G with generating set S, |g|S is the length of a geodesic representative for g in S.
When there is no confusion on the generating set, we simply write |g|.
Our main result, Theorem 1.1 below, shows that a large class of languages
cannot be part of an automatic structure for Thompson’s group F .
Unsurprisingly, the FSAs in an automatic structure are valuable tools for understanding the associated group. Primarily, they provide efficient algorithms for
solving many problems associated with their group, including efficiently building the Cayley graph. The word acceptor allows for efficient computation of the

1

growth function of a group [EFZ]. If the word acceptor accepts unique geodesics,
it allows one to quickly enumerate unique representatives of the group. The multiplier automata can be used to reduce arbitrary words, providing an efficient
solution to the word problem of the group.
Demonstrating that a group is automatic involves picking a language and
building the necessary FSAs. There are computer techniques that can potentially
algorithmically demonstrate the structure of the necessary machines, if they existed. The alternatives usually involve a good deal of geometry with the group or
class of groups involved. Early sources, including [ECHLPT], showed that finite
groups, finitely generated free groups, finitely generated abelian groups, hyperbolic groups, and Braid groups are all automatic. Euclidean groups, Artin groups
of finite type, and many Coxeter groups have also been shown to be automatic.
Additionally, the class of automatic groups is closed under direct products, free
products, and free products with amalgamation over a finite subgroup, producing
many more examples of automatic groups.
Proving that a group is not automatic is generally a difficult task. This involves showing that it is impossible for any language and set of FSAs to meet the
requirements of an automatic structure. The general techniques to do so center
around known properties of automatic groups, namely, all automatic groups must
be finitely presented and must satisfy a quadratic isoperimetric function. While
an automatic structure for F is not readily apparent, it does not violate any of the
known properties of automatic groups. Some examples of groups known to not be
automatic include infinite torsion groups, nilpotent groups, and Baumslag-Solitar
groups.
A reasonable starting point in the search for an automatic structure on F is
with geodesic representatives. The study of automatic groups began when Cannon
essentially demonstrated in [Cannon] that hyperbolic groups must be automatic.
For any hyperbolic group, there is an automatic structure whose language consists of all geodesic representatives. Groups that possess this property are called
strongly geodesically automatic. It has since been demonstrated in Theorem 2 of
2

[Papa] that the class of strongly geodesically automatic groups are exactly the
hyperbolic groups. Because F is not hyperbolic, it follows from [Papa] that F is
not strongly geodesically automatic.
There is also the more general concept of weakly geodesically automatic groups.
These are precisely those automatic groups whose language consists of at least one
geodesic representative of each element. There are numerous advantages to a group
that is weakly geodesically automatic.
Cleary and Taback [ClTa] proved that F is not almost convex. Chapter 6 of
[Belk] independently demonstrates this result and goes on to show that this means
F cannot be weakly geodesically automatic. With this in mind, we give our main
result.
Theorem 1.1.
−1
Let L be a language over the alphabet X = {x0 , x1 , x−1
0 , x1 } and assume there is

a non-negative integer c so that for every element g ∈ F there is a single word
w ∈ L such that w represents g and |w| ≤ |g|X + c. Then L cannot be a subset of
the language associated with an automatic structure for F .
In the case that c = 0, we are showing that the language on an automatic
structure for F cannot contain a geodesic representative for each element. This
recovers Belk’s result within our own.

3

Chapter 2: Automatic Groups
In this chapter, we note several key results relevant to our discussion on potential automatic structures for F . These results are given without proof. For these
details, see [ECHLPT] for a full treatment on finite state automata and their use
in understanding the structure of groups.

2.1 Geometric Characterization of Automatic Structures.
We have already noted that an automatic structure on a group G consists
of a language and a finite set of FSAs including a word acceptor and multiplier
automata. We will not use this approach to automaticity or define an FSA. We
point interested readers to [ECHLPT] for these details. Automaticity has a second,
geometric characterization which is more useful for our purposes.
Let G be a group and S ⊆ G which does not contain the identity element.
The Cayley graph associated with G and S, ΓS (G), is the directed graph with
one vertex associated with each group element and directed edges (g, h) whenever
gh−1 ∈ S. When S is a symmetric generating set for G, the edges can be identified
with exactly the generators in S. The distance between two elements of g1 , g2 ∈ G
in ΓS (G) is the minimum number of edges in a path from g1 and g2 in the Cayley
graph, denoted dΓS (G) (g1 , g2 ).
We will let (G, L(X)) stand for an automatic structure on group G with language L over symmetric generating set X. The words in L(X) are representative
choices for elements of G. It is natural to think of these words as paths in ΓX (G)
from the identity vertex to the element they represent. Our second characterization focuses on these paths.
Let w be a word in the symmetric generating set X of group G. We define |w|
as the word length of w. We define w(t) as the prefix of w of length t if t < |w| or
w if t ≥ |w|. Word w is associated with a unique path through ΓX (G) given by
the mapping w:[0,
b
∞) → G where w(t)
b is the element of G that w(t) represents.
4

By convention, we use w to refer to the element represented by w itself. Note that
w(t)
b = w(t).
Definition 2.2. Let w and v be words in symmetric generating set X of group G.
We say that w and v satisfy the M-fellow traveler property if dΓX (G) (w(t),
b
v(t)) ≤
b

M for all t ≥ 0.

The fellow traveler property can be used to build a statement equivalent to
the existence of an automatic structure for a group. This result, given below, is
Theorem 2.3.5 of [ECHLPT].
Theorem 2.3. A group G has an automatic structure if and only if both of the
following hold:
(1) G has a word acceptor W under finite symmetric generating set X,
(2) There is a constant M such that for every pair w, v ∈ L(X), the language
of words accepted by W with respect to X, with w, v distance zero or one
apart in the Cayley graph, w and v satisfy the M-fellow traveler property.

2.2 Properties of Automaticity.
In this section, we note important results relating to the automaticity of a
group. We begin with Theorem 2.4.1 of [ECHLPT] that says automaticity is an
algebraic property of the group itself, rather than a geometric property derived
from the choice of a particular generating set.
Theorem 2.4. Let (G, L(A1 )) be an automatic structure for a group G. If A2 is
any other finite symmetric generating set for G, then there is a language L(A2 )
such that there is an automatic structure (G, L(A2 )) for G as well.
The language for an automatic structure has the uniqueness property if it has
exactly one representative word for each element of the associated group. Not
every automatic structure has a language with the uniqueness property. However,
every group that admits an automatic structure also admits an automatic structure
whose language has the uniqueness property. To describe this, let A be a totally
5

ordered alphabet. We use this to define an ordering on the all possible words using
A.
Definition 2.5. Given two words in A of the same length, a = a1 a2 ...ak and
b = b1 b2 ...bk , we say a < b lexicographically if ai < bi in A and aj = bj for all j < i.
Definition 2.6. The ShortLex order is a total order on the set of all words in the
alphabet A where for a, b ∈ A, a < b if and only if |a| < |b| or |a| = |b| and a < b
lexicographically.
Given language L(A), we will say that a word w ∈ L(A) is ShortLex minimal in
L if it is the minimum in the ShortLex ordering of all possible words representing
w in L(A). Theorem 2.5.1 of [ECHLPT] uses this ordering to create a special
automatic structure for an automatic group G.
Theorem 2.7. Let G be an automatic group with an automatic structure (G, L(A)).
For each g ∈ G, let lg ∈ L(A) be the ShortLex minimal word of all representative
words for g in L(A). Define L′ (A) ⊆ L to be {lg | g ∈ G}. Then, (G, L′ (A)) is
also an automatic structure for G, and L′ (A) contains exactly one representative
word for each element of G.

6

Chapter 3: Thompson’s Group F
Thompson’s group F is a particularly interesting group of piecewise-linear
homeomorphisms of the unit interval. It was first discovered by Richard J. Thompson in 1965 through his study of logic. F has many different manifestations and
has been studied extensively in many areas of mathematics.
We begin by defining F analytically and defining the standard finite presentation for F . Then, we briefly introduce the concept of tree pair diagrams. Of
particular interest is how these two methods of defining F allow us to understand
the action of F on the vertices of the infinite binary tree and the action of individual generators of F . For further detail, [CFP] provides an excellent introduction
to F and related groups defined by Thompson.

3.1 Defining F .
Definition 3.8. F is the group of all piecewise-linear homeomorphisms of [0, 1]
to itself, differentiable except at a finite number of dyadic rationals (numbers of
the form

a
2b

where a is an integer and b is a natural number), and the derivatives

on all intervals of differentiability are integral powers of 2.
We will look at two specific elements of F , denoted x0 and x1 . Their graphs
are in Figure 1.



2x




x0 (x) = x +





 x+1
2

1
4

0≤x≤

1
4

1
4

≤x≤

1
2

1
2

≤x≤1

x1 (x) =




x







2x −



x+






 x+1
2

1
8

1
2

0≤x≤

1
2

1
2

≤x≤

5
8

5
8

≤x≤

3
4

3
4

≤x≤1

] where a
A standard dyadic interval in [0, 1] is an interval of the form [ 2an , a+1
2n
and n are non-negative integers with a ≤ 2n − 1. A standard dyadic partition of
7

1
3
4

1
2

0

1

♦♦
♦♦♦
♦
♦
♦♦
♦♦♦
♦
⑧
⑧⑧
⑧⑧
⑧
⑧⑧
✎✎⑧
✎✎
✎✎✎
✎✎
✎✎✎
✎
0

1
4

1
2

7
8
3
4

1
2

0

1

♦♦♦
♦♦♦
♦
⑧⑧
⑧⑧
⑧
✎✎
✎✎✎
✎✎
⑧⑧
⑧
⑧
⑧⑧
⑧
⑧⑧
⑧⑧
⑧
⑧
⑧⑧
⑧⑧
0

1
2

5
8

3
4

1

Figure 1. x0 and x1
[0, 1] is a partition 0 = a0 ≤ a1 ≤ ... ≤ an = 1 where each sub-interval [ai , ai+1 ]
is a standard dyadic interval. We use standard dyadic partitions as a way to
understand elements of F . The following result is Lemma 2.2 of [CFP] which
defines the direct connection between F and these partitions.
Lemma 3.9. Let f ∈ F . Then there is a standard dyadic partition 0 = a0 ≤
a1 ≤ ... ≤ an = 1 such that f is linear on each interval of the partition and
0 = f (a0 ) ≤ f (a1 ) ≤ ... ≤ f (an ) = 1 is standard dyadic partition.
Finally, before moving on, we note that our composition for elements of F
is done left-to-right. Additionally, we will note that the special elements x0 and
x1 given above, along with their inverses, form the standard finite generating set
for F . In what follows, if we discuss a finite generating set for F , we will be
−1
specifically referring to X = {x0 , x1 , x−1
0 , x1 }.

3.2 Tree Pair Diagrams.
Definition 3.10. An ordered, rooted binary tree is a tree that:
(1) Has a root vertex,
(2) If it has more vertices than the root, then the root has valence 2,
(3) If v is a vertex with valence greater than 1, then there are exactly two
edges, ev,L and ev,R , which contain v and are not contained in the geodesic
path from the root to v. We refer to ev,L as the left edge of v and ev,R as
the right edge of v. These edges terminate in vertices, the left child of v
and the right child of v respectively.
8

The single vertex of valence 0 or 2 is the root of the tree. Any vertex of valence
1 is a leaf of the tree. If an ordered, rooted binary tree has at least two vertices
and no vertices of valence 1, we will refer to it as the infinite binary tree T . If an
ordered, rooted binary tree has a finite number of vertices, call it a finite binary
tree.
Given two vertices v1 and v2 on an ordered, rooted binary tree, we will use d(v1 , v2 )
to denote the number of edges on a geodesic path between these vertices.
We define a way to label the vertices of T , or a finite binary tree, using
standard dyadic intervals in [0, 1]. The root vertex is labeled [0, 1]. The children
of each vertex divide the label interval of their parent vertex in half. The left
child is the left half of its parent interval while the right child is the right half of
its parent interval. See Figure 2 for a labeling of T with these standard dyadic
intervals. We will assume that T is always given with this labeling.
Definition 3.11. Vertices with labels of the form [0, k] will be said to be on the
left spine, L, of the tree. Vertices with labels of the form [j, 1], where j is not 0
will be said to be on the right spine, R, of the tree.
A vertex v in T is called an exterior vertex if it is in L ∪ R. Any vertex that is
not exterior is called an interior node. The collection of exterior vertices L ∪ R is
called the exterior set. The collection of interior vertices is called the interior set.
Note that it is a deliberate choice put the root in L and not in R. This will
become useful when we discuss the generators of F , specifically x1 and x−1
1 .
[0,1]

♦♦❖❖❖❖❖
♦♦♦
❖❖❖
♦
♦
♦
❖❖❖
♦
♦
❖❖❏[ 1 ,1]
[0, 12 ]t✴♦♦♦
❏2
tt ✴✴✴
✎✎ ❏❏❏❏
t
✎
t
❏❏
t
✴✴
✎
❏❏ 3
tt
✎✎[ 1 , 3 ]
❏❄[ ,1]
tt
[ 41 , 12 ] ✴✴
[0, 41 ] t
✎
✴
✴
2
4
❄4
⑧ ✴✴
✎✎ ✴✴
✎✎ ✴✴
⑧
✎✎ ❄❄❄
⑧
✴
✴
✴
✎
✎
✎
⑧
❄❄
⑧
✴✴
✎✎ ✴✴✴
✎✎ ✴✴✴
✎✎
❄❄
⑧⑧
✴
✎✎
✎✎
⑧⑧
✎✎

Figure 2. T with Standard Dyadic Intervals Labels
9

Consider a finite binary tree labeled as a subtree of T . The leaves of such
a tree form a standard dyadic partition of [0, 1]. In fact, any standard dyadic
partition of [0, 1] can be given as the leaves of a unique finite binary tree.
We will use tree pair diagrams to understand and work with F from a geometric perspective. A tree pair diagram consists of an ordered pair of rooted finite
binary trees D and R with the same number of leaves. These are usually given as
(D, R) where D is called the domain tree and R is called the range tree. When
both trees are labeled using standard dyadic intervals, the leaves of the trees give
standard dyadic partitions that define an element of F . The partition given by D
is the domain partition of the element and the partitions given by R is the range
partition of the element as we saw in Lemma 3.9. There are multiple tree pair
diagrams that can be obtained that represent the same element of F . Additionally, the tree pair diagram for the inverse of an element of F can be obtained by
interchanging the domain and range trees.
We will take note of tree pair diagrams for x0 and x1 . First, x0 sends the
dyadic partition 0 ≤

1
4

≤

1
2

≤ 1 to the partition 0 ≤

1
2

≤

3
4

≤ 1. This corresponds

with the tree pair diagram shown in Figure 3.
[0,1]
❄
⑧⑧ ❄❄ [ 1 ,1]
❄
⑧
❄
⑧
⑧⑧ ❄ 2

[0, 21 ]

[0, 21 ]

[0, 41 ] [ 41 , 21 ]

[0,1]
❄❄❄
❄❄[ 1 ,1]
⑧⑧⑧ ⑧
⑧⑧ ❄2

[ 21 , 34 ] [ 34 ,1]

Figure 3. Reduced Tree Pair for x0 with Dyadic Interval Labels

Next, x1 sends the dyadic partition 0 ≤
0≤

1
2

≤

3
4

≤

7
8

1
2

≤

5
8

≤

3
4

≤ 1 to the partition

≤ 1. This corresponds with the tree pair diagram shown in Figure

4.
[0,1]

[0,1]

❄
⑧⑧ ❄❄ 1
⑧⑧ ❄
❄
⑧⑧ ❄❄[ 2 ,1]3
⑧⑧ ❄
❄
⑧⑧ ❄❄[ 4 ,1]
⑧⑧ ❄ [ 7 ,1]

❄
⑧⑧ ❄❄ 1
⑧⑧ ❄
⑧❄❄[ ,1]
⑧⑧ ❄❄2 [ 3 ,1]
⑧❄
❄
⑧
4
⑧ ❄
⑧⑧ ❄ [ 5 , 3 ]

[0, 21 ]
[ 21 , 43 ]
1 5
[2,8]

[0, 21 ]
[ 21 , 34 ]
[ 43 , 87 ]

8 4

8

Figure 4. Reduced Tree Pair for x1 with Dyadic Interval Labels

10

3.3 The Action of F on T and the Infix Ordering.
We begin by observing that each dyadic rational in (0, 1) is the midpoint of
exactly one standard dyadic interval in [0, 1]. Each dyadic number in (0, 1) can
be written in the form [ 2n+1
] where n and k are positive integers. It will be the
2k
n
midpoint of standard dyadic interval [ 2k−1
, 2n+1
k−1 ] and no other standard dyadic

interval. Given any vertex v ∈ T , this gives a secondary label r(v) where r(v) is
the midpoint of the interval label for v. This labeling r is a bijection between the
vertices of T and the dyadics in (0, 1).
The vertices of an ordered rooted binary tree, including T , have a natural
ordering, the infix order. It is a left to right ordering defined as follows. If the
tree has a single vertex, the ordering is trivial. Otherwise, given any vertex v with
children vL and vR , vL and its descendants are to the left of v in the infix ordering,
while vR and its descendants are to the right of v in the infix ordering.
Observe that a vertex v ∈ T , labeled with interval label I and dyadic label
r(v), will have left and right descendants. All left descendants of v have interval
labels which are subintervals of the left half of I. Thus, their dyadic labels, which
are the center of these subintervals, are less than r(v). All right descendants of V
have interval labels which are subintervals of the right half of I, so their dyadic
labels are greater then r(v). Therefore, r carries the infix ordering of vertices in
T to the usual ordering of the dyadics in (0, 1).
There is a standard action for F on the vertices of T , which we will note is
a right action. Let f ∈ F and note that f has a tree pair diagram (D, R). The
action of f maps the leaves of the domain tree to the leaves of the range tree in
left-to-right order, viewed as a subtree of T . This corresponds with the fact that f
carries the interval labels of the domain tree’s leaves in order to the interval labels
of the range tree’s leaves linearly. If f carries interval I to interval J affinely, it
carries the left half of I to the left half of J affinely and similarly for the right
halves. Thus if the action of f maps a vertex v to v ′ , we define the action of f to
map the left child of v to the left child of v ′ and the right child of v to the right
child of v ′ , consistent with the action on the intervals. This inductively defines the
11

action on all the descendants of the leaves of the domain tree. There are finitely
many vertices above the leaves where we must still define the action.
Notice that the above means that if f takes a leaf v to leaf v ′ , the full subtree
of T rooted at v will be rigidly taken to the subtree rooted at v ′ . Also, whenever
f takes an interval I to interval J, it certainly takes the midpoint of I to the
midpoint of J. Thus, the action of f on the vertices defined so far maps dyadic
labels to dyadic labels exactly as the element f does as a homeomorphism of
[0, 1].
This allows us to define the action of f on the finitely remaining vertices of T .
For each vertex v above the leaves of the domain tree, define f (v) to be the unique
vertex so that r(f (v)) = f (r(v)). This fully defines the action of an element f of
F on the vertices of T .
The action of f on the vertices of T as defined above fully corresponds to
the mapping of f as a homeomorphism on the dyadic labeling of these vertices.
Because all elements of F are order-preserving on dyadics as homeomorphisms of
[0, 1] and r is order-preserving for the infix order, the action of F preserves the
infix ordering of the vertices of T .
Before moving on, we will look at the finite generating set for F and consider
the action of the generators on T . We begin with x0 . Generator x0 preserves
the exterior and interior sets, simply mapping vertices to new positions in their
respective sets. Vertices in R are mapped to R, one position further from the root.
The root vertex is mapped to [ 21 , 1]. The remaining vertices in L are mapped to
L, one position closer to the root. All of the interior vertices are carried along as
each interior vertex is the descendant of a unique vertex on the spine, except for
the descendants of [ 14 , 21 ]. These vertices are mapped to the descendants of [ 12 , 43 ].
In general, this can be thought of as a clockwise rotation of the vertices of T by
a single position.

12

We can examine the tree pair diagram for x−1
0 by interchanging the domain
and range trees in the tree pair diagram for x0 . This gives a general counterclockwise rotation of T by a single position. As with x0 , x−1
0 does not change the
interior and exterior sets.
Likewise, we can see the action of x1 on T . Generator x1 preserves the vertices
of L and their descendants entirely, mapping them to their original positions. On
the subtree of T rooted at [ 12 , 1], x1 acts exactly as x0 does on the full tree. Define
the vertex [ 12 , 1] as the pivot vertex. Notice that exactly one vertex is carried from
the interior to the exterior; namely [ 21 , 43 ] is mapped to the pivot. However, x1
does not move any vertices between the left and right spines of the tree.
Generator x−1
1 , similarly obtained by interchanging the domain and range
trees of x1 , gives a counter-clockwise rotation about the pivot. It takes a single
exterior vertex and makes it interior and does not move any vertices between the
two spines of the tree.
This gives us a solid understanding of the standard finite generating set for
F . Of particular note, we can only change the interior/exterior sets by using an
x−1
1 or x1 rotation. The only way to move vertices between the left and right sides
of the tree is by using an x0 or x−1
0 rotation. Further, any use of a generator may
only change the interior and exterior sets by at most one vertex.

3.4 Other Notes on F .
For some time, geodesic elements of F posed a problem. However, in his thesis,
Blake Fordham laid out a method to use reduced tree pair diagrams to calculate
−1
minimal lengths of representative words in the generating set {x0 , x1 , x−1
0 , x1 }.

Since then, several similar techniques have been developed to calculate minimal
lengths, but Fordham’s method was highly innovative at the time. It involves
labeling carets in the domain and range trees according to the infix ordering and
classifying them into one of seven types. Weights are assigned to vertex pairs,
determined by the infix ordering, and summing these weights gives us word lengths.
13

We will use Fordham’s method and direct interested readers to [Ford] for complete
details.
Any word in the standard finite generating set for F , read left to right, can
be thought of as a sequence of instructions for moving the vertices of T . This
will allow vertices that are initially quite far from positions [ 12 , 1] and [ 12 , 43 ] to be
mapped to these positions and then mapped between the interior and exterior sets.
Recall from our discussion of automaticity that we use w to refer to the element
represented by a word w.
Definition 3.12. Let w be a word in X and let v be a vertex in T . We say that
v is made interior at time t in w if w(t)(v) = [ 21 , 43 ], a vertex in the interior set,
but w(t − 1)(v) = [ 12 , 1], a vertex in the exterior set. Similarly, we say that v is
made exterior at time t in w if w(t)(v) = [ 12 , 1] but w(t − 1)(v) = [ 12 , 43 ].
In general, we can say that vertex v is interior in w if w(v) is in the interior set.
Alternatively, v is exterior in w if w(v) is in the exterior set.
Note, a vertex may be made interior or exterior multiple times in a given word.
Further, a vertex that is made interior/exterior during the course of a word need
not be interior/exterior in the completed word itself.

14

Chapter 4: Minimal Length Plus a Constant
Consider the family of elements of F , {fk }, given by representative words fk
−(k−1) −1 (2k) −1 −k
x1 x0 x1 x0

= x0

for values of k greater than or equal to 2. These elements

correspond to the tree pairs shown in the figure below, where each tree has k + 1
carets on both the left and right side of the tree, excluding the caret at the apex
of the tree.

·

❄
⑧⑧ ❄❄❄
❄❄
⑧❄⑧ ⑧
❄
⑧
⑧⑧ ❄ ⑧⑧ ❄❄❄
⑧
❄
⑧⑧ ❄❄
⑧⑧ ❄❄
⑧⑧ ❄
⑧⑧ ❄

··· ❄
⑧ ❄❄

❄··
⑧⑧ ❄❄❄
⑧
⑧❄
⑧❄
⑧⑧ ❄❄
⑧❄
❄
⑧
⑧ ❄
⑧⑧ ❄

·

❄
⑧⑧ ❄❄
⑧❄⑧ ❄
❄
⑧
⑧❄❄
⑧⑧ ❄ ⑧⑧ ❄❄❄
⑧
❄
⑧⑧ ❄❄
⑧⑧ ❄❄
⑧⑧ ❄
⑧⑧ ❄

··· ❄
⑧ ❄❄

❄··
⑧⑧ ❄❄❄
⑧
⑧
❄
⑧⑧ ❄❄
⑧⑧ ❄
❄
⑧⑧ ❄❄
⑧⑧ ❄

⑧ ❄
❄
⑧⑧ ⑧
⑧ ❄❄❄
❄
⑧⑧ ⑧
⑧ ❄❄
⑧⑧ ❄

⑧ ❄
❄
⑧⑧ ⑧
⑧ ❄❄❄
⑧⑧
❄
❄
⑧
⑧ ❄
⑧⑧ ❄

Figure 5. Tree Pair for fk

There are many ways we can build a word representing each fk with two
specific ways that are of particular use to us. Roughly speaking, they correspond to
k

k

making [0, 21 ] internal first then making [ 2 2−1
k , 1] internal, or the reverse. Starting
with the empty word, we carry out a series of x−1
0 rotations to reach the position
k

where vertex [0, 21 ] can be made internal. Then, a series of x0 rotations brings
k

us to the position where vertex [ 2 2−1
k , 1] can be made internal, after which we
rebalance the tree. The alternative proceeds in an analogous fashion, but we
k

k

1
make vertex [ 2 2−1
k , 1] internal before making node [0, 2 ] internal.
−1
These instructions correspond to words in X = {x0 , x1 , x−1
0 , x1 }, so we can

write the element fk as either:
−(k−1) −1 (2k) −1 −k
x1 x0 x1 x0

(1) fk = x0

or

(k+1) −1 −(2k−1) −1 (k−1)
x1 x0
x1 x0

(2) gk = x0

It follows from the relations in F that fk = gk . Using Fordham’s method
for computing geodesic lengths of elements of F , it is relatively straightforward
to show that any minimal length representative of fk in the alphabet {x0 , x1 ,
15

−1
x−1
0 , x1 } has length 4k + 1. That is to say, |fk | = 4k + 1. This means that both

fk and gk are geodesic words for |fk |. These geodesics and the ways they make
k

k

vertices [0, 12 ] and [ 2 2−1
k , 1] internal will serve as the foundation for our proof of
Theorem 1.1.

4.1 Conventions.
Over the course of proving our main result, we will rely on a few conventions to
keep track of distances, rotations, and vertices. These will hold for the remainder
of this paper.
k

For brevity of notation, we will refer to the vertex [0, 12 ] as va and the vertex
k

1
[ 2 2−1
k , 1] as vb . Position [ 2 , 1] may be referred to as the pivot. At times, we will

be concerned about the distance between where a word w maps these vertices
and the pivot on T . We will say that da in w at time t gives the distance in T
between w(t)(va ) and [ 21 , 1]. It is a function given by da (w(t)) = d(w(t)(va ), [ 12 , 1]).
Similarly, db in w at time t will be used to record the distance in T between w(t)(vb )
and [ 21 , 1], given by db (w(t)) = d(w(t)(vb ), [ 21 , 1]). When there is no ambiguity
about the word under discussion, we may simply use da (t) and db (t).
p

Let A be the set of vertices [0, 21 ], 0 ≤ p ≤ k − 1. Let B be the set of vertices
q

[ 2 2−1
q , 1], 1 ≤ q ≤ k − 1. We refer to the interior set of T as I and the exterior set
p

of T as E. Let L be the set of all vertices [0, 21 ], p ≥ 0: the left spine of the tree.
q

Let R be the set of vertices [ 2 2−1
q , 1], q ≥ 1: the right spine of the tree.
We define three counters to keep track of the vertices in A ∪ B. These will
be functions CL , CR , and CI that take a word w and time t as input. CL (w(t)) =
|(w(t)(A∪B))∩L| tracks the number of vertices in A∪B mapped by w(t) to the left
spine of the infinite binary tree. CR (w(t)) = |(w(t)(A∪B))∩R| tracks the number
of vertices in A ∪ B mapped by w(t) to the right spine of the infinite binary tree.
CI (w(t)) = |(w(t)(A ∪ B)) ∩ I| will count the number of vertices in A ∪ B mapped
to the internal set by w(t). When there is no ambiguity about the word under
discussion, we may simply use CL (t), CR (t), and CI (t). Note, these functions are
16

strictly non-negative and CL (w(t)) + CR (w(t)) + CI (w(t)) = 2k − 1 = |A ∪ B|.
Also note CL (w(0)) = k, CR (w(0)) = k − 1, and CI (w(0)) = 0.
We will assume that a language L satisfies the hypotheses of Theorem 1.1, but
not the conclusion. Our method will have us prove facts about L by showing that
certain behaviors will force L to violate the length restrictions of the hypotheses.
This will require us to keep track of how many times certain generators must be
used throughout segments of a given word.
To track generator usage in a word, we define a collection of counters: Cx0 ,
−1 . We increment each counter when we know the
, and Cx−1
, Cx−1
Cx1 , Cx−1
0 ||x1
1
0

corresponding generator is used in the word we are examining. At times, a change
−1
in a word might have been accomplished using either x−1
0 or x1 , in which case we
−1 . Likewise with C
for rotations x0 and x−1
increment Cx−1
0 . We may use
x0 ||x−1
0
0 ||x1

similar notation when two different types of rotations may have been used over a
given time interval.
As a general note, if va is made internal by w(t) for some word w, it must be
the case that w(t − 1)(va ) = [ 21 , 1] and thus da (w(t − 1)) = 0. Similarly, if vb is
made internal at time t, db (w(t − 1)) = 0.
4.2 Proving Theorem 1.1.
−1
Theorem. 1.1 Let L be a language over the alphabet X = {x0 , x1 , x−1
0 , x1 } and

assume there is a non-negative integer c so that for every element g ∈ F there is
a single word w ∈ L such that w represents g and |w| ≤ |g|X + c. Then L cannot
be a subset of the language associated with an automatic structure for F .
An automatic structure for F would consist of a language L(X) and a number
of FSAs. Associated with these is a fellow traveler constant M. Let L be a
language as described in the claim. We will suppose, for contradiction, that all of
L is in L(X). By Theorem 2.7, there is an automatic structure (F, L′ (X)) with
L′ (X) a subset of L(X) with the uniqueness property. While L′ (X) may not be L,
the single representative word in L′ (X) for each element of F is chosen such that
its length is shortest of all possible representative words for that element in L(X).
17

Thus, L′ (X) inherits the length property of L. This means we can assume we are
working with an automatic structure (F, L(X)) where L(X) has the uniqueness
property and L(X) = L which contains a single representative for each element of
F.
Consider the family of elements fk of F described previously. Define C =
max(c, M) if max(c, M) is even or C = max(c, M) + 1 if it is odd. We will select
a value for k significantly larger than C, say k > 1000C. Take note that we have
two separate representative means of writing out fk given by fk and gk .
We will approach fk from two separate directions, moving through ΓX (F )
along the paths outlined by fk and gk . First, we will look at successively longer
prefixes of fk and examine the representative words for these elements in L. We
will show that the final time vertex vb is made internal in one of these prefixes
must occur before the first time va is made internal at all. This will be done
by supposing otherwise, counting the number of generators that must be used in
these words and showing that the length of the words would have to be longer
than the length restrictions on L, giving a contradiction. Prefixes of fk that differ
by length one represent adjacent elements in ΓX (F ) so their representative words
in L satisfy the M fellow traveler property. We will use this and similar word
length techniques to show that the vb before va property holds in the L accepted
representative of successfully longer prefixes of fk , up to fk itself.
Then, we will examine the prefixes of gk and use a similar line of argument to
show that in the L accepted representative for gk , va must be made internal for
the final time before vb is made internal at all. Because fk and gk represent the
same element and the L accepted representative of each is the same word, this
will give a contradiction, proving Theorem 1.1.

4.3 The Path for fk :
−(k−1) −1 (2k) −1 −k
x1 x0 x1 x0 .

We will look at the prefixes of fk = x0

look at a particular collection of prefixes of fk .
−(k−1) −1 (2k) −1 −i
x1 x0 x1 x0

Definition 4.13. wi = x0

18

where 0 ≤ i ≤ k

To do so, we will

Take note that wi = fk (3k + 1 + i) is the 3k + 1 + i prefix of fk . Thus, wk = fk .
Note that wi maps both va and vb to the interior of T .
Using Fordham’s method, we can compute that any minimal length repre−1
sentative of wi in the letters {x0 , x1 , x−1
0 , x1 } has length 3k + 1 + i. That is to

say, |wi | = 3k + 1 + i. By our assumption before, each element of F has a single
representative in L whose length is at most c greater than minimal. We use wi′ to
denote the representative in L of wi . Note that |wi′ | ≤ |wi |+c = 3k +i+1+c.
We will explore the path for fk using six lemmas given below. These lemmas
are a collection of useful results as well as the parts of an inductive argument
to show vb must be made internal before va in the accepted representative for fk .
Define l =

C
2

′
+1. Word wk−l
will serve as the starting word for our induction.

Lemma 4.14. In wi′ , k − l ≤ i ≤ k, there can be no more than 2C times where
any of the vertices in A are made internal.
The next two lemmas give the base of the inductive argument.
′
Lemma 4.15. In wk−l
, the final time where vertex vb is made internal must occur

before the first time the vertex va is made internal.
Lemma 4.16. None of the vertices in B are internal at any time when va is made
′
internal in wk−l
.

Lemma 4.17. If, in wi′ , k − l ≤ i ≤ k, the final time where vertex vb is made
internal must occur before the first time the vertex va is made internal and wi (t)
makes vb internal, then k ≤ t ≤ k + C + 2.
Lemma 4.18. If, in wi′ , k − l ≤ i ≤ k, the following two conditions hold:
(1) The final time where vertex vb is made internal must occur before the first
time the vertex va is made internal,
(2) None of the vertices in B are internal at any time when va is made internal,
then we cannot reduce da to M − 1 before time 3k − M in wi′ .
The following lemma gives the inductive step.
19

Lemma 4.19. If, in wi′ , k − l ≤ i ≤ k − 1, the following two conditions hold:
(1) The final time vertex vb is made internal occurs before the first time the
vertex va is made internal,
(2) None of the vertices in B are internal at any time when va is made internal,
′
then (1) and (2) hold true in wi+1
, as well.

We now prove each of these lemmas and then complete the inductive argument
they establish.
Lemma. 4.14 In wi′ , k − l ≤ i ≤ k, there can be no more than 2C times where
any of the vertices in A are made internal.
Proof. Assume, for contradiction, that in wi′ , there are T ≥ 2C + 1 times where
any of the vertices in A are made internal.
We look at times t0 , ta , tb , and tf . Define t0 = 0 and tf = |wi′ |. Define ta as the
final time that vertex va is made internal in wi′ and tb as the final time that vertex
vb is made internal in wi′ . Most of these times are clearly distinct because the action
of F on the tree is bijective and wi′ (t0 )([ 21 , 43 ]) = wi′ (ta )(va ) = wi′ (tb )(vb ) = [ 21 , 43 ].
Time tf must be distinct from the others because it is certainly not t0 as vertices
are made internal in wi′ and because va and vb are mapped approximately k from
the pivot at tf .
One of the following two orderings must hold: t0 < ta < tb < tf or t0 < tb <
ta < tf . We consider the impact each has on |wi′ |.
Ordering t0 < ta < tb < tf :
We begin with the time intervals given by t0 < ta < tb < tf and account for
the total rotations needed in each interval.
Interval t0 ≤ t ≤ ta :
At t0 , all of A is mapped to the left of the pivot and to the right of va .
Thus, CL (t0 ) = k and da (t0 ) = k + 1. Because va will be made internal at ta ,
da (ta − 1) = 0. The vertices in A are mapped to the left of the pivot, so the only
way to decrease da is with x0 rotations. We must increment Cx0 by at least k + 1.
20

At ta , a single x−1
by 1.
1 rotation makes va internal, so we increment Cx−1
1
Additionally, some of the vertices in A and B may be internal at ta , say m1
of the vertices in A and n1 of the vertices in B. Because CI (t0 ) = 0, it will take a
single x−1
1 rotation to make each of these internal, requiring us to increment Cx−1
1
by another m1 + n1 this step.
In total, this interval requires us to increment Cx0 by k + 1 and Cx−1
by
1
m1 + n1 + 1 for a total of k + m1 + n1 + 2 rotations in this interval.
Interval ta < t ≤ tb :
Because wi′ (ta )(va ) = [ 21 , 43 ] and F preserves the infix ordering of vertices,
wi′ (ta ) maps A ∪ B at or to the right of the pivot. Thus, CL (ta ) = 0. We also know
that CI (ta ) = m1 +n1 , so CR (ta ) = 2k −1−(m1 +n1 ) and db (ta ) ≥ 2k −m1 −n1 −1.
These vertices are mapped to the right spine, so reducing db can be accomplished
either by moving them to the left spine of the tree with x−1
0 rotations or making
1
′
them internal with x−1
1 rotations. Because wi (tb − 1)(vb ) = [ 2 , 1], db (tb − 1) = 0
−1 by at least 2k − m1 − n1 − 1.
and we must increment Cx−1
0 ||x1

At tb , a single x−1
by 1.
1 rotation makes vb internal, so we increment Cx−1
1
It is possible some of the vertices in A ∪ B that were internal at ta are external
at tb . Additionally, some of these vertices which were external at ta may be internal
at tb . We may have already accounted for making these new vertices internal. Say
that at tb , m2 vertices in A are internal that were external at ta and n2 vertices
in B are internal that were external at ta . Of the m1 vertices in A that were
internal at ta , say m2e are external at tb , and of the n1 vertices in B that were
internal at ta , say n2e are external at tb . We have not accounted for making any
vertices external this step, so we must increment Cx1 by m2e + n2e to accomplish
this change. Take note, CI (tb ) = (m1 + m2 − m2e ) + (n1 + n2 − n2e ).
−1 by 2k − m1 − n1 − 1,
In total, this interval requires us to increment Cx−1
0 ||x1

Cx−1
by 1, and Cx1 by m2e + n2e for a total of 2k − m1 − n1 + m2e + n2e rotations
1
in this interval.
Interval tb < t ≤ tf :

21

Note, wi′ (tb )(vb ) = [ 21 , 43 ]. Because F preserves the infix ordering of vertices,
this means all of A ∪ B is mapped to the left of position [ 21 , 43 ]. Thus these vertices
must be mapped to the left side of the tree, meaning CR (tb ) = 0. We know that
CI (tb ) = m1 + m2 + n1 + n2 − m2e − n2e , so CL (tb ) = 2k − 1 − (m1 + m2 + n1 +
n2 − m2e − n2e ). Note that CI (tf ) = 0 and wi′ (tf )([0, 12

k−i

]) = [0, 1], the root of the

tree. Thus, we must have CL (tf ) = i and CR (tf ) = 2k − i − 1.
Bringing CI (tf ) to 0 requires all of A ∪ B to be internal. Because CI (tb ) =
m1 + m2 + n1 + n2 − m2e − n2e , it will take at least that many x1 rotations to make
these vertices external, incrementing Cx1 by m1 + m2 + n1 + n2 − m2e − n2e .
We require additional rotations related to the vertices we have just made
external. Any time a vertex is made external, it is mapped from the interior of
q

the tree to the pivot. This is fine for the vertices [ 2 2−1
q , 1], 1 ≤ q ≤ k − 1, and
p

[0, 21 ], 0 ≤ p ≤ k − i − 1, because wi′ (tf ) maps them to the right spine of the tree.
p

However, all of the vertices [0, 12 ], k − i ≤ p ≤ k − 1 must be mapped to the left
spine in wi′ (tf ). Mapping a vertex from the right spine of the tree to the left spine
−1
can only be accomplished by an x−1
0 rotation and we have accounted for no x0

rotations in this step thus far. Note, wi′ (tb ) maps exactly m1 + m2 − m2e of the
vertices in A to the interior. If m1 + m2 − m2e > k − i, then m1 + m2 − m2e − (k − i)
p

of these vertices must come from the set [0, 12 ], k − i ≤ p ≤ k − 1. These vertices
will each require an x−1
0 rotation to map them to the left side of the tree by time
tf , so if m1 + m2 − m2e > k − i, then we increment Cx0 by m1 + m2 − m2e − (k − i).
Recall, CR (tb ) = 0 and CR (tf ) = 2k−i−1. Making a vertex from A∪B external
increases CR by 1 and we have accounted for making certain all of A∪B is external
with m1 + m2 + n1 + n2 − m2e − n2e rotations. If m1 + m2 + n1 + n2 − m2e − n2e <
2k − i − 1, we must increment Cx0 by (2k − i − 1) − (m1 + m2 + n1 + n2 − m2e − n2e )
as the only remaining way to increase CR is mapping vertices from the left spine
of the tree to the right spine.
In total, this interval requires us to increment Cx1 by m1 +m2 +n1 +n2 −m2e −
n2e . If m1 + m2 − m2e > k − i, we must increment Cx0 by m1 + m2 − m2e − k + i.

22

If m1 + m2 + n1 + n2 − m2e − n2e < 2k − i − 1, we must increment Cx0 by
2k − i − 1 − m1 − m2 − n1 − n2 + m2e + n2e .
Additional Accounting:
By our assumption, we needed T ≥ 2C + 1 times in wi′ where any vertices in A
were made internal. In the above, we have accounted for m1 + m2 instances where
one of these vertices is made internal. Each of these times occurs when one of the
vertices is made internal during one of our time intervals and is not external at
the end of it. We have also accounted for all instances where these were eventually
made external and no other instances where a vertex in A was made external.
If m1 + m2 ≥ T , we are done. If not, there must be additional times where
vertices in A were made internal. These must be times t when a vertex a ∈ A is
made internal where both t and the next time t′ when a is made external occur
in the same time interval. Each such pair contributes both an x−1
and an x1
1
rotation that we have not yet accounted for, requiring us to increment Cx−1
by
1
T − (m1 + m2 ) and Cx1 by T − (m1 + m2 ) if m1 + m2 < T .
In total, this step requires us to increment Cx1−1 by T − (m1 + m2 ) and Cx1 by
T − (m1 + m2 ) if m1 + m2 < T for a total of 2T − 2m1 − 2m2 if m1 + m2 < T .
Total Rotations:
In total, we have established that |wi′ | ≥ (k + m1 + n1 + 2) + (2k − m1 − n1 +
m2e + n2e ) + (m1 + m2 + n1 + n2 − m2e − n2e ) = 3k + 2 + m1 + n1 + m2 + n2 , plus
an additional m1 + m2 − m2e − k + i if (a) : m1 + m2 − m2e ≥ k − i, an additional
2k−i−1−m1 −m2 −n1 −n2 +m2e +n2e if (b) : m1 +m2 +n1 +n2 −m2e −n2e < 2k−i−1,
and an additional 2T − 2m1 − 2m2 if (c) : m1 + m2 < T .
If (a) does not hold, then m1 + m2 − m2e < k − i. But this means that
m1 + m2 + n1 + n2 − m2e − n2e < 2k − i − 1 as n1 + n2 ≤ k − 1 and n2e ≥ 0. So if
(a) is false, (b) is true.
If (c) does not hold, then m1 + m2 ≥ T ≥ 2C + 1. Recall, k − l ≤ i ≤ k − 1,
so 0 ≤ k − i ≤ l =
C
2

C
2

+ 1. This means m1 + m2 − m2e ≥ m1 + m2 ≥ 2C + 1 >

+ 1 ≥ k − i. So, if (c) is false, (a) is true.

23

Also of note, T = 2C + 1, m2e ≥ 0, and k > i.
This gives us five cases to consider:
(1) Conditions (a), (b), and (c) hold. Thus, |wi′ | ≥ 3k + 2 + m1 + n1 + m2 + n2 +
(m1 +m2 −m2e −k +i)+(2k −i−1−m1 −m2 −n1 −n2 +m2e +n2e )+(2T −
2m1 − 2m2 ) = 4k + 1 − m1 − m2 + n2e + 2T . Note, m1 + m2 < T because (c)
holds. So, |wi′ | ≥ 4k+1−m1 −m2 +n2e +2T > 4k+1+n2e +T > 3k+i+1+C.
(2) Conditions (a) and (b) hold, (c) is false. Thus, |wi′ | ≥ 3k+2+m1 +n1 +m2 +
n2 + (m1 + m2 − m2e − k + i) + (2k − i − 1 − m1 − m2 − n1 − n2 + m2e + n2e ) =
4k + 1 + m1 + m2 + n2e . We know m1 + m2 ≥ T > C because (c) is false.
So |wi′ | ≥ 4k + 1 + m1 + m2 + n2e > 4k + 1 + C + n2e > 3k + i + 1 + C.
(3) Conditions (a) and (c) hold, (b) is false. Thus, |wi′ | ≥ 3k+2+m1 +n1 +m2 +
n2 +(m1 +m2 −m2e −k+i)+(2T −2m1 −2m2 ) = 2k+2+n1 +n2 −m2e +i+2T .
Because (c) holds, m1 + m2 < T . Also, (b) does not hold. Putting this
together, T +n1 +n2 −m2e > m1 +m2 +n1 +n2 −m2e −n2e ≥ 2k−i−1. Now,
we can see, |wi′ | ≥ 2k + 2 + n1 + n2 −m2e + i+ 2T > 2k + 1 + 2k −i−1 + T >
4k + T > 3k + i + 1 + C.
(4) Only (a) is true. Thus, |wi′ | ≥ 3k +2+m1 +n1 +m2 +n2 +(m1 +m2 −m2e −
k+i) = 2k+2+2m1 +2m2 −m2e +n1 +n2 +i. Because (b) does not hold, we
know m1 + m2 + n1 + n2 − m2e ≥ m1 + m2 + n1 + n2 − m2e − n2e ≥ 2k − i − 1.
This, along with the fact that (c) is false, means m1 + m2 ≥ T Thus, |wi′ | ≥
2k +2+2m1 +2m2 +n1 +n2 +i ≥ 4k +1+T ≥ 3k +i+1+T > 3k +i+1+C.
(5) Conditions (b) and (c) hold, (a) is false. Thus, |wi′ | ≥ 3k+2+m1 +n1 +m2 +
n2 + (2k − i − 1 − m1 − m2 − n1 − n2 + m2e + n2e ) + (2T − 2m1 − 2m2 ) =
5k + 1 − i + m2e + n2e + 2T − 2m1 − 2m2 . Because (a) doesn’t hold,
m1 + m2 − m2e < k − i, meaning k − i − m1 − m2 + m2e > 0. So,
|wi′ | ≥ 5k +1−i+m2e +n2e +2T −2m1 −2m2 > 4k +1+n2e +2T −m1 −m2 .
Then, because (c) holds, we know m1 + m2 < T , and we have |wi′ | ≥
4k + 1 + n2e + 2T − m1 − m2 > 4k + 1 + T > 3k + i + 1 + C.

24

In every case, |wi′ | > 3k + i + 1 + C ≥ 3k + i + 1 + c = |wi′ | + c ≥ |wi′ |, so we
have a contradiction.
Ordering t0 < tb < ta < tf :
We next examine the time intervals given by t0 < tb < ta < tf and account
for the total rotations needed in each interval.
Interval t0 ≤ t ≤ tb :
At t0 , all of B is mapped at or to the right of the pivot and to the left of vb .
Thus, CR (t0 ) = k − 1 and db (t0 ) = k − 1. We must have db (tb − 1) = 0 so that vb
can be made internal at tb . Decreasing db requires us to either map the intervening
−1
vertices to the left of the pivot with x−1
0 rotations or make them internal with x1
−1 by at least k − 1. Let n1 be the number
rotations. Thus, we increment Cx−1
0 ||x1

of vertices in B that are internal at tb .
by 1.
At tb , a single x−1
1 rotation makes vb internal, so we increment Cx−1
1
Additionally, it is possible that some vertices in A are internal at tb . At t0 , A
is mapped to the left spine. The only way to bring a vertex from the left spine to
the pivot is an x0 rotation. No x0 rotations were yet required in this interval, so
each vertex in A that is internal at tb requires an x0 rotation to reach the pivot
and an x−1
1 rotation to make it internal. Say m1 vertices in A are internal at tb ,
by m1 .
requiring us to increment Cx0 by m1 and Cx−1
1
−1 by k − 1, Cx by m1 ,
In total, this interval requires us to increment Cx−1
0
0 ||x1

and Cx−1
by m1 + 1, for a total of k + 2m1 rotations in this step.
1
Interval tb < t ≤ ta :
Because wi′ (tb )(vb ) = [ 21 , 43 ] and F preserves the infix ordering of vertices, wi′ (tb )
maps A ∪ B to the left of the pivot. This is the final time vb is made internal,
so none of the vertices in A ∪ B can be suspended from it. Thus, wi′ (tb ) maps
A ∪ B to the left side of the tree with va mapped to the left of where all these
vertices are mapped. This means CR (tb ) = 0 and we know CI (tb ) = m1 + n1 , so
CL (tb ) = 2k − 1 − (m1 + n1 ) and da (tb ) ≥ 2k − 1 − (m1 + n1 ) + 1 = 2k − m1 − n1 .
We must have da (ta − 1) = 0, so the vertices in A ∪ B mapped to the left of the
25

pivot must be mapped to the right side of the tree with x0 rotations. Thus, Cx0
must be incremented by 2k − m1 − n1 .
At ta , a single x−1
by 1.
1 rotation makes va internal, so we increment Cx−1
1
It is possible some of the vertices in A ∪ B that were internal at tb are external
at ta . Additionally, some of these vertices which were external at tb may be internal
at ta . Making an external vertex internal takes an x−1
1 rotation and making an
internal vertex external takes an x1 rotation. Say that at ta , m2 vertices in A
and n2 vertices in B are internal that were external at tb . Of the m1 vertices in
A that were internal at tb , say m2e were external at ta , and of the n1 vertices
in B that were internal at tb , n2e are external at ta . We must increment Cx−1
1
by m2 + n2 and Cx1 by m2e + n2e to accomplish this change. In total then,
CI (tb ) = (m1 + m2 − m2e ) + (n1 + n2 − n2e ).
by
In total, this interval requires us to increment Cx0 by 2k − m1 − n1 , Cx−1
1
m2 +n2 +1, and Cx1 by m2e +n2e , for a total of 2k+m2 +m2e +n2 +n2e +1−m1 −n1
rotations in this step.
Interval ta < t ≤ tf :
Note, wi′ (ta )(va ) = [ 12 , 43 ]. Because F preserves the infix ordering of vertices,
all of A ∪ B is mapped to the right of position [ 12 , 43 ]. Thus CL (ta ) = 0. We know
the CI (ta ) = m1 + m2 + n1 + n2 − m2e − n2e , so CR (tb ) = 2k − 1 − (m1 + m2 +
n1 + n2 − m2e − n2e ). Note that CI (tf ) = 0 and wi′ (tf )([0, 12

k−i

]) = [0, 1], the root

of the tree. Thus, we must have CL (tf ) = i and CR (tf ) = 2k − i − 1.
Bringing CI (tf ) to 0 requires all of A ∪ B to be internal. Because CI (ta ) =
m1 + m2 + n1 + n2 − m2e − n2e , it will take at least that many x1 rotations to make
vertices external, incrementing Cx1 by m1 + m2 + n1 + n2 − m2e − n2e .
The only way to increase CL is using x0 rotations to move vertices from the
right side of the tree to the left side. Because CL (ta ) = 0 and CL (tf ) = i, we must
increment Cx0 by i.

26

In total, this step requires us to increment Cx1 by m1 +m2 +n1 +n2 −m2e −n2e
and Cx0 by i, for a total of m1 + m2 + n1 + n2 − m2e − n2e + i rotations in this
step.
Additional Accounting:
In the above, we have accounted for m1 + m2 instances where a vertex in A is
made internal. Each of these times occurs when one of the vertices is made internal
during one of our time intervals and is not external at the end of it. We have also
accounted for all instances where these were eventually made external and no other
instances where a vertex in A were made external. There may be times t when a
vertex a ∈ A is made internal where both t and the next time t′ when a is made
external occur in the same time interval. Each such pair contributes both an x−1
1
and an x1 rotation that we have not yet accounted for, so say there are m3 pairs,
requiring us to increment Cx−1
by m3 and Cx1 by m3 for a total of 2m3 rotations
1
in this step. Note, m1 + m2 + m3 = T ≥ 2C + 1.
Total rotations:
Between all these steps, we have established that |wi′ | ≥ (k + 2m1 ) + (2k +
m2 + m2e + n2 + n2e + 1 − m1 − n1 ) + (m1 + m2 + n1 + n2 − m2e − n2e + i) + (2m3 ) =
3k + i + 2(m1 + m2 + m3 ) + 2n2 + 1 ≥ 3k + i + 1 + 2(m1 + m2 + m3 ). We know
m1 +m2 +m3 ≥ 2C +1, so |wi′ | ≥ 3k+i+1+2(m1 +m2 +m3 ) ≥ 3k+i+1+4C +2 =
3k + i + 1 + C + (3C + 1) + 2 > 3k + i + 1 + C ≥ 3k + i + 1 + c > |wi′ | + c ≥ |wi′ |.
This is a contradiction.
Conclusion
Now, whether tb < ta or ta < tb , we see that the length of wi′ must be longer
than the necessary restriction that |wi′ | ≤ |wi′ | + c demands. Because we have a
contradiction either way, we see that in wi′ , there can be no more than 2C times
that any of the vertices in A are made internal. Thus, the lemma holds.



′
Lemma. 4.15 In wk−l
, the final time where vertex vb is made internal must occur

before the first time the vertex va is made internal.
27

Proof. Assume, for contradiction, the final time vb is made internal occurs after
the first time va is made internal.
′
We consider the impact this has on |wk−l
|. We look at times t0 , ta , tb , and tf .
′
Define t0 = 0 and tf = |wk−l
|. Define ta as the first time that va is made internal
′
′
in wk−l
and tb as the final time vb is made internal in wk−l
. These times are clearly
′
distinct because the action of F on the tree is bijective and wk−l
(t0 )([ 12 , 43 ]) =
l

′
′
′
(ta )(va ) = wk−l
(tb )(vb ) = wk−l
(tf )([ 12 , 21
wk−l

l−1

]) = [ 21 , 43 ].

′
This means t0 < ta < tb < tf . We consider the impact each has on |wk−l
|.

Interval t0 ≤ t ≤ ta :
At t0 , all of A is mapped to the left of the pivot and to the right of va . Thus,
CL (t0 ) = k and da (t0 ) = k + 1. We know that va is made internal at time ta ,
so da (ta − 1) = 0. Because the intervening vertices are mapped to the left of the
pivot, the only way to decrease da is with x0 rotations. Thus, we must increment
Cx0 by at least k + 1.
At ta , a single x−1
by 1.
1 rotation makes va internal, so we increment Cx−1
1
Additionally, some of the vertices in A and B may be internal at ta , say m1
of the vertices in A and n1 of the vertices in B. Because CI (t0 ) = 0, it will take a
single x−1
1 rotation to make each of these internal, requiring us to increment Cx−1
1
by another m1 + n1 this step.
by
In total, this interval requires us to increment Cx0 by k + 1 and Cx−1
1
m1 + n1 + 1 for a total of k + m1 + n1 + 2 rotations in this interval.
Interval ta < t ≤ tb :
′
Because wk−l
(ta )(va ) = [ 21 , 43 ] and F preserves the infix ordering of vertices,
′
(ta ) maps A∪B at or to the right of the pivot. Thus, CL (ta ) = 0. We also know
wk−l

that CI (ta ) = m1 +n1 , so CR (ta ) = 2k −1−(m1 +n1 ) and db (ta ) ≥ 2k −m1 −n1 −1.
′
Because wk−l
(tb − 1)(vb ) = [ 21 , 1], db (tb − 1) = 0. These intervening vertices are

mapped to the right spine, so reducing db can be accomplished either by moving
them to the left spine of the tree with x−1
0 rotations or making them internal with
−1 by at least 2k − m1 − n1 − 1.
x−1
1 rotations. Thus, we must increment Cx−1
0 ||x1

28

At tb , a single x−1
by 1.
1 rotation makes vb internal, so we increment Cx−1
1
It is possible some of the vertices in A ∪ B that were internal at ta are external
at tb . Additionally, some of these vertices which were external at ta may be internal
at tb . We may have already accounted for making any new vertices internal. Say
that by time tb , m2 vertices in A are internal that were external at ta and n2
vertices in B are internal that were external at ta . Of the m1 vertices in A that
were internal at ta , say m2e are external at tb , and of the n1 vertices in B that
were internal at ta , n2e are external at tb . We must increment Cx1 by m2e + n2e to
accomplish this change. In total then, CI (tb ) = (m1 + m2 − m2e ) + (n1 + n2 − n2e ).
−1 by 2k − m1 − n1 − 1,
In total, this interval requires us to increment Cx−1
0 ||x1

Cx−1
by 1, and Cx1 by m2e + n2e for a total of 2k − m1 − n1 + m2e + n2e rotations
1
in this interval.
Interval tb < t ≤ tf :
′
Note, wk−l
(tb )(vb ) = [ 21 , 43 ]. This is the final time vb is made internal, so none

of the vertices in A ∪ B can be suspended from it. Otherwise, removing them
from the interior of the tree would require us to make vb external again before
tf , which cannot occur. Because F preserves the infix ordering of vertices, this
means all of A ∪ B is mapped to the left of position [ 21 , 43 ], but not below it. Thus
it must be on the left side of the tree, meaning CR (tb ) = 0. We know the CI (tb ) =
m1 + m2 + n1 + n2 − m2e − n2e , so CL (tb ) = 2k − 1 − (m1 + m2 + n1 + n2 − m2e − n2e ).
l

′
(tf )([0, 12 ]) = [0, 1], the root of the tree. Thus, we
Note that CI (tf ) = 0 and wk−l

must have CL (tf ) = k − l and CR (tf ) = 2k − k + l − 1.
Bringing CI (tf ) to 0 requires all of A ∪ B to be internal. Because CI (tb ) =
m1 + m2 + n1 + n2 − m2e − n2e , it will take at least that many x1 rotations to make
vertices external, incrementing Cx1 by m1 + m2 + n1 + n2 − m2e − n2e .
We require additional rotations related to these vertices we have made external. Any time a vertex is made external, it is mapped from the interior of
q

the tree to the pivot. This is fine for the vertices [ 2 2−1
q , 1], 1 ≤ q ≤ k − 1, and
p

′
(tf ) maps them to the right spine of the tree.
[0, 21 ], 0 ≤ p ≤ l − 1, because wk−l
p

However, all of the vertices [0, 21 ], l ≤ p ≤ k − 1 must be mapped to the left
29

′
spine in wk−l
(tf ). Mapping a vertex from the right spine of the tree to the left

spine can only be accomplished by an x−1
0 rotation and we have accounted for no
′
x−1
0 rotations in this step thus far. wk−l (tb ) maps exactly m1 + m2 − m2e of the

vertices in A to the interior. If m1 + m2 − m2e > l, then m1 + m2 − m2e − l of
p

these vertices must come from the set [0, 12 ], l ≤ p ≤ k − 1. These vertices will
each require an x−1
0 rotation to map them to the left side of the tree before time
tf , so if m1 + m2 − m2e > l, then we increment Cx0 by m1 + m2 − m2e − l.
Recall, CR (tb ) = 0 and CR (tf ) = 2k − i − 1. Making a vertex from A ∪ B
external increases CR by 1 and we have accounted for making all of A ∪ B external
with m1 +m2 +n1 +n2 −m2e −n2e rotations. If m1 +m2 +n1 +n2 −m2e −n2e < k+l−1,
we must increment Cx0 by (k + l − 1) − (m1 + m2 + n1 + n2 − m2e − n2e ) as the
only remaining way to increase CR is mapping vertices from the left spine of the
tree to the right spine.
In total, this interval requires us to increment Cx1 by m1 + m2 + n1 + n2 −
m2e − n2e . If m1 + m2 − m2e > l, we must increment Cx0 by m1 + m2 − m2e − l.
If m1 + m2 + n1 + n2 − m2e − n2e < k + l − 1, we must increment Cx0 by k + l −
1 − m1 − m2 − n1 − n2 + m2e + n2e .
Total Rotations:
′
Between all these intervals, |wk−l
| ≥ (k + m1 + n1 + 2) + (2k − m1 − n1 +

m2e + n2e ) + (m1 + m2 + n1 + n2 − m2e − n2e ) = 3k + 2 + m1 + m2 + n1 + n2 , plus
an additional m1 + m2 − m2e − l if (a) : m1 + m2 − m2e ≥ l, and an additional
k+l−1−m1 −m2 −n1 −n2 +m2e +n2e if (b) : m1 +m2 +n1 +n2 −m2e −n2e < k+l−1.
If (a) does not hold, then m1 + m2 − m2e < l. But this means that m1 + m2 +
n1 + n2 − m2e − n2e < k + l − 1 as n1 + n2 ≤ k − 1 and n2e ≥ 0. So if (a) is false,
(b) is true.
Recall, l =

C
2

+ 1, m2e ≥ 0, and n2e ≥ 0.

This gives us three cases to consider:
′
(1) Conditions (a) and (b) hold. Thus, |wk−l
| ≥ 3k+2+m1 +m2 +n1 +n2 +(m1 +

m2 −m2e −l)+(k+l−1−m1 −m2 −n1 −n2 +m2e +n2e ) = 4k+1+m1 +m2 +n2e .

30

Note that because (a) holds and m2e ≥ 0, m1 + m2 ≥ m1 + m2 − m2e ≥ l.
′
This means |wk−l
| ≥ 4k + 1 + m1 + m2 + n2e ≥ 4k + l + 1.
′
(2) Condition (a) holds, (b) is false. Thus, |wk−l
| ≥ 3k +2+m1 +m2 +n1 +n2 +

(m1 + m2 − m2e − l) = 3k + 2 + (m1 + m2 ) + (m1 + m2 + n1 + n2 − m2e ) − l.
Because (b) does not hold and n2e ≥ 0, m1 + m2 + n1 + n2 − m2e ≥
m1 + m2 + n1 + n2 − m2e − n2e ≥ k + l − 1. And because (a) does hold and
′
m2e ≥ 0, m1 + m2 ≥ m1 + m2 − m2e > l. So, |wk−l
| ≥ 3k + 2 + (m1 + m2 ) +

(m1 + m2 + n1 + n2 − m2e ) − l > 3k + 2 + l + k + l − 1 − l = 4k + l + 1.
′
(3) Condition (b) holds, (a) is false. Thus, |wk−l
| ≥ 3k +2+m1 +m2 +n1 +n2 +

(k +l−1−m1 −m2 −n1 −n2 +m2e +n2e ) = 4k +l+1+m2e +n2e ≥ 4k +l+1.
′
In every case, |wk−l
| ≥ 4k + l + 1 = 4k − l + 2l + 1 > 4k − l + 1 + C ≥
′
′
4k − l + 1 + c = |wk−l
| + c ≥ |wk−l
|, so we have a contradiction. The length of
′
′
′
wk−l
must be longer than the restriction that |wk−l
| ≤ |wk−l
| + c demands. Thus,
′
in wk−l
, the final time where vertex vb is made internal must occur before the first

time the vertex va is made internal.



Lemma. 4.16 None of the vertices in B are internal at any time when va is made
′
internal in wk−l
.
′
Proof. Assume, for contradiction, that in wk−l
, at least one of the vertices in B

is internal at a time when va is made internal. Call this vertex vj . We look at
′
times t0 , tb , ta , tj and tf . Define t0 = 0 and tf = |wk−l
|. Define ta to be the last
′
time va is made internal in wk−l
while vj was internal. Let tb be the final time
′
vb is made internal in wk−l
. Let tj be the final time vj is made external. Most

of these times are clearly distinct because the action of F on the tree is bijective
l

′
′
′
′
(t0 )([ 21 , 43 ]) = wk−l
(ta )(va ) = wk−l
(tb )(vb ) = wk−l
(tf )([ 12 , 21
and wk−l

l−1

]) = [ 12 , 43 ].

Because tj is when vj is made external, it cannot be t0 , ta , or tb . It cannot be tf
′
. By definition, tj must come after ta . Note that by
as vj is not internal in wk−l

Lemma 4.15, tb < ta . All of this means that we can consider the time intervals
′
given by t0 < tb < ta < tj ≤ tf and the impact this has on |wk−l
|.

Interval t0 ≤ t ≤ tb :
31

At t0 , all of B is mapped at or to the right of the pivot and to the left of vb .
Thus, CR (t0 ) = k − 1 and db (t0 ) = k − 1. We must have db (tb − 1) = 0 so that vb
can be made internal at tb . Decreasing db requires us to either map the intervening
−1
vertices to the left of the pivot with x−1
0 rotations or make them internal with x1
−1 by at least k − 1. Let n1 be the number
rotations. Thus, we increment Cx−1
0 ||x1

of vertices in B that are internal at tb .
At tb , a single x−1
by 1.
1 rotation makes vb internal, so we increment Cx−1
1
Additionally, it is possible that some subset of A is internal at tb . At t0 , A is
mapped to the left spine. The only way to bring a vertex from the left spine to
the pivot is an x0 rotation. No x0 rotations were yet required in this interval, so
each vertex in A that is internal at tb requires an x0 rotation to reach the pivot
and an x−1
1 rotation to make it internal. Say m1 vertices in A are internal at tb ,
by m1 .
requiring us to increment Cx0 by m1 and Cx−1
1
−1 by k − 1, Cx by m1 ,
In total, this interval requires us to increment Cx−1
0
0 ||x1

by m1 + 1, for a total of k + 2m1 rotations in this step.
and Cx−1
1
Interval tb < t ≤ ta :
′
Because wk−l
(tb )(vb ) = [ 21 , 43 ] and F preserves the infix ordering of vertices,
′
(tb ) maps A ∪ B to the left of the pivot. This is the final time vb is made
wk−l
′
(tb )
internal, so none of the vertices in A ∪ B can be suspended from it. Thus, wk−l

maps A ∪ B to the left side of the tree with va mapped to the left of where all
these vertices are mapped. This means CR (tb ) = 0 and we know CI (tb ) = m1 + n1 ,
so CL (tb ) = 2k − 1 − (m1 + n1 ) and da (tb ) ≥ 2k − 1 − (m1 + n1 ) + 1 = 2k − m1 − n1 .
We must have da (ta − 1) = 0 to make va internal at ta , so the vertices in A ∪ B
mapped to the left of the pivot must be mapped to the right side of the tree with
x0 rotations. Thus, Cx0 must be incremented by 2k − m1 − n1 .
At ta , a single x−1
by 1.
1 rotation makes va internal, so we increment Cx−1
1
It is possible some of the vertices in A ∪ B that were internal at tb are external
at ta . Additionally, some of these vertices which were external at tb may be internal
at ta . Making an external vertex internal takes an x−1
1 rotation and making an
internal vertex external takes an x1 rotation. Say that at ta , m2 vertices in A
32

and n2 vertices in B are internal that were external at tb . Of the m1 vertices in
A that were internal at tb , say m2e were external at ta , and of the n1 vertices
in B that were internal at tb , n2e are external at ta . We must increment Cx−1
1
by m2 + n2 and Cx1 by m2e + n2e to accomplish this change. In total then,
CI (tb ) = (m1 + m2 − m2e ) + (n1 + n2 − n2e ).
In total, this interval requires us to increment Cx0 by 2k − m1 − n1 , Cx−1
by
1
m2 +n2 +1, and Cx1 by m2e +n2e , for a total of 2k+m2 +m2e +n2 +n2e +1−m1 −n1
rotations in this step.
Interval ta < t < tj :
′
Note, wk−l
(ta )(va ) = [ 12 , 43 ]. Because F preserves the infix ordering of vertices,

all of A ∪ B is mapped to the right of position [ 12 , 43 ]. Thus CL (ta ) = 0. Because
′
(tj )(vj ) = [ 21 , 1] and F again preserves the infix ordering of vertices, all of A
wk−l

must be mapped to the left of [ 12 , 1] by tj . Thus, all of the vertices in A must either
be internal or mapped to the left spine of the tree. At ta , k − (m1 + m2 − m2e ) of
the vertices in A were external, and moving these vertices from the right spine of
−1 by k − (m1 + m2 − m2e ). Say that at
the tree requires us to increment Cx−1
0 ||x1

tj , m3 vertices in A are internal that were external at ta .
In addition to the above it is possible some of the vertices in A ∪ B that were
internal at ta are external at tj and some of these vertices in B which were external
at ta may be internal at tj . Say that at tj , n3 vertices in B are internal that were
external at ta . Additionally, say that of the m1 + m2 − m2e vertices in A that
were internal at ta , m3e were external at tj and of the n1 + n2 − n2e vertices in B
that were internal at ta , say n3e were external at tj . We have not accounted for
these changes yet, so we must increment Cx1 by m3e + n3e to make these vertices
external and Cx−1
by n3 to make the required vertices internal.
1
In total, this interval requires us to increment Cx1 by m3e + n3e , Cx−1
by n3 ,
1
−1 by k−(m1 +m2 −m2e ), for a total of k−m1 −m2 +m2e +n3 +m3e +n3e
and Cx−1
0 ||x1

rotations in this step.
Interval tj ≤ t ≤ tf :

33

Note, wi′ (tj )(vj ) = [ 21 , 1]. Because F preserves the infix ordering of vertices, all
of A is mapped to the left of position [ 12 , 1], meaning either internal or suspended
from [ 21 , 43 ]. Thus, none of A is mapped to the right spine of the tree. Note,
l

m1 + m2 + m3 − m2e − m3e vertices in A are internal at tj . Because wi′ (tf )([0, 12 ]) =
p

[0, 1], all of the vertices [0, 12 ], 0 ≤ p ≤ l−1, in A will eventually need to be mapped
p

to the right spine. Say that s of the vertices [0, 21 ], 0 ≤ p ≤ l − 1 are internal
at time tj . Then, l − s of these vertices are external and thus mapped to the left
spine at tj . Thus, we must increment Cx0 by l − s to move these vertices from the
left spine to the right spine. Note, s ≤ m1 + m2 + m3 − m2e − m3e ≤ m1 + m2 + m3 .
We know CI (tj ) = m1 + n1 + m2 + n2 + m3 + n3 − m2e − n2e − m3e − n3e while
CI (tf ) = 0. Making the remainder of A ∪ B internal requires incrementing Cx1 by
m1 + n1 + m2 + n2 + m3 + n3 − m2e − n2e − m3e − n3e .
In total, this step requires us to increment Cx1 by m1 + n1 + m2 + n2 + m3 +
n3 − m2e − n2e − m3e − n3e and Cx0 by l − s, for a total of m1 + n1 + m2 + n2 +
m3 + n3 − m2e − n2e − m3e − n3e + l − s rotations in this step.
Total rotations:
′
Between all these intervals, |wk−l
| ≥ (k + 2m1 ) + (2k + m2 + m2e + n2 + n2e +

1 −m1 −n1 ) + (k −m1 −m2 + m2e + n3 + m3e + n3e ) + (m1 + n1 + m2 + n2 + m3 + n3 −
m2e − n2e − m3e − n3e + l − s) = 4k + 1 + l + m1 + 2n2 + m2e + 2n3 + m2 + m3 − s ≥
4k+1+l+(m1 +m2 +m3 −s) ≥ 4k+l+1 = 3k+(k−l)+2l+1 > 3k+(k−l)+1+C ≥
′
′
3k + (k − l) + 1 + c = |wk−l
| + c ≥ |wk−l
|. This is a contradiction, so vj could not

have been internal at any point where va was made internal. Thus, none of the
′
vertices in B are internal at any time when va is made internal in wk−l
.



Lemma. 4.17 If, in wi′ , k − l ≤ i ≤ k, the final time where vertex vb is made
internal must occur before the first time the vertex va is made internal and wi (t)
makes vb internal, then k ≤ t ≤ k + C + 2.
34

Proof. Assume that in wi′ , k − l ≤ i ≤ k, the final time where vertex vb is made
internal must occur before the first time the vertex va is made internal and wi (t)
makes vb internal. We examine the limitations this imposes on t.
Time t is greater than k − 1:
k

Note, wi′ (0)(vb ) = [ 2 2−1
k , 1], meaning db (0) = k − 1. If vb is made internal at
time t, db (t − 1) = 0. As vb is initially mapped to the right of the pivot, db can
be reduced with either x−1
or x−1
rotations. At least k − 1 such rotations are
0
1
required to reduce db to zero. Then, a single x−1
1 rotation can be used to make
vb internal. Thus, we can see it takes a minimum of k rotations before vb can be
made internal, meaning t > k − 1.
Time t is less than k + C + 3:
Suppose that t > k + C + 2. Thus, the final time vb is made internal in wi′
also occurs after time k + C + 2. By our assumption, the final time vb is made
internal in wi′ must occur before the first time va is made internal. We look at
times t0 = 0, tb , ta , and tf = |wi′ | where tb is the final time vb is made internal
and ta is the final time va is made internal. By our assumption, tb < ta . Most
of these times are clearly distinct because the action of F on the tree is bijective
and wi′ (t0 )([ 21 , 34 ]) = wi′ (ta )(va ) = wi′ (tb )(vb ) = [ 21 , 43 ]. Time tf must be distinct
from the others because it is certainly not t0 as vertices are made internal in wi′
and because va and vb are mapped approximately k from the pivot at tf . Thus,
t0 < tb < ta < tf . We will look at the intervals between these times and see the
impact each has on |wi′ |.
Interval t0 ≤ t ≤ tb :
During this time interval, we must ensure db (tb −1) = 0 so that vb can be made
internal at tb itself. Vertex va is not made internal during this period. Additionally,
some of the vertices in A and B may be internal at tb , say m1 of the vertices in A
and n1 of the vertices in B.

35

Note that all of this takes at least k + C + 3 rotations as the final time that
vb is made internal must occur at some point after time k + C + 2.
Interval tb < t ≤ ta :
Because wi′ (tb )(vb ) = [ 21 , 34 ] and F preserves the infix ordering of vertices,
wi′ (tb ) maps A ∪ B to the left of the pivot. Thus, CR (tb ) = 0. We also know that
CI (tb ) = m1 +n1 , so CL (tb ) = 2k−1−(m1 +n1 ) and da (tb ) ≥ 2k−m1 −n1 . Because
wi′ (ta − 1)(va ) = [ 12 , 1], da (ta − 1) = 0. The intervening vertices are mapped to
the left of the pivot, so reducing da can only be accomplished by moving vertices
to the right spine of the tree with x0 rotations and we must increment Cx0 by at
least 2k − m1 − n1 .
by 1.
At ta , a single x−1
1 rotation makes va internal, so we increment Cx−1
1
It is possible some of the vertices in A ∪ B that were internal at tb are external
at ta . Additionally, some of these vertices which were external at tb may be internal
at ta . Say that by time ta , m2 vertices in A are internal that were external at tb
and n2 vertices in B are internal that were external at tb . We must increment Cx−1
1
by m2 + n2 to accomplish this change. Of the m1 vertices in A that were internal
at tb , say m2e are external at ta , and of the n1 vertices in B that were internal at
tb , n2e are external at ta . We must increment Cx1 by m2e + n2e to accomplish this
change. In total then, CI (tb ) = (m1 + m2 − m2e ) + (n1 + n2 − n2e ).
by
In total, this interval requires us to increment Cx0 by 2k − m1 − n1 , Cx−1
1
m2 +n2 +1, and Cx1 by m2e +n2e for a total of 2k +1−m1 −n1 +m2 +n2 +m2e +n2e
rotations in this interval.
Interval ta < t ≤ tf :
Note, wi′ (ta )(va ) = [ 12 , 43 ]. Because F preserves the infix ordering of vertices,
this means all of A ∪ B is mapped to the right of position [ 21 , 43 ]. Thus they
must be on the right side of the tree, meaning CL (ta ) = 0. We know that CI (ta ) =
m1 + m2 + n1 + n2 −m2e −n2e , so CR (ta ) = 2k −1 −(m1 + m2 + n1 + n2 −m2e −n2e ).
Note that CI (tf ) = 0 and wi′ (tf )([0, 12

k−i

]) = [0, 1], the root of the tree. Thus, we

must have CL (tf ) = i and CR (tf ) = 2k − 1 − i.

36

Bringing CI (tf ) to 0 requires all of A ∪ B to be internal. Because CI (tb ) =
m1 + m2 + n1 + n2 − m2e − n2e , it will take at least that many x1 rotations to make
vertices external, incrementing Cx1 by m1 + m2 + n1 + n2 − m2e − n2e .
Nothing we have done yet increases CL , which can only be done with x−1
0
by i.
rotations. Bringing CL from 0 to i requires us to increment Cx−1
0
In total, this interval requires us to increment Cx1 by m1 + m2 + n1 + n2 −
by i for a total of m1 + m2 + n1 + n2 − m2e − n2e + i rotations
m2e − n2e and Cx−1
0
in this interval.
Total Rotations:
Between all these steps we have established that |wi′ | ≥ (k + C + 3) + (2k +
1 − m1 − n1 + m2 + n2 + m2e + n2e ) + (m1 + m2 + n1 + n2 − m2e − n2e + i) =
3k + 4 + i + C + 2m2 + 2n2 > 3k + i + 1 + C ≥ 3k + i + 1 + c = |wi′ | + c ≥ |wi′ |.
This is a contradiction, so t < k + C + 3.
Conclusion:
Now, we have shown that t ≥ k and t ≤ k + C + 2, so k ≤ t ≤ k + C + 2 and
the lemma holds.



Lemma. 4.18 If, in wi′ , k − l ≤ i ≤ k, the following two conditions hold:
(1) The final time where vertex vb is made internal must occur before the first
time the vertex va is made internal,
(2) None of the vertices in B are internal at any time when va is made internal,
then we cannot reduce da to M − 1 before time 3k − M in wi′ .
Proof. Assume that in wi′ , k − l ≤ i ≤ k, conditions (1) and (2) hold. Suppose, for
contradiction, there is a first time tc < 3k − M where da is M − 1 in wi′ . We will
consider several additional times in wi′ : t0 = 0, tf = |wi′ |, ta which is the first time
va is made internal in wi′ , and tb which is the final time vb is made internal in wi′ . By
condition (1), tb < ta . Most of these times are clearly distinct because the action
of F on the tree is bijective and wi′ (t0 )([ 21 , 43 ]) = wi′ (ta )(va ) = wi′ (tb )(vb ) = [ 21 , 43 ].
Time tf must be distinct from the others because it is certainly not t0 as vertices
37

are made internal in wi′ and because va and vb are mapped approximately k from
the pivot at tf . So t0 < tb < ta < tf .
We can now consider tc in this ordering. Obviously, tc < ta as da is initially
greater than M − 1 and va cannot be made internal before the first time da is
reduced to M − 1. We briefly show another restriction on tc .
Claim. Time tc > tb
Proof. Suppose tc < tb . Then by time tc we must reduce da to M − 1 and by
time tb − 1 we must reduce db to 0. We know that initially, db = k − 1 and
p

da = k + 1. At time t0 , the vertices [0, 21 ], 0 ≤ p ≤ k − 1, are mapped to the
left of [ 21 , 1] and the only way to move them to reduce da is to use x0 rotations to
move vertices to the right side of the tree. Note, k − (M − 1) such x0 rotations are
q

required. Reducing db requires moving the vertices [ 2 2−1
q , 1], 1 ≤ q ≤ k − 1, which
are mapped on the right side of the tree at time t0 , off of the right spine. This
−1
can be done with either x−1
0 or x1 rotations and (k − 1) of these are required.

Because we use different types of rotations to reduce da and db , reducing both
of these will take (k − (M − 1)) + (k − 1) = 2k − M rotations. This means
tb ≥ 2k − M > k + C + 2 ≥ tb as k > 1000C = 1000max(c, M) and Condition 2
of this Lemma requires tb ≤ k + C + 2. This is a contradiction, so tc > tb .



Thus we can see that t0 < tb < tc < ta < tf . We will look at each of the
intervals given by this partition and consider the number of rotations required
during each one to complete wi′ .
Interval t0 ≤ t ≤ tb :
At time t0 , all of the vertices in B are mapped at or to the right of the pivot.
We know CI (t0 ) = 0 so CR (t0 ) = k − 1. Thus, db (t0 ) = k − 1 initially. Because
vb is made internal at tb , db (tb − 1) = 0. Because the intervening vertices are
mapped to the right spine of the tree, we can reduce db using either x−1
0 rotations
to move them to the left spine or x−1
rotations to make them internal. It will
1
−1 by
take a combination of k − 1 such rotations, requiring us to increment Cx−1
0 ||x1

k − 1. We will say that at time tb , n1 of the vertices in B are internal.
38

It is possible that at tb , some of the vertices in A are internal, say m1 in total.
It will take at least one x−1
1 rotation to make each one internal, requiring us to
by m1 .
increment Cx−1
1
Additionally, at time tb itself, it will take a single x−1
rotation to make vb
1
by 1.
internal, requiring us to increment Cx−1
1
−1 by at least k − 1 and C −1
In total, this step requires us to increment Cx−1
x1
0 ||x1

by m1 + 1, for a total of k + m1 rotations in this interval.
Interval tb < t ≤ tc :
We know CI (tb ) = m1 + n1 . Because wi′ (tb )(vb ) = [ 21 , 43 ] and F preserves
the infix ordering of vertices, wi′ (tb ) maps A ∪ B to the left of the pivot and to
the right of va . Thus, CR (tb ) = 0 meaning CL (tb ) = 2k − 1 − m1 − n1 and
da (tb ) = 2k − 1 − m1 − n1 . We will need to make da (tc ) = M − 1 by the definition
of tc . Because the intervening vertices are to the left of the pivot on the left spine
of the tree, the only way to decrease da is to move them from the left side of
the tree to the right side using x0 rotations. Thus, we must increment Cx0 by
2k − 1 − m1 − n1 − (M − 1).
It is possible that during this interval, we may make some of the vertices in
B that were internal at time tb external by time tc . We may also make some of
these vertices that were external at tb internal by tc . Of the n1 vertices of B that
were internal at tb , we will say that n2e of these are external by tb , and n2 of the
external vertices are made internal by tb . In order to accomplish this, we must
by n2 and Cx1 by n2e .
increment Cx−1
1
In total, this step requires us to increment Cx0 by 2k − 1 − m1 − n1 − (M − 1),
by n2 , and Cx1 by n2e for a total of 2k − 1 − m1 − n1 − (M − 1) + n2 + n2e
Cx−1
1
rotations in this interval.
A Note:
Between these first two time intervals, we require a total of (k + m1 ) + (2k −
1 − m1 − n1 − (M − 1) + n2 − n2e ) = 3k − M − n1 + n2 + n2e rotations. Recall
that tc < 3k − M by our base assumption, so −n1 + n2 + n2e < 0. This means

39

n1 − n2e > n2 ≥ 0 so n1 > n2e . This means that at time tc , at least one vertex of
B will be internal. Call this vertex vc .
Interval tc < t ≤ ta :
At time ta , none of the vertices in B may be internal because condition (2)
holds. Because vc is internal at tc , it will be necessary to make vc external again
before ta . Note, tc is the first time da is M − 1, so we know that wi′ (tc )(va ) is to
the left of the pivot as it begins to the left of the pivot and moving it to the right
would require us to reduce da to 0. No vertices have changed between the internal
and external sets to the left of the pivot at this time as that could only occur if
da had been less than M − 1 prior to this. Thus, less than M of the vertices in
A can be to the left of the pivot at tc . Because F preserves the infix ordering of
vertices, the remaining vertices in A are mapped at or to the right of this position
and all of the vertices in B must be mapped to the right of these on the tree. We
must at least map the leftmost vertex in B to the pivot or underneath the pivot
if it was internal before we can make vc external.
Because da (tc ) = M − 1 and no more than 2C of the vertices in A can be
internal at tc by Lemma 4.14, at least k − (M − 1) − 2C of these vertices are
mapped to the right spine of the tree at or to the right of the pivot. Before vc can
be made external, these vertices must be brought to the left of the pivot. This can
be accomplished with x−1
0 rotations to move them to the left spine. At most 2C
of these vertices can be internal, so the remaining vertices cannot be dealt with
using x−1
1 rotations to make them internal. Thus, it will be necessary to increment
Cx−1
by at least k − (M − 1) − 2C.
0
Once vertex [ 21 , 1] has been mapped to either the pivot or to a position below
the pivot if it was internal, it is possible that we are able to make vc external
again. We next concentrate on making va internal. Because [ 12 , 1] is now either at
or to the left of position [ 21 , 1] and F preserves the infix ordering of vertices, all of
the vertices in A are now mapped to the left of the pivot. At most 2C of them
may be internal at this time, so at least k − 1 − 2C of these vertices on the left

40

spine must be moved from it before da can be reduced to 0. This can only be done
using x0 rotations. Thus, we must increment Cx0 by at least k + 1 − 2C.
Then at time ta itself, it will take a single x−1
1 rotation to make va internal,
making us increment Cx−1
by 1.
1
In total, this step requires us to increment Cx−1
by k − (M − 1) − 2C, Cx0 by
0
k + 1 − 2C, and Cx−1
by 1 for a total of 2k + 3 − M − 4C rotations in this step.
1
Interval ta < t ≤ tf :
Because wi′ (ta )(va ) = [ 21 , 34 ] and F preserves the infix ordering of vertices, all
p

of the vertices in A of the form [0, 21 ], k − i ≤ p ≤ k − 1, are mapped at or to the
right of the pivot. By tf , vertex [0, 12

k−i

] is mapped to the apex of the tree. We

must also ensure CI (tf ) = 0.
p

All of the vertices [0, 12 ], k − i ≤ p ≤ k − 1, are either internal at time ta or are
external and mapped to the right spine of the tree and must be mapped to the left
of the image of [0, 21

k−i

]. We do not know how many of these vertices are internal,

but any internal ones can be made external with a single x1 rotation. Any external
vertices can be moved to the left of the pivot with an x−1
0 rotation. Making more
of them internal would require additional rotations to make them external before
leaving them exactly where they were before, so using x−1
rotations is not an
1
option. Thus, we would need to increment Cx−1
by at least (k−1)−(i−1) = k−i.
0 ||x1
Recall that by time tc , we had n1 +n2 +n2e vertices of B internal. We have not
yet accounted for making these external, but they must be made external by tf .
Each one can be made external with a single x1 rotation, requiring us to increment
Cx1 by n1 + n2 − n2e .
In total, this step requires us to increment Cx−1
by k − i and Cx1 by n1 +
0 ||x1
n2 − n2e , for a total of k − i + n1 + n2 − n2e rotations in this step.
Total Rotations:
In total then, this tells us |wi′ | ≥ (k + m1 ) + (2k − 1 − m1 − n1 − (M − 1) + n2 +
n2e ) + (2k + 3 − M − 4C) + (k − i + n1 + n2 − n2e ) = 6k + 3 + 2n2 − 2M − 4C − i =
3k + i + 1 + C + (k − i) + (k + 2n2 ) + (k − 2M − 5C − 1) + 1. Note (k + n2 ) ≥ 0 as

41

n2 ≥ 0, (k − 2M − 5C − 1) ≥ 0 as k > 1000max(M, C) and k ≥ i. So, this means
|wi′ | > 3k + i + 1 + C = |wi′ | + C ≥ |wi′ | + c ≥ |wi′ | which is a contradiction.



Lemma. 4.19 If, in wi′ , k − l ≤ i ≤ k − 1, the following two conditions hold:
(1) The final time vertex vb is made internal occurs before the first time the
vertex va is made internal,
(2) None of the vertices in B are internal at any time when va is made internal,
′
then (1) and (2) hold true in wi+1
, as well.

Proof. Assume that in wi′ , conditions (1) and (2) hold as above.
′
(1) The final time vertex vb is made internal in wi+1
occurs before the
′
first time the vertex va is made internal in wi+1
.
′
Suppose, for contradiction, that condition (1) does not hold in wi+1
. That is,

the first time va is made internal occurs before the final time vb is made internal.
Let tb denote the final time, in wi′ , where vb has been made internal. By condition
(1) of our assumption, at this time in wi′ , vb has just been made internal while va
′
has not been made internal at all. Because wi′ and wi+1
are M fellow travelers and
′
′
for all t ≥ tb , wi′ (t)(vb ) is internal, either wi+1
(t)(vb ) is internal or db (wi+1
(t)) ≤ M

so that vb could be made internal within M rotations.
′
Claim. It is not possible that va was made internal in wi+1
at or before tb .
′
′
Proof. Immediately before va is made internal in wi+1
, da is 0. We know, db (wi+1
(tb )) ≤

M or vb is already internal, meaning at some point prior to tb , db was 0. Either
way, db must have been reduced to at least M prior to tb in wi+1 . At time 0 in
′
wi+1
, db = k − 1 and da = k + 1. Reducing da from k + 1 to 0 requires a total of

at least k + 1 x0 rotations to map the intermediate vertices from the left spine to
the right spine. Reducing db from k − 1 to M requires a combination of k − 1 − M
−1
x−1
1 and x0 rotations. In total, this requires 2k − M rotations to occur before tb .

However, 2k − M > k + C + 2 as k ≥ 1000C where C = max(c, M), meaning this
violates condition (2) of our assumption. Thus, it is impossible to bring va into
the interior set in wi+1 at or before time tb .
42



′
We can now show that in wi+1
, it is not possible to make va internal unless vb

is already internal.
′
Claim. In wi+1
, it is not possible to make va internal unless vb is already internal.

′
Proof. By the previous claim, we cannot make va internal in wi+1
until after time
′
′
tb . At any time t > tb , we know that either vb is internal in wi+1
or db (wi+1
(t)) ≤

M. So, at any time t′ that va might be made internal, at least one of these
′
two conditions hold. If vb is not already internal, then db (wi+1
(t′ )) ≤ M and
′
′
db (wi+1
(t′ )) ≤ M + 1. Because va will be made internal at t′ , da (wi+1
(t′ − 1)) = 0.

Given that F preserves the infix ordering of vertices, we know that at t′ , no more
than M of the vertices in A ∪ B can remain external. This holds because all of
these vertices must be mapped between the positions where va and vb are mapped,
either on the spines of the tree or internal. But then, less than 2C of the vertices
in A are external, violating Lemma 4.14.



′
Thus, we have established that whenever va is made internal in wi+1
, vb is

already internal. There must be at least one time when va is made internal in
′
wi+1
. Our supposition means this could not be the final time vb will be made

internal, so at some point after this, vb must be made external and then internal
again.
Because conditions (1) and (2) hold in wi′ , Lemma 4.18 holds as well and we
cannot reduce da to M − 1 before time 3k − M in wi′ . We also know that wi′ and
′
wi+1
are M fellow travelers and da is initially greater than M − 1 in both words.
′
This means it is not possible to make va internal in wi+1
before time 3k − M.
′
Otherwise, if va was internal in wi+1
before time 3k − M, then at that time in

wi , it must have been possible to make va internal within M steps. It would take
a single x−1
1 rotation to actually make va internal, so reducing da to zero would
have taken at most M − 1 steps, meaning that at this time which was less than
3k − M, da ≤ M − 1 in wi′ , which is a contradiction.
′
Thus, the first time it is possible to make va internal in wi+1
occurs at or after

time 3k −M. Call this time ta . At time ta , vb is internal and will be made external
43

′
and then internal again before the end of wi+1
. Because va has just been made

internal, it is mapped to position [ 21 , 43 ]. Because F preserves the infix ordering of
vertices, all of the vertices in A∪B are mapped at or to the right of the pivot. Each
of these vertices is either internal or external, though we know at most 2C of the
vertices in A may be internal at any time by Lemma 4.14. We will say that n of the
vertices in B are internal at time ta . In order to make vb external while it is already
internal, we must bring it to position [ 21 , 43 ], bringing db to 1. Again, because F
preserves the infix ordering of vertices, we know that at this time, vb is mapped
to the right of all the vertices in A ∪ B. Thus, da ≥ (k − 1 + k) − 2C − n. Because
all of these intervening vertices are mapped to the right of the pivot, reducing da
−1
to 1 can be accomplished with a combination of x−1
0 and x1 rotations. We will
−1 by at least 2k − 1 − 2C − n.
need to increment Cx−1
0 ||x1

Additionally, any vertices that were internal at time ta that were not initially
′
internal must be made external by the end of wi+1
. This includes the n vertices in

B, which were noted to be internal above. Making each of these external requires
a single x1 rotation, requiring us to increment Cx1 by at least n.
This is sufficient to give us a contradiction. We know that at time ta , we have
used at least 3k − M rotations. Adding these to the minimum number of rotations
′
that must follow, we can see that: |wi+1
| ≥ (3k − M) + (2k − 1 − 2C − n) + n =

5k − M − 1 − 2C. Note, k > 1000C where C = max(c, M) and M ≥ 1, so
′
k > M − 3 − 3C. Also, by our choice of i, k ≥ i. So, |wi+1
| ≥ 5k − M − 1 − 2C =
′
′
|+c ≥ |wi+1
|.
3k+2+C+(k−M −3−3C)+(k) > 3k+2+C+i ≥ 3k+2+c+i = |wi+1

This is a contradiction, so va cannot be made internal at all until after the final
′
′
time vb is made internal in wi+1
and condition (1) holds in wi+1
.

(2) None of the vertices in B are internal at any time when va is made
′
internal, in wi+1
.

Suppose not, for contradiction. Note, because our assumed conditions hold,
Lemma 4.18 holds for wi and da (wi′ (t)) > M − 1 for all t < 3k − M. Clearly, va
′
could not be made internal in wi′ before time 3k −M then. Recall that wi′ and wi+1

are M fellow travelers. This also means that it is not possible for va to have been
44

′
made internal in wi+1
prior to time 3k − M. Otherwise, at the time it was made

internal, it would have been possible within M steps in wi′ to make va internal as
well. However, this would have meant da was less than M − 1 at that time in wi′ ,
a contradiction.
Claim. At time 3k − M − 1, none of the vertices in B were internal in wi′ .
Proof. Suppose not, for contradiction. Then at least one vertex in B is internal
in wi′ at 3k − M − 1. By condition (2) of our assumption, we also know that
none of the vertices in B are internal in wi′ at any time when va is made internal.
Because va is internal at the end of wi′ , there must be some time at or after 3k −M
where va was made internal and at this time, no vertices in B would be internal.
Thus, there must be a time between 3k − M and the time where va is finally made
internal in wi′ where a vertex of B could be made external. At this time, all of the
vertices of A are either external on the spine of the tree or internal. By Lemma
4.14, no more than 2C of the vertices in A may be internal, so there would be at
least k − 2C external vertices at this time. Moving these vertices to the right side
of the tree would require k − 2C x0 rotations. Then, after va was made internal,
all of the vertices of A would need to be made external and CL would need to
be brought from 0 to i. This would require at least i total rotations. Thus, this
would require |wi′ | ≥ 3k − M + k − 2C + i = 3k + 1 + C + i + (k − 3C − 1) >
3k + 1 + C + i ≥ 3k + 1 + c + i = |wi′ | + c ≥ |wi′ |, which is impossible. Thus, no
vertices in B could have been internal at time 3k − M − 1.



What’s more, a modification to the above argument shows that at time 3k −
M − 1, wi′ could not have been within

k
2

steps of making a vertex of B internal.

Claim. At time 3k −M −1, in wi′ , it is not possible to make a vertex of B internal
in less than

k
2

rotations.

Proof. Suppose not. Then at 3k − M − 1, at least one vertex of B is mapped
within

k
2

− 1 rotations of the pivot. By the same reasoning as in the previous

claim, there is a time after 3k − M − 1 when va is made internal. At 3k − M − 1,
45

all of the vertices of A are either external on the spine of the tree or internal.
By Lemma 4.14, no more than 2C of the vertices in A may be internal, so there
would be at least k − 2C external vertices at this time. Because at most

k
2

−1

vertices of A can be mapped between the vertices of B and the pivot and 2C may
be internal, at least k −2C − k2 +1 vertices of A are mapped to the left of the pivot.
Because F preserves the infix ordering of vertices, to make va internal, we must
move these vertices to the right side of the tree using k − 2C − k2 + 1 x0 rotations.
Then, after va was made internal, all of the vertices of A would need to be made
external and CL would need to be brought from 0 to i. This would require at least
i total rotations. Thus, this would require |wi′ | ≥ 3k − M + k − 2C −

k
2

+1+i =

3k + 1 + C + i + ( k2 − 3C − 1) > 3k + 1 + C + i ≥ 3k + 1 + c + i = |wi′ | + c ≥ |wi′ |,
which is impossible. Thus the lemma holds.



′
Likewise, no vertices in B in wi+1
could have been internal at time 3k − M −

1. Because these words are M fellow travelers, if a vertex in B was internal in
′
wi+1
(3k−M −1), then that vertex would either need to be internal in wi′ (3k−M −1)

or it would need to be possible to make it internal within M rotations in wi′ at
this time. However, neither option is possible.
This leads directly to a contradiction. This would require us to make a vertex
in B internal at or after time 3k−M, then make va internal, and then rebalance the
′
tree. As in our first claim above, this would require |wi+1
| ≥ 3k −M + k −2C + i =
′
′
| + c ≥ |wi+1
|
3k + 2 + C + i + (k − 3C − 2) > 3k + 2 + C + i ≥ 3k + 2 + c + i = |wi+1

and the lemma holds.



4.4 The Claim for fk :
Claim. In the sole accepted representative word for fk , the final time vertex vb is
made internal occurs before the final time the vertex va is made internal.
′
Proof. We begin with wk−l
, the accepted representative for wk−l . By Lemma 4.14,
′
we know that in wk−l
, the final time where vertex vb is made internal must occur

before the first time the vertex va is made internal. Lemma 4.15 says that none of
46

′
the vertices in B are internal at any time when va is made internal in wk−l
. Note,
′
this means that wk−l
fulfills conditions (1) and (2) of Lemma 4.18.

Suppose that in wi′ , the accepted representative for wi k − l ≤ i ≤ k − 1, the
following two conditions hold:
(1) The final time vertex vb is made internal occurs before the first time the
vertex va is made internal,
q

(2) None of the vertices [ 2 2−1
q , 1], 1 ≤ q ≤ k − 1 are internal at any time when
va is made internal,
′
Then by Lemma 4.18, in wi+1
, the accepted representative for wi+1 , these two

conditions hold as well and our induction is complete. Thus, in wk′ , condition (1)
will hold as well, so the final time vertex vb is made internal occurs before the first
time the vertex va is made internal. But wk′ is the accepted representative for wk
and wk = fk so our claim is complete.



4.5 The Path for gk :
(k+1) −1 −(2k−1) −1 (k−1)
x1 x0
x1 x0
.

We now look at the prefixes of gk = x0

(k+1) −1 −(2k−1) −1 −i
x1 x0
x1 x0

Definition 4.20. ui = x0

where 0 ≤ i ≤ k − 1

Take note that ui = gk (3k + 2 + i) is the 3k + 2 + i prefix of gk . Thus,
k

k

uk−1 = gk . In each ui , vertices [0, 12 ] and [ 2 2−1
k , 1] are in the interior set at the
k

end of the word. In particular, vertex [ 2 2−1
k , 1] is made interior at time k + 2 by
(k+1) −1
x1

prefix ui (k + 2) = x0

k

and vertex [0, 12 ] is made interior at time 3k + 2 with

(k+1) −1 −(2k−1) −1
x1 x0
x1 .

prefix ui (3k + 2) = x0

Again, using Fordham’s method, we can compute that any minimal length
−1
representative of ui in the letters {x0 , x1 , x−1
0 , x1 } has length 3k + 2 + i. That is

to say, |ui | = 3k + 2 + i. By our assumption before, each element of F has a single
representative in L whose length is at most c greater than minimal. We use u′i to
denote the representative in L for ui . Note that |u′i | ≤ |ui | + c.
47

We will explore the path for gk using six lemmas as the basis for an inductive
argument to show va must be made internal before vb in the accepted representative
for gk .
Lemma 4.21. In u′i , (k − 1) − (C + 1) ≤ i ≤ k − 1, there can be no more than
2C times where any of the vertices in A are made internal.
The following pair of lemmas give the base for an inductive argument.
Lemma 4.22. In u′(k−1)−(C+1) , no more than C of the vertices in B are internal
at the final time va is made internal.
Lemma 4.23. In u′(k−1)−(C+1) , the final time va is made internal occurs before the
first time vb is made internal.
Lemma 4.24. If in u′i , (k − 1) − (C + 1) ≤ i ≤ k − 2, the following two conditions
hold:
(1) The final time va is made internal occurs before the first time vb is made
internal,
(2) No more than C of the vertices in B are internal at the final time va is
made internal,
then, da (u′i (t)) > M − 1 if t > k + M + 2C + 2.
The following two lemmas give the inductive step for our argument.
Lemma 4.25. If in u′i , (k − 1) − (C + 1) ≤ i ≤ k − 2, the following two conditions
hold:
(1) The final time va is made internal occurs before the first time vb is made
internal,
(2) No more than C of the vertices in B are internal at the final time va is
made internal,
then, in u′i+1 , (1) holds as well.
Lemma 4.26. If in u′i , (k − 1) − (C + 1) ≤ i ≤ k − 2, the following two conditions
hold:
48

(1) The final time va is made internal occurs before the first time vb is made
internal,
(2) No more than C of the vertices in B are internal at the final time va is
made internal,
then, in u′i+1 , (2) holds as well.
We now prove each of these lemmas and then complete the inductive argument
they establish.
Lemma. 4.21 In u′i , (k − 1) − (C + 1) ≤ i ≤ k − 1, there can be no more than
2C times where any of the vertices in A are made internal.
Proof. Assume, for contradiction, that in u′i , there are T ≥ 2C + 1 times where
any of the vertices in A are made internal.
We look at times t0 , ta , tb , and tf . Define t0 = 0 and tf = |u′i |. Define ta as the
final time that vertex va is made internal in u′i and tb as the final time that vertex vb
is made internal in u′i . Most of these times are clearly distinct because the action
of F on the tree is bijective and (u′i (t0 ))([ 12 , 43 ]) = (u′i (ta ))(va ) = (u′i (tb ))(vb ) =
(u′i (tf ))([ 12

k−i 1 k−i−1
,2
])

= [ 21 , 43 ]. Time tf must be distinct from the others because

it is certainly not t0 as vertices are made internal in wi′ and because va and vb are
mapped approximately k from the pivot at tf .
One of the following two orderings are true: t0 < ta < tb < tf or t0 < tb <
ta < tf . We consider the impact each has on |u′i |.
Ordering t0 < ta < tb < tf
We begin with the time intervals given by t0 < ta < tb < tf and account for
the total rotations needed in each interval.
Interval t0 ≤ t ≤ ta :
At t0 , all of A is mapped to the left of the pivot and to the right of va . Thus,
CL (t0 ) = k and da (t0 ) = k + 1. Note, da (ta − 1) = 0. Because these vertices are
mapped to the left of the pivot, the only way to decrease da is with x0 rotations
so we must increment Cx0 by at least k + 1.
49

At ta , a single x−1
by 1.
1 rotation makes va internal, so we increment Cx−1
1
Additionally, some of the vertices in A and B may be internal at ta , say m1
of the vertices in A and n1 of the vertices in B. Because CI (t0 ) = 0, it will take a
single x−1
1 rotation to make each of these internal, requiring us to increment Cx−1
1
by another m1 + n1 this step.
In total, this interval requires us to increment Cx0 by k + 1 and Cx−1
by
1
m1 + n1 + 1 for a total of k + m1 + n1 + 2 rotations in this interval.
Interval ta < t ≤ tb :
Because u′i (ta )(va ) = [ 21 , 43 ] and F preserves the infix ordering of vertices, u′i (ta )
maps A ∪ B at or to the right of the pivot. Thus, CL (ta ) = 0. We also know that
CI (ta ) = m1 + n1 , so CR (ta ) = 2k − 1 − (m1 + n1 ) and db (ta ) ≥ 2k − m1 − n1 − 1.
These vertices are mapped to the right spine, so reducing db can be accomplished
either by moving them to the left spine of the tree with x−1
0 rotations or making
1
′
them internal with x−1
1 rotations. Because ui (tb − 1)(vb ) = [ 2 , 1], db (tb − 1) = 0
−1 by at least 2k − m1 − n1 − 1.
and we must increment Cx−1
0 ||x1

At tb , a single x−1
by 1.
1 rotation makes vb internal, so we increment Cx−1
1
It is possible some of the vertices in A ∪ B that were internal at ta are external
at tb . Additionally, some of these vertices which were external at ta may be internal
at tb . We may have already accounted for making the new vertices internal. Say
that by time tb , m2 vertices in A are internal that were external at ta and n2
vertices in B are internal that were external at ta . Of the m1 vertices in A that
were internal at ta , say m2e are external at tb , and of the n1 vertices in B that
were internal at ta , n2e are external at tb . We must increment Cx1 by m2e + n2e to
accomplish this change. In total then, CI (tb ) = (m1 + m2 − m2e ) + (n1 + n2 − n2e ).
−1 by 2k − m1 − n1 − 1,
In total, this interval requires us to increment Cx−1
0 ||x1

by 1, and Cx1 by m2e + n2e for a total of 2k − m1 − n1 + m2e + n2e rotations
Cx−1
1
in this interval.
Interval tb < t ≤ tf :

50

Note, u′i (tb )(vb ) = [ 12 , 43 ]. Because F preserves the infix ordering of vertices, all
of A ∪ B is mapped to the left of position [ 21 , 34 ]. Thus CR (tb ) = 0. We know that
CI (tb ) = m1 + m2 + n1 + n2 − m2e − n2e , so CL (tb ) = 2k − 1 − (m1 + m2 + n1 +
k−1−i

n2 − m2e − n2e ). Note that CI (tf ) = 0 and u′i (tf )([ 2 2k−1−i−1 , 1]) = [0, 1], the root of
the tree. Thus, we must have CL (tf ) = 2k − 1 − i and CR (tf ) = i.
Bringing CI (tf ) to 0 requires all of A ∪ B to be internal. Because CI (tb ) =
m1 + m2 + n1 + n2 − m2e − n2e , it will take at least that many x1 rotations to make
vertices external, incrementing Cx1 by m1 + m2 + n1 + n2 − m2e − n2e .
We require additional rotations related to these vertices we have made external. Any time a vertex is made external, it is mapped from the interior of the tree
q

to the pivot. This is fine for the vertices [ 2 2−1
q , 1], k − 2 − i ≤ q ≤ k − 1, because
|u′i (tf )| maps them to the right spine of the tree. However, all of the vertices in
q

′
Aand [ 2 2−1
q , 1], 1 ≤ q ≤ k − 1 − i must be mapped to the left spine in ui (tf ).

Mapping a vertex from the right spine of the tree to the left spine can only be
−1
accomplished by an x−1
0 rotation and we have accounted for no x0 rotations in

this step thus far. All of the m1 + m2 − m2e vertices in A that are internal at tb
will need to be brought to the left side of the tree. This requires us to increment
Cx−1
by m1 + m2 − m2e .
0
Recall, CR (tb ) = 0 and CR (tf ) = i. Making vertices from A ∪ B external
increases CR by 1 and we have accounted for making all of A ∪ B external with
m1 + m2 + n1 + n2 − m2e − n2e rotations. However, any vertices in A must be
moved to the left side of the tree after they have been made external as we noted
above, and moving a vertex in A ∪ B from the right spine to the left decreases
CR by 1 and increases CL by 1. Thus, we have accounted for a net increase in CR
of at most n1 + n2 − n2e in this step. Increasing CR further would require taking
vertices in B from the left spine of the tree and bringing them to the right spine
of the tree using Cx0 rotations. If n1 + n2 − n2e < i, we must increment Cx0 by at
least i − (n1 + n2 − n2e ) as this is the only way to ensure that CR (tf ) = i.
In total, this interval requires us to increment Cx1 by m1 +m2 +n1 +n2 −m2e −
n2e and Cx−1
by m1 + m2 − m2e for a total of 2m1 + 2m2 − 2m2e + n1 + n2 − n2e
0
51

rotations in this interval. If n1 + n2 − n2e < i, we must increment Cx0 by an
additional i − (n1 + n2 − n2e ).
Additional Accounting:
In the above, we have accounted for m1 + m2 instances where a vertex in A
is made internal. Each of these times occurs when one of the vertices is made
internal during one of our time intervals and is not external at the end of it. We
have also accounted for all instances where these were eventually made external
and no other instances where a vertex in A was made external. There may be times
t when a vertex a ∈ A is made internal where both t and the next time t′ when a
is made external occur in the same time interval. Each such pair contributes both
an x−1
1 and an x1 rotation that we have not yet accounted for, so say there are
by m3 and Cx1 by m3 for a total of 2m3
m3 pairs, requiring us to increment Cx−1
1
rotations in this step. Note, m1 + m2 + m3 = T ≥ 2C + 1.
Total Rotations:
In total, we have established that |u′i | ≥ (k + m1 + n1 + 2) + (2k − m1 − n1 +
m2e + n2e ) + (2m1 + 2m2 − 2m2e + n1 + n2 − n2e ) + (2m3 ) = 3k + 2m1 + 2m2 +
2m3 − m2e + n1 + n2 + 2 plus an additional i − (n1 + n2 − n2e ) if n1 + n2 − n2e < i.
This gives us two cases to consider.
First of all, if n1 + n2 − n2e < i, then |u′i | ≥ 3k + 2m1 + 2m2 + 2m3 − m2e +
n1 + n2 + 2 + (i − (n1 + n2 − n2e )) = 3k + i + 2 + 2m1 + 2m2 + 2m3 − m2e + n2e ).
Note that m1 + m2 + m3 = T ≥ 2C + 1, m1 + m2 + m3 ≥ m2e , and n2e ≥ 0.
Thus |u′i | ≥ 3k + i + 2 + (m1 + m2 + m3 ) + ((m1 + m2 + m3 ) − m2e ) + n2e ) ≥
3k + i + 2 + 2C + 1 > 3k + i + 2 + C.
Otherwise, if n1 + n2 − n2e ≥ i, then |u′i | ≥ 3k + 2m1 + 2m2 + 2m3 − m2e + n1 +
n2 + 2. In addition to what was noted above, note that n1 + n2 ≥ n1 + n2 −n2e ≥ i.
Thus, |u′i | ≥ 3k + (m1 + m2 + m3 ) + ((m1 + m2 + m3 ) − m2e ) + (n1 + n2 ) + 2 ≥
3k + i + 2 + (2C + 1) > 3k + i + 2 + C.

52

In either case, we see that |u′i | > 3k + 2 + i+ C ≥ 3k + 2 + i+ c = |u′i | + c ≥ |u′i |.
This is a contradiction.
Ordering t0 < tb < ta < tf
We next examine the time intervals given by t0 < tb < ta < tf and account
for the total rotations needed in each interval.
Interval t0 ≤ t ≤ tb :
At t0 , all of B is mapped at or to the right of the pivot and to the left of vb .
Thus, CR (t0 ) = k − 1 and db (t0 ) = k − 1. We must have db (tb − 1) = 0. Decreasing
db requires us to either map the intervening vertices to the left of the pivot with
−1
x−1
0 rotations or to make them internal with x1 rotations. Thus, we increment
−1 by at least k − 1. Let n1 be the number of vertices in B that are internal
Cx−1
0 ||x1

at tb .
by 1.
At tb , a single x−1
1 rotation makes vb internal, so we increment Cx−1
1
Additionally, it is possible that some subset of A is internal at tb . At t0 , A is
mapped to the left spine. The only way to bring a vertex from the left spine to
the pivot is an x0 rotation. No x0 rotations were yet required in this interval, so
each vertex in A that is internal at tb requires an x0 rotation to reach the pivot
and an x−1
1 rotation to make it internal. Say m1 vertices in A are internal at tb ,
requiring us to increment Cx0 by m1 and Cx−1
by m1 .
1
−1 by k − 1, Cx by m1 ,
In total, this interval requires us to increment Cx−1
0
0 ||x1

by m1 + 1, for a total of k + 2m1 rotations in this step.
and Cx−1
1
Interval tb < t ≤ ta :
Because u′i (tb )(vb ) = [ 21 , 43 ] and F preserves the infix ordering of vertices, u′i (tb )
maps A ∪ B to the left of the pivot. This is the final time vb is made internal,
so none of the vertices in A ∪ B can be suspended from it. Thus, u′i (tb ) maps
A ∪ B to the left side of the tree with va mapped to the left of where all these
vertices are mapped. This means CR (tb ) = 0 and we know CI (tb ) = m1 + n1 , so
CL (tb ) = 2k − 1 − (m1 + n1 ) and da (tb ) ≥ 2k − 1 − (m1 + n1 ) + 1 = 2k − m1 − n1 .
We must have da (ta − 1) = 0, so the vertices in A ∪ B mapped to the left of the
53

pivot must be mapped to the right side of the tree with x0 rotations. Thus, Cx0
must be incremented by 2k − m1 − n1 .
At ta , a single x−1
by 1.
1 rotation makes va internal, so we increment Cx−1
1
It is possible some of the vertices in A ∪ B that were internal at tb are external
at ta . Additionally, some of these vertices which were external at tb may be internal
at ta . Making an external vertex internal takes an x−1
1 rotation and making an
internal vertex external takes an x1 rotation. Say that at ta , m2 vertices in A
and n2 vertices in B are internal that were external at tb . Of the m1 vertices in
A that were internal at tb , say m2e were external at ta , and of the n1 vertices
in B that were internal at tb , n2e are external at ta . We must increment Cx−1
1
by m2 + n2 and Cx1 by m2e + n2e to accomplish this change. In total then,
CI (ta ) = (m1 + m2 − m2e ) + (n1 + n2 − n2e ).
by
In total, this interval requires us to increment Cx0 by 2k − m1 − n1 , Cx−1
1
m2 +n2 +1, and Cx1 by m2e +n2e , for a total of 2k+m2 +m2e +n2 +n2e +1−m1 −n1
rotations in this step.
Interval ta < t ≤ tf :
Note, u′i (ta )(va ) = [ 21 , 43 ]. Because F preserves the infix ordering of vertices,
all of A ∪ B is mapped to the right of position [ 12 , 43 ]. Thus CL (ta ) = 0. We know
the CI (ta ) = m1 + m2 + n1 + n2 − m2e − n2e , so CR (tb ) = 2k − 1 − (m1 + m2 +
k−1−i

n1 + n2 − m2e − n2e ). Note that CI (tf ) = 0 and u′i (tf )([ 2 2k−1−i−1 , 1]) = [0, 1], the
root of the tree. Thus, we must have CL (tf ) = 2k − 1 − i and CR (tf ) = i.
Bringing CI (tf ) to 0 requires all of A ∪ B to be internal. Because CI (ta ) =
m1 + m2 + n1 + n2 − m2e − n2e , it will take at least that many x1 rotations to make
vertices external, incrementing Cx1 by m1 + m2 + n1 + n2 − m2e − n2e .
The only way to increase CL is using x0 rotations to move vertices from the
right side of the tree to the left side. Because CL (ta ) = 0 and CL (tf ) = i, we must
increment Cx−1
by 2k − 1 − i.
0

54

In total, this step requires us to increment Cx1 by m1 +m2 +n1 +n2 −m2e −n2e
and Cx0 by 2k − 1 − i, for a total of m1 + m2 + n1 + n2 − m2e − n2e + 2k − 1 − i
rotations in this step.
Additional Accounting:
In the above, we have accounted for m1 + m2 instances where a vertex in A is
made internal. Each of these times occurs when one of the vertices is made internal
during one of our time intervals and is not external at the end of it. We have also
accounted for all instances where these were eventually made external and no other
instances where a vertex in A were made external. There may be times t when a
vertex a ∈ A is made internal where both t and the next time t′ when a is made
external occur in the same time interval. Each such pair contributes both an x−1
1
and an x1 rotation that we have not yet accounted for, so say there are m3 pairs,
requiring us to increment Cx−1
by m3 and Cx1 by m3 for a total of 2m3 rotations
1
in this step. Note, m1 + m2 + m3 = T ≥ 2C + 1.
Total rotations:
Between all these steps, we have established that |u′i | ≥ (k + 2m1 ) + (2k + m2 +
m2e +n2 +n2e +1−m1 −n1 )+(m1 +m2 +n1 +n2 −m2e −n2e +2k −1−i)+(2m3 ) =
5k − i + 2(m1 + m2 + m3 ) + 2n2 ≥ 5k − i + 2(m1 + m2 + m3 ). We know i ≤ k and
m1 +m2 +m3 ≥ 2C +1, so |u′i | ≥ 5k−i+2(m1 +m2 +m3 ) ≥ 3k+k+(k−i)+4C +2 =
3k + 2 + k + C + ((k − i) + 3C) > 3k + 2 + i + C ≥ 3k + 2 + i + c = |u′i | + c ≥ |u′i |.
This is a contradiction.
Conclusion
Now, whether tb < ta or ta < tb , we see that the length of u′i must be longer
than the necessary restriction that |u′i | ≤ |u′i | + c demands. Because we have a
contradiction either way, we see that in u′i , there can be no more than 2C times
that any of the vertices in A are made internal. Thus, the lemma holds.



Lemma. 4.22 In u′(k−1)−(C+1) , the final time va is made internal occurs before
the first time vb is made internal.
55

Proof. Assume, for contradiction, the final time va is made internal occurs after
the first time vb is made internal.
We consider the impact this has on |u′(k−1)−(C+1) |. We look at times t0 , ta ,
tb , and tf . Define t0 = 0 and tf = |u′(k−1)−(C+1) |. Define ta as the final time
that va is made internal in u′(k−1)−(C+1) and tb as the first time vb is made internal in u′(k−1)−(C+1) . These times are clearly distinct because the action of F
on the tree is bijective and (u′(k−1)−(C+1) (t0 ))([ 12 , 43 ]) = (u′(k−1)−(C+1) (ta ))(va ) =
l

(u′(k−1)−(C+1) (tb ))(vb ) = (u′(k−1)−(C+1) (tf ))([ 12 , 12

l−1

]) = [ 21 , 34 ].

This means t0 < tb < ta < tf . We consider the impact the intervals of time
defined by this have on |u′(k−1)−(C+1) |.
Interval t0 ≤ t ≤ tb :
At t0 , all of B is mapped to the right of the pivot and to the left of vb . Thus,
CR (t0 ) = k − 1 and db (t0 ) = k − 1. Because these vertices are mapped to the
−1
right of the pivot, we can decrease db with either x−1
0 or x1 rotations. We know
−1 by at least k − 1.
db (tb − 1) = 0, so we must increment Cx−1
0 ||x1

At tb , a single x−1
by 1.
1 rotation makes vb internal, so we increment Cx−1
1
Additionally, some of the vertices in A and B may be internal at tb , say m1
of the vertices in A and n1 of the vertices in B. Because CI (t0 ) = 0, it will take
a single x−1
1 rotation to make each of these internal. We have potentially already
accounted for making vertices in B internal earlier in this interval, however none
of our rotations could have made a vertex in A internal, requiring us to increment
Cx−1
by another m1 in this step.
1
−1 by k − 1 and C −1 by
In total, this interval requires us to increment Cx−1
x1
0 ||x1

m1 + 1 for a total of k + m1 rotations in this interval.
Interval tb < t ≤ ta :
Because u′(k−1)−(C+1) (tb )(vb ) = [ 12 , 43 ] and F preserves the infix ordering of
vertices, u′(k−1)−(C+1) (tb ) maps A ∪ B to the left of the pivot. Thus, CR (tb ) = 0.
We also know that CI (tb ) = m1 + n1 , so CL (tb ) = 2k − 1 − (m1 + n1 ) and da (tb ) ≥
2k − m1 − n1 . These vertices are mapped to the left spine, so reducing da can

56

only be accomplished by moving vertices to the right spine of the tree with x0
rotations. Because u′(k−1)−(C+1) (ta − 1)(va ) = [ 12 , 1], da (ta − 1) = 0 and we must
increment Cx0 by at least 2k − m1 − n1 .
At ta , a single x−1
by 1.
1 rotation makes va internal, so we increment Cx−1
1
It is possible some of the vertices in A ∪ B that were internal at tb are external
at ta . Additionally, some of these vertices which were external at tb may be internal
at ta . Say that at time ta , m2 vertices in A are internal that were external at tb
and n2 vertices in B are internal that were external at tb . We must increment Cx−1
1
by m2 + n2 to accomplish this change. Of the m1 vertices in A that were internal
at tb , say m2e are external at ta , and of the n1 vertices in B that were internal at
tb , n2e are external at ta . We must increment Cx1 by m2e + n2e to accomplish this
change. In total then, CI (ta ) = (m1 + m2 − m2e ) + (n1 + n2 − n2e ).
−1 by 2k−m1 −n1 , C −1 by
In total, this interval requires us to increment Cx−1
x1
0 ||x1

m2 +n2 +1, and Cx1 by m2e +n2e for a total of 2k +1−m1 −n1 +m2 +n2 +m2e +n2e
rotations in this interval.
Interval ta < t ≤ tf :
Note, u′(k−1)−(C+1) (ta )(va ) = [ 21 , 43 ]. Because F preserves the infix ordering of
vertices, this means all of A ∪ B is mapped to the right of position [ 21 , 34 ]. Thus it
must be mapped to the right side of the tree, meaning CL (ta ) = 0. We know that
CI (ta ) = m1 + m2 + n1 + n2 − m2e − n2e , so CR (ta ) = 2k − 1 − (m1 + m2 + n1 +
C+1

n2 − m2e − n2e ). Note that CI (tf ) = 0 and u′(k−1)−(C+1) (tf )([ 2 2C+1−1 , 1]) = [0, 1], the
root of the tree. Thus, we must have CL (tf ) = k + C + 1 and CR (tf ) = k − 2 − C.
Bringing CI (tf ) to 0 requires all of A ∪ B to be internal. Because CI (tb ) =
m1 + m2 + n1 + n2 − m2e − n2e , it will take at least that many x1 rotations to make
vertices external, incrementing Cx1 by m1 + m2 + n1 + n2 − m2e − n2e .
Nothing we have done yet increases CL , which can only be done with x−1
0
rotations. Bringing CL from 0 to k + C + 1 requires us to increment Cx−1
by
0
k + C + 1.

57

In total, this interval requires us to increment Cx1 by m1 +m2 +n1 +n2 −m2e −
n2e and Cx−1
by k + C + 1 for a total of k + C + 1 + m1 + m2 + n1 + n2 − m2e − n2e
0
rotations in this interval.
Total Rotations:
Between all these intervals, |u′(k−1)−(C+1) | ≥ (k +m1 )+(2k +1−m1 −n1 +m2 +
n2 + m2e + n2e ) + (k + C + 1 + m1 + m2 + n1 + n2 − m2e − n2e ) = 4k + 2 + m1 + 2m2 +
2n2 + C > 4k + 1 + C > 4k − C + C = |u′(k−1)−(C+1) | + C ≥ |u′(k−1)−(C+1) | + C ≥
|u′(k−1)−(C+1) |. However, this is a contradiction. Thus, in u′(k−1)−(C+1) , the final
time where vertex va is made internal must occur before the first time the vertex
vb is made internal.



Lemma. 4.23 In u′(k−1)−(C+1) , no more than C of the vertices in B are internal
at the final time va is made internal.
Proof. Assume, for contradiction, that at least C + 1 of the vertices in B are
internal at the final time va is made internal.
We consider the impact this has on |u′(k−1)−(C+1) |. We look at times t0 , ta ,
tb , and tf . Define t0 = 0 and tf = |u′(k−1)−(C+1) |. Define ta as the final time
that va is made internal in u′(k−1)−(C+1) and tb as the first time vb is made internal in u′(k−1)−(C+1) . These times are clearly distinct because the action of F
on the tree is bijective and (u′(k−1)−(C+1) (t0 ))([ 12 , 43 ]) = (u′(k−1)−(C+1) (ta ))(va ) =
l

(u′(k−1)−(C+1) (tb ))(vb ) = (u′(k−1)−(C+1) (tf ))([ 12 , 12

l−1

]) = [ 21 , 34 ]. Because Lemma 4.23

holds, ta < tb .
This means t0 < ta < tb < tf . We consider the impact the intervals of time
defined by this has on |u′(k−1)−(C+1) |.
Interval t0 ≤ t ≤ ta :
At t0 , all of A is mapped to the left of the pivot and to the right of va . Thus,
CL (t0 ) = k and da (t0 ) = k + 1. Because these vertices are mapped to the left of
the pivot, we can only decrease da using x0 rotations. We know da (ta − 1) = 0, so
we must increment Cx0 by at least k + 1.
58

At ta , a single x−1
by 1.
1 rotation makes va internal, so we increment Cx−1
1
Additionally, some of the vertices in A and B must be internal at ta , say m1
of the vertices in A and n1 of the vertices in B. Because CI (t0 ) = 0, it will take a
single x−1
1 rotation to make each of these internal. Also note, by our assumption,
by
n1 ≥ C + 1. To actually make these vertices internal, we increment Cx−1
1
another m1 + n1 in this step.
We also require additional accounting related to each of these vertices we make
q

internal, so we consider the vertices in B of form [ 2 2−1
q , 1], 1 ≤ q ≤ C +1. We know
that n1 ≥ C + 1 and there are exactly C + 1 such vertices in B. If any of these
vertices are not made internal, they must be mapped to the left side of the tree so
that the remainder of the above n1 vertices in B can be made internal by ta . All
q

of the vertices [ 2 2−1
q , 1], 1 ≤ q ≤ C + 1 will either be made internal or moved to
the left spine of the tree. If these vertices are internal at ta , we may have already
accounted for this in our n1 above. Say that o of the vertices are not internal at
−1 by at least o to account for moving these vertices
ta . We must increment Cx−1
0 ||x1

to the left of the pivot. Note, these rotations are moving vertices in B which are
not internal at ta and are thus clearly distinct from any other rotations in this
step. Additionally, these vertices are eventually mapped back to the right spine
of the tree before time ta , so we must likewise increment Cx0 ||x1 by o.
−1 by o,
In total, this interval requires us to increment Cx0 by k + 1, Cx−1
0 ||x1

Cx0 ||x1 by o, and Cx−1
by m1 + n1 + 1 for a total of k + 2 + m1 + n1 + 2o rotations
1
in this interval.
Interval ta < t ≤ tb :
Because u′(k−1)−(C+1) (ta )(va ) = [ 21 , 43 ] and F preserves the infix ordering of
vertices, u′(k−1)−(C+1) (ta ) maps A ∪ B to the right of the pivot. Thus, CL (ta ) = 0.
We also know that CI (ta ) = m1 + n1 , so CR (ta ) = 2k − 1 − m1 − n1 ) and db (ta ) ≥
2k−1−m1 −n1 . These vertices are mapped to the right spine, so reducing db can be
−1
′
accomplished using either x−1
0 or x1 rotations. Because u(k−1)−(C+1) (tb − 1)(vb ) =
−1 by at least 2k − 1 − m1 − n1 .
[ 12 , 1], db (tb − 1) = 0 and we must increment Cx−1
0 ||x1

by 1.
At tb , a single x−1
1 rotation makes vb internal, so we increment Cx−1
1
59

It is possible some of the vertices in A ∪ B that were internal at ta are external
at tb . Additionally, some of these vertices which were external at ta may be internal
at tb . Say that at time tb , m2 vertices in A are internal that were external at ta
and n2 vertices in B are internal that were external at ta . We may have already
accounted for making these vertices internal above. Of the m1 vertices in A that
were internal at ta , say m2e are external at tb , and of the n1 vertices in B that
were internal at ta , n2e are external at tb . We must increment Cx1 by m2e + n2e to
accomplish this change. Not only must these vertices be brought to the external
set, they must also be moved to the left side of the tree. These are distinct
rotations from the ones above and require us to increment Cx−1
by m2e + n2e . In
0
total then, CI (tb ) = (m1 + m2 − m2e ) + (n1 + n2 − n2e ).
−1 by 2k−1−m1 −n1 , C −1
In total, this interval requires us to increment Cx−1
x1
0 ||x1

by m2e +n2e for a total of 2k−m1 −n1 +2m2e +2n2e
by 1, Cx1 by m2e +n2e , and Cx−1
0
rotations in this interval.
Interval tb < t ≤ tf :
Note, u′(k−1)−(C+1) (tb )(vb ) = [ 12 , 43 ]. Because F preserves the infix ordering of
vertices, this means all of A ∪ B is mapped to the pivot. Thus, CR (tb ) = 0. We
know that CI (tb ) = m1 + m2 + n1 + n2 − m2e − n2e , so CL (tb ) = 2k − 1 − (m1 + m2 +
C+1

n1 +n2 −m2e −n2e ). Note that CI (tf ) = 0 and u′(k−1)−(C+1) (tf )([ 2 2C+1−1 , 1]) = [0, 1],
the root of the tree. Thus, we must have CL (tf ) = k+C +1 and CR (tf ) = k−2−C.
Bringing CI (tf ) to 0 requires all of A ∪ B to be internal. Because CI (tb ) =
m1 + m2 + n1 + n2 − m2e − n2e , it will take at least that many x1 rotations to make
these vertices external, incrementing Cx1 by m1 + m2 + n1 + n2 − m2e − n2e .
Decreasing CI with an x1 rotation increases CR because a vertex is brought
from the interior to the right spine of the tree. This provides an increase in CR of
m1 + m2 + n1 + n2 − m2e − n2e . We require CR (tf ) = k − 2 − C and it is possible
k − 2 − C > m1 + m2 + n1 + n2 − m2e − n2e . If so, the only way to further increase
CR is using x0 rotations to move vertices from the left side of the tree to the right
side. Thus, if k − 2 − C > m1 + m2 + n1 + n2 − m2e − n2e , then we must increase
Cx0 by at least k − 2 − C − (m1 + m2 + n1 + n2 − m2e − n2e ).
60

q

If any of the vertices in A or some of the vertices in B of the form [ 2 2−1
q , 1],
1 ≤ q ≤ C + 1 were internal at tb , they will be brought to the external set at tf .
When this occurs, these vertices are mapped to position [ 12 , 1] on the right spine of
(C+1)

the tree. Because u′(k−1)−(C+1) (tf )([ 2 2(C+1)−1 , 1]) = [0, 1], all of these vertices must
eventually be mapped to the left spine of the tree. There are m1 + m2 − m2e
such vertices in A that were internal at tb , requiring us to increment Cx−1
by
0
q

m1 + m2 − m2e . Of the vertices in B of the form [ 2 2−1
q , 1], 1 ≤ q ≤ C + 1, we know
C + 1 − o were internal at time ta . Some of these may have been made external
among the n2e vertices in B that were internal at time ta and external at time tb .
The remainder will have been made external in this interval, say p of the vertices
q

[ 2 2−1
q , 1], 1 ≤ q ≤ C + 1, requiring us to increment Cx−1 by an additional p this
0
interval. Note, p + n2e ≥ C + 1 − o and therefore p + o + n2e ≥ C + 1.
In total, this interval requires us to increment Cx1 by m1 +m2 +n1 +n2 −m2e −
n2e and Cx−1
by m1 +m2 −m2e +p, for a base total of 2m1 +2m2 +n1 +n2 −2m2e −
0
n2e + p rotations in this interval. If k − 2 − C > m1 + m2 + n1 + n2 − m2e − n2e ,
then we also increase Cx0 by k − 2 − C − (m1 + m2 + n1 + n2 − m2e − n2e ).
Total Rotations:
Between all these intervals, |u′(k−1)−(C+1) | ≥ (k + 2 + m1 + n1 + 2o) + (2k −m1 −
n1 +2m2e +2n2e )+(2m1 +2m2 +n1 +n2 −2m2e −n2e +p) = 3k+2+2o+2m1 +2m2 +
n1 + n2 + n2e + p = 3k + 2 + 2o + p + 2m1 + n1 + 2m2 + n2 + n2e plus an additional
k−2−C −(m1 +m2 +n1 +n2 −m2e −n2e ) if k−2−C > m1 +m2 +n1 +n2 −m2e −n2e .
If k−2−C ≤ m1 +m2 +n1 +n2 −m2e −n2e , then |u′(k−1)−(C+1) | ≥ 3k+2+2o+p+
2m1 + n1 + 2m2 + n2 + n2e ≥ 3k + 2 + 2o + p + m1 + m2 + n2e + (m1 + n1 + m2 + n2 ).
Because m1 + n1 + m2 + n2 ≥ m1 + m2 + n1 + n2 − m2e − n2e ≥ k − 2 − C,
we know |u′(k−1)−(C+1) | ≥ 3k + 2 + 2o + p + m1 + m2 + n2e + (k − 2 − C) =
4k + (p + o + n2e ) − C + (o + m1 + m2 ) ≥ 4k + (p + o + n2e ) − C ≥ 4k + 1 − C + C.
If k − 2 − C > m1 + m2 + n1 + n2 − m2e − n2e , then |u′(k−1)−(C+1) | ≥ 3k + 2 +
2o + p + 2m1 + n1 + 2m2 + n2 + n2e + (k − 2 − C − (m1 + m2 + n1 + n2 − m2e − n2e )) =
4k+2o+p−C+m1 +m2 +2n2e +m2e = 4k+(o+p+n2e )−C+o+m1 +m2 +n2e +m2e ≥
4k + (p + o + n2e ) − C ≥ 4k + 1 − C + C.
61

In either case we see that |u′(k−1)−(C+1) | ≥ 4k + 1 − C + C > 4k − C +
C = |u′(k−1)−(C+1) | + C ≥ |u′(k−1)−(C+1) | + C ≥ |u′(k−1)−(C+1) |. However, this is
a contradiction. Thus, in u′(k−1)−(C+1) , no more than C of the vertices in B are
internal at the final time va is made internal.



Lemma. 4.24 If in u′i , (k − 1) − (C + 1) ≤ i ≤ k − 2, the following two conditions
hold:
(1) The final time va is made internal occurs before the first time vb is made
internal,
(2) No more than C of the vertices in B are internal at the final time va is
made internal,
then, da (u′i (t)) > M − 1 if t > k + M + 2C + 2.
Proof. Assume that in u′i , conditions (1) and (2) hold as above. Suppose not, for
contradiction. Then in u′i , there will be at least one time, and thus a final time tc ,
where da (tc ) ≤ M − 1 with tc > k + M + 2C + 2. Because da ends up much larger
than M − 1 in u′i , it must be the case that da (tc ) = M − 1.
We look at the following times in ui : t0 , ta , tc , tb , and tf . Define t0 = 0 and
tf = |u′i |. Define ta as the final time that vertex va is made internal in u′i and tb as
the first time that vertex vb is made internal in u′i . By part one of our assumption,
ta < tb . We can also easily show that tc > ta . Because da (ta ) = −1 < M − 1 and
da (tf ) > M − 1, there must be a time after ta where da is exactly M − 1. However,
if tc < ta , there would be a time after tc where da was M − 1 while tc was the final
such time.
Further, we can understand a good deal about the structure of u′i (tc ). First
of all, because tc > ta , we know that at tc , va is internal as va must be internal
at the end of u′i . Additionally, va must be suspended from the left spine of the
tree, exactly distance one away from the spine. This again holds because in u′i , va
will ultimately end up hanging distance one from the left spine and changing this
can only be done by bringing va closer to the pivot, which cannot occur after tc .
Thus, we know va is hanging from the left spine of the tree some distance from
62

the pivot. There are vertices on the left spine of the tree at u′i (tc ) on the path
between va and the pivot. Exactly M − 3 vertices of A are on the spine between
p

va and the pivot, the vertices [0, 12 ], (k − 1) − (M − 3) ≤ p ≤ k − 1. After time tc ,
there are no times where da is less than or equal to M − 1. If any of these vertices
are not on the spine at this point, there is no way they can be moved to the spine
after this.
Most of these times are clearly distinct because the action of F on the tree is bijective and (u′i (t0 ))([ 21 , 43 ]) = (u′i (ta ))(va ) = (u′i (tb ))(vb ) = (u′i (tf ))([ 12

k−i 1 k−i−1
,2
])

=

[ 12 , 43 ]. We know that tc is clearly distinct from ta because da is not one. It cannot
be t0 or tf because da is much larger than M − 1. It cannot be tb because at tb , db
is one and for da to be M − 1 while db is one, we would need more than 2C vertices
of A internal. Because F preserves the infix ordering of vertices, all of A ∪ B is
mapped between va and vb on the tree and for these two distance to be less than
M at the same time, all but 2M of the k vertices in A would need to be mapped
internal, a contradiction to Lemma 4.21. Thus, we know that t0 < ta < tb < tf
and tc > ta .
This means that one of the following two orderings are true: t0 < ta < tc <
tb < tf or t0 < ta < tb < tc < tf . We consider the impact each has on |u′i |.
Ordering t0 < ta < tc < tb < tf
We begin with the time intervals given by t0 < ta < tc < tb < tf and account
for the total rotations needed in each interval.
Interval t0 ≤ t ≤ ta :
At t0 , all of A is mapped to the left of the pivot and to the right of va . Thus,
CL (t0 ) = k and da (t0 ) = k +1. Because these vertices are mapped to the left of the
pivot, the only way to decrease da is with x0 rotations. We know da (ta − 1) = 0,
so we must increment Cx0 by at least k + 1.
At ta , a single x−1
by 1.
1 rotation makes va internal, so we increment Cx−1
1
Additionally, some of the vertices in A and B may be internal at ta , say m1
of the vertices in A and n1 of the vertices in B. Because CI (t0 ) = 0, it will take a

63

single x−1
1 rotation to make each of these internal, requiring us to increment Cx−1
1
by another m1 + n1 this step. Note that by part two of our assumption, n1 ≤ C.
In total, this interval requires us to increment Cx0 by k + 1 and Cx−1
by
1
m1 + n1 + 1 for a total of k + m1 + n1 + 2 rotations in this interval.
Interval ta < t ≤ tc :
Because u′i (ta )(va ) = [ 21 , 43 ] and F preserves the infix ordering of vertices, u′i (ta )
maps A ∪ B at or to the right of the pivot. Thus, CL (ta ) = 0. We also know that
CI (ta ) = m1 + n1 , so CR (ta ) = 2k − 1 − (m1 + n1 ) and da (ta ) ≥ 1. We require
that da (tc ) = M − 1 and this is the final t where da (t) = M − 1 in ui . Bringing da
from 1 at ta to M − 1 will require x−1
0 rotations. Technically, because all of these
vertices are on the right spine of the tree we could also use x−1
1 rotations to make
them internal. If any x−1
1 rotations were used to increase da , this would move va
more than distance one from the spine. In ui , va is mapped exactly distance one
from the left spine. These extra internal vertices cannot be made external without
first making da equal M − 1 which cannot occur after time tc . Thus x−1
1 rotations
by at least M − 3.
cannot be used to accomplish this, so we must increment Cx−1
0
It is possible some of the vertices in A ∪ B that were internal at ta are external
at tc . Additionally, some of these vertices which were external at ta may be internal
at tb . Say that at time tc , m2 vertices in A are internal that were external at ta
and n2 vertices in B are internal that were external at ta . Of the m1 vertices in A
that were internal at ta , say m2e are external at tc , and of the n1 vertices in B that
were internal at ta , n2e are external at tc . We must increment Cx−1
by m2 + n2
1
and Cx1 by m2e + n2e to accomplish these changes.
Note that if either n2 > 0 or n2e > 0, we will require additional rotations. At
most 2C vertices in A may be internal at any time in u′i by Lemma 4.21. Note
M − 2 ≤ C. At ta , all of the vertices in A are either internal or mapped to the
right side of the tree and to the left of all of the vertices in B. We have accounted
for moving less than C of these vertices to the left side of the tree during this
interval. Because at most 2C of these can be made internal, in order to make a
vertex in B either internal or external, at least k − 3C vertices would first need to
64

be moved to the left side of the tree to accomplish this, and then moved back to
the right side of the tree afterwards. Thus, we would need to increment Cx0 and
by at least k − 3C each to accomplish this change, requiring an additional
Cx−1
0
2k − 6C rotations if n2 > 0 or n2e > 0.
Before moving forward, note that by our assumption, tc ≥ k + M + 2C + 2.
Between the first interval and the above portion of our second interval, we have
tc ≤ (k + m1 + n1 + 2) + (m2 + n2 + m2e + n2e + M − 3) = k + M + (m1 +
n1 + m2 + n2 + m2e + n2e − 1) if n2 = 0 and n2e = 0 or alternatively tc ≤
(k + m1 + n1 + 2) + (m2 + n2 + m2e + n2e + M − 3) + (2k − 6C) = k + M +
(2k − 6C + m1 + n1 + m2 + n2 + m2e + n2e ) − 1 if n2 > 0 or n2e > 0. Note that
2k − 6C + m1 + n1 + m2 + n2 + m2e + n2e − 1 > 2C + 2. However, in the other
case, it is possible that m1 + n1 + m2 + n2 + m2e + n2e − 1 < 2C + 2. If this is
so, additional rotations must have occurred to ensure that tc ≥ k + 2C + M + 2.
Thus, we can say that an additional L ≥ 0 rotations occurred in this case and
that L + m1 + n1 + m2 + n2 + m2e + n2e − 1 ≥ 2C + 2.
In total then, this interval requires us to increment Cx−1
by M − 3, Cx−1
by
0
1
m2 + n2 , and Cx1 by m2e + n2e for a total of m2 + n2 + m2e + n2e + M − 3 rotations
in this interval with an additional 2k − 6C rotations if n2 > 0 or n2e > 0 and an
additional L rotations if n2 = n2e = 0.
Interval tc < t ≤ tb :
We know that da (tc ) = M −1 and CI (tc ) = m1 +n1 +m2 +n2 −m2e −n2e . None
of the internal vertices in A are to the left of the pivot, so CL (tc ) = M −3 and thus
CR (tc ) = 2k −1−(m1 +n1 +m2 +n2 −m2e −n2e )−(M −3) = 2k +2−M −m1 −n1 −
m2 −n2 + m2e + n2e and db (ta ) ≥ 2k + 2 −M −m1 −n1 −m2 −n2 + m2e + n2e . These
vertices are mapped to the right spine, so reducing db can be accomplished either
by moving them to the left spine of the tree with x−1
0 rotations or making them
1
′
internal with x−1
1 rotations. Because ui (tb − 1)(vb ) = [ 2 , 1], db (tb − 1) = 0 and we
−1 by at least 2k + 2 − M − m1 − n1 − m2 − n2 + m2e + n2e .
must increment Cx−1
0 ||x1

At tb , a single x−1
by 1.
1 rotation makes vb internal, so we increment Cx−1
1

65

It is possible some of the vertices in A ∪ B that were internal at ta are external
at tb . Additionally, some of these vertices which were external at ta may be internal
at tb . We may have already accounted for making these new vertices internal. Say
that by time tb , m3 vertices in A are internal that were external at ta and n3
vertices in B are internal that were external at ta . Of the m1 + m2 − m2e vertices
in A that were internal at ta , say m3e are external at tb , and of the n1 + n2 + n2e
vertices in B that were internal at ta , n3e are external at tb . We must increment
Cx1 by m3e + n3e to accomplish this change.
−1 by 2k + 2 − M −
In total, this interval requires us to increment Cx−1
0 ||x1

by 1, and Cx1 by m3e + n3e for a total of
m1 − n1 − m2 − n2 + m2e + n2e , Cx−1
1
2k + 3 − M − m1 − n1 − m2 − n2 + m2e + n2e + m3e + n3e rotations in this interval.
Interval tb < t ≤ tf :
Note, u′i (tb )(vb ) = [ 21 , 43 ]. Because F preserves the infix ordering of vertices,
all of A ∪ B is mapped to the left of position [ 12 , 34 ]. Thus CR (tb ) = 0. We
know that CI (tb ) = m1 + m2 + m3 + n1 + n2 + n3 − m2e − m3e − n2e − n3e , so
CL (tb ) = 2k − 1 − (m1 + m2 + m3 + n1 + n2 + n3 − m2e − m3e − n2e − n3e ). Note
k−1−i

that CI (tf ) = 0 and u′i (tf )([ 2 2k−1−i−1 , 1]) = [0, 1], the root of the tree. Thus, we
must have CL (tf ) = 2k − 1 − i and CR (tf ) = i.
Bringing CI (tf ) to 0 requires all of A ∪ B to be internal. Because CI (tb ) =
m1 + m2 + m3 + n1 + n2 + n3 − m2e − m3e − n2e − n3e , it will take at least that
many x1 rotations to make vertices external, incrementing Cx1 by m1 + m2 + m3 +
n1 + n2 + n3 − m2e − m3e − n2e − n3e .
We require additional rotations related to these vertices we have made external. Any time a vertex is made external, it is mapped from the interior of the tree
q

to the pivot. This is fine for the vertices [ 2 2−1
q , 1], k − 2 − i ≤ q ≤ k − 1, because
|u′i (tf )| maps them to the right spine of the tree. However, all of the vertices in
q

′
A and [ 2 2−1
q , 1], 1 ≤ q ≤ k − 1 − i must be mapped to the left spine in ui (tf ).

Mapping a vertex from the right spine of the tree to the left spine can only be
−1
accomplished by an x−1
0 rotation and we have accounted for no x0 rotations in

this step thus far. All of the m1 + m2 + m3 − m2e − m3e vertices in A that are
66

internal at tb will need to be brought to the left side of the tree. This requires us
to increment Cx−1
by m1 + m2 + m3 − m2e − m3e .
0
Recall, CR (tb ) = 0 and CR (tf ) = i. Making vertices from A ∪ B external
increases CR by 1 and we have accounted for making all of A ∪ B external with
m1 + m2 + m3 + n1 + n2 + n3 − m2e − m3e − n2e − n3e rotations. At the same time,
moving the vertices in A that we have made external decreases CR by 1 for each
of the m1 + m2 + m3 − m2e − m3e such vertices. This is a net increase in CR of
n1 + n2 + n3 − n2e − n3e that we have accounted for in this step. It is possible that
n1 + n2 + n3 − n2e − n3e < i. If so, we will need to increment CR by the difference,
bringing vertices from the left side of the tree to the right side. This means using
Cx0 by i − (n1 + n2 + n3 − n2e − n3e ).
In total, this interval requires us to increment Cx1 by m1 + m2 + m3 + n1 +
by m1 + m2 + m3 − m2e − m3e for a total of
n2 + n3 − m2e − m3e − n2e − n3e and Cx−1
0
2m1 +2m2 +2m3 −2m2e −2m3e +n1 +n2 +n3 −n2e −n3e . If n1 +n2 +n3 −n2e −n3e < i,
we must increment Cx0 by an additional i − (n1 + n2 + n3 − n2e − n3e ).
Total Rotations:
In total, we have established that |u′i | ≥ (k + m1 + n1 + 2) + (m2 + n2 + m2e +
n2e + M − 3) + (2k + 2 − M − m1 − n1 − m2 − n2 + m2e + n2e + m3e + n3e ) + (2m1 +
2m2 + 2m3 − 2m2e − 2m3e + n1 + n2 + n3 − n2e − n3e ) = 3k + 1 + 2m1 + 2m2 +
2m3 − m3e + n1 + n2 + n3 + n2e plus an additional i − (n1 + n2 + n3 − n2e − n3e )
if n1 + n2 + n3 − n2e − n3e < i, 2k − 6C if n2 > 0 or n2e > 0, and an additional L
rotations if n2 = n2e = 0. This gives us four cases to consider.
First of all, if n1 + n2 + n3 − n2e − n3e < i and n2 = n2e = 0, then |u′i | ≥
3k + 1 + 2m1 + 2m2 + 2m3 − m3e + n1 + n2 + n3 + n2e + (i − (n1 + n2 + n3 −
n2e − n3e )) + L = 3k + 1 + i + L + 2m1 + 2m2 + 2m3 − m3e + n2e + n3e =
3k+1+i+L+2m1 +2m2 +2m3 −m3e +n3e . Note, m1 +m2 +m3 ≥ m2e +m3e , n3e ≥ 0,
and n1 ≤ C so |u′i | = 3k + 1 + i + L + 2m1 + 2m2 + 2m3 + m2e − m2e − m3e + n3e ≥
3k + 1 + i + (L + m1 + m2 + m3 + m2e ) = 3k + 1 + i + (L + m1 + m2 + m3 +
m2e + C) − C ≥ 3k + 2 + i + (L + m1 + m2 + m3 + m2e + n1 − 1) − C. We know,

67

L + m1 + m2 + m2e + n1 − 1 = L + m1 + m2 + m2e + n1 + n2 + n2e − 1 ≥ 2C + 2.
So now |u′i | ≥ 3k + 2 + i + (2C + 2) − C > 3k + 2 + i + C.
Second, if n1 + n2 + n3 − n2e − n3e < i and n2 > 0 or n2e > 0, then |u′i | ≥
3k + 1 + 2m1 + 2m2 + 2m3 − m3e + n1 + n2 + n3 + n2e + (i − (n1 + n2 + n3 −
n2e − n3e )) + 2k − 6C = 5k + i − 6C + 1 + 2m1 + 2m2 + 2m3 − m3e + 2n2e + n3e =
3k + 2 + i+ C + (2k −7C −1) + (m1 + m2 + m3 ) + (m1 + m2 + m3 −m3e + 2n2e + n3e ).
Note, m1 + m2 + m3 ≥ m3e , 2k > 7C, and m1 + m2 + m3 − m3e + 2n2e + n3e ≥ 0
so |u′i | > 3k + 2 + i + C.
Third, if n1 +n2 +n3 −n2e −n3e ≥ i and n2 = n2e = 0, then |u′i | ≥ 3k+1+2m1 +
2m2 +2m3 −m3e +n1 +n2 +n3 +n2e +L = 3k+2+(n1 +n2 +n3 )+(L+m1 +m2 +m3 +
n1 −1)+(m1 +m2 +m3 −m3e )−n1 . Note, n1 +n2 +n3 ≥ n1 +n2 +n3 −n2e −n3e ≥ i,
m1 + m2 + m3 − m3e ≥ 0, and L + m1 + m2 + m2e + n1 − 1 = L + m1 + m2 + m2e +
n1 + n2 + n2e − 1 ≥ 2C + 2. Thus, |u′i | ≥ 3k + 2 + i + (2C + 2) − n1 > 3k + 2 + i + C
as n1 ≤ C.
Finally, if n1 + n2 + n3 − n2e − n3e ≥ i and n2 > 0 or n2e > 0, then |u′i | ≥
3k + 1 + 2m1 + 2m2 + 2m3 − m3e + n1 + n2 + n3 + n2e + 2k − 6C = 3k + 2 +
(n1 + n2 + n3 ) + C + (2k − C − 1) + (2m1 + 2m2 + 2m3 − m3e ) + n2e . Note,
n1 + n2 + n3 ≥ n1 + n2 + n3 − n2e − n3e ≥ i, m1 + m2 + m3 − m3e ≥ 0, and
2k − C − 1 > 0 meaning |u′i | > 3k + 2 + i + C.
In every case, we see that |u′i | > 3k + 2 + i + C ≥ 3k + 2 + i + c = |u′i | + c ≥ |u′i |.
This is a contradiction.
Ordering t0 < ta < tb < tc < tf
We now handle the time intervals given by t0 < ta < tb < tc < tf and account
for the total rotations needed in each interval.
Interval t0 ≤ t ≤ ta :
At t0 , all of A is mapped to the left of the pivot and to the right of va . Thus,
CL (t0 ) = k and da (t0 ) = k +1. Because these vertices are mapped to the left of the
pivot, the only way to decrease da is with x0 rotations. We know da (ta − 1) = 0,
so we must increment Cx0 by at least k + 1.

68

At ta , a single x−1
by 1.
1 rotation makes va internal, so we increment Cx−1
1
Additionally, some of the vertices in A and B may be internal at ta , say m1
of the vertices in A and n1 of the vertices in B. Because CI (t0 ) = 0, it will take a
single x−1
1 rotation to make each of these internal, requiring us to increment Cx−1
1
by another m1 + n1 this step.
In total, this interval requires us to increment Cx0 by k + 1 and Cx−1
by
1
m1 + n1 + 1 for a total of k + m1 + n1 + 2 rotations in this interval.
Interval ta < t ≤ tb :
Because u′i (ta )(va ) = [ 21 , 43 ] and F preserves the infix ordering of vertices, u′i (ta )
maps A ∪ B at or to the right of the pivot. Thus, CL (ta ) = 0. We also know that
CI (ta ) = m1 + n1 , so CR (ta ) = 2k − 1 − (m1 + n1 ) and db (ta ) ≥ 2k − m1 − n1 − 1.
These vertices are mapped to the right spine, so reducing db can be accomplished
either by moving them to the left spine of the tree with x−1
0 rotations or making
1
′
them internal with x−1
1 rotations. Because ui (tb − 1)(vb ) = [ 2 , 1], db (tb − 1) = 0
−1 by at least 2k − m1 − n1 − 1.
and we must increment Cx−1
0 ||x1

At tb , a single x−1
by 1.
1 rotation makes vb internal, so we increment Cx−1
1
It is possible some of the vertices in A ∪ B that were internal at ta are external
at tb . Additionally, some of these vertices which were external at ta may be internal
at tb . We may have already accounted for making these new vertices internal. Say
that by time tb , m2 vertices in A are internal that were external at ta and n2
vertices in B are internal that were external at ta . Of the m1 vertices in A that
were internal at ta , say m2e are external at tb , and of the n1 vertices in B that
were internal at ta , n2e are external at tb . We must increment Cx1 by m2e + n2e to
accomplish this change. In total then, CI (tb ) = (m1 + m2 − m2e ) + (n1 + n2 − n2e ).
−1 by 2k − m1 − n1 − 1,
In total, this interval requires us to increment Cx−1
0 ||x1

by 1, and Cx1 by m2e + n2e for a total of 2k − m1 − n1 + m2e + n2e rotations
Cx−1
1
in this interval.
Interval tb < t ≤ tc :

69

Note, u′i (tb )(vb ) = [ 21 , 43 ]. Because F preserves the infix ordering of vertices,
all of A ∪ B is mapped to the left of position [ 12 , 43 ]. Thus CR (tb ) = 0. We know
that CI (tb ) = m1 + m2 + n1 + n2 − m2e − n2e , so CL (tb ) = 2k − 1 − (m1 +
m2 + n1 + n2 − m2e − n2e ). da (tc ) = M − 1 and va is already internal and
will remain internal through this interval. Thus, CL (tc ) = M − 2 < C. Note,
m1 + m2 − m2 e < 2C by Lemma 4.21 and n1 + n2 − n2e ≤ k. This means
CL (tb ) ≥ k − 1 − C which is significantly larger than C. Thus, we can note
with certainty that CL (tb ) > CL (tc ). We must decrease CL using x0 rotations
to move vertices from the left side of the tree to the right side. Thus, we must
increment Cx0 by at least 2k − 1 − (m1 + m2 + n1 + n2 − m2e − n2e ) − (M − 2) =
2k + 1 − M − m1 − m2 − n1 − n2 + m2e + n2e . This is sufficient accounting for this
interval.
Interval tc < t ≤ tf :
k−1−i

Above, we noted that CL (tc ) = M − 2. We know that u′i (tf )([ 2 2k−1−i−1 , 1]) =
[0, 1], the root of the tree. Thus, we must have CL (tf ) = 2k − 1 − i. Increasing
CL from M − 2 to 2k − 1 − i would require x−1
0 rotations to bring vertices from
by
the right spine of the tree to the left spine. Thus, we must increment Cx−1
0
2k − 1 − i − M + 2.
Total Rotations:
In total, we have established that |u′i | ≥ (k + m1 + n1 + 2) + (2k − m1 − n1 +
m2e + n2e ) + (2k + 1 − M − m1 − m2 − n1 − n2 + m2e + n2e ) + (2k − 1 − i − M + 2) =
7k + 4 − 2M − i − m1 − m2 + 2m2e − n1 − n2 + 2n2e = 3k + i + 2 + C + (k − C − 2M −
m1 − m2 ) + (k − i) + (k − n1 − n2 ) + (k − i) + 2m2e + 2n2e + 2 > 3k + i + 2 + C ≥
3k + 2 + i + c = |u′i | + c ≥ |u′i |. This is a contradiction.
Conclusion:
Now, with either ordering we see that the length of u′i must be longer than the
necessary restriction that |u′i | ≤ |u′i |+c demands. Because we have a contradiction
either way, we see that in u′i , if the final time va is made internal occurs before the
first time vb is made internal, then, da (u′i (t)) > M − 1 if t > k + 1 + 2C + M. 
70

Lemma. 4.25 If in u′i , (k − 1) − (C + 1) ≤ i ≤ k − 2, the following two conditions
hold:
(1) The final time va is made internal occurs before the first time vb is made
internal,
(2) No more than C of the vertices in B are internal at the final time va is
made internal,
then, in u′i+1 , (1) holds as well.
Proof. Assume that in u′i , conditions (1) and (2) hold as above. Suppose not for
contradiction. That is, in u′i+1 , the first time vb is made internal occurs before the
final time va is made internal.
Because conditions (1) and (2) hold in u′i , Lemma 4.23 tells us da (u′i (t)) >
M − 1 if t > k + 1 + 2C + M. In order for va to be made internal in a word, da
must be 0 at the moment before it is made internal. In u′i , va must be internal at
the end of the word. Thus, if t > k + 1 + 2C + M, va must be internal at time
u′i (t). Note that u′i and u′i+1 are M fellow travelers. Because va is internal in u′i
from time t onward, it must be the case that either va is internal in u′i+1 or can
be made internal in u′i+1 within M rotations.
We will begin by considering times in u′i+1 : t0 = 0, tf = |u′i+1 |, ta which
is the final time va is made internal in u′i+1 , and tb which is the first time vb is
made internal in ui+1 . By our supposition tb < ta . Most of these times are clearly
distinct because the action of F on the tree is bijective and (u′i+1(t0 ))([ 21 , 43 ]) =
(u′i+1 (ta ))(va ) = (u′i+1(tb ))(vb ) = [ 21 , 34 ]. Time tf must be distinct from the others
because it is certainly not t0 as vertices are made internal in wi′ and because va and
vb are mapped approximately k from the pivot at tf . This means t0 < tb < ta < tf .
Claim. tb > k + 2 + 2C + M.
Proof. Suppose not for contradiction. That is tb ≤ k + 2 + 2C + M. Then at some
time t1 ≤ k +2+2C +M, db (ui+1 (t1 )) = 0. Additionally, we know by Lemma 4.24,
that at some time t2 ≤ k + 2 + 2C + M, da (ui (t2 )) ≤ M − 1. This holds because
da is initially greater than M − 1 in u′i , it must be reduced to zero before va can
71

be made internal in u′i , va is ultimately internal in u′i , and the only times da (ui )
can be reduced below M − 1 are obviously less than k + 2 + 2C + M. Because u′i
and u′i+1 are M fellow travelers, we know that at t2 it must be possible, within M
steps, to reach a point where da is M −1 in u′i+1. Thus, 0 ≤ da (ui+1(t2 )) ≤ 2M −1.
Note, db (ui+1 (t0 )) = k − 1 and da (ui+1 (t0 )) = k + 1. Reducing da (ui+1 ) from
k + 1 to 2M − 1 requires a total of at least (k + 1) − (2M − 1) = k + 2 − 2M
x0 rotations to map the intermediate vertices from the left spine to the right
−1
spine. Reducing db from k − 1 to 0 requires a combination of k − 1 x−1
1 and x0

rotations. In total, this requires 2k +1−2M rotations to occur before tb . However,
2k + 1 − 2M > k + 2 + 2C + M as k ≥ 1000C where C = max(c, M) and we have
a contradiction. Thus, tb > k + 1 + C + M.



Now, we wish to consider a final time, tc . We claim that at tc , va is made
internal in u′i+1 before tb .
Claim. There exists tc ≤ tb such that va is made internal in u′i+1 at tc .

Proof. Suppose not for contradiction. That is, there are no times before tb where
va is made internal in u′i+1 . In our previous claim, we have established that
tb > k + 2 + C + M. We also know that after k + 2 + 2C + M, va must be
internal in u′i and cannot be made external again. Because u′i and u′i+1 are M
fellow travelers, we know that while va is internal in u′i , it is either internal in
u′i+1 or can be made internal within M rotations. Thus, from k + 2 + 2C + M
onward in u′i+1 , one of these two states hold. By our supposition, va is not made
internal in u′i+1 before tb . So for k + 1 + 2C + M < t < tb , it must be the case
that da (u′i+1 (t)) ≤ M − 1. However, we also require that db (u′i+1 (tb − 1)) = 0.
This would require that CR (ui+1 (tb − 1)) = 0, CL (ui+1 (tb − 1)) ≤ M − 1, and
therefore CI (ui+1 (tb − 1)) ≥ 2k − 1 − (M − 1). In order for us to accomplish this,
all but M − 1 of the vertices in A ∪ B must be internal. But then more than 2C of
the vertices in A would need to be internal, a clear contradiction to Lemma 4.21.
Thus, at some point tc < tb , va is made internal in u′i+1 .
72



Now, we have established that t0 < tc < tb < ta < tf . We can consider the
impact this has on |u′i+1|.
Interval t0 ≤ t ≤ tc :
At t0 , all of A is mapped to the left of the pivot and to the right of va . Thus,
CL (t0 ) = k and da (t0 ) = k + 1. Because these vertices are mapped to the left of
the pivot, the only way to decrease da is with x0 rotations. To make va internal
at tc , da (tc − 1) = 0, so we must increment Cx0 by at least k + 1.
At tc , a single x−1
by 1.
1 rotation makes va internal, so we increment Cx−1
1
Additionally, some of the vertices in A and B may be internal at tc , say m1
of the vertices in A and n1 of the vertices in B. Because CI (t0 ) = 0, it will take a
single x−1
1 rotation to make each of these internal, requiring us to increment Cx−1
1
by another m1 + n1 this step.
In total, this interval requires us to increment Cx0 by k + 1 and Cx−1
by
1
m1 + n1 + 1 for a total of k + m1 + n1 + 2 rotations in this interval.
Interval tc < t ≤ tb :
Because u′i+1 (tc )(va ) = [ 21 , 43 ] and F preserves the infix ordering of vertices,
u′i+1 (tc ) maps A∪B at or to the right of the pivot. Thus, CL (tc ) = 0. We also know
that CI (tc ) = m1 +n1 , so CR (tc ) = 2k −1−(m1 +n1 ) and db (tc ) ≥ 2k −m1 −n1 −1.
These vertices are mapped to the right spine, so reducing db can be accomplished
either by moving them to the left spine of the tree with x−1
0 rotations or making
1
′
them internal with x−1
1 rotations. Because ui+1 (tb − 1)(vb ) = [ 2 , 1], db (tb − 1) = 0
−1 by at least 2k − m1 − n1 − 1.
and we must increment Cx−1
0 ||x1

At tb , a single x−1
by 1.
1 rotation makes vb internal, so we increment Cx−1
1
It is possible some of the vertices in A ∪ B that were internal at tc are external
at tb . Additionally, some of these vertices which were external at tc may be internal
at tb . We may have already accounted for making these new vertices internal. Say
that by time tb , m2 vertices in A are internal that were external at tc and n2
vertices in B are internal that were external at tc . Of the m1 vertices in A that
were internal at tc , say m2e are external at tb , and of the n1 vertices in B that

73

were internal at tc , n2e are external at tb . We must increment Cx1 by m2e + n2e to
accomplish this change. In total then, CI (tb ) = (m1 + m2 − m2e ) + (n1 + n2 − n2e ).
−1 by 2k − m1 − n1 − 1,
In total, this interval requires us to increment Cx−1
0 ||x1

Cx−1
by 1, and Cx1 by m2e + n2e for a total of 2k − m1 − n1 + m2e + n2e rotations
1
in this interval.
Interval tb < t ≤ ta :
Because u′i+1 (vb ) = [ 21 , 43 ] and F preserves the infix ordering of vertices, u′i+1 (tb )
maps A∪B to the left of the pivot. Thus, CR (tb ) = 0. We also know that CI (tb ) =
m1 + m2 − m2e + n1 + n2 − n2e , so CL (tb ) = 2k − 1 − (m1 + m2 − m2e + n1 + n2 − n2e )
and da (tb ) ≥ 2k − m1 − m2 + m2e − n1 − n2 + n2e . These vertices are mapped to the
left spine, so reducing da can only be accomplished by moving vertices to the right
spine of the tree with x0 rotations. Because u′i+1 (ta − 1)(va ) = [ 21 , 1], da (ta −1) = 0
and we must increment Cx0 by at least 2k − m1 − m2 + m2e − n1 − n2 + n2e .
At ta , a single x−1
by 1.
1 rotation makes va internal, so we increment Cx−1
1
It is possible some of the vertices in A ∪ B that were internal at tb are external
at ta . Additionally, some of these vertices which were external at tb may be internal
at ta . Say that by time ta , m3 vertices in A are internal that were external at tb
and n3 vertices in B are internal that were external at tb . We must increment Cx−1
1
by m3 + n3 to accomplish this change. Of the vertices in A that were internal at
tb , say m3e are external at ta , and of the vertices in B that were internal at tb , n3e
are external at ta . We must increment Cx1 by m3e + n3e to accomplish this change.
In total then, CI (ta ) = (m1 + m2 + m3 − m2e − m3e ) + (n1 + n2 + n3 − n2e − n3e ).
−1 by 2k − m1 − m2 +
In total, this interval requires us to increment Cx−1
0 ||x1

m2e − n1 − n2 + n2e by m3 + n3 + 1, and Cx1 by m3e + n3e for a total of 2k + 1 −
m1 − m2 + m3 + m2e + m3e − n1 − n2 + n3 + n2e + n3e rotations in this interval.
Interval ta < t ≤ tf :
Note, u′i+1 (va ) = [ 21 , 34 ]. Because F preserves the infix ordering of vertices,
this means all of A ∪ B is mapped to the right of position [ 21 , 43 ]. Thus it must
be on the right side of the tree, meaning CL (ta ) = 0. We know that CI (ta ) =
m1 + m2 + m3 − m2e − m3e ) + (n1 + n2 + n3 − n2e − n3e , so CR (ta ) = 2k − 1 − (m1 +
74

m2 + m3 − m2e − m3e ) + (n1 + n2 + n3 − n2e − n3e ). Note that CI (tf ) = 0
k−2−i

and u′i+1 (tf )([ 2 2k−2−i−1 , 1]) = [0, 1], the root of the tree. Thus, we must have
CL (tf ) = 2k − 2 − i.
Bringing CI (tf ) to 0 requires all of A ∪ B to be internal. Because CI (tb ) =
m1 + m2 + m3 − m2e − m3e + n1 + n2 + n3 − n2e − n3e , it will take at least that
many x1 rotations to make vertices external, incrementing Cx1 by m1 + m2 + m3 −
m2e − m3e + n1 + n2 + n3 − n2e − n3e .
Nothing we have done yet increases CL , which can only be done with x−1
0
by
rotations. Bringing CL from 0 to 2k − 2 − i requires us to increment Cx−1
0
2k − 2 − i.
In total, this interval requires us to increment Cx1 by m1 + m2 + m3 − m2e −
by 2k − 2 − i for a total of 2k − 2 − i +
m3e + n1 + n2 + n3 − n2e − n3e and Cx−1
0
m1 + m2 + m3 − m2e − m3e + n1 + n2 + n3 − n2e − n3e rotations in this interval.
Total Rotations:
In total, we have established that |u′i+1 | ≥ (k + m1 + n1 + 2) + (2k − m1 − n1 +
m2e +n2e )+(2k+1−m1 −m2 +m3 +m2e +m3e −n1 −n2 +n3 +n2e +n3e )+(2k−2−i+
m1 +m2 +m3 −m2e −m3e +n1 +n2 +n3 −n2e −n3e ) = 7k+1−i+m2e +n2e +2m3 +2n3 >
7k − i ≥ 6k > 3k + 2 + (i + 1) + C ≥ 3k + 2 + (i + 1) + c = |u′i+1| + c ≥ |u′i+1 |.
This is a contradiction.

Lemma. 4.26 If in u′i , (k − 1) − (C + 1) ≤ i ≤ k − 2, the following two conditions
hold:
(1) The final time va is made internal occurs before the first time vb is made
internal,
(2) No more than C of the vertices in B are internal at the final time va is
made internal,
then, in u′i+1 , (2) holds as well.
Proof. Suppose that conditions (1) and (2) hold as above in u′i . Assume, for
contradiction, that in u′i+1 , at the final time va is made internal at least C + 1
75

vertices in B are internal. We begin by noting that by Lemma 4.25, condition (1)
holds in u′i+1 as well. We also note that u′i and u′i+1 are M fellow travelers.
We start by considering times t0 , ta , tb , and tf . Define t0 = 0 and tf = |u′i+1 |.
Define ta as the final time that va is made internal in u′i+1 and tb as the first
time vb is made internal in u′i+1 . Most of these times are clearly distinct because
the action of F on the tree is bijective and (u′i+1 (t0 ))([ 12 , 43 ]) = (u′i+1 (ta ))(va ) =
(u′i+1 (tb ))(vb ) = [ 12 , 43 ]. Time tf must be distinct from the others because it is
certainly not t0 as vertices are made internal in wi′ and because va and vb are
mapped approximately k from the pivot at tf .
By Lemma 4.24, we know that from time tc = k + M + 2C + 2 onward,
da (u′i (t)) > M − 1. Thus va must be internal in u′i (tc ) and onwards as it is
ultimately internal in ui and there is no way to make it internal without reducing
da to 0. Because u′i and u′i+1 are M fellow travelers, this means that from tc
onward in u′i+1 , either va is internal or can be made internal within M rotations.
Claim. ta > tc .

Proof. Suppose not for contradiction. Then ta ≤ tc so va is made internal for the
last time in u′i+1 before tc . By our assumption, at least C + 1 vertices in B are
internal at this time. However, va is also made internal before tc in u′i with at
most C vertices in B internal. Before va can be made internal in either word, da
must be reduced from k + 1 to 0. This requires k + 1 x0 rotations and va cannot
be made internal prior to this. If ta < tc , this means va can only be made internal
between times k + 2 and k + 2 + 2C + M, leaving 2C + M ≤ 3C rotations of this
in either word. We have specifically accounted for k + 1 x0 rotations, meaning
there can be less than 3C x−1
1 rotations in this time before time tc in either word.
Thus, at tc , the distance between the pivot and the nearest vertex in B is at least
k − 1 − 3C. However, this means that at tc , va will be internal in both words
with different numbers of vertices from B internal. Because it would take at least
k − 1 − 3C > M rotations to make a vertex in B internal or external in either
word, this violates the M fellow traveler property, a contradiction.
76



Additionally, we note that there must be a time ta′ ≤ tc where da (ta′ ) = M
with at most C vertices in B internal. When va is made internal for the final time
in u′i , it must be possible to make va internal in u′i+1 within M steps. So da would
need to be at most M. Further, because at most 2C vertices in A can be internal
by Lemma 4.21, the number of external vertices of A is at least k − 2C − M at
this time. Because F preserves the infix order, these vertices in A are mapped
between the pivot and all the vertices in B. Thus, making a vertex in B external
would first require moving all of these remaining vertices in A off the right spine,
requiring k − 2C − M > M rotations. Thus, it would be impossible, within M
steps, to make va internal in u′i+1 and make any vertex in B external.
Clearly, ta′ < ta . We can also note that at some point between these times,
at least one vertex of B must be made internal. Call the time when this occurs
td . Now we have t0 < ta′ < td < ta < tb < tf and we can consider the implications
this has on |u′i+1|.
Interval t0 ≤ t ≤ ta′ :
At t0 , all of A is mapped to the left of the pivot and to the right of va . Thus,
CL (t0 ) = k and da (t0 ) = k + 1. Because these vertices are mapped to the left of
the pivot, the only way to decrease da is with x0 rotations. We know da (ta′ ) = M,
so we must increment Cx0 by at least k + 1 − M.
Additionally, some of the vertices in B may be internal at ta′ , say n1 of the
vertices in B. Because CI (t0 ) = 0, it will take a single x−1
1 rotation to make each
of these internal, requiring us to increment Cx−1
by another n1 this step. Note,
1
n1 ≤ C.
by
In total, this interval requires us to increment Cx0 by k + 1 − M and Cx−1
1
n1 for a total of k + n1 + 1 − M rotations in this interval.
Interval ta′ < t ≤ td :
At ta′ , at most 2C of the vertices in A may be internal. When da (ta′ ) = M, at
most M of the vertices in A may be external and to the left of the pivot. Because
F preserves the infix ordering of vertices, the vertices in A must always be to the
right of va in the tree. If more than M of the vertices in A are external and to the
77

left of the pivot, these all increase the distance between va and the pivot, making
da greater than M. Thus, at ta′ , at least k − 3C vertices in A are external, to the
left of va , and to the right of the pivot.
At td , it must be possible to make a vertex in B internal, so we must move all
of the vertices of A to the left of the pivot by this time. Moving vertices from the
−1
right side of the tree to the left side can be accomplished using either x−1
0 or x1

rotations and we will require at least k − 3C such rotations.
In this interval, it is not possible for any of the vertices in B to be made
external or internal. The first time this is possible is after td itself once all of the
vertices in A are left of the pivot.
−1 by k − 3C rotations in
In total, this interval requires us to increment Cx−1
0 ||x1

this interval.
Interval td < t ≤ ta :
At td , all of the vertices in A are mapped to the left of the pivot and by Lemma
4.21, at least k − 2C of them are external. Thus, da (td ) ≥ k − 2C. Because these
vertices are to the left of the pivot on the spine of the tree, da can only be reduced
using x0 rotations. We require da (ta − 1) = 0. Thus we must increment Cx0 by
k − 2C in this interval.
It is possible some of the vertices in B that were internal at td are external at
ta . Additionally, some of these vertices which were external at td may be internal
at ta . Say that by time ta , n2 vertices in B are internal that were external at td .
Of the n1 vertices in B that were internal at td , n2e are external at ta . We must
by n2 and Cx1 by n2e to accomplish this change.
increment Cx−1
1
by n2 , and
In total, this interval requires us to increment Cx0 by k − 2C, Cx−1
1
Cx1 by n2e for a total of k − 2C + n2 + n2e rotations in this interval.
Interval ta < t ≤ tb :
Because u′i+1 (ta )(va ) = [ 21 , 43 ] and F preserves the infix ordering of vertices,
u′i+1 (ta ) maps A ∪ B to the right of the pivot. Thus, CL (ta ) = 0. We also know
that CI (ta ) ≤ 2C + n1 + n2 − n2e , so CR (ta ) = 2k − 1 − (2C + n1 + n2 − n2e ) and

78

db (ta ) ≥ 2k − 1 − (2C + n1 + n2 − n2e ). These vertices are mapped to the right
−1
spine, so reducing db can be accomplished using either x−1
0 or x1 rotations. Note,
−1 by at least 2k−1−2C −n1 −n2 +n2e .
db (tb −1) = 0 and we must increment Cx−1
0 ||x1

It is possible some of the vertices in B that were internal at ta are external at
tb . Additionally, some of these vertices which were external at ta may be internal
at tb . Say that by time tb , n3 vertices in B are internal that were external at ta .
Of the n1 + n2 − n2e vertices in B that were internal at ta , n3e are external at tb .
We have already potentially accounted for making vertices in B internal in the
previous paragraph. Thus, we only need to increment Cx1 by n3e to accomplish
this change.
−1 by 2k − 1 − 2C − n1 −
In total, this interval requires us to increment Cx−1
0 ||x1

n2 + n2e and Cx1 by n3e for a total of 2k − 1 − 2C − n1 − n2 + n2e + n3e rotations
in this interval.
Interval tb < t ≤ tf :
We know that CI (tb ) ≥ n1 + n2 + n3 − n2e − n3e . Also, CI (tf ) = 0. Bringing
CI (tf ) to 0 requires all of A ∪ B to be internal. Because CI (tb ) ≥ n1 + n2 + n3 −
n2e − n3e , it will take at least that many x1 rotations to make vertices external,
incrementing Cx1 by n1 + n2 + n3 − n2e − n3e . This should be sufficient accounting
for this interval.
Total Rotations:
In total, we have established that |u′i+1| ≥ (k + n1 + 1 − M) + (k − 3C) + (k −
2C + n2 + n2e ) + (2k − 1 − 2C − n1 − n2 + n2e + n3e ) + (n1 + n2 + n3 − n2e − n3e ) =
5k − 7C − M + n1 + n2 + n3 + n2e = 3k + 2 + (k + 1) + C + (k − 3 − 8C − M) +
n1 + n2 + n3 + n2e . Note, k ≥ i, k − 3 − 8C − M > 0 and n1 + n2 + n3 + n2e ≥ 0.
Thus, |u′i+1 | > 3k + 2 + (i + 1) + C ≥ 3k + 2 + (i + 1) + c = |u′i+1| + c ≥ |u′i+1 |.
This is a contradiction.



4.6 The Claim for gk :
79

Claim. In the sole accepted representative word for gk , the final time vertex va is
made internal occurs before the final time the vertex vb is made internal.
Proof. We begin with u′(k−l)−(C+1) , the accepted representative for u(k−l)−(C+1) . By
Lemma 4.23, we know that in u′(k−l)−(C+1) , the final time where vertex va is made
internal must occur before the first time the vertex vb is made internal. Lemma
4.22 says that no more than C of the vertices in B are internal at the final time
time when va is made internal in u′(k−l)−(C+1) . Note, this means that u′(k−l)−(C+1)
fulfills conditions (1) and (2) of Lemmas 4.25 and 4.26.
Suppose that in u′i , the accepted representative for ui (k − 1) − (C + 1) ≤ i ≤
k − 2, the following two conditions hold:
(1) The final time where vertex vb is made internal must occur before the first
time the vertex va is made internal,
(2) None of the vertices in B are internal at any time when va is made internal.
Then, by Lemma 4.25, in u′i+1 , condition (1) holds in u′i+1 . By Lemma 4.26,
condition (2) holds in u′i+1 . As both conditions hold, our induction holds. Thus,
in u′k−1, condition (1) is true, so the final time vertex va is made internal occurs
before the first time the vertex vb is made internal. But u′k−1 is the accepted
representative for uk−1 and uk−1 = gk so our claim is complete.



4.7 Conclusion of Theorem 1.1.
Completing the claims for fk and gk concludes our proof of Theorem 1.1. The
claim for fk showed that in the single accepted representative word for fk , the
final time vertex vb is made internal occurs before the final time the vertex va is
made internal. The claim for gk showed that in the single accepted representative
word for gk , the final time vertex va is made internal occurs before the final time
the vertex vb is made internal. Because fk = gk , this is the same representative
word. va and vb cannot be made internal at the same time, so this is a clear
contradiction, proving Theorem 1.1.

80

Bibliography
[Belk]

James Belk. ”Thompson’s Group F”. Preprint (2007), arXiv:/0708.3609.

[Cannon]

J. W. Cannon. “The Combinatorial Structure of Cocompact Discrete Hyperbolic
Groups”. Geom. Dedicata 16 (1984), 123-148.

[CFP]

J. W. Cannon, W. J. Floyd, and W. R. Parry. “Introductory Notes to Richard
Thompsons Groups”. LEnseignement Mathmatique 42 (1996), 215-256.

[ClTa]

Sean Cleary and Jennifer Taback. “Thompsons Group F is not Almost Convex”. J.
Algebra 270 (2003), no. 1, 133-149.

[EFZ]

D B A Epstein, A R Fletcher, U Zwick, “Growth functions and automatic groups”.
Experimental Mathematics 5 (1996), 297-315

[ECHLPT] D. B. A. Epstein, J. W. Cannon, D. F. Holt, S. V. F. Levy, M. S. Paterson, W. P.
Thurston. Word Processing in Groups. Jones and Bartlett Publishers, Boston (1992).
[Ford]

S. Blake Fordham. “Minimal Length Elements of Thompsons Group F”. Geom.
Dedicata 99 (2003), 179-220.

[Guba]

Guba, V.S. “Polynomial Isoperimetric Inequalities for Richard Thompsons Groups
F, T, and V”. Algorithmic Problems in Groups and Semigroups. pp. 91-120. Boston,
Basel, Berlin: Birkhuser 2000

[Guba2]

V. S. Guba. “The Dehn Function of Richard Thompsons Group F is Quadratic”.
Preprint (2002), arXiv:/0211395.

[Papa]

P. Papasoglu “Strongly Geodesically Automatic Groups are Hyperbolic”. Inventiones mathematicae 121 (1995), 323-334.

81

