Problem 328

../

claims/: The 3 claim pages of Problem 328, one per claimant's result; the problem's standing derives from them.

---

Statement. Suppose $A\subseteq\mathbb{N}$ and $C>0$ is such that $1_A\ast 1_A(n)\leq C$ for all $n\in\mathbb{N}$. Can $A$ be partitioned into $t$ many subsets $A_1,\ldots,A_t$ (where $t=t(C)$ depends only on $C$) such that $1_{A_i}\ast 1_{A_i}(n)<C$ for all $1\leq i\leq t$ and $n\in \mathbb{N}$?

Statement (corrected). Suppose $A\subseteq\mathbb{N}$ and $C>0$ is such that $f_A(n)\leq C$ for all $n\in\mathbb{N}$, where $f_B(n)$ denotes the number of solutions to $n=b+b'$ with $b,b'\in B$, $b<b'$. Can $A$ be partitioned into $t$ many subsets $A_1,\ldots,A_t$ (where $t=t(C)$ depends only on $C$) such that $f_{A_i}(n)<C$ for all $1\leq i\leq t$ and $n\in \mathbb{N}$?

Notes. The site writes $1_A\ast 1_A(n)$, which counts ordered pairs $(a,b)\in A\times A$ with $a+b=n$, $a=b$ included. Under that count the question fails trivially at $C=2$: two distinct elements $x<y$ of one part give the two ordered pairs $(x,y)$ and $(y,x)$ for $x+y$, so the bound $1_{A_i}\ast1_{A_i}(n)<2$ allows at most one element in each part, while an infinite Sidon set such as the powers of two has $1_A\ast1_A(n)\le2$ for every $n$ and cannot be split into finitely many parts of one element. The answer at $C=2$ then says nothing about the question Erdős and Newman asked; the case $C=1$ is answered no under every count, as in the poser's texts, and is not counted as a failure.

The change replaces $1_A\ast1_A(n)$ and $1_{A_i}\ast1_{A_i}(n)$ by $f_A(n)$ and $f_{A_i}(n)$ and inserts the definition of $f$; nothing else changes. The evidence is the poser's own statement of the question, which the site's wording renders. Erdős and Graham [ErGr80], printed p. 48 (Old and new problems and results in combinatorial number theory), write: "For the sequence $A = \{a_k\}$, let $f(n) = f_A(n)$ denote the number of solutions to $n = a_i + a_j$, $i < j$", and their question 7 (pp. 48--49), credited to Erdős and D. J. Newman, asks with that $f_A$ whether a set with $f_A(n)\le c$ for all $n$ can always be partitioned into $t=t(c)$ subsets $A_k$ with $f_{A_k}(n)<c$ for all $k$ and $n$. Erdős [Er80e], p. 43 (Some applications of Ramsey's theorem to additive number theory), also counts representations without regard to order: in the proof of his Theorem 1 a sum of four distinct terms $n_i+n_j+n_r+n_s$ has three representations, and $2n_i+n_r+n_s$ has one. That paper counts the sum $a+a$ once ($2n_i+2n_j$ has one representation), where [ErGr80] excludes it. The difference changes no recorded answer: every construction in [Er80e] reaches $C$ representations only through sums of two distinct elements, and [ErGr80], p. 49, reports that Nešetřil and Rödl answered the question as it states it in the negative for all $c$. No text of the poser counts ordered pairs, so the defect is the site's. The form follows the poser's statement of this question, not the results that settle it.

Results about the site's wording are credited here and count for nothing. AxiomMath published on 2026-06-18 a Lean 4 development generated by its prover AxiomProver (pinned file) that refutes the ordered-count statement at $C=2$ with the powers of two, with copies in the repository Jayyhk/erdos-lean (added 2026-06-22) and in Boris Alexeev's lean-proofs collection (added 2026-08-26). It answers the site's ordered count, not the corrected Statement's count of sums of two distinct elements, so it does not count toward the standing and its claim page is rejected.

Formulation. Erdős's own conjecture in [Er80e] is phrased through Sidon's $B_2^{(k)}$ sequences, sets in which every $n$ has at most $k$ representations and some $n$ has exactly $k$: for every $k$ there is a $B_2^{(k)}$ sequence such that every partition into finitely many parts has a part that is again a $B_2^{(k)}$ sequence. With $C=k$ that is the negative answer to the question under his count, which counts $a+a$ once. For every integer $C\geq 2$ the answer is no by [NeRo85], whose count also includes $a+a$, and [ErGr80], p. 49, reports the same answer for its count. Under either unordered count the answer is trivially no for $C=1$, since every part with two elements has a representation; for non-integer $C$ the hypothesis already gives fewer than $C$ representations of every $n$, and one part suffices.

Status. The site shows DISPROVED (LEAN), a label that describes the corrected Statement, and credits Nešetřil and Rödl with the negative answer for all $C$. The corrected Statement is disproved: the answer is no for every integer $C \geq 2$, even when $t$ may depend on $A$, by Nešetřil and Rödl [NeRo85], recorded on its claim page with its refereed and site evidence. Erdős [Er80e] had earlier answered no for $C = 2$, $3$, every $2^s$ and every $\tfrac12\binom{2s}{s}$, recorded on its own claim page. The label's Lean mark rests on AxiomMath's Lean refutation of the site's ordered-count wording, which the formal-conjectures statement shares; it gives no evidence for the corrected Statement, and its claim page is rejected.

Source. erdosproblems.com/328, accessed 2026-09-04. Cite as: T. F. Bloom, Erdős Problem #328, https://www.erdosproblems.com/328.

References.

• [Er80e] Erdős, P., Some applications of Ramsey's theorem to additive number theory. European J. Combin. (1980), 43-46.
• [ErGr80] Erdős, P. and Graham, R. L., Old and new problems and results in combinatorial number theory. Monographies de L'Enseignement Mathématique 28, Université de Genève (1980); pp. 48-49.
• [NeRo85] J. Nešetřil and V. Rödl, Two proofs in combinatorial number theory. Proc. Amer. Math. Soc. (1985), 185-188.

Formalization. Statement in formal-conjectures. Its theorem erdos_328 states the site's wording for natural numbers $C>0$, with a representation function sumRep that counts ordered pairs, and the file records the Jayyhk/erdos-lean copy of AxiomMath's development as its formal proof; it gives no evidence for the corrected Statement.

Progress

Not yet compiled.

Known Results

Not yet compiled.

Linked library material

These entries are derived from explicit links on library pages. They are navigation only and do not by themselves record mathematical progress.

• erdos_1980_applications_ramsey_s_theorem_additive_number
• erdos_1980_applications_ramsey_s_theorem_additive_number / conjecture_p44
• erdos_1980_applications_ramsey_s_theorem_additive_number / theorem_1
• erdos_1980_applications_ramsey_s_theorem_additive_number / theorem_1_prime