17
$\begingroup$

Given a polynomial $p(x_1,x_2,\ldots,x_d)$ in $d$ variables, with maximum degree $k$, what is the maximum number of components of $\mathbb{R}^d$ minus $p(\ldots)=0$? In other words, into how many pieces can an implicit polynomial equation partition $\mathbb{R}^d$?

For example, the following three equations partition $\mathbb{R}^2$ or $\mathbb{R}^3$ into $3$, $4$, and $2$ pieces respectively (I think!):

$$x^3 y^2+x^3 -3 x^2 y -y^2 +4 x y+x=0$$

$$x^6 y^8+x^3+4 x y-y=0$$

$$x^4+3 \left(x^2+y^4+z\right)- \left(x^2+y^2+z^2\right)^2+y^3+z^5 + 2 xy=3$$


   Implicit Functions
Of course the answer is $k+1$ in $\mathbb{R}^1$. I suspect this is well known for $\mathbb{R}^d$; if so, I would appreciate a pointer. Thanks!

Update. Greg Martin's idea (from the comments), using the 5th Chebyshev polynomial of the first kind:
         Cheb5
As Aaron Meyerowitz points out, here the degree $k=10$, and the plane is partitioned into $28$ pieces. But using Pietro Majer's line-arrangement idea leads to (now corrected:) $56$ pieces for a degree $10$ polynomial.

Improve this question
$\endgroup$
4
  • 3
    $\begingroup$ An observation, which can probably be generalized: let $T_n$ be the $n$th Chebyshev polynomial of the first kind. For $n$ odd, consider the polynomial $(y-T_n(x))(x-T_n(y))$. The graph of the zero locus of this degree-$2n$ polynomial splits the plane into $n^2+3$ pieces (4 unbounded pieces and $n^2-1$ bounded pieces). The bounded pieces come up because the graph of $y-T_n(x)=0$ oscillates up and down $n$ times inside the unit box $[-1,1]^2$, while $x-T_n(x)$ oscillates $n$ times side to side. See: en.wikipedia.org/wiki/Chebyshev_polynomials#Roots_and_extrema $\endgroup$
    – Greg Martin
    Commented Sep 6, 2012 at 23:15
  • 2
    $\begingroup$ If $p$ is a product of $k$ affine functions in $\mathbb{R}^d$, its zero-set is the union of $k$ affine hyperplanes. If these are in generic position, the number of components of the co-set is the well-known $\sum_{j=0}^d\binom kj$. I'd conjecture this is not worse than any polynomial of degree $k$. Note that $2n$ lines disconnect the plane into $2n^2+n+1\ge n^2+3$ components. $\endgroup$
    – Pietro Majer
    Commented Sep 7, 2012 at 0:42
  • 1
    $\begingroup$ I'm pretty sure it is $56$ and not $58$ regions. I may have heard once that this is optimal. You lose something in not having curved borders which can multiply intersect but gain more in having lots of linear borders heading off in many directions. Look at the quintic factor $y-T_5(x).$ Wouldn't you rather straighten the rounded turns and replace them with $5$ lines going off to infinity? The $\pm \epsilon$ adjustment gives a prettier picture but then the number of regions is $n^2+O(n).$ $\endgroup$
    – Aaron Meyerowitz
    Commented Sep 8, 2012 at 3:17
  • $\begingroup$ See the edit to my response for a sharper (in fact, I am pretty sure it is sharp) bound. $\endgroup$
    – Igor Rivin
    Commented Sep 8, 2012 at 15:40

4 Answers 4

Reset to default
7
$\begingroup$

In some contexts (for example, in the study of spherical harmonics), the connected components of the complement of the zero set of a polynomial are called nodal domains.

The maximum number of nodal domains in the real projective plane of a polynomial of degree $d$ (i.e. a homogeneous polynomial in $\mathbb{R}^3$) is bounded above by $d(d-1)+2.$ A nice exposition of this result can be found Leydold's paper On the number of nodal domains of spherical harmonics.

A related result is Harnack's curve theorem. It says that the number of connected components of the zero set of a polynomial in the real projective plane is bounded by $(d-1)(d-2)/2+1$.

Improve this answer
$\endgroup$
4
  • $\begingroup$ @Matthew: Thanks! I didn't know this theorem. But I am confused because the Chebyshev example I posted has $d=6$, and so should have at most $11$ regions, but I count $24$ bounded regions... $\endgroup$
    – Joseph O'Rourke
    Commented Sep 7, 2012 at 1:28
  • 1
    $\begingroup$ @Joseph: Oops! I confused components of the curve and components of the complement of the curve. I've updated the answer to fix this. $\endgroup$
    – Matthew Badger
    Commented Sep 7, 2012 at 3:32
  • $\begingroup$ @Matthew: isn't your latter bound shifted by one? For a 2-variables real polynomial of degree $d$, I'd say at least $d(d-1)/2+1$ components in the real projective plane (and $d(d+1)/2+1$ in the affine plane), which is reached if the polynomial is a product of linear terms (see my comment above). $\endgroup$
    – Pietro Majer
    Commented Sep 7, 2012 at 8:01
  • $\begingroup$ (And, as Aaron pointed out, $d=10$, not $6$ as I claimed above.) $\endgroup$
    – Joseph O'Rourke
    Commented Sep 7, 2012 at 11:52
7
$\begingroup$

You are asking for the number of components of the semialgebraic set defined by $P\geq 0.$ It is a classical result that the number of connected components is of order $O(k^d).$ In the below paper, the author gives all the relevant references, and extends the results to estimating higher Betti numbers.

Basu, Saugata(1-GAIT-CC) Different bounds on the different Betti numbers of semi-algebraic sets. (English summary) ACM Symposium on Computational Geometry (Medford, MA, 2001).

