Regular cycles of elements in finite primitive permutation groups

Cheryl Praeger, Pablo Spiga and I have just uploaded to the arxiv our preprint  Finite primitive permutation groups and regular cycles of their elements.   Everyone recalls from their first course in group theory that if you write a permutation in cycle notation, for example (1,2)(3,4,5)(6,7,8,9,10), then its order is the lowest common multiple of it cycle lengths. As I have just demonstrated, not every permutation must have a cycle whose length is the same as the order of the element. We call a cycle of an element g whose length is the order of g, a regular cycle.  A natural question to ask is when can you guarantee that a permutation has a regular cycle? Or in particular, for which permutation groups do all elements have a regular cycle?

Clearly, the full symmetric group contains elements with no regular cycles, but what about other groups?  Siemons and Zalesskii showed that for any group G  between PSL(n,q) and PGL(n,q) other than for (n,q)=(2,2) or (2,3), then in any action of G, every element of G has a regular cycle, except G=PSL(4,2) acting on  8 points. The exceptions are due to isomorphisms with the symmetric or alternating groups.  They also later showed that for any finite simple group G,other than the alternating group, that admits a 2-transitive action, in any action of G every element has a regular cycle. This was later extended by Emmett and Zalesskii to any finite simple classical group not isomorphic to PSL(n,q).

With these results in mind, we started investigating elements in primitive permutation groups. The results of this work are in the preprint. First we prove that for k\leq m/2, every element of Sym(m) in its action on k-sets has a regular cycle if and only if m is less than the sum of the first k+1 primes. After further computation we were then willing to make the following conjecture:

Conjecture: Let G\leqslant Sym(\Omega) be primitive such that some element has no regular cycle. Then there exist integers k\geq1, r\geq1 and m\geq5 such that
G preserves a product structure on \Omega=\Delta^r with |\Delta|=\binom{m}{k}, and Alt(m)^r  \vartriangleleft G\leqslant Sym(m)\textrm{wr} Sym(r), where Sym(m) induces its k-set action on \Delta.

The general philosophy behind why such a result should be true is that most primitive groups are known to be small in terms of a function of the degree.  There is a large body of work bounding the orders of primitive permutation groups with the best results due to Maroti. The actions of Sym(m) on k-sets are the usual exceptions.

Our paper  goes about attempting to prove this conjecture. We make substantial progress and reduced its proof to having to deal with all the primitive actions of classical groups. Note that Emmett and Zalesskii only dealt with simple ones.  One consequence of our work is we showed that every automorphism of a finite simple group has a regular cycle in its action on the simple group.

Pablo and Simon Guest have subsequently gone on to prove the result for all actions of classical groups and so the conjecture is now a theorem.

Pablo gave a great talk about the conjecture and its subsequent proof  at the recent BIRS workshop on Permutation Groups in Banff which you can view here.

Two postdoctoral positions

We again have two new postdoctoral positions in the Centre for the Mathematics of Symmetry and Computation here at UWA, funded by two Australian Research Council Discovery Project grants. Both are two-year positions and in the field of finite permutation groups and graph symmetry. One position is on a grant held by Michael Giudici and the other is on a grant held by myself, Alice Devillers, and Cheryl Praeger.

The deadline for applications is 8th February (2013).

More details and instructions on how to apply can be found here (refs 4261 and 4262).


Last week and this week I have been at the University of Southampton visiting Tim Burness to work on our big project concerning derangements. Despite it being summer here, the weather has been  more like a Perth winter. I am staying in a self-catered hall of residence so the cooked breakfasts have come to an end and it is back to cornflakes.

A derangement is a permutation that moves all the points of the set which it acts on.  I have only recently been converted to the term derangement, have previously preferred the term fixed point free element. Peter Cameron has had a bit to say about derangements in several posts on his blog.

By the Orbit-Counting Lemma, the average number of fixed points of an element of a transitive permutation group is 1. Since the identity permutation fixes all the elements of the set,  a transitive permutation group on a set of size at least two must therefore contain a derangement.   This leads to the natural questions that have attracted a lot of attention:

  • how many derangements are there?
  • what properties do the derangements have?

The project with Tim focuses on the second.

Fein, Kantor and Schacher proved that every transitive permutation group contains a derangement of prime power order. The result was motivated by an application to number theory as the existence of a derangement of prime power order is equivalent to the relative Brauer group of any nontrivial field extension of global fields being infinite. Whereas the existence of a derangement is an elementary observation, the proof of the existence of one of prime power order relies heavily on the Classification of Finite Simple Groups. The proof though does not give information about which primes or which powers.

