Séminaire Lotharingien de Combinatoire 52 (2004), Article B52e

DECOMPOSITION OF THE DIAGONAL ACTION OF S_{n} ON THE COINVARIANT SPACE OF S_{n} × S_{n}

F. BERGERON AND F. LAMONTAGNE

À celui qui a fait une multitude de contributions fondamentales pour faire de

L’entreprise Artistique et Scientifique Combinatoire, une Oeuvre Unificatrice, peut-être même en Xiang

à l’occasion de son soixantième anniversaire.

Abstract. The purpose of this paper is to give an explicit description of the irreducible decomposition of the bigraded S_{n}-module of coinvariants of S_{n} × S_{n}. Many of the results presented here can be extended to S_{n}^{k}, and to other finite reflection group.

Contents

1. Introduction. 2 2. Diagonal context. 4 3. Algebraic motivation. 6 4. Bigrading and bigraded Frobenius characteristic. 7 5. Plethystic notation. 8 6. S_{n}-Frobenius characteristic of the module of S_{n} × S_{n} coinvariants. 9 7. Properties of the bigraded Frobenius of coinvariants. 12 8. Trivial component. 12 9. Alternating component. 15 10. Generalities on diagrams. 15 11. Characterizations of compact diagrams. 17 12. The fundamental bijection. 19 13. Basis of symmetric coinvariants. 20 14. Strict diagrams. 21 15. Final remarks. 22 References 23

F. Bergeron is supported in part by NSERC-Canada and FQRNT-Québec.

1. Introduction.

We study, in this paper, the diagonal action of S_{n} on the space of coinvariants of S_{n}^{k}, with main emphasis on the case k = 2. We first recall some results of Artin, Shephard-Todd, and Steinberg [2, 19, 22] that hold for any finite reflection group, in order to specialize them to the symmetric group S_{n}, as well as to S_{n} × S_{n}.

Let G be a finite subgroup of GL(V), where V is a finite dimensional vector space with given basis x = x_{1}, …, x_{n}. The x_{i}’s are here considered as variables. The group G acts naturally on polynomials P (x) in ℂ[x] by

g · P (x) := P (gx),

As usual, the corresponding space of G-invariant polynomials is denoted by ℂ[x]^{G}. We also denote I_{G} the ideal (of ℂ[x]) generated by constant term free G-invariant polynomials. By definition, the coinvariant space of G is

ℂ[x]_{G} := ℂ[x]/I_{G}.  (1.1)

It is naturally graded with respect to degree and comes equipped with an action of G, since I_{G} is both invariant and homogeneous. A theorem of Steinberg states the group G is generated by reflections if and only if its coinvariant space is isomorphic to the (left) regular representation of G.

In particular, for G = S_{n} the group of permutations, one can show that I_{n} (= I_{S_{n}}) admits the set

{h_{k}(x_{k}, …, x_{n}) | 1 ≤ k ≤ n }

as a Gröbner basis. Here we are considering the lexicographic order on monomials, with the usual order x_{1} < ⋯ < x_{n} on variables. It follows from general theory that ℂ[x]_{S_{n}} can be identified to the linear span of the set^{1}

{x^{a} | a = (a_{1}, …, a_{n}) ∈ ℕ^{n}, 0 ≤ a_{i} < i },

with the classical vectorial notation for monomials:

x^{a} = x_{1}^{a_{1}} … x_{n}^{a_{n}}.

This is often called the Artin basis of ℂ[x]_{S_{n}}. It is evidently a homogeneous “basis”, and it makes apparent that the coinvariant space of S_{n} has dimension n!.

Another fundamental property of coinvariant spaces of finite groups generated by reflections, is that there is an isomorphism of graded G-modules

ℂ[x] ≃ ℂ[x]^{G} ⊗ ℂ[x]_{G}.  (1.2)

In other words, ℂ[x] is a free ℂ[x]^{G}-module. Thus every polynomial P (x) can be expressed in a unique manner (say with respect to the descent basis) as

P (x) = ∑_{σ∈S_{n}} f_{σ}(x) x_{σ},  (1.3)

with each coefficient f_{σ}(x) a symmetric polynomial.

1This is in fact a set of representatives of corresponding equivalence classes.

COINVARIANTS OF S_{n} × S_{n} 3

We recall that the Hilbert series of ℂ[x] is easily shown to be

dim_{q} ℂ[x] = \frac{1}{(1 − q)^{n}} ,

and that is well known that

dim_{q} ℂ[x]^{S_{n}} = \frac{1}{(q; q)_{n}} ,

where

(q; q)_{n} := (1 − q)(1 − q^{2}) ⋯ (1 − q^{n}).

It follows from identity (1.2), in the particular case of S_{n}, that

dim_{q} ℂ[x]_{S_{n}} = \frac{(q; q)_{n}}{(1 − q)^{n}} .  (1.4)

This is readily generalized to other groups generated by reflections.

The coinvariant space ℂ[x]_{G} is clearly isomorphic (as a graded G-module) to the space H_{G} = I_{G}^{⊥} of harmonic polynomials for G. Here I_{G}^{⊥} denotes the orthogonal complement of I_{G} for the scalar product on ℂ[x] defined as:

⟨P, Q⟩ = P (∂x)Q(x)|_{x=0}  (1.5)

In this last expression, P (∂x) is to be understood as the differential operator obtained by replacing each variable x_{i} in P (x) by the partial derivative ∂x_{i}, with respect to the variable x_{i}. Moreover, x = 0 stands for

x_{1} = ⋯ = x_{n} = 0.

From the fact that I_{G} is an ideal, it follows easily that P (x) is in H_{G} if and only if it satisfies the system of differential equations

f_{a}(∂x)P (x) = 0, a ∈ A,

where {f_{a}}_{a∈A} is any set of generators for T_{G}. This leads us to yet another characterization of groups generated by reflections. Namely, there exists an explicit polynomial Δ_{G}(x) (see [15]), such that the set of all partial derivatives of Δ_{G} (of all orders) contains a basis of H_{G}, if and only if G is a group generated by reflections.

In particular, we can explicitly describe H_{n} (= H_{S_{n}}) as the linear span of all partial derivatives of the Vandermonde determinant Δ_{n}(x), where as usual

Δ_{n}(x) = ∏_{i<j}(x_{i} − x_{j}).

In formula,

H_{n} = L_{∂}[Δ_{n}(x)]  (1.6)

where L_{∂} stands for “linear span of all derivatives of”.

The context for this paper is a “bigraded” version of the constructions outlined above in the case G = S_{n}×S_{n}. More precisely, for y = y_{1}, …, y_{n} a second set of n variables, we consider the ring R := ℂ[x, y] of polynomials in both sets of variables x and y.

Here the group S_{n} × S_{n} acts as a reflection group on R by permuting these two sets of variables independently. Namely,

(σ, τ) x_{i} = x_{σ(i)}, and (σ, τ) y_{i} = y_{τ(i)}.

Clearly this action respects the “bidegree”, where the bidegree of a monomial x^{a}y^{b} is (|a|, |b|) with

|a| = a_{1} + … + a_{n}, |b| = b_{1} + … + b_{n}.

Our purpose is to give an explicit description of the irreducible decomposition of the coinvariant module R_{S_{n}×S_{n}} (or equivalently the module H_{S_{n}×S_{n}} of (S_{n} × S_{n})- harmonics) considered as an S_{n}-module under the diagonal action. We want this decomposition to take into account the natural bigrading with respect to bidegree (degree in x and degree in y). We further plan to make explicit^{2} the isomorphism of S_{n}-modules corresponding to (1.2). Among other things, such a decomposition gives rise to beautiful bijections. One of these is between n element subsets of ℕ × ℕ and triples (D_{σ}, λ, μ), with λ and μ partitions with at most n parts. The D_{σ}’s, appearing in this bijection, belong to a special class of n element subsets of ℕ × ℕ, that we call compact diagrams. As we will see, these compact diagrams have many nice combinatorial properties that make their study interesting on its own.

