Bound $\delta_k$, the guaranteed density of monochromatic $k$-term APs in any 2-colouring (Erdős #1186)
Statement
Let $\delta_k$ be the optimal constant such that in any $2$-colouring of $\{1,\ldots,n\}$ there exist at least $(\delta_k+o(1))n^2$ monochromatic $k$-term arithmetic progressions. (A progression is monochromatic if all of its terms receive the same colour; the count runs over all $k$-term arithmetic progressions contained in $\{1,\ldots,n\}$, of which there are $\asymp n^2$.) Give reasonable bounds — or even an asymptotic formula — for $\delta_k$.
Acceptance. FULLY RESOLVES: a complete proof of an asymptotic formula for $\delta_k$ (exact values for all $k$, or the asymptotic behaviour as $k\to\infty$), or an exact determination of $\delta_3$ closing the Parrilo–Robertson–Saracino gap — machine-checkable (Lean/Coq) preferred, otherwise a full written proof with all steps. ADVANCES: strictly improve any bound stated in the background — the lower or upper bound on $\delta_3$, either bound on $\tilde{\delta}_4$, or the general upper bound $\frac{1}{(k-1)2^k}$ — with a proof or a reproducible certificate: for upper bounds, an explicit colouring family plus an exactly-verified monochromatic-AP count; for lower bounds, an LP/SDP/flag-algebra certificate in exact rational arithmetic together with independent verification code. Deliver the proof file, or the colouring/certificate plus the verification code.
Background
Posed by Erdős [Er80, p.93], who suggested 'perhaps one can get an asymptotic formula' for $\delta_k$ (the site curator notes this now seems unlikely); listed as open on erdosproblems.com/1186 (fetched 2026-07-13, status 'open', tagged 'additive combinatorics | arithmetic progressions'). Van der Waerden's theorem forces $\delta_k\gg_k 1$, while a uniformly random colouring gives the upper bound $\delta_k\leq \frac{1}{(k-1)2^{k}}$. For $k=3$ the state of the art is due to Parrilo, Robertson, and Saracino [PRS08]: $0.0511\approx\frac{1675}{32768}\leq\delta_3\leq\frac{117}{2192}\approx 0.0533$; they conjecture the upper bound is the true value, and report that Graham offered \$100 in 1999 for determining $\delta_3$ exactly. The finite-field analogue $\tilde{\delta}_k$ (2-colourings of $\mathbb{F}_p$) is cleaner: $\tilde{\delta}_3=1/8$ exactly (see Wolf [Wo10]), a random colouring gives $\tilde{\delta}_k\leq 2^{-k}$, and for $k=4$ the record is $\frac{7}{192}\leq\tilde{\delta}_4\leq\frac{17}{300}$, proved by Lu and Peng [LuPe12], improving earlier bounds of Wolf [Wo10] and Cameron–Cilleruelo–Serra [CCS07]. The attacker's tools: structured extremal-colouring search (block/periodic colourings with exact rational AP-counting) to push the upper bounds on $\delta_3$ and $\tilde{\delta}_4$, and LP/SDP or flag-algebra-style counting certificates, verified in exact arithmetic, to push the lower bounds.
References
| Ref | Source | Type |
|---|---|---|
| REF-01 | Erdős Problem #1186 (T. F. Bloom) | website |
Investigations · 0
No published investigations yet. This problem is unclaimed territory.