9512.net

# On the absence of uniform denominators in Hilbert's 17th problem

arXiv:math/0306163v1 [math.AG] 10 Jun 2003

ON THE ABSENCE OF UNIFORM DENOMINATORS IN HILBERT’S 17TH PROBLEM
BRUCE REZNICK Abstract. Hilbert showed that for most (n, m) there exist psd forms p(x1 , . . . , xn ) of degree m which cannot be written as a sum of squares of forms. His 17th problem asked whether, in this case, there exists a form h so that h2 p is a sum of squares of forms; that is, p is a sum of squares of rational functions with denominator h. We show that, for every such (n, m) there does not exist a single form h which serves in this way as a denominator for every psd p(x1 , . . . , xn ) of degree m.

1. Introduction Let Hd (Rn ) denote the set of real homogeneous forms of degree d in n variables (“nary d-ics”) . By identifying p ∈ Hd (Rn ) with the N = n+d?1 -tuple of its coe?cients, n?1 we see that Hd (Rn ) ≈ RN . Suppose m is an even integer. A form p ∈ Hm (Rn ) is called positive semide?nite or psd if p(x1 , . . . , xn ) ≥ 0 for all (x1 , . . . , xn ) ∈ Rn . Following , we denote the set of psd forms in Hm (Rn ) by Pn,m . Since Pn,m is closed under addition and closed under multiplication by positive scalars, it is a convex cone. In fact, Pn,m is a closed convex cone: if pn → p coe?cient-wise, and each pn is psd, then so is p. A psd form is called positive de?nite or pd if p(x1 , . . . , xn ) = 0 implies xj = 0 for 1 ≤ j ≤ n. The pd n-ary m-ics are the interior of the cone Pn,m. A form p ∈ Hm (Rn ) is called a sum of squares or sos if it can be written as a sum of squares of polynomials; that is, p = k h2 . It is easy to show in this case that k each hk ∈ Hm/2 (Rn ). Again following , we denote the set of sos forms in Hm (Rn ) by Σn,m . Clearly, Σn,m is a convex cone; less obviously, it is a closed cone, a result due to R. M. Robinson . In light of the inclusion Σn,m ? Pn,m , let ?n,m = Pn,m \ Σn,m . It was well-known by the late 19th century that Pn,m = Σn,m when m = 2 or n = 2. In 1888, Hilbert proved  that Σ3,4 = P3,4 ; more speci?cally, every p ∈ P3,4 can be written as the sum of three squares of quadratic forms. (An elementary proof, with “?ve” squares is in [2, pp.16-17]; for modern expositions of Hilbert’s proof, see  and .) Hilbert also proved in  that the preceding are the only cases for which ?n,m = ?. That is,
Date: May 12, 2003. 1991 Mathematics Subject Classi?cation. Primary: 11E10, 11E25, 11E76, 12D15, 14P99. This material is based in part upon work of the author, supported by the USAF under DARPA/AFOSR MURI Award F49620-02-1-0325. Any opinions, ?ndings, and conclusions or recommendations expressed in this publication are those of the author and do not necessarily re?ect the views of these agencies.
1

2

BRUCE REZNICK

