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

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}$?

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.

-
Not an explicit formula, but the Newton identity $\sum\limits_{n=1}^{\infty}p_nT^n=T\frac{d}{dT}\log\left(\prod\limits_{i=1}^N\df‌​rac{1}{1-x_iT}\right)$ (this is an identity of formal power series, where $\log$ is the natural logarithm, and $x_1$, $x_2$, ..., $x_N$ are our variables) yields $\exp\left(-\sum\limits_{n=1}^{\infty}\frac{1}{n}p_nT^n\right)=\prod\limits_{i=1‌​}^N\left(1-x_iT\right)$, which is a polynomial of degree $N$, so that all coefficients before $T^{N+1}$, $T^{N+2}$, ... are zero - and this yields exactly the formulas you want. –  darij grinberg Aug 26 '10 at 15:40
Actually, you can write it as $\sum\limits_{i=0}^k\left(-1\right)^i\sum\limits_{j_1,\ j_2,\ ...,\ j_i\geq 1;\ j_1+j_2+...+j_i=n}\dfrac{1}{j_1j_2...j_i}p_{j_1}p_{j_2}...p_{j_i}=0$ for $k>N$ unless I have made a mistake. –  darij grinberg Aug 26 '10 at 15:46
Thanks! If I understand correctly, this yields a nice relation between the power sum polynomials $p_1,\ldots,p_k$ for $k > N$. However, as you mentioned, this is not an explicit formula. Indeed, in order to expand $$p_k(x_1,\ldots,x_N)$$ in terms of only $N$ power sums $$p_1(x_1,\ldots,x_N),\ldots,p_N(x_1,\ldots,x_N)$$ that form a complete basis for symmetric polynomials in $N$ variables, one should further apply your formula iteratively for each of the lower degree power sums $p_{k-1},\ p_{k-2},\ldots, p_{N+1}$ that appear in your formula for $p_k$. –  Peter Erskin Aug 27 '10 at 9:00
I am not sure that the formula for the Schur functions which I quoted from Wikipedia (see my question) includes only $p_j$ with $j\le N$ when the degree of the Schur function is higher than $N$. Apparently, in this case one has $p_k$ with $k > N$ on the r.h.s. However, the corresponding coefficients might be identically zero --- I did not check. If this is not the case, it is interesting to learn what is the expansion of the Schur function $s_\lambda$ of degree higher than $N$ in terms of only the first $N$ power sums $p_1,...,p_N$. –  Peter Erskin Aug 27 '10 at 9:42
@ darij grinberg: it seems that there might be some $1/i!$'s (or something) missing from your formula? Compare to Akkerman's answer for computing $p_{N+1}$. –  Ian Agol Aug 22 '13 at 21:29

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}}$.

-
Thank you very much for the explicit (in contrast to previous suggestions) formula and for the clarification! The formula really works and it looks simpler than the determinant-of-determinants that I proposed in the "Note Added". Unfortunately, I do not see how to present your expression for $p_k$ in the form similar to your formula for $e_n$. Is it possible to find the combinatorial coefficients $a_{k;\rho}$ as discussed in my question? –  Peter Erskin Aug 27 '10 at 15:40
@Gjergji: instead of the first identity I would just say that the trace of the matrix you wrote down is p_{k-n} and leave it at that. –  Qiaochu Yuan Aug 27 '10 at 15:54
@Qiaochu: Yes, I don't know why I wrote it like that, same thing I guess. @Peter Erskin, I mentioned above that combinatorialists care about the case of infinitely many variables. What reasons do we have to believe that $a_{k,\rho}$ has any nice form? They aren't even integers, and they depend on $N$... –  Gjergji Zaimi Aug 28 '10 at 1:32

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$.

-
I have fixed some obvious typos, but are you sure about requiring $k\geq 2N$? –  darij grinberg Aug 26 '10 at 17:59
I mean, you can define $p_u$ for negative $u$ by $p_u=0$, and $p_0=n$. –  darij grinberg Aug 26 '10 at 18:00
Darij, I am assuming $p_0=N$ but for negative $u$ one still needs $p_u=\sum x_j^u$. –  Robin Chapman Aug 26 '10 at 18:17
Thank you, Robin! Your formula relates $p_k$ to lower degree power sums including $p_m$ with $m>N,$ right? However, I wanted to express $p_k$ entirely through $p_1,...,p_N.$ This is formally done in the next answer by Gjergji Zaimi, as well as in the "Note Added" above (probably, the original formulation of my question was not particularly clear, sorry). Nevertheless, I think your contribution to the discussion is really very important. Thanks. –  Peter Erskin Aug 27 '10 at 15:54

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.

-

$$p_k = -k\int_0^{2\pi}\frac{d\theta}{2\pi}e^{-i k \theta} \ln\left\{ \int_0^{2\pi}\frac{d\phi}{2\pi}\ \sum_{m=0}^N e^{i m (\theta-\phi)} \exp\left[ -\sum_{s=1}^N \frac{p_s}{s}\ e^{i s \phi} \right] \right\}.$$

-
Can you give an explanation for this? –  Stefan Kohl Oct 9 '13 at 23:04
The formula can be derived using the proposal by Robin Chapman and Gjergji Zaimi (see also the comment by Qiaochu Yuan) above. If you are interested in details, please contact me over e-mail. –  Igor Gornyi Oct 10 '13 at 8:28