Timeline for Conjugacy in the quaternion group
Current License: CC BY-SA 4.0
10 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Apr 29, 2020 at 17:11 | comment | added | YCor | Also here's a way to make the question meaningful, typically for Lie groups: assume that $G$ is a Polish group. Then we can ask whether there exists a Borel subset $X$ of $G^3$ such that for all conjugate $x,y$ in $G$, there exists a unique $z\in G$ such that $(x,y,z)\in X$, and moreover it satisfies $zxz^{-1}=y$. (Clearly we can always suppose that $X\subset\{(x,y,z)\in G^3:zxz^{-1}=y\}$.) Possibly there are natural variants of this, replacing the "Borel" condition by a weaker or stronger one, I haven't thought enough. | |
| Apr 29, 2020 at 8:47 | comment | added | YCor | (...) For the infinite symmetric group $S_\omega$ (of all permutations of the set $\omega=\{0,1,\dots\}$) with $g,h$ computable this can be done algorithmically if the function mapping $n$ to the (possibly infinite) length of the $g$-cycle of $n$ is computable (and the same for $h$) and in addition being on the same cycle is decidable, which I think is not always the case. | |
| Apr 29, 2020 at 8:45 | comment | added | YCor | @DerekHolt (Yes, and even for recursive presentations.) Actually I don't even think that the OP considered the problem under an algorithmic angle (as in this recent question). Another example where the "algorithm" is only in principle: if we have two conjugate elements $g,h$ in a symmetric group (finite or infinite), we "choose" a length-preserving bijection between the sets of cycles of $g$ and $h$, we choose an element in each cycle, and then can induce a conjugating element. (...) | |
| Apr 29, 2020 at 8:02 | comment | added | Derek Holt | @YCor OK, so this problem is solvable in theory for finitely (or even countably) generated groups with solvable word problem. But we seem to see a lot of questions of the type "Can we do this?" where it is not clear whether this means is this problem decidable or is there some practical algorithm to solve it. This one seems to be a mixture of both! | |
| Apr 29, 2020 at 7:54 | comment | added | YCor | @DerekHolt no, because OP takes as an assumption that the elements are conjugate, and asks to output a conjugating element. As you know, plenty of algorithmic problems (e.g., isomorphism problem for hyperbolic groups, etc) have this kind of scheme (input X, output something about X, requiring the program to work if X satisfies some property P and possibly not halt otherwise— where usually property P is not decidable). | |
| Apr 29, 2020 at 7:46 | review | Close votes | |||
| May 4, 2020 at 17:22 | |||||
| Apr 29, 2020 at 7:23 | comment | added | Derek Holt | You seem to be just asking whether a group $G$ has a solvable conjugacy problem, which is one of the three fundamental decidability problems for groups posed by Dehn in 1911. | |
| Apr 29, 2020 at 0:35 | comment | added | YCor | I'm not sure whether "can we find" makes sense in general, but if $G$ is a computable group, one has an algorithm whose input is a pair $(x,y)$, and: if $x,y$ are conjugate, outputs some $z$ with $zxz^{-1}=y$ (and if they're not conjugate possibly doesn't answer): just enumerate all $z$, test $zx=yz$ and stop when it's true. A better algorithm is when the algorithm can be improved to stop and say no (no pun intended!) when they're not conjugate. This is called solvable conjugacy problem, is well documented (and not always true for f.p. groups with solvable word problem). | |
| Apr 29, 2020 at 0:27 | answer | added | John Voight | timeline score: 4 | |
| Apr 28, 2020 at 23:54 | history | asked | Gautam | CC BY-SA 4.0 |