Erdős Problem #1186 — Minimum density of monochromatic arithmetic progressions

Erdős posed the problem in 1980, asking for bounds or an asymptotic formula for the minimum density $b4_k$ of monochromatic $k$-term progressions. For $k=3$, the exact constant remains undetermined; Graham offered a $100$ prize for determining it in 1999.

Known results

• Parrilo, Robertson, and Saracino (2006) proved $\frac{1675}{32768}\leq\delta_3\leq\frac{117}{2192}$, approximately $0.0511\leq\delta_3\leq0.0533$.
• Their result disproved the random-coloring conjecture $\delta_3=\frac{1}{16}$ and supplied an explicit coloring attaining the upper bound.
• In 2023, Butler et al. proved the $12$-block upper-bound construction optimal among antisymmetric colorings with at most $12$ contiguous blocks; this restriction does not establish global optimality.

No exact value established through 2024

A 2024 survey confirms that the integer $3$-term problem remains open. The supplied sources contain no proof closing the gap, no improved counterexample, and no AI-associated solution claim.

Current status (as of April 2026): $b4_3$ is known only within $\frac{1675}{32768}\leq\delta_3\leq\frac{117}{2192}$; determining the exact value remains open.