Séminaire Lotharingien de Combinatoire 54A (2006), Article B54Ao

THE GENESIS OF THE MACDONALD POLYNOMIAL STATISTICS

J. Haglund

Department of Mathematics University of Pennsylvania Philadelphia, PA 19104-6395

                 jhaglund@math.upenn.edu

Dedicated to Adriano Garsia

Abstract. Recently M. Haiman, N. Loehr and the author [J. Amer. Math. Soc. 18 (2005), 735–761] proved that for μ a partition of n, the modified Macdonald polynomial H̃_{μ}[z_{1}, …, z_{n}; q, t] can be expressed as a sum of monomials in the z_{i} times certain nonnegative integral powers of q, t with direct combinatorial descriptions (i.e. statistics). These powers are generalizations of the classical permutation statistics maj and inv. The result was first conjectured by the author [Proc. Nat. Acad. Sci. U.S.A. 101 (2004), 16127–16131], and was partially motivated by a conjectured formula for the character of the space of diagonal harmonics [Duke J. Math. 126 (2005), 195–232]. Beyond giving a long-sought after combinatorial formula for Macdonald polynomials, this result has many nice corollaries, including a simple proof of Lascoux and Schützenberger’s formula, involving the statistic cocharge, for Hall-Littlewood polynomials. In this paper we describe the sequence of experimental steps and Maple calculations which led to the discovery of these Macdonald polynomial statistics.

Riassunto. In un recente lavoro in collaborazione con M. Haiman, N. Loehr [J. Amer. Math. Soc. 18 (2005), 735–761] dimostriamo che per una partizione di n, μ, il polinomio di Macdonald modificato H̃_{μ}[z_{1}, …, z_{n}; q, t] puo’ essere espresso come un polinomio nelle variabili z_{i} i cui cofficienti sono potenze non negative di q, t. Questo risultato ha una diretta interpretazione combinatoria (o meglio statistica). Gli esponenti dei coefficienti sono una generalizzazione delle classiche statistiche di permutazione maj e inv. L’ipotesi di un tale risultato fu avanzata in [Proc. Nat. Acad. Sci. U.S.A. 101 (2004), 16127–16131] e in parte fu motivata dalla formula, in forma di congettura, per i caratteri dello spazio delle armoniche diagonali [Duke J. Math. 126 (2005), 195–232]. Questo risultato non solo da’ un’interpretazione combinatoria, cercata da lungo tempo, dei polinomi di Macdonald, ma permette di derivare anche altri risultati rilevanti. Per esempio e’ possibile dare una dimostrazione semplificata della formula di Lascoux and Schützenberger riguardante la statistica cocharge per i polinomi di Hall-Littlewood. In questo articolo descriviamo la sequenza di passaggi sperimentali e di calcoli fatti utilizzando Maple che portano alla scoperta della statistica dei polinomi di Macdonald.

1. Introduction

Given a sequence μ = (μ_{1}, μ_{2}, …) of nonincreasing, nonnegative integers with ∑_{i} μ_{i} = n, we say μ is a partition of n, denoted by either |μ| = n or μ ⊢ n. By adding or subtracting parts of size 0 if necessary, we will always assume partitions of n have exactly n parts. We let n(μ) = ∑_{i}(i − 1)μ_{i}, and if λ is another partition, set K̃_{λ,μ}(q, t) = t^{n(μ)}K_{λ,μ}(q, 1/t), where K_{λ,μ}(q, t) is Macdonald’s q, t-Kostka polynomial [Mac95, p.354]. We call H̃_{μ}[Z; q, t] = ∑_{λ⊢|μ|} s_{λ}K̃_{λ,μ}(q, t) the modified Macdonald polynomial, where s_{λ} = s_{λ}[Z] is the Schur function, the sum is over all λ ⊢ |μ|, and Z = z_{1}, …, z_{n}. The H̃_{μ}[Z; q, t] can be easily transformed by a plethystic substitution into Macdonald’s original symmetric functions P_{μ}[Z; q, t]. Macdonald defined the P_{μ} in terms of orthogonality with respect to a scalar product, and conjectured K_{λ,μ}(q, t) ∈ ℕ[q, t] [Mac95, p. 355]. (From their definition, all one can infer is that the K_{λ,μ}(q, t) are rational functions in q, t). This conjecture in turn led Garsia and Haiman to the “n! conjecture” [GH93], which was proved by Haiman in 2000 [Hai01]. This result implies that K̃_{λ,μ}(q, t) ∈ ℕ[q, t], and moreover that H̃_{μ}[X; q, t] is the character of a certain S_{n}-module V (μ), and thus gives a representation-theoretical interpretation for the coefficients of K̃_{λ,μ}(q, t). Macdonald also posed the problem of finding a combinatorial rule to describe the K_{λ,μ}(q, t), which is still open.

Recently the author introduced a conjectured combinatorial formula for the coefficient of a monomial in H̃_{μ}[Z; q, t] [Hag04a]. The formula, described in Section 2, is manifestly in ℕ[q, t, z_{1}, …, z_{n}]. Soon after its introduction, the conjecture was proved by M. Haiman, N. Loehr and the author: the formula took much longer to find than to prove. Some comments on the surprisingly short and elegant proof are made in Section 3. As a corollary they obtain a new, short proof of a famous result of Lascoux and Schützenberger, namely that the coefficients in the Schur function expansion of the Hall-Littlewood polynomial H̃_{μ}[Z; 0, t] can be expressed as a sum, over semi-standard Young tableaux W, of q to a statistic known as cocharge(W). This new proof is discussed in more detail in Section 4. Also, since the matrix expressing the Schur basis in terms of the monomial basis is upper unitriangular, another consequence is a new proof that the K̃_{λ,μ}(q, t) ∈ Z[q, t]. In addition a simple formula for the K̃_{λ,μ}(q, t) is obtained when μ has two columns. It is hoped that further refinements will result in combinatorial formulas for the K̃_{λ,μ}(q, t) for general μ.

