Erdős Problem #142
Editorial depth: Reviewed explanatory article — evidence qualified.
Snapshot classification: open (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 maximum number of integers one can choose from \(1,\ldots,N\) without forming a nontrivial arithmetic progression of length \(k\). Erdős #142 requests an asymptotic formula for \(r_k(N)\), rather than merely proof that its density tends to zero.
A sharp asymptotic formula would identify the main growth function and sufficient error control. Even a correct order-of-magnitude estimate would be a major advance, though it is weaker than an equivalent with a precise leading constant.
A small example
To find \(r_3(5)\), list every three-term progression in \(\{1,2,3,4,5\}\), including \(1,2,3\), \(2,3,4\), \(3,4,5\), and \(1,3,5\). The set \(\{1,2,4,5\}\) contains no three-term progression, giving \(r_3(5)\ge4\). A five-element set is the entire interval and is forbidden, so \(r_3(5)=4\). This small exact value cannot determine an asymptotic formula.
What is known
OPEN, even for \(k=3\). Szemerédi's theorem establishes \(r_k(N)=o(N)\). Subsequent quantitative upper bounds, including Kelley–Meka for three-term progressions, Green–Tao for four-term progressions, and Leng–Sah–Sawhney for longer lengths, constrain its growth but do not provide the exact extremal asymptotics. Behrend-type constructions yield important lower bounds for \(k=3\). The gap remains wide. Problem #139 is a proved density theorem and must not be confused with the open asymptotic request.
GCL's current state
The maintained Erdős #142 and original issue #1411 classify the problem OPEN. The frozen Formal Conjectures 142 entry represents a requested \(\Theta\) comparison to an unspecified function rather than supplying a proved explicit formula; its proof is absent. This formulation is less precise than the plain-language request for an asymptotic equivalent, a distinction future formalization must resolve.
The original source assignment has an authenticated RESULT/1 report. This is unadjudicated source evidence, not a proof certificate or accepted article.
What remains
Compute exact values of \(r_3(N)\) through \(N=20\) using integer-programming or exhaustive search with proof certificates. Acceptance: all forbidden triples are included, witness subsets match the upper bound, and the output clearly distinguishes exact finite data, order-of-magnitude statements and asymptotic equivalence.
Sources and claim boundaries
- Erdős #142, quantitative work and historical prize statements.
- Formal Conjectures 142; GCL issue #1411.
No new asymptotic formula, independent source-proof replay or editorial admission is claimed.
Catalogue and evidence provenance
- Pinned catalogue source: teorth/erdosproblems at
536408716724. - GCL issue: #1411 — protected issue/assignment identity; its labels and results are live, not reproduced automatically here.
- GCL triage: CROSS_CAMPAIGN_SYNERGY_ONLY.
- 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.