Erdős's harmonic-set (divergent reciprocal sum) conjecture: must every set of natural numbers whose reciprocals sum to infinity contain arbitrarily long arithmetic progressions?

The problem originates in Hirschfeld's 2007 note "Harmonic ultrafilters" (arXiv:0709.1204), which studies the semigroup of harmonic ultrafilters on the natural numbers and states as its main open question the celebrated conjecture of Erdős: every set $A\subseteq\mathbb{N}$ whose reciprocals form a divergent series ($\sum_{a\in A}1/a=\infty$) must contain arithmetic progressions of arbitrary finite length. The conjecture implies Szemerédi's theorem; the prime special case is the Green–Tao theorem; the 3-term case is now a theorem via the quantitative Roth-type bound $r_3(N)\ll N/(\log N)^{1+c}$ of Bloom–Sisask (2020), strengthened by Kelley–Meka (2023); but the conjecture remains open for every progression length $k\ge 4$, and in full generality it is one of the most famous open problems in additive combinatorics and combinatorial number theory.

Background

A $k$-term arithmetic progression is a set of the form $\{a, a+d, \dots, a+(k-1)d\}$ with common difference $d\ge 1$. Szemerédi's theorem (1975) states that every subset of the natural numbers with positive upper density (the upper density of $A$ being $\limsup_{N\to\infty}|A\cap\{1,\dots,N\}|/N$) contains $k$-term progressions for every $k$; some largeness hypothesis is necessary, since lacunary sets such as the powers of $2$ contain no 3-term progression at all. A set $A\subset\mathbb{N}$ is called harmonic (or harmonically large) if the reciprocals of its elements form a divergent series, $\sum_{a\in A}1/a=\infty$. Harmonicity is a much weaker largeness condition than positive density: the set of primes is harmonic (a consequence of the prime number theorem) yet has density zero, and every positive-density set is harmonic. The family of harmonic sets is also partition regular: whenever a harmonic set is split into finitely many disjoint cells, at least one cell is harmonic. In the 1970s Paul Erdős conjectured that harmonicity alone already forces long progressions — every harmonic set contains arithmetic progressions of arbitrary finite length. This is the strongest standard density-type property conjectured to force arithmetic progressions; it directly implies Szemerédi's theorem, and Erdős attached to it one of his largest monetary prizes (commonly reported as $3,000).

The source, a short 2007 note of Rudi Hirschfeld, approaches the conjecture through the topological algebra of ultrafilters. An ultrafilter on $\mathbb{N}$ is a maximal family of subsets of $\mathbb{N}$ closed under finite intersections and taking supersets (equivalently, a finitely additive $\{0,1\}$-valued measure on all subsets of $\mathbb{N}$); the set of all ultrafilters, with a natural topology, forms the Stone–Čech compactification $\beta\mathbb{N}$ of $\mathbb{N}$, and ordinary addition on $\mathbb{N}$ extends to a compact semigroup operation on $\beta\mathbb{N}$ (the Glazer, or ultrafilter, addition) under which translations are continuous. Hindman (1988), in a paper establishing several equivalents of Erdős's conjecture, introduced the collection $\mathcal{D}$ of harmonic ultrafilters — those ultrafilters all of whose members are harmonic sets — and showed it is a closed right ideal of $\beta\mathbb{N}$. Hirschfeld proved that the smallest two-sided ideal of the compact semigroup $\mathcal{D}$ coincides with the smallest two-sided ideal $K(\beta\mathbb{N})$ of the whole semigroup. The sets belonging to ultrafilters in $K(\beta\mathbb{N})$ are exactly the piecewise syndetic sets — sets which, after thickening by intervals of some fixed bounded length, contain arbitrarily long runs of consecutive integers — and by a version of van der Waerden's theorem (every finite coloring of an interval contains a monochromatic long progression) every piecewise syndetic set contains arbitrarily long progressions. So the ideal structure of $\beta\mathbb{N}$ recovers long progressions for the piecewise syndetic harmonic sets; but the most famous harmonic set, the primes, is not piecewise syndetic, and its long progressions come instead from the Green–Tao theorem (2008). The ideal-level structure of $\mathcal{D}$ therefore does not currently reach general harmonic sets — exactly the gap the source note leaves open.

