A proof of the shuffle conjecture

By Erik Carlsson and Anton Mellit


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 whose degree zero part is the ring of symmetric functions over . We then extend these operators to an action of an algebra acting on this space, and interpret the right generalization of the using an involution of the algebra which is antilinear with respect to the conjugation .

1. Introduction

The shuffle conjecture of Haglund, Haiman, Loehr, Remmel, and Ulyanov Reference HHL05b predicts a combinatorial formula for the Frobenius character of the diagonal coinvariant algebra in pairs of variables, which is a symmetric function in infinitely many variables with coefficients in . By a result of Haiman Reference Hai02, the Frobenius character is given explicitly by

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

Here is a Dyck path of length , and is some extra data called a “word parking function” depending on . The functions are statistics associated to a Dyck path and a parking function, and is a monomial in the variables . It was shown in Reference HHL05b that this sum, denoted , is symmetric in the 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 -Catalan numbers, and other special cases Reference GH96Reference GH02Reference Hag03Reference EHKK03Reference Hag04. Remarkably, had not even been proven to be symmetric in the variables until now, even though the symmetry of is obvious. The name “shuffle conjecture” has to do with the fact that the coefficient of in equation Equation 1.1 can be expressed in terms of parking functions that are -shuffles”. See Conjecture 6.1 of Haglund’s book Reference Hag08 for a detailed explanation, and Chapter 6 in general for a thorough introduction to this topic.

In Reference HMZ12 Haglund, Morse, and Zabrocki conjectured a refinement of the original conjecture which partitions by specifying the points where the Dyck path touches the diagonal called the “compositional shuffle conjecture”. The refined conjecture states

Here is a composition, i.e., a finite list of positive integers specifying the gaps between the touch points of . The function is defined below as a composition of creation operators for Hall–Littlewood polynomials in the variable . They proved that

implying that Equation 1.2 does indeed generalize Equation 1.1. The right-hand side of Equation 1.2 will be denoted by . A desirable approach to proving Equation 1.2 would be to determine a recursive formula for and to interpret the result in terms of some commutation relations for . Indeed, this approach has been applied in some important special cases; see Reference GH02Reference GXZ12Reference Hic12. In Reference 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 Reference 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 of symmetric functions over with additional variables adjoined, where is the length of the composition ,

In our first result (Theorem 4.11) we will explain how to recover from , which is defined by an explicit recursion. In fact, while they live in different vector spaces, the recursions for are similar to the recursions for the Catalan case in Reference 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 and which are isomorphic by an antilinear isomorphism with respect to the conjugation , as well as an explicit action of each on the direct sum . We will then prove that there is an antilinear involution on which intertwines the two actions (Theorem 7.4) and represents an involutive automorphism on a larger algebra . This turns out to be the essential fact that relates the to .

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


There is a surjection coming from

which maps a monomial in the variables to an element which is similar to and maps to , up to a sign.


The involution commutes with and maps to .


The restriction of to agrees with composed with a conjugation map which essentially exchanges the and .

It then becomes clear that these properties imply Equation 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 Reference BGLX14Reference GORS14Reference GN15Reference Neg13Reference Hik14Reference SV11Reference SV13. We hope that future applications to these fascinating topics will be forthcoming.

2. The compositional shuffle conjecture

2.1. Plethystic operators

A -ring is a ring with a family of ring endomorphisms satisfying

Unless stated otherwise, the endomorphisms are defined by for each variable such as . The ring of symmetric functions over the -ring is a free -ring with generator , and it will be denoted . We will employ the standard notation used for plethystic substitution defined as follows: given an element and in some -ring , the plethystic substitution is the image of the homomorphism from defined by replacing by . For instance, we would have

See Reference Hai01 for a reference.

The modified Macdonald polynomials Reference GHT99 will be denoted

where is the integral form of the Macdonald polynomial Reference Mac95, and

The operator is defined by

Note that our definition differs from the usual one from Reference BGHT99 by the sign . We also have the sequences of operators given by the formulas

where is the plethystic exponential and denotes the operation of taking the coefficient of of a Laurent power series. Our definition again differs from the one in Reference HMZ12 by a factor . For any composition , let denote the composition , and similarly for .

Finally, we denote by the involutive automorphism of obtained by sending to . We denote by the -ring automorphism of obtained by sending to and by its composition with , i.e.,

2.2. Parking functions

We now recall the combinatorial background to state the shuffle conjecture, for which we refer to Haglund’s book Reference Hag08. We consider the infinite grid on the top right quadrant of the plane. Its intersection points are denoted as with . For each cell of the grid, its coordinates are the coordinates of the top right corner. Thus indexes the columns and indexes the rows. Let be the set of Dyck paths of all lengths. A Dyck path of length is a grid path, from to consisting of North and East steps, that stays above the main diagonal . For denote by its length . For , let

This is the set of cells between the path and the diagonal. Let denote the number of cells in the row . The area sequence is the sequence and we have .

Let be the cells immediately to the right of the North steps. The sequence is called the coarea sequence, and we have for all .

We have the statistic and the set defined by

For , we say that attacks .

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

In other words, the elements of are -tuples 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 , let

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 . This corresponds to choosing the opposite total ordering on everywhere, which does not affect the final answer and is more convenient for the purposes of this paper.

Let us call the touch composition of if are the lengths of the gaps between the points where touches the main diagonal starting at the lower left. Equivalently, and the numbers , , , are the positions of in the area sequence .

Example 2.1.

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

whence , . The labels shown above correspond to the vector , which we can see is an element of because we have , , . We then have

giving .

2.3. The shuffle conjectures

For any infinite set of variables , let . In this notation, the original shuffle conjecture Reference HHL05b states

Conjecture (Reference HHL05b).

We have

In particular, the right-hand side is symmetric in the , and in .

The stronger compositional shuffle conjecture Reference HMZ12 states

Conjecture (Reference HMZ12).

For any composition , we have

2.4. From to

In this paper, we will prove an equivalent version of this conjecture, as obtained in Reference LN14, Theorem 14, by applying the to bijection from Reference HL05 and Reference 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 , we will obtain a pair , by a procedure described below. After the end of this section we will only work with , so we will drop the apostrophe.

The Dyck path is obtained as follows: sort the cells in the reading order, i.e., in increasing order by the corresponding labels , using the row index 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 from Example 2.1, the list would be

Let be the position of the cell in this list. This defines a permutation . In the example case, we would get

Now we observe that for each the cell attacks all the subsequent cells in the reading order whose position is before the position where we would place if it were an element of the list.

More precisely, there is a unique Dyck path for which