I am working on finitely presented groups with more than 5 generators and relators and I'm so curious: is it possible to determine residually finitness of finitely presented groups with MAGMA or GAP?
$\begingroup$
$\endgroup$
Add a comment
|
2 Answers
$\begingroup$
$\endgroup$
4
It is a consequence of the Adian-Rabin theorem that there is no algorithm that decides, given a finite presentation of a group, whether the group is residually finite.
In a similar spirit, it is undecidable whether a finitely presented group has any non-trivial finite quotients, by
Bridson, Martin R.; Wilton, Henry, The triviality problem for profinite completions, Invent. Math. 202, No. 2, 839-874 (2015). ZBL1360.20020.
-
4$\begingroup$ On the other hand, magma is rather good at doing some things in special cases which are undecidable in general. (E.g. deciding what a group is from a presentation ...) I'm not aware of any approaches to the OP's problem though... $\endgroup$ Commented Jul 22, 2022 at 8:12
-
$\begingroup$ There are very few known ways of certifying residual finiteness. Perhaps the most obvious way is to find a faithful representation, but this is very difficult to do in general. (I don't know if GAP or Magma have databases of linear groups to get you started...) One modern approach is to look for a special cubulation, but I don't think there has been much work on doing this effectively. $\endgroup$– HJRWCommented Jul 22, 2022 at 10:16
-
$\begingroup$ I feel this answer is a bit misleading without qualifying the statement, as Geordie pointed out: of course there is no algorithm that can do this in general, but for specific examples it may still be possible. Also if there is additional information about the group due to how it was constructed, that can change the picture. $\endgroup$– Max HornCommented Jul 22, 2022 at 13:04
-
1$\begingroup$ @ALanKay perhaps you'd be inclined to post your presentation, possible as a separate question: while I don't want to get your hopes up (despite my complaint, Giles is of course fundamentally correct!) but who knows, perhaps it's one of those special cases, or someone has another purely theoretical idea how to deal with it... $\endgroup$– Max HornCommented Jul 22, 2022 at 13:07
$\begingroup$
$\endgroup$
1
To precise Giles Gardam's answer, let me add the following.
The Adian-Rabin theorem shows that residual finiteness is undecidable, by showing that no algorithm can stop exactly on non-residually finite groups. In other words, the set of non-residually finite groups is not recursively enumerable -or not semi-decidable.
However, the Adian-Rabin theorem fails to prove that there cannot exist an algorithm that stops exactly on finite presentations of residually finite groups, i.e. an algorithm that will testify that a given group is residually finite and not stop otherwise. Yet this is also the case, it follows easily from the article Algorithmically complex residually finite groups of Kharlampovich, Myasnikov and Sapir, see Corollary 22 of my article for a written out proof.
This result contrasts for instance with the situation for hyperbolic groups, a property that the Adian-Rabin theorem also proves undecidable, but which was shown to be partially decidable by Papasoglu.
-
$\begingroup$ Very small remark: in the proof of Proposition 26 in your article, you use a construction of groups $G_w$ with $w \in H$, where $H$ is a group with unsolvable word problem, with the property that $G_w = 1$ if and only if $w=1$ in $H$, and attribute this to Miller's proof of the Adian-Rabin theorem. However, both Adian and Rabin construct such groups already in their own proofs (see Adian's groups $\mathfrak{A}_{q,A,B}$ in his 1957 Theorem 1, and Rabin's groups $G_{\pi_w}$). Note that Adian does not use Markov properties at all. $\endgroup$ Commented Aug 3, 2022 at 23:04