Dear GAP forum,

Peter M"uller has asked in the GAP forum whether there is a special
normaliser function in GAP for normalisers in the symmetric group,
similar to `SymmetricNormalizer' in CAYLEY. Well, in GAP-3.4 there isn't.

I can imagine only one advantage that you have from the symmetric group:
you do not have to set up a stabiliser chain for S_n, because you know
that every element you will enumerate during the backtrack search is in
S_n. In GAP-3.4, only setting up a stabiliser chain for S_n takes a
considerable amount of time (12 sec for S_25, 180 sec for S_50 on our
machine). In the next release of GAP (which will be the first release of
GAP-4), we will avoid the stabiliser chain construction in the case of a
symmetric group.

I have asked Peter M"uller with separate mail to give an example where
GAP's normaliser function is unusably slow. He has told me that he wanted
to compute the normaliser of Sz(8) on 65 points in the symmetric group.
This subgroup is doubly transitive, and this makes it harder to think of
methods which allow substantial pruning of the search tree through which
the backtrack algorithm for `Normalizer' has to run. (A prototype of the
normaliser function to be released with GAP-4 does this calculation in
about 15 seconds, but it cannot do so well for all 2-transitive
subgroups.)

There is an alternative approach to this particular problem which can be
realised in GAP-3.4: Since Sz(8) is a simple group, its outer
automorphism group is known, it is of order 3. If one has a generating
automorphism for this cyclic group, it only remains to test whether it
can be realised in S_65. The following commands do this:

gap> S := SymmetricGroup(65);;
gap> G := <Suz(8) on 65 points>;;

# `PermGroupOps.RationalClasses' is too slow on <G>, so ...
gap> G.rationalClasses := GroupOps.RationalClasses( G );;

# `AutomorphismGroup' needs `<G>.rationalClasses'.
gap> aut := AutomorphismGroup( G );;
gap> out := aut.generators[4];;

# The following function is probably too slow, better use the function
# below instead.
gap> x := RepresentativeOperation( S,
> out.generators, out.genimages, OnTuples );;

The function makes use of the following lemma:

Let $G$ and  $H\le S_n$ be transitive  groups, $G_1$ and $H_1$ the  point
stabilisers and  $f:  G ->  H$  an isomorphism.  Then  $f$ is realised by
conjugation in  $S_n$ if and only  if $f(G_1)$ is  conjugate to  $H_1$ in
$H$.

#########################################################################
##
#F  AutomorphismByConjugation( <Omega>, <d>, <e> ) do auto by conjugation
##
AutomorphismByConjugation := function( Omega, d, e )
    local   bpt,  aut,  D1,  E1,  fix,  Imega,  sliced,  pnt,  img,  j;

aut := GroupHomomorphismByImages( Group( d, () ), Group( e, () ),
                                  d,              e );
aut.coKernel := TrivialSubgroup( aut.source );
if not IsTransitive( aut.source, Omega )  then
    Error( "<d> and <e> must generate transitive subgroups of <G>" );
elif not IsTransitive( aut.range, Omega )  then
    return false;
fi;

bpt := Omega[ 1 ];
D1 := Stabilizer( aut.source, bpt );
E1 := Image( aut, D1 );
if PermGroupOps.NrMovedPoints( E1 ) = Length( Omega )  then
    return false;
fi;
fix := First( Omega, p ->
              ForAll( E1.generators, gen -> p ^ gen = p ) );

# The  automorphism <aut> maps  <d>_bpt  to <e>_fix, so permutes  the
# points. Find an element in <G> with the same action.
Imega := [  ];
for pnt  in Omega  do
    sliced := [  ];
    while pnt <> bpt  do
        Add( sliced, aut.transimages[ pnt ] );
        pnt := pnt ^ aut.transversal[ pnt ];
    od;
    img := fix;
    for j  in Reversed( [ 1 .. Length( sliced ) ] )  do
        img := img / sliced[ j ];
    od;
    Add( Imega, img );
od;

return MappingPermListList( Omega, Imega );
end;

gap> x := AutoByConjugation( [ 1..65 ], out.generators, out.genimages );
( 1,27,51)( 2,43, 7)( 3,12,56)( 4,39,60)( 5,41,65)( 6,36,19)( 9,35,29)
(10,37,22)(11,23,58)(14,28,59)(15,45,55)(16,57,30)(17,61,46)(18,34,32)
(20,24,49)(21,50,54)(25,38,44)(31,48,42)(33,52,64)(47,53,62)
gap> N := Closure( G, x );;
# <N> is the normaliser.

Hope this helps, Heiko Thei{\ss}en