COMPLEXITY AMONG THE FINITELY GENERATED SUBGROUPS OF THOMPSON’S GROUP

COLLIN BLEAK, MATTHEW G. BRIN, AND JUSTIN TATCH MOORE

Abstract. We demonstrate the existence of a family of finitely generated subgroups of Richard Thompson’s group F which is strictly well-ordered by the embeddability relation in type ε_{0} + 1. All except the maximum element of this family (which is F itself) are elementary amenable groups. In fact we also obtain, for each α < ε_{0}, a finitely generated elementary amenable subgroup of F whose EA-class is α + 2. These groups all have simple, explicit descriptions and can be viewed as a natural continuation of the progression which starts with Z + Z, Z ≀ Z, and the Brin-Navas group B. We also give an example of a pair of finitely generated elementary amenable subgroups of F with the property that neither is embeddable into the other.

1. Introduction

Subgroups of P L_{+}(I), the group of order preserving, piecewise linear self homeomorphisms of the unit interval, have been a source of groups with interesting properties in which calculations are practical. There is increasing evidence that all countable, or at least finitely generated, such subgroups will eventually be undertood. Among these groups is Richard Thompson’s group F. It is extremely easy for a subgroup of P L_{+}(I) to contain an isomorphic copy of F as a subgroup [4]. Thus not containing a subgroup isomorphic to F (being F -less) is a severe restriction on subgroups of P L_{+}(I). This has led to the following conjectured dichotomy of Brin and Sapir.

Conjecture 1. [5] [22] If G is a subgroup of P L_{+}(I), then either G is elementarily amenable or else G contains a copy of F.

The elementary amenable groups form a class EG and are those groups that can be built recursively from finite and abelian groups by a (possibly transfinite) process using extension and directed union. The elementary amenability class (EA-class) of a group G in EG is an ordinal valued measure of the complexity of the recursive construction of G. (Details are given in Section 3.) Thompson’s group F is not elementary amenable; it is finitely generated and every nontrivial normal subgroup of F contains isomorphic copies of F (see [8]). Thus an elementary amenable group must be F -less.

2010 Mathematics Subject Classification. 20E22, 20B07, 20B10, 20E07.

Key words and phrases. elementary amenable, elementary group, geometrically fast, homeomorphism group, ordinal, Peano Arithmetic, piecewise linear, Thompson’s group, transition chain.

This paper is in part a product of a visit of the first and third author to the Mathematisches Forschungsinstitut Oberwolfach, Germany in December 2016 as part of their Research In Pairs program. The third author was partially supported by NSF grant DMS–1600635.

Our basic thesis is that Conjecture 1 will eventually be a corollary of a more complete understanding of the partial order (𝔉, ↪) where 𝔉 is the set of biembeddability classes of finitely generated subgroups of F and A ↪ B asserts that members of the class A embed into members of the class B. While we do not settle Conjecture 1, this paper explores the universe of F -less subgroups of P L_{+}(I) and finds a complex collection 𝔖 of elementary amenable subgroups of Thompson’s group F itself. The collection 𝔖 is likely to play an important role in settling Conjecture 1 and more generally in understanding the class of finitely generated F -less subgroups of F.

There are two main features of this paper. The first is the shift of attention away from the usual “isomorphism type and containment relation” (the Hasse diagram) of subgroups, and toward the coarser “biembeddability class and embeddability relation” where two groups are biembeddable if each embeds in the other. A finer analysis of the isomorphism types of subgroups of F does not seem feasible at this time.

The second feature is the discovery of a rich arithmetic that lives on 𝔖 that greatly facilitates transfinite induction and recursion. The usual ingredients of transfinite recursion are base, successor, and limit stage: a base object A_{0} must be built, an object A_{α+1} must be built from the object A_{α}, and for a limit α, an object A_{α} must be built from the objects A_{β} with β < α. We show that 𝔖 can be equipped with arithmetic operations that allow us to easily build from B_{α} ∈ 𝔖 not only B_{α+1}, but also B_{α·ω} and even B_{ω^{α}} with equal ease. This has two consequences. First, our groups are remarkably easy to “write down.” This gives a set of groups that are remarkably simple to describe in spite of having extremely complex constructions (high EA-class) as elementary amenable groups. Second, the bulk of the work in the paper is shifted from construction to analysis. In fact, it is still a wonder to the authors that these groups can be analyzed at all.

1.1. The results. We now state and discuss our results in somewhat more detail. We give indication of the meaning of terminology in what follows; full definitions are given in Sections 2 and 3 and as noted.

The complex nature of (𝔉, ↪) is demonstrated by our main result:

Theorem 1. There is a transfinite sequence (G_{ξ} | ξ < ε_{0}) of finitely generated elementary amenable subgroups of F such that:

• G_{0} is the trivial group and G_{ξ+1} ≅ G_{ξ} + Z;

• G_{ξ} embeds into G_{η} if and only if ξ ≤ η;

• Given 0 ≤ α < ε_{0} and n < ω, let ξ = ω^{(ω^{α})·(2^{n})}. If α > 0, then the EA-class

of G_{ξ} is ω · α + n + 2. If α = 0, then the EA-class of G_{ξ} is n + 1.

In particular, for each α < ε_{0}, there is a ξ such that the EA-class of G_{ξ} is α + 2. (If the EA-class of a finitely generated group is infinite, it is always of the form α + 2.) Thus Theorem 1 improves previous work of the second author [5], who demonstrated that there are finitely generated subgroups of F in EG of class ξ + 2 for each ξ < ω^{2}. With ω the smallest infinite ordinal, the ordinal ε_{0} is the smallest ordinal solution to the equation ω^{x} = x. If we define a sequence (τ_{k})_{k∈ω} of ordinals recursively by τ_{0} := 2, τ_{1} := ω and τ_{k+1} := ω^{τ_{k}} for k > 1, then ε_{0} can be described as

ε_{0} = sup{τ_{k} | k ∈ ω} = ω^{ω^{ω^{ω^{·^{·^{·}}}}}} .

g_{4}^{.................}^{.................}^{.................} f_{4}  ^{1}^{1} ^{0}^{0}  g_{5}^{.................}^{.................}^{.................}^{.................} f_{5}  _{1}^{1} _{0}^{0}

Figure 1. G_{τ_{4}} := ⟨f_{4}, g_{4}⟩ and G_{τ_{5}} := ⟨f_{5}, g_{5}⟩. The EA-classes of these groups are ω^{ω} + 2 and ω^{ω^{ω}} + 2, respectively.