The idea for this article was suggested by A. Garsia, who thought it would be beneficial to have a detailed description of the sequence of steps which led the author to the discovery of the formula. In Section 5 we overview the pioneering work of Garsia, Haiman and others on the n! conjecture, the space of diagonal harmonics DH_{n}, and the q, t-Catalan numbers. These numbers were defined by Garsia and Haiman as a complicated sum of rational functions in q, t, which they conjectured simplified to a polynomial in ℕ[q, t] [GH96]. We then discuss a series of discoveries by the author, M. Haiman and others involving combinatorial formulas for the q, t-Catalan numbers and other sequences connected to DH_{n}, which culminated in the introduction of the “shuffle conjecture” by Haglund, Haiman, Loehr, Remmel and Ulyanov [HHL^{+}05b], which gives a combinatorial formula for the character of DH_{n}.

In Section 6 we discuss how various special cases of the shuffle conjecture led the author to suspect an analogous combinatorial formula for the monomial expansion of H̃_{μ}[X; q, t] could be found. We then include an explanation of the various stages and Maple calculations in the experimental process which resulted in the discovery of the statistics.

2. The Formula

We assign (row,column)-coordinates to squares in the first quadrant, obtained by permuting the (x, y) coordinates of the upper right-hand corner of the square, so the lower left-hand square has coordinates (1, 1), the square above it (2, 1), etc.. For a square w, we call the first coordinate of w the row value of w, denoted row(w), and the second coordinate of w the column value of w, denoted col(w). Given μ ⊢ n, we let μ also stand for the Ferrers diagram of μ (French convention), consisting of the set of n squares with coordinates (i, j), with 1 ≤ i ≤ n, 1 ≤ j ≤ μ_{i}.

Let T be a finite set of squares in the first quadrant. A subset of squares of T consisting of all those w ∈ T with a given row value is called a row of T, and a subset of squares of T consisting of all those w ∈ T with a given column value is called a column of T. Furthermore, we let T (i) denote the ith square of T encountered if we read across rows from left to right, starting with the squares of largest row value and working downwards. Given a square w ∈ T, define the leg of w, denoted leg(w), to be the number of squares in T which are strictly above and in the same column as w, and the arm of w, denoted arm(w), to be the number of squares in T strictly to the right and in the same row as w. Also, if w has coordinates (i, j), we let south(w) denote the square with coordinates (i − 1, j).

A word σ of length n in an alphabet A is a linear sequence σ_{1}σ_{2} ⋯ σ_{n}, with σ_{i} ∈ A. Note that repeats are allowed. If the letter i occurs α_{i} times in σ, for each i ≥ 1, we say σ has content α, denoted content(σ) = α. We call a pair (σ, T), where σ is a word of positive integers and T is a set of squares in the first quadrant, a filling. We represent (σ, T) geometrically by placing σ_{i} in square T (i), for 1 ≤ i ≤ n. For w ∈ T, we let σ(w) denote the element of σ placed in square w, and we call σ_{1} ⋯ σ_{n} the reading word of (σ, T). A descent of (σ, T) is a square w ∈ T, with south(w) ∈ T and σ(w) > σ(south(w)).

Let Des(σ, T) denote the set of all descents of (σ, T). For partitions μ, define a generalized major index statistic maj(σ, μ) via

(1) maj(σ, μ) = ∑_{w∈Des(σ,μ)}(1 + leg(w)).

An inversion of (σ, T) is a pair of squares (a, b) with a, b ∈ T, σ(a) > σ(b), and either

\begin{cases}row(a) = row(b) and col(a) < col(b), or \\ row(a) = row(b) + 1 and col(a) > col(b) . \end{cases}

(2)

Let Inv(σ, T) denote the set of all inversions of (σ, T), and define the inversion statistic inv(σ, T) via

(3) inv(σ, T) = |Inv(σ, T)| − ∑_{w∈Des(σ,T)} arm(w),

where |T | denotes the cardinality of a set T. For example, if (σ, μ) is the filling in Figure 1, then representing squares by their coordinates,

Des(σ, μ) = {(2, 1), (4, 2), (2, 2)},
Inv(σ, μ) = {((3, 1), (3, 2)), ((2, 2), (2, 3)), ((2, 2), (1, 1)), ((2, 3), (1, 1)), ((2, 3), (1, 2))}, (4)

so maj(σ, μ) = 3 + 1 + 3 = 7, inv(σ, μ) = 5 − (2 + 0 + 1) = 2.

Figure 1. A filling of the partition (3, 3, 2, 2) by the word 2221353114.

Note that, if 1^{n} denotes a column of n cells, then

maj(σ, 1^{n}) = ∑_{i∈Des(σ,1^{n})} i, (5)

the usual major index statistic on the word σ, while

inv(σ, (n)) = ∑_{{1≤i<j≤n \atop σ_{i}>σ_{j}}} 1, (6)

the usual inversion statistic.

For μ ⊢ n, define

C̃_{μ}[Z; q, t] = ∑_{σ} t^{maj(σ,μ)}q^{inv(σ,μ)}z^{σ}, (7)

where z^{σ} = ∏_{i=1}^{n} z_{σ_{i}} is the “weight” of σ and the sum is over all words σ of n positive integers satisfying 1 ≤ σ_{i} ≤ n for 1 ≤ i ≤ n. The following result was conjectured by the author [Hag04a] and proved by Haglund, Haiman, Loehr [HHL05a]).

Theorem 1. For all partitions μ,

C̃_{μ}[Z; q, t] = H̃_{μ}[Z; q, t]. (8)

Given a set T of squares and a subset S ⊆ T, define

F_{T} [Z; q, S] = ∑_{{σ \atop Des(σ,T)=S}} q^{inv(σ,T)}z^{σ}. (9)

In [Hag04a] the following result is obtained.

Theorem 2. For all S, T, F_{T} [Z; q, S] is a symmetric function in the z_{i}.

Given S ⊆ μ, let

P (S) = ∑_{w∈S}(1 + leg(w)). (10)

Note that by the definition of maj(σ, μ),

C̃_{μ}[Z; q, t] = ∑_{S⊆μ} t^{P (S)}F_{μ}[Z; q, S]. (11)

