Skip to content

Erdős Problem #156

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

A maximal Sidon subset \(A\subseteq\{1,\ldots,N\}\) is one to which no further integer from the interval can be added while keeping all unordered pair sums distinct. “Maximal” means maximal under inclusion, not maximum possible cardinality.

Erdős, Sárközy and Sós asked whether, for every large \(N\), there exists such a maximal Sidon set of cardinality only

\[ O(N^{1/3}). \]

This is a problem about finding unusually small sets which nevertheless cannot be enlarged, not about how many points can fit into a largest Sidon set.

A small example

The set \(A=\{1,2,4\}\) is Sidon. It may or may not be maximal in a specified ambient interval: to decide, inspect each unchosen integer \(x\in\{1,\ldots,N\}\setminus A\), compute all pair sums of \(A\cup\{x\}\) and reject \(x\) only when a duplicate sum appears. A set that cannot be enlarged by one point is maximal, even if another Sidon set in the same interval is much larger.

Adding a candidate \(x\) creates new sums \(x+a\) for \(a\in A\) and \(2x\), so testing only pairs of old elements misses precisely the obstruction relevant to maximality.

What is known

The sharp \(O(N^{1/3})\) upper existence bound remains OPEN. Imre Z. Ruzsa constructed maximal Sidon sets with

\[ |A|\ll(N\log N)^{1/3}, \]

reported in his 1998 paper, [Ru98b]. The logarithmic factor cannot be dropped by merely absorbing it into the implied constant. The maintained Erdős #156 also records the elementary lower bound that every maximal Sidon set has cardinality \(\gg N^{1/3}\), obtained by counting the integer candidates forbidden by each short additive collision.

Thus lower and upper bounds agree in their power of \(N\), but a logarithmic gap remains. The problem is distinct from #155, which concerns largest Sidon sets of order roughly \(\sqrt N\).

GCL's current state

The pinned and current catalogue classify #156 OPEN. The source issue is #1425. Ruzsa's original construction and precise implicit constant were not independently page-audited; the historically recorded bound is cited rather than re-proved.

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

An exhaustive finite successor enumerates Sidon subsets of \([1,N]\) for \(N\le16\), retaining precisely those for which every missing candidate introduces a repeated unordered pair sum. Acceptance: verify each candidate's Sidon property and maximality separately, report the smallest maximal cardinality and a witness for every tested \(N\), and compare numerically with \(N^{1/3}\) without asserting an asymptotic improvement. Source verification should locate the exact theorem/page in Ruzsa's 1998 publication.

Sources and claim boundaries

No removal of the logarithmic factor, complete original proof audit or editorial admission is claimed.

Catalogue and evidence provenance

  • Pinned catalogue source: teorth/erdosproblems at 536408716724.
  • GCL issue: #1425 — 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.

Back to catalogue · Compendium introduction