9512.net

甜梦文库

甜梦文库

当前位置：首页 >> >> # Descent representations and multivariate statistics

TRANSACTIONS OF THE AMERICAN MATHEMATICAL SOCIETY Volume 357, Number 8, Pages 3051–3082 S 0002-9947(04)03494-4 Article electronically published on July 16, 2004

DESCENT REPRESENTATIONS AND MULTIVARIATE STATISTICS

RON M. ADIN, FRANCESCO BRENTI, AND YUVAL ROICHMAN Abstract. Combinatorial identities on Weyl groups of types A and B are derived from special bases of the corresponding coinvariant algebras. Using the Garsia-Stanton descent basis of the coinvariant algebra of type A we give a new construction of the Solomon descent representations. An extension of the descent basis to type B , using new multivariate statistics on the group, yields a re?nement of the descent representations. These constructions are then applied to re?ne well-known decomposition rules of the coinvariant algebra and to generalize various identities.

1. Introduction 1.1. Outline. This paper studies the interplay between representations of classical Weyl groups of types A and B and combinatorial identities on these groups. New combinatorial statistics on these groups are introduced, which lead to a new construction of representations. The Hilbert series which emerge give rise to multivariate identities generalizing known ones. The set of elements in a Coxeter group having a ?xed descent set carries a natural representation of the group, called a descent representation. Descent representations of Weyl groups were ?rst introduced by Solomon [30] as alternating sums of permutation representations. This concept was extended to arbitrary Coxeter groups, using a di?erent construction, by Kazhdan and Lusztig [22], [21, §7.15]. For Weyl groups of type A, these representations also appear in the top homology of certain (Cohen-Macaulay) rank-selected posets [34]. Another description (for type A) is by means of zig-zag diagrams [19, 16]. In this paper we give a new construction of descent representations for Weyl groups of type A, using the coinvariant algebra as a representation space. This viewpoint gives rise to a new extension for type B , which re?nes the one by Solomon. The construction of a basis for the coinvariant algebra is important for many applications, and has been approached from di?erent viewpoints. A geometric approach identi?es the coinvariant algebra with the cohomology ring H ? (G/B ) of

Received by the editors October 13, 2002 and, in revised form, August 15, 2003. 2000 Mathematics Subject Classi?cation. Primary 05E10, 13A50; Secondary 05A19, 13F20, 20C30. The research of all authors was supported in part by the EC’s IHRP programme, within the Research Training Network “Algebraic Combinatorics in Europe”, grant HPRN-CT-2001-00272, by the Israel Science Foundation, founded by the Israel Academy of Sciences and Humanities, and by internal research grants from Bar-Ilan University.

c 2004 American Mathematical Society

3051

3052

RON M. ADIN, FRANCESCO BRENTI, AND YUVAL ROICHMAN

the ?ag variety. This leads to the Schubert basis [7, 10], and applies to any Weyl group. This identi?cation also appears in Springer’s construction of irreducible representations [31]; see also [15]. Barcelo [6] found bases for the resulting quotients. An algebraic approach, applying Young symmetrizers, was used by Ariki, Terasoma and Yamada [39, 5] to produce a basis compatible with the decomposition into irreducible representations. This was extended to complex re?ection groups in [26]. A combinatorial approach, which produces a basis of monomials, was presented by Garsia and Stanton in [17] (see also [13, 37]). They actually presented a basis for a ?nite-dimensional quotient of the Stanley-Reisner ring arising from a ?nite Weyl group. For type A, unlike other types, this quotient is isomorphic to the coinvariant algebra. The Garsia-Stanton descent basis for type A may be constructed from the coinvariant algebra via a straightening algorithm [4]. Using a reformulation of this algorithm we give a natural construction of Solomon’s descent representations as factors of the coinvariant algebra of type A. An analogue of the descent basis for type B is now given. This analogue (again consisting of monomials) involves extended descent sets and new combinatorial statistics. An extension of the construction of descent representations, using the new basis for type B , gives rise to a family of descent representations, re?ning Solomon’s. A decomposition of these descent representations into irreducibles, re?ning theorems of Lusztig and Stanley [33, Prop. 4.11], [28, Theorem 8.8] (for type A) and Stembridge [38] (for type B ), is carried out using a multivariate version of Stanley’s formula for the principal specialization of Schur functions. This algebraic setting is then applied to obtain new multivariate combinatorial identities. Suitable Hilbert series are computed and compared to each other and to generating functions of multivariate statistics. The resulting identities present a far reaching generalization of bivariate identities from [18], [14], and [1].

W 1.2. Main results. Let W be a classical Weyl group of type A or B , and let In be the ideal of the polynomial ring Pn := Q[x1 , . . . , xn ] generated by W -invariant W polynomials without a constant term. The quotient Pn /In is called the coinvariant algebra of W . See Subsection 2.5 below. For any partition λ with (at most) n parts, let Pλ be the subspace of the polynomial ring Pn = Q[x1 , . . . , xn ] spanned by all monomials whose exponent partition is dominated by λ, and let Rλ be a distinguished quotient of the image of Pλ under the projection of Pn onto the coinvariant algebra. For precise de?nitions see Subsections 3.5 and 5.3. We will show that the homogeneous components of the coinvariant algebra decompose as direct sums of certain Rλ ’s. This will be done using an explicit construction of a basis for Rλ . The construction of this basis involves new statistics on Sn and Bn .

1.2.1. New statistics. Let Σ be a linearly ordered alphabet. For any ?nite sequence σ = (σ1 , . . . , σn ) of letters in Σ de?ne Des(σ ) := {i | σi > σi+1 }, the descent set of σ , and di (σ ) := |{j ∈ Des(σ ) : j ≥ i}|, the number of descents in σ from position i on.

DESCENT REPRESENTATIONS AND MULTIVARIATE STATISTICS

3053

If Σ consists of integers, let Neg(σ ) := {i | σi < 0}; ni (σ ) := |{j ∈ Neg(σ ) : j ≥ i}|; εi (σ ) := and fi (σ ) := 2di (σ ) + εi (σ ). The statistics fi (σ ) re?ne the ?ag-major index fmaj(σ ), which was introduced and studied in [2, 3, 1]. For various properties of these statistics see Sections 3, 5, and 6 below. 1.2.2. The Garsia-Stanton descent basis and its extension. Garsia and Stanton [17] associated the monomial aπ :=

i∈Des(π )

1, if σi < 0, 0, otherwise;

(xπ(1) · · · xπ(i) )

n d (π )

to any π ∈ Sn . It should be noted that in our notation aπ = i=1 xπi(i) . Using Stanley-Reisner rings, Garsia and Stanton [17] showed that the set {aπ + In | π ∈ Sn } forms a basis for the coinvariant algebra of type A. This basis will be called the descent basis. The Garsia-Stanton approach is not applicable to the coinvariant algebras of other Weyl groups. In this paper we extend the descent basis to the Weyl groups of type B . We associate the monomial

n

bσ :=

i=1

i x|σ (i)|

f (σ )

to any σ ∈ Bn . Theorem 1.1 (See Corollary 5.3). The set

