Erdős Problem #347
Editorial depth: Reviewed explanatory article — evidence qualified.
Snapshot classification: proved (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 #347 asks whether one can build an increasing sequence of positive integers whose successive ratios approach \(2\), while its finite subset sums cover almost every natural number, even after deleting finitely many terms. If \(A\) is the sequence and \(A'\) is any cofinite subsequence, the relevant set is
“Density \(1\)” means that the proportion of integers up to \(X\) which belong to \(P(A')\) tends to \(1\) as \(X\) grows. It does not mean that every sufficiently large integer is represented. The question therefore asks for a sequence that is close to doubling, but whose subset sums still have only a vanishing proportion of gaps after any finite deletion.
The maintained Erdős Problems entry records the exact displayed question, tags it as number theory and complete sequences, and currently says that the answer is affirmative. Its wording uses a nondecreasing sequence of integers; the explicit construction discussed below is positive and strictly increasing.
A small example
The construction in the primary source starts with \(M_0=10\) and
Its first block is
The next scale is
For the greedy argument, the associated digit set is
It has \(63\) elements. Exact integer enumeration checked every \(x\) from \(0\) through \(625\): choosing the largest member \(b\) of \(B_0\) with \(b\leq x\) always leaves \(0\leq x-b\leq10\). The check therefore verifies the first finite instance of the local covering lemma used by the construction. For example, \(x=625\) uses \(b=621\) and leaves \(4\); just below the first shifted digit, \(x=320\) uses \(b=310\) and leaves \(10\).
This calculation does not establish density \(1\), the limiting ratio, or the statement for every cofinite subsequence. It is only a transparent finite check of one exact-arithmetic component of the proof.
What is known
The original reference attached to the live entry is P. Erdős and R. Graham, Old and new problems and results in combinatorial number theory (1980), cited there as [ErGr80]. It is the source of the problem statement, not a proof of the later affirmative result. A related primary paper is S. A. Burr and P. Erdős, “Completeness properties of perturbed sequences,” Journal of Number Theory 13 (1981), 446–455, doi:10.1016/0022-314X(81)90036-6. That paper studies subset-sum completeness and strong completeness; it is useful context, but it should not be cited as independently proving this exact ratio-limit problem.
The decisive source located for this audit is Enrique Barschkis, “A Sequence with Doubling Ratio and Full-Density Subset Sums,” dated January 21, 2026. The author’s LaTeX source has blob 3a00fe38a57bf4bab34127b5cf4e1965ce4a8893 and SHA-256 bf930dce2008febe10a424f96e1e7f21ef70c33567b997276d51fa4d7bae5cbc; the accompanying PDF has Git blob 833d3dfb1c06f91169d7a8c1a019480c4506e0d1 and the retrieved file’s SHA-256 is a5c563a0eeaa248bd15d678cc194d48765043d3177b7b658176e350ae005ea99.
The proof concatenates blocks containing powers of \(2\) times \(M_n\), plus one adjusted final term. The block length grows slowly, while \(M_{n+1}\) is approximately \((2^{k_n}-3/2)M_n\). Within and between blocks, the ratio tends to \(2\). A greedy expansion chooses one digit from each block, leaving a bounded remainder. Most digit vectors contain enough copies of a special digit; replacing that digit by its shifted companion corrects the remainder. The source then bounds the exceptional digit vectors by an exponential decay times a fixed polynomial, yielding density \(1\) for every tail and hence for every cofinite subsequence.
GCL's current state
The frozen catalogue packet is teorth/erdosproblems 536408716724a2402bdfa7c1d764bf83d64a8c89, file blob 4e60263a80af6207aca494d2e1388e44fa372889, source SHA-256 be65b0db56fe13becec3178f2937685ee7e6a2f5df9325712474722c279c4182. Entry 347 says informal_status: proved, formal_status: Lean, and status: proved (Lean), all updated January 21, 2026, with topics number theory and complete sequences.
The pinned FormalConjectures file is commit 85f863718beeec7b58a3a1926ee92e3472bc2020, blob e084037735af8e83f24bd6c212da4d7129911c96, SHA-256 08bdafe5f6936a5e3abe8a805c059763acd750bbcf392cbcd877fa48cd58e48f. It formalizes an existential sequence, a monotonicity condition, the ratio limit, and density for every cofinite-index map, but its theorem body is by sorry. It is a statement interface, not a checked proof. The live page’s “PROVED (LEAN)” label and the discussion reports are external status evidence; neither is GCL mathematical certification.
What remains
The source-level theorem is available and matches the registered affirmative question in its main quantifiers: one sequence, ratio limit \(2\), and density \(1\) after every finite deletion. A bounded successor task should now audit the semantic bridge between the Barschkis construction and the pinned formal interface. In particular, check positivity and indexing, the meaning of “cofinite subsequence,” the use of Monotone rather than strict monotonicity, and whether range ι with finite complement exactly expresses finite deletion.
The same task can formalize the finite greedy-cover lemma for arbitrary \(n\), then isolate the exceptional-vector estimate. Acceptance should require matching hypotheses and a proof that the finite estimates extend from scale endpoints to all cutoffs. It should stop if the formal statement needs material changes or if the source proof’s omitted details cannot be supplied from the locked note. This is a bounded verification and reusable-lemma opportunity, not a new claim that GCL has certified the theorem.
Sources and claim boundaries
- Original GCL issue #1617, assignment
ERDOS-CATALOGUE-0347-S01; it had zero comments at audit time. Original SOURCE RESULT/1 citation: authenticated original RESULT/1. - Live problem page, last edited January 22, 2026, and its discussion, which records the author’s report, Tao’s comments, and later formalization reports. Forum comments are not independently verified mathematical authority.
- Barschkis source note and PDF, the primary proof documents used here.
- Pinned catalogue bytes and pinned formal statement, with the hashes recorded above.
This article reports source evidence, a reproducible finite check, and a bounded formalization target. It does not replay Lean, certify the mathematics, convert an external report into a GCL result, or decide accepted coverage; the V2 ledger alone governs that documentary status.
Catalogue and evidence provenance
- Pinned catalogue source: teorth/erdosproblems at
536408716724. - GCL issue: #1617 — 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.