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

MaRDI QIDQ6335883zbMATH OpenFDO

Authors J. Maurice Rojas, Yuyu Zhu

Publication date 29 February 2020

Abstract: 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 $Kinmathbb{Q}_2,mathbb{Q}_3,mathbb{Q}_5,ldots$, we prove that any polynomial $finmathbbZ[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(lo{g}^{O(1)}(dH))$ in the classical Turing model. (The best previous algorithms were of complexity exponential in $logd$, even for just counting roots in $mathbb{Q}_p$.) In particular, our algorithm generates approximations in $mathbbQ$ with bit-length $O(lo{g}^{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(dlogH)$ digits to distinguish the base-$p$ expansions of their roots in $K$.

This page was built for publication: A complexity chasm for solving univariate sparse polynomial equations over $p$-adic fields

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6335883)