In fact, not every transitive permutation group contains a derangement of prime order. My favourite example is the Mathieu group M_{11} in its 3-transitive action on 12 points.  Note that if a group G acts transitively on a set with the stabiliser of some point being the subgroup H, then an element g fixes a point if and only if it is conjugate to an element of H.   Since M_{11}  contains a unique conjugacy class of elements of order 2 and a unique class of elements of order 3, and 6  divides the order of the stabiliser of a point (PSL(2,11)), it follows that all elements of order 2 and 3 fix a point.

Continue reading “Derangements”

Quotients of geometries

Last week I uploaded to the arxiv the latest in a sequence of papers that introduces a “normal quotient” method for the study of incidence geometries. The first paper was `Quotients of incidence geometries‘ with Philippe Cara, Alice Devillers and Cheryl Praeger, the second was `Basic and degenerate geometries‘ with Cai Heng Li, Geoffrey Pearce and Cheryl Praeger, and the third was `Basic coset geometries‘ with Geoffrey and Cheryl. I will give a brief outline of the whole project here including motivation and some of the main results.

The study of graphs via their quotients has proved a very fruitful avenue of investigation. The general method for studying a particular class of graphs is to identify some reduction process that takes any graph in the family to a “basic graph” in the family, determine all “basic graphs”, and then determine all ways of lifting the “basic graphs” so that we can enumerate all graphs in the class. Examples of classes of graphs where this has proved a useful method of attack are:

  • distance-transitive graphs: Distance-transitive graphs with an imprimitive group of automorphisms are either bipartite or antipodal and can be reduced to smaller distance-transitive graph. Hence the basic graphs are the ones with a primitive group of automorphisms.
  • {s}-arc transitive graphs: If {G} acts transitively on the set of {s}-arcs, for {s\geq 2} of a graph {\Gamma} and {G} has a normal subgroup {N} with at least 3 orbits on vertices then the quotient graph {\Gamma_N} is also {s}-arc transitive and {\Gamma} is cover of {\Gamma_N}. Hence the basic graphs to study are those for which every nontrivial normal subgroup of {\mathrm{Aut}(\Gamma)} has at most two orbits, that is, {\mathrm{Aut}(\Gamma)} is quasiprimitive (all nontrivial normal subgroups are transitive) or biquasiprimitive (all have at most 2 orbits but not all are transitive).
  • vertex-intransitive, locally {s}-arc transitive graphs: Here the graphs are bipartite and the bipartite halves are the two orbits of {G} on vertices. We can apply the same quotienting process and the basic graphs are those for which {G} is quasiprimitive on at least one orbit.

In all cases we can use the O’Nan-Scott Theorem for primitive or quasiprimitive groups to study the basic graphs. This involves seeing which primitive/quasiprimitive types are possible and then determining all graphs for a given type. Usually we can reduce to studying the case where the action is either almost simple or affine.

The aim of our project on incidence geometries is to extend these methods to geometries. Jacques Tits introduced the notion of a building to study the simple groups of Lie type. Francis Buekenhout then introduced incidence geometries and their associated diagrams as a generalisation in an attempt to find a larger class of geometries that would include buildings but also contain geometries associated to the sporadic simple groups. One rationale for our project was to give a geometrical justification for the study of geometries of simple groups. The hope was that geometries of almost simple groups would arise as one of a small number of “basic” families of graphs.

First some definitions. A pregeometry {\Gamma = (X,\ast,t)} consists of a set {X} of elements (often called points) with an incidence relation {\ast} on the points, and a map {t} from {X} onto a set {I} of types. The incidence relation is symmetric and reflexive, and if {x \ast y} we say that {x} and {y} are incident. Furthermore if {x \ast y} with {x \neq y} then {t(x) \neq t(y)}. The number {|I|} of types is called the rank of the pregeometry. A rank 2 geometry is merely a bipartite graph and so our earlier work on quotients of locally {s}-arc transitive graphs can be seen as investigating the rank 2 case.

A flag {F} is a set of pairwise incident elements of {\Gamma} (which implies that the elements of {F} are of pairwise distinct types). The type of a flag is the set of types of its elements. A chamber is a flag containing one element of each type. A pregeometry in which every flag is contained in a chamber is called a geometry. The typical example is a projective space. Here the elements are the points, lines, planes etc and incidence is given by inclusion.

Let {\Gamma=(X,*,t)} be a pregeometry and let {\mathcal{B}} be a partition of {X} which is a refinement of the type partition of {\Gamma}. We define a new pregeometry {\Gamma_{/\mathcal{B}}=(\mathcal{B},*_{/\mathcal{B}},t_{/\mathcal{B}})} where

  1. {B_1 *_{/\mathcal{B}} B_2} if and only if there exist {\alpha_i\in B_i} (for {i=1,2}) with {\alpha_1*\alpha_2},
  2. {t_{/\mathcal{B}}:X_{\mathcal{B}}\rightarrow I} and {t_{/\mathcal{B}}(B)=t(\alpha)} for {\alpha\in B}.

Quotients of geometries under certain conditions were studied by Tits and Pasini. However, in general the quotient of a geometry is not necessarily a geometry. Our first paper investigated necessary and sufficient conditions for when the quotient of a geometry is a geometry, and also which geometrical properties are preserved by quotients.

The automorphism group of a pregeometry is the group of all permutations of the element set {X} that preserves the type of each element and that preserves incidence. We say that a group of automorphisms {G} is vertex-transitive on the pregeometry if {G} is transitive on each set {X_i=t^{-1}(i)} for {i\in I}, that is, is transitive on each set of points of a given type. That is, the orbits of {G} on points are as large as possible. We say that {G} is incidence-transitive if for each pair {\{i,j\}} of types, {G} is transitive on the set of flags of type {\{i,j\}}. We say that {G} is flag-transitive if for each {J\subseteq I}, {G} is transitive on the set of flags of type {J}.

One class of pregeometries are coset pregeometries. Given a group {G} with subgroups {\{G_i\}_{i\in I}}, the coset pregeometry {\Gamma=\Gamma(G,\{G_i\}_{i\in I})} is the pregeometry whose elements of type {i\in I} are the right cosets of {G_i} in {G} and two cosets {G_ix} and {G_jy} are incident if {i\neq j} and {G_ix\cap G_jy} is nonempty. The group {G} acts by right multiplication on the elements of {\Gamma} inducing automorphisms of the pregeometry, that is, maps incident elements to incident elements. In our first paper we showed that a pregeometry is a coset pregeometry if and only if its group of automorphisms is incidence-transitive and vertex-transitive and the pregeometry contains a chamber.

One of the main results of our first paper is that the quotient of a coset pregeometry is still a coset pregeometry. This motivated us to take the class of coset pregeometries with connected rank 2 truncations as the class of objects that we should study, instead of the narrower class of flag-transitive geometries.

The next thing to do is to determine what the degenerate and basic coset pregeometries should be. The basic pregeometries are those such that all quotients are degenerate. We investigated this question in our second paper. The definitions will depend on whether we are taking normal quotients (that is quotients with respect to the set of orbits of some normal subgroup) or imprimitive quotients, (that is quotients with respect to some {G}-invariant partition). In the normal quotients case we were able to show that the basic pregeometries can be built from pregeometries where for each type {i}, the action of {G} is quasiprimitive on each set of elements of type {i}. In the imprimitive quotients case we replace `quasiprimitive’ with `primitive’.

Thus the important pregeometries to study are those where {G} is quasiprimitive on each set of elements of type {i}. We investigated these in our third paper which contains many constructions of flag-transitive geometries. One type of primitive action is the almost simple case. The projective space {PG(n,q)} is an example of an incidence geometry of rank {n} and the automorphism group {P\Gamma L(n+1,q)} is primitive of almost simple type on each set of elements. Our initial aim was to see if there was some number {N} such that if {\Gamma} were a flag-transitive geometry of rank at least {N} such that the automorphism group {G} acts primitively on each set of elements then {G} is almost simple. However, the main result of our third paper was to show that this is not true. In fact for each positive integer {n} and each of the 8 O’Nan-Scott types of primitive group, we were able to find a primitive group {G} on a set {\Omega} whose action is primitive of that type and construct a rank {n} geometry {\Gamma} such that each set of elements of a given type is a copy of {\Omega} and {G} acts on flag-transitively on {\Gamma}.


Point regular automorphism groups of generalised quadrangles

John and I have just uploaded to the arxiv a copy of our recent paper, `Point regular automorphism groups of generalised quadrangles‘. We investigate the regular subgroups of some of the known generalised quadrangles. We demonstrate that the class of groups which can act as a point regular group of automorphisms of a generalised quadrangle is much wilder than previously thought.

