A Shuffle Theorem for Paths Under Any Line

The shuffle theorem, conjectured by Haglund et al. [15] and proven by Carlsson and Mellit [6], is a combinatorial formula for the symmetric polynomial $\nabla e_{k}$ as a sum over LLT polynomials indexed by Dyck paths—that is, lattice paths from $(0,k)$ to $(k,0)$ that lie weakly below the line segment connecting these two points. Here $e_{k}$ is the $k$-th elementary symmetric function, and $\nabla$ is an operator on symmetric functions with coefficients in ${\mathbb{Q}}(q,t)$ that arises in the theory of Macdonald polynomials [3].

The polynomial $\nabla e_{k}$ is significant because it describes the character of the ring $R_{k}$ of diagonal coinvariants for the symmetric group $S_{k}$ [18, Proposition 3.5]. The character of $R_{k}$ had been conjectured in the early 1990s to have surprising connections with the enumeration of combinatorial objects such as trees and Dyck paths—for instance, its dimension is equal to the number $(k+1)^{k-1}$ of rooted trees on $k+1$ labelled vertices, and the multiplicity of the sign character is equal to the Catalan number $C_{k}$. A summary of these early conjectures, contributed by a number of people, can be found in [19]. More precisely, $\nabla e_{k}$ describes the character of $R_{k}$ as a doubly graded $S_{k}$ module. The double grading in $R_{k}$ thus gives rise to $(q,t)$-analogs of the numbers that enumerate the associated combinatorial objects. The conjectures connect specializations of these $(q,t)$-analogs with previously known $q$-analogs in combinatorics.

Using results in [10], the whole suite of earlier combinatorial conjectures follows from the character formula $\nabla e_{k}$ and the shuffle theorem.

Along with the formula for $\nabla e_{k}$ given by the shuffle theorem, Haglund et al. conjectured a combinatorial formula for $\nabla^{m}e_{k}$ as a sum over LLT polynomials indexed by lattice paths below the line segment from $(0,k)$ to $(km,0)$. Extending this, Bergeron et al. [4] conjectured, and Mellit [27] proved, an identity giving the symmetric polynomial $e_{k}[-MX^{m,n}]\cdot 1$ as a sum over LLT polynomials indexed by lattice paths below the segment from $(0,kn)$ to $(km,0)$, for any pair of positive integers expressed in the form $(km,kn)$ with $m,n$ coprime. Here we have written $e_{k}[-MX^{m,n}]$ for the operator on symmetric functions given by a certain element of the elliptic Hall algebra ${\mathcal{E}}$ of Burban and Schiffmann [5], such that for $n=1$ the symmetric polynomial $e_{k}[-MX^{m,n}]\cdot 1$ reduces to $\nabla^{m}e_{k}$. This notation is explained in §3.

In this paper we prove an even more general version of the shuffle theorem, involving a sum over LLT polynomials indexed by lattice paths lying under the line segment between arbitrary points $(0,s)$ and $(r,0)$ on the positive real axes, and reducing to the shuffle theorem of Bergeron et al. and Mellit when $(r,s)=(km,kn)$ are integers.

Our generalized shuffle theorem (Theorem 5.5.1) is an identity

whose ingredients we now summarize briefly, deferring full details to later parts of the paper.

The sum on the right hand side of (1) is over lattice paths $\lambda$ from $(0,\lfloor s\rfloor)$ to $(\lfloor r\rfloor,0)$ that lie below the line segment from $(0,s)$ to $(r,0)$. The quantity $a(\lambda)$ is the number of lattice squares enclosed between the path $\lambda$ and the highest such path $\delta$. We set $p=s/r$ and define $\operatorname{dinv}_{p}(\lambda)$ to be the number of ‘$p$-balanced’ hooks in the (French style) Young diagram enclosed by $\lambda$ and the $x$ and $y$ axes. A hook is $p$-balanced if a line of slope $-p$ passes through the segments at the top of its leg and the end of its arm (Definition 5.4.1 and Figure 3).

