Grigorchuk's group

In a previous post we constructed a rather intricate counterexample to the Generalized Burnside Problem using the Golod-Shafarevich criterion for the infinite dimensionality of algebras.
In this post, we will look at a famous group introduced by Grigorchuk which will also be a counterexample to the generalized Burnside problem. Namely, it will be an infinite, finitely generated, $2$-group. The construction is amazingly elementary.

Start with an infinite rooted binary tree $T$, which we visualize growing downward.

         

The non-root nodes of the tree are in 1-1 correspondence with finite sequences of $0$'s and $1$'s. $0$ means head left while $1$ means head right.  The Grigorchuk group $G$ is a subgroup of the automorphism group of $T$. Let $a\in\mathrm{Aut}(T)$ be the involution which exchanges the left and right branches of the tree. On the level of finite bitstrings, it just flips the first bit. We define three other automorphisms $b$, $c$, and $d$ as follows:

    So each of $b,c,d$ fixes the rightmost chain of nodes and alternates acting by $a,a,1$ on the sequence of trees branching off to the left.

If an automorphism fixes the two nodes adjacent to the root, it can be written as a pair of autmorphisms $(x,y)$, each acting on a tree isomorphic to $T$. In other words, let $\mathrm{stab}_1$ denote the group of automorphisms fixing the two nodes of distance $1$ from the root. Then $\mathrm{stab}_1\cong \mathrm{Aut}(T)\times \mathrm{Aut}(T)$. With this convention, we see that $$b=(a,c), c=(a,d), d=(1,b).$$ Moreover one can take these as recursive definitions for $b,c,d$! It is easy to see that $\{1,b,c,d\}$ form a Klein 4-group.

Definition: Grigorchuk's group $G$ is the subgroup of $\mathrm{Aut}(T)$ generated by $\{a,b,c,d\}$.

By definition, $G$ is finitely generated. We also want so show that it is infinite and torsion.

To see that it is infinite, calculate $aba=(c,a), aca=(d,a)$ and $ada=(b,1)$. Thus $H=\mathrm{stab}_1\cap G$ contains elements with $a,b,c,d$ as their first coordinates. So $H$ surjects onto $G$ itself. But $H$ is a proper subgroup of $G$ (in fact index $2$) so the only way this could happen is if $G$ is infinite.

Now we show that $G$ is a torsion group. Any element of $G$ can be written as a product of generators which alternate between $a$ and non-$a$ letters. Moreover any such word is conjugate to one which begins with $a$ and ends with a non-$a$ letter. So consider a word
$$g=au_1au_2\ldots au_k,$$ where $u_i\in\{b,c,d\}$. We proceed by induction on the length $2k$. (If $k=1$, it is not hard to check that $ab,ac,ad$ are all torsion.) We consider two cases: $k$ even and $k$ odd. If $k$ is even, then $g\in\mathrm{stab}_1$, so we can write $g=(x,y)$. But $x$ and $y$ are now both words of length $\leq k$. For example, $$abac=(aba)c=(c,a)(a,d)=(ca,ad).$$ So we have reduced to a smaller case. Now suppose that $k$ is odd. Then $g\not\in\mathrm{stab}_1$, so we can't quite do the same thing. However $g^2\in\mathrm{stab}_1$. Now $g^2=(x,y)$ where $x$ and $y$ have length $\leq|g|$, so it doesn't look like we've made progress. However, if $d$ appears as one of the letters, then the length of each $x,y$ does go down. For example, if $g=abacad$, then
$\begin{align*} g^2&=(aba)c(ada)b(aca)d\\ &=(c,a)(a,d)(b,1)(a,c)(d,a)(1,b)\\ &=(cabad,adcab) \end{align*}$
The point is that $d$ appears (at least) twice and parity considerations show that it puts a copy of $1$ into the first and second coordinates. Thus $g^2$ is torsion, and hence so is $g$, by induction.

If $d$ doesn't appear in $g$, then similar parity considerations will show that every appearance of $b$ in $g$ will put a copy of $c$ into $x$ and $y$, while every appearance of $c$ will put a copy of $d$ into $x$ and $y$. That is $g^2=(x,y)$ where $x$ and $y$ now have either a $c$ or $d$ in both. If there is a $d$, then $x$ and $y$ are both torsion, and so therefore is $g^2$ and $g$. If there is a $c$, then $$g^4=(x^2,y^2)=((\alpha_1,\alpha_2),(\alpha_3,\alpha_4)),$$ where $d$ appears in each $\alpha_i$, so $g^4$ is torsion here as well.

Thus we have shown that $G$ is torsion (in fact a $2$-group)!