Skip to content
Preprint

Faster Deterministic Integer Root Finding for Integer Polynomials

Aug 2026 · 0 citations · 27 references
Mathematics Computer Science

Abstract

We give a deterministic algorithm for finding all integer roots of a square-free polynomial $f\in\mathbb Z[x]$ of degree $n$ with $\lVert f\rVert_\infty<2^b$. The running time is $$ \tilde{O}(n^{3/2}b), $$ improving the $\tilde{O}(n^2b)$ bound of Harvey and Hittmeir (Research in Number Theory, 2022). The algorithm follows the classical $p$-adic framework: find roots modulo a prime $p$, lift them modulo a high power of $p$, and verify the lifted candidates. The main new idea is to avoid searching for a prime for which $f\bmod p$ is square-free. Instead, we find a prime for which the total multiplicity of repeated roots modulo $p$ is small. This requires lifting repeated roots, which we handle using a weighted lifting tree. We also give a faster deterministic candidate-verification algorithm: given $n$ candidate integers smaller in absolute value than $2^b$, we decide which are roots of $f$ in $$ \tilde{O}(nb+\min(n^2,nb^2)) $$ bit operations. Together, these ingredients give the first deterministic subquadratic-in-$n$ improvement for integer root finding in the square-free case.

View source

Similar papers

Preprint Aug 2026

$13$ unknowns over quadratic integer rings and Lucas congruences

For every quadratic number field $K$, we prove a uniform $3$-unknown Diophantine definition of integer tuples in $\mathcal{O}_K$, allowing finitely many polynomial nonvanishing conditions. This yields an effective $+3$ transfer principle and a $13$-unknown representation of every recursively enumerable integer relation...

Ge Zhang · 0 citations
Preprint Sep 2026

On the largest prime factors less than $y$ of consecutive shifted primes

For an integer $n>1$, let $P^+(n)$ be the largest prime factor of $n$, and let $P_y^+(n)$ denote the largest prime factor of $n$ not exceeding $y$. One of Erd\H{o}s and Tur\'an's conjectures asserts that the asymptotic density of integers $n$ satisfying $P^+(n)<P^+(n+1)$ is $1/2$. Furthermore, Wang conjectures that for...

Zhi-Yuan Yang · 0 citations
Preprint Sep 2026

Estimating the number of real zeros of linear combinations of radicals of polynomials

We obtain upper bounds for the number of real zeros of functions of the form $$ f(x) = \sum_{k=1}^{n} c_k \bigl(P_k(x)\bigr)^{\alpha_k}, $$ where $c_k, \alpha_k \in \mathbb{R}$ and each $P_k$ is a real polynomial of degree at most $d$ that is non-negative on an interval $I\subset \mathbb{R}$. We improve previously know...

Gal Binyamini, Avner Kiro, A. Logunov et al. · 0 citations
Preprint Sep 2026

Long runs of integers with small prime factors and the divisor function of $n!$

Let $d$ be the divisor function, and let $K(n)$ be the least positive integer $K$ for which $d((n + K)!) \ge 2d(n!)$. Erd\H{o}s, Graham, Ivi\'c and Pomerance proved that, for infinitely many $n$, \begin{equation*} K(n)>(1/9)(\log n)(\log_{2} n)(\log_{4} n)/(\log_{3} n)^3. \end{equation*} We improve upon this by a facto...

Tristan Freiberg · 0 citations
Preprint Sep 2026

Sums of distinct divisors of factorials

For practical $N$ let $h(N)$ be the least $k$ such that every integer $1\le m\le N$ is a sum of at most $k$ distinct divisors of $N$. We prove $h(n!)\le(2\log2+o(1))\,n/\log n$. This improves the bounds of order $n/(\log n)^{1/2-\varepsilon}$ established in Tenenbaum-Yokota's Lemma 4 and Yokota's 1995 knapsack note. We...

S. D. Hughes · 0 citations
Preprint Sep 2026

Efficient Computation and Congruences for Colored Partition Functions

For a positive integer $\alpha$, let $p_\alpha(n)$ denote the number of $\alpha$-colored partitions of $n$. The Rademacher-type expansion of Iskander, Jain, and Talvola is valid for every real $\alpha>0$, but when $\alpha>24$ it involves several polar terms and a two-parameter family of exponential sums $A_k^{(\alpha)}...

Jean Carlos Villegas-Morales · 0 citations

We use cookies to run the site and, with your consent, for analytics and to show ads. See our Cookie Policy.