The Grigorchuk group and groups of intermediate growth

Title: The Grigorchuk group and groups of intermediate growth Author: Aitor Pérez Pérez Advisor: José Burillo Puig Department: Departament de Matemàtica Aplicada IV Academic year: 2014-2015 Master of Science in Advanced Mathematics and Mathematical Engineering Abstract In this work we make an introduction of growth in groups, giving the definition, some properties and examples. We present the Grigorchuk group Gas a subgroup of automorphisms of the infinite binary tree, and prove that it has intermediate growth, becoming a counterexample both for Milnor’s conjecture [8] and for the Burnside problem on periodic groups. Finally, we propose some generalizations to this group and analyze their similarities and differences with the group Gitself, exploring the order of some elements and making some conjectures about their growth. Mathematical Subject Classification: 20F65, 20F50, 20F69, 20E08. Keywords: groups of intermediate growth, Grigorchuk group, automorphisms of the infinite binary tree. Contents 1 Growth 9 1.1 Basicdefinitions.......................... 9 1.2 Equivalence of growth functions . . . . . . . . . . . . . . . . . 11 1.3 Finite index subgroups . . . . . . . . . . . . . . . . . . . . . . 13 1.4 Growthrates ........................... 15 2 Grigorchuk’s first group: G19 2.1 Automorphisms of the tree . . . . . . . . . . . . . . . . . . . . 19 2.2 Generators of G.......................... 23 2.3 Basic properties of G....................... 24 3 Intermediate growth of G29 3.1 Technicallemmas......................... 29 3.2 Superpolynomial growth of G.................. 33 3.3 Rewritingrules .......................... 35 3.4 Subexponential growth of G................... 37 4 Similar constructions 43 4.1 The group G2........................... 43 4.2 Generalizations .......................... 48 5 Introduction Growth in groups has been a studied topic since the 1960s, motivated by the fact that the volume growth of the universal covering of a Riemannian manifold is equal to the growth of its fundamental group. This was presented by Milnor [8], who also stated that soluble groups had either polynomial or exponential growth. Since at that time no groups of intermediate growth were known, this fact motivated Milnor to state the conjecture that not only soluble groups had polynomial or exponential growth but all groups. This conjecture remained open some years, until 1980, year in which R. I. Grigorchuk [3] found a group of intermediate growth, not polynomial nor exponential. This group was an adequately chosen subgroup of the group of automorphisms of the infinite binary tree, with several good properties which allowed to prove both the superpolynomial and the subexponential growth. Moreover, Grigorchuk also contributed to the Burnside problem, since the same group served as a counterexample. The Burnside problem stated the question of whether every periodic group must be finite. A periodic group is a group in which every element has finite order. Indeed, every element of the Grigorchuk group has finite order (it is a 2-group), but it is not difficult to see that it is infinite. In parallel, Gromov [4] arrived to a characterization of groups of polynomial growth as the virtually nilpotent groups. A group is virtually nilpotent if it contains a nilpotent subgroup of finite index, and a group is nilpotent if it has a finite lower central series G=G1B· · · BGn= 1, where Gi= [Gi−1, G]. This classification and Grigorchuk’s work already unveiled a lot about 7 growth in groups. From this point, several authors have studied this topic and have made important contributions: P. de la Harpe [1], R. I. Grigorchuk and I. Pak [2], A. Mann [7] or Lysenok [6]. Gupta and Sidki [5] proposed some generalizations of the Grigorchuk group as other counterexamples for the Burnside problem on periodic groups, which also served as candidates for other groups of intermediate growth. However, this still remains as an open problem. This document is structured in the following way: In the first chapter, we aim to give an introduction about growth in order to make this work as selfcontained as possible. The second chapter presents the Grigorchuk group, starting with the automorphisms of the infinite binary tree in search of its generators. The proof of its intermediate growth is detailed in the third chapter, separating the superpolynomial and the subexponential growth, which is more involved and needs the definition of the rewriting rules. Finally, in the fourth chapter we try to generalize the construction of the Grigorchuk group as a family of groups by considering other sets as generators, indexing them by a natural number n≥2, which yield some surprising facts and allow some conjectures, as for instance that such groups have intermediate growth for odd nand that they have an element of infinite order if nis even, which could imply their exponential growth. 8 1 Growth 1.1 Basic definitions Definition 1.1. Let Gbe a finitely generated group, and let S={x1, . . . , xd} be a set of generators. Let x∈G. The length of xwith respect to this set of generators, denoted `S(x) or simply `(x), is the minimum length of words in x1, . . . , xd, x−1 1, . . . , x−1 drepresenting the element x. Since the length of the empty word is zero, so is `(1), the length of the trivial element. Definition 1.2. For n≥0, we denote γ(n) = |{x∈G|`(x)≤n}| the number of elements of length at most n. As a function of n,γG,S(n), or simply γ(n), is the growth function of Gwith respect to the generating set S. Remark 1.3. This function can be regarded as the cardinality of balls centered in the trivial element and with radius n. Note that the definition of the growth function strongly depends on the generating set used to define the length. The only fact we assume is that no one of the generators equals another one or the inverse of another one, but we are not assuming, for example, that the set of generators does not contain a proper subset which also generates the same group. Remark 1.4. Gis finite if and only if γ(n) is eventually constant. Proposition 1.5. Growth functions are subadditive: γ(n+m)≤γ(n)γ(m) 9 log(γ(n)γ(m)) = log γ(n) + log γ(m), to show that the limit lim n→∞ log γ(n) n= lim n→∞ log γ(n)1/n exists, and hence also ω(G). Besides, ω(G)≥1, and, since the free group serves as an upper bound, ω(G)≤2d−1, if Ghas dgenerators. Remark 1.17. While the exact value for ω(G) depends on the chosen set of generators X, because γ(n) may be different, the fact that ω(G) = 1 or not does not. This can be seen taking two generating sets and their growth functions and using the equivalence conditions on the limits for ω(G). There are groups satisfying ω(G)>1 for every generating set but for which there exist a sequence of generating sets {Xn}nsuch that ωX1(G)> · · · > ωXn(G)>· · · , in a way that sup i ωXi(G) = 1. However, this supreme is never attained, so it does not contradict what we stated before. Definition 1.18. Let Gbe a finitely generated group, and let γ(n) be a growth function. •Ghas exponential growth if ω(G)>1, and has subexponential growth if ω(G) = 1. The number ω(G) is called the exponential growth rate of G (or of (G, X), when the set of generators is not clear from the context). •Ghas polynomial growth if there exist c, t such that γ(n)≤cntfor every n. Depending on the value of t, we say that Ghas linear growth (t= 1), quadratic growth (t= 2), etc. Obviously, groups with polynomial growth have subexponential growth. If Ghas polynomial growth, we define its degree in a natural way as deg(G) = inf{t| ∃c s(G)≤cnt}. •Ghas intermediate growth if it has neither exponential nor polynomial growth. 16 Proposition 1.19. Let Gbe a group, H≤Gand N / G, all of them finitely generated. (a) The type of growth of Gdoes not depend on the chosen set of generators X. (b) If Ghas subexponential growth, so have Hand G/N. If Ghas polynomial growth, deg(H),deg(G/N)≤deg(G). (c) If the index of His finite, then Gand Hhave equivalent growth functions. In particular, they have the same type of growth. If it is polynomial, they have the same degree. (d) If Nis finite, then Gand G/N have equivalent growth functions. In particular, they have the same type of growth. If it is polynomial, they have the same degree. (e) If Ghas polynomial growth and Hhas infinite index, then deg(H)≤ deg(G)−1. (f) If Ghas polynomial growth and Nis infinite, then deg(G/N)≤ deg(G)−1. Proof. Let G=hx1, . . . , xdiand H=hy1, . . . , yei. If we put k= max `(yi), then γH(n)≤γG(kn). Let G/N =hNx1, . . . Nxdi, so γH(n)≤γG(n) trivially. This shows (b), and (a) is a particular case when G=H. If Hhas finite index t, take a transversal of H{1 = a1, . . . , at}, and consider r= max `(ai). Now let g∈Gbe an element of length at most n. We write g=ha, with h∈Hand ain the transversal. In particular, write 17 h=y1. . . yl, relabeling the yior maybe taking their inverses. Since h=ga−1, l=`H(h)≤n+r. We can write g= (y1a−1 i1)(ai1y2a−1 i2). . . (ail−1yla−1 il), and then, if we consider the generators aiyja−1 m,`(g)≤l. Hence, γG(n)≤ rγH(l)≤rγH(n+r)≤rγH((r+ 1)n). In particular, if the growth rate is polynomial, they have the same degree. This shows (c). For (d), consider again the generators Nx1, . . . Nxdof N. Every element g∈Gof length at most nmaps to one of length at most nin the quotient G/N. Since exactly |N|elements of Gmap in each element of G/N, we have γG/N (n)≤γG(n)≤ |N|γG/N (n). This implies that, if the growth is polynomial, the degree is the same. If Hhas infinite degree, let Ha1, . . . , Hanbe ndifferent cosets of H. We can assume that `(ai)≤i, using the same construction as in Proposition 1.13. Now take h1, . . . , hk∈Hof length at most n. All elements hiajare different, otherwise the two a’s would be in the same coset, so nsH(n)≤sG(2n). If the growth is polynomial, we have deg(H)≤deg(G)−1, which proves (e). Finally, if Nis infinite, we choose a set of generators for Gcontaining a subset of generators of N. Then, there are more elements in Gof length 2nthan those of the form xa, with x∈Nand aa representative of any ncosets. This means that γG(2n)≥nγG/N (n), and so if the growth is polynomial, deg(G/H)≤deg(G)−1. 18 2 Grigorchuk’s first group: G 2.1 Automorphisms of the tree Definition 2.1. Let Tbe an infinite rooted binary tree. Given a node v∈T, we will denote its left and right children as v0and v1, respectively. In general, we can define recursively the n-children of vto be the (n−1)- children of v0and v1, being v0and v1its 1-children. The level of vis the distance of vto the root. Notice that, since Tis infinite, if we denote as Tvthe subtree rooted at v,Tis isomorphic to Tv. v v0v1 Figure 3: Rooted infinite binary tree T. Definition 2.2. Aut(T) is the group of automorphisms of T. Precisely, Aut(T) = {τ:T−→ T| {τ(v0), τ(v1)}={τ(v)0, τ(v)1},∀v∈T}. This condition means that an automorphism of Tmaps edges to edges. This implies, for instance, that the root is always mapped to itself and more generally that each vertex is mapped to a vertex in the same level. Now we are interested in defining some particular elements of Aut(T), which will be used later as generators of the Grigorchuk’s group. 19 Definition 2.3. Let a∈Aut(G) be the automorphism of Tthat exchanges the two subtrees T0=Tr0and T1=Tr1rooted at the two children of the root vertex. Formally, if ris the root of T,amaps rto itself, r0to r1,r1to r0, and the subtrees below r0and r1are exchanged. More generally, amaps a vertex r0ε1...εnto r1ε1...εnand viceversa. r r0r1 T0T1 r r1r0 T1T0 a Figure 4: a∈Aut(T) exchanges the subtrees T0and T1. Notice that ais an involution: a2=id. Moreover, we can extend this definition to the rest of vertices. For any vertex v,avis the automorphism fixing every v0/∈Tvand defined as ain Tv via the isomorphism T∼ =Tv. In this setting, a=ar. To define the rest of generators, let us introduce the following map, which will help to better understand the structure of Aut(T). Let i0:T−→ T0and i1:T−→ T1be the isomorphisms between T0,T1 and T. Now we define the map ϕas follows: ϕ: Aut(T)×Aut(T)−→ Aut(T) (τ0, τ1)7−→ i0(τ0)·i1(τ1) If we define Aut(Tε) to be the subgroup of Aut(T) fixing every vertex outside Tε, then iε(τε)∈Aut(Tε), so the order of the factors in this definition is irrelevant, because they commute. 20 Nevertheless, this map ϕis not surjective. For instance, ais not in the image. Indeed, automorphisms mapping r0to r1and viceversa do not belong to Im ϕ. In order to extend this map to an isomorphism, we have to consider the following definition. Definition 2.4. The wreath product of a group Gwith Z2is GoZ2=G× Go Z2, where the semidirect product exchanges the order of both copies of G. In particular, if g1, g2∈G, and Z2={1, t}, t(g1, g2)t= (g2, g1). We will use this definition with the group Aut(T). If we consider Z2= {1, t}in the wreath product, we can define the following extension for ϕ: ϕ: Aut(T)×Aut(T)o Z2−→ Aut(T) (τ0, τ1)7−→ i0(τ0)·i1(τ1) t7−→ a For 1 ∈Z2,ϕis exactly the same map as before. However, for t∈Z2, we get the automorphism exchanging the two vertices r0and r1, and behaving as τ1in T0and as τ0in T1. r r0r1 τ0τ1 φ (τ0, τ1) Figure 5: If tis not involved, ϕ(τ0, τ1) is the automorphism constructed as τ0in the first subtree and τ1in the second. 21 r r1r0 τ1τ0 φ t(τ0, τ1) Figure 6: If tis present, we have to apply aafter the previous construction and switch the subtrees. Extending ϕto Aut(T)oZ2converts it to an isomorphism between Aut(T)oZ2and Aut(T), because every automorphism can be decomposed into how does it map the left subtree, the right subtree and whether it exchanges the two children of the root. From now on, we will refer to this isomorphism as ϕand to its inverse as ψ: Aut(T)−→ Aut(T)×Aut(T)o Z2, which maps an automorphism to its left and right children, and to 1 or tif it exchanges r0and r1, respectively. 22 2.2 Generators of G As we have mentioned, one of the generators of Gis a. Now we are in a good situation to define the remaining generators. Definition 2.5. Let b,cand dbe the elements of Aut(T) complementarily defined as b=ϕ(a, c), c=ϕ(a, d) and d=ϕ(id, b). Although this definition may not be very intuitive, it uniquely defines these three elements. Pictorially, these elements are the following: a a a a a a b a a a a a c a a a a a d Figure 7: b,cand dare defined applying ato each left child, but skipping one every three. Definition 2.6. The Grigorchuk group is G=ha, b, c, di ⊂ Aut(T). 23 2.3 Basic properties of G With the generators defined, we want to present some of the properties of the group G, as for example the order of some special elements, the definition of one important subgroup and a normal form for elements of G. Remark 2.7. The first we can notice about the generators of Gis that not only ais an involution, but every one of them is. Hence, a2= 1 b2= 1 c2= 1 d2= 1. Another relation we can easily see through the pictures is the following: bcd = 1. This means that we can express any of the generators b,cand din terms of the other two: b=dc,c=bd and d=cb. This proves that, actually, we do not need to have the four generators define G, since G=ha, b, ci= ha, b, di=ha, c, di. However, in order to keep everything symmetric, we prefer to consider all four of them as a generating set for G. Finally, other relations one may want to check are that b,cand dcommute pairwise: bc =cb bd =db cd =dc and that the orders of the elements ab,ac and ad are the following: (ab)16 = (ac)8= (ad)4= 1. They imply that the subgroups ha, bi,ha, ciand ha, diof Gare finite. 24 Remark 2.8. Every element of Gcan be written as a word w= (a)∗a∗ · · · ∗ a∗(a), where ∗∈{b, c, d}and the first and the last amay or may not appear. Since the generators have order 2, their inverses are themselves, and if we consider an arbitrary word in a, b, c, d representing an element, we can collapse any two consonants into the third one. Iterating this process, we eventually modify the word to this form, without altering the element it represents. Definition 2.9. There is a very important subgroup of G. The fundamental subgroup of G, denoted H, is the subgroup of automorphisms leaving fixed the first layer of the tree: H={τ∈G|τ(v) = v∀vsuch that |v|= 1}. As a first check, we may notice that a6∈ H, while b, c, d ∈H. Proposition 2.10. 1. [G:H]=2. 2. HCG. 3. H=hb, c, d, ba, ca, dai. Proof. Let g∈Gand let w= (a)∗a∗ · · · ∗ a∗(a) be a reduced word representing g. If we focus on the two vertices on the first layer of T, they are fixed by b, c, d but exchanged by a. Hence, g∈Hif and only if whas an even number of occurrences of a(|w|aeven). This shows that [G:H] = 2, and, since subgroups of index 2 are always normal, we also have the second statement. Finally, since |w|ais even, we can arrange weither as 25 = (ln C+kln α+kln n) + Anν(1 −ε)≤Anν, for an adequate choice of A, satisfying both this condition and the base of the induction. 32 3.2 Superpolynomial growth of G Definition 3.3. Two groups G1and G2are commensurable (G1≈G2) if they contain isomorphic subgroups of finite index (i.e. ∃H1⊆G1, H2⊆G2 such that H1∼ =H2and [G1:H1],[G2:H2]<∞). Remark 3.4. Recall that finite-index subgroups have the same growth as the group itself. This means that γG∼γH. If G1≈G2, then we have that γG1∼γH1∼γH2∼γG2, and so commensurable groups have equivalent growth functions. To prove the superpolynomial growth of G, we will see that G≈G×G. Definition 3.5. Let Bbe the normal subgroup of Ggenerated by b: B=hg−1bg |g∈Gi Proposition 3.6. [G:B]≤8. Proof. Notice that a2=d2= (ad)4= 1. The first two imply that reduced words in aand dare (a)dad . . . ad(a), and the third implies that since adad = dada, in fact there are 8 such words. Indeed, ha, di∼ =D4, the dihedral group of 8 elements. But G=ha, b, di, and since b∈B,G/Bis a quotient of ha, di. In particular, [G:B]≤8. Proposition 3.7. B×B⊆˜ H⊆G×G. Proof. ˜ H=ψ(H), so, since d, da∈H,hψ(d), ψ(da)i=h(1, b),(b, 1)i ⊆ ˜ H. Let h∈Hsuch that ψ(h) = (h0, h1). ψ(dh) = ψ(h−1dh) = ψ(h)−1ψ(d)ψ(h) = (h−1 0, h−1 1)(1, b)(h0, h1) = (1, bh1). 33 Now since both projections pr1:˜ H−→ Gand pr2:˜ H−→ Gare epimorphisms, we can choose h1to be any element of G. This means that ˜ H contains all elements of the form (1, bg), ∀g∈G, and these elements generate h(1, bg)|g∈Gi= 1 ×B⊆˜ H. Similarly, writing dainstead of dwe get B×1⊆˜ H, and these two subgroups generate another subgroup h(bg1,1),(1, bg2)|g1, g2∈Gi=h(bg1, bg2)| g1, g2∈Gi∼ =B×B⊆˜ H. Proposition 3.8. [G×G:˜ H]≤64. Proof. Using the previous proposition, we have that [G×G:˜ H]≤[G×G: B×B]. Now, if ϕ:G−→ G/Bis the natural quotient epimorphism, we can consider the homomorphism (ϕ, ϕ) : G×G−→ G/B×G/B, which is also an epimorphism, and its kernel is B×B. This defines an isomorphism (G×G)/(B×B)∼ =G/B×G/B, and so [G×G:B×B]=[G:B]2≤82= 64. This proves the proposition. Proposition 3.9. G≈G×G. Proof. We consider H⊆Gand ˜ H⊆G×G. Both are normal subgroups of finite index, since the former has index 2 and the latter has index ≤64, as we have just checked. Moreover, H∼ =˜ H, via the isomorphism ψ. Theorem 3.10. Ghas superpolynomial growth. In particular, there exists some ν > 0such that γG<enν. Proof. Now that we have that G≈G×G, we can simply use the lower bound lemma to prove the result. 34 3.3 Rewriting rules It will be useful to have an explicit way of writing the image by ψof any element of G. The rewriting rules we will introduce now will fulfill this purpose. Definition 3.11. We define the rewriting rules as the following rules acting on words representing elements of Gby substituting each letter by its corresponding letter or the empty word 1: Φ0:         a→1, b→a, c →a, d →1,if π(∗) odd, b→c, c →d, d →b, if π(∗) even. Φ1:         a→1, b→a, c →a, d →1,if π(∗) even, b→c, c →d, d →b, if π(∗) odd. We denote by π(∗) the number of apreceding ∗in the word. Thus, for instance, if we take w=abacadad, then Φ0(w) = adb and Φ1(w) = cab. Notice that these words may not be reduced, but they still represent elements of G. In this example, Φ0(w) is not reduced but represents the same element as ac and Φ1(w) is already a reduced word. Proposition 3.12. Let g∈G, and let ψ(g) = s(g0, g1)∈G×GoZ2, with s∈ {0, t}=Z2. Let w= (a)∗a∗ · · · ∗ a∗(a)be a reduced word representing g, as in Remark 2.8, and let g0 0and g0 1be the elements of Grepresented, respectively, by Φ0(w)and Φ1(w). Then, g0=g0 0and g1=g0 1. Proof. We proceed by induction on the length of g. The base case is trivial as shown in Theorem 2.12, and for the general case we only have to decompose 35 winto products of ∗and a∗a=∗a. Then, (g0, g1) equals the product of the images by ψof such syllables, which by induction hypothesis are represented by the rewriting rules. Remark 3.13. This decomposition can be used to prove that `(g0)+`(g1)≤ `(g) + 1, which is not enough to see the subexponential growth but still is useful. 36 3.4 Subexponential growth of G Definition 3.14. The n-th level stabilizer of Gis H(n)= StG(n) = {τ∈G|τ(v) = v∀v∈T:|v| ≤ n}, the subgroup of elements in Gleaving fixed the first nlevels of the tree. Proposition 3.15. [G:H(n)]≤22n−1. Proof. Let v∈T. Let εv: Aut(T)−→ {0,1}be a map defined as εv(τ) =      0 if τ(v0) = τ(v)0,τ(v1) = τ(v)1 1 if τ(v0) = τ(v)1,τ(v1) = τ(v)0. In other words, at each vertex v∈T,τmaps its children v0, v1to the children of τ(v). So, for each vertex, τhas two possibilities: either τmaps the left child to the left child and the right child to the right child, and so εv(τ) = 0, or it exchanges them, and so εv(τ) = 1. Notice that an automorphism τ∈Aut(T) is uniquely determined by εv(τ), ∀v∈T. Now let us consider the following subgroup of Aut(T): Am={τ∈Aut(T)|εv(τ) = 0 ∀v∈T:|v| ≥ m}. Elements in Ammay only exchange vertices in the first mlevels. For instance, A1={1, a}and A2has 8 elements, since we can only choose the value for εv(τ) in three vertices, the root and its children. More generally, since elements in Amhave freedom in the first mlevels of the tree, which means 2m−1 vertices, and for each vertex we may choose εv(τ) = 0,1, Amhas 22m−1elements. 37 Finally, consider the quotient Aut(T)/H(n). Every element in Aut(T) can be decomposed as the product of an element in Anand an element in H(n). In the quotient, this decomposition means that the number of equivalence classes is |An|. Now, [G:H(n)]≤[Aut(T) : H(n)] = |An|= 22n−1. At this point, we are interested in finding some upper bound condition on the length of elements in Gin order to check its subexponential growth. If we denote ψ3=ψH(3) , we have a map χ:H(3) −→ G8 h7−→ (g000, g001, . . . , g111) where gijk denote 3-children of h, which all belong to G. A straightforward application of the rewriting rules yields that `(g000)+`(g001)+· · ·+`(g111)≤ `(h)+7, but unfortunately, this condition is not enough to assure the subexponential growth. To this purpose we introduce the following lemma. Lemma 3.16. Let h∈H(3) and g000, g001, . . . , g111 as above. Then, `(g000) + `(g001) + · · · +`(g111)≤5 6`(h)+8. Proof. Let w= (a)∗a∗· · ·∗a∗(a) be a reduced decomposition of h. Applying the rewriting rules, we get two words w0, w1, representing elements g0, g1. If we do it again with these two words, we get four words w00, w01, w10, w11, representing the elements g00, g01, g10, g11. Finally, another iteration gives eight words w000, w001, . . . , w111, and again we call the elements they represent g000, g001, . . . , g111. Notice that the resulting words may not be reduced, but in any case we have `(gi)≤ |wi|,`(gij)≤ |wij|and `(gijk)≤ |wijk|. Moreover, the rewriting rules provide the following inequalities: `(g0) + `(g1)≤`(h)+1 38 `(g00) + · · · +`(g11)≤`(g0) + `(g1)+2 `(g000) + · · · +`(g111)≤`(g00) + · · · +`(g11)+4. Now, to simplify notation, let us define the words w0=w0w1,w00 = w00 . . . w11,w000 =w000 . . . w111 by concatenation. By the construction of the rewriting rules, every ain wgets cancelled both in w0and w1, and every din wgets cancelled either in w0or in w1, and not in both. So |w0| ≤ |w|+ 1 − |w|d. This inequality cannot be iterated because w0and w1may not be reduced, but similarly, every cin wproduces adin w0, which is cancelled in w00, and every bin wproduces a cin w0, which produces a din w00, which is cancelled in w000. Hence we have the following inequalities: |w0|≤|w|+ 1 − |w|d |w00| ≤ |w|+ 3 − |w|c |w000| ≤ |w|+ 7 − |w|b. Since |w|b+|w|c+|w|d≥|w|−1 2, at least one letter satisfies |w|∗>|w| 6−1. Recovering all the inequalities above, we have `(g000) + · · · +`(g111)≤min{|w0|+ 2 + 4,|w00|+ 4,|w000|} ≤ ≤min{|w|+ 1 − |w|d+ 2 + 4,|w|+ 3 − |w|c+ 4,|w|+ 7 − |w|b}= = min{|w|+ 7 − |w|d,|w|+ 7 − |w|c,|w|+ 7 − |w|b}= =|w|+7−max{|w|b,|w|c,|w|d}≤|w|+7−(|w| 6−1) = 5 6|w|+8 = 5 6`(h)+8. 39 Proposition 3.17. Ghas subexponential growth. In particular, there exists some ν < 1such that γG(n)4enν. Proof. Let g∈G. It can be written as g=uh, with h∈H(3) and ua coset representative of G/H(3). Since [G:H(3)]≤128, there are at most 127 such representatives u, and moreover we can choose them to satisfy `(u)≤127. This is so because we start with the neutral element 1, which is a representative for H(3), and multiply it by a,b,cor d. This gives, at least, one representative for a coset different from H(3), and it has length 1. Iterating this construction, at each step iwe have a number of cosets for which we have a representative with length not greater than i, and multiplying all these representatives by all the generators yield necessarily at least one representative of a coset for which we did not have one yet. Hence, we can assume `(u)≤127. Writing h=u−1ggives `(h)≤`(u−1) + `(g)≤`(g) + 127, but we can decompose has the product of its 3-children, which commute since h∈H(3). This gives h=g000g001 . . . g111. In this situation, Lemma 3.16 states that `(g000)+`(g001)+· · ·+`(g111)≤5 6`(h)+8 ≤5 6(`(g)+127)+8 <5 6`(g)+114. Now we want to count how many elements gof length ≤ncan be constructed. Since g=uh,γ(n)≤128k, where kis the number of different h we can construct. Notice that h=g000g001 . . . g111, so the number of different such hequals the number of different such gijk. In this decomposition, we had the restriction `(g000) + · · · +`(g111)≤5 6`(g) + 114 = 5 6n+ 114. Hence, γ(n)≤128 X (n1,...,n8) γ(n1). . . γ(n8),with X i ni≤5 6n+ 114. 40 To eliminate the constant term, let us define m= 137 + n, so that 5 6n+ 114 <5 6m, and rewrite γ(m) = γ(137 + n)≤4137γ(n)≤4137128 X (n1,...,n8) γ(n1). . . γ(n8) = = 2281γ∗85 6n+ 114≤2281γ∗85 6m. With this inequality, the hypothesis for Lemma 3.2 are satisfied and so Ghas subexponential growth. 41 4.2 Generalizations So far we have shown that G2and Ghave some differences. Essentially, these differences come from the element resulting of the product of all generators different from a: In G,bcd = 1 but for G2bc =r, a new element which is composed by an arooted at each left branch. This new element is not in G, and ar has infinite order. If we consider the same construction modulo 4, and define b, c, d and ein a similar way, then we get again the element ras bcde, and so ar is also in G4. For G5, however, we get again bcdef = 1. This seems enough to conclude some conjectures, but before, let us define the groups formally. Definition 4.11. We define Gnas ha, a1, . . . , ani, where aiis defined as ϕ(a, ai+1) except for an=ϕ(1, a1). Remark 4.12. Under this setting, Grigorchuk’s group Gis G3, and G2 preserves its definition. Remark 4.13. If we consider the product a1. . . an, we can write the following equality: ψ(a1. . . an) = ψ(a1). . . ψ(an) = ψ(ϕ(a, a2)) . . . ψ(ϕ(a, an))ψ(ϕ(1, a1)) = = (a, a2). . . (a, an)(1, a1)=(an−1, a2. . . ana1) = (an−1, a1. . . an), where in the last step we have used that the aicommute pairwise. This is (1, a1. . . an) for odd n, which implies that a1. . . anis the identity at each left branch and so a1. . . an= 1. For even n, however, this is (a, a1. . . an), 48 which shows that the product equals the element rwe defined above, applying ato every left branch without exception. It seems that the first left branch with an identity determines the order of the element, both in the Grigorchuk group ((ab)16 = (ac)8= (ad)4= 1) and in G2((ab)8= (ac)4= 1). Hence, the element ar has infinite order, and it belongs to Gnonly for even n. Regarding the growth, it seems plausible that for every nwe have groups of superpolynomial growth, which might be proved in the same way that for G, but adapting the proof. The subexponentiality, however, seems a reasonable hypothesis for odd n, but for even nwe can find a subgroup ha1. . . an−1, aaniin Gnsatisfying (a1. . . an−1)2= 1, (aan)4= 1 but with the product aa1. . . anwith infinite order. If one can prove that this subgroup has no other relations, then it could be isomorphic to the free product Z2∗Z4, which has exponential growth, and so would have Gnwith even n. Indeed, we cannot expect the same proof of the subexponential growth of Gto be easily generalized to Gnfor even n. Recall the rewriting rules we defined, and now consider them for G2, for instance: If we have a reduced word w= (a)∗a∗ · · · ∗ a∗(a), with ∗ ∈ {b, c, r}, then they would be: Φ0:         a→1, b→a, c →1, r →a, if π(∗) odd, b→c, c →b, r →r, if π(∗) even. Φ1:         a→1, b→a, c →1, r →a, if π(∗) even, b→c, c →b, r →r, if π(∗) odd. 49 We observe that each ryields another reither by Φ0o by Φ1. This implies that words of the type w= (a)rar . . . rar(a) yield again two more words of the same type and half the length, and so the length of both words concatenated is constant, so the bound cannot be improved. 50 References [1] Pierre de la Harpe. Topics in geometric group theory. Chicago Lectures in Mathematics. University of Chicago Press, Chicago, IL, 2000. [2] Rostislav Grigorchuk and Igor Pak. Groups of intermediate growth: an introduction. Enseign. Math. (2), 54(3-4):251–272, 2008. [3] R. I. Grigorˇcuk. On Burnside’s problem on periodic groups. Funktsional. Anal. i Prilozhen., 14(1):53–54, 1980. [4] Mikhael Gromov. Groups of polynomial growth and expanding maps. Inst. Hautes ´ Etudes Sci. Publ. Math., (53):53–73, 1981. [5] Narain Gupta and Sa¨ıd Sidki. On the Burnside problem for periodic groups. Math. Z., 182(3):385–388, 1983. [6] I. G. Lys¨enok. A set of defining relations for the Grigorchuk group. Mat. Zametki, 38(4):503–516, 634, 1985. [7] Avinoam Mann. How groups grow, volume 395 of London Mathematical Society Lecture Note Series. Cambridge University Press, Cambridge, 2012. [8] John Milnor. Growth of finitely generated solvable groups. J. Differential Geometry, 2:447–449, 1968. 51