2. Diagonal context.

Let us detail further the structure of the bigraded components R_{j,k}, of bidegree (j, k), of the ring R = ℂ[x, y]. Clearly R_{j,k} affords as a basis the set of monomials

{ x^{a}y^{b} | |a| = j and |b| = k },

with a, b ∈ ℕ^{n}. On the other hand, monomials x^{a}y^{b} are clearly in bijection with bipartite compositions

(a, b) := ((a_{1}, b_{1}), (a_{2}, b_{2}), …, (a_{n}, b_{n})),

with some of the (a_{i}, b_{i})’s possibly equal to (0, 0). We will often use a matrix notation for these bipartite compositions:

(a, b) = (\begin{matrix}a_{1} & a_{2} & … & a_{n} \\ b_{1} & b_{2} & … & b_{n} \end{matrix})

Now, when |a| = j and |b| = k, we say that (a, b) is a bipartite composition of (j, k), and clearly,

(j, k) = (a_{1}, b_{1}) + (a_{2}, b_{2}) + … + (a_{n}, b_{n}).

The dimension of R_{j,k} is thus the number of bipartite compositions of (j, k), which is readily shown to be

dim R_{j,k} = \binom{n + j − 1}{j}\binom{n + k − 1}{k}.

2This will be completed in an upcoming paper. See section 15.

The ideal generated by constant term free (S_{n} × S_{n})-invariant polynomials, is bihomogeneous with respect to bidegree. Hence, we clearly have as generator set for it:

{h_{1}(x), h_{2}(x), …, h_{n}(x), h_{1}(y), h_{2}(x), …, h_{n}(y)}.

Using a Gröbner basis computation, with the order

x_{1} < y_{1} < x_{2} < y_{2} < … < x_{n} < y_{n}

on the variables and the lexicographic order on monomials, we can identify the space R_{S_{n}×S_{n}} with the linear span of the monomials

{x^{a}y^{b} | a_{i} < i, and b_{j} < j }.

This is thus a bihomogeneous linear basis of R_{S_{n}×S_{n}}. We naturally call this the Artin basis of of R_{S_{n}×S_{n}}.

In order to to make explicit the S_{n}-modules bigraded isomorphisms

R ≃ R^{S_{n}×S_{n}} ⊗ R_{S_{n}×S_{n}}  (2.1)
≃ R^{S_{n}×S_{n}} ⊗ H_{S_{n}×S_{n}}  (2.2)

observe that R^{S_{n}×S_{n}} is in fact isomorphic to Λ(x)⊗Λ(y), where we simply write Λ(x) for ℂ[x]^{S_{n}}. In other words, for each choice of bihomogeneous basis B of R_{S_{n}×S_{n}} (or H_{S_{n}×S_{n}}), there is a unique decomposition of polynomials P (x, y) of the form

P (x, y) = ∑_{b∈B} f_{b} b(x, y),  (2.3)

with coefficients f_{b} = f_{b}(x, y) in Λ(x) ⊗ Λ(y). If the polynomial P (x, y) is bihomogeneous of bidegree (s, t) and b(x, y) is bihomogeneous of bidegree (u, v), then the f_{b}’s can be expressed in the form

f_{b}(x, y) = _{∑_{λ⊢k} ; μ⊢j}a_{λ,μ}m_{λ}(x)m_{μ}(y),  (2.4)

with k−s−u and j = t−v. Here, λ ⊢ k means that λ = (λ_{1}, λ_{2}, …, λ_{n}) is a partition of k. Recall that this is to say that

k = |λ| := λ_{1} + λ_{2} + … + λ_{n},

with the λ_{i}’s non negative integers such that

λ_{1} ≥ λ_{2} ≥ … ≥ λ_{n} ≥ 0.

The length ℓ(λ) is the number of non zero parts λ_{i} of λ. We underline that the number of variables, n, is implicitly involved in this description as an upper bound for both ℓ(λ) and ℓ(μ). We further recall that the various bases of symmetric functions are well known (See [17]) to be naturally indexed by partitions. In particular, one such basis corresponds to the monomial symmetric polynomials m_{λ}(x) defined as:

m_{λ}(x) = ∑ x^{a},

where the sum is over all distinct permutations a = (a_{1}, a_{2}, …, a_{n}) of λ. With this in mind, (2.4) is simply making explicit the usual description of Λ(x) ⊗ Λ(y) for a particular choice of basis of Λ(x) and Λ(y).

Let us illustrate all this for n = 2. Every bihomogeneous polynomial P (x, y) of bidegree (j, k) can be expressed in a unique manner as

P (x, y) = f_{00} + f_{10}x_{2} + f_{01}y_{2} + f_{11}x_{2}y_{2},

with the f_{uv}(x, y) in Λ_{j−u}(x_{1}, y_{2})⊗Λ_{k−v}(y_{1}, y_{2}). Here, Λ_{j}(x) denotes the homogeneous component of degree j of Λ(x). For example, we have

x_{1}y_{2} + y_{1}x_{2} = m_{1}(y) x_{2} + m_{1}(x) y_{2} − 2 x_{2}y_{2}

3. Algebraic motivation.

Our main reason to study H_{S_{n}×S_{n}} is the fact that it naturally contains the now famous space of diagonal harmonics of S_{n}. Recall that this is the bigraded S_{n}-module, DH_{n}, obtained as the orthogonal complement of the ideal, J_{n}, generated by all (constant term free) diagonally symmetric polynomials. Because of this diagonal aspect, the space DH_{n} cannot appear as a special case of harmonics for some reflection groups. In fact, its structure appears to be much more complicated. It has been extensively studied in the last 15 years (see [3, 5, 11, 12, 13, 14]), and has many nice properties of its own, including the fact that its dimension is (n + 1)^{n−1}. It is clear that we have the bigraded S_{n}-modules inclusion

DH_{n} ⊂ H_{S_{n}×S_{n}},  (3.1)

since J_{n} clearly contains constant free elements of Λ(x)⊗Λ(y). Thus a more detailed understanding of H_{S_{n}×S_{n}} will shed light on the structure of DH_{n}. The point here is that H_{S_{n}×S_{n}} (or equivalently R_{S_{n}×S_{n}}) is much easier to study than DH_{n}. In particular, it is easy to see that

H_{S_{n}×S_{n}} ≃ H_{n} ⊗ H_{n}

as S_{n}-modules, with the diagonal action of S_{n} on the right hand side. ¿From the explicit description (1.6) of H_{n}, it follows that

H_{S_{n}×S_{n}} = L_{∂}[Δ_{n}(x) Δ_{n}(y)],

and the above discussion shows that the (bigraded) Hilbert series of H_{S_{n}×S_{n}} is

dim_{q,t} H_{S_{n}×S_{n}} = \frac{(q; q)_{n}}{(1 − q)^{n}} \frac{(t; t)_{n}}{(1 − t)^{n}} ,  (3.2)

which is a bigraded analog of n!^{2}. Much of this can also be formulated in the context of the coinvariant space R_{S_{n}×S_{n}}. It is sometimes more convenient to work in this latter context.

4. Bigrading and bigraded Frobenius characteristic.

