# Complexity and asymptotics of structure constants

Greta Panova  “Thinking out of the black box”

###### Abstract.

Kostka, Littlewood-Richardson, Kronecker, and plethysm coefficients are
fundamental quantities in algebraic combinatorics, yet many natural questions
about them stay unanswered for more than 80 years. Kronecker and plethysm
coefficients lack “nice formulas”, a notion that can be formalized using
computational complexity theory. Beyond formulas and combinatorial
interpretations, we can attempt to understand their asymptotic behavior in
various regimes, and inequalities they could satisfy. Understanding these
quantities has applications beyond combinatorics. On the one hand, the
asymptotics of structure constants is closely related to understanding the
[limit] behavior of vertex and tiling models in statistical mechanics. More
recently, these structure constants have been involved in establishing
computational complexity lower bounds and separation of complexity classes
like VP vs VNP, the algebraic analogs of P vs NP in arithmetic complexity
theory. Here we discuss the outstanding problems related to asymptotics,
positivity, and complexity of structure constants focusing mostly on the
Kronecker coefficients of the symmetric group and, less so, on the plethysm
coefficients.

This expository paper is based on the talk presented at the Open Problems in
Algebraic Combinatorics coneference in May 2022.

Department of Mathematics, University of Southern California,
https://sites.google.com/usc.edu/gpanova/
To appear in _Proceedings of the Open Problems in Algebraic Combinatorics_
conference, May 2022. https://www.samuelfhopkins.com/OPAC/opac.html

##  1\. Introduction

Algebraic Combinatorics studies symmetries via their manifestations in
discrete objects, connecting with areas like Representation Theory,
Statistical Mechanics, Computational Complexity Theory, and Algebraic
Geometry. Many of its problems arise from the need for a quantitative and
explicit understanding of algebraic phenomena like group representations and
decompositions into irreducible representations, dimension formulae for
modules, intersection numbers in geometry, etc.

In its origin lies the representation theory of the symmetric group $S_{n}$
and general linear group $GL_{N}$. Their irreducible modules are indexed by
integer partitions, and their bases can be described via standard and semi-
standard Young tableaux (SYTs and SSYTs). As a next step, it is natural to
understand how tensor products of irreducible representations decompose into
irreducible components. In the case of $GL_{N}$ the multiplicities of isotypic
components are the Littlewood-Richardson (LR) coefficients. For $S_{n}$ the
multiplicities are the Kronecker coefficients. The composition of irreducible
$GL$ modules decomposes into irreducibles with multiplicities given by the
plethysm coefficients.

While no compact formula for the LR coefficients exists, they can be
understood via their combinatorial interpretation, the LR rule, which gives
them in the form of certain skew SSYTs. The LR rule was formulated in 1934,
but it took 40 years to prove formally. Inspired by the LR coefficients,
Murnaghan defined the Kronecker coefficients in 1938 and observed that
computing them is a highly nontrivial task. In late 70s and 80s the research
turned towards obtaining positive formulas. In 2000 Stanley stated as a major
open problem in Algebraic Combinatorics the problem of finding a nonnegative
combinatorial interpretation for the Kronecker coefficients, as well as the
plethysm coefficients. However, the progress has been minimal.

Besides presenting fundamental natural questions needing answers, the
Kronecker and plethysm coefficients also play an important role in algebraic
complexity theory, specifically Geometric Complexity Theory (GCT). Algebraic
complexity theory studies the complexity of computing formal polynomials using
arithmetic circuits, and some of its main problems concern the separation of
complexity classes ${{\rm{\textsf{VP}}}}\neq{{\rm{\textsf{VNP}}}}$, the
algebraic analog of the ${{\rm{\textsf{P}}}}\neq{{\rm{\textsf{NP}}}}$
Millennium problem. GCT approaches these problems by studying the symmetries
and geometric properties of the universal polynomials (usually determinant and
permanent), passing onto the coordinate rings of $GL$ orbit closures of these
polynomials. Complexity lower bounds and separation of classes then reduces to
understanding the $GL$-irreducible representations of these rings and
comparing their multiplicities. Such multiplicities are closely related to LR,
Kronecker, and plethysm coefficients, and separating complexity classes can be
achieved by proving certain inequalities for such multiplicities.

Another application of Algebraic Combinatorics is in Statistical Mechanics,
Asymptotic Representation Theory and Random Matrix Theory. Some of the early
connections date to the remarkable story of the longest increasing subsequence
of permutations, which has the same [Tracy-Widom] distribution as the maximal
eigenvalue of a random Hermitian matrix and the height of an SYT from the
Plancherel measure. Symmetric polynomials, and particularly Schur functions,
appear extensively in the study of random lozenge tilings, exclusion processes
and vertex models. Plane partitions themselves are lozenge tilings with
certain boundaries. Conversely, probabilistic and asymptotic methods have been
used to understand algebro-combinatorial quantities. In the lack of compact
formulas and combinatorial interpretations, understanding the growth behavior
of structure constants is a natural next step. Beyond the interaction with
Statistical Mechanics, understanding their growth is closely related to their
application in GCT mentioned above.

### Paper structure

Here we will briefly define the relevant structure constants, give some
background, and phrase the open problems of three separate aspects:
positivity, complexity, asymptotics. For more background on Complexity Theory
and its specific connections with Algebraic Combinatorics we refer to the
companion paper [Pan23] and references therein.

This paper presents the professional view of the author and is centered around
problems on which she has worked on. It has no aspirations to be a
comprehensive survey on the topics.

### Acknowledgements

The author is grateful to her collaborators throughout the years and in
particular Christian Ikenmeyer and Igor Pak for the extensive work on the
subject of this paper. We would like to dedicate this to the memory of
Christine Bessenrodt, whose deep and insightful work in the area has led a lot
of the progress and with whom the author had the honor to collaborate briefly
in 2020. We are grateful to the organizers of “Open Problems in Algebraic
Combinatorics” for the inspiring conference and the opportunity to present
these problems.

The author has been partially supported by the NSF.

##  2\. Basic objects and notions

We will assume the reader is familiar with basic notions in Algebraic
Combinatorics like integer partitions, Young tableaux and symmetric functions.
For a concise recap of those see [Pan23]. For details on the combinatorial
sides see [Sta99, Mac95] and for the representation theoretic aspects see
[Sag01, Ful97].

###  2.1. Partitions and Young tableaux

We use standard notation from [Mac95] and [Sta99, $\S$7] throughout the paper.

Let $\lambda=(\lambda_{1},\lambda_{2},\ldots,\lambda_{\ell})$ be a _partition_
of size $n:=|\lambda|=\lambda_{1}+\lambda_{2}+\ldots+\lambda_{\ell}$, where
$\lambda_{1}\geq\lambda_{2}\geq\ldots\geq\lambda_{\ell}\geq 1$. We write
$\lambda\vdash n$ for this partition, and $\mathcal{P}=\\{\lambda\\}$ for the
set of all partitions. The length of $\lambda$ is denoted
$\ell(\lambda):=\ell$. Denote by $p(n)$ the number of partitions
$\lambda\vdash n$. Let $\lambda+\mu$ denote the partition
$(\lambda_{1}+\mu_{1},\lambda_{2}+\mu_{2},\ldots)$

Special partitions include the _rectangular shape_ $(a^{b})=(a,\ldots,a)$, $b$
times, the _hooks shape_ $(k,1^{n-k})$, the _two-row shape_ $(n-k,k)$, and the
_staircase shape_ $\rho_{\ell}=(\ell,\ell-1,\ldots,1)$.

boxsize=2ex

A _Young diagram_ of _shape_ $\lambda$ is an arrangement of squares
$(i,j)\subset\mathbb{N}^{2}$ with $1\leq i\leq\ell(\lambda)$ and $1\leq
j\leq\lambda_{i}$. Let $\lambda\vdash n$. A _semistandard Young tableau_ $T$
of _shape_ $\lambda$ and _weight_ $\alpha$ is an arrangement of $\alpha_{k}$
many integers $k$ in squares of $\lambda$, which weakly increase along rows
and strictly increase down columns, i.e. $T(i,j)\leq T(i,j+1)$ and $T(i,j)\leq
T(i+1,j)$. For example, centertableaux 11244,2235,45 is an SSYT of shape
$\lambda=(5,4,2)$ and type $\alpha=(2,3,1,3,2)$. Denote by ${\text{\rm
SSYT}}(\lambda,\alpha)$ the set of such tableaux, and
$K(\lambda,\alpha)=\bigl{|}{\text{\rm SSYT}}(\lambda,\alpha)\bigr{|}$ the
_Kostka number_. A _standard Young tableau_ (SYT) of shape $\lambda$ is an
SSYT of type $(1^{n})$, and we have $f^{\lambda}:=K_{\lambda,1^{n}}$, which
can be computed by the hook-length formula (HLF) of [FRT54].

###  2.2. Representations of $S_{n}$ and $GL_{N}$

The irreducible representations of the _symmetric group_ $S_{n}$ are the
_Specht modules_ $\mathbb{S}_{\lambda}$ and are indexed by partitions
$\lambda\vdash n$. A basis for $\mathbb{S}_{\lambda}$ can be indexed by the
SYTs. In particular

$\dim\mathbb{S}_{\lambda}=f^{\lambda}.$

We have that $\mathbb{S}_{(n)}$ is the trivial representation assigning to
every $w$ the value $1$ and $\mathbb{S}_{1^{n}}$ is the sign representation.

The _character $\chi^{\lambda}(w)$_ of $\mathbb{S}_{\lambda}$ can be computed
via the _Murnaghan-Nakayama_ rule. Let $w$ have type $\alpha$, i.e. it
decomposes into cycles of lengths $\alpha_{1},\alpha_{2},\ldots,\alpha_{k}$.
Then

$\chi^{\lambda}(w)=\chi^{\lambda}(\alpha)=\sum_{T\in
MN(\lambda;\alpha)}(-1)^{ht(T)},$

where $MN$ is the set of rim-hook tableaux of shape $\lambda$ and type
$\alpha$, so that the entries are weakly increasing along rows and down
columns, and all entries equal to $i$ form a rim-hook shape (i.e. connected,
no $2\times 2$ boxes) of length $\alpha_{i}$. The height of each rim-hook is
one less than the number of rows it spans, and $ht(T)$ is the sum of all these
heights. For examples

$\ytableaushort{112333,12234,22334}$

is a Murnaghan-Nakayama tableau of shape $(6,5,5)$, type $(3,5,6,2)$ and has
height $ht(T)=1+2+2+1=6$.

The irreducible polynomial representations of $GL_{N}(\mathbb{C})$ are the
_Weyl modules_ $V_{\lambda}$ and are indexed by all partitions with
$\ell(\lambda)\leq N$. Their characters are exactly the Schur functions
$s_{\lambda}(x_{1},\ldots,x_{N})$, where $x_{1},\ldots,x_{N}$ are the
eigenvalues of $g\in GL_{N}(\mathbb{C})$.

###  2.3. Symmetric functions

Let $\Lambda[{\textbf{{x}}}]$ be the ring of _symmetric functions_
$f(x_{1},x_{2},\ldots)$, where the symmetry means that
$f({\textbf{{x}}})=f({\textbf{{x}}}_{\sigma})$ for any permutation $\sigma$ of
the variables, and $f$ is a formal power series. The ring $\Lambda_{n}$ of
homogeneous symmetric functions of degree $n$ has several important bases: the
_homogenous symmetric functions_ $h_{\lambda}$ , _elementary symmetric
functions_ $e_{\lambda}$, _monomial symmetric functions_ $m_{\lambda}$ ,
_power sum symmetric functions_ $p_{\lambda}$ and _Schur functions_
$s_{\lambda}$. The Schur functions can be defined as the generating functions
for SSYTs of shape $\lambda$

