• unlimited access with print and download
    $ 37 00
  • read full document, no print or download, expires after 72 hours
    $ 4 99
More info
Unlimited access including download and printing, plus availability for reading and annotating in your in your Udini library.
  • Access to this article in your Udini library for 72 hours from purchase.
  • The article will not be available for download or print.
  • Upgrade to the full version of this document at a reduced price.
  • Your trial access payment is credited when purchasing the full version.
Buy
Continue searching

Polynomials nonnegative on noncompact subsets of the plane

Dissertation
Author: Ha Ngoc Nguyen
Abstract:
In 1991, Schmüdgen proved that if f is a polynomial in n variables with real coefficients such that f > 0 on a compact basic closed semialgebraic set K ⊆ [Special characters omitted.] Rn , then there always exists an algebraic expression showing that f is positive on K. Then in 1999, Scheiderer showed that if K is not compact and its dimension is 3 or more, there is no analogue of Schmüdgen's Theorem. However, in the noncompact two-dimensional case, very little is known about when every f positive or nonnegative on a noncompact basic closed semialgebraic set K ⊆ [Special characters omitted.] R2 has an algebraic expression proving that f is nonnegative on K. Recently, M. Marshall answered a long-standing question in real algebraic geometry by showing that if f ∈ [Special characters omitted.] R [x, y ] and f ≥ 0 on the strip [0, 1] × [Special characters omitted.] R , then f has a representation f = σ0 + σ1x (1 - x ), where σ0 , σ1 ∈ [Special characters omitted.] R [x, y ] are sums of squares. This thesis gives some background to Marshall's result, which goes back to Hilbert's 17th problem, and our generalizations to other noncompact basic closed semialgebraic sets of [Special characters omitted.] R2 which are contained in strip. We also give some negative results.

Contents 1 Introduction 1 2 Preliminaries 4 2.1 Positivity and Sums of Squares.................4 2.2 Nonnegative Polynomials in R 2 .................11 3 Polynomials Nonnegative on Half-strips in the Plane 14 3.1 Introduction............................14 3.2 Half-strips.............................15 3.3 Further Examples in [0,1] ×R + .................21 4 Polynomials Nonnegative on Strips in the Plane 27 4.1 Reduction to a Positive Leading Coefficient...........28 4.2 Additional Results........................34 4.3 Representations of f by Analytic Functions...........35 4.4 Proof of Theorem 4.1.......................37 5 Conclusion and Future Work 42 Bibliography 44

List of Figures 2.1 S = {x −x 2 , y,1 −xy}......................12 2.2 The strip [0,1] ×R........................13 3.1 Half-strip [0,1] ×R + .......................16 3.2 Half-strip cut by parabola y = x 2 ................18 3.3 Half-strip cut by xy = 1.....................19 3.4 Half-strip cut by xy = 1 and xy = 2...............22 3.5 Half-strip in R 3 ..........................24 3.6 Half-strip cut by y 2 = x.....................26 4.1 Multiple Strips K = [0,1] ∪[2,3] ×R..............41 5.1 “strip” {(x,y) ∈ R 2 | x −x 2 ≥ 0,y 2 −q 2 (x) ≥ 0}........43 5.2 “strip” cut by finitely many polynomials in R[x]........43

1 Cha pter 1 Introduction In 1900,Hilbert posed his 17th problem,asking whether every real polyno- mial f in n variables that is nonnegative on R n can be written as a sum of squares of rational functions.In 1927,Artin [1] gave an affirmative answer to Hilber’s 17th Problem.A natural question to ask is what would happen if we change the condition “f ≥ 0 on R n ” by some other positivity condition, for example,f ≥ 0,or f > 0 on some subset K of R n . Given a finite subset S = {g 1 ,...,g r } ⊆ R[x 1 ,...,x n ] =:R[X],the basic closed semialgebraic set K S associated to S is K S := {α ∈ R n | g i (α) ≥ 0,i = 1,...,r}, and the preordering T S of R[X] generated by S is T S := {

ǫ∈{0,1} r s ǫ g ǫ 1 1 ...g ǫ r r }, where s ǫ is a sum of squares of polynomials in R[X] for all ǫ ∈ {0,1} r . Since sums of squares of polynomials in R[X] are globally nonnegative,and the g i are nonnegative on K S ,f ∈ T S implies that f is nonnegative on K S , and a representation of f in T S ,i.e.,f =

