A Plethysm Formula for p_{μ}(\underline{x}) ∘ h_{λ}(\underline{x})

William F. Doran IV

Department of Mathematics California Institute of Technology Pasadena, CA 91125

                        doran@cco.caltech.edu

Submitted: September 10, 1996; Accepted: May 2, 1997

Abstract This paper gives a new formula for the plethysm of power-sum symmetric functions and complete symmetric functions. The form of the main result is that for μ ⊢ b and λ ⊢ a with length t, then

p_{μ}(\underline{x}) ∘ h_{λ}(\underline{x}) = ∑_{T} \underline{ω}^{maj_{μ^{t}} (T)}s_{sh(T)}(\underline{x})

where the sum is over semistandard tableaux of weight λ_{1}^{b}λ_{2}^{b} … λ_{t}^{b} and \underline{ω}^{maj_{μ^{t}} (T)} is a root of unity which depends on μ, t, and T.

1. Introduction

This paper gives a formula for the plethysm of power-sum symmetric functions and complete symmetric functions. In Section 1, some tableaux and symmetric function notation is given. In Section 2, the work of [D] is reviewed. The key result in this section is that for μ ⊢ b,

p_{μ}(\underline{x}) ∘ h_{a}(\underline{x}) = ∑_{T} \underline{ω}^{maj_{μ}(T)}s_{sh(T)}(\underline{x})

where the sum is over all semistandard tableaux T of weight a^{b} and \underline{ω}^{maj_{μ}(T)} is a root of unity which depends on T and μ. In Section 3, a technical result which is needed later is proven. In Section 4, the main result of the paper is proven. The form of this result is that for μ ⊢ b and λ ⊢ a with length t

p_{μ}(\underline{x}) ∘ h_{λ}(\underline{x}) = ∑_{T} \underline{ω}^{maj_{μ^{t}} (T)}s_{sh(T)}(\underline{x})

where the sum is over semistandard tableaux T of weight λ_{1}^{b}λ_{2}^{b} … λ_{t}^{b} and \underline{ω}^{maj_{μ^{t}} (T)} is a root of unity which depends on μ, t, and T.

Keywords: Symmetric Functions, Plethysm

Mathematics Subject Classification: Primary 05E05, Secondary 05E10 1.1 Tableaux

A partition of n is a weakly decreasing sequence λ = (λ_{1} ≥ ⋯ ≥ λ_{l}) of positive integers which sum to n. Either |λ| = n or λ ⊢ n is used to denote that λ is a partition of n. The value l is called the length of λ and is denoted l(λ). Let [λ] = {(i, j): 1 ≤ i ≤ l(λ) and 1 ≤ j ≤ λ_{i}} ⊂ Z^{2}. The set [λ] is the Ferrers diagram of λ and is thought of as a collection of boxes arranged using matrix coordinates.

A composition of n is a sequence α = (α_{1}, …, α_{l}) of positive integers which sum to n. For notational purposes, let a_{1}^{b_{1}}a_{2}^{b_{2}} … a_{l}^{b_{l}} denote the composition

(\underbrace{a_{1}, …, a_{1}}_{b_{1} times}, \underbrace{a_{2}, …, a_{2}}_{b_{2} times}, …, \underbrace{a_{l}, …, a_{l}}_{b_{l} times}).

Also, given a composition α = (α_{1}, …, α_{l}), let α^{t} denote the composition

(α_{1}, …, α_{l}, …, α_{1}, …, α_{l})

where α is repeated t times.

A tableau of shape λ and weight (or content) α = (α_{1}, …, α_{l}) is a filling of the Ferrers diagram of λ with positive integers such that i appears α_{i} times. A tableau is semistandard if its entries are weakly increasing from left to right in each row and strictly increasing down each column. The Kostka number K_{λ,μ} equals the number of semistandard tableaux of shape λ and weight μ. If [ν] ⊆ [λ], let [λ/ν] denote the skew-shape [λ] \ [ν]. A filling of [λ/ν] with α_{i} i’s is a skew-tableau of shape λ/ν and weight α. A semistandard skew-tableau is defined similarly.

1.2 Symmetric Functions

The symmetric function notation in this papers closely follows that of Chapter 1 in Macdonald [M]. Let Λ denote the ring of symmetric functions with rational coefficients in the variables \{x_{1}, x_{2}, … \}. Let s_{λ}(\underline{x}), p_{λ}(\underline{x}), and h_{λ}(\underline{x}) denote the Schur symmetric functions, power-sum symmetric functions, and complete symmetric functions respectively. The ring Λ has a bilinear, symmetric, positive definite scalar product given by ⟨s_{λ}, s_{μ}⟩ = δ_{λ,μ}.

