The Chameleon Groups of Richard J. Thompson: Automorphisms and Dynamics

Matthew G. Brin

Department of Mathematical Sciences State University of New York at Binghamton Binghamton, NY 13902-6000 December 27, 1994

Contents

Part I. Background . . . . . . . . . . . . . . . . . . . . . . . . 1 0. Introduction . . . . . . . . . . . . . . . . . . . . . . . . . 1 1. Statements, history and outline . . . . . . . . . . . . . . . . . . 3 2. Transitivity properties of Thompson’s groups . . . . . . . . . . . . 10

Part II. Generalities . . . . . . . . . . . . . . . . . . . . . . 14 3. Germs, half germs, germ functions and germ generators . . . . . . . . 14 4. Normalizers and germs of Thompson’s groups . . . . . . . . . . . 22 5. Realizing automorphisms . . . . . . . . . . . . . . . . . . . 25

Part III. PL normalizers . . . . . . . . . . . . . . . . . . . . 28

6. Proof of Theorems 1 and 2 from Theorem 3 . . . . . . . . . . . . 28 Part IV. Non-PL normalizers — proof of Theorem 3 . . . . . . . . 32

7. Markov partitions . . . . . . . . . . . . . . . . . . . . . . 32 8. Trees . . . . . . . . . . . . . . . . . . . . . . . . . . 35 9. The calculus of break values . . . . . . . . . . . . . . . . . . 36 10. Criteria for piecewise linearity . . . . . . . . . . . . . . . . . 39

10.1. The piecewise linearity of h . . . . . . . . . . . . . . . . 39 10.2. The piecewise linearity of h^{−1}ν_{n}h . . . . . . . . . . . . . . 43

11. Relating the criteria . . . . . . . . . . . . . . . . . . . . 45 11.1. Locating d . . . . . . . . . . . . . . . . . . . . . . 46 11.2. Verifying properties . . . . . . . . . . . . . . . . . . . 50

Part V. Examples . . . . . . . . . . . . . . . . . . . . . . . 52 12. Machinery . . . . . . . . . . . . . . . . . . . . . . . . 52 13. The examples . . . . . . . . . . . . . . . . . . . . . . . 55

This paper is dedicated to the memories of Craig C. Squier 1946–1992, and Peter A. Greenberg 1956–1993.

Part I. Background

0. Introduction.

In the late 1960’s Richard Thompson introduced a family of groups in connection with studies in logic. Thompson’s groups have since appeared in a variety of mathematical topics: the word problem, infinite simple groups, homotopy and shape theory, group cohomology, dynamical systems and analysis. Univeral algebraic properties of these groups have been exploited in several of these connections. Thus we see that Thompson’s groups have the ability to be interesting objects in many settings.

In this paper, we exploit the interaction between Thompson’s groups and the subjects of ordered permutation groups and dynamical systems to analyze the automorphisms of some of the groups. Along the way we discover rigidity properties of some local structures on the real line and the circle. To show where ordered permutation groups and dynamical systems are used, and to explain the connection between the automorphisms and rigidity properties, we describe one of our results.

Thompson’s groups have various representations including representations as piecewise linear bijections of the real line, the unit interval or the circle. Further, Thompson’s groups can be described as all bijections that satisfy certain local properties. If we view the circle S^{1} as R/Z (the reals mod the integers), then one of Thompson’s groups T consists of all homeomorphisms f from S^{1} to itself that

(1) are piecewise linear (PL),

(2) preserve orientation,

(3) use only slopes that are integral powers of 2,

(4) have have their breaks (discontinuities of f′) in the set Z[\frac{1}{2}] (all a/2^{b} where a and b are integers), and

(5) satisfy f(Z[\frac{1}{2}]) ⊆ Z[\frac{1}{2}].

We interpret the requirement that f be PL to mean that each x in S^{1} has an open neighborhood on which x is (at most) the only break of f. From this it follows that elements of T have finitely many breaks.

We prove that the outer automorphism group of T is the cyclic group of order 2 generated by the homeomorphism x ↦ −x on S^{1} = R/Z. The first step in this proof comes from the theory of ordered permutation groups where it is shown that any automorphism of T is realized as a conjugation by some self homeomorphism of S^{1} . Thus we are reduced to the study of normalizers of T in the homeomorphism group of S^{1} . The second step uses dynamical systems techniques to show that such a self homeomorphism (perhaps after composition with x ↦ −x) must be in T. We discuss this second step further.

Properties (1)–(5) are local properties in the same way that being smooth is a local property. The group T both defines and is defined by a local structure G. There is more than one approach to defining such a structure, but the simplest is to let G be the set of germs of elements of T. A function is said to be compatible with G if all the germs of the function are in G. The group T then becomes the largest group of homeomorphisms that are compatible with G. Our second step above can now be reworded to say that (up to composition with x ↦ −x) a homeomorphism of S^{1} that normalizes T is compatible with G. Since T also defines G, we can reword this further to say that (up to composition with x ↦ −x) a conjugation that preserves the local structure G must be by an element that is compatible with G. This last sentence states our rigidity property.

Once rigidity is established, we can apply it to analyze the automorphism groups of groups and monoids on S^{1} other than T that consist of elements that are compatible with G. From there we can lift the local structure to the real line R and derive results about automorphisms of groups and monoids that are defined on R. In particular, we analyze the automorphisms of another of Thompson’s groups known as F that acts either on the unit interval or R, depending on the representation chosen.

In order to apply a single rigidity result to a large collection of groups, we develop machinery for relating the local structures that define different classes of groups. We also use this machinery to reduce the rigidity result to a much narrower statement. It is very natural to regard the elements of T as generators of the structure G. We formalize this notion and show that G is generated by the doubling map x ↦ 2x on S^{1} if we introduce “flexibility” at the points in Z[\frac{1}{2}]. Note that the doubling map is compatible with G. With this single generator for G in hand, we derive rigidity from the following statement: If h is an orientation preserving homeomorphism from S^{1} to itself that preserves the set Z[\frac{1}{2}], and if both h and h^{−1} conjugate the doubling map to functions that are compatible with G, then h must be compatible with G. Since this statement investigates conjugators of an expanding map, the use of techniques from dynamical systems is natural at this point.

We discuss another interesting aspect of Thompson’s group T. The cyclic group of order two is also the outer automorphism group of Homeo_{+}(S^{1}), the full group of orientation preserving homeomorphisms of S^{1} . Thus T, a countable group, is imitating the behavior of a larger group. This coincidence is not isolated since both T and Homeo_{+}(S^{1}) are simple. (The group T is finitely presented, and was among the first examples of finitely presented, infinite, simple groups.) See also the remarks on Page 188 of [12] about how the cohomology of T imitates that of larger groups.

Having proofs that two objects share a property makes one curious about the proofs. The more identical the proofs, the more it is likely that one object is revealing secrets about the other. (The proofs that T and Homeo_{+}(S^{1}) are simple can be made identical to the last step where it must be shown the commutator subgroup contains all elements that fix sets with non-empty interior. The known proofs of the last step are quite different.)

This idea has affected our choice of technique. The results that we use from ordered group theory are quite general. To apply them to Thompson’s groups we only need properties (high levels of transitivity on dense subsets) that that the groups share with larger homeomorphism groups. In our use of dynamical systems techniques, we have attempted to suppress purely algebraic properties of these groups and again use only properties that they share with larger homeomorphisms groups. For example, the fact that these groups are finitely generated has been replaced in Sections 3 and 4 by the more general fact that the relevant local structures are finitely generated.

There is a rather extensive literature on Thompson’s groups and their generalizations. We give some references in Section 1. However, the only properties that we need are the transitivity properties which we derive in Section 2.

We do not analyze some generalizations of Thompson’s groups. For each integer n > 1, there is a group F_{n} that acts on R of which F_{2} is F. For integers n and r with 1 ≤ r < n, there is a group T_{n,r} that acts on the circle of which T_{2,1} is T. Among the properties that distinguish these groups from one another is the fact that elements of F_{n} and T_{n,r} all have slopes that are powers of n. The only automorphism groups that we analyze from these families are those of F and T. All of our techniques apply to the groups F_{n} and T_{n,r} except the techniques in Section 11. Since we hope that the automorphism groups of all the F_{n} and T_{n,r} can be analyzed eventually, and since restricting the discussion in sections other than Section 11 would not substantially shorten the exposition (except possibly in Section 2), we have made the discussion general wherever possible.

There is also a family of groups G_{n,r} that act on the Cantor set that generalize another of Thompson’s groups (often referred to as G = G_{2,1} ) that we have not mentioned above. We have no analysis of the automorphisms of any G_{n,r}.

1. Statements, history and outline.

We wish to describe certain homeomorphisms of the real line R and the circle S^{1} . It turns out that we will need several parametrizations of the circle, and we will use S_{r} to denote the space R/rZ, where Z denotes the integers and r is in Z. This makes S_{r} the circle of length r. We avoid the superscript 1 as in S_{r}^{1} for purely aesthetic reasons. With this parametrization in place, we can discuss linearity, piecewise linearity and slope of functions on S_{r} and the rationality of points in S_{r} exactly as we would on R.

Let n be a positive integer greater than 1 and let Z[\frac{1}{n}] denote the set of points in R or S_{r} that have the form an^{b} where a and b are in Z. Let P L_{n}(R) denote the set of all homeomorphisms f from R to itself satisfying:

(1) f is piecewise linear;

(2) f is orientation preserving;

(3) all slopes of f are integral powers of n;

(4) the “breaks” of f (discontinuities of f′) are in a discrete subset of Z[\frac{1}{n}]; and

(5) f(Z[\frac{1}{n}]) ⊆ Z[\frac{1}{n}].

It is easy to verify that every f ∈ P L_{n}(R) satisfies f(Z[\frac{1}{n}]) = Z[\frac{1}{n}] and that P L_{n}(R) is closed under composition and inversion and is thus a group. The term “break” goes back to [8] where the simplicity of certain groups of PL hoemeomorphisms of R is proven.

We are interested in various subgroups of P L_{n}(R) and groups on the circles S_{r} that are related to P L_{n}(R). Any unsupported statements that we make about the groups that we define are not needed in this paper. Justifications can be found in the references that we give later in this section. Given a homeomorphism h from a topological space X to itself, we define the support of f to be the set of points x ∈ X for which f(x) ≠ x. We define BP L_{n}(R) to be the elements of P L_{n}(R) whose support is a bounded subset of R, and we refer to the elements of BP L_{n}(R) as the elements of P L_{n}(R) with bounded support.

We let F_{n} be those elements f of P L_{n}(R) that are translations by multiples of (n − 1) near ±∞ in that there are integers i and j and a real M so that f(x) = x + i(n − 1) for all x > |M| and f(x) = x + j(n − 1) for all x < −|M|. We have BP L_{n}(R) ⊆ F_{n}. The technicalities in the definition of F_{n} come from our choice of representation. (A fact not needed in this paper is that F_{n} is isomorphic to the elements of P L_{n}(R) with support in the unit interval [0, 1]. The isomorphism can be achieved as a conjugation by a suitably chosen PL homeomorphism (with infinitely many breaks) from the open unit interval to the real line.) Note that (5) follows from

(5′) f(x) ∈ Z[\frac{1}{n}] for some x ∈ Z[\frac{1}{n}]

so that (5) follows from (1)–(4) for F_{n} and BP L_{n}(R).

We let T_{n,r} be those homeomorphisms from S_{r} to itself that satisfy (1)–(5) above. (We will not need the fact that T_{n,r} and T_{n,r′} are isomorphic if r and r′ are congruent mod n − 1.) In imitation of BP L_{n}(R), we let BT_{n,r} be the subgroup of T_{n,r} that is generated by those elements of T_{n,r} whose support misses an open interval of S_{r}. That is, BT_{n,r} is generated by elements of T_{n,r} that are the identity on some open interval of S_{r}. It will be seen later that BT_{n,r} is sometimes a proper subgroup of T_{n,r}.

We also consider elementary extensions of these groups. If we replace (2) with

(2′) f is orientation preserving or orientation reversing, then we get groups P̃ L_{n}(R) and T̃_{n,r} that respectively contain P L_{n}(R) and T_{n,r} as subgroups of index 2. We also consider certain monoids. We let \overline{P L}_{n}(R) be the set of functions f whose domain and range are open sets of R that satisfy (1)–(5) where (2) is to be interpreted locally and (4) is to require that breaks of f occur in Z[\frac{1}{n}] and be discrete in the domain of f. The same definition for functions from open sets of S_{r} to open sets in S_{r} gives \overline{T}_{n,r}. These are monoids if we make composition defined on the largest domain possible and if we include the empty function as a zero element. Note that the degree n map x ↦ nx is an element of \overline{T}_{n,r}. Lastly we consider ˜ \overline{P L}_{n}(R) and ˜ \overline{T}_{n,r} which are the obvious two-fold extensions of \overline{P L}_{n}(R) and \overline{T}_{n,r} obtained by also allowing functions that are locally orientation reversing. We do not allow functions that preserve orientation on some open sets and reverse orientation on others.

At this point we have defined the largest and smallest objects that we will look at. Our results will be be about all groups and certain monoids G for which BP L_{n}(R) ⊆ G ⊆ ˜\overline{P L}_{n}(R) or BT_{n,r} ⊆ G ⊆ ˜ \overline{T}_{n,r}. Our “smallest” groups are BP L_{n}(R) and BT_{n,r} since, as we will see in Section 2, they have all the transitivity properties that we will need.

We will need a certain amount of control on a monoid if we are to say anything about its automorphisms. Note that the invertible elements of a monoid G (those a ∈ G for which there is a b ∈ G with ab and ba the identity in G) form a group. This group will have particular importance since our results for monoids will be consequences of our results for groups. This is emphasized in the next definitions. If X is a topological space, then a local homeomorphism f on X is a function from a union of opens sets U_{α} of X into X so that the restriction of f to each U_{α} is an embedding onto an open set in X. It is not required that f be injective. If G is a monoid of local homeomorphisms on X and f is a local homeomorphism on X, then we say that f is compatible with the invertible elements of G if for every x in the domain of f there is an invertible a ∈ G that agrees with f on an open set about x. We say that G is determined by its invertible elements if G consists exactly of all local homeomorphisms of X that are compatible with the invertible elements of G. Note that the invertible elements of G are automatically compatible with the invertible elements of G. Note also that while the restrictions of invertible elements of G to open subsets of X will all be in G, these will not be all the elements of G. As examples, \overline{P L}_{n}(R) and \overline{T}_{n,r} are determined by their invertible elements.

We are interested in automorphisms of the objects that we have defined. We get certain automorphisms by conjugation. Let G be a group or monoid for which BP L_{n}(R) ⊆ G ⊆ ˜\overline{P L}_{n}(R). We let Homeo(R) to be the set of all self homeomorphisms of R and define N(G), the normalizer of G in Homeo(R), to be the set of all h ∈ Homeo(R) for which hGh^{−1} = G. For G with BT_{n,r} ⊆ G ⊆ ˜ \overline{T}_{n,r}, we define N(G) similarly with respect to Homeo(S_{r}). We have a homomorphism Φ : N(G) → Aut(G) where for an h ∈ N(G), we have (Φ(h))f = hfh^{−1} .

We can now give our main result. Recall that F_{2} = F and T_{2,1} = T.

Theorem 1. Let G be a group or monoid for which BP L_{n}(R) ⊆ G ⊆ ˜ \overline{P L}_{n}(R) or BT_{n,r} ⊆ G ⊆ ˜ \overline{T}_{n,r}. If G is not a group, then assume G is determined by its invertible elements. Then

(i) Φ : N(G) → Aut(G) is an isomorphism.

For n = 2, we further have

(ii) N(G) ⊆ P̃ L_{2}(R) or N(G) ⊆ T̃_{2,1} whichever applies, (iii) the containment in (ii) is equality if G is one of BP L_{2}(R), P L_{2}(R), P̃ L_{2}(R),

\overline{P L}_{2}(R), ˜ \overline{P L}_{2}(R), BT_{2,1} , T_{2,1} , T̃_{2,1} , \overline{T}_{2,1} , or ˜ \overline{T}_{2,1} , and (iv) if N_{o}(F_{2}) represents the index 2 subgroup of N(F_{2}) of orientation preserving ele-

ments, then there is a short exact sequence

1 → F_{2} → N_{o}(F_{2}) → T_{2,1} × T_{2,1} → 1.

Remark: The appearance of T_{2,1} × T_{2,1} in (iv) above is easy to explain. Elements of F_{2} are translations by integers near ±∞. Thus near each of −∞ and +∞, elements of F_{2} commute with functions that are lifts of homeomorphism of S_{1} . Those homeomorphisms of S_{1} that lift to P L_{2}(R) are elements of T_{2,1} . For an n other than 2, the statement of (iv) would be more complicated. See Section 6.

We can give our “intermediate” result. It is actually not weak enough to be truly intermediate. Let ν_{2}(x) = 2x. If we regard this as a function on S_{1} then it is an element of \overline{T}_{2,1} .

Theorem 2. Let h : S_{1} → S_{1} be an orientation preserving homeomorphism for which h(Z[\frac{1}{2}]) = Z[\frac{1}{2}], and assume that hν_{2}h^{−1} and h^{−1}ν_{2}h are both in \overline{T}_{2,1} . Then h ∈ T_{2,1} .

The requirement h(Z[\frac{1}{2}]) = Z[\frac{1}{2}] is an annoying technical hypothesis. We can give a cosmetically improved statement. It is “equivalent” to Theorem 2. Note that the unique fixed point of ν_{2} on S_{1} is the element 0 in S_{1} .

Corollary 2.1. Let h : S_{1} → S_{1} be an orientation preserving homeomorphism that fixes 0 in S_{1} , and assume that hν_{2}h^{−1} and h^{−1}ν_{2}h are both in \overline{T}_{2,1} . Then h ∈ T_{2,1} .

The true intermediate result is the following.

Theorem 3. Let h : S_{1} → S_{1} be an orientation preserving homeomorphism for which h(Z[\frac{1}{2}]) = Z[\frac{1}{2}], and assume that hν_{2}h^{−1} and h^{−1}ν_{2}h are both in \overline{T}_{2,1} . Then h is PL.

The proofs of Theorems 1 and 2 from Theorem 3 will be given in Part III as well as the “equivalence” of Corollary 2.1 and Theorem 2. It follows from the arguments in Part III that if Theorem 3 is known for ν_{n}, S_{n−1} , Z[\frac{1}{n}] and T_{n,n−1} for values of n other than 2, then Theorems 1 and 2 will hold for these objects and these values of n as well. The proof of Theorem 3 occupies Part IV.

A separate statement of a rigidity property is deferred to Part III. See Theorem 6.5. This is because the statement needs the terminology of Section 3, and because Part III is a convenient place where all the ingredients needed in the statement can be pulled together.

We give a brief outline of the paper.

There have been many facts discovered about the groups that we consider. However the only properties that we need are the transitivity properties. These are presented in Section 2. Thus the current paper can be read without reference to the (rather extensive) literature on the groups considered. The transitivity properties are crucial to all other sections of the paper.

Provision (i) of Theorem 1 follows directly from a result in the theory of ordered permutation groups due to McCleary and Rubin [18] and a short lemma that we prove that covers the monoid case. Thus we are in a position of needing only to verify hypotheses. This is all done in Section 5. Once (i) of Theorem 1 is proven, we are reduced to the study of normalizers rather than automorphisms.

We consider many groups of homeomorphisms defined on various domains. One of our tasks is to reduce the scope of the investigation by showing that all the normalizers that we wish to study are locally like certain conjugators of a very small set of maps. We build some general machinery for this in Section 3 that applies to groups of homeomorphisms that are defined by local properties. Section 4 applies this to the Thompson groups where we identify the small set of maps as the maps ν_{n} on the circles S_{n−1} .

In Part III, we show that all PL normalziers can be analyzed. From the results of Section 4, this gives the implication that all normalizers (and thus automorphisms) are analyzed if a certain set of conjugators of the maps ν_{n} contain only PL homeomorphisms. This is done in the argument that Theorem 3 implies Theorems 1 and 2.

Part IV contains the proof of Theorem 3. Here it must be shown that any homeomorphism h from S_{1} to itself that has hν_{2}h^{−1} and h^{−1}ν_{2}h in \overline{T}_{2,1} must be PL. Since ν_{2} is an expanding map, we extract a large amount of information about h from our knowledge of hν_{2}h^{−1} . We use this information to do a fairly direct calculation of h^{−1}ν_{2}h. It is then possible to tie together enough properties h^{−1}ν_{2}h with properties of h to show that h must be PL under the hypotheses of the theorem. The difficulty in the argument is the amount of information that must be recorded before the calculation of h^{−1}ν_{2}h can proceed. The bulk of the effort in Part IV goes into the development of structures that keep track of the data.

