Around Hilbert’s 17th Problem

Konrad Schmüdgen

2010 Mathematics Subject Classification: 14P10

Keywords and Phrases: Positive polynomials, sums of squares

The starting point of the history of Hilbert’s 17th problem was the oral defense of the doctoral dissertation of Hermann Minkowski at the University of Königsberg in 1885. The 21 year old Minkowski expressed his opinion that there exist real polynomials which are nonnegative on the whole ℝ^{n} and cannot be written as finite sums of squares of real polynomials. David Hilbert was an official opponent in this defense. In his “Gedächtnisrede” [6] in memorial of H. Minkowski he said later that Minkowski had convinced him about the truth of this statement. In 1888 Hilbert proved in a now famous paper [4] the existence of a real polynomial in two variables of degree six which is nonnegative on ℝ^{2} but not a sum of squares of real polynomials. Hilbert’s proof used some basic results from the theory of algebraic curves. Apart from this his construction is completely elementary. The first explicit example of this kind was given by T. Motzkin [10] only in 1967. It is the polynomial

M(x, y) = x^{4}y^{2} + x^{2}y^{4} + 1 − 3x^{2}y^{2}.

(Indeed, the arithmetic-geometric mean inequality implies that M ≥ 0 on ℝ^{2}. Assume to the contrary that M = ∑_{j} f_{j}^{2} is a sum of squares of real polynomials. Since M(0, y) = M(x, 0) = 1, the polynomials f_{j}(0, y) and f_{j}(x, 0) are constants. Hence each f_{j} is of the form f_{j} = a_{j} + b_{j}xy + c_{j}x^{2}y + d_{j}xy^{2}. Then the coefficient of x^{2}y^{2} in the equality M = ∑_{j} f_{j}^{2} is equal to −3 = ∑_{j} b_{j}^{2}. This is a contradiction.)

A nice exposition around Hilbert’s construction and many examples can be found in [16]. Hilbert also showed in [4] that each nonnegative polynomial in two variables of degree four is a finite sum of squares of polynomials.

As usual we denote by ℝ[x_{1}, …, x_{n}] and ℝ(x_{1}, …, x_{n}) the ring of polynomials resp. the field of rational functions in x_{1}, …, x_{n} with real coefficients.

The second pioneering paper [5] of Hilbert about this topic appeared in 1893. He proved by an ingenious and difficult reasoning that each nonnegative polynomial p ∈ ℝ[x, y] on ℝ^{2} is a finite sum of squares of rational (!) functions from ℝ(x, y). Though not explicitly stated therein a closer look at Hilbert’s proof shows even that p is a sum of four squares. For Motzkin’s polynomial one has the identity

M(x, y) = \frac{x^{2}y^{2}(x^{2} + y^{2} + 1)(x^{2} + y^{2} − 2)^{2} + (x^{2} − y^{2})^{2}}{(x^{2} + y^{2})^{2}}

which gives a representation of M as a sum of four squares of rational functions.

Motivated by his previous work Hilbert posed his famous 17th problem at the International Congress of Mathematicians in Paris (1900):

Hilbert’s 17th problem: Suppose that f ∈ ℝ(x_{1}, …, x_{n}) is nonnegative at all points of ℝ^{n} where f is defined. Is f a finite sum of squares of rational functions?

A slight reformulation of this problem is the following: Is each polynomial f ∈ ℝ[x_{1}, …, x_{n}] which is nonnegative on ℝ^{n} a finite sum of squares of rational functions, or equivalently, is there an identity q^{2}f = ∑_{j} p_{j}^{2}, where q, p_{1}, ⋯, p_{k} ∈ ℝ[x_{1}, …, x_{n}] and q ≠ 0. In the case n = 1 this is true, since the fundamental theorem of algebra implies that each nonnegative polynomial in one variable is a sum of two squares of real polynomials. As noted above, the case n = 2 was settled by Hilbert [5] itself. Hilbert’s 17th problem was solved in the affirmative by Emil Artin [1] in 1927. Using the Artin-Schreier theory of ordered fields Artin proved

