# The complexity of computing Kronecker coefficients

Peter Bürgisser† and Christian Ikenmeyer

Institute of Mathematics, University of Paderborn, 33095 Paderborn, Germany

**Abstract.** Kronecker coefficients are the multiplicities in the tensor product decomposition of two irreducible representations of the symmetric group $S_n$. They can also be interpreted as the coefficients of the expansion of the internal product of two Schur polynomials in the basis of Schur polynomials. We show that the problem KRONCOEFF of computing Kronecker coefficients is very difficult. More specifically, we prove that KRONCOEFF is #P-hard and contained in the complexity class GapP. Formally, this means that the existence of a polynomial time algorithm for KRONCOEFF is equivalent to the existence of a polynomial time algorithm for evaluating permanents.

**Résumé.** Les coefficients de Kronecker sont les multiplicités dans la décomposition du produit tensoriel de deux représentations irréductibles du groupe symétrique. On peut aussi les voir comme les coefficients du développement du produit interne des polynômes de Schur. Nous montrons que le problème KRONCOEFF de calculer les coefficients de Kronecker est très difficile. Plus précisément, nous prouvons que KRONCOEFF est #P-dur et que KRONCOEFF est dans la classe de complexité GapP. Cela veut dire qu'il existe un algorithme pour KRONCOEFF s'exécutant en temps polynomial si et seulement s'il existe un algorithme pour l'évaluation du permanent s'exécutant en temps polynomial.

**Keywords:** representations of symmetric groups, tensor products, Kronecker coefficients, computational complexity

## 1 Introduction

It is well known that the irreducible representations of the symmetric group $S_n$ on $n$ letters (in characteristic zero) can be indexed by the partitions $\lambda \vdash n$ of $n$, cf. Sagan (2001). Let $\mathcal{S}_\lambda$ denote the irreducible module corresponding to $\lambda$ (Specht module). For given partitions $\lambda, \mu, \nu \vdash n$ the Kronecker coefficient $g_{\lambda\mu\nu}$ is defined as the multiplicity of $\mathcal{S}_\nu$ in the tensor product $\mathcal{S}_\mu \otimes \mathcal{S}_\nu$. It is thus a nonnegative integer. If $\chi^\lambda$ denotes the irreducible character of $\mathcal{S}_\lambda$, then the Kronecker coefficients $g_{\lambda\mu\nu}$ are determined by the expansion

$$ \chi^{\lambda} \chi^{\mu} = \sum_{\nu \vdash n} g_{\lambda \mu \nu} \chi^{\nu}. \qquad (1) $$

We note that $g_{\lambda\mu\nu}$ is invariant under permuting the indices $\lambda, \mu, \nu$. Related to this are the Littlewood-Richardson coefficients $c_{\lambda\mu\nu}^\lambda$, which can be characterized by the expansion of the product of two Schur

<footnote>†Partially supported by DFG grant BU 1371/2-1.</footnote>
functions $s_\mu s_\nu$ in the basis of Schur functions:

$$s_{\mu\nu} = \sum_{\lambda \vdash |\mu| + |\nu|} c_{\mu\nu}^{\lambda} s_{\lambda}. \qquad (2)$$

It is well known that the coefficients $c_{\mu\nu}^{\lambda}$ describe the multiplicities in the tensor product decomposition of irreducible representations of the general linear group $GL(n, \mathbb{C})$.

These coefficients play an important role in various mathematical disciplines (combinatorics, representation theory, algebraic geometry; cf. Fulton (1997)) as well as in quantum mechanics. However, our interest in the tensor product multiplicities stems from lower bound questions in computational complexity. Early work by Strassen (1983) pointed out that a good understanding of the Kronecker coefficients could lead to complexity lower bounds for bilinear maps, notably matrix multiplication. The idea is to get information about the irreducible constituents of the vanishing ideal of secant varieties to Segre varieties, for recent results we refer to Landsberg and Manivel (2004).

Kronecker coefficients also play a crucial role in the geometric complexity theory of Mulmuley and Sohoni (2001, 2006). This is an approach to arithmetic versions of the famous P vs. NP problem and related questions in computational complexity via geometric representation theory. What has been achieved so far is a series of reductions from orbit closure problems to subgroup restriction problems. The latter involve the problems of deciding in specific situations whether multiplicities $g_{\lambda\mu\nu}$ or $c_{\mu\nu}^{\lambda}$ are positive. However, until very recently, no efficient algorithms were known for the general problem of deciding the positivity of such multiplicities.

The well-known Littlewood-Richardson rule gives a combinatorial description of the numbers $c_{\mu\nu}^{\lambda}$ and also leads to algorithms for computing them. All of these algorithms take exponential time in the size of the input partitions (consisting of integers encoded in binary notation). However, quite surprisingly, the positivity of $c_{\mu\nu}^{\lambda}$ can be decided by a polynomial time algorithm! This follows from the proof of the Saturation conjecture (Knutson and Tao, 1999), as pointed out by Mulmuley and Sohoni (2005). On the other hand, Narayanan (2006) proved that the computation of $c_{\mu\nu}^{\lambda}$ is a #P-complete problem. Hence there does not exist a polynomial time algorithm for computing $c_{\mu\nu}^{\lambda}$ under the widely believed hypothesis $P \neq NP$.

