Combinatorial theory of Macdonald polynomials I: Proof of Haglund's formula

Background in Algebraic Combinatorics

We begin by reviewing some standard material concerning partitions, tableaux, and symmetric functions; more details may be found in ref. 10. Throughout this whole discussion, let n and N ≥ n be fixed positive integers, and let z ₁,..., z_N be independent indeterminates. (By taking suitable inverse limits, we can allow N = ∞ as well.)

Partitions. A “partition” of n is a weakly decreasing sequence μ = (μ₁ ≥ μ₂ ≥ ··· ≥ μ_s) of positive integers such that μ₁ + ··· + μ_s = n. In this situation, we write |μ| = n, μ ⊢ n, l (μ) = s, μ_i = 0 for , and . The “diagram” of μ, which we also denote by μ, is the set of “cells” . We lexicographically order the cells in by setting (x, y) <_lex (u, v) if and only if (iff) y > v or y = v and x < u. For any c = (x ₀, y ₀) in the diagram of μ, we define the “arm” a(c) = |{(x, y ₀) ∈ μ: x > x ₀}| and the “leg” l(c) = |{(x ₀, y) ∈ μ: y > y ₀}|.

Pictorially, we represent the cell c = (x, y) as a unit square the upper-right corner of which is located at (x, y). Then the diagram of μ consists of l(μ) rows of squares in the first quadrant of the xy plane, left-justified, with μ_i squares in the ith row from the bottom. For any square c, a(c) is the number of squares strictly to the right of c in μ, and l(c) is the number of squares strictly above c in μ.

The “transpose” of μ, denoted μ′, is the partition with diagram {(y, x): (x, y) ∈ μ}. Geometrically, the diagram of μ′ is the reflection of the diagram of μ about the line y = x. For λ, μ ⊢ n, we write λ ≤ μ iff λ₁ + ··· + λ_i ≤ μ₁ + ··· + μ_i for all i. This gives the “dominance” partial ordering on the set of partitions of n.

Fillings and Tableaux. For all m > 0, we define “alphabets” . For μ ⊢ n, a “filling” of the diagram μ with entries in an alphabet A is a function T: μ → A. A “standard filling” is a bijection . For any filling T, we set T(x, y) = 0 whenever (x, y) is not in the diagram of μ. We also define z_T =∏_{c ∈μ} z _{| T ( c )|}, N(T) = |T ^–1({i ∈ A: i < 0})|, and P(T) = |T ^–1 ({i ∈ A: i > 0})|.

Given any total ordering ≺ on some alphabet A, a semistandard tableau of shape μ relative to ≺ is a filling Q: μ → A such that: x < x′ implies Q(x, y) ⪯ Q(x′, y) for all y such that (x, y), (x′, y) ∈ μ; and y < y′ implies Q(x, y) ⪯ Q(x, y′) for all x such that (x, y), (x, y′) ∈ μ. We let SSYT_≺(μ) denote the set of such tableaux; let SSYT_≺(μ, ν) = {Q ∈ SSYT_≺(μ): z_Q = z ^ν}. Also, define the “standard tableaux” SYT(μ) to be the set of standard fillings S: μ → A ⁺ _n in SSYT_<(μ), where < is the usual total ordering on A ⁺ _n.

Pictorially, a filling T of μ is obtained by putting the letter T(x, y) ∈ A in each square (x, y) of the diagram of μ. T is a standard filling iff it uses the letters 1,..., n exactly once each. The monomial z_T records which letters appear in T, disregarding signs; N(T) is the number of negative letters used; and P(T) is the number of positive letters used. In a semistandard tableau Q, letters weakly increase in each row and strictly increase in each column (relative to the given ordering ≺). A standard tableau is a semistandard tableau (relative to <) in which the letters 1,..., n are used once each.

