Erdős Problem #343
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
Take a multiset \(A\) of positive integers. Repetitions count: if the value \(7\) occurs five times, those are five available occurrences for making sums. Let \(A(N)\) count occurrences whose value is at most \(N\), and let \(P(A)\) be the set of sums of finitely many distinct occurrences, including the empty sum. Erdős Problem 343 asks whether a uniform linear lower bound on \(A(N)\) forces \(P(A)\) to contain an infinite arithmetic progression.
In the formulation recorded on the maintained problem page, the hypothesis is \(A(N)\gg N\) for every \(N\). The natural theorem-level normalization is slightly more precise: there is an absolute constant \(C>0\) such that every positive, nondecreasing sequence of occurrences satisfying \(A(N)\geq CN\) for all sufficiently large \(N\) is subcomplete. “Subcomplete” means that \(P(A)\) contains all terms of some progression \(a,a+d,a+2d,\ldots\) with \(d>0\). The eventual version is the one proved in the primary source and implies the all \(N\) version after changing finitely many initial terms or enlarging the constant.
This is a question about additive structure, not merely about how many elements are present. A dense collection can still have congruence obstructions: for example, the even numbers have many elements below \(N\) but all their subset sums are even. The theorem says that linear density, when repetitions and the full sequence structure are handled correctly, is enough for subcompleteness; it does not say that every sufficiently large integer is a subset sum.
A small example
Here is an exact finite check. For \(A=[1,2,3,4]\), enumerate every subset of the four labelled occurrences. The calculation
A= [1, 2, 3, 4]
P(A)= [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
equals_interval_0_10= True
contains_AP_3_8_step_1= True
was produced by exact integer enumeration of all \(2^4\) subsets. Thus this finite \(P(A)\) contains the progression \(3,4,5,6,7,8\). It illustrates the definitions and checks the occurrence-sensitive subset-sum operation, but it proves nothing about an infinite multiset or a density threshold. No finite experiment can establish the existence of one progression continuing forever.
What is known
The primary resolving source is E. Szemerédi and V. H. Vu, “Long arithmetic progressions in sumsets: Thresholds and bounds,” Journal of the American Mathematical Society 19 (2006), 119–169, DOI 10.1090/S0894-0347-05-00502-3. In the author manuscript, Section 6, Theorem 6.3, p. 28, states that some constant \(C\) works for every infinite nondecreasing sequence of positive integers with \(A(N)\geq CN\) for all sufficiently large \(N\). Its conclusion is exactly subcompleteness. The manuscript defines \(A(N)\) as an occurrence count and explicitly allows repeated values, so the multiset reading is not an editorial invention.
The proof uses a finite long-progression theorem for subset sums, then organizes the infinite sequence into blocks. A fixed positive difference is stabilized across arbitrarily long finite progressions, and a complementary additive-net argument turns those finite progressions into an infinite one. The same section records Folkman’s stronger earlier result with a density of order \(N^{1+\epsilon}\), and explains why the linear threshold is the sharp scale up to constants. Folkman’s paper is J. Folkman, “On the representation of integers as sums of distinct terms from a fixed sequence,” Canadian Journal of Mathematics 18 (1966), 643–655.
The live Problem 343 page, last edited 2 December 2025, attributes the original question to Folkman and identifies the Szemerédi–Vu result. The page’s statement uses \(\gg N\) for all \(N\); the primary theorem uses an eventual bound. That difference is a harmless presentation strengthening only after the quantifiers and finite-prefix convention are made explicit. It should remain documented rather than silently erased.
GCL's current state
The original issue #1613 pins teorth/erdosproblems at commit 536408716724a2402bdfa7c1d764bf83d64a8c89, data/problems.yaml, blob 4e60263a80af6207aca494d2e1388e44fa372889. That entry reports informal status proved, formal status Lean, and formalized: no, with a September 2026 update. The maintained catalogue is status evidence, not a mathematical certificate; V2 ledger rules alone decide accepted coverage.
The admitted GCL FormalConjectures provider snapshot FC-GDM-85F86371 has no FormalConjectures/ErdosProblems/343.lean at the pinned commit, and the current provider tree checked during this audit also has no such file. Therefore there is no pinned official Lean statement, theorem body, or sorry-bearing declaration to compare. This absence is a provider-snapshot fact, not evidence against the theorem.
An external package, JSP-000285, supplies a no-sorry statement and proof development for the eventual multiset theorem. Its Statement.lean blob is e68c6164ff16ef8d6f49ec0cc98888c8cdb6b961; its verification report claims a successful Lean build and replay. Those are useful reproducibility reports, not a GCL replay or certification. The report also says no official #343 comparator was available at its checked pin.
What remains
The bounded successor is a source-alignment and formal-interface task. Its input should be the pinned Szemerédi–Vu theorem, the catalogue entry, and the external package’s definitions of occurrence counting, eventual linear density, and subcompleteness. The target is a short correspondence table proving, at the statement level, that the package’s HasEventualLinearCountingLowerBound and IsSubcomplete match the paper’s nondecreasing multiset formulation, including positivity, distinct occurrence indices, and the meaning of an infinite progression.
Acceptance should require a line-by-line quantifier comparison, exact source hashes, and a finite test covering repeated values. Falsification is triggered by any missing hypothesis, a change from multisets to sets, an altered “eventually” quantifier, or a conclusion that gives only arbitrarily long finite progressions. Stop after the interface report and finite checks; do not launch an exhaustive Lean build merely to refresh an external claim. A later formal certification would need its own authorized mathematical and replay route.
Sources and claim boundaries
The documentary source lock is the issue-specific inquiry: issue #1613, the frozen catalogue commit and blob above, the live page, the Szemerédi–Vu author manuscript (downloaded PDF SHA-256 2ed539da3c750fb286e8291eaef34a4d10922a343158309cc8abac1adce50852), and the Folkman reference. The external formal package is cited as an unverified report with its commit and statement blob, not as GCL evidence. The original SOURCE RESULT/1 citation is authenticated original RESULT/1.
Accordingly, this article records an established published mathematical result, a precise normalization, a reproducible finite calculation, and a reported external formalization. It does not claim independent Lean replay, GCL mathematical certification, official prize acceptance, priority, or publication status. It also does not convert catalogue labels into accepted coverage: those labels remain inputs to the governed V2 ledger process.
Catalogue and evidence provenance
- Pinned catalogue source: teorth/erdosproblems at
536408716724. - GCL issue: #1613 — protected issue/assignment identity; its labels and results are live, not reproduced automatically here.
- GCL triage: OUTSIDE_STRICT_OPEN_TRIAGE.
- Formal-statement coverage: No statement was confirmed in GCL's pinned formal-provider snapshot. Presence does not mean the statement or proof has been checked.
- External mathematical status: consult current problem page and its dated bibliography.