OAI.Problem348.no_polynomial_removal_bound

The theorem states that no polynomial removal bound holds for a specific fixed 66×66 binary pattern H (fixedH). Matrices are n×n arrays of Booleans. A copy of H in an n×n matrix A is a pair of strictly increasing maps r, s from the 66 indices into Fin n such that A(r(i), s(j)) = H(i,j) for all i, j (exact entry-wise agreement, with zeros as well as ones required to match); copyCount(H,A) is the number of such pairs, and A is H-free when this count is zero. fixedDistance(A) is the minimum Hamming distance from A to an H-free n×n matrix, divided by n². The pattern H is built from a 64×64 block in which an entry is true exactly when its row and column differ, except that in rows 32 to 63 and columns 59 to 63 the entry is instead the binary digit of (row−32), namely the bit with place value 2^(5−b) for b = column−58; two extra indices 64 and 65 are then added, with entries true at (0,64), (64,0), (1,65), (65,1) and, within the 2×2 corner, true exactly when the row index is 65 or the column index is 64, and false elsewhere. The claim is that for all real c > 0 and C > 0 there exist an integer n ≥ 1, a real ε with 0 < ε < 1, and an n×n binary matrix A such that fixedDistance(A) ≥ ε while copyCount(H,A) < c·ε^C·n^132. Thus no bound of the form c·ε^C·n^132 on the number of copies of H can hold for matrices that are ε-far from H-free, for any positive constant c and exponent C.