Much less is known about the Kronecker coefficients $g_{\lambda\mu\nu}$. Lascoux (1980), Remmel (1989, 1992), Remmel and Whitehead (1994) and Rosas (2001) gave combinatorial interpretations of the Kronecker coefficients of partitions indexed by two row shapes or hook shapes. Very recently, Ballantine and Orellana (2005/07) managed to describe $g_{\lambda\mu\nu}$ in the case where $\mu = (n-p, p)$ has two row shape and the diagram of $\lambda$ is not contained inside the $2(p-1) \times 2(p-1)$ square. Except for these special cases, a combinatorial interpretation of the numbers $g_{\lambda\mu\nu}$ is still lacking. Given this sad state of affair, it is not surprising that it is generally believed that the computation of Kronecker coefficients is a very difficult problem.

Our main result confirms this belief and gives a rigorous and precise meaning to it. We prove that the problem KRONCOEFF of computing the Kronecker coefficient $g_{\lambda\mu\nu}$ for given partitions $\lambda, \mu, \nu$ (consisting of integers encoded in binary notation) is hard for the counting complexity class #P. (For general information about complexity theory we refer to Papadimitriou 1994.) This implies that there does not exist a polynomial time algorithm for KRONCOEFF under the widely believed hypothesis $P \neq NP$.

We do not know whether KRONCOEFF is contained in the class #P. In fact, the latter would just express that $g_{\lambda\mu\nu}$ counts a number of appropriate combinatorial objects (and it can be decided in polynomial time whether a given object is appropriate). However, we can show that $g_{\lambda\mu\nu}$ can be written as the difference
<figure><img src="image_1.png" /><figcaption>**Fig. 1:** Young diagrams and skew diagrams</figcaption></figure>

of two functions in $\#P$, that is, KRONCOEFF belongs to the complexity class GapP.

Summarizing, we have:

**Theorem 1** *The problem KRONCOEFF of computing Kronecker coefficients is GapP-complete. Hence the existence of a polynomial time algorithm for KRONCOEFF is equivalent to the existence of a polynomial time algorithm for evaluating permanents of matrices with entries in $\{0, 1\}$.*

A few word about the proofs. Using the description of $g_{\lambda\mu\nu}$ in Ballantine and Orellana (2005/07) we reduce the computation of Kostka numbers to the subproblem of KRONCOEFF where one of the partitions has two row shape. The $\#P$-hardness then follows from Narayanan (2006). For the upper bound, we show that a well-known method (see Remmel 1989), which combines a formula of Garsia and Remmel (1985) with the Jacobi-Trudi identity, leads to an algorithm placing KRONCOEFF into the complexity class GapP.

Of course, the tantalizing question is whether the positivity of Kronecker coefficients can be decided in polynomial time. In Mulmuley (2007) it is conjectured that is in fact the case.

# 2 Preliminaries and notation

For more information on tableaux and symmetric functions we refer to Stanley (1999, Chap. 7).

## 2.1 Skew diagrams and tableaus

A *Young diagram* is a collection of boxes, arranged in left justified rows, such that from top to bottom, the number of boxes in a row is monotonically (weakly) decreasing. For $\lambda := (\lambda_1, \dots, \lambda_s) \subseteq \mathbb{N}^s$ we define its length as $\ell(\lambda) := \max\{i|\lambda_i > 0\}$ and its size as $|\lambda| := \sum_{i=1}^{\ell(\lambda)} \lambda_i$. Moreover we set $\lambda_r := 0$ for all $r > s$. If the $\lambda_i$ are monotonically weakly decreasing and $|\lambda| = n$, then we call $\lambda$ a *partition* of $n$ and write $\lambda \vdash n$. In this case, $\lambda$ specifies a Young diagram consisting of $n$ boxes, with $\lambda_i$ boxes in the $i$th row for all $i$ (see Figure 1(a)). To any partition $\lambda$ there corresponds its *conjugate partition* $\lambda'$ which is obtained by transposing the Young diagram of $\lambda$, that is, reflecting it at the main diagonal (see Figure 1(b)). We note that every row in $\lambda$ corresponds to a column in $\lambda'$ and vice versa. Moreover, $|\lambda| = |\lambda'|$.

A *skew diagram* is the set of boxes obtained by removing a smaller Young diagram from a larger one (see Figure 1(c)). If we remove $\alpha \subseteq \lambda$ from $\lambda$, then we denote the resulting skew diagram by $\lambda/\alpha$ and
<figure><img src="image_2.png" /><figcaption>Fig. 2: The skew diagram of the product $(3, 2)/(1) * (3, 2, 2)/(2, 1)$.</figcaption></figure>

<figure><img src="image_3.png" /><figcaption>**Fig. 3:** A semistandard skew tableau of shape $(5, 3, 3, 1)/(2, 1)$ and type $(1, 4, 3, 1)$. Its reverse reading word is $(3, 2, 1, 2, 2, 3, 3, 2, 4)$, which is not a lattice permutation, but an $\alpha$-lattice permutation for $\alpha = (4, 1)$.</figcaption></figure>