In [HHL05a] it is shown that the F_{T} [Z; q, t] are special cases of polynomials introduced by Lascoux, Leclerc and Thibon [LLT97], commonly known as LLT polynomials. These are symmetric polynomials whose description involves a tuple of arbitrary skew shapes and whose coefficients depend on q. It has been an open conjecture of theirs that the coefficients of these polynomials when expanded in the Schur basis are in ℕ[q]. Thus we now have the expansion of H̃_{μ}[Z; q, t] into LLT polynomials, and furthermore understanding the positivity of the coefficients of the K̃_{λ,μ}(q, t) is reduced to understanding the special case of the positivity of LLT polynomials (when each skew-shape in the tuple is a ribbon).

Definition 1. Given a word σ of content (γ_{1}, γ_{2}, …), construct a permutation σ′, the standardization of σ, by replacing the γ_{1} 1’s in σ by the numbers 1, …, γ_{1}, the γ_{2} 2’s in σ by the numbers γ_{1} + 1, …, γ_{1} + γ_{2}, etc., in such a way that, for i < j, σ_{i} ≤ σ_{j} if and only if σ′_{i} < σ′_{j}. For example, if σ = 224123114 then σ′ = 458167239.

Remark 1. At first glance it may seem that inv(σ, T) may not always be nonnegative, but given a square u ∈ Des(σ, T), for each square v in the same row as u and to the right of u, either σ(u) > σ(v), or σ(v) > σ(south(u)), or both. Assume for the moment that σ has distinct entries. If we adopt the convention that for a square w ∉ T, σ(w) = ∞, it follows that inv(σ, T) equals the number of triples of squares u, v, w, where u ∈ T, v ∈ T, row(u) = row(v), col(u) < col(v), and south(u) = w, and if we draw a circle through u, v, w, and read in the σ values of u, v, w in counterclockwise order around the circle, starting at the smallest value, then the three values form a strictly increasing sequence. If σ has repeated entries, first standardize then count triples in (σ′, T) as above.

3. The Proof

Let p_{k}(Z) = ∑_{i} z_{i}^{k} be the kth power sum. Given a real parameter w, let p_{k}[Z(1 − w)] = ∑_{i} z_{i}^{K}(1 − w^{k}) and p_{k}[Z/(1 − w)] = ∑_{i} z_{i}^{k}/(1 − w^{k}). These are both special cases of plethystic notation, indicated by the square brackets around Z(1 − w) and Z/(1 − w). For an arbitrary symmetric function F (Z), let F [Z(1 − w)] (respectively F [Z/(1 − w)]) be the result of first expressing F (Z) as a polynomial in the p_{k}(Z), then replacing each p_{k}(Z) by p_{k}[Z(1 − w)] (respectively p_{k}[Z/(1 − w)]).

The polynomial H̃_{μ}[Z; q, t] can be defined [Hai03] as the unique polynomial satisfying the following axioms, where λ ≤ μ refers to the dominance order λ_{1} + … + λ_{i} ≤ μ_{1} + … + μ_{i} − 1 for 1 ≤ i ≤ n:

(M1) H̃_{μ}[Z(q − 1)] = ∑_{λ≤μ′} a_{λ,μ}m_{λ} for some a_{λ,μ} ∈ ℚ(q, t) (M2) H̃_{μ}[Z(t − 1)] = ∑_{λ≤μ} a_{λ,μ}m_{λ} for some a_{λ,μ} ∈ ℚ(q, t) (M3) The coefficient of z_{1}^{n} in the expansion of H̃_{μ}[Z; q, t] into monomials equals 1. We call a filling of μ by arbitrary nonzero integers a “super filling”. We usually

represent negative letters, such as −2, −4, −7 by “barred letters” \overline{2}, \overline{4}, \overline{7}. Assume the letters satisfy the ordering

1 < \overline{1} < 2 < \overline{2} < ⋯ < n < \overline{n}. (12)

Given a super filling σ, we define the standardization σ′ of σ to be the unique permutation satisfying σ′_{i} < σ′_{j} whenever σ_{i} < σ_{j}, or whenever i < j and σ_{i} = σ_{j} with σ_{i} a positive letter, or whenever i > j and σ_{i} = σ_{j} with σ_{i} a negative letter. We then extend the definition of maj and inv to super fillings by letting maj(σ, μ) = maj(σ′, μ) and inv(σ, μ) = inv(σ′, μ). Furthermore, we let |σ| be the filling obtained by replacing each σ_{i} by its absolute value.

Using some general results about quasi-symmetric functions and the superization of a symmetric function derived in [HHL^{+}05b], one easily obtains the fact that

C̃_{μ}[Z(q − 1); q, t] = ∑_{σ}(−1)^{m(σ)}q^{p(σ)+inv(σ,μ)}t^{maj(σ,μ)}z^{|σ|} (13)

C̃_{μ}[Z(t − 1); q, t] = ∑_{σ}(−1)^{m(σ)}q^{inv(σ,μ)}t^{p(σ)+maj(σ,μ)}z^{|σ|} (14)

where the sum is over all super fillings σ of μ, m(σ) is the number of negative letters in σ, and p(σ) is the number of positive letters in σ.

We say two squares u, v of a Ferrers shape attack each other if they are either in the same row, or if u is one row above v and in a column strictly to the right of v. Otherwise u, v are said to be nonattacking. We call a super filling (σ, μ) nonattacking if for all u, v ∈ μ, |σ(u)| = |σ(v)| implies u, v are nonattacking.

The first step in the proof of Theorem 1 involves the construction of a sign-reversing involution on super fillings of μ which cancels most of the terms in (13). The involution looks for an attacking pair of squares containing 1’s or \overline{1}’s. If more than one such pair exists, it chooses the last such pair in the reading word, and switches the sign of the first element of the pair in the reading word. One checks that the q, t-weights are preserved. If no attacking pairs containing 1, \overline{1}’s exist, then you search for attacking pairs containing 2, \overline{2}’s, etc. The fixed points are super fillings with no attacking pairs, which are easily seen to satisfy the triangularity condition (M1).

So far we have assumed (12) holds, but in fact (13) and (14) hold for any fixed total ordering of the alphabet of positive and negative letters. We now construct a second involution assuming the ordering

1 < 2 < ⋯ < n < \overline{n} < ⋯ < \overline{2} < \overline{1}. (15)

