Bases for primitive permutation groups

The theory of permutation groups is a classical area of algebra, which arises naturally in the study of symmetry in a vast range of mathematical and physical systems. With origins in the 19th century, permutation groups remain an important area of current research in Pure Mathematics, with far-reaching applications across the sciences and beyond. In the last thirty years the subject has been greatly invigorated by the classification of finite simple groups, a truly remarkable theorem which is widely regarded as one of the greatest achievements of 20th century mathematics. This has led to many interesting problems and the development of powerful new techniques to solve them.Let G be a group of permutations of a set S. A subset B of S is a base for G if the identity is the only element of G fixing each of the points in B. We define the base size of G, denoted by b(G), to be the smallest cardinality of a base. In some sense, the base size measures the complexity of the underlying symmetry encoded by G, and determining this number is a fundamental problem in permutation group theory, with important applications to graph theory and the computational study of finite groups.Our aim is to study bases for a wide variety of permutation groups, both finite and infinite. The simple primitive groups are the basic building blocks of all permutation groups, analogous to the prime numbers in number theory, and they are the focus of the proposed project. In recent years there have been great advances in our understanding of the subgroup structure, conjugacy classes and representation theory of simple groups, and combined with new computational and probabilistic methods, some remarkably strong bounds on the base sizes of almost simple primitive groups have been obtained. Perhaps most strikingly, the PI and several collaborators have recently proved that if G is such a group then either b(G) is at most 7, or G belongs to a short prescribed list of obvious exceptions. The proof utilises a variety of different tools from group theory, representation theory and probability, providing another example of the power of probabilistic methods in group theory to solve entirely deterministic problems.In fact, it seems likely that most of these groups are extremal in the sense that they admit a base of size two, and we propose to classify all such groups with this interesting property and establish related asymptotic results. This has an immediate application to the study of so-called extremely primitive groups, initiated recently by Mann, Praeger and Seress, and constitutes an important first step towards the ultimate aim of a classification of base-two primitive groups.More generally, if G is an arbitrary permutation group of degree n then it is easy to see that b(G) is bounded from below by log |G|/log n. In terms of upper bounds, an important open problem concerns a conjecture of Pyber, which asserts that the base size of a primitive group is rather restricted in the sense that there is an absolute constant c such that b(G) is at most c.log |G|/log n for any primitive group G of degree n. In the almost simple case, this has been established by Liebeck and Shalev, while some specific affine-type groups have been dealt with by various authors. We intend to prove Pyber's conjecture in its entirety, revealing a deep and profound property of primitive permutation groups.In a different direction, another key objective of the proposed research is to develop a theory of bases for infinite permutation groups, with an emphasis on linear algebraic groups defined over algebraically closed fields. Very little is presently known and there is an interesting interplay here between the base size of the algebraic group and that of the corresponding finite group obtained by taking the fixed points of a Frobenius morphism. In particular, results at the algebraic group level will be very useful for the above problems concerning finite simple groups.

As for any project in the area of Pure Mathematics, the main beneficiaries of the proposed research will be other mathematicians. However, groups arise naturally in the study of symmetry in a huge variety of mathematical and physical systems, and thus the objects of study have far-reaching applications across the sciences and beyond. For instance, permutation groups are used in chemistry to study molecules and crystal structures, where the base size of the group can be considered a measure of the complexity of the physical object's underlying symmetry. In addition, small bases play a critical role in the computational study of the symmetry groups which arise in this way, and our theoretical results on the base size and related asymptotics may well have implications for the design and implementation of the relevant underlying algorithms. Consequently, this would have a positive impact on the many hundreds of academic researchers around the world who use computer algebra systems such as MAGMA and GAP in their work, in addition to various non-academic endeavours in areas such as cryptography and the work of the British intelligence agency GCHQ. The base size also has a natural interpretation in the language of graph theory, where it is closely related to the notion of metric dimension. Results on the latter have found important applications in areas as diverse as network optimisation, robot navigation, sonar and the analysis of large data sets. The proposed project will advance our understanding of bases for simple groups, which are the basic building blocks of all groups, so it will have an impact on all these applications. One of the main features of this grant proposal is the funding of a post-doctoral researcher to work on the suggested problems. This will provide a unique opportunity for the PDRA to learn the novel theory and tools outlined in the Case for Support, and to work in collaboration with some of the leading experts in the field. Such an experience will be invaluable at this early stage of his or her career, and will help in establishing the PDRA as a member of the mathematical community, both in the UK and internationally. Reciprocally, the PDRA will have a positive impact on the Pure Mathematics Group within the School of Mathematics of the University of Southampton, enriching the group academically and contributing to the overall scientific environment. The group has an enviable track-record in hosting post-doctoral researchers and provides an excellent environment for the professional development of young mathematicians. The results of the proposed research will be published in academic journals of international standing. Prior to publication they will be made available on the PI's website, on the pre-print server of the University of Southampton and on open-access repositories such as the arxiv (www.arxiv.org). The PDRA, PI and named collaborators will also give seminars, lectures and colloquia at universities and conferences around the world on the topics related to this work.