The board / additive combinatorics / #142
Erdős Problem #142
OPENdatabase updated 2025-08-31
No proof or disproof is known, and it isn't known whether a finite computation could settle it.
What the community database records, not our verdict. erdosproblems.com no longer shows statuses (why).
Prove an asymptotic formula for \(r_k(N)\), the largest possible size of a subset of \(\{1, \dots, N\}\) that does not contain any non-trivial \(k\)-term arithmetic progression. That is, find \(f_k\) with \(r_k(N) / f_k(N) \to 1\) as \(N \to \infty\).
Statement as formalized in Formal Conjectures (Google DeepMind, Apache-2.0) · their label: research open · 3 further variants / known partial results in the Lean file. The authoritative wording is on erdosproblems.com/142.Newer public claim (6 Oct 2026): OpenAI's internal-model release claims, for this problem, new upper bounds on r_k(N) for every k (the asymptotic formula itself stays open) — family 159 at github.com/openai/math, partly Lean-formalized. Bloom calls these claims, not endorsements; anything on this page that says the question is open was written before that release and has not re-checked it.
Prize$10,000
Statement in LeanFormal Conjectures
Solution in Leanno
Original pageerdosproblems.com/142
Attempts
submit one →Read our full write-up →
Erdős's largest bounty ($10,000): an actual asymptotic formula for r_k(N), the size of the largest subset of {1,...,N} with no non-trivial k-term arithmetic progression. "Probably unattackable," Erdős said — and it still is. We sent two frontier models after it independently, expecting no proof, and got no proof — but both surfaced and verified two genuine 2024–2026 breakthroughs most casual summaries (including our own brief) had gotten stale, plus a precise account of exactly why "formula" is a different kind of hard than "bounds."
NO PROOF TODAY