Root repulsion and faster solving for very sparse polynomials over p-adic fields.

For any fixed field K ∈ { Q 2 , Q 3 , Q 5 , ... } , we prove that all univariate polynomials f with exactly 3 (resp. 2) monomial terms, degree d , and all coefficients in { ± 1 , ... , ± H } , can be solved over K within deterministic time log 4 + o (1) ⁡ (d H) log 3 ⁡ d (resp. log 2 + o (1) ⁡ (d H)) 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 Q with logarithmic height O (log 2 ⁡ (d H) log ⁡ d) that converges at a rate of O ((1 / 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 ⁡ (d H) log ⁡ d) for distinct roots in C p , and even stronger root repulsion when there are nonzero degenerate roots in C p : p -adic distance p − O (log p ⁡ (d H)). On the other hand, we prove that there is an explicit family of tetranomials with distinct nonzero roots in Z p indistinguishable in their first Ω (d log p ⁡ H) most significant base- p digits. So speed-ups for t -nomials with t ≥ 4 will require evasion or amortization of such worst-case instances. For a video summary of this paper, please visit https://youtu.be/npfdxLk04MY. [ABSTRACT FROM AUTHOR]