Posted by: yanzhang | April 9, 2009

A Useful Symmetric Function Identity

A not often-mentioned skill that I have been trying to develop is the evaluation of the “usefulness” of statements. Given my horrible memory and degrading mental RAM, I must prioritize which facts to consciously absorb and which ones to skim, since I’m sure I forget at least one theorem every time I learn a new one. Luckily, books aid to an extent by labelling the important things “Theorems” and “Lemmas,” though sometimes the latter are just as important as (if not much more than) the former, and sometimes even more important items appear in the Exercises section. Something about Exercise 7.70 in Richard Stanley’s Enumerative Combinatorics 2 really struck me as “useful.” The statement is:

\sum_{\lambda \vdash n} H_\lambda^{k-2} \prod_i^k s_\lambda(x^{(i)}) = \frac{1}{n!}\sum_{\prod w_i = 1} \prod_i^k p_{\rho(w_i)}(x^{(i)}), where the x^{(i)} are sets of variables, H_\lambda the product of the hook-lengths, \rho(w) gives the cycle structure, and w_i are permutations of size n.

Two things make the intuition of “useful” more concrete:

One, the statement has a lot of flexibility; By the symmetry of the symmetric group and the fact that cycles are preserved under inverses, you can sum over, say, products of all ordered (k-1)-tuples of w_i by rewriting the sum on the right as over w_1 = w_2\ldots w_k, for example, or sum over pairs which give the same product, say w_1w_2 = w_3w_4. Furthermore, having the choice over the variables makes a lot of specialization techniques useful. For example, you can “pick out” cycles by specializing x^{(i)} = (1, \zeta, \ldots, \zeta^{n-1}, 0, 0, \ldots), where \zeta is an n-th root of unity, because the power sums then give p_c(x^{(i)}) = 0 unless c = n.

Two, the statement has a lot of power; the proof of this fact has a “Stanley difficulty” of [3] (out of 5) means it contains some nontrivial usage of the symmetric function machinery already. Thus, by using it we know we are backed with some complex stuff in the background. Note when k = 1, we get the amazing Hook-length formula directly; when k = 2, by observing that summing over w_1w_2 = 1 is really summing over a single w (a special case of our discussion above on “flexibility”), we get the familiar “inner product” identity\sum_{\lambda \vdash n} s_\lambda(x) s_\lambda(y) = \frac{1}{n!}\sum_w p_{\rho(w)}(x) p_{\rho(w)}(y). These are two nontrivial statements without an obvious connection with each other, a pleasant surprise.

This warm “finding a hidden gem” feeling is very nice.


P.S. Well, there is a third (and less glamorous) cue, which is that at least two problems in the problem sets came with the hint: “Look at Exercise 7.70.” The power of hindsight in all its glory, I suppose. However, I liked this statement too much that I needed an excuse to write it down, so shhh.


Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s


%d bloggers like this: