The shuffle conjecture

Abstract

Walks in the plane taking unit-length steps north and east from $(0,0)$ to $(n,n)$ never dropping below $y=x$ and parking cars subject to preferences are two intriguing ingredients in a formula conjectured in 2005, now famously known as the shuffle conjecture.

Here we describe the combinatorial tools needed to state the conjecture. We also give key parts and people in its history, including its eventual algebraic solution by Carlsson and Mellit, which was published in the Journal of the American Mathematical Society in 2018. Finally, we conclude with some remaining open problems.

They can see the topography…the treetops, but we can see the parakeets.

Adriano Garsia

Often, in order to delve deep into the structure of an abstract mathematical construct (the treetops), we need to interpret it concretely with a combinatorial visualization (the parakeets). The shuffle conjecture, as we will see, is one such story. In this article we will integrate the motivation, history, and mathematics of the shuffle conjecture as we proceed. Hence, we will begin by recalling necessary concepts from combinatorics in Section 1 and from algebra in Section 2 in order to state the shuffle conjecture in Theorem 3.3. This recently proved conjecture is, in essence, a formula for encoding the graded dimensions of the symmetric group representation in the character of a particular vector space on which the symmetric group $\mathfrak{S}_n$ acts. In Section 3 we also discuss some of the motivation and history of the shuffle conjecture, including its refinement known as the compositional shuffle conjecture whose algebraic resolution by Carlsson and Mellit, announced in 2015 5 and published in 2018 6, excited the combinatorial community. We mention some of their proof ingredients in Section 4, where we also conclude with some future avenues.

1. The combinatorics of Dyck paths and parking functions

A crucial concept for the statement of the shuffle conjecture is that of parking functions. Although originally studied by Pyke 27, they were introduced as a model for parking $n$ cars subject to preferences by Konheim and Weiss who were studying data storage 23, Section 6: A parking problem—the case of the capricious wives. Konheim and Weiss also proved that the number of parking functions involving $n$ cars is $(n+1)^{(n-1)}$. Since then these functions have arisen in a plethora of places from hyperplane arrangements 33 to chip-firing 8. More details on parking functions can be found, for example, in the survey by Yan 36. Rather than using the original definition, given in terms of drivers parking cars, we will instead use an equivalent definition introduced by Garsia, for example in his paper with Haiman 11, p. 227. However, before we do this, we need to define a Dyck path.

Definition 1.1 (Dyck path).

A Dyck path of order $n$ is a path in the $n \times n$ lattice from $(0,0)$ to $(n,n)$ that consists of $n$ unit-length north steps and $n$ unit-length east steps, which stays weakly above the line $y=x$.

Example 1.2.

If we let $N$ denote a unit-length north step and $E$ denote a unit-length east step, then the following path $NNNEEENNENEENNEE$ from $(0,0)$ in the bottom-left corner to $(8,8)$ in the top-right corner is a Dyck path of order 8.

$$\begin{equation*} \vcenter{\img[][162pt][162pt][{\renewcommand{\arraystretch}{1} \setlength{\unitlength}{1.0pt} \begin{tikzpicture}[scale=0.7, every node/.style={font=\Large}] \useasboundingbox(-1,0) rectangle (8, 8); \draw[line width=0.5pt, color=gray] (0, 0) grid (8, 8); \draw[line width=0.5pt, dashed, color=gray] (0, 0) -- (8, 8); \draw[rounded corners=4, color=black, line width=4pt] (0, 0) -- (0, 1) -- (0, 2) -- (0, 3) -- (1, 3) -- (2, 3) -- (3, 3) -- (3, 4) -- (3, 5) -- (4, 5) -- (4, 6) -- (5, 6) -- (6, 6) -- (6, 7) -- (6, 8) -- (7, 8) -- (8, 8); \end{tikzpicture}}]{Images/img861d8d87b019f8c736b9796c668ae382.svg}} \end{equation*}$$

Definition 1.3 (Parking function).

A parking function of order $n$ is a Dyck path of order $n$ such that each north step has a label, called a car, written in the square to its immediate right. The cars are $1$, $2$, …, $n$, each occurring exactly once, and cars in the same column increase from bottom to top. We denote the set of all parking functions of order $n$ by $PF _n$.

Example 1.4.

An example of a parking function, which we will use throughout this article, is given in Figure 1.

We now define three statistics on parking functions that will be useful later, the first of which is the area of a parking function, and it depends only on its Dyck path.

Definition 1.5 (Area).

If $\pi$ is a parking function, then its area is the number of complete squares between the Dyck path of $\pi$ and $y=x$, denoted by $\operatorname {area}(\pi )$.

Example 1.6.

If $\pi$ is the parking function from Figure 1, then by counting the number of complete squares in each row contributing to the area, from bottom to top, we get

$$\begin{equation*} \operatorname {area}(\pi ) = 0+1+2+0+1+1+0+1 = 6. \end{equation*}$$

The second statistic is slightly more intricate than the area.

Definition 1.7 (Dinv).

Consider a parking function $\pi$ and a pair of cars $\{c_1, c_2\}$ in it.

•

If the cars $c_1, c_2$ are in the same diagonal (that is, their squares are the same distance from $y=x$) with the larger car occurring farther right, then $\{c_1, c_2\}$ is a primary diagonal inversion. Let $\operatorname {Dinv}^{pri}(\pi )$ be the set of all such pairs.

