The partition algebra: a new approach to the symmetric group and applications to P vs NP.
Lead Research Organisation:
City, University of 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.
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.
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
Bessenrodt C
(2017)
Multiplicity-free Kronecker products of characters of the symmetric groups
in Advances in Mathematics
Enyang J
(2016)
Cellular Bases for Algebras with a Jones Basic Construction
in Algebras and Representation Theory
Bowman C
(2015)
The Blocks of the Partition Algebra in Positive Characteristic
in Algebras and Representation Theory
Briggs B
(2023)
On the Lie algebra structure of integrable derivations
in Bulletin of the London Mathematical Society
Goodman F
(2020)
The Cellular Second Fundamental Theorem of Invariant Theory for Classical Groups
in International Mathematics Research Notices
Bowman C
(2016)
A Family of Graded Decomposition Numbers for Diagrammatic Cherednik Algebras
in International Mathematics Research Notices
Bowman C
(2019)
Simple Modules for the Partition Algebra and Monotone Convergence of Kronecker Coefficients
in International Mathematics Research Notices
Bowman C
(2021)
The co-Pieri rule for stable Kronecker coefficients
in Journal of Combinatorial Theory, Series A
Bowman C
(2014)
Decomposition numbers for Brauer algebras of type in characteristic zero
in Journal of Pure and Applied Algebra
BOWMAN C
(2017)
DIAGRAM ALGEBRAS, DOMINANCE TRIANGULARITY AND SKEW CELL MODULES
in Journal of the Australian Mathematical Society
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 |
Description | London Mathematical Society small grant |
Amount | £2,500 (GBP) |
Funding ID | 11502 |
Organisation | London Mathematical Society |
Sector | Academic/University |
Country | United Kingdom |
Start | 08/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 |