Timeline for Examples of "natural" finitely generated groups with an undecidable conjugacy problem
Current License: CC BY-SA 4.0
13 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Dec 2, 2020 at 6:59 | vote | accept | Ville Salo | ||
| Sep 24, 2020 at 9:41 | comment | added | user1729 | (This is probably related to the $F_2\times F_2$ example, although Martino and Minasyan do use properties of hyperbolic groups in their proof. However, their proof is pleasantly short, and the properties used are pretty basic (e.g. an element has finite index in its centraliser, etc.) so it may generalise.) | |
| Sep 24, 2020 at 9:38 | comment | added | user1729 | If $N$ is a finitely generated torsion-free normal subgroup of a hyperbolic group $H$ such that $H/N$ has undecidable word problem, then $N$ has undecidable conjugacy problem. Therefore, Rips' construction gives many examples of f.g. groups with decidable word problem but undecidable conjugacy problem. (However, the groups are not f.p., and their "natural"-ness is debatable!). Reference is: Theorem 1.2 of A. Martino, and A. Minasyan. "Conjugacy in normal subgroups of hyperbolic groups." Forum Mathematicum. Vol. 24. No. 5. De Gruyter, 2012 (doi). | |
| Sep 22, 2020 at 4:48 | comment | added | Ville Salo | @YCor: We agree, it's just that this question is a compromise between a good question of general interest and me actually just needing a very specific thing for boring reasons. | |
| Sep 21, 2020 at 20:40 | comment | added | YCor | 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! | |
| Sep 21, 2020 at 15:33 | comment | added | YCor | References to Miller are [19] and [20] here: arxiv.org/abs/0708.4331 | |
| Sep 21, 2020 at 15:24 | answer | added | Carl-Fredrik Nyberg Brodda | timeline score: 4 | |
| Sep 21, 2020 at 15:18 | comment | added | Ville Salo | 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? | |
| Sep 21, 2020 at 15:15 | comment | added | Carl-Fredrik Nyberg Brodda | 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). | |
| Sep 21, 2020 at 13:00 | history | edited | Ville Salo | CC BY-SA 4.0 |
added 5 characters in body
|
| Sep 21, 2020 at 13:00 | comment | added | Ville Salo | It was indeed a typo. Your latter sentence then solves my question completely. Could you write it out? Apologies if this was too easy. | |
| Sep 21, 2020 at 12:55 | comment | added | YCor | 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. | |
| Sep 21, 2020 at 12:41 | history | asked | Ville Salo | CC BY-SA 4.0 |