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 $xinA$, 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{array}{ll}2{\beta}_{i},& {\beta}_{i}>0,\\ -2{\beta}_{i}+1,& {\beta}_{i}<0.\end{array}$$

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 \stackrel{.}{-}\lfloor \lfloor {z}^{\frac{1}{2}}{\rfloor}^{\frac{1}{2}}{\rfloor}^{2}\\ L(z)& =& z\stackrel{.}{-}\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 $\le 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.

## Results

**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\to K\to F\to G\to 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\ge 3$. Assume ${H}_{a}leq{G}_{a}$ are ${E}_{n}(A)$ decidable subgroups and $\varphi :{H}_{1}\to {H}_{2}$ is an isomorphism such that $phi$ and $ph{i}^{-1}$ are ${E}_{n}(A)$ computable. Then $G={G}_{1}\underset{\varphi}{\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\to 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}_{1}{w}_{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}\varphi ({w}_{i}){w}_{i+1}$. If ${w}_{i}in{H}_{2}$, replace it and its neighbours with ${w}_{i-1}{\varphi}^{-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 $\varphi $ and ${\varphi}^{-1}$ might increase the index of our word, so the recursion is unbounded. Hence, the kernel of $F\to 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!

## References

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.