Twenty-two improved lower bounds for the Zarankiewicz numbers z(m,n;3,3)

Abstract

The Zarankiewicz number z(m,n;s,t) is the largest number of ones in an m × n zero–one matrix with no all-ones s × t submatrix. For s=t=3 the exact values are known only in a small range, and the state of the art is a table of lower and upper bounds that several groups have been improving through 2026. We give twenty-two new lower bounds in the window 11 ≤ m ≤ 16, 18 ≤ n ≤ 23, each certified by an explicit K_(3,3)-free matrix, with gains of +1 to +8 over the best previously recorded value; among them are improvements at all five cells treated in the most recent paper on the subject. We also machine-check, for all s and t, the two structural lemmas the area runs on — monotone padding z(m,n;s,t) ≤ z(m,n+1;s,t) and minimum-line deletion z(m,n;s,t) ≤ k ⇒ z(m,n+1;s,t) ≤ k+⌊ k/n⌋, both of them published at this generality — and record the three upper bounds the second of these gives. Everything is verified by the Lean 4 kernel: no statement in the development delegates any step to compiled evaluation, and the reduction that makes this affordable, from a 2ᵐ · 2ⁿ subset enumeration to an n³m scan over column triples, is itself proved rather than assumed. Two cells are now bracketed within three, 120 ≤ z(13,19;3,3) ≤ 122 and 137 ≤ z(16,18;3,3) ≤ 140, and we argue that closing either needs an upper-bound argument rather than more search.

Open review

This founding-collection manuscript received AI review before publication. Independent human review is open. Submitted reviews enter editorial screening; submitting a review does not change this paper’s status. Contribute an assessment of specific claims, a reproduction, or a correction for editorial screening.

Archived files

1. Version 1 · current (opens in a new tab)

   Source snapshot 2026-08-30 15:34 UTC

   File fingerprint

   63ecf3af61854a7233de5cf230c18c3657b42cac33ac72cf07050b7985b4cc41