Further exercises on permutation groups
I will keep here some additional exercises, mostly suggested to me by
various people.
1. Let G be a transitive permutation group on Ω. Show that, for
any permutation h of Ω, the average number of fixed points of
the elements of the coset Gh is equal to 1.
2. (Antonio Machì, Roma)
A descent
in a permutation g in the symmetric group S_{n} is
a point i such that ig <= i; it is a strict
descent if ig < i.
Prove that, if a subgroup G of S_{n}
has h orbits, then
the average number of descents of a permutation in G is
(n+h)/2, and the average number of strict descents is
(nh)/2. Deduce the OrbitCounting Lemma.
3. (Antonio Machì, Roma)
(a) Let z(g) be the number of cycles of a permutation
g in S_{n}, and t(g) the minimum
number of transpositions whose product is g. Prove that
z(g)+t(g)=n.
(b) Prove that, if t_{1}, ..., t_{k} are
transpositions which generate a transitive subgroup of S_{n},
then k >= n1. If, further,
t_{1}...t_{k}=1, then k >= 2n2
and k is even.
(c) Hence show that, if g_{1}, ..., g_{m}
generate a transitive subgroup of S_{n}, then
z(g_{1}) + ... + z(g_{m})
<= (m1)n+1.
If, further, g_{1}...g_{m}=1, then
z(g_{1}) + ... + z(g_{m})
<= (m2)n+2,
and the difference of these two quantities is even.
(d) How should the preceding result be modified if the group generated by
g_{1}, ..., g_{m} has a prescribed number
p of orbits?
(e) Suppose that g_{1}, g_{2},
g_{3} generate a regular subgroup G of
S_{n}, and
g_{1}g_{2}g_{3}=1. Let
z(g_{1})+z(g_{2})
+z(g_{3})=n+22g. Prove
Hurwitz's Theorem:
If g > 1 then the order of G is at most 84(g1).
Construct an example meeting the bound when g=3.
Hint: If g_{i} has order n_{i} for
i=1,2,3, show that
1/n_{1}+1/n_{2}+1/n_{3}
= 1  2(g1)/n,
where n=G.
For a crib, see:
A. Machì, The RiemannHurwitz formula for the centralizer of a pair of
permutations, Arch. Math. 42 (1984), 280288.
A. Jacques, Sur le genre d'une paire de substitutions, C.R. Acad. Sci.
Paris 267 (1968), 625627.
4. Define the automorphism group of a Gspace Ω,
and prove that it is equal to the centraliser of G in the
symmetric group on Ω.
If G is transitive on Ω, prove that the automorphism group
of Ω is isomorphic to
N_{G}(G_{α})/G_{α},
where α is a point of Ω.
5. Let p be a prime congruent to 3 mod 4. Prove that a simple
group of order p(p+1)(p1)/2 is isomorphic to
PSL(2,p). Hence show that the simple groups PSL(3,2) and PSL(2,7)
are isomorphic.
Hint: Let G be such a group, and P a Sylow
psubgroup and N its normaliser. Show that
G:N=p+1, and that, acting on the cosets of N,
G is a 2transitive group in which the stabiliser of a point
is isomorphic to the group
x > a^{2}x+b of permutations
of GF(p) (fixing a point infty).
Now show that the 2point stabiliser is cyclic of order (p1)/2,
and its normaliser is dihedral, containing the element
x > (1)/x.
Deduce that G is isomorphic to PSL(2,p).
6. This is Iwasawa's Lemma: see K. Iwasawa, Uber die
Einfachkeit der speziellen projektiven Gruppen, Proc. Imp. Acad.
Tokyo 17 (1941), 5759.
Let G be a permutation group on Ω. Suppose that there is
an abelian normal subgroup A of the stabiliser of a point with the
property that the conjugates of A generate G. Then any
nontrivial normal subgroup of G contains the derived group
G'. In particular, if A is contained in G', then
G is simple.
Prove this, and use it to show that the groups PSL(n,F) are
simple for n>1 (except for PSL(2,2) and PSL(2,3)).
For a crib, see D. E. Taylor, The Geometry of the Classical Groups,
Heldermann, Berlin, 1992. ISBN: 3885380099.
7. For this exercise, recall from pages 3334 (and 79) of the book that
there are 30 projective planes on a set of 7 points,
falling into two orbits O_{1} and
O_{2} of size 15 under the action of the alternating group
A_{7}.
Construct a new geometry with three kinds of elements, "Points", "Lines"
and "Planes", as follows:
 the Points are the elements of O_{1};
 the Lines are the 3element subsets of the 7set;
 the Planes are the elements of O_{2};
 a Point P and Line ijk are incident if ijk