B | σ ∈ Bn } {bσ + In

forms a basis for the coinvariant algebra of type B . 1.2.3. Descent representations. For a monomial m in the polynomial ring Pn = Q[x1 , . . . , xn ], let the exponent partition λ(m) be the partition obtained by rearranging the exponents in a weakly decreasing order. For any partition λ with at most n parts, let Pλ be the subspace of Pn spanned by all monomials whose exponent partition is dominated by λ: Pλ := spanQ {m | λ(m) Similarly, de?ne Pλ by strict dominance: Pλ := spanQ {m | λ(m) λ}. Now consider the canonical projection of Pn onto the coinvariant algebra ψ : Pn ?→ Pn /In . De?ne Rλ to be a quotient of images under this map: Rλ := ψ (Pλ )/ψ (Pλ ). Then Rλ is an Sn -module. λ}.

3054

RON M. ADIN, FRANCESCO BRENTI, AND YUVAL ROICHMAN

For any subset S ? {1, . . . , n} de?ne a partition λS := (λ1 , . . . , λn ) by λi := | S ∩ {i, . . . , n} |. Using a straightening algorithm for the descent basis it is shown that Rλ = 0 if and only if λ = λS for some S ? [n ? 1] (Corollary 3.10), and that a basis for RλS may be indexed by the permutations with descent set equal to S (Corollary 3.11). Let Rk be the k -th homogeneous component of the coinvariant algebra Pn /In . Theorem 1.2 (See Theorem 3.12). For every 0 ≤ k ≤ Rk ? =

S n 2

,

RλS

i∈S

as Sn -modules, where the sum is over all subsets S ? [n ? 1] such that Let

B := ψ B (Pλ ) / ψ B (Pλ ), Rλ

i = k.

B where ψ B : Pn ?→ Pn /In is the canonical map from Pn onto the coinvariant algebra of type B . For subsets S1 ? [n ? 1] and S2 ? [n], let λS1 ,S2 be the vector

λS1 ,S2 := 2λS1 + 1S2 , where λS1 is as above and 1S2 ∈ {0, 1}n is the characteristic vector of S2 . Again, B Rλ = 0 if and only if λ = λS1 ,S2 for some S1 ? [n ? 1], S2 ? [n] (Corollary 5.6). In B may be indexed by the signed permutations σ ∈ Bn this case, a basis for Rλ S1 ,S2 with Des(σ ) = S1 and Neg(σ ) = S2 (Corollary 5.7). B be the k -th homogeneous component of the coinvariant algebra of type Let Rk B . The following theorem is a B -analogue of Theorem 1.2. Theorem 1.3 (See Theorem 5.8). For every 0 ≤ k ≤ n2 ,

B ? Rk = S1 ,S2 B Rλ S1 ,S2

as Bn -modules, where the sum is over all subsets S1 ? [n ? 1] and S2 ? [n] such that λS1 ,S2 is a partition and 2·

i∈S1

i + |S2 | = k.

1.2.4. Decomposition into irreducibles. Theorem 1.4 (See Theorem 4.1). For any subset S ? [n ? 1] and partition ? n, the multiplicity in RλS of the irreducible Sn -representation corresponding to ? is mS,? := | { T ∈ SY T (?) | Des(T ) = S } |, the number of standard Young tableaux of shape ? and descent set S . This theorem re?nes the well-known decomposition (due, independently, to Lusztig and Stanley) of each homogeneous component of the coinvariant algebra into irreducibles. See Subsection 2.5.

DESCENT REPRESENTATIONS AND MULTIVARIATE STATISTICS

3055

For type B we have Theorem 1.5. For any pair of subsets S1 ? [n ? 1], S2 ? [n], and a bipartition (?1 , ?2 ) of n, the multiplicity of the irreducible Bn -representation corresponding to B (?1 , ?2 ) in Rλ is S ,S

1 2

mS1 ,S2 ,?1 ,?2 := | { T ∈ SY T (?1 , ?2 ) | Des(T ) = S1 and Neg(T ) = S2 } |, the number of pairs of standard Young tableaux of shapes ?1 and ?2 with descent set S1 and sets of entries [n] \ S2 and S2 , respectively. For de?nitions and more details see Subsection 5.4 and Theorem 5.9 below. The proofs apply multivariate extensions of Stanley’s formula for the principal specialization of a Schur function. See Lemmas 4.3 and 5.10 below. 1.2.5. Combinatorial identities. For any partition λ = (λ1 , . . . , λn ) with at most n parts de?ne (?j ≥ 0). mj (λ) := | {1 ≤ i ≤ n | λi = j } | By considering Hilbert series of the polynomial ring with respect to rearranged multi-degree and applying the Straightening Lemma for the coinvariant algebra of type A we obtain Theorem 1.6 (See Theorem 6.2). For any positive integer n n m0 (λ), m1 (λ), . . .

n i=1 λi qi = π ∈ Sn n i=1 (1 d i (π ) n i=1 qi

(λ)≤n

? q1 · · · qi )

in Z [[q1 , . . . , qn ]], where the sum on the left-hand side is taken over all partitions with at most n parts. This theorem generalizes Gessel’s theorem for the bivariate distribution of descent number and major index [18]. The main combinatorial result for type B asserts: Theorem 1.7 (See Theorem 6.1). For any positive integer n

n σ∈Bn i=1 n

qi i

d (σ)+ni (σ?1 )

=

σ∈Bn i=1

qi

2di (σ)+εi (σ)

.

For further identities see Section 6. In particular, it is shown that central results from [1] follow from Theorem 1.7. 2. Preliminaries 2.1. Notation. Let P := {1, 2, 3, . . .}, N := P ∪ {0}, Z be the ring of integers, and Q be the ?eld of rational numbers; for a ∈ N let [a] := {1, 2, . . . , a} (where [0] := ?). Given n, m ∈ Z , n ≤ m, let [n, m] := {n, n + 1, . . . , m}. For S ? N write S = {a1 , . . . , ar }< to mean that S = {a1 , . . . , ar } and a1 < . . . < ar . The cardinality of a set A will be denoted by |A|. More generally, given a multiset M = {1a1 , 2a2 , . . . , rar } denote by |M | its cardinality, so |M | = r i=1 ai . Given a variable q and a commutative ring R, denote by R[q ] (respectively, R[[q ]]) the ring of polynomials (respectively, formal power series) in q with coe?cients in R. For i ∈ N let, as customary, [i]q := 1 + q + q 2 + . . . + q i?1 (so [0]q = 0). Given a vector v = (v1 , . . . , vn ) ∈ P n and a sequence of variables x1 , . . . , xn denote by x ?v n vi the monomial i=1 xi ∈ R[x1 , . . . , xn ].

3056

RON M. ADIN, FRANCESCO BRENTI, AND YUVAL ROICHMAN

2.2. Sequences and permutations. Let Σ be a linearly ordered alphabet. Given a sequence σ = (σ1 , . . . , σn ) ∈ Σn we say that a pair (i, j ) ∈ [n] × [n] is an inversion of σ if i < j and σi > σj . We say that i ∈ [n ? 1] is a descent of σ if σi > σi+1 ; Des(σ ) := {1 ≤ i ≤ n ? 1 | σi > σi+1 } is the descent set of σ . Denote by inv(σ ) (respectively, des(σ )) the number of inversions (respectively, descents) of σ . We also let maj (σ ) :=

i∈Des(σ)

i

and call it the major index of σ . Given a set T let S (T ) be the set of all bijections π : T → T , and Sn := S ([n]). For π ∈ Sn write π = π1 . . . πn to mean that π (i) = πi , for i = 1, . . . , n. Any π ∈ Sn may also be written in disjoint cycle form (see, e.g., [35, p. 17]), usually omitting the 1-cycles of π . For example, π = 365492187 may also be written as π = (9, 7, 1, 3, 5)(2, 6). Given π, τ ∈ Sn let πτ := π ? τ (composition of functions) so that, for example, (1, 2)(2, 3) = (1, 2, 3). Denote by Bn the group of all bijections σ of the set [?n, n] \ {0} onto itself such that σ (?a) = ?σ (a) for all a ∈ [?n, n] \ {0}, with composition as the group operation. This group is usually known as the group of “signed permutations” on [n], or as the hyperoctahedral group of rank n. We identify Sn as a subgroup of Bn , and Bn as a subgroup of S2n , in the natural ways. For σ ∈ Bn write σ = [a1 , . . . , an ] to mean that σ (i) = ai for i = 1, . . . , n, and (using the natural linear order on [?n, n] \ {0}) let inv(σ ) := inv(a1 , . . . , an ), des(σ ) := des(a1 , . . . , an ), Neg(σ ) := {i ∈ [n] : ai < 0}, neg(σ ) := |Neg(σ )|, fmaj(σ ) := 2 · maj(σ ) + neg(σ ). maj(σ ) := maj(a1 , . . . , an ), The statistic fmaj was introduced in [2, 3] and further studied in [1]. 2.3. Partitions and tableaux. Let n be a nonnegative integer. A partition of n is an in?nite sequence of nonnegative integers with ?nitely many nonzero terms λi = n is called λ = (λ1 , λ2 , . . .), where λ1 ≥ λ2 ≥ . . . and ∞ i=1 λi = n. The sum the size of λ, denoted |λ|; also write λ n. The number of parts of λ, (λ), is the maximal j for which λj > 0. The unique partition of n = 0 is the empty partition ? = (0, 0, . . . ), which has length (?) := 0. For a partition λ = (λ1 , . . . , λk , . . .) de?ne the conjugate partition λ = (λ1 , . . . , λi , . . .) by letting λi be the number of parts of λ that are ≥ i (?i ≥ 1). The dominance partial order on partitions is de?ned as follows: For any two partitions ? and λ of the same integer, ? dominates λ (denoted ? λ) if and only i i ∞ ∞ if j =1 ?j ≥ j =1 λj for all i (and, by assumption, j =1 ?j = j =1 λj ). The subset {(i, j ) | i, j ∈ P, j ≤ λi } of P2 is called the Young diagram of shape λ. (i, j ) is the cell in row i and column j . The diagram of the conjugate shape λ may be obtained from the diagram of shape λ by interchanging rows and columns. A Young tableau of shape λ is obtained by inserting the integers 1, . . . , n (where n = |λ|) as entries in the cells of the Young diagram of shape λ, allowing no

DESCENT REPRESENTATIONS AND MULTIVARIATE STATISTICS

3057

repetitions. A standard Young tableau of shape λ is a Young tableau whose entries increase along rows and columns. We shall draw Young tableaux as in the following example. Example. 1 3 4 2 7 8 5 10 6 9 11

A descent in a standard Young tableau T is an entry i such that i + 1 is strictly south (and hence weakly west) of i. Denote the set of all descents in T by Des(T ). The descent number and the major index (for tableaux) are de?ned as follows: des(T ) :=

i∈Des(T )

1;

maj(T ) :=

i∈Des(T )

i.

Example. Let T be the standard Young tableau drawn above. Then Des(T ) = {1, 4, 6, 9}, des(T ) = 4, and maj(T ) = 1 + 4 + 6 + 9 = 20. A semistandard Young tableau of shape λ is obtained by inserting positive integers as entries in the cells of the Young diagram of shape λ, so that the entries weakly increase along rows and strictly increase down columns. A reverse semistandard Young tableau is obtained by inserting positive integers into the diagram so that the entries weakly decrease along rows and strictly decrease down columns. A bipartition of n is a pair (λ1 , λ2 ) of partitions of total size |λ1 | + |λ2 | = n. A (skew) diagram of shape (λ1 , λ2 ) is the disjoint union of a diagram of shape λ1 and a diagram of shape λ2 , where the second diagram lies southwest of the ?rst. A standard Young tableau T = (T 1 , T 2 ) of shape (λ1 , λ2 ) is obtained by inserting the integers 1, 2, . . . , n as entries in the cells, such that the entries increase along rows and columns. The descent set Des(T ), the descent number des(T ), and the major index maj(T ) of T are de?ned as above. The negative set, Neg(T ), of such a tableau T is the set of entries in the cells of λ2 . De?ne neg(T ) := |Neg(T )| and fmaj(T ) := 2 · maj(T ) + neg(T ). Example. Let T be 2 3 1 4 7 8 5 6

We shall also consider T as a pair of tableaux (T 1 , T 2 ) = 2 5 3 6 , 1 4 7 8 .

T is a standard Young tableau of shape ((3, 1), (2, 2)); Des(T ) = {2, 3, 6, 7}, des(T ) = 4, maj(T ) = 18, N eg (T ) = {1, 4, 7, 8}, neg(T ) = 4, and fmaj(T ) = 40. Denote by SY T (λ) the set of all standard Young tableaux of shape λ. Similarly, SSY T (λ) and RSSY T (λ) denote the sets of all semistandard and reverse semistandard Young tableaux of shape λ, respectively. SY T (λ1 , λ2 ) denotes the set of all standard Young tableaux of shape (λ1 , λ2 ).

3058

RON M. ADIN, FRANCESCO BRENTI, AND YUVAL ROICHMAN

? be a (reverse) semistandard Young tableau. The content vector cont(T ?) = Let T (m1 , m2 , . . . ) is de?ned by ? with entry i}| mi := |{cells in T (?i ≥ 1). 2.4. Symmetric functions. Let Λ (Λn ) be the ring of symmetric functions in in?nitely many (resp. n) variables. In this paper we consider three bases for the vector space Λ: The elementary symmetric functions are de?ned as follows. For a nonempty partition λ = (λ1 , λ2 , . . . , λt )

t

eλ (? x) :=

i=1

eλi (? x),

where x ? = (x1 , x2 , . . . ) and for any k ∈ P ek (? x) :=

i1 <i2 <···<ik

xi1 · · · xik .

The power sum symmetric functions are de?ned as follows. For a nonempty partition λ = (λ1 , λ2 , . . . , λt )

t

x) := pλ (? where for any k ∈ P

i=1

pλi (? x),

∞

x) := pk (?

i=1

xk i.

The Schur functions are de?ned in a di?erent manner. For a nonempty partition λ de?ne x) := x ?cont(T ) . sλ (?

T ∈SSY T (λ)

x) = p? (? x) = s? (? x) := 1. For the empty partition λ = ?, de?ne e? (? Claim 2.1 (See [36, Prop. 7.10.4]). sλ (? x) =

T ∈RSSY T (λ)

x ?cont(T ) .

Note that corresponding spanning sets for Λn are obtained by substituting xn+1 = xn+2 = · · · = 0. The conjugacy classes of the symmetric group Sn are described by their cycle type; thus, by partitions of n. The irreducible representations of Sn are also indexed by these partitions (cf. [29]). Let λ and ? be partitions of n. Denote by χλ ? the value, at a conjugacy class of cycle type ?, of the character of the irreducible Sn -representation corresponding to λ. These character values are entries in the transition matrix between two of the above bases. This fact was discovered and applied by Frobenius as an e?cient tool for calculating characters (cf. [36, p. 401]). Frobenius formula ([36, Corollary 7.17.4]). For any partition ? of n p? (? x) =

λ n

χλ x), ? sλ (?

where the sum runs through all partitions λ of n.

DESCENT REPRESENTATIONS AND MULTIVARIATE STATISTICS

3059

Recall that the Weyl group Bn may be described as the group of all signed permutations of order n (Subsection 2.2). The conjugacy classes of Bn are described by the signed cycle type (i.e., each cycle is described by its length and the product of the signs of its entries). Thus, the conjugacy classes are described by ordered pairs of partitions whose total size is n: the ?rst partition consists of the lengths of the positive cycles, while the second consists of the lengths of the negative cycles. The irreducible representations of Bn are also indexed by these pairs of partitions; cf. [24, §I, Appendix B]. For two partitions ?1 and ?2 , and two in?nite sets of independent variables x ? = x1 , x2 , . . . and y ? = y1 , y2 , . . . , de?ne p?1 ,?2 (? x, y ?) :=

i

1 2

(p?1 (? x) + p?1 (? y )) · i i

j

(p?2 (? x) ? p?2 (? y )). j j

,λ 1 2 Let χλ ?1 ,?2 be the irreducible Bn -character indexed by (λ , λ ) evaluated at a conjugacy class of cycle type (?1 , ?2 ). Then

Frobenius formula for Bn ([24, p. 178]). With the above notations, for any bipartition (?1 , ?2 ) of n p?1 ,?2 (? x, y ?) =

λ1 ,λ2 ,λ 1 x)sλ2 (? χλ y ), ?1 ,?2 sλ (?

1 2

where the sum runs through all ordered pairs of partitions (λ1 , λ2 ) of total size |λ1 | + |λ2 | = n. 2.5. The coinvariant algebra. The groups Sn and Bn have natural actions on the ring of polynomials Pn (cf. [21, §3.1]). Sn acts by permuting the variables, and Bn acts by permuting the variables and multiplying by ±1. The ring of Sn -invariant polynomials is Λn , the ring of symmetric functions in x1 , . . . , xn . Similarly, the ring 2 2 of Bn -invariant polynomials is ΛB n , the ring of symmetric functions in x1 , . . . , xn . B B Let In , In be the ideals of Pn generated by the elements of Λn , Λn (respectively) B without constant term. The quotient Pn /In (Pn /In ) is called the coinvariant algebra of Sn (Bn ). Each group acts naturally on its coinvariant algebra. The resulting representation is isomorphic to the regular representation. See, e.g., [21, §3.6] and [20, §II.3]. Let Rk (0 ≤ k ≤ n 2 ) be the k -th homogeneous component of the coinvariant algebra of Sn : Pn /In = k Rk . Each Rk is an Sn -module. The following theorem is apparently due to G. Lusztig (unpublished) and, independently, to R. Stanley [33, Prop. 4.11]. It was also proved by Kraskiewicz and Weyman [23]; see [28, p. 215]. Lusztig-Stanley theorem ([33, Prop. 4.11], [28, Theorem 8.8]). For any 0 ≤ n, the multiplicity in Rk of the irreducible Sn -representation k ≤ n 2 and ? corresponding to ? is mk,? = | { T ∈ SY T (?) | maj(T ) = k } |.

B The following B -analogue (in di?erent terminology) was proved in [38]. Here Rk is the k -th homogeneous component of the coinvariant algebra of Bn .

Stembridge’s theorem. For any 0 ≤ k ≤ n2 and bipartition (?1 , ?2 ) of n, the B of the irreducible Bn -representation corresponding to (?1 , ?2 ) is multiplicity in Rk mk,?1 ,?2 = | { T ∈ SY T (?1 , ?2 ) | fmaj(T ) = k } |.

3060

RON M. ADIN, FRANCESCO BRENTI, AND YUVAL ROICHMAN

2.6. The Garsia-Stanton descent basis (Type A). For any π ∈ Sn de?ne the monomial (xπ(1) · · · xπ(j ) ). aπ :=

j ∈Des(π )

Using Stanley-Reisner rings Garsia and Stanton showed that the set {aπ + In | π ∈ Sn } forms a basis for the coinvariant algebra of type A [17]. This basis will be called the descent basis. Unfortunately, this approach does not give a basis for the coinvariant algebras of other Weyl groups. In this paper we shall ?nd an analogue of the descent basis for Bn . Our approach will allow us to obtain re?nements of the Lusztig-Stanley and Stembridge theorems. 3. Construction of descent representations In this section we introduce several combinatorial concepts (Subsections 3.1 and 3.2). Then we present a straightening algorithm for the expansion of an arbitrary monomial in Pn in terms of descent basis elements, with coe?cients from Λn (Subsections 3.3 and 3.4). This algorithm is essentially equivalent to the one presented by Allen [4], but our formulation leads naturally to descent representations and may be extended to type B (Subsections 3.5 and 5.2). 3.1. Descent statistics. In this subsection we introduce a family of descent statistics for sequences of letters from a linearly ordered alphabet. Let Σ be a linearly ordered alphabet. For any sequence σ of n letters from Σ de?ne (1 ≤ i ≤ n), di (σ ) := |{j ∈ Des(σ ) : j ≥ i}| the number of descents in σ from position i on. Clearly, (3.1) and

n

d1 (σ ) = des(σ )

(3.2)

i=1

di (σ ) = maj(σ ).

Note that dn (σ ) = 0. Also, for any sequence σ from Σ (3.3) (3.4) (3.5) di (σ ) ≥ di+1 (σ ), 1 ≤ i < n, di (σ ) = di+1 (σ ) =? σ (i) < σ (i + 1), di (σ ) > di+1 (σ ) =? σ (i) > σ (i + 1) and di (σ ) = di+1 (σ ) + 1.

It follows from (3.2) and (3.3) that the sequence (d1 (σ ), d2 (σ ), . . . , dn (σ )) is a partition of maj(σ ). It follows from (3.4) and (3.5) that this sequence uniquely determines the descent set of σ . More explicitly, the partition conjugate to (d1 (σ ), . . . , dn (σ )) is obtained by writing the elements of Des(σ ) in decreasing order. Finally, for a permutation π ∈ Sn , let aπ be the corresponding descent basis element. Then, clearly,

n

aπ =

i=1

xπi(i) .

d (π )

DESCENT REPRESENTATIONS AND MULTIVARIATE STATISTICS

3061

3.2. The index permutation and the exponent partition. The index permun i tation of a monomial m = i=1 xp i ∈ Pn is the unique permutation π = π (m) ∈ Sn such that pπ(i) ≥ pπ(i+1) and pπ(i) = pπ(i+1) =? π (i) < π (i + 1). In other words, π reorders the variables xi by (weakly) decreasing exponents, where the variables with a given exponent are ordered by increasing indices. n i Let m = i=1 xp i be a monomial in Pn , π = π (m) its index permutation, and p (i) n aπ the corresponding descent basis element. Then m = i=1 xππ (i) and aπ =

n i=1

(1 ≤ i < n)

xπi(i) .

d (π )

Claim 3.1. The sequence (pπ(i) ? di (π ))n i=1 of exponents in m/aπ consists of nonnegative integers, and is weakly decreasing: pπ(i) ? di (π ) ≥ pπ(i+1) ? di+1 (π ) (1 ≤ i < n).

Proof. If π (i) < π (i + 1), then di (π ) = di+1 (π ) and the claim follows from pπ(i) ≥ pπ(i+1) . If π (i) > π (i + 1), then di (π ) = di+1 (π ) + 1 and pπ(i) > pπ(i+1) , so that pπ(i) ? pπ(i+1) ≥ 1 = di (π ) ? di+1 (π ). This proves monotonicity. Nonnegativity now follows from dn (π ) = 0, implying pπ(n) ? dn (π ) ≥ 0. For a monomial m =

n i=1

i xp i with index permutation π ∈ Sn , let

λ(m) := (pπ(1) , pπ(2) , . . . , pπ(n) ) be its exponent partition. Note that λ(m) is a partition of the total degree of m. De?ne the complementary partition ?(m) of a monomial m to be the partition conjugate to the partition (pπ(i) ? di (π ))n i=1 . Namely, ?j := |{i | pπ(i) ? di (π ) ≥ j }| (?j ≥ 1).

4 2 3 4 3 2 2 1 0 0 Example. Let m = x2 1 x2 x3 x5 x6 and n = 7. Then m = x2 x6 x1 x3 x5 x4 x7 , λ(m) = (4, 3, 2, 2, 1, 0, 0), π = 2613547 ∈ S7 , (d1 (π ), . . . , d7 (π )) = (2, 2, 1, 1, 1, 0, 0), and ?(m) = (4, 1).

3.3. A partial order for monomials. We shall now de?ne a partial order on the monomials in Pn . Comparable monomials will always have the same total degree. Fix such a total degree p; we may assume p ≥ 1. De?nition. For monomials m1 , m2 of the same total degree p , m1 ? m2 if one of the following holds: (1) λ(m1 ) λ(m2 ) (strictly smaller in dominance order); or (2) λ(m1 ) = λ(m2 ) and inv(π (m1 )) > inv(π (m2 )). The partial order “?” may be replaced, in this paper, by any linear extension of it; for example, by the linear extension obtained by replacing the dominance order by lexicographic order in (1). (This is common in the de?nition of Gr¨ obner bases, which partially motivated our de?nition.)

3062

RON M. ADIN, FRANCESCO BRENTI, AND YUVAL ROICHMAN

3.4. Straightening. Lemma 3.2. Let m ∈ Pn be a monomial and let 1 ≤ k ≤ n. Let S (k) be the set of all monomials which appear (with coe?cient 1) in the expansion of the polynomial m · ek , the product of m and the k -th elementary symmetric function. Let m(k) := m · xπ(1) · xπ(2) · · · xπ(k) , where π = π (m) is the index permutation of m. Then: (1) m(k) ∈ S (k) . (2) m ∈ S (k) and m = m(k) =? m ? m(k) . Proof. (1) is obvious. For (2), let m ∈ S (k) . Then m = m · xi1 xi2 · · · xik , where 1 ≤ i1 < i2 < · · · < ik ≤ n. Now, let λi (m) be the i-th part of the exponent partition of the monomial m. Then λi (m(k) ) ? λi (m) = and also λi (m ) ? λi (m) ∈ {0, 1}

n

1, if 1 ≤ i ≤ k ; 0, if i > k ,

(?i);

[λi (m ) ? λi (m)] = k.

i=1

Thus

t t t

λi (m ) ≤

i=1 t i=1 i=1

[λi (m) + 1] =

t i=1 t

λi (m(k) ) λi (m(k) )

(1 ≤ t ≤ k ), (k < t ≤ n).

λi (m ) ≤ k +

i=1

λi (m) =

i=1

Therefore λ(m ) λ(m(k) ). If λ(m ) λ(m(k) ), then m ? m(k) , as claimed. Otherwise, λ(m ) = λ(m(k) ). Now let I> := {1 ≤ i ≤ n | λi (m) > λk (m)}; I= := {1 ≤ i ≤ n | λi (m) = λk (m)}; I< := {1 ≤ i ≤ n | λi (m) < λk (m)}. Namely, i ∈ I> if the exponent (in m) of xπ(i) is strictly larger than that of xπ(k) ; and similarly for I= and I< . By de?nition, π (m(k) ) = π (m). Since λ(m ) = λ(m(k) ), it follows that π (m ) and π (m) agree on I< ∪ I> , but may di?er on I= . Also, π (m(k) ) = π (m) is monotone increasing on I= . It follows that if m = m(k) , then inv(π (m )) > inv(π (m(k) )) and thus m ? m(k) in the monomial partial order.

DESCENT REPRESENTATIONS AND MULTIVARIATE STATISTICS

3063

Lemma 3.3. Let m1 and m2 be monomials in Pn of the same total degree, and let ek be the k -th elementary symmetric function, 1 ≤ k ≤ n. If m1 ? m2 , then m1 ? m2 , where mi (i = 1, 2) is the ?-maximal summand in mi ek whose existence is guaranteed by Lemma 4.2. Proof. By the de?nition of mi , π (mi ) = π (mi ) and λ(mi ) = λ(mi ) + δ (k) , where δ (k) = (1, . . . , 1, 0, . . . , 0) (k ones, n ? k zeroes). Using this with the de?nition (k ) (k ) of ? shows that m1 ? m2 =? m1 ? m2 . Corollary 3.4. Let m ∈ Pn be a monomial, π = π (m) its index permutation, and ? = ?(m) the complementary partition de?ned in Subsection 3.2. Let S be the set of monomials which appear (with nonzero coe?cient) in the expansion of aπ · e? . Then: (1) m ∈ S . (2) m ∈ S and m = m =? m ? m. Proof. This is proved by iterative applications of Lemma 3.2, using π (m) = π (aπ(m) ) and Lemma 3.3. A straightening algorithm follows. Straightening algorithm. For a monomial m ∈ Pn , let π = π (m) be its index permutation, aπ the corresponding descent basis element, and ? = ?(m) the corresponding complementary partition. Write (by Corollary 3.4) m = a π · e ? ? Σ, where Σ is a sum of monomials m ? m. Repeat the process for each m . Example. Let m = x2 1 x2 x3 ∈ P3 . Then π (m) = 123, aπ (m) = 1 and ?(m) = (3, 1). Hence x2 1 x2 x3 = 1 · e(3,1) ? Σ = (x1 x2 x3 )(x1 + x2 + x3 ) ? Σ, 2 2 2 so Σ = x1 x2 x3 + x1 x2 x2 3 . For the ?rst summand π (x1 x2 x3 ) = 213 and ?(x1 x2 x3 ) = 2 (3). Indeed x1 x2 x3 = a213 · e3 = x2 · (x1 x2 x3 ). Similarly, for the second summand 2 2 π (x1 x2 x2 3 ) = 312 and ?(x1 x2 x3 ) = (3), and x1 x2 x3 = a312 · e3 = x3 · (x1 x2 x3 ). We have obtained x2 1 x2 x3 = a123 · e(3,1) ? a213 · e3 ? a312 · e3 . This algorithm implies Lemma 3.5 (Straightening Lemma). Each monomial m ∈ Pn has an expression m = e?(m) · aπ(m) +

m ?m (k ) (k ) (k ) (k ) (k ) (k )

nm ,m e?(m ) · aπ(m ) ,

where nm ,m are integers. The following corollary appears in [4]. Corollary 3.6. The set {aπ + In | π ∈ Sn } forms a basis for the coinvariant algebra Pn /In . Proof. By Lemma 3.5, {aπ + In | π ∈ Sn } spans Pn /In as a vector space over Q. Since dim (Pn /In ) = |Sn | [21, §3.6], this is a basis.

3064

RON M. ADIN, FRANCESCO BRENTI, AND YUVAL ROICHMAN

3.5. Descent representations. Let λ = (λ1 , . . . , λn ) be a partition with at most n parts. Let Pλ be the subspace of the polynomial ring Pn = Q[x1 , . . . , xn ] spanned by all monomials whose exponent partition is dominated by λ: Pλ := spanQ {m | λ(m) Similarly, de?ne Pλ by strict dominance: Pλ := spanQ {m | λ(m) λ}. These subspaces are Sn -modules consisting of homogeneous polynomials of degree k = |λ|. Now consider the canonical projection of Pn onto the coinvariant algebra ψ : Pn ?→ Pn /In . De?ne Rλ to be a quotient of images under this map: Rλ := ψ (Pλ )/ψ (Pλ ). Then Rλ is also an Sn -module. We will show that every homogeneous component of the coinvariant algebra may be decomposed into a direct sum of certain Rλ ’s. For any subset S ? {1, . . . , n} de?ne a partition λS := (λ1 , . . . , λn ) by λi := | S ∩ {i, . . . , n} | For example, for any π ∈ Sn λDes(π) = (d1 (π ), . . . , dn (π )). Hence we have the following claim. Claim 3.7. For any permutation π ∈ Sn λ(aπ ) = λDes(π) . The Straightening Lemma (Lemma 3.5) implies Lemma 3.8. For any two permutations τ and π in Sn , the action of τ on the monomial aπ ∈ Pn has the expression τ (aπ ) =

{w ∈Sn | λ(aw ) λ(aπ )}

λ}.

(1 ≤ i ≤ n).

nw aw + p,

where nw ∈ Z and p ∈ In . Proof. Apply the Straightening Lemma (Lemma 3.5) to m = τ (aπ ). Note that e?(m ) ∈ In i? ?(m ) = ?, and then m = aπ(m ) . Denoting w := π (m ) we get m m =? λ(aw ) = λ(m ) λ(m) = λ(τ (aπ )) = λ(aπ ). Another description of the Sn -module ψ (Pλ ) follows. Lemma 3.9. For any partition λ ψ (Pλ ) = spanQ {aπ + In | π ∈ Sn , λ(aπ ) Proof. Clearly, for any π ∈ Sn with λ(aπ ) opposite inclusion follows from Lemma 3.5. λ }.

λ, aπ + In = ψ (aπ ) ∈ ψ (Pλ ). The

DESCENT REPRESENTATIONS AND MULTIVARIATE STATISTICS

3065

Let Jλ := spanQ {aπ + In | π ∈ Sn , λ(aπ ) and Jλ := spanQ {aπ + In | π ∈ Sn , λ(aπ ) By Lemma 3.9 Rλ = Jλ /Jλ . Hence Corollary 3.10. The following conditions on a partition λ = (λ1 , . . . , λn ) are equivalent: (1) Rλ = 0. (2) λ = λ(aπ ) for some π ∈ Sn . (3) λ = λS for some S ? [n ? 1]. (4) The di?erence between consecutive parts of λ is either 0 or 1, i.e. (denoting λn+1 := 0), (1 ≤ i ≤ n). λi ? λi+1 ∈ {0, 1} Proof. Rλ = 0 if and only if Jλ = Jλ . This happens if and only if there exists a permutation π ∈ Sn for which λ(aπ ) = λ (since, by Corollary 3.6, the various aπ + In are linearly independent). By Claim 3.7, λ(aπ ) = λS for S = Des(π ). Conversely, any subset of [n ? 1] is a descent set for an appropriate permutation. This shows the equivalence of the ?rst three conditions. The equivalence of (3) and (4) follows easily from the de?nition of λS . From now on denote RS := RλS . For π ∈ Sn , let a ?π be the image of the descent basis element aπ + In ∈ JλS in the quotient RS , where S := Des(π ). Corollary 3.11. For any subset S ? [n ? 1], the set {? aπ | π ∈ Sn , Des(π ) = S } forms a basis of RS . Proof. Follows by elementary linear algebra from Corollary 3.6, Claim 3.7, and the de?nitions of JS , JS and a ?π . Recall the notation Rk for the k -th homogeneous component of the coinvariant algebra Pn /In . Theorem 3.12. For every 0 ≤ k ≤

n 2

λ} λ }.

, RS

S i∈S

Rk ? =

as Sn -modules, where the sum is over all subsets S ? [n ? 1] such that

i = k.

Proof. Note that aπ + In ∈ Rk ?? maj(π ) = k . It follows, by Corollary 3.6, that {aπ + In |maj(π ) = k } is a basis for Rk , so that, by Corollary 3.11, Rk ? = S RS (sum over all S ? [n ? 1] with i∈S i = k ) as vector spaces over Q. By Maschke’s Theorem, if V is a ?nite-dimensional G-module for a ?nite group G (over a ?eld of characteristic zero) and W ? V is a G-submodule, then V ? = W ⊕ (V /W ) as G-modules. Apply this to the poset {JS | S ? [n ? 1] , i = k}

i∈S

3066

RON M. ADIN, FRANCESCO BRENTI, AND YUVAL ROICHMAN

ordered by dominance order on the partitions λS . Using the de?nition of RS , we get by induction on the poset the required isomorphism. 4. Decomposition of descent representations In this section we re?ne the Lusztig-Stanley Theorem. Theorem 4.1. For any subset S ? [n ? 1] and partition ? n, the multiplicity in RS of the irreducible Sn -representation corresponding to ? is mS,? := | { T ∈ SY T (?) | Des(T ) = S } |. The proof applies an argument of Stanley (cf. [28, Theorem 8.8] and references therein), using symmetric functions. Its use is possible here due to the Straightening Lemma. A key lemma in the proof is a multivariate version of Stanley’s formula. 4.1. A multivariate version of Stanley’s Formula. In this subsection we state and prove a multivariate version of a well known formula of Stanley for the principal specialization of a Schur function. Recall that sλ (x1 , . . . , xn ) denotes the Schur function corresponding to a partition λ of n. Then Proposition 4.2 ([36, Prop. 7.19.11]). If λ is a partition of n, then (1 ? where T runs through all standard Young tableaux of shape λ. sλ (1, q, q 2 , . . . ) =

maj(T ) T ∈SY T (λ) q , q )(1 ? q 2 ) · · · (1 ? q n )

De?ne Q[[z1 , z1 z2 , . . .]] to be the ring of formal power series in countably many variables z1 , z1 z2 , . . . , z1 z2 · · · zk , . . . ; a linear basis for it consists of the monomials λ1 λk · · · zn for all partitions λ = (λ1 , . . . , λk ) (λ1 ≥ · · · ≥ λk ≥ 0). Let z λ := z1 Q[[q1 , q1 q2 , . . .]] be similarly de?ned. Let ι : Q[[z1 , z1 z2 , . . .]] ?→ Q[[q1 , q1 q2 , . . .]] be de?ned by (4.1) ι(z λ ) := q λ (?λ), where λ is the partition conjugate to λ. Extend ι by linearity. Note that ι is not a ring homomorphism. For any standard Young tableau T de?ne di (T ) := | { j ≥ i | j ∈ Des(T ) } | (1 ≤ i ≤ n), where Des(T ) is the set of all descents in T (as in Subsection 2.3). Lemma 4.3 (Multivariate Formula). If λ is a partition of n, then ι[sλ (1, z1 , z1 z2 , . . . , z1 z2 · · · zi , . . . )] =

d i (T ) n T ∈SY T (λ) i=1 qi , n i=1 (1 ? q1 q2 · · · qi )

where T runs through all standard Young tableaux of shape λ. Note that Proposition 4.2 is the special case obtained by substituting q1 = q2 = . . . = qn = q . Lemma 4.3 is actually implicit in [32, p. 27] (formula (18), within the proof of Theorem 9.1), in the general context of (P, ω )-partitions. The fact that the LHS there is equal to the LHS above is part of the following proof, which will later be adapted to prove a B -analogue (Lemma 5.10 below). The key bijection is basically the one used in [38, Lemma 3.1].

DESCENT REPRESENTATIONS AND MULTIVARIATE STATISTICS

3067

Proof. By Claim 2.1

∞

sλ (x1 , x2 , . . . ) =

? ∈RSSY T (λ) i=1 T

xi

?) mi (T

,

? runs through all reverse semi-standard Young tableaux of shape λ, and where T ? ) := |{cells in T ? with entry i}| mi (T (?i ≥ 1). Letting x1 = 1 and xi = z1 z2 · · · zi?1 we get sλ (1, z1 , z1 z2 , . . . ) =

? ∈RSSY T (λ) i=1 T

(i ≥ 2)

∞

zi

?) m>i (T

,

where ? ) := |{cells in T ? with entry > i}| m>i (T Of course, ? ) = n. m>0 (T ? ) be the vector (m>1 (T ? ), m>2 (T ? ), . . . ). Then ?(T ? ) is a partition with largest Let ?(T part at most n. Note that the conjugate partition is ?) = (T ?1 ? 1, T ?2 ? 1, . . . , T ?n ? 1), ?(T ?1 , . . . , T ?n are the entries of T ? in weakly decreasing order. Thus where T

n

(?i).

(4.2)

ι[sλ (1, z1 , z1 z2 , . . . )] =

? ∈RSSY T (λ) i=1 T

Ti ?1 qi .

?

Recall that SY T (λ) and RSSY T (λ) are the sets of standard Young tableaux and reverse semi-standard Young tableaux of shape λ, respectively. For any λ n de?ne a map φλ : RSSY T (λ) ?→ SY T (λ) × N n by ? ) := (T, ?), φλ (T ? ∈ RSSY T (λ), T is a standard Young tableau of shape λ and ? = where, for T (?1 , . . . , ?n ) is a sequence of nonnegative integers, de?ned as follows: ?1 , . . . , T ?n ) be the vector of entries of T ?, in weakly decreasing order. (1) Let (T ? , having Then T is the standard Young tableau, of the same shape as T ? has entry T ?i . If some of entry i (1 ≤ i ≤ n) in the same cell in which T ? are equal, then they necessarily belong to distinct columns, the entries of T and the corresponding entries of T are then chosen increasing from left to right (i.e., with increasing column indices). (2) De?ne ?i ? di (T ) ? T ?i+1 + di+1 (T ) ?i := T (1 ≤ i ≤ n), ?n+1 := 1 and dn+1 (T ) := 0. where, by convention, T

3068

RON M. ADIN, FRANCESCO BRENTI, AND YUVAL ROICHMAN

Example. Let λ = (3, 2, 2) and 7 ?= 4 T 3 4 2 1 4 ∈ RSSY T (λ).

?) = (T, ?), the ?rst step yields Computing φλ (T 1 T = 2 5 3 4 6 ∈ SY T (λ), 7

?1 ?d1 (T ), . . . , T ?7 ?d7 (T )) = (4, 2, 2, 2, 2, 1, 1) so that Des(T ) = {1, 4, 6}. Therefore, (T and ? = (2, 0, 0, 0, 1, 0, 0). The following claim is easy to verify. Claim 4.4. (1) φλ is a bijection. ?n ) is the vector of entries of T ? , in weakly decreasing order, and ?1 , . . . , T (2) If (T ? ) = (T, ?), then φλ (T ?i ? 1 = di (T ) + T

j ≥i

?j

(1 ≤ i ≤ n).

? ∈ RSSY T (λ) By Claim 4.4, for any T

n

(4.3)

i=1

Ti ?1 qi =

?

n i=1

qi i

d (T )

n

·

j =1

(q1 · · · qj )?j ,

? ). where (T, ?) = φλ (T Substituting (4.3) into (4.2) we get the formula in the statement of Lemma 4.3. 4.2. Proof of Theorem 4.1. For a permutation τ ∈ Sn let the (graded) trace of its action on the polynomial ring Pn be TrPn (τ ) :=

m

τ (m), m · q ?λ(m) ,

where the sum is over all monomials m in Pn , λ(m) is the exponent partition of the monomial m, and the inner product is such that the set of all monomials is an orthonormal basis for Pn . In particular, τ (m), m ∈ {0, 1} (?τ ∈ Sn ). Claim 4.5. If τ ∈ Sn is of cycle type ?, then the trace of its action on Pn is TrPn (τ ) = ι[p? (1, z1 , z1 z2 , . . . )], where p? is the power sum symmetric function corresponding to ?, and z1 , z2 , . . . are independent variables. Proof. For a monomial m in Pn , τ (m), m = 1 (i.e., τ (m) = m) if and only if, for each cycle of τ , the variables xi with indices in that cycle all have the same exponent in m. If ? = (?1 , . . . , ?t ) is the cycle type of τ we thus obtain, for each sequence (e1 , . . . , et ) ∈ N t , a unique monomial m with τ (m) = m and ej as the

DESCENT REPRESENTATIONS AND MULTIVARIATE STATISTICS

3069

common exponent for cycle number j (1 ≤ j ≤ t). Thus λ(m) consists of ?j copies of ej (1 ≤ j ≤ t), reordered, and ι?1 [? q λ(m) ] = z ?λ(m) =

t

(z1 · · · zej )?j .

j =1

Summing over all choices of e1 , . . . , et gives p? (1, z1 , z1 z2 , . . .). Recall that for the coinvariant algebra Pn /In we have the descent basis {aπ + In | π ∈ Sn }. De?ne, for τ ∈ Sn , TrPn /In (τ ) :=

π ∈ Sn

τ (aπ + In ), aπ + In · q ?λ(aπ ) ,

where the inner product is such that the descent basis is orthonormal. From the Straightening Lemma (Lemma 3.5) it follows that Claim 4.6. For every n ≥ 1 and every τ ∈ Sn TrPn (τ ) = TrPn /In (τ ) ·

λ

q ?λ ,

where the sum is over all partitions λ with at most n parts. Proof. Replace the monomial basis of Pn by the homogeneous polynomial basis {aπ e? | π ∈ Sn , ? is a partition with largest part at most n}. The trace TrPn (τ ) is not changed, provided that we now use the inner product for which the new basis is orthonormal. Note that τ (e? ) = e? (?τ ∈ Sn ). Also note that, by the Straightening Lemma, the ?-maximal monomial m in aπ e? has an exponent partition λ(m) = λ(aπ ) + ? , where addition of partitions is componentwise. Observation 4.7. q ?λ =

λ

1 , 1 ? q 1 · · · qi i=1

n

where the sum is over all partitions λ with at most n parts. Using the Frobenius formula, Lemma 4.3 (the multivariate version of Stanley’s formula) and Claim 4.5, we obtain for every permutation τ ∈ Sn of cycle type ?: TrPn (τ ) = ι[p? (1, z1 , z1 z2 , . . . )] = χλ ?·

λ n T ∈SY T (λ) n i=1 (1 ? q1 q2

χλ ? ι[sλ (1, z1 , z1 z2 , . . .)]

λ n d i (T ) n i=1 qi

=

· · · qi )

n

.

By Claim 4.6 and Observation 4.7 we now get TrPn /In (τ ) =

λ n

χλ ?

T ∈SY T (λ) i=1

qi i

d (T )

.

We conclude that the graded multiplicity in Pn /In of the irreducible Sn -representation corresponding to λ is

n T ∈SY T (λ) i=1

qi i

d (T )

=

T ∈SY T (λ)

q ?λDes(T ) .

3070

RON M. ADIN, FRANCESCO BRENTI, AND YUVAL ROICHMAN

Consider now the claim of Theorem 3.12. Its proof shows that Pn /In ? =

S ?[n?1]

RS

actually holds as an isomorphism of graded Sn -modules. By Corollary 3.11 and Claim 3.7, RS is the homogeneous component of multi-degree λS in Pn /In . It thus follows that the multiplicity in RS of the irreducible Sn -representation corresponding to λ is | {T ∈ SY T (λ) | Des(T ) = S } |, and the proof of Theorem 4.1 is complete. 5. Descent representations for type B In this section we give B -analogues of the concepts and results in Sections 3 and 4. 5.1. The signed descent basis. For any signed permutation σ ∈ Bn let Des(σ ) := {i ∈ [n ? 1] : σ (i) > σ (i + 1)} be the set of descents in σ with respect to the standard linear order on the integers, and let di (σ ) := |{j ∈ Des(σ ) : j ≥ i}| (1 ≤ i ≤ n) be the number of descents in σ from position i on. Also let 1, if σ (i) < 0, εi (σ ) := 0, otherwise, and fi (σ ) := 2di (σ ) + εi (σ ). Note that

n

fi (σ ) = fmaj(σ ).

i=1

Finally, associate to σ the monomial

n

bσ :=

i=1 B In

i x|σ (i)| .

f (σ )

We will show that the set {bσ + | σ ∈ Bn } forms a linear basis for the coinvariant algebra of type B . We call it the signed descent basis. 5.2. Straightening. The signed index permutation of a monomial m = Pn is the unique signed permutation σ = σ (m) ∈ Bn such that (1) (2) and (3) p|σ(i)| ≡ 0(mod 2) ?? σ (i) > 0. In other words, σ reorders the variables xi as does the corresponding index permutation of type A (see Subsection 3.2), after attaching a minus sign to (indices of) variables with odd exponents. Note that this reverses the order of “negative” indices. p|σ(i)| ≥ p|σ(i+1)| (1 ≤ i < n), p|σ(i)| = p|σ(i+1)| =? σ (i) < σ (i + 1)

n i=1

i xp i ∈

DESCENT REPRESENTATIONS AND MULTIVARIATE STATISTICS

3071

3 2 3 3 3 2 2 1 0 0 Example. m = x2 1 x2 x3 x5 x6 and n = 7. Then m = x2 x6 x1 x3 x5 x4 x7 and σ (m) = [?6, ?2, 1, 3, ?5, 4, 7] ∈ B7 .

i Let m = i=1 xp i be a monomial in Pn , σ = σ (m) its signed index permutation, and bσ the corresponding signed descent basis element. In analogy with Claim 3.1 (for type A) we have

n

Claim 5.1. The sequence (p|σ(i)| ? fi (σ ))n i=1 of exponents in m/bσ consists of nonnegative even integers, and is weakly decreasing: p|σ(i)| ? fi (σ ) ≥ p|σ(i+1)| ? fi+1 (σ ) (1 ≤ i < n). Proof. By condition (3) above εi (σ ) = 0 ?? p|σ(i)| ≡ 0(mod 2). The numbers p|σ(i)| ? fi = p|σ(i)| ? εi (σ ) ? 2di (σ ) are therefore even integers. Also dn (σ ) = 0 so that p|σ(n)| ? fn = p|σ(n)| ? εn (σ ) ≥ 0. It remains to show that the sequence is weakly decreasing. If σ (i) < σ (i + 1), then di (σ ) = di+1 (σ ), and p|σ(i)| ? εi (σ ) ≥ p|σ(i+1)| ? εi+1 (σ ) since their di?erence is an even integer ≥ ?1. If σ (i) > σ (i + 1) and εi (σ ) = εi+1 (σ ), then di (σ ) = di+1 (σ ) + 1; so (p|σ(i)| ? fi (σ )) ? (p|σ(i+1)| ? fi+1 (σ )) = p|σ(i)| ? p|σ(i+1)| ? 2 ≥ 0 since p|σ(i+1)| ≡ p|σ(i+1)| (mod 2) and because of conditions (1) and (2) above. Finally, if σ (i) > σ (i + 1) and εi (σ ) = εi+1 (σ ), then σ (i) > 0 > σ (i + 1) so that εi (σ ) = 0, ε(i + 1) = 1 and di (σ ) = di+1 (σ ) + 1. Thus (p|σ(i)| ? fi (σ )) ? (p|σ(i+1)| ? fi+1 (σ )) = p|σ(i)| ? p|σ(i+1)| ? 1 ≥ 0. Denote by ?B (m) the partition conjugate to (

p|σ(i)| ?fi (σ) n )i=1 . 2

De?nition. For monomials m1 , m2 ∈ Pn of the same total degree, m1 ?B m2 if, for every 1 ≤ i ≤ n, the exponents of xi in m1 and m2 have the same parity, and also either λ(m2 ) (strictly smaller in dominance order); or (1) λ(m1 ) (2) λ(m1 ) = λ(m2 ) and inv(π (m1 )) > inv(π (m2 )). Here π (mi ) is the (unsigned) index permutation of mi as in Subsection 3.2. Imitating the proof of Lemma 3.5 we obtain Corollary 5.2 (Straightening Lemma). Each monomial m ∈ Pn has an expression

2 m = e?B (m) (x2 1 , . . . , xn ) · bσ(m) + m ?B m 2 nm ,m e?B (m ) (x2 1 , . . . , xn ) · bσ(m ) ,

where nm ,m are integers. 5.3. Construction of descent representations. Recall (from Subsection 2.5) B the de?nition of In . Corollary 5.3. The set

B {bσ + In | σ ∈ Bn } B forms a basis for the coinvariant algebra Pn /In .

Proof. Similar to the proof of Corollary 3.6. Remark. A di?erent proof of Corollary 5.3 may be obtained by combining and extending the proofs of [5, Theorems 1(3) and 2].

3072

RON M. ADIN, FRANCESCO BRENTI, AND YUVAL ROICHMAN

Corollary 5.4. For any pair of elements τ and σ in Bn , the action of τ on bσ ∈ Pn has the expression τ (bσ ) =

{w ∈Bn | λ(bw ) B where nw ∈ Z and p ∈ In . λ(bσ )}

nw bw + p,

Proof. The same as the proof of Lemma 3.8. Note that, actually, nw = 0 in Corollary 5.4 only if bw and bσ have the same number of odd exponents. Note also that, unlike the case of type A (Claim 3.7), for σ ∈ Bn , λ(bσ ) and λDes(σ) are not necessarily equal. Indeed, for subsets S1 ? [n ? 1] and S2 ? [n] de?ne a vector λS1 ,S2 by λS1 ,S2 := 2λS1 + 1S2 , where λS1 is as in Subsection 3.5 above, 1S2 ∈ {0, 1}n is the characteristic vector of S2 , and addition is componentwise. Thus λS1 ,S2 (i) = 2 · |{j ≥ i| j ∈ S1 }| + 1S2 (i). It should be noted that λS1 ,S2 is not always a partition. Claim 5.5. For any σ ∈ Bn λ(bσ ) = λS1 ,S2 , where Des(σ ) = S1 and Neg(σ ) = S2 . Now de?ne

B := ψ B (Pλ ) / ψ B (Pλ ), Rλ B is the canonical map from Pn onto the coinvariant where ψ B : Pn ?→ Pn /In algebra of type B , and P , P are as in Subsection 3.5. B may be By arguments similar to those given in the proof of Lemma 3.9, Rλ described via the signed descent basis B Rλ = Jλ,B /Jλ,B ,

where

B Jλ,B := spanQ {bσ + In | σ ∈ Bn , λ(bσ )

λ}, λ}.