•

If the cars $c_1, c_2$ are in adjacent diagonals with the larger car occurring in the higher diagonal (that is, its square is distance 1 farther from $y=x$ than that of the smaller car) and farther left, then $\{c_1, c_2\}$ is a secondary diagonal inversion. Let $\operatorname {Dinv}^{sec}(\pi )$ be the set of all such pairs.

Then

$$\begin{equation*} \operatorname {dinv}(\pi ) = | \operatorname {Dinv}^{pri}(\pi ) | + | \operatorname {Dinv}^{sec}(\pi ) |. \end{equation*}$$

Example 1.8.

If $\pi$ is from Figure 1, then $\{3,7\}$ is a primary diagonal inversion, but $\{5,7\}$ is not since the smaller car 5 occurs farther right. Likewise $\{5,8\}$ is a secondary diagonal inversion, but $\{3,4\}$ is not, since the smaller car 3 occurs in the higher diagonal and farther left. Note that $\{4,8\}$ is neither type of diagonal inversion since the cars are not in the same or adjacent diagonals.

Hence,

$$\begin{equation*} \operatorname {Dinv}^{pri}(\pi ) = \{\{2,4\}, \{3,6\}, \{3,7\}, \{3,5\}, \{6,7\}\}, \end{equation*}$$

$$\begin{equation*} \operatorname {Dinv}^{sec}(\pi ) = \{\{1,3\}, \{1,6\}, \{1,7\}, \{6,8\}, \{7,8\}, \{5,8\}\} \end{equation*}$$ so

$$\begin{equation*} \operatorname {dinv}(\pi ) = | \operatorname {Dinv}^{pri}(\pi ) | + | \operatorname {Dinv}^{sec}(\pi ) | = 5+6 = 11. \end{equation*}$$

Our third statistic is a permutation associated to a parking function.

Definition 1.9 (Word).

If $\pi$ is a parking function, then its word is the permutation in one-line notation obtained by reading cars from the diagonal farthest from $y=x$ to the diagonal $y=x$, and within a diagonal reading from right to left. We denote this by $\operatorname {word}(\pi )$.

Example 1.10.

If $\pi$ is from Figure 1, then

$$\begin{equation*} \operatorname {word}(\pi ) = 85763142. \end{equation*}$$

With our three statistics now defined, we end this section by recalling the $i$-descent set of a permutation, in our case specialized to the word of a parking function.

Definition 1.11 (Ides).

If $\pi$ is a parking function, then its $i$-descent set is

$$\begin{equation*} \operatorname {ides}(\pi ) = \{ i \;|\;i+1 \text{ is left of $i$ in $\operatorname {word}(\pi )$}\}. \end{equation*}$$

Example 1.12.

If $\pi$ is from Figure 1 with $\operatorname {word}(\pi ) = 85763142$ from Example 1.10, then

$$\begin{equation*} \operatorname {ides}(\pi ) = \{2,4,6,7\}. \end{equation*}$$

2. The algebras of quasisymmetric and symmetric functions

We now start to turn our attention to the algebraic ingredients needed to state the shuffle conjecture after first recalling the notions of compositions and partitions.

A composition $\alpha$ of $n$, denoted by $\alpha \vDash n$, is a list of positive integers $\alpha = \alpha _1\alpha _2 \cdots \alpha _{\ell (\alpha )}$ such that $\sum _{i=1} ^{\ell (\alpha )} \alpha _i = n$. We call the $\alpha _i$ the parts of $\alpha$, call $n$ the size of $\alpha$, and call $\ell (\alpha )$ the length of $\alpha$. If, furthermore, $\alpha _1\geq \alpha _2\geq \cdots \geq \alpha _{\ell (\alpha )}$, then we say that $\alpha$ is a partition of $n$ and denote this by $\alpha \vdash n$. For example, $332$ is both a composition and partition, with size 8 and length 3.

Now we focus on defining the algebra of quasisymmetric functions, before using them to define the algebra of symmetric functions.

The algebra of quasisymmetric functions, $\operatorname {QSym}$, is a subalgebra of $\mathbb{C}[[z_1, z_2, \ldots ]]$, meaning that $\operatorname {QSym}$ is a vector space, over $\mathbb{C}$, of formal power series in the variables $z_1$, $z_2$, …, in which we can also multiply the elements together. A basis for $\operatorname {QSym}$ is given by the set of all fundamental quasisymmetric functions that we now define in the variables $Z=\{z_1, z_2, \ldots \}$, indexed by $n$ and subsets of $[n-1] = \{1,2, \ldots ,n-1\}$.

Definition 2.1 (Fundamental quasisymmetric function).

Let

$$\begin{equation*} S=\{ s_1, s_2, \ldots , s_{|S|}\}\subseteq [n-1]. \end{equation*}$$

Then the fundamental quasisymmetric function $F_{n,S}$ is defined to be

$$\begin{equation*} F_{n,S} = \sum z_{i_1}z_{i_2}\cdots z_{i_n}, \end{equation*}$$

where the sum is over all $n$-tuples $(i_1, i_2, \ldots , i_n)$ satisfying

$$\begin{equation*} i_1\leq i_2 \leq \cdots \leq i_n \text{ and } i_j<i_{j+1} \text{ if } j\in S. \end{equation*}$$

Example 2.2.