Words. A “word” in an alphabet A is a sequence of letters w = w ₁ w ₂ ··· w_m, where each w_i ∈ A. We can identify this word with a filling w: (m) → A in the obvious way. Define as before. A word w on A ⁺ _N has “partition content” iffz_w = z ^μ for some μ ⊢ n; if μ = (1ⁿ), the word w is a “permutation.” Given μ ⊢ n, let c ₁,..., c_n be the cells of μ in lex order. For a filling T: μ → A, define the “reading word” of T to be the word w(T) = T(c ₁) ··· T(c_n), i.e., the word obtained by reading the elements in the rows of T from left to right, visiting the rows from top to bottom.

Suppose (A, <) and (B, ≺) are two totally ordered alphabets. Also suppose that v is a word of length m in A, w is a word of length m in B such that w ₁ ⪯ ··· ⪯ w_m, and w_i = w_{i +1} implies v_i ≤ v_{i +1}. The Robinson-Schensted-Knuth (RSK) algorithm gives a bijection from the set of such pairs (v, w) onto the set of pairs (P, Q), where P ∈ SSYT_<(μ) and Q ∈ SSYT_≺(μ) for some μ ⊢ m. P is called the “insertion tableau” for (v, w), and Q is called the “recording tableau.” We have z_P = z_v and z_Q = z_w. See ref. 11 for more details.

Standardization. Let (A, ≺) be a totally ordered alphabet, and let T: μ → A be a filling of μ ⊢ n. We define a standard filling S = std(T, ≺) called the “standardization of T relative to ≺.” Formally, S: μ → A ⁺ _n is the unique standard filling such that: T(c) ≺ T(d) implies S(c) < S(d); T(c) = T(d) > 0 and c <_lex d implies S(c) < S(d); and T(c) = T(d) < 0 and c <_lex d implies S(c) > S(d). Informally, we obtain S from T by relabeling the cells of T with the numbers 1,..., n, such that: earlier symbols in the ordering ≺ get relabeled first; cells containing equal positive symbols get relabeled in lex order; and cells containing equal negative symbols get relabeled in reverse lex order. See Fig. 2 for examples of standardization relative to the orderings <₁ and <₂ defined below. In Fig. 2, we denote –a by ā for clarity.

If w is a permutation of n letters, we define D(w) to be the set of a ∈ {1, 2,..., n – 1} such that a + 1 occurs earlier than a in w. If S is a standard filling with reading word w(S), we define D(S) = D(w(S)). If T: μ → A is a filling and ≺ is a total ordering of A, we define D _≺(T) = D(std(T, ≺)).

Symmetric Functions. Let F be the field . We consider homogeneous polynomials of degree n in the variables z ₁,..., z_N with coefficients in F. Such a polynomial is “symmetric” iff it is unchanged under any permutation of the variables z ₁,..., z_N; let denote the set of symmetric polynomials. Important examples of symmetric functions are the “power sums” p_k, the “elementary symmetric functions” e_k, and the “complete homogeneous symmetric functions” h_k, defined by is an F-vector space with bases that are indexed by partitions of n. There are five classical bases for (10).

1. Monomial basis. For μ ⊢ n, let m _μ be the sum of all distinct monomials in z ₁,..., z_N that can be obtained by permuting the subscripts of the monomial . It is clear that {m _μ: μ ⊢ n} is an independent set spanning .

2. Power-sum basis. For μ ⊢ n, let . Then {p _μ: μ ⊢ n} is a basis for .

3. Elementary basis. For μ ⊢ n, let . Then {e _μ: μ ⊢ n} is a basis for .

4. Homogeneous basis. For μ ⊢ n, let . Then {h _μ: μ ⊢ n} is a basis for .

5. Schur basis. Let ≺ be any total ordering of the alphabet . Define the “Schur function” s _μ = ∑_{T ∈SSYT} (μ)z_T. It can be shown that: s _μ does lie in ; the element s _μ is independent of the total ordering ≺ on ; and {s _μ: μ ⊢ n} is a basis for .

The “Hall scalar product” 〈·, ·〉 is defined on by requiring that the Schur basis be orthonormal. For any u ∈ F, we define a linear map A_u on by setting and extending by linearity. The maps A_u form a commuting family of linear operators on , which are invertible for u ≠ 1. The classical map ω, which sends p _μ to .

