Skip to content

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

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.

Back to catalogue · Compendium introduction