Séminaire Lotharingien de Combinatoire 60 (2008), Article B60c

A GENERALIZED MAJOR INDEX STATISTIC

SAMI H. ASSAF

Abstract. Inspired by the k-inversion statistic for LLT polynomials, we define a k-inversion number and k-descent set for words. Using these, we define a new statistic on words, called the k-major index, that interpolates between the major index and inversion number. We give a bijective proof that the k-major index is equi-distributed with the major index, generalizing a classical result of Foata and rediscovering a result of Kadell. Inspired by recent work of Haglund and Stevens, we give a partial extension of these definitions and constructions to standard Young tableaux. Finally, we give an application to Macdonald polynomials made possible through connections with LLT polynomials.

1. Introduction

Given a multiset M of n positive integers, a word on M is a sequence of positive integers w = w_{1}w_{2} ⋯ w_{n} that reorders M. A statistic on words is an association of an element of ℕ to each word. A fundamental statistic that has been rediscovered in many guises is the inversion number of a word, defined as the number of pairs of indices (i < j) such that w_{i} > w_{j}. A descent of a word is an index i such that w_{i} > w_{i+1}. In 1913, Major P. MacMahon [Mac13] introduced an important statistic, now called the major index in his honor, defined as the sum over the descents of a word. Using generating functions, MacMahon [Mac16] proved the remarkable fact that the major index has the same distribution as the inversion number. Precisely, he showed that for W_{M} the set of words on a fixed multiset M,

(1)  ∑_{w∈W_{M}} q^{maj(w)} = ∑_{w∈W_{M}} q^{inv(w)},

where maj(w) denotes the major index of w and inv(w) denotes the inversion number of w. Any statistic that is equi-distributed with the major index, i.e. a statistic satisfying the above equation, is called Mahonian. In 1968, Foata [Foa68] constructed a bijection on words with the property that the major index of a word equals the inversion number of its image, thereby providing a bijective proof of equation (1).

In this paper, we introduce a statistic called the k-major index that interpolates between the major index and inversion number. More precisely, the 1-major index is MacMahon’s major index, and the n-major index of a word of length n is the inversion number. By constructing bijections on words with a recursive structure similar to Foata’s bijection, we give a bijective proof that the k-major index is Mahonian for all k. Looking back through the literature, this same statistic was discover by Kadell [Kad85] who also gave a bijective proof that the distribution is Mahonian. Whereas Kadell’s bijections in fact refine Foata’s original bijection, the family of bijections defined herein is not the same as Kadell’s and, when taking the major index to the inversion number, gives a bijection different from that of Foata. The k-major index statistic is defined in Section 2, and the bijections and proof that the distribution is Mahonian are given in Section 3. Other nice interpolating statistics were introduced by Rawlings [Raw81] and Clarke and Foata [CF95], though these differ from the statistic presented here.

2000 Mathematics Subject Classification. Primary 05A15;Secondary 05A05 05A19 05E05 05E10 .

Key words and phrases. Major index, descents, inversions, Foata bijection, tableaux statistics, Macdonald polynomials.

Work supported in part by NSF Postdoctoral Fellowship DMS-0703567.

It is also natural to define a major index statistic on standard Young tableaux, which are central objects in the study of symmetric functions. Recently, Haglund and Stevens [HS07] defined an inversion number on tableaux. Their construction generalizes Foata’s bijection to tableaux and shows that the inversion number and major index are equi-distributed over standard Young tableaux of a fixed shape. Motivated by this, we use the bijections presented here to extend the notion of the k-major index to standard Young tableaux, for k ≤ 3. We hope this method might be used to build a complete family of statistics interpolating between major index and inversion number on tableaux. This exploration takes place in Section 4.

Our discovery of the k-major index and the family of bijections presented here came about through the study of Macdonald polynomials [Ass07a]. In Section 5, we elaborate on this connection and present a conjecture for yet another family of bijections sharing many of the same properties that would have the further consequence of providing a remarkably simple combinatorial proof of Macdonald positivity.

2. Definitions and notation

At times it will be convenient to consider a slightly more general definition for a word w, where w_{i} is allowed to be either a positive integer or an ∅. In this case, ∅’s should be regarded as incomparable to other letters, so that they are simply a way of spacing out the nonempty letters of w. This idea will be especially important in connection with Macdonald polynomials discussed in Section 5.

Definition 2.1. For w a word, k a positive integer, define the k-descent set of w, denoted Des_{k}(w), by

Des_{k}(w) = {(i, i + k) | w_{i} > w_{i+k}},

and define the k-inversion set of w, denoted Inv_{k}(w), by

Inv_{k}(w) = {(i, j) | k > j − i > 0 and w_{i} > w_{j}}.

For example, for w = 986173245 and k = 3 we have

Des_{3}(9 8 6 1 7 3 2 4 5) = {(1, 4), (2, 5), (3, 6), (5, 8)},
Inv_{3}(9 8 6 1 7 3 2 4 5) = {(1, 2), (1, 3), (2, 3), (2, 4), (3, 4), (5, 6), (5, 7), (6, 7)}.

In fact, it is enough to define k-descents since k-inversions may be recovered from the observation

(2)  Inv_{k}(w) = ⋃_{j<k} Des_{j}(w).

Note that when k = 1, Des_{k} gives the usual descent set for a word. Similarly, when N ≥ n, Inv_{N} gives the usual set of inversion pairs for a word of length n. We interpolate between the corresponding statistics, maj and inv, with the following statistic depending on the parameter k.

Definition 2.2. Given a word w and a positive integer k, define the k-major index of w by

