Skip to content

Erdős Problem #329

Editorial depth: Reviewed explanatory article — evidence qualified.
Snapshot classification: open (not automatically the live result).
Subject areas: number theory, 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

Take a set \(A\) of positive integers with the Sidon property: no two different unordered pairs of elements have the same sum. Let \(A(N)\) count the elements of \(A\) from \(1\) through \(N\). Erdős Problem 329 asks for the largest possible eventual upper size of \(A(N)\) when measured on the square-root scale, namely \(\limsup_{N\to\infty} A(N)/\sqrt{N}\). The normalization matters. A Sidon set cannot have ordinary positive density, but it can repeatedly come close to a constant multiple of \(\sqrt N\).

The obvious candidate ceiling is \(1\). Erdős and Turán proved the corresponding finite estimate, while the exact question is whether some infinite Sidon set reaches that ceiling along an unbounded sequence of cutoffs. The problem is therefore an extremal question about all infinite sets, not a request to find one especially good finite set.

A small example

The finite set \(A=\{1,2,4,8,13\}\) is a useful check on the vocabulary. Enumerating unordered pairs with repetition gives

(1,1),(1,2),(1,4),(1,8),(1,13),(2,2),(2,4),(2,8),(2,13),
(4,4),(4,8),(4,13),(8,8),(8,13),(13,13)

and their sums are

2,3,5,9,14,4,6,10,15,8,12,17,16,21,26.

An exact-arithmetic enumeration returned sum_count = 15 and unique_sum_count = 15; the ten positive differences between distinct elements were also all distinct. Thus this is a verified finite Sidon example. At \(N=13\) its partial numerator is \(5\), so its displayed finite ratio is \(5/\sqrt{13}\). This calculation does not show that the set extends to a perfect difference set, nor does it say anything by itself about an infinite limsup. In particular, finite Sidon-ness and the asymptotic extremal problem must not be conflated.

What is known

The primary source read for this audit is P. Erdős and P. Turán, “On a Problem of Sidon in Additive Number Theory, and on some Related Problems,” Journal of the London Mathematical Society 16 (1941), pages 212–215. Its introduction states the square-root scale and the elementary difference-counting ceiling; Section II proves, for the largest size of a Sidon sequence below \(n\), an estimate of the form \(\sqrt n+O(n^{1/4})\). This gives the normalized upper bound \(1\) in the corresponding limsup formulation. The paper also records a construction with positive square-root-scale density and explains that existence of an exact limiting constant was not proved there.

The maintained Erdős Problems page reports the later milestones: Erdős obtained \(1/2\), and Krückeberg reported \(1/\sqrt 2\). The page says that Erdős and Krückeberg conjectured that \(1\) is possible. The Krückeberg bibliographic record is identified as F. Krückeberg, “B2-Folgen und verwandte Zahlenfolgen,” J. Reine Angew. Math. 1961, no. 206, 53–60. The catalogue and page agree that the main question remains open. The full Krückeberg paper was not independently read in this bounded audit, so its exact construction and hypotheses remain a reported external result here, not a new verification.

A related extension route has changed status. Alexeev and Mixon’s 2025 primary preprint reports that the finite Sidon set \(\{1,2,4,8,13\}\) does not extend to any finite perfect difference set, and discusses Hall’s earlier counterexample. That result blocks the implication “every finite Sidon set extends” as a general strategy for proving the density \(1\) conjecture. It does not settle Problem 329 itself: the density question concerns infinite integer sets and their limsup, whereas the extension statement concerns finite modular difference sets.

GCL's current state

The frozen catalogue source is teorth/erdosproblems commit 536408716724a2402bdfa7c1d764bf83d64a8c89, with data/problems.yaml blob 4e60263a80af6207aca494d2e1388e44fa372889. Its #329 record says informal status open, formal status unformalized, and statement formalized yes, with last update 2025-08-31. The live repository file has blob 97ae243a7fc056bb9c6413ce665b575eadd27ff3; its #329 entry is unchanged, so this audit found source drift in the file hash but not in the record.

The pinned formal source is google-deepmind/formal-conjectures commit 85f863718beeec7b58a3a1926ee92e3472bc2020, file FormalConjectures/ErdosProblems/329.lean, blob b03c4b6b71c50b3c30354f6f8ff29e5f1b52fad1. It defines the finite count on Set ℕ, takes a limsup at atTop, and states the main supremum with answer(sorry). The lower-bound, Krückeberg, and Erdős–Turán variants are also theorem-shaped declarations whose bodies are by sorry; their category labels are metadata, not replayed proofs. The imported IsSidon convention should still receive semantic review against the paper’s positive, strictly increasing B2 sequence convention before formal coverage is treated as equivalent. No Lean replay or GCL mathematical certification is supplied here.

What remains

The smallest useful successor is a source-normalization and finite-interface task. Its input should be the pinned formal file, the 1941 paper, and the maintained page’s exact references. Its target should be a checked equivalence table: set-versus-sequence convention, whether diagonal sums are included, the interval convention \(\{1,\ldots,N\}\), the meaning of limsup, and the exact finite estimate that implies the upper bound. A second bounded output should be a reproducible certificate for a chosen finite Sidon set, plus a separate citation-level summary of the Krückeberg lower bound and the Alexeev–Mixon extension counterexample.

Acceptance requires every quantified clause to be source-backed, every cited theorem to have a page or section location, and every formal claim to be marked either proved in the cited paper, reported but not independently checked, or formalized only by sorry. Falsification is any mismatch in the ambient domain, diagonal convention, normalization, or status date. Stop when the table and certificate are complete or when the primary Krückeberg text or the imported Sidon definition remains inaccessible; do not infer beyond that boundary.

Sources and claim boundaries

The assignment and source packet are original issue #1599. The maintained entry is Erdős Problems #329, accessed 2026-10-12; it reports last edit 2026-04-06. The primary 1941 paper is available from Wiley. The related 2025 source is Alexeev and Mixon, arXiv:2510.19804, and the formal file is pinned at its stated commit.

This article is a bounded source audit and explanatory article, not a proof, certification, publication decision, or accepted-coverage determination. V2 ledger state alone decides accepted coverage. The original SOURCE RESULT/1 citation is authenticated original RESULT/1.

Catalogue and evidence provenance

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