A four by four matrix reveals limits on polynomial pattern removal
A Four-by-Four Obstruction to Polynomial Removal for Ordered Binary Matrices
Discrete Mathematics
Summary
The paper shows a specific small binary matrix that challenges how easily certain patterns can be removed from larger ordered binary matrices. The authors prove that for this pattern, no method can remove all its occurrences with a polynomial amount of editing. They use a careful counting argument and formal verification to show an infinite gap between removing some of these pattern copies and completely eliminating all of them. This suggests fundamental limits on algorithms attempting to clean such data by editing few entries.
What this means in practice
- •For algorithm designers: Recognize fundamental limits on algorithms that attempt to edit ordered binary matrices to remove all copies of certain fixed small patterns efficiently.
- •For database engineers: Understand cases where minimal data edits cannot guarantee full pattern elimination, informing data cleaning strategies in order-sensitive data.
A theory result. No direct application yet.
Authors
Zinan Wang
Abstract
We exhibit a fixed $4\times 4$ binary matrix with no polynomial induced ordered removal bound. At depth $h\geq 1$, let $m=2^h$. Our explicit host has order $(14h+2)m$, exactly $2m^6+\frac{1}{2}(m-2)m^5$ induced copies, and exact editing distance $m^2$ cells. Its normalized editing distance is $Θ(h^{-2})$, while its induced-copy density is $Θ(4^{-h}h^{-8})$. The lower bound holds against arbitrary cell edits through an injective family of $m^2$ protected selections. An exhaustive arithmetic classification identifies every induced copy and proves that a matching canonical repair creates none. The original-copy transversal number is exactly $m$, yielding an unbounded gap between hitting existing copies and eliminating all copies. The identities and the obstruction at every depth are formalized in Lean, with verification sources included as ancillary files.