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

$$\begin{equation*} \operatorname {Area}(\pi ')=\sigma (\operatorname {Dinv}(\pi ))= \left\{(\sigma _j,\sigma _{j'}):(j,j')\in \operatorname {Dinv}(\pi )\right\}. \end{equation*}$$

The map $\pi \to \pi '$ is the desired bijection. To see the bijectivity one can either use Hag08 or see Remark 2.3.

If $\pi$ is the Dyck path from our example, then $\pi '$ would be given by the path in Figure 2.

The above statistics can be translated into new statistics under this bijection. First, it is clear from the construction that $\operatorname {dinv}(\pi )=\operatorname {area}(\pi ')$. We next explain how to calculate $\operatorname {area}(\pi )$ from $\pi '$. For any path, we obtain a new Dyck path called the “bounce path” as follows: Start at the origin $(0,0)$, and begin moving North until contact is made with the first East step of $\pi$. Then start moving East until contacting the diagonal. Then move North until contacting the path again, and so on. Note that contacting the path means running into the left endpoint of an East step, but passing by the rightmost endpoint does not count, as illustrated below. The bounce path splits the main diagonal into the bounce blocks. We number the bounce blocks starting from $0$ and define the bounce sequence $b(\pi )=(b_1, b_2, \ldots , b_n)$ in such a way that for any $i$ the cell $(i,i)$ belongs to the $b_i$th block. We then define

$$\begin{equation*} \operatorname {bounce}(\pi '):=\sum _{i=1}^n b_i. \end{equation*}$$

Another way to describe this construction is to say that $b_1=0$, $b_{i+1}\in \{b_i, b_i+1\}$ and if $i, i'$ are the smallest indices for which $b_i=c$ and $b_{i'}=c+1$ for some $c$, then $i'$ is the smallest index with $i'>i$ such that $(i,i')\notin \operatorname {Area}(\pi ')$. This description and $\operatorname {Area}(\pi ')=\sigma (\operatorname {Dinv}(\pi ))$ implies $b_{\sigma _i} = a_i$, hence $\operatorname {bounce}(\pi ')=\operatorname {area}(\pi )$; see Hag08 for an alternative treatment.

For the path $\pi '$ above, the bounce path is shown in Figure 3 with the original path in gray. The bounce sequence is given by the numbers written under the diagonal. We have

$$\begin{equation*} b(\pi ')=(0,0,0,1,1,2,2,3),\quad \operatorname {bounce}(\pi ')=9=\operatorname {area}(\pi ). \end{equation*}$$

Next, we show how to reconstruct $\operatorname {touch}(\pi )$ from $\pi '$. For any path $\pi '$ of length $n$, let $l$ be the number of North steps from $(0,0)$ until the first East step, which is the same as the length of the first bounce block. Let $\tilde{\pi }$ be the part of the path such that $\pi '=N^lE\tilde{\pi }$, the result of beginning with $l$ North steps starting at the origin, followed by an East step, followed by the contents of $\tilde{\pi }$. Define numbers $t_i$ by

$$\begin{equation*} t_i:=\operatorname {bounce}\left(N^{i+1}EN^{l-i}E \tilde{\pi }\right),\quad 0\leq i \leq l. \end{equation*}$$

Note that the path $N^{i+1}EN^{l-i}E \tilde{\pi }$ has length $n+1$ for each $i$, and we have $t_0=n+\operatorname {bounce}(\pi ')$ and the $t_i$ go down to $t_l=\operatorname {bounce}(\pi ')$. Define

$$\begin{equation*} \operatorname {touch}'(\pi '):=(t_0-t_{1},\ldots ,t_{l-1}-t_{l}). \end{equation*}$$

Proposition 2.2.

For every Dyck path $\pi$

$$\begin{equation*} \operatorname {touch}'(\pi ')=\operatorname {touch}(\pi ). \end{equation*}$$

For instance, in the example above we would have $l=3$,

$$\begin{equation*} (t_0,t_1,t_2,t_3)=(17,16,11,9),\quad \operatorname {touch}'(\pi ')=\operatorname {touch}(\pi )=(1,5,2). \end{equation*}$$

Proof.

Consider the $i$th touch point $(x,x)$ of $\pi$ (we count the touch points starting from $0$, i.e., $(0,0)$ is the $0$th touch point.) It splits $\pi$ into two parts: $\pi _1$ followed by $\pi _2$. Construct a new path $\hat{\pi }$ of length $n+1$ by taking a step North, then following a translated copy of $\pi _2$, then taking a step East, then following a translated copy of $\pi _1$. The new path has length $n+1,$ and its area is bigger than the area of $\pi$ by $n-x$. The (area,dinv) to (bounce,area$'$) map applied to $\hat{\pi }$ gives precisely the path $N^{i+1}EN^{l-i}E \tilde{\pi }$. Thus we have

$$\begin{align*} \operatorname {area}(\hat{\pi }) &= \operatorname {bounce}(N^{i+1}EN^{l-i}E \tilde{\pi }) = t_i, \\ \operatorname {area}(\hat{\pi }) &= n-x+\operatorname {area}(\pi ) = n-x+\operatorname {bounce}(\pi '). \end{align*}$$

So the sizes of the gaps between the touch points of $\pi$ are exactly the differences $t_{i-1}-t_i$.

■

Remark 2.3.

The construction we have used in the proof above can also be used to prove the bijectivity of the (area,dinv) to (bounce,area$'$) map. Here is an idea of a proof. First, every Dyck path arises as $\hat{\pi }$ above for unique $\pi$ and $i$. On the other hand, every Dyck path can be uniquely written as $N^{i+1}EN^{l-i}E \tilde{\pi }$. Thus, iterating the construction, we obtain every Dyck path on each side of the (area,dinv) to (bounce,area$'$) map in a unique way.

Having analyzed the statistics associated to a Dyck path, we turn to the analysis of what happens to word parking functions. The $\operatorname {dinv}$ statistic is straightforward. For any $w'\in \mathbb{Z}_{>0}^n$, let

$$\begin{equation*} \operatorname {inv}(\pi ',w'):=\#\operatorname {Inv}(\pi ',w'),\quad \operatorname {Inv}(\pi ',w'):=\left\{(i,j) \in \operatorname {Area}(\pi '),\ w'_i>w'_j\right\}, \end{equation*}$$

so that

$$\begin{equation*} \operatorname {Inv}(\pi ',w')=\sigma \left(\operatorname {Dinv}(\pi ,w)\right),\quad w'_{\sigma _i}=w_{i}. \end{equation*}$$

For the value of $w$ from Example 2.1, we would have

$$\begin{equation*} w'=(9,5,3,2,2,1,5,2),\quad \operatorname {Inv}(\pi ',w')=\{(1,2),(1,3),(2,3),(3,4),(5,6)\}. \end{equation*}$$

In particular, $\operatorname {inv}(\pi ',w')=\operatorname {dinv}(\pi ,w)=5$.

Finally, we reconstruct the word parking function condition. A cell $(i,j)$ is called a corner of $\pi '$ if it is above the path, but both its Southern and Eastern neighbors are below the path. Denote the set of corners by $c(\pi ')$. One can check that the corners of $\pi '$ correspond to pairs of cells with one on top of the other in $\pi$. For instance, from our example we have $c(\pi ')=\{(2,4),(3,5),(4,6),(7,8)\}$. More precisely, we have

$$\begin{equation*} c(\pi ') := \{(\sigma _j, \sigma _{j+1}):\;1\leq j<n,\;x_j=x_{j+1}\}. \end{equation*}$$

We therefore define

$$\begin{equation} \mathcal{WP}'_{\pi '}:=\left\{w' \in \mathbb{Z}_{>0}^n : w'_i>w'_j \text{ for } (i,j) \in c(\pi ')\right\}, {\tag{2.4}} \end{equation}$$

