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

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

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:

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