GROUPS OF FAST HOMEOMORPHISMS OF THE INTERVAL AND THE PING-PONG ARGUMENT

COLLIN BLEAK, MATTHEW G. BRIN, MARTIN KASSABOV, JUSTIN TATCH MOORE, AND MATTHEW C. B. ZAREMSKY

Abstract. We adapt the Ping-Pong Lemma, which historically was used to study free products of groups, to the setting of the homeomorphism group of the unit interval. As a consequence, we isolate a large class of generating sets for subgroups of Homeo_{+}(I) for which certain finite dynamical data can be used to determine the marked isomorphism type of the groups which they generate. As a corollary, we will obtain a criterion for embedding subgroups of Homeo_{+}(I) into Richard Thompson’s group F. In particular, every member of our class of generating sets generates a group which embeds into F and in particular is not a free product. An analogous abstract theory is also developed for groups of permutations of an infinite set.

1. Introduction

The ping-pong argument was first used in [13, §III,16] and [11, §II,3.8] to analyze the actions of certain groups of linear fractional transformations on the Riemann sphere. Later distillations and generalizations of the arguments (e.g., [14, Theorem 1]) were used to establish that a given group is a free product. In the current paper we will adapt the ping-pong argument to the setting of subgroups of Homeo_{+}(I), the group of the orientation preserving homeomorphisms of the unit interval. Our main motivation is to develop a better understanding of the finitely generated subgroups of the group PL_{+}(I) of piecewise linear order-preserving homeomorphisms of the unit interval. The analysis in the current paper resembles the original ping-pong argument in that it establishes a tree structure on certain orbits of a group action. However, the arguments in the current paper differ from the usual analysis as the generators of the group action have large sets of fixed points.

The focus of our attention in this article will be subgroups of Homeo_{+}(I) which are specified by what we will term geometrically fast generating sets. On one hand, our main result shows that the isomorphism types of the groups specified by geometrically fast generating sets are determined by their dynamical diagram which encodes their qualitative dynamics; see Theorem 1.1 below. This allows us

2010 Mathematics Subject Classification. 20B07, 20B10, 20E07, 20E34, 20F65. Key words and phrases. algebraically fast, dynamical diagram, free group, geometrically fast,

geometrically proper, homeomorphism group, piecewise linear, ping-pong lemma, symbol space, symbolic dynamics, Thompson’s group, transition chain.

Acknowledgments: The authors would like to thank the two anonymous referees for their careful reading of the paper and for offering a number of useful comments. This paper was prepared in part during a visit of the first and fourth author to the Mathematisches Forschungsinstitut Oberwolfach, Germany in December 2016 as part of their Research In Pairs program. The research of the third author was supported in part by NSF grant DMS-1601406; the fourth author was supported in part by NSF grant DMS-1262019.

[figure: b_{0}; b_{2}; b_{1}]

Figure 1. Three homeomorphisms

to show, for instance, that such sets generate groups which are always embeddable into Richard Thompson’s group F. On the other hand, we will see that a broad class of subgroups of PL_{+}(I) can be generated using such sets. This is substantiated in part by Theorem 1.5 below.

At this point it is informative to consider an example. First recall the classical Ping-Pong Lemma (see [16, Prop. 1.1]):

Ping Pong Lemma. Let S be a set and A be a set of permutations of S such that a^{−1} ∉ A for all a ∈ A. Suppose there is an assignment a ↦ D_{a} ⊆ S of pairwise disjoint sets to each a ∈ A^{±} := A ∪ A^{−1} and an x ∈ S \ ⋃_{a∈A^{±}} D_{a} such that if a ≠ b^{−1} are in A^{±}, then

(D_{b} ∪ {x})a ⊆ D_{a}.

Then A freely generates ⟨A⟩.

(We adopt the convention of writing permutations to the right of their arguments; other notational conventions and terminology will be reviewed in Sections 2 and 3.) In the current paper, we relax the hypothesis so that the containment D_{b}a ⊆ D_{a} is required only when D_{b} intersects the support of a; similarly xa ∈ D_{a} is only required when xa ≠ x.

Consider the three functions (b_{i} | i < 3) in Homeo_{+}(I) whose graphs are shown in Figure 1. A schematic diagram (think of the line y = x as drawn horizontally) of these functions might be:

b_{0}  b_{1}  b_{2} ∘ S_{0}  ∘ S_{1}  • D_{0}  ∘ D_{2}  • D_{1}  • S_{2}

In this diagram, we have assigned intervals S_{i} and D_{i} to the ends of the support to each b_{i} so that the entire collection of intervals is pairwise disjoint. Our system of homeomorphisms is assumed to have an additional dynamical property reminiscent of the hypothesis of the Ping-Pong Lemma:

• S_{i}b_{i} ∩ D_{i} = ∅;

• b_{i} carries supt(b_{i}) \ S_{i} into D_{i};
• b_{i}^{−1} carries supt(b_{i}) \ D_{i} into S_{i} for each i.

A special case of our main result is that these dynamical requirements on the b_{i}’s are sufficient to characterize the isomorphism type of the group ⟨b_{i} | i < 3⟩: any triple (c_{i} | i < 3) which produces this same dynamical diagram and satisfies these dynamical requirements will generate a group isomorphic to ⟨b_{i} | i < 3⟩. In fact the map b_{i} ↦ c_{i} will extend to an isomorphism. In particular,

⟨b_{i} | i < 3⟩ ≅ ⟨b_{i}^{k_{i}} | i < 3⟩

for any choice of k_{i} ≥ 1 for each i < 3.

We will now return to the general discussion and be more precise. Recall that if f is in Homeo_{+}(I), then its support is defined to be supt(f) := {t ∈ I | tf ≠ t}; the support of a subset of Homeo_{+}(I) is the union of the supports of its elements. A left (right) transition point of f is a t ∈ I \ supt(f) such that for every ϵ > 0, (t, t + ϵ) ∩ supt(f) ≠ ∅ (respectively (t − ϵ, t) ∩ supt(f) ≠ ∅). An orbital of either an element or subgroup of Homeo_{+}(I) is a component its support. An orbital of f is positive if f moves elements of the orbital to the right; otherwise it is negative. If f has only finitely many orbitals, then the left (right) transition points of f are precisely the left (right) end points of its orbitals.

A precursor to the notion of a geometrically fast generating set is that of a geometrically proper generating set. A set X ⊆ Homeo_{+}(I) is geometrically proper if there is no element of I which is a left transition point of more than one element of X or a right transition point of more than one element of X. Observe that any geometrically proper generating set with only finitely many transition points is itself finite. Furthermore, geometrically proper sets are equipped with a canonical ordering induced by the usual ordering on the least transition points of its elements. While the precise definition of geometrically fast will be postponed until Section 3, the following statements describe the key features of the definition:

• geometrically fast generating sets are geometrically proper.

• if {a_{i} | i < n} is geometrically proper, then there is a k ≥ 1 such that {a_{i}^{k} | i < n} is geometrically fast.

• if {a_{i}^{k} | i < n} is geometrically fast and k ≤ k_{i} for i < n, then {a_{i}^{k_{i}} | i < n}

is geometrically fast. Our main result is that the isomorphism types of groups with geometrically fast generating sets are determined by their qualitative dynamics. Specifically, we will associate a dynamical diagram to each geometrically fast set {a_{i} | i < n} ⊆ Homeo_{+}(I) which has finitely many transition points. Roughly speaking, this is a record of the relative order of the orbitals and transition points of the various a_{i}, as well as the orientations of their orbitals. In the following theorem M_{X} is a certain finite set of points chosen from the orbitals of elements of X and M⟨X⟩ = {tg | t ∈ M_{X} and g ∈ ⟨X⟩}. These points will be chosen such that any nonidentity element of ⟨X⟩ moves a point in M⟨X⟩.

Theorem 1.1. If two geometrically fast sets X, Y ⊆ Homeo_{+}(I) have only finitely many transition points and have isomorphic dynamical diagrams, then the induced bijection between X and Y extends to an isomorphism of ⟨X⟩ and ⟨Y ⟩ (i.e. ⟨X⟩ is marked isomorphic to ⟨Y ⟩). Moreover, there is an order preserving bijection θ : M⟨X⟩ → M⟨Y ⟩ such that f ↦ f^{θ} induces the isomorphism ⟨X⟩ ≅ ⟨Y ⟩.

We will also establish that under some circumstances the map θ can be extended to a continuous order preserving surjection θ̂: I → I.

Theorem 1.2. For each finite dynamical diagram D, there is a geometrically fast X_{D} ⊆ PL_{+}(I) such that if X ⊆ Homeo_{+}(I) is geometrically fast and has dynamical diagram D, then there is a marked isomorphism ϕ : ⟨X⟩ → ⟨X_{D}⟩ and a continuous order preserving surjection θ̂ : I → I such that fθ̂ = θ̂ϕ(f) for all f ∈ ⟨X⟩. Furthermore, every orbit of the action of ⟨X_{D}⟩ on (0, 1) is dense.

Theorem 1.1 has two consequences. The first is proved at the end of Section 8:

Corollary 1.3. Any finitely generated subgroup of Homeo_{+}(I) which admits a geometrically fast generating set with only finitely many transition points embeds into Thompson’s group F.

Since by [7] F does not contain nontrivial free products of groups, subgroups of Homeo_{+}(I) which admit geometrically fast generating sets are not free products. It should also be remarked that while our motivation comes from studying the groups F and PL_{+}(I), the conclusion of Corollary 1.3 remains valid if F is replaced by, e.g. Diff_{+}^{∞}(I).

Secondly, geometrically fast generating sets are algebraically fast in the following sense:

Corollary 1.4. If {f_{i} | i < n} is geometrically fast, then ⟨f_{i} | i < n⟩ is marked isomorphic to ⟨f_{i}^{k_{i}} | i < n⟩ for any choice of k_{i} ≥ 1.

It is natural to ask how restrictive having a geometrically fast or geometrically proper generating set is. The next theorem shows that many finitely generated subgroups of PL_{+}(I) in fact do have at least a geometrically proper generating set.

Theorem 1.5. Every n-generated one orbital subgroup of PL_{+}(I) either contains an isomorphic copy of F or else admits an n-element geometrically proper generating set.

Notice that every subgroup of Homeo_{+}(I) is contained in a direct product of oneorbital subgroups of Homeo_{+}(I). Thus if one’s interest lies in studying the structure of subgroups of PL_{+}(I) which do not contain copies of F, then it is typically possible to restrict one’s attention to groups admitting geometrically proper generating sets. The hypothesis of not containing an isomorphic copy of F in Theorem 1.5 can not be eliminated. This is a consequence of the following theorem and the fact that there are finite index subgroups of F which are not isomorphic to F (see [3]).

Theorem 1.6. If a finite index subgroup of F is isomorphic to ⟨X⟩ for some geometrically proper X ⊆ Homeo_{+}(I), then it is isomorphic to F.

We conjecture, however, that every finitely generated subgroup of F is bi-embeddable with a subgroup admitting a geometrically fast generating set.

While the results of this paper do of course readily adapt to Homeo_{+}(R) ≅ Homeo_{+}(I), it is important to keep in mind that ±∞ must be allowed as possible transition points when applying the definition of geometric properness and hence geometric fastness. For example, it is easy to establish that ⟨t + sin(t), t + cos(t)⟩ contains a free group using the ping-pong lemma stated above (the squares of the generators generate a free group). Moreover, once we define geometrically fast in Section 3, it will be apparent that the set of squares of the generators satisfies all of the requirements of being geometrically fast except that it is not geometrically proper (since, e.g., ∞ is a right transition point of both functions). As noted above, this group does not embed into F and thus does not admit a geometrically fast (or even a geometrically proper) generating set. See Example 3.1 below for a more detailed discussion of a related example.

The paper is organized as follows. We first review some standard definitions, terminology and notation in Section 2. In Section 3, we will give a formal definition of geometrically fast and a precise definition of what is meant by a dynamical diagram. Section 4 gives a reformulation of geometrically fast for finite subsets of Homeo_{+}(I) which facilitates algorithmic verification. The proof of Theorem 1.1 is then divided between Sections 5 and 6. The bulk of the work is in Section 5, which uses an analog of the ping-pong argument to study the dynamics of geometrically fast sets of one orbital homeomorphisms. The proofs are done axiomatically, anticipating the more general framework in Section 11. Section 6 shows how this analysis implies Theorem 1.1 and how to derive its corollaries. In Section 7, we will prove Theorem 1.2. The group F_{n}, which is the n-ary analog of Thompson’s group F, is shown to have a geometrically fast generating set in Section 8. Section 9 examines when bumps in geometrically fast generating sets are extraneous and can be excised without affecting the marked isomorphism type. Proofs of Theorems 1.5 and 1.6 are given in Section 10. Finally, the concept of geometrically fast is abstracted in Section 11, where a generalization of Theorem 1.1 is stated and proved, as well as corresponding embedding theorems for Thompson’s groups F, T, and V. This generalization in particular covers infinite geometrically fast subsets of Homeo_{+}(I). Even in the context of geometrically fast sets X ⊆ Homeo_{+}(I) with only finitely many transition points, this abstraction gives a new way of understanding ⟨X⟩ in terms of symbolic manipulation.

2. Preliminary definitions, notation and conventions