Theorem 1. If f ∈ ℝ[x_{1}, ⋯, x_{n}] is nonnegative on ℝ^{n}, then there are polynomials q, p_{1}, …, p_{k} ∈ ℝ[x_{1}, ⋯, x_{n}], q ≠ 0, such that

f = \frac{p_{1}^{2} + ⋯ + p_{k}^{2}}{q^{2}} .

Artin’s proof of this theorem is nonconstructive. For strictly positive polynomials f (that is, f(x) > 0 for all x ∈ ℝ^{n}) a constructive method was developed by Habicht [3]. It is based on Polya’s theorem [13] which states that for each homogeneous polynomial p such that p(x_{1}, …, x_{n}) > 0 for all x_{1} ≥ 0, ⋯, x_{n} ≥ 0 and (x_{1}, …, x_{n}) ≠ 0, there exists a natural number N such that all coefficients of the polynomial (x_{1} + ⋯ + x_{n})^{N}p are positive. A quantitative version of Polya’s theorem providing a lower estimate for the number N in terms of p was recently given by Powers and Reznick [14].

There is also a quantitative version of Hilbert’s 17th problem which asks how many squares are needed. In mathematical terms it can be formulated in terms of the pythagoras number. For a ring K, the pythagoras number p(K) is the smallest natural number m such that each finite sum of squares of elements of K is a sum of m squares. If there is no such number m we set p(K) = ∞. Clearly, p(ℝ[x]) = p(ℝ(x)) = 2. Recall that Hilbert [5] had shown that p(ℝ(x, y)) ≤ 4. The landmark result on the quantitative version of Hilbert’s 17th problem was published in 1967 by A. Pfister [11] who proved

Theorem 2. p(ℝ(x_{1}, ⋯, x_{n})) ≤ 2^{n}.

That is, by Theorems 1 and 2, each nonnegative polynomial f ∈ ℝ[x_{1}, …, x_{n}] is a sum of at most 2^{n} squares of rational functions. Pfister’s proof was based on the theory of multiplicative forms (see, e.g., [12]), now also called Pfister forms.

The next natural question is: What is value of the number p(ℝ(x_{1}, …, x_{n}))? For n ≥ 3 this is still unknown! It is not difficult to prove that the sum 1 + x_{1}^{2} + ⋯ + x_{n}^{2} of n + 1 squares is not a sum of m squares with m < n + 1. Therefore

n + 1 ≤ p(ℝ(x_{1}, …, x_{n})) ≤ 2^{n}.

Using the theory of elliptic curves over algebraic function fields it was shown in [2] that Motzkin’s polynomial is not a sum of 3 squares. Hence p(ℝ(x_{1}, x_{2})) = 4.

Artin’s theorem triggered many further developments. The most important one in the context of optimization is to look for polynomials which are nonnegative on sets defined by polynomial inequalities rather than the whole ℝ^{n}. To formulate the corresponding result some preliminaries are needed. Let us write ∑_{n}^{2} for the cone of finite sums of squares of polynomials from ℝ[x_{1}, …, x_{n}].

In what follows we suppose that F = {f_{1}, …, f_{k}} is a finite subset of ℝ[x_{1}, …, x_{n}]. In real algebraic geometry two fundamental objects are associated with F. These are the basic closed semialgebraic set

K_{F} = {x ∈ ℝ^{n} : f_{1}(x) ≥ 0, ⋯, f_{k}(x) ≥ 0}

and the preorder

T_{F} := { ∑_{ε_{i}∈{0,1}} f_{1}^{ε_{1}} ⋯ f_{k}^{ε_{k}}σ_{ε}; σ_{ε} ∈ ∑_{n}^{2} }.

Note that the preorder T_{F} depends on the set F of generators for the semialgebraic set K_{F} rather than the set K_{F} itself.

