Erdős Problem #158
Editorial depth: Reviewed explanatory article — evidence qualified.
Snapshot classification: open (not automatically the live result).
Subject areas: 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 \(A\) be an infinite subset of the positive integers. Suppose every integer \(n\) has at most two representations as a sum \(n=a+b\) with \(a,b\in A\) and \(a\le b\). Such a set is usually called a \(B_2[2]\) set, generalizing Sidon sets, for which each integer has at most one representation.
Erdős, Sárközy and Sós asked whether every such \(A\) must have unusually sparse initial intervals along an unbounded sequence of cutoffs:
This is a liminf, not a full limit: it only demands arbitrarily large sparse cutoffs. The constant two bounds unordered representations including diagonals.
A small example
The infinite condition is essential: every finite set has the displayed liminf equal to zero because its numerator eventually stays constant. On a finite prefix, construct a representation histogram by enumerating all pairs \(a\le b\) and counting their sums. A candidate passes the \(B_2[2]\) test if no histogram count exceeds two.
The set \(\{1,2,4\}\) is already a Sidon set and hence a \(B_2[2]\) example. However, extending this finite set without ever creating a third representation is the actual challenge.
What is known
The \(B_2[2]\) problem remains OPEN. For strict Sidon sets (\(B_2[1]\)), Erdős proved the corresponding liminf-zero theorem. Replacing one allowed representation by two changes the problem substantially: a finite example or a statement about average density is insufficient.
Javier Cilleruelo, Sidon basis, constructs an infinite \(B_2[2]\) set that is also an asymptotic basis of order three. This does not settle the question here; an additive basis property alone gives no precise lower bound on \(|A\cap[1,N]|/\sqrt N\) along every sufficiently large cutoff. The later genuine Sidon basis of order three constructed by Pilatte (#157) likewise does not answer the \(B_2[2]\) liminf question.
GCL's current state
The pinned and maintained Erdős #158 classify the question OPEN. Original GCL issue: #1427. The older \(B_2[1]\) theorem and Cilleruelo construction are source-attributed; neither is presented as resolving the \(B_2[2]\) statement.
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 enumerates exact representation histograms for finite subsets of \([1,18]\) and classifies \(B_2[1]\) versus \(B_2[2]\). Acceptance: include diagonal sums, verify at most two unordered representations for each integer, and exhibit an explicit finite set that is \(B_2[2]\) but not Sidon. Record maximal prefix cardinalities only as finite evidence. Stop before claiming anything about all infinite \(B_2[2]\) sets.
Sources and claim boundaries
- Erdős #158, original Erdős–Sárközy–Sós 1994 formulation.
- Cilleruelo, Sidon basis, arXiv:1304.5351, related construction with different conclusion.
- Original GCL issue #1427.
No density-limit theorem, independent original proof audit or editorial admission is claimed.
Catalogue and evidence provenance
- Pinned catalogue source: teorth/erdosproblems at
536408716724. - GCL issue: #1427 — 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.