From: kovarik@mcmail.cis.McMaster.CA (Zdislav V. Kovarik)
Newsgroups: sci.math
Subject: Re: Checking if a polynomial is a sum of squares
Date: 3 Jun 1998 20:46:52 -0400

In article <357563f7.0@news.rz.uni-passau.de>,
Markus Schweighofer <schweigh@fmi.uni-passau.de> wrote:
>Does anyone know an algorithm which takes an arbitrary element of
>Q[X_1, ..., X_n] and decides whether it is a sum of squares
>in R[X_1, ..., X_n] or not?

Try to re-post in sci.math.research. In addition, look for articles by
Man-Duen Choi, of the University of Toronto. He has written a number of
articles on that.

Good luck, ZVK(Slavek).

[snip]

>For the first question I am even interested in the case n = 1.

Yes: by a rational procedure, you can factor out squares (consider the
greatest common divisor b(x) of p(x) and p'(x) ; every its square-free
divisor c(x) makes p(x) divisible by (c(x))^2 , and you can proceed
recursively).

What is left (call it q(x)) will be a sum of squares if and only if it is
positive everywhere. Why? Subtract the minimum of q(x) from q(x), and the
difference is divisible by a non-constant square, unless q was already
constant. Recursively, you do obtain a constant after finitely many steps.

And then you reconstruct the sum of squares in an obvious way.

(Too bad it does not extend to more than one variable - see Choi's
articles.)

Cheers, ZVK (Slavek).