Expressing power sum symmetric polynomials in terms of lower degree power sums - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-24T20:28:25Z http://mathoverflow.net/feeds/question/36771 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/36771/expressing-power-sum-symmetric-polynomials-in-terms-of-lower-degree-power-sums Expressing power sum symmetric polynomials in terms of lower degree power sums Peter Erskin 2010-08-26T15:11:47Z 2010-09-01T07:35:04Z <p>Is there an explicit formula expressing the <a href="http://en.wikipedia.org/wiki/Power_sum_symmetric_polynomial" rel="nofollow">power sum symmetric polynomials</a> $$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 &lt; k$ variables entirely through the power sum symmetric polynomials $p_j(x_1,\ldots,x_N)$ of degrees $j \le N$? </p> <p>Examples: $$N=1,\ k=2: \quad p_2=x^2=x\times x=p_1^2$$</p> <p>$$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$$</p> <blockquote> <p>What is the general formula?</p> </blockquote> <p>I am looking for a formula similar to that for the expansion of the <a href="http://en.wikipedia.org/wiki/Schur_polynomial#Relation_to_representation_theory" rel="nofollow">Schur functions</a> $s_\lambda$ in terms of the symmetric power sums:</p> <p>$$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$. </p> <p>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$. </p> <p>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$. </p> <blockquote> <p>My question can be thus reformulated as follows: given $r_1,...,r_N$ what is the explicit formula for $a_{k;\rho}$?</p> </blockquote> <hr> <p><strong>Note Added</strong></p> <p>Actually, <a href="http://en.wikipedia.org/wiki/Newton%27s_identities#Expressions_as_determinants" rel="nofollow">Wikipedia</a> 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> <p>$$p_n = \begin{vmatrix} e_1 &amp; 1 &amp; 0 &amp; \cdots &amp; \\ 2e_2 &amp; e_1 &amp; 1 &amp; 0 &amp; \cdots &amp; \\ 3e_3 &amp; e_2 &amp; e_1 &amp; 1 &amp; \cdots &amp; \\ \vdots &amp;&amp;&amp; \ddots &amp; \ddots &amp; \\ ne_n &amp; e_{n-1} &amp; \cdots &amp; &amp; e_1 &amp; \end{vmatrix},$$</p> <p>and for $e_n$ with $n=N$ in terms of $p_j,$</p> <p>$$e_n=\frac1{n!} \begin{vmatrix}p_1 &amp; 1 &amp; 0 &amp; \cdots\\ p_2 &amp; p_1 &amp; 2 &amp; 0 &amp; \cdots \\ \vdots&amp;&amp; \ddots &amp; \ddots \\ p_{n-1} &amp; p_{n-2} &amp; \cdots &amp; p_1 &amp; n-1 \\ p_n &amp; p_{n-1} &amp; \cdots &amp; p_2 &amp; p_1 \end{vmatrix}.$$</p> <p>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 &lt; N$.</p> <p>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. </p> <p>Substituting the determinants for $e_j$ into the determinant for $p_k$, one gets the explicit formula which seems to solve the problem. </p> <p>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. </p> http://mathoverflow.net/questions/36771/expressing-power-sum-symmetric-polynomials-in-terms-of-lower-degree-power-sums/36779#36779 Answer by Robin Chapman for Expressing power sum symmetric polynomials in terms of lower degree power sums Robin Chapman 2010-08-26T16:41:05Z 2010-08-26T18:15:43Z <p>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 <strong>rational function</strong> (alas!) of $p_{k-1},\ldots,p_{k-2N}$.</p> <p><strong>Added</strong> 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$.</p> http://mathoverflow.net/questions/36771/expressing-power-sum-symmetric-polynomials-in-terms-of-lower-degree-power-sums/36873#36873 Answer by Gjergji Zaimi for Expressing power sum symmetric polynomials in terms of lower degree power sums Gjergji Zaimi 2010-08-27T11:16:51Z 2010-08-27T12:06:21Z <p>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 &amp; 1 &amp; \cdots &amp; 0 \\ -e_2 &amp; 0 &amp; \ddots &amp; \vdots \\ \vdots &amp; \vdots &amp; \ddots &amp; 1 \\ (-1)^{n-1}e_n &amp; 0 &amp; \cdots &amp; 0 \end{pmatrix}^{k-n}=(p_k,p_{k-1},\dots, p_{k-n+1})$$</p> <p>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$.</p> <hr> <p>I thought I'd remark that the formulas you are quoting are all valid in $\Lambda_{\mathbb{Q}}$, the ring of symmetric functions in <em>infinitely</em> 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}}$.</p> http://mathoverflow.net/questions/36771/expressing-power-sum-symmetric-polynomials-in-terms-of-lower-degree-power-sums/37235#37235 Answer by Akkerman for Expressing power sum symmetric polynomials in terms of lower degree power sums Akkerman 2010-08-31T08:59:39Z 2010-09-01T07:35:04Z <p>Combining the trace formula proposed by Gjergji Zaimi and Qiaochu Yuan, $$p_k={\rm Tr}\begin{pmatrix} e_1 &amp; 1 &amp; \cdots &amp; 0 \\ -e_2 &amp; 0 &amp; \ddots &amp; \vdots \\ \vdots &amp; \vdots &amp; \ddots &amp; 1 \\ (-1)^{N-1}e_N &amp; 0 &amp; \cdots &amp; 0 \end{pmatrix}^{k},$$ with the formula quoted by Peter Erskin, $$e_n=\frac1{n!} \begin{vmatrix}p_1 &amp; 1 &amp; 0 &amp; \cdots\\ p_2 &amp; p_1 &amp; 2 &amp; 0 &amp; \cdots \\ \vdots&amp;&amp; \ddots &amp; \ddots \\ p_{n-1} &amp; p_{n-2} &amp; \cdots &amp; p_1 &amp; n-1 \\ p_n &amp; p_{n-1} &amp; \cdots &amp; p_2 &amp; p_1 \end{vmatrix},$$ Mathematica produces the following expansions of $p_k$:</p> <hr> <p>$$N=2$$</p> <p>$$p_3=-\frac{1}{2}\ p_1^3+\frac{3}{2}\ p_1p_2$$</p> <p>$$p_4=-\frac{1}{2}\ p_1^4+p_1^2p_2+\frac{1}{2}\ p_2^2$$</p> <p>$$p_5=-\frac{1}{4}\ p_1^5+\frac{5}{4}\ p_1p_2 ^2$$</p> <p>$$p_6=-\frac{3}{4}\ p_1^4p_2+\frac{3}{2}\ p_1^2p_2^2+\frac{1}{4}\ p_2^3$$</p> <p>$$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> <p>$$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> <p>$$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> <p>$$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> <p>$$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$$</p> <hr> <p>$$N=3$$</p> <p>$$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> <p>$$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> <p>$$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> <p>$$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> <p>$$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$$</p> <hr> <p>$$N=4$$</p> <p>$$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> <p>$$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> <p>$$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> <p>$$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.$$</p> <hr> <p>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. </p> <p>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$. </p> <p>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.</p> <p>Hope this helps.</p>