Rectangular Kronecker coefficients and plethysms in geometric complexity theory

Geometric complexity theory and Kronecker positivity

is the permanent polynomial, a polynomial of interest in particular in graph theory and physics. From a complexity theory standpoint the determinant is complete for the complexity class VPs [Val79a, Tod92, MP08], while the permanent is complete for VNP [Val79a] and also for #P [Val79b]. By definition we have \textup{{VP{}_{s}}}\subseteq\textup{{VNP}} and a major conjecture in algebraic complexity theory related to the famous $\textup{{P}}\neq\textup{{NP}}$ conjecture (see [Coo00]) is the following.

\textup{{VP{}_{s}}}\neq\textup{{VNP}}.

so $\textup{dc}(X_{1}X_{2}-X_{2}^{2}+2X_{1}-X_{2})\leq 2$. Conjecture 1.1 can be equivalently stated as follows:

The sequence $\textup{dc}(\textup{per}_{m})$ grows superpolynomially in $m$.

Finding lower bounds for $\textup{dc}(\textup{per}_{m})$ is an important research area in algebraic complexity theory, see for example the recent progress in [MR04, CCL10, LMR13, HI16, ABV15, Yab15]. Mulmuley and Sohoni [MS01, MS08] proposed an approach to this problem using algebraic geometry and representation theory and coined the term geometric complexity theory.

In the following we outline how one can prove lower bounds on $\textup{dc}(\textup{per}_{m})$ using rectangular Kronecker coefficients, see (1.5) below.

If $q^{m}_{\lambda}(d[n])>g(\lambda,n\times d,n\times d)$, then $\textup{dc}(\textup{per}_{m})>n$.

Kronecker coefficients are #P-hard to compute as they are generalizations of the well-known Littlewood-Richardson coefficients [Nar06]. But the positivity of Littlewood-Richardson coefficients can be decided in polynomial time [DLM06, MNS12], even by a combinatorial max-flow algorithm [BI13]. Even though deciding positivity of Kronecker coefficients is NP-hard in general, see [IMW15], the same paper provides evidence that the rectangular Kronecker coefficient case is significantly simpler. Thus to implement Thm. 1.4 [MS08] proposed to focus on the positivity of representation theoretic multiplicities in order to use the weaker statement

to prove lower bounds, see also [Lan15, Sec. 6.6] and [Bür15, Problem 3.13], where this approach is explained. The results in [BCI11b, BHI15, Kum15] already indicate that vanishing of $g(\lambda,n\times d,n\times d)$ might be rare. In [IMW15] sequences of partition triples $(\lambda,\mu,\mu)$ are constructed that satisfy $g(\lambda,\mu,\mu)=0$. Unfortunately $\mu$ has not the necessary rectangular shape. Indeed, our main result Thm. 1.6 completely rules out the possibility that (1.5) could be used to prove superpolynomial lower bounds on $\textup{dc}(\textup{per}_{m})$.

Let $n>3m^{4}$, $\lambda\vdash nd$. If $g(\lambda,n\times d,n\times d)=0$, then $q^{m}_{\lambda}(d[n])=0$.

Thm. 1.6 holds in higher generality: In the proof of Thm. 1.6 we do not use any specific property of the permanent other than it is a family of polynomials whose degree and number of variables is polynomially bounded in $m$. For all these families of polynomials no superpolynomial lower bounds on the determinantal complexity can be shown using the vanishing of $g(\lambda,n\times d,n\times d)$.

To use (1.5) it is required by (1.3) that

An example is $\lambda=(13,13,2,2,2,2,2)$ and $d=12$, $n=3$, where we have $a_{\lambda}(d[n])=1>0=g(\lambda,n\times d,n\times d)$, see [Ike12, Appendix].

A natural generalization of our main theorem would be to consider symmetric rectangular Kronecker coefficients instead of just $g(\lambda,n\times d,n\times d)$, because those are the multiplicities in the coordinate ring of the orbit $\GL_{n^{2}}\textup{det}_{n}$. Our proof does not immediately work for those coefficients as they lack the important transposition symmetry, but an equivalent no-go result for these coefficients follows directly from [BIP16].

For a partition $\lambda$ we write $\bar{\lambda}$ to denote $\lambda$ with its first row removed, so $|\bar{\lambda}|+\lambda_{1}=|\lambda|$. Vice versa, for a partition $\rho$ and $N\geq\rho_{1}$ we write $\rho(N):=(N-|\rho|,\rho)$ to denote the partition $\rho$ with an additional new first row containing $N-|\rho|$ boxes. The following theorem gives a very strong restriction on the shape of the partitions $\lambda$ that we have to consider.

We sometimes write $\lambda_{1}\geq d(n-m)$ instead of $|\bar{\lambda}|\leq md$.

The main ingredients for the proof of Thm. 1.6 are the following Corollary 1.9 and Thm. 1.10.

