How to write a polynomial as a sum of squares of polynomials, and why you'd want to do so

Professor Bruce Reznick, Department of Mathematics, University of Illinois

One of the fundamental questions one can ask about a real polynomial is whether it only takes non-negative values; such a polynomial is called {\it psd}. Both pure and applied mathematicians frequently wish to know whether a particular polynomial is psd. If a polynomial can be written as a sum of squares of polynomials -- such a polynomial is called {\it sos} -- then it is evidently psd. For polynomials in one variable or quadratic forms, these two conditions coincide, but in 1888, David Hilbert showed that there exist more complicated psd polynomials in more variables and higher degree which are not sos.

The 17th of Hilbert's famous list of 23 problems asked the variant question of whether every psd polynomial is a sum of squares of rational functions. Artin answered affirmatively in the 1920s, though with an abstract proof that gives no hint of how one might find such a representation. And Hilbert's original example was cast in the difficult language of 19th century curve theory, and did not attract much interest until the mid 60s.

In the mid-60s, Theodore S. Motzkin and Raphael M. Robinson independently found separate simplifications of Hilbert's example, which then brought new light onto the subject. Their examples are: $$ \gather M(x,y) = x^4y^2 + x^2y^4 + 1 - 3x^2y^2, \\ R(x_1,x_2,x_3) = \sum_{i=1}^3 x_i^6 - \sum_{i \neq j} x_i^4x_j^2 + 3x_1^2x_2^2x_3^2. \endgather $$ The proofs that these are psd and not sos come from ``The Book", in the sense of Erd\"os.

This talk will discuss the work of M.D. Choi, T.Y. Lam, Pablo Parrilo, the speaker and others, done over the last 25 years. We now know an effective algorithm for determining whether a given psd polynomial is sos. We also have an explicit formula for writing a psd polynomial without zeros as a sum of squares of rational functions. The talk will be expository, go lightly on abstraction and present many concrete examples.