3
$\begingroup$

Suppose you have two subgroups $H, K$ of $S_n$ that are given to be conjugate. How do you go about finding an element $\sigma$ of $S_n$ such that $\sigma H \sigma^{-1} = K$?

For two elements $\alpha, \beta$ of $S_n$, I know that they are conjugate if and only if they have the same cycle type, and I know how to find an element $\tau$ such that $\tau \alpha \tau^{-1} = \beta$. I would write the cycle decompositions for both $\alpha$ and $\beta$ in nondecreasing order of lengths of their cycles (including 1-cycles), and define $\tau$ to be the permutation that takes $a_i$ in $\alpha$ to the $b_i$ in $\beta$ in the corresponding position. But for a subgroup, how would this procedure work? Or does this not work? Is it easier to do if a generating set is known for $H$?

EDIT: I should mention that two specific subgroups of $S_8$ were given, a generating set is known for both $H$ and $K$, and I saw that someone came up with a $\sigma$ that worked, but there was no indication of how $\sigma$ was found, which is what I'm really after here.

$\endgroup$
5
  • $\begingroup$ The problem is, even if you find $\alpha\in H$ and $\beta\in K$ of same cycle type and use that to find $\sigma$ with $\sigma\alpha\sigma^{-1}=\beta$, this does not imply $\sigma H\sigma^{-1}=K$. Not only do you have a lot of choice in picking $\sigma$ (order of same-length cycles, first element of each cycle), but it may even happen that $\alpha$ is not conjugate to $\beta$ under any $\sigma$ that conjugates $H$ to $K$. $\endgroup$ – Hagen von Eitzen May 1 '20 at 9:25
  • 2
    $\begingroup$ I think what you need is a generating set of $H$, and a generating set of $K$ of "the same type", and then go from there. That ought to work. $\endgroup$ – Arthur May 1 '20 at 9:27
  • $\begingroup$ @Arthur of the same type and with the same relations $\endgroup$ – Hagen von Eitzen May 1 '20 at 9:28
  • $\begingroup$ @HagenvonEizen When I say the entire generating set, and not just the separate elements, is of the same type, that's what I meant. I was thinking more extrinsic in terms of corresponding overlaps between the elements and whatnot, but that might be a bit too cumbersome to spell out explicitly. So your intrinsic formulation is probably better. $\endgroup$ – Arthur May 1 '20 at 9:30
  • $\begingroup$ In principle, it's possible for $H=\langle X\mid R(X)\rangle$ and $K=\langle Y\mid R(Y)\rangle$ to be conjugate subgroups with the same presentation and yet there not to exist a $\sigma\in S_n$ for which $Y=\sigma X$. The general answer is probably too broad as there are likely way too many different techniques or ideas applicable to way too many different situations. $\endgroup$ – runway44 May 1 '20 at 9:35
2
$\begingroup$

For finite $G$ and $H,K\le G$, the following algorithm suggests itself:

  1. Pick a set $S$ of generators of $H$.
  2. Let $X$ be a set of representatives of $G/H$
  3. For each $h\in S$, loop over all $g\in X$ and check whether $ghg^{-1}\in K$. If not, remove $g$ from $X$ (i.e., set $X\leftarrow X\setminus\{g\}$).
  4. Terminate with answer "$gHg^{-1}=K$ iff $g\in XH$".

Some simplifications may be possible for the case of $G=S_n$. For example, if instead of an oracle that tells us whether a group element is $\in K$, we may have use the oracle that enumerates all elements of $K$ of the desired cycle type and enumerates all $g\in G$ for which $ghg^{-1}$ equals one of them. We'd still have to perform intersection with $X$, and that may not be easier than the method of the algorithm.

$\endgroup$
9
  • 1
    $\begingroup$ So if $G = S_8$, $H$ is a subgroup of order 8, and two generators, $|X| = 5040$, step 3 would involve $2 \times 5040$ steps. Not very practical, for a human at least. $\endgroup$ – Junglemath May 1 '20 at 9:46
  • 1
    $\begingroup$ @Junglemath Yes, but there is no essentially better method known of doing this. The complexity of this problem is believed to be exponential in $n$. There are lots of heuristic tricks you can use to speed up computer implementations (for example, a conjugating element must map the orbits of $H$ to the orbits of $K$), but you would need to learn the basics of computational group theory to understand that. $\endgroup$ – Derek Holt Jun 20 '20 at 11:08
  • $\begingroup$ @DerekHolt Somehow I think there should be a way to do this by hand, considering it's an exercise in Dummit and Foote. Unless they want you to use trial and error? $\endgroup$ – Junglemath Jun 20 '20 at 14:42
  • $\begingroup$ I am sure there is, but you asked a general question not a specific question. You haven't even said what $H$ and $K$ are in the exercise. $\endgroup$ – Derek Holt Jun 20 '20 at 16:49
  • 1
    $\begingroup$ Maybe I was lucky, but my first attempt worked - I tried (2 3 5)(4 7 6), which conjugates (1 2 3 4)(5 8 7 6) to (1 3 5 7)(2 8 6 4), and it also conjuages $H$ to $K$. $\endgroup$ – Derek Holt Jun 21 '20 at 20:08

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.