A short proof for the polynomiality of the stretched littlewood-Richardson coefficients

1. Introduction

The Littlewood-Richardson coefficients appear in many areas of mathematics [5,8,9, 12,17]. An example comes from the study of symmetric functions. The set of Schur functions $s_{\lambda }$, indexed by partitions $\lambda$, is a linear basis for the ring of symmetric functions. Thus, for any partitions $\lambda$ and $\mu$, the product of Schur functions $s_{\lambda }$ and $s_{\mu }$ can be uniquely expressed as $$\begin{array}{}\text{(1)}& \begin{array}{r}{s}_{\lambda }\cdot s_{\mu }=\sum _{\nu :|\nu |=|\lambda |+|\mu |}{c}_{\lambda ,\mu }^{\nu }{s}_{\nu },\end{array}\end{array}$$ for some real numbers $c_{\lambda ,\mu }^{\nu }$, where $|\lambda |$ denotes the sum of the parts of $\lambda$. The coefficient $c_{\lambda ,\mu }^{\nu }$ of $s_{\nu }$ in (1) is called the Littlewood-Richardson coefficient.

There are several ways to compute $c_{\lambda ,\mu }^{\nu }$ such as the Littlewood-Richardson rule [14], the Littlewood-Richardson triangles [10], the Berenstein-Zelevinsky triangles [1], and the honeycombs [7]. In this paper, we employ the hive model that was first introduced by Knutson and Tao [7]. The hive model imposes certain inequalities that allow us to compute $c_{\lambda ,\mu }^{\nu }$ as the number of integer points in a rational polytope, which we call a hive polytope.

For fixed partitions $\lambda ,\mu ,\nu$ such that $|\nu |=|\lambda |+|\mu |$, we define the stretched Littlewood-Richardson coefficients to be the function $c_{t\lambda ,t\mu }^{t\nu }$ for non-negative integers $t.$ The hive model implies that $$\begin{array}{r}{c}_{t\lambda ,t\mu }^{t\nu }=\text{ the number of integer points inthe }{t}^{\mathrm{t}\mathrm{h}}\text{-dilation of the hive polytope}.\end{array}$$

By Ehrhart theory (see Thoerem 2.1), $c_{t\lambda ,t\mu }^{t\nu }$ is a quasi-polynolmial in $t\in \mathbb{Z}$, which means $c_{t\lambda ,t\mu }^{t\nu }$ is a function of the form $a_d(t)t^d+\cdots +a_1(t)t+a_0(t)$ where each of $a_d(t),\dots ,a_0(t)$ is a periodic function in $t$ with an integral period. The function $c_{t\lambda ,t\mu }^{t\nu }$ was, however, observed and conjectured by King, Tollu, and Toumazet [6] to be a polynomial function in $t$ (as opposed to a quasi-polynomial). The conjecture was then shown to be true by Derksen-Weyman [3], and Rassart [11]. More precisely, they proved the following theorem.

The proof by Derksen and Weyman [3] makes use of semi-invariants of quivers. They proved a result on the structure of a ring of quivers and then derived the polynomiality of $c_{t\lambda ,t\mu }^{t\nu }$ as a special case. Later, Rassart [11] proved a stronger result, which gives Theorem 1.1 as an easy consequence, by showing that $c_{\lambda ,\mu }^{\nu }$ is a polynomial in variables $\lambda ,\mu ,\nu$ provided that they lie in certain polyhedral cones of a chamber complex. The proof by Rassart employs Steinberg’s formula, the hive conditions, and the Kostant partition function to give the chamber complex of cones in which $c_{\lambda ,\mu }^{\nu }$ is a polynomial in variables $\lambda ,\mu ,\nu$. A considerably large portion of Rassart’s paper was devoted to describing this chamber complex and showing its desired property, resulting in a fairly long justification. We note that although this chamber complex of cones was provided, it is in practice computationally hard to work out the cones.

Inspired by Rassart’s approach, we ask if similar tools can be utilized to give a simple proof of Theorem 1.1 directly. We found that Steinberg’s formula and a simple argument about the chamber complex of the Kostant partition function are indeed sufficient. The main objective of this paper is to give a short alternative proof of Theorem 1.1 using this idea.

2. Preliminaries

We begin this section by presenting necessary notations and theories related to polytopes and then describe the hive model for computing $c_{\lambda ,\mu }^{\nu }$. The hive model will help us understand the behavior of the stretched Littlewood-Richardson coefficients through a property of polytopes. We then introduce the Kostant partition functions and state Steinberg’s formula and related results that will later be used for proving Theorem 1.1.

2.1. Ehrhart theory

A polyhedron $P$ in ${\mathbb{R}}^d$ is the solution to a finite set of linear inequalities, that is, $$P=\{(x_1,\dots ,x_d)\in {\mathbb{R}}^d|\sum _{j=1}^d{a}_{ij}{x}_j\le b_i\text{ for }i\in I\},$$ where $a_{ij}\in \mathbb{R}$, $b_i\in \mathbb{R},$ and $I$ is a finite set of indices. A polytope is a bounded polyhedron. We can also equivalently define a polytope in ${\mathbb{R}}^d$ as the convex hull of finitely many points in ${\mathbb{R}}^d.$ A polytope is said to be rational if all of its vertices have rational coordinates, and is said to be integral if all of its vertices have integral coordinates. We refer readers to [18] for basic definitions regarding polyhedra.