ǫ∈{0,1} r s ǫ g ǫ 1 1 ...g ǫ r r ,is an algebraic identity certifying that f is nonnegative on K S . Fix S as above.In 1991,Schm¨udgen [17] proved that if K S is compact and f ∈ R[X] such that f > 0 on K S ,then f ∈ T S ,i.e.,there always exists an algebraic expression proving that the given polynomial f is positive on K S . In general Schm¨udgen’s result does not hold if the condition “f > 0 on K S ” is replaced by “f ≥ 0 on K S ”.

2 An obvious question to ask is:What happens when K S is not compact? In 1999,Scheiderer [15] showed that if K S is not compact and its dimen- sion is 3 or more,there is no analogue of Schm¨udgen’s Theorem.Then in 2002,Kuhlmann and Marshall [6] proved that there is a result similar to Schm¨udgen’s Theorem for a noncompact set K S ⊆ R,provided that S con- tains the “right” set of generators for K S . In the noncompact two-dimensional case,very little is known about when every f positive or nonnegative on a noncompact set K S ⊆ R 2 has an alge- braic expression proving that f is nonnegative on K S ,i.e.,f > 0 or f ≥ 0 implies that f ∈ T S .Recently,M.Marshall showed that if f ∈ R[x,y] is nonnegative on the strip [0,1] ×R ⊆ R 2 ,then f ∈ T S ,where S = {x,1 −x}. This is a stronger result than Schm¨udgen’s Theorem,as Marshall proved that the preordering in this case contains all polynomials nonnegative on K S . In this thesis,we explore representations of polynomials that are nonneg- ative on some noncompact subsets of the plane.Our work concerns gener- alizations of Marshall’s result and an attempt to characterize noncompact semialgebraic sets for which there is a corresponding finitely generated pre- ordering which contains all polynomials nonnegative on the set. In Chapter 3,we generalize Marshall’s theorem to the half-strip situa- tion,by which we mean noncompact basic closed semialgebraic subsets of the form {(x,y) | 0 ≤ x ≤ 1,g(x,y) ≥ 0} which are bounded as y → −∞. We show that if f ∈ R[x,y] is nonnegative on certain types of half-strips in the plane,then f ∈ T S ,provided we choose the “right” set of generators S. The proof of the theorem involves two steps of reduction:first to the case [0,1] × R + and secondly to the strip [0,1] × R,and then using Marshall’s theorem on the strip.Combining this half-strip result with a substitution technique fromScheiderer’s work [16],we obtain more examples of half-strips for which the corresponding preorderings contain all nonnegative polynomi- als.Then we end this chapter with a family of examples of half-strips for

3 whic h no corresponding finitely generated preordering contains all positive polynomials. In Chapter 4,we give another generalization of Marshall’s result by showing that if f ∈ R[x,y] such that f(x,y) ≥ 0 on U ×R,where U ⊆ R is compact, i.e.,U × R consists of multiple strips in the plane,then f ∈ T S ,again provided we choose the right set of generators.The proof uses generalizations of Marshall’s arguments.The idea of the proof is to get representations of f on some small strips covering U × R,where the representations use the generators and sums of squares of polynomials in y whose coefficients are analytic functions of x defined in some open neighborhoods of these small strips.Then we apply a version of the Weierstrass Approximation Theorem to obtain a polynomial representation of f(x,y) in T S . Finally we end this thesis with Chapter 5,where we summarize our work and propose a list of open problems.

4 Cha pter 2 Preliminaries Fix n ∈ N and let R[X]:= R[x 1 ,...,x n ] be the ring of polynomials in n variables over R.For the special cases n = 1 and n = 2,we use R[x] and R[x,y],respectively.Throughout,R + denotes the nonnegative elements of R,and R >0 denotes the strictly positive elements of R. 2.1 Positivity and Sums of Squares We say that a polynomial f ∈ R[X] is positive semidefinite,or psd,if f(α) ≥ 0 for all α ∈ R n .A polynomial f ∈ R[X] is a sum of squares,or sos,if f =

k i=1 g 2 i ,for g 1 ,...,g k ∈ R[X].We write

R[X] 2 for the set of sums of squares in R[X].Obviously,f sos implies that f is psd,since squares in R are nonnegative.The converse,in general,is not true.Also,writing f as a sum of squares gives an algebraic identity proving that f is psd. It has been well-known since the late 19th century that in the one variable case,f psd implies f sos.This follows from the Fundamental Theorem of Algebra: Theorem 2.1.If f(x) ∈ R[x] is psd,then f(x) is a sum of two squares in R[x].

5 Pr oof.Factor f(x) in C[x].Since f ≥ 0 on R,real roots appear to even degree,and complex roots appear in conjugate pairs.Thus,we have f(x) =

