# Coefficients of polynomials appearing in Newton identities relating symmetric polynomials to power sums

Let $$p_k(x_1,\ldots,x_n)=x_1^k+\cdots+x_n^k$$ and let $$e_k(x_1,\ldots,x_n)=\sum_{1\le i_1<i_2<\ldots<i_k\le n}x_{i_1}\cdots x_{i_k}$$ be the $k$'th symmetric polynomial. It is well known that there exists a unique polynomial $$F_k(y_1,\ldots,y_k)\in\mathbb Z[y_1,\ldots,y_k]$$ such that $$p_k(x_1,\ldots,x_n) = F_k\bigl(e_1(x_1,\ldots,x_n),\ldots,e_k(x_1,\ldots,x_n)\bigr).$$ (See for example https://en.wikipedia.org/w/index.php?title=Newton%27s_identities&oldid=733760875#Expressing_power_sums_in_terms_of_elementary_symmetric_polynomials.)

I have two questions about the polynomial $F_k$.

1. Are there reasonable upper and lower bounds, in terms of $n$ and $k$, for the number of monomials that appear in $F_k$?

2. Are there reasonable upper and lower bounds, in terms of $n$ and $k$, for the average absolute value of the coefficients of the monomials in $F_k$?

And here a more specific question, which is where the above problems arose:

1. If we let $(\epsilon_1,\ldots,\epsilon_k)$ range over the $2^k$ elements of $\{-1,1\}^k$, find decent upper and lower bounds for the average value of $\bigl|F_k(\epsilon_1,\ldots,\epsilon_k)\bigr|$ in terms of $n$ and $k$. In particular, is it true that if, say, $\frac14 n \le k \le \frac34 n$, then the average value of $\bigl|F_k(\epsilon_1,\ldots,\epsilon_k)\bigr|$ grows exponentially in $n$?
• For Q#1, isn't the number of terms (monomials) equal to the partition number of $k$, i.e. $\sum_{\lambda\vdash k}1$? – T. Amdeberhan Dec 7 '16 at 1:07
• See oeis.org/A263916 on the Faber polynomials. – Tom Copeland Dec 7 '16 at 3:33
• Isn't $F_k$ independent of $n$ (for $n\geq k$)? – Julian Rosen Dec 7 '16 at 3:44
• I agree with the above comments: $F_k$ is independent of $n$ for $n\geq k$ (which is your case of interest in #3), and the number of monomials in it is the number of partitions of $k$, which is asymptotically $(4k\sqrt{3})^{-1}\exp(\pi\sqrt{2k/3})$ as $k\to\infty$. – GH from MO Dec 7 '16 at 10:31
• Info on the asymptotics is in A000041, naturally, in the formula section along with references and a link to another table of estimates and a refinement. – Tom Copeland Dec 7 '16 at 15:22

OEIS A00041 gives the number of monomials. The absolute values of the coefficients of the polynomials sum to $2^k-1$. See A263916 for more notes and references on these Faber polynomials.