maj_{k}(w) = |Inv_{k}(w)| + ∑_{(i,i+k)∈Des_{k}(w)} i.

For the same example, we have maj_{3}(9 8 6 1 7 3 2 4 5) = 8 + 1 + 2 + 3 + 5 = 19. For a word w of length n ≤ N, the previous observations show that

maj_{1}(w) = maj(w),
maj_{N}(w) = inv(w).

The statistic maj_{k} was first defined by Kadell [Kad85], who gives a bijective proof that this statistic is Mahonian. Kadell’s bijections take inv to maj_{k}, with the extreme case from inv to maj corresponding precisely to the inverse of Foata’s bijection [Foa68]. In Section 3, we give a different family of bijections, taking maj_{k−1} to maj_{k}, which, when composed appropriately, give a different bijection from maj to inv.

In the case when w is a permutation (possibly with ∅s), we will also be interested in the descent set of the inverse permutation, denoted iDes, defined by

(3)  iDes(w) = Des(w^{−1}) = {i | i appears to the left of i + 1 in w}.

For example, iDes(9 8 6 1 7 3 2 4 5) = {2, 5, 7, 8}.

Recall that a partition λ is a weakly decreasing sequence of positive integers: λ = (λ_{1}, λ_{2}, …, λ_{m}), λ_{1} ≥ λ_{2} ≥ ⋯ ≥ λ_{m} > 0. A partition λ may be identified with its Young diagram: the set of points (i, j) in the ℤ_{+} × ℤ_{+} lattice quadrant such that 1 ≤ i ≤ λ_{j}. We draw the diagram so that each point (i, j) is represented by the unit cell southwest of the point. A standard Young tableau of shape λ is a labelling of the cells of the Young diagram of λ with the numbers 1 through n, where n = ∑_{i} λ_{i}, such that the entries increase along rows and up columns. For example, see Figure 1.

8 2 5 6 1 3 4 7

Figure 1. A standard Young tableau of shape (4, 3, 1).

For a standard Young tableau T, recall the descent set of T, denoted Des(T), defined by

(4)  Des(T) = {(i, i + 1) | i lies strictly south of i + 1 in T }.

Completely analogous to the case with words, define the major index of T, denoted maj(T), by

(5)  maj(T) = ∑_{(i,i+k)∈Des(T)} i.

For the example in Figure 1, Des = {(1, 2), (4, 5), (7, 8)} and so maj = 1 + 4 + 7 = 12. The descent set for tableaux corresponds to the descent set of permutations in the sense that for a fixed set D,

#{w ∈ S_{n} | Des(w) = D} = ∑_{λ} f^{λ} · #{T ∈ SYT(λ) | Des(T) = D},

where SYT(λ) denotes the set of standard Young tableaux of shape λ and f^{λ} = |SYT(λ)|. This identity can be proved using the Robinson–Schensted–Knuth correspondence that bijectively associates each permutation w with a pair of standard tableaux (P, Q) of the same shape such that iDes(w) = Des(Q). We postpone the definition of Des_{k} and maj_{k} for tableaux until Section 4.

3. A family of bijections on words

For k ≥ 2, we will construct bijections ϕ^{(k)} on words of length n such that

(6)  maj_{k−1}(w) = maj_{k}(ϕ^{(k)}(w)).

As noted earlier, these bijections are not equivalent to those defined by Kadell, and the appropriate composition does not give Foata’s bijection. That said, the construction below follows the idea of [Foa68] in that ϕ^{(k)} will be defined recursively using an involution γ_{j}^{(k)} to permute the letters of a given word.

Let x, a, b be (not necessarily distinct) integers. Say that x splits the pair a, b if a ≤ x < b or b ≤ x < a. Let w be a word of length n. For k ≥ 2 and j ≤ n, define a set of indices Γ_{j}^{(k)} of w by

(7)  j − k ∈ Γ_{j}^{(k)}(w) if w_{j} splits the pair w_{j−k}, w_{j−k+1},

and if i ∈ Γ_{j}^{(k)}(w), then

(8)  i − k ∈ Γ_{j}^{(k)}(w) if exactly one of w_{i} or w_{i+1} splits the pair w_{i−k}, w_{i−k+1}.

For our running example, we have Γ_{8}^{(3)}(9 8 6 1 7 3 2 4 5) = {5, 2}.

Let permutations act on words by permuting the indices, i.e. τ · w = w_{τ(1)}w_{τ(2)} ⋯ w_{τ(n)}. Define a map γ_{j}^{(k)} by

(9)  γ_{j}^{(k)}(w) = ( ∏_{i∈Γ_{j}^{(k)}(w)}(i, i + 1)) · w.

That is to say, γ_{j}^{(k)}(w) is the result of interchanging w_{i} and w_{i+1} for all i ∈ Γ_{j}^{(k)}(w). Back to our running example, we have γ_{8}^{(3)}(9 8 6 1 7 3 2 4 5) = 9 6 8 1 3 7 2 4 5.

For w a word of length n, define ϕ^{(k)} by

(10)  ϕ^{(k)}(w) = γ_{n}^{(k)} ∘ γ_{n−1}^{(k)} ∘ ⋯ ∘ γ_{1}^{(k)}(w).

Since γ_{j}^{(k)} is the identity for j ≤ k, these terms may be omitted from equations 10 and 11. For example, for w = 6 9 3 8 1 7 2 4 5, ϕ^{(3)}(w) is computed as follows.

