> < ^ From:

< ^ Subject:

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]