Wiki
Wiki

Research notes on every problem, and a library of the papers behind them. Built from the open erdos repository.

Updated


Claim. A sequence AA of positive integers is rr-Ramsey complete if, however it is split into rr classes, every sufficiently large integer is a sum of distinct terms from one class. Conlon, Fox and Pham prove (Theorem 1.2, p. 4) that for every degree kk there is a constant C(k)C(k) such that, for every polynomial PP of degree kk whose sequence (P(m))m≥1(P(m))_{m\ge1} is complete and every r≥2r\ge2, that sequence contains an rr-Ramsey complete subsequence AA with ∣A∩[n]∣≤C(k)rlog⁡2n|A\cap[n]|\le C(k)r\log^2n for all nn. At P(x)=x2P(x)=x^2 and r=2r=2 this gives a 2-Ramsey complete subsequence of the squares, and a sequence containing a 2-Ramsey complete subsequence is itself 2-Ramsey complete: any 2-coloring of the squares restricts to the subsequence, whose monochromatic sums of distinct terms are monochromatic sums of distinct squares. So the squares are Ramsey 2-complete, which answers Problem 843 in the affirmative. The theorem's hypothesis, that the squares form a complete sequence, is the classical fact that every sufficiently large integer is a sum of distinct squares; the paper's p. 4 states Graham's criterion for a polynomial sequence to be complete, which x2x^2 satisfies. The library card is Conlon, Fox and Pham 2021, whose Bears-on entry for this problem records the specialization.

Burr's unpublished proof. In Erdős 1995, item 11 of Part I (typescript p. 7), Erdős reports that Burr had a proof that the kk-th powers are Ramsey rr-complete for every kk and rr; the proof was never published, and the paper's p. 4 says its theorem subsumes that result. With no manuscript, Burr's proof has no claim page of its own; the problem's standing rests on the published argument above.

Acceptance. The site's curator, Thomas Bloom, labels the problem proved and credits the stronger result to Conlon, Fox and Pham in the page's commentary, which is the reviewed evidence. The paper is an arXiv preprint: its arXiv record lists no journal reference and no published version is recorded, so there is no refereed evidence. No formalization is on record; the community database lists the problem as unformalized.

Scope. The claim covers the problem's question for the squares and, by the same theorem, the kk-th powers for every k≥2k\ge2 and every number rr of colors, the variant the site's commentary mentions. The constant C(k)C(k) is not made explicit in the statement.