In the remaining factor $\omega({\mathcal{G}}_{\nu(\lambda)}(X;q^{-1}))$, the function ${\mathcal{G}}_{\nu}(X;q)$ is an ‘attacking inversions’ LLT polynomial (Definition 4.1.1), and $\omega(h_{\mu})=e_{\mu}$ is the standard involution on symmetric functions. The index $\nu(\lambda)$ is a tuple of one-row skew Young diagrams of the same lengths as runs of contiguous south steps in $\lambda$, arranged so that the reading order on boxes of $\nu(\lambda)$ corresponds to the ordering on south steps in $\lambda$ given by decreasing values of $y+px$ at the upper endpoint of each step.

The operator $D_{{\mathbf{b}}}=D_{b_{1},\ldots,b_{l}}$ on the left hand side of (1) is one of a family of special elements defined by Negut [29] in the Schiffmann algebra ${\mathcal{E}}$. Letting $\delta$ again denote the highest path under the given line segment, the index ${\mathbf{b}}$ is defined by taking $b_{i}$ to be the number of south steps in $\delta$ on the line $x=i-1$.

To recover the previously known cases of the theorem, we take $s=kn$ and $r$ slightly larger than $km$, so $p=n/m-\epsilon$ for a small $\epsilon>0$. The segment from $(0,s)$ to $(r,0)$ has the same lattice paths below it as the segment from $(0,kn)$ to $(km,0)$, and $\operatorname{dinv}_{p}(\lambda)$ reduces to the version of $\operatorname{dinv}(\lambda)$ in the original conjectures. The element $D_{{\mathbf{b}}}$ associated to the highest path $\delta$ below the segment from $(0,kn)$ to $(km,0)$ is equal to $e_{k}[-MX^{m,n}]$. Hence, (1) reduces to the $(km,kn)$ shuffle theorem.

We prove our generalized shuffle theorem by a remarkably simple method, which we now outline to help orient the reader in following the details. In §3 we will see that the left hand side of (1), after applying $\omega$ and evaluating in $l=\lfloor r\rfloor+1$ variables $x_{1},\ldots,x_{l}$, becomes the polynomial part

of an explicit infinite series of $\operatorname{GL}_{l}$ characters

When $\nu$ is a tuple of one-row skew shapes $(\beta_{i})/(\alpha_{i})$, the LLT polynomial ${\mathcal{G}}_{\nu}(x;q^{-1})$ is equal, up to a factor of the form $q^{d}$, to the polynomial part of an infinite $\operatorname{GL}_{l}$ character series

defined by Grojnowski and the second author [13]. In Theorem 5.3.1 we establish an identity of infinite series

where ${\mathcal{L}}^{\sigma}_{\beta/\alpha}(x;q)$ is a ‘twisted’ variant of ${\mathcal{L}}_{\beta/\alpha}(x;q)$ (see §4). Then (1) follows once we see that the polynomial part of the right hand side of (5) is equal to the right hand side of (1) with the $\omega$ omitted.

In fact, (4) holds when $\alpha_{i}\leq\beta_{i}$ for all $i$, and otherwise ${\mathcal{L}}_{\beta/\alpha}(x;q)_{\operatorname{pol}}=0$. When we take the polynomial part in (5), this leaves a non-vanishing term $t^{|{\mathbf{a}}|}q^{d}{\mathcal{G}}_{\nu(\lambda)}(x;q^{-1})$ for each path $\lambda$ under the given line segment, with ${\mathbf{a}}$ giving the number of lattice squares in each column between $\lambda$ and the highest path $\delta$, so $t^{|{\mathbf{a}}|}=t^{a(\lambda)}$. The factor $q^{d}$ from (4) turns out to be precisely $q^{\operatorname{dinv}_{p}(\lambda)}$, yielding (1).

Finally, the infinite series identity (5) from Theorem 5.3.1 is essentially a corollary to a Cauchy identity for non-symmetric Hall-Littlewood polynomials, Theorem 5.1.1. This Cauchy formula is quite general and can be applied in other situations, some of which we will take up elsewhere.

(i) The conjectures in [4, 15] and proofs in [6, 27] use a version of $\operatorname{dinv}(\lambda)$ that coincides with $\operatorname{dinv}_{p}(\lambda)$ for $p=n/m-\epsilon$. Alternatively, one can tilt the segment from $(0,kn)$ to $(km,0)$ in the other direction, taking $r=km$ and $s$ slightly larger than $kn$, to get a version of the original conjectures with a variant of $\operatorname{dinv}(\lambda)$ that coincides with $\operatorname{dinv}_{p}(\lambda)$ for $p=n/m+\epsilon$. Our theorem implies this version as well.

