The partition algebra: a new approach to the symmetric group and applications to P vs NP.

Lead Research Organisation: City University London
Department Name: Sch of Engineering and Mathematical Sci

Abstract

The Kronecker problem is a classical problem in Mathematics, which has been open for over a hundred years. It asks for a description of some coefficients, called the Kronecker coefficients, appearing in the representation theory of the symmetric group. More recently, this problem has been shown to play a key role in Geometric Complexity theory, an approach that seeks to settle the famous P vs NP problem.

We have recently proposed a completely new approach to the Kronecker problem using the duality between the symmetric group and the partition algebra. Early results suggest that this may well lead to a complete solution. This proposal aims at developing this tool further (and extending it to positive characteristics) to give a systematic study of the ordinary and modular representation theory of the symmetric group.

In parallel, we plan to liaise with the Computer Science community to investigate the implications of our work to the celebrated P vs NP problem.

Planned Impact

The central idea in this project is to use an algebraic structure coming from Mathematical Physics, to tackle the classical Kronecker problem in Pure Mathematics.

The main impact, outside of the academic community, comes from the deep connections between the Kronecker problem and the famous P vs NP problem. The P vs NP problem is one of the 7 Millenium prize problems set up be the Clay Mathematical Institute in Cambridge Massachussets
in 2000 and considered to be the most important open problems in
Mathematics (only one of them has been solved to date).
It is the central question in an area of theoretical computer
science called Computational Complexity, which focusses on quantifying the efficiency
of algorithms to solve computational problems. It is well-known that a solution to the P vs NP problem would have enormous impact on our society, from cryptography to many aspects of logistics.

Publications

10 25 50

publication icon
BOWMAN C (2017) DIAGRAM ALGEBRAS, DOMINANCE TRIANGULARITY AND SKEW CELL MODULES in Journal of the Australian Mathematical Society

publication icon
Bowman C (2014) The partition algebra and the Kronecker coefficients in Transactions of the American Mathematical Society

publication icon
Bowman C (2014) Decomposition numbers for Brauer algebras of type in characteristic zero in Journal of Pure and Applied Algebra

publication icon
Bowman C (2016) A Family of Graded Decomposition Numbers for Diagrammatic Cherednik Algebras in International Mathematics Research Notices

publication icon
Bowman C (2019) Simple Modules for the Partition Algebra and Monotone Convergence of Kronecker Coefficients in International Mathematics Research Notices

publication icon
Bowman C (2015) The Blocks of the Partition Algebra in Positive Characteristic in Algebras and Representation Theory

publication icon
De Visscher M (2016) On Brauer algebra simple modules over the complex field in Transactions of the American Mathematical Society

publication icon
Goodman F (2020) The Cellular Second Fundamental Theorem of Invariant Theory for Classical Groups in International Mathematics Research Notices

 
Description The main idea of this project was to use a new tool coming from Mathematical Physics, called the partition algebra, to study a classical problem in Mathematics, namely the Kronecker problem. The first step was to construct explicit bases for the simple modules of the partition algebra. This has now been completed.
The second step was to use this construction to find positive combinatorial formulas for the Kronecker coefficients. We have found such a formula for a large new class of Kronecker coefficients. The multiplicity free Kronecker coefficients have also been completed classified.
In parallel, the project aimed at developing a systematic study of the modular representation theory of the symmetric groups using the partition algebra. To that end, we have already developed the modular representation theory of the partition algebra and will now explore its implication on the symmetric group.

As our work on this project progressed, we realised that similar methods could be used to study some other related algebras and have obtained new results for the diagrammatic Cherednik algebras and Brauer algebras.
Exploitation Route Our new approach to the partition algebra has already generated a lot of interest from the Representation theory and Algebraic Combinatorics communities studying the Kronecker problem. All our work is available on the ArXiv and we have spoken at numerous national and international conferences.

We also organised a conference on Kronecker coefficients in September 2016 to bring together the various academic communities studying the Kronecker problem, including the Theoretical Computer Science community.
Sectors Education,Security and Diplomacy

URL https://arxiv.org/pdf/1710.04523v2.pdf
 
Description London Mathematical Society small grant
Amount £2,500 (GBP)
Funding ID 11502 
Organisation London Mathematical Society 
Sector Academic/University
Country United Kingdom
Start 09/2016 
End 09/2016
 
Description Christine Bessenrodt 
Organisation Gottfried Wilhelm Leibniz Universität Hannover
Department Faculty of Mathematics and Physics
Country Germany 
Sector Academic/University 
PI Contribution expertise in Combinatorial representation theory
Collaborator Contribution expertise in representation theory of symmetric group
Impact • C. Bessenrodt; C. Bowman, Multiplicity-free Kronecker products of characters for the symmetric groups, arXiv:1609.03596. (preprint)
Start Year 2016
 
Description Fred Goodman 
Organisation University of Iowa
Department Carver College of Medicine
Country United States 
Sector Academic/University 
PI Contribution expertise in representation of diagram algebras
Collaborator Contribution expertise in developing abstract frameworks to study cellular algebras
Impact Christopher Bowman, John Enyang, and F.M. Goodman, Diagram algebras, dominance triangularity, and skew cell modules, preprint (2016), arXiv:1610.09010 (preprint) Christopher Bowman, John Enyang, and F.M. Goodman, The cellular second fundamental theorem of invariant theory for classical groups, preprint (2016), arXiv:1610.09009 (preprint)
Start Year 2015
 
Description AMS-EMS international conference, Porto. 
Form Of Engagement Activity A talk or presentation
Part Of Official Scheme? No
Geographic Reach International
Primary Audience Other audiences
Results and Impact research presentation to general and specialised audience.
Year(s) Of Engagement Activity 2015
 
