A NOTE ON THE SYMMETRIC POWERS OF THE STANDARD REPRESENTATION OF S_{n}

David Savitt^{1} Department of Mathematics, Harvard University Cambridge, MA 02138, USA

                          dsavitt@math.harvard.edu

Richard P. Stanley^{2} Department of Mathematics, Massachusetts Institute of Technology Cambridge, MA 02139, USA

                             rstan@math.mit.edu

Submitted: January 7, 2000; Accepted: February 12, 2000

Abstract

In this paper, we prove that the dimension of the space spanned by the characters of the symmetric powers of the standard n-dimensional representation of S_{n} is asymptotic to n^{2}/2. This is proved by using generating functions to obtain formulas for upper and lower bounds, both asymptotic to n^{2}/2, for this dimension. In particular, for n ≥ 7, these characters do not span the full space of class functions on S_{n}.

Notation

Let P (n) denote the number of (unordered) partitions of n into positive integers, and let ϕ denote the Euler totient function. Let V be the standard n-dimensional representation of S_{n}, so that V = ℂe_{1} ⊕ ⋯ ⊕ ℂe_{n} with σ(e_{i}) = e_{σi} for σ ∈ S_{n}. Let S^{N}V denote the N^{th} symmetric power of V, and let χ_{N} : S_{n} → ℤ denote its character. Finally, let D(n) denote the dimension of the space of class functions on S_{n} spanned by all the χ_{N}, N ≥ 0.

1. Preliminaries

Our aim in this paper is to investigate the numbers D(n). It is a fundamental problem of invariant theory to decompose the character of the symmetric powers of an irreducible representation of a finite group (or more generally a reductive group). A special case with a nice theory is the reflection representation of a finite Coxeter group. This is essentially what we are looking at. (The defining representation of S_{n} consists of the direct sum of the reflection representation and the trivial representation. This trivial summand has no significant effect on the theory.) In this context it seems natural to ask: what is the dimension of the space spanned by the symmetric powers? Moreover, decomposing the symmetric powers of the character of an irreducible representation of S_{n} is an example of the operation of inner plethysm [1, Exer. 7.74], so we are also obtaining some new information related to this operation.

1Supported by an NSERC PGS-B fellowship

2Partially supported by NSF grant DMS-9500714

We begin with:

Lemma 1.1. Let λ = (λ_{1}, …, λ_{k}) be a partition of n (which we denote by λ ⊢ n), and suppose σ ∈ S_{n} is a λ-cycle. Then χ_{N}(σ) is equal to the number of solutions (x_{1}, …, x_{k}) in nonnegative integers to the equation λ_{1}x_{1} + ⋯ + λ_{k}x_{k} = N.

Proof. Suppose without loss of generality that σ = (1 2 ⋯ λ_{1})(λ_{1} + 1 ⋯ λ_{1} + λ_{2}) ⋯ (λ_{1} + ⋯ + λ_{k−1} + 1 ⋯ n). Consider a basis vector e_{1}^{⊗c_{1}} ⊗ ⋯ ⊗ e_{n}^{⊗c_{n}} of S^{N}V, so that c_{1} + ⋯ + c_{n} = N with each c_{i} ≥ 0. This vector is fixed by σ if and only if c_{1} = ⋯ = c_{λ_{1}}, c_{λ_{1}+1} = ⋯ = c_{λ_{1}+λ_{2}} and so on. Since χ_{N}(σ) equals the number of basis vectors fixed by σ, the lemma follows.

It seems difficult to work directly with the χ_{N}’s; fortunately, it is not too hard to restate the problem in more concrete terms. Given a partition λ = (λ_{1}, …, λ_{k}) of n, define

f_{λ}(q) = \frac{1}{(1 − q^{λ_{1}}) ⋯ (1 − q^{λ_{k}})}. (1)

Next, define F_{n} ⊂ ℂ[[q]] to be the complex vector space spanned by all of these f_{λ}(q)’s. We have:

