Skip to content

Erdős Problem #340

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

Start with \(1\). Having chosen a finite set of integers, append the smallest larger integer that keeps all sums \(a+b\), with \(a\leq b\), different. The resulting infinite sequence is the greedy Sidon sequence, also called the Mian–Chowla sequence:

\[ 1,2,4,8,13,21,31,45,66,81,97,\ldots \]

Problem 340 asks how quickly this particular sequence accumulates. If \(A(N)\) denotes the number of its terms at most \(N\), the principal question is whether, for every fixed positive \(\varepsilon\), there is a constant depending on \(\varepsilon\) such that \(A(N)\) is at least that constant times \(N^{1/2-\varepsilon}\) for all sufficiently large \(N\). The wording “what is the order of growth?” is broader than this displayed lower-bound question: it invites a matching description, not merely one inequality.

This is a question about one deterministic sequence, not about the largest possible Sidon subset of \(\{1,\ldots,N\}\). A Sidon set has no repeated pair sums, including diagonal sums such as \(2a\). That convention matters when translating between the sequence definition, counting functions, and formal statements.

The original task is recorded in MATH-PROGRAMME issue #1610. The issue’s requested source-result citation remains authenticated original RESULT/1; no result comment existed during this audit.

A small example

Take the first five terms \(A_5=\{1,2,4,8,13\}\). The unordered sums with repetition allowed are

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

They are fifteen distinct integers, exactly the number of pairs \(a\leq b\) from five elements, so the finite set is Sidon. To test the greedy next term, exact integer enumeration gives the following first collision for each candidate: \(14\) gives \(1+14=2+13\), \(15\) gives \(2+15=4+13\), \(16\) gives \(1+16=4+13\), \(17\) gives \(4+17=8+13\), \(18\) gives \(8+18=13+13\), \(19\) gives \(2+19=8+13\), and \(20\) gives \(1+20=8+13\). Candidate \(21\) produces no repeated sum, so the next term is \(21\).

This is a reproducible finite check over integers, not a numerical approximation. It verifies the construction through the fifth step and illustrates why the greedy rule is local but not obviously amenable to a simple recurrence. It does not prove any eventual estimate for \(A(N)\), nor does it decide the problem’s quantifier over every \(\varepsilon>0\).

What is known

The primary historical reference for the initial computation is A. M. Mian and S. Chowla, “On the \(B_2\) sequences of Sidon,” Proceedings of the National Academy of Sciences of India, Section A 14 (1944), pages 3–4, bibliographic record MR0014114. The first terms are independently transcribed in Kevin O’Bryant’s annotated bibliography of Sidon-sequence work, page 3 of the PDF. Those sources support the name, definition, and initial terms; they are not evidence of a solution to the modern asymptotic formulation.

The same bibliography reports Alfred Stöhr’s treatment in “Gelöste und ungelöste Fragen über Basen der natürlichen Zahlenreihe,” Journal für die reine und angewandte Mathematik 194 (1955), 111–140, especially the Sidon discussion on pages 129–135 (primary journal record). For the greedy sequence it records the upper estimate that the term at index \(k\) is less than \((k-1)^3+1\). In counting-function language this yields the familiar cubic-root-scale lower bound, up to the usual indexing and constant translation. It is far weaker than the target exponent \(1/2-\varepsilon\).

The frozen catalogue packet classifies Problem 340 as open, with informal status last updated 2025-08-31, and records statement formalization but no formal solution. The live page erdosproblems.com/340 returned HTTP 403 during this audit, so no newer live status is asserted here. Coverage and acceptance remain status-neutral and are determined by the applicable V2 ledger rather than by this article.

GCL's current state

The frozen catalogue source is teorth/erdosproblems data/problems.yaml, commit 536408716724a2402bdfa7c1d764bf83d64a8c89, Git blob 4e60263a80af6207aca494d2e1388e44fa372889. Its entry has tags number theory, additive combinatorics, and Sidon sets; it says open, not a prize problem, and lists OEIS identifiers A080200 and A005282. Those metadata are useful locators, not proof or acceptance.

The pinned formal source is FormalConjectures/ErdosProblems/340.lean, commit 85f863718beeec7b58a3a1926ee92e3472bc2020, Git blob 10e7814eec26f668c9c1f41ebded40ac6de0f4f1 (content SHA-256 533c2a0d124ee90ac506010e55ecab270213fda98d6694da58e8fb38b3c26fb5). Its main theorem quantifies over real \(\varepsilon>0\) and expresses the target as an eventual Big-O lower comparison between \(\sqrt N/N^\varepsilon\) and the count of greedySidon values in \([1,N]\). The theorem proof is sorry, so the file is a formal statement, not a checked proof.

The same file includes greedySidon finite tests through index ten, a sorry-backed cubic-root variant, and separate sorry-backed difference-set questions. The solved 22 membership lemma is a finite witness only. It must not be conflated with the principal growth problem.

What remains

The smallest useful successor is a source-locked statement audit followed by a bounded exact computation. First, fix one definition of \(A(N)\), one indexing convention, and the equivalence between “all pairwise sums with \(i\leq j\) are distinct” and the formal IsSidon predicate. Then generate a machine-readable prefix through a declared bound \(N_0\), checking every pair sum exactly and recording the first rejected candidate at each step. Acceptance should require a replayable certificate: the prefix, its pair-sum collision table, and a proof or independently checkable script that each selected term is the least admissible integer.

This can validate the implementation and expose indexing errors, but it cannot establish an asymptotic exponent. A separate mathematical task would need a proved upper bound on the greedy terms strong enough to imply the desired counting lower bound, or a counterexample sequence of certified prefixes plus a theorem showing that the proposed asymptotic assertion fails. Stopping is reached when the source normalization is settled and the bounded certificate either replays exactly or produces a concrete discrepancy; unresolved asymptotic theory should then be handed to mathematical review rather than inferred from data.

Sources and claim boundaries

The primary historical citations are Mian–Chowla (1944) for the initial greedy sequence and Stöhr (1955) for the cited cubic-scale estimate. O’Bryant’s bibliography is a secondary map to those sources; its page references are reported as such. The exact formal interface is the pinned Lean file above, with theorem bodies containing sorry; no Lean build or mathematical certification was performed. The exact finite example in this article was checked by direct integer enumeration during the audit, and proves only that finite prefix calculation.

The original issue is the GCL source-audit record; its original SOURCE RESULT/1 citation is authenticated original RESULT/1. The live catalogue page was unavailable, and no claim is made about later revisions beyond the pinned packet. This article therefore distinguishes historical statements, formal declarations, finite checks, and open claims. It does not declare acceptance, publication, solution, novelty, or GCL mathematical certification.

Catalogue and evidence provenance

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