(ii) Haglund, Zabrocki and the third author [16] formulated a ‘compositional’ generalization of the original shuffle conjecture, in which the sum over Dyck paths is decomposed into partial sums over paths touching the diagonal at specified points. Bergeron et al. also gave a compositional form of their $(km,kn)$ shuffle conjecture in [4]. The proofs by Carlsson and Mellit [6] and Mellit [27] include the compositional forms of the conjectures, and indeed this seems to be essential to their methods.

Our results here do not cover the compositional shuffle theorems. For the generalization to paths under any line, it is not yet clear whether something like a compositional extension is possible or what form it might take.

(iii) By [15, Proposition 5.3.1], the LLT polynomials ${\mathcal{G}}_{\nu(\lambda)}(x;q)$ in (1) are $q$ Schur positive, meaning that their coefficients in the basis of Schur functions belong to ${\mathbb{N}}[q]$. The right hand side of (1) is therefore $q,t$ Schur positive. In the cases corresponding to the $(km,kn)$ shuffle theorem for $k=1$, this can also be seen from the representation theoretic interpretation of the right hand side given by Hikita [20].

Identity (1) therefore implies that the expression $D_{{\mathbf{b}}}\cdot 1$ on the left hand side is $q,t$ Schur positive. In the cases where the left hand side coincides with $\nabla^{m}e_{k}$, this can be explained using the representation theoretic interpretations of $\nabla e_{k}$ in [18] and $\nabla^{m}e_{k}$ in [15, Proposition 6.1.1]. In §7 we conjecture a more general condition for $D_{{\mathbf{b}}}\cdot 1$ to be $q,t$ Schur positive.

(iv) The algebraic left hand side of (1) is manifestly symmetric in $q$ and $t$. Hence, the combinatorial right hand side is also symmetric in $q$ and $t$. No direct combinatorial proof of this symmetry is currently known.

Integer partitions are written $\lambda=(\lambda_{1}\geq\cdots\geq\lambda_{l})$, possibly with trailing zeroes. We set $|\lambda|=\lambda_{1}+\cdots+\lambda_{l}$ and let $\ell(\lambda)$ be the number of non-zero parts. We also define

The transpose of $\lambda$ is denoted $\lambda^{*}$.

The partitions of a given integer $n$ are partially ordered by

where the sums include trailing zeroes for $k>\ell(\lambda)$ or $k>\ell(\mu)$.

The (French style) Young or Ferrers diagram of a partition $\lambda$ is the set of lattice points $\{(i,j)\mid 1\leq j\leq\ell(\lambda),\;1\leq i\leq\lambda_{j}\}$. We often identify $\lambda$ and its diagram with the set of lattice squares, or boxes, with northeast corner at a point $(i,j)\in\lambda$. A skew diagram (or skew shape) $\lambda/\mu$ is the difference between the diagram of a partition $\lambda$ and that of a partition $\mu\subseteq\lambda$ contained in it. The diagram generator of $\lambda$ is the polynomial

Let $\Lambda=\Lambda_{{\mathbf{k}}}(X)$ be the algebra of symmetric functions in an infinite alphabet of variables $X=x_{1},x_{2},\ldots$, with coefficients in the field ${\mathbf{k}}={\mathbb{Q}}(q,t)$. We follow Macdonald’s notation [25] for various graded bases of $\Lambda$, such as the elementary symmetric functions $e_{\lambda}=e_{\lambda_{1}}\cdots e_{\lambda_{k}}$, complete homogeneous symmetric functions $h_{\lambda}=h_{\lambda_{1}}\cdots h_{\lambda_{k}}$, power-sums $p_{\lambda}=p_{\lambda_{1}}\cdots p_{\lambda_{k}}$, monomial symmetric functions $m_{\lambda}$ and Schur functions $s_{\lambda}$. The involutory ${\mathbf{k}}$-algebra automorphism $\omega\colon\Lambda\rightarrow\Lambda$ mentioned in the introduction may be defined by any of the formulas

We also need the symmetric bilinear inner product $\langle-,-\rangle$ on $\Lambda$ defined by any of

