How long a monochromatic AP with difference $d$ does every 2-colouring of the integers force? (Erdős #187)
Statement
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$. That is: determine the fastest-growing $f$ for which every $2$-colouring of $\mathbb{Z}$ admits infinitely many $d$ such that some colour class contains an arithmetic progression of length $f(d)$ with common difference exactly $d$.
Acceptance. FULLY RESOLVES: determine $f$ up to asymptotic order — prove a lower-bound theorem (every $2$-colouring of $\mathbb{Z}$ has infinitely many $d$ with a monochromatic progression of difference $d$ and length $\ge g(d)$) and exhibit a colouring with a matching upper-bound analysis, with $g$ and the cap of the same asymptotic order (e.g. establishing $f(d) = \Theta(\log d)$, or whatever the true order is). Machine-checkable proof preferred, else full written proof. ADVANCES: (a) any explicit unbounded lower-bound rate — a proof that some named $g(d) \to \infty$ works, since the background records unboundedness with no rate; (b) an improved upper bound — a colouring with proven cap asymptotically strictly below the $(1+o(1))\log_2 d$ stated in the background (e.g. constant $c<1$ in $c\log_2 d$), or an explicit (non-probabilistic) colouring certified to achieve $O(\log d)$; (c) reproducible finite-range computations: for initial segments $\{1,\ldots,N\}$, exact extremal values of the guaranteed monochromatic progression length per difference, with search code and exhaustiveness certificates, as evidence for the true rate. Deliver the proof file, or the colouring construction plus analysis, or the code plus certificates.
Background
Originally asked by Cohen; circulated by Erdős [Er73], Erdős–Graham [ErGr79], [Er80, p.93], [ErGr80, p.17]; listed as open on erdosproblems.com/187 (fetched 2026-07-13, status 'open', tagged 'additive combinatorics | ramsey theory | arithmetic progressions'). Lower frontier: van der Waerden's theorem forces the optimal $f$ to be unbounded, $f(d) \to \infty$, but no explicit growth rate is recorded on the page. Upper frontier (colourings that cap $f$): Erdős observed that colouring $n$ by whether $\{\sqrt{2}\,n\} < 1/2$ (fractional part) shows $f(d) \ll d$, using $\|\sqrt{2} q\| \gg 1/q$ where $\|x\|$ is the distance to the nearest integer; Erdős [Er80] reports that Petruska and Szemerédi improved this to $f(d) \ll d^{1/2}$, and Erdős expected $f(d) \le d^{o(1)}$; Beck [Be80] went much further with the probabilistic method, constructing a $2$-colouring showing $f(d) \le (1+o(1)) \log_2 d$. So the truth sits between 'unbounded, no known rate' and $\log_2 d$, and the natural conjecture is logarithmic order. Attacker's tools: on the upper side, derandomizing or sharpening Beck's colouring (a construction with certified analysis lowering the constant in $\log_2 d$); on the lower side, quantitative van der Waerden arguments to extract an explicit $g(d) \to \infty$; SAT/exhaustive computation over $2$-colourings of initial segments can chart the exact finite trade-offs and inform the conjectured rate.
References
| Ref | Source | Type |
|---|---|---|
| REF-01 | Erdős Problem #187 (T. F. Bloom) | website |
Investigations · 0
No published investigations yet. This problem is unclaimed territory.