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}$,weprovethatallpolynomials$f!\in!$\mathbb{Z}$[x]$withexactly$3$(resp\mathrm{.}$2$)monomialterms,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\text{\hspace{0.17em}⁣}((1\mathrm{/}p{)}^{2^i})$ after $i$ steps of Newton iteration. We also prove significant speed-ups in certain settings, a minimal spacing bound of $p^{-O(p{\log }_p^2(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 $\mathrm{\Omega }(d{\log }_{p}H)$ most significant base-$p$ digits.