Obviously, all polynomials from T_{F} are nonnegative on the set K_{F}, but in general T_{F} does not exhaust the nonnegative polynomials on K_{F}. The Positivstellensatz of Krivine-Stengle describes all nonnegative resp. positive polynomials on the semialgebraic set K_{F} in terms of quotients of elements of the preorder T_{F}.

Theorem 3. Let f ∈ ℝ[x_{1}, …, x_{n}].

(i) f(x) ≥ 0 for all x ∈ K_{F} if and only if there exist p, q ∈ T_{F} and m ∈ ℕ such that pf = f^{2m} + q.

(ii) f(x) > 0 for all x ∈ K_{F} if and only if there are p, q ∈ T_{F} such that pf = 1 + q.

This theorem was proved by G. Stengle [19], but essential ideas were already contained in J.-L. Krivine’s paper [8]. In both assertions (i) and (ii) the ‘if’ parts are almost trivial. Theorem 3 is a central result of modern real algebraic geometry. Proofs based on the Tarski-Seidenberg transfer principle can be found in [15] and [9].

Let us set f_{1} = 1 and k = 1 in Theorem 3(i). Then K_{F} = ℝ^{n} and T_{F} = ∑_{n}^{2}. Hence in this special case Theorem 3(i) gives Artin’s Theorem 1. The Krivine–Stengle Theorem 3(i) expresses the nonnegative polynomial f on K_{F} as a quotient of the two polynomials f^{2m} + q and p from the preorder T_{F}. Simple examples show that the denominator polynomial p cannot be avoided in general. For instance, if f_{1} = 1, k = 1, the Motzkin polynomial M is nonnegative on K_{F} = ℝ^{n}, but it is not in the preorder T_{F} = ∑_{n}^{2}. Replacing M by the polynomial M̃(x, y) := x^{4}y^{2} + x^{2}y^{4} + 1 − x^{2}y^{2} we even get a strictly positive polynomial of this kind. (One has M̃(x, y) ≥ \frac{26}{27} for all (x, y) ∈ ℝ^{2}.) Letting f_{1} = (1 − x^{2})^{3}, k = n = 1, the semialgebraic set K_{F} is the interval [−1, 1] and the polynomial f = 1−x^{2} is obviously nonnegative on K_{F}. Looking at the orders of zeros of f at ±1 one concludes easily that f is not in T_{F}. In view of these examples it seems to be surprising that strictly positive polynomials on a compact basic closed semialgebraic set always belong to the preorder. This result is the Archimedean Positivstellensatz which was proved by the author [17] in 1991.

Theorem 4. Suppose that f ∈ ℝ[x_{1}, …, x_{n}]. If the set K_{F} is compact and f(x) > 0 for all x ∈ K_{F}, then f ∈ T_{F}.

The original proof given in [17] (see also [18], pp. 344–345) was based on the solution of the moment problem for compact semialgebraic sets. The first algebraic proof of Theorem 4 was found by T. Wörmann [20], see, e.g., [15] or [9].

By definition the preorder T_{F} is the sum of sets f_{1}^{ε_{1}} ⋯ f_{k}^{ε_{k}} ∑_{n}^{2} . It is natural to ask how many terms of this kind are really needed. This question is answered by a result of T. Jacobi and A. Prestel in 2001. Let g_{1}, …, g_{l_{k}} denote the first l_{k} := 2^{k−1} + 1 polynomials of the following row of mixed products with no repeated factors of the generators f_{1}, … f_{k}:

1, f_{1}, …, f_{k}, f_{1}f_{2}, f_{1}f_{3}, …, f_{k−1}f_{k}, f_{1}f_{2}f_{3}, …, f_{k−2}f_{k−1}f_{k}, f_{1}f_{2} ⋯ f_{k}.

Let S_{F} be the sum of sets g_{j} ∑_{n}^{2}, where j = 1, …, l_{k}. Then Jacobi and Prestel [7] proved the following

