Georgia Institute of Technology College of Sciences

Suppose $f$ is a univariate polynomial with integer coefficients of absolute value at most $H$, exactly $t$ monomial terms, and degree $d$. Suppose also that $p,q$ are integers of absolute value at most $H$. Then one can determine the sign of $f(p/q)$ in time $(d^3 \log H)^{2+\epsilon}$, by combining work of Liouville from about 170 years ago, work of Mahler from about 60 years ago, work of Neff, Reif, and Pan from about 30 years ago, and more recent refinements.

However, when $t$ is small, one can do much better: When $t=2$, one can determine the sign of $f(p/q)$ in time $\log^5(dH)$, via work of Baker from about 55 years ago. Koiran asked, around 2016, about the $t=3$ case, after proving new bounds on the minimal separation of complex roots of univariate trinomials.

We make progress on Koiran's question by giving a new, dramatically faster algorithm for solving univariate trinomials over the real numbers. The key innovation is a new family of non-hypergeometric series for the roots of $f$ when $f$ is close to having a degenerate root. This is joint work with Emma Boniface and Weixun Deng.