Root Repulsion and Faster Solving for Very Sparse Polynomials Over p-adic Fields
Root Repulsion and Faster Solving for Very Sparse Polynomials Over p-adic Fields
复制标题
DOI：
10.1016/j.jnt.2022.01.013
复制
发表时间：
2021-07
期刊：
影响因子：
--
通讯作者：
J. Rojas;Yuyu Zhu
中科院分区：
文献类型：
--
作者：
J. Rojas;Yuyu Zhu
对于任意固定域K∈{q2， q3, q5，…}，我们证明了所有的单变量多项式f都恰好具有3 (resp。2)单项项d和{±1，…，±H}中的所有系数都可以在确定性时间log 4+ o (1) d (H) log 3 d （resp）内在K上求解。经典图灵模型中的log 2+ o (1) d (H))：我们的底层算法正确地计算了K中f的根的个数，并且对于每个这样的根，在Q中生成一个对数高度为o (log 2 (d) H) log (d)的近似，在牛顿迭代i步后以o （(1/p) 2 i）的速率收敛。我们还证明了在某些情况下显著的加速，对于不同的C p根有一个极小的间距界p−O (p log p 2 (d H))，当C p中有非零的退化根时，甚至更强的根排斥：p进距p−O （log p (d H)）。另一方面，我们证明了在zp中存在一个具有不同非零根的显式四分体族，它们的第一个Ω （d log p (H)）以p为底的最有效位数是不可区分的。因此，当t≥4时，加速将需要规避或摊销这些最坏情况。有关本文的视频摘要，请访问https://youtu。/ npfdxLk04MY。
Text 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. Video For a video summary of this paper, please visit https://youtu. be/npfdxLk04MY.