On the product decomposition conjecture for finite simple groups

Within mathematics the study of symmetry is called "group theory". Given some kind of object (physical or mathematical), its "symmetry group" is the set of transformations of the object that preserve its structure. A very symmetrical object will have a large symmetry group, an asymmetrical object will have a tiny symmetry group.

The cube, for instance, has a symmetry group of size 48 - these are all the reflections and rotations of 3-dimensional space that leave the vertices of the cube unchanged set-wise.

Given such a group of symmetries we can consider the "composition" of two group elements and it is clear that such a composition will itself be a group element. For instance if I rotate the cube around one axis, and then again around another, the end result will be the same as if I had rotated the cube around a third axis.

This project studies groups of a particular type. Firstly, they are FINITE; secondly, they are SIMPLE. In this context, simple means that the group cannot be "broken up" into smaller pieces. It is important to note that simple does not mean easy! The study of the finite simple groups is an extraordinarily rich area of mathematics containing many very difficult open questions.

This research starts with the following set-up: Suppose that we have a finite simple group G and a subset A inside G with A of size at least 2.

It is well-known that any element of G can be written as a composition of some number N of elements "of the same type" as A. (Here "of the same type" has a technical meaning that we won't discuss. Roughly speaking though, if one looks at the cube example, one can see that a ROTATION has different qualities to a REFLECTION. The idea of "type" is a refinement of this qualitative distinction.)

We would like to write all of the elements of G in the most efficient way possible using elements of the same type as A. By efficient we mean using as few compositions as possible. The Product Decomposition Conjecture (PDC) asserts that elements of finite simple groups can be written very efficiently indeed.

APPLICATIONS: Although the setting for this research is very abstract, there are a surprising number of rather concrete applications. One of the original motivations for the PDC, for instance, was in the explicit construction of EXPANDER FAMILIES. These are mathematical models of efficient networks which have a myriad of applications in mathematics, computer science and elsewhere. It turns out that one can use notions of "efficiency" in finite simple groups to construct expander families.

METHODS: The primary tool at our disposal to prove PDC is the Classification of Finite Simple Groups (CFSG). This monumental theorem was proved by hundreds of mathematicians over a period of about 40 years, culminating in 2001. CFSG asserts that all finite simple groups are on an explicit (infinitely long) list. Thus to prove PDC it is enough to prove the result for all of the groups on the list. In fact some of the groups on the list have already been attended to in earlier collaborative work of the Principal Investigator and others.

It is expected that research into the PDC on the groups that remain will, in addition to yielding a proof of PDC, shed light on some of the deep and mysterious properties of the finite simple groups.

The proposed research is in the area of pure mathematics and so, like most research in this area, it is likely that the main impact in the short term will be within the academic community. It is hard to judge what the longer term impacts might be but, in order to maximise the chances of impact to other areas, the results of the research will be publicised as widely as possible.

Within the academic community, the initial impact will be greatest amongst researchers working in areas connected to the study of expansion; these include group theory, number theory and combinatorics. As stated in the case, the proposed research constitutes a dramatic generalization of many existing results and conjectures that already exist in the literature, many of which have been the subject of intense study themselves, as well as being applied in work further afield.

Complete success in achieving the research objectives would constitute a very significant development in all of the aforementioned areas. It would unify a host of earlier results thereby closing one chapter; equally it would open another as one would start to believe that a number of famous conjectures in several areas could lie in reach (we refer, for example, to the conjecture of Shalev mentioned in the Case for Support, with its implications for Thompson's conjecture).

Research in this topic has a long history of throwing up deep and sometimes unexpected connections between different areas of mathematics. We mention here earlier work of the PI on the Product Decomposition Conjecture which, in addition to proving a major case of the conjecture, also led to several dramatic generalizations of classical results in additive combinatorics. This despite the fact that the principle methods used were group theoretic.

Indeed the proposed research specifically includes a programme to connect two hitherto quite separate questions in group theory - the notion of base-size, a classically studied quantity on which dozens of papers have been written by many authors - with the modern study of width. Preliminary investigations by the PI suggest that the notion of base-size may be generalized and applied to the study of the Product Decomposition Conjecture, thereby connecting a host of established, even classical results with this burgeoning new area.

The proposed research has the advantage that it is perfectly possible to communicate many of the fundamental ideas to undergraduate students, and the area is a rich entry point for young mathematicians wishing to embark on a research career. We refer, for example to the celebrated monographs of Davidoff, Sarnak and Valette; as well as that of Linial and Wigderson. The PI will make sure that the proposed research is communicated in as accessible a way as possible, and will take every opportunity to introduce new audiences to this research area.

The UK is currently world leading in the study of growth and width questions - this project would further establish the UK's reputation in this area and strengthen links with other research groups in Europe.