If $|\bar{\lambda}|\leq md$ with $a_{\lambda}(d[n])>g(\lambda,n\times d,n\times d)$, then $d>\frac{n}{m}$.

Note that if $n>3m^{4}$ and $d>\frac{n}{m}$, then $d>3m^{3}$.

Let ${\mathscr{X}}$ be the set of the following 6 exceptional partitions.

Thm. 1.10 is proved in Section 4. The proof cuts the partition $\lambda$ into smaller pieces in several significantly different ways and makes heavy use of the following three properties:

The semigroup property: If for 6 partitions $\lambda,\mu,\nu,\lambda^{\prime},\mu^{\prime},\nu^{\prime}$ of $N$ we have that $g(\lambda,\mu,\nu)>0$ and $g(\lambda^{\prime},\mu^{\prime},\nu^{\prime})>0$, then also $g(\lambda+\lambda^{\prime},\mu+\mu^{\prime},\nu+\nu^{\prime})>0$, where we interpret partitions as integer vectors in order to define the sum of two partitions.

The transposition property: $g(\lambda,\mu,\nu)=g(\lambda,\mu^{t},\nu^{t})=g(\lambda^{t},\mu^{t},\nu)=g(\lambda^{t},\mu,\nu^{t})$.

The square positivity: For all positive $k$ we have $g(k\times k,k\times k,k\times k)>0$.

The first property is easy to see if we interpret $g(\lambda,\mu,\nu)$ as the dimension of the $(\lambda,\mu,\nu)$-highest weight vector space in the coordinate ring of $V\otimes V\otimes V$. Here the acting group is $\GL(V)\times\GL(V)\times\GL(V)$ and the semigroup property follows from multiplying highest weight vectors. The second and third property follow from the character theory of the symmetric group. While the second property is immediate, the third property (in [BB04]) requires reduction to the alternating group and specific properties of characters of symmetric partitions, later generalized in [PPV16] and further in [PP14a].

(b) Consequences for geometric complexity theory

We remark that the overall proof structure in [BIP16] closely mimics the proof structure of our Thm. 1.6: [KL14] is used to prove a degree lower bound and then an analog to Thm. 1.10 is proved, also by cutting the partition $\lambda$ into smaller pieces. The details and the methods used in [BIP16] are very different from our paper though.

(c) Positivity results for Kronecker coefficients

In Section 4 we prove the rectangular Kronecker positivity for a large class of partitions: If the side lengths of the rectangles are at least quadratic in the partition length we have positivity, see Theorem 4.7 for the precise statement. More exact Kronecker positivity results are given in Section 6.

Combinatorial conjectures like the Saxl conjecture [PPV16, Ike15, LS15] are also concerned with the positivity of Kronecker coefficients.

In Section 5 we we prove that the saturation of the rectangular Kronecker semigroup is trivial, we show that the rectangular Kronecker positivity stretching factor is 2 for a long first row, and we completely classify the positivity of rectangular limit Kronecker coefficients.

We gratefully acknowledge the helpful comments of the anonymous reviewers. GP was partially supported by NSF grant DMS-1500834.

Proof of the degree lower bound

In this section we prove the degree lower bound Cor. 1.9. The main ingredients are Manivel’s result about limit rectangular Kronecker coefficients (Section 2 (a)) and Valiant’s insights about finite determinantal complexity (Section 2 (b)).

The main contribution to the specific limits of Kronecker coefficients that we are interested in in this paper comes from Manivel.

Since $g(\rho(nd),n\times d,n\times d)$ is symmetric in $n$ and $d$, if both $d\geq|\rho|$ and $n\geq|\rho|$, then $g(\rho(nd),n\times d,n\times d)=a_{\rho}$ and $a_{\rho}$ depends only on $\rho$. $\blacksquare$

Analogously, the 1-stable range is defined as

The following tables show the Kronecker coefficients $g(\rho(nd),n\times d,n\times d)$ for $\rho=(6)$, $\rho=(2,1,1,1,1,1)$, and $\rho=(3,1,1,1,1)$, from left to right.

(b) Complexity lower bounds literally too good to be true: inequality of multiplicities and degree lower bound

In this section we prove Corollary 1.9 by using the finiteness of the determinantal complexity.

As the following proposition shows, the existence of an $m$-obstruction of quality $n$ proves the existence of an $f\in V_{m}$ that cannot be written as an $n\times n$ determinant.

If there exists an $m$-obstruction of quality $n$, then $\textup{dc}(f)>n$ for some $f\in V_{m}$.

Given $\lambda\vdash nd$, if $|\bar{\lambda}|>dm$, then $o_{\lambda}^{m}(d[n])=0$.

Given $\lambda\vdash md$, we have $o_{\lambda+(dn-dm)}^{m}(d[n])\geq a_{\lambda}(d[m])$.