In this section we collect a number of definitions and conventions which will be used extensively in later sections. Throughout this paper, the letters i, j, k, m, n will be assumed to range over the nonnegative integers unless otherwise stated. For instance, we will write (a_{i} | i < k) to denote a sequence with first entry a_{0} and last entry a_{k−1}. In particular, all counting and indexing starts at 0 unless stated otherwise. If f is a function and X is a subset of the domain of f, we will write f ↾ X to denote the restriction of f to X.

As we have already mentioned, Homeo_{+}(I) will be used to denote the set of all orientation preserving homeomorphisms of I; PL_{+}(I) will be used to denote the set of all piecewise linear elements of Homeo_{+}(I). These groups will act on the right. In particular, tg will denote the result of applying a homeomorphism g to a point t. If f and g are elements of a group, we will write f^{g} to denote g^{−1}fg.

Recall from the introduction that if f is in Homeo_{+}(I), then its support is defined to be supt(f) := {t ∈ I | tf ≠ t}. The support of a subset of Homeo_{+}(I) is the union of the supports of its elements. A left (right) transition point of f is a t ∈ I \ supt(f) such that for every ϵ > 0, (t, t + ϵ) ∩ supt(f) ≠ ∅ (respectively (t−ϵ, t)∩supt(f) ≠ ∅). An orbital of f is a component of its support. An orbital of f is positive if f moves elements of the orbital to the right; otherwise it is negative. If f has only finitely many orbitals, then the left (right) transition points of f are precisely the left (right) end points of its orbitals. An orbital of a subset of Homeo_{+}(I) is a component of its support.

An element of Homeo_{+}(I) with one orbital will be referred to as a bump function (or simply a bump). If a bump a satisfies that ta > t on its support, then we say that a is positive; otherwise we say that a is negative. If f ∈ Homeo_{+}(I), then b ∈ Homeo_{+}(I) is a signed bump of f if b is a bump which agrees with f on its support. If X is a subset of Homeo_{+}(I), then a bump a is used in X if a is positive and there is an f in X such that f coincides with either a or a^{−1} on the support of a. A bump a is used in f if it is used in {f}. We adhere to the convention that only positive bumps are used by functions to avoid ambiguities in some statements. Observe that if X ⊆ Homeo_{+}(I) is such that the set A of bumps used in X is finite, then ⟨X⟩ is a subgroup of ⟨A⟩.

If (g_{i} | i < n) and (h_{i} | i < n) are two generating sequences for groups, then we will say that ⟨g_{i} | i < n⟩ is marked isomorphic to ⟨h_{i} | i < n⟩ if the map g_{i} ↦ h_{i} extends to an isomorphism of the respective groups. If X is a finite geometrically proper subset of Homeo_{+}(I), then we will often identify X with its enumeration in which the minimum transition points of its elements occur in increasing order. When we write ⟨X⟩ is marked isomorphic to ⟨Y ⟩, we are making implicit reference to these canonical enumerations of X and Y.

At a number of points in the paper it will be important to distinguish between formal syntax (for instance words) and objects (such as group elements) to which they refer. If A is a set, then a string of elements of A is a finite sequence of elements of A. The length of a string w will be denoted |w|. We will use ε to denote the string of length 0. If u and v are two strings, we will use uv to denote their concatenation; we will say that u is a prefix of uv and v is a suffix of uv. If A is a subset of a group, then an A-word is a string of elements of A^{±} := A ∪ A^{−1}; we will write word if A is clear from the context. A subword of a word w must preserve the order from w, but does not have to consist of consecutive symbols from w. We write w^{−1} for the formal inverse of w: the product of the inverses of the symbols in w in reverse order.

Often strings have an associated evaluation (e.g. a word represents an element of a group). While the context will often dictate whether we are working with a string or its evaluation, we will generally use the typewriter font (e.g. w) for strings and symbols in the associated alphabets and standard math font (e.g. w) for the associated evaluations.

In Section 10, we will use the notion of the left (right) germ of a function f ∈ Homeo_{+}(I) at an s ∈ I which is fixed by f (left germs are undefined at 0 and right germs are undefined at 1). If 0 ≤ s < 1, then define the right germ of f at s to be the set of all g ∈ Homeo_{+}(I) such that for some ϵ > 0, f ↾ (s, s + ϵ) = g ↾ (s, s + ϵ); this will be denoted by γ_{s}^{+}(f). Similarly if 0 < s ≤ 1, then one defines the left germ of f at s; this will be denoted by γ_{s}^{−}(f). The collections

{γ_{s}^{+}(f) | f ∈ Homeo_{+}(I) and sf = s}
{γ_{s}^{−}(f) | f ∈ Homeo_{+}(I) and sf = s}

form groups and the functions γ_{s}^{+} and γ_{s}^{−} are homomorphisms defined on the subgroup of Homeo_{+}(I) consisting of those functions which fix s.

3. Fast collection of bumps and their dynamical diagrams

We are now ready to turn to the definition of geometrically fast in the context of finite subsets of Homeo_{+}(I). First we will need to develop some terminology. A

[figure: a_{0}; a_{1}; p; q; r; s; t]

Figure 2. A geometrically fast set of bumps

marking of a geometrically proper collection of positive bumps A is an assignment of a marker t ∈ supt(a) to each a in A; if t is the marker of a, then we also regard t as the marker of a^{−1}. If a ∈ A has support (x, y) and marker t, then we define its source to be the interval src(a) := (x, t) and its destination to be the interval dest(a) := [ta, y). We also set src(a^{−1}) := dest(a) and dest(a^{−1}) := src(a). The source and destination of a marked set of bumps are collectively called its feet. Note that there is a deliberate asymmetry in this definition: the source of a positive bump is an open interval whereas the destination is half open. This choice is necessary so that for any t ∈ supt(a), there is a unique k such that ta^{k} is not in the feet of a, something which is a key feature of the definition.

A collection A of bumps is geometrically fast if there is a marking of A for which its feet form a pairwise disjoint family (in particular we require that A is geometrically proper). This is illustrated in Figure 2, where the feet of a_{0} are (p, q) and [r, s) and the feet of a_{1} are (q, r) and [s, t). Being geometrically fast is precisely the set of dynamical requirements made on the set {a_{i} | i < 3} of homeomorphisms mentioned in the introduction. We do not require here that A is finite and we will explicitly state finiteness as a hypothesis when it is needed. Notice however that, since pairwise disjoint families of intervals in I are at most countable, any geometrically fast set of bumps is at most countable. The following are readily verified and can be used axiomatically to derive most of the lemmas in Section 5 (specifically Lemmas 5.1–5.11):

• for all a ∈ A^{±}, dest(a) ⊆ supt(a) and if x ∈ supt(a) then there exists a k such that xa^{k} ∈ dest(a);

• if a ≠ b ∈ A^{±}, then dest(a) ∩ dest(b) = ∅;

• if a ∈ A^{±} and x ∈ supt(a), then xa ∈ dest(a) if and only if x ∉ src(a) := dest(a^{−1}).

• if a, b ∈ A^{±}, then dest(a) ⊆ supt(b) or dest(a) ∩ supt(b) = ∅.

This axiomatic viewpoint will be discussed further in Section 11.

The definition of geometrically fast readily extends to sets of functions which possibly use more than one bump: a set X ⊆ Homeo_{+}(I) is geometrically fast if it is geometrically proper and the set of bumps used in X is geometrically fast. Note that while geometric properness is a consequence of the disjointness of the feet if X uses only finitely many bumps, it is an additional requirement in general. This is illustrated in the next example.

Example 3.1. Consider the following homeomorphism of R:

tγ = \begin{cases}3t & if 0 ≤ t ≤ 1/2 \\ (t + 4)/3 & if 1/2 ≤ t ≤ 2 \\ t & otherwise \end{cases}

Define α, β ∈ Homeo_{+}(R) by (t + 2p)α = tγ + 2p and (t + 2p + 1)β = tγ + 2p + 1 where p ∈ Z and t ∈ [0, 2]. Thus the bumps used in α are obtained by translating γ by even integers; the bumps in β are the translates of γ by odd integers. If we assign the marker 1/2 to γ and mark the translation of γ by p with p + 1/2, then it can be seen that the feet of α and β are the intervals {(p, p + 1/2) | p ∈ Z} ∪ {[p + 1/2, p + 1) | p ∈ Z}, which is a pairwise disjoint family. Thus the bumps used in {α, β} are geometrically fast. Since ∞ is a right transition point of both α and β, {α, β} is not geometrically proper and hence not fast. In fact, it follows readily from the formulation of the classical ping-pong lemma in the introduction that ⟨α, β⟩ is free.

Observe that if X is geometrically proper, if each of its elements uses only finitely many bumps, and if the set of transition points of X is discrete, then there is a map f ↦ k(f) of X into the positive integers such that {f^{k(f)} | f ∈ X} is geometrically fast. To see this, start with a marking such that the closures of the sources of the bumps used in X are disjoint; pick f ↦ k(f) sufficiently large so that all of the feet become disjoint. Also notice that if {f^{k(f)} | f ∈ X} is geometrically fast and if k(f) ≤ l(f) for f ∈ X, then {f^{l(f)} | f ∈ X} is geometrically fast as well.

If X is a geometrically fast generating set with only finitely many transition points, then the dynamical diagram D_{X} of X is the edge labeled vertex ordered directed graph defined as follows:

• the vertices of D_{X} are the feet of X with the order induced from the order of the unit interval;

• the edges of D_{X} are the signed bumps of X directed so that the source (destination) of the edge is the source (destination) of the bump;

• the edges are labeled by the elements of X that they come from. Notice that, given our assumptions, the dynamical diagram of X is necessarily finite. The dynamical diagram of a generating set for the Brin-Navas group B [5] [15] is illustrated in the left half of Figure 3; the generators are f = a_{0}^{−1}a_{2} and g = a_{1}^{−1}, where the (a_{i} | i < 3) is the geometrically fast generating sequence illustrated in Figure 4. We have found that when drawing dynamical diagram D_{X} of a given X, it is more æsthetic whilst being unambiguous to collapse pairs of vertices u and v of D_{X} such that:

• v is the immediate successor of u in the order on D_{X},

• u’s neighbor is below u, and v’s neighbor is above v. Additionally, arcs can be drawn as over or under arcs to indicate their direction, eliminating the need for arrows. This is illustrated in the right half of Figure 3. The result qualitatively resembles the graphs of the homeomorphisms rotated so that the line y = x is horizontal.

An isomorphism between dynamical diagrams is a directed graph isomorphism which preserves the order of the vertices and induces a bijection between the edge labels (i.e. two directed edges have equal labels before applying the isomorphism if and only if they have equal labels after applying the isomorphism). Notice that

\xymatrix{• & • & • \ar[ll]^{f} & • \ar[rr]^{f} & • \ar[lll]^{g} & •}  •  •  •_{f}  ^{f}•_{g}  •

Figure 3. The dynamical diagram for the Brin-Navas generators, with an illustration of the contraction convention

[figure: a_{0}; a_{1}; a_{2}]

Figure 4. A point is tracked through a fast transition chain

such an isomorphism is unique if it exists — there is at most one order preserving bijection between two finite linear orders.

Observe that the (uncontracted) dynamical diagram of any geometrically fast X ⊆ Homeo_{+}(I) which has finitely many transition points has the property that all of its vertices have total degree 1. Moreover, any finite edge labeled vertex ordered directed graph in which each vertex has total degree 1 is isomorphic to the dynamical diagram of some geometrically fast X ⊆ Homeo_{+}(I) which has finitely many transition points (see the proof of Theorem 1.2 in Section 7). Thus we will write dynamical diagram to mean a finite edge labeled vertex ordered directed graph in which each vertex has total degree 1. The edges in a dynamical diagram will be referred to as bumps and the vertices in a dynamical diagram will be referred to as feet. Terms such as source, destination, left/right foot will be given the obvious meaning in this context.

Now let A be a geometrically fast set of positive bump functions. An element of A is isolated (in A) if its support contains no transition points of A. In the dynamical diagram of A, this corresponds to a bump whose source and destination are consecutive feet. The next proposition shows that we may always eliminate isolated bumps in A by adding new bumps to A. This will be used in Section 7.

Proposition 3.2. If A ⊆ Homeo_{+}(I) is a geometrically fast set of positive bump functions, then there is a geometrically fast B ⊆ Homeo_{+}(I) such that A ⊆ B and B has no isolated bumps. Moreover, if A is finite, then B can be taken to be finite as well.

Proof. If a ∈ A is isolated, let b_{0} and b_{1} be a geometrically fast pair of bumps with supports contained in supt(a) \ (src(a) ∪ dest(a)) such that neither b_{0} nor b_{1} is isolated in {b_{0}, b_{1}}; see Figure 5. Since the feet of A are disjoint, so are the feet

\xymatrix{• \ar[rrrrr]^{a} & • \ar[rr]^{b_{0}} & • \ar[rr]^{b_{1}} & • & • & •}

Figure 5. The bump a is made nonisolated by the addition of bumps b_{0} and b_{1}.

of A ∪ {b_{0}, b_{1}} and a is no longer isolated in A ∪ {b_{0}, b_{1}}. Let B be the result of adding such a pair of bumps for each isolated bump in A. □

4. An algorithmic criterion for geometric fastness

In this section we will consider geometrically proper sets which have finitely many transition points and develop a characterization of when they are geometrically fast. This characterization moreover allows one to determine algorithmically when such sets are geometrically fast. It will also provide a canonical marking of geometrically fast sets with finitely many transition points. We need the following refinement of the notion of a transition chain introduced in [2].

