| | | 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=ág1,...,grñ, together with the actions of the gi on X. Then, for xÎX, we can put
W0:={x}, and Wi:=Èj=1rgjWi-1, iÎN*.It is obvious that the smallest i such that Wi=Wi-1 satisfies
G(x)=Wi-1.The concrete implementation of this way of evaluating G(x) of course may heavily depend on our knowledge of X,G and GX. For example, if | X | =1, then G(x)=W0, while G(x)=X, if | G\\X | =1, so that the Cauchy-Frobenius lemma can serve as a stopping rule. The knowledge of | G\\X | is helpful in particular if we are after the whole set of orbits G\\X, in which case we proceed with the remaining subset X\G(x) correspondingly. The implementation of this method is obvious.
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/Gx. Thus we can also obtain generators of the stabilizer Gx by an application of the following fact:
Lemma: (Schreier) If U is a subgroup of G=ág1,...,grñ which is finite and which decomposes as follows into left cosets of U:Proof: Assume that u=a1...atÎU, where the ai are elements of the generating set {g1,...,gr}. We putG=Èi=1s hiU, where h1=1,and if the mapping f is defined byf:G -> {h1,...,hs}:g -> hi, if gÎhiU,then U is generated by the elements f(gihk)-1gihk:U=áf(gihk)-1gihk | iÎr,kÎsñ.
ui:=ai...at, and xi:=f(ui),so that in particular x1=f(u)=1. Putting xt+1:=1, we can rewrite u in the form
u=(x1-1a1x2)(x2-1a2x3)...(xt-1atxt+1).Now xi=f(ui)=f(aiui+1)=f(aixi+1), for xi+1=f(ui+1) means that ui+1=xi+1u', for a suitable u'ÎU, and hence aiui+1=aixi+1u. Thus
u=f(a1x2)-1a1x2f(a2x3)-1a2x3...,which completes the proof.
A direct evaluation of the stabilizer Gx will be discussed later. In the case when X is too big to be stored, we can do the following in order to evaluate the set of orbits. We number the elements of X, being now faced with an operation of G on n, say, so that there is a canonic transversal of G\\n, consisting of the smallest orbit elements. So we take 1În as the first element of the desired transversal. Then we evaluate the minimal iÎn which is not contained in G(1), take this point i as the second element of the transversal and evaluate the minimal jÎn that is not in G(i) and bigger than i. There are now two cases. Either there is a gÎG such that gj<j, in which case jÎG(1), or there is no such g, so j not ÎG(1)ÈG(i), and therefore j has to be taken as the third element of the transversal, and so on.
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 bar (G) so that not too many checks are necessary. We therefore introduce the pointwise stabilizer of the subset kÍn which we denote as follows:
Cbar (G)(k):={pÎbar (G) | " iÎk:pi=i}.We call this group the centralizer of k in order to distinguish it from the setwise stabilizer
Nbar (G)(k):={pÎbar (G) | pk=k},which we call the normalizer of k. (Correspondingly in the general case GX we have Cbar (G)(M) and Nbar (G)(M) for subsets MÍX.) These centralizers form the chain of subgroups
{1}=Cbar (G)(n)£Cbar (G)(n-1)£...£Cbar (G)(0)=bar (G).Hence there exists a smallest bÎn such that
{1}=Cbar (G)(b )£...£Cbar (G)(0)=bar (G).We call b the base of the action of G on n, b its length, and the formula above the Sims chain of this action. Now we consider the left coset decompositions
Cbar (G)(i-1)=Èj=1r(i)pj(i)Cbar (G) (i),and note that each pÎbar (G) can uniquely be written in terms of these coset representatives as follows:
p=pj1(1)...pjb(b).Hence in particular the following holds:
| bar (G) | =Õi=1br(i).This shows that storing the pj(i),iÎb ,jÎr(i), allows an economic way to deal with the elements of bar (G). Moreover, as pj(i)k=k, if i>k, the following is true for the orbit of kÎn under G:
G(k)={pj1(1)...pjk(k)i | j1Îr(1),...,jbÎ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 of sup on the set of 2-element subsets of p. In order to evaluate the base of bar (G)=Sp[2] we first of all embed the set of 2-element subsets into n, where n:= p choose 2, by ordering the pairs lexicographically:Another helpful property of the base is described in{1,2}<{1,3}<...<{1,p}<{2,p}<...<{p-1,p},and by replacing the pairs correspondingly by the natural numbers 1,..., p choose 2. An easy check shows that, according to this numbering, the following chain of canonic Young subgroupssup³S(2,p-2)³S(1,1,1,p-3)³...³S(1,...,1,2)³{1}yields via embedding the Sims chainbar (G)=Sp[2] ³S(2,p-2)[2]³S(1,1,p-3)[2]³...³S(1,...,1,2)[2]³{1}.Thus p-2 is the base for the canonic action of Sp[2] on the set of 2-element subsets and its lexicographic ordering. Hence in particular for p:=5 we obtain the Sims chain (with respect to the above numbering of the pairs of points)S5[2]³S(2,3)[2]³S(1,1,1,2)[2]³{1}.
Lemma: The elements pÎbar (G) are uniquely determined by their action on the base b .Proof: If pi=ri, for each iÎb , then p-1rÎCbar (G)(b )=1, so that p=r.
Once the base b is at hand we can evaluate the orbits G(k), kÎb , as it is described above. These orbits can serve very well for a check if pÎSn is contained in bar (G) or not: Consider p1 first. If p1 not ÎG(1), then obviously p not Îbar (G), and we can stop. If otherwise p1ÎG(1), then there exists a left coset representative pj(1) such that pj(1)1=p1ÎG(1), and therefore (pj(1))-1pÎCG(1). Hence, by induction, we obtain
Corollary: Either there exist pn(i)ÎCbar (G)(i), for which(pjb(b))-1...(pj1(1))-1pÎCbar (G)(b )= {1G}, so that p=pj1(1)...pjb(b)Îbar (G),or p is not an element of bar (G).
| | | Orbit evaluation |