From: rusin@vesuvius.math.niu.edu (Dave Rusin) Newsgroups: sci.math Subject: Re: Polynomial mappings of cones. Date: 6 May 1998 04:57:58 GMT In article , Jonathan King wrote: >Hello. Suppose f() is a polynomial in N variables, and with integer >coefficients. What is an algorithmic way to tell if f maps the positive cone >(well... non-negative, actually) > >C1: x_1 >= 0 & x_2 >= 0 & ... & x_N >= 0 > >into the cone of non-negative real numbers? Wouldn't this fall under Tarski's elimination of quantifiers? > Is there a particularly simple method if N=1? Well, the degree of f needs to be even and the lead coefficient positive. Then you want to know whether f'(x)=0 implies f(x) >=0. Here I think you must decide what it means to "know" f; let me assume that the coefficients of f are rational so that there is no problem with the computability of "f(x)=0?" Now you could state this as a pair of integer polynomial equations f'(x)=f(x)-y=0. Eliminate x to get a polynomial P which y must satisfy. Apply Sturm sequences or whatever to determine whether P has any negative roots. If not, f is nonnegative at all critical points, hence everywhere. If P(y0)=0 for some y0<0, then for each such y0, compute gcd(f'(x), f(x)-y0) and again use some established technique to see if that gcd has a real root -- if so, then you have not only shown f is somewhere negative, you have even found a spot where f<0; if instead all these gcd's have only complex roots, then f is everywhere positive. I can't believe this procedure is optimal. Note in particular that in order to compute the GCD one must decide at each stage whether or not the remainder is the zero polynomial in x; the coefficients of that polynomial will be polynomials in y0, so ascertaining whether or not they vanish at the one particular value of y0 will require testing whether or not they are multiples of the minimum polynomial of y0 over the integers. Thus we will either have to factor P or be prepared to compute a lot of GCDs with P . There's got to be a better way! I believe there has been some work linking Groebner basis techniques to the elimination of quantifiers, which presumably ties together my comments for the cases N=1 and N>1. dave ============================================================================== From: rusin@vesuvius.math.niu.edu (Dave Rusin) Newsgroups: sci.math Subject: Re: Polynomial mappings of cones. Date: 6 May 1998 17:57:29 GMT Jonathan King wrote: >Hello. Suppose f() is a polynomial in N variables, and with integer >coefficients. What is an algorithmic way to tell if f maps the positive cone >(well... non-negative, actually) > >C1: x_1 >= 0 & x_2 >= 0 & ... & x_N >= 0 > >into the cone of non-negative real numbers? I responded with some detail for the case N=1 which was also requested: > Well, the degree of f needs to be even and the lead coefficient positive. Today Jan Kristian Haugland wrote: >I think you missed that x_1, ..., x_N are all nonnegative. >So sum x_i of degree 1 would work, for example. Right. (I also missed that the original poster explicitly said the coefficients were integers, which makes irrelevant some of the other comments in my first post.) But really I have no idea why I went off the deep end like that. A polynomial of one variable is positive on [0, oo) iff it is positive somewhere and has no real roots on [0, oo). Computing the number of real roots in an interval is well-known and easy. [ The case of functions which are _nonnegative_ on [0, oo) is just a little trickier; you need only compute a sequence of gcd's to write f = f1*f2^3*f3^3*... with the f_i relatively prime; it is then f1, f3, f5, ... which must have no roots on [0, oo). ] I must've just gone off to la-la-land while posting because I had elimination theory on the brain (see sci.math.symbolic). Sorry. dave