Return to Answer

3 Corrected a switch between N and n in the Khovanskii bound

To expand on David's answer, the bound given by Khovanskii's theorem is of the form $2^{\binom{N}{2}} (N+1)^n$ 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).

2 Added the paragraphs about algorithm.

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

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.
{"extraction_info": {"found_math": true, "script_math_tex": 0, "script_math_asciimath": 0, "math_annotations": 0, "math_alttext": 0, "mathml": 0, "mathjax_tag": 0, "mathjax_inline_tex": 3, "mathjax_display_tex": 0, "mathjax_asciimath": 0, "img_math": 0, "codecogs_latex": 0, "wp_latex": 0, "mimetex.cgi": 0, "/images/math/codecogs": 0, "mathtex.cgi": 0}, "config": {"markdown_headings": false, "markdown_code": true, "boilerplate_config": {"ratio_threshold": 0.18, "absolute_threshold": 10, "end_threshold": 15, "enable": true}, "remove_buttons": true, "remove_image_figures": true, "remove_link_clusters": true, "table_config": {"min_rows": 2, "min_cols": 3, "format": "github"}, "remove_chinese": true, "remove_edit_buttons": true, "extract_latex": true}, "english_confidence": 0.9513077139854431, "perplexity_flag": "middle"}