A proof of the shuffle conjecture

Abstract

We present a proof of the compositional shuffle conjecture by Haglund, Morse and Zabrocki [Canad. J. Math., 64 (2012), 822–844], which generalizes the famous shuffle conjecture for the character of the diagonal coinvariant algebra by Haglund, Haiman, Loehr, Remmel, and Ulyanov [Duke Math. J., 126 (2005), 195–232]. We first formulate the combinatorial side of the conjecture in terms of certain operators on a graded vector space $V_*$ whose degree zero part is the ring of symmetric functions $\operatorname {Sym}[X]$ over $\mathbb{Q}(q,t)$. We then extend these operators to an action of an algebra $\tilde{\mathbb{A}}$ acting on this space, and interpret the right generalization of the $\nabla$ using an involution of the algebra which is antilinear with respect to the conjugation $(q,t)\mapsto (q^{-1},t^{-1})$.

1. Introduction

The shuffle conjecture of Haglund, Haiman, Loehr, Remmel, and Ulyanov HHL${+}$05b predicts a combinatorial formula for the Frobenius character $\mathcal{F}_{R_n}(X;q,t)$ of the diagonal coinvariant algebra $R_n$ in $n$ pairs of variables, which is a symmetric function in infinitely many variables with coefficients in $\mathbb{Z}_{\geq 0}[q,t]$. By a result of Haiman Hai02, the Frobenius character is given explicitly by

$$\begin{equation*} \mathcal{F}_{R_n}(X;q,t)=(-1)^n \nabla e_n[X], \end{equation*}$$

where, up to a sign convention, $\nabla$ is the operator which is diagonal in the modified Macdonald basis defined in BGHT99. The original shuffle conjecture states

$$\begin{equation} (-1)^n \nabla e_n[X] = \sum _{\pi } \sum _{w \in \mathcal{WP}_\pi } t^{\operatorname {area}(\pi )} q^{\operatorname {dinv}(\pi ,w)} x_w. {\tag{1.1}} \end{equation}$$

Here $\pi$ is a Dyck path of length $n$, and $w$ is some extra data called a “word parking function” depending on $\pi$. The functions $(\operatorname {area},\operatorname {dinv})$ are statistics associated to a Dyck path and a parking function, and $x_w$ is a monomial in the variables $x$. It was shown in HHL${+}$05b that this sum, denoted $D_n(X;q,t)$, is symmetric in the $x$ variables, and so it does at least define a symmetric function. It was also shown there that the shuffle conjecture included many previous conjectures and results about the $q,t$-Catalan numbers, and other special cases GH96GH02Hag03EHKK03Hag04. Remarkably, $D_n(X;q,t)$ had not even been proven to be symmetric in the $q,t$ variables until now, even though the symmetry of $\mathcal{F}_{R_n}(X;q,t)$ is obvious. The name “shuffle conjecture” has to do with the fact that the coefficient of $m_\mu$ in equation 1.1 can be expressed in terms of parking functions that are “$\mu$-shuffles”. See Conjecture 6.1 of Haglund’s book Hag08 for a detailed explanation, and Chapter 6 in general for a thorough introduction to this topic.

In HMZ12 Haglund, Morse, and Zabrocki conjectured a refinement of the original conjecture which partitions $D_n(X;q,t)$ by specifying the points where the Dyck path touches the diagonal called the “compositional shuffle conjecture”. The refined conjecture states

$$\begin{equation} \nabla \left(C_{\alpha }[X;q]\right)= \sum _{\operatorname {touch}(\pi )=\alpha } \sum _{w \in \mathcal{WP}_\pi } t^{\operatorname {area}(\pi )}q^{\operatorname {dinv}(\pi ,w)} x_w. {}{\tag{1.2}} \end{equation}$$

Here $\alpha$ is a composition, i.e., a finite list of positive integers specifying the gaps between the touch points of $\pi$. The function $C_{\alpha }[X;q]$ is defined below as a composition of creation operators for Hall–Littlewood polynomials in the variable $1/q$. They proved that

$$\begin{equation*} \sum _{|\alpha |=n} C_\alpha [X;q]=(-1)^n e_n[X], \end{equation*}$$

