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)& :=2{i}_{1}^{\prime}(x),\\ {m}_{1}(x,y)& :=2{m}_{1}^{\prime}(\frac{x}{2},\frac{y}{2})\\ {j}_{1}(x)& :=2{j}_{1}^{\prime}\left(\frac{x}{2}\right).\end{array}$$

$$\begin{array}{rl}{i}_{2}(x)& :=2{i}_{2}^{\prime}(x)\u20131,\\ {m}_{2}(x,y)& :=2{m}_{2}^{\prime}(\frac{x+1}{2},\frac{y+1}{2})\\ {j}_{2}(x)& :=2{j}_{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})]+{\textstyle \phantom{\rule{-0.167em}{0ex}}}{\textstyle \phantom{\rule{-0.167em}{0ex}}}{\textstyle \phantom{\rule{-0.167em}{0ex}}}{\textstyle \phantom{\rule{-0.167em}{0ex}}}+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})]+{\textstyle \phantom{\rule{-0.167em}{0ex}}}{\textstyle \phantom{\rule{-0.167em}{0ex}}}{\textstyle \phantom{\rule{-0.167em}{0ex}}}{\textstyle \phantom{\rule{-0.167em}{0ex}}}+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})]+{\textstyle \phantom{\rule{-0.167em}{0ex}}}{\textstyle \phantom{\rule{-0.167em}{0ex}}}{\textstyle \phantom{\rule{-0.167em}{0ex}}}{\textstyle \phantom{\rule{-0.167em}{0ex}}}+y[2\dots ]$

**endif**

**else**

$[{h}_{1}{m}_{1}(x,(y{)}_{0}),{k}_{1}{m}_{2}(x,(y{)}_{0})]+{\textstyle \phantom{\rule{-0.167em}{0ex}}}{\textstyle \phantom{\rule{-0.167em}{0ex}}}{\textstyle \phantom{\rule{-0.167em}{0ex}}}{\textstyle \phantom{\rule{-0.167em}{0ex}}}+y[1\dots ]$

**endif**

**endif**

**else**

**If** {$x\in {i}_{2}({H}_{2})$ }

$[{m}_{1}({\varphi}^{-1}(x),(y{)}_{0})]+{\textstyle \phantom{\rule{-0.167em}{0ex}}}{\textstyle \phantom{\rule{-0.167em}{0ex}}}{\textstyle \phantom{\rule{-0.167em}{0ex}}}{\textstyle \phantom{\rule{-0.167em}{0ex}}}+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})]+{\textstyle \phantom{\rule{-0.167em}{0ex}}}{\textstyle \phantom{\rule{-0.167em}{0ex}}}{\textstyle \phantom{\rule{-0.167em}{0ex}}}{\textstyle \phantom{\rule{-0.167em}{0ex}}}+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})]+{\textstyle \phantom{\rule{-0.167em}{0ex}}}{\textstyle \phantom{\rule{-0.167em}{0ex}}}{\textstyle \phantom{\rule{-0.167em}{0ex}}}{\textstyle \phantom{\rule{-0.167em}{0ex}}}+y[2\dots ]$

**endif**

**else**

$[{\varphi}^{-1}{h}_{2}{m}_{2}(x,\varphi ((y{)}_{0})),{k}_{2}{m}_{2}(x,\varphi ((y{)}_{0}))]+{\textstyle \phantom{\rule{-0.167em}{0ex}}}{\textstyle \phantom{\rule{-0.167em}{0ex}}}{\textstyle \phantom{\rule{-0.167em}{0ex}}}{\textstyle \phantom{\rule{-0.167em}{0ex}}}+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.

## Comments

## Comments

David Roberts

‘Free product with amalgamation’, also known an a pushout of groups. 🙂 This result is really quite useful for computing homotopy groups using the van Kampen theorem, which states that given a pushout of pointed spaces space with all maps open embeddings, and all spaces path connected, then the fundamental group of the pushout is the pushout of the fundamental groups. I have no idea what ‘E^n computable’ means, but I’m sure it is nice!