# Grigorchuk group

In the mathematical area of group theory, the Grigorchuk group or the first Grigorchuk group is a finitely generated group constructed by Rostislav Grigorchuk that provided the first example of a finitely generated group of intermediate (that is, faster than polynomial but slower than exponential) growth. The group was originally constructed by Grigorchuk in a 1980 paper[2] and he then proved in a 1984 paper[3] that this group has intermediate growth, thus providing an answer to an important open problem posed by John Milnor in 1968. The Grigorchuk group remains a key object of study in geometric group theory, particularly in the study of the so-called branch groups and automata groups, and it has important connections with the theory of iterated monodromy groups.[4]

## History and generalizations

The growth of a finitely generated group measures the asymptotics, as n$\infty$ of the size of an n-ball in the Cayley graph of the group (that is, the number of elements of G that can be expressed as words of length at most n in the generating set of G). The study of growth rates of finitely generated groups goes back to 1950s and is motivated in part by the notion of volume entropy (that is, the growth rate of the volume of balls) in the universal covering space of a compact Riemannian manifold in differential geometry. It is obvious that the growth rate of a finitely generated group is at most exponential and it was also understood early on that finitely generated nilpotent groups have polynomial growth. In 1968 John Milnor posed a question[5] about the existence of a finitely generated group of intermediate growth, that is, faster than any polynomial function and slower than any exponential function. An important result in the subject is Gromov's theorem on groups of polynomial growth, obtained by Gromov in 1981, which shows that a finitely generated group has polynomial growth if and only if this group has a nilpotent subgroup of finite index. Prior to Grigorchuk's work, there were many results establishing growth dichotomy (that is, that the growth is always either polynomial or exponential) for various classes of finitely generated groups, such as linear groups, solvable groups,[6][7] etc.

Grigorchuk's group G was constructed in a 1980 paper of Rostislav Grigorchuk,[2] where he proved that this group is infinite, periodic and residually finite. In a subsequent 1984 paper[3] Grigorchuk proved that this group has intermediate growth (this result was announced by Grigorchuk in 1983).[8] More precisely, he proved that G has growth b(n) that is faster than $\exp(\sqrt n)$ but slower than exp(ns) where $s=\log_{32}31\approx 0.991$. The upper bound was later improved by Laurent Bartholdi[9] to $s=\log2/(\log2-\log\eta)\approx0.7675$, with $\eta^3+\eta^2+\eta=2$. A lower bound of $\exp(n^{0.504})$ was proved by Yurii Leonov.[10]

Grigorchuk's group was also the first example of a group that is amenable but not elementary amenable, thus answering a problem posed by Mahlon Day in 1957.[11]

Originally, Grigorchuk's group G was constructed as a group of Lebesgue-measure-preserving transformations on the unit interval, but subsequently simpler descriptions of G were found and it is now usually presented as a group of automorphisms of the infinite regular binary rooted tree. The study of Grigorchuk's group informed in large part the development of the theory of branch groups, automata groups and self-similar groups in the 1990s–2000s and Grigorchuk's group remains a central object in this theory. Recently important connections between this theory and complex dynamics, particularly the notion of iterated monodromy groups, have been uncovered in the work of Volodymyr Nekrashevych.[12] and others.

After Grigorchuk's 1984 paper, there were many subsequent extensions and generalizations,[13][14][15][16] though no improvement on the upper and lower bounds of the growth of the Grigorchuk group; the precise asymptotics of its growth is still unknown. It is conjectured that $\lim_{n\to \infty} \log_n \log b(n)$ on the word growth exist, but even this remains a major open problem.

## Definition

