A combinatorial model for the Macdonald polynomials

Symmetry

Lemma 1 below can be easily obtained from corollary 5.2.4 in ref. 6 (by letting each μ_i there be a single square, and choosing the offsets s _i appropriately). For any two sets A, B, we let A - B = {a ∈ A, a ∉ B}.

Definition 2: Let β₁ < β₂···< β_n be real numbers. Define a β-inversion of a function f: {1,..., n} → {1, 2} to be a pair i, j such that 0 < β_j - β_i < 1 and f(i) > f(j). Let inv_β(f) denote the number of β-inversions and set

Lemma 1. With the definitions above, we have G _β(z ₁, z ₂; q) = G _β(z ₂, z ₁; q) for all β.

Proof of Theorem 1: Given S, T let , so A _T is symmetric in the z _i if and only if F _T is, and

By inclusion-exclusion, it suffices to show that the right side of Eq. 14 is symmetric if we instead sum over all σ such that S ⊆ Des(σ, T). We denote this larger sum by A _T[Z; q, ≥ S]. Furthermore, it suffices to prove A _T[Z; q, ≥ S] is symmetric in any two consecutive variables z _i, z _i+1. Given (σ, T), let R _i(σ) be the set of those w ∈ T with w(σ) = i or w(σ) = i + 1. Note that if we permute the i and i + 1 entries among themselves we do not affect any inversion pairs or descents that involve a square outside R _i(σ). It follows that if we consider the contribution to A _T[Z; q, ≥ S] from all σ for which R _i(σ) equals a fixed set T ₀, and the values of σ at the squares of T - T ₀ equal a fixed filling (β, T - T ₀), we get the product of a constant monomial in {z ₁..., z _i-1, z _i+2,..., z _n}, a constant power of q, and A _T0[z _i, z _i+1; q, ≥ S ∩ T ₀]. Hence it suffices to show that for any S, T, A _T[z ₁, z ₂; q, ≥ S] = A _T[z ₂, z ₁; q, ≥ S].

Assume w ∈ Des(σ, T), so w(σ) = 2 and south(w)(σ) = 1. It is easy to check that if c is any square not equal to w or south(w), then the number of inversion pairs involving c and either w or south(w) is the same whether c(σ) = 1 or c(σ) = 2. Thus pairs of squares (w, south(w)), w ∈ S, contribute a constant power of q times a fixed power of z ₁ z ₂ to A _T[z ₁, z ₂; ≥ S]. Thus if E = T - S - {south(w), w ∈ S}, it now suffices to show A _E[z ₁, z ₂; q, ≥ ∅] = A _E[z ₂, z ₁; q, ≥ ∅].

Let n =|E|, and let m be the maximal row value of the squares of E. For 1 ≤ i ≤ n, if E(i) has coordinates (y, x) then set β_i = m - y + xε, where ε is a small positive number. It is easy to check that a pair (E(i), E(j)) of squares of E are in Inv(σ, E) if and only if (i, j) forms a β-inversion in the sense of Definition 2, with f replaced by σ. The symmetry of A _E[z ₁, z ₂; q, ≥ ∅] now follows from Lemma 1.

Shuffles

We say a sequence σ₁,..., σ_n is a shuffle of sequences a ₁,..., a _k if each a _i is a subsequence of σ, and σ is their disjoint union. Given a word σ of content α, note that the statistics maj(σ, T) and inv(σ, T) equal maj(σ′, T) and inv(σ′, T), respectively, where σ′ is the standardization of σ. Also, σ′ is a shuffle of increasing sequences of lengths α₁, α₂,..., or equivalently (σ′)^-1 is a concatenation of increasing sequences of lengths α₁, α₂,.... We call such a permutation an α-shuffle, and if β is an α-shuffle, we let word(β, α) denote the corresponding word of content α [so the standardization of word(β, α) equals β]. More generally, given a pair of partitions η, λ, with|η| +|λ| = n, we say σ ∈ S _n is a λ, η-shuffle if σ^-1 is the concatenation of alternating increasing and decreasing sequences of lengths λ₁, η₁, λ₂, η₂,.... This definition also applies if η,λ are any compositions, where by a composition of n we mean a finite sequence of nonnegative integers whose sum is n.

Let 〈,〉 denote the Hall scalar product, with respect to which the Schur functions are orthonormal. It is well known that the coefficient of m _λ in a symmetric function f is given by 〈f, h _λ〉, where h _k = s _k = ∑_λ⊢k m _λ and h _λ = ∏_i h _λi. Results in ref. 6 involving the “superization” of symmetric functions connected to the space of diagonal harmonics transfer easily to the F _T[Z; q, S]. We list a few of the consequences below.

Theorem 2. For any S, T, μ ⊢ n, and compositions η, λ,

