Erdős Problem #342
Editorial depth: Reviewed explanatory article — evidence qualified.
Snapshot classification: open (not automatically the live result).
Subject areas: number theory.
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
Erdős Problem 342 concerns the classical \((1,2)\) Ulam sequence. Start with \(a_1=1\) and \(a_2=2\). Once the first \(n\) terms are known, choose \(a_{n+1}\) to be the smallest integer larger than \(a_n\) that has exactly one representation as \(a_i+a_j\) with \(i<j\leq n\). “Exactly one” counts unordered pairs of distinct earlier terms: the same summands in the opposite order do not count as a second representation.
The page asks four related questions. Do infinitely many pairs of terms differ by \(2\)? Do the successive differences \(a_{n+1}-a_n\) eventually repeat periodically? Does the sequence have density zero among the positive integers? More generally, what can be said about its global structure? The last question is broad; the first three are concrete targets.
This is a greedy definition, but its long-term behaviour is not controlled by the first few terms. A finite computation can show exactly what the rule does for a specified range. It cannot by itself settle an assertion about infinitely many pairs, eventual periodicity, or an asymptotic density.
A small example
The first four terms are \(1,2,3,4\). At the next stage, the unordered sums from these four terms include \(1+4=5\) and \(2+3=5\), so \(5\) is not unique. The value \(6\) has the single representation \(2+4\) among distinct earlier terms: the other pairs give \(3,4,5,5,\) and \(7\). Therefore the rule selects \(a_5=6\).
Continuing the same exact integer test gives the reproducible prefix
For an additional check, at the stage with earlier terms \(1,2,3,4,6\), the value \(8\) has the unique distinct-pair representation \(2+6\); candidates between the previous selected value \(6\) and \(8\) do not pass the uniqueness test. An exact-arithmetic enumeration that counts every pair \(i<j\) produces these values and verifies the uniqueness/minimality conditions term by term. This confirms a finite prefix only. It does not estimate a limiting density and does not provide evidence strong enough to infer periodicity.
What is known
The maintained Erdős Problems entry gives the definition, the same initial values, and the four questions. It currently labels the problem open. It cites Guy’s Unsolved Problems in Number Theory as problem C4 and identifies the source location as page 53 of the cited collection.
Ben Green’s 100 Open Problems gives a closely related formulation as Problem 7 on PDF page 4 (printed page 5). Green asks whether Ulam’s sequence has positive density and whether its unusual Fourier behaviour can be explained. The comments distinguish the density question from computational observations about a frequency near \(2.5714474995\). Green presents these as open questions and points to earlier computations; this is not an external proof of any answer to Problem 342.
The primary paper “A Hidden Signal in the Ulam sequence” reports numerical evidence for that Fourier phenomenon, including a computation on a large finite prefix. Its abstract and introduction explicitly describe the observation as empirical. It is useful evidence about the Fourier subquestion, but it does not establish the density, infinitely-many-pairs, or eventual-periodicity claims. No primary source read in this audit supplies a theorem resolving those claims.
GCL's current state
The source packet fixes the catalogue at teorth/erdosproblems commit 536408716724a2402bdfa7c1d764bf83d64a8c89, entry number: "342", whose data record says informal status open, formal-solution status unformalized, and statement-formalized metadata yes. The entry’s status date is 2025-08-31; its formalized metadata carries a later date, 2026-03-17. That metadata distinction is not a proof-status change.
The pinned FormalConjectures file defines IsUlamSequence with zero-based Lean indices and formalizes parts (i), (ii), and (iii). The definitions correctly encode distinct earlier indices, uniqueness, strict increase, and minimality. The file contains proved small tests for the initial terms, but the three research statements are written as equivalences involving answer(sorry) and end with by sorry. Thus statement formalization is present; a checked proof is not.
The zero-based convention is semantically equivalent to the one-based presentation after shifting indices, but that equivalence has not been certified by GCL here. The supplied file blob token is recorded as eef32745fc22bf23e8b2d960c17967d10c253a; it is unusually 38 characters, so this article preserves it as packet metadata rather than silently correcting it. The exact commit and readable file are the stronger locator.
What remains
The smallest useful successor is a pinned finite certificate: take the exact external recurrence and the pinned IsUlamSequence definition as inputs, generate a specified prefix such as the first 10,000 terms, and record for every selected term its unique pair and the rejection of every smaller candidate. The certificate should also state the one-based/zero-based index translation and carry a content hash. Acceptance means an independent rerun reproduces every term and every uniqueness/minimality check; the first mismatch is a falsification. Stop after the bound is certified or at the first mismatch.
This task would test semantic alignment and provide auditable finite evidence without pretending to settle an asymptotic question. Any later work on density, pair gaps, periodic differences, or Fourier structure needs a separate mathematical argument and source review.
Sources and claim boundaries
This article is tied to original issue #1612, assignment ERDOS-CATALOGUE-0342-S01. The frozen catalogue commit is 536408716724a2402bdfa7c1d764bf83d64a8c89 with blob 4e60263a80af6207aca494d2e1388e44fa372889. The frozen FormalConjectures commit is 85f863718beeec7b58a3a1926ee92e3472bc2020 with the packet-supplied file token noted above. The live page was read separately on 2026-10-12 and has no repository commit hash.
The Green document and Steinerberger paper are primary source documents for the stated questions and reported finite observations, not GCL certifications. The formal Lean file is a theorem interface containing sorry, not a replayed proof. The finite prefix is an exact calculation, not an asymptotic result. No claim here assigns a solution, award, publication status, or accepted coverage. V2 ledger 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: #1612 — 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.