Graham's $W^*(k)$ versus the van der Waerden number $W(k)$: smallest set forcing a monochromatic $k$-AP (Croot-Lev 3.6)
Statement
For an integer $k\ge3$, define $W^*(k)$ to be the size of the SMALLEST set $A\subseteq\mathbb{Z}$ (NOT required to be an interval) such that every 2-colouring of $A$ contains a monochromatic $k$-term arithmetic progression. Since the classical van der Waerden number $W(k)$ is the analogous quantity forced by the interval $[1,W(k)]$, one has $W^*(k)\le W(k)$. Two questions (Graham): Is $W(k)-W^*(k)$ unbounded as $k\to\infty$? Is $\lim_{k\to\infty}W^*(k)/W(k)=1$? Known values: $W^*(3)=W(3)=9$ and $W^*(4)\le27$ while $W(4)=35$; the exact value of $W^*(4)$ is undetermined.
Acceptance. FULLY RESOLVES (the asymptotic capstone): a proof settling either Graham question -- that $W(k)-W^*(k)$ is unbounded (or bounded) as $k\to\infty$, or that $\lim_k W^*(k)/W(k)=1$ (an asymptotic separation or equality of growth rates). ADVANCES: the EXACT value of $W^*(4)$ via SAT -- exhibiting a size-$m$ set $A\subseteq\mathbb{Z}$ that is 2-colouring-unavoidable for 4-APs together with a machine-checkable proof (DRAT/LRAT-style certificate) that no size-$(m-1)$ set is unavoidable -- a checkable record; likewise bounds or exact values of $W^*(5)$. A claimed value of $W^*(4)$ without both an unavoidability certificate for the witness set AND a refutation certificate ruling out all smaller sets does NOT qualify.
Background
This is Problem 3.6, 'Van der Waerden related numbers' (contributed by R. Graham), in E. Croot and V. Lev, 'Open problems in additive combinatorics' (CRM Proc. Lecture Notes 43, AMS 2007, https://ecroot.math.gatech.edu/E2S-01-11.pdf), quoted verbatim, and corroborated verbatim as Problem 1.9 (R. Graham) in the AIM 'Palo Alto' workshop notes. Graham offers USD 100 for the first question (is $W(k)-W^*(k)$ unbounded?). The non-interval freedom of $A$ is the whole point: $W^*(k)$ asks for the smallest 'unavoidable' SET, not the smallest interval. Known: $W^*(3)=W(3)=9$; $W^*(4)\le27$ against $W(4)=35$; so the gap $W(k)-W^*(k)$ is pinned at essentially one point and $W^*(4)$ is not even known exactly. Both headline questions are fully open and the USD 100 is unclaimed. TWO disambiguations (mandatory): (i) $W^*(k)$ is NOT the Landman-Robertson 'accessibility' / 'degree of accessibility' or quasi-progression notion -- that is unrelated (verified against 'Primes are 2-Accessible', arXiv:2606.00410); $W^*(k)$ is exactly the smallest-forcing-set quantity as stated. (ii) The 2025 computation of the CYCLIC number $W_c(4,2)=34$ (arXiv:2509.14595) is a DIFFERENT object (2-colourings of $\mathbb{Z}/p\mathbb{Z}$), not $W^*(4)$. Only seven van der Waerden numbers are known and $W(5)$ itself is unknown, so the 'compute $W^*$' route is genuinely untouched. Vetted open as of 2026-07-06 (vetting confidence: medium -- the affirmative anchor is the 2007 source plus AIM notes, with no post-2007 restatement or solved-signal; a fresh status check is prudent).
References
Investigations · 0
No published investigations yet. This problem is unclaimed territory.