c(x −z j )(x − ¯z j ), where c ∈ R + .Let g =

(x −z j ) and write g = g 1 +ig 2 ,with g 1 ,g 2 ∈ R[x]. Then f = c(g 2 1 +g 2 2 ). If deg f = 2,it is easy to see that f is sos,using diagonalization of psd quadratic forms.In 1888,Hilbert [4] proved the following remarkable theo- rem: Theorem 2.2 (Hilbert).Suppose f is psd of degree 4 in two variables,then f is sos.For all other cases,there exist psd f which are not sos. However,Hilbert did not give an explicit example of a psd polynomial that is not sos.The first published examples did not appear until the 1960s,and the most famous is the Motzkin polynomial [9] from 1967: x 4 y 2 +x 2 y 4 −3x 2 y 2 +1 In 1893,Hilbert [5] proved that for n = 2 every psd polynomial in R[X] can be written as a sum of squares of rational functions.Unable to answer the general question of whether every psd polynomial is a sum of squares of rational functions,it became the 17th problemon Hilbert’s list of 23 problems he gave in his address to the International Congress of Mathematicians in 1900.In 1927,E.Artin [1] gave an affirmative solution to Hilbert’s 17th problem. Theorem 2.3 (Artin 1927).Suppose f ∈ R[X] is psd.Then there are polynomials g i ,i = 1,...,k,and a nonzero h ∈ R[X] such that f =

g 1 h

2 + +

g k h

2

6 Note that an identity f =

g 1 h

2 + +

g k h

2 is an algebraic expression showing that f is psd. What can be said if we replace the condition “f ≥ 0 on R n ” by f ≥ 0 on some subset K of R n ?In particular,we consider semialgebraic subsets, which are the sets of solutions of some finite system of polynomial equations and inequalities. A subset of R n is called basic semialgebraic if it is the set of solutions of a finite system of polynomial equations and inequalities,and semialgebraic if it is a finite union of basic semialgebraic sets.One checks easily that a subset of R is semialgebraic if and only if it is a finite union of points and intervals. In classical algebraic geometry,the key idea is to associate algebraic objects – the ideal – with the geometric objects – varieties.In real algebraic geometry, the geometric objects are semialgebraic sets,and the corresponding algebraic objects are preorderings and quadratic modules. We are interested in quadratic modules and preorderings in R[X] associated to basic closed semialgebraic sets.Given a finite subset S = {g 1 ,...,g s } of R[X].Recall that the basic closed semialgebraic set K S generated by S is K S := {x ∈ R n | g i (x) ≥ 0,i = 1,...,s}. The quadratic module M S generated by S is M S := {σ 0 +σ 1 g 1 + +σ s g s | σ i ∈

R[X] 2 for all i = 0,...,s}, and the preordering T S generated by S is T S :=   

e∈{0,1} s σ e g e | σ e ∈

R[X] 2 for all e ∈ {0,1} s    , where g e := g e 1 1 ...g e s s ,if e = (e 1 ,...,e s ).The preordering T S is a quadratic

7 mo dule generated by products of the g i ’s.Notice that an identity f =

ǫ∈{0,1} r s ǫ g ǫ 1 1 ...g ǫ r r in T S is an algebraic identity certifying that f is nonnegative on K S . Note that if M S is the quadratic module (respectively,preordering T S ) of R[X] generated by S,and I is the ideal of R[X] generated by h 1 ,...,h t ,then M+I is the quadratic module (respectively,preordering) of R[X] generated by g 1 ,...,g s ,h 1 ,−h 1 ,...,h t ,−h t . The preordering R[X] 2 +I of R[X] is generated (as a quadratic module or as a preordering) by h 1 ,−h 1 ,...,h t ,−h t . Fix S as above.In 1991,Schm¨udgen [17] proved a remarkable theorem that created quite a stir in the community and gave rise to new directions in research. Theorem 2.4 (Schm¨udgen’s Positivstellensatz).Given a finite set S ⊆ R[X].If K S is compact,then for any f ∈ R[X], f > 0 on K S ⇒f ∈ T S . In other words,the theorem says that if f > 0 on a compact basic closed semialgebraic set K S ,there always exists an algebraic expression proving the positivity condition.In general,Schm¨udgen’s result does not hold if the condition “f > 0 on K S ” is replaced by “f ≥ 0 on K S ”,as the following example shows. Example 2.5.[7,2.7.3].Take n = 1 and S = {−x 2 }.Then K S is the singleton set {0}.Clearly,x ≥ 0 on K S .Assume that x ∈ T S ,so x can be written as x = s 0 +s 1 (−x 2 ),

