# How to find a particular element of $S_n$ that conjugates one subgroup to another

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.

• 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$. – Hagen von Eitzen May 1 '20 at 9:25
• 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. – Arthur May 1 '20 at 9:27
• @Arthur of the same type and with the same relations – Hagen von Eitzen May 1 '20 at 9:28
• @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. – Arthur May 1 '20 at 9:30
• 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. – runway44 May 1 '20 at 9:35

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.

• 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. – Junglemath May 1 '20 at 9:46
• @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. – Derek Holt Jun 20 '20 at 11:08
• @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? – Junglemath Jun 20 '20 at 14:42
• 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. – Derek Holt Jun 20 '20 at 16:49
• 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$. – Derek Holt Jun 21 '20 at 20:08