say that it has the shape $\lambda/\alpha$. Note that for a given skew diagram $\lambda/\alpha$, the partitions $\alpha$ and $\lambda$ need not be uniquely defined (see Figure 1(d)). Every Young diagram is a skew diagram, as one can choose $\alpha$ to be the empty set of boxes. The product $\lambda/\alpha * \tilde{\lambda}/\tilde{\alpha}$ of two skew diagrams $\lambda/\alpha$ and $\tilde{\lambda}/\tilde{\alpha}$ is defined to be the skew diagram obtained by attaching the upper right corner of $\lambda$ to the lower left corner of $\tilde{\lambda}$ (see Figure 2). A similar definition applies for more than one factor.

A filling of a skew diagram $\lambda/\alpha$ is a numbering of its boxes with (not necessarily distinct) positive integers. A semistandard skew tableau $T$ of shape $\lambda/\alpha$ is defined to be a filling of $\lambda/\alpha$ such that the entries are weakly increasing from left to right across each row, and strictly increasing from top to bottom, down each column. If $T$ houses $\mu_j$ copies of $j$ for $j \le t$, then the tableau $T$ is said to have the type $\mu := (\mu_1, \dots, \mu_t)$ (see Figure 3). Note that $|\lambda| - |\alpha| = |\mu|$, but in contrast to $\lambda$ and $\alpha$, $\mu$ need not be weakly decreasing. A semistandard Young tableau of shape $\lambda$ is defined to be a semistandard skew tableau of shape $\lambda/\alpha$, where $\alpha$ is the empty partition. The Kostka number $K_{\lambda\mu}$ is defined to be number of semistandard Young tableaux of shape $\lambda$ and type $\mu$.

The reverse reading word $w^-$ of a skew tableau $T$ is the sequence of entries in $T$ obtained by reading the entries from right to left and top to bottom, starting with the first row. A *lattice permutation* is a sequence $(a_1, a_2, \dots, a_n)$ such that in any prefix segment $(a_1, a_2, \dots, a_p)$ the number of $i$'s is at least as large as the number of $(i+1)$'s for all $i$ (see Figure 3).

## 2.2 Schur functions and Kronecker product

Given a semistandard skew tableau $T$ of shape $\lambda/\alpha$, we define its weight $w(T)$ to be the monomial obtained by replacing each entry $i$ of $T$ by the variable $x_i$ and taking the product over all boxes. In other words, $w(T) = x_1^{\mu_1} \cdots x_t^{\mu_t}$, where $(\mu_1, \dots, \mu_t)$ is the type of $T$. The skew Schur function $s_{\lambda/\alpha}$ is defined to be the polynomial

$$s_{\lambda/\alpha} = \sum_{T} w(T),$$
where the sum runs over all semistandard skew tableau $T$ of shape $\lambda/\alpha$. We will interpret $s_{\lambda/\alpha}$ as a polynomial in the variables $x_1, \dots, x_n$, where $n \ge |\lambda|$ (the actual choice of $n$ is not important). The usual Schur function $s_\lambda$ is defined as $s_{\lambda/\emptyset}$. It is immediate from the definition that $s_{\lambda/\alpha * \tilde{\lambda}/\tilde{\alpha}} = s_{\lambda/\alpha} s_{\tilde{\lambda}/\tilde{\alpha}}$. An important special case of Schur functions are the complete symmetric functions defined as $h_k := s_\lambda$ corresponding to the partition $\lambda = (k)$ for $k \in \mathbb{N}$ (one sets $h_0 := 1$). Moreover, for a partition $\lambda = (\lambda_1, \dots, \lambda_\ell)$ one sets $h_\lambda := h_{\lambda_1} \cdots h_{\lambda_\ell}$. It is well known that both the families $(s_\lambda)$ and $(h_\lambda)$ form a $\mathbb{Z}$-basis of the ring $\Lambda$ of symmetric functions in $n$ variables and that the transition matrix is given by the Kostka numbers.

We recall that the Littlewood-Richardson coefficient $c_{\mu\nu}^{\lambda}$ is the coefficient of $s_\lambda$ in the expansion of $s_\mu s_\nu$ in the basis of Schur functions, cf. Equation (2). The famous Littlewood-Richardson rule states that $c_{\mu\nu}^{\lambda}$ equals the number of semistandard skew tableaus of shape $\lambda/\mu$ and type $\nu$, whose reverse reading word is a lattice permutation.

Recall the definition of the Kronecker coefficient $g_{\lambda\mu\nu}$ as the coefficient of $\chi^\nu$ in the expansion of the product of irreducible characters $\chi^\lambda \chi^\mu$ of $S_n$, cf. Equation (1). The Kronecker (or internal) product of $s_\lambda$ and $s_\mu$, for $\lambda, \mu \vdash n$, is defined by

$$s_{\lambda} * s_{\mu} = \sum_{\nu \vdash n} g_{\lambda\mu\nu} s_{\nu}$$

(cf. Stanley 1999, Ex. 7.78). This extends to a commutative and associative product on $\Lambda$. In order to see this, one notes that the characteristic map $ch$ defined by $ch(\chi^\lambda) = s_\lambda$ is a linear isomorphism from the space of class functions on $S_n$ to the space of homogeneous symmetric functions of degree $n$ in $n$ variables. We have $s_\lambda * h_n = s_\lambda$ for all $\lambda \vdash n$.