Part V contains examples that justify hypotheses and phases of the arguments. This section comes at the end of the paper since the examples are most easily described after the machinery in Part IV is developed.

Some unpublished work by others on the automorphisms of Thompson’s groups has been available to the author. All have made the observation in the proof of Statement 6.2 that the main problem is to prove that normalizers are PL. Also, all have made the observation not needed or mentioned in this paper that a normalizer that is PL on some open interval must be PL. A preprint version [11] of [12] that considered the question of automorphisms gave us the idea used in Part IV of studying Markov partitions for the conjugates of the maps ν_{n}. The author is also indebted to Dennis Sullivan for suggesting that it might be useful to look at the non-linearity of the conjugates of the maps ν_{n}.

The most extensive work on the material considered in this paper is the unpublished notes [1] of Bieri and Strebel. (A very small sampling of material from [1] is given in an appendix to [22].) The overlap between [1] and the current paper outside of Part IV is large. Section 2 of the current paper gives a special case of the analysis in [1], and Sections 3, 4 and 6 generalize and repackage ideas in [1]. The theorem of [18] that we quote in Section 5 is a generalization of a theorem in [1] which applies to R which in turn is a generalization of a theorem in [17] which applies to more transitive actions. Most of the examples in Section 13 have their equivalents in [1] but the machinery we use to build the examples is different and the properties are therefore easier to verify. Items from Part IV found in [1] include a formula that gives h from hν_{2}h^{−1} and an invariant based on summing break values (which are defined below in Section 9). Missing from [1] is most of the analysis of Part IV.

We state two results from [1] that complement the results of the current paper. Considered in [1] are groups G(I; A, P) of all orientation preserving, PL self homeomorphisms of an interval I in R with slopes in a multiplicative subgroup P of the positive reals and breaks in a finite subset of an additive ZP module A in R (with action coming from multiplication in R). Also considered is the subgroup B(I; A, P) of those elements of G(I; A, P) with support in some compact subset of the interior of I. It is proven in [1] that if G is a group with B(I; A, P) ⊆ G ⊆ G(I; A, P) where P is not cyclic, then all automorphisms of G are realized as conjugations by PL self homeomorphisms of I. This result uses the density of such a P in the positive reals. It is also proven in [1] that automorphisms of G(I; A, P) are realized by PL self homeomorphisms of I if I is unbounded and by PL self homeomorphisms of I with finitely many breaks if I = R. This result uses the fact that restriction to an unbounded end gives a surjection onto a group of affine functions. The structures of the automorphism groups are also examined in [1].

The result, Theorem 5.1, that we use from [18] realizes automorphisms as conjugations. An earlier version of this result is found in [17], and is used there to analyze the automorphism groups of other homeomorphism groups. It is shown that the full group of PL homeomorphisms on R has trivial outer automorphism group as does the group of PL homeomorphisms on R with finitely many breaks and also the largest group of homeomorphisms of R all of whose elements are (not necessarily continuously) differentiable. See [17] for more details and older references. A special case of Theorem 5.1 for Thompson’s group T appears in [12]. The proof in [12] makes use of algebraic properties of T including its simplicity.

The literature on Thompson’s groups is very scattered. Because of this, many letters from different alphabets have been used to refer to Thompson’s groups. Thompson’s groups also admit a wide variety of representations, so the difficulty of recognition extends beyond the multiplicity of notation. We will not give a complete history, we will not sort out the notation, and we will not list all the representations. We will try to give enought references to enable the reader to get to the literature on the various topics in which these groups have appeared.

A paper that relates some of the representations, that gives a key to some of the notation used, and that gives a brief history is [3]. This is also done in [7].

For relations with the word problem and for the early history of Thompson’s groups see [19].

The connection to infinite simple groups is discussed in [3] and more recently in [21]. See also [22].

Thompson’s group F was rediscovered (by Dydak and Minc and also independently by Freyd and Heller) in connection with questions in homotopy/shape theory. This is discussed in [10] and [6]. It is in this topic that the universal algebraic properties of the groups are derived and exploited. The final paper [16] on the homotopy question is the first to investigate the homological properties of one of Thompson’s groups.

The paper [6] is the start of a systematic investigation of the (co)homology properties of Thompson’s groups and their generalizations. More recent papers are [3], [4], [5], [12],

[22] and [9]. The (co)homology of structures resembling those discussed in Section 3 are investigated in [13]. An acyclic extension of the infinite braid group by BP L_{2}(R) is constructed in [15].

The paper [12] considers the group T from a dynamic point of view.

In analysis, the existence of Thompson’s group F demonstrates that either there is a non-amenable finitely presented group with no free subgroup on two generators or there is a finitely presented amenable group that is not elementary amenable. This is discussed in [7] where it is shown that F is not elementary amenable and in [2] and [7] where it is shown that F contains no free subgroup on two generators. The monograph [7] also contains a version of Thompson’s original proof that T is simple and a proof of Thurston’s observations that T and F are isomorphic to groups of piecewise projective homeomophisms on the circle and the interval respectively. The projective aspects of T are also discussed in [14].

2. Transitivity properties of Thompson’s groups.

This is the only section in which a restriction to n = 2 would result in substantial simplification.

We will concentrate on those properties of Thompson’s groups that are needed for our analysis. It turns out that the only properties we will need are transitivity and related properties (ability to approximate), and not various algebraic properties such as being finitely generated or simple.

Since translations have slope 1 and no breaks, all translations by elements of Z[\frac{1}{n}] are in P L_{n}(R). Similarly, all rotations by elements of Z[\frac{1}{n}] are in T_{n,r}. Thus P L_{n}(R) and T_{n,r} are transitive on Z[\frac{1}{n}]. This is false in general for BP L_{n}(R), F_{n} and BT_{n,r}. We will look at this and at higher levels of transitivity that these groups exhibit on subsets of R and S_{r}. The main point is that these groups are very “flexible.” Any element of Homeo_{+}(R) and Homeo_{+}(S_{r}) can be approximated locally by an element of BP L_{n}(R) or BT_{n,r}.

The main obstruction to strong transitivity of all the groups that we consider is the following which corresponds to “casting out nines” when n = 10. It is also the reason that considering arbitrary n in this section is more involved than just considering n = 2. Lemma 2.1. There is a surjective ring homomorphism ϕ_{n} : Z[\frac{1}{n}] → Z_{n−1} . Proof: Let

(2-1)  x = ∑_{i=1}^{j} a_{i}n^{b_{i}}

where each a_{i} and b_{i} are in Z. Let k = ∑ a_{i} and define ϕ_{n}(x) = k mod (n−1). We first show that this is well defined. We can replace any one a_{i}n^{b_{i}} by (na_{i})n^{b_{i}−1} and k is altered by na_{i} − n = (n − 1)a_{i}. With a finite number of alterations of this type, any two sums (2-1) that give x can be reduced to two expressions x = k_{1}n^{b_{1}} and x = k_{2}n^{b_{2}} . Another flurry of the same kind of steps will make the two expressions identical. This shows that ϕ_{n}(x) is well defined. Now any two elements of Z[\frac{1}{n}] can be represented as multiples of the same integral power of n. This makes it clear that ϕ_{n} is a ring homomorphism.

Lemma 2.2. There is a homomorphism d_{n} : P L_{n}(R) → Z_{n−1} so that for all f ∈ P L_{n}(R) and x ∈ Z[\frac{1}{n}], ϕ(f(x)) = ϕ(x) + d_{n}(f).

Proof: We must show that d_{n}(f) = ϕ(f(x)) − ϕ(x) is independent of x ∈ Z[\frac{1}{n}]. Equivalently, we must show for all x and y in Z[\frac{1}{n}], the truth of

ϕ(f(x)) − ϕ(x) = ϕ(f(y)) − ϕ(y),

or equivalently

(2-2)  ϕ(f(x)) − ϕ(f(y)) = ϕ(x) − ϕ(y).

We can find points x = x_{0} < x_{1} < ⋯ < x_{k} = y so that every break of f in [x, y] is one of the x_{i}. For 0 ≤ i < k, there are b_{i} ∈ Z and c_{i} ∈ Z[\frac{1}{n}] so that x ∈ [x_{i}, x_{i+1}] implies f(x) = n^{b_{i}}x + c_{i}. Since ϕ is a ring homomorphism and ϕ(n) is the multiplicative identity in Z_{n−1} , we get

(2-3)  ϕ(f(x_{i+1})) − ϕ(f(x_{i})) = ϕ(f(x_{i+1}) − f(x_{i}))
= ϕ(n^{b_{i}}x_{i+1} − n^{b_{i}}x_{i})
= ϕ(n^{b_{i}})ϕ(x_{i+1} − x_{i})
= ϕ(x_{i+1} − x_{i})

= ϕ(x_{i+1}) − ϕ(x_{i}) (2-4)

and (2-2) follows by summing (2-3) and (2-4). To see that d_{n} is a homomorphism, note that x ∈ Z[\frac{1}{n}] implies g(x) ∈ Z[\frac{1}{n}] and

d_{n}(fg) = ϕ(f(g(x))) − ϕ(x)
= [ϕ(f(g(x))) − ϕ(g(x))] + [ϕ(g(x)) − ϕ(x)]
= d_{n}(f) + d_{n}(g).

Let Δ_{n} be the kernel of ϕ_{n} : Z[\frac{1}{n}] → Z_{n−1} . We have Δ_{n} = Z[\frac{1}{n}] if and only if n = 2. We now know that an f ∈ P L_{n}(R) induces a specific rotation on the cosets of Δ_{n} in Z[\frac{1}{n}]. The elements of the kernel of d_{n} : P L_{n}(R) → Z_{n−1} are those elements that induce the trivial permutation on the cosets of Δ_{n}. The oddities in the definition of F_{n} are now partly explained by the next corollary. Recall that BP L_{n}(R) ⊆ F_{n}.

Corollary 2.2.1. We have F_{n} ⊆ ker(d_{n}) and thus elements of BP L_{n}(R) and F_{n} preserve the cosets of Δ_{n} in Z[\frac{1}{n}] as sets.

Proof: Near ±∞ the action of elements of F_{n} is to add multiples of (n − 1). This preserves cosets of Δ_{n}.

We now see how transitive BP L_{n}(R) is on Δ_{n}.

Lemma 2.3. Let x_{1} < x_{2} < ⋯ < x_{n} and y_{1} < y_{2} < ⋯ < y_{k} be elements of Δ_{n}. Then there is an f ∈ BP L_{n}(R) so that f(x_{i}) = y_{i} for all i with 0 ≤ i ≤ k.

Remark: We refer to the property in the lemma by saying that BP L_{n}(R) acts order k - transitively or o-k -transitively on Δ_{n} for all k. Any G withBP L_{n}(R) ⊆ G ⊆ ˜ \overline{P L}_{n}(R), is o-k -transitive on Δ_{n} for all k as well. Proof: By adding an extra point from Δ_{n} to each sequence sufficiently far below x_{1} and y_{1} and another from Δ_{n} sufficiently far above x_{k} and y_{k}, we can assume that x_{1} = y_{1} and that x_{k} = y_{k}. If for each i with 0 ≤ i < k, we find a homeomorphism from [x_{i}, x_{i+1}] to [y_{i}, y_{i+1}] that satisfies the local properties required of functions in P L_{n}(R), then we can piece these functions together with the identity on (−∞, x_{1}] ∪ [x_{k}, ∞) to get the required function. Thus it suffices to consider four points a < b, c < d in Δ_{n} and build a homeomorphism from [a, b] to [c, d] that satisfies the properties of functions in P L_{n}(R).

Since all four points are in Δ_{n} ⊆ Z[\frac{1}{n}], there is an integral power of n that evenly divides b − a and d − c. Thus we can divide the intervals [a, b] and [c, d] into subintervals of length an integral power of n. We know that the number of these intervals in each of [a, b] and [c, d] is 0 modulo (n−1). If the number of intervals is not the same for [a, b] and [c, d], then we can increase the number of intervals for one of them as much as we want by repeatedly subdividing random subintervals into n equally spaced smaller intervals. Each time this is done, the number of intervals increases by (n−1). This preserves the property that the lengths of all the intervals are a (perhaps varying) integral power of n. Once the number of subintervals in [a, b] and [c, d] are the same, then a function can be built to map each interval in the subdivision of [a, b] affinely to the corresponding interval in the subdivision of [c, d].

The action is not k -transitive on all of R. However, the set Δ_{n} is dense in R, so we get close. If I and J are two closed intervals in R, then we write I < J if every point in I is less than every point in J. We say that a group acting on R is acting approximately o-k -transtively on R if whenever points x_{1} < x_{2} < ⋯ < x_{k} and closed intervals I_{1} < I_{2} < ⋯ < I_{k} with non-empty interiors are given in R then there is an element of the group that takes each x_{i} into I_{i}.

Corollary 2.3.1. Let G be a group with BP L_{n}(R) ⊆ G ⊆ ˜ \overline{P L}_{n}(R). Then G acts approximately o-k -transitively on R for all k.

The situation is slightly different on the circle. There is an ambiguity of reprentatives for elements of Z[\frac{1}{n}] in S_{r} = R/rZ. If r ≢ 0 mod (n−1) then there is no homomorphism from Z[\frac{1}{n}] in S_{r} to Z_{n−1} but rather one to Z_{a} where a is the greatest common divisor of r and (n − 1). (In fact it turns out that T_{n,r} is simple when a = 1. See [3].) There is also the problem of not having a linear order on S_{r}. This is solved by referring to the counterclockwise orientation on S_{r}. Since functions in T_{n,r} lift to functions in P L_{n}(R) and since functions in P L_{n}(R) can be built in pieces, we leave it as an easy exercise for the reader to verify the following.

Lemma 2.4. Let x_{1}, x_{2}, …, x_{k} be different points in S_{r} that are arranged in counterclockwise order on S_{r} in the order listed, and let I_{1}, I_{2}, …, I_{k} be pairwise disjoint closed intervals with non-empty interiors in S_{r} that are arranged in counterclockwise order on S_{r} in the order listed. Then there is an element in BT_{n,r} that takes each x_{i} into I_{i}.

We will need the following approximation lemma.

Lemma 2.5. Given f ∈ ker(d_{n}) and −∞ < a < b < ∞, there is an element g in BP L_{n}(R) that aggrees with f on [a, b].

Proof: By decreasing a and increasing b we can assume that a and b are in Δ_{n}. By the hypothesis on f we know that f(a) and f(b) are in Δ_{n}. By Lemma 2.3, there is a g_{1} in BP L_{n}(R) that carries a to f(a) and b to f(b). Now we let g agree with f on [a, b] and with g_{1} elsewhere.

Lemma 2.6. Let Γ be generated by translations x ↦ x + a with a ∈ Δ_{n} ∩ (−\frac{1}{2}, \frac{1}{2}) and elements of BP L_{n}(R) with support in (0, 1). Then Γ contains BP L_{n}(R).

Proof: The set of translations x ↦ x + a with a ∈ Δ_{n} is a topological group and the set of translations in the statement of the lemma is a neighborhood of the identity. Thus Γ contains all translations by elements of Δ_{n}. This puts all elements of BP L_{n}(R) with support in an interval of length 1 in Γ. It is now an easy matter to generate all elements of BP L_{n}(R). For example, let f have support in an interval J and let b be an element of Δ_{n} very near the midpoint of J. We can assume that J is not contained in I = (b − \frac{1}{2}, b + \frac{1}{2}). We can find functions g_{1}, g_{2}, …, g_{k} whose supports are in intervals of length less than 1 that are contained in the support of f, and whose composition g = g_{1}g_{2} … g_{k} takes b to f(b). Now g^{−1}f_{1} has its support in J and a fixed point at b. There is an h with support in a small neighborhood of b so that hg^{−1}f_{1} is fixed near b and has support contained in the union of two disjoint closed intervals with lengths less that half the length of J. The rest is clear.

Let p_{r} : R → R/rZ be projection. If r ≡ 0 mod (n − 1), then Δ_{n} = p_{r}^{−1}(p_{r}(Δ_{n})). If not, then we get a proper containment Δ_{n} ⊊ p_{r}^{−1}(p_{r}(Δ_{n})). The next lemma shows that the group BT_{n,r} depends on the image of Δ_{n} under p_{r}.

Lemma 2.7. The group BT_{n,r} consists of those elements of T_{n,r} that preserve p_{r}(Δ_{n}) and it is generated by the rotations x ↦ x + a with a ∈ p_{r}(Δ_{n}) ∩ (−\frac{1}{2}, \frac{1}{2}) and elements of BT_{n,r} with support in (0, 1).

Proof: We first argue that BT_{n,r} contains the rotations by elements of p_{r}(Δ_{n}). Given a rotation ρ(x) = x + a with a ∈ Δ_{n} ∩ (−\frac{1}{2}, \frac{1}{2}) (we bring in p_{r} later), Lemma 2.5 builds a generator g of BT_{n,r} that imitates a portion of ρ so that g^{−1}ρ is another generator of BT_{n,r}. Now as in the previous lemma, BT_{n,r} contains all rotations by all elements of Δ_{n}. However, on S_{r}, these are just rotations by elements of p_{r}(Δ_{n}). Any element in T_{n,r} that preserves p_{r}(Δ_{n}) can be composed with a rotation by an element of p_{r}(Δ_{n}) so that the composition has a fixed point. Now a composition with a generator of BT_{n,r} gives a fixed interval and a new generator of BT_{n,r}. The rest of the proof repeats arguments used here and in the proof of the previous lemma.

Note that the previous lemma shows that BT_{n,r} = T_{n,r} when p_{r}(Δ_{n}) = Z[\frac{1}{n}] in S_{r}. This will happen when r is relatively prime to (n−1). As mentioned above, T_{n,r} is simple when r is relatively prime to (n − 1). We will not need these facts. We will need to know that p_{n−1}(Δ_{n}) = Δ_{n} in S_{n−1} . This will make BT_{n,n−1} a particularly important group.

Part II. Generalities

3. Germs, half germs, germ functions and germ generators.

The restrictions (1)–(5) on P L_{n}(R) and related groups are local in nature. In this section, we make this statement more precise and derive some consequences. On the way, we develop some generalities about locally defined classes of functions. We start with the particular and move to the general.

We start with P L_{n}(R) as typical of the groups that we study. Consider an f ∈ P L_{n}(R). From (4) and (5), we know that each point in R lies in a closed interval J with endpoints in Z[\frac{1}{n}] so that f|_{J} is the restriction to J of an affine function with slope n^{k}, k ∈ Z, and y -intercept b ∈ Z[\frac{1}{n}]. Specifically, f|_{J}(x) = n^{k}x + b.

The behavior of x ↦ n^{k} + b can be better understood if we express elements of R as expansions in base n. That is, each x ∈ R is representable as

(3-1)  x = ∑_{i=−∞}^{∞} a_{i}n^{i}, a_{i} ∈ {0, 1, 2, …, n − 1}

where a_{i} = 0 for all sufficiently large i. The expression is unique for elements of R−Z[\frac{1}{n}]. For elements of Z[\frac{1}{n}], there are two possible representations, one with all a_{i} = 0 for all sufficiently small i, and one with all a_{i} = n − 1 for all sufficiently small i. We adopt the convention that all elements of Z[\frac{1}{n}] are represented so that all a_{i} = 0 for sufficiently small i. Note that this makes the sum of the a_{i} definable for elements of Z[\frac{1}{n}]. We can use this to identify the elements of Δ_{n} as those elements of Z[\frac{1}{n}] for which the sum of the a_{i} is congruent to 0 modulo (n − 1).

We use the usual notation

(3-2)  x = a_{j}a_{j−1} … a_{0}.a_{−1}a_{−2} …

to symbolize the expression in (3-1) where all a_{i} = 0 for i > j. We will refer to the a_{i} as letters (or numerals) in the alphabet {0, 1, …, n − 1} and we will refer to the expressions (3-2) as words that are infinite to the right with a single position between two letters marked by “.” the n-ary point.

The act of taking x to n^{k}x shifts the word (3-2) representing x to the left k places with respect to the n-ary point (with net shift to the right if k is negative). Since b ∈ Z[\frac{1}{n}], the act of adding b is to alter a finite number of letters in (3-2) at the left end of the word. From this we see that if x = … a_{1}a_{0}.a_{−1}a_{−2} … and y = … b_{1}b_{0}.b_{−1}b_{−2} … are in the same orbit under P L_{n}(R), then

(3-3)  there are integers j and k so that for all i < j, a_{i−k} = b_{i}.

Conversely, if (3-3) is satisfied, then y − n^{k}x is in Z[\frac{1}{n}] and (x, y) is on the graph of t ↦ n^{k}t + (y − n^{k}x). We can now define a relation on R by saying that x ∼ y with x and y as represented above if (3-3) is satisfied. This is an equivalence relation whose equivalence classes are the orbits of P L_{n}(R). Note that we have shown that the orbits of P L_{n}(R) are exactly the orbits of

