The number of squares and higher powers in an arithmetic progression: Rudin's conjecture and the Bombieri–Granville–Pintz $k$-th power bounds

How many perfect squares can occur among the first $N$ terms of an integer arithmetic progression? Fermat proved that no four distinct squares form a progression, and Szemerédi proved Erdős's conjecture that the maximum count $Q(N)$ is $o(N)$. Rudin conjectured in 1960 that $Q(N)=O(\sqrt N)$, with the sharp asymptotic expected to be $Q(N)\sim\sqrt{8N/3}$, attained by the progression $24n+1$. Bombieri, Granville and Pintz (Duke Math. J., 1992) proved the first power-saving bound $Q(N)\le c_1N^{2/3}(\log N)^{c_2}$ using Faltings' theorem on curves of genus 5, and stated without proof that the method should give $Q_3(N)\lesssim N^{3/5}$ for cubes and $Q_k(N)\lesssim N^{1/2}$ for $k\ge4$; Bombieri–Zannier (2002) improved the squares exponent to $3/5$, which remains the best known for unrestricted common differences. The surviving open core is establishing upper bounds of the conjectured order, uniformly over all progressions, for the number of squares (Rudin's conjecture, its sharp asymptotic, or the strong form $Q(N)=Q(N;24,1)$ for $N\ge6$) and for the number of $k$-th powers with $k\ge3$. All currently known bounds of the conjectured order require restrictions on the common difference (few divisors, polynomially bounded, or fixed progression) or unproved arithmetic-geometry conjectures (the Bombieri–Lang uniformity conjecture, the ABC conjecture), and the gap between the exponents $3/5$ and $1/2$ for squares has remained open since 2002.

Background

An arithmetic progression (AP) of length $N$ is a sequence $a, a+q, a+2q, \ldots, a+(N-1)q$ with integers $a$ and $q\ne0$. For an integer $k\ge2$, let $Q_k(N;q,a)$ be the number of $k$-th powers of integers among these $N$ terms, and let $Q_k(N)=\max_{a,\,q\ne0}Q_k(N;q,a)$ be the maximum over all nontrivial progressions; write $Q(N)=Q_2(N)$. Taking $a=0$, $q=1$, the terms $0,1,\ldots,N-1$ contain $\lceil N^{1/k}\rceil$ $k$-th powers, so $Q_k(N)\ge N^{1/k}$: the conjectured order $N^{1/k}$, if true, is sharp. The problem is to determine the order of magnitude of $Q_k(N)$, above all for squares.

Fermat proved (with the first complete proof published by Euler) that no four distinct squares form an arithmetic progression; since among any four consecutive terms of a progression at most three can then be squares, $Q(N)\le(3N+3)/4$. Erdős conjectured that squares cannot be dense inside a long progression, $Q(N)=o(N)$; Szemerédi proved this in 1974 by combining his theorem that every set of integers of positive relative density contains arbitrarily long arithmetic progressions with Fermat's four-squares theorem. This qualitative argument gives no power saving, and the quantitative problem remained open (for this history see the account by Granville, 2017).

The sharp prediction comes from W. Rudin's 1960 paper "Trigonometric series with gaps", written in connection with his theory of $\Lambda(p)$-sets (a set $E$ of integers is a $\Lambda(p)$-set if the $L^p$ norm of every trigonometric series with frequencies in $E$ is bounded by a constant times its $L^2$ norm), because the squares inside an arithmetic progression control such estimates. Rudin conjectured that $Q(N)=O(\sqrt N)$; the commonly used weak form is $Q(N)\ll_\varepsilon N^{1/2+\varepsilon}$ for every $\varepsilon>0$ (here $\ll$ is Vinogradov's notation, hiding a constant depending at most on the subscripts). The evidence is the progression $24n+1$: a square $m^2$ is congruent to $1$ modulo $24$ exactly when $m$ is coprime to $6$, and $m^2=24n+1$ holds precisely when $n$ is a generalized pentagonal number, $n=k(3k\pm1)/2$ for some integer $k$, because $24\cdot k(3k\pm1)/2+1=(6k\pm1)^2$. There are $\sim\sqrt{8N/3}$ generalized pentagonal numbers below $N$, so $Q(N)\ge\sqrt{8N/3}+O(1)$. The strong form of Rudin's conjecture asserts that this is optimal: $Q(N)=Q(N;24,1)$ for every $N\ge6$, that is, no progression of any length beats $24n+1$.

