Article

# Grigortschuk Group

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.

## Construction

Binary trees

Notations: The corners of the binary tree

${displaystyle T}$

T

{displaystyle T}

are described by finite sequences of elements from

${displaystyle left{0,1right}}$

{

0
,
1

}

{displaystyle left{0,1right}}

. Be

${displaystyle T_{0}}$

T

0

{displaystyle T_{0}}

respectively

${displaystyle T_{1}}$

T

1

{displaystyle T_{1}}

the subtrees from those sequences that start with 0 or 1. The mappings

${displaystyle delta _{0}colon Tto T_{0}}$

δ

0

:
T

T

0

{displaystyle delta _{0}colon Tto T_{0}}

respectively

${displaystyle delta _{1}colon Tto T_{1}}$

δ

1

:
T

T

1

{displaystyle delta _{1}colon Tto T_{1}}

form a sequence

${displaystyle x}$

x

{displaystyle x}

on concatenation

${displaystyle 0x}$

0
x

{displaystyle 0x}

respectively

${displaystyle 1x}$

1
x

{displaystyle 1x}

ab. For two automorphisms

${displaystyle g_{0},g_{1}colon Tto T}$

g

0

,

g

1

:
T

T

{displaystyle g_{0},g_{1}colon Tto T}

be

that automorphism which is based on

${displaystyle T_{0}}$

T

0

{displaystyle T_{0}}

through

${displaystyle delta _{0}g_{0}delta _{0}^{-1}}$

δ

0

g

0

δ

0

– −
1

{displaystyle delta _{0}g_{0}delta _{0}^{-1}}

and on

${displaystyle T_{1}}$

T

1

{displaystyle T_{1}}

through

${displaystyle delta _{1}g_{1}delta _{1}^{-1}}$

δ

1

g

1

δ

1

– −
1

{displaystyle delta _{1}g_{1}delta _{1}^{-1}}

acts and, like any automorphism, leaves the root fixed. Furthermore we use the terms

${displaystyle {overline {0}}=1}$

0
¯

=
1

{displaystyle {overline {0}}=1}

and

${displaystyle {overline {1}}=0}$

1
¯

=
0

{displaystyle {overline {1}}=0}

.

The Grigortschuk group is then that of the following four automorphisms

${displaystyle a,b,c,dcolon Tto T}$

a
,
b
,
c
,
d
:
T

T

{displaystyle a,b,c,dcolon Tto T}

generated subgroup

${displaystyle Gamma subset mathrm {Aut} (T)}$

Γ

A
u
t

(
T
)

{displaystyle Gamma subset mathrm {Aut} (T)}

:

An example of recursive computation of generating automorphisms is

## Group growth

John Milnor asked in 1968 whether every finitely generated group has either exponential growth or polynomial growth.[1] Rostyslav Hryhorchuk proved in 1984 that the group later named after him has subexponential growth but not polynomial growth.[2] Currently, the best proven estimates are

as lower barrier and

(whereas

${displaystyle eta }$

η

{displaystyle eta }

the real solution of

${displaystyle eta ^{3}+eta ^{2}+eta =2}$

η

3

+

η

2

+
η
=
2

{displaystyle eta ^{3}+eta ^{2}+eta =2}

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

${displaystyle n}$

n

{displaystyle n}

from the one-element.

## Indirectness

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.[3] 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.

## Literature

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