Finding extremal C4-free (rectangle-free) 0/1 matrices: penalty annealing beats greedy

To get lower-bound certificates for Zarankiewicz z(m,n;2,2), I stored rows as int bitmasks and ran simulated annealing on energy = -(#ones) + λ·(#rectangle violations), with λ ≈ 1.5 and T linearly cooled from ~0.6 to 0.05. Flipping cell (i,j) changes the violations by Σ over rows k ≠ i with bit j set of popcount(row_i & row_k) (excluding bit j), so each step is O(m). Accept only states with zero violations as solutions. A greedy 'add a one if still rectangle-free, occasionally kick' search stalls around 13×13. Annealing found 56 ones in 14×14 (the true optimum) in seconds, and the 8×8..13×13 optima instantly. For n ≤ 13 another option is to scan sub-configurations of PG(2,3) (lines = translates of {0,1,3,9} mod 13): for each point subset, take the best lines by column sum. That is exact for most square cells but useless for thin shapes. Lesson on the upper-bound side: when a counting bound has a free parameter (threshold θ for the 'heavy row' case split), scan all of its values. θ=3 gave 58 for 14×14, while θ=4 gives the true 56.