This countable ordinal is well known to play a central role in proof theory and in particular in understanding the limitations and consistency of Peano Arithmetic (see e.g. [12, # 4] [15] [16] [1, §D8]).

The groups in 𝔖 := {G_{ξ} | ξ < ε_{0}} are built from Z using certain familiar group-theoretic operations — direct sums and wreath products — as well as a new operation which is analogous to ordinal exponentiation base ω. Whether this new operation is meaningful in a broader setting is unclear but even in our rather restrictive setting, it already yields a wealth of examples. The operations also make the construction of the groups in 𝔖 straightforward and highly analogous to the construction of ordinals below ε_{0} from 0 using exponentiation base ω and addition. Specifically, given the Cantor normal form for an ordinal ξ < ε_{0} there is an efficient algorithm that lets one write down a finite number of generators (explicitly as words in the generators of F if desired) for a group with EA-class ω · ξ + 2.

While the results of this paper concern groups, the focus of the analysis is on generating sets. The groups in 𝔖 are specified by a family of generating sets S. This collection has the property that A is in S if and only if each of its two element subsets is in S. The 2-element sets in S generate precisely the groups G_{τ_{k}} in the family 𝔖 = {G_{ξ} | ξ < ε_{0}}; this is the reason for setting τ_{0} := 2. Theorem 1 implies, in particular, that the G_{τ_{k}} are an infinite family of elementary amenable 2-generated subgroups of F which are not pairwise biembeddable. Two of these generating pairs are illustrated in Figure 1.

The isomorphism types of the G_{τ_{k}} are parametrized by the nonnegative integer k which we refer to as the oscillation of the generating pair from S. Figure 1 illustrates pairs with oscillation 4 and 5. The function giving the oscillations of the pairs from an A ∈ S is the signature of A. Each generating set in S is equipped with a total order, and the signature serves as a complete invariant for all of S.

Theorem 2. If A, B ∈ S have the same signature, then the order preserving bijection from A and B extends to an isomorphism from ⟨A⟩ to ⟨B⟩.

Thus one may analyze 𝔖 by analyzing the set 𝒮 of all signatures of S. We also algebraically characterize the relation ≤ on 𝒮 which comes from the embeddability relation on 𝔖.

The family S is robust at a group-theoretic level: if A ∈ S, then ⟨A⟩ is an HNN extension of a group which is itself an increasing union subgroups of the form ⟨B⟩ for B ∈ S. On the other hand, while the closure properties of S — and thus of 𝒮 — are important in the group-theoretic analysis of 𝔖, they introduce redundancies which obscure the structure of the order on these classes. This is resolved by introducing algebraic operations +, ∗, and exp on 𝒮 and using them to define a subclass ℛ of 𝒮. The next theorem is at the core of the proof of Theorem 1. It shows that ℛ provides a notion of “normal form” for 𝒮 and consequently for S (here A ≡ B denotes A ≤ B ≤ A).

Theorem 3. For each A is in 𝒮 there is a unique B in ℛ such that A ≡ B. Moreover there is a natural isomorphism

(ℛ, <, +, exp) ≅ (ε_{0}, ∈, +, ζ ↦ ω^{−1+ζ})

provided + is restricted to those pairs in ℛ for which the sum remains in ℛ.

Thus each biembeddability class in 𝔖 has a distinguished representative — unique up to marked isomorphism — identified by the form of its signature. Moreover, this representative can be viewed as being built up from Z using simple arithmetic operations which are analogs of the fundamental operations of ordinal arithmetic.

The well-foundedness and linearity of (𝒮 , <) are subtle matters and likely to be of independent interest. In fact while it can be phrased in the language of arithmetic, the well-foundedness of (𝒮 , <) is not provable in Peano Arithmetic. This is a consequence of Gentzen’s analysis of the consistency of Peano Arithmetic [12, #4] and Gödel’s second incompleteness theorem [13] [14]. At a more pragmatic level, future methods of proof may lend themselves more naturally to induction on 𝒮 than to induction on ε_{0}.

Extending the chain 𝔖 by setting G_{ε_{0}} = F, we make the following conjectures. Recall that PL_{+}(I) is the group of all piecewise linear elements of Homeo_{+}(I).

Conjecture 2. If H is a finitely generated subgroup of PL_{+}(I), then either F embeds into H or else there is an η < ε_{0} such that H embeds into G_{η}.

Conjecture 3. The partial order (𝔉, ↪) is a well-quasi-order — it contains no infinite decreasing sequences and no infinite antichains.

Observe that Conjecture 2 immediately implies Conjecture 1 since each G_{η} for η < ε_{0} is elementary amenable. It also implies another conjecture of the second author which complements Conjecture 1: every elementary amenable subgroup of PL_{+}(I) embeds into F. Moreover, this would imply that ε_{0} is a strict upper bound for the EA-class of every finitely generated elementary amenable subgroup of F.

Conjecture 3 is really about understanding those finitely generated subgroups of F which do not contain F. The second author has shown that not containing an isomorphic copy of F is a strong restriction on subgroups of F (and more generally subgroups of PL_{+}(I)) [4]. Motivation for Conjecture 3 stems in part from the heuristic that forbidding a ubiquitous substructure often portends a well developed structure theory (see, for instance [17]).

There are limitations, however, as to what one can expect in the direction of these conjectures. We show that there is a finitely generated subgroup of F which is not biembeddable with any G_{ξ} for ξ ≤ ε_{0}. Moreover, we show that (𝔉, ↪) is not a linear ordering.

Theorem 4. There are finitely generated subgroups H_{0} and H_{1} of F of EA-class ω + 2 such that H_{0} does not embed into H_{1} and vice versa.

Lastly we remark, without proof, that the sequence of groups G_{τ_{k}} with the generating pairs (f_{k}, g_{k}) converges in the space of 2-marked groups to the free group on 2 generators. We refer the reader to [6] for definitions and relevant arguments.

1.2. Related results. All solvable groups are necessarily elementary amenable. The solvable subgroups of F have been thoroughly analyzed by the first author in [2]. In particular, he proves that Conjecture 2 holds for the finitely generated solvable subgroups H of PL_{+}(I) [2]: every finitely generated solvable subgroup of PL_{+}(I) embeds into G_{ω^{ω}}, which is the Brin-Navas group B ([5] Fig. 5, [18] Example 6.3).

In [23], A. Taylor finds uncountably many pairwise nonisomorphic elementary amenable subgroups of F. These examples are not finitely generated, are not solvable but are locally solvable, and all have EA-class ω + 1.

In [20], Ol’shanskii and Osin show that for every countable ordinal α, there is a finitely generated group G ∈ EG with EA(G) = α + 2. The construction in [20] is recursive and based on HNN extensions. The operations on 𝔖 in the current paper accelerate the recursive process and lead to easier descriptions of the elements of 𝔖.

1.3. Organization. Section 2 is essentially a continuation of this introduction and it gives definitions and examples sufficient to introduce the reader to the groups that we build and how we build them. It does not give any hints as to their analysis. Section 3 fixes more notation and terminology which is used in the paper. It also contains a review of a number of prerequisites for the paper: details from [3]; ordinals and their arithmetic; elementary amenable groups and EA-class; wreath products of permutation groups. The reader may wish to skim or skip Section 3 and then refer back to the various subsections as needed. In Section 4, the oscillation function is developed. This function is further developed in the context of standard generating sets in Section 5, where we study the signature of an element of S and prove Theorem 2. In Section 6 we introduce the notion of an inflation of a standard generating set by one of its elements and show that the result is again a standard generating set. The interaction of the family S with wreath products is detailed in Section 7. Section 8 develops analogs of the operations of ordinal arithmetic for signatures of elements of S. This analysis is then used to show that (𝔖, ↪) is a well-order with ordertype ε_{0} in Section 9, where the proofs of Theorems 1 and 3 are completed. Finally, Section 10 contains a proof of Theorem 4, establishing that (𝔉, ↪) is not a linear order.

2. The objects of study

In this section we describe the generating sets in S and the functions that are elements of such sets. We also describe the signature associated to a generating set. The class of signatures ℛ of Theorem 3 is described as well as the isomorphism from ℛ to ε_{0}. An aim of this section is to indicate how, given a suitable EA class α < ε_{0}, one can write down a set of generators of a group with EA class α.

2.1. The anatomy of a homeomorphism. To describe the elements of Homeo_{+}(I) that we work with, we set some terminology. We write homeomorphisms to the right of their arguments and compose from left-to-right. The support supt(f) of f ∈ Homeo_{+}(I) is the set {t ∈ [0, 1] | tf ≠ t}, and the extended support of f is the interior of the closure of supt(f).

For f ∈ Homeo_{+}(I), a component J of supt(f) is an orbital of f, and a function with exactly one orbital is be called a bump. The transition points of f are the endpoints of the orbitals of f. A bump f with orbital J is positive if tf > t for one (equivalently all) t ∈ J, and negative otherwise. If g ∈ Homeo_{+}(I) has multiple orbitals one of which is J, then the bump f ∈ Homeo_{+}(I) with f|_{J} = g|_{J} is called a bump of g. If f ∈ Homeo_{+}(I) and X ⊆ I is a union of orbitals and fixed points of f, then we write f|_{X} to denote the homeomorphism which coincides with f on X and which is the identity outside of X.

To conserve space in drawing functions, we do not use horizontal and vertical x and y axes as in Figure 1, but draw as if the x and y axes are at 45 degrees and the part of the line y = x in the first quadrant stretches horizontally to the right from the origin. The axes themselves and the line y = x are suppressed, as are intervals of fixed points. As in the following,

(2.1)  f  g

positive bumps become arcs above the horizontal, and negative bumps are arcs below the horizontal. The function f is a positive bump, and the function g has one negative bump and two positive bumps.

2.2. The attribute fast. To control the isomorphism type of the groups that we generate, we need some mild controls on the dynamics of our generating sets. We use some concepts from [3].

Suppose that A ⊂ Homeo_{+}(I) is a set of bumps.

Definition 2.1. A marking of A is an assignment a ↦ s_{a} of an element of the support of a to each a ∈ A. The feet of a with respect to this marking are the intervals (u, s_{a}) and [t_{a}, v) where (u, v) is the support of a and t_{a} := s_{a}a if a is positive and t_{a} := s_{a}a^{−1} if a is negative.

This is illustrated below for positive a.

a u s_{a}  t_{a} v

An f ∈ Homeo_{+}(I) equipped with a marking of its bumps is a marked function. The expression “a marked function f ∈ Homeo_{+}(I)” always means that f comes with a fixed marking even if the marking is not specified.

The finiteness assumptions in the next definitions are more restrictive than in [3], but are sufficient for us and add some conveniences. A collection B of marked bumps is geometrically fast (or just fast) if for every f ≠ g in B the feet of f are disjoint from the feet of g. If S ⊂ Homeo_{+}(I) is a finite set of marked functions and each element of S has only finitely many bumps, then we define S to be fast if the set of bumps of S is fast and no bump occurs in more than one element of S. Given a fast S, we always view S as being ordered according to the order on the maximum transition points of its elements. Note that no two different elements of such an S are equal under this order.

The point of these concepts is that the isomorphism type of a subgroup of Homeo_{+}(I) generated by a fast set S of functions is determined by a very small amount of information from S. Specifically, if S′ is another fast set and h : S → S′ is a bijection that “preserves enough of the combinatorics” (including the order given above, the order of the feet, and the signs of the bumps), then h extends to an isomorphism from ⟨S⟩ to ⟨S′⟩. A more detailed statement is given in Section 3.2.

We exploit this in two ways. We can specify groups up to isomorphism by giving somewhat sloppy descriptions of the generating sets. Further, a result of [3] says that if S is fast, then ⟨S⟩ embeds in Thompson’s group F. Thus under the assumption that the pairs {f_{4}, g_{4}} and {f_{5}, g_{5}} in Figure 1 are fast, we can regard the groups G_{τ_{4}} and G_{τ_{5}} as subgroups of F with very specific isomorphism types.

2.3. Standard functions and standard pairs. Thompson’s group F is not elementary amenable, and to build a subgroup of F that is elementary amenable one must avoid including an isomorphic copy of F in the subgroup. By the Ubiquity Theorem [4], this places severe restrictions on the generating sets and the functions that can be used in the generating sets. The restrictions in the next definition reflect this.

Definition 2.2. A standard function is a marked function f in Homeo_{+}(I) with finitely many bumps satisfying all following properties:

(1) The extended support of f is an interval;

(2) every positive bump of f is to the right of every negative bump;

(3) the number of positive and negative bumps of f differ by at most one and there are at least as many positive bumps as negative bumps.

The functions f and g in (2.1) are both standard.

A set A of standard functions forms an element of S if each pair of elements of A forms a standard pair, which we will define after making some preliminary definitions. If f, g ∈ Homeo_{+}(I) are standard, then we write f ≪ g if their extended supports are disjoint and the extended support of f is to the left in [0, 1] of the extended support of g. We write f ⊏ g if the closure of the extended support of f is contained in the extended support of g. We write f < g if f ≪ g or f ⊏ g. If S ∈ Homeo_{+}(I) is fast and is totally ordered by < as just defined, then < is identical to the order on S from Section 2.2 determined by the order of the rightmost transition points.

The diagram below illustrates two pairs (f, g) of standard functions, where the left pair satisfies f ≪ g and the right pair satisfies f ⊏ g.

(2.2)  f.................  g  g  .................^{.................} f

Standard pairs of functions are defined recursively using a reduction operation that will be heavily used during our analysis in later sections. Suppose that f is a standard function. If f has more than two orbitals, then let X be the union of the orbitals of f except the maximum (rightmost) and minimum (leftmost) orbitals, and define f^{∘} to be f|_{X}. Observe that f^{∘} is again a standard function — we mark f^{∘} with the markers of f on the orbitals which remain in f^{∘}. If f has one or two orbitals and the left foot of the positive orbital is (r, s), define f^{∘} to be any positive bump with support (r, s) and an arbitrary marker. It will not be necessary to be more specific. It will be important later that in all cases each foot of f^{∘} is a subset of a foot of f.

Definition 2.3. A pair (f, g) of standard functions is a standard pair if it satisfies the following recursive definition:

(1) The set {f, g} is fast, and

(2) either f ≪ g, or else f ⊏ g and (g^{∘}, f) a standard pair.

The following diagram illustrates the recursive clause:

g .........^{.........} f  ↝  g^{∘} .........^{.........} f  ↝ g^{∘}^{.......} f^{∘} ↝ ^{g^{∘}^{∘}} ^{.......} f^{∘}

It is easily checked that both pairs (f, g) in (2.2), and the pairs (f_{4}, g_{4}) and (f_{5}, g_{5}) in Figure 1 are standard and that, up to topological conjugacy, (g_{5}^{∘}, f_{5}) coincides with (f_{4}, g_{4}).

Definition 2.4. A standard generating set is a finite set of marked functions in Homeo_{+}(I) which is pairwise standard. The collection of all standard generating sets is denoted S.

It is important to note here that any standard generating set is fast.

2.4. Oscillation and signature. In our analysis, we reduce the information in a standard generating set to a finite matrix of integers.

Definition 2.5. If f < g is a fast pair of marked functions, then we define their oscillation o(f, g) to be the number of orbitals of g that contain at least one transition point of f.

Definition 2.6. If A is in S, then the signature of A is the function A defined by A(f, g) = o(f, g) whenever f < g are in A. We refer to A as the base of the signature A.

Figure 2 shows the signature of a standard generating set with four elements. Since elements of S may have either one or even no elements, we include the base as part of the data of a signature.

If A and B are signatures with bases A and B, then we say that A and B are equivalent if |A| = |B| and the order preserving bijection θ : A → B satisfies A(f, g) = B(θ(f), θ(g)) whenever f < g are in A. We also extend this notion of equivalence to when A and B are just integer functions defined on pairs from ordered sets A and B; we use signature to refer to a function which is equivalent in this way to a signature of an element of S. In particular, every signature is uniquely equivalent to a signature with base {0, …, n − 1} for some n. These canonical representatives allow us say without guilt that a signature A is the signature of some S ∈ S when in reality A is only equivalent to the signature of S.

Theorem 2 (proven in Section 5) says that if A, B ∈ S have the same signature, then the order preserving bijection between A and B extends to an isomorphism between ⟨A⟩ and ⟨B⟩. If A is a signature, we define ⟨A⟩ := ⟨A⟩ where A ∈ S has signature (equivalent to) A.

[figure: .................................; ^{.......................}; ...........; ^{.......................}; d; c; b; a; c; b; a; d; 2; 2; 2; c; 2; 2; b; 3]

Figure 2. Four functions that are pairwise standard with various oscillation numbers. Their signature is displayed on the right. They generate a group of EA-class ω^{2} + ω · 2 + 2.

2.5. Arithmetic on signatures and normal forms. We now introduce arithmetic operations on the set of signatures which allow us to readily specify complex standard generating sets. The following theorem of Cantor is important motivation. (Ordinal arithmetic is reviewed in Section 3.3.)

Theorem 5. [9, §19 Theorem B] If α is a nonzero ordinal, there is a unique sequence β_{0} ≥ β_{1} ≥ ⋯ ≥ β_{n} such that

α = ∑_{i≤n} ω^{β_{i}} = ω^{β_{0}} + ω^{β_{1}} + … + ω^{β_{n}}.

If 0 < α < ε_{0}, each positive β_{i} is less than α and may be further expanded in the form of Theorem 5. Iterating the process, one obtains an expression of α in terms of 0, + and exponentiation base ω which is known as the Cantor normal form of α.

We now define analogs of these arithmetic operations on the set of signatures. We use 0 to denote the signature with empty base and Z to denote the signature with singleton base; notice that if |Z| = 1, then ⟨Z⟩ ≅ Z.

If A, B, C is in S then we define A = B + C to mean:

• A = B ∪ C and b < c for all b ∈ B and c ∈ C, and

• o(b, c) = 0 for all b ∈ B and c ∈ C. Notice that b ≪ c is equivalent to o(b, c) = 0 and b < c. Thus if A = B + C, then ⟨A⟩ = ⟨B⟩+⟨C⟩. Observe that while A = B+C expresses a ternary relation on S, it induces a well defined binary operation + on the set 𝒮 of signatures. Additionally, we will show in Section 5 that if A ∈ 𝒮, then the function exp(A)(a, b) = A(a, b)+1 defined for a < b are in A is equivalent to signature of some standard generating set.

Observe that the ordinals below ε_{0} can all be generated from {0, 1} via the operations + and ζ ↦ ω^{−1+ζ}. Moreover a slight modification of the Cantor normal form specifies, for each ξ < ε_{0}, a unique term in these operations which generates ξ. Let R_{ξ} ∈ 𝒮 denote the result of evaluating the same term but in the structure (𝒮 , 0, Z, +, exp) in place of (ε_{0}, 0, 1, +, ζ ↦ ω^{−1+ζ}).

Definition 2.7. The family ℛ of reduced signatures is the collection {R_{ξ} | ξ < ε_{0}}.

The groups G_{ξ} from Theorem 1 are given by G_{ξ} := ⟨R_{ξ}⟩. To summarize, we will eventually prove Theorems 1 and 3, showing that:

• every S-generated group is biembeddable with some G_{ξ};

• G_{ξ} embeds into G_{η} if and only if ξ < η < ε_{0};

• if ξ = ω^{ω^{α}·2^{n}} for 0 < α < ε_{0} and 0 < n < ω, then the EA-class of G_{ξ} is

ω · α + n + 2. In fact we can take the analogy with ordinal arithmetic further. If A, B, C ∈ S

we define A = B ∗ C to mean:

• C = A ∪ B and a < b for all a ∈ A and b ∈ B, and

• o(a, b) = 1 for all a ∈ A and b ∈ B.

The ternary relation A = B∗C on S allows us to define an operation ∗ at the level of signatures as in the case of +. We show in Section 7 that if A = B ∗C for nonempty B, C and o(f, g) > 0 for all f < g in A, then ⟨A⟩ ≅ ⟨B⟩ ≀ ⟨C⟩. We caution that ≀ is a permutation wreath product and typically not the standard wreath product — see Section 3.5 for further details, including a precise definition of which permutation wreath product is being used here. Also, it can be shown that if 1 < β ≤ α < ε_{0} are indecomposable ordinals, then R_{α·β} ≡ R_{α} ∗R_{β} with equality holding if R_{α} ∗R_{β} ∈ ℛ.

Finally, if A ∈ 𝒮, define E(A) = exp(exp((A)). Unlike exp, E also comes from a natural binary relation on standard generating sets: if A, B ∈ S then A = E(B) asserts that o(f, g) ≥ 2 for all f < g ∈ A and B = {f^{∘} | f ∈ A}. The operations +, ∗, and E generate ℛ in the following strong sense.

Proposition 2.8. if A ∈ ℛ, then exactly one of the following hold:

• A = E(B) for some B ∈ ℛ;

• there are B, C ≠ 0 in ℛ such that A = B+C, in which case ⟨A⟩ = ⟨B⟩+⟨C⟩;

• there are B, C ≠ 0 in ℛ such that A = B ∗ C, in which case ⟨A⟩ is the

permutation wreath product ⟨B⟩ ≀ ⟨C⟩ In particular, each A ≠ 0 in ℛ can be uniquely expressed as a term in the operations +, ∗, and E and the constant Z so that E(Z) does not occur as a subterm.

For instance, the example in Figure 2 is E(Z ∗ Z + Z + Z).

3. Intermission

3.1. Background and conventions. We adopt the convention that the natural numbers include 0 and in particular all counting starts at 0. We use Z to denote the set of integers. Unless otherwise stated, i, j, k, l, m, n range over the natural numbers and p, q, r range over the integers. For instance we write i < n to mean that i is a natural number less than n.

If G and H are two groups, we use G+H to denote their direct sum. Even though we work primarily with nonabelian groups, this additive notation and terminology fits better with the correspondence we develop between 𝔖 and the ordinals below ε_{0}.

Given f, g ∈ Homeo_{+}(I), we denote by f^{g} the conjugate g^{−1}fg and remark that under this notation supt(f^{g}) = supt(f)g. Given X ⊂ I we write Xf for {xf | x ∈ X} .

In this paper we think of F as being a subgroup of PL_{+}(I), although there typically is not a need to fix a specific model. Representing F in PL_{+}(I) gives us access to results about subgroups of PL_{+}(I) (specifically results about centralizers). This representation also guarantees that any element f of F has only finitely many components of its support and hence is a product of the bumps of f.

3.2. Fast generating sets. We now give more details to some of the claims in Section 2.2 and more information from [3]. If S ⊂ Homeo_{+}(I) is a fast set of marked functions, then the dynamical diagram of S is the edge labeled, ordered, directed graph D_{S} defined as follows:

• the vertices of D_{S} are the feet of S with the order induced from I;

• the directed edges of D_{S} are the bumps a which occur in S with the endpoints of a being the feet of a;

• positive bumps are directed to the right and negative bumps are directed to the left;

• the label of a directed edge a in D_{S} is the unique f ∈ S for which a is a

bump of f. Note that such ordered directed graphs do not have multiple edges. We sometimes refer to the constituents of a dynamical diagram — the vertices, the directed edges, the labels — in terms of the objects they are intended to represent — the feet, the bumps, the functions in S.

For two fast sets of marked functions S_{0} and S_{1}, an isomorphism from D_{S_{0}} to D_{S_{1}} is an isomorphism θ : D_{S_{0}} → D_{S_{1}} of ordered directed graphs such that for bumps a and b which occur in S_{0}, the labels of a and b are equal if and only if the labels of θ(a) and θ(b) are equal. Note that the choice of marking affects the dynamical diagram but not its isomorphism type. Also observe that the isomorphism θ induces a well defined order preserving bijection from S_{0} to S_{1}. Lastly, there is at most one isomorphism between any two dynamical diagrams.

If A is a totally ordered finite subset of a group, then the pair (⟨A⟩, A) is a marked group that is marked by A. A marked isomorphism θ : (⟨A⟩, A) → (⟨B⟩, B) between marked groups is an isomorphism from ⟨A⟩ to ⟨B⟩ that restricts to an order preserving bijection from A to B. The next theorem asserts that the dynamical diagram determines the marked isomorphism type of ⟨S⟩ whenever S ⊂ Homeo_{+}(I) is a fast set of marked functions. (The two uses of “marked” in the previous sentence are not the same.)

Theorem 6. [3] If S_{0} and S_{1} are fast sets of marked functions in Homeo_{+}(I), and the dynamical diagrams of S_{0} and S_{1} are isomorphic, then the order preserving bijection from S_{0} to S_{1} extends to an isomorphism ⟨S_{0}⟩ ≅ ⟨S_{1}⟩.

We also need the following proposition which is closely related to the results of [3].

Proposition 3.1. Suppose that A is a finite geometrically fast set of bumps and X ⊂ I intersects each orbital of A. If g ∈ ⟨A⟩ is not the identity, then there is an x ∈ X⟨A⟩ such that xg ≠ x.

Proof. Observe that the closure of X⟨A⟩ contains the transition points of A. The proof of Proposition 4.3 of [3] yields a marking of A which witnesses that it is geometrically fast and has the property that every marker is in the closure of X⟨A⟩; let M denote the set of these markers. From [3], if g ∈ ⟨A⟩ is not the identity, then there is a t ∈ M⟨A⟩ ⊂ \overline{X⟨A⟩} such that tg ≠ t. Continuity of g implies that there is an x ∈ X⟨A⟩ such that xg ≠ x. □

It is convenient to develop some conventions for drawing dynamical diagrams. First, we arrange the vertices horizontally from left to right in increasing order. We draw right directed edges as over-arcs and left directed edges as underarcs, suppressing the arrows. If f is a generator and a right foot J of f is immediately followed by a left foot J′ of f, then the pair of vertices {J, J′} is contracted to a single vertex when drawing the diagram. This has the effect of simplifying the dynamical diagram visually. It also has the feature that if f ∈ S has connected extended support, then the edges with label f form a connected component of the contracted diagram. Thus it is sufficient to label only one bump of each such component.

This graphical representation of D_{S} can be derived from the graphs of the elements of S drawn as in Section 2.1. The drawing

g_{4} .................^{.................}^{.................} f_{4}

is the graph of {f_{4}, g_{4}} from Figure 1 as drawn in Section 2.1 and it is also a drawing of the dynamical diagram for {f_{4}, g_{4}}. In general, the dynamical diagram of a fast set of standard functions S is a sketch of the graphs of the functions in S.

Suppose that S ⊂ Homeo_{+}(I) is a finite fast set of marked functions with connected essential supports. A bump b of S is isolated in S if its support contains no transition points of S. If E is a set of isolated bumps of S and for each f ∈ S there is a bump of f which is not in E, then we say that E is an extraneous set of bumps of S. We need a result of [3] which says that extraneous sets of bumps can be excised without affecting the marked isomorphism type of S. This is made precise as follows. For g ∈ Homeo_{+}(I) and E a set of bumps (not necessarily bumps of g), we define g/E ∈ Homeo_{+}(I) to be the function which agrees with g on

I \ ⋃{supt(b) | b ∈ E and b is a bump of g}

and is the identity elsewhere. We extend the definition above to a set S ⊂ Homeo_{+}(I) by:

S/E := {g/E | g ∈ S}.

The next theorem is a special case of Theorem 9.1 of [3].

Theorem 7. [3] If S ⊂ Homeo_{+}(I) is a fast set of marked functions and E is an extraneous set of bumps of S, then the map g ↦ g/E extends to a isomorphism from ⟨S⟩ to ⟨S/E⟩.

3.3. Ordinals and their arithmetic. Recall that an ordinal is the isomorphism type of a well-ordered set. If α and β are ordinals, then α < β is defined to mean that there is well-order of type α which is a proper initial part of a well-ordering of type β. For any two ordinals α and β, precisely one of the following is true: α < β, β < α, or α = β. We adopt von Neumann’s convention that an ordinal is the set of its predecessors and that α < β means α ∈ β. The least ordinal is 0 := ∅ and the least infinite ordinal is ω, which can be thought of as coinciding with the natural numbers. If A is a set of ordinals, then there is always a least ordinal sup(A) := ⋃ A which is an upper bound for A. If α is an ordinal, then α + 1 := α ∪ {α} is the least ordinal greater than α. Ordinals of the form α + 1 are said to be successor ordinals; all other nonzero ordinals are said to be limit ordinals.

It is possible to extend the usual arithmetic operations on the finite ordinals to all ordinals as follows:

α + β := \begin{cases}α & if β = 0 \\ (α + γ) + 1 & if β = γ + 1 \\ sup_{γ<β}(α + γ) & if β is limit \end{cases}

α · β := \begin{cases}0 & if β = 0 \\ (α · γ) + α & if β = γ + 1 \\ sup_{γ<β}(α · γ) & if β is limit \end{cases}

α^{β} := \begin{cases}1 & if β = 0 \\ (α^{β}) · α & if β = γ + 1 \\ sup_{γ<β}(α^{γ}) & if β is limit \end{cases}

The reader is cautioned that while + and · are associative, neither + nor · are commutative. For instance:

2 · ω = sup_{n∈ω} (2 · n) = ω < ω · 2 = sup_{n∈ω} (ω + n) = ω + ω.

Further, ordinal addition is not right cancellative, but is left cancellative: α + β = α + γ implies β = γ. We adopt the standard binding conventions from ordinary arithmetic (e.g. α ·β +γ = (α ·β)+γ) and associate exponentiation to the right (as one does in ordinary arithmetic): α^{β^{γ}} = α^{(β^{γ})}, which typically does not coincide with (α^{β})^{γ} = α^{β·γ}.

The ordinal ε_{0} is the least ordinal solution to ω^{x} = x. It also has the property that if α, β < ε_{0}, then α + β, α · β, and α^{β} are all less than ε_{0}. Further details on ordinal arithmetic can be found in article II of [9].

3.4. Elementary amenable groups. Consider the smallest class EG containing the finite and abelian groups and closed under the following operations:

(1) taking an extension of one group by another group;

(2) taking a directed union of a set of groups;

(3) taking a subgroup of a group;

(4) taking a quotient of a group by a normal subgroup; This class of groups was first considered by Day [11, P. 520] under the name elementary groups; it is more common in the current literature to refer to them as the elementary amenable groups. This class was later studied by Chou [10] who worked out much of the basic theory and showed that the operations of extension and directed union are all that are needed to generate EG. Chou stratified EG by subclasses EG_{α} with α from the ordinals by setting:

• EG_{0} to be the class of all abelian and finite groups;

• EG_{α+1} to be those groups obtainable from groups in EG_{α} by a single application of operation (1) or (2) above;

• EG_{α} := ⋃_{β<α} EG_{β} if α is a limit ordinal. It is proven in [10] that each EG_{α} is closed under taking subgroups and quotients and that every element of EG is in EG_{α} for some ordinal α.

For G ∈ EG, it has become customary to define the elementary amenability class EA(G) of G as the smallest α for which G ∈ EG_{α}. It follows from the definitions that for every limit α there is no G ∈ EG with EA(G) = α, and there is no finitely

A Y ⊇ supt(G) X Xg_{1} Xg_{2} ⋯  Y h_{1}  Y h_{2}  ⋯

Figure 3. An illustration of the sets in Lemma 3.2

generated G ∈ EG with EA(G) = α + 1. From Chou’s result that the EG_{α} are closed under taking subgroups and quotients, it follows that for G and H in EG, if G is either a subgroup or a quotient of H, then EA(G) ≤ EA(H).

3.5. Wreath products. Given a group of permutations G of X and a group of permutations H of Y, then the 1937 article [21] defines G ≀ H, the wreath product of G and H, as a group of permutations of X × Y. Since the 1964 paper [19], the standard wreath product obtained from G and H by regarding H as permuting itself by (e.g.) right multiplication has become standard and “wreath product” often means “standard wreath product”; “permutation wreath product” has been used for the older notion. Our focus is primarily on permutation wreath products in this article and we proceed with the definition.

Given pairs (G, X) and (H, Y) where G is a group acting on X and H is a group acting on Y, then we write G ≀ H, the permutation wreath product of G and H as shorthand for the pair (G ≀ H, X × Y) where the group and the action have to be defined. We regard G^{Y}, the set of functions from Y to G, as a group by multiplying pointwise. With 1 the identity of G and for ϕ ∈ G^{Y}, we use supt(ϕ) to denote {y ∈ Y | ϕ(y) ≠ 1}, the support of ϕ. We use ∑_{Y} G to denote the direct sum of copies of G indexed over Y which can be viewed concretely as the group of finitely supported elements of G^{Y}.

The group H also acts on ∑_{Y} G on the right by ϕ^{h}(y) = ϕ(yh^{−1}). We use this action to form the semidirect product ∑_{Y} G ⋊ H on the set (∑_{Y} G) × H with multiplication (ϕ, h)(θ, j) = (ϕθ^{h^{−1}}, hj). This semidirect product is the wreath product of G and H and is denoted G ≀ H. The action of G ≀ H on X × Y is given by (x, y)(ϕ, h) = (xϕ(y), yh).

In our setting, wreath products arise as in the next lemma. A proof is given in the proof of [5, Proposition 2.5]. The following definitions make the lemma easier to state. Let H be a group acting on a set A, let Y be a subset of A, and let Y = {Y h | h ∈ H}; note that H also acts on Y. We say that the action of H on Y is consistent to mean that for all h ∈ H if Y h ∩ Y ≠ ∅, then h fixes Y pointwise. We say that the action of H on Y is faithful to mean that the only element of H that fixes all elements of Y is the identity of H. The lemma is now stated as follows (see Figure 3):

Lemma 3.2. Suppose that G and H act on a set A on the right. Assume there are sets X ⊂ supt(G) ⊂ Y ⊂ A such that the action of G on X = {Xg | g ∈ G} and the action of H on Y = {Y h | h ∈ H} are both consistent and faithful. Then the action of W = ⟨G, H⟩ on W = {Xw | w ∈ W } is also consistent and faithful and is isomorphic to the action of the permutation wreath product G ≀ H on X × Y.

We now detail how the EA-classes of groups interact with certain permutation wreath products. For convenience, we let ΣG denote the direct sum of countably many copies of the group G. It is clear that EA(ΣG) ≥ EA(G). It is a straightforward inductive exercise to show that for all G, we have EA(G + G) = EA(G). It follows that EA(ΣG) ≤ EA(G) + 1. In the special case that EA(ΣG) = EA(G), we say that G has property Σ. Notice, for instance, that every abelian group has Σ and that the groups with Σ are closed under the elementary operations (1)–(2). The family of groups 𝔖 which we construct all satisfy Σ.

The next proposition, mostly proven in [5], is very fruitful in calculating and estimating the EA-classes of the groups we consider later in the article.

Proposition 3.3. For an infinite, finitely generated group G ∈ EG acting faithfully on an infinite set Y, we have

EA(G) + 1 ≤ EA(G ≀ G) ≤ EA(G) + 2.

Further, if EA(ΣG) = EA(G), then EA(G ≀ G) = EA(G) + 1.

4. The oscillation function

In this section, we establish some further facts about the oscillation function first introduced in Section 2.4. If A is a fast set of marked functions, then we say that an orbital is active with respect to A if it contains a transition point of an element of A. Notice that an orbital J is active with respect to A if and only if it contains a foot of A other than those of J. Recall that if f < g are marked functions, then o(f, g) is the number of orbitals of g which are active with respect to {f, g}. By convention o(f, g) is a symmetric function — o(g, f) := o(f, g).

If f is a standard function with at least one negative bump, we will call the unique common transition point of a positive bump and negative bump of f the expansion point of f. The following is a sketch of a standard function where we have highlighted the expansion point with a bullet:

f  •

The next two lemmas provide a number of useful characterizations of the oscillation function. We omit the routine proofs.

Lemma 4.1. Let f and g be standard functions so that {f, g} is fast with f ⊏ g. Then the following hold:

(1) The pair (f, g) is standard and o(f, g) = 1 if and only if the support of f is contained in the rightmost orbital of g.

(2) The pair (f, g) is standard and o(f, g) = 2 if and only if g has an expansion point, and for the rightmost orbital (a, b) of f, the endpoint a is contained in the leftmost orbital of g and the endpoint b is contained in the rightmost orbital of g.

(3) If the pair (f, g) is standard and o(f, g) > 2, then f has an expansion point, and the leftmost orbital of g and the rightmost orbital of g each contain exactly one transition point of f and neither contains the expansion point of f.

Lemma 4.2. If f ⊏ g is a fast pair of standard functions, then the following are true:

(1) o(f, g) is one greater than the number of active orbitals of f with respect to {f, g};

(2) if (f, g) is a standard pair, then o(f, g) = o(g^{∘}, f) + 1;

(3) if n is the cardinality of the smallest cover of the feet of {f, g} by disjoint intervals each of which intersects the feet of at most one of f or g, then o(f, g) = (n − 1)/2;

Many arguments about S are inductive and take advantage of the recursive nature of the definition of a standard pair. Note that if (f, g) is standard and o(f, g) > 1, then f ⊏ f^{g}. Also observe that even without an assumption that f ⊏ g, we have o(f, g) = o(f^{p}, g^{q}) for any nonzero p, q ∈ Z and that for every homeomorphism h, o(f^{h}, g^{h}) = o(f, g). The next lemma is useful in calculating values of the oscillation function in subsequent sections.

Lemma 4.3. If f ⊏ h and g ⊏ h are marked functions in Homeo_{+}(I) with {f, g, h} fast (possibly f = g), then

o(f, g^{h}) ≤ min (o(f, h), o(g, h)).

Moreover if (f, h) and (g, h) are standard pairs, then f < g^{h} and

o(f, g^{h}) ≤ min (o(f, h), o(g, h) − 1).

Proof. Observe that since the feet of g and h are disjoint, every foot of g^{h} is contained in a foot of h. By (3) of Lemma 4.2, o(f, g^{h}) ≤ o(f, h). Furthermore, we have o(f, g^{h}) = o(f^{h^{−1}}, g) ≤ o(g, h^{−1}) = o(g, h).

Assume that (f, h) and (g, h) are standard pairs. Since g ⊏ h, we have o(g, h) ≥ 1. If o(g, h) = 1, then Lemma 4.1 and the assumption that {g, h} is fast implies that support of g^{h} is contained in the rightmost foot of h which is to the right of the support of f. Thus f ≪ g^{h} and o(f, g^{h}) = 0 ≤ min (o(f, h), o(g, h) − 1).

Now assume that o(g, h) > 1. Let J be the union of the feet of h other than the leftmost and rightmost feet of h. Notice that since o(g, h) > 1, J is nonempty. The feet of f^{h^{−1}} are contained in J which in turn is contained in the support of g since o(g, h) > 1. Thus f^{h^{−1}} ⊏ g and all the feet, and thus all the transition points, of f^{h^{−1}} are contained in the orbitals of g that are active with respect to {h^{∘}, g}. By (1) of Lemma 4.2, the number of these orbitals is o(h^{∘}, g) = o(g, h) − 1, and so o(f, g^{h}) = o(f^{h^{−1}}, g) ≤ o(g, h) − 1. □

For the following, recall that if A is in S, then A is linearly ordered by <. If |A| = n, we let a_{0} < a_{1} < ⋯ < a_{n−1} be the elements of A. We also use a_{max} to denote the greatest element of A.

Recall that if A ∈ S, then we write A = B +C if A = B ∪C, and b ≪ c whenever b ∈ B and c ∈ C.

Definition 4.4. If there are no nonempty B and C where A = B + C, then we say that A is indecomposable.

Many proofs that follow argue the decomposable and indecomposable cases separately. The next lemma gives a useful characterization of when an element of S is decomposable.

Lemma 4.5. An A ∈ S is decomposable if and only if there is an i < |A| − 1 such that o(a_{i}, a_{max}) = 0.

Proof. We begin by observing that b ≪ c is equivalent to b < c and o(b, c) = 0. The forward implication in the lemma follows immediately from this equivalence. To see the reverse implication, let j < |A| − 1 be maximal such that o(a_{j}, a_{max}) = 0. Observe that every element of the support of a_{j} is less than every element of the support of a_{max}. If i < j, then sup supt(a_{i}) < sup supt(a_{j}) and consequently o(a_{i}, a_{max}) = 0. We claim that if i ≤ j < k < |A| − 1, then o(a_{i}, a_{k}) = 0. Since o(a_{k}, a_{max}) > 0, it follows that the extended support of a_{k} is contained in the extended support of a_{max}. Since sup supt(a_{i}) < inf supt(a_{max}), it follows that sup supt(a_{i}) < inf supt(a_{k}) and hence that o(a_{i}, a_{k}) = 0. By the equivalence noted at the start of the proof, we therefore have that if i ≤ j < k < |A|, then a_{i} ≪ a_{k}. If we take B = {a_{i} | i ≤ j} and C = {a_{k} | j < k < |A|}, then we’ve shown that A = B + C. □

The following operation is useful in analyzing S.

Definition 4.6. If A ∈ S, the rotation of A is defined by A^{∘} := A∪{a_{max}^{∘}}\{a_{max}} if there is an i < |A| − 1 such that o(a_{i}, a_{max}) > 0; otherwise set A^{∘} := A \ {a_{max}}.

Notice that it follows immediately from the definition of standard pair that A^{∘} is again in S.

Lemma 4.7. If A ∈ S, then the following are true:

(1) if A = B + C and C ≠ ∅, then A^{∘} = B + (C^{∘}).

(2) If A is indecomposable, then the least element of A^{∘} is a_{max}^{∘}.

Proof. To see (1), observe first that a_{max} = c_{max}. It remains to show that for all i < |B|, b_{i} < c_{max}^{∘}. Because A = B + C, we have that for all i < |B|, b_{i} ≪ c_{max}. Since the support of c_{max}^{∘} is contained in the support of c_{max}, it follows that b_{i} ≪ c_{max}^{∘} for every i < |B|. To see (2), observe that o(a_{0}, a_{max}) > 0 by Lemma 4.5. Thus (a_{max}^{∘}, a_{0}) is standard and hence a_{max}^{∘} < a_{0}. □

The following lemma gives a useful criteria for membership to S.

Lemma 4.8. If A is a fast set of standard functions which is totally ordered by <, then A is in S provided that the following conditions are satisfied:

• A^{∘} is in S;
• for all i < |A| − 1 if a_{i} ⊏ a_{max}, then a_{max}^{∘} < a_{i}.

Proof. Let A ∈ S be given as in the statement of the lemma. If |A| ≤ 1 there is nothing to show, so assume that |A| > 1. Observe that A \ {a_{max}} ⊆ A^{∘} is in S by assumption and therefore in order to verify A ∈ S, we need only to show that (a_{i}, a_{max}) is standard whenever i < |A| − 1. Let j < |A| − 1 be minimal such that o(a_{j}, a_{max}) > 0. Since the support of a_{max}^{∘} is contained in the support of a_{max}, a_{i} ≪ a_{max} whenever i < j. If j ≤ i, then a_{max}^{∘} < a_{i} by hypothesis. Furthermore, (a_{max}^{∘}, a_{i}) is standard since A^{∘} is assumed to be in S. Since o(a_{i}, a_{max}) > 0 and thus a_{i} ⊏ a_{max}, it follows that (a_{i}, a_{max}) is standard as desired. □

5. Signatures

In this section we expand on the notion of signature as defined in Section 2.4 and prove several properties. We show that the signature A of an A ∈ S completely encodes the marked isomorphism type of ⟨A⟩. Moreover, we give a simple description of the family of all signatures.

Before proving the main results, it will be helpful to define some terminology and prove some lemmas.

Definition 5.1. If A ∈ S, the complexity of A is the pair

(|A|, ∑_{i<j} o(a_{i}, a_{j})).

The set of all complexities is ordered lexicographically.

Observe that if A ∈ S, then A^{∘} has strictly smaller complexity than A. In what follows, it is frequently useful to prove statements about the elements of S by induction on their complexity. Theorem 7 allows us to remove extraneous bumps without changing the isomorphism type of the group which is generated. However if A ∈ S has extraneous bumps, Theorem 7 does not ensure the modified generating set remains in S. The next two lemmas address this.

Lemma 5.2. If A ∈ S has an extraneous bump, then there is a nonempty set E of extraneous bumps of A such that A/E has the same dynamical diagram as a member of S.

Proof. This is proved by induction on the complexity of A. First suppose that A = {f}. Recall that f has at least 2 bumps, and has either the same number of positive and negative bumps or one more positive bump. If f has more positive bumps than negative bumps, then let b be the rightmost bump of f and observe that f/{b} is still a standard function. Similarly, if f has the same number of positive an negative bumps and b is the leftmost bump of f, then f/{b} is a standard function. In both cases A/{b} is in S. If A = B + C for B, C ≠ ∅, then either B or C has an extraneous bump and we are finished by our induction hypothesis.

Suppose that |A| > 1 is indecomposable with an extraneous bump. If o(a_{i}, a_{max}) = 1 for all i < |A| − 1, then the support of every a_{i} < a_{max} is in the rightmost bump of a_{max}. If the number of bumps of a_{max} is at least 2, we let E consist of all bumps of a_{max} but the rightmost. If a_{max} has only one bump, then there is a bump extraneous in A′ = A \ {a_{max}}. By induction there is an E consisting of extraneous bumps of A′ with such that A′/E has the same dynamical diagram as an element of S. Notice that that every element of E is also extraneous in A and A/E = (A′/E) ∪ {a_{max}} has the same dynamical diagram as an element of S.

If there is an i < |A| − 1 with o(a_{i}, a_{max}) > 1, then both of the outer orbitals of a_{max} are active. Thus A^{∘} has an extraneous bump and we can apply our induction hypothesis to find a nonempty set of extraneous bumps E of A^{∘} such that A^{∘}/E has the same dynamical diagram as a member of S. Observe that every element of E is also a bump of A: the only situation in which a bump of A^{∘} is not a bump of A occurs when a_{max} has at most two bumps and in this case a_{max}^{∘} is isolated and hence not extraneous. Finally, it is easily checked that A/E has the same dynamical diagram as a member of S. □

Lemma 5.3. If A is an element of S, then there is an A′ ∈ S such that:

(1) ⟨A′⟩ is marked isomorphic to ⟨A⟩;

(2) A′ and A have the same signature;

(3) A′ has no extraneous bumps.

Proof. Observe that extraneous bumps are not counted by signatures. In particular, if E is a set of extraneous bumps of A ∈ S, then the signature of A/E coincides with the signature of A. The proof of the lemma is now by induction on the number of extraneous bumps of A, using Lemma 5.2 and Theorems 6 and 7. □

Lemma 5.4. If A ∈ S and no bump of A is extraneous, then no bump of A^{∘} is extraneous.

Proof. First suppose that a_{max} has at most two orbitals. Notice that since a_{max}^{∘} has only one orbital, its only bump is not extraneous. If a_{max} has one orbital, none of its transition points are in an orbital of another element of A and hence a_{max} plays no role in witnessing that other elements of A are not extraneous. If a_{max} has two orbitals, then the only transition point which it has to witness that another element of A is not extraneous is its middle transition point, which remains a transition point of a_{max}^{∘}. This completes the proof under the assumption that a_{max} has at most two orbitals.

Now suppose that a_{max} more than two orbitals. If b is an orbital of A^{∘}, it is an orbital of A and is not extraneous in A. So b contains a transition point t of some a_{i} ∈ A. The only transition points of A that are not transition points of A^{∘} are the rightmost and leftmost transition points of a_{max}. But these are in no orbital of A and so t is neither of these points. So t is a transition point of A^{∘} and b is not extraneous in A^{∘}. □

We now are ready to prove Theorem 2 which asserts that if A and B are elements of S which have the same signature, then the order preserving bijection between A and B extends to an isomorphism ⟨A⟩ ≅ ⟨B⟩.

Proof of Theorem 2. The proof is by induction on the complexity of the common signature of A and B; let n denote |A| = |B|. By Lemma 5.3, we may assume that A and B have no extraneous bumps. By Theorem 6 it suffices to show that A and B have isomorphic dynamical diagrams.

If A = A′ + A′′ for some nonempty A′ and A′′, then B = B′ + B′′ for some B′ and B′′ having the same signatures as A′ and A′′ respectively. Notice that every orbital of A′ is active (in A′) and similarly for A′′, B′, and B′′. Thus we can apply our induction hypothesis to conclude that the dynamical diagrams of A′ and B′ are isomorphic and similarly for A′′ and B′′. Since the dynamical diagram of A is obtained by putting the diagram for A′ to the left of the diagram for A′′ — and similarly for B — we have that the dynamical diagrams of A and B are isomorphic.

Now suppose that neither A nor B decompose as a sum. By Lemma 4.5, this means that o(a_{i}, a_{max}) = o(b_{i}, b_{max}) > 0 for all i < n − 1. If a_{max} has a single orbital, then a_{max} is a positive bump, and o(b_{i}, b_{max}) = o(a_{i}, a_{max}) = 1 for all i < n − 1. Notice that the definition of standard pair implies that if i < n − 1, then the support of b_{i} is contained in the rightmost orbital of b_{max}. Since no bump of b_{max} is extraneous, this must mean that b_{max} has only one orbital and must be a positive bump. By our induction hypothesis, A \ {a_{max}} and B \ {b_{max}} have isomorphic dynamical diagrams; let D denote the common isomorphism type. Notice that the dynamical diagram for A and for B are both obtained by a pair of new vertices to D — one to the far left and one to the far right — as well as a right directed edge between these new vertices. This new edge is given a label distinct from the other labels. Hence A and B have isomorphic dynamical diagrams.

Finally, we may now assume that both a_{max} and b_{max} have more than one orbital. Observe that A^{∘} and B^{∘} have the same signature and lower complexity than A and B: if i < n − 1, then

o(a_{max}^{∘}, a_{i}) = o(a_{i}, a_{max}) − 1 = o(b_{i}, b_{max}) − 1 = o(b_{max}^{∘}, b_{i}).

By Lemma 5.4, A^{∘} and B^{∘} have no extraneous bumps. By our induction hypothesis, A^{∘} and B^{∘} have dynamical diagrams which are isomorphic to some common D. Notice that since every orbital of a_{max} is active in A, (a_{max})^{∘} is an isolated bump in A^{∘} if and only if a_{max} has exactly two orbitals. Since the former equivalent condition is a property of the dynamical diagram of A, it follows that a_{max} has exactly two orbitals if and only if b_{max} has exactly two orbitals. It is now easily checked that in both cases, A and B must have isomorphic dynamical diagrams. □

We now turn to our characterization of the set of signatures. We start with the following proposition. The function ϱ defined in its proof models the effects on oscillation numbers when an indecomposable A ∈ S is replaced by A^{∘}.

Proposition 5.5. The following are equivalent for an ordered triple (p, q, r) of integers:

(1) r ≥ min(p − 1, q), with equality holding unless p = q;

(2) q ≥ min(p, r), with equality holding unless p = r + 1;

(3) p ≥ min(q, r + 1), with equality holding unless q = r;

(4) all of the following three inequalities hold:

p ≥ min(q, r + 1), q ≥ min(p, r), r ≥ min(p − 1, q).

Proof. We first show that (1) implies (2) and then argue that (2) and (3) are equivalent to (1) by symmetry. Let us assume that p, q, r ∈ Z with r ≥ min(p−1, q) and with equality holding unless p = q. If p > q then we have r = q so that p > q = r. Therefore q = min(p, r) and (2) holds. If p < q then we have r = p−1 < p < q so in particular p = r + 1 and q > min(p, r) = r and again (2) holds. Finally, if p = q then r ≥ p − 1 = q − 1 by assumption. We therefore have that min(p, r) ≤ p = q and again (2) holds.

Now consider the transformation ϱ : Z^{3} → Z^{3} defined by ϱ(p, q, r) = (r, p−1, q − 1). Observe that (p, q, r) satisfies (1) if and only if (p̄, q̄, r̄) := ϱ(p, q, r) satisfies (3): the assertion “r ≥ min(p − 1, q), with equality holding unless p = q” is the same as “p̄ ≥ min(q̄, r̄ + 1), with equality holding unless q̄ = r̄.” Similarly, (p, q, r) satisfies (2) if and only if ϱ(p, q, r) satisfies (1). Similarly, (p, q, r) satisfies (3) if and only if ϱ(p, q, r) satisfies (2). It follows that (1), (2), and (3) are equivalent.

Next observe that the equivalence of (1), (2), and (3) immediately yields that each implies (4). Lastly, we assume (4) and show that (1) holds. If p = q, then (1) just asserts r ≥ min(p − 1, q) and there is nothing to show. If p < q, then since p ≥ min(q, r + 1), it must be that q > r + 1 and hence p ≥ r + 1. Since r ≥ min(p − 1, q) = p − 1 we have r = p − 1 = min(p − 1, q). Similarly if q < p, then q ≥ min(p, r) implies that q ≥ r. Taken with r ≥ min(p − 1, q), this implies r = q = min(p − 1, q). □

Definition 5.6. (p, q, r) ∈ Z^{3} is an admissible triple if it satisfies any of the equivalent relationships stated in Proposition 5.5.

Proposition 5.5 and the equality min(a − 1, b − 1) = min(a, b) − 1 immediately yields the following corollary.

Corollary 5.7. For all (p, q, r) ∈ Z^{3} the following are equivalent:

(1) (p, q, r) is admissible.

(2) (q, r, p − 1) is admissible.

(3) (r, p − 1, q − 1) is admissible.

If A is a function from the pairs a < b of a finite linear order A into ω, then we say that A is admissible if whenever a < b < c are in A, the triple (A(b, c), A(a, c), A(a, b)) is admissible. Recall that each A is equivalent, under the equivalence defined in Section 2.4, to a map on pairs in which the base is {0, …, n − 1}.

Define 𝒮 to be the collection of all equivalence classes of such maps which are admissible. (Formally we view 𝒮 as a set by using the choice of canonical representatives from each equivalence class noted above.) We often write that a function on pairs is in 𝒮 when we really mean that its equivalence class is in 𝒮. Our next task is to prove that that 𝒮 is exactly the set of signatures of elements of S, up to the above notion of equivalence. Recall that 0 and Z denote the elements of 𝒮 with bases having cardinalities 0 and 1 respectively. Anticipating 𝒮 ’s relation to S, we will often confuse the distinction between an A ∈ 𝒮 and its base, writing things such as “the cardinality of A” or “the elements of A” when we are really referring to the cardinality or elements of the base of A.

The operation + defined in Section 2.5 is well defined on 𝒮. Unlike with S, + is a bona fide binary operation on 𝒮. Observe that if A = B + C, then A = B + C — the signature of a sum is the sum of the signatures.

The following property of elements of 𝒮 will be used often.

Lemma 5.8. Suppose A ∈ 𝒮. If i < j < k < |A| and A(j, k) = 0, then A(i, k) = 0.

Proof. If A(i, k) ≠ 0, then

A(i, j) = min(A(j, k) − 1, A(i, j)) = −1

which is not possible. □

Definition 5.9. An element A of 𝒮 is indecomposable if there do not exist B, C ≠ 0 such that A = B + C.

We need the following analog of Lemma 4.5.

Lemma 5.10. If A ∈ 𝒮 is indecomposable and i < n = |A| − 1, then A(i, n) > 0.

Proof. We prove the contrapositive. Let j be maximal such that A(j, n) = 0. By Lemma 5.8, A(i, n) = 0 for all i < j. If i < j < k ≤ n, we have A(i, n) = 0 < A(k, n) so

A(i, k) = min(A(j, k) − 1, A(i, n)) = 0.

Thus setting B := {0, …, j} and C := {j + 1, …, n} we have A = B + C. □

We now define the analog of the rotation operation on 𝒮. Just as in the case of S, we define the complexity of an element A ∈ 𝒮 to be the pair (|A|, ∑_{i<j} A(i, j)). Set 0^{∘} = 0 and Z^{∘} = 0. If A = B + C for B, C ≠ 0 and C^{∘} has been defined, then we set A^{∘} := B + (C^{∘}). If A ∈ 𝒮 is indecomposable and has {0, …, n} as its base for some n > 0, define n^{∘} := −1 and A^{∘} := {n^{∘}, 0, …, n − 1} = {−1, 0, …, n − 1}. For n^{∘} < i < n, set A^{∘}(n^{∘}, i) = A(i, n) − 1; if n^{∘} < i < j < n, set A^{∘}(i, j) = A(i, j). By Lemma 5.10, the values taken by A^{∘} are nonnegative. In order to verify that A^{∘} is in 𝒮, it suffices to show that if n^{∘} < i < j < n, then

A^{∘}(n^{∘}, i) ≥ min (A^{∘}(i, j) − 1, A^{∘}(n^{∘}, j))

with equality holding unless A^{∘}(i, j) = A^{∘}(n^{∘}, j). But this is equivalent to A(i, n) ≥ min (A(i, j), A(j, n)) with equality unless A(i, j) = A(j, n) − 1. Since this is true by the equivalence of (1) and (2) in Proposition 5.5, we have that A^{∘} is in 𝒮. Observe that if A ≠ 0, then the complexity of A^{∘} is strictly less than that of A. Also notice that the map A ↦ A^{∘} is one-to-one on the indecomposable elements of 𝒮.

Theorem 8. 𝒮 is the set of signatures of elements of S. Moreover, if A ∈ S, then the signature of the rotation of A is the rotation of the signature of A.

Proof. First we prove that every signature of an element A of S is admissible and hence is in 𝒮. The proof is by induction on the complexity of A. If |A| ≤ 2, there is nothing to show, so suppose that |A| ≥ 3. Also, if A = B + C for nonempty B, C ∈ S, then B and C are in 𝒮 by our induction hypothesis and since A = B + C, A ∈ 𝒮 by the closure of 𝒮 under sums.

Now suppose that A is indecomposable. Then A^{∘} is in S and by Lemma 4.7, a_{max}^{∘} < a_{i} for all i < |A|. Since it has lower complexity than A, A^{∘} is subject to the induction hypothesis and hence its signature is in 𝒮. It suffices to show that if i < j < k = |A| − 1, then (o(a_{j}, a_{k}), o(a_{i}, a_{k}), o(a_{i}, a_{j})) is admissible. By our inductive assumption we know that

(o(a_{i}, a_{j}), o(a_{k}^{∘}, a_{j}), o(a_{k}^{∘}, a_{i}))

is admissible and thus

(o(a_{i}, a_{j}), o(a_{j}, a_{k}) − 1, o(a_{i}, a_{k}) − 1)

is admissible. By Corollary 5.7, this is equivalent to

(o(a_{j}, a_{k}), o(a_{i}, a_{k}), o(a_{i}, a_{j}))

being admissible. This completes the proof that signatures of elements of S are in 𝒮.

Suppose now that A is in 𝒮; we need to prove that there is an A ∈ S whose signature is A. This is proved by induction on the complexity of A. We may assume A has base {0, …, n}. If n = 0, there is nothing to show. Also, if A = B + C, then let B and C be elements of S which have B and C as their respective signatures. By scaling and translating if necessary, we may assume that the elements of B are supported on (0, 1/2) and the elements of C are supported on (1/2, 1). It is now easy to check that every pair from A = B + C = B ∪ C is standard and thus A is in S and has A = B + C as its signature.

Now suppose that n > 0 and A is indecomposable. By Lemma 5.10, A(i, n) > 0 for all i < n. Since the complexity of A^{∘} is less than that of A, our induction hypothesis implies that A^{∘} is the signature of some ordered sequence a_{n^{∘}}, a_{0}, …, a_{n−1} comprising an element of S. Without loss of generality, we may assume that the supports of each of these functions is contained in (1/3, 2/3) and that moreover the greatest and least transition points of a_{n^{∘}} are not in the closures of the feet of the a_{i}’s. Let a_{n} be a standard function with extended support (0, 1) such that a_{n}^{∘} = a_{n^{∘}} and whose feet are disjoint from those of a_{i} for all i < n. It follows that (a_{i}, a_{n}) is standard for all i < n. Since the signature of A is A, we are finished with the proof of the first conclusion of the theorem. That the signature and rotation maps commute follows from their definitions and Lemmas 4.2 and 4.7. □

6. The inflation operation

In this section we introduce a fundamental operation on S and establish how it influences signatures. This operation plays a central role in subsequent sections. Let us begin with the observation that if A ∈ S, then

N := ⟨(a_{i})^{a_{max}^{p}} | i < |A| − 1 and p ∈ Z⟩

is a normal subgroup of ⟨A⟩, and ⟨A⟩ is an extension of N by Z. If we define, for each k,

A_{k} := {(a_{i})^{a_{max}^{p}} | i < |A| − 1 and |p| ≤ k},

then A_{k} is fast and N = ⋃⟨A_{k}⟩. Each A_{k} has the same dynamical diagram as

B_{k} := {(a_{i})^{a_{max}^{p}} | i < |A| − 1 and 0 ≤ p ≤ 2k}.

The need to understand the relationships between the groups ⟨A⟩, N, and the ⟨A_{k}⟩ motivates a family of primitive transformations which we term inflations.

Definition 6.1. If A is in S and a ∈ A, then the inflation of A by a is the set

A^{_{⇁} a}:= A ∪ {a^{2}} ∪ {b^{a} | b ∈ A and b < a} \ {a}.

Observe if a = a_{max}, then by iterating this procedure we obtain supersets of the B_{k}. Note that clearly ⟨A^{_{⇁} a}⟩ ⊆ ⟨A⟩ and since A is fast, ⟨A⟩ embeds into ⟨A^{_{⇁} a}⟩; see the end of the proof of Lemma 6.2 for details.

For A, B in S, we write A ≤ B if there is a sequence (B_{i} | i ≤ n) such that B_{0} = B, B_{n} has the same dynamical diagram as A, and such that if i < n, then B_{i+1} is contained in an inflation of B_{i}. Allowing n = 0 makes ≤ reflexive and ≤ is clearly transitive. Define an equivalence relation ≡ on S by A ≡ B if and only if A ≤ B ≤ A. A major aim of the rest of the paper is to show that the relation ≤ coincides with the embeddability relation on S and that moreover (S/≡ , ≤) is a well-order with order type ε_{0}.

Now we assign a marking to A^{_{⇁} a}. The functions in A^{_{⇁} a} ∩ A = A \ {a} maintain their markings. The markers of b^{a} are of the form sa where s is a marker of b. Finally, if s is a marker of a positive bump of a, then s is a marker of a^{2}; if s is a marker of a negative bump of a, then sa is a marker of a^{2}. This marking has the property that if t is in the support of a but not in one of its feet, then ta is not in a foot of a^{2}. In particular, A^{_{⇁} a} is fast. Notice that if A = B + C, then A^{_{⇁} b} = B^{_{⇁} b}+ C for all b ∈ B, and A^{_{⇁} c} = B + C^{_{⇁} c} for all c ∈ C.

Lemma 6.2. If A is in S and a ∈ A, then A^{_{⇁} a} is in S and ⟨A^{_{⇁} a}⟩ is biembeddable with ⟨A⟩.

Proof. The proof of that A^{_{⇁} a} is in S is by induction on the complexity of A. There is nothing to show if |A| ≤ 1. We have noted that if A ∈ S and a ∈ A, then A^{_{⇁} a} is fast. Furthermore, if b ∈ A, then {b^{a}, a^{2}} = {b^{a}, (a^{2})^{a}} is a standard pair. Also, by the previous observation we may assume that A is indecomposable.

If a < a_{max}, then observe that (A^{_{⇁} a})^{∘} ⊂ (A^{∘})^{_{⇁} a}. By our inductive hypothesis, (A^{∘})^{_{⇁} a} is in S and thus (A^{_{⇁} a})^{∘} is in S. From the definition of standard pairs and the indecomposability of A, we have that (a_{max}^{∘}, b) is standard for all b ∈ A \ {a_{max}}. We know j := o(b, a_{max}) > 0. If j = 1, then supt(b) is contained in the rightmost orbital of a_{max} which implies that supt(b^{a}) is contained in that same orbital. Thus a_{max}^{∘} ≪ b^{a}. If j > 1, then the extreme orbitals of a_{max} are active for both {a_{max}, b} and {a_{max}, b^{a}}, so a_{max}^{∘} ⊏ b^{a}. By Lemma 4.8, A^{_{⇁} a} is in S.

Now suppose that a = a_{max}. Observe that it suffices to assume that A = {a, b, c} with b < a and c < a. Since A is indecomposable, Lemma 4.3 gives that c < b^{a} and b < c^{a}. Thus we need only to verify that that (c, b^{a}) and (b, c^{a}) are standard pairs.

Assume first that o(c, a) ≥ 3 and o(b, a) ≥ 3, and consider pairs (c, b^{a}) and (b, c^{a}). By two applications of Lemma 4.2, we have o(c^{∘}, a^{∘}) ≥ 1 and o(b^{∘}, a^{∘}) ≥ 1. Thus c^{∘} ⊏ a^{∘} and b^{∘} ⊏ a^{∘} from which (b^{∘})^{a^{∘}} = (b^{∘})^{a} = (b^{a})^{∘} and (c^{∘})^{a^{∘}} = (c^{∘})^{a} = (c^{a})^{∘} follows. By inductive assumption, (c^{∘}, (b^{∘})^{a^{∘}}) = (c^{∘}, (b^{a})^{∘}) is a standard pair. From the definition, (c, b^{a}) is standard. Similarly, (b, c^{a}) is standard as well.

Next suppose that either o(c, a) ≤ 2 or o(b, a) ≤ 2. By the symmetry of b and c, we can assume o(b, a) ≤ o(c, a). Since we assume A is indecomposable, we have 1 ≤ o(b, a) ≤ 2.

We first assume o(b, a) = 2. From Lemma 4.1, we have that the extreme orbitals of a are active in both {a, c} and {a, b}. Further the extreme orbitals of a contain all the transition points of b with only one transition point of b in the rightmost orbital of a. This puts the support of c in the rightmost orbital of b^{a}. From Lemma 4.1, this makes (c, b^{a}) standard. If o(c, a) = 2, a similar argument makes (b, c^{a}) standard. If o(c, a) ≥ 3, then o(a^{∘}, c) ≥ 2 and it follows from Lemma 4.1 that the extreme orbitals of c each contain exactly one transition point of a. This puts all of the transition points of b^{a^{−1}} into the extreme orbitals of c with only one transition point of b^{a^{−1}} in the rightmost orbital of c. From Lemma 4.1, this implies (b^{a^{−1}}, c) standard, and thus (b, c^{a}) is also standard.

Now assume o(b, a) = 1. From Lemma 4.1, this puts the support of b in the rightmost orbital of a. If o(c, a) = 1, then c ≪ b^{a} and b ≪ c^{a} making both (c, b^{a}) and (b, c^{a}) standard. If o(c, a) ≥ 2, then from Lemma 4.1, the only transition point of c in rightmost orbital of a is the rightmost transition point of c. We still have c ≪ b^{a} making (c, b^{a}) standard. But now the support of b^{a^{−1}} is in the rightmost orbital of c which makes (b^{a^{−1}}, c) standard by Lemma 4.1. This completes the proof that S is closed under inflation.

To see that ⟨A^{_{⇁} a}⟩ is embeddable in ⟨A⟩, first note that ⟨A^{_{⇁} a}⟩ ⊂ ⟨A⟩. Also, since A′ := A\{a}∪{a^{2}} has the same dynamical diagram as A, ⟨A′⟩ ⊂ ⟨A^{_{⇁} a}⟩ is isomorphic to ⟨A⟩ by Theorem 6. □

We can also define an operation of inflation and a relation ≤ on 𝒮 that corresponds to inflation and ≤ on S.

Definition 6.3. If A is in 𝒮 and m ∈ A, then the inflation of A by m, denoted A^{_{⇁} m} has as its base (where i^{m} is a formal symbol)

(6.1)  A ∪ {i^{m} | (i ∈ A) and (i < m) and (A(i, m) > 0)}

to which the linear order on A is extended by declaring j < i^{m} < j^{m} < m ≤ k whenever i < j < m ≤ k < |A|. The function A^{_{⇁} m} extends that of A by defining for each i, j < m ≤ k < |A|:

A^{_{⇁} m}(i^{m}, j^{m}) := A(i, j)
A^{_{⇁} m}(i, j^{m}) := min (A(j, m) − 1, A(i, m))
A^{_{⇁} m}(i^{m}, k) := min (A(i, m), A(m, k)).

Here we adopt the notational convention that A(m, m) = ∞.

From the provision A(i, m) > 0 in (6.1), we get the following fact that parallels the behavior of inflations in S: if A = B + C, then A^{_{⇁} b} = B^{_{⇁} b}+ C for all b ∈ B, and A^{_{⇁} c} = B + C^{_{⇁} c} for all c ∈ C.

Lemma 6.4. If A is in S and m < |A|, then the signature of the inflation of A by a_{m} is the inflation of A by m.

Proof. The proof is by induction on the complexity of A. Since the lemma is vacuous if |A| ≤ 1 and by the remarks made just before Lemma 6.2, we may assume that A is indecomposable.

First suppose that m = |A| − 1. Since A^{^{⇁} a_{m}} is in S, Theorem 8 implies that if i, j < m then

o(a_{i}, a_{j}^{a_{m}}) ≥ min (o(a_{j}^{a_{m}}, a_{m}) − 1, o(a_{i}, a_{m}))
= min (o(a_{j}, a_{m}) − 1, o(a_{i}, a_{m})).

On the other hand, Lemma 4.3 implies

o(a_{i}, a_{j}^{a_{m}}) ≤ min (o(a_{j}, a_{m}) − 1, o(a_{i}, a_{m})).

Thus o(a_{i}, a_{j}^{a_{m}}) = min (o(a_{j}, a_{m}) − 1, o(a_{i}, a_{m})) = A^{_{⇁} m}(i, j^{m}), as desired.

If m < |A| − 1, then by our induction hypothesis the signature of the inflation (A^{∘})^{_{⇁} m} is the corresponding inflation (A^{∘})^{_{⇁} m} of the signature A^{∘}. Since the signature and rotation maps commute, it therefore suffices to verify that whenever i < m

o(a_{i}^{m}, a_{max}) = min (o(a_{i}, a_{m}), o(a_{m}, a_{max})).

By our induction hypothesis

o(a_{i}^{m}, a_{max}) = o(a_{max}^{∘}, a_{i}^{m}) + 1
= min (o(a_{max}^{∘}, a_{m}), o(a_{i}, a_{m}) − 1) + 1
= min (o(a_{m}, a_{max}) − 1, o(a_{i}, a_{m}) − 1) + 1
= min (o(a_{i}, a_{m}), o(a_{m}, a_{max})).
□

Remark 6.5. Note the complementary role which the inequalities Proposition 5.5 and those in Lemma 4.3 play in this proof.

We now define the relation ≤ on 𝒮 just as with S: A ≤ B if and only if there is a sequence B_{0} = B, B_{1}, ..., B_{n} = A such that if i < n then B_{i+1} is contained in (i.e., is a restriction of) an inflation of B_{i}.

Proposition 6.6. If A, B ∈ S then the following are true:

(1) if A ≤ B, then A ≤ B;

(2) if A ≤ B, then there exist A′ ∈ S with signature A such that A′ ≤ B. In particular, if A ≤ B are in 𝒮, then ⟨A⟩ embeds into ⟨B⟩.

Proof. The first assertion is an immediate consequence of Lemma 6.4. The second assertion in the case A = B^{_{⇁} m} for some m is also an immediate consequence of Lemma 6.4; the general case follows by induction. The final assertion follows from the second assertion, Theorem 2 and Proposition 6.2. □

7. Wreath products of S-generated groups

In this section we show that the operation ∗ on 𝒮 introduced in Section 2.5 corresponds to forming a permutation wreath product of the associated groups. Recall that if A, B, C ∈ S then A = B ∗ C asserts that A = B ∪ C and both b < c and o(b, c) = 1 hold whenever b ∈ B and c ∈ C. Observe that if A ∈ S and A = B ∗ C for nonempty B, C, then there is an open interval J ⊂ I such that:

• J contains the supports of all elements of B;

• J is contained in the rightmost orbital of each element of C and is disjoint

from the feet of C. If moreover B(i, j) > 0 for all i < j < |B|, then there is a t_{0} which is in the rightmost orbital of each b_{i}. Fix such J and t_{0} and define

X := {t_{0}f | f ∈ ⟨B⟩} Y := {Jf | f ∈ ⟨C⟩}.

The goal of this section is to prove the following proposition.

Proposition 7.1. Suppose that A ∈ S and A(i, j) > 0 for all i < j < |A|. If A = B ∗C for nonempty B, C ⊂ A, then the actions of ⟨B⟩ on X and ⟨C⟩ on Y are faithful and consistent. In particular the action of ⟨A⟩ on X × Y is the permutation wreath product of these actions: ⟨B ∗ C⟩ ≅ ⟨B⟩ ≀ ⟨C⟩.

Proof. Observe that by Theorem 7 of this paper and by Theorem 7.1 of [3], we may assume that A has no extraneous bumps. The proposition is an immediate consequence of the next two lemmas using the assignments K = {t_{0}} with S = B, and K = J with S = C. □

Lemma 7.2. Let S ∈ S and K be a singleton or an open interval disjoint from the feet of S. If g ∈ ⟨S⟩ and Kg ∩ K ≠ ∅, then g|_{K} is the identity.

Proof. In the language of [3], every point in K has trivial history. Lemma 5.6 of [3] implies that every orbit of ⟨S⟩ intersects K in at most one point. This gives the conclusion if K is a singleton. If K is open, observe that if Kg ∩ K ≠ ∅, then some t ∈ K has tg ∈ K which implies tg = t. Let x be any fixed point of g in K. By continuity, there is an open subset U of K about g with Ug ⊂ K implying that g is the identity on U. Thus the fixed set of g in K is open in K. Again by continuity, the fixed set of g in K is closed in K and must equal K. □

Lemma 7.3. Let S ∈ S have no extraneous bumps and satisfy that S(i, j) > 0 for all i < j < |S|. If J is a singleton or an open interval contained in the rightmost orbital of every f ∈ S and disjoint from the feet of S, then the action of ⟨S⟩ on {Jg | g ∈ ⟨S⟩} is faithful.

Proof. By Proposition 3.1, it suffices to show that ⋃{Jg | g ∈ ⟨S⟩} intersects each orbital of S. We prove this by induction on the complexity of S. Let f be the top element of S. If |S| ≤ 1, there is nothing to show. By our inductive assumption,

X := ⋃{Jg | g ∈ ⟨S \ {f}⟩}

intersects every orbital of S \ {f}. Moreover the closure of X contains the set of all transition points of S \ {f} and hence intersects every active orbital of f. Since every orbital of f is active and open, X intersects every orbital of f. □

8. The signatures are well-ordered by reduction

Our next task is to analyze the structure of the transitive, reflexive relation (𝒮 , ≤) and prove that it is a pre-well-order (i.e. a well-order on the equivalence classes obtained by identifying A and B whenever A ≤ B ≤ A). We introduce a subcollection ℬ ⊂ 𝒮 of signatures in block form. We show that elements of 𝒮 are equivalent to elements of ℬ and that elements of ℬ are equivalent to unique elements of ℛ modulo permuting summands. Our goal is to analyze the structure of (ℛ, ≤) and prove Theorem 3 from the introduction.

8.1. Signatures in block and reduced form. We use the notation

∑_{i<k+1} A_{i} := ( ∑_{i<k} A_{i}) + A_{k}, and A · m := ∑_{i<m} A.

Recall that if A is in 𝒮, then exp(A) has the same base as A and exp(A)(i, j) = A(i, j) + 1 for all i < j in A. Note that exp(Z) = Z. Observe that exp maps 𝒮 injectively into 𝒮 and that the range of exp is exactly those elements of 𝒮 which take only positive values. As noted earlier A ∗ B is only defined if B = exp(X) for some X ∈ 𝒮. Observe that + and ∗ are associative operations on 𝒮 and that exp(A + B) = exp(A) ∗ exp(B).

We now give a more detailed description of the family ℛ from Section 2.5. It is easiest to define ℛ if we first define a class ℬ (signatures in block form), and an ordinal function ρ on ℬ.

Definition 8.1. The class ℬ is the smallest class containing {0, Z} so that whenever (X_{i} | i < n) is a sequence of elements of ℬ, then ∑_{i<n} exp(X_{i}) is in ℬ.

Observe that if B ≠ 0 is in ℬ, then there exists a unique sequence (A_{i} | i < n) of nonzero elements of ℬ such that B = ∑_{i<n} exp(A_{i}). Define ρ recursively on ℬ by ρ(0) = 0, ρ(Z) = 1, ρ( exp(A)) = ω^{−1+ρ(A)}, and ρ(∑_{i<n} exp (A_{i})) = ∑_{i<n} ρ( exp(A_{i})). Here −1 + α = β if α = 1 + β (so −1 + α = α if α is infinite). This technicality exists because Z is a fixed point of exp, but the ordinal 1 is not a fixed point of α ↦ ω^{α}.

Definition 8.2. ℛ is the smallest subfamily of ℬ which contains 0 and Z so that if (X_{i} | i < n) is a sequence of nonzero elements of ℛ and ρ(X_{i+1}) ≤ ρ(X_{i}) for all i < n − 1, then ∑_{i<n} exp(X_{i}) is in ℛ.

The reader can verify that if X is the signature in Figure 2, then X ∈ ℛ and

ρ(X) = ω^{ω^{(ω+2)}}.

Observe that if B ∈ ℬ and A ∈ 𝒮 is contained in B, then A ∈ ℬ and moreover ρ(A) ≤ ρ(B) (both facts are established by induction on the complexity of B). The next lemma has a straightforward inductive proof and is left to the reader.

Lemma 8.3. The restriction of ρ to ℛ is a bijective correspondence between between the elements of ℛ and the Cantor normal forms for ordinals below ε_{0}. Further, the bijection ρ defines an isomorphism

(ℛ, 0, Z, +, exp) ≅ (ε_{0}, 0, 1, +, ζ ↦ ω^{−1+ζ}).

provided + is restricted to those pairs in ℛ whose sum remains in ℛ.

Here we formally define ω^{−1+0} = 0. Our first task in proving Theorem 3 is to show ρ preserves the order which ℛ inherits from 𝒮. The next lemma gives basic facts about the algebraic operations and their interaction with the relation ≤ on 𝒮; the proof is straightforward and left to the reader.

Lemma 8.4. Suppose that A ≤ A′ and B ≤ B′ are in 𝒮. The following are true:

(1) exp(A^{_{⇁} m}) ≤ (exp(A))^{_{⇁} m} for m < |A|.

(2) exp(A) ≤ exp(A′).

(3) A + B ≤ A′ + B′.

(4) A ∗ exp(B) ≤ A′ ∗ exp(B′).

For the following, recall that A ≡ B means A ≤ B ≤ A.

Lemma 8.5. The following are true:

(1) If (A_{i} | i < n) and B ≠ 0 are in 𝒮 and j < n is such that A_{i} ≤ A_{j} for all i < n, then (∑_{i<n} A_{i}) ∗ exp(B) ≡ A_{j} ∗ exp(B).

(2) If A ∈ 𝒮 then for all m, exp(A) · m ≤ exp(A + Z).

Proof. For (1), first observe that either j > 0 and A_{0} ≤ ∑_{k=1}^{n−1} A_{k} or else A_{n−1} ≤ A_{0} ≤ ∑_{k=0}^{n−2} A_{k}. Thus, by induction, it is sufficient to prove the lemma when n = 2. Furthermore, by Lemma 8.4, it suffices to prove that (A + A) ∗ exp(B) ≤ A ∗ exp(B). In fact we show that (A + A) ∗ exp(B) = (A ∗ exp(B))^{_{⇁} m} where m is the minimum element of exp(B) regarded as a suborder of A ∗ exp(B). To see this, let i, j be elements of A and k be an element of exp(B) above m. We have that

(A ∗ exp(B))^{_{⇁} m}(i, j^{m}) = min (A ∗ exp(B)(i, m), A ∗ exp(B)(j, m) − 1)
= min(1, 0) = 0
(A ∗ exp(B))^{_{⇁} m}(j^{m}, k) = min (A ∗ exp(B)(j, m), A ∗ exp(B)(m, k))
= min (1, exp(B)(m, k)) = 1

which coincides with the definition of (A + A) ∗ exp(B).

To see that (2) is true, let A and m be given. By (1) we have (exp(A) · m) ∗ Z ≡ exp(A) ∗ Z. The conclusion follow by observing

(exp(A) · m) ≤ (exp(A) · m) ∗ Z,

exp(A) ∗ Z = exp(A) ∗ exp(Z) = exp(A + Z).

□

Lemma 8.5 is an early hint that the arithmetic on 𝒮 imitates the behavior of arithmetic on the ordinals. For instance, in analogy to (1), using 1+ω = ω we note

(ω + 1) · ω = sup_{n∈ω} (ω + 1) · n = sup_{n∈ω} ω · n + 1 = ω^{2}.

Next we begin our analysis of ℛ.

Lemma 8.6. If B is in ℛ and α < ρ(B), then there an A in ℛ such that A ≤ B and ρ(A) = α.

Proof. The proof is by induction on ρ(B). If ρ(B) = 0, then the lemma is vacuously true. Now suppose ρ(B) ≥ 1 and let B = ∑_{i<n} exp(X_{i}) where ρ(X_{i+1}) ≤ ρ(X_{i}) for each i < n − 1 (note that possibly n = 1 in which case B = exp(X_{0})). Let k < n be minimal such that α < ρ( ∑_{i≤k} exp(X_{i})). If k = 0 and X_{0} = Z, then α < exp(X_{0}) = 1 and thus α = 0. In this case we take A = 0.

If k = 0 and X_{0} = Y + Z for some Y ≠ 0, then

α < ρ( exp(X_{0})) = ρ( exp(Y + 1)) = ω^{−1+ρ(Y)+1} = ρ( exp(Y)) · ω

and there is an m such that α < ρ( exp(Y)) · m. From (2) of Lemma 8.5,

B′ := exp(Y) · m ≤ exp(Y + Z) = exp(X_{0}) ≤ B.

Since B′ is in ℛ, by our induction hypothesis there is an A in ℛ such that A ≤ exp(Y) · m = B′ ≤ B and such that ρ(A) = α.

If k = 0 but we are not in the previous cases, then ρ(X_{0}) = δ is a limit ordinal. Let 0 < γ < δ be such that α < ω^{−1+γ}. By our induction hypothesis, there is a C ≤ X_{0} in ℛ such that ρ(C) = γ and hence

ρ( exp(C)) = ω^{−1+γ} < ω^{−1+δ} = ρ(B).

Applying our induction hypothesis again, there is an A ≤ exp(C) ≤ exp(X_{0}) = B such that A is in ℛ and ρ(A) = α.

Finally, if 0 < k ≤ n, then let 0 < α′ < ρ( exp(X_{k})) be such that

α = ρ(∑_{j<k} exp (X_{j})) + α′.

Now

α′ < ρ( exp(X_{k})) < ρ( exp(X_{0}) + exp(X_{k})) ≤ ρ(B).

By our induction hypothesis there is an A′ ≤ exp(X_{k}) such that A′ ∈ ℛ and ρ(A′) = α′. Observe that A′ = ∑_{i<m} exp(Y_{i}) for some m ≥ 1 where the Y_{i}’s come from ℛ and ρ( exp(Y_{i+1})) ≤ ρ( exp(Y_{i})) for all i < m. In particular, ρ( exp(Y_{0})) ≤ α′ < ρ( exp(X_{k})) and therefore

A = ∑_{i<k} exp(X_{i}) + ∑_{j<m} exp(Y_{j})

is in ℛ and satisfies that ρ(A) = α. □

Lemma 8.7. If A and B are in ℛ, then ρ(A) ≤ ρ(B) implies A ≤ B.

Proof. If ρ(A) < ρ(B), then by Lemma 8.6 there is an A′ ≤ B in ℛ such that ρ(A′) = ρ(A). Since ρ is one-to-one on ℛ, we have that A′ = A. Similarly, if ρ(A) = ρ(B), then A = B. □

For X ∈ 𝒮, recall that E(X) = exp ( exp(X)).

Lemma 8.8. If A, B ∈ ℛ and A+1 ≤ B, then ⟨E(B)⟩ does not embed into ⟨E(A)⟩.

Proof. Let n be the maximum element of E(A + Z) and note that E(A) ∗ E(A) is obtained from E(A + Z)^{_{⇁} n} by removing its maximum element. Consequently

E(A) ∗ E(A) ≤ E(A + Z) ≤ E(B).

By Propositions 6.6, 7.1, and 8.7

⟨E(A) ∗ E(A)⟩ ≅ ⟨E(A)⟩ ≀ ⟨E(A)⟩

embeds into ⟨exp(B)⟩. By Theorem 3.3, the EA-class of ⟨E(A)⟩ is less than that of ⟨E(A)⟩ ≀ ⟨E(A)⟩ which is at most that of ⟨E(B)⟩. Consequently ⟨E(B)⟩ is not embeddable into ⟨E(A)⟩. □

Lemma 8.9. If A and B are in ℛ and ρ(A) < ρ(B), then ⟨E(B)⟩ does not embed into ⟨E(A)⟩.

Proof. If ρ(A) < ρ(B), then ρ(A + Z) ≤ ρ(B). By Lemma 8.7, A + Z ≤ B and therefore we have the desired conclusion by Lemma 8.8. □

This now leads to the following characterization of the restriction of ≤ to ℛ.

Lemma 8.10. If A and B are elements of ℛ, then the following are equivalent: (1) A ≤ B.

(2) ρ(A) ≤ ρ(B).

Proof. Lemma 8.7 establishes that (2) implies (1). If A ≤ B, Lemma 8.4 gives E(A) ≤ E(B) which implies that ⟨E(A)⟩ embeds in ⟨E(B)⟩ by Proposition 6.6. The contrapositive of Lemma 8.9 with the roles of A and B reversed gives ρ(A) ≤ ρ(B). □

Remark 8.11. While Lemma 8.10 does not mention groups or embeddings between them, it is convenient to use the group theory concept of the EA-class to establish the implication. This is a matter of economy since we will eventually generalize the lemma to 𝒮 and add “⟨A⟩ embeds into ⟨B⟩” to the list of equivalents. On the other hand, it not obvious how to provide a proof of Lemma 8.10 which avoids group theory.

We now broaden our analysis to ℬ and then to 𝒮.

Lemma 8.12. If A, B, and C are in 𝒮 with B, C ≠ 0, then

exp (A + B ∗ exp(C)) ≤ exp ((A + B) ∗ exp(C)).

Proof. Let m be the minimal element of B in exp ((A + B) ∗ exp(C)). It suffices to check that the map

π : exp (A + B ∗ exp(C)) → exp ((A + B) ∗ exp(C))^{_{⇁} m}

defined by

π(i) = \begin{cases}i^{m} & if i ∈ A \\ i & if i ∈ B ∗ exp(C) \end{cases}

is an embedding.

First observe that the restrictions of π to A and B ∗ exp(C) are embeddings. Furthermore, if i ∈ A and j ∈ B ∗ exp(C), then i^{m} < m ≤ j and hence π is order preserving. Finally suppose that i ∈ A and j ∈ B ∗ exp(C). By definition,

exp ((A + B) ∗ exp(C))^{_{⇁} m}(π(i), π(j)) =
min ( exp ((A + B) ∗ exp(C))(i, m), exp ((A + B) ∗ exp(C))(m, j))
= min (1, exp ((A + B) ∗ exp(C))(m, j))
= 1 = exp (A + B ∗ exp(C))(i, j).
□

Lemma 8.13. If A is in ℬ and β < ρ(A), then there exist B, C ∈ ℬ such that exp(A) is equivalent to exp(B + C) and β ≤ ρ(B) < ρ(A). Moreover, if A is indecomposable, then we can take C = A.

Proof. The proof is by induction on ρ(A) and then on the cardinality of A. Toward this end, let A be given; there are now several cases to consider. If A = 0, then the lemma is vacuously true and if A = Z then β = 0 and we can take B = 0 and C = A.

Next suppose that A = B_{0} + C_{0} with both B_{0} and C_{0} not 0. If β ≤ ρ(B_{0}), then we are done. Otherwise, let γ be such that β = ρ(B_{0}) + γ, noting that γ < ρ(C_{0}). Since the cardinality of C_{0} is smaller than that of A, we can apply our induction hypothesis to find B_{1} and C such that exp(B_{1} + C) is equivalent to exp(C_{0}) and γ ≤ ρ(B_{1}) < ρ(C_{0}). Observe that B = B_{0} + B_{1} and C satisfies the conclusion of the lemma:

β = ρ(B_{0}) + γ ≤ ρ(B_{0}) + ρ(B_{1}) = ρ(B_{0} + B_{1}) = ρ(B)

while basic manipulations with the arithmetic in ℬ gives

exp(B + C) = exp(B_{0}) ∗ exp(B_{1} + C) ≡ exp(B_{0}) ∗ exp(C_{0}) = exp(A).

Next suppose that A = exp(D+Z) for D ≠ 0. Let n be such that β ≤ ω^{−1+ρ(D)}·n. Set B = exp(D) · n. By our choice of n we have that β ≤ ρ(B) < ρ(A). Also, it is clear that exp(A) ≤ exp(B + A) and hence it is sufficient in this case to show that exp(B + A) ≤ exp(A). This follows from Lemmas 8.12 and 8.5 respectively:

exp ( exp(D) · n+ exp(D + Z)) = exp ( exp(D) · n + exp(D) ∗ exp(Z))
≤ exp (( exp(D) · (n + 1)) ∗ exp(Z))
≤ exp ( exp(D) ∗ exp(Z)) = exp ( exp(D + Z)).

Finally, suppose that A = exp(D) and ρ(D) is a limit ordinal δ. Let γ < δ be such that β ≤ ω^{−1+γ}. By our induction hypothesis, there exist E, F ∈ ℬ such that exp(D) ≡ exp(E + F) and γ ≤ ρ(E) < δ. We set B = exp(E). As in the previous case, it suffices to show that exp(B+A) ≤ exp(A). This again follows from Lemmas 8.12 and 8.5 respectively:

exp (B + A) ≡ exp ( exp(E) + exp(E + F))
= exp ( exp(E) + exp(E) ∗ exp(F))
≤ exp (( exp(E) + exp(E)) ∗ exp(F))
≤ exp ( exp(E) ∗ exp(F)) ≡ exp ( exp(D)) = exp(A).
□

Lemma 8.14. If A is in ℬ and β < ρ(A), then there exist B, C ∈ ℬ such that exp(A) is equivalent to exp(B+C) and β = ρ(B). Moreover, if A is indecomposable, then we can take C = A.

Proof. The proof is by induction on ρ(A). As before, the case ρ(A) ≤ 1 is trivial. If β < ρ(A), then by Lemma 8.13, there exist X, Y ∈ ℬ such that exp(X+Y) ≡ exp(A), β ≤ ρ(X) < ρ(A), and Y = A if A is indecomposable. If ρ(X) = β, then we are done. Otherwise, by our inductive assumption, there exist B, R ∈ ℬ such that ρ(B) = β and exp(B + R) ≡ exp(X). If we set C := R + Y, we have that

exp(B + C) = exp (B + (R + Y)) = exp(B + R) ∗ exp(Y)
≡ exp(X) ∗ exp(Y) = exp(X + Y) ≡ exp(A).

If A is indecomposable, then we get exp(B + A) ≡ exp(A) from

exp(A) ≤ exp(B + A) ≤ exp(B + R + A) = exp(B + R) ∗ exp(A)
≡ exp(X) ∗ exp(A) = exp(X + A) ≡ exp(A).

So C = A fits the conclusion of the lemma. □

Lemma 8.15. If A is an indecomposable element of ℬ, then there is a unique B ∈ ℛ such that A ≡ B.

Proof. First observe that if A ∈ ℬ is indecomposable, then A = exp(X) for some X. Uniqueness of B follows immediately from Lemma 8.10.

The proof of existence of B is by induction on ρ(A). If ρ(A) = 1, then A = Z and A ∈ ℛ. If A = exp(X) and X is indecomposable, then by our induction hypothesis, there is a Y ∈ ℛ such that Y ≡ X. Since B = exp(Y) is also in ℛ, it follows from Lemma 8.4 that A = exp(X) ≡ exp(Y) = B.

If A = exp ( ∑_{i<n} exp(X_{i})), then by our induction hypothesis there are (Y_{i} | i < n) in ℛ such that Y_{i} ≡ X_{i} for each i < n. If there is no k < n − 1 such that ρ(Y_{k}) < ρ(Y_{k+1}), then exp ( ∑_{i<n} exp(Y_{i})) is in ℛ and is equivalent to A.

Suppose now that there is an k < n − 1 such that ρ(Y_{k}) < ρ(Y_{k+1}) and note that in this case n > 1. We first claim that exp ( exp(Y_{k}) + exp(Y_{k+1})) ≡ exp ( exp(Y_{k+1})). To see this, observe that by Lemma 8.14 with A = exp(Y_{k+1}) and β = ρ(exp(Y_{k})) there exists a R ∈ ℬ such that ρ(R) = ρ( exp(Y_{k})) and exp (R + exp(Y_{k+1})) ≡ exp ( exp(Y_{k+1})). Since

ρ( exp(Y_{k})) < ρ( exp(Y_{k+1})) ≤ ρ(A),

we can apply our induction hypothesis to conclude that R ≡ exp(Y_{k}) and thus that exp ( exp(Y_{k}) + exp(Y_{k+1})) ≡ exp ( exp(Y_{k+1})). Reindexing the remaining summands and repeating the process if necessary, we eventually arrive at an element of ℛ which is equivalent to A. □

8.2. Representing elements of 𝒮 in ℛ. Next we turn to the general analysis of elements of 𝒮. We need the following characterization of nontrivial products, analogous to Lemma 4.5.

Lemma 8.16. Suppose A is in 𝒮 and has cardinality at least 2 and maximum element n. If A satisfies the following conditions:

• for all i < n, A(i, n) ≥ 1 and

• there exist m < n such that A(i, n) = 1 if and only if i ≤ m, then A = B ∗ exp(C) for some nonzero B, C ∈ 𝒮.

Proof. If i ≤ m < j < n, then A(i, n) = 1 < A(j, n) and hence A(i, j) = min (A(j, n)−1, 1) = 1. Furthermore, if m < i < j < n then A(i, j) ≥ min(A(j, n)− 1, A(i, n)) > 0. Thus A = B ∗ exp(C), where exp(C) consists of the elements of A above m and B consists of the remaining elements. This holds even if m = n − 1. In this case A = B ∗ Z = B ∗ exp(Z). □

Lemma 8.17. If A ≠ 0, Z is in 𝒮, then one of the following is true for some nonzero B, C ∈ 𝒮:

(1) A = exp(B),

(2) A = B + C, or

(3) A is equivalent to B ∗ exp(C) and B ∗ exp(C) has the same cardinality as A.

Proof. Let A be given with maximum element n. We are done if there are no i < j ≤ n such that A(i, j) = 0 since then A = exp(B) for some B. If A(i, n) = 0 for some i < n, then A is decomposable by Lemma 5.10 and we are finished.

Now suppose the first two conclusions of the lemma do not occur. In this case, there is an i < j < n such that A(i, j) = 0 but there is no i′ < n such that A(i′, n) = 0. Since A is in 𝒮, it must be that A(j, n) = 1 and in particular there is a j < n such that A(j, n) = 1. Define D to be the restriction of A^{_{⇁} n} such that

D = {i^{n} | i < n and A(i, n) > 1} ∪ {i | A(i, n) = 1} ∪ {n}.

Clearly D ≤ A. Observe that D satisfies the hypothesis of Lemma 8.16 and thus has the desired form B ∗ exp(C) for some nontrivial B and C.

Thus it is sufficient to show that A ≤ D. For each i < n with A(i, n) = 1, let u_{i} be the unique least element of A with i < u_{i} ≤ n and A(u_{i}, n) > 1. This always exists since A(n, n) = ∞. We now perform a sequence of inflations of D by the members of

J := {u_{i}^{n} | i < n and A(i, n) = 1}

in increasing order and then remove some of the resulting conjugates so that the base of the resulting X ∈ 𝒮 consists of:

• all i^{n} such that i ≤ n and A(i, n) > 1 (where n^{n} := n);

• all i^{(u_{i}^{n})} such that A(i, n) = 1.

We claim that A isomorphic to X. Define π : A → X by

π(i) = \begin{cases}i^{n}, & i ≤ n, A(i, n) > 1, \\ i^{(u_{i}^{n})}, & i < n, A(i, n) = 1. \end{cases}

The proof is completed by Claims 8.18 and 8.20 below. □

Claim 8.18. π is order preserving.

Proof. Let i < j < n. If A(i, n) and A(j, n) are both greater than 1, then π(i) = i^{n} < j^{n} = π(j). If A(i, n) = 1 and A(j, n) > 1, then i < u_{i} ≤ j and π(i) = i^{(u_{i}^{n})} < u_{i}^{n} ≤ j^{n} = π(j). If A(i, n) > 1 and A(j, n) = 1, then i < j < u_{j}, i^{n} < u_{j}^{n}, and in the inflation by u_{j}^{n}, we have π(i) = i^{n} < j^{(u_{j}^{n})} = π(j).

Finally if A(i, n) = A(j, n) = 1, then either u_{i} = u_{j} or u_{i} < u_{j}. In the first case, π(i) = i^{(u_{j}^{n})} < j^{(u_{j}^{n})} = π(j). In the second case, i^{(u_{i}^{n})} < u_{i}^{n} < u_{j}^{n}, so π(i) = i^{(u_{i}^{n})} < u_{i}^{n} < j^{(u_{j}^{n})} = π(j). □

Claim 8.19. If i < u_{i} < j < u_{j}, then D(i, u_{i}^{n}) = 1, and A(i, j) = 0.

Proof. The definition of inflation gives

D(i, u_{i}^{n}) = min ((A(u_{i}, n) − 1, A(i, n)) = 1.

For the second conclusion, we have A(j, n) = 1 < A(u_{i}, n), so

A(u_{i}, j) = min (A(j, n) − 1, A(u_{i}, n)) = 0.

Now i < u_{i} and Lemma 5.8 gives A(i, j) = 0. □

Claim 8.20. If i < j ≤ n, then X(π(i), π(j)) = A(i, j).

Proof. We first consider j = n. If either A(i, n) > 1 or both A(i, n) = 1 and u_{i} = n, then X(π(i), π(n)) = D(i^{n}, n) = A(i, n). If A(i, n) = 1 and u_{i} < n, then by Claim 8.19 we have

X(i^{(u_{i}^{n})}, n) = min(D(i, u_{i}^{n}), D(u_{i}^{n}, n)) = min(1, D(u_{i}^{n}, n)) = 1.

For i < j < n, we first assume A(i, n) ≠ A(j, n). Since X is in 𝒮, the previous case implies

X(π(i), π(j)) = min (X(π(j), n) − 1, X(π(i), n))
= min (A(j, n) − 1, A(i, n))
= A(i, j).

If A(i, n) = A(j, n) > 1, then π(i) = i^{n} and π(j) = j^{n}. In this case we have that X(i^{n}, j^{n}) = D(i^{n}, j^{n}) = A(i, j).

Finally we have the case A(i, n) = 1 = A(j, n). If u_{i} = u_{j}, then X(i^{(u_{j}^{n})}, j^{(u_{j}^{n})}) = D(i, j) = A(i, j). So we assume i < u_{i} < j < u_{j}. From the beginning of the proof X(j^{(u_{j}^{n})}, n) = A(j, n) = 1. Since X(u_{i}^{n}, n) = D(u_{i}^{n}, n) = A(u_{i}, n) > 1, we have

X(u_{i}^{n}, j^{(u_{j}^{n})}) = min(X(j^{(u_{j}^{n})}, n) − 1, X(u_{i}^{n}, n)) = 0.

Now i^{(u_{i}^{n})} < u_{i}^{n}, so by Lemma 5.8, we have X(i^{(u_{i}^{n})}, j^{(u_{j}^{n})}) = 0. By Claim 8.19, A(i, j) = 0 = X(π(i), π(j)). □

Lemma 8.21. If A is in 𝒮, then there is a B ∈ ℬ such that A ≡ B. Moreover, if A is indecomposable, then B can be taken to be indecomposable.

Proof. The proof is by induction on the complexity of A. If A = Z or A = 0, then A is already in ℬ. If A = exp(B) for some B, then by our induction hypothesis, there is a B′ ∈ ℬ such that B′ ≡ B. Since exp(B′) ∈ ℬ, by Lemma 8.4, A ≡ exp(B′). If A = B + C, then by our induction hypothesis, there are B′, C′ ∈ ℬ such that B′ ≡ B and C′ ≡ C. Again, B′ + C′ ∈ ℬ and A = B + C ≡ B′ + C′.

If A is not of these three forms, then Lemma 8.17 implies that there exist B, C ∈ 𝒮 such that A ≡ B ∗ exp(C) and the cardinality of B ∗ exp(C) is the same as that of A. As above, by induction hypothesis, we may assume that B and C are both in ℬ. If B = exp(X) for some X (which would necessarily be in ℬ), then B ∗ exp(C) = exp(X) ∗ exp(C) = exp(X + C), which is in ℬ. Thus we may assume that B = ∑_{i=1}^{n} exp(X_{i}) where each X_{i} is in ℬ. Let i ≤ n be such that ρ(X_{i}) is maximized. By Lemmas 8.10 and 8.15, we have that X_{j} ≤ X_{i} for all j ≠ n. By Lemma 8.5,

( ∑_{i=1}^{n} exp(X_{i})) ∗ exp(C) ≡ exp(X_{j}) ∗ exp(C) = exp(X_{j} + C) ∈ ℬ.
□

We are now in a position to extend the definition of ρ to 𝒮: if A ∈ 𝒮 set ρ(A) := ρ(B) where B ∈ ℛ and A ≡ B. Such a B exists by Lemmas 8.21 and 8.15 and is unique by Lemma 8.10. Lemma 8.10 now immediately extends to all of 𝒮.

Lemma 8.22. If A and B are indecomposable elements of 𝒮, then the following are equivalent:

(1) A ≤ B.

(2) ρ(A) ≤ ρ(B).

If A ≠ 0 is in 𝒮, let A^{−} be the result of removing the top element of A.

Lemma 8.23. If A ≠ 0 is in 𝒮, then ρ(A^{−}) < ρ(A).

Proof. We first show that A^{−}+Z ≤ A. This is proved by induction on the complexity of A. If A = A^{−} + Z, there is nothing to show. Let n = |A| − 1 and fix an i < n such that A(i, n) > 0. Define B to be the restriction of A^{_{⇁} n} to {0, …, n − 1, i^{n}}, noting that B^{−} = A^{−}. We now have that B(i, i^{n}) = A(i, n) − 1 and for all j < n,

B(j, i^{n}) = min (A(i, n) − 1, A(j, n)) ≤ A(j, n).

Thus B ≤ A and B has smaller complexity than A. By our induction hypothesis A^{−} = B^{−} ≤ A^{−} + Z = B^{−} + Z ≤ B ≤ A.

Now suppose that ρ(A^{−}) ≥ ρ(A). Since A^{−} + Z ≤ A,

ρ(A^{−}) ≤ ρ(A^{−} + Z) ≤ ρ(A) ≤ ρ(A^{−})

and it must be that ρ(A^{−}) = ρ(A^{−} + Z) = ρ(A). It follows from Lemma 8.22 that E(A^{−}) ≡ E(A^{−} + Z) and that ⟨E(A^{−})⟩ and ⟨E(A^{−} + Z)⟩ are in the same biembeddability class. This contradicts Lemma 8.8. □

8.3. EA-class calculations. If ξ < ε_{0}, then R_{ξ} ∈ ℛ is the unique element with ρ(R_{ξ}) = ξ and G_{ξ} := ⟨R_{ξ}⟩; these are just restatements of the definitions of R_{ξ} and G_{ξ} given in Section 2.5 which made only implicit reference to ρ. With these definitions, it is immediate that G_{ξ+1} ≅ G_{ξ} + Z and by Proposition 9.3, G_{ξ} embeds into G_{η} if and only if ξ ≤ η.

We now verify the EA-class calculations asserted in Theorem 1. Observe that if ξ < η < ε_{0}, then EA(G_{ξ}) ≤ EA(G_{η}). We first note the following lemma.

Lemma 8.24. If A ∈ S and |A| > 1, then

sup_{B<A} EA(⟨B⟩) ≤ EA(⟨A⟩) ≤ ( sup_{B<A} EA(⟨B⟩)) + 2

and ⟨A⟩ has property Σ. In particular, if sup_{B<A} EA(⟨B⟩) is a limit ordinal, then EA(⟨A⟩) = ( sup_{B<A} EA(⟨A⟩)) + 2.

Proof. Since B < A implies ⟨B⟩ embeds into ⟨A⟩, the first inequality follows from the monotonicity of EA-class. To see the second inequality, define for each k ∈ ω

B_{k} := {a_{i}^{a_{max}^{p}} | i < |A| − 1 and 0 ≤ p ≤ 2k}.

As noted in the beginning of Section 6, if A_{k} is obtained from A by iteratively inflating by a_{max}, then B_{k} ≤ A_{k}^{−}. In particular by Lemma 8.23, ρ(B_{k}) < ρ(A). By Lemma 8.22, B_{k} < A. Setting

N := ⋃_{k=0}^{∞}⟨a_{i}^{a_{max}^{p}} | i < |A| − 1 and − k ≤ p ≤ k⟩

we have that ⟨A⟩ is an extension of N by Z and N is an increasing union of groups isomorphic to ones of the form ⟨B_{k}⟩. Thus

EA(⟨A⟩) ≤ EA(N) + 1 ≤ ( sup_{k} EA(⟨B_{k}⟩)) + 2 ≤ ( sup_{B<A} EA(⟨B⟩)) + 2

as desired.

The above argument in particular shows that every S-generated group is in the smallest class that contains the abelian groups and is closed under the elementary operations of extensions and directed unions. Since the class of groups which has property Σ includes this class, it follows that every S-generated group has Σ. □

Lemma 8.25. If ξ = ω^{(ω^{α})·(2^{n})} for 0 ≤ α < ε_{0} and n < ω, then EA(G_{ξ}) = ω · α + n + 2 if α > 0 and EA(G_{ξ}) = n + 1 if α = 0.

Proof. Define

Ξ := {ω^{(ω^{α})·(2^{n})} | 0 < α < ε_{0} and n < ω}

and set θ(ω^{(ω^{α})·(2^{n})}) = ω·α+n+2. We verify by induction on ξ that EA(G_{ξ}) = θ(ξ), which is what is asserted in the first conclusion.

The least element of Ξ is ω^{ω}. In this case, R_{ω^{ω}} = E(Z + Z) is the signature of a standard pair with oscillation 2 and G_{ω^{ω}} is the Brin-Navas group, which has EA-class ω + 2 = θ(ω^{ω}). Next observe that if ω^{(ω^{α})·(2^{n})} is in Ξ, then the next element of Ξ is ω^{(ω^{α})·(2^{n+1})}. In particular, ξ ∈ Ξ is a limit point of Ξ precisely when ξ = ω^{ω^{α}} for some α > 1. If ξ ∈ Ξ is of the form ω^{(ω^{α})·(2^{n+1})}, then setting ξ′ = ω^{(ω^{α})·(2^{n})} we have R_{ξ} = R_{ξ′} ∗ R_{ξ′}. By Proposition 7.1, G_{ξ} = G_{ξ′} ≀ G_{ξ′}. By Proposition 3.3 and our induction hypothesis,

EA(G_{ξ}) = EA(G_{ξ′}) + 1 = θ(ξ′) + 1 = θ(ξ).

Now assume that ξ ∈ Ξ is a limit point of Ξ. In what follows ξ′ always represents an element of Ξ. We first claim that

(8.1)  θ(ξ) = ( sup_{ξ′<ξ} θ(ξ′)) + 2.

If ξ = ω^{ω^{α+1}}, then (8.1) follows from the fact that ξ = sup_{n} ω^{(ω^{α})·(2^{n})} and consequently that

\begin{matrix}θ(ξ) = & ω · (α + 1) + 2 = ω · α + ω + 2 \\ = & ( sup_{n} ω · α + n) + 2 = ( sup_{n} θ(ω^{(ω^{α})·(2^{n})})) + 2. \end{matrix}

If ξ = ω^{ω^{α}} for a limit ordinal α, then (8.1) follows from the continuity of the maps α ↦ ω^{ω^{α}} and α ↦ ω · α. Observe that in both cases sup_{ξ′<ξ} θ(ξ′) = ω · α is a limit ordinal. Now observe that by Lemma 8.24 and our induction hypothesis

EA(G_{λ}) = ( sup_{ξ′<ξ} EA(G_{ξ′})) + 2 = ( sup_{ξ′<ξ} θ(ξ′)) + 2 = θ(ξ).

The first equality holds since sup_{ξ′<ξ} EA(G_{ξ′}) = sup_{ξ′<ξ} θ(ξ′) is a limit ordinal.

If α = n = 0, then ξ = ω, R_{ω} = exp(Z + Z) = Z ∗ Z, G_{ω} = Z ≀ Z, and EA(G_{ω}) = 1. The last conclusion follows from Lemma 8.24 and arguments similar to those above. □

We have established the following proposition.

Proposition 8.26. For each ξ < ε_{0}, G_{ξ} is elementary amenable and in particular does not contain a copy of Thompson’s group F.

9. The embeddability relation on S-generated groups

We now complete the proof of Theorem 1. We have seen that that if A and B are indecomposable elements of ℛ, then ⟨A⟩ embeds into ⟨B⟩ if and only if ρ(A) ≤ ρ(B). Moreover, we have seen that if A is an indecomposable element of 𝒮, then there is a unique B in ℛ such that ⟨A⟩ is biembeddable with ⟨B⟩. To prove Theorem 1, we must extend our analysis to groups generated by decomposable elements of ℛ and 𝒮. The following lemma is used in this section and the next.

Lemma 9.1. Let H be generated by a finite geometrically fast system S of functions with |S| > 1 and a ⊏-maximum element h in that g ⊏ h for every g ∈ S \ {h}. Let N be the normal closure of S \ {h}. Then the following hold:

(1) There there is an embedding of H into PL_{+}(I) so that the image of S has a ⊏-maximum element and so that every element of H \ N has extended support identical to that of the image of h.

(2) For each f ∈ N \ {1} and each g ∉ N, we have [f, g] ≠ 1. Thus the center of H is trivial.

(3) The centralizer of every element of H \ N is cyclic.

Proof. In this proof, ⟨2⟩ is the multiplicative subgroup of R generated by 2, and 3⟨2⟩ is the coset containing 3. We first adjust the elements of S slightly so that after the adjustment it still satisfies the hypotheses, the isomorphism class of ⟨S⟩ has not changed, and each element of S is piecewise linear with all slopes used by h coming from 3⟨2⟩ and all slopes used by elements of S \ {h} coming from ⟨2⟩. We can do this by keeping all transition points the same and changing each bump so that its graph is two affine pieces. If the pieces have slopes sufficiently close to 0 or +∞, as appropriate, then the feet of each new bump are small enough to be contained in the feet of the bump it replaces. The dynamical diagram is unchanged and the group generated isomorphic to the original.

All elements of H are of the form f = uh^{i} with u ∈ N a product of elements of C = {g^{h^{j}} | g ∈ S \ {h}, j ∈ Z}. It follows from the chain rule and the fact that h is the identity on no open interval that every element of C has slopes restricted to ⟨2⟩. The element f = uh^{i} is outside N if and only if i ≠ 0. Thus every element f of H \ N has slope in 3^{i}⟨2⟩ everywhere the slope of f is defined. Hence every f ∈ H \ N has extended support equal to that of h, proving (1).

With f ∈ N \ {1} and g ∈ H \ N, the only way to have [f, g] = 1 is for the orbitals of f to be among the orbitals of g. It then follows from Theorem 4.18 of [7] that on each orbital J of g, there would be a piecewise linear bump b with support J with f|_{J} and g|_{J} each a power of b|_{J}. This is not possible because 3 to a nonzero, rational power is never equal to such a power of 2, proving the first part of (2). The center of H is trivial because there is no room for a nontrivial central element.

To prove (3), we add to the information in the paragraph above. For g ∈ H \ N and [f, g] = 1, we now know f ∉ N, and the extended supports of f and g equal that of h. Thus the orbitals of f and g are identical. Again, Theorem 4.18 of [7] makes each of f and g powers of a common root on each orbital. By Theorem 4.15 of [7], for each orbital J of g there is a unique minimum root r_{J} so that all roots of f and g on J are integral powers of r_{J}. For each orbital J of g, let m_{J} and n_{J} be the integers so that f|_{J} = r_{J}^{m_{J}} and g|_{J} = r_{J}^{n_{J}}.

Assume by way of contradiction that there are orbitals J ≠ K of f for which m_{J}/n_{J} ≠ m_{K}/n_{K}. Now

\begin{aligned}(f|_{J})^{n_{J}} & = r_{J}^{(m_{J} n_{J})} = (g|_{J})^{m_{J}} , while \\ (f|_{K})^{n_{J}} & = r_{K}^{(m_{K}n_{J})} ≠ r_{K}^{(m_{J} n_{K})} = (g|_{K})^{m_{J}} . \end{aligned}

Thus a = f^{n_{J}} g^{−m_{J}} is the identity on J and not on K. From (1) we have a ∈ N. But this contradicts the fact that a commutes with g ∉ N which by (2) means that a ∉ N. Thus m_{J}/n_{J} = m_{K}/n_{K} for all orbitals J and K of g. Thus f is determined by g and by the restriction of f to one particular orbital of g. By Theorem 5.5 of [7], if J is an orbital of g, then the restriction of the centralizer of g to J is cyclic. Thus the centralizer of g in H is cyclic. □

Lemma 9.2. If A, B ∈ ℛ and ρ(A) < ρ(B), then ⟨B⟩ does not embed into ⟨A⟩.

Proof. Assume the lemma is false, and let (β, α) be the lexicographically minimal pair for which there are A and B in ℛ so that ρ(A) = α < β = ρ(B) and ⟨B⟩ embeds in ⟨A⟩. Since we know that ⟨C⟩ embeds in ⟨B⟩ whenever C ∈ ℛ has ρ(C) < ρ(B), our choice of α and β must have β = α + 1 and ⟨A⟩ embeds in no ⟨D⟩ with D ∈ ℛ and ρ(D) < ρ(A).

The result holds if α is finite since then ⟨A⟩ = Z^{α} and ⟨B⟩ = Z^{α+1} and an embedding of ⟨B⟩ in ⟨A⟩ is not possible. We thus assume that α is infinite with Cantor normal form

(9.1)  α = ω^{α_{0}} + ω^{α_{1}} + ⋯ + ω^{α_{k}} + n

with α_{0} ≥ α_{1} ≥ ⋯ ≥ α_{k} > 0 and n ≥ 0.

We thus have

A = A_{0} + A_{1} + ⋯ + A_{k} + Z · n,  and
B = A_{0} + A_{1} + ⋯ + A_{k} + Z · (n + 1),

where, for 0 ≤ i ≤ k, each A_{i} is in ℛ and indecomposable with |A_{i}| > 1 and ρ(A_{i}) = ω^{α_{i}}.

With G_{i} = ⟨A_{i}⟩, we have ⟨A⟩ representable as G_{0} +G_{1} +⋯+G_{k} +Z^{n} and ⟨B⟩ as G_{0} + G_{1} + ⋯ + G_{k} + Z^{n+1}. We assume a homomorphic embedding ϕ : ⟨B⟩ → ⟨A⟩. For 0 ≤ i ≤ k, we let π_{i} : ⟨A⟩ → G_{i} be the projection homomorphism, and let ϕ_{i} = π_{i} ∘ ϕ : ⟨B⟩ → G_{i}.

If for all i with 0 ≤ i ≤ k, we have ϕ_{i}(Z^{n+1}) trivial, then ϕ embeds Z^{n+1} into Z^{n} which is not possible. Thus for some i with 0 ≤ i ≤ k and some element x ∈ Z^{n+1}, we have that y = ϕ_{i}(x) is a nonidentity element of G_{i}. Let A_{i} ∈ S have signature A_{i}, let h_{i} be the maximum element of A_{i}, and let N_{i} be the normal closure in G_{i} = ⟨A_{i}⟩ of A_{i} \ {h_{i}}.

We note that for all g ∈ B, we have [g, x] = 1. Thus [ϕ_{i}(g), y] = 1 in G_{i}. If y ∉ N_{i}, then by Lemma 9.1(3) the centralizer C_{i} of y in G_{i} is cyclic. From this, we have ϕ_{i}(g) ∈ C_{i}. This puts the image of ϕ in

⟨A_{0}⟩ + ⋯ ⟨A_{i−1}⟩ + C_{i} + ⟨A_{i+1}⟩ + ⋯ ⟨A_{k}⟩ + Z^{n}

which is isomorphic to the group generated by

E = A_{0} + ⋯ + A_{i−1} + A_{i+1} + ⋯ + A_{k} + Z · (n + 1)

which is in ℛ. Since (9.1) is in normal form and since ρ(A_{i}) > ω, we have ρ(E) < ρ(A) = α. This contradicts our initial choice of α.

If y ∈ N_{i}, then by Lemma 9.1(2) the centralizer C_{i} of y in G_{i} is contained in N_{i}, and ϕ_{i}(g) is in N_{i}. This puts the image of ϕ in

⟨A_{0}⟩ + ⋯ ⟨A_{i−1}⟩ + N_{i} + ⟨A_{i+1}⟩ + ⋯ ⟨A_{k}⟩ + Z^{n}.

Since ⟨B⟩ is finitely generated, we can replace N_{i} in the above by a suitable finitely generated subgroup. There is an l so that ϕ_{i}(⟨B⟩) is contained in ⟨K_{l}⟩ where

K_{l} := {h^{m_{i}^{j}} | h ∈ A_{i}, h < m_{i}, and − l ≤ j ≤ l}.

If K′_{l} is similarly defined with −l ≤ j ≤ l replaced by 0 ≤ j ≤ 2k, then ⟨K_{l}⟩ is isomorphic to ⟨K′_{l}⟩. But K′_{l} ≤ K′′_{l} where K′′_{l} is an appropriately chosen iterated inflation of A_{i}. By Lemma 6.2, K′′_{l} and thus also K′_{l} are in S and ρ(K′′_{l}) = ρ(A_{i}). By Lemma 8.23, ρ(K′_{l}) < ρ(K′′_{l}) = ρ(A_{i}).

We now have that ⟨B⟩ embeds in

⟨A_{0}⟩ + ⋯ ⟨A_{i−1}⟩ + ⟨K′_{l}⟩ + ⟨A_{i+1}⟩ + ⋯ ⟨A_{k}⟩ + Z^{n}.

Once again, since (9.1) is in normal form, we get that ρ(F) < ρ(A) = α. Again, this contradicts our choice of α. This completes the proof. □

We are finally in a position to complete the proof of Theorem 1. Observe that if A and B are in 𝒮, then

⟨A + B⟩ = ⟨A⟩ + ⟨B⟩ ≅ ⟨B⟩ + ⟨A⟩ = ⟨A + B⟩.

On the other hand, the symbolic manipulations which define ≤ on 𝒮 do not typically yield A + B ≤ B + A. We deal with this as follows. Define 𝒮′ to be all A in 𝒮 such that A = ∑_{i<n} A_{i} where A_{i} is indecomposable and if ρ(A_{i+1}) ≤ ρ(A_{i}) for all i < n. Clearly, if A is in 𝒮, then ⟨A⟩ is isomorphic to ⟨B⟩ for some B ∈ 𝒮′. Putting this together with Lemma 9.2 gives the following proposition.

Proposition 9.3. If A and B are in 𝒮′, then the following are equivalent: (1) A ≤ B

(2) ⟨A⟩ embeds into ⟨B⟩

(3) ρ(A) ≤ ρ(B). Moreover, for each A in 𝒮′, there is a unique element B of ℛ such that ⟨A⟩ is biembeddable with B.

10. (𝔉, ↪) is not linear

We conclude this paper by showing that the class of those subgroups of F admitting a finite geometrically fast generating set is not linearly ordered by the embeddability relation. Consider the groups B + Z and G with geometrically fast generating sets specified by the dynamical diagrams in Figures 4 and 5 below. We apply Lemma 9.1 embedding B + Z and G in PL_{+}(I) so that {a, b} and {f, g, h} satisfy (1) of the Lemma. Notice that ⟨a, b⟩ is the Brin-Navas group B; c generates a copy of Z which commutes with the elements of B.

Theorem 9. With G and B + Z as above, the following are true:

(1) EA(G) = EA(B + Z) = ω + 2.

(2) There is no embedding of B + Z into G.

(3) There is no embedding of G into B + Z.

Proof. We begin by verifying (1). Define N_{G} to be the normal closure of {g, h} in G and N_{B} to be the normal closure of b in B. The group N_{G} is generated by C = {h^{f^{i}}, g^{f^{i}} | i ∈ Z}. If C_{n} = {g^{f^{i}}, h^{f^{i}} | −n ≤ i ≤ n}, then Theorem 3.3 implies sup_{n} EA(⟨C_{n}⟩) = ω and hence that EA(N_{G}) = ω + 1. Since G is finitely generated and G/N_{G} ≅ Z, we have EA(G) = ω + 2. Similarly, the group N_{B} + Z is generated by D = {b^{a^{i}} | i ∈ Z} ∪ {c}. An analogous computation shows that EA(N_{B} + Z) = ω + 1 and that EA(B + Z) = ω + 2.

Next we turn to (2). Assume there is an embedding B+Z into G. The centralizer of c in B + Z includes B and is not abelian. By (3) of Lemma 9.1 the image of c must be in N_{G}. By (2) of Lemma 9.1 the image of every element of B must be in N_{G} since otherwise that image would not commute with the image of c. Thus an embedding of B + Z into G has its image in N_{G}. But EA(N_{G}) = ω + 1 and EA(B + Z) = ω + 2 so this is not possible.

We will verify (3) through a series of claims.

Claim 10.1. If G embeds in B + Z, then G embeds in B.

Proof. If an embedding exists it can be composed with the projection to B. The kernel of this projection consists of all (1, c^{k}) in B + Z. These are all in the center of B + Z and if the image of the embedding intersected this kernel, then the image would have nontrivial center. But by (2) of Lemma 9.1, G has trivial center. Thus the composition of the embedding with the projection is one-to-one. □

Next we introduce some tools used in [23]. Define the following predicates where the variables are intended to range over elements of B + Z and G:

\begin{aligned}C(x, y) & := ^{⌜}[x, y] = 1^{⌝}, \\ D(x, y) & := ^{⌜}(¬C(x, y)) ∧ C(x, x^{y})^{⌝}, \\ T (x, y, z) & := ^{⌜}D(x, y) ∧ D(x, z) ∧ D(y, z) ∧ C(x, y^{z})^{⌝}. \end{aligned}

We think of D(x, y) as saying that y “dominates” x in that a typical pair that satisfies this is a fast pair of nested one bump functions with the orbital of y as the larger of the two. We think of T (x, y, z) as saying that (x, y, z) forms a “tower” in that a typical triple that satisfies T is a fast triple of nested one bump functions

a  b  c

Figure 4. A diagram for B + Z

f  h g

Figure 5. The group G = ⟨f, g, h⟩ with z the largest and x the smallest. While these are typical, they are not the only examples and we need to know a little more about the functions that satisfy these predicates.

Claim 10.2. If x, y ∈ F and D(x, y) holds, then:

(1) For each orbital J of x one of the following holds: (a) J is disjoint from all orbitals of y,

(b) J equals an orbital of y with [x|_{J}, y|_{J}] = 1, or (c) Jy is disjoint from J.

(2) There is an orbital J of x such that Jy is disjoint from J.

Proof. Toward proving (1), fix an orbital J of x. Observe that Jy is an orbital of x^{y}. If Jy intersects J but differs from J, then x and x^{y} can’t commute. If Jy is disjoint from J, then (1c) holds.

Now suppose Jy = J. The chain rule implies that x and x^{y} agree at the endpoints of J. If x|_{J} ≠ x^{y}|_{J}, then Theorem 4.18 of [7] implies x^{y}|_{J} cannot commute with x|_{J}, contradicting D(x, y). It follows that x|_{J} commutes with y|_{J}. Moreover either y|_{J} is the identity or else J is an orbital of y. Thus if Jy = J then either (1a) or (1b) hold.

Finally observe that if Conclusion (2) fails, then [x, y] = 1 by Conclusion (1). This would contradict D(x, y). □

Claim 10.3. If x, y, z ∈ F and T (x, y, z) holds, then if J is an orbital of x properly contained in an orbital K of y, then there is an orbital L of z that properly contains K.

Proof. By Claim 10.2 applied to x and y, we have that Jy is disjoint from J. In particular, x|_{K} does not commute with y|_{K}. By Claim 10.2 applied to y, z, and the orbital K, we have that either K is an orbital of z and y^{z}|_{K} = y|_{K} or else Kz is disjoint from K. The former is impossible since it implies ¬C(x|_{K}, y^{z}|_{K}) which is contrary to C(x, y^{z}). It follows that Kz is disjoint from K. Thus any orbital L of z which intersects K contains all of K ∪ Kz and hence properly contains K. □

Claim 10.4. Let x and y be in B \ N_{B}. Then D(x, y) is false.

Proof. Since {a, b} were chosen using (1) of Lemma 9.1, we know that the extended supports of x and y are connected and identical. If D(x, y) held, then [x, y] ≠ 1 implying that x^{y} ≠ x. Thus x^{y} has connected extended support equal to that of x.

If [x^{y}, x] = 1, then x^{y} and x have identical orbitals. Thus y fixes all the transition points of x. This implies that the derivatives of x and x^{y} agree near the ends of each orbital of y. But commuting bumps on the same orbital on which the slopes agree near the ends of the orbital must be identical bumps by Theorem 4.18 of [7]. Thus x^{y} = x and D(x, y) cannot hold. □

We return to the task of proving (3) of Theorem 9. By Claim 10.1 it suffices to show that G does not embed in B. Suppose for contradiction that there is an embedding ϕ : G → B. Recall that G is generated by f < g < h as illustrated in Figure 5.

Claim 10.5. The ϕ-image of N_{G} is contained in N_{B}.

Proof. Observe that if x is in B \ N_{B}, then for all z ∈ B, D(x, x^{z}) is false by Claim 10.4: since N_{B} is normal x^{z} ∉ N_{B}. Since both D(h, h^{f}) and D(g, g^{f}) are true, we have ϕ(g) ∈ N_{B} and ϕ(h) ∈ N_{B}. The conclusion of the claim now follows from the fact that N_{G} is the normal closure of {f, g} in G and N_{B} is normal in B. □

For each i, define f_{i} := f^{h^{−i}}. Observe that

supt(f_{0}) ⊊ supt(f_{1}) ⊊ supt(f_{2}) ⊊ ⋯ ⊊ supt(g).

Define A := {f_{i} | i ≥ 0} ∪ {g} and note that all elements of A are in N_{G} and must have ϕ-images in N_{B}.

For any triple x < y < z from A, we have T (x, y, z) and hence T (ϕ(x), ϕ(y), ϕ(z)). It follows from (2) of Claim 10.2 and Claim 10.3 that there are intervals I_{0} ⊊ I_{1} ⊊ I_{2} ⊊ ⋯ ⊊ J where each I_{i} is an orbital of ϕ(f_{i}) and J is an orbital of ϕ(g).

However the orbitals used in N_{B} come in families 𝒥_{n} indexed over Z with each orbital in family 𝒥_{n} contained in an orbital in family 𝒥_{n+1}. Since orbital I_{0} of ϕ(f_{0}) must come from some 𝒥_{m} and orbital J of ϕ(g) must come from some 𝒥_{n} with m < n, there are only finitely many different orbitals available in N_{B} between I_{0} and J. This contradicts the assumption that there is an embedding of N_{G} into N_{B}. Since this was shown to follow from the existence of an embedding of G into B + Z, we have completed our proof of (3). □

Remark 10.6. Theorem 9 does not provide a counterexample to Conjecture 2. If we let a = g_{4} and b = f_{4} be the generators of G_{τ_{4}} as shown in Figure 1, then the reader can check that A = {a^{2}, b^{a^{−1}b^{−1}}, b^{ab}} is fast and that after extraneous bumps are excised from A, the dynamical diagram for A is identical to that of {f, g, h}, the generating set for G. Thus G embeds in G_{τ_{4}}.

References

[1] Proof theory and constructive mathematics. pages 819–1142. Studies in Logic and the Foundations of Math., Vol. 90, 1977. With contributions by C. Smoryński, Helmut Schwichtenberg, Richard Statman, Solomon Feferman, A. S. Troelstra, Michael P. Fourman, Henk Barendregt, Jeff Paris and Leo Harrington.

[2] Collin Bleak. An algebraic classification of some solvable groups of homeomorphisms. J. Algebra, 319(4):1368–1397, 2008.

[3] Collin Bleak, Matthew G. Brin, Martin Kassabov, Justin Tatch Moore, and Matthew Zaremsky. Groups of fast piecewise linear homeomorphisms. arXiv:1701.08321. 32 pages, 2017.

[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(2):449–460, 1999.

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

[6] . The free group of rank 2 is a limit of Thompson’s group F. Groups Geom. Dyn., 4(3):433–454, 2010.

[7] Matthew G. Brin and Craig C. Squier. Presentations, conjugacy, roots, and centralizers in groups of piecewise linear homeomorphisms of the real line. Comm. Algebra, 29(10):4557– 4596, 2001.

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

[9] Georg Cantor. Contributions to the founding of the theory of transfinite numbers. Dover Publications, Inc., New York, N. Y., 1952. Translated, and provided with an introduction and notes, by Philip E. B. Jourdain.

[10] Ching Chou. Elementary amenable groups. Illinois J. Math., 24(3):396–407, 1980.

[11] Mahlon M. Day. Amenable semigroups. Illinois J. Math., 1:509–544, 1957.

[12] Gerhard Gentzen. The collected papers of Gerhard Gentzen. Edited by M. E. Szabo. Studies in Logic and the Foundations of Mathematics. North-Holland Publishing Co., Amsterdam-London, 1969.

[13] Kurt Gödel. Über formal unentscheidbare Sätze der Principia Mathematica und verwandter Systeme I. Monatsh. Math. Phys., 38(1):173–198, 1931.

[14] . Collected works. Vol. I. The Clarendon Press, Oxford University Press, New York, 1986. Publications 1929–1936, Edited and with a preface by Solomon Feferman.

[15] L. A. S. Kirby and J. B. Paris. Initial segments of models of Peano’s axioms. pages 211–226. Lecture Notes in Math., Vol. 619, 1977.

[16] . Accessible independence results for Peano arithmetic. Bull. London Math. Soc., 14(4):285–293, 1982.

[17] Richard Laver. On Fraïssé’s order type conjecture. Ann. of Math. (2), 93:89–111, 1971.

[18] Andrés Navas. Quelques groupes moyennables de difféomorphismes de l’intervalle. Bol. Soc. Mat. Mexicana (3), 10(2):219–244 (2005), 2004.

[19] Peter M. Neumann. On the structure of standard wreath products of groups. Math. Z., 84:343–373, 1964.

[20] Alexander Yu. Ol’shanskii and Denis V. Osin. A quasi-isometric embedding theorem for groups. Duke Math. J., 162(9):1621–1648, 2013.

[21] G. Polya. Kombinatorische Anzahlbestimmungen fr Gruppen, Graphen und chemische Verbindungen. Acta Mathematica, 68:145–254, 1937.

[22] Mark V. Sapir. Some group theory problems. Internat. J. Algebra Comput., 17(5-6):1189– 1214, 2007.

[23] Amanda Taylor. Locally solvable subgroups of PLo(I), 2017. Ph.D. thesis.

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

   E-mail address: cb211@st-andrews.ac.uk

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

   E-mail address: matt@math.binghamton.edu

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

   E-mail address: justin@math.cornell.edu