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

The group action on the range of functions

A group action HY induces a group action of H on the set of all functions f:X -> Y by definition. Without loss of generality let X be the set n. A transversal T(H\\YX) can be computed by applying the homomorphism principle in the following way: The function
j:Yn -> Yn-1,         f -> j(f):=f | n-1
is compatible with the group action since
j(h o f)=(h o f) | n-1=h o f | n-1= h o j(f).
From that we deduce that a transversal T(H\\Yn) can be computed as
T(H\\Yn)=Èf'ÎT(H\\Yn-1)T(Hf'\\j-1({f'} ),
where Hf', the stabilizer of f' in H,
Hf'={hÎH|h o f'=h)} ={hÎH|hf'(i)=f'(i) " iÎn-1)}
acts on the set
j-1({f'} )={fÎYn|j(f)=f')} ={fÎYn|f | n-1=f')} .

This method leads to the following recursive algorithm: Without loss of generality let Y be m, then each function fÎYX=mn can be written as an n-tuple (f(1),...,f(n)). These vectors are totally ordered by the lexicographical ordering. As the canonic representative of the orbit H(f) the smallest element of the orbit will be chosen. Furthermore we can assume that the elements of a transversal T(H'\\Y) for H'£H are the smallest elements in their H'-orbits. Then the canonic representatives f can be computed as follows:

  1. For f(1) take any element of T(H\\Y).
  2. Let i<n and let the first i values of the canonic representative be (f(1),...,f(i)), then determine the pointwise stabilizer H{f(1),...,f(i)} of the set {f(1),...,f(i)} .
    H{f(1),...,f(i)} ={hÎH{f(1),...,f(i-1)} |hf(i)=f(i))}
    and take for f(i+1) any element of T(H{f(1),...,f(i)} \\Y).

In this situation we can also compute the canonic representative of the orbit H(f) from any orbit element f=(f(1),...,f(n))Îmn. Let f0=f and H0=H. Then for 1£i£n we can use the Schreier vectors (cf. [2]) for the group action Hi-1Y to determine an element hi-1ÎHi-1 such that hi-1fi-1(i) is the canonic representative of the orbit Hi-1(fi-1(i)). Let fi be the function hi-1 o fi-1, then by construction fi(j)=fi-1(j) for all 1£j£i-1. Finally let

Hi={hÎHi-1|hfi(i)=fi(i))} ,
then Hi is the pointwise stabilizer of {fi(1),...,fi(i)} . The canonic representative of the orbit H(f) is given by fn and the stabilizer of fn is Hn.

This algorithm can easily be changed to produce only representatives of injective functions. In the case n=m these representatives are coset representatives H\Sn.

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

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