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.

-Y

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.