> < ^ Date: Fri, 31 May 1996 08:12:00 +0100 (MET)
> < ^ From: Heiko Theissen <heiko.theissen@math.rwth-aachen.de >
< ^ Subject: Re: Lattices of intermediate subgroups

Dear Gap forum,

Vitaliy Mysovskikh has asked about a way to compute a right
transversal for the normaliser of a given permutation group. The
general way to produce a right transversal in GAP is to say

gap> RightTransversal( supergroup, subgroup );

which will return the right transversal as a list. This works
reasonably for permutation groups of small degree. For example, if you
want to loop over all conjugates of $H$ in $G$, it should be faster to
loop over `RightTransversal( G, Normalizer( G, H ) )' and form the
conjugate $H^x$ for each transversal element $x$ than to perform an
orbit algorithm with `Orbit( G, H )'. The latter makes $G$ act on
$\{H^x | x\in G\}$ by conjugation and has to check repeatedly whether
a conjugate of $H$ is new in the orbit, thereby comparing it to all
the groups in the orbit.

You cannot, however, let a group operate on such a right transversal
list via `OnRight', because the product of a right transversal element
with an arbitrary group element need not belong to the transversal
again. This problem can be overcome by replacing the right transversal
by a ``canonical right transversal'' and the operation `OnRight' by an
operation `opr' which is defined by the two properties

opr( c, g ) is in the same right coset as c*g and
opr( c, g ) is in the canonical right transversal again.

An example:

gap> s := SymmetricGroup( 4 );; u := SylowSubgroup( s, 2 );;
gap> c := CanonicalRightTransversal( s, u );
[ (), (2,3), (2,4,3) ]
gap> opr := OnCanonicalCosetElements( s, u );
function ( a, b ) ... end
gap> Operation( s, c, opr );
Group( (1,2), (1,3), (2,3) );

This method of operating on right cosets is faster than the method

gap> Operation( s, RightCosets( s, u ), OnRight );

I hope this helps,

Heiko Thei{\ss}en

> < [top]