Hilbert's seventeenth problem

From HandWiki
Short description: Expression of polynomials as sum of squares

Hilbert's seventeenth problem is one of the 23 Hilbert 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.

Motivation

Main page: Polynomial SOS

The formulation of the question takes into account that there are non-negative polynomials, for example[1]

[math]\displaystyle{ f(x,y,z)=z^6+x^4y^2+x^2y^4-3x^2y^2z^2, }[/math]

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.[2] Hilbert's proof did not exhibit any explicit counterexample: only in 1967 the first explicit counterexample was constructed by Motzkin.[3] 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.[4]

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:

Any homogeneous polynomial of degree 2d and n variables can be represented as sum of squares? 2d (Degree) Any polynomial of degree 2d and n variables can be represented as sum of squares? 2d (Degree)
2 4 ≥6 2 4 ≥6
n (Number of variables) 1 Yes Yes Yes n (Number of variables) 1 Yes Yes Yes
2 Yes Yes Yes 2 Yes Yes No
3 Yes Yes No 3 Yes No No
≥4 Yes No No ≥4 Yes No No

Solution and generalizations

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

Dubois showed in 1967 that the answer is negative in general for ordered fields.[10] In this case one can say that a positive polynomial is a sum of weighted squares of rational functions with positive coefficients.[11] 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. Mckenna K. New facts about Hilbert's 17th problem. Lecture Notes in Math, 498, Berlin, New York: Springer-Verlag, 1975, 220-230.

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[12] and Procesi, Schacher,[13] with an elementary proof given by Hillar and Nie.[14]

Minimum number of square rational terms

It is an open question what is the smallest number

[math]\displaystyle{ v(n,d), }[/math]

such that any n-variate, non-negative polynomial of degree d can be written as sum of at most [math]\displaystyle{ v(n,d) }[/math] square rational functions over the reals.

The best known result ((As of 2008)) is

[math]\displaystyle{ v(n,d)\leq2^n, }[/math]

due to Pfister in 1967.[8]

On the other hand, 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, [math]\displaystyle{ v(n,d) = 2^{\Omega(n)} }[/math].

In complex analysis the Hermitian analogue, requiring the squares to be squared norms of holomorphic mappings, is somewhat more complicated, but true for positive polynomials by a result of Quillen.[15] The result of Pfister on the other hand fails in the Hermitian case, that is there is no bound on the number of squares required, see D'Angelo–Lebl.[16]

See also

Notes

  1. ↑ Marie-Françoise Roy. The role of Hilbert's problems in real algebraic geometry. Proceedings of the ninth EWM Meeting, Loccum, Germany 1999
  2. ↑ Hilbert, David (September 1888). "Ueber die Darstellung definiter Formen als Summe von Formenquadraten". Mathematische Annalen 32 (3): 342–350. doi:10.1007/bf01443605. https://zenodo.org/record/1428214. 
  3. ↑ Motzkin, T. S. (1967). "The arithmetic-geometric inequality". in Shisha, Oved. Inequalities. Academic Press. pp. 205–224. 
  4. ↑ Blekherman, Grigoriy (2006). "There are significantly more nonegative polynomials than sums of squares" (in en). Israel Journal of Mathematics 153 (1): 355–380. doi:10.1007/BF02771790. ISSN 0021-2172. 
  5. ↑ Hilbert, David (December 1893). "Über ternäre definite Formen". Acta Mathematica 17 (1): 169–197. doi:10.1007/bf02391990. https://zenodo.org/record/1428402. 
  6. ↑ Artin, Emil (1927). "Über die Zerlegung definiter Funktionen in Quadrate". Abhandlungen aus dem Mathematischen Seminar der Universität Hamburg 5 (1): 100–115. doi:10.1007/BF02952513. 
  7. ↑ Delzell, C.N. (1984). "A continuous, constructive solution to Hilbert's 17th problem". Inventiones Mathematicae 76 (3): 365–384. doi:10.1007/BF01388465. Bibcode: 1984InMat..76..365D. 
  8. ↑ 8.0 8.1 Pfister, Albrecht (1967). "Zur Darstellung definiter Funktionen als Summe von Quadraten" (in German). Inventiones Mathematicae 4 (4): 229–237. doi:10.1007/bf01425382. Bibcode: 1967InMat...4..229P. 
  9. ↑ Lam (2005) p.391
  10. ↑ Dubois, D.W. (1967). "Note on Artin's solution of Hilbert's 17th problem". Bull. Am. Math. Soc. 73 (4): 540–541. doi:10.1090/s0002-9904-1967-11736-1. 
  11. ↑ Lorenz (2008) p.16
  12. ↑ Gondard, Danielle; Ribenboim, Paulo (1974). "Le 17e problème de Hilbert pour les matrices". Bull. Sci. Math. (2) 98 (1): 49–56. 
  13. ↑ Procesi, Claudio; Schacher, Murray (1976). "A non-commutative real Nullstellensatz and Hilbert's 17th problem". Ann. of Math.. 2 104 (3): 395–406. doi:10.2307/1970962. 
  14. ↑ Hillar, Christopher J.; Nie, Jiawang (2008). "An elementary and constructive solution to Hilbert's 17th problem for matrices". Proc. Am. Math. Soc. 136 (1): 73–76. doi:10.1090/s0002-9939-07-09068-5. 
  15. ↑ Quillen, Daniel G. (1968). "On the representation of hermitian forms as sums of squares". Invent. Math. 5 (4): 237–242. doi:10.1007/bf01389773. Bibcode: 1968InMat...5..237Q. 
  16. ↑ D'Angelo, John P.; Lebl, Jiri (2012). "Pfister's theorem fails in the Hermitian case". Proc. Am. Math. Soc. 140 (4): 1151–1157. doi:10.1090/s0002-9939-2011-10841-4. 

References

  • Pfister, Albrecht (1976). "Hilbert's seventeenth problem and related problems on definite forms". in Felix E. Browder. Mathematical Developments Arising from Hilbert Problems. Proceedings of Symposia in Pure Mathematics. XXVIII.2. American Mathematical Society. pp. 483–489. ISBN 0-8218-1428-1. 
  • Lam, Tsit-Yuen (2005). Introduction to Quadratic Forms over Fields. Graduate Studies in Mathematics. 67. American Mathematical Society. ISBN 0-8218-1095-2. 
  • Lorenz, Falko (2008). Algebra. Volume II: Fields with Structure, Algebras and Advanced Topics. Springer-Verlag. pp. 15–27. ISBN 978-0-387-72487-4. 
  • Rajwade, A. R. (1993). Squares. London Mathematical Society Lecture Note Series. 171. Cambridge University Press. ISBN 0-521-42668-5. 



Retrieved from "https://handwiki.org/wiki/index.php?title=Hilbert%27s_seventeenth_problem&oldid=3385245"