6
$\begingroup$

I am looking for natural groups with undecidable conjugacy problem. By natural, I mean that the word problem should be decidable, and the group should be given by some natural action. I know that $\mathbb{Z}^d \rtimes F_m$ (with a suitable action of $F_m$) has undecidable conjugacy problem. That's very nice, but I'd like to know other examples. I do not care about finite presentation, and I'm also fine with the group being a f.g. subgroup of something natural and geometric, which maybe simplifies things. A concrete case I was not able to resolve is whether all f.g. subgroups of right-angled Artin groups have decidable conjugacy problem.

Šunić, Zoran; Ventura, Enric, The conjugacy problem in automaton groups is not solvable., J. Algebra 364, 148-154 (2012). ZBL1261.20034.

Improve this question
$\endgroup$
9
  • 1
    $\begingroup$ It's trivial that all f.g. subgroups of RAA groups have decidable word problem. If you meant conjugacy, it's known that some f.g. subgroup of $F_2\times F_2$ has unsolvable conjugacy problem. $\endgroup$
    – YCor
    Commented Sep 21, 2020 at 12:55
  • $\begingroup$ It was indeed a typo. Your latter sentence then solves my question completely. Could you write it out? Apologies if this was too easy. $\endgroup$
    – Ville Salo
    Commented Sep 21, 2020 at 13:00
  • $\begingroup$ You can find a reference to the $F_2 \times F_2$ result in C.F.'s Miller's book/thesis from 1971. Miller also showed that if $S_1$ and $S_2$ are recursively enumerable subsets of $\mathbb{N}$, then $S_1$ is Turing reducible to $S_2$ if and only if there exists a f.g. recusrively presented group whose word problem has the Turing degree $S_1$ and whose conjugacy problem has the Turing degree of $S_2$. You might be interested in this (and the construction is rather straightforward modulo the naturality of a group with undecidable conjugacy problem). $\endgroup$
    – Carl-Fredrik Nyberg Brodda
    Commented Sep 21, 2020 at 15:15
  • $\begingroup$ Thanks, I was not aware of the reference! The latter result I've heard of, can you do that in a RAAG as well, or is there some HNN magic or the like? $\endgroup$
    – Ville Salo
    Commented Sep 21, 2020 at 15:18
  • 1
    $\begingroup$ My own interpretation of the fact that there are f.g. subgroups of $F_2\times F_2$ with undecidable conjugacy problem, is not that they are "natural" instances of f.g. groups with undecidable conjugacy problem, but rather that they are "non-natural" f.g. subgroups of $F_2\times F_2$... of course "natural" is subjective! $\endgroup$
    – YCor
    Commented Sep 21, 2020 at 20:40

1 Answer 1

Reset to default
4
$\begingroup$

Chuck Miller in [Miller, Charles F., III On group-theoretic decision problems and their classification. Annals of Mathematics Studies, No. 68. Princeton University Press, Princeton, N.J.; University of Tokyo Press, Tokyo, 1971] proves the following two rather nice and natural examples.

Theorem III.10. The free product of two free groups with finitely generated amalgamation can have unsolvable conjugacy problem. Further, the finitely presented HNN extension of a free group can have unsolvable conjugacy problem.

(Note that Miller calls HNN extensions 'Strong Britton extensions').

Now by Bass-Serre theory, there is a natural action of an amalgamated free product/HNN on the associated Bass-Serre tree, which should satisfy your "natural action" criterion.

Edit: The result mentioned by YCor can also be found in Miller's book.

Theorem III.23 The group $F_2 \times F_2$ has a finitely generated subgroup with undecidable conjugacy problem.

An important side remark, however, is that $F_2 \times F_2$ itself has decidable conjugacy problem, as do all RAAGs, in linear time. See [Crisp, John; Godelle, Eddy; Wiest, Bert; The conjugacy problem in subgroups of right-angled Artin groups. J. Topol. 2 (2009), no. 3, 442–460.].

Improve this answer
$\endgroup$
13
  • $\begingroup$ This is nice, but not quite as nice as I understood from the comments, i.e. literal subgroup of RAAG. $\endgroup$
    – Ville Salo
    Commented Sep 21, 2020 at 15:28
  • $\begingroup$ (I guess this is, nicer in a different direction.) $\endgroup$
    – Ville Salo
    Commented Sep 21, 2020 at 15:29
  • $\begingroup$ This is a different example. There are also f.g. subgroups of $F_2 \times F_2$ which have undecidable conjugacy problem; I wanted to give YCor some time to write that answer up. $\endgroup$
    – Carl-Fredrik Nyberg Brodda
    Commented Sep 21, 2020 at 15:29
  • $\begingroup$ Gotcha! I did realize this has nicer generators (presumably). $\endgroup$
    – Ville Salo
    Commented Sep 21, 2020 at 15:30
  • $\begingroup$ @Carl-FredrikNybergBrodda no, feel free to expand your own post, I don't need to answer just to provide a reference. Actually I don't know these examples (unlike the membership issue in f.g. subgroups of $F_2^2$ which I understand). $\endgroup$
    – YCor
    Commented Sep 21, 2020 at 15:35

You must log in to answer this question.

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