Skip to main content

Gatterdam’s proof that free products with amalgamation are \(\mathcal{E}^{n+1}\)-computable

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.


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 \(\phi’: H_1 \to H_2\) be an isomorphism, with \(\phi’, \phi’^{-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{\phi’}{\ast} G_2\), is \(\mathcal{E}^{n+1}\)-computable.


Let \((i’_1,m’_1,j’_1)\) be the index of \(G_1\) and \((i’_2,m’_2,j’_2)\) be the index of \(G_2\). The dashes will be explained later.

We can assume, without loss of generality, that \(0 \notin i’_a(G_a)\) and \(i’_a(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 \Leftrightarrow g_i \in G_2\).

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

\[ \begin{align} i_1(x) &:= 2i’_1(x), \\ m_1(x,y) &:= 2m’_1 \left( \frac{x}{2},\frac{y}{2} \right) \\ j_1(x) &:= 2j’_1 \left( \frac{x}{2} \right). \end{align} \]

\[ \begin{align} i_2(x) &:= 2i’_2(x) – 1, \\ m_2(x,y) &:= 2m’_2 \left( \frac{x+1}{2},\frac{y+1}{2} \right) \\ j_2(x) &:= 2j’_2 \left( \frac{x+1}{2} \right). \end{align} \]


\[ \begin{align} x \in i_1(G_1) &\Leftrightarrow 2 \mid x \wedge \frac{x}{2} \in i’_1(G_1), \\ x \in i_1(H_1) &\Leftrightarrow x \in i_1(G_1) \wedge \frac{x}{2} \in i’_1(H_1), \\ x \in i_2(G_2) &\Leftrightarrow 2\not \mid x \wedge \frac{x+1}{2} \in i’_2(G_2), \\ x \in i_2(H_2) &\Leftrightarrow x \in i_2(G_2) \wedge \frac{x+1}{2} \in i’_2(H_2). \end{align} \]

The subgroup isomorphism also needs to be redefined:

\[ \begin{align} \phi(x) &:= 2\phi’ \left( \frac{x}{2} \right)-1 \\ \phi^{-1}(x) &:= 2 \phi’^{-1} \left( \frac{x+1}{2} \right) \end{align} \]

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_ak_a\), where \(h_a \in H_a\) and \(k_a\) is a coset representative of \(g_a\) in \(G_a / H_a\).


\[ \begin{align} k_a(x) &:= \min_{y \leq x} \left( m_a(x,j_a(y)) \in i_a(H_a) \right), \\ h_a(x) &:= m_a(x,j_a(k_a(x))). \end{align} \]

Now we can define \(i(G)\) by

\[ i(hg_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)\)
  • \(\forall 2 \lt i \lt |x|\), \((x)_i \in i_1(G_1) \Leftrightarrow (x)_{i-1} \in i_2(G_2)\)
  • \(\forall 1 \lt i \lt |x|\), \((x)_i \in i_a(G_a) \rightarrow 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:


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

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

\([m_1(x,(y)_0)] +\!\!\!\!+ y[1 \dots]\)


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]\)


\([h_1m_1(m_1(x,(y)_0),(y)_1), k_1m_1(m_1(x,(y)_0),(y)_1)] +\!\!\!\!+ y[2 \dots]\)



\([h_1m_1(x,(y)_0),k_1m_2(x,(y)_0)] +\!\!\!\!+ y[1 \dots]\)




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

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


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

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

\([\phi^{-1}m_2(m_2(x,\phi((y)_0)),(y)_1)] +\!\!\!\!+ y[2 \dots]\)


\([\phi^{-1}h_2m_2(m_2(x,\phi((y)_0)),(y)_1), k_2m_2(m_2(x,\phi((y)_0)),(y)_1)] +\!\!\!\!+ y[2 \dots]\)



\([\phi^{-1}h_2m_2(x,\phi((y)_0)),k_2m_2(x,\phi((y)_0))] +\!\!\!\!+ y[1 \dots]\)





Now we can do multiplication on \(G\) in general:

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

And inversion:

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

\[ \hat{j}(x) := \begin{cases} j_1(x), & x \in i_1(G_1), \\ j_2(x), & x \in i_2(G_2). \end{cases} \]

(\(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.


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



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