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.