Skip to content

Erdős Problem #356

Editorial depth: Reviewed explanatory article — evidence qualified.
Snapshot classification: proved (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

Let \(a = (a_1,\ldots,a_k)\) be a strictly increasing list of positive integers, with every term at most \(n\). A consecutive sum is obtained by choosing two indices \(u\) and \(v\) with \(1 \leq u \leq v \leq k\) and adding the entries from \(a_u\) through \(a_v\). The question is whether there is one fixed constant \(c>0\) such that, for every sufficiently large \(n\), some such list has at least \(cn^2\) different consecutive-sum values. The number of intervals is at most quadratic, so the question asks whether a positive proportion of the possible interval positions can produce different integers.

This is Erdős Problem 356, attributed to Erdős and Graham. The exact source question is recorded in the original issue and in the frozen catalogue entry at commit 536408716724a2402bdfa7c1d764bf83d64a8c89. The entry is the object with Git blob 4e60263a80af6207aca494d2e1388e44fa372889; its catalogue fields say “proved” and separately report formal_status: Lean, while its formalized field says “no.” Those metadata are evidence to reconcile, not the mathematical statement.

A small example

Take \(a=(1,2,4,8)\). Enumerating the ten intervals gives, in interval order,

\[ 1,2,4,8,3,6,14,7,12,15. \]

After sorting, this is \(\{1,2,3,4,6,7,8,12,14,15\}\), with ten distinct values. Thus the exact count is \(4\cdot5/2=10\), equal to the number of intervals. This was checked by integer enumeration: for every pair \((u,v)\), compute sum(a[u:v+1]), sort the resulting list, and verify that it equals [1,2,3,4,6,7,8,12,14,15] and has length ten.

The example illustrates the object being counted and provides a reproducible finite arithmetic check. It does not establish the Erdős--Graham assertion: one finite list gives no constant valid for all large \(n\), and this particular binary sequence does not supply a construction bounded by \(n\) at every scale.

What is known

The primary resolving source is Adrian Beker, “On a problem of Erdős and Graham about consecutive sums in strictly increasing sequences.” The work appeared first as arXiv:2311.10087v1, submitted 16 November 2023, and was published in the Bulletin of the London Mathematical Society 56 (2024), 2749--2759, DOI 10.1112/blms.13098. The arXiv v1 PDF was read as a nine-page primary source; its downloaded-byte SHA-256 was 9f490cf7ecb609e0471bb130ba3ba21b152e2f49ea96cd7376331ee1cc156143.

Beker’s Theorem 1.2 states the affirmative result with stronger quantification: there is a constant \(c_1>0\) such that for every positive integer \(n\) there are integers \(1\leq a_1<\cdots<a_k\leq n\) whose consecutive sums contain at least \(c_1n^2\) distinct values. The proof first treats random perturbations \(a_i=3i+\varepsilon_i\), where the signs are independent and symmetric, by bounding the expected additive energy of the partial-sum set. It also gives an explicit family, with a parameter \(b\) in the stated logarithmic range, and derives a positive quadratic lower bound. The paper’s Proposition 1.5 supplies a separate upper bound, while its final section leaves the optimal constant and typicality questions open.

The original problem source is P. Erdős and R. Graham, Old and New Problems and Results in Combinatorial Number Theory, Monographie 28, Université de Genève, 1980, p. 58, cited as ErGr80 by the maintained problem page. The maintained page currently says “PROVED,” attributes the affirmative solution to Beker, links the paper, and records “Formalised statement? No.” Its LaTeX source view also records the related permutation problem and other follow-up questions; those are not part of the registered theorem.

GCL's current state

The frozen catalogue revision was generated at commit 536408716724a2402bdfa7c1d764bf83d64a8c89 on 2026-10-09 and records the status as “proved (Lean)” despite formalized: no. The live page, the exact Beker theorem, and the programme issue agree on the ordinary mathematical resolution, but they do not establish a formal theorem in GCL. The admitted FormalConjectures provider snapshot is FC-GDM-85F86371, upstream revision 85f863718beeec7b58a3a1926ee92e3472bc2020; its manifest SHA-256 is faa43f174717ef0126114b9bbd61bb9fdc827ce7eb9f64e56c1e63c7b15608db, and the relevant catalogue shard has SHA-256 33d1929f630431fe731cf0880cd01312cee3c7fa043ed5f1d4499fa28c0533fd. A direct exact-commit lookup for FormalConjectures/ErdosProblems/356.lean returns no file. Therefore there is no pinned Lean theorem, with or without sorry, to inspect for this problem.

This article records source evidence and a documentary boundary. It does not certify the proof, certify formal coverage, or convert any upstream label into GCL acceptance. Accepted coverage is decided by the V2 ledger alone. The original source-audit result citation remains authenticated original RESULT/1.

What remains

The natural bounded successor is a statement-and-provenance package. First, copy the exact quantifiers of Beker’s Theorem 1.2 into a proposed formal statement, explicitly choosing the type of \(n\), the finite sequence length \(k\), positivity, strict ordering, the upper bound \(a_k\leq n\), and the cardinality condition on the set of interval sums. Second, compare that statement line by line with the Erdős--Graham wording and the live entry, keeping the permutation and “consecutive integers greater than \(n\)” follow-ups separate. Third, record whether a new formal file exists at a newly pinned upstream commit; if it does not, stop at the source-normalized statement.

Acceptance should require a source-linked statement, theorem and page references, a documented semantic comparison, and a finite exact test such as the example above. Falsification is any missing quantifier, changed bound, conflation of the random and deterministic constructions, or claim that a provider label is a checked proof. The stopping rule is reached when the statement, sources, hashes, and formal-file presence have been recorded; a Lean build or mathematical certification is outside this article’s authority.

Sources and claim boundaries

The source chain is: issue #1626; the frozen catalogue commit and blob; the maintained live entry; Erdős and Graham (1980), p. 58; and Beker’s arXiv v1 HTML/PDF and published DOI record. The programme’s read-only provider metadata are recorded in mathforge_external_source_imports.json.

The external paper supplies an established published theorem; the live and frozen catalogues supply dated status metadata; the finite enumeration supplies only a checked small instance; and no FormalConjectures file was found at the pinned commit. None of these observations is a GCL mathematical certificate. No priority, prize, novelty, or publication claim is made, and the unrelated follow-up problems are deliberately excluded.

Catalogue and evidence provenance

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

Back to catalogue · Compendium introduction