is a line of P;
 similarly for incidence between Planes and Lines;
 a Point and Plane are incident if they share three lines through a point.
Prove that this geometry is isomorphic to 3dimensional projective space
over GF(2). (You may find it convenient to define an addition on
the set {0} ∪ O_{1} by the rules that
P+0 = 0+P = P, P+P = 0, and
P+Q = R whenever P,Q,R are the three Points
incident with a Line. Show that this is an elementary abelian 2group, using
the existence and structure of the Planes to verify that addition is
associative.)
Deduce that A_{7} is a subgroup of
PSL(4,2) with index 8. Hence conclude that PSL(4,2) is isomorphic to
A_{8}.
8. Let P_{n} be the set of all partitions of the set
{1, ..., n}. There is a function C from S_{n}
to P_{n}, which maps any permutation to the partition
induced by its cycles.
Prove that the set C(G), for a permutation group G,
determines
 the order of G;
 for each p in P_{n}, the cardinality of
C^{1}(p) (the set of elements of G whose
cycle partition is p);
 The cycle index of G.
Note: Eamonn O'Brien
has shown that there are two pairs of groups of order 64 (numbers
19 and 111, and 94 and 249, in the lists in MAGMA and GAP), which act
transivitely on 16 points, such that the two groups in each pair give
rise to the same sets of cycle partitions. So C(G) does
not determine G up to isomorphism. Here is
a GAP program to verify this.
The idea for this exercise came from
Alberto Leporati, Milano.
9. Let G be a group with two subgroups H and K so
that the actions of G on the cosets of H and K are
not permutation isomorphic but have the same permutation character. Let
n be the index of H (or K) in G. Now let
G'=S_{n}, and let H' and K' be the
subgroups of G' obtained by embedding G in S_{n}
according to the two given actions. Show that the actions of G' on the
cosets of H' and K' are not permutation isomorphic but
have the same permutation character.
This exercise is taken from R. M. Guralnick and J. Saxl, "Primitive
permutation characters", pp. 364367 in Groups, Combinatorics and
Geometry (ed.M. W. Liebeck and J. Saxl), London Math. Soc. Lecture
Notes 165, Cambridge Univ. Press, Cambridge, 1992.
10. Let G be a subgroup of S_{n}, and k a
positive integer not greater than n. The kclosure
G^{(k)} consists of all permutations in
S_{n} which preserve all the Gorbits on
ktuples; that is, all permutations h in S_{n}
which satisfy
for all i_{1}, ..., i_{k}, there exists
g in G such that
i_{1}g=i_{1}h, ...,
i_{k}g=i_{k}h.
Prove the following:
 G^{(k)} contains G^{(k+1)};
 G^{(n)} = G;
 G is ktransitive if and only if
G^{(k)} = S_{n};
 if G is abelian then so is G^{(2)};
 if G is the automorphism group of a graph (acting on the
vertices) then G^{(2)} = G.
See H. Wielandt's lecture notes Permutation Groups through Invariant
Relations and Invariant Functions, Ohio State University 1969 (also
available in his collected works, Volume 1, published by de Gruyter in 1994).
11. An application of the OrbitCounting Lemma.

How many different ways of colouring the faces of a cube with three colours
are there, if two colourings related by a rotation of the cube are counted
as being equal?

Same question for edges.

Same question for vertices.
12. Let G be a transitive permutation group of prime degree p,
and let P be a Sylow psubgroup of G. Suppose that
N_{G}(P)=P. Show that G is a
cyclic group of order p, acting regularly. (Hint: Show that the number
of elements not of order p is equal to the order of
G_{α}, and deduce that G_{α} is a
normal subgroup of G.)
13. This question should only be attempted with the help of a computer algebra
system such as GAP, otherwise the computations will be rather long!
Let G be a nonabelian simple transitive group of degree 11.
 Show that the Sylow 11subgroup P of G has order 11,
and that its normaliser has order 55. (You may use the result of the
preceding question, and the fact that a simple permutation group of
degree greater than 2 cannot contain an odd permutation.)
 Show that, unless G is the alternating group A_{11},