Proposition 1.2. dim F_{n} = D(n).

Proof. Consider the table of the characters χ_{N}; we are interested in the dimension of the row-span of this table. Since the dimension of the row-span of a matrix is equal to the dimension of its column-span, we can equally well study the dimension of the space spanned by the columns of the table. By the preceeding lemma, the N^{th} entry of the column corresponding to the λ-cycles is equal to the number of nonnegative integer solutions to the equation λ_{1}x_{1} + ⋯ + λ_{k}x_{k} = N. Consequently, one easily verifies that f_{λ}(q) is the generating function for the entries of the column corresponding to the λ-cycles. The dimension of the column-span of our table is therefore equal to dim F_{n}, and the proposition is proved.

2. Upper Bounds on D(n)

Our basic strategy for computing upper bounds for dim F_{n} is to put all the generating functions f_{λ}(q) over a common denominator; then the dimension of their span is bounded above by 1 plus the degree of their numerators. For example, one can see without much difficulty that (1 − q)(1 − q^{2}) ⋯ (1 − q^{n}) is the least common multiple of the denominators of the f_{λ}(q)’s. Putting all of the f_{λ}(q)’s over this common denominator, their numerators then have degree n(n + 1)/2 − n, which proves

D(n) ≤ \frac{n(n − 1)}{2} + 1. (2)

By modifying this strategy carefully, it is possible to find a somewhat better bound. Observe that the denominator of each of our f_{λ}’s is (up to sign change) a product of cyclotomic polynomials. In fact, the power of the j^{th} cyclotomic polynomial Φ_{j}(q) dividing the denominator of f_{λ}(q) is precisely equal to the number of λ_{i}’s which are divisible by j. It follows that Φ_{j}(q) divides the denominator of f_{λ}(q) at most ⌊\frac{n}{j}⌋ times, and the partitions λ for which this upper bound is achieved are precisely the P (n − j ⌊\frac{n}{j}⌋) partitions of n which contain ⌊\frac{n}{j}⌋ copies of j. Let S_{j} be the collection

of f_{λ}’s corresponding to these P (n − j ⌊\frac{n}{j}⌋) partitions. One sees immediately that

the dimension of the space spanned by the functions in S_{j} is just D (n − j ⌊\frac{n}{j}⌋):

in fact, the functions in this space are exactly 1/(1 − q^{j})^{⌊^{\frac{n}{j}}⌋} times the functions in F_{n−j⌊\frac{n}{j}⌋}.

Now the power of Φ_{j}(q) in the least common multiple of the denominators of all of the f_{λ}(q)’s excluding those in S_{j} is only ⌊\frac{n}{j}⌋ − 1, so the degree of this common denominator is only n(n + 1)/2 − ϕ(j). Therefore, as in the first paragraph of this section, the dimension of the space spanned by all of the f_{λ}’s except those in S_{j} is at most n(n − 1)/2 + 1 − ϕ(j); since the dimension spanned by the functions in S_{j} is D (n − j ⌊\frac{n}{j}⌋), we have proved the upper bound

D(n) ≤ \frac{n(n − 1)}{2} + 1 − ϕ(j) + D (n − j ⌊\frac{n}{j}⌋) .

If it happens that D (n − j ⌊\frac{n}{j}⌋) < ϕ(j), then this upper bound is an improvement on our original upper bound. If we repeat this process, this time simultaneously excluding the sets S_{j} for all of the j’s which gave us an improved upper bound in the above argument, we find that we have proved:

Proposition 2.1.

D(n) ≤ \frac{n(n − 1)}{2} + 1 − ∑_{j=1}^{n} max (0, ϕ(j) − D (n − j ⌊\frac{n}{j}⌋)).

Finally, we obtain an upper bound for D(n) which does not depend on other values of D(·):

Corollary 2.2. Recursively define U(0) = 1 and

U(n) = \frac{n(n − 1)}{2} + 1 − ∑_{j=1}^{n} max (0, ϕ(j) − U (n − j ⌊\frac{n}{j}⌋)).