Let A ⊆ Homeo_{+}(I) be a finite geometrically proper set of positive bump functions. Let (a_{i} | i ≤ k) be a sequence of non-isolated elements of A and let x_{i} < y_{i} denote the endpoints of the support of a_{i}. The sequence C = (a_{i} | i ≤ k) is a stretched transition chain of A if:

(1) for all i < k, x_{i} < x_{i+1} < y_{i} < y_{i+1};

(2) no transition point of A is in any interval (x_{i+1}, y_{i}). Thus if 1 ≤ i ≤ k, then y_{i−1} is the least transition point of A in the support of a_{i} and if 0 ≤ i < k, then x_{i+1} is the greatest transition point of A in the support of a_{i}. Define C_{min} to be the least transition point of A in the support of a_{0} and C_{max} to be the greatest transition point of A in the support of a_{k}. Note that, in spite of the notation, C_{min} and C_{max} depend on A as well as on C.

Notice that the ordering on the x_{i}’s is increasing and because of this we will identify the stretched transition chain (a_{i} | i ≤ k) with the set {a_{i} | i ≤ k}. A stretched transition chain is maximal if it is maximal among stretched transition chains with respect to containment when regarded as a subset of A. An element a of A is initial if it is either isolated or if the least transition point of A in the support of a is not the right transition point of some element of A. It follows from Proposition 4.1 below that a non-isolated initial element of A is the leftmost element of a unique maximal stretched transition chain.

Figure 6 shows a dynamical diagram, along with a list of the maximal stretched transition chains.

Proposition 4.1. If A is a finite geometrically proper set of positive bump functions in Homeo_{+}(I), then the maximal stretched transition chains in A partition the nonisolated elements of A.

Remark 4.2. We will see in Section 8 that geometrically fast stretched transition chains of length n generate F_{n}, the n-ary analog of Thompson’s group F. Thus if A is geometrically fast, then ⟨A⟩ is a sort of amalgam of copies of the F_{n} and copies of Z.

\xymatrix{• \ar[rrr]^{a_{0}} & • \ar[rrrrr]^{a_{1}} & • \ar[rrrrrrr]^{a_{2}} & • \ar[rrrr]^{a_{3}} & • \ar[r]^{a_{4}} & • \ar[rrr]^{a_{5}} & • & • & • & •}

Figure 6. The maximal stretched transition chains in this dynamical diagram are {a_{0}, a_{2}}, {a_{1}, a_{5}}, and {a_{3}}; a_{4} is isolated

Proof. First observe that any sequence consisting of a single nonisolated element of A is a stretched transition chain and thus is a subsequence of some maximal stretched transition chain in A. Next suppose that a and b are consecutive members of a stretched transition chain. It follows that b’s left transition point is in the support of a and is the greatest transition point of A in the support of a. In particular, b must immediately follow a in any maximal stretched transition chain. Similarly, a must immediately precede b in any maximal stretched transition chain. This shows that every nonisolated element of A occurs in a unique maximal stretched transition chain of A. □

Proposition 4.3. If A ⊆ Homeo_{+}(I) is a finite geometrically proper set of positive bump functions, then the following are equivalent:

(1) A is geometrically fast;

(2) every stretched transition chain C of A satisfies C_{max} ≤ C_{min} ∏ C.

(3) every maximal stretched transition chain C of A satisfies C_{max} ≤ C_{min} ∏ C.

Remark 4.4. This criterion for being geometrically fast was our original motivation for the choice of the terminology: the dynamics of the homeomorphisms are such that transition points can be moved to the right through transition chains as efficiently as possible. This is illustrated in Figure 4.

Remark 4.5. The choice not to allow isolated bumps to be singleton stretched transition chains is somewhat arbitrary, although it would be necessary to make awkward adjustments to the definitions above if we took the alternate approach. It seems appropriate to omit them since they play no role in determining whether a group is fast other than contributing to the collective set of transition points of the set of bumps under consideration.

Proof. To see that (1) implies (2), let A be given equipped with a fixed marking witnessing that it is geometrically fast. Let C = (a_{i} | i ≤ k) and let s_{i} denote the marker of a_{i}. Notice that if t is a transition point of A which is in the support of a_{i}, then s_{i} ≤ t ≤ s_{i}a_{i}; otherwise a foot adjacent to t would intersect a foot of a_{i}. Further s_{i}a_{i} is in the support of a_{i+1} since the left transition point of a_{i+1} is in the support of a_{i} by (1) in the definition of stretched transition chain. Therefore the left foot of a_{i+1} is to the left of the right foot of a_{i} and so s_{i+1} ≤ s_{i}a_{i}. We now have inductively that s_{k} ≤ s_{0}a_{0} ⋯ a_{k−1} and hence

C_{max} ≤ s_{k}a_{k} ≤ s_{0}a_{0} ⋯ a_{k} ≤ C_{min}a_{0} ⋯ a_{k}.

Of course (2) implies (3) is immediate.

We prove that (3) implies (1). We assign markers to A as follows. If a is isolated, its marker is the midpoint of its support. We mark the rest of the elements of A according to the maximal stretched transition chain to which they belong. Let C = {a_{i} | i ≤ k} be a maximal stretched transition chain and let x_{i} < y_{i} be the endpoints of the support of a_{i}. Set s_{0} := C_{min} and for 1 ≤ i ≤ k set s_{i} := s_{0}a_{0}a_{1} ⋯ a_{i−1}.

We argue inductively from (3) that for 1 ≤ i ≤ k we have x_{i} < s_{i} < y_{i−1}. We start with the second inequality. Since s_{0} is in the support of a_{0}, we have s_{1} = s_{0}a_{0} < y_{0}. Now if s_{i} < y_{i−1}, then s_{i} < y_{i} and s_{i+1} = s_{i}a_{i} < y_{i}. Now assume the first inequality is false and let j ≤ k be least so that s_{j} ≤ x_{j}. This means that for j ≤ i ≤ k we have that s_{j} ≤ x_{i} and that s_{j} is to the left of the support of a_{i}. So for j ≤ i ≤ k, we have s_{i} = s_{j}a_{j}a_{j+1} ⋯ a_{i−1} = s_{j}. Since C_{max} is in the support of a_{k}, we cannot have s_{0}ΠC = s_{j}a_{j}a_{j+1} ⋯ a_{k−1}a_{k} ≥ C_{max} violating (3).

With the marking of each a_{i} in C by s_{i}, we have that the feet of a_{i} are (x_{i}, s_{i}), and [s_{i}a_{i}, y_{i}). We have s_{0} = C_{min}, we have s_{k}a_{k} ≥ C_{max}, and for 0 ≤ i < k, we have s_{i}a_{i} = s_{i+1}. Thus we have:

• the feet of a_{0} are (x_{0}, C_{min}) and [s_{1}, y_{0});
• the feet of a_{k} are (x_{k}, s_{k}) and [s_{k}a_{k}, y_{k}) ⊆ (C_{max}, y_{k});
• for 1 ≤ i < k, the feet of a_{i} are (x_{i}, s_{i}) and [s_{i+1}, y_{i}).

For 1 ≤ i ≤ k, the interval (x_{i}, y_{i−1}) is divided into two disjoint feet. Since the intervals (x_{i}, y_{i−1}) are pairwise disjoint, since s_{0} = C_{min} ≤ x_{1}, and since s_{k}a_{k} ≥ C_{max} ≥ y_{k−1}, we have that the feet of C are pairwise disjoint. In addition, the definition of stretched transition chain and the definitions of C_{min} and C_{max} give us that none of the interiors of the feet of C contain a transition point of A.

It remains to be shown that feet coming from different maximal stretched transition chains and/or isolated elements of A are disjoint. Suppose for contradiction that there are two feet K and K′ of A that intersect. Let a and a′ be the elements of A whose feet include K and K′, respectively. One endpoint t of K is a transition point of a, and the other endpoint s of K is not. A similar statement describes the endpoints t′ and s′ of K′. Since the interiors of K and K′ contain no transition points of A, the interval J := K ∪ K′ has no transition points of A in its interior. Thus t and t′ are among the endpoints of J. If t = t′ were a single endpoint of J, then t and t′ violate our assumption of geometric properness. Thus t ≠ t′ are distinct and, by exchanging the roles of a and a′ if necessary, we may assume t < t′. Observe that this forces t to be the left transition point of a and t′ to be the right transition point of a′. Furthermore, there are no transition points of A strictly between t and t′. Thus a and a′ are consecutive entries in a maximal stretched transition chain. However, the feet of a single maximal stretched transition chain were shown above to be disjoint, a contradiction. This completes the proof that (3) implies (1). □

Observe that the proof of Proposition 4.3 gives an explicit construction of a marking of a family A of positive bumps. This marking has the property that if A is geometrically fast, then it is witnessed as such by the marking. We will refer to this marking as the canonical marking of A.

Finally, let us note that Proposition 4.3 gives us a means to algorithmically determine whether a set of positive bumps A is fast. Specifically, perform the following sequence of steps:

• determine whether A is geometrically proper; • if so, partition the non isolated elements of A into maximal stretched tran-

sition chains;

• for each maximal stretched transition chain C of A, determine whether C_{max} ≤ C_{min} ∏ C.

This is possible provided we are able to perform the following basic queries:

• test for equality among the transition points of elements of A;

• determine the order of the transition points of elements of A;

• determine the truth of C_{max} ≤ C_{min} ∏ C whenever C is a stretched transition chain.

5. The ping-pong analysis of geometrically fast sets of bumps

In this section, we adapt the ping-pong argument to the setting of fast families of bump functions. While the culmination will be Theorem 5.12 below, the lemmas we will develop will be used in subsequent sections. They also readily adapt to the more abstract setting of Section 11.

Until we reach Theorem 5.12, we will work only with finite fast collections of positive bumps. Fix, until further notice, a finite geometrically fast collection A of positive bumps equipped with a marking; in particular we will write word to mean A-word. Central to our analysis will be the notion of a locally reduced word. A word w is locally reduced at t if it is freely reduced and whenever ua is a prefix of w for a ∈ A^{±}, tua ≠ tu. If w is locally reduced at every element of a set J ⊆ I, then we write that w is locally reduced on J.

The next lemma collects a number of useful observations about locally reduced words; we omit the obvious proofs. Recall that if u and v are freely reduced, then the free reduction of uv has the form u_{0}v_{0} where u = u_{0}w, v = w^{−1}v_{0}, and w is the longest common suffix of u and v^{−1}. In particular, if u, v, and w are freely reduced words and the free reductions of uv and uw coincide, then v = w.

Lemma 5.1. All of the following are true:

• For all x ∈ I and all words w, there is a subword v of w which is locally reduced at x so that xv = xw.

• For all x ∈ I and words u and v, if u is locally reduced at x, and v is locally reduced at xu, then the free reduction of uv is locally reduced at x.

• For all x ∈ I and words w, if w is locally reduced at x and w = uv, then u is locally reduced at x and v is locally reduced at xu.

• For all x ∈ I and words w, if w is locally reduced at x, then w^{−1} is locally reduced at xw.

(Recall here our convention that a subword is not required to consist of consecutive symbols of the original word.) For x ∈ I, we use x⟨A⟩ to denote the orbit of x under the action of ⟨A⟩ and for S ⊆ I, we let S⟨A⟩ be the union of those x⟨A⟩ for x ∈ S.

A marker t of A is initial if whenever s < t is the marker of a ∈ A, then t ≠ sa. Define M_{A} be the set of initial markers of A. We will generally suppress the subscript if the meaning is clear from the context; in particular we will write M⟨A⟩ for M_{A}⟨A⟩. (The only reason we assume that A is finite is so that every marker is in the orbit of an initial marker.)

Aside from developing lemmas for the next section, the goal of this section is to prove that the action of ⟨A⟩ on M⟨A⟩ is faithful. The next lemma is the manifestation of the ping-pong argument in the context in which we are working. If w ≠ ε is a word, the source (destination) of w is the source of the first (destination of the last) symbol in w. The source and destination of ε are ∅.

Lemma 5.2. If x ∈ I and w ≠ ε is a word which is locally reduced at x, then either x ∈ src(w) or xw ∈ dest(w).

Proof. The proof is by induction on the length of w. We have already noted that if w consists of a single symbol a and t ∈ supt(a), then ta ∈ dest(a) = dest(w) if and only if t ∉ src(a) = src(w). Next suppose that w has length at least 2, x ∉ src(w), and let v be a (possibly empty) word such that w = vab for a, b ∈ A^{±}. Since w is locally reduced, b ≠ a^{−1} and thus the destination of a is not the source of b. Since A is geometrically fast, the destination of a is disjoint from the source of b. By our inductive hypothesis, y = xva is in dest(a) ⊆ supt(b)\src(b). Thus xw = xvab = yb is in the destination of b. □

If w is a word, define J(w) := supt(a) \ src(a) where a is the first symbol of w. Notice that if w is locally reduced at x, then “x ∈ J(w)” is equivalent to “x ∉ src(w).” The following lemma is easily established by induction on the length of w using Lemma 5.2.

Lemma 5.3. If w is a word and x ∈ J(w), then w is locally reduced at x if and only if w is freely reduced and dest(a) ⊆ supt(b) whenever ab are consecutive symbols in w. In particular, if w is freely reduced, then w is locally reduced on J(w) provided w is locally reduced at some element of J(w).

When applying Lemma 5.2, it will be useful to be able to assume that x is not in src(w). Notice that if x is not in the feet of any element of A, then this is automatically true (for instance this is true if x ∈ M). The next lemma captures an important consequence of Lemma 5.2.