\begin{aligned}w & = & 6 & 9 & 3 & 8 & 1 & 7 & 2 & 4 & 5 \\ γ_{4}^{(3)}(w) & = & 9 & 6 & 3 & 8 & 1 & 7 & 2 & 4 & 5 \\ γ_{5}^{(3)}γ_{4}^{(3)}(w) & = & 9 & 6 & 3 & 8 & 1 & 7 & 2 & 4 & 5 \\ γ_{6}^{(3)}γ_{5}^{(3)}γ_{4}^{(3)}(w) & = & 9 & 6 & 8 & 3 & 1 & 7 & 2 & 4 & 5 \\ γ_{7}^{(3)}γ_{6}^{(3)}γ_{5}^{(3)}γ_{4}^{(3)}(w) & = & 9 & 6 & 8 & 1 & 3 & 7 & 2 & 4 & 5 \\ γ_{8}^{(3)}γ_{7}^{(3)}γ_{6}^{(3)}γ_{5}^{(3)}γ_{4}^{(3)}(w) & = & 9 & 8 & 6 & 1 & 7 & 3 & 2 & 4 & 5 \\ ϕ^{(3)}(w) = γ_{9}^{(3)}γ_{8}^{(3)}γ_{7}^{(3)}γ_{6}^{(3)}γ_{5}^{(3)}γ_{4}^{(3)}(w) & = & 9 & 8 & 6 & 1 & 7 & 3 & 2 & 4 & 5 \end{aligned}

Notice that for this example maj_{2}(w) = 19 = maj_{3}(ϕ^{(3)}(w)). Before proving equation (6) in general, we take note of a few important properties that ϕ^{(k)} shares with Foata’s bijection (for Foata, properties (i) and (ii) are shown in [Foa68], and property (iii) is shown in [FS78]).

Proposition 3.1. For each k ≥ 2, we have (i) the map ϕ^{(k)} is a bijection on words on M with fixed ∅ positions; (ii) for w a word of length n, w_{n−k+1} > w_{n} if and only if ϕ^{(k)}(w)_{n−k} > ϕ^{(k)}(w)_{n} = w_{n}; (iii) for w a permutation, iDes(w) = iDes(ϕ^{(k)}(w)).

Proof. Since Γ_{j}^{(k)}(γ_{j}^{(k)}(w)) = Γ_{j}^{(k)}(w), γ_{j}^{(k)} is an involution on words of length n for all j ≤ n and k ≥ 2. Therefore ϕ^{(k)} is a bijection on words of length n for all k ≥ 2 with inverse given by

(11)  ψ^{(k)}(w) = γ_{1}^{(k)} ∘ ⋯ ∘ γ_{n−1}^{(k)} ∘ γ_{n}^{(k)}(w).

It is clear from the definition of γ_{j}^{(k)} that ϕ^{(k)} in fact fixes the last k − 1 letters of a word, so indeed the last letter is fixed for every k. Let u = γ_{n−1}^{(k)} ⋯ γ_{1}^{(k)}(w), u_{j} = w_{j} for j ≥ n − k + 1. If u_{n−k} and u_{n−k+1} compare the same with u_{n}, then u = ϕ^{(k)}(w) and (ii) clearly holds; otherwise, these two letters are interchanged by γ_{n}^{(k)}, again showing that (ii) is satisfied. Also note that ϕ^{(k)} may be defined recursively by

(12)  ϕ^{(k)}(wx) = γ_{n+1}^{(k)} (ϕ^{(k)}(w)) x,

which completely parallels Foata’s original construction. Finally, since consecutive letters cannot be split (in the sense of Γ_{j}^{(k)}) they may never be interchanged by γ_{j}^{(k)}. Thus the inverse descent set is preserved. □

To prove equation (6), we follow the strategy of [Foa68]. The key, therefore, lies in the following lemma.

Lemma 3.2. For k ≥ 2, w a word of length n and j ≤ n,

maj_{k} (γ_{j}^{(k)}(w_{1} ⋯ w_{j−1})) = maj_{k}(w_{1} ⋯ w_{j−1}) + \begin{cases}1 & if w_{j−k} > w_{j} ≥ w_{j−k+1}, \\ −1 & if w_{j−k+1} > w_{j} ≥ w_{j−k}, \\ 0 & otherwise. \end{cases}

Proof. If neither of the first two cases holds, then j − k ∉ Γ_{j}^{(k)}(w), so γ_{j}^{(k)}(w) = w, and the result follows. Assume, then, that j − k ∈ Γ_{j}^{(k)}(w), and set u = w_{j−k}w_{j−k+1} ⋯ w_{j−1}. Then

(13)  maj_{k} (γ_{j}^{(k)}(u)) = maj_{k}(u) + \begin{cases}1 & if w_{j−k} > w_{j} ≥ w_{j−k+1}, \\ −1 & if w_{j−k+1} > w_{j} ≥ w_{j−k}. \end{cases}

For i ∈ Γ_{j}^{(k)}(w), let u = w_{i}w_{i+1} ⋯ w_{j−1}, and, by induction, assume that equation (13) holds for u. Let u′ = w_{i−k}w_{i−k+1} ⋯ w_{j−1}. We will show that u′ also satisfies equation (13) by considering the contribution to maj_{k} of w_{i−k}, w_{i−k+1}, …, w_{i−1}. For i − k + 1 < h < i, kinversions and k-descents involving w_{h} are the same for u′ and γ_{j}^{(k)}(u′), so we need only consider contributions from the potential k-inversions (i − k, i − k + 1) and (i − k + 1, i), and the potential k-descents (i − k, i) and (i − k + 1, i + 1).

