Skip to content

Erdős Problem #152

Editorial depth: Reviewed explanatory article — evidence qualified.
Snapshot classification: proved (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 finite set \(A\) of natural numbers is a Sidon set if each sum \(a+b\) with \(a,b\in A\) and \(a\le b\) identifies the unordered pair uniquely. Form the sumset \(S=A+A\) and call \(s\in S\) isolated when neither \(s-1\) nor \(s+1\) belongs to \(S\).

Erdős, Sárközy and Sós asked whether, for every fixed positive integer \(M\), every sufficiently large finite Sidon set has at least \(M\) isolated elements in \(A+A\). The stronger conjecture asks whether the number of isolated sums is bounded below by a constant times \(|A|^2\).

A small example

The set \(A=\{1,2,4\}\) is Sidon: its unordered sums (allowing equal terms) are exactly \(2,3,4,5,6,8\), all distinct. Among these, \(8\) is isolated because neither \(7\) nor \(9\) is a sum; the other five sums have a neighbouring element of the sumset. Thus this example has one isolated sum.

An isolated element is counted once, not once for each representation as \(a+b\). For a Sidon set, sums with \(a\ne b\) have a unique unordered representation, but \(a+a\) is still part of \(A+A\). Omitting diagonal sums would produce the wrong isolation test.

What is known

PROVED, including a quadratic lower bound. A Google DeepMind prover agent produced an external formal proof of the original assertion and a stronger numerical inequality. As recorded in the maintained Erdős #152 discussion and upstream Formal Conjectures entry, if \(I(A+A)\) is the number of isolated sums and \(n=|A|\), then

\[ 16I(A+A)+100n+16\ge n^2, \]

so for large \(n\), \(I(A+A)\gg n^2\). This explicitly implies the original question for arbitrarily large fixed \(M\) by taking \(n\) sufficiently large.

The source records two exact third-party formal proof revisions: the original positive-growth proof and the stronger quadratic variant. GCL has not independently executed those exact Lean toolchains or audited their complete axiom dependencies. A related extension to truncations of infinite Sidon sets is a separate assertion requiring its own hypotheses.

GCL's current state

The pinned and maintained catalogue classify #152 as PROVED. The original issue is #1421. The public primary proof pointer and exact constant-bearing inequality were checked, but proof status is externally reported, not protected GCL formal admission.

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 all Sidon subsets of \(\{1,\ldots,12\}\), forms \(A+A\) including diagonal terms, and counts isolated values exactly. Acceptance: the example \(\{1,2,4\}\) yields one isolated sum, every unordered sum is unique, and the inequality above is tested as a finite consistency condition without treating numerical tests as its proof. Formal source review should replay the precise second external Lean snapshot with axiom and theorem matching.

Sources and claim boundaries

No new Sidon theorem, independent Lean kernel proof, or protected editorial admission is claimed.

Catalogue and evidence provenance

  • Pinned catalogue source: teorth/erdosproblems at 536408716724.
  • GCL issue: #1421 — protected issue/assignment identity; its labels and results are live, not reproduced automatically here.
  • GCL triage: OUTSIDE_STRICT_OPEN_TRIAGE.
  • 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