Then D(n) ≤ U(n).

Proof. We proceed by induction on n. Equality certainly holds for n = 0. For larger n, the inductive hypothesis shows that D (n − j ⌊\frac{n}{j}⌋) ≤ U (n − j ⌊\frac{n}{j}⌋) when j > 0, and so

D(n) ≤ \frac{n(n − 1)}{2} + 1 − ∑_{j=1}^{n} max (0, ϕ(j) − D (n − j ⌊\frac{n}{j}⌋))

≤ \frac{n(n − 1)}{2} + 1 − ∑_{j=1}^{n} max (0, ϕ(j) − U (n − j ⌊\frac{n}{j}⌋))
= U(n).

Below is a table of values of D(n) and U(n) for n ≤ 23, calculated in Maple, with P (n) and our first estimate \frac{n(n−1)}{2} + 1 provided for contrast. Note that in the range 1 ≤ n ≤ 23, we have D(n) = U(n) except for n = 19, 20, when U(n) − D(n) = 1. Is it true, for instance, that

−D(n) + \frac{n(n − 1)}{2} + 1 − ∑_{j=1}^{n} max (0, ϕ(j) − D (n − j ⌊\frac{n}{j}⌋))

is bounded as n → ∞?

\begin{matrix}n & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 & 11 & 12 & 13 & 14 \\ D(n) & 1 & 2 & 3 & 5 & 7 & 11 & 13 & 19 & 23 & 29 & 35 & 45 & 51 & 62 \\ U(n) & 1 & 2 & 3 & 5 & 7 & 11 & 13 & 19 & 23 & 29 & 35 & 45 & 51 & 62 \\ n(n − 1)/2 + 1 & 1 & 2 & 4 & 7 & 11 & 16 & 22 & 29 & 37 & 46 & 56 & 67 & 79 & 92 \\ P (n) & 1 & 2 & 3 & 5 & 7 & 11 & 15 & 22 & 30 & 42 & 56 & 77 & 101 & 135 \end{matrix}

\begin{matrix}n & 15 & 16 & 17 & 18 & 19 & 20 & 21 & 22 & 23 \\ D(n) & 69 & 79 & 90 & 106 & 118 & 134 & 146 & 161 & 176 \\ U(n) & 69 & 79 & 90 & 106 & 119 & 135 & 146 & 161 & 176 \\ n(n − 1)/2 + 1 & 106 & 121 & 137 & 154 & 172 & 191 & 211 & 232 & 254 \\ P (n) & 176 & 231 & 297 & 385 & 490 & 627 & 792 & 1002 & 1255 \end{matrix}

Table 1. Values of D(n), U(n), n(n − 1)/2 + 1, P (n) for small n

Example 1. The first dimension where D(n) < P (n) is n = 7, and it is easy then to show that D(n) < P (n) for all n ≥ 7. The difference P (7) − D(7) = 2 arises from the following two relations:

\frac{4}{(1 − x^{2})^{2}(1 − x)^{3}} = \frac{3}{(1 − x^{3})(1 − x)^{4}} + \frac{1}{(1 − x^{3})(1 − x^{2})^{2}}

and

\frac{3}{(1 − x^{3})(1 − x^{2})(1 − x)^{2}} = \frac{2}{(1 − x^{4})(1 − x)^{3}} + \frac{1}{(1 − x^{4})(1 − x^{3})}.

The first relation, for example, says that if χ is a linear combination of χ_{N}’s, then

4 · χ((2, 2)-cycle) = 3 · χ(3-cycle) + χ((3, 2, 2)-cycle).

Alternately, it tells us that for any N ≥ 0, four times the number of nonnegative integral solutions to 2x_{1} + 2x_{2} + x_{3} + x_{4} + x_{5} = N is equal to three times the number of such solutions to 3x_{1} + x_{2} + x_{3} + x_{4} + x_{5} = N plus the number of such solutions to 3x_{1} + 2x_{2} + 2x_{3} = N.

