LITTLEWOOD-RICHARDSON WITHOUT ALGORITHMICALLY DEFINED BIJECTIONS

BY

Peter HOFFMANN

John Stembridge [St] has recently solved the important problem of finding a “Littlewood-Richardson rule” for Q-functions. His proof is very natural combinatorially, but lengthy, if all the background is included. It uses extensive material from Worley’s thesis [W] and Sagan’s similar theory of shifted tableaux [Sa]. To include this result in a forthcoming book (coauthored by John Humphreys), and in order to keep the volume of material under control, a second proof was sought for it and for an analogous product theorem in the ℤ/2 × ℕ-graded algebra of projective representations of A_{n} and S_{n} [H, HH].

Given below is a similar, less tableau-theoretic, proof of the usual Littlewood-Richardson rule for Schur functions. The best of the earlier proofs have considerable combinatorial explanatory power. The proof below explains only why the product of two Schur functions is what it is.

More precisely, one might say that an algorithmically defined bijection (a.d.b.) A_{α} → B_{α}, between sets indexed by a parameter α which runs over an infinite set, is a definition in which the image of an element in A_{α} is determined using successive applications of a least one algorithm, and where, to produce that image, the number of needed applications of the algorithm is unbounded as we vary the element over A_{α} for all α. Earlier proofs apparently use a.d.b.’s; the proof below does not. This remark is included to point readers, who attempt to compare this with earlier proofs, in the correct direction.

Our notation will be largely from [Ma], with the ring Λ of symmetric functions having the inner product ⟨ , ⟩ for which the Schur functions s_{λ} give an orthonormal basis, as λ ranges over all partitions. For f in Λ, the operator f^{⊥} on Λ is defined by ⟨f^{⊥}(g), h⟩ = ⟨g, fh⟩. The Schur function can be given by

(1)  s_{n_{1},...,n_{ℓ}} = B_{n_{1}} … B_{n_{ℓ}}

where B_{n} is the operator Σ_{i}(−1)^{i}h_{n+i}e_{i}^{⊥} (see [Z; p. 69]). A proof of (1), which is more basic than quoting the Jacobi-Trudi identity, can be had by defining elements s_{λ}^{B} by the right hand side of (1). Obviously

(2)  s_{λ}^{B} − h_{λ} ∈ Span{h_{μ} : μ < λ}.

By an induction on length, one gets