Lemma 5.4. Suppose x_{0}, x_{1} ∈ I, u_{i} is locally reduced at x_{i} and x_{i} ∉ src(u_{i}). If |u_{0}| ≤ |u_{1}| and x_{0}u_{0} = x_{1}u_{1}, then u_{0} is a suffix of u_{1}. In particular if t ∈ I is not in any of the feet of A and u and v are words that are locally reduced at t with tu = tv, then u = v.

Proof. The main part of the lemma is proved by induction on |u_{0}|. If u_{0} = ε, this is trivially true. Next suppose that u_{i}a_{i} with a_{i} ∈ A^{±} is locally reduced at x_{i} and x_{i} ∉ src(u_{i}a_{i}). If z = x_{0}u_{0}a_{0} = x_{1}u_{1}a_{1}, then z ∈ dest(a_{0}) and z ∈ dest(a_{1}) and hence a_{0} = a_{1}. We are now finished by applying our induction hypothesis to conclude that u_{0} is a suffix of u_{1}.

In order to see the second conclusion, let t, u and v be given such that x := tu = tv and assume without loss of generality that |u| ≤ |v|. By the main assertion of the lemma, v = wu for some w. Since tw = t, Lemma 5.2 implies w = ε. □

If x ∈ src(a) for some a ∈ A^{±}, then x ∈ dest(a^{−1}). This suggests that we have “arrived at” x by applying a locally reduced word to some other point. Moreover a^{−1} is the unique element b of A^{±} such that x ∈ dest(b). Thus we may attempt to “trace back” to where x “came from.” This provides a recursive definition of a sequence which starts at a^{−1} and grows to the left, possibly infinitely far. This gives rise to the notion of a history of a point x ∈ I, which will play an important role in the proof of Theorem 5.12 below and also in Section 11. If t ∈ I is not in dest(a) for any a ∈ A^{±}, then we say that t has trivial history and define t̃:= {a ∈ A : t ∈ supt(a)}. If x ∈ I, define η(x) to be the set of all strings of the following form:

• words u such that for some t ∈ I, tu = x, u is locally reduced at t, and t ∉ src(u);

• strings ~ tu such that t has trivial history, u is locally reduced at t, and tu = x.

(In the second item ~ tu is the concatenation of the formal symbol representing t̃ with the string u.) Notice that if w is a word, then w^{−1} is in η(x) if and only if w is locally reduced at x and xw ∉ dest(w).

We will refer to elements of η(x) as histories of x. We will say that x has finite history if η(x) is finite. The following can be easily established using Lemmas 5.1 and 5.4; the proof is omitted.

Lemma 5.5. The following are true for each x ∈ I:

• η(x) is closed under taking suffixes;

• for each n, η(x) contains at most one sequence of length n;

• If v is a word in η(x), then η(xv^{−1}) = {u : uv ∈ η(x)}.

It is useful to think of η(x) as the suffixes of a single sequence which is either finite or grows infinitely to the left. By considering the unique string in η(x) of length one, observe that if η(x) = η(y), then for every word w ≠ ε, x ∈ J(w) if and only if y ∈ J(w).

In what follows, we will typically use s and t to denote elements of I with finite history and x and y for arbitrary elements of I. The following is a key property of having a trivial history.

Lemma 5.6. If s ≠ t have trivial history, then s⟨A⟩ and t⟨A⟩ are disjoint.

Proof. If the orbits intersect, then t = sw for some word w. By Lemma 5.1 we can take w to be locally reduced at s. By Lemma 5.2, sw is in the destination of w. But t = sw has trivial history, which is impossible. □

Recall that the set of freely reduced words in a given generating set has the structure of a rooted tree with the empty word as root and where “prefix of” is synonymous with “ancestor of.” The ping-pong argument discovers orbits that reflect this structure. Define a labeled directed graph on I by putting an arc with label a from x to xa whenever a ∈ A^{±} and xa ≠ x. The second part of Lemma 5.4 asserts that if x is in the orbit of a point t with trivial history, then there is a unique path in this graph connecting t to x. It follows that if there is a path between two elements of I with finite history, it is unique, yielding the following lemma.

Lemma 5.7. If s, t ∈ I have finite histories, then there is at most one word w which is locally reduced at s so that sw = t.

Notice that the assumption of finite history in this lemma is necessary. For instance if we consider the positive bumps a_{0} and a_{1} in Figure 2, there must be an x ∈ supt(a_{0}) ∩ supt(a_{1}) such that xa_{0}a_{1}^{−1} = x. This follows from the observation that if s < t are, respectively, the left transition point of a_{1} and the right transition point of a_{0}, then

sa_{0}a_{1}^{−1} > sa_{1}^{−1} = s  and  ta_{0}a_{1}^{−1} = ta_{1}^{−1} < t

which implies the existence of the desired x by applying the Intermediate Value Theorem to x ↦ xa_{0}a_{1}^{−1} − x.

Given two points x, y ∈ I and a word w, it will be useful to find a single word w′ which is locally reduced at x and y and which satisfies xw′ = xw and yw′ = yw. The goal of the next set of lemmas is to provide a set of sufficient conditions for the existence of such a w′. It will be convenient to introduce some additional terminology at this point. If x ∈ I, then we say that w is a return word for x if xw = x and w ≠ ε; a return prefix for x is a prefix which is a return word. We will see that “w does not have a return prefix for x” is a useful hypothesis. The next lemma provides some circumstances under which this is true.

Lemma 5.8. If s ∈ I has finite history, u is locally reduced at s, and w is a word of length less than u, then uw has no return prefix for s.

Proof. Notice that it suffices to prove that uw is not a return word for s. If it were, then there would be a locally reduced subword v of w^{−1} such that su = sv. Since |v| ≤ |w| < |u|, this would contradict Lemma 5.7. □

Lemma 5.9. Suppose that w ≠ ε is a word and s ∈ J(w) has finite history. If w has no return prefix for s and w′ is locally reduced at s with sw′ = sw, then:

• J(w′) = J(w);

• w′ is locally reduced on J(w);

• if x ∈ J(w), then xw′ = xw.

Proof. First observe that by Lemma 5.7, w′ is uniquely determined by w. In particular, it is sufficient to prove that for each w satisfying the hypothesis of the lemma, there is a w′ which satisfies the three itemized conclusions. The proof of the lemma is by induction on the length of w. If w has length 1, then w′ = w and there is nothing to show. Suppose now that w = ub for some b ∈ A^{±} and u ≠ ε. Let u′ be locally reduced at s such that su′ = su. By our inductive assumption, J := J(u′) = J(u) = J(w), u′ is locally reduced on J and if x ∈ J, then xu′ = xu. By our assumption, su′ = su ≠ s and so u′ ≠ ε. If u′b is not freely reduced, then its free reduction w′ satisfies that sw′ = su′b = sub = sw ≠ s. In particular, w′ ≠ ε and retains the first symbol of u′. Furthermore, since u′ is locally reduced on J and since w′ is a prefix of u′, w′ is also locally reduced on J. Also, if x ∈ J, then xw = xub = xu′b = xw′.

Suppose now that u′b is freely reduced. By Lemma 5.2, Ju = Ju′ ⊆ dest(u′). If dest(u′) is disjoint from supt(b), then xu′ = xu′b = xub = xw for all x ∈ J. Since u′ is locally reduced, we are again done in this case. In the remaining case, dest(u′) ⊆ supt(b) in which case w′ = u′b is locally reduced at all x ∈ J. Since for all x ∈ J, xu = xu′ ≠ xu′b = xub = xw we have that w′ is locally reduced on J. Clearly J(w′) = J(u′) = J(w) and we are finished. □

Lemma 5.9 has two immediate consequences which will be easier to apply directly.

Lemma 5.10. If w is a word and there is an s ∈ J := J(w) with finite history such that w is a minimal return word for s, then w is the identity on J.

Proof. Let w = ua and let u′ be locally reduced at s with su′ = su. Since sw = su′a = s, it must be that u′ = a^{−1}. By Lemma 5.9, xu′ = xu whenever x ∈ J. Thus xw = xu′a = xa^{−1}a = x for all x ∈ J. □

Lemma 5.11. If s, t ∈ I have trivial histories and s̃ = t̃, then any return word for s is a return word for t. Moreover if w ≠ ε is not a return word for s, then there is an a ∈ A^{±} such that {sw, tw} ⊆ dest(a).

Proof. Suppose that s and t are as in the statement of the lemma. Observe that for any word u, s ∈ J(u) if and only if t ∈ J(u). Now let w be any word. If there is a minimal return prefix of w for s, then by Lemma 5.10, it is also a return prefix for t. (If neither s nor t are in J(w), the the first symbol of w is a return word for both s and t.) By iteratively removing minimal return prefixes for s — which also are return prefixes for t — we may assume w either either empty or else has no return prefixes for s or for t. Since s̃ = t̃, {s, t} ⊆ J(w). An application of Lemma 5.9 followed by Lemma 5.2 now yields the desired conclusion. □

The following theorem shows that the restriction of the action of ⟨A⟩ to M⟨A⟩ is faithful. At this point we will depart from our purely axiomatic treatment of the dynamics and start to utilize the order and topology of the interval.

Theorem 5.12. Suppose that A ⊆ Homeo_{+}(I) is a (possibly infinite) geometrically fast set of positive bump functions, equipped with a marking. If g ∈ ⟨A⟩ is not the identity, then there is an x ∈ M⟨A⟩ such that xg ≠ x.

Remark 5.13. If A is infinite, then M has not been defined. In this case, we let M denote the set of all markers. If A is finite and equipped with the canonical marking, then the cardinality of M is the sum of the number of maximal stretched transition chains in A and the number of isolated elements of A.

Proof. Clearly it suffices to prove the theorem when A is finite and we will assume this for the duration of the proof. Observe that if there is an x ∈ I such that xg ≠ x, then by continuity of g, there is an x ∈ I such that xg ≠ x and x is not in the orbit of a transition point or marker (orbits are countable and neighborhoods are uncountable). Fix such an x and a word w representing g for the duration of the proof. The proof of the theorem breaks into two cases, depending on whether x has finite history.

We will first handle the case in which x has trivial history; this will readily yield the more general case in which x has finite history. Suppose that x ∉ src(a) for all a ∈ A. Let y < x be maximal such that y is either a transition point or a marker.

Claim 5.14. y has trivial history and x̃ = ỹ.

Proof. First suppose that y is the marker of some a ∈ A. Notice that by our assumption of maximality of y, the right transition point of a is greater than x. In this case, both x and y are in the support of a. Furthermore, observe that y is not in the foot of any b ∈ A. To see this, notice that this would only be possible if y is in the right foot of some b. However since x is not in the right foot of b, the right transition point of b would then be less than x, which would contradict the maximal choice of y. Finally, if c ∈ A \ {a}, the maximal choice of y implies that x is in the support of c if and only if y is.

If y is a transition point of some a ∈ A, then y must be the right transition point of a since otherwise our maximality assumption on y would imply that x is in the left foot of a, contrary to our assumption that x has trivial history. In this case neither x nor y are in the support of a. If b ∈ A \ {a}, then our maximality assumption on y implies that {x, y} is either contained in or disjoint from the support of b. To see that y has trivial history, observe that the only way a transition point can be in a foot is for it to be the left endpoint of a right foot. If y is the left endpoint of a right foot, then our maximal choice of y would mean that x is also in this foot, which is contrary to our assumption. Thus y must have trivial history. □

By Claim 5.14 and Lemma 5.11, yw ≠ y. If y is a marker, we are done. If y is a transition point of some a ∈ A, then as noted above it is the right transition point of a. If s is the marker of a, then sa^{k} → y and by continuity sa^{k}w → yw. Thus for large enough k, sa^{k}w ≠ sa^{k}. Since sa^{k} ∈ M⟨A⟩, we are done in this case.

Now suppose that x has finite history and let ~ tu ∈ η(x) with t ∈ I and tu = x. By definition of η(x), t has trivial history. Since xw ≠ x, we have that tuw ≠ tu and hence tuwu^{−1} ≠ t. It follows from the previous case that there is an s ∈ M⟨A⟩ such that suwu^{−1} ≠ s. We now have that y := su is in M⟨A⟩ and satisfies yw ≠ y as desired.

Finally, suppose that η(x) is infinite. Let u ∈ η(x) be longer than w, let s be the marker for the initial symbol of u, and set y := xu^{−1} and t := su. Since u is locally reduced at y by assumption, Lemma 5.3 implies that u is locally reduced at s. By Lemma 5.8, uw has no return prefix for s. Let v be locally reduced at s such that suw = sv. Applying Lemma 5.9 to uw, s and v, we can conclude that J(v) = J(uw), that v is locally reduced at y, and yuw = yv. Notice that since xw ≠ x, yuw = yv ≠ yu and in particular v ≠ u. By Lemma 5.7, we have that t = su ≠ sv = suw = tw. This finishes the proof of Theorem 5.12. □

We finish this section with two lemmas which concern multi-orbital homeomorphisms but which otherwise fit the spirit of this section. They will be needed in Section 9.

Lemma 5.15. Suppose that X ⊆ Homeo_{+}(I) is geometrically fast and equipped with a fixed marking. Let A be the (possibly infinite) set of bumps used in X and s ∈ M. If w is an X-word and u is an A-word which is locally reduced at s and satisfies su = sw, then for every prefix u′ of u, there is a prefix w′ of w such that su′ = sw′.

