Positive-definite Polynomial Game

Given $n$ a positive even number. Alice and Bob are playing a game as follows. On the board initially there are $n+1$ unassigned numbers: $a_0, a_1, \dots, a_n$.

With Alice going first, each player alternatingly chooses an unassigned number and assigns a positive real value to it. Once all numbers have been assigned values, polynomial $P(x)$ is defined as:

$$P(x) = a_nx^n + \dots + a_1x +a_0$$

If $P(x) > 0$ for all $x \in R$ then Alice wins, otherwise Bob wins. Determine who has a winning strategy.

Variant 1: if the number $a_0$ is already fixed to 1, so there are only $n$ numbers on the board, who has a winning strategy?

Variant 2: if the winning condition is flipped: Alice wins if there exists an $x$ such that $P(x) < 0$.

Solution

The player who moves last has a winning strategy, regardless of winning condition. Variant 1 merely flips who moves last. If Variant 1 is in play and Alice moves first, then Bob moves last and Bob has a winning strategy. Note that $P(x)$ is positive definite iff $tP(x)$ for all $t$ positive numbers, so the magnitude of each number doesn't matter, only the relative magnitude of all coefficients. Therefore, the number "1" set by variant 1 is arbitrary and the variant merely ensures Bob's ability to win. For the rest of this solution, we assume that variant 1 is not in play and Alice goes first, and she should assign $a_0 = 1$. The rest of the proof can then be extensible to variant 1 while flipping the name Alice and Bob.

Lemma: polynomial $P(x)$ with positive coefficients are positive definite if and only if $P(1/x) > 0$ for all $x \neq 0$. This lemma is easy to see because $P(0) > 0$ anyways.

Part 1: proving that Alice can ensure positive definiteness.

Assume that $a_0 = 1$ has already been assigned. Now divide the remaining coefficients into pairs: $(a_1,a_2), (a_3,a_4), \dots, (a_{n-1},a_n)$. Whenever Bob makes a move and assigns a value to a coefficient, Alice assigns a value to its pair accordingly. We claim that Alice will be able to choose her value such that the resulting polynomial $Q_k(x) = a_{2k}.x^{2k} + a_{2k-1}.x^{2k-1} + 2/n$ is positive definite.

Proof: From the lemma, $Q_k$ is positive definite iff $R_k(x) = \frac{2}{n}x^{2k} + a_{2k-1}x + a_{2k}$ is positive definite.

If Bob chooses $a_{2k-1}$ then Alice can choose $a_{2k}$ large enough to make $R_k(x)$ positive definite. Whichever local minimum may exist due to Bob's choice, Alice can compensate it enough by adding a positive constant term to the whole polynomial.

If Bob chooses $a_{2k}$ then there exists an $a_{2k-1}$ small enough to make $R_k(x)$ positive definite. If $x \geq 0$ positive then $R_k(x) > 0$ because all coefficients are positive. But if $x < 0$ then by AM-GM:

$$ \frac{2}{n}x^{2k} + a_{2k} = \frac{2}{n}x^{2k} + \frac{a_{2k}}{2k-1} + \dots + \frac{a_{2k}}{2k-1} \geq 2k \sqrt[2k]{\frac{2}{n}.\left(\frac{a_{2k}}{2k-1}\right)^{2k-1}}.(-x) > -a_{2k-1}x$$

for small enough positive value of $a_{2k-1}$.

The final polynomial can be expressed as the sum:$P = Q_1 + \dots + Q_{n/2}$, and because at each step Alice can always ensure that the resulting $Q_k(x)$ is positive definite no matter what Bob chooses, then the final polynomial is also guaranteed to be positive definite.

Part 2: proving that Alice can ensure non-positive definiteness.

If $n=2$ then Alice can always ensure that the discriminant of the quadratic polynomial is positive, therefore the polynomial has two real roots. For $n > 2$, the general strategy is as follows: divide the coefficients into pairs as above, and Alice's assignment is always the pair of Bob's assignment as well. But this time the difference is that, after each of her move, Alice ensures that the TOTAL polynomial $P(x)$ is negative for some values of $x$ and maintains this invariant throughout the game.

First note that if Bob ever chooses an even coefficient $a_2,a_4,\dots$ then Alice's job is really easy. Take the current value of $P(-1)$ (after including Bob's addition), and by choosing her corresponding odd coefficient large enough, she can make $P(-1)$ negative because she's adding a multiple of $x^{2k-1}$ which is negative at $x=-1$.

Consider the first round. If Bob chooses $a_{2k}$ then Alice chooses large enough $a_{2k-1}$ as described above. But if Bob chooses $a_{2k-1}$, Alice can choose small enough $a_{2k}$ to ensure non-positive definiteness. The current resulting polynomial is $a_{2k-1}x^{2k-1}+1 < 0$ as $x \to -\infty$, so pick any $y$ such that $a_{2k-1}y^{2k-1}+1 < 0$. Then Alice chooses $a_{2k}$ small enough such that $0 < a_{2k} < \frac{-a_{2k-1}y^{2k-1}-1}{y^{2k}}$ so that $a_{2k}y^{2k}+a_{2k-1}y^{2k-1}+1 < 0$

So once the invariant is established after the first round, then Bob has no choice but to keep choosing even coefficients. If Bob chooses an odd coefficient, then whichever value of $x$ caused $P(x)$ to be negative at the end of last round will continue to be (even more) negative, so Alice simply chooses a very small value of the corresponding even coefficient as described above. But even if Bob chooses an even coefficient, Alice can counter by choosing a large enough odd coefficient. Therefore she maintains the invariant of $P$ being non-positive definite until the end of the game.