where $z_{\lambda}=\prod_{i}r_{i}!\,i^{r_{i}}$ if $\lambda=(1^{r_{1}},2^{r_{2}},\ldots)$.

We write $f^{\bullet}$ for the operator of multiplication by a function $f$. Otherwise, the custom of writing $f$ for both the operator and the function would make it hard to distinguish between operator expressions such as $(\omega f)^{\bullet}$ and $\omega\cdot f^{\bullet}$. When $f$ is a symmetric function, we write $f^{\perp}$ for the $\langle-,-\rangle$ adjoint of $f^{\bullet}$.

We briefly recall the device of plethystic evaluation. If $A$ is an expression in terms of indeterminates, such as a polynomial, rational function, or formal series, we define $p_{k}[A]$ to be the result of substituting $a^{k}$ for every indeterminate $a$ occurring in $A$. We define $f[A]$ for any $f\in\Lambda$ by substituting $p_{k}[A]$ for $p_{k}$ in the expression for $f$ as a polynomial in the power-sums $p_{k}$, so that $f\mapsto f[A]$ is a homomorphism.

The variables $q,t$ from our ground field ${\mathbf{k}}$ count as indeterminates.

As a simple example, the plethystic evaluation $f[x_{1}+\cdots+x_{l}]$ is just the ordinary evaluation $f(x_{1},\ldots,x_{l})$, since $p_{k}[x_{1}+\cdots+x_{l}]=x_{1}^{k}+\cdots+x_{l}^{k}$. This also works in infinitely many variables.

When $X=x_{1},x_{2},\ldots$ is the name of an infinite alphabet of variables, we use $f(X)$, with round brackets, as an abbreviation for $f(x_{1},x_{2},\ldots)\in\Lambda(X)$. In this situation we also make the convention that when $X$ appears inside plethystic brackets, it means $X=x_{1}+x_{2}+\cdots$. With this convention, $f[X]$ is another way of writing $f(X)$.

As a second example and caution to the reader, the formula in (9) for $\omega\,p_{k}$ implies the identity $\omega f(X)=f[-zX]|_{z=-1}$. Note that $f[-zX]|_{z=-1}$ does not reduce to $f(X)$, as it might at first appear, since specializing the indeterminate $z$ to a number does not commute with plethystic evaluation.

Plethystic evaluation of a symmetric infinite series is allowed if the result converges as a formal series. The series

is particularly useful. The classical Cauchy identity can be written using this notation as

Taking the inner product with $f(X)$ in (12) yields $f[A]=\langle\Omega[AX],f(X)\rangle$, which implies

As $B$ is arbitrary, $\Omega[BX]$ is in effect a general symmetric function, so (13) implies

Note that although $\Omega[AX]^{\perp}=\sum_{k}h_{k}[AX]^{\perp}$ is an infinite series, it converges formally as an operator applied to any $f\in\Lambda(X)$, since $h_{k}[AX]^{\perp}$ has degree $-k$, and so kills $f$ for $k\gg 0$.

Identifying $\Lambda$ with a polynomial ring in the power-sums $p_{k}$, we have

In fact, taking $A=z$ and $f=p_{k}$ in (14) shows that $\exp(\sum(p_{k}^{\perp}z^{k})/k)$ is the operator that substitutes $p_{k}+z^{k}$ for $p_{k}$ in any polynomial $f(p_{1},p_{2},\ldots)$. This operator can also be written $\exp(\sum z^{k}\frac{\partial}{\partial p_{k}})$, giving (15).

Another consequence of (14) is the operator identity

with notation $\Omega[BX]^{\bullet}$ as in §2.1.

The weight lattice of $\operatorname{GL}_{l}$ is $X={\mathbb{Z}}^{l}$, with Weyl group $W=S_{l}$ permuting the coordinates. Letting $\varepsilon_{1},\ldots,\varepsilon_{l}$ be unit vectors, the positive roots are $\varepsilon_{i}-\varepsilon_{j}$ for $i<j$, with simple roots $\alpha_{i}=\varepsilon_{i}-\varepsilon_{i+1}$ for $i=1,\ldots,l-1$. The standard pairing on ${\mathbb{Z}}^{l}$ in which the $\varepsilon_{i}$ are orthonormal identifies the dual lattice $X^{*}$ with $X$. Under this identification, the coroots coincide with the roots, and the simple coroots $\alpha_{i}^{\vee}$ with the simple roots. A weight $\lambda\in{\mathbb{Z}}^{l}$ is dominant if $\lambda_{1}\geq\cdots\geq\lambda_{l}$; a weight is regular (has trivial stabilizer in $S_{l}$) if $\lambda_{1},\ldots,\lambda_{l}$ are distinct.