First suppose i − k ∈ Γ_{j}^{(k)}(w). In all possible scenarios for w_{i−k}, w_{i−k+1}, w_{i}, w_{i+1}, we have

(i − k, i − k + 1) ∈ Inv_{k}(w) ⇔ (i − k, i − k + 1) ∉ Inv_{k} (γ_{j}^{(k)}(w)) ,
(i − k, i) ∈ Des_{k}(w) ⇔ (i − k + 1, i + 1) ∈ Des_{k} (γ_{j}^{(k)}(w)) ,
(i − k + 1, i + 1) ∈ Des_{k}(w) ⇔ (i − k, i) ∈ Des_{k} (γ_{j}^{(k)}(w)) .

If both or neither of (i − k, i) and (i − k + 1, i + 1) are k-descents of w, then the same holds for u′ and γ_{j}^{(k)}(u′). In this case exactly one of (i − k, i − k + 1) and (i − k + 1, i) is a k-inversion for w, and

(i − k + 1, i) ∈ Inv_{k}(u′) ⇔ (i − k + 1, i) ∉ Inv_{k} (γ_{j}^{(k)}(u′)) .

The lemma now follows. On the other hand, if exactly one of (i−k, i) and (i−k+1, i+1) is a k-descent of w, then the difference in the contribution to maj_{k} from the potential k-descents is offset by the difference from the potential k-inversion (i − k, i − k + 1). Furthermore,

(i − k + 1, i) ∈ Inv_{k}(u′) ⇔ (i − k + 1, i) ∈ Inv_{k} (γ_{j}^{(k)}(u′)) ,

thereby establishing the result.

To complete the proof, note that when i − k ∉ Γ_{j}^{(k)}(w), either w_{i} and w_{i+1} compare the same with w_{i−k} and also with w_{i−k+1} and so the k-inversions and k-descents beginning with i − k or i − k + 1 are unchanged, or the k-descent at (i − k + 1, i + 1) is exchanged for a k-descent at (i − k, i) along with a k-inversion at (i, i + 1). In both cases the contribution to the k-major index is preserved. □

Proposition 3.3. For k ≥ 2 and w a word, maj_{k−1}(w) = maj_{k} (ϕ^{(k)}(w)).

Proof. The result is clear for a words of length ≤ k. We proceed by induction, assuming the result for words of length n − 1. Let w be a word of length n − 1 and x a letter. To simplify notation, let

u = γ_{n}^{(k)} (ϕ^{(k)}(w)) .

By expanding the definition of maj_{k}, we have

maj_{k} (ϕ^{(k)}(wx))

= maj_{k}(ux)

= maj_{k}(u) + #\{i > n − k | u_{i} > x\} + \begin{cases}0 & if x ≥ u_{n−k} \\ n−k & if u_{n−k} > x \end{cases}

= maj_{k}(u) + #\{i > n − k + 1 | u_{i} > x\} + \begin{cases}n−k + 1 & if u_{n−k} > x, u_{n−k+1} > x \\ 0 + 0 & if x ≥ u_{n−k}, x ≥ u_{n−k+1} \\ n−k + 0 & if u_{n−k} > x, x ≥ u_{n−k+1} \\ 0 + 1 & if x ≥ u_{n−k}, u_{n−k+1} > x \end{cases}

Applying Lemma 3.2 and simplifying gives

maj_{k} (ϕ^{(k)}(wx))

= maj_{k} (γ_{n}^{(k)}(u)) + #\{i > n − k + 1 | u_{i} > x\} + \begin{cases}n−k+1 + 0 & if u_{n−k}, u_{n−k+1} > x \\ 0 + 0 & if x ≥ u_{n−k}, u_{n−k+1} \\ n−k + 1 & if u_{n−k} > x ≥ u_{n−k+1} \\ 1 − 1 & if u_{n−k+1} > x ≥ u_{n−k} \end{cases}

= maj_{k−1} (ϕ^{(k)}(w)) + #\{i > n − k + 1 | u_{i} > x\} + \begin{cases}0 & if x ≥ u_{n−k} \\ n−k+1 & if u_{n−k} > x \end{cases}

Recall from Proposition 3.1 that for i ≥ n − k + 2, u_{i} = w_{i}, and so

{i > n − k + 1 | u_{i} > x} = {i > n − k + 1 | w_{i} > x}.

Furthermore, since ϕ^{(k)}(w)_{n−k+1} = w_{n−k+1}, we also have

u_{n−k} ≤ x ⇔ w_{n−k+1} ≤ x.

Continuing from the above equation using these two facts and the inductive hypothesis, we have

maj_{k} (ϕ^{(k)}(wx)) = maj_{k−1}(w) + #\{i > n − k + 1 | w_{i} > x\} + \begin{cases}0 & if x ≥ w_{n−k+1} \\ n−k+1 & if w_{n−k+1} > x \end{cases}

which is exactly maj_{k−1}(wx), as desired. □

For 1 ≤ h < i, we can compose these bijections to form the bijection

(14)  ϕ^{[i,h]} = ϕ^{(i)} ∘ ⋯ ∘ ϕ^{(h+1)}

satisfying maj_{h}(w) = maj_{i} (ϕ^{[i,h]}(w)). In particular, ϕ^{[k,1]} provides a bijective proof of the following.

Theorem 3.4. Let W_{M} be the set of words on a multiset M with a fixed ∅ positions. Then for k ≥ 1,

∑_{w∈W_{M}} q^{maj(w)} = ∑_{w∈W_{M}} q^{maj_{k}(w)}.

