| | | **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 _{G}X and _{H}Y 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__^{n}
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}^{(i)}|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}^{(i)}C_{G}(i), where
p_{1}^{(i)}ÎC_{G}(i),

then we have:
- If
*H(f)<H(f o p*_{j}^{(i)})
and *H(f)(i)<H(f o p*_{j}^{(i)})(i)
then *H(f)<C*_{G}(i)(H(f o p_{j}^{(i)})).
- If
*H(f)£C*_{G}(i)(H(f))
and if there is some *sÎC*_{G}(i)
such that *H(f o p*_{j}^{(i)} o s)=H(f) then *H(f)£C*_{G}(i)(H(f o p_{j}^{(i)})).

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