Aff_{n}(R) = \{x ↦ n^{k}x + b | k ∈ Z, b ∈ Z[\frac{1}{n}]\}.

We can now discuss germs. We start with the “smaller” group Aff_{n}(R). Let x ∼ y in R. The set of germs Aff_{n}(R)_{x,y} will be the set of equivalence classes of those f ∈ Aff_{n}(R) that have f(x) = y under the relation f ∼ g if there is an open set about x on which f and g agree. Since an affine map is determined by its behavior on an open set, we see that Aff_{n}(R)_{x,y} is simply the set of affine maps in Aff_{n}(R) that take x to y. These in turn are indexed by the set of integers k for which t ↦ n^{k}t + (y − n^{k}x) is in Aff_{n}(R). That is, y − n^{k}x ∈ Z[\frac{1}{n}]. If there is more than one such k, say k_{1} and k_{2} , then x − n^{k_{1}−k_{2}}x is in Z[\frac{1}{n}], x is in the rationals Q and the expression x = … a_{1}a_{0}.a_{−1}a_{−2} … ends in a periodic pattern with period dividing k_{1} −k_{2} . Conversely, if x is in Q, then the expression x = … a_{1}a_{0}.a_{−1}a_{−2} … ends in a periodic pattern of minimum period d and the slopes that appear in Aff_{n}(R)_{x,y} are exactly those slopes of the form n^{k+di} for all i ∈ Z, where k is some integer determined modulo d by x and y. From this, we have that Aff_{n}(R)_{x,y} has one element if x is irrational and that the slopes Aff_{n}(R)_{x,y} are all integral powers of n if x ∈ Z[\frac{1}{n}]. (Note that there are rationals outside of Z[\frac{1}{n}] with this last property if n > 2.)

If we now turn to P L_{n}(R), we get sets of germs P L_{n}(R)_{x,y} that are identical to those of Aff_{n}(R)_{x,y} except where x ∈ Z[\frac{1}{n}]. For x ∈ Z[\frac{1}{n}], behavior to the right of x and to the left of x are independent and we get all integral powers of n as slopes to the right and all integral powers of n as slopes to the left.

We can now generalize. Let X be a topological space. Let H(X) be the set of homeomorphisms from open sets in X to open sets in X. For each x and y in X, let H(X)_{x,y} be the set of elements of H(X) that take x to y. Let G(X)_{x,y} be the set of germs at x of the elements of H(X)_{x,y}. That is G(X)_{x,y} is the set of equivalence classes in H(X)_{x,y} under the relation that declares two elements related if they agree on some neighborhood of x.

We can compose germs in that elements of G(X)_{x,y} compose with those of G(X)_{y,z} to give elements of G(X)_{x,z}. Also, each G(X)_{x,x} contains the germ of the identity. If we regard G(X) as a function defined on X × X, then we have that G(X) is a category whose objects are the elements of X and whose morphism sets are the sets G(X)_{x,y}. Each element in G(X)_{x,y} has an inverse in G(X)_{y,x} so that the two possible compositions give the identities of G(X)_{x,x} and G(X)_{y,y}. Thus all morphisms are isomorphisms and G(X) is a groupoid. We will deal with substructures of this groupoid. We will have no need to consider topological groupoids.

Let G be a function on X×X written so that G_{x,y} represents the value of G at (x, y) and assume that for each (x, y) ∈ X ×X we have G_{x,y} ⊆ G(X)_{x,y}. If we further assume that G is a groupoid, then we call G a groupoid of invertible germs on X. We will usually omit the word invertible. It is standard to arrive at a groupoid of germs from a pseudogroup (here, the set of G-compatible maps defined below). We will not bother to do this, although we are not really avoiding that much work. See for example [20].

We say that f : U → X, where U is an open subset of X, is G-compatible at x ∈ U if there is a g representing a class in G_{x,f(x)} that agrees with f on some neighborhood of x. We say that f is G-compatible if it is G-compatible at x for each x ∈ U. We let F (G) be the set of all G-compatible functions, we let H(G) be the set of all G-compatible homeomorphisms from X to X, and we let O(G) be the orbits of F (G). We have that O(G) is just the set of equivalence classes in which two points x and y are related when G_{x,y} is not empty. Note that every element of F (G) is a local homeomorphism in that every point in its domain has an open neighborhood that is carried homeomorphically onto an open set in X.

Note that we have not made enough assumptions to guarantee that H(G) is not empty. This can be fixed by requiring that each G_{x,x} be non-empty. This will mean that G_{x,x} contains at least the germ of the identity function and this will make the identity function on X an element of F (G) and thus H(G). Equivalently we could require that the identity function on X be in F (G). When H(G) contains the identity function on X, we will say that the groupoid G contains the identity. Note that this is implied if we require that for each x ∈ X, there is a y so that G_{x,y} is not empty.

To imitate the relationship between P L_{n}(R) and Aff_{n}(R), we need to split germs in half. We now work on the real line R and we let G be a groupoid of germs on R. Given a set of germs G_{x,y} and a function f taking x to y, we say that f is G^{+} -compatible at x if there is an ϵ > 0 so that f and some representative in G_{x,y} agree on [x, x + ϵ). Similarly, f is G^{−} -compatible if f and a representative in G_{x,y} agree on some (x − ϵ, x]. If A is a union of orbits in O(G), then we say that a local homeomorphism f : U → R is (G; A)-compatible if f is G-compatible for all x ∈ U − A and if f is both G^{+} -compatible and G^{−} -compatible for each x ∈ A. Note that we must insist in advance that f be a local homeomorphism since without making that requirement explicit, an increasing germ from G_{x,f(x)}^{+} might be combined with a decreasing germ from G_{x,f(x)}^{−} or the reverse. We denote the groupoid of germs of all (G; A)-compatible functions by (G; A). We let F (G; A) be the set of all (G; A)-compatible maps, and we let H(G; A) be the set of all (G; A)-compatible homeomorphisms. The constructions in this paragraph can be compared to Paragraph 1.6 in [13].

Note that (x, y) ↦ Aff_{n}(R)_{x,y} defines a groupoid of germs on R. To avoid ambiguities of notation, we use A_{n}(R) rather than Aff_{n}(R) to denote this groupoid. Now if A = Z[\frac{1}{n}], then

H(A_{n}(R)) = Aff_{n}(R),
H(A_{n}(R); A) = P L_{n}(R), and
F (A_{n}(R); A) = \overline{P L}_{n}(R).

We now consider the circle S_{r} and its covering map, the projection R → R/rZ. If G is a groupoid of germs on S_{r}, then we can lift G to a groupoid of germs on R. One way to define this is to let P be the set of germs of the covering projection R → R/rZ and let P^{−1} be the inverses of the elements of P. Then the lift of G to R is the set of all allowable compositions in P^{−1}GP. We can build a groupoid of germs A_{n}(S_{r}) on S_{r} that lifts to A_{n}(R) on R. We can be precise about this too. Here we are going from R to S_{r}, so let G be a groupoid of germs on R, and let s : R → R be defined by s(x) = x + r. We say that G is s-invariant if the germ of s^{q}αs^{−p} at x + pr is in G_{x+pr,y+qr} for every germ α in G_{x,y} and every p and q in Z. If G contains the identity, then the s-invariance of G is equivalent to the requirement that s be in H(G). This is seen by noting that the germ of s at x is the germ of s^{1}αs^{0} at x where α is the germ of the identity at x. Assuming that G is s-invariant, we can now let the projection of G onto S_{r} be the set of all allowable compositions in PGP^{−1} . Since s is in A_{n}(R), we let A_{n}(S_{r}) be the projection of A_{n}(R) onto S_{r}. The set of A_{n}(S_{r})-compatible maps that are defined on all of S_{r} is the monoid generated by the map ν_{n}(x) = nx and the rotations by elements of Z[\frac{1}{n}]. If A = Z[\frac{1}{n}], then

\begin{aligned}H(A_{n}(S_{r}); A) & = T_{n,r}, and \\ F (A_{n}(S_{r}); A) & = \overline{T}_{n,r}. \end{aligned}

We now consider how little information is needed to specify a set of germs. Consider the map ν_{n}(x) = nx on the circle S_{1} . We represent the elements of S_{1} as words (3-2) where all a_{i} = 0 for positive i. The action of ν_{n} on these words is to shift the entire word one letter to the left and to discard (replace with zero) the letter that passes to the left of the n-ary point. From this we see that if x and y satisfy (3-3), then there are non-negative integers a and b so that ν_{n}^{a}(x) = ν_{n}^{b}(y). The converse is clear and we see that (3-3) captures not the orbits of ν_{n} but the symmetric, transitive closure of the orbits of ν_{n}. The non-negative powers of ν_{n} form a semigroup (the word monoid leads to a phonetically unacceptable result) and so the germs of ν_{n} could be called a semigroupoid. Since ν_{n} is a local homeomorphism, we have that the germs of ν_{n} are all invertible and in fact the groupoid of germs A_{n}(S_{1}) is the smallest groupoid that contains the germs of ν_{n}. (We do not need this exact statement, and the suspicious reader can wait for the more precise statement and proof of Lemma 6.4.) We refer to this by saying that ν_{n} generates A_{n}(S_{1}). We can abuse notation a bit and regard ν_{n}(x) = nx as a function on R. If we let τ(x) = x + 1 on R, then we have that A_{n}(R) is generated by the pair of functions ν_{n} and τ. (This will not be needed.)

We become more formal. Let X be a topological space. Let F be a collection of local homeomorphisms defined on open subsets of X. Note that the set of germs of F is a subset of the collection of germs in G(X). Thus compositions of germs of F and inverses of germs of F exist in G(X). Standard arguments show that the collection of finite (allowable) compositions of germs from F and their inverses is a groupoid and is thus the smallest groupoid that contains the germs of F. We refer to this groupoid as the groupoid of germs generated by F. The orbits of the groupoid of germs generated by F are the equivalence classes of the symmetric, transitive closure of the relation that is defined by declaring x ∼ y if there is a non-negative integer a and an f ∈ F so that y = f^{a}(x). The following is clear.

Lemma 3.1. Let X be a topological space and let F and F_{1} be collections of local homeomorphisms defined on open subsets of X.

(i) If F ⊆ F_{1} , then the groupoid of germs generated by F is contained in the groupoid of germs generated by F_{1} .

(ii) If F_{c} is the set of finite compositions of elements of F, or if F_{c} is a group and F is a set of generators of F_{c}, then the groupoid of germs generated by F_{c} equals the groupoid of germs generated by F.

We need a definition to state the next lemma. If G is a groupoid of germs on a topological space X, then we say that a homeomorphism h : X → X preserves G under conjugation if hfh^{−1} is in F (G) for all f ∈ F (G). Note that this implies that hfh^{−1} is in H(G) for all f ∈ H(G).

Lemma 3.2 (Consistency). Let F be a family of local homeomorphisms on a topological space X and let G be the groupoid of germs generated by F. Let h : X → X be a homeomorphism and assume that h conjugates each element of F into F (G). Then h preserves G under conjugation. If in addition, X is one of S_{r} or R, A is a union of orbits in O(G), h(A) ⊆ A, and h conjugates each element of F into F (G; A), then h preserves (G; A) under conjugation.

Proof: We give the argument that applies when X is R or S_{r}, and let the reader omit the irrelvant parts for the simpler case. Let f be in F (G; A). If x ∉ A, then h^{−1}(x) ∉ A and the germ of f at h^{−1}(x) is a composition of a finite number of germs or their inverses from elements of F. If x ∈ A, then h^{−1}(x) might be in A or not. If not, then the previous statement about f applies. If h^{−1}(x) ∈ A, then the two half germs of f at h^{−1}(x) are compositions of corresponding half germs from F. (Which half germ of each factor goes into each half germ of f depends on the order in which the factors are orientation reversing or preserving.) The conjugate of the composition is the composition of the conjugates. Since the conjugate of each factor is known to have its germ or two half germs in (G; A), we have that hfh^{−1} is in F (G; A).

The notation (G; A) refers not only to a groupoid, but also emphasizes its construction. We could use a simpler notation (a single letter, for example) to refer to the groupoid so constructed. For the remainder of the section, we will not be concerned with the construction of groupoids and notations like (G; A) will not be needed.

The hypothesis of the next corollary is implied by a stronger condition that we will introduce later.

Corollary 3.2.1. Let G be a groupoid of germs on a topological space X and assume that H(G) generates G. If h : X → X is a homeomorphism for which hH(G)h^{−1} ⊆ H(G), then h preserves G under conjugation.

If G is a groupoid of germs, then G_{x,x} is the set of germs at x of those elements of F (G) that have x as a fixed point. The following standard observation will be needed in several places.

Lemma 3.3. Let X be a topological space and let G be a groupoid of germs on X that contains the identity. Then each G_{x,x} is a group. If h : X → X is a homeomorphism and h and h^{−1} preserve G under conjugation, then the function from G_{x,x} to G_{h(x),h(x)} taking each α ∈ G_{x,x} to the germ of hαh^{−1} at h(x) is an isomorphism.

We can illustrate this with examples that we have been discussing. With A_{n}(R) the groupoid of germs generated by Aff_{n}(R) and A = Z[\frac{1}{n}], then (A_{n}(R); A)_{x,x} is isomorphic to Z×Z if x ∈ Z[\frac{1}{n}], to Z if x ∈ Q−Z[\frac{1}{n}], and to \{1\} if x ∉ Q. Thus any homeomorphism h : R → R that normalizes F (A_{n}(R); A) must preserve the three sets, Z[\frac{1}{n}], Q − Z[\frac{1}{n}] and R − Q.

Let X be a topological space, let G be a groupoid of germs on X, and let H(X) be the set of self homeomorphisms of X. We say that g ∈ H(X) is obtained from f ∈ H(X) by G-rearrangement if for every x ∈ X, the germ of g at x is that of αfβ where α and β are germs in G that vary with x. Note that this relation does not seem to be symmetric. This relation becomes more symmetric when we consider normalizers. We let N(G) be the set of h ∈ H(X) so that both h and h^{−1} preserve G under conjugation. Note that H(G) is a normal subgroup of N(G).

Lemma 3.4 (Rearrangement). Let X be a topological space and let G be a groupoid of germs on X that contains the identity. If f and g in H(X) are in the same left coset of H(G) in H(X) or the same right coset of H(G) in H(X), then each is a G-rearrangment of the other. If h is in N(G), then any G-rearrangement of h is in N(G) and elements of N(G) are in the same coset of H(G) in N(G) if and only if they are G-rearrangements of each other.

Proof: If g = fH(G), then g = fh with h ∈ H(G). This and a similar observation for right cosets finishes the first claim. If h is in N(G), g is a G-rearrangement of h and f is in F (G), then the composition of germs

gfg^{−1} = (αhβ)f(α′hβ′)^{−1}

shows that gfg^{−1} is in F (G) as well. We know that elements of the same coset of H(G) in N(G) are G-rearrangements of each other. Now if g and h in N(G) satisfy g = αhβ at each x for some germs α and β that vary with x, then gh^{−1} = αhβh^{−1} at each x, and h ∈ N(G) implies that gh^{−1} ∈ F (G) and thus in H(G), and g and h are in the same coset of H(G) in N(G).

We borrow a property from the study of foliations. Let G be a groupoid of germs on R. We say that G is interpolating if for every pair of germs α ∈ G_{a,b} and β ∈ G_{c,d} with both α and β increasing, with a < c and with b < d, there is an f ∈ F (G) with α the germ of f at a and β the germ of f at c. This is condition (γ) in [20] and is called germ-connected in [13].

Lemma 3.5. Let G be an interpolating groupoid of germs on R that contains the identity. Then for every pair of germs α ∈ G_{a,b} and β ∈ G_{c,d} with both α and β increasing, with a < c and with b < d, there is an h ∈ H(G) with α the germ of h at a and β the germ of h at c.

Proof: There is an f ∈ F (G) with α the germ of f at a and β the germ of f at c. For some x with x < a and x < b there is a g_{1} ∈ F (G) with α the germ of g_{1} at a and with the germ of g_{1} at x the germ of the identity. For some y with y > c and y > d there is a g_{2} ∈ F (G) with β the germ of g_{2} at c and with the germ of g_{2} at y the germ of the identity. Now let

