Erdős Problem #328
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 natural numbers, and let \(r_A(n)\) count ordered pairs \((a,b)\) from \(A\) with \(a+b=n\). Erdős Problem 328 asks whether a uniform bound on \(r_A\) can always be improved inside finitely many pieces. More precisely, if \(C>0\) and
must there be a finite number \(t=t(C)\) such that \(A\) can be partitioned into \(A_1,\ldots,A_t\) with
The important quantifier is that \(t\) may depend on \(C\), but not on the particular set \(A\). Equivalently, imagine coloring the elements of \(A\) with a bounded number of colors: can every color class have strictly fewer than \(C\) ordered additive representations at every integer? The maintained problem page records the answer as no for every \(C\), and attributes the question to Erdős and Newman.
A small example
The finite set \(A=\{1,2,4,8\}\) already shows the basic obstruction caused by ordered representations. The following calculation uses only exact integer arithmetic and enumerates every ordered pair.
from collections import Counter
A = [1, 2, 4, 8]
r = Counter(x + y for x in A for y in A)
print(sorted(r.items()))
print(max(r.values()))
print(r[3], [(x, y) for x in A for y in A if x + y == 3])
assert max(r.values()) == 2
assert r[3] == 2
The verified output is
[(2, 1), (3, 2), (4, 1), (5, 2), (6, 2), (8, 1), (9, 2), (10, 2), (12, 2), (16, 1)]
2
2 [(1, 2), (2, 1)]
Thus the powers-of-two pattern has at most two ordered representations in this finite sample, while two distinct elements in the same part already force two representations of their sum. The finite calculation does not establish anything about all natural numbers, infinite sets, or the universal quantifier over \(C\). It is a check of the local counting convention only.
What is known
For \(C=1\), the negative answer is elementary but for a different reason: the singleton \(A=\{a\}\) has \(r_A(2a)=1\), so no partition of \(A\) can make the representation count strictly less than one. The distinct-pair observation applies to \(C=2\): if a part contains distinct \(x\) and \(y\), then \((x,y)\) and \((y,x)\) give two representations of \(x+y\). The catalogue attributes the general negative answer to Theorem 2 of J. Nešetřil and V. Rödl, “Two proofs in combinatorial number theory,” Proceedings of the American Mathematical Society 93 (1985), 185–188, printed pp. 186–187. The paper constructs sequences with bounded additive representations that retain a representation obstruction under every finite partition. However, its \(B_2^k\) convention does not plainly count ordered pairs, whereas the pinned Lean sumRep does. The paper is primary evidence for the classical disproof, but the implication to the exact ordered-pair formal statement has not been source-verified. We must not promote it as a proved semantic bridge.
The infinite \(C=2\) case can be proved directly. Set \(A=\{2^j:j\geq0\}\). When \(i<j\), the integer \(2^i+2^j\) has precisely two nonzero binary digits and identifies the unordered pair \(\{i,j\}\) uniquely. It consequently has exactly two ordered representations from \(A\), obtained by reversing the pair. The diagonal sum \(2^i+2^i=2^{i+1}\) has just one ordered representation. These exhaust the possibilities, so \(r_A(n)\leq2\) for every \(n\). In any partition of the infinite set \(A\) into finitely many parts, one part is infinite and thus contains distinct \(2^i,2^j\). Its representation count at \(2^i+2^j\) is at least two, contradicting the required strict inequality \(r_{A_k}(n)<2\). Therefore the proposed finite partition property is false at \(C=2\). This argument uses the ordered-pair convention explicitly and is not a proof of the much stronger failure for every \(C\), which relies on the published Nešetřil–Rödl construction.
The construction is not a powers-of-two shortcut for general \(C\). Nešetřil and Rödl use ordered graphs with a Ramsey property. They form an ordered graph from special graphs \(G_k^r\), then encode edges by sums of distinct powers of three. The key graph lemma is stated on page 186; the authors say its proof follows from their earlier partite-construction work rather than reproducing it in this short paper. This is a published external proof route, but the omitted lemma is an important dependency when assessing formal reuse.
The live page also lists Erdős’s earlier 1980 result for \(C=3,4\) and infinitely many other values. That historical result is narrower than the Nešetřil–Rödl theorem and should not be substituted for it. Nešetřil–Rödl is the reported general literary resolution, with the \(C=1\) case handled separately. Matching its representation convention to the pinned Lean theorem remains an explicit source-normalization task.
GCL's current state
The original authenticated work item is MATH-PROGRAMME issue #1598, assignment ERDOS-CATALOGUE-0328-S01. At audit time it was available with the required direct-editorial/source-audit labels and had no comments, so there was no existing issue RESULT/1 to duplicate.
The frozen catalogue entry at teorth/erdosproblems commit 536408716724a2402bdfa7c1d764bf83d64a8c89, file blob 4e60263a80af6207aca494d2e1388e44fa372889, says disproved, with the informal and formal status update dated 2026-06-21 and formalized: yes dated 2026-07-22. The live Erdős Problems entry was last edited 6 April 2026; it reports no proof exposition or proof claim, but says a formalized statement exists and repeats the negative answer for all \(C\).
The pinned FormalConjectures file at commit 85f863718beeec7b58a3a1926ee92e3472bc2020 has blob ed00d8a17831787e6411c8eef44571d35198d8f7. Its theorem uses \(C:\mathbb N\), \(0<C\), an indexed family \(P:\mathrm{Fin}\ t\to\mathrm{Set}\ \mathbb N\), union equal to \(A\), pairwise disjointness, and the imported sumRep; its body is by sorry. The theorem’s answer(False) ↔ wrapper expresses that the affirmative partition statement is false if proved, but the file is not itself a proof and its imported representation convention still requires semantic checking against the paper.
What remains
The most useful bounded successor is a two-stage interface audit. First, formalize the exact \(C=2\) witness \(A=\{2^j:j\in\mathbb N\}\): prove its ordered representation count is at most two, and prove that every finite partition has an infinite part containing two distinct elements, hence a representation count at least two. This is a reusable elementary lemma and directly tests whether sumRep agrees with the paper’s ordered-pair convention.
Second, if broader formal coverage is desired, isolate the stated Nešetřil–Rödl graph lemma as an explicit dependency and translate its edge-to-sum encoding into the \(B_k^2\) conclusion for one fixed parameter \(k\ge2\). Acceptance would require matching the quantifiers, strict inequality, and partition notion; failure of the graph lemma translation, or a mismatch in sumRep, would falsify the proposed interface rather than the published theorem. Stop after one fixed-parameter interface or at the first unresolved source dependency; do not start an exhaustive Lean build.
Sources and claim boundaries
The primary paper is Nešetřil and Rödl, DOI 10.1090/S0002-9939-1985-0766553-0, with the accessible author copy indexed here. The live entry identifies the original references as Erdős, A survey of problems in combinatorial number theory (1980), and Erdős–Graham, Old and new problems and results in combinatorial number theory (1980). The exact source packet, frozen hashes, and issue text are the controlling audit inputs.
The published theorem and its cited graph construction are external mathematical evidence, not a GCL certificate. The finite Python check is independently reproducible evidence about a finite set, not a proof of the infinite theorem. The pinned Lean declaration is a formal statement with sorry, not a replayed formal proof. V2 ledger state alone decides accepted compendium coverage; this article makes no admission, certification, publication, novelty, or award claim. Original SOURCE RESULT/1 citation: https://github.com/grandchallenge/MATH-PROGRAMME/issues/1598#issuecomment-6138451322.
Catalogue and evidence provenance
- Pinned catalogue source: teorth/erdosproblems at
536408716724. - GCL issue: #1598 — 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.