# Dimension reduction for non-negativity of elementary symmetric polynomials

Fix integers $$1 \leq k \leq n$$ and suppose $$\mathbf{x} \in \mathbb{R}^n$$ is such that $$e_j(x_1,x_2,\ldots,x_n) \geq 0$$ for all $$1 \leq j \leq k$$, where $$e_j$$ is the $$j$$-th elementary symmetric polynomial.

Question 1: Is it true that $$x_1 + x_2 + \cdots + x_{n-k+1} \geq 0$$?

The answer is trivially "yes" in the edge cases $$k = 1$$ and $$k = n$$, but the intermediate cases seem much less obvious.

While Question 1 is the one that I'm really interested in, there is a natural generalization of it that is perhaps known, so I'll ask it now:

Question 2: Is it true that $$e_j(x_1,x_2,\ldots,x_{n-1}) \geq 0$$ for all $$1 \leq j \leq k-1$$?

In other words, can we use non-negativity of elementary symmetric polynomials in $$n$$ variables to infer non-negativity of elementary symmetric polynomials in $$n-1$$ variables? If the answer to Question 2 is "yes" then we can use it $$k-1$$ times to see that the answer to Question 1 is "yes" too.

The answer to question 2, and therefore question 1, is "yes". We abbreviate $$e_k(x_1, x_2, \ldots, x_{n-1})$$ to $$b_k$$ and $$e_k(x_1, x_2, \ldots, x_{n-1}, x_n)$$ to $$a_k$$, so $$a_k = x_n b_{k-1} + b_k$$.

We are trying to show that, if $$a_1$$, $$a_2$$, ..., $$a_k \geq 0$$ then $$b_1$$, $$b_2$$, ..., $$b_{k-1} \geq 0$$. We prefer to prove the contrapositive: If $$b_j<0$$ then one of $$a_1$$, $$a_2$$, ..., $$a_j$$, $$a_{j+1} <0$$. We may assume that $$j$$ is minimal with $$b_j<0$$, so $$b_1$$, $$b_2$$, ..., $$b_{j-1} \geq 0$$.

Case 1: $$x_n<0$$. Then $$a_j = x_n b_{j-1} + b_j < 0$$.

Case 2: $$x_n \geq 0$$. First of all, if $$b_{j-1} \leq 0$$, then $$a_j<0$$ and, if $$b_{j+1} \leq 0$$, then $$a_{j+1} < 0$$. So we may assume that $$b_{j-1}$$ and $$b_{j+1}>0$$.

Now, Newton's inequalities give $$\frac{b_{j-1} b_{j+1}}{\binom{n-1}{j-1} \binom{n-1}{j+1}} \leq \frac{b_j^2}{\binom{n-1}{j}^2}$$ or $$b_{j-1} b_{j+1} \leq \frac{j(n-j-1)}{(j+1)(n-j)} b_j^2 < b_j^2.$$ So $$0<\frac{b_{j+1}}{- b_j} < \frac{-b_j}{b_{j-1}}.$$

We must either have $$x_n > \tfrac{b_{j+1}}{- b_j}$$ or $$x_n < \tfrac{-b_j}{b_{j-1}}$$. In the first case, $$0 > x_n b_j + b_{j+1} = a_{j+1}$$; in the second case, $$a_j = x_n b_{j-1} + b_j < 0$$. Either way, we have found a negative $$a_j$$.

• This is very like a standard proof of Descartes' rule of signs, where one checks that multiplying by $f(t)$ by $t+a$ adds one sign alternation if $a<0$ and, if $a>0$ and all roots of $f$ are real, keeps the number of sign alternatations the same. I couldn't find this version of the proof quickly enough to link to though. Mar 7, 2022 at 15:17
• The equality $a_j=x_n b_{j-1}+b_j$ does not seem to be correct. E.g., when $j=2$ and $x_1=\cdots=x_{n-1}=0$, then $a_j=0\ne x_n^2=x_n b_{j-1}+b_j$ if $x_n<0$. Mar 7, 2022 at 16:34
• $a$'s and $b$'s switched from the first paragraph to the rest; try now. Mar 7, 2022 at 16:49
• Why can't $x_n$ be equal to $\frac{b_{j+1}}{- b_j}$ or $\frac{-b_j}{b_{j-1}}$? Mar 7, 2022 at 17:09
• Regarding my latter comment, it appears that the things can be fixed by a density-continuity argument, which allows one to assume that all the $a_j$'s and $b_j$'s are nonzero. Mar 7, 2022 at 18:37