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

z(g)+t(g)=n.

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

• the Points are the elements of O1;
• the Lines are the 3-element subsets of the 7-set;
• the Planes are the elements of O2;
• 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 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

• the order of G;
• for each p in Pn, 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'=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:
• G(k) contains G(k+1);
• G(n) = G;
• G is k-transitive if and only if G(k) = Sn;
• 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 Orbit-Counting 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 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.

• Show that the Sylow 11-subgroup 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 A11, the Sylow 5-subgroup Q of G has order 5, by verifying that G cannot contain either of the 5-cycles of an element in the normaliser of P. Show further that CQ(Q)=Q, by examining which elements of the symmetric group S11 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 A11 or a 2-transitive 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 y2=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 A11 in one case, and a sharply 4-transitive 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

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

• PGL(2,5) is isomorphic to S5;
• S6 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 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.

Peter J. Cameron
14 October 2009.