Hilbert's seventeenth problem

Hilbert's seventeenth problem is one of the 23 of Hilbert's problems set out in a celebrated list compiled in 1900 by David Hilbert.

Uses your system voice; voice and rate in settings.

Snapshot

≈ 4 min read

Names in other languages

No names in other languages are held for this entry yet.

Article bodies are English and are not machine-translated. A name in another language is not a translation of the article.

Hilbert's seventeenth problem is one of the 23 of Hilbert's problems set out in a celebrated list compiled in 1900 by David Hilbert. It concerns the expression of positive definite rational functions as sums of quotients of squares.

The original question may be reformulated as: * Given a multivariate polynomial that takes only non-negative values over the reals, can it be represented as a sum of squares of rational functions? Hilbert's question can be restricted to homogeneous polynomials of even degree, since a polynomial of odd degree changes sign, and the homogenization of a polynomial takes only nonnegative values if and only if the same is true for the polynomial.

Hilbert's seventeenth problem is one of the 23 of Hilbert's problems set out in a celebrated list compiled in 1900 by David Hilbert. It concerns the expression of positive definite rational functions as sums of quotients of squares.

The original question may be reformulated as: Given a multivariate polynomial that takes only non-negative values over the reals, can it be represented as a sum of squares of rational functions? Hilbert's question can be restricted to homogeneous polynomials of even degree, since a polynomial of odd degree changes sign, and the homogenization of a polynomial takes only nonnegative values if and only if the same is true for the polynomial. f(x,y,z)=z^6+x^4y^2+x^2y^4-3x^2y^2z^2, which cannot be represented as a sum of squares of other polynomials.

In 1888, Hilbert showed that every non-negative homogeneous polynomial in n variables and degree 2d can be represented as sum of squares of other polynomials if and only if either (a) n = 2 or (b) 2d = 2 or (c) n = 3 and 2d = 4. Hilbert's proof did not exhibit any explicit counterexample: only in 1967 the first explicit counterexample was constructed by Motzkin.

Furthermore, if the polynomial has a degree 2d greater than two, there are significantly many more non-negative polynomials that cannot be expressed as sums of squares. The following table summarizes in which cases every non-negative homogeneous polynomial (or a polynomial of even degree) can be represented as a sum of squares: The particular case of n = 2 was already solved by Hilbert in 1893.

The general problem was solved in the affirmative, in 1927, by Emil Artin, for positive semidefinite functions over the reals or more generally real-closed fields. An algorithmic solution was found by Charles Delzell in 1984. A result of Albrecht Pfister shows that a positive semidefinite form in n variables can be expressed as a sum of 2 n squares.

Dubois showed in 1967 that the answer is negative in general for ordered fields. In this case one can say that a positive polynomial is a sum of weighted squares of rational functions with positive coefficients.

McKenna showed in 1975 that all positive semidefinite polynomials with coefficients in an ordered field are sums of weighted squares of rational functions with positive coefficients only if the field is dense in its real closure in the sense that any interval with endpoints in the real closure contains elements from the original field. A generalization to the matrix case (matrices with polynomial function entries that are always positive semidefinite can be expressed as sum of squares of symmetric matrices with rational function entries) was given by Gondard, Ribenboim and Procesi, Schacher, with an elementary proof given by Hillar and Nie.

In complex analysis and complex geometry, the Hermitian analogue, requiring the squares to be squared norms of holomorphic polynomials, was proven for strictly positive polynomials by Quillen using techniques based on elliptic partial differential equations. The sum-of-squares representation is unique if it exists, which was first observed by Putinar in the context of optimization.

In the other direction, a conditional lower bound can be derived from computational complexity theory. An n-variable instance of 3-SAT can be realized as a positivity problem on a polynomial with n variables and d=4. This proves that positivity testing is NP-hard.

More precisely, assuming the exponential time hypothesis to be true, v(n,d) = 2^{\Omega(n)} . The result of Pfister fails in the Hermitian case, that is there is no bound on the number of squares required, see D'Angelo–Lebl.

See also

Krivine–Stengle Positivstellensatz Polynomial SOS Positive polynomial Sum-of-squares optimization SOS-convexity

Text derived from https://en.wikipedia.org/w/index.php?oldid=1369579819 under CC BY-SA 4.0; modifications have been made.

Sources cited in this revision

3 named source(s) extracted from the cited revision. A source with no author is shown by its publication; nothing is invented.