$s_{\lambda}=\sum_{\mu\vdash n}K_{\lambda\mu}m_{\mu},$

but also using _Weyl’s determinantal_ formula

$s_{\lambda}(x_{1},\ldots,x_{\ell})=\frac{\mathrm{det}[x_{i}^{\lambda_{j}+\ell-j}]_{i,j=1}^{\ell}}{\prod_{i<j}(x_{i}-x_{j})}$

and the _Jacobi-Trudi_ identity

$s_{\lambda}=\mathrm{det}[h_{\lambda_{i}-i+j}]_{i,j=1}^{\ell(\lambda)}.$

The _Cauchy identity_

$\sum_{\lambda}s_{\lambda}(\mathbf{x})s_{\lambda}(\mathbf{y})=\prod_{i,j}\frac{1}{1-x_{i}y_{j}}$

has a remarkable combinatorial proof given by the RSK correspondence between
pairs of same shape SSYTs and matrices with nonnegative integer entries.

###  2.4. Computational Complexity

We refer to [Aar16, Wig19, BCS97] for details on Computational Complexity
classes, and to [Pak22+, Pan23] and references therein for the connections
with Algebraic Combinatorics.

A _decision problem_ is a computational problem, for which the output is Yes
or No. There are two major complexity classes P and NP, subject of the P vs NP
Millennium problem. P is the class of decision problems, where given any input
of size $n$ (number of bits required to encode it), such that the answer can
be obtained in _polynomial time_ denoted by $poly(n)$, i.e. there is a fixed
$k$ and an algorithm taking $O(n^{k})$ many steps (elementary operations). NP
is the class of decision problems, where if the answer is Yes, then it can be
verified in polynomial time, i.e. there is a poly-time computable witness.
Naturally, ${{\rm{\textsf{P}}}}\subset{{\rm{\textsf{NP}}}}$ and it is widely
believed that ${{\rm{\textsf{P}}}}\neq{{\rm{\textsf{NP}}}}$. The classes FP
and #P are the counting analogues of P and NP. A _counting problem_ is in #P
if it is the number of accepting paths of an NP Turing machine. In practice,
these are counting problems where the answers are exponentially large sums of
$0$-$1$ valued functions $M$, each of which can be computed in $O(n^{k})$ time
for a fixed $k$:

$\sum_{b\in\\{0,1\\}^{m}}M(b),$

