Given a finitely presented group (finite number of generators and finite number of relations) is there any efficient algorithms which detects whether the group is Abelian or not? (So the problem is to check whether the commutators can be generated by the relations or not.)
$\begingroup$
$\endgroup$
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
5
No, by reduction from the undecidability of checking whether the group is trivial.
Consider such a presentation. If we know the group to be non abelian, then we know it to be non-trivial. If we know the group to be abelian, them we can calculate whether it is trivial or not by computing the Smith normal form of the presentation.
-
3$\begingroup$ Actually, the proof that the triviality of a group given by a presentation is undecidable is completely applicable here. The key idea in the proof is that of "Markov properties". Markov properties are undecidable. "Being trivial" is a Markov property, and, relevant to this question, "being abelian" is also a Markov property. Hence, being abelian is undecidable. For more details Google/DuckDuckGo the Adian-Rabin theorem, or see this old answer of mine. $\endgroup$– user1729Commented Aug 10, 2019 at 11:53
-
1$\begingroup$ (also, the link explains that there exists a partial algorithm where if the group is abelian then the algorithm will detect this.) $\endgroup$– user1729Commented Aug 10, 2019 at 12:46
-
$\begingroup$ @user1729 Thanks! Based on your answers, it seems like it could be the case that deciding whether a presentation gives an Abelian group is possible for certain classes of groups. Maybe the person who asked this question has a particular group in mind, and it could belong to a such class of groups... $\endgroup$ Commented Aug 10, 2019 at 13:08
-
1$\begingroup$ Certainly! For example, being abelian is decidable amongst finite groups, abelian groups (cough well it is!), and probably hyperbolic groups too. There are also tricks. For example, if your presentation has 2 more generators than relators then it is non-abelian, while if it has more generators than relators and one of the relators is a proper power then it is non-abelian. $\endgroup$– user1729Commented Aug 10, 2019 at 13:57
-
3$\begingroup$ More generally, we can decide whether finitely generated groups with solvable word problem are abelian, because we just need to check whether all pairs of generators commute. $\endgroup$ Commented Aug 11, 2019 at 17:01