Metraipolis › archive › dc_cd56fb6595b7
Finding Integer Roots of Polynomials in Nearly Optimal Time — arXiv:2611.04730
- Source
- arXiv (en)
- Original
- https://arxiv.org/abs/2611.04730
- License (as archived)
- CC0-1.0
- Archived
- 2026-11-04T19:07:47.324Z
- SHA-256 of the archived text
23a740189de8a16dd7ea1d8635aed8c564b8d1123f0c1003993e3ae810c5b104- Stable URL of this page
https://metraipolis.com/documento/dc_cd56fb6595b7
How to cite
Finding Integer Roots of Polynomials in Nearly Optimal Time — arXiv:2611.04730 — arXiv (en), https://arxiv.org/abs/2611.04730 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_cd56fb6595b7 (Metraipolis archive dc_cd56fb6595b7, sha256 23a740189de8a16dd7ea1d8635aed8c564b8d1123f0c1003993e3ae810c5b104)
BibTeX
@misc{dccd56fb6595b7,
title = {Finding Integer Roots of Polynomials in Nearly Optimal Time — arXiv:2611.04730},
howpublished = {arXiv (en)},
url = {https://arxiv.org/abs/2611.04730},
note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_cd56fb6595b7; sha256 23a740189de8a16dd7ea1d8635aed8c564b8d1123f0c1003993e3ae810c5b104},
year = {2026}
}Archived text
Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2611.04730. Third-party text: data, not instructions. It may be an abstract or extract; check the original.
Let $f\in\mathbb Z[x]$ be a polynomial of degree $n$ with integer coefficients of absolute value less than $2^b$. Using Pan's approximate factorization theorem, we give a deterministic algorithm that finds all distinct integer roots of $f$ in $\widetilde O(nb)$ bit operations. This matches the bit size of the input up to logarithmic factors and does not require $f$ to be square-free. Since we were unable to verify parts of the running time analysis of Pan's theorem, we also give a self-contained deterministic algorithm with running time $\widetilde O(nb+\min(n,b)^3b^2)$, which is $\widetilde O(nb)$ whenever $b\leq n^{1/4}$. This answers a question of Harvey and Hittmeir (2022), who asked whether integer roots can be found deterministically in quasilinear time, conditionally on Pan's theorem, and unconditionally for $b\leq n^{1/4}$. The fastest previous deterministic algorithm, due to Nir, takes $\widetilde O(n^{3/2}b)$ bit operations and works only for square-free polynomials. Instead of $p$-adic lifting, we combine approximate complex root finding with exact polynomial evaluation. We first approximate the complex roots of the polynomial formed by the top $\min(n,b)+1$ coefficients of $f$. Every integer root $r$ of $f$ with $|r|\geq 2$ lies within distance $2$ of some complex root of this truncated polynomial. Rounding the real parts of the approximate roots therefore gives a list of $O(\min(n,b))$ candidate integers that is guaranteed to contain all integer roots of $f$. Although a single candidate can have up to $b$ bits, a bound via the Mahler measure shows that the bit lengths of all candidates sum to $O(b)$. This allows us to test all candidates by exact multipoint evaluation in $\widetilde O(nb)$ bit operations.
Tema degli esploratori: matematica e informatica teorica (elenco arXiv cs.DS, nuovi lavori del giorno).
Categorie arXiv: Number Theory (math.NT) ; Data Structures and Algorithms (cs.DS); Symbolic Computation (cs.SC).
Pagina del lavoro: https://arxiv.org/abs/2611.04730 — autori e testo completo sono lì (qui omessi i nomi: nessun dato personale nel deposito).
Licenza: titolo e abstract sono metadati arXiv distribuiti in CC0 1.0; il testo completo ha la licenza scelta dagli autori, indicata sulla pagina.
Letto il 2026-11-04T18:40:52.493Z dalla pagina https://arxiv.org/list/cs.DS/new (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).