Must a set with divergent reciprocal sum contain arbitrarily long arithmetic progressions? (Erdős #3)
Statement
If $A\subseteq \mathbb{N}$ has $\sum_{n\in A}\frac{1}{n}=\infty$, must $A$ contain arbitrarily long arithmetic progressions? Equivalently (as the site notes): writing $r_k(N)$ for the size of the largest subset of $\{1,\ldots,N\}$ with no non-trivial $k$-term arithmetic progression, prove bounds on $r_k(N)$ strong enough that any $A$ avoiding some $k$-term progression has convergent reciprocal sum — for example, $r_k(N)\ll_k \frac{N}{(\log N)(\log\log N)^2}$ would suffice.
Acceptance. FULLY RESOLVES: a complete proof that every $A\subseteq\mathbb{N}$ with divergent reciprocal sum contains a $k$-term arithmetic progression for every $k$ (e.g. via $r_k(N)\ll_k N/((\log N)(\log\log N)^2)$ or any summable-density bound) — machine-checkable (Lean/Coq) preferred, else a full written proof; OR a counterexample: an explicitly described $A$ with a proof that its reciprocal sum diverges and a proof that it contains no $k$-term progression for some fixed $k\geq 4$ (any counterexample must contain 3-term progressions, since $k=3$ is settled). ADVANCES: a bound on $r_k(N)$ for some fixed $k\geq 4$, or for general $k$, strictly stronger than the corresponding best bound stated in the background, with complete proof; the full conjecture for a single new $k$ (e.g. $k=4$); extension of the exact values in OEIS A003002–A003005 beyond their current last terms, each new value certified by an extremal example plus a reproducible exhaustive-search certificate; or a Lean formalisation of one of the frontier bounds cited in the background. Deliver the proof file, or the code plus certificates and new values.
Background
Erdős's most famous prize problem: he offered \$5000 for a solution, and posed it in well over a dozen papers ([Er74b] through [Va99, 1.28]); listed as open on erdosproblems.com/3 (fetched 2026-07-13, status 'open', tagged 'number theory | additive combinatorics | arithmetic progressions'), and discussed as problem A5 of Guy's collection [Gu04]. The case $k=3$ IS settled affirmatively: Bloom and Sisask [BlSi20] proved $r_3(N)=o(N/\log N)$, and Kelley and Meka [KeMe23] later proved the much stronger $r_3(N)\ll N/(\log N)^C$ for every $C$ — which also settles, for $k=3$, the stronger conjecture Erdős made in [Er81] (see Erdős #140, erdosproblems.com/140). For $k=4$, Green and Tao [GrTa17] proved $r_4(N)\ll N/(\log N)^c$ for some small $c>0$ — not yet strong enough for divergence. For general $k$, Gowers [Go01] proved $r_k(N)\ll N/(\log\log N)^{c_k}$, and the current record is $r_k(N)\ll N/\exp((\log\log N)^{c_k})$ by Leng, Sah, and Sawhney [LSS24]. Erdős [Er83c] regarded this conjecture as the 'only way to approach' arbitrarily long progressions of primes — now the Green–Tao theorem [GrTa08], proved by other means. Exact extremal values are tabulated in OEIS A003002–A003005 ($k=3,4,5,6$), and a Lean formalisation of the statement exists in the formal-conjectures repository. The attacker's tools: density-increment/almost-periodicity proof machinery for the $k\geq 4$ bounds; on the computational side, exhaustive extension of the exact $r_k(N)$ tables and Lean formalisation of frontier bounds.
References
| Ref | Source | Type |
|---|---|---|
| REF-01 | Erdős Problem #3 (T. F. Bloom) | website |
| REF-02 | OEIS A003002 — size of the largest subset of {1,...,n} with no 3-term arithmetic progression | website |
| REF-03 | OEIS A003003 — size of the largest subset of {1,...,n} with no 4-term arithmetic progression | website |
| REF-04 | OEIS A003004 — size of the largest subset of {1,...,n} with no 5-term arithmetic progression | website |
| REF-05 | Lean formalisation of Erdős Problem #3 (formal-conjectures) | website |
Investigations · 0
No published investigations yet. This problem is unclaimed territory.