if n ≥ 3 and m ≥ 6 or n ≥ 4 and m ≥ 4, then there exist psd forms n-ary m-ics that are not sos. In 1893, Hilbert  generalized his three-square result for P3,4 to ternary forms of higher degree. Suppose p ∈ P3,m with m ≥ 6. Then there exist p1 ∈ P3,m?4 and h1k ∈ Hm?2 (R3 ), 1 ≤ k ≤ 3, so that p1 p = h2 + h2 + h2 . 11 12 13 (Hilbert’s proof seems to be non-constructive, and lacks a modern exposition. In the very recent paper , de Klerk and Pasechnik discuss the implementation of an algorithm to ?nd p1 so that p1 p is sos, though not necessarily as a sum of three squares. This paper uses Hilbert’s result without giving an independent proof.) If m = 6 or 8, then p1 is a sum of three squares of forms, and hence (as Landau later noted ), the four-square identity implies that p2 p = p1 (p1 p) is the sum of 1 four squares of forms. If m ≥ 10, then the argument can be applied to p1 : there exists p2 ∈ P3,m?8 with p2 p1 = h2 + h2 + h2 . Thus, if m = 10 or 12 (so that 23 22 21 P3,m?8 = Σ3,m?8 ), then (p1 p2 )2 p = p2 (p2 p1 )(p1 p) is the sum of four squares of forms, 2 An easy induction shows that there exists q ∈ Ht (R3 ) with t = ? (m?2) ? so that q 2 p 8 is the sum of four squares of forms. Hilbert’s 17th Problem asked whether this generalizes to n > 3 variables; that is, if p ∈ Pn,m, must there exist some form q so that q 2 p is sos? Artin proved that there must be, in a way that gives no information about q. Much more on the history of this subject can be found in the survey paper . This discussion leads to two closely related questions. Suppose p ∈ Pn,m . Can we ?nd a form h such that hp is sos? Can we ?nd a form q so that q 2 p is sos? If we’ve answered the second, we’ve answered the ?rst. Conversely, if p = 0 is psd and hp is sos, then h is psd. But it needn’t be sos; indeed, a trivial answer to the ?rst question is to take h = p. Stengle proved  that if p(x, y, z) = x3 z 3 + (y 2z ? x3 ? z 2 x)2 , then p2s+1 ∈ ?3,6(2s+1) for every integer s. That is, p2s?1 · p is sos, but p2s · p is not. Choi and Lam showed  that for S ∈ ?3,6 (see (3) below), the product S(x, y, z)S(x, z, y) is actually sos. The author gratefully acknowledges correspondence with Chip Delzell, Pablo Parrilo, Vicki Powers, Marie-Fran?oise Roy and Claus Scheiderer. Their suggestions have c made this a better paper. 2. What is known about the denominator The ?rst concrete result about a denominator in Hilbert’s 17th Problem was found by P?lya . He showed that if f ∈ Hd (Rn ) is positive on the unit simo plex {(x1 , . . . , xn ) | xj ≥ 0, xj = 1}, then for su?ciently large N, ( j xj )N f has positive coe?cients. Replacing each xj by x2 , we see that if p ∈ H2d (Rn ) is an even j positive de?nite form, then ( j x2 )N p is a sum of even monomials with positive coj e?cients, and so, as it stands, is a sum of squares of monomials. Taking even N, we see that q = ( j x2 )N/2 is a denominator for p. Habicht  generalized P?lya’s o j

ON THE ABSENCE OF UNIFORM DENOMINATORS IN HILBERT’S 17TH PROBLEM

3

proof to give an alternate solution to Hilbert’s 17th Problem for pd forms; however, h is not readily constructible and in general is no longer a power of x2 . Except j for one example, P?lya did not attempt to determine an explicit value of N. A good o exposition of the theorems of P?lya and Habicht can be found in . o For positive de?nite p ∈ Pn,m , let ?(p) := inf{p(u) : u ∈ S n?1 } sup{p(u) : u ∈ S n?1 }

measure how “close” p is to having a zero. The author  showed that if N≥ nm(m ? 1) n+m ? , (4 log 2)?(p) 2

then ( j x2 )N p is a sum of (m + 2N)-th powers of linear forms, and so is sos. A j similar lower bound has been shown to apply in P?lya’s case, one which goes to o in?nity as p approaches the boundary of Pn,m . (See papers by de Loera and Santos  and by Powers and the author .) The restriction to positive de?nite forms is necessary. There exist psd forms p in n ≥ 4 variables so that, if h2 p is sos, then h must have a speci?ed zero. The existence of these unavoidable singularities, or so-called “bad points”, insures that ( x2 )r p j can never be a sum of squares of forms for any r. Habicht’s Theorem implies that no positive de?nite form can have a bad point. Bad points were ?rst noted by Straus and have been extensively studied by Delzell; see, e.g. [4, 5]. 3. Recent results and a new theorem Scheiderer has shown in very recent work  that for p ∈ P3,m , there exists N = N(p) so that (x2 + y 2 + z 2 )N p(x, y, z) is sos; indeed, x2 + y 2 + z 2 can be replaced by any positive de?nite form. This is a strong refutation to the existence of bad points for ternary forms. Also very recently, Lombardi and Roy  have constructed a quantitative version of the Positivstellensatz. A special case is that for ?xed (n, m), there exists d = d(n, m) so that if p ∈ Pn,m , there exists q ∈ Hd (Rn ) so that q 2 p is sos. Suppose (n, m) is such that ?n,m = ?. Theorem 1 below states that there is no single form h so that, if p ∈ Pn,m , then hp is sos. Corollary 2 says that there is not even a ?nite set of forms H so that, if p ∈ Pn,m , then there exists h ∈ H so that hp in sos. In particular, there does not exist a ?nite set of denominators which apply to all of Pn,m . This result implies that N(p) in Scheiderer’s theorem is not bounded as p ranges over P3,m . It also implies that the denominators in the Lombardi-Roy theorem cannot be chosen from a ?nite, predetermined set. The proof of the Theorem is elementary and relies on a few simple observations. If p = 0 is psd and hp is sos, then h is psd. As previously noted, Σn,m is a closed cone for all (n, m). This cone is invariant under the action of taking invertible linear changes of form. Thus, if h′ is derived from h by such a linear change, and if hp is sos

