I’m going to write up a result I think I’ve proved, which follows on from Gatterdam’s thesis. He showed that if a group is $E_n$ computable, then doing a free product with amalgamation or any number of HNN extensions to it results in a group which is at worst $E_{n+1}$ computable. What I’m going to say is that the fundamental group of a graph of $E_n$ groups is at most $E_{n+1}$ computable. This isn’t unreasonable, because a fgoagog (( ‘fgoagog’ is short for ‘fundamental group of a graph of groups’, because I can’t be doing with writing that out once every three minutes )) represents a load of HNN extensions and amalgamated products.

The tactic will be to follow Gatterdam’s method for amalgamated products – if we can find an algorithm which solves the word problem of the fgoagog (decides if a word on the generators is equivalent to the identity) in $E_{n+1}$ time, then the whole group is $E_{n+1}$ computable as a quotient of the free group by the set of trivial words.

I will define an admissible form for words from the fgoagog, which is an alternating series of edge letters and words from the vertex groups, such that the edge letters make up a cycle starting and ending at the base vertex. Once we have a word in admissible form, we can reduce it by swapping the image of an edge group in one vertex with its counterpart in the vertex at the other end, and eventually a trivial word will end up as just a word on the base vertex, which is an $E_n$ decision.

Clearly the process of putting a word in admissible form involves knowing something about the shape of the graph, so we need to make some $E_n$ computable functions which can represent the graph and compute paths between vertices. That’s a tiny bit interesting on its own, so I’ll spend my next post talking about that. It will need some pretty pictures of trees though, which is why I’ve put off writing it for so long.