In this section, the term “function”, in the expression “symmetric function”, is used to underline that we will be using infinitely many variables. The actual variables, z = z_{1}, z_{2}, z_{3}, …, only play a formal role, and will often omit to mention them. Hence we will denote s_{λ}, rather then s_{λ}(z), the usual Schur function. These “formal” symmetric functions allow a translation of computations on characters of S_{n} into the more convenient and effective context of symmetric functions through the Frobenius characteristic map.

The S_{n}-modules of the previous section (all submodules of R) are bihomogeneous with respect to bidegree. We can thus decompose them as direct sums of their bihomogeneous components, which are obtained using the usual linear projections defined on monomials as

π_{j,k}(x^{a}y^{b}) := \begin{cases}x^{a}y^{b} & |a| = j, and |b| = k \\ 0 & otherwise. \end{cases}

Recall that the bigraded Frobenius characteristic of any invariant bihomogeneous submodule V of Q[x, y] is defined to be the symmetric function

F_{V}(z; q, t) := ∑_{j,k} q^{j}t^{k} \frac{1}{n!} ∑_{σ∈S_{n}} χ_{V_{j,k}}(σ) p_{λ(σ)},  (4.1)

where χ_{V_{j,k}} is the character of the bihomogeneous component V_{j,k} = π_{j,k}(V) of V, and where λ(σ) denotes the (integer) partition describing the cycle structure of the permutation σ. As usual, we have denoted here by

p_{λ} = p_{λ}(z) := p_{λ_{1}}(z)p_{λ_{2}}(z) ⋯ p_{λ_{k}}(z)

the power sum symmetric functions, with

p_{i}(z) = z_{1}^{i} + z_{2}^{i} + z_{3}^{i} + …

Irreducible representations of S_{n} are indexed by partitions of n, and there is a natural indexing of them such that the corresponding Frobenius characteristics are the Schur functions s_{λ}. Thus, when expressed in term of Schur functions, the bigraded Frobenius characteristic of an S_{n}-module V describes the decomposition into irreducibles of each bihomogeneous component of V. Namely

F_{V}(z; q, t) = ∑_{μ⊢n} ∑_{j,k} m_{j,k}^{μ}q^{j}t^{k}s_{μ},  (4.2)

where m_{j,k}^{μ} is the multiplicity of the irreducible representation of S_{n} naturally indexed by μ. In other words, if we denote V^{μ} the isotypic component of V of type μ, for μ a partition of n, we get

F_{V}(z; q, t) = ∑_{μ⊢n} f_{V^{μ}}(q, t)s_{μ},  (4.3)

where f_{V^{μ}}(q, t) is the Hilbert series of V^{μ}. Recall that V^{μ} is the submodule of V made of all its irreducible submodules that have same character indexed by μ. We will give below explicit expressions for the bigraded Frobenius characteristic of both H_{S_{n}×S_{n}} and R_{S_{n}×S_{n}}, using plethystic notations.

5. Plethystic notation.

For any symmetric function f, expressed in term of power sum symmetric functions as:

g(z) := ∑_{μ} g_{μ} p_{μ}(z),

we set

g [\frac{z}{1 − q} ] := ∑_{μ} g_{μ} p_{μ} [\frac{z}{1 − q} ] ,

where, for a partition μ = μ_{1}μ_{2} ⋯ μ_{r},

p_{μ} [\frac{z}{1 − q} ] := ∏_{i=1}^{r} \frac{p_{μ_{i}}}{1 − q^{μ_{i}}} .

The idea here is to consider a power sum p_{k} as an operator that raises all variables (between brackets) to the power k. Hence, if one thinks that z = z_{1} + z_{2} + …, then

p_{k}(z) = p_{k}(z_{1}, z_{2}, …).

Thus, the z that appears in the above expressions stands for the variables of the symmetric functions that we are dealing with. In fact, in this context, we consider the number of variables to be infinite.

Now, let h_{n} = s_{(n)} denote the complete homogeneous symmetric functions, then

F_{ℂ[x]}(z; q) = h_{n} [\frac{z}{1 − q} ] .  (5.1)

is the graded Frobenius characteristic of the S_{n}-module of polynomials. Hence, using (1.2), one deduces that the graded Frobenius characteristic of ℂ[x]_{S_{n}} is

F_{ℂ[x]_{Sn}}(z; q) = (q; q)_{n}h_{n} [\frac{z}{1 − q} ]  (5.2)
= ∑_{λ⊢n} f_{λ}(q)s_{λ},  (5.3)

with the f_{λ}(q)’s polynomials having positive integer coefficients^{3}.

Moreover, observe that

lim_{q→1} (q; q)_{n}h_{n} [\frac{z}{1 − q} ] = h_{1}^{n},  (5.4)

3In fact, the left hand side of (5.2) is a special case of a Hall-Littlewood symmetric function (see Macdonald [17] for more details).

which is well known to be the Frobenius characteristic of the regular representation of S_{n}. It follows that each f_{λ}(q) specializes, at q = 1, to the dimension f_{λ} of the irreducible irreducible representation of S_{n} indexed by λ. It is well known that these f_{λ}’s are given by the hook length formula.

6. S_{n}-Frobenius characteristic of the module of S_{n} × S_{n} coinvariants.

One deduces, from results mentioned in section 1, that the (simply) graded Frobenius characteristic of H_{S_{n}} is precisely

F_{H_{Sn}}(z; q) = (q; q)_{n}h_{n} [\frac{z}{1 − q} ]  (6.1)

In view of (2.1), we can use this to calculate the bigraded Frobenius characteristic of H_{S_{n}×S_{n}} using the following well known fact. For two S_{n}-modules V and W,

F_{V⊗W} = F_{V} ∗ F_{W},  (6.2)

where “∗” stands for the “internal product” of symmetric functions. Recall that the internal product of two symmetric functions is the bilinear product such that

p_{λ} ∗ p_{μ} = \begin{cases}z_{μ} p_{μ} & if λ = μ, \\ 0 & otherwise, \end{cases}

where

z_{μ} = 1^{k_{1}}k_{1}!2^{k_{2}}k_{2}! ⋯ n^{k_{n}}k_{n}!,

if μ has k_{i} parts of size i. We thus easily obtain the following expression for the bigraded Frobenius characteristic of H_{S_{n}×S_{n}}, since

Theorem 6.1. We have

F_{n}(z; q, t) := F_{H_{Sn×Sn}}(z; q, t) = (q; q)_{n}(t; t)_{n} h_{n} [\frac{z}{(1 − t)(1 − q)}] .  (6.3)

For example, we have

F_{1}(z; q, t) = s_{1}
F_{2}(z; q, t) = (q t + 1)s_{2} + (q + t)s_{11}
F_{3}(z; q, t) = (q^{3}t^{3} + q^{2}t^{2} + q^{2}t + qt^{2} + qt + 1)s_{3}

+(q^{3}t^{2} + q^{2}t^{3} + q^{3}t + q^{2}t^{2} + qt^{3} + q^{2}t + qt^{2} + q^{2} + qt + t^{2} + q + t)s_{21}

+(q^{2}t^{2} + q^{3} + q^{2}t + qt^{2} + t^{3} + qt)s_{111}

Writing the coefficients of these symmetric functions as matrices gives a better idea of the nice symmetries involved in these expressions. This is to say that the coefficient of q^{i}t^{j} is the entry in position (i, j), starting at (0, 0) and going from bottom to top and left to right. Using this convention, F_{4}(z; q, t) equals to

