# The shuffle conjecture

By Stephanie van Willigenburg

On the occasion of Adriano Garsia’s 90th birthday

## Abstract

Walks in the plane taking unit-length steps north and east from to never dropping below 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.

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 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 Reference 5 and published in 2018 Reference 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 Reference 27, they were introduced as a model for parking cars subject to preferences by Konheim and Weiss who were studying data storage Reference 23, Section 6: A parking problem—the case of the capricious wives. Konheim and Weiss also proved that the number of parking functions involving cars is . Since then these functions have arisen in a plethora of places from hyperplane arrangements Reference 33 to chip-firing Reference 8. More details on parking functions can be found, for example, in the survey by Yan Reference 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 Reference 11, p. 227. However, before we do this, we need to define a Dyck path.

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.

The second statistic is slightly more intricate than the area.

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

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

## 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 of , denoted by , is a list of positive integers such that . We call the the parts of , call the size of , and call the length of . If, furthermore, , then we say that is a partition of and denote this by . For example, 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, , is a subalgebra of , meaning that is a vector space, over , of formal power series in the variables , , …, in which we can also multiply the elements together. A basis for is given by the set of all fundamental quasisymmetric functions that we now define in the variables , indexed by and subsets of .

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

Given a partition , we define its Young diagram, also denoted by , to be the array of left-justified boxes with boxes in row from the top. Given the Young diagram, , a standard Young tableau (SYT) of shape , , is a filling of the boxes of with , , …, , 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 by .

Given an SYT, , of shape , we define its descent set to be

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

The Schur functions are not the only basis of . Another basis that will be vital to our story is the basis consisting of all elementary symmetric functions: We define the th elementary symmetric function to be

where is the partition consisting of parts equal to 1. Then if , we define the elementary symmetric function to be

Symmetric functions date back to Girard Reference 13 in 1629, although Schur functions are much younger, dating to an 1815 paper by Cauchy Reference 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 Reference 29, while standard Young tableaux were defined by Young in his 1928 publication Reference 37, p. 258. Substantial historical notes on this subject can be found in Stanley’s second volume on enumerative combinatorics Reference 34, Chapter 7, which is also an excellent resource for symmetric functions and some related representation theory, as is the book by Sagan Reference 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.

The symmetric group, , acts naturally on by the diagonal action that permutes the and variables simultaneously. Namely, given and , we have that

By equation Equation 3.1 we see that if , then . Furthermore, if we let be the subspace of , whose elements have total degree in the variables , , …, and total degree in the variables , , …, , then if , then . This enables us to define the bigraded Frobenius characteristic of to be

where, as before, is a Schur function in the variables and is the multiplicity of the irreducible character of , , in the character of under the diagonal action of , .

### 3.1. The shuffle conjecture

The shuffle conjecture is a combinatorial formula for computing in equation 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 Reference 21 and in the illuminating texts by Bergeron Reference 3 and Haglund Reference 14.

In 1988 Kadell Reference 22 looked for, and then Macdonald Reference 26 found, a generalization of Schur functions, with additional parameters , , where . This generalization specialized to the Schur functions at , and to other well-known functions such as the elementary symmetric functions and Hall–Littlewood functions, which were likewise recovered by setting and to various values. These functions were then transformed by Garsia and Haiman Reference 11, p. 194, thus creating modified Macdonald polynomials , 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 Reference 10, now known as Garsia–Haiman modules, and conjectured that the bigraded Frobenius characteristic of was . Moreover, they conjectured in Reference 10, Conjecture 1 that irrespective of , we have

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

At the same time, Garsia and Haiman were studying , which contains all the for as subspaces, and they conjectured a formula for in terms of the . Bergeron and Garsia noted that this formula was almost identical to the formula for the elementary symmetric functions in terms of . More precisely, if the coefficient of in was , then its conjectured coefficient in was

where if , then and is the transpose of , which is the partition created from by setting

For example, if , then . This inspired Bergeron and Garsia to officially define the nabla operator in the paper Reference 4, Equation (4.11) as

Hence, when Haiman, using algebraic geometry, proved the conjectured formula for Reference 19, Theorem 3.2, this automatically yielded that Reference 19, Proposition 3.5

since from above

and now it was proved that

Haiman had also proved Reference 19, Proposition 3.6 that

This supported the search for a collection of objects, such as all parking functions of order , along with statistics on them, in order to find a formula to compute more easily. The shuffle conjecture of Haglund, Haiman, Loehr, Remmel, and Ulyanov Reference 15, Conjecture 3.1.2 proposed such a formula, which we give now. This conjecture was proved recently by Carlsson and Mellit Reference 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.