3. Lower Bounds on D(n)

Let λ = (λ_{1}, …, λ_{k}) ⊢ n. The rational function f_{λ}(q) of equation (1) can be written as

f_{λ}(q) = p_{λ}(1, q, q^{2}, …),

where p_{λ} denotes a power sum symmetric function. (See [1, Ch. 7] for the necessary background on symmetric functions.) Since the p_{λ} for λ ⊢ n form a basis for the vector space (say over ℂ) Λ^{n} of all homogeneous symmetric functions of degree n [1, Cor. 7.7.2], it follows that if {u_{λ}}_{λ⊢n} is any basis for Λ^{n} then

D(n) = dim span_{ℂ}{u_{λ}(1, q, q^{2}, …) : λ ⊢ n}.

In particular, let u_{λ} = e_{λ}, the elementary symmetric function indexed by λ. Define

d(λ) = ∑_{i} \binom{λ_{i}}{2}.

According to [1, Prop. 7.8.3], we have

e_{λ}(1, q, q^{2}, …) = \frac{q^{d(λ)}}{∏_{i}(1 − q)(1 − q^{2}) ⋯ (1 − q^{λ_{i}})}.

Since power series of different degrees (where the degree of a power series is the exponent of its first nonzero term) are linearly independent, we obtain from Proposition 1.2 the following result.

Proposition 3.1. Let E(n) denote the number of distinct integers d(λ), where λ ranges over all partitions of n. Then D(n) ≥ E(n).

Note. We could also use the basis s_{λ} of Schur functions instead of e_{λ}, since by [1, Cor. 7.21.3] the degree of the power series s_{λ}(1, q, q^{2}, …) is d(λ′), where λ′ denotes the conjugate partition to λ.

Define G(n) + 1 to be the least positive integer that cannot be written in the form ∑_{i} \binom{λ_{i}}{2}, where λ ⊢ n. Thus all integers 1, 2, …, G(n) can be so represented, so D(n) ≥ E(n) ≥ G(n). We can obtain a relatively tractable lower bound for G(n), as follows. For a positive integer m, write (uniquely)

m = \binom{k_{1}}{2} + \binom{k_{2}}{2} + ⋯ + \binom{k_{r}}{2}, (3)

where k_{1} ≥ k_{2} ≥ ⋯ ≥ k_{r} ≥ 2 and k_{1}, k_{2}, … are chosen successively as large as possible so that

m − \binom{k_{1}}{2} − \binom{k_{2}}{2} − ⋯ − \binom{k_{i}}{2} ≥ 0

for all 1 ≤ i ≤ r. For instance, 26 = \binom{7}{2} + \binom{3}{2} + \binom{2}{2} + \binom{2}{2}. Define ν(m) = k_{1} + k_{2} + ⋯ + k_{r}. Suppose that ν(m) ≤ n for all m ≤ N. Then if m ≤ N we can write m = \binom{k_{1}}{2} + ⋯ + \binom{k_{r}}{2} so that k_{1} + ⋯ + k_{r} ≤ n. Hence if λ = (k_{1}, …, k_{r}, 1^{n−∑ k_{i}}) (where 1^{s} denotes s parts equal to 1), then λ is a partition of n for which ∑_{i} \binom{λ_{i}}{2} = m. It follows that if ν(m) ≤ n for all m ≤ N then G(n) ≥ N. Hence if we define H(n) to be the largest integer N for which ν(m) ≤ n whenever m ≤ N, then we have established the string of inequalities

D(n) ≥ E(n) ≥ G(n) ≥ H(n). (4)

Here is a table of values of these numbers for 1 ≤ n ≤ 23. Note that D(n) appears to be close to E(n + 1). We don’t have any theoretical explanation of this observation.

