On Sushchansky p-groups

We study Sushchansky p-groups introduced in [Sus79]. We recall the original definition and translate it into the language of automata groups. The original actions of Sushchansky groups on p-ary tree are not level-transitive and we describe their orbit trees. This allows us to simplify the definit...

Ausführliche Beschreibung

Gespeichert in:

Bibliographische Detailangaben
Datum:	2007
Hauptverfasser:	Bondarenko, I.V., Savchuk, D.M.
Format:	Artikel
Sprache:	English
Veröffentlicht:	Інститут прикладної математики і механіки НАН України 2007
Schriftenreihe:	Algebra and Discrete Mathematics
Online Zugang:	http://dspace.nbuv.gov.ua/handle/123456789/157340
Tags:	Tag hinzufügen Keine Tags, Fügen Sie den ersten Tag hinzu!
Назва журналу:	Digital Library of Periodicals of National Academy of Sciences of Ukraine
Zitieren:	On Sushchansky p-groups / I.V. Bondarenko, D.M. Savchuk // Algebra and Discrete Mathematics. — 2007. — Vol. 6, № 2. — С. 22–42. — Бібліогр.: 28 назв. — англ.

Institution

Digital Library of Periodicals of National Academy of Sciences of Ukraine

id	irk-123456789-157340
record_format	dspace
spelling	irk-123456789-1573402019-06-21T01:30:23Z On Sushchansky p-groups Bondarenko, I.V. Savchuk, D.M. We study Sushchansky p-groups introduced in [Sus79]. We recall the original definition and translate it into the language of automata groups. The original actions of Sushchansky groups on p-ary tree are not level-transitive and we describe their orbit trees. This allows us to simplify the definition and prove that these groups admit faithful level-transitive actions on the same tree. Certain branch structures in their self-similar closures are established. We provide the connection with, so-called, G groups [BGS03] that shows that all Sushchansky groups have ˇ intermediate growth and allows to obtain an upper bound on their period growth functions. 2007 Article On Sushchansky p-groups / I.V. Bondarenko, D.M. Savchuk // Algebra and Discrete Mathematics. — 2007. — Vol. 6, № 2. — С. 22–42. — Бібліогр.: 28 назв. — англ. 1726-3255 2000 Mathematics Subject Classification: 20F69, 20F10, 20E08. http://dspace.nbuv.gov.ua/handle/123456789/157340 en Algebra and Discrete Mathematics Інститут прикладної математики і механіки НАН України
institution	Digital Library of Periodicals of National Academy of Sciences of Ukraine
collection	DSpace DC
language	English
description	We study Sushchansky p-groups introduced in [Sus79]. We recall the original definition and translate it into the language of automata groups. The original actions of Sushchansky groups on p-ary tree are not level-transitive and we describe their orbit trees. This allows us to simplify the definition and prove that these groups admit faithful level-transitive actions on the same tree. Certain branch structures in their self-similar closures are established. We provide the connection with, so-called, G groups [BGS03] that shows that all Sushchansky groups have ˇ intermediate growth and allows to obtain an upper bound on their period growth functions.
format	Article
author	Bondarenko, I.V. Savchuk, D.M.
spellingShingle	Bondarenko, I.V. Savchuk, D.M. On Sushchansky p-groups Algebra and Discrete Mathematics
author_facet	Bondarenko, I.V. Savchuk, D.M.
author_sort	Bondarenko, I.V.
title	On Sushchansky p-groups
title_short	On Sushchansky p-groups
title_full	On Sushchansky p-groups
title_fullStr	On Sushchansky p-groups
title_full_unstemmed	On Sushchansky p-groups
title_sort	on sushchansky p-groups
publisher	Інститут прикладної математики і механіки НАН України
publishDate	2007
url	http://dspace.nbuv.gov.ua/handle/123456789/157340
citation_txt	On Sushchansky p-groups / I.V. Bondarenko, D.M. Savchuk // Algebra and Discrete Mathematics. — 2007. — Vol. 6, № 2. — С. 22–42. — Бібліогр.: 28 назв. — англ.
series	Algebra and Discrete Mathematics
work_keys_str_mv	AT bondarenkoiv onsushchanskypgroups AT savchukdm onsushchanskypgroups
first_indexed	2025-07-14T09:47:08Z
last_indexed	2025-07-14T09:47:08Z
_version_	1837615210218651648
fulltext	Jo u rn al A lg eb ra D is cr et e M at h . Algebra and Discrete Mathematics RESEARCH ARTICLE Number 2. (2007). pp. 22 – 42 c© Journal “Algebra and Discrete Mathematics” On Sushchansky p-groups Ievgen V. Bondarenko, Dmytro M. Savchuk Dedicated to V.I. Sushchansky on the occasion of his 60th birthday Abstract. We study Sushchansky p-groups introduced in [Sus79]. We recall the original definition and translate it into the language of automata groups. The original actions of Sushchan- sky groups on p-ary tree are not level-transitive and we describe their orbit trees. This allows us to simplify the definition and prove that these groups admit faithful level-transitive actions on the same tree. Certain branch structures in their self-similar clo- sures are established. We provide the connection with, so-called, G groups [BGŠ03] that shows that all Sushchansky groups have intermediate growth and allows to obtain an upper bound on their period growth functions. Introduction Sushchansky p-groups were introduced in [Sus79] as one of the pioneering examples of finitely generated infinite torsion groups, providing counter- examples to the General Burnside problem. Initially, this problem was solved by E.S. Golod in [Gol64] using the Golod-Shafarevich theorem. Simpler and easier to handle counter-examples were constructed by S. V. Aleshin in [Ale72] by means of automata. The use of automata groups to resolve Burnside’s problem was earlier suggested by V. M. Glush- kov in [Glu61]. But only after the results of R. I. Grigorchuk from [Gri80, Gri83] automata groups became the subject of deeper investigation. It Both authors were partially supported by NSF grants DMS-0308985 and DMS- 0456185 2000 Mathematics Subject Classification: 20F69, 20F10, 20E08. Key words and phrases: Burnside groups, growth of groups, automata groups, branch groups. Jo u rn al A lg eb ra D is cr et e M at h .I. Bondarenko, D. Savchuk 23 happened that this class contains groups with many extraordinary prop- erties, like infinite torsion groups, groups of intermediate growth, groups of finite width, just-infinite groups, etc. V.I. Sushchansky used a different language, namely the language of tableaux, introduced by L. Kaluzhnin to study properties of iterated wreath products [Kal48]. For each prime p > 2, V.I. Sushchansky con- structed a finite family of infinite p-groups generated by two tableaux. Each such a tableau naturally defines an automorphism of a rooted tree and, as was already noticed in [GNS00], can be represented by a finite initial automaton. We describe these automata and study Sushchansky groups and their actions on rooted trees by means of this well-developed language. The structure of the paper is as follows. In Section 1 we recall the original definition of Sushchansky groups. In Section 2 we describe the corresponding automata. The associated action on a rooted tree is not level-transitive and in Section 3 we describe its orbit tree and show that there exists a faithful level-transitive action given by finite initial au- tomata. The self-similar closure is studied in Section 4. The main re- sults are presented in Section 5. It was pointed out in [Gri85a] that all Sushchansky p-groups have intermediate growth, but only the main idea of the proof was given. Here we provide a complete proof of this fact together with new estimates on the growth function, thus contributing to the Milnor question [Mil68], which was solved in [Gri83] by R.I. Grig- orchuk. Also we give an upper bound on the period growth function. The main idea is to use G groups of intermediate growth introduced in [BŠ01] (see also [BGŠ03]). For each Sushchansky p-group we construct a G group of intermediate growth and prove that their growth functions are equivalent. The authors wish to thank Zoran Šunić for fruitful discussions and important comments, which enhanced the paper. 1. Original definition via tableaux Let X = {0, 1, . . . , p − 1} be a finite alphabet for some prime p. We identify X with the finite field Fp. The set X∗ of all finite words over X has a natural structure of a rooted p-ary tree. Every automorphisms g ∈ Aut X∗ of this tree induces an automorphism g\|v of the subtree vX∗ by the rule g\|v(w) = u if and only if g(vw) = g(v)u. This automorphism is called the restriction of g on word v (in some papers the word section or state is used). The Sylow p-subgroup P∞ of the profinite group Aut X∗ is equal to Jo u rn al A lg eb ra D is cr et e M at h .24 On Sushchansky p-groups the infinite wreath product of cyclic groups of order p, i.e. P∞ = ≀i≥1C (i) p . Using this description one can construct special “tableau” representa- tion of P∞. The “tableau” representation was initially introduced by L. Kaluzhnin for Sylow p-subgroups of symmetric groups of order pm in [Kal48]. The group P∞ is isomorphic to the group of triangular tableaux of the form: u = [a1, a2(x1), a3(x1, x2), . . .], where a1 ∈ Fp, ai+1(x1, . . . , xi) ∈ Fp[x1, . . . , xi]/〈x p 1 − x1, . . . , x p i − xi〉. The multiplication of tableaux is given by the formula: [a1, a2(x1), a3(x1, x2), . . .] · [b1, b2(x1), b3(x1, x2), . . .] = = [a1 + b1, a2(x1) + b2(x1 + a1), a3(x1, x2) + b3(x1 + a1, x2 + a2(x1)), . . .]. The action of the tableau u on the tree X∗ is given by: u(x1x2 . . . xn) = y1y2 . . . yn, (1) where y1 = x1 + a1, y2 = x2 + a2(x1), . . . , yn = xn + an(x1, . . . , xn−1), where all calculations are made by identifying X with the field Fp. For the duration of the rest of the paper we fix a prime p > 2. Fix some order λ = {(αi, βi), i = 1, . . . , p2} on the set of pairs {(α, β)\|α, β ∈ Fp}. For j > p2 we define (αj , βj) = (αi, βi) where i ≡ j mod p2. Define two tableaux A = [1, x1, 0, 0, . . .], Bλ = [0, 0, b3(x1, x2), b4(x1, x2, x3), . . .], where the coordinates of Bλ are defined by its values in the following way: a) b3(2, 1) = 1; b) bi(0, 0, . . . , 0, 1) = 1 if βi 6= 0; c) bi(1, 0, . . . , 0, 1) = −αi βi if βi 6= 0 and bi(1, 0, . . . , 0, 1) = 1 if βi = 0; d) all the other values are zeroes. The group Gλ = 〈A, Bλ〉 is called the Sushchansky group of type λ. The following theorem is proven in [Sus79]. Theorem 1. Gλ is infinite periodic p-group for any type λ. Jo u rn al A lg eb ra D is cr et e M at h .I. Bondarenko, D. Savchuk 25 2. Automata approach Another language dealing with groups acting on rooted trees is the lan- guage of automata groups. For a definitions we refer to the survey pa- per [GNS00]. Many groups related to Burnside and Milnor Problems happen to be in the class of groups generated by finite automata. The Sushchansky groups are not an exception and we describe the structure of the corresponding automata in this section. The action of every automorphism g of the rooted tree X∗ can be encoded by an initial automaton whose states are the restrictions of g on the finite words over X. In the case when this set is finite we call g a finite-state automorphism. The action of such an automorphism is encoded by a finite automaton. It is known that (see [GNS00]) that Aut X∗ ∼= AutX∗≀Sym(X), which gives a convenient way to represent every automorphism in the following form: g = (g\|0, g\|1, . . . , g\|p−1)πg, where g\|0, g\|1, . . . , g\|p−1 are the restrictions of g on the letters of X and πg is the permutation of X induced by g. The multiplication of automorphisms written in this way is performed as follows. If h = (h\|0, h\|1, . . . , h\|p−1)πh then gh = (g\|0h\|πg(0), . . . , g\|p−1h\|πg(p−1))πgπh. Now we proceed with an explicit construction of automata associated to Sushchansky groups. Let σ = (0, 1, . . . , p− 1) be a cyclic permutation of X. With a slight abuse of notation, depending on the context, σ will also denote the automorphism of X∗ of the form (1, 1, . . . , 1)σ. Given the order λ = {(αi, βi)} define words u, v ∈ Xp2 in the following way: ui = { 0, if βi = 0; 1, if βi 6= 0. vi = { 1, if βi = 0; −αi βi , if βi 6= 0. The words u and v encode the actions of Bλ on the words 00 . . . 01∗ and 10 . . . 01∗, respectively. Using the words u and v we can construct auto- morphisms q1, . . . , qp2 , r1, . . . , rp2 of the tree X∗ by the following recurrent formulas: qi = (qi+1, σ ui , 1, . . . , 1), ri = (ri+1, σ vi , 1, . . . , 1), (2) for i = 1, . . . , p2, where the indices are considered modulo p2, i.e. i = i + np2 for any n. Jo u rn al A lg eb ra D is cr et e M at h .26 On Sushchansky p-groups Formula (1) implies that qi and ri are precisely the restrictions of Bλ on the words 00(0)i−1+np2 and 10(0)i−1+np2 , respectively, for any n ≥ 0. The action of the tableau A is given by: A = (1, σ, σ2, . . . , σp−1)σ; while Bλ acts trivially on the second level and the action on the rest is given by the restrictions: Bλ\|00 = q1, Bλ\|10 = r1, Bλ\|21 = σ and all the other restrictions are trivial. In particular, the automorphisms A and Bλ are finite-state and Sushchansky group Gλ is generated by two finite initial automata. Denote the union of these two automata by Au,v. Its structure is shown in Figure 1. The particular automaton for p = 3 and the lexicographic order on {(α, β)\|α, β ∈ Fp} is given in Figure 2 (all the arrows not shown in the figures go to the trivial state 1). Jo u rn al A lg eb ra D is cr et e M at h . PSfrag repla ements 0=1 p� 1=01 0=00=0 0=0 0=0 0=00=00=00=00=00=00=00=0 0=0 0=00=0 1=1 1=1 1=1 1=12=2 � �p�2 �p�1�2A B q1r1r2r3r4r5 rp2�1 rp2 q2 q3 q4q5qt�1qt Figure 1: The Structure of Sushchansky automata Notice that the word v cannot be periodic since it contains exactly p−1 zeros and p−1 ∤ p2. On the contrary u may be periodic with period p. In this case we have qi = qi+p and the minimization of Au,v contains p2 + 2p + 5 states. If u is not periodic then Au,v contains 2p2 + p + 5 states. Let t be the length of the minimal period in u (thus either t = p or t = p2). Jo u rn al A lg eb ra D is cr et e M at h .I. Bondarenko, D. Savchuk 27 Lemma 2. The group 〈q1, . . . , qt, r1, . . . , rp2〉 is elementary abelian p- group. Proof. All qi, rj have order p because qp i = (qp i+1, 1, 1, . . . , 1), rp i = (rp i+1, 1, 1, . . . , 1), and therefore qp i and rp i act trivially on the tree. All qi, rj commute with each other, because qiqj = (qi+1qj+1, σ ui+uj , 1, . . . , 1), qjqi = (qj+1qi+1, σ ui+uj , 1, . . . , 1); rirj = (ri+1rj+1, σ vi+vj , 1, . . . , 1), rjri = (rj+1ri+1, σ vi+vj , 1, . . . , 1); qirj = (qi+1rj+1, σ ui+vj , 1, . . . , 1), rjqi = (rj+1qi+1, σ ui+vj , 1, . . . , 1), so the corresponding pairs act equally on the tree. The last lemma implies that the order of Bλ is p. Since Ap = (σ p(p−1) 2 , σ p(p−1) 2 , . . . , σ p(p−1) 2 ) and p is odd, the order of A is also p. Jo u rn al A lg eb ra D is cr et e M at h . PSfrag repla ements 0=00=00=00=00=00=0 0=00=00=00=00=0 0=0 0=0 0=00=0 1=1 1=11=11=11=11=11=11=1 1=1 1=11=1 2=2 1=22=0 � ��2 A B q2 q3q1r1 r2r3r4r5 r6 r7 r8 r9 Figure 2: Sushchansky automaton for p = 3 corresponding to the lexico- graphic order Jo u rn al A lg eb ra D is cr et e M at h .28 On Sushchansky p-groups 3. Actions on rooted trees Here we describe the structure of the action of Gλ on a p-ary tree by means of the orbit tree. This notion is defined in [Ser03] and used in [GNS01] to establish a criterion determining when two automorphisms of a rooted tree are conjugate. Here we use it to simplify the definition of Sushchan- sky groups and show that they admit a faithful level-transitive action on a regular rooted tree. Definition 1. Let G be a group acting on a regular p-ary tree X∗. The orbit tree of G is a graph whose vertices are the orbits of G on the levels of X∗ and two orbits are adjacent if and only if they contain vertices that are adjacent in X∗. Proposition 3. The structure of the orbit tree of Gλ does not depend on the type λ and is shown in Figure 3. Figure 3: The Orbit Tree of Sushchansky group Proof. Let TO be the orbit tree of Gλ. Denote by Orb(w) the orbit of the word w ∈ X∗ under the action of Gλ. Define the set V = {xyw ∈ X∗\|xy ∈ Orb(00) and w ∈ X∗} ∪ {∅}, (3) where ∅ is the root of the tree. The generator Bλ stabilizes the second level of the tree and hence the orbit Orb(00) coincides with the orbit of 00 under the action of the group generated by A. The set V and its compliment W = X∗ \V are invariant under the action of Gλ. Jo u rn al A lg eb ra D is cr et e M at h .I. Bondarenko, D. Savchuk 29 Notice that {00, 10, 21} ⊂ Orb(00) and the generator Bλ acts trivially on all words that lie in the set W . Since the restrictions of A on all words of length ≥ 2 are trivial, every element g ∈ Gλ that acts trivially on the second level of the tree must stabilize all the vertices of the set W . Hence, the orbits of Gλ on W coincide with the ones of A. Automorphism A acts transitively on the first level and has order p. Therefore the orbit of any word w ∈ W consists of p vertices, namely the images of w under the action of the cyclic group of order p generated by A. Therefore the first two levels of TO are exactly as shown in Figure 3 and p − 1 vertices on the second level of TO are the roots of regular p-ary trees. Let us prove that Gλ acts transitively on the levels of the set V , i.e. for every n ≥ 1 the group Gλ acts transitively on the set Vn = {xyw ∈ Xn+1\|xy ∈ Orb(00) and w ∈ Xn−1}. We use induction on n. For n = 1 there is nothing to prove. Assume Gλ acts transitively on Vn and consider the (n + 1)-th level. Since by construction either un−1 = 1 or vn−1 = 1, the restriction of Bλ on either 00 . . . 01 or 10 . . . 01 is equal to σ. Denote this word as s (here s ∈ Vn) and note that B stabilizes s. To prove the induction step it suffices for an arbitrary s′z′ ∈ Vn+1, where s′ ∈ Vn and z′ ∈ X, to construct an element g ∈ Gλ such that g(s0) = s′z′. By the inductive assumption there is an element h ∈ Gλ such that h(s) = s′. Suppose h−1(s′z′) = sz for some letter z ∈ X. Then for g = (Bλ)zh (here we consider z as an integer) we have g(s0) = h((Bλ)z(s0)) = h(s(Bλ)z\|s(0)) = h(s(Bλ\|s) z(0)) = = h(sσz(0)) = h(sz) = s′z′ as required. The set V has a natural structure of a rooted p-ary tree T , where the root ∅ is connected by an edge with every vertex in Orb(00) and there is an edge between w and wx for all w ∈ V and x ∈ X. In other words, there is a natural 1-to-1 correspondence between V and vertices of T given by xyw 7→ xw for xy ∈ Orb(00) and w ∈ X∗. Since the set V is invariant under the action of Gλ, the group Gλ acts by automorphisms on the tree T . This action has simpler structure and the following proposition holds. Proposition 4. The action of Sushchansky group Gλ on the tree T is faithful, level transitive and has the following form A = σ, Bλ = (q1, r1, σ, 1, . . . , 1), qi = (qi+1, σ ui , 1, . . . , 1), ri = (ri+1, σ vi , 1, . . . , 1). (4) Jo u rn al A lg eb ra D is cr et e M at h .30 On Sushchansky p-groups Proof. The expressions (4) follow directly from the definition of Sushchan- sky groups. Let us prove that this action is faithful. Take an arbitrary nontrivial element g ∈ Gλ. If g acts non-trivially on the second level of X∗, then the exponent of A in g is not divisible by p. But then g acts non-trivially on the first level of T as well because it is fixed under Bλ and A acts there as σ. If g acts trivially on the second level of X∗ then it acts trivially on the complement of V in X∗ according to Proposition 3. Therefore to be nontrivial it must act nontrivially on T . We proved in Proposition 3 that Gλ acts transitively on every set Vn, which is precisely the nth level of the tree T . 4. Self-similar closure The Sushchansky group Gλ is not generated by all the states of Au,v and is not self-similar (see definition below). However, we can embed it into a larger self-similar group where we can use some known techniques to derive some important results about Gλ itself. In particular that Gλ is amenable (Corollary 8) and that the word problem is solvable in poly- nomial time (Corollary 9). For the definitions not given here and more information on self-similar groups we refer to [Nek05] and [BGŠ03]. Definition 2. A group G < Aut X∗ is called self-similar if g\|u ∈ G for any g ∈ G and word u ∈ X∗. The self-similar closure of G < Aut X∗ is the group generated by all the restrictions of all the elements of G on words in X∗. Let G̃λ be the self-similar closure of Gλ, i.e. G̃λ is generated by all the states of the automaton Au,v. Consider also the self-similar subgroup K = 〈q1, . . . , qt, r1, . . . , rp2 , σ〉 of G̃λ. Lemma 5. The group K is not periodic. Proof. First, consider the case t = p. Then all ui’s are equal to 1 except one equal to 0. In particular, ∑p i=1 ui = p − 1. Then the element g = q1q2 · · · qtσ p−1 has representation g = (q1q2 · · · qt, σ p−1, 1, . . . , 1)σp−1. Therefore gp = (q1q2 · · · qtσ p−1, ∗, . . . , ∗) = (g, ∗, . . . , ∗). Since g is nontrivial it must have infinite order. Jo u rn al A lg eb ra D is cr et e M at h .I. Bondarenko, D. Savchuk 31 In case t = p2, exactly p of ui’s are zeros. We mark the vertices of the cycle of qi’s in the automaton by the corresponding ui’s. There are at most ( p 2 ) different distances between the zeros in the cycle. But the length of the cycle is p2 so there are p2 − 1 2 > p2 − p 2 = ( p 2 ) possible distances in the cycle, so let d be a distance that is not attained as a distance between two zeros. Now consider the element g = q1qd+1σ up2+ud . It can be written as g = (q2qd+2, σ u1+ud+1 , 1, . . . , 1)σup2+ud . Since the distance between states qp2 and qd in the cycle is exactly d at least one of up2 and ud is nonzero so σup2+ud is a cycle of length p. Hence gp = (q2qd+2σ u1+ud+1 , ∗, . . . , ∗). Therefore if the order \|g\| of g is finite, then it is not smaller than p · \|q2qd+2σ u1+ud+1 \|. Now we repeat this procedure p2 times and on the i-th iteration we get qiqd+iσ ui−1+ud+i−1 = (qi+1qd+i+1, σ ui+ud+i , 1, . . . , 1)σui−1+ud+i−1 . Again, the distance between qi−1 and qd+i−1 is exactly d so σui−1+ud+i−1 is a cycle of length p and (qiqd+iσ ui−1+ud+i−1)p = (qi+1qd+i+1σ ui+ud+i , ∗, . . . , ∗). Therefore \|qiqd+iσ ui−1+ud+i−1 \| ≥ p · \|qi+1qd+i+1σ ui+ud+i \|. But after p2 steps we will meet g again. So its order cannot be finite. Definition 3. A group G acting on the tree X∗ is called weakly regular branch over its subgroup P , if 1. G acts transitively on each level Xn, n ≥ 0; 2. P ≻ P × P × · · · × P as geometric embedding induced by the restriction on some level Xk. In case if P is a subgroup of finite index in G, the group G is said to be regular branch over P . Jo u rn al A lg eb ra D is cr et e M at h .32 On Sushchansky p-groups Proposition 6. G̃λ is a weakly regular branch group over Kp. Proof. First of all note that Lemma 5 guarantees that Kp is nontrivial. At least one (in fact more) of the ui’s is non zero, say u1. Then the relations (2) and σq1σ p−1 = (σu1 , 1, . . . , 1, q2) show that the set of restrictions of the elements of K, that stabilize the first level X of the tree, on letter 0 includes the generators of K and hence the whole group K (therefore conjugating by σ ∈ K yields that K is self-replicating, i.e. for any x ∈ X the projection of Stx(K) onto the vertex x coincides with K). Thus for any v ∈ K there is w ∈ K of the form w = (v, σi, 1, . . . , 1, qj 2) for some i and j. But then by Lemma 2 wp = (vp, σip, 1, . . . , 1, qjp 2 ) = (vp, 1, . . . , 1). Therefore Kp ≻ Kp×1×· · ·×1. Since σ acts transitively on the first level and belongs to the normalizer of Kp in K (because σ−1vpσ = (σ−1vσ)p) by conjugation we get Kp ≻ Kp × Kp × · · · × Kp, as geometric embedding. The transitivity of G̃λ on levels follows from the fact that its subgroup K acts nontrivially on the first level and is self-replicating, and hence, level transitive. Another explanation comes from the known fact that a self-similar subgroup of ≀i≥1C (i) p acts level-transitively if and only it is infinite (see [BGK+06]). The proof of the last fact is similar to the proof of transitivity in Proposition 3. We summarize some general properties of G̃λ in the following propo- sition: Proposition 7. The self-similar closure of Gλ is neither torsion, nor torsion free, level-transitive group of tree automorphisms. Moreover, it is generated by a bounded automaton, hence it is contracting and amenable. Proof. The first three assertions are already proved above. The automa- ton Au,v is bounded by Corollary 14 in [Sid00] (see the definition there as well). As a corollary G̃λ is contracting (see [BN03]) and amenable (see [BKNV06]). Corollary 8. Gλ is amenable. Jo u rn al A lg eb ra D is cr et e M at h .I. Bondarenko, D. Savchuk 33 Note also that the last corollary follows from Theorem 16. Corollary 9. The word problem in Gλ is solvable in polynomial time. Proof. See Proposition 2.13.10 in [Nek05]. 5. Intermediate growth Let G be a group finitely generated by a set S. The growth function of G is defined by γG(n) = ∣ ∣{g ∈ G\|g = s1s2 . . . sk for some si ∈ S ∪ S−1, k ≤ n} ∣ ∣ . Two functions γ1 and γ2 are called equivalent if there exists a constant C > 0 such that γ1( 1 C n) ≤ γ2(n) ≤ γ1(Cn) for all n. The growth function γG depends both on G and on S, but the equivalence class of γG does not depend on S. In 1968 John Milnor asked about the existence of finitely generated groups with growth that is intermediate between polynomial and expo- nential. The first examples of such groups were provided by R.I. Grig- orchuk in [Gri83], where he constructed uncountable family of such groups. In particular, it was shown, that there are groups of intermediate growth generated by automata with 5 states, namely, Gω for ω = (012)∞ (not to be confused with Sushchansky groups Gλ). These examples were general- ized to the notion of G groups [BGŠ03]. Under some finiteness restriction all G groups have intermediate growth. Recently it was proved [BP06] that there is a 4-state automaton over a 2-letter alphabet generating a group of intermediate growth. This group itself is isomorphic to the iterated monodromy group of the map f(z) = z2 + i. But it is still an open question whether there is a group of intermediate growth generated by a 3-state automaton over a 2-letter alphabet. In view of the examples above it is not very surprising that the two of the pioneering examples of infinite finitely generated periodic groups introduced by S.V. Aleshin in [Ale72] and V.I. Sushchansky in [Sus79] also have intermediate growth. For Aleshin group it follows from the intermediate growth of Grigorchuk group and the result of Y.I. Mer- zlyakov [Mer83], who proved that Aleshin group contains a subgroup of finite index isomorphic to the subdirect product of four copies of Grig- orchuk group. Also the relation between these two groups was studied in [Gri85b]. As was mentioned above in [Gri85a] R.I. Grigorchuk pointed out that all Sushchansky groups have intermediate growth, but only the idea of Jo u rn al A lg eb ra D is cr et e M at h .34 On Sushchansky p-groups proof was given. In this paper we give a complete proof of this fact based on the results from [BŠ01]. At the present moment the main method of obtaining the upper bounds for growth functions of groups was originated by R.I. Grigorchuk in [Gri84]. Different modifications of this method in [Bar98, MP01, BŠ01] allowed to improve existing estimates and to prove the estimates for new groups. As for the lower bounds for growth functions, there are several tech- niques. In [Gri84] R.I. Grigorchuk uses self-similarity to obtain the lower bound of the form e √ n for most of his groups. Moreover, he shows that any group G that is abstractly commensurable with its own power Gk for some k ≥ 2 has a growth function not smaller that enα for some 0 < α ≤ 1. In [Gri89] R.I. Grigorchuk used bounds on the coefficients of Hilbert- Poincaré series of graded algebras associated with groups to bound their growth functions. Namely, it was obtained that any residually p-group whose growth function is not bounded above by polynomial, must grow at least as e √ n. Y.G. Leonov [Leo01], L. Bartholdi and Z. Šunić [Bar98, BŠ01] used more advanced techniques (common in spirit to the ones used in [Gri84]) also based on certain self-similarity of the groups acting on trees. In obtaining the lower bounds for the growth functions of these groups the important role was played by the property, which is in some sense opposite to contraction. The main idea is that the restrictions of elements can not be much shorter than the elements themselves. A. Erschler used random walks and Poisson boundary to approach to this question. In particular, in [Ers04] it was shown that the growth function of Grigorchuk group Gω for ω = (01)∞, which is generated by 5- state automaton, grows faster than enα for any α < 1. The upper estimate of the same sort was obtained for this group in spirit of [Gri84], which shows that groups Gω for ω = (012)∞ and ω = (01)∞ have essentially different growth functions. Recall the definition of a G group. Definition 4. Let R be a subgroup of Sym(X), D be any group with a sequence of homomorphisms wi : D → Sym(X), i ≥ 1. Then R acts on the first level of X∗ and D acts on X∗ in the following way. Each d ∈ D defines the automorphism d̂ that acts trivially on the first level and is given by its restrictions d̂ ∣ ∣ 0i1 = wi(d), i ≥ 1 and all the other restrictions act trivially on X. Denote D̂ = {d̂ \| d ∈ D}. Jo u rn al A lg eb ra D is cr et e M at h .I. Bondarenko, D. Savchuk 35 The group G = 〈R, D̂〉 is called a G group if the following conditions are satisfied: (i) The groups R and wi(D), i ≥ 1, act transitively on X. (ii) For each d ∈ D the permutation wi(d) is trivial for infinitely many indices. (iii) For each nontrivial d ∈ D the permutation wi(d) is nontrivial for infinitely many indices. The groups R and D are called the root part and the directed part of G correspondingly. Note that in [BGŠ03] the definition of a G group is given in slightly more general settings. The results in [BŠ01] and [BGŠ03] imply the following theorem. Theorem 10. All G groups with finite directed part have intermediate growth. There is a lower bound for the growth of such groups given in [BGŠ03]: γG(n) � enα , (5) where α = log(\|X\|) log(\|X\|)+log(2) . The sequence of homomorphisms wi in the definition of a G group is called r-homogeneous, if for every finite subsequence of r consecutive homomorphisms wi+1, wi+2, . . . , wi+r every element of D is sent to the identity by at least one of the homomorphisms from this finite subse- quence. In particular, if the sequence of homomorphisms {wi, i ≥ 1} defining a G group is periodic with period r, it is also r-homogeneous. It is proved in [BŠ01] that in case of r-homogeneous sequence of defin- ing homomorphisms there is an estimate of the upper bound on the growth function. Moreover, in this case if the directed part has finite exponent there is an upper bound on the torsion growth function π(n) (the maximal order of an element of length at most n). Theorem 11 (η-estimate). Let G be a G group defined by an r-homoge- neous sequence of homomorphisms. Then the growth function of the group G satisfies γG(n) � enβ , (6) where β = log(\|X\|) log(\|X\|)−log(ηr) < 1 and ηr is the positive root of the polynomial xr + xr−1 + xr−2 − 2. Jo u rn al A lg eb ra D is cr et e M at h .36 On Sushchansky p-groups If the directed part D of G has finite exponent q, then the group G is torsion and there exists a constant C > 0, such that the torsion growth function satisfies π(n) ≤ Cnlog1/ηr (q). (7) Sushchansky groups Gλ are not G groups, because the automorphism Bλ cannot be expressed as d̂ for some homomorphisms wi. On the other hand, the automorphisms qi and ri can, and the following proposition shows that the self-similar closure of Gλ contains a subgroup which is a G group. Since the simplified definition of Gλ from Proposition 4 does not simplify considerably the proofs in this section, we use the original definition in order to make this section independent. Proposition 12. The group H = 〈q1, r1, σ〉 is a G group with finite directed part defined by a periodic sequence of homomorphisms with period p2. Proof. We prove that the subgroups 〈q1, r1〉 and 〈σ〉 are the directed and the root parts of H. First observe that 〈q1, r1〉 ≃ Zp ⊕ Zp. Indeed, the group 〈q1, r1〉 is elementary abelian p-group by Lemma 2. Suppose that r1 ∈ 〈q1〉, r1 = qk 1 . Comparing restrictions on words 0 . . . 01 we get vi = kui. Contradiction, since ui = 0 and vi = 1 for i with βi = 0. Consider the periodic sequence of homomorphisms wi : 〈q1, r1〉 → Sym(X) with period p2 given by wi(q1) = σui and wi(r1) = σvi . Then for any d ∈ 〈q1, r1〉 the associated d̂ from the definition of a G group coincides with the automorphism d. To complete the proof we need to check the conditions (i)–(iii) from the definition of a G group. (i) The root part generated by σ acts transitively on X. Furthermore, for any i ≥ 1 wi(q1) = σ, if βi 6= 0; wi(r1) = σ, if βi = 0. In any case wi(〈q1, r1〉) contains σ and thus acts transitively on X. (ii),(iii) Let d = qk 1rl 1, k, l ∈ Zp, be an arbitrary nontrivial element of 〈q1, r1〉. Since the sequence wi is periodic it suffices to show at least one occurrence of trivial and one occurrence of nontrivial wi(d). Find i such that (αi, βi) = (1, 0), if l = 0; (αi, βi) = (k, l), if l 6= 0. Jo u rn al A lg eb ra D is cr et e M at h .I. Bondarenko, D. Savchuk 37 Then wi(d) = { wi(q k 1 ) = σkui = 1, if l = 0; wi(q k 1rl 1) = σkui+lvi = σk+l(−k/l) = 1, if l 6= 0. For a nontrivial occurrence find i such that (αi, βi) = (0, 1), if l = 0; (αi, βi) = (1, 0), if l 6= 0. Then wi(d) = { wi(q k 1 ) = σkui = σk, if l = 0; wi(q k 1rl 1) = σkui+lvi = σl, if l 6= 0. The last proposition shows that the growth function of H satisfies inequalities (5) and (6), for r = p2. Also note that it is proved in [BGŠ03] that a G group is torsion if and only if its directed part D is torsion. Therefore, the group H is torsion. The next proposition exhibits another branch structure inside G̃λ. Proposition 13. The group H = 〈q1, r1, σ〉 is regular branch over its commutator subgroup H ′. Proof. Let Hk = 〈qk, rk, σ〉, k = 1, . . . , p2 be the subgroups of G̃λ. First we show that H ′ k � H ′ k+1 × H ′ k+1 × · · · × H ′ k+1 (8) for all k. Indeed, at least one of uk and vk is nonzero. Suppose uk 6= 0. Then relations qk = (qk+1, σ uk , 1, . . . , 1) and rk = (rk+1, σ vk , 1, . . . , 1) imply [qk, rk] = ([qk+1, rk+1], 1, . . . , 1), [qk, (q σ−1 k )1/uk ] = ([qk+1, σ], 1, . . . , 1), [rk, (q σ−1 k )1/uk ] = ([rk+1, σ], 1, . . . , 1). Since the projection of the stabilizer of the first level in Hk on the leftmost vertex coincides with Hk+1 we get H ′ k � H ′ k+1 × 1×· · ·× 1. Conjugation by σ ∈ Hk implies inclusion (8). Since H1 = Hp2+1 = H, we obtain H ′ � H ′×H ′×· · ·×H ′ as geometric embedding induced by the restriction on Xp2 . The transitivity of H on the levels is proved by the method used in Proposition 3. Now H is a torsion p-group, hence, so is H/H ′, which is abelian. But each torsion finitely generated abelian group is finite. Thus, H ′ is a subgroup of finite index in H. Jo u rn al A lg eb ra D is cr et e M at h .38 On Sushchansky p-groups When we deal with a group G of automorphisms of X∗, it is sometimes difficult to say something about the whole group, but we know something about the group P generated by all the restrictions of the elements in G on some level k of the tree. In case G is self-similar, P is a subgroup of G and if G is self-replicating, P coincides with G. Some properties of P are inherited by G itself. In particular, if P is finite or torsion then so is G (the converse is not true). But what we are interested in here is that the growth of G can be estimated in terms of the growth of P . Let S be a finite generating set of G. Then P is generated by the set S̃ of the restrictions of all elements of S on all vertices of k-th level Xk of the tree. The following lemma holds. Lemma 14. The growth function γG(n) of the group G with respect to S is bounded from above by γG(n) � ( γP (n) )\|X\|k , (9) where γP (n) is the growth function of the group P with respect to S̃. In particular, the growth type of G (finite, polynomial, intermediate or exponential) cannot exceed the one of P . Proof. Let g ∈ G be an element of length n with respect to the generating set S. This element induces a permutation πk of the k-th level of the tree and \|X\|k restrictions g\|v, v ∈ Xk, on words of length k. Moreover, different automorphisms correspond to different tuples (πk, {g\|v, v ∈ Xk}) of restrictions and permutations. Each such a restriction is a word of length not greater than n with respect to the generating set S̃ of P . So for each vertex v ∈ Xk the number of possible restrictions on v is bounded from above by γP (n). The following corollary shows an easy way to construct new examples of groups with intermediate (finite, polynomial, exponential) growth. Corollary 15. Let F be a finite set of automorphisms from Aut X∗, whose restrictions on some level k belong to G (in particular, F could be a set of finitary automorphisms). Then γG(n) - γ〈G,F 〉(n) - ( γG(n) )\|X\|k . where γ〈G,F 〉(n) is the growth function of the group 〈G, F 〉 with respect to S ∪ F . In particular the previous corollary shows that if a group G is gener- ated by a finite automaton, then the growth type of this group depends only on the nucleus (see definition in [Nek05]) of this automaton. Jo u rn al A lg eb ra D is cr et e M at h .I. Bondarenko, D. Savchuk 39 An interesting question is whether it is true that if G grows faster than polynomially then γG(n) ∼ γ〈G,F 〉(n). We are ready to prove the main results. Theorem 16. All Sushchansky p-groups have intermediate growth. The growth function of each Sushchansky p-group Gλ satisfies enα � γGλ (n) � enβ , where α = log(p) log(p)+log(2) , β = log(p) log(p)−log(ηr) and ηr is the positive root of the polynomial xr + xr−1 + xr−2 − 2, where r = p2. Proof. The group generated by all the restrictions of elements of Gλ on the second level is H = 〈q1, r1, σ〉, which is a G group of intermediate growth by Proposition 12 and Theorems 10 and 11, whose growth function satisfies inequalities (5) and (6). Therefore by Lemma 14 the Sushchansky group Gλ has subexponential growth function, which satisfies inequality γG(n) - (γH(n))p2 - γH(n). (10) The last part of this inequality follows from Proposition 13, where it is proved that H is regular branch over H ′. Now consider the subgroup L = 〈Bλ, ABλAp−1, A2BλAp−2〉 of Gλ. This subgroup stabilizes the second level of the tree and the restrictions of the generators on the second level look like: Bλ = (q1, ∗, . . . , ∗), ABλAp−1 = (r1, ∗, . . . , ∗), A2BλAp−2 = (σ, ∗, . . . , ∗). Each word of length n in L will be projected on the corresponding word of length n in H. Therefore γL(n) ≥ γH(n) for all n ≥ 1. But L is a finitely generated subgroup of Gλ. Thus γH(n) - γL(n) - γG(n). (11) Inequalities (10) and (11) imply γG(n) ∼ γH(n). (12) Finally, it was mentioned above that the group H is torsion as a G group with torsion directed part. But periodicity of H implies that Gλ is periodic as well. This gives a different proof of Theorem 1 proved by V.I. Sushchansky. The theory of G groups allows to sharpen this result. Jo u rn al A lg eb ra D is cr et e M at h .40 On Sushchansky p-groups Theorem 17. There is a constant C > 0, such that the torsion growth function of each Sushchansky p-group Gλ satisfies inequality πGλ (n) ≤ Cnlog1/ηr (p), where ηr is the same as in the previous theorem. Proof. By Proposition 12 the group H is a G group defined by a p2- homogenous sequence of homomorphisms, whose directed part 〈q1, r1〉 is an elementary abelian p-group (see Lemma 2). Therefore by Theorem 11 the torsion growth function πH(n) satisfies inequality πH(n) ≤ C1n log1/ηr (p) for some constant C1. For any element g of length n in Gλ, gp stabilizes the second level of the tree and the restrictions of gp at the vertices of the second level are the elements of H, whose length is not bigger than pn. Hence, the order of gp cannot be bigger than the least common multiple of the orders of g\|v, v ∈ X2. Since the orders of these restrictions are the powers of p, the least common multiple coincides with the maximal order among the restrictions. This implies Order(g) = p · Order(gp) ≤ pπH(pn) ≤ pC1(pn)log1/ηr (p) ≤ Cnlog1/ηr (p) for C = C1p log1/ηr (p)+1. References [Ale72] S. V. Alešin. Finite automata and the Burnside problem for periodic groups. Mat. Zametki, 11:319–328, 1972. [Bar98] Laurent Bartholdi. The growth of Grigorchuk’s torsion group. Internat. Math. Res. Notices, (20):1049–1054, 1998. [BGK+06] Ievgen Bondarenko, Rostislav Grigorchuk, Rostyslav Kravchenko, Yevgen Muntyan, Volodymyr Nekrashevych, Dmytro Savchuk, and Zoran Šunić. Groups generated by 3-state automata over 2-letter alphabet, I. (available at http://arxiv.org/abs/math.GR/0612178 ), 2006. [BGŠ03] Laurent Bartholdi, Rostislav I. Grigorchuk, and Zoran Šuniḱ. Branch groups. In Handbook of algebra, Vol. 3, pages 989–1112. North-Holland, Amsterdam, 2003. [BKNV06] Laurent Bartholdi, Vadim Kaimanovich, Volodymyr Nekrashevych, and Balint Virag. Amenability of automata groups. (preprint), 2006. [BN03] E. Bondarenko and V. Nekrashevych. Post-critically finite self-similar groups. Algebra Discrete Math., (4):21–32, 2003. Jo u rn al A lg eb ra D is cr et e M at h .I. Bondarenko, D. Savchuk 41 [BP06] Kai-Uwe Bux and Rodrigo Pérez. On the growth of iterated monodromy groups. In Topological and asymptotic aspects of group theory, volume 394 of Contemp. Math., pages 61–76. Amer. Math. Soc., Providence, RI, 2006. (available at http://www.arxiv.org/abs/math.GR/0405456 ). [BŠ01] Laurent Bartholdi and Zoran Šuniḱ. On the word and period growth of some groups of tree automorphisms. Comm. Algebra, 29(11):4923–4964, 2001. [Ers04] Anna Erschler. Boundary behavior for groups of subexponential growth. Ann. of Math. (2), 160(3):1183–1210, 2004. [Glu61] V. M. Gluškov. Abstract theory of automata. Uspehi Mat. Nauk, 16(5 (101)):3–62, 1961. [GNS00] R. I. Grigorchuk, V. V. Nekrashevich, and V. I. Sushchanskĭı. Automata, dynamical systems, and groups. Tr. Mat. Inst. Steklova, 231(Din. Sist., Avtom. i Beskon. Gruppy):134–214, 2000. [GNS01] Piotr W. Gawron, Volodymyr V. Nekrashevych, and Vitaly I. Sushchansky. Conjugation in tree automorphism groups. Internat. J. Algebra Comput., 11(5):529–547, 2001. [Gol64] E. S. Golod. On nil-algebras and finitely approximable p-groups. Izv. Akad. Nauk SSSR Ser. Mat., 28:273–276, 1964. [Gri80] R. I. Grigorčuk. On Burnside’s problem on periodic groups. Funktsional. Anal. i Prilozhen., 14(1):53–54, 1980. [Gri83] R. I. Grigorchuk. On the Milnor problem of group growth. Dokl. Akad. Nauk SSSR, 271(1):30–33, 1983. [Gri84] R. I. Grigorchuk. Degrees of growth of finitely generated groups and the theory of invariant means. Izv. Akad. Nauk SSSR Ser. Mat., 48(5):939–985, 1984. [Gri85a] R. I. Grigorchuk. Degrees of growth of p-groups and torsion-free groups. Mat. Sb. (N.S.), 126(168)(2):194–214, 286, 1985. [Gri85b] R.I. Grigorchuk. Groups with intermediate growth function and their ap- plications. Habilitation, Steklov Institute of Mathematics, 1985. [Gri89] R. I. Grigorchuk. On the Hilbert-Poincaré series of graded algebras that are associated with groups. Mat. Sb., 180(2):207–225, 304, 1989. [Kal48] Léo Kaloujnine. La structure des p-groupes de Sylow des groupes symétriques finis. Ann. Sci. École Norm. Sup. (3), 65:239–276, 1948. [Leo01] Yu. G. Leonov. On a lower bound for the growth of a 3-generator 2-group. Mat. Sb., 192(11):77–92, 2001. [Mer83] Yu. I. Merzlyakov. Infinite finitely generated periodic groups. Dokl. Akad. Nauk SSSR, 268(4):803–805, 1983. [Mil68] J. Milnor. Problem 5603. Amer. Math. Monthly, 75:685–686, 1968. [MP01] Roman Muchnik and Igor Pak. On growth of Grigorchuk groups. Internat. J. Algebra Comput., 11(1):1–17, 2001. [Nek05] Volodymyr Nekrashevych. Self-similar groups, volume 117 of Mathematical Surveys and Monographs. American Mathematical Society, Providence, RI, 2005. [Ser03] Jean-Pierre Serre. Trees. Springer Monographs in Mathematics. Springer- Verlag, Berlin, 2003. Jo u rn al A lg eb ra D is cr et e M at h .42 On Sushchansky p-groups [Sid00] S. Sidki. Automorphisms of one-rooted trees: growth, circuit structure and acyclicity. J. of Mathematical Sciences (New York), 100(1):1925–1943, 2000. [Sus79] V. I. Sushchansky. Periodic permutation p-groups and the unrestricted Burnside problem. DAN SSSR., 247(3):557–562, 1979. (in Russian). Contact information I. Bondarenko Kyiv Taras Shevchenko University, Ukraine and Texas A&M University, USA E-Mail: ibond@math.tamu.edu D. Savchuk Texas A&M University, USA E-Mail: savchuk@math.tamu.edu URL: www.math.tamu.edu/˜savchuk

On Sushchansky p-groups

Institution

Ähnliche Einträge