# Is the diagonal of finitely presented groups computable?

Let $$f:G\to H$$ be a surjective homomorphism of finitely presented groups. If the kernel of $$f$$ is finitely generated then is $$G\times_H G$$ is a finitely presented group? Can one compute an explicit finite presentation?

• If $F$ is free of finite rank and $Q$ is an infinite quotient of $F$ with infinite kernel, then the fiber product $F\times_Q F$ is not finitely presentable. – YCor Apr 22 at 8:00
• @YCor I edited is it correct now? – Oniqa Apr 22 at 8:04
• If you checked that the fiber product is finitely presentable, don't you get an explicit finite presentation? – YCor Apr 22 at 8:13
• @YCor: the fact that they are finitely presented follows from the 1-2-3 theorem of Baumslag--Bridson--Miller--Short, but the proof doesn't give an explicit presentation. – HJRW Apr 22 at 8:48
• @YCor: I omitted to mention that there is an extra hypthesis needed, namely that the quotient $H$ should be of type $F_3$. – HJRW Apr 22 at 20:35

The answer is "no". The hypotheses for the fibre product to be finitely presentable are given by the 1-2-3 theorem of Bridson--Baumslag--Miller--Short:

1-2-3 Theorem (BBMS): The fibre product $$G\times_H G$$ is guaranteed to be finitely presentable as long as:

1. the kernel of $$G\to H$$ is finitely generated;
2. $$G$$ itself is finitely presented;
3. $$H$$ satisfies a higher finiteness condition, namely being of "type $$F_3$$".

However, there is no general algorithm that can compute a finite presentation for $$G\times_H G$$. Indeed, stronger, there is no algorithm that can compute its abelianisation, and the result follows since the abelianisation can be computed from a finite presentation.

This is proved in my paper with Bridson:

Bridson & Wilton, "On the difficulty of presenting finitely presentable groups", Groups Geom. Dyn. 5(2), pp. 301–325, 2011

available on the arXiv here. See Theorem A, and note in the proof that the subgroup $$\Lambda_n$$ is indeed a fibre product.

To give a brief sketch of the argument, one takes a sequence of perfect groups $$Q_n$$ such that the second Betti numbers $$b_2(Q_n)$$ are known to be impossible to compute. The Rips short exact sequence gives

$$1\to K_n\to\Gamma_n\to Q_n\to 1$$

with $$K_n$$ finitely generated, and then let $$\Lambda_n\leq \Gamma_n\times\Gamma_n$$ be the fibre product. Finally, an argument with the Stallings exact sequence relates the Betti numbers:

$$b_1(\Lambda_n) = 2b_1(\Gamma_n)+b_2(Q_n).$$

Since $$b_1(\Gamma_n)$$ is computabe and $$b_2(Q_n)$$ isn't, it follows that $$b_1(\Lambda_n)$$ is not computable. In particular, no presentation for $$\Lambda_n$$ can be computed, even though we are given explicit generating sets and know that they are finitely presented.

• So then at which level in the arithmetical hiearchy is the claim that a given group is finitely presentable? Seems like an oracle for the halting problem couldn't solve that? – Oniqa Apr 22 at 11:00
• @Oniqa: that question is above my pay-grade, unfortunately! – HJRW Apr 22 at 11:51
• @Oniqa What data are you using to represent the group? Are we talking about arbitrary computable groups? Or do you mean relative to the group as an oracle? – James Hanson Apr 23 at 4:40
• @Oniqa I guess it doesn't really matter that much. Suppose you're given a group as an oracle $G$. If you pick some finite set $\bar{a}$ of elements and some relations on those, checking to see if those relations give a presentation of the subgroup generated by $\bar{a}$ is a $\Pi^0_1(G)$ condition. – James Hanson Apr 23 at 5:03
• @Oniqa Checking to see if a finite presentation exists is therefore $\Sigma^0_3(G)$, which implies that checking to see if no such finite presentation exists is $\Pi^0_3(G)$. So all told, deciding if a given group has a finite presentation takes at most $3$ Turing jumps above the complexity of the group itself. I don't know if this is optimal, but usually these kinds of things aren't any easier than a naïve calculation like this. (Although I also may have miscounted.) – James Hanson Apr 23 at 5:04