| | | **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 *_{X}G 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 *_{X}G acts in the following way
on *F(i)*:
*
(y,g)F(i)(x)=y(x)F(i)(g*^{-1}x) 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 *_{X}G´(Y^{m})^{X} -> (Y^{m})^{X},
((y,g),F)
-> (y,g)F,

where
*(y,g)F(x)=y(x)F(g*^{-1}x) for *xÎX*, and for
each *iÎ*__m__ we have
*
(y,g)F(x)(i)=y(x)F(g*^{-1}x)(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 *_{X}G \\(Y^{X})^{m}|=|H wr _{X}G \\(Y^{m})^{X}|=
|G\\(H\\Y^{m})^{X}|.

So all representatives of *m*-tuples in *Y*^{X} under the action of
*H wr *_{X}G 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__^{n}.
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 *_{X}G.
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 |