Quasisymmetric Functions. For each subset I ⊆ {1, 2,..., n – 1}, define Gessel's “fundamental quasisymmetric function” by.It can be shown that these 2^{n –1} polynomials are linearly independent. Let denote the vector space spanned by the elements Q _n,I. Then is a subspace of .

Suppose μ ⊢ n, S ∈ SYT(μ), and < is the standard total ordering of . From the definition of standardization, one sees easily that.Adding over all standard tableaux S, we obtain the expansion

Macdonald Polynomials

We now introduce several versions of the Macdonald polynomials (10, 12, 13), beginning with the “modified Macdonald polynomials” H̃ _μ = H̃ _μ[z ₁,..., z_N; q, t].

Theorem 1. There exists a unique basis {H̃ _μ: μ ⊢ n} for satisfying the following axioms:

1. (M1) ω(A_q(H̃ _μ)) = ∑_λ≥μ a _μ,λ s _λ for some a _μ,λ ∈ F.

   (M2) ω(A_t(H̃)) = ∑_λ≥μ′ b _μ,λ s _λ for some b _μ,λ ∈ F.

2. (M3) 〈H̃ _μ, s _{( n )}〉 = 1.

Our main result is a constructive combinatorial proof of the existence assertion in Theorem 1. The uniqueness assertion is much easier to prove. Suppose the basis {G _μ: μ ⊢ n} also satisfies the three axioms. Consider column vectors G = (G _μ)_{μ⊢ n}, H = (H̃ _μ)_{μ⊢ n}, S_q = ((ωA_q)^–1(s _μ))_{μ⊢ n}, and S_t = ((ωA_t)^–1(s _μ′))_{μ⊢ n}. Axiom M1 says that H = X′S_q and G = X″S_q for some invertible upper-triangular matrices X′, X″; hence, G = X H for some upper-triangular matrix X. Similarly, axiom M2 says that G = Y H for some lower-triangular matrix Y. Because {G _μ} and {H̃ _μ} are bases, we must have X = Y, so that X is a diagonal matrix. Axiom M3 now shows that X is the identity matrix, and G = H. For example, take G _μ = H̃ _μ′[z ₁,..., z_N; t, q]. The family {G _μ: μ ⊢ n} clearly satisfies M1–M3, so uniqueness gives the “symmetry” propertyHere is the outline of our proof of the existence of H̃ _μ.

1. We rewrite the axioms M1–M3 in the following simpler form:

   1. (A1) A_q(H̃ _μ) = ∑_λ≤μ′ c _μ,λ m _λ for some c _μ,λ ∈ F.

   2. (A2) A_t(H̃ _μ) = ∑_λ≤μ d _μ,λ m _λ for some d _μ,λ ∈ F.

   3. (A3) The coefficient of zⁿ ₁ in H̃ _μ is 1.

   The equivalence of the two sets of axioms easily follows from these facts: μ ≤ ν iff ν′ ≤ μ′; ω(s _μ) = s _μ′; and the monomial and Schur bases are related by the triangular Kostka matrix.

2. We recall Haglund's definition of the “combinatorial Macdonald polynomials” , which are sums of weighted objects depending on μ. It will be clear that axiom A3 holds for C _μ.

3. We prove that , i.e., that these polynomials are symmetric.

4. We use quasisymmetric functions to find combinatorial interpretations for A_q(C _μ) and A_t(C _μ) as sums of signed, weighted objects.

5. We construct sign-reversing involutions to verify axioms A1 and A2 for C _μ. Because {H̃ _μ : μ ⊢ n} are the unique elements of satisfying A1–A3, it follows that C _μ = H̃ _μ.

