Problem Statement
Let $H(k)$ be the smallest $N$ such that in any finite colouring of $\{1,\ldots,N\}$ (into any number of colours) there is always either a monochromatic $k$-term arithmetic progression or a rainbow arithmetic progression (i.e. all elements are different colours). Estimate $H(k)$. Is it true that\[H(k)^{1/k}/k \to \infty\]as $k\to\infty$?
Categories:
Additive Combinatorics Arithmetic Progressions
Progress
This type of problem belongs to 'canonical' Ramsey theory. The existence of $H(k)$ follows from Szemerédi's theorem, and it is easy to show that $H(k)^{1/k}\to\infty$.Source: erdosproblems.com/190 | Last verified: January 14, 2026