# Stability of Kronecker coefficients via discrete tomography (Extended abstract)

Ernesto Vallejo

► To cite this version:

Ernesto Vallejo. Stability of Kronecker coefficients via discrete tomography (Extended abstract). 27th International Conference on Formal Power Series and Algebraic Combinatorics (FPSAC 2015), Jul 2015, Daejeon, South Korea. pp.805-816, 10.46298/dmtcs.2525 . hal-01337772

HAL Id: hal-01337772

https://hal.science/hal-01337772

Submitted on 27 Jun 2016

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_1.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
# Stability of Kronecker coefficients via discrete tomography (Extended abstract)

Ernesto Vallejo †

Centro de Ciencias Matemáticas, Universidad Nacional Autónoma de México, Morelia, Mexico

**Abstract.** In this paper we give a sufficient condition for a general stability of Kronecker coefficients, which we call additive stability. Its main ingredient is the property of a matrix of being additive. This notion seems to be an important one: it appears in Discrete Tomography as a sufficient condition to uniqueness; it also appears in Manivel's study of asymptotic properties of plethysm through Borel-Weil theory. The proof sketched here combines several results of the author on integer matrices motivated by Discrete Tomography with a new idea of Stembridge, that permits to bound some sequences of Kronecker coefficients. The advantage of additivity with respect to the previous approach by Stembridge is that it is very easy to produce new examples of additive matrices and, therefore, to produce many new examples of stability of Kronecker coefficients. We also show that Murnaghan's stability property and other instances of stability discovered previously by the author are special cases of additive stability. Besides, our approach permits us to disprove a recent conjecture of Stembridge and to give a new characterization of additivity.

**Résumé.** Dans ce papier nous donnons une condition suffisant pour la stabilité general des coefficients de Kronecker, que nous appelons stabilité additive. Le ingrédient principal est la propriété d'une matrice d'être additif. Cette notion est apparemment d'importance: elle apparaît en Tomographie Discrète comme une condition suffisant pour unicité; elle apparaît aussi dans l'étude de Manivel de propriétés asymptotiques du plethysm par moyen de la théorie de Borel-Weil. La démonstration esquissé ici combine plusieurs résultats de l'auteur sur les matrices à coefficients entières stimulés pour la Tomographie Discrète avec une nouvelle idée de Stembridge, qui permet d'borner quelques successions des coefficients de Kronecker. L'avantage de notre méthode sur l'approche de Stembridge est qui c'est très facile de produire nouveaux exemples de matrices additives, et pourtant, nouveaux exemples d'estabilité des coefficients de Kronecker. Nous démontrons aussi que la stabilité de Murnaghan et d'autres exemples de stabilité trouvés antérieurement par l'auteur sont des cas spéciales de la stabilité additive. En plus, avec notre approche nous réfutons une conjecture de Stembridge et donnons une nouvelle caractérisation d'additivité.

**Keywords:** Kronecker coefficient, Schur function, Stability, Discrete tomography, Additivity, Transportation polytope.

## 1 Introduction

Kronecker coefficients are among the most fascinating and complex objects in algebraic combinatorics. They appear as multiplicities of various constructions involving tensor products of representations of the

<footnote>†Email: vallejo@matmor.unam.mx. Supported by UNAM-DGAPA IN108314.</footnote>
symmetric group $S_n$, Schur powers of some representations of the general linear group $GL_n(\mathbb{C})$ or the space of sections of a line bundle over a flag variety. They also appear in certain expansions of symmetric functions. A long sought combinatorial or geometric description of Kronecker coefficients (such as the ones existing for the Littlewood-Richardson coefficients) is still to be found.

For our purposes, given three partitions $\lambda, \mu, \nu$ of a positive integer $n$, we choose to define the Kronecker coefficient $g(\lambda, \mu, \nu)$ as the multiplicity of the complex irreducible character $\chi^\nu$ of $S_n$ associated to $\nu$ in the Kronecker product $\chi^\lambda \otimes \chi^\mu$ of other two irreducible characters $\chi^\lambda$ and $\chi^\mu$ of $S_n$. Thus, if $\langle \cdot, \cdot \rangle$ denotes the scalar product of complex characters of $S_n$,

$$g(\lambda, \mu, \nu) = \langle \chi^\lambda \otimes \chi^\mu, \chi^\nu \rangle.$$

In the first paper on the Kronecker coefficients [19], published in 1938, Murnaghan stated without proof the following stability property for Kronecker coefficients (see also [20]): For each triple of partitions $\lambda, \mu, \nu$ of the same size, the sequence of integers

$$\{g(\lambda + (n), \mu + (n), \nu + (n))\}_{n \in \mathbb{N}} \qquad (1)$$

converges. It was first proved by Littlewood [14]. Since then many other proofs of this property with different flavours have appeared [2, 4, 6, 22, 30, 33, 40]. Estimations of lower bounds $L$ for stability can be found in [3, 4, 33, 40].

Recently, a generalization of Murnaghan's stability was discovered [40, Thm. 10.2]. Let $d(\nu) = |\nu| - \nu_1$ denote the depth of $\nu$. There it is shown that if $i \le \min\{\ell(\lambda), \ell(\mu)\}$, $\lambda_i - \lambda_{i+1} \ge d(\nu)$ and $\mu_i - \mu_{i+1} \ge d(\nu)$ (if $i = \ell(\lambda)$, we define $\lambda_{i+1} = 0$), then for all $n \in \mathbb{N}$, we have

$$g(\lambda + (n^i), \mu + (n^i), \nu + (n^i)) = g(\lambda, \mu, \nu). \qquad (2)$$

The case $i = 1$ yields Murnaghan's stability. The stability given in equation (2) was found independently in [22] (with different bounds), where it was called k-stability. Both results were inspired on a particular case of (2) (when $\lambda = \mu$), that appears on the first version of [40]$^{(i)}$.

