Kvant Math Problem 1444
Consider polynomials with a negative coefficient, such as $P(x) = -x + 2$ or $P(x) = x^2 - x + 1$.
Verified: no
Verdicts: SKIP + SKIP
Solve time: 7m19s
Source on kvant.digital
Problem
Does there exist a polynomial $P(x)$ that has a negative coefficient, while all the coefficients of any of its powers $P^n(x)$, $n\gt1$ are positive?
O. Kryzhanovsky
Moscow Mathematical Olympiad (LVII, 1994)
Exploration
Consider polynomials with a negative coefficient, such as $P(x) = -x + 2$ or $P(x) = x^2 - x + 1$. Calculating low powers quickly shows that negative coefficients propagate: for $P(x) = -x + 2$, the square is $P^2(x) = (-x + 2)^2 = x^2 - 4x + 4$, which still has a negative coefficient. Trying to compensate by adding larger positive terms, such as $P(x) = x^2 + 3x - 1$, the square is $P^2(x) = x^4 + 6x^3 + 7x^2 - 6x + 1$, which retains a negative coefficient. Testing $P(x) = -1 + x + x^2$ gives $P^2(x) = 1 - 2x + 3x^2 + 2x^3 + x^4$, again a negative term persists.
Small-degree examples suggest that a single negative coefficient in $P(x)$ leads to at least one negative coefficient in $P^2(x)$. The intuition is that multiplication distributes the negative contribution across terms, and the initial negativity cannot be fully absorbed by positive coefficients of other terms. This suggests the problem may be impossible, and a general argument must show that for any polynomial with at least one negative coefficient, some power will always retain a negative coefficient.
The crucial difficulty is proving this for arbitrary degree and arbitrary coefficient combinations, particularly when the negative coefficient is small in magnitude compared to positive coefficients. Any careless summation could overlook a cancellation that would produce an entirely positive power, so each step must carefully trace which terms contribute to each coefficient in the powers.
Problem Understanding
The problem asks whether there exists a polynomial $P(x)$ with at least one negative coefficient such that for all integers $n > 1$, every coefficient of $P^n(x)$ is positive. This is a Type D problem: "Construct / Show there exists," or prove impossibility if none exists. The core difficulty is that negative contributions multiply and combine in the expansion of powers, potentially leaving negative coefficients. Exploration strongly suggests that no such polynomial exists because a negative coefficient in $P(x)$ inevitably produces a negative coefficient in some higher power. Intuitively, multiplication spreads the negative influence and cannot be fully canceled by other positive terms without fine-tuned coefficients, which appear impossible for all $n>1$.
Proof Architecture
Lemma 1: If $P(x)$ has a negative coefficient, then its lowest-degree term with a negative coefficient is strictly positive in its degree contribution after any positive power. Sketch: Track the contribution of the negative term in the lowest-degree monomial of each $P^n(x)$.
Lemma 2: Any polynomial with a negative coefficient will produce a negative coefficient in some power $P^n(x)$, $n > 1$. Sketch: Consider the minimal and maximal degrees where the negative coefficient appears; their convolution with other terms in expansion always produces a negative coefficient eventually.
Main Claim: No polynomial $P(x)$ exists with a negative coefficient such that $P^n(x)$ has all positive coefficients for all $n > 1$. Sketch: Apply Lemma 2; any negative term in $P$ cannot disappear in all powers.
Hardest step: Lemma 2, showing negative coefficients inevitably survive some power.
Solution
Assume for contradiction that there exists a polynomial $P(x)$ with at least one negative coefficient, and that for all $n>1$, $P^n(x)$ has only positive coefficients. Write $P(x) = a_0 + a_1 x + \dots + a_m x^m$ with integer $m \ge 0$, and let $k$ be the smallest index such that $a_k < 0$. Then $a_0, \dots, a_{k-1} \ge 0$, and $a_k < 0$.
Consider $P^2(x) = P(x) \cdot P(x)$. The coefficient of $x^k$ in $P^2(x)$ is
$$\sum_{i=0}^k a_i a_{k-i}.$$
All terms with $i < k$ have $a_i \ge 0$ and $a_{k-i} \ge 0$ unless $k-i = k$, which occurs only for $i=0$ giving $a_0 a_k \le 0$. The term $i = k$ contributes $a_k a_0 < 0$, and terms with $0 < i < k$ are nonnegative. Hence the sum is $a_0 a_k + (\text{nonnegative terms}) \le a_0 a_k < 0$. Therefore, the coefficient of $x^k$ in $P^2(x)$ is negative, contradicting the assumption that all coefficients of $P^2(x)$ are positive.
This argument applies equally for any $n > 1$: the lowest-degree term with a negative coefficient in $P(x)$ propagates to $P^n(x)$, producing a negative coefficient. Therefore, no polynomial with a negative coefficient can have all positive coefficients in all powers $n > 1$.
This completes the proof.
∎
Verification of Key Steps
The delicate step is identifying the coefficient of $x^k$ in $P^2(x)$. Compute explicitly: let $P(x) = a_0 + \dots + a_m x^m$ with $k$ minimal such that $a_k < 0$. Then $x^k$ in $P^2(x)$ comes from $a_i a_{k-i}$, $i = 0, \dots, k$. Since $a_0, \dots, a_{k-1} \ge 0$, only $a_0 a_k$ and $a_k a_0$ are negative. All other contributions are nonnegative. Adding these gives a negative sum. Testing small examples, e.g., $P(x) = 2 - x + x^2$, gives $P^2(x) = 4 - 4x + 5x^2 - 2x^3 + x^4$, where the $x$ coefficient is negative, confirming the reasoning.
Alternative Approaches
An alternative is to consider the generating function approach, viewing coefficients as sums over multisets of indices corresponding to products in the expansion of powers. The negative coefficient in $P(x)$ produces a negative term in every multiset containing it, ensuring some negative coefficient survives. The direct minimal-degree argument is preferable for clarity and minimal technical overhead, avoiding combinatorial explosion and making the proof fully elementary.