and

B Jλ,B := spanQ {bσ + In | σ ∈ Bn , λ(bσ )

Corollary 5.6. The following conditions on a partition λ = (λ1 , . . . , λn ) are equivalent: B = 0. (1) Rλ (2) λ = λ(bσ ) for some σ ∈ Bn . (3) λ = λS1 ,S2 for some S1 ? [n ? 1] and S2 ? [n], and λS1 ,S2 is a partition. (4) The di?erence between consecutive parts of λ is either 0, 1 or 2, i.e. (denoting λn+1 := 0), λi ? λi+1 ∈ {0, 1, 2} Proof. Similar to the proof of Corollary 3.10.

B B From now on, denote RS := Rλ . For σ ∈ Bn , denote by ? bσ the image of 1 ,S2 S1 ,S2 B B the signed descent basis element bσ + Iw ∈ JλS ,S ,B in RS1 ,S2 .

1 2

(1 ≤ i ≤ n).

DESCENT REPRESENTATIONS AND MULTIVARIATE STATISTICS

3073

Corollary 5.7. For any S1 ? [n ? 1] and S2 ? [n], the set {? bσ | σ ∈ Bn , Des(σ ) = S1 , Neg(σ ) = S2 }

B . forms a basis of RS 1 ,S2 B B for the k -th homogeneous component of Pn /In . Recall the notation Rk

Theorem 5.8. For every 0 ≤ k ≤ n2 ,

B ? Rk = S1 ,S2 B RS , 1 ,S2

as Bn -modules, where the sum is over all subsets S1 ? [n ? 1] and S2 ? [n] such that λS1 ,S2 is a partition and 2·

i∈S1

i + |S2 | = k.

Proof. Similar to the proof of Theorem 3.12. 5.4. Decomposition of descent representations. In this subsection we give a B -analogue of Theorem 4.1. Theorem 5.9. For any pair of subsets S1 ? [n ? 1], S2 ? [n], and a bipartition (?1 , ?2 ) of n, the multiplicity of the irreducible Bn -representation corresponding to B (?1 , ?2 ) in RS is 1 ,S2 mS1 ,S2 ,?1 ,?2 := | { T ∈ SY T (?1 , ?2 ) | Des(T ) = S1 and Neg(T ) = S2 } |. Again, we need a (type B ) multivariate version of Proposition 4.2. Recall de?nition (4.1) of the mapping ι. Let (λ1 , λ2 ) be a bipartition of n. Recall the de?nitions of a standard Young tableau T = (T 1 , T 2 ) of shape (λ1 , λ2 ) and the sets Des(T ) and Neg(T ) from Subsection 2.3. Denote the set of all standard tableaux of shape (λ1 , λ2 ) by SY T (λ1 , λ2 ). ?1 , T ? 2 ) of reverse A reverse semi-standard Young tableau of shape (λ1 , λ2 ) is a pair (T ?i ? i has shape λi (i = 1, 2); the entries of T semi-standard Young tableaux, where: T are congruent to i (mod 2); the entries in each row are weakly decreasing; and the entries in each column are strictly decreasing. Denote by RSSY T (λ1 , λ2 ) the set of all such tableaux. For any standard Young tableau T = (T 1 , T 2 ) of shape (λ1 , λ2 ) de?ne di (T ) := |{j ∈ Des(T ) | j ≥ i}|, εi (T ) := and fi (T ) := 2di (T ) + εi (T ). Then

n

1, if i ∈ Neg(T ), 0, otherwise,

fmaj(T ) =

i=1

fi (T ).

3074

RON M. ADIN, FRANCESCO BRENTI, AND YUVAL ROICHMAN

Lemma 5.10. If (λ1 , λ2 ) is a bipartition of n, then ι[sλ1 (1, z1 z2 , z1 z2 z3 z4 , . . .) · sλ2 (z1 , z1 z2 z3 , . . .)] =

fi (T ) n i=1 qi T ∈SY T (λ1 ,λ2 ) , n 2 2 2 i=1 (1 ? q1 q2 · · · qi )

where T runs through all standard Young tableaux of shape (λ1 , λ2 ). Proof. By Claim 2.1

∞

sλ (x1 , x2 , . . . ) =

? ∈RSSY T (λ) i=1 T

xi

?) mi (T

,

? runs through all reverse semi-standard Young tableaux of shape λ, and where T ? ) := |{cells in T ? with entry i}| (?i ≥ 1). mi (T ? 2 ) ∈ RSSY T (λ1 , λ2 ) we have (T ? 1 + 1)/2 ∈ RSSY T (λ1 ), where ?1, T Note that for (T 1 ? 1 by (i + 1)/2; and similarly ? (T + 1)/2 is obtained by replacing each entry i of T 2 2 ? T /2 ∈ RSSY T (λ ). Thus

∞

sλ1 (x1 , x2 , . . . ) · sλ2 (y1 , y2 , . . . ) =

? 1 ,T ? 2 )∈RSSY T (λ1 ,λ2 ) i=1 (T

xi

? 1 ) m2i (T ?2 ) m2i?1 (T yi .

Letting x1 = 1 and xi = z1 z2 · · · z2i?2 for sλ1 , while for sλ2 , we get

∞

(i ≥ 2) (i ≥ 1)

? 1 ,T ?2 ) m>i (T

yi = z1 z2 · · · z2i?1

sλ1 (1, z1 z2 , . . .) · sλ2 (z1 , z1 z2 z3 , . . .) =

? 1 ,T ? 2 )∈RSSY T (λ1 ,λ2 ) i=1 (T

zi

,

where ?1, T ? 2 ) := |{cells in (T ?1 , T ? 2 ) with entry > i}| (?i ≥ 1). m>i (T 1 2 1 2 1 2 ? ) be the vector (m>1 (T ? ,T ? ), m>2 (T ? ,T ? ), . . .). Then ?(T ?1 , T ? 2 ) is a ? ,T Let ?(T partition with largest part at most n. The conjugate partition is ? 2 ) = ((T ?1 , T ? 2 )1 ? 1, (T ?1, T ? 2 )2 ? 1, . . . , (T ?1 , T ? 2 )n ? 1), ?1 , T ?(T ? 2 )1 , . . . , (T ?1, T ? 2 )n are the entries of (T ?1, T ? 2 ) in weakly decreasing order. ?1, T where (T Thus

n

(5.1)

ι[sλ1 (1, z1 z2 , . . . ) · sλ2 (z1 , . . .)] =

? 1 ,T ? 2 )∈RSSY T (λ1 ,λ2 ) i=1 (T

qi

? 1 ,T ? 2 )i ?1 (T

.

For any bipartition (λ1 , λ2 ) of n de?ne a map φ(λ1 ,λ2 ) : RSSY T (λ1 , λ2 ) ?→ SY T (λ1 , λ2 ) × N n by ?1, T ? 2 ) := ((T 1 , T 2 ), ?), φ(λ1 ,λ2 ) (T

DESCENT REPRESENTATIONS AND MULTIVARIATE STATISTICS

3075

?1, T ? 2 ) ∈ RSSY T (λ1 , λ2 ), (T 1 , T 2 ) is a standard Young tableau of where, for (T 1 2 shape (λ , λ ) and ? = (?1 , . . . , ?n ) is a sequence of nonnegative integers, de?ned as follows: ? 2 )1 , . . . , (T ?1, T ? 2 )n ) be the vector of entries of (T ?1, T ? 2 ) in weakly ?1 , T (1) Let ((T 1 2 decreasing order. Then (T , T ) is the standard Young tableau, of the ? 2 ), with entry i (1 ≤ i ≤ n) in the same cell in which ?1 , T same shape as (T ?1 , T ? 2 ) has entry (T ?1 , T ? 2 )i . If some of the entries of (T ?1, T ? 2 ) are equal, (T then they necessarily belong to distinct columns (in the same tableau), and the corresponding entries of (T 1 , T 2 ) are then chosen as consecutive integers, increasing from left to right (i.e., with increasing column indices). (2) De?ne ?1, T ? 2 )i ? fi (T 1 , T 2 ) ? (T ?1, T ? 2 )i+1 + fi+1 (T 1 , T 2 ))/2 ?i := ((T ?1, T ? 2 )n+1 := 1 and fn+1 := 0. where, by convention, (T Example. Let (λ1 , λ2 ) = ((3, 1), (2, 1)) be a bipartition of 7, and let ?1, T ?2) = (T 11 7 3 3 , 10 8 2 ∈ RSSY T (λ1 , λ2 ). (1 ≤ i ≤ n),

?1, T ? 2 ) = ((T 1 , T 2 ), ?), the ?rst step yields Computing φ(λ1 ,λ2 ) (T (T 1 , T 2 ) = 1 5 4 6 , 2 3 7 ∈ SY T (λ1 , λ2 ),

so that Des(T 1 , T 2 ) = {1, 4, 6} and Neg(T 1 , T 2 ) = {2, 3, 7}. Therefore (f1 (T 1 , T 2 ), . . . , f7 (T 1 , T 2 )) = (6, 5, 5, 4, 2, 2, 1), ? 2 )1 ? f1 (T 1 , T 2 ), . . . , (T ?1 , T ? 2 )7 ? f7 (T 1 , T 2 )) = (5, 5, 3, 3, 1, 1, 1), ?1, T ((T and ? = (0, 1, 0, 1, 0, 0, 0). The following claim is easy to verify. Claim 5.11. (1) φ(λ1 ,λ2 ) is a bijection. 1 ?2 ?1, T ? 2 )n ) is the vector of entries of (T ?1, T ? 2 ), in weakly ? (2) If ((T , T )1 , . . . , (T 1 2 1 2 ? ? decreasing order, and φ(λ1 ,λ2 ) (T , T ) = ((T , T ), ?), then ?1 , T ? 2 )i ? 1 = fi (T 1 , T 2 ) + (T

j ≥i

2?j

(1 ≤ i ≤ n).

? 2 ) ∈ RSSY T (λ1 , λ2 ), ?1 , T By Claim 5.11, for any (T

n

(5.2)

i=1

qi

? 1 ,T ? 2 )i ? 1 (T

n

=

i=1

qi i

f (T 1 ,T 2 )

n

·

j =1

(q1 · · · qj )2?j .

Substituting (5.2) into (5.1) we get the formula in the statement of Lemma 5.10.

3076

RON M. ADIN, FRANCESCO BRENTI, AND YUVAL ROICHMAN

5.5. Proof of Theorem 5.9. For a permutation τ ∈ Bn let the trace of its action on the polynomial ring Pn be TrPn (τ ) :=

m

τ (m), m q ?λ(m) ,

where the sum is over all monomials m in Pn , λ(m) is the exponent partition of the monomial m, and the inner product is such that the set of all monomials is an orthonormal basis for Pn . Claim 5.12. If τ ∈ Bn is of cycle type (?1 , ?2 ), then the trace of its action on Pn is x, y ?)], TrPn (τ ) = ι[p?1 ,?2 (? where p?1 ,?2 is as in Subsection 2.4, x ? := (1, z1 z2 , z1 z2 z3 z4 , . . . ) and y ? := (z1 , z1 z2 z3 , . . . ). Proof. Let ?1 = (1α1 , 2α2 , . . .) and ?2 = (1β1 , 2β2 , . . .). Then τ (m), m = 0 (and is ±1) i? all variables xi with i in the same cycle of τ have equal exponents in m. The sign depends on the number of negative cycles with odd exponent. Thus ? ι?1 [TrPn (τ )] =

i≥1

?αi (z1 · · · zt )i ?

t≥0

? ·

j ≥1

?βj (?1)s (z1 · · · zs )j ?

s≥0

?

?

= p?1 ,?2 (? x, y ?). Proof of Theorem 5.9. From the Straightening Lemma for type B (Corollary 5.2) it follows that for any τ ∈ Bn TrRB (τ ) · n 1 = TrPn (τ ). 1 ? ( q · · · qi )2 1 i=1

n

Inserting Claim 5.12 and the Frobenius formula for type B (see Subsection 2.4) we obtain

n

TrRB (τ ) = n

n

[1 ? (q1 · · · qi )2 ] · ι[p?1 ,?2 (? x, y ?)]

,λ 1 x)sλ2 (? χλ y )]. ?1 ,?2 sλ (?

1 2

i=1

=

[1 ? (q1 · · · qi )2 ] · ι[

λ1 ,λ2

i=1

Applying the linearity of ι and Lemma 5.10 gives TrRB (τ ) = n

,λ χλ ?1 ,?2

1 2

n (T 1 ,T 2 )∈SY T (λ1 ,λ2 ) i=1

qi i

f (T 1 ,T 2 )

.

λ1 ,λ2

DESCENT REPRESENTATIONS AND MULTIVARIATE STATISTICS

3077

6. Combinatorial identities In this section we apply the above algebraic setting to obtain new combinatorial identities. The basic algebraic-combinatorial tool here is the Hilbert series of polynomial rings with respect to multi-degree rearranged into a weakly decreasing sequence (i.e., a partition). The computation of the Hilbert series follows in general the one presented in [28, §8.3] for total degree; the major di?erence is the fact that total degree gives a grading of the polynomial ring, whereas rearranged multi-degree only leads to a ?ltration: Pn = λ Pλ and Pλ · P? ? Pλ+? . For this reason, not every homogeneous basis for the coinvariant algebra will do: the numerators of the RHS in Theorems 6.2 and 6.5 below are generating functions for the descent basis (signed descent basis, respectively), but other bases (e.g., Schubert polynomials) have di?erent generating functions, and are therefore not appropriate for use here. The success of the argument relies on properties of the descent basis. 6.1. Main combinatorial results. For any signed permutation σ ∈ Bn let di (σ ), ni (σ ), and εi (σ ) have the same meaning as in Subsection 1.2.1. The main result of this section is Theorem 6.1. Let n ∈ P . Then

n σ∈Bn i=1 d (σ)+ni (σ?1 ) n

qi i

=

σ∈Bn i=1

qi

2di (σ)+εi (σ)

.

Proof. Theorem 6.1 is an immediate consequence of Theorems 6.5 and 6.7 below. For any partition λ = (λ1 , . . . , λn ) with at most n positive parts let mj (λ) := | {1 ≤ i ≤ n | λi = j } |

n m ? (λ)

(?j ≥ 0),

n and let denote the multinomial coe?cient m0 (λ),m . 1 (λ),... By considering the Hilbert series of the polynomial ring Pn with respect to weakly decreasing multi-degree we obtain

Theorem 6.2. Let n ∈ P . Then n m ? (λ)

n i=1 λi qi = π ∈ Sn n i=1 (1

(λ)≤n

? q1 · · · qi )

d i (π ) n i=1 qi

in Z [[q1 , . . . , qn ]], where the sum on the left-hand side is taken over all partitions with at most n parts. The theorem will be proved using the following lemma. Recall from Subsection 3.2 the de?nitions of the index permutation π (m) and the complementary partition ?(m) of a monomial m ∈ Pn . Lemma 6.3. The mapping m ?→ (π (m), ?(m) ) is a bijection between the set of all ?), where π ∈ Sn and ? ? is a partition monomials in Pn and the set of all pairs (π, ? with at most n parts. Proof of Lemma 6.3. The indicated mapping is clearly into the claimed set, since the largest part of the complementary partition ?(m) is at most n. Conversely, to each pair (π, ? ?) as in the statement of the lemma, associate the ?-maximal monomial m in the expansion of aπ · e? ?. Thus the ? . Then π (m) = π and ?(m) = ? mapping is a bijection.

3078

RON M. ADIN, FRANCESCO BRENTI, AND YUVAL ROICHMAN

Proof of Theorem 6.2. Recall the notation λ(m) for the exponent partition of a monomial m ∈ Pn . For any partition with n parts denote by q ?λ the product n λi i=1 qi . n For any partition λ with at most n parts, m ? (λ) is the number of monomials in Pn with exponent partition equal to λ. Therefore the Hilbert series of the polynomial ring Pn by exponent partition is equal to the LHS of the theorem. On the other hand, since λ(m) = λ(aπ(m) ) + ?(m) , using Lemma 6.3 we get q ?λ(m) =

m∈Pn m∈Pn

q ?λ(aπ(m) )+?(m) =

π ∈ Sn

q ?λ(aπ ) ·

?

q ?? ,

where ? in the last sum runs through all partitions having at most n parts. By Claim 3.7 and Observation 4.7, this product is equal to the RHS of the theorem. A well-known result, attributed by Garsia [14] to Gessel [18], follows. Corollary 6.4. Let n ∈ P . Then

des(π ) maj(π ) q π ∈ Sn t n i i=0 (1 ? tq )

=

r ≥0

r [r + 1]n qt

in Z [q ][[t]]. Proof. Substitute, in Theorem 6.2, q1 = qt and q2 = q3 = · · · = qn = q , divide both sides by 1 ? t, and apply (3.1) and (3.2). We obtain

des(π ) maj(π ) q π ∈ Sn t n i i=0 (1 ? tq ) ∞

=

(λ)≤n

n tλ1 · q Σi λi · m ? (λ) 1?t n q Σi λi tr . m ? (λ)

=

r =0 (λ)≤n , λ1 ≤r

The coe?cient of tr is n q Σi λi = m ? (λ) q Σi

(

1 ,..., n )∈[0,r ] n

r

i

= (

j =0

q j )n = [r + 1]n q.

(λ)≤n , λ1 ≤r

The same Hilbert series of Pn may be computed in a di?erent way, by considering the signed descent basis for the coinvariant algebra of type B and applying the Straightening Lemma for this type. Theorem 6.5. With notations as in Theorem 6.2, n m ? (λ)

n i=1 λi qi

=

(λ)≤n

2di (σ)+εi (σ) n σ∈Bn i=1 qi n 2 2 i=1 (1 ? q1 · · · qi )

in Z [[q1 , . . . , qn ]], where the sum on the left-hand side runs through all partitions with at most n parts. Recall from Subsection 5.2 the de?nitions of the signed index permutation σ (m) ∈ Bn and the complementary partition ?B (m) of a monomial m ∈ Pn .

DESCENT REPRESENTATIONS AND MULTIVARIATE STATISTICS

3079

Lemma 6.6. The mapping m ?→ (σ (m), ?B (m) ) is a bijection between the set of all monomials in Pn and the set of all pairs (σ, ? ? ), where σ ∈ Bn and ? ? is a partition with at most n parts. Proof of Lemma 6.6. Similar to the proof of Lemma 6.3. Here to each pair (σ, ? ?) 2 2 ( x , . . . , x ), and then σ ( m ) = σ associate the ?-maximal monomial m in bσ · e? ? 1 n ?. and ?B (m) = ? Proof of Theorem 6.5. Again, the LHS of the theorem is equal to the Hilbert series of the polynomial ring Pn by exponent partition. On the other hand, since λ(m) = λ(bσ(m) ) + 2?B (m) , Lemma 6.6 gives q ?λ(m) =

m∈Pn m∈Pn

q ?λ(bσ(m) )+2?B (m) =

σ∈Bn

q ?λ(bσ ) ·

?

q ?2? ,

where ? in the last sum runs through all partitions having at most n parts. By Claim 5.5, this product is equal to the RHS of the theorem. Direct combinatorial arguments imply Theorem 6.7. With notations as in Theorem 6.2, n m ? (λ)

n i=1 λi qi

=

(λ)≤n

di (σ)+ni (σ?1 ) n σ∈Bn i=1 qi n 2 2 i=1 (1 ? q1 · · · qi )

in Z [[q1 , . . . , qn ]]. Proof. De?ne the subset T ? Bn by T := {π ∈ Bn : des(π ) = 0}. It is clear from our de?nitions that di (σu) = di (u) and ni (u?1 σ ?1 ) = ni (σ ?1 ) for all σ ∈ T , u ∈ Sn and 1 ≤ i ≤ n. Therefore

n π ∈Bn i=1

qi i

d (π )+ni (π ?1 )

n

=

u∈Sn σ∈T i=1 n

qi i qi i

d (σu)+ni ((σu)?1 )

=

d (u)+ni (σ?1 )

=

u∈Sn σ∈T i=1 n d (u) qi i u∈Sn i=1

n

·

σ∈T i=1

qi i

n ( σ ?1 )

.

An element σ ∈ T is uniquely determined by the set Neg(σ ?1 ). Hence

n σ∈T i=1

qi i

n ( σ ?1 )

n

=

(1 + q1 · · · qi ).

i=1

Theorem 6.2 completes the proof.

3080

RON M. ADIN, FRANCESCO BRENTI, AND YUVAL ROICHMAN

6.2. Negative and ?ag statistics. In this subsection we present a central result from [1] and show that it may be obtained as a special case of results from the previous subsection. For any σ ∈ Bn de?ne the negative descent multiset by NDes(σ ) := Des(σ ) Neg(σ ?1 ),

where Neg(σ ) is the set of positions of negative entries in σ , de?ned in Subsection 1.2.1. Note that NDes(σ ) can be de?ned rather naturally also in purely Coxeter group theoretic terms. In fact, for i ∈ [n] let ηi ∈ Bn be de?ned by ηi := [1, . . . , i ? 1, ?i, i + 1, . . . , n], so η1 = s0 . Then η1 , . . . , ηn are re?ections of Bn (in the Coxeter group sense; see, e.g., [21]). Clearly NDes(σ ) = {i ∈ [n ? 1] : l(σsi ) < l(σ )} For σ ∈ Bn let ndes(σ ) := |NDes(σ )|, Recall the notation f maj (σ ) = 2 maj (σ ) + |Neg(σ )| and let fdes(σ ) := 2 des(σ ) + ε1 (σ ). Then the two pairs of statistics (fdes, fmaj) and (ndes, nmaj) are equidistributed over Bn . Corollary 6.8 ([1, Corollary 4.5]). Let n ∈ P . Then tndes(σ) q nmaj(σ) =

σ∈Bn σ∈Bn

{i ∈ [n] : l(σ ?1 ηi ) < l(σ ?1 )}.

nmaj(σ ) :=

i∈NDes(σ)

i.

tfdes(σ) q fmaj(σ) .

Proof. Substitute in Theorem 6.1 q1 = qt, q2 = · · · = qn = q , and apply the identities d1 (σ ) + n1 (σ ?1 ) = ndes(σ );

n i=1

(di (σ ) + ni (σ ?1 )) = nmaj(σ );

and

n

(2 · di (σ ) + εi (σ )) = fmaj(σ ).

i=1

Acknowledgments This paper grew out of stimulating discussions with Dominique Foata and Ira Gessel during the conference “Classical Combinatorics” in honor of Foata’s 65th birthday. The authors are indebted to Ira Gessel for the idea of using the coinvariant algebra in the study of multivariate statistics. Thanks are also due to Eli Bagno and Richard Stanley for useful comments.

DESCENT REPRESENTATIONS AND MULTIVARIATE STATISTICS

3081

References

[1] R. M. Adin, F. Brenti and Y. Roichman, Descent numbers and major indices for the hyperoctahedral group, Adv. Appl. Math. 27 (2001), 210–224. [2] R. M. Adin and Y. Roichman, A ?ag major index for signed permutations, Proc. 11-th Conference on Formal Power Series and Algebraic Combinatorics, Universitat Polit` ecnica de Catalunya, Barcelona, 1999, 10–17. [3] R. M. Adin and Y. Roichman, The ?ag major index and group actions on polynomial rings, Europ. J. Combin. 22 (2001), 431–446. MR 2002d:05004 [4] E. E. Allen, The descent monomials and a basis for the diagonally symmetric polynomials, J. Alg. Combin. 3 (1994), 5–16. MR 95e:05121 [5] S. Ariki, T. Terasoma and H. F. Yamada, Higher Specht polynomials, Hiroshima Math. J. 27 (1997), 177–188. MR 98c:05163 [6] H. Barcelo, Young straightening in a quotient Sn -module, J. Alg. Combin. 2 (1993), 5–23. MR 94b:20016 [7] I. N. Bernstein, I. M. Gelfand and S. I. Gelfand, Schubert cells and cohomology of Schubert spaces G/P , Usp. Mat. Nauk. 28 (1973), 3–26. MR 55:2941 [8] A. Bj¨ orner and F. Brenti, Combinatorics of Coxeter Groups, Graduate Texts in Mathematics, Springer-Verlag, to appear. [9] F. Brenti, q -Eulerian polynomials arising from Coxeter groups, Europ. J. Combin. 15 (1994), 417–441. MR 95i:05013 [10] M. Demazure, Invariants sym? etriques entiers des groupes de Weyl et torsion, Invent. Math. 21 (1973), 287–301. MR 49:7268 [11] D. Foata, personal communication, July 2000. [12] D. Foata and G. N. Han, Calcul basique des permutations signees. I. Longueur et nombre d’inversions, Adv. Appl. Math. 18 (1997), 489–509. MR 98c:05001a [13] A. M. Garsia, Combinatorial methods in the theory of Cohen-Macaulay rings, Adv. Math. 38 (1980), 229–266. MR 82f:06002 [14] A. M. Garsia, On the “maj” and “inv” q -analogues of Eulerian polynomials, Linear and Multilinear Algebra 8 (1979/80), 21–34. MR 81h:05017 [15] A. M. Garsia and C. Procesi, On certain graded Sn -modules and the q -Kostka polynomials, Adv. Math. 94 (1992), 82–138. MR 93j:20030 [16] A. M. Garsia and J. Remmel, Shu?es of permutations and the Kronecker product, Graphs and Combinatorics 1 (1985), 217–263. MR 89h:05006 [17] A. M. Garsia and D. Stanton, Group actions of Stanley-Reisner rings and invariants of permutation groups, Adv. Math. 51 (1984), 107–201. MR 86f:20003 [18] I. M. Gessel, Generating functions and enumeration of sequences, Ph.D. Thesis, M.I.T., 1977. [19] I. M. Gessel, Multipartite P -partitions and inner products of Schur functions, Contemp. Math. 34 (1984), 289–302. MR 86k:05007 [20] H. L. Hiller, Geometry of Coxeter Groups, Res. Notes in Math. 54, Pitman, Boston, 1982. MR 83h:14045 [21] J. E. Humphreys, Re?ection Groups and Coxeter Groups, Cambridge Studies in Advanced Mathematics, no. 29, Cambridge Univ. Press, Cambridge, 1990. MR 92h:20002 [22] D. Kazhdan and G. Lusztig, Representations of Coxeter groups and Hecke algebras, Invent. Math. 53 (1979), 165–184. MR 81j:20066 [23] W. Kraskiewicz and J. Weyman, Algebra of coinvariants and the action of a Coxeter element, Bayreuther Math. Schriften 63 (2001), 265–284 (preprint: University of Torun, 1987). MR 2002j:20026 [24] I. G. Macdonald, Symmetric Functions and Hall Polynomials, second edition, Oxford Math. Monographs, Oxford Univ. Press, Oxford, 1995. MR 96h:05207 [25] P. A. MacMahon, Combinatory Analysis, Chelsea, New York, 1960. (Originally published in 2 vols. by Cambridge University Press, 1915-1916.) MR 25:5003 [26] H. Morita and H. F. Yamada, Higher Specht polynomials for the complex re?ection group G(r, p, n), Hokkaido Math. J. 27 (1998), 505–515. MR 99k:20085 [27] V. Reiner, Signed permutation statistics, Europ. J. Combin. 14 (1993), 553–567. MR 95e:05008 [28] C. Reutenauer, Free Lie Algebras, London Math. Soc. Monographs, New Series 7, Oxford Univ. Press, 1993. MR 94j:17002

3082

RON M. ADIN, FRANCESCO BRENTI, AND YUVAL ROICHMAN

[29] B. E. Sagan, The Symmetric Group: Representations,Combinatorial Algorithms & Symmetric Functions, Wadsworth & Brooks/Cole, 1991. MR 93f:05102 [30] L. Solomon, The orders of the ?nite Chevalley groups, J. Algebra 3 (1966), 376–393. MR 33:7424 [31] T. A. Springer, A construction of representations of Weyl groups, Invent. Math. 44 (1978), 279–293. MR 58:11154 [32] R. P. Stanley, Ordered Structures and Partitions, Memoirs Amer. Math. Soc. no. 119, 1972. MR 48:10836 [33] R. P. Stanley, Invariants of ?nite groups and their applications to combinatorics, Bull. Amer. Math. Soc. (new series) 1 (1979), 475–511. MR 81a:20015 [34] R. P. Stanley, Some aspects of group acting on ?nite posets, J. Combin. Theory Ser. A 32 (1982), 132–161. MR 83d:06002 [35] R. P. Stanley, Enumerative Combinatorics, Vol. 1, Wadsworth and Brooks/Cole, Monterey, CA, 1986. MR 87j:05003 [36] R. P. Stanley, Enumerative Combinatorics, Vol. 2, Cambridge Studies in Advanced Mathematics 62, Cambridge Univ. Press, Cambridge, 1999. MR 2000k:05026 [37] R. Steinberg, On a theorem of Pittie, Topology 14 (1975), 173–177. MR 51:9101 [38] J. Stembridge, On the eigenvalues of representations of re?ection groups and wreath products, Paci?c J. Math. 140 (1989), 353–396. MR 91a:20022 [39] T. Terasoma and H. F. Yamada, Higher Specht polynomials for the symmetric group, Proc. Japan Acad. Ser. A Math. Sci. 69 (1993), 41–44. MR 94b:20020 Department of Mathematics and Statistics, Bar-Ilan University, Ramat-Gan 52900, Israel E-mail address : radin@math.biu.ac.il ? di Roma “Tor Vergata”, Via della Ricerca Dipartimento di Matematica, Universita Scientifica, 00133 Roma, Italy E-mail address : brenti@mat.uniroma2.it Department of Mathematics and Statistics, Bar-Ilan University, Ramat-Gan 52900, Israel E-mail address : yuvalr@math.biu.ac.il

- A Step-by-Step Approach to Using SAS for Univariate and Multivariate Statistics
- Entropy, Information Matrix and order statistics of Multivariate Pareto, Burr and related d
- Multivariate statistics of Jacobian matrices in Tensor Based Morphometry and their applicat
- DATO (Descent and Ascent Trajectory Optimisation)- A tool for quick evaluations of descent and asce
- The US 2000-2002 Market Descent How Much Longer and Deeper
- METHODOLOGY AND IMPROVEMENTS IN AIRCREW PARACHUTE DESCENT VIRTUAL REALITY SIMULATION TRAINI
- T Mars Exploration Rovers Entry, Descent, and Landing Trajectory Analysis
- Colored-Descent Representations of Complex Reflection Groups G(r,p,n)
- MMW-Scanning Radar for Descent Guidance and Landing Safeguard
- The effect of the descent technique and truck cabin layout on the landing impact forces

更多相关文章：
**
***Multivariate* Analysis_Chap1_Aspects_图文.ppt

Note From UIC*Statistics* course. STAT 4020 *Multivariate* Analysis Dr. Peng ...more sophisticated graphical *representations* of multi-dimensional data can be used...**
统计学习导论(1)_图文.pdf
**

*Statistics* vs. Artificial intelligence ?Application ...*Multivariate* Gaussian 2015/9/18 39 Gaussian ...*descent* Constrained *and* linear linear programming...**
数学名词英语翻译.txt
**

*multivariate* analysis 多元分析 N negative ...*statistics* 次序统计量 origin 原点 orthogonal 正交的...*descent* 最速下降法 transpose 转置 U unconstrained ...**
High-Dimensional Image Registration Using Symmetric....pdf
**

Bayesian*statistics* are used to obtain a maximum ...A gradient *descent* algorithm is presented that ...We have previously presented a *multivariate* approach...**
A SEQUENTIAL APPROACH FOR MULTI-CLASS DISCRIMINANT ANALYSIS....pdf
**

(LDA) is a classical*multivariate* technique both ...This strategy allows low dimensional *representations* ...*descent* strategy avoiding the need of inverting or...**
A ***multivariate* Lagrange inversion formula for asymp....pdf

estimate [tn ] g (w(t)) by steepest*descent* or stationary phase, one ...[2] E. A. Bender *and* L. B. Richmond, Asymptotics for *multivariate* ...**
2013_Google speech recognition Lecture 14-Neural Ne....pdf
**

*Multivariate* Bernouilli random variables P (? yi ...*and* make a Stochastic Gradient *Descent* (SGD) update...(1986). Learning *representations* by back-...**
Score ***and* information for recursive exponential mod....pdf

Hessian,*multivariate* normal prior, Dirichlet prior...(1995) with a gradient-*descent* application for ...r=1 p *and* take as canonical *statistics* t6jx (...**
Mapping symbolic knowledge into locally receptive f....pdf
**

*and* compared with multi-layer perceptron *and* *multivariate* statistical analysis....3.2 Symbolic Algorithms Gradient *Descent* As we adopted continuous activation ...**
Optimal kernel shapes for local linear regression.pdf
**

it leads to an e cient gradient*descent* algorithm...*multivariate* Gaussian with mean x0 *and* covariance ...Tech. report, Department of *Statistics*, Stanford ...**
A non-linear information maximisation algorithm tha....pdf
**

*statistics* than those second-order ones involved ...stochastic gradient *descent* learning rule: w w x...Analogously to eq.3, the *multivariate* probability ...**
A COMPARISON OF SADDLEPOINT APPROXIMATIONS FOR MARG....pdf
**

*statistics* *and* used them to derive a very ...*descent* from the saddlepoint, one can derive a ...For *multivariate* problems, the key issue from a ...**
...Matrix Parameterization of the ***Multivariate*.pdf

Matrix Parameterization of the*Multivariate*_专业资料...However, we can use gradient *descent* to ?nd a...B. Petersen *and* M. S. Pedersen. http://...**
Deep Learning with Kernel Regularization for Visual....pdf
**

*descent*, *and* demonstrate encouraging results on a ...nite set of inputs is a *multivariate* Gaussian. ...compact document *representations* with deep networks....**
Quality Control ***and* Diagnostic_图文.pdf

(MOVE/MRI.COM)*Multivariate* Ocean Variational Estimation (MOVE) System → ...Preconditioned nonlinear *descent* scheme It is possible to apply nonlinear constrain...**
Fast Change Point Detection in Switching Dynamics u....pdf
**

Note that the extension to*multivariate* time ...for the given t (i) using gradient *descent*. Since...The Annals of Mathematical *Statistics*, 41:164{171...**
Gauge Fixing ***and* the Gibbs Phenomenon.pdf

general method for finding the minimum or maximum of a*multivariate* function...2 The initial vector is taken to be in direction of steepest *descent* from...**
On minimax prediction for nonparametric autoregress....pdf
**

The majority of the known estimates of*multivariate* regression functions, see...It has been rst introduced in 7] *and* is referred to as mirror-*descent* ...**
MODEL COMPARISON FOR MONTHLY FORECASTS OF THE CAC 40.pdf
**

*and* *multivariate* ARX models that employ as "exogenous" variables the various...*descent*, *and* we retain the network having the lowest error on the CS ...**
Density estimation with stagewise optimization of t....pdf
**

We consider*multivariate* density estimation with identically...*descent* algorithm, *and* then extended to regression...Technical report 460, Department of *Statistics*,... 更多相关标签：

Note From UIC

Bayesian

(LDA) is a classical

estimate [tn ] g (w(t)) by steepest

Hessian,

it leads to an e cient gradient

Matrix Parameterization of the

(MOVE/MRI.COM)

Note that the extension to

general method for finding the minimum or maximum of a

The majority of the known estimates of

We consider