The proof of Theorem 10.2 in [40] also yields a more general type of stability, which includes (2). We now describe it. Let $\lambda, \mu, \nu$ be a triple of partitions of the same size and let $d = d(\nu)$, then for any pair of vectors $(i_1, \dots, i_t)$, $(n_1, \dots, n_t) \in \mathbb{N}^t$, such that $i_1 > i_2 > \dots > i_t$ and $n_j \ge d$, for all $j \in [t]$,

$$g \left( \lambda + \sum_{j=1}^{t} (n_j^{i_j}), \mu + \sum_{j=1}^{t} (n_j^{i_j}), \nu + \left( \sum_{j=1}^{t} n_j i_j \right) \right) = g \left( \lambda + \sum_{j=1}^{t} (d^{i_j}), \mu + \sum_{j=1}^{t} (d^{i_j}), \nu + \left( \sum_{j=1}^{t} d i_j \right) \right) \quad (3)$$

Let $\alpha$ be the conjugate partition of $(i_1, \dots, i_t)$, then $\sum_{j=1}^{t} (1^{i_j}) = \alpha$ and $\sum_{j=1}^{t} (d^{i_j}) = d\alpha$. Thus, identity (3) can be rewritten in the following way

$$g \left( \lambda + \sum_{j=1}^{t} (n_j^{i_j}), \mu + \sum_{j=1}^{t} (n_j^{i_j}), \nu + \left( \sum_{j=1}^{t} n_j i_j \right) \right) = g(\lambda + d\alpha, \mu + d\alpha, \nu + (d|\alpha|)). \quad (4)$$

<footnote>(i) See Section 9 in arXiv:1310.8362v1 [math.CO] 31 Oct 2013.</footnote>
Another, apparently different, kind of stability was discovered sometime ago in [39, Thm. 3.1]. There, it is shown that, if $q, r$ are positive integers such that $\ell(\lambda) \le qr, \ell(\mu) \le q$ and $\ell(\nu) \le r$. Then for all $n \in \mathbb{N}$,

$$g(\lambda + (n^{qr}), \mu + ((nr)^q), \nu + ((nq)^r)) = g(\lambda, \mu, \nu). \qquad (5)$$

Even more recently, J. Stembridge [28, Corollary 6.2] proved the following general stability property for Kronecker coefficients. Denote $\phi^\lambda = \text{Ind}_{\mathbb{S}_\lambda}^n(1_\lambda)$ denote the permutation character associated to $\lambda$. Let $\alpha, \beta, \gamma$ be partitions of the same size, such that $g(\alpha, \beta, \gamma) > 0$ and

$$\langle \phi^{n\alpha} \otimes \phi^{n\beta}, \chi^{n\gamma} \rangle = 1, \text{ for all } n \in \mathbb{N}. \qquad (6)$$

Then, for any triple of partitions $\lambda, \mu, \nu$ of the same size, there is a positive integer $L$ such that, for all $n \ge L$,

$$g(\lambda + n\alpha, \mu + n\beta, \nu + n\gamma) = g(\lambda + L\alpha, \mu + L\beta, \nu + L\gamma). \qquad (7)$$

In this paper we will show that practically all these stability properties fit into what we call *additive stability*. The main contribution of this paper is the discovery of the connection between additivity of integer matrices with Stembridge's approach to stability. Additivity, in our context, is a concept coming from discrete tomography (see [11, 12] for an overview of the area). In [8, 9] Fishburn et al. consider the problem of studying finite subsets in $\mathbb{R}^n$ that are uniquely reconstructible from its coordinate projection counting functions. They called them *sets of uniqueness*, and observed that there was no loss of generality in considering them as subsets of $\mathbb{N}^n$. They also introduced the notion of *additive sets* and proved that it was sufficient for uniqueness, but not necessary. Later, the author of this paper and Torres-Cházaro considered the case $n = 3$, and, by viewing those sets as 3-dimensional binary matrices, gave a characterization of sets of uniqueness using the dominance order of partitions [31]. Afterward, the author of this paper introduced a notion of additivity for matrices with nonnegative integer entries [35] and used it to give a characterization of additive sets in the sense of [8]. A different but equivalent definition of additivity appears already in Manivel's study of plethysm by means of Borel-Weil theory [16]. The first proof for our characterization of uniqueness [31] used character theory of the symmetric group (this proof can be translated into a purely combinatorial one [5]). At that time, we thought to apply the representation theory of the symmetric group to learn about uniqueness. It turned the other way round. Direct applications of discrete tomography to Kronecker coefficients were given in [1, 34]. These are, to my best knowledge, the first applications of discrete tomography to Kronecker coefficients. Here, we apply ideas from [21, 25, 31, 32, 34, 35, 36, 37, 38] to prove additive stability, give examples and get some related results.

In order to state our main theorem we need the following definition, which is fundamental for this paper. A matrix $A = (a_{i,j})$ of size $p \times q$ is called *additive* (see [35, Thm. 1]), if there exist real numbers $x_1, \dots, x_p, y_1, \dots, y_q$, such that

$$a_{i,j} > a_{k,l} \implies x_i + y_j > x_k + y_l,$$

for all $1 \le i, k \le p$ and all $1 \le j, l \le q$. Let $\alpha, \beta$ be partitions of the same size. Denote by $M(\alpha, \beta)$ the set of matrices $A$ with nonnegative integer entries, row-sum vector $\alpha$ and column-sum vector $\beta$. Also denote by $\pi(A)$ the sequence of entries of $A$ arranged in weakly decreasing order. Our main result is

**Theorem (Additive stability) 1.1** Let $\alpha, \beta, \gamma$ be partitions of the same size. If there is an additive matrix $A \in M(\alpha, \beta)$ with $\pi(A) = \gamma$, then, for any triple of partitions $\lambda, \mu, \nu$ of the same size, the sequence
$\{g(\lambda + n\alpha, \mu + n\beta, \nu + n\gamma)\}_{n \in \mathbb{N}_0}$ is weakly increasing and bounded from above. In particular, there is a positive integer $L$ such that, for all $n \ge L$,