We have that

$$\begin{equation*} F_{3, \{1\}} = z_1z_2^2+z_1z_3^2+ z_2z_3^2+\cdots +z_1z_2z_3+z_1z_2z_4+\cdots , \end{equation*}$$

whereas

$$\begin{equation*} F_{3, \{2\}} = z_1^2z_2+z_1^2z_3+z_2^2z_3+\cdots +z_1z_2z_3+z_1z_2z_4+\cdots . \end{equation*}$$

In 1972 quasisymmetric functions were first mentioned implicitly with regard to $P$-partitions in Stanley’s thesis 32, and then Gessel developed and published much of the classical theory explicitly in 1984 12. Since then they have arisen in a variety of areas, for example, from probability 20 to category theory 1. However, our interest lies in a special case of a result from Gessel’s original paper 12, Theorem 3. For this we first need to define Young diagrams and Young tableaux.

Given a partition $\lambda = \lambda _1\lambda _2 \cdots \lambda _{\ell (\lambda )}\vdash n$, we define its Young diagram, also denoted by $\lambda$, to be the array of left-justified boxes with $\lambda _i$ boxes in row $i$ from the top. Given the Young diagram, $\lambda$, a standard Young tableau (SYT) of shape $\lambda$, $T$, is a filling of the $n$ boxes of $\lambda$ with $1$, $2$, …, $n$, each appearing exactly once such that the entries in the rows increase when read from left to right, and the entries in each column increase when read from top to bottom. We denote the set of all SYTs of shape $\lambda$ by $SYT(\lambda )$.

Example 2.3.

We have that $T = \vcenter{\img[][63pt][47pt][{\renewcommand{\arraystretch}{1} \setlength{\unitlength}{1.0pt} \begin{ytableau}1&3&4&5\\2&6&8\\7\end{ytableau}}]{Images/imgf55a068be6c3b9f6525f21e547bf9107.svg}}$ is an SYT of shape $431\vdash 8$.

Given an SYT, $T$, of shape $\lambda \vdash n$, we define its descent set to be

$$\begin{equation*} \operatorname {Des}(T) = \{ i \;|\;i+1 \text{ is in the same column or left of } i\} \subseteq [n-1]. \end{equation*}$$

Example 2.4.

If $T$ is from Example 2.3, then

$$\begin{equation*} \operatorname {Des}(T) = \{1,5,6\} \subseteq [7]. \end{equation*}$$

We can now define the algebra of symmetric functions, $\operatorname {Sym}$, which is a subalgebra of $\operatorname {QSym}$. This algebra is so named because its elements are invariant under any permutation of its variables, and a basis for $\operatorname {Sym}$ is the set of all Schur functions that we now define as a special case of 12, Theorem 3.

Definition 2.5 (Schur function).

Let $\lambda \vdash n$. Then the Schur function $s_\lambda$ is defined to be

$$\begin{equation*} s_\lambda = \sum _{T\in SYT(\lambda )} F_{n, \operatorname {Des}(T)}. \end{equation*}$$

Example 2.6.

We have that $s_{21} = F_{3, \{1\}} + F_{3, \{2\}}$ from the SYTs below.

$$\begin{equation*} \vcenter{\img[][33pt][32pt][{\renewcommand{\arraystretch}{1} \setlength{\unitlength}{1.0pt} \begin{ytableau}1&3\\2\end{ytableau}}]{Images/img4a26a97d7f40a12e73f3295f7d882621.svg}}\qquad \vcenter{\img[][33pt][32pt][{\renewcommand{\arraystretch}{1} \setlength{\unitlength}{1.0pt} \begin{ytableau}1&2\\3\end{ytableau}}]{Images/img4b7b8a837c59db3c36a08ed9e14268f9.svg}} \end{equation*}$$

The Schur functions are not the only basis of $\operatorname {Sym}$. Another basis that will be vital to our story is the basis consisting of all elementary symmetric functions: We define the $i$th elementary symmetric function $e_i$ to be

$$\begin{equation*} e_i = s _{1^i}, \end{equation*}$$

where $1^i$ is the partition consisting of $i$ parts equal to 1. Then if $\lambda =\lambda _1\lambda _2\cdots \lambda _{\ell (\lambda )}\vdash n$, we define the elementary symmetric function $e_\lambda$ to be

$$\begin{equation*} e_\lambda = e_{\lambda _1}e_{\lambda _2}\cdots e_{\lambda _{\ell (\lambda )}}. \end{equation*}$$

Symmetric functions date back to Girard 13 in 1629, although Schur functions are much younger, dating to an 1815 paper by Cauchy 7. The Schur functions were named after Schur who proved in 1901 that they were characters of the irreducible polynomial representations of the general linear group 29, while standard Young tableaux were defined by Young in his 1928 publication 37, p. 258. Substantial historical notes on this subject can be found in Stanley’s second volume on enumerative combinatorics 34, Chapter 7, which is also an excellent resource for symmetric functions and some related representation theory, as is the book by Sagan 28.

3. The space of diagonal harmonics and the shuffle conjecture

With our essential combinatorial and algebraic notations now defined, we can begin to work towards our statement of the shuffle conjecture, which is about the vector space of diagonal harmonics. However, before we do that, let us define our desired space.

Definition 3.1 (Space of diagonal harmonics).

