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

Question

We say that a group G is in the class F_q 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 F₀ contains all groups, F₁ contains exactly the finitely generated groups, F₂ 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 F_q 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 F_q and H is a finitely presented subgroup, then H ∈ F_q as well. This would make being in F_q a Markov property, or at least close enough to make it undecidable.

Henry Wilton's comment below makes it clear that being F_q is not even quasi-Markov, so the above idea won't work. I still suspect that "G ∈ F_q" 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?

Answer 1

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$.

Answer 2

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.

Answer 3

[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 (!)

Answer 4

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$.

Answer 5

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.

Answer 6

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.