## Thursday, January 26, 2006

### Nonnegativity. Topic: Algebra/Polynomials. Level: Olympiad.

Problem: (Olympiad Problem Solving MidTerm) Let $p(x)$ be a polynomial that is nonnegative for all real $x$. Prove that for some $k$, there are polynomials $f_1(x), . . . , f_k(x)$ such that

$\displaystyle p(x) = \sum_{j=1}^k (f_j(x))^2$.

Solution: First we will make some restrictions on $p$, namely that it has an even degree and a positive coefficient on the highest-order term. If it has an odd degree take $x \rightarrow \pm \infty$ and we get $p(x) \rightarrow -\infty$ for one of the cases which is a contradiction. Similarly, if it has a negative coefficient on the highest-order term, take $x \rightarrow \infty$ so again $p(x) \rightarrow -\infty$. In both these cases, $p$ cannot be nonnegative for all real $x$.

Next, we will proceed by strong induction on the degree of $p$.

Base case: $deg(p) = 0$. Then $p(x) = a = (\sqrt{a})^2$.

Then suppose the condition is satisfied for $deg(p) = 0, \ldots, 2n$. We will show that it must also hold for $deg(p) = 2n+2$.

Denote $m = min(p(x))$ over all reals $x$. Since $p$ is nonnegative, $m \ge 0$.

Consider the polynomial $f(x) = p(x)-m$, which is still nonnegative and of degree $2n+2$. For some value of $x$, $f(x) = 0$ because $p(x) = m$ at some point. Let that value be $x_0$ (just take one of them; there might be more). The multiplicity at $x_0$ must be even because if it was odd then $f$ would go negative for some $x > x_0$. Let the multiplicity at $x_0$ be $2b > 0$.

So we have $f(x) = (x-x_0)^{2b}g(x)$ for some $g(x)$. We note that $g(x)$ is nonnegative as well because $(x-x_0)^{2b}$ is nonnegative and $f(x)$ would be negative if $g(x)$ was negative anywhere, a contradiction. By our original restrictions, $deg(g)$ is even. However, that means $g(x)$ is a nonnegative polynomial with $deg(g) < deg(f) = 2n+2$ so $g$ must be expressible in the form $\displaystyle g(x) = \sum_{j=1}^{k_1} (f_j(x))^2$ for some $k_1$ by our inductive hypothesis.

Then $\displaystyle p(x) = f(x)+m = (x-x_0)^{2b}g(x)+m = \sum_{j=1}^{k_1} [(x-x_0)^bf_j(x)]^2 + (\sqrt{m})^2$, completing the induction. QED.

--------------------

Comment: A pretty fun, semi-difficult problem. I tried a few failed approaches before reaching this cool one, including getting rid of higher order terms first and reducing it to a lower degree polynomial which employs the same general idea but fails in some cases. Another way to do this problem (from the solutions guide) is simply to factor the polynomial into linear and quadratic terms, show that each linear term has even multiplicity and use the sum of squares product formula on the quadratic terms - $(a^2+b^2)(c^2+d^2) = (ac+bd)^2+(ad-bc)^2$. This actually proves a stronger result, that each nonnegative polynomial $p$ can be written as the sum of the squares of two other polynomials.

--------------------

Practice Problem: (Olympiad Problem Solving MidTerm) Find a polynomial in more than one variable that is always nonnegative that cannot be written as the sum of squares.