From: kovarik@mcmail.cis.McMaster.CA (Zdislav V. Kovarik) Subject: Re: Polynomials positive on the real line Date: 12 Apr 1999 01:20:04 -0400 Newsgroups: sci.math In article <37114BE2.E676BF73@psu.edu>, Alan Horwitz wrote: :If p(x) is a quadratic(assume it's monic for simplicity), then it is :easy to show that p is positive on the real line R iff p(x) = (L(x))^2+c :for some linear function L and positive constant c. My question is the :following: Suppose that p has degree n with real coefficients, n even. :What are analagous necessary and sufficient conditions for p to be :positive on R ? In particular, are there fairly simple conditions for n := 4 ? I am not assuming that p is reducible. This depends on how much you want to invest in solving polynomial equations. If you don't mind it, the property can be expressed recursively (and it takes very small mental effort both to formulate it and to prove it): Let n >= 1. A monic polynomial p(x) of degree 2*n, with real coefficients, is positive on the real line iff p(x) = c + (q(x))^2 * r(x) where c>0, q(x) is a non-constant monic polynomial (which can be required to have only real roots), and r(x) is a monic polynomial of an even degree less than 2*n, which is positive on the real line. If you go into the details of the recursion, you get Let n >= 1. A monic polynomial p(x) of degree 2*n, with real coefficients, is positive on the real line iff it is the sum of a positive constant and of a list of squares of polynomials of strictly decreasing degrees (the condition being vacuous if there is only one such square). There is another test, which requires only rational operations on the coefficients of the polynomial; it uses Sturm sequence, and in the process of finding it, one will also discover repeated divisors of p(x). Cheers, ZVK(Slavek). ============================================================================== From: Alan Horwitz Subject: Polynomials Positive on the Real Line Date: Fri, 23 Apr 1999 16:21:58 -0400 Newsgroups: sci.math.research, sci.math Here was my original question, followed by a summary of some of the responses. For fixed even n, define the set NZR = polynomials p of degree n, which are nonzero on the real line R. Are there necessary and sufficient conditions for p to be in NZR of the following form: Finitely many inequalities of the form p_1(a_0,...,a_n) > 0(or < 0), ..., p_m(a_0,...,a_n) > 0(or < 0), where a_0,...,a_n are the coefficients of p and the p_k are polynomials ? The p_k should only depend on n, and not on the particular polynomial p. One approach mentioned was to use results of Tarski, and in particular Tarski's quantifier elimination theory. Others mentioned the use of Sturm sequences, though it was not clear whether this would give inequalities independent of p. Alexei Uteshev provided much useful information. First he cited the following references: 1. Uteshev,A.Yu. and Shulyak,S.G. 1992. Hermite's Method of Separation of Solutions of Systems of Algebraic Equations and Its Applications, Linear Algebra and Its Applications 177:49-88 2. Kalinina,E.A. and Uteshev,A.Yu. 1993. Determination of the Number of Roots of a Polynomial Lying in a Given Algebraic Domain, Linear Algebra and Its Applications 185:61-81 3. Uteshev,A.Yu. and Cherkasov, T.M. 1998. The Search for the Maximum of a Polynomial, J.Symbolic Computation 25(5):587-618 He also provided the following for sign-definiteness(no real roots) of x^4+A_1*x^3+A_2*x^2+A_3*x+A_4, which uses Sturm's theorem or Hankel matrices: S$_{1}$=4,S$_{2}$=3A$_{1}^{2}$-8A$_{2}$,S$_{3}$=36I$_{3}$+2S$_{2}$I$_{2}$,S$_{4}$=4I$_{2}^{3}$-27I$_{3}^{2}$, I$_{2}$:=4A$_{4}$-A$_{1}$A$_{3}$+$\frac{1}{3}$A$_{2}^{2}$,\newline{}, I$_{3}$:=-A$_{3}^{2}$-A$_{1}^{2}$A$_{4}$+$\frac{8}{3}$A$_{2}$A$_{4}$+I$_{3}$:=-A$_{3}^{2}$-A$_{1}^{2}$A$_{4}$+$\frac{8}{3}$A$_{2}$A$_{4}$+IfS$_{4}\ne $0,thenF(x)\TEXTsymbol{>}0iffS$_{4}$\TEXTsymbol{>}0,S$_{2}$\TEXTsymbol{<}0,S$_{3}$\TEXTsymbol{<}0 IfS$_{4}$=0thenF(x)\TEXTsymbol{>}0iffS$_{4}$=0,S$_{3}$=0,S$_{2}$\TEXTsymbol{<}0 ============================================================================== [I think that is intended to be: $S_1=4, S_2=3 A_1^2-8 A_2, S_3=36 I_3+2 S_2 I_2, S_4=4 I_2^3 -27 I_3^2,$ $I_2:=4 A_4 - A_1 A_3 +\frac{1}{3} A_2^2, I_3:=- A_3^2 -A_1^2 A_4 +\frac{8}{3} A_2 A_4 + $ %something missing? If $S_4 \ne 0$, then $F(x)>0$ iff $S_4>0, S_3<0, S_2<0 $ If $S_4=0$, then $F(x)>0$ iff $S_4=0, S_3=0, S_2<0 $ --djr] ============================================================================== From: greg@math.ucdavis.edu (Greg Kuperberg) Subject: Re: Polynomials Positive on the Real Line Date: 26 Apr 1999 11:40:34 -0700 Newsgroups: sci.math.research In article <3720D665.17A14970@psu.edu>, Alan Horwitz wrote: >Here was my original question, followed by a summary of some of the >responses. For fixed even n, define the set NZR = polynomials p of >degree n, which are nonzero on the real line R. It is worth pointing out that the set of such polynomials forms a convex cone. The extremal rays of (the closure of) this cone consists of the polynomials which are squares of other polynomials. Any other such polynomial is a sum of two squares. Another way to say it is that an element p(x) of R[x] is a sum of two squares if and only if each prime factor in R[x] which remains prime in C[x] appears an even number of times. This is exactly analagous to the criterion for an integer to be a sum of two squares, i.e. that each rational prime factor which is a Gaussian prime should appear an even number of times. The whole story is false for polynomials in more than one variable. There are positive polynomials which are not a sum of squares. This may be related to the fact that R[x,y] is not a PID. Anyway, the polynomials which are squares of other polynomials form an algebraic set. Consequently the convex hull is a semi-algebraic set. This may clarify the "necessary and sufficient conditions" that Alan requested. -- /\ Greg Kuperberg (UC Davis) / \ \ / Visit the Math Archive Front at http://front.math.ucdavis.edu/ \/ * All areas of mathematics, all the time * ============================================================================== From: hrubin@stat.purdue.edu (Herman Rubin) Subject: Re: nonnegative polynomials and linear maps of cones Date: 24 Jun 1999 13:42:54 -0500 Newsgroups: sci.math.research In article , Dima Pasechnik wrote: >Dear all, >A polynomial f(x)=f(x_1...x_n) in n (real) variables is >called nonnegative if f(x)>= 0 for all x. >For n=1 a complete description of such polynomials is known: >f is nonnegative iff it is represented as a sum of squares >of polynomials. >What can one say for n>1 ? >17-th Hilbert conjecture (already >proved), says that f is nonnegative iff it is represented as >a sum of squares of rational functions. Are there any good bounds on >the degrees of that rational functions (even for particular small >deg(f) and n?) >Second question. Note that for a given n and maximal degree d of f's, >the coefficients of such polynomials form a cone C(n,d) in R^k >for appropriate k. >For n=1, there is a linear map from the cone S^(m+1) of positive >semidefinite (m+1)x(m+1)-matrices to C(1,2m). >(it is given by the following >mapping of the matrix Y to the polynomial in t:=x_1: >Y |-> eYe^T, for e=(1 t t^2 ... t^m)) >What about n>1 ? (or even n=2 ?) >What kind of technique one could employ for >showning (non)-existense of such maps from S^m to C(n,d)? >Even for particular (small) values of n and d. There is some of this in the literature on the moment problem. I do not believe the extreme non-negative polynomials in two variables are well known, if indeed the problem has been solved. A necessary and sufficient condition that there exists a measure with given moments is that the linear operator on all non-negative polynomials is non-negative, which provides the connection. -- This address is for information only. I do not claim that these views are those of the Statistics Department or of Purdue University. Herman Rubin, Dept. of Statistics, Purdue Univ., West Lafayette IN47907-1399 hrubin@stat.purdue.edu Phone: (765)494-6054 FAX: (765)494-0558