Root Repulsion and Faster Solving for Very Sparse Polynomials Over p-adic Fields
share
For any fixed field K∈{ℚ_2,ℚ_3,ℚ_5, …}, we prove that all polynomials f∈ℤ[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 ℚ with logarithmic height O(log^3(dH)) 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(plog^2_p(dH)log d) for distinct roots in ℂ_p, and even stronger repulsion when there are nonzero degenerate roots in ℂ_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 ℤ_p indistinguishable in their first Ω(dlog_p H) most significant base-p digits.
READ FULL TEXT