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

Updated Oct 7

Problem 201

Statement. Let $G_k(N)$ be such that any set of $N$ integers contains a subset of size at least $G_k(N)$ which does not contain a $k$ -term arithmetic progression. Determine the size of $G_k(N)$ . How does it relate to $R_k(N)$ , the size of the largest subset of $\{1,\ldots,N\}$ without a $k$ -term arithmetic progression? Is it true that

\lim_{N\to \infty}\frac{R_3(N)}{G_3(N)}=1?

Status. Open. The site's label is OPEN (page last edited 8 April 2026; site export of 2026-10-06); its commentary records the trivial $G_k(N)\le R_k(N)$ , that the inequality can be strict ( $G_3(5)=3$ against $R_3(5)=4$ ), and the theorem of Komlós, Sulyok and Szemerédi [KSS75] that $R_k(N)\ll_kG_k(N)$ . No claim page is recorded. Theorem 1.1 of the OpenAI release manuscript Quasipolynomial bounds for arithmetic progressions (23 September 2026) claims $R_k(N)\le C_kN\exp(-c_k(\log N)^{\varepsilon_k})$ for every fixed $k\ge3$ ; it bounds $G_k(N)$ from above only through the trivial inequality $G_k(N)\le R_k(N)$ and settles none of the problem's three questions, the size of $G_k(N)$ , its comparison with $R_k(N)$ and the limit of $R_3(N)/G_3(N)$ , so it has no claim page, and the problem is open with no claim.

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

References.

[KSS75] Komlós, J. and Sulyok, M. and Szemeredi, E., Linear problems in combinatorial number theory. Acta Math. Acad. Sci. Hungar. (1975), 113-121.
[Ri69] Riddell, J., On sets of numbers containing no $l$ terms in arithmetic progression. Nieuw Arch. Wisk. (3) (1969), 204-209.

Formalization. None recorded.

Current assessment

Known results. The inequality $G_k(N)\le R_k(N)$ holds because $\{1,\ldots,N\}$ is one set of $N$ integers, and it can be strict: $G_3(5)=3$ while $R_3(5)=4$ . In the other direction Komlós, Sulyok and Szemerédi [KSS75] proved $R_k(N)\ll_kG_k(N)$ with the explicit constant $2^{-15}$ : their residue reductions compress an arbitrary $N$ -element set into an interval of length $O(N)$ while keeping a fixed share of its elements and every solution of the progression relation (the library's comparison theorem and its progression corollary). A. Semchankau, Maximal subsets free of arithmetic progressions in arbitrary sets, Math. Notes 102 (2017), 396-402 (arXiv:2010.04490), improved the constant to $1/4$ along a dense sequence of $N$ : for every $k\ge3$ there are $N_1<N_2<\cdots$ , every segment $[N,Ne^{(\log N)^{1/2+o(1)}}]$ containing one, with $G_k(N)>(1/4+o(1))R_k(N)$ for each of them, by compressing modulo a prime twice and keeping about half the elements each time (the paper's card is semchankau_2020_maximal_subsets_free_arithmetic_progressions_arbitrary). These results leave a constant factor between $G_k(N)$ and $R_k(N)$ and do not decide whether $R_3(N)/G_3(N)\to1$ .

Upper bounds through $R_k(N)$ . Every upper bound on $R_k(N)$ bounds $G_k(N)$ from above. Theorem 1.1 of the OpenAI release manuscript Quasipolynomial bounds for arithmetic progressions (23 September 2026; intake card openai_2026_quasipolynomial_bounds_arithmetic_progressions, the theorem paged at Theorem 1.1) claims $R_k(N)\le C_kN\exp(-c_k(\log N)^{\varepsilon_k})$ for every fixed $k\ge3$ , a stretched-exponential saving over $N$ for every $k$ . The manuscript does not name $G_k(N)$ or this problem; the bound passes to $G_k(N)$ only through the trivial inequality and says nothing about the size of $G_k(N)$ itself, about its comparison with $R_k(N)$ beyond [KSS75], or about the ratio $R_3(N)/G_3(N)$ , so it settles no instance of the problem and has no claim page. For $k=3$ the claimed bound is weaker than the known bounds on $R_3(N)$ , which the manuscript says it does not improve. The release's Lean tree at its pinned revision proves the manuscript's reciprocal-sum theorem, recorded on Problem 3, and a weaker formal density bound, $r_k(N)\le CN\exp(-c(\log\log N)^{1+\eta})$ for $k\ge3$ ; neither names $G_k(N)$ , and this corpus's verification has not confirmed the build of the density declaration. The release states that its manuscripts were produced by an internal OpenAI model at different stages of verification.

Scope. This assessment rests on the site's page and commentary (export of 2026-10-06), the library's cards of [KSS75], of Semchankau's paper and of the release manuscript's Theorem 1.1; the site's reference [Ri69] is not held. It includes no search of the literature after 2020 beyond the release.

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 (21)

Sumsets and Arithmetic Progressions Problem 1207 additive_combinatorics/erdos_1979_old_new_problems_results_combinatorial_number additive_combinatorics/komlos_1975_linear_problems_combinatorial_number_theory Arithmetic-progression corollary — the E201 KSS bound Lemma 1′ — factorial pigeonhole compression Lemma 2 — first residue reduction Lemma 3 — sparse-collision residue reduction Lemma 4 — bounded-range residue reduction Lemma 5 — reduction to the first n integers Lemma 6 — averaging a translate Linear-relation setup for the KSS comparison theorem Remark 3 — relation-preserving residue compression Theorem (p. 114): every n integers hold a relation-free subset of a fixed share of f(n)KSS theorem — translation-invariant comparison 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 additive_combinatorics/semchankau_2020_maximal_subsets_free_arithmetic_progressions_arbitrary Hypothesis 1: removing εn elements compresses the rest into [n h(n)]Lemma 3.2: φ_k(n) > αn ρ_k(C_{α,k} n ln n)Theorem 1: φ_k(n) > (1/4 + o(1)) g_k(n) along a dense sequence of n

Graph