Xref: utzoo sci.math:10167 comp.theory:417
Path: utzoo!utgpu!jarvis.csri.toronto.edu!cs.utexas.edu!usc!ucla-cs!math.ucla.edu!vijayaraghavan!dgc
From: dgc@vijayaraghavan.math.ucla.edu (David G. Cantor)
Newsgroups: sci.math,comp.theory
Subject: Re: polynomials
Message-ID: <2335@sunset.MATH.UCLA.EDU>
Date: 5 Mar 90 17:22:30 GMT
References: <4499@ucrmath.UCR.EDU>
Sender: news@MATH.UCLA.EDU
Reply-To: dgc@math.ucla.edu (David G. Cantor)
Organization: UCLA Department of Mathematics
Lines: 36
CC:             Marek Chrobak <marek@ucrmath.ucr.edu>
CC:             dgc
Summary:
Expires:
Sender:
Followup-To:
Distribution:
Keywords:

In article <4499@ucrmath.UCR.EDU> marek@ucrmath () writes:  We have a
problem that looks pretty classic, but we don't know the solution.

	You are given a polynomial with integer coefficients over
	n variables, p(x_1,... x_n).  You want to know whether the
	polynomial is always non-negative for non-negative values of x_i
	(real values).
------------------------------------------------------------------------
This is closely related to Hilbert Problem 17, solved by Emil Artin.  He
showed that a polynomial with real coefficients is non-negative for all
real values of its variables if and only if it is a sum of squares of
rational functions (not necessarily polynomials) in the same variables. 
Theodore Motzkin gave a simple example of such a polynomial which is not
a sum of squares of polynomials.

For the case here, where the variables are are to be non-negative, then
it follows from Artin's reasoning that a polynomial is non-negative
if and only if it is a sum of squares of rational functions, each one
possibly multiplied by one or more of the (non-negative) variables.

For a "logical" proof, see Abraham Robinson's book on Model Theory.

Constructive methods are available.  In particular, Tarski published a
decision procedure for the real numbers which handles this problem.  The
complexity is quite large however.

In the above any real-closed field can be substituted for the field
of real numbers. 

dgc

David G. Cantor
Department of Mathematics
University of California at Los Angeles
Internet:  dgc@math.ucla.edu
UUCP:      ...!{randvax, sdcrdcf, ucbvax}!ucla-cs!dgc