| | | **Actions of the form **_{G}X |

#### Actions of the form _{G}X

Given a permutation group *G* acting on the set *X:={1,...n} *, we use *Schreier vectors*
for describing the orbits of *G* on *X*. These orbits will
be labelled as *1,2,...,|G\\X|*.
With such a group action _{G}X we associate 5 VECTORs.
There are 3 VECTORs of length *|X|*, namely
`SVorbit`

,
`SVlast`

and `SVgen`

.
The VECTOR `SVorbit`

gives for each *iÎX* the number of the orbit *w* such that
*iÎw*. (In other words the number of the orbit *G(i)* is
the INTEGER object `S_V_I(SVorbit,i-1L)`

.)
The other two VECTORs of length *|X|*
are used for describing how an arbitrary
element of the orbit can be reached through a path labelled by
generators of the group when applied to the standard
representative of the orbit. For a standard representative *i*
both `S_V_I(SVlast,i-1L)`

and `S_V_I(SVgen,i-1L)`

have the value *-1*. If *i* is not a standard representative
of an orbit *w*, then there is a further element *jÎw*
and a generator *g* of *G* such that *i=gj*. In this case
`S_V_I(SVlast,i-1L)`

is the number *jÎX* (*1£j£n*)
and `S_V_I(SVgen,i-1L)`

is the position
of *g* in the VECTOR of generators of the acting group *G*.
So it takes values from 0 to `S_V_LI(a)-1L`

.
Furthermore there are two VECTORs of size *|G\\X|*, namely
`Ofirst`

and `Osize`

.
The standard representative of the orbit *w* labelled by
*iÎ{1,...,|G\\X|} * is given by
`S_V_I(Ofirst,i-1L)`

, whereas the number of elements
in this orbit is given by
`S_V_I(Osize,i-1L)`

.

You can compute these VECTORs using the routine

INT all_orbits(g,SVorbits,SVlast,SVgen,Ofirst,Osize)
OP g,SVorbits,SVlast,SVgen,Ofirst,Osize;

where `g`

is a VECTOR consisting of generators of *G*.
These generators must be PERMUTATIONs all of the same degree.
If you are only interested in the orbit representatives
you can use

INT allorbits(g,Ofirst) OP g,Ofirst;

where `g`

is a VECTOR consisting of generators of *G*.
Having the Schreier vectors at hand we can determine an element
of the group *G* which maps the standard representative of the
orbit *G(k)* of an arbitrary element *kÎX* to *k*, by using

INT trace_schreier_vectors(g,SVlast,SVgen,k,gtrace)
OP g,SVlast,SVgen,k,gtrace;

where `g`

is a VECTOR consisting of generators of *G*.
`k`

is an INTEGER object *1£k£n* and
`gtrace`

is a group element which maps
the standard representative of the orbit *G(k)* to `k`

.
Furthermore we can compute the stabilizer of the
standard representative of the orbit labelled with *k* by

INT schreier_stabilizer(g,SVorbit,SVlast,SVgen,Ofirst,Osize,k,stab)
OP g,SVorbit,SVlast,SVgen,Ofirst,Osize,k,stab;

where `g`

is a VECTOR consisting of generators of *G*.
Please take care that
`k`

is the label of an orbit (i.e. an element of
*{1,...,|G\\X|} *) and not the
standard representative of an orbit. A VECTOR of
generators of the stabilizer of the
standard representative of this orbit is computed as
`stab`

. The stabilizer of any other element of this orbit
is conjugated to `stab`

.

harald.fripertinger@kfunigraz.ac.at,

last changed: November 19, 2001

| | | **Actions of the form **_{G}X |