Failure of polynomial removal for ordered binary matrices

Source and verification

This article explains family 190 of the October 6, 2026 OpenAI collection. Research conclusions are attributed to its manuscripts. The review covers statements, introductions, and selected proof mechanisms; it is not an independent verification of the complete proofs.

🏷️ Ordered binary patterns and edit distance

An ordered copy of a fixed $k\times k$ binary matrix $H$ in an $n\times n$ binary matrix $A$ chooses increasing row indices and, independently, increasing column indices. Every selected entry must agree with $H$, including its zeros.

Let $N_H(A)$ count these copies. The normalized distance from $H$-freeness is the minimum fraction of the $n^2$ entries that must be changed to eliminate all copies. Entries can be changed in either direction, from zero to one or from one to zero.

A polynomial removal bound would assert that being $\epsilon$-far from $H$-free forces at least $c_H{\epsilon }^{C_H}{n}^{2k}$ copies. Qualitative removal gives some positive dependence on $\epsilon$; the conjecture asks whether that dependence can always be polynomial.

Manuscript claim

There is one fixed $66\times 66$ binary pattern $H$ and matrices $A_h$ with

$$\begin{array}{c}{n}_h=(386h+2)2^h,\\ {\epsilon }_h=(386h+2{)}^{-2},\end{array}$$

such that

$$\begin{array}{c}{\mathrm{dist}}_H(A_h)\ge {\epsilon }_h,\\ \frac{N_H(A_h)}{n_h^{132}}\le {\epsilon }_h{2}^{-h}.\end{array}$$

Consequently this fixed pattern has no polynomial removal bound. (OpenAI, 2026)

The host alphabet is exactly binary. The result concerns two independent orders on rows and columns, not unordered matrices or an ordered graph with one shared vertex order.

🏷️ Why the sequence defeats every polynomial

For any fixed $C>0$,

$$\begin{array}{c}\frac{{\epsilon }_h{2}^{-h}}{{\epsilon }_h^C}\\ =2^{-h}(386h+2{)}^{2(C-1)}\\ ⟶0.\end{array}$$

Exponential decay in $h$ beats every fixed power of $h$. Thus for any proposed positive constants $c,C$, sufficiently large $h$ gives a matrix at distance at least ${\epsilon }_h$ but copy density below $c{\epsilon }_h^C$.

There is no contradiction with qualitative removal: the distance parameters ${\epsilon }_h$ tend to zero. The construction disproves a uniform polynomial rate, not the existence of a positive rate for each fixed distance.

🏷️ Hitting old copies is not repairing a matrix

Every original copy in the construction meets one of only $2^h$ distinguished cells. It might therefore seem that changing those cells eliminates the pattern cheaply.

The problem is that editing can create new copies. To be $H$-free, the final matrix must avoid all copies after every change, not merely destroy copies present initially. The manuscript proves that any successful repair changes at least $4^h$ cells, despite the small hitting set for original copies.

Since $n_h^2=(386h+2{)}^2{4}^h$, this lower edit count gives exactly the distance scale $(386h+2{)}^{-2}$. The gap between hitting and repair is the central mechanism.

🏷️ Anchors and propagation down a tree

The last two rows and columns of $H$ contain the pattern

$$P=\left(\begin{array}{cc}1& 0\\ 1& 1\end{array}\right).$$

The first 64 rows and columns form an anchor specifying which host rows and columns can play those final roles. The host has many anchors imposing different instances of the same two-by-two restriction.

Rows and columns are organized by a binary tree, with plus and minus blocks at internal nodes. At a leaf, the two blocks on each axis coincide. Two root entries have opposite values. Avoiding the designated $P$ patterns propagates those values down a common path, first through a row level and then a column level. At the leaf, opposite values would be forced into the same position, which is impossible.

To make this an edit-distance proof, the source samples a path together with anchor and auxiliary positions in an arbitrary edited matrix. Each needed cell is selected with probability $m^{-2}$ for $m=2^h$. Summing over changed cells shows that fewer than $m^2$ edits leave one suitable collection of anchors, auxiliary incidences, and root values unchanged.

All other entries may have changed. The propagation uses avoidance of $H$ in the edited matrix itself, so it still forces the contradiction. This is what turns the argument into a lower bound against every repair strategy.

🏷️ Counting every original copy

The copy-density estimate is a separate obligation. It must locate all copies in the unedited host, not just the designated ones used for propagation.

Dense rows and columns, together with a small block realizing all binary words of a fixed length, force an anchor into one of the prescribed anchor blocks. The remaining rows and columns then have fixed roles. Order and threshold rules force every copy to use a diagonal leaf cell, yielding the small count.

The same source derives a lower bound for a specific canonical tester: independently sample $q$ rows and $q$ columns and reject only upon finding $H$ in the sampled submatrix. Along the construction, fixed positive rejection probability requires $q\ge \exp (\Omega ({\epsilon }_h^{-1/2}))$. Here $q$ counts sampled positions on each axis, while $q^2$ entries are inspected. This conclusion is about that testing model, not every possible adaptive algorithm.

