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.