Expressing power sum symmetric polynomials in terms of lower degree power sums - MathOverflow

Expressing power sum symmetric polynomials in terms of lower degree power sums

2010-08-26T15:11:47Z

Is there an explicit formula expressing the power sum symmetric polynomials $$p_k(x_1,\ldots,x_N)=\sum\nolimits_{i=1}^N x_i^k = x_1^k+\cdots+x_N^k$$ of degree $k$ in $N < k$ variables entirely through the power sum symmetric polynomials $p_j(x_1,\ldots,x_N)$ of degrees $ j \le N $?

Examples: $$N=1,\ k=2: \quad p_2=x^2=x\times x=p_1^2$$

$$N=2,\ k=3: \quad p_3 = x^3 + y^3 = [3(x^2+y^2)(x+y)-(x+y)^3]/2 = (3 p_2 p_1-p_1^3)/2$$

What is the general formula?

I am looking for a formula similar to that for the expansion of the Schur functions $s_\lambda$ in terms of the symmetric power sums:

$$ s_\lambda=\sum_{\rho=(1^{r_1},2^{r_2},3^{r_3},\dots)}\chi^\lambda_\rho \prod_j \frac{p^{r_j}_j}{r_j!},$$ where the coefficients $\chi^\lambda_\rho$ are the characters of the representation of the symmetric group indexed by the partition $\lambda$ evaluated at elements of cycle type indexed by the partition $\rho=(1^{r_1},2^{r_2},3^{r_3},\dots)$, which contains $ r_j $ parts of length $j$.

Clearly, the power sums of degree higher than $N$ can be expanded in a similar manner: $$ p_k=\sum_{\rho}a_{k;\rho}\prod_{j=1}^N p_j^{r_j}, $$ where $\rho=(1^{r_1},2^{r_2},\dots,N^{r_N})$ is the partition of $k$ such that $k=r_1+2r_2+3r_3+...+Nr_N$.

In the above example for $N=2,\ k=3$ one has $a_{3;\ (1^{1},2^{1}) }=3/2$ and $a_{3;\ (1^{3},2^{0})}=-1/2$.

My question can be thus reformulated as follows: given $r_1,...,r_N$ what is the explicit formula for $a_{k;\rho}$?

Note Added

Actually, Wikipedia tells us how to construct a certain explicit formula for $p_k$. It gives the following expressions for $p_n$ with $n=N$ in terms of $ e_j, $

$$ p_n = \begin{vmatrix} e_1 & 1 & 0 & \cdots & \\ 2e_2 & e_1 & 1 & 0 & \cdots & \\ 3e_3 & e_2 & e_1 & 1 & \cdots & \\ \vdots &&& \ddots & \ddots & \\ ne_n & e_{n-1} & \cdots & & e_1 & \end{vmatrix}, $$

and for $e_n$ with $n=N$ in terms of $ p_j, $

$$ e_n=\frac1{n!} \begin{vmatrix}p_1 & 1 & 0 & \cdots\\ p_2 & p_1 & 2 & 0 & \cdots \\ \vdots&& \ddots & \ddots \\ p_{n-1} & p_{n-2} & \cdots & p_1 & n-1 \\ p_n & p_{n-1} & \cdots & p_2 & p_1 \end{vmatrix}. $$

As far as I can see from the derivation described in Wikipedia, these determinant expressions are also valid for $p_n$ with $ n > N $ and for $e_n$ with $ n < N $.

For $p_n$ with $n>N$ one should take into account that all $ e_k=0 $ for $ k > N $, so that the resulting matrix has zeros in both right-upper and left-lower corners.

Substituting the determinants for $e_j$ into the determinant for $p_k$, one gets the explicit formula which seems to solve the problem.

However, I still don't know how to obtain the coefficients $a_{k;\rho}$ in the expansion of $ p_k $ in terms of the first $N$ power sums which would be the desired (really explicit) formula.

Answer by Robin Chapman for Expressing power sum symmetric polynomials in terms of lower degree power sums

2010-08-26T16:41:05Z

If $e_1,\ldots,e_N$ are the elementary symmetric functions of $x_1,\ldots,x_N$ then for $k\ge N$ one has $$p_k=\sum_{j=1}^N(-1)^{j-1}e_j p_{k-j}.$$ This formula uses the elementary symmetric functions, which I presume you want to avoid, but it means that for $k\ge 2N$ the $(N+1)$ by $(N+1)$ matrix $$M_k=(p_{k-i-j})_{i,j=0}^N$$ has the null-vector $(1,-e_1,e_2,-e_3,\ldots,\pm e_N)$ and so $\det(M_k)=0$. Expanding this out gives an explicit formula for $p_k$ as a rational function (alas!) of $p_{k-1},\ldots,p_{k-2N}$.

