Orbit evaluation |

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

It is obvious that the smallestW_{0}:={x}, and W_{i}:=È_{j=1}^{r}g_{j}W_{i-1}, iÎN^{*}.

The concrete implementation of this way of evaluatingG(x)=W_{i-1}.

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

Proof: Assume thatLemma:(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ñ.

so that in particularu_{i}:=a_{i}...a_{t}, and x_{i}:=f(u_{i}),

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

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

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

We call this group theC_{bar (G)}(k):={pÎbar (G) | " iÎk:pi=i}.

which we call theN_{bar (G)}(k):={pÎbar (G) | pk=k},

Hence there exists a smallest{1}=C_{bar (G)}(n)£C_{bar (G)}(n-1)£...£C_{bar (G)}(0)=bar (G).

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

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

Hence in particular the following holds:p=p_{j1}^{(1)}...p_{jb}^{(b)}.

This shows that storing the| bar (G) | =Õ_{i=1}^{b}r(i).

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.G(k)={p_{j1}^{(1)}...p_{jk}^{(k)}i | j_{1}Îr(1),...,j_{b}Îr(k)}.

Another helpful property of the base is described inExample: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}.

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

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@kfunigraz.ac.at,

last changed: August 28, 2001

Orbit evaluation |