\documentclass[11pt,a4paper]{article} \usepackage[utf8]{inputenc} \usepackage[T1]{fontenc} \usepackage{lmodern} \usepackage{amsmath,amssymb,amsthm} \usepackage[margin=2.3cm]{geometry} \usepackage{booktabs} \newtheorem{theorem}{Theorem} \newtheorem{proposition}[theorem]{Proposition} \newtheorem{lemma}[theorem]{Lemma} \newtheorem{corollary}[theorem]{Corollary} \theoremstyle{definition} \newtheorem{definition}[theorem]{Definition} \newtheorem{remark}[theorem]{Remark} \newcommand{\lab}[1]{\textup{\textbf{[#1]}}} \title{The ordered $2\times2$ corner pattern: a removal exponent\\ of at least $9/2$, and other partial results} \author{David Niedbala Giraudin\\ \small Independent researcher, France} \date{20 November 2026} \begin{document} \maketitle \begin{abstract} Let $P=\begin{pmatrix}1&0\\1&1\end{pmatrix}$. An ordered induced copy of $P$ in a binary matrix is given by rows $ic$ in $y$ and not in $x$. \end{proof} \begin{definition} For rows $xc$ of $y\setminus x$; $d(x,y)$ is its minimum vertex cover. Given a cover, let $\Pi$ be just to the left of the leftmost common column not in the cover: the cover contains all common columns left of $\Pi$ and all columns of $y\setminus x$ right of $\Pi$. For an optimal cut, let $e$ and $h$ be the two numbers. To the right of $\Pi$, $y$ has $a-e$ common columns and $h$ others. If $h\le e$, the last $a$ ones of $y$ are these $a-e+h$ columns and $e-h$ more, and the symmetric difference has at most $2e$ elements. If $h>e$, the last $a$ ones of $y$ all lie to the right of $\Pi$ and the difference has at most $2h$ elements. \end{proof} \noindent\lab{computed} Both assertions were checked on $300\,000$ random pairs of rows. \section{Gluing consecutive intervals} \begin{theorem}[gluing $m$ intervals]\lab{proved}\label{thm:glue} Let $M$ have $n$ rows and $W$ columns, the columns being partitioned into $m$ consecutive intervals $I_1,\dots,I_m$ such that each restriction $M|_{I_j}$ is $P$-free. Suppose $d(x,y)\le K$ for all pairs of rows, with $K\ge1$, and put $s=\lceil2\sqrt{KW}\,\rceil$. Then $M$ can be made $P$-free by deleting fewer than $3ms$ ones in each row. In particular \[ D(M)<3mns\le 6m\,n\sqrt{KW}+3mn . \] \end{theorem} \begin{proof} If $K>W$ then $s>2W$ and deleting all ones costs at most $Wi$ this gives $\mathrm{Anc}_{z_1>\dots>z_H=z$. Extract $u_0=z_0$ and, while $u_i=z_t$ with $tt$ is the largest index with $a_{K$; it exists since $a_{s\ge K$. We reach $u_h=z$, and each hop has $p_j\le K$, so $|(y\cap I_j)\setminus z|\le hK$. For $0\le i\le h-2$ let $S_i$ be the set of the last $s+1$ ones of $u_{i+1}$ in the interval of its next link on the path. If $i'\ge i+2$ then $u_{i'+1}$ is higher on the path than $u_{i+2}$, so $a_{qs-\frac{Kq^2}2\ge\frac{qs}2\ge\frac{s^2}{4K}\ge W, \] which is impossible. Hence $h\le2q-1$ and $hK<2s$. Altogether fewer than $ms+2(m-1)s<3ms$ deletions per row. \end{proof} \noindent\lab{computed} The construction was programmed. On $741\,891$ random matrices with $2$ to $5$ $P$-free intervals the output is always $P$-free; the parameter $s$ being drawn at random, in the $17\,492$ cases with $s\ge2K$ and $s^2\ge4KW$ the cost bounds hold. \begin{remark}\label{rem:hops} The counting step uses neither $P$-freeness nor the shape of the rows. \lab{proved} In any matrix with $W$ columns, if $z_0>\dots>z_H$ are rows such that consecutive ones share more than $s$ columns, with $s\ge2K$ and $s^2\ge4KW$, one can go from $z_0$ to $z_H$ in fewer than $2s/K$ hops along the sequence, each hop joining two rows that share more than $K$ columns. \end{remark} \begin{corollary}\lab{proved} Call a matrix a \emph{staircase matrix} if its nonzero columns are partitioned into classes and every row, restricted to each class, is a final segment of that class. If the matrix has $n$ rows and $W$ columns, the classes form $R$ maximal runs of consecutive columns and $d\le K$ for all pairs of rows, with $K\ge1$, then $D<3Rn\lceil2\sqrt{KW}\,\rceil$. \end{corollary} \section{Two families limiting the gluing bounds} \begin{proposition}[chain family]\lab{proved}\label{prop:chain} Let $n_0\ge2$, $h\ge1$. Columns, from left to right: blocks $Q_{n_0},\dots,Q_1,Q_0$ of $h$ columns each (part $A$), then columns $e_{n_0},\dots,e_2$ (part $B$). The rows are $r_1,\dots,r_{n_0}$ from top to bottom, and $r_i$ consists of $Q_i$, $Q_{i-1}$ and the columns $e_j$ with $j\le i$. Then $M|_A$ and $M|_B$ are $P$-free, the matrix is a staircase matrix with $n_0+2$ classes, $d\le1$ for all pairs, and every $P$-free matrix differs from it in at least $\min(h/2,(n_0-1)/2)$ entries of some row. \end{proposition} \begin{proof} Rows $r_i,r_j$ with $j\ge i+2$ share no column of $A$, and $r_i\cap B$ is a final segment of $r_j\cap B$. For $j=i+1$ the common columns in $A$ are those of $Q_i$, a final segment of $r_{i+1}\cap A$, and the only later column of $r_{i+1}$ missing from $r_i$ is $e_{i+1}$. Suppose a $P$-free matrix changes at most $t$ entries per row with $2t\max_{x0$ and $a\ge0$ such that every $n\times n$ staircase matrix with $m$ classes and $d\le K$ for all pairs satisfies $D\le C\,m^a\,n^{3/2}\sqrt K$. Then every $n\times n$ matrix with $d\le\kappa n$ for all pairs of rows, $0<\kappa\le1$, satisfies $D\le C'\kappa^{1/(2a+3)}n^2$. \end{corollary} \begin{proof} If $\kappa n<1$ the matrix is $P$-free. Otherwise let $m=\lceil\kappa^{-1/(2a+3)}\rceil\le n$ and apply Theorem~\ref{thm:pivot} with $s=\lceil n/m\rceil$; the matrix obtained has at most $m$ classes, cost at most $\kappa mn^2+2n^2/m$ and pair distances at most $(2m+1)\kappa n$. The hypothesis adds $C\,m^an^{3/2}\sqrt{(2m+1)\kappa n}\le2C\,m^{a+1/2}\sqrt\kappa\,n^2$. \end{proof} \noindent By Theorem~\ref{thm:glue} the hypothesis of the corollary holds, with $a=1$, when the classes are intervals of columns. \lab{open} It is not known for interleaved classes. The step from the conclusion of the corollary to a polynomial removal lemma for $P$ is not treated in this note. \section{The row-block method does not transfer directly} Lupini \cite{L} proved polynomial removal for the ordered $2\times2$ identity. His short-span estimate keeps blocks of consecutive rows separated by zeroed rows, observes that a column pair is \emph{mixed} in at most one block, and repairs a block of $m$ rows with $Q$ mixed pairs at cost at most $2m\sqrt{2Q}$ by rows that are lattice polynomials of the rows of the block, which preserves compatibility between blocks. Write $x\,R\,y$ if the row $x$ placed above the row $y$ forms no copy of $P$. \begin{lemma}\lab{proved}\label{lem:lattice} For fixed $y$, $\{x: x\,R\,y\}$ is closed under coordinatewise minimum and maximum. For fixed $x$, $\{y: x\,R\,y\}$ is closed under coordinatewise minimum and under passing to a smaller row, but not under maximum. \end{lemma} \begin{proof} For fixed $y$ the condition is $x_c\le x_d$ for all $ci$, both carry a copy on columns $ct$, $y\in x_s$ and $x_t\cap x_s\cap I_{y-1}\ne\varnothing$ imply $s\in S$; \item[(G2)] for a cut $\Pi$ such that $U\cap F_\Pi\subseteq W$ and $U\cap I_\Pi$ is empty or has its last element in $W$, replace $U$ by $U\cup(W\cap F_\Pi)$. \end{itemize} Both moves preserve $\mathcal J(a)$. Hence, starting from $M$ and treating the adjacent pairs from bottom to top, applying moves \textup{(G1)}, \textup{(G2)} to the pair $(a,a+1)$ until it forms no copy (which \textup{(G1)} alone always achieves), one obtains a $P$-free matrix; $D$ is at most the number of entries changed. \end{theorem} \begin{proof} (G1) creates no copy in any matrix: a new copy on rows $ti$, $b\le j$, and the elements of $W_{abl}$ to the right of $c_{ibl}$ lie in $F_i\subseteq Q_{ij}$. The head of $W_{ijl'}$ meets $U_{abl}$ only in $c_{ijl}$, when $a=i$, $l'=l$, and the elements of $U_{ibl}$ to the right of $c_{ijl}$ lie in $Q_{ij}$; it meets $W_{abl}$ in two cases: if $b=j$, $l'=l$, then $W_{ijl}\supseteq W_{ajl}$; if $a=i$, $l'=l$, the least common element lies in $\mu_{i,l}$ and all elements of $W_{ibl}$ to its right ($\mu_{i,l}$, $e_{ib'l}$ for $b'i$, $x\cap y=y\setminus\xi_{a,l}$. If $a=i$, $x\cap y$ is $\{c_{ibl}\}_{b>j}\cup F_i$, enlarged to $y$ if $x=U_{ijl}$ and by $c_{ijl}$ if $x=W_{ijl}$. (D) \emph{$x=K_{i,l}$, $y$ below.} For $y$ in a bouquet $(a,b)$ with $a>i$, the head $\xi_{i,l}\cup\{c_{ibl}\}_b$ meets only $W_{abl}$, in $c_{ibl}$, and the elements of $W_{abl}$ to its right lie in $F_i$. Moreover $K_{i,l}\cap K_{a,l'}=K_{a,l'}\setminus\xi_{a,l'}$ for $a>i$ and $K_{i,l}\cap K_{i,l'}=F_i$ for $l\ne l'$. (E) \emph{$y=J_{b,l}$.} For $x$ in a bouquet or $x=K_{i,l'}$, $x\cap y$ is $y$ itself (if $x=W_{ibl}$) or of the form $\{c_{abl}:a\ge a_0\}$. (F) \emph{$y=R_{a,l}$.} $x\cap y$ is $y$ itself, or $\{e_{abl}:b>j\}$, or empty. Rows of type $J$ and $R$ are pairwise disjoint or equal. \end{proof} \begin{lemma}[rectangles]\lab{proved}\label{lem:rect} Let $R_1,\dots,R_m$ be rectangles $R_t=Z_t\times\Lambda_t$ in a grid, and let $\varepsilon_t$ be the number of $t'j$) in $e_{ijl}$; this is then the least common element, and the elements of $W_{ibl}$ to its right lie in $Q_{ij}$. For $y=K_{a,l'}$ or $J_{b,l'}$ nothing changes, since $e_{ijl}$ belongs to none of these rows outside $F_i$. For $y=R_{a,l'}$, $x\cap y$ is $y$ if $a>i$, empty if $aj\}$, together with $e_{ijl}$ when $l'=l$, if $a=i$. Finally $K_{i,l'}\cap U'_{abl}=U'_{abl}\setminus\xi_{a,l}$ for $a>i$. The cost is $p+1$ per conflict. \end{proof} \begin{corollary}\lab{proved} For matrices of row span one, the distance to $P$-freeness is not bounded by $C\,(S+n)$, where $S$ is the sum over adjacent pairs of rows of the distance of the pair: for $M(q,q,q)$, $S=n/6$. With $n/6$ copies at distance $(n/6)^{4/3}+n/6$, any removal exponent for $P$ is at least $9/2$. \end{corollary} \noindent\lab{computed} Exact distances obtained with a constraint solver (optimality proved) agree with the formula for $(q,s,p)=(2,1,1),\allowbreak(2,2,2),\allowbreak(2,3,3),\allowbreak(3,1,1),\allowbreak(3,2,2),\allowbreak(3,3,3),\allowbreak(4,1,1),\allowbreak(2,3,1),\allowbreak(2,3,2),\allowbreak(3,3,1)$; for $p>s$ the two bounds differ and the solver gives $25,17,62,17$ for $(2,2,3),\allowbreak(2,1,3),\allowbreak(3,1,2),\allowbreak(2,1,4)$. The ancillary script \texttt{verif\_cube.py} (plain Python) rebuilds $M(q,s,s)$ for six sizes up to side $882$ and checks Proposition~\ref{prop:cubeclass}, the entries used in the proof of Theorem~\ref{thm:cube}, and the repair of Proposition~\ref{prop:cubeupper}. The same construction can be carried out for more general incidence patterns between conflicts and blocks (rows of bouquets in which the classes of type $K$ are confined to one row and the classes of type $J$ meet each row at most once); this extension is not written out here. For $135\,421$ random patterns of this kind the matrix has row span one and the analogous repair is $P$-free, of cost (number of conflicts)$\times(p+1)$. \lab{open} Whether $D\le C\,n\sqrt m$ holds for span-one matrices with $m$ conflicts carrying one copy each; the family above gives $n\,m^{1/3}/6$. \section{Open questions} \begin{enumerate} \item \lab{open} Does $P$ admit a polynomial removal lemma? A literature search on 20 November 2026 (arXiv, Zenodo, public repositories and the public race board for this problem) found the obstructions of \cite{O,W,S} for larger patterns and the positive result \cite{L} for the identity, and nothing on $P$. \item \lab{open} Extend Theorem~\ref{thm:glue} to two interleaved $P$-free parts, or to $m$ interleaved staircase classes with a bound polynomial in $m$. \item \lab{open} Extend Theorem~\ref{thm:two} to three classes. \item \lab{open} Prove $D\le Cn^{2-\alpha}$ for matrices of row span one. \item \lab{open} Close the gap between the orders $n^{4/3}$ and $n^{3/2}$ for two $P$-free intervals with $K=1$. \end{enumerate} \paragraph{Ancillary files.} Three plain Python scripts, with fixed parameters and no external module: \texttt{verif\_corner\_note.py} (Lemmas~\ref{lem:cut} and~\ref{lem:thr}, Theorems~\ref{thm:glue} and~\ref{thm:two}, and the families of Propositions~\ref{prop:chain}, \ref{prop:windows} and~\ref{prop:lock}, on random and small instances), \texttt{verif\_portee1.py} (the section on row span one) and \texttt{verif\_cube.py} (the family $M(q,s,p)$). The first two print their messages in French. They test the statements on finitely many instances and are not part of the proofs. \paragraph{Acknowledgement.} This note was prepared with the assistance of Claude (Anthropic). \begin{thebibliography}{9} \bibitem{AB} N. Alon, O. Ben-Eliezer, Efficient removal lemmas for matrices, \emph{Order} 37 (2020), 83--101; arXiv:1609.04235. \bibitem{GS} L. Gishboliner, A. Shapira, Polynomial property testing, arXiv:2508.16878. \bibitem{L} M. Lupini, Polynomial removal for the ordered two-by-two identity matrix, preprint, Zenodo 23618367, 2 November 2026. \bibitem{O} OpenAI, Polynomial removal fails for ordered binary matrices, preprint, 25 September 2026. \bibitem{S} R. Shea, a $3\times3$ obstruction to polynomial removal for ordered binary matrices, public repository \texttt{shea256/ordered-binary-matrix-removal}, October 2026. \bibitem{W} Z. Wang, A four-by-four obstruction to polynomial removal for ordered binary matrices, arXiv:2610.15370. \end{thebibliography} \end{document}