Preliminaries

# Preliminaries

When speaking about constructions under finite group actions we want to compute complete lists of orbit representatives for a given group action. The problem of counting orbits by using the Cauchy-Frobenius-Lemma, Pólya-theory and various other methods is well studied. Now by using quite powerful computers it is possible not only to determine the number of all these different orbits but to compute a representative from each orbit as well.

Let me start with some basic concepts about finite group actions. (More details can be found in [12].) Let G denote a multiplicative finite group and X a nonempty set. A finite group action GX of G on X is described by a mapping

G ´X -> X,         (g,x) -> gx,
such that g(g'x) = (gg')x, and 1x=x. In other words, there is a group homomorphism d from G into the symmetric group SX on X (i.e. the set of all permutations of X) which is called a permutation representation of G on X:
d:G -> SX, g -> d(g)=:bar (g), where bar (g)(x) :=gx.
A group action GX defines the following equivalence relation on X:
x ~G x' iff \$g ÎG : x'=gx.
The equivalence classes are called orbits, and the orbit of x ÎX will be indicated as
G(x) := {gx | g ÎG }.
The set of all G-orbits on X
G\\X:={G(x) | xÎX}
forms a partition of X. A complete system of orbit representatives will be indicated as a transversal T(G\\X). For each x ÎX the stabilizer Gx of x
Gx := {g ÎG | gx=x }
is a subgroup of G. The mapping G(x) -> G/Gx, gx -> gGx is a bijection. So we conclude that
| G(x) | = | G | / | Gx | .
Finally the set of all fixed points of gÎG is denoted by
Xg := {x | gx=x }.
Interesting examples for group actions can be found as actions on the set YX of all functions from X to Y, where the group action on YX is induced from actions on X or Y. Let GX and HY be finite group actions,
• then G acts on YX by the definition
G´YX -> YX,        (g,f) -> f o g-1,
• then H acts on YX by the definition
H´YX -> YX,        (h,f) -> h o f,
• then the direct product G´H acts on YX by the definition
(G´H)´YX -> YX,        ((g,h),f) -> h o f o g-1,
De Bruijn proved that whenever a direct product G´H is acting on a set M we obtain natural actions of H on the set of G-orbits:
H´(G\\M) -> G\\M,        (h,G(m)) -> G(hm)
and of G on the set of H-orbits:
G´(H\\M) -> H\\M,        (g,H(m)) -> H(gm).
• then G acts on XX by the definition
G´XX -> XX,        (g,f) -> g o f o g-1,
• then the wreath product H wr XG acts in form of the exponentiation on YX. The wreath product is a group formed by a set H wr XG:={(y,g) | yÎHX, gÎG} with multiplication (y,g)(y', g')=(yy'g, gg'), where yy'g(x):=y(x)y'g (x) and y'g(x):=y'(g-1x). It acts in a natural way on YX by
(H wr XG)´YX -> YX,        ((y,g),f) -> [~f] ,
where [~f] (x)= y(x)f(p-1x). There is a bijection due to Lehmann ([13],[14]) which reduces the action of a wreath product to the action of the group G on the set of all functions from X into the set of all orbits of H on Y:
F:H wr XG\\YX -> G\\(H\\Y)X,    (H wr XG(f)) -> G(F),
where FÎ(H\\Y)X is given by F(x)=H(f(x)), and G acts on (H\\Y)X by g(F):= F o g-1.

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

 Preliminaries