Part (a) is the first part of [KL14, Thm 1.3]. Part (b) follows from the proof of the second part of [KL14, Thm 1.3]: From a highest weight vector $P$ of weight $\lambda\vdash md$ in $\Sym^{d}(V_{m})$ they construct a highest weight vector $P^{\sharp n}$ of weight $\lambda+(d(n-m))\vdash nd$ in $\Sym^{d}(V_{n})$ such that the evaluations $P(f)=P^{\sharp n}(f^{\sharp n})$ coincide. Take a basis $P_{1},\ldots,P_{a_{\lambda}(d[m])}$ of the highest weight vector space of weight $\lambda$ in $\Sym^{d}(V_{m})$ and take general points $f_{1},\ldots,f_{a_{\lambda}(d[m])}$ from $V_{m}$. Then the evaluation matrix $\big(P_{i}(f_{j})\big)_{1\leq i,j\leq a_{\lambda}(d[m])}$ has full rank. Thus $\big(P^{\sharp n}_{i}(f^{\sharp n}_{j})\big)_{1\leq i,j\leq a_{\lambda}(d[m])}$ has full rank, which implies the statement. ∎

Let {\textup{dc{}_{\textup{max}}}}(m) denote the maximum $\max\{\textup{dc}(f)\mid f\in V_{m}\}$. The following lemma shows that {\textup{dc{}_{\textup{max}}}}(m) is a well-defined finite number.

From [Val79a] it follows that if $f$ has $r$ monomials, then $\textup{dc}(f)\leq rm$. In particular, since every $f\in V_{m}$ has at most $\binom{m+m^{2}-1}{m}$ monomials, it follows that $\forall f\in V_{m}:\ \textup{dc}(f)\leq\binom{m+m^{2}-1}{m}m$. ∎

Fix $\rho$, and let $(n,d)\in\St^{1}(\rho)$, which is true in particular if $n\geq|\rho|$. Let $\lambda=\rho(nd)$. Then $g(\lambda,n\times d,n\times d)\geq a_{\lambda}(d[n]).$

Interestingly the proof of this purely representation theoretic statement uses the finiteness of the determinantal complexity.

Assume the contrary, i.e., there exists a $\rho$ and $(m,d)\in\St^{1}(\rho)$ with $g(\rho(md),m\times d,m\times d)<a_{\rho(md)}(d[m]).$ Since $(m,d)\in\St^{1}(\rho)$, the Kronecker coefficient $g(\rho(nd),n\times d,n\times d)$ is the same for all $(n,d)$ with $n\geq m$. Thus we have $g(\rho(nd),n\times d,n\times d)<a_{\rho(md)}(d[m])$ for all $n$ with $n\geq m$. By Prop. 2.6(b) we have $o_{\rho(nd)}^{m}(d[n])\geq a_{\rho(md)}(d[m])$ for all $n\geq m$. This implies $\rho(nd)$ is an $m$-obstruction of quality $n$ for all $n\geq m$. By Prop. 2.5 there exist functions $f_{n}\in V_{m}$ such that $\textup{dc}(f_{n})>n$ for every $n>m$. In particular we have \textup{dc}(f_{{\textup{dc{}_{\textup{max}}}}(m)})>{\textup{dc{}_{\textup{max}}}}(m), in contradiction to Lem. 2.7. ∎

The proof is now immediate. By assumption we have $|\bar{\lambda}|\leq md$. By Prop. 2.8 we have $(n,d)\notin\St^{1}(\bar{\lambda})$, so $|\bar{\lambda}|>n$. Thus $dm\geq|\bar{\lambda}|>n$ and therefore $d>\frac{n}{m}$. ∎

Kronecker positivity: A simplified version

In this section we prepare the reader for the combinatorially intricate arguments to come in the proof of Thm. 1.10. This section is a purely didactical one. We prove a weaker statement (Thm. 3.1) than Thm. 1.10 in the following sense. The bound we obtain is weaker and we exclude column lengths 2, 3, 5, and 7 from $\lambda$, which are the column lengths that cause most of the technical issues. The paper is self-contained without this section 3. Neither Thm. 3.1 nor its proof are referenced later. On the contrary, to prove Thm. 3.1 we use two positivity results (Lem. 4.2 and Cor. 4.5) that will be proved in section 4.

Let $(i,1^{j})$ denote the hook partition of $i+j$ with $j+1$ boxes in the first column.

Let $m\geq 3$ and $d\geq m^{2}$. Let $1\leq j<m^{2}$, $j\notin\{1,2,4,6\}$. Then $g((dm^{2}-j,1^{j}),d\times m^{2},d\times m^{2})>0$.

This follows from Cor. 4.5, because $m^{4}-6>m^{2}$. ∎

Together with Lem. 4.2 we now have all the building blocks to prove Thm. 3.1.