Added I suppose one can express the $e_j$ in terms of $p_1,\ldots,p_n$ and put them into the above linear recurrence for $p_k$.

Answer by Gjergji Zaimi for Expressing power sum symmetric polynomials in terms of lower degree power sums

2010-08-27T11:16:51Z

Assuming you have $n$ variables then for $k\geq n$, Robin Chapman's identity above can be written as $$(p_n,p_{n-1},\dots, p_1)\begin{pmatrix} e_1 & 1 & \cdots & 0 \\ -e_2 & 0 & \ddots & \vdots \\ \vdots & \vdots & \ddots & 1 \\ (-1)^{n-1}e_n & 0 & \cdots & 0 \end{pmatrix}^{k-n}=(p_k,p_{k-1},\dots, p_{k-n+1})$$

Now to finish the job you need to express the $e_i$'s in terms of the power sum symmetric functions too. This is given by $$e_n=\sum_{|\lambda|=n}(-1)^{|\lambda|-l(\lambda)} z_{\lambda}^{-1}p_{\lambda}$$ where $|\lambda|$ is the size of the partition $\lambda$ and $l(\lambda)$ is its length, $p_{\lambda}=p_{\lambda_1}p_{\lambda_2}\cdots$ and $$z_{\lambda}=\prod_{i\geq 1}\left(i^{m_i}\cdot m_i!\right)$$ where $m_i$ is the number of parts of $\lambda$ equal to $i$.

I thought I'd remark that the formulas you are quoting are all valid in $\Lambda_{\mathbb{Q}}$, the ring of symmetric functions in infinitely many variables while the one you are searching for is not, because the $p_\lambda$'s are an orthogonal basis in this ring with $\langle p_{\lambda},p_{\mu}\rangle =\delta_{\lambda \mu}z_{\lambda}$. This is also the same reason why the formula for Schur polynomials may contain arbitrary $p_{\lambda}$'s in it. In fact the reason why that formula is important is because it gives you the transition from the basis of Schur polynomials to that of power sum polynomials in $\Lambda_{\mathbb{Q}}$.

Answer by Akkerman for Expressing power sum symmetric polynomials in terms of lower degree power sums

2010-08-31T08:59:39Z

Combining the trace formula proposed by Gjergji Zaimi and Qiaochu Yuan, $$ p_k={\rm Tr}\begin{pmatrix} e_1 & 1 & \cdots & 0 \\ -e_2 & 0 & \ddots & \vdots \\ \vdots & \vdots & \ddots & 1 \\ (-1)^{N-1}e_N & 0 & \cdots & 0 \end{pmatrix}^{k}, $$ with the formula quoted by Peter Erskin, $$ e_n=\frac1{n!} \begin{vmatrix}p_1 & 1 & 0 & \cdots\\ p_2 & p_1 & 2 & 0 & \cdots \\ \vdots&& \ddots & \ddots \\ p_{n-1} & p_{n-2} & \cdots & p_1 & n-1 \\ p_n & p_{n-1} & \cdots & p_2 & p_1 \end{vmatrix}, $$ Mathematica produces the following expansions of $p_k$:

$$N=2$$

$$ p_3=-\frac{1}{2}\ p_1^3+\frac{3}{2}\ p_1p_2 $$

$$ p_4=-\frac{1}{2}\ p_1^4+p_1^2p_2+\frac{1}{2}\ p_2^2 $$

$$ p_5=-\frac{1}{4}\ p_1^5+\frac{5}{4}\ p_1p_2 ^2 $$

$$ p_6=-\frac{3}{4}\ p_1^4p_2+\frac{3}{2}\ p_1^2p_2^2+\frac{1}{4}\ p_2^3 $$

$$ p_7=\frac{1}{8}\ p_1^7-\frac{7}{8}\ p_1^5p_2+\frac{7}{8}\ p_1^3p_2^2+\frac{7}{8}\ p_1p_2^3 $$

$$ p_8=\frac{1}{8}\ p_1^8-\frac{1}{2}\ p_1^6p_2-\frac{1}{4}\ p_1^4p_2^2+\frac{3}{2}\ p_1^2p_2^3+\frac{1}{8}\ p_2^4 $$

$$ p_9=\frac{1}{16}\ p_1^9-\frac{9}{8}\ p_1^5p_2^2+\frac{3}{2}\ p_1^3p_2^3 +\frac{9}{16}\ p_1p_2^4 $$

$$ p_{10}=\frac{5}{16}\ p_1^8p_2-\frac{5}{4}\ p_1^6p_2^2+\frac{5}{8}\ p_1^4p_2^3 +\frac{5}{4}\ p_1^2p_2^4+\frac{1}{16}\ p_2^5 $$

