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[1] and he then proved in a 1984 paper[2] 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.[3]
History and significance
The growth of a finitely generated group measures the asymptotics, as of the size of an n-ball in the
Grigorchuk's group G was constructed in a 1980 paper of
A lower bound of was proved by Yurii Leonov.[9] 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.[10] They show that the limit equals .
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.[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
After Grigorchuk's 1984 paper, there were many subsequent extensions and generalizations.[13][14][15][16]
Definition
![](http://upload.wikimedia.org/wikipedia/commons/thumb/1/11/T2_tree.svg/200px-T2_tree.svg.png)
Although initially the Grigorchuk group was defined as a group of
The Grigorchuk group G is the
![](http://upload.wikimedia.org/wikipedia/commons/thumb/1/1e/Grigorchuk_group_generators.svg/400px-Grigorchuk_group_generators.svg.png)
Only the element a is defined explicitly; it swaps the child trees of ∅. The elements b, c, and d are defined through a mutual recursion.
To understand the effect of the latter operations, consider the rightmost branch B of T2, which begins {∅, 1, 11, 111, ...}. As a branch, B is
The operations b, c, and d all respect this decomposition: they fix each element of B and act as automorphisms on each indexed subtree. When b acts, it fixes every subtree with index ≡ 2 (mod 3), but acts as a on the rest. Likewise, when c acts, it fixes only the subtrees of index ≡ 1 (mod 3); and d fixes those of index ≡ 0 (mod 3).
A compact notation for these operations is as follows: let the left (resp. right) branch of T2 be TL = 0Σ* (resp. TR = 1Σ*), so that We write f = (g, h) to mean that f acts as g on TL and as h on TR. Thus Similarly where id is the identity function.
Properties
The following are basic algebraic properties of the Grigorchuk group (see[17] for proofs):
- The group G is infinite.[2]
- The group G is residually finite.[2] Let be the restriction homomorphism that sends every element of G to its restriction to the first n levels of T2. The groups Aut(T[n]) are finite and for every nontrivial g in G there exists n such that
- The group G is generated by a and any two of the three elements b,c,d. For example, we can write
- 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 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.[1]
- The group G has intermediate growth.[2]
- The group G is amenable but not elementary amenable.[2]
- 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
- The group G has solvable subgroup membership problem, that is, there is an algorithm that, given arbitrary words w, u1, ..., un decides whether or not w represents an element of the subgroup generated by u1, ..., un.[18]
- The group G is subgroup separable, that is, every finitely generated subgroup is closed in the pro-finite topology on G.[18]
- Every maximal subgroup of G has finite index in G.[19]
- The group G is finitely generated but not
- The stabilizerof the level one vertices in in G (the subgroup of elements that act as identity on the strings 0 and 1), is generated by the following elements:
- is a normal subgroup of index 2 in G and
- A reduced word represents an element of 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:
- 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
References
- ^ 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.
- ^ a b c d e f g 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.
- ISBN 0-8218-3831-8.
- American Mathematical Monthly, vol. 75 (1968), pp. 685–686.
- ^ John Milnor. Growth of finitely generated solvable groups. Archived 2011-05-23 at the Wayback Machine Journal of Differential Geometry. vol. 2 (1968), pp. 447–449.
- ^ Joseph Rosenblatt. Invariant Measures and Growth Conditions, Transactions of the American Mathematical Society, vol. 193 (1974), pp. 33–53.
- Doklady Akademii Nauk SSSR(in Russian). 271 (1): 30–33.
- ^ 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.
- ^ 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.
- ^ Anna Erschler, Tianyi Zheng. "Growth of periodic Grigorchuk groups." Inventiones Mathematicae, vol. 219 (2020), no.3, pp 1069–1155.
- ^ Mahlon M. Day. Amenable semigroups. Illinois Journal of Mathematics, vol. 1 (1957), pp. 509–544.
- ISBN 0-8218-3831-8.
- ^ Roman Muchnik, and Igor Pak. On growth of Grigorchuk groups. International Journal of Algebra and Computation, vol. 11 (2001), no. 1, pp. 1–17.
- ^ Laurent Bartholdi. The growth of Grigorchuk's torsion group. International Mathematics Research Notices, 1998, no. 20, pp. 1049–1054.
- ^ Anna Erschler. Critical constants for recurrence of random walks on G-spaces. Archived 2011-07-25 at the Wayback Machine Université de Grenoble. Annales de l'Institut Fourier, vol. 55 (2005), no. 2, pp. 493–509.
- ^ Jeremie Brieussel, Growth of certain groups Archived 2011-10-02 at the Wayback Machine, Doctoral Dissertation, University of Paris, 2008.
- ISBN 0-226-31719-6; Ch. VIII, The first Grigorchuk group, pp. 211–264.
- ^ Journal of the London Mathematical Society(2), vol. 68 (2003), no. 3, pp. 671–682.
- ^ 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.
- ^ I. G. Lysënok, A set of defining relations for the Grigorchuk group. Matematicheskie Zametki, vol. 38 (1985), no. 4, pp. 503–516.