#### Project Info

# Partition problems for geometric complexity theory, and the permanent vs. determinant problem.

#### Project Goals and Description:

*ombinatorial representation theory*, but there are practical formulas for computing coefficients only in very limited cases. Nevertheless, they are believed to have a particular combinatorial interpretation, meaning that their values describe the sizes of certain sets of explicitly describable objects. For a large class of Kronecker coefficients which are directly applicable to the broader goals of GCT, a so-called

*cancellative formula*exists (meaning the Kronecker coefficient is obtained as the subtraction of two positive quantities), but this formula is of limited use for describing the (approximate) behavior of Kronecker coefficients. This information is necessary for GCT, because the numerical behavior of Kronecker coefficients can serve as a “certificate of hardness” for certain algorithmic problems like evaluating

*matrix permanents*. Based on ideas that have proved successful in the simple cases, in this project we will work on eliminating the cancellation in the Kronecker coefficients formula, working towards a formula which is entirely

*positive*. The cancellation in the formula that we begin from is between two families of objects that are very concrete – namely paths in a rectangular box that begin at one corner and end at the opposite corner, and can only take specified steps that are “up” and “over.” Thus, despite the sophisticated theory that gives context to this problem, the actual business of obtaining a positive formula for our Kronecker coefficients involves just finding a way to identify one set of visualizable objects with a subset of another. We will be able to experiment with rules to make this identification using computer algebra tools such as Python/SageMath. Once we identify candidate rules for eliminating the cancellation in the starting formula, we can set to proving that our mappings are well-defined and provide new positive formulas Kronecker coefficients. As a parallel line of investigation, it will also be valuable to better understand what is known as the “determinantal complexity” of the matrix permanent. The matrix permanent is a polynomial based on the entries of a square matrix, and it is believed that the computational complexity of evaluating permanents is exponential. However, the determinantal complexity is not fully understood even for small order permanents. For instance, this complexity measure for permanents of order 4 is known to be at least 8 and most 15, but is not known precisely. Furthermore, it is not known how many determinants are needed in order to write the permanent polynomial as a

*sum*of determinants. This is a new line of inquiry which could possibly still have complexity theoretic consequences. This work will be of interest to the algebraic combinatorics, number theory, and theoretical computer science research fields. GCT has seen contributions by hundreds of researchers from diverse fields since its inception, and the aspects treated in this project involve concrete objects that are well-suited to an undergraduate research project.

#### More Information:

*Computers and intractability: A Guide to the Theory of NP-*

*completeness*. Grenet, B., 2011. “An upper bound for the permanent versus determinant problem.”

*Theory of Computing*. Hahn, H., Huh, J., Lim, E. and Sohn, J., 2018. “From partition identities to a combinatorial approach to explicit Satake inversion.”

*Annals of Combinatorics*,

*22*(3), pp.543-562. Pak, I. and Panova, G., 2014. “Unimodality via Kronecker products.”

*Journal of Algebraic Combinatorics*,

*40*(4), pp.1103-1120. Mignon, Thierry, and Nicolas Ressayre. "A quadratic bound for the determinant and permanent problem."

*International Mathematics Research Notices*2004.79 (2004): 4241-4253. Pak, I. and Panova, G., 2013. “Strict unimodality of q-binomial coefficients.”

*Comptes Rendus Mathematique*,

*351*(11-12), pp.415-418. Stanley, R.P., 2011.

*Enumerative Combinatorics Volume 1 (2nd edition).*Cambridge studies in advanced mathematics.

#### Primary Contacts:

#### Student Preparation

## Qualifications

## TIME COMMITMENT (HRS/WK)

## SKILLS/TECHNIQUES GAINED

## MENTORING PLAN

During semesters, we will have weekly meetings, allowing at least an hour to discuss progress, share ideas, and offer direction. I view undergraduate research projects as true collaborations, in which all participants work off each other’s strengths in order to make progress on a problem, so I work closely with students to determine which tasks and parts of the project are best suited to each one’s interests and abilities. I am also available outside of scheduled meeting times, either over e-mail or in additional office hours to help troubleshoot issues that come up in between meetings.

I model steps towards partial progress for students during meetings so that the time they spend working independently is well-used, with a clear understanding of what they should be attempting to do. In research, many attempts often end in failure, so I am sure to describe my own failed ideas and the insights they have sometimes brought.

I like to ensure that students have an opportunity to present their work in some extramural forum at the end of the project. I plan to support the student through this process, including offering coaching on abstract submission, poster/talk design, research conference etiquette etc. Should the opportunity arise where journal submission becomes a viable possibility, I would gladly offer guidance and help with this process as well.

My mentoring relationships often extend beyond the duration of direct contact, and I enjoy being available for students to consult as they progress through their careers. By understanding their goals and interests, I try to shape the research experience to something that they will find valuable for years to come.