That is to say, the k-major index has Mahonian distribution.

4. Extending the k-major index to tableaux

In [HS07], Haglund and Stevens define an inversion number for standard tableaux that is equi-distributed with the major index. Therefore it is natural to try to extend the k-major index statistic to tableaux in a similar manner. However, to do this, we must first define Des_{k} for standard Young tableaux.

Consider the possible relative positions of i and i + k in a standard Young tableau T. Since i < i + k, i must lie strictly west or strictly south of i + k. If i lies strictly west and weakly north of i + k, then the pair (i, i + k) should not count as a k-descent. Conjugately, if i lies strictly south and weakly east of i + k, then the pair (i, i + k) should count as a k-descent. The difficulty arises in how to resolve the situation where i lies strictly southwest of i+k. The approach given in [HS07] is quite involved as it is based on inversion paths which must be computed iteratively. In most cases, interchanging even two consecutive entries in a tableau completely alters the inversion paths in an opaque way. Therefore we begin at the other extreme, though below we succeed only up to k = 3.

For k = 2, the ambiguous case when i lies strictly southwest of i + 2 cannot arise in a standard tableaux. However, for k = 3 we must decide whether (i − 3, i) is a 3-descent when i − 3, i − 2, i − 1, i appear in a 2 × 2 box in T. For reasons that will become clear, we resolve the situations as indicated in Figure 2.

\begin{matrix}\begin{matrix}i−1 & i \\ i−3 & i−2 \end{matrix} & \begin{matrix}i−2 & i \\ i−3 & i−1 \end{matrix} \\ (i − 3, i) ∈ Des_{3} & (i − 3, i) ∉ Des_{3} \end{matrix}

Figure 2. Ambiguous cases for whether (i − 3, i) should constitute a 3-descent.

To simplify notation, we introduce the following terminology. For i < n, say that i attacks n if i lies strictly south and weakly east of n or if i lies strictly southwest of n and i + 1 attacks n.

Definition 4.1. For T a standard tableau, k ≤ 3, define the k-descent set of T, denoted Des_{k}(T), by

Des_{k}(T) = {(i, i + k) | i attacks i + k},

define the set of k-inversions of T, denoted Inv_{k}(T), by

Inv_{k}(T) = ⋃_{j<k} Des_{j}(T),

and finally define the k-major index of T, denoted maj_{k}(T), by

maj_{k}(T) = |Inv_{k}(T)| + ∑_{(i,i+k)∈Des_{k}(T)} i.

Note that for defining k-inversions we made use of the alternate description of k-inversions for words given in equation (2). For the example given in Figure 1, we have Des_{2} = {(3, 5), (4, 6), (6, 8)}, Inv_{2} = {(1, 2), (4, 5), (7, 8)} and so maj_{2} = 3 + 3 + 4 + 6 = 16.

Parallel to Section 3, we aim to generalize Theorem 3.4 to tableaux by constructing bijections Φ^{(k)}, k = 2, 3, on standard Young tableaux of fixed shape such that

(15)  maj_{k−1}(T) = maj_{k}(Φ^{(k)}(T)).

The first task, then, is to define the set Γ_{j}^{(k)}. Here care must be taken when determining when the “splitting” condition is satisfied. As a minimum requirement, since the intention is to interchange i and i + 1, we must ensure that we do this only if i and i + 1 do not appear in the same row or column. This motivates the decision in Figure 2 as well as the following definitions.

Say that n splits a, b if exactly one of a, b attacks n. For k = 2, 3, define Γ_{j}^{(k)} by

j − k ∈ Γ_{j}^{(k)}(T) if j splits the pair j − k, j − k + 1,

and if i ∈ Γ_{j}^{(k)}(T), then

i − k ∈ Γ_{j}^{(k)}(T) if exactly one of i, i + 1 splits the pair i − k, i − k + 1.

By the definition of attacking, both or neither i, i + 1 attack n whenever i is strictly southwest of n. Therefore in order for n to split i, i + 1, one must lie strictly south and weakly east of n, and the other must lie weakly north of n. It follows, then, that if i and i + 1 lie in the same row or column of T, then n does not split i, i + 1 for any n.

Let permutations act on standard fillings of a Young diagram by permuting the entries. While this is not, in general, a well-defined action on tableaux, the following application in fact is. For k = 2, 3, define γ_{j}^{(k)} by

(16)  γ_{j}^{(k)}(T) = ( ∏_{i∈Γ_{j}^{(k)}(T)}(i, i + 1)) · T.

That is, γ_{j}^{(k)} interchanges i and i + 1 for all i ∈ Γ_{j}^{(k)}(T). As before, γ_{j}^{(k)} is the identity for j ≤ k.

If i is strictly southwest of n, then n cannot split the pair i, i + 1. It follows that Γ_{j}^{(k)}(T) = Γ_{j}^{(k)}(γ_{j}^{(k)}(T)); in particular, γ_{j}^{(k)} is an involution. For k = 2, 3, define a bijection Φ^{(k)} on tableaux of a fixed shape by

(17)  Φ^{(k)}(T) = γ_{n}^{(k)} ∘ γ_{n−1}^{(k)} ∘ ⋯ ∘ γ_{1}^{(k)}(T).

For the example in Figure 3, observe that maj_{1}(T) = 16 = maj_{2}(Φ^{(2)}(T)).

T = 8 2 4 6 1 3 5 7  8 3 4 6 1 2 5 7  8 2 5 6 1 3 4 7 = Φ^{(2)}(T)

γ_{4}^{(2)} γ_{6}^{(2)}

