Skip to content

Erdős Problem #348

Editorial depth: Reviewed explanatory article — evidence qualified.
Snapshot classification: open (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 348 asks how robust an infinite nondecreasing sequence of integers can be as a source of subset sums. Call a sequence complete when every sufficiently large integer can be written as a sum of finitely many terms, with each indexed occurrence used at most once. The question fixes integers \(0 \leq m < n\) and asks whether there is a sequence that stays complete after deleting any \(m\) occurrences, but becomes incomplete after deleting any \(n\) occurrences.

The word “any” is decisive. The first requirement is universal over all choices of \(m\) deleted positions, and the second is universal over all choices of \(n\) positions. Repeated values are still separate occurrences: two copies of \(1\) can be used independently, and deleting one copy need not delete the other. The 1980 source also uses eventual completeness, allowing finitely many exceptional integers. That is weaker than requiring every positive integer to be represented.

A small example

The powers of two explain the easiest boundary. For the finite prefix \(A_4 = \{1,2,4,8,16\}\), exact enumeration of all \(2^5=32\) subsets gives every sum from \(0\) through \(31\). After deleting the occurrence \(4\), the remaining subset sums are

\[ \{0,1,2,3\} + \{0,8\} + \{0,16\} = \{0,1,2,3,8,9,10,11,16,17,18,19,24,25,26,27\}. \]

Thus the verified missing values in this finite window are \(4\) through \(7\), \(12\) through \(15\), \(20\) through \(23\), and \(28\) through \(31\). The calculation is exact integer arithmetic, not a heuristic search: an exhaustive bit-mask enumeration reports 32 sums for the full prefix and 16 for the deleted prefix. Passing to the infinite powers-of-two sequence makes the pattern permanent: numbers whose binary expansion needs the deleted bit occur infinitely often, so one deletion destroys eventual completeness. This finite check illustrates the mechanism; it does not by itself prove an infinite statement.

The other classical example is the Fibonacci sequence with two initial ones, \(1,1,2,3,5,\ldots\). The original source records that it survives any one deletion but not any two deletions. The repeated initial \(1\)’s matter: they are two indexed occurrences, not one set element.

What is known

Erdős and Graham’s Old and New Problems and Results in Combinatorial Number Theory (1980), section 6, defines completeness as eventual coverage by finite subset sums on printed page 54. On printed page 57 it poses this question and records the powers-of-two and Fibonacci examples, while saying that the case \(m=2\), \(n=3\) was not known. That is the original primary statement and the historical baseline.

The maintained Erdős Problems entry remains marked OPEN when consulted for this audit. It repeats the two examples and says that Wouter van Doorn ruled out \(2 \leq m < n\) for the stronger interpretation in which every positive integer, rather than all sufficiently large integers, must be represented. The entry itself warns that the intended Erdős–Graham interpretation is probably the weaker, eventual one. A 6 September 2025 discussion comment also identified this strong/weak distinction and said the formalization had been updated; a 16 July 2026 comment reports computational experiments around \((2,3)\), but explicitly presents them as evidence and not a witness or proof.

Jesse Geneson’s arXiv preprint, version 1 dated 20 September 2026, claims a full answer for the eventual interpretation: such sequences exist exactly when \(m \leq 1\). Its Theorem 1 uses indexed occurrences and eventual completeness. The proof’s central-interval theorem controls long prefixes when the prefix slack \(S_j-a_{j+1}\) tends to infinity, and the paper gives a deletion obstruction for \(m \geq 2\). This is the strongest located result, but it is an external, unrefereed preprint; this audit read its statement and proof structure, not an independent mathematical verification.

GCL's current state

The issue-specific packet identifies catalogue commit 536408716724a2402bdfa7c1d764bf83d64a8c89, whose data/problems.yaml blob is 4e60263a80af6207aca494d2e1388e44fa372889. At that frozen revision, problem 348 is open, last updated 2025-08-31, with formal_status: unformalized and statement metadata present. The packet assigns the protected triage class PROTECTED_READY_BACKLOG.

The pinned FormalConjectures source is commit 85f863718beeec7b58a3a1926ee92e3472bc2020, file blob 3829170aaedd7757c71bde9710576908f009137f. Its theorem is tagged research open and ends in sorry. It uses eventual IsAddComplete, but its witness is a function a : ℕ → ℕ and its completeness test uses Set.range (Function.updateFinset a s 0). Since Set.range collapses equal values, this is not automatically the same as occurrence-sensitive multiset subset sums. The live file has since changed to an indexed-sequence predicate and cites Geneson, but it also still contains sorry and is not a GCL proof. V2 ledger state alone decides accepted coverage; neither this article nor an external preprint changes that state.

What remains

A bounded successor should first reconcile the formal interface with the primary statement: indexed occurrences, nondecreasing integer versus nonnegative sequences, eventual rather than strong completeness, and the meaning of deletion after duplicate values. Its input should be Geneson v1, the page-54/page-57 Erdős–Graham definitions, and the exact pinned and live Lean files. Its target should be a line-by-line semantic map and a short list of hypotheses needed to transport Theorem 1 to the catalogue formulation.

Acceptance should require that every quantifier and deletion operation is matched, that the claimed \(m \leq 1\) classification is clearly labelled as an external preprint result, and that any mismatch is recorded rather than patched by interpretation. Falsification is either a counterexample to the semantic map or a cited theorem hypothesis that the catalogue statement does not satisfy. Stop after the comparison and one bounded source check; do not launch a Lean build or promote the problem to solved status.

Sources and claim boundaries

Primary sources are Erdős and Graham, Old and New Problems and Results in Combinatorial Number Theory (1980), especially pp. 54 and 57, retrieved from the UCSD scan whose SHA-256 is 0cbf0c32f0ab1e1c71db5121a88bac905bf976c4a6ab6bb6d7d9cf9ddd184ed3; and Geneson, Deletion thresholds and exponential examples for complete sequences, arXiv:2609.25107v1, whose retrieved PDF SHA-256 is 9060ebcc3812b9a33bf08cc8dbdf6b5c8714acda2f54ed4ecfca7c152cb8dcc2. The maintained entry is Erdős Problem 348, and the assignment record is original issue #1618. Frozen code references are the catalogue file and FormalConjectures file.

The article distinguishes the original published statement, the maintained site’s status, an unrefereed external theorem claim, a finite exact check, and Lean source containing sorry. It supplies no mathematical certification, no claim that the preprint is accepted coverage, and no future issue link: the original SOURCE RESULT/1 citation is authenticated original RESULT/1.

Catalogue and evidence provenance

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