4

BRUCE REZNICK

2 for every p ∈ Pn,m , then so is h′ p. Suppose ? is a linear form, p = j gk is sos, and ? | p. Then ?2 | p and ? | gk for each k, and by induction, ?2s | p =? ?s | gk . Thus, we can “peel o?” squares of linear factors from any sos form; this is a common practice, dating back at least to [20, p. 267]. We use this observation in the contrapositive: if p ∈ ?n,m , then ?2s p ∈ ?n,m+2s .

Theorem 1. Suppose ?n,m = ?. Then there does not exist a non-zero form h so that if p ∈ Pn,m , then hp is sos. Proof. Suppose to the contrary that such a form h exists. Since h = 0, there exists a point a ∈ Rn so that h(a) = 0. By making an invertible linear change of variables, we can take a = (1, 0, . . . , 0). Thus, we may assume without loss of generality that h(x1 , 0, . . . , 0) = αxd , where α > 0 and d is even. In the sequel, we distinguish x1 1 from the other variables. Choose p ∈ Pn,m \ Σn,m . Then h(x1 , x2 , . . . , xn )p(x1 , rx2 , . . . , rxn ) is sos for every r ∈ N. By making the change of variables xi → xi /r for i ≥ 2, we see that h(x1 , r ?1 x2 , . . . , r ?1xn )p(x1 , x2 , . . . , xn ) is also sos. Since
r→∞

lim h(x1 , r ?1 x2 , . . . , r ?1xn ) = h(x1 , 0, . . . , 0) = αxd , 1

and since Σn,m+d is closed, it follows that
r→∞

lim h(x1 , r ?1x2 , . . . , r ?1 xn )p(x1 , x2 , . . . , xn ) = αxd p(x1 , . . . , xn ) 1

is sos. Thus p is sos, a contradiction. The following elegant proof is due to Claus Scheiderer and is included with his permission; it supersedes the proof in an earlier version of this manuscript. Corollary 2. Suppose ?n,m = ?. Then there does not exist a ?nite set of non-zero forms H = {h1 , ..., hN } with the property that, if p ∈ Pn,m , then hk p is sos for some hk ∈ H. Proof. Suppose H exists. For each k, there exists non-zero p ∈ ?n,m so that hk p is sos. (Otherwise, we may delete hk harmlessly from H.) Thus, each hk is psd, and 2 2 there exists a form qk so that qk hk is sos. De?ne h = k qk hk . We now show that for every p ∈ Pn,m, hp is sos: this contradicts the Theorem and proves the Corollary. By hypothesis, there exists hj ∈ H so that hj p is sos. Thus, hp =
k=j 2 qk hk 2 · qj · hj p

is a product of sos factors, and so is sos.

ON THE ABSENCE OF UNIFORM DENOMINATORS IN HILBERT’S 17TH PROBLEM

5

Finally, we know by Hilbert’s theorem that for p ∈ P3,6 , there exists quadratic h so that hp ∈ Σ3,8 . The three simplest forms in ?3,6 are (1) M(x, y, z) = x4 y 2 + x2 y 4 + z 6 ? 3x2 y 2z 2 , due to Motzkin ; Robinson’s  simpli?cation of Hilbert’s construction (2) R(x, y, z) = x6 + y 6 + z 6 ? (x4 y 2 + x2 y 4 + x4 z 2 + x2 z 4 + y 4 z 2 + y 2 z 4 ) + 3x2 y 2z 2 ; and (3) S(x, y, z) = x4 y 2 + y 4z 2 + z 4 x2 ? 3x2 y 2 z 2 , due to Choi and Lam [1, 2]. It is not too di?cult to consider qM, qR, qS for q(x, y, z) = a2 x2 + b2 y 2 + c2 z 2 , and determine whether these are sos using the algorithm of  directly or its implementation in, e.g., . Interestingly enough, these conditions are the same in each case: the forms are sos if and only if 2(a2 b2 + a2 c2 + b2 c2 ) ≥ a4 + b4 + c4 . This expression factors rather neatly into: (a + b + c)(a + b ? c)(b + c ? a)(c + a ? b) ≥ 0, so if a ≥ b ≥ c ≥ 0 without loss of generality, the only non-trivial condition is that b+c ≥ a; that is, there is a (possibly degenerate) triangle with sides a, b, c. (Robinson [20, p. 273] has a super?cially similar condition, but note that his multiplier is ax2 + by 2 + cz 2 .) By specializing this result and scaling variables as in the proof of the theorem, we note that (x2 + y 2 + z 2 )M(x, λy, λz), (x2 + y 2 + z 2 )R(x, λy, λz), (x2 + y 2 + z 2 )S(x, λy, λz) are sos if and only if 0 ≤ λ ≤ 2. References
 Choi, M. D. and T. Y. Lam, An old question of Hilbert, Queen’s Papers in Pure and Appl. Math. (Proceedings of Quadratic Forms Conference, Queen’s University (G. Orzech ed.)), 46 (1976), 385–405.  Choi, M. D. and T. Y. Lam, Extremal positive semide?nite forms, Math. Ann., 231 (1977), 1–18.  Choi, M. D., T. Y. Lam and B. Reznick, Sums of squares of real polynomials, Proc. Sympos. Pure Math., 58.2 (1995), 103–126.  Delzell, C. N., Bad points for positive semide?nite polynomials, Abstracts Amer. Math. Soc., 18 (1997), #926-12-174, 482.  Delzell, C. N., Unavoidable singularities when writing polynomials as sums of squares of real rational functions, in preparation. ¨  Habicht, W., Uber die Zerlegung strikte de?niter Formen in Quadrate, Comment. Math. Helv., 12 (1940) 317–322.  Hardy, G. H., J. E.. Littlewood and G. P?lya, Inequalities, Camb. U. Press, 2nd ed., 1967. o