[ \begin{matrix}0 & 0 & 0 & 0 & 0 & 0 & 1 \\ 0 & 0 & 0 & 1 & 1 & 1 & 0 \\ 0 & 0 & 1 & 1 & 2 & 1 & 0 \\ 0 & 1 & 1 & 2 & 1 & 1 & 0 \\ 0 & 1 & 2 & 1 & 1 & 0 & 0 \\ 0 & 1 & 1 & 1 & 0 & 0 & 0 \\ 1 & 0 & 0 & 0 & 0 & 0 & 0 \end{matrix} ] s_{4} + [ \begin{matrix}0 & 0 & 0 & 1 & 1 & 1 & 0 \\ 0 & 1 & 2 & 2 & 2 & 1 & 1 \\ 0 & 2 & 3 & 4 & 3 & 2 & 1 \\ 1 & 2 & 4 & 4 & 4 & 2 & 1 \\ 1 & 2 & 3 & 4 & 3 & 2 & 0 \\ 1 & 1 & 2 & 2 & 2 & 1 & 0 \\ 0 & 1 & 1 & 1 & 0 & 0 & 0 \end{matrix} ] s_{31} + [ \begin{matrix}0 & 0 & 1 & 0 & 1 & 0 & 0 \\ 0 & 1 & 1 & 2 & 1 & 1 & 0 \\ 1 & 1 & 2 & 2 & 2 & 1 & 1 \\ 0 & 2 & 2 & 4 & 2 & 2 & 0 \\ 1 & 1 & 2 & 2 & 2 & 1 & 1 \\ 0 & 1 & 1 & 2 & 1 & 1 & 0 \\ 0 & 0 & 1 & 0 & 1 & 0 & 0 \end{matrix} ] s_{22}

+ [ \begin{matrix}0 & 1 & 1 & 1 & 0 & 0 & 0 \\ 1 & 1 & 2 & 2 & 2 & 1 & 0 \\ 1 & 2 & 3 & 4 & 3 & 2 & 0 \\ 1 & 2 & 4 & 4 & 4 & 2 & 1 \\ 0 & 2 & 3 & 4 & 3 & 2 & 1 \\ 0 & 1 & 2 & 2 & 2 & 1 & 1 \\ 0 & 0 & 0 & 1 & 1 & 1 & 0 \end{matrix} ] s_{211} + [ \begin{matrix}1 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 1 & 1 & 1 & 0 & 0 & 0 \\ 0 & 1 & 2 & 1 & 1 & 0 & 0 \\ 0 & 1 & 1 & 2 & 1 & 1 & 0 \\ 0 & 0 & 1 & 1 & 2 & 1 & 0 \\ 0 & 0 & 0 & 1 & 1 & 1 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 1 \end{matrix} ] s_{1111}

We can easily reformulate formula (6.3) as

F_{H_{Sn×Sn}}(z; q, t) = ∑_{λ⊢n} f_{λ}(q, t)s_{λ}

= ∑_{λ⊢n}((q; q)_{n}(t; t)_{n} s_{λ} [\frac{1}{(1 − q)(1 − t)}])s_{λ},  (6.4)

Thus we have an explicit expression for the bigraded enumeration, f_{λ}(q, t), of irreducible representations indexed by λ in H_{S_{n}×S_{n}}. In particular, the respective bigraded dimensions of the spaces T_{n}, of diagonally symmetric harmonic polynomials, and A_{n}, of diagonally antisymmetric harmonic polynomials, are

f_{(n)}(q, t) = (q; q)_{n}(t; t)_{n} h_{n} [\frac{1}{(1 − t)(1 − q)}]  (6.5)
= ∑_{σ∈S_{n}} q^{maj(σ)}t^{maj(σ^{−1})}.

and

f_{1^{n}}(q, t) = (q; q)_{n}(t; t)_{n} e_{n} [\frac{1}{(1 − t)(1 − q)}]  (6.6)
= ∑_{σ∈S_{n}} q^{maj(σ)}t^{\binom{n}{2}−maj(σ^{−1})}.

Here we have made use of results (see [21]) regarding maj(σ), the major index of a permutation σ, defined as:

maj(σ) := _{∑_{i} ; σ(i)>σ(i+1)}i.  (6.7)

It is well known (see for instance [21]) that

∑_{σ∈S_{n}} q^{maj(σ)} = ∏_{k=1}^{n} \frac{q^{k} − 1}{q − 1},

gives a classical q-analog of n!. In general, using (5.4), one can easily derive that

f_{λ}(q, 1) = f_{λ} ∏_{k=1}^{n} \frac{q^{k} − 1}{q − 1},  f_{λ}(1, t) = f_{λ} ∏_{k=1}^{n} \frac{t^{k} − 1}{t − 1},  (6.8)
f_{λ}(q, 0) = f_{λ},  and  f_{λ}(0, t) = f_{λ}.  (6.9)

Our purpose in the following sections is to give an explicit combinatorial description of the various isotypic components of H_{S_{n}×S_{n}} (or equivalently of R_{S_{n}×S_{n}}) considered as an S_{n}-module. Before going on with this task, let us recall briefly recall (see [14] for more details) how to compute the bigraded Frobenius characteristic of DH_{n}.

Theorem 6.2 (Haiman 2002). Let ∇ be the linear operator defined in terms of the modified Macdonald symmetric functions H̃(z; q, t) by

∇H̃(z; q, t) = t^{n(μ)}q^{n(μ′)}H̃(z; q, t)  (6.10)

where n(μ) := ∑_{k}(k − 1) μ_{k}. Then we have

F_{DH_{n}}(z; q, t) = ∇(e_{n})  (6.11)

where e_{n} is the n^{th} elementary symmetric function.

The operator ∇, defined by (6.10), has been introduced by the first author with A. Garsia to study properties of Macdonald polynomials in conjunction with the study of diagonal harmonics. Many conjectures about it remain open (See [4]). For example, we have

∇(e_{1}) = s_{1}
∇(e_{2}) = s_{2} + (q + t)s_{11}
∇(e_{3}) = s_{3} + (q^{2} + qt + t^{2} + q + t)s_{21} + (t^{3} + qt^{2} + q^{2}t + qt + q^{3})s_{111}

Recently, an explicit conjecture (see [12]) for a combinatorial description of the coefficients of ∇(e_{n}), when expressed in term of the monomial basis m_{μ}, has been suggested. It should be interesting to know how this combinatorial description can be explained in the larger context of R_{S_{n}×S_{n}}. Illustrating with n = 3, this would make evident why the coefficients of the m_{λ}’s in

∇(e_{3}) = m_{3} + [ \begin{matrix}1 & 0 & 0 \\ 1 & 1 & 0 \\ 1 & 1 & 1 \end{matrix} ] m_{21} + [ \begin{matrix}1 & 0 & 0 & 0 \\ 2 & 1 & 0 & 0 \\ 2 & 3 & 1 & 0 \\ 1 & 2 & 2 & 1 \end{matrix} ] m_{111}

are “contained” in the corresponding coefficients in

F_{3}(z; q, t) = [ \begin{matrix}0 & 0 & 0 & 1 \\ 0 & 1 & 1 & 0 \\ 0 & 1 & 1 & 0 \\ 1 & 0 & 0 & 0 \end{matrix} ] m_{3} + [ \begin{matrix}0 & 1 & 1 & 1 \\ 1 & 2 & 2 & 1 \\ 1 & 2 & 2 & 1 \\ 1 & 1 & 1 & 0 \end{matrix} ] m_{2,1} + [ \begin{matrix}1 & 2 & 2 & 1 \\ 2 & 4 & 4 & 2 \\ 2 & 4 & 4 & 2 \\ 1 & 2 & 2 & 1 \end{matrix} ] m_{1,1,1}

7. Properties of the bigraded Frobenius of coinvariants.