Let $X_n = \{x_1, x_2, \ldots ,x_n\}$ and $Y_n = \{y_1, y_2, \ldots ,y_n\}$. Then the space of diagonal harmonics, $DH_n$, is the vector space of polynomials in these variables, $f(X_n, Y_n)$, which satisfy

$$\begin{equation} \partial ^a _{x_1}\partial ^b _{y_1} f(X_n, Y_n) + \partial ^a _{x_2}\partial ^b _{y_2} f(X_n, Y_n) + \cdots + \partial ^a _{x_n}\partial ^b _{y_n} f(X_n, Y_n) = 0 {\tag{3.1}} \end{equation}$$

for all $a,b\geq 0$ and $a+b>0$. That is,

$$\begin{equation*} DH_n = \{ f(X_n, Y_n) \in \mathbb{C} [X_n, Y_n] \;|\;\sum _{i=1}^{n} \partial ^a _{x_i}\partial ^b _{y_i} f(X_n, Y_n) = 0, \forall a,b\geq 0, a+b>0\}. \end{equation*}$$

Example 3.2.

$DH_2$ consists of all polynomials $f(X_2, Y_2) = f(x_1, x_2, y_1, y_2)$ such that

$$\begin{equation*} \begin{array}{lcccll} a+b=1&\text{gives}&\partial _{x_1} f(X_2, Y_2) + \partial _{x_2} f(X_2, Y_2)=0&\text{when} &a=1&b=0\\&&\partial _{y_1} f(X_2, Y_2) + \partial _{y_2} f(X_2, Y_2)=0&&a=0&b=1\\a+b=2&\text{gives}&\partial _{x_1}^2 f(X_2, Y_2) + \partial _{x_2}^2 f(X_2, Y_2)=0&\text{when} &a=2&b=0\\&&\partial _{x_1}\partial _{y_1} f(X_2, Y_2) + \partial _{x_2}\partial _{y_2} f(X_2, Y_2)=0&&a=1&b=1\\&&\partial _{y_1}^2 f(X_2, Y_2) + \partial _{y_2}^2 f(X_2, Y_2)=0&&a=0&b=2, \end{array} \end{equation*}$$

etc., and we can check that the solution set has basis $\{1, x_1-x_2, y_1-y_2\}$.

The symmetric group, $\mathfrak{S}_n$, acts naturally on $DH_n$ by the diagonal action that permutes the $X_n$ and $Y_n$ variables simultaneously. Namely, given $\sigma \in \mathfrak{S}_n$ and $f(X_n, Y_n) = f(x_1, x_2,\ldots , x_n, y_1, y_2,\ldots , y_n)$, we have that

$$\begin{equation*} \sigma f(x_1, x_2, \ldots , x_n, y_1, y_2, \ldots , y_n) = f(x_{\sigma (1)}, x_{\sigma (2)}, \ldots , x_{\sigma (n)}, y_{\sigma (1)}, y_{\sigma (2)}, \ldots , y_{\sigma (n)}). \end{equation*}$$

By equation 3.1 we see that if $f(X_n, Y_n) \in DH_n$, then $\sigma f(X_n, Y_n) \in DH_n$. Furthermore, if we let $DH_n^{c,d}$ be the subspace of $DH_n$, whose elements have total degree $c$ in the variables $x_1$, $x_2$, …, $x_n$ and total degree $d$ in the variables $y_1$, $y_2$, …, $y_n$, then if $f(X_n, Y_n) \in DH_n ^{c,d}$, then $\sigma f(X_n, Y_n) \in DH_n ^{c,d}$. This enables us to define the bigraded Frobenius characteristic of $DH_n$ to be

$$\begin{equation} DH_n[Z;q,t] = \sum _{c,d\geq 0} t^cq^d \sum _{\lambda \vdash n} s_\lambda \operatorname {Mult}(\chi ^\lambda , \operatorname {Char}DH_n ^{c,d}), {\tag{3.2}} \end{equation}$$

where, as before, $s_\lambda$ is a Schur function in the variables $Z=\{z_1, z_2, \ldots \}$ and $\operatorname {Mult}(\chi ^\lambda , \operatorname {Char}DH_n ^{c,d})$ is the multiplicity of the irreducible character of $\mathfrak{S}_n$, $\chi ^\lambda$, in the character of $DH_n ^{c,d}$ under the diagonal action of $\mathfrak{S}_n$, $\operatorname {Char}DH_n ^{c,d}$.

3.1. The shuffle conjecture

The shuffle conjecture is a combinatorial formula for computing $DH_n[Z;q,t]$ in equation 3.2, but before we give it and do an example, we will briefly recount a skeletal history of what motivated it. More details on this fascinating story can be found in the excellent state-of-the-art survey article by Hicks 21 and in the illuminating texts by Bergeron 3 and Haglund 14.

