Combinatorial and metric properties of Thompson's group T

COMBINATORIAL AND METRIC PROPERTIES OF THOMPSON’S GROUP T JOS´ E BURILLO, SEAN CLEARY, MELANIE STEIN, AND JENNIFER TABACK Abstract. We discuss metric and combinatorial properties of Thompson’s group T, such as the normal forms for elements and uniqueness of tree pair diagrams. We relate these properties to those of Thompson’s group Fwhen possible, and highlight combinatorial differences between the two groups. We define a set of unique normal forms for elements of Tarising from minimal factorizations of elements into convenient pieces. We show that the number of carets in a reduced representative of Testimates the word length, that Fis undistorted in T, and that cyclic subgroups of Tare undistorted. We show that every element of Thas a power which is conjugate to an element of Fand describe how to recognize torsion elements in T. 1. Introduction Thompson’s groups F,Tand Vare a remarkable family of infinite, finitely-presentable groups studied for their own interesting properties as well as for their connections with questions in logic, homotopy theory and measure theory of discrete groups. Cannon, Floyd and Parry give an excellent introduction to these groups in [5]. These three groups can be studied either algebraically, analytically or geometrically. Algebraically, each has both finite and infinite presentations. Geometrically, an element in each group can be viewed as a tree pair diagram; that is, as a pair of finite binary rooted trees with the same number of leaves, with a numbering system pairing the leaves in the two trees. Analytically, an element of each group can be viewed as a self map of the unit interval: •in Fas a piecewise linear homeomorphism, •in Tas a homeomorphism of the unit interval with the endpoints identified, and thus of S1, Date: April 3, 2005. The first, second and fourth authors acknowledge support from NSF International Collaboration grant DMS-0305545 and are grateful for the hospitality of the Centre de Recerca Matem`atica. 1 2 JOS´ E BURILLO, SEAN CLEARY, MELANIE STEIN, AND JENNIFER TABACK •in Vas a right-continuous bijection which is locally orientation preserving. Thompson’s group Fin particular has been studied extensively. The group Fhas a standard infinite presentation in which every element has a unique normal form, and a standard two-generator finite presentation. Fordham [8] presented a method of computing the word length of w∈F with respect to the standard finite generating set directly from the tree pair diagram representing w. Regarding Fas a diagram group, Guba [10] also obtained an effective geometric method for computing the word metric with respect to the standard finite generating set. Belk and Brown [1] have similar results which arise from viewing elements of Fas forest diagrams. In this paper, we discuss analogues for Tof some properties of F, such as normal forms for elements. We consider metrically how Fis contained as a subgroup of T, and show that the number of carets in a reduced tree pair diagram representing w∈Testimates the word length of wwith respect to a particular generating set. We show that cyclic subgroups of Tare undistorted and that every element of Thas a power which is conjugate to an element of F. The groups Tand V, unlike F, contain torsion elements, and we describe how to recognize these torsion elements from their tree pair diagrams. 2. Background on Thompson’s groups Fand T 2.1. Presentations and tree pair diagrams. Thompson’s groups Fand Tboth have representations as groups of piecewise-linear homeomorphisms. The group Fis the group of orientation-preserving homeomorphisms of the interval [0,1], where each homeomorphism is required to have only finitely many discontinuities of slope, called breakpoints, have slopes be powers of two and have the coordinates of the breakpoints all lie in the set of dyadic rationals. Similarly, the group Tconsists of orientation-preserving homeomorphisms of the circle S1satisfying the same conditions where we represent the circle S1as the unit interval [0,1] with the two endpoints identified. Cannon, Floyd and Parry give an excellent introduction to Thompson’s groups F,Tand Vin [5]. We refer the reader to this paper for full details on results mentioned in this section. Both Fand Tcan be studied either through finite or infinite presentations. With respect to the infinite presentation hxi, i ≥0|xjxi=xixj+1, i < ji for F, group elements have simple normal forms which are unique. It is easy to see that Fcan be generated by x0and x1, which form the standard finite generating set for F, and yield the finite presentation COMBINATORIAL AND METRIC PROPERTIES OF THOMPSON’S GROUP T3 hx0, x1|[x0x−1 1, x−1 0x1x0],[x0x−1 1, x−2 0x1x2 0]i. The group Talso has both a finite and an infinite presentation. The infinite presentation is given by two families of generators, {xi, i ≥0}, the same generators as in the infinite presentation of F, a family {ci, i ≥0}of torsion elements, and the following relators: (1) xjxi=xixj+1, if i < j (2) cnxk=xk+1cn+1, if k < n (3) cn=x0c2 n+1 (4) cnxn=cn+1. Using the first three relators, we see that only the generators x0,x1and c1are required to generate the group, since the other generators can be obtained from these three. In the following, we will use cto denote the generator c1. The group Tis finitely presented using the following relators, both with respect to the infinite generating set and the finite generating set {x0, x1, c}: (1) [x0x−1 1, x−1 0x1x0] (2) [x0x−1 1, x−2 0x1x2 0] (3) c2x1=x2c3, (that is, x−1 1cx0=cx1) (4) c1=x0c2 2, (that is, c=x0(x−1 1cx0)2) (5) c1x1=c2, (that is, x−1 1cx0x1=x−1 0x1x0x−2 1cx2 0) (6) c3= 1. As with Thompson’s group F, we will frequently work with the more convenient infinite set of generators when constructing normal forms for elements and performing computations in the group. We will need to express elements with respect to the finite generating set when discussing word length. A convenient representation for an element win For Tis a tree pair diagram, as discussed in [5]. A tree pair diagram is a pair of finite rooted binary trees with the same number of vertices, together with a numbering of the valence one vertices. A node of the tree together with its two downward directed edges is called a caret. Valence one vertices of these trees are called exposed leaves. In F, we insist that both leaf numberings begin at 0 and increase from left to right. In T, the numberings need only increase cyclically from left to right. The left side of the tree consists of the root caret, and all carets connected to the root by a path of left edges; the right side of the tree is defined analogously. A caret is called a left caret if its left leaf lies on the left side of the tree. A caret is called a right caret if it is not the root caret and its right leaf lies on the right side of the tree. All other carets are called interior. 4 JOS´ E BURILLO, SEAN CLEARY, MELANIE STEIN, AND JENNIFER TABACK A caret is called exposed if it contains two exposed leaves. We write w= (T−, T+) to express was a tree pair diagram, and refer to T−as the source tree and T+as the target tree. Such a tree pair diagram is not unique. There are many possible diagrams representing a given element. We can choose the cyclic ordering for elements of Tto always begin with 0 on the leftmost leaf of the source tree, and furthermore we impose a natural reduction condition: if w= (T−, T+) and both trees contain a caret with two exposed leaves numbered nand n+ 1, then we remove these carets and renumber the leaves, thus forming a representative for wwith fewer carets and leaves. A tree pair diagram which admits no such reductions is called a reduced tree pair diagram, and any element of Fis represented by a unique reduced tree pair diagram. When we write w= (T−, T+) below, we are assuming that the tree pair diagram is reduced unless otherwise specified. When w∈For w∈T, we denote the number of carets in either tree of a tree pair diagram representing wby N(w). When pis a word in the generators of For T, then prepresents an element win either For T, and we write N(p) interchangeably with N(w). If w= (T−, T+)∈F, then the leaves in both trees are numbered from left to right, beginning with zero. In this case, the subdivisions of the interval are paired in increasing order, so that the intervals with zero as their left endpoint are paired, and the intervals with one as their right endpoint are paired. We may omit leaf numberings for elements of Ffor brevity without any ambiguity. If w∈T, then wcorresponds to a homeomorphism of S1 rather than [0,1]. In elements of T, we can omit most leaf numbers for brevity by adopting the following convention from [5]: we understand the leaves in the source tree to be numbered from 0 to nbeginning with the leftmost leaf, and indicate by a circle or zero which of the leaves in the target tree is paired with the first leaf in the source tree. Other leaf numberings can be deduced from this single mark using the cyclic order. For this reason, we often refer to tree pair diagrams representing elements of Tas marked tree pair diagrams. For example, the element ccorresponds to the homeomorphism of S1 given by c(t) =    1 2t+3 4if 0 ≤t < 1 2 2t−1 if 1 2≤t < 3 4 t−1 4if 3 4≤t≤1 and has the marked tree pair diagram given in Figure 1. 2.2. Group Multiplication in Fand T.Group multiplication in Fand Tcorresponds to composition of homeomorphisms, which we can interpret on the level of tree pair diagrams as well. First, we consider u, v ∈F, where COMBINATORIAL AND METRIC PROPERTIES OF THOMPSON’S GROUP T5 Figure 1. The tree pair diagram for the generator cin T. u 210 4 3 43 21 0 0 0 1 2 3 4 3 4 1 2 v Figure 2. The tree pair diagram for sample elements u and vin T. u= (T−, T+) and v= (S−, S+). To compute the tree pair diagram corresponding to the product vu, we create unreduced representatives (T0 −, T0 +) and (S0 −, S0 +) of the two elements in which T0 +=S0 −. Then the product is represented by the possibly unreduced tree pair diagram (T0 −, S0 +). To multiply tree pair diagrams representing elements of Twe follow a similar procedure. We let u, v ∈T, where u= (T−, T+) and v= (S−, S+). To compute the tree pair diagram corresponding to the product vu, we create unreduced representatives (T0 −, T0 +) and (S0 −, S0 +) of the two elements in which T0 +=S0 −as trees. The product vu will be represented by the pair (T0 −, S0 +) of trees. To decide which leaf in S0 +to mark with the zero, we just note that it should be the leaf which is mapped onto by the zero leaf in T0 −. To identify this leaf, we find the zero leaf in T0 +. Since T0 +=S0 − as trees, this leaf viewed as a leaf in S0 −will be labelled m. Then the leaf labelled min S0 +will be the new zero leaf in the tree pair diagram (T0 −, S0 +) for vu. Alternately, we can follow the composition in both pairs of trees to see how the leaves map to each other. This constructed tree pair diagram will represent vu and is not necessarily reduced. For an example of this multiplication, see Figures 2, 3 and 4. 3. Words and diagrams 3.1. Normal forms and tree pair diagrams in F.With respect to the infinite presentation for Fgiven above, every element of Fhas a unique normal form. To describe these, we first observe that any wcan be written in the form w=xr1 i1xr2 i2. . . xrk ikx−sl jl. . . x−s2 j2x−s1 j1 6 JOS´ E BURILLO, SEAN CLEARY, MELANIE STEIN, AND JENNIFER TABACK v 2 31 45 0 0 1 2 3 45 0 3 1 2 45 3 21 0 45 u Figure 3. Unreduced versions of uand vfor the multiplication vu in T, with carets added to perform the multiplication indicated with dashes. Now the target tree of uhas the same shape as the source tree of v, allowing the composition. vu 3 21 0 45 23 4 1 5 0 Figure 4. The tree pair diagram representing the product vu. where ri, si>0, 0 ≤i1< i2. . . < ikand 0 ≤j1< j2. . . < jl. However, this expression is not unique. Uniqueness is guaranteed by the addition of the following condition: when both xiand x−1 ioccur in the expression, so does xi+1 or x−1 i+1, as discussed by Brown and Geoghegan [2]. When we refer to elements of Fin normal form, we mean this unique normal form. If the normal form for w∈Fcontains no generators with negative exponents, we refer to was a positive word and similarly, we say a normal form is a negative word if there are no generators with positive exponents. We call any word which has the form w=xr1 i1xr2 i2. . . xrk ikx−sl jl. . . x−s2 j2x−s1 j1 where ri, si>0, 0 ≤i1< i2. . . < ikand 0 ≤j1< j2. . . < jl, a word in pq form, where pis the positive part of the normal form and qthe negative part. The normal form for an element of Fis the shortest word among all words in pq form representing the given element. COMBINATORIAL AND METRIC PROPERTIES OF THOMPSON’S GROUP T7 To any (not necessarily reduced) tree pair diagram (T−, T+) for an element of Fwe may associate a word in pq form representing the element, using the leaf exponents in the target and source trees. When the leaves of a finite rooted binary tree are numbered from left to right, beginning with zero, the leaf exponent of leaf kis the integer length of the longest string of left edges of carets which originates at leaf kand does not reach the right side of the tree. A tree pair diagram then gives the word xr1 i1xr2 i2. . . xrn inx−sm jm. . . x−s2 j2x−s1 j1 precisely when leaf ikin T+has exponent rk, leaf jkin T−has leaf exponent sk, and generators which do not appear in the word correspond to leaves with exponent zero. We think of this word as the pq factorization of the element given by the particular tree pair diagram. On the other hand, any word in pq form can be translated into a tree pair diagram. Furthermore, under this correspondence for F, reduced tree pair diagrams correspond exactly to normal forms. For examples of this correspondence, see [5, 6, 7]. We observe that if an exposed caret has leaves numbered iand i+1, then leaf i+ 1 must have leaf exponent zero, since it is a right leaf. If both trees in a tree pair diagram have exposed carets with leaves numbered iand i+1, then the corresponding normal form, computed via leaf exponents, contains the generators xito both positive and negative indices, but no instances of the generator xi+1. This is precisely the situation when the normal form can be reduced by a relator of F. Thus the condition that the normal form is unique is exactly the condition that the tree pair diagram is reduced. This correspondence will be extended to elements of Tin the next section. 3.2. Tree pair diagrams for elements of T.We now discuss the relationship between words in Tand tree pair diagrams. The relationship is more complicated in Tthan it is in F. The representation of elements of T by marked tree pair diagrams suggests a way to decompose an element of T into a product of three elements: the positive and negative parts together with a torsion part in the middle, as described in [5]. Definition 3.1. Let the marked tree pair diagram (T−, T+)represent g∈T. If T−and T+each have i+1 carets, then we let Rbe the all-right tree which has i+ 1 carets, all of which lie on the right side of the tree. We can write gas a product of: (1) a∈Fwith tree pair diagram (T−, R)and ahas negative normal form u, (2) a cyclic permutation cj ifor some iwhere 1≤j≤i+ 1 (which permutes the leaf numbering in R), and 8 JOS´ E BURILLO, SEAN CLEARY, MELANIE STEIN, AND JENNIFER TABACK q pc Figure 5. Three tree pair diagrams representing the word x1x2c5 5x−2 2x−1 1x−2 0factorized as pcq. (3) b∈Frepresented by (R, T+), where bhas positive normal form v, ignoring the leaf numbering on T+. Then the word w=vcj iuis called the pcq factorization of gassociated to the marked tree pair diagram (T−, T+). In the special case where g∈F⊂T, the pcq factorization will just be the usual pq factorization, as we consider the cpart of the word to be empty. Figure 5 illustrates an example of an element of Tdecomposed in this way. The following theorem follows from the existence of these decompositions, and an algebraic proof of this result is found in [5]. Theorem 3.2 ([5], Theorem 5.7).Any element x∈Tadmits an expression of the form xr1 i1xr2 i2. . . xrn incj ix−sm jm. . . x−s2 j2x−s1 j1, where 0≤i1< i2<· · · < inand 0≤j1< j2<··· < jmand either 1≤j < i + 2 or cj iis not present. We refer to any word satisfying the hypotheses of Theorem 3.2 as a word in pcq form for an element of T(just as words of this form with no cj iterm are called words in pq form in the group F) . Neither proof of the existence of pcq forms gives an easy explicit method for transforming a general word in the generators x±1 i, ciinto pcq form without resorting to drawing tree pair diagrams, so we will outline such a method below. We recall that the four types of relators we are using in Tare: (1) xjxi=xixj+1, if i < j (2) cnxk=xk+1cn+1, if k < n (3) cn=x0c2 n+1 (4) cnxn=cn+1 Lemma 3.3 (Pumping Lemma).The generators xiand cjof Tsatisfy cm n=xm−1cm+1 n+1 if 1≤m < n + 2. Proof. This follows immediately from the relators of the types (2) and (3). tu COMBINATORIAL AND METRIC PROPERTIES OF THOMPSON’S GROUP T9 We consider a word w∈Twritten in the generators {xi, cj}. To put winto pcq form, we must move all the positive powers of the xito the left and all negative powers to the right, leaving only generators ciin the middle. We can use relators of types (1), (2) and (4) to accomplish that in the following way. If there is a cnfollowed by an xk, we apply a relator of type (2) to switch them if n > k. If n≤k, then we use the Pumping Lemma to increase the index of the cnuntil it is large enough, and then we use the equation cm kxk=cm−1 kck+1 =xm−2cm+1 k+1 , where the first equality is a relator of type (4) and the second equality follows from the Pumping Lemma. The same procedure can be used for negative powers of the xiby taking inverses in the relators and the Pumping Lemma. During this process, if two generators of the type xnneed to be moved past each other, we use the relators of type (1). The result of this process is a product of a positive word in F, several powers of different elements of the form cj, and a negative word in F. To combine a product of several cjinto a single element ck, we use the Pumping Lemma. We can always combine cicjto obtain an expression with a single ckby raising the lower index via the Pumping Lemma, at the cost of potentially accumulating some positive powers of xigenerators at the front of the expression or negative powers of xiat the back of the expression. For example, c2 3c5=x1c3 4c5=x1x2c4 5c5=x1x2c5 5. Once the resulting expression contains a single cigenerator, we can again use the relators of type (1), the relators in F, to arrange the positive and negative words so that the generators have the appropriate increasing or decreasing order by index. The relationship between words in pq form and tree pair diagrams in F is different than the relationship between pcq forms and tree pair diagrams in T. In F, every tree pair diagram has a pq factorization associated to it, and any word in pq form is in fact the pq factorization associated to a (not necessarily unique) tree pair diagram. Given any word in pq form, then we can form a tree pair diagram for this element as follows. We consider reduced tree pair diagrams for pand q, and construct a tree pair diagram for the product pq as described in Section 2.2. The middle trees of the four trees involved in the product are all-right trees. The all-right trees in this decomposition may not have the same number of carets, so in forming the diagram for pq we simply enlarge the smaller of the two of these all-right trees (as well as the other tree in that diagram). Since only right carets are ever added during this process, all of whose leaves have leaf exponent zero, 16 JOS´ E BURILLO, SEAN CLEARY, MELANIE STEIN, AND JENNIFER TABACK To obtain lower bound on the word length, one only needs to observe that the tree pair diagram for each generator has either two or three carets. If uis a word in x0,x1and cwith length n, then as these generators are multiplied together, each product may add at most 3 carets to the tree pair diagram. Thus the diagram for uwill have at most 3ncarets. It then follows that N(w)≤3|w|. Combining this with the above inequality, we obtain the desired bounds. tu We use Theorem 5.1 to show that the inclusion of Fin Tis a quasiisometric embedding. This means that there are constants K > 0 and Cso that for any w, z ∈Fwe have 1 KdF(w, z)−C≤dT(w, z)≤KdF(w, z) + C where dFand dTrepresent the word metric in Fand Trespectively, with regard to the generating set {x0, x1}of Fand {x0, x1, c}of T. When considering whether the inclusion of a finitely generated subgroup Hinto a finitely generated group Gis a quasi-isometric embedding, we can instead equivalently show that the distortion function is bounded. The distortion function is defined by h(r) = 1 rmax{|x|Hsuch that x∈H, |x|G≤r}. Word length in Fis comparable to the number of carets in the reduced tree pair diagram representing the word, as seen in [4, 8]. This, combined with Theorem 5.1 easily shows that the distortion function is bounded, and thus proves the following corollary. Corollary 5.2. The inclusion of Fin Tis a quasi-isometric embedding. 5.2. Comparing word length in Fand T.Although Corollary 5.2 shows that Fis quasi-isometrically embedded in T, we now show that the word length of certain elements of Fdoes not change when these elements are considered as elements of T, with respect to natural finite generating sets. For this, we use the standard finite generating set {x0, x1}for Fand the generating set {x0, x1, t}for T, where t=c0is the non-identity element of Tin which each tree has a single caret. This element corresponds to a rotation of the unit circle of order 2. We use tinstead of c=c1for the third generator because we are interested in understanding how multiplication by generators can change the number of carets, which is more straightforward using tthan c. To find elements which have the same length in Fand Twith respect to these generating sets, we consider the process by which they are constructed. COMBINATORIAL AND METRIC PROPERTIES OF THOMPSON’S GROUP T17 A geodesic word an· · · a2a1in the generators {x0, x1, t}representing w∈ F⊂Tdescribes how a tree pair diagram for w= (T−, T+) is created by successively applying the generators akto the tree pair diagram for the word ak−1· · · a2a1, as kincreases from 1 to n. We begin with the identity element of Tand its reducible tree pair diagram consisting of two identical trees with one caret each, and multiply first by a1. This changes the tree pair diagram of the identity element by creating some new carets or adding a marking. As each successive generator is added to the product, the number of carets in the existing tree pair diagram may increase, decrease or remain the same. If the number of carets increases, it can increase by at most two since each generator has at most two carets in addition to the root caret. In other cases, the number of carets may remain the same or decrease. When all generators in the sequence an···a2a1have been added to the product, the resulting tree pair diagram is (T−, T+). We now carefully analyze the circumstances under which a single generator in this product can add two carets to an existing tree pair diagram. Lemma 5.3. If w∈Tis a non-identity element, and w6=t, then N(tw) = N(w). Proof. Since the tree pair diagram for tcontains a single caret, no new carets must be added to the tree pair diagram for win order to perform the multiplication tw. It is easy to see that no reduction can occur after multiplication by t.tu Lemma 5.4. Let w= (T−, T+)∈Tbe nontrivial and α∈ {x±1 0, x±1 1, t}. Then N(αw) = N(w) + 2 if and only if α=x±1 1and the right subtree of the root caret of T+is empty. Proof. Since the source tree of the tree pair diagram for x±1 1contains two carets in the right subtree of the root caret, it is clear that these carets must be added to (T−, T+) in order to perform the multiplication, and that the resulting product does not have reducible carets in the right subtree of the root caret in either tree. The tree pair diagram for x±1 0contains two carets in each tree, but one is the root caret, so the maximum number of carets that could be added to (T−, T+) in order to multiply by x±1 0is one. Lemma 5.3 completes the proof. tu We consider the process of constructing the tree pair diagram for a product an· · · a2a1where ai∈ {x±1 0, x±1 1, t}. Let Pi=aiai−1· · · a2a1for 1≤i≤n. We construct the tree pair diagrams for the successive products Pifor i= 1,· · · , n. Each additional generator may either reduce, leave unchanged, increase by one, or increase by two the number of carets in the tree pair diagram corresponding to the suffix Piof Pn. To distinguish those 18 JOS´ E BURILLO, SEAN CLEARY, MELANIE STEIN, AND JENNIFER TABACK generators which add two carets to the tree pair diagram, we will use the letter b, while for other generators we will use the letter a. So we represent an element w∈Tby a string of generators ar· · · ahbk· · · as+1b1as· · · a1 where if atis the generator immediately to the right of bj, then N(bjat· · ·a1)= N(at· · · a1) + 2, and otherwise we have N(as· · · a1)≤N(as−1· · · a1) + 1. Lemma 5.5. If w∈Fand w=ar···ahbk···as+1b1as· · · a1where not all ai∈ {x±1 0, x±1 1}, then there must be at least two indices iand jso that ai=aj=t. Proof. Suppose that in the expression above for w∈F, there was a single letter t. Then we easily obtain t∈F, a contradiction. tu Lemma 5.6. Let w∈Tbe given by an expression of the form ar· · · ahbk· · · as+1b1as· · · a1. Then bj+1 and bjcannot be adjacent in the expression. Note that possibly s= 0 in which case the word ends with b1 and that possibly h−1 = rin which case the word begins with bk. Proof. Let vbe the suffix of the word wto the right of the generator bj. We know from Lemma 5.4 that in a tree pair diagram (R−, R+) for v, the right subtree of the root caret of R+is empty. Since bj=x±1 1, the right subtree of the root caret of S+has one of two forms: two right carets or a right caret with a left child. In either case, the right subtree of the root caret is nonempty, and thus the next generator in the multiplication cannot add two carets to the tree pair diagram, so is not bj+1.tu We now characterize one type of element of Fwhose word length is unchanged when viewed as an element of T, using the generating set {x0, x1} for Fand {x0, x1, t}for T. These are elements w∈Ffor which N(w) exceeds the word length |w|F. Fordham [8] computes |w|Fby assigning an integer weight between zero and four to each pair of carets in the tree pair diagram representing w. In a given word there are at most two weights of zero. Here we investigate words in which most weights are one. Such words, for example, are represented by tree pair diagrams with no interior carets having right children. Theorem 5.7. If w∈Fwith N(w)≥ |w|F+ 1 then |w|T=|w|F, where word length if computed with respect to the generating set {x0, x1}for F and {x0, x1, t}for T. We immediately obtain the following corollary, since |xn 0|F=|xn 1|F=n, while N(xn 0) = n+ 1 and N(xn 1) = n+ 3. COMBINATORIAL AND METRIC PROPERTIES OF THOMPSON’S GROUP T19 Corollary 5.8. The elements xn 0and xn 1have word length nin both Fand T with respect to the finite generating sets {x0, x1}and {x0, x1, t}respectively. We now prove Theorem 5.7. Proof. Suppose w∈Fcan be written as w=ar· · · a2a1where ai∈ {x±1 0, x±1 1, t}, and r < n =|w|F. If aiis a generator which adds two carets to the tree pair diagram, then rename this generator bj. So we rewrite the expression for was w=ap· · · bk· · · as+1b1as· · · a1 with r=p+kwhere kis the number of bjgenerators. By Lemma 5.6 we have k−1≤p, and we know from Lemma 5.4 that bi=x±1 1. We first prove the following lemma relating to this expression for w: Lemma 5.9. Let ap· · · ahbk· · · bjat· · · as+1b1as· · · a1be an expression for a word w∈T, where each bj=x±1 iis a generator which adds two carets to the tree pair diagram, and each aiis a generator from the set {x±1 0, x±1 1, t} which adds at most one caret to the tree pair diagram. We consider the generators akwhich appear between bj+1 and bj. (1) There is at least one generator between bj+1 and bjwhich does not increase the number of carets. (2) Let aJbe the generator between bj+1 and bjand closest to bj+1 such that if vJis the suffix of wimmediately to the right of aJ, then the right subtree of the the target tree of vJis nonempty, but the right subtree of the target tree of aJvJis empty. If aJ=tand bjis not the rightmost generator in the expression for w, then there is another generator aLbetween bj+1 and bjwhich does not add carets to the tree pair diagram. Proof. We know that bj+1 =x±1 1, and for multiplication by bj+1 to add two carets to the tree pair diagram, the target tree of the tree pair diagram for the suffix of wimmediately following bj+1 must have an empty right subtree. We also know that the target tree of the tree pair diagram for the suffix of wbeginning with bjdoes not have an empty right subtree, according to Lemma 5.4. Thus the generator aJin the statement of the lemma must exist. As in the statement of the lemma, let vJdenote the suffix of wimmediately to the right of aJ. We now claim that N(vJ)≥N(aJvJ). If aJ=t then the claim follows from Lemma 5.3. If aJ=x−1 0or aJ=x±1 1, and N(aJvJ) = N(vJ) + 1, then the right subtree of the target tree of aJvJcan never be empty. Thus if aJis one of the above three generators, it can never add a caret to the tree pair diagram of vJ, because we know that the right subtree of the target tree of aJvJmust be empty. 20 JOS´ E BURILLO, SEAN CLEARY, MELANIE STEIN, AND JENNIFER TABACK Suppose that aJ=x0. If N(aJvJ) = N(vJ) + 1, then the right subtree of the target tree of the tree pair diagram for vJmust be empty. But this contradicts the definition of aJ, and thus N(aJvJ)≤N(vJ), and the claim is again true. Now consider the case aJ=twhen bjis not the rightmost generator in the expression for w. Let bj· · · a1= (R−, R+) and vJ= (S−, S+). Since bj=x±1 1, the right subtree of the root caret of R+has one of two forms: two right carets or a right caret with a left child. Let Adenote the left subtree of the root caret of this tree. Denote the right subtree of S+by A0. Since bj is not the rightmost generator in the expression for w, we know that both Aand A0are nonempty. Thus there must be at least one generator between aJand bj. We claim that there must be a generator between aJand bj which does not increase the number of carets in the tree pair diagram. Since the right subtree of the root caret of R+is nonempty, as is the left subtree Aof the root caret, we see immediately that N(x±1 0bj· · · a1)≤ N(bj· · · a1). Similarly, multiplication by b−1 jcannot increase the number of carets in the tree pair diagram (R−, R+), and multiplication by tnever increases the number of carets in any tree pair diagram. Thus the only generator which can precede bjand increase the number of carets in the tree pair diagram is bjitself. Repeat occurrences of bj=x±1 1are written as aiin the expression for w, since they do not increase the number of carets by 2. But the target tree in the tree pair diagram for bm j· · · a1will always have left subtree Aand a nonempty right subtree. Since vJ= (S−, S+) has a tree S+with empty right subtree of the root caret, we see that there must be another generator not equal to bjbetween bm j· · · a1and the leftmost letter in vJ. By the above argument, this generator must not increase the number of carets in the tree pair diagram. Hence there must be another generator between aJand bjwhich does not increase the number of carets in the tree pair diagram. tu According to Lemma 5.9, between each pair of generators bj+1 and bj there is a generator which does not add carets to the tree pair diagram. There are at least k−1 such generators in the expression for w, between bj+1 and bjfor j= 1,2,· · · k−1. In the proof of Lemma 5.9, these generators are denoted aJ. Lemma 5.9 also shows the existence of at least one additional generator which does not increase the number of carets in the tree pair diagram, for the following reason. We can assume that the expression for wcontains at least one generator t, otherwise we would have a word in F. In F, we know that the word length of wis n>r. It follows from Lemma 5.5 that there must be at least two tgenerators in the expression for w. We now prove in COMBINATORIAL AND METRIC PROPERTIES OF THOMPSON’S GROUP T21 three cases that there must be an additional generator in the sequence ap· · · ahbk· · · bjat· · · as+1b1as· · · a1which is not one of the aJgenerators guaranteed by Lemma 5.9, which does not increase the number of carets in the tree pair diagram. (1) If no aJ=t, then we have found two additional generators which do not increase the number of carets in the tree pair diagram, namely the two instances of the generator tguaranteed by Lemma 5.5. (2) If two tgenerators play the role of aJ, one between bj+1 and bj, and the other between bm+1 and bm, then at most one of bjand bm, say bj, can be the rightmost generator in the sequence representing w. Then Lemma 5.9 guarantees one additional generator between bm+1 and bmwhich does not increase the number of carets in the tree pair diagram. (3) If only one of the tgenerators in the expression is an aJgenerator, then the other tgenerator guaranteed by Lemma 5.5 does not increase the number of carets in the tree pair diagram. Thus we always have at least kgenerators in the expression ap· · · ahbk· · · bjat· · · as+1b1as· · · a1which do not increase the number of carets in the tree pair diagram. We then obtain the following upper bound for the number of carets N(w): n+ 1 ≤N(w)≤1+2k+ (r−k−k) = r+ 1 < n + 1 which is clearly a contradiction. Thus we are unable to express wusing fewer generators than n=|w|F.tu 5.3. Cyclic subgroups of T.We can use the interpretation of elements of Tas homeomorphisms of the circle to understand how Fis contained in Tand that the cyclic subgroups of Tare quasi-isometrically embedded. Theorem 5.10. Every element in Thas a power which is conjugate to an element in F. Proof. Ghys and Sergiescu [9] and Liousse [12] show that every element in T has rational rotation number as a homeomorphism of S1. A standard result in dynamics is that a homeomorphism of the circle has rational rotation number if and only if it has a periodic orbit (see, for example Katok and Hasselblatt [11].) Thus, every element in Thas a periodic orbit. That is, given f∈T, there exists a dyadic rational x∈[0,1] such that fn(x) = x for some n. Given a dyadic rational x, we consider the rotation of the circle tx(p) = p+x, where we view S1as the unit interval with the endpoints identified. 22 JOS´ E BURILLO, SEAN CLEARY, MELANIE STEIN, AND JENNIFER TABACK Then txis an element of T, and conjugation of w∈Tby tx, for the appropriate choice of xyields an element with zero as a fixed point. Thus the conjugated element must lie in F.tu We use Theorem 5.10 to show that cyclic subgroups of Tare quasiisometrically embedded. We again bound the distortion function, as in the proof of Corollary 5.2. Theorem 5.11. Let x∈Tbe a non-torsion element. Then the cyclic subgroup hxigenerated by xis quasi-isometrically embedded in T. Proof. If the element xlies in F, the result can be deduced from Corollary 5.2, since Burillo [3] shows that all cyclic subgroups in Fare quasiisometrically embedded, and Fis quasi-isometrically embedded in T. If x /∈F, it has a power wnwhich is conjugate to an element of Fby some element z∈T. Since xis not a torsion element, this power is not conjugate to the identity element of F. The cyclic subgroup generated by zwnz−1is quasi-isometrically embedded in T. Conjugation by zchanges the number of carets by at most a factor of 2N(z), and thus we see that hximust also be quasi-isometrically embedded in T.tu 6. Torsion elements Although the group Fis torsion free, both Tand Vcontain torsion elements. It is easy to construct torsion elements in Tor Vby choosing any binary tree Sand making any marked tree pair diagram with Sas both source and target tree. If the labelling of the target tree is the same as the labelling of the source tree, we get an unreduced representative of the identity; otherwise, we get a non-trivial torsion element. If this is an element of T, the tree pair diagram has pcq factorization in which q=p−1. In fact, any torsion element can be represented by such a tree pair diagram, though its reduced marked tree pair diagram may well not have the same source and target trees, corresponding to the fact that although it has a pcq word where q=p−1, the normal form may well not have this special balanced appearance. Proposition 6.1. If f∈F, T or Vis a torsion element, then it can be represented by a (marked) tree pair diagram with the same source and target trees. Before proving Proposition 6.1, we establish some notation which links the analytic and geometric interpretations of these groups. For f∈F,T, or V, if (T−, T+) is a marked tree pair diagram representing f, then it is sometimes convenient to denote the tree T+by f(T−). The element fcan COMBINATORIAL AND METRIC PROPERTIES OF THOMPSON’S GROUP T23 be though of as mapping the leaves of T−to the leaves of f(T−) = T+, where the marking defines this mapping of the leaves. Given two rooted binary trees Tand T0, we say that T0is an expansion of Tif T0can be obtained from Tby attaching the roots of additional trees to some subset of the leaves of T. We observe that if (T, f(T)) is a marked tree pair diagram for f, and T0is an expansion of T, then there is always a tree pair diagram (T0, f(T0)) for f, and f(T0) is an expansion of f(T). Given two rooted binary trees Sand T, by the minimal common expansion of Sand Twe mean the smallest rooted binary tee which is an expansion of both Sand T. Using this language, if (T, f(T)) and (S, g(S)) are marked tree pair diagrams for fand grespectively, the process described in Section 2.3 for creating a tree pair diagram for the product gf could be summarized as follows. If Eis the minimal common expansion of f(T) and S, then there are tree pair diagrams (f−1(E), E) for f, (E, g(E)) for g, and (f−1(E), g(E)) for gf. Proof. Suppose that fis a torsion element, and that fcannot be represented by a tree pair diagram with the same source and target trees. Since there exists a positive integer msuch that fmis the identity, it follows that all tree pair diagrams for fmhave the same source and target trees. We reach a contradiction by constructing (marked) tree pair diagrams (An, Bn) for fnsuch that An6=Bnfor every n≥1. These tree pair diagrams are constructed inductively, viewing fnas a product (fn−1)(f). For n= 1, let (A1, B1) be the reduced marked tree pair diagram for f. If k≥2, suppose the marked tree pair diagram (Ak−1, Bk−1) for fk−1has been constructed. Let Ek−1be the minimal common expansion of the trees A1and Bk−1. Then fkhas tree pair diagram (f−(k−1)(Ek−1), f(Ek−1)), and we let Bk= f(Ek−1) and Ak=f−(k−1)(Ek−1). By construction, Ak+1 is an expansion of Akfor all k≥1. We claim also that Bk+1 is an expansion of Bkfor all k≥1. For k= 1, E1is by definition an expansion of A1, which implies that B2=f(E1) is an expansion of B1=f(A1). Suppose inductively that Bkis an expansion of Bk−1. Now Ekis an expansion of Bkand A1, so Ekis an expansion of Bk−1and A1. But Ek−1is the minimal common expansion of Bk−1and A1, so Ekis an expansion of Ek−1, which implies that Bk+1 =f(Ek) is an expansion of Bk=f(Ek−1). Now if An=Bn, then since Anis an expansion of A1,Bnis an expansion of A1. But since En−1is the minimal common expansion of Bn−1and A1, this implies that Bn=f(En−1) is an expansion of En−1. But they have the same number of carets, so in fact f(En) = En−1, which cannot be. Hence An6=Bnfor all n, as claimed. tu 24 JOS´ E BURILLO, SEAN CLEARY, MELANIE STEIN, AND JENNIFER TABACK Corollary 6.2. An element of Tis torsion if and only if it is a conjugate of some cj i. Proof. If an element is torsion, then it admits a diagram with two equal trees. The pcq factorization associated with this diagram has the form pcj ip−1, where pis a positive element of F.tu A particularly natural torsion subgroup is the subgroup Rof pure rotations, where by a pure rotation by d=a 2n(where ais not divisible by 2) we mean an element gd∈Twhich corresponds to the homeomorphism of S1 given by gd(t) = ½t+a 2nif 0 ≤t < 1−a 2n t+a 2n−1 if 1 −a 2n≤t < 1 Such pure rotations were used in Section 5.3 to conjugate the fixed point of a homeomorphism to 0. This subgroup is isomorphic to the group of dyadic rational numbers modulo 1, which has a 2-adic metric as follows: if x=p 2l,y=q 2m, and z=|x−y|=r 2k, where p, q and rare odd, then d(x, y) = 2k. With respect to this metric, the subgroup of rotations is quasi-isometrically embedded in T. Proposition 6.3. The subgroup Rof the pure rotations, with the 2-adic metric, is quasi-isometrically embedded in T. Proof. We note that if g∈Tis the rotation by a 2nwhere ais not divisible by 2, then there are 2n−1 carets in the reduced tree pair diagram representing g, so N(g) = 2n−1. Since we have shown that the word length of gin Tis bi-Lipschitz equivalent to N(g), the proposition follows. tu References [1] James Belk and Kenneth S. Brown. Forest diagrams for elements of Thompson’s group F. Preprint. [2] Kenneth S. Brown and Ross Geoghegan. An infinite-dimensional torsion-free F P∞ group. Inventiones mathematicae, 77:367–381, 1984. [3] Jos´e Burillo. Quasi-isometrically embedded subgroups of Thompson’s group F.J. Algebra, 212(1):65–78, 1999. [4] Jos´e Burillo, Sean Cleary, and Melanie Stein. Metrics and embeddings of generalizations of Thompson’s group F.Trans. Amer. Math. Soc., 353(4):1677–1689 (electronic), 2001. [5] J. W. Cannon, W. J. Floyd, and W. R. Parry. Introductory notes on Richard Thompson’s groups. Enseign. Math. (2), 42(3-4):215–256, 1996. [6] Sean Cleary and Jennifer Taback. Combinatorial properties of Thompson’s group F.Trans. Amer. Math. Soc., 356(7):2825–2849 (electronic), 2004. [7] S. Blake Fordham. Minimal Length Elements of Thompson’s group F. PhD thesis, Brigham Young Univ, 1995. COMBINATORIAL AND METRIC PROPERTIES OF THOMPSON’S GROUP T25 [8] S. Blake Fordham. Minimal length elements of Thompson’s group F.Geom. Dedicata, 99:179–220, 2003. [9] ´ Etienne Ghys and Vlad Sergiescu. Sur un groupe remarquable de diff´eomorphismes du cercle. Comment. Math. Helv., 62(2):185–239, 1987. [10] Victor Guba. On the properties of the Cayley graph of Richard Thompson’s group F. Preprint. [11] Anatole Katok and Boris Hasselblatt. Introduction to the modern theory of dynamical systems, volume 54 of Encyclopedia of Mathematics and its Applications. Cambridge University Press, Cambridge, 1995. With a supplementary chapter by Katok and Leonardo Mendoza. [12] Isabelle Liousse. Nombre de rotation dan les groupes de thompson g´eneralis`es et applications. Preprint. Dep. de Matem` atica Aplicada IV, Univ. Polit` ecnica de Catalunya, Escola Polit` ecnica Superior de Castelldefels, 08860 Castelldefels, Barcelona, Spain E-mail address:[email protected] Department of Mathematics, The City College of New York & The CUNY Graduate Center, New York, NY 10031 E-mail address:[email protected] Department of Mathematics, Trinity College, Hartford, CT 06106 E-mail address:[email protected] Department of Mathematics, Bowdoin College, Brunswick, ME 04011 E-mail address:[email protected]