15
$\begingroup$

I'm looking for a necessary and sufficient conditions (I'm not even sure these exist) for a polynomial $p:\mathbb{R}^n\to\mathbb{R}$ to be "radially unbounded", that is

$$\|x\|\to\infty\implies p(x)\to\infty,$$

where $\|{\cdot}\|$ denotes any $p$-norm on $\mathbb{R}^n$. Ideally, I'm looking for conditions in terms of the polynomial's coefficients and degree.

For example, if $n=1$ it is straightforward to see that $p$ is radially unbounded if and only if its degree is even and the monomial of highest degree has a positive coefficient.

However, I'm struggling to generalise this to arbitrary $n$. Any help would great.

Motivation: I'm interested in the above because I'm trying to come up with an automatised test that can decide whether or not the all the sublevel sets of a given polynomial are compact (this is so if and only if the polynomial is radially unbounded).


Edit: If no necessary and sufficient conditions (or argument that no such conditions exist in general) are posted before the bounty ends, I'd be more than happy to award the bounty to any answer containing insightful remarks or necessary or sufficient conditions.

$\endgroup$
7
  • $\begingroup$ Is it so easy as to just restrict to each variable and do the $(n=1)$-check, or do you have some counterexamples where this doesn't work? (At least it's a simple, necessary condition.) $\endgroup$
    – Arthur
    Oct 9 '13 at 13:33
  • $\begingroup$ @Arthur Think of $p(x)=(x_1-x_2)^2$. Fixing any variable we have that the degree of the polynomial (now in just one variable) is odd, and the coefficient of the highest degree monomial is $1$. However $p(t[1$ $1]^T)=0$ for all $t\in\mathbb{R}$. $\endgroup$
    – jkn
    Oct 9 '13 at 13:37
  • $\begingroup$ Yes, of course. $\endgroup$
    – Arthur
    Oct 9 '13 at 13:39
  • $\begingroup$ I think $p$ is radially unbounded if and only if it is unbounded in every direction : for all $y \in S_{n-1}$, the polynomial $p(Xy) \in \Bbb R[X]$ is of positive even degree and positive leading coefficient. So you have to look at the homogeneous piece of highest degree, see if the degree is even, check if it ever gets negative, and if it ever gets zero, look at the next homogeneous piece of highest degree on that subvariety, on so on. $\endgroup$
    – mercio
    Oct 24 '13 at 13:08
  • 2
    $\begingroup$ @mercio: Unless I misunderstand what you mean by direction, I think you are wrong. For example, $p(x, y) = (x^3 - y)^2$ yields a non-constant non-negative polynomial when restricted to any 1-dimensional subspace, but its zero set is clearly unbounded. $\endgroup$ Oct 25 '13 at 21:36
1
+100
$\begingroup$

Changing to generalized spherical coordinates, $p$ becomes a polynomial $$q(r,\cos\theta_2,\sin\theta_2,\ldots,\cos\theta_n,\sin\theta_n)$$ which we can view as a polynomial in $r$ with coefficients that are polynomials in $\cos\theta_2,\sin\theta_2,\ldots,\cos\theta_n,\sin\theta_n$. We want to show that this goes to $\infty$ as $r\to\infty$, independent of the values of $\theta_2,\ldots,\theta_n$. It is sufficient to show that the leading coefficient $c(\cos\theta_2,\sin\theta_2,\ldots,\cos\theta_n,\sin\theta_n)$ is bounded below by some $\epsilon>0$. Since the domain of the $\theta_i$ is compact, it suffices to show that $c$ is strictly positive. The range of $(\cos\theta_i,\sin\theta_i)$ is precisely the set of pairs $(x_i,y_i)$ such that $x_i^2+y_i^2=1$. Thus $c$ is strictly positive if the system $$\begin{align} c(x_2,y_2,\ldots,x_n,y_n) &\leq 0\\ x_2^2+y_2^2 &= 1\\ \vdots\\ x_n^2+y_n^2 &= 1\\ \end{align}$$ has no real solutions. Determining whether such a system has real solutions is a classic problem in Real Semialgebraic Decomposition, and can be accomplished using Cylindrical Algebraic Decomposition.

As Giraffe points out, this condition is not quite necessary: if $c$ is nonnegative but not strictly positive, it may so happen that whenever $c=0$ the next coefficient $d$ is strictly positive, in which case $f$ is still radially unbounded. Thus $f$ is radially unbounded if both $$\begin{align} c(x_2,y_2,\ldots,x_n,y_n) &< 0\\ x_2^2+y_2^2 &= 1\\ \vdots\\ x_n^2+y_n^2 &= 1\\ \end{align}$$ and $$\begin{align} d(x_2,y_2,\ldots,x_n,y_n) &\leq 0\\ c(x_2,y_2,\ldots,x_n,y_n) &= 0\\ x_2^2+y_2^2 &= 1\\ \vdots\\ x_n^2+y_n^2 &= 1\\ \end{align}$$ have no solutions. In the same manner, it is possible that both $c$ and $d$ are nonnegative and wherever both are zero the next coefficient is strictly positive. We can express this using three systems of equalities and inequalities. Proceeding in the same manner until we get to the last coefficient gives us a necessary and sufficient condition.

