gistfile1.txt

Every time we say 'polynomial' we will mean a polynomial with real coefficients. 

Suppose f is a polynomial that is everywhere non-negative, i.e. f(x) >= 0 for all x.

We may assume f is monic. Indeed, we can divide by any positive number
without changing the matter, and after such normalization the leading
coefficient cannot be -1 or f would assume negative values for large enough x. 

First suppose f factors completely into linear parts:

    f(x) = (x - a_1)^n_1 ... (x - a_m)^n_m

When x crosses some a_i, the sign of f is multiplied by (-1)^n_i and hence
changes if and only if n_i is odd. Therefore the only way for f to never 
have any sign changes is for every n_i to be even, which implies f is square:

    f(x) = ((x - a_1)^(n_1 / 2) ... (x - a_m)^(n_m / 2))^2

More generally, f may also have irreducible quadratic factors of the form
x^2 - 2bx + c. A translation by b eliminates the linear term and gives us 
the reduced quadratic x^2 + d for d = c + b^2. This is non-negative if and
only if d >= 0. But in that case d has a real square root, so we see that
the reduced quadratic is a sum of the squares x^2 and sqrt(d)^2. Undoing the
reduction, we have x^2 - 2bx + c = (x - b)^2 + sqrt(c + b^2)^2. 

As we have already characterized products of linear polynomials as squares, and a
square is just a sum of two squares where the other square is zero, we should
investigate what happens when sums of two squares are multiplied. Fibonacci's identity
from number theory tells us that these products are also sums of two squares! That is,
sums of two squares are closed under multiplication. This is typically seen as an
identity for integers but it actually applies over any commutative ring, including
our ring of real polynomials. (The deeper reason for the identity is the existence
of the multiplicative norm for complex numbers.)

This finally gives us our characterization:

A polynomial is non-negative if and only if it is a sum of two squares.