Erdős Problem #346
Editorial depth: Reviewed explanatory article — evidence qualified.
Snapshot classification: solved (not automatically the live result).
Subject areas: number theory, complete sequences.
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 346 concerns additive decompositions of the integers. Start with a strictly increasing set of positive integers \(A=\{a_1<a_2<\cdots\}\). Call \(A\) complete when every sufficiently large integer is a sum of distinct members of \(A\). The problem asks about a particularly fragile kind of complete set: deleting any finite subset \(B\) leaves a complete set, but deleting any infinite subset \(B\) destroys completeness. If the successive ratios satisfy \(a_{n+1}/a_n\geq 1+\epsilon\) for one fixed \(\epsilon>0\), must those ratios converge to the golden ratio
The point is not merely that \(A\) grows quickly. The two deletion conditions demand that additive representations are both abundant and delicately distributed. The proposed conclusion says that these requirements force one very specific asymptotic growth rate.
A small example
Graham’s basic finite calculation uses Fibonacci numbers with \(F_0=0\), \(F_1=1\), and \(F_{n+2}=F_{n+1}+F_n\). His paper studies the sequence \(s_n=F_n-(-1)^n\) through its subset-sum set, allowing each term at most once. Exact arithmetic gives
F = [0, 1]
for _ in range(2, 10):
F.append(F[-1] + F[-2])
s = [F[n] - (-1 if n % 2 else 1) for n in range(10)]
print(F)
print(s)
The verified output is \(F_0,\ldots,F_9=(0,1,1,2,3,5,8,13,21,34)\) and \(s_0,\ldots,s_9=(-1,2,0,3,2,6,7,14,20,35)\). Thus \(s_7/s_6=14/7=2\), \(s_8/s_7=20/14=10/7\), and \(s_7+s_8=34=F_9\). If the positive distinct prefix is \(\{2,3,6,7,14,20\}\), direct subset enumeration covers every integer from \(5\) through \(24\); in the interval \(0\) through \(24\) it misses exactly \(1\) and \(4\).
This is a reproducible finite check of the arithmetic and of the meaning of subset sums. It does not establish completeness of an infinite sequence, either deletion property, strict increase of the displayed indexed sequence, or any limiting ratio. In particular, a finite block cannot certify or refute the Erdős assertion.
What is known
The primary source is R. L. Graham, “A Property of Fibonacci Numbers,” The Fibonacci Quarterly 2 (1964), 1–10. Graham defines \(P(A)\) as the sums formed by choosing zero or one copy of each term and calls a sequence complete when all sufficiently large integers lie in \(P(A)\). His theorem proves that the sequence \(S\) with term \(F_n-(-1)^n\) has the two deletion properties: every finite subsequence deletion leaves a complete sequence, while deletion of an infinite subsequence leaves a non-complete one. The proof is on the paper’s pages 2–10 and is a genuine external proof of that Fibonacci example, not a proof of the later ratio question.
Erdős and Graham’s 1980 monograph records Problem 346 on page 57. The live problem page repeats the question and Graham’s example, and reports that a ratio strictly larger than \(\varphi\) automatically gives the non-completeness condition after infinite deletion. Its current text, last edited 1 September 2026, then says “This is false” and attributes a counterexample to GPT Pro, prompted by Liam Price: the reported sequence has ratios at least \(6/5\) and two subsequential ratio limits, \(\varphi\) and \(\varphi+1/4\). That is a current external report, not a primary published proof inspected in this audit.
GCL's current state
The original MATH-PROGRAMME issue #1616 is assignment ERDOS-CATALOGUE-0346-S01. At readback it was open, carried the direct-editorial source-audit labels, and had zero comments, hence no existing RESULT/1 to duplicate. The issue body’s verified SHA-256 is 59c9f36894478c062f3481c31cbc10bebdbcd8d39de213e61b63171593ef6e7f.
The frozen catalogue snapshot is teorth/erdosproblems commit 536408716724a2402bdfa7c1d764bf83d64a8c89, entry 346, blob 4e60263a80af6207aca494d2e1388e44fa372889; it says solved, with formal status unformalized and statement-formalized metadata yes. The current catalogue main commit 76848eddd25687dfc69bb26bec740c35c4a9c6b4, blob 97ae243a7fc056bb9c6413ce665b575eadd27ff3, retains those fields.
The pinned FormalConjectures file is at commit 85f863718beeec7b58a3a1926ee92e3472bc2020, blob 56ad21bdf05f1f39d0e441e6ed1257e43046868. Its main theorem is tagged research/open and uses an unrestricted function \(A:\mathbb N\to\mathbb N\), predicates IsLacunary and IsAddStronglyCompleteNatSeq, and a ratio limit. The theorem and all research variants except the elementary lacunarity check contain sorry. The file is therefore a formal statement and interface, not a replayed proof or certification. Its range A formulation and truncated natural subtraction in the Fibonacci variant also require semantic review against the positive strictly increasing set in the original question.
What remains
The decisive missing item is a readable, versioned proof of the reported counterexample, together with a line-by-line comparison to the original quantifiers. The Overleaf report and linked web Lean code are not primary literature, and they were not independently replayed here. A successor audit should extract the construction, prove strict positivity and increase, verify the two deletion properties for the infinite construction, and prove the ratio lower bound and subsequential limits. It should separately state whether the construction is a set or merely an indexed function, and whether finite initial anomalies are removed by an explicitly justified reindexing.
Until that evidence is available, “solved,” “false,” and “formalized” must remain labels from different evidence surfaces. Neither the finite calculation nor the Lean file settles the problem. V2 ledger status alone decides accepted compendium coverage; this article supplies documentary context, not mathematical certification.
Sources and claim boundaries
The original issue is the assignment and source packet; the original SOURCE RESULT/1 citation is authenticated original RESULT/1. The frozen catalogue entry and current catalogue snapshot provide dated metadata, not theorem authority. The readable primary paper is Graham’s 1964 PDF, downloaded here with SHA-256 fa59f6ea280108744b6d56bd73f1cdc49edd5e3a631e534928b116d12494978d; the 1980 reference is identified on the live problem page. The pinned Lean source is an auditable formal interface with sorry, not a proof readback. The live counterexample report remains unverified external evidence. No statement here grants acceptance, publication, independent review, or GCL mathematical certification.
Catalogue and evidence provenance
- Pinned catalogue source: teorth/erdosproblems at
536408716724. - GCL issue: #1616 — 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.