Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

How are polynomials called that are positive for all positive, real arguments, e.g., xy + z?

How can one determine if a polynomial has this property?

share|improve this question
    
The answer to the second half of your question is probably Sturm's Theorem, see en.wikipedia.org/wiki/Sturm%27s_theorem –  Roland Bacher Jun 15 '11 at 11:19
    
@Roland, I thought Sturm's Theorem applied only to polynomials in one variable. –  Gerry Myerson Jun 15 '11 at 12:38
1  
Please read the introduction of arXiv:1010.3465v1 [math.AG] –  Claudio Gorodski Jun 15 '11 at 13:27
    
@Claudio, seems like the paper is only about the stronger property that the polynomial is positive (or non-negative) for all arguments, not only for all positive arguments. –  ccom Jun 15 '11 at 13:38
4  
@ccom You can probably apply that paper to P(x^2,y^2,...) –  Laurent Berger Jun 15 '11 at 14:35
show 2 more comments

4 Answers

up vote 5 down vote accepted

A matrix $A$ such that $x'Ax\geq 0$ for all $x$ is called positive semidefinite. A matrix $A$ such that $x'Ax\geq 0$ for all $x\geq 0$ (componentwise) is called copositive. While positive semidefiniteness is easy to test algorithmically, the weaker condition of copositivity is co-NP-complete to test.

Up to some details about strict vs. nonstrict inequalities which I do not think will be crucial, testing copositivity is an instance of the problem you propose, so we should expect this problem to be NP-hard. That is, we should not expect an efficient general procedure for solving it.

There are algorithmic techniques such as sums-of-squares and semidefinite programming which can in practice certify positivity of many polynomials (globally, or as you want here, on sets such as the positive orthant) quickly, but except in very special cases the efficiency of these methods is not guaranteed.

share|improve this answer
    
How does it relate to checking positive definiteness of P(x1^2, x2^2, ...), as Laurent Berger suggested? –  ccom Jun 15 '11 at 21:03
    
After appropriate simplifications to take into account the newly-introduced symmetries (the new polynomial will be invariant under all maps $x_i\mapsto -x_i$), the approaches are essentially equivalent. –  Noah Stein Jun 16 '11 at 1:06
    
I learned about these things from my advisor Pablo Parrilo's course "Algebraic Techniques and Semidefinite Optimization" (notes at stellar.mit.edu/S/course/6/sp10/6.256). If that link doesn't work (it may require some MIT credentials) I believe he has an older version of the course notes on MIT OCW. –  Noah Stein Jun 16 '11 at 9:22
    
Thank you very much, Noah. –  ccom Jun 16 '11 at 13:44
    
You're welcome; I'm glad I could help. –  Noah Stein Jun 16 '11 at 15:50
add comment

I am not sure what they are called, but let's call them positive for now.

I also don't know if there is a really good criterion for deciding whether a polynomial is positive, but here is what I would try:

Let $f$ be the polynomial in question. If you can determine the zero set of the polynomial, then basically you are in business. This zero set will cut up the space into connected cells (not necessarily bounded) and in each of these cells the sign of the values will be constant. Also, I think there should be only finitely many such cells, so you would have to check only finitely many values to know where your polynomial is positive.

Of course, finding the zero set may not be simple and finding the cell decomposition may be even harder, but if your polynomial is somewhat special you might get lucky.

For example if $f(x,y,z)=xy+z$ then the zero set is $$ Z(f)=\{(x,y,-xy)| (x,y)\in \mathbb R^2\}\subset \mathbb R^3 $$ The corresponding cell decomposition is $$ \mathbb R^3= Z_+\cup Z(f) \cup Z_- $$ where $$ Z_+=\{(x,y,-xy+a)| (x,y)\in \mathbb R^2, a\in\mathbb R_+\}\subset \mathbb R^3 $$and $$ Z_-=\{(x,y,-xy-a)| (x,y)\in \mathbb R^2, a\in\mathbb R_+\}\subset \mathbb R^3 $$ and so it is enough to check that $f(1,1,1)>0$ and $f(1,1,-1)<0$ to see that $f|_{Z_+}>0$ and $f|_{Z_-}<0$. Finally you check that $$ Z_+\supseteq \mathbb {R_+\times R_+ \times R_+} $$


If finding the zeros seems to be too difficult there is one more thing you can try. Fix the value of one variable and see if the one smaller dimensional problem is solvable. Then you "only" have to do it for every positive value of that one variable.

In the above example this would work out like this:

For an $c\in\mathbb R_+$ let $$f_c(x,y):=f(x,y,c)=xy+c$$

Now the zero set of $f_c$ is $$ Z(f_c)=\{(x, -\frac cx) | x\in \mathbb R\}. $$ For this the cell decomposition is easy (left to the reader) and it can be easily seen that $f_c$ is positive for any $c$. I suppose you can iterate this, although it will become increasingly more difficult to see how the value does or does not depend on the fixed variables. In any case, this is at least something to try.

share|improve this answer
    
Thanks, Sándor. Unfortunately, the zero set is difficult to determine, and fixing a variable, also. They're polynomials of high degree and of many (>10) variables. –  ccom Jun 15 '11 at 16:25
add comment

As mentioned, $P(x,y,z)$ being positive for positive x,y,z is the same as $P(x^2,y^2,z^2)$ always being positive, so we can just consider the case of positive polynomials. The single-variable case is a lot easier since a polynomial being non-negative is equivalent to it being a sum of squares, and there are good algorithms for decomposing a polynomial (even multivariate) as a sum of squares. There's an overview of this at: http://junction.stanford.edu/~lall/data/engr210b_0405/sum_of_squares_2004_11_07_01.pdf

In the multivariable case the positivstellensatz (also see: Hilbert's Seventeenth Problem http://en.wikipedia.org/wiki/Hilbert%27s_seventeenth_problem) tells us that the polynomial isn't necessarily a sum of squares, but that if you multiply it by some appropriate square you can get a sum of squares. These polynomials are sometimes called (semi-)definite polynomials.

We have no real good way of recognizing definite polynomials, which is to be expected since this problem is NP-complete (you can encode SAT in terms of arithmetic on variables being 0 or 1)

share|improve this answer
add comment

In the case of a quadratic form they are called positive definite and you can tell if a homogeneous quadratic form has this property by looking at the eigenvalues of the matrix that defines it. In general for a non homogeneous one you could use calculus.

share|improve this answer
    
I think you missed the "positive" in "positive real arguments." –  Qiaochu Yuan Jun 15 '11 at 11:14
    
O yes I did, i will edit. –  Oliver Jun 15 '11 at 11:21
    
I'm probably missing something. How do I use calculus in case effectively? Suppose I have a homogeneous polynomial of degree 6 in 12 variables. –  ccom Jun 15 '11 at 11:52
1  
This property isn't equivalent to positive-definite for quadratic forms. For example, $xy$ has the desired property but is not positive-definite. –  Qiaochu Yuan Jun 15 '11 at 12:28
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.