Problem Statement
Let $h(N)$ be the smallest $k$ such that $\{1,\ldots,N\}$ can be coloured with $k$ colours so that every four-term arithmetic progression must contain at least three distinct colours. Estimate $h(N)$.
Categories:
Additive Combinatorics Arithmetic Progressions
Progress
Investigated by Erdős and Freud. This has been discussed on MathOverflow, where LeechLattice shows\[h(N) \ll N^{2/3}.\]In the comments of this site Hunter improves this to\[h(N) \ll N^{\frac{\log 3}{\log 22}+o(1)}\](note $\frac{\log 3}{\log 22}\approx 0.355$).The observation of Zach Hunter in that question coupled with recent progress on the size of subsets without three-term arithmetic progression (see [BlSi23] which improves slightly on the bounds due to Kelley and Meka [KeMe23]) imply that\[h(N) \gg \exp(c(\log N)^{1/9})\]for some $c>0$.
Source: erdosproblems.com/160 | Last verified: January 13, 2026