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.

En computable groups

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

We can also add the characteristic function (( cA such that cA(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 cA, the characteristic function of the set A, to our hierarchy, then we say a function (or group) is En(A) computable ((or “En computable relative to A)) if it can be obtained from composition and bounded recursion on En functions and cA.

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α1β1xα2β2xαnβn,


Where pi is the ith 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 bi deals with negative powers:


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


Where z12 is the integer square root of z, that is, the smallest integer whose square is 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 E3 computable.


Theorem. For every countable group G there exists AN such that G is an E3(A) group.

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

Theorem. If G is finitely generated and En(A) computable then G is En+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 G1,G2 be En(A) standard groups for n3. Assume HaleqGa are En(A) decidable subgroups and ϕ:H1H2 is an isomorphism such that phi and phi1 are En(A) computable. Then G=G1ϕG2 is En+1(A) standard.

Proof. Suppose we have a word on the free group F=F1F2. We want to recognise the kernel of the homomorphism FG with an En+1(A) function.

Split the word into ‘syllables’ – subwords which alternate between being elements of G1 and G2,


If n=1, then w is trivial if and only if it is trivial in G1 or G2 (En decidable).

Otherwise, find a syllable wi which belongs to H1 or H2 (En decidable). If wiinH1, replace it and its neighbours with wi1ϕ(wi)wi+1. If wiinH2, replace it and its neighbours with wi1ϕ1(wi)wi+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 ϕ and ϕ1 might increase the index of our word, so the recursion is unbounded. Hence, the kernel of FG is En+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.

Cannonito, FB, and RW Gatterdam. “The Computability of Group Constructions. Part 1” (1972).