Proof. Let w_{i} be the prefix of w of length i for i ≤ |w| and let u_{i} be the unique A-word which is locally reduced at s such that su_{i} = sw_{i}. Notice that if u_{i+1} ≠ u_{i}, then u_{i+1} is obtained by inserting or deleting a single symbol at/from the end of u_{i}. It follows that all prefixes of u occur among the u_{i}’s. □

If X ⊆ Homeo_{+}(I), then an element s of I is defined to have finite history with respect to X if it has finite history with respect to the set of bumps used in X. The meaning of return word is unchanged in the context of X-words.

Lemma 5.16. Suppose that X ⊆ Homeo_{+}(I) is geometrically fast, equipped with a fixed marking, and that A denotes the (possibly infinite) set of bumps used in X. Let w ≠ ε be an X-word and a ∈ A^{±} be a signed bump of the first symbol of w. If s ∈ J := J(a) has finite history and w has no proper return prefix for s, then there is an A-word v which begins with a and is such that v and w coincide on J.

Proof. The proof is by induction on the length of w. Observe that the lemma is trivially true if w has length at most 1. Therefore suppose that w = ug with g ∈ X^{±} and u ≠ ε. Let v′ be an A-word which begins with a and is such that v′ and u agree on J. Since u has no return prefix, Lemma 5.15 implies that v′ has no return prefix. Let v′′ be a subword of v′ which is locally reduced at s and satisfies sv′′ = sv′. By Lemma 5.9, v′′ is locally reduced on J and J(v′′) = J(v′) = J. (Notice that even though A may be infinite, we can apply the lemma to a sufficiently large finite set of bumps and obtain the desired conclusion.) In particular, Ju ⊆ dest(v′′). If the support of g is disjoint from dest(v′′), set v := v′. Otherwise, let b ∈ A^{±} be the signed bump of g such that dest(v′′) ⊆ supt(b) and set v := v′b. Observe that v satisfies the conclusion of the lemma. □

6. The isomorphism theorem for geometrically fast generating sets

At this point we have developed all of the tools needed to prove Theorem 1.1, whose statement we now recall.

Theorem 1.1. If two geometrically fast sets X, Y ⊆ Homeo_{+}(I) have only finitely many transition points and have isomorphic dynamical diagrams, then the induced bijection from X to Y extends to an isomorphism from ⟨X⟩ to ⟨Y ⟩ (i.e. ⟨X⟩ is marked isomorphic to ⟨Y ⟩). Moreover, there is an order preserving bijection θ : M⟨X⟩ → M⟨Y ⟩ such that f ↦ f^{θ} induces the isomorphism ⟨X⟩ ≅ ⟨Y ⟩.

Observe that it is sufficient to prove this theorem in the special case when X and Y are finite geometrically fast collections of positive bumps: if A and B are the bumps used in X and Y respectively, then the dynamical diagrams of A and B are isomorphic and the isomorphism of ⟨A⟩ and ⟨B⟩ restricts to a marked isomorphism from ⟨X⟩ to ⟨Y ⟩.

Fix, for the moment, a finite geometrically fast set of positive bumps X. As we have noted, it is a trivial matter, given a word w and a t ∈ M, to find a subword w′ which is locally reduced at t and satisfies tw = tw′. Theorem 1.1 will fall out of an analysis of a question of independent interest: how does one determine w′ from w and t using only the dynamical diagram of X? Toward this end, we define ~ tw to be a local word if t ∈ M and w is a word. (Notice that t ↦ t̃ is injective on M; the reason for working with t̃ is in anticipation of a more general definition in Section 11.) A local word ~ tw is freely reduced if w is. It will be convenient to adopt the convention that dest(~ t) = {t} if t ∈ M. Define Λ = Λ_{X} to be the set of all freely reduced local words ~ tw such that if ab are consecutive symbols in ~ tw, then the destination of a is between src(b) and dest(b) (and possibly equals dest(b)) in the diagram’s ordering. Notice that the assertion that ~ tw is in Λ can be formulated as an assertion about w, the element of X which has t as a marker and the dynamical diagram of X.

Every local word ~ tw can be converted into an element of Λ by iteratively removing symbols by the following procedure: if ab is the first consecutive pair in ~ tw which witnesses that it is not in Λ, then:

• if b = a^{−1} then delete the pair ab;

• if b ≠ a^{−1} then delete b.

Observe that since the first symbol of a local word is not removed by this procedure, the result is still a local word. The local reduction of a local word ~ tw is the result of applying this procedure to ~ tw until it terminates at an element of Λ. The following lemma admits a routine proof by induction, which we omit.

Lemma 6.1. Suppose that X is a geometrically fast set of positive bumps. If t ∈ M and w is a word, then w is locally reduced at t if and only if ~ tw is in Λ. Moreover, if w′ is such that ~ tw′ is the local reduction of ~ tw, then tw′ and tw coincide.

Next, order A^{±} so that if a, b ∈ A^{±}, then a is less than b if every element of dest(a) is less than every element of dest(b). Order Λ with the reverse lexicographic order: if uw and vw are in Λ and the last symbol of u is less than that of v, then we declare uw less than vw. Define the evaluation map on Λ to be the function which assigns the value tu to each string ~ tu ∈ Λ. (This is well defined since t ↦ ~ t is injective on M.) This order is chosen so that the following lemma is true.

Lemma 6.2. The evaluation map defined on Λ is order preserving.

Proof. Suppose that uw and vw are in Λ and the last symbol of u is less than the last symbol of v. Observe that by Lemma 5.2, the evaluation of u is an element of its destination. Thus if the destination of u is less than the destination of v, then this is true of their evaluations as well. Since t ↦ tw is order preserving, we are done. □

Now we are ready to prove Theorem 1.1.

Proof of Theorem 1.1. As noted above, we may assume that X and Y are geometrically fast families of positive bump functions with isomorphic dynamical diagrams. By Theorem 5.12, we know that ⟨X⟩ ↾ (M⟨X⟩) is marked isomorphic to ⟨X⟩; similarly ⟨Y ⟩ ↾ (M⟨Y ⟩) is marked isomorphic to ⟨Y ⟩. It therefore suffices to define an order preserving bijection θ : M⟨X⟩ → M⟨Y ⟩ such that saθ = sθτ(a), where s ∈ M⟨X⟩ and a ∈ X and where τ : X → Y is the bijection induced by the isomorphism of the dynamical diagrams of X and Y.

Define μ : M_{X} → M_{Y} by sμ = t if s is the marker for a ∈ X and t is the marker for τ(a) ∈ Y. Let λ denote the translation of local X-words into local Y -words induced by μ and τ. Define θ : M⟨X⟩ → M⟨Y ⟩ so that tuθ is the evaluation of λ(~ tu) for ~ tu ∈ Λ_{X}. This is well defined by Lemmas 5.6, 5.7, and 6.1. By Lemma 6.2 and the fact that λ preserves the reverse lexicographic order, θ is order preserving.

Now suppose that s ∈ M⟨X⟩ and a ∈ X^{±}. Fix ~ tu ∈ Λ_{X} such that s = tu and let ~ tv ∈ Λ_{X} be the local reduction of ~ tua. Observe that on one hand saθ = tvθ is the evaluation of λ(~ tv). On the other hand sθτ(a) is the evaluation of λ(~ tua). Since λ is induced by an isomorphism of dynamical diagrams, it satisfies that w′ is the local reduction of w if and only if λ(w′) is the local reduction of λ(w). In particular, λ(~ tv) is the local reduction of λ(~ tua). By Lemma 6.1, these local Y -words have the same evaluation and coincide with saθ and sθτ(a), respectively. This completes the proof of Theorem 1.1. □

As we noted in the introduction Theorem 1.1 has two immediate consequences. First, geometrically fast sets X = {f_{i} | i < n} ⊆ Homeo_{+}(I) with finitely many transition points are algebraically fast: if 1 ≤ k_{i} for each i < n, then ⟨f_{i} | i < n⟩ is marked isomorphic to ⟨f_{i}^{k_{i}} | i < n⟩. The reason for this is that the dynamical diagrams associated to {f_{i} | i < n} and {f_{i}^{k_{i}} | i < n} are isomorphic. Second, since the dynamical diagram of any geometrically fast set with finitely many transition points can be realized by a geometrically fast subset of F (see, e.g., [10, Lemma 4.2]), every group admitting a finite geometrically fast generating set can be embedded into F. The notion of history in the previous section is revisited in Section 11 where it is used to prove a relative of Theorem 1.1.

More evidence of the restrictive nature of geometrically fast generating sets can be found in [12] where groups generated by stretched transition chains C as defined in Section 3 are considered under the weaker assumption that consecutive pairs of elements in C are geometrically fast. Groups generated by such a C with n elements are called n-chain groups. It is proven in [12] that every n-generated subgroup of Homeo_{+}(I) is a subgroup of an (n + 2)-chain group. Another result of [12] is that for each n ≥ 3, there are uncountably many isomorphism types of nchain groups. By contrast, Theorem 1.1 (with Corollary 9.1 below) implies that the number of isomorphism types of groups with finite, geometrically fast generating sets is countable because the number of isomorphism types of dynamical diagrams is countable.

7. Minimal representations of geometrically fast groups and topological semi-conjugacy

Theorem 1.1 partitions the subgroups of Homeo_{+}(I) generated by geometrically fast sets with finitely many transition points: two such sets are considered equivalent if their dynamical diagrams are isomorphic. In this section we show that each class contains a (nonunique) representative Y so that for each X in the class there is a marked isomorphism ϕ : ⟨X⟩ → ⟨Y ⟩ which is induced by a semi-conjugacy on I. Specifically, the bijection θ : M⟨X⟩ → M⟨Y ⟩ of Theorem 1.1 extends to a continuous order preserving surjection θ̂ : I → I so that for all f ∈ ⟨X⟩ we have fθ̂ = θ̂ϕ(f). Notice that in this situation, the graph of ϕ(f) is the image of the graph of f under the transformation (x, y) ↦ (xθ̂, yθ̂). We will refer to such a Y ⊆ Homeo_{+}(I) as terminal. Theorem 1.2 can now be stated as follows.

Theorem 7.1. Each dynamical diagram D can be realized by a terminal X_{D} ⊆ PL_{+}(I).

Proof. As in the proof of Theorem 1.1, it suffices to prove the theorem under the assumption that all bumps in D are positive and all labels are distinct. Furthermore, by Proposition 3.2, we may assume that D has no isolated bumps. Let n denote the number of bumps of D, set ℓ := 1/(2n) and

J := {[iℓ, (i + 1)ℓ) | 0 ≤ i < 2n},

observing that J has the same cardinality as the set of feet of D. Order J by the order on the left endpoints of its elements. If i < 2n, we will say that the i^{th} interval in J corresponds to the i^{th} foot of D.

For i < n, let (x_{i}, s_{i}) and (t_{i}, y_{i}) be the intervals in J which correspond to the left and right feet of the i^{th} bump of D, respectively. Note that since D has no isolated bumps, s_{i} < t_{i}. Define b_{i} to be the bump which has support (x_{i}, y_{i}), maps s_{i} to t_{i} and is linear on (x_{i}, s_{i}) and (s_{i}, y_{i}) — see Figure 7. If we assign b_{i} the marker s_{i}, then the feet of b_{i} are either in J or are the interior of an element of J; in particular, the feet of X_{D} = {b_{i} | i < n} are disjoint. Thus X_{D} is geometrically fast and has dynamical diagram isomorphic to D.

Notice that the feet (x_{i}, s_{i}) and [t_{i}, y_{i}) of b_{i} are each intervals of length ℓ contained in I while the middle interval [s_{i}, t_{i}) is of length mℓ for some positive integer m.

[figure: x_{i}; s_{i}; t_{i}; y_{i}]

Figure 7. The function b_{i}.

Moreover, since D has no isolated bumps, there is an interval of J between s_{i} and t_{i}; in particular, t_{i} − s_{i} ≥ ℓ. It follows that the slope of the graph of b_{i} on its source (x_{i}, s_{i}) and the slope of the graph of b_{i}^{−1} on its source [t_{i}, y_{i}) are both at least 2.

Claim 7.2. If X_{D} is the set of positive bumps constructed above, then M⟨X_{D}⟩ is dense in I.

Remark 7.3. Note that we are working under the assumption that D has no isolated elements. If D has isolated bumps, then M⟨X_{D}⟩ can not be dense.

Proof. Since every transition point of X_{D} is in the closure of M⟨X_{D}⟩, it suffices to show that if 0 ≤ p < q ≤ 1, then (p, q)f contains an endpoint of an interval in J for some f ∈ ⟨X_{D}⟩. The proof is by induction on the minimum k ≥ 0 such that ℓ2^{−k} < q − p. Observe that if k = 0, then q − p > ℓ and thus q − p must contain an endpoint of an interval in J.

Next observe that if (p, q) does not contain an endpoint of an element of J, then (p, q) is contained in the foot of some b_{i} for i < n. If (p, q) ⊆ src(b_{i}), then since the derivative of b_{i} is at least 2 on it source, it follows that (p, q)b_{i} is at least twice as long as (p, q). By our induction hypothesis, there is an f ∈ ⟨X_{D}⟩ such that (p, q)b_{i}f contains an endpoint of J. Similarly, if (p, q) ⊆ src(b_{i}^{−1}), then (p, q)b_{i}^{−1} is at least twice as long as (p, q) and we can find an f ∈ ⟨Y ⟩ such that (p, q)b_{i}^{−1}f contains an endpoint of J. □

