# Is any interesting question about a group G decidable from a presentation of G?

We say that a group G is in the class Fq if there is a CW-complex which is a BG (that is, which has fundamental group G and contractible universal cover) and which has finite q-skeleton. Thus F0 contains all groups, F1 contains exactly the finitely generated groups, F2 the finitely presented groups, and so forth.

My question: For a fixed q ≥ 3, is it possible to decide, from a finite presentation of a group G, whether G is in Fq or not? I would assume not, but am not having much luck proving it.

One approach would be to prove that, if G is a group in Fq and H is a finitely presented subgroup, then HFq as well. This would make being in Fq a Markov property, or at least close enough to make it undecidable.

Henry Wilton's comment below makes it clear that being Fq is not even quasi-Markov, so the above idea won't work. I still suspect that "GFq" is not decidable, but now my intuition is from Rice's theorem:

If $\mathcal{B}$ is a nonempty set of computable functions with nonempty complement, then no algorithm accepts an input n and decides whether φn is an element of $\mathcal{B}$.

It seems likely to me that something similar is true of finite presentations and the groups they define.

John Stillwell notes below that this can't be true for a number of questions involving the abelianization of G. This wouldn't affect the Rips construction/1-2-3 theorem discussion below if the homology-sphere idea works, since those groups are all perfect.

Any thoughts?

