# Counting roots: multidimensional Sturm's theorem

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.

-
NP-hardness is one barrier for this kind of theorem, since it is NP-hard to check if a multi-variable polynomial has at least one root. It is still NP-hard if you restrict yourself to polynomials which have finitely many roots all of which must be in $[0,1]^n$. So any counting algorithm would take at least exponential time in $n$. – alex Oct 28 '10 at 22:13
Is it NP-hard in fixed dimension, though? – Boris Bukh Oct 29 '10 at 8:43

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).

-
Your answer is very helpful, as it indicates what the current state of knowledge is. If you can provide a reference where Roy states this as an open problem, I will consider my question fully answered. – Boris Bukh Oct 28 '10 at 16:00
I don't have the book, but I'm almost certain that it's in her article in the volume Mathematics unlimited, 2001 and Beyond amazon.com/Mathematics-Unlimited-Bj%C3%B6rn-Engquist/dp/… – Thierry Zell Oct 28 '10 at 16:30
Thanks, I will look into it. – Boris Bukh Oct 28 '10 at 19:30
I went to the library: on page 996 Roy asks a question of counting the number of roots of a fewnomial by an algorithm with complexity bounded by the number of mononomials. – Boris Bukh Oct 29 '10 at 13:11

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".

-
This is an interesting result. It seems to be too crude to be of practical use though. – Boris Bukh Oct 28 '10 at 15:31

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. this was shown by Becker and Wörmann and independently by Pedersen, see:

http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.40.9539

-