> < ^ From:

^ Subject:

Dear GAP forum,

Simon Norton has sent us a message (not in the GAP forum) in which he

proposes

A. a simplified way of calculating transversal elements for an orbit

of integers under a permutation group,

B. a way of calculating the $i$th element from a list of objects on

which a group operates.

This mail contains:

A. description of Simon's idea A

B. description of Simon's idea B

C. description of how GAP now does such a calculation

Function for A. a GAP function implementing Simon's idea A

Function for B. a GAP function implementing Simon's idea B* * * A. * * *

Let $G$ be a transitive permutation group acting on `[1..n]'. Assume

that, for every $p<>1$, there is an element $g_1$ of `$G$.generators'

such that $p / g_1 < p$ (i.e. the preimage of $p$ is less than $p$ in

the natural ordering). By finding such a generator and repeating this

method, one gets a word in `$G$.generators', say $g_m * ... * g_1$

such that

p / g_1 / g_2 / ... / g_m = 1,

i.e., this word is a transversal element mapping $1$ to $p$.

For this procedure, we do *not* require an orbit calculation, we only

have to know that our ``general assumption'' about the existence of

such generators is true. This is, for example, always the case if the

permutation group $G$ was constructed from another group $H$ (acting

on the orbit of a point $pnt$) via the GAP functions `Orbit' and

`Operation':

orbit := Orbit( H, pnt, opr ); G := Operation( H, orbit, opr );

where `opr' is something like `OnPoints'. Why is this so? During the

construction of `orbit', every new point is found as the image of an

old point under one of `$G$.generators', and this new point is then

put at the end of `orbit' so that it corresponds to a higher integer

than the old point.

The same thing is true if $G$ was constructed by coset enumeration

using the function `OperationCosetsFpGroup' (section 23.5 of the GAP

manual).

* * * B. * * *

The possibility of determining a word $w$ in `$G$.generators' such

that $1 ^ w = p$ also allows one to calculate the point from `orbit'

to which $p$ corresponds, if only the point $pnt$ corresponding to $1$

is known. You simply calculate $opr( pnt, w' )$ where $w'$ is the same

word as $w$, but this time evaluated in `$H$.generators', which are in

bijection with `$G$.generators'. To be more precise, `$H$.generators'

is in bijection with `$G$.operation.genimages'.

* * * C. * * *

What does GAP currently do if you ask it for a transversal element in

$G$ mapping $1$ to $p$?

First, GAP constructs the orbit of $1$ under $G$ and locates $p$ in

it. Then it traces back the generators used to reach $p$ in the orbit

construction, just like described above. This method could be

interpreted as a re-construction of $G$:

orbit := Orbit( G, 1, OnPoints );

G := Operation( G, orbit, OnPoints );

after which $G$ fulfills the ``general assumption''. The point is,

however, that this additional `orbit' calculation may be unnecessary,

if $G$ already fulfilled the ``general assumption'' from the

beginning.

Second, and much more serious: GAP not only constructs the orbit of

$1$, but also the stabiliser of $1$, i.e., a whole stabiliser chain.

This would only be necessary if we were looking for transversal

element mapping $1$ to $p$ and $2$ to $q$ etc. In our case, it is

simply superfluous and may take quite some time.

* * * Function for A. * * *

What can you do if you do not want to wait so long?

1. If you want to avoid a stabiliser chain construction and just need

a transversal element in $G$ mapping $a$ to $b$, you can use the

following function:

TransversalElement := function( G, a, b ) local S, t; S := rec( generators := [ ], identity := G.identity ); S.stabilizer := Copy( S ); S.orbit := [ a ]; S.transversal := [ ]; S.transversal[ a ] := S.identity; PermGroupOps.AddGensExtOrb( S, G.generators ); t := S.identity; while b <> a do t := S.transversal[ b ] mod t; b := b ^ S.transversal[ b ]; od; return t; end; It returns a permutation $t$ for which $a ^ t = b$.

2. If you do not want a permutation $t$, but rather a word in

`$G$.generators', replace the line

t := S.identity; by t := [ ]; and t := S.transversal[ b ] mod t; by Add( t, Position( G.generators, S.transversal[ b ] ) );

This gives you a list [ t_1, ..., t_n ] such that

G.generators[t_1] * ... * G.generators[t_n]

maps $b$ *back* to $a$.

3. If you even know that the ``general assumption'' is fulfilled,

e.g., if $G$ was constructed by `Orbit' and `Operation', you can use

the following code, which is due to Simon Norton:

TransversalElement1 := function( G, p ) local t, i; t := G.identity; # or: t := [ ]; while p <> 1 do i := First( [ 1 .. Length( G.generators ) ], i -> p / G.generators[ i ] < p ); t := G.generators[ i ] mod t; # or: Add( t, i ); p := p / G.generators[ i ]; od; return t; end; It returns a permutation $t$ such that $1 ^ t = p$. The #-variant returns a word mapping $p$ *back* to $1$.

* * * Function for B. * * *

4. If $G$ was constructed from $H$ via `Orbit' and `Operation', you

can use the ``integer word'' $t$ to calculate the point corresponding

to $p$, namely as

CorrespondingPoint := function( G, p ) local H, pnt, opr, t, i;

# If $G$ was constructed as `Operation(H,Orbit(H,pnt,opr),opr)',

# $H$, $pnt$ and $opr$ can be found in the record of $G$ (the

# manual does not tell this).

H := G.operation.structure;

pnt := G.operation.domain[ 1 ];

opr := G.operation.operation;

t := TransversalElement1( G, p ); for i in Reversed( [ 1 .. Length( t ) ] ) do pnt := opr( pnt, H.generators[ t[ i ] ] ^ -1 ); od; return pnt; end;

If you use this function, you must use the variant of

`TransversalElement1' where $t$ is a list, and you have to replace

`G.generators' by `G.operation.genimages' everywhere in the function

`TransversalElement1' to ensure the bijective correspondence with

`H.generators'.

* * *

We will consider to incorporate some these ideas in the next version

of GAP (GAP-4).

I hope this helps,

Heiko Thei{\ss}en

> < [top]