h_{a+i}^{⊥}(s_{a,b,...}^{B}) = \{ \begin{matrix}s_{b,...}^{B}, & if i = 0; \\ 0, & if i > 0. \end{matrix}

Thus, for μ ≤ λ (partitioning the same integer),

⟨h_{μ}, s_{λ}^{B}⟩ = ⋯ h_{μ_{2}}^{⊥}h_{μ_{1}}^{⊥}(s_{λ}^{B}) = δ_{μ,λ}.

Using (2), this yields, for all ν and λ,

(3)  ⟨s_{ν}^{B}, s_{λ}^{B}⟩ = δ_{ν,λ}.

Thus s_{λ}^{B} = s_{λ} by (2) and (3).

Equation (1) may be used to extend the definition of s_{n_{1},...,n_{ℓ}} to any sequence {n_{i}} of integers. These elements coincide with Murnaghan’s “non-standard symbols” [Mu; p. 761], and with the t = 0 specialization of the extension of Hall-Littlewood polynomials [Ma; p. 109]. Each is either zero or ±s_{λ} for a partition λ, by the identity

(4)  s_{...,c,d,...} = −s_{...,d−1,c+1,...}.

A natural proof of (4) using the B-operators is to show by straightforward calculation that

(5)  B_{c}B_{d} = −B_{d−1}B_{c+1}.

The elements s_{...,c,c+1,...} and s_{n_{1},...,n_{ℓ}} when n_{ℓ} < 0, are both zero.

We shall use λ̃ for the conjugate of a partition λ, and also f̃ for the image of f under the involution of Λ which interchanges h_{n} and e_{n}. Thus for λ = (n_{1}, …, n_{ℓ}) we have

sλ̃ = s̃_{λ} = B̃_{n_{1}} … B̃_{n_{ℓ}},

where B̃_{n} is the operator ∑_{i}(−1)^{i}e_{n+i}h_{i}^{⊥}. Equation (5) holds also for the operators B̃_{n}.

Definition. For a partition λ and a sequence (t_{1}, …, t_{k}) of non-negative integers, let MUR(λ; t_{1}, …, t_{k}) be the set of all matrices of 0’s and 1’s whose row sums are the parts of λ, whose column sums are t_{1}, …, t_{k}, and such that

∑ rightmost j entries of row i ≥ ∑ rightmost j entries of row (i + 1)

for 0 < j ≤ k and 1 ≤ i < length(λ).

Proposition 1. For any partition λ and sequences m_{1}, …, m_{k}, we have

s̃_{λ}^{⊥}(s_{m_{1},...,m_{k}}) = ∑_{t_{1},...,t_{k}} # MUR(λ; t_{1}, …, t_{k})s_{m_{1}−t_{1},...,m_{k}−t_{k}}.

Proof. The equations

e_{i}^{⊥}(h_{n}) = \{ \begin{matrix}h_{n−i}, & if i = 0, 1; \\ 0, & if i > 1; \end{matrix}
e_{i}^{⊥}(xy) = ∑_{j} e_{j}^{⊥}(x)e_{i−j}^{⊥}(y);

and

∑_{i}(−1)^{i}e_{i}h_{k−i} = δ_{0,k}

immediately give

[h_{i}^{⊥}(y)]^{⊥}(u) = ∑_{ℓ}(−1)^{ℓ}e_{ℓ}y^{⊥}(h_{i−ℓ}u).

This follows by induction on i, applying ⟨ , u⟩, for arbitrary u, to both sides. It leads immediately to

(6)  [B̃_{n}(y)]^{⊥}(z) = ∑_{p,q}(−1)^{p}e_{q}y^{⊥}[h_{p}e_{n+p+q}^{⊥}(z)].

Now proceed by induction on ℓ to prove

(7)  s̃_{n_{1},...,n_{ℓ}}^{⊥}(h_{m}x) = ∑_{δ_{i}=0,1} h_{m−Σδ_{i}}s̃_{n_{1}−δ_{1},...,n_{ℓ}−δ_{ℓ}}^{⊥}(x).

This is trivial for ℓ = 1. The inductive step is

s̃_{n_{1},...,n_{ℓ}}^{⊥}(h_{m}x) = [B̃_{n_{1}}(s̃_{n_{2},...,n_{ℓ}})]^{⊥}(h_{m}x)

= ∑_{p,q}(−1)^{p}e_{q}s̃_{n_{2},...,n_{ℓ}}^{⊥}[h_{p}e_{n_{1}+p+q}^{⊥}(h_{m}x)]

= ∑_{p,q}(−1)^{p}e_{q}s̃_{n_{2},...,n_{ℓ}}^{⊥}[h_{p}h_{m}e_{n_{1}+p+q}^{⊥}(x) + h_{p}h_{m−1}e_{n_{1}+p+q−1}^{⊥}(x)]

= ∑_{p,q}(−1)^{p}e_{q}_{∑_{δ_{i}=0,1} ; i≥2}{h_{m−(δ_{2}+···+δ_{q})}s̃_{n_{2}−δ_{2},...,n_{ℓ}−δ_{ℓ}}^{⊥}(h_{p}e_{n_{1}+p+q}^{⊥}(x))

+ h_{m−1−(δ_{2}+···+δ_{q})}s̃_{n_{2}−δ_{2},...,n_{ℓ}−δ_{ℓ}}^{⊥}(h_{p}e_{n_{1}+p+q}^{⊥}(x))}

= ∑_{δ_{2},...,δ_{ℓ}}{h_{m−(δ_{2}+···+δ_{q})}[B̃_{n_{1}}(s̃_{n_{2}+δ_{2},...,n_{ℓ}−δ_{ℓ}})]^{⊥}(x)

+ h_{m−1(1+δ_{2}+···+δ_{q})}[B̃_{n_{1}−1}(s̃_{n_{2}−δ_{2},...,n_{ℓ}−δ_{ℓ}})]^{⊥}(x)},

as required.

Finally, we can prove the proposition by induction on k. For k = 1, take x = 1 in (7). For the inductive step, with λ = (n_{1}, …, n_{ℓ}),

s̃_{λ}^{⊥}(s_{m_{1},...,m_{k}}) = s̃_{λ}^{⊥}( ∑_{i}(−1)^{i}h_{m_{1}+i}e_{i}^{⊥}(s_{m_{2},...,m_{k}}))

= ∑_{i}(−1)^{1} ∑_{δ_{1},...,δ_{ℓ}} h_{m_{1}+i−(δ_{1}+···+δ_{ℓ})}s̃_{n_{1}−δ_{1},...,n_{ℓ}−δ_{ℓ}}^{⊥}e_{i}^{⊥}(s_{m_{2},...,m_{k}})

= ∑_{\begin{matrix}δ_{1},...,δ_{ℓ} \\ n_{p}−δ_{p}≥n_{p+1}−δ_{p+1} \end{matrix}} B_{m_{1}−(δ_{1}+···+δ_{ℓ})} ∑ s_{m_{2}−t_{2},...,m_{k}−t_{k}},

where the second summation is over all E′ in MUR(n_{1} − δ, …, n_{ℓ} − δ_{ℓ}; t_{2}, …, t_{k}) for all t_{2}, …, t_{k}. The restriction n_{p} − δ_{p} ≥ n_{p+1} − δ_{p+1} for all p follows by the remark after (5). Now letting t_{1} = ∑ δ_{i} and

E = ( \begin{matrix}δ_{1} \\ ⋮ & E′ \\ δ_{ℓ} \end{matrix} ) ,

the sum becomes ∑_{t_{1},...,t_{k}} ∑_{E∈MUR(λ;t_{1},...,t_{k})} s_{m_{1}−t_{1},...,m_{k}−t_{k}}, as required.

Definition. Let LAT(λ; t_{1}, …, t_{k}) be the set of sentences S = (w_{1}, …, w_{k}), where w_{i} is a weakly decreasing sequence of positive integers of length t_{i}, such that the concatenated word w_{1}w_{2} … w_{k} satisfies the lattice permutation condition of the Littlewood-Richardson rule [Ma; p. 68] and has content (or weight) λ. Define

LAT_{k}(λ) = ⋃_{t_{1},...,t_{k}} LAT(λ; t_{1}, …, t_{k}).

Proposition 2. # MUR(λ; t_{1}, …, t_{k}) = # LAT(λ̃; t_{1}, …, t_{k}).

Proof. Let TAB(λ; t_{1}, …, t_{k}) be the set of (column strict) tableaux of shape λ and content (t_{1}, …, t_{k}). We have

# MUR(λ; t_{1}, …, t_{k}) {i) \atop =} #TAB(λ̃; t_{k}, …, t_{1}) {ii) \atop =} #TAB(λ̃; t_{1}, …, t_{k})

{iii) \atop =}# MUR(λ; t_{k}, …, t_{1}){iv) \atop =}# LAT(λ̃; t_{1}, …, t_{k}),

as required. In i) and iii), a bijection is defined by having an i in the jth column of a tableau if and only if there is a 1 in place (j, k −i+1) of the corresponding matrix. In iv), a bijection is defined by replacing the 1′s in the ith row of a matrix by 1, 2, …, n_{i} (= ith of part λ) from right to left, and then reading the columns downwards (omitting zeros) to obtain the words of sentence (the first word from rightmost column, etc.). A bijection for ii) exists, since the number of tableaux of given shape does not vary if we permute the content sequence (that is, the Schur function is symmetric).

