Orbit evaluation

Orbit evaluation

We consider a finite action _GX 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₁,...,g_rñ, together with the actions of the g_i on X. Then, for xÎX, we can put

W₀:={x}, and W_i:=È_j=1^rg_jW_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 _GX. For example, if | X | =1, then G(x)=W₀, 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/G_x. Thus we can also obtain generators of the stabilizer G_x by an application of the following fact:

Lemma:  (Schreier) If U is a subgroup of G=ág₁,...,g_rñ which is finite and which decomposes as follows into left cosets of U:

G=È_i=1^s h_iU, where h₁=1,

and if the mapping f is defined by

f:G -> {h₁,...,h_s}:g -> h_i, if gÎh_iU,

then U is generated by the elements f(g_ih_k)^-1g_ih_k:

U=áf(g_ih_k)^-1g_ih_k | iÎr,kÎsñ.

Proof: Assume that u=a₁...a_tÎU, where the a_i are elements of the generating set {g₁,...,g_r}. We put

u_i:=a_i...a_t, and x_i:=f(u_i),

so that in particular x₁=f(u)=1. Putting x_t+1:=1, we can rewrite u in the form

u=(x₁^-1a₁x₂)(x₂^-1a₂x₃)...(x_t^-1a_tx_t+1).

Now x_i=f(u_i)=f(a_iu_i+1)=f(a_ix_i+1), for x_i+1=f(u_i+1) means that u_i+1=x_i+1u', for a suitable u'ÎU, and hence a_iu_i+1=a_ix_i+1u. Thus

u=f(a₁x₂)^-1a₁x₂f(a₂x₃)^-1a₂x₃...,

which completes the proof.

A direct evaluation of the stabilizer G_x 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:

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 setwise stabilizer

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

which we call the normalizer of k. (Correspondingly in the general case _GX we have C_{bar (G)}(M) and N_{bar (G)}(M) for subsets MÍX.) These centralizers form the chain of subgroups

{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 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

C_{bar (G)}(i-1)=È_j=1^r(i)p_j⁽ⁱ⁾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⁽¹⁾...p_jb^(b).

Hence in particular the following holds:

| bar (G) | =Õ_i=1^br(i).

This shows that storing the p_j⁽ⁱ⁾,iÎb ,jÎr(i), allows an economic way to deal with the elements of bar (G). Moreover, as p_j⁽ⁱ⁾k=k, if i>k, the following is true for the orbit of kÎn under G:

  G(k)={p_j1⁽¹⁾...p_jk^(k)i | j₁Î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 of sup on the set of 2-element subsets of p. In order to evaluate the base of bar (G)=S_p^[2] we first of all embed the set of 2-element subsets into n, where n:= p choose 2, by ordering the pairs lexicographically:

{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 subgroups

sup³S_(2,p-2)³S_(1,1,1,p-3)³...³S_(1,...,1,2)³{1}

yields via embedding the Sims chain

bar (G)=S_p^[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 S_p^[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)

S₅^[2]³S_(2,3)^[2]³S_(1,1,1,2)^[2]³{1}.

Another helpful property of the base is described in

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ÎC_{bar (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ÎS_n 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 p_j⁽¹⁾ such that p_j⁽¹⁾1=p1ÎG(1), and therefore (p_j⁽¹⁾)^-1pÎC_G(1). Hence, by induction, we obtain

Corollary: Either there exist p_n⁽ⁱ⁾ÎC_{bar (G)}(i), for which

(p_jb^(b))^-1...(p_j1⁽¹⁾)^-1pÎC_{bar (G)}(b )= {1_G}, so that p=p_j1⁽¹⁾...p_jb^(b)Îbar (G),

or p is not an element of bar (G).

Orbit evaluation