We forget about the first row of $\lambda$ and treat each column length $k\in\{2,\ldots,m^{2}\}$ in $\lambda$ separately. For the ease of notation let $\bar{k}:=k-1$. For each $k$ let $c_{k}$ be the number of columns of length $k$ in $\lambda$. We divide $c_{k}$ by $k$, formally $c_{k}=x_{k}k+r_{k}$ with $r_{k}<k$. The partition $\bar{\lambda}$ decomposes as follows:

Note that by assumption on $\lambda$ both sums exclude the four values $k\in\{2,3,5,7\}$. We now group together the $(\bar{k}\times k)$ rectangles into groups of roughly $\frac{d}{k}$, so that the result is roughly of size $\bar{k}\times d$. Formally we define $s_{k}:=\lfloor d/k\rfloor$ and divide $x_{k}=h_{k}s_{k}+t_{k}$ with $t_{k}<s_{k}$. Now $\bar{\lambda}$ decomposes as follows:

We prove Kronecker positivity for the summands separately. For the leftmost sum, $g((\bar{k}\times ks_{k})(dk),d\times k,d\times k)>0$ by Lem. 4.2 with $a=d$. For the middle sum, $g((\bar{k}\times kt_{k})(dk),d\times k,d\times k)>0$ with the same argument. For the rightmost sum, $g((dm^{2}-\bar{k},1^{\bar{k}}),d\times m^{2},d\times m^{2})>0$ by Lem. 3.2. According to these observations we add a new first row to $\bar{\lambda}$. Formally $\mu:=$

Using the semigroup property the above three positivity considerations we show that

Proof of Kronecker positivity

In this section we prove Thm. 1.10. If $\bar{\lambda}\in{\mathscr{X}}$, a finite calculation reveals $a_{\bar{\lambda}}=0$. Combining this with Prop. 2.8 gives $a_{\lambda}(d[n])=0$. Thus we are left to analyze the case $\bar{\lambda}\notin{\mathscr{X}}$.

Given a partition $\nu\notin{\mathscr{X}}$ we want to decompose it into smaller partitions and use the semigroup property to show the positivity of $g(\nu(ab),a\times b,a\times b)$. We use the following decomposition theorem to write $\nu$ as a sum of partitions that are not in ${\mathscr{X}}$.

with $y_{k}<k$ and where all columns in $\xi$ have distinct lengths and no column in $\xi$ has length 1, 2, 4, or 6, and where $\rho$ is of one of the following shapes:

$\rho$ has only columns of length 1, 2, 4, 6, all column lengths are distinct, and $\rho\notin{\mathscr{X}}$.

$\rho=(i\times 2)+\eta$, where $i\in\{2,4,6\}$ and $\eta\in{\mathscr{X}}\setminus\{(3,1)\}$.

$\rho=(4)+\eta$, where $\eta\in{\mathscr{X}}\setminus\{(3,1)\}$.

$\rho\in\{(3,1,1,1,1,1),(3,1,1,1),(3),(4,1)\}$.

We start by treating each $k$ independently. Let $c_{k}$ denote the number of columns of length $k-1$ in $\nu$. In a greedy manner cut off from $\nu$ as many rectangles of size $(k-1)\times k$ as possible. Formally, we divide $c_{k}=x^{\prime}_{k}k+r^{\prime}_{k}$ with $r^{\prime}_{k}<k$. We are left with a $(k-1)\times r^{\prime}_{k}$ rectangle. We now join (if possible) one of the $(k-1)\times k$ rectangles with the $(k-1)\times r_{k}$ rectangle: If $x^{\prime}_{k}\geq 1$, define $r_{k}:=r^{\prime}_{k}+k$ and $x_{k}:=x^{\prime}_{k}-1$. If $x^{\prime}_{k}=0$, define $r_{k}:=r^{\prime}_{k}$ and $x_{k}:=x^{\prime}_{k}$. We obtain a $(k-1)\times r_{k}$ rectangle and call it $R_{k}$. Note that $r_{k}<2k$.

Cut off from $R_{k}$ rectangle as many rectangles of size $(k-1)\times 2$ as possible. Formally, define $y_{k}:=\lfloor r_{k}/2\rfloor$, so $y_{k}<k$ as required in the claim. After cutting we are left with either the empty partition or a column $(k-1)\times 1$. In the former case (i.e., $r_{k}$ is even) define $b_{k}:=0$, otherwise $b_{k}:=1$.

as required in the statement of the claim. Moreover, $\xi$ has the correct shape. Clearly $\rho$ has only columns of length 1, 2, 4, 6 and all column lengths are distinct. If $\rho\notin{\mathscr{X}}$, then we are done by property (1).

