Erdős Problem #39
Editorial depth: Reviewed explanatory article — evidence qualified.
Snapshot classification: open (not automatically the live result).
Subject areas: number theory, sidon sets, additive combinatorics.
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
A Sidon set has unique unordered sums of two elements, counting repeated summands as legitimate pairs. Finite Sidon subsets of \(\{1,\ldots,N\}\) can have about \(\sqrt N\) elements, but making one infinite Sidon set with that density scale is more delicate. Erdős Problem #39 asks whether some infinite Sidon set \(A\) satisfies, for every \(\varepsilon>0\), a lower growth estimate proportional to \(N^{1/2-\varepsilon}\) for its counting function at sufficiently large cutoffs.
The quantifiers refer to one fixed infinite set, not a separate optimal finite set chosen for each \(N\).
A small example
The set \(\{1,2,3\}\) fails the strong Sidon condition because
The repeated 2 on the right is allowed and creates a genuine collision. In contrast \(\{1,2,4,8\}\) has no repeated unordered pair sum.
For a finite Sidon set of size \(k\) inside \([1,N]\), all \(k(k-1)/2\) positive differences of distinct pairs are different and lie in \([1,N-1]\). Thus
This is a necessary finite constraint, not a construction of a dense infinite Sidon set.
What is known
The maintained problem record reports the infinite density question as OPEN and attributes partial constructions to Ruzsa and other additive-number-theory work. The source audit has not independently rechecked the exact leading exponent in all those primary papers, so no more precise published construction rate is asserted here.
GCL's current state
Audit #1308 establishes the positive-difference injection lemma and highlights the necessity of checking that the frozen finite Sidon predicate includes repeated summands. The source file's research theorem is unfilled; finite examples are not a global solution.
What remains
Produce one infinite Sidon set with the proposed near-square-root growth at all sufficiently large cutoffs, or establish that none can attain it. Finite difference-counting bounds do not supply the required compatible infinite construction.
Sources and claim boundaries
- Erdős Problems #39: open conjecture and historical bibliography.
- GCL source audit #1308: exact finite proof and semantics boundary, not mathematical certification.
Catalogue and evidence provenance
- Pinned catalogue source: teorth/erdosproblems at
536408716724. - GCL issue: #1308 — 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.