Zarankiewicz problem, square 2 x 2

# Zarankiewicz problem, square 2 x 2 ## Goal `matrix.py` exposes `matrix(n: int, time_budget: float, seed: int) -> list[int]`: `n` row bitmasks (bit `c` of entry `r` set means a 1 at row `r`, column `c`, with `0 <= c < n`) describing an `n x n` 0/1 matrix with no 2 x 2 all-ones submatrix, i.e. no two rows have 1s in two common columns. Maximise the number of 1s. This is Zarankiewicz's `z(n; 2)` (OEIS A072567; A001197 is `z + 1`), equivalently the most edges in a `C4`-free bipartite graph with `n + n` vertices. Reiman's bound gives `z(n; 2) <= n (1 + sqrt(4n - 3)) / 2`, with equality exactly when `n = q^2 + q + 1` and a projective plane of order `q` exists: its point-line incidence matrix has `(q + 1)(q^2 + q + 1)` ones (186 for `n = 31`, 456 for `n = 57`). Away from those `n` the truth is known only by computation: Guy's 1969 tables to `n = 21`, Afzaly and McKay (2015, unpublished) to `n = 31`, Tan's SAT proofs (2022) confirming `n <= 24` in the OEIS. `n = 32` is the first open case, `189 <= z(32; 2) <= 190`. `n = 43 = 6^2 + 6 + 1` is the famous one: there is no plane of order 6 (Tarry 1900), so the Reiman bound 301 is unattainable; the best matrix, 290 ones, was found by local search in the mid-1990s and posted on MathOverflow in 2015 (question 191571, "How close can one get to the missing finite projective planes?"), and Sadhu (arXiv:2608.01606, August 2026) proved `z(43; 2) <= 294` and that nothing built from PG(2, 7) can exceed 288. ## Instances and records Every instance is scored against the best-known number of 1s. `record_ratio` for an instance is `ones / record`, so 1.0 is a match and above 1.0 is a new record. | n | best known | upper bound | status | source | |---|---|---|---|---| | 25 | 130 | 130 | exact, unpublished | Afzaly and McKay 2015, reported in Collins, Riasanovsky, Wallace, Radziszowski, arXiv:1604.01257, Table 3 | | 26 | 138 | 138 | exact, unpublished | same | | 27 | 147 | 147 | exact, unpublished | same | | 32 | 189 | 190 | open | same table ("189/190", first open case) | | 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 = 25, 26, 27` are calibration: their values are exact according to Afzaly and McKay's computation, which Collins et al. cite as personal communication and which the OEIS has not yet absorbed (A001197 stops at `n = 24`), so a match is the best possible result there and any excess would mean the reported value is wrong. `n = 32` and `n = 43` are open: 190 ones on a 32 x 32 matrix or 291 on a 43 x 43 matrix is a new record. ## Metric metric = mean over n in {25, 26, 27, 32, 43} of ones(n) / record(n) The eval re-derives everything from the row bitmasks you return: exactly `n` integers, no bits beyond column `n - 1`, and for every pair of rows the bitwise AND has at most one bit set. Any violation on any `n` is a failed run (`wrong_answer`), and a solver that raises or overruns `1.25 * time_budget + 3` seconds fails too. `ZT_EVAL_SEED` only changes the `seed` handed to your solver; the instance set is fixed, so your method has to be robust to its starting point. ## Constraints - Standard library only. No numpy, no scipy, no SAT or ILP libraries. The eval rejects other imports. - Respect `time_budget` (seconds, per call). The default is 20 s per instance, so a full eval takes about 100 s; use the whole budget, nothing is gained by returning early. - Deterministic given `seed`: use `random.Random(seed)`. - Rows and columns are interchangeable (the transpose is also C4-free), and so are permutations of either: only the count matters. ## Iterating quickly - `ZT_EVAL_INSTANCES=32,43` (comma-separated `n` values from the table) runs a subset. - `ZT_EVAL_PER_INSTANCE_SECONDS=5` shrinks the per-instance budget. Example: `ZT_EVAL_INSTANCES=25 ZT_EVAL_PER_INSTANCE_SECONDS=5 python eval.py`. ## Ideas that are known to matter (check the journal before repeating one) - Work on bitmasks. Setting `(r, c)` is legal iff every other row with a 1 in column `c` shares no column with row `r`: one AND per such row. Keep column masks too and the test is a handful of integer operations. - The extremal matrices are nearly regular: in the records almost every row and column has degree `floor` or `ceil` of `ones / n` (the 290 matrix has row sums 6 and 7 only). Searches that hold degree sequences near-regular and move 1s along rows (swap a 1 in row `r` from column `c` to column `c'`) explore the right space; unconstrained add/remove random walks get stuck far below. - Algebra gets you close for free: for `n = 43`, delete 14 points and 14 lines from PG(2, 7) (`57 x 57`, 456 ones) and re-add 1s greedily; Sadhu shows this family tops out at 288, so the last two 1s need genuine search. For `n = 32`, add a row and a column to PG(2, 5) (186 ones) and refill. For `n = 25..27`, delete from PG(2, 5) or extend AG(2, 5). - Difference-set matrices (row `i` has 1s at columns `i + d mod n` for `d` in a Sidon set) are circulant and C4-free; they reach the plane bound when a perfect difference set exists and are a strong start elsewhere. - Tan (arXiv:2203.02283) lists every maximal matrix up to `n = 24` with its automorphism group; most have symmetry, so imposing a cyclic or dihedral symmetry group shrinks the search without losing the optimum in most cases. Write one honest line in `NOTES.md`: the idea, and which `n` 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.