In order to see that X_{D} is terminal, let X ⊆ Homeo_{+}(I) be geometrically fast, have finitely many transition points, and have a dynamical diagram isomorphic to D. Let θ : M⟨X⟩ → M⟨X_{D}⟩ be order preserving and satisfy that tfθ = tθϕ(f) for all t ∈ M⟨X⟩, where ϕ : ⟨X⟩ → ⟨X_{D}⟩ is the marked isomorphism. Define θ̂: I → I by

xθ̂:= sup{tθ | t ∈ M⟨X⟩ and t ≤ x}

where we adopt the convention that sup ∅ = 0. Clearly θ̂: I → I is order preserving and extends θ. In particular its range contains M⟨X_{D}⟩, which by Claim 7.2 is dense in I. It follows that θ̂ is a continuous surjection (any order preserving map from I to I with dense range is a continuous surjection). That xfθ̂ = xθ̂ϕ(f) follows from the fact that this is true for x ∈ M⟨X⟩ and from the continuity of f and ϕ(f). This completes the proof that X_{D} is terminal. □

8. Fast generating sets for the groups F_{n}

In this section we will give explicit generating sets for some well known variations of Thompson’s group F. First notice that since (0, 1) is homeomorphic to R by an order preserving map, all of the analysis of geometrically fast subsets of Homeo_{+}(I) transfers to Homeo_{+}(R) (with the caveat that ±∞ must be considered as possible transition points of elements of Homeo_{+}(R); see Example 10.3 below). Fix an integer n ≥ 2. For 0 ≤ i < n, let g_{i} be a homeomorphism from R to itself defined by:

tg_{i} := \begin{cases}t & if t ≤ i \\ i + n(t − i) & if i ≤ t ≤ i + 1 \\ t + (n − 1) & if i + 1 ≤ t. \end{cases}

In words, g_{i} is the identity below i, has constant slope n on the interval [i, i + 1], and is translation by n − 1 above i + 1. We will use F_{n} to denote ⟨g_{i} | 0 ≤ i < n⟩. The group F_{2} is one of the standard representations of Thompson’s group F. (The more common representation of F is as a set of piecewise linear homeomorphisms of the unit interval [10, §1].)

The groups F_{n} (n ≥ 2) are discussed in [9, §4] where F_{n} is denoted F_{n,∞}, and in [6, §2] where F_{n} is denoted F_{n,0}. The standard infinite presentation of F_{n} is given in [6, Cor. 2.1.5.1]. It follows easily from that presentation that the commutator quotient of F_{n} is a free abelian group of rank n. In particular the F_{n}’s are pairwise nonisomorphic.

We now describe an alternate generating set for F_{n} which consists of n positive bump functions and is geometrically fast. For i < n − 1, set h_{i} := g_{i}g_{i+1}^{−1} and let h_{n−1} denote g_{n−1}. It is clear that C = {h_{i} | i < n} generates F_{n}. We claim that C is a geometrically fast stretched transition chain. If i < n−1, then h_{i} is the identity outside [i, i + 2]. On that interval it is a positive, one bump function since chain rule considerations show that h_{i} has slope n on [i, i + \frac{1}{n}], slope one on [i + \frac{1}{n}, i + 1] and slope 1/n on [i + 1, i + 2]. Thus the support of h_{i} is (i, i + 2) and the support of h_{n−1} is (n − 1, ∞). In particular, C forms a stretched transition chain.

Next we will show that C is geometrically fast. Observe that for 0 < j ≤ n we have:

(i + \frac{j}{n}) h_{i} = (i + 1) + \frac{j − 1}{n}.

For 0 ≤ i ≤ n set t_{i} := i + \frac{n−i}{n}. It follows from the above computation that for 0 ≤ i < n − 1, we have t_{i}h_{i} = t_{i+1} so that t_{0} = 1 and t_{n} = n. This makes t_{0} the leftmost transition point in the support of h_{0} and t_{n} the rightmost transition point in the support of h_{n−1}. By Proposition 4.3, C is geometrically fast. Combining this with Theorem 1.1, we now have that any geometrically fast stretched transition chain generates a copy of F_{n}.

Remark 8.1. The above proof that F_{n} is isomorphic to the group generated by a geometrically fast stretched transition chain of length n is not an efficient way to reach this conclusion. There is a more straightforward argument based on the standard presentation of F_{n} as indicated in the proof of [12, Proposition 1.11]. We included this example as an introduction to the variety of isomorphism classes in groups generated by geometrically fast sets.

It is convenient now to prove Corollary 1.3.

Proof. To build a dynamical diagram, we need bumps that have feet small enough to avoid each other. It is easiest to describe such bumps using the model of F = F_{2} on [0, ∞) as described in the beginning of this section. We use the g_{i} as described there with n = 2, but we let i be any non-negative integer. The group generated by these g_{i} is still generated by g_{0} and g_{1}, but the extra elements are useful.

Easy calculations show, for i ≥ 0 and k ≥ 1, that x_{i,k} = (g_{i}g_{i+k}^{−1})^{k+1} has support on [i, i + k + 1] and takes i + \frac{1}{2} to i + k + \frac{1}{2}. The calculation for k = 1 is slightly different from that for k ≥ 2. Thus we can choose from a set of bumps with feet of size \frac{1}{2} with support having any integer width from 2 on up. This is a sufficient set of bumps to build any dynamical diagram. □

9. Excision of extraneous bumps in fast generating sets

Sometimes fast generating sets use bumps which do not affect the marked isomorphism type of the resulting group. This section gives a sufficient condition for when those bumps can be excised while preserving the marked isomorphism type. We make no finiteness assumptions in this section.

If f ∈ Homeo_{+}(I) and E is a set of positive bumps, then we define f/E ∈ Homeo_{+}(I) to be the function which agrees with f on

I \ ⋃{supt(a) | a ∈ E and a is used in f}

and is the identity elsewhere. If X is a fast generating set and E is a set of positive bumps, we define X/E := {f/E | f ∈ X}.

Now let X be a fast generating set and let J ⊆ I be an interval. We say a set E of bumps is extraneous in X as witnessed by J if for some f ∈ X:

• every element of E is an isolated bump used in f whose support is contained in J;

• there is a bump a used in f not in E such that J contains a foot of a;

• J is disjoint from the feet of all g ∈ X \ {f}.

Theorem 9.1. If X ⊆ Homeo_{+}(I) is a (possibly infinite) geometrically fast set and E is an extraneous set of bumps used in X, then the map g ↦ g/E extends to an isomorphism between ⟨X⟩ and ⟨X/E⟩.

Proof. Fix X and E as in the statement of the theorem and let J be an interval witnessing that E is extraneous and f ∈ X be the element of X such that the elements of E occur in f. Let A denote the set of bumps used in X, M denote M_{X}, and M̃ denote M_{X/E}. Set S := M⟨X⟩ = M⟨A⟩ and S̃ := M̃⟨X/E⟩ = M̃⟨A \ E⟩. Observe that since the elements of E are isolated in A and since every element of M̃⟨A\E⟩\M̃ is in dest(b) for some b ∈ (A\E)^{±}, it follows that M̃⟨A\E⟩ = M̃⟨A⟩. In particular, S̃ is ⟨A⟩-invariant and hence g ↦ g ↾ S̃ defines a homomorphism of ⟨X⟩ to ⟨X⟩ ↾ S̃.

Recall that, by Theorem 5.12, g ↦ g ↾ S defines an isomorphism between ⟨X⟩ and ⟨X⟩ ↾ S. Similarly, g/E ↦ g/E ↾ S̃ defines an isomorphism between ⟨X/E⟩ and ⟨X/E⟩ ↾ S̃. Since g ↾ S̃ = (g/E) ↾ S̃, it suffices to show that g ↾ S ↦ g ↾ S̃ is injective on ⟨X⟩ ↾ S. That is, if w is an X-word, s is a marker for an a ∈ E, and suw ≠ su for some X-word u, then there is a t ∈ S̃ such that tuw ≠ tu. Equivalently we need to show that for every marker s of an a ∈ E and X-word w, if sw ≠ s, then there is a t ∈ S̃ with tw ≠ t. To this end let such s, a, and w be given with sw ≠ s.

Claim 9.2. If there is an x ∈ supt(a) such that xw ∉ supt(a), then there is a t ∈ S̃ such that tw ≠ t.

Proof. Suppose that xw ∉ supt(a) for some x ∈ supt(a). Let uv be locally reduced at x such that xuv = xw with u maximal such that xu ∈ supt(a); notice that v ≠ ε. Since a is isolated, xu ∉ src(v) and thus by Lemma 5.2 xuv ∈ dest(v). Notice also that the last symbol of v is not a bump in E^{±}. It follows that w must move an endpoint of dest(v), both of which are in the closure of S̃∩ dest(v). Hence w moves an element of S̃. □

We may therefore assume that sw ≠ s but that w maps supt(a) to supt(a). Let w = ∏_{i<n} w_{i} be a factorization of w into minimal positive length words which define maps from supt(a) into supt(a). Let b be the bump used in f with b ∉ E and such that J contains a foot of b. Let t ∈ J ∩S̃ be sufficiently close to the transition point of b which is in J such that for all k ∈ Z with |k| ≤ |w|, tf^{k} ∈ J.

Claim 9.3. For all i < n, there is a p ∈ {1, 0, −1} such that w_{i} ↾ J = f^{p} ↾ J.

Proof. If w_{i} begins with f or f^{−1}, then it must have length 1 and there is nothing to show. If w_{i} begins with g ≠ f^{±1}, then either J is contained in or disjoint from the support of g and it is disjoint from all of the feet of g. If g ↾ J is the identity, then again w_{i} has length 1.

Now suppose that J is contained in the support of g where g is neither f nor f^{−1} and has s in its support. Notice that since J is disjoint from the feet of g, J is contained in the support of a single bump c ∈ A^{±} of g.

We will now show that sw_{i} = s. Let gvh be a minimal prefix of w_{i}, for h ∈ X, such that sgvh ∈ supt(a). (Notice that this prefix must have length at least 2 by our assumption that sg is not in the support of a; possibly v = ε.) Let d be the bump of h whose support contains sgv and observe that, by minimality of gvh, J is contained in the support of d and disjoint from its feet. By applying Lemma 5.16 to gv and s ∈ J(gv), there is an A-word cu such that cu and gv coincide on J. By Lemma 5.9 and replacing u if necessary, we may assume that cu is locally reduced at s. Furthermore since d is locally reduced at scu, the free reduction of cud is locally reduced at s. If this free reduction is not ε, then by Lemma 5.15 there would be a prefix w′ of gv of positive length such that scud = sw′, which contradicts our minimal choice of gvh. It must therefore have been that cud = cc^{−1}. It follows that gvh is the identity on J. By minimality of w_{i}, w_{i} = gvh and thus w_{i} is the identity on J. □

Applying the claim, there are p_{i} ∈ {1, 0, −1} for i < n such that:

sw = s ∏_{i<n} f^{p_{i}} tw = t ∏_{i<n} f^{p_{i}}.

In particular, since sw ≠ s, it follows that ∑_{i<n} p_{i} ≠ 0 and hence tw ≠ t. □

Corollary 9.4. If X ⊆ Homeo_{+}(I) is geometrically fast and finite, then there is a geometrically fast Y ⊆ Homeo_{+}(I) which has finitely many transition points such that ⟨X⟩ is marked isomorphic to ⟨Y ⟩.

Proof. Let X be given and let J consist of the maximal intervals J ⊆ I such that for some f ∈ X (dependent on J):

• J contains at least one transition point of f;

• J contains no transition points of X \ {f};

• J is disjoint from the feet of X \ {f}.

Observe that since X is geometrically proper, J is finite. The proof is by induction on the number of elements of J which contain infinitely many transition points of X. Suppose that J ∈ J contains infinitely many transition points of some f ∈ X. Let E consist of all but one of the isolated bumps of f with support contained in J. Notice that J witnesses that E is extraneous in X. By Theorem 9.1, ⟨X/E⟩ is marked isomorphic to ⟨X⟩. We are now finished by our induction hypothesis. □

10. The existence of geometrically proper generating sets

In this section we consider the question of when finitely generated subgroups of F admit geometrically proper generating sets. Our first task will be to prove:

Theorem 1.5. Every n-generated one orbital subgroup of PL_{+}(I) either contains an isomorphic copy of F or else admits an n-element geometrically proper generating set.

In this section we will use the standard embedding of Thompson’s group F in PL_{+}(I) and we will make use of the homomorphism π : PL_{+}(I) → R × R defined by π(f) := ( log_{2} (f′(0)) , log_{2} (f′(1)) ). If G is a subgroup of PL_{+}(I), we will write π_{G} for π ↾ G. It is well known that F′ is exactly the kernel of π_{F} and that F′ is simple. We will need the following lemma which combines the main result of [4] and Lemma 3.11 of [1].

Lemma 10.1. If G is a finitely generated subgroup of PL_{+}(I) with connected support into which F does not embed, then the image of the homomorphism π_{G} is either trivial or cyclic.

Proof of Theorem 1.5. Let G be a one orbital subgroup of PL_{+}(I) which is generated by a finite set X. By conjugating by an appropriate affine homeomorphism of R, we may assume that the support of G is (0, 1). We assume that F does not embed in G. By Lemma 10.1, the image of π_{G} must then be isomorphic to Z. Let ϖ be the composition of π_{G} with this isomorphism. If there is more than one element of X not in the kernel of ϖ, then we apply the Euclidean algorithm and repeatedly reduce ∑ {|ϖ(f)| | f ∈ X} by replacing at each stage some g ∈ X by gh^{ϵ}, for some suitably chosen h ∈ X and ϵ ∈ {−1, 1}, where |ϖ(h)| ≤ |ϖ(g)|. Note that this replacement does not change the cardinality of X. Thus we can assume that there is only one element f of X not in the kernel of ϖ.