h(t) = \{ \begin{matrix}t & t ≤ x, \\ g_{1}(t) & x ≤ t ≤ a, \\ f(t) & a ≤ t ≤ b, \\ g_{2}(t) & b ≤ t ≤ y, \\ t & y ≤ t. \end{matrix}

Corollary 3.5.1. If G is an interpolating groupoid of germs on R that contains the identity, then H(G) generates G.

Lemma 3.6 (Reduction). Let G be an interpolating groupoid of germs on R that contains the identity and is s-invariant with respect to the map s(x) = x + r. Let G′ be the projection of G on S_{r}. Then there is a natural isomorphism from N(G)/H(G) to N(G′)/H(G′).

Proof: Let h be in N(G). We wish to find a function g in the same coset of H(G) in N(G) so that g is a lift of a homeomorphism of S_{r}. Note that if g is increasing this means that we want g to commute with s. However, if g is decreasing, we want g to satisfy g = sgs.

We know that hsh^{−1} is in H(G), as are shs^{−1}h^{−1} and shsh^{−1} . Also, shs^{−1}h^{−1} and shsh^{−1} are increasing no matter what the behavior of h is.

If h is increasing, then h(0) < h(r) and we let a = h(0) and c = h(r). Now (shs^{−1}h^{−1})(h(r)) = h(0) + r and if we let b = h(0) and d = h(0) + r, then we have a < c and b < d. There is an f in H(G) whose germ at h(0) is that of the identity and whose germ at h(r) is that of shs^{−1}h^{−1} . Now fh takes 0 to h(0) with the germ of h at 0 and takes r to h(0) + r with the germ of shs^{−1} at r. Since the germ of (fh) at r is the germ of s(fh)s^{−1} at r, we can build a function g in H(G) that agrees with fh on [0, r] and that commutes with s on all of R. Specifically, g on [ir, (i + 1)r] is defined to be s^{i}(fh)s^{−i}. Slightly to the left of ir, the behavior of g is that of s^{i−1}(fh)s^{−i+1} with the relevant part of fh being that in a small neighborhood of r. But here we have fh = s(fh)s^{−1} so the behavior of g to the left of ir is also that of s^{i}(fh)s^{−i} which agrees with the behavior of g to the right of ir. Thus g is G-compatible at each ir. It is also G-compatible in the interior of each [ir, (i + 1)r] since G is s-invariant.

If h is decreasing, then h(r) < h(0) and we let a = h(r) and c = h(0). Now (shsh^{−1})(h(0)) = h(r) + r and if we let b = h(r) and d = h(r) + r, then we have a < c and b < d. There is an f in H(G) whose germ at h(r) is that of the identity and whose germ at h(0) is that of shsh^{−1} . Now fh takes r to h(r) with the germ of h at r and takes 0 to h(r) + r with the germ of shs at 0. The rest of the argument is similar to the paragraph above except we define g on [−ir, −(i − 1)r] to be s^{i}fs^{i} and get a decreasing function that satisfies sgs = g.

In both cases, we get a function that defines a homeomorphism on S_{r} = R/rZ. This function is in the same coset as h since it is a G-rearrangement. We must show that another function g′ in the same coset as h that has sg′s^{−1} = g′ if g′ is increasing or sg′s = g′ if g′ is decreasing has the projection of g′ to S_{r} in the same coset as the projection of g. We know that g^{−1}g′ is in H(G). Now g′ is increasing if and only if g and h are increasing. If g and g′ are increasing, then g^{−1}g′ = sg^{−1}s^{−1}sg′s^{−1} = sg^{−1}g′s^{−1} and g^{−1}g′ projects to S_{r} and shows that the projection of g and g′ are in the same coset of H(G′). If h and g′ are decreasing, then g^{−1}g′ = s^{−1}g^{−1}s^{−1}sg′s = s^{−1}g^{−1}gs and the same conclusion holds.

The map clearly defines a homomorphism. We want to show that the function is one to one and onto. It is onto by lifting representatives of N(G′)/H(G′) to R. Such lifts are in N(G) since G is s-invariant. It is one to one, since if h projects to a G′ -compatible homeomorphism of S_{r}, then h is G-compatible.

4. Normalizers and germs of Thompson’s groups.

One of the goals in the paper is to show that non-PL homeomorphisms do not normalize the groups that we consider. We first reduce this to a study of normalizers of a small set of groups, and then show that we need only study conjugates of a small set of function. To do the first step, we need to compare the normalizers of the various groups. The next lemma starts this process.

Lemma 4.1. Let G be a group or monoid for which BP L_{n}(R) ⊆ G ⊆ ˜ \overline{P L}_{n}(R) or BT_{n,r} ⊆ G ⊆ ˜ \overline{T}_{n,r}. Then N(G) ⊆ N(BP L_{n}(R)) or N(G) ⊆ N(BT_{n,r}) whichever applies.

Proof: Conjugation preserves the properties of being invertible, being orientation preserving, having bounded support, and being the identity on an open interval.

We now know that the existence of a non-PL normalizer for any G considered in Lemma 4.1 implies the existence of a non-PL element in either N(BP L_{n}(R)) or N(BT_{n,r}). We wish to reduce the set of normalizers to consider to just the normalizers N(BT_{n,n−1}). The order of analysis is to first compare N(BT_{n,r}) to N(BP L_{n}(R)), and then compare N(BP L_{n}(R)) to N(BT_{n,n−1}).

We will work with groupoids of germs. Let B_{n,r} be the groupoid of germs generated by the group BT_{n,r}. Let B_{n} be the groupoid of germs generated by the group BP L_{n}(R). From Lemma 2.5, we have H(B_{n}) = ker(d_{n}). Let P_{n} be the groupoid of germs generated by the group P L_{n}(R). We have H(P_{n}) = P L_{n}(R). The groupoid P_{n} was identified in Section 3 as (A_{n}(R); Z[\frac{1}{n}]), but we will not need this fact and will use the simpler notation. Let B̃_{n,r} be the lift of B_{n,r} to R.

Lemma 4.2. We have the containments

B_{n} ⊆ B̃_{n,r} ⊆ P_{n}

and the equality

B_{n} = B̃_{n,n−1}.

Proof: We get B̃_{n,r} ⊆ P_{n} because all lifts of elements of BT_{n,r} are elements of P L_{n}(R). The germs of the generators mentioned in Lemma 2.6 are contained in the germs of lifts of the generators mentioned in Lemma 2.7. The containment B_{n} ⊆ B̃_{n,r} now follows from Lemma 3.1.

The translation x ↦ x + (n − 1) preserves Δ_{n} and so (using the notation of Lemma 2.7) p_{n−1}^{−1}(p_{n−1}(Δ_{n})) = Δ_{n}. This and Lemma 2.7 imply that all lifts to R of elements of BT_{n,n−1} preserve Δ_{n}. Now Lemma 2.5 gives B̃_{n,n−1} ⊆ B_{n}.

We now can compare N(BT_{n,r}) to N(BP L_{n}(R)). Let Ñ(BT_{n,r}) be the set of all lifts to R of elements of N(BT_{n,r}).

Lemma 4.3. We have Ñ(BT_{n,r}) ⊆ N(BP L_{n}(R)).

Proof: Let B̃T_{n,r} be the set of lifts to R of the elements of BT_{n,r}. We know that the elements of Ñ(BT_{n,r}) normalize B̃T_{n,r}. However B̃T_{n,r} generates B̃_{n,r}, so Ñ(BT_{n,r}) normalizes H(B̃_{n,r}). We have

B_{n} ⊆ B̃_{n,r} ⊆ P_{n}

and thus

BP L_{n}(R) ⊆ H(B_{n}) ⊆ H(B̃_{n,r}) ⊆ H(P_{n}) = P L_{n}(R).

So elements of Ñ(BT_{n,r}) conjugate BP L_{n}(R) into P L_{n}(R). We now repeat the arguments in the proof of Lemma 4.1.

To compare the normalizers of BP L_{n}(R) and BT_{n,n−1} we need to know more about the groupoid of germs B_{n}.

Lemma 4.4.

(i) B_{n} contains the identity.

(ii) B_{n} is s-invariant where s(x) = x + (n − 1).

(iii) B_{n} is interpolating.

Proof: We get (i) and (ii) from the fact that the identity and s are in H(B_{n}) = ker(d_{n}). To see (iii) we let a < c and b < d where (B_{n})_{a,b} and (B_{n})_{c,d} are non-empty. Given α ∈ (B_{n})_{a,b} and β ∈ (B_{n})_{c,d}, we can get a < a′ < c′ < c where a′ and c′ are in Δ_{n} and [a, a′] is in the domain of some representative f of α and [c′, c] is in the domain of some representative g of β. We know that f and g preserve Δ_{n}. Now Lemma 2.3 allows us to fill the missing part on [a′, c′].

Corollary 4.4.1. We have N(B_{n})/H(B_{n}) ≃ N(B_{n,n−1})/H(B_{n,n−1}). In particular, if there is a non-PL normalizer of BP L_{n}(R), then there is a non-PL normalizer of BT_{n,n−1} .

Proof: The isomorphism follows from Lemmas 3.6, 4.2 and 4.4.

Corollary 4.4.2. Let G be a group or monoid for which BP L_{n}(R) ⊆ G ⊆ ˜ \overline{P L}_{n}(R) or BT_{n,r} ⊆ G ⊆ ˜ \overline{T}_{n,r}. If there is a non-PL normalizer of G, then there is a non-PL normalizer of BT_{n,n−1} .

Proof: From Lemma 4.1, there is a non-PL element in either N(BP L_{n}(R)) or N(BT_{n,r}). From Lemma 4.3, there is a non-PL element of N(BP L_{n}(R)). Corollary 4.4.1 finishes the argument.

Let ν_{n} : S_{n−1} → S_{n−1} be the degree n map defined by ν_{n}(x) = nx. It is an element of \overline{T}_{n,n−1} . It also preserves p_{n−1}(Δ_{n}) and so lies in F (B_{n,n−1}).

Lemma 4.5. Let G be a group or monoid for which BP L_{n}(R) ⊆ G ⊆ ˜ \overline{P L}_{n}(R) or BT_{n,r} ⊆ G ⊆ ˜ \overline{T}_{n,r}. If there is a non-PL normalizer of G, then there is a non-PL homeomorphism h : S_{n−1} → S_{n−1} for which h(Z[\frac{1}{n}]) = Z[\frac{1}{n}] and for which hν_{n}h^{−1} and h^{−1}ν_{n}h are in \overline{T}_{n,n−1} .

Proof: By Corollary 4.4.2, there is a non-PL normalizer h of BT_{n,n−1} . Since x ↦ −x normalizes BT_{n,n−1} , we can assume that h preserves orientation. Since the groups of germs (B_{n,n−1})_{x,x} at fixed points of functions in BT_{n,n−1} are isomorphic to Z × Z when x ∈ Z[\frac{1}{n}], while at all other points these groups are isomorphic to Z or are trivial, we have that h(Z[\frac{1}{n}]) = Z[\frac{1}{n}] from Lemma 3.3. We have ν_{n} ∈ F (B_{n,n−1}) ⊆ \overline{T}_{n,n−1} and BT_{n,n−1} generates B_{n,n−1} . By Lemma 3.2, we get the last items of the statement.

5. Realizing automorphisms.

In this section we show that the automorphisms of the groups that we consider are all realized as conjugations by homeomorphisms. This follows from very general results in the theory of ordered groups. Our task is simply that of verifying the hypotheses. We also show that automorphisms of the monoids that we consider are realized as conjugations by homeomorphisms. The arguments simply reduce this to the group case.

We need hypotheses that define sufficient levels of transitivity for groups acting on R or S^{1} . For a group acting on R, we use the notion of o-k -transitivity defined in Section 2. We need a different definition on S^{1} . Let G be a group that acts on S^{1} by homeomorphisms. We say that a closed interval (arc) is proper in S^{1} if it and its complement have nonempty interior. We say that G is approximately arc transitive if for all proper arcs I, J_{1} , J_{2} in S^{1} , with J_{1} ⊆ J̊_{2} , there is a g ∈ G so that J_{1} ⊆ g(I) ⊆ J_{2} . Note that if G is approximately o-3-transitive (where “o” refers to preserving orientation), then G is approximately arc transitive. Recall that a homeomorphism of S^{1} has bounded support if it fixes some open interval. Most of the work in this section is taken care of in the following theorem from [18].

Theorem 5.1 (McCleary-Rubin). Let G act on R or S^{1} by homeomorphisms. Assume that G contains a non-identity element of bounded support. If G acts on R, then assume that the action is approximately o-2-transitive, and if G acts on S^{1} , then assume that the action is approximately arc transitive. Then for each automorphism α of G, there is a unique self homeomorphism h of R or S^{1} (whichever is appropriate) so that α(f) = hfh^{−1} for every f ∈ G.

We will use this to demonstrate provision (i) of Theorem 1. Specifically, we will show:

Theorem 1. Let G be a group or monoid for which BP L_{n}(R) ⊆ G ⊆ ˜ \overline{P L}_{n}(R) or BT_{n,r} ⊆ G ⊆ ˜ \overline{T}_{n,r}. If G is not a group, then assume G is determined by its invertible elements. Then

(i) Φ : N(G) → Aut(G) is an isomorphism.

The first step is to show:

Theorem 5.2. Let G be a group for which BP L_{n}(R) ⊆ G ⊆ ˜ \overline{P L}_{n}(R) or BT_{n,r} ⊆ G ⊆ ˜\overline{T}_{n,r}. Then Φ : N(G) → Aut(G) is an isomorphism.

Proof: That G satisfies the hypotheses of Theorem 5.1 follows from the results in Section 2. The existence and uniqueness statements in Theorem 5.1 show that Φ is one to one and onto.

We use Theorem 5.2 in the proof of the next theorem which handles the case in which G is a monoid.

Theorem 5.3. Let M be a monoid for which BP L_{n}(R) ⊆ M ⊆ ˜ \overline{P L}_{n}(R) or BT_{n,r} ⊆ M ⊆ ˜ \overline{T}_{n,r} and assume M is determined by its invertible elements. Then Φ : N(M) → Aut(M) is an isomorphism.

Proof: Note that the group of invertible elements in M satisfies the hypotheses of Theorem 5.2. We will refer to this group as G(M). If ϕ is an automorphism of M, then ϕ|_{G(M)} is an automorphism of G(M). By Theorem 5.2, there is an h ∈ Homeo(X) so that ϕ|_{G(M)} is realized as conjugation by h. By Corollary 3.2.1, Φ(h) is an automorphism of M. If we form the composition (Φ(h))^{−1} ∘ ϕ, then we have an automorphism of M that is the identity on G(M). We are done if we show that (Φ(h))^{−1} ∘ ϕ is the identity on all of M. We thus reduce the problem and assume that ϕ is an automorphism on M that is the identity on G(M). Our task is to show that ϕ is the identity on M.

We focus on P, the set of restrictions of the identity to open subsets of X. These are all in M because M is determined by its invertible elements, among which is the identity of M. All the elements of P are idempotents of M, α ∈ P implies αα = α, but they are not all the idempotents. We wish to distinguish P from the other idempotents. For α ∈ P, if fα = α, then f must the identity on the domain of α and is arbitrary off the domain. If f is invertible, then it must preserve the complement of the domain of α. This will give αf = α. Thus every invertible left identity of α is a right identity of α. Now suppose that β is an idempotent that has β(x) ≠ x for some x. There is an open set U about x in the domain of β for which β(U) ∩ U = ∅. By further restricting U, we can assume that β is one to one on U. If some y ∈ U is in the range of β, then y = β(z) and

y ≠ β(y) = β(β(z)) = β(z) = y

so U is disjoint from the range of β. Using the transitivity properties of G(M), we can build an invertible g in M that is the identity on the range of β and takes x to some point w ∈ U with x ≠ w. Since g is the identity on the range of β it is a left identity for β. But if g is also a right identity for β, then we get β(x) = β(g(x)) = β(w). With both x and w in U on which β is one to one, we get x = w. Thus g cannot be a right identity for β. Since we have characterized the elements of P using the operation in M, we have that ϕ(P) = (P).

We want to argue that ϕ is the identity on P. An element of P is identified by its domain. For α ∈ P, let D(α) be the closure of the domain of α. Assume that D(α) and D(ϕ(α)) are different. Assume first that D(ϕ(α)) has points that are not in D(α). Thus the domain of ϕ(α) has a point x not in D(α) and there is an open set U about x in the domain of ϕ(α) that is disjoint from D(α). Thus we can build an invertible element g in M that is the identity on D(α) but has g(x) ≠ x. Recall that α and ϕ(α) are the identities on their domains. Since g is invertible, it is fixed by ϕ and since g is the identity on D(α) we get gα = α. Thus ϕ(α) = ϕ(gα) = ϕ(g)ϕ(α) = gϕ(α). This says that x = ϕ(α)(x) = gϕ(α)(x) = g(x) ≠ x. Thus D(ϕ(α)) ⊆ D(α). By working with ϕ^{−1} we also get D(α) ⊆ D(ϕ(α)) and so we must have D(ϕ(α)) = D(α).

Now let d(α) be the domain of α ∈ P. Assume that d(α) contains a point x that is not in d(ϕ(α)). By the transitivity properties of G(M) and since d(α) is an open set, we can build an invertible element g of M whose support lies in d(α) and for which g(x) ≠ x. Now ϕ(α) is not defined on x, so ϕ(α)g^{−1} cannot be defined on g(x). Because the support of g lies in d(α), so does the support of g^{−1} , and we have gαg^{−1} = α. Since g and g^{−1} are invertible, we have ϕ(g) = g, ϕ(g^{−1}) = g^{−1} and

ϕ(α) = ϕ(gαg^{−1}) = gϕ(α)g^{−1}.

But the right hand expression is not defined on g(x) so neither is ϕ(α). Since we can build sufficiently varied invertible elements g in M to carry x to a dense subset of d(α), we get that ϕ(α) is not defined on a dense subset of d(α). The domain of ϕ(α) is an open set, so we now know that d(ϕ(α)) is disjoint from d(α). But we showed that d(α) and d(ϕ(α)) have identical closures, so we must have d(α) ⊆ d(ϕ(α)). Again, by working with ϕ^{−1} we get that d(ϕ(α)) ⊆ d(α). We have shown that ϕ preserves the domains of the elements of P, and from this it follows that ϕ fixes the elements of P.

We can use elements of P to identify domains. We have an order on elements of P given by subset on the domains. This is captured by the monoid operation by saying that f and g in P are related by f ≤ g if and only if gf = fg = f. We can now identify the domain of an element h in M as the minimum f in P that satisfies hf = h. Now that we know that ϕ fixes elements of P, we know that ϕ preserves domains in that for h in M, the domain of ϕ(h) equals the domain of h.

We can use subsets of P to identify values of functions. Let x be in X and let U_{x} = {f ∈ P | f(x) is defined}. Let h be in M with x in the domain of h. The statement that h(x) = y is equivalent to the statement that for all f ∈ U_{x} and all g ∈ U_{y}, ghf is not the empty function. Since the empty function is a zero (it is absorbing under composition on either side with all functions) it is determined by the operations. Since ϕ fixes the empty function and all the elements of P, it preserves the statement h(x) = y in that ϕ(h)(x) = y for all x ∈ X and all h ∈ M. Thus ϕ is the identity on M which is what we wanted to show.

Part III. PL normalizers

6. Proof of Theorems 1 and 2 from Theorem 3.

It is the goal of this section to prove Theorems 1 and 2 and Corollary 2.1 assuming Theorem 3. These implications are true even when n is not restricted to 2. It is only in the proof in Part IV of Theorem 3 that we need to assume n = 2. We restate Theorems 1, 2, Corollary 2.1 and Theorem 3 for arbitrary n. We call these “Statements” since only the implications between them are known to be true. We also show the “equivalence” of Theorem 2 and Corollary 2.1 by showing that Statement 2.1′ implies Statement 2′ when n = 2.

Statement 1′. Let G be a group or monoid for which BP L_{n}(R) ⊆ G ⊆ ˜ \overline{P L}_{n}(R) or BT_{n,r} ⊆ G ⊆ ˜ \overline{T}_{n,r}. If G is not a group, then assume G is determined by its invertible elements. Then

(i) Φ : N(G) → Aut(G) is an isomorphism, (ii) N(G) ⊆ P̃ L_{n}(R) or N(G) ⊆ T̃_{n,r} whichever applies, (iii) the containment is equality if G is one of BP L_{n}(R), P L_{n}(R), P̃ L_{n}(R), \overline{P L}_{n}(R),

˜\overline{P L}_{n}(R), BT_{n,r}, T_{n,r}, T̃_{n,r}, \overline{T}_{n,r}, or ˜ \overline{T}_{n,r}, and (iv) if N_{o}(F_{n}) represents the index 2 subgroup of N(F_{n}) of orientation preserving ele-

ments, then there is an exact sequence

1 → F_{n} → N_{o}(F_{n}) → T_{n,n−1} × T_{n,n−1} → Z_{n−1} → 1.

Statement 2′. Let h : S_{n−1} → S_{n−1} be an orientation preserving homeomorphism for which h(Z[\frac{1}{n}]) = Z[\frac{1}{n}], and assume that hν_{n}h^{−1} and h^{−1}ν_{n}h are both in \overline{T}_{n,n−1} . Then h ∈ T_{n,n−1} .

Statement 2.1′. Let h : S_{n−1} → S_{n−1} be an orientation preserving homeomorphism that fixes the images of Z in S_{n−1} , and assume that hν_{n}h^{−1} and h^{−1}ν_{n}h are both in \overline{T}_{n,n−1} . Then h ∈ T_{n,n−1} .

Statement 3′. Let h : S_{n−1} → S_{n−1} be an orientation preserving homeomorphism for which h(Z[\frac{1}{n}]) = Z[\frac{1}{n}], and assume that hν_{n}h^{−1} and h^{−1}ν_{n}h are both in \overline{T}_{n,n−1} . Then h is PL.

For the rest of this section, we assume the truth of Statement 3′. From Lemma 4.5, we know the following.

Statement 6.1. Let G be a group or monoid for which BP L_{n}(R) ⊆ G ⊆ ˜ \overline{P L}_{n}(R) or BT_{n,r} ⊆ G ⊆ ˜ \overline{T}_{n,r}. Then every element in the normalizer of G is PL.

Proof of Statement 1′ from Statement 3′: Part (i) is proven in Section 5. From Lemmas 4.1 and 4.3, we know that if we prove that N(BP L_{n}(R)) ⊆ P̃ L_{n}(R), then we can conclude that N(G) ⊆ P̃ L_{n}(R) or N(G) ⊆ T̃_{n,r} for the objects G covered in the lemmas. This will prove Part (ii) of Statement 1′. Thus we must prove:

Statement 6.2. N(BP L_{n}(R)) ⊆ P̃ L_{n}(R).

Proof assuming Statement 3′: Let h be an element of N(BP L_{n}(R)). As argued in the proof of Lemma 4.5, we know that h(Z[\frac{1}{n}]) = Z[\frac{1}{n}]. Given any interval on which h is affine, there are a pair of elements of Z[\frac{1}{n}] in the interval whose distance apart is in integral power of n. Since the images of these two points are in Z[\frac{1}{n}], the distance between the images is in Z[\frac{1}{n}], and the slope of h on the interval must have an integral power of n for the denominator. The discussion also applies to h^{−1} , and it follows that the slope is an integral power of n. This completes the proof of the this statement and Part (ii) of Statement 1′.

The proof of Part (iii) of Statement 1′ is one of checking that P̃ L_{n}(R) and T̃_{n,r} normalize the groups listed. This is quite easy and is left to the reader.

We consider (iv) of Statement 1′. We know that N(F_{n}) ⊆ P̃ L_{n}(R). Let f be in N_{o}(F_{n}), the orientation preserving elements of N(F_{n}). The germ of F_{n} at −∞ is isomorphic to Z generated by translation to the right or left by (n − 1). A normalizer must preserve the germ at −∞ and so must take a generator to a generator. (This is identical to the concept discussed in Lemma 3.3.) An orientation preserving conjugator will take a right translation to a right translation. Thus near −∞, an orientation preserving normalizer commutes with translation to the right by (n−1). This forces f(x+n−1) = f(x)+(n−1) near −∞. Similarly, we get f(x + n − 1) = f(x) + (n − 1) near +∞. Conversely, any f in P L_{n}(R) that satsifies f(x + n − 1) = f(x) + (n − 1) near ±∞ conjugates elements of F_{n} into F_{n}. Thus we have characterized the elements of N_{o}(F_{n}). Now by restricting an f ∈ N_{o}(F_{n}) sufficently far to the left, we get a well defined element f_{−} of T_{n,n−1} . Similarly, the restriction of f near +∞ gives a well defined element f_{+} of T_{n,n−1} . The function f ↦ (f_{−}, f_{+}) is a homomorphism into T_{n,n−1} × T_{n,n−1} . The kernel consists of all elements of F_{n}.

We use the homomorphism d_{n} of Section 2 to understand the image of the homomorphism above. Each element g of T_{n,n−1} lifts to various elements of P L_{n}(R) that all have the same value of d_{n}. This gives a well defined meaning to d_{n}(g). Easy applications of Lemmas 2.2 and 2.3 show that two elements g_{1} and g_{2} of T_{n,n−1} will have the lift of g_{1} near −∞ and the lift of g_{2} near +∞ connectable into one function in P L_{n}(R) if and only if d_{n}(g_{1}) = d_{n}(g_{2}). Thus the image of the homomorphism is the kernel of (g_{1}, g_{2}) ↦ d_{n}(g_{1}) − d_{n}(g_{2}). This completes the proof of Statement 1′. Proof of Statement 2′ from Statement 3′: From Statement 1′, Part (ii), we are done when we show the truth of the following lemma.

Lemma 6.3. Let h : S_{n−1} → S_{n−1} be an orientation preserving homeomorphism for which h(Z[\frac{1}{n}]) = Z[\frac{1}{n}], and assume that hν_{n}h^{−1} and h^{−1}ν_{n}h are both in \overline{T}_{n,n−1} . Then h is in N(BT_{n,n−1}).

Remark: This lemma does not depend on Statement 3′, and is true for all n as stated. This lemma will also be important in the proof of Theorem 3 in Part IV. Proof: Let V_{n} be the groupoid of germs generated by the function ν_{n}. From Lemma 3.2, we know that h normalizes H(V_{n}; Z[\frac{1}{n}]). Recall that B_{n,n−1} is the groupoid of germs generated by BT_{n,n−1} . We have B_{n,n−1} ⊆ T_{n,n−1} where T_{n,n−1} is the groupoid of germs generated by T_{n,n−1} . Thus H(B_{n,n−1}) ⊆ H(T_{n,n−1}) = T_{n,n−1} . If we show that (V_{n}; Z[\frac{1}{n}]) = B_{n,n−1} , then we have that h normalizes a group G with BT_{n,n−1} ⊆ G ⊆ T_{n,n−1} , and by Lemma 4.1, we are done. Thus we must show the following.

Lemma 6.4. (V_{n}; Z[\frac{1}{n}]) = B_{n,n−1} .

Proof: Since translation by n − 1 preserves Δ_{n}, we have that the ring homomorphism ϕ_{n} : Z[\frac{1}{n}] → Z_{n−1} makes sense on S_{n−1} . Since ν_{n} is just a shift of the expression x = a_{j}a_{j−1} … a_{0}.a_{−1}a_{−2} … as in (3-2), it commutes with ϕ_{n} and preserves p_{n−1}(Δ_{n}). Combining this with Lemma 2.7 gives V_{n} ⊆ B_{n,n−1} . It follows from Lemma 2.5 that arbitrary changes of slope of elements of BT_{n,n−1} can occur at elements of Z[\frac{1}{n}]. This puts (V_{n}; Z[\frac{1}{n}]) ⊆ B_{n,n−1} .

Since (V_{n}; Z[\frac{1}{n}]) allows arbitrary changes of slope at elements of Z[\frac{1}{n}], we need only show that all linear parts of elements of BT_{n,n−1} are in V_{n}. If we are presented with a linear part of an element f of BT_{n,n−1} , then it is the restriction to an interval I of an affine map x ↦ xn^{k} +d where d ∈ Δ_{n}. We can assume that the interval I has an element a of Z[\frac{1}{n}] as a left endpoint. If f(a) = b, then we must show that (ν_{n})^{j}(a) = (ν_{n})^{k}(b) for some integers j and k so that (ν_{n})^{k} ∘f = (ν_{n})^{j} on I. This will make f|_{I} the composition of two germs in V_{n}. However, each of a and b have finite expression of the type in (3-2). The action of ν_{n} is to shift the expressions to the left and reduce modulo (n − 1). Under powers of ν_{n}, the expressions for a and b can be reduced to single integers which represent ϕ_{n}(a) and ϕ_{n}(b). Since f is in BT_{n,n−1} which preserves p_{n−1}(Δ_{n}), and lifts of f commute with ϕ_{n}, we have that ϕ_{n}(a) = ϕ_{n}(b) and thus have a common point in the forward orbit of ν_{n}. This completes the proof. Remark: The ideas behind Lemma 6.3, Corollary 4.4.2 and Lemma 4.5 motivated the approach taken in this paper. Lemma 6.3, Corollary 4.4.2 and Lemma 4.5 make it clear that if Statement 1′ were to fail, then it would be possible to find examples of this failure by investigating conjugates of the maps ν_{n}. Since the maps ν_{n} are expanding, the conjugators are determined by the conjugates.

We can give a separately worded result concerning rigidity. It is simply a translation of parts of Theorem 1 into other terminology. There is a corresponding statement for arbitrary n that would be true if Statement 3′ is true. Recall that B_{n,r}, T_{n,r}, B_{n} and P_{n} were defined as the groupoids of germs generated by BT_{n,r}, T_{n,r}, BP L_{n}(R) and P L_{n}(R) respectively. Recall from Section 3 that if G is a groupoid of germs on X, then a homeomorphism h : X → X preserves G under conjugation if hfh^{−1} is in F (G) for all f ∈ F (G). We say that h normalizes G if h and h^{−1} preserve G under conjugation.

Theorem 6.5. If an orientation preserving homeomorphism h : R → R normalizes B_{2} or P_{2} , then h is P_{2} -compatible. If an orientation preserving homeomorphism h : S_{1} → S_{1} normalizes B_{2,1} or T_{2,1} , then h is T_{2,1} -compatible.

Proof of Statement 2.1′ from Statement 2′: We must show h(Z[\frac{1}{n}]) = Z[\frac{1}{n}]. The fixed points of ν_{n} are the integer points in S_{n−1} . The preimages of the fixed points under powers of ν_{n} are exactly the points of Z[\frac{1}{n}] in S_{n−1} . By hypothesis, h fixes the fixed points of ν_{n}. Thus the conjugates of ν_{n} by h and h^{−1} also have their fixed points at the integer points of S_{n−1} and h and h^{−1} carry Z[\frac{1}{n}] (the preimages of the fixed points of powers ν_{n}) into the preimages of the fixed points of the powers of the conjugates. Since the conjugates of ν_{n} by h and h^{−1} are in T_{n,n−1} , we know that they preserve Z[\frac{1}{n}] and S_{n−1} − Z[\frac{1}{n}] so that the preimages of the fixed points of powers of the conjugates are all in Z[\frac{1}{n}]. Thus both h and h^{−1} carry Z[\frac{1}{n}] to Z[\frac{1}{n}].

Proof of Statement 2′ from Statement 2.1′ when n = 2: Let h be as in the hypothesis of Statement 2′. We are conjugating ν_{2} by a homeomorphism h and its inverse. The unique fixed point of ν_{2} is the point 0 in S_{1} . Since h(Z[\frac{1}{2}]) = Z[\frac{1}{2}], we know that the point 0 is taken to an element x of Z[\frac{1}{2}]. We know that rotation ρ by x is in T_{2,1} and thus normalizes \overline{T}_{2,1} . We are done if we show that ρ^{−1}h is in T_{2,1} . But this is true since ρ^{−1}h satisfies the hypotheses of Statement 2.1′.

Part IV. Non-PL normalizers — proof of Theorem 3

In this part we will prove:

Theorem 3. Let h : S_{1} → S_{1} be an orientation preserving homeomorphism for which h(Z[\frac{1}{2}]) = Z[\frac{1}{2}], and assume that hν_{2}h^{−1} and h^{−1}ν_{2}h are both in \overline{T}_{2,1} . Then h is PL.

We had hoped to prove:

Statement 3′. Let h : S_{n−1} → S_{n−1} be an orientation preserving homeomorphism for which h(Z[\frac{1}{n}]) = Z[\frac{1}{n}], and assume that hν_{n}h^{−1} and h^{−1}ν_{n}h are both in \overline{T}_{n,n−1} . Then h is PL.

All of the sections in this part except Section 11 apply to Statement 3′. Thus except for Section 11, we will give arguments that apply to all n and not just n = 2.

Our outline will be to extract as much information as possible about h from the fact that hν_{n}h^{−1} is in \overline{T}_{n,n−1} . Then, when n = 2, we will prove that h must be PL if h^{−1}ν_{n}h is PL. It might seem that we will only use that h^{−1}ν_{n}h is PL. However, we will also use Lemma 6.3 which uses the full hypothesis. We do not know if we can weaken the hypotheses of Theorem 3 so that we only assume that h^{−1}ν_{n}h is PL. See Example 2 and remarks in Section 13. The use of Lemma 6.3 will be crucial in our argument, and we point out that its conclusion allows us to assume throughout this part that h is a normalizer of BT_{n,n−1} . Since any rotation by an element of Z[\frac{1}{n}] is a normalizer of BT_{n,n−1} , we can compose h by a rotation through −h(0) to get an element satisfying the hypotheses that fixes 0 and that is PL if and only if h is. Thus throughout the rest of this part, we assume h(0) = 0.

For the remainder of this part we will let g = hν_{n}h^{−1} .

7. Markov partitions.

We can build a very nice Markov partition for g. It is derived from a Markov partition for ν_{n}. A Markov partition for the map ν_{n} with (n − 1)n^{k} intervals can be obtained by dividing S_{n−1} into the intervals [in^{−k}, (i+1)n^{−k}] for all integers i with 0 ≤ i < (n−1)n^{k}. The action of the map ν_{n} is to take each interval affinely onto the union of n consecutive intervals. We call this the standard Markov partition for ν_{n} of level k. The endpoints of these intervals are all in Z[\frac{1}{n}]. Given finitely many points in Z[\frac{1}{n}] we can realize them as a subset of the endpoints of such a partition by taking k large enough.

We can now apply h to the endpoints of these intervals and get a sequence of points in S_{n−1} that divide S_{n−1} into (n − 1)n^{k} intervals that form a Markov partition for g. We invent notation for these intervals by defining

(7-1)  I_{i}^{k} = h([in^{−k}, (i + 1)n^{−k}]).

We treat the subscripts cyclically modulo (n − 1)n^{k}. We let P^{k} denote the Markov partition itself. That is, P^{k} is the collection of intervals {I_{i}^{k} | 0 ≤ i < (n − 1)n^{k}}. Properties of the standard Markov partition of level k for ν_{n} are carried over by h to the partition P^{k}.

The action of ν_{n} on [in^{−k}, (i + 1)n^{−k}] is to take it affinely onto the union of [jn^{−k}, (j + 1)n^{−k}] for ni ≤ j < n(i + 1). The action of g on the intervals of P^{k} is to take I_{i}^{k} homeomorphically onto the union of I_{j}^{k} for ni ≤ j < n(i + 1). We argue that this action fails to be affine for only finitely many of these intervals. We know that h(Z[\frac{1}{n}]) = Z[\frac{1}{n}]. With g ∈ \overline{T}_{n,n−1} , we have the set D of break points of g (the set x on which g′(x) fails to exist) is a finite subset of Z[\frac{1}{n}]. The set h^{−1}(D) is a finite set in Z[\frac{1}{n}] and is in the set of endpoints for the standard Markov partition for ν_{n} of level k for some finite k. We let K be the smallest value of k for which this applies and we call this the stable level for g. We will need to refer to K repeatedly in what follows and the reason for the word stable will become clear later. We now have that the set D of breakpoints of g is contained in the set of endpoints of the intervals of P^{K}. This makes the action of g affine on each interval in P^{K}. The endpoints of P^{K} are among the endpoints of P^{k} for all k ≥ K. Thus the action of g affine on each interval in P^{k} for all k ≥ K.

We have Markov partitions P^{k} for g for every positive integer k. Each is obtained from the corresponding stardard Markov partition of level k for ν_{n} by applying h. We can also describe how each P^{k+1} is obtained from P^{k}. Each interval I_{i}^{k} is subdivided into n intervals I_{j}^{k+1} for ni ≤ j < n(i+1) by adding as new endpoints those point in the interior of I_{i}^{k} that are carried to the endpoints of I_{j}^{k} for ni ≤ j < n(i + 1). That is, we are pulling back the structure P^{k} locally by the action of g^{−1} . Since g is a local homeomorphism, this makes sense. We can thus refer to P^{k+1} as the partition derived from P^{k}.

When k ≥ K, the description gets simpler. Now, I_{i}^{k} is subdived into intervals I_{j}^{k+1} , ni ≤ j < n(i + 1), whose succession of lengths in increasing j are in proportion to the succession of lenghts in increasing j of the intervals I_{j}^{k}, ni ≤ j < n(i+1). This is because with k > K, the action of g on each of the intervals of P^{k} is affine.

Not only does g carry intervals of P^{k} onto unions of intervals of P^{k}, but we can describe how g carries intervals of one partition to intervals of another. We note that g carries I_{j}^{k+1} of P^{k+1} homeomorphically onto I_{j}^{k} of P^{k}. This action is affine if k + 1 ≥ K. Inductively, we get

(7-2)  g^{m} carries I_{j}^{k+m} of P^{k+m} homeomorphically onto I_{j}^{k} of P^{k}.

Again, the action is affine if k + 1 ≥ K (not just k + m ≥ K). Note that the subscripts of the intervals of P^{k} are treated cyclically modulo (n − 1)n^{k} and the subscripts of the intervals P^{k+m} are treated cyclically modulo (n − 1)n^{k+m}.

We develop more notation that will be needed later. Each I_{i}^{k} in P^{k} has two endpoints, and we label them so that

I_{i}^{k} = [x_{i}^{k}, x_{i+1}^{k}].

We use V P^{k} to denote the endpoints (vertices) of the partition P^{k}. Since endpoints of the partition P^{k} are also endpoints in all partitions P^{k+m}, we have V P^{k} ⊆ V P^{k+m} and we end up with multiple labels for the same points. Thus x_{i}^{k} = x_{in^{m}}^{k+m}. Note that since I_{i}^{k} = h([in^{−k}, (i + 1)n^{−k}]), we have

(7-3)  x_{i}^{k} = h(in^{−k}) = h(i/n^{k}).

We know that every x ∈ Z[\frac{1}{n}] is of such form and if x ∈ Z[\frac{1}{n}] has x = h(i/n^{k}) so that n ∤ i, then k is the least integer for which x ∈ V P^{k}. We call this the natural level of x and denote it λ(x). We can derive some information about λ(x).

Let x = h(i/n^{k}) so that n ∤ i and λ(x) = k. Since i/n^{k} is in S_{n−1} = R/(n − 1)Z, we can assume that 0 ≤ i/n^{k} < (n − 1). If i/n^{k} is expanded in base n as given in (3-2), then there will be no more than one non-zero numeral to the left of the n-ary point, and the number of non-zero numerals to the right of the n-ary point is exactly k = λ(x). If k = 0, then i/n^{k} = i is one of the integers 0 ≤ i < (n − 1). The action of ν_{n} on the expansion (3-2) is to shift the expression one position to the left and then reduce modulo (n − 1). If k = 0, then i/n^{k} = i is a fixed point of ν_{n} and λ(g(x)) = λ(x). Otherwise ν_{n}(i/n^{k}) has one less numeral to the right of the n-ary point than i/n^{k} and λ(g(x)) = λ(x) − 1. In general

(7-4)  λ(g^{m}(x)) is the larger of λ(x) − m or 0.

We can write down the orbits of an element of V P^{k}. If x ∈ Z[\frac{1}{n}] has x = h(i/n^{k}) = x_{i}^{k}, then the action of g on x is to take it to g(x) = h(ni/n^{k}) = h(i/n^{k−1}) = x_{ni}^{k} = x_{i}^{k−1} . The action of higher powers of g has

(7-5)  g^{m}(x_{i}^{k+m}) = x_{in^{m}}^{k+m} = x_{i}^{k}.

Again the subscripts are treated cyclically modulo a base that varies with the superscript. The natural level of an x changes by 1 with each appliation of g and eventually, the image of an x under powers of g reach level zero. The points of level zero are the images under h of the integers in S_{n−1} . The integers in S_{n−1} are the fixed points of ν_{n}, so their images under h are the fixed points of g. Thus each x = x_{i}^{k} has a fixed point of g in its forward orbit under g. The value of this fixed point is x_{i′}^{0} = h(i′) where i′ ≡ i mod (n − 1). Thus the forward orbits under g of elements of Z[\frac{1}{n}] arrange themselves into (n − 1) different classes depending at which fixed point the forward orbits ends. We call these classes the extended orbits of g. Recalling the ring homomorphism ϕ_{n} : Z[\frac{1}{n}] → Z_{n−1} of Lemma 2.1, we have that if x = x_{i}^{k} = h(i/n^{k}), then the fixed point in the forward orbit of i/n^{k} under ν_{n} is ϕ_{n}(i/n^{k}) and the fixed point in the forward orbit of x under g is h(ϕ_{n}(i/n^{k}). We use V_{j} with 0 ≤ j < (n − 1) to denote the extended orbits of g, and we have

(7-6)  x ∈ V_{j} when x = h(i/n^{k}) and j = ϕ_{n}(i/n^{k}).

We carry these classes into the endpoints of the partitions and use V_{j}P^{k} to denote V_{j} ∩ V P^{k}.

We note that as an element of \overline{T}_{n,n−1} with connected domain, Lemma 2.2 implies that g must cyclically permute the cosets of p_{n−1}(Δ_{n}) in Z[\frac{1}{n}]. Since g has fixed points, it fixes one of them, so it fixes them all. Every element of Z[\frac{1}{n}] has a fixed point of g in its forward orbit, so there is a fixed point of g for each coset. There are as many fixed points as cosets, so there is one fixed point per coset. This discussion applies as well to ν_{n} and we get that h induces a well defined permutation on the cosets of p_{n−1}(Δ_{n}) in Z[\frac{1}{n}]. The identity coset is preserved by h since we have h(0) = 0.

Each interval I_{i}^{k} in P^{k} has a length that we denote by L(I_{i}^{k}). These lengths are related. Note that a power of g carries I_{i}^{s} affinely onto I_{i′}^{K} if s ≥ K and i ≡ i′ mod ((n − 1)n^{K}). Now (perhaps different) powers of g will carry I_{i}^{s} and I_{j}^{t} affinely onto the same interval in P^{K} if s ≥ K, t ≥ K and i ≡ j mod ((n − 1)n^{K}). Since the affine parts of g have slopes that are integral powers of n, this implies that L(I_{i}^{s})/L(I_{j}^{t}) is an integral power of n.

8. Trees.

It is possible to arrange the ingredients of the various partitions P^{k} into trees. One tree has the endpoints as vertices and the immediate descendents of each x_{i}^{k} are all the x_{j}^{k+1} that map to x_{i}^{k} under g. Another tree has the intervals as vertices and the immediate descendents of each I_{i}^{k} are all the intervals I_{j}^{k+1} contained in I_{i}^{k}. The levels of the trees are given by the natural levels of the vertices. The numerical functions that we describe in the following sections are attached to these trees where appropriate. If the reader is helped by viewing the objects as being arranged in trees, then this view is available. The trees are not necessary for the arguments that follow and do not simplify them to any extent. Thus we will not mention these trees in what follows.

9. The calculus of break values.

Given an element x of S_{n−1} , we associate a measure of the change of slope of g that occurs at x. It acts like a derivative, so we give it a notation that resembles g′. We define

g^{b}(x) = log_{n} (\frac{g′_{+}(x)}{g′_{−}(x)})

where g′_{+}(x) represents the right derivative of g at x (the slope of g immediately to the right of x) and g′_{−}(x) represents the left derivative of g at x. Since g is PL, this is defined for all x. We call g^{b}(x) the break value of g at x. We use the logarithm to make the chain rule additive in that if g_{1} and g_{2} are two PL functions, then

(9-1)  (g_{1} ∘ g_{2})^{b}(x) = g_{1}^{b}(g_{2}(x)) + g_{2}^{b}(x).

This follows because left and right derivatives satisfy the usual chain rule. We use log base n to make the numbers come out nicer — a fact that we will never use except in examples.

We can think of the break value as the non-linearity concentrated at a point. For a continuously twice differentiable function f, the non-linearity Nf(x) of f at x is usually defined to be

Nf(x) = (ln(f′(x)))′ = \frac{f′′(x)}{f′(x)}.

Now

∫_{a}^{b} Nf = ln(f′)|_{a}^{b}

= ln(f′(b)) − ln(f′(a))

= ln (\frac{f′(b)}{f′(a)}) .

Except for the different log base, this last expression gives the break value at x of a PL function f if we apply the expression to an interval [a, b] with x ∈ (a, b) and with no other break of f in [a, b]. The behavior of the break value and the use that we make of it are similar to the behavior and use of non-linearity.

Some properties of the break value are as follows.

(9-2)  g^{b}(x) = 0 if and only if g is affine in a neighborhood of x.

(9-3)  (g^{n})^{b}(x) = ∑_{i=o}^{n−1} g^{b}(g^{i}(x)).

This is just the sum of the break values of g at n consecutive points in an orbit starting with x. If f : S_{n−1} → S_{n−1} is a PL homeomorphism, then

(9-4)  (fgf^{−1})^{b}(x) = −f^{b}(f^{−1}(x)) + g^{b}(f^{−1}(x)) + f^{b}((gf^{−1})(x))

and

(9-5)  (fgf^{−1})^{b}(f(x)) = −f^{b}(x) + g^{b}(x) + f^{b}(g(x))

where (9-4) and (9-5) have been simplified by using the fact that (f^{−1})^{b}(f(x)) = −f^{b}(x) which follows from applying (9-1) to (f^{−1}f)^{b}(x).

Since g is a PL function defined on a circle S_{n−1} , the sum of the break values of g once around S_{n−1} must be zero. Since V P^{k} contains all the break points of g as long as k ≥ K, we get

(9-6)  ∑_{x∈V P^{k}} g^{b}(x) = 0 whenever k ≥ K.

We will use these properties to make two observations, but first we need to understand the break values of g at its fixed points.

From Lemma 6.3, we know that h is a normalizer of BT_{n,n−1} . Recall that we denote the groupoid of germs generated by BT_{n,n−1} by B_{n,n−1} . From Lemma 3.3, we know that h induces an isomorphism from the group of germs (B_{n,n−1})_{i,i} of functions of BT_{n,n−1} with fixed points at the integer i in S_{n−1} to the group of germs (B_{n,n−1}))_{h(i),h(i)} . Now this group of germs is isomorphic to Z × Z and the two natural generators are “slope n to the right of i” and “slope n to the left of i.” Conjugation by an orientation preserving homeomorphism keeps the “behavior to the right” separate from the “behavior to the left” in that the germ to the right of h(i) of the conjugate is determined only by the germ to the right of i of the conjugated function, and similarly for germs to the left. Thus a germ to the right of i that represents “slope n to the right” must be carried to “slope n to the right” or “slope 1/n to the right.” However, conjugation preserves the property of a fixed point being repelling. Thus “slope n to the right” must be carried to “slope n to the right.” Similarly for the slopes to the left. We now note that ν_{n} has slope n at all its fixed points — the integer points i in S_{n−1} . Thus g has slope n at both sides of all its fixed points h(i). We now can say

(9-7)  g^{b}(h(i)) = 0, where the h(i), 0 ≤ i < n are the fixed points of g.

We can now give our first observation. For any x ∈ Z[\frac{1}{n}] we have g^{N}(x) = h(i) is a fixed point of g where x = h(i/n^{N}) and N = λ(x) is the natural level of x. Thus every n ≥ N has g^{n}(x) = h(i). Since g^{b}(h(i)) = 0, we get from (9-3) that (g^{n})^{b}(x) is independent of n as long as n ≥ N. For any x ∉ Z[\frac{1}{n}], the forward orbit of x under g is disjoint from Z[\frac{1}{n}]. Since Z[\frac{1}{n}] contains all the break points of g, we get that (g^{n})^{b}(x) = 0 for all n if x ∉ Z[\frac{1}{n}]. This allows us to define a function Σ : S_{n−1} → Z by

(9-8)  Σ(x) = lim_{n→∞}(g^{n})^{b}(x).

We can refer to it as the total iterated break value at x, and it is the sum of all the break values in the forward orbit of x (including x) under g. We know that the set of breakpoints of g is contained in the set of endpoints of the intervals of P^{K} where K is the stable level for g. Thus all x ∈ Z[\frac{1}{n}] with natural level λ(x) > K have g^{b}(x) = 0. If x ∈ Z[\frac{1}{n}] has λ(x) > K, then all (g^{i})^{b}(x) = 0 for i < λ(x) − K and we have

(9-9)  Σ(x) = Σ(x′) where x′ = g^{λ(x)−K}(x) has λ(x′) = K.

Since there are only finitely many endpoints of P^{K} (those x ∈ Z[\frac{1}{n}] with λ(x) ≤ K), there are only finitely many different values that Σ(x) can achieve. The property given in (9-9) is the reason for calling the level K the stable level.

Note that (9-8) and (9-3) imply that g^{b}(x) = Σ(x) − Σ(g(x)) for any x. This allows us to to say that the existence of the function Σ() implies that g^{b} is a coboundary on an appropriate complex. In smooth settings, this is often enough to reach conclusions about the conjugating homeomorphism h. We show in Example 1 of Section 13, that this is not sufficient here.

The second observation is a refinement of the first observation and motivates what is needed beyond the existence of the function Σ() to prove that h is PL. We assume that h is PL. We know from Lemma 6.3 that this will imply that h is in T_{n,n−1} so that the break points of h are in Z[\frac{1}{n}]. For x ∈ Z[\frac{1}{n}] we have ν_{n}^{k}(x) = i for some integer i with 0 ≤ i < n and all sufficiently large k. Since ν_{n} has no break points, we have

(9-10)  (g^{k})^{b}(h(x)) = (hν_{n}^{k}h^{−1})^{b}(h(x)) = −h^{b}(x) + h^{b}(ν_{n}^{k}(x)) = −h^{b}(x) + h^{b}(i)

for all sufficiently large k. However, (g^{k})^{b}(h(x)) = Σ(h(x)) for all sufficiently large k. Since there are only finitely many break points of h, we have for all but finitely many x ∈ Z[\frac{1}{n}] that Σ(h(x)) = h^{b}(i) and depends only on the extended orbit of h(x). Thus in the case that h is PL, the observation made above that Σ() takes on only finitely many values is further refined. Since we are trying to show that h is PL, we do not need this observation, but it motivates the converse that we prove in the next section.

10. Criteria for piecewise linearity.

In this section we develop separate criteria for the piecewise linearity of h and h^{−1}ν_{n}h. Section 11 has the task of relating these two criteria. 10.1. The piecewise linearity of h. We will show that the observation made at the end of the previous section has a converse. We know that if h is PL, then it must have certain properties. If h is not known to be PL, but is known to have these properties, then we will build a PL function h̄ that has these properties. Then we will show that it must be equal to h by showing that h̄ also conjugates ν_{n} to g.

From (9-10), we know that if h is PL, if x ∈ Z[\frac{1}{n}], and if i = ϕ_{n}(x) is the fixed point of ν_{n} in the forward orbit of x under ν_{n}, then Σ(h(x)) = h^{b}(i) − h^{b}(x). For a PL function h, we know that h^{b}(x) = 0 for almost all x and that will make Σ(h(x)) take one value Σ_{i} for almost all x with ϕ_{n}(x) = i. Since we will have Σ_{i} = Σ(h(x)) = h^{b}(i) − 0 = h^{b}(i) for those x with h^{b}(x) = 0, we will have h^{b}(i) = Σ_{i}. For those x with h^{b}(x) ≠ 0, we will have h^{b}(x) = Σ_{i} − Σ(h(x)). This motivates our proof the converse.

Let h be as given in the hypothesis of Theorem 3 and assume, for each i with 0 ≤ i < (n − 1), that Σ(h(x)) takes on one value Σ_{i} for all but finitely many x ∈ Z[\frac{1}{n}] with ϕ_{n}(x) = i. For each x ∈ Z[\frac{1}{n}], define b(x) = Σ_{i} − Σ(x) where i = ϕ_{n}(x). Note that our hypothesis and construction imply that b(x) = 0 for all but finitely many x ∈ Z[\frac{1}{n}]. We want to argue that h is PL with all its break points in Z[\frac{1}{n}] and that h^{b}(x) = b(h(x)) for all x ∈ Z[\frac{1}{n}]. We will do this by building an h̄ with these properties and then showing that h̄ must equal h. As in (9-6), we must also have

(10-1)  ∑_{x∈Z[ \frac{1}{n}]} b(h(x)) = ∑_{x∈Z[ \frac{1}{n}]} h^{b}(x) = 0.

in order for this to work. This is a tedious calculation that is based on (9-6) that we now tackle. Note that since h is a one to one correspondence from Z[\frac{1}{n}] to itself, we can replace b(h(x)) with b(x) in (10-1).

We have b(x) = Σ_{i} − Σ(x) where i = ϕ_{n}(x). The condition i = ϕ_{n}(x) is equivalent to h(x) ∈ V_{i}, so we have b(x) = Σ_{i} − Σ(x) where x ∈ V_{i}. We know that for x ∈ V_{i}, and λ(x) ≥ K, we have Σ(x) = Σ_{i}. Thus b(x) = 0 for all x with λ(x) ≥ K. In spite of the fact that x with λ(x) = K contributes nothing to a sum of the values of b(x), it is convenient to include them. We now know that to verify (10-1), it is sufficient to verify

∑_{x∈V P^{K}} b(x) = ∑_{i=0}^{n−2} ∑_{x∈V_{i}P^{K}} b(x) = ∑_{i=0}^{n−2} ∑_{x∈V_{i}P^{K}}(Σ_{i} − Σ(x)) = 0.

We will need to know the sizes of some collections of elements of Z[\frac{1}{n}]. We let M(k) be the number of elements of V P^{k}, we let M_{i}(k) be the number of elements of V_{i}P^{k} and we let m_{i}(k) be the number of elements x of V_{i}P^{k} that have λ(x) = k. We have

\begin{aligned}M(k) & = (n − 1)n^{k}, \\ M_{i}(k) & = n^{k}, and \\ m_{i}(k) & = n^{k} − n^{k−1} = (n − 1)n^{k−1}. \end{aligned}

Now

\begin{aligned}∑_{i=0}^{n−2} ∑_{x∈V_{i}P^{K}}(Σ_{i} − Σ(x)) & = ∑_{i=0}^{n−2} M_{i}(K)Σ_{i} − ∑_{i=0}^{n−2} ∑_{x∈V_{i}P^{K}} Σ(x) \\ & = n^{K} ∑_{i=0}^{n−2} Σ_{i} − ∑_{x∈V P^{K}} Σ(x) \end{aligned}

so it suffices to prove

∑_{x∈V P^{K}} Σ(x) = n^{K} ∑_{i=0}^{n−2} Σ_{i}.

We have

(10-2)  ∑_{x∈V P^{K}} Σ(x) = ∑_{λ(x)=K} Σ(x) + ∑_{x∈V P^{K−1}} Σ(x).

But x ∈ V_{i}P^{K} and λ(x) = K imply Σ(x) = Σ_{i} so we have

(10-3)  ∑_{λ(x)=K} Σ(x) = m_{i}(K) ∑_{i=0}^{n−2} Σ_{i} = (n − 1)n^{K−1} ∑_{i=0}^{n−2} Σ_{i}.

Thus we have

∑_{x∈V P^{K}} Σ(x) = (n − 1)n^{K−1} ∑_{i=0}^{n−2} Σ_{i} + ∑_{x∈V P^{K−1}} Σ(x)

and we are done if we show

∑_{x∈V P^{K−1}} Σ(x) = n^{K−1} ∑_{i=0}^{n−2} Σ_{i}.

By (10-3), this is equivalent to

(n − 1) ∑_{x∈V P^{K−1}} Σ(x) = ∑_{λ(x)=K} Σ(x)

and from (10-2) this is equivalent to the following which will be more convenient to prove:

(10-4)  n ∑_{x∈V P^{K−1}} Σ(x) = ∑_{x∈V P^{K}} Σ(x).

We now expand the expression Σ(x). From (9-8) and (9-3), this is a sum of values of g^{b}(g^{i}(x)) as i runs over the non-negative integers. The various g^{i}(x) have natural levels given by λ(g^{i}(x)) = λ(x) − i as long as the result is not negative. If we sum all Σ(x) over all x with λ(x) fixed at some k, then we will get contributions of the form g^{b}(y) from elements y with λ(y) ≤ λ(x). Since there are n elements of level k that map to a given element of level k − 1, n^{2} elements of level k that map to a given element of level k − 2 and so forth, we can assess the multiplicity of contribution of elements of various levels. The pattern breaks down at level 0 however. This is because while a fixed point has n preimages, one of them is the fixed point itself. Thus there are only (n−1) elements of level 1 that map to a given fixed point. We will ignore this because by (9-7), the fixed points do not contribute to the expressions Σ(x). Also for this reason, it makes no difference whether our sums include level zero. We attack (10-4) by writing down a sum of Σ(x) over a single level, and then summing over levels.

We have

∑_{λ(x)=k} Σ(x) = ∑_{λ(x)≤k} n^{k−λ(x)}g^{b}(x).

Summing over various levels, we get

∑_{λ(x)≤j} Σ(x) =  ∑_{k≤j} ∑_{λ(x)≤k} n^{k−λ(x)}g^{b}(x)  = ∑_{k≤j} ∑_{i≤k} ∑_{λ(x)=i} n^{k−i}g^{b}(x)
=  ∑_{i=0}^{j} ∑_{λ(x)=i} ∑_{k=i}^{j} n^{k−i}g^{b}(x)  = ∑_{i=0}^{j} ∑_{λ(x)=i} ∑_{k=0}^{j−i} n^{k}g^{b}(x)
= ∑_{i=0}^{j} ∑_{λ(x)=i} (\frac{n^{j−i+1} − 1}{n − 1}) g^{b}(x).

Multiplying through by (n − 1) gives

(n − 1) ∑_{λ(x)≤j} Σ(x) = ∑_{i=0}^{j} ∑_{λ(x)=i} (n^{j−i+1} − 1) g^{b}(x), and

(n − 1) ∑_{λ(x)≤j−1} Σ(x) = ∑_{i=0}^{j−1} ∑_{λ(x)=i} (n^{j−i} − 1) g^{b}(x)

= ∑_{i=0}^{j} ∑_{λ(x)=i} (n^{j−i} − 1) g^{b}(x)

because n^{j−j} = 1.

Breaking these sums into two parts each gives

(10-5)  (n − 1) ∑_{λ(x)≤j} Σ(x) = ∑_{i=0}^{j} ∑_{λ(x)=i} (n^{j−i+1}) g^{b}(x) − ∑_{x∈V P^{j}} g^{b}(x),

and

(n − 1) ∑_{λ(x)≤j−1} Σ(x) = ∑_{i=0}^{j} ∑_{λ(x)=i} (n^{j−i}) g^{b}(x) − ∑_{x∈V P^{j}} g^{b}(x).

But from (9-6), we know that

∑_{x∈V P^{j}} g^{b}(x) = 0

whenever j ≥ K. Thus we set j = K, we factor an n from the right side of (10-5), and we obtain (10-4). This proves (10-1) and we now continue with the construction of h̄.

Let m be a real number greater than 0. We build a function h̄_{m} on [0, n − 1] as follows. It essentially “integrates” the information given by the the function b(x). Except for x = 0, we draw horizontal lines H_{x} in the plane through the points (0, x) on the y -axis that have b(x) ≠ 0. We draw a graph of a function from [0, ∞) to itself to satisfy the following: The graph is piecewise linear, it passes through (0, 0), it has slope m to the right of 0, it breaks only when it intersects one of the horizontal lines H_{x}, and the break value that it has there is the value b(x). Note that all slopes of this function will be positive. That such a function can be built, and the uniqueness of the function given m is clear. We let h̄_{m} be the function with this graph. The x coordinate at which h̄_{m} achieves the value (n − 1) is a continuous monotone function of m, and in fact it is easily seen to depend linearly on m^{−1} . Thus there is a unique m for which h̄_{m}(n − 1) = (n − 1). We let h̄ = h̄_{m} for this m. We view h̄ as a homeomorphism from S_{n−1} to itself. This will make the sum of the break values of h̄ over all of S_{n−1} equal to zero. By construction, we have h̄^{b}(h̄^{−1}(x)) = b(x) at all x except possibly x = 0. Because of (10-1), we will have that the break value of h̄ at 0 = h̄(0) will be b(0).

If we let ḡ = h̄ν_{n}h̄^{−1} , then we can define \overline{Σ}(x) as the sum of the breaks in the forward orbit of x under ḡ in analogy with Σ(x). From (9-10) applied to h̄, we get

\overline{Σ}(h̄(x)) = h̄^{b}(i) − h̄^{b}(x)

or equivalently

\overline{Σ}(x) = h̄^{b}(h̄^{−1}(i)) − h̄^{b}(h̄^{−1}(x))
= b(i) − b(x)
= (Σ_{i} − Σ(i)) − (Σ_{i} − Σ(x))
= Σ(x)

since Σ(i) = 0. From the definitions of \overline{Σ}() and Σ(), we know that we can recover ḡ^{b}(x) as \overline{Σ}(x) − \overline{Σ}(ḡ(x)) and g^{b}(x) as Σ(x) − Σ(g(x)). From this, we conclude that ḡ^{b} and g^{b} are identical functions. Further, we know that ḡ(0) = g(0) = 0 since ν_{n}, h̄ and h all fix 0. Just as the properties of h̄ made h̄ unique, we can argue that the properties listed make g unique. Thus ḡ = g and h̄ conjugates ν_{n} to g. Since ν_{n} is an expanding map, the homeomorphism that conjugates ν_{n} to g is unique. One way to se this is to note that the conjugator must take the endpoints of the standard Markov partition of level k for ν_{n} to the elements of V P^{k} in order. This forces the value of the conjugator on the elements of Z[\frac{1}{n}], a dense set in S_{n−1} . If we were arguing existence of a conjugator, we would have to argue the denseness of ⋃_{k}{V P^{k}}. However, a conjugator (namely h) exists by hypothesis. 10.2. The piecewise linearity of h^{−1}ν_{n}h. This title is somewhat misleading. Our aim is to show that h is PL. However, from Lemma 6.3, we know that h normalizes BT_{n,n−1} , so not only must h^{−1}ν_{n}h be PL, but so must h^{−1}fh for any f ∈ BT_{n,n−1} . Our approach will be to show that if h is not PL (violates the criterion in 10.1), then h must fail to normalize BT_{n,n−1} . Being able to test any f ∈ BT_{n,n−1} gives more flexibility than just testing h^{−1}ν_{n}h. Thus we develop a criterion for the piecewise linearity of any h^{−1}fh for any f ∈ BT_{n,n−1} .

We can show that a function is not PL by showing that a sequence of chords to its graph changes slope infinitely many times in a bounded interval. This allows us to reduce our calculations of the behavior to a countable set of points. We have enough information about h and h^{−1} from the Markov partitions for ν_{n} and g to calculate the behavior of h^{−1}fh on a countable set of points, and this gives us enough machinery to derive our criterion.

Let P^{s} and P^{t} be two Markov partitions obtained from standard Markov partitions of levels s and t for ν_{n}. We know that either s = t or one of P^{s} or P^{t} is derived from the other (it doesn’t matter which). Assume that (x_{1} < x_{2} < ⋯ < x_{k}) is a sequence in V P^{s} so that all points [x_{1}, x_{k}] ∩ V P^{s} are in the sequence. Assume that (x′_{1} < x′_{2} < ⋯ < x′_{k}) is a sequence in V P^{t} containing all [x′_{1}, x′_{k}] ∩ V P^{t}. Assume that f ∈ BT_{n,n−1} takes x_{i} to x′_{i} for 1 ≤ i < k and that it fails to take x_{k} to x′_{k}. We have that the points h^{−1}(x_{i}) are equally spaced (they are consecutive endpoints in the standard Markov partition of level s for ν_{n}) as are the points h^{−1}(x′_{i}). Thus the graph of h^{−1}fh has chords of the same slope spanning all the intervals [h^{−1}(x_{i}), h^{−1}(x_{i+1})] for 1 ≤ i ≤ (k − 2) but the chord spanning [h^{−1}(x_{k−1}), h^{−1}(x_{k})] has a different slope. Thus h^{−1}fh is not affine on [h^{−1}(x_{1}), h^{−1}(x_{k})]. In order for this to be a useful observation, we need to show that we can arrange f to take two consecutive endpoints in a Markov partition for g to two consecutive endpoints in a (perhaps different) Markov partition for g, and we need to understand when f fails to carry a string of consecutive endpoints to a string of consecutive endpoints.

If f takes two consecutive endpoints from one partition to two consecutive endpoints from another partition, then f is carrying some interval of one partiton to an interval of the other. We achieve this by starting with the fact that f carries an endpoint of one partition to an endpoint of the other and then take derived partitions until we get what we want.

Let f take some a = x_{i}^{s} to b = x_{j}^{t}. Since f preserves cosets of p_{n−1}(Δ_{n}), we know that the forward orbits of a and b include the same fixed point of g. Specifically, g^{λ(a)}(a) = g^{λ(b)}(b) = z is a fixed point of g and λ(a) and λ(b) are the smallest powers of g that achieve this. Assume temporarily that s = λ(a) + K and t = λ(b) + K. Then g^{λ(a)}(I_{i}^{s}) = g^{λ(b)}(I_{j}^{t}) = I_{i′}^{K} where i ≡ j ≡ i′ mod (n − 1)n^{K}. We know that for these values of s and t, that L(I_{j}^{t})/L(I_{i}^{s}) is an integral power of n.

If f has this ratio as its slope to the right of a, then f carries I_{i}^{s} affinely onto I_{j}^{t} and we have that f takes two consecutive endpoints of P^{s} to two consecutive endpoints of P^{t}. For future reference, we call this ratio (with s = λ(a) + K and t = λ(b) + K) the natural slope of the pair (a, b).

If f has slope to the right of a that is different from the natural slope of (a, b), then it differs from it by a factor that is an integral power of n. Assume first that the slope of f is too large so that L(I_{i}^{s}) is too large. We note that I_{ni}^{s+1} has a = x_{i}^{s} = x_{ni}^{s+1} as left endpoint and since g^{λ(a)}(a) is a fixed point of g, we have g^{λ(a)+1}(I_{ni}^{s+1}) = I_{i′}^{K} in P^{K} and g^{λ(a)}(I_{ni}^{s+1}) = I_{ni′}^{K+1} in P^{K+1} where I_{i′}^{K} and I_{ni′}^{K+1} have the same left endpoint z. Because z is a fixed point of g, we have that g(I_{ni′}^{K+1}) = (I_{i′}^{K}). We know that g has slope n near its fixed points, so L(I_{i′}^{K})/L(I_{ni′}^{K+1}) = n. The slope of g^{λ(a)} on I_{ni}^{s+1} is the same as it has on I_{i}^{s} so we can conlude that L(I_{i}^{s})/L(I_{ni}^{s+1}) = n and that the ratio L(I_{j}^{t})/L(I_{ni}^{s+1}) differs from the natural slope of (a, b) by a factor of 1/n.

By taking further derivations of P^{s}, we can achieve an adjustment by any integral multiple of 1/n we wish. If the slope of f is too small, then we take derivations of P^{t} instead of P^{s}. In this way we can get f to take two consecutive points of one partition to two consecutive points of another. Further, we can do this with any f in BT_{n,n−1} and have as the two first points any a and b in Z[\frac{1}{n}] where f(a) = b.

Now assume that an element f of BT_{n,n−1} carries the sequence of consecutive endpoints (a = x_{i}^{s}, x_{i+1}^{s}, …, x_{i+k}^{s} = b) in a partition P^{s} for g to consecutive endpoints (c = x_{j}^{t}, x_{j+1}^{t}, …, x_{j+k}^{t} = d) in a partition P^{t} for g. Assume further that f is affine on [a, b]. If both P^{s} and P^{t} have their derivations taken, then f carries the new endpoints in [a, b] in P^{s+1} onto the new endpoints in [c, d] in P^{t+1} . Thus we can derive domain and range partitions the same number of times and keep the assumed hypotheses on the original interval [a, b]. Thus we can assume that s ≥ λ(a) + K and t ≥ λ(c) + K. As observed before, a and c have a common fixed point z of g in their forward orbits. Our assumptions on s and t guarantee that for this fixed point z of g, we have g^{s−K}(a) = g^{t−K}(c) = z = x_{i′}^{K} where i′ ≡ i ≡ j mod (n − 1)n^{K}.

We now assume that f is affine on [a, x_{i+k+1}^{s}]. We wish to see if f takes x_{i+k+1}^{s} to x_{j+k+1}^{t}. This is equivalent to having f carry I_{i+k}^{s} onto I_{j+k}^{t}. This in turn is equivalent to having the lengths of I_{j+k}^{t} and I_{i+k}^{s} have the same ratio as the lengths of I_{j+k−1}^{t} and I_{i+k−1}^{s}. The intervals I_{i+k−1}^{s} and I_{i+k}^{s} are carried affinely by g^{s−K} onto I_{i′+k−1}^{K} and I_{i′+k}^{K} with slopes m_{1} and m_{2} respectively. The intervals I_{j+k−1}^{t} and I_{j+k}^{t} are carried affinely by g^{t−K} onto I_{i′+k−1}^{K} and I_{i′+k}^{K} with slopes m_{3} and m_{4} respectively. Our chain of equivalent statements is equivalent to m_{3}/m_{1} = m_{4}/m_{2} which is equivalent to m_{2}/m_{1} = m_{4}/m_{3} . Thus we have the equality of break values

(10-6)  (g^{s−K})^{b}(x_{i+k}^{s}) = (g^{t−K})^{b}(x_{j+k}^{t}).

But

g^{s−K}(x_{i+k}^{s}) = g^{t−K}(x_{j+k}^{t}) = x_{i′+k}^{K}.

So (10-6) is equivalent to

\begin{aligned}Σ(x_{i+k}^{s}) = (g^{s})^{b}(x_{i+k}^{s}) & = (g^{s−K})^{b}(x_{i+k}^{s}) + (g^{K})^{b}(x_{i′+k}^{K}) \\ & = (g^{t−K})^{b}(x_{j+k}^{t}) + (g^{K})^{b}(x_{i′+k}^{K}) = (g^{t})^{b}(x_{j+k}^{t}) = Σ(x_{j+k}^{t}). \end{aligned}

Thus extending the fact that an affine f carries a sequence of consecutive endpoints to a sequence of consecutive endpoints is equivalent to the equality of the values of Σ(x) on the corresponding endpoints (except the last endpoint in each sequence). Specifically, given that f is affine on [a, b] as given above, and takes the pair (x_{i}^{s}, x_{i+1}^{s}) to the pair (x_{j}^{t}, x_{j+1}^{t}) with s ≥ λ(a) + K and t ≥ λ(c) + K, then it takes (x_{i}^{s}, x_{i+1}^{s}, …, x_{i+k}^{s}) to (x_{j}^{t}, x_{j+1}^{t}, …, x_{j+k}^{t}) if and only if all of Σ(x_{i+q}^{s}) = Σ(x_{j+q}^{t}) for all q with 1 ≤ q < k.

11. Relating the criteria.

In this section, we restrict n to 2. Theorem 3 follows from the next proposition, from the criterion for the piecewise linearity of h, and the fact that an f can be built as described in the proposition by Lemma 2.3. Recall that the V_{i}, 0 ≤ i < (n − 1), are the extended oribts of g in Z[\frac{1}{n}]. When n = 2, there is only one such set V_{0} = Z[\frac{1}{2}]. The criterion in Section 10.1 that h is PL if the function Σ() is almost constant on each V_{i} reduces to requiring that Σ() be constant off a finite set in Z[\frac{1}{2}].

Proposition 11.1. Assume that Σ() is not constant on the complement of a finite set in Z[\frac{1}{2}]. Let a and c be in Z[\frac{1}{2}] with s = λ(a) ≥ K and t = λ(c) ≥ K. Let a = x_{j}^{s} and b = x_{j+1}^{s}. If f ∈ BT_{2,1} takes a to c, is affine on [a, b] and does not have the natural slope of the pair (a, c) on the interval [a, b], then h^{−1}fh is not PL on [h^{−1}(a), h^{−1}(b)].

The proposition follows immediately by induction from the next lemma.

Lemma 11.2 (Inductive Step). If f, Σ(), [a, b] and c satisfy the hypotheses of the proposition, then there is an interval [d, e] ⊆ (a, b] so that f and [d, e] satisfy the hypotheses of the proposition and so that d is a break point of h^{−1}fh.

Proof: The bulk of the proof is in finding the point d at which h^{−1}fh breaks. After that it is a straightforward matter to verify that d has the remaining properties claimed. 11.1. Locating d. We have that f takes a to c. We have a = x_{j}^{s} where s = λ(a). With t = λ(c), we can say c = x_{k}^{t}. From Section 10.2, we have that the natural slope of (a, c) is gotten by regarding a = x_{2^{K}j}^{s+K} and c = x_{2^{K}k}^{t+K} and that the natural slope is equal to L(I_{2^{K}k}^{t+K})/L(I_{2^{K}j}^{s+K}). Given a positive integer p, we also know that

(11-1)  L(I_{2^{K+p}j}^{s+K+p}) = 2^{−p}L(I_{2^{K}j}^{s+K}) and L(I_{2^{K+p}k}^{t+K+p}) = 2^{−p}L(I_{2^{K}k}^{t+K}).

Since the slope m of f on [a, b] is not the natural slope of (a, c), we know that either m = L(I_{2^{K+p}k}^{t+K+p})/L(I_{2^{K}j}^{s+K}) or m = L(I_{2^{K}k}^{t+K})/L(I_{2^{K+p}j}^{s+K+p}) for some positive integer p. From this it follows that either f(I_{2^{k}j}^{s+K}) = I_{2^{K+p}k}^{t+K+p} or f(I_{2^{K+p}j}^{s+K+p}) = I_{2^{K}k}^{t+K} and f takes two consecutive endpoints of P^{s+K} or P^{s+K+p} to two consecutive endpoints of P^{t+K+p} or P^{t+K} respectively.

To verify the criterion in Section 10.2, we must compare Σ() on the endpoints of P^{s+K} or P^{s+K+p} to corresponding endpoints of P^{t+K+p} or P^{t+K} respectively. Since the direction of f is irrelevant to the comparison, we will assume that m = L(I_{2^{K+p}k}^{t+K+p})/L(I_{2^{K}j}^{s+K}). Later we will say a few words about the other possibility.

When we locate d, we will want to claim that d is a break point of h^{−1}fh. We note that our criterion in Section 10.2 only detects breaks in the slopes of chords to the graph of h^{−1}fh. A break in the slopes of chords implies that a break in the graph of h^{−1}fh takes place somewhere in the domain covered by the two chords with differing slopes, but it does not precisely locate the break of h^{−1}fh. To make the location more precise, we will investigate the slopes of chords on increasingly fine intervals. The next paragraph shows how we can do this.

We are assuming that f(I_{2^{K}j}^{s+K}) = I_{2^{K+p}k}^{t+K+p}. This means that f(x_{2^{K}j+i}^{s+K}) = x_{2^{K+p}k+i}^{t+K+p} for i = 0 and i = 1. We are to see if Σ(x_{2^{K}j+i}^{s+K}) = Σ(x_{2^{K+p}k+i}^{t+K+p}) for various values of i. However, (11-1) and our assumption that f(I_{2^{K}j}^{s+K}) = I_{2^{K+p}k}^{t+K+p} imply that

(11-2)  f(I_{2^{K+q}j}^{s+K+q}) = I_{2^{K+p+q}k}^{t+K+p+q}

for any non-negative integer q. Thus we have f(x_{2^{K+q}j+i}^{s+K+q}) = x_{2^{K+p+q}k+i}^{t+K+p+q} for i = 0 and i = 1 and we can also see if Σ(x_{2^{K+q}j+i}^{s+K+q}) = Σ(x_{2^{K+p+q}k+i}^{t+K+p+q}) for various values of i. In other words, we can not only compare values of Σ() on sequences in V P^{s+K} and V P^{t+K+p}, but also compare values of Σ() on sequences in V P^{s+K+q} and V P^{t+K+p+q}.

Note that V P^{s+K} ⊆ V P^{s+K+q} and V P^{t+K+p} ⊆ V P^{t+K+p+q}. What we will show will be that a discrepancy in the values of Σ() will occur at some point in V P^{s+K} ∩ (a, b), but that no discrepancy occurs in (a, b) at a point in V P^{s+K+q} − V P^{s+K}. Since V P^{s+K} is finite, any discrepancy in (a, b) in any of the V P^{s+K+q} occurs in a fixed finite set of points. We will let d be the leftmost point in (a, b) at which a discrepancy occurs.

Since no discrepancy occurs to the left of d in any V P^{s+K+q}, we have that the slopes of chords of h^{−1}fh are the same on a dense set of points in [a, d] so h^{−1}fh is affine on [h^{−1}(a), h^{−1}(d)]. If d′ is the point immediately to the right of d in V P^{s+K}, then we know that h^{−1}fh is not affine on [h^{−1}(a), h^{−1}(d′)]. However, if h^{−1}fh is affine on an interval in [h^{−1}(a), h^{−1}(d′)] that properly contains [h^{−1}(a), h^{−1}(d)], then there would have to be a discrepancy of values of Σ() at some point d′′ in (d, d′) in some V P^{s+K+q}. But since d and d′ are consecutive points in V P^{s+K}, we would have to have d′′ ∈ V P^{s+K+q} −V P^{s+K}. Since this will be shown not to happen, we must have that h^{−1}fh breaks at d.

We are to see if the equalities Σ(x_{2^{K+q}j+i}^{s+K+q}) = Σ(x_{2^{K+p+q}k+i}^{t+K+p+q}) hold. Since the notation is getting out of hand, and since we will need to understand the effect of powers of g on the indexes, we shift our point of view. We make use of (7-3) which gives

x_{2^{K+q}j+i}^{s+K+q} = h((2^{K+q}j + i)/2^{s+K+q})

and

x_{2^{K+p+q}k+i}^{t+K+p+q} = h((2^{K+p+q}k + i)/2^{t+K+p+q}).

This will allow us to refer to the binary expansions of (2^{K+q}j +i)/2^{s+K+q} and (2^{K+p+q}k+ i)/2^{t+K+p+q}.

Let x = h(a/2^{b}) where a and b are positive integers. We know from the remarks following (7-3) that λ(x) is the position to the right of the binary point of the last 1 in the binary expansion of a/2^{b}. Assume that λ(x) ≥ K. From (9-9), we know that Σ(x) = Σ(g^{λ(x)−K}(x)). Now

(11-3)  g^{λ(x)−K}(x) = hν_{2}^{λ(x)−K}h^{−1}(x) = hν_{2}^{λ(x)−K}(a/2^{b}) = hΩ_{K}(a/2^{b}),

where Ω_{K}(a/2^{b}) is defined to be ν_{2}^{λ(x)−K}(a/2^{b}). If we refer to the last 1 in the binary expansion of a/2^{b} (which we know occurs in position λ(x)) as the “last” bit in the expansion of a/2^{b}, then the expansion of Ω_{K}(a/2^{b}) consists of a binary point followed by the “last” K bits of the expansion of a/2^{b}. Thus Σ(x) depends on the “last” K bits of the binary expansion of h^{−1}(x) = a/2^{b}.

It will be convenient to introduce another notational device. For an integer i, we let z(i) be the largest integer z for which 2^{z} | i holds. This is the number of trailing zeros in the binary expansion of i.

We consider a pair of points x and y at which values of Σ() are to be compared. We let x = h((2^{K+q}j+i)/2^{s+K+q}). Since s = λ(a) = λ(x_{j}^{s}), we know that the last 1 in the binary expansion of j/2^{s} is in position s to the right of the binary point. We are only interested in points in (a, b) = (x_{j}^{s}, x_{j+1}^{s}) and x_{j+1}^{s} = h((j + 1)/2^{s}). Now (2^{K+q}j + i)/2^{s+K+q} = (j/2^{s}) + (i/2^{s+K+q}). Thus we are only interested in values of i with 1 ≤ i < 2^{K+q}, and λ(x) = s + K + q − z(i). The point y corresponding to x is given by

y = h((2^{K+p+q}k + i)/2^{t+K+p+q}) = h((k/2^{t}) + (i/2^{t+K+p+q})),

and we have λ(y) = t + K + p + q − z(i).

As i runs through its range of values, then x and y run through consecutive points in V P^{s+K+q} and V P^{t+K+p+q} that are in (a, b) and (f(a), f(b)) respectively. However, we can break this into levels, and observe that as i runs through those values in its range that have z(i) equal to some constant ζ, then x runs, in order, through the points in V P^{s+K+q} ∩ (a, b) that are at the constant natural level s + K + q − ζ, and similarly y runs, in order, through those points in V P^{t+K+p+q} ∩ (f(a), f(b)) at the natural level t + K + p + q − ζ. The crucial point is that as i runs through its values with z(i) = ζ, the points g(x)^{λ(x)−K} are running, in order, through a set of consecutive point on level K, and the points g^{λ(x)−K}(y) are running through a perhaps different set of consecutive points also on level K. We will exploit the fact that values of Σ() will be compared on different sequences of points on level K. We must now compute which sequences will be compared.

Let ζ be fixed and let x = h((j/2^{s}) + (i/2^{s+K+q})) where z(i) = ζ. We have λ(x) = s + K + q − ζ. From (9-9) and (11-3), we know that

Σ(x) = Σ(hΩ_{K}((j/2^{s}) + (i/2^{s+K+q}))).

Now the last 1 in the expansion of j/2^{s} is at position s and the last 1 in the expansion of i/2^{s+K+q} is at position s + K + q − ζ. Thus if λ(x) = s + K + q − ζ ≥ s + K, then Ω_{K}((j/2^{s}) + (i/2^{s+K+q})) depends only on i and so does Σ(x). Further, the definition of Ω_{K} makes it clear that

Ω_{K}((j/2^{s}) + (i/2^{s+K+q})) = Ω_{K}(i/2^{s+K+q}) = Ω_{K}(i/2^{K}) = i/2^{K} mod (1),

and we get that Σ(x) = Σ(hΩ(i/2^{K})) whenever λ(x) ≥ s + K. Similarly, for y = h((k/2^{t}) + (i/2^{t+K+p+q})), we have Σ(y) = Σ(hΩ(i/2^{K})) whenever λ(y) ≥ t + K. This establishes that no discrepancy in the values of Σ will be discovered when we are considering points x from V P^{s+K+q} − V P^{s+K}. (In fact this is true for V P^{s+K+q} − V P^{s+K−1} , but there is no need to dwell on this.)

From now on we take q to be 0. We are looking at points x = h((j/2^{s}) + (i/2^{s+K})) and y = h((k/2^{t}) + (i/2^{t+K+p})) where 1 ≤ i < 2^{K}. The restrictions on i dictate that the binary expansions of i/2^{s+K} and i/2^{t+K+p} have no ones outside the “last” K bits of the expansion. We have λ(x) = s + K − z(i) and λ(y) = t + K + p − z(i). We now look at all those i with z(i) a fixed value ζ ≥ 0.

For these i, we have have

Σ(x) = Σ(hΩ_{K}((j/2^{s}) + (i/2^{s+K})))

where Ω_{K}((j/2^{s}) + (i/2^{s+K})) expands as the “last” ζ bits of j/2^{s} followed by the K − ζ bits of i/2^{s+K} that end at the last 1 in the expansion of i/2^{s+K}. For a similar i, we have

Σ(y) = Σ(hΩ_{K}((k/2^{t}) + i/2^{t+K+p})))

