{"id":"schur-lower","name":"Schur numbers, lower bounds by sum-free partitions","family":"additive-combinatorics","description":"Partition {1..N} into r sum-free sets (no x + y = z in one part, x = y allowed) to certify S(r) >= N. Instances r = 6, 7, 8, scored against the best-known partitions (Fredricksen-Sweet 2000, Rowley 2021, Bengone et al. 2026).","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":"# Schur numbers: lower bounds by sum-free partitions\n\n## Goal\n\nA set of integers is *sum-free* if it contains no `x, y, z` with `x + y = z`; `x = y` is allowed,\nso `{1, 2}` is not sum-free (`1 + 1 = 2`). The Schur number `S(r)` is the largest `N` such that\n`{1, ..., N}` can be partitioned into `r` sum-free sets. (Some authors define it as `N + 1`, the least\n`n` forcing a monochromatic solution; Wikipedia's `S(5) = 161` is the same fact as the `S(5) = 160`\nused here.) `S(1..5) = 1, 4, 13, 44, 160`; the last was settled by Heule's 2-petabyte SAT proof in\n2017. Nothing beyond `r = 5` is known exactly, and every known lower bound is an explicit partition.\n\n`colouring.py` exposes\n\n    colouring(r: 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 by `r`:\n\n| label | r | record N |\n|---|---|---|\n| `6` | 6 | 536  |\n| `7` | 7 | 1696 |\n| `8` | 8 | 5362 |\n\n## Metric\n\n    metric = mean over instances of  N(instance) / record(instance)\n\nThe eval checks every `x + y = z` exactly (colour classes as bitmasks: `x` has a partner in its class\n`B` iff `B & (B >> x)` is non-zero). A single monochromatic triple fails the run (`wrong_answer`,\nnaming `x + y = z`). 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 `S(r)` and is flagged in `records_beaten`. `ZT_EVAL_SEED` only changes the `seed` handed to\nyour solver; the instance set is fixed.\n\n## Records\n\nNone of the three is known to be optimal; the best upper bounds (via `S(r) ≤ R_r(3) − 2`) are far\nabove them. Each record partition was re-verified by this pack's checker before being pinned.\n\n| label | record | source | status |\n|---|---|---|---|\n| `6` | 536  | H. Fredricksen, M. M. Sweet, \"Symmetric sum-free partitions and lower bounds for Schur numbers\", EJC 7 (2000) R32 — the symmetric partition is printed in the paper | open |\n| `7` | 1696 | F. Rowley, \"An improved lower bound for S(7) and some interesting templates\", arXiv:2107.03560 (2021), ancillary file; supersedes 1680 (Fredricksen–Sweet 2000) | open |\n| `8` | 5362 | N. Bengone, A. Brouk, M. Grinsztajn, T. Helbert, B. Lugherini, A. Rimmel, J. Tomasik, \"Shifted S-templates and improved lower bounds for Schur numbers\", arXiv:2607.15034 (2026): a width-10 template applied to the Fredricksen–Sweet 536-partition, `S(r+2) ≥ 10 S(r) + 2`; supersedes 5286 | open |\n\nFor orientation only (not instances): `S(9) ≥ 17 803` and `S(10) ≥ 60 948` (Ageron, Casteras,\nPellerin, Portella, Rimmel, Tomasik, arXiv:2112.03175, 2022).\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=6,7` restricts the eval to a subset of labels (default `6,7,8`).\n- `ZT_EVAL_PER_INSTANCE_SECONDS=5` shrinks the per-instance budget (default 30; the full eval takes\n  about 90 s).\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- Recurrences from small partitions (the baseline uses Schur's `S(r+1) ≥ 3 S(r) + 1`): Abbott–Hanson\n  `S(r+2) ≥ 9 S(r) + 4`, Rowley's templates `S(r+3) ≥ 33 S(r) + 6`, `S(r+4) ≥ 109 S(r) + 39`,\n  `S(r+5) ≥ 376 S(r) + 160`, and the 2026 shifted template `S(r+2) ≥ 10 S(r) + 2`. From\n  `S(5) = 160` and `S(6) ≥ 536` these already give 1444 (`r = 7`) and 5362 (`r = 8`); the `r = 6`\n  record is pure search.\n- Symmetry: every record partition is (almost) symmetric, `colour(x) = colour(N + 1 − x)`. Halve\n  the search space by imposing it; Fredricksen–Sweet also track the \"e-depth\" (how far a partition\n  of `[1, n]` extends) to pick which partial partitions to grow.\n- Rowley's `S(7) ≥ 1696` came from taking a six-colour partition of `[1, 536]`, giving 537 the new\n  colour, forcing symmetry about 1697, and running a plain tree search upward from 538: the\n  integers just above 537 are already heavily blocked, so the search is narrow.\n- Local search: state = a colouring, cost = number of monochromatic `x + y = z`; the classic SAT\n  encoding (one clause per triple) responds well to WalkSAT-style flips. Use the bitmask trick from\n  the checker so that evaluating a flip costs a few big-int operations.\n- Start from a good partition of a shorter interval and extend greedily, backtracking only over the\n  last few dozen integers.\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 schur-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 30)\n  ZT_EVAL_INSTANCES              comma-separated colour counts (default \"6,7,8\")\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\", \"30\"))\nINSTANCES = [s.strip() for s in os.environ.get(\"ZT_EVAL_INSTANCES\", \"6,7,8\").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 -> N, the largest known partition of [1, N] into r sum-free sets (x + y = z forbidden within a set,\n# x = y allowed), i.e. S(r) >= N. Sources and status in program.md; none is proven optimal.\nRECORDS = {\"6\": 536, \"7\": 1696, \"8\": 5362}\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 schur_triple(seq: list[int], r: int):\n    \"\"\"Exact check. Returns (colour, x, y) with x <= y and x, y, x + y all of one colour, or None.\n\n    Class bitmask B (bit z set iff z has the colour): x in B has a partner iff B & (B >> x) != 0.\n    \"\"\"\n    masks = [0] * r\n    for z, c in enumerate(seq, start=1):\n        masks[c] |= 1 << z\n    for colour, b in enumerate(masks):\n        rest = b\n        while rest:\n            x = (rest & -rest).bit_length() - 1\n            rest &= rest - 1\n            hit = b & (b >> x)\n            if hit:\n                return colour, x, (hit & -hit).bit_length() - 1\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, time_budget, seed)\", \"compile_error\")\n\n    seed_int = random.Random(f\"schur|{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, record = int(label), RECORDS[label]\n        t0 = time.perf_counter()\n        try:\n            out = cand.colouring(r, 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 = schur_triple(seq, r)\n        if bad is not None:\n            colour, x, y = bad\n            fail(f\"colouring({label}): {x} + {y} = {x + y} all in colour {colour}\", \"wrong_answer\")\n        n = len(seq)\n        per[label] = {\"r\": r, \"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: Schur's tripling from Baumert's 4-colour partition of [1, 44], then random greedy extension. Beat it.\n\nFrom a sum-free partition of [1, n] into r colours, colouring [n+1, 2n+1] with a new colour and\n[2n+2, 3n+1] like [1, n] gives a sum-free partition of [1, 3n+1] into r+1 colours (Schur 1916). After\nthat the colouring is extended one integer at a time with random restarts for as long as the budget lasts.\n\"\"\"\n\nimport random\nimport time\n\n# Baumert (1965): S(4) = 44. Each list is one colour class.\nBAUMERT_44 = [\n    [1, 3, 5, 15, 17, 19, 26, 28, 40, 42, 44],\n    [2, 7, 8, 18, 21, 24, 27, 33, 37, 38, 43],\n    [4, 6, 13, 20, 22, 23, 25, 30, 32, 39, 41],\n    [9, 10, 11, 12, 14, 16, 29, 31, 34, 35, 36],\n]\n\n\ndef _triple(seq: list[int], new_colour: int) -> list[int]:\n    n = len(seq)\n    return seq + [new_colour] * (n + 1) + seq\n\n\ndef colouring(r: int, time_budget: float, seed: int) -> list[int]:\n    rng = random.Random(seed)\n    deadline = time.perf_counter() + 0.85 * time_budget\n    if r >= 4:\n        base = [0] * 44\n        for c, cls in enumerate(BAUMERT_44):\n            for z in cls:\n                base[z - 1] = c\n        used = 4\n    else:\n        base, used = [0], 1\n    while used < r:\n        base = _triple(base, used)\n        used += 1\n\n    # sums[c] has bit s set iff s = x + y for some x <= y already of colour c; z may take colour c iff bit z is clear.\n    # Each restart cuts a random tail off the base (the tripled colouring is maximal as it stands) and re-grows it.\n    best = base\n    while time.perf_counter() < deadline:\n        seq = base[: len(base) - rng.randrange(0, min(80, len(base) // 3))]\n        masks, sums = [0] * r, [0] * r\n        for z, c in enumerate(seq, start=1):\n            sums[c] |= (masks[c] << z) | (1 << (2 * z))\n            masks[c] |= 1 << z\n        while True:\n            z = len(seq) + 1\n            ok = [c for c in range(r) if not (sums[c] >> z) & 1]\n            if not ok:\n                break\n            c = rng.choice(ok)\n            seq.append(c)\n            sums[c] |= (masks[c] << z) | (1 << (2 * z))\n            masks[c] |= 1 << z\n        if len(seq) > len(best):\n            best = seq\n    return best\n"}}