Skip to main content

Groups and the Grzegorczyk Hierarchy

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.

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

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.