implying that 1.2 does indeed generalize 1.1. The right-hand side of 1.2 will be denoted by $D_{\alpha }(X;q,t)$. A desirable approach to proving 1.2 would be to determine a recursive formula for $D_{\alpha }(X;q,t)$ and to interpret the result in terms of some commutation relations for $\nabla$. Indeed, this approach has been applied in some important special cases; see GH02GXZ12Hic12. In GXZ12, for instance, the authors devise a recursive formula (Proposition 3.12) to prove the Catalan case of the compositional conjecture, extending the results of GH02. Unfortunately, no such recursion is known in the general case, and so an even more refined function is needed.

In this paper, we will construct the desired refinement as an element of a larger vector space $V_k$ of symmetric functions over $\mathbb{Q}(q,t)$ with $k$ additional variables $y_i$ adjoined, where $k$ is the length of the composition $\alpha$,

$$\begin{equation*} N_{\alpha } \in V_k=\operatorname {Sym}[X][y_1,\ldots ,y_k]. \end{equation*}$$

In our first result (Theorem 4.11) we will explain how to recover $D_\alpha (X;q,t)$ from $N_\alpha$, which is defined by an explicit recursion. In fact, while they live in different vector spaces, the recursions for $N_\alpha$ are similar to the recursions for the Catalan case in GXZ12. We make this connection precise in Proposition 4.14, which explains how the latter formulas follow as a special case.

We then define a pair of algebras $\mathbb{A}$ and $\mathbb{A}^*$ which are isomorphic by an antilinear isomorphism with respect to the conjugation $(q,t)\rightarrow (q^{-1},t^{-1})$, as well as an explicit action of each on the direct sum $V_*=\bigoplus _{k\geq 0} V_k$. We will then prove that there is an antilinear involution $\mathcal{N}$ on $V_*$ which intertwines the two actions (Theorem 7.4) and represents an involutive automorphism on a larger algebra $\mathbb{A},\mathbb{A}^*\subset \tilde{\mathbb{A}}$. This turns out to be the essential fact that relates the $N_\alpha$ to $\nabla$.

The compositional shuffle conjecture (Theorem 7.5) then follows as a simple corollary from the following properties:

(i)

There is a surjection coming from $\mathbb{A},\mathbb{A}^*$$$\begin{equation*} d_-^{k} : V_k \rightarrow V_0=\operatorname {Sym}[X] \end{equation*}$$

which maps a monomial $y_\alpha$ in the $y$ variables to an element $B_{\alpha }[X;q]$ which is similar to $C_\alpha [X;q]$ and maps $N_\alpha$ to $D_{\alpha }(X;q,t)$, up to a sign.

(ii)

The involution $\mathcal{N}$ commutes with $d_-$ and maps $y_\alpha$ to $N_\alpha$.

(iii)

The restriction of $\mathcal{N}$ to $V_0=\operatorname {Sym}[X]$ agrees with $\nabla$ composed with a conjugation map which essentially exchanges the $B_{\alpha }[X;q]$ and $C_{\alpha }[X;q]$.

It then becomes clear that these properties imply 1.2.

While the compositional shuffle conjecture is clearly our main application, the shuffle conjecture has been further generalized in several remarkable directions such as the rational compositional shuffle conjecture, and relationships to knot invariants, double affine Hecke algebras, and the cohomology of the affine Springer fibers; see BGLX14GORS14GN15Neg13Hik14SV11SV13. We hope that future applications to these fascinating topics will be forthcoming.

2. The compositional shuffle conjecture

2.1. Plethystic operators

A $\lambda$-ring is a ring $R$ with a family of ring endomorphisms $(p_i)_{i\in \mathbb{Z}_{>0}}$ satisfying

$$\begin{equation*} p_1[x]=x,\quad p_m[p_n[x]]=p_{mn}[x]\quad (x\in R,\quad m,n\in \mathbb{Z}_{>0}). \end{equation*}$$

