# A bijective proof of a factorization formula for Macdonald polynomials at roots of unity

F. Descouens<fnref n="1" />†, H. Morita<fnref n="2" />‡ and Y. Numata<fnref n="3" />

**Abstract.** We give a combinatorial proof of the factorization formula of modified Macdonald polynomials $\tilde{H}_{\lambda}(X; q, t)$ when $t$ is specialized at a primitive root of unity. Our proof is restricted to the special case where $\lambda$ is a two columns partition. We mainly use the combinatorial interpretation of Haiman, Haglund and Loehr giving the expansion of $\tilde{H}_{\lambda}(X; q, t)$ on the monomial basis.

**Résumé.** Nous présentons une preuve combinatoire de la formule de factorisation des polynômes de Macdonald modifiés $\tilde{H}_{\lambda}(X; q, t)$ quand $t$ est spécialisé à une racine primitive de l’unité. Notre preuve se restreint au cas particulier des partitions $\lambda$ n’ayant que deux colonnes. On utilise principalement l’interprétation combinatoire de Haglund, Haiman and Loehr donnant le développement de $\tilde{H}_{\lambda}(X; q, t)$ sur la base des fonctions monomiales.

**Keywords:** Macdonald polynomials, roots of unity

## 1 Introduction

The different versions of Macdonald polynomials have been intensively studied from a combinatorial and algebraic approach since their introduction in [M1]. These polynomials are deformations with two parameters of usual symmetric functions and generalize the Hall-Littlewood functions. We are mainly interested in the modified version of Macdonald polynomials $\tilde{H}_{\lambda}(X; q, t)$. In [HHL], Haglund, Haiman and Loehr give a combinatorial interpretation of the expansion of these modified Macdonald polynomials in the monomial basis. This combinatorial interpretation is based on the definition of two statistics $inv(T)$ and $maj(T)$ on the set $\mathcal{F}_{\mu,\nu}$ of all the fillings $T$ of a given shape $\mu$ and evaluation $\nu$. Hence, we have the following formula

$$ \tilde{H}_{\mu}(X; q, t) = \sum_{\nu} \left( \sum_{T \in \mathcal{F}_{\mu, \nu}} q^{\mathrm{inv}(T)} t^{\mathrm{maj}(T)} \right) X^T . $$

<footnote n="1">¹ Fields Institute, 222 College Street, Toronto, Ontario, M5T 3J1, Canada. fdescoue@fields.utoronto.ca</footnote>

<footnote n="2">² Oyama National College of Technology, Nakakuki 771, Oyama, 323-0806, Japan. morita@oyama-ct.ac.jp</footnote>

<footnote n="3">³ Department of Mathematics, Hokkaido University, Kita 10, Nishi 8, Kita-Ku, Sapporo, Hokkaido, 060-0810, Japan. nu@math.sci.hokudai.ac.jp</footnote>

<footnote>†The first author is partially supported by the NSF Focus Research Group NSF 06-580.</footnote>

