> < ^ Date: Fri, 05 Jul 1996 16:52:00 +0100 (MET)
> < ^ From: Heiko Theissen <heiko.theissen@math.rwth-aachen.de >
^ Subject: Re: Finding transversal elements for an orbit

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;
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]