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.


  1. Quick question. What is the difference between induction and strong induction? Or are they the same and strong induction just sounds cooler?

  2. Regular Induction - showing that case k+1 follows from case k.

    Strong Induction - showing that case k+1 follows from cases 1 through k.

    They are similar, but strong induction uses a stronger hypothesis, as the name suggests. For instance, in this problem, I had to use strong induction because g(x) could be ANY even degree less than 2n+2. If I could show that the degree of g(x) had to be 2n, then regular induction would've sufficed.

  3. P(x) = 3(xy)^2 + 3? Can't be that easy. Or do you mean real coefficients rather than integer/rational?

  4. Uhh... P(x) = 3(xy)^2+3 = (xy)^2+(xy)^2+(xy)^2+3... So that doesn't work, maybe you read the question wrong. And it's real coefficients.