Remark. The bijections for i), iii), and iv) are entirely elementary. No a.d.b’s are used there, nor in the proof [Ma; (5.12)] that s_{λ} has coefficients # TAB(λ; ).

Definition. Given S = (w_{1}, …, w_{k}) ∈ LAT_{k}(λ) and a partition (m_{1}, …, m_{k}), we say that, with respect to (m_{1}, …, m_{k}):

i) S has a bottom line violation iff length(w_{k}) > m_{k}; ii) S has a (d + 1, i)-shape violation (for d ≥ 0 and 1 ≤ i < k) iff

m_{i+1} − length(w_{i+1}) = m_{i} − length(w_{1}) + d + 1;

iii) S has a (d − 1, i)-column violation (for d ≥ 1 and 1 ≤ i < k) iff both

m_{1} − length(w_{i}) = m_{i+1} − length(w_{i+1}) + d − 1

and when words w_{i}, w_{i+1} are inserted from the right on lines i, i + 1 of the Young diagram of (m_{1}, …, m_{k}), there exists a vertical pair [ \begin{matrix}x \\ y \end{matrix} ] with x ≥ y.

Remark. When the words of S are all inserted on their respective lines as in iii), one obtains a skew tableau iff there are no violations. In this case, we say that S is (m_{1}, …, m_{k})-innocent. Since s_{μ/λ} = s_{λ}^{⊥}(s_{μ}), the following is therefore exactly the usual statement of the Littlewood-Richardson rule.

