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