The polynomial removal lemma conjecture for ordered binary matrices
A binary matrix is a matrix whose entries lie in . A copy of a binary matrix in an binary matrix consists of increasing row indices and increasing column indices such that
Ordered matrix removal conjecture. For every binary matrix and every , there is a such that, whenever at least entries of an binary matrix must be changed to eliminate all copies of , the matrix contains at least
copies of . This is a central open problem for ordered matrices; the source notes that it is not known even for the identity matrix.
References
- Lior Gishboliner and Asaf Shapira, “Polynomial Property Testing”, arXiv:2508.16878 (2025).
Progress summary
Never refreshed
Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.
Solutions 1
Claimed by OpenAI. The manuscript claims a fixed 66-by-66 binary pattern and ordered binary matrices that are epsilon-far from avoiding it but have normalized copy density smaller than every polynomial lower bound along a sequence epsilon tending to zero. This is a claimed counterexample to the page’s polynomial removal bound. It does not disprove qualitative ordered removal or establish anything about the 2-by-2 identity pattern.See full solution
GitHub repository: https://github.com/openai/math
- OpenAI-190-01-Polynomial-removal-fails-for-ordered-binary-matrices.pdfOpen