# Upper bound on the number of convex connected components of the complement of the zero set of a polynomial

The classic Milnor-Thom upper bound on the sum of the Betti numbers of real algebraic sets (for a nice exposition and references, see e.g. N.R. Wallach, On a Theorem of Milnor and Thom, in S. Gindikin (ed.), Topics in Geometry: In Memory of Joseph D'Atri, Progress in Nonlinear Differential Equations and their Applications 20 (Birkhäuser, 1996), pp. 331-348) allows one to give an upper bound on the number of connected components of the complement $$U_P=\{\xi\in\mathbb{R}^n\ |\ P(\xi)\neq 0\}$$ of the zero set of a real polynomial function $P:\mathbb{R}^n\rightarrow\mathbb{R}$, since $U_P$ is homeomorphic to the real algebraic subset $\tilde{U}_P=\{(\xi,\lambda)\in\mathbb{R}^{n+1}\ |\ \lambda P(\xi)=1\}$ of $\mathbb{R}^{n+1}$ through the map $$U_P\ni\xi\mapsto\left(\xi,\frac{1}{P(\xi)}\right)\in\tilde{U}_P\ ,$$ whose inverse is simply the (restriction of the) projection $$\mathbb{R}^{n+1}\ni(\xi_1,\ldots,\xi_n,\xi_{n+1})\mapsto(\xi_1,\ldots,\xi_n)\in\mathbb{R}^n$$ (to $\tilde{U}_P$).

The aforementioned bound tells us that if the degree of $P$ is $r$, then the sum of the Betti numbers of $U_P$ (and, therefore, its number of connected components) is bounded above by $(r+1)(2r+1)^n$.

Question: is there an upper bound on the number of convex connected components of $U_P$ which is sharper than the Milnor-Thom bound but also only depends on $n$ and $r$?

My intuition is that the Milnor-Thom bound is too crude to this end, even in the exceptional case when all connected components of $U_P$ are convex - take, for instance, $P(\xi)=\prod^n_{j=1}\xi_j$, in which case $r=n$ but the connected components of $U_P$ are precisely the $2^n$ orthants $$\mathbb{R}^n_I\doteq\{\xi\in\mathbb{R}^n\ |\ \xi_j>0\text{ if }j\in I\ ,\,\xi_j<0\text{ if }j\not\in I\}\ ,\quad I\subset\{1,\ldots,n\}$$ of $\mathbb{R}^n$, which are clearly convex. More generally, if $P(\xi)$ is the elementary symmetric polynomial of order $1\leq r\leq n$ $$P(\xi)=\sum_{1\leq j_1<\cdots<j_r\leq n}\xi_{j_1}\cdots\xi_{j_r}\ ,$$ then $U_P$ has $2^r$ connected components, all of them convex.

My motivation for the above question is related to Lars Gårding's theory of hyperbolic polynomials (see e.g. L. Gårding, An Inequality for Hyperbolic Polynomials, J. Math. Mech. 8 (1959) 957-965). Recall that an homogeneous polynomial $P:\mathbb{R}^n\rightarrow\mathbb{R}$ is said to be hyperbolic with respect to $0\neq\tau\in\mathbb{R}^n$ if $P(\tau)\neq 0$ and the roots of the one-variable polynomial $P_{\xi,\tau}(\lambda)\doteq P(\xi-\lambda\tau)$ are all real. The hyperbolicity cone $C(P,\tau)$ to which $\tau$ belongs is the connected component of $U_P$ to which $\tau$ belongs. Gårding has shown that $$C(P,\tau)=\{\xi\in\mathbb{R}^n\ |\ \text{all roots of }P_{\xi,\tau}\text{ are positive}\}$$ and, as a consequence, that $C(P,\tau)$ is an open convex cone. Roughly speaking, dual cones of hyperbolicity cones provide upper bounds to the propagation speed of the support of solutions of hyperbolic partial differential equations with principal symbol $i^rP$.

Due to the homogeneity of $P$, hyperbolicity cones always come in opposite pairs - more precisely, if $P$ is hyperbolic with respect to $\tau$, then it also is with respect to $-\tau$, and $C(P,-\tau)=-C(P,\tau)$. Since $P$ in the above examples is hyperbolic with respect to any $\tau$ in $U_P$, we conclude that the number of hyperbolicity cones of an hyperbolic homogeneous polynomial $P:\mathbb{R}^n\rightarrow\mathbb{R}$ is an even number bounded above by the number of convex connected components of $U_P$, and such an upper bound is sharp. Therefore, a positive answer to the above question would provide an upper bound to the number of hyperbolicity cones of $P$ which is sharper than the Milnor-Thom bound.

Update: This is not exactly an answer to my question (hence it does not appear as a separate answer) but rather to the original question that motivated it - to wit, a sharp upper bound on the number of hyperbolicity cones of an (homogeneous) hyperbolic polynomial. Since the result is connected to Aaron Meyerowitz's bounty-awarded answer, I feel it is worthwhile to bring it up here.

Thorsten Jörgens and Thorsten Theobald have just posted (March 15th, 2017) the arXiv preprint Hyperbolicity Cones and Imaginary Projections, arXiv:1703.04988 [math.AG].

The main result of the paper (Theorem 1.1) states (I have retained only the part of the statement that interests us here and added a short explanation on the notation):

Let $P\in\mathbb{R}[\mathbf{z}]$ be an homogeneous $n$-variable polynomial of degree $r$ with real coefficients. Then the number of hyperbolicity cones of $P$ is at most $$\mathcal{H}(n,r)=\begin{cases} 2^r & \text{for }r\leq n\ ,\\ 2\sum^{n-1}_{k=0}\binom{r-1}{k} & \text{for }r>n\ .\end{cases}$$ The maximum is attained if and only if $P$ is a product of linear polynomials.

To get a feeling for the saturation of the above bound, we point out that $\mathcal{H}(n,r)$ is exactly the number of connected components of the complement of a central arrangement of hyperplanes in general position (here "central" means that all hyperplanes in the arrangement contain the origin) - the centrality comes from the fact that we are requiring here that $P$ is homogeneous. Notice that the saturation of the bound occurs precisely as conjectured in Boris Bukh's comment below (in the homogeneous case).

Of course, the conjecture of whether the above bound also applies to the total number of connected components of the complement of the zero set of an homogeneous polynomial $P$ remains. If so, the bound will also be sharp.

• As far as I know, the conjecture is that the largest number of components (convex or not) in a complement of $\{f=0\}$ occurs attained when $f$ is a union of hyperplanes in general position. As I am no expert, and cannot recall a reference, I refrain from making this into an answer. – Boris Bukh Feb 9 '16 at 20:02

It may be that the bound is only fairly good for $r \ll n.$ This is supported by the following which is an elaboration on the comment by Boris Bukh.

We can get a lower bound of $$f(r,n)=\sum_{j=0}^n \binom{r}{j}.$$ This is the number of regions (all of which happen to be convex) in the complement of the union of $r$ hyperplanes in general position. This would be $$\{\xi\in\mathbb{R}^n\ |\ P(\xi)\neq 0\}$$ for $P$ the product of $r$ linear polynomials.

Interesting, but not obviously relevant to this question is that for such a $P$, when $n \ge 2$, the surface $$\{\xi\in\mathbb{R}^n\ | \ |P(\xi)| = \epsilon\}$$ where $\epsilon \gt 0$ is small enough, has ${f(n,r)}$ components. This is the union of two polynomial surfaces $P(\xi) = \pm \epsilon$ each with about half that many components.

I had the vague impression of hearing that both bounds are optimal, at least in the case $n=2.$ But I have nothing to go on there. Are any examples known where the number of components exceeds $\mathbf{ f(n,r)}?$

As you note, $f(n,r)=2^r$ for $1 \le r \le n$ and this is quite a bit less than $(r+1)(2r+1)^n.$ Again, it may be that the bound is only fairly good for $r \ll n.$ Then (as always) the upper bound is $O(r^{n+1})$ and the lower bound is $O(r^n)$.

Certainly for $n=1,$ The zero set of a degree $r$ polynomial can divide $\mathbb{R}^1$ into $f(1,r)=r+1$ intervals but no more.

In the case that $2n \le r$ we have $$\binom{r}n \lt f(n,r) \lt \binom{r}n \frac{r-n+1}{r-2n+1}.$$ The upper bound is found in Sum of 'the first $k$' binomial coefficients for fixed $n$ (which we would prefer to call Sum of 'the first $n+1$' binomial coefficients for fixed $r$) and is quite good for $n \lt \frac{r}2+\sqrt{r}.$

• Thanks Aaron, this has been quite helpful, I couldn't find the conjecture stated by @BorisBukh explicitly in the literature so far. Is it "folk wisdom" among specialists, or are there references for it? By the way, where can I find a proof that the number $f(n,r)$ of connected components of the complement of the union of $r$ hyperplanes in $\mathbb{R}^n$ in general position is the sum of binomial coefficients you wrote? – Pedro Lauridsen Ribeiro May 25 '16 at 14:39
• I am not an expert. I heard a talk from one (long ago) and came away with that impression (for the not obviously relevant result) but my memory might be off or it might have been specifically for dimension $2.$ – Aaron Meyerowitz May 26 '16 at 5:58
• As far as the formula for $f(n,r)$, it is neat to think about and easy to find described as "well known". If one is convinced that $f(n,r)$ is a degree $n$ polynomial in $r$ then it follows from the fact that the formula is such a polynomial and equal to the right thing ($2^r$) For $0 \le r \le n.$ For a more direct proof consider $f(n,r+1)-f(n,r).$ One more hyper-plane $E$ is added, it intersects all the previous hyper-planes, the intersections divide $E$ into dimension $n-1$ regions each of which splits a previous component in half. I leave the rest to you. – Aaron Meyerowitz May 26 '16 at 6:00
• I got the gist, you then get $f(n-1,r)$ regions on the $(r+1)$-th hyperplane $E$, whose cuts add $f(n-1,r)=f(n,r+1)-f(n,r)$ pieces to the counting by standard combinatorial reasoning. According to P. Orlik and H. Terao's book (Hyperplane Arrangements, Springer-Verlag, 1992), this formula seems to be due to L. Schläfli (1901), but it also follows from a more general one (not assuming general position) due to T. Zaslavsky (Facing up to Arrangements: Face-Count Formulas for Partitions of Space by Hyperplanes, Mem. Amer. Math. Soc. 154 (1975), which seems to be his 1974 PhD Thesis at MIT). – Pedro Lauridsen Ribeiro May 30 '16 at 6:09