In the
mathematical
Mathematics is an area of knowledge that includes the topics of numbers, formulas and related structures, shapes and the spaces in which they are contained, and quantities and their changes. These topics are represented in modern mathematics ...
area of
group theory
In abstract algebra, group theory studies the algebraic structures known as group (mathematics), groups.
The concept of a group is central to abstract algebra: other well-known algebraic structures, such as ring (mathematics), rings, field ...
, the Grigorchuk group or the first Grigorchuk group is a
finitely generated group
In algebra, a finitely generated group is a group ''G'' that has some finite generating set ''S'' so that every element of ''G'' can be written as the combination (under the group operation) of finitely many elements of ''S'' and of inverses o ...
constructed by
Rostislav Grigorchuk that provided the first example of a
finitely generated group
In algebra, a finitely generated group is a group ''G'' that has some finite generating set ''S'' so that every element of ''G'' can be written as the combination (under the group operation) of finitely many elements of ''S'' and of inverses o ...
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
John Willard Milnor (born February 20, 1931) is an American mathematician known for his work in differential topology, algebraic K-theory and low-dimensional holomorphic dynamical systems. Milnor is a distinguished professor at Stony Brook Univ ...
in 1968. The Grigorchuk group remains a key object of study in
geometric group theory
Geometric group theory is an area in mathematics devoted to the study of finitely generated groups via exploring the connections between algebraic properties of such group (mathematics), groups and topology, topological and geometry, geometric pro ...
, particularly in the study of the so-called branch groups and automata groups, and it has important connections with the theory of
iterated monodromy group In geometric group theory and dynamical systems the iterated monodromy group of a covering map is a group describing the monodromy action of the fundamental group on all iterations of the covering. A single covering map between spaces is therefore u ...
s.
[Volodymyr Nekrashevych]
''Self-similar groups.''
Mathematical Surveys and Monographs, 117. American Mathematical Society, Providence, RI, 2005. .
History and significance
The
growth of a
finitely generated group
In algebra, a finitely generated group is a group ''G'' that has some finite generating set ''S'' so that every element of ''G'' can be written as the combination (under the group operation) of finitely many elements of ''S'' and of inverses o ...
measures the asymptotics, as
of the size of an ''n''-ball in the
Cayley graph
In mathematics, a Cayley graph, also known as a Cayley color graph, Cayley diagram, group diagram, or color group is a graph that encodes the abstract structure of a group. Its definition is suggested by Cayley's theorem (named after Arthur Cay ...
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 group
In algebra, a finitely generated group is a group ''G'' that has some finite generating set ''S'' so that every element of ''G'' can be written as the combination (under the group operation) of finitely many elements of ''S'' and of inverses o ...
s 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 A covering of a topological space X is a continuous map \pi : E \rightarrow X with special properties.
Definition
Let X be a topological space. A covering of X is a continuous map
: \pi : E \rightarrow X
such that there exists a discrete spa ...
of a
compact
Compact as used in politics may refer broadly to a pact or treaty; in more specific cases it may refer to:
* Interstate compact
* Blood compact, an ancient ritual of the Philippines
* Compact government, a type of colonial rule utilized in British ...
Riemannian manifold in
differential geometry. It is obvious that the growth rate of a finitely generated group is at most
exponential
Exponential may refer to any of several mathematical topics related to exponentiation, including:
*Exponential function, also:
**Matrix exponential, the matrix analogue to the above
*Exponential decay, decrease at a rate proportional to value
*Expo ...
and it was also understood early on that finitely generated
nilpotent group
In mathematics, specifically group theory, a nilpotent group ''G'' is a group that has an upper central series that terminates with ''G''. Equivalently, its central series is of finite length or its lower central series terminates with .
Intui ...
s have polynomial growth. In 1968
John Milnor
John Willard Milnor (born February 20, 1931) is an American mathematician known for his work in differential topology, algebraic K-theory and low-dimensional holomorphic dynamical systems. Milnor is a distinguished professor at Stony Brook Univ ...
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 In geometric group theory, Gromov's theorem on groups of polynomial growth, first proved by Mikhail Gromov, characterizes finitely generated groups of ''polynomial'' growth, as those groups which have nilpotent subgroups of finite index.
Statement ...
, obtained by
Gromov in 1981, which shows that a finitely generated group has polynomial growth if and only if this group has a
nilpotent
In mathematics, an element x of a ring R is called nilpotent if there exists some positive integer n, called the index (or sometimes the degree), such that x^n=0.
The term was introduced by Benjamin Peirce in the context of his work on the cla ...
subgroup
In group theory, a branch of mathematics, given a group ''G'' under a binary operation ∗, a subset ''H'' of ''G'' is called a subgroup of ''G'' if ''H'' also forms a group under the operation ∗. More precisely, ''H'' is a 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 group In mathematics, a matrix group is a group ''G'' consisting of invertible matrices over a specified field ''K'', with the operation of matrix multiplication. A linear group is a group that is isomorphic to a matrix group (that is, admitting a f ...
s,
solvable group
In mathematics, more specifically in the field of group theory, a solvable group or soluble group is a group that can be constructed from abelian groups using extensions. Equivalently, a solvable group is a group whose derived series terminate ...
s, etc.
Grigorchuk's group ''G'' was constructed in a 1980 paper of
Rostislav Grigorchuk,
[R. I. Grigorchuk. ''On Burnside's problem on periodic groups.'' (Russian) Funktsionalyi Analiz i ego Prilozheniya, vol. 14 (1980), no. 1, pp. 53–54.] where he proved that this group is infinite,
periodic and
residually finite {{unsourced, date=September 2022
In the mathematical field of group theory, a group ''G'' is residually finite or finitely approximable if for every element ''g'' that is not the identity in ''G'' there is a homomorphism ''h'' from ''G'' to a fini ...
. In a subsequent 1984 paper
[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.] 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
but slower than
where
. The upper bound was later improved by
Laurent Bartholdi
Laurent may refer to:
*Laurent (name), a French masculine given name and a surname
**Saint Laurence (aka: Saint ''Laurent''), the martyr Laurent
**Pierre Alphonse Laurent, mathematician
**Joseph Jean Pierre Laurent, amateur astronomer, discoverer ...
to
:
A lower bound of
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
.
Grigorchuk's group was also the first example of a group that is
amenable but not
elementary amenable In mathematics, a group is called elementary amenable if it can be built up from finite groups and abelian groups by a sequence of simple operations that result in amenable groups when applied to amenable groups. Since finite groups and abelian gro ...
, 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
Binary may refer to:
Science and technology Mathematics
* Binary number, a representation of numbers using only two digits (0 and 1)
* Binary function, a function that takes two arguments
* Binary operation, a mathematical operation that ta ...
rooted tree
In graph theory, a tree is an undirected graph in which any two vertices are connected by ''exactly one'' path, or equivalently a connected acyclic undirected graph. A forest is an undirected graph in which any two vertices are connected by ''a ...
. 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 group In geometric group theory and dynamical systems the iterated monodromy group of a covering map is a group describing the monodromy action of the fundamental group on all iterations of the covering. A single covering map between spaces is therefore u ...
s, 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
Binary may refer to:
Science and technology Mathematics
* Binary number, a representation of numbers using only two digits (0 and 1)
* Binary function, a function that takes two arguments
* Binary operation, a mathematical operation that ta ...
rooted tree
In graph theory, a tree is an undirected graph in which any two vertices are connected by ''exactly one'' path, or equivalently a connected acyclic undirected graph. A forest is an undirected graph in which any two vertices are connected by ''a ...
''T''
2. The tree ''T''
2 is realized as the set
of all finite strings in the alphabet
plus the empty string
which is the root vertex of ''T''
2. For a vertex ''x'' of ''T''
2 the string ''x''0 is the
left child of ''x'' and the string ''x''1 is the
right child of ''x'' in ''T''
2. The group of all automorphisms Aut(''T''
2) can thus be thought of as the group of all length-preserving
permutations
In mathematics, a permutation of a set is, loosely speaking, an arrangement of its members into a sequence or linear order, or if the set is already ordered, a rearrangement of its elements. The word "permutation" also refers to the act or pr ...
''σ'' of
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
In group theory, a branch of mathematics, given a group ''G'' under a binary operation ∗, a subset ''H'' of ''G'' is called a subgroup of ''G'' if ''H'' also forms a group under the operation ∗. More precisely, ''H'' is a subgroup ...
of Aut(''T''
2)
generated by four specific elements of Aut(''T''
2):
:
where the automorphisms ''a'', ''b'', ''c'', ''d'' are defined as follows (note that
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
has a natural gradation into ''levels'' given by the length of the strings:
:
Now let