Figure 3. An example of Φ^{(2)}; here γ_{j}^{(2)} = id for j ≠ 4, 6.

Similar to before, the inverse of Φ^{(k)} is given by composing the maps γ_{j}^{(k)} in the reverse order. This establishes the analogue of the property (i) of Proposition 3.1, and the analogue of property (ii) is that the largest letter of T is fixed by Φ^{(k)}. As property (iii) has no real analogue in this setting, we move on to the more important statement observed in the example, namely the analogue of Proposition 3.3 below.

Proposition 4.2. For T a standard Young tableau and k = 2, 3, we have

maj_{k−1}(T) = maj_{k} (Φ^{(k)}(T)) .

Proof. We use the proofs of Lemma 3.2 and Proposition 3.3. For this to make sense, we make the substitution that for i < n, w_{i} > w_{n} should be interpreted as “i attacks n” and similarly w_{i} ≤ w_{n} should be interpreted as “i does not attack n”. In order for the arguments to remain valid under this translation, interchanging entries using γ_{j}^{(k)} may not change k-inversions or k-descents between unmoved entries. The only potential violation of this is the potential 3-descent between i − 3 and i in the situations depicted in Figure 2. However, in either case i − 2 ∉ Γ_{j}^{(3)} since neither i + 1 nor i + 2 can split the pair i − 2, i − 1. Therefore, with this translation, the proofs carry through verbatim. □

Theorem 4.3. For λ a (skew) partition diagram, we have

(18)  ∑_{T ∈SYT(λ)} q^{maj(T)} = ∑_{T ∈SYT(λ)} q^{maj_{2}(T)} = ∑_{T ∈SYT(λ)} q^{maj_{3}(T)}.

Unfortunately, Theorem 4.3 is the best we can do towards extending Theorem 3.4 using this direct analogue of ϕ^{(k)}. This technique breaks down at k = 4 for the shape (2, 2, 2). In this case, the 6 must lie in the northeast corner and will necessarily interchange the 2 and 3 if they both lie in the first two rows. Then if 1, 2, 3, 4 occupy the first two rows, this changes whether (1, 4) is a 3-descent (4-inversion). In order to overcome this shortfall, either we must adopt a more dynamic notion of k-inversions as in the Haglund–Stevens approach or a more complicated bijection.

5. Connections with Macdonald polynomials

The k-major index statistic was rediscovered in the author’s study of Macdonald polynomials. In this section we connect the results of Section 3 back to Macdonald polynomials.

In [HHL^{+}05b], Bylund and Haiman introduced the k-inversion number of a k-tuple of tableaux to be the number of inversions between certain entries, and it is shown that this statistic may be used to give an alternative definition for Lascoux-Leclerc-Thibon polynomials. In particular, when each shape of the k-tuple is a ribbon, i.e. contains no 2×2 block, the k-inversion number of the k-tuple is exactly |Inv_{k}(w)| where w is a certain reading word of the k-tuple. In further study of these objects [Ass07a], it became natural to associate to each k-tuple not only the k-inversion number, but also a k-descent set. Again, when the shapes of the k-tuple in question are all ribbons, this is exactly given by Des_{k}(w) for the same reading word w. Here it is essential that w be allowed to contain ∅’s in order to correctly space the entries of the k-tuple.

The case when the k-tuple consists entirely of ribbons is an important special case in light of [Hag04, HHL05a] where it is shown that the Macdonald polynomials are in fact positive sums of LLT polynomials where the shapes are ribbons. In this context, the index k is given by the number of columns of the indexing partition of the Macdonald polynomial. The Macdonald Positivity Theorem, conjectured by Macdonald in 1988 [Mac88], was first proved by Haiman using algebraic geometry [Hai01], and more recently by Grojnowski and Haiman using Kazhdan-Lusztig theory [GH07] and the author using a purely combinatorial argument [Ass07a]. This latter proof, while purely combinatorial, relies on new combinatorial machinery, namely dual equivalence graphs, involving rather technical proofs of the main theorems. Below we suggest how Macdonald positivity may be recovered in a completely elementary way using bijections similar to ϕ^{(k)}.

The main idea behind [Ass07a] is to group together terms of a Macdonald polynomial contributing to a single Schur function and having the same associated statistics. This is done in three steps; for complete details, see [Ass07b]. First, quasisymmetric functions are used to reduce to standard words, i.e. permutations, and it is here that the inverse descent set of a permutation is relevant. Next, for a given k, the permutations are divided into equivalence classes (in the language of [Ass07a], connected components of a graph) using the following involutions.

For i ≥ 2, define involutions d_{i} and d̃_{i} on permutations where i does not lie between i − 1 and i + 1 by

(19)  d_{i}(⋯ i ⋯ i ± 1 ⋯ i ∓ 1 ⋯) = ⋯ i ∓ 1 ⋯ i ± 1 ⋯ i ⋯,
(20)  d̃_{i}(⋯ i ⋯ i ± 1 ⋯ i ∓ 1 ⋯) = ⋯ i ± 1 ⋯ i ∓ 1 ⋯ i ⋯,

where all other entries remain fixed. Combining these, define D_{i}^{(k)} by

(21)  D_{i}^{(k)}(w) = \begin{cases}d_{i}(w) & if dist(i − 1, i, i + 1) > k \\ d̃_{i}(w) & if dist(i − 1, i, i + 1) ≤ k \end{cases} ,

where dist(i − 1, i, i + 1) is the maximum distance between the positions of i − 1, i, i + 1 in w. The ∅’s, or spacers, in w are essential for this step as they adjust the relative distance of the letters of w.

