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.