6

BRUCE REZNICK

¨  Hilbert, D., Uber die Darstellung de?niter Formen als Summe von Formenquadraten, Math. Ann. 32 (1888), 342–350; see Ges. Abh. 2, 154–161, Springer, Berlin, 1933, reprinted by Chelsea, New York, 1981. ¨  Hilbert, D., Uber tern¨re de?nite Formen, Acta Math. 17 (1893) 169–197; see Ges. Abh. 2, a 345–366, Springer, Berlin, 1933, reprinted by Chelsea, New York, 1981 .  de Klerk, E. and D. V. Pasechnik, Products of positive forms, linear matrix inequalities, and Hilbert 17-th problem for ternary forms, to appear in European J. of Oper. Res. ¨  Landau, E., Uber die Darstellung de?niter Funktionen durch Quadrate, Math. Ann., 62 (1906), pp. 272–285; also in Collected Works, vol. 2, pp. 237–250, Thales-Verlag, Essen, 1986.  de Loera, J. A. and F. Santos, An e?ective version of P?lya’s theorem on positive de?nite o forms, J. Pure Appl. Algebra, 108 (1996), 231–240. (See correction, same journal, 155 (2001), 309–310.)  Lombardi, H. and M.-F. Roy, Elementary recursive degree bounds for Positivstellensatz, in preparation.  Motzkin, T, S., The arithmetic-geometric inequality, pp. 205–224 in Inequalities (O. Shisha, ed.) Proc. of Sympos. at Wright-Patterson AFB, August 19–27, 1965 , Academic Press, New York, 1967; also in Theodore S. Motzkin: Selected Papers, Birkh¨user, Boston, (D. Cantor, B. a Gordon and B. Rothschild, eds.).  Parrilo, P., Structured semide?nite programs and semialgebraic methods in robustness and optimization, Ph.D. thesis, Calif. Inst. of Tech., 2000. ¨  P?lya, G., Uber positive Darstellung von Polynomen, Vierteljschr. Naturforsch. Ges. Z¨ rich, o u 73 (1928), 141–145; see Collected Papers, Vol. 2, pp. 309–313, MIT Press, Cambridge, Mass., London, 1974.  Powers, V. and B. Reznick, A new bound for P?lya’s theorem with applications to polynomials o positive on polyhedra, J. Pure Appl. Algebra 164 (2001), 221–229.  Reznick, B., Uniform denominators in Hilbert’s Seventeenth Problem, Math. Z., 220 (1995), 75–98.  Reznick, B., Some concrete aspects of Hilbert’s 17th Problem, Contemp. Math., 253 (2000), 251–272.  Robinson, R. M., Some de?nite polynomials which are not sums of squares of real polynomials, Izdat. “Nauka” Sibirsk. Otdel. Novosibirsk, (1973) pp. 264–282, (Selected questions of algebra and logic (a collection dedicated to the memory of A. I. Mal’cev), abstract in Notices AMS, 16 (1969), p. 554.  Rudin, W., Sums of squares of polynomials, Amer. Math. Monthly, 107 (2000), 813–821.  Scheiderer, C., Sums of squares on compact real algebraic surfaces, in preparation.  Stengle, G., Integral solution of Hilbert’s seventeenth problem, Math. Ann. 246 (1979/1980), 33–39.  Swan, R.G., Hilbert’s theorem on positive ternary quartics, Contemp. Math. 272 (2000), 287– 292. Department of Mathematics, University of Illinois at Urbana-Champaign, Urbana, IL 61801 E-mail address: reznick@math.uiuc.edu