🏷️ Key steps and proof outlines

Sample one untouched chain against an arbitrary repair

Fix an edited matrix $B$ differing from the constructed matrix in a set $E$ of fewer than $m^2$ cells, where $m=2^h$. Choose a uniform leaf label $z\in \{0,\dots ,m-1\}$ and its ancestors

$$a_i=\lfloor \frac{z}{2^{h-i}}\rfloor ,0\le i\le h.$$

At level $i$, choose row and column positions uniformly in the plus and minus blocks belonging to $a_i$. Use the same plus and minus position at the leaf, where those blocks coincide. Independently choose a position in each anchor and dummy class. (OpenAI, 2026)

Each variable position is uniform in its entire size-$m$ class: its node is selected with probability $2^{-i}$ and its node block has size $m/2^i$, so the product is $1/m$. The needed independence across axes holds for anchor and dummy incidences, and for the two root coordinates. Thus each cell of these particular types is sampled with probability $m^{-2}$.

The union bound protects only the required cells

The probability that any selected anchor incidence, dummy incidence, or root entry was edited is at most $|E|/m^2<1$. Hence one selection leaves all of them unchanged. The proof makes no claim that arbitrary variable-variable cells along the selected path remain unchanged; their values will instead be forced by avoidance of the forbidden pattern.

This is why the argument works against simultaneous changes in both directions, including changes that create new copies.

The two-by-two rule propagates both a one and a zero

The selected anchors identify valid row and column roles. If $B$ were $H$-free, none of the corresponding bodies could equal

$$P=\left(\begin{array}{cc}1& 0\\ 1& 1\end{array}\right).$$

Suppose the plus and minus diagonal entries at level $i-1$ are respectively one and zero. The vertical modes supply bodies

$$\left(\begin{array}{cc}1& b_{+}\\ 1& 1\end{array}\right),\left(\begin{array}{cc}1& 0\\ 1& b_{-}\end{array}\right),$$

where $b_{\pm }$ are entries from a level-$i$ row to a level-$(i-1)$ column. The dummy column gives the left-hand ones. Avoiding $P$ forces $b_{+}=1$ and $b_{-}=0$.

The horizontal modes then supply

$$\left(\begin{array}{cc}1& c_{+}\\ 1& 1\end{array}\right),\left(\begin{array}{cc}{c}_{-}& 0\\ 1& 1\end{array}\right),$$

with $c_{\pm }$ the new level-$i$ diagonal entries. The unchanged dummy row gives the bottom ones, so avoidance forces $c_{+}=1$ and $c_{-}=0$. The unchanged root starts this induction. At the leaf both entries are the same cell, giving the contradiction $1=0$. Thus every repair requires at least $m^2$ edits, and division by $n^2=((386h+2)m{)}^2$ gives the stated distance.

Count original copies by a different argument

The anchor-pinning lemma first shows that every original copy uses the prescribed roles of one mode. It is an indispensable separate input: the designated propagation copies need not exhaust all copies without it.

Write $\pi (p)=\lfloor p/2\rfloor$ for the parent of a node. In a plus vertical mode, row order gives $\pi (p)\le a$, while the required bottom-right one gives $a\le b$. The construction therefore makes the top-right entry one, contrary to $P$. The minus vertical mode reverses these inequalities and likewise contradicts the required bottom-right one.

In a horizontal mode, the child row and column indices have the same parity. Parent inequalities can therefore be converted into child inequalities. The plus case again contradicts the top-right zero. The minus case is impossible at internal levels, where the entry rule is the strict comparison $1[p<q]$. Only at the shared leaf does that rule become $1[p\le q]$, permitting precisely $p=q$.

Every original copy therefore sends one fixed pattern entry to one of $m$ diagonal leaf cells. Fixing that row and column leaves at most $n^{130}$ choices for the other indices, so $N_H(A_h)\le m{n}^{130}$. Dividing by $n^{132}$ gives the exponentially small density.

Changing those $m$ cells destroys every original copy, but creates a plus horizontal body $P$ at each changed leaf: the parent-child one and dummy row remain. This explicit example explains why a small hitting set does not contradict the much larger repair distance. The distance and copy-count sections establish these two obligations separately.

See Also

• Random triangle removal concerns a stochastic packing process; its use of “removal” is different from the edit-distance notion here.
• Snaky also uses tree-organized finite constraints, but to preserve a winning continuation under one adversarial move at a time.

🏷️ Manuscripts and verification scope

• Polynomial removal fails for ordered binary matrices — pinned manuscript and companion source.

The family scope page describes selected formalization coverage. The page selects the fixed 66-by-66 binary obstruction, with independently ordered rows and columns and edits allowed in both directions. No Lean build, axiom audit, or manuscript-to-formal-statement equivalence check was performed for these notes.

OpenAI collection provides prerequisites and the reading sequence; coverage register records completed and pending families.

🐻  OpenAI 2026. Polynomial removal fails for ordered binary matrices.