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).