where Ω_{K}((k/2^{t}) + i/2^{t+K+p})) expands as the “last” ζ − p bits of k/2^{t} followed by p zeros followed by the same K − ζ bits of i/2^{s+K} that end at the last 1 in the expansion of i/2^{s+K} that are the last K − ζ bits of Ω_{K}((j/2^{s}) + (i/2^{s+K})).

Thus we see that the sequence of values Σ(x) that we get for those i with z(i) = ζ are those Σ(h(w)) where w runs over the 2^{K−ζ} patterns of K bits that start with the last ζ bits of j/2^{s}. This means that all the patterns w have a common prefix of ζ bits and that the bit in position ζ (the last bit of j/2^{s}) is a 1. The sequence of values Σ(y) that we get are those Σ(h(v)) where v runs over the 2^{K−ζ} patterns of K bits that start with a prefix of ζ bits and where the bit in position ζ is a 0.

Note that our use of (9-9) means that all values of Σ() are reduced to values of Σ(u) with λ(u) = K. Since there are 2^{K−1} different u with λ(u) = K (see Section 10.1), we know that the full sequence of values of Σ() that are available is a sequence with 2^{K−1} elements. We call a string of 2^{K−ζ} such values given by all Σ(h(w)) with w a K bit expression with a fixed ζ bit prefix a ζ -string of the values of Σ(). The full sequence of 2^{K−1} possible Σ() values is divided into 2^{ζ} different ζ -strings.

