I haven’t posted any research in ages! I haven’t done any research in ages! Here’s a rewriting of a theorem from Ronald Gatterdam’s doctoral thesis, in more sensible language. I’ve proved the same theorem for fundamental groups of graphs of groups.

The main problem with Gatterdam’s proof was that he didn’t invent any new notation to make life simpler, so he wrote out pages and pages of very repetitive function applications.

I’ve made up a lot of notation to make dealing with functions in the Grzegorczyk hierarchy a lot easier, so you’ll probably need to refer to my draft paper for a few things. I keep all my research notes in a repository on github, by the way.

Theorem

Let $G_1,G_2$ be ${\mathcal{E}}^n$-computable groups. Let $H_1,H_2$ be ${\mathcal{E}}^n$-decidable subgroups of the latter. Let ${\varphi }^{\prime }:H_1\to H_2$ be an isomorphism, with ${\varphi }^{\prime },{\varphi }^{\prime -1}$ both ${\mathcal{E}}^n$-computable.

Then the free product of $G_1$ and $G_2$ with $H_1$ and $H_2$ amalgamated, $G=G_1\underset{{\varphi }^{\prime }}{\ast }{G}_2$, is ${\mathcal{E}}^{n+1}$-computable.

Proof

Let $(i_1^{\prime },m_1^{\prime },j_1^{\prime })$ be the index of $G_1$ and $(i_2^{\prime },m_2^{\prime },j_2^{\prime })$ be the index of $G_2$. The dashes will be explained later.

We can assume, without loss of generality, that $0\notin i_a^{\prime }(G_a)$ and $i_a^{\prime }(1)=1$ for $a=1,2$. (Might not even need this.)

By Magnus, Karrass, Solitar, etc., all elements $g\in G$ have normal form

$$g=h{g}_1\dots g_r$$

where $h\in H_1$, and the $g_i$ are coset representatives of $G_a/H_a$, $a=1,2$, such that $g_{i+1}\in G_1\iff g_i\in G_2$.

The following proof becomes a lot easier if we redefine the factor group indices as follows:

$$\begin{array}{rl}{i}_1(x)& :=2i_1^{\prime }(x),\\ m_1(x,y)& :=2m_1^{\prime }(\frac{x}{2},\frac{y}{2})\\ j_1(x)& :=2j_1^{\prime }\left(\frac{x}{2}\right).\end{array}$$

$$\begin{array}{rl}{i}_2(x)& :=2i_2^{\prime }(x)–1,\\ m_2(x,y)& :=2m_2^{\prime }(\frac{x+1}{2},\frac{y+1}{2})\\ j_2(x)& :=2j_2^{\prime }\left(\frac{x+1}{2}\right).\end{array}$$

Now,

$$\begin{array}{rl}x\in i_1(G_1)& \iff 2\mid x\wedge \frac{x}{2}\in i_1^{\prime }(G_1),\\ x\in i_1(H_1)& \iff x\in i_1(G_1)\wedge \frac{x}{2}\in i_1^{\prime }(H_1),\\ x\in i_2(G_2)& \iff 2\nmid x\wedge \frac{x+1}{2}\in i_2^{\prime }(G_2),\\ x\in i_2(H_2)& \iff x\in i_2(G_2)\wedge \frac{x+1}{2}\in i_2^{\prime }(H_2).\end{array}$$

The subgroup isomorphism also needs to be redefined:

$$\begin{array}{rl}\varphi (x)& :=2{\varphi }^{\prime }\left(\frac{x}{2}\right)-1\\ {\varphi }^{-1}(x)& :=2{\varphi }^{\prime -1}\left(\frac{x+1}{2}\right)\end{array}$$

In order to do multiplication, we need to be able to split every $g_a\in G_a$, $a=1,2$, into a word of the form $h_a{k}_a$, where $h_a\in H_a$ and $k_a$ is a coset representative of $g_a$ in $G_a/H_a$.

Define:

