Erdős conjecture on arithmetic progressions: does every set of positive integers with divergent reciprocal sum contain arbitrarily long arithmetic progressions?

A 2019 note of Fraser proves that every 'large set' in the sense of Erdős–Turán — a set $X\subseteq\mathbb{Z}^+$ with divergent reciprocal sum $\sum_{x\in X}1/x=\infty$ — gets arbitrarily close to arbitrarily long arithmetic progressions, and highlights as the principal open problem the genuine, exact version of the Erdős–Turán (Erdős) conjecture: must such an $X$ actually contain arithmetic progressions of every length? This is the famous Erdős conjecture on arithmetic progressions. It remains open: the case of 3-term progressions was settled by Bloom and Sisask (2020), strengthened by Kelley and Meka (2023), but for progressions of length 4 and beyond — and hence for the full 'arbitrarily long' statement — no proof or counterexample is known.

Background

An arithmetic progression (AP) of length $k>1$ and gap $\Delta>0$ is a set $\{x, x+\Delta, x+2\Delta,\dots, x+(k-1)\Delta\}$, i.e. $k$ points with a common spacing. A central theme of additive combinatorics and combinatorial number theory is finding long APs inside sets defined by weak 'largeness' conditions. A set of positive integers has positive upper density if $\limsup_{N\to\infty}|X\cap\{1,\dots,N\}|/N>0$. Szemerédi's theorem (1975) proves that every set of positive upper density contains arbitrarily long APs; it settled the density conjecture that Erdős and Turán posed in 1936. A strictly stronger 'largeness' condition, not implying positive upper density, is divergence of the reciprocal sum: $X\subseteq\mathbb{Z}^+$ is large in the sense of Erdős–Turán when $\sum_{x\in X}1/x=\infty$. The primes are such a set, since Euler proved that the reciprocals of the primes diverge, and the Green–Tao theorem (2008) shows that the primes contain arbitrarily long APs — a deep special case. The famous Erdős conjecture on arithmetic progressions (also called the Erdős–Turán conjecture in this context, and one of the problems for which Erdős offered his largest monetary prizes) asserts that every such large set contains arbitrarily long APs; it implies Szemerédi's theorem and the Green–Tao theorem as special cases, and remains one of the landmark open problems of combinatorial number theory. Fraser's note (2019) isolates exactly why the conjecture is hard for current methods. He defines a weak notion of approximate containment: $X$ gets arbitrarily close to arbitrarily long APs if for every $k\in\mathbb{N}$ and $\varepsilon>0$ there is an AP $P$ of length $k$ and gap $\Delta>0$ with $\sup_{p\in P}\inf_{x\in X}|p-x|\le\varepsilon\Delta$, the factor $\varepsilon\Delta$ being the natural scale normalization. Fraser proves (Theorem 1.4) that every large set gets arbitrarily close to arbitrarily long APs, via three elementary lemmas starting from Euler's divergence of $\sum 1/p$; the same conclusion for the primes follows from Green–Tao or directly. Thus the approximate, geometric version of the conjecture is elementary — while the exact combinatorial conclusion (actual containment of exact APs of every length) is wide open. Quantitatively, writing $r_k(N)$ for the size of the largest subset of $\{1,\dots,N\}$ containing no AP of length $k$, the conjecture is equivalent to the assertion that the reciprocal sum of every $k$-AP-free set converges, which by partial summation would follow from bounds $r_k(N)\ll N/(\log N)^{1+c_k}$. For $k=3$ such bounds now exist: Bloom and Sisask (2020) proved $r_3(N)\ll N/(\log N)^{1+c}$ for some absolute $c>0$, which by partial summation settles the $k=3$ case of Erdős's conjecture, and Kelley and Meka (2023) strengthened this to the quasi-polynomial bound $r_3(N)\ll 2^{-O((\log N)^{\beta})}N$. For $k\ge 4$ the best known bounds for $r_k(N)$ (of Gowers- and Green–Tao-type, far weaker than $N/(\log N)^{1+c}$) do not force convergence of the reciprocal sum, and all known constructions of sets avoiding long APs have convergent reciprocal sums, so neither direction of the general conjecture is within reach of current technology.

Problem Statement

Does every set $X\subseteq\mathbb{Z}^+$ of positive integers with divergent reciprocal sum $\sum_{x\in X}\frac{1}{x}=\infty$ contain arithmetic progressions of every length — that is, for each integer $k>1$, elements $x, x+\Delta, x+2\Delta,\dots, x+(k-1)\Delta\in X$ with $\Delta>0$? Equivalently: for every $k$, must the reciprocal sum of a set of positive integers containing no $k$-term arithmetic progression converge? This is the exact ('genuine') Erdős–Turán, i.e. Erdős, conjecture on arithmetic progressions that Fraser's note (arXiv:1809.01409) poses against its proved approximate counterpart (Theorem 1.4, which guarantees only approximate APs in the $\varepsilon\Delta$ sense). The $k=3$ case is settled affirmatively by Bloom–Sisask (2020) and Kelley–Meka (2023); the problem remains open for progressions of length $k\ge 4$, and the conjecture in its original full generality — arbitrarily long progressions from divergence of the reciprocal sum alone — is what must be proved or refuted.

References

1. Jonathan M. Fraser, 'Almost arithmetic progressions in the primes and other large sets', arXiv:1809.01409 (v2, 2019), https://arxiv.org/abs/1809.01409
2. Paul Erdős and Paul Turán, 'On Some Sequences of Integers', Journal of the London Mathematical Society s1-11 (1936), 261–264, DOI 10.1112/jlms/s1-11.4.261, https://doi.org/10.1112/jlms/s1-11.4.261
3. E. Szemerédi, 'On sets of integers containing no k elements in arithmetic progression', Acta Arithmetica 27 (1975), 199–245, DOI 10.4064/aa-27-1-199-245, https://doi.org/10.4064/aa-27-1-199-245
4. Benjamin Green and Terence Tao, 'The primes contain arbitrarily long arithmetic progressions', Annals of Mathematics 167 (2008), 481–547, DOI 10.4007/annals.2008.167.481, https://doi.org/10.4007/annals.2008.167.481
5. Thomas F. Bloom and Olof Sisask, 'Breaking the logarithmic barrier in Roth's theorem on arithmetic progressions', arXiv:2007.03528 (2020), https://arxiv.org/abs/2007.03528
6. Zander Kelley and Raghu Meka, 'Strong Bounds for 3-Progressions', arXiv:2302.05537 (2023), https://arxiv.org/abs/2302.05537
7. Sarah Peluse, 'Recent progress on bounds for sets with no three terms in arithmetic progression (after Bloom and Sisask, Croot, Lev, and Pach, and Ellenberg and Gijswijt)', Séminaire Bourbaki, Astérisque 438, Exposé 1196 (2022), DOI 10.24033/ast.1197, https://doi.org/10.24033/ast.1197