Erdős Problem #344
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
Let \(A\) be an infinite set of positive integers. Write \(A(N)\) for the number of elements of \(A\) at most \(N\), and let \(P(A)\) be the set of all finite subset sums, including the empty sum. Erdős Problem 344 asks whether there is an absolute constant \(c>0\) such that
An infinite arithmetic progression has the form \(u,u+d,u+2d,\ldots\) with \(d>0\). The word “subcomplete” is shorthand for containing such a progression. It is weaker than being complete, which means that \(P(A)\) contains every sufficiently large integer. The distinction matters: a fixed congruence obstruction can prevent completeness even when arbitrarily long progressions occur.
The maintained page phrases the density assumption with the asymptotic notation \(A(N)\gg N^{1/2}\). The source-audit normalization is the equivalent quantified form “there is a fixed \(c>0\) and a threshold after which \(A(N)\ge c\sqrt N\).” The finite sums use each member of \(A\) at most once. The frozen catalogue identifies the problem as number theory about complete sequences and records it as proved, not open.
A small example
Take the finite set \(A_4=\{1,2,4,8\}\). Every subset sum is an integer between \(0\) and \(15\), and the binary expansion shows that each such integer occurs exactly once. An exact enumeration verifies the finite statement:
For a reproducible check, enumerate all subsets by bit masks. The calculation returns 16 sums, minimum 0, maximum 15, and no missing or extra values. This illustrates why finite subset sums naturally produce intervals, but it does not establish the problem: \(A_4\) is finite, it has no asymptotic counting function, and a finite interval is not an infinite arithmetic progression. Even the infinite set of powers of two requires a separate binary-expansion argument; a finite experiment cannot replace the quantified theorem.
What is known
The primary resolution is Endre Szemerédi and Van H. Vu, “Finite and infinite arithmetic progressions in sumsets,” Annals of Mathematics 163 (2006), 1–35, DOI 10.4007/annals.2006.163.1. Their Theorem 1.1 on printed p. 2 states that for some positive constant \(c\), every subset \(B\subseteq\{1,\ldots,n\}\) with at least \(c\sqrt n\) elements has finite subset sums containing an arithmetic progression of length \(n\). This is a finite theorem with a uniform constant.
The same paper then gives the exact infinite interface needed here. Corollary 1.4 on printed p. 4 says that every increasing sequence of density at least \(c\sqrt n\) is subcomplete. The proof is developed in Section 6: Lemma 6.4 (printed p. 32) constructs arbitrarily long progressions with one stabilized difference, and the final argument combines two interlaced subsequences to obtain an infinite progression. Thus the paper’s Corollary 1.4 matches the normalized Problem 344 claim, not merely a nearby finite variant.
The page also records a sharper-looking threshold as still open:
That is a different claim from the solved existence of a suitable constant. The density condition therefore has two layers: Szemerédi–Vu settle the qualitative threshold up to an unspecified absolute constant, while the extremal constant question remains outside the solved statement. Folkman’s earlier result under \(N^{1/2+\epsilon}\) is historical context and a strictly stronger hypothesis, not the final answer.
GCL's current state
The exact assignment issue is MATH-PROGRAMME #1614. At audit time it was open, labelled for direct editorial pickup and source audit, and had zero comments; the original SOURCE RESULT/1 citation is authenticated original RESULT/1. No result is being invented or posted by this worker.
The frozen catalogue source is teorth/erdosproblems at commit 536408716724a2402bdfa7c1d764bf83d64a8c89, specifically data/problems.yaml, entry 344. Its Git blob is 4e60263a80af6207aca494d2e1388e44fa372889; the entry says proved, last updated 2025-08-31, formal_status: unformalized, and formalized: no. The live Problem 344 page, last edited 28 December 2025, agrees that the statement is proved by Szemerédi and Vu, while separately calling the following strengthening open:
The pinned FormalConjectures upstream revision 85f863718beeec7b58a3a1926ee92e3472bc2020 contains no Problem 344 file. A separate external repository has a newer theorem source at plby/lean-proofs commit 8822f7ddef30fadbd92e1c6ab4ed897af356af5, but its file Erdos344.lean ends the theorem with by sorry. It is an unverified external interface, not a replay or GCL certification. Accepted coverage is decided by the protected V2 ledger alone.
What remains
The original yes/no claim is source-resolved, so a successor task should not reopen it as an open conjecture. The useful bounded work is a source-locked formal interface audit. It should compare the primary Corollary 1.4 with a Lean statement using an explicit set \(A\subseteq\mathbb N\), an eventual lower bound \(A(N)\ge c\sqrt N\), finite subset sums, and an explicit witness \(u,d\) with \(d>0\) and \(u+id\in P(A)\) for every \(i\in\mathbb N\).
Acceptance would require a line-by-line quantifier comparison, a pinned source reference, and a machine-readable theorem statement whose proof status remains clearly sorry until independently checked. Falsification would be any mismatch in “eventually” versus “for all,” finite subset versus repeated summand, or an omitted positivity condition on the common difference. Stop after the interface and semantic ledger are complete; do not attempt an exhaustive Lean build or claim that a formal theorem has been proved.
Sources and claim boundaries
- Primary theorem: Szemerédi–Vu, Annals PDF, Theorem 1.1 p. 2, Corollary 1.4 p. 4, Lemma 6.4 and the completion argument pp. 32–33. The accessed PDF has SHA-256
288fdc41db18e95409d36d95f777a882f64330edbc26100e84630731eef4e747. - Original catalogue citation: the maintained page identifies Erdős and Graham, Old and New Problems and Results in Combinatorial Number Theory (1980), p. 54, as
[ErGr80]; the exact source packet and frozen commit are linked above. - Status evidence: live Problem 344 and the frozen catalogue commit/blob. Their metadata is evidence about recorded status, not mathematical certification.
- Formal boundary: no Problem 344 file exists in the pinned FormalConjectures revision. The newer
plby/lean-proofssource is explicitlysorry-bearing and unverified. - Finite boundary: the exact \(\{1,2,4,8\}\) enumeration verifies one finite identity only; it proves neither the asymptotic hypothesis nor the infinite theorem.
This article reports an externally published proof and preserves the stronger-threshold open question. It supplies no new proof, Lean replay, GCL mathematical certification, publication authority, or award claim. Accepted editorial coverage remains whatever the protected V2 ledger records.
Catalogue and evidence provenance
- Pinned catalogue source: teorth/erdosproblems at
536408716724. - GCL issue: #1614 — 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.