Action on the domain of functions

#### Action on the domain of functions

A permutation group G on the set X induces a group action on the set of all functions from X to a set Y.

For the following routines you have to specify the operating group G by giving a system of generators. The cardinality n of the set X is the degree of the permutations in G. In some cases you furthermore have to input the cardinality m of the set Y. In some cases, when we are dealing with characteristic functions, the cardinality of Y is already set to 2.

A very simple routine generating a set of all representatives of G-orbits on the set of all functions from {1,...,n} to {1,...,m} is

```INT all_orbits_right(g,m,reps) OP g,m,reps;
```
where `g` is a VECTOR of generators of the acting group G, `m` is the cardinality of Y and `reps` is a VECTOR object consisting of the representatives of the G-orbits. Such a representative f is written as a VECTOR of the form
[f(1),f(2),...,f(n)].
This routine does not use the homomorphism principle, the surjective method and the Read method for minimizing the number of minimality tests needed.

At first the Sims chain of the acting group is computed by

```INT strong_generators(a,b)  OP a,b;
```
where `a` is a VECTOR of generators of the permutation group G of degree n. `b` becomes an (n+1)´(n+1) MATRIX which is an upper triangular matrix. For iÎ{1,...,n} let CG(i) be the pointwise stabilizer of {1,...,i} , then the PERMUTATIONs in the i-1-th row of `b` are representatives of the cosets CG(i-1)/CG(i). For j³i the entry `S_M_IJ(b,i-1,j-1)` is a PERMUTATION p such that p(i)=j. The elements in `S_M_IJ(b,i-1,i-1)` are the identity permutation of degree n.

Then some minimality tests are applied, as described in the last chapter of [11].

The routine

```INT all_orbits_ksubsets(g,k,vec) OP g,k,reps;
```
computes a transversal of representatives of characteristic functions of k-subsets of X. `g` is a VECTOR of generators of G, `k` is an INTEGER object, indicating the cardinality of the subsets, `reps` is again a VECTOR of representatives. If k>n/2 (where n is the cardinality of X), then it computes the number of orbits of n-k-subsets of X.

There is a recursive routine

```INT all_orbits_ksubsets_rec(g,k,reps)  OP g,k,reps;
```
which uses the Read method in order to minimize the number of minimalityt tests needed. It computes a transversal of the characteristic functions of all s-sets 1£s£k. Again `g` is a system of generators of G, `k` indicates k and `reps` is a transversal of these representatives.
harald.fripertinger@kfunigraz.ac.at,
last changed: November 19, 2001

 Action on the domain of functions