Grigorchuk group


In the mathematical area of group theory, the Grigorchuk group or the first Grigorchuk group is a generated group">Generating set of a group">generated group constructed by Rostislav Grigorchuk that provided the first example of a finitely generated group of intermediate 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 of the size of an n-ball in the Cayley graph of the group. 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 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 (mathematician)|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 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. More precisely, he proved that G has growth b that is faster than but slower than where. The upper bound was later improved by Laurent Bartholdi to
A lower bound of was proved by Yurii Leonov. It was conjectured that the limit
and this remained a major open problem until the problem was resolved in 2020 by Anna Erschler and Tianyi Zheng in which it was shown that the limit equals.
Grigorchuk's group was also the first example of a group that is amenable but not amenable group|elementary amenable], thus answering a problem posed by Mahlon Marsh 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 . The tree is the set of all finite strings in the alphabet , including the empty string , which roots. For a vertex of the string is the left child of and the string is the right child of in. The group of all automorphisms can thus be thought of as the group of all length-preserving permutations of that also respect the initial segment relation: whenever a string is an initial segment of a string then is an initial segment of.
The Grigorchuk group is the subgroup of generated by four specific elements of defined as follows : where and
Only the element is defined explicitly; it swaps the child trees of. The elements,, and are defined through a mutual recursion.
To understand the effect of the latter operations, consider the rightmost branch of, which begins. As a branch, is order-isomorphic to The original tree can be obtained by rooting a tree isomorphic to at each element of ; conversely, one can decompose into isomorphic subtrees indexed by elements of.
The operations,, and all respect this decomposition: they fix each element of and act as automorphisms on each indexed subtree. When acts, it fixes every subtree with index, but acts as on the rest. Likewise, when acts, it fixes only the subtrees of index ; and fixes those of index.
A compact notation for these operations is as follows: let the left branch of be , so that We write to mean that acts as on and as on. Thus Similarly where is the identity function.

Properties

The following are basic algebraic properties of the Grigorchuk group :