Computational explorations in Thompson's group F

COMPUTATIONAL EXPLORATIONS IN THOMPSON’S GROUP F JOS´ E BURILLO, SEAN CLEARY, AND BERT WIEST Abstract. Here we describe the results of some computational explorations in Thompson’s group F. We describe experiments to estimate the cogrowth of Fwith respect to its standard finite generating set, designed to address the subtle and difficult question whether or not Thompson’s group is amenable. We also describe experiments to estimate the exponential growth rate of Fand the rate of escape of symmetric random walks with respect to the standard generating set. 1. Introduction Richard Thompson’s group Fhas attracted a great deal of interest over the last years. The group Fis a finitely presented group which arises quite naturally in different contexts, and allows several different, but fairly simple, descriptions – for instance by a presentation, as a diagram group [14], as a group of homeomorphisms of the unit interval, as the geometry group of associativity [7], and as the fundamental group of a component of the loop space of the dunce hat. Cannon, Floyd and Parry [3] give an excellent introduction to F. The interest in this group stems partly from F’s unusual properties, and partly from the fact that some of the basic questions about this group are still open, in particular those related to its cogrowth and growth. It seems clear is that Flies very close to the borderline between different regimes. Probably the most famous open question is whether or not Fis amenable. Also, it is known that Fhas exponential growth, but the growth rate is unknown. Similarly, the rate of escape of random walks in Fis unknown. The question of amenability is especially intriguing since Fis either an example of a finitely presented non-amenable group without free non-abelian Date: May 31, 2005. We would like to thank the Centre de Recerca Matem`atica for their hospitality and support, and the first and second authors are grateful for support from NSF grant #0305545. 1 2 JOS´ E BURILLO, SEAN CLEARY, AND BERT WIEST subgroups, or an example of a finitely presented amenable but not elementary amenable group. Though there are finitely presented examples of groups for each of these phenomena from Grigorchuk [11] and Sapir and Olshanskii [17], those groups were constructed explicitly for those purposes, whereas Fis a more “naturally occurring” example to consider – so either answer would be remarkable. The aim of this paper is to contribute new empirical evidence to the quest to understand cogrowth, growth, and escape rate. This evidence was obtained using large computer simulations. The structure of this paper is as follows. In Section 2 we recall briefly the definition and those properties of the group Fthat will be needed in the paper. Moreover, we give the definition of amenability which will be used in our experiments (there are other, equivalent, definitions which are probably more well-known). In Section 3 we describe the algorithms used in our computations relating to amenability. In Section 4 we present the results of our computer experiments, with the aim of obtaining evidence for or against the amenability of F. In Section 5, we describe two computational approaches to estimate the exponential growth rate of Fwith respect to the standard two-generator generating set, and in Section 6, we describe the results of some computations to measure the average distance from the origin of increasingly-long random walks, known as the rate of escape. 2. Background on Thompson’s group Fand amenability Richard J. Thompson’s group Fis usually defined as the group of piecewise-linear orientation-preserving homeomorphisms of the unit interval, where each homeomorphism has finitely many changes of slope (“breakpoints”) which all are dyadic integers and and whose slopes, when defined, are powers of 2. Fadmits an infinite presentation given by hx1, x2, x3, . . . |xjxi=xixj+1 if i < ji which is convenient for its symmetry and simplicity, while there is a finite presentation given by x0, x1|[x0x−1 1, x−1 0x1x0],[x0x−1 1, x−2 0x1x2 0]®. Brin and Squier [1] showed that Fhas no free non-abelian subgroups, and thus the question of the amenability of Fis potentially connected to the conjecture of Von Neumann that a group is amenable if and only if it had no free non-abelian subgroups. The conjecture has since been solved negatively, but the problem of the amenability of Fis of independent interest and it has been open for at least 25 years. The usefulness of the infinite presentation is the fact that Fadmits a normal form based on the infinite set of generators. The relators of the COMPUTATIONAL EXPLORATIONS IN THOMPSON’S GROUP F3 infinite presentation can be used to reorder generators of a given word into an expression of the following form: xr1 i1xr2 i2. . . xrn inx−sm jm. . . x−s2 j2x−s1 j1 with i1< i2< . . . < inj1< j2< . . . < jm. This normal form is unique if one requires the following extra condition: if the generators xiand x−1 iboth appear, then either xi+1 or x−1 i+1 must appear as well. Indeed, if neither xi+1 nor x−1 i+1 appeared, then the relator could be applied so as to obtain a shorter word representing the same element. The uniqueness of this normal form can be used to solve the word problem in short time: given a word in the infinite set of generators, find the normal form, which can be done in quadratic time, and the element is the identity if and only if the normal form is empty. This unique normal form is most helpful when the task at hand is to decide whether two words represent the same element of F. If one wishes simply to test whether a given word represents the trivial element of F, it is enough to reorder the generators, but without checking the extra condition for uniqueness. For an introduction to Fand proofs of its basic properties see Cannon, Floyd and Parry [3]. Also, for an excellent introduction to amenability, the interested reader can consult Wagon [18], Chapters 10 to 12. There are several equivalent definitions of amenability, especially for finitely generated groups. The standard definition is given by the existence of a finitely-additive left-invariant probability measure on the set of subsets of G. If the group is finitely generated, a celebrated characterization due to Følner [8] in terms of the existence of sets with small boundary, has given a special interest to this concept from the point of view of geometric group theory, making it easier to see that amenability is a quasi-isometry invariant. The numerical criterion we will use extensively in this paper is due to Kesten [15, 16] and it uses the concept of cogrowth. Definition 2.1. Let Gbe a finitely generated group and let 1→K→Fm→G→1 be a presentation for G. The cogrowth of Gis the growth of the subgroup Kinside Fm. In particular, the cogrowth function of Gis g(n) = #(B(n)∩K), where B(n)is the ball of radius nin Fm,and the cogrowth rate of Gis γ= lim n→∞ g(n)1/n. 4 JOS´ E BURILLO, SEAN CLEARY, AND BERT WIEST Kesten’s cogrowth criterion for amenability states basically that a group is amenable when it has a large proportion of freely reduced words, for every length n, representing the trivial element; that is, when the cogrowth is large. Theorem 2.2 (Kesten).Let Gbe a finitely generated group, and let Xbe a finite set of generators, with cardinal m. Let γbe its cogrowth rate. Then Gis amenable if and only if γ= 2m−1. This can also be interpreted in terms of random walks. If the group is nonamenable (that is, if there are very few nontrivial words representing the trivial element of the group), then the probability of a random walk in the group ending at 1 is small. Since our random walks are taken to be non-reduced, we consider the (2m)Lnon-reduced words of length Lin mgenerators, and let T(L) be the set of these words which represent the identity in the group G. Then, define p(L) = #T(L) (2m)L, that is, we define p(L) to be the proportion of words which are equal to the identity in G. Then, a rewriting of Kesten’s criterion for non-reduced words can be given by Theorem 2.3 (Kesten).A group is amenable if and only if lim sup L→∞ p(L)1/L = 1 Roughly speaking, a group is amenable if the probability of a random walk of length Lreturning to 1 decreases more slowly than exponentially with L. This form of the criterion will be used in the subsequent sections to try to study numerically the amenability of F. 3. Algorithms and programs The direct approach at finding the numbers p(L) exactly for Thompson’s group Ffails even at quite small values of Ldue to the fact that the number of words grows exponentially, so the computation times get large easily. For instance, for a length as small as 14 the number of total words is 414=268,435,456, out of which there are 1,988,452 representing the neutral element, for a value p(14)1/14 = 0.704423677. It would be hard to decide whether the sequence approaches 1. A number of improvements can be made to ease the calculation so it becomes more feasible to estimate whether the sequence tends to 1. First, we take samples of words of a given length instead of the all words of a given length. The number 4Lgrows impracticably large even for small COMPUTATIONAL EXPLORATIONS IN THOMPSON’S GROUP F5 values of L, so sampling becomes a necessity. Since the number p(L) is basically a proportion (or a probability), it can be approximated by Monte Carlo methods. One can always take a random non-reduced word in the two generators x0and x1and check if it is the identity by solving the word problem quickly using the normal form. Repeating this process one can find a reasonably good approximation of the number p(L). A further improvement can be implemented by taking only balanced words. We observe that, since the two relators in Gare commutators, a word which represents the identity has to be balanced: it has to have total exponent zero in both generators x0and x1. So we consider not all random words, but only balanced ones. We remark that the abelianization of F is Z2, generated by x0and x1, so being balanced is in fact equivalent to representing the trivial element of Z2=Fab. Now we let C(L) be the set of balanced words among the 4Lnon-reduced words of length Lin F2, and define bp(L) = #T(L) #C(L), the proportion of words representing the identity of Famong balanced words of length L. We have L pp(L) = L r#T(L) 4L=L s#T(L) #C(L)·L r#C(L) 4L =L pbp(L)·L r#C(L) 4L. Moreover, the last factor L q#C(L) 4Ltends to 1 as Ltends to infinity, because Z2is amenable. Thus Fis amenable if and only if we have lim supL→∞ bp(L)1/L = 1. So in order to decide whether Fis amenable, we shall try to find good approximations of bp(L), the proportion of words representing 1Famong balanced words of length L, and this for values of Lwhich are as large as possible. Obviously, the algorithm for creating random balanced words must be designed in such a way that all balanced words of length Lhave the same chance of appearing. The practical advantage of approximating bp(L) rather than p(L) is that bp(L) is much larger (roughly by a factor πL/2), so much smaller sample sizes are required. Yet another improvement, which substantially increases the efficiency of the algorithm, can be made by using a “divide and conquer” strategy. The underlying observation is that if Lis even, then the probability that a random word of length Lrepresents the trivial element of Fis equal to the 6 JOS´ E BURILLO, SEAN CLEARY, AND BERT WIEST probability that two random words of length L/2 represent the same element. Thus, the idea of the algorithm is to create a large number Nof random words of length L/2 (in our implementations, values for Nbetween 15,000 and 200,000 were generally used). Each of the Nwords is immediately brought into normal form, and these normal forms are stored. In order to decide if two words represent the same element of F, we simply compare their normal forms. Therefore we can consider all N(N−1)/2 unordered pairs of words in normal form, and we count how many identical pairs we see. This number, divided by N(N−1)/2, is an approximation for the proportion p(L). However, the description just provided is an oversimplification, because as described above, we would like to restrict our sample to balanced words. Here we describe the estimation algorithm more precisely: Each iteration of the algorithm has the following steps. In a preliminary step, we create one random balanced word of length L. Then we focus our attention on the first half (the first L/2 letters) of this word and we count which element in the quotient Fab =Z2this first half represents —that is, we count the exponent sums of the letters x0and x1for the first half of the word. In the second step, we create Nrandom words of length L/2 which all represent this same element of the abelianization Fab =Z2, in such a way that all possible words of length L/2 with the given x0-balance and x1- balance have the same chance of appearing. As soon as it is created, each random word is transformed into normal form, and this normal form is stored. In the third step, we count the proportion of identical pairs among all N(N−1)/2 unordered pairs of stored words in normal form. In this way, each iteration of the algorithm gives an approximation to the true value of bp(L). Performing a few thousand iterations, and taking the mean of the proportions obtained in each step, one obtains an approximation to bp(L). The expected value for the result of this algorithm is indeed bp(L), which we interpret as the probability that two random words of length L/2 represent the same element of F, under the condition that they represent the same element of Fab =Z2. It is immediate from the construction of the algorithm that for any pair (k, l)∈Z2, the proportion of words representing (k, l) in Fab among all words constructed by the algorithm is what it should be —namely the probability that the first half of a balanced random word of length Lrepresents (k, l) in Fab =Z2. Then, having fixed some pair (k, l) in Z2, we restrict our attention to those iterations of the algorithm that deal with words with x0-balance k and x1-balance l(and length L/2). We have to prove that the expected COMPUTATIONAL EXPLORATIONS IN THOMPSON’S GROUP F7 value for the proportion of identical pairs of words in our algorithm is what it should be – namely the probability that a pair of random words, chosen with uniform probability from the set pairs of words of length L/2 representing the element (k, l) of Fab =Z2, represent the same element of F. That is, we have to prove that our taking words in batches of Nand comparing all couples in that batch, rather than taking independent samples of pairs of words, does not distort the result. That, however, follows immediately from the fact that in our algorithm, all pairs of words of length L/2 with x0-balance kand x1-balance l, appear on average with the same frequency (they have uniform probability). The fact that our N(N−1)/2 samples are not independent has no impact on the expected value. It does have an impact on the variation, that is, on the size of the error bars, but even this negative impact becomes negligible when we have, on average, less than one identical pair per batch of Nwords, as we typically have. The authors have implemented the last two algorithms in computer programs written in FORTRAN and C. These programs were run for several weeks on the “Wildebeest” 132-processor Beowulf cluster at the City University of New York. The results of these implementations will be shown in the next section. 4. Computational results concerning amenability The results for the computations of trivial words for Fare represented in Table 1. This table contains the following information. For lengths L= 20,40, . . . , 300,320, it gives in the second and third columns the sample size (the number of words that were tested) and the number of words among them that were found to represent the trivial element of F; thus the quotient of these two quantities is an approximation of bp(L). The fourth column contains the Lth root of this proportion. The last column contains the 20th root of the quotient of the proportions obtained for length Land for length L−20. In order to clarify the last two columns we remark that the sequences L pbp(L) and 20 pbp(L)/bp(L−20) have the same limits – for instance if we had bp(L)≃const ·aLthen we would obtain lim L→∞ L pbp(L) = lim L→∞ 20 pbp(L)/bp(L−20) = a The difference between the two sequences is that the second one converges much more quickly, but it is also more sensitive to statistical errors related to insufficient sample size. In summary, the question of amenability comes down to the question whether the numbers in the last two columns converge to 1, or to a smaller 8 JOS´ E BURILLO, SEAN CLEARY, AND BERT WIEST length Lsample size trivial L pbp(L)20 qbp(L) bp(L−20) 20 2.000 ·1071 364 638 0.8744 40 2.000 ·10782 922 0.8718 0.8693 60 2.000 ·1076 341 0.8744 0.8794 80 2.500 ·1011 7 255 725 0.8776 0.8873 100 3.125 ·1011 938 587 0.8806 0.8928 120 8.750 ·1012 2 961 321 0.8832 0.8966 140 1.312 ·1013 551 480 0.8857 0.9009 160 1.238 ·1013 67 542 0.8879 0.9030 180 2.420 ·1013 18 618 0.8900 0.9067 200 1.425 ·1014 16 040 0.8918 0.9084 220 1.572 ·1015 26 596 0.8934 0.9096 240 2.063 ·1016 55 941 0.8950 0.9125 260 2.716 ·1016 12 162 0.8964 0.9139 280 7.566 ·1015 599 0.8976 0.9139 300 1.343 ·1016 196 0.8993 0.9221 320 5.856 ·1016 148 0.9003 0.9161 Table 1. Cogrowth estimates for F. number. The numbers in the second to last column converge more slowly, but they are more reliable. Before we can establish any conclusions, it would be interesting to compare these results with the corresponding results for groups which are known to be amenable or not. As test groups we will take the free group on two generators as a nonamenable example, and the group ZoZ(Zwreath Z). The latter group is amenable since it is abelian-by-cyclic, and it appears as a subgroup of Fin multiple ways [14, 4]. The group ZoZadmits the presentation Da, t |hati, atji, i, j ∈ZE, and being two-generated it appears to be a good match to compare with F. The results for these two groups are in Table 2. A graphical representation of comparing these estimates of cogrowth in the three groups F,ZoZand F(2) is given in Figures 1. Do these pictures suggest that Fis amenable or non-amenable? It is difficult to discern convergence to 1 or something less than 1 with this data, and it is clear by considering other amenable groups such as iterated wreath products like ZoZoZthat the convergence to 1 could be exceptionally slow. COMPUTATIONAL EXPLORATIONS IN THOMPSON’S GROUP F9 ZoZF2 Lsample trivial L pbp(L) sample trivial L pbp(L) 20 2.475 ·1071 802 935 0.8772 1.000 ·107655 940 0.8727 40 2.475 ·107247 710 0.8913 1.000 ·10730 685 0.8653 60 1.980 ·10734 658 0.8996 2.000 ·1072 888 0.8630 80 2.475 ·1079 669 0.9066 3.000 ·107230 0.8631 100 1.980 ·1072 079 0.9125 4.000 ·108159 0.8630 120 1.095 ·1083 485 0.9173 6.975 ·1011 14 167 0.8628 140 9.950 ·1071 035 0.9213 8.000 ·1011 819 0.8626 160 4.990 ·1081 847 0.9248 2.400 ·1012 136 0.8629 180 2.997 ·1094 141 0.9278 200 4.740 ·1010 26 919 0.9306 220 8.636 ·1010 20 625 0.9330 240 1.859 ·1011 19 469 0.9352 260 4.249 ·1011 20 112 0.9372 280 5.734 ·1011 12 735 0.9390 300 5.844 ·1011 6 256 0.9407 320 4.050 ·1012 21 229 0.9422 Table 2. Cogrowth estimates for ZoZand the free group of rank 2. 5. Computational results concerning the growth of F Another family of open questions about Thompson’s group Fcenter on the growth of Fwith respect to its standard generating set {x0, x1}. To study the growth of a group with respect to a generating set, we consider gn, the number of distinct elements of Fof length nand we form the spherical growth series, g(x) = Pgnxn. If we consider balls of radius n and the number of elements bnwhose length is less than or equal to n, we have the growth series b(x) = Pbnxn. Thompson’s group has exponential growth as the submonoid generated by x0, x1and x−1 1is free (see Cannon, Floyd and Parry [3]). Burillo [2] computed the exact growth function for positive words in Fwith respect to the standard two generator generating set {x0, x1}which gives a lower bound for the growth rate of words in the full group as the largest root of x3−2x2−x+ 1, which is about 2.24698. Guba [12] used the normal forms for elements of Fdeveloped by Guba and Sapir [13] to sharpen the lower bound of the growth function to 1 2(3 + √5) which is about 2.61803. Guba conjectures that 2.7956043 is an upper bound by considering the ratio of the ninth and eighth terms in the spherical growth series of F. But the exact growth function of Fremains unknown – it is 16 JOS´ E BURILLO, SEAN CLEARY, AND BERT WIEST [12] V. S. Guba. On the properties of the Cayley graph of Richard Thompson’s group F.Internat. J. Algebra Comput., 14(5-6):677–702, 2004. International Conference on Semigroups and Groups in honor of the 65th birthday of Prof. John Rhodes. [13] V. S. Guba and M. V. Sapir. The Dehn function and a regular set of normal forms for R. Thompson’s group F.J. Austral. Math. Soc. Ser. A, 62(3):315–328, 1997. [14] Victor Guba and Mark Sapir. Diagram groups. Mem. Amer. Math. Soc., 130(620):viii+117, 1997. [15] Harry Kesten. Full Banach mean values on countable groups. Math. Scand., 7:146– 156, 1959. [16] Harry Kesten. Symmetric random walks on groups. Trans. Amer. Math. Soc., 92:336–354, 1959. [17] Alexander Yu. Ol0shanskii and Mark V. Sapir. Non-amenable finitely presented torsion-by-cyclic groups. Publ. Math. Inst. Hautes ´ Etudes Sci., (96):43–169 (2003), 2002. [18] Stan Wagon. The Banach-Tarski paradox, volume 24 of Encyclopedia of Mathematics and its Applications. Cambridge University Press, Cambridge, 1985. With a foreword by Jan Mycielski. Escola Polit` ecnica Superior de Castelldefels, UPC, Avda del Canal Ol´ ımpic s/n, 08860 Castelldefels, Barcelona, Spain E-mail address:[email protected] Department of Mathematics R8133, The City College of New York, Convent Ave & 138th, New York, NY 10031, USA E-mail address:[email protected] IRMAR (UMR 6625 du CNRS), Universit´ e de Rennes 1, Campus de Beaulieu, 35042 Rennes Cedex, France E-mail address:[email protected]