Counting roots: multidimensional Sturm's theorem

Question

Sturm's theorem gives a way to compute the number of roots of a one-variable polynomial in an interval [a,b]. Is there a generalization to boxes in higher dimensions? Namely, let $P_1,\dotsc,P_n\in \mathbb{R}[X_1,\dotsc,X_n]$ be a collection of $n$ polynomials such that there are only finitely many roots of $P_1=P_2=\dotsb=P_n=0$. I want to be able to compute the number of roots in $[a,b]^n$. I do not care if the roots are counted with or without multiplicity.

I would also be interested in upper bounds on the number of roots that is similar to Descartes' rule of signs. The only work in this connection that I managed to find is by Itenberg and Roy, who postulated a conjectural extension of Descartes' rule of signs, which however later was shown to be false.

Answer 1

To expand on David's answer, the bound given by Khovanskii's theorem is of the form $2^{\binom{N}{2}} (n+1)^N$ per quadrant (more or less). Incremental improvements on this bounds have been obtained http://arxiv.org/abs/1010.2962 being the latest, but nothing revolutionary and we're nowhere near realistic bounds.

As far as I know, there have been no new attempts on a multivariable Descartes (something that would take signs into consideration) since Itenberg and Roy's paper, and it remains a major open problem in the area.

Added Later: As far as an algorithm is concerned, I don't think you can count without solving, in which case the standard one to use would be the Cylindrical Algebraic Decomposition pioneered by Collins. It is more or less based on Sturm and induction, but it is a lot more involved than the 1-dimensional case. For reference, I recommend the book by Basu Pollack and Roy Algorithms in Real Algebraic Geometry (free download).

(More on counting without solving: Marie-Françoise Roy mentions the problem of determining if a semi-algebraic set is non-empty without producing one point per connected components as one of the major open problems in algorithmic real algebraic geometry).

Answer 2

I don't know any results like Sturm's theorem, which give a precise simple formula for the number of roots. I have always thought of the analogue of Descartes' rule of signs as Khovanskii's theorem. This states

Fix integers $N$ and $n$. Then there is a constant $C$ such that, for any real polynomials $P_1$, ..., $P_n$ in $n$ variables, each of which contain only $N$ nonzero monomials, if there are finitely many real solutions to $P_1 = P_2 = \cdots = P_n =0$, then there are at most $C$ real solutions.

Note that $C$ does not depend on the degree of the terms in the $P_i$. This is like Descartes Rule of Signs -- a polynomial with $N$ nonzero terms has at most $2N$ real roots -- and very unlike the fundamental theorem of algebra/Bezout's theorem.

If you want to look into modern research on this, the key term is "Fewnomial Theory".

Answer 3

The Hermite method for real root counting generalizes to the multivariate case if your system of polynomial inequalities has only a finite number of COMPLEX roots. See for example the article "Radical computations of zero-dimensional ideals and real root counting" by Becker and Wörmann and the references therein.