11
$\begingroup$

Let

$$P(X,Y)= c_{22}X^2Y^2 +c_{21}X^2Y +c_{12}XY^2 +c_{20}X^2 +c_{11}XY+c_{02}Y^2+c_{10}X+c_{01}Y+c_{00}$$

be a polynomial of two variables $X$ and $Y$ with real coefficients $c_{ij}$.

What are the necessary and sufficient conditions on the coefficients $c_{ij}$ such that $P(X,Y) \geq 0$ for all pairs $(X,Y)$ with $X\geq 0$, $Y\geq 0$?

$\endgroup$
  • $\begingroup$ Why this particular form? $\endgroup$ – Felix Goldberg Sep 22 '14 at 0:24
  • $\begingroup$ I am trying to prove an inequality which originates in a geometric problem. I know that if $Y=X$, that is $P$ is a single variable quartic, there are ways to decide this using the discriminant of the polynomial. Is there something similar for polynomials of two variables? $\endgroup$ – Dan Ismailescu Sep 22 '14 at 0:28
  • $\begingroup$ Can you give me a reference for the quartic case? This is a bit related to copositive matrices (a matrix can be thought of as a homogenous 2nd degree polynomial) but right now I can't offer any tangible result. $\endgroup$ – Felix Goldberg Sep 22 '14 at 0:30
  • $\begingroup$ en.wikipedia.org/wiki/Quartic_function#Nature_of_the_roots $\endgroup$ – Dan Ismailescu Sep 22 '14 at 0:40
  • 1
    $\begingroup$ Thank you Igor; Handelman looks the most promising in my specific case. $\endgroup$ – Dan Ismailescu Sep 22 '14 at 2:14
11
$\begingroup$

There is Stengle's positivensatz,, otherwise, if your polynomial were homogeneous, you could use Polya's theorem, and if you could make your domain compact, you can use Handelman's theorem, but otherwise, Stengle is your man.

For Polya and Handelman see Powers and Reznick:

\bib{MR1854339}{article}{
  author={Powers, Victoria},
  author={Reznick, Bruce},
  title={A new bound for P\'olya's theorem with applications to polynomials
  positive on polyhedra},
  note={Effective methods in algebraic geometry (Bath, 2000)},
  journal={J. Pure Appl. Algebra},
  volume={164},
  date={2001},
  number={1-2},
  pages={221--229},
  issn={0022-4049},
  review={\MR{1854339 (2002g:14087)}},
  doi={10.1016/S0022-4049(00)00155-9},

}

$\endgroup$
  • 2
    $\begingroup$ By homogenizing the polynomial, that is, considering $Z^4P(X/Z,Y/Z)$, you can apply Polya in the inhomogeneous case as well. $\endgroup$ – Peter Mueller Sep 22 '14 at 14:06
  • 1
    $\begingroup$ @PeterMueller Yes, of course, I wasn't thinking (then you are in the orthant in $\mathbb{R}^3.$) The tricky part with all these algorithms is that they are much better at detecting positivity than non-negativity (see the Powers and Reznick paper - their bounds, which look a little horrible at times, are actually sharp, unfortunately). $\endgroup$ – Igor Rivin Sep 22 '14 at 14:10
  • 1
    $\begingroup$ for bivariate polynomials the much better route is outlined in my answer. $\endgroup$ – Dima Pasechnik Sep 23 '14 at 19:03
  • $\begingroup$ Yes but is Polya's theorem to check for positive polynomials? Not for non-negative polynomials? Perhaps you know the answer to this here where I am confused which theorem to use? $\endgroup$ – hhh Jul 23 '16 at 16:28
  • 2
    $\begingroup$ @hhh : indeed, Polya is for checking strict positivity, not nonnegativity. $\endgroup$ – Dima Pasechnik Jul 25 '16 at 10:47
8
$\begingroup$

You can rewrite your polynomial in squared variables (so it will be of degree 8) and homogenise it, obtaining a ternary form of degree 8.

