CHARACTERS AND INVERSIONS

IN THE SYMMETRIC GROUP

Anne de Médicis, Victor Reiner, Mark Shimozono

Department of Mathematics University of Minnesota Minneapolis, MN 55455

November 1993

Abstract We consider sums of the form

∑_{π∈S_{n}} χ^{λ/μ}(π) q^{inv(π)}

where χ^{λ/μ} is a skew character of the symmetric group and inv(π) is the number of inversions of π. Our main result gives a lower bound on the number of factors of 1 + q and 1 − q which divide the above sum, and is shown to be sharp when λ/μ is a hook partition shape.

Résumé Nous considérons des sommes de la forme

∑_{π∈S_{n}} χ^{λ/μ}(π) q^{inv(π)}

où χ^{λ/μ} est un caractère gauche du groupe symétrique et inv(π) désigne le nombre d’inversions de π. Notre résultat principal donne une borne inférieure pour le nombre de facteurs (1 + q) et (1 − q) qui divisent ces sommes. Nous démontrons en particulier que cette borne est exacte lorsque λ/μ est une équerre.

Typeset by AMS-TEX

Section 1. Introduction

In this paper, we consider sums over the symmetric group S_{n} of the form

∑_{π∈S_{n}} χ^{λ/μ}(π) q^{inv(π)}

where χ^{λ/μ} is a skew character of the symmetric group [JP] and inv(π) is the number of inversions of π, i.e.

inv(π) = #{(i, j) : 1 ≤ i < j ≤ n, π^{−1}(i) > π^{−1}(j)}.

There are two motivations for considering such sums. Firstly, other than some special results of Gessel [Ge] and Edelman [Ed], there is very little known about the joint distribution of inversions and conjugacy class (i.e. cycle type) in S_{n}. This is in stark contrast to the joint distributions known for inversions and descent statistics [GaGe], and for cycle type and descent statistics [GR]. Thus it seems reasonable to ask what can be said about the sum

∑_{π∈S_{n}} f(π) q^{inv(π)}

when f is some class function, i.e. a function which is constant on conjugacy classes in S_{n}, such as an irreducible character χ^{λ}.

Remark As pointed out by the referee, there is a different interpretation one can attach to these sums, namely that

∑_{π∈S_{n}} χ^{λ/μ}(π) q^{inv(π)} = ⟨s_{λ/μ}, F_{n}⟩

where ⟨, ⟩ is the usual Hall inner product on symmetric functions, s_{λ/μ} is the skew Schur function corresponding to λ/μ, and F_{n} is a certain symmetric function with coefficients in Z[q] which encodes all the information about the distribution of inversions and conjugacy class in S_{n}:

F_{n} := ∑_{π∈S_{n}} q^{inv(π)}p_{λ(π)}

where p_{λ}(π) is the power sum symmetric function corresponding to the cycle type of π (see [Mac]).

The second motivation is by analogy to the work of [DF,Re]. Here it was shown that sums of the form

∑_{π∈W} χ(w) q^{des(π)}

have high divisibility by linear polynomial factors, where W is a classical Weyl group, χ is a one-dimensional character of W, and des is the descent statistic on W.

Our main theorem is the following Theorem 1. Let λ/μ be a skew shape with longest row of length r and longest column of length s. Then

∑_{π∈S_{n}} χ^{λ/μ}(π) q^{inv(π)}

is divisible by

(1 + q)^{⌊r/2⌋}(1 − q)^{⌊s/2⌋}.

This Theorem is proven in Section 2.

The divisibilities in the previous theorem are sometimes tight, as demonstrated by

Theorem 2. If λ is a hook partition (r, 1^{s−1}) then

\begin{aligned}∑_{π∈S_{n}} χ^{λ}(π) q^{inv(π)} & = (1 − q)^{⌊s/2⌋}S(q) \\ & = (1 + q)^{⌊r/2⌋}R(q) \end{aligned}

where S(q), R(q) ∈ ℤ[q] satisfy