where $m=poly(n)$. We set the classes
${{\rm{\textsf{GapP}}}}=\\{f-g|\,f,g\in{{\rm{\textsf{\\#P}}}}\\}$ and
${{\rm{\textsf{GapP}}}}_{\geq 0}=\\{f-g|\,f,g\in{{\rm{\textsf{\\#P}}}}\text{
and }f-g\geq 0\\}$.

The algebraic complexity classes VP and VNP were introduced by Valiant [V79a],
as the algebraic analogues of P and NP (we refer to [Bür00a] for formal
definitions and properties). They concern the computation of polynomials
$f\in\mathbb{F}[x_{1},\ldots,x_{N}]$ of degree $poly(N)$ using arithmetic
circuits where the inputs are constants of arbitrary size from the field
$\mathbb{F}$ and the formal variables $x_{1},\ldots,x_{n}$, the gates are
$+,\times$, and the output is $f$. Then VP is the class of polynomials for
which there is a fixed $k$ and a circuit of size $O(n^{k})$ computing the
polynomial $f$. VNP is the class of polynomials $f$, such that there exist a
$k$ and $m=O(N^{k})$ and a polynomial $g\in{{\rm{\textsf{VP}}}}$ in $N+m$
variables, such that

$f(x_{1},\ldots,x_{N})=\sum_{b\in\\{0,1\\}^{m}}g(x_{1},\ldots,x_{N},b_{1},\ldots,b_{m}).$

The main conjecture is that ${{\rm{\textsf{VP}}}}\neq{{\rm{\textsf{VNP}}}}$
and is closely related to ${{\rm{\textsf{P}}}}\neq{{\rm{\textsf{NP}}}}$, see
e.g. [Bür00b]. As Valiant showed, for every polynomial
$f\in\mathbb{C}[x_{1},\ldots,x_{n}]$ there exists a $K$ and a $K\times K$
matrix $A:=A_{0}+\sum_{i=1}^{N}A_{i}x_{i}$ with $A_{j}\in\mathbb{C}^{K\times
K}$ such that $\mathrm{det}A=f$. The smallest such $K$ is the _determinantal
complexity_ of $f$ denoted $\mathsf{dc}(f)$ and it is finite for every $f$.
The $\mathsf{VP}_{\mathrm{ws}}$-universal polynomial is the determinant, in
the sense that $f\in\mathsf{VP}_{\mathrm{ws}}$ iff $\mathsf{dc}(f)=poly(n)$,
where $poly(n)$ denotes any fixed degree polynomial in $n$. Here
$\mathsf{VP}_{\mathrm{ws}}$ is the class of polynomials with poly-sized
Algebraic Branching Programs (a model between “formula” and “circuit”’). The
class $\mathsf{VP}_{\mathrm{ws}}$ has been the main subject of study and is
often interchangably used for VP. The classical universal VNP-complete
polynomial is the permanent

$\mathrm{per}_{m}[X_{ij}]_{i,j=1}^{m}=\sum_{\sigma\in
S_{m}}\prod_{i=1}^{m}X_{i\sigma(i)}.$

Thus, separating $\mathsf{VP}_{\mathrm{ws}}$ from VNP can be done by showing
that $\mathsf{dc}(per_{m})\gg poly(m)$.

The _Geometric Complexity Theory_ (GCT) program of Mulmuley and Sohoni [MS01,
MS08] compares the determinant and permanent by comparing their orbit closures
under the action of $GL_{n^{2}}$ on the variables $(X_{11},\ldots,X_{nn})$. If
$\mathsf{dc}(\mathrm{per}_{m})\leq n$, then
$\overline{GL_{n^{2}}\mathrm{per}_{m}}\subset\overline{GL_{n^{2}}{\mathrm{det}}_{n}}$,
and passing to the coordinate ring, this induces a $GL_{n^{2}}$-equivariant
surjection

(2.1)
$\displaystyle\mathbb{C}[\overline{GL_{n^{2}}{\mathrm{det}}_{n}}]\twoheadrightarrow\mathbb{C}[\overline{GL_{n^{2}}X_{11}^{n-m}\mathrm{per}_{m}}]$

To show a lower bound for $\mathsf{dc}(\mathrm{per}_{m})$, i.e.
$\mathsf{dc}(\mathrm{per}_{m})>n$, then we need to show that the above
surjection does not happen. Decomposing these modules into irreducibles for
any given degree $d$, we have

(2.2)
${\mathbb{C}}[\overline{\mathrm{GL}_{n^{2}}{\mathrm{det}}_{n}}]_{d}\simeq\bigoplus_{\lambda}V_{\lambda}^{\oplus\delta_{\lambda,d,n}},\quad\text{and}\quad{\mathbb{C}}[\overline{\mathrm{GL}_{n^{2}}\mathrm{per}_{m}^{n}}]_{d}\simeq\bigoplus_{\lambda}V_{\lambda}^{\oplus\gamma_{\lambda,d,n,m}}.$

Thus, to show that 2.1 is not possible, we can find an irreducible
$GL_{n^{2}}$ module $V_{\lambda}$, such that
$\gamma_{\lambda,d,n,m}>\delta_{\lambda,d,n}$ for some $d$. Such $\lambda$’s
are called _multiplicity obstructions_ and $\gamma$ and $\delta$ are closely
related to plethysm and Kronecker coefficients. When $\delta_{\lambda,d,n}=0$
also, then $\lambda$ is an _occurrence obstruction_. It was shown in [BIP19]
that there are no occurrence obstructions for $n>m^{25}$, so we need to find
multiplicity obstructions.

This is one of the main applications of Kronecker and plethysm coefficients
and motivates our work. In particular, we have

$\delta_{\lambda,d,n}\leq
g(\lambda,n^{d},n^{d})\qquad\text{and}\qquad\gamma_{\lambda,d,n,m}\leq
a_{\lambda}(d[n]).$

See §3 for the definitions and [Pan23] for a brief overview of these
connections.

##  3\. Multiplicities and structure constants

Once the irreducible representations have been sufficiently understood, it is
natural to consider what other representations can be formed by them and how
such representations decompose into irreducibles.

In the case of $GL_{N}(\mathbb{C})$ these coefficients are the
_Littlewood–Richardson_ _coefficients_ (LR) $c^{\lambda}_{\mu\nu}$ defined as
the multiplicity of $V_{\lambda}$ in $V_{\mu}\otimes V_{\nu}$, so

$V_{\mu}\otimes V_{\nu}=\bigoplus_{\lambda}V_{\lambda}^{\oplus
c^{\lambda}_{\mu\nu}}.$

Via their characters, they can be equivalently defined as

$s_{\mu}s_{\nu}=\sum_{\lambda}c^{\lambda}_{\mu\nu}s_{\lambda},\quad\text{ and
}\quad s_{\lambda/\mu}=\sum_{\nu}c^{\lambda}_{\mu\nu}s_{\nu}.$

While no nice product formula exists for their computation, they have a
_combinatorial interpretation_ , the so called _Littlewood-Richardson rule_ ,
see [Sta99, App. 1].

######  Theorem 3.1 (Littlewood-Richardson rule).

The Littlewood-Richardson coefficient $c^{\lambda}_{\mu\nu}$ is equal to the
number of skew SSYT $T$ of shape $\lambda/\mu$ and type $\nu$, whose reading
word is a ballot sequence.

A ballot sequence means that in every prefix of the sequence the number of
$1$’s$\geq$ the number of $2$’s $\geq$ number of $3$’s etc. For example, we
have $c^{(6,4,3)}_{(3,1),(4,3,2)}=2$ as there are two LR tableaux (SSYT of
shape $(6,4,3)/(3,1)$ and type $(4,3,2)$ whose reading words are ballot
sequences) 111,122,233 with reading word $111221332$ and 111,222,133 with
reading word 111222331.

The _Kronecker coefficients_ $g(\lambda,\mu,\nu)$ of the symmetric group are
the corresponding structure constants for the ring of $S_{n}$\- irreducibles.
Namely, $S_{n}$ acts diagonally on the tensor product of two Specht modules
and the corresponding module factors into irreducibles with multiplicities
$g(\lambda,\mu,\nu)$

$\mathbb{S}_{\lambda}\otimes\mathbb{S}_{\mu}=\bigoplus_{\nu}\mathbb{S}_{\nu}^{\oplus
g(\lambda,\mu,\nu)}.$

In terms of characters we can write them as

(3.1)
$g(\lambda,\mu,\nu)=\langle\chi^{\lambda}\chi^{\mu},\chi^{\nu}\rangle=\frac{1}{n!}\sum_{w\in
S_{n}}\chi^{\lambda}(w)\chi^{\mu}(w)\chi^{\nu}(w).$

The last formula shows that they are symmetric upon interchanging the
underlying partitions $g(\lambda,\mu,\nu)=g(\mu,\nu,\lambda)=\cdots$ which
motivates us to use such symmetric notation.

The _Kronecker product_ $*$ on $\Lambda$ is defined on the Schur basis by

$s_{\lambda}*s_{\mu}=\sum_{\nu}g(\lambda,\mu,\nu)s_{\nu},$

and extended by linearity.

Inspired by the Littlewood-Richardson coefficients, Murnaghan defined them in
1938. In fact, he showed that, see [Mur56],

######  Theorem 3.2 (Murnaghan).

For every $\lambda,\mu,\nu$, such that $|\lambda|=|\mu|+|\nu|$ we have that

$c^{\lambda}_{\mu\nu}=g((n-|\lambda|,\lambda),(n-|\mu|,\mu),(n-|\nu|,\nu)),$

for sufficiently large $n$.

In particular, one can see that $n=2|\lambda|+1$ would work. Note that even
when the sizes of the partitions do not add up, the RHS stabilizes as
$n\to\infty$ to the _reduced Kronecker coefficients_ , see 7.

Thanks to the Schur-Weyl duality, they can also be interpreted via Schur
functions as

$s_{\lambda}[{\textbf{{x}}}{\textbf{{y}}}]=\sum_{\mu,\nu}g(\lambda,\mu,\nu)s_{\mu}({\textbf{{x}}})s_{\nu}({\textbf{{y}}}),$

where
${\textbf{{x}}}{\textbf{{y}}}=(x_{1}y_{1},x_{1}y_{2},\ldots,x_{2}y_{1},\ldots)$
is the vector of all pairwise products. In terms of $GL$ representations they
give us the dimension of the invariant space

$g(\lambda,\mu,\nu)=\dim(V_{\mu}\otimes V_{\nu}\otimes
V^{*}_{\lambda})^{GL_{N}\times GL_{M}},$

where $V_{\mu}$ is considered as a $GL_{N}$-module, and $V_{\nu}$ as a
$GL_{M}$-module and $V_{\lambda}^{*}$ is a dual $GL_{NM}$-module. In other
words, they are dimensions of highest weight vector spaces, and using this
interpretation for them as dimensions of highest weight spaces one can show
the following, see [CHM07]

######  Theorem 3.3 (Semigroup property).

Let $(\alpha^{1},\beta^{1},\gamma^{1})$ and
$(\alpha^{2},\beta^{2},\gamma^{2})$ be two partition triples, such that
$|\alpha^{1}|=|\beta^{1}|=|\gamma^{1}|$ and
$|\alpha^{2}|=|\beta^{2}|=|\gamma^{2}|$. Suppose that
$g(\alpha^{1},\beta^{1},\gamma^{1})>0$ and
$g(\alpha^{2},\beta^{2},\gamma^{2})>0$. Then

$g(\alpha^{1}+\alpha^{2},\beta^{1}+\beta^{2},\gamma^{1}+\gamma^{2})\geq\max\\{g(\alpha^{1},\beta^{1},\gamma^{1}),g(\alpha^{2},\beta^{2},\gamma^{2})\\}.$

From the original $S_{n}$ characters definition we see that

$g(\lambda,\mu,\nu)=g(\lambda^{\prime},\mu^{\prime},\nu)$

since $\chi^{\lambda^{\prime}}(w)=\chi^{\lambda}(w)\mathrm{sgn}(w)$. In
particular, we have $g(\lambda,\mu,(n))=\delta_{\lambda,\mu}$ for all
$\lambda$ and $g(\lambda,\mu,1^{n})=\delta_{\lambda,\mu^{\prime}}$.

######  Example 3.4.

By the above observation we have that

$h_{k}[{\textbf{{x}}}{\textbf{{y}}}]=s_{k}[{\textbf{{x}}}{\textbf{{y}}}]=\sum_{\lambda\vdash
k}s_{\lambda}({\textbf{{x}}})s_{\lambda}({\textbf{{y}}}).$

Using the Jacobi-Trudi identity we can write

$\displaystyle
s_{2,1}[{\textbf{{x}}}{\textbf{{y}}}]=h_{2}[{\textbf{{x}}}{\textbf{{y}}}]h_{1}[{\textbf{{x}}}{\textbf{{y}}}]-h_{3}[{\textbf{{x}}}{\textbf{{y}}}]=\left(s_{2}({\textbf{{x}}})s_{2}({\textbf{{y}}})+s_{1,1}({\textbf{{x}}})s_{1,1}({\textbf{{y}}})\right)s_{1}({\textbf{{x}}})s_{1}({\textbf{{y}}})$
$\displaystyle-
s_{3}({\textbf{{x}}})s_{3}({\textbf{{y}}})-s_{2,1}({\textbf{{x}}})s_{2,1}({\textbf{{y}}})-s_{1,1,1}({\textbf{{x}}})s_{1,1,1}({\textbf{{y}}})$
$\displaystyle=s_{2,1}({\textbf{{x}}})s_{2,1}({\textbf{{y}}})+s_{2,1}({\textbf{{x}}})s_{3}({\textbf{{y}}})+s_{3}({\textbf{{x}}})s_{2,}({\textbf{{y}}})+s_{1,1,1}({\textbf{{x}}})s_{2,1}({\textbf{{y}}})+s_{2,1}({\textbf{{x}}})s_{1,1,1}({\textbf{{y}}}).$

So we see that $g((2,1),(2,1),(2,1))=1$.

The _plethysm coefficients_ $a^{\lambda}_{\mu,\nu}$ are multiplicities of an
irreducible $\mathrm{GL}$ representation in the composition of two
$\mathrm{GL}$ representations. Namely, let $\rho^{\mu}:GL_{N}\to GL_{M}$ be
one irreducible, and $\rho^{\nu}:GL_{M}\to GL_{K}$ be another. Then
$\rho^{\nu}\circ\rho^{\mu}:GL_{N}\to GL_{K}$ is another representation of
$GL_{N}$ which has a character $s_{\nu}[s_{\mu}]$, which decomposes into
irreducibles as

$s_{\nu}[s_{\mu}]=\sum_{\lambda}a^{\lambda}_{\mu,\nu}s_{\lambda}.$

Here the _plethystic_ notation $f[g]$ means the evaluation of $f$ over the
monomials of $g$ as variables: if
$g={\textbf{{x}}}^{\alpha^{1}}+{\textbf{{x}}}^{\alpha^{2}}+\cdots$, then
$f[g]=f({\textbf{{x}}}^{\alpha^{1}},{\textbf{{x}}}^{\alpha^{2}},\ldots)$.

######  Example 3.5.

We have that

$\displaystyle
s_{(2)}[s_{(1^{2})}]=h_{3}[e_{2}]=h_{2}(x_{1}x_{2},x_{1}x_{3},\ldots)=x_{1}^{2}x_{2}^{2}+x_{1}^{2}x_{2}x_{3}+3x_{1}x_{2}x_{3}x_{4}+\cdots$
$\displaystyle=s_{2,2}(x_{1},x_{2},x_{3},\ldots)+s_{1,1,1,1}(x_{1},x_{2},x_{3},\ldots),$

so $a^{(2,2)}_{(2),(1,1)}=1$ and $a^{(3,1)}_{(2),(1,1)}=0$.

We will be particularly interested when $\mu=(d)$ or $(1^{d})$ which are the
$d$th symmetric power $Sym^{d}$ and the $d$th wedge power $\Lambda^{d}$, and
$\nu=(n)$. We denote this plethysm coefficient by
$a_{\lambda}(d[n]):=a^{\lambda}_{(d),(n)}$ and

$h_{d}[h_{n}]=\sum_{\lambda}a_{\lambda}(d[n])s_{\lambda}.$

These coefficients are central to the GCT application and deserve special
attention.

##  4\. Combinatorial interpretations

“Combinatorial interpretation”, albeit never formally defined in the
literature, is assumed to mean a family of nice discrete objects whose
cardinality gives the desired quantity. In practice, for quantities with
combinatorial interpretation, computing them is in #P. On the other hand,
being in #P does not necessarily give a “nice” combinatorial interpretation,
but is certainly a starting point. All problems considered here are in GapP,
which makes #P the natural class to consider in relation to “manifestly
nonnegative” formulas. If such a problem is not in #P, then there could not be
a reasonable nonnegative combinatorial interpretation within the given
context. This paradigm is discussed at length in [IP22, Pak22+, Pan23].

Following the discovery of the Littlewood-Richardson rule in 1934, Murnaghan
[Mur38] defined the Kronecker coefficients of $S_{n}$ and computed various
special cases, but quickly observed that this is no easy task. Interest in
nonnegative combinatorial interpretation of these coefficients reemerged in
the 80s, see [Las79, GR85], and was stated as Problem 10 in Stanley’s
list111See this for the original list and updates on the problems
https://mathoverflow.net/questions/349406/ of “Open Problems in Algebraic
Combinatorics” [Sta00].

######  Open Problem 4.1 (Stanley).

Find a combinatorial interpretation of $g(\lambda,\mu,\nu)$, thereby
combinatorially proving that they are nonnegative.

Over the years, there has been very little progress on the question. In 1989
Remmel determined $g(\lambda,\mu,\nu)$ when two of the partitions are hooks.
In 1994 Remmel and Whitehead [RW94] determined $g(\lambda,\mu,\nu)$ when two
of the partitions are two-rows, i.e. $\ell(\lambda),\ell(\mu)\leq 2$. This
case was subsequently studied also in [BMS15]. In 2006 Ballantine and Orellana
[BO05] determined a rule for $g(\lambda,\mu,\nu)$ when one partition is a two-
row, e.g. $\mu=(n-k,k)$, and the first row of one of the others is large,
namely $\lambda_{1}\geq 2k-1$. The most general rule was determined by Blasiak
[B13] in 2012 when one partition is a hook, and this was later simplified by
Blasiak and Liu [BL18], and further in [Liu17]. Other very special cases have
been computed for multiplicity free Kronecker products by Bessenrodt-Bowman
[BB17], Kroneckers corresponding to pyramids by Ikenmeyer-Mulmuley-Walter
[IMW17], $g(m^{k},m^{k},(mk-n,n))$ as counting labeled trees by Pak-Panova see
Remark 4.4, near rectangular partitions by Tewari in [T15], etc.

Similar questions pertain to the plethysm coefficients. The following problem
is number 9 in Stanley’s list [Sta00].

######  Open Problem 4.2 (Stanley).

Find a combinatorial interpretation for the plethysm coefficients
$a^{\lambda}_{\mu,\nu}$.

A detailed survey on the partial results and methods can be found in
[COSSZ22].

Even the simple case for $a_{\lambda}(d[n])=\langle
s_{\lambda},h_{d}[h_{n}]\rangle$ is not known in general unless $n=2$. While,
there is no direct connection between the Kronecker and plethysm coefficients,
the case when $\ell(\lambda)=2$ coincide, see [PP14], and actually give a
combinatorial interpretation as explained below.

######  Proposition 4.3.

We have that
$g(\lambda,n^{d},n^{d})=a_{\lambda}(d[n])=p_{k}(n,d)-p_{k-1}(n,d)$ for
$\lambda=(nd-k,k)\vdash nd$. Here $p_{r}(a,b)=\\#\\{\mu\vdash r:\mu_{1}\leq
a,\ell(\mu)\leq b\\}$ are the partitions of $r$ which fit inside the $a\times
b$ rectangle.

######  Remark 4.4.

In particular, these are the coefficients in the $q$-binomials

$\sum_{r}p_{r}(a,b)q^{r}=\binom{a+b}{a}_{q}:=\prod_{i=1}^{a}\frac{(1-q^{i+b})}{1-q^{i}}.$

The combinatorial proof by Kathy O’Hara of the unimodality of the $p_{r}(a,b)$
is what gives the cominatorial interpration for the particular Kronecker and
plethysm coefficients as counting certain labeled trees, see [Pan15, p. 9].

To formalize these problems, we formulate them within the Computational
Complexity framework. To set the stage with an example, we start with the
Littlewood-Richardson coefficients.

ComputeLR:

Input: $\lambda,\mu,\nu$

Output: Value of $c^{\lambda}_{\mu\nu}$.

Here and below, the input can be encoded in _unary_ or _binary_ , and this
could affect the complexity. By unary we mean that the input for each
partition is written as $(\underbrace{11\ldots
1}_{\lambda_{1}},\underbrace{1\ldots 1}_{\lambda_{2}},\ldots)$, so the input
size is $O(|\lambda|)=O(n)$. In binary, we encode each part $\lambda_{i}$ in
base 2, so the input size is
$\log_{2}(\lambda_{1})+\log_{2}(\lambda_{2})+\cdots=O(\ell(\lambda)\log_{2}(\lambda_{1}))$.

By the Littlewood-Richardson rule we have that when the input is unary,
ComputeLR$\in{{\rm{\textsf{\\#P}}}}$, as our witnesses are the skew
$\lambda/\mu$ tableaux, which are at most $n^{n}=O(2^{n^{2}})$-many, and each
can be checked to be an LR tableaux in time $O(n^{2})$. The LR conditions can
be translated into $O(\ell(\lambda)^{2})$ many linear inequalities, which
comprise the LR polytope. This description gives us that if the input is in
binary we still have ComputeLR$\in{{\rm{\textsf{\\#P}}}}$.

Using a reduction to Knapsack for binary input, it is not difficult to see
that

######  Theorem 4.5 (Narayanan [Nar06]).

When the input $\lambda,\mu,\nu$ is in binary, ComputeLR is #P-complete.

When the input is in unary, we do not know whether the problem is still that
hard.

######  Conjecture 4.6 (Pak-Panova 2020).

When the input is in unary we have that ComputeLR is #P-complete.

None of the above has been achieved for the Kronecker and plethysm
coefficients, however, due to the lack of any positive combinatorial formula.
Mulmuley also conjectured that computing the Kronecker coefficients would be
in #P, mimicking the Littlewood-Richardson coefficients.

ComputeKron:

Input: $\lambda,\mu,\nu$

Output: Value of $g(\lambda,\mu,\nu)$.

######  Conjecture 4.7 (Pak).

ComputeKron is not in #P under reasonable complexity theoretic assumptions
like PH not collapsing.

If the above is proven, that would make any solution to Open Problem 4.1 as
unlikely as the polynomial hierarchy collapsing. Any reasonable combinatorial
interpretation such as counting certain objects would show that the problem is
in #P, since the objects would likely be verifiable in polynomial time. The
problem stands for both unary and binary input.

Note that ComputeKron$\,\in{{\rm{\textsf{GapP}}}}$ ([BI08]) as it is easy to
write an alternating sum for its computation, for example using contingency
arrays, see [PP17b].

The author’s experience with Kronecker coefficients suggests that some
particular families would be as hard as the general problem.

######  Conjecture 4.8 (Panova).

ComputeKron is in #P when $\ell(\lambda)=2$ if and only if ComputeKron is in
#P . Likewise, ComputeKron is in #P for $\mu=\nu=(n^{d})$ and $\lambda\vdash
nd$ as the input if and only if ComputeKron is in #P .

Of course, the backward direction is clear, if the general problem is in #P,
then also the special subproblems are in #P.

The plethysm coefficients can also be studied from this perspective.

ComputePleth:

Input: $\lambda,\mu,\nu$

Output: Value of $a^{\lambda}_{\mu,\nu}$.

######  Open Problem 4.9.

Determine whether ComputePleth$\in{{\rm{\textsf{\\#P}}}}$.

Using symmetric function identities, it is not hard to find an alternating
formula for the plethysms and show that they are also in GapP , see [FI20].
They also show that deciding positivity is NP -hard and thus the
computational problem is #P-hard. ComputePleth may not in be in #P in the
general case, but also when $\mu,\nu$ are single row partitions. The
coefficient $a_{\lambda}(d[n])$ in this case has special significance in GCT,
see [Pan23].

Underlying all the representation theoretic multiplicities mentioned above are
the characters of the symmetric group. For example, equation (3.1) expresses
the Kronecker coefficients via characters, and the other structure constants
can also be expressed in similar ways. This motivates us to understand them
also computationally. As we shall see, they also provide a proof of concept
for the idea that certain positive integral algebro-combinatorial quantities
may indeed not have a combinatorial interpretation.

The characters satisfy some particularly nice identities coming from the
orthogonality of the rows and columns of the character table in $S_{n}$. We
have that

(4.1) $\sum_{\lambda\vdash
n}\chi^{\lambda}(w)^{2}=\prod_{i}i^{c_{i}}c_{i}!\,,$

where $c_{i}=$ number of cycles of length $i$ in $w\in S_{n}$. When
$w=\mathrm{id}$, we have that $\chi^{\lambda}(\mathrm{id})=f^{\lambda}$, the
number of SYTs and the identity is proven using the beautiful RSK bijection.
The first step in this proof is to identify $(f^{\lambda})^{2}$ as the number
of pairs of SYTs of the same shape.

Could anything like that be done for equation (4.1)? The first step would be
to understand what objects $\chi^{\lambda}(w)^{2}$ counts, does it have any
positive combinatorial interpretation? We formulate it again using the CC
paradigm as

ComputeCharSq:

Input: $\lambda,\alpha\vdash n$, unary.

Output: the integer $\chi^{\lambda}(\alpha)^{2}$.

######  Theorem 4.10 ([IPP22]).

ComputeCharSq$\not\in{{\rm{\textsf{\\#P}}}}$ unless
$PH=\Sigma^{{{\rm{\textsf{P}}}}}_{2}$.

The last condition says “polynomial hierarchy collapses to the second level”,
which is almost as unlikely as P =NP . The widely believe complexity theoretic
assumptions are that ${{\rm{\textsf{P}}}}\neq{{\rm{\textsf{NP}}}}$ and that PH
does not collapse. This problem shows that some natural questions in Algebraic
Combinatorics are indeed not in #P.

The proof of this Theorem follows from another complexity theoretic result we
show, namely that deciding if $\chi^{\lambda}(\alpha)\neq 0$ is PH-hard as
well, see end of §5.

##  5\. Positivity problems

Motivated by other developments, further questions about the Kronecker
coefficients have appeared. Following their work in [HSTZ13] on the square of
the Steinberg character for finite groups of Lie type, the authors conjectured
that a similar irreducible character should exist for the symmetric group and
formulated the following.

######  Conjecture 5.1 (Tensor square conjecture).

For every $n\geq 9$ there exists a symmetric partition $\lambda\vdash n$, such
that $\mathbb{S}_{\lambda}\otimes\mathbb{S}_{\lambda}$ contains every
irreducible $S_{n}$ module. In other words $g(\lambda,\lambda,\mu)>0$ for all
$\mu\vdash n$.

Following this, Saxl conjectured a specific partition, namely the staircase,
which would satisfy that.

######  Conjecture 5.2 (Saxl, see [PPV16]).

Let $\delta_{k}=(k,k-1,\ldots,1)$ be the staircase partition. Then
$g(\delta_{k},\delta_{k},\mu)>0$ for all $k$ and $\mu\vdash\binom{k+1}{2}$.

This conjecture has received a lot of attention partially due to its
concreteness.

Positivity results were proved using a combination of three methods – the
semigroup property constructing recursively positive triples from building
blocks, explicit heighest weight constructions using the techniques in
[Ful00], and an unusual comparison with characters, which was originally
stated in by Bessenrodt and Behns [BB04] to show that
$g(\lambda,\lambda,\lambda)>0$ for $\lambda=\lambda^{\prime}$, later
generalized in [PPV16], and in its final form in [PP17a].

######  Theorem 5.3 ([PP17a]).

Let $\lambda,\mu\vdash n$ and $\lambda=\lambda^{\prime}$. Let
$\hat{\lambda}=(2\lambda_{1}-1,2\lambda_{2}-3,3\lambda_{3}-5,\ldots)$ be the
principal hooks of $\lambda$. Then

$g(\lambda,\lambda,\mu)\geq|\chi^{\mu}(\hat{\lambda})|.$

The technique of explicit highest weight vectors construction led to the
following more general result.

######  Theorem 5.4 ([I15]).

Let $\mu\vdash\binom{k+1}{2}$ be a partition comparable to $\rho_{k}$ in the
dominance order, i.e. $\mu\succ\rho_{k}$ or $\rho_{k}\succ\mu$. Then
$g(\rho_{k},\rho_{k},\mu)>0$.

Using this result and generalizations, and clever combinations of the
semigroup property 3.3, Luo and Sellke [LS17] proved that
$\chi^{\rho_{k}}\otimes\chi^{\rho_{k}}\otimes\chi^{\rho_{k}}\otimes\chi^{\rho_{k}}$
contains every $\chi^{\mu}$, and that $\chi^{\rho_{k}}\otimes\chi^{\rho_{k}}$
contains “most” irreducible representations. In [B18], Bessenrodt proved that
all double hooks, i.e. partitions with Durfee size 2, are contained in
$\chi^{\rho_{k}}\otimes\chi^{\rho_{k}}$, and Li generalized to triple hooks
[L21]. Harman and Ryba [HR22] showed that
$\chi^{\rho_{k}}\otimes\chi^{\rho_{k}}\otimes\chi^{\rho_{m}}$ contains every
irreducible representation.

The semigroup property is a powerful tool to create positive Kronecker triples
by induction out of building blocks. However, creating a particular partition,
like the staircase or a rectangle, out of building blocks is very restrictive
and quickly encounters number theoretic issues. A rectangle can be “cut” only
into other rectangles. This prompts us to enlarge the class of positive
triples. In 2020, with Christine Bessenrodt we generalized Conjecture 5.1 as
follows (and checked for partitions up to size 20).

######  Conjecture 5.5 (Bessenrodt-Panova 2020).

For every $n$ there exists a $k(n)$, such that for every $\lambda\vdash n$
with $\lambda=\lambda^{\prime}$ and $d(\lambda)>k_{n}$ which is not the square
partition, we have $g(\lambda,\lambda,\mu)>0$ for all $\mu\vdash n$.

Here $d(\lambda)=\max\\{i:\lambda_{i}\geq i\\}$ is the Durfee square size of
the partition. Partial progress on that conjecture will appear in the work of
Chenchen Zhao.

Another positivity result, motivated by applications in GCT, was obtained in
[IP17] as

######  Lemma 5.6 ([IP17, Thm 1.10]).

Let $X:=\\{1,\hskip 1.70709pt1^{2},\hskip 1.70709pt1^{4},\hskip
1.70709pt1^{6},\hskip 1.70709pt2\hskip 0.85355pt1,\hskip 1.70709pt3\hskip
0.85355pt1\\}$, and let partition $\nu\notin X$. Denote
$\ell:=\max\\{\ell(\nu)+1,9\\}$, and suppose $r>3\ell^{3/2}$, $s\geq
3\ell^{2}$, and $|\nu|\leq rs/6$. Let
$\nu[N]:=(N-|\nu|,\nu_{1},\nu_{2},\ldots)$. Then $g(s^{r},s^{r},\nu[rs])>0$.

The tensor square conjectures raise the question on simply determining when
$g(\lambda,\mu,\nu)>0$. It is a consequence of representation theory that when
$n>2$ for every $\mu\vdash n$ there is a $\lambda\vdash n$, such that
$g(\lambda,\lambda,\mu)>0$, see [Sta99, Ex. 7.82] but even that has no
combinatorial proof.

To understand why such problems are difficult, we resort to the computational
complexity framework. For Kostka numbers, determining if $K_{\lambda,\mu}>0$
is easy, it just requires us checking that $\lambda\succ\mu$ in the dominance
order. For Littlewood-Richardson that’s a lot less trivial despite the
combinatorial rule.

LRPos:

Input: $\lambda,\mu,\nu$

Output: Is $c^{\lambda}_{\mu\nu}>0$?

The proof of the Saturation Conjecture by Knutson and Tao showed that an LR
coefficient is nonzero if and only if the corresponding hive polytope is
nonempty. This polytope is a refinement of the Gelfand-Tsetlin polytope, and
is defined by $O(\ell(\lambda)^{2})$ many inequalities. Showing that the
polytope is nonempty is thus a linear programming problem, which can be solved
in polynomial time, see [MNS12].

######  Theorem 5.7.

We have that LRPos $\in{{\rm{\textsf{P}}}}$ when the input is in binary (and
unary).

KronPos:

Input: $\lambda,\mu,\nu$

Output: Is $g(\lambda,\mu,\nu)>0$?

In the early stages of GCT Mulmuley conjectured [MS08] that they would behave
like the Littlewood-Richardson, so KronPos$\in{{\rm{\textsf{P}}}}$, which was
recently disproved.

######  Theorem 5.8 ([IMW17]).

When the input $\lambda,\mu,\nu$ is in unary, KronPos is NP -hard.

The proof uses the fact that in certain cases $g(\lambda,\mu,\nu)$ is equal to
the number of pyramids with marginals $\lambda,\mu,\nu$ and deciding if there
is such a pyramid is NP-complete. However, the problem is not yet in NP: we do
not have, for every $\lambda,\mu,\nu$, polynomial witnesses showing that
$g(\lambda,\mu,\nu)>0$ when this is the case. This is yet another open
problem.

######  Open Problem 5.9.

Determine whether when the input $\lambda,\mu,\nu$ is in unary, KronPos is in
NP.

Needless to say, the problem would be [computationally] harder when the input
is in binary.

Positivity of plethysm coefficients is even less understood. Plethysm
coefficients $a_{\lambda}(d[n])$ are important in GCT and positivity of
$a_{\lambda}(d[n])$ for partitions $\lambda$ with long first rows was
established in [BIP19]. In general, we do not expect the problem to be any
easier.

PlethPos:

Input: $\lambda,\mu,\nu$

Output: Is $a^{\lambda}_{\mu,\nu}>0$?

In [FI20], Fischer and Ikenmeyer showed that PlethPos is NP-hard. As there is
no combinatorial interpretation and no nice positivity criteria in general we
cannot say whether the problem is in NP.

######  Open Problem 5.10.

Determine whether PlethPos is in NP.

There is one major conjecture on plethysm coefficients.

######  Conjecture 5.11 (Foulkes).

Let $d>n$, then

$a_{\lambda}(d[n])\geq a_{\lambda}(n[d])$

for all $\lambda\vdash nd$.

This conjecture is related to the Alon-Tarsi conjecture, and has appeared in
GCT-related research. In [DIP19] we proved it for some families of 3-row
partitions.

As most of these quantities can be computed via symmetric group characters, it
is natural to ask how easy it is to decide if a character is 0 or not.

CharVanish:

Input: $\lambda,\alpha\vdash n$, unary.

Output: Is $\chi^{\lambda}(\alpha)=0?$

######  Theorem 5.12 ([IPP22]).

We have that CharVanish is C=P -complete under many-to-one reductions.

The class C=P is defined formally as $[{{\rm{\textsf{GapP}}}}=0]$, the class
of deciding when two #P functions have equal values, and this is a class
believed to be strictly larger than coNP and NP. Thus we cannot expect that
deciding $\chi=0$ would be in coNP and $\chi\neq 0$ in NP. This also leads to
the proof of Proposition 5.3. See [Pan23] for a discussion on that topic and
sketch of the proof.

##  6\. Asymptotic Algebraic Combinatorics

Asymptotic Algebraic Combinatorics is a natural extension of Algebraic
Combinatorics inspired by Probability and Asymptotic Representation Theory.
Instead of searching for exact formulas, bijections, combinatorial
interpretations, we are looking to understand quantities approximately. This
is, indeed, what we could hope for with the given structure constants in the
absence of nice formulas.

As mentioned in the Introduction, such problems have natural interplay with
Statistical Mechanics and Integrable Probability. They would also be important
in the search of multiplicity obstructions in GCT, see [Pan23].

###  6.1. Maximal multiplicities

The first step in such asymptotic analysis begins with estimating the range of
possible values. In [Sta99, Sta20], Stanley observed that

$\displaystyle\qquad\quad\ \max_{\lambda\vdash n}\max_{\mu\vdash
n}\max_{\nu\vdash n}\,\,g(\lambda,\mu,\nu)$
$\displaystyle=\,\sqrt{n!}\,e^{-O(\sqrt{n})}\,,$
$\displaystyle\qquad\,\max_{0\leq k\leq n}\max_{\lambda\vdash
n}\max_{\mu\vdash k}\max_{\nu\vdash n-k}\,\,c^{\lambda}_{\mu,\nu}$
$\displaystyle=\,2^{n/2-O(\sqrt{n})}.$

and asked

######  Open Problem 6.1 (Stanley).

Fix $n$. For which $\lambda,\mu,\nu$ with $\lambda\vdash n$, is
$c^{\lambda}_{\mu\nu}$ asymptotically maximal? For which $\lambda,\mu,\nu$ is
$g(\lambda,\mu,\nu)$ asymptotically maximal?

Using various symmetric function and representation theoretic identities
involving sums of these coefficients, it was observed in [PPY19a] that such
maximal partitions $\lambda$ must also have asymptotically maximal dimensions
$f^{\lambda}$. By the pioneering work of Vershik-Kerov [VK] and Loggan-Shepp
[LoS], we know that such partitions approach certain explicit curve, which we
refer to as the VKLS shape and VKLS partitions, and for all those we have
$f^{\lambda}=\sqrt{n!}e^{-O(\sqrt{n})}$.

######  Theorem 6.2 ([PPY19a]).

Let $\\{\lambda^{(n)}\vdash n\\}$, $\\{\mu^{(n)}\vdash n\\}$,
$\\{\nu^{(n)}\vdash n\\}$ be three partition sequences, such that

$(*)\qquad\qquad g\bigl{(}\hskip 0.85355pt\lambda^{(n)},\hskip
0.85355pt\mu^{(n)},\hskip 0.85355pt\nu^{(n)}\hskip
0.85355pt\bigr{)}\,=\,\sqrt{n!}\,e^{-O(\sqrt{n})}\hskip 1.70709pt.$

Then $\lambda^{(n)},\mu^{(n)},\nu^{(n)}$ have VKLS shape (i.e. are
asymptotically maximal). Conversely, for every two VKLS sequences
$\\{\lambda^{(n)}\vdash n\\}$ and $\\{\mu^{(n)}\vdash n\\}$, there exists a
VKLS partition sequence $\\{\nu^{(n)}\vdash n\\}$, s.t. (*) holds.

This statement shows “existence”, the problem here is to exhibit a particular
explicit family of partitions for which this asymptotics holds.

######  Open Problem 6.3.

Determine a family of partitions $\lambda^{(n)},\mu^{(n)},\nu^{(n)}\vdash n$,
such that

$g\bigl{(}\hskip 0.85355pt\lambda^{(n)},\hskip 0.85355pt\mu^{(n)},\hskip
0.85355pt\nu^{(n)}\hskip 0.85355pt\bigr{)}\,=\,\sqrt{n!}\,e^{-O(\sqrt{n})}$

as $n\to\infty$.

We believe that for the staircase partitions $\rho_{k}=(k,k-1,\ldots,1)$ the
Kronecker coefficient $g(\rho_{k},\rho_{k},\rho_{k})$ grows
superexponentially, and this is one specific candidate which could achieve
large, but not maximal, values. However, no exponential lower bounds are known
in this case.

Similar analysis can be done for the Littlewood-Richardson coefficients.
Again, the proofs can only derive “existence”, but not exhibit any specific
families.

######  Theorem 6.4 ([PPY19a]).

Fix $0<\theta<1$ and let $k_{n}:=\lfloor\theta n\rfloor$. Then:

1\. for every VKLS partition sequence $\\{\lambda^{(n)}\vdash n\\}$, there
exist VKLS partition sequences $\\{\mu^{(n)}\vdash k_{n}\\}$ and
$\\{\nu^{(n)}\vdash n-k_{n}\\}$, s.t.

$(**)\qquad\ c^{\lambda^{(n)}}_{\mu^{(n)},\hskip
1.70709pt\nu^{(n)}}\,=\,\binom{n}{k_{n}}^{1/2}\,e^{-O(\sqrt{n})}\hskip
1.70709pt,$

2\. for all VKLS partition sequences $\\{\mu^{(n)}\vdash k_{n}\\}$ and
$\\{\nu^{(n)}\vdash n-k_{n}\\}$, there exists a VKLS partition sequence
$\\{\lambda^{(n)}\vdash n\\}$, s.t. $(**)$ holds,

3\. for all VKLS partition sequences $\\{\lambda^{(n)}\vdash n\\}$ and
$\\{\mu^{(n)}\vdash k_{n}\\}$, there exists a partition sequence
$\\{\nu^{(n)}\vdash n-k_{n}\\}$, s.t.

$f^{\nu^{(n)}}\,=\,\sqrt{n!}\,e^{-O(n^{2/3}\log n)}\quad\text{and}\quad
c^{\lambda^{(n)}}_{\mu^{(n)},\hskip
1.70709pt\nu^{(n)}}\,=\,\binom{n}{k_{n}}^{1/2}\,e^{-O(n^{2/3}\log n)}\hskip
1.70709pt.$

We again ask when such maxima are achieved.

######  Open Problem 6.5.

Let $\theta\in(0,1)$ be some fixed number and let $k_{n}:=\lfloor\theta
n\rfloor$. Find families of partitions $\\{\lambda^{(n)}\vdash n\\}$,
$\\{\mu^{(n)}\vdash k_{n}\\}$ and $\\{\nu^{(n)}\vdash n-k_{n}\\}$, for which

$\ c^{\lambda^{(n)}}_{\mu^{(n)},\hskip
1.70709pt\nu^{(n)}}\,=\,\binom{n}{k_{n}}^{1/2}\,e^{-O(\sqrt{n})}\hskip
1.70709pt,$

While asymptotics of Kronecker coefficients have barely been studied, Schur
functions asymptotics in various regimes has been central to the field of
Integrable Probability. It is closely related to the Harish-Chandra-
Itzhykhson-Zuber integrals in random matrix theory. A step further takes us to
Kostka and Littlewood-Richardson coefficients, which can also be estimated
using the so-called elliptic integrals, see [BGH]. There, the problem of
asymptotics is translated into an implicit variational analysis, and it still
does not give explicit concrete answers.

There are currently no nontrivial asymptotic results of this kind for plethysm
coefficients.

######  Open Problem 6.6.

Determine the maximal asymptotic value of the plethysm coefficients

$\max_{\lambda\vdash n^{2}}a_{\lambda}(n[n]).$

The only nontrivial bounds come from their relation to rectangular Kronecker
coefficients, and in particular when $\lambda$ is a two-row partition, see §
6.3. We expect that the maxima should be at least exponential. Another source
of nontrivial lower bounds can be found in [FI20] where plethysms are compared
to pyramids. Similar comparison was used to obtain a family of large Kronecker
coefficients in [PP20a, PP23].

###  6.2. Bounded rows and diagonals

In the “maximal” regime, the partitions involved were close to the VKLS shape
which is symmetric and has length $O(\sqrt{n})$ for partitions of $n$. The
asymptotics changes significantly depending on the regimes of convergence for
the partitions involved.

When the lengths of the partitions are bounded, formulas coming from symmetric
functions and relating them to contingency tables become useful. We have the
following upper bound.

######  Theorem 6.7 ([PP20a]).

Let $\lambda,\mu,\nu\vdash n$ such that $\ell(\lambda)=\ell$, $\ell(\mu)=m$,
and $\ell(\nu)=r$. Then:

$g(\lambda,\mu,\nu)\,\leq\,\left(1+\frac{\ell
mr}{n}\right)^{n}\left(1+\frac{n}{\ell mr}\right)^{\ell mr}.$

In particular, when $\lambda=\mu=\nu=((\ell^{2})^{\ell})\vdash\ell^{3}=n$, we
have $g(\lambda,\mu,\nu)\leq 4^{n}$. Yet, a similar lower bound for that case
is beyond reach.

Further analysis using Schur function techniques also gives bounds when the
Durfee size (diagonal) of a partition is bounded, even if the length grows. We
have the following, see [PP23].

######  Theorem 6.8 ([PP23]).

Let $n,k\geq 1$, and let $\lambda,\mu,\nu\vdash n$, such that
$d(\lambda),\hskip 0.85355ptd(\mu),\hskip 0.85355ptd(\nu)\hskip
1.70709pt\leq\hskip 0.85355ptk$. Then:

(6.1) $g(\lambda,\mu,\nu)\,\leq\,\frac{1}{k^{8k^{2}}\hskip
0.85355pt2^{8k^{3}}}\,\,n^{4k^{3}\hskip 0.85355pt+\hskip
0.85355pt13k^{2}\hskip 0.85355pt+\hskip 0.85355pt31k}.$

We also know that the actual maximal value is not much further from this
bound. Let

$A(n,k)\,:=\,\max\hskip 1.70709pt\big{\\{}\hskip 0.85355ptg(\lambda,\mu,\nu)\
:\ \lambda,\mu,\nu\vdash n\ \ \text{and}\ \
\ell(\lambda),\ell(\mu),\ell(\nu)\leq k\hskip 0.85355pt\big{\\}}.$

######  Theorem 6.9 ([PP23]).

For all $k\geq 1$, there is a constant $C_{k}>0$, such that

(6.2) $A(n,k)\,\geq\,C_{k}\hskip 1.70709ptn^{k^{3}\hskip 0.85355pt-\hskip
0.85355pt3k^{2}\hskip 0.85355pt-\hskip 0.85355pt3k\hskip 0.85355pt+\hskip
0.85355pt3}\qquad\text{for all \ \ $n\geq 1$\hskip 0.85355pt.}$

However, we are nowhere close to finding asymptotics close to these maxima for
concrete families of partitions.

######  Open Problem 6.10.

For every fixed $k$ determine a family of partitions
$\lambda^{(n)},\mu^{(n)},\nu^{(n)}\vdash n$ with
$\ell(\lambda^{(n)}),\ell(\mu^{(n)}),\ell(\nu^{(n)})\leq k$, such that

$g(\lambda^{(n)},\mu^{(n)},\nu^{(n)})=O(n^{(k-1)^{3}}).$

Using the powerful technique of ACSV (Asymptotic Combinatorics in Several
Variables), the cases of $k\leq 4$ have been somewhat well understood and
explicit asymptotics derived in [MT]. For arbitrary, but fixed, values of $k$
though the ACSV is no longer applicable and we need other ways to compute
this.

The same question pertains to the plethysm coefficients.

######  Open Problem 6.11.

Show that for every fixed $k$ the maximal plethysm coefficient over partitions
with length $k$ grows polynomially in $n$. In particular, we have

$\log\max_{\lambda\vdash
n^{2},\,\ell(\lambda)=k}a_{\lambda}(n[n])=\Omega(\log(n))$

It was establsihed in [IP17] that plethysms are bounded above by rectangular
Kronecker coefficients,

$a_{\lambda}(d[n])\leq g(\lambda,n^{d},n^{d})$

for $\ell(\lambda)\leq m^{2}$, $\lambda_{1}\geq d(n-m)$ and $d,n$ large enough
so we are in the stable regime, i.e. the values of the plethysm and Kronecker
are constant when only $d,n$ and $\lambda_{1}$ grow. Thus, we would not expect
that plethysm coefficients would have larger growth than Kroneckers.

###  6.3. Tight asymptotics

There are very few nontrivial cases where we have certain explicit formulas
for Kronecker and plethysm coefficients and would be able to derive tight
asymptotics. One such case is for rectangular Kronecker coefficients
$g(\lambda,m^{\ell},m^{\ell})$ when $\lambda$ has two rows. We have that, see
[PP17a], for $\lambda=(m\ell-n,n)$,

$g(m^{\ell},m^{\ell},\lambda)=p_{n}(\ell,m)\hskip 0.85355pt-\hskip
0.85355ptp_{n-1}(\ell,m)=a_{\lambda}(m[\ell]),$

where $p_{n}(\ell,m)=\\#\\{\alpha\vdash n,\alpha_{1}\leq
m,\ell(\alpha)\leq\ell\\}$ is the number of partitions of $k$ whose Young
diagram fits inside an $\ell\times m$ rectangle.

Using this partition counting interpretation, and deriving tight asymptotics
for $p_{n}(m,\ell)$ using tilted geometric random variables, we obtain

######  Theorem 6.12 ([MPP19a]).

Let $A:=\frac{\ell}{m}$ $B:=\frac{n-1}{m^{2}}$. Let $c,d$ be solutions of a
certian system of integral equations with parameters $A,B$. We have

$a_{\lambda}(m[\ell])=g(\lambda,m^{\ell},m^{\ell})=p_{n}(\ell,m)-p_{n-1}(\ell,m)\sim\frac{d}{m}p_{n-1}(\ell,m)\sim\frac{d\,\,e^{m\left[cA+2dB-\log(1-e^{-c-d})\right]}}{2\pi
m^{3}\sqrt{D}}.$

Note that some technical conditions for the theorem to hold also include that
$\ell,m$ grow at the same rate, and also that $\frac{n}{m\ell}$ should be away
from $\frac{1}{2}$. When $n\sim\frac{1}{2}m\ell$ we can no longer estimate the
difference between $p_{n}$’s so tightly and we need a different approach for
the following

######  Open Problem 6.13.

Find tight asymptotics when $\lambda=(\lceil m^{2}/2\rceil,\lfloor
m^{2}/2\rfloor)$ for $g(m^{m},m^{m},\lambda)$.

The best lower bound in this case comes from characters and is obtained in
[PP17a].

Needless to say, any other explicit tight asymptotic results would be of great
interest and, using semigroup property, could lead to improved lower bounds in
other regimes.

##  7\. Reduced Kronecker coefficients

Since the Kronecker coefficients quickly turned out to be difficult to
understand, hopes turned towards the _stable Kronecker coefficients_ defined
as

$\overline{g}(\alpha,\beta,\gamma)\hskip 1.70709pt:=\hskip
1.70709pt\lim_{n\to\infty}\hskip
1.70709ptg\bigl{(}\alpha[n],\beta[n],\gamma[n]\bigr{)},\
\quad\alpha[n]:=(n-|\alpha|,\alpha_{1},\alpha_{2},\ldots),\
n\geq|\alpha|+\alpha_{1}.$

They generalize the Littlewood-Richardson coefficients, following Theorem 3.2
from [Mur56].

$\overline{g}(\alpha,\beta,\gamma)\,=\,c^{\alpha}_{\beta\gamma}\quad\text{for}\quad|\alpha|\hskip
1.70709pt=\hskip 1.70709pt|\beta|\hskip 0.85355pt+\hskip
0.85355pt|\gamma|\hskip 0.85355pt,$

and were thereby called “extended Littlewood-Richardson coefficients” in
[Kir04]. They have thus occupied an intermediate spot between the Littlewood-
Richardson and ordinary Kronecker coefficients, and have been a subject of
independent study and interest, see [Mur38, Mur56, Bri93, Val99, Kir04, Kly04,
BOR11, BDO15, CR15, Man15, SS16, IP17, PP20b, OZ21]. Together with the
ordinary Kronecker coefficients, the problem of finding a combinatorial
interpretation has also been part of the agenda, see [Sta00].

The ordinary Kronecker coefficients can be expressed as a small alternating
sum of reduced Kroneckers and reduced Kroneckers are certain sums of ordinary
Kroneckers, see [BOR11, BDO15]. These relationships show that reduced
Kroneckers are also #P-hard to compute, see [PP20b]. However, it could not be
immediately deduced that their positivity is NP -hard, which prompted the
following question.

######  Open Problem 7.1.

Given input $\lambda,\mu,\nu$ (in unary), is deciding whether
$\overline{g}(\lambda,\mu,\nu)>0$ NP-hard? Determine whether computing
$\overline{g}(\lambda,\mu,\nu)$ is #P-complete?

As we noted, the second part of that problem would follow if there is a
combinatorial interpretation for them, or for the ordinary Kronecker
coefficients.

Some special cases of combinatorial interpretations can be derived from the
ordinary Kronecker coefficients. Separately, in [CR15] a combinatorial
interpretation was given when $\mu,\nu$ are rectangles and $\lambda$ is one
row, and other similar cases were derived in [BO05]. Methods to compute them,
as well as for the ordinary Kronecker coefficients, have been developed in a
series of papers, see [BDO15, BOR11, OZ20, OZ21].

Until recently, it was believed they are strictly better behaved than the
ordinary Kroneckers, with the following conjecture appearing in [Kir04, Kly04]

######  Conjecture 7.2 (Kirillov, Klyachko).

The reduced Kronecker coefficients satisfy the saturation property:

$\overline{g}(N\alpha,N\beta,N\gamma)>0\quad\text{for some}\hskip 1.70709pt\
N\geq 1\quad\Longrightarrow\quad\overline{g}(\alpha,\beta,\gamma)>0\hskip
0.85355pt.$

Using the recent positivity results, in particular for rectangular Kroneckers
from [IP17], this was also disproved.

######  Theorem 7.3 ([PP20b]).

For all $k\geq 3$, the triple of partitions
$\bigl{(}1^{k^{2}-1},1^{k^{2}-1},k^{k-1}\bigr{)}$ is a counterexample to the
Conjecture. For every partition $\gamma$ s.t. $\gamma_{2}\geq 3$, there are
infinitely many pairs $(a,b)\in\mathbb{N}^{2}$ s.t. $(a^{b},a^{b},\gamma)$ is
a counterexample.

As shown in [PP20b], asymptotically, and complexity-wise they behave more
similarly to the ordinary Kronecker than to the Littlewood-Richardson
coefficients.

######  Remark 7.4.

In the course of writing this paper, the first part of Open Problem 7.1 was
settled in [IP23], where it was shown that every Kronecker coefficient is
equal to a [not much larger] reduced Kronecker coefficient:

$g(\lambda,\mu,\nu)=\overline{g}(\nu_{1}^{\ell(\lambda)}+\lambda,\nu_{1}^{\ell(\mu)}+\mu,(\nu_{1}^{\ell(\lambda)+\ell(\mu)},\nu)).$

Thus the reduced Kronecker coefficients are just as hard as the Kroneckers,
and the complexity results follow from§ 4. This also shows that the problems
are essentially the same, and the reduced Kronecker coefficients are not
easier in general.

##  8\. Methods

While the concrete open problems inspire work in the area, the pertinent task
is to create tools for understanding the Kronecker and plethysm coefficients.
Of course, an ultimate tool could be the “combinatorial interpretation”, but
this itself has become the hardest problem to understand and its solution
requires new tools. So far, as very little progress has been made in this
direction, it is clear that we need something new.

Kronecker coefficients can be interpreted via $S_{n}$ as multiplicities. Via
Schur-Weyl duality, they are also dimensions of invariant spaces under $GL$
action. The last interpretation is what gives the semigroup property,
something that cannot be seen from the $S_{n}$ perspective. On the other hand,
the transpositional invariance
$g(\lambda,\mu,\nu)=g(\lambda^{\prime},\mu^{\prime},\nu)$ is visible from
their $S_{n}$ definition. There are many more examples showing the variety of
results one can get using different methods and the limitations of each one
also. Perhaps the best tool would be able to unify all these views.

Symmetric functions have been one of the most useful tools in Algebraic
Combinatorics, and is certainly the author’s favorite. The Littlewood-
Richardson coefficients are structure constants in the ring of symmetric
functions and thus have been very successfully studied using Schur functions.
But the Kronecker coefficients cannot be interpreted in that way. Motivated by
that, a family of symmetric functions was developed in [OZ20, OZ21]. Symmetric
functions have not been very useful in establishing positivity results,
because the formulas involved are often alternating sums. However, they are
useful for finding asymptotics and bounds as done in [PP20a, PP23] for
example. Within integrable probability they have been a lot more successful,
from Asymptotic Representation Theory, through lozenge tilings, to Random
Matrices, see e.g. [BG15, GP15, BGH] and references therein.

Plethysm coefficients can also be studied using symmetric functions, yet again
positivity properties cannot usually be derived this way. For example in
[DIP19] symmetric functions were used to derive some explicit formulas for
$a_{\lambda}(d[n])$ with $\lambda$ a three row partition, and later this
method generalized in [FI20] to exhibit an alternating formula and put them in
GapP.

A technique to show positivity is the construction of explicit highest weight
tableau evaluations, see [Ful00], which is easier for plethysms but also
applicable for Kroneckers. For example, this technique was used in [I15] to
prove Theorem 5.4, generalized in [LS17], and in [BIP19] to show positive
plethysm coefficients.

Useful tools in Representation Theory are induction and restriction of
modules, passing to the representation theory of other groups. For example,
the character bound 5.3 was obtained by restricting to the alternating group
$A_{n}\subset S_{n}$, see [BB04, PPV16, PP17a]. Similar methods were developed
to extract positivity criteria working with representations over finite
fields, see e.g. [BBL]. In another direction, diagram algebras can also be
used to study Kronecker, see e.g. [BDO15], and plethysm coefficients, see e.g.
[COSSZ22, OSSZ].

Another useful approach comes from discrete geometry. This is not at all
surprising given that many objects in representation theory correspond to
integer points in polytopes, e.g. SSYTs are integer points in Gelfand-Tsetlin
polytopes, see e.g. [DM06] for some complexity connections also. Vallejo used
such relations to develop methods of discrete tomography and find a lower
bound for Kronecker coefficients via pyramids, see [Val97, Val99, IMW17].
Kronecker coefficients are bounded above by 3d contingency tables with given
2d marginals, as seen in [IMW, PP20a] to obtain upper bounds. Similar
expressions tying them to Kostant partition functions were developed in
[MRS21] and used in [MT] to find asymptotics.

Finally, Computational Complexity theory provides some tools besides the
framework. The framework is to explain the hardness of the problems and what
possible answers to expect. The tools come in the form of gadgets and basic
hard/complete problems to reduce to like 3SAT, PerfectMatching, SetPartition
etc. Embedding such a complete problem in our problem is an art, very similar
to finding injections, see e.g. [GJ79] for some classical results. Other tools
come from algebraic complexity and GCT, where the complexity of certain
polynomials could imply inequalities between the relevant structure constants.

Despite the variety of questions, methods and applications, the Kronecker and
plethysm coefficients are still a mysterious black box. It sometimes gives us
presents. But we cannot see inside… just yet.

## References

  * [Aar16] S. Aaronson, ${{\rm{\textsf{P}}}}\overset{?}{=}{{\rm{\textsf{NP}}}}$, in _Open problems in mathematics_ , Springer, Cham, 2016, 1–122.
  * [BO05] C. Ballantine, R. Orellana, A combinatorial interpretation for the coefficients in the Kronecker product $s_{(n-p,p)}*s_{\lambda}$. _Sém. Lothar. Combin._ 54A (2005/07), 29 pp.
  * [BGH] S. Belinschi, A. Guionnet, J. Huang, Large deviation principles via spherical integrals, _Prob. Math. Phys._ 3 (3) (2022), pp. 543–625.
  * [BB04] C. Bessenrodt and C. Behns, On the Durfee size of Kronecker products of characters of the symmetric group and its double covers, J. Algebra 280 (2004), 132–144.
  * [BB17] C. Bessenrodt, C. Bowman, Multiplicity-free Kronecker products of characters of the symmetric groups. _Adv. Math._ 322 (2017), pp. 473–529.
  * [B18] C. Bessenrodt, Critical classes, Kronecker products of spin characters, and the Saxl conjecture, _Alg. Combinatorics_ 1 (2018), 353–369.
  * [BBL] C. Bessenrodt, C. Bowman, L. Sutton, Kronecker positivity and 2-modular representation theory, _Trans. Amer. Math. Soc. Ser. B_ 8(2021), 1024–1055.
  * [BBR06] F. Bergeron, R. Biagioli and M. H. Rosas, Inequalities between Littlewood–Richardson coefficients, _J. Combin. Theory, Ser. A_ 113 (2006), 567–590.
  * [Bia98] Ph. Biane, Representations of Symmetric Groups and Free Probability, _Adv. Math._ 138 (1998), 126–181.
  * [B13] J. Blasiak, Kronecker coefficients for one hook shape,_Sém. Lothar. Combin_ , 77:2016–2017.
  * [BL18] J. Blasiak, R.I. Liu, Kronecker coefficients and noncommutative super Schur functions. _J. Combin. Theory Ser. A_ 158 (2018), 315–361.
  * [BMS15] J. Blasiak, K. Mulmuley, M. Sohoni, Geometric complexity theory IV: nonstandard quantum group for the Kronecker problem. _Mem. Amer. Math. Soc._ 235 (2015), no. 1109.
  * [BI18] M. Bläser and C. Ikenmeyer, _Introduction to geometric complexity theory_ , Summer school lecture notes, 2018, 148 pp.; https://tinyurl.com/nhe2wxvw
  * [BDO15] C. Bowman, M. De Visscher, R. Orellana, The partition algebra and the Kronecker coefficients. _Trans. Amer. Math. Soc._ 367 (2015), no. 5, 3647–3667.
  * [BOR11] E. Briand, R. Orellana and M. Rosas, The stability of the Kronecker product of Schur functions, _J. Algebra_ 331 (2011), 11–27.
  * [Bri93] M. Brion, Stable properties of plethysm: on two conjectures of Foulkes, _Manuscripta mathematica_ (1993), 80:347–371.
  * [BG15] A. Bufetov, V. Gorin, Representations of classical Lie groups and quantized free convolution. _Geom. Funct. Anal._ 25, 763–814 (2015).
  * [Bür00a] P. Bürgisser, _Completeness and reduction in algebraic complexity theory_ , Springer, Berlin, 2000, 168 pp.
  * [Bür00b] P. Bürgisser, Cook’s versus Valiant’s hypothesis, _Theor. Comp. Sci._ 235 (2000), 71–88.
  * [BCS97] P. Bürgisser, M. Clausen and M. A. Shokrollahi, _Algebraic complexity theory_ , Springer, Berlin, 1997.
  * [BI08] P. Bürgisser, C. Ikenmeyer, The complexity of computing Kronecker coefficients. _20th Annual International Conference on Formal Power Series and Algebraic Combinatorics_ (FPSAC 2008), pp. 357–368.
  * [BIP19] P. Bürgisser, C. Ikenmeyer and G. Panova, No occurrence obstructions in geometric complexity theory, _J. Amer. Math. Society_ 32 (2019), 163–193; extended abstract in _57-th FOCS_ (2016), IEEE, Los Alamitos, CA, 386–5.
  * [BLMW11] P. Bürgisser, J. M. Landsberg, L. Manivel and J. Weyman, An overview of mathematical issues arising in the Geometric Complexity Theory approach to ${{\rm{\textsf{VP}}}}\overset{?}{=}{{\rm{\textsf{VNP}}}}$, _SIAM J. Comput._ 40 (2011), 1179–1209.
  * [CHM07] M. Christandl, A. Harrow, G. Mitchison, Nonzero Kronecker coefficients and what they tell us about spectra. _Comm. Math. Phys._ 270 (2007), no. 3, pp.575–585.
  * [CDW12] M. Christandl, B. Doran and M. Walter, Computing Multiplicities of Lie Group Representations, in _Proc. 53-rd FOCS_ (2012), IEEE, 639–648.
  * [COSSZ22] L. Colmenarejo, R. Orellana, F. Saliola, . Schilling, M. Zabrocki, The mystery of plethysm coefficients, https://arxiv.org/abs/2208.07258 (2022).
  * [CR15] L. Colmenarejo and M. Rosas, Combinatorics on a family of reduced Kronecker coefficients, _C.R. Math. Acad. Sci. Paris_ 353 (2015), no. 10, 865–869.
  * [DM06] J. A. De Loera and T. B. McAllister, On the computation of Clebsch–Gordan coefficients and the dilation effect, _Experimental Math._ 15 (2006), 7–19.
  * [D93] Y. Dvir, On the Kronecker product of $S_{n}$ characters, _J. Algebra_ 154 (1993), 125–140.
  * [DIP19] J. Dörfler, C. Ikenmeyer and G. Panova, On geometric complexity theory: Multiplicity obstructions are stronger than occurrence obstructions in _Proc. 46-th ICALP_ (2019), Art. 51, 14 pp. i
  * [FI20] N. Fischer and C. Ikenmeyer, The computational complexity of plethysm coefficients, _Comput. Complexity_ 29 (2020), no. 2, Paper 8, 43 pp.
  * [FRT54] J. S. Frame, G. de B. Robinson and R. M. Thrall, The hook graphs of the symmetric group, Canad. J. Math. 6 (1954), 316–324.
  * [Ful97] W. Fulton, _Young tableaux_ , Cambridge Univ. Press, Cambridge, UK, 1997, 260 pp.
  * [Ful00] W. Fulton, Eigenvalues, invariant factors, highest weights, and Schubert calculus, _Bull. AMS_ 37 (2000), 209–249.
  * [GJ79] M. R. Garey and D. S. Johnson, _Computers and intractability_ , Freeman, San Francisco, CA, 1979.
  * [GR85] A. M. Garsia and J. Remmel, Shuffles of permutations and the Kronecker product, _Graphs and Combinatorics_ (1985), 1:217-263.
  * [GIP17] F. Gesmundo, C. Ikenmeyer and G. Panova, Geometric complexity theory and matrix powering, _Diff. Geom. Applications_ 55 (2017), 106–127.
  * [GP15] V. Gorin and G. Panova, Asymptotics of symmetric polynomials with applications to statistical mechanics and representation theory, _Ann. Probab._ 43 (2015), 3052–3132.
  * [HR22] N. Harman, C. Ryba, A Tensor-Cube Version of the Saxl Conjecture, arXiv:2206.13769 .
  * [HSTZ13] G. Heide, J. Saxl, P. H. Tiep, A. Zalesski, Conjugacy action, induced representations and the Steinberg square for simple groups of Lie type, _Proc. Lond. Math. Soc._ (3) 106 (2013), no. 4, 908–930.
  * [I15] C. Ikenmeyer, The Saxl conjecture and the dominance order, _Disc. Math._ (11) 6 (2015), pp.1970–1975.
  * [IMW17] C. Ikenmeyer, K. D. Mulmuley and M. Walter, On vanishing of Kronecker coefficients, _Computational Complexity_ 26 (2017), 949–992.
  * [IP22] C. Ikenmeyer and I. Pak, What is in #P and what is not?, preprint (2022), 82 pp.; extended abstract to appear in _Proc. 63rd FOCS_ (2022); arXiv:2204.13149.
  * [IPP22] C. Ikenmeyer, I. Pak and G. Panova, Positivity of the symmetric group characters is as hard as the polynomial time hierarchy, preprint (2022), 15 pp.; extended abstract to appear in _Proc. 34th SODA_ (2023); arXiv:2207.05423.
  * [IP17] C. Ikenmeyer and G. Panova, Rectangular Kronecker coefficients and plethysms in geometric complexity theory, _Adv. Math._ 319 (2017), 40–66; extended abstract in _57th FOCS_ (2016), IEEE, Los Alamitos, CA, 396–4055.
  * [IP23] C. Ikenemeyer and G. Panova, All Kronecker coefficients are reduced Kronecker coefficients, (2023).
  * [Kir04] A. N. Kirillov, An invitation to the generalized saturation conjecture, _Publ. RIMS_ 40 (2004), 1147–1239.
  * [Kly04] A. Klyachko, Quantum marginal problem and representations of the symmetric group, arXiv:quant-ph/0409113.
  * [KT99] A. Knutson and T. Tao, The honeycomb model of $\mathrm{GL}_{n}(\mathbb{C})$ tensor products I: Proof of the saturation conjecture, J. AMS 12 (1999), 1055–1090.
  * [Las79] A. Lascoux, Produit de Kronecker des représentations du groupe symétrique. _Séminaire dÀlgèbre Paul Dubreil et Marie-Paule Malliavin: Proceedings_ , Paris 1979 (32ème Année), pages 319–329 (1979).
  * [L21] Xin Li, Saxl Conjecture for triple hooks, _Discrete Math._ 344 (2021) 6.
  * [Liu17] Ricky Liu, A simplified Kronecker rule for one hook shape, _Proc. Amer. Math. Soc._(2017), 145(9):3657-3664.
  * [LoS] B. F. Logan and L. A. Shepp, A variational problem for random Young tableaux, _Adv. Math._ 26 (1977), 206–222.
  * [LS17] S. Luo,M. Sellke, The Saxl conjecture for fourth powers via the semigroup property. _J. Algebraic Combin._ 45 (2017), no. 1, 33–80.
  * [Mac95] I. G. Macdonald, _Symmetric functions and Hall polynomials_ (Second edition), Oxford University Press, New York, 1995.
  * [Man15] L Manivel, On the asymptotics of Kronecker coefficients, _J. Alg. Combinatorics_(2015), 42(4):999-1025.
  * [MPP19a] S. Melczer, G. Panova and R. Pemantle, Counting partitions inside a rectangle, _SIAM J. Discrete Math._ 34 (2020), 2388–2410; extended abstact in Proc. 31st FPSAC, 2019.
  * [MRS21] M. Mishna, M. Rosas, S. Sundaram, Vector partition functions and Kronecker coefficients, _J. Phys. A: Math. Theor._ (2021) 54.
  * [MT] M. Mishna, S. Trandafir, Estimating and computing Kronecker Coefficients: a vector partition function approach, arXiv:2210.12128.
  * [Mul11] K. D. Mulmuley, Geometric Complexity Theory VI: The flip via positivity, preprint (2011), 40 pp., available at http://gct.cs.uchicago.edu/gct6.pdf; cf. arXiv:0704.0229, 139 pp.
  * [Mul17] K. Mulmuley, Geometric Complexity Theory V. Efficient algorithms for Noether normalization, _J. AMS_ 30 (2017), 225–309.
  * [MNS12] K. D. Mulmuley, H. Narayanan and M. Sohoni, Geometric complexity theory III. On deciding nonvanishing of a Littlewood-Richardson coefficient, _J. Algebraic Combin._ 36 (2012), 103–110.
  * [MS01] K. D. Mulmuley and M. Sohoni, Geometric complexity theory. I An approach to the P vs. NP and related problems, SIAM J. Comput. 31, 2001, 496–526.
  * [MS08] K. D. Mulmuley and M. Sohoni, Geometric complexity theory. II Towards explicit obstructions for embeddings among class varieties, SIAM J. Comput. 38, 2008, 1175–1206.
  * [Mur38] F. D. Murnaghan, The analysis of the Kronecker product of irreducible representations of the symmetric group, _Amer. J. Math._ 60 (1938), 761–784.
  * [Mur56] F. D. Murnaghan, On the Kronecker product of irreducible representations of the symmetric group, _Proc. Natl. Acad. Sci. USA_ 42 (1956), 95–98.
  * [Nar06] H. Narayanan, On the complexity of computing Kostka numbers and Littlewood–Richardson coefficients, _J. Algebraic Combin._ 24 (2006), 347–354.
  * [OSSZ] R. Orellana, F. Saliola, A. Schilling, M. Zabrocki, Plethysm and the algebra of uniform block permutations, _Alg. Combinatorics_ 5 (2022) (5), pp. 1165–1203.
  * [OZ20] R. Orellana, M. Zabrocki, A combinatorial model for the decomposition of multivariate polynomials rings as an $S_{n}$-module _The Elect. Journal of Comb._ 27(3) (2020), #P3.24.
  * [OZ21] R. Orellana, M. Zabrocki, Symmetric group characters as symmetric functions _Adv. Math._ 390 (2021).
  * [Pak22+] I. Pak, What is a combinatorial interpretation?, preprint (2022), 58 pp.; to appear in _Proc. OPAC_ , AMS, Providence, RI.
  * [PP13] I. Pak and G. Panova, Strict unimodality of $q$-binomial coefficients, _C. R. Math. Acad. Sci. Paris_ 351 (2013), 415–418.
  * [PP14] I. Pak and G. Panova, Unimodality via Kronecker products, _J. Algebraic Combin._ 40 (2014), 1103–1120.
  * [PP17a] I. Pak, G. Panova, Bounds on certain classes of Kronecker and q-binomial coefficients, _Journal of Combinatorial Theory, Series A_ 147 (2017), pp.1–17.
  * [PP17b] I. Pak and G. Panova, On the complexity of computing Kronecker coefficients, _Comput. Complexity_ 26 (2017), 1–36.
  * [PP20a] I. Pak and G. Panova, Bounds on Kronecker coefficients via contingency tables, _Linear Alg. Appl._ 602 (2020), 157–178.
  * [PP20b] I. Pak, G. Panova, Breaking down the reduced Kronecker coefficients, _Comptes Rendus. Mathématique_ 358 (4), 463-468
  * [PP23] I. Pak, G. Panova, Durfee squares, symmetric partitions and bounds on Kronecker coefficients, _J. Algebra_ (2023), to appear.
  * [PPV16] I. Pak, G. Panova, E. Vallejo, Kronecker products, characters, partitions, and the tensor square conjectures, _Advances in Mathematics_ 288 (2016), pp.702–731.
  * [PPY19a] I. Pak, G. Panova and D. Yeliussizov, On the largest Kronecker and Littlewood–Richardson coefficients, _J. Combin. Theory, Ser. A_ 165 (2019), 44–77.
  * [Pan15] G. Panova, Kronecker coefficients: combinatorics, complexity and beyond, AMS-EMS meeting, Porto, Portugal (2015), slides at https://tinyurl.com/bdd4w3pj
  * [Pan23] G. Panova, Computational Complexity in Algebraic Combinatorics, _Current Developments in Mathematics_ , Harvard University (2023).
  * [RW94] J. Remmel, T. Whitehead, On the Kronecker product of Schur functions of two row shapes. _Bull. Belg. Math. Soc. Simon Stevin_ 1(1994), no. 5, 649–683.
  * [Sag01] B. E. Sagan, _The symmetric group_ (Second ed.), Springer, New York, 2001.
  * [SS16] S. V. Sam and A. Snowden, _Proof of Stembridge’s conjecture on stability of Kronecker coefficients_ , _J. Alg. Combinatorics_(2016), 43(1):1-10.
  * [Sta99] R. P. Stanley, Enumerative Combinatorics, vol. 1 (Second ed.) and 2, Cambridge Univ. Press, 2012 and 1999.
  * [Sta00] R. P. Stanley, Positivity problems and conjectures in algebraic combinatorics, in _Mathematics: frontiers and perspectivies_ , AMS, Providence, RI, 2000, 295–319.
  * [Sta20] R. P. Stanley, Supplementary Excercies to [Sta99], available at http://www-math.mit.edu/~rstan/ec.
  * [T15] V. Tewari, Kronecker coefficients for some near-rectangular partitions, _J. Algebra_ (2015) 429, p. 287–317.
  * [V79a] L. G. Valiant, Completeness classes in algebra. _Proc. 11th STOC_ (1979), 249–261.
  * [V79b] L. G. Valiant, The complexity of computing the permanent. _Theor. Comp. Sci._ 8 (1979), 189–201.
  * [Val97] E. Vallejo, Reductions of additive sets, sets of uniqueness and pyramids, _Discrete Math._ 173 (1997), 257–267.
  * [Val99] E. Vallejo, Stability of Kronecker products of irreducible characters of the symmetric group, _Electron. J. Combin._ 6 (1999), RP 39, 7 pp.
  * [VK] A. M. Vershik and S. V. Kerov, Asymptotic of the largest and the typical dimensions of irreducible representations of a symmetric group, _Funct. Anal. Appl._ 19 (1985), 21–31.
  * [Wig19] A. Wigderson, _Mathematics and Computation_ , monograph draft, 2019.