> < ^ From:

> < ^ Subject:

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

> < [top]