> < ^ From:

^ Subject:

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

> < [top]