The rest of the proof is devoted to the case where $\rho\in{\mathscr{X}}$. We will use that if $y_{k}=0$, then $\nu$ has at most 1 column of length $k-1$, by definition of $R_{k}$. Note that $\rho\neq(3,1)$, because no two columns in $\rho$ have the same length. If $\nu$ has a column of length $i$ different from 1, 2, 4, 6, then such a column appears in $\xi$ or we have that $y_{i+1}>0$ and $\xi$ has no column of length $i$. If it appears in $\xi$, then we remove it from $\xi$ and add it to $\rho$ and we are done by property (2). If it does not appear in $\xi$ but $y_{i+1}>0$, then we decrease $y_{i+1}$ by 1 and add a column of length $i$ to both $\xi$ and $\rho$, so that we are done by property (2).

So from now on we assume that $\nu$ only has columns of length 1, 2, 4, or 6 (and thus $x_{k}=0$ for all $k\notin\{2,3,5,7\}$).

If $y_{i+1}>0$ for some $i\in\{2,4,6\}$, then we can decrease $y_{i+1}$ by 1 and set $\rho\leftarrow\rho+(i\times 2)$, so we are done by property (3).

Thus from now on we assume $y_{i+1}=0$ for all $i\in\{2,4,6\}$. Note that $y_{2}$ corresponds to the columns of length 1 in $\nu$. If $y_{2}\geq 2$, then we can decrease $y_{2}$ by 2 and set $\rho\leftarrow\rho+(4)$, so we are done by property (4).

At this point the possible shapes of $\nu$ are quite limited: $c_{i+1}=0$ for all $i\notin\{1,2,4,6\}$, $c_{i+1}\leq 1$ for $i\in\{2,4,6\}$, $c_{2}\leq 3$.

If $y_{2}=0$, then $\nu=\rho$ by construction, which is impossible because $\nu\notin{\mathscr{X}}$ and $\rho\in{\mathscr{X}}$.

Recall $\rho\in{\mathscr{X}}\setminus\{(3,1)\}$. If $y_{2}=1$, then $\nu=\rho+(2)$, so $\nu\in\{(3,1,1,1,1,1),(3,1,1,1),(3,1),(3),(4,1)\}.$ Since $\nu\notin{\mathscr{X}}$ it follows $\nu\in\{(3,1,1,1,1,1),(3,1,1,1),(3),(4,1)\}.$ Now we set $y_{2}\leftarrow 0$ and $\rho\leftarrow\nu$ and we are done by property (5). ∎

All summands in the partition decomposition will yield a positive rectangular Kronecker coefficient, but we will need to group large blocks of $(k-1)\times k$ rectangles. This is done with the following lemma.

Let $\mu=(k\times(ks))$ and $a\geq ks$, then $g(k\times(ks)+(k(a-ks)),a\times k,a\times k)>0$.

For all $k$ we have $g(k\times k,k\times k,k\times k)>0$ as shown in [BB04]. By the semigroup property we can add these square triples $s$ times and obtain $g(k\times(ks),k\times(ks),k\times(ks))>0.$ Let $(k(a-ks))$ denote the single row partition of $k(a-ks)$. Clearly $g((k(a-ks)),k\times(a-ks),k\times(a-ks))>0$. Adding these two triples with the semigroup property we get $g(k\times(ks)+(k(a-ks)),k\times a,k\times a)>0.$ Finally, transposing the last two partitions we obtain the statement. ∎

The following proposition will be used to prove positivity for building blocks of partitions like hooks and fat hooks. Here, for a set $S$ and a number $x$ we denote by $x-S$ the set $\{x-y\mid y\in S\}$.

Note that $R_{\rho}$ is the size of the partition obtained from $\rho$ by adding a shortest possible top row and one extra box at the top left corner, so that the largest possible column we can add is $h^{2}-R_{\rho}$ to still have a valid partition.

Claim: Suppose that $k\in P_{c}$, then $k,k+2c+1\in P_{c+1}$.

Next, to show that $k+2c+1\in P_{c+1}$ we first transpose $\nu^{k}(c^{2})$ and one of the squares, apply the argument from above to it, and then transpose again:

The claim implies that $P_{c}\cup(2c+1+P_{c})\subset P_{c+1}$.

and we see that $k\notin S_{k+1}$, in contradiction to $k\in S_{k+1}$. Thus the assumption is wrong and we conclude $S_{c+1}\subset P_{c+1}$, so the induction is complete. ∎

Let $1^{j}$ denote the rectangular partition $j\times 1$. Let $(i,1^{j})$ denote the hook partition of $i+j$ with $i$ boxes in the first row and $j+1$ boxes in the first column. So $(k-j,1^{j})$ has $k$ boxes. The next corollary says that most hooks have positive rectangular Kronecker coefficient.

Let $w\geq h\geq 7$, then $g((hw-j,1^{j}),h\times w,h\times w)>0$ for all $j\in[0,h^{2}-1]\setminus\{1,2,4,6,h^{2}-2,h^{2}-3,h^{2}-5,h^{2}-7\}$.