On the quantitative side, write $r_3(N)$ for the maximum size of a subset of $\{1,\dots,N\}$ containing no non-trivial 3-term progression; Roth's theorem is the statement $r_3(N)=o(N)$. If $r_3(N)\ll N/(\log N)^{1+c}$ for some constant $c>0$, then summing the dyadic-block bounds shows that every 3-progression-free set has convergent reciprocal sum, so every harmonic set must contain a 3-term progression. Bloom and Sisask (2020) established precisely this bound — their paper states it proves "the first non-trivial case of a conjecture of Erdős on arithmetic progressions" — and Kelley and Meka (2023) strengthened it to $r_3(N)\le N\exp(-c(\log N)^{1/12})$. For progressions of length $k\ge 4$, however, the best quantitative Szemerédi-type bounds available are only of the general shape $N/(\log N)^{c}$ for some constant $c$ depending on $k$ (for $k=4$, the Green–Tao bound $r_4(N)\ll N/(\log N)^{c}$ for some small $c>0$), far from the $N/(\log N)^{1+\delta}$ scale that would force progressions in every harmonic set. The conjecture for lengths $k\ge 4$ — and hence the general conjecture — remains open.

Problem Statement

Prove or disprove Erdős's conjecture on harmonic sets: must every set $A\subseteq\mathbb{N}$ with $\sum_{a\in A}1/a=\infty$ contain a $k$-term arithmetic progression for every $k$? The 3-term case ($k=3$) is known affirmatively, so the open content is the statement for every length $k\ge 4$ — equivalently, for all $k$ simultaneously — with no density, structure, regularity, or measurability side assumptions on $A$ beyond divergence of the reciprocal sum. The source paper's angle concerns whether the ultrafilter-level structure of the semigroup $\mathcal{D}$ of harmonic ultrafilters of $\beta\mathbb{N}$ reveals additional structural properties of harmonic sets strong enough to bridge the gap between harmonicity and the guarantee of arbitrarily long progressions (beyond what its identification $K(\mathcal{D})=K(\beta\mathbb{N})$ recovers for piecewise syndetic sets). The problem is resolved by a rigorous proof that every harmonic set contains arbitrarily long arithmetic progressions, or by an explicit harmonic set together with a proof that it avoids progressions of some fixed length $k$.

References

1. Rudi Hirschfeld, "Harmonic ultrafilters", arXiv:0709.1204 (2007), DOI: 10.48550/arXiv.0709.1204, https://arxiv.org/abs/0709.1204 (source paper)
2. Neil Hindman, "Some equivalents of the Erdős sum of reciprocals conjecture", European Journal of Combinatorics 9, no. 1 (1988), 39–47, DOI: 10.1016/S0195-6698(88)80025-8, https://doi.org/10.1016/S0195-6698(88)80025-8
3. Endre 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. Ben Green and Terence Tao, "The primes contain arbitrarily long arithmetic progressions", Annals of Mathematics (2) 167, no. 2 (2008), 481–547, DOI: 10.4007/annals.2008.167.481, arXiv:math/0404188, https://arxiv.org/abs/math/0404188
5. Thomas F. Bloom and Olof Sisask, "Breaking the logarithmic barrier in Roth's theorem on arithmetic progressions", arXiv preprint (2020), arXiv:2007.03528, DOI: 10.48550/arXiv.2007.03528, https://arxiv.org/abs/2007.03528
6. Zander Kelley and Raghu Meka, "Strong bounds for 3-progressions", Proceedings of the 64th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2023), IEEE Computer Society (2023), 933–973, DOI: 10.1109/FOCS57990.2023.00059, arXiv:2302.05537, https://arxiv.org/abs/2302.05537
7. Thomas F. Bloom and Olof Sisask, "The Kelley–Meka bounds for sets free of three-term arithmetic progressions", Essential Number Theory 2, no. 1 (2023), 15–44, DOI: 10.2140/ent.2023.2.15, arXiv:2302.07211, https://arxiv.org/abs/2302.07211
8. 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)", Exposé Bourbaki 1196, Séminaire Bourbaki, volume 2021/2022, Astérisque 438, Société Mathématique de France (2022), pp. 547–581, DOI: 10.24033/ast.1197, arXiv:2206.10037, https://doi.org/10.24033/ast.1197
9. Ben Green and Terence Tao, "New bounds for Szemerédi's theorem, II: A new bound for $r_4(N)$", in: Analytic number theory — Essays in honour of Klaus Roth on the occasion of his 80th birthday, Cambridge University Press (2009), pp. 180–204, arXiv:math/0610604, https://arxiv.org/abs/math/0610604