A permutation group {G} on a set {\Omega} acts regularly on a set {\Omega} if it acts transitively on {\Omega} and only the identity of {G} fixes an element of {\Omega}. Studying regular automorphism groups of projective planes has received much attention over the years. Recently attention has turned to the study of groups acting regularly on generalised quadrangles.

Dina Ghinelli proved in 1992 that a Frobenius group or a group with a nontrivial centre cannot act regularly on the points of a generalised quadrangle of order {(s,s)}, where {s} is even. Stefaan De Winter and Koen Thas proved in 2006 that if a finite thick generalised quadrangle admits an abelian group of automorphisms acting regularly on its points, then it is the Payne derivation of a translation generalised quadrangle of even order. Satoshi Yoshiara proved that there are no generalised quadrangles of order {(s^2 , s)} admitting an automorphism group acting regularly on points.

Continue reading “Point regular automorphism groups of generalised quadrangles”

Rank 3 permutation groups

Alice Devillers, Cai Heng Li, Geoff Pearce, Cheryl Praeger and I have just uploaded to the arxiv a preprint of our recently submitted paper `On imprimitive rank 3 permutation groups‘.

A permutation group {G} on a set {\Omega} also acts on the set {\Omega\times\Omega} via {(\omega_1,\omega_2)^g=(\omega_1^g,\omega_2^g)}. If {G} is transitive on {\Omega} then we cannot expect it to be transitive on {\Omega\times\Omega} as the subset {\{(\omega,\omega)\mid\omega\in\Omega\}} is an orbit. The best that we can hope for is that {G} has two orbits on {\Omega\times\Omega} and this is equivalent to {G} acting 2-transitively on {\Omega}, that is, {G} acts transitively on the set of ordered pairs of distinct elements of {G}. The rank of a permutation group {G} is the number of orbits of {G} on {\Omega\times\Omega}. Thus 2-transitive groups have rank 2.

The number of orbits of {G} on {\Omega\times \Omega} is equal to the number of orbits of the point stabiliser {G_{\omega}} on {\Omega}. Indeed, given an orbit {\Delta} of {G_{\omega}} on {\Omega} the set {\{(\omega,\delta)^g\mid \delta\in\Delta,g\in G\}} is an orbit of {G} on {\Omega\times\Omega}. Conversely, given an orbit {\Delta} of {G} on {\Omega\times\Omega}, the set {\{\delta\in\Omega\mid (\omega,\delta)\in\Delta\}} is an orbit of {G_{\omega}} on {\Omega}. In this set up, {\{\omega\}} corresponds to {\{(\omega,\omega)\mid\omega\in\Omega\}}.

Continue reading “Rank 3 permutation groups”

Strongly regular Cayley graphs

Have you ever asked someone a question only to find that they asked you the same question a few months earlier? Well that happened in our research group today when Michael and I knocked on Pablo Spiga’s door to ask him whether he knows of a particular type of strongly regular Cayley graph. Deja vu immediately hit us, and the rest is a shameful example of a poor memory. Anyway, here is the problem that the three of us do not know the answer to, but for which someone out there might enlighten us.

Does there exist a strongly regular Cayley graph Cay(G, S) where G is a nonabelian simple group?

The O’Nan-Scott Theorem

I have decided that any mathematical blog entitled SymOmega should have an expository post about one of the most influential theorems of permutation group theory, that is, The O’Nan-Scott Theorem. Originally, this was a theorem about maximal subgroups of the symmetric group.  It appeared as an appendix to a paper of Leonard Scott in the proceedings of the Santa Cruz symposium on finite simple groups in 1979, with a footnote that Michael O’Nan had independently proved the same result. Apparently there are even earlier versions due to various people but it was the Classification of Finite Simple Groups (CFSG) which meant that it would become very useful.

In its simplest form the theorem states that a maximal subgroup of the symmetric group \mathrm{Sym}(\Omega) where |\Omega|=n, is one of the following:

  1. S_k\times S_{n-k}, the stabiliser of a k-set (that is, intransitive),
  2. S_a \mathrm{wr} S_b with n=ab, the stabiliser of a partition into b parts of size a (that is, imprimitive), or
  3. primitive (that is, preserves no nontrivial partition) and of one of the following types:
  • \mathrm{AGL}(d,p),
  • S_\ell \mathrm{wr} S_k with n=\ell^k, the stabiliser of a product structure \Omega=\Delta^k,
  • a group of diagonal type, or
  • an almost simple group.

(These  types will be explained in further detail below).

It was soon recognised (perhaps first in a paper of Peter Cameron)  that the real power is in the ability to split the finite primitive groups into various types.  Problems concerning primitive groups can then be studied by solving them for each type.  This often sees questions about primitive groups reduced to questions about simple groups and then the force of the classification can be harnessed to get your result.  Furthermore, many results about transitive permutation groups can be reduced to the primitive case and so we actually have a tool for studying questions about transitive groups.

The division of primitive groups into various types is usually finer than given in the statement about maximal subgroups of S_n as we are no longer concerned about maximality in S_n but instead are more concerned about the types of actions. In Cameron’s original paper, the twisted wreath product case (again, more details later) which does not appear as a maximal subgroup of S_n but is an important type of action with a distinctly different flavour to the maximal subgroup S_\ell \mathrm{wr} S_k  it is contained in,  was left out and this was corrected in a subsequent paper of Aschbacher and Scott, and in work of Laci Kovacs. A complete self-contained proof is given in a paper by Martin Liebeck, Cheryl Praeger and Jan Saxl.

Since I am from Perth, I usually  follow the  division and labelling into 8 types due to Cheryl Praeger which appears here and here.  First we need to deal with a few preliminaries.

Continue reading “The O’Nan-Scott Theorem”

Up ↑