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.

Improve this question
$\endgroup$

2 Answers 2

Reset to default
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.

Improve this answer
$\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$
    – Carl-Fredrik Nyberg Brodda
    Commented 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.

Improve this answer
$\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
    Commented Mar 22, 2023 at 13:34
  • $\begingroup$ @YCor Even better! Thanks -- that's a great example to remember. $\endgroup$
    – Carl-Fredrik Nyberg Brodda
    Commented Mar 22, 2023 at 14:25

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .