Polynomial removal fails for ordered binary matrices
There is a fixed binary matrix for which ordered matrix removal has no polynomial bound, disproving the polynomial ordered binary matrix-removal conjecture; specifically, for every integer , with and , there is a binary matrix such that and .
The construction of H and A_h, the distance lower bound (Proposition 3.1), the copy-count upper bound (Proposition 4.6), and the asymptotic limit in Section 5 are all complete and mathematically sound.
“Theorem 1.1. There is a fixed binary 66 × 66 matrix H with the following property. For every integer h ≥ 1, put nh = (386h + 2)2h, ϵh = (386h + 2)−2. There is a binary nh × nh matrix Ah such that distH(Ah) ≥ ϵh, NH(Ah)/n132h ≤ ϵh2−h. Consequently, no positive constants c, C give a polynomial removal bound for this fixed H.” · Show in paper