Search for the first occurrence of a 1 or \overline{1} in the reading word, ignoring any such letters in the bottom row. If such a 1, \overline{1} exists, then switch its sign. If there is no such 1 or \overline{1}, look for the first occurrence of a 2 or \overline{2}, ignoring any letters in the bottom two rows, etc. As in the first involution, the q, t weights are preserved. The fixed points are now super fillings with no 1’s or \overline{1}’s above the bottom row, no 2’s or \overline{2}’s above the bottom two rows, etc.. Hence the weight z^{|σ|} must satisfy λ_{1} ≤ μ_{1}, λ_{1} + λ_{2} ≤ μ_{1} + μ_{2}, etc., and (M2) is satisfied. The proof is completed by noting that if σ is the filling of all 1’s, inv(σ, μ) = maj(σ, μ) = 0, which implies (M3).

4. The Cocharge Formula

In this section we briefly highlight two consequences of Theorem 1, which are described in more detail in [HHL05a]. The first is the following famous result of Lascoux and Schützenberger, where SSY T (λ, μ) denotes the set of a semi-standard Young tableau of shape λ and weight μ, i.e. the set of fillings of λ by μ_{1}-1’s, μ_{2}-2’s, etc., with entries that are weakly increasing across rows and strictly increasing up columns.

Theorem 3.

(16)  H̃_{μ}[Z; 0, t] = ∑_{λ} s_{λ} ∑_{T ∈SSY T (λ,μ)} t^{cocharge(read(T))},

where the statistic cocharge is described (in the proof) below.

Proof. We begin by describing the set of fillings with no inversions. Let M_{i} be an arbitrary multiset of μ_{i} positive integers, for 1 ≤ i ≤ μ′_{1}, and consider those fillings of μ where the elements of M_{i} are placed in the ith row of μ, in any arbitrary order, for each i in the range 1 ≤ i ≤ μ′_{1}. It turns out there is exactly one of these fillings with no inversions. This filling can be constructed by first filling the bottom row of μ with the elements of M_{1}, in nondecreasing order left to right. Then in square (2, 1), place the smallest integer in M_{2} which is strictly bigger than σ_{M}(1, 1), if it exists. If all elements of M_{2} are less than or equal to σ_{M}(1, 1), then place the smallest element of M_{2} in (2, 1). It is easy to see that this will force any triple of squares of the form {(2, 1), (2, j), (1, 1)}, j ≥ 2, to form a clockwise circle in the sense of Remark 1. Next remove σ_{M}(2, 1) from M_{2} to form M′_{2}, and place the smallest element of M′_{2} larger than σ_{M}(1, 2) in square (2, 2), if it exists. If not, place the smallest element of M′_{2} in square (2, 2). Now iterate the process, moving left to right, in each square of row two placing the smallest remaining element larger than the element in the square just below, if it exists, and otherwise placing the smallest remaining element in the square. The same process is then applied to row 3, comparing elements of M_{3} to elements in the second row of σ_{M}, then moving on to row 4, etc.. If μ = 5531, M_{1} = {1, 1, 3, 6, 7}, M_{2} = {1, 2, 4, 4, 5}, M_{3} = {1, 2, 3}, and M_{4} = {2}, then σ_{M} is the filling in Figure 2.

Figure 2. A filling with no inversions.

We now construct a word associated to a filling σ we call the cocharge word cword(σ). Initialize cword(σ) to the empty string, then scan through the reading word of σ, starting at the beginning. Whenever a 1 is encountered, adjoin the number of the row containing this 1 to the left of cword(σ). After reaching the end of the reading word, scan through the reading word again, from the beginning, this time looking for 2’s. Whenever a 2 is encountered, adjoin the row number to the left of cword(σ) as before. After finishing the 2’s, loop back and scan through the reading word for 3’s, etc. For example, if σ is the filling in Figure 2, cword(σ) = 11222132341123.

Next we translate the statistic maj(σ, μ) into a statistic on cword(σ). Note that σ(1, 1) corresponds to the rightmost 1 in cword(σ) - denote this 1 by w_{11}. If σ(2, 1) > σ(1, 1), σ(2, 1) corresponds to the rightmost 2 which is left of w_{11}, otherwise it corresponds to the rightmost 2 (in cword(σ)). In any case denote this 2 by w_{12}. More generally, the element in cword(σ) corresponding to σ(i, 1) is the first i encountered when travelling left from w_{1,i−1}, looping around and starting at the beginning of cword(σ) if necessary. To find the subword w_{21}w_{22} ⋯ w_{2μ′_{2}} corresponding to the second column of σ, we do the same algorithm on the word cword(σ)′ obtained by removing the elements w_{11}w_{12} ⋯ w_{1μ′_{1}} from cword(σ), then remove w_{21}w_{22} ⋯ w_{2μ′_{2}} and apply the same process to find w_{31}w_{32} ⋯ w_{3μ′_{3}} etc..

Clearly σ(i, j) ∈ Des(σ, μ) if and only if w_{ij} occurs to the left of w_{i,j−1} in cword(σ). Thus maj(σ, μ) is transparently equal to the statistic cocharge(cword(σ)) described in [Man01, pp.48-49].

It is well known that for any word w of partition content,

cocharge (w) = cocharge (read(P (w))),

where read(P (w)) is the reading word of the insertion tableau P (w) under the RSK algorithm [Man01, pp.48-49], [Sta99, p.417]. Also, the RSK algorithm induces a bijection between certain two-line arrays of positive integers and pairs (P, Q) of SSYT of the same shape. The two-line arrays have the property that the entries in the upper row are nondecreasing, and below equal entries in the upper row the entries in the lower row are also nondecreasing. Under this bijection, the content of the upper row is the content of Q, and the content of the lower row is the content of P. The number of different Q tableau of content ν matched to a given P tableau of shape λ is the Kostka number K_{λ,ν} [Sta99, p.319].

We associate a two-line array to a filling σ with no inversions by letting the upper row be nonincreasing with the same content as σ, and the lower row be cword(σ). For example, to the filling in Figure 2 we associate the two-line array

7 6 5 4 4 3 3 2 2 2 1 1 1 1

