in Context of Burnside's Problems

Tim B. Herbstrith

28 April 2017

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

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

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)

Is every finitely generated, periodic group finite?

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.

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

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.

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)

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.

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

- 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* 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 red vertex is identified with the sequence \((0, 0, 1, 1)\).

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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.

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

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

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

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

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

The word in eq. 1 does contain \(l\) letters ‘\(a\)’.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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.