If X = {g_{i} | i < n}, define N(X) to be the number of pairs (j, x) such that for some i < j either x is left transition point of both g_{i} and g_{j} or a right transition point of both g_{i} and g_{j}. Observe that N(X) is finite since X has only finitely many transition points and that X is geometrically proper precisely if N(X) = 0. Notice also that if (j, x) is a pair counted by N(X), then x can be neither 0 nor 1.

Assume that N(X) > 0, and let x be a point that contributes to N(X) with g ≠ h two functions in X with x a common left transition point or common right transition point of both g and h. Since x ∈ (0, 1), our assumption on the support of G implies that there is an f ∈ X with xf ≠ x. Let T be the set of transition points of g that are moved by f. Since each point in T is moved to infinitely many places by powers of f and since the set of transition points of elements of X is finite, we can find a power f^{k} of f so that no element of T f^{k} is a transition point of an element of X. Let X′ be obtained from X by replacing g by g^{f^{k}}. We have arranged that |X′| = |X|, that ⟨X′⟩ = ⟨X⟩ = G, that there is only one element of X′ outside the kernel of ϖ, and that N(X′) < N(X). By induction ⟨X′⟩ = ⟨X⟩ admits a geometrically proper generating set. □

The assumption that the support of G be connected in Theorem 1.5 turns out to be necessary as the next example shows. Before proceeding we will develop some notation which will be helpful in proving Theorem 1.6 as well. For the remainder of the section, fix two elements a and b of F which are one bump functions whose supports are, respectively, (0, \frac{1}{2}) and (\frac{1}{2}, 1) and which satisfy a′(0) = b′(1) = 2. Notice that a is a positive bump and b is a negative bump.

Example 10.2. The group ⟨ab, a^{−1}b⟩ is isomorphic to Z × Z but has no geometrically proper generating set. We leave the details as an exercise for the reader.

Example 10.3. It was shown in [17] that subgroup ⟨t + 1, t^{3}⟩ of Homeo_{+}(R) is free. Since any minimal generating set for a free group is a free basis for the group, any minimal generating set is algebraically fast. On the other hand this group is not embeddable into F by [7] and hence by Corollary 1.3 is not isomorphic to a group with a geometrically proper generating set.

Next we will prove Theorem 1.6, which shows that the “F -less” hypothesis in Theorem 1.5 can not be removed. Note that no assumption is made in this theorem concerning the number of bumps used in the geometrically proper generating set.

Theorem 1.6. If a finite index subgroup of F is isomorphic to ⟨X⟩ for some geometrically proper X ⊆ Homeo_{+}(I), then it is isomorphic to F.

Proof. Let G be a subgroup of F of finite index such that G ≅ ⟨X⟩ for some finite geometrically proper X ⊆ Homeo_{+}(I). Without loss of generality we may assume that both 0 and 1 are in the closure of the support of ⟨X⟩. Let H denote ⟨X⟩ and ϕ : G → H be a fixed isomorphism. We must show that G is isomorphic to F.

By [3] we know that, since G ≤ F is of finite index, it is of the form π^{−1}(K) for some finite index subgroup K of Z × Z. Furthermore, also by [3], π^{−1}(K) is isomorphic to F if and only if K admits a generating set of the form {(p, 0) , (0, q)} for p, q ∈ Z \ {0}.

Observe in any case that K admits a two element generating set {(p_{i}, q_{i}) | i < 2}, as it is of finite index in Z × Z. We will first derive some properties of G which come from viewing it as a subgroup of F. Define f_{i} := a^{p_{i}}b^{q_{i}}. It is shown in [3] that G can be generated by {f_{i} | i < 2} ∪ F′. For 0 ≤ x < y ≤ 1 with both x and y in Z[1/2] we let F_{[x,y]} denote the subgroup of F consisting of those elements of F whose support is contained in [x, y]. It is standard that F_{[x,y]} ≅ F and that if x < w < y < z, then F_{[x,y]} ∪ F_{[w,z]} generates F_{[x,z]}.

Next we claim that the kernel of π_{G} is G′ = F′. It is trivial that F′ ⊆ G and since F′ is simple and not abelian it follows that we also have F′ ⊆ G′. On the other hand, since G ⊆ F we have G′ ⊆ F′. Since the image of π_{G} is abelian, we have G′ is contained in the kernel of π_{G}. Lastly, ker(π_{G}) ⊆ ker(π) ⊆ F′.

Claim 10.4. If g ∈ G is such that neither coordinate of π(g) is 0, then there is a finite subset T of G′ with G′ ⊆ ⟨T ∪ {g}⟩.

Proof. Notice that there is an ϵ > 0 so that g moves all points in (0, ϵ) and (1−ϵ, 1). It follows that for some x < y in Z[1/2] the images of (x, y) under integral powers of g cover (0, 1). Hence the conjugates of F_{[x,y]} under integral powers of g generate F′ = G′. The claim now follows from the fact that F_{[x,y]} ≅ F is generated by two elements. □

In what follows, we will refer to the closure of the support of an f ∈ Homeo_{+}(I) as the extended support of f.

Claim 10.5. Suppose g ∈ G \ G′ has connected extended support and h ∈ G. If g commutes with g^{h} then g commutes with h.

Proof. We know that 0 or 1 is in the extended support of g and both 0 and 1 are fixed by h. Since g has only finitely many bumps, it has finitely many transition points. If any of these are moved by h, then at least one fixed point of g^{h} is moved by g or at least one fixed point of g is moved by g^{h}. In either case this implies that g does not commute with g^{h}. If no transition point of g is moved by h, then the orbitals of g^{h} are those of g. It follows from the chain rule that on each orbital J of g, g and g^{h} agree on a small neighborhood of the endpoints of J. By [8, §4] two elements of PL_{+}(I) commute over a common orbital of support only if they admit a common root over that orbital. In particular, if g ↾ J and g^{h} ↾ J agree in a neighborhood of the endpoints of J and they commute, then they must be equal. Hence h commutes with g over each orbital of support of g, so h and g commute. □

We now turn our attention to our representation of G as a subgroup H = ⟨X⟩ of Homeo_{+}(I) where X is geometrically proper. If H has more than one component of support, then the restriction to each is a quotient of H. Since no non-trivial element of F commutes with every element of F′ and since F′ = G′ is simple, it follows that every nontrivial normal subgroup of G contains G′. Consequently every proper quotient of H ≅ G is abelian. Thus if no restriction were an isomorphism, H would be abelian (which is absurd). We can thus replace H by its restriction to a component of its support on which the restriction is faithful, and further, we can conjugate by a homeomorphism of R so that the support is (0, 1). Note that this new embedding of G in Homeo_{+}(I) is geometrically proper if the original embedding is geometrically proper.

Let π_{0} denote the restriction of the germ homomorphism γ_{0}^{+} to H and π_{1} denote the restriction of γ_{1}^{−} to H; define π_{H}(h) := (π_{0}(h), π_{1}(h)). Observe that since X is geometrically proper we have that for each i < 2, there is at most one element of X which is not in the kernel of π_{i}. Observe that this implies the image of π_{H} is abelian and hence H′ ⊆ ker(π_{H}).

Claim 10.6. The image of π_{H} is not cyclic.

Proof. Recall that G′ = ker(π_{G}) and H′ ⊆ ker(π_{H}). In particular, ϕ induces a well defined homomorphism from G/G′ to H/ ker(π_{H}). If the image of π_{H} were cyclic, then this homomorphism would have a nontrivial kernel.

Pick g := f_{0}^{m}f_{1}^{n} ∈ G \ G′ in the kernel of π_{H}. The element g will have connected extended support. As ϕ(g) ∈ ker(π_{H}) we must have the support of ϕ(g) is contained in [x, y] for some 0 < x < y < 1. As the support of H is (0, 1) there is an h ∈ H so that xh > y, and for this h we have ϕ(g) commutes with ϕ(g)^{h}, but not with h. Now, g commutes with ϕ^{−1}(ϕ(g)^{h}), but not with ϕ^{−1}(h), however, ϕ^{−1}(ϕ(g)^{h}) = g^{ϕ^{−1}(h)}, contradicting Claim 10.5. □

At this point we know that, by the geometric properness of X, for each coordinate i ∈ {0, 1} there is a unique element h_{i} ∈ X so that i is in the extended support of h_{i} and so that h_{0} ≠ h_{1}. The fact that h_{0} and h_{1} are distinct and unique implies that the image of π_{H} is the product of the images of π_{0} and π_{1}.

Claim 10.7. For each element h of X whose extended support contains 0 or 1, there is no finite subset T of the kernel of π_{H} so that ker(π_{H}) ⊆ ⟨T ∪ {h}⟩.

Proof. Let h be given and suppose without loss of generality that 0 is in the extended support of h. As noted above, 1 can not be in the extended support of h. Since ⟨X⟩′ ⊆ ker(π_{H}), there are nontrivial elements in ker(π_{H}). Because the orbital of H is (0, 1), there are points arbitrarily close to 0 and 1 moved by elements of ker(π_{H}). It follows that if T ⊆ ker(π_{H}) is finite, then there is a neighborhood of 1 fixed by all elements of ⟨T ∪ {h}⟩ and thus ⟨T ∪ {h}⟩ cannot contain all of ker(π_{H}). □

In order to finish the proof, it suffices to show that π_{G} (ϕ^{−1}(h_{0})) and π_{G} (ϕ^{−1}(h_{1})) generate the image of π_{G} and that each have exactly one (necessarily different) nonzero coordinate. Since, by the proof of Claim 10.6, ϕ induces an isomorphism G/G′ ≅ H/ ker(π_{H}), it follows that {π_{G}(ϕ^{−1}(h_{i})) | i < 2} must generate G/G′. On the other hand, by Claims 10.4 and 10.7, it must be that one coordinate of π_{G}(ϕ^{−1}(h_{i})) must be 0 for each i ∈ {0, 1}. This shows that these two elements, which generate the group K, together make a set of the form {(p, 0), (0, q)} for some non-zero p and q, and therefore G ≅ F. □

Remark 10.8. The group E = {(p, q) ∈ Z × Z | p + q ≡ 0 mod 2} is a subgroup of Z × Z which is not of the form P × Q and hence π_{F}^{−1}(E) is a finite index subgroup of F which is not isomorphic to F. In particular, there are finite index subgroups of F which do not admit geometrically proper generating sets.

11. Abstract Ping-Pong Systems

In this section we will abstract the analysis of geometrically fast systems of bumps in previous sections to the setting of permutations of a set S. (By permutation of S we simply mean a bijection from S to S.) Our goal will be to state the analog of Theorem 1.1 and its consequences. The proofs are an exercise for the reader.

Suppose now that A is a collection of permutations of a set S such that A∩A^{−1} = ∅. A ping-pong system on A is an assignment a ↦ dest(a) of sets to each element of A^{±} such that whenever a and b are in A^{±} and s ∈ S:

• dest(a) ⊆ supt(a) and if s ∈ supt(a), then there is an integer k such that sa^{k} ∈ dest(a);

• if s ∈ supt(a), then sa ∈ dest(a) if and only if s ∉ src(a) := dest(a^{−1});

• if a ≠ b, then dest(a) ∩ dest(b) is empty;

• if dest(a) ∩ supt(b) ≠ ∅, then dest(a) ⊆ supt(b). The following lemma summarizes some immediate consequences of this definition.

Lemma 11.1. Given a set S and a collection A of permutations of S equipped with a ping-pong system, the following are true:

• if a ∈ A and s ∈ supt(a), then there is a unique k ∈ Z such that:

sa^{k} ∈ supt(a) \ (src(a) ∪ dest(a))

• if a ∈ A, then dest(a)a ⊆ dest(a); In particular, all elements of A have infinite order.

As remarked in Section 3, geometrically fast sets of bumps admit a ping-pong system. The meanings of source, destination, and locally reduced word all readily adapt to this new context. Furthermore, the proofs of Lemmas 5.1–5.11 given in Section 5 use only the axiomatic properties of a ping-pong system and thus these lemmas are valid in the present context. The next example is simplistic, but it will serve to illustrate a number of points in this section.

Example 11.2. View the real projective line P as R ∪ {∞} and PSL_{2}(Z) as a group of fractional linear transformations of P. The homeomorphisms α and β of P defined by

tα := t + 1 tβ := \frac{t}{1 − t}

generate PSL_{2}(Z). If we take A = {α^{2}, β^{2}}, then

src(α^{2}) := (−∞, −1) dest(α^{2}) := [1, ∞)
src(β^{2}) := (0, 1) dest(β^{2}) := [−1, 0)

defines a ping-pong system. It is well known that ⟨α^{2}, β^{2}⟩ is free; in fact this is one of the classical applications of the Ping-Pong Lemma.

In order to better understand ⟨A⟩ when A is a set of permutations admitting a ping-pong system, it will be helpful to represent ⟨A⟩ as a family of homeomorphisms of a certain space K_{A}. This space can be thought of as a space of histories in the sense of Section 5. If S is the underlying set which elements of A permute, let M = M_{A} denote the collection of all sets of the form

s̃:= {a ∈ A | s ∈ supt(a)}

