Skip to content

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

\[ r_3(N)=O_C\!\left(\frac{N}{(\log N)^C}\right). \]

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

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.

Back to catalogue · Compendium introduction