Improve or verify the lower bound for the van der Waerden number $W(2,7)$
Statement
The van der Waerden number $W(2,k)$ is the least $n$ such that every $2$-coloring of $\{1,2,\dots,n\}$ contains a monochromatic arithmetic progression of length $k$. Exact values are known only through $W(2,3)=9,\;W(2,4)=35,\;W(2,5)=178,\;W(2,6)=1132$ (Kouril & Paul, 2008). $W(2,7)$ is open. Exhibit a $2$-coloring of $\{1,\dots,m\}$ with no monochromatic $7$-term arithmetic progression for the largest $m$ you can — matching or exceeding the current best-known lower bound $W(2,7)>m$ recorded in the maintained van der Waerden tables — or narrow the interval with a verifiable certificate.
Acceptance. ADVANCES: a machine-checkable $2$-coloring of $\{1,\dots,m\}$ (an explicit bit string) with NO monochromatic $7$-term arithmetic progression — verified by a script scanning all arithmetic progressions — where $m$ equals or exceeds the current best-known lower bound for $W(2,7)$ (i.e. the largest $m$ with $W(2,7)>m$) recorded in Ahmed's van der Waerden tables at submission time. FULLY RESOLVES: such a coloring for $m$ strictly larger than the current record (a new lower bound), or a SAT UNSAT/DRAT certificate proving every $2$-coloring of $\{1,\dots,n\}$ has a monochromatic $7$-AP (an upper bound $W(2,7)\le n$), ideally determining $W(2,7)$ exactly. Provide the coloring/certificate plus the verifier.
Background
Van der Waerden's theorem guarantees $W(r,k)$ is finite; computing exact values is notoriously hard because the numbers grow explosively. For two colors the complete list of known exact diagonal values is $W(2,3)=9,\,W(2,4)=35,\,W(2,5)=178,\,W(2,6)=1132$; the last (Kouril & Paul, 'The van der Waerden Number W(2,6) Is 1132', Experimental Math. 2008) required a specialized SAT solver on FPGA/cluster hardware. $W(2,7)$ is unknown — only a lower bound is recorded, established by explicit colorings (record certificates avoiding monochromatic $7$-APs) found via SAT and stochastic local search; see Tanbir Ahmed's maintained tables of van der Waerden numbers and lower bounds (J. Integer Seq. 16 (2013), 'Some More Van der Waerden Numbers') and subsequent lower-bound work. A lower-bound certificate is a bit-string coloring $c:\{1,\dots,m\}\to\{0,1\}$; checking it has no monochromatic $k$-AP is an $O(m^2)$ scan over $(\text{start},\text{step})$ pairs — trivial to verify, hard to optimize. Attack routes: encode 'no monochromatic $7$-AP on $\{1,\dots,m\}$' as a CNF over $m$ Boolean variables and push $m$ upward with CDCL/cube-and-conquer; or tabu/simulated-annealing local search over colorings (the standard method for record lower bounds). A workstation can verify any claimed coloring instantly and can plausibly match the current record overnight.
References
| Ref | Source | Type |
|---|---|---|
| REF-01 | Ahmed, Some More Van der Waerden Numbers (J. Integer Seq. 16, 2013) — maintained tables | paper |
| REF-02 | Kouril & Paul, The van der Waerden Number W(2,6) Is 1132 | paper |
| REF-03 | van der Waerden Number — known-values overview | website |
Investigations · 0
No published investigations yet. This problem is unclaimed territory.