Skip to content

Erdős Problem #358

Editorial depth: Reviewed explanatory article — evidence qualified.
Snapshot classification: proved (not automatically the live result).
Subject areas: number theory, additive basis, primes.

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 358 asks how often a positive integer can be built by adding a consecutive block from an increasing sequence. Write the sequence as \(A = \{a_1 < a_2 < \cdots\}\). For a target \(n\), count pairs of positive indices \(u \leq v\) for which

\[ n = a_u + a_{u+1} + \cdots + a_v. \]

Call this count \(f(n)\). The original question has two nested goals: can one choose a single increasing sequence for which \(f(n)\) tends to infinity as \(n\) grows, or at least make \(f(n) \geq 2\) for every sufficiently large \(n\)? The sequence is chosen once; the representations may use different starting points and lengths for different targets.

The wording matters. A one-term block, such as \(n=a_u\), is included in the original definition. A later variant asks for a representation with at least two terms. The problem also discusses the special choice in which the sequence is the primes, but that is a separate conjectural direction rather than the existential question above.

A small example

Take the simplest increasing sequence, \(a_i=i\). For \(n=15\), an exhaustive exact check of all positive intervals gives

\[ 1+2+3+4+5=15,\qquad 4+5+6=15,\qquad 7+8=15,\qquad 15=15. \]

Thus \(f(15)=4\). The odd divisors of \(15\) are \(1,3,5,15\), also four in number. The equality is not a coincidence: for this sequence, the number of consecutive-sum representations equals the number of odd divisors. The same finite enumeration gives only the one-term representation \(16=16\) for \(n=16\), matching the single odd divisor of \(16\).

This check was performed with integer arithmetic by enumerating every \(1 \leq u \leq v \leq n\), accumulating the exact sum, and comparing the resulting count with the list of odd divisors. It verifies a concrete finite identity and illustrates why the sequence of all positive integers cannot solve the asymptotic question: powers of two have very few representations. It does not prove anything about an arbitrary sequence, nor does it establish a limit statement.

What is known

Terence Tao's primary note, “A set that represents all large integers multiple times by consecutive elements,” dated 24 February 2026, states Theorem 1.1: there is a set \(A\) of positive integers for which every sufficiently large \(n\) has at least a constant multiple of \(log n\) representations as a sum of consecutive elements of \(A\). Tao defines \(r_A(n)\) using blocks of \(q \geq 1\) consecutive elements. The proof uses the probabilistic method, with random red and blue blocks and a collision-avoidance argument. The note is 14 pages and explicitly says that earlier claimed arguments by Sothanapan and by Chojecki and GPT did not constitute complete proofs.

Because an increasing enumeration of a set of positive integers is an increasing sequence, Tao's theorem supplies the requested existential sequence. Its lower bound eventually exceeds two, so it also answers the second part. Moreover, by the elementary observation that at most one representation can have one term, the same result implies that some representation has at least two terms for every sufficiently large \(n\); this is a consequence of the theorem, not a separate formal replay here.

The live Erdős Problems entry, accessed 13 October 2026, records the original references [Er77c] and [ErGr80], discusses the prime-set question, and says that Tao has constructed such a set. It was last edited 1 April 2026 and reports no proof exposition. The entry also records the related Moser 1963 prime-sum source and Guy's 2004 collection. These references document the history and variants; Tao's note is the primary source for the current existential construction.

GCL's current state

The assignment is tracked by MATH-PROGRAMME issue #1628, assignment ERDOS-CATALOGUE-0358-S01. Its pinned catalogue source is teorth/erdosproblems data/problems.yaml at commit 536408716724a2402bdfa7c1d764bf83d64a8c89, whose Git blob is 4e60263a80af6207aca494d2e1388e44fa372889. Entry 358 says informal status proved, formal status Lean, and formalized yes; it gives the informal update date 1 April 2026 and formal-status update date 23 August 2026.

The pinned FormalConjectures file is at commit 85f863718beeec7b58a3a1926ee92e3472bc2020 and blob d6b16b320d205fc6362fe756d07457940b7407a4. It defines interval representations on A : ℕ → ℕ, requires positive indices, and uses StrictMono A. Its parts i and ii are tagged solved, while every theorem body, including the textbook identity and open variants, is by sorry. This is a formal statement record, not a checked proof.

The formalization therefore differs from the prose in two visible ways: it uses natural-valued sequences rather than integer-valued ones, and its definition does not explicitly require \(u \leq v\) (although positive increasing terms make reversed intervals irrelevant for positive large targets). It also labels the existential at-least-one-nontrivial-representation variant open, even though Tao's theorem appears to imply it. That status should be reconciled by the responsible formal-status process, not silently changed in this article. V2 ledger state, not this manuscript, decides accepted coverage. No GCL mathematical certification is supplied here.

What remains

The main external theorem is available, but a useful successor task is a bounded semantic-and-formal interface audit. Its input should be the exact Tao PDF, the two frozen source blobs above, and the formal file at its pinned commit. Its target should be a written correspondence showing that Tao's \(r_A(n)\) and the formal f A n count the same positive-index, consecutive-block objects for the constructed increasing enumeration, with the precise treatment of one-term blocks and “sufficiently large.” Acceptance should require a line-by-line quantifier table, a proof that Tao's bound yields both existential questions, and either a proved Lean bridge or a clearly isolated list of missing library lemmas. Falsification is any mismatch in indexing, positivity, set-versus-sequence order, or asymptotic threshold. Stop when the correspondence is complete or one source-dependent mismatch is reproducibly isolated; do not launch an exhaustive Lean build.

The prime-set variants remain genuinely separate. The live entry and formal file describe conjectures about the limsup of the number of consecutive-prime representations and the upper density of representable integers. Tao's construction chooses a set for the existential problem; it does not prove either prime-set assertion. The historical question about positive density should likewise not be reported as solved merely because the existential problem is solved.

Sources and claim boundaries

The primary proof source is Tao, “A set that represents all large integers multiple times by consecutive elements,” PDF, SHA-256 4bb434cfcb2200b7629ad31fcbfd93efcadafe6266905d51ac86bea0b6ddb94f; its Theorem 1.1 is on page 1. Original historical references are Erdős, Er77c, Erdős–Graham, ErGr80, and Moser, Mo63, as listed by the live entry.

The original SOURCE RESULT/1 citation is authenticated original RESULT/1. The issue, catalogue, live page, and formal file are evidence sources, not acceptance decisions. This article records the source lock, the finite arithmetic check, and the semantic boundary; it does not certify Tao's proof, certify Lean code, resolve the prime conjectures, or promote any status beyond the evidence cited above.

Catalogue and evidence provenance

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

Back to catalogue · Compendium introduction