A polynomial weight is a dominant weight $\lambda$ such that $\lambda_{l}\geq 0$. In other words, polynomial weights of $\operatorname{GL}_{l}$ are integer partitions of length at most $l$.

The algebra of virtual $\operatorname{GL}_{l}$ characters $({\mathbf{k}}X)^{W}$ can be identified with the algebra of symmetric Laurent polynomials ${\mathbf{k}}[x_{1}^{\pm 1},\ldots,x_{l}^{\pm 1}]^{S_{l}}$. If $\lambda$ is a polynomial weight, the irreducible character $\chi_{\lambda}$ is equal to the Schur function $s_{\lambda}(x_{1},\ldots,x_{l})$. Given a virtual $\operatorname{GL}_{l}$ character $f(x)=f(x_{1},\dots,x_{l})=\sum_{\lambda}c_{\lambda}\chi_{\lambda}$, we denote the partial sum over polynomial weights $\lambda$ by $f(x)_{\operatorname{pol}}$. Thus, $f(x)_{\operatorname{pol}}$ is a symmetric polynomial in $l$ variables. We also use this notation for infinite formal sums $f(x)$ of irreducible $\operatorname{GL}_{l}$ characters, in which case $f(x)_{\operatorname{pol}}$ is a symmetric formal power series.

The Weyl symmetrization operator for $\operatorname{GL}_{l}$ is

For dominant weights $\lambda$, the Weyl character formula can be written $\chi_{\lambda}={\boldsymbol{\sigma}}(x^{\lambda})$.

Fix a weight $\rho$ such that $\langle\alpha_{i}^{\vee},\rho\rangle=1$ for each simple coroot $\alpha_{i}^{\vee}$, e.g., $\rho=(l-1,\ldots,1,0)$. Although $\rho$ is only unique up to adding a constant vector, all formulas in which $\rho$ appears will be independent of the choice. Let $\mu$ be any weight, not necessarily dominant. If $\mu+\rho$ is not regular, then ${\boldsymbol{\sigma}}(x^{\mu})=0$. Otherwise, if $w\in S_{l}$ is the unique permutation such that $w(\mu+\rho)=\lambda+\rho$ for $\lambda$ dominant,

The following identities are useful for working with the Weyl symmetrization operator.

Given a Laurent polynomial $\phi(x_{1},\ldots,x_{l})$, we define

Here and in similar raising operator formulas elsewhere, the factors $1/(1-q\,x_{i}/x_{j})$ are to be understood as geometric series, making ${\mathbf{H}}_{q}(\phi(x))$ an infinite formal sum of irreducible $\operatorname{GL}_{l}$ characters with coefficients in ${\mathbf{k}}$. Since $1/(1-q\,x_{i}/x_{j})$ is a power series in $q$, if we expand the coefficients of $\phi(x)$ as formal Laurent series in $q$, then ${\mathbf{H}}_{q}(\phi(x))$ becomes a formal Laurent series in $q$ over virtual $\operatorname{GL}_{l}$ characters. This is how the last formula in (23) should be interpreted.

We recall here some definitions and results from [5, 7, 29, 30, 31] concerning the elliptic Hall algebra ${\mathcal{E}}$ of Burban and Schiffmann [5] (or Schiffmann algebra, for short) and its action on the algebra of symmetric functions $\Lambda$, constructed by Feigin and Tsymbauliak [7] and Schiffmann and Vasserot [31].

From a certain point of view, this material is unnecessary: two of the three quantities equated by (1) and (2) are defined without reference to the Schiffmann algebra, and we could take “Shuffle Theorem” to mean the identity between these two, namely

with ${\mathcal{H}}_{{\mathbf{b}}}(x)$ as in (3). This identity still has the virtue of equating the combinatorial right hand side, involving Dyck paths and LLT polynomials, with a simple algebraic left hand side that is manifestly symmetric in $q$ and $t$. Furthermore, our proof of (1) in Theorem 5.5.1 proceeds by combining (2) with a proof of (24) (via Theorem 5.3.1) that makes no use of the Schiffmann algebra.

