Logo
All Random Solved Random Open
SOLVED
Is it true that, in any finite colouring of the integers, there must be two integers $x\neq y$ of the same colour such that $x+y$ is a square? What about a $k$th power?
A question of Roth, Erdős, Sárközy, and Sós [ESS89] (according to some reports, although in [Er80c] Erdős claims this arose in a conversation with Silverman in 1977). Erdős, Sárközy, and Sós [ESS89] proved this for $2$ or $3$ colours.

In other words, if $G$ is the infinite graph on $\mathbb{N}$ where we connect $m,n$ by an edge if and only if $n+m$ is a square, then is the chromatic number of $G$ equal to $\aleph_0$?

This is true, as proved by Khalfalah and Szemerédi [KhSz06], who in fact prove the general result with $x+y=z^2$ replaced by $x+y=f(z)$ for any non-constant $f(z)\in \mathbb{Z}[z]$ such that $2\mid f(z)$ for some $z\in \mathbb{Z}$.

See also [438].

Additional thanks to: Deepak Bal