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 (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 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₁, ..., t_k are transpositions which generate a transitive subgroup of S_n, then k >= n-1. If, further, t₁...t_k=1, then k >= 2n-2 and k is even.

z(g₁) + ... + z(g_m) <= (m-1)n+1.

If, further, g₁...g_m=1, then

z(g₁) + ... + z(g_m) <= (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 g₁, ..., g_m has a prescribed number p of orbits?

(e) Suppose that g₁, g₂, g₃ generate a regular subgroup G of S_n, and g₁g₂g₃=1. Let z(g₁)+z(g₂) +z(g₃)=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 g_i has order n_i for i=1,2,3, show that

1/n₁+1/n₂+1/n₃ = 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 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)(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 -> a²x+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 O₁ and O₂ of size 15 under the action of the alternating group A₇.

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

the Points are the elements of O₁;
the Lines are the 3-element subsets of the 7-set;
the Planes are the elements of O₂;
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} ∪ O₁ 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 A₇ is a subgroup of PSL(4,2) with index 8. Hence conclude that PSL(4,2) is isomorphic to A₈.

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. 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 S_n, and k a positive integer not greater than n. The k-closure G^(k) consists of all permutations in S_n which preserve all the G-orbits on k-tuples; that is, all permutations h in S_n which satisfy

for all i₁, ..., i_k, there exists g in G such that i₁g=i₁h, ..., i_kg=i_kh.

Prove the following:

G^(k) contains G^(k+1);
G⁽ⁿ⁾ = G;
G is k-transitive if and only if G^(k) = S_n;
if G is abelian then so is G⁽²⁾;
if G is the automorphism group of a graph (acting on the vertices) then G⁽²⁾ = 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 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 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 A₁₁, 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 C_Q(Q)=Q, by examining which elements of the symmetric group S₁₁ 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₁₁ 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 y²=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₁₁ 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

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 S₆ of order 120.

Hence show that

PGL(2,5) is isomorphic to S₅;
S₆ 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 2^n-1 for n > 0.

More generally show that the number of orbits of A Wr ... Wr A (with k factors) on n-sets is k^n-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 2^n(n+1)/2.

22. The weight of a monomial s₁^a₁+...+s_n^a_n in the indeterminates s₁,...,s_n is defined to be s₁+...+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₁F₂, then all monomials in F_i have the same weight n_i, where n₁+n₂=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.

1. Amharic	A. Brazil
2. Farsi	B. Ethiopia
3. Portuguese	C. India
4. Telegu	D. Iran
5. Urdu	E. Pakistan