$$\begin{array}{rl}{k}_a(x)& :=\underset{y\le x}{min}(m_a(x,j_a(y))\in i_a(H_a)),\\ h_a(x)& :=m_a(x,j_a(k_a(x))).\end{array}$$

Now we can define $i(G)$ by

$$i(h{g}_1\dots g_r):=[h,g_1,\dots ,g_r].$$

(encode it as a Gödel number)

$i(G)$ is ${\mathcal{E}}^n$-decidable because $x\in i(G)$ if and only if:

• $x$ is a Gödel number
• $(x{)}_0\in i_1(H_1)$
• $\mathrm{\forall }2<i<|x|$, $(x{)}_i\in i_1(G_1)\iff (x{)}_{i-1}\in i_2(G_2)$
• $\mathrm{\forall }1<i<|x|$, $(x{)}_i\in i_a(G_a)\to k_a((x{)}_i)=(x{)}_i$.

Now define a function $r:(i_1(G_1)\cup i_2(G_2))\times i(G)\to i(G)$ which does multiplication of elements of $G$ on the left by elements of $G_1$ and $G_2$.

$r$ is defined by cases in a decision tree, so here’s some programming-ish syntax:

$r(x,y):=$

If {$x\in i_1(G_1)$}

If {$x\in i_1(H_1)$}

$[m_1(x,(y{)}_0)]++y[1\dots ]$

else

If {$(y{)}_1\in i_1(G_1)$}

If {$m_1(m_1(x,(y{)}_0),(y{)}_1)\in i_1(H_1)$ }

$[m_1(m_1(x,(y{)}_0),(y{)}_1)]++y[2\dots ]$

else

$[h_1{m}_1(m_1(x,(y{)}_0),(y{)}_1),k_1{m}_1(m_1(x,(y{)}_0),(y{)}_1)]++y[2\dots ]$

endif

else

$[h_1{m}_1(x,(y{)}_0),k_1{m}_2(x,(y{)}_0)]++y[1\dots ]$

endif

endif

else

If {$x\in i_2(H_2)$ }

$[m_1({\varphi }^{-1}(x),(y{)}_0)]++y[1\dots ]$

else

If {$(y{)}_1\in i_2(G_2)$ }

If {$m_2(m_2(x,\varphi ((y{)}_0)),(y{)}_1)\in i_2(H_2)$ }

$[{\varphi }^{-1}{m}_2(m_2(x,\varphi ((y{)}_0)),(y{)}_1)]++y[2\dots ]$

else

$[{\varphi }^{-1}{h}_2{m}_2(m_2(x,\varphi ((y{)}_0)),(y{)}_1),k_2{m}_2(m_2(x,\varphi ((y{)}_0)),(y{)}_1)]++y[2\dots ]$

endif

else

$[{\varphi }^{-1}{h}_2{m}_2(x,\varphi ((y{)}_0)),k_2{m}_2(x,\varphi ((y{)}_0))]++y[1\dots ]$

endif

endif

endif

 

Now we can do multiplication on $G$ in general:

$$\begin{array}{rl}m([],y)& :=y,\\ m(x:xs,y)& :=r(x,m(xs,y)).\end{array}$$

And inversion:

$$\begin{array}{rl}j([1])& :=[1],\\ j(x:xs)& :=r(\hat{j}(x),j(xs)).\end{array}$$

$$\hat{j}(x):=\{\begin{array}{ll}{j}_1(x),& x\in i_1(G_1),\\ j_2(x),& x\in i_2(G_2).\end{array}$$

($x:xs$ means a list of the form $[x,x_1,x_2,\dots ]$. I borrowed this syntax from Haskell. I need to show that you can define recursive functions on lists like this, but I hope you agree it works)

The functions $m$ and $j$ are defined recursively. Because we don’t know anything about how quickly the original multiplication functions grow, the recursion is unbounded, so the best we can do is to say that the index of $G$ is at worst ${\mathcal{E}}^{n+1}$-computable.

QED

Gatterdam also shows that the embeddings $G_a\to G$ are natural, but I lost the will.