Erdős Problem #201
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 a fixed integer \(k\ge3\), define \(G_k(N)\) as the largest guaranteed size of a subset without any nonconstant \(k\) term arithmetic progression, starting from an arbitrary \(N\) element set of integers. Separately, let \(R_k(N)\) be the largest progression-free subset of the interval \(\{1,\ldots,N\}\).
Erdős asked whether these two extremal quantities are asymptotically identical for three-term progressions:
The arbitrary ambient set in \(G_k\) may contain very widely separated integers. This is much stronger than optimizing only within an interval.
A small example
Every \(N\) element integer set contains at least one \(G_k(N)\) element progression-free subset by definition. Taking the interval itself as a test set shows \(G_k(N)\le R_k(N)\).
The maintained Erdős #201 records the exact small discrepancy \(G_3(5)=3\), \(R_3(5)=4\); the set \(\{1,2,3,4,5\}\) contains a four-element 3-progression-free subset, whereas a different five-element integer set has no such four-element subset. An additional finite inequality \(G_3(14)\le7<R_3(14)=8\) is recorded. These are finite separations, not evidence for or against a limit of one.
What is known
The asymptotic equality is OPEN. Riddell (1969) first investigated the problem. Komlós, Sulyok and Szemerédi (1975) established comparison up to a constant depending on \(k\):
Together with \(G_k(N)\le R_k(N)\), this gives the same order up to constants for fixed \(k\). It does not force their ratio toward one. Roth's and Szemerédi's theorems give separate density estimates, but asymptotically sparse progression-free subsets can still differ by a nonvanishing constant factor.
GCL's current state
Pinned status and maintained status: OPEN. Original authenticated issue #1470. Its protected triage requires a source statement capture, and the frozen provider has no #201 statement file. The original KSS75 proof is source-attributed; no independent reconstruction or updated protected statement is claimed.
The original issue contains an authenticated RESULT/1 source report. This is unadjudicated source evidence only, not independent mathematical certification or editorial admission.
What remains
A bounded successor enumerates all subsets of \([1,12]\), computes \(R_3(N)\) for \(N\le12\), and checks arbitrary five-element sets in a controlled wider interval to exhibit \(G_3(5)=3\). Acceptance: count only nonzero-difference progressions; show both inequalities \(G_k\le R_k\) and the exact five-element fixture; explicitly distinguish finite lower bounds for \(G_k\) from universal ones over all integer sets.
Sources and claim boundaries
- Erdős #201, historical Ri69 and KSS75 and small exact cases.
- GCL issue #1470, original protected source packet.
No proof of asymptotic ratio one, independent KSS proof or editorial admission is claimed.
Catalogue and evidence provenance
- Pinned catalogue source: teorth/erdosproblems at
536408716724. - GCL issue: #1470 — protected issue/assignment identity; its labels and results are live, not reproduced automatically here.
- GCL triage: STATEMENT_CAPTURE_REQUIRED.
- 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.