Growth of positive words and lower bounds of the growth rate for Thompson's group (F)p

GROWTH OF POSITIVE WORDS AND LOWER BOUNDS OF THE GROWTH RATE FOR THOMPSON’S GROUPS F(p) JOS´ E BURILLO AND VICTOR GUBA Abstract. Let F(p), p≥2 be the family of generalized Thompson’s groups. Here F(2) is the famous Richard Thompson’s group usually denoted by F. We find the growth rate of the monoid of positive words in F(p) and show that it does not exceed p+ 1/2. Also we describe new normal forms for elements of F(p) and, using these forms, we find a lower bound for the growth rate of F(p) in its natural generators. This lower bound asymptotically equals (p−1/2) log2e+1/2 for large values of p. Introduction The family of generalized Thompson’s groups F(p) was introduced by K. S. Brown in [6]. Additional facts about these groups can be found in [8, 22]. The case p= 2 corresponds to the famous Richard Thompson’s group F. See the survey [9] for details about this group. The groups F(p) have many common features. All of them are embeddable into each other [4]. None of them has free non-abelian subgroups. None of these groups satisfy any nontrivial group law. The derived subgroups of each of the F(p) is simple (infinitely generated). Every proper homomorphic image of F(p) is abelian (so these groups are not residually finite). Each F(p) is finitely presented and has quadratic Dehn function [16]. Each of these groups has a faithful representation by piecewise linear functions. The word problem has an easy solution in each of these groups. Also all these groups are diagram groups in the sense of [17]. Namely, F(p) is a diagram group over a very simple semigroup presentation hx|x=xpi. It 2000 Mathematics Subject Classification. Primary 20F32; Secondary 05C25. Key words and phrases. Generalized Thompson’s groups; growth. Both authors thank the Centre de Recerca Matem`atica for the hospitality and support. The research of the second author was also partially supported by the RFFI grant 05-01- 00895. 1 2 JOS´ E BURILLO AND VICTOR GUBA follows then from [17, Section 15] that F(p) has solvable conjugacy problem. Each group F(p) satisfies homological finiteness condition F∞. All integer homology groups Hn(F(p),Z) are free abelian of finite rank and the Poincar´e series are rational [19]. However, there is some difference between the groups of this family. Brin [3] described the group Aut Ffor F=F(2). Some information about automorphisms of F(p), where p > 2, can be found in [4], where it is shown that already for p= 3 there are “wild” automorphisms of F(p). The goal of this article is to obtain analogs of some results for the group F. The first author found the growth function of the monoid of positive elements of F. This function is rational, namely, it equals 1−x2 1−2x−x2+x3. Notice that the elements x0,x1, . . . , xp−1generate a free submonoid of rank pin F(p). Thus the growth rate of positive elements in F(p) is at least p. In this paper we show that for any p, the exact value of the growth rate of positive elements is only slightly higher than p— it never exceeds p+ 1/2. Guba and Sapir [18] found two new normal forms for elements of F. One of them is a normal form in the infinite set of generators. This normal form is locally testable (unlike the standard normal form). It has the same feature as the normal form in the free group: a word is in a normal form if and only if all its subwords of length 2 are in the normal form. In this paper, we find such a form for every F(p). Another normal form constructed in [18] for Fallows one to construct a regular set of normal forms in F. We find an analogous construction for each F(p). Using the above regular normal form, the second author proved in [15] that the growth rate of the group Fin generators x0,x1is at least (3+√5)/2. Notice that neither the growth function, nor the growth rate for Fis known at the present. In this paper we find a lower bound of the growth rate for each of the groups F(p), where the generating set consists of x0,x1, . . . , xp−1. We show that the lower bound is a root of a certain algebraic equation and find the asymptotic behaviour of this root. For large values of p, this is (p−1/2) log2e+ 1/2, where log2e= 1.442695 . . . . The plan of the paper is as follows. In Section 1 we recall the definition of the family F(p) of generalized Thompson’s groups and some basic facts about growth functions and growth rates. This Section also contains a description of (positive) elements in F(p) in terms of rooted p-trees. In Section 2 we describe Fordham’s method to calculate the word length in F(p). We restrict ourselves to the case of positive words only (the description for this case is much simpler). Recall that for the case p= 2, a LOWER BOUNDS FOR THE GROWTH OF F (P) 3 fast algoritm to find the word length metric was described in [11, 12]. This algorithm is very effective but it has quite a complicated description. A simplification of the method due to Belk and Brown can be found in [1]. One of the easiest algorithms to find the word length in F(the so-called Length Formula) is contained in [15, Section 5]. Notice that for p > 2, none of the simplified versions exists so we use Fordham’s approach from [13]. In Section 3, using Fordham’s method, we find equations for generating functions describing the growth of F+(p). We solve these equations in Section 4 and show that the generating function for positive words in F(p) is irrational provided p > 2 (unlike the case p= 2). Then we find the growth rate of positive words in F(p) as a root of an algebraic equation. We prove that this growth rate never exceeds p+ 1/2 approaching this value as p approaches infinity. Thus the set F+(p) of all positive words is not much higher than the free submonoid generated by x0,x1, . . . , xp−1. Section 5 describes two new normal forms of elements in F(p). The first of these forms is locally testable (one needs to test only subwords of length 2, similar to a free group). The second of the normal forms leads to a regular language that represents each element of F(p) exactly once. Based on that regular language, we construct the corresponding automaton and find a lower bound for the growth rate of F(p) in Section 6. This lower bound is given as a root of an algebraic equation. We also describe its asymptotic behaviour showing that it approaches (p−1/2) log2e+ 1/2 for large values of p. 1. Preliminaries The family of generalized Thompson’s group can be defined as follows. The group F(p) is the group of all piecewise linear self homeomorphisms of the unit interval [0,1] that are orientation preserving (that is, send 0 to zero and 1 to 1) with all slopes integer powers of pand such that their singularities (breakpoints of the derivative) belong to Z[1 p]. The group F(p) admits a presentation given by (1) hxi(i≥0) |xjxi=xixj+p−1(i < j)i. This presentation is infinite, but a close examination shows that the group is actually finitely generated, since x0,x1, . . . , xp−1are sufficient to generate it. In fact, the group is finitely presented. The finite presentation is awkward and it is not used much. The symmetric and simple nature of the infinite presentation makes it much more adequate for almost all purposes. One such example where the infinite presentation is particularly appropriate is in the construction of the normal form. A word given in the generators 4 JOS´ E BURILLO AND VICTOR GUBA xiand their inverses, can have its generators moved around according to the relators, and the result is the following well-known statement: Theorem 1.1. An element in F(p)always admits an expression of the form xi1xi2···ximx−1 jn···x−1 j2x−1 j1, where i1≤i2≤ ··· ≤ im, j1≤j2≤ ··· ≤ jn. In general, this expression is not unique, but for every element there is a unique word of this type which satisfies certain technical condition (see [9] for details). This unique word is called the standard normal form for the element of F(p). Observe that the infinite presentation for F(p) is actually a monoid presentation. Hence F(p) admits a submonoid, the submonoid F+(p) given by the same presentation, whose elements are called positive words. Theorem 1.1 shows that F(p) is the group of right fractions of this monoid. An element of F(p) can be represented by two subdivisions of the interval [0,1], namely, the subdivision into intervals which get mapped linearly to each other. A subdivision of this type, where the dividing points are all in Z[1 p], can always be obtained by subsequent subdivisions of the interval into pequal pieces. Hence, a subdivision of the interval is equivalent to a rooted tree where each vertex has valence p+ 1 except the root, which has valence p(or 1 in case when the tree consists of the root only), and the leaves, which have valence 1. A node (except the root and the leaves) is pictured to have one edge going up and pedges going down to its pchildren. These trees will be called rooted p-trees. An element of F(p) is then represented by a pair of rooted p-trees called the source tree and the target tree. This representation has been extensively studied in the case p= 2. Note that positive words can be represented by a single p-tree, because the other tree is always the same: the tree which consists of all right carets. A piece of these p-trees consisting of a node and its pedges going down to its children is called a caret. Carets are the building blocks of the trees and they give rise to the algorithm for finding the word metric in F(p), see Section 2. As stated in the introduction, the exact growth function for the groups F(p) is not known. In this paper we will give lower bounds for growth rates of these groups, computing lower bounds for the number of elements in each length. To be precise, given a finitely generated group Gwith finite generating set X, denote its sphere of radius nby S(n) = {g∈G|`(g) = n}, LOWER BOUNDS FOR THE GROWTH OF F (P) 5 where `(g) is the length of g∈Gin the set of generators X. We also have the ball of radius n B(n) = n [ k=0 S(k). If γn= #B(n), the series Γ(x) = ∞ X n=0 γnxn is called the (general) growth function for Gwith respect to X, and the number γ= lim n→∞ γn is the growth rate of Gwith respect to X. The limit always exists due to the submultiplicative property of γn, that is, γm+n≤γmγnfor all m, n ≥0. Also, the spherical growth function is given by σn= #S(n) and Σ(x) = ∞ X n=0 σnxn, which has the same growth rate as the general growth function (for all infinite groups). For details about growth functions, see, for instance, [14]. If P⊆Gis a subset of a group, not necessarily a subgroup, we can define the growth functions of the set Pby the same formulas as above but where the coefficients are actually the cardinals of the sets P∩B(n) or P∩S(n). The goal for one of the next sections is to compute the growth series of the subset F+(p) in F(p). In order to do that, we need to describe the algorithm for calculating the word metric in F(p). 2. Positive words in Thompson’s groups F(p)and Fordham’s method In 1995, S. Blake Fordham [11] constructed an algorithm which, for any given element in F=F(2), finds its distance to the identity in the word metric given by generators x0,x1. This algorithm consists in defining different types of carets, then having each caret of the source tree paired to its corresponding caret in the target tree, and assigning a weight to each type of pairs of carets. A table is given for all possible pairs of types, with the assignment of the weight. The sum of all the weights of all the pairs is the exact distance from the element to the identity. In a set of unpublished notes [13], Fordham extends his method to the groups F(p). This method will be the starting block of the computation. The method used to compute this growth will be an extension to F(p) of the method developed in [7] for the case of F=F(2). Consider a positive 6 JOS´ E BURILLO AND VICTOR GUBA element of F(p). As we know, the element can be represented by a rooted p-tree. We are going to define different types of carets and their weights, following Fordham [13]. A caret will be called left or right if it is situated in the leftmost edge of the tree or in the rightmost edge, and middle or interior if it is situated in the middle, i.e. if it is not right or left. For instance, a caret is left if it represents a subinterval of [0,1] which has left endpoint equal to zero. Middle carets will be subdivided into p−1 types, denoted by M1,M2, . . . , Mp−1according to which caret they are children of, and its position as child. The children of a caret are subdivided in two types, the predecessors and the successors. This subdivision will give a total order to the set of carets, with a caret being always after its predecessor children and before its successors. The definitions of the caret types are as follows: •The root caret is special. Its children are: –Its left child is a left caret and it is the only predecessor. –Its middle children are successors, and have types M1,M2, . . . , Mp−2, in order-preserving way. –Its right child is obviously a successor and a right caret. •A left caret has the following children: –Its only predecessor is the left child, a left caret. –All the other children are successors, all middle carets, and of types M1,M2, . . . , Mp−1, in order. •A right caret has the following children: –One single predecessor of type Mp−1. –It has p−1 successors, which in order are of types M1,M2, . . . , Mp−2and the last one of type R. •A caret of type Mi(1 ≤i≤p−1) has the following children: –The first p−ichildren are predecessors, and their types are Mi, . . . , Mp−1. –The other ichildren are successors, and they are of types M1, M2, . . . , Mi. For the purposes of computing the length of an element, these caret types are subdivided in further types depending on the existence of predecessor and successor types. This classification is actually more complicated in Fordham’s paper but we do not need the total strength of the method since we are dealing only with positive words. We will indicate also which is the weight of each caret for the purposes of the computation of the length of a positive word. The caret types are as follows: LOWER BOUNDS FOR THE GROWTH OF F (P) 7 •The root, which has always weight zero. •Left carets, which have always weight one. •Carets of type R∅are right carets whose all successors are right carets, i.e., it has no middle successors. Its only successors hang from its rightmost leaf. These carets carry weight zero. •Carets of type RMare right carets which are not R∅, that is, which have middle successors. Observe that the middle successors do not have to be immediate successors, they can be successors of successors. Carets of type RMhave weight two. •Carets of type Mi ∅are middle carets which do not have any successor children. They carry weight one. •Carets of type Mi Mare middle carets which have at least a successor child. These carets have weight three. Observe that the index on the middle carets is only necessary to identify its successors, but it has no role in the weight assignment beyond that one. Now, the main theorem giving the length is as follows: Theorem 2.1. (S. B. Fordham) [13] Given a positive word in F(p)represented by a rooted p-tree, the distance from this element to the identity (in the word metric for F(p)with generators x0,x1, . . . , xp−1)is equal to the total sum of the weights of its carets. 3. Generating functions for the growth of positive words Once the theorem for the length has been established, now the computation of the growth function is reduced to a combinatorial problem, namely, finding how many trees have a given weight, according to the rules above. The method for finding the number of trees with a given weight is to split the trees in several ones in such a way that recurrences can be found. The reader can see details about generating functions in [23], and can see this method used already in [7]. We will make use of several sequences: •The sequence sn= #(F+(p)∩S(n)). This is the number of trees which have weight n. •The sequence ln. This sequence gives the number of subtrees which can be left subtrees of a rooted p-tree and such that its total weight is n. The subtrees are required to be strict, that is, the main tree does not qualify as a left subtree. •Analogously the sequence rnis the sequence of possible right subtrees of weight n. •The sequence m(i) nfor i= 1, . . . , p −1, gives the number of interior subtrees which start with a caret of type Mi. Observe that this 8 JOS´ E BURILLO AND VICTOR GUBA subtree is completely composed of middle carets, and also with total weight n. Observe that the subtrees are always considered as subtrees of the main tree, which means that, for instance, a left subtree never has carets of type Rbecause that would mean it is the total tree. A subtree which starts in an Micaret has all interior carets. Each one of these sequences will have its generating function: S(x) = ∞ X n=0 snxnL(x) = ∞ X n=0 lnxn R(x) = ∞ X n=0 rnxnMi(x) = ∞ X n=0 m(i) nxn. Now we will establish relations between the sequences which will give functional equations for their generating functions, which then will allow us to find the growth of the submonoid of positive words. For instance, if one considers the tree representing a word, and assumes the tree has total weight n, since the root has weight zero, the weight has to be distributed among all the pchildren subtrees. Hence, a tree of total weight nwill be obtained every time that we take a family of subtrees such that the sum of their separate weights as subtrees is n. This fact gives the first formula satisfied by the sequences, and also by the generating functions: (2) sn=X j0+···+jp−1=n lj0m(1) j1···m(p−2) jp−2rjp−1 (3) S=LM1···Mp−2R. To find a formula for the function L(x) of left subtrees, one needs to consider that left carets have weight 1. Hence the different subtrees only have to add up to n−1. The formula is ln=X j0+···+jp−1=n−1 lj0m(1) j1···m(p−2) jp−2m(p−1) jp−1 (4) L−1 = xLM1M2···Mp−1. The formula for the generating functions is obtained by multiplying each side of the formula for sequences by xn. The right hand side has an x multiplying because the indices are shifted by one. For the function for right trees, one has to take into account the fact that a right caret can be of type R∅or RM, with weights zero and two respectively. For the first possibility, the caret is of type R∅, and all its LOWER BOUNDS FOR THE GROWTH OF F (P) 9 successors have no weight. Observe that in a positive word there can be one and only one caret of type R∅, because any others would be reducible. Hence, if the caret is of type R∅, all the weight is concentrated in its only predecessor. So there are as many right subtrees of this type as trees of the type Mp−1with the same weight, which gives the first part of the recurrence equal to m(p−1) n. If the right caret is of type RM, it carries weight 2 and one the successors is necessarily nonempty with a middle caret somewhere. Hence if one of the successors is necessarily nonempty, the term in the recurrence has all possible weights for these successors. The formula is rn=m(p−1) n+X j0+···+jp−1=n−2 j1+···+jp−1≥1 m(p−1) j0m(1) j1···m(p−2) jp−2rjp−1 (5) R=Mp−1+x2(M1M2···Mp−1R−Mp−1). Finally, the middle subtrees are the ones whose children are also middle subtrees and hence facilitate the resolution of the equations. A middle caret of type Mihas either weight 1 if its successors are empty or weight 3 if one of the successor subtrees is nonempty. Both cases correspond to the two adding terms of the formula for the sequence: m(i) n= =X ji+···+jp−1=n−1 m(i) ji···m(p−1) jp−1+X j0+j1+···+jp−1=n−3 jp−i+···+jp−1≥1 m(i) j0···m(p−1) jp−i−1m(1) jp−i···m(i) jp−1 which gives the following formula for the generating functions: (6) Mi−1 = xMiMi+1 ···Mp−1+x3MiMi+1 ···Mp−1(M1···Mi−1Mi−1). Solving these equations will give us information on the function S(x), which is the one we are interested in, and the growth of positive elements in the groups F(p). 4. Growth functions and growth rates of F+(p) Now we collect formulas (3), (4), (5), (6) to find the equation on S(x) and the radius of convergence of the corresponding series. First of all, we have to mention that F+(p) has a free submonoid generated by x0,x1, . . . , xp−1and so the growth rate of F+(p) is at least p. As we will see at the end of this Section, the exact value of the growth rate is only slightly larger than p. (In fact, it is always less than p+ 1/2.) Let M(x) = M1(x)M2(x)···Mp−1(x). 16 JOS´ E BURILLO AND VICTOR GUBA distinguish between these two cases. Namely, if mh<0, then dh= 0, kh=mh. If mh≥0, then kh= 0, dh=mh. Now we know dhand kh. If h≥2, then kh−1≤0. As above, we have one of the two cases: kh−1<0, dh−1= 0, or kh−1= 0. The number kh−1+dh−1is negative in the first case and nonnegative in the second case. But this number equals mh−1+dh, so we know it and thus we are able to distinguish these cases. In the first case we have dh−1= 0, kh−1=mh−1+dh; in the second case —kh−1= 0, dh−1=mh−1+dh. Therefore, we know dh−1and kh−1. Continuing in this way, we get the values of dh−2,kh−2, . . . , d1,k1. At the final step we get k0=m0+d1. Now we show that the mapping is surjective. We start with a word from Nfin. This word has the form (12) xm0 0xl1 r1xm1 0xl2 r2···xmh−1 0xlh rhxmh 0. Using the rules described in the first part of the proof, we define the numbers k0,d1,k1, . . . , dh,kh. It follows that di≥0 for all ifrom 1 to h. So we can form a word was in (10), where αi=ri+di(p−1) (1 ≤i≤h). It is obvious that ¯wequals the word (12). It remains to prove that wbelongs to Ninf . Let us assume the contrary. Since whas no subwords of the form xε 0x−ε 0, it should contain one of the following subwords: a) xε ix−ε i(i≥1, ε=±1); b) x±1 jxi(j > i); c) x±1 j+p−1x−1 i(j > i). In case a), ¯wwill contain a forbidden subword of the form xε rx−ε r. Notice that ki≤0 for all 1 ≤i≤h; if ki<0, then di= 0. This means that in cases b) and c) one has i≥1. Let j=α+d(p−1), i=β+d0(p−1), where 1≤α, β ≤r−1, d, d0≥0. Applying the “bar” mapping to b) and c), we see that the word ¯wcontains u=x±1 αxd−d0 0xβin case b) and v=x±1 αxd−d0+1 0x−1 β in case c). Since j > i, we have (d−d0)(p−1) > β −α > −(p−1). Hence d−d0≥0. If uis not forbidden, then α≤β. But in this case d−d0>0 so uhas to be forbidden anyway. If vis not forbidden, then we also have α≤β, which implies d−d0+ 1 ≥2. We have a final contradiction. The proof is complete. ¤ From Lemmas 5.2 and 5.3 we obtain Theorem 5.4. Each element g∈F(p)can be uniquely represented by a word w∈ Nfin. This means that for every g∈F(p)there is exactly one word over {x±1 0, x±1 1, . . . , x−1 p−1}that represents gand has no forbidden subwords. This gives a regular set of normal forms for the group F(p). LOWER BOUNDS FOR THE GROWTH OF F (P) 17 Indeed, the set of forbidden subwords is a regular language. So the set Nfin of words that do not contain forbidden subwords will be also regular. Throughout the rest of the paper, we will denote this language by Lp. (For basic properties of regular languages see [21].) 6. Lower bounds for the growth rates of F(p) A lower bound of (3 +√5)/2 = 2.618 . . . for the growth rate of F=F(2) was obtained by the second author in [15]. Now we will find a similar lower bound for each F(p). In the previous section, we constructed a regular language Lpof normal forms for F(p). Each word of length nin Lpis at a distance at most nfrom the identity in the Cayley graph of F(p). So the growth function of Lpdoes not exceed the number of elements in the ball of radius nfor F(p). Then, finding the growth function and the growth rate of Lp, we find a lower bound for the growth rate of the group F(p). An automaton to recognize the language Lphas 3p+ 1 states. However, it is easier to construct a directed graph with only 2p+ 1 vertices (states). This graph will be denoted by Apand we will also call it an automaton although its edges have no labels. The description of Apis as follows. The vertices (states) of Apare denoted by q,q0,q1, . . . , qp−1,q1,0,q2,0, . . . , qp−1,0, ¯q. They will correspond to the following partition of Lpinto disjoint subsets: •The set {1}that consists of the empty word (state q). •The set of words that end with x±1 0and do not have a terminal segment of the form x±1 ixk 0, where 1 ≤i≤p−1, k≥1 (state q0). •The set of words that end with x±1 i(state qifor each 1 ≤i≤p−1). •The set of words that end with x±1 ix0(state qi,0for each 1 ≤i≤ p−1). •The set of words that end with x±1 ixk 0for some 1 ≤i≤p−1 and k≥2 (state ¯q). Let w∈ Lp. If wis empty, then wx±1 iwill be in Lpfor all 0 ≤i≤p−1. We draw two arrows from qto qifor each 0 ≤i≤p−1. Let wcorrespond to the state q0. Then w=vxε 0for some word vand for some ε=±1. The word wxε 0will be in Lp; for each 1 ≤i≤p−1 the word wx±1 iwill be also in Lpsince whas no terminal segments of the form x±1 ixk 0(1 ≤i≤p−1, k≥1. Thus we draw an arrow from q0to itself and two arrows from q0to each qi(1 ≤i≤p−1). Let wcorrespond to qi(1 ≤i≤p−1). The words wx−1 0and wx0belong to Lp; we draw an arrow from qito q0and an arrow from qito qi,0. The words wxjbelong to Lpwhenever i < j ≤p−1; the words wx−1 jbelong to 18 JOS´ E BURILLO AND VICTOR GUBA Lpfor all 1 ≤j≤p−1. So we draw one arrow from qito each q1, . . . , qi and two arrows from qito each qi+1, . . . , qp−1. Let wcorrespond to qi,0(1 ≤i≤p−1). The word wx0is in Lpand we draw an arrow from qi,0to ¯q. Also wx−1 j∈ Lpwhenever i≤j≤p−1. So one arrow goes from qi,0to each qi, . . . , qp−1. No other arrows can appear. Finally, let wcorrespond to ¯q. Now only wx0leads to a word in Lp; it corresponds to an arrow from ¯qto itself. The description of Apis complete. Notice that the number of words in Lpof length nis exactly the number of (directed) paths of length nin Ap starting at q. We would like to compute the number of paths in Apof length nstarting at qand ending at a given state. For each state we consider the corresponding generating function. Namely, to each vertex vwe assign a series of the form P∞ n=0 antn, where anis the number of paths in Apstarting at qand ending at v. These generating functions will be denoted by f,fi (0 ≤i≤p−1), fi,0(1 ≤i≤p−1), ¯ ffor each of the states, respectively. We will write down a system of equations for these functions. First of all, it is clear that f(t) = 1. To find f0, we mention that two arrows go from qinto q0and one arrow goes into q0from each of the states q0,q1, . . . , qp−1. Hence (13) f0=t(2f+f0+f1+···+fp−1). Given a vertex qi(1 ≤i≤p−1), we observe that two arrows go into qi from q,q0, . . . , qi−1and one arrow from qi, . . . , qp−1. Also one arrow goes into qifrom each q1,0, . . . , qi,0. Thus (14) fi=t(2f+ 2f0+···+ 2fi−1+fi+···+fp−1) + t(f1,0+···+fi,0). Notice that fi,0=tfifor each 1 ≤i≤p−1 because only one arrow goes into qi,0(from the state qi). Thus we can rewrite (14) as follows: (15) fi=t(2f+ 2f0+···+ 2fi−1+fi+···+fp−1) + t2(f1+···+fi). Finally, there is one arrow that goes into ¯qfrom each of the states q1,0, . . . , qp−1,0, ¯q. So (16) ¯ f=t(f1,0+···+fp−1,0+¯ f) = t2(f1+···+fp−1) + t¯ f. In order to solve the system, let us consider the difference of equation (15) with i= 1 and (13). This gives f1−f0=tf0+t2f1, that is, (1−t2)f1= (1 + t)f0. So f0= (1 −t)f1. Now suppose that 1 ≤i < p −1. If we take the difference between fi+1 and fiusing (15), we obtain fi+1 −fi=tfi+t2fi+1, which implies fi= (1 −t)fi+1. LOWER BOUNDS FOR THE GROWTH OF F (P) 19 Now for all 0 ≤i≤p−1 one has fi= (1 −t)p−1−ifp−1. The equation (13) becomes (1−t)p−1fp−1= 2t+tfp−1((1−t)p−1+···+(1−t)+1) = 2t+fp−1(1−(1−t)p). This gives (17) fp−1(t) = 2t (1 −t)p+ (1 −t)p−1−1. In order to find the number of words in Lphaving length n, we need to add all the generating functions for all states. The result will be Φp(t) = 1+f0+f1+···+fp−1+t(f1+···+fp−1) + t2 1−t·(f1+···+fp−1) (here we used (16) to express ¯ f). Taking into account that f1+···+fp−1=1−t t·f0−2 from (13), we have Φp(t) = 1+f0+µ1 + t+t2 1−t¶(f1+···+fp−1) = 1+µ1 + 1 t¶f0−2 1−t. Now, using f0= (1 −t)p−1fp−1and (17), we finally have (18) Φp(t) = 1 + t 1−t·1−t(1 −t)p−1 (1 −t)p+ (1 −t)p−1−1. This is the generating function for Lp. Thus the growth rate of Lpwill be the reciprocal of t, where tis the smallest positive root of the denominator of the right hand side of (18). The number y= (1 −t)−1is the root of yp=y+ 1. It is clear that y > 1. Let y= 1 + x, where x > 0. We would like to solve the equation (1 + x)p= 2 + x. Notice that 0 <x<1. Since (1 + x)p<3, the root x approaches 0 as pgoes to infinity. The equation (1 + x)p= 2 + xcan be written as p=ln(2 + x) ln(1 + x)=ln 2 + ln(1 + x/2) ln(1 + x)=ln 2 + x/2 + o(x) x−x2/2 + o(x2). Therefore, (19) p−1 2 ln 2 =1 + o(x) x−x2+ox2=x−1(1 + x/2 + o(x)) = x−1+1 2+o(1) as p→ ∞. 20 JOS´ E BURILLO AND VICTOR GUBA We are interested in the number ξp=t−1, where tis the root of (1 − t)p+ (1 −t)p−1−1 = 0. Here (1 −t)−1=y, where y= 1 + xis the root of yp=y+ 1. It is easy to see that ξp= 1 + x−1. So we deduce from (19) that ξp=p−1 2 ln 2 +1 2+o(1), p → ∞. It is also easy to see that ξp=t−1satisfies the following equation: (2ξ− 1)(ξ−1)p−1=ξp. So we proved Theorem 6.1. The growth rate of the group F(p),p≥2has a lower bound of ξp, where ξpsatisfies the equation (2ξ−1)(ξ−1)p−1=ξp. The following asymptotic formula holds: ξp=p−1 2 ln 2 +1 2+o(1), p → ∞. Here are several numerical values of ξp: ξ2= 2.618033989 ξ3= 4.079595623 ξ4= 5.530132718 ξ5= 6.977144180 and so on. For large values of p, the growth rate of F(p) is at least 0.72(2p− 1) (recall that 2p−1 is the maximum value of the growth rate of a pgenerated group; this happens if and only if the group is free of rank p). It would be interesting to find nontrivial upper bounds for the growth rates of F(p). This means to find a constant c < 1 such that the growth rate of F(p) in its natural generators does not exceed c(2p−1). References [1] J. M. Belk, K. S. Brown. Forest diagrams for elements of Thompson’s group F. http://www.arxiv.org/abs/math.GR/0305412 [2] R. V. Book and F. Otto. String-rewriting systems. Springer-Verlag, New York, 1993. [3] M. G. Brin. The chameleon groups of Richard J. Thompson: Automorphisms and dynamics. Inst. Hautes ´ Etudes Sc. Publ. Math. 84 (1996), 5–33. [4] M. G. Brin, F. Guzm´an. Autmorphisms of generalized Thompson’s groups. J. Algebra 203, no. 1 (1998), 285–348. [5] M. G. Brin, C. C. Squier. Groups of piecewise linear homeomorphisms of the real line. Invent. Math. 79 (1985), 485–498. [6] K. S. Brown. Finiteness properties of groups. J. Pure Appl. Algebra 44 (1987), 45–75. [7] J. Burillo. Growth of positive words in Thompson’s group F. Comm. Algebra 32, no. 8 (2004), 3087–3094. LOWER BOUNDS FOR THE GROWTH OF F (P) 21 [8] J. Burillo, S. Cleary, M. Stein. Metrics and embeddings of generalizations of Thompson’s group F. Trans. Amer. Math. Soc. 353, no. 4 (2001), 1677–1689. [9] J. W. Cannon, W. J. Floyd and W. R. Parry. Introductory notes on Richard Thompson’s groups. L’Enseignement Math´ematique (2) 42 (1996), 215–256. [10] N. Dershovitz and J.-P. Jouannaud. Rewrite systems. In: J. van Leeuwen, editor, handbook of Theoretical Computer Science, chapter 6, pp. 244–320. Elsevier Science Publishers B.V., 1990. [11] S. B. Fordham. Minimal length elements of Thompson’s group F. PhD thesis, Brigham Young University (1995). [12] S. B. Fordham. Minimal length elements of Thompson’s group F. Geom. Dedicata 99 (2003), 179–220. [13] S. B. Fordham. Minimal length elements of F(p) (unpublished notes). [14] R. I. Grigorchuk, P. de la Harpe. On problems related to growth, entropy, and spectrum in group theory. J. Dynam. Control Systems 3 (1997), 51–89. [15] V. S. Guba. On the properties of the Cayley graph of Richard Thompson’s group F. Int. J. Alg. Comp. 14, no. 5-6 (2004), 677–702. [16] V. S. Guba. The Dehn function of Richard Thompson’s group Fis quadratic. Invent. Math. (2005, to appear). [17] V. S. Guba, M. V. Sapir. Diagram groups. Memoirs of the Amer. Math. Soc. 130, no. 620 (1997), 1–117. [18] V. S. Guba, M. V. Sapir. The Dehn function and a regular set of normal forms for R. Thompson’s group F. J. Austal. Math. Soc (Ser. A) 62 (1997), 315–328. [19] V. S. Guba, M. V. Sapir. Diagram groups and directed 2-complexes: homotopy and homology. J. Pure and Appl. Algebra (2005, to appear). [20] W. Ljunggren. On the irreducibility of certain trinomials and quadrinomials. Math. Scand. 8 (1960), 65–70. [21] A. Salomaa. Jewels of formal language theory. Computer Science Press, 1981. Rockville, Maryland. [22] M. Stein. Groups of piecewise linear homeomorphisms. Trans. Amer. Math. Soc. 332, no. 2 (1992), 477–514. [23] H. Wilf. Generatingfunctionology. Academic Press, Boston, MA, 1994. Escola Polit` ecnica Superior de Castelldefels, UPC, Avda del Canal Ol´ ımpic s/n, 08860 Castelldefels, Barcelona, Spain E-mail address:[email protected] Vologda State Pedagogical University, 6 S. Orlov Street, Vologda 160600 Russia E-mail address:[email protected]