> < ^ From:

< ^ Subject:

Dear GAP forum,

Heiko Theissen wrote:

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.)

(Remainder deleted)

I remember reading about the CAYLEY `SymmetricNormalizer' function some

time ago (I can't remember where, unfortunately - it might have been

in Butler's article on computing normalizers in permutation groups,

on which the current GAP code seems to be based.) My memory is that

`SymmetricNormalizer' is a significantly different algorithm due originally

(like many others) to Charles Sims.

A transitive permutation group G gives rise to a number of directed or

undirected graphs, each one based on one of the orbits of the stabilizer of G,

and G acts as an automorphism group of each of these grapohs. The normalizer

of G in the symmetric group (or indeed any of its subgroups) acts in a

well-defined way on these graphs (it may permute them among themselves), and

this information can be used to restrict the backtrack search for the

normalizer. Since, in the case of a 2-transitive group, there is only one

graph and it is complete, it provides no useful information. I presume that

the strategy is to go down to a point stabilsier in that case, and use its

graphs.

I don't think there was any particular reason why this was only coded in

CAYLEY for the symmetric group. It was probably just done for that case, and

further work on it got postponed indefinitely.

It is true that SymmetricNormalizer returns the answer almost immediately

for Sz(8) (I just tried it), and other similar examples where there is

plenty of information to be got out of the graphs. Unfortunately, it is not

likely to be easy to combine the SymmetricNormalizer algorithm with the

one currently in GAP, since they involve rather different structures.

In any case, there are examples in which both methods fail miserably, the

most obvious being when the group acts regularly (transitively and with

trivial stabilizer), in which case there is no combinatorial information

to help you at all. In such cases (and others as well), one needs to use

group theory rather than combinatorics, and make use of the fact that the

normalizer of G is inducing automorphisms of G. (This is essentially the

method proposed by Heiko Theissen for Sz(8) in the remainder of his letter,

but it has the disadvantage that the user needs to supply information

relevant to the particular example.) I wrote a standalone normalizer

program a few years ago that performed particularly well on regular

groups. Unfortunately, as it stands, it is rather slow on Sz(8), which

has a particuarly bad orbit structure (all orbits of the 2-point stabiliser

have the same length).

It would be nice, in the long term, to have a normalizer function (and

perhaps a related function for testing conjugacy of subgroups in

permutation groups), that worked without complete disaster for all

groups up to degree 100, say!

Derek Holt.

> < [top]