<footnote>‡The second author is partially supported by Grant-in-Aid for Scientific Research (C) 19540155, Japan Society for the Promotion of Science.</footnote>
In [DM], the authors give an algebraic proof of factorization formulas for these polynomials, when the parameter $t$ is specialized at primitive roots of unity. More precisely, for any positive integer $n$ and any partition $\mu$ such that $\mu = (\mu', n^l, \mu'')$, we have

$$ \tilde{H}_{\mu}(X; q, \zeta_l) = \tilde{H}_{(\mu', \mu'')}(X; q, \zeta_l) \cdot \tilde{H}_{(n^l)}(X; q, \zeta_l), \quad (1) $$

where $\zeta_l$ is an $l$-th primitive root of unity. We propose to give a combinatorial proof of this formula in the special case where $\mu'' = \emptyset$ and $n = 1$ or $2$.

## 2 Combinatorial interpretation for Macdonald polynomials

We mainly follow the notations of [M2] for symmetric functions. We recall the combinatorial interpretation of the expansion of modified Macdonald polynomials on the monomials basis given in [HHL].

A partition $\lambda$ is a sequence of positive integers $(\lambda_1, \dots, \lambda_n)$ such that $\lambda_1 \ge \dots \ge \lambda_n$. We represent such a partition by its Young diagram using the French convention. For a given cell $u$ of $\lambda$, the arm of $u$, denoted by $\text{arm}(u)$, is the number of cells strictly to the right of $u$. The leg of $u$, denoted by $\text{leg}(u)$, is the number of cells strictly above $u$.

**Example 2.1** The partition $(4, 3, 2)$ can be represented by the following diagram

<figure><img src="image_1.png" /></figure>

For the cell $\bullet$, we have $\text{arm}(\bullet) = 2$ and $\text{leg}(\bullet) = 1$.

We call $T$ a filling of shape $\lambda$ if $T$ is a tableau obtained by assigning integer entries to the cells of the diagram of $\lambda$ with no increasing conditions. The evaluation of a filling $T$ is the vector where the $i$-th entry is the number of cells labeled by $i$ in $T$. The set of all the fillings of shape $\lambda$ and evaluation $\mu$ is denoted by $\mathcal{F}_{\lambda, \mu}$.

A descent of a filling $T$ is a pair of cells satisfying the following condition

$$ T_{i+1,j} > T_{i,j}. $$

For a given filling $T$, we define the set $\text{Des}(T)$ of the descents of $T$ by

$$ \text{Des}(T) = \{T_{i+1,j} \text{ such that } T_{i+1,j} > T_{i,j}\}. $$

The statistic $\text{maj}(T)$ is defined by

$$ \text{maj}(T) = \sum_{u \in \text{Des}(T)} (\text{leg}(u) + 1). $$

**Example 2.2** The following tableau is a filling of shape $(4, 3, 2)$ and evaluation $(1, 2, 1, 3, 0, 1, 0, 1)$:

<figure><img src="image_2.png" /></figure>
The descent set of this filling is $\text{Des}(T) = \{(3, 1), (2, 3)\}$. Hence,

$$ \text{maj}(T) = 2. $$

Two cells of a filling are said to attack each other if either

1. they are in the same row, or

2. they are in consecutive rows, with the cell in the upper row strictly to the right of the one in the lower row.

**Example 2.3** The following picture shows the two kinds of attacking cells:

<figure><img src="image_3.png" /></figure>

The reading order of a filling is the row by row reading from top to bottom and left to right within each row. A pair $(u, v)$ of cells is an inversion if they satisfy the three following conditions:

1. they are attacking each others,

2. $T_u < T_v$, and

3. the cell $v$ appears before the cell $u$ in the reading order.

The number of inversions of $T$ is denoted by $\text{Inv}(T)$. The statistic $\text{inv}(T)$ is defined by

$$ \text{inv}(T) = \text{Inv}(T) - \sum_{u \in \text{Des}(T)} \text{arm}(u). $$

**Example 2.4** For the filling $T$ of Example 2.2, we have $\text{inv}(T) = 8 - 1 = 7$.

**Theorem 2.5 ([HHL])** The modified Macdonald polynomial $\tilde{H}_{\mu}(x; q, t)$ has a description as the following weighted generating function over fillings of shape $\mu$

$$ \tilde{H}_{\mu}(X; q, t) := \sum_{\nu} \sum_{T \in \mathcal{F}_{\mu, \nu}} q^{\text{inv}(T)} t^{\text{maj}(T)} X^T, $$

where the sum is over all the compositions $\nu$ of size $|\mu|$.

**Theorem 2.6 ([DM])** For any positive integer $n$ and any partition $\mu$ such that $\mu = (\mu', n^l, \mu'')$, we have

$$ \tilde{H}_{\mu}(X; q, \zeta_l) = \tilde{H}_{(\mu', \mu'')}(X; q, \zeta_l) \cdot \tilde{H}_{(n^l)}(X; q, \zeta_l), $$

where $\zeta_l$ is an $l$-th primitive root of unity.

We now give some technical definitions on fillings, which are needed later in our proof.
**Definition 2.7** For any partition $\mu$, we define the sets $\text{Att}_i(\mu)$ and $\text{Att}_{i,i-1}(\mu)$ of pairs of boxes of $\mu$ by

$$ \text{Att}_i(\mu) := \{ ((i,j), (i,k)) \mid 1 \le j < k \le \mu_i \}, \\ \text{Att}_{i,i-1}(\mu) := \{ ((i,j), (i-1,k)) \mid 1 \le j < k \le \mu_i \}. $$

The union of these two sets gives us the attacking cells of $\mu$ coming from its i-th row.

**Definition 2.8** For a filling $T$ of shape $\mu$, we define the set $\text{Des}_{i,i-1}(T)$ of pairs of boxes of $\mu$ by

$$ \text{Des}_{i,i-1}(T) := \{ (i,j) \in \mu \mid T_{i,j} > T_{i-1,j} \}. $$

This set is the restriction of the descents set $\text{Des}(T)$ to the descents which occurs in the i-th row of $\mu$. Let us now define the following restrictions of the quantities $\sum_{u \in \text{Des}(T)} \text{arm}(u)$ and $\sum_{u \in \text{Des}(T)} \text{leg}(u)$

$$ \text{arm}_{i,i-1}(T) := \sum_{b \in \text{Des}_{i,i-1}(T)} \text{arm}(b), $$

$$ \text{maj}_{i,i-1}(T) := \sum_{b \in \text{Des}_{i,i-1}(T)} (1 + \text{leg}(b)). $$

**Example 2.9** For the following filling $T$

$$ \begin{bmatrix} 1 \\ 4 & 7 \\ 3 & 2 \\ 5 & 6 \end{bmatrix}, $$

the set $\text{Des}_{3,2}(T) = \{ (3,1), (3,2) \}$ consists of the boxes where 4 and 7 lie. The sets $\text{Des}_{2,1}(T)$ and $\text{Des}_{4,3}(T)$ are reduced to the empty set. Hence we have

$$ \text{arm}_{3,2}(T) = 1 + 0 = 1, $$

$$ \text{arm}_{2,1}(T) = \text{arm}_{4,3}(T) = 0, $$

$$ \text{maj}_{3,2}(T) = 2 + 1 = 3, $$

$$ \text{maj}_{2,1}(T) = \text{maj}_{4,3}(T) = 0. $$

**Definition 2.10** We define the subset $\text{Inv}_i(T)$ (resp. $\text{Inv}_{i,i-1}(T)$) of $\text{Att}_i(T)$ (resp. $\text{Att}_{i,i-1}(T)$) by

$$ \text{Inv}_i(T) := \{ (b,c) \in \text{Att}_i(\mu) \mid T_b > T_c \}, \\ \text{Inv}_{i,i-1}(T) := \{ (b,c) \in \text{Att}_{i,i-1}(\mu) \mid T_b > T_c \}. $$

The union of these sets gives us the inversions of $T$ which are coming from the i-th row of $\mu$. Let now define the corresponding restriction of the statistic $\text{inv}(T)$ by

$$ \text{inv}_{i,i-1}(T) := |\text{Inv}_i(T)| + |\text{Inv}_{i,i-1}(T)| - \text{arm}_{i,i-1}(T). $$

**Example 2.11** For the filling $T$ of Example 2.9, we have

$$ \text{Inv}_2(T) = \{ (2,1), (2,2) \}, $$

$$ \text{Inv}_1(T) = \text{Inv}_3(T) = \text{Inv}_4(T) = \emptyset, $$

$$ \text{Inv}_{3,2}(T) = \{ (2,1), (3,2) \}, $$

$$ \text{Inv}_{2,1}(T) = \text{Inv}_{4,3}(T) = \emptyset. $$
Hence we have

$$ \mathrm{inv}_{2,1}(T) = 1 + 0 - 0 = 1, $$

$$ \mathrm{inv}_{3,2}(T) = 0 + 1 - 1 = 0, $$

$$ \mathrm{inv}_{4,3}(T) = 0 + 0 - 0 = 0. $$

Using all these restrictions, we can express the statistics maj($T$) and inv($T$) by

$$ \mathrm{maj}(T) := \sum_{i=2}^{l(\mu)} \mathrm{maj}_{i,i-1}(T) \quad \text{and} \quad \mathrm{inv}(T) := |\mathrm{Inv}_1(T)| + \sum_{i=2}^{l(\mu)} \mathrm{inv}_{i,i-1}(T). $$

**Example 2.12** Let $T$ be the filling of Example 2.9. From computations of Examples 2.9 and 2.11, we obtain the following statistics

$$ \mathrm{maj}(T) = 0 + 3 + 0 = 3 \quad \text{and} \quad \mathrm{inv}(T) = 0 + (1 + 0 + 0) = 1. $$

## 3 Main results

For two compositions $\nu' = (\nu'_1, \dots, \nu'_k)$ and $\nu'' = (\nu''_1, \dots, \nu''_k)$, $\nu' + \nu''$ denotes the composition $(\nu'_1 + \nu''_1, \dots, \nu'_k + \nu''_k)$. Let $\mu$ be a partition such that $\mu = (\mu', n^l, \mu'')$ such that $\mu'_{l(\mu')} \ge n$ and $\mu''_1 \le n$. In order to prove combinatorially Theorem 2.6, we have to define two bijections $\tau$ and $\pi^*$ between different sets of fillings

$$ \left\{ \begin{array}{rcl} \tau: & \mathcal{F}_{\mu,\nu} & \to \mathcal{F}_{\mu,\nu}, \\ \pi^*: & \mathcal{F}_{\mu,\nu} & \to \bigcup_{\nu=\nu'+\nu''} \mathcal{F}_{(\mu',\mu''),\nu'} \times \mathcal{F}_{(n^l),\nu''}, \end{array} \right. $$

with

$$ \left\{ \begin{array}{l} \mathrm{maj}(\tau(T)) \equiv \mathrm{maj}(\pi^*(T)) \pmod l, \\ \mathrm{inv}(\tau(T)) = \mathrm{inv}(\pi^*(T)). \end{array} \right. $$

The definition of the statistics maj and inv are extended on couples of fillings by

$$ \left\{ \begin{array}{l} \mathrm{maj}(\pi^*(T)) := \mathrm{maj}(\pi^*(T)_1) + \mathrm{maj}(\pi^*(T)_2), \\ \mathrm{inv}(\pi^*(T)) := \mathrm{inv}(\pi^*(T)_1) + \mathrm{inv}(\pi^*(T)_2). \end{array} \right. $$

We restrict ourselves to the case $n = 1$ or 2 and Young diagrams $\mu$ with tails, i.e.,

$$ \mu = (\mu', n^l) \quad \text{and} \quad \mu'_{l(\mu')} \ge n. $$

Hence, the factorization formula (1) becomes

$$ \tilde{H}_{(\mu', n^l)}(X; q, \zeta_l) = \tilde{H}_{\mu'}(X; q, \zeta_l) \cdot \tilde{H}_{(n^l)}(X; q, \zeta_l). $$

For the factorization in the case when $n = 1$ or 2, we give a bijective proofs in Theorems 3.2 and 3.10, and the proofs are detailed in Section 4.
Let $\pi: \mu' \cup (n^l) \to \mu = (\mu', n^l)$ be the natural bijection, i.e.,

$$ \begin{cases} \pi(i,j) = (i,j) & \text{if } (i,j) \in \mu', \\ \pi(i,j) = (i+l(\mu'),j) & \text{if } (i,j) \in (n^l). \end{cases} $$

The map $\pi$ on partitions induces the following bijection on fillings

$$ \pi^*: \mathcal{F}_{\mu,\nu} \to \bigcup_{\nu=\nu'+\nu''} \mathcal{F}_{\mu',\nu'} \times \mathcal{F}_{(n^l),\nu''}, \qquad (2) $$

defined for all $T$ in $\mathcal{F}_{\mu,\nu}$ by

$$ \begin{cases} (\pi^*(T))_1 = (T_{i,j})_{(i,j) \in \mu'}, \\ (\pi^*(T))_2 = (T_{i+l(\mu'),j})_{(i,j) \in (n^l)}. \end{cases} $$

**Proposition 3.1** For a filling $T$ of shape $\mu$, let $(T', T'')$ be an element of $\mathcal{F}_{\mu',\nu'} \times \mathcal{F}_{(n^l),\nu''}$ satisfying the condition $\pi^*(T) = (T', T'')$. Then

$$ \begin{align*} \pi^{*-1}(\mathrm{Des}_{i+1,i}(T)) &= \mathrm{Des}_{i+1,i}(T'), & \pi^{*-1}(\mathrm{Des}_{k+i+1,k+i}(T)) &= \mathrm{Des}_{i+1,i}(T''), \\ \pi^{*-1}(\mathrm{Inv}_{i+1,i}(T)) &= \mathrm{Inv}_{i+1,i}(T'), & \pi^{*-1}(\mathrm{Inv}_{k+i+1,k+i}(T)) &= \mathrm{Inv}_{i+1,i}(T''), \\ \pi^{*-1}(\mathrm{Inv}_i(T)) &= \mathrm{Inv}_i(T'), & \pi^{*-1}(\mathrm{Inv}_{k+i}(T)) &= \mathrm{Inv}_i(T''). \end{align*} $$

Hence we have the following equations

$$ \begin{align*} \mathrm{maj}_{i,i-1}(T) &= \mathrm{maj}_{i,i-1}(T') + l \cdot |\mathrm{Des}_{i,i-1}(T')|, & \mathrm{maj}_{k+i,k+i-1}(T) &= \mathrm{maj}_{i,i-1}(T''), \\ \mathrm{inv}_{i,i-1}(T) &= \mathrm{inv}_{i,i-1}(T'), & \mathrm{inv}_{k+i,k+i-1}(T) &= \mathrm{inv}_{i,i-1}(T''). \end{align*} $$

This implies the following expression for $\mathrm{maj}(T)$ and $\mathrm{inv}(T)$

$$ \left\{ \begin{array}{l} \mathrm{maj}(T) \equiv \mathrm{maj}(T') + \mathrm{maj}(T'') + \mathrm{maj}_{l(\mu')+1,l(\mu')}(T) \pmod l, \\ \mathrm{inv}(T) = \mathrm{inv}(T') + \mathrm{inv}(T'') + |\mathrm{Inv}_{l(\mu')+1,l(\mu')}| - \mathrm{arm}_{l(\mu')+1,l(\mu')}(T). \end{array} \right. $$

### 3.1 The case $n=1$

Let $\mu$ be a partition of the form $\mu = (\mu'_1, \dots, \mu'_k, 1^l)$. In this special case, we have

$$ \mathrm{Att}_{k+1,k} = \emptyset \quad \text{and} \quad \mathrm{Inv}_{k+1,k}(T) = \emptyset. $$

The cell $b = (k+1, 1) \in \mu$ is the unique candidate for being an element of $\mathrm{Des}_{k+1,k}(T)$. Hence

$$ \mathrm{arm}(b) = 0. $$

Consequently $\mathrm{arm}_{k+1,k}(T) = 0$ and $\mathrm{inv}(T) = \mathrm{inv}(\pi(T))$.

Since $\mathrm{maj}_{k+1,k}(T) = l|\mathrm{Des}_{k+1,k}(T)|$ and $\mathrm{maj}_{k+1,k}(T) \equiv 0 \pmod l$, we have

$$ \mathrm{maj}(T) \equiv \mathrm{maj}(\pi(T)) \pmod l. $$

Hence, we can take the identity map $\mathrm{id}$ for $\tau$ in order to obtain a combinatorial proof of Theorem 2.6 in the case $n=1$.
**Theorem 3.2** For a partition $\mu = (\mu'_1, \dots, \mu'_k, 1^l)$, let $\pi: \mu' \cup (1^l) \to \mu$ be the natural bijection and $\pi^*: \mathcal{F}_{\mu,\nu} \to \bigcup \mathcal{F}_{\mu',\nu'} \times \mathcal{F}_{(1^l),\nu''}$ be the bijection induced by $\pi$ as defined in (2). Let $\tau$ be the identity map on $\mathcal{F}_{\mu,\nu}$. Then $\pi^*$ and $\tau$ satisfy

$$ \left\{ \begin{array}{l} \mathrm{maj}(\tau(T)) \equiv \mathrm{maj}(\pi^*(T)) \pmod l, \\ \mathrm{inv}(\tau(T)) = \mathrm{inv}(\pi^*(T)). \end{array} \right. $$

**Example 3.3** Let us consider the case $l=3$ and $\mu = (2, 2, 1, 1, 1)$. In this case, we have

$$ \mathrm{maj} \left( \begin{array}{|c|c|c|c|c|} \hline \mathbf{2} \\ \hline \mathbf{1} \\ \hline \mathbf{3} \\ \hline \mathbf{2} & \mathbf{3} \\ \hline \mathbf{1} & \mathbf{2} \\ \hline \end{array} \right) = 1+3+4+1=9, \quad \mathrm{maj} \left( \begin{array}{c|c} \mathbf{2} & \mathbf{3} \\ \hline \mathbf{1} & \mathbf{2} \end{array} \right) + \mathrm{maj} \left( \begin{array}{c|c} \mathbf{2} \\ \hline \mathbf{1} \\ \hline \mathbf{3} \end{array} \right) = (1+1)+1=3, $$

$$ \mathrm{inv} \left( \begin{array}{c|c|c|c|c|} \mathbf{2} \\ \hline \mathbf{1} \\ \hline \mathbf{3} \\ \hline \mathbf{2} & \mathbf{3} \\ \hline \mathbf{1} & \mathbf{2} \\ \hline \end{array} \right) = 1-1=0, \quad \mathrm{inv} \left( \begin{array}{c|c} \mathbf{2} & \mathbf{3} \\ \hline \mathbf{1} & \mathbf{2} \end{array} \right) + \mathrm{inv} \left( \begin{array}{c|c} \mathbf{2} \\ \hline \mathbf{1} \\ \hline \mathbf{3} \end{array} \right) = (1-1)+0=0. $$

## 3.2 The case $n=2$

First we determine two conditions in order to define the appropriate $\tau$. We first define some technical conditions on fillings which we will permit us to define the elementary steps of Algorithm 3.7.

**Definition 3.4 (Condition $xAx$)** A filling $\begin{bmatrix} a & b \\ A \end{bmatrix}$ satisfies the condition $xAx$ if one of the following conditions holds
$$ a \le A < b \quad \text{or} \quad b \le A < a. $$

**Definition 3.5 (Condition $xXxX$)** A filling $\begin{bmatrix} a & b \\ A & B \end{bmatrix}$ satisfies the condition $xXxX$ if one of the following conditions holds
$$ \begin{array}{ll} a \le A < b \le B, & A < b \le B < a, \\ b \le A < a \le B, & A < a \le B < b, \\ a \le B < b \le A, & B < b \le A < a, \\ b \le B < a \le A, & B < a \le A < b. \end{array} $$

**Proposition 3.6** We have the following property on the conditions $xAx$ and $xXxX$

1. If a filling $\begin{bmatrix} a & b \\ A \end{bmatrix}$ satisfies the condition $xAx$, then $\begin{bmatrix} b & a \\ A \end{bmatrix}$ also satisfies the condition $xAx$,

2. If a filling $\begin{bmatrix} a & b \\ A & B \end{bmatrix}$ satisfies the condition $xXxX$, then $\begin{bmatrix} b & a \\ B & A \end{bmatrix}$ also satisfies the condition $xXxX$.

We give an algorithm which permits to determine $\tau$ for any filling of shape $\mu = (\mu'_1, \dots, \mu'_k, 2^l)$ with $\mu'_k \ge 2$.
**Algorithm 3.7 (Definition of τ)**

* **Input:** A filling $T$ and $k$.

* **Procedure**

▷ Initialization of variables

(a) $i \leftarrow k$,

(b) $T' \leftarrow T$.

▷ If the $i$-th row and the $(i+1)$-th row of $T'$ satisfy the condition $xAx$ do

(a) swap the two values in the $(i+1)$-th row of $T'$,

(b) $i \leftarrow i + 1$.

else return $T'$.

▷ While the $i$-th row and the $(i+1)$-th row of $T'$ satisfy the condition $xXxX$ do

(a) swap the two values in $(i+1)$-th row of $T'$,

(b) $i \leftarrow i + 1$.

* **Output:** The filling $T'$.

**Example 3.8** For $l = 5$ and the following filling $T$, the steps of the algorithm are

$$ T = \begin{array}{c} \begin{array}{|c|c|} \hline 1 & 4 \\ \hline 3 & 5 \\ \hline 2 & 6 \\ \hline 1 & 3 \\ \hline \mathbf{2} & \mathbf{4} \\ \hline \mathbf{3} & 3 \\ \hline 4 & 4 \end{array} & \longrightarrow \begin{array}{c} \begin{array}{|c|c|} \hline 1 & 4 \\ \hline 3 & 5 \\ \hline 2 & 6 \\ \hline \mathbf{1} & \mathbf{3} \\ \hline \mathbf{4} & \mathbf{2} \\ \hline 3 & 3 \\ \hline 4 & 4 \end{array} & \longrightarrow \begin{array}{c} \begin{array}{|c|c|} \hline 1 & 4 \\ \hline 3 & 5 \\ \hline \mathbf{2} & \mathbf{6} \\ \hline \mathbf{3} & \mathbf{1} \\ \hline 4 & 2 \\ \hline 3 & 3 \\ \hline 4 & 4 \end{array} & \longrightarrow \begin{array}{c} \begin{array}{|c|c|} \hline 1 & 4 \\ \hline 3 & 5 \\ \hline 6 & 2 \\ \hline 3 & 1 \\ \hline 4 & 2 \\ \hline 3 & 3 \\ \hline 4 & 4 \end{array} & \longrightarrow \mathbf{\tau}(T) \end{array} \end{array} $$

We have put in bold the cells which occur at each step of the algorithm. The first step corresponds to the condition $xAx$ and the others to the condition $xXxX$.

**Proposition 3.9** The application $\tau$ determined by the Algorithm 3.7 is an involution and a bijection.

**Proof:** The fact that $\tau$ is an involution follows directly from Proposition 3.6. Moreover, as each step of the Algorithm 3.7 is invertible, the map $\tau$ is a bijection on $\mathcal{F}_{\mu,\nu}$. $\square$

**Theorem 3.10** For a partition $\mu = (\mu'_1, \dots, \mu'_k, 2^l)$ such that $\mu'_k \ge 2$, let $\pi^*$ be the natural bijection defined in (2), and $\tau$ be the involution determined by Algorithm 3.7. Then $\pi^*$ and $\tau$ satisfy

$$ \left\{ \begin{array}{lcl} \mathrm{maj}(\tau(T)) & = & \mathrm{maj}(\pi^*(T)) \pmod l, \\ \mathrm{inv}(\tau(T)) & = & \mathrm{inv}(\pi^*(T)). \end{array} \right. $$
**Example 3.11** Let $l = 5$ and $T$ be the filling of Example 3.8. For the statistic maj, we have

$$
\left\{
\begin{array}{l}
\text{maj}(\tau(T)) = \text{maj} \begin{pmatrix} 1 & 4 \\ 3 & 5 \\ 6 & 2 \\ 3 & 1 \\ 4 & 2 \\ 3 & 3 & 3 \\ 4 & 4 & 4 \end{pmatrix} = 13, \\[1.5em]
\text{and} \\[1em]
\text{maj}(\pi^*(T)) = \text{maj} \left( \begin{smallmatrix} 3 & 3 & 3 \\ 4 & 4 & 4 \end{smallmatrix} \right) + \text{maj} \begin{pmatrix} 1 & 4 \\ 3 & 5 \\ 6 & 2 \\ 3 & 1 \\ 4 & 2 \end{pmatrix} = 0 + 8 = 8 \equiv 13 \quad \text{mod } 5.
\end{array}
\right.
$$

And for the statistic inv, we have

$$
\left\{
\begin{array}{l}
\text{maj}(\tau(T)) = \text{inv} \begin{pmatrix} 1 & 4 \\ 3 & 5 \\ 6 & 2 \\ 3 & 1 \\ 4 & 2 \\ 3 & 3 & 3 \\ 4 & 4 & 4 \end{pmatrix} = 2, \\[1em]
\text{maj}(\pi^*(T)) = \text{inv} \left( \begin{smallmatrix} 3 & 3 & 3 \\ 4 & 4 & 4 \end{smallmatrix} \right) + \text{inv} \begin{pmatrix} 1 & 4 \\ 3 & 5 \\ 6 & 2 \\ 3 & 1 \\ 4 & 2 \end{pmatrix} = 0 + 2 = 2.
\end{array}
\right.
$$

**4 Proof of the main Theorem**

In order to prove Theorem 3.10, i.e

$$
\mathrm{maj}(\pi^*(T)) \equiv \mathrm{maj}(\tau(T)) \pmod{l} \quad \text{and} \quad \mathrm{inv}(\pi^*(T)) = \mathrm{inv}(\tau(T)),
$$

we present the following five technical lemmas which follow from direct computations.

**Lemma 4.1** Let $T = \begin{bmatrix} a & b \\ A & \end{bmatrix}$ and $T' = \begin{bmatrix} b & a \\ A & \end{bmatrix}$. If $T$ satisfies the condition $xAx$, then

$$
|\mathrm{Inv}_2(T)| = \mathrm{inv}_{2,1}(T').
$$

**Lemma 4.2** If a filling $T = \begin{bmatrix} a & b \\ A & \end{bmatrix}$ does not satisfy the condition $xAx$, then

$$
|\mathrm{Inv}_2(T)| = \mathrm{inv}_{2,1}(T).
$$
**Lemma 4.3** Let $T = \begin{bmatrix} a & b \\ A & B \end{bmatrix}$ and $T' = \begin{bmatrix} a & b \\ B & A \end{bmatrix}$ be two fillings such that $T$ satisfies one of the following conditions

$$ \begin{array}{ll} a, b \le A, B, & a \le A, B < b, \\ A, B < a, b, & b \le A, B < a. \end{array} $$

Hence, we have the following relations

$$ \begin{align*} \mathrm{Des}_{2,1}(T) &= \mathrm{Des}_{2,1}(T'), \\ \mathrm{Inv}_{2,1}(T) &= \mathrm{Inv}_{2,1}(T'), \\ \mathrm{Inv}_2(T) &= \mathrm{Inv}_2(T'). \end{align*} $$

**Lemma 4.4** Let $T = \begin{bmatrix} a & b \\ A & B \end{bmatrix}$ and $T' = \begin{bmatrix} a & b \\ B & A \end{bmatrix}$ be two fillings such that $T$ satisfies one of the following conditions

$$ \begin{array}{l} A < a, b \le B, \\ B < a, b \le A. \end{array} $$

Hence, we have

$$ |\mathrm{Des}_{2,1}(T)| = |\mathrm{Des}_{2,1}(T')| \quad \text{and} \quad \mathrm{inv}_{2,1}(T) = \mathrm{inv}_{2,1}(T'). $$

**Lemma 4.5** Let $T = \begin{bmatrix} a & b \\ A & B \end{bmatrix}$ and $T' = \begin{bmatrix} b & a \\ B & A \end{bmatrix}$ be two fillings such that $T$ satisfies the condition $xXxX$. Hence, we have

$$ |\mathrm{Des}_{2,1}(T)| = |\mathrm{Des}_{2,1}(T')| \quad \text{and} \quad \mathrm{inv}_{2,1}(T) = \mathrm{inv}_{2,1}(T'). $$

**Lemma 4.6** Let $T = \begin{bmatrix} a & b \\ A & B \end{bmatrix}$ be a filling which satisfies $A \neq B$. Then, $T$ satisfies the condition $xXxX$ or the conditions used in Lemma 4.3 and 4.4.

Lemmas 4.3, 4.4 and 4.5 imply the following key lemma.

**Lemma 4.7** In Algorithm 3.7, the swapping of the value in the $i+1$-th row when the $i$-th and the $i+1$-th rows are in the condition $xXxX$ does not change the statistic $\mathrm{maj}_{i+1,i}$ and $\mathrm{inv}_{i+1,i}$.

**Proof:** If the $i$-th and $(i+1)$-th row satisfy the condition $xXxX$, then the values of the $(i+1)$-th row are different from each other. Using Lemma 4.6, we obtain that the $i$-th and $(i+1)$-th row satisfy the condition $xXxX$ or the conditions of Lemma 4.3 and 4.4. Hence, it follows from Lemmas 4.3, 4.4 and 4.5 that

$$ \mathrm{inv}_{i+1,i}(T) = \mathrm{inv}_{i+1,i}(\tau(T)). $$

The lemmas also imply $|\mathrm{Des}_{i+1,i}(T)| = |\mathrm{Des}_{i+1,i}(\tau(T))|$. In this case,

$$ \mathrm{maj}_{i+1,i}(T) = (k+l-i) |\mathrm{Des}_{i+1,i}(T)| \quad \text{and} \quad \mathrm{maj}_{i+1,i}(\tau(T)) = (k+l-i) |\mathrm{Des}_{i+1,i}(\tau(T))|. $$

Finally,

$$ \mathrm{maj}_{i+1,i}(T) = \mathrm{maj}_{i+1,i}(\tau(T)). $$

□
Now we can finish the proof of Theorem 2.6. Lemmas 4.1, 4.2 and 4.7 imply the second statement of the theorem

$$ \mathrm{inv}(\pi^*(T)) = \mathrm{inv}(\tau(T)). $$

It also follows from these lemmas that

$$ \mathrm{maj}(\pi^*(T)) + l \cdot |\mathrm{Des}_{k+1,k}(T)| = \mathrm{maj}(\tau(T)). $$

which implies the first statement on statistic maj

$$ \mathrm{maj}(\pi^*(T)) \equiv (\tau(T)) \pmod{l}. $$

**Remark 4.8** We can mention that the $(q, t)$-Kostka polynomials $K_{\lambda, \mu}(q, t)$ (coefficient of the expansion of the modified Macdonald polynomials on the Schur basis) for the special case of two columns partitions $\mu = (2^r 1^{n-2^r})$ have been studied in [S] and combinatorially interpreted with rigged configurations in [F]. An other approach using statistics on Young tableaux has been developed in [Z] and [LM].

## References

[DM] F. Descouens and H. Morita, Factorization formula for Macdonald polynomials, European Journal of Combinatorics (to appear).

[F] S. Fishel, Statistics for Special q.t-Kostka polynomials, Proc. Amer. Math. Soc. Vol. 123, No. 10, (1995), pp. 2961-2969.

[HHL] J. Haglund, M. Haiman and N. Loehr, A combinatorial formula for Macdonald polynomials, J. Amer. Math. Soc. 18, (2005), pp. 195-232.

[LM] L. Lapointe, J. Morse, Tableaux statistics for two parts Macdonald polynomials, preprint math.CO/9812001.

[M1] I.G. Macdonald, A new class of symmetric functions, Actes du 20e Séminaire Lothatingien de Combinatoire, vol. 372/S-20, Publications I.R.M.A., Strasbourg, (1998), pp. 131-171.

[M2] I.G. Macdonald, Symmetric functions and Hall polynomials, second ed. The Clarendon Press, Oxford University Press, New-York, 1995.

[S] J.R. Stembridge, Some particular entries of the two parameter Kostka matrix, Proc. Amer. Math. Soc., 121, (1994), 367-373.

[Z] M. Zabrocki, A Macdonald Vexport Operator and Tableaux Statistics for the Two-Column (q, t)-Kostka Coefficients, Electronic Journal of Combinatorics, 5, R45, (1998), 46p.