# The First Grigorchuk Group

in Context of Burnside's Problems

28 April 2017

# Burnside's Problems

## Periodic Groups

### Definition

A group $$G$$ is called periodic if for each element $$a \in G$$ there exists an integer $$n > 0$$ such that $a^n = e.$

### Examples

• Every finite group is periodic.
• The direct sum of cyclic groups $\bigoplus_{i=2}^\infty \operatorname{\mathbb{Z}}_i$ is periodic.

## Unbounded Burnside Problem

A still undecided problem in the theory of discontinuous groups is whether the order of a group may be not finite while the order of every operation it contains is finite.
Burnside (1902)

### Common Interpretation

Is every finitely generated, periodic group finite?

## Special Case: Abelian Groups

If the group $$G$$ is assumed to be abelian then the answer to UBP is affirmative since $G\cong\operatorname{\mathbb{Z}}^n \oplus \operatorname{\mathbb{Z}}_{q_1} \oplus \cdots \oplus \operatorname{\mathbb{Z}}_{q_t}$ by the fundamental theorem of finitely generated abelian groups.

## Groups with Exponent

### Definition

If there exists a positive integer $$N$$, such that $a^N = e$ for all elements $$a$$ of a group $$G$$, we say $$G$$ is of exponent $$N$$.

### Example

Let $$\operatorname{\mathbb{F}}_2$$ be the field of order $$2$$. Then the polynomials $$\mathbb F_2[X]$$ over $$\operatorname{\mathbb{F}}_2$$ form a group of exponent $$2$$ w. r. t. addition.

## Bounded Burnside Problem

Let $${A_1,\ldots, A_{m}}$$ be a set of independent operations finite in number, and suppose that they satisfy the system of relations given by $S^n=1$ where $$n$$ is a given integer, while $$S$$ represents in turn any and every operation which can be generated from the m given operations $$A$$.

Is the group thus defined one of finite order, and if so what is its order?
Burnside (1902)

## Special Case: Exponent $$2$$

If the group is of exponent $$2$$ then it is abelian since

$ab = (ab)^{-1} = ba.$

The answer to BBP is affirmative by the fundamental theorem of finitely generated abelian groups.

# Graphtheoretical Preliminaries

## Graphs

A (simple) graph is a pair of two sets $$(V,E)$$, where $$V$$ is non-empty and $$E$$ is a subset of all unordered pairs $$\lbrace v_1,v_2\rbrace\in\mathcal{P}(V)$$ that fulfil $$v_1\neq v_2$$. The set $$V$$ is called the vertex set and $$E$$ the edge set of the graph $$(V,E)$$.

## Graph-Automorphisms

• Let $$G = (V, E)$$ be a graph. A mapping $$\varphi \colon V \to V$$ is called graph-automorphism of $$G$$ if $\lbrace v_1,v_2\rbrace\in E \Leftrightarrow \lbrace \varphi(v_1),\varphi(v_2)\rbrace\in E$
• The set $$\operatorname{\mathrm{Aut}}(G)$$ of all automorphisms of $$G$$ forms a group w. r. t. composition.

## The Full Binary Tree $${T^{(2)}}$$

The full binary tree is the graph $${T^{(2)}}:= \left({V\left({T^{(2)}}\right)}, {E\left({T^{(2)}}\right)}\right)$$ where ${V\left({T^{(2)}}\right)}:= \lbrace ({b_1,\ldots, b_{n}}) \mid {b_1,\ldots, b_{n}} \in \lbrace{0, 1\rbrace}, n \geq 0 \rbrace$ and two vertices are adjacent if the longer sequence can be obtained by concatenating $$0$$ or $$1$$ to the shorter sequence.

## The Full Binary Tree $${T^{(2)}}$$

The red vertex is identified with the sequence $$(0, 0, 1, 1)$$.

## Subtrees of $${T^{(2)}}$$

The induced subgraph of $${T^{(2)}}$$ containing all sequences that extend $$({b_1,\ldots, b_{n}}) \in {T^{(2)}}$$ is denoted by $${{T^{(2)}}_{({b_1,\ldots, b_{n}})}}$$.

## Levels of $${T^{(2)}}$$

• The vertex $$({b_1,\ldots, b_{n}})$$ is on level $$n$$.
• We note $$| ({b_1,\ldots, b_{n}}) | = n$$ and $\mathrm{L}(k):=\left\lbrace v\in{V\left({T^{(2)}}\right)}\middle\vert \lvert v\rvert=k\right\rbrace$