Many symmetries are apparent in the explicit values of the bigraded Frobenius Characteristics F_{n}(z; q, t) given above. Among these, we have the following.

Proposition 7.1. For all n,

(1) F_{n}(z; t, q) = F_{n}(z; q, t)

(2) F_{n}(z; t, q) = (q t)^{\binom{n}{2}}F_{n}(z; q^{−1}, t^{−1})

(3) \begin{aligned}ω(F_{n}(z; q, t)) & = & q^{\binom{n}{2}}F_{n}(z; q^{−1}, t) \\ & = & t^{\binom{n}{2}}F_{n}(z; q, t^{−1}) \end{aligned}

Here ω is the usual involution on symmetric functions that send s_{λ} to s_{λ′} (λ′ denoting, as usual, the conjugate of λ). This is well known to correspond to “twisting” by the sign representation.

Sketch of Proof. All of these symmetries correspond to automorphisms (or anti automorphisms) of H_{S_{n}×S_{n}}.

(1) corresponds to the evident symmetry of H_{S_{n}×S_{n}} that corresponds to exchanging the x variables with the y variables.

(2) corresponds to the morphism that sends P (x, y) into P (∂x, ∂y)Δ_{n}(x)Δ_{n}(y).

(3) corresponds to the anti automorphism (twisting by the sign representation) that sends P (x, y) into P (∂x, y)Δ_{n}(x), for the first identity.

3’) For the second identity, we rather consider the anti automorphism P (x, y) ↦ P (x, ∂y)Δ_{n}(y).

We will respectively denote these last two anti automorphism

↓_{x} P (x, y) := P (∂ x, y)Δ_{n}(x)  (7.1)

and

↓_{y} P (x, y) := P (x, ∂ y)Δ_{n}(y).  (7.2)

These are both called “flips”; with respect to x in the first case, and y in the second. Clearly, if P (x, y) is of bidegree (j, k), then ↓_{x} P (x, y) is of bidegree (\binom{n}{2} − j, k), and ↓_{y} P (x, y) is of bidegree (j, \binom{n}{2} − k).

8. Trivial component.

Let us now recapitulate. According to (2.1), we have a decomposition of R, as a tensor product of the ring of (S_{n}×S_{n})-invariants with the coinvariant module R_{S_{n}×S_{n}}, giving a S_{n}-module isomorphism

R ≃ Λ(x) ⊗ Λ(y) ⊗ R_{S_{n}×S_{n}},  (8.1)

for the diagonal action of S_{n}. Formula (6.3) translates this decomposition in terms of Frobenius characteristic. Since, both Λ(x) and Λ(y) are S_{n} invariant by definition, it follows that each isotypic component R^{λ} of R decomposes as

R^{λ} ≃ Λ(x) ⊗ Λ(y) ⊗ R_{S_{n}×S_{n}}^{λ}.  (8.2)

Although we will now concentrate on the trivial (λ = (n)) and alternating (λ = 1^{n}) components, most of constructions and results that follow can be extended to all isotypic components^{4}.

For the purpose of our exposition, we need to recall some definitions. An n-cell diagram (also called bipartite partition in the literature)

(α, β) = ((a_{1}, b_{1}), (a_{2}, b_{2}), …, (a_{n}, b_{n}))

is a bipartite composition with cells, (a_{i}, b_{i}), listed in increasing^{5} lexicographic order. Recall that this is the order such that

(a, b) ⪯ (a′, b′) iff \begin{cases}b < b′ & or, \\ b = b′ and a ≤ a′. \end{cases}

In other words, the matrix representation of a diagram

(α, β) = (\begin{matrix}a_{1} & a_{2} & … & a_{n} \\ b_{1} & b_{2} & … & b_{n} \end{matrix})  (8.3)

is such that the columns are in increasing lexicographic order. Observe that a special cases of diagrams corresponds to the usual two line notation for permutations:

σ = (\begin{matrix}1 & 2 & … & n \\ σ(1) & σ(2) & … & σ(n) \end{matrix})  (8.4)

The trivial isotypic component R^{S_{n}} of R is clearly spanned by the (n-cell diagrams indexed) set of monomial diagonally symmetric polynomials

M_{(α,β)} := ∑ x^{a}y^{b},

where the sum is over all distinct bipartite compositions (a, b) obtained by permuting the cells of (α, β). For example,

M(\begin{matrix}012 \\ 001 \end{matrix}) = y_{2}x_{3}^{2}y_{3} + y_{1}x_{3}^{2}y_{3} + x_{2}^{2}y_{2}x_{3} + x_{1}^{2}y_{1}x_{3} + y_{1}x_{2}^{2}y_{2} + y_{1}x_{2}x_{1}^{2}

Observe that the leading monomial of M_{(α,β)} is X^{α}Y^{β}, for the lexicographic monomial order with the variables order:

x_{n} > y_{n} > … > x_{2} > y_{2} > x_{1} > y_{1}.

Moreover M_{(α,β)} is clearly bihomogeneous of bidegree (|α|, |β|). For more on diagonally symmetric polynomials, see [10] or [18].

In view of (8.2), the trivial isotypic component of the space

T_{n} := R_{S_{n}×S_{n}}^{S_{n}}

4See comment in section 15.

5It is convenient for our exposition to follow this convention rather than the usual one which would correspond to the decreasing lexicographic order..

has dimension of T_{n} is n!. In fact, its bigraded dimension is given by formula (6.5). We will now construct, for each permutation σ in S_{n}, a diagram (α(σ), β(σ)) with the property that

|α(σ)| = maj(σ),  and |β(σ)| = maj(σ^{−1}).  (8.5)

Furthermore, we will verify that any diagonally symmetric polynomial can be uniquely decomposed in term of the symmetric polynomials associated to these monomials. More explicitly we will show that, for all diagram (γ, δ), we have

M_{(γ,δ)} = ∑_{σ∈S_{n}} f_{σ}(x, y) M_{(α(σ),β(σ))},  (8.6)

with f_{σ}(x, y) in Λ(x) ⊗ Λ(y).

For example, with n = 3, our construction will give as a basis for T_{3} the set

M(\begin{matrix}000 \\ 000 \end{matrix}) = 1,
M(\begin{matrix}011 \\ 100 \end{matrix}) = x_{1}x_{2}y_{3} + x_{1}y_{2}x_{3} + y_{1}x_{2}x_{3},
M(\begin{matrix}001 \\ 110 \end{matrix}) = x_{1}y_{2}y_{3} + x_{2}y_{1}y_{3} + x_{3}y_{1}y_{2},
M(\begin{matrix}001 \\ 010 \end{matrix}) = x_{1}y_{2} + x_{1}y_{3} + x_{2}y_{1} + x_{2}y_{3} + x_{3}y_{1} + x_{3}y_{2},
M(\begin{matrix}011 \\ 101 \end{matrix}) = x_{1}y_{1}x_{2}y_{3} + x_{1}y_{1}y_{2}x_{3} + x_{1}x_{2}y_{2}y_{3} + x_{1}y_{2}x_{3}y_{3} + y_{1}x_{2}y_{2}x_{3} + y_{1}x_{2}x_{3}y_{3},
M(\begin{matrix}012 \\ 210 \end{matrix}) = x_{1}^{2}x_{2}y_{2}y_{3}^{2} + x_{1}^{2}y_{2}^{2}x_{3}y_{3} + x_{1}y_{1}x_{2}^{2}y_{3}^{2} + x_{1}y_{1}y_{2}^{2}x_{3}^{2} + y_{1}^{2}x_{2}^{2}x_{3}y_{3} + y_{1}^{2}x_{2}y_{2}x_{3}^{2}.

