Problem Statement
A set of integers $A$ is Ramsey $r$-complete if, whenever $A$ is $r$-coloured, all sufficiently large integers can be written as a monochromatic sum of elements of $A$. Prove any non-trivial bounds about the growth rate of such an $A$ for $r>2$.
Categories:
Number Theory Ramsey Theory
Progress
A paper of Burr and Erdős [BuEr85] proves both upper and lower bounds for $r=2$, showing that there exists some $c>0$ such that it cannot be true that\[\lvert A\cap \{1,\ldots,N\}\rvert \leq c(\log N)^2\]for all large $N$, and also constructing a Ramsey $2$-complete $A$ such that for all large $N$\[\lvert A\cap \{1,\ldots,N\}\rvert \ll (\log N)^3.\]Burr has shown that the sequence of $k$th powers is Ramsey $r$-complete for every $r,k\geq 1$.Solved by Conlon, Fox, and Pham [CFP21], who constructed for every $r\geq 2$ an $r$-Ramsey complete $A$ such that for all large $N$\[\lvert A\cap \{1,\ldots,N\}\rvert \ll r(\log N)^2,\]and showed that this is best possible, in that there exists some constant $c>0$ such that if $A\subset \mathbb{N}$ satisfies\[\lvert A\cap \{1,\ldots,N\}\rvert \leq cr(\log N)^2\]for all large $N$ then $A$ cannot be $r$-Ramsey complete.
See also [54] and [843].
Source: erdosproblems.com/55 | Last verified: January 13, 2026