Dear GAP users,

Barry Monson wants to compute the normaliser in a permutation group
<G> of a sub*set* <T>. There is no function for this special purpose
built into GAP. However, there are several more general functions that
can be applied to this problem.

*** Numbers 1 to 3 apply to an arbitrary group <G>. ***

1. <G> acts by conjugation on the union of the conjugacy classes of
the elements in <T>, and in this representation the set normaliser is
simply a set stabiliser. To convert the result back to <G>, an
operation homomorphism is used.

classes := List( T, t -> Orbit( G, t ) );
newdomain := Union( classes );
newT := Set( List( T, t -> Position( newdomain, t ) ) );
O := Operation( G, newdomain );
hom := OperationHomomorphism( G, O );
S := Stabilizer( O, newT, OnSets );
N := PreImage( hom, S );  # <N> is the set stabilizer of <T>

This method has several bottlenecks, however. First, if the classes
are large the domain will take up much storage space; also the
conversion done by 'Operation' will take some time since it requires
applying every generator of <G> to every element of <newdomain> and
finding the result in the list <newdomain> again. Second, the degree
of <O> will be the size of <newdomain> --- probably much more than the
degree of <G>, and this will slow down 'Stabilizer'. Third, the set
stabilizer routine is still a backtrack, and the set stabilizer is a
really hard problem, so it may not be faster than methods below.

As an example, take <G> the Mathieu group of degree 11 and <T> a set
containing one element from each of the two 8-classes. Then the set
stabilizer on the 1980 elements from both 8-classes takes about 6
minutes and the preimage under the operation homomorphism takes one
more minute. (Your timing may vary.)

2. Steve Linton has suggested the simplest solution, namely to use

T := Set( T );
Stabilizer( G, T, OnSets );

At the present stage, this setting (operation on sets of group
elements) causes GAP to invoke the all-purpose stabilizer routine
which calculates the orbit and applies Schreier's subgroup theorem.
Since the elements of the orbit are sets of group elements, the orbit
can become quite large: in the example of the last paragraph, the
orbit has length 990 and the calculation takes about 30 seconds.

While method 1 requires an orbit whose length is the sum of the class
lengths, this approach involves an orbit whose length can be much
greater, so in other examples with more than two elements in <T> it
will probably be slower than method 1.

However, the set normaliser must preserve certain invariants (like the
order) of the elements, so it may be possible to partition <T> into
smaller sets <T_i> such that the set normaliser of <T> is just the
intersection of the set normalisers of <T_i>. This leads to an
iterative method.

3. With both methods, the computation will be faster if the normaliser
of <T> is computed not in <G> but instead in a smaller group <N> which
still contains the normaliser. Such a smaller group is, for example,
the normaliser of the subgroup generated by <T>, so in method 2 one
could write

T := Set( T );
N := Normalizer( G, Subgroup( G, T ) );
Stabilizer( N, T, OnSets );

One could also calculate normalisers of subgroups generated by all <t>
in <T> which have a certain order (cf. the <T_i> from the last
paragraph) and intersect these various normalisers.

*** Numbers 4 and 5 only apply if <G> is a permutation group. ***

4. The function 'PermGroupOps.SubgroupProperty( G, prop )' will
calculate the fulfilling subgroup of any property <prop>, provided
that the fulfilling set *is* a subgroup. <prop> must be a GAP function
that returns 'true' or 'false', so in this case one could write

T := Set( T );
PermGroupOps.SubgroupProperty( G, g -> OnSets( T, g ) = T );

This is much faster than the previous methods, it takes only 7 seconds
in the M_11-example.

5. 'PermGroupOps.SubgroupProperty' can be given a third argument,
which must be a subgroup of the subgroup in question. This will speed
up the backtrack search which 'SubgroupProperty' performs. For
example, the centraliser of the subgroup generated by <T> is such a
subgroup, and it can be computed as

C := Centralizer( G, Subgroup( G, T ) );
PermGroupOps.SubgroupProperty( G, g -> ..., C );

If the elements of <T> all have distinct orders, then <C> is equal to
the set normaliser.

If 'PermGroupOps.SubgroupProperty' is called with the normaliser <N>
instead of <G> and with the centraliser <C> as known subgroup, the
computation of the M_11-example takes less than half a second.

Hope this helps, Heiko Theissen

---------------------------------------------------------------------------
Heiko Thei{\ss}en,    Heiko.Theissen@Math.RWTH-Aachen.DE,    +49 241 804551
Lehrstuhl D f\"ur Mathematik, Templergraben 64, RWTH, 52056 Aachen, Germany