$$g(\lambda + n\alpha, \mu + n\beta, \nu + n\gamma) = g(\lambda + L\alpha, \mu + L\beta, \nu + L\gamma).$$

This theorem appears in [41]. It is implicit in [16] and is made explicit in [17]. Manivel's proof uses Borel-Weil theory and is of very different nature from ours.

Triples of partitions $(\alpha, \beta, \gamma)$ such that the sequence $\{g(\lambda + n\alpha, \mu + n\beta, \nu + n\gamma)\}_{n \in \mathbb{N}_0}$ is weakly increasing and bounded from above for all triples of partitions $\lambda, \mu, \nu$ are called *stable* ([28]). So, the additive stability theorem can be rephrased by saying that any additive matrix $A$ yields a stable triple, or more precisely, if $A \in M(\alpha, \beta)$ is an additive matrix with $\pi(A) = \gamma$, then $(\alpha, \beta, \gamma)$ is a stable triple.

The next two results are new instances of stability. They follow from the additivity of matrices $B$ and $C$ in Example 3.12.

**Corollary 1.2** Let $a, b, c$ be nonnegative integers. Then, the triple

$$((b + c + 1, 1^a), (a + c + 1, 1^b), (c + 1, 1^{a+b}))$$

is stable.

**Corollary 1.3** For any $k \in \mathbb{N}$, the triple

$$((\binom{k+1}{2}, \dots, \binom{2}{2}), (\binom{k+1}{2}, \dots, \binom{2}{2}), (k, (k-1)^2, \dots, 1^k))$$

is stable.

Next Corollary follows from the additivity of the matrix $A$ in Example 3.13. It also appears as Example 6.3(b) in [28].