where s ∈ S \ ⋃{dest(a) | a ∈ A^{±}}. Elements of M will play the same role as the initial markers of a geometrically fast collection of bumps.

Example 11.3. Continuing with the Example 11.2, M consists of two points: ˜0 = {α} and ˜∞ = {β}. We can also restrict the action of PSL_{2}(Z) on P to the irrationals. In this case M is empty.

For s ∈ M, it will be convenient to define dest(s̃) := ⋂{supt(a) \ src(a) | a ∈ s̃} and supt(s̃) := ∅. Define K_{A} to be all η such that:

• η is a suffix closed family of finite strings in the alphabet A^{±} ∪ M;

• if ab are consecutive symbols of an element of η, then dest(a) ⊆ supt(b) \ src(b);

• for each n, there is at most one element of η of length n;

• if w ∈ η and η does not contain a symbol from M, then w is a proper suffix

of an element of η. The second condition implies that elements of η are freely reduced since if b = a^{−1}, then src(b) = dest(a). Observe that if w is in η, the only occurrence of an element of M in w must be as the first symbol of w (and there need not be any occurrence of an element of M in w).

Notice that every η ∈ K_{A} has at least one element other than ε and that all elements of η of positive length must have the same final symbol. We define dest(η) := dest(a) where a is the final symbol of every element of η other than ε. We topologize K_{A} by declaring that [w] := {η ∈ K_{A} | w ∈ η} is closed and open. Notice that if η is finite, it is an isolated point of K_{A}.

Proposition 11.4. K_{A} is a Hausdorff space and if A is finite, then K_{A} is compact.

Each a ∈ A^{±} defines a homeomorphism â : K_{A} → K_{A} by:

ηâ := \begin{cases}\{ua | u ∈ η\} ∪ \{ε\} & if dest(η) ⊆ supt(a) \ src(a) \\ \{u | ua^{−1} ∈ η\} & if dest(η) = src(a) \\ η & if dest(η) ∩ supt(a) = ∅ \end{cases}

Thus ηâ is obtained by appending a to the end of every element of η, performing local reductions with applicable, and possibly including ε. Set Â = {â : a ∈ A}.

We say that a ping-pong system on A is faithful if Λ_{A} := {η ∈ K_{A} : η is finite} is dense in K_{A} (i.e. whenever w is in some η ∈ K_{A}, there is a finite η′ ∈ K_{A} which has w as an element). This hypothesis ensures that the group ⟨A⟩ can be faithfully represented as a group of homeomorphisms of K_{A} — see Theorem 11.6 below.

Example 11.5. As noted above, if we restrict the elements of PSL_{2}(Z) to the set S of irrationals, then M = ∅ and in particular the system is not faithful. On the other hand,

dest(α^{4}) := (2, ∞) ∩ S dest(α^{−4}) := (−∞, −2) ∩ S
dest(β^{4}) := (−1/2, 0) ∩ S dest(β^{−4}) := (0, 1/2) ∩ S.

defines a ping-pong system in which M contains a single element {α, β}.

While not every ping-pong system is faithful, the reader is invited to verify that if A admits a ping-pong system, then {a^{2} | a ∈ A} admits a faithful ping-pong system.

The next theorem is the abstract analog of Theorem 5.12; the proof is left to the interested reader.

Theorem 11.6. If A is a set of permutations which admits a ping-pong system, then a ↦ â extends to an epimorphism of ⟨A⟩ onto ⟨Â⟩. If the ping-pong system is faithful, then the epimorphism is an isomorphism.

The map x ↦ η(x) defined in Section 5 adapts mutatis mutandis to define a map s ↦ η(s) from S into K_{A}. It is readily verified that if a ∈ A and s ∈ S, then η(sa) = η(s)â.

We now introduce an abstract data structure which encodes the symbolic dynamics of a ping-pong system. A blueprint for a ping-pong system is a pair 𝔅 = (B, supt) such that:

• B is a set and supt is a binary relation on B which is interpreted as a set-valued function: b ∈ supt(a) if (a, b) ∈ supt;

• if a ∈ B and supt(a) is nonempty, then a ∈ supt(a);

• if a ∈ A, then there is a unique a^{−1} ∈ A \ {a} with supt(a^{−1}) = supt(a). Additionally, setting A := {a ∈ B | supt(a) ≠ ∅} we require that:

• if b ≠ c ∈ B \ A, then ~ b ≠ ~ c where ~ b := {a ∈ A | b ∈ supt(a)}. If A is a set of permutations which admits a ping-pong system, then the blueprint 𝔅_{A} = (B_{A}, supt_{A}) for the system is defined by B_{A} := {a | a ∈ A^{±}} ∪ {~ s | s̃ ∈ S̃} with b ∈ supt_{A}(a) if dest(b) ⊆ supt(a). Also, if 𝔅 = (A, supt) is a blueprint for a ping-pong system, then one defines K_{𝔅} and homeomorphisms ^a : K_{𝔅} → K_{𝔅} for a ∈ A^{𝔅} by a routine adaptation of the construction above. For instance, K_{𝔅} consists of all η such that:

• η is a suffix closed family of finite strings in the alphabet B;

• if ab are consecutive symbols of an element of η, then b ≠ b^{−1} and a ∈

       supt(b);

• for each n, there is at most one element of η of length n;

• if w ∈ η and η contains only symbols from A, then w is a proper suffix of an

element of η. In fact K_{A} is can be regarded as factoring though its blueprint in the sense that K_{A} = K_{𝔅_{A}} modulo identifying a and a. Two blueprints are isomorphic if they are isomorphic as structures. It is routine to verify that the following theorem holds as well.

Theorem 11.7. If 𝔅_{0} and 𝔅_{1} are isomorphic blueprints for ping-pong systems, then the isomorphism induces a homeomorphism θ : K_{𝔅_{0}} → K_{𝔅_{1}} such that g ↦ g^{θ} defines an isomorphism between ⟨â | a ∈ A_{0}⟩ and ⟨â | a ∈ A_{1}⟩.

If A is a set of permutations which admits a faithful ping-pong system, then the blueprint for A and for {a^{k(a)} | a ∈ A} are canonically isomorphic whenever a ↦ k(a) is an assignment of a positive integer to each element of A.

Corollary 11.8. Any set of permutations A which admits a faithful ping-pong system is an algebraically fast generating set for ⟨A⟩.

If the system is not faithful, then {a^{2} | a ∈ A^{2}} may contain new markers, as was illustrated in Example 11.5. Notice that in this example, both ⟨α^{2}, β^{2}⟩ and ⟨α^{4}, β^{4}⟩ are free — and hence marked isomorphic — even though the blueprints associated to the ping-pong systems are not isomorphic.

The following example shows that an abstract ping-pong system can have structure and behavior that are quite different from a fast system of functions in PL_{+}(I).

Example 11.9. Consider the blueprint 𝔅 with the underlying set of symbols consisting of a, b, a^{−1}, b^{−1} and ∗. The support function is defined as follows:

supt(a) := supt(a^{−1}) = {a, a^{−1}, ∗} supt(b) := supt(b^{−1}) = {b, b^{−1}, ∗}

Thus A = {a, b, a^{−1}, b^{−1}} and M = {∗}. Observe histories in K_{𝔅} use at most one symbol from A = {a, b, a^{−1}, b^{−1}}. That is, aside from the possible presence of an initial marker, words occurring in histories are constant. We now note that the group G := ⟨â, b̂⟩ has torsion. Consider the commutator aba^{−1}b^{−1} and let g be its evaluation in G. One can check that

∗ · g = ∗b^{−1}  ∗ · g^{2} = ∗a^{−1}  ∗ · g^{3} = ∗

and that ∗, ∗a^{−1}, and ∗b^{−1} are the only elements of K_{𝔅} not fixed by the action of g (here we are referring to these three finite histories by their maximal element). In particular, g has order 3.

A blueprint 𝔅 is (cyclically) orderable if there is a (cyclic) ordering on B such that for all a ∈ A, supt(a) is an interval in the (cyclic) ordering with endpoints src(a) and dest(a). It is readily verified that the (cyclic) order on B induces a reverse lexicographic (cyclic) order on K_{𝔅} which is preserved by the homeomorphisms â for a ∈ A.

Corollary 11.10. If A is a finite set of permutations which admits a faithful pingpong system, then ⟨A⟩ embeds into Thompson’s group V. If the blueprint of A is cyclically orderable, then ⟨A⟩ embeds into T. If the blueprint of A is orderable, then ⟨A⟩ embeds into F.

Proof. It is readily verified that any finite blueprint can be realized as the blueprint of a ping-pong system of a finite subset of V. Moreover, if the blueprint is cyclically orderable (or orderable), then it can be realized by elements of T (respectively F). The corollary follows by Theorem 11.7. □

We finish by noting the following proposition which shows that while torsion can be observed in fast generated subgroups of V, as illustrated in Example 11.9 and Corollary 11.10, any fast generated subgroup of T is torsion free. This is perhaps surprising since T itself does have many elements of finite order.

Proposition 11.11. If A is a fast set of bumps in Homeo_{+}(S^{1}), then ⟨A⟩ is torsion free.

Proof (sketch). For each s ∈ S^{1} and a ∈ A^{±}, fix a curve γ_{s,a} : [0, 1] → S^{1} such that s = γ_{s,a}(0) and sa = γ_{s,a}(1) and either the range of γ_{s,a} is contained in supt(a) or else sa = s and γ_{s,a} is constant. If s ∈ S^{1} and w is an A-word, we define γ_{s,w} by concatenating the curves and reparametrizing (in the sense of homotopy): γ_{s,ua} is γ_{s,u} followed by γ_{su,a} if u is a word and a ∈ A^{±}. If u is a local reduction of w at s, then γ_{s,u} is homotopic to γ_{s,w} (relative to the endpoints).

Suppose for contradiction that w is a word such that w has finite order n > 1. Notice that w cannot have fixed points. In particular, for any lifting of the paths {γ_{s,w} | s ∈ S^{1}} to R, the net change in position for the lifted paths is either always positive or always negative. This implies that for any t ∈ S^{1}, the path γ_{t,w^{n}} — which can be lifted to a concatenation of lifts of the γ_{sw^{i},w} for i < n — cannot be homotopic to a point. In particular, no local reduction of w^{n} can be trivial. Now let t be the left transition point of some element of A, noting that t is not in any foot of an element of A. Since γ_{s,w^{n}} is not homotopic to a point, the local reduction of w^{n} at t is not trivial. Thus tw^{n} is in a foot of A, a contradiction. □

References

1. C. Bleak, An algebraic classification of some solvable groups of homeomorphisms, J. Algebra 319 (2008), no. 4, 1368–1397.

2. , A minimal non-solvable group of homeomorphisms, Groups Geom. Dyn. 3 (2009), no. 1, 1–37.

3. C. Bleak and B. Wassink, Finite index subgroups of R. Thompson’s group F, ArXiv preprint: https://arxiv.org/pdf/0711.1014.pdf, 2007.

4. Matthew G. Brin, The ubiquity of Thompson’s group F in groups of piecewise linear homeomorphisms of the unit interval, J. London Math. Soc. (2) 60 (1999), no. 2, 449–460.

5. , Elementary amenable subgroups of R. Thompson’s group F, Internat. J. Algebra Comput. 15 (2005), no. 4, 619–642.

6. Matthew G. Brin and Fernando Guzmán, Automorphisms of generalized Thompson groups, J. Algebra 203 (1998), no. 1, 285–348.

7. M. G. Brin and C. C. Squier, Groups of piecewise linear homeomorphisms of the real line, Invent. Math. 79 (1985), 485–498.

8. , Presentations, conjugacy, roots, and centralizers in groups of piecewise linear homeomorphisms of the real line, Comm. Algebra 29 (2001), no. 10, 4557–4596.

9. K. S. Brown, Finiteness properties of groups, Journal of Pure and Applied Algebra 44 (1987), 45–75.

10. J. W. Cannon, W. J. Floyd, and W. R. Parry, Introductory notes on Richard Thompson’s groups, Enseign. Math. (2) 42 (1996), no. 3-4, 215–256.

11. R. Fricke and F. Klein, Vorlesungen über die theorie der automorphen funktionen, vol. 1, Teubner, Leipzig, 1897.

12. S. Kim, T. Koberda, and Y. Lodha, Chain groups of homeomorphisms of the interval and the circle, accepted for publication in Ann. Sci. Éc. Norm. Supér.

13. F. Klein, Neue Beiträge zur Riemann’schen Functionentheorie, Math. Annalen 21 (1883), 141–218.

14. A. M. Macbeath, Packings, free products and residually finite groups, Proc. Cambridge Philos. Soc. 59 (1963), 555–558.

15. A. Navas, Quelques groupes moyennables de difféomorphismes de l’intervalle, Bol. Soc. Mat. Mexicana (3) 10 (2004), no. 2, 219–244 (2005).

16. J. Tits, Free subgroups in linear groups, J. Algebra 20 (1972), 250–270.

17. S. White, The group generated by x ↦ x + 1 and x ↦ x^{p} is free, J. Algebra 118 (1988), 408–422.

Collin Bleak, School of Mathematics and Statistics, University of St. Andrews, St. Andrews, Fife KY16 9SS

Matthew G. Brin, Department of Mathematical Sciences, Binghamton University, Binghamton, NY 13902-6000

Martin Kassabov, Justin Tatch Moore, Department of Mathematics, Cornell University, Ithaca, NY 14853-4201

Matthew C. B. Zaremsky, Department of Mathematics, University at Albany (SUNY), Albany, NY 12222