golue3120 wrote:

Here, we have a solution without WLOG $k=n-1$ , without Descartes rule of signs, without Rolle, but is somehow not terrible?

Let $e_k$ denote the degree $k$ elementary symmetric polynomial.

Suppose for the sake of contradiction that all roots of $P(x)$ were real. Let the roots be $r_1,r_2,\dotsc,r_n$ . Let $R$ be the set of roots. Then for every subset $S$ of $k$ roots, $e_i(S)=0$ for some $1\le i\le k-1$ .

Define two subsets of $k$ elements to be adjacent if they share $k-1$ elements.
Lemma. If $\mathcal F$ is a family of $k$ -element subsets of $R$ such that no two are adjacent, then $|\mathcal F|\le\frac{1}{k+1}\binom nk$ .
Proof. Every set $T$ in $\mathcal F$ is adjacent to exactly $k(n-k)$ sets outside of $\mathcal F$ because we may pick any element of $T$ to remove and any root not in $T$ to add. Meanwhile, any set $U$ not in $\mathcal F$ is adjacent to at most $n-k$ sets in $\mathcal F$ because when we remove an element of $U$ and add a root not in $U$ , the additional roots for the adjacent sets in $\mathcal F$ must be distinct. Counting then gives the desired result.

Now define $\mathcal F_i$ to be the family of $k$ -element subsets of roots such that $e_i$ vanishes. Then there are $k-1$ such families, and every size $k$ subset of the roots is in at least one family, so one family must have size at least $\frac{1}{k-1}\binom nk$ . Therefore, at least one family must contain two adjacent subsets. This implies that there are roots $r_1,r_2,\dotsc,r_k,r_k'$ such that
$e_i(r_1,r_2,\dotsc,r_k)=e_i(r_1,r_2,\dotsc,r_{k-1},r_k')=0.$ Now we expand these by writing
$e_i(r_1,r_2,\dotsc,r_{k-1})+r_ke_{i-1}(r_1,r_2,\dotsc,r_{k-1})=e_i(r_1,r_2,\dotsc,r_{k-1})+r_k'e_{i-1}(r_1,r_2,\dotsc,r_{k-1})=0,$ and since $r_k\neq r_k'$ , we have
$e_i(r_1,r_2,\dotsc,r_{k-1})=e_{i-1}(r_1,r_2,\dotsc,r_{k-1})=0.$
Suppose that $\{r_1,r_2,\dotsc,r_{k-1}\}$ is a set of real numbers such that $e_i(r_1,r_2,\dotsc,r_{k-1})=e_{i-1}(r_1,r_2,\dotsc,r_{k-1})=0$ for some $i$ , but no strict subset has this property. It suffices to show that such a set cannot exist.

Now we perform a bit of further expansion
$e_i(r_1,r_2,\dotsc,r_{k-2})+r_{k-1}e_{i-1}(r_1,r_2,\dotsc,r_{k-2})=e_{i-1}(r_1,r_2,\dotsc,r_{k-2})+r_{k-1}e_{i-2}(r_1,r_2,\dotsc,r_{k-2})=0,$ from which we may deduce that
$e_i(r_1,r_2,\dotsc,r_{k-2})e_{i-2}(r_1,r_2,\dotsc,r_{k-2})=e_{i-1}(r_1,r_2,\dotsc,r_{k-2})^2.$
By minimality, none of $e_i$ , $e_{i-2}$ , or $e_{i-1}$ can vanish, for then two consecutive elementary symmetric polynomials must vanish. By "On the nonnegativity of generalized discriminants of quadratics",
$e_{i-1}(r_1,r_2,\dotsc,r_{k-2})^2\ge \frac{i(k-i)}{(i-1)(k-i-1)}e_i(r_1,r_2,\dotsc,r_{k-2})e_{i-2}(r_1,r_2,\dotsc,r_{k-2}).$ Since $e_{i-1}(r_1,r_2,\dotsc,r_{k-2})^2$ is strictly positive, we have a contradiction.

Wow. I spent around two hours in contest looking for an inequality-based approach to proving this but failed. Honestly, given the premise of the problem, I'm slightly surprised one exists. Is there any clean way to prove the inequality you cite? It looks like the terms could line up with some Cauchy-Schwartz / Sum of Squares approach, but I don't immediately see how to do it.
(I ultimately found the Descartes' Rule of Signs approach, so fortunately I avoided a crisis.

)