Algebraic Combinatorics -- Paradigmatic Examples

Paradigmatic Examples

Paradigmatic Examples

Finally we introduce the actions derived from _GX and _HY which form our paradigmatic examples, and which will be discussed in full detail in later sections. In order to prepare this we form the set of all the mappings from X into Y:

Y^X:= {f | f:X -> Y },

and notice: If G acts on X and H acts on Y, then G, H and H ´G act on Y^X as follows:

G ´Y^X -> Y^X :(g,f) -> f o bar (g)^-1, i.e. (g,f) is mapped onto [~f] , where [~f] (x):=f(g^-1x). The corresponding permutation group on Y^X will be denoted by E^{bar (G)}.
H ´Y^X -> Y^X :(h,f) -> bar (h) o f, i.e. (h,f) is mapped onto [~f] , where [~f] (x):=hf(x). The corresponding permutation group will be denoted by bar (H)^E.
(H ´G) ´Y^X -> Y^X :((h,g),f) -> bar (h) o f o bar (g)^-1, i.e. ((h,g),f) is mapped onto [~f] , where [~f] (x):=hf(g^-1x). The corresponding permutation group on Y^X will be denoted by bar (H)^{bar (G)}, and it will be called the power group of bar (H) by bar (G).

There is a fourth action which contains these three actions as subactions, but in order to describe it we first need to introduce the wreath product H wr _X G : Its underlying set is

H wr _X G :=H^X ´G= {( y,g) | y:X -> H,g ÎG },

and the multiplication is defined by

( y,g)( y',g'):= ( yy'_g,gg'), yy'_g(x):= y(x) y'_g(x):= y(x) y'(g^-1x).

The actions _GX and _HY yield the following natural action of H wr _X G on Y^X:

H wr _X G ´Y^X -> Y^X :(( y,g),f) -> [~f] , [~f] (x):= y(x)f(g^-1x).

The corresponding permutation group on Y^X will be denoted by [ bar (H)]^{bar (G)}, and it will be called the exponentiation group of bar (H) by bar (G). The orbits of G,H,H ´G and H wr _X G on Y^X will be called symmetry classes of mappings of mappings.

A few remarks concerning the wreath product H wr _X G are in order, they will in particular show that the actions of G, H, and H ´G on Y^X are restrictions of the action of H wr _X G on Y^X defined above. The reader is kindly asked carefully to check the following statements on wreath products H wr _X G :

Lemma: The wreath product H wr _X G has the following properties:
The identity element of H wr _X G is ( i,1), where i:x -> 1_H.
If we define y^-1 ÎH^X by y^-1(x):= y(x)^-1, we get
( y,g)^-1=( y^-1_g^-1,g^-1), where y^-1_g^-1:= ( y^-1)_g^-1=( y_g^-1)^-1.

The normal subgroup
H^*:= {( y,1) | yÎH^X } lefttriangleeq H wr _X G ,
is called the base group, and it is the direct product of | X | copies H^x of H:
H^x:= {( y,1) | " x' not = x : y(x')=1_H } simeq H, for each x ÎX.

The subgroup G ':= {( i,g) | g ÎG } simeq G is a complement of H^*, so that we have
H wr _X G =H^* ·G ' , H^* lefttriangleeq H wr _X G , H^* ÇG ' = {( i,1) }.

The diagonal
D(H^*):= {( y,1) | y constant } simeq H,
satisfies
D(H^*) ·G ' = {( y,g) | y constant, g ÎG } simeq H ´G.

This shows that the subgroups G ', D(H^*) and D(H^*) ·G ' are natural embeddings of G, H and H ´G into H wr _X G , in short:

G hookrightarrow H wr _X G , H hookrightarrow H wr _X G , H ´G hookrightarrow H wr _X G ,

so that in fact the actions of G, H, and H ´G on Y^X introduced above are restrictions of the action of H wr _X G on Y^X.

In order to prepare later applications of such actions we mention that actions of direct products and of wreath products can be reformulated in terms of the respective factors of the direct and of the wreath product. Here is, to begin with, a lemma on actions of direct products, which is very easy to check (exercise):

harald.fripertinger@kfunigraz.ac.at,
last changed: August 28, 2001

Paradigmatic Examples