In mathematics, the Grigorchuk group ( Grigorchuk group in English-language publications) is a certain group of automorphisms of a binary tree. It is important in group theory because it provides a counterexample to a number of dichotomies. It is named after Rostislav Ivanovich Grigorchuk.
Notations: The corners of the binary tree
are described by finite sequences of elements from
the subtrees from those sequences that start with 0 or 1. The mappings
form a sequence
ab. For two automorphisms
that automorphism which is based on
acts and, like any automorphism, leaves the root fixed. Furthermore we use the terms
The Grigortschuk group is then that of the following four automorphisms
An example of recursive computation of generating automorphisms is
John Milnor asked in 1968 whether every finitely generated group has either exponential growth or polynomial growth. Rostyslav Hryhorchuk proved in 1984 that the group later named after him has subexponential growth but not polynomial growth. Currently, the best proven estimates are
as lower barrier and
the real solution of
is) as an upper bound fũr the number of group elements which in a Cayley graph of the Grigortschuk group have a distance less than or equal to
from the one-element.
The Grigortschuk group is an indirect group. As early as 1957 Mahlon Day had asked whether every indirect group is elementarily indirect, that is, can be formed from abelian and finite groups by iterated formation of subgroups, factor groups, extensions and inductive limits. Grigorchuk’s group is a counterexample to this.
Properties of the Grigortschuk Group
- The Grigorchuk group is infinite.
- It is finitely generated.
- It is a 2-group, that is, each element has a finite order that is a power of
- It is residually finite.
Chapter VI in: Pierre de la Harpe: Topics in geometric group theory. Chicago Lectures in Mathematics. University of Chicago Press, Chicago, IL, 2000. ISBN 0-226-31719-6; 0-226-31721-8
- K. Waddle: The Grigorchuk group
- J. Milnor: Growth of finitely generated solvable groups. J. Differential Geometry 2 (1968), 447-449.
- R. I. Grigorchuk: Degrees of growth of finitely generated groups and the theory of invariant means. (Russian) Izv. Akad. Nauk SSSR Ser. Mat. 48 (1984), no. 5, 939-985.
- Mahlon M. Day.: Amenable semigroups. Illinois Journal of Mathematics, vol. 1 (1957), pp. 509-544.