In the following we will briefly present the main result from Ballantine and Orellana (2005/07). Let $k^l$ denote the sequence consisting of $l$ occurrences of $k$. Let $\alpha = (\alpha_1, \alpha_2, \dots, \alpha_l)$ be a partition. A sequence $a = (a_1, a_2, \dots, a_n)$ is called an $\alpha$-lattice permutation if the concatenation $(1^{\alpha_1} 2^{\alpha_1} \cdots n^{\alpha_n} a)$ is a lattice permutation (see Figure 3). As the concatenation of two lattice permutations is a lattice permutation, the concatenation $ab$ of an $\alpha$-lattice permutation $a$ and a lattice permutation $b$ is an $\alpha$-lattice permutation.

The following definition is from Ballantine and Orellana (2005/07).

**Definition 2 (Kronecker-Tableau)** Let the $\lambda, \alpha, \nu$ be partitions such that $\alpha \subseteq \lambda \cap \nu$ and let $T$ be a semistandard skew tableau $T$ of shape $\lambda/\alpha$ and type $\nu - \alpha$. We call $T$ a Kronecker Tableau iff its reverse reading word is an $\alpha$-lattice permutation and one of the following three conditions is satisfied:

* $\alpha_1 = \alpha_2$

* $\alpha_1 > \alpha_2$ and the number of 1's in the second row of $T$ is exactly $\alpha_1 - \alpha_2$,

* $\alpha_1 > \alpha_2$ and the number of 2's in the first row of $T$ is exactly $\alpha_1 - \alpha_2$.

We denote by $k_{\alpha\nu}^{\lambda}$ the number of Kronecker-Tableaux of shape $\lambda/\alpha$ and type $\nu - \alpha$.

Ballantine and Orellana (2005/07) showed the following.

**Theorem 3** Suppose $\mu = (n-p,p)$, $\lambda \vdash n$, $\nu \vdash n$ such that $n \ge 2p$ and $\lambda_1 \ge 2p-1$. Then we have

$$g_{\lambda,\mu,\nu} = g_{\lambda,(n-p,p),\nu} = \sum_{\substack{\beta \vdash p \\ \beta \subseteq \lambda \cap \nu}} k_{\beta\nu}^{\lambda}.$$
## 2.3 Counting complexity classes

For information about complexity theory we refer to Papadimitriou (1994). In order to characterize the complexity of counting problems, Valiant (1979) introduced the complexity class #P (pronounced sharp P), which consists of the functions $f: \{0, 1\}^* \to \mathbb{N}$ such that there exists a polynomial $p$ and a Turing machine $M$ working in polynomial time such that, for all $n \in \mathbb{N}$ and all $w \in \{0, 1\}^n$,

$$f(w) = |\{z \in \{0, 1\}^{p(n)} | M \text{ accepts } (w, z)\}|.$$

For instance, the problem of computing the Kostka numbers $K_{\lambda\mu}$ is in #P (see Narayanan (2006) for details).

We compare the complexity of functions $f, g: \{0, 1\}^* \to \mathbb{N}$ by means of reductions. We say that $f$ reduces many-one to $g$ iff there exists a polynomial time computable function $\varphi: \{0, 1\}^* \to \{0, 1\}^*$ and a polynomial time computable function $\psi: \mathbb{N} \to \mathbb{N}$ such that $f(w) = \psi(g(\varphi(w)))$ for all $w \in \{0, 1\}^*$. If we may take $\psi = \text{id}_{\mathbb{N}}$, then we say that $f$ reduces parsimoniously to $g$.

A function $g: \{0, 1\}^* \to \mathbb{N}$ is called #P-complete iff $g \in \#P$ and every $f \in \#P$ reduces many-one to $g$. Valiant (1979) proved that the computation of the permanent of a matrix $A \in \{0, 1\}^{m \times m}$ is a #P-complete problem. Besides in combinatorics, important #P-complete problems are known in different areas, such as geometry, knot theory (Jones polynomial), statistical physics, and network reliability, see Welsh (1993) for more information on this.

We note that #P is closed under the formation of products. The class #P is also closed under exponential summation: for the simple proof of the following fact we refer to Fortnow (1997).

**Proposition 4** Let $f: \{0, 1\}^* \to \mathbb{N}$ be in #P and $p$ be a polynomial. Then the function $\{0, 1\}^* \to \mathbb{N}$ mapping $w \in \{0, 1\}^n$ to $\sum_{z \in \{0, 1\}^{p(n)}} f(w, z)$ is also in #P.

The complexity class GapP is defined as the set of functions $f: \{0, 1\}^* \to \mathbb{Z}$ which can be written as the difference of two functions in #P. Similarly as above we have the notions of many-one reduction and GapP-completeness for such functions $f$.

## 3 Upper bound for KRONCOEFF

We shall encode a partition $\lambda = (\lambda_1, \dots, \lambda_l)$ as the sequence of the positive integers $\lambda_i$ encoded in binary; thus the bitsize of $\lambda$ equals $\sum_i (1 + \lfloor \log \lambda_i \rfloor)$. The problem KRONCOEFF is defined as follows:

**KRONCOEFF** Given partitions $\lambda, \mu, \nu \vdash n$, compute the Kronecker coefficient $g_{\lambda\mu\nu}$.

The following result provides the upper bound in Theorem 1.

**Proposition 5** The problem KRONCOEFF is contained in the complexity class GapP.