Below are a few illustrations of decompositions of form (8.6) using this basis.

M(\begin{matrix}001 \\ 001 \end{matrix}) = s_{1}(x)s_{1}(y) M(\begin{matrix}000 \\ 000 \end{matrix}) − M(\begin{matrix}001 \\ 010 \end{matrix})
M(\begin{matrix}002 \\ 001 \end{matrix}) = s_{2}(x)s_{1}(y) M(\begin{matrix}000 \\ 000 \end{matrix}) − s_{1}(x) M(\begin{matrix}001 \\ 010 \end{matrix}) + M(\begin{matrix}011 \\ 100 \end{matrix})
M(\begin{matrix}002 \\ 010 \end{matrix}) = s_{1}(x) M(\begin{matrix}001 \\ 010 \end{matrix}) − s_{11}(x)s_{1}(y) M(\begin{matrix}000 \\ 000 \end{matrix}) − M(\begin{matrix}011 \\ 100 \end{matrix})
M(\begin{matrix}011 \\ 001 \end{matrix}) = s_{11}(x)s_{1}(y) M(\begin{matrix}000 \\ 000 \end{matrix}) − M(\begin{matrix}011 \\ 100 \end{matrix})
M(\begin{matrix}001 \\ 002 \end{matrix}) = s_{1}(x)s_{2}(y) M(\begin{matrix}000 \\ 000 \end{matrix}) − s_{1}(y) M(\begin{matrix}001 \\ 010 \end{matrix}) + M(\begin{matrix}001 \\ 110 \end{matrix})
M(\begin{matrix}001 \\ 020 \end{matrix}) = s_{1}(y) M(\begin{matrix}001 \\ 010 \end{matrix}) − s_{1}(x)s_{11}(y) M(\begin{matrix}000 \\ 000 \end{matrix}) − M(\begin{matrix}001 \\ 110 \end{matrix})
M(\begin{matrix}011 \\ 001 \end{matrix}) = s_{1}(x)s_{11}(y) M(\begin{matrix}000 \\ 000 \end{matrix}) − M(\begin{matrix}001 \\ 110 \end{matrix})

For any permutation σ in S_{n}, we simply define

α(σ) := (d_{1}(σ), d_{2}(σ), …, d_{n}(σ)),  (8.7)

with

d_{i}(σ) := #{k | k < i and σ_{k} > σ_{k+1} }.  (8.8)

If we further define

β(σ) := (d_{σ(1)}(σ^{−1}), d_{σ(2)}(σ^{−1}), …, d_{σ(n)}(σ^{−1})),  (8.9)

then it is clear that identities (8.5) hold for the bipartite composition (α(σ), β(σ)). The fact that the cells of (α(σ), β(σ)) are actually in increasing lexicographic order is also readily verified. Hence we get a diagram. We will show in section 13 that the set

M_{n} := { M_{(α(σ),β(σ))} | σ ∈ S_{n} },  (8.10)

is indeed a basis of T_{n}.

9. Alternating component.

We can easily transpose to the submodule R^{±} of diagonal alternants of R, the discussion of the last section. This space affords as linear basis the set of all determinants

Δ_{D}(x, y) := det((x_{i}^{a}y_{i}^{b})\begin{matrix}(a,b)∈D \\ 1≤i≤n \end{matrix})

with D varying in the set of strict diagrams. This is to say that we are not allowing repetition of cells. Observe that, choosing D = {(i, 0) | 0 ≤ i ≤ n − 1}, we get the usual Vandermonde determinant as a special case. The module of diagonal harmonic alternants has been the object of a lot interest (See [11, 12, 13]) in the last 15 years. It is a submodule of

A_{n} = R^{±} ∩ H_{S_{n}×S_{n}}.

We have already observed that this last module has dimension n! and its Hilbert series is

(q; q)_{n}(t; t)_{n}e_{n} [\frac{1}{(1 − q)(1 − t)}] .

The space R^{±} is a free (Λ_{n}(x) ⊗ Λ_{n}(y))-module, which is made explicit by the isomorphism

R^{±} ≃ Λ_{n}(x) ⊗ Λ_{n}(y) ⊗ A_{n}.

To get a basis of A_{n}, we need only “flip” the basis M_{n} of section 8, either with respect to x or y.

10. Generalities on diagrams.

We intend to describe a natural classification of n-cell diagrams in terms of permutations in S_{n}. To this end, it is sometimes best to think of diagrams as n-element multisubsets of ℕ × ℕ. A diagram D = (α, β) can thus be “drawn” as a multiset of 1 × 1 boxes, in the combinatorial plane ℕ × ℕ. Figure 1 gives the representation of the diagram whose two line representation is:

(\begin{matrix}0 & 1 & 3 & 4 & 4 & 4 & 6 & 7 & 7 & 7 \\ 0 & 6 & 2 & 5 & 5 & 5 & 5 & 3 & 4 & 4 \end{matrix})  (10.1)

The numbers appearing in the cells are multiplicities, and when no multiplicity is mentioned it is understood to be 1.

Let D be an n-cell diagram

D = (\begin{matrix}a_{1} & a_{2} & … & a_{n} \\ b_{1} & b_{2} & … & b_{n} \end{matrix}) ,  (10.2)

[figure: 3; 2]

Figure 1. A diagram.

hence its cells are ordered in increasing lexicographic order. We say that i is a descent of D, if a_{i+1} > a_{i} and b_{i+1} < b_{i}. We denote Desc(D) the set of descents of D. For (a, b) in D, the set Desc_{(a,b)}(D) of descents of D that precede (a, b) is then defined as

Desc_{(a,b)}(D) := Desc(D) ∩ {k | (a_{k}, b_{k}) ⪯ (a, b) }.

We denote d_{(a,b)}(D) the cardinality of Desc_{(a,b)}(D). Writing simply d_{i}(D) for d_{(a_{i},b_{i})}(D), we see that this definition generalizes our previous notion of definition (8.8). Observe that, for each (a, b) in D, we have

a ≥ d_{(a,b)}(D).  (10.3)

We classify n-cell diagrams in term of permutations of S_{n} in the following way. We associate (as described below) to each n-cell diagram D a certain permutation σ(D), and set

D ≃ D′, iff σ(D) = σ(D′). (10.4)

We define the classifying permutation σ = σ(D), of an n-cell diagram D, to be the unique permutation, σ ∈ S_{n}, such that σ^{−1} reorders the b_{i}’s in increasing order:

b_{σ^{−1}(1)} ≤ b_{σ^{−1}(2)} ≤ … ≤ b_{σ^{−1}(n)},

in such a way that σ(i + 1) = σ(i) + 1, whenever b_{i} = b_{i+1} and a_{i} ≤ a_{i+1}. Observe that this definition forces the descents of σ to be the same as those of D. Moreover, the descents of σ^{−1} are the same as those of D^{−1}.

The classifying permutation of the diagram in (10.1) is:

(\begin{matrix}1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 \\ 1 & 10 & 2 & 6 & 7 & 8 & 9 & 3 & 4 & 5 \end{matrix})  (10.5)

Evidently a permutation is its own classifying permutation:

σ(τ) = τ.

We further associate to each diagram D = (α, β) a special diagram Γ(D), called the compactified of D, as follows:

Γ(D) := {(d_{(a,b)}(D), d_{(b,a)}(D^{−1})) | (a, b) ∈ D }.  (10.6)

Here D^{−1} is the diagram obtained by reordering (β, α) in increasing lexicographic order. Naturally, D is said to be compact if and only if D = Γ(D).

The compactified of the diagram appearing in (10.1) is