1 1 2 2 2 1 3 2 3 4 1 1 2 3 (17)

By construction, below equal entries in the upper row the entries in the lower row are nondecreasing. As is, the upper row is nonincreasing instead of nondecreasing, but we can get around this problem by replacing j by n − j + 1 in the upper row, for 1 ≤ j ≤ n, where n is the size of μ. At the same time, we reverse the order of the variables, replacing x_{j} by x_{n−j+1} for 1 ≤ j ≤ n - this doesn’t change C_{μ} since it is a symmetric function. Then x^{σ} is the same as the content of Q, and since cocharge(cword(σ)) depends only on the P tableau,

C̃_{μ}[X; 0, t] = ∑_{ν} m_{ν} ∑_{λ} ∑_{{P ∈SSY T (λ,μ) \atop Q∈SSY T (λ,ν)}} t^{cocharge(read(P))}

= ∑_{λ} ∑_{P ∈SSY T (λ,μ)} t^{cocharge(read(P))} ∑_{ν} m_{ν}K_{λ,ν}

(18) = ∑_{λ} s_{λ} ∑_{P ∈SSY T (λ,μ)} t^{cocharge(read(P))}.

□

For our second consequence of Theorem 1, we use the super filling interpretation for H̃_{μ}[Z(q − 1); q, t] from (13) to obtain a new formula for the expansion of Macdonald’s symmetric function J_{μ}[Z; q, t] into monomials. We then show how our formula immediately implies a result of Knop and Sahi for Jack symmetric functions.

By definition we have

J_{μ}[Z; q, t] = t^{n(μ)}H̃_{μ}[Z(1 − t); q, 1/t]
= t^{n(μ)}H̃_{μ}[Zt(1/t − 1); q, 1/t]

= t^{n(μ)+n}H̃_{μ′}[Z(1/t − 1); 1/t, q] (19)

using the well-known relation H̃_{μ}[Z; q, t] = H̃_{μ′}[Z; t, q]. The first involution from the proof of Theorem 1 gives a combinatorial interpretation for (19) in terms of super fillings of μ′. Say two super fillings σ, β are “companions” if |σ| = |β|. Note that companionship forms an equivalence relation. By grouping fillings according to this relation, one can easily derive the following result.

Theorem 4. For any partition μ,

J_{μ}[Z; q, t] = ∑_{nonattacking fillings (T, μ′)} z^{T} q^{maj(T,μ′)}t^{n(μ)−inv(T,μ′)}

(20)  × ∏_{{w∈μ′ \atop T (w)=T (South(w))}}(1 − q^{1+leg(w)}t^{1+arm(w)}) ∏_{{w∈μ′ \atop T (w)≠T (South(w))}}(1 − t).

Remark 2. The (integral form) Jack polynomials J_{μ}^{α}[Z] can be defined as [Mac95, p.381]

lim_{t→1}(1 − t)^{−|μ|}J_{μ}[Z; t^{α}, t]. (21)

By setting q = t^{α} in Theorem 4 and taking the limit as t → 1 of (21) we immediately get the following formula of Knop and Sahi [KS97].

J_{μ}^{α}[Z] = ∑_{nonattacking fillings (T, μ′)} z^{T} ∏_{{w∈μ′ \atop T (w)=T (South(w))}}(1 + α(1 + leg(w)) + 1 + arm(w)). (22)

5. Diagonal Harmonics and the n! Conjecture

Assume μ ⊢ n, w_{1}, …, w_{n} is an arbitrary ordering of the squares of μ, and set

Δ_{μ}(x_{1}, …, x_{n}, y_{1}, …, y_{n}) = |x_{i}^{row(w_{j})}y_{i}^{col(w_{j})}|_{1≤i,j≤n} . (23)

For example,

Δ_{221} = |\begin{matrix}1 & y_{1} & x_{1} & x_{1}y_{1} & x_{1}^{2} \\ 1 & y_{2} & x_{2} & x_{2}y_{2} & x_{2}^{2} \\ 1 & y_{3} & x_{3} & x_{3}y_{3} & x_{3}^{2} \\ 1 & y_{4} & x_{4} & x_{4}y_{4} & x_{4}^{2} \\ 1 & y_{5} & x_{5} & x_{5}y_{5} & x_{5}^{2}. \end{matrix}| (24)

Note that Δ_{1^{n}} is, up to sign, the Vandermonde determinant in x_{1}, …, x_{n}.

Next define the Garsia-Haiman module V (μ) as the linear span over ℂ of Δ_{μ} and its partial derivatives of all orders. An element σ = σ_{1} ⋯ σ_{n} in the symmetric group S_{n} acts on a polynomial f ∈ V (μ) via the “diagonal action”

(25)  σf(x_{1}, …, x_{n}, y_{1}, …, y_{n}) = f(x_{σ_{1}}, …, x_{σ_{n}}, y_{σ_{1}}, …, y_{σ_{n}}).

Note that V (μ) = ⨁_{i,j≥0} V (μ)^{(i,j)}, where V (μ)^{(i,j)} is the portion of V (μ) of bihomogeneous (x, y)-degree (i, j), and that the diagonal action respects this bigrading.

In 2000 Haiman [Hai01] proved the “n! conjecture”, first posed in [GH93], which says that the dimension of V (μ) equals |μ|!. It had previously been shown [Hai99] that the n! conjecture implies the coefficient of q^{i}t^{j} in K̃_{λ,μ}(q, t) equals the multiplicity of the irreducible S_{n} character χ^{λ} in the character of V (μ)^{(i,j)} under the diagonal action, or equivalently that H̃_{μ}[Z; q, t] equals the image of the character of V (μ) under the Frobenius map which sends χ^{λ} to s_{λ}. Macdonald’s conjecture that K̃_{λ,μ}(q, t) ∈ ℕ[q, t] follows.

The definition of the statistic |Inv(σ, μ)| was motivated by the “dinv” statistic occurring in recent work on the combinatorics of the space DH_{n} of diagonal harmonics [HHL^{+}05b], [HL05]. This space is defined [Hai94] as the linear span over ℚ of the set of all polynomials f(x_{1}, …, x_{n}, y_{1}, …, y_{n}) satisfying