Theorem 5. If K_{F} is compact and f ∈ ℝ[x_{1}, …, x_{n}] satisfies f(x) > 0 for all x ∈ K_{F}, then f ∈ S_{F}.

We briefly discuss this result. If k = 3, then l_{k} = 5 and S_{F} = ∑_{n}^{2} +f_{1} ∑_{n}^{2} +f_{2} ∑_{n}^{2} +f_{3} ∑_{n}^{2} +f_{1}f_{2} ∑_{n}^{2}, that is, the sets g ∑_{n}^{2} for g = f_{1}f_{3}, f_{2}f_{3}, f_{1}f_{2}f_{3} do not enter in the definition of S_{F}. If k = 4, then no products of three or four generators occur in the definition of S_{F}. Thus, if k ≥ 3, Theorem 5 is an essential strengthening of Theorem 4.

References

[1] E. Artin, Über die Zerlegung definiter Funktionen in Quadrate, Abh. math. Sem. Hamburg 5(1927), 110–115.

[2] J.S.W. Cassels, W.J. Ellison and A. Pfister, On sums of squares and on elliptic curves over function fields, J. Number Theory 3(1971), 125–49.

[3] W. Habicht, Über die Zerlegung strikte definiter Formen in Quadrate, Comment. Math. Math. 12(1940), 317–322.

[4] D. Hilbert, Über die Darstellung definiter Formen als Summe von Formenquadraten, Math. Ann. 32(1888), 342–350.

[5] D. Hilbert, Über ternäre definite Formen, Acta Math. 17 (1893), 169–197.

[6] D. Hilbert, Hermann Minkowski. Gedächtnisrede, Math. Ann. 68(1910), 445–471.

[7] T. Jacobi and A. Prestel, Distinguished representations of strictly positive polynomials, J. reine angew. Math. 532(2001), 223–235.

[8] J.-L. Krivine, Anneaux preordennes, J. Analyse Math. 12(1964), 307–326.

[9] M. Marshall, Positive Polynomials and Sums of Squares, Math. Surveys and Monographs 146, Amer. Math. Soc., 2008.

[10] T.S. Motzkin, The arithmetic-geometric inequality. In: Proc. Symposium on Inequalities, edited by O. Shisha, Academic Press, New York, 1967, pp. 205–224.

[11] A. Pfister, Zur Darstellung definiter Formen als Summe von Quadraten, Invent. Math. 4(1967), 229–237.

[12] A. Pfister, Quadratic Forms and Applications in Algebraic Geometry and Topology, London Math. Soc. Lect. Notes 217, Cambridge, 1995.

[13] G. Polya, Über positive Darstellung von Polynomen, Vierteljschr. Naturforsch. Ges. Zürich 73(1928), 141–145.

[14] V. Powers and B. Reznick, A new bound for Polya’s theorem with applications to polynomials positive on polyhedra, J. Pure Applied Algebra 164(2001), 221–229.

[15] A. Prestel and C. N. Delzell, Positive Polynomials, Springer-Verlag, Berlin, 2001.

[16] B. Reznick, On Hilbert’s construction of positive polynomials, Preprint, 2007.

[17] K. Schmüdgen, The K-moment problem for compact semi-algebraic sets, Math. Ann. 289(1991), 203–206.

[18] K. Schmüdgen, Noncommutative real algebraic geometry – some basic concepts and first ideas. In: Emerging Appl. Algebraic Geometry, edited by M. Putinar and S. Sullivant, Springer-Verlag, Berlin, 2009, pp. 325–350.

[19] G. Stengle, A Nullstellensatz and a Positivstellensatz in semialgebraic geometry, Math. Ann. 207( 1974), 87–97.

[20] T. Wörmann, Strikt positive Polynome in der semialgebraischen Geometrie, Dissertation, Universität Dortmund, 1998.

Konrad Schmüdgen Mathematisches Institut Universität Leipzig Johannisgasse 26 04103 Leipzig

konrad.schmuedgen@math.uni-leipzig.de