(\begin{matrix}0 & 0 & 1 & 1 & 1 & 1 & 1 & 2 & 2 & 2 \\ 0 & 2 & 0 & 1 & 1 & 1 & 1 & 0 & 0 & 0 \end{matrix})

It corresponds to the pictorial representation of Figure 2. The observations above

[figure: 3; 4]

Figure 2. A compact diagram.

imply that

Γ(σ(D)) = Γ(D),  (10.7)

since the “position” taken by (b_{i}, a_{i}) in D^{−1} is σ(i). We will show that the compactified of a diagram is uniquely characterized by its classifying permutation. This implies that there are exactly n! compact n-cell diagrams, one in each equivalence class with respect to relation ≃. They can thus be naturally labeled D_{σ}, for the corresponding classifying permutation σ. In fact, D_{σ} is none other then the diagram (α(σ), β(σ)) considered in the definition of M_{n} in section 8. Figures 3 and 4 respectively give the compact diagrams for n equal 3 and 4, with the corresponding permutation labels.

3

123  132  213
2  2
231  312  321

Figure 3. Compact diagrams for n = 3.

11. Characterizations of compact diagrams.

We are now going to characterize D_{σ} as being “minimal” among those that are equivalent with respect to the relation ≃. This is the motivation behind the terminology.

It immediately follows from definition (10.6) that the descent set of Γ(D) and of Γ(D)^{−1} are respectively the same as those for D and D^{−a}. This implies that

Γ^{2}(D) = Γ(D).  (11.1)

Moreover, in view of (10.3), we get that

4  2  2
1234  1243  1324  1342
2  2
1423  1432  2134  2143
2  3
2314  2341  2413  2431

2

3124  3142  3214  3241
2 2  2  3
3412  3421  4123  4132

2  2
4213  4231  4312  4321

Figure 4. Compact diagrams for n = 4.

Lemma 11.1. For all diagram D, the matrix D − Γ(D) has non negative integer entries.

For A and B two k × n matrix of non negative integers, let us say that A ≤ B if and only if B − A has non negative entries. This is a partial order on k × n matrices of non negative integers. Putting together our observations of section 10 with (11.1) and Lemma 11.1, we get

Proposition 11.2. For each permutation σ in S_{n}, there is a unique compact diagram, D_{σ}, in the class of diagrams classified by σ. Moreover, D_{σ} is minimal. This is to say that we have the inequality

D_{σ} ≤ D,  (11.2)

as 2 × n non negative integer matrices, for all D classified by σ.

Proof. The only part that remains to be checked is that Γ(D) is indeed classified by σ, but this readily follows from the definition of Γ(D). □

Another approach to compactification of diagrams is through step by step transformations of diagrams that ultimately turns them into compact diagrams. Namely, for a cell c = (a, b), we define the left translation of c

c ⇝ ◁(c) := (a − 1, b),

and down translation of c

c ⇝ ▽(c) := (a, b − 1).

A compacting move consists in replacing c, in a diagram D, either by the cell ◁(c) or ▽(c) when some conditions described below are fulfilled. We respectively denote ◁_{c}(D) and ▽_{c}(D) the resulting diagrams. To describe the constraints on compacting moves, we first associate to each cell for c in D some constraints intervals (see Figure 5):

Vert(c, D) := {(a, b) ∈ D | ◁ (c) ≺ (a, b) ≺ c }

and

Horiz(c, D) := Vert(c^{−1}, D^{−1})^{−1},

where (a, b)^{−1} = (b, a).

[figure]

Figure 5. Constraint intervals for diagram compacting moves.

We can then set

◁_{c}(D) := (D \ {c}) ∪ {◁(c)},  (11.3)

if ◁(c) is in ℕ × ℕ and Vert(c, D) is empty. The reasoning behind this is that ◁_{c} moves the cell c = (a, b) one unit to the left, if this change does not modify the underlying classifying permutation. In other words, the condition that Vert(c, D) be empty ensures that

σ(◁_{c}(D)) = σ(D).  (11.4)

In a similar manner, we set

▽_{c}(D) := (D \ {c}) ∪ {▽(c)},  (11.5)

if ▽(c) is in ℕ × ℕ and Horiz(c, D) is empty. To summarize,

◁_{c}(D) ≃ D, and ▽_{c}(D) ≃ D,

when the respective conditions are met. It is easy to check that a diagram D is compact if and only if there is no possible compacting move.

12. The fundamental bijection.

The reason behind the introduction of compact diagrams is the following theorem^{6} that will play a key role in showing that the set M_{n} is a basis of the trivial part of R_{S_{n}×S_{n}}.

6This theorem is closely related, although in a more effective form, to a theorem of Garsia and Gessel (see [6]) on bipartite partitions.

Theorem 12.1. There is a natural bijection between n-cell diagrams, and triplets (D_{σ}, λ, μ), where σ is the classifying permutation of D and both λ and μ are integer partitions having at most n non zero parts. Moreover,

ω(D) = ω(D_{σ}) + (|λ|, |μ|),

where ω(D) := ∑_{(a,b)∈D}(a, b).

Proof. Let us denote φ the bijection in question, and set

φ(D) := (D_{σ}, λ, μ),  (12.1)

with λ and μ defined as follows. We simply set

λ_{n+1−i} := a_{i} − d_{i}(σ),

and

μ_{n+1−σ(i)} := b_{i} − d_{σ(i)}(σ^{−1}).

The particular indexing in these definitions ensures that parts of λ and μ are in decreasing order. Recall that