Bombieri, Granville and Pintz (1992) obtained the first bound with a power saving: $Q(N)\le c_1N^{2/3}(\log N)^{c_2}$ with effectively computable constants. Fixing $q$ and $a$, each square $a+n_iq=m_i^2$ in the progression determines a rational point from which the position $n_i$ is recoverable; four solutions cut out the intersection of two quadrics in projective 3-space, an elliptic curve, and five solutions cut out curves of genus 5 (the genus is the number of handles of the Riemann surface of the curve). By Faltings' theorem (finiteness of the set of rational points on a curve of genus at least 2) such curves have only finitely many rational points; combining this with the Mordell–Weil theorem (the statement that the rational points on the Jacobian of a curve form a finitely generated abelian group, used here to bound the relevant ranks) and with the large sieve (a classical analytic inequality bounding how many integers in a range can simultaneously avoid a given family of residue classes) for small common differences, they obtained the $2/3$ bound. The crux of the remaining difficulty is progressions whose difference $q$ is very large and divisible by many small primes. They also stated, without proof, that the method should give $Q_3(N)\lesssim N^{3/5}$ for cubes and $Q_k(N)\lesssim N^{1/2}$ for $k\ge4$, flagging "further complications" in controlling the Mordell–Weil groups of the Jacobians of the curves attached to runs of $k$-th powers; and they announced a companion paper of Bombieri on the number of rational points of algebraic curves that was to make the diophantine-geometric input more explicit.

Bombieri and Zannier (2002) improved the exponent to $3/5$: $Q(N)\le c_1N^{3/5}(\log N)^{c_2}$ with computable constants, by a substantial simplification that works only with elliptic curves (curves of genus 1, carrying a group law on their rational points) arising from four solutions; the uniform bounds on rational points of bounded height on the relevant elliptic curves, in terms of the height of the curve, appear in their companion paper of 2004. This is still the best unconditional upper bound for $Q(N)$ when the common difference is unrestricted, as confirmed by Bourgain–Demeter in 2018, by Croot–Mao–Yip in 2026 and by Novaković in 2026.

For higher powers, Bourgain and Demeter (2018) conjectured the sharper form $Q_k(N)\lessapprox N^{1/k}$ for every $k\ge2$ (where $\lessapprox$ suppresses factors of order $(\log N)^{O(1)}$), and proved it for progressions whose step $q$ has $d(q)=O(1)$ divisors ($d(q)$ is the number of positive divisors of $q$), by an induction exploiting the multiplicative structure of the step; Novaković (2026) extended the argument to $d(q)\lesssim N^{1/(k(k+1))}\log^{O(1)}N$ and, for $N>N_0(\varepsilon,k)$, to all polynomially bounded steps. For a fixed progression, Hajdu and Tengely (2021) completely described the progressions containing asymptotically the most $\ell$-th powers ($24x+1$ for squares), and Hajdu and Papp (2022) proved that each fixed progression contains at most $(1+\varepsilon)N^{1/\ell}$ $\ell$-th powers for all $N$ beyond a bound depending on the progression. None of these results is uniform over all progressions. Unconditionally, for $k\ge3$ no power-saving bound is known at all: the best quantitative statement, recorded by Croot–Mao–Yip (2026), combines a quantitative form of Roth's theorem with the theorem of Darmon and Merel (1997) that no three distinct $k$-th powers form a progression for $k\ge3$, and gives $Q_k(N)\le N\exp(-c(\log N)^{1/9})$ — still $N^{1-o(1)}$.