so that the condition $w\in \mathcal{WP}_\pi$ is equivalent to $w'\in \mathcal{WP}'_{\pi '}$.

Putting this together, we have

Proposition 2.4.

For any composition $\alpha$ we have

$$\begin{equation} D_{\alpha }(q,t)= \sum _{\operatorname {touch}'(\pi )=\alpha } t^{\operatorname {bounce}(\pi )}\sum _{w \in \mathcal{WP}'_\pi } q^{\operatorname {inv}(\pi ,w)} x_w, {\tag{2.5}} \end{equation}$$

where $D_\alpha (q,t)$ is the right-hand side of 2.2.

3. Characteristic functions of Dyck paths

3.1. Simple characteristic function

We are going to study the summand in $D_{\alpha }(q,t)$ as a function of $\pi$. It is convenient to first introduce a simpler object where we drop the assumption $w\in \mathcal{WP}'_\pi$ and instead sum over all labelings. Given a Dyck path of length $n$, define $\chi (\pi )\in \operatorname {Sym}[X]$ as follows:

Definition 3.1.

$$\chi (\pi ): = \sum _{w \in \mathbb{Z}_{>0}^{n}} q^{\operatorname {inv}(\pi , w)} x_w.$$

If $i<j$ and $(i,j)$ is under $\pi$, i.e., $(i,j)\in \operatorname {Area}(\pi ),$ we say that $i$ and $j$ attack each other. It is not obvious from the definition that $\chi (\pi )$ defines a symmetric function. In fact, as we point out in Remark 3.6, $\chi (\pi )$ is actually an example of an LLT polynomial, but we present a proof in our setup here:

Proposition 3.2.

The expression for $\chi (\pi )$ above is symmetric in the variables $x_1, x_2, x_3,\ldots$, so that Definition 3.1 correctly defines an element of $\operatorname {Sym}[X]$.

Proof.

We take the main idea from the proof of Lemma 10.2 from HHL05a. First note that for each $n$ the correspondence $\pi \to \operatorname {Area}(\pi )$ is a bijection between the set of Dyck paths of length $n$ and the set of subsets $R\subset \{(j,j'):1\leq j<j'\leq n\}$ satisfying the property

$$\begin{equation*} \text{if $j<j'<j''$ and $(j,j'')\in R$, then both $(j,j')$ and $(j',j'')$ are in $R$.} \tag{*} \end{equation*}$$

In the proof we will work with $R$ instead of $\pi$ and write $\chi (R,n)$, $\operatorname {inv}(R,w)$ instead of $\chi (\pi )$, $\chi (\pi ,w)$. For each subset $S\subset \{1,2,\ldots ,n\}$, $S=\{s_1<s_2<\cdots <s_{\#S}\},$ let $R_S=\{(j,j'):\,(s_j,s_{j'})\in R\}$. Then $R_S$ again satisfies (*).

It is enough to show that $\chi (R,n)$ is unaffected by interchange of $x_i$ and $x_{i+1}$ for any two neighboring indices $i, i+1$. For each subset $S\subset \{1,2,\ldots ,n\}$ and a function $f:\{1,\ldots ,n\}\to \mathbb{Z}_{>0}\setminus \{i,i+1\},$ let $\chi _{S,f}$ be the sub-sum of $\chi (R,n)$ corresponding to sequences $w$ where the set of positions of $i$ and $i+1$ in $w$ is $S$, and the values of $w$ outside of $S$ are given by $f$. It is enough to show that $\chi _{S,f}$ is symmetric in $x_i$ and $x_{i+1}$. We have

$$\begin{equation*} \operatorname {inv}(R,w) = \#\{(j,j')\in R_S: w_{s_j}=i+1,\,w_{s_{j'}}=i\} + \operatorname {inv}_{S,f}, \end{equation*}$$

where $\operatorname {inv}_{S,f}$ depends only on $S$ and $f$, but does not depend on the positions of $i$ or $i+1$ in $S$. Thus we have

$$\begin{equation*} \chi _{S,f} = \chi (R_S,\#S)(x_i,x_{i+1}) \; q^{\operatorname {inv}_{S,f}} \prod _{j\notin S} x_{f(j)}, \end{equation*}$$

where

$$\begin{equation*} \chi (R,k)(x_1,x_2) = \sum _{w\in \{1,2\}^k} q^{\operatorname {inv}(R, w)} x_w. \end{equation*}$$

So it is enough to show that $\chi (R,k)(x_1,x_2)$ is symmetric in $x_1$ and $x_2$ for any $k$, $R$ satisfying (*). We proceed by induction on the size of $R$, the base case $\#R=0$ being trivial. Fix $k$ and $R\neq \varnothing$, and pick $(a,b)\in R$ maximal in the sense that $(a,j)\notin R$ for all $j>b$ and $(j,b)\notin R$ for all $j<a$. Then $R'=R\setminus \{(a,b)\}$ satisfies (*). Consider the difference

$$\begin{equation*} \chi (R,k) - \chi (R',k) = \sum _{w\in \{1,2\}^k} (q^{\operatorname {inv}(R, w)}-q^{\operatorname {inv}(R', w)}) x_w. \end{equation*}$$

The coefficient $(q^{\operatorname {inv}(R, w)}-q^{\operatorname {inv}(R', w)})$ is nonzero only if $w_a=2$ and $w_b=1$. If this happens, then $\operatorname {inv}(R,w)=\operatorname {inv}(R',w)+1$. Consider contributions of pairs of the form $(a,j)$, $(b,j)$, $(j,a)$, $(j,b)$ to $\operatorname {inv}(R',w)$. Since $w_a=2$ pairs $(j,a)$ do not contribute anything, and pairs $(a,j)$ contribute $1$ precisely when $a<j<b$ and $w_j=1$. Since $w_b=1$ pairs $(b,j)$ do not contribute, and pairs $(j,b)$ contribute $1$ precisely when $a<j<b$ and $w_j=2$. The net contribution is the number of $j$ such that $a<j<b$, which is $b-a-1$. We see that $\operatorname {inv}(R',w)=b-a-1 + \operatorname {inv}(R'_{S},w_S)$, where $S=\{1,\ldots ,k\}\setminus \{a,b\}$, $w_S$ denotes the sequence $w$ with the entries $w_a$ and $w_b$ removed. Thus we obtain

$$\begin{equation*} \chi (R,k) - \chi (R',k) = (q-1) x_1 x_2 \chi (R'_S,k-2). \end{equation*}$$

By the induction hypothesis $\chi (R',k)$ and $\chi (R'_S,k-2)$ are symmetric in $x_1, x_2$. Hence $\chi (R,k)$ is also symmetric.

■

Another way to formulate this property is as follows: For a composition $c_1+c_2+\cdots +c_k=n$, consider the multiset $M_c = 1^{c_1} 2^{c_2} \cdots k^{c_k}$. Consider the sum

$$\sum _{w \text{  a permutation of $M_c$}} q^{\operatorname {inv}(\pi , w)}.$$

Proposition 3.2 simply says that this sum does not depend on the order of the numbers $c_1, c_2, \ldots , c_k$, or equivalently on the linear order on the set of labels. If $\lambda$ is the partition with components $c_1,c_2,\ldots ,c_k$, then this sum computes the coefficient of the monomial symmetric function $m_\lambda$ in $\chi (\pi )$, so we have (set $h_c=h_{c_1}\cdots h_{c_k}$)

$$\begin{equation} (\chi (\pi ), h_c) = \sum _{w \text{  a permutation of $M_c$}} q^{\operatorname {inv}(\pi , w)}. {\tag{3.1}} \end{equation}$$

We list here a few properties of $\chi$ so that the reader has a feeling of what kind of object it is.

For a Dyck path $\pi$ denote by $\pi ^{op}$ the reversed Dyck path, i.e., the path obtained by replacing each North step by East step and each East step by North step and reversing the order of steps. Reversing also the order of the components of $c$ in 3.1, we see

Proposition 3.3.

$$\chi (\pi ) = \chi (\pi ^{op}).$$

Proofs of the following two statements are essentially taken from HHL05a.

Proposition 3.4.

$$\bar{\omega }\chi (\pi ) = (-1)^{|\pi |} q^{-\operatorname {area}(\pi )} \chi (\pi ).$$

Proposition 3.5.

$$\chi (\pi )[(q-1)X] = (q-1)^{|\pi |} \sum _{w \in \mathbb{Z}_{>0}^{|\pi |}\; \text{no attack}} q^{\operatorname {inv}(\pi , w)} x_w,$$

where “no attack” means that the summation is only over vectors $w$ such that $w_i\neq w_j$ for $(i,j)\in \operatorname {Area}(\pi )$.

Proofs.

We follow Chapter 4 of HHL05a. For an integer $n$ and a subset $D\subset \{1,\ldots ,n-1\},$ Gessel’s quasi-symmetric function $Q_{n,D}$ in $x=(x_1,x_2,\ldots )$ is given by

$$\begin{equation*} Q_{n,D}(x) = \sum _{\substack{w_1\leq \cdots \leq w_n \\ w_i=w_{i+1} \Rightarrow i\notin D}} x_w. \end{equation*}$$

For each sequence $w\in \mathbb{Z}_{>0}^n$, its standardization is the unique permutation $\operatorname {Std}(w)\in S_n$ such that

$$\begin{equation*} w_i<w_j\;\text{or}\;(w_i=w_j\;\text{and}\;i<j) \Leftrightarrow \operatorname {Std}(w)_i<\operatorname {Std}(w)_j. \end{equation*}$$

In other words, $\operatorname {Std}(w)$ sorts pairs $(w_i,i)$ in lexicographic order. We notice the following properties:

$$\begin{equation} \operatorname {Inv}(\pi , w) = \operatorname {Inv}(\pi ,\operatorname {Std}(w)),\qquad \sum _{w:\operatorname {Std}(w)=\sigma } x_w = Q_{n,\operatorname {Des}(\sigma ^{-1})}(x)\qquad (\sigma \in S_n), {\tag{3.2}} \end{equation}$$

where $\operatorname {Des}(\sigma ) = \{i:\sigma _i>\sigma _{i+1}\}$ is the descent set of $\sigma$. Thus the sum $\chi (\pi )$ splits as follows:

$$\begin{equation*} \chi (\pi ) = \sum _{\sigma \in S_n} q^{\operatorname {inv}(\pi , \sigma )} Q_{n,\operatorname {Des}(\sigma ^{-1})}. \end{equation*}$$

Since $\chi (\pi )$ is symmetric by Proposition 3.2, we can apply Proposition 4.2 in HHL05a. Let $\mathcal{A}$ be the “super” alphabet

$$\begin{equation*} \mathcal{A}=\mathbb{Z}_+\cup \mathbb{Z}_-=\{1,2,3,\ldots ,\bar{1},\bar{2},\bar{3},\ldots \} \end{equation*}$$

consisting of positive letters $i\in Z_+$ and negative letters $\bar{i}$. Let

$$\begin{equation*} z_i = x_i\quad (i\in \mathbb{Z}_+),\qquad z_{\overline{i}} = -y_i \quad (\bar{i}\in \mathbb{Z}_-). \end{equation*}$$

Then we have the following expression for $X=\sum _i x_i$, $Y=\sum _i y_i$:

$$\begin{equation*} \chi (\pi )[X-Y] = \sum _{\sigma \in S_n} q^{\operatorname {inv}(\pi , \sigma )} \tilde{Q}_{n,\operatorname {Des}(\sigma ^{-1})}(x,y), \end{equation*}$$

where

$$\begin{equation*} \tilde{Q}_{n,D} = \sum _{\substack{w_1\leq \cdots \leq w_n \\ w_i=w_{i+1},\,w_i\in \mathbb{Z}_+ \Rightarrow i\notin D \\ w_i=w_{i+1},\,w_i\in \mathbb{Z}_- \Rightarrow i\in D}} z_w, \end{equation*}$$

and the summation is over the sequences of elements of $\mathcal{A}$. The statement holds for an arbitrary choice of total ordering on $\mathcal{A}$. We work with the following ordering:

$$\begin{equation*} 1<\bar{1}<2<\bar{2}<\cdots {}. \end{equation*}$$

We extend the definitions of $\operatorname {Std}$, $\operatorname {Inv}$, and $\operatorname {inv}$ to sequences of elements of $\mathcal{A}$,

$$\begin{equation*} w_i<w_j\;\text{or}\;(w_i=w_j\in \mathbb{Z}_+\;\text{and}\;i<j) \;\text{or}\;(w_i=w_j\in \mathbb{Z}_-\;\text{and}\;i>j) \end{equation*}$$

$$\begin{equation*} \Leftrightarrow \operatorname {Std}(w)_i<\operatorname {Std}(w)_j, \end{equation*}$$

$$\begin{equation*} \operatorname {inv}(\pi ,w):=\#\operatorname {Inv}(\pi ,w),\ \, \operatorname {Inv}(\pi ,w):=\left\{(i,j) \in \operatorname {Area}(\pi ):\,w_i>w_j\;\text{or}\; w_i=w_j\in \mathbb{Z}_-\right\}\!, \end{equation*}$$

so that the properties 3.2 are satisfied. Therefore, we have

$$\begin{equation} \chi (\pi )[X-Y] = \sum _{w\in \mathcal{A}^n} q^{\operatorname {inv}(\pi ,w)} z_w. {\tag{3.3}} \end{equation}$$

Setting $X=0,Y=-X,$ we obtain

$$\chi (\pi )[-X] = (-1)^n \sum _{w\in \mathbb{Z}_{>0}^n} q^{\operatorname {inv}'(\pi , w)} x_w,$$

where $\operatorname {inv}'(\pi , w)$ is the number of nonstrict inversions of $w$ under the path,

$$\begin{equation*} \operatorname {inv}'(\pi ,w):=\#\left\{(i,j) \in \operatorname {Area}(\pi ),\ w_i\geq w_j\right\}. \end{equation*}$$

Reversing the order of labels, we have

$$\chi (\pi )[-X] = (-1)^{|\pi |} \sum _{w\in \mathbb{Z}_{>0}^n} q^{\operatorname {area}(\pi ) - \operatorname {inv}(\pi , w)} x_w,$$

which implies Proposition 3.4.

To prove Proposition 3.5, we set $X=qX$, $Y=X$ in 3.3. Applying the involution from the proof of Lemma 5.1 in HHL05a (flipping the sign of the last label that attacks a label with the same absolute value), we see that the terms for $w\in \mathcal{A}^n,$ such that $|w_i|=|w_j|$ for some $(i,j)\in \operatorname {Area}(\pi ),$ cancel out. In the remaining terms we have $|w_i|\neq |w_j|$ whenever $(i,j)\in \operatorname {Area}(\pi )$. Therefore the comparison between $w_i$ and $w_j$ depends only on $|w_i|$ and $|w_j|$. So we can first sum over sequences in $\mathbb{Z}_{>0}$ and then over the choices of signs. The latter summation produces an overall factor of $(q-1)^n$, and we obtain Proposition 3.5.

■

3.2. Weighted characteristic function

To study the summand of $D_{\alpha }(q,t)$ in (2.5) as a function of $\pi$, we introduce a more general characteristic function. Given a function $\mathrm{wt}:c(\pi )\to R$ on the set of corners of some Dyck path $\pi$ of size $n$, let

$$\begin{equation} \chi (\pi , \mathrm{wt}) := \sum _{w \in \mathbb{Z}_{>0}^{n}} q^{\operatorname {inv}(\pi ,w)} \left(\prod _{(i,j)\in c(\pi ),\;w_i\leq w_j} \mathrm{wt}(i,j) \right)x_w, {\tag{3.4}} \end{equation}$$

so in particular $(\xhref[disp-formula]{#texmlid4}{2.5})$ becomes

$$\begin{equation*} D_{\alpha }(q,t)=\sum _{\operatorname {touch}'(\pi )=\alpha } t^{\operatorname {bounce}(\pi )} \chi (\pi ,0). \end{equation*}$$

For a constant function $\mathrm{wt}=1$, we recover the simpler characteristic function

$$\begin{equation} \chi (\pi ,1)=\chi (\pi ). {\tag{3.5}} \end{equation}$$

It turns out that we can express the weighted characteristic function $\chi (\pi , \mathrm{wt})$ in terms the unweighted one evaluated at different paths. In particular this implies that $\chi (\pi , \mathrm{wt})$ is symmetric too.

Remark 3.6.

If $\pi '$ is the image of $\pi$ under the bijection from section 2.4, then we have that $\chi (\pi ',0)=F_{\pi }(X;q)$, where $F_{\pi }(X;q)$ are the path symmetric functions from Haglund’s book Hag08, page 95. As Haglund explains, these functions are examples of LLT polynomials of vertical strips, using the description of Bylund and Haiman. In fact, $\chi (\pi ',1)$ is also an example of an LLT polynomial, but for a disjoint union of single boxes:

$$\begin{equation*} \chi (\pi ',1)=\operatorname {LLT}_{[a_n+1]/[a_n],\ldots ,[a_1]/[a_1]}(X;q), \end{equation*}$$

where $(a_1,\ldots ,a_n)=a(\pi )$ is the area sequence.

Proposition 3.7.

We have that $\chi (\pi ,{\mathrm{wt}})$ is symmetric in the $x_i$ variables, and so it defines an element of $\operatorname {Sym}[X]$.

Proof.

Let $\pi$ be a Dyck path, and let $(i,j)\in c(\pi )$ be one of its corners. We denote by $\mathrm{wt}_1$ the weight on $\pi$ which is obtained from $\mathrm{wt}$ by setting the weight of $(i,j)$ to $1$. Let $\pi '$ be the Dyck path obtained from $\pi$ by turning the corner inside out, in other words the Dyck path of smallest area which is both above $\pi$ and above $(i,j)$. Let $\mathrm{wt}_2$ be the weight on $\pi '$ which coincides with $\mathrm{wt}$ on all corners of $\pi '$ which are also corners of $\pi$ and is $1$ on other corners. We claim that

$$\begin{equation} \chi (\pi , \mathrm{wt}) = \frac{q \mathrm{wt}(i,j) - 1}{q-1} \chi (\pi , \mathrm{wt}_1) + \frac{1 - \mathrm{wt}(i,j)}{q-1} \chi (\pi ', \mathrm{wt}_2). {\tag{3.6}} \end{equation}$$

To see this, notice that if we group the terms on the right-hand side, then both sides may be written as a sum over vectors $w\in \mathbb{Z}_{>0}$. Split both sums according to terms in which $w_{i}>w_{j}$, resulting in an additional factor of $q$, or $w_i\leq w_j$, resulting in an additional weight factor. It is easy to check that both sums agree on both the left and right sides.

The result now follows because we may recursively express any $\chi (\pi ,{\mathrm{wt}})$ in terms of $\chi (\pi )$, which we have already remarked is symmetric.

■

Example 3.8.

In particular, we can use this to extract $\chi (\pi ,0)$ from $\chi (\pi ',1)$ for all $\pi '$. If $S\subset c(\pi )$ is any subset of the set of corners, let $\pi _S\in \mathbb{D}$ denote the path obtained by flipping the corners that are in $S$. Then equation 3.6 implies that

$$\begin{equation} \chi (\pi ,0)=(1-q)^{-|c(\pi )|} \sum _{S \subset c(\pi )} (-1)^{|S|}\chi (\pi _S,1). {\tag{3.7}} \end{equation}$$

For instance, let $\pi$ be the Dyck path in Figure 4.

Then setting $x_i=0$ for $i>3$ reduces formula 3.4 to a finite sum over 27 terms, from which we can deduce that

$$\begin{equation*} \chi (\pi )=m_3+(2+q)m_{21}+(3+3q)m_{111}=s_3+(1+q)s_{21}+qs_{111}. \end{equation*}$$

Similarly, if $\pi '=\pi _{\{(1,2)\}}$, we have

$$\begin{equation*} \chi (\pi ')=s_3+2qs_{21}+q^2s_{111}. \end{equation*}$$

By formula 3.7 we obtain

$$\begin{equation*} \chi (\pi ,0)=(1-q)^{-1}\left(\chi (\pi )-\chi (\pi ')\right)=s_{21}+qs_{111}. \end{equation*}$$

Example 3.9.

We can check that the Dyck path from Example 3.8 is the unique one satisfying $\operatorname {touch}'(\pi )=(1,2)$ and that $\operatorname {bounce}(\pi )=1$. Therefore, using the calculation that followed, we have that

$$\begin{equation*} D_{(2,1)}(q,t)=t\chi (\pi ,0)=ts_{21}+qts_{111}, \end{equation*}$$

which can be seen to agree with $\nabla C_1 C_2(1)$.

Example 3.10.

Though we will not need it, this weighted characteristic function can be used to describe an interesting reformulation of the formula for the modified Macdonald polynomial given in HHL05a. Let $\mu =(\mu _1\geq \mu _2 \geq \cdots \geq \mu _l)$ be a partition of size $n$. Let us list the cells of $\mu$ in the reading order,

$$(l,1), (l,2), \ldots , (l, \mu _l), (l-1,1), \ldots , (l-1, \mu _{l-1}) ,\ldots , (1,1),\ldots , (1,\mu _1).$$

Denote the $m$th cell in this list by $(i_m, j_m)$.

We say that a cell $(i,j)$ attacks all cells which are after $(i,j)$ and before $(i-1,j)$. Thus $(i,j)$ attacks precisely $\mu _i-1$ following cells if $i>1$ and all following cells if $i=1$. Next construct a Dyck path $\pi _\mu$ of length $n$ in such a way that $(m_1, m_2)$ with $m_1<m_2$ is under the path if and only if $(i_{m_1}, j_{m_1})$ attacks $(i_{m_2}, j_{m_2})$. More specifically, the path begins with $\mu _l$ North steps, then it has $\mu _l$ pairs, of steps East-North, then $\mu _{l-1}-\mu _l$ North steps followed by $\mu _{l-1}$ East-North pairs and so on until we reach the point $(n-\mu _1, n)$. We complete the path by performing $\mu _1$ East steps.

Note that the corners of $\pi _\mu$ precisely correspond to the pairs of cells $(i,j), (i-1, j)$. We set the weight of such a corner to $q^{\mathrm{arm}(i,j)} t^{-1-\mathrm{leg}(i,j)}$ and denote the weight function thus obtained by $\mathrm{wt}_\mu$. Note that in our convention for $\chi (\pi ,\mathrm{wt})$ we should count noninversions in the corners, while in HHL05a they count “descents”, which translates to counting inversions in the corners. Taking this into account, we obtain a translation of their Theorem 2.2:

$$\tilde{H}_\mu = q^{-n(\mu ')+\binom{\mu _1}{2}} t^{n(\mu )} \chi (\pi _\mu , \mathrm{wt}_\mu ).$$

4. Raising and lowering operators

Now let $\mathbb{D}_{k,n}$ be the set of Dyck paths from $(0,k)$ to $(n,n)$, which we will call partial Dyck paths, and let $\mathbb{D}_k$ be their union over all $n$. For $\pi \in \mathbb{D}_{k,n}$, let $|\pi |=n-k$ denote the number of North steps. Unlike $\mathbb{D}$, the union of the sets $\mathbb{D}_k$ over all $k$ is closed under the operation of adding a North or East step to the beginning of the path, and any Dyck path may be created in such a way starting with the empty path in $\mathbb{D}_0$. This is the set of paths for which we will develop a recursion. More precisely, we will define an extension of the function $\chi$ to a map from $\mathbb{D}_k$ to a new vector space $V_k$, and prove that certain operators on these vector spaces commute with adding North and East steps.

Given a polynomial $P$ depending on variables $u, v,$ define

$$\begin{gather*} (\Delta _{uv} P)(u,v) = \frac{(q-1) v P(u,v) + (v - q u) P(v,u)}{v - u},\\ (\Delta _{uv}^* P)(u,v) = \frac{(q-1) u P(u,v) + (v - q u) P(v,u)}{v - u}. \end{gather*}$$

We can easily check that $\Delta _{uv}^* = q \Delta _{uv}^{-1}$. We can recognize these operators as a simple modification of Demazure–Lusztig operators. The following can be checked by direct computation:

Proposition 4.1.

We have the following relations:

$$\begin{gather*} (\Delta _{uv} - q) (\Delta _{uv} + 1) = 0,\qquad (\Delta _{uv}^* - 1) (\Delta _{uv}^* + q) = 0,\\ \Delta _{uv}\Delta _{vw}\Delta _{uv}=\Delta _{vw}\Delta _{uv}\Delta _{vw},\qquad \Delta _{uv}^*\Delta _{vw}^*\Delta _{uv}^*=\Delta _{vw}^*\Delta _{uv}^*\Delta _{vw}^*. \end{gather*}$$

Definition 4.2.

Let $V_k=\operatorname {Sym}[X]\otimes \mathbb{Q}[y_1,y_2,\ldots ,y_{k}]$, and let

$$\begin{equation*} T_i = \Delta _{y_i y_{i+1}}^* : V_{k} \rightarrow V_{k},\quad i=1,\ldots ,k-1. \end{equation*}$$

Define operators

$$\begin{equation*} d_{+} : V_k \rightarrow V_{k+1}, \quad d_- : V_{k} \rightarrow V_{k-1} \end{equation*}$$

by

$$\begin{equation} (d_{+} F)[X] = T_1 T_2\cdots T_k \left(F[X+(q-1)y_{k+1}]\right), {\tag{4.1}} \end{equation}$$

and

$$\begin{equation} (d_- F)[X] = -F[X-(q-1)y_k] \operatorname {Exp}[-y_k^{-1} X] |_{y_k^{-1}} {\tag{4.2}} \end{equation}$$

for $F\in V_k$.

Remark 4.3.

Note that the operator $d_-$ is related to the $B_i$ operators,

$$\begin{equation*} d_-(y_k^i F)= -B_{i+1} F \end{equation*}$$

for $F\in V_k$ which do not depend on $y_k$.

We now claim the following theorem:

Theorem 4.4.

For any Dyck path $\pi$ of size $n$, let $\epsilon _1\cdots \epsilon _{2n}$ denote the corresponding sequence of plus and minus symbols where a plus denotes an East step, and a minus denotes a North step reading $\pi$ from bottom left to top right. Then

$$\begin{equation*} \chi (\pi )=d_{\epsilon _1}\cdots d_{\epsilon _{2n}}(1) \end{equation*}$$

as an element of $V_0=\operatorname {Sym}[X]$.

Example 4.5.

Let $\pi$ be the Dyck path from Example 3.8. We have that

$$\begin{equation*} \begin{split} &d_- d_- d_+d_+d_-d_+(1)= d_- d_- d_+d_+d_-(1)=d_- d_- d_+d_+(s_1)\\ &\quad =d_- d_- d_+\left(s_1+(q-1)y_1\right)= d_- d_- \left(s_1+(q-1)(y_1+y_2)\right)\\ &\quad =d_- \left(s_2+s_{11}+(q-1)s_1y_1\right)=s_3+(1+q)s_{21}+qs_{111}, \end{split} \end{equation*}$$

which agrees with the value calculated for $\chi (\pi )$.

Combining this result with equation 3.7 implies the following:

Corollary 4.6.

The following procedure computes $\chi (\pi ,0)$: start with $1\in \operatorname {Sym}[X]=V_0$, follow the path from right to left applying $\frac{1}{q-1}[d_{-}, d_{+}]$ for each corner of $w$, and $d_{-}$ $(d_{+})$ for each North (resp. East) step that is not a side of a corner.

4.1. Rank experiment

The proof of Theorem 4.4 will be divided into several parts. However, before we proceed to the proof of Theorem 4.4, we would like to explain why we expected such a result to hold, and how we obtained it. In fact, the definition of $\chi _k$ from equation 4.5 in the proof below actually came first, and was discovered using computer experimentation, as we now explain.

First note that the number of Dyck paths of length $n$ is given by the Catalan number $C_n=\frac{1}{n+1} \binom{2n}{n}$ which grows exponentially with $n$. The dimension of the degree $n$ part of $\operatorname {Sym}[X]$ is the number of partitions of size $n$, which grows subexponentially. For instance for $n=3$, we have five Dyck paths but only three partitions. Thus there must be linear dependences between different $\chi (\pi )$.

Now fix a partial Dyck path $\pi _1\in \mathbb{D}_{k,n}$. For each partial Dyck path $\pi _2\in \mathbb{D}_{k,n'},$ we can reflect $\pi _2$ and concatenate it with $\pi _1$ to obtain a full Dyck path $\pi _2^{op}\pi _1$ of length $n+n'-k$. We may then consider its character $\chi (\pi _2^{op}\pi _1)$. We keep $n$, $\pi _1$ fixed and vary $n'$, $\pi _2$, thus obtaining a map $\varphi _{\pi _1}:\mathbb{D}_k\to \operatorname {Sym}[X]$. The map $\pi _1\to \varphi _{\pi _1}$ is a map from $\mathbb{D}_k$ to the vector space of maps from $\mathbb{D}_k$ to $\operatorname {Sym}[X]$, which is very high dimensional, because both the set $\mathbb{D}_k$ is infinite and $\operatorname {Sym}[X]$ is infinite dimensional. A priori, it could be the case that the images of the elements of $\mathbb{D}_{k,n}$ in $\mathrm{Maps}(\mathbb{D}_k,\operatorname {Sym}[X])$ are linearly independent. However, computer experiments convinced us that it is not the case, and that there should be a vector space $V_{k,n}$ whose dimension is generally smaller than the size of $\mathbb{D}_{k,n}$. In fact, by restricting $n'$ to be bounded by some arbitrary but large enough cut-off value, we were able to predict that the dimension of this space stabilizes to a very simple formula, which is the dimension of $V_{k,n}$, the degree $n-k$ component of $V_{k}$ as it is defined above.

We therefore predicted the existence of a commutative diagram

$$\begin{equation*} \vcenter{\img[][128pt][52pt][{\renewcommand{\arraystretch}{1} \setlength{\unitlength}{1.0pt} \begin{tikzcd} \DD_{k,n} \arrow{r}{\chi_{k,n}} \arrow{d}{\varphi} &amp; V_{k,n}\arrow{ld}\\ \mathrm{Maps}(\DD_k,\Sym[X]) &amp; \end{tikzcd}}]{Images/img67887469a1d8c82940d3de92f8a3d800.svg}} \end{equation*}$$

for some map $\chi _{k,n}$, whose image spans all of $V_{k,n}$. This ultimately led to the guess of the formula for $\chi _k$ in 4.5 as the correct extension of $\chi (\pi ,1)$. It is not at all trivial to deduce this formula from the dimension of $V_{k,n}$, and indeed, some substantial guesswork was required. However, the validity of any particular guess $\chi _{k,n}$ can be determined experimentally, by testing if its kernel in the $\mathbb{C}(q)$-span of $\mathbb{D}_{k,n}$ agrees with the kernel of $\varphi$. Clearly the existence of a testable criterion such as this makes the problem of determining $\chi _{k,n}$ experimentally much more reasonable.

Once the definition of $\chi _{k,n}$ was conjectured, finding formulas for $d_{\pm }$ that satisfy 4.6 turned out to be relatively straightforward.

4.2. Characteristic functions of partial Dyck paths

The following definition is motivated by Proposition 3.5. Let $\pi \in \mathbb{D}_{k,n}$. Let $\sigma =(\sigma _1, \sigma _2,\ldots ,\sigma _k)\in \mathbb{Z}_{>0}$ be a tuple of distinct numbers. The elements of $\mathrm{Im}(\sigma )\subset \mathbb{Z}_{>0}$ will be called special. Let

$$\begin{equation*} U_{\pi ,\sigma }=\left\{w\in \mathbb{Z}^{n}_{>0} : w_i=\sigma _i \text{ for } i \leq k,\ w_i \neq w_j \text{ for } (i,j) \in \operatorname {Area}(\pi )\right\}. \end{equation*}$$

The second condition on $w$ is the “no attack” condition as before. The first condition says that we put the special labels in the positions $1,2,\ldots ,k$ as prescribed by $\sigma$. Let

$$\begin{equation} \chi _\sigma '(\pi )=\sum _{w \in U_{\pi ,\sigma }} q^{\operatorname {inv}(\pi ,w)} z_w. {\tag{4.3}} \end{equation}$$

Here we use variables $z_1,z_2,\ldots$.

Suppose $\sigma$ is a permutation, i.e., $\sigma _i\leq k$ for all $i$. Set $z_i=y_i$ for $i\leq k$ and $z_i=x_{i-k}$ for $i>k$. We denote

$$\begin{equation*} \chi '_{k}(\pi )=\chi _{(1,2,\ldots ,k)}'(\pi ). \end{equation*}$$

Let us group the summands in 4.3 according to the positions of special labels. More precisely, let $S\subset \{1,\ldots ,n\}$ such that $\{1,\ldots ,k\}\subset S$ and $w^S:S\to \{1,\ldots ,k\}$ such that $w^S_i=\sigma _i$ for $i=1,2,\ldots ,k$ and $w_i\neq w_j$ for $i,j\in S$, $(i,j)\in \operatorname {Area}(\pi )$. Set

$$\begin{gather*} U_{\pi ,\sigma }^{S,w^S}:=\left\{w\in U_{\pi ,\sigma } : w_i=w^S_i\text{ for } i \in S,\; w_i>k\text{ for } i \notin S\right\},\\ \Sigma _{\pi ,\sigma }^{S,w^S}:=\sum _{w \in U_{\pi ,\sigma }^{S,w^S}} q^{\operatorname {inv}(\pi ,w)} x_w,\qquad \chi _\sigma '(\pi ) = \sum _{S, w^S} \Sigma _{\pi ,\sigma }^{S,w^S}. \end{gather*}$$

Let $m_1<m_2<\cdots <m_r$ be all the positions not in $S$. Let $\pi _S$ be the unique Dyck path of length $r$ such that $(i,j)\in \operatorname {Area}(\pi _S)$ if and only if $m_i, m_j\in \operatorname {Area}(\pi )$. We have

$$\begin{equation*} \Sigma _{\pi ,\sigma }^{S,w^S} = q^A \prod _{i\in S} y_{w_i} \sum _{w \in \mathbb{Z}_{>0}^{r} \text{no attack}} q^{\operatorname {inv}(\pi _S, w)} x_w, \end{equation*}$$

where

$$\begin{equation*} A=\#\{(i,j)\in \operatorname {Area}(\pi ) : (i\in S, j\in S, w^S_i>w^S_j) \text{ or } (i\notin S, j\in S)\}. \end{equation*}$$

By Proposition 3.5 we have

$$\begin{equation} \Sigma _{\pi ,\sigma }^{S,w^S} = q^A (q-1)^{|S|-n} \chi (\pi ^S)\left[(q-1)X\right] \prod _{i\in S} y_{w_i}. {\tag{4.4}} \end{equation}$$

In particular $\chi _\sigma (\pi )$ is a symmetric function in $x_1, x_2,\ldots ,$ and it makes sense to define

$$\begin{equation} \chi _\sigma (\pi )[X] := \frac{1}{y_1 y_2\cdots y_k} (q-1)^{|\pi |}\chi _\sigma '(\pi )\left[\frac{X}{q-1}\right]\in V_k,\quad \chi _k(\pi ):=\chi _{\operatorname {Id}_k}(\pi ). {\tag{4.5}} \end{equation}$$

Remark 4.7.

The identity (4.4) also implies that the coefficients of $\chi _\sigma (\pi )[X]$ are polynomials in $q$, and it gives a way to express $\chi _\sigma$ in terms of the characteristic functions $\chi (\pi _S)$ for all $S$.

For $k=0$, we recover $\chi (\pi )$:

$$\begin{equation*} \chi _0(\pi )=\chi (\pi )\qquad (\pi \in \mathbb{D}_0=\mathbb{D}). \end{equation*}$$

Thus, it suffices to prove that

$$\begin{equation} \chi _{k+1}(E\pi )=d_{+} \chi _{k}(\pi ),\quad \chi _{k-1}(N\pi )=d_{-} \chi _{k}(\pi ) \quad (\pi \in \mathbb{D}_k). {\tag{4.6}} \end{equation}$$

4.3. Raising operator

We begin with the first case. Let $\pi \in \mathbb{D}_{k,n}$ so that $E\pi \in \mathbb{D}_{k+1, n+1}$, and we need to express $\chi _{k+1}(E\pi )$ in terms of $\chi _k(\pi )$. Let $\sigma$ be the following sequence:

$$\begin{equation*} \sigma =(k+1, 1, 2, \ldots , k). \end{equation*}$$

Then we have a bijection $f:U_{\pi ,\operatorname {Id}_k} \to U_{E\pi ,\sigma }$ obtained by sending

$$\begin{equation*} w=(1, 2, \ldots , k, w_{k+1},\ldots ,w_n) \end{equation*}$$

to

$$\begin{equation*} f(w):=(k+1, 1, 2, \ldots ,k, w_{k+1},\ldots ,w_n). \end{equation*}$$

This is possible because $1$ does not attack $k+1$ in $E\pi$. We clearly have $\operatorname {inv}({E\pi }, f(w)) = \operatorname {inv}(\pi , w) + k$, which implies

$$\begin{equation*} \chi '_{\sigma }(E\pi ) = z_{k+1} q^k \chi '_k(\pi ), \end{equation*}$$

where both sides are written in terms of the variables $z_i$. When we pass to the variables $x_i$, $y_i$ on the left, we have

$$\begin{equation*} (z_1,z_2,\ldots )=(y_1,y_2,\ldots ,y_{k+1},x_1,x_2,\ldots ), \end{equation*}$$

but on the right we have

$$\begin{equation*} (z_1,z_2,\ldots )=(y_1,y_2,\ldots ,y_{k},x_1,x_2,\ldots ). \end{equation*}$$

Thus we need to perform the substitution $X=y_{k+1}+X$,

$$\begin{equation*} \chi '_{\sigma }(E\pi )[X] = y_{k+1} q^k \chi '_k(\pi )[X+y_{k+1}]. \end{equation*}$$

Performing the transformation 4.5, we obtain

$$\begin{equation} \chi _{\sigma }(E\pi ) = q^k \chi _k(\pi )\left[X+(q-1)y_{k+1}\right]. {\tag{4.7}} \end{equation}$$

To finish the computation, we need to relate $\chi _{k+1}=\chi _{\operatorname {Id}_{k+1}}$ and $\chi _\sigma$. We first note that $\sigma$ can be obtained from $\operatorname {Id}_{k+1}$ by successively swapping neighboring labels. Let $\sigma ^{(1)}=\operatorname {Id}_{k+1}$ and

$$\begin{equation*} \sigma ^{(i)} = (i, 1, 2,\ldots ,i-1,i+1,\ldots ,k+1)\qquad (i=2,3,\ldots ,k+1) \end{equation*}$$

so that $\sigma = \sigma ^{(k+1)}$. It is clear that $\sigma ^{(i+1)}$ can be obtained from $\sigma ^{(i)}$ by interchanging the labels $i$ and $i+1$.

We show below (Proposition 4.8) that this kind of interchange is controlled by the operator $\Delta _{y_i, y_{i+1}}$:

$$\begin{equation} \chi _{\sigma ^{(i+1)}}(E\pi )=\Delta _{y_i,y_{i+1}} \chi _{\sigma ^{(i)}}(E\pi ). {\tag{4.8}} \end{equation}$$

This implies

$$\begin{equation*} \chi _\sigma (E\pi ) = \Delta _{y_{k-1},y_{k}}\cdots \Delta _{y_{1},y_{2}} \chi _{k+1}(E\pi ). \end{equation*}$$

When we insert this equation into 4.7, we arrive at

$$\begin{equation*} \chi _{k+1}(E\pi ) = T_{1}\cdots T_{k} \left(\chi _k(\pi )\left[X+(q-1) y_{k+1}\right]\right) = d_+ \chi _k(\pi ). \end{equation*}$$

4.4. Swapping operators

Proposition 4.8.

For any $w\in \mathbb{D}_k$, $\sigma$ as above and $m$ special, suppose that $m+1$ is not special or $\sigma ^{-1}(m)<\sigma ^{-1}(m+1)$. Then we have

$$\begin{equation*} \chi '_{\tau _m \sigma }(w) = \Delta _{z_{m}, z_{m+1}} \chi '_{\sigma }, \end{equation*}$$

where $\tau _m$ is the transposition $m\leftrightarrow m+1$, $(\tau _m\sigma )_i = \tau _m(\sigma _i)$ for $i=1,\ldots ,k$.

Proof.

We decompose both sides as follows. For any $w \in U_{\pi , \sigma },$ let $S(w)$ be the set of indices $j$ where $w_j\in \{m,m+1\}$. For $w,w'\in U_{\pi , \sigma }$ write $w\sim w'$ if $S(w)=S(w')$ and $w_i=w_i'$ for all $i\notin S(w)$. This defines an equivalence relation on $U_{\pi , \sigma }$. The sum 4.3 is then decomposed as follows:

$$\begin{equation} \chi '_\sigma (\pi ) = \sum _{[w]\in U_{\pi , \sigma }/\sim } q^{\operatorname {inv}_1(\pi , w)} \prod _{i\notin S} z_{w_i} \sum _{w'\sim w} a(w'), {\tag{4.9}} \end{equation}$$

where

$$\begin{equation*} \operatorname {inv}_1(\pi , w) = \#\{(i,j)\in \operatorname {Area}(\pi ): w_i>w_j, i\notin S(w) \text{ or } j\notin S(w)\}, \end{equation*}$$

which does not depend on the choice of a representative $w$ in the equivalence class $[w]$, and

$$\begin{equation*} a(w) = q^{\operatorname {inv}_2(\pi , w)} \prod _{i\in S} z_{w_i}, \end{equation*}$$

$$\begin{equation*} \operatorname {inv}_2(\pi , w) = \#\{(i,j)\in \operatorname {Area}(\pi ): w_i>w_j, i,j \in S(w)\}. \end{equation*}$$

Let $f:U_{\pi , \sigma }\to U_{\pi , \tau _m\sigma }$ be the bijection defined by $f(w)_i = \tau _m(w_i)$. This bijection respects the equivalence relation $\sim$, and we have $S(f(w))=S(w)$. Moreover, we have $\operatorname {inv}_1(\pi , w) = \operatorname {inv}_1(\pi , f(w))$. We now make the stronger claim that for any $w\in U_{\pi , \sigma }$

$$\begin{equation} \sum _{w'\sim f(w)} a(w') = \Delta _{z_m,z_{m+1}} \sum _{w'\sim w} a(w'), {\tag{4.10}} \end{equation}$$

which would imply the statement by summing over all equivalence classes.

For each $w\in U_{\pi , \sigma },$ the set $S(w)$ is decomposed into a disjoint union of runs, i.e., subsets

$$\begin{equation*} R=\{j_1,\ldots ,j_l\} \subset \{1,\ldots ,n\},\quad j_1<\cdots <j_l \end{equation*}$$

such that in each run $j_a$ attacks $j_{a+1}$ for all $a$ and elements of different runs do not attack each other. Because of the nonattacking condition, the labels $w_{j_a}$ must alternate between $m,m+1,$ and $j_a$ does not attack $j_{a+2}$. Thus to fix $w$ in each equivalence class, it is enough to fix $w_{j_1}$ for each run. Suppose the runs of $S(w)$ have lengths $l_1, l_2,\ldots , l_r$ and the first values of $w$ in each run are $c_1, c_2,\ldots , c_r,$ respectively.

With this information $a(w)$ can be computed as follows:

$$\begin{equation*} a(w) = \prod _{i=1}^r a(l_i, c_i), \end{equation*}$$

where

$$\begin{equation*} a(l,c):= \begin{cases} q^{l'-1} z_{m}^{l'} z_{m+1}^{l'} & l=2l', c=m,\\ q^{l'} z_{m}^{l'+1} z_{m+1}^{l'} & l=2l'+1, c=m, \\ q^{l'} z_{m}^{l'} z_{m+1}^{l'} & l=2l', c=m+1, \\ q^{l'} z_{m}^{l'} z_{m+1}^{l'+1} & l=2l'+1, c=m+1. \end{cases} \end{equation*}$$

For instance, let $k=3$, and let $\pi$ be the Dyck path in Figure 5, and let

$$\begin{equation*} w=(1,3,2,7,1,7,1,2) \in U_{\pi ,(132)}. \end{equation*}$$

Let $m=1$. Then we have $S(w)=\{1,3,5,7,8\}$, which decomposes into two runs $\{1,3,5\}$ and $\{7,8\}$. So we have $r=2$, $(l_1, l_2)=(3, 2)$, $(c_1, c_2) = (1, 1)$ and we obtain

$$\begin{equation*} a(w)=a(3, 1) a(2, 1) = q z_1^2 z_2 z_1 z_2 = q z_1^3 z_2^2. \end{equation*}$$

Note that by the assumption on $\sigma ,$ we have $c_1=m$, while $c_i$ can take arbitrary values $\{m, m+1\}$ for $i>1$. This implies

$$\begin{equation*} \sum _{w'\sim w} a(w') = a(l_1, m) \prod _{i=2}^r (a(l_i, m) + a(l_i, m+1)). \end{equation*}$$

On the other hand we have

$$\begin{equation*} \sum _{w'\sim f(w)} a(w') = \sum _{w'\sim w} a(f(w')) = a(l_1, m+1) \prod _{i=2}^r (a(l_i, m) + a(l_i, m+1)). \end{equation*}$$

Now notice that for all $l$ the sum $a(l, m) + a(l, m+1)$ is symmetric in $z_m, z_{m+1}$. The operator $\Delta _{z_m,z_{m+1}}$ commutes with multiplication by symmetric functions and satisfies

$$\begin{equation*} \Delta _{z_m,z_{m+1}}(a(l, m)) = a(l, m+1). \end{equation*}$$

This establishes 4.10 and the proof is complete.

■

Remark 4.9.

The arguments used in the proof can be used to show that in the case when $m, m+1$ are both not special, the function $\chi '_\sigma (\pi )$ is symmetric in $z_m, z_{m+1}$. In particular, we can obtain a direct proof of the fact that $\chi '_\sigma$ is symmetric in the variables $z_m, z_{m+1}, z_{m+2},\ldots$ for $i=\max (\sigma )+1$, without use of Proposition 3.5.

4.5. Lowering operator

We now turn to the remaining identity $\chi _{k-1}(N\pi )=d_-\chi _k(\pi )$. Assume $\pi \in \mathbb{D}_{k,n}$, so that $N\pi \in \mathbb{D}_{k-1,n}$. We observe that

$$\begin{equation*} \chi '_{k-1}(N\pi )[X + y_{k}] = \sum _{r\geq 0} \chi '_{k,r}(\pi )[X], \end{equation*}$$

where

$$\begin{equation*} \chi '_{k,r}(\pi )=\chi '_{\sigma }(\pi ),\quad \sigma =(1,2,\ldots ,k-1,k+r), \end{equation*}$$

and to get to the second equality, we have summed over all possible values of $r=w_k-k$ that do not result in an attack. It is convenient to set $x_0=y_k$. Using Proposition 4.8, we can characterize $\chi '_{k,r}(\pi )$ by

$$\begin{equation} \chi '_{k,0}(\pi ) = \chi '_{k}(\pi ),\quad \chi '_{k,r+1}(\pi ) = \Delta _{x_r,x_{r+1}} \chi '_{k,r}(\pi )\quad (r\geq 0). {\tag{4.11}} \end{equation}$$

Now notice that there is a unique expansion

$$\begin{equation*} \chi '_{k}(\pi )[X]=\sum _{j \geq 1} y_k^j g_j(\pi )[X+y_k],\quad g_j(\pi )\in V_{k-1}. \end{equation*}$$

The advantage over the more obvious expansion in powers of $y_k$ is that each coefficient $g_j[X+y_k]$ is symmetric in the variables $y_k,x_1,\ldots .$ As a result, we have that

$$\begin{equation*} \chi '_{k,r}(\pi )[X]=\Delta _{x_{r-1},x_{r}}\cdots \Delta _{x_2,x_1}\Delta _{y_k,x_1} \sum _{i\geq 1} y_k^i g_i(\pi )[X+y_k]= \sum _{i\geq 1} f_{i,r} g_i(\pi )[X+y_k], \end{equation*}$$

where

$$\begin{equation*} f_{i,r}=\Delta _{x_{r-1},x_{r}}\cdots \Delta _{x_1,x_2}\Delta _{y_k,x_1}(y_k^i)\quad (i\geq 1, r\geq 0). \end{equation*}$$

The extra symmetry in the $y_k$ variable is used to pass $\Delta _{y_k,x_1}$ by multiplication by $g_i(\pi )[X+y_k]$.

Now we need an explicit formula for $f_{i,r}$:

Proposition 4.10.

Denote $X_r=y_k+x_1+\cdots +x_r$, $X_{-1}=0$. We have

$$\begin{equation*} f_{i,r}=\frac{h_i[(1-q)X_r] - h_i[(1-q)X_{r-1}]}{1-q}. \end{equation*}$$

Proof.

Denote the right-hand side by $f_{i,r}'$. The proof goes by induction on $r$. For $r=0$ both sides are equal to $y_k^i$. Thus it is enough to show that

$$\begin{equation} \Delta _{x_{r},x_{r+1}}(f'_{i,r})=f'_{i,r+1}. {\tag{4.12}} \end{equation}$$

Use $X_r=X_{r-1}+x_r$ to write $f_{i,r}'$ as

$$\begin{equation} f_{i,r}' = \sum _{j=1}^i x_r^j h_{i-j}[(1-q) X_{r-1}] = x_r h_{i-1}[(1-q) X_{r-1} + x_r]. {\tag{4.13}} \end{equation}$$

Now $X_{r-1}$ does not contain the variables $x_r$, $x_{r+1}$, so we have

$$\begin{equation*} \Delta _{x_{r},x_{r+1}}(f'_{i,r}) = \sum _{j=1}^i h_{i-j}[(1-q) X_{r-1}] \Delta _{x_{r},x_{r+1}} x_r^j. \end{equation*}$$

Using the formula

$$\begin{equation*} \Delta _{x_r, x_{r+1}} x_r^j = x_{r+1} h_{j-1}[(1-q)x_r + x_{r+1}], \end{equation*}$$

which is straightforward to check, we can evaluate

$$\begin{equation*} \begin{split} \Delta _{x_r x_{r+1}} f'_{i,r} &= x_{r+1}\sum _{j=1}^i h_{j-1}[(1-q)x_r + x_{r+1}] h_{i-j}[(1-q)X_{r-1}]\\ &= x_{r+1} h_{i-1}[(1-q) X_{r} + x_{r+1}], \end{split} \end{equation*}$$

which matches $f_{i,r+1}'$ by 4.13.

■

Now, if we sum over all $r$, we obtain

$$\begin{equation} \sum _{r \geq 0} f_{i,r}= (1-q)^{-1}h_i\left[(1-q)(X+y_k)\right]. {\tag{4.14}} \end{equation}$$

Thus

$$\begin{equation*} \chi _{k-1}'(N \pi )[X + y_{k}] = (1-q)^{-1} \sum _{i\geq 1} h_i[(1-q)(X+y_k)] g_i(\pi )[X+y_k]. \end{equation*}$$

This implies

$$\begin{equation} \chi _{k-1} (N\pi )[X] = - \frac{(q-1)^{n-k}}{y_1\cdots y_{k-1}} \sum _{i\geq 1} h_i[-X] g_i(\pi )\left[\frac{X}{q-1}\right]. {\tag{4.15}} \end{equation}$$

On the other hand $g_i(\pi )$ were defined in such a way that

$$\begin{equation*} \chi _k(\pi )[(q-1)X] = \frac{(q-1)^{n-k}}{y_1\cdots y_{k}} \sum _{i\geq 1} y_k^i g_i(\pi )[X+y_{k}]. \end{equation*}$$

Substituting $\frac{1}{q-1}X-y_k$ for $X$ gives

$$\begin{equation} \chi _k(\pi )[X-(q-1)y_k] = \frac{(q-1)^{n-k}}{y_1\cdots y_{k}} \sum _{i\geq 1} y_k^i g_i(\pi )\left[\frac{X}{q-1}\right]. {\tag{4.16}} \end{equation}$$

Comparing 4.15 and 4.16, we obtain

$$\begin{equation*} \chi _{k-1} (N\pi )[X] = \sum _{i\geq 0} -h_{i+1}[-X]\left(\chi _k(\pi )[X-(q-1)y_k]|_{y_k^i}\right). \end{equation*}$$

This can be seen to coincide with $d_- \chi _k(\pi )$, establishing the second case of 4.6. Thus the proof of Theorem 4.4 is complete.

4.6. Main recursion

We now show how to express all of $D_{\alpha }(q,t)$ using our operators:

Theorem 4.11.

If $\alpha$ is a composition of length $l$, we have

$$\begin{equation*} D_{\alpha }(q,t)=d_-^l(N_\alpha ), \end{equation*}$$

where $N_\alpha \in V_l$ is defined by the recursion relations

$$\begin{equation} N_{\emptyset }=1,\quad N_{[1,\alpha ]}=d_+N_{\alpha },\quad N_{a \alpha } = \frac{t^{a-1}}{q-1} [d_{-},d_{+}] \sum _{\beta \models a-1} d_{-}^{l(\beta )-1} N_{\alpha \beta }. {\tag{4.17}} \end{equation}$$

Proof.

For any $k> 0,$ let $\mathbb{D}_k^0\subset \mathbb{D}_k$ denote the subset of partial Dyck paths that begin with an East step. For $k=0,$ let $\mathbb{D}_0^0=\{\emptyset \}$. Define functions $\chi ^0:\mathbb{D}_k^0\rightarrow V_k$ by

$$\begin{equation*} \chi ^0(\emptyset )=1,\quad \chi ^0(EN^i\pi )=\frac{1}{q-1}[d_{-}, d_{+}] d_-^{i-1}\chi ^0(\pi ), \end{equation*}$$

$$\begin{equation*} \chi ^0(E\pi )=d_+\chi ^0(\pi ). \end{equation*}$$ Given a composition $\alpha$ of length $l$, let

$$\begin{equation*} \mathbb{D}_{\alpha }=\left\{\pi \in \mathbb{D}: \operatorname {touch}'(\pi )=\alpha \right\}. \end{equation*}$$

By the definition of $\operatorname {touch}'$, every element of $\mathbb{D}_{\alpha }$ is of the form $\pi =N^l \tilde{\pi }$ for a unique element $\tilde{\pi }\in \mathbb{D}_l^0$ so that by Corollary 4.6 we have

$$\begin{equation*} \chi (\pi , 0) = d_-^l \chi ^0_l(\tilde{\pi }). \end{equation*}$$

Let

$$\begin{equation*} N'_\alpha = \sum _{\pi \in \mathbb{D}_\alpha } t^{\operatorname {bounce}(\pi )}\chi _l^0(\tilde{\pi }) \in V_l, \end{equation*}$$

so that $D_{\alpha }(q,t)=d_-^l(N'_{\alpha })$. It suffices to show that $N'_\alpha$ satisfies the relations 4.17, and so agrees with $N_\alpha$.

For a composition $\alpha$ of length $l$ and $0\leq r\leq l$, we have a map $\gamma _{\alpha , r}: \mathbb{D}_\alpha \to \mathbb{D}$ as follows: $\gamma _{\alpha , r}(\pi ) = N^{r+1} E N^{l-r} \tilde{\pi }$. Clearly $|\gamma _{\alpha , r}(\pi )| = |\pi |+1$. From the definition of $\operatorname {touch}'$, we see the following relation:

$$\begin{equation*} \operatorname {bounce}(\gamma _{\alpha , r}(\pi )) = \operatorname {bounce}(\pi ) + \sum _{i>r} \alpha _i. \end{equation*}$$

Next we compute $\operatorname {touch}'(\gamma _{\alpha , r}(\pi ))$. For $0\leq i\leq r$, we have

$$\begin{equation*} \operatorname {bounce}(N^{i+2} E N^{r-i} E N^{l-r} \tilde{\pi }) = \operatorname {bounce}(N^{i+1} E N^{l-i} \tilde{\pi }). \end{equation*}$$

This implies

$$\begin{equation*} \operatorname {touch}'(\gamma _{\alpha , r}(\pi )) = \left(1+\sum _{i>r} \alpha _i,\, \alpha _1,\, \alpha _2,\ldots ,\, \alpha _r\right), \end{equation*}$$

so in particular $\operatorname {touch}'(\gamma _{\alpha , r}(\pi ))$ depends only on $\alpha$ and $r$.

Since every nonempty Dyck path can be obtained as $\gamma _{\alpha , r}(\pi )$ in a unique way, we obtain for every composition $\alpha$ of length $r$,

$$\begin{equation*} \mathbb{D}_{a\alpha } = \bigsqcup _{\beta \models a-1} \gamma _{\alpha \beta , r}(\mathbb{D}_{\alpha \beta }). \end{equation*}$$

It is not hard to see that this identity precisely translates to the relations 4.17 for $N_\alpha '$.

■

Example 4.12.

Using Theorem 4.11, we find that

$$\begin{equation*} \begin{split} N_{31}&=\frac{t^3}{(q-1)^2} \left(d_{-++-++}-d_{-+++-+}-d_{+-+-++}+d_{+-++-+}\right)\\ &\quad +[\frac{t^2}{q-1}\left(d_{-+-+++}-d_{+--+++}\right)= qt^3y_1^2-qt^2y_1 e_1\in V_2, \end{split} \end{equation*}$$

where $d_{\epsilon _1\cdots \epsilon _n}=d_{\epsilon _1}\cdots d_{\epsilon _n} (1).$ We may then check that

$$\begin{equation*} d_-^2 N_{31}=qt^3B_{3}B_1(1)+qt^2B_{2}B_1B_1(1)=\nabla C_{3}C_1(1). \end{equation*}$$

Example 4.13.

Let $\alpha =(a_1,\ldots ,a_k)$ be a composition of norm $n$ and length $k,$ and consider the polynomials in $q,t$ given by

$$\begin{equation*} D^{(-)}_{\alpha }(q,t)=\langle D_{\alpha }(q,t), e_n \rangle =(-1)^n D_{\alpha }(q,t)[-1], \end{equation*}$$

which encode the Catalan case of the compositional shuffle conjecture. This case of the conjecture was proved in GXZ12, using recursions (Proposition 3.12) that are similar to those defining $N_{\alpha }$ 4.17, and it is natural to ask if they follow as a special case. Indeed, this can be achieved with help of the following proposition:

Proposition 4.14.

Let $\pi$ be Dyck path of size $N$ ending with $k$ East steps, and let $(\epsilon _1,\ldots ,\epsilon _{2N-k}, +^k)$ denote the corresponding sequence of plus and minus symbols, as in Theorem 4.4. Then for $f\in V_k$, we have

$$\begin{equation} \left(d_{\epsilon _1}\cdots d_{\epsilon _{2N-k}} (f)\right)[-1]= (-1)^N q^{\operatorname {area}(\pi )} f[-q^k]\big |_{y_i=q^{i-1}}. {\tag{4.18}} \end{equation}$$

Proof.

We prove this by induction on $2N-k$, the number of $d_\pm$ symbols.

First, suppose the final step $\epsilon _{2N-k}$ is a plus. Let $\rho _k$ denote the homomorphism $f\mapsto f[-q^k]|_{y_i=q^{i-1}}$ on the right-hand side of 4.18. Using the definition 4.1 of $d_+$, and the observation that $\rho _k T_i=\rho _k$, we have that

$$\begin{equation*} \rho _{k+1}(d_+f)= \rho _{k+1}(f[X+(q-1)y_{k+1}])= \rho _k(f). \end{equation*}$$

The case now follows from the above equation, the induction step, and the fact that the path $\pi$ remains the same.

The second case follows easily from the formula

$$\begin{equation*} \rho _{k}(d_-(fy_{k+1}^a))=-q^{d+1-(k-1)a} \rho _k(f), \end{equation*}$$

for $f\in V_k$ homogeneous of degree $d$ in the symmetric function part. The base case is obvious.

■

The recursions of GXZ12 now follow fairly easily from 4.17 as a special case, if Theorem 4.11 is taken as the definition of $D_{\alpha }(q,t)$. The relations for $N_\alpha$ were not discovered this way, and the authors only noticed this connection after following up on a useful suggestion from one of the referees, for which the authors are grateful.

5. Operator relations

We have operators

$$\begin{equation} e_k,d_{\pm },T_i \mathrel{\vcenter{\img[][10pt][7pt][{\reflectbox{$\righttoleftarrow$}}]{Images/img9e69a78e384b741dc2b20ca62dfc1cd8.svg}}}V_*=V_0\oplus V_1\oplus \cdots , {\tag{5.1}} \end{equation}$$

where $e_k$ is the projection onto $V_k$, and the others are defined as above. It is natural to ask for a complete set of relations between them. They are formalized in the following algebra:

Definition 5.1.

The Dyck path algebra $\mathbb{A}=\mathbb{A}_q$ (over $R$) is the path algebra of the quiver with vertex set $\mathbb{Z}_{\geq 0}$, arrows $d_+$ from $i$ to $i+1$, arrows $d_-$ from $i+1$ to $i$ for $i\in \mathbb{Z}_{\geq 0}$, and loops $T_1, T_2, \ldots , T_{k-1}$ from $k$ to $k$ subject to the following relations:

$$(T_i-1)(T_i+q)=0,\quad T_i T_{i+1} T_i = T_{i+1} T_i T_{i+1}, \quad T_i T_j = T_j T_i\quad (|i-j|>1),$$

$$T_i d_- = d_- T_i,\quad d_+ T_i = T_{i+1} d_+, \quad T_1 d_+^2 = d_+^2,\quad d_-^2 T_{k-1} = d_-^2,$$

$$d_-(d_+ d_- - d_- d_+) T_{k-1} = q (d_+ d_- - d_- d_+) d_- \quad (k\geq 2),$$

$$T_1 (d_+ d_- - d_- d_+) d_+ = q d_+(d_+ d_- - d_- d_+),$$ where in each identity $k$ denotes the index of the vertex where the respective paths begin. We have used the same letters $T_i,d_{\pm }$ to label the $i$th loop at every node $k$ to match with the previous notation. To distinguish between different nodes, we will use $T_i e_k,$ where $e_k$ is the idempotent associated with node $k$.

We will prove:

Theorem 5.2.

The operators 5.1 define a representation of $\mathbb{A}$ on $V_*$. Furthermore, we have an isomorphism of representations

$$\begin{equation*} \varphi :\mathbb{A}e_0 \xrightarrow {\sim } V_*, \end{equation*}$$

which sends $e_0$ to $1\in V_0$, and maps $e_k \mathbb{A}e_0$ isomorphically onto $V_k$.

The proof will occupy the rest of this section. We begin by establishing that we have a defined a representation of the algebra.

Lemma 5.3.

The operators $T_i$ and $d_{\pm }$ satisfy the relations of Definition 5.1.

Proof.

The first line is just Proposition 4.1, and most follow from definition. The first one that does not is the commutation relation of $d_+$ with $T_i$. We have

$$\begin{equation*} \begin{split} d_+ T_i(F)&=T_1\cdots T_k\left((T_i F)[X+(q-1)y_{k+1}]\right)\\ &=T_1\cdots T_i T_{i+1} T_i \cdots T_k(F)[X+(q-1)y_{k+1}]\\ &=T_1\cdots T_{i+1} T_{i} T_{i+1} \cdots T_k(F)[X+(q-1)y_{k+1}]= T_{i+1} d_+(F), \end{split} \end{equation*}$$

using the braiding relations.

For the next, we have

$$\begin{equation*} \begin{split} d_+^2 F &= T_1 T_2\cdots T_{k+1} T_1 T_2 \cdots T_k(F[X+(q-1) y_{k+1}+(q-1) y_{k+2}])\\ &=T_2 T_3\cdots T_{k+1} T_1 T_2\cdots T_{k+1} (F[X+(q-1) y_{k+1}+(q-1) y_{k+2}]). \end{split} \end{equation*}$$

The last $T_{k+1}$ can be removed because its argument is symmetric in $y_{k+1}$ and $y_{k+2}$, and we obtain $T_1^{-1} d_+^2 F$.

The next identity is more technical. The operator image of $T_{k-1}-1$ consists of elements of the form $(q y_{k-1} - y_k) F$, where $F$ is symmetric in $y_{k-1}$ and $y_k$. Thus we need to check that $d_-^2$ vanishes on such elements. Let us evaluate $d_-^2$ on

$$(q y_{k-1} - y_k) y_{k-1}^a y_{k} ^b F,$$

where $F$ does not contain the variables $y_{k-1}$ and $y_k$, and $a,b\in \mathbb{Z}_{\geq 0}$. We obtain

$$(q B_{a+2} B_{b+1} - B_{a+1} B_{b+2}) F.$$

This expression is antisymmetric in $a$, $b$ by Corollary 3.4 of HMZ12, which implies our identity.

Next using the previous relations and Lemma 5.4 below write

$$\begin{equation} \begin{split} &d_- (d_+ d_- - d_- d_+) T_{k-1} = (q-1) d_- T_1 T_2 \cdots T_{k-1} y_k T_{k-1}\\ &\quad =q (q-1) d_- T_1 T_2 \cdots T_{k-2} y_{k-1}\\ &\quad =q (q-1) T_1 T_2 \cdots T_{k-2} y_{k-1} d_- = q (d_+ d_- - d_- d_+) d_-. \end{split}{\tag{5.2}} \end{equation}$$

Similarly,

$$\begin{align} &T_1 (d_+ d_- - d_- d_+) d_+ = (q-1) T_1 T_1 T_2 \cdots T_{k} y_{k+1} d_+ \\ &\quad =(q-1) q^k T_1 y_1 T_1^{-1} T_2^{-1} \cdots T_k^{-1} d_+= (q-1) q^k T_1 y_1 T_1^{-1} d_+ T_1^{-1} \cdots T_{k-1}^{-1} {\tag{5.3}}\\ &\quad = (q-1) q^k d_+ y_1 T_1^{-1} \cdots T_{k-1}^{-1} = q d_+(d_+ d_- - d_- d_+). \end{align}$$■

To establish the isomorphism, we first show that we can produce the operators of multiplication by $y_i$ from $\mathbb{A}$.

Lemma 5.4.

For $F\in V_k$, we have

$$\begin{equation} (d_{-} d_{+} - d_{+} d_{-}) F = (q-1) T_1 T_2\cdots T_{k-1} (-y_k F),\quad y_i = \frac{1}{q} T_i y_{i+1} T_i. {\tag{5.4}} \end{equation}$$

Proof.

First, we endow $V_k$ with the following twisted action of $\operatorname {Sym}[X]$:

$$\begin{equation*} (F\ast G)[X] = F\left[X+(q-1)\sum _{i=1}^k y_i\right] G, \end{equation*}$$

for $F\in \operatorname {Sym}[X]$, and $G\in V_k.$ It can be checked that the operators $d_{+}$, $d_{-}$ intertwine this action:

$$\begin{equation} d_{+} (F\ast G) = F\ast d_{+} G, \quad d_{-} (F\ast G) = F\ast d_{-} G. {\tag{5.5}} \end{equation}$$

For the second one, for instance, it suffices to assume that $k=1$. Then by the definition of $d_-$ given in 4.2, we have

$$\begin{equation*} d_-(F[X+(q-1)y_1] G)=-F[X] G[X-(q-1)y_1]\operatorname {Exp}[-y_1^{-1}X] \big |_{y_1^{-1}}=F \ast d_-G. \end{equation*}$$

We will not need this, but in fact, if $\pi _1\in \mathbb{D}_k$, $\pi _2\in \mathbb{D}$, and $\pi _1 \cdot \pi _2\in \mathbb{D}_k$ is their concatenation, then we must also have that

$$\begin{equation*} \chi _k(w_1\cdot w_2) = \chi (w_2) \ast \chi _k(w_1). \end{equation*}$$

Since the operators on both sides commute with the twisted action of $\operatorname {Sym}[X]$ introduced above, we may assume without loss of generality that $F$ is a polynomial of $y_1,y_2,\ldots ,y_k$.

Write the left-hand side of the first identity as

$$\begin{equation*} d_{-} T_1 \cdots T_{k-1} T_k F - T_1\cdots T_{k-1} \left((d_{-} F)[X+(q-1) y_k]\right). \end{equation*}$$

The operator $d_{-}$ in the first summand involves only the variable $y_{k+1}$. Thus we can write the left-hand side as

$$T_1 \cdots T_{k-1} (d_{-} T_k F - (d_{-}F)[X+(q-1) y_k]).$$

Hence it is enough to prove

$$d_{-} T_k F - (d_{-}F)[X+(q-1) y_k] = (1-q) y_k F.$$

It is clear that none of the operations involve the variables $y_1, y_2, \ldots , y_{k-1}$. Thus we can assume $F=y_k^i$ for $i\in \mathbb{Z}_{\geq 0}$ without loss of generality. Direct computation gives

$$T_k(y_k^i)=y_{k+1}^i + (1-q) \sum _{j=1}^i y_k^j y_{k+1}^{i-j}.$$

Thus the left-hand side equals

$$\begin{equation*} \begin{split} &-h_{i+1}[-X] - (1-q)\sum _{j=1}^i y_k^j h_{i-j+1}[-X] + h_{i+1}[-X-(q-1)y_k]\\ &\qquad =- (1-q)\sum _{j=1}^i y_k^j h_{i-j+1}[-X] + (1-q)\sum _{j=1}^{i+1} y_k^j h_{i-j+1}[-X]= (1-q) y_k^{i+1}. \end{split} \end{equation*}$$

The second relation is easy.

■

The operators of multiplication by $y_i$ are characterized by these relations and therefore come from elements of $\mathbb{A}$. We next establish the relations these operators satisfy within $\mathbb{A}$:

Lemma 5.5.

For $k\in \mathbb{Z}_{>0}$ define elements $y_1,\ldots ,y_k\in e_k \mathbb{A}e_k$ by solving for $y_iF$ in the identities 5.4. Then the following identities hold in $\mathbb{A}$:

$$\begin{align*} y_i T_j & = T_j y_i\qquad \text{for $i\notin \{j,j+1\}$,} \\ y_i d_- & = d_- y_i,\quad d_+ y_i = T_1 T_2 \cdots T_i y_i (T_1 T_2 \cdots T_i)^{-1} d_+, \\ y_i y_j & = y_j y_i\quad \text{ for any $i,j$.} \end{align*}$$

Proof.

Note that $y_1$ can be written as

$$y_1 = \frac{1}{q^{k-1}(q-1)} (d_+ d_- - d_- d_+) T_{k-1} \cdots T_1.$$

Our task becomes easier if we notice that it is enough to check the first identity for $i=1$ and $i=k$, the second one for $i=k$, the third one for $i=1,$ and the last one for $i=1$, $j=k$. The other cases can be deduced from these by applying the $T$-operators.

For $j>1,$ we have

$$\begin{align*} y_1 T_j & = \frac{1}{q^{k-1}(q-1)} (d_+ d_- - d_- d_+) T_{k-1} \cdots T_1 T_j\\ & = \frac{1}{q^{k-1}(q-1)} (d_+ d_- - d_- d_+) T_{j-1} T_{k-1} \cdots T_1 = T_j y_1. \end{align*}$$

Similarly, we verify that $y_k$ commutes with $T_j^{-1}$ hence with $T_j$ for $j<k-1$.

Reversing the arguments in 5.2 and 5.3, we verify the second and the third identities.

Thus it is left to check that $y_k y_1 = y_1 y_k$. We assume $k\geq 2$. Write the left-hand side as

$$\begin{equation*} \begin{split} y_k y_1 &=\frac{1}{q-1} T_{k-1}^{-1} \cdots T_1^{-1} (d_+ d_- - d_- d_+) y_1\\ &= \frac{1}{q-1} T_{k-1}^{-1} \cdots T_1^{-1} (T_1 y_1 T_1^{-1}) (d_+ d_- - d_- d_+), \end{split} \end{equation*}$$

using the already established commutation relations and that $k\geq 2$ to swap $T_1 y_1 T_1^{-1}$ and $d_-$. Performing the cancellation, we obtain $y_1 y_k$.

■

The following lemma completes the proof of the theorem:

Lemma 5.6.

The elements of the form

$$\begin{equation} d_-^m y_1^{a_1} \cdots y_{k+m}^{a_{k+m}} d_+^{k+m} e_0 {\tag{5.6}} \end{equation}$$

with $a_{k+1}\geq a_{k+2}\geq \cdots \geq a_{k+m}$ form a basis of $\mathbb{A}e_0$. Furthermore, the representation $\varphi$ maps these elements to a basis of $V_*$.

Proof.

We first show that elements of the form 5.6, with no condition on the $a_i$ span $\mathbb{A}$. It suffices to check that the span of these elements is invariant under $d_-$, $T_i$, and $d_+$. This can be done by applying the following reduction rules that follow from the definition of $\mathbb{A}$ and Lemma 5.5:

$$\begin{equation*} T_i d_- \to d_- T_i,\quad T_j y_i \to y_i T_j \quad (i\notin \{j,j+1\}), \end{equation*}$$

$$\begin{equation*} T_i y_i \to y_{i+1} T_i + (1-q) y_i, \quad T_i y_{i+1} \to y_{i} T_i + (q-1) y_i, \end{equation*}$$

$$\begin{equation*} T_i d_+^{k+m} e_0 \to d_+^{k+m} e_0, \end{equation*}$$

$$\begin{equation*} d_+ d_- \to d_- d_+ + (q-1) T_1 T_2 \cdots T_{k-1} y_k,\quad y_i d_- \to d_- y_i. \end{equation*}$$

The next step is to reduce the spanning set. We can use the following identity, which follows from $d_-^2 T_{k-1}=d_-^2$:

$$\begin{equation*} d_-^m (1-T_j) y_1^{a_1}\cdots y_{k+m}^{a_{k+m}} d_+^{k+m} e_0 = 0 \qquad (k<j<k+m). \end{equation*}$$

Note that $T_j$ commutes with $y_j y_{j+1}$. Suppose $a_j<a_{j+1}$. Then we can rewrite the above identity as

$$\begin{equation*} 0=d_-^m y_1^{a_1}\cdots y_j^{a_j} y_{j+1}^{a_j} (1-T_j) y_{j+1}^{a_{j+1}-a_j} y_{j+2}^{a_{j+2}} \cdots y_{k+m}^{a_{k+m}} d_+^{k+m} e_0. \end{equation*}$$

Using $T_j y_{j+1} = y_j (T_j+(q-1))$, $T_j y_r = y_r T_j$ for $r>j+1$, and $T_j d_+^{k+m} e_0=d_+^{k+m} e_0$, we can rewrite the identity as vanishing of a linear combination of terms of the form 5.6, and the lexicographically smallest term is precisely

$$\begin{equation*} d_-^m y_1^{a_1}\cdots y_{k+m}^{a_{k+m}} d_+^{k+m} e_0. \end{equation*}$$

Thus we can always reduce terms of the form 5.6 which violate the condition $a_{k+1}\geq a_{k+2}\geq \cdots \geq a_{k+m}$ to a linear combination of lexicographically greater terms, showing that the subspace in the lemma at least spans $\mathbb{A}e_0$.

We now show that they map to a basis of $V_*$, which also establishes that they are independent, completing the proof. Consider the image of the elements of our spanning set

$$\begin{gather} d_-^m y_1^{a_1} \cdots y_{k+m}^{a_{k+m}} d_+^{k+m} (1) = d_-^m (y_1^{a_1} \cdots y_{k+m}^{a_{k+m}}),\\ (-1)^m y_1^{a_1} y_2^{a_2} \cdots y_k^{a_k} B_{a_{k+1}+1} B_{a_{k+2}+1} \cdots B_{a_{k+m}+1} (1). {\tag{5.7}} \end{gather}$$

Notice that $\lambda :=(a_{k+1}+1,a_{k+2}+1,\ldots ,a_{k+m}+1)$ is a partition, so

$$\begin{equation*} B_{a_{k+1}+1} B_{a_{k+2}+1} \cdots B_{a_{k+m}+1} (1) \end{equation*}$$

is a multiple of the Hall–Littlewood polynomial $\tilde{H}_{\lambda '}[-X;1/q,0]$. These polynomials form a basis of the space of symmetric functions, thus the elements 5.7 form a basis of $\bigoplus _{k\in \mathbb{Z}_{\geq 0}} V_k$.

■

6. Conjugate structure

It is natural to ask if there is a way to extend $\nabla$ to the spaces $V_k$ recovering the original operator at $k=0$. What we have found is that it is simpler to extend the composition

$$\begin{equation} \mathcal{N}(F)=\nabla \bar{\omega }F=\nabla \omega \overline{F}, {\tag{6.1}} \end{equation}$$

where the conjugation simply makes the substitution $(q,t)=(q^{-1},t^{-1})$, $\omega (F)=F[-X]$ is the Weyl involution up to a sign, and $\bar{\omega }$ denotes the composition. This is a very interesting operator, which in fact is an antilinear involution on $\operatorname {Sym}[X]$ corresponding to dualizing vector bundles and tensoring with $\mathcal{O}(1)$ in the Haiman–Bridgeland–King–Reid picture, which identifies $\operatorname {Sym}[X]$ with the equivariant $K$-theory of the Hilbert scheme of points in the complex plane BKR01. The key to our proof is to extend this operator to an antilinear involution on every $V_k$, suggesting that $V_k$ should have a geometric interpretation as well. Since this paper was completed, E. Gorsky and the authors have discovered this connection in terms of a smooth subscheme of the flag Hilbert scheme. This will be explained in an upcoming paper, which also explains a family of ways to extend the operator $\nabla$ itself in addition to the involution $\mathcal{N}$, also in terms of line bundles.

We will define the operator, which was discovered experimentally to have nice properties, by explicitly constructing the action of $\mathbb{A}$ conjugated by the conjectural involution $\mathcal{N}$. Let $\mathbb{A}^*=\mathbb{A}_{q^{-1}}$, and label the corresponding generators by $d^*_{\pm },T_i^*,e_i^*$. Denote by $z_i$ the image of $y_i$ under the isomorphism from $\mathbb{A}$ to $\mathbb{A}^*$ which sends generators to generators, and which is antilinear with respect to $q\mapsto q^{-1}$.

Theorem 6.1.

There is an action of $\mathbb{A}^*$ on $V_*$ given by the assignment

$$\begin{equation} T_i^*=T^{-1}_i,\quad d^*_{-}=d_-,\quad e_i^*=e_i,\quad (d_+^* F)[X] = \gamma F[X+(q-1)y_{k+1}], {\tag{6.2}} \end{equation}$$

where $F\in V_k$ and $\gamma$ is the operator which sends $y_i$ to $y_{i+1}$ for $i=1,\ldots ,k$ and $y_{k+1}$ to $t y_1$. Furthermore, it satisfies the additional relations

$$\begin{equation} z_{i+1} d_+ = d_+ z_i,\quad y_{i+1} d_+^* = d_+^* y_i,\quad z_1 d_+ = -y_1 d_+^* t q^{k+1},\quad d_+^* d_+^m (1) = d_+^{m+1}(1) {\tag{6.3}} \end{equation}$$

for any $m\geq 0$.

The statement is equivalent to validity of a certain set of relations satisfied by the operators. These will be verified in the following propositions.

First we list the obvious relations:

Proposition 6.2.

$$d_+^* T_i^{-1} = T_{i+1}^{-1} d_+^*, \qquad T_1^{-1} d_+^{*2} = d_+^{*2}, \qquad d_+^* y_i = y_{i+1} d_+^*.$$

Proof.

Easy from the definition.

■

To verify the rest of the relations, we use an approach similar to the one used in the proof of Lemma 5.4. Now we need not just one, but a family of twisted multiplications: For $F\in \operatorname {Sym}[X]$, $G\in V_k$, $m=0,1,2,\ldots ,k,$ put

$$\begin{equation*} (F \ast _m G)[X] = F\left[X + (q-1)\left(\sum _{i=1}^m t y_i + \sum _{i=m+1}^k y_i\right)\right] G. \end{equation*}$$

It is not hard to show that they satisfy

$$\begin{equation} d_+^*(F\ast _m G) = F \ast _{m+1} d_+^* G,\quad d_-(F\ast _m G) = F\ast _m d_- G, {\tag{6.4}} \end{equation}$$

where $F\in \operatorname {Sym}[X]$, and $G\in V_k$, the first identity holds for $0\leq m\leq k$, and the second one for $0\leq m<k$.

Let us first verify

Proposition 6.3.

$$\begin{equation} d_-(d_+^* d_- - d_- d_+^*) T_{k-1}^{-1} = q^{-1} (d_+^* d_- - d_- d_+^*) d_-\quad (k\geq 2). {\tag{6.5}} \end{equation}$$

Proof.

Rewrite it as

$$d_+^* d_-^2 - d_- d_+^* d_- (T_{k-1} + q) + q d_-^2 d_+^* = 0.$$

Multiplying both sides by $q-1=T_{k-1}-1 + q-T_{k-1}$ produces an equivalent relation, which can be reduced to

$$(d_+^* d_-^2 - (q+1) d_- d_+^* d_- + q d_-^2 d_+^*)(T_{k-1}+q) = 0.$$

Note that the image of $T_{k-1}+q$ consists of elements which are symmetric in $y_{k-1}$, $y_k$. Let

$$A=d_+^* d_-^2 - (q+1) d_- d_+^* d_- + q d_-^2 d_+^*.$$

It is enough to show that $A$ vanishes on elements of $V_k$ that are symmetric in $y_{k-1}$, $y_k$. We have (recall that $k\leq 2$)

$$A(F\ast G) = F \ast _1 A (G),\quad A y_i = y_{i+1} A \quad (F\in \operatorname {Sym}[X],\, G\in V_k,\, i<k-1).$$

Thus it is enough to verify vanishing of $A$ on symmetric polynomials of $y_{k-1}, y_k$. We evaluate $A$ on $y_{k-1}^a y_k^b$:

$$\begin{multline*} A (y_{k-1}^a y_k^b) = \big (\Gamma _+(t(q-1)y_1) B_{a+1} B_{b+1} - (q+1) B_{a+1} \Gamma _+(t(q-1)y_1) B_{b+1}\\ + q B_{a+1} B_{b+1} \Gamma _+(t(q-1)y_1) \big ) 1, \end{multline*}$$

where $\Gamma _+(Z)$ is the operator $F[X]\to F[X+Z]$. For any monomial $u$ and integer $i$, we have operator identities

$$\Gamma _+(u) B_i = (B_i - u B_{i-1}) \Gamma _+(u),\quad B_i \Gamma _+(-u) = \Gamma _+(-u)(B_i - u B_{i-1}),$$

thus we have

$$\begin{align*} \Gamma _+(t(q-1)y_1) B_{a+1} B_{b+1} &= \Gamma _+(-ty_1) (B_{a+1} - qty_1 B_a) (B_{a+1} - qty_1 B_a) \Gamma _+(qty_1), \\ B_{a+1} \Gamma _+(t(q-1)y_1) B_{b+1} &= \Gamma _+(-ty_1) (B_{a+1} - ty_1 B_a) (B_{a+1} - qty_1 B_a) \Gamma _+(qty_1),\\ B_{a+1} B_{b+1} \Gamma _+(t(q-1)y_1) &= \Gamma _+(-ty_1) (B_{a+1} - ty_1 B_a) (B_{a+1} - ty_1 B_a) \Gamma _+(qty_1). \end{align*}$$

Performing the cancellations, we arrive at

$$A (y_{k-1}^a y_k^b) = \Gamma _+(-ty_1) (t y_1 (1-q) (B_{a} B_{b+1} - q B_{a+1} B_b)) 1.$$

This expression is antisymmetric in $a$, $b$ by HMZ12, Corollary 3.4. Thus 6.5 is true.

■

Next we have to check:

Proposition 6.4.

$$\begin{equation*} T_1^{-1} (d_+^* d_- - d_- d_+^*) d_+^* = q^{-1} d_+^*(d_+^* d_- - d_- d_+^*). \end{equation*}$$

Proof.

Multiplying both sides by $q T_1$ and using the easier relations, rewrite it as

$$d_+^{*2} d_- - (T_1+q) d_+^* d_- d_+^* + q d_- d_+^{*2} = 0.$$

Again, because of the commutation relations with the twisted multiplication by symmetric functions and $y_i$, it is enough to evaluate the left-hand side on $y_k^a$ for all $a\in \mathbb{Z}_{\geq 0}$. We obtain

$$- h_{a+1}[-X - t(q-1)(y_1+y_2)] + (T_1+q) h_{a+1}[-X-t(q-1)y_1] - q h_{a+1}[-X].$$

We use the identity $h_n[X+Y]=\sum _{i+j=n} h_i[X] h_j[Y]$ to write the left-hand side as a linear combination of terms $h_{a+1-b}[-X]$ with $b>0$. The coefficient in front of each term with $b>0$ is

$$- h_{b}[t(1-q)(y_1+y_2)] + (T_1+q) h_{b}[t(1-q)y_1]{}.$$

By a direct computation,

$$\begin{equation*} \begin{split} &(T_1+q) h_{b}[t(1-q)y_1] = (T_1+q) (1-q) t^b y_1^b \\ &\quad =(1-q) t^b (y_1^b + (1-q)\sum _{i=1}^{b-1} y_1^i y_2^{b-i} + y_2^b) = h_{b}[t(1-q)(y_1+y_2)], \end{split} \end{equation*}$$

and we are done.

■

At this point, we have established the fact that the operators given by 6.2 define an action of $\mathbb{A}^*$ on $V_*$. Also we have established the second relation in 6.3. The last relation is obvious. The first and the third are verified below:

Proposition 6.5.

$$z_1 d_+ = -y_1 d_+^* t q^{k+1},\qquad z_{i+1} d_+ = d_+ z_i.$$

Proof.

Using 6.4 we see that the operator $y_1 d_+^*$ satisfies the two properties,

$$\begin{equation*} y_1 d_+^* y_i = y_{i+1} y_1 d_+^*,\qquad y_1 d_+^* (F\ast G) = F \ast _1 y_1 d_+^*(G) \end{equation*}$$

for $F\in \operatorname {Sym}[X]$, $G\in V_k$, $i=1,\ldots ,k$. By definition (on $V_{k}$)

$$z_1 = \frac{q^{k-1}}{q^{-1}-1} (d_+^* d_- - d_- d_+^*) T_{k-1}^{-1} \cdots T_1^{-1},$$

thus (again, on $V_k$)

$$z_1 d_+ = \frac{q^{k}}{q^{-1}-1} (d_+^* d_- - d_- d_+^*) T_{k}^{-1} \cdots T_1^{-1} d_+.$$

From this expression we see, using 6.4 once again, that $z_1 d_+$ satisfies the same two properties as the operator $y_1 d_+^*$,

$$z_1 d_+ y_i = y_{i+1} z_1 d_+,\qquad z_1 d_+ (F\ast G) = F \ast _1 z_1 d_+(G)$$

for $F\in \operatorname {Sym}[X]$, $G\in V_k$, $i=1,\ldots ,k$. Thus it is enough to verify the first identity on $1\in V_k$. The right-hand side is $-t q^{k+1} y_1$. The left-hand side is

$$\frac{q^k}{q^{-1}-1}(d_+^*-1)d_-(1) = \frac{q^k}{q^{-1}-1}(X+t (q-1)y_1-X) = -t q^{k+1} y_1,$$

so the first identity holds.

It is enough to verify the second identity for $i=1$ because the general case can be deduced from this one by applying the $T$-operators. For the identity $z_2 d_+ = d_+ z_1$, expressing $z_1$, $z_2$ in terms of $d_-$, $d_+^*$ and the $T$-operators, we arrive at the equivalent identity

$$T_1^{-1} d_+(d_+^* d_- - d_- d_+^*) = (d_+^* d_- - d_- d_+^*) d_+.$$

If we denote by $A$ either of the two sides, we have

$$A (F\ast G) = F\ast _1 A(G),\qquad A y_i = T_2 T_3\cdots T_{i+1} y_{i+1} (T_2 T_3 \cdots T_{i+1})^{-1} A$$

for $F\in \operatorname {Sym}[X]$, $G\in V_k$, $i=1,\ldots ,k-1$. Thus it is enough to verify the identity on $y_k^a\in V_k$ ($a\in \mathbb{Z}_{\geq 0}$). Applying $T_k^{-1} T_{k-1}^{-1} \cdots T_2^{-1}$ to both sides, the identity to be verified is

$$T_k^{-1} T_{k-1}^{-1} \cdots T_1^{-1} d_+ (d_+^* d_- - d_- d_+^*)(y_k^a) = (d_+^* d_- - d_- d_+^*) T_{k-1}^{-1} \cdots T_1^{-1} d_+(y_k^a).$$

The left-hand side is evaluated to

$$-h_{a+1}[-X-t(q-1)y_1-(q-1)y_{k+1}] + h_{a+1}[-X-(q-1)y_{k+1}].$$

The right-hand side is evaluated to

$$(d_+^* d_- - d_- d_+^*) T_k(y_{k+1}^a) = F[X+t(q-1)y_1] - F[X]$$

with

$$\begin{equation*} \begin{split} F[X] &= -h_{a+1}[-X] - (1-q)\sum _{i=0}^{a-1} y_{k+1}^{a-i} h_{i+1}[-X]\\ &= -h_{a+1}[-X+(1-q)y_{k+1}] + (1-q)y_{k+1}^{a+1}, \end{split} \end{equation*}$$

and the identity follows.

■

This completes our proof of Theorem 6.1.

We also have the following proposition, which we will use to connect the conjugate action with $N_{\alpha }$.

Proposition 6.6.

For a composition $\alpha$ of length $k,$ let

$$y_\alpha = y_1^{\alpha _1-1}\cdots y_k^{\alpha _k-1} \in V_k.$$

Then the following recursions hold:

$$y_{1\alpha } = d_+^* y_\alpha ,\quad y_{a \alpha } = \frac{t^{1-a}}{q-1}(d_+^* d_- - d_- d_+^*) \sum _{\beta \models a-1} q^{1-l(\beta )} d_-^{l(\beta )-1}(y_{\alpha \beta })\quad (a>1).$$

Proof.

The first identity easily follows from the explicit formula for $d_+^*$. For $i=1,2,\ldots ,k-1$, we have

$$(d_- d_+^* - d_+^* d_-) y_i = y_{i+1} (d_- d_+^* - d_+^* d_-).$$

Therefore it is enough to verify the following identity for any $a\in \mathbb{Z}_{\geq 1}$:

$$\begin{equation} (q-1) t^a y_1^a = (d_+^* d_- - d_- d_+^*) \sum _{\beta \models a} q^{1-l(\beta )} d_-^{l(\beta )-1}(y_k^{\beta _1-1} \cdots y_{k+l(\beta )-1}^{\beta _{l(\beta )}-1}) \in V_k. {\tag{6.6}} \end{equation}$$

We group the terms on the right-hand side by $b=\beta _1-1,$ and the sum becomes

$$\begin{align*} & \sum _{b=0}^{a-1} y_k^b \sum _{\beta \models a-b-1} q^{-l(\beta )} d_-^{l(\beta )}\left(y_{k+1}^{\beta _1-1}\cdots y_{k+l(\beta )}^{\beta _{l(\beta )}-1}\right) \\ &\qquad =\sum _{b=0}^{a-1} y_k^b \sum _{\beta \models a-b-1} q^{-l(\beta )} (-1)^{l(\beta )} B_{\beta _1} \cdots B_{\beta _{l(\beta )}}(1) =\sum _{b=0}^{a-1} y_k^b h_{a-b-1}[q^{-1}X]. \end{align*}$$

We have used the identity

$$\begin{equation} h_n[q^{-1}X] = \sum _{\alpha \models n} q^{-l(\alpha )} (-1)^{l(\alpha )} B_\alpha (1), {\tag{6.7}} \end{equation}$$

which can be obtained by applying $\bar{\omega }$ to Proposition 5.2 of HMZ12:

$$h_n[-X] = \sum _{\alpha \models n} C_\alpha (1).$$

Thus the right-hand side of (6.6) is evaluated to the expression

$$\begin{align*} &(d_+^* d_- - d_- d_+^*) \sum _{b=0}^{a-1} y_k^b q^{-(a-b-1)} h_{a-b-1}[X]\\ &\quad = -\sum _{b=0}^{a-1}\left(\Gamma _{+}(t(q-1)y_1) B_{b+1} - B_{b+1} \Gamma _{+}(t(q-1)y_1)\right) h_{a-b-1}[q^{-1} X].\\ &\quad = - \sum _{b=0}^{a-1} \Gamma _+(-t y_1) \left((B_{b+1} - qt y_1 B_{b}) - (B_{b+1} - t y_1 B_{b})\right) (h_{a-b-1}[q^{-1}X + ty_1])\\ &\quad = (q-1) t y_1 \Gamma _+(-t y_1) \sum _{b=0}^{a-1} B_{b} ( h_{a-b-1}[q^{-1}X+t y_1]). \end{align*}$$

Thus we need to prove

$$\sum _{b=0}^{a-1} B_b (h_{a-b-1}[q^{-1} X+ty_1]) = t^{a-1} y_1^{a-1}.$$

Then the left-hand side as a polynomial in $y_1$ indeed has the right coefficient of $y_1^{a-1}$. The coefficient of $y_1^i$ for $i<a-1$ is

$$t^i \sum _{b=0}^{a-1-i} B_b(h_{a-b-1-i}[q^{-1} X]).$$

So it is enough to show

$$\sum _{b=0}^m B_b(h_{m-b}[q^{-1}X]) = 0 \quad (m\in \mathbb{Z}_{>0}).$$

Using (6.7) again, we see that the left-hand side equals

$$B_0(h_m[q^{-1}X]) - q h_m[q^{-1}X] = (B_0-q)(-q^{-1} C_m(1)) = 0$$

because $B_0 C_m = q C_m B_0$ by HMZ12, Proposition 3.5 and $B_0(1)=1$.

■

7. The involution

Definition 7.1.

Consider $\mathbb{A}$ and $\mathbb{A}^*$ as algebras over $\mathbb{Q}(q,t)$, and let $\tilde{\mathbb{A}}=\tilde{\mathbb{A}}_{q,t}$ be the quotient of the free product of $\mathbb{A}$ and $\mathbb{A}^*$ by the relations

$$\begin{equation*} d_-^* = d_-,\quad T_i^*=T_i^{-1},\quad e_i^*=e_i, \end{equation*}$$

$$\begin{equation*} z_{i+1} d_+ = d_+ z_i,\quad y_{i+1} d_+^* = d_+^* y_i,\quad z_1 d_+ = -y_1 d_+^* t q^{k+1}. \end{equation*}$$

Remark 7.2.

For any $k\geq 0,$ the affine Hecke algebra $\mathrm{AHA}_k$ is the algebra generated over $\mathbb{Q}(q)$ by $T_1,\ldots ,T_{k-1}, y_1^{\pm 1}, \ldots , y_k^{\pm 1}$ modulo relations

$$\begin{equation*} (T_i-1)(T_i+q)=0,\quad T_i T_{i+1} T_i = T_{i+1} T_i T_{i+1}, \quad T_i T_j = T_j T_i\quad (|i-j|>1), \end{equation*}$$

$$\begin{equation*} y_i T_j = T_j y_i\quad (i\notin \{j,j+1\}), \quad y_i y_j = y_j y_i, \quad T_i y_{i+1} T_i = q y_i. \end{equation*}$$ The positive part $\mathrm{AHA}_k^+$ is defined as the subalgebra of $\mathrm{AHA}_k$ generated by $T_i$ and $y_i$, or equivalently as the algebra generated over $\mathbb{Q}(q)$ by $T_1,\ldots ,T_{k-1}, y_1, \ldots , y_k$ modulo the same relations. We have a natural homomorphism $\mathrm{AHA}_k^+\to e_k\mathbb{A}e_k$ which can be shown to be injective using Lemma 5.6. It is tempting to guess that in a similar way the subalgebra of $e_k\tilde{\mathbb{A}}e_k$ generated by $T_i$, $y_i$, and $z_i$ is isomorphic to the positive part $\mathrm{DAHA}_k^{++}$ of the double affine Hecke algebra $\mathrm{DAHA}_k$. To fix a version of $\mathrm{DAHA}_k^{++}$ which is close to our notations, we start with relations SV11, (2.1)–(2.7) and perform substitutions $q=t^{-1}$, $v=q^{\frac{1}{2}}$, $T_i=q^{\frac{1}{2}} T_i^{-1}$, $X_i=y_i$, $Y_i=z_i$ followed by reversal of the order of generators in each monomial. So $\mathrm{DAHA}_k^{++}$ is defined over $\mathbb{Q}(q,t)$ by generators $T_1,\ldots ,T_{k-1}, y_1, \ldots , y_k, z_1, \ldots , z_k$ and relations of two copies of $\mathrm{AHA}_k$ (the second copy is transformed by $T_i\to T_i^{-1}$, $q\to q^{-1}$)

$$\begin{equation*} (T_i-1)(T_i+q)=0,\quad T_i T_{i+1} T_i = T_{i+1} T_i T_{i+1}, \quad T_i T_j = T_j T_i\quad (|i-j|>1), \end{equation*}$$

$$\begin{equation*} y_i T_j = T_j y_i\quad (i\notin \{j,j+1\}), \quad y_i y_j = y_j y_i, \quad T_i y_{i+1} T_i = q y_i, \end{equation*}$$

$$\begin{equation*} z_i T_j = T_j z_i\quad (i\notin \{j,j+1\}), \quad z_i z_j = z_j z_i, \quad T_i z_{i} T_i = q z_{i+1}, \end{equation*}$$

and two extra relations. The first one is

$$\begin{equation*} z_2 y_1 = q y_1 T_1^{-2} z_2\quad \Leftrightarrow \quad q y_2 z_1 = z_1 T_1^2 y_2, \end{equation*}$$

which can be deduced in $\tilde{A}$ from 5.4 and $z_2 d_+ = d_+ z_1$. The second relation is

$$\begin{equation*} z_1 y_1 \cdots y_k = t y_1 \cdots y_k z_1. \end{equation*}$$

The following identity can be deduced from the rest of the relations:

$$\begin{equation*} y_2 \cdots y_k z_1 = q^{1-k} z_1 T_1 \cdots T_{k-1} T_{k-1} \cdots T_1 y_2\cdots y_k. \end{equation*}$$

Thus we expect to have

$$\begin{equation*} z_1 y_1 = q^{1-k}\, t\, y_1 z_1 T_1 \cdots T_{k-1} T_{k-1} \cdots T_1. \end{equation*}$$

However this does not hold in $\tilde{A}$. Instead we have

$$\begin{equation*} z_1 y_1 = q^{1-k}\, t\, y_1 z_1 T_1 \cdots T_{k-1} T_{k-1} \cdots T_1 \;+\; q t y_1 d_- d_+^* T_{k-1} \cdots T_1. \end{equation*}$$

So we see that we do not obtain a natural homomorphism $\mathrm{DAHA}_k^{++}\to e_k \tilde{\mathbb{A}}e_k$. One way to repair the situation is to introduce the “partially symmetrized” $\mathrm{SDAHA}_{k,\infty }^{++}$ by starting with the DAHA in infinitely many generators $T_i$, $z_i$, $y_i$ ($i=1,2,3,\ldots$), and then symmetrizing in generators with $i>k$. For instance for $k=0,$ we expect $e_0 \tilde{\mathbb{A}}e_0$ to coincide with the positive part of the elliptic Hall algebra, which is the stable limit of spherical DAHAs as shown in SV11. Details of this construction will be provided in a future publication.

We now prove

Theorem 7.3.

The operations $T_i$, $d_-$, $d_+$, $d_+^*$, $e_i$ define an action of $\tilde{\mathbb{A}}$ on $V_*$. Furthermore, the kernel of the natural map $\tilde{\mathbb{A}} e_0 \rightarrow V_*$ that sends $f e_0$ to $f(1)$ is given by $I e_0$ where $I \subset \tilde{\mathbb{A}}$ is the ideal generated by

$$\begin{equation} I=\langle d_+^* d_+^m-d_+^{m+1}|\quad m \geq 0\rangle . {\tag{7.1}} \end{equation}$$

In particular, we have an isomorphism $V_* \cong \tilde{\mathbb{A}} e_0/Ie_0$.

Proof.

Theorem 6.1 shows that we have a map of modules $\tilde{\mathbb{A}} e_0 \rightarrow V_*$ that restricts to the isomorphism of Theorem 5.2 on the subspace $\mathbb{A}e_0$, so in particular is surjective. Furthermore, the last relation of 6.3 shows that it descends to a map $\tilde{\mathbb{A}} e_0/Ie_0 \mapsto V_*$, which must still be surjective. We have the following commutative diagram.

$$\begin{equation*} \vcenter{\img[][73pt][46pt][{\renewcommand{\arraystretch}{1} \setlength{\unitlength}{1.0pt} \begin{tikzcd} \tilde{\AA} e_0/Ie_0 \arrow{r} &amp; V_*\\ \AA e_0 \arrow{u} \arrow{ur}{\sim} &amp; \end{tikzcd}}]{Images/img0a297d3f1694d2e053c58b829bb4b2a3.svg}} \end{equation*}$$

Thus we have an inclusion $\mathbb{A}e_0 \subset \tilde{\mathbb{A}}e_0/Ie_0$ and it remains to show that the image of $\mathbb{A}e_0$ in $\tilde{\mathbb{A}}e_0/Ie_0$ is the entire space. We do so by induction: notice that both $\mathbb{A}e_0$ and $\tilde{\mathbb{A}}e_0/Ie_0$ have a grading by the total degree in $d_+$, $d_+^*$, and $d_-$, as all the relations are homogeneous. For instance, $y_i$ and $z_i$ have degree $2$, and $T_i$ has degree $0$ for all $i$. Denote the space of elements of degree $m$ in $\mathbb{A}e_0$, $\tilde{\mathbb{A}}e_0/Ie_0$ by $V^{(m)}$, $W^{(m)},$ respectively. We need to prove $V^{(m)}=W^{(m)}$. The base cases $m=0$, $m=1$ are clear.

For the induction step, suppose $m>0$, $V^{(i)}=W^{(i)}$ for $i\leq m,$ and let $F\in V^{(m)}$. It is enough to show that $d_+^* F \in V^{(m+1)}$. By Lemma 5.6, we can assume that $F$ is in the canonical form 5.6. We therefore must check three cases: $F=d_+^m (1)$ for $1\in V_0$, $F=y_i G$ for $G\in V^{(m-2)}$, and $F=d_- (G)$ for $G\in V^{(m-1)}$. In the first case we have $d_+^* F = d_+^{m+1} 1$. In the second case we have $d_+^* (F) = y_{i+1} d_+^* (G)$. In the third case we have

$$\begin{equation*} d_+^* F = d_+^* d_- G = d_- d_+^* G + (q^{-1} - 1) T_1^{-1}\cdots T_{k-1}^{-1} z_k G. \end{equation*}$$

Now we use expansion of $G$ in terms of the generators $T_i$, $d_+$, and $d_-$. Because of the commutation relations between $T_i$ and $z_j,$ it is enough to consider two cases, $G=d_+ G'$ and $G=d_- G'$ for $G'\in V^{(m-2)}$. In the first case we have $z_k G = d_+ z_{k-1} G'$ if $k>1$ and $z_1 G = -y_1 d_+^* t G'$ if $k=1$. In the second case we have $z_k G = d_- z_k G'$. In all cases the claim is reduced to the induction hypothesis.

■

Now by looking at the defining relations of $\tilde{\mathbb{A}}$, we make the remarkable observation that there exists an involution $\iota$ of $\tilde{\mathbb{A}}$ that permutes $\mathbb{A}$ and $\mathbb{A}^*$ and is antilinear with respect to the conjugation $(q,t)\mapsto (q^{-1},t^{-1})$ on the ground field $\mathbb{Q}(q,t)$! Furthermore, this involution preserves the ideal $I$, and therefore induces an involution on $V_*$ via the isomorphism of Theorem 7.3.

Theorem 7.4.

There exists a unique antilinear degree-preserving automorphism $\mathcal{N} : V_* \rightarrow V_*$ satisfying

$$\begin{equation*} \mathcal{N}(1)=1,\quad \mathcal{N} T_i = T_i^{-1} \mathcal{N}, \quad \mathcal{N} d_- = d_- \mathcal{N},\quad \mathcal{N} d_+ = d_+^* \mathcal{N}, \quad \mathcal{N} y_i = z_i \mathcal{N}. \end{equation*}$$

Moreover, we have

(i)

$\mathcal{N}$ is an involution, i.e., $\mathcal{N}^2=\operatorname {Id}$.

(ii)

For any composition $\alpha$ we have$$\mathcal{N}(y_\alpha ) = q^{\sum (\alpha _i-1)} N_\alpha .$$

(iii)

On $V_0=\operatorname {Sym}[X]$, we have $\mathcal{N} = \nabla \bar{\omega }$, where $\bar{\omega }$ is the involution sending $q$, $t$, $X$ to $q^{-1}$, $t^{-1}$, $-X$, respectively (see 6.1).

Proof.

The automorphism is induced from the involution of $\tilde{\mathbb{A}}$, from which part (i) follows immediately. Part (ii) follows from applying $\mathcal{N}$ to the relations of Proposition 6.6.

Finally, let $D_1, D_1^*: V_0\to V_0$ be the operators

$$\begin{equation*} (D_1 F)[X] = F[X+(1-q)(1-t) u^{-1}] \operatorname {Exp}[-uX] |_{u^1}, \end{equation*}$$

$$\begin{equation*} (D_1^* F)[X] = F[X-(1-q^{-1})(1-t^{-1}) u^{-1}] \operatorname {Exp}[uX] |_{u^1}, \end{equation*}$$ and let $\underline{e}_1: V_0\to V_0$ be the operator of multiplication by $e_1[X]=X$. It is easy to verify that

$$\begin{equation*} D_1 = -d_- d_+^*,\quad \underline{e}_1 = d_- d_+,\quad \bar{\omega }D_1 = D_1^*\bar{\omega }. \end{equation*}$$

Thus it follows that

$$\begin{equation*} \mathcal{N} D_1 = -\underline{e}_1 \mathcal{N},\quad \mathcal{N} \underline{e}_1 = -D_1 \mathcal{N}. \end{equation*}$$

Let $\nabla '=\mathcal{N}\bar{\omega }$ on $V_0$. Then

$$\begin{equation*} \nabla '(1) = 1,\quad \nabla ' \underline{e}_1 = D_1 \nabla ',\quad \nabla ' D_1^* = -\underline{e}_1 \nabla '. \end{equation*}$$

It was shown in GHT99 that $\nabla$ satisfies the same commutation relations, and that one can obtain all symmetric functions starting from $1$ and successively applying $\underline{e}_1$ and $D_1^*$. Thus $\nabla =\nabla '$, proving part (iii).

■

The compositional shuffle conjecture now follows easily:

Theorem 7.5.

For a composition $\alpha$ of length $k$, we have

$$\begin{equation*} \nabla C_{\alpha _1}\cdots C_{\alpha _k}(1)= D_{\alpha }(X;q,t). \end{equation*}$$

Proof.

Using Theorems 4.11 and 7.4, we have

$$\begin{align*} D_{\alpha }(q,t)&=d_-^{k} (N_\alpha ) = d_-^k(\mathcal{N}(q^{|\alpha |-k} y_\alpha ))=\mathcal{N}(q^{|\alpha |-k} d_-^k(y_\alpha ))\\ &=\mathcal{N}\left(q^{|\alpha |-k} (-1)^{k} B_{\alpha }(1)\right) = \mathcal{N}\bar{\omega }C_{\alpha }(1)=\nabla C_{\alpha }(1). \end{align*}$$■

Figure 1.

Example of a Dyck path of size 8.

Figure 2.

Image of the path from Figure 1 under the $(\operatorname {area},\operatorname {dinv})$ to $(\operatorname {bounce},\operatorname {area}')$ bijection.

Figure 3.

The bounce path of the path in Figure 2.

Figure 4.

Figure 5.