Problems on Permutation Groups

??? ??? ???

These are research problems containing notes and references to solutions if they exist. There is also a list of old problems from my homepage; if you are interested in exercises on permutation groups, there are many in my book, and you can find some further exercises on the web. You may also be interested in the Permutation Groups Resources Page, or the page devoted to problems from the paper P. J. Cameron, Permutations, pp. 205-239 in Paul Erdős and his Mathematics, Vol. II (ed. G. Halász, L. Lovász, M. Simonovits and V. T. Sós), Bolyai Society Mathematical Studies 11, Springer, Berlin, 2002.

Problem 1. Is there a function F(m,p) (where the first argument is an integer and the second a prime) such that, if G is a finite permutation group which is a p-group with m orbits, each of size at least pF(m,p), then G contains a fixed-point-free element? (This is a very old problem; for p=2, it is implicitly due to Isbell in 1959.)

STOP PRESS 23 December 2008: Eleonora Crestani and Pablo Spiga have claimed a negative solution to this problem. More news later . . .

Problem 2. Let G be a permutation group on an infinite set X. There is a graded algebra A[G] associated with G as follows: the nth homogeneous component Vn is the set of all G-invariant functions from the set of n-element subsets of X to the complex numbers; multiplication is defined by the rule that, if f in Vn, g in Vm, and K is an (n+m)-element set then

(fg)(K) = sum f(L)g(K-L) : L subseteq K, |L| = n.

The constant function e in V1 with value 1 is not a zero-divisor. We say that G is entire if A[G] is an integral domain, and strongly entire if A[G]/eA[G] is an integral domain. It is conjectured that G is (strongly) entire if and only if it has no finite orbits on X. In the absence of a proof of this conjecture, can one show the following:

If the permutation groups G1 on X1 and G2 on X2 are (strongly) entire, then G1 × G2 (in its intransitive action on X1 union X2) is (strongly) entire.
Note: Maurice Pouzet has proved that, if G has no finite orbits, then G is entire. This appears in Theor. Inform. Appl. 42 (2008), 83-103.
Problem 3. Let S be the symmetric group on the infinite set X. Consider the product action of S2 on X2, and let an be the number of orbits on subsets of size n. The problem is to find a formula for, or an efficient means of calculating, an.

The number an has various other interpretations:

The initial terms in the sequence can be found here.

Problem 4. This problem is due to Dragan Marusic and Mikhail Klin. It appears in the research problems from the 15th British Combinatorial Conference. A permutation group G is 2-closed if any permutation which preserves the orbits of G on ordered pairs belongs to G. Problem: is there a 2-closed transitive permutation group containing no non-identity semiregular subgroup?

(Not every transitive permutation group contains a non-identity semiregular subgroup; the smallest counterexample has degree 12.)

Note: Michael Giudici has some partial results on this problem, including the statement that every minimal normal subgroup of any counterexample to the conjecture is intransitive. See:

Problem 5. A base for a permutation group G is a sequence of points whose pointwise stabiliser is the identity; it is irredundant if no point in the sequence is fixed by the stabiliser of its predecessors. The group G is said to be an IBIS group if any two irredundant bases have the same number of elements. If this condition holds, then the irredundant bases are the bases of a matroid (and conversely). It is too much to ask for a classification of IBIS groups (since, for example, any semiregular group is IBIS); but can one classify the matroids which can arise?

Note added 22 November 2001: The matroids include all those representable over finite fields (with each element replaced by q parallel elements, where q is the field order). See Problem 18 below for further details.

Problem 6. McIver and Neumann, Quart. J. Math. (2) 38 (1987), 473-488, showed that a subgroup of the symmetric group Sn can be generated by at most n/2 elements, provided that n is at least 4. Problem: Give an efficient algorithm to find such a generating set, preferably an "on-line" algorithm (one which, given a small generating set for H and a permutation g, finds efficiently a small generating set for the group generated by H and g).
Problem 7. Martin Liebeck and Aner Shalev have shown that there is an absolute constant c such that an almost simple primitive finite permutation group, which is not a symmetric or alternating group acting on subsets or partitions, or a classical group acting on subspaces or complementary pairs of subspaces in its natural module, has a base of size c. Does this assertion hold with c = 5 (if we allow finitely many more exceptions)?

Note added 13/7/2007: It has now been proved by Burness et al. that the assertion holds for c = 6, with a single exception, the Mathieu group M24.

Problem 8. Let G be a transitive permutation group on a set X. For each orbit Oi of G on X2, we associate a basis matrix Ai, whose xy entry is equal to 1 if (x,y) is in Oi, or 0 otherwise. The matrices Ai span an algebra, which is the centraliser algebra of the permutation group G.

