---

Claim. For every $\varepsilon>0$ there is a 2-coloring of the integers under which, for all $d$ large enough depending only on $\varepsilon$, no monochromatic arithmetic progression of common difference $d$ has more than $(1+\varepsilon)\log_2d$ terms. In the terms of Problem 187, a function $f$ that qualifies, one such that every 2-coloring has, for infinitely many $d$, a monochromatic progression of difference $d$ and length $f(d)$, must satisfy $f(d)\le(1+\varepsilon)\log_2d$ for infinitely many $d$, so the best $f$ is at most $(1+o(1))\log_2d$. The paper's single Theorem (printed p. 376) states the bound; the proof (pp. 377--379) reduces to a finite interval by compactness and 2-colors the set system of long progressions with small difference by Spencer's weighted form of the Lovász local lemma. The source is J. Beck, A remark concerning arithmetic progressions, J. Combin. Theory Ser. A 29 (1980), no. 3, 376--379; the result is on the theorem page of its library card. Beck remarks that the bound is best possible relative to the then-known upper bound $W(n)\le\log_2n$ for the two-color van der Waerden function, since any improvement would improve that bound; the remark is not an absolute optimality statement.

Covers. The upper bound $f(d)\le(1+o(1))\log_2d$ on the best $f$ alone. Not covered: any lower bound beyond $f(d)\to\infty$, which van der Waerden's theorem gives, and the determination of the best $f$, which the problem asks for. The earlier bound $f(d)<cd$ is Erdős's claim, which this result supersedes.

Depends on. Spencer's weighted local lemma (Theorem 1.1 of J. Spencer, Discrete Math. 20 (1977), 69--76), which the proof quotes as its Lemma 2; the rest of the argument is in the cited paper.

Acceptance. Refereed: the paper is the version of record in the Journal of Combinatorial Theory, Series A, a refereed journal, received May 21, 1980; the publisher's record dates the issue to November 1980 without a day, so this page is named by the first day of that month. The site's curator credits the bound to Beck in the problem's commentary, but the site labels the problem OPEN, so that credit is not acceptance of the problem and no reviewed evidence is listed. The corpus records no check of the proof.