1 · The essentials
Consider a rectangular grid whose entries are all zeros or ones, and a smaller grid you want to avoid finding inside it. A match must keep the chosen rows and columns in their original order, and every zero and one must agree with the smaller grid. You may change entries in either direction to eliminate all matches. The question is whether needing many changes guarantees that matches are reasonably common, with a guarantee based on a fixed power of the fraction of entries that need changing. The manuscript gives one fixed pattern for which no such power-based guarantee works. Grids can be far from having no matches even though their matches are too rare for any proposed guarantee of this kind. The main result has a Lean formalization.
A picture to help (an imperfect image, not to be taken literally)
As an imperfect image, imagine a seating chart marked with zeros and ones, where you look for a particular smaller chart by selecting rows and columns without rearranging them. The result says that a particular target chart can be very rare among these selections, yet eliminating every occurrence can still require changing many marks.
Why it matters
The result separates two ways of measuring avoidance: how rarely a pattern appears and how much of a grid must be changed to remove it entirely. It disproves the polynomial ordered binary matrix-removal conjecture, rather than merely showing that one proposed power is insufficient. The requirements to preserve order and match both zeros and ones are part of the result.
2 · Going further
An ordered copy of a binary matrix is obtained by selecting rows and columns in increasing order and requiring every selected entry to match the corresponding pattern entry. The removal problem compares copy density with distance from being pattern-free, where distance is measured by the fraction of entries that must be changed. Both changes from zero to one and changes from one to zero are permitted.
The manuscript constructs a fixed binary matrix of size for which there is no polynomial ordered removal bound. For this pattern, matrices can require many entry changes to become pattern-free while their copy density falls below every proposed polynomial lower bound in that distance. The source identifies this as a disproof of the polynomial ordered binary matrix-removal conjecture.
The argument described in the abstract is a counterexample construction: one fixed pattern suffices to defeat all proposed polynomial bounds. The supplied abstract does not describe how that pattern or the accompanying matrices are constructed, so it does not support a more detailed account of the mechanism. The main result has a Lean formalization; no companion manuscripts or further details about the formalization's scope are supplied.
Useful notions
- Grids of zeros and ones
- Selecting rows and columns without reordering
- Fractions and powers
- Changing entries to eliminate a pattern
What was known before / what is new
Before
The source identifies a polynomial ordered binary matrix-removal conjecture as the claim being challenged. It supplies no earlier bounds, historical development, or attribution for that conjecture.
New
The manuscript provides one fixed binary pattern for which ordered removal admits no polynomial bound. The counterexample uses exact matching of both zeros and ones and allows entry changes in either direction. The main result has a Lean formalization.
Limits and assumptions
The result concerns ordered binary matrices: copies preserve the separate row and column orders and match every zero and one. It establishes failure of polynomial removal for one fixed pattern, not for every pattern, and does not assert the failure of all possible non-polynomial bounds. The main result has a Lean formalization, but the supplied source does not specify its scope beyond that designation. It provides neither construction details nor a list of remaining open questions.
Mini glossary
- Binary matrix —
- A rectangular array whose entries are zeros or ones.
- Ordered copy —
- A match to a pattern using selected rows and columns in their original orders, with both zeros and ones matching exactly.
- Pattern-free —
- Containing no ordered copy of the specified pattern.
- Copy density —
- The fraction of eligible row-and-column selections that form a copy of the pattern.
- Distance from being pattern-free —
- The smallest fraction of entries that must be changed to eliminate every copy of the pattern.
- Polynomial removal bound —
- A lower bound on copy density in terms of a fixed power of the distance from being pattern-free.
Keywords : Ordered binary matrices · Matrix removal · Polynomial bounds
AI-generated explanation based on the manuscript. Unofficial. Refer to the manuscript for the authoritative version.
3 · Technical details and sources
Claim made in the manuscript (source text)
Disproves polynomial ordered binary matrix removal with one fixed zero–one pattern. Matrices can require many binary-entry changes to become pattern-free while their copy density is smaller than every proposed polynomial bound in that distance. Copies preserve row and column orders and match both zeros and ones.
Verified by Lean: the Lean software checked the part of the reasoning described below, sometimes only part of the manuscript. This does not mean independent mathematicians have validated the result.
Manuscripts in this family
Polynomial removal fails for ordered binary matrices
25/09/2026We construct a fixed binary matrix for which ordered matrix removal has no polynomial bound. This disproves the polynomial ordered binary matrix-removal conjecture. Ordered copies preserve the separate row and column orders and match both zeros and ones; removal permits changing entries in either direction.