Van der Waerden numbers, lower bounds by explicit colourings

# Van der Waerden numbers: lower bounds by explicit colourings ## Goal The van der Waerden number `W(r, k)` is the least `n` such that every `r`-colouring of `{1, ..., n}` contains a monochromatic `k`-term arithmetic progression `a, a+d, ..., a+(k-1)d` (`d ≥ 1`). Only seven non-trivial values are known (`W(2,3..6) = 9, 35, 178, 1132`, `W(3,3) = 27`, `W(3,4) = 293`, `W(4,3) = 76`). For every other pair the only handle is a *certificate*: an `r`-colouring of `{1, ..., N}` with no monochromatic `k`-AP proves `W(r, k) > N`. This pack scores such certificates for thirteen open pairs against the longest ones known. `colouring.py` exposes colouring(r: int, k: int, time_budget: float, seed: int) -> list[int] returning a list of Python ints in `range(r)`; entry `i` is the colour of the integer `i + 1`. Its length `N` is what you are maximising. Instances are labelled `r-k`: | label | r | k | record N | |---|---|---|---| | `2-7` | 2 | 7 | 3703 | | `2-8` | 2 | 8 | 11495 | | `2-9` | 2 | 9 | 41265 | | `2-10` | 2 | 10 | 103474 | | `3-5` | 3 | 5 | 2173 | | `3-6` | 3 | 6 | 11191 | | `3-7` | 3 | 7 | 48811 | | `4-4` | 4 | 4 | 1048 | | `4-5` | 4 | 5 | 17705 | | `5-3` | 5 | 3 | 170 | | `5-4` | 5 | 4 | 2254 | | `6-3` | 6 | 3 | 223 | | `6-4` | 6 | 4 | 9778 | ## Metric metric = mean over instances of N(instance) / record(instance) The eval checks every arithmetic progression exactly (colour classes as bitmasks: a class contains a `k`-AP of difference `d` iff `B & (B >> d) & ... & (B >> (k-1)d)` is non-zero; a few hundred milliseconds even at `N = 200 000`). A single monochromatic `k`-AP fails the run (`wrong_answer`, the progression is named). Entries that are not ints in `range(r)` fail the run. A list longer than `2 × record` is refused rather than checked. Anything above 1.0 on an instance is a new lower bound for that `W(r, k)` and is flagged in `records_beaten`. `ZT_EVAL_SEED` only changes the `seed` handed to your solver; the instance set is fixed. ## Records `N` is the length of the longest published certificate, i.e. the best-known lower bound minus one (`W(r, k) > N`). None of the thirteen values is known to be optimal. Sources: J. Rabung, "Some progression-free partitions constructed using Folkman's method", Canad. Math. Bull. 22 (1979); P. Herwig, M. Heule, M. van Lambalgen, H. van Maaren, "A new method to construct lower bounds for van der Waerden numbers", EJC 14 (2007) R6; J. Rabung, M. Lotts, "Improving the use of cyclic zippers in finding lower bounds for van der Waerden numbers", EJC 19(2) (2012) P35, Table 1; M. Heule, "Avoiding triples in arithmetic progression", J. Comb. 8 (2017), Table 7 and github.com/marijnheule/vdWaerden; D. Monroe, "New lower bounds for van der Waerden numbers using distributed computing", JCMCC 128 (2025), Table 1 (all primes below 950 million checked for Rabung's method, no change to these cells). | label | record | construction | source | |---|---|---|---| | `2-7` | 3703 | power residues mod `p = 617`, `6p + 1` | Rabung 1979 | | `2-8` | 11495 | cyclic zipper of `p = 821` (period 1642) | Herwig et al. 2007 | | `2-9` | 41265 | cyclic zipper of `p = 2579` (period 5158) | Herwig et al. 2007 | | `2-10` | 103474 | power residues mod `p = 11497`, `9p + 1` | Rabung–Lotts 2012 | | `3-5` | 2173 | SAT with pre-partitioning, period 543 | Heule 2009/2017 | | `3-6` | 11191 | SAT with pre-partitioning, period 2238 | Heule 2009/2017 | | `3-7` | 48811 | listed as prior work in Rabung–Lotts 2012 (Heule's van der Waerden web page, 2011); Heule 2017 prints its own period-7309 certificate for 43855 | Heule 2011 | | `4-4` | 1048 | power residues mod `p = 349`, `3p + 1` | Rabung 1979 | | `4-5` | 17705 | cyclic zipper of `p = 2213` (period 4426) | Herwig et al. 2007 | | `5-3` | 170 | SAT with internal symmetry, period 85 | Heule 2017 | | `5-4` | 2254 | period 751 | Rabung 1979 | | `6-3` | 223 | SAT with internal symmetry, period 111 | Heule 2017 (Wikipedia's table shows `> 225` for this cell without a citation; no such certificate could be located, so 223 is used) | | `6-4` | 9778 | period 3259 | Rabung 1979 | Wikipedia's table (Sept 2026) agrees with every other row. Much larger `k` (`W(2,11) > 193 941`, `W(3,8) > 238 400`, Monroe's four-colour bounds in the millions) is deliberately left out: those certificates come from the same prime scans and would only reward copying a prime. ## Constraints - Standard library only. No numpy, no scipy. The eval rejects other imports. - Respect `time_budget` (seconds, per call). The eval fails a call that runs more than 25 % over. - Deterministic given `seed`: use `random.Random(seed)`. ## Iterating - `ZT_EVAL_INSTANCES=2-7,4-4` restricts the eval to a subset of labels (default: all thirteen). - `ZT_EVAL_PER_INSTANCE_SECONDS=2` shrinks the per-instance budget (default 6; the full eval takes about 90 s, verification included). - `ZT_EVAL_SEED` only changes the `seed` handed to your solver. ## Ideas that are known to matter (check the journal before repeating one) - Rabung's construction (the baseline): for a prime `p` and primitive root `g`, colour `x` by `log_g(x) mod r`. Multiplying an AP by a unit permutes the colours, so the colouring of `[0, (k-1)p]` that repeats the pattern mod `p` is a certificate iff two cheap conditions on the pattern hold (no run of `k` equal colours in `1..p-1`, and no "run through 0"). Scanning primes reproduces every record that came from this method (`2-7`, `2-10`, `4-4`, `5-4`, `6-4`) in seconds. - Cyclic zipping (Herwig et al.; Rabung–Lotts give the arithmetic): interleave a cyclic certificate of period `p` with a shifted copy of itself to get period `2p`, then repeat `k-1` times. This is where `2-8`, `2-9`, `4-5` come from, and the zipped colouring can be checked in linear time. - Heule's "pre-partitioning": a period-`m` cyclic certificate is forced to satisfy an extra symmetry (`x → x + m/q` shifts the colour by a fixed amount) and then found by SAT. Every `3-5`, `3-6`, `5-3`, `6-3` record has this shape; a pure-Python local search (WalkSAT on the AP clauses of one period, with the symmetry baked in) is the natural analogue. - Extend a good cyclic certificate at both ends: the `+1` in `(k-1)p + 1` comes from colouring the multiples of `p`; check whether a few more integers can be appended before the first violation. - The checker is bitset based; use the same trick inside your search so that one AP test costs `O(N/(k-1))` big-int operations instead of `O(N²)`. Write one honest line in `NOTES.md`: the idea, and which instance it helped. Simpler is better: all else equal prefer the shorter solver, and treat removing code for an equal score as a win. Log every experiment, including discards, in your results.tsv.