Root Repulsion and Faster Solving for Very Sparse Polynomials Over $p$-adic Fields

For any fixed field $K!in!{mathbb{Q}_2,mathbb{Q}_3,mathbb{Q}_5, ldots}$, we prove that all polynomials $f!in!mathbb{Z}[x]$ with exactly $3$ (resp. $2$) monomial terms, degree $d$, and all coefficients having absolute value at most $H$, can be solved over $K$ within deterministic time $log^{7+o(1)}(dH)$ (resp. $log^{2+o(1)}(dH)$) in the classical Turing model: Our underlying algorithm correctly counts the number of roots of $f$ in $K$, and for each such root generates an approximation in $mathbb{Q}$ with logarithmic height $O(log^3(dH))$ that converges at a rate of $O!left((1/p)^{2^i}
ight)$ after $i$ steps of Newton iteration. We also prove significant speed-ups in certain settings, a minimal spacing bound of $p^{-O(plog^2_p(dH)log d)}$ for distinct roots in $mathbb{C}_p$, and even stronger repulsion when there are nonzero degenerate roots in $mathbb{C}_p$: $p$-adic distance $p^{-O(log_p(dH))}$. On the other hand, we prove that there is an explicit family of tetranomials with distinct nonzero roots in $mathbb{Z}_p$ indistinguishable in their first $Omega(dlog_p H)$ most significant base-$p$ digits.

Root Repulsion and Faster Solving for Very Sparse Polynomials Over $p$-adic Fields Institutional Repository Document