Why rare ordered binary patterns can be hard to remove

← All digests

Family 190 · Combinatorics
Importance 2/5 · Provisional editorial rating
Sources consulted 2026-10-11

1. The question

Suppose a large table contains only zeros and ones. A small forbidden pattern appears when certain rows and columns, read in their original orders, reproduce a prescribed binary matrix. If the table contains very few such appearances, can we eliminate all of them by changing a small number of entries?

A qualitative removal theorem says yes: sufficiently few appearances imply that the table is close to one with none. The quantitative question is how few appearances are needed. Can the relation between the fraction of changed entries and the density of forbidden patterns always be expressed by a fixed power?

The manuscript in this family claims a negative answer for a single explicitly specified $66\times66$ binary pattern. Its examples contain exceptionally few copies relative to the amount of editing needed to remove the pattern.

A subtlety drives the construction. Changing one cell can destroy an existing occurrence while creating another. A small set of cells touching all current violations therefore need not give a cheap repair. Ordered binary matrices provide a setting where that distinction becomes a strong quantitative obstruction.

2. Background and essential definitions

Copies preserve both orders and both symbols

Let $A$ be an $n\times n$ matrix with entries in $\{0,1\}$, and let $H$ be a fixed $k\times k$ binary matrix. An ordered copy of $H$ is a choice of rows and columns

$$r_1<\cdots<r_k,\qquad c_1<\cdots<c_k$$

such that $A(r_i,c_j)=H(i,j)$ for every $i,j$. The row and column choices are separate; their indices need not be equal.

The chosen positions need not be consecutive. However, we may not rearrange them after selection. A copy must match zeros as well as ones, so it is not enough to find all the locations where $H$ has a one.

Write $N_H(A)$ for the number of copies. The matrix is $H$-free if this count is zero. Its normalized editing distance from being $H$-free is

$$\operatorname{dist}_H(A) =\frac{1}{n^2}\min_{B\text{ is }H\text{-free}} \bigl|\{(r,c):A(r,c)\ne B(r,c)\}\bigr|.$$

Both kinds of changes, zero to one and one to zero, are allowed. Saying that $A$ is $\varepsilon$-far means that every successful repair changes at least $\varepsilon n^2$ cells.

What a polynomial removal bound would say

There are at most $n^{2k}$ choices of $k$ rows and $k$ columns, so $N_H(A)/n^{2k}$ is a convenient copy-density normalization. A polynomial removal statement would provide constants $c_H,C_H>0$, depending only on the fixed pattern, such that

$$\frac{N_H(A)}{n^{2k}}\ge c_H\varepsilon^{C_H} \quad\text{whenever}\quad \operatorname{dist}_H(A)\ge\varepsilon.$$

In words, a table requiring substantial editing would necessarily contain a polynomially large density of visible violations. The exponent may be large, but it must stay fixed as the table and accuracy parameter vary.

A qualitative removal bound asks only for some positive function of $\varepsilon$, which can decrease far faster than every power. The distinction between these two demands is the problem’s central issue.

3. Development history and previous partial results

Alon, Fischer, and Newman developed efficient testing results for forbidden binary matrix patterns when row and column order is ignored. Their 2007 work also raised the ordered question. Retaining order changes which patterns count as copies, so the unordered conclusion cannot simply be transferred.

Alon, Ben-Eliezer, and Fischer established qualitative removal for ordered matrices in 2017. Thus a fixed positive editing distance already guaranteed a positive density of forbidden patterns. The open issue was the rate at which that guarantee deteriorates as the permitted editing fraction shrinks. Their paper treats ordered graphs and matrices in a broader testing framework.

Alon and Ben-Eliezer’s Efficient removal lemmas for matrices obtained polynomial bounds in important cases, including finite forbidden families closed under row permutations, or under column permutations by transposition. They also proved a useful result relating many copies that are disjoint in cells to polynomial copy density. Their work formulated the remaining general binary-matrix question. The article supplies these positive results and the quantitative problem.

A singleton version, concerning just one forbidden binary matrix, appears in the first version of Gishboliner and Shapira’s 2025 survey. M1 claims to disprove that version, and consequently the more general finite-family proposal as well.

Earlier negative examples used a third symbol in the large host matrix. Even if the forbidden pattern used only two symbols, that additional symbol changed the available repairs. M1’s construction keeps both the pattern and the host genuinely binary. It also concerns separate row and column orders, rather than the single order and symmetric adjacency of an ordered graph.

4. What the new manuscripts claim

The family contains one manuscript, M1. It specifies a fixed binary matrix $H$ of size $66\times66$. For every integer $h\ge1$, it constructs a square binary matrix $A_h$ of side length

$$n_h=(386h+2)2^h$$

and sets

$$\varepsilon_h=(386h+2)^{-2}.$$

The claimed estimates are

$$\operatorname{dist}_H(A_h)\ge\varepsilon_h, \qquad \frac{N_H(A_h)}{n_h^{132}}\le\varepsilon_h2^{-h}.$$

The exponent 132 is twice the pattern size, because a copy selects 66 row positions and 66 column positions. The same $H$ is used for every $h$.

The distance parameter decreases roughly as $h^{-2}$, while the additional factor $2^{-h}$ decreases exponentially. For every fixed positive $c$ and $C$, the ratio of the displayed copy-density upper bound to $c\varepsilon_h^C$ eventually tends to zero. This is how the claimed sequence contradicts every polynomial removal bound for that one pattern.