In 1988 Kadell 22 looked for, and then Macdonald 26 found, a generalization of Schur functions, with additional parameters $q,t$, $P_\lambda [Z;q,t]$, where $\lambda \vdash n$. This generalization specialized to the Schur functions at $q=t$, and to other well-known functions such as the elementary symmetric functions and Hall–Littlewood functions, which were likewise recovered by setting $q$ and $t$ to various values. These functions were then transformed by Garsia and Haiman 11, p. 194, thus creating modified Macdonald polynomials $\widetilde{H} _\lambda [Z; q,t]$, which they hoped to prove were a positive linear combination of Schur functions. Proving this would imply the Macdonald positivity conjecture dating from Macdonald’s original work in 1988, which conjectured that Macdonald polynomials were a positive linear combination of Schur functions. In order to prove their conjecture, they defined vector spaces $\mathcal{H} _\lambda$ 10, now known as Garsia–Haiman modules, and conjectured that the bigraded Frobenius characteristic of $\mathcal{H} _\lambda$ was $\widetilde{H} _\lambda [Z; q,t]$. Moreover, they conjectured in 10, Conjecture 1 that irrespective of $\lambda$, we have

$$\begin{equation*} \dim (\mathcal{H} _\lambda ) = n !. \end{equation*}$$

This conjecture became known as the $n!$ conjecture, and both it and the Macdonald positivity conjecture were eventually proved by Haiman 18, Theorem 3.2.

At the same time, Garsia and Haiman were studying $DH_n$, which contains all the $\mathcal{H} _\lambda$ for $\lambda \vdash n$ as subspaces, and they conjectured a formula for $DH_n[Z;q,t]$ in terms of the $\widetilde{H} _\lambda [Z; q,t]$. Bergeron and Garsia noted that this formula was almost identical to the formula for the elementary symmetric functions $e_n$ in terms of $\widetilde{H} _\lambda [Z; q,t]$. More precisely, if the coefficient of $\widetilde{H} _\lambda [Z; q,t]$ in $e_n$ was $\mathscr{C}_\lambda$, then its conjectured coefficient in $DH_n[Z;q,t]$ was