Unless stated otherwise, the endomorphisms are defined by $p_n(x)=x^n$ for each variable $x$ such as $q,t,u,v,z,x_i,y_i$. The ring of symmetric functions over the $\lambda$-ring $\mathbb{Q}(q,t)$ is a free $\lambda$-ring with generator $X=x_1+x_2+\cdots$, and it will be denoted $\operatorname {Sym}[X]$. We will employ the standard notation used for plethystic substitution defined as follows: given an element $F\in \operatorname {Sym}[X]$ and $A$ in some $\lambda$-ring $R$, the plethystic substitution $F[A]$ is the image of the homomorphism from $\operatorname {Sym}[X]\rightarrow R$ defined by replacing $p_n$ by $p_n(A)$. For instance, we would have

$$\begin{equation*} p_1 p_2[X/(1-q)]=p_1[X] p_2[X](1-q)^{-1}(1-q^2)^{-1}. \end{equation*}$$

See Hai01 for a reference.

The modified Macdonald polynomials GHT99 will be denoted

$$\begin{equation*} \tilde{H}_\mu =t^{n(\mu )} J_{\mu }[X/(1-t^{-1});q,t^{-1}] \in \operatorname {Sym}[X], \end{equation*}$$

where $J_\mu$ is the integral form of the Macdonald polynomial Mac95, and

$$\begin{equation*} n(\mu )=\sum _{i} (i-1)\mu _i. \end{equation*}$$

The operator $\nabla :\operatorname {Sym}[X]\to \operatorname {Sym}[X]$ is defined by

