From: rusin@vesuvius.math.niu.edu (Dave Rusin) Subject: Re: inequality Date: 22 Aug 2000 06:30:16 GMT Newsgroups: sci.math Summary: Proving a real inequality using sums of squares of functions In article <8np5g7$v17$1@nnrp1.deja.com>, Serge Zlobin wrote: >I offer to solve the inequality that I've made for an olympiad. It's >interesting for me to get known different solutions. >Let x, y, z be positive numbers satisfy the condition xyz=1. Prove that >1/(x+2)+1/(y+2)+1/(z+2)<=1. In contests, clever and/or elegant solutions are prized; but as a practical matter, it is good to have a _uniform_ way of demonstrating inequalities. I usually try a sum-of-squares argument, but this particular example proves to be very interesting with regard to that method. I'd like to show why, and to pose some questions. We may express our problem this way: given that x>0 and y>0, we are asked to show that (some rational function in x and y) is nonnegative. Replacing x and y by u^2 and v^2 respectively, (and clearing some obviously-positive factors from the denominator) we are reduced to showing that (u^2+v^2) - 3*u^2*v^2 + (u*v)^4 is everywhere nonnegative. Now, Hilbert's 17th problem asks about just this situation: real polynomials which are everywhere non-negative. Clearly we can prove that a polynomial is everywhere positive by expressing it as a sum of squares; the question is whether such a representation is always possible, and it turns out the answer is: "it depends". If "squares" means "squares of polynomials", the answer is "no" but if "squares" means "squares of rational functions", the answer is "yes". To return to the problem at hand, I looked for a representation of the given polynomial as a sum of squares of polynomials. I found none. Meanwhile, two other posters have followed up with nice solutions using the arithmetic-geometric mean inequality with three variables. Here is the idea, rephrased to match my general approach: First, given positive numbers a,b,c, the AGM inequality states that S = A^3 - 27*C is non-negative, where A=(a+b+c) and C=(a*b*c). Well, then, given our three positive numbers x,y,z we may set a=x*y, b=y*z, c=z*x and then define A, C, and S as above. After a bit of algebra we check that S = (A+B-4) * ( (2*A+3*B)^2 + 27*B^2 )/4 - (B-1)*(2*A+3*B)^2 where B = x*y*z is the square root of C. On the other hand, T = 1 - ( 1/(x+2)+1/(y+2)+1/(z+2) ) simplifies to (A+B-4)/(2+x)/(2+y)/(2+z) , so we see that, when B=1, the positivity of T is equivalent to that of S. So we may choose not to _use_ the AGM inequality, but we will essentially _reprove_ it! To match this to my strategy for proving inequalities, we now see that it is sufficient to provide an expression for S as a sum of squares; substituting a=x*y and so on, and using the premise that x*y*z = 1, we would eventually find an expression for (A+B-4), and for T itself if we like, as a sum of squares, showing that it too is everywhere non-negative. This would give a one-line proof of the original problem which can be checked with simple algebra. I thought I remembered something about this particular AGM inequality, however, and a check of my notes found something interesting: it was during an attempt to prove precisely that inequality with the sum-of-squares trick that Motzkin found his example of a positive polynomial which was _not_ a sum of polynomial squares! This perhaps explains why my initial ventures failed. So I ask the following questions: (1) Could someone please express (u^2+v^2+w^2)^3 - 27*(u*v*w)^2 as a sum of squares of rational functions? (As noted above, I could then do the same for 1 - ( 1/(x+2)+1/(y+2)+1/(z+2) ) , completing the original problem.) (2) More generally, what's the best algorithm to represent a polynomial as a sum of squares? ("Best" is deliberately nebulous. I like useful heuristics which I can use by hand for contest problems. I also like complete methods I can program into symbolic engines. It would be of interest to know how to find representations of squares of _polynomials_, when possible, and of _rational functions_ in general.) (3) Am I correct, that (u^2+v^2) - 3*(u*v)^2 + (u*v)^4 is not a sum of squares of polynomials? dave ============================================================================== From: israel@math.ubc.ca (Robert Israel) Subject: Re: inequality Date: 23 Aug 2000 09:09:21 GMT Newsgroups: sci.math In article <8nt6lo$a4l$1@gannett.math.niu.edu>, Dave Rusin wrote: >(3) Am I correct, that (u^2+v^2) - 3*(u*v)^2 + (u*v)^4 is not a sum > of squares of polynomials? Yes. If u^2+v^2-3(uv)^2+(uv)^4 was a sum of squares of polynomials P_j, each of these P_j would have degree at most 2 in u and degree at most 2 in v, and the only terms of degree 2 in u (or similarly in v) could be a constant multiple of u^2 v^2. There is no constant term because P_j(0,0) = 0. This leaves P_j of the form a u^2 v^2 + b u v + c u + d v. Plug this into the equations P_j(1,1)=P_j(-1,1)=P_j(1,-1)=P_j(-1,-1)=0 and you get a=b=c=d=0. Robert Israel israel@math.ubc.ca Department of Mathematics http://www.math.ubc.ca/~israel University of British Columbia Vancouver, BC, Canada V6T 1Z2 ============================================================================== From: "Peter L. Montgomery" Subject: Re: inequality Date: Wed, 23 Aug 2000 03:39:54 GMT Newsgroups: sci.math In article <8nt6lo$a4l$1@gannett.math.niu.edu> rusin@vesuvius.math.niu.edu (Dave Rusin) writes: >(1) Could someone please express (u^2+v^2+w^2)^3 - 27*(u*v*w)^2 as a > sum of squares of rational functions? (As noted above, I could then > do the same for 1 - ( 1/(x+2)+1/(y+2)+1/(z+2) ) , completing the > original problem.) (u^2/4 + v^2 + w^2)*(2*u^2 - v^2 - w^2)^2 + (27/4)*u^2*(v^2 - w^2)^2 QUESTION 1: This is a sum of four squares of polynomials over R or six such squares over Q (using 27/4 = 25/4 + 1/4 + 1/4, for example). Can either count be reduced? QUESTION 2: Can we express this as a sum of squares in Z[u, v, w] (i.e., using only integer coefficients)? -- E = m c^2. Einstein = Man of the Century. Why the squaring? Peter-Lawrence.Montgomery@cwi.nl Home: San Rafael, California Microsoft Research and CWI ============================================================================== From: rusin@vesuvius.math.niu.edu (Dave Rusin) Subject: Re: inequality Date: 23 Aug 2000 18:23:19 GMT Newsgroups: sci.math In article , Peter L. Montgomery wrote: > >>(1) Could someone please express (u^2+v^2+w^2)^3 - 27*(u*v*w)^2 as a >> sum of squares of rational functions? > > (u^2/4 + v^2 + w^2)*(2*u^2 - v^2 - w^2)^2 + (27/4)*u^2*(v^2 - w^2)^2 Following Peter Montgomery's calculation we deduce that T = 1 - ( 1/(x+2)+1/(y+2)+1/(z+2) ) equals / 2 2 \ | ((x y + 4 y z + 4 z x) (2 x y - y z - z x) + 27 x y (y z - z x) | | | | 2 | \ + 4 (x y z - 1) (2 x y + 2 y z + 2 z x + 3 x y z) ) / --------------------------------------------------------------------- 2 2 2 2 ((2 x y + 2 y z + 2 z x + 3 x y z) + 27 x y z ) (2 + x) (2 + y) (2 + z) As long as x,y,z are positive, the denominator is positive and the numerator is the sum of two positive terms and a multiple of (xyz-1). It follows that when xyz=1, this T is non-negative, which is the original equality desired. Perfect: a direct, simple, mysterious proof :-) Comparing to my previous post, we may also obtain a representation for the everywhere-nonnegative polynomial u^4*v^4 - 3*u^2*v^2 + u^2+v^2 as a sum of squares of rational functions: it's equal to 4 4 2 2 4 4 2 2 2 4 4 2 2 2 (u v + 4 v + 4 u ) (2 u v - v - u ) + 27 u v ( u - v ) ----------------------------------------------------------------- 4 4 2 2 2 2 2 4 4 (2 u v + 2 v + 2 u + 3 u v ) + 27 u v which is sufficient (since for example we may expand (X^2+Y^2)/(Z^2+W^2) = ((X*Z-Y*W)/(Z^2+W^2))^2 + ((X*W+Y*Z)/(Z^2+W^2))^2 So the polynomial is a sum of, at worst, four squares of rational functions. Robert Israel has separately posted a proof that no representation as a sum of squares of polynomials exists. I'm a little confused, since PM's decomposition shows the AGM inequality for three variables _can_ be proved with a sum-of-squares-of-polynomials argument; I had thought not. (He has simply noted that (a+b+c)^3 - 27*(a*b*c) = (a/4+b+c)*(2*a-b-c)^2 + (27/4)*a*(b-c)^2; with a,b,c positive this proves (a+b+c)/3 > (a*b*c)^(1/3).) But his computations, together with RI's proof, give a concrete example showing the difference between "sum of squares of polynomials" and "sum of squares of rational functions". I notice the remaining question has not been answered: Peter, how did you *do* that? In hindsight, I guess I see how you might have played around and found this equation; but did you proceed systematically somehow? What's techniques _find_ a sum-of-squares decomposition? dave ============================================================================== From: "Peter L. Montgomery" Subject: Re: sums of squares (was: inequality) Date: Wed, 23 Aug 2000 19:48:46 GMT Newsgroups: sci.math In article <8o14qn$epb$1@gannett.math.niu.edu> rusin@vesuvius.math.niu.edu (Dave Rusin) writes: >I'm a little confused, since PM's decomposition shows the AGM inequality >for three variables _can_ be proved with a sum-of-squares-of-polynomials >argument; I had thought not. (He has simply noted that > (a+b+c)^3 - 27*(a*b*c) = (a/4+b+c)*(2*a-b-c)^2 + (27/4)*a*(b-c)^2; >with a,b,c positive this proves (a+b+c)/3 > (a*b*c)^(1/3).) But >his computations, together with RI's proof, give a concrete example >showing the difference between "sum of squares of polynomials" and >"sum of squares of rational functions". > > >I notice the remaining question has not been answered: Peter, how did >you *do* that? In hindsight, I guess I see how you might have played >around and found this equation; but did you proceed systematically >somehow? What's techniques _find_ a sum-of-squares decomposition? All summands must vanish when a = b = c. While trying to eliminate the a^3 term, I wanted something symmetric in b and c. a*(a - b/2 - c/2)^2 meets these requirements. The remainder 4a^2*(b + c) + (11/4)*a*(b+c)^2 + (b + c)^3 - 27abc is a quadratic in a. Maple verified that the discriminant of this quadratic is nonnegative and its leading coefficient 4*(b + c) is positive unless b = c = 0. Therefore this remainder is always nonnegative. We could complete the square in a, getting 4*(b + c) * (a + something)^2 + (new remainder in b, c only) Here `something' and `new remainder' are rational functions. Perhaps another reader would observe this and post it -- meanwhile I tried to find something more elegant. Instead I tried subtracting b*(b - a/2 - c/2)^2 and c*(c - a/2 - b/2)^2 from the first remainder, trying to preserve the symmetry in a, b, c. The new (symmetric) remainder has degree at most 2 in each of a, b, c. Alas, a discriminant test reveals that the new remainder can be negative. Looking back at the first remainder, I stared at the quadratic and constant terms 4*a^2*(b + c) (b + c)^3 The polynomial (b + c)*(2*a - b - c)^2 shares these terms and vanishes (as required) when a = b = c. Subtracting this from the first remainder left (27/4)*a*(b - c)^2. -- E = m c^2. Einstein = Man of the Century. Why the squaring? Peter-Lawrence.Montgomery@cwi.nl Home: San Rafael, California Microsoft Research and CWI ============================================================================== From: reznick@mimas.math.uiuc.edu (Bruce Reznick) Subject: Re: inequality Date: 25 Aug 2000 11:15:56 -0500 Newsgroups: sci.math Apologies for a late entry into this thread, I am not a regular reader of s.m.r. Most of the examples discussed are forms derived from substitution into the arithmetic geometric inequality. Let me immodestly cite several of my own papers as relevant to the discussion: [1] Extremal psd forms with few terms, Duke Math. J. 45 (1978), 363-374 (MR 58.511). [2] A quantitative version of Hurwitz' theorem on the arithmetic-geometric inequality, J. Reine Angew. Math., 377 (1987), 108-112 (MR 88e.11019) [3] Forms derived from the arithmetic-geometric inequality, Math. Ann. 283 (1989), 431-464 (MR 90i.11043). [4] (With M. D. Choi and T. Y. Lam) Sums of squares of real polynomials. Proc. Sympos. Pure Math. 58.2 (1995), 103-126 (MR 96f:11058). [5] Some concrete aspects of Hilbert's 17th problem, Real Algebraic Geometry and Ordered Structures, (C. N. Delzell, J.J. Madden eds.) Cont. Math., 253 (2000), 251-272. (Of these, [5] is downloadable as a preprint from my somewhat-out-of-date website www.math.uiuc.edu/~reznick.) Now, to answer some of the questions that have come up, from Dave Rusin, Peter Montgomery and Robert Israel: --> (DR) More generally, what's the best algorithm to represent a polynomial as a sum of squares? ("Best" is deliberately nebulous. I like useful heuristics which I can use by hand for contest problems. I also like complete methods I can program into symbolic engines. It would be of interest to know how to find representations of squares of _polynomials_, when possible, and of _rational functions_ in general.) There is an algorithm described in [5] and discussed in greater detail in [4]. Very recently, Pablo Parrilo at Caltech has shown that the algorithm can be implemented [I apologize for not knowing the technical terminology here.] Essentially, to each polynomial, one associates a family of real symmetric matrices, and the polynomial is a sum of squares if one of those matrices is psd. (The algorithm for finding such a matrix is the part of the problem that Parrilo has worked on.) Choi, Lam and I wrote a series of papers in which we used the algorithm without writing it up in detail until 1997; we knew the main ideas for about 20 years. --> Could someone please express (u^2+v^2+w^2)^3 - 27*(u*v*w)^2 as a > sum of squares of rational functions? (As noted above, I could then > do the same for 1 - ( 1/(x+2)+1/(y+2)+1/(z+2) ) , completing the > original problem.) (u^2/4 + v^2 + w^2)*(2*u^2 - v^2 - w^2)^2 + (27/4)*u^2*(v^2 - w^2)^2 (PM) QUESTION 1: This is a sum of four squares of polynomials over R or six such squares over Q (using 27/4 = 25/4 + 1/4 + 1/4, for example). Can either count be reduced? The number of squares (over R) is the rank of this psd matrix noted above. The methods of [4] would let you decide whether there is a solution over R of rank 3. I *think* (5 minute calculation) there is not such a solution. --> QUESTION 2: Can we express this as a sum of squares in Z[u, v, w] (PM) (i.e., using only integer coefficients)? I think not, because x^3, y^3 and x^3 could each appear in only one summand. I could be wrong. -->(DR) Am I correct, that (u^2+v^2) - 3*(u*v)^2 + (u*v)^4 is not a sum > of squares of polynomials? (RI) Yes. See the homogenized version of this in [1], p.372, second line, corresponding to m = 4. The "mother" of all such examples is due to Theodore S. Motzkin in 1967. I give the full story in [4]. His example was 1 + x^4y^2 + x^2y^4 - 3x^2y^2. What made it interesting as an exercise in mathematical psychology is this: Hilbert had shown in 1888 that there exist non-negative polynomials which cannot be written as a sum of squares of polynomials, but his example involved 19th-century style curve theory, and was considered so abstruse that, as far as I know, nobody every worked out the details in print. Motzkin's example was entirely different and much simpler. His is a "Book Proof" in the sense of Erdos, and found in the cited paper. Bruce Reznick ============================================================================== From: Bruce Reznick Subject: Re: positive polynomials. Date: Wed, 6 Sep 2000 08:57:03 -0500 (CDT) To: rusin@math.niu.edu [deletia --djr] Interestingly, Motzkin came up with his example as part of a seminar to prove inequalities by writing them as a sum of squares. [See my survey paper for a reference.] I should have said in my article, but didn't, that a form derived from monomial substitution into the arithmetic-geometric inequality is a sum of squares depending only on the combinatorial configuration in a set of lattice points determined by the substitution. I'll be happy to answer any more questions you might have on the subject, whenever. Bruce ==============================================================================