Status
On this page
Status
Topics
Status
On this page
Status
Topics
Suppose and is such that for all . Can be partitioned into many subsets (where depends only on ) such that for all and ?
Suppose and is such that for all , where denotes the number of solutions to with , . Can be partitioned into many subsets (where depends only on ) such that for all and ?
Source: erdosproblems.com/328
An accepted solution exists. The statement is false.
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 . The corrected Statement is disproved: the answer is no for every integer , even when may depend on , by Nešetřil and Rödl [NeRo85], recorded on its claim page (Nešetřil and Rödl, 1985) with its refereed and site evidence. Erdős [Er80e] had earlier answered no for , , every and every , recorded on its own claim page (Erdős, 1980). 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 (AxiomMath, 2026) is rejected.
The site writes , which counts ordered pairs with , included. Under that count the question fails trivially at : two distinct elements of one part give the two ordered pairs and for , so the bound allows at most one element in each part, while an infinite Sidon set such as the powers of two has for every and cannot be split into finitely many parts of one element. The answer at then says nothing about the question Erdős and Newman asked; the case is answered no under every count, as in the poser's texts, and is not counted as a failure.
The change replaces and by and and inserts the definition of ; 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 , let denote the number of solutions to , ", and their question 7 (pp. 48--49), credited to Erdős and D. J. Newman, asks with that whether a set with for all can always be partitioned into subsets with for all and . 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 has three representations, and has one. That paper counts the sum once ( has one representation), where [ErGr80] excludes it. The difference changes no recorded answer: every construction in [Er80e] reaches 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 . 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 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 (AxiomMath, 2026)
is rejected.