Once we have constructed the modified Macdonald polynomials H̃ _μ = H̃ _μ[z ₁,..., z_N; q, t], we can define the “integral Macdonald polynomials” J _μ, the “dual Macdonald polynomials” Q _μ, and the “original Macdonald polynomials” P _μ by setting We remark that P _μ has the following specializations: when q = t, P _μ reduces to s _μ; when t → 1, P _μ reduces to m _μ; when q → 1, P _μ reduces to e _μ′; when q → 0, P _μ reduces to a Hall–Littlewood polynomial; and when q = t ^α and then t → 1, P _μ reduces to Jack's symmetric polynomial. In turn, Jack's polynomials reduce to zonal spherical functions when α = 1/2 and to zonal symmetric polynomials when α = 2.

We will use the identity c _μ = H̃ _μ to give combinatorial formulas for the bases J _μ, Q _μ, and P _μ. One of our formulas for J _μ specializes to a formula of Sahi and Knop for Jack polynomials. As additional applications of our combinatorial formulas, we sketch derivations of one of Macdonald's specializations for H̃ _μ, Lascoux and Schützenberger's cocharge formula for Hall–Littlewood polynomials, and interpretations for certain Kostka–Macdonald coefficients.

Haglund's Combinatorial Polynomials

Fix μ ⊢ n. An ordered pair of cells ((x, y), (u, v)) in μ is an “attacking pair” iff y = v and x < μ, or y = v + 1 and u < x. For a cell (x, y) ∈ μ, we let d(x, y) = (x, y – 1) be the cell directly below it, which does not lie in μ if y = 1. A “special triple” of μ consists of three cells (c ₁, c ₂, c ₃) with c ₁ = (x, y) ∈ μ, c ₂ = (x, y – 1) = d(x, y), and c ₃ = (z, y) ∈ μ for some z > x and some y ≥ 1.

Let S be a standard filling. A “descent” of S is a cell (x, y) ∈ μ such that y > 1 and S(x, y) > S(x, y – 1). The set of all such cells is the “descent set” of S, denoted Des(S). The “major index” of S is maj(S) = ∑_{c ∈Des( S )}(l(c) + 1). An “inversion pair” of S is an attacking pair ((x, y), (u, v)) such that S(x, y) > S(u, v); let Inv(S) be the set of such pairs. An “inversion triple” of S is a special triple (c ₁, c ₂, c ₃) with S(c ₁) < S(c ₂) < S(c ₃) or S(c ₂) < S(c ₃) < S(c ₁) or S(c ₃) < S(c ₁) < S(c ₂); let Trip(S) be the set of such triples. The “inversion statistic” for S is inv(S) = |Inv(S)| – ∑_{c ∈Des( S )} a(c). An easy case analysis shows that inv(S) = |Trip(S)|. For any totally ordered alphabet (A, ≺) and any filling T: μ → A, we set inv ≺(T) = inv(std(T, ≺)) and maj_≺(T) = maj(std(T, ≺)).

Haglund defined the combinatorial Macdonald polynomials (9) by settingwhere < is the usual ordering on . For each μ, there is exactly one positive filling T on μ with z_T = zⁿ ₁, and inv_<(T) = 0 = maj_<(T) for this T. Therefore, axiom A3 holds for C _μ. Moreover, by using the definition of standardization, it is easy to see that. Fig. 1 shows the objects used to calculate C _(2,1). We have

Symmetry of C_μ

Lascoux et al. (14) introduced a class of symmetric polynomials commonly known as Lascoux–Leclerc–Thibon (LLT) polynomials. One way to show that is to write C _μ as a weighted sum of LLT polynomials. For μ ⊢ n and D ⊆ μ, setWe clearly have C _μ = ∑_{D ⊆μ} C _{μ, D} ∏_{c ∈ D} t^{l (c)+1} q ^–a(c), so it suffices to prove that each C _{μ, D} is a symmetric polynomial. Using corollary 5.2.4 of ref. 15, it is easily shown that C _{μ, D} is an LLT polynomial indexed by a tuple of ribbons the sizes of which are the parts of μ′ and the shapes of which are determined by D. Because LLT polynomials are known to be symmetric, it follows that each , and so .