∑_{i=1}^{n} ∂_{x_{i}}^{h} ∂_{y_{i}}^{k} f = 0, ∀h + k > 0. (26)

We can write DH_{n} = ⨁_{i,j≥0} DH_{n}^{(i,j)}, and the diagonal action (25) respects this bigrading. The modules V (μ) are S_{n}-submodules of DH_{n}.

Let ∇ be the linear operator on symmetric functions defined on the H̃_{μ}[Z; q, t] basis via

∇H̃_{μ}[Z; q, t] = t^{n(μ)}q^{n(μ′)}H̃_{μ}[Z; q, t]. (27)

Another famous result of Haiman [Hai02] is that the bigraded character of DH_{n} under the diagonal action is given by ∇e_{n}, where e_{n} is the nth elementary symmetric function. This was first conjectured by Garsia and Haiman in the early 1990’s, who made a special study of < ∇e_{n}, s_{1^{n}} >, the coefficient of s_{1^{n}} in the expansion of ∇e_{n} into Schur functions. They called < ∇e_{n}, s_{1^{n}} > the “q, t-Catalan sequence”, denoted C_{n}(q, t), since they were able to prove that C_{n}(1, 1) = \binom{2n}{n}/(n + 1), the nth Catalan number. As in the case of K̃_{λ,μ}(q, t), all one can infer from its definition is that C_{n}(q, t) is a complicated sum of rational functions in q, t.

A Dyck path is a lattice path, consisting of north (0, 1) and east (1, 0) steps, starting at (0, 0) and ending at (n, n), which never goes below the diagonal x = y. The first major step in the path to the Macdonald polynomial statistics was made in 2000, when Haglund discovered empirically that C_{n}(q, t) appeared to be expressible as the sum of q^{area}t^{bounce} over Dyck paths, for combinatorial statistics area, bounce [Hag03]. Shortly after, this conjecture was independently discovered by Haiman in the following form, which is more convenient for generalization.

(28) C_{n}(q, t) = ∑_{D} q^{dinv(D)}t^{area(D)}.

Here area(D) is the number of complete squares below D but strictly above y = x. We let a_{i} = a_{i}(D) denote the number of these squares in the ith row, from the bottom of the square n × n grid, and define dinv(D), the number of “diagonal” inversions of D, as the number of pairs (i, j) with

1 ≤ i < j ≤ n and a_{i} = a_{j} or a_{i} = a_{j} + 1. (29)

For example, for the path in Figure 3 (ignore the numbers in the grid for the moment), we have area = 9, dinv = 13.

The Haglund-Haiman conjecture for C_{n}(q, t) was proved shortly after by Garsia and Haglund [GH01], [GH02], by a complicated application of plethystic symmetric function identities previously developed by Garsia, Bergeron and others through a series of papers [GT96], [BGHT99], [GHT99]. More recently Haglund [Hag04b] used the same techniques to prove a more general result conjectured by Egge, Haglund, Kremer and Killpatrick [EHKK03] giving the coefficient of an arbitrary hook shape in ∇e_{n} in terms of statistics on lattice paths with diagonal (1, 1) steps also allowed (known as Schröder paths).

A consequence of Haiman’s formula for the character of DH_{n} is the fact that the dimension of DH_{n}, as a ℚ-vector space, is (n + 1)^{n−1}. This number is wellknown to equal the number of parking functions on n cars, which can be represented geometrically by starting with a Dyck path D, then placing the numbers 1 through n immediately to the right of the North steps of D, with strict decrease down columns. Shortly after the proof of the combinatorial formula for C_{n}(q, t), Haglund and Loehr [HL05] conjectured that the Hilbert series of DH_{n} equals the sum of q^{dinv(P)}t^{area(P)} over all parking functions on n cars. Here the statistic area(P) is simply area(D) for the underlying Dyck path D. If we refer to the number j as car_{j}, then dinv(P) is the number of pairs (i, j) which satisfy the conditions (29), and in addition, if a_{i} = a_{j}, then the car in the jth row is larger than the car in the ith row, while if a_{i} = a_{j} + 1, then the car in the jth row is smaller than the car in the ith row. The Haglund–Loehr conjecture is still open.

The research into the combinatorics of DH_{n} culminated with the discovery of the “shuffle conjecture” about two years ago by Haglund et al. [HHL^{+}05b]. This gives a formula for ∇e_{n} in terms of statistics on “word parking functions”, which are placements of positive integers in the columns as before, but we allow repeats (but still require strict decrease down columns, and require cars to be no larger than n). A given object P of this type is weighted by z^{P} q^{dinv(P)}t^{area(P)}, where area(P) is again the area of the underlying Dyck path. The description of dinv(P) involves the diagonal reading word σ = σ(P) of P, which is obtained by reading in the cars along diagonals (lines parallel to y = x), outside to in and top to bottom. Next standardize σ as in Remark 1, regard σ′ as the reading word of some P′, then set dinv(P) = dinv(P′). For example, if P is the word parking function in Figure 3, we have σ = 64641532, σ′ = 74851632, area = 9, and dinv = 6, with inversion “pairs” (i, j) of rows equal to (3, 8), (4, 8), (1, 7), (2, 7), (5, 6) and (3, 4) each contributing 1 to dinv. Also, z^{P} is defined as z^{σ}.

Figure 3. A word parking function with the a_{i} on the right

Conjecture 1 (The shuffle conjecture - [HHL^{+}05b]).

(30) ∇e_{n} = ∑_{P} z^{P} q^{dinv(P)}t^{area(P)},

where the sum is over all word parking functions P with n cars.

An equivalent formulation of the conjecture is that the coefficient of the monomial z_{1}^{λ_{1}}z_{2}^{λ_{2}} ⋯ in ∇e_{n} equals the sum of q^{dinv}t^{area} over all parking functions whose diagonal reading word is a shuffle of increasing sequences of lengths λ_{1}, λ_{2}, …, hence the phrase “shuffle conjecture”. As is well known, the Hilbert series is the coefficient of z_{1} ⋯ z_{n} in the expansion of the character into monomials, hence the shuffle conjecture contains Haglund and Loehr’s conjectured formula for the Hilbert series of DH_{n} as a special case. In [HL05] it is shown that it also implies the formula for C_{n}(q, t), as well as the formula for hook shapes in terms of Schröder paths.

