Problem 1186

Let $\delta_k$ be such that in any $2$ -colouring of $\{1,\ldots,n\}$ there exist at least $(\delta_k+o(1))n^2$ many monochromatic $k$ -term arithmetic progressions. Give reasonable bounds (or even an asymptotic formula) for $\delta_k$ .

Source: erdosproblems.com/1186

Additive combinatorics
Arithmetic progressions

Wiki page

Status

Open

No claim settles this problem.

Open. The label is the site's (OPEN, page last edited 8 April 2026); its commentary records the bounds $1675/32768\le\delta_3\le117/2192$ of Parrilo, Robertson and Saracino, an accepted partial claim on its claim page (Parrilo, Robertson and Saracino, 2006). The site's proof-claims tab carries a partial proof claim by Carlos Toledo, submitted 2026-10-05 and produced with Claude (Anthropic), the system the claim names, that $\delta_3=117/2192$ , so that the upper bound of Parrilo, Robertson and Saracino is exact, by a computer-assisted proof closed with exact rational certificates; it is recorded as claimed on its claim page (Toledo, 2026).

CCS07: Cameron, Peter and Cilleruelo, Javier and Serra, Oriol, On monochromatic solutions of equations in groups. Rev. Mat. Iberoam. (2007), 385-395.
Er80: Erdős, Paul, A survey of problems in combinatorial number theory. Ann. Discrete Math. (1980), 89-115.
LuPe12: Lu, Linyuan and Peng, Xing, Monochromatic 4-term arithmetic progressions in 2-colorings of $\Bbb Z_n$ . J. Combin. Theory Ser. A (2012), 1048-1065.
PRS08: Parrilo, Pablo A. and Robertson, Aaron and Saracino, Dan, On the asymptotic minimum number of monochromatic 3-term arithmetic progressions. J. Combin. Theory Ser. A (2008), 185-192.
Wo10: Wolf, J., The minimum number of monochromatic 4-term progressions in $\Bbb Z_p$ . J. Comb. (2010), 53-68.

Problem 1186

Status

Proof claims

Discussion