When two Schur symmetric functions are multiplied together and expanded in terms of Schur symmetric functions,

s_{μ}(\underline{x})s_{ν}(\underline{x}) = ∑_{λ⊢|μ|+|ν|} c_{μ,ν}^{λ}s_{λ}(\underline{x}),

the resulting multiplication coefficients c_{μ,ν}^{λ} are nonnegative integers. These coefficients are called Littlewood-Richardson coefficients. See either Section I.9 of [M] or Section 4.9 of [S] for details.

Let f(\underline{x}) and g(\underline{x}) be symmetric functions. The plethysm of f(\underline{x}) and g(\underline{x}) is denoted f(\underline{x}) ∘ g(\underline{x}). A definition of plethysm is given in Section I.8 of [M]. The plethysm results in this paper use a plethysm formula in [D] which is recalled in Section 2. Plethysm has the property of being algebraic in the first coordinate.

Proposition 1.1. For all symmetric functions f_{1}(\underline{x}), f_{2}(\underline{x}), and g(\underline{x}) the following two identities hold.

(a) (f_{1}(\underline{x}) + f_{2}(\underline{x})) ∘ g(\underline{x}) = (f_{1}(\underline{x}) ∘ g(\underline{x})) + (f_{2}(\underline{x}) ∘ g(\underline{x})).

(b) (f_{1}(\underline{x})f_{2}(\underline{x})) ∘ g(\underline{x}) = (f_{1}(\underline{x}) ∘ g(\underline{x}))(f_{2}(\underline{x}) ∘ g(\underline{x})).

While plethysm is not in general symmetric, the following is true.

Proposition 1.2. For any symmetric function f(\underline{x}) and positive integer n, p_{n}(\underline{x})∘ f(\underline{x}) = f(\underline{x}) ∘ p_{n}(\underline{x}).

Proofs of these propositions are given in Section I.8 of [M].

2. Formula for p_{μ}(\underline{x}) ∘ h_{a}(\underline{x})

This section reviews some results in [D]. Definition: Given a semistandard tableau or semistandard skew-tableau T, i is a descent with multiplicity k if there exists k disjoint pairs {(x_{1}, y_{1}), …, (x_{k}, y_{k})} of boxes in the Ferrers diagram of T such that the entry in each x_{j} is i, the entry in each y_{j} is i + 1, y_{j} is in a lower row than x_{j} for all j, and there does not exist a set of k + 1 pairs of boxes which satisfy these conditions. Let m_{i}(T) denote the multiplicity of i as a descent in T. Finally, the Major index of T, denoted maj(T), is sum of the descents with multiplicity. That is, maj(T) = ∑ i m_{i}(T).

Given a semistandard tableau T whose weight has length b and a composition α = (α_{1}, …, α_{l}) of b, decompose T into a sequence of semistandard skew-tableaux (T_{1}, …, T_{l}) by letting the shape of T_{1} be those positions in T which contain 1 through α_{1}, T_{2} be those positions in T which contain α_{1} + 1 through α_{2}, and so on. The actual entries in T_{i} are the entries of T but reindexed so they run from 1 to α_{i}. Definition: Following the notation of the previous paragraph, define the root of unity

\underline{ω}^{maj_{α}(T)} = ∏_{i=1}^{l} ω_{α_{i}}^{maj(T_{i})}

where the ω_{k} = e^{2πi/k}.

Example 1: Consider

T = 1 1 1 2 3 2 2 2 3 4 3 4 5 .

T is a semistandard tableau of shape (5, 5, 3) and weight (3, 4, 3, 2, 1). The descent multiplicities are m_{1}(T) = 3, m_{2}(T) = 2, m_{3}(T) = 2, m_{4}(T) = 1. Its Major index is 17. Take α = (2, 3). Then the decomposition of T is

T_{1} = 1 1 1 2 2 2 2  and  T_{2} = 1 1 2 1 2 3

The Major indices are maj(T_{1}) = 3 and maj(T_{2}) = 4. Finally, \underline{ω}^{maj_{α}(T)} = ω_{2}^{3}ω_{3}^{4} = −ω_{3}.

The main result of [D] is the following. Theorem 2.1. Let μ ⊢ b, then

p_{μ}(\underline{x}) ∘ h_{a}(\underline{x}) = ∑_{{SST T \atop wt(T)=a^{b}}} \underline{ω}^{maj_{μ}(T)} s_{sh(T)}(\underline{x}).