S(1) = \{ \begin{matrix}\frac{(n+1)!⌊s/2⌋!}{(s+1)!} & s is even \\ \frac{n!⌊s/2⌋!}{s!} & s is odd \end{matrix}

and

R(−1) = \{ \begin{matrix}\frac{(n+1)!⌊r/2⌋!}{(r+1)!} & r is even \\ \frac{n!⌊r/2⌋!}{r!} & r is odd \end{matrix}

This is proven in Section 2. It is also conjectured there that S(q) has nonnegative coefficients whenever r ≥ s. In Section 3, we look more closely at the very special case s = 2 where can prove this conjecture by an interesting bijection. In this special case, the results relate to the joint distribution of fixed points and inversions over the symmetric group.

Section 2. Proof of Theorem 1

Theorem 1 will follow by a sequence of straightforward reductions from the following lemma, which appears to be the essence of the divisibilities appearing in this context. Notation: for A ⊆ [n], let S_{A} be the subgroup of permutations in S_{n} which only permute within the elements of A and fix all elements of [n] − A.

Lemma 3. Fix a subset A ⊆ [n] having cardinality r and fix any permutation σ ∈ S_{[n]−A}. Then

∑_{π∈S_{A}} q^{inv(πσ)}

is divisible by (1 + q)^{⌊r/2⌋}

Proof:. Make a change of variable to p = 1 + q. We need to show p^{⌊r/2⌋} divides

\begin{aligned}∑_{π∈S_{A}}(p − 1)^{inv(πσ)} & = ∑_{{π∈S_{A} \atop J⊆Inv(π)}} p^{#J}(−1)^{inv(πσ)−#J} \\ & = ∑_{J⊆\binom{[n]}{2}}(−1)^{inv(σ)+#J}p^{#J} ∑_{{π∈S_{A} \atop J⊆Inv(π)}}(−1)^{inv(π)} \end{aligned}

Here Inv(π) denotes the inversion set of π, that is

Inv(π) = {(i, j) : 1 ≤ i < j ≤ n, π^{−1}(i) > π^{−1}(j)}

So it suffices to show that for any J ⊆ \binom{[n]}{2} with #J < ⌊r/2⌋ we have

∑_{{π∈S_{A} \atop J⊆Inv(π)}}(−1)^{inv(π)} = 0

Since 2#J ≤ r − 2, there must exist a pair i, j ∈ A which are not involved in any of the pairs in J, and hence multiplication on the left by the transposition (ij) is a sign-reversing involution which shows all terms in the above sum cancel. □

Remark The preceding lemma bears some resemblance to results of Björner and Wachs [BW] on the distribution of inversions over certain subsets of S_{n} which they call generalized quotients. In particular, for certain of these generalized quotients, they produce nice hook-formula factorizations for the generating function of inversions, which naturally have high divisibility by (1+q). It would be desirable to understand this connection better.

Proof of Theorem 1. We wish to show that if λ/μ is a skew shape with longest row of length r and longest column of length s, then

∑_{π∈S_{n}} χ^{λ/μ}(π) q^{inv(π)}

is divisible by

(1 + q)^{⌊r/2⌋}(1 − q)^{⌊s/2⌋}.

Our strategy will be to reduce the theorem to a very special case and then apply the Lemma.

First note that if (λ/μ)^{t} denotes the skew shape which is the transpose of λ/μ, then

\begin{aligned}∑_{π∈S_{n}} χ^{(λ/μ)^{t}}(π) q^{inv(π)} & = ∑_{π∈S_{n}} χ^{λ/μ}(π) sgn(π) q^{inv(π)} \\ & = ∑_{π∈S_{n}} χ^{λ/μ}(π) (−q)^{inv(π)} \end{aligned}

using the fact that

χ^{(λ/μ^{t})}(π) = χ^{λ/μ}(π) sgn(π)

Therefore it suffices to show only divisibility by (1 + q)^{⌊r/2⌋}.

Using the Littlewood-Richardson rule [Sa], one knows that

χ^{λ/μ}(π) = ∑_{ν} χ^{ν}(π)

where the sum ranges over a multiset of partitions ν which all have longest part of size at least r. Then using the Jacobi-Trudi identity [Sa], one can write

χ^{ν}(π) = ∑_{ρ} ±χ^{H(ρ)}(π)

Here ρ runs over a set of partitions of n, and H(ρ) is the skew diagram having disjoint horizontal rows of size ρ_{i} for each i.

Furthermore, expanding the Jacobi-Trudi determinant along its top row tells us that each ρ appearing in the above sum will have its largest part ρ_{1} of size at least r. Since we are only trying to show divisibility by (1 + q)^{⌊r/2⌋}, it therefore suffices to prove the theorem in the special case where λ/μ = H(ρ) for some partition ρ with largest part of size r.

The character χ^{H(ρ)} is easy to write down explicitly, as it is the character of the permutation representation of S_{n} acting on the left cosets of the Young subgroup S_{ρ} which permutes the first ρ_{1} numbers among themselves, permutes the next ρ_{2} among themselves, etc. So χ^{H(ρ)}(π) is the number of such left cosets fixed by π. Therefore,

∑_{π∈S_{n}} χ^{H(ρ)}(π) q^{inv(π)} = ∑_{π∈S_{n}} #{cosets τS_{ρ} : πτS_{ρ} = τS_{ρ}} q^{inv(π)}

= ∑_{cosets τS_{ρ}} ∑_{{π∈Sn \atop πτSρ=τSρ}} q^{inv(π)}

= ∑_{{(A_{1},... ,A_{k}) \atop ⊎A_{i}=[n],#A_{i}=ρ_{i}}} ∑_{{(π_{1},... ,π_{k}) \atop π_{i}∈S_{A_{i}}}} q^{inv(π_{1}···π_{k})}

= ∑_{{(A_{1},... ,A_{k}) \atop ⊎A_{i}=[n],#A_{i}=ρ_{i}}} ∑_{{(π_{2},... ,π_{k}) \atop π_{i}∈S_{A_{i}}}} ∑_{π_{1}∈S_{A_{1}}} q^{inv(π_{1}σ)}

where σ = π_{2} ⋯ π_{k} in the last summation. By the Lemma, each of these sums

∑_{π_{1}∈S_{A_{1}}} q^{inv(π_{1}σ)}

are divisible by (1 + q)^{⌊r/2⌋}, and hence the theorem is proven. □

Remark At least some of the divisibility asserted by Theorem 1 is immediate, namely that for s ≥ 2 the sum is divisible by (1 − q)^{1}, and by the transpose symmetry, for r ≥ 2 the sum is divisible by (1 + q)^{1}. We simply note that by the Littlewood-Richardson rule, for s ≥ 2, χ^{λ/μ} does not contain the trivial character in its irreducible decomposition, and hence by the orthogonality relation for characters, we have

[ ∑_{π∈S_{n}} χ^{λ/μ}(π) q^{inv(π)}]_{q=1} = ∑_{π∈S_{n}} χ^{λ/μ}(π) · 1(π) = 0

This implies the sum is divisible by (1 − q)^{1}.

Section 3. Proof of Theorem 2 We only give a sketch of the proof. To begin, we note that our earlier comment about the effect of transposing the

shape λ/μ on the sum implies that we only need to prove that S(1) has the asserted value.

We will proceed by descending induction on r, beginning with the base case r = n. Note that in this case χ^{(r,1^{s−1})} is the trivial character and

∑_{π∈S_{n}} q^{inv(π)} = [n]!_{q} = [n]_{q}[n − 1]_{q} ⋯ [2]_{q}[1]_{q}

where [n]_{q} = 1 + q + q^{2} + ... + q^{n−1}. The theorem then immediately follows in this case from the above expression. For the inductive step, our strategy will be to replace χ^{(r,1^{s−1})} with a character we can compute more explicitly. Let (1^{s−1}) ⊕ (r) denote the skew shape which has a column of size s − 1 disjoint from a row of size r. By an easy case of the Littlewood-Richardson rule,

χ^{(1^{s−1})⊕(r)} = χ^{(r,1^{s−1})} + χ^{(r+1,1^{s−2})}

and hence

χ^{(r,1^{s−1})} = χ^{(1^{s−1})⊕(r)} − χ^{(r+1,1^{s−2})}

Using the last equation, one can check that the inductive step is equivalent to proving the following:

[\frac{∑_{π∈S_{n}} χ^{(1^{s−1})⊕(r)}(π) q^{inv(π)}}{(1 + q)^{⌊r/2⌋}} ]_{q=−1} = \{ \begin{matrix}\frac{(n+2)n!⌊r/2⌋!}{(r+1)!} & r is even \\ \frac{n!⌊r/2⌋!}{r!} & r is odd \end{matrix}

To prove the last expression, we make the change of variable p = 1 + q as before, and we will use the fact that the character χ^{(1^{s−1})⊕(r)} is the induction from S_{s−1}×S_{r} to S_{n} of the character sgn ⊗ 1. We then have

[\frac{∑_{π∈S_{n}} χ^{(1^{s−1})⊕(r)}(π) q^{inv(π)}}{(1 + q)^{⌊r/2⌋}} ]_{q=−1}

= [\frac{∑_{π∈S_{n}} χ^{(1^{s−1})⊕(r)}(π) (p − 1)^{inv(π)}}{p^{⌊r/2⌋}} ]_{p=0}

= [p^{−⌊r/2⌋} ∑_{π∈S_{n}} ∑_{{A∈\binom{[n]}{s−1} \atop π(A)=A}} sgn(π|_{A})(p − 1)^{inv(π)}]_{p=0}

= [p^{−⌊r/2⌋} ∑_{π∈S_{n}} ∑_{{A∈\binom{[n]}{s−1} \atop π(A)=A}} sgn(π|_{A}) ∑_{{J⊆\binom{[n]}{2} \atop J⊆Inv(π)}} p^{#J}(−1)^{inv(π)−#J} ]_{p=0}

= (−1)^{⌊r/2⌋} ∑_{{A∈\binom{[n]}{s−1}, J⊆\binom{[n]}{2} \atop #J=⌊r/2⌋}} ∑_{{π∈Sn \atop π(A)=A, J⊆Inv(π)}} sgn(π|_{[n]−A})

The proof then proceeds by finding a sequence of relatively simple sign-reversing involutions which sieve the above sum down to a small set of terms, each having sign (−1)^{⌊r/2⌋}. and having the desired cardinality to prove the assertion. □

The data suggests that even more is true in the hook case:

Conjecture 4. Let λ be a hook partition (r, 1^{s−1}), and S(q) as before, i.e

∑_{π∈S_{n}} χ^{λ}(π) q^{inv(π)} = (1 − q)^{⌊s/2⌋}S(q)

If r ≥ s, then S(q) has non-negative coefficients.

Section 4. The defining representation

When s = 2, the character χ^{(r,1^{s−1})} is essentially the defining character of S_{n}, i.e. the permutation representation of S_{n} acting on [n]. This character has the particularly simple expression

χ^{(n−1,1)}(π) = #F ix(π) − 1

where F ix(π) is the set of fixed points or 1-cycles of π i.e.

F ix(π) = {k : 1 ≤ k ≤ n, π_{k} = k}

Therefore our results in this case have interpretations in terms of the joint distribution of fixed points and inversions over the symmetric group, some of which are interesting. For example, it is well-known and easy to see that “the average permutation in S_{n} has one fixed point” and “the average permutation in S_{n} has \frac{1}{2} \binom{n}{2} inversions”. The following corollary asserts that the value of #F ix(π) · inv(π) for the “average permutation π in S_{n}” is

\frac{(3n + 1)(n − 2)}{12}

Corollary 5.

∑_{π∈S_{n}} #F ix(π) · inv(π) = \frac{(3n + 1)(n − 2)}{12}n!

Proof. Let f(q) denote the sum

∑_{π∈S_{n}} χ^{(n−1,1)}(π) q^{inv(π)} = ∑_{π∈S_{n}}(#F ix(π) − 1) q^{inv(π)}

Then we have

S(1) = {lim \atop q → 1} (\frac{f(q)}{1 − q} )

= [\frac{d}{dq} f(q)]_{q=1}

= ∑_{π∈S_{n}}(#F ix(π) − 1) · inv(π)

By Theorem 2 in the case s = 2, we have S(1) = (n + 1)!/6. Combining this with the easy fact that

∑_{π∈S_{n}} inv(π) = \binom{n}{2} \frac{n!}{2}

gives the result. □

The preceding result can be considerably strengthened:

Proposition 6.

∑_{π∈S_{n}} #F ix(π) q^{inv(π)} = ∑_{k=1}^{n}[k − 1]!_{q}[n − k]!_{q} ∑_{j≥0} q^{j^{2}+2j} \left[{k − 1 \atop j}\right]_{q} \left[{n − k \atop j}\right]_{q}

where

\left[{n \atop k}\right]_{q} = \frac{[n]!_{q}}{[k]!_{q}[n − k]!_{q}}

.

Proof.

\begin{aligned}∑_{π∈S_{n}} #F ix(π) q^{inv(π)} & = ∑_{k=1}^{n} ∑_{{π∈Sn \atop π_{k}=k}} q^{inv(π)} \\ & = ∑_{k=1}^{n} ∑_{σ∈S_{[1,k−1]}×S_{\{k}\}×S_{[k+1,n]}} q^{inv(σ)} ∑_{{τ∈Sn, τ_{k}=k \atop τ_{1}<···τ_{k−1}, τ_{k+1}<···τn}} q^{inv(τ)} \end{aligned}

where the last equality comes from the well-known fact that any permutation π may be factored uniquely as π = στ with σ ∈ S_{[1,k−1]} × S_{{k}} × S_{[k+1,n]} and

τ_{1} < ⋯ < τ_{k−1} and τ_{k+1} < ⋯ τ_{n}

Note that we are restricting this factorization to the set of π which fix k, but this creates no difficulties. Since ∑_{π∈S_{n}} q^{inv(π)} = [n]!_{q}, we have

∑_{π∈S_{n}} #F ix(π) q^{inv(π)} = ∑_{k=1}^{n}[k − 1]!_{q}[n − k]!_{q} ∑_{{τ∈Sn, τ_{k}=k \atop τ_{1}<···τ_{k−1}, τ_{k+1}<···τn}} q^{inv(π)}

and it only remains to compute the last sum on the right-hand side. Given such a τ, define two subsets J_{1}, J_{2} ⊆ [n] by

\begin{aligned}J_{1} & = \{i : 1 ≤ i ≤ k − 1, τ^{−1}(i) ≥ k + 1\} \\ J_{2} & = \{i : k + 1 ≤ i ≤ n, τ^{−1}(i) ≤ k − 1\} \end{aligned}

Note that J_{1}, J_{2} must have the same cardinality which we denote by j, and choosing the sets J_{1}, J_{2} completely determines τ. There are exactly j^{2} inversions between J_{1} and J_{2}, and exactly 2j inversions between k and J_{1}, J_{2}. This accounts for the q^{j^{2}+2j} term in the sum. The remaining inversions of τ come from among the numbers in [1, k − 1] and among the numbers in [k + 1, n], and correspond to MacMahon’s “inv” statistic on subsets [Ma] applied to the sets J_{1}, J_{2} respectively. Since the distribution of “inv” over k-subsets of an n-set is given by \left[{n \atop k}\right]_{q}, the theorem follows. □

Remark The last sum on the right-hand side in the preceding theorem is similar to the q-Vandermonde convolution

∑_{j≥0} q^{j^{2}} \left[{k − 1 \atop j}\right]_{q} \left[{n − k \atop j}\right]_{q} = \left[{n − 1 \atop k}\right]_{q}

but does not sum so nicely. However, when we set q = 1 or q = −1, the two are the same.

Finally, we wish to prove the s = 2 case of Conjecture 4. Unravelling the statement in this case, it conjectures that for all k ≤ n, one has

∑_{{π∈Sn \atop inv(π)≤k}} #F ix(π) ≥ #\{π ∈ S_{n} : inv(π) ≤ k\}

Recalling that the average permutation in S_{n} has one fixed point, this may be paraphrased as saying that the set of all permutations with length at most k have, on average, “more than their fair share” of fixed points. This seems plausible, since one would think that having few inversions and having fixed points should be positively correlated. It is not hard to see that the assertion follows from

Theorem 7. There exists a bijection ϕ between the sets

{(π, k) : π ∈ S_{n}, k ∈ [n], π_{k} = k} ↔ S_{n}

with the property that if ϕ(π, k) = σ then inv(σ) ≥ inv(π).

Proof. First define the folding bijection f : [n] → [n] by

f(k) = \{ \begin{matrix}2 min\{k − 1, n − k\} + 1 & if k ≤ ⌈\frac{n}{2}⌉ \\ 2 min\{k − 1, n − k\} + 2 & if k > ⌈\frac{n}{2}⌉ \end{matrix}

Given a pair (π, k) as in the left-hand side of the theorem, define the permutation σ = σ_{1}σ_{2} ⋯ σ_{n} as follows: σ_{1} = f(k), and σ_{2}, …, σ_{n} are the numbers [n] − f(k) listed in the same relative order of magnitude as π_{1}, …, π_{k−1}, π_{k+1}, … π_{n}. It is easy to check that this is a bijection with the desired property. □

Can such a bijection ϕ be found so that σ ≥ π in weak Bruhat order? This would imply that the permutations in any lower order ideal of weak Bruhat order have, on average, “more than their fair share” of fixed points.

Section 5. Acknowledgements

The authors would like to thank Paul Edelman and Dennis Stanton for helpful discussions and references.

References

[BW] A. Björner and M. Wachs, Generalized quotients in Coxeter groups, Trans. AMS 308, 1-37. [Ed]P. H. Edelman, On inversions and cycles in permutations, Eur. J. Comb. 8, 269-279. [DF]J. Désarménien and D. Foata, The signed Eulerian numbers, preprint. [GG]A. Garsia and I. Gessel, Permutation statistics and partitions, Adv. Math. 31, 288-305. [Ge]I. Gessel, A q-analogue of the exponential formula, Disc. Math. 40, 69-80. [GR]I. Gessel and C. Reutenauer, Counting permutations by descent set and cycle structure,

preprint. [Ma]P. A. MacMahon, Combinatory Analysis, Vol .1, Cambridge Univ. Press, Cambridge. [Re]V. Reiner, Descents and one-dimensional characters for classical Weyl groups, to appear in

Disc. Math..

[Sa] B. Sagan, The symmetric group: representations, combinatorial algorithms, and symmetric functions, Wadsworth & Brooks/Cole, Pacific Grove, 1991.