Wreath product action on m-tuples

## Wreath product action on m-tuples

The group action of definition induces by definition the following action of H wr XG on the set (YX)m, which can be interpreted as the set of all m-tuples of functions fÎYX. Let F be an element of (YX)m then F(i) is an element of YX for all iÎm and (y,g)ÎH wr XG acts in the following way on F(i):
(y,g)F(i)(x)=y(x)F(i)(g-1x) for all xÎX.
In order to apply Lehmanns Lemma for this group action, first consider the natural action of H on Ym given by definition
H´Ym -> Ym,        (h,f) -> h o f.
The exponentiation of H (for this group action) by G gives the following action:
H wr XG´(Ym)X -> (Ym)X,         ((y,g),F) -> (y,g)F,
where (y,g)F(x)=y(x)F(g-1x) for xÎX, and for each iÎm we have
(y,g)F(x)(i)=y(x)F(g-1x)(i).
Since y(F)(i)(x):=F(x)(i) defines a bijection from (Ym)X to (YX)m the action of definition can be translated into formula and
|H wr XG \\(YX)m|=|H wr XG \\(Ym)X|= |G\\(H\\Ym)X|.
So all representatives of m-tuples in YX under the action of H wr XG can be computed by finding a transversal Y' of the action of H on the set of all m-tuples in Y, and then determining a transversal of G-classes in Y'X.
Example: Consider the following example for X=n, G=Sn, Y=a and H=Sa. Here we want to compute a transversal of m-tuples of elements of an. These elements are considered to be words of length n over the alphabet a. As was described above we have to compute a transversal of Sa-orbits on am. These orbits correspond to partitions of m into at most a parts. In the case m<a it is enough to consider only the orbits in Sm \\mm (where Sm acts according to formula on the range of these functions.) Then the representatives of Sa\\am can be given as "Reimschemata", (see [11]) which are defined to be functions f:m -> a, such that f(1)=1 and f(j+1)ÎzÇa, where z:=max{ f(i) | i£j} +1. The set of these Reimschemata can totally be ordered by the lexicographic order. Then a standard algorithm can be applied for computing a transversal of Sn orbits on the set of all functions from n into the set of all Reimschemata.

Unfortunately these methods can't be applied for determining transversals of m-subsets of YX under the induced action of H wr XG. In many cases however standard methods are strong enough to compute such transversals. In [7] it is demonstrated how these methods can be applied for the enumeration, construction and random generation of block codes.

In the computer algebra system SYMMETRICA there are all kinds of routines in order to compute orbit transversals or to generate orbit representatives uniformly at random using the Dixon-Wilf-algorithm.

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

 Wreath product action on m-tuples