Putnam 1999, Problem A-2

Let \(p(x)\) be a polynomial that is nonnegative for all real \(x\). Prove that for some \(k\), there are polynomials \(f_1(x), \ldots, f_k(x)\) such that
\[
p(x) = \sum_{j=1}^k (f_j(x))^2.
\]

Solution:
First solution: First factor $p(x) = q(x)r(x)$, where $q$ has all real roots and $r$ has all complex roots. Notice that each root of $q$ has even multiplicity, otherwise $p$ would have a sign change at that root. Thus $q(x)$ has a square root $s(x)$.

Now write $r(x) = \prod_{j=1}^k (x-a_j)(x-\overline{a_j})$ (possible because $r$ has roots in complex conjugate pairs). Write $\prod_{j=1}^k (x-a_j) = t(x) + iu(x)$ with $t,x$ having real coefficients. Then for $x$ real,
$$p(x) = q(x)r(x)$$
$$= s(x)^2(t(x) + iu(x))\overline{(t(x) + iu(x))}$$
$$= (s(x)t(x))^2 + (s(x)u(x))^2.$$

(Alternatively, one can factor $r(x)$ as a product of quadratic polynomials with real coefficients, write each as a sum of squares, then multiply together to get a sum of many squares.)

Second solution: We proceed by induction on the degree of $p$, with base case where $p$ has degree 0. As in the first solution, we may reduce to a smaller degree in case $p$ has any real roots, so assume it has none. Then $p(x) > 0$ for all real $x$, and since $p(x) \to \infty$ for $x \to \pm\infty$, $p$ has a minimum value $c$. Now $p(x) - c$ has real roots, so as above, we deduce that $p(x) - c$ is a sum of squares. Now add one more square, namely $(\sqrt{c})^2$, to get $p(x)$ as a sum of squares.