We apply Prop. 4.3 with $\rho=\emptyset$, $a=7$, $R_{\rho}=1$ and $H^{1}_{\rho}=\{1,2,4,6\}$ and $H^{2}_{\rho}=\{2,3,5,7\}$. The values at $a=7$ are readily verified by direct computation. Then we have for all $b\geq 7$ that $g((b^{2}-j,1^{j}),b\times b,b\times b)>0$ for $j\in[0,b^{2}-1]\setminus(H^{1}_{\rho}\cup(b^{2}-H^{2}_{\rho}))$. Let $h=b$ and use the semigroup property once to add the positive triple $((h(w-h)),h\times(w-h),h\times(w-h))$ in order to obtain the statement. ∎

Let $(i,1^{j}+\rho)$ denote the partition that results from $\rho$ by first adding an additional column with $j$ boxes and then adding a top row with $i$ boxes. The next corollary treats the positivity of hooks that are not covered by Cor. 4.5.

Fix $w\geq h\geq 7$. We have that $g(\lambda,h\times w,h\times w)>0$ for all $\lambda=(hw-j-|\rho|,1^{j}+\rho)$ with $\rho\neq\emptyset$ and $|\rho|\leq 6$ for all $j\in[1,h^{2}-R_{\rho}]$, where $R_{\rho}=|\rho|+\rho_{1}+1$, except in the following cases: (i) $\rho=(1)$ with $j=2$ or $j=h^{2}-4$; (ii) $\rho=(2)$ with $j=2$; (iii) $\rho=(1^{2})$ and $j=1$ or $j=h^{2}-5$; (iv) $\rho=(2,1)$ and $j=1$.

For all values of $j\leq 6$ we have finitely many partitions $\nu^{j}:=1^{j}+\rho$ of length at most 6 and width at most 7, for which we verify computationally the statement with $h=w=7$ and then by the semigroup property deduce it for $\lambda=\nu^{j}(hw),h\times w,h\times w$ with $h,w\geq 7$.

(i) When $\rho=(1)$ then $R_{\rho}=3$, $H^{1}_{\rho}=\{2\}$ and $H^{2}_{\rho}=\{4\}$, we obtain $g((h^{2}-1-j,2,1^{j-1}),h\times h,h\times h)>0$ for $j\in[1,h^{2}-R_{\rho}]\setminus\{2,h^{2}-4\}$.

(ii) When $\rho=(2)$ then $R_{\rho}=5$, $H^{1}_{\rho}=\{2\}$ and $H^{2}_{\rho}=\emptyset$.

(iv) When $\rho=(2,1)$ and $j\geq 2$, then we apply Proposition 4.3 with $H^{1}_{\rho}=H^{2}_{\rho}=\emptyset$, and the case $j=1$ was excluded computationally.

Last, we add the positive triple $(h(w-h),h\times(w-h),h\times(w-h))$ to $(h^{2}-j-|\rho|,1^{j}+\rho),h\times h,h\times h$ to obtain the statement. ∎

Now we are ready to prove the main positivity theorem.

We will treat these 5 summands independently.

Using Lem. 4.2 with $s=s_{k}$ (recall $a_{k}=ks_{k}$) we see that $g((\bar{k}\times a_{k})(ak),a\times k,a\times k)>0.$ Using the semigroup property for the $h_{k}$ summands we get

Using Lem. 4.2 again, this time with $s=t_{k}$ we see that

Using Corollary 4.5 twice with the semigroup property (in the case $k\notin\{2,3,5,7\}$) or using Corollary 4.6 we see that $g((\bar{k}\times 2)(2hw),h\times 2w,h\times 2w)>0$ for all $h,w\geq 7$, $h\geq\sqrt{k+7}$, $w\geq\sqrt{k+7}$.

For $\rho$ we make the case distinction from Lemma 4.1. In cases $(1)$, $(3)$, $(4)$, and $(5)$ a finite calculation shows that $g(\rho(49),7\times 7,7\times 7)>0$. In case $(2)$ we invoke Cor. 4.6 to see that $g(\rho(wa),a\times w,a\times w)>0$. In both cases we have

Using the semigroup property on equations (4.8), (4.9), (4.10), (4.11), and (4.12) we obtain

Further positivity results: limit coefficients, stretching factor, and semigroup saturation

In the rest of the appendix we prove the positivity of rectangular Kronecker coefficients for a large class of partitions where the side lengths of the rectangle are at least quadratic in the length of the partition. Moreover, we prove that the saturation of the rectangular Kronecker semigroup is trivial, we show that the rectangular Kronecker positivity stretching factor is 2 for a long first row, and we completely classify the positivity of rectangular limit Kronecker coefficients that were introduced by Manivel in 2011.

Recall the definition ${\mathscr{X}}=\{(1),(2\times 1),(4\times 1),(6\times 1),(2,1),(3,1)\}$ from Thm. 1.10. Using Thm. 1.10 we get a complete classification of all cases in which $a_{\rho}=0$.

