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 $n\to \mathrm{\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 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 $\exp (\sqrt{n})$ but slower than $\exp (n^s)$ where $s={\log }_{32}31\approx 0.991$. The upper bound was later improved by Laurent Bartholdi to

$s=\frac{\log 2}{\log 2-\log \eta }\approx 0.7674,{\eta }^3+{\eta }^2+\eta =2.$

A lower bound of $\exp (n^{0.504})$ was proved by Yurii Leonov. It was conjectured that the limit

$\underset{n\to \mathrm{\infty }}{\lim }{\log }_n\log b(n),$

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 $s$.

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 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

The infinite binary tree Template:Math. Its nodes are labeled by strings of 0s and 1s.

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 Template:Math. The tree Template:Math is the set Template:Math of all finite strings in the alphabet Template:Math, including the empty string Template:Math, which roots Template:Math. For a vertex Template:Mvar of Template:Math the string Template:Math is the left child of Template:Mvar and the string Template:Math is the right child of Template:Mvar in Template:Math. The group of all automorphisms Template:Math can thus be thought of as the group of all length-preserving permutations Template:Math of Template:Math that also respect the initial segment relation: whenever a string Template:Mvar is an initial segment of a string Template:Mvar then Template:Math is an initial segment of Template:Math.

The Grigorchuk group Template:Mvar is the subgroup of Template:Math generated by four specific elements of Template:Math defined as follows (note that Template:Math is fixed by any tree-automorphism): $$G=⟨a,b,c,d⟩\le \text{Aut}(T_2)\text{,}$$ where $$a(0)=1\text{,}a(1)=0\text{,}\mathrm{\forall }x\in {\mathrm{\Sigma }}^{*}\{\begin{array}{c}a(0x)=1x\\ a(1x)=0x\end{array}$$ and $$\begin{array}{cc}& b(0)=c(0)=d(0)=0\\ & b(1)=c(1)=d(1)=1\text{,}\end{array}\mathrm{\forall }x\in {\mathrm{\Sigma }}^{*}\begin{array}{cc}& \{\begin{array}{c}b(0x)=0a(x)\\ b(1x)=1c(x)\end{array}\\ & \{\begin{array}{c}c(0x)=0a(x)\\ c(1x)=1d(x)\end{array}\\ & \{\begin{array}{c}d(0x)=0x\\ d(1x)=1b(x)\text{.}\end{array}\end{array}$$

The action of the standard generating set of the Grigorchuk group on the tree T₂. The triangles denote infinite subtrees that remain unchanged.

Only the element Template:Mvar is defined explicitly; it swaps the child trees of Template:Math. The elements Template:Mvar, Template:Mvar, and Template:Mvar are defined through a mutual recursion.

To understand the effect of the latter operations, consider the rightmost branch Template:Mvar of Template:Math, which begins Template:Math. As a branch, Template:Mvar is order-isomorphic to $\mathbb{N}.$ The original tree Template:Math can be obtained by rooting a tree isomorphic to Template:Math at each element of Template:Mvar; conversely, one can decompose Template:Math into isomorphic subtrees indexed by elements of $B\cong \mathbb{N}$.

The operations Template:Mvar, Template:Mvar, and Template:Mvar all respect this decomposition: they fix each element of Template:Mvar and act as automorphisms on each indexed subtree. When Template:Mvar acts, it fixes every subtree with index Template:Math, but acts as Template:Mvar on the rest. Likewise, when Template:Mvar acts, it fixes only the subtrees of index Template:Math; and Template:Mvar fixes those of index Template:Math.

A compact notation for these operations is as follows: let the left (resp. right) branch of Template:Math be Template:Math (resp. Template:Math), so that $$a(T_L)\subseteq T_R,a(T_R)\subseteq T_L\text{.}$$ We write Template:Math to mean that Template:Mvar acts as Template:Mvar on Template:Math and as Template:Mvar on Template:Math. Thus $$\begin{array}{cc}b=(a,c)& ⟺b(x)=\{\begin{array}{cc}a(x)& x\in T_L\\ c(x)& x\in T_R\end{array}\\ c=(a,d)& ⟺c(x)=\{\begin{array}{cc}a(x)& x\in T_L\\ d(x)& x\in T_R\end{array}\\ d=(\text{id},b)& ⟺d(x)=\{\begin{array}{cc}x& x\in T_L\\ b(x)& x\in T_R\text{.}\end{array}\end{array}$$ Similarly $$aba=(c,a),aca=(d,a),ada=(b,\text{id})\text{,}$$ where Template:Math is the identity function.

Properties

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

• The group G is infinite.
• The group G is residually finite. Let ${\rho }_n:G\to \text{Aut}(T[n])$ be the restriction homomorphism that sends every element of G to its restriction to the first Template:Mvar levels of Template:Math. The groups Aut(T[n]) are finite and for every nontrivial g in G there exists n such that ${\rho }_n(g)\ne 1.$
• The group G is generated by a and any two of the three elements b,c,d. For example, we can write $G=⟨a,b,c⟩.$
• The elements a, b, c, d are involutions.
• The elements b, c, d pairwise commute and bc = cb = d, bd = db = c, dc = cd = 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.
• Combining the previous two properties we see that 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.
• The group G is a 2-group, that is, every element in G has finite order that is a power of 2.
• The group G is periodic (as a 2-group) and not locally finite (as it is finitely generated). As such, it is a counterexample to the Burnside problem.
• The group G has intermediate growth.
• The group G is amenable but not elementary amenable.
• The group G is just infinite, that is G is infinite but every proper quotient group of G is finite.
• The group G has the congruence subgroup property: a subgroup H has finite index in G if and only if there is a positive integer n such that $\ker ({\rho }_n)⩽H.$
• The group G has solvable subgroup membership problem, that is, there is an algorithm that, given arbitrary words w, u₁, ..., u_n decides whether or not w represents an element of the subgroup generated by u₁, ..., u_n.
• The group G is subgroup separable, that is, every finitely generated subgroup is closed in the pro-finite topology on G.
• Every maximal subgroup of G has finite index in G.
• The group G is finitely generated but not finitely presentable.
• The stabilizer of the level one vertices in $T_2$ in G (the subgroup of elements that act as identity on the strings 0 and 1), is generated by the following elements:

$G_{\{0,1\}}=⟨b,c,d,aba,aca,ada⟩.$

$G_{\{0,1\}}$ is a normal subgroup of index 2 in G and

$G=G_{\{0,1\}}\bigsqcup a{G}_{\{0,1\}}.$

• A reduced word represents an element of $G_{\{0,1\}}$if and only if this word involves an even number of occurrences of a.
• If w is a reduced word in G with a positive even number of occurrences of a, then there exist words u, v (not necessarily reduced) such that:

$w=(u,v)\text{and}\{\begin{array}{cc}|u|,|v|⩽\frac{1}{2}|w|& |w|\text{ odd}\\ |u|,|v|⩽\frac{1}{2}(|w|+1)& |w|\text{ even}\end{array}$

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

• The group G has solvable word problem and solvable conjugacy problem (consequence of the contraction property).

See also

• Geometric group theory
• Growth of finitely generated groups
• Amenable groups
• Iterated monodromy group
• Non-commutative cryptography

External links

• Rostislav Grigorchuk and Igor Pak, Groups of Intermediate Growth: an Introduction for Beginners, preprint, 2006, arXiv