What we need the Schiffmann algebra for is to provide the link between our shuffle theorem and the classical and $(km,kn)$ versions. Indeed, the very definition of the algebraic side in the $(km,kn)$ shuffle theorem is $e_{k}[-MX^{m,n}]\cdot 1$ for a certain operator $e_{k}[-MX^{m,n}]\in{\mathcal{E}}$, while the classical shuffle theorems refer implicitly to the same operators through the identity $\nabla^{m}e_{k}=e_{k}[-MX^{m,1}]\cdot 1$.

In this section, we review what is needed to relate the symmetric functions $\nabla^{m}e_{k}$ and $({\mathcal{H}}_{{\mathbf{b}}})_{\operatorname{pol}}$ to the action of the elements $e_{k}[-MX^{m,n}]$ and $D_{{\mathbf{b}}}$ on $\Lambda$. For ease of reference, we have collected most of the statements that will be used elsewhere in the paper in §3.7, after the technical development in §§3.2–3.6.

Let ${\mathbf{k}}={\mathbb{Q}}(q,t)$. The Schiffmann algebra ${\mathcal{E}}$ is generated by subalgebras $\Lambda(X^{m,n})$ isomorphic to the algebra $\Lambda_{{\mathbf{k}}}$ of symmetric functions, one for each pair of coprime integers $(m,n)$, and a central Laurent polynomial subalgebra ${\mathbf{k}}[c_{1}^{\pm 1},c_{2}^{\pm 1}]$, subject to some defining relations which we will not list in full here, but only invoke a few of them as needed.

For purposes of comparison with [5, 30, 31], our notation (on the left hand side of each formula) is related as follows to that in [5, Definition 6.4] (on the right hand side). Note that our indices $(m,n)\in{\mathbb{Z}}^{2}$ correspond to transposed indices $(n,m)$ in [5].

where $\varepsilon_{n,m}$, which is equal to $(1-\epsilon_{n,m})/2$ in the notation of [5], is given by

The expression $e_{k}[-\widehat{M}X^{m,n}]$ in (25) uses plethystic substitution (§2.2) with

The quantity $M$ will be referred to repeatedly.

A natural action of ${\mathcal{E}}$ by operators on $\Lambda(X)$ has been constructed in [7, 31]. Actually these references give several different normalizations of essentially the same action. The action we use is a slight variation of the action in [31, Theorem 3.1].

To write it down we need to recall some notions from the theory of Macdonald polynomials. Let $\tilde{H}_{\mu}(X;q,t)$ denote the modified Macdonald polynomials [10], which can be defined in terms of the integral form Macdonald polynomials $J_{\mu}(X;q,t)$ of [25] by

with $n(\mu)$ as in (6). For any symmetric function $f\in\Lambda$, let $f[B]$, $f[\overline{B}]$ denote the eigenoperators on the basis $\{\tilde{H_{\mu}}\}$ of $\Lambda$ such that

with $B_{\mu}(q,t)$ as in (8) and $\overline{B_{\mu}(q,t)}=B_{\mu}(q^{-1},t^{-1})$. More generally we use the overbar to signify inverting the variables in any expression, for example

The next proposition essentially restates the contents of [31, Theorem 3.1 and Proposition 4.10] in our notation. To be more precise, since these two theorems refer to different actions of ${\mathcal{E}}$ on $\Lambda$, one must first use the plethystic transformation in [31, §4.4] to express [31, Proposition 4.10] in terms of the action in [31, Theorem 3.1]. Rescaling the generators $u_{\pm 1,l}$ then yields the following.

We will show in Proposition 3.3.4, below, that the elements $p_{1}[-MX^{1,a}]\in{\mathcal{E}}$ act on $\Lambda$ as operators $D_{a}$ given by the coefficients $D_{a}=\langle z^{-a}\rangle D(z)$ of a generating series

defined by either of the equivalent formulas

using the operator notation from §2.1. These operators $D_{a}$ differ by a sign $(-1)^{a}$ from those studied in [3, 11], and by a plethystic transformation from operators previously introduced by Jing [22].