**Proof:** The proof will use fairly standard ideas, compare Stanley (1999, Chap. 7). We fix $n \in \mathbb{N}$ and denote by $s_\lambda$ the Schur polynomial in the variables $x_1, \dots, x_n$ corresponding to the partition $\lambda \vdash n$. The
Jacobi-Trudi identity expresses $s_λ$ as the following determinant of a structured matrix, whose entries are the complete symmetric functions $h_k$:

$$ 
\begin{aligned}
s_{\lambda} = \det(h_{\lambda_i - i + j})_{1 \le i, j \le n} &= \sum_{\pi \in A_n} \prod_{i=1}^{n} h_{\lambda_i - i + \pi(i)} - \sum_{\pi \in S_n \setminus A_n} \prod_{i=1}^{n} h_{\lambda_i - i + \pi(i)} \\
&=: \sum_{\alpha \vdash n} N_{\alpha\lambda}^{+} h_{\alpha} - \sum_{\alpha \vdash n} N_{\alpha\lambda}^{-} h_{\alpha}.
\end{aligned} 
\quad (3) $$

Here, $N_{\alpha\lambda}^{+}$ counts the even permutations $\pi \in S_n$ such that $\prod_{i=1}^{n} h_{\lambda_i - i + \pi(i)} = h_{\alpha}$. Similarly, $N_{\alpha\lambda}^{-}$ is defined by counting the odd permutations. Hence the functions $(\alpha, \lambda) \mapsto N_{\alpha\lambda}^{+}$ and $(\alpha, \lambda) \mapsto N_{\alpha\lambda}^{-}$ are in the class #P.

A formula of Garsia and Remmel (see also Stanley 1999, Ex. 7.84, p. 478) states that for $\alpha, \mu \vdash n$ with $\ell(\alpha) = \ell$

$$ h_{\alpha} * s_{\mu} = \sum_{D} \prod_{i=1}^{\ell} s_{\mu^i / \mu^{i-1}}, \quad (4) $$

where the sum is over all decompositions $D = (\mu^0, \dots, \mu^\ell)$ of the shape $\mu$ with type $\alpha$, that is, $\emptyset = \mu^0 \subseteq \mu^1 \subseteq \dots \subseteq \mu^\ell = \mu$ with $|\mu^i/\mu^{i-1}| = \alpha_i$ for all $i$. If we denote by $\pi(D)/\rho(D)$ the skew diagram $\mu^1 * \mu^2/\mu^1 * \dots * \mu^\ell/\mu^{\ell-1}$, then $s_{\pi(D)/\rho(D)} = \prod_i s_{\mu^i/\mu^{i-1}}$.

It is well known that the Littlewood-Richardson coefficients appear in the expansion of Schur polynomials of skew diagrams as follows

$$ s_{\pi(D)/\rho(D)} = \sum_{\nu \vdash n} c_{\rho(D)\nu}^{\pi(D)} s_{\nu}. \quad (5) $$

We set $M_{\alpha\mu}^{\nu} := \sum_{D} c_{\rho(D)\nu}^{\pi(D)}$, where the sum is over all decompositions $D$ of the shape $\mu$ with type $\alpha$. The Littlewood-Richardson rule implies that the map $(\pi, \rho, \nu) \mapsto c_{\rho\nu}^{\pi}$ is in the class #P (compare Narayanan 2006). Since #P is closed under exponential summation (Proposition 4), the map $(\alpha, \mu, \nu) \mapsto M_{\alpha\mu}^{\nu}$ lies in #P as well. We conclude from (4) and (5) that

$$ h_{\alpha} * s_{\mu} = \sum_{\nu \vdash n} M_{\alpha\mu}^{\nu} s_{\nu}. $$

By combining this with (3) we obtain

$$ s_{\lambda} * s_{\mu} = \sum_{\nu \vdash n} \left( \sum_{\alpha \vdash n} N_{\alpha\lambda}^{+} M_{\alpha\mu}^{\nu} - \sum_{\alpha \vdash n} N_{\alpha\lambda}^{-} M_{\alpha\mu}^{\nu} \right) s_{\nu}. $$

Hence the expression in the parenthesis equals $g_{\lambda\mu\nu}$. Proposition 4 implies that the map $(\lambda, \mu, \nu) \mapsto \sum_{\alpha \vdash n} N_{\alpha\lambda}^{+} M_{\alpha\mu}^{\nu}$ is in #P. Similarly, $(\lambda, \mu, \nu) \mapsto \sum_{\alpha \vdash n} N_{\alpha\lambda}^{-} M_{\alpha\mu}^{\nu}$ is in #P. Therefore, we have written $(\lambda, \mu, \nu) \mapsto g_{\lambda\mu\nu}$ as the difference of two functions in #P, which means that is is contained in GapP. $\square$
# 4 Lower bound for KRONCOEFF

Narayanan (2006) proved that the following problem KOSTKASUB is #P-complete.

**KOSTKASUB** Given a partition $x = (x_1, x_2) \vdash m$ and $y = (y_1, \dots, y_\ell)$ with $|y| = m$, compute the Kostka number $K_{xy}$.

In order to complete the proof of Theorem 1 it thus suffices to exhibit a many-one reduction from KOSTKASUB to KRONCOEFF. This is established by the following result (which even gives a parsimonious reduction). For an illustration see Figure 4.

