Let $G\le S_n$ be a permutation group and suppose that $C_1,C_2$ are two distinct conjugacy classes that have the same cardinality and is represented by a permutation of the same cycle-type. My question is whether one can (maybe by using GAP?) determine if a (non-inner) $G$-automorphism exists that maps $C_1$ to $C_2$?


Generically, you can do so in GAP with RepresentativeAction, trying to find an element in the automorphism group that maps a representative of one conjugacy class to one in the other class. (It will return fail if no such automorphism exists.) For example:

gap> g:=AlternatingGroup(6);;
gap> au:=AutomorphismGroup(g);
<group with 4 generators>
gap> RepresentativeAction(au,(1,2,3),(1,2,3)(4,5,6));
[ (2,3)(4,5), (1,2,3,4)(5,6) ] -> [ (1,3)(4,5), (1,6)(2,3,4,5) ]

Not that this calculates an orbit under the automorphism group, which can be costly in terms of memory and runtime. In larger examples it could be more efficient (i.e. faster and using less memory) to represent $G\rtimes Aut(G)$ as a permutation group and do the search there using the backtrack functionality for permutation groups, and then pull back the conjugating permutation to an automorphism:

gap> sdp:=SemidirectProduct(au,g);
gap> embau:=Embedding(sdp,1);;
gap> embg:=Embedding(sdp,2);;
gap> elms:=[(1,2,3),(1,2,3)(4,5,6)];;
gap> elmsim:=List(elms,x->ImagesRepresentative(embg,x));
gap> rep:=RepresentativeAction(Image(embau),elmsim[1],elmsim[2]);;
gap> PreImagesRepresentative(embau,rep);
[ (1,2,3,4,5), (4,5,6) ] -> [ (1,6,3,2,5), (1,3,2)(4,5,6) ]
  • $\begingroup$ In your first example the output looks more like one automorphism than the orbit under the automorphism group (or am I missing something). In any case this fully answers the existence question (if such an automorphism does not exist then I suppose I get an error). $\endgroup$ – quantum Apr 20 at 3:01
  • $\begingroup$ In the second example, could you very briefly write (or give reference) why this is more efficient for larger groups? The algorithm interests me a bit. Thanks! $\endgroup$ – quantum Apr 20 at 3:03
  • 1
    $\begingroup$ @quantum Done so. for both. The algorithm in the first case is an orbit algorithm, in the second case a backtrack search. Se, e.g. Holt/Eick/O'Brien: Handbook of Computational Group Theory, or my lecture notes math.colostate.edu/~hulpke/CGT/cgtnotes.pdf $\endgroup$ – ahulpke Apr 20 at 14:27

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.