## Automorphisms of $${T^{(2)}}$$

### Proposition

Let $$\varphi\in{\operatorname{\mathrm{Aut}}\left({T^{(2)}}\right)}$$. Then

• $$\varphi$$ fixes the root, i. e., $\varphi(\emptyset) = \emptyset$ and
• $$\varphi$$ fixes the levels, i. e., $\lvert \varphi(v)\rvert=\lvert v\rvert,\quad\forall v\in{V\left({T^{(2)}}\right)}.$

## Action of $${\operatorname{\mathrm{Aut}}\left({T^{(2)}}\right)}{}$$ on $$\mathrm{L}(k)$$

By enumerating the vertices on level $$k$$ via $$\beta_k({b_1,\ldots, b_{k}}) := 1+\sum_{i=1}^{k} b_i2^{k-i},$$ one obtains a group-homomorphism

$p_k \colon {\operatorname{\mathrm{Aut}}\left({T^{(2)}}\right)}\to \mathfrak{S}_{2^k}.$

## Stabiliser Groups

### Definition

The normal subgroup $${\mathrm{St}_{}(k)}=\ker(p_k)$$ of the automorphism group $${\operatorname{\mathrm{Aut}}\left({T^{(2)}}\right)}$$ is called $$k$$-th stabiliser group of $${T^{(2)}}$$.

### Remark

$${\mathrm{St}_{}(k)}$$ preserves the first $$k + 1$$ levels of $${T^{(2)}}$$ pointwise.

## Restrictions to Subtrees

### Lemma

The mapping

$\psi\colon{\mathrm{St}_{}(1)}\to{\operatorname{\mathrm{Aut}}\left({T^{(2)}}\right)}\times{\operatorname{\mathrm{Aut}}\left({T^{(2)}}\right)}$

defined by

$\varphi\mapsto\left(\varphi\big\vert_{{{T^{(2)}}_{(0)}}},\varphi\big\vert_{{{T^{(2)}}_{(1)}}}\right)$

is an isomorphism of groups.

$$\psi$$ identifies an automorphism with its restrictions to $${{T^{(2)}}_{(0)}}$$ and $${{T^{(2)}}_{(1)}}$$.

## First Grigorchuk Group

### Definition

• One defines the automorphisms $$a, b, c$$ and $$d \in {\operatorname{\mathrm{Aut}}\left({T^{(2)}}\right)}$$ as follows
$$a({b_1,\ldots, b_{n}}) := (1-b_1, b_2, \ldots, b_n)$$ and recursively
$$b := \psi^{-1}(a, c),$$
$$c := \psi^{-1}(a, d)$$ as well as
$$d := \psi^{-1}(\operatorname{id}, b).$$
• The first Grigorchuk group is defined as $\Gamma := \langle a, b, c, d \rangle \subseteq {\operatorname{\mathrm{Aut}}\left({T^{(2)}}\right)}.$

## Automorphism $$c$$

$$\psi(c) = (a, d)$$

$$c(1, 1, 0, 0) = (1, d(1, 0, 0))$$

## Automorphism $$c$$

$$\psi(c) = (a, d)$$, $$\psi(d) = (\operatorname{id}, b)$$

$$c(1, 1, 0, 0) = (1, d(1, 0, 0)) = (1, 1, b(0, 0))$$

## Automorphism $$c$$

$$\psi(c) = (a, d)$$, $$\psi(d) = (\operatorname{id}, b)$$ and $$\psi(b) = (a, c)$$

$$c(1, 1, 0, 0) = (1, d(1, 0, 0)) = (1, 1, b(0, 0)) = (1, 1, 0, a(0))$$

## Automorphism $$c$$

$$\psi(c) = (a, d)$$, $$\psi(d) = (\operatorname{id}, b)$$ and $$\psi(b) = (a, c)$$

$$c(1, 1, 0, 0) = (1, d(1, 0, 0)) = (1, 1, b(0, 0)) = (1, 1, 0, a(0)) = (1, 1, 0, 1)$$

## Identities of the Generators

### Proposition

• The generators are of order $$2$$, i. e., $a^2 = b^2 = c^2 = d^2.$
• Three generators suffice since
$$bc = cb = d, bd = db = c$$ and $$cd = dc = b$$

## Word Length

As a consequence of the proposition, each $$\gamma \in \Gamma$$ can be written as

$\gamma=u_0au_1au_2a\ldots u_lau_{l+1},$

