Problem 142

Let $r_k(N)$ be the largest possible size of a subset of $\{1,\ldots,N\}$ that does not contain any non-trivial $k$ -term arithmetic progression. Prove an asymptotic formula for $r_k(N)$ .

Source: erdosproblems.com/142

Additive combinatorics
Arithmetic progressions

Wiki page

Status

Open

No claim settles this problem.

Open. The OpenAI mathematics release of 23 September 2026 claims $r_k(N)\le C_kN\exp(-c_k(\log N)^{\varepsilon_k})$ for every fixed $k\ge3$ , an upper bound beyond those recorded below for $k\ge4$ . It gives no asymptotic formula, no order of magnitude and no answer to whether $r_k(N)/r_{k+1}(N)\to0$ for any $k$ , so it settles no instance of the problem and has no claim page. The bound would also give $r_k(N)=o(N/\log N)$ , which the formal-conjectures file linked under Formalization states as the open variant erdos_142.variants.lower; the site's commentary attaches that statement to Problem 3, not to this problem. The theorem is recorded on the claim page of Problem 139 (OpenAI, 2026), and its reciprocal-sum corollary is accepted on the claim page of Problem 3 (OpenAI, 2026). The site's label is OPEN (page last edited 4 April 2026).

Er80: Erdős, Paul, A survey of problems in combinatorial number theory. Ann. Discrete Math. (1980), 89-115.
Er81: Erdős, P., On the combinatorial problems which I would most like to see solved. Combinatorica (1981), 25-42.
Er97c: Erdős, Paul, Some of my favorite problems and results. The mathematics of Paul Erdős, I, Algorithms Combin. 13, Springer (1997), 47--67; printed pp. 50--51: "I offer $500 for a proof that $r_3(n)<n/(\log n)^c$ for every $c$ , and $1000 for any asymptotic formula for $r_k(n)$ ", with $r_k(n)$ defined as the smallest size forcing a $k$ -term progression. Library home: Erdős 1997; paged at Erdős 1997, Problem (p. 51).
GrTa17: Green, Ben and Tao, Terence, New bounds for Szemerédi's theorem, III: a polylogarithmic bound for $r_4(N)$ . Mathematika (2017), 944-1040.
KeMe23: Kelley, Z. and Meka, R., Strong Bounds for 3-Progressions. arXiv:2302.05537 (2023).
LSS24: Leng, J., Sah, A. and Sawhney, M., Improved bounds for Szemerédi's theorem. arXiv:2402.17995 (2024).
Va99: Various, Some of Paul's favorite problems. Booklet produced for the conference "Paul Erdős and his mathematics", Budapest, July 1999 (1999).

Problem 142

Status

Proof claims

Discussion