\begin{matrix}n & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 & 11 & 12 & 13 & 14 \\ D(n) & 1 & 2 & 3 & 5 & 7 & 11 & 13 & 19 & 23 & 29 & 35 & 45 & 51 & 62 \\ E(n) & 1 & 2 & 3 & 5 & 7 & 9 & 13 & 18 & 21 & 27 & 34 & 39 & 46 & 54 \\ G(n) & 0 & 1 & 1 & 3 & 4 & 4 & 7 & 13 & 13 & 18 & 25 & 32 & 32 & 32 \\ H(n) & 0 & 1 & 1 & 3 & 4 & 4 & 7 & 11 & 13 & 18 & 19 & 19 & 25 & 32 \end{matrix}

\begin{matrix}n & 15 & 16 & 17 & 18 & 19 & 20 & 21 & 22 & 23 \\ D(n) & 69 & 79 & 90 & 106 & 118 & 134 & 146 & 161 & 176 \\ E(n) & 61 & 72 & 83 & 92 & 106 & 118 & 130 & 145 & 162 \\ G(n) & 40 & 49 & 52 & 62 & 73 & 85 & 102 & 112 & 127 \\ H(n) & 40 & 43 & 52 & 62 & 73 & 85 & 89 & 102 & 116 \end{matrix}

Table 2. Values of D(n), E(n), G(n), H(n) for small n

Proposition 3.2. We have

ν(m) ≤ \sqrt{2m} + 3m^{1/4} (5)

for all m ≥ 405.

Proof. The proof is by induction on m. It can be checked with a computer that equation (5) is true for 405 ≤ m ≤ 50000. Now assume that M > 50000 and that (5) holds for 405 ≤ m < M. Let p = p_{M} be the unique positive integer satisfying

\binom{p}{2} ≤ M < \binom{p + 1}{2}.

Thus p is just the integer k_{1} of equation (3). Explicitly we have

p_{M} = ⌊\frac{1 + \sqrt{8M + 1}}{2}⌋ .

By the definition of ν(M) we have

ν(M) = p_{M} + ν (M − \binom{p_{M}}{2}) .

It can be checked that the maximum value of ν(m) for m < 405 is ν(404) = 42. Set q_{M} = (1 + \sqrt{8M + 1})/2. Since M − \binom{p_{M}}{2} ≤ p_{M} ≤ q_{M}, by the induction hypothesis we have

ν(M) ≤ q_{M} + max(42, \sqrt{2q_{M}} + 3q_{M}^{1/4}).

It is routine to check that when M > 50000 the right hand side is less than \sqrt{2M} + 3M^{1/4}, and the proof follows.

Proposition 3.3. There exists a constant c > 0 such that

H(n) ≥ \frac{n^{2}}{2} − cn^{3/2}

for all n ≥ 1.

Proof. From the definition of H(n) and Proposition 3.2 (and the fact that the righthand side of equation (5) is increasing), along with the inquality ν(m) ≤ 42 = ⌈\sqrt{2 · 405} + 3 · 405^{1/4}⌉ for m ≤ 404, it follows that

H (⌈\sqrt{2m} + 3m^{1/4}⌉) ≥ m

for m > 404. For n sufficiently large, we can evidently choose m such that n = ⌈\sqrt{2m} + 3m^{1/4}⌉, so H(n) ≥ m. Since \sqrt{2m} + 3m^{1/4} + 1 > n, an application of the quadratic formula (again for n sufficiently large) shows

m^{1/4} ≥ \frac{−3 + \sqrt{9 + 4\sqrt{2}(n − 1)}}{2\sqrt{2}},

from which the result follows without difficulty.

Since we have established both upper bounds (equation (2)) and lower bounds (equation (4) and Proposition 3.3) for D(n) asymptotic to n^{2}/2, we obtain the following corollary.

Corollary 3.4. There holds the asymptotic formula D(n) ∼ \frac{1}{2}n^{2}.

References

[1] R. Stanley, Enumerative Combinatorics, vol. 2, Cambridge University Press, New York/Cambridge, 1999.