ReferencesTopAction in form of conjugationThe wreath product acting in form of the exponentiation

The wreath product acting in form of the exponentiation

The two group actions GX and HY induce a natural action of the wreath product on YX by definition. Lehmann's Lemma can be used in order to compute the number of H wr XG-orbits on YX by
|H wr XG\\YX|= |G\\(H\\Y)X|=(1)/(|G|)ågÎGÕi=1|X| |H\\Y|ai(g)=
(1)/(|G|)ågÎGÕi=1|X| ((1)/(|H|)åhÎH|Yh|)ai(g),
where (a1(g),a2(g),...) is the cycle type of g as a permutation of X. It can also be used in order to construct a transversal of the H wr XG orbits of YX, which shall be described now: Such an algorithm for the group action of the exponentiation of H by G can be split into two algorithms for simpler types of group actions. In a first step one has to find a transversal Y', say, of the orbits of H on Y. Then in a second step it is enough to find a transversal of the G-classes on Y'X, where G acts on Y'X according definition. For this second algorithm all the methods described in section can be applied.

Furthermore Lehmanns Lemma offers a new possibility to apply the so called Dixon-Wilf-algorithm (see [6][12]) for constructing H wr XG-orbits uniformly at random. The Dixon-Wilf-algorithm for the exponentiation can be split into a Dixon-Wilf-algorithm for the action of H on Y and a Dixon-Wilf-algorithm for the action of G on the set of all mappings from X to Y', where Y' is a transversal of the H-orbits of Y.

In addition to this Lehmann proved a theorem for weighted enumeration under the exponentiation of H by G.

Theorem: Let R be a commutative ring such that the set of the reals is a subring of R. A weight function w:Y -> R, which is constant on each H-orbit on Y, can be used to define a weight function [~w] :H\\Y -> R by [~w] (H(y)):=w(y). Then for fÎYX or FÎ(H\\Y)X the functions W and [~W] defined by
W(f):=ÕxÎXw(f(x)),        [~W] (F):=ÕxÎX[~w] (F(x))
are compatible with the group action of H wr XG or G on YX or (H\\Y)X respectively. The sum of the weights of H wr XG-orbits can be evaluated by
åH wr XG(f)ÎH wr XG\\YXW(H wr XG(f))= åG(F)ÎG\\(H\\Y)X[~W] (G(F))=
=Z(G,X | xi=åH(y)ÎH\\Y [~w] (H(y))i )= Z(G,X | xi=åH(y)ÎH\\Y w(y)i),
where Z(G,X | xi=f(i)) is the cycle index of G acting on X (see for instance [12][5][15]) where the variable xi must be replaced by f(i).
Using the weight function described above together with two applications of weighted forms of the Dixon-Wilf-algorithm, one for the action of H on Y and one for the action of G on (T(H\\Y))X, it is possible to generate H wr XG-orbits of given weight uniformly at random.
  • Wreath product action on m-tuples
    • harald.fripertinger@kfunigraz.ac.at,
    last changed: January 23, 2001

    ReferencesTopAction in form of conjugationThe wreath product acting in form of the exponentiation