For a polytope $P$ in ${\mathbb{R}}^d$ and a non-negative integer $t,$ the $t^{\mathrm{t}\mathrm{h}}$-dilation $tP$ is the set $\{tx|x\in P\}.$ We define $$i(P,t):=|{\mathbb{Z}}^d\cap tP|,$$ to be the number of integer points in the $t^{\mathrm{t}\mathrm{h}}$-dilation $tP.$

Recall that a quasi-polynomial is a function of the form $f(t)=a_d(t)t^d+\cdots a_1(t)t+a_0(t)$ where each of $a_d(t),\dots ,a_0(t)$ is a periodic function in $t$ with an integral period. The period of $f(t)$ is the least common period of $a_d(t),\dots ,a_0(t)$. Clearly, a quasi-polynomial of period one is a polynomial.

For a rational polytope $P$, the least common multiple of the denominators of the coordinates of its vertices is called the denominator of $P$. The behavior of the function $i(P,t)$ is described by the following theorem due to Ehrhart [4].

The polynomial (resp. quasi-polynomial) $i(P,t)$ is called the Ehrhart polynomial of $P$ (resp. Ehrhart quasi-polynomial of $P$).

2.2. The littlewood-Richardson coefficients

We say that $\lambda =({\lambda }_1,\dots ,{\lambda }_k)$ is a partition of a non-negative integer $m$ if ${\lambda }_1\ge \cdots \ge {\lambda }_k$ are positive integers such that ${\lambda }_1+\cdots +{\lambda }_k=m.$ For convenience, we will abuse the notation by allowing ${\lambda }_i$ to be zero. The positive numbers among ${\lambda }_1,\dots ,{\lambda }_k$ are called parts of $\lambda$. For example, $\lambda =(2,2,1,0)$ is a partition of $5$ with $3$ parts. We write $|\lambda |$ to denote ${\lambda }_1+\cdots +{\lambda }_k.$

A hive ${\mathrm{\Delta }}_k$ of size $k$ is an array of vertices $h_{ij}$ arranged in a triangular grid consisting of $k^2$ small equilateral triangles as shown in Figure 1. Two adjacent equilateral triangles form a rhombus with two equal obtuse angles and two equal acute angles. There are three types of these rhombi: tilted to the right, left, and vertical as shown in Figure 1.

Let $\lambda =({\lambda }_1,\dots ,{\lambda }_k),\mu =({\mu }_1,\dots ,{\mu }_k),\nu =({\nu }_1,\dots ,{\nu }_k)$ be partitions with at most $k$ parts such that $|\nu |=|\lambda |+|\mu |.$ A hive of type $(\nu ,\lambda ,\mu )$ is a labelling $(h_{i,j})$ of ${\mathrm{\Delta }}_k$ that satisfies the following hive conditions.

Boundary condition: The labelings on the boundary are determined by $\lambda ,\mu ,\nu$ in the following ways. $$\begin{array}{rlr}& h_{0,0}=0,h_{j,j}–h_{j-1,j-1}={\nu }_j,h_{0,j}–h_{0,j-1}={\lambda }_j,& \text{ for }1\le j\le k.\\ & h_{i,k}–h_{i-1,k}={\mu }_i,& \text{ for }1\le i\le k.\end{array}$$

Rhombi condition: For every rhombus, the sum of the labels at obtuse vertices is greater than or equal to the sum of the labels at acute vertices. That is, for $1\le i<j\le k,$ $$\begin{array}{rl}{h}_{i,j}–h_{i,j-1}& \ge h_{i-1,j}–h_{i-1,j-1},\\ h_{i,j}–h_{i-1,j}& \ge h_{i+1,j+1}–h_{i,j+1},\end{array}$$ and $$\begin{array}{rl}{h}_{i-1,j}–h_{i-1,j-1}& \ge h_{i,j+1}–h_{i,j}.\end{array}$$

Let $H_k(\nu ,\lambda ,\mu )$ denote the set of all hives of type $(\nu ,\lambda ,\mu )$. Then the hive conditions (HC1) and (HC2) imply that $H_k(\nu ,\lambda ,\mu )$ is a rational polytope in ${\mathbb{R}}^n$ where $n=(\genfrac{}{}{0ex}{}{k+2}{2})$. Hence, we will call $H_k(\nu ,\lambda ,\mu )$ the hive polytope of type $(\nu ,\lambda ,\mu )$. Knutson-Tao [7] and Buch [2] showed that $$c_{\lambda ,\mu }^{\nu }=\text{ the number ofinteger points in }{H}_k(\nu ,\lambda ,\mu ).$$