Here is a quick application of this formula. It is a generalization of Example 9(b) in Section I.8 of [M]. Proposition 2.2. If b is prime power p^{n}, then ⟨p_{b}(\underline{x}) ∘ h_{a}(\underline{x}), s_{λ}(\underline{x})⟩ ≡ K_{λ,a^{b}} (mod p). Proof: By Theorem 2.1, ⟨p_{b}(\underline{x}) ∘ h_{a}(\underline{x}), s_{λ}(\underline{x})⟩ is a sum of K_{λ,a^{b}} many terms where each term is a p^{n}-th root of unity. □

One last result needed (Theorem 2.1 of [D]). This concerns an algorithm for selecting the (x_{j}, y_{j}) pairs which contribute to the statistic m_{i}(T) for a given T. Here is the algorithm.

Select an ordering σ of the α many boxes which contain an i.

Set j = 0.

For k = 1 to α Do Let x = σ(k). If there are any boxes below x which contain i+1 and have not already been selected as an y_{j} Then Increment j by 1. Let x_{j} = x. Let y_{j} be the right-most of these unselected boxes containing i + 1.

End If End Do

Algorithm 1.

This algorithm clearly works when the ordering σ is to consider the i’s from right to left in T. The surprising result is that this algorithm works for any choice of σ. Theorem 2.3. The above algorithm for determining m_{i}(T) works for all choices of the ordering σ of the i’s. It should be noted that the choice of pairs (x_{j}, y_{j}) may differ based on the choice of σ, but the number of pairs does not differ.

3. A technical result

Definition: Given a semistandard skew-tableau T, define J(T) to be the semistandard tableau obtained by the following algorithm, called Jeu de Taquin.

While T has skew-shape Do Let λ/μ be the shape of T. Let ⋆ be any outer corner of μ. While ⋆ is not an outer corner of λ Do

If value of T to right of ⋆ is greater than or equal to the value below ⋆

Swap ⋆ with the value below it. Else

Swap ⋆ with the value to its right. End If End Do

End Do

Algorithm 2.

Example 2: Let

T = 1 2 3 1 2 2 1 2 3 .

One iteration of the inner loop is

\begin{aligned}& & ⋆ & 1 & 2 & 3 \\ & 1 & 2 & 2 \\ 1 & 2 & 3 \end{aligned} ,  \begin{aligned}& & 1 & ⋆ & 2 & 3 \\ & 1 & 2 & 2 \\ 1 & 2 & 3 \end{aligned} ,  \begin{aligned}& & 1 & 2 & 2 & 3 \\ & 1 & 2 & ⋆ \\ 1 & 2 & 3 \end{aligned} .

Here are the tableaux after each application of the inner loop along with the choice of ⋆ for the next iteration:

\begin{aligned}& ⋆ & 1 & 2 & 2 & 3 \\ & 1 & 2 \\ 1 & 2 & 3 \end{aligned} ,  \begin{aligned}& 1 & 1 & 2 & 2 & 3 \\ ⋆ & 2 & 2 \\ 1 & 3 \end{aligned} ,

\begin{matrix}⋆ & 1 & 1 & 2 & 2 & 3 \\ 1 & 2 & 2 \\ 3 \end{matrix} ,  1 1 1 2 2 3 2 2 3 .

It is clear that J(T) is semistandard and that wt(J(T)) = wt(T). However it is not clear from the definition that this operation is well-defined. The choices for the initial position of ⋆ in each iteration might effect the outcome of the algorithm. But, it has been shown (see Section 3.9 of [S] for a proof) that for all choices of the ⋆’s, the resulting J(T) is the same. The next result gives an important property of the Jeu de Taquin operation. A proof is given in the proof of Theorem 4.9.4 of [S].

Lemma 3.1. Given a semistandard tableau Q of shape η, the number of semistandard tableaux T of shape λ/ν such that J(T) = Q equals the Littlewood-Richardson coefficient c_{ν,η}^{λ}.

Another fact about Jeu-de-Taquin is that preserves descent multiplicities.

Lemma 3.2. Let T be a semistandard tableau whose weight has length b and let α be a composition of b. Then m_{i}(T) = m_{i}(J(T)) for all i.

Proof: Suppose T ↦ T′ in one application of the inner loop of the Jeu de Taquin algorithm. We want to show that m_{i}(T) = m_{i}(T′) for all i. If the swap of this kind

\begin{matrix}⋆ & j \\ k \end{matrix} → \begin{matrix}j & ⋆ \\ k \end{matrix} ,

where k > j, then since no element has changed which row it occupies, it is clear that all m_{i}(T) are unchanged. However, if the swap is of the other kind