Conditionally on arithmetic-geometry conjectures the picture improves but does not close. Cilleruelo and Granville (2007) showed that the Bombieri–Lang conjecture (the standard arithmetic-geometry conjecture implying that the number of rational points on a curve of genus at least 2 is bounded uniformly across all such curves) implies only $\sigma(k)\ll k^{4/5}$ ($\sigma$ is their notation for the same maximum count), weaker than the unconditional $3/5$; Shkredov and Solymosi (2021), assuming the Uniformity Conjecture of Caporaso–Harris–Mazur (a consequence of Bombieri–Lang for the curves $y^k=f(x)$, $f$ a polynomial), proved $Q(N)\ll N^{2/3}$ for squares — again weaker than $3/5$ — as well as $Q_3(N)\ll N^{2/3}\exp(-O(\log^\alpha N))$ for every fixed $\alpha<1/11$ and $Q_k(N)\ll N^{1/2}\exp(-O((\log N)^{1/3}))$ for $k>3$, the latter breaking the square-root barrier but not reaching $N^{1/k}$. Croot, Mao and Yip (2026), assuming the abc conjecture (the standard conjecture relating $a+b=c$ for coprime positive integers to the product of the distinct prime divisors of $abc$), proved $Q_k(N)\le N^{1/k}\exp(C_k\sqrt{\log N/\log\log N})$ for $k\ge4$, which is nearly sharp; for $k\in\{2,3\}$ no bound of the conjectured order is known even conditionally on ABC. So neither of the two standard arithmetic-geometry conjectures currently yields the conjectured order for squares or cubes.

Two further circles frame the problem. The strong Rudin conjecture has been verified computationally for $6\le N\le52$ by González-Jiménez and Xarles (2014), who classified the extremal progressions by combining covering arguments with arithmetic-geometric computations. And the effectiveness question that Bombieri–Granville–Pintz deferred to a forthcoming paper of Bombieri remains embedded in the broader still-open problem of uniform bounds for rational points on curves of genus $\ge2$: such uniformity would follow from the Bombieri–Lang conjecture (Caporaso–Harris–Mazur, 1997), and unconditional uniform bounds are known only in restricted classes (Katz–Rabinoff–Zureick-Brown, 2016, for curves whose Mordell–Weil rank is at most $g-3$; García-Fritz–Pasten, 2025, for curves with sufficiently many automorphisms). Adjacent lines of work — squares in arithmetic progressions over number fields (Xarles, 2012), and the dual problem of progressions avoiding squares (Croot–Lyall–Rice, 2015; Dietmann–Elsholtz, 2026) — do not address the uniform integer bound.

Problem Statement

Let $Q_k(N;q,a)$ denote the number of $k$-th powers of integers among the terms $a+qn$, $0\le n<N$, where $a$ and $q\ne0$ are integers, and let $Q_k(N)=\max_{a,\,q\ne0}Q_k(N;q,a)$; write $Q(N)=Q_2(N)$. Note $Q_k(N)\ge\lceil N^{1/k}\rceil$ (take $a=0$, $q=1$), so the conjectured order $N^{1/k}$ is sharp. Prove, or refute, the following conjectured upper bounds, each required to hold uniformly over all nontrivial arithmetic progressions — with no restriction on the common difference $q$, the offset $a$, or the number of divisors of $q$:

(1) Rudin's conjecture for squares: $Q(N)=O(\sqrt N)$, in the commonly used weak form $Q(N)\ll_\varepsilon N^{1/2+\varepsilon}$ for every $\varepsilon>0$ (Vinogradov notation: the implied constant depends only on the subscript); more sharply, $Q(N)=(1+o(1))\sqrt{8N/3}$; in strongest form, $Q(N)=Q(N;24,1)$ for every $N\ge6$.

(2) The Bombieri–Granville–Pintz conjectures for higher powers: $Q_3(N)\ll_\varepsilon N^{3/5+\varepsilon}$ and, for every $k\ge4$, $Q_k(N)\ll_\varepsilon N^{1/2+\varepsilon}$; or the sharper Bourgain–Demeter conjecture: $Q_k(N)\lessapprox N^{1/k}$ for every $k\ge2$ (as in the Background, $\lessapprox$ suppresses factors of order $(\log N)^{O(1)}$).