We now sketch an alternative, elementary proof that . If m ≥ 0 and S is a subset of {(i, j): 1 ≤ i < j ≤ m}, we say that S has the “connectivity property” iff for all i, j, k with i < j < k, (i, k) ∈ S implies (i, j) ∈ S and (j, k) ∈ S. Let W_m = {1, 2}^m for m ≥ 0. For each w ∈ W_m, define inv_S(w) = |{(i, j): (i, j) ∈ S and w_i > w_j}|. For any set Z ⊆ W_m, let

Lemma 1. For all m ≥ 0, G_{S , Wm}(z ₁, z ₂; q) = G_{S , Wm}(z ₂, z ₁; q).

Proof: We use induction on m, the cases m ≤ 1 being easy. Assume m > 1 and Lemma 1 holds for all m′ < m. Consider the set of integers j such that (j, m) ∈ S. If this set is empty, then inv_S(w) does not depend on w_m, and henceBy induction, the right side is symmetric in z ₁ and z ₂.

Otherwise, choose j minimal with (j, m) ∈ S. Now we prove the result for m by induction on |S|, the case |S| = 0 being easy. The idea is to compare G_{S , Wm} and G_{S ′, Wm}, where S′ = S – {(j, m)}. Note that |S′| < |S| and S′ satisfies the connectivity condition. Let B = {w ∈ W_m: w_j = 2 and w_m = 1}, and let A = W_m – B. Let S″ be obtained from S by deleting all pairs involving j or m and subtracting one from all indices exceeding j; S″ satisfies the connectivity property. One must now verify the following equations: Here, Eqs. 7 and 8 are clear, and Eq. 9 follows because inv_S(w) = inv_{S ′}(w) for all w ∈ A. To prove Eq. 10, consider the bijection φ: B → W_{m –2} that deletes w_j = 2 and w_m = 1 from each w ∈ B. It suffices to show that inv_S(w) = inv_{S ″}(φ(w)) + m – j for w ∈ B. For every k with j < k < m, the pairs (j, k) and (k, m) are both in S by connectivity. Exactly one of these contributes to inv_S(w), depending on whether w_k = 1 or w_k = 2. Moreover, the pair (j, m) ∈ S contributes an inversion. No other pair involving j or m contributes to inv_S(w), by minimality of j. It follows easily that inv_S(w) exceeds inv_{S ″}(φ(w)) by exactly m – j. Eq. 11 is proved in the same way, noting that (j, m) ∉ S′. Finally, Eq. 12 follows from the preceding five relations. By induction on m and |S|, the right side of Eq. 12 is symmetric in z ₁ and z ₂, completing the proof.

Now we prove symmetry of C _{μ, D}. For D ⊆ μ, let C _{μ,≥ D} = ∑_{E : D ⊆ E ⊆μ} C _{μ, E}. First, it suffices to show that C _{μ,≥ D} is symmetric for all D. Second, it suffices to show that C _{μ,≥ D} is unchanged when z_i and z_{i +1} are interchanged. Third, suppose we are given a fixed decomposition of the diagram of μ into disjoint sets A, B, and a fixed partial filling T ₀: B → {1,..., N} – {i, i + 1}. Consider the set Z of fillings T of μ with Des(T) ⊇ D, T|B = T ₀, and T ^–1({i, i + 1}) = A. It suffices to show that ∑_{T ∈ Z} q ^inv(T) _zT is symmetric in z_i and z_{i +1}, because C _{μ,≥ D} is a sum of such expressions. Let A ₁ = {c: c ∈ A ∩ D and d(c) ∈ A}, A ₂ = d(A ₁), and A ₃ = A – (A ₁ ∪ A ₂). One checks that, if Z is nonempty,Hence, we can identify T ∈ Z with the word w_T ∈ {i, i + 1}^|A₃| that lists the entries of the cells in A ₃ in lex order. Change notation so that w_T ∈ {1, 2}^|A₃|. For T ∈ Z, one checks that there exists a set S satisfying the connectivity property and a constant j ₀ (which depend on T ₀, D, A, and B but not on T|A ₃) such that inv(T) = j ₀ + inv_S(w_T). It readily follows that

