oai-math-revised beta

Browse › Combinatorics › 190 Polynomial removal fails for ordered binary matrices

Polynomial removal fails for ordered binary matrices

OpenAI · September 25, 2026

Lean

Open PDFCite Report a problem Add a reference or comment Interested in working on this Start a discussion

Edit NOTES.md · Existing issues · Source on GitHub

Abstract

We construct a fixed $66\times66$ 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.

If the PDF does not display here, open it directly: Open PDF.

Notes

No notes yet. Add a reference, a comment or your name with the buttons above, or edit NOTES.md on GitHub.

Automatically collected notes (unreviewed)

work in progress

Collected automatically by AI tools (Claude Opus 5.5 and GPT-6 Astra, 2026-10-21) and not checked by a person. May be wrong or incomplete. Report an error.

Follow-up works

  • Zinan Wang, A Four-by-Four Obstruction to Polynomial Removal for Ordered Binary Matrices (arXiv:2610.15370 [cs.DM], 2026-10-11). Cites this paper and, following its tree-propagation approach, reports a fixed $4\times4$ pattern with no polynomial removal bound, with exact induced-copy counts, unrestricted editing distance and a Lean formalization.
  • Zinan Wang and Xinhao Yang, h4-ordered-matrix-removal (GitHub repository, announced 2026-10-11). Manuscript and Lean 4 package for the $4\times4$ obstruction, copy counts and edit distance, with reproduction scripts; the README says the construction "builds on the tree-propagation approach" of this paper.
  • Erebos Labs, ordered-matrix-removal-4x4, release v1.0.0 (GitHub release, 2026-10-09; v1.1.0 claims the exact repair distance $m^2$). Lean-checked obstruction for the $4\times4$ pattern with rows 0110, 1001, 1010, 0111, crediting this paper's signed-tree construction; it says its reviews were AI-assisted.
  • Ryan Shea, ordered-binary-matrix-removal (GitHub repository, README dated 2026-10-12; PR #10). Claims the $3\times3$ pattern 011/101/110 has no polynomial removal bound, checked in Lean, with tree and propagation ideas credited to this paper's $66\times66$ construction; prepared "with Codex assistance", peer review pending. [AI-generated per source]

Formalization

Possibly relevant literature (found by the agent, not checked)

Elsewhere

Independent sites; their content is not reviewed here.

Cite

@misc{OAI:Polynomial-removal-fails-for-ordered-binary-matrices-September-25-2026,
  author = {{OpenAI}},
  title = {{Polynomial removal fails for ordered binary matrices}},
  howpublished = {OpenAI Math Release preprint
                  \href{https://github.com/openai/math/blob/main/preprints/Polynomial-removal-fails-for-ordered-binary-matrices-September-25-2026/paper.pdf}{OAI:Polynomial-removal-fails-for-ordered-binary-matrices-September-25-2026}},
  year = {2026}
}

Lean formalization

OpenAI provides Lean files for this family: lean/docs/190.md. The Lean statements have not been checked by people against the paper's claims.

Family 190: Polynomial removal fails for ordered binary matrices

Disproves polynomial ordered binary matrix removal with one fixed $66\times66$ 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.

This is the only paper in this family.