---
tag: M0WAT1VQZH
kind: object
name: Grigorchuk group
msc: ["20F50", "20F69", "20E08"]
instance_of: [JZNQTTMG58, HEE922EHQ8]
sources:
  - url: https://en.wikipedia.org/wiki/Grigorchuk_group
same_as:
  wikidata: Q5609013
  wikipedia: Grigorchuk group
---

## Description

Let $\set{0, 1}^*$ be the set of finite words in the letters $0$ and $1$, the vertices of the infinite rooted binary [[tree|062D9KXJB1]].
Define four maps $a, b, c, d$ of $\set{0, 1}^*$ to itself by recursion on the length of a word $w$.
Each map sends the empty word to the empty word, and:
$$a(0w) = 1w, \quad a(1w) = 0w,$$
$$b(0w) = 0\,a(w), \quad b(1w) = 1\,c(w),$$
$$c(0w) = 0\,a(w), \quad c(1w) = 1\,d(w),$$
$$d(0w) = 0w, \quad d(1w) = 1\,b(w).$$
Each map is a bijection that preserves the length of words and the tree structure.
The *Grigorchuk group* $\Gamma$ is the [[group|G5S1M9]] generated by $a, b, c, d$ under composition.

## Remarks

Each generator has order $2$, and $\set{1, b, c, d}$ is a group isomorphic to $\Z/2 \times \Z/2$ with $bc = d$.
$\Gamma$ is infinite, finitely generated, and every element has order a power of $2$, so it answers the general [[Burnside problem|XWEMJ7T2XV]] in the negative.
It is [[residually finite|HEE922EHQ8]]: the action on the words of length $n$ gives finite quotients that separate all elements.
It has [[growth|4CMRM3975W]] faster than every polynomial and slower than every exponential; it was the first group known with this intermediate growth.
It is [[amenable|CEAT9BESKK]] and not finitely presented.

## Explanations

### L1 human

The Grigorchuk group is a group of symmetries of an infinite binary tree, generated by four explicit moves.
The move $a$ swaps the two halves of the tree.
The moves $b$, $c$ and $d$ act on the two halves separately, each time by $a$ or by another of $b$, $c$, $d$, in a repeating pattern.
From these simple rules comes a group with properties that were long thought hard to find together.
It is infinite, every element repeated enough times gives the identity, and its size grows at an unusual speed.