Open problem, Arithmetic and number theory, Combinatorics and discrete mathematics, posed 1973

Erdős conjecture on arithmetic progressions

OpenErdős

Let $A \subseteq \mathbb{Z}^+$ be a set of positive integers whose reciprocals form a divergent series, $\sum_{n \in A} \frac{1}{n} = \infty$ . Then $A$ contains arithmetic progressions of every finite length $k \ge 3$ .

Posed by, 1973Paul Erdős

Research frontier as of 2026

As of 2026, the conjecture is completely proved for $k = 3$ (Bloom–Sisask, 2020), with the quantitative bound subsequently sharpened to $r_3(N) \le \exp(-c (\log N)^{1/9}) N$ following Kelley–Meka (2023) and Bloom–Sisask (2023). For $k \ge 4$ , the conjecture remains open: the best upper bounds on $r_k(N)$ (Green–Tao for $k = 4$ , Leng–Sah–Sawhney 2024 for $k \ge 5$ giving $r_k(N) \le N \exp(-(\log \log N)^{c_k})$ ) are still too weak to make $\sum r_k(N)/N^2$ converge.

Best known results

Every set $A$ with $\sum_{n \in A} \frac{1}{n} = \infty$ contains infinitely many $3$ -term arithmetic progressions (Bloom and Sisask, 2020).
Quasi-polynomial bound for $3$ -term progressions: $r_3(N) \le \exp(-c (\log N)^{1/9}) N$ (Kelley–Meka, 2023; Bloom–Sisask, 2023).
For $k \ge 5$ , improved inverse theorem bounds give $r_k(N) \le N \exp(-(\log \log N)^{c_k})$ (Leng, Sah, and Sawhney, 2024).

Tools and where they stop

Tool	Achieved	Where it stops
Spectral boosting, almost-periodicity, and sifting in Fourier analysis	Resolves the $k = 3$ case by showing that $3$ -progression-free sets have strong density increments on Bohr sets, yielding $r_3(N) \ll N / (\log N)^{1+\varepsilon}$ .	Linear Fourier analysis only controls $3$ -term progressions; progressions of length $k \ge 4$ depend on higher-order Gowers uniformity norms $U^{k-1}$ .
Higher-order Fourier analysis and Gowers $U^{k-1}$ inverse theorems	Correlates functions having large $U^{k-1}$ norm with nilsequences, yielding explicit quantitative bounds $r_k(N) = o(N)$ for all $k \ge 4$ .	Passing to high-dimensional nilmanifolds incurs double-logarithmic losses, falling short of the $N / (\log N)^{1+\varepsilon}$ bound needed for $\sum_{N} \frac{r_k(N)}{N^2} < \infty$ .

Open questions

Does every subset of $\mathbb{Z}^+$ with $\sum_{n \in A} \frac{1}{n} = \infty$ contain a $4$ -term arithmetic progression ( $k = 4$ )?
Does the bound $r_k(N) \ll N / (\log N)^{1 + \varepsilon}$ hold for all $k \ge 4$ ?

References

Thomas F. Bloom, Olof Sisask (2020). Breaking the logarithmic barrier in Roth's theorem on arithmetic progressions · arXiv:2007.03528
Zander Kelley, Raghu Meka (2023). Strong bounds for 3-progressions · arXiv:2302.05537
Ben Green, Terence Tao (2008). The primes contain arbitrarily long arithmetic progressions · DOI:10.4007/annals.2008.167.481