\begin{matrix}⋆ & j \\ k \end{matrix} → \begin{matrix}k & j \\ ⋆ \end{matrix}

where k ≤ j, then there are two possible problems: some (k, k + 1) pairs may have been created, or some (k − 1, k) pairs may have been destroyed. Either of these “problems” might alter the value of m_{k}(T) or m_{k−1}(T), respectively.

First, we show that any new (k, k + 1) pairs do not effect the value of m_{k}(T). Let r be the row containing ⋆ in T. So, the possible new (k, k + 1) pairs in T′ are from the k which just moved into row r and the k + 1’s in row r + 1. Since T and T′ are semistandard, each of these k + 1 must have a k directly above them in both T and T′. The key is apply Theorem 2.3 with the properly chosen ordering σ of the k’s. The proper choice is to place the k’s in row r which have a k + 1 directly below them (say from right to left) at the beginning of σ, then fill in all the other k’s (again say from right to left). Now apply the algorithm to determine m_{k}(T) and m_{k}(T′). In both cases, the first group of k’s in row r with a k + 1 below them get matched with the k + 1 directly below them. Thus, all of the new (k, k + 1) pairs in T′ do effect the outcome of the algorithm since all of the k + 1’s get selected before the algorithm can consider using one of these pairs. Therefore, m_{k}(T) = m_{k}(T′).

The proof that m_{k−1}(T) = m_{k−1}(T′) is similar. The (k − 1, k) pairs that get destroyed in T′ are from the k which moved into row r and the k − 1’s in row r. Since T is semistandard, each of the k − 1’s in row r must have a k directly below them in both T and T′. Order the k − 1’s by placing the k − 1’s in row r first and other k − 1’s later. The algorithm for determining m_{k−1}(T) and m_{k−1}(T′) give the same result. □

Finally, these two lemmas are put together to prove a key technical result used in the next section.

Theorem 3.3. Let |λ/ν| = n, β be a composition of n with l parts, and α be a composition of l. Then

∑_{SSST T sh(T)=λ/ν,wt(T)=β} \underline{ω}^{maj_{α}(T)} = ∑_{η⊢n} (c_{ν,η}^{λ} ∑_{{SST T \atop sh(T)=η,wt(T)=β}} \underline{ω}^{maj_{α}(T)}) .

Proof: By Lemma 3.1, Jeu-de-Taquin provides the bijection between the two sides. By Lemma 3.2, \underline{ω}^{maj_{α}(T)} is preserved under this bijection. □

4. Formula for p_{μ}(\underline{x}) ∘ h_{λ}(\underline{x})

Theorem 4.1. Given μ ⊢ b and λ ⊢ a where the length of μ is l and the length of λ is t, let α = μ^{t} and β = λ_{1}^{b}λ_{2}^{b} … λ_{t}^{b}. So, β is a composition of ab with tb parts, and α is a composition of tb. Then

p_{μ}(\underline{x}) ∘ h_{λ}(\underline{x}) = ∑_{{SST T \atop wt(T)=β}} \underline{ω}^{maj_{α}(T)}s_{sh(T)}(\underline{x}).

Proof: Proof by induction on t. The case t = 1 is Theorem 2.1. So assume the theorem is valid when μ has length less than t. Let λ^{∗} = (λ_{1}, …, λ_{t−1}). Now a computation gives the desired result. Explanations of the steps are given after the computation.

p_{μ}(\underline{x})∘h_{λ}(\underline{x}) = ∏_{i} p_{μ_{i}}(\underline{x}) ∘ h_{λ}(\underline{x})  (1)

= ∏_{i} h_{λ}(\underline{x}) ∘ p_{μ_{i}}(\underline{x})  (2)
= ∏_{i}(h_{λ^{∗}}(\underline{x}) ∘ p_{μ_{i}}(\underline{x})) (h_{λ_{t}}(\underline{x}) ∘ p_{μ_{i}}(\underline{x}))  (3)
= ∏_{i}(p_{μ_{i}}(\underline{x}) ∘ h_{λ^{∗}}(\underline{x})) ∏_{i}(p_{μ_{i}}(\underline{x}) ∘ h_{λ_{t}}(\underline{x}))  (4)

= ( ∑_{{SST T_{1} \atop wt(T_{1})=λ_{1}^{b}...λ_{t−1}^{b}}} \underline{ω}^{maj_{μ^{t−1}} (T_{1})}s_{sh(T_{1})}(\underline{x}))

( ∑_{{SST T_{2} \atop wt(T_{2})=λ_{t}^{b}}} \underline{ω}^{maj_{μ}(T_{2})}s_{sh(T_{2})}(\underline{x}))  (5)