8 where s 0 , s 1 are sums of squares in R[x].Evaluating at x = 0 yields that s 0 (0) = 0.As s 0 ∈

R[x] 2 ,write s 0 =

g 2 i ,where g i ∈ R[x].Then s 0 (0) = 0 implies that

g i (0) 2 = 0,which means g i (0) = 0,for every i. Hence we can factor g i as g i = h i x,with h i ∈ R[x] and deg h i ≤ deg g i .This implies that s 0 =

g 2 i =

(h i x) 2 =

(h i ) 2 x 2 .Thus,we have x =

(h i ) 2 x 2 +s 1 (−x 2 ). Dividing x on both side of the equation yields 1 =

(h i ) 2 x −s 1 x = (

h 2 i −s 1 )x, which is not possible. Hence,x is not in the preordering T S . An obvious question to ask is:What happens when K S is not compact?It turns out that,unlike the compact case,the answer depends on choosing the right set of generators. Definition 2.6.Given U ⊆ R,a basic closed semialgebraic set.Then U is finite union of closed intervals and points.As in [6],we define the natural set of generators S for U as follows: (1) If U is compact,then U = [a 1 ,b 1 ] ∪ ∪ [a k ,b k ],where a i ,b i ,∈ R with i = 1,...,k,and a 1 ≤ b 1 < a 2 ≤ b 2 < < a k ≤ b k ∈ R.Let S = {x −a 1 ,(b 1 −x)(a 2 −x),...,(b k−1 −x)(a k −x),b k −x}. (2) If U is noncompact,then S is defined as follows: • If a ∈ U and (−∞,a) ∩U = ∅,then x −a ∈ S. • If a ∈ U and (a,∞) ∩U = ∅,then a −x ∈ S. • If a,b ∈ U,a < b and (a,b) ∩U = ∅,then (x −a)(x −b) ∈ S • Other than the above,S has no other elements.

9 Clearly ,in both case,K S = U. For example,the natural set of generators of {−1} ∪[0,1] ∪[2,∞) is {x+1,(x+1)x,(x−1)(x−2)},and the natural set of generators for [0,1]∪[2,3] is {x,(1 −x)(2 −x),3 −x}. Definition 2.7.(i) Set T alg S = {f ∈ R[X] | f ≥ 0 on K S }.The set T alg S is a preordering,called the saturation of T S .We say T S is saturated if T S = T alg S . (ii) The closure of a quadratic module M S ⊆ R[X] is defined to be the closure of M S in the unique finest locally convex topology on R[X],and M S is said to be closed if M S = M S . (iii) We say that M S has the strong moment property,or (SMP),if M S = M alg S . In 1999,Scheiderer [15] gave a negative result for the dim K S ≥ 3 case. Theorem 2.8 (Scheiderer,1999).Suppose K S is not compact,and dim K S is 3 or more.Then there always exists a polynomial that is strictly positive on K S but not in the preordering T S ,regardless of the choice of generators S. Then in 2002,Kuhlmann and Marshall [6] settled the case where K S ⊆ R is noncompact. Theorem2.9.[6,Theorem 2.2] Suppose S ⊆ R[x],and K S is a noncompact subset of R.Then T S is saturated if and only if S contains the natural set of generators. We begin by showing that if S ⊆ R[x] and K S is compact,then T S is saturated.We will need this result for our main theorem (Theorem 4.1) in Chapter 4.This result is probably well-known to experts,but we were unable to find a proof in the literature.The proof is a generalization of the proof of Theorem 2.9.

10 Prop osition 2.10.Suppose U ⊆ R is a compact set,and S is the natural set of generators for U.If f(x) ∈ R[x] is nonnegative on U,then f is in the preordering T S .In other words,T S is saturated. Proof.We have U = [a 1 ,b 1 ] ∪ ∪[a k ,b k ],where a i ,b i ,∈ R with i = 1,...,k, and a 1 ≤ b 1 < a 2 ≤ b 2 < < a k ≤ b k .Recall by Definition 2.6 that the natural set of generators S for U is S = {x −a 1 ,(b 1 −x)(a 2 −x),...,(b k−1 −x)(a k −x),b k −x} Suppose f is a polynomial in R[x] of degree d and f ≥ 0 on K S .Then f can be written as a product of psd quadratic polynomials times a product of linear polynomials in R[x].Since each psd quadratic polynomial is a sum of squares in R[x],without lost of generality,we can reduce to the case where f is a product of linear polynomials in R[x]. We will prove the proposition by induction on d,the degree of f.If d = 0, then f = a ∈ R with a > 0.In this case,f is clearly in T S .Hence we may assume d ≥ 1.If f ≥ 0 on R,then f ∈