• For my edification, can you give an example of a finitely presented group not in F_3? – Reid Barton Feb 21 '10 at 23:26
• Here's an example of an interesting question whose decidability status is unknown. 'Does G have a proper subgroup of finite index?' – HJRW Feb 23 '10 at 2:28
• Your revised question is truly outstanding! I had already voted up your previous question, but now all I want to know whether Rice's theorem holds for finite group presentations. – Joel David Hamkins Feb 23 '10 at 3:17
• (Stillwell's example shot down my earlier comment, so I deleted it.) – François G. Dorais Feb 23 '10 at 5:10
• At the risk of sounding churlish, I think the original question, about finiteness properties, was really interesting, and the modified version is really dull. – HJRW Feb 27 '10 at 2:49

It seems to me that the analogue of Rice's theorem fails for finitely presented groups $G$ because of questions like: is the abelianization of $G$ of rank 3? The rank of the abelianization of any finitely presented $G$ can be computed by reducing the abelianization to normal form, so this (slightly) interesting question can be decided from the presentation of $G$.

• Yes, you're absolutely right. More generally, any property of G that is computable from the isomorphism type of ab(G) is computable from a finite presentation for G. – Chad Groft Feb 23 '10 at 4:46
• +1. Very good. It's too bad we can't have Rice's theorem here... – Joel David Hamkins Feb 23 '10 at 12:05
• There's still a reasonable question in that area. For instance, you could restrict yourself to perfect groups. – HJRW Feb 23 '10 at 17:27
• Henry, I had had the same thought, and I have asked a question at mathoverflow.net/questions/16532 following up on this. – Joel David Hamkins Feb 26 '10 at 17:38

Sorry I came to this question late. $$F_q$$ is undecidable from a presentation for each fixed $$3\leq q<\infty$$. First note that for finitely presented groups $$F_q$$ is equivalent to the homological finiteness condition $$FP_q$$ so it is enough to show this condition undecidable. This was done for $$q =3$$ in Section 5 of Cremanns, Robert; Otto, Friedrich, For groups the property of having finite derivation type is equivalent to the homological finiteness condition FP3. J. Symbolic Comput. 22 (1996), no. 2, 155–177 https://www.sciencedirect.com/science/article/pii/S0747717196900462. The same construction works for any fixed finite $$q\geq 3$$. They use essentially the same construction as the proof that Markov properties are undecidable but different details.

[This answers Reid's petition for an example in the comments, in answer form so as to be able to preview]

Stallings has given in [Stallings, John. A finitely presented group whose 3-dimensional integral homology is not finitely generated. Amer. J. Math. 85 1963 541--543. MR0158917] an example of a finitely presented group $G$ such that $H_3(G)$ is not finitely generated. It follows from this that the 3-skeleton of $BG$ is infinite. The group is $$G=\langle a,b,c,x,y:[x,a], [y,a],[x,b],[y,b],[a^{-1}x,c],[a^{-1}y,c],[b^{-1}a,c]\rangle.$$ Stallings' paper is characteristically short and beautiful, and the proof is a nice application of Mayer-Vietoris (!)

• Bestvina and Brady gave a beautiful generalization of Stallings's theorem using PL morse theory (they manage to construct groups with all kinds of weird (non)finiteness properties). Their methods become especially simple when restricted to Stallings's example -- an elementary account of this can be found in Bestvina's wonderful "PL Morse theory notes", which are available on his homepage at math.utah.edu/~bestvina/research.html – Andy Putman Feb 22 '10 at 15:39
• Stallings's example shoots down Chad's approach from the last paragraph. G is equal to the kernel of the map F_2 x F_2 x F_2-> Z. In particular, F_2 x F_2 x F_2 is in F_3 but G is not. – HJRW Feb 23 '10 at 0:14

I don't have a complete answer, but here are some thoughts.

The Rips Construction takes an arbitrary finitely presented group Q and produces a 2-dimensional hyperbolic group $\Gamma$ and a short exact sequence

$1\to K\to \Gamma\stackrel{q}{\to} Q\to 1$

such that the kernel $K$ is generated by 2 elements. It turns out, by a result of Bieri, that $K$ is finitely presentable if and only if $Q$ is finite.

One can improve the finiteness properties of $K$ using a fibre product construction. Let

$P=\{(\gamma,\delta)\in\Gamma\times\Gamma\mid q(\gamma)=q(\delta)\}$.

By the '1-2-3 Theorem', if $Q$ is of type $F_3$ then $P$ is finitely presentable.

I would guess that $P$ has good higher finiteness properties if and only if $Q$ is finite. Perhaps one can use the fact that $P\cong K \rtimes\Gamma$.

Even if this is true then it still doesn't quite solve your problem, as we don't have a presentation for $P$. To do this, one needs to be given a set of generators for $\pi_2$ of the presentation complex of $Q$, which enable one to apply an effective version of the 1-2-3 Theorem. (In the absence of this data, presentations for $P$ are not computable. Indeed, $H_1(P)$ is not computable.)

Question: Does there exist a list of presentations for groups $Q_n$ such that:

1. each group $Q_n$ is of type $F_3$;

2. the set $\{n\in\mathbf{N}\mid Q_n\cong 1\}$ is recursively enumerable but not recursive;

3. but generators for $\pi_2(Q_n)$ (as a $Q_n$-module) are computable?

If so, and if I'm right that the higher finiteness properties of $P$ are determined by $Q$, then higher finiteness properties are indeed undecidable. Simply apply the Rips Construction and the effective version of the 1-2-3 Theorem to the list $Q_n$.

• Gah! Why has my latex not worked? – HJRW Feb 23 '10 at 2:22
• I fixed it for you. Put backticks  around your latex when something goes wrong. – François G. Dorais Feb 23 '10 at 3:24
• I'll check these references out in the near future. (I'm not "affiliated with an institution" at the moment, so it'll take a little while.) I know it's possible to get an effective sequence {Sigma_k} of homology n-spheres (for fixed n ≥ 5) for which the set { k : Sigma_k = S^n } is noncomputable. (Since a simply connected homology n-sphere is just the n-sphere, the set is r.e.) Also the fundamental groups would necessarily have zero homology in dimensions 1 and 2. Might it be possible to take Q_k = pi_1(Sigma_k)? What kind of control do we get on pi_2(Q_k)? – Chad Groft Feb 23 '10 at 3:47
• Gah. It's gone again. – HJRW Feb 23 '10 at 5:35
• Chad, I think the problem with that idea is that we need to know about $\pi_2$ of a presentation complex, not $\pi_2$ of some space with the right $\pi_1$. – HJRW Feb 23 '10 at 5:51

I am fascinated by your question about whether there is a finite group presentation analogue of Rice's theorem. If true, this would settle your original question and all other similar decidability questions about group presentations, as long as they are questions about the class of groups presented, rather than a question about the presentation itself. Such a theorem would simultaneously answer hundreds of such similar decidability questions.

The evidence against an analogue of Rice's theorem would include the fact that there are large classes of groups having very nice decidability features. For example, the class of automatic groups have many decidable properties. They have decidable word problems, and it is decidable whether they are trivial or nontrivial, whether they are infinite or not. I think that the conjugacy problem is decidable, when the presentation of the group and subgroup is automatic. According to the Wikipedia page, the automatic groups include

• Negatively curved groups
• Euclidean groups
• All finitely generated Coxeter groups [1]
• Braid groups
• Geometrically finite groups

Automaticity does not depend on the set of generators. Furthermore, one can sometimes tell from a presentation that one has an automatic group. I recall that the Magnus group theory program is very happy when it finds that a group presentation that you give it is automatic, and it will tell you so (but I don't have so much experience with these programs).

But this evidence does not seem to refute the Rice theorem analogue, unless we could tell from a presentation whether it was automatic or not. At least sometimes we can, but I don't think automaticity is decidable in general.

So I am holding out for a positive answer to the Rice Theorem analogue.

• Automaticity is not decidable. The proof that Markov properties are undecidable would apply here. More generally, any condition on a group that applies to the trivial group, and which implies that the group has decidable word problem, cannot be decidable. So hope survives! Specifically, there is a construction which takes a f.p. group G and a word w in G, and builds a group G_w. This new group is trivial if w is trivial and contains G as a subgroup if w is not trivial. Testing G_w for the condition would test w for triviality, which is clearly a problem. – Chad Groft Feb 23 '10 at 4:40
• I think this misses the point somewhat. There are some very general, very well-behaved classes of groups. For instance, a 'randomly chosen' finitely presented group is hyperbolic, which is a very nice sort of hyperbolic group. But the point is that one can't recognise if a given presentation falls into a nice class or not. Indeed, we can't recognise if a given presentation is of the trivial group! That's the point about Markov properties. – HJRW Feb 23 '10 at 5:30
• Henry, thanks for your comment. Yes, I understand that point very well. This was why I found the possibility of a Rice's theorem in this context so tantalizing, because if true, it would have explained the phenomenon so completely. But alas, Stillwell has refuted it. – Joel David Hamkins Feb 23 '10 at 13:57

I've been told that the answer to a related question (namely, can one decide if a finitely presented group has a finite classifying space) is no, and that the proof can be extracted from the book `Computers, rigidity, and moduli''. I would guess that one can also consult the book for a proof of the original question, but the book is currently unavailable to me.

• Do you mean this book - books.google.com/… – François G. Dorais Mar 20 '10 at 5:31
• It's possible. I have a copy of that book; perhaps I should take a closer look. – Chad Groft Mar 21 '10 at 1:38