We call a ζ -string an even ζ -string if the prefix of ζ bits that determines the ζ -string ends in a 0. Similarly, we call a ζ -string an odd ζ -string if the prefix of ζ bits that determines the ζ -string ends in a 1. Note that remarks made above say that we are always comparing an even ζ -string with an odd ζ -string.

Note that ζ can be fixed at any value from 0 through K −1. At ζ = 0, we are comparing all of the sequence of 2^{K−1} values of Σ() with itself. This results in no discrepancy and reflects that parenthetical remark above that no discrepancy will be discovered for an x outside of V P^{s+K−1} . For ζ = 1 we compare the unique odd 1-string with the unique even 1-string. In simpler words, we compare the first half of the sequence of Σ() values to the second half of the sequence. For ζ = 2, we compare some odd quarter to some even quarter. The pattern continues.

We now have a very elementary induction. If the first half is the same as the second half (as sequences), then all odd quarters are equal to each other (as sequences) and all even quarters are equal to each other (as sequences). If now one odd quarter is shown to equal one even quarter (as sequences), then all four quarters are equal (as sequences). We now note by induction that the sequence of 2^{K−1} values of Σ() must be constant if all comparisons of some even ζ -string with some odd ζ -string show no discrepancies for all ζ with 1 ≤ ζ ≤ (K − 1). Since we assume that Σ() is not constant over those u with λ(u) = K, we must have a discrepancy at some level.

