Erdős Problem #341
Editorial depth: Reviewed explanatory article — evidence qualified.
Snapshot classification: open (not automatically the live result).
Subject areas: number theory.
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
Start with any finite set of positive integers \(A=\{a_1<\cdots<a_k\}\). After the seed has been prescribed, repeatedly choose the least integer larger than the current last term that is not a sum \(a_i+a_j\) of two already chosen terms, where repeated indices are allowed. This is the Dickson version of the greedy sum-avoiding construction. The question is whether, for every finite seed, the successive gaps
eventually repeat with some fixed period.
“Eventually” matters: the first part of a sequence may look irregular for a long time, while the tail could repeat forever. Green’s open-problems list distinguishes this rule from Queneau’s variant, which forbids \(i=j\). Problem 341 concerns the rule allowing \(i=j\).
The wording on the maintained Erdős Problems page is an individual-seed formulation, but its mathematical question is naturally read universally over finite positive seeds. It also records the historical example \(\{1,4,9,16,25\}\) and says that periodicity can take thousands of terms to appear. That remark is a motivation, not a theorem about all seeds.
A small example
Take the page’s seed \(A=\{1,4,9,16,25\}\). I recomputed the greedy rule using exact integers: at each stage I formed every sum of two terms already present, including equal pairs, then scanned upward from the last term. The calculation gives
and
The second six-term block is the first block translated by \(1176\). More importantly, an exact finite certificate checks the proposed tail through \(2\cdot426+1176-2=2026\). Below \(426\) there are \(86\) selected values; from \(426\) onward there are \(224\) selected residues modulo \(1176\). If \(R\) is that residue set and \(E\) is the union of \(R\) with the residues of the pre-tail values, the direct residue calculation gives \(|E|=233\) and
with both sides having \(952\) residues. Together with the exact recurrence check up to \(2026\), this is a finite all-future certificate for this seed: \(a_{n+224}=a_n+1176\) for every \(n\ge87\). It proves one instance, not the universal assertion. It also does not validate unrelated computations or settle whether every seed eventually behaves this way.
What is known
The primary historical reference named by the live page is P. Erdős and R. L. Graham, Old and New Problems and Results in Combinatorial Number Theory, p. 53. A directly fetched copy has SHA-256 0cbf0c32f0ab1e71c71db5121a88bac905bf976c4a6ab6bb6d7d9cf9ddd184ed3; the page’s bibliography label is [ErGr80,p.53]. The source is the historical problem reference, not evidence that the question has since been solved.
Ben Green’s current 100 Open Problems, Problem 7 and its comments, explicitly describes both the Dickson rule and the distinct-index variant, and says that eventual periodicity appears open for both. Green points readers to references and computations, not to a resolution. This is the clearest dated primary source located in the inquiry for the status boundary.
The live page was edited 20 January 2026 and still displays open status, zero proof expositions, one discussion comment, and a formalised-statement link. Its July 2026 comment reports a period length of \(224\) terms and a translation of \(1176\), but the forum warns that proof claims and comments are unverified. The exact calculation above independently reproduces the stated finite certificate; it is not a proof of the general problem.
GCL's current state
The frozen catalogue packet is teorth/erdosproblems at commit 536408716724a2402bdfa7c1d764bf83d64a8c89, entry number: "341", Git blob 4e60263a80af6207aca494d2e1388e44fa372889. It records informal status open, last update 2025-08-31, and formal-solution status unformalized; its separate metadata says the statement is formalized.
The pinned FormalConjectures file is at commit 85f863718beeec7b58a3a1926ee92e3472bc2020, blob efaaf059358f43005bbf785dd8b6a1a5c789b937. Its theorem is marked research open, but the proof ends in sorry. It quantifies over arbitrary integer-valued sequences satisfying an eventual leastness condition; it does not explicitly quantify over positive finite seeds or assert the full seed-to-extension construction. Therefore “formalized” is not “proved,” and the file is not yet a certified semantic match to the historical statement.
What remains
The central task is to prove or refute eventual periodicity for every finite positive seed under the repeated-index rule. A useful bounded successor is to formalize and independently check the finite-certificate lemma used above: a proposed tail onset \(N\), period modulus \(q\), and residue set \(R\) should be accepted only after exact recurrence checks through \(2N+q-2\) and a residue identity. This would turn individual computational discoveries into auditable theorems without pretending that a finite search proves the universal claim.
The smallest semantic prerequisite is a precise definition of the greedy extension, including the seed boundary, positivity, strict ordering, and whether equal summands are permitted. Only after that normalization should the Lean statement be repaired and proved or falsified. Extensive searches for apparent nonperiodicity remain finite evidence unless coupled to a proof of aperiodicity.
Sources and claim boundaries
- Original GCL issue #1611: assignment, labels, source packet, and required return. Original SOURCE RESULT/1 citation: authenticated original RESULT/1.
- Erdős Problems #341: live wording, bibliography label, dated page state, and unverified discussion link.
- Erdős and Graham, Old and New Problems and Results in Combinatorial Number Theory, p. 53: historical source named by the live entry. The fetched PDF hash was
0cbf0c32f0ab1e71c71db5121a88bac905bf976c4a6ab6bb6d7d9cf9ddd184ed3. - Green, 100 Open Problems, Problem 7 and comments; fetched PDF hash
e06971245914947f152550dee59bbb29fe0e798f0c51b2bc2557f824c2f9a44a. - The finite values and residue counts above are exact arithmetic checks. They are not GCL mathematical certification, and V2 ledger state alone decides accepted coverage.
Catalogue and evidence provenance
- Pinned catalogue source: teorth/erdosproblems at
536408716724. - GCL issue: #1611 — 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.