# On the product decomposition conjecture for finite simple groups

Lead Research Organisation:
University of South Wales

Department Name: Faculty of Computing, Eng. and Science

### Abstract

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 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.

### Planned Impact

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.

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.

### Organisations

- University of South Wales, Rhondda (Lead Research Organisation)
- University of Bristol, United Kingdom (Collaboration)
- Open University, United Kingdom (Collaboration)
- University of Milano-Bicocca (Collaboration)
- Imperial College London (Collaboration)
- London Mathematical Society, United Kingdom (Collaboration)
- Moi University (Collaboration)
- University of Leicester, United Kingdom (Collaboration)
- University of Western Australia, Australia (Collaboration)

## People |
## ORCID iD |

Nick Gill (Principal Investigator) |

### Publications

Barrantes D
(2016)

*Abelian covers of alternating groups*in Archiv der Mathematik
Gill N
(2016)

*GENERATING GROUPS USING HYPERGRAPHS*in The Quarterly Journal of Mathematics
GILL N
(2016)

*QUASIRANDOM GROUP ACTIONS*in Forum of Mathematics, Sigma
N. Gill

*Conway's groupoid and its relatives*in American Mathematical Society Contemporary Mathematics Series
N. Gill

*Conway groupoids and completely transitive codes*in CombinatoricaDescription | This project is about the "growth of sets inside the finite simple groups". Groups are just sets equipped with a multiplication (satisfying certain axioms), and the notion of growth is defined in relation to this multiplication operation. We are interested in proving a major conjecture about growth (called PDC); parts of this conjecture are already proved for various special cases -- in fact, what remains is to study growth in four major families: the linear groups, the unitary groups, the symplectic groups and the orthogonal groups. In this research so far, I (along with collaborators) have: (a) stated and proved a "strong version" of PDC for certain families for which PDC was already known. This work was made public in January 2019. (b) proved two "weak versions" of PDC inside the linear groups -- the first pertains to small subsets only, while the second pertains to subgroups only. I expect to make this work in the coming months. Furthermore, my expectation is that these weak versions will extend to the remaining outstanding families -- this is ongoing work. The final gap between the weak version and the full version of PDC remains a vexatious open problem at this stage (c) sketched out some promising ideas relating to a probabilistic version of the PDC. We are currently pursuing this line of investigation. |

Exploitation Route | The results so far make significant progress towards proving a weak version of the Product Decomposition Conjecture. Even this weak version would be a significant advance in our understanding of the way sets grow inside the finite simple groups. I expect that the programme that this project is a part of will eventually result in a full proof of this weak version... although at this stage it is unclear how the final stage of that proof will be achieved. |

Sectors | Digital/Communication/Information Technologies (including Software),Education |

Description | London Mathematical Society Scheme 5 |

Amount | £1,200 (GBP) |

Organisation | London Mathematical Society |

Sector | Learned Society |

Country | United Kingdom |

Start | 04/2016 |

End | 04/2016 |

Description | PhD studentship |

Amount | £55,000 (GBP) |

Organisation | University of South Wales |

Sector | Academic/University |

Country | United Kingdom |

Start | 10/2016 |

End | 09/2019 |

Description | Research funding |

Amount | £10,000 (GBP) |

Organisation | London Mathematical Society |

Sector | Learned Society |

Country | United Kingdom |

Start | 10/2016 |

End | 09/2018 |

Description | Collaboration with Francis Hunt (South Wales), Martin Liebeck (Imperial), Pablo Spiga (Milano-Biccoca) |

Organisation | Imperial College London |

Country | United Kingdom |

Sector | Academic/University |

PI Contribution | This is a collaborative research partnership between individuals at three institutions. |

Collaborator Contribution | All individuals are experts in group theory, and we have joined forces to write several papers together. |

Impact | One preprint has been produced -- see the link. Two more are in preparation, and a fourth is planned. |

Start Year | 2016 |

Description | Collaboration with Francis Hunt (South Wales), Martin Liebeck (Imperial), Pablo Spiga (Milano-Biccoca) |

Organisation | University of Milano-Bicocca |

Country | Italy |

Sector | Academic/University |

PI Contribution | This is a collaborative research partnership between individuals at three institutions. |

Collaborator Contribution | All individuals are experts in group theory, and we have joined forces to write several papers together. |

Impact | One preprint has been produced -- see the link. Two more are in preparation, and a fourth is planned. |

Start Year | 2016 |

Description | Collaboration with Neil Gillespie (Bristol), Jason Semeraro (Leicester), Cheryl Praeger (Western Australia) |

Organisation | University of Bristol |

Department | School of Biochemistry Bristol |

Country | United Kingdom |

Sector | Academic/University |

PI Contribution | We are all experts in group theory, and have combined forces to write several papers together. |

Collaborator Contribution | As above |

Impact | One article has appeared, two more have been accepted, one is in the refereeing process. A fifth preprint is in preparation. |

Start Year | 2015 |

Description | Collaboration with Neil Gillespie (Bristol), Jason Semeraro (Leicester), Cheryl Praeger (Western Australia) |

Organisation | University of Leicester |

Department | Department of Geography |

Country | United Kingdom |

Sector | Academic/University |

PI Contribution | We are all experts in group theory, and have combined forces to write several papers together. |

Collaborator Contribution | As above |

Impact | One article has appeared, two more have been accepted, one is in the refereeing process. A fifth preprint is in preparation. |

