Skip to main content

The computability of a fgoagog (intro)

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 En computable, then doing a free product with amalgamation or any number of HNN extensions to it results in a group which is at worst En+1 computable. What I’m going to say is that the fundamental group of a graph of En groups is at most En+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 En+1 time, then the whole group is En+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 En 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 En 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.