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.\]

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)

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\).

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.

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)}}\).

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)\)

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)\)

Generators of \(\Gamma\)

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\) 

Generators of \(\Gamma\)

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.\)

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.

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\).

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)}. \]

Proof – Case 2.2

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

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 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 \]

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}. \]

Restrictions to Subtrees

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

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}\).

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})\]

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.\]

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)