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
    Commented May 1, 2020 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
    Commented May 1, 2020 at 9:27
  • $\begingroup$ @Arthur of the same type and with the same relations $\endgroup$
    – Hagen von Eitzen
    Commented May 1, 2020 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
    Commented May 1, 2020 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$
    – anon
    Commented May 1, 2020 at 9:35

1 Answer 1

Reset to default
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
    Commented May 1, 2020 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
    Commented Jun 20, 2020 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
    Commented Jun 20, 2020 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
    Commented Jun 20, 2020 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
    Commented Jun 21, 2020 at 20:08

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .