{"id":"zarankiewicz-c4-free","name":"Zarankiewicz problem, square 2 x 2","family":"combinatorics","description":"Zarankiewicz's z(n;2) (OEIS A072567 / A001197): the most 1s an n x n 0/1 matrix can hold without a 2 x 2 all-ones submatrix. Instances n = 25, 26, 27 (exact by Afzaly and McKay, unpublished), 32 (189 <= z <= 190) and 43 (290 <= z <= 294), scored against the best-known counts.","metric":"record_ratio","direction":"maximize","tolerance":0.05,"eval_timeout_seconds":300,"agent_timeout_seconds":1800,"mutable":["matrix.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":"# Zarankiewicz problem, square 2 x 2\n\n## Goal\n\n`matrix.py` exposes `matrix(n: int, time_budget: float, seed: int) -> list[int]`: `n` row bitmasks\n(bit `c` of entry `r` set means a 1 at row `r`, column `c`, with `0 <= c < n`) describing an\n`n x n` 0/1 matrix with no 2 x 2 all-ones submatrix, i.e. no two rows have 1s in two common\ncolumns. Maximise the number of 1s. This is Zarankiewicz's `z(n; 2)` (OEIS A072567; A001197 is\n`z + 1`), equivalently the most edges in a `C4`-free bipartite graph with `n + n` vertices.\n\nReiman's bound gives `z(n; 2) <= n (1 + sqrt(4n - 3)) / 2`, with equality exactly when\n`n = q^2 + q + 1` and a projective plane of order `q` exists: its point-line incidence matrix has\n`(q + 1)(q^2 + q + 1)` ones (186 for `n = 31`, 456 for `n = 57`). Away from those `n` the truth is\nknown only by computation: Guy's 1969 tables to `n = 21`, Afzaly and McKay (2015, unpublished) to\n`n = 31`, Tan's SAT proofs (2022) confirming `n <= 24` in the OEIS. `n = 32` is the first open\ncase, `189 <= z(32; 2) <= 190`. `n = 43 = 6^2 + 6 + 1` is the famous one: there is no plane of\norder 6 (Tarry 1900), so the Reiman bound 301 is unattainable; the best matrix, 290 ones, was found\nby local search in the mid-1990s and posted on MathOverflow in 2015 (question 191571, \"How close\ncan one get to the missing finite projective planes?\"), and Sadhu (arXiv:2608.01606, August 2026)\nproved `z(43; 2) <= 294` and that nothing built from PG(2, 7) can exceed 288.\n\n## Instances and records\n\nEvery instance is scored against the best-known number of 1s. `record_ratio` for an instance is\n`ones / record`, so 1.0 is a match and above 1.0 is a new record.\n\n| n | best known | upper bound | status | source |\n|---|---|---|---|---|\n| 25 | 130 | 130 | exact, unpublished | Afzaly and McKay 2015, reported in Collins, Riasanovsky, Wallace, Radziszowski, arXiv:1604.01257, Table 3 |\n| 26 | 138 | 138 | exact, unpublished | same |\n| 27 | 147 | 147 | exact, unpublished | same |\n| 32 | 189 | 190 | open | same table (\"189/190\", first open case) |\n| 43 | 290 | 294 | open | lower: user48028, MathOverflow 191571 (March 2015), matrix re-verified by this pack's checker on 2026-09-07; upper: Sadhu, arXiv:2608.01606 |\n\n`n = 25, 26, 27` are calibration: their values are exact according to Afzaly and McKay's\ncomputation, which Collins et al. cite as personal communication and which the OEIS has not yet\nabsorbed (A001197 stops at `n = 24`), so a match is the best possible result there and any excess\nwould mean the reported value is wrong. `n = 32` and `n = 43` are open: 190 ones on a 32 x 32\nmatrix or 291 on a 43 x 43 matrix is a new record.\n\n## Metric\n\n    metric = mean over n in {25, 26, 27, 32, 43} of  ones(n) / record(n)\n\nThe eval re-derives everything from the row bitmasks you return: exactly `n` integers, no bits\nbeyond column `n - 1`, and for every pair of rows the bitwise AND has at most one bit set. Any\nviolation on any `n` is a failed run (`wrong_answer`), and a solver that raises or overruns\n`1.25 * time_budget + 3` seconds fails too. `ZT_EVAL_SEED` only changes the `seed` handed to your\nsolver; the instance set is fixed, so your method has to be robust to its starting point.\n\n## Constraints\n\n- Standard library only. No numpy, no scipy, no SAT or ILP libraries. The eval rejects other imports.\n- Respect `time_budget` (seconds, per call). The default is 20 s per instance, so a full eval takes\n  about 100 s; use the whole budget, nothing is gained by returning early.\n- Deterministic given `seed`: use `random.Random(seed)`.\n- Rows and columns are interchangeable (the transpose is also C4-free), and so are permutations of\n  either: only the count matters.\n\n## Iterating quickly\n\n- `ZT_EVAL_INSTANCES=32,43` (comma-separated `n` values from the table) runs a subset.\n- `ZT_EVAL_PER_INSTANCE_SECONDS=5` shrinks the per-instance budget.\n\nExample: `ZT_EVAL_INSTANCES=25 ZT_EVAL_PER_INSTANCE_SECONDS=5 python eval.py`.\n\n## Ideas that are known to matter (check the journal before repeating one)\n\n- Work on bitmasks. Setting `(r, c)` is legal iff every other row with a 1 in column `c` shares no\n  column with row `r`: one AND per such row. Keep column masks too and the test is a handful of\n  integer operations.\n- The extremal matrices are nearly regular: in the records almost every row and column has degree\n  `floor` or `ceil` of `ones / n` (the 290 matrix has row sums 6 and 7 only). Searches that hold\n  degree sequences near-regular and move 1s along rows (swap a 1 in row `r` from column `c` to\n  column `c'`) explore the right space; unconstrained add/remove random walks get stuck far below.\n- Algebra gets you close for free: for `n = 43`, delete 14 points and 14 lines from PG(2, 7)\n  (`57 x 57`, 456 ones) and re-add 1s greedily; Sadhu shows this family tops out at 288, so the\n  last two 1s need genuine search. For `n = 32`, add a row and a column to PG(2, 5) (186 ones) and\n  refill. For `n = 25..27`, delete from PG(2, 5) or extend AG(2, 5).\n- Difference-set matrices (row `i` has 1s at columns `i + d mod n` for `d` in a Sidon set) are\n  circulant and C4-free; they reach the plane bound when a perfect difference set exists and are a\n  strong start elsewhere.\n- Tan (arXiv:2203.02283) lists every maximal matrix up to `n = 24` with its automorphism group;\n  most have symmetry, so imposing a cyclic or dihedral symmetry group shrinks the search without\n  losing the optimum in most cases.\n\nWrite one honest line in `NOTES.md`: the idea, and which `n` 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 zarankiewicz-c4-free. Prints one JSON line: {\"metric\": record_ratio, ...}.\n\nEnv:\n  ZT_EVAL_SEED                   seed handed to matrix()\n  ZT_EVAL_PER_INSTANCE_SECONDS   time budget per matrix size n (default 20)\n  ZT_EVAL_INSTANCES              comma-separated matrix sizes n (default \"25,26,27,32,43\")\n\"\"\"\n\nfrom __future__ import annotations\n\nimport ast\nimport json\nimport math\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\", \"20\"))\nINSTANCES = [int(x) for x in os.environ.get(\"ZT_EVAL_INSTANCES\", \"25,26,27,32,43\").split(\",\")]\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# Best-known number of 1s in an n x n 0/1 matrix with no 2 x 2 all-ones submatrix, z(n;2)\n# (= OEIS A001197(n) - 1 = A072567(n)).\n#   25, 26, 27: exact values computed by Afzaly and McKay (2015, unpublished; personal communication\n#               reported in Collins, Riasanovsky, Wallace, Radziszowski, \"Zarankiewicz numbers and\n#               bipartite Ramsey numbers\", arXiv:1604.01257, Table 3). Not in the OEIS, which stops\n#               at n = 24 (Tan, arXiv:2203.02283). Treated as exact but not as published proofs.\n#   32: 189 <= z(32;2) <= 190, the first open case (same Table 3).\n#   43: 290 <= z(43;2) <= 294. Lower bound: an explicit matrix posted on MathOverflow in March 2015\n#       (local search from the mid-1990s, never improved); upper bound: Sadhu, arXiv:2608.01606\n#       (2026), improving the Reiman bound 301, which would need the non-existent plane of order 6.\n# Update when a hub-verified submission exceeds these.\nRECORDS = {25: 130, 26: 138, 27: 147, 32: 189, 43: 290}\nUPPER = {25: 130, 26: 138, 27: 147, 32: 190, 43: 294}\nSTATUS = {25: \"exact (Afzaly-McKay 2015, unpublished)\", 26: \"exact (Afzaly-McKay 2015, unpublished)\",\n          27: \"exact (Afzaly-McKay 2015, unpublished)\", 32: \"open\", 43: \"open\"}\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 matrix.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(rows, n: int) -> int:\n    \"\"\"Check the returned row bitmasks and return the number of 1s. Nothing the solver reports is trusted.\"\"\"\n    if not isinstance(rows, (list, tuple)) or len(rows) != n:\n        fail(f\"matrix({n}) must return a list of {n} row bitmasks\", \"wrong_answer\")\n    masks = []\n    for i, m in enumerate(rows):\n        if isinstance(m, bool) or not isinstance(m, int):\n            fail(f\"matrix({n}) row {i} is {m!r}, not an int bitmask\", \"wrong_answer\")\n        if m < 0 or m >> n:\n            fail(f\"matrix({n}) row {i} has bits outside columns 0..{n - 1}\", \"wrong_answer\")\n        masks.append(m)\n    # No 2 x 2 all-ones submatrix <=> every two rows share at most one column with a 1.\n    for i in range(n):\n        for j in range(i + 1, n):\n            common = masks[i] & masks[j]\n            if common & (common - 1):\n                cols = [c for c in range(n) if common >> c & 1][:2]\n                fail(f\"matrix({n}): rows {i} and {j} both have 1s in columns {cols[0]} and {cols[1]}\", \"wrong_answer\")\n    ones = sum(m.bit_count() for m in masks)\n    reiman = int(n * (1 + math.isqrt(4 * n - 3)) / 2)  # Reiman's bound, floor(n(1+sqrt(4n-3))/2) is safe\n    if ones > reiman + 1:\n        fail(f\"matrix({n}) claims {ones} ones, above the Reiman bound; validation is broken\", \"error\")\n    return ones\n\n\ndef main() -> None:\n    here = Path(__file__).parent\n    check_imports(here / \"matrix.py\")\n    sys.dont_write_bytecode = True  # a stale matrix.pyc must never be what gets scored\n    sys.path.insert(0, str(here))\n    try:\n        import matrix as cand  # noqa: E402\n    except SystemExit:\n        raise\n    except Exception as e:\n        fail(f\"import matrix.py failed: {e!r}\", \"compile_error\")\n    if not hasattr(cand, \"matrix\"):\n        fail(\"matrix.py must define matrix(n, time_budget, seed)\", \"compile_error\")\n\n    seed_int = random.Random(f\"zarankiewicz|{SEED}\").getrandbits(32)\n    per_n, beaten = {}, []\n    for n in INSTANCES:\n        if n not in RECORDS:\n            fail(f\"no record for n={n}\", \"error\")\n        t0 = time.perf_counter()\n        try:\n            rows = cand.matrix(n, BUDGET, seed_int)\n        except SystemExit:\n            raise\n        except Exception as e:\n            fail(f\"matrix({n}) raised {e!r}\", \"runtime_error\")\n        elapsed = time.perf_counter() - t0\n        if elapsed > 1.25 * BUDGET + 3:\n            fail(f\"matrix({n}) took {elapsed:.1f}s against a {BUDGET:.0f}s budget\", \"timeout\")\n        ones = validate(rows, n)\n        per_n[n] = {\"ones\": ones, \"record\": RECORDS[n], \"upper_bound\": UPPER[n], \"status\": STATUS[n],\n                    \"proven_optimal\": False, \"ratio\": round(ones / RECORDS[n], 6), \"seconds\": round(elapsed, 2)}\n        if ones > RECORDS[n]:\n            beaten.append(n)\n    metric = sum(v[\"ratio\"] for v in per_n.values()) / len(per_n)\n    print(json.dumps({\"metric\": round(metric, 6), \"per_n\": per_n, \"records_beaten\": beaten}))\n\n\nif __name__ == \"__main__\":\n    main()\n","baseline":{"matrix.py":"\"\"\"Baseline: random greedy fill of a C4-free 0/1 matrix plus a fixed number of ruin-and-recreate\nrounds, all on row bitmasks. Scores roughly 0.8 of the records. Beat it.\"\"\"\n\nimport random\nimport time\n\n\ndef matrix(n: int, time_budget: float, seed: int) -> list[int]:\n    rng = random.Random(seed)\n    deadline = time.perf_counter() + time_budget\n    cells = [(r, c) for r in range(n) for c in range(n)]\n\n    def can_set(rows, r, c):\n        \"\"\"Setting (r, c) is safe iff no other row with a 1 in column c shares a column with row r.\"\"\"\n        mine = rows[r]\n        for r2 in range(n):\n            if r2 != r and rows[r2] >> c & 1 and rows[r2] & mine:\n                return False\n        return True\n\n    def build(keep):\n        rows = list(keep)\n        order = cells[:]\n        rng.shuffle(order)\n        for r, c in order:\n            if not rows[r] >> c & 1 and can_set(rows, r, c):\n                rows[r] |= 1 << c\n        return rows\n\n    best = build([0] * n)\n    for _ in range(1500):  # a fixed round count keeps the result deterministic under seed\n        if time.perf_counter() > deadline:  # only bites when the budget is cut short\n            break\n        keep = list(best)\n        for r in rng.sample(range(n), max(1, n // 4)):\n            keep[r] = 0  # wipe a quarter of the rows and refill everything greedily\n        cand = build(keep)\n        if sum(m.bit_count() for m in cand) >= sum(m.bit_count() for m in best):\n            best = cand\n    return best\n"}}