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 Sn is a point i such that ig <= i; it is a strict descent if ig < i. Prove that, if a subgroup G of Sn 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 (n-h)/2. Deduce the Orbit-Counting Lemma.
3. (Antonio Machì, Roma)

(a) Let z(g) be the number of cycles of a permutation g in Sn, and t(g) the minimum number of transpositions whose product is g. Prove that


(b) Prove that, if t1, ..., tk are transpositions which generate a transitive subgroup of Sn, then k >= n-1. If, further, t1...tk=1, then k >= 2n-2 and k is even.

(c) Hence show that, if g1, ..., gm generate a transitive subgroup of Sn, then

z(g1) + ... + z(gm) <= (m-1)n+1.
If, further, g1...gm=1, then
z(g1) + ... + z(gm) <= (m-2)n+2,
and the difference of these two quantities is even.

(d) How should the preceding result be modified if the group generated by g1, ..., gm has a prescribed number p of orbits?

(e) Suppose that g1, g2, g3 generate a regular subgroup G of Sn, and g1g2g3=1. Let z(g1)+z(g2) +z(g3)=n+2-2g. Prove Hurwitz's Theorem:

If g > 1 then the order of G is at most 84(g-1).
Construct an example meeting the bound when g=3.

Hint: If gi has order ni for i=1,2,3, show that

1/n1+1/n2+1/n3 = 1 - 2(g-1)/n,
where n=|G|.

For a crib, see:

A. Machì, The Riemann-Hurwitz formula for the centralizer of a pair of permutations, Arch. Math. 42 (1984), 280-288.

A. Jacques, Sur le genre d'une paire de substitutions, C.R. Acad. Sci. Paris 267 (1968), 625-627.

4. Define the automorphism group of a G-space Ω, 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 NG(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)(p-1)/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 p-subgroup and N its normaliser. Show that |G:N|=p+1, and that, acting on the cosets of N, G is a 2-transitive group in which the stabiliser of a point is isomorphic to the group x -> a2x+b of permutations of GF(p) (fixing a point infty).

Now show that the 2-point stabiliser is cyclic of order (p-1)/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), 57-59.

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 non-trivial 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 33-34 (and 79) of the book that there are 30 projective planes on a set of 7 points, falling into two orbits O1 and O2 of size 15 under the action of the alternating group A7.

Construct a new geometry with three kinds of elements, "Points", "Lines" and "Planes", as follows:

Prove that this geometry is isomorphic to 3-dimensional projective space over GF(2). (You may find it convenient to define an addition on the set {0} ∪ O1 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 2-group, using the existence and structure of the Planes to verify that addition is associative.)

Deduce that A7 is a subgroup of PSL(4,2) with index 8. Hence conclude that PSL(4,2) is isomorphic to A8.

8. Let Pn be the set of all partitions of the set {1, ..., n}. There is a function C from Sn to Pn, which maps any permutation to the partition induced by its cycles.

Prove that the set C(G), for a permutation group G, determines

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'=Sn, and let H' and K' be the subgroups of G' obtained by embedding G in Sn 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. 364-367 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 Sn, and k a positive integer not greater than n. The k-closure G(k) consists of all permutations in Sn which preserve all the G-orbits on k-tuples; that is, all permutations h in Sn which satisfy
for all i1, ..., ik, there exists g in G such that i1g=i1h, ..., ikg=ikh.
Prove the following: 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 Orbit-Counting Lemma.
12. Let G be a transitive permutation group of prime degree p, and let P be a Sylow p-subgroup of G. Suppose that NG(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 non-abelian simple transitive group of degree 11.

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 Orbit-Counting 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 S6 of order 120.

Hence show that

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 n-sets is equal to the number of choices of k non-negative integers with sum n. Hence show that this number is (n+k-1 choose n).
19. Let A be the group of order-preserving permutations of the rational numbers. Prove that the number of orbits of A Wr A (in its imprimitive action) on n-sets is equal to the number of expressions for n as an ordered sum of positive integers. Hence show that this number is 2n-1 for n > 0.

More generally show that the number of orbits of A Wr ... Wr A (with k factors) on n-sets is kn-1 for n > 0.

20. Let G=Sym(Δ) be the symmetric group on an infinite set Δ, and let Ω be the set of 2-element 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 n-subsets 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 n-tuples of distinct points is equal to 2n(n+1)/2.
22. The weight of a monomial s1a1+...+snan in the indeterminates s1,...,sn is defined to be s1+...+nsn. So, in the cycle index of a permutation group of degree n, every monomial has weight n.

Prove that, if Z(G)=F1F2, then all monomials in Fi have the same weight ni, where n1+n2=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 Sn and An.

(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.