Erdős Problem #34
Editorial depth: Reviewed explanatory article — evidence qualified.
Snapshot classification: disproved (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
List the numbers from 1 to \(n\) in some order. Consider every consecutive block of the list and form its sum. Can the number of different block-sum values always be much smaller than \(n^2\) as \(n\) becomes large?
Erdős Problem #34 conjectured that the number was \(o(n^2)\) for every permutation. This is disproved: suitable permutations produce a quadratic-order number of different consecutive sums. Consecutive blocks are not the same as arbitrary subsets.
A small example
For the permutation \((1,2,3)\), the six nonempty consecutive blocks yield sums
There are five distinct values, because 3 appears twice. Define the prefix sums by \(P_0=0\) and \(P_j=a_1+\cdots+a_j\). Every consecutive block sum can be written exactly as
Thus the possible sums are forward differences between prefix sums. There are \(n(n+1)/2\) blocks, giving a trivial quadratic upper bound; the conjecture asked for strictly smaller asymptotic order.
What is known
The negative answer was developed through counterexamples of Hegyvári and subsequent constructions studied by Jakub Konieczny, On consecutive sums in permutations (2015). The primary work produces permutations with a positive multiple of \(n^2\) distinct consecutive sums. A finite illustration of prefix differences cannot establish that asymptotic construction.
GCL's current state
Source audit #1303 checks the exact distinction between consecutive and arbitrary subset sums, derives the prefix-difference identity and specifies a bounded permutation enumeration task. The registry reports external Lean work, not a GCL-protected kernel replay.
What remains
The original little-oh conjecture has been refuted. Further inquiry concerns sharp extremal constants, explicit optimal permutations and fully source-pinned formal verification of the published constructions, not another claim that the original question is open.
Sources and claim boundaries
- Erdős Problems #34: DISPROVED status and historical references.
- Konieczny (2015), primary author manuscript: construction-based disproof, not re-proved here.
- GCL source return #1303: elementary prefix-sum algebra, not asymptotic certification.
Catalogue and evidence provenance
- Pinned catalogue source: teorth/erdosproblems at
536408716724. - GCL issue: #1303 — 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.