This locates d under the assumption that m = L(I_{2^{K+p}k}^{t+K+p})/L(I_{2^{K}j}^{s+K}).

If we had assumed that m = L(I_{2^{K}k}^{t+K})/L(I_{2^{K+p}j}^{s+K+p}), then an identical argument would locate a discrepancy at some x = h((j/2^{s}) + (i/2^{s+K+p})) with 1 ≤ i < 2^{K}. This will be a point that is well within the interval (x_{j}^{s}, x_{j+1}^{s}). 11.2. Verifying properties. We will work with the point d in Section 11.1 found under the assumption that m = L(I_{2^{K+p}k}^{t+K+p})/L(I_{2^{K}j}^{s+K}). Arguments for the assumption m = L(I_{2^{K}k}^{t+K})/L(I_{2^{K+p}j}^{s+K+p}) are not significantly different. We have

d = h (\frac{j}{2^{s}} + \frac{i}{2^{s+K}} ) = h (\frac{j}{2^{s}} + \frac{i/2^{ζ}}{2^{s+K−ζ}} )

where ζ = z(i) and λ(d) = s + K − ζ. Since 1 ≤ i < 2^{K}, we have K − ζ > 0 and i/2^{ζ} is an integer with 1 ≤ i/2^{ζ} < 2^{K−ζ}. From this we get λ(d) > s ≥ K and also