A subalgebra of the centraliser algebra which contains the identity matrix and is spanned by symmetric zero-one matrices is the Bose-Mesner algebra of an association scheme on the set X, and G acts as a group of automorphisms of this association scheme. There is always at least one such subalgebra, namely the span of I and J-I, where J is the all-one matrix. We call this subalgebra or association scheme trivial.

Problem: For which transitive permutation groups is it true that the only association scheme invariant under G is the trivial one?

This class of groups includes the 2-homogeneous groups. Any such group must be primitive, and (if not 2-homogeneous) is either of diagonal type or almost simple.

Examples which are not 2-homogeneous do exist. Some can be found in table 3.5.1 of I. A. Faradzev, M. H. Klin and M. E. Muzichuk, "Cellular rings and groups of automorphisms of graphs", pp. 1-152 in Investigations in Algebraic Theory of Combinatorial Objects (ed. I. A. Faradzev, A. A. Ivanov, M. H. Klin and A. J. Woldar), Kluwer, Dordrecht, 1994. The smallest is the group PSL(3,3) acting on the cosets of PO(3,3); this group has degree 234. (I am grateful to Leonard Soicher for this reference).

No such group of diagonal type is known, and the problem of deciding whether any such group exists remains open. There are none having two or three simple factors in their socle. See:

Problem 9. A derangement problem.

Let d(k,n) be the proportion of derangements in the symmetric group Sn in its action on k-sets. Then d(k,n) tends to a limit a(k) as n tends to infinity. (So, for example, a(1)=e-1 - this is the usual "derangement problem".) Does a(k) tend monotonically to 1 as k tends to infinity?

Problem 10. It is known that, for any finite group G, if x(G,n) is the number of (unlabelled) graphs on n vertices whose automorphism group contains G, and y(G,n) the number whose automorphism group is precisely G, then the ratio y(G,n)/x(G,n) tends to a limit as n tends to infinity.

Problem: Does this result hold for trivalent graphs? What about other special classes of graphs such as strongly regular graphs?

Problem 11. The Parker vector of a finite permutation group G is the n-tuple whose kth component is the number of orbits of G on the set of k-cycles occurring in elements of G.

If G has the same Parker vector as a Frobenius group (resp. a 2-transitive group), is it a Frobenius group (resp. a 2-transitive group)?

Problem 12. Is the following true?
If P is a 2-group which is not elementary abelian, then some non-identity element of the centre of P is a square.
The answer to this question is negative. The smallest counterexamples have order 128, and there are two of them. This was found by Alexander Hulpke and Andreas Caranti. Alexander provided the following example in GAP: 

gap> g:=SmallGroup(128,36);

gap> z:=Centre(g);
Group([ f6, f7 ])
gap> r:=List(ConjugacyClasses(g),Representative);;
gap> s:=Filtered(r,i->Order(i)>2);;
gap> List(s,Order);
[ 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4 ]
gap> Set(List(s,i->i^2));
[ f4,f5,f4*f7,f5*f6,f3*f4*f5,f3*f4*f5*f6,f3*f4*f5*f7,f3*f4*f5*f6*f7 ]
gap> List(last,i->i in z);
[ false, false, false, false, false, false, false, false ]
If not, is the following weaker statement true?
If P is a 2-group which is not elementary abelian, and Q is a core-free subgroup of P, then there is an element lying in no conjugate of Q which is a square.
Avinoam Mann also suggested the above group as a possible counterexample to the second question. However, Steve Linton and John Murray both checked that there is no core-free subgroup Q for which it is a counterexample. So the question is still open.

Solution (13 September 2004): The answer to the second question is also negative. Pablo Spiga found that the group of order 128 with generators (1,2,7,3)(4,8)(5,11)(6,9)(10,14)(12,16,13,15), (1,4,7,5)(2,8)(3,11)(6,13,14,12)(9,15)(10,16), and (1,6)(2,9,3,10)(4,12,5,13)(7,14)(8,15)(11,16) is a counterexample. Indeed, in this group the set of elements with fixed points coincides with the set of squares. This group is SmallGroup(128,836) in the GAP library.

The motivating question, whether a vertex-transitive trivalent graph necessarily has a semiregular automorphism of order greater than 2, is currently still open. (But see Problem 23.)

Problem 13. It is known that, if G is a permutation group in which every non-identity element fixes exactly k points, then either G has a fixed set of size k, or G is one of a finite list of groups (for given k). The problem is to find a good upper bound (in terms of k) for the orders of the groups in this finite list.

For example, when k=2, the groups are the tetrahedral, octahedral and icosahedral groups, acting on the vertices, edges and faces of the corresponding polyhedra. (Every rotation has an axis, so has just two fixed points in this action.) So the correct bound is 60. (This is a theorem of Iwahori, J. Fac. Sci., Univ. Tokyo 11 (1964), 47-64.)