$$\begin{equation} \nabla \tilde{H}_\mu = \tilde{H}_\mu [-1] \tilde{H}_\mu = (-1)^{|\mu |} q^{n(\mu ')} t^{n(\mu )} \tilde{H}_\mu . {\tag{2.1}} \end{equation}$$

Note that our definition differs from the usual one from BGHT99 by the sign $(-1)^{|\mu |}$. We also have the sequences of operators $B_r, C_r:\operatorname {Sym}[X]\rightarrow \operatorname {Sym}[X]$ given by the formulas

$$\begin{gather*} (B_r F)[X] = F[X-(q-1)z^{-1}] \operatorname {Exp}[-z X]\big |_{z^r},\\ (C_r F)[X] = -q^{1-r} F[X+(q^{-1}-1)z^{-1}] \operatorname {Exp}[z X]\big |_{z^r}, \end{gather*}$$

where $\operatorname {Exp}[X]=\sum _{n=0}^\infty h_n[X]$ is the plethystic exponential and $\vert _{z^r}$ denotes the operation of taking the coefficient of $z^r$ of a Laurent power series. Our definition again differs from the one in HMZ12 by a factor $(-1)^r$. For any composition $\alpha$, let $C_\alpha$ denote the composition $C_{\alpha _1}\cdots C_{\alpha _l}$, and similarly for $B_\alpha$.

Finally, we denote by $x \mapsto \bar{x}$ the involutive automorphism of $\mathbb{Q}(q,t)$ obtained by sending $q,t$ to $q^{-1},t^{-1}$. We denote by $\omega$ the $\lambda$-ring automorphism of $\operatorname {Sym}[X]$ obtained by sending $X$ to $-X$ and by $\bar{\omega }$ its composition with $\bar{*}$, i.e.,

$$\begin{equation*} (\omega F)[X] = F[-X],\quad (\bar{\omega }F)[X] = \bar{F}[-X]. \end{equation*}$$

2.2. Parking functions

We now recall the combinatorial background to state the shuffle conjecture, for which we refer to Haglund’s book Hag08. We consider the infinite grid on the top right quadrant of the plane. Its intersection points are denoted as $(i,j)$ with $i,j\in \mathbb{Z}$. For each cell of the grid, its coordinates $(i,j)$ are the coordinates of the top right corner. Thus $i=1,2,\ldots$ indexes the columns and $j=1,2,\ldots$ indexes the rows. Let $\mathbb{D}$ be the set of Dyck paths of all lengths. A Dyck path of length $n$ is a grid path, from $(0,0)$ to $(n,n)$ consisting of North and East steps, that stays above the main diagonal $i=j$. For $\pi \in \mathbb{D}$ denote by $|\pi |$ its length $n$. For $\pi \in \mathbb{D}$, let

$$\begin{equation*} \operatorname {area}(\pi ):=\#\operatorname {Area}(\pi ),\quad \operatorname {Area}(\pi ):=\left\{(i,j): i<j,\ (i,j) \text{ under } \pi \right\}. \end{equation*}$$

This is the set of cells between the path and the diagonal. Let $a_j$ denote the number of cells $(i,j) \in \operatorname {Area}(\pi )$ in the row $j$. The area sequence is the sequence $a(\pi )=(a_1,a_2,\ldots ,a_n),$ and we have $\operatorname {area}(\pi )=\sum _{j=1}^n a_n$.

Let $(x_1,1), (x_2,2),\ldots , (x_n, n)$ be the cells immediately to the right of the North steps. The sequence $x(\pi )=(x_1,x_2,\ldots ,x_n)$ is called the coarea sequence, and we have $a_j+x_j=j$ for all $j$.

We have the $\operatorname {dinv}$ statistic and the $\operatorname {Dinv}$ set defined by

$$\begin{equation*} \begin{split} \operatorname {dinv}(\pi )&:=\#\operatorname {Dinv}(\pi ),\\ \operatorname {Dinv}(\pi )&:= \operatorname {Dinv}^0(\pi ) \cup \operatorname {Dinv}^1(\pi )\\ &=\left\{(j,j'):1\leq j<j'\leq n,\ a_j=a_{j'}\right\}\\ &\quad \cup \left\{(j,j'):1\leq j'<j\leq n,\ a_{j'}=a_j+1\right\}. \end{split} \end{equation*}$$

For $(j,j')\in \operatorname {Dinv}(\pi )$, we say that $(x_j, j)$ attacks $(x_{j'}, j')$.

For any $\pi$, the set of word parking functions associated to $\pi$ is defined by

$$\begin{equation*} \mathcal{WP}_\pi :=\left\{{w} \in \mathbb{Z}_{>0}^n : w_{j}>w_{j+1} \;\text{whenever}\; x_{j}=x_{j+1}\right\}. \end{equation*}$$

In other words, the elements of $\mathcal{WP}_\pi$ are $n$-tuples $w$ of positive integers which, when written from bottom to top to the right of each North step, are strictly decreasing on cells such that one is on top of the other. For any $w$, let

$$\begin{equation*} \operatorname {dinv}(\pi ,w):=\#\operatorname {Dinv}(\pi ,w),\quad \operatorname {Dinv}(\pi ,w):=\left\{(j,j') \in \operatorname {Dinv}(\pi ):w_j>w_{j'}\right\}. \end{equation*}$$

We note that both of these conditions differ from the usual notation in which parking functions are expected to increase rather than decrease, and in which the inequalities are reversed in the definition of $\operatorname {dinv}$. This corresponds to choosing the opposite total ordering on $\mathbb{Z}_{>0}$ everywhere, which does not affect the final answer and is more convenient for the purposes of this paper.

Let us call $\alpha =(\alpha _1,\ldots ,\alpha _k)=\operatorname {touch}(\pi )$ the touch composition of $\pi$ if $\alpha _1,\ldots ,\alpha _k$ are the lengths of the gaps between the points where $\pi$ touches the main diagonal starting at the lower left. Equivalently, $\sum _{i=1}^k \alpha _i=n$ and the numbers $1$, $1+\alpha _1$, $1+\alpha _1+\alpha _2$, …$,1+\alpha _1+\cdots +\alpha _{k-1}$ are the positions of $0$ in the area sequence $a(\pi )$.

Example 2.1.

Let $\pi$ be the following Dyck path of length $8$ described in Figure 1. Then we have

$$\begin{align*} \operatorname {Area}(\pi )&=\left\{(2,3),(2,4),(3,4),(3,5),(3,6),(4,5),(4,6),(5,6),(7,8)\right\},\\ \operatorname {Dinv}(\pi )&=\left\{(1,2),(1,7),(2,7),(3,8),(4,5)\right\} \cup \left\{(7,3),(8,4),(8,5)\right\},\\ \operatorname {touch}(\pi )&=(1,5,2),\quad a(\pi )=(0,0,1,2,2,3,0,1),\\ x(\pi )&=(1,2,2,2,3,3,7,7) \end{align*}$$

whence $\operatorname {area}(\pi )=9$, $\operatorname {dinv}(\pi )=5+3=8$. The labels shown above correspond to the vector $w=(9,5,2,1,5,2,3,2)$, which we can see is an element of $\mathcal{WP}_\pi$ because we have $5>2>1$, $5>2$, $3>2$. We then have

$$\begin{equation*} \operatorname {Dinv}(\pi ,w)=\left\{(1,2),(1,7),(2,7)\right\}\cup \left\{(7,3),(8,4)\right\}, \end{equation*}$$

giving $\operatorname {dinv}(\pi ,w)=5$.

2.3. The shuffle conjectures

For any infinite set of variables $X=\{x_1,x_2,\ldots \}$, let $x_w=x_{w_1}\cdots x_{w_n}$. In this notation, the original shuffle conjecture HHL${+}$05b states

Conjecture (HHL${+}$05b).

We have

$$\begin{equation*} (-1)^n \nabla e_n= \sum _{|\pi |=n} t^{\operatorname {area}(\pi )}\sum _{w\in \mathcal{WP}_\pi } q^{\operatorname {dinv}(\pi ,w)} x_{w}. \end{equation*}$$

In particular, the right-hand side is symmetric in the $x_i$, and in $q,t$.

The stronger compositional shuffle conjecture HMZ12 states

Conjecture (HMZ12).

For any composition $\alpha$, we have

$$\begin{equation} (-1)^n \nabla C_{\alpha }(1)= \sum _{\operatorname {touch}(\pi )=\alpha } t^{\operatorname {area}(\pi )}\sum _{w\in \mathcal{WP}_\pi } q^{\operatorname {dinv}(\pi ,w)} x_w. {\tag{2.2}} \end{equation}$$

2.4. From $(\operatorname {area},\operatorname {dinv})$ to $(\operatorname {bounce},\operatorname {area}')$

In this paper, we will prove an equivalent version of this conjecture, as obtained in LN14, Theorem 14, by applying the $(\operatorname {area},\operatorname {dinv})$ to $(\operatorname {bounce},\operatorname {area}')$ bijection from HL05 and Hag08. We include our construction of this bijection because it seems to be different from the original one, and to demonstrate that it comes naturally from analysis of the attack relation. An important property of our construction is that it comes with a natural lift from Dyck paths to parking functions.

From any pair $\pi \in \mathbb{D}$, $w\in \mathcal{WP}_\pi$ we will obtain a pair $\pi '\in \mathbb{D}$, $w'\in \mathcal{WP}'_{\pi '}$ by a procedure described below. After the end of this section we will only work with $\pi ', w'$, so we will drop the apostrophe.

The Dyck path $w'$ is obtained as follows: sort the cells $(x_j, j)$ in the reading order, i.e., in increasing order by the corresponding labels $a_j$, using the row index $j$ to break ties. Equivalently, we read the cells by diagonals from bottom to top, and from left to right in each diagonal. For instance, for the path $\pi$ from Example 2.1, the list would be

$$\begin{equation} \left\{(1,1),(2,2),(7,7),(2,3),(7,8),(2,4),(3,5),(3,6)\right\}. {\tag{2.3}} \end{equation}$$

Let $\sigma _j$ be the position of the cell $(x_j,j)$ in this list. This defines a permutation $\sigma \in S_n$. In the example case, we would get

$$\begin{equation*} \sigma = \begin{pmatrix} 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 \\ 1 & 2 & 4 & 6 & 7& 8 & 3 & 5 \end{pmatrix}. \end{equation*}$$

Now we observe that for each $j=1,\ldots ,n,$ the cell $(x_j, j)$ attacks all the subsequent cells in the reading order whose position is before the position where we would place $(x_j, j+1)$ if it were an element of the list.

More precisely, there is a unique Dyck path $\pi '$ for which