Component (1) is the central instance of the problem; component (2) is the extension of the same question posed together with it by Bombieri, Granville and Pintz. Within each component a stronger form implies the weaker ones, and a refutation of a stronger form leaves the weaker forms open. The best current unconditional bounds are $Q(N)\le c_1N^{3/5}(\log N)^{c_2}$ for squares (Bombieri–Zannier, 2002) and, for $k\ge3$, only $Q_k(N)\le N\exp(-c(\log N)^{1/9})$ (Croot–Mao–Yip, 2026, via a quantitative form of Roth's theorem — the 3-term case of Szemerédi's density theorem, on three-term arithmetic progressions inside sets of positive relative density — together with Darmon–Merel); bounds of the conjectured order are known only under restrictions on the step $q$ (Bourgain–Demeter: $d(q)=O(1)$, where $d(q)$ denotes the number of positive divisors of $q$; Novaković: $d(q)\lesssim N^{1/(k(k+1))}\log^{O(1)}N$, or $q\lesssim N^r$ with $N>N_0(\varepsilon,k)$) or for a fixed progression (Hajdu–Tengely, Hajdu–Papp), or conditionally on arithmetic-geometry conjectures (Cilleruelo–Granville, Shkredov–Solymosi under the Uniformity Conjecture; Croot–Mao–Yip under ABC, $k\ge4$ only). No restricted or conditional result currently known reaches the conjectured order $N^{1/k}$ uniformly over all progressions.

References