$$ p_{11}=-\frac{1}{32}\ p_1^{11}+\frac{11}{32}\ p_1^9p_2-\frac{11}{16}\ p_1^7p_2^2-\frac{11}{16}\ p_1^5p_2^3 +\frac{55}{32}\ p_1^3p_2^4+\frac{11}{32}\ p_1p_2^5 $$

$$N=3$$

$$ p_4=\frac{1}{6}\ p_1^4-p_1^2p_2+\frac{1}{2}\ p_2^2+ \frac{4}{3}\ p_1p_3 $$

$$ p_5=\frac{1}{6}\ p_1^5-\frac{5}{6}\ p_1^3p_2+\frac{5}{6}\ p_1^2p_3+\frac{5}{6}\ p_2p_3 $$

$$ p_6=\frac{1}{12}\ p_1^6-\frac{1}{4}\ p_1^4p_2-\frac{3}{4}\ p_1^2p_2^2+\frac{1}{4}\ p_2^3+\frac{1}{3}\ p_1^3p_2^3+p_1 p_2 p_3 +\frac{1}{3}\ p_3^2 $$

$$ p_7=\frac{1}{36}\ p_1^7-\frac{7}{12}\ p_1^3p_2^2+\frac{7}{36}\ p_1^4p_3+\frac{7}{12}\ p_2^2p_3+\frac{7}{9}\ p_1p_3^2 $$

$$ p_8=\frac{1}{72}\ p_1^8-\frac{1}{18}\ p_1^6p_2+\frac{1}{12}\ p_1^4p_2^2-\frac{1}{2}\ p_1^2p_2^3+\frac{1}{8}\ p_2^4+\frac{2}{9}\ p_1^5p_3 $$ $$ -\frac{8}{9}\ p_1^3p_2p_3+\frac{2}{3}\ p_1p_2^2p_3+\frac{8}{9}\ p_1^2p_3^2+\frac{4}{9}\ p_2p_3^2 $$

$$N=4$$

$$ p_5=-\frac{1}{24}\ p_1^5+\frac{5}{12}\ p_1^3p_2-\frac{5}{8}\ p_1p_2^2-\frac{5}{6}\ p_1^2p_3+\frac{5}{6}\ p_2p_3+\frac{5}{4}\ p_1p_4 $$

$$ p_6=-\frac{1}{24}\ p_1^6+\frac{3}{8}\ p_1^4p_2-\frac{3}{8}\ p_1^2p_2^2-\frac{1}{8}\ p_2^3-\frac{2}{3}\ p_1^3p_3+\frac{1}{3}\ p_3^2+\frac{3}{4}\ p_1^2p_4+\frac{3}{4}\ p_2p_4 $$

$$ p_7=-\frac{1}{48}\ p_1^7+\frac{7}{48}\ p_1^5p_2+\frac{7}{48}\ p_1^3p_2^2-\frac{7}{16}\ p_1p_2^2-\frac{7}{24}\ p_1^4p_3-\frac{7}{12}\ p_1^2p_2p_3 $$ $$+\frac{7}{24}\ p_2^2p_3 +\frac{7}{24}\ p_1^3p_4+\frac{7}{8}\ p_1p_2p_4+\frac{7}{12}\ p_3p_4 $$

$$ p_8=-\frac{1}{144}\ p_1^8+\frac{1}{36}\ p_1^6p_2+\frac{5}{24}\ p_1^4p_2^2 -\frac{1}{4}\ p_1^2p_2^2-\frac{1}{16}\ p_2^4 $$ $$ -\frac{1}{9}\ p_1^5p_3-\frac{2}{9}\ p_1^3p_2p_3 -\frac{1}{3}\ p_1p_2^2p_3-\frac{4}{9}\ p_1^2p_3^2+\frac{4}{9}\ p_2p_3^2 $$ $$ +\frac{1}{12}\ p_1^4p_4+\frac{1}{2}\ p_1^2p_2p_4+\frac{1}{4}\ p_2^2p_4 +\frac{2}{3}\ p_1p_3p_4+\frac{1}{4}\ p_4^2. $$

It seems to me that a nice and compact formula for $a_{k,\rho}$ does exist. Indeed, the coefficients in the above examples are extremely simple.

In particular, I observe that the last terms in each of $p_k$ for $N=8$ have the form $$ k\ \prod_j \frac{1}{j^{r_j}r_j!}p_j^{r_j}, $$ which corresponds to $$ a_{k,\rho}=k\prod_j \frac{1}{j^{r_j}r_j!}. $$ This formula (whose structure resembles the coefficients in the expansion of Schur functions quoted by Peter Erskin) also works for all terms of the type $p_jp_{k-j}$ at arbitrary $N$.

Apparently, this is not a general formula, as can be seen from the coefficients in front of $p_1^k$ which do depend on $N$. I believe, however, that the general formula for $a_{k,\rho}$ with $N$ properly included should not be much more complex than the empirical one above.

Hope this helps.