Theorem. For all partitions λ and (m_{1}, …, m_{k}),

s̃_{λ}^{⊥}(s_{m_{1},...,m_{k}}) = _{∑_{S∈LAT_{k}(λ̃)} S is (m_{1},...,m_{k})−innocent}s_{m_{1}−length(w_{1}),...,m_{k}−length(w_{k})}.

Proof. The two previous propositions prove the analogous equation where S ranges over all of LAT_{k}(λ̃). We must now prove that, in this sum, the terms coming from S which have a violation add up to zero. For such S choose the largest i for which there is a violation. If it is a bottom line violation or a (1, i)-shape violation, the term itself is zero, by the remark after (5). The remaining such terms will cancel in pairs as follows, using (4). Fix d ≥ 1, 1 ≤ i < k and all the words of S except w_{i} and w_{i+1}. Let A be the content remaining to be used for w_{i}w_{i+1}. Let B be the submultiset of A of the form {j_{1}, j_{1} + 1, …, j_{p}, j_{p} + 1} for which {j_{1}, …, j_{p}} must occur in w_{i}, and {j_{1} + 1, …, j_{p} + 1} in w_{i+1} in order that the lattice permutation condition should hold. We need bijections from the set V (A, B, q, r, d) of S having a (d−1, i)-column violation to the sets M(A, B, q, r, d) having a (d+1, i)-shape violation; that is, bijections between sets of two row integer arrays

V (A, B, q, r, d)  M(A, B, q, r, d)^{…  . . . . . .  … ^{d−1} ^{r+1} ^{q}  …  . . . . . .  … ^{d+1} ^{r} ^{q}}

with weakly increasing rows, with at least one [ \begin{matrix}x \\ y \end{matrix} ] with x ≥ y in V, and with content A, where B is inserted as mentioned above. Note that fixing r and q fixes the length of w_{i} and w_{i+1}, but differently for V and M. When p = 0, so that B is empty, a bijection, shown to me by Ian Goulden, is given below, together with its inverse:

∘ ∘ ∘ ∘ ∘ ∘ ∘ ∘ y x ∘ ∘ ∘ ∘ ∘ ∘ ↑ rightmost for which x ≥ y  ⟷ ∘ ∘ ∘ ∘ ∘ ∘ ∘ ∘ v u ∘ ∘ ∘ ∘ ∘ ∘ ↑rightmost for which u ≥ v ↑ here if no such (u, v)

The general case can be reduced to the case p = 0 as follows. If p > 0, adding and removing {j_{p}, j_{p} +1} clearly gives mutually inverse maps between M(A, B, q, r, d) and M(A′, B′, q, r − 1, d) where

A′ = A \{j_{p}, j_{p} + 1}  and  B′ = B \{j_{p}, j_{p} + 1}.

The same holds for the sets V (A, B, q, r, d) and V (A′, B′, q, r − 1, d), noting that the existence of a pair [ \begin{matrix}x \\ y \end{matrix} ] with x ≥ y persists after the addition or removal. This completes the proof.

References

[H] HOFFMAN (P.), A Bernstein-Type Formula for Projective Representations of S_{n} and A_{n}, Adv. Math. 74 (1989), 135–143.

[HH] HOFFMAN (Peter) and HUMPHREYS (John), Hopf Algebras and Projective Representations of G ≀ S_{n} and G ≀ A_{n}, Can. J. Math. 38 (1986), 1380–1458.

[Ma] MACDONALD (I.G.), Symmetric Functions and Hall Polynomials, Oxford Univ. Press, Oxford, 1979.

[Mu] MURNAGHAN (F.D.), The Analysis of the Kronecker Product of Irreducible Representations of the Symmetric Group, Amer. J. of Math. 60 (1938), 761–784.

[Sa] SAGAN (B.E.), Shifted Tableaux, Schur Q-Functions, and a Conjecture of R. Stanley, J. Comb. Theory, Ser. A 45 (1987), 62–103.

[St] STEMBRIDGE (J.R.), Shifted Tableaux and the Projective Representations of Symmetric Groups, Adv. Math. 74 (1989), 87–134.

[W] WORLEY (D.R.), A Theory of Shifted Tableaux, Ph.D. thesis M.I.T, 1984.

[Z] ZELEVINSKI (Andrey V.), Representations of Finite Classical Groups, Lecture Notes in Math., vol. 869, Springer-Verlag, Berlin, 1981.