Definition 5.1. Call two permutations w and u k-equivalent, denoted w ∼_{k} u, if there exists a sequence i_{1}, i_{2}, …, i_{m} ≥ 2 such that w = D_{i_{1}}^{(k)}D_{i_{2}}^{(k)} ⋯ D_{i_{m}}^{(k)}(u).

1-classes: {1 2 3}; {2 1 3 , 3 1 2}; {2 3 1 , 1 3 2}; {3 2 1}
2-classes: {1 2 3}; {2 1 3 , 1 3 2}; {2 3 1 , 3 1 2}; {3 2 1}

Figure 4. Equivalence classes of permutations of length 3.

Remark 5.2. Note that the 1-equivalence classes are exactly the dual equivalence classes for partitions; see [Hai92]. In particular, the sum of the quasisymmetric functions associated to the permutations in a 1-equivalence class is a Schur function.

One of the main observations in [Ass07a] is that

Des_{k}(w) = Des_{k} (D_{i}^{(k)}(w)) and |Inv_{k}(w)| = |Inv_{k} (D_{i}^{(k)}(w))| .

In particular, Des_{k} and |Inv_{k}| are constant on k-equivalence classes. Therefore, the third and final step toward establishing the Macdonald Positivity Theorem is to prove that the sum over the quasisymmetric functions associated to a given k-equivalence class is Schur positive. By Remark 5.2, a natural approach is to relate k-classes to 1-classes. Indeed, the proof presented in [Ass07a] does this by showing that a connected component of the graph for k-columns (a k-equivalence class) may be broken into a union of connected dual equivalence graphs (1-equivalence classes). It is for this step that the proof becomes quite technical and involved, and so the idea is to bypass the machinery of dual equivalence graphs altogether. The following result achieves this for the 2-column/2-equivalence class case.

Theorem 5.3. For w a permutation such that i does not lie between i − 1 and i + 1, we have

(22)  ϕ^{(2)} (D_{i}^{(1)}(w)) = D_{i}^{(2)} (ϕ^{(2)}(w)) .

Proof. First note that D_{i}^{(1)} = d_{i}. Furthermore, D_{i}^{(2)}(w) = d_{i}(w) unless i − 1, i, i + 1 are adjacent in w. Without loss of generality, we may assume that w_{r} = i + 1, w_{s} = i − 1 and w_{t} = i for some indices r < s < t. Set w̃ = d_{1}(w), so that w̃_{r} = i, w̃_{s} = i − 1 and w̃_{t} = i + 1. We aim to show that D_{i}^{(2)}(ϕ^{(2)}(w)) = ϕ^{(2)}(w̃).

For notational convenience, we write γ_{j} for γ_{j}^{(2)} and Γ_{j} for Γ_{j}^{(2)}. Since the definition of Γ_{j} depends only on the relative orders of letters, it follows that Γ_{j}(w) = Γ_{j}(w̃) for j < t. Along the same lines, Γ_{t}(w) ≠ Γ_{t}(w̃) if and only if r, s = t − 2, t − 1. If this is not the case, then γ_{t} ⋯ γ_{1}(w) = d_{i} (γ_{t} ⋯ γ_{1}(w̃)) and indeed dist(i − 1, i, i + 1) > 2 in γ_{t} ⋯ γ_{1}(w). In the affirmative case, Γ_{t}(w) = {t − 2} since both or neither i − 1, i + 1 splits any pair of preceding letters and Γ_{t}(w̃) = ∅. Therefore γ_{t} ⋯ γ_{1}(w) = d̃_{i} (γ_{t} ⋯ γ_{1}(w̃)) as desired since dist(i − 1, i, i + 1) = 2 in γ_{t} ⋯ γ_{1}(w).

Now consider the effect of γ_{j} for j > t. For the same reasons as before, Γ_{j}(w) ≠ Γ_{j}(w̃) if and only if i − 1, i, i + 1 are adjacent either before or after γ_{j} is applied. For w̃, the relative positions of i − 1, i, i + 1 will never change. Moreover, the position of i + 1 in w̃ tracks the position of i in w, and the positions of i, i − 1 in w̃ are the positions of i − 1, i + 1 in w (though not necessarily respectively). For w, each time i moves between adjacent and nonadjacent to i − 1, i + 1, the difference between Γ_{j} for w and w̃ is exactly that the former contains the index of the leftmost of i − 1, i + 1 and the latter does not. Comparing d_{i} with d̃_{i}, this is exactly the difference between the two involutions, i.e. i − 1 and i + 1 interchange positions. Therefore in the end, d̃_{i}(ϕ^{(2)}(w)) = ϕ^{(2)}(w̃) if i − 1, i, i + 1 are adjacent in ϕ^{(2)}(w), and d_{i}(ϕ^{(2)}(w)) = ϕ^{(2)}(w̃) otherwise. □

Recall that the sum over of an equivalence class is determined by the quasisymmetric functions associated to the permutations of the class. Since the quasisymmetric function associated to a permutation is determined by the inverse descent set of the permutation, Proposition 3.1 (iii) and Remark 5.2 establish the following corollary to Theorem 5.3.

Corollary 5.4. Macdonald polynomials indexed by partitions with 2 columns are Schur positive.

For k ≥ 3, it is not possible for ϕ^{(k)} (D_{i}^{(k−1)}(w)) = D_{i}^{(k)} (ϕ^{(k)}(w)) in general. The reason for this is that the sizes of the k-equivalence classes increase with k. For permutations of length n, the n-equivalence classes have a nice description given in [Ass07a] allowing us to prove the following.

