Orbit evaluation |

We consider a finite action * _{G}X* in order to evaluate particular orbits,
the whole set of orbits, a transversal of the orbits, stabilizers, and so
on. It is clear that for all these calculations the orbit evaluation is
basic, hence let us discuss this first.

In the case when both * | X | * and * | G | * or * | bar (G) | *
are very small
and *G* or *bar (G)* is given as a *set* together with the operation of
each of its
elements, then we may just apply this set to *x* in order to get the
desired orbit *G(x)*.
But quite often it is so that *G* is given by a set of generators:
*G=ág _{1},...,g_{r}ñ*, together with the actions of the

W_{0}:={x}, and W_{i}:=È_{j=1}^{r}g_{j}W_{i-1}, iÎN^{*}.

It is obvious that the smallest *i* such that *W _{i}=W_{i-1}*
satisfies

G(x)=W_{i-1}.

The concrete implementation of this way of evaluating *G(x)* of course may
heavily depend on our knowledge of *X,G* and * _{G}X*. For example, if

It is clear that a careful implementation of this procedure
also yields products of the generators which lead from *x* to any other
element of its orbit, and which therefore form a transversal of *G/G _{x}*.
Thus we can also obtain generators of the stabilizer

Lemma:(Schreier)IfUis a subgroup ofG=ágwhich is finite and which decomposes as follows into left cosets of_{1},...,g_{r}ñU:and if the mappingG=È_{i=1}^{s}h_{i}U, where h_{1}=1,fis defined bythenf:G -> {h_{1},...,h_{s}}:g -> h_{i}, if gÎh_{i}U,Uis generated by the elementsf(g:_{i}h_{k})^{-1}g_{i}h_{k}U=áf(g_{i}h_{k})^{-1}g_{i}h_{k}| iÎr,kÎsñ.

Proof: Assume that *u=a _{1}...a_{t}ÎU*, where the

u_{i}:=a_{i}...a_{t}, and x_{i}:=f(u_{i}),

so that in particular *x _{1}=f(u)=1*. Putting

u=(x_{1}^{-1}a_{1}x_{2})(x_{2}^{-1}a_{2}x_{3})...(x_{t}^{-1}a_{t}x_{t+1}).

Now
*x _{i}=f(u_{i})=f(a_{i}u_{i+1})=f(a_{i}x_{i+1})*,
for

u=f(a_{1}x_{2})^{-1}a_{1}x_{2}f(a_{2}x_{3})^{-1}a_{2}x_{3}...,

which completes the proof.

A direct evaluation of the stabilizer *G _{x}* will be discussed later.
In the case when

In order to evaluate this canonic transversal of *G\\ n* in an economic
way we can use a problem oriented description of the elements of

C_{bar (G)}(k):={pÎbar (G) | " iÎk:pi=i}.

We call this group the *centralizer* of
* k* in order to distinguish it from the

N_{bar (G)}(k):={pÎbar (G) | pk=k},

which we call the *normalizer* of * k*.
(Correspondingly in the general case

{1}=C_{bar (G)}(n)£C_{bar (G)}(n-1)£...£C_{bar (G)}(0)=bar (G).

Hence there exists a smallest *bÎ n* such that

{1}=C_{bar (G)}(b)£...£C_{bar (G)}(0)=bar (G).

We call * b * the

C_{bar (G)}(i-1)=È_{j=1}^{r(i)}p_{j}^{(i)}C_{bar (G)}(i),

and note that each *pÎbar (G)* can uniquely be written in terms of
these coset representatives as follows:

p=p_{j1}^{(1)}...p_{jb}^{(b)}.

Hence in particular the following holds:

| bar (G) | =Õ_{i=1}^{b}r(i).

This shows that storing the *p _{j}^{(i)},iÎb ,jÎr(i)*,
allows an economic way to deal with the elements of

G(k)={p_{j1}^{(1)}...p_{jk}^{(k)}i | j_{1}Îr(1),...,j_{b}Îr(k)}.

Thus the knowledge of the Sims chain considerably reduces the number of necessary checks for an orbit evaluation. The calculation of the base is therefore very important.

Example:Let us consider for example the action ofsupon the set of 2-element subsets of. In order to evaluate the base ofpbar (G)=Swe first of all embed the set of 2-element subsets into_{p}^{[2]}, wherenn:= p choose 2, by ordering the pairs lexicographically:and by replacing the pairs correspondingly by the natural numbers{1,2}<{1,3}<...<{1,p}<{2,p}<...<{p-1,p},1,..., p choose 2. An easy check shows that, according to this numbering, the following chain of canonic Young subgroupsyields via embedding the Sims chainsup³S_{(2,p-2)}³S_{(1,1,1,p-3)}³...³S_{(1,...,1,2)}³{1}Thusbar (G)=S_{p}^{[2]}³S_{(2,p-2)}^{[2]}³S_{(1,1,p-3)}^{[2]}³...³S_{(1,...,1,2)}^{[2]}³{1}.is the base for the canonic action ofp-2Son the set of 2-element subsets and its lexicographic ordering. Hence in particular for_{p}^{[2]}p:=5we obtain the Sims chain (with respect to the above numbering of the pairs of points)S_{5}^{[2]}³S_{(2,3)}^{[2]}³S_{(1,1,1,2)}^{[2]}³{1}.

Another helpful property of the base is described in

Lemma:The elementspÎbar (G)are uniquely determined by their action on the base.b

Proof: If *pi=ri*, for each *iÎ b *, then

Once the base * b * is at hand we can evaluate the orbits

Corollary:Either there existp, for which_{n}^{(i)}ÎC_{bar (G)}(i)or(p_{jb}^{(b)})^{-1}...(p_{j1}^{(1)})^{-1}pÎC_{bar (G)}(b)= {1_{G}}, so that p=p_{j1}^{(1)}...p_{jb}^{(b)}Îbar (G),pisnotan element ofbar (G).

harald.fripertinger "at" uni-graz.at | http://www-ang.kfunigraz.ac.at/~fripert/ |

UNI-Graz | Institut für Mathematik |

UNI-Bayreuth | Lehrstuhl II für Mathematik |

Orbit evaluation |