Construction -- Wreath product action on m-tuples

The wreath product acting in form of the exponentiation

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 (Y^X)^m, which can be interpreted as the set of all m-tuples of functions fÎY^X. Let F be an element of (Y^X)^m then F(i) is an element of Y^X 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 Y^m given by definition

H´Y^m -> Y^m, (h,f) -> h o f.

The exponentiation of H (for this group action) by G gives the following action:

H wr _XG´(Y^m)^X -> (Y^m)^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 (Y^m)^X to (Y^X)^m the action of definition can be translated into formula and

|H wr _XG \\(Y^X)^m|=|H wr _XG \\(Y^m)^X|= |G\\(H\\Y^m)^X|.

So all representatives of m-tuples in Y^X 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=S_n, Y=a and H=S_a. Here we want to compute a transversal of m-tuples of elements of aⁿ. 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 S_a-orbits on a^m. 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 S_m \\m^m (where S_m acts according to formula on the range of these functions.) Then the representatives of S_a\\a^m 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 S_n 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 Y^X 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