Start Year | 2015 |

Description | Collaboration with Neil Gillespie (Bristol), Jason Semeraro (Leicester), Cheryl Praeger (Western Australia) |

Organisation | University of Western Australia |

Department | School of Molecular Sciences |

Country | Australia |

Sector | Academic/University |

PI Contribution | We are all experts in group theory, and have combined forces to write several papers together. |

Collaborator Contribution | As above |

Impact | One article has appeared, two more have been accepted, one is in the refereeing process. A fifth preprint is in preparation. |

Start Year | 2015 |

Description | Collaboration with mathematicians at Moi University, Kenya |

Organisation | London Mathematical Society |

Country | United Kingdom |

Sector | Learned Society |

PI Contribution | Ian Short of the Open university and I have a grant via the LMS' "Mentoring African Research Mathematicians" that connects us with Moi University. We have been assigned a masters student, and two PhD students -- supervising these students is our primary role. I will visit Kenya in April 2017 to give an advanced course in algebra to graduate students. The stated aim is to produce material research outcomes. |

Collaborator Contribution | The LMS have provided £10000. Moi University have provided personnel. |

Impact | No outputs yet -- the partnership started in October 2017 |

Start Year | 2016 |

Description | Collaboration with mathematicians at Moi University, Kenya |

Organisation | Moi University |

Country | Kenya |

Sector | Academic/University |

PI Contribution | Ian Short of the Open university and I have a grant via the LMS' "Mentoring African Research Mathematicians" that connects us with Moi University. We have been assigned a masters student, and two PhD students -- supervising these students is our primary role. I will visit Kenya in April 2017 to give an advanced course in algebra to graduate students. The stated aim is to produce material research outcomes. |

Collaborator Contribution | The LMS have provided £10000. Moi University have provided personnel. |

Impact | No outputs yet -- the partnership started in October 2017 |

Start Year | 2016 |

Description | PhD student via the Open University |

Organisation | Open University |

Country | United Kingdom |

Sector | Academic/University |

PI Contribution | I am supervising a PhD student, Margaret Stanier, at the Open University. |

Collaborator Contribution | Ian Short and Jozef Siran of the OU are also supervising this student. |

Impact | Outcomes pending. |

Start Year | 2016 |

Description | Advanced course on growth in groups at the University of Costa Rica |

Form Of Engagement Activity | Participation in an activity, workshop or similar |

Part Of Official Scheme? | No |

Geographic Reach | International |

Primary Audience | Postgraduate students |

Results and Impact | I gave a short advanced course on groups at the University of Costa Rica. The course was in Spanish and notes are available online. One important outcome is that I am informally supervising a Costa Rican student in research that we hope will lead to a PhD -- he has yet to complete the registration process for this, but the research is underway. |

Year(s) Of Engagement Activity | 2016 |

URL | https://boolesrings.org/nickgill/2016/07/19/crecimiento-en-grupos-y-otras-estructuras/ |

Description | Contributed talk to International Conference on Algebraic Combinatorics and Group Actions |

Form Of Engagement Activity | A talk or presentation |

Part Of Official Scheme? | No |

Geographic Reach | International |

Primary Audience | Professional Practitioners |

Results and Impact | Contributed talk at an international conference, Herstmonceux Castle, UK |

Year(s) Of Engagement Activity | 2016 |

URL | http://www.commalg.org/2015/11/algebraic-combinatorics-and-group-actions-herstmonceux-uk/ |

Description | Course in Galois Theory in Nepal |

Form Of Engagement Activity | Participation in an activity, workshop or similar |

Part Of Official Scheme? | No |

Geographic Reach | International |

Primary Audience | Postgraduate students |

Results and Impact | I participated in a 2 month programme to teach a Masters course in Galois Theory as part of a push to develop expertise in algebra amongst Nepali mathematicians. I taught a 2 week module as part of this programme. |

Year(s) Of Engagement Activity | 2016 |

URL | http://www.rnta.eu/nap/ |

Description | Invited speaker at the Open University Winter Combinatorics Meeting |

Form Of Engagement Activity | A talk or presentation |

Part Of Official Scheme? | No |

Geographic Reach | National |

Primary Audience | Professional Practitioners |

Results and Impact | Invited talk at an annual combinatorics meeting |

Year(s) Of Engagement Activity | 2016 |

URL | http://wcm.open.ac.uk/ |

Description | Seminar at the Welsh Institute of Mathematics Annual Conference in Gregynog |

Form Of Engagement Activity | A talk or presentation |

Part Of Official Scheme? | No |

Geographic Reach | Regional |

Primary Audience | Professional Practitioners |

Results and Impact | I gave a seminar at the annual gather of Welsh mathematics departments. |

Year(s) Of Engagement Activity | 2016 |

URL | http://www.wimcs.ac.uk/gregynog.html |

Description | Summer school on group theory in Leon, Nicaragua |

Form Of Engagement Activity | Participation in an activity, workshop or similar |

Part Of Official Scheme? | No |

Geographic Reach | International |

Primary Audience | Postgraduate students |

Results and Impact | I gave a short course in Spanish on group theory. This was associated with the event in Costa Rica which I have reported on elsewhere, but the level of this course was rather different due to the weaker background of the students. |

Year(s) Of Engagement Activity | 2016 |

URL | https://boolesrings.org/nickgill/2016/07/19/crecimiento-en-grupos-y-otras-estructuras/ |