Corollary. If Conjecture 1 holds, then

For a subset D of {1, 2,..., n - 1}, let

denote Gessel's quasisymmetric function.

Proposition 1. For any S, T,

Special Values

Proposition 2. Conjecture 1 is true if q = 1.

Proof: Clearly C̃ _μ[Z; 1, t] = ∏_i C̃ _(μi)[Z; 1, t], and H̃ _μ[Z; 1, t] is also known to factor similarly. Thus it suffices to consider the case μ = (1ⁿ), in which case it follows from the well known Cauchy identity and MacMahon's result on the equidistribution of t ^maj(σ) and t ^inv(σ) over words σ of fixed content.

One of the basic properties of the H̃ _μ[Z; q, t] is

where μ′ is the “conjugate” partition obtained by reflecting μ about the line y = x. Using this, the t = 1 case of Conjecture 1 follows from the following lemma, which was noticed by me and proven by N. Loehr and G. Warrington (personal communication).

Lemma 2. Let μ be a partition with two rows. Let β be a word of length μ₁, and α a composition of μ₂. Then

where the sum is over all words σ of content α, and σ + β is the word obtained by concatenating σ and β. Here is the q-multinomial coefficient (7).

A semistandard Young tableau of shape μ is a filling (σ, μ) where the entries are weakly increasing across rows and strictly decreasing down columns. The tableau is called standard if σ ∈ S _n. We let SSYT(μ, λ) denote the set of semistandard tableau of shape μ and content λ, and SYT(μ) denote the set of standard tableaux of shape μ. If τ is a standard tableau, we define the tableau descent set of τ, denoted descent(τ), to be the set of all i for which i + 1 is in a row of μ above the row containing i. Note that descent(τ) is different from the descent set Des when τ is viewed as a filling.

Theorem 3. Conjecture 1 is true if μ is a hook, i.e. μ = k1^{n- k} for some 1 ≤ k ≤ n.

Proof: Converting (ref. 8, theorem 2.1) into a statement about the K̃ _λ,μ(q, t), we get

where

Using Eq. 19 we can rephrase Eq. 21 as

Applying the well known fact that

where K _ν,λ =|SSYT(ν, λ)|, we now have

For any word σ of length n with 1 ≤ σ_i ≤ n, let rev(σ) = σ_n···σ₂σ₁ and flip_n(σ) = n - σ₁ + 1···n - σ_n + 1. Foata (9) (see also ref. 10) gave a bijective transformation φ on words that satisfies maj(σ) = inv(φ(σ)), and furthermore content (φ(σ)) = content (σ) and φ(σ)_n = σ_n. Let comaj(σ) = ∑_i∈Des(σ) n - i. For σ ∈ S _n, let π(σ) = (flip_n ○ rev ○ φ ○ rev ○ flip_n)(σ), where ○ denotes composition. For σ a word of content λ, define π(σ) = word(π(σ′), λ). One checks that comaj(σ) = inv(π(σ)), π(σ)₁ = σ₁, and π is an invertible map from the set of words of content λ to itself.

Given a λ-shuffle ζ ∈ S _n, let σ = word(ζ, λ), and let γ = σ₁···σ_n-k + π^-1(σ_n-k+1···σ_n) be the word of content λ obtained by applying the map π^-1 to the last k letters of σ, and fixing the first n - k letters. The standardization γ′ is a λ-shuffle, and if we apply the RSK algorithm to γ′, we get a pair (P _γ′, Q _γ′) of SYT of the same shape, with Des(γ′) = descent(Q _γ′) and Des((γ′)^-1) = descent(P _γ′) (see, for example, ref. 2, chapter 7). Furthermore, the values of maj(ζ, k1^n-k) and inv(ζ, k1^n-k) depend only on Q _γ′. Now descent (P _γ′) ⊆ {λ₁, λ₁ + λ₂,...}, hence in P _γ′ the numbers 1 through λ₁ form a horizontal strip, as do the numbers λ₁ + 1 through λ₁ + λ₂, etc. Thus we can associate a SSYT of content λ to P _γ′. It follows that as we vary ζ over all λ-shuffles in S _n, the number of different P _γ′ that will occur with a given Q _γ′ of shape ν equals K _ν,λ. Hence

by Eq. 26.

Remark 3: An interesting and perhaps important problem is to show

which by Eq. 19 must hold if Conjecture 1 is true. The arguments above show only that C̃ _μ[Z; 1, t] = C̃ _μ′[Z; t, 1]. We leave it as an exercise for the reader to verify Eq. 32 bijectively for hook shapes by using only the fact that C̃ _μ[Z; q, t] is a symmetric function, together with properties of the maps φ and π.

We can also prove the following special cases of our conjectures.