where $$u_1\ldots u_{l}\in\lbrace b,c,d\rbrace$$ and $$u_0,u_{l+1}\in\lbrace \operatorname{id},b,c,d\rbrace.$$

### Notation

The number of generators appearing in the shortest representation of $$\gamma$$ as a word of the form above is denoted by $$\ell(\gamma)$$.

# A Counterexample to the Unbounded Burnside Problem

## Stabiliser Groups Revisited

One defines $${\mathrm{St}_{\Gamma}(k)} := {\mathrm{St}_{}(k)} \cap \Gamma.$$

### Lemma

Let $$\gamma=u_0au_1a\ldots u_lau_{l+1}.$$ Then $$\gamma \in {\mathrm{St}_{\Gamma}(1)}$$ iff $$l$$ is odd.

### Lemma

Let $$\psi\colon{\mathrm{St}_{}(1)}\to{\operatorname{\mathrm{Aut}}\left({T^{(2)}}\right)}^2$$ be defined as before. Then

$\psi(aba) = (c, a),$ $\psi(aca) = (d, a),$ $\psi(ada) = (b, \operatorname{id}).$

## $$\Gamma$$ is Infinite

### Theorem

The mapping $$\psi_\mathrm{right}\colon{\mathrm{St}_{\Gamma}(1)}\to\Gamma$$, defined by

$\psi_\mathrm{right}(\gamma)=\gamma_2$

if $$\psi(\gamma)=(\gamma_1,\gamma_2)$$, is an epimorphism of groups.

## Dihedral Subgroups

### Lemma

$$\Gamma$$ contains the following subgroups isomorphic to an dihedral group

• $$\langle a,d\rangle\cong\operatorname{D}_4$$,
• $$\langle a,c\rangle\cong\operatorname{D}_8$$ and
• $$\langle a,b\rangle\cong\operatorname{D}_{16}$$.

## $$\Gamma$$ is periodic

### Theorem

The first Grigorchuk group $$\Gamma$$ is a $$2$$-group, i. e., for each automorphism $$\gamma\in\Gamma$$ there exists a non-negative integer $$n$$ such that

$\gamma^{2^n}=\operatorname{id}.$

## Proof by Induction on the Length

• If $$\ell(\gamma) = 0$$ then $$\gamma = \operatorname{id}$$.
• If $$\ell(\gamma) = 1$$ then $$\gamma \in \lbrace a, b, c, d \rbrace$$.
• If $$\ell(\gamma) = 2$$ then $$\gamma ^ {16} = \operatorname{id}$$ by the lemma above.

Hence, one may assume $$k := \ell(\gamma) > 2$$ and the claim to be proven for all automorphisms of smaller length.

## Proof – Case 1

If $$\ell(\gamma)$$ is odd then

• $$\gamma = au_1a\ldots u_la$$ or
• $$\gamma = u_0au_1a\ldots u_lau_{l+1}$$

for some $$u_0,\ldots u_{l+1}\in\lbrace b,c,d\rbrace$$.

## Proof – Case 2

If $$\ell(\gamma)$$ is even then w. l. o. g. one may assume

$\gamma = a u_1 a \ldots u_l \qquad(1)$

where $$l = \frac{\ell(\gamma)}{2}$$ and $${u_1,\ldots, u_{l}} \in \lbrace b, c, d \rbrace$$.

### Remark

The word in eq. 1 does contain $$l$$ letters ‘$$a$$’.

## Proof – Case 2.1

If $$l$$ is even then in the word representing $$\gamma$$ an even number of letters ‘$$a$$’ is contained. Hence, $\gamma \in {\mathrm{St}_{\Gamma}(1)}.$

We have

$(\gamma_1, \gamma_2) := \psi(\gamma) = \psi(au_1 a u_2 a\ldots u_l) =\psi(au_1 a)\psi(u_2)\ldots\psi(au_{l-1}a)\psi(u_l)$

and therefore $$\ell(\gamma_1), \ell(\gamma_2) \leq l$$.

## Proof – Case 2.2

If $$l$$ is odd then $$\gamma^2 \in {\mathrm{St}_{\Gamma}(1)}$$.

Therefore, $(\alpha,\beta) := \psi(\gamma^2)=\psi(au_1 a u_2 a\ldots u_lau_1 a u_2 a\ldots u_l)=$ $=\psi(au_1 a)\psi(u_2)\ldots\psi(au_{l-2}a)\psi(u_{l-1})\psi(au_l a)\psi(u_1)\ldots\psi(au_{l-1}a)\psi(u_l)$

## Proof – Case 2.2

