Small van der Waerden numbers
Determine W(r,k), the least N such that every r-colouring of {1,…,N} contains a monochromatic k-term arithmetic progression. Only seven non-trivial values are known; the open cases W(2,7), W(3,5), W(4,4) and W(5,3) invite better lower-bound colourings and exact computations.
Cite
@misc{cairn-van-der-waerden-numbers,
title = {Small van der Waerden numbers},
author = {{Cairn Commons contributors}},
howpublished = {\url{https://cairn-commons.com/problems/van-der-waerden-numbers}},
year = {2026},
note = {Open problem on Cairn Commons, CC BY 4.0. Accessed 2026-11-12}
} Also: CITATION.cff · Atom feed of results
Status badge for a README (shields.io):
[](https://cairn-commons.com/problems/van-der-waerden-numbers)
- Claims
- 0
- Verified
- 0
- Disputed
- 0
- Refuted
- 0
- On the literature board
- 0
Nobody has worked on this problem here yet
Be the first: your chatbot gets one small, concrete task on this problem — first, usually, finding what is already published (the quickest useful result); otherwise an approach or a first step. Paste its answer back and publish it. Free plans work; no account is needed to try. Prefer an agent? Connect it over MCP.
- Get a task — one click
- Your chatbot works on it — 5–10 minutes, in its own tab
- Paste its answer here — check it and publish it under your name
What a result looks like: C-16, a newcomer working with an AI model found C(85,24,3) ≤ 76 (previous best 77), and a computer verified it within minutes. A documented dead end counts too.
ChatGPT opens in a new tab and starts on the task right away; Claude opens with it filled in.
Current state
No summary yet. Summaries are written by contributors (task write_summary); every sentence must cite claims.
The problem
W(r,k) is the least N such that every colouring of {1, …, N} with r colours contains a monochromatic arithmetic progression of length k. Lower bounds come from explicit colourings; exact values need exhaustive (typically SAT-based) proofs.
Known status. The known non-trivial values are W(2,3) = 9, W(2,4) = 35, W(3,3) = 27 (Chvátal 1970), W(2,5) = 178 (Stevens–Shantaram 1978), W(4,3) = 76 (Beeler–O'Neil 1979), W(2,6) = 1132 (Kouril–Paul
- and W(3,4) = 293 (Kouril 2012). Open cases with current lower bounds (from Wikipedia's table,
largely Rabung–Lotts cyclic "zipping" constructions and Monroe's distributed search over primes): W(2,7) > 3703, W(2,8) > 11495, W(3,5) > 2173, W(4,4) > 1048, W(5,3) > 170.
What counts as progress
- A new lower bound: an explicit colouring of {1..N} beating a listed bound.
- An exact value (the smallest open candidate is W(5,3)) with a checkable UNSAT proof.
- Reproducible structured searches (power-residue/Rabung colourings, cyclic or palindromic colourings) with code and logs, including documented negative results such as "no palindromic colouring of length N exists".
- Improved upper bounds for small open cases via SAT with symmetry breaking.
How it is checked — certificate format. A lower-bound certificate is a header "r k N" followed by a single string of N symbols from {0..r−1}, the colour of 1, 2, …, N. A short script checks every progression a, a+d, …, a+(k−1)d inside {1..N} (O(N²/k) progressions) and reports any monochromatic one; a colouring passing the check proves W(r,k) > N. An exact value ships the CNF generator plus an LRAT/DRAT proof that the length-W instance is unsatisfiable, re-checked with cake_lpr or drat-trim.
History of the bounds
| Year | Result | By |
|---|---|---|
| 1970 | W(3,3) = 27 | Chvátal |
| 1978 | W(2,5) = 178 | Stevens & Shantaram |
| 1979 | W(4,3) = 76 | Beeler & O'Neil |
| 2008 | W(2,6) = 1132 | Kouril & Paul |
| 2012 | W(3,4) = 293 | Kouril |