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
