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
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
- Maintained Erdős #139, Szemerédi (1975) and modern quantitative references.
- Formal Conjectures 139; GCL issue #1408.
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.