Erdős Problem #155
Editorial depth: Reviewed explanatory article — evidence qualified.
Snapshot classification: open (not automatically the live result).
Subject areas: additive combinatorics, sidon sets.
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
Let \(F(N)\) be the largest possible cardinality of a Sidon subset of \(\{1,\ldots,N\}\): every sum \(a+b\) with \(a\le b\) drawn from the set must have a unique unordered representation. Erdős asked whether, for every fixed integer \(k\ge1\), there is a threshold after which enlarging the permitted interval by \(k\) increases its maximum Sidon-set size by at most one:
The threshold is allowed to depend on \(k\); one cannot reverse the order of these quantifiers. The suggested strengthening allows \(k\) to grow like a small multiple of \(\sqrt N\).
A small example
For a Sidon set in \([1,N+k]\), deleting all elements larger than \(N\) leaves a Sidon subset of \([1,N]\). Hence the elementary universal inequality is only
For \(k=1\) the desired inequality already follows from this argument. The challenge is that it predicts the same increase of one for each larger fixed \(k\), no matter how many new positions become available.
A Sidon set of three elements such as \(\{1,2,4\}\) has six distinct unordered sums \(2,3,4,5,6,8\). This is the correct convention: counting only sums of different elements would change the extremal function.
What is known
The general fixed-window conjecture remains OPEN. Classical Erdős–Turán estimates and later finite-field constructions give the leading order \(F(N)\sim\sqrt N\), but this asymptotic estimate does not control bounded changes in \(F\). An error of order \(N^{1/4}\) in a global extremal estimate is much larger than one. The maintained Erdős #155 identifies the proposed strengthening for \(k\approx\varepsilon\sqrt N\) separately from the fixed-window question.
The original question appears in Erdős's [Er92c], [Er94b] and the Erdős–Sárközy–Sós [ESS94] collection. No verified source currently supplies an eventual eventual proof for any fixed \(k\ge2\).
GCL's current state
The pinned and maintained catalogue label #155 OPEN, and its original issue is #1424. The elementary one-step monotonicity argument is self-contained; the general conjecture and the growing-window variant are not certified.
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 task exactly enumerates \(F(N)\) for \(N\le24\) by searching Sidon subsets and testing all unordered sums, then checks the inequality for \(k=1,2,3\) on every finite pair within this range. Acceptance: produce maximizing witnesses and independent pair-sum verification, and explicitly distinguish a finite violation from asymptotic falsification. Stop without extrapolating finite cases into an eventual theorem.
Sources and claim boundaries
- Erdős #155, source leads [Er92c], [ESS94], [Er94b] and fixed-parameter quantifier.
- Original GCL issue #1424.
No new extremal Sidon bound or final editorial admission is claimed.
Catalogue and evidence provenance
- Pinned catalogue source: teorth/erdosproblems at
536408716724. - GCL issue: #1424 — protected issue/assignment identity; its labels and results are live, not reproduced automatically here.
- GCL triage: PROTECTED_READY_BACKLOG.
- 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.