Proposition 3. Let d satisfy 0 ≤ d ≤ n. Then Eq. 16 holds when η = (n - d), λ = (d). Also,

where for any polynomial f(x), f|_xj stands for the coefficient of x^j in f. In addition, Conjecture 2 holds when q = 1.

Remark 4: By taking the coefficient of z ₁ z ₂···z _n in C̃ _μ[Z; q, t] we obtain a conjectured formula for the bigraded Hilbert series of the Garsia-Haiman modules V(μ). Garsia and Haiman (11) derive a statistical description for the Hilbert series when μ = k1^n-k, which is easily shown to be equivalent to ours. They also obtain statistics for the case where μ has two rows, but I do not know how to show their formula is equivalent to that predicted by Conjecture 1 for this case.

A Recursive Formulation

Given λ ⊢ n and S, T with S ⊆ T, to calculate the coefficient of the monomial symmetric function m _λ in F _T[Z; q, S], by symmetry it suffices to calculate the coefficient of , so we can consider only fillings involving words of content rev(λ).

Recall the description of inv(σ, T) in Remark 2, involving triples of squares. The fact that all of the ns are larger than any other entry of σ will allow us to isolate the contribution to inv(σ, T) from triples involving an n. We will view the set of squares of (σ, T) containing ns as P ∪ Q, where P ⊆ T - S, Q ⊆ S.

Definition 3: Given P, Q, S, T as above, let ind(P, Q, S, T) denote the number of triples of squares u, v, w satisfying

where in these patterns a square occupied by

The following result is easily derived from the definition of F _T[Z; q, S] and ind(P, Q, S, T).

Theorem 4. For λ ⊢ n and S ⊆ T,

with the initial condition F _∅[Z; q, ∅] = 1.

Conjectures Involving Schur Coefficients

It would be very desirable to have a combinatorial description of the Schur coefficients of the F _T[Z; q, S]. Such formulas exist for the K̃ _λ,μ when λ or μ is a hook or when μ has two columns or two rows, and for some other shapes obtained by adding a square or two to one of the above shapes. All of the published formulas for the case when μ has two columns are fairly complicated, involving such things as rigged configurations and catabolism (12-14).

We now advance a conjectured combinatorial description for 〈F _μ[Z; q, S], s _λ〉 whenever μ has at most three columns. Let F ₁ = (12···n, μ) be the filling of μ by the identity permutation and F ₂ = (n···21, μ) the filling by the reverse of the identity. For any pair of integers (a, b) with 1 ≤ a < b ≤ n, say a is in square A in F ₁ and b is in square B in F ₁, i.e. A = μ(a), B = μ(b). Define the (multi-t variate) μ-weight of (a, b), denoted wt(μ, a, b), as

For example, for F ₁ as on the left in Fig. 3,

Given a SYT τ of partition shape with|μ| squares, our strategy will be to identify pairs (a, b) as “inversion pairs” of τ, then weight them as in Eq. 38. We begin by partially defining what constitutes an inversion by the following.

1. The pair (a, b) forms an inversion in τ if 1 ≤ a < b ≤|μ| and b is weakly northwest of a in τ, i.e. b is not in a column to the right of a.

2. If a < b and b is weakly southeast of a, i.e. is not in a row above a, then (a, b) do not form an inversion pair.

3. If a + 3 is neither weakly northwest or weakly southeast of a, then (a, a + 3) forms an inversion pair if τ contains the pattern on the left in Fig. 4 and does not if τ contains the pattern on the right.

Define

which is a “multi-t variate” version of C̃ _μ. By Eq. 12, if we replace t _w by t ^leg(w)+1 for all w, this multi-t version will reduce to C̃ _μ[Z; q, t].

Let inversion(τ) denote the set of inversion pairs of τ.

Conjecture 3. If μ has at most three columns,

Example: If τ is the tableau on the right in Fig. 3, then

form inversions with nontrivial 3321-weights, so the contribution of τ to is t _(3,0) ^* q ^* q ^* t _(1,0) q ^{-2 *} q ^* q ^* t _(1,2) ^* q ^* q = t _(3,0) t _(1,0) t _(1,2) q ⁴.

Conjecture 3 has been checked in maple for all λ, μ with|λ| ≤ 12 and|μ| ≤ 12. The calculation made use of tables of the K _λ,μ(q, t) supplied by G. Tesler (Univeristy of California at San Diego, La Jolla), as well as J. Stembridge's maple package for symmetric functions sf (15), which was also used in testing our other conjectures. Note that if Eq. 40 holds, by taking the coefficient of ∏_w∈S t _w in the right side of Eq. 40 we obtain a formula for 〈F _μ[Z; q, S], s _λ〉.

Note. Conjecture 1 has been proven by M. Haiman (University of California, Berkeley), N. Loehr (University of Pennsylvania), and myself.