8
$\begingroup$

Let $G$ be a finitely presented simple group. By Kuznetsov (1958), $G$ has decidable word problem. However, by Scott [1], $G$ may have undecidable conjugacy problem. Is anything known about other decision problems for $G$, in generality? I am particularly interested in the question of the subgroup membership problem, i.e. the problem of, given a set of words $w_1, \dots, w_k$ and a word $w$, deciding whether or not $w$ belongs to the subgroup $\langle w_1, \dots, w_k \rangle$ of $G$. This is undecidable already for the direct product $H \times H$ of any group $H$ admitting a finitely presented quotient with undecidable word problem (in particular, we can take $H$ to be a free group of rank $2$), but such direct products are of course very far from being simple.

${}$

[1] Scott, Elizabeth A., A finitely presented simple group with unsolvable conjugacy problem, J. Algebra 90, 333-353 (1984). ZBL0544.20029.

$\endgroup$

2 Answers 2

9
$\begingroup$

As another example, the problem of computing the order of an element of the finitely presented simple Brin–Thompson group $2V$ is undecidable by

Belk, James; Bleak, Collin, Some undecidability results for asynchronous transducers and the Brin-Thompson group (2V), Trans. Am. Math. Soc. 369, No. 5, 3157-3172 (2017). ZBL1364.20015.

$\endgroup$
1
  • $\begingroup$ Very nice, thanks! (Small note: the result attributed to Arzhantseva, Lafont, and Minasyan (2012) in the abstract (a f.p. group with decidable word problem but undecidable order problem) appears already in McCool (1970), but it is also rather non-constructive) $\endgroup$ Mar 22, 2023 at 13:23
7
$\begingroup$

After some digging, I was able to find that the answer to my question exists: the problem can be undecidable. Rattaggi, in an unpublished manuscript (available here), proved that there exists a finitely presented simple group $G$ which contains $F_2 \times F_2$ as a subgroup. This group $G$ arises from constructions related to the Burger-Mozes groups. In particular, $G$ is incoherent (and, importantly for my question), has undecidable subgroup membership problem.

$\endgroup$
2
  • 4
    $\begingroup$ Great. But you don't need Rataggi: Thompson's group $V$ contains $V\times V$ (trivial fact), and $V$ contains a non-abelian free subgroup $F$ (very easy too), so $V$ contains $F\times F$. $\endgroup$
    – YCor
    Mar 22, 2023 at 13:34
  • $\begingroup$ @YCor Even better! Thanks -- that's a great example to remember. $\endgroup$ Mar 22, 2023 at 14:25

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.