**Proposition 6** Let $x = (x_1, x_2) \vdash m$ and $y = (y_1, \dots, y_\ell)$ with $|y| = m > 0$ be given. For $i = 1, \dots, \ell - 1$ we define $\rho_i := \sum_{j>i} y_j$ and we set $p := 3m + \sum_{i=1}^{\ell-1} \rho_i$ and $M := 2p - 1 - m$. Consider

$$ \lambda := (M + m, m + x_1, m + x_2, \underbrace{m, m, \dots, m}_{\ell+3 \text{ times}}, \rho_1, \rho_2, \dots, \rho_{\ell-1}), $$

$$ \nu := (M + 2m, 2m, m + y_1 + \rho_1, m + y_2 + \rho_2, m + y_3 + \rho_3, \dots, m + y_{\ell-1} + \rho_{\ell-1}, m + y_{\ell}). $$

and write $n := |\lambda|$. Then we have $K_{xy} = g_{\lambda, (n-p,p), \nu}$.

<figure><img src="image_4.png" /><figcaption>**Fig. 4:** A Kronecker tableau generated from the input data $x = (7, 3)$, $y = (3, 2, 2, 3)$ according to Proposition 6. We have $m = 10$, $M = 79$.</figcaption></figure>

In the following we assume the notation and setting of Proposition 6. Its proof will proceed by a sequence of Lemmas.
**Lemma 7** We have $\lambda_1 = 2p - 1$ and $n \ge 2p$. Moreover, $\lambda \vdash n$ and $\nu \vdash n$.

**Proof:** The first assertion is obvious. Moreover, one easily checks that $\lambda$ is a partition (note that $M \ge 5m - 1 \ge m$ as $p \ge 3m$). By a straightforward calculation we get

$$|\nu| = M + (\ell + 6) \cdot m + \sum_{i=1}^{\ell-1} \rho_i + \sum_{i=1}^{\ell} y_i = M + (\ell + 6) \cdot m + \sum_{i=1}^{\ell-1} \rho_i + x_1 + x_2 = |\lambda|.$$

Finally, $M + 2m \ge 2m = m + \rho_1 + y_1$. And as $\rho_i + y_i = \rho_{i-1}$ for all $2 \le i \le \ell$ and $\rho_i \ge 0$, it follows that $\nu$ is weakly decreasing. Therefore $\nu \vdash n$. $\square$

By Lemma 7 all technical requirements for Theorem 3 are met and we conclude that

$$g_{\lambda, (n-p, p), \nu} = \sum_{\substack{\beta \vdash p \\ \beta \subseteq \lambda \cap \nu}} k_{\beta \nu}^{\lambda} \qquad (6)$$

Define $\alpha := (m, m, m, \rho_1, \rho_2, \dots, \rho_{\ell-1})$. Then $\alpha$ is a partition of $p$ contained in $\nu \cap \lambda$. The next lemma shows that only the term corresponding to $\beta = \alpha$ contributes to the sum in (6), hence $g_{\lambda, (n-p, p), \nu} = k_{\alpha \nu}^{\lambda}$.

**Lemma 8** Let $\beta \vdash p$ be such that $\beta \subseteq \lambda \cap \nu$ and suppose that $k_{\beta \nu}^{\lambda} > 0$. Then $\beta$ equals the partition $\alpha := (m, m, m, \rho_1, \rho_2, \dots, \rho_{\ell-1})$.

**Proof:** Let $T$ be a Kronecker tableau of shape $\lambda/\beta$ and type $\nu - \beta$. As $\ell(\nu) = \ell + 3$, we have $\ell(\nu - \beta) \le \ell(\nu) = \ell + 3$. Therefore $T$ can only be filled with elements from the set $\{1, 2, \dots, \ell + 3\}$. Hence, because of $T$'s column strictness property, each of its columns can contain at most $\ell + 3$ boxes.

Let $\rho'$ and $\beta'$ denote the partitions conjugate to $\rho$ and $\beta$. In the $i$th column of $\lambda$, $1 \le i \le m$, there are exactly $3 + \ell + 3 + \rho'_i$ boxes. Since the $i$th column of $T$ contains at most $\ell + 3$ boxes, the top $3 + \rho'_i$ boxes must belong to $\beta$, which means $\beta'_i \ge 3 + \rho'_i$ for all $1 \le i \le m$. So in the first $m$ columns, this results in at least $3m + \sum_{i=1}^m \rho'_i = 3m + |\rho| = p$ boxes belonging to $\beta$. But $\beta \vdash p$, therefore $\beta'_i = 3 + \rho'_i$ for all $1 \le i \le m$ and $\beta'_i = 0$ for $i > m$. Transposing $\beta'$ back gives $\beta = (m, m, m, \rho_1, \rho_2, \dots, \rho_{\ell-1}) = \alpha$. $\square$

Let $\mathcal{T}$ denote the set of semistandard tableaus of shape $x = (x_1, x_2)$ and type $(0, 0, 0, y_1, y_2, \dots, y_\ell)$. Clearly, there is a bijection between $\mathcal{T}$ and set of semistandard tableaus of shape $x = (x_1, x_2)$ and type $(y_1, y_2, \dots, y_\ell)$ (just map entry $j$ to $j - 3$. See Figure 5 for an illustration). Hence $|\mathcal{T}| = \mathbf{K}_{xy}$.