1. Enrico Bombieri, Andrew Granville, János Pintz, Squares in arithmetic progressions, Duke Mathematical Journal 66 (1992), no. 3, 369–385. DOI: 10.1215/s0012-7094-92-06612-9, https://doi.org/10.1215/s0012-7094-92-06612-9; zbMATH Zbl 0771.11034, https://zbmath.org/0771.11034.
2. W. Rudin, Trigonometric series with gaps, Journal of Mathematics and Mechanics 9 (1960), no. 2, 203–227. zbMATH Zbl 0091.05802, https://zbmath.org/0091.05802.
3. E. Szemerédi, The number of squares in an arithmetic progression, Studia Scientiarum Mathematicarum Hungarica 9 (1974), 417. zbMATH Zbl 0318.10029, https://zbmath.org/0318.10029.
4. Enrico Bombieri, The Mordell conjecture revisited, Annali della Scuola Normale Superiore di Pisa, Classe di Scienze, Serie IV 17 (1990), no. 4, 615–640. Open-access copy: https://www.numdam.org/item/ASNSP_1990_4_17_4_615_0/.
5. Enrico Bombieri, Umberto Zannier, A note on squares in arithmetic progressions. II, Atti della Accademia Nazionale dei Lincei. Rendiconti Lincei. Matematica e Applicazioni, Serie 9, 13 (2002), no. 2, 69–75. zbMATH Zbl 1072.11010, https://zbmath.org/1072.11010; open-access copy: https://geodesic.mathdoc.fr/item/RLIN_2002_9_13_2_a0/.
6. Enrico Bombieri, Umberto Zannier, On the number of rational points on certain elliptic curves, Izvestiya: Mathematics 68 (2004), no. 3, 437–445. DOI: 10.1070/IM2004v068n03ABEH000483, https://doi.org/10.1070/IM2004v068n03ABEH000483; zbMATH Zbl 1080.11050, https://zbmath.org/1080.11050.
7. Javier Cilleruelo, Andrew Granville, Lattice points on circles, squares in arithmetic progressions and sumsets of squares, in: Additive Combinatorics, CRM Proceedings and Lecture Notes 43, American Mathematical Society, Providence, RI, 2007, pp. 241–262. DOI: 10.1090/crmp/043/12, https://doi.org/10.1090/crmp/043/12; also arXiv:math/0608109, https://arxiv.org/abs/math/0608109.
8. Enrique González-Jiménez, Xavier Xarles, On a conjecture of Rudin on squares in arithmetic progressions, LMS Journal of Computation and Mathematics 17 (2014), no. 1, 58–76. DOI: 10.1112/S1461157013000259, https://doi.org/10.1112/S1461157013000259; also arXiv:1301.5122, https://arxiv.org/abs/1301.5122.
9. Jean Bourgain, Ciprian Demeter, On the number of kth powers inside arithmetic progressions, preprint (2018). arXiv:1811.11919, https://arxiv.org/abs/1811.11919.
10. Lajos Hajdu, Szabolcs Tengely, Powers in arithmetic progressions, The Ramanujan Journal 55 (2021), no. 3, 965–986. DOI: 10.1007/s11139-020-00331-5, https://doi.org/10.1007/s11139-020-00331-5.
11. Lajos Hajdu, Á. Papp, Uniform bounds for the number of powers in arithmetic progressions, Revista de la Real Academia de Ciencias Exactas, Físicas y Naturales. Serie A. Matemáticas 116 (2022), article 169. DOI: 10.1007/s13398-022-01313-6, https://doi.org/10.1007/s13398-022-01313-6.
12. Andrew Granville, Squares in arithmetic progressions and infinitely many primes, The American Mathematical Monthly 124 (2017), no. 10, 951–954. DOI: 10.4169/amer.math.monthly.124.10.951, https://doi.org/10.4169/amer.math.monthly.124.10.951; also arXiv:1708.06951, https://arxiv.org/abs/1708.06951.
13. Ilya Shkredov, József Solymosi, The uniformity conjecture in additive combinatorics, SIAM Journal on Discrete Mathematics 35 (2021), no. 1, 307–321. DOI: 10.1137/20m1367672, https://doi.org/10.1137/20m1367672; also arXiv:2005.11559, https://arxiv.org/abs/2005.11559.
14. Saša Novaković, A comment on the number of $k$-th powers inside arithmetic progressions, preprint (2026). arXiv:2607.15895, https://arxiv.org/abs/2607.15895.
15. Ernie Croot, Junzhe Mao, Chi Hoi Yip, Hilbert cubes in sets with arithmetic properties, preprint (2026). arXiv:2603.14654, https://arxiv.org/abs/2603.14654.
16. H. Darmon, L. Merel, Winding quotients and some variants of Fermat's Last Theorem, Journal für die reine und angewandte Mathematik 490 (1997), 81–100. DOI: 10.1515/crll.1997.490.81, https://doi.org/10.1515/crll.1997.490.81.
17. Rainer Dietmann, Christian Elsholtz, Two-dimensional arithmetic progressions avoiding squares, Proceedings of the American Mathematical Society 154 (2026), no. 11, 4657–4666. DOI: 10.1090/proc/17810, https://doi.org/10.1090/proc/17810; also arXiv:2605.11104, https://arxiv.org/abs/2605.11104.
18. Ernie Croot, Neil Lyall, Alex Rice, Polynomials and primes in generalized arithmetic progressions, International Mathematics Research Notices 2015 (2015), no. 15, 6021–6043. DOI: 10.1093/imrn/rnu112, https://doi.org/10.1093/imrn/rnu112.
19. Xavier Xarles, Squares in arithmetic progression over number fields, Journal of Number Theory 132 (2012), no. 3, 379–389. DOI: 10.1016/j.jnt.2011.07.010, https://doi.org/10.1016/j.jnt.2011.07.010; also arXiv:0909.1642, https://arxiv.org/abs/0909.1642.
20. Lucia Caporaso, Joe Harris, Barry Mazur, Uniformity of rational points, Journal of the American Mathematical Society 10 (1997), no. 1, 1–35. DOI: 10.1090/S0894-0347-97-00195-1, https://doi.org/10.1090/S0894-0347-97-00195-1; zbMATH Zbl 0872.14017, https://zbmath.org/0872.14017.
21. Eric Katz, Joseph Rabinoff, David Zureick-Brown, Uniform bounds for the number of rational points on curves of small Mordell–Weil rank, Duke Mathematical Journal 165 (2016), no. 16, 3189–3240. DOI: 10.1215/00127094-3673558, https://doi.org/10.1215/00127094-3673558; also arXiv:1504.00694, https://arxiv.org/abs/1504.00694.
22. Natalia García-Fritz, Héctor Pasten, Effective Mordell for curves with enough automorphisms, preprint (2025). arXiv:2503.10443, https://arxiv.org/abs/2503.10443.