Erdős #187 · additive combinatorics / ramsey theory

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). In [Er80] he states that Petruska and Szemerédi have proved that $f(d) \ll d^{1/2}$, and expected $f(d)\leq d^{o(1)}$.

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.

The source labels this entry OPEN in the 2026-09-08 snapshot. Editorial progress notes are reproduced as source commentary, not independently verified results. Prize amounts and Lean badges at the source are not local awards or verification.