Right, so I’ve written about computable groups and the Grzegorczyk hierarchy previously. Now it’s time to join the two together so we can talk about the computational complexity of certain groups.

$E_n$ computable groups

Let $G$ be a group with an admissible index $i$ and corresponding multiplication function $m$. If $i(G)$ is $E_n$ decidable (( there is an $E_n$ computable function which returns $1$ on numbers which are indices of elements of $G$, and $0$ otherwise )) and $m$ is $E_n$ computable, then $G$ is said to be $E_n$ computable.

We can also add the characteristic function (( $c_A$ such that $c_A(x) = 1$ if $x in A$, and $0$ otherwise )) of a particular set to the primitive functions in the Grzegorczyk hierarchy to make some arguments about group computability easier. If we have $c_A$, the characteristic function of the set $A$, to our hierarchy, then we say a function (or group) is $E_n(A)$ computable ((or “$E_n$ computable relative to $A$”)) if it can be obtained from composition and bounded recursion on $E_n$ functions and $c_A$.

A standard index

Cannonito’s first paper relied on a particular construction of indices for its results. The second paper, with Gatterdam, gave a slightly nicer-looking standard index and dealt with the situation where nothing is known about how the index works. Here’s the nice standard index for a countably-generated group:

Given a word $w = x_{\alpha_1}^{\beta_1}x_{\alpha_2}^{\beta_2} \dots x_{\alpha_n}^{\beta_n}$,

\[ i(w) = \prod_{i=1}^n p_i^{J(\alpha_i,b_i)} \]

Where $p_i$ is the $i$th prime number, $J$ is a pairing function (( I think I need to do a post on coding functions at some point )) combining two numbers into one, and $b_i$ deals with negative powers:

\[  b_i = \begin{cases} 2\beta_i, & \beta_i \gt 0, \\ -2\beta_i + 1,& \beta_i \lt 0. \end{cases} \]

I need to define a pairing function, and unpairing functions to go with it. Here we go:

\[ \begin{array}{rcl} J(x,y) &=& ( (x+y)^2+x)^2+y \\ K(z) &=& \lfloor z^{\frac{1}{2}} \rfloor \overset{.}{-} \lfloor \lfloor z^{\frac{1}{2}} \rfloor^{\frac{1}{2}} \rfloor^2 \\ L(z) &=& z \overset{.}{-} \lfloor z^{\frac{1}{2}} \rfloor^2 \end{array} \]

Where $\lfloor z^{\frac{1}{2}} \rfloor$ is the integer square root of $z$, that is, the smallest integer whose square is $\leq z$.

It takes a little bit of looking to see that $K(J(x,y)) = x$ and $L(J(x,y)) = y$.

The multiplication function for this index is defined by decoding the words represented by the two given indices; concatenating them; then freely reducing the resultant word.

Thanks to this index, every countably-generated free group is $E_3$ computable.


Theorem. For every countable group $G$ there exists $A \subset \mathbb{N}$ such that $G$ is an $E_3(A)$ group.

Proof. There is a short exact sequence $1 \rightarrow K \rightarrow F \rightarrow G \rightarrow 1$. If we let $A = i(K)$, then we can pick as an index for $g \in G$ the smallest element of $F$ which is in the same coset modulo $K$ as $g$.

Theorem. If $G$ is finitely generated and $E_n(A)$ computable then $G$ is $E_{n+1}(A)$ standard.

What this says is that if we don’t have a standard index for a group, we can get one by moving up a level in the hierarchy.

Theorem. Let $G_1, G_2$ be $E_n(A)$ standard groups for $n \geq 3$. Assume $H_a leq G_a$ are $E_n(A)$ decidable subgroups and $\phi: H_1 \rightarrow H_2$ is an isomorphism such that $phi$ and $phi^{-1}$ are $E_n(A)$ computable. Then $G = G_1 \underset{\phi}{\ast} G_2$ is $E_{n+1}(A)$ standard.

Proof. Suppose we have a word on the free group $F = F_1 \ast F_2$. We want to recognise the kernel of the homomorphism $F \rightarrow G$ with an $E_{n+1}(A)$ function.

Split the word into ‘syllables’ – subwords which alternate between being elements of $G_1$ and $G_2$,

\[ w = w_1w_2 \dots w_n \]

If $n = 1$, then $w$ is trivial if and only if it is trivial in $G_1$ or $G_2$ ($E_n$ decidable).

Otherwise, find a syllable $w_i$ which belongs to $H_1$ or $H_2$ ($E_n$ decidable). If $w_i in H_1$, replace it and its neighbours with $w_{i-1} \phi(w_i) w_{i+1}$. If $w_i in H_2$, replace it and its neighbours with $w_{i-1} \phi^{-1}(w_i) w_{i+1}$.

We now have a word with fewer syllables. By induction on the number of syllables, we can decide if $w$ is trivial or not. Note that the use of $\phi$ and $\phi^{-1}$ might increase the index of our word, so the recursion is unbounded. Hence, the kernel of $F \rightarrow G$ is $E_{n+1}(A)$ decidable.

That’ll do for now, I think. They also deal with HNN extensions, which move you up two levels instead of one. The proof is in Gatterdam’s thesis though, so I can’t type it up until I’ve seen it!


Cannonito, Frank B. “Hierarchies of Computable Groups and the Word Problem.” The Journal of Symbolic Logic 31, no. 3 (1966): 376 – 392. http://www.jstor.org/stable/2270453.

Cannonito, FB, and RW Gatterdam. “The Computability of Group Constructions. Part 1” (1972). http://handle.dtic.mil/100.2/AD740603.