Skip to content

Erdős Problem #763

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

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 a set of positive integers, and r₂(n)=Σ_{a+b=n}1_A(a)1_A(b), counting ORDERED representations. Erdős–Turán asked whether some A and c>0 could satisfy the cumulative relation Σ_{n≤N}r₂(n)=cN+O(1). This is DISPROVED by Erdős–Fuchs; much smaller-than-N^(1/4) discrepancy is impossible under their hypotheses.

A small example

For A={1,2,3}, the ordered two-sum counts for n=2,3,4,5,6 are 1,2,3,2,1, totaling 9. For A=all positive integers, r₂(n)=n−1 for n≥2, so Σ_{n≤N}r₂(n)=N(N−1)/2, quadratic rather than linear. Such finite/examples with wrong growth do not by themselves rule out a carefully chosen infinite set.

What is known

Erdős–Fuchs [ErFu56] proved that Σ_{n≤N}r₂(n)=cN+o(N^(1/4)/(log N)^(1/2)) is impossible for c>0. Jurkat (unpublished) and Montgomery–Vaughan [MoVa90] improved the boundary to impossibility of error o(N^(1/4)). Since O(1) is o(N^(1/4)/sqrt(log N)), the original bounded-error conjecture is decisively false. This concerns cumulative ordered sums, NOT the pointwise statement r₂(n)=c+O(1). Full original analytic proofs were not independently reproduced.

GCL's current state

The authenticated original source return remains in its original BOUNDED_TASK_DESIGNED state. This is an editorially reviewed explanatory article in protected EC-BULK-005-R7, subject to that PR's protected merge. Original research theorem proofs and any external formalizations are attributed to their authors, not newly GCL-certified. The historical source and proof-review limitations recorded in the return remain applicable.

What remains

Verify direct convolution and cumulative sum fixtures, source-lock Erdős–Fuchs and Montgomery–Vaughan exact asymptotic theorem assumptions (A infinite/finite, positive integers and error), and articulate why an O(1) error would violate the proven lower fluctuation. Do not present elementary examples as an independent proof of universal impossibility.

Sources and claim boundaries

Maintained #763; authenticated source return. Historic primary proofs, external Lean and deployed browser MathJax not fully audited. no independent theorem proof certification.

Catalogue and evidence provenance

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