Research notes on every problem, and a library of the papers behind them. Built from the open erdos repository.

Updated Oct 8

Problem 142

Statement. 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)$ .

Status. 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, and its reciprocal-sum corollary is accepted on the claim page of Problem 3. The site's label is OPEN (page last edited 4 April 2026).

Source. erdosproblems.com/142, accessed 2026-09-04. Cite as: T. F. Bloom, Erdős Problem #142, https://www.erdosproblems.com/142.

References.

[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: erdos_1997_some_my_favorite_problems_results; paged at problem_p51.
[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).

Formalization. Statement in formal-conjectures at the revision current on 2026-10-06, which states the asymptotic as erdos_142 with answer(sorry) and a sorry body, together with three open variants, and carries no formal_proof attribute.

Progress

Not yet compiled.

Known Results

Not yet compiled.

Linked library material

These entries are derived from explicit links on library pages. They are navigation only and do not by themselves record mathematical progress.

Linked from (17)

Szemerédi's theorem on sets without long progressions Sumsets and Arithmetic Progressions Sumsets and Arithmetic Progressions additive_combinatorics/erdos_1957_unsolved_problems Problem 10 (p. 294): r_k(n), sets without k-term arithmetic progressions additive_combinatorics/green_2017_new_bounds_szemeredi_s_theorem Theorem 1.1 (p. 2): r_4(N) << N(log N)^{-c}Theorem 3.1 (p. 5): Khintchine-type recurrence with a thickness bound additive_combinatorics/kelley_2023_strong_bounds_3_progressions additive_combinatorics/leng_2024_improved_bounds_szemeredi_s_theorem Lemma 2.1 (p. 4): a Schmidt-type decomposition of [N] for several nilsequences Theorem 1.1 (p. 1): r_k(N) << N exp(-(log log N)^{c_k}) for every fixed k >= 5 additive_combinatorics/openai_2026_quasipolynomial_bounds_arithmetic_progressions Theorem 1.1: r_k(N) ≤ C_k N exp(-c_k (log N)^{ε_k}) for every fixed k ≥ 3 ramsey_theory/erdos_1997_some_my_favorite_problems_results Problem (p. 51): offers for r_3(n) < n/(log n)^c for every c and for an asymptotic formula for r_k(n)set_systems/erdos_1981_combinatorial_problems_which_i_would_most

Graph