Trinomials and Deterministic Complexity Limits for Real Solving

Abstract

We detail an algorithm that -- for all but a $\frac{1}{\hat{I}\text{c◯}(\log (dH))}$ fraction of $f\in \mathbb{Z}[x]$ with exactly $3$ monomial terms, degree $d$, and all coefficients in $\{-H,\dots ,H\}$ -- produces an approximate root (in the sense of Smale) for each real root of $f$ in deterministic time ${\log }^{4+o(1)}(dH)$ in the classical Turing model. (Each approximate root is a rational with logarithmic height $O(\log (dH))$.) The best previous deterministic bit complexity bounds were exponential in $\log d$. We then relate this to Koiran's Trinomial Sign Problem (2017): Decide the sign of a degree $d$ trinomial $f\in \mathbb{Z}[x]$ with coefficients in $\{-H,\dots ,H\}$, at a point $r\in \mathbb{Q}$ of logarithmic height $\log H$, in (deterministic) time ${\log }^{O(1)}(dH)$. We show that Koiran's Trinomial Sign Problem admits a positive solution, at least for a fraction $1-\frac{1}{\hat{I}\text{c◯}(\log (dH))}$ of the inputs $(f,r)$.

17 pages