Erdős's conjecture on arithmetic progressions (Jensen's zero-solution-set formulation): does every set of natural numbers with divergent reciprocal sum contain arbitrarily long arithmetic progressions?

The question, in the formulation of Jensen's preprint 'On arithmetic progressions in nullspaces of integer matrices' (arXiv:1106.2937), is whether every set $A\subseteq\mathbb{N}$ whose reciprocal sum $\sum_{a\in A}1/a$ diverges must be a 'zero-solution set': every integer matrix whose nullspace has dimension at least two and contains the all-ones vector admits infinitely many solutions with all coordinates in $A$, not all equal. Jensen proved this property equivalent to containing arithmetic progressions of every finite length, so the question is exactly the classical Erdős conjecture on arithmetic progressions, one of the most famous open problems in additive combinatorics. Szemerédi's theorem (positive upper density) and the Green–Tao theorem (primes) are major special cases; Bloom and Sisask (2020) resolved the length-3 case by proving that a divergent reciprocal sum forces infinitely many 3-term progressions, a bound strengthened by Kelley and Meka (2023). The conjecture remains open for progressions of length 4 and above.

Background

An arithmetic progression (AP) of length $k$ is a set of the form $\{a, a+d, a+2d,\dots, a+(k-1)d\}$ with $a\ge 0$, $d\ge 1$. A central theme of additive combinatorics is how 'large' a set of natural numbers must be to contain APs of every finite length. Szemerédi's theorem (1975) settled the conjecture of Erdős and Turán (1936) in density form: every set of positive upper density (i.e., a set $A$ with $\limsup_{N\to\infty}|A\cap\{1,\dots,N\}|/N>0$) contains arbitrarily long APs. The Green–Tao theorem (2008) showed that the primes, although of density zero, contain arbitrarily long APs. Erdős later conjectured a much stronger, purely metric criterion: if $A\subseteq\mathbb{N}$ satisfies $\sum_{a\in A}1/a=\infty$ (a condition met by the primes, by Euler's theorem, but not by the squares), then $A$ contains arbitrarily long arithmetic progressions. This conjecture implies Szemerédi's theorem and has the Green–Tao theorem as an immediate corollary, and it remains open. Jensen's preprint (arXiv:1106.2937) contributes an equivalent linear-algebraic formulation. Call $A$ an AP-set if for every $k\ge 1$ some length-$k$ AP is contained in $A$. Call an integer matrix $M$ null-diagonal if its nullspace $N(M)=\{x: Mx=0\}$ has dimension at least two and contains the all-ones vector $(1,\dots,1)$. Call $A$ a zero-solution set if every null-diagonal matrix $M$ has infinitely many solutions $\bar{x}$ with all coordinates in $A$ and not all coordinates equal. Jensen's Theorem 16 proves that $A$ is a zero-solution set if and only if $A$ is an AP-set (the 'only if' direction uses the matrices whose nullspace is spanned by $(1,\dots,1)$ and $(0,1,2,\dots,n-1)$, whose solution vectors are exactly APs). Hence Erdős's conjecture is equivalent to: divergent reciprocal sum implies the zero-solution property. As for the true state of the problem: for 3-term progressions, Bloom and Sisask (2020, arXiv:2007.03528) proved that any $A\subseteq\{1,\dots,N\}$ with no 3-term AP has size $\ll N/(\log N)^{1+c}$, where $\ll$ means 'bounded above by a constant multiple of' and $c>0$ is an absolute constant; their Corollary 1.2 then deduces by partial summation (the standard technique for converting a bound on the counting function $|A\cap\{1,\dots,N\}|$ into a bound on the weighted sum $\sum_{a\in A}1/a$) that every $A\subseteq\mathbb{N}$ with $\sum_{a\in A}1/a=\infty$ contains infinitely many 3-term APs — the first non-trivial case of Erdős's conjecture. Kelley and Meka (2023, arXiv:2302.05537) strengthened the underlying density bound: writing $r_3(N)$ for the maximum size of a subset of $\{1,\dots,N\}$ containing no 3-term AP, they proved $r_3(N)\le 2^{-O((\log N)^{\beta})}N$ for an absolute constant $\beta>0$, which yields the same reciprocal-sum conclusion a fortiori. No comparable result is known for progressions of length 4 or more, where the problem stands wide open.

Problem Statement

Let $A\subseteq\mathbb{N}$ be a set of positive integers such that $\sum_{a\in A}1/a=\infty$. Prove, or refute, that $A$ contains an arithmetic progression of every finite length $k\ge 3$; equivalently (by Jensen's Theorem 16), prove, or refute, that $A$ is a zero-solution set: every integer matrix $M$ whose nullspace $N(M)$ satisfies $\dim N(M)\ge 2$ and contains the all-ones vector $(1,\dots,1)$ of length equal to the number of columns of $M$ admits infinitely many solutions $\bar{x}=(x_1,\dots,x_n)$ with all $x_i\in A$ and not all $x_i$ equal. The length-3 case is already a theorem (Bloom–Sisask 2020, arXiv:2007.03528: such an $A$ contains infinitely many non-trivial 3-term progressions), so the open content is progressions of length $k\ge 4$; a complete resolution must establish the implication for all lengths $k\ge 4$, or else exhibit a set $A$ with divergent reciprocal sum containing no arithmetic progression of some fixed length $k\ge 4$.

References

1. Jonas Lindstrøm Jensen, "On arithmetic progressions in nullspaces of integer matrices", arXiv:1106.2937 (2011), DOI 10.48550/arXiv.1106.2937, https://arxiv.org/abs/1106.2937
2. Thomas F. Bloom and Olof Sisask, "Breaking the logarithmic barrier in Roth's theorem on arithmetic progressions", arXiv:2007.03528 (2020), DOI 10.48550/arXiv.2007.03528, https://arxiv.org/abs/2007.03528
3. Zander Kelley and Raghu Meka, "Strong Bounds for 3-Progressions", arXiv:2302.05537 (2023), DOI 10.48550/arXiv.2302.05537, https://arxiv.org/abs/2302.05537
4. Benjamin Green and Terence Tao, "The primes contain arbitrarily long arithmetic progressions", Annals of Mathematics (2) 167 (2008), no. 2, pp. 481–547, DOI 10.4007/annals.2008.167.481, https://doi.org/10.4007/annals.2008.167.481
5. E. Szemerédi, "On sets of integers containing k elements in arithmetic progression", Acta Arithmetica 27 (1975), pp. 199–245, DOI 10.4064/aa-27-1-199-245, https://doi.org/10.4064/aa-27-1-199-245
6. Paul Erdős and Paul Turán, "On Some Sequences of Integers", Journal of the London Mathematical Society s1-11 (1936), no. 4, pp. 261–264, DOI 10.1112/jlms/s1-11.4.261, https://doi.org/10.1112/jlms/s1-11.4.261