1. If $$\gamma$$ contains a ‘$$d$$’ then $$\alpha$$ and $$\beta$$ are at most of length $$\ell(\gamma) - 1$$.
2. If $$\gamma$$ contains a ‘$$c$$’ then $$\alpha$$ and $$\beta$$ contain a ‘$$d$$’.
3. If neither is the case then $$\gamma \in \langle a, b \rangle \cong \operatorname{D}_{16}$$.

# Growth of the First Grigorchuk Group

## Growth of the Orders of Automorphisms

### Definition

The set of all orders of automorphisms of length at most $$k$$ is denoted $O_k := \lbrace ord(\gamma) \mid \gamma\in\Gamma, \ell(\gamma) \leq k \rbrace$

The growth function is defined as $o(k) = \max(O_k)$

### Remark

Since $$O_k \subseteq O_{k + 1}$$, the growth function is monotonically increasing.

## Upper Bounds for the Growth of $$\Gamma$$

### Corollary

The growth of $$\Gamma$$ is bound by an exponential function. More precisely,

$o(k)\leq 2^{\frac{1}{2}k+3}.$

### Remark

This is far from optimal. Bartholdi and Šunić (2006) proved that $o(k)\leq 4k^2+1.$

## Restrictions to Subtrees

Recall the enumerating function $$\beta_k({b_1,\ldots, b_{k}}) := 1+\sum_{i=1}^{k} b_i2^{k-i}.$$

### Definition

Let $$k\geq 1$$ be an integer. We define $\psi_k\colon{\mathrm{St}_{\Gamma}(k)}\to\Gamma^{2^k}$ by $\gamma\mapsto\left(\gamma\big\vert_{{{T^{(2)}}_{\beta_k^{-1}(1)}}},\gamma\big\vert_{{{T^{(2)}}_{\beta_k^{-1}(2)}}},\ldots,\gamma\big\vert_{{{T^{(2)}}_{\beta_k^{-1}(2^k)}}}\right).$

## Restrictions to Subtrees

### Example

$\psi_2(d) = (\operatorname{id}, \operatorname{id}, a, c)$

## One Technical Lemma

### Lemma

Let $$K$$ denote the normal subgroup of $$\Gamma$$ generated by $$(ab)^2$$.

1. $${\mathrm{St}_{\Gamma}(3)} \subseteq K \subseteq {\mathrm{St}_{\Gamma}(1)}$$
2. For each integer $$k\geq 1$$, the image $$\psi_k\left({\mathrm{St}_{\Gamma}(k)}\right)$$ contains $$K^{2^k}$$.

### Remark

Note that the second assertion is very strong:

$$\pi_1 \circ \psi_1$$ and $$\pi_2 \circ \psi_1$$ are automorphisms of $$\Gamma$$ but $$(a, a) \not\in \psi_1(\Gamma)$$.

## Final Lemma

### Lemma

Let $$n$$ be a positive integer. Given an automorphism $$\gamma\in K$$, such that $$\operatorname{ord}(\gamma)\geq 2^n$$, we find an automorphism $$\eta\in K$$ satisfying

$\operatorname{ord}(\eta)\geq 2^{n+1}.$

## Proof

By the lemma above there exists an automorphism $$h\in{\mathrm{St}_{\Gamma}(5)}\subseteq K$$, such that

$\psi_5(h)=(\gamma,\operatorname{id},\ldots,\operatorname{id})$

We set $$\eta:=(ab)^8h$$. A short calculation shows

$\psi_5\left(\eta^2\right)=(\gamma,\gamma,\operatorname{id},\ldots,\operatorname{id})\in{\mathrm{St}_{\Gamma}(1)}^{32}.$

## Infinite Growth

### Theorem

Let $$n$$ be a positive integer. There exists an automorphism $$\gamma_{n}\in K\subseteq\Gamma$$, such that

$\operatorname{ord}(\gamma)\geq 2^n.$

# Thank you for your attention

## History and Variants

For a brief exposition on variants and the history of Burnside's problems please visit https://tim6her.github.io/FirstGrigorchukGroup/history.html. (German)

## References

Bartholdi, L., and Z. Šunić. 2006. “Some Solvable Automaton Groups.” In Topological and Asymptotic Aspects of Group Theory, 394:11–29. Contemp. Math. Amer. Math. Soc., Providence, RI.

Burnside, W. 1902. “On an Unsettled Question in the Theory of Discontinuous Groups.” Quarterly Journal of Pure and Applied Math 33.