Polynomial removal fails for ordered binary matrices

The explanation

Take a small grid of zeros and ones, two rows by two columns. Its top row reads 1, 0 and its bottom row reads 1, 1. Call it the pattern. Now take a 3 by 3 grid of ones, except a 0 in the top right corner. Where does the pattern appear inside it?

A copy means choosing two rows, top to bottom, and two columns, left to right. The four cells where they cross must match the pattern exactly, zeros includedSource 1. The 0 must be the top right corner. Then either of the other two columns works, and either of the lower two rows. That gives 4 copies. Change that single 0 to a 1, and every copy disappears.

Grids like this are called binary matrices. The row and column order matters, which is why these copies are called ordered. A matrix is ε-far from pattern-free if you must change at least a fraction ε of its cells to remove every copy. Changes may go either way, 0 to 1 or 1 to 0Source 2. A removal lemma says that a matrix far from pattern-free must contain many copies.

That qualitative statement was already known for ordered matrices, from Alon, Ben-Eliezer and FischerSource 3. The open question was how many copies it guarantees. Alon, Fischer and Newman raised the ordered questionSource 4. Alon and Ben-Eliezer later posed the polynomial versionSource 5. It predicts at least c·ε^C·n^(2k) copies in an n by n matrix, for a k by k patternSource 6. Here c and C are constants that depend only on the pattern. In words, the guarantee should shrink only like a power of ε.

This paper shows that this failsSource 7. It gives one fixed 66 by 66 pattern of zeros and ones. For each whole number h, it builds a square matrix n = (386h + 2)·2^h cells wide. For h = 1 that is 776. The matrix is far from pattern-free: at least one cell in (386h + 2)² must change. Yet its number of copies, divided by n^132, is at most that same fraction times 2^(−h). The fraction shrinks slowly as h grows, while 2^(−h) halves at every step. No fixed power of the fraction can keep up.

The difficulty is that removing copies can create new ones. A small set of cells can hit every existing copy. Here, all original copies pass through only 2^h cellsSource 8. But any repaired matrix must differ from the original in at least 4^h cellsSource 9. So changing those 2^h cells is never enough. The paper makes this happen by indexing rows and columns with a branching treeSource 10. Avoiding the pattern pushes conflicting values down the tree until they collide at its leaves.

Earlier examples of this kind of failure needed a third symbol in the big matrix. This one uses only 0 and 1Source 11.

How sure is this? A computer proof checker called Lean has checked a formal version of the main result. The Lean scope note says it covers the explicit 66 by 66 pattern and the sequence of matrices. It requires every zero and one to match, and it allows edits in both directions. No specialist review of the paper has been published.

What it doesn't show. This does not say how bad removal can get in general; it gives one pattern and one family of examples.