**Corollary 1.4** Let $\alpha$ be a partition. Then, the triple $(\alpha, \alpha', (1^{|\alpha|}))$ is stable.

Stembridge's hypothesis (6) and additivity are closely related. In Section 6 we show that additivity implies condition (6), and that this condition implies the existence of certain unique additive matrix. The advantage of our hypothesis is that it is far easier to find examples of additive matrices than to find examples of partitions $\alpha, \beta, \gamma$ satisfying (6). Therefore, it is much easier to find new examples of stability. Another advantage is that there is already a body of results concerning additive matrices [8, 9, 21, 25, 32, 35, 37, 38].

This manuscript is an extended abstract of [41]. It is organized as follows. Section 2 contains some notation. Section 3 contains a summary of all results about uniqueness and additivity required for this paper, as well as examples and one application to Kronecker coefficients needed in the proof of additive stability. In Section 4 we present a geometric characterization of additivity from [21]. This is fundamental in the proof of the main theorem, sketched in Section 5, and also in Section 6, where we study the relation between additivity and condition (6). We also present a new characterization of additivity (Theorem 6.4), that might be of interest in discrete tomography. Finally, in section 7, we relate additive stability to the previous known cases of stability of Kronecker coefficients.
## 2 Notation

We assume the reader is familiar with the standard results in the representation theory of the symmetric group (see for example [13, 15, 23, 27]). We use throughout the following notation: $\mathbb{N}$ is the set of positive integers, $\mathbb{N}_0 = \mathbb{N} \cup \{0\}$, and, for any $n \in \mathbb{N}_0$, $[n] = \{1, \dots, n\}$, so that $[0] = \emptyset$. If $\lambda = (\lambda_1, \dots, \lambda_p)$ is a partition (a weakly decreasing sequence of positive integers), we denote its size $\sum_{i \in [p]} \lambda_i$ by $|\lambda|$ and its length $p$ by $\ell(\lambda)$. If $|\lambda| = n$, we also write $\lambda \vdash n$. The notation $\lambda = (1^{a_1}, 2^{a_2}, \dots)$ means that $\lambda$ has $a_i$ parts equal to $i$. We denote by $\lambda'$ the partition conjugate to $\lambda$, obtained by transposing the diagram of $\lambda$. The depth of $\lambda$ is $d(\lambda) = |\lambda| - \lambda_1$. If $\lambda$ and $\mu$ are two partitions of length $p$ and $q$, respectively, and $p \le q$, we denote $\lambda_{p+1} = \dots = \lambda_q = 0$ and define its sum by

$$ \lambda + \mu = (\lambda_1 + \mu_1, \dots, \lambda_q + \mu_q). $$

Given two partitions $\lambda, \mu$ of $n$ we write $\lambda \succ \mu$ to indicate that $\lambda$ is greater than or equal to $\mu$ in the dominance order of partitions. We write $\lambda \succ \mu$, if $\lambda \succ \mu$ and $\lambda \neq \mu$. The number of semistandard Young tableaux of shape $\lambda$ and content $\nu$ is denoted by $K_{\lambda\nu}$.

For any partition $\lambda \vdash n$, we denote by $\chi^\lambda$ the irreducible character of $S_n$ associated to $\lambda$, and, for any partition $\nu = (\nu_1, \dots, \nu_r)$ of $n$, by $\phi^\nu = \text{Ind}_{S_\nu}^{S_n}(1_\nu)$ the permutation character associated to $\nu$. That is, $\phi^\nu$ is the character induced from the trivial character of the Young subgroup $S_\nu = S_{\nu_1} \times \dots \times S_{\nu_r}$ to $S_n$.

## 3 Discrete tomography

In this section we gather several results from discrete tomography that are used to prove additive stability. These results have been obtained mainly by the author of this note and his collaborators along the years. Some of them have been recently rediscovered by Stembridge and appear in [28, §6]. Applications of discrete tomography to Kronecker coefficients have already been given before in [34, 1]. Two notions from discrete tomography are relevant for this paper: uniqueness and additivity of 3-dimensional binary matrices (see [9, 38]). They are related to the notions of minimality, $\pi$-uniqueness [31, 37] and additivity [35, 21, 37], which are defined for matrices with nonnegative integer entries. Below we explain these concepts, the relations among them, give examples and show how they are related to Kronecker coefficients.

**Integral matrices 3.1** Let $A = (a_{i,j})$ be a matrix of size $p \times q$. We associate to $A$ two compositions and one partition. For each $i \in [p]$ and each $j \in [q]$, one defines

$$ \alpha_i = \sum_{y \in [q]} a_{i,y} \quad \text{and} \quad \beta_j = \sum_{x \in [p]} a_{x,j}. $$

Then, $\alpha = (\alpha_1, \dots, \alpha_p)$ is called the row-sum vector and $\beta = (\beta_1, \dots, \beta_q)$ the column-sum vector of $A$. We denote by $\pi(A)$ the vector of entries of $A$ arranged in weakly decreasing order. Then, $\pi(A)$ is a partition called the $\pi$-sequence of $A$. We say that $A$ is a plane partition if it has nonnegative integer entries and its rows and columns are weakly decreasing. For the applications we have in mind we assume, from now on, without loss of generality, that the row-sum and column-sum vectors are weakly decreasing. Otherwise we just permute rows and columns.

We denote by $M(\alpha, \beta)$ the set of all matrices $A = (a_{i,j})$ with nonnegative integer entries, row-sum vector $\alpha$ and column-sum vector $\beta$. If $\gamma$ is a partition, we denote by $M(\alpha, \beta)_\gamma$ the set of all matrices in $M(\alpha, \beta)$ with $\pi$-sequence $\gamma$.
**Binary matrices 3.2** Let $A = (a_{i,j,k})$ be a matrix of size $p \times q \times r$ with entries in $\{0, 1\}$ (we call it a binary matrix for short). We associate to $A$ three compositions. For each $i \in [p]$, $j \in [q]$ and $k \in [r]$, one defines

$$ \alpha_i = \sum_{(y,z) \in [q] \times [r]} a_{i,y,z}, \quad \beta_j = \sum_{(x,z) \in [p] \times [r]} a_{x,j,z} \quad \text{and} \quad \gamma_k = \sum_{(x,y) \in [p] \times [q]} a_{x,y,k}. $$

Then, the compositions $\alpha = (\alpha_1, \dots, \alpha_p)$, $\beta = (\beta_1, \dots, \beta_q)$, $\gamma = (\gamma_1, \dots, \gamma_r)$ are called the *1-marginals* of $A$. See, for example [7], where 3-dimensional binary matrices are called three-way statistical tables. For the applications we have in mind we assume, **from now on**, without loss of generality, that the 1-marginals are weakly decreasing. Otherwise we just permute 2-dimensional slices.

We denote by $M^*(\alpha, \beta, \gamma)$ the set of all 3-dimensional binary matrices with 1-marginals $\alpha, \beta, \gamma$, and by $m^*(\alpha, \beta, \gamma)$ its cardinality. A matrix $X \in M^*(\alpha, \beta, \gamma)$ is called a *matrix of uniqueness* [8], if $m^*(\alpha, \beta, \gamma) = 1$.

**More on integral matrices 3.3** Let $\alpha, \beta$ be partitions of the same size and let $A = (a_{i,j}) \in M(\alpha, \beta)$. We say that $A$ is *minimal* [31] if there is no matrix $B \in M(\alpha, \beta)$ such that $\pi(B) \prec \pi(A)$, and we say that $A$ is *$\pi$-unique* if there is no other matrix $B \in M(\alpha, \beta)$ such that $\pi(B) = \pi(A)$. Suppose $A$ has size $p \times q$, and let $r$ be the maximum of the entries of $A$. The *graph* of $A$ is the 3-dimensional binary matrix $G(A) = (a_{i,j,k})$ defined, for all $(i, j, k) \in [p] \times [q] \times [r]$, by

$$ a_{i,j,k} = \begin{cases} 1 & \text{if } 1 \le k \le a_{i,j}; \\ 0 & \text{otherwise.} \end{cases} $$

Note that, if $A \in M(\alpha, \beta)_\gamma$, then $G(A) \in M^*(\alpha, \beta, \gamma')$. Therefore,

$$ G : M(\alpha, \beta)_\gamma \rightarrow M^*(\alpha, \beta, \gamma') $$

is a well-defined injective map. If $X$ is the image $G(A)$ of a plane partition $A$, then $X$ is called the *diagram* of $A$ [26] or *pyramid* [32].

The next theorem relates the property of uniqueness for binary matrices to properties of integral matrices. Part of it was recently rediscovered by J. Stembridge (see [28, Thm. 6.4]).

**Theorem 3.4** [31, Thm. 1] Let $\alpha, \beta, \gamma$ be partitions. Then $m^*(\alpha, \beta, \gamma') = 1$ if and only if there is a matrix $A \in M(\alpha, \beta)_\gamma$ that is minimal and $\pi$-unique. Moreover, if $A \in M(\alpha, \beta)$ is minimal and $\pi$-unique, then $A$ is a plane partition.

To the best of our knowledge, the first application of uniqueness to Kronecker coefficients is Theorem 1.1 in [34]. Here, we need only a particular case, which was recently rediscovered by J. Stembridge [28, Thm. 6.4].

**Theorem 3.5** [34, Cor. 4.2] Let $A \in M(\alpha, \beta)_\gamma$ be a matrix that is minimal and $\pi$-unique. Then,

$$ g(\alpha, \beta, \gamma) = 1. $$

Now we turn to the notion of additivity, which is fundamental for our main theorem. It appears already, with no name, in [35].
**Definition 3.6** Let $A = (a_{i,j})$ be a matrix of size $p \times q$. Then, $A$ is called *additive* [37, § 6] if there exist real numbers $x_1, \dots, x_p, y_1, \dots, y_q$ such that

$$a_{i,j} > a_{k,l} \implies x_i + y_j > x_k + y_l,$$

for all $i, k \in [p]$ and all $j, l \in [q]$. Even though the definition makes sense in general, we will be concerned only with matrices having nonnegative entries. In this section we work with matrices having integer entries, in Section 4 with matrices having real entries.

In the next example we illustrate the concepts of minimal, $\pi$-unique and additive (see Example 8 in [38]).

**Example 3.7** Let

$$A = \begin{bmatrix} 3 & 3 & 1 \\ 2 & 1 & 1 \\ 2 & 0 & 0 \end{bmatrix}, \quad B = \begin{bmatrix} 4 & 4 & 1 \\ 2 & 1 & 1 \\ 2 & 0 & 0 \end{bmatrix} \quad \text{and} \quad C = \begin{bmatrix} 4 & 3 & 2 \\ 3 & 1 & 0 \\ 1 & 1 & 0 \end{bmatrix}.$$

The three matrices $A, B, C$ are plane partitions. The first one is minimal, but not $\pi$-unique. The matrix $B$ is $\pi$-unique, but not minimal. Finally the matrix $C$ is additive. To see this take $(x_1, x_2, x_3) = (7, 2, 0)$ and $(y_1, y_2, y_3) = (6, 3, 0)$.

Now we show some relations between being additive, minimal, $\pi$-unique and a plane partition. We start with the following result. Part of it was recently rediscovered by J. Stembridge (see [28, Prop. 6.9]).

**Theorem 3.8** [35, Thm. 2] Let $A \in M(\alpha, \beta)$ of size $2 \times q$. Then, the conditions of $A$ being a plane partition; minimal and $\pi$-unique; and additive are equivalent.

This result does not hold in general. Already, the matrix $A$ in Example 3.7 is a plane partition that is not $\pi$-unique, and $B$ is a plane partition that is not minimal. Obstructions for a plane partition $A$ of size $3 \times 3$ to be minimal and $\pi$-unique are given in [32, §5]. These correspond to the obstructions for additivity given by the arrow diagram in [25, Fig. 3] and its transpose. It is not difficult to show that these are all obstructions to additivity for a plane partition of size $3 \times 3$ (see [24, Ch. 2]). Compare with Proposition 6.11 in [28]. We have however one implication.

**Theorem 3.9** [35, Thm. 6.1] Let $A$ be an additive matrix, then $A$ is minimal and $\pi$-unique.

The converse is not true (see [37, Ex. 7.4] and [25, §3]).

**Example 3.10** The matrix

$$A = \begin{bmatrix} 5 & 5 & 5 & 4 & 4 \\ 5 & 5 & 5 & 3 & 3 \\ 3 & 3 & 1 & 1 & 0 \\ 2 & 1 & 1 & 1 & 0 \\ 2 & 1 & 0 & 0 & 0 \end{bmatrix}$$

is minimal and $\pi$-unique but not additive.

Next result follows from Theorems 3.4, 3.5 and 3.9. Part of it also appears in [16].
**Theorem 3.11** Let $A \in M(\alpha, \beta)_{\gamma}$ be additive. Then A is a plane partition and

$$g(\alpha, \beta, \gamma) = 1.$$

**Examples 3.12** The following are additive matrices

$$A = \begin{bmatrix} r & \cdots & r \\ \vdots & \ddots & \vdots \\ r & \cdots & r \end{bmatrix}, \quad B = \begin{bmatrix} c+1 & 1 & \cdots & 1 \\ 1 & 0 & \cdots & 0 \\ \vdots & \ddots & \ddots & \vdots \\ 1 & 0 & \cdots & 0 \end{bmatrix}, \quad C = \begin{bmatrix} k & k-1 & \cdots & 2 & 1 \\ k-1 & k-2 & \cdots & 1 & 0 \\ \vdots & \vdots & \ddots & \vdots & \vdots \\ 2 & 1 & \cdots & 0 & 0 \\ 1 & 0 & \cdots & 0 & 0 \end{bmatrix}.$$

The graph of A is a 3-dimensional box of size $p \times q \times r$; the graph of B is called tripod, it has size $(a+1) \times (b+1) \times (c+1)$ and 1-marginals $(b+c+1, 1^a)$, $(a+c+1, 1^b)$, and $(a+b+1, 1^c)$. The graph of C is a pyramid of size $k \times k \times k$.

**Example 3.13** Let $\alpha$ be a partition. Let A be the only binary matrix in $M(\alpha, \alpha')$. Then A is additive. For example, if $\alpha = (4, 2, 1)$, then

$$A = \begin{bmatrix} 1 & 1 & 1 & 1 \\ 1 & 1 & 0 & 0 \\ 1 & 0 & 0 & 0 \end{bmatrix}.$$

To see that A is additive take $x_i = \alpha_i$ and $y_j = (\alpha')_j$.

**Symmetries of plane partitions 3.14** There is a group $T$ of order 12 of operations on plane partitions. These operations are very natural if we look at the graph or diagram of a plane partition. The group is generated by a rotation of order 3, a transposition of order 2 and a complementation of order 2, see [26, § 2]. It is not difficult to prove that these operations preserve additivity. Therefore, given any additive matrix, we can generate up to 12 different additive matrices.

**Definition 3.15** We say that $(\alpha, \beta, \gamma)$ is an *additive triple* if there is an additive matrix $A \in M(\alpha, \beta)_{\gamma}$. Using rotations and transpositions on $G(A)$ we obtain that $(\gamma', \alpha, \beta')$, $(\beta, \gamma', \alpha')$, $(\beta, \alpha, \gamma)$, $(\alpha, \gamma', \beta')$ and $(\gamma', \beta, \alpha')$ are also additive triples.

Theorem 1.1 can be reformulated by saying that any additive triple is stable. The converse is not true since the triple ((2, 2), (2, 2), (2, 2)) is stable [28], but not additive.

**Remark 3.16** The additive triples $(\alpha, \beta, \gamma)$ and $(\gamma', \alpha, \beta')$ yield different stability properties. The identity $g(\lambda, \mu, \nu) = g(\lambda, \mu', \nu')$ and other symmetries of Kronecker coefficients are not enough to prove that they yield the same stability property, because, in general $(\mu + \beta)' \neq \mu' + \beta'$.

**Example 3.17** Let $\beta = (\beta_1, \dots, \beta_b) \vdash n$. Then, $B = [\beta_1 \cdots \beta_b]$ is an additive matrix and $((n), \beta, \beta)$ is an additive triple. Hence, also $(\beta, \beta', (1^n))$ is an additive triple. This is Example 3.13.

**Obstructions to additivity 3.18** There are also ways of proving that a matrix is not additive. In [25, Thm. 3.8] we showed that certain arrow diagrams are obstructions to additivity. While the case of two rows is fairly simple (Theorem 3.8), the general case is much more complex. We showed in [25, § 5] that there are infinitely many essentially different obstructions needed for deciding additivity of plane partitions with three rows.
## 4 Geometry of additive matrices

In this section we explain a geometric characterization of additivity from [21]. It will be central in our proof of additive stability. We start by extending some notions defined for objects with integer entries to objects with real entries. For a vector $a = (a_1, \dots, a_m) \in \mathbb{R}^m$, we denote by $\pi(a) = (a_{[1]}, \dots, a_{[m]})$ the vector formed by the entries of $a$ arranged in weakly decreasing order. We say that $a$ is majorized by $b = (b_1, \dots, b_m)$ (see [10, 18]), and denote it by $a \preceq b$, if

$$ \sum_{i=1}^{m} a_i = \sum_{i=1}^{m} b_i, \quad \text{and} \quad \sum_{i=1}^{k} a_{[i]} \le \sum_{i=1}^{k} b_{[i]}, \quad \text{for all } k \in [m]. $$

If $a \preceq b$ and $\pi(a) \neq \pi(b)$, then we write $a \prec b$.

Let $\alpha, \beta$ be two partitions of the same size. Denote by $\mathcal{T}(\alpha, \beta)$ the set of all matrices with nonnegative real entries, row-sum vector $\alpha$ and column-sum vector $\beta$. $\mathcal{T}(\alpha, \beta)$ is called a transportation polytope. We say that a matrix $A \in \mathcal{T}(\alpha, \beta)$ is real-minimal [21], if there is no other matrix $B \in \mathcal{T}(\alpha, \beta)$ such that $\pi(B) \prec \pi(A)$.

**Theorem 4.1** [21, Thm. 6.2] Let $A \in \mathcal{T}(\alpha, \beta)$. Then $A$ is additive if and only if $A$ is real-minimal.

Let $a \in \mathbb{R}^m$ and $\rho \in S_m$. Denote by $a_\rho$ the vector $(a_{\rho(1)}, \dots, a_{\rho(m)})$. The permutohedron determined by $a$ is the convex hull of the set of all vectors obtained by permuting the entries of $a$:

$$ P(a) = \operatorname{conv}\{a_\rho \mid \rho \in S_m\}. $$

In order to state our next results, we denote, by $M_{p,q}$ the set of all matrices with real entries of size $p \times q$ and define a linear isomorphism $\Phi : M_{p,q} \to \mathbb{R}^{pq}$, for each $A = (a_{i,j})$, by

$$ \Phi(A) = (a_{11}, a_{12}, \dots, a_{1q}, a_{21}, a_{22}, \dots, a_{2q}, \dots, a_{p1}, a_{p2}, \dots, a_{pq}). $$

We have the following characterization of real-minimality.

**Proposition 4.2** [21, Cor. 5.2] Let $A \in \mathcal{T}(\alpha, \beta)$. Then $A$ is real-minimal if and only if

$$ P(\Phi(A)) \cap \Phi(\mathcal{T}(\alpha, \beta)) = \{\Phi(A)\}. $$

Next result is fundamental in our proof of additive stability. It is a consequence of Theorem 4.1 and Proposition 4.2.

**Theorem 4.3** Let $A \in \mathcal{T}(\alpha, \beta)$. Then $A$ is additive if and only if

$$ P(\Phi(A)) \cap \Phi(\mathcal{T}(\alpha, \beta)) = \{\Phi(A)\}. $$

The following example disproves Conjecture 6.7 in [28].

**Example 4.4** Let

$$ A = \begin{bmatrix} 5 & 5 & 5 & 4 & 4 \\ 5 & 5 & 5 & 3 & 3 \\ 3 & 3 & 1 & 1 & 0 \\ 2 & 1 & 1 & 1 & 0 \\ 2 & 1 & 0 & 0 & 0 \end{bmatrix} \quad \text{and} \quad X = \begin{bmatrix} 0 & 0 & 0 & -1 & 1 \\ 0 & 0 & 1 & -1 & 0 \\ 0 & 1 & 0 & 0 & -1 \\ -1 & -1 & 0 & 2 & 0 \\ 1 & 0 & -1 & 0 & 0 \end{bmatrix}. $$
The matrix $X$ comes from the obstruction to additivity given in [25, Fig. 4]. Let $\alpha = (23, 21, 8, 5, 3)$, $\beta = (17, 15, 12, 9, 7)$. Since the row-sum and column-sum vectors of $X$ are zero, $A$ and $A - \frac{1}{2}X$ are elements of $\mathcal{T}(\alpha, \beta)$. We know, by Example 3.10, that $A$ is minimal and $\pi$-unique. One easily checks that $\pi(A - \frac{1}{2}X) \prec \pi(A)$. Therefore $A$ is not real minimal. Hence, $\mathcal{P}(\Phi(A)) \cap \Phi(\mathcal{T}(\alpha, \beta))$ has only one integer point, but it is not 0-dimensional.

# 5 Sketch of the proof of additive stability

For each convex polytope $P$ let us denote by $\#P$ the number of integer points in $P$.

Next result follows from Theorem 4.3 and a close analysis of the convergence of the sequence of polytopes $\{\mathcal{P}(\frac{1}{n}\nu + \gamma) \cap \Phi(\mathcal{T}(\frac{1}{n}\lambda + \alpha, \frac{1}{n}\mu + \beta))\}_{n \in \mathbb{N}}$ to $\mathcal{P}(\gamma) \cap \Phi(\mathcal{T}(\alpha, \beta))$ in the Hausdorff metric.

**Theorem 5.1** Let $A \in \mathbf{M}(\alpha, \beta)_\gamma$ be additive. Then, for any triple of partitions $\lambda, \mu, \nu$ of the same size, the sequence of integers

$$ \{\#\mathcal{P}(\nu + n\gamma) \cap \Phi(\mathcal{T}(\lambda + n\alpha, \mu + n\beta))\}_{n \in \mathbb{N}} $$

is weakly increasing and bounded from above.

The proof of additive stability combines Theorem 5.1 and Proposition 5.2 in [28] and a well-known formula for the Kronecker product of two permutation characters.

# 6 Relation between Stembridge's hypothesis and additivity

In this Section we show the relation between Stembridge's hypothesis (6) and additivity.

**Theorem 6.1** Let $A \in \mathbf{M}(\alpha, \beta)_\gamma$ be an additive matrix. Then, $\langle \phi^{n\alpha} \otimes \phi^{n\beta}, \chi^{n\gamma} \rangle = 1$, for all $n \in \mathbb{N}$.

If $\langle \phi^{n\alpha} \otimes \phi^{n\beta}, \chi^{n\gamma} \rangle = 1$, for all $n \in \mathbb{N}$, we cannot assure the existence of an additive matrix in $\mathbf{M}(\alpha, \beta)_\gamma$ (see Example 6.3). But we can prove.

**Theorem 6.2** Let $\alpha, \beta, \gamma$ be partitions of the same size. If $\langle \phi^{n\alpha} \otimes \phi^{n\beta}, \chi^{n\gamma} \rangle = 1$, for all $n \in \mathbb{N}$. Then, there is a unique matrix $A \in \mathcal{P}(\gamma) \cap \mathbf{M}(\alpha, \beta)$. Besides $A$ is additive and $K_{\gamma, \pi(A)} = 1$.

Compare with Theorem 6.1 in [28].

**Example 6.3** Let $\alpha = (7, 1)$, $\beta = (5, 3)$ and $\gamma = (4, 4)$. We will show that $\langle \phi^{n\alpha} \otimes \phi^{n\beta}, \chi^{n\gamma} \rangle = 1$, for all $n \in \mathbb{N}$, and that there is no additive matrix in $\mathbf{M}(\alpha, \beta)_\gamma$. First, note that $\mathbf{M}(\alpha, \beta)_\gamma = \emptyset$. Hence, the second assertion holds. For each $t \in \mathbb{N}$, let $X_t = \left[ \begin{smallmatrix} 4n+t & 3n-t \\ n-t & t \end{smallmatrix} \right]$. Then, $\mathbf{M}(n\alpha, n\beta) = \{X_t \mid 0 \le t \le n\}$. The only $t$ for which, $\pi(X_t) \le n\gamma$, is $t = 0$. The first assertion follows from $K_{n\gamma, n(4,3,1)} = 1$.

We also obtain a new characterization of additivity.

**Theorem 6.4** Let $A$ be a plane partition. Then $A$ is additive if and only if $nA$ is minimal and $\pi$-unique, for all $n \in \mathbb{N}$.

**Example 6.5** Let $A$ and $X$ be defined as in Example 4.4. We now that $A$ is minimal and $\pi$-unique, but not additive (Example 3.10). Besides $2A$ is not minimal because $\pi(2A - X) \prec \pi(2A)$.
# 7 Relations between additive stability and other stability known results

In this section we explore the relation of previous stability known results to additive stability.

Let us consider the additive triples $((|\alpha|), \alpha, \alpha)$ and $(\alpha, \alpha', (1^{|\alpha|}))$, see Example 3.17. Practically, all known stability properties follow from Theorem 1.1 applied to some instance of one of these triples, together with some symmetry of Kronecker coefficients. In other words, every known stability property is related, up to symmetry of its graph (Paragraph 3.14), to some particular case of the additive matrix from Example 3.17, or equivalently, to some particular case of the additive matrix from Example 3.13. The power of additive stability is that we can construct very easily many other examples of additive matrices, thus producing new instances of stability. However, the method of proof of this theorem does not produce an explicit bound $L$ for stability.

Murnaghan's stability (1) follows from $\alpha = (1)$. The stability from equation (4), which includes (2) as a particular case, follows, in case $n_1 = \cdots = n_t$, from Theorem 1.1 applied to the additive triple $((|\alpha|), \alpha, \alpha)$ together with the symmetry $g(\zeta, \eta, \theta) = g(\eta, \theta, \zeta)$. The diagrammatic method from [40] provides better results in the case of the triple $((|\alpha|), \alpha, \alpha)$, because it gives very precise bounds for stability and also because it permits to consider independent parameters $n_1, \dots, n_t$ in equation (4).

Finally, the stability property from equation (5) follows from Theorem 1.1 applied to the additive triple $(\alpha, \alpha', (1^{|\alpha|}))$ in the particular case in which $\alpha = (q^r)$ is a rectangular partition, together with a symmetry of Kronecker coefficients. Formula (5) gives, under some conditions, a very good bound for stability, which is useful in some applications (see [39, §5]).

# Acknowledgements

I would like to thank to Richard Brualdi, Jesús De Loera, Laurent Manivel, Shmuel Onn, Igor Pak, Greta Panova and Adolfo Torres-Cházaro for fruitful conversations.

# References

[1] D. Avella-Alaminos and E. Vallejo, Kronecker products and the RSK correspondence, *Discrete Math.* **312** (2012), 1476–1486.

[2] C. Bowman, M. De Visscher and R. Orellana, The partition algebra and the Kronecker coefficients, to appear in *Trans. A.M.S.*.

[3] E. Briand, R. C. Orellana and M. Rosas, The stability of the Kronecker product of Schur functions, *J. Algebra* **331** (2011), 11–27.

[4] M. Brion, Stable properties of plethysm: on two conjectures of Foulkes, *manuscripta math.* **80** (1993), 347–371.

[5] R. Brualdi, Minimal nonnegative integral matrices and uniquely determined (0, 1)-matrices, *Linear Algebra Appl.* **314** (2002), 351–356.

[6] T. Church, J.S. Ellenberg and B. Farb. FI-modules: a new approach to stability for $S_n$-representations, arXiv:1204.4533v2 [math.RT], 28 Jun 2012.

[7] J. De Loera and E.D. Kim, Combinatorics and geometry of transportation polytopes: an update, arXiv:1307.0124v1, 29 Jun 2013.

[8] P.C. Fishburn, J.C. Lagarias, J.A. Reeds and L.A. Shepp, Sets uniquely determined by projections on axes II. Discrete case, *Discrete Math.* **91** (1991), 149–159.

[9] P.C. Fishburn and L.A. Shepp, Sets of uniqueness and additivity in integer lattices. In: Herman, G.T., Kuba, A. (eds.), *Discrete Tomography: Foundations, Algorithms, and Applications* Birkhäuser, Boston, pp. 35–58 (1999).

[10] G. Hardy, J.E. Littlewood and G. Pólya, “Inequalities”, Second ed., Cambridge Univ. Press, 1952.

[11] G.T. Herman and A. Kuba, editors, “Discrete Tomography: Foundations, Algorithms, and Applications”, Birkhäuser, Boston, 1999.
[12] G.T. Herman and Attila Kuba, editors, "Advances in Discrete Tomography and Its Applications", Applied and Numerical Harmonic Analysis, Birkhäuser, Boston, 2007.

[13] G.D. James and A. Kerber, "The representation theory of the symmetric group", Encyclopedia of mathematics and its applications, Vol. 16, Addison-Wesley, Reading, Massachusetts, 1981.

[14] D.E. Littlewood, Products and plethysms of characters with orthogonal, symplectic and symmetric groups, *Canad. J. Math.* **10** (1958), 17–32.

[15] I.G. Macdonald, "Symmetric functions and Hall polynomials", 2nd. edition, Oxford Mathematical Monographs Oxford Univ. Press 1995.

[16] L. Manivel, Applications de Gauss et pléthysme, *Ann. Inst. Fourier* **47** (1997), 715–773.

[17] L. Manivel, On the asymptotics of Kronecker coefficients, preprint, October 14, 2014.

[18] A.W. Marshall, I. Olkin, "Inequalities: Theory of majorization and its applications", Academic Press, 1979.

[19] F.D. Murnaghan, The analysis of the Kronecker product of irreducible representations of the symmetric group, *Amer. J. Math.* **60** (1938), 761–784.

[20] F.D. Murnaghan, On the analysis of the Kronecker product of irreducible representations of $S_n$, *Proc. Nat. Acad. Sci. USA* **41** (1955), 515–518.

[21] S. Onn and E. Vallejo, Permutohedra and minimal matrices, *Linear Algebra Appl.* **412** (2006), 471–489.

[22] I. Pak and G. Panova, Bounds on the Kronecker coefficients, arXiv:1406.2988v2, 16 Jun 2014.

[23] B.E. Sagan, "The Symmetric Group," 2nd. ed., Graduate Texts in Mathematics 203, Springer Verlag, 2001.

[24] M. Santoyo, Aditividad para matrices y (0, 1)-aditividad para pirámides, Ph. D Thesis, Universidad Michoacana de San Nicolás de Hidalgo, 2008.

[25] M. Santoyo and E. Vallejo, Additivity obstructions for integral matrices and pyramids, *Theoret. Comput. Sci.* **406** (2008), 136–145.

[26] R.P. Stanley, Symmetries of plane partitions, *J. Combin. Theory. Ser. A* **43** (1986), 103–113.

[27] R.P. Stanley, "Enumerative Combinatorics, Vol. 2", Cambridge Studies in Advanced Mathematics 62. Cambridge Univ. Press, 1999.

[28] J.R. Stembridge, Generalized stability of Kronecker coefficients, preprint.

[29] J.R. Stembridge, Appendix to: Generalized stability of Kronecker coefficients, preprint.

[30] J.Y. Thibon, Hopf algebras of symmetric functions and tensor products of symmetric group representations, *Internat. J. Algebra Comput.* **1** (1991), 207–221.

[31] A. Torres-Cházaro and E. Vallejo, Sets of uniqueness and minimal matrices. *J. Algebra* **208** (1998), 444–451.

[32] E. Vallejo, Reductions of additive sets, sets of uniqueness and pyramids, *Discrete Math.* **173** (1997), 257–267.

[33] E. Vallejo, Stability of Kronecker product of irreducible characters of the symmetric group, *Electron. J. Combin* **6** (1999) Research Paper 39, 7 pp.

[34] E. Vallejo, Plane partitions and characters of the symmetric group, *J. Algebraic Comb.* **11** (2000), 79–88.

[35] E. Vallejo, A characterization of additive sets, *Discrete Math.* **259** (2002), 201–210.

[36] E. Vallejo, The classification of minimal matrices of size $2 \times q$, *Linear Algebra Appl.* **340** (2002), 169–181.

[37] E. Vallejo, Minimal matrices and discrete tomography, *Electron. Notes Discrete Math.* **20** (2005), 113–132.

[38] E. Vallejo, Uniqueness and additivity for $n$-dimensional binary matrices with respect to their 1-marginals. In: Herman, G.T., Kuba, A. (eds.), *Advances in Discrete Tomography and its Applications*, Birkhäuser, Boston, pp. 83–112 (2007).

[39] E. Vallejo, A stability property for coefficients in Kronecker products of complex $S_n$ characters, *Electron. J. Combin* **16** (2009) #N22, 8 pp. (electronic).

[40] E. Vallejo, A diagrammatic approach to Kronecker squares, *J. Combin. Theory. Ser. A* **127** (2014), 243–285.

[41] E. Vallejo, Stability of Kronecker coefficients via discrete tomography, arXiv:1052389, 26 Aug 2014.