Does every decidable question about finitely presented groups amount to a question about abelian groups?

Question

This question is about an issue left unresolved by Chad Groft's excellent question and John Stillwell's excellent answer of it. Since I find the possibility of an affirmative answer so tantalizing, I would like to pursue it further here.

For background, Rice's Theorem asserts essentially that no nontrivial question about computably enumerable sets is decidable. If W_e is the set enumerated by program e, then the theorem states:

Rice's Theorem. If A is a collection of computably enumerable sets and { e | W_e ∈ A } is decidable, then either A is empty or A contains all computably enumerable sets.

In short, one can decide essentially nothing about a program e, if the answer is to depend only on what the program computes rather than how it computes it.

The question here is about the extent to which a similar phenomenon holds for finitely presented groups, using the analogy between programs and finite group presentations:

• a program e is like a finite group presentation p
• the set W_e enumerated by e is like the group ⟨p⟩ presented by p.

According to this analogy, the analogue of Rice's theorem would state that any decidable collection of finitely presented groups (closed under isomorphism) should be either trivial or everything. John Stillwell pointed out in answer to Chad Groft's question that this is not true, because from a presentation p we can easily find a presentation of the abelianization of ⟨p⟩, by insisting that all generators commute, and many nontrivial questions are decidable about finitely presented abelian groups. Indeed, since the theory of abelian groups is a decidable theory, there will be many interesting questions about finitely presented abelian groups that are decidable from their presentations.

My question is whether this is the only obstacle.

Question. Does Rice's theorem hold for finitely presented groups modulo abelianization?

In other words, if A is a set of finitely presented groups (closed under isomorphism) and the corresponding set of presentations { p | ⟨p⟩ ∈ A } is decidable, then does A completely reduce to a question about the abelianizations of the groups, in the sense that there is a set B of abelian groups such that G ∈ A iff Ab(G) ∈ B?

Of course, in this case B consists exactly of the abelian groups in A. The question is equivalently asking whether A respects the equivalence of groups having isomorphic abelianizations. In other words, must it be that G ∈ A iff Ab(G) ∈ A? The question is asking whether every decidable set of finitely presented groups amounts actually to a decidable set of abelian groups, extended to all finitely presented groups just by saturating with respect to abelianization.

In particular, the set A should contain either none or all perfect groups.

An affirmative answer would seem to provide a thorough explanation of the pervasive undecidability phenomenon in group presentations. But perhaps this may simply be too much to hope for...

In any event, I suppose that there is an equivalence relation on finite group presentations, saying that p ≡ q just in case ⟨p⟩ and ⟨q⟩ have the same answer with repsect to any decidable question about finitely presented groups. The question above asks whether this equivalence relation is just Ab(⟨p⟩) = Ab(⟨q⟩). If this turns out not to be true, then what can be said about ≡?

Answer 1

The question "Is there a nonzero homomorphism from your group to $A_5$?" is decidable. (Just write down all ways of sending the generators of your group to $A_5$, and see whether they satisfy the required relations.) The same is true with $A_5$ replaced by any finite group. I don't see how to reduce this to questions about the abelianization.

Answer 2

You can compute the representation variety from $G$ into $M_n(\mathbb C)$ or your favorite algebraic group. This contains much more information than the abelianization.

Similarly, and slimilar to David Speyer's response, you can count the subgroups of index $n$: Index $n$ subgroups in $G$ correspond to transitive permutation representations on $n$ elements by the action of cosets. Many of these do not factor through the abelianization.

Answer 3

There are quotients you can take other than the abelianization. For instance, most questions about finitely generated nilpotent groups are easily decidable. If you have a finite presentation for a group $G$, then you can easily produce a finite presentation for $G/\gamma_k(G)$, where $\gamma_k(G)$ is the kth term of the lower central series for $G$. This will be a $k$-step nilpotent group canonically associated to $G$ (often called the $k$-step nilpotent truncation of $G$). For $k=1$, this reduces to taking the abelianization.

Be warned : things are much worse if you take SOLVABLE quotients. For example, Kharlampovich has produced a finitely presented 3-step solvable group with an unsolvable word problem...

EDIT : For a wealth of information about obtaining information about groups from their nilpotent quotients, I recommend reading Ralph Fox's classic series of papers on the free differential calculus.

Answer 4

One more counterexample. Makanin's algorithm solves systems of equations and inequations over any non-abelian free group F. The statement

'$G=\langle x_1,\ldots, x_m\mid r_1,\ldots,r_n\rangle$ surjects a non-abelian free group'

is equivalent to the negation of the system of equations and inequations

$ (r_i=1 \mid \forall i) \Rightarrow ([x_i,x_j]=1\mid\forall i,j) $

over F, where $x_i$ are now interpreted as variables and $r_j$ are now interpreted as equations.

Therefore, the statement is decidable. On the other hand, $F$ surjects a non-abelian free group, but its abelianisation does not.