A Fixed 66-by-66 Pattern Defeats Polynomial Removal Bounds

In an ordered binary matrix, a copy of a pattern uses selected rows and columns in their existing order. Every selected entry must match—including zeros. A removal question asks how many entries must be flipped to eliminate every copy.

For the fixed 66-by-66 pattern in the manuscript, a polynomial removal bound would say: if the best repair must change at least an ε fraction of the host matrix’s entries, then the matrix contains at least cε^C n^132 ordered copies. Here n is the host’s side length; the exponent 132 counts the 66 selected rows and 66 selected columns. The positive constants c and C may depend on the pattern, but not on n or ε.

The manuscript constructs one pattern H and an infinite family of host matrices that defeat every such choice of constants. The hosts remain a noticeable distance from being H-free even as their normalized copy counts fall below every fixed power of that distance. The result is a failure of a polynomial guarantee, not of qualitative removal: being far from pattern-free still forces copies. ^†

The pattern is designed to control where copies can occur. Its upper-left 64-by-64 block is a dense anchor, almost entirely ones off the diagonal. Two extra rows and columns provide sparse signatures; the remaining 2-by-2 body is P = [[1, 0], [1, 1]]. In the anchor’s last five columns, the bottom 32 rows list every five-bit word. The manuscript proves that these signatures, together with the dense rows and columns, make the anchor rigid: copies cannot assemble themselves in unintended positions. The counterexample depends on the complete 66-by-66 pattern, not P alone.

The mechanism starts with a local rule. Put a fixed column of ones beside two entries a and b, making the 2-by-2 matrix [[1, a], [1, b]]. This contains P exactly when a = 0 and b = 1. So avoiding P requires b ≤ a: if the right entry is one, the left must be one; if the left is zero, the right must be zero.

Put the fixed ones across the bottom row instead, and avoiding P requires a ≤ b. The anchor determines which comparisons apply, while dummy rows and columns supply the fixed ones. These local rules let avoidance of a 2-by-2 pattern transmit values between positions.

The host arranges the constraints along a binary tree of depth h. Each internal node has separate plus and minus row blocks and plus and minus column blocks. The two signals begin at different root cells, one representing 1 and the other 0. Along a chosen branch, the local implications force each signal through successive row levels and then column levels; the row and column orders make the comparisons point in the required directions. At the leaf, both signals must occupy the same cell. It cannot hold both 1 and 0.

Thus, if a repair leaves the relevant anchor entries, signatures, dummy incidences and root cells intact for some setup, that setup still contains H. An H-free repair must disrupt every setup.

The proof applies the tree contradiction to a randomly selected setup. The protected entries are the ones that make the contradiction work: anchor entries, anchor-to-body signatures, dummy incidences and root-cell intersections. The argument does not require the same probability bound for every cell in the matrix; it concerns only these protected entries.

Let m = 2^h, the number of leaves. Each axis is divided into classes of size m. Choose a leaf uniformly, follow its ancestor path on both axes, and independently choose uniform positions from the needed anchor groups, dummy groups and ancestor blocks. Each fixed protected cell is selected with probability 1/m².

If a repair changes r entries, the union bound says the probability that the selected setup touches any changed protected entry is at most r/m². When r < m², this probability is below one, so there is a setup that avoids all those edits. The tree contradiction then forces an H-copy to remain. Consequently, every H-free repair must change at least m² entries.

The unedited host is nevertheless sparse in copies. Anchor rigidity and a check of the permitted modes force each copy into a designated arrangement. Every surviving copy must use a diagonal leaf cell in one particular slot of H. There are only m choices for that cell; after fixing it, at most n^130 choices remain. The copy count is therefore at most m n^130.

Flipping those m leaf cells from one to zero destroys the original copies, but need not eliminate all copies. In the leaf-cell example, an anchored 2-by-2 body that was all ones becomes P after an edit. The anchor signatures remain unchanged, and a new H-copy appears. Hitting every old copy is not the same as repairing the matrix.

At depth h, the host’s side length is nₕ = (386h + 2)2ʰ. Since every H-free repair requires at least m² = 2²ʰ edits out of nₕ² entries, the distance from being H-free is at least εₕ = (386h + 2)⁻². Meanwhile, the normalized copy count is at most N_H(Aₕ)/nₕ¹³² ≤ εₕ 2⁻ʰ.

For any fixed positive exponent C, dividing this bound by εₕ^C leaves a fixed power of 386h + 2 multiplied by 2⁻ʰ. As h grows, that ratio tends to zero: exponential decay eventually beats every fixed power. It therefore falls below any proposed positive constant c. The same fixed pattern H defeats every polynomial removal bound of the stated form.