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$?
  • 3
    $\begingroup$ For Q#1, isn't the number of terms (monomials) equal to the partition number of $k$, i.e. $\sum_{\lambda\vdash k}1$? $\endgroup$ – T. Amdeberhan Dec 7 '16 at 1:07
  • $\begingroup$ See oeis.org/A263916 on the Faber polynomials. $\endgroup$ – Tom Copeland Dec 7 '16 at 3:33
  • 2
    $\begingroup$ Isn't $F_k$ independent of $n$ (for $n\geq k$)? $\endgroup$ – Julian Rosen Dec 7 '16 at 3:44
  • 1
    $\begingroup$ 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$. $\endgroup$ – GH from MO Dec 7 '16 at 10:31
  • $\begingroup$ 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. $\endgroup$ – 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.

| cite | improve this answer | |
  • $\begingroup$ The sum of the coefficients is -1. $\endgroup$ – Tom Copeland Dec 7 '16 at 4:11
  • $\begingroup$ Rather 1 in your case. $\endgroup$ – Tom Copeland Dec 7 '16 at 5:08
  • $\begingroup$ That's oeis.org/A000041. $\endgroup$ – Tom Copeland Apr 1 '17 at 15:41

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.