Description Algebra seminar, University of Warwick 
Form Of Engagement Activity A talk or presentation
Part Of Official Scheme? No
Geographic Reach National
Primary Audience Other audiences
Results and Impact presentation of research results prompting discussions with other algebraists in the field.
Year(s) Of Engagement Activity 2015
 
Description Algebraic Combinatorics in Representation theory Conference (Luminy) 
Form Of Engagement Activity A talk or presentation
Part Of Official Scheme? No
Geographic Reach International
Primary Audience Postgraduate students
Results and Impact share our recent work on Kronecker coefficents
Year(s) Of Engagement Activity 2016
 
Description American Institute of Mathematics workshop: Combinatorics and complexity of Kronecker coefficient, Palo Alto, USA 
Form Of Engagement Activity A talk or presentation
Part Of Official Scheme? No
Geographic Reach International
Primary Audience Professional Practitioners
Results and Impact presentations of our results and very fruitful discussions with experts in the field, initiated discussions about our conference at City University London in Sept 2016.
Year(s) Of Engagement Activity 2014
 
Description Conference on Algebraic Lie theory and representation theory, International Centre for Mathematical Science, Edinburgh 
Form Of Engagement Activity Participation in an activity, workshop or similar
Part Of Official Scheme? No
Geographic Reach International
Primary Audience Professional Practitioners
Results and Impact workshop for postgraduate and postdoctoral students followed by research presentations.
Year(s) Of Engagement Activity 2014
 
Description Conference on Representation theory and Physics (University of Leeds) 
Form Of Engagement Activity A talk or presentation
Part Of Official Scheme? No
Geographic Reach International
Primary Audience Other audiences
Results and Impact share our recent results on this project
Year(s) Of Engagement Activity 2016
 
Description Conference on Representation theory of Algebraic groups (York) 
Form Of Engagement Activity A talk or presentation
Part Of Official Scheme? No
Geographic Reach International
Primary Audience Other audiences
Results and Impact share our recent progress on this project
Year(s) Of Engagement Activity 2016
 
Description Journees du GDR (Clermont-Ferrand) 
Form Of Engagement Activity A talk or presentation
Part Of Official Scheme? No
Geographic Reach International
Primary Audience Professional Practitioners
Results and Impact presentation of our latest results on Kronecker coefficients
Year(s) Of Engagement Activity 2017
 
Description Kronecker coefficiant conference 2016 
Form Of Engagement Activity Participation in an activity, workshop or similar
Part Of Official Scheme? No
Geographic Reach International
Primary Audience Other audiences
Results and Impact Bring together the various academic communities interested in the Kronecker problem, namely the representation theory community, the algebraic combinatorics community, the computational complexity community and the quantum information theory community.
Year(s) Of Engagement Activity 2016
 
Description Pure Mathematics Seminar, University of Kent 
Form Of Engagement Activity A talk or presentation
Part Of Official Scheme? No
Geographic Reach National
Primary Audience Other audiences
Results and Impact research presented to a group of academics and young researches, prompting discussions about future collaborations.
Year(s) Of Engagement Activity 2014
 
Description Representation theory in Samos 
Form Of Engagement Activity A talk or presentation
Part Of Official Scheme? No
Geographic Reach International
Primary Audience Other audiences
Results and Impact share our recent progress on this project
Year(s) Of Engagement Activity 2016
 
Description Representations of symmetric groups (Kaiserslautern) 
Form Of Engagement Activity A talk or presentation
Part Of Official Scheme? No
Geographic Reach International
Primary Audience Postgraduate students
Results and Impact share our recent progress on this research project
Year(s) Of Engagement Activity 2016
 
Description Seminaire Chevalley, Paris 
Form Of Engagement Activity A talk or presentation
Part Of Official Scheme? No
Geographic Reach International
Primary Audience Other audiences
Results and Impact recent results presented to a group of academics, young researchers and postgraduate students, prompting discussions afterwards.
Year(s) Of Engagement Activity 2014
 
Description Seminar in Cologne 
Form Of Engagement Activity A talk or presentation
Part Of Official Scheme? No
Geographic Reach International
Primary Audience Other audiences
Results and Impact share our recent progress on this project
Year(s) Of Engagement Activity 2016
 
Description Seminar in Hannover 
Form Of Engagement Activity A talk or presentation
Part Of Official Scheme? No
Geographic Reach International
Primary Audience Other audiences
Results and Impact share our recent progress on this project
Year(s) Of Engagement Activity 2016
 
Description Seminar in Kaiserslautern 
Form Of Engagement Activity A talk or presentation
Part Of Official Scheme? No
Geographic Reach International
Primary Audience Other audiences
Results and Impact share our recent progress on this project
Year(s) Of Engagement Activity 2015
 
Description Seminar in Paris 
Form Of Engagement Activity A talk or presentation
Part Of Official Scheme? No
Geographic Reach International
Primary Audience Other audiences
Results and Impact share our recent progress on this project
Year(s) Of Engagement Activity 2016
 
Description Seminar, Universita degli studi di Padova, Italy 
Form Of Engagement Activity A talk or presentation
Part Of Official Scheme? No
Geographic Reach International
Primary Audience Professional Practitioners
Results and Impact Research presentation of our most recent results which sparked questions and discussion with colleagues, postdocs and postgraduate students.
Year(s) Of Engagement Activity 2015
 
Description Seminar, University of Kaiserslautern, Germany 
Form Of Engagement Activity A talk or presentation
Part Of Official Scheme? No
Geographic Reach International
Primary Audience Professional Practitioners
Results and Impact research presentation of our results to a group of experts in the field, prompting discussions.
Year(s) Of Engagement Activity 2015