Theorem 5.5. For w a permutation such that i does not lie between i − 1 and i + 1, we have

(23)  ϕ^{[1,n]}(w) ∼_{n} ϕ^{[1,n]} (D_{i}^{(1)}(w)) .

Proof. For this case, maj_{n} = inv in the usual sense and there are no n-descents to consider. As already noted, inv is constant on n-equivalence classes and, since D_{i}^{(n)} ≡ d̃_{i}, w_{1} > w_{n} for some w in an n-class if and only if w_{1} > w_{n} for every w in an n-class. Furthermore, it is not difficult to show that these two properties completely characterize n-classes. Since D_{i}^{(1)} ≡ d_{i}, w_{n−1} > w_{n} for some w in a 1-class if and only if w_{n−1} > w_{n} for every w in a 1-class. By Proposition 3.3, maj(w) = inv(ϕ^{[1,n]}(w)), and by Proposition 3.1 (ii), w_{n−1} > w_{n} if and only if ϕ^{[1,n]}(w)_{1} > ϕ^{[1,n]}(w)_{n}. Therefore if w ∼_{1} u, then inv(ϕ^{[1,n]}(w)) = inv(ϕ^{[1,n]}(u)), and ϕ^{[1,n]}(w)_{1} > ϕ^{[1,n]}(w)_{n} if and only if ϕ^{[1,n]}(u)_{1} > ϕ^{[1,n]}(u)_{n}. The result now follows. □

Corollary 5.6. Macdonald polynomials indexed by a single row are Schur positive.

Given this, one might still hope to express each k-equivalence class as a union of the images of certain k − 1-equivalence classes under an appropriate map. However, for k ≥ 3, neither ϕ^{(k)} nor the corresponding composition of Kadell’s bijections accomplishes this. There is, however, considerable evidence suggesting that such a family of bijections does exist, and so we conclude with the following conjecture.

Conjecture 5.7. There exists a family of bijections θ^{(k)} on permutations satisfying Propositions 3.1 and 3.3 such that if w ∼_{k−1} u then θ^{(k)}(w) ∼_{k} θ^{(k)}(u).

The main corollary to Conjecture 5.7 would be a simple, elementary combinatorial proof of Macdonald positivity. Furthermore, if these bijections are found and can be extended to tableaux as in Section 4, then this would also give a combinatorial formula for the Schur coefficients of Macdonald polynomials in terms of standard Young tableaux. By Theorem 5.3 and the constructions in Section 4, we recover the formula for the Schur coefficients of Macdonald polynomials indexed by 2 columns given in [HHL05a]. Finding such a formula in general remains an important open problem in the theory of Macdonald polynomials.

References

[Ass07a] S. Assaf, A combinatorial proof of LLT and Macdonald positivity, preprint, 2007.

[Ass07b] , The Schur expansion of Macdonald polynomials, preprint, 2007.

[CF95] R. Clarke and D. Foata, Eulerian Calculus, II: An extension of Han’s fundamental transformation, European J. Combin. 16 (1995), 221–252.

[Foa68] D. Foata, On the Netto inversion number of a sequence, Proc. Amer. Math. Soc. 19 (1968), 236–240.

[FS78] D. Foata and M.-P. Schützenberger, Major index and inversion number of permutations, Math. Nachr. 83 (1978), 143–159.

[GH07] I. Grojnowski and M. Haiman, Affine Hecke algebras and positivity of LLT and Macdonald polynomials, preprint, 2007.

[Hag04] J. Haglund, A combinatorial model for the Macdonald polynomials, Proc. Natl. Acad. Sci. USA 101 (2004), no. 46, 16127–16131 (electronic).

[Hai92] M. Haiman, Dual equivalence with applications, including a conjecture of Proctor, Discrete Math. 99 (1992), no. 1-3, 79–113.

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

[HHL05a] J. Haglund, M. Haiman, and N. Loehr, A combinatorial formula for Macdonald polynomials, J. Amer. Math. Soc. 18 (2005), no. 3.

[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 Math. J. 126 (2005), no. 2, 195–232.

[HS07] J. Haglund and L. Stevens, An extension of the Foata map to standard Young tableaux, Sém. Lothar. Combin. 56 (2006/07), Art. B56c, 15 pp. (electronic).

[Kad85] K. W. J. Kadell, Weighted inversion numbers, restricted growth functions, and standard Young tableaux, J. Combin. Theory Ser. A 40 (1985), no. 1, 22–44.

[Mac13] P. A. MacMahon, The Indices of Permutations and the Derivation Therefrom of Functions of a Single Variable Associated with the Permutations of any Assemblage of Objects, Amer. J. Math. 35 (1913), no. 3, 281–322.

[Mac16] , Two applications of general theorems in combinatory analysis, Proc. London Math. Soc. 15 (1916), 314–321.

[Mac88] I. G. Macdonald, A new class of symmetric functions, Actes du 20e Séminaire Lotharingien de Combinatoire, Publ. I.R.M.A. Strasbourg, 1988, 372/S-20, pp. 131–171; Sém. Lotharingien Combin. 20 (1988), Art. B20a (electronic).

[Raw81] D. Rawlings, The r-major index, J. Combin. Theory Ser. A 31 (1981), no. 2, 175–183.

Department of Mathematics, University of Pennsylvania, Philadelphia, PA 19104 Current address: Department of Mathematics, Massachusetts Institute of Technology, 77 Massachusetts

Avenue, Cambridge, MA 02139-4307

E-mail address: sassaf@math.mit.edu