Title: Hilbert’s Seventeenth Problem
Abstract: If p is a real polynomial in n variables, then p is “psd" if it only takes non-negative values, and p is sos if it can be written as a sum of squares of real polynomials. Every sos polynomial is psd, and for small values of n and the degree, every psd polynomial is sos. In 1888, Hilbert proved that there exist psd polynomials which are not sos, and in 1900 asked whether every psd polynomial is a sum of squares of rational functions (he had proved this for n=2). Artin gave a non-constructive proof in the 1920s using the theory of real algebra, which he had developed.
No explicit polynomials which are psd and not sos were constructed until the late 1960s (by Motzkin and R. Robinson), and they are surprisingly simple. Choi and Lam started a systematic study of "psd and sos" in the mid 1970s and I joined them a few years later. We developed a natural algorithm for determining whether p is sos. Around 2000, Parrilo realized that this algorithm can be made to work in polynomial time (whereas determining whether p is psd is NP-hard.) Recent contributions have been made by Blekherman and others. These questions are now considered part of computational real algebraic geometry.
This talk should be accessible to graduate students; all techniques are elementary or hand-waved. There will be more historical stories than proofs.
