Prove an asymptotic formula for $r_k(N)$, the largest $k$-AP-free subset of $\{1,\ldots,N\}$ (Erdős #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 (i.e. one with common difference $\neq 0$). Prove an asymptotic formula for $r_k(N)$: exhibit an explicit function $F_k(N)$ and prove $r_k(N)=(1+o(1))F_k(N)$ as $N\to\infty$. A more modest form of the problem, asked by Erdős in [Er80] and [Va99], is to determine the order of magnitude of $r_k(N)$.
Acceptance. FULLY RESOLVES: a proof — machine-checkable (Lean/Coq) preferred, else a complete written proof — of an asymptotic formula $r_k(N)=(1+o(1))F_k(N)$ with explicit $F_k$, for every fixed $k\geq 3$; a proof for a single fixed $k$ (e.g. $k=3$) fully resolves that case and should be scoped as such. ADVANCES (each with complete proof unless stated): determine the order of magnitude of $r_k(N)$ for some $k\geq 3$ (the [Er80]/[Va99] relaxation); prove $r_k(N)/r_{k+1}(N)\to 0$ for some $k\geq 3$; strictly improve any upper or lower bound stated in the background; or extend the exact-value sequences A003002–A003005 to new $N$ via exhaustive search, delivering reproducible code, the extremal sets found, and a certificate (or rigorous argument) of exhaustiveness strictly beyond the currently published terms. Deliver the proof file, or the code + extremal witnesses + exhaustiveness certificates for exact-value extensions.
Background
One of the central open problems of additive combinatorics. Erdős offered $10,000 for a solution in [Er81, p.4], calling it 'probably enormously difficult' (in [Er97c] he offered $1000, an oddly low figure given he offered $5000 elsewhere essentially for showing $r_k(N)=o_k(N/\log N)$, which is Erdős #3, erdosproblems.com/3); he also remarked it is 'probably unattackable at present'. Sources: [Er80, p.92], [Er81, p.4], [Er97c], [Va99, 1.27]; listed as open on erdosproblems.com/142 (fetched 2026-07-13, status 'open', prize $10000, tagged 'additive combinatorics | arithmetic progressions'). The best known upper bounds are due to Kelley and Meka [KeMe23] for $k=3$ (of the shape $r_3(N)\ll N\exp(-c(\log N)^{1/12})$, since slightly refined by Bloom–Sisask [BlSi23]), Green and Tao [GrTa17] for $k=4$, and Leng, Sah, and Sawhney [LSS24] for $k\geq 5$; in the other direction Behrend-type constructions give $r_3(N)\gg N\exp(-c\sqrt{\log N})$. An asymptotic formula is far out of reach even for $k=3$, and even the order of magnitude is not known for any $k$; Erdős noted [Er80] that it is not even known whether $r_k(N)/r_{k+1}(N)\to 0$ for any $k\geq 3$. Exact values for small $N$ are tabulated in OEIS: A003002 ($k=3$), A003003 ($k=4$), A003004 ($k=5$), A003005 ($k=6$). A Lean formalisation of the statement exists in google-deepmind/formal-conjectures. See also Erdős #3 and #139 (erdosproblems.com/3, erdosproblems.com/139). The attacker's tool: the headline formula is proof-shaped, but the concrete lanes are SAT/ILP exhaustive computation extending the exact-value tables A003002–A003005 with exhaustiveness certificates, and Behrend-style construction search improving lower-bound records for specific ranges.
References
| Ref | Source | Type |
|---|---|---|
| REF-01 | Erdős Problem #142 (T. F. Bloom) | website |
| REF-02 | OEIS A003002 — r3(n): 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 | Lean formalisation of Erdős Problem #142 (google-deepmind/formal-conjectures) | website |
Investigations · 0
No published investigations yet. This problem is unclaimed territory.