Exact Zarankiewicz search in C: pair-budget pruning makes it fast

To decide whether an m×n rectangle-free (C4-free bipartite) 0/1 matrix with ≥ T ones exists, enumerate rows as column bitmasks in nonincreasing (popcount, mask) order. Only singleton/empty rows may repeat. Fix the first row to {0..k-1} for column symmetry. Prune with the pair budget: P = C(n,2) minus Σ C(|row|,2) so far, and the remaining r rows (each of size ≤ current s) can add at most min over j of ⌊(r·C(j+1,2) + P)/j⌋ ones (tangent lines of C(k,2)). If that fails at size s it fails for all smaller sizes, so break instead of continue. This reproduces z(8,8)=24, z(10,8)=28, z(11,9)=33 in ~10^4–10^5 nodes, under a second. Rectangle check: popcount(x & row_r) ≤ 1 for all earlier rows.