By Lemma 1, this expression is unchanged when z_i and z _{i + 1} are interchanged.

Combinatorial Interpretation for A_u(C_μ)

Let {x_i: i ∈ A_N} be a new set of indeterminates, and let R = F[{x_i: i ∈ A_N}] be the corresponding polynomial ring. Define an F-linear map B: by settingand extending by linearity. Let ≺ be any total ordering of A_N. Define an F-linear map B _≺: Qⁿ_F → R by settingand extending by linearity.

It can be shown, by using the Pieri rules and the expansion (Eq. 1) of Schur functions in terms of quasisymmetric functions, that B(s _μ) = B _≺(s _μ) for all μ. Because these two linear maps agree on a basis of , we see that for any ordering ≺ on A_N.

Now, given u ∈ F, consider the evaluation homomorphism e: R → F[z ₁,..., z_N] sending x_i to uz_i for i > 0 and sending x_i to –z _|i| for i < 0. Clearly, e ○ B is the restriction to of every map e ○ B _≺. On one hand, we see that e ○ B = A_u by evaluating each side on p _μ. On the other hand,Using the fact that , the same standardization argument used to prove Eq. 1 establishes the following theorem: for any total ordering ≺ of A_N,

Involutions

For λ, μ ⊢ n, let A _μ,λ be the set of fillings T: μ → A_N such that z_T = z ^λ. We apply Eq. 13 with u = q and ≺ = <₁, where

We conclude that the coefficient of m _λ in A_q(C _μ) isTo verify axiom A1, we define a sign-reversing, weight-preserving involution I: A _μ,λ → A _μ,λ such that I has no fixed points unless λ ⪯ μ′.

Let T ∈ A _μ,λ. To compute IT, consider the set of all attacking pairs of cells (c, d) in μ such that |T(c)| = |T(d)|. If this set is empty, then T is a fixed point of I; we call such fillings T “nonattacking.” Otherwise, choose the attacking pair in this set for which: (i) |T(c)| is minimized; (ii) d is maximal (relative to <_lex) among all attacking pairs satisfying i; and (iii) c is maximal (relative to <_lex) among all attacking pairs satisfying i and ii. Define IT by flipping the sign of the entry in cell c; i.e., IT(c) = –T(c) and IT(e) = T(e) for all e ≠ c. See Fig. 2 for an example.

It is clear that I maps A _μ,λ into itself and that I is an involution. Without loss of generality, assume that T(c) > 0. Write S = std(T, <₁) and IS = std(IT, <₁). One must now check the following statements by using the definitions of I and <₁:(i) N(IT) = N(T) + 1 and P(IT) = P(T) – 1; (ii) Des(IS) = Des(S) and so maj(IS) = maj(S); (iii) Inv(IS) = Inv(S) ∪ {(c,d)}, where (c,d) ∉ Inv(IS); and (iv) inv(IS) = inv(S) + 1. It follows that the summands indexed by T and IT cancel out in Eq. 14.

If c _μ,λ ≠ 0, there must exist an uncancelled summand in Eq. 14, which corresponds to some fixed point T of I. For this T, there are no attacking pairs (c, d) with |T(c)| = |T(d)|. In particular, for each row of T, no two entries in that row have the same absolute value. For each i, we have λ₁ + ··· + λ_i = |T ^–1({±1,..., ±i})| because z_T = z ^λ. On the other hand, adding up the number of entries in each row of T with absolute value at most i, we see thatTherefore, λ ≤ μ′.

Next, we apply Eq. 13 with u = t and ≺ = <₂, whereWe conclude that the coefficient of m _λ in A_t(C _μ) isTo verify axiom A2, we define a sign-reversing, weight-preserving involution J: A _μ,λ → A _μ,λ such that J has no fixed points unless λ ≤ μ.

