Over Christmas I typed up my Bass-Serre / Grzegorczyk stuff in quite a lot of detail and fairly rigorously. It’s far too much to put up here as blog posts, so here’s a link to the PDF.

The big theorem I prove says that the fundamental group of a graph of $E_n$-computable groups is $E_{n+1}$-computable. But are there cases when the fgoagog stays at $E_n$, and can we pin down what conditions cause it to move up to $E_{n+1}$? I’ve found a couple of examples which begin to answer those questions.

Corollary 1 says that if the edge groups are finitely generated then you don’t go up a level, while Corollary 2 gives an example of a graph with infinitely generated edge groups that does go up a level.

Little Facts

1. The $n$^th prime $p_n\approx n\log n$.
2. $\exp (x,y):=x^y\in E_3$.
3. The Gödel encoding of a word of length $n$ on an alphabet $X$ is $\le p_n^{J(n,n)}$, an $E_3$ function.

Theorem 6.7 (from the paper)

Suppose we have $G={\pi }_1(\mathbf{G},\mathrm{\Gamma },T,v_0)$, where $\mathrm{\Gamma }$ is finite. Suppose all the $G_i\in \mathbf{G}$ are finitely generated $E_n$-computable groups, $n\ge 3$. Assume all the identified subgroups are $E_n$-decidable, and all the isomorphisms ${\varphi }_e$ are $E_n$-computable. Then $G$ is $E_{n+1}$-computable.

Corollary 1

Same assumptions as the Theorem 6.7, but also assume that the edge groups are finitely generated. So each edge homomorphism ${\varphi }_{e_{ij}}$ sends a finitely generated subgroup $E_{ij}\le G_i$ to another finitely generated subgroup $E_{ji}\le G_j$. Suppose everything is $E_n$-computable.

Then $G={\pi }_1(\mathbf{G},\mathrm{\Gamma },T,v_0)$ is $E_n$-computable.

Proof

In the algorithm from Theorem 6.7, the potential for unbounded recursion comes from applying the edge homomorphisms repeatedly. We will show that the result of applying the edge homomorphisms repeatedly is bounded by an $E_3$ function.

Let $w$ be a word on $G$ of length $n$. An upper bound on the number of syllables in $w$ is $n$, so let’s say there are $n$ applications of edge homomorphisms.

A homomorphism ${\varphi }_{e_{ij}}$ rewrites generators $x\in X_i$ as words ${\varphi }_{e_{ij}}(x)\in X_j^{\ast }$. As $G-i$ is finitely generated, there is a word ${\varphi }_{e_{ij}}(x)$ of maximum, finite length $k_{ij}$. So a word $w_i\in E_{ij}$ of length $m$ is rewritten to a word $w_j\in E_j$ of length at most $k_{ij}m$.

Because the graph is finite, we can find a greatest $k\in \{k_{ij}\}$. So after reducing all the syllables (assuming that can be done for the input word), the resulting word in $G_0$ has length at most $k^{n}n=L$.

Hence the index of the resulting word is bounded by

$$p_{k^{n}n}^{J(k^{n}n,k^{n}n)},$$

an $E_3$ function, by Fact 2. So recursion on the edge homomorphisms is bounded by an $E_n$ function, and so $G$ is $E_n$-computable.

$◻$

Corollary 2

We will construct a graph of $E_3$-computable groups whose fundamental group is $E_4$-computable.

Let $\mathbf{G}=\{G_0,G_1\}$ be two copies of the free group on two generators, so $G_0=⟨x,y⟩$ and $G_1=⟨a,b⟩$. The graph has a single edge $e$ from $v_0$ to $v_1$, so $\mathrm{\Gamma }=T=(\{v_0,v_1\},\{e,\overline{e}\})$.

Let $E_{01}=⟨\{x^{-n}y{x}^n,n\in \mathbb{N}\}⟩$, $E_{10}=⟨\{a^{-n}b{a}^n,n\in \mathbb{N}\}⟩$. So the edge groups are infinitely generated.

Define

$$\begin{array}{rl}{\varphi }_e(x^{-2n}y{x}^{2n})& =a^{(-2n)!}b{a}^{(2n)!},\\ \\ {\varphi }_{\overline{e}}(a^{-2n-1}b{a}^{2n+1})& =x^{-(2n)!-1}y{x}^{(2n)!+1}.\end{array}$$

Then $G={\pi }_1(\mathbf{G},\mathrm{\Gamma },T,v_0)$ is $E_4$-computable.

Proof

First of all, the homomorphisms are $E_3$-computable because words of the form $a^{-n}b{a}^n$ can be recognised by an $E_3$ function. Hence all the ingredients of the graph of groups are $E_3$-computable.

A word of the form

$$e{a}^{-1}{e}^{-1}\dots x^{-1}e{a}^{-1}{e}^{-1}{x}^{-n}y{x}^{n}ea{e}^{-1}x\dots ea{e}^{-1}$$

will be reduced to a word on $G_0$ whose length is proportional to ${\mathrm{fact}}^{(m)}(n)$, where $m$ is the number of syllables. As $m$ depends on the input, this length can only be computed by unbounded recursion on an $E_3$ function, so is only $E_4$-computable.

Therefore, $G$ is $E_4$-computable. $◻$