D_{σ} = (α(σ), β(σ))
= {(d_{i}(σ), d_{σ(i)}(σ^{−1}) | 1 ≤ i ≤ n }.

It follows that λ and μ are respectively obtained by reordering in decreasing order the entries of the first and second line of the matrix D −D_{σ}(i). This makes it evident that φ is a bijection. The compact diagram clearly corresponds to the case when λ = μ = 0. □

13. Basis of symmetric coinvariants.

We are now in a position to prove that the set M_{n} (see (8.10)) actually is a basis of the trivial isotypic component of the space R_{S_{n}×S_{n}}. This will simply follow from the following proposition.

Proposition 13.1. The set of diagonally symmetric polynomial

{ m_{λ}(x)m_{μ}(y)M_{(α(σ),β(σ))}(x, y) | ℓ(λ) ≤ n, ℓ(μ) ≤ n, and σ ∈ S_{n} }  (13.1)

is linearly independent.

Proof. We need only observe that, for the lexicographic monomial order, the leading monomial of m_{λ}(x)m_{μ}(y)M_{(α(σ),β(σ))}(x, y) is simply X^{γ}Y^{δ}, where

φ(D) = (D_{σ}, λ, μ),

with D = (γ, δ). □

14. Strict diagrams.

As we have seen in section 6, the function

↓_{x} P (x, y) = P (∂x, y)Δ_{n}(x)  (14.1)

establishes a sign twisting automorphism of the S_{n}-module of S_{n}×S_{n}-harmonics. This is reflected in part by a natural bijection between the set of compact diagrams, and a natural indexing set for a basis of the alternating part of this same S_{n}-module. This is also equivalent to a description of an explicit basis for the alternating S_{n}-isotypic component of the coinvariant module of S_{n} × S_{n}.

Once again, we are looking for a family of special (compact) “strict” diagrams indexed by permutations, together with a bijective encoding of general strict diagrams as triples (D_{σ}^{s}, λ, μ), with D_{σ}^{s} one of these special strict diagrams, and λ and μ partitions having at most n parts. These diagrams are simply obtained by translating, in term of diagrams, the effect of the sign twisting automorphism in (14.1). This takes the form of the following transform on compact diagrams:

D_{σ} ↦ D_{σ}^{s} := (0, σ − 1^{n}) + JD_{σ},  with J := (\begin{matrix}1 & 0 \\ 0 & −1 \end{matrix})  (14.2)

where σ − 1^{n} := (σ(1) − 1, σ(2) − 1, …, σ(n) − 1). One easily verifies easily that the resulting diagrams have all their cells distinct, and it is clear that

∑_{(a,b)∈D_{σ}^{s}}(a, b) = (maj(σ), \binom{n}{2} − maj(σ^{−1})) .

The following table illustrates the result of this process.

123 (\begin{matrix}0 & 0 & 0 \\ 0 & 0 & 0 \end{matrix}) ↦ (\begin{matrix}0 & 0 & 0 \\ 0 & 1 & 2 \end{matrix})
132 (\begin{matrix}0 & 0 & 1 \\ 0 & 1 & 0 \end{matrix}) ↦ (\begin{matrix}0 & 0 & 1 \\ 0 & 1 & 1 \end{matrix})
213 (\begin{matrix}0 & 1 & 1 \\ 1 & 0 & 1 \end{matrix}) ↦ (\begin{matrix}0 & 1 & 1 \\ 0 & 0 & 1 \end{matrix})
231 (\begin{matrix}0 & 0 & 1 \\ 1 & 1 & 0 \end{matrix}) ↦ (\begin{matrix}0 & 0 & 1 \\ 0 & 1 & 0 \end{matrix})
312 (\begin{matrix}0 & 1 & 1 \\ 1 & 0 & 0 \end{matrix}) ↦ (\begin{matrix}0 & 1 & 1 \\ 1 & 0 & 1 \end{matrix})
321 (\begin{matrix}0 & 1 & 2 \\ 2 & 1 & 0 \end{matrix}) ↦ (\begin{matrix}0 & 1 & 2 \\ 0 & 0 & 0 \end{matrix})

Strictly compact diagrams, for all permutations in S_{4}, are depicted in Figure 6.

Just as in our previous case, we can describe strictly compact diagrams directly in term of their indexing permutation, or in term of strict compacting moves. These are the same moves as before, but the constraint intervals are modified as follows. We now set

Vert_{s}(c, D) := {(a, b) ∈ D | ◁ (c) ⪯ (a, b) ≺ c }

1234  1243  1324  1342

1423  1432  2134  2143

2314  2341  2413  2431

3124  3142  3214  3241

3412  3421  4123  4132
4213  4231  4312  4321

Figure 6. Strictly compact diagrams, n = 4.

and

Horiz_{s}(c, D) := {(a, b) ∈ D | (b, a) ⪯ ◁(c^{−1}), or c^{−1} ≺ (b, a) }

These two intervals considered are illustrated in Figure 7.

[figure]

Figure 7. Constraint intervals for strict compacting moves.

Once again, there is a natural bijection between the set of strict n-cell diagrams, and the set of triples (D_{σ}^{s}, λ, μ), with λ and μ partitions having at most n parts. Many nice properties of strict diagrams have been explored in [16].

15. Final remarks.

The constructions and results for diagrams and strict diagrams afford a common generalization that allows a combinatorial description of each isotypic component of the S_{n}-module of S_{n} × S_{n}-coinvariants. More precisely, there is a notion of compact diagrams indexed by pairs (σ, τ), with σ a permutation and τ a standard tableau, where the charge statistic plays a natural role. There are also similar results for the decomposition of the diagonal action of S_{n} on S_{n}^{k}-coinvariants, as well as for other Coxeter groups such as B_{n} and D_{n}. All these generalizations will be the subject of an upcoming paper.

References

[1] R. Adin, F. Brenti and Y. Roichman, Descent Representations and Multivariate Statistics, Trans. Amer. Math. Soc., to appear. arXiv:math.CO/0112073.

[2] E. Artin, Galois Theory, Notre Dame Mathematical Lecture 2 (1944), Notre Dame, IN.

[3] F. Bergeron, N. Bergeron, A. Garsia, M. Haiman and G. Tesler, Lattice Diagram Polynomials and Extended Pieri Rules, Advances in Mathematics, 142 (1999), 244-334.

[4] F. Bergeron, A. Garsia, M. Haiman and G. Tesler, Identities and Positivity Conjectures for Some Remarkable Operators in the Theory of Symmetric Functions, Methods and Applications of Analysis, Volume 6, No. 3, (1999), 363–420.

[5] F. Bergeron, A. Garsia and G. Tesler, Multiple Left Regular Representations Generated by Alternants, Journal of Combinatorial Theory, Series A, 91, 1-2 (2000), 49–83.

[6] A.M. Garsia and I. Gessel, Permutation statistics and partitions, Advances in Mathematics, 31 (1979), 288–305.

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

[8] A.M. Garsia and D. Stanton, Group Action of Stanley-Reisner Rings and Invariants of Permutations Groups, Advances in Mathematics, 51 (1984), 107–201.

[9] I. Gessel, Multipartite P -partitions and products of skew Schur functions, in Combinatorics and Algebra, C. Greene, ed., vol. 34 of Contemporary Mathematics Math., AMS (1984), 289– 317.

[10] I. Gessel, Enumerative Applications of Symmetric Functions, Séminaire Lotharingien de Combinatoire, 17 (1987), 5–21.

[11] I. Gordon, On the quotient ring by diagonal invariants, Inventiones Mathematicae, 153 (2003), 503-518.

[12] J. Haglund, M. Haiman, N. Loehr, J.B. Remmel and A. Ulyanov, A Combinatorial Formula for the Character of Diagonal Coinvariants, Duke Math. J. (to appear).

arXiv.math.CO/0310424.

[13] M. Haiman, Hilbert schemes, polygraphs, and the Macdonald positivity conjecture, Journal of the American Mathematical Society, 14 (2001), 941-1006. arXiv.math.AG/0201148.

[14] M. Haiman, Vanishing Theorems and Character Formulas for the Hilbert Scheme of Points in the plane, Inventiones Mathematicae, 149 (2002), 371–407.

[15] R. Kane, Reflection Groups and Invariant Theory, CMS Books in Mathematics, Vol. 5, Springer, 2001.

[16] F. Lamontagne, Étude d’espaces de polynômes harmoniques généralisés, Ph. D. Thesis, UQAM, 2003.

[17] I. Macdonald, Symmetric Functions and Hall Polynomials, Oxford University Press, 1995, second edition.

[18] M. Rosas, MacMahon symmetric functions, the partition lattice, and Young tableaux, Journal of Combinatorial Theory, Series A, 96 (2001), 326–340.

[19] G. C. Shephard and J. A. Todd, Finite unitary reflection groups, Canadian Journal of Mathematics 6 (1954), 274–304.

[20] R. Stanley, Invariants of Finite Groups and their Application to Combinatorics, Bull. Amer. Math. Soc. (new series) 1 (1979), 475–511.

[21] R. Stanley, Enumerative Combinatorics Vol. 2, no. 62 in Cambridge Studies in Advanced Mathematics, Cambridge University Press, 1999. Appendix 1 by Sergey Fomin.

[22] R. Steinberg, Differential equations invariant under finite reflection groups, Transaction of the American Mathematical Society, 112 (1964), 392–400.

(F. Bergeron) Département de Mathématiques, Université du Québec à Montréal, Montréal, Québec, H3C 3P8, CANADA

E-mail address: bergeron.francois@uqam.ca

(F. Lamontagne) Département de Mathématiques, Université du Québec à Montréal, Montréal, Québec, H3C 3P8, CANADA

E-mail address: lamontag@math.uqam.ca