Problem 187

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$ .

Source: erdosproblems.com/187

Additive combinatorics
Ramsey theory
Arithmetic progressions

Wiki page

Status

Open

No claim settles this problem.

Open: the site labels the problem OPEN (page last edited 4 April 2026). The only results on the exact question are upper bounds; the best is Beck's theorem (J. Combin. Theory Ser. A 29 (1980), 376--379, refereed), which gives, for every $\varepsilon>0$ , a 2-coloring under which $F(d)\le(1+\varepsilon)\log_2d$ for all large $d$ , so the best $f$ satisfies $f(d)\le(1+o(1))\log_2d$ ; it is an accepted partial claim on Beck's claim page (1980). Erdős's earlier bound $f(d)<cd$ (1973) is a pending partial claim on his claim page (Erdős, 1973), superseded by Beck's. In the other direction only the growth that van der Waerden's theorem gives is known: Erdős's "Van der Waerden's theorem certainly implies that $f(d)\to\infty$ " (1973), which a diagonal choice of the multiple turns into the qualifying $f(d)=\max\{L:W(L)^2\le d\}$ , $W(L)$ the two-color van der Waerden number (under What is known), a function tending to infinity only as slowly as the inverse of the van der Waerden numbers; and "no lower bound for $l(d)$ is in sight" (1980), "we currently have no usable lower bound for $h(d)$ " (1979, 1980). No source proving a lower bound of usable size, or improving Beck's upper bound, was found in the search whose scope the Current assessment records; this is a bounded negative finding, not a certificate of openness. The sources disagree on the strength of the unpublished Petruska–Szemerédi result, recorded below and not resolved.

Be80: J. Beck, A remark concerning arithmetic progressions. J. Combin. Theory Ser. A 29 (1980), no. 3, 376--379, DOI 10.1016/0097-3165(80)90035-7 (received May 21, 1980; issue dated November 1980 in the Crossref record). The Theorem on p. 376, Lemmas 1--3 on pp. 377--378. Library home: Beck 1980.
Er73: P. Erdős, Problems and results on combinatorial number theory. A Survey of Combinatorial Theory (Fort Collins, 1971), North-Holland (1973), 117--138; Section 2, printed p. 121. Library home: Erdos 1973.
Er80: P. Erdős, A survey of problems in combinatorial number theory. Ann. Discrete Math. 6 (1980), 89--115; printed pp. 92--93. Library home: Erdos 1980.
ErGr79: P. Erdős and R. L. Graham, Old and new problems and results in combinatorial number theory: van der Waerden's theorem and related topics. Enseign. Math. (2) 25 (1979), 325--344; printed p. 333. Library home: Erdős and Graham 1979.
ErGr80: P. Erdős and R. L. Graham, Old and new problems and results in combinatorial number theory. Monographies de L'Enseignement Mathématique 28 (1980); printed p. 17, the same passage as [ErGr79] p. 333. Library home: Erdős and Graham 1980.
BrLa99: T. C. Brown and B. M. Landman, Monochromatic arithmetic progressions with large differences. Bull. Austral. Math. Soc. 60 (1999), 21--35; an adjacent variant, not progress (below). Library home: Brown and Landman 1999.
Er76: P. Erdős, Problems and results on combinatorial number theory II. J. Indian Math. Soc. (N.S.) 40 (1976), 285--298 (received April 25, 1975); Beck's reference [2] for Cohen's question; the Cohen passage on printed pp. 289--290. Library home: Erdős 1976.
Sp77: J. Spencer, Asymptotic lower bounds for Ramsey functions. Discrete Math. 20 (1977), no. 1, 69--76, DOI 10.1016/0012-365X(77)90044-9 (Beck's reference for his Lemma 2, dated 1976 in his list; the running head reads 1977). Theorem 1.1, printed p. 70, the local lemma Beck quotes as his Lemma 2. Library home: Spencer 1977; paged at Spencer 1977, Theorem 1.1 (Lovász). - Not held: G. Petruska and E. Szemerédi, the unpublished result credited on the pages above.

Problem 187

Status

Proof claims

Discussion