Although initially the Grigorchuk group was defined as a group of Lebesgue measure-preserving transformations of the unit interval, at present this group is usually given by its realization as a group of automorphisms of the infinite regular binary rooted tree T2. The tree T2 is realized as the set Σ* of all (including the empty string) finite strings in the alphabet Σ = {0,1}. The empty string Ø is the root vertex of T2 and for a vertex x of T2 the string x0 is the left child of x and the string x1 is the right child of x in T2. The group of all automorphisms Aut(T2) can thus be thought of as the group of all length-preserving permutations σ of Σ* that also respect the initial segment relation, that is such that whenever a string x is an initial segment of a string y then σ(x) is an initial segment of σ(y).

The Grigorchuk group G is then defined as the subgroup of Aut(T2) generated by four specific elements a,b,c,d of Aut(T2), that is G = <a,b,c,d> ≤ Aut(T2), where the automorphisms a,b,c,d of T2 are defined recursively as follows:

• a(0x) = 1x, a(1x) = 0x for every x in Σ*;
• b(0x) = 0a(x), b(1x) = 1c(x) for every x in Σ*;
• c(0x) = 0a(x), c(1x) = 1d(x) for every x in Σ*;
• d(0x) = 0x, d(1x) = 1b(x) for every x in Σ*.

Thus a swaps the right and left branch trees TL = 0Σ* and TR = 1Σ* below the root vertex Ø and the elements b,c,d can be represented as:

• b = (a,c),
• c = (a,d),
• d = (1,b).

Here b = (a,c) means that b fixes the first level of T2 (that is, it fixes the strings 0 and 1) and that b acts on TL exactly as the automorphism a does on T2 and that b acts on TR exactly as the automorphism c does on T2. The notation c = (a,d) and d = (1,b) is interpreted similarly, where 1 in d = (1,b) means that d acts on TL as the identity map does on T2.

Of the four elements a, b, c, d of Aut(T2) only the element a is defined explicitly and the elements b, c, d are defined inductively (by induction on the length |x| of a string x in Σ* ), that is, level by level.

### Basic features of the Grigorchuk group

The following are basic algebraic properties of the Grigorchuk group (see[1] for proofs):

• The group G is residually finite. Indeed, for every positive integer n let T[n] be the finite subtree of T2 which is the union of the first n levels of and let ρn:G→Aut(T[n]) be the restriction homomorphism that sends every element of G to its restriction to the finite tree T[n]. The groups Aut(T[n]) are finite and for every nontrivial g in G there exists n such that ρn(g) $\ne$ 1.
• Each of the elements a,b,c,d has order 2 in G, that is, a2 = b2 = c2 = d2 = 1. Thus a = a−1, b = b−1, c = c−1 and d = d−1, so that every element of G can be written as a positive word in a,b,c,d, without using inverses.
• The elements b,c,d pairwise commute and bc = cb = d, bd = db = c, dc = dc = b, so that <b,c,d>≤G is an abelian group of order 4 isomorphic to the direct product of two cyclic groups of order 2.
• The group G is generated by a and any two of the three elements b,c,d (e.g. G = <a, b, c>).
• Using the above recursive notation, in G we have aba = (c,a), aca = (d,a), ada = (b,1).
• The stabilizer StG[1] in G of the 1st level of T2 is the subgroup generated by b, c, d, aba, aca, ada. The subgroup StG[1] is a normal subgroup of index 2 in G and
G = StG[1] $\sqcup$ a StG[1].
• Every element of G can be written as a (positive) word in a,b,c,d such that this word does not contain any subwords of the form aa, bb, cc, dd, cd, dc, bc, cb, bd, db. Such words are called reduced.
• A reduced word represents an element of StG[1] if and only if this word involves an even number of occurrences of a.
• If w is a reduced word of even length involving a positive even number of occurrences of a then there are some words u,v in a,b,c,d (not necessarily reduced) such that in G we have w = (u,v) and such that |u| ≤ |w|/2, |v| ≤ |w|/2. A similar statement holds if w is a reduced word of odd length involving a positive even number of occurrences of a where in the conclusion we have |u| ≤ (|w| + 1)/2, |v| ≤ (|w| + 1)/2.

The last property of G is sometimes called the contraction property. This property plays a key role in many proofs regarding G since it allows to use inductive arguments on the length of a word.