Given $\rho\notin{\mathscr{X}}$, $a_{\rho}>0$ can be seen by choosing large $d$ and $n$ and applying Thm. 1.10. For $\rho\in{\mathscr{X}}$, $a_{\rho}=0$ is a small finite calculation. ∎

(b) Double and triple column hooks

Here we study Kronecker coefficients for partitions $\lambda=i^{k}$ and the Kronecker coefficients $g(\lambda(ab),a\times b,a\times b)$ when $i=2$ and $i=3$. In the case of $i=1$ these were exactly the hooks which were already classified. By that classification and the semigroup property it is readily seen that since $\lambda=i(1^{k})$, for $k\neq 1,2,4,6,d^{2}-7,a^{2}-5,a^{2}-3,a^{2}-2$ we have $g(\lambda(ab),a\times b,a\times b)>0$ for $b$ large enough. We now prove that this positivity holds in fact for all $k\in[0,a^{2}-1]$ when $i>1$.

Let $i>1$. For any $m\geq 7$ and $k\in[0,m^{2}-1]$ we have that $g(i(m^{2}-k,1^{k}),m\times(im),m\times(mi))>0$.

First, note that proposition follows from the hook positivity as long as $k\neq 1,2,4,6,m^{2}-7,m^{2}-5,m^{2}-3,m^{2}-2$. In the case when $k=1,2,4,6$ finite calculations for $i=2,3$ and $m=7$ give positive values. For $i\geq 4$ we have that $i=2i_{1}+3i_{2}$ for some $i_{1},i_{2}\geq 0$, and then we apply the semigroup property for $i_{1}$ many double hooks plus $i_{2}$ many triple hooks. By that argument, we can always assume that $i\leq 3$.

So we can assume that $k\in\{m^{2}-7,m^{2}-5,m^{2}-3,m^{2}-2\}$, i.e. $r:=m^{2}-k-1\in$ is finite.

Let $\mu^{i}[a,b]:=((k+1)^{i},1^{ir})=((ab-r)^{i},1^{ir})$ be its transpose partition. Note that $\mu^{i}[m,m]=(i(m-k,1^{k}))^{t}$, so by transposing one of the rectangles the statement to prove is equivalent to showing that

This will follow from the following claim applied when $a=b=m$:

Claim: We have that for all $a,b\geq 6$, $r\leq 7$ and $i\in$

We prove this claim by induction on $(a,b)$, with initial condition computationally verified for $(a,b)=(7,7)$ for the given finite set of values for $i$ and $r$. Suppose that the claim holds for some values $a=a_{0},b=b_{0}\geq 7$, i.e. we have $g(\mu^{i}[a_{0},b_{0}],(ia_{0})\times b_{0},a_{0}\times(b_{0}i))>0$. Consider the triple $(a,b)=(a_{0},b_{0}+1)$. Since $g((ia_{0}),(a_{0}^{i}),(a_{0}^{i}))>0$ after transposing the first two partitions and rearranging them we also have that $g(a_{0}^{i},1^{ia_{0}},i^{a_{0}}))>0$. Add this triple to $\mu^{i}[a_{0},b_{0}],(ia_{0})\times b_{0},a_{0}\times(b_{0}i)$, applying the semigroup property, we have that

This show that the claim holds for $(a_{0},b_{0}+1)$ as well. By the symmetry between $a$ and $b$, we also have the statement for $(a_{0}+1,b_{0})$, so by induction the claim holds for all $(a,b)$, s.t. $a,b\geq 7$.

Applying the claim with $a=b=m$ completes the proof.

(c) Stretching factor 2

Cut $\rho$ columnwise and group pairs of columns of the same length $k$ so that you get partitions $(k\times 2)$. By Prop. 5.2 we have $a_{(k\times 2)}(m)>0$. Using the semigroup property we get the result. ∎

(d) Trivial saturation of the rectangular Kronecker semigroup

Let $d\geq 7$. The group $G_{d}$ contains all partitions $\lambda$ for which $d$ divides $|\lambda|$.

By Prop. 5.2 for all $0\leq k<m^{2}$ we have $(k\times 3)(3m^{2})\in S_{d}$ and $(k\times 2)(2m^{2})\in S_{d}$. Subtracting these we obtain $(m^{2}-k,k\times 1)\in G_{d}$. For $1\leq k<m^{2}$ we subtract $(m^{2}-k+1,(k-1)\times 1)$ from $(m^{2}-k,k\times 1)$ to obtain $v_{k+1}:=(-1,0,\ldots,0,1,0,\ldots,0)\in G_{d}$, where the $1$ is at position $k+1$. Given a partition $\lambda$ we define $\nu:=\sum_{k=2}^{m^{2}}\lambda_{k}v_{k}$ and obtain a vector that coincides with $\lambda$ in every entry but the first: $\nu_{1}=-|\bar{\lambda}|$. We calculate $\lambda=\mu+j\cdot(d,0,\ldots,0)$ with $j=|\lambda|/d$. Since $d$ divides $|\lambda|$ it follows that $j$ is an integer. Since $(d,0,\ldots,0)\in S_{d}$ we have $\lambda=\mu+j\cdot(d,0,\ldots,0)\in G_{d}$. ∎

