{"id":"van-der-waerden-lower","name":"Van der Waerden numbers, lower bounds by explicit colourings","family":"additive-combinatorics","description":"An r-colouring of {1..N} with no monochromatic k-term arithmetic progression certifies W(r,k) > N. Thirteen open (r,k) pairs from (2,7) to (6,4), scored against the longest known certificates (Rabung, Herwig-Heule-van Lambalgen-van Maaren, Rabung-Lotts, Heule).","metric":"record_ratio","direction":"maximize","tolerance":0.1,"eval_timeout_seconds":240,"agent_timeout_seconds":1800,"mutable":["colouring.py"],"runtime":"python>=3.11, standard library only (math, random, itertools, functools, collections, heapq, time)","decomposable":true,"status":"active","captain":null,"parent_problem":null,"program_md":"# Van der Waerden numbers: lower bounds by explicit colourings\n\n## Goal\n\nThe van der Waerden number `W(r, k)` is the least `n` such that every `r`-colouring of `{1, ..., n}`\ncontains a monochromatic `k`-term arithmetic progression `a, a+d, ..., a+(k-1)d` (`d ≥ 1`). Only seven\nnon-trivial values are known (`W(2,3..6) = 9, 35, 178, 1132`, `W(3,3) = 27`, `W(3,4) = 293`,\n`W(4,3) = 76`). For every other pair the only handle is a *certificate*: an `r`-colouring of\n`{1, ..., N}` with no monochromatic `k`-AP proves `W(r, k) > N`. This pack scores such certificates\nfor thirteen open pairs against the longest ones known.\n\n`colouring.py` exposes\n\n    colouring(r: int, k: int, time_budget: float, seed: int) -> list[int]\n\nreturning a list of Python ints in `range(r)`; entry `i` is the colour of the integer `i + 1`. Its\nlength `N` is what you are maximising. Instances are labelled `r-k`:\n\n| label | r | k | record N |\n|---|---|---|---|\n| `2-7`  | 2 | 7  | 3703   |\n| `2-8`  | 2 | 8  | 11495  |\n| `2-9`  | 2 | 9  | 41265  |\n| `2-10` | 2 | 10 | 103474 |\n| `3-5`  | 3 | 5  | 2173   |\n| `3-6`  | 3 | 6  | 11191  |\n| `3-7`  | 3 | 7  | 48811  |\n| `4-4`  | 4 | 4  | 1048   |\n| `4-5`  | 4 | 5  | 17705  |\n| `5-3`  | 5 | 3  | 170    |\n| `5-4`  | 5 | 4  | 2254   |\n| `6-3`  | 6 | 3  | 223    |\n| `6-4`  | 6 | 4  | 9778   |\n\n## Metric\n\n    metric = mean over instances of  N(instance) / record(instance)\n\nThe eval checks every arithmetic progression exactly (colour classes as bitmasks: a class contains a\n`k`-AP of difference `d` iff `B & (B >> d) & ... & (B >> (k-1)d)` is non-zero; a few hundred\nmilliseconds even at `N = 200 000`). A single monochromatic `k`-AP fails the run (`wrong_answer`, the\nprogression is named). Entries that are not ints in `range(r)` fail the run. A list longer than\n`2 × record` is refused rather than checked. Anything above 1.0 on an instance is a new lower bound\nfor that `W(r, k)` and is flagged in `records_beaten`. `ZT_EVAL_SEED` only changes the `seed` handed\nto your solver; the instance set is fixed.\n\n## Records\n\n`N` is the length of the longest published certificate, i.e. the best-known lower bound minus one\n(`W(r, k) > N`). None of the thirteen values is known to be optimal. Sources: J. Rabung, \"Some\nprogression-free partitions constructed using Folkman's method\", Canad. Math. Bull. 22 (1979);\nP. Herwig, M. Heule, M. van Lambalgen, H. van Maaren, \"A new method to construct lower bounds for van\nder Waerden numbers\", EJC 14 (2007) R6; J. Rabung, M. Lotts, \"Improving the use of cyclic zippers in\nfinding lower bounds for van der Waerden numbers\", EJC 19(2) (2012) P35, Table 1; M. Heule, \"Avoiding\ntriples in arithmetic progression\", J. Comb. 8 (2017), Table 7 and github.com/marijnheule/vdWaerden;\nD. Monroe, \"New lower bounds for van der Waerden numbers using distributed computing\", JCMCC 128\n(2025), Table 1 (all primes below 950 million checked for Rabung's method, no change to these cells).\n\n| label | record | construction | source |\n|---|---|---|---|\n| `2-7`  | 3703   | power residues mod `p = 617`, `6p + 1` | Rabung 1979 |\n| `2-8`  | 11495  | cyclic zipper of `p = 821` (period 1642) | Herwig et al. 2007 |\n| `2-9`  | 41265  | cyclic zipper of `p = 2579` (period 5158) | Herwig et al. 2007 |\n| `2-10` | 103474 | power residues mod `p = 11497`, `9p + 1` | Rabung–Lotts 2012 |\n| `3-5`  | 2173   | SAT with pre-partitioning, period 543 | Heule 2009/2017 |\n| `3-6`  | 11191  | SAT with pre-partitioning, period 2238 | Heule 2009/2017 |\n| `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 |\n| `4-4`  | 1048   | power residues mod `p = 349`, `3p + 1` | Rabung 1979 |\n| `4-5`  | 17705  | cyclic zipper of `p = 2213` (period 4426) | Herwig et al. 2007 |\n| `5-3`  | 170    | SAT with internal symmetry, period 85 | Heule 2017 |\n| `5-4`  | 2254   | period 751 | Rabung 1979 |\n| `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) |\n| `6-4`  | 9778   | period 3259 | Rabung 1979 |\n\nWikipedia's table (Sept 2026) agrees with every other row. Much larger `k` (`W(2,11) > 193 941`,\n`W(3,8) > 238 400`, Monroe's four-colour bounds in the millions) is deliberately left out: those\ncertificates come from the same prime scans and would only reward copying a prime.\n\n## Constraints\n\n- Standard library only. No numpy, no scipy. The eval rejects other imports.\n- Respect `time_budget` (seconds, per call). The eval fails a call that runs more than 25 % over.\n- Deterministic given `seed`: use `random.Random(seed)`.\n\n## Iterating\n\n- `ZT_EVAL_INSTANCES=2-7,4-4` restricts the eval to a subset of labels (default: all thirteen).\n- `ZT_EVAL_PER_INSTANCE_SECONDS=2` shrinks the per-instance budget (default 6; the full eval takes\n  about 90 s, verification included).\n- `ZT_EVAL_SEED` only changes the `seed` handed to your solver.\n\n## Ideas that are known to matter (check the journal before repeating one)\n\n- Rabung's construction (the baseline): for a prime `p` and primitive root `g`, colour `x` by\n  `log_g(x) mod r`. Multiplying an AP by a unit permutes the colours, so the colouring of\n  `[0, (k-1)p]` that repeats the pattern mod `p` is a certificate iff two cheap conditions on the\n  pattern hold (no run of `k` equal colours in `1..p-1`, and no \"run through 0\"). Scanning primes\n  reproduces every record that came from this method (`2-7`, `2-10`, `4-4`, `5-4`, `6-4`) in seconds.\n- Cyclic zipping (Herwig et al.; Rabung–Lotts give the arithmetic): interleave a cyclic certificate of\n  period `p` with a shifted copy of itself to get period `2p`, then repeat `k-1` times. This is where\n  `2-8`, `2-9`, `4-5` come from, and the zipped colouring can be checked in linear time.\n- Heule's \"pre-partitioning\": a period-`m` cyclic certificate is forced to satisfy an extra symmetry\n  (`x → x + m/q` shifts the colour by a fixed amount) and then found by SAT. Every `3-5`, `3-6`,\n  `5-3`, `6-3` record has this shape; a pure-Python local search (WalkSAT on the AP clauses of one\n  period, with the symmetry baked in) is the natural analogue.\n- Extend a good cyclic certificate at both ends: the `+1` in `(k-1)p + 1` comes from colouring the\n  multiples of `p`; check whether a few more integers can be appended before the first violation.\n- The checker is bitset based; use the same trick inside your search so that one AP test costs\n  `O(N/(k-1))` big-int operations instead of `O(N²)`.\n\nWrite one honest line in `NOTES.md`: the idea, and which instance it helped.\n\nSimpler is better: all else equal prefer the shorter solver, and treat removing code for an\nequal score as a win. Log every experiment, including discards, in your results.tsv.\n","eval_py":"\"\"\"Eval for van-der-waerden-lower. Prints one JSON line: {\"metric\": record_ratio, ...}.\n\nEnv:\n  ZT_EVAL_SEED                   seed handed to colouring()\n  ZT_EVAL_PER_INSTANCE_SECONDS   time budget per instance (default 6)\n  ZT_EVAL_INSTANCES              comma-separated \"r-k\" labels (default: all thirteen)\n\"\"\"\n\nfrom __future__ import annotations\n\nimport ast\nimport json\nimport os\nimport random\nimport sys\nimport time\nfrom pathlib import Path\n\nSEED = os.environ.get(\"ZT_EVAL_SEED\", \"dev-seed\")\nBUDGET = float(os.environ.get(\"ZT_EVAL_PER_INSTANCE_SECONDS\", \"6\"))\nINSTANCES = [s.strip() for s in os.environ.get(\"ZT_EVAL_INSTANCES\", \"2-7,2-8,2-9,2-10,3-5,3-6,3-7,4-4,4-5,5-3,5-4,6-3,6-4\").split(\",\") if s.strip()]\nSTDLIB_ALLOW = {\"math\", \"random\", \"itertools\", \"functools\", \"collections\", \"heapq\", \"time\", \"sys\", \"typing\", \"operator\"}\nFORBIDDEN_NAMES = {\"__import__\", \"importlib\", \"builtins\", \"__builtins__\", \"open\", \"exec\", \"eval\", \"compile\",\n                   \"globals\", \"__loader__\", \"__spec__\", \"breakpoint\", \"input\", \"memoryview\", \"vars\"}\n\n# \"r-k\" -> N, the longest known r-colouring of [1, N] with no monochromatic k-term arithmetic\n# progression (so W(r, k) > N). Sources and status in program.md; none of these is proven optimal.\nRECORDS = {\n    \"2-7\": 3703, \"2-8\": 11495, \"2-9\": 41265, \"2-10\": 103474,\n    \"3-5\": 2173, \"3-6\": 11191, \"3-7\": 48811,\n    \"4-4\": 1048, \"4-5\": 17705,\n    \"5-3\": 170, \"5-4\": 2254,\n    \"6-3\": 223, \"6-4\": 9778,\n}\nCAP_FACTOR = 2  # a colouring longer than CAP_FACTOR * record is refused rather than checked\n\n\ndef fail(msg: str, kind: str = \"error\") -> None:\n    print(json.dumps({\"metric\": 0.0, \"error\": msg, \"kind\": kind}))\n    sys.exit(1)\n\n\ndef check_imports(path: Path) -> None:\n    try:\n        tree = ast.parse(path.read_text(encoding=\"utf-8\"))\n    except SyntaxError as e:\n        fail(f\"syntax error in pack.py: {e}\", \"compile_error\")\n    for node in ast.walk(tree):\n        names = []\n        if isinstance(node, ast.Import):\n            names = [a.name.split(\".\")[0] for a in node.names]\n        elif isinstance(node, ast.ImportFrom) and node.module:\n            names = [node.module.split(\".\")[0]]\n        for nm in names:\n            if nm not in STDLIB_ALLOW:\n                fail(f\"import of '{nm}' is not allowed (stdlib subset only: {sorted(STDLIB_ALLOW)})\", \"compile_error\")\n        # dynamic imports and raw file/process access are not part of the problem either\n        ident = node.id if isinstance(node, ast.Name) else node.attr if isinstance(node, ast.Attribute) else None\n        if ident in FORBIDDEN_NAMES:\n            fail(f\"use of '{ident}' is not allowed in a solver\", \"compile_error\")\n        if isinstance(node, ast.ImportFrom) and node.level:\n            fail(\"relative imports are not allowed in a solver\", \"compile_error\")\n\n\ndef validate(label: str, out, r: int, cap: int) -> list[int]:\n    if not isinstance(out, (list, tuple)):\n        fail(f\"colouring({label}) must return a list of colour indices, got {type(out).__name__}\", \"wrong_answer\")\n    if len(out) == 0:\n        fail(f\"colouring({label}) returned an empty list\", \"wrong_answer\")\n    if len(out) > cap:\n        fail(f\"colouring({label}) returned {len(out)} colours; refused, more than {CAP_FACTOR} x the record\", \"wrong_answer\")\n    seq = []\n    for x in out:\n        if type(x) is not int or not 0 <= x < r:\n            fail(f\"colouring({label}) returned a non-colour entry {x!r} (need ints in range({r}))\", \"wrong_answer\")\n        seq.append(x)\n    return seq\n\n\ndef mono_ap(seq: list[int], r: int, k: int):\n    \"\"\"Exact check. Returns (colour, a, d) of a monochromatic k-AP a, a+d, ..., a+(k-1)d in [1, N], or None.\n\n    Colour classes are bitmasks (bit x set iff x has that colour); a class contains a k-AP of\n    difference d iff  B & (B >> d) & ... & (B >> (k-1)d)  is non-zero. O(N/(k-1)) big-int ops per class.\n    \"\"\"\n    n = len(seq)\n    masks = [0] * r\n    for x, c in enumerate(seq, start=1):\n        masks[c] |= 1 << x\n    for colour, b in enumerate(masks):\n        if not b:\n            continue\n        for d in range(1, (n - 1) // (k - 1) + 1):\n            m = b\n            for i in range(1, k):\n                m &= b >> (i * d)\n                if not m:\n                    break\n            if m:\n                return colour, (m & -m).bit_length() - 1, d\n    return None\n\n\ndef main() -> None:\n    here = Path(__file__).parent\n    check_imports(here / \"colouring.py\")\n    sys.path.insert(0, str(here))\n    try:\n        import colouring as cand  # noqa: E402\n    except SystemExit:\n        raise\n    except Exception as e:\n        fail(f\"import colouring.py failed: {e!r}\", \"compile_error\")\n    if not hasattr(cand, \"colouring\"):\n        fail(\"colouring.py must define colouring(r, k, time_budget, seed)\", \"compile_error\")\n\n    seed_int = random.Random(f\"vdw|{SEED}\").getrandbits(32)\n    per, beaten = {}, []\n    for label in INSTANCES:\n        if label not in RECORDS:\n            fail(f\"no record for instance {label!r} (known: {sorted(RECORDS)})\", \"error\")\n        r, k = (int(x) for x in label.split(\"-\"))\n        record = RECORDS[label]\n        t0 = time.perf_counter()\n        try:\n            out = cand.colouring(r, k, BUDGET, seed_int)\n        except SystemExit:\n            raise\n        except Exception as e:\n            fail(f\"colouring({label}) raised {e!r}\", \"runtime_error\")\n        elapsed = time.perf_counter() - t0\n        if elapsed > 1.25 * BUDGET + 3:\n            fail(f\"colouring({label}) took {elapsed:.1f}s against a {BUDGET:.0f}s budget\", \"timeout\")\n        seq = validate(label, out, r, CAP_FACTOR * record)\n        bad = mono_ap(seq, r, k)\n        if bad is not None:\n            colour, a, d = bad\n            fail(f\"colouring({label}): monochromatic {k}-AP {a}, {a + d}, ..., {a + (k - 1) * d} in colour {colour}\", \"wrong_answer\")\n        n = len(seq)\n        per[label] = {\"r\": r, \"k\": k, \"N\": n, \"record\": record, \"ratio\": round(n / record, 6), \"seconds\": round(elapsed, 2)}\n        if n > record:\n            beaten.append(label)\n    metric = sum(v[\"ratio\"] for v in per.values()) / len(per)\n    print(json.dumps({\"metric\": round(metric, 6), \"per_instance\": per, \"records_beaten\": beaten}))\n\n\nif __name__ == \"__main__\":\n    main()\n","baseline":{"colouring.py":"\"\"\"Baseline: Rabung's power-residue colouring, scanning primes until the budget runs out. Beat it.\n\nFor a prime p and a primitive root g, colour x in [1, p-1] by (log_g x) mod r. Multiplying an AP by a\nunit mod p just shifts every colour, so the pattern repeated over [0, (k-1)p] (multiples of p coloured\nalternately) has no monochromatic k-AP as soon as two O(p) conditions hold (Rabung 1979; Rabung-Lotts\n2012): no run of k equal colours in 1..p-1, and no \"run through 0\". That is what is checked here; the\nfinal candidate is also verified exactly with bitsets before it is returned.\n\"\"\"\n\nimport random\nimport time\n\n\ndef _next_prime(p: int) -> int:\n    p += 1\n    while True:\n        if p % 2 and all(p % q for q in range(3, int(p ** 0.5) + 1, 2)):\n            return p\n        p += 1\n\n\ndef _primitive_root(p: int) -> int:\n    m, factors, q = p - 1, [], 2\n    while q * q <= m:\n        if m % q == 0:\n            factors.append(q)\n            while m % q == 0:\n                m //= q\n        q += 1\n    if m > 1:\n        factors.append(m)\n    for g in range(2, p):\n        if all(pow(g, (p - 1) // q, p) != 1 for q in factors):\n            return g\n    return 1\n\n\ndef _rabung(p: int, r: int, k: int, rng: random.Random):\n    \"\"\"Colouring of [0, (k-1)p] from the power classes mod p, or None if the pattern fails.\"\"\"\n    g = _primitive_root(p)\n    col = [0] * p\n    x = 1\n    for i in range(p - 1):\n        col[x] = i % r\n        x = x * g % p\n    # (a) no monochromatic run of k consecutive residues in 1..p-1\n    run = 1\n    for x in range(2, p):\n        run = run + 1 if col[x] == col[x - 1] else 1\n        if run >= k:\n            return None\n    # (b) an AP that passes through a multiple of p at index i covers residues -i..-1 and 1..k-1-i (scaled);\n    #     log(-1) = (p-1)/2 shifts the negative side, so those k-1 residues must not be one colour\n    h = ((p - 1) // 2) % r\n    for i in range(k):\n        seen = {(col[j] + h) % r for j in range(1, i + 1)} | {col[j] for j in range(1, k - i)}\n        if len(seen) <= 1:\n            return None\n    c0 = rng.randrange(r)\n    c1 = (c0 + 1 + rng.randrange(r - 1)) % r\n    out = []\n    for x in range((k - 1) * p + 1):\n        if x % p:\n            out.append(col[x % p])\n        else:\n            out.append(c0 if (x // p) % 2 == 0 else c1)\n    return out\n\n\ndef _has_mono_ap(seq, r, k) -> bool:\n    n = len(seq)\n    masks = [0] * r\n    for x, c in enumerate(seq):\n        masks[c] |= 1 << x\n    for b in masks:\n        for d in range(1, (n - 1) // (k - 1) + 1):\n            m = b\n            for i in range(1, k):\n                m &= b >> (i * d)\n                if not m:\n                    break\n            if m:\n                return True\n    return False\n\n\ndef colouring(r: int, k: int, time_budget: float, seed: int) -> list[int]:\n    rng = random.Random(seed)\n    deadline = time.perf_counter() + 0.85 * time_budget\n    best = [0] * (k - 1)  # [1, k-1] holds no k-term AP at all\n    p = max(k, 2)\n    while time.perf_counter() < deadline:\n        p = _next_prime(p)\n        cand = _rabung(p, r, k, rng)\n        if cand and len(cand) > len(best) and not _has_mono_ap(cand, r, k):\n            best = cand\n    return best\n"}}