## References

1. ^ a b c Pierre de la Harpe. Topics in geometric group theory. Chicago Lectures in Mathematics. University of Chicago Press, Chicago. ISBN 0-226-31719-6; Ch. VIII, The first Grigorchuk group, pp. 211–264.
2. ^ a b c R. I. Grigorchuk. On Burnside's problem on periodic groups. (Russian) Funktsionalyi Analiz i ego Prilozheniya, vol. 14 (1980), no. 1, pp. 53–54.
3. R. I. Grigorchuk, Degrees of growth of finitely generated groups and the theory of invariant means. Izvestiya Akademii Nauk SSSR. Seriya Matematicheskaya. vol. 48 (1984), no. 5, pp. 939–985.
4. ^ Volodymyr Nekrashevych. Self-similar groups. Mathematical Surveys and Monographs, 117. American Mathematical Society, Providence, RI, 2005. ISBN 0-8218-3831-8.
5. ^ John Milnor, Problem No. 5603, American Mathematical Monthly, vol. 75 (1968), pp. 685–686.
6. ^ John Milnor. Growth of finitely generated solvable groups. Journal of Differential Geometry. vol. 2 (1968), pp. 447–449.
7. ^ Joseph Rosenblatt. Invariant Measures and Growth Conditions, Transactions of the American Mathematical Society, vol. 193 (1974), pp. 33–53.
8. ^ Grigorchuk, R. I. (1983). К проблеме Милнора о групповом росте [On the Milnor problem of group growth]. Doklady Akademii Nauk SSSR (in Russian) 271 (1): 30–33.
9. ^ Laurent Bartholdi. Lower bounds on the growth of a group acting on the binary rooted tree. International Journal of Algebra and Computation, vol. 11 (2001), no. 1, pp. 73–88.
10. ^ Yu. G. Leonov, On a lower bound for the growth of a 3-generator 2-group. Matematicheskii Sbornik, vol. 192 (2001), no. 11, pp. 77–92; translation in: Sbornik Mathematics. vol. 192 (2001), no. 11–12, pp. 1661–1676.
11. ^ Mahlon M. Day. Amenable semigroups. Illinois Journal of Mathematics, vol. 1 (1957), pp. 509–544.
12. ^ Volodymyr Nekrashevych, Self-similar groups. Mathematical Surveys and Monographs, 117. American Mathematical Society, Providence, RI, 2005. ISBN 0-8218-3831-8.
13. ^ Roman Muchnik, and Igor Pak. On growth of Grigorchuk groups. International Journal of Algebra and Computation, vol. 11 (2001), no. 1, pp. 1–17.
14. ^ Laurent Bartholdi. The growth of Grigorchuk's torsion group. International Mathematics Research Notices, 1998, no. 20, pp. 1049–1054.
15. ^ Anna Erschler. Critical constants for recurrence of random walks on G-spaces. Université de Grenoble. Annales de l'Institut Fourier, vol. 55 (2005), no. 2, pp. 493–509.
16. ^ Jeremie Brieussel, Growth of certain groups, Doctoral Dissertation, University of Paris, 2008.
17. ^ a b R. I.Grigorchuk, and J. S. Wilson. A structural property concerning abstract commensurability of subgroups. Journal of the London Mathematical Society (2), vol. 68 (2003), no. 3, pp. 671–682.
18. ^ E. L. Pervova, Everywhere dense subgroups of a group of tree automorphisms. (in Russian). Trudy Matematicheskogo Instituta Imeni V. A. Steklova. vol. 231 (2000), Din. Sist., Avtom. i Beskon. Gruppy, pp. 356–367; translation in: Proceedings of the Steklov Institute of Mathematics, vol 231 (2000), no. 4, pp. 339–350.
19. ^ I. G. Lysënok, A set of defining relations for the Grigorchuk group. Matematicheskie Zametki, vol. 38 (1985), no. 4, pp. 503–516.