(\frac{j}{2^{s}} + \frac{(i/2^{ζ}) + 1}{2^{s+K−ζ}}) ≤ (\frac{j}{2^{s}} + \frac{2^{K−ζ}}{2^{s+K−ζ}} ) = (\frac{j + 1}{2^{s}}) .

We have

(\frac{j}{2^{s}} + \frac{i/2^{ζ}}{2^{s+K−ζ}} ) = (\frac{j2^{K−ζ} + i/2^{ζ}}{2^{s+K−ζ}} )

so that if we let s′ = s + K − ζ and j′ = j2^{K−ζ} + i/2^{ζ}, then we have d = x_{j′}^{s′}, and

e = x_{j′+1}^{s′} ≤ x_{j+1}^{s} = b.

Since f is affine on [a, b] and [d, e] ⊆ (a, b], we have that f is affine on [d, e].

We have

f(d) = h (\frac{k}{2^{t}} + \frac{i/2^{ζ}}{2^{s+K+p−ζ}} )

and λ(f(d)) = t + K + p − ζ > t ≥ K. The only point left to argue is that the slope of f to the right of d is not the natural slope of the pair (d, f(d)). We note that if we let t′ = t + K + p − ζ and k′ = k2^{K+p−ζ} + i/2^{ζ}, then f(d) = x_{k′}^{t′}.

From the discussion in Section 10.2, we have that the natural slope of a pair of points (x_{β}^{α}, x_{δ}^{γ}) is the ratio L(I_{δ}^{γ})/L(I_{β}^{α}) as long as α − λ(x_{β}^{α}) = γ − λ(x_{δ}^{γ}) ≥ K. Note that α − λ(x_{β}^{α}) = z(β) and γ − λ(x_{δ}^{γ}) = z(δ) where z() is the “number of trailing zeros” function defined in Section 11.1.

Let q be a non-negative integer. We have

d = h (\frac{j}{2^{s}} + \frac{2^{q}i}{2^{s+K+q}} ) , and f(d) = h (\frac{k}{2^{t}} + \frac{2^{q}i}{2^{t+K+p+q}} ) .

Since d is the leftmost point in [a, b] at which h^{−1}fh has a break, we know, for every r with 1 ≤ r < 2^{q}i, that

(11-4)  Σ(x_{β(r)}^{α}) = Σ(x_{δ(r)}^{γ}).

From (11-4) and (11-2), we know, for every r with 0 ≤ r < 2^{q}i, that

(11-5)  f carries I_{β(r)}^{α} affinely onto I_{δ(r)}^{γ}

where α = s + K + q, γ = t + K + p + q, β(r) = 2^{K+q}j + r and δ(r) = 2^{K+p+q}k + r so that

x_{β(r)}^{α} = h (\frac{j}{2^{s}} + \frac{r}{2^{s+K+q}} ) , and x_{δ(r)}^{γ} = h (\frac{k}{2^{t}} + \frac{r}{2^{t+K+p+q}} ) .

We know that (11-4) fails when r = 2^{q}i, so (11-5) must fail for this value of r as well.

We know that L(I_{δ(r)}^{γ})/L(I_{β(r)}^{α}) is the natural slope of the pair (x_{β(r)}^{α}, x_{δ(r)}^{γ}) as long as z(β(r)) = z(δ(r)) ≥ K. Since 1 ≤ i < 2^{K}, those values of r with 1 ≤ r ≤ 2^{q}i < 2^{K+q} have z(β(r)) = z(r) and z(δ(r)) = z(r). We now let q = K and r = 2^{q}i = 2^{K}i. For this r, we have z(r) ≥ K so that L(I_{δ(r)}^{γ})/L(I_{β(r)}^{α}) is the natural slope of the pair (x_{β(r)}^{α}, x_{δ(r)}^{γ}) = (d, f(d)). But (11-5) fails for this value of r and f is affine on all of I_{β(r)}^{α} ⊆ [d, e]. Thus we know that the slope of f to the right of d must be different from the natural slope of the pair (d, f(d)). This completes the proof of Theorem 3.

Part V. Examples

In the next two sections we give examples that illustrate the necessity of the various hypotheses. The first section sets up the machinery by which we build the examples and the second section gives the examples themselves.

12. Machinery.

It is very easy to build examples. We essentially give a converse to Section 7. From Lemma 6.4 and the proof of Lemma 6.3 we get the following half of Lemma 6.3.

Lemma 12.1. Let h : S_{n−1} → S_{n−1} be an orientation preserving homeomorphism for which h(Z[\frac{1}{n}]) ⊆ Z[\frac{1}{n}], and assume that hν_{n}h^{−1} is in \overline{T}_{n,n−1} . Then hBT_{n,n−1}h^{−1} ⊆ BT_{n,n−1} .

The next step is to build homeomorphisms h that conjugate ν_{n} into \overline{T}_{n,n−1} . However, ν_{n} is an expanding map, so that building its conjugate is almost equivalent to building the conjugator. Let g be an element of \overline{T}_{n,n−1} for which there is a Markov partition P that has the following properties.

(1) P is a collection {I_{0}, I_{1}, …, I_{p−1}} closed intervals of S_{n} whose union is S_{n}.

(2) The I_{i} are disjoint except for their endpoints.

(3) Regarding the subscripts modulo p, we have that (a) each I_{i} intersects only I_{i−1} and I_{i+1} ,

(b) the I_{i} are arranged in counter-clockwise order around S_{n} as the subscripts increase, and

(c) g carries each I_{i} affinely onto I_{ni} ∪ I_{ni+1} ∪ ⋯ ∪ I_{ni+n−1} .

We call such a partition of g an affine, n-ary Markov partition for g. We let x_{i} = I_{i−1}∩I_{i}. We have the following.

Lemma 12.2. Let g be an element of \overline{T}_{n,n−1} that has an affine, n-ary Markov partition P. Then there is an orientation preserving homeomorphism h for which g = hν_{n}h^{−1} . If we know that the vertices of P are in Z[\frac{1}{n}] and the number of intervals in P is divisible by (n − 1), then h(Z[\frac{1}{n}]) ⊆ Z[\frac{1}{n}].

Proof: This is standard. Let p be the number of intervals in P. We define a Markov partition Q for ν_{n} that has p intervals by setting y_{i} = (n − 1)/pi for o ≤ i < p and setting J_{i} = [y_{i−1}, y_{i}] with subscripts taken modulo p. We form derived partitions of P by using g and Q by using ν_{n} as discussed in Section 7. It is clear that the endpoints in the derived partitions of Q are dense in S_{n−1} .

Let (a, b) be an open interval in S_{n−1} . To show that an endpoint of a derived partition of P is in (a, b), we must show that some image g^{k}(a, b) of (a, b) contains an endpoint of P. If (a, b) does not already contain an endpoint of P, then (a, b) lies in some I_{i} of P. The length of (a, b) equals rL(I_{i}) for some real r with 0 < r ≤ 1. If g(a, b) contains no endpoint of P, then g(a, b) lies in some I_{j}. Since g is affine on I_{i}, the length of g(a, b) equals r′L(I_{j}) with r < r′ ≤ 1 and the ratio r′/r depends only on i and j. There are only finitely many pairs of intervals from P and so each application of g increases the fraction of an interval in P occupied by the image of (a, b) by an amount that is at least some fixed α > 1. Eventually some image of (a, b) under a power of g must contain an endpoint of P. Thus the endpoints in the derived partitions of P are dense in S_{n−1} .

Now we take endpoints of the derived partitions of Q to the corresponding endpoints of the derived partitions of P and we have built a function h on a dense subset of S_{n−1} . Since the endpoints of the derived partitons of P are dense in S_{n−1} , the function h extends to a continuous function that has a continuous inverse.

We know that the element g of \overline{T}_{n,n−1} preserves the sets Z[\frac{1}{n}], Q−Z[\frac{1}{n}] and S_{n,n−1}−Q. If we now assume that the endpoints of P are in Z[\frac{1}{n}], then we have that all endpoints of the derived partitions of P are in Z[\frac{1}{n}]. If the number of intervals in P is divisible by (n − 1), then the fixed points of ν_{n} (the integer points in S_{n−1} ) are in the endpoints of Q. The elements of Z[\frac{1}{n}] are precisely the preimages of the integer points in S_{n−1} under iterates of ν_{n} and thus must show up in the endpoints of the derived partitions of Q. This will give that h takes Z[\frac{1}{n}] into Z[\frac{1}{n}].

We now see how to build examples. We will build examnples for n = 2. We will build functions g that are conjugate to the doubling map ν_{2} : S_{1} → S_{1} and that are elements of \overline{T}_{2,1} . Since we wish to have the conjugating homeomorphism h have h(Z[\frac{1}{2}]) ⊆ Z[\frac{1}{2}], we will build g from an affine, binary Markov partition with (2 − 1)2^{m} = 2^{m} intervals whose endpoints are in Z[\frac{1}{2}]. From Lemma 12.1, we will know that the conjugator h will satisfy hBT_{2,1}h^{−1} ⊆ BT_{2,1} . Since Δ_{2} = Z[\frac{1}{2}], we know from Lemma 2.7 that BT_{2,1} = T_{2,1} , so that we will have hT_{2,1}h^{−1} ⊆ T_{2,1} . From the proof of half of Lemma 4.3, we will have that a lift h̃ of h to R, will satisfy h̃BP L_{n}(R)h̃^{−1} ⊆ BP L_{n}(R). From Lemma 2.5, we get that h̃ ker(d_{n})h̃^{−1} ⊆ ker(d_{n}). We note that the lift h̃ of h commutes with the translation x ↦ x + (n − 1 on R. This fact, the fact that F_{n} ⊆ ker(d_{n}) and the definition of F_{n} imply that h̃ will satisfy h̃F_{n}h̃^{−1} ⊆ F_{n}.

The easiest way to give an affine, binary Markov partition of S_{1} is to give the sequence of lengths {L(I_{i})}. Since we know that these lengths must add up to 1, we can give these lengths in arbitrary units with the understanding that the final lengths must be normalized to add up to 1. Note that this determines g only up to conjugation by a rotation since we do not say what the values of the endpoints are. We adopt the convention that the endpoint x_{0} that is the intersection of the first and last intervals is the point 0 in S_{1} . This restricts the set of examples, but not the qualities obtained since conjugation by a rotation does not change any of the properties that we are interested in.

For example, the sequence

(12-1)  2, 2, 3, 1, 4, 2, 1, 1, 2, 2, 3, 1, 2, 2, 2, 2

defines a sequence of 16 intervals lengths. The sum of the lengths given is 32 so that the true length of each interval is 1/32 times the lengths given. From this it follows that all the endpoints are in Z[\frac{1}{2}]. It is easily checked that the function g defined by this partition is in \overline{T}_{2,1} . For example, the first interval I_{0} is of length 2 (in units of 1/32) and is carried to the union I_{0} ∪ I_{1} of the first two intervals which has length 4. Thus the slope of g on I_{0} is 2. Similarly

\frac{L(I_{2} ∪ I_{3})}{L(I_{1})} = \frac{L(I_{4} ∪ I_{5})}{L(I_{2})} = \frac{L(I_{6} ∪ I_{7})}{L(I_{3})} = 2

so that g has slope 2 on I_{1} , I_{2} and I_{3} , but L(I_{8} ∪ I_{9})/L(I_{4}) = 1 so that g has slope 1 on I_{4} . This gives a break of −1 at x_{4} = I_{3} ∩ I_{4} . By summing lengths, we have x_{4} = 8/32 = 1/4. Further calculations give g breaks of +1 at x_{5} = 3/8 and x_{6} = 7/16 and −1 at x_{8} = 1/2. The values of Σ() are −2, 0, −1, −1, −2, 0, −2, −1 at the endpoints of the stable level x_{1}, x_{3}, x_{5}, x_{7}, x_{9}, x_{11}, x_{13}, x_{15} respectively.

The fact that the stable level does not have a constant value for Σ() implies that h is not PL. This is a much easier observation to make than by all the calculations given above. We leave the next lemma as a very easy exercise for the reader.

Lemma 12.3. Let g ∈ \overline{T}_{2,1} have an affine, binary Markov partition P with 2k intervals. The homeomorphism h that conjugates ν_{2} to g is PL if and only if for every i with 0 ≤ i < k we have L(I_{2i}) = L(I_{2i+1}).

We can refer to the condition in the lemma as the equal pairs condition. It is easier to state than the condition for the piecewise linearity of h in Section 10.1, but we found it harder to combine with the criterion for the piecewise linearity of h^{−1}ν_{n}h in Section 10.2. It turns out that there is a nice inductive proof using the expanding properties of the doubling map on the circle that the criterion of Section 10.1 (for n = 2) implies the equal pairs condition. For n = 2, this might give an easier argument than that of Section 10.1 that the criterion there implies the piecewise linearity of h (it would eliminate the need for the calculation that verifies (10-1)), but it would hide the rather direct construction of a PL homeomorphism given the criterion. We do not know how much the arguments change when n = 2 is not assumed.

13. The examples. Example 1: Most of the analysis of Part IV was discovered by studying this example. We use the partition defined by the sequence of lengths in (12-1). This gives an example of a non-PL homeomorphism h that conjugates ν_{2} into \overline{T}_{2,1} , and, by the remarks in the previous section, conjugates T_{2,1} into T_{2,1} and has lifts that conjugate F_{2} into F_{2} . In addition, the function g = hν_{2}h^{−1} has zero break at its fixed point 0. This makes the function Σ() well defined. Since

(13-1),  g^{b}(x) = Σ(x) − Σ(g(x))

it also makes the non-linearity of g a “coboundary.” Thus this example shows that the existence of the function Σ() and the equation (13-1) are not sufficient to reach the conclusion of Theorem 3. We note that the right hypotheses to replace (13-1) and the existence of Σ() seems to be the assumption that the following stamement fails for only finitely many pairs of points x and y in S_{n−1} :

(∗) If x and y have g^{p}(x) = g^{q}(y) for some positive integers p and q, then (g^{p})^{b}(x) = (g^{q})^{b}(y).

Example 2: This example is given by the sequence of 6 lengths

2, 2, 1, 1, 1, 1

which totals to 8 = 2^{3} . Since it satisfies the equal pairs condition, the conjugating homeomorphism h is PL. Since the number of intervals is not a power of 2, there are points in the endpoints of the derived partitions of Q that are not in Z[\frac{1}{2}]. Thus we will have h(Z[\frac{1}{2}]) ⊆ Z[\frac{1}{2}], but not h(Z[\frac{1}{2}]) = Z[\frac{1}{2}]. Thus we have a PL homeomorphism h that conjugates T_{2,1} into T_{2,1} but cannot conjugate T_{2,1} onto T_{2,1} . The inverse of h must conjugate T_{2,1} onto a group of PL homeomorphisms of S_{1} that properly contains T_{2,1} . Remark: We do not have an example of a non-PL homeomorphism h so that h conjugates ν_{2} into \overline{T}_{2,1} and h^{−1} conjugates ν_{2} to a PL function. Thus we do not know whether the hypothesis that h^{−1}ν_{2}h be in \overline{T}_{2,1} in Theorem 3 can or cannot be replaced by the hypothesis that h^{−1}ν_{2}h be PL. Example 3: This example is given by the sequence of 16 lengths

1, 1, 3, 1, 2, 4, 1, 1, 1, 1, 6, 2, 2, 2, 2, 2

which total to 32 = 2^{5} . Here the conjugator h fails to have h(Z[\frac{1}{2}]) = Z[\frac{1}{2}] in spite of the fact that there are 2^{4} intervals. It is easy to check that the midpoint of I_{5} (the unique interval of length 4) is a point of period 2 under the action of g. This is the point 10/32 = 5/16 and cannot be the image of any element of Z[\frac{1}{2}] since the only points of period 2 under the action of ν_{2} are the points 1/3 and 2/3.

Example 4: This example is given by the sequence of 8 lengths

1, 3, 4, 2, 1, 3, 1, 1

which total to 16 = 2^{4} . This example has no well defined function Σ() since the break at the fixed point is not zero.

Example 5: This example is given by the sequence of 18 lengths

1, 1, 3, 1, 2, 1, 3, 1, 2, 2, 1, 3, 2, 1, 1, 3, 2, 2

which total to 32 = 2^{5} . The points x_{6} and x_{12} form a cycle of period 2 and g^{b}(x_{6}) = −2 while g^{b}(x_{12}) = +1. Even though the g^{b}(0) = 0, we cannot define Σ() because the sum of the breaks on a future orbit that contains x_{6} and x_{12} does not converge.

Bibliography

1. R. Bieri and R. Strebel, On groups of PL-homeomorphisms of the real line, preprint, Math. Sem. der Univ. Frankfurt, Frankfurt, 1985.

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

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

4. , The geometry of finitely presented infinite simple groups, Algorithms and Classification in Combinatorial Group Theory, G. Baumslag and C. F. Miller, III, Eds., MSRI Publications, Number 23, Springer-Verlag, New York, 1991, pp. 121–136.

5. , The geometry of rewriting systems: a proof of the Anick-Groves-Squier Theorem, ibid, pp. 137–163.

6. K. S. Brown and R. Geoghegan, An infinite-dimensional torsion-free F P_{∞} group, Invent. Math. 77 (1984), 367–381.

7. J. W. Cannon, W. J. Floyd and W. R. Parry, Notes on Richard Thompson’s groups F and T , Research Report GCG63, The Geometry Center, Univ. Minn., 1994.

8. C. G. Chehata, An algebraically simple ordered group, Proc. Lond. Math. Soc. (3) 2 (1952), 183–197.

9. S. Cleary, Groups of piecewise-linear homeomorphisms with irrational slopes, to appear in Rocky Mountain J. Math.

10. J. Dydak and J. Segal, Shape Theory: An Introduction, Lecture Notes in Math., Number 688, Springer-Verlag, Berlin, 1978.

11. E. Ghys and V. Sergiescu, Sur un groupe remarquable de difféomorphismes du cercle, preprint IHES/M/85/65, Institut des Hautes Études Scientifiques, Bures-sur-Yvette, 1985.

12. , Sur un groupe remarquable de difféomorphismes du cercle, Comment. Math. Helvetici 62 (1987), 185–239.

13. P. Greenberg, Pseudogroups from group actions, Amer. J. Math. 109 (1987), 893–906.

14. , Projective aspects of the Higman-Thompson group, Group Theory from a Geometrical Viewpoint, ICTP conference, Triest, Italy, 1990, E. Ghys, A. Haefliger, A. Verjovsky, Editors, World Scientific, Singapore, 1991, pp. 633–644.

15. P. Greenberg and V. Sergiescu, An acyclic extension of the braid group, Comm. Math. Helvetici 66 (1991), 19–138.

16. H. M. Hastings and A. Heller, Homotopy idempotents on finite-dimensional complexes split, Proc. Amer. Math. Soc. 85 (1982), 619–622.

17. S. H. McCleary, Groups of homeomorphisms with manageable automorphism groups, Comm. in Algebra 6 (1978), 497–528.

18. S. H. McCleary and M. Rubin, Locally moving groups and the reconstruction problem for chains and circles, preprint, Bowling Green State University, Bowling Green, Ohio.

19. R. McKenzie and R. J. Thompson, An elementary construction of unsolvable word problems in group theory, Word Problems, Boone, Cannonito and Lyndon Eds., North Holland, 1973.

20. J. N. Mather, Integrability in codimension 1, Comment. Math. Helvetici 48 (1973), 195–233.

21. E. A. Scott, A tour around finitely presented infinite simple groups, Algorithms and Classification in Combinatorial Group Theory, G. Baumslag and C. F. Miller, III, Eds., MSRI Publications, Number 23, Springer-Verlag, New York, 1991, pp. 83–119.

22. M. Stein, Groups of piecewise linear homeomorphisms, Trans. Amer. Math. Soc. 332 (1992), 477–514.