Article

Read

Grigortschuk Group

from Wikipedia, the free encyclopedia

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




T


{displaystyle T}

are described by finite sequences of elements from





{

0
,
1

}



{displaystyle left{0,1right}}

. Be





T

0




{displaystyle T_{0}}

respectively





T

1




{displaystyle T_{1}}

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





δ

0


:
T


T

0




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

respectively





δ

1


:
T


T

1




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

form a sequence




x


{displaystyle x}

on concatenation




0
x


{displaystyle 0x}

respectively




1
x


{displaystyle 1x}

ab. For two automorphisms





g

0


,

g

1


:
T

T


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

be

that automorphism which is based on





T

0




{displaystyle T_{0}}

through





δ

0



g

0



δ

0


– −
1




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

and on





T

1




{displaystyle T_{1}}

through





δ

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






0
¯


=
1


{displaystyle {overline {0}}=1}

and






1
¯


=
0


{displaystyle {overline {1}}=0}

.

The Grigortschuk group is then that of the following four automorphisms




a
,
b
,
c
,
d
:
T

T


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

generated subgroup




Γ


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 }

the real solution of





η

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




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

Web links

Individual references

  1. J. Milnor: Growth of finitely generated solvable groups. J. Differential Geometry 2 (1968), 447-449.
  2. 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.
  3. Mahlon M. Day.: Amenable semigroups. Illinois Journal of Mathematics, vol. 1 (1957), pp. 509-544.