The group action both on the domain and on the range of functions

The group action both on the domain and on the range of functions

Two group actions _GX and _HY induce a group action of the direct product G´H on the set of all functions f:X -> Y by definition. By de Bruijns Lemma such an action of the direct product can be replaced by the following action of G on the set of all H-orbits on Y^X.

G´(H\\Y^X) -> H\\Y^X, (g,H(f)) -> H(f o g^-1).

In order to compute all G´H-orbits on Y^X we have to adapt the algorithm for computing all G-orbits on Y^X. Again we write the elements in Y^X as vectors in mⁿ such that we can choose the lexicographically smallest element of an orbit as its canonic representative. The list of all possible representatives, which must be tested to be the smallest elements in their orbits, is given by the transversal T(H\\Y^X) of canonic representatives of H-orbits on Y^X computed above. When doing the minimality test for the orbit H(f) given by its canonic representative f, for all gÎG we first have to compute f o g. Then we must determine the canonic representative [~f] of the orbit H(f o g). If [~f] <f then f is not the canonic representative of the orbit (G´H)(f). Only in those cases when f is less than or equal to the canonic representatives of H(f o g) for all gÎG, the function f is the canonic representative of its G´H-orbit. (For the rest of this paragraph we will not distinguish between the orbit H(f) and its canonic representative, which will be indicated as H(f) as well.) For doing this minimality test it is convenient to know strong generators (the so called Sims-chain) of the group G. In certain cases we don't have to compute and apply all group elements, but we can make jumps and leave some parts of the tree (holding all elements of G, built from its generators) out, which will be described next.

Let C_G(i) be the pointwise stabilizer of {1,...,i} in G and let

{p_j⁽ⁱ⁾|1£i£n, 1£j£r(i))}

be the strong generators of G such that

C_G(i-1)=È_j=1^r(i)p_j⁽ⁱ⁾C_G(i), where p₁⁽ⁱ⁾ÎC_G(i),

then we have:

If H(f)<H(f o p_j⁽ⁱ⁾) and H(f)(i)<H(f o p_j⁽ⁱ⁾)(i) then H(f)<C_G(i)(H(f o p_j⁽ⁱ⁾)).
If H(f)£C_G(i)(H(f)) and if there is some sÎC_G(i) such that H(f o p_j⁽ⁱ⁾ o s)=H(f) then H(f)£C_G(i)(H(f o p_j⁽ⁱ⁾)).

This algorithm is not very fast, since whenever applying an element g of G to H(f) in the minimality test for H(f), we have to compute the canonic representative of H(f o g^-1).

Again we can restrict this group action to an action on the set of all injective functions, which leads to the determination of double-coset representatives H\S_n/G in the case n=m. This algorithm works for arbitrary groups G and H. In the case when H is a Young group or a wreath product you should apply special routines using the so called Leiterspiel, implemented by Schmalz [19], Weinrich [21] and Betten [1], which are much faster in these situations.

harald.fripertinger@kfunigraz.ac.at,
last changed: January 23, 2001

The group action both on the domain and on the range of functions