Timeline for Examples of "natural" finitely generated groups with an undecidable conjugacy problem
Current License: CC BY-SA 4.0
16 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Dec 2, 2020 at 6:59 | vote | accept | Ville Salo | ||
| Sep 22, 2020 at 11:51 | comment | added | Benjamin Steinberg | OK. I remembered a reduction to F_2xF_2 but didn't remember the details | |
| Sep 22, 2020 at 7:07 | comment | added | Ville Salo | @BenjaminSteinberg: The undecidability of the conjugacy problem in semidirect products $\mathbb{Z}^d \rtimes F_m$ by Sunic-Ventura uses orbit-undecidability, which comes from a result of ddd.uab.cat/pub/prepub/2007/hdl_2072_9160/Pr766.pdf which in turn uses $F_2 \times F_2$ and Mihajlova's trick. | |
| Sep 21, 2020 at 18:48 | comment | added | Benjamin Steinberg | You can embed F_2 in GL_2 and hence F_2xF_2 into GL_4 by direct sum. They my belief is they embed the undecidable issues of F_2xF_2 in the orbit problem but maybe I am wrong | |
| Sep 21, 2020 at 18:41 | comment | added | Ville Salo | (On a second reading, I guess you were suggesting something more specific with your comment which I didn't understand, and were just stating the embeddability in GL$_4(\mathbb{Z})$ as a fact.) | |
| Sep 21, 2020 at 18:39 | comment | added | Ville Salo | @BenjaminSteinberg: Certainly $F_2 \times F_2$ at least embeds in GL$_6(\mathbb{Z})$. But not the other way around, and I was precisely hoping for something slightly simpler than the semidirect product example (which I learned about from an MO post of yours). | |
| Sep 21, 2020 at 16:26 | comment | added | Benjamin Steinberg | I think these F2xF2 examples are also related to the free abelian group semidirect product free group examples. I vaguely remember a talk by Ventura and he said something to that effect maybe using that F_2xF_2 ends in GL_4(Z). This may be nonsense. It was long ago | |
| Sep 21, 2020 at 15:55 | comment | added | Carl-Fredrik Nyberg Brodda | @YCor I don't understand the examples well; they are quite artificial, and tie together several constructions, but the overall strategy is not too different from the membership problem, afaik. | |
| Sep 21, 2020 at 15:53 | history | edited | Carl-Fredrik Nyberg Brodda | CC BY-SA 4.0 |
Added reference to F2xF2
|
| Sep 21, 2020 at 15:38 | comment | added | Carl-Fredrik Nyberg Brodda | @VilleSalo Miller gives explicit generators and relations (modulo the generators and relations for a f.p. group with undecidable word problem). It should not be too horrible to work through to get an explicit presentation (and also Bass-Serre tree), though I have not done this. | |
| Sep 21, 2020 at 15:35 | comment | added | YCor | @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). | |
| Sep 21, 2020 at 15:30 | comment | added | Ville Salo | Gotcha! I did realize this has nicer generators (presumably). | |
| Sep 21, 2020 at 15:29 | comment | added | Carl-Fredrik Nyberg Brodda | 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. | |
| Sep 21, 2020 at 15:29 | comment | added | Ville Salo | (I guess this is, nicer in a different direction.) | |
| Sep 21, 2020 at 15:28 | comment | added | Ville Salo | This is nice, but not quite as nice as I understood from the comments, i.e. literal subgroup of RAAG. | |
| Sep 21, 2020 at 15:24 | history | answered | Carl-Fredrik Nyberg Brodda | CC BY-SA 4.0 |