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 and he then proved in a 1984 paper 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. History and significance. The growth of a finitely generated group measures the asymptotics, as formula_1 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 the 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 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, etc. Grigorchuk's group "G" was constructed in a 1980 paper of Rostislav Grigorchuk, where he proved that this group is infinite, periodic and residually finite. In a subsequent 1984 paper Grigorchuk  proved that this group has intermediate growth (this result was announced by Grigorchuk in 1983). More precisely, he proved that "G" has growth "b"("n") that is faster than formula_2 but slower than formula_3 where formula_4. The upper bound was later improved by Laurent Bartholdi to A lower bound of formula_6 was proved by Yurii Leonov. The precise asymptotics of the growth of "G" is still unknown. It is conjectured that the limit exists but even this remained a major open problem. This problem was resolved in 2020 by Erschler and Zheng. They show that the limit equals formula_8. 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. 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. and others. After Grigorchuk's 1984 paper, there were many subsequent extensions and generalizations. 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 "T". The tree "T" is realized as the set formula_9  of all finite strings in the alphabet formula_10 plus the empty string formula_11 which is the root vertex of "T". For a vertex "x" of "T" the string "x"0 is the left child of "x" and the string "x"1 is the right child of "x" in "T". The group of all automorphisms Aut("T") can thus be thought of as the group of all length-preserving permutations "σ" of formula_9 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("T") generated by four specific elements of Aut("T"): where the automorphisms "a", "b", "c", "d" are defined as follows (note that formula_11 is fixed by "all" automorphisms of the tree): We see that only the element "a" is defined explicitly and the elements "b", "c", "d" are defined recursively. To get a better picture of this action we note that formula_16 has a natural gradation into "levels" given by the length of the strings: Now let formula_18 denote the union of all vertices with level formula_19 This means: Since  automorphisms of the tree are length-preserving, formula_18 as a set is fixed by formula_22 for all formula_23 With this in mind we write: We call formula_25 (resp. formula_26) the left (resp. right) branch and denote it by formula_27 (resp. formula_28). With this notation we see that: Now we can also write the action of the elements "b", "c" and "d" in terms of the disjoint union as follows: Similarly we have: Properties. The following are basic algebraic properties of the Grigorchuk group (see for proofs):