No polynomial bound?

0:00The question

Take a grid of zeros and ones, with its rows in a fixed order and its columns in a fixed order. A small pattern, like this 2-by-2 grid with one zero and three ones, has an ordered copy wherever you can choose some rows, top to bottom, and some columns, left to right, chosen independently, so that the big grid shows exactly the pattern, zeros as well as ones. This 4-by-4 grid contains 8 copies. Now ask how far a grid is from having none: the fewest entries you must flip, either way, as a fraction of all its entries. A removal lemma says that a grid far from pattern-free must contain many copies, a fraction of all possible choices that depends only on the distance. In our exhaustive search of 4-by-4 grids, the farthest from free of this pattern need 4 flips, and each of them has at least 9 copies. The question is how fast that guaranteed fraction must shrink as the distance shrinks. If it shrinks only like a power of the distance, removal is called polynomial. As the paper tells it, Alon, Fischer and Newman raised the ordered-matrix question, after proving polynomial testing when row and column order is ignored. Alon and Ben-Eliezer formulated the polynomial removal question for finite families of patterns, and the conjecture for a single pattern appears in a 2025 survey by Gishboliner and Shapira, which itself calls it one of the key open problems in the area. Alon, Ben-Eliezer and Fischer had proved the qualitative version: some positive fraction always exists. Polynomial bounds were known for families closed under row permutations, or column permutations. And polynomial removal was already known to fail when the big grid may use a third symbol, even with order ignored, by Fischer and Rozenberg, and in a related construction of Alon and Ben-Eliezer. For grids of only zeros and ones, the conjecture stood.

1:59The claim

Result 190 is one OpenAI preprint, 12 pages, dated September 25, 2026. It claims a counterexample: one fixed 66-by-66 pattern H, and for every positive whole number h, a grid with (386h+2)·2^h rows and columns. Each of these grids needs at least a fraction 1/(386h+2)² of its entries flipped to be free of H, yet its fraction of copies is smaller than that by a further factor of 2^(−h). Since 2^(−h) shrinks faster than any power of one over h, no bound of the form a constant times a power of the distance can hold for this pattern. The first grid already has 776 rows. The paper also derives a lower bound for one natural sampling test. Not claimed: that removal fails for every pattern. This is one pattern of size 66, with no claim that it is the smallest, and nothing about small patterns. Removal itself is not refuted: the qualitative version still holds, and only polynomial dependence fails. The distance does not stay large: the required fraction tends to zero, just much more slowly than the copies vanish. The examples are explicit but huge: by our arithmetic, the paper’s bound first beats the square of the distance at h = 27, a grid with about 10^12 rows. And the testing bound covers only the test that samples random rows and columns and looks for the pattern.

3:37How the proof goes

The pattern has two parts. The paper calls the big one the anchor: 64-by-64, all ones except a diagonal of zeros, with a corner strip whose 32 rows spell out every 5-bit word. The small part is the body: one zero and three ones in the bottom-right corner, wired to the anchor by single ones. The body acts like a logic gate. In a 2-by-2 whose left column is all ones, avoiding the body forces the bottom-right entry to be at most the top-right one: if the smaller entry is one, the larger is forced to one, and if the larger is zero, the smaller is forced to zero. The anchor’s job is to pin down which rows and columns can play the body’s roles. The big grid lays out a binary tree on its rows and another on its columns, with a plus block and a minus block at every node, in mirror-image orders. At the root, the plus entry is one and the minus entry is zero. At each leaf, plus and minus are the same single row and the same single column. In front sit many copies of the anchor, one family for each mode, six modes per level of the tree, each wiring the gate between neighbouring levels. Here is the whole non-anchor part of the first grid, 8 by 8. Now suppose someone flips fewer than 4^h entries. Pick a random root-to-leaf path, with random anchor and dummy positions: each flipped cell lands on a protected spot with chance at most 1/4^h, so some choice survives untouched. If the edited grid had no copy of H, the gates would carry the root’s one down the plus side, level by level, rows then columns, and the root’s zero down the minus side. At the leaf, plus and minus are the same cell, which cannot be both. So at least 4^h flips are needed: a fraction 1/(386h+2)². Why are copies rare? Look for every copy in the unedited grid. The 5-bit strip needs 5 columns showing all 32 words, but on tree and dummy rows, any five tree or dummy columns show at most 27, so a copy must use anchor positions. Density, and the zeros between modes, then force its whole anchor part into one mode’s block, and the body into that mode’s designated rows and columns. The order and threshold rules then rule out the body everywhere except at a leaf, where the shared cell lies on the diagonal. So every copy passes through one of only 2^h cells, which leaves at most 2^h/n² of all choices. Our brute force for h up to 4 agrees: every placement of the body in a mode’s designated rows and columns sits on the leaf diagonal. And the twist: those 2^h cells meet every copy, yet flipping them creates new copies, and any repair needs at least 4^h changes. The same thing happens in this small grid of ours: one cell meets both copies, and flipping it makes a new one.

6:34Where it stands

The preprint is unrefereed and has not been revised. OpenAI’s Lean files state the paper’s pattern exactly, with the exact definitions of ordered copies and of distance, flips in both directions, and prove that no polynomial bound holds; they also prove the explicit sequence of grids. That is 61 files and about 7,600 lines, with no gaps we could find by search; we did not run the check. The sampling corollary and the remark about repairs are not formalized. The paper is not among those OSVerify reviewed, and we have seen no expert review. If it holds, ordered removal for zero-one grids has no polynomial bound: for this one 66-by-66 pattern, grids can be far from free of it while its copies are rarer than any power of the distance.