# Mathematical Food for Thought

Serves a Daily Special and an All-You-Can-Eat Course in Problem Solving. Courtesy of me, Jeffrey Wang.

• ## Meta

Nonnegativity. Topic: Algebra/Polynomials. Level: Olympiad. January 27th, 2006

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

.

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

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

Base case: . Then .

Then suppose the condition is satisfied for . We will show that it must also hold for .

Denote over all reals . Since is nonnegative, .

Consider the polynomial , which is still nonnegative and of degree . For some value of , because at some point. Let that value be (just take one of them; there might be more). The multiplicity at must be even because if it was odd then would go negative for some . Let the multiplicity at be .

So we have for some . We note that is nonnegative as well because is nonnegative and would be negative if was negative anywhere, a contradiction. By our original restrictions, is even. However, that means is a nonnegative polynomial with so must be expressible in the form for some by our inductive hypothesis.

Then , 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 – . This actually proves a stronger result, that each nonnegative polynomial 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.

### 4 Responses to “Nonnegativity. Topic: Algebra/Polynomials. Level: Olympiad.”

1. Matt Says:

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

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. QC Says:

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