= ∑_{ν⊢ab} s_{ν}(\underline{x}) [ ∑_{{SST T_{1} \atop wt(T_{1})=λ_{1}^{b}...λ_{t−1}^{b}}} (\underline{ω}^{maj_{μ^{t−1}} (T_{1})}

(c_{sh(T_{1}),η}^{ν} ∑_{{SST T_{2} \atop sh(T_{2})=η,wt(T_{2})=λ_{t}^{b}}} \underline{ω}^{maj_{μ}(T_{2})}))]  (6)

= ∑_{ν⊢ab} s_{ν}(\underline{x}) [ ∑_{{SST T_{1} \atop wt(T_{1})=λ_{1}^{b}...λ_{t−1}^{b}}} (\underline{ω}^{maj_{μ^{t−1}} (T_{1})}

∑_{SST T_{2} sh(T_{2})=ν/sh(T_{1}),wt(T_{2})=λ_{t}^{b}} \underline{ω}^{maj_{μ}(T_{2})})]  (7)

= ∑_{ν⊢ab} s_{ν}(\underline{x}) [  ∑_{{SST T_{3} \atop sh(T_{3})=ν,wt(T_{3})=β}} \underline{ω}^{maj_{α}(T_{3})}]  (8)

(1) Apply Proposition 1.1(b). (2) Apply Proposition 1.2. (3) Apply Proposition 1.1(b). (4) Apply Proposition 1.2. (5) Apply the induction hypothesis. (6)

Multiply the Schur symmetric functions and collect the terms which contribute to s_{ν}(\underline{x}). (7) Apply Theorem 3.3. (8) Combine T_{1} and T_{2} to form T_{3} by first reindexing the values in T_{2} to run from b(λ_{1}+⋯+λ_{t−1})+1 to b(λ_{1}+⋯+λ_{t}) and then place T_{1} inside the reindexed T_{2}. Notice that under this bijection \underline{ω}^{maj_{μ^{t−1}} (T_{1})} \underline{ω}^{maj_{μ}(T_{2})} = \underline{ω}^{maj_{α}(T_{3})}. □

Example 3: Let μ = (2) and λ = (2, 1). Then α = (2, 2) and β = (2, 2, 1, 1). The semistandard tableaux T with weight β and \underline{ω}^{maj_{α}(T)} are given in Table 1. So, p_{(2)}(\underline{x}) ∘ h_{(2,1)}(\underline{x}) = s_{(6)}(\underline{x}) − s_{(5,1)}(\underline{x}) + 2s_{(4,2)}(\underline{x}) − 2s_{(3,3)}(\underline{x}) − s_{(4,1,1)}(\underline{x}) + s_{(2,2,2)}(\underline{x}) + s_{(3,1,1,1)}(\underline{x}) − s_{(2,2,1,1)}(\underline{x}).

References

[D] W. Doran, A New plethysm Formula for Symmetric Functions, J. of Alg. Combin., submitted.

[M] I. Macdonald, “Symmetric Functions and Hall Polynomials,” 2nd ed., Clarendon Press, Oxford, 1995.

[S] B. Sagan, “The Symmetric Group: Representations, Combinatorial Algorithms, & Symmetric Functions,” Wadsworth & Brooks/Cole, Pacific Grove, CA, 1991.

\begin{matrix}T & \underline{ω}^{maj_{(2,2)}(T)} & T & \underline{ω}^{maj_{(2,2)}(T)} \\ 1 1 2 2 3 4 & 1 & 1 1 2 2 3 4 & −1 \\ 1 1 2 2 4 3 & 1 & 1 1 2 4 2 3 & −1 \\ 1 1 2 2 3 4 & −1 & 1 1 2 3 2 4 & 1 \\ 1 1 2 3 4 2 & −1 & 1 1 2 2 3 4 & 1 \\ 1 1 2 2 3 4 & 1 & 1 1 2 2 4 3 & −1 \\ 1 1 2 4 2 3 & −1 & 1 1 4 2 2 3 & 1 \\ 1 1 2 3 2 4 & 1 & 1 1 3 2 2 4 & −1 \\ 1 1 3 4 2 2 & 1 & 1 1 2 2 3 4 & 1 \\ 1 1 2 2 3 4 & 1 & 1 1 2 2 3 4 & 1 \\ 1 1 3 2 2 4 & 1 & 1 1 2 2 3 4 & −1 \end{matrix}

Table 1: Semistandard Tableaux of Weight (2, 2, 1, 1)