Let T ∈ A _μ,λ. To compute JT, consider the set of cells (x, y) ∈ μ such that |T(x, y)| < y. If this set is empty, then T is a fixed point of J. Otherwise, choose the cell (x, y) in this set for which: (i) |T(x, y)| is minimized; (ii) y is maximized among all cells satisfying i; and (iii) x is minimized among all cells satisfying i and ii. Define JT by flipping the sign of the entry in cell (x, y); i.e., JT(x, y) = –T(x, y) and JT(c) = T(c) for all c ≠ (x, y). See Fig. 2 for an example.

It is clear that J maps A _μ,λ into itself and that J is an involution. Without loss of generality, assume that T(x, y) > 0. Write S = std(T, <₂) and JS = std(JT, <₂). One must now check the following statements by using the definitions of J and <₂:(i) N(JT) = N(T) + 1 and P(JT) = P(T) – 1; (ii) Trip(JS) = Trip(S) and so inv(JS) = inv(S); (iii) (x, y) ∉ Des(S) and (x, y) ∈ Des(JS); (iv) either (x, y + 1) ∉ μ, or else (x, y + 1) ∈ Des(S) and (x, y + 1) ∉ Des(JS); and (v) maj(JS) = maj(S) + 1. It follows that the summands indexed by T and JT cancel out in Eq. 15.

If d _μ,λ ≠ 0, there must exist an uncancelled summand in Eq. 15, which corresponds to some fixed point T of J. For this T, we must have y ≤ |T(x, y)| for all cells (x, y) ∈ μ. In other words, for j > 0, all occurrences of j or –j in T must appear in the lowest j rows of T. Hence, for any i, all occurrences of ±1,..., ±i in T appear in the lowest i rows of T. Consequently,for all i, where the equality follows because z_T = z ^λ. Therefore, λ ≤ μ.

Other Macdonald Bases

Now we give combinatorial formulas for J _μ, Q _μ, and P _μ. From Eqs. 2 and 13, we deduce thatSimilarly, Eqs. 3 and 13 lead to the formulaBy comparing a filling T to the corresponding positive filling U given by U(c) = |T(c)|, one can show thatThe negative terms in ∏₁ and ∏₂ contribute the necessary extra powers of q and t that arise from making certain entries in U negative. For any cell c, setting T(c) = –U(c) always leads to an extra factor of –t. If c is a cell for which U(c) ≠ U(d(c)), one checks that this is the only extra factor needed, because U is nonattacking. On the other hand, if U(c) = U(d(c)), making U(c) negative causes a new descent at cell c, leading to a further correction factor of q^{l (c)+1} t^{a (c)}.

From any of these formulas for J _μ, we get formulas for Q _μ and P _μ by interpreting the denominators in Eqs. 4 and 5 as geometric series. Explicitly, we haveMoreover, setting q = t ^α in J _μ, dividing by (1 – t)^|μ|, and letting t approach 1, we obtain the integral Jack polynomials. Applying these operations to Eq. 16 and simplifying, we obtain the Sahi–Knop formula (16)

Applications

We now give three more applications of our combinatorial formulas for Macdonald polynomials. These applications all involve the (modified) “Kostka–Macdonald coefficients” K̃ _λ,μ(q, t), which are the unique scalars in satisfying H̃ _μ = ∑_{λ⊢ n}K̃ _λ,μ(q, t)s _λ.

Macdonald's Specialization. Let u be a new indeterminate, and let be the linear map defined on the power-sum basis by . We show that the coefficient of (–u)^d in ε_u(H̃ _μ) isThis result is equivalent to Macdonald's formula VI.8.8 (10) and to the formulagiving the Kostka–Macdonald coefficient when λ is a hook.

Now we sketch the proof of Eq. 17. The same arguments that led to Eq. 13 show thatwhere we use the ordering 1 < –1. To extract the coefficient of (–u)^d, we restrict to fillings T with N(T) = d. Such a filling T is uniquely determined by the d-element subset S′= T ^–1({–1}) of μ. The definitions easily imply thatDefine a bijection φ on the diagram of μ by reversing the order of the cells in row 1 and reversing the order of the cells above the first row in each column. Setting S = φ(S′), one sees thatfrom which Eq. 17 readily follows.