M1 also states a consequence for a specific canonical tester: independently sample $q$ row positions and $q$ column positions, inspect their ordered submatrix, and reject only if it contains $H$. Along the construction sequence, a fixed positive rejection probability requires

$$q\ge \exp\bigl(\Omega(\varepsilon_h^{-1/2})\bigr).$$

Here $\Omega$ indicates a positive constant multiple in the exponent for sufficiently large $h$. The sample has $q$ positions on each axis and $q^2$ inspected entries. This is a statement about that sampling procedure, not every conceivable testing algorithm.

5. Why the advance matters

Importance: 2/5. The claim settles a specific quantitative conjecture in ordered matrix removal and supplies a concrete obstruction to a natural sampling strategy. Its significance is concentrated in property testing and extremal matrix theory.

A removal lemma connects a global property, distance from any successful repair, with local evidence, the number of forbidden patterns. Polynomial bounds make that connection especially useful because the required local search remains controlled as the accuracy demand becomes stricter.

The claimed construction shows that ordering and binary editing can frustrate this expectation even for one fixed pattern. Its conceptual lesson is wider than the numerical size 66: repairing violations is a dynamic problem, because changing a cell can move the obstruction rather than eliminate it.

The result preserves the qualitative removal theorem. For each fixed positive distance there is still some positive copy-density guarantee. What fails is the expectation that a fixed power always suffices.

6. The main idea

A small pattern transmits constraints

The lower-right corner of $H$ is the two-by-two pattern

$$P=\begin{pmatrix}1&0\\1&1\end{pmatrix}.$$

The other 64 rows and columns form an anchor: a larger pattern that identifies which rows and columns may play the roles in this small corner. This prevents an intended local restriction from drifting to unrelated positions in the host matrix.

Avoiding $P$ can impose inequalities between binary entries. For example,

$$\begin{pmatrix}1&a\\1&b\end{pmatrix}\ne P \quad\Longleftrightarrow\quad b\le a, \qquad a,b\in\{0,1\}.$$

The forbidden case is exactly $a=0,b=1$. Such a restriction can transmit a known zero or one from one location to another. M1 uses anchored versions of these implications in both row and column directions.

Arrange the implications on a tree

The host positions are organized around a binary tree of depth $h$. Each internal node has plus and minus blocks on both axes. At a leaf, the two named blocks coincide. The row and column orders are chosen differently so that an ordered copy imposes the intended relation between successive levels.

Two root entries begin with opposite values. If an edited matrix avoids the forbidden pattern while retaining suitable anchors, the restrictions propagate those values down a common tree path. At the bottom, the plus and minus roles occupy the same positions. They cannot still carry opposite values.

To turn this contradiction into a distance estimate, the paper samples a path and the necessary anchor and auxiliary positions. Its argument states that fewer than $4^h$ edits leave a suitable selection untouched. The propagation contradiction then forces every successful repair to make at least $4^h$ changes, which equals $\varepsilon_h n_h^2$.

Make all original violations rare

A separate part of the argument locates every copy in the unedited host. The anchor contains dense rows and columns together with a block encoding all five-bit words. According to M1, these features force any occurrence into the prescribed roles.

The resulting copies must use one of only $2^h$ distinguished leaf cells. That bottleneck gives the small copy count and the sampling lower bound: a randomly selected submatrix is unlikely even to encounter a cell through which every violation must pass.

Notice the two scales. All original copies meet a set of $2^h$ cells, yet the claimed minimum repair uses at least $4^h$ edits. Simply changing the cells in that small meeting set does not solve the problem, because the edits can create new copies. The tree mechanism is designed to make that gap persist.

7. Scope, limitations, and open questions

The counterexample uses one particular $66\times66$ pattern. It does not claim that all ordered binary patterns have nonpolynomial removal bounds, or that 66 is the smallest possible size for a negative example.

Matching both symbols and preserving both orders are essential parts of the model. Ignoring order, allowing a third host symbol, forbidding only selected one-entries, or permitting only one direction of editing would pose different questions.

The lower bounds occur along the explicit sequence $\varepsilon_h$. That is enough to refute a bound intended to hold for every positive $\varepsilon$. It is not an exact determination of the best removal function at every distance.

The testing consequence concerns independent uniform row and column sampling followed by rejection only on a witnessed copy. Claims about adaptive queries, different rejection rules, or unrestricted testing complexity would require additional arguments.

A natural remaining task is to classify which ordered binary patterns admit polynomial bounds and to locate the smallest obstructions. The manuscript supplies a negative example, while the earlier positive subclasses show that the landscape is not uniform.

8. Sources and further reading

• Alon, Ben-Eliezer, and Fischer, Testing hereditary properties of ordered graphs and matrices, for qualitative ordered removal.
• Alon and Ben-Eliezer, Efficient removal lemmas for matrices, for polynomial positive cases and the earlier question.
• Gishboliner and Shapira, Polynomial property testing, version 1, for the singleton conjecture cited by M1.

M1 gives the complete binary anchor, the ordered tree matrices, and the stated repair and copy-count estimates.

Source manuscripts

• M1. OpenAI, Polynomial removal fails for ordered binary matrices (September 25, 2026).

Sources consulted on 11 October 2026 at repository revision fd4aeeb. Download the manuscript citations.