Skip to content

Erdős Problem #139

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

For fixed \(k\ge3\), let \(r_k(N)\) be the largest possible size of a subset of \(\{1,\ldots,N\}\) containing no nontrivial \(k\) term arithmetic progression. A nontrivial progression has a nonzero common difference. Erdős and Turán asked whether

\[ r_k(N)=o(N),\quad\text{equivalently}\quad\lim_{N\to\infty}\frac{r_k(N)}N=0. \]

The limit is for each fixed \(k\), not one claim about a growing progression length.

A small example

The three integers \(1,2,3\) form a nontrivial arithmetic progression, so they cannot all belong to a set counted by \(r_3(3)\). The set \(\{1,3,4\}\) contains no nontrivial three-term progression and has size three when considered inside \(\{1,2,3,4\}\). Finite examples show the definition, not the asymptotic density limit.

What is known

PROVED. Endre Szemerédi's 1975 theorem proves that a subset of the positive integers with positive upper density contains arithmetic progressions of every prescribed finite length. Taking its contrapositive yields the stated limit. Quantitative refinements have different scopes: Kelley–Meka and subsequent work give strong bounds for \(k=3\); Green–Tao treat \(k=4\); Leng–Sah–Sawhney address \(k\ge5\). These advances must not be conflated with an exact asymptotic formula for \(r_k(N)\), which remains open in Erdős #142.

GCL's current state

Pinned and maintained #139 mark PROVED. Original source issue #1408. The frozen Formal Conjectures declaration represents the density limit and still uses a proof hole; its existence is not a GCL Lean proof of Szemerédi's theorem.

The original source assignment has an authenticated RESULT/1 report. This is unadjudicated source evidence, not a proof certificate or accepted article.

What remains

Write a finite exact solver for \(r_3(N)\), \(N\le16\). Acceptance: test every subset or provide a transparent integer-programming certificate, prohibit zero common difference, and compare computed values with independently enumerated witnesses. Do not claim that these finite values establish the density-zero theorem or the still-open problem of exact asymptotics.

Sources and claim boundaries

No novel density theorem, full independent Szemerédi proof or editorial admission is claimed.

Catalogue and evidence provenance

  • Pinned catalogue source: teorth/erdosproblems at 536408716724.
  • GCL issue: #1408 — protected issue/assignment identity; its labels and results are live, not reproduced automatically here.
  • GCL triage: OUTSIDE_STRICT_OPEN_TRIAGE.
  • Formal-statement coverage: A provider statement was included in the pinned 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