An upper bound in terms of k has been found by C. Franchi, On permutation groups of finite type, European J. Combinatorics 22 (2001), 821-837.

Problem 14. Let G be a finite group, a an automorphism of G, and X the semidirect product of G by the group generated by a. Suppose that every element of X not in G has prime order p.

It follows that the centraliser of a in G is a p-group. Let its order be pm.

A theorem of Kegel (Math. Z. 75 (1961), 373-376) shows that G is nilpotent. Then a theorem of Khukhro (Mat. Zametki 38 (1985), 652-657) shows that G has a normal subgroup whose nilpotency class and index are bounded by functions of p and m.

Is it true that the nilpotency class of G is bounded by a function of p and m?

This question has been settled in the affirmative by Andrei Jaikin, using a theorem of E. Khukhro, On locally nilpotent groups admitting a splitting automorphism of prime order, Mat. sb. 130 (1986), 120-127.

Problem 15. Let Sn and Pn be the respectively the symmetric group (the set of all permutations) and the set of all partitions on the set [1..n]. There is a function F from Sn to Pn which replaces every permutation by the partition corresponding to its cycle decomposition.

(a) Is there an efficient method to decide whether a set of partitions is the image under F of a subgroup of Sn?

(b) If G and H are subgroups of Sn such that F(G)=F(H), then G and H have the same order. Are they necessarily isomorphic?

Note added 19 May 2000: The answer to (b) is negative. 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. You can find a GAP program to verify this.

See P. J. Cameron, Partitions and permutations, Discrete Math. 291 (2005), 45-54.

Problem 16. Let G be a subgroup of the symmetric group Sn. For i = 0, ..., n, let pi be the probability that a random element of G has exactly i fixed points, and let Fi be the number of orbits of G on i-tuples of distinct points. These two sequences determine each other. In fact, N. Boston, W. Dabrowski, T. Foguel, P. J. Gies, J. Leavitt, D. T. Ose and D. A. Jackson, Communications in Algebra 21 (1993), 3259-3275, showed that, if
P(x) = Sum pi xi and F(x) = Sum Fi xi/i! , then
F(x) = P(x+1).

Now consider the linear analogue. Let G be a subgroup of the general linear group GL(n,q). For i = 0, ..., n, let pi be the probability that the fixed points of a random element form precisely an i-dimensional subspace, and let Fi be the number of orbits of G on linearly independent i-tuples. Again the two sequences determine each other.

Problem: Express the relation between these two sequences in terms of generating functions.

Note: This problem is now solved (2 August 2000). It is just a case of finding the right definitions of the q-analogues! See:

Problem 17. (An old problem revisited)