$$\begin{equation*} t^{n(\lambda )}q^{n(\lambda ')}\mathscr{C}_\lambda , \end{equation*}$$

where if $\lambda = \lambda _1 \lambda _2 \cdots \lambda _{\ell (\lambda )}$, then $n(\lambda ) =\sum _{i=1} ^{\ell (\lambda )}\lambda _i(i-1)$ and $\lambda ' = \lambda ' _1 \lambda ' _2 \cdots \lambda ' _{\ell (\lambda ')}$ is the transpose of $\lambda$, which is the partition created from $\lambda$ by setting

$$\begin{equation*} \lambda ' _i = \text{ number of parts of } \lambda \text{ that are }\geq i. \end{equation*}$$

For example, if $\lambda = 211$, then $\lambda ' = 31$. This inspired Bergeron and Garsia to officially define the nabla operator in the paper 4, Equation (4.11) as

$$\begin{equation*} \nabla \widetilde{H} _\lambda [Z; q,t] = t^{n(\lambda )}q^{n(\lambda ')} \widetilde{H} _\lambda [Z; q,t]. \end{equation*}$$

Hence, when Haiman, using algebraic geometry, proved the conjectured formula for $DH_n[Z;q,t]$ 19, Theorem 3.2, this automatically yielded that 19, Proposition 3.5

$$\begin{equation} DH_n[Z;q,t] = \nabla e_n, {\tag{3.3}} \end{equation}$$

since from above

$$\begin{equation*} e_n = \sum _{\lambda \vdash n} \mathscr{C}_\lambda \widetilde{H} _\lambda [Z; q,t], \end{equation*}$$

and now it was proved that

$$\begin{equation*} DH_n[Z;q,t] = \sum _{\lambda \vdash n} t^{n(\lambda )}q^{n(\lambda ')}\mathscr{C}_\lambda \widetilde{H} _\lambda [Z; q,t]. \end{equation*}$$

Haiman had also proved 19, Proposition 3.6 that

$$\begin{equation*} \dim (DH_n) = (n+1) ^{(n-1)}. \end{equation*}$$

This supported the search for a collection of $(n+1) ^{(n-1)}$ objects, such as all parking functions of order $n$, along with statistics on them, in order to find a formula to compute $\nabla e_n$ more easily. The shuffle conjecture of Haglund, Haiman, Loehr, Remmel, and Ulyanov 15, Conjecture 3.1.2 proposed such a formula, which we give now. This conjecture was proved recently by Carlsson and Mellit 6, Theorem 7.5 as a consequence of proving a refinement of it called the compositional shuffle conjecture. However, many still refer to it as the shuffle conjecture, and hence we will too.

Theorem 3.3 (The shuffle conjecture).

$$\begin{equation*} \nabla e_n = \sum _{\pi \in PF_n} t^{\operatorname {area}(\pi )} q^{\operatorname {dinv}(\pi )} F_{n, \operatorname {ides}(\pi )}. \end{equation*}$$

Example 3.4.

Let us compute $n=2$. In order to compute $\nabla e_2$, we first need to calculate the elements of $PF_2$ that are as follows.

$$\begin{equation*} \vcenter{\img[][43pt][67pt][{\renewcommand{\arraystretch}{1} \setlength{\unitlength}{1.0pt} \begin{tikzpicture}[scale=0.7, every node/.style={font=\Large}] \draw[line width=0.5pt, color=gray] (0, 0) grid (2, 2); \draw[line width=0.5pt, color=gray, dashed] (0, 0) -- (2, 2); \draw[rounded corners=4, color=black, line width=4pt] (0, 0) -- (0, 1) -- (0, 2) -- (1, 2) -- (2, 2); \node[] at (0.5, 0.5) {$\mathbf{1}$}; \node[] at (0.5, 1.5) {$\mathbf{2}$}; \node[] at (1, -1) {\large$\pi^{(1)}$}; \end{tikzpicture}}]{Images/img34ac096dc64f63d6494d754d4052927e.svg}} \qquad \vcenter{\img[][43pt][67pt][{\renewcommand{\arraystretch}{1} \setlength{\unitlength}{1.0pt} \begin{tikzpicture}[scale=0.7, every node/.style={font=\Large}] \draw[line width=0.5pt, color=gray] (0, 0) grid (2, 2); \draw[line width=0.5pt, color=gray, dashed] (0, 0) -- (2, 2); \draw[rounded corners=4, color=black, line width=4pt] (0, 0) -- (0, 1) -- (1, 1) -- (1, 2) -- (2, 2); \node[] at (0.5, 0.5) {$\mathbf{2}$}; \node[] at (1.5, 1.5) {$\mathbf{1}$}; \node[] at (1, -1) {\large$\pi^{(2)}$}; \end{tikzpicture}}]{Images/imgfe209500d23b533a7846b96d60da9a7f.svg}} \qquad \vcenter{\img[][43pt][67pt][{\renewcommand{\arraystretch}{1} \setlength{\unitlength}{1.0pt} \begin{tikzpicture}[scale=0.7, every node/.style={font=\Large}] \draw[line width=0.5pt, color=gray] (0, 0) grid (2, 2); \draw[line width=0.5pt, color=gray, dashed] (0, 0) -- (2, 2); \draw[rounded corners=4, color=black, line width=4pt] (0, 0) -- (0, 1) -- (1, 1) -- (1, 2) -- (2, 2); \node[] at (0.5, 0.5) {$\mathbf{1}$}; \node[] at (1.5, 1.5) {$\mathbf{2}$}; \node[] at (1, -1) {\large$\pi^{(3)}$}; \end{tikzpicture}}]{Images/img189808f8df4bf90f8713047b298cf688.svg}} \end{equation*}$$

They have

$$\begin{equation*} \begin{array}{lccclcc} \operatorname {area}(\pi ^{(1)})&=&1&\ &\operatorname {dinv}(\pi ^{(1)})&=&0\\\operatorname {area}(\pi ^{(2)})&=&0&\ &\operatorname {dinv}(\pi ^{(2)})&=&0\\\operatorname {area}(\pi ^{(3)})&=&0&\ &\operatorname {dinv}(\pi ^{(3)})&=&1\\&&&&&&\\\operatorname {word}(\pi ^{(1)})&=&21&\ &\operatorname {ides}(\pi ^{(1)})&=&\{1\}\\\operatorname {word}(\pi ^{(2)})&=&12&\ &\operatorname {ides}(\pi ^{(2)})&=&\emptyset \\\operatorname {word}(\pi ^{(3)})&=&21&\ &\operatorname {ides}(\pi ^{(3)})&=&\{1\}\\\end{array} \end{equation*}$$

and hence

$$\begin{equation*} \nabla e_2 = tF_{2, \{1\}} + F_{2,\emptyset } + q F_{2,\{1\}} = F_{2,\emptyset } + (q+t) F_{2,\{1\}}. \end{equation*}$$

By equation 3.3 and the definition of $DH_n[Z;q,t]$ in equation 3.2, we know that $\nabla e_2$ can be written as a positive linear combination of Schur functions. Using Definition 2.5, we have that

$$\begin{equation*} s_2 = F_{2,\emptyset }\quad \text{and}\quad s_{11} = F_{2,\{1\}} \end{equation*}$$

from the respective SYTs

$$\begin{equation*} \vcenter{\img[][33pt][16pt][{\renewcommand{\arraystretch}{1} \setlength{\unitlength}{1.0pt} \begin{ytableau}1&2\end{ytableau}}]{Images/imga5774a07816414d0f8a0eaaea9155e01.svg}} \quad \text{ and }\quad \vcenter{\img[][17pt][32pt][{\renewcommand{\arraystretch}{1} \setlength{\unitlength}{1.0pt} \begin{ytableau}1\\2\end{ytableau}}]{Images/img6f9feb2b69c252ff6ac0d87570622ed5.svg}} \end{equation*}$$

and hence

$$\begin{equation*} \nabla e_2 = s_2 + (q+t) s_{11}. \end{equation*}$$

It is still an open problem to find a formula for $\nabla e_n$ that is a manifestly positive linear combination of Schur functions.

We conclude this subsection with an indication of why the shuffle conjecture was so named. The name arose because the coefficient of the monomial $z_1^{\lambda _1} z_2^{\lambda _2}\cdots z_{\ell (\lambda )}^{\lambda _{\ell (\lambda )}}$ in $\nabla e_n$ is equal to 15, Corollary 3.3.1

$$\begin{equation*} \sum t^{\operatorname {area}(\pi )}q^{\operatorname {dinv}(\pi )}, \end{equation*}$$

where the sum is over all ${\pi \in PF_n}$ such that $\operatorname {word}(\pi )$ is a shuffle of the lists

$$\begin{equation*} [1, 2, \ldots , \lambda _1],\ [\lambda _1 +1, \lambda _1 +2, \ldots ,\lambda _1+\lambda _2], \ldots ,\ [m+ 1, m+2, \ldots , n], \end{equation*}$$

where $m= \sum _{i=1} ^{\ell (\lambda ) -1}\lambda _i$; that is, within $\operatorname {word}(\pi )$ the numbers within each list appear in order when $\operatorname {word}(\pi )$ is read from left to right.

Example 3.5.

Given the lists $[\mathit{1},\mathit{2}]$ and $[\mathbf{3},\mathbf{4}]$, note that $\mathit{1}\mathbf{3}\mathbf{4}\mathit{2}$ is a shuffle of the lists, but $\mathit{1}\mathbf{4}\mathbf{3}\mathit{2}$ is not since $\mathbf{3}$ and $\mathbf{4}$ are not in order.

3.2. The compositional shuffle conjecture

The conjecture that Carlsson and Mellit proved was not the shuffle conjecture from the previous subsection, but rather a refinement of it known as the compositional shuffle conjecture. This refinement by Haglund, Morse, and Zabrocki 16, Conjecture 4.5 centred around further symmetric functions $C_\alpha$, where $\alpha \vDash n$, that satisfy

$$\begin{equation*} e_n = \sum _{\alpha \vDash n} C_\alpha \end{equation*}$$

so that

$$\begin{equation} \nabla e_n = \sum _{\alpha \vDash n} \nabla C_\alpha , {\tag{3.4}} \end{equation}$$

and it involved a fourth statistic on parking functions, that of a touch composition.

Definition 3.6 (Touch).

If $\pi$ is a parking function of order $n$, then note the set of row numbers from bottom to top where there is a car in a square on the diagonal $y=x$

$$\begin{equation*} \{i_1=1, i_2, \ldots , i_k\}. \end{equation*}$$

Then the touch composition is

$$\begin{equation*} \operatorname {touch}(\pi ) = (i_2-i_1)(i_3-i_2)\cdots (n+1-i_k). \end{equation*}$$

Example 3.7.

If $\pi$ is from Figure 1, then the set of row numbers where there is a car in a square on $y=x$ is $\{1,4,7\}$, and hence

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

We can now state the compositional shuffle conjecture of Haglund, Morse, and Zabrocki 16, Conjecture 4.5, which was proved by Carlsson and Mellit 6, Theorem 7.5.

Theorem 3.8 (The compositional shuffle conjecture).

Let $\alpha \vDash n$.

$$\begin{equation*} \nabla C_\alpha = \sum _{\pi \in PF_n \atop \operatorname {touch}(\pi )=\alpha } t^{\operatorname {area}(\pi )} q^{\operatorname {dinv}(\pi )} F_{n, \operatorname {ides}(\pi )}. \end{equation*}$$

Observe that proving this would immediately prove the shuffle conjecture since if we sum over all $\alpha \vDash n$, then the left-hand side would yield $\nabla e_n$ by equation 3.4 and the right-hand side would lose its touch composition restriction.

Example 3.9.

Let us compute $n=2$. From Example 3.4 we have that the elements of $PF_2$ are again as follows.

$$\begin{equation*} \vcenter{\img[][43pt][67pt][{\renewcommand{\arraystretch}{1} \setlength{\unitlength}{1.0pt} \begin{tikzpicture}[scale=0.7, every node/.style={font=\Large}] \draw[line width=0.5pt, color=gray] (0, 0) grid (2, 2); \draw[line width=0.5pt, color=gray, dashed] (0, 0) -- (2, 2); \draw[rounded corners=4, color=black, line width=4pt] (0, 0) -- (0, 1) -- (0, 2) -- (1, 2) -- (2, 2); \node[] at (0.5, 0.5) {$\mathbf{1}$}; \node[] at (0.5, 1.5) {$\mathbf{2}$}; \node[] at (1, -1) {\large$\pi^{(1)}$}; \end{tikzpicture}}]{Images/img34ac096dc64f63d6494d754d4052927e.svg}} \qquad \vcenter{\img[][43pt][67pt][{\renewcommand{\arraystretch}{1} \setlength{\unitlength}{1.0pt} \begin{tikzpicture}[scale=0.7, every node/.style={font=\Large}] \draw[line width=0.5pt, color=gray] (0, 0) grid (2, 2); \draw[line width=0.5pt, color=gray, dashed] (0, 0) -- (2, 2); \draw[rounded corners=4, color=black, line width=4pt] (0, 0) -- (0, 1) -- (1, 1) -- (1, 2) -- (2, 2); \node[] at (0.5, 0.5) {$\mathbf{2}$}; \node[] at (1.5, 1.5) {$\mathbf{1}$}; \node[] at (1, -1) {\large$\pi^{(2)}$}; \end{tikzpicture}}]{Images/imgfe209500d23b533a7846b96d60da9a7f.svg}} \qquad \vcenter{\img[][43pt][67pt][{\renewcommand{\arraystretch}{1} \setlength{\unitlength}{1.0pt} \begin{tikzpicture}[scale=0.7, every node/.style={font=\Large}] \draw[line width=0.5pt, color=gray] (0, 0) grid (2, 2); \draw[line width=0.5pt, color=gray, dashed] (0, 0) -- (2, 2); \draw[rounded corners=4, color=black, line width=4pt] (0, 0) -- (0, 1) -- (1, 1) -- (1, 2) -- (2, 2); \node[] at (0.5, 0.5) {$\mathbf{1}$}; \node[] at (1.5, 1.5) {$\mathbf{2}$}; \node[] at (1, -1) {\large$\pi^{(3)}$}; \end{tikzpicture}}]{Images/img189808f8df4bf90f8713047b298cf688.svg}} \end{equation*}$$

They have

$$\begin{equation*} \begin{array}{lcl} \operatorname {touch}(\pi ^{(1)})&=&2\\\operatorname {touch}(\pi ^{(2)})&=&11\\\operatorname {touch}(\pi ^{(3)})&=&11,\\\end{array} \end{equation*}$$

hence

$$\begin{align*} \nabla C_2&=tF_{2, \{1\}}\\ \nabla C_{11}&=F_{2,\emptyset } + q F_{2,\{1\}}, \end{align*}$$

and from Example 3.4

$$\begin{equation*} \nabla e_2 = tF_{2, \{1\}} + F_{2,\emptyset } + q F_{2,\{1\}} = \nabla C_2 + \nabla C_{11}. \end{equation*}$$

4. The proof and further directions

On 25 August 2015 Carlsson and Mellit posted an article on the arXiv 5 titled simply “A proof of the shuffle conjecture”, in which they proved the compositional shuffle conjecture, which in turn proved the shuffle conjecture. In their proof they refined the compositional shuffle conjecture yet further, and they proved this refinement.

They worked with the right-hand side of the compositional shuffle conjecture under what is known as the $\zeta$ map, which takes a parking function $\pi$ to a new Dyck path with cars placed in the squares along $y=x$ such that when the cars are read from right to left we obtain $\operatorname {word}(\pi )$. This required them to develop an analogue of $\operatorname {touch}$ that they called $\operatorname {touch}'$. They also worked with the reverse ordering of cars, so that, for example, in a parking function the cars in the same column decrease when read from bottom to top. The list of other ingredients that they were required to create is impressive and included a generalization of the double affine Hecke algebra; partial Dyck paths; numerous operators including raising and lowering operators involving Hecke algebra operators and plethysm, and a modification of Demazure–Lusztig operators; and a recurrence that their refinement satisfied.

To give a further idea of the complexity of the proof, this proof was almost 30 pages in length. In order to make it more accessible to combinatorialists, at the request of Garsia, in 17 Haglund, and Xin expanded the proof, and their resulting article is 60 pages in length.

4.1. Further directions

Carlsson and Mellit’s proof of the shuffle conjecture was published in the Journal of the American Mathematical Society in 2018 6, but there remain many related open problems, some of which we list below.

(1)

A Schur-positive formula for $\nabla e_n$. By equations 3.3 and 3.2 we know that when we express $\nabla e_n$ as a linear combination of Schur functions,$$\begin{equation*} \nabla e_n = \sum _{c,d\geq 0} t^cq^d \sum _{\lambda \vdash n}\mathscr{D}_\lambda s_\lambda , \end{equation*}$$

we have that the coefficients $\mathscr{D}_\lambda$ must be nonnegative integers since they are counting multiplicities. It remains an open problem to find a combinatorial formula for the $\mathscr{D}_\lambda$, namely a formula that would compute them directly as nonnegative integers by counting a set of objects.

(2)

Nabla on other symmetric functions. While the search for a combinatorial formula for $\nabla e_n$ has now been concluded with the proof of the shuffle conjecture, it remains to prove the formula of Loehr and Warrington 25, Conjecture 2.1 for$$\begin{equation*} \nabla s_\lambda \end{equation*}$$

as the formula would generalize the result for $\nabla e_n$ since $e_n = s_{1^n}$. However, a conjecture of Loehr and Warrington 24, p. 667 for$$\begin{equation*} \nabla p_n, \end{equation*}$$

where $p_n$ is the $n$th power sum symmetric function$$\begin{equation*} p_n = z_1^n+ z_2^n+\cdots , \end{equation*}$$

was recently proved by Sergel 30, Theorem 4.11 who has also conjectured the existence of a formula 31, Conjecture 3.1 for$$\begin{equation*} \nabla m_\lambda , \end{equation*}$$

where $m_\lambda$ is the monomial symmetric function$$\begin{equation*} m_\lambda = \sum z_{i_1}^{\lambda _1}z_{i_2}^{\lambda _2}\cdots z_{i_{\ell (\lambda )}}^{\lambda _{\ell (\lambda )}} \end{equation*}$$

for $\lambda = \lambda _1\lambda _2\cdots \lambda _{\ell (\lambda )} \vdash n$ and the indices and monomials are distinct.

(3)

A formula for $q,t$-Kostka polynomials. The modified Macdonald polynomials $\widetilde{H}_\lambda$, $\lambda \vdash n$, can be expanded as a linear combination of Schur functions$$\begin{equation*} \widetilde{H}_\lambda = \sum _{\mu \vdash n} \widetilde{K}_{\mu \lambda }(q,t) s_\mu , \end{equation*}$$

where the $\widetilde{K}_{\mu \lambda }(q,t)$ are known as $q,t$-Kostka polynomials. It is still an open problem to find a combinatorial formula for them, although such formulas have been found for $\lambda = m1^{n-m}$ by Stembridge 35, Theorem 2.1, and also for $\lambda = 2^m1^{n-2m}$ by Fishel 9, Theorem 1.1, and others. Assaf, furthermore, has a theorem that enables the unification of these two cases 2, Theorem 18.

Figure 1.

A parking function of order 8