the Sylow 5subgroup Q of G has order 5, by verifying that
G cannot contain either of the 5cycles of an element in the
normaliser of P. Show further that
C_{Q}(Q)=Q, by examining which elements of the
symmetric group S_{11} commute with Q.
 Show that a generator of Q is conjugate in G to its
inverse. What is the cycle structure of a conjugating element x?
 Hence show that the group generated by P, Q and x
is either the alternating group A_{11} or a 2transitive
group of order 660. Identify the group G in the latter case
(compare Question 4).
 In the cases where the group has order 660, show that there are only
two choices for an element y satisfying y^{2}=x
and normalising Q and contained in a simple group, up to inversion. If
y is such an element, show that P, Q and y
generate A_{11} in one case, and a sharply 4transitive
group H of order 7920 in the other.
14. Investigate similarly the possibilities for a transitive simple group
of degree 7 or 23.
15. This problem is taken from the puzzle page
of METRO, 20 December 2000. First the following question was posed.
Match each of these languages to where they are spoken:
1. Amharic 
A. Brazil 
2. Farsi 
B. Ethiopia 
3. Portuguese 
C. India 
4. Telegu 
D. Iran 
5. Urdu 
E. Pakistan 
The paper then asked:
If the options for this puzzle were given in an entirely random order,
how many of the five pairs of answers would line up correctly in the
same row, averaged over many puzzles? What about if there were ten
options in each column?
16. This question is Enigma 1124 from New Scientist, where you can find
it stated with more detail. It can be solved by a few applications of the
OrbitCounting Lemma, or more easily by the Cycle Index Theorem.
A stained glass window consists of nine squares of glass in a
3 × 3 array. Of the nine squares, k are red, the rest
blue. A set of windows is produced such that any possible window can be formed
in just one way by rotating and/or turning over one of the windows in the
set. Altogether there are more than 100 red squares in the set. Find k.
17. Let PGL(2,5) denote the group of linear fractional transformations of
the projective line over GF(5).
Show that PGL(2,5) is a subgroup of S_{6} of order 120.
Hence show that
 PGL(2,5) is isomorphic to S_{5};
 S_{6} has an outer automorphism.
18. Let S=Sym(Ω) be the symmetric group on an infinite
set Ω. Show that the number of orbits of
S x ... x S (with k factors, acting
on the disjoint union of k copies of Ω) on the set of
nsets is equal to the number of choices of k nonnegative
integers with sum n. Hence show that this number is
(n+k1 choose n).
19. Let A be the group of orderpreserving permutations of the
rational numbers. Prove that the number of orbits of
A Wr A (in its imprimitive action) on nsets
is equal to the number of expressions for n as an ordered sum of
positive integers. Hence show that this number is 2^{n1}
for n > 0.
More generally show that the number of orbits of
A Wr ... Wr A (with k factors)
on nsets is k^{n1}
for n > 0.
20. Let G=Sym(Δ) be the symmetric group on an infinite
set Δ, and let Ω be the set of 2element subsets of
Δ. Then G acts as a permutation group on Ω.
Show that G in this action is oligomorphic, and that the number
of orbits on nsubsets of Ω is equal to the number of
simple undirected graphs with n edges and no isolated vertices.
21. Let C be the Fraissé class consisting of all finite
undirected graphs which have no multiple edges but may have loops (with at
most one loop at each vertex). Let G be the automorphism group of
the corresponding countable homogeneous structure. Prove that the number
of orbits of G on ntuples of distinct points is equal to
2^{n(n+1)/2}.
22. The weight of a monomial
s_{1}^{a1}+...+s_{n}^{an}
in the indeterminates s_{1},...,s_{n} is defined
to be s_{1}+...+ns_{n}. So, in the cycle index
of a permutation group of degree n, every monomial has weight
n.
Prove that, if Z(G)=F_{1}F_{2},
then all monomials in F_{i} have the same weight
n_{i}, where n_{1}+n_{2}=n.
Prove that the cycle index of the symmetric or alternating group is
irreducible over the integers (ignoring the factor of 1/G).
23. For each n from 5 to 33 inclusive, or for as many as you can,
find a primitive permutation group of degree n other than
S_{n} and A_{n}.
(Harder!) Show that the only primitive groups of degree 34 are the symmetric
and alternating groups.
Book homepage

Permutation groups resources
Peter J. Cameron
14 October 2009.