Exact results for Kronecker coefficients

Here we provide a complete classification of triples $\lambda,a,b$ with $\lambda$ – hook or two-column partition, for which the Kronecker coefficient $g(\lambda,a\times b,a\times b)$ is positive and in the course of the proof give certain stronger quantitative relationships between these coefficients.

Assume that $n\geq d$. Let $d\geq 7$. We then have that $g((nd-k,1^{k}),d\times n,d\times n)>0$ $k\in[0,d^{2}-1]\setminus\{1,2,4,6,d^{2}-7,d^{2}-5,d^{2}-3,d^{1}-2\}$ and is 0 for all other values of $k$.

For $d\leq 6$ we have that $g((nd-k,1^{k}),d\times n,d\times n)=0$ if $k>d^{2}-1$ or in the following cases:

Moreover, we have that $g((nd-k,1^{k}),d\times n,d\times n)>g((nd-k+2,1^{k-2}),d\times n,d\times n)$ for $k\leq d^{2}/2$ and the coefficients form a symmetric sequence in $k=0,\ldots,d^{2}-1$.

It is immediate to characterize the triples for which the Kronecker coefficient is 1.

Fix $d>6$ and let $\rho$ be a partition with $m_{i}$ columns of length $i$. Then $g(\rho(nd),d\times n,d\times n)>0$ if $m_{i}\neq 1$ for $i=1,2,4,6$ and $m_{i}=0$ for $i=d^{2}-7.d^{2}-5,d^{2}-3,d^{2}-2$.

Direct computation shows that $g(((6^{2}-3i),i^{3}),6\times 6,6\times 6)>0$ for $i=1,2,4,6$, so by the semigroup property we have $g(nd-3i,i^{3}),d\times n,d\times n)>0$ for all $d,n\geq 6$. Since every $m_{i}\geq 2$ is either even, or $3+2a_{i}$, we have that $(i^{m_{i}})$ is an even partition or is the sum of $(i^{3})+(i^{2a_{i}})$. By the semigroup property for Kronecker coefficients then we must have $g((nd-im_{i},i^{m_{i}}),d\times n,d\times n)>0$ for all $m_{i}\geq 2$ when $i=1,2,4,6$. By Theorem 6.1 for any $m_{i}$ for the remaining values of $i\geq d^{2}-1$.

Since $\rho=\sum_{i}(i^{m_{i}})$, the statement follows by the Kronecker semigroup property.∎

In order to prove this theorem, we will derive a simple formula for these Kronecker coefficients, following the approaches set in [Bla12, Liu14, PP14b]. For brevity we set $g_{k}(d,n)=g((nd-k,1^{k}),d\times n,d\times n)$.

We have that the Kronecker coefficients $g((nd-k,1^{k}),d\times n,d\times n)$ are equal to the number of partitions of $k$ into distinct parts from $\{3,5,\ldots,2d-1\}$, where without loss of generality by the symmetry of the Kronecker coefficients we assume $d\leq n$. In other words, we have the following generating function identity:

Let $s_{\lambda}$ denote the Schur function indexed by a partition $\lambda$ and let $*$ denote the Kronecker product on the ring of symmetric functions, i.e. given by

For the sake of self-containment we repeat some calculations appearing in [Bla12, Liu14, PP14b].

We invoke Littlewood’s identity, stating that

In the case when $\alpha=(1^{k})$ and $\beta=(nd-k)$ we have that $s_{\theta}*s_{1^{k}}=s_{\theta^{\prime}}$ and $s_{\tau}*s_{nd-k}=s_{\tau}$, where $\theta^{\prime}$ is the transposed (conjugate) partition of $\theta$. Observe that $s_{1^{k}}s_{nd-k}=s_{(nd-k,1^{k})}+s_{(nd-k+1,1^{k-1})}$. Rewriting the above identity in this case leads to

Take inner product with $s_{\mu}$ on both sides. Observe that the left-hand side gives two Kronecker coefficients and on the right side we have $\langle s_{\mu},s_{\theta^{\prime}}s_{\tau}\rangle=c^{\mu}_{\theta^{\prime}\tau}$ by the Littlewood-Richardson rule, so

Note that when $k=0$ we have that $g(\lambda,\mu,(nd))=1$ if $\lambda=\mu$ and $0$ otherwise, and the above identity holds assuming that the term with $(nd-k+1,1^{k-1})$ is 0 when $k<1$.