Cocharge Formula for Hall–Littlewood Polynomials. We define “cocharge” first on permutations, then on words with partition content, and finally on semistandard tableaux. If w = w ₁ w ₂ ··· w_n is a permutation, define the cocharge of w by cchg(w) = ∑_{i ∈ D ( w )}(n – i). If w has partition content, we use the following algorithm to compute cocharge. Let l = max_c w_c, and let c ₁ be the largest index such that w_{c 1} = 1. Proceeding inductively, if c_{i –1} has been determined for i < 1, let c_i be the largest index less than c_{i –1} with w_{c i} = i; if there is no such index, let c_i be the largest index with w _ci = i. Let S be the set of cells c ₁,..., c_l. Let y be the subword of w consisting of the letters at the positions in S from left to right, and let z be the complementary subword of w. Then y is a permutation, and z has partition content. Define cocharge recursively by cchg(w) = cchg(y) + cchg(z). Finally, if T ∈ SSYT(λ, μ), define cchg(T) = cchg(w(T)). Given a pair of words (v, w) mapping to (P, Q) under the RSK algorithm, if v has partition content, then cchg(v) = cchg(P). This fact is easily verified using Knuth relations.

The Lascoux and Schützenberger formula for Hall–Littlewood polynomials (17) isWe sketch a combinatorial proof of this formula. Let < be the standard total ordering of , and let ≺ be the reverse of this ordering. Using the definition of C _μ and the formula , it suffices to show thatLet X be the set of pairs (P, Q) with P ∈ SSYT_<(λ, μ) and Q ∈ SSYT_≺(λ) for some λ ⊢ n. Let Y be the set of fillings T: with inv_<(T) = 0. It now suffices to construct a bijection φ: Y → X such that, whenever (P, Q) = φ(T), z_T = z_Q and maj_<(T) = cchg(P). Given T ∈ Y, we compute φ(T) in three steps.

First, map T to the list of triples ((a ₁, x ₁, y ₁),..., (a_n, x_n, y_n)), where (x_i, y_i) ∈ μ, a_i = T(x_i, y_i), a ₁ ≥ ··· ≥ a_n, and a_i = a_{i +1} implies y_i ≤ y_{i +1}. Note that , and the word y ··· y_n has μ_i occurrences of i for all i. Clearly, T can be recovered from the list of triples.

Second, we delete the x coordinates x_i to obtain a list of pairs ((a ₁, y ₁),..., (a_n, y_n)). This step is reversible because of the condition inv_<(T) = 0. In more detail, knowing the multiset of entries in each row of T, there exists a unique arrangement of the entries in each row for which inv_<(T) = 0. Entries in the lowest row must appear in weakly increasing order. Suppose the first i – 1 rows have been filled, and S is the multiset of a_j values such that y_j = i. We fill the cells c in row i from left to right. At each step, cell c in row i is filled with the smallest unused element in S larger than T(d(c)), if any; otherwise, cell c is filled with the smallest unused element of S. Comparing this process to the definition of cocharge, it is not hard to check that maj_<(T) is precisely cchg(y ₁ y ₂ ··· y_n).

Third, to find (P, Q) = φ(T), we apply the RSK insertion algorithm to the pair of words y = y ₁ ··· y_n and a = a ₁ ··· a_n, inserting y in P and recording a in Q. Clearly, z_Q = z_T, z_P = z ^μ, and cchg(P) = cchg(y ₁ ··· y_n) = maj_<(T), as required. It is easy to see that φ is a bijection.

Kostka–Macdonald Coefficients for Two-Column Shapes. Our final application is a formula for K̃ _λ,μ when μ has at most two columns. A “Yamanouchi word” is a word w = w ₁... w_n such that for all k, the suffix w_k ··· w_n has partition content. Then, for μ₁ ≤ 2,.We omit the proof, which uses crystals, the RSK algorithm, and jeu de taquin.