From: rusin@vesuvius.math.niu.edu (Dave Rusin) Subject: Re: roots of polynomials in many variables Date: 27 Feb 1999 08:31:43 GMT Newsgroups: sci.math Keywords: When is a real algebraic variety a bounded set? In article <7b346d$cvk$1@nnrp1.dejanews.com>, wrote: >Definition.- A polynomial is bounded iff there exist a number greater than >the distances to the origin of every of its real roots. Example: P(x)=x^4 - >2x^3 - 3x^2 + 4x + 4 is bounded because 100 is a number greater than the >distances to de origin of the two real roots r_1= -1 , r_2= 2 of the >polynomial. I'm looking for conditions to determine when a polynomial in many >variables with integer coefficients is bounded. All your pointers will be >wellcome. Luis Homero Lavin, lavin5@hotmail.com Please don't refer to "roots" for polynomials of more than one variable. I assume you're refering to the zero-locus, or variety, determined by the polynomial; for example, you know the set described by P(x,y)=0 is a circle (hence bounded) if P(x,y)=x^2+y^2-1 and a hyperbola (hence unbounded) if P(x,y)=x^2-y^2-1. Your question seems to be whether there an algorithm which takes P as input and can determine whether the zero locus is bounded or not. Are you familiar with projective space? This is a topological space which contains Euclidean space but is compact. If that means nothing to you, think of adding some points to space to "close it up", in the sense that a circle can be thought of a copy of the real line (shrunk to an open interval) with both ends approaching an additional point (the "point at infinity"). It's actually more useful to think of projective space a little differently: draw the real line as the line x=1 in the xy-plane, and then observe that all the lines through the origin can be paired off with points on the real line by seeing where the line-through-the-origin meets the line x=1; the vertical line-through-the-origin x=0 is exceptional, and corresponds to the "point at infinity". More generally we can define (as a set, at least) RP^n to be the set of lines through the origin in R^n; most of these lines meet the hyperplane x0=1 (in R^(n+1)) in a unique point, so most of the elements of RP^n can be thought of as elements of R^n, but the vertical lines add some additional points. There is a natural topology (the quotient topology) on RP^n under which it becomes a compact space with R^n as an open subset. There's a different picture of RP^n which is useful: every line through the origin pierces the unit sphere in precisely two points. So we can think of RP^n as being just the n-sphere with the stipulation that antipodal points on the sphere count as a single point of RP^n. So for example a trip from the North Pole to the South Pole counts as a closed loop in RP^2. Here is the application of projective space: given a polynomial P of degree d in n variables, define a polynomial Q of degree d in n+1 variables by Q(x0, ..., xn) = (x0)^d P(x1/x0, ..., xn/x0). Since Q behaves well under scalings of the variables, the zero-locus of Q becomes a well-defined subset of projective space. It's very nearly the same as the zero-locus of P. The big advantage of projective space is that there are other points in the zero-locus of Q besides the points in the zero-locus of P, and that's because RP^n has "points at infinity" not lying in R^n. ASCII is a terrible medium for this, so I encourage you to sketch this as I go along. Put the unit sphere in R^3 with the plane x0=1 tangent to it. Draw on that plane the hyperbola x1^2 - x2^2 - 1. Draw all the lines through the origin which pass through points on the hyperbola. Note where each pierces the sphere (should be exactly one point in each hemisphere x0>0 and x0<0). You should get two circles (one antipodal pair) except that there are some points on the plane x0=0 which appear to be parts of the circles and yet were never touched. Now what you need to know is the a polynomial mapping like Q is a continuous function on projective space, and that (therefore) its zero-locus is closed. That is, limits of points in the zero-locus also lie in the zero-locus. In particular, the zero-locus of Q includes these extra points. In short: the zero-locus of Q is nearly the same as that of P but with extra points. On the other hand, that's pretty obvious: we compute Q(0, a, +-a) = 0 for any a, giving exactly two more lines through the origin which are in the zero locus of Q and which do not lie in the subset R^2 of RP^2. So now we tie this in to your original question. The zero locus of P is precisly the part of the zero locus of Q which lies in the open subset R^n or RP^n. It's unbounded iff it contains points pt1, pt2, ... whose distance from the origin tends to +oo. These points have no limit in R^n, but by compactness, some subsequence of them must converge in the larger space RP^n. By closure, that limit point is now an element of the zero locus of Q which is among the "points at infinity", that is, has x0=0. Conversely, any point in the zero-locus of Q with z0=0 leads to such an unbounded sequence of points in the zero-locus of P (unless this new point is sufficiently isolated; that's getting a little technical). Let's try some examples. If P(x1,x2)=x1^2-x2^2-1, then Q(x0,x1,x2)=x1^2-x2^2-x0^2. If we test with x0=0 we get the condition that x1^2=x2^2 which, as we have said, corresponds to precisely two lines through the origin, giving two "points at infinity". Thus the hyperbola P=0 is unbounded (and in fact heads in two directions: along y=x and along y=-x. The asymptotes correspond to the points at infinity.) If P(x1,x2)=x1^2+x2^2-1, then Q(x0,x1,x2)=x1^2+x2^2-x0^2. When x0=0 we have x1^2+x2^2=0 which can only happen if x1=x2=0, too. This time there is _no_ line through the origin where Q vanishes, i.e. the zero locus of Q contains no "points at infinity". Thus the zero-locus of P must already be bounded. If P(x1,x2)=ax1^2+bx1x2+cx2^2+dx1+ex2+f, then Q(x0,x1,x2)=...[you do it!]. This time, if x0=0 then Q=0 iff ax1^2+bx1x2+cx2^2=0. This equation is satisfied if x1=x2=0, of course, but is only satisfied on some line through the origin if the equation a + b(x2/x1) + c(x2/x1)^2=0 has a real root, i.e., iff b^2-4ac>=0. So that becomes the condition that the zero-locus of Q includes points at infinity, and thus also becomes the condition that the zero-locus of P is unbounded. (Of course as you may know, it also characterizes hyperbolas among the nondegenerate conics). For a related example, consider P(x1,x2)=x1^2+1. This time the zero-locus of P is empty. There is one point at infinity in Q=0, though: x0=x1=0 (with x2 arbitrary) describes a line through the origin where Q vanishes. Nonetheless P=0 _is_ bounded because this point at infinity in Q=0 is isolated. If you want to test for this kind of thing, you can use the implicit function theorem, which guarantees that a point in a zero-locus is never isolated as long as the function Q is regular at these points; what makes this example different is the fact that all the derivatives of Q vanish at this point at infinity. Example: P(x1,x2)=x2^2-(x1^3-4x1). Now Q(x0,x1,x2)=x0 x2^2 - x1^2 + 4 x0 x1 so x0=0 and Q=0 give x1=0, with x2 arbitrary. So the projective curve Q=0 has a point at infinity, and indeed P=0 is unbounded, consisting of an "egg" and a sort of parabolic curve. The projective curve Q=0 adds a point at infinity to the latter, giving two closed loops in RP^2. If you notice the pattern in these examples, you'll see that the principal determinant of whether a curve is bounded or not is the behaviour of the highest-degree terms of the polyomail. (Terms of lower degree in P will be multiplied by a power of x0 in Q so setting x0=0 makes them vanish.) By the way, if P is homogeneous in the first place, you don't need any of this transition to RP^n; simply note that if P vanishes at one point then it vanishes at all multiples of that point too, so the zero-locus of a homogeneous P is never bounded unless it contains only the point (0,0,...0). Try P(x1,x2)=x1^2-x2^2 and P(x1,x2)=x1^2+x2^2 for examples. Projective space is the "right" setting for studying the zero-loci of polynomials. This is domain of Algebraic Geometry, see e.g. index/14-XX.html dave