All Random Solved Random Open
Find the best function $f(d)$ such that, in any 2-colouring of the integers, at least one colour class contains an arithmetic progression with common difference $d$ of length $f(d)$ for infinitely many $d$.
Originally asked by Cohen. Erdős observed that colouring according to whether $\{ \sqrt{2}n\}<1/2$ or not implies $f(d) \ll d$ (using the fact that $\|\sqrt{2}q\| \gg 1/q$ for all $q$, where $\|x\|$ is the distance to the nearest integer). Beck [Be80] has improved this using the probabilistic method, constructing a colouring that shows $f(d)\leq (1+o(1))\log_2 d$. Van der Waerden's theorem implies $f(d)\to \infty$ is necessary.