Example 2.2. Let $k=3$, $\nu =(4,3,1),\lambda =(2,1,0),$ and $\mu =(3,2,0)$, we have that $c_{\lambda ,\mu }^{\nu }=2$. The two corresponding integer points (integer labels) of $H_3(\nu ,\lambda ,\mu )$ are shown in Figure 2.

For fixed partitions $\lambda ,\mu ,\nu$ with at most $k$ parts such that $|\nu |=|\lambda |+|\mu |$, we define the the stretched Littlewood-Richardson coefficient to be the function $c_{t\lambda ,t\mu }^{t\nu }$ for non-negative integer $t.$ Because $$\begin{gathered} H_k(t\nu ,t\lambda , \\ t\mu )=t{H}_k(\nu ,\lambda ,\mu ) \end{gathered}$$, we have that $$c_{t\lambda ,t\mu }^{t\nu }=i(H_k(\nu ,\lambda ,\mu ),t).$$

Examples provided in [6] indicate that $H_k(\nu ,\lambda ,\mu )$ is in general not an integral polytope. Thus, by Ehrhart theory (Theorem 2.1), $c_{t\lambda ,t\mu }^{t\nu }$ is a quasi-polynomial in $t$. We will show that $c_{t\lambda ,t\mu }^{t\nu }$ is indeed a polynomial in $t$ even though the corresponding hive polytope $H_k(\nu ,\lambda ,\mu )$ is not integral.

2.3. Kostant partition function and Steinberg’s formula

We will show the polynomiality of $c_{t\lambda ,t\mu }^{t\nu }$ by using Steinberg’s formula as derived in [11] by Rassart and the chamber complex of the Kostant partition function. To this end, we state the related notations and results for later reference.

Let $e_1,\dots ,e_k$ be the standard basis vectors in ${\mathbb{R}}^k$, and let ${\mathrm{\Delta }}_{+}=\{e_i–e_j:1\le i<j\le k\}$ be the set of positive roots of the root system of type $A_{k-1}.$ We define $M$ to be the matrix whose columns consist of the elements of ${\mathrm{\Delta }}_{+}$. The Kostant partition function for the root system of type $A_{k-1}$ is the function $K:{\mathbb{Z}}^k⟶{\mathbb{Z}}_{\ge 0}$ defined by $$K(v)=|\{b\in {\mathbb{Z}}_{\ge 0}^{(\genfrac{}{}{0ex}{}{k}{2})}|Mb=v\}|.$$

That is, $K(v)$ equals the number of ways to write $v$ as nonnegative integer linear combinations of the positive roots in ${\mathrm{\Delta }}_{+}$.

An important property of the matrix $M$, when written in the basis of simple roots $\{e_i–e_{i+1}|i=1,\dots ,k-1\}$, is that it is totally unimodular, i.e. the determinant of every square submatrix equals $-1,0,$ or $1.$ Indeed, it was shown in [13] that a matrix $A$ is totally unimodular if every column of $A$ only consists of 0’s and 1’s in a way that the 1’s come in a consecutive block. Let $$\mathrm{c}\mathrm{o}\mathrm{n}\mathrm{e}({\mathrm{\Delta }}_{+})=\{\sum {\lambda }_{v}v|v\in {\mathrm{\Delta }}_{+},{\lambda }_v\ge 0\},$$ be the cone spanned by the vectors in ${\mathrm{\Delta }}_{+}.$ The chamber complex is the polyhedral subdivision of $\mathrm{c}\mathrm{o}\mathrm{n}\mathrm{e}({\mathrm{\Delta }}_{+})$ that is obtained from the common refinement of cones $\mathrm{c}\mathrm{o}\mathrm{n}\mathrm{e}(B)$ where $B$ are the maximum linearly independent subsets of ${\mathrm{\Delta }}_{+}$. A maximum cell (a cone of maximum dimension) $\mathcal{C}$ in the chamber complex is called a chamber. Since $M$ is totally unimodular, the behavior of $K(v)$ is given by the following lemma as a special case of [16, Theorem 1] due to Sturmfels.

Steinberg’s formula [15] expresses the tensor product of two irreducible representations of semisimple Lie algebras as the direct sum of other irreducible representations. When restricting the formula to ${\mathrm{S}\mathrm{L}}_k\mathbb{C}$, we obtain the following version of Steinberg’s formula for computing $c_{\lambda ,\mu }^{\nu }$.

Details of the derivation can be found in [11].

3. Proof of the polynomiality

We are now ready to prove Theorem 1.1.

In the proof of Theorem 1.1, we showed that every $K(r_{\sigma ,\tau }^{\lambda ,\mu ,\nu }(t))$ is eventually either the zero polynomial or a non-zero polynomial in $t$. Proposition 3.2 gives a characterization of those $K(r_{\sigma ,\tau }^{\lambda ,\mu ,\nu }(t))$ that eventually become nonzero polynomials. The proof uses the following characterization of nonzero $K(v)$.

Acknowledgment

I am grateful to Fu Liu. Her careful review and thoughtful comments significantly improved the exposition of this paper. I also would like to thank UC Davis’s College of Letter and Science for providing the Dean’s Summer Graduate Fellowship to support me during the summer of 2022.