<figure><img src="image_5.png" /><figcaption>**Fig. 5:** An illustration of the bijection between $\mathcal{T}$ and the set of semistandard tableaus of shape $x = (x_1, x_2)$ and type $(y_1, y_2, \dots, y_\ell)$</figcaption></figure>

Let $\mathcal{K}$ denote the set of Kronecker tableaus of shape $\lambda/\alpha$ and type $\nu - \alpha$. By definition, its cardinality equals $k_{\alpha \nu}^{\lambda}$. For the proof of Proposition 6 it is now sufficient to set up a bijection $\mathcal{K} \to \mathcal{T}$. Then we have shown $k_{\alpha \nu}^{\lambda} = \mathbf{K}_{xy}$ as claimed.
**Lemma 9** Let $T$ be a semistandard skew tableau of shape $\lambda/\alpha$ and type $\nu - \alpha$. Then:

1. The filling of $T$ in the first $m$ columns is fixed, namely in each of these the entries from 1 to $\ell + 3$ occur exactly once.

2. The first row of $T$ is filled with 1's.

3. The restriction of $T$ to its second and third row (denoted $T_{[2,3]}$) has the type $(0, 0, 0, y_1, y_2, \dots, y_\ell)$.

**Proof:** 1. This was already shown at the beginning of the proof of Lemma 8.

2. The shape $\lambda/\alpha$ of $T$ has $M+m$ columns and the type $\nu - \alpha$ has $M+m$ 1's. No two 1's can share a column, so every column has exactly one 1. In a column, the 1's must be the top elements. So in the first row, if a box is to be filled, it must be filled with a 1.

3. $T$ has the type $\nu - \alpha = (M + m, m, m, m + y_1, m + y_2, \dots, m + y_{\ell-1}, m + y_\ell)$. Hence there are only integers according to the type $(M, 0, 0, y_1, y_2, \dots, y_\ell)$ left to distribute in the columns with a number greater than $m$. As the first row contains exactly $M+m$ 1's, the claim follows. $\square$

According to Lemma 9, the map $\mathcal{K} \to \mathcal{T}, T \mapsto T_{[2,3]}$ is well defined and injective. (For an illustration see the Figures 4 and 6.)

<figure><img src="image_6.png" /><figcaption>**Fig. 6:** The semistandard Young tableau corresponding to the Kronecker tableau in Figure 4.</figcaption></figure>

We now proceed to prove that the map $\mathcal{K} \to \mathcal{T}, T \mapsto T_{[2,3]}$ is surjective. Let $S \in \mathcal{T}$ and consider the skew tableau $T$ of shape $\lambda/\alpha$ such that $S = T_{[2,3]}$, the first row of $T$ contains only 1's, and each of the first $m$ columns contain the entries $1, 2, \dots, \ell + 3$ in increasing order.

**Lemma 10** We have $T \in \mathcal{K}$.

**Proof:** First of all, it is easy to check that $T$ has the type $\nu - \alpha$. Next, we want to show that $T$ is a semistandard skew tableau using that $S = T_{[2,3]}$ is a semistandard tableau.

There are only 3 types of columns of $T$: The column strictness in the first $m$ columns is guaranteed by the fixed entries. The column strictness in the next $x_1$ columns is assured as the first row contains only 1's and the other rows contain entries starting with 4 and $T_{[2,3]}$ is semistandard. Each other column contains only a single 1. There are three types of rows: The first row contains only 1's. The second and third row only contain $T_{[2,3]}$ which is semistandard. The other rows have at most $m$ columns by definition of $\lambda$ and have fixed entries. The semistandard property of these rows follows from the fact that $\alpha$ is a partition. Altogether, we see that $T$ is a semistandard skew tableau.

In order to prove that $T$ is a Kronecker tableau it is sufficient to show that its reverse reading word $w^-$ is an $\alpha$-lattice permutation (note that $\alpha_1 = \alpha_2$). Let $T_{\le 3}$ denote the restriction of $T$ to the first three rows and let $w_{\le 3}^-$ be its reverse reading word. Moreover, we denote by $T_{\ge 4}$ the skew tableau obtained from $T$ by deleting the first three rows and let $w_{\ge 4}^-$ be its reverse reading word. Then we have $w^- = w_{\le 3}^- \cdot w_{\ge 4}^-$ (concatenation).
We first note that $w_{\le 4}$ is a lattice permutation. Indeed, this easily follows from the observation that for each entry $i > 1$ in $T_{\ge 4}$ there is an entry $i - 1$ in the same column right above (see Figure 4).

**Claim.** $w_{\le 3}$ is an $\alpha$-lattice permutation.

