https://arxiv.org/abs/1010.3465
(G.Blekherman. Nonnegative Polynomials and Sums of Squares)

«It is a central question in real algebraic geometry, whether a non-negative polynomial can be written in a way that makes its nonnegativity apparent, i.e. as a sum of squares of polynomials (or more general objects). Algorithms to obtain such representations, when they are known, have many applications in polynomial optimization [9],[10],[11].

The investigation of the relation between nonnegativity and sums of squares began in the seminal paper of Hilbert from 1888. Hilbert showed that every nonnegative polynomial is a sum of squares of polynomials only in the following 3 cases: univariate polynomials, quadratic polynomials and bivariate polynomials of degree 4. In all other cases Hilbert showed existence of nonnegative polynomials that are not sums of squares. Hilbert’s proof used the fact that polynomials of degree d satisfy linear relations, known as the Cayley-Bacharach relations, which are not satisfied by polynomials of full degree 2d [14],[15].

Hilbert then showed that every bivariate nonnegative polynomial is a sum of squares of rational functions and Hilbert’s 17th problem asked whether this is true in general. In 1920’a Artin and Schreier solved Hilbert’s 17th problem in the affirmative. However, there is no known algorithm to obtain this representation. In particular we may need to use numerators and denominators of very large degree, thus representing a simple object (the polynomial) as a sum of squares of significantly more complex objects [3].

It should be noted that Hilbert did not provide an explicit nonnegative polynomial that is not a sum of squares of polynomials, he only proved its existence. The first explicit example appeared only eighty years later and is due to Motzkin. Since then many explicit examples of nonnegative polynomials that are not sums of squares have appeared [14].»