Edit: It turns out the modification (looking at later coefficients) doesn't quite work, as we could have $\theta_i$ approach zeros of $c$ as $r\to \infty$ fast enough to cancel out the larger power of $r$. At least the first part provides a sufficient condition.

$\endgroup$
8
  • $\begingroup$ @Giraffe Thanks for pointing that out, can't believe I missed it. Hopefully my revised answer is less misguided. $\endgroup$ Oct 27 '13 at 6:03
  • $\begingroup$ @Giraffe Good point. I can add some steps to take care of that. $\endgroup$ Oct 27 '13 at 6:46
  • $\begingroup$ It looks fine to me now. :) I think the original question is very hard to me and a full answer is far beyond my knowledge, because I know nothing about real algebraic geometry. I am interested in to what extent I can follow the answer. For example, when $n=2$ and $\deg p=4$($\deg p\le 3$ is not interesting for any $n$), is there a simple answer? $\endgroup$ Oct 27 '13 at 7:02
  • $\begingroup$ @Giraffe When $n=2$ we can simplify this considerably since $c(\cos\theta,\sin\theta)$ is a function of $1$ variable, so we can use univariate root-finding methods to minimize $c$, and its root set will be finite, so any checks of the remaining coefficients are simple. $\endgroup$ Oct 27 '13 at 7:20
  • 1
    $\begingroup$ How would this work on the example $(x^2-y)^2$ inspired by @NielsDiepeveen? $\endgroup$
    – WimC
    Oct 27 '13 at 8:04
1
$\begingroup$

To make mercio’s comment more formal and explicit :

One can decompose $P=\sum_{i=0}^{d} P_i$ where each $P_i$ is a sum of monomials all of whose total degree are equal to $i$ and $P_d \neq 0$.

Obviously, a necessary condition for $P$ to satisfy your condition is that it involves all variables $x_1,x_2, \ldots ,x_n$.

That leads up to the following definition : the essential part of a polynomial $P$ (involving all the variables) is the sum $\sum_{i=w}^{d} P_i$, where $w$ is the largest index which such that $\sum_{i=w}^{d} P_i$ involves all the variables.

Fact 1. If $Q$ is the essential part of a polynomial $P$, then $P-Q=o(Q)$ when $||x|| \to \infty$. [EDIT : this is incorrect as explained in Giraffe’s comments below]

Corollary. $P$ satisfies your property iff $Q$ does.

For example, if $n=6$ and $P=x_1^{2013}-5x_2x_3^{2012}+7x_4^{20}x_5^{30}x_6^{100}+48x_1+2x_6$, we have $P_{2013}=x_1^{2013}-5x_2x_3^{2012}$, $P_{150}=7x_4^{20}x_5^{30}x_6^{100}$, $P_{1}=48x_1+2x_6$ and $Q=P_{2013}+P_{100}=x_1^{2013}-5x_2x_3^{2012}+7x_4^{20}x_5^{30}x_6^{100}$.

Remark 1. If $P$ is a quadratic form, then $P$ satisfies your condition iff it is positive definite.

Remark 2. If $P$ is homogeneous, then $P$ satisfies your property iff ${\min}_{S^{n-1}}(P) > 0$, where $S^{n-1}=\lbrace x\in {\mathbb R}^n | ||x||=1\rbrace$ (that’s because $P(ru)=r^nP(u)$, for $u\in S^{n-1}$).

$\endgroup$
8
  • $\begingroup$ I guess you want $w$ to be the largest index such that $\sum_{i=w}^d P_i$ involves all the variables? $\endgroup$
    – Christoph
    Oct 25 '13 at 8:28
  • $\begingroup$ @ChristophPegel corrected, thanks. $\endgroup$ Oct 25 '13 at 8:28
  • $\begingroup$ I feel confused about your definition of ”essential part“ and "Fact 1". For example, if $P(x,y)=x+y+1$, is $P-Q=1$? If so, what does $o(Q)$ mean and how could $1=o(Q)$? $\endgroup$ Oct 25 '13 at 14:46
  • $\begingroup$ @Giraffe $o$ is Landau’s o-notation. And yes, in your example $Q=x+y$, so $\frac{1}{Q}=\frac{1}{x+y} \leq \frac{1}{\sqrt{x^2+y^2}}$ which tends to zero when $x^2+y^2 \to \infty$. $\endgroup$ Oct 26 '13 at 7:48
  • 1
    $\begingroup$ @EwanDelanoy: You are welcome. The "corollary" seems incorrect, if I understand the meaning of "essential part" correctly. For example, if $n=2$ and $P=P_4+P_2$, where $P_4=(x_1-x_2)^4$and $P_2=x_1^2+x_2^2$, then is $Q=P_4$? If so, $P$ satisfies the property but $Q$ doesn't. $\endgroup$ Oct 26 '13 at 11:03

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.