6. The Empirical Method

Recall that H̃_{μ}[Z; q, t] is the character of the S_{n} module V (μ), which is a submodule of DH_{n}. Thus we could hope that some version of the shuffle conjecture would hold for H̃_{μ}[Z; q, t]. Furthermore, since the statistics in the shuffle conjecture are defined solely in terms of the statistics for the Hilbert series of DH_{n}, together with the simple operation of standardization, we could hope that discovering statistics for the Hilbert series of V (μ) would result in a combinatorial formula for the monomial expansion of H̃_{μ}[Z; q, t] through a similar standardization process.

Let Hilb_{μ}(q, t) denote the bigraded Hilbert series of V (μ). The problem of finding a combinatorial description of Hilb_{μ}(q, t) was studied by Garsia and Haiman, who obtained statistics when μ has two rows or is a hook shape [GH95]. The author had also made some previous unsuccessful attempts at this problem, but the reasoning in the above paragraph increased the stakes dramatically, and so the author decided to give a more determined attack on the problem.

Since the dimension of V (μ) is n!, it is natural to view the problem in terms of searching for a pair of permutation statistics, which depend on μ, to generate Hilb_{μ}(q, t). Since μ has n squares, permutations are in bijection with fillings of μ by distinct integers, and furthermore from a result of Macdonald [Mac95, p.365,Ex.6] one can easily deduce that

Hilb_{μ}(1, t) = ∑_{σ∈S_{n}} t^{maj(σ,μ)}. (31)

We now assume that there exists some q-statistic to match with this maj t-statistic, and try to find it.

For a given Dyck path D, let t^{area(D)}F_{D}(Z; q) denote the restriction of the sum on the right-hand-side of (30) to those word parking functions for D. It is proved in [HHL^{+}05b] that F_{D}(Z; q) is a symmetric function, and moreover is a constant power of q times an LLT polynomial (as described in [HHL^{+}05b], LLT polynomials can be parameterized by tuples of skew shapes; in the case of the F_{D} the elements of the tuple are vertical columns associated with the lengths of the vertical segments of D). Let μ be a partition, and abbreviate μ_{1} by ℓ. While working with the F_{D}, the author proved that if D = D(μ) is the special type of path consisting of μ′_{ℓ} vertical steps, followed by μ′_{ℓ} horizontal steps, followed by μ′_{ℓ−1} vertical steps, followed by μ′_{ℓ−1} horizontal steps, etc., then

F_{D(μ)}(Z; q) = q^{n(μ)} ∑_{λ⊢n} s_{λ}K_{λ′,μ′}(q), (32)

where K_{λ,μ}(q) = q^{n(μ)}K̃_{λ,μ}(q^{−1}) is the charge version of the polynomial from Section 4. This can be proved from recurrences for the F_{D(μ)}, obtained by placing the largest car n at the top of columns, then showing these recurrences are equivalent to those obtained by Garsia and Procesi [GP92] for the Hall-Littlewood polynomials. (This fact also follows from statements in [SSW03], where it is deduced from recurrences of this type for general LLT polynomials).

Since

H̃_{μ}[Z; 0, q] = ∑_{λ} s_{λ}K̃_{λ,μ}(q), (33)

and since by (32) the monomial expansion of

∑_{λ⊢n} s_{λ}K_{λ′,μ′}(q) (34)

can be obtained by summing q^{−n(μ)+dinv(T)}z^{T} over word parking functions for D(μ), one could hope that the power of q to insert into (31) involves dinv in some way. A parking function σ for D(μ) can be transformed into a filling σ of μ by pushing all squares in the ith column from the left down i−1 squares, removing all empty columns, and finally rotating 180 degrees, as in Figure 4. Furthermore this sends dinv(σ) to |Inv(σ, μ)|. Note that area gets sent to maj, since we have descents everywhere. We are thus led to

∑_{σ∈S_{n}} t^{maj(σ,μ)}q^{−n(μ)+|Inv(σ,μ)|} (35)

as a candidate for the Hilb_{μ}(q, t).

Figure 4. Transforming a parking function into a filling

Maple computations verified that (35) correctly predicts the coefficient of t^{n(μ)} (the highest power of t) in Hilb_{μ}(q, t), and that the coefficient of t^{0} would be correct if we didn’t have the −n(μ) in the q-power. This led to the hypothesis that |Inv(σ, μ)| formed an upper bound for the correct q-statistic, and that the key was to find the right thing to subtract from it, something possibly depending on the descent set. The final stage involved a series of Maple calculations, each testing a different idea for something to subtract. Many things worked up through n = 4 and for various special cases like μ = 2, 1, 1, 1, ..., but continually failed for n = 5. Here is a sample of the author’s daily journal summarizing the experiments;

Journal entry:

On 3/29/04, ran pistolbad.map, which computes inversion in columns for tstat and dinv minus mindinv for qstat. Bombs for μ = [2, 2, 1]. See bomb.out. Tried a modification, where comaj of the columns replaced the tstat, same qstat. This also bombed in general, but surprisingly works for μ = 221, μ = 222, μ = 2221, and μ = 2222. Bombs for μ = 2211 though.

Journal Entry:

On 4/2/04 ran pistolbbad.map, which computes inversions in columns for tstat and dinv minus mindinv for qstat, where mindinv is defined as the sum over all descents, of the number of entries to the left of the top element of the decent pair. Seems to work for μ having two rows, but bombs for μ = 2, 2, 1.

At this point the author planned to drop the problem, and return to less speculative projects. The idea of subtracting the arm of each descent occurred to him, however, and he decided to run one last experiment, which successfully generated Hilb_{μ}(q, t) for all |μ| ≤ 8. A subsequent calculation a few days later extended this to |μ| ≤ 9, and moreover verified that applying the Hilbert series statistics to the standardization of words generated the entire monomial expansion of the H̃_{μ}[Z; q, t]. In a phone conversation a few months later after the conjecture was made public A. Garsia told the author “You found water on Mars”.