R[x] 2 by Theorem 2.1.Thus we can assume that f(c) < 0 for some c ∈ R and consider the following 3 cases: Case 1:c < a 1 .In this case,as f changes sign in the interval (c,a 1 ], there must be a least root r of f in (c,a 1 ].Write f = (x − r)f 1 ,where f 1 ∈ R[x] is of degree d − 1.As a 1 − r ≥ 0 and x − a 1 ∈ T S ,we have x − r = (x − a 1 ) + (a 1 − r) ∈ T S .Since f ≥ 0 on K S and x − r ∈ T S , this forces f 1 ≥ 0 on K S .Then f 1 ∈ T S by the induction hypothesis.Thus, f ∈ T S . Case 2:b i ≤ c ≤ a i+1 .Since f(c) < 0 by assumption while f ≥ 0 on K S with b i ,a i+1 ∈ K S ,there must be a greatest root r 1 in the interval [b i ,c) and a least root r 2 in the interval (c,a i+1 ].Thus b i ≤ r 1 < c < r 2 ≤ a i+1 .Write f = (x −r 1 )(x −r 2 )f 1 ,where f 1 ∈ R[x] is of degree d −2. By [2,Lemma 4],since b i ≤ r 1 < r 2 ≤ a i+1 ,the product (x −r 1 )(x −r 2 ) is in the preordering generated by (x −b i )(x −a i+1 ).In particular,we have

11 (x −r 1 )(x −r 2 ) ∈ T S , as (x −b i )(x −a i+1 ) is in T S . Using an argument similar to that in Case 1,it follows that f 1 ∈ K S ,and and subsequently f is in T S . Case 3:b k < c.By a similar argument in the above cases,there must exist a greatest root r in the interval [b k ,c).Write f = (r − x)f 1 ,where f 1 (x) ∈ R[x] is of degree d −1.As r −b k ≥ 0 and b k −x ∈ T S ,it follows that (r −x) = (b k −x) +(r −b k ) ∈ T S .Since f ≥ 0 on K S and x −r ∈ T S , this implies that f 1 ≥ 0 on K S .Then f 1 ∈ T S by the induction hypothesis. Thus,f ∈ T S . Remark 2.11.Note that this is a stronger result than Schm¨udgen’s Pos- itivstellensatz (Theorem 2.4),since Schm¨udgen’s Positivstellensatz tells us that f strictly positive on a compact set K S holds in this case,but it does not imply that T S is saturated. 2.2 Nonnegative Polynomials in R 2 Fix S = {g 1 ,...,g r } ⊆ R[x,y].Recall that T S is saturated if f ≥ 0 on K S implies f ∈ T S .Define the following property of T S : (*) For all f ∈ R[x,y],f > 0 on K S implies f ∈ T S . Schm¨udgen’s Theorem (Theorem 2.4)says that if K S is compact,then (*) holds.Obviously,if T S is saturated,then (*) holds for T S .Example 2.5 shows that the converse is not true in general. We focus on noncompact subsets of R 2 .In 2000,by work of Powers and Scheiderer [14],and independently proven by Kuhlmann and Marshall [6],if K S ⊆ R 2 is not compact and contains a 2-dimensional cone,then (*) never holds,regardless of the choice of generators S.

Full document contains 58 pages
Abstract: In 1991, Schmüdgen proved that if f is a polynomial in n variables with real coefficients such that f > 0 on a compact basic closed semialgebraic set K ⊆ [Special characters omitted.] Rn , then there always exists an algebraic expression showing that f is positive on K. Then in 1999, Scheiderer showed that if K is not compact and its dimension is 3 or more, there is no analogue of Schmüdgen's Theorem. However, in the noncompact two-dimensional case, very little is known about when every f positive or nonnegative on a noncompact basic closed semialgebraic set K ⊆ [Special characters omitted.] R2 has an algebraic expression proving that f is nonnegative on K. Recently, M. Marshall answered a long-standing question in real algebraic geometry by showing that if f ∈ [Special characters omitted.] R [x, y ] and f ≥ 0 on the strip [0, 1] × [Special characters omitted.] R , then f has a representation f = σ0 + σ1x (1 - x ), where σ0 , σ1 ∈ [Special characters omitted.] R [x, y ] are sums of squares. This thesis gives some background to Marshall's result, which goes back to Hilbert's 17th problem, and our generalizations to other noncompact basic closed semialgebraic sets of [Special characters omitted.] R2 which are contained in strip. We also give some negative results.