There is a result of Hilbert in Acta Math. 17(1893) that applies here; he shows that a real ternary form of degree $2d$ satisfies $f(x,y,z)\geq 0$ for all $x,y,z$ iff it is representable as the rational function $p(x,y,z)/q(x,y,z)$, with $p$ and $q$ homogeneous globally nonnegative of degrees $4d-4$, resp., $2d-4$, and $p$ being a sum of squares of forms. (the result also says how many terms there are, etc)

Here, as $d=4$, we can assume that $q$ is a sum of squares of forms, as it is of degree 4 (by much more famous Hilbert's result from 1888).

We showed that this can be made into an algorithm, cf. http://www.optimization-online.org/DB_HTML/2001/11/399.html (published here: http://www.sciencedirect.com/science/article/pii/S0377221703005162)

$\endgroup$
  • $\begingroup$ Cool! Does this only work for ternary? $\endgroup$ – Igor Rivin Sep 23 '14 at 19:17
  • $\begingroup$ for more variables nothing of this sort is known; Hilbert's (1893) paper substantially uses quite tricky algebraic geometry of complex plane curves (something that nowadays one would explain using en.wikipedia.org/wiki/Theta_characteristic) $\endgroup$ – Dima Pasechnik Sep 23 '14 at 19:24
  • $\begingroup$ something like this (i.e. one can produce explicit small degrees of s.o.s. forms to multiply with) also works for quaternary forms of degree 4, see arxiv.org/abs/1511.03473 $\endgroup$ – Dima Pasechnik Feb 16 '17 at 21:42
4
$\begingroup$

Here's a trick (which sometimes works), but it might be contained in the comments above. As stated, the Newton polyhedron (convex hull of the exponents, the latter viewed as lattice points in ${\bf R}^2$), $K$, of $P$, is contained in the double unit square in ${\bf R}^2$. First, an obvious necessary condition for nonnegativity: the coefficients of the extreme points of $K$ must be positive (as opposed to negative).

Next, for each edge of $K$, there is a corresponding polynomial (just take the exponents appearing in the edge, and use the coefficients from $P$); if $P$ is nonnegative, each of these edge polynomials must be nonnegative---but after a change of variables, the edge polynomials are really just polynomials in one variable, for which testing for nonnegativity is just the quadratic formula in your example).

This gives some necessary conditions.

Now a sufficient condition for positivity: If $P(x,y) >$ on the interior of the positive orthant, and each of the edge polynomials is positive (which implies the coefficients at the extreme points of $K$ are all positive), then for any $Q$ with the same supporting monomials as $P$ and $Q$ having no nonnegative coefficients, there exists an integer $M$ such that the product, $Q^M P$, has no negative coefficients. (This is a generalization of Polya and Meissner's theorems; when $K$ is the double unit square, this is Meissner's theorem.)

The simplest (but probably not the best) choice for $Q$ is $\sum x^w$ where $w$ varies over the lattice points in $K$ (where $x^w = x_1^{w(1)}x_2^{w(2)}$ is the usual monomial, with $w = (w(1),w(2))$. Another choice is to replace the negative coefficients in $P$ by their absolute value. In any event, you can try testing $Q^m P$ for large (whatever that means in this context) choices of $m$.

And a variation: if you suspect your thing is only nonnegative, add $\epsilon Q = \epsilon \cdot \sum_{w \in K} x^w$ to $P$, where $0 <\epsilon$ is much smaller than all the absolute values of the nonzero coefficients of $P$, and test $Q^m \cdot (P + \epsilon Q)$ for nonnegative coefficients. If succcessful, reduce $\epsilon$. If unsuccessful, increase $\epsilon$; this might give estimates of lower bounds.

The problem, as usual, is that it can't give a negative answer, although it might suggest where to look.

$\endgroup$
  • $\begingroup$ On nonnegativity of polynomial in compact polytope, I am trying to understand very basic example here with Handelman's theorem. Can you instruct? Thank you in advance. $\endgroup$ – hhh Jul 25 '16 at 8:07

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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