Counting Real Roots in Polynomial-Time via Diophantine Approximation

J Maurice Rojas

doi:10.1007/s10208-022-09599-z

Counting Real Roots in Polynomial-Time via Diophantine Approximation

Found Comut Math. 2022 Nov 28:1-43. doi: 10.1007/s10208-022-09599-z. Online ahead of print.

Author

J Maurice Rojas¹

Affiliation

¹ Department of Mathematics, Texas A & M University, TAMU 3368, College Station, TX 77843-3368 USA.

Abstract

Suppose $A = {a_{1}, \dots, a_{n + 2}} \subset Z^{n}$ has cardinality $n + 2$ , with all the coordinates of the $a_{j}$ having absolute value at most d, and the $a_{j}$ do not all lie in the same affine hyperplane. Suppose $F = (f_{1}, \dots, f_{n})$ is an $n \times n$ polynomial system with generic integer coefficients at most H in absolute value, and A the union of the sets of exponent vectors of the $f_{i}$ . We give the first algorithm that, for any fixed n, counts exactly the number of real roots of F in time polynomial in $log (d H)$ . We also discuss a number-theoretic hypothesis that would imply a further speed-up to time polynomial in n as well.

Keywords: Baker–Wustholtz theorem; Circuit; Descartes’ rule; Gale dual; Mahler’s theorem; Positive root; Real root; Rolle’s theorem; Sparse polynomial system.

© SFoCM 2022, Springer Nature or its licensor (e.g. a society or other partner) holds exclusive rights to this article under a publishing agreement with the author(s) or other rightsholder(s); author self-archiving of the accepted manuscript version of this article is solely governed by the terms of such publishing agreement and applicable law.