In order to show this, note that the first three rows of $T$ contain $M + m$ boxes. Let $k \in \{1, \dots, M + m\}$ be a position in the reverse lattice word $w_{\le 3}$. Then $(\#1's \text{ up to } k) + \alpha_1 = \min(M, k) + m$, $(\#2's \text{ up to } k) + \alpha_2 = (\#3's \text{ up to } k) + \alpha_3 = m$, and $(\#4's \text{ up to } k) + \alpha_4 = (\#4's \text{ up to } k) + m - y_1 \le m$. For every entry $i > 3$ we have

$$ (\#i's \text{ up to } k) + \alpha_i \ge \alpha_i = \rho_{i-3} = \rho_{i-2} + y_{i-2} = \alpha_{i+1} + y_{i-2} \ge (\#(i+1)'s \text{ up to } k) + \alpha_{i+1} $$

Therefore $w_{\le 3}$ is an $\alpha$-lattice permutation, which proves the claim.

Since $w_{\le 3}$ is an $\alpha$-lattice permutation and $w_{\ge 4}$ is a lattice permutation, we conclude that $w^{-}$ is an $\alpha$-lattice permutation. □

We have finished the proof of Proposition 6.

## References

* Cristina M. Ballantine and Rosa C. Orellana. A combinatorial interpretation for the coefficients in the Kronecker product $s_{(n-p,p)} * s_{\lambda}$. Sém. Lothar. Combin., 54A:Art. B54Af, 29 pp. (electronic), 2005/07. ISSN 1286-4889.

* Lance Fortnow. Counting complexity. In Complexity theory retrospective, II, pages 81–107. Springer, New York, 1997.

* William Fulton. Young tableaux, volume 35 of London Mathematical Society Student Texts. Cambridge University Press, Cambridge, 1997. ISBN 0-521-56144-2; 0-521-56724-6.

* Adriano M. Garsia and Jeffrey Remmel. Shuffles of permutations and the Kronecker product. Graphs Combin., 1(3):217–263, 1985. ISSN 0911-0119.

* Allen Knutson and Terence Tao. The honeycomb model of $GL_n(C)$ tensor products. I. Proof of the saturation conjecture. J. Amer. Math. Soc., 12(4):1055–1090, 1999. ISSN 0894-0347.

* Joseph M. Landsberg and Laurent Manivel. On the ideals of secant varieties of Segre varieties. Found. Comput. Math., 4(4):397–422, 2004. ISSN 1615-3375.

* Alain Lascoux. Produit de Kronecker des représentations du groupe symétrique. In Séminaire d'Algèbre Paul Dubreil et Marie-Paule Malliavin, 32ème année (Paris, 1979), volume 795 of Lecture Notes in Math., pages 319–329. Springer, Berlin, 1980.

* Ketan D. Mulmuley. Geometric complexity theory VI: The flip via saturated and positive integer programming in representation theory and algebraic geometry. Technical Report TR-2007-04, Computer Science Department, The University of Chicago, 2007.

* Ketan D. Mulmuley and Milind Sohoni. Geometric complexity theory. I. An approach to the P vs. NP and related problems. SIAM J. Comput., 31(2):496–526 (electronic), 2001. ISSN 1095-7111.
Ketan D. Mulmuley and Milind Sohoni. Geometric complexity theory III: On deciding positivity of Littlewood-Richardson coefficients. cs.ArXive preprint cs.CC/0501076, 2005.

Ketan D. Mulmuley and Milind Sohoni. Geometric complexity theory II: Towards explicit obstructions for embeddings among class varieties. cs.ArXive preprint cs.CC/0612134. To appear in SIAM J. Comput., 2006.

Hariharan Narayanan. On the complexity of computing Kostka numbers and Littlewood-Richardson coefficients. *J. Algebraic Combin.*, 24(3):347–354, 2006. ISSN 0925-9899.

Christos H. Papadimitriou. *Computational complexity*. Addison-Wesley Publishing Company, Reading, MA, 1994. ISBN 0-201-53082-1.

Jeffrey B. Remmel. A formula for the Kronecker products of Schur functions of hook shapes. *J. Algebra*, 120(1):100–118, 1989. ISSN 0021-8693.

Jeffrey B. Remmel. Formulas for the expansion of the Kronecker products $S_{(m,n)} \otimes S_{(1^{p-r},r)}$ and $S_{(1^k 2^l)} \otimes S_{(1^{p-r},r)}$. *Discrete Math.*, 99(1-3):265–287, 1992. ISSN 0012-365X.

Jeffrey B. Remmel and Tamsen Whitehead. On the Kronecker product of Schur functions of two row shapes. *Bull. Belg. Math. Soc. Simon Stevin*, 1(5):649–683, 1994. ISSN 1370-1444.

Mercedes H. Rosas. The Kronecker product of Schur functions indexed by two-row shapes or hook shapes. *J. Algebraic Combin.*, 14(2):153–173, 2001. ISSN 0925-9899.

Bruce E. Sagan. *The symmetric group*, volume 203 of *Graduate Texts in Mathematics*. Springer-Verlag, New York, second edition, 2001. ISBN 0-387-95067-2. Representations, combinatorial algorithms, and symmetric functions.

Richard P. Stanley. *Enumerative combinatorics. Vol. 2*, volume 62 of *Cambridge Studies in Advanced Mathematics*. Cambridge University Press, Cambridge, 1999. ISBN 0-521-56069-1; 0-521-78987-7. With a foreword by Gian-Carlo Rota and appendix 1 by Sergey Fomin.

V. Strassen. Rank and optimal computation of generic tensors. *Linear Algebra Appl.*, 52/53:645–685, 1983. ISSN 0024-3795.

Leslie G. Valiant. The complexity of computing the permanent. *Theoret. Comput. Sci.*, 8(2):189–201, 1979. ISSN 0304-3975.

Dominic J. A. Welsh. *Complexity: knots, colourings and counting*, volume 186 of *London Mathematical Society Lecture Note Series*. Cambridge University Press, Cambridge, 1993. ISBN 0-521-45740-8.