A complexity chasm for solving univariate sparse polynomial equations over $p$-adic fields

We reveal a complexity chasm, separating the trinomial and tetranomial cases, for solving univariate sparse polynomial equations over certain local fields. First, for any fixed field $Kin{mathbb{Q}_2,mathbb{Q}_3,mathbb{Q}_5,ldots}$, we prove that any polynomial $finmathbb{Z}[x]$ with exactly $3$ monomial terms, degree $d$, and all coefficients having absolute value at most $H$, can be solved over $K$ in deterministic time $O(log^{O(1)}(dH))$ in the classical Turing model. (The best previous algorithms were of complexity exponential in $log d$, even for just counting roots in $mathbb{Q}_p$.) In particular, our algorithm generates approximations in $mathbb{Q}$ with bit-length $O(log^{O(1)}(dH))$ to all the roots of $f$ in $K$, and these approximations converge quadratically under Newton iteration. On the other hand, we give a unified family of tetranomials requiring $Omega(dlog H)$ digits to distinguish the base-$p$ expansions of their roots in $K$.

A complexity chasm for solving univariate sparse polynomial equations over $p$-adic fields Institutional Repository Document