Bounding right-arm rotation distances

BOUNDING RIGHT-ARM ROTATION DISTANCES SEAN CLEARY AND JENNIFER TABACK Abstract. Rotation distance quantifies the difference in shape between two rooted binary trees of the same size by counting the minimum number of elementary changes needed to transform one tree to the other. We describe several types of rotation distance, and provide upper bounds on distances between trees with a fixed number of nodes with respect to each type. These bounds are obtained by relating each restricted rotation distance to the word length of elements of Thompson’s group Fwith respect to different generating sets, including both finite and infinite generating sets. 1. Introduction Rotation distance quantifies the difference in shape between two rooted binary trees of the same size by counting the minimum number of elementary changes needed to transform one tree to the other. Search algorithms are most efficient when searching balanced trees, which have few levels relative to the number of nodes in the tree. Thus one is often interested in calculating, or at least bounding, the number of these changes necessary to alter a given tree into one with a more desirable shape, such a balanced tree. If we allow these elementary changes, called rotations, to take place at any node, we obtain ordinary rotation distance. This was analyzed by Sleator, Tarjan and Thurston [14], who proved that there is an upper bound of 2n−6 rotations needed to transform one rooted binary tree with nnodes into any other. Furthermore, they showed that the 2n−6 bound is achieved for large values of nand thus is the best possible upper bound. No efficient algorithm is known to compute rotation distance exactly, though there are polynomial-time algorithms of Pallo [11] and Rogers [13] which estimate rotation distance efficiently. The first author acknowledges support from PSC-CUNY grant #66490, NSF grant DMS-0305545 and the hospitality of the Centre de Recerca Matem`atica. The second author acknowledges support from NSF grants DMS-0305545 and DMS- 0437481 and the hospitality of the Centre de Recerca Matem`atica. 1 2 SEAN CLEARY AND JENNIFER TABACK C T1 A B C N T2 A B N Figure 1. Right rotation at node Ntransforms T1to T2; similarly, left rotation at node Ntransforms T2to T1. The labels A,Band Crepresent (possibly empty) subtrees of T1and T2. Here we expand on the study of restricted rotation distance begun in [4] and [5]. Restricted rotation distance allows rotations only at the root node and the right child of the root node. Restricted rotation distance is related to the word length of elements of Thompson’s group Fwith respect to its standard finite generating set. This is illustrated in [4, 5] and involves the interpretation of elements of Fas pairs of finite binary rooted trees and Fordham’s method [9] for computing the word length of an element of Fwith respect to that standard finite generating set directly from such trees. These methods not only give an effective algorithm to compute restricted rotation distance, but they also give an effective algorithm to find the appropriate rotations which realize this distance. Right and left rotations at a node Nof a rooted binary tree Tare defined to be the permutations of the subtrees of Tdescribed in Figure 1. Right rotation at a node Ntransforms the original tree T1, given on the left side of Figure 1, to the tree T2on the right side of Figure 1. Left rotation at a node is the inverse operation. In all that follows, T1and T2denote trees with the same number of leaves. In this paper, we discuss generalizations and variations of restricted rotation distance, in which rotations are again only allowed at specified nodes of the tree. We relate these distances to distinct word metrics on Thompson’s group F. We use this interpretation to exhibit asymptotically sharp linear bounds on the number of allowable elementary rotations needed to transform one tree with nnodes into another. These alternate definitions all allow rotations at the root node and at nodes connected to the root node by a path consisting entirely of right edges, that is, nodes that lie on the right side or right arm of the tree. The root node is considered to lie on the right side of the tree. While the original restricted rotation distance is well defined between any two trees with the same number of nodes, this is no BOUNDING RIGHT-ARM ROTATION DISTANCES 3 longer necessarily the case when we allow rotations at other collections of nodes along the right side of the tree. Some transformations between trees cannot be accomplished with a specified set of rotations unless additional nodes are added to the trees– which is not permitted for rotation distance. Below, we describe when such a transformation is possible, and describe all pairs of trees for which rotation distance is defined. The sharp upper bound on the restricted rotation distance between two trees, each with nnodes, obtained in [5] is 4n−8. Below, we consider allowing additional rotations along the right side of the tree and note that allowing rotations at any finite collection of nodes on the right side of the tree does not change the multiplicative constant of 4 in the upper bound. It is only when we allow an infinite set of rotations along the right arm of the tree that we obtain the multiplicative constant of 2 in the upper bound, analogous to ordinary rotation distance. These rotation distances and bounds are summarized in Table 1, where nis the number of nodes in each tree. Type of distance: Rotations allowed at: Symbol: Upper Bound: Rotation distance all nodes dR2n−6 Restricted rotation root node and right dRR 4n−8 distance child of the root node Restricted right arm root node and a finite 4n−C rotation distance collection Sof nodes on dS RRA some C the right side of the tree Right arm all nodes on the right dRA 2n−2 rotation distance side of the tree Restricted spinal root node and a finite 4n−C rotation distance collection Sof nodes on dS RS some C both sides of the tree Table 1. Summary of rotation distances between trees with nnodes. Culik and Wood [8] allowed rotations only at nodes along the right side of the tree, and showed that under these conditions a sharp upper bound on this right-arm rotation distance between two trees with nnodes is 2n−2. Since the ordinary rotation distance between two such trees can be as much as 2n−6, it is remarkable that restricting rotations to the right side of the tree adds only four rotations to the upper bound. Below, we describe this in terms of the metric on Thompson’s group F, and explain how allowing 4 SEAN CLEARY AND JENNIFER TABACK rotations at all nodes along the right arm of a tree corresponds to the word metric with respect to the standard infinite generating set for F. Pallo studied right-arm rotation distance in [12], allowing rotations at all nodes along the right side of the tree. He described a process for computing right-arm rotation distance which we show below is equivalent to finding the word length in Thompson’s group Fwith respect to the standard infinite generating set. Each node in the trees we consider consists of a vertex and two downward directed edges. We will only consider finite, rooted binary trees with n nodes. These trees are called extended binary trees in Knuth [10] or 0-2 trees. A vertex of valence one in a tree is called an exposed leaf or simply a leaf. The exposed leaves in a tree are numbered from left to right, beginning with zero. Our trees will have nnodes, which yield n+ 1 exposed leaves, numbered from 0 to n. A node with both of its leaves exposed is called an exposed node, and its leaves are termed siblings and those leaves are said to form a sibling pair. A node Nwhich is attached to the right (respectively left) edge of a node Mis called the right (respectively left) child of M. A node which has one edge on the left side of the tree is called a left node. A node which has one edge on the right side of the tree and is not the root node is called a right node. Nodes which are neither right nor left are called interior nodes. The union of left and right nodes in a tree is called the spine of the tree. A tree consisting of only the root node and n−1 right nodes is called the all-right tree with nnodes. An ancestor of a node is any node which lies along the shortest path between it and the root node. The connection between Thompson’s group Fand restricted rotation distance is described below. Thompson’s group Fis combinatorially studied in two ways: via a finite presentation and an infinite presentation. Computing restricted rotation distance between two trees is related to computing the word length of the element of Fdescribed by those trees with respect to the standard finite generating set for the group F. Analogously, right-arm rotation distance corresponds to computing the word length of the element with respect to the word metric induced by the standard infinite generating set for F. Restricted right-arm rotation distances and restricted spinal rotation distances, defined below, relate to the word metric on Fwith respect to other finite generating sets for F. 2. Thompson’s Group F The connection between Thompson’s group Fand rotations at nodes of trees is described in [4] and [5], using the work of Fordham [9]. Here, we briefly describe this connection, and refer the reader to Cannon, Floyd and BOUNDING RIGHT-ARM ROTATION DISTANCES 5 Parry [3] for a survey of the properties of Thompson’s group F, and the further connection between elements of Fand pairs of binary rooted trees. 2.1. The infinite presentation of Thompson’s group F.Thompson’s group Fhas a presentation with an infinite number of generators and relations: P=x0, x1, . . . |x−1 ixnxi=xn+1,∀i < n®. In this presentation, there are normal forms for elements given by xr1 i1xr2 i2. . . xrk ikx−sl jl. . . x−s2 j2x−s1 j1 with ri, si>0, where the indices satisfy 0 ≤i1< i2. . . < ikand 0 ≤j1< j2. . . < jl. This normal form is unique for a given element if we further require the reduction condition that when both xiand x−1 ioccur, so does xi+1 or x−1 i+1, as discussed by Brown and Geoghegan [2]. The relations provide a quick and efficient method for rewriting words into normal form, and form a complete rewriting system, as described by Brown [1]. There is a natural shift homomorphism φ:F→Fwhere φ(xi) = xi+1 which respects the relators, and the reduction from normal form to unique normal form is accomplished with a sequence of operations replacing words of the form uxiφ(v)x−1 iwwith uvw, where φ(v) is a subword which contains only generators of index i+ 2 and higher. We note that Fcan be generated by just x0and x1in the above presentation; the relators show that x0conjugates x1to x2. Similarly, all higher-index generators are conjugates of x1by higher powers of x0, as xn=x−(n−1) 0x1xn−1 0. This leads to a finite presentation for Fwith generating set {x0, x1}. In fact, x0and any higher index generator are sufficient to generate the group. Two generators xi, xjwith i6=jwill generate an subgroup of Fwhich is isomorphic to the entire group but which is the entire group only when one of ior jis 0. We begin by proving that in the word metric arising from this infinite generating set, the normal form expressions are geodesic representatives for elements of F. Lemma 2.1. Let w=xr1 i1xr2 i2. . . xrk ikx−sl jl. . . x−s2 j2x−s1 j1be in unique normal form, as described above. Then xr1 i1xr2 i2. . . xrk ikx−sl jl. . . x−s2 j2x−s1 j1is a geodesic in the word metric arising from the standard infinite generating set {xi}of F. Proof. Suppose that xr1 i1xr2 i2. . . xrk ikx−sl jl. . . x−s2 j2x−s1 j1was not a geodesic representative in this word metric. Then there is a shorter expression, not necessarily in normal form, which we call α, representing win this infinite generating set. It is clear from the relations of Pthat the conversion of αinto unique normal form can only preserve or decrease the length of α. 6 SEAN CLEARY AND JENNIFER TABACK Thus, after converting αinto normal form we have obtained a second expression of win unique normal form shorter than the initial unique normal form for w, and we have a contradiction. ¤ 2.2. Tree pair diagrams for elements of Thompson’s group F.The group Fhas a geometric description in terms of equivalence classes of tree pair diagrams. A tree pair diagram is a pair of finite rooted binary trees with the same number of leaves. We write w= (T1, T2) to denote the two trees comprising a pair representing w. The equivalence between the geometric and algebraic interpretations of Fis described in [3], and examples of this equivalence and its connection with rotations are given in [7]. Given two trees with the same number of nodes T1and T2, the word in normal form associated to w= (T1, T2) is found as follows. The leaves of each tree are numbered from left to right, beginning with zero. The leaf exponent of a leaf numbered kis the integral length of the longest path starting at leaf kconsisting entirely of left edges which does not touch the right side of the tree. The tree pair diagram (T1, T2) has an associated normal form xf0 0xf1 1. . . xfn nx−en n. . . x−e1 1x−e0 0where eiis the leaf exponent of leaf iin tree T1and fiis the leaf exponent of leaf iin T2. We refer to T1 as the negative tree of the tree pair diagram and T2as the positive tree of the tree pair diagram. An example of a tree with leaf exponents computed is given in Figure 2. 11 0 1 2 3 4 5 6 7 8 9 10 Figure 2. A tree whose leaves are numbered from left to right. The leaf exponents of the leaves, according to increasing leaf number, are 2,0,1,1,0,0,0,1,0,1,0, and 0. An element of Fis represented uniquely by a tree pair diagram satisfying the following reduction condition. A tree pair diagram (T1, T2) is unreduced BOUNDING RIGHT-ARM ROTATION DISTANCES 7 if both T1and T2contain a node with two exposed leaves numbered iand i+ 1. A tree pair diagram which is not unreduced is reduced. Geometrically, any tree pair diagram has a unique reduced form that is obtained by successively deleting exposed nodes with identical leaf numbers from both trees, renumbering the leaves, and repeating this process until no further such reductions are possible. Elements of Fare equivalence classes of tree pair diagrams, where the equivalence relation is that two tree pairs are equivalent if they have a common reduced form. This tree pair reduction condition corresponds exactly to the combinatorial reduction condition given above to ensure uniqueness for words in normal form in the infinite presentation of F. That is, if leaves iand i+ 1 form a sibling pair in both T1and T2, then in both cases, the leaf exponent of iwill be non-zero and that for i+ 1 will be zero, as it is a right leaf. So the corresponding normal form will have both xiand x−1 ibut no x±1 i+1, meaning that the normal form is not unique. To perform the group operation on the level of tree pair diagrams, it may be necessary to use unreduced representatives of elements. Namely, to multiply (T1, T2) and (S1, S2), we create unreduced representatives (T0 1, T 0 2) and (S0 1, S0 2) in which T0 2=S0 1, and write the product as the (possibly unreduced) element (T0 1, S0 2). See [3] for examples of group multiplication using tree pair diagrams for elements of F. n n n+1 n+2 n n+1 n+2 x0x1x Figure 3. The tree pair diagrams corresponding to the generators x0,x1and xnof F. The reduced tree pair diagrams associated to the generators x0, x1and xnare pictured in Figure 3. As explained in Lemmas 2.6 and 2.7 of [6], the generators x0and x1can be viewed in terms of rotations of rooted binary trees as well. The generator x0can be interpreted as a left rotation at the root of the left tree in the pair, yielding the right tree in the pair. Similarly, the generator x1performs a left rotation at the right child of the root node, transforming the left tree in the pair to the right one. The inverses x−1 0 and x−1 1perform right rotations at the root node and right child of the root node, respectively. 8 SEAN CLEARY AND JENNIFER TABACK One complication that may arise when using the geometry of the tree pair diagrams to understand rotation distance involves the possibility of adding nodes to a tree in order to perform group multiplication. Since elements of Thompson’s group are equivalence classes of tree pair diagrams, we can always multiply any group element wby any group generator g. It is possible that we may have to add nodes to the reduced tree pair diagram for win order to perform this multiplication. From the standpoint of group theory, the reduced and unreduced tree pair diagrams are interchangeable. When considering rotation distance, we are not allowed to change the number of carets in the starting tree. Thus certain rotations, corresponding to multiplication by specific generators, may not be permitted when calculating rotation distance. wxw 1 w Figure 4. In order to multiply the tree pair diagram representing wby the generator x1, we form the unreduced representative wof win which the dashed node is added to both trees. Only then are we able to form the product wx1. For example, we cannot perform a right rotation at the right child of the root to either of the trees in the tree pair diagram for x0as shown in Figure 3 because in both of these trees, the left subtree of the right child of the root node does not exist. As an element of Thompson’s group, we can enlarge any pair of trees to be able to multiply by any generator. A typical such application is shown in Figure 4 where a node is added to a tree to be able to perform the desired rotation. The tree pair diagram wdoes not have a left child of the right child of the root, so performing a right rotation at the right child of the root is not possible. However, the word w0which represents the same element of Fdoes have a left child of the right child of the root and it is possible to perform the right rotation at the right child of the root there. We obtain w0by adding an additional node (indicated by dashing) to leaf number 3 in both trees of the tree pair diagram. BOUNDING RIGHT-ARM ROTATION DISTANCES 9 To describe when it is necessary to add a node to a tree to perform a particular rotation, we make the following definitions. We say a right rotation at the root can be applied to a tree Tif the left subtree of the root of Tis non-empty. Similarly, we say a left rotation at the root can be applied to a tree Tif the right subtree of the root of Tis non-empty and we also adopt this terminology when performing rotations at other nodes along the right side of the tree. Understanding when rotations can be performed on trees helps us develop the connection between rotations of trees and right multiplication by generators of F. If, for example, we have a tree pair diagram (T1, T1) representing the identity and we can perform a left rotation at the root to T1 to obtain x0T1, then the new tree pair diagram (T1, x0T1) is the tree pair diagram representing the word x0in F, and similarly the new tree pair diagram (x0T1, T1) is tree pair diagram representing the word x−1 0in F. We note that in F, multiplication by a generator may result in an unreduced tree pair diagram. So during the course of a long sequence of multiplications by generators of F, the number of nodes in the reduced tree pair diagram representing the partial products may fluctuate– rising when needing to add one or more nodes to apply a generator, and falling when multiplying by a generator results in an unreduced tree pair diagram. To understand rotation distance, however, as we apply a sequence of rotations to a single tree, we do not allow the number of nodes in the tree to change. The link between restricted rotation distance and Thompson’s group F is the word metric on Fwith respect to the generators {x0, x1}. Given two rooted binary trees T1and T2with the same number of nodes, we consider a minimal length word in x±1 0and x±1 1representing the element w= (T1, T2)∈F. As described in [4], this word gives a minimal sequence of rotations at the root and right child of the root which transform the tree T1into the tree T2. It follows from Fordham [9] that these minimal words which transform one tree into the other maintain a constant number of carets at each stage in the sequence of rotations. The issue of certain rotations altering the number of nodes in the tree does not arise in the case of restricted rotation distance. More precisely, suppose that w∈Fis given by the tree pair diagram (T1, T2), and a minimal length representative for wis g1g2. . . gn, where each gi∈ {x±1 0, x±1 1}. Then the tree pair diagram (T1, gn. . . g2g1T1) will represent w, and we can think of the sequence of generators gn. . . g2g1 as a sequence of rotations which transforms T1to T2. At each stage of this process, we will be able to perform the rotation corresponding to the generator gi+1 to the tree gi. . . g2g1T1without adding additional nodes. There may be reductions possible to tree pair diagrams, or equivalently to 16 SEAN CLEARY AND JENNIFER TABACK negative exponents and T2to those with positive exponents. We thus write the normal form as the product P N, where Ncontains the generators with negative exponents, and Pthose with positive exponents. We see that Nis a word which rotates the tree T1into the all-right tree without requiring the addition of any nodes, and the subword Pis a string of generators which rotates the all-right tree into the tree T2. Thus we see that a lower bound for right arm rotation distance is |(T1, T2)|I, and an upper bound is given by combining the length of the strings Pand N. It follows from Lemma 2.1 that |(T1, T2)|I=|(T1,∗)|I+ |(T2,∗)|Iwhere ∗is the all-right tree with nnodes, proving the proposition. ¤ 3.2. Bounds on restricted rotation distances. Now that we have described the relationship between the different rotation distances and word lengths in F, we obtain numerical bounds on these rotation distances as summarized in Table 1. We note that word length of an element of Fcomputed with respect to a generating set of the form Sgiven above has the potential to be much shorter than the word length of the same element computed with respect to the generating set {x0, x1}. Thus we might expect significantly smaller asymptotic upper bounds on restricted right-arm rotation distance than on restricted rotation distance. In fact, this is not the case, and the difference between the upper bounds on the two rotation distances is at most a constant. The goal of this section is to prove that the multiplicative constant of 4 in the upper bound on restricted right-arm rotation distance cannot be improved upon. That is, both the restricted rotation distance and the restricted right-arm rotation distance between two trees with nnodes each, when defined, are bounded above by 4nminus a constant. This constant depends upon the particular finite set of rotations permitted. These bounds are shown to be sharp for restricted rotation distance in [5]. We show below that they are asymptotically sharp for restricted right-arm rotation distance. While allowing additional rotations may shorten the restricted right-arm rotation distance between certain pairs of trees, asymptotically the worst-case scenario differs from restricted rotation distance by an additive constant. One way to improve the multiplicative constant of 4 is to allow rotation at an infinite collection of nodes along the right side of the tree, in which case the multiplicative constant may decrease to 2. The necessity of the constant 4 is shown in two steps. We first show that the restricted right-arm rotation distance, when defined, is always bounded above by 4n, where nis the number of nodes in either tree. We then show that there are words which realize this bound, up to an additive constant. BOUNDING RIGHT-ARM ROTATION DISTANCES 17 Proposition 3.8. Let S={x0, xm1, xm2, . . . xml}be a generating set for Fwith 0< m1< m2<· · · < ml, and let dS RRA the corresponding restricted right-arm rotation distance. Let T1and T2be binary trees, each with n nodes, for which dS RRA is defined. Then dS RRA(T1, T2)≤4n. Proof. The case where m1= 1 is already addressed by the analysis of ordinary rotation distance, described in [5]. We consider the element w= (T1, T2)∈F, where T1and T2are trees for which the relevant restricted right-arm rotation distance dS RRA is defined, and assume that m1>1. Case 1: The tree pair diagram (T1, T2)is reduced. In this case, we know that the normal form of wcontains no generators x±1 tfor 1 ≤t≤m1−1. In addition, this normal form can contain x0or x−1 0but not both. If both x0and x−1 0were present in the normal form with no x±1 1generator, then the normal form could be reduced. We can assume by symmetry that the normal form for wcontains x−k 0but no factors of x0. Using the correspondence between the normal form and the leaf exponents in the trees T1and T2, we see that the leaves of both trees numbered from 1 through m1−1 are either exposed right leaves of left nodes or exposed left leaves of right nodes. In T1, denote the (possibly empty) subtrees of the left and right nodes by A1, A2,··· , An, where the smallest leaf number in A1is m1. Similarly, in T2denote these subtrees by B1, B2,· · · , Bm, where the smallest leaf number in B1is m1. Let w0=wxk 0, so that the tree pair diagram (S1, T2) of w0has tree S1 containing a single left node, namely the root node, and m1−1 right nodes with exposed left leaves, followed by right nodes having A1,· · · , Anas their left subtrees. The pair (S1, T2) has the form given in Figure 6. We consider the element v∈Fwhich has tree pair diagram (R1, R2), where R1has a single left node, namely the root node, and the left subtree of the right node at height iis Ai. The tree R2is defined analogously, using the subtrees Bifrom the original tree T2. Since restricted rotation distance is well defined for all trees with the same number of nodes, we apply Theorem 3.2 to obtain the bound dRR(R1, R2)≤4(n−(m1−1)) −8. This restricted rotation distance is realized by a string αof the generators {x±1 0, x±1 1}. We define a string of generators α0by replacing each instance of x±1 1in αwith x±1 m1. Then this string of generators exactly produces the tree pair diagram (S1, T2). Since the number of nodes in each tree remains constant as each generator from αis applied to create (R1, R2), the same is true as we multiply the generators in α0to create w0= (S1, T2). 18 SEAN CLEARY AND JENNIFER TABACK 1 R1R2 A A 1 A2 nBn B2 B1 S1T2 A A 1 A2 nBn B2 B Figure 6. The tree pair diagrams for the words used to show that the restricted right-arm rotation distance is bounded above by 4n. Thus the restricted right-arm rotation distance with respect to T= {x0, xm1}is bounded as follows: dT RRA(S1, T2)≤4(n−(m1−1)) −8. Now we note that w=w0xk 0, and since there were initially k+1 left nodes in the tree T1, the number of nodes in each tree remains constant during these successive multiplications by x−1 0. Thus the string α0x−k 0realizes the restricted rotation distance between the trees T1and T2. If k≤m1−1, then the left nodes which are changed to right nodes under multiplication by x−k 0do not appear in R1and R2, and so are not represented in the upper bound given above. Thus, when the rotation distance is increased by k, we trivially extend the bound to dT RRA(T1, T2)≤4n−8. Since adding additional generators to the generating set, or equivalently allowing rotations at additional nodes, can only decrease the rotation distance, the upper bound still holds when we consider the entire generating set S. If k≥m1, then the left nodes which are changed to right nodes by this multiplication by x−1 0are of two types: those with exposed left leaves numbered from 1 to m1−1, and those with left subtrees of the form Ai. BOUNDING RIGHT-ARM ROTATION DISTANCES 19 The first type of right node is not counted in the upper bound given above, and thus we increase the number of nodes in the bound by m1−1 to (more than) account for the additional generators. The right nodes of the second type, with left subtrees of the form Ai, are already counted in the bound given above. However, we recall that the word α0which realizes the restricted right-arm rotation distance between S1and T2, came from the word αin {x±1 0, x±1 1}. We know from Fordham’s method of calculating word length with respect to the generating set {x0, x1}directly from the tree pair diagram that each pair of nodes contributes a certain number of generators to this word length. Fordham calls this the weight of the pair of nodes. We see from Fordham’s table of weights [9] that any pair of nodes in which one node is a right node has a weight of at most three. So using an extra generator of the form x−1 0to transform this right node into a left node means that these nodes contribute at most four generators each to the length of the word realizing the restricted right-arm rotation distance between T1and T2. We have thus shown the existence of the upper bound dT RRA(T1, T2)≤4n−8. Since rotation distance can only decrease when additional rotations are permitted, this extends immediately to show dS RRA(T1, T2)≤4n−8. Case 2: The tree pair diagram (T1, T2)is not reduced. In this case, since dS RRA(T1, T2) is defined, we know from Lemma 3.6 that there is a partially reduced form of wobtained by applying the usual reduction rules but without reducing instances of x0and x−1 0with no x±1 1 from the normal form. The number of nodes in the tree pair diagram may reduce to n0< n. The proof of this case is now identical to that of Case 1. This produces an upper bound of 4n0−8<4n−8 on the restricted right-arm rotation distance between the two trees. ¤ We now show that the multiplicative constant of 4 is necessary for the above inequality. Theorem 3.9. Let S={x0, xi1,· · · , xim}. Then there exist trees T1and T2, each with nnodes, so that dS RRA(T1, T2)is defined, and with 4n−2im+ 4 ≤dS RRA(T1, T2). The generating set Sused in Theorem 3.9 corresponds to a series of rotations along the right side of the tree from levels 0 to imbut does not necessarily include all rotations at levels within this range. We now enlarge our generating set to correspond to all rotations at levels 0 to mi, and work 20 SEAN CLEARY AND JENNIFER TABACK with this set S0in Theorem 3.10. It will be enough to use this larger set of generators and show that dS0 RRA(T1, T2)≥4n−2im+ 4. Thus we prove the following theorem. Theorem 3.10. Let S0={x0, x1, x2,· · · , xm}. Then there exist trees T1 and T2, each with nnodes, so that dS0 RRA(T1, T2)is defined, and with 4n−2m+ 4 ≤dS0 RRA(T1, T2). The elements we will use to prove this theorem have normal form xm+2xm+3 · · · xnx−1 n−1···x−1 m+1, and tree pair diagram which we denote (T1, T2). These elements are pictured in Figure 7. 1 m+1 m+2 n−1 n n+1 n+2 m+1 m+2 m+3 n n+1 n+2 0 1 m 0 Figure 7. The tree pair diagram (T1, T2) for words of the form xm+2xm+3...xnx−1 n−1...x−1 m+1. Note that Fordham’s method for computing exact word length is only valid for the generating set {x0, x1}, so we bound the lengths of these elements indirectly in a series of lemmas by considering the number of rotations needed to create and destroy particular sibling pairs in the tree pair diagram. We write [i, i + 1] if leaves iand i+ 1 form a sibling pair. Performing a rotation corresponding to the generator xnon a tree Tis equivalent to taking the product of xnwith the tree pair diagram (T, ∗), where ∗is the tree consisting only of the root node and a series of right nodes. By analyzing the effect of a rotation at a right node on a tree T, we see that there are BOUNDING RIGHT-ARM ROTATION DISTANCES 21 only three configurations of Twhich allow a sibling pair to be created or destroyed. These are presented in Figure 8, where capital letters refer to nonempty subtrees of Tand lower case letters denote leaf numbers. Right rotation at the appropriate node Nalong the right side of the tree has the following effect on the sibling pairs. (i) The pair [a,b] is destroyed and the pair [b,c] is created. (ii) The pair [a,b] is destroyed. (iii) The pair [b,c] is created. We can similarly consider left rotation at the node N, in which case we refer to Figure 9. Left rotation at node Nalong the right side of the tree has the following effect on the sibling pairs. (i) The pair [a,b] is created and the pair [b,c] is destroyed. (ii) The pair [a,b] is created. (iii) The pair [b,c] is destroyed. (iii) a b c a b b c C A (i) (ii) Figure 8. Instances where right rotation at node Nalong the right side of the tree creates or destroys sibling pairs in the tree T. Capital letters represent nonempty subtrees of T, and lower case letters denote leaf numbers. (iii) a b c a b b c C A (i) (ii) Figure 9. Instances where left rotation at node Nalong the right side of the tree creates or destroys sibling pairs in the tree T. Capital letters represent nonempty subtrees of T, and lower case letters denote leaf numbers. 22 SEAN CLEARY AND JENNIFER TABACK From these observations, we can see immediately at which nodes it is possible to create and destroy sibling pairs with a set of rotations. Lemma 3.11. Suppose a tree T0is obtained from a tree Tby applying a right rotation at a node Nat level non the right side of T. If leaves mand m+ 1 are siblings in Tand are not siblings in T0, then leaves mand m+ 1 are the leaves of an exposed node whose parent is node N. Similarly, if we have the sibling pair [m, m + 1] in T0but not in T, then [m, m + 1] must be the rightmost node in T0and mmust be a leaf in Twhose parent is the node at level nin T. Similarly, for left rotations we have the opposite conditions. We note that when Nis the root node, the only sibling pairs that can be affected by rotation at Nconsist of the first and last two leaves in the tree. When we consider the trees T1and T2in Figure 7 from the word xm+2xm+3...xnx−1 n−1...x−1 m+1, we see that in T1, leaves n−1 and nare siblings and in T2,nand n+ 1 are siblings. Now we consider the number of applications of generators needed to change the sibling pairings from [n−1, n] to [n, n + 1] via a minimal length sequence of transformations, expressed as a word w=g1g2. . . gl. In order to change the pairings, we will need to destroy the sibling pair [n−1, n] and then create the sibling pair [n, n + 1]. The exposed nodes with siblings [n−1, n] and [n, n + 1] are deeply buried in the sense that many rotations are required to affect those nodes and thus those leaf pairings. We measure this depth more precisely with the following definition. Definition 3.12. Let cbe an exposed node, and define G(c)to be the node connected to cby a maximal length path of downward directed right edges. We also define the ordered pair D(c) = (p, r), where pis the length of the maximal path of right edges from G(c)to cand ris the level in the tree of the ancestor closest to G(c)which is a right caret. For example, in the tree T1for wand cthe node with exposed leaves [n−1, n], we have that G(c) is the node with left leaf m+ 1 and the closest right ancestor of G(c) is its parent. Thus D(c) = (n−m−2, m + 1). For the node c0in the tree T2with leaves [n, n + 1], we have that G(c0) is the node with left leaf m+ 2 and D(c0) = (n−m−2, m + 2). Lemma 3.13. Let w= (T1, T2)∈Fhave normal form xm+2xm+3 ···xnx−1 n−1· · · x−1 m+1 where n>m+ 1. The tree T0resulting from the application of at most 2n−2m−3rotations at locations at levels 0to malong the right side of the tree to Twill contain the sibling pair [n-1,n]. BOUNDING RIGHT-ARM ROTATION DISTANCES 23 Proof. We note that by Lemma 3.11, sibling pairs can be destroyed only when they are connected by a single left edge to a node on the right side of the tree at level mor less, or are the rightmost node in the tree. The exposed node cwith leaves n−1 and ncannot be moved to be the rightmost node of the tree, as all rotations preserve the natural infix order on the nodes. Thus, until the node cis connected by a single left edge to the right side of the tree at level mor less, leaves n−1 and nwill remain sibling pairs. We use the ordered pair D(c) to monitor the position of node cwhile rotations are performed on the tree. The leaves n−1 and nwill remain sibling pairs until D(c) = (0, l) for some l≤m. We consider the sequence of trees S0=T1,S1, S2,··· , Skresulting from performing a series of krotations corresponding to a sequence of kgenerators g1g2· · · gk. Each Siis the result of applying gito Si−1. We trace the images of the node cthrough this sequence and denote its image in Siby ci. While the exposed leaves of each cihave the same leaf numbers in Si, the entries in D(ci) may change as a result of each rotation. First we consider the possible changes in D(ci)=(ri, si) resulting from performing a rotation to the tree corresponding to a single generator. Recall that siis the level in the tree of the closest ancestor of G(ci) on the right side of the tree. There are several cases depending upon the relative location of the node where the rotation takes place and the closest ancestor of G(c) on the right side of the tree. Here we describe the changes in (ri, si) caused by rotation at a right node at level k, with 0 ≤k≤m. •Case k < si:In this case, the rotation takes place at a level above both ciand the closest ancestor of G(ci) on the right side of the tree and we obtain D(ci+1) = (ri, si−1) = (ri+1, si+1) for a left rotation and D(ci+1) = (ri, si+ 1) = (ri+1, si+1) for a right rotation. Note that right rotation may not be possible at level kif the left subtree of the relevant node is empty. •Case k=si:In this case, a right rotation moves G(ci) or one of its ancestors which is not on the right side of the tree to the right side of the tree. If G(ci) is only a single edge away from the right side of the tree and we rotate rightwards, this will change one of the right edges in its path to cito a left edge, so G(ci+1) is distinct from G(c) and its closest ancestor on the right side of the tree will be one level further from the root node of the tree, so we have D(ci+1) = (ri−1, si+ 1) = (ri+1, si+1). If G(ci) is more than a single edge away from the right side of the tree, a right rotation will not change D(ci) and we have D(ci+1) = D(ci). A left rotation, if permitted, moves G(c) one level further from the root node, but 24 SEAN CLEARY AND JENNIFER TABACK will not change the location of the closest ancestor of G(c) on the right side of the tree, and we obtain D(ci+1) = D(ci). •Case k > si:In this case, the right or left rotation takes place further down the right side of the tree and does not affect the location of cior G(ci) = G(ci+1), so we have D(ci+1) = D(ci). We note that it is possible to move cand G(c) by a sequence of rotations to hang from the left side of the tree, but that they will need to be moved back to the hang from the right side of the tree to split the sibling pair [n−1, n] so this will not happen in any minimal length transformation. We know that D(c) begins at (n−m−2, m + 1), and the sibling pair [n−1, n] is not destroyed until after D(ci) = (0, l), with l≤m. The only rotations which potentially reduce the first coordinate n−m−2 are from the case where s=k, with k≤m. There will need to be at least n−m−2 such reductions, and each such reduction will increase the second component by 1. We will require at least n−m−2 additional reductions to reduce the second coordinate back to its starting value, which do not change the first coordinate. We then must perform at least one additional rotation to decrease the second coordinate to mbefore the sibling pair in question can be destroyed. This gives a minimum of 2n−2m−3 rotations before we are in a position to destroy the sibling pair [n−1, n]. ¤ Similarly, in the following lemma we consider the number of rotations required to destroy the sibling pair [n, n + 1] in the positive tree T2of w. Lemma 3.14. Let T2be the positive tree for the word xm+2xm+3 ···xnx−1 n−1· · · x−1 m+1 with m < n. The tree T0resulting from the application of at most 2n−2m−2 rotations at locations on the right side of the tree at levels less than or equal to mwill contain the sibling pair [n,n+1]. Proof. We note that in this case, when cis the node with exposed leaves numbered nand n+1, we have D(c) = (n−m−2, m+2) and to reduce D(c) to (0, l) with l≤mwill take at least (n−m−2)+(n−m−2)+2 = 2n−2m−2 rotations by the same analysis as in Lemma 3.13. ¤ These lemmas show that we can find elements with nnodes whose restricted right arm rotation distance satisfies both upper and lower bounds with a multiplicative constant of 4, proving Theorem 3.10. Proof of Theorem 3.10. We consider the reduced tree pair diagram (T1, T2) corresponding to the element w=xm+2xm+3...xnx−1 n−1...x−1 m+1, as above. Lemma 3.13 shows that any application of 2n−2im−3 allowed rotations to T1will still result in a tree with leaves n−1 and npaired, and BOUNDING RIGHT-ARM ROTATION DISTANCES 25 Lemma 3.14 shows that any application of 2n−2im−2 allowed rotations to T2will result in a tree with leaves nand n+ 1 paired. Since it will take at least one additional rotation to destroy each sibling pair, we have that the restricted right arm rotation distance between the two trees is at least 4n−4m−4. ¤ Theorem 3.10 gives a family of pairs of trees with nnodes which satisfy a lower bound on restricted right-arm rotation distance with respect to a generating set S0which includes all generators from x0to xm. Restricting the generating set to a subset Sof S0which includes x0can only increase the restricted right-arm rotation distance between two trees or cause it to be undefined. In the case of the words used in the proof of Theorem 3.10, the restricted right-arm distance will still be defined by Lemma 3.6, as the trees involved do not involve generators of index lower than the largest level where rotation is allowed. Thus we have proven Theorem 3.9 as well. 4. Bounding right-arm rotation distance The original arguments of Culik and Wood [8] which give a bound on ordinary rotation distance apply to right-arm rotation distance as well. Their argument is that any binary tree Twith nnodes can be transformed to or from the all-right tree with nnodes by no more than n−1 rotations, all of which can be chosen to lie on the right arm of the tree. Thus, the right-arm rotation distance between two trees T1and T2each with nnodes is no more than 2n−2, as we can transform T1to the all-right tree and from there transform it to T2. While this bound is not optimal for the original rotation distance, we show that it is optimal for right-arm rotation distance. Theorem 4.1. For each n≥3, there are rooted binary trees T1and T2each with nnodes so that the right-arm rotation distance between them satisfies dRA(T1, T2) = 2n−2. Proof. To prove this we consider the elements of Fwith normal form x0x1x2x3. . . xn−2x−1 n−3x−1 n−4. . . x−1 1x−2 0, pictured in Figure 10, which have n nodes and have word length 2n−2 with respect to the infinite generating set for F. It follows from Proposition 3.7 that this is also the right-arm rotation distance between the two trees. ¤ 5. Left-arm and spinal rotation distances We now consider rotation distances which include rotations at nodes along the left side of the tree instead of or in addition to nodes along the right side of the tree. It is clear by symmetry that restricted left-arm rotation distance, which allows rotations at only nodes on the left side of the tree and