Journal Entry:

Also on 4/2/04, ran pistolb.map, which computes maj on columns for tstat, and uses mindinv as described in paragraph just above. Surprisingly, works for all μ with |μ| <= 8! The run for n = 9 took over a week, but finally finished successfully.

Journal Entry:

On 4/6/04 ran program pistolc.map, which computes the Macdonald poly from shuffles using the Hilbert series inv and maj stats. Correctly generates the Macdonald poly H̃_{μ} for all μ with |μ| ≤ 8! From 4/7 thru 4/16 ran tempc.map, which extends this computation through n = 9.

References

[BGHT99] F. Bergeron, A. M. Garsia, M. Haiman, and G. Tesler. Identities and positivity conjectures for some remarkable operators in the theory of symmetric functions. Methods Appl. Anal., 6:363–420, 1999.

[EHKK03] E. Egge, J. Haglund, K. Killpatrick, and D. Kremer. A Schröder generalization of Haglund’s statistic on Catalan paths. Electron. J. Combin., 10:Research Paper 16, 21 pp. (electronic), 2003.

[GH93] A. M. Garsia and M. Haiman. A graded representation model for Macdonald polynomials. Proc. Nat. Acad. Sci. U.S.A., 90(8):3607–3610, 1993.

[GH95] A. M. Garsia and M. Haiman. Factorizations of Pieri rules for Macdonald polynomials. Discrete Math., 139(1-3):219–256, 1995. Formal power series and algebraic combinatorics (Montreal, PQ, 1992).

[GH96] A. M. Garsia and M. Haiman. A remarkable q, t-Catalan sequence and q-Lagrange inversion. J. Algebraic Combin., 5(3):191–244, 1996.

[GH01] A. M. Garsia and J. Haglund. A positivity result in the theory of Macdonald polynomials. Proc. Nat. Acad. Sci. U.S.A., 98:4313–4316, 2001.

[GH02] A. M. Garsia and J. Haglund. A proof of the q, t-Catalan positivity conjecture. Discrete Math., 256:677–717, 2002.

[GHT99] A. M. Garsia, M. Haiman, and G. Tesler. Explicit plethystic formulas for Macdonald q, t-Kostka coefficients. Sém. Lothar. Combin., 42:Art. B42m, 45 pp. (electronic), 1999. The Andrews Festschrift (Maratea, 1998).

[GP92] A. M. Garsia and C. Procesi. On certain graded S_{n}-modules and the q-Kostka polynomials. Adv. Math., 94(1):82–138, 1992.

[GT96] A. M. Garsia and G. Tesler. Plethystic formulas for Macdonald q, t-Kostka coefficients. Adv. Math., 123:144–222, 1996.

[Hag03] J. Haglund. Conjectured statistics for the q, t-Catalan numbers. Adv. Math., 175(2):319– 334, 2003.

[Hag04a] J. Haglund. A combinatorial model for the Macdonald polynomials. Proc. Nat. Acad. Sci. U.S.A., 101:16127–16131, 2004.

[Hag04b] J. Haglund. A proof of the q, t-Schröder conjecture. Internat. Math. Res. Notices, 11:525–560, 2004.

[Hai94] M. Haiman. Conjectures on the quotient ring by diagonal invariants. J. Algebraic Combin., 3:17–76, 1994.

[Hai99] M. Haiman. Macdonald polynomials and geometry. In New perspectives in algebraic combinatorics (Berkeley, CA, 1996–97), volume 38 of Math. Sci. Res. Inst. Publ., pages 207–254. Cambridge Univ. Press, Cambridge, 1999.

[Hai01] M. Haiman. Hilbert schemes, polygraphs, and the Macdonald positivity conjecture. J. Amer. Math. Soc., 14:941–1006, 2001.

[Hai02] M. Haiman. Vanishing theorems and character formulas for the Hilbert scheme of points in the plane. Invent. Math., 149:371–407, 2002.

[Hai03] Mark Haiman. Combinatorics, symmetric functions, and Hilbert schemes. In Current developments in mathematics, 2002, pages 39–111. Int. Press, Somerville, MA, 2003.

[HHL05a] J. Haglund, M. Haiman, and N. Loehr. A combinatorial formula for Macdonald polynomials. J. Amer. Math. Soc., 18:735–761, 2005.

[HHL^{+}05b] J. Haglund, M. Haiman, N. Loehr, J. B. Remmel, and A. Ulyanov. A combinatorial formula for the character of the diagonal coinvariants. Duke J. Math., 126:195–232, 2005.

[HL05] J. Haglund and N. Loehr. A conjectured combinatorial formula for the Hilbert series for Diagonal Harmonics. Discrete Math. (Proceedings of the FPSAC 2002 Conference held in Melbourne, Australia), 298:189–204, 2005.

[KS97] Friedrich Knop and Siddhartha Sahi. A recursion and a combinatorial formula for Jack polynomials. Invent. Math., 128(1):9–22, 1997.

[LLT97] Alain Lascoux, Bernard Leclerc, and Jean-Yves Thibon. Ribbon tableaux, Hall-Littlewood functions, quantum affine algebras, and unipotent varieties. J. Math. Phys., 38(2):1041–1068, 1997.

[Mac95] I. G. Macdonald. Symmetric Functions and Hall Polynomials. Oxford Mathematical Monographs, second ed., Oxford Science Publications. The Clarendon Press Oxford University Press, New York, 1995.

[Man01] Laurent Manivel. Symmetric functions, Schubert polynomials and degeneracy loci, volume 6 of SMF/AMS Texts and Monographs. American Mathematical Society, Providence, RI, 2001. Translated from the 1998 French original by John R. Swallow, Cours Spécialisés [Specialized Courses], 3.

[SSW03] A. Schilling, M. Shimozono, and D. E. White. Branching formula for q-Littlewood-Richardson coefficients. Adv. in Appl. Math., 30(1-2):258–272, 2003. Formal power series and algebraic combinatorics (Scottsdale, AZ, 2001).

[Sta99] R. P. Stanley. Enumerative Combinatorics, volume 2. Cambridge University Press, Cambridge, United Kingdom, 1999.