Dear GAP-Forum,

Sebastian Egner wrote:

# the PermGroupOps.Normalizer function of gap3r4p1 may be
# improved to handle cyclic groups of low degree more efficiently.
# Maybe this has already been done in a later releases?

[code omitted]

First, I'd like to thank you for providing your code. Indeed the
original normalizer performs abysmal in such situations (for ex-
ample take the normalizer of Z_23 in M_23), your routine shows
that this can be enormously improved. As it might be of interest,
some comments about the normalizer routine:

>From version 3.4 to 3.4.1 the normalizer has not undergone major
improvements. Our current development version contains a greatly
improved normalizer routine, written by Heiko Theissen. (The rou-
tines use partition backtrack methods, introduced by Jeffrey
Leon.) The new routines are to be released with GAP 4, mainly be-
cause they utilize small but subtle changes in the stabilizer
chain concept to be introduced then. These new routines usually
yield (based on my experiences with them) a speedup of 2 or more
when applying the routines for normalizers in the symmetric group
(or large wreath products). The improvement for cyclic groups is
even higher: For example the normalizer N_G(U) for

# as smaller degrees are too fast for timing
G:=SymmetricGroup(100);
U:=Subgroup(G,[Product(G.generators)]);

takes (on a 50Mhz 486PC) 3200ms in our experimental version.
(I did not want to wait for the 3.4 version, it certainly will
be MUCH slower ...) Your version, however, takes only 800ms on
the same machine.

Your observation remains valid even in a more general context: If
U<=G, then N_G(U)/C_G(U) is isomorphic to a subgroup of Aut(U).
Centralizer computations are easier than normalizer computations.
Thus if we know enough about the automorphism group to
guess subgroups (close supergroups) for N_G(U)/C_G(U), then
we can take these subgroups and check which subgroups are actu-
ally induced by G-conjugation. For this purpose we'll have to
find representatives of conjugating elements. This is however
again in cost similar to centralizers. So, if the automorphism
group is smaller in size than G, it might be worth to use this
approach.

For cyclic groups your algorithm implements this, guessing the
whole automorphism group and searching for suitable elements. If
|U| becomes larger this might also become expensive. An easy im-
provement is to run through all subgroups of Aut(U) (which are
easily parametrized) and to check for subgroup generators if they
are induced by conjugacy in $G$. (This is described in more de-
tail in: G.Butler, An inductive scheme for computing conjugacy
classes in permutation groups, Math. Comp. 62 (1994), 363--383.)
Thus the loop

for k in PrimeResidues(r) do

in your algorithm would be changed into a loop over subgroups of
Z_r^imes and another loop over their generators. This should give
another speedup, especially if |U| is larger. As a side effect
you get fewer generators.

One can extend this approach to abelian groups U: Here we can
take the subgroup of Aut(U), which fixes the cycle structures of
all elements in U as guessed group. Certainly it has to contain
the normalizer induced subgroup; usually it is much smaller. When
using the permutation action of Aut(U) on U, this subgroup can be
computed as a set stabilizer. Another backtrack routine then
searches for the actual normalizer induced subgroup. It turns out
that the guessed group usually is in very good approximation to
the group we want, so we don't have to worry about this last
backtrack. I reckon it might be even worth to extend it to other
relatively small groups, however then the automorphism group is
not that easy to get.

I have implemented this approach for elementary abelian groups
(it would be not too hard to extend it to the general abelian
case, but I just needed elementary abelian). In computations for
my thesis, I usually have to compute normalizers of (Z_p)^d in
Z_p \wr S_n (n>=d). Even the faster normalizer choked on these
problems for higher (p,n),while the 'automorphism guessing' works
quite well. If there is interest for it, I can put a version for
GAP 3.4 on our ftp server.

Alexander