Let G be a permutation group on the infinite set X. Assume that G is oligomoprhic, that is, G has only finitely many (say fn) orbits on the set of n-element subsets of X. Dugald Macpherson, Proc. London Math. Soc. (3) 46 (1983), 471-486, showed that, if G is primitive on X (preserves no non-trivial equivalence relation) but not highly set-transitive ((that is, fn > 1 for some n), then the sequence (fn) grows exponentially, that is, limsup (fn)1/n > 1. These two assumptions apply throughout this problem, though analogous problems can be posed with primitivity relaxed.

  1. Is it true that lim (fn)1/n exists for any group G?
  2. What is the smallest possible value of the limsup? (Macpherson's lower bound of 21/5 has been improved by F. Merola to about 1.324. The smallest known value is 2.)
  3. What is the smallest limit point of the set of values of the limsup?

Further information on such sequences is available in my survey article.

Problem 18.

A base for a permutation group is a sequence of points whose stabiliser is the identity; it is irredundant if no point is fixed by the stabiliser of its predecessors. Cameron and Fon-Der-Flaass, Europ. J. Combinatorics 16 (1995), 537-544, called a permutation group an IBIS group if all irredundant bases have the same number of elements; they showed that the irredundant bases of an IBIS group are the bases of a matroid.

Problem: What is the relation between the Tutte polynomial of the matroid and the cycle index of the permutation group?

It is known that sometimes the first determines the second and sometimes vice versa. Perhaps there is a gadget which generalises both! See P. J. Cameron, Cycle index, weight enumerator and Tutte polynomial, Electronic J. Combinatorics 9(1) (2002), #N2 (10pp).

Problem 19.

How large is the largest antichain of subgroups of the symmetric group Sn? More precisely, estimate an/sn, where an is the size of the largest antichain and sn the total number of subgroups.

Problem 20.

Let L(G) be the subgroup lattice of the finite group G. Is the following true or false? Suppose that the Boolean lattice B(n) of subsets of an n-element set is embeddable as a meet-semilattice of L(G), and suppose that n is maximal with this property. Then there is an embedding of B(n) as meet-semilattice, such that the least element of B(n) is a normal subgroup of G.

Note: The quaternion group Q8 shows that we cannot make the least element of B(n) correspond to the identity in general.

Problem 21.

Let Z(G) denote the cycle index of the permutation group G, and let Fn*(G) be the number of orbits of G on the set of all n-tuples of its permutation domain.

Let G and H be permutation groups acting on sets X and Y respectively. We consider G×H as a permutation group on X×Y. We have

The second assertion is trivially proved directly. The challenge is to deduce it from the first; this will probably require methods of dealing with these very strange operations on polynomials.

Solution: Solved by Daniele Gewurz. See a paper by Daniele Gewurz, Francesca Merola and me in Discrete Mathematics 308 (2008), 386-394; doi: 10.1016/j.disc.2006.11.054

Problem 22.

Let G be a Frobenius group with Frobenius kernel N and Frobenius complement H having orders n and h respectively. Number the elements of N as x1,...,xn. Now let Xij be the n × n matrix with (k,l) entry equal to the cardinality of the intersection of xi-1Hxk and xj-1Hxl. Note that Xii = hI while, for i and j distinct, Xij is a zero-one matrix.

Is it true that

Sumk XikXkj = nXij+h(h-1)J,
where J is the all-one matrix?

Solution: This problem is now solved in the affirmative (but I have lost the solution . . .)

Problem 23. Since Problem 20 in the list of old problems has a negative solution, the following problem (due to John Sheehan and me, BCC problem 17.12) is open again.

Is it true that a vertex-transitive trivalent graph has a semiregular automorphism (one with all cycles of the same size) of order greater than 2?

Note: This has now been settled affirmatively: see P. J. Cameron, J. Sheehan and P. Spiga, Europ. J. Combinatorics 27 (2006), 924-930; doi: 10.1080/00927870701404812, and a stronger result has been given by Cai Heng Li, Proc. Amer. Math. Soc. 136 (2008), 1905-1910.

Problem 24. Let G be a permutation group of degree n. The base size of G is the smallest number b(G) of points whose stabiliser is the identity; the separation number of G is the smallest size of a set S of points such that, for any two distinct points x,y, there exists s in S such that x and y lie in distinct orbits of the stabiliser of s.

Clearly b(G) <= s(G). Is it true that, if G is primitive but not 2-transitive, then s(G) <= b(G) log n?

See Combinatorics Study Group notes on this problem (PDF file).

Problem 25. Let F be the set of sequences F of positive integers whose nth term is the number of orbits on n-tuples of distinct elements of an infinite permutation group.

Is F closed under pointwise multiplication?

I conjecture that the answer is "no". Specifically, let F be the sequence (1,2,4,10,26,...) whose nth term is the number of solutions of g2=1 in the symmetric group of degree n. This sequence belongs to F, but I conjecture that the sequence (1,4,16,100,676...) whose terms are the squares of the terms in this sequence is not in F.

Remark: The set of sequences counting orbits of permutation groups on all n-tuples is closed under pointwise multiplication. Moreover, the set of sequences counting orbits on n-tuples of distinct elements for groups with the property that the stabiliser of a finite set fixes no additional points is closed under pointwise multiplication.

Further remark: The answer in general is "no": if G is the stabiliser of a point in the symmetric group, the sequence begins 2, 3, 4, ..., but a group with 4 orbits on points must have at least 12 orbits on ordered pairs of distinct points. It is harder for transitive groups (where a possible counterexample is given in the question), and still more so for primitive groups.

Problem 26. I conjectured in 1972 that there is a function f with the following property: Let G be a finite primitive permutation group, with rank r; let s be the subrank of G, the maximum rank of a point stabiliser on any of its orbits. Then either Perhaps the time has come to revisit this conjecture.

The most extreme example I know is an extension of a 2n-dimensional vector space over GF(2) by a dihedral group of order 2(2n+1); this has rank 2n and subrank 2n-1+1. So perhaps the conjecture holds with a linear function f.

Problem 27. Let S be a set of elements of the symmetric group Sn. It is not always true that every element in the group generated by S can be written as a word in S of length bounded by a polynomial in n. (Take S to be a singleton whose element has maximum possible order in Sn.)
Problem: If the group generated by S contains a fixed-point-free element, can we always find one which is a word of polynomially bounded length?

My homepage | Permutation Groups Resources

Peter J. Cameron
p.j.cameron(at)qmul.ac.uk
11 September 2007

Permutation Groups Pages at Queen Mary:
Resources | Lecture Notes | Problems | The Book | Problems from "Permutations"
Maths Research Centre