Erdős Problem #140
Editorial depth: Reviewed explanatory article — evidence qualified.
Snapshot classification: proved (not automatically the live result).
Subject areas: additive combinatorics, arithmetic progressions.
Read this status correctly
The status above is reproduced from GCL's immutable external-catalogue snapshot. It is not a new claim of current mathematical resolution, a source-semantic review, an independent proof check, or GCL certification. A published proof and a GCL replay are separate events.
The question in plain language
Let \(r_3(N)\) be the maximum size of a set of integers from \(1\) through \(N\) with no three distinct numbers in arithmetic progression. Erdős #140 asks for every fixed \(C>0\) an upper bound
The constant may depend on \(C\), but the exponent must be arbitrarily large and fixed before \(N\to\infty\). Merely proving \(r_3(N)=o(N)\) does not suffice.
A small example
If \(a,b,c\) are distinct and \(a+c=2b\), they form a nontrivial three-term progression. For example \(2,5,8\) is forbidden. A finite optimizer can encode one linear forbidden triple for each integer pair \(a<c\) with even \(a+c\), allowing at most two selected vertices from that triple.
What is known
PROVED. Kelley and Meka's Strong Bounds for 3-Progressions proves a density bound of the form \(r_3(N)/N\le\exp(-c(\log N)^\beta)\) for absolute \(c,\beta>0\). Since \((\log N)^\beta\) grows faster than \(\log\log N\), this exponential factor is eventually smaller than \((\log N)^{-C}\) for every fixed \(C>0\). A 2023 exposition by Bloom and Sisask simplifies portions of the proof. The corresponding conjectures for longer progressions must be checked separately; this theorem is specifically for \(k=3\).
GCL's current state
Pinned and maintained #140 classify the problem PROVED. Original source issue #1409. There is no admitted frozen Formal Conjectures statement file for #140. The primary Kelley–Meka abstract supports the result, but the complete analytic proof has not been independently reconstructed in this tranche.
The original source assignment has an authenticated RESULT/1 report. This is unadjudicated source evidence, not a proof certificate or accepted article.
What remains
Prove the elementary consequence from an assumed \(\exp(-c(\log N)^\beta)\) bound to \((\log N)^{-C}\), with quantified constants and every fixed \(C\). Acceptance: compare logarithms rigorously and keep \(k=3\) fixed. A separate source-proof replay would need to audit Bohr-set and additive-energy estimates from the 2023 paper.
Sources and claim boundaries
- Kelley and Meka, arXiv:2302.05537, primary theorem; Bloom and Sisask exposition.
- Erdős #140; GCL issue #1409.
No new progression-free bound, formal proof certification or editorial admission is claimed.
Catalogue and evidence provenance
- Pinned catalogue source: teorth/erdosproblems at
536408716724. - GCL issue: #1409 — protected issue/assignment identity; its labels and results are live, not reproduced automatically here.
- GCL triage: OUTSIDE_STRICT_OPEN_TRIAGE.
- Formal-statement coverage: No statement was confirmed in GCL's pinned formal-provider snapshot. Presence does not mean the statement or proof has been checked.
- External mathematical status: consult current problem page and its dated bibliography.