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