EDIT In fact, the result is much stronger than a Big-O result: Milnor (in his paper MR0161339 (28 #4547) Reviewed Milnor, J. On the Betti numbers of real varieties) Shows that in this situation the upper bound is $\frac12(2+k)(1+k)^{d-1}.$

Improve this answer
$\endgroup$
6
  • 2
    $\begingroup$ I think Joseph is asking for the semi algebraic set that is the union of $P>0$ and $P<0$. Nonetheless, I was also wondering if work of Basu would be the place to look. $\endgroup$
    – Patricia Hersh
    Commented Sep 7, 2012 at 3:08
  • 1
    $\begingroup$ @Patricia: I am sure he is, but once you have $O(),$ what's a factor of two among friends... $\endgroup$
    – Igor Rivin
    Commented Sep 7, 2012 at 13:28
  • $\begingroup$ @Igor: good point. My real concern was that throwing in $P=0$ as your statement does might reduce the number of connected components. I also wondered if the fact that Joseph is actually considering a Zariski open set might mean that there are also relevant results in algebraic geometry. $\endgroup$
    – Patricia Hersh
    Commented Sep 7, 2012 at 13:57
  • $\begingroup$ @Patricia: No, I don't think this reduces the number of connected components, which should be equal to the number of components of $P\geq 0$ plus the number for $P\leq 0$ but I am not 100% certain -- it is conceivable that one has two components meeting at a point, or some lower dimensional stratum -- presumably one can bound the number of such occurrences but a lower order term than the main term in the bound... $\endgroup$
    – Igor Rivin
    Commented Sep 7, 2012 at 14:36
  • $\begingroup$ @Igor: Very useful to know the asymptotic growth rate. (I should have thought of Basu's work myself.) Thanks! $\endgroup$
    – Joseph O'Rourke
    Commented Sep 7, 2012 at 15:42
7
$\begingroup$

A slightly more general result -- namely on the number of connected components of the non-zeros of a polynomial, restricted to the zeros of another polynomial -- where the degrees of the two polynomials could be different, can be deduced from the main theorem in the paper titled

"Refined Bounds on the Number of Connected Components of Sign Conditions on a Variety" by Barone and Basu, DISCRETE & COMPUTATIONAL GEOMETRY Volume 47, Number 3 (2012), 577-597, DOI: 10.1007/s00454-011-9391-3

Note that this is a bound only on the number of connected components and not on he higher Betti numbers. I don't know if the added generality is helpful to the original poster.

Improve this answer
$\endgroup$
5
  • 1
    $\begingroup$ Welcome to MO! Perhaps you can address @Patricia's question: The Oleinik/Milnor/Thom bound is for the number of connected components of $P\geq 0.$ Does anything particularly unpleasant happen if the inequalities are strict? $\endgroup$
    – Igor Rivin
    Commented Sep 9, 2012 at 2:00
  • $\begingroup$ Or is the "semi-algebraically connected component" in fact the open set? $\endgroup$
    – Igor Rivin
    Commented Sep 9, 2012 at 2:07
  • $\begingroup$ The number of connected components of $P> 0$ is the same as the number for $P\geq \epsilon$ for $\epsilon$ sufficiently small. This doesn't work as well for two-sided bounds but if it's one-sided I don't think that's a big problem $\endgroup$
    – Will Sawin
    Commented Sep 9, 2012 at 4:52
  • $\begingroup$ It could happen of course that $P>0$ is empty, even though $P\geq 0$ is not. However, the reduction mentioned above works to give the same bound. If one is interested in bounding the number of connected components of the basic semi-algebraic defined by $P_1 > 0,\ldots,P_s >0$, then a slightly better bound (better dependence on $s$) is available in the case where the inequalities are strict. Need to thank Patricia Hersh for pointing me to this discussion since I don't follow this forum regularly. $\endgroup$
    – Saugata Basu
    Commented Sep 9, 2012 at 12:04
  • $\begingroup$ In fact, looking at the Milnor paper, that seems to be exactly what he does (jiggle the $\epsilon$ a bit...) $\endgroup$
    – Igor Rivin
    Commented Sep 10, 2012 at 1:32
1
$\begingroup$

Your example of $f(x,y)=\left(y-T_5(x)\right)\left(x-T_5(y)\right)$ is $$ 256\,{x}^{5}{y}^{5}-320\,{x}^{5}{y}^{3}-320\,{x}^{3}{y}^{5}-16\,{x}^{6 }+80\,{x}^{5}y+400\,{x}^{3}{y}^{3}+80\, x{y}^{5}\\-16\,{y}^{6}+20\,{x}^{4 }-100\,{x}^{3}y-100\,x{y}^{3}+20\,{y}^{4}-5\,{x}^{2}+26\,xy-5\,{y}^{2} $$

If I count correctly, it has $28$ regions. Would that qualify as maximum degree $10?$ If so, then as Pietro points out, $g(x,y)=\prod_{i=1}^{10}\left(a_ix+b_iy+c_i\right)$ will have $56$ regions (if $a_i,b_i,c_i$ are such that the $10$ lines are in general position: no two parallel and no three meeting at a common point). Similar things (as he says) can be done with hyperplane arrangements in higher dimension. You can color the regions $g \gt 0$ white and $g \lt 0$ black so that each region is bounded by regions of the opposite color.

If you want the curve itself to have many disjoint connected components then $g(x,y)+\epsilon$ and $g(x,y)-\epsilon$ are nice to look at. Then all the regions of one color fuse together but each of the others becomes a nicely bordered region. I think that (in the two variable case with a projective viewpoint, at any rate) these achieve that bound given by Harnack's theorem.

Improve this answer
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .