WorksMathematics
The ordered 2x2 corner pattern: a removal exponent of at least 9/2, and other partial results
Abstract
Let P = [[1,0],[1,1]]. An ordered induced copy of P in a binary matrix is given by rows i<j and columns c<d with entries (1,0) in row i and (1,1) in row j. Whether P admits a polynomial removal lemma is, to our knowledge, open; it is the last open 2x2 case. This note does not settle it and records partial results. Main result: for every q >= 2 we construct a square binary matrix of side n = 6q^3, with exactly n/6 copies of P, each on a pair of adjacent rows, these pairs being disjoint, whose distance to P-freeness is exactly (n/6)^{4/3} + n/6 entry changes; consequently any removal exponent for P is at least 9/2. Further results: (1) if the columns are split into m consecutive intervals on each of which the matrix is P-free, and any two rows can be made P-free by deleting at most K columns, then the n x n matrix is within 6 m n^{3/2} sqrt(K) + 3mn entry changes of a P-free matrix; (2) two explicit families show that no bound of the form CK per row, or CKn in total, holds with an absolute constant, even for two intervals; (3) for matrices made of two interleaved "staircase" classes we give a repair with at most 4K changes per row; (4) the block-repair lemma used by Lupini for the 2x2 identity has no direct analogue for P; (5) for matrices in which every copy uses two adjacent rows, we give two safe repair moves and a matrix with a single copy at linear distance from P-freeness. Statements are labelled proved, computed or open. The results are established facts whose novelty has not been verified. The note was prepared with an AI model; the proofs were examined by independent AI reviews and by computation, and nothing has been checked by a third party.
Setting
The general polynomial removal question for ordered binary matrices is surveyed in [2]; [1] proves it for finite families closed under row permutations, and a weak form (a small set of entries meeting all copies) for every single pattern.
Matrices are binary; rows are numbered from top to bottom and columns from left to right. A row is identified with the set of its columns containing a 1. For a matrix , is the minimum number of entry changes (in either direction) producing a -free matrix.
Lemma 1. [proved] A matrix is -free if and only if, for all rows , the set is a final segment of (every column of to the right of a common column is common). Equivalently: for every column , the rows containing , read from top to bottom and restricted to the columns to the right of , are decreasing for inclusion.
Proof. A copy is a pair of rows containing together with a column in and not in .
Definition 2. For rows , is the minimum number of columns whose deletion makes the pair -free.
Lemma 3 (cut formula). [proved] For rows with a common columns,
the minimum being over cut positions . Moreover the set of common columns differs from the set of the last ones of in at most columns.
Proof. The copies of the pair are the edges of the bipartite graph joining a common column to a column of ; is its minimum vertex cover. Given a cover, let be just to the left of the leftmost common column not in the cover: the cover contains all common columns left of and all columns of right of . For an optimal cut, let and be the two numbers. To the right of , has common columns and others. If , the last ones of are these columns and more, and the symmetric difference has at most elements. If , the last ones of all lie to the right of and the difference has at most elements.
[computed] Both assertions were checked on random pairs of rows.
Gluing consecutive intervals
Theorem 4 (gluing intervals). [proved] Let have rows and columns, the columns being partitioned into consecutive intervals such that each restriction is -free. Suppose for all pairs of rows, with , and put . Then can be made -free by deleting fewer than ones in each row. In particular
Proof. If then and deleting all ones costs at most per row; so assume . For a finite set of columns let be without its largest elements. Say that rows are linked through if . Since is -free, the common columns in form a final segment of ; a common column that is not among the last of therefore forces more than common columns in . Let be the set of rows reached from by going up through links of indices , step by step. Define
is -free. Inside : for above , is an initial segment of , so is minus an initial segment. Removing initial segments keeps -freeness: if are kept in and is kept in , then (final segment) and is to the right of , hence kept in . Removing the last ones of every row also keeps -freeness: if with common, kept in and removed from , then has at least ones after , all in , so is not among the last ones of . Across intervals: if share a column of in , they are linked through , because whenever . For this gives , hence and (an element with successors in has successors in ). So no copy has its common column in and its other column in .
Cost in . At most for , plus over (the sets are nested initial segments). Let be the number of common columns to the left of and the number of columns of not in . Every column left of precedes every column of , so . Fix a path of links . Extract and, while with , let where is the largest index with ; it exists since . We reach , and each hop has , so .
For let be the set of the last ones of in the interval of its next link on the path. If then is higher on the path than , so by the
choice of , and . Put ; since we have and . If , the sets have a union of size at least
which is impossible. Hence and . Altogether fewer than deletions per row.
[computed] The construction was programmed. On 741 891 random matrices with 2 to 5 -free intervals the output is always -free; the parameter being drawn at random, in the 17 492 cases with and the cost bounds hold.
Remark 5. The counting step uses neither -freeness nor the shape of the rows. [proved] In any matrix with columns, if are rows such that consecutive ones share more than columns, with and , one can go from to in fewer than hops along the sequence, each hop joining two rows that share more than columns.
Corollary 6. [proved] Call a matrix a 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 rows and columns, the classes form maximal runs of consecutive columns and for all pairs of rows, with , then .
Two families limiting the gluing bounds
Proposition 7 (chain family). [proved] Let , . Columns, from left to right: blocks of columns each (part A), then columns (part B). The rows are from top to bottom, and consists of , and the columns with . Then and are -free, the matrix is a staircase matrix with classes, for all pairs, and every -free matrix differs from it in at least entries of some row.
Proof. Rows with share no column of , and is a final segment of . For the common columns in are those of , a final segment of , and the only later column of missing from is . Suppose a -free matrix changes at most entries per row with . The modified rows keep a common column in , to the left of all of , so every column of in is in . Hence the columns of in , at least of them, are in , which has at most : .
[computed] Exact values for : the minimum number of changes in the most modified row is 1, 2, 3, 4, and . Consequently (take , so that and ) a per-row bound of the form for staircase matrices with classes requires , and the per-row bound of order in Theorem 4 cannot be replaced by .
Proposition 8 (sliding windows). [proved] Let be even and . Rows are numbered . Part A has columns and row contains the consecutive columns . Part B, to the right of A, consists of the columns in this order, with , and row contains for . Then and are -free, for all pairs, and .
Proof. For the common columns in are the last columns of the window of (none if r_i\cap B$ is a final segment of ; a copy has its common column in and its other column among the at most one of when N$ be -free. If two rows of share a column in the zone of , every column of of the lower one is in the upper one. Call a row bad if changes at least of its entries in the zone of . Two good rows at distance at most keep a common column in . Fix a block of consecutive rows. If it contains consecutive bad rows, or more than bad rows, it carries at least changes. Otherwise consecutive good rows are at distance at most , the -parts of the good rows decrease from top to bottom in , and for an index whose first row lies in the block the column needs at least changes, where count the good rows before and from that row. Between the good rows of ranks and there are at least rows, hence at least indices , each with : at least changes. Each block thus carries at least changes and there are at least disjoint blocks.
So no bound ( the larger side) holds for two -free parts, even for intervals. When this family has , fewer than columns and , against an upper bound of order from Theorem 4.
Staircase matrices
For a staircase matrix with classes , row is described by its starts : it contains the columns of at or after .
Lemma 9 (threshold criterion). [proved] For a row and classes with , let be the last column of strictly between and if there is one, and otherwise; put when . The matrix is -free if and only if, for every row and every pair of classes , exceeds and for all rows $x<y.
Proof. A copy uses two columns of different classes, with common column in and other column , , . If and , then and form a copy. Conversely a copy gives , so , and , .
[computed] Compared with the direct test on 60 000 staircase matrices with 2 to 5 classes: no disagreement.
Theorem 10 (two classes). [proved] Let be a staircase matrix with two classes and for all pairs of rows, with . Then can be made -free by changing at most entries in each row.
Proof. An empty row forms no copy and is left unchanged. For a nonempty row let be its starts (with if meets only one class), , their classes, the set of columns of strictly between and , and . By Lemma 9 the matrix is -free iff for all .
Step 1 (each row separately). If , lower to the first column of after . Otherwise lower to the -th largest column of and let be the -th largest; if contains at most columns of , raise to the first column of after . Cost at most . Afterwards a row either has no column between its starts, or is heavy: it has filled its top gap columns, its level is , and contains more than columns of .
Fact 1. Let be heavy and an original row below whose start in is at most . The column and the filled columns belong to and not to the original row , and every common column of before is to their left; so there are at most such common columns. Hence starts after in and has at most columns of before .
Step 2 (top to bottom). Let be the largest among the final rows above , attained by a row , and . If both starts of after Step 1 are at most : if the original start of in class is at most , raise the start of in class to the first column of that class after ; otherwise raise the start in class to the first column of that class after . Fact 2. A row modified in Step 2 has one start at most and the other equal to the first column of its class after ; its gap columns are at most , so it does not raise the level. By induction the level is always attained by a heavy row not modified in Step 2, and Fact 1 applies to it and to original rows.
Cost of Step 2. Step 1 lowers a start by at most columns of its class. In the first case Fact 1 gives at most columns of class between the original start of and , so at most deletions. In the second case the start in class was above originally and was lowered by at most columns: at most deletions. In the final matrix every row has a start above the level of the rows above it.
[computed] On 201 318 two-class matrices the output is always -free and no row exceeds (maximum observed ). [open] The same statement for interleaved classes with a bound per row; by Proposition 7, .
Theorem 11 (pivot reduction). [proved] Let be an matrix with for all pairs of rows and let be an integer. There is a staircase matrix with classes such that and for all pairs of rows.
Proof. Process the rows from bottom to top, keeping a set of classified columns. For the row , let be the set of its ones in unclassified columns. If , becomes a pivot and a new class: every row above is replaced, on the columns of , by the nearest final segment of . Otherwise the ones of in are erased. When becomes a pivot, the entries of the columns of in the rows above are still those of ; since is identically 1 on , turning into a final segment of costs exactly the number of columns of to delete to make the pair -free on , at most . There are at most pivots, hence at most changes, and the erasures cost less than per row. A row below a pivot was processed before it, so its ones in the then unclassified columns were classified into another class or erased: it is zero on that class, and a column never classified is zero. For the distances, let ; delete the columns of a minimum set for the pair in and those where or was modified by a rounding: at most columns. On the remaining columns differs from only by erasures. An erasure in creates no copy of the pair. An erasure of the entry happens when is unclassified at the time of ; then the row , processed earlier, is zero at in . So every copy of the pair in on these columns is a copy in .
Corollary 12. [proved, conditional] Suppose there are constants and such that every staircase matrix with classes and for all pairs satisfies . Then every matrix with for all pairs of rows, , satisfies .
Proof. If the matrix is -free. Otherwise let and apply Theorem 11 with ; the matrix obtained has at most classes, cost at most and pair distances at most . The hypothesis adds .
By Theorem 4 the hypothesis of the corollary holds, with , when the classes are intervals of columns. [open] It is not known for interleaved classes. The step from the conclusion of the corollary to a polynomial removal lemma for is not treated in this note.
The row-block method does not transfer directly
Lupini [3] proved polynomial removal for the ordered identity. His short-span estimate keeps blocks of consecutive rows separated by zeroed rows, observes that a column pair is mixed in at most one block, and repairs a block of rows with mixed pairs at cost at most by rows that are lattice polynomials of the rows of the block, which preserves compatibility between blocks. Write if the row placed above the row forms no copy of .
Lemma 13. [proved] For fixed , is closed under coordinatewise minimum and maximum. For fixed , is closed under coordinatewise minimum and under passing to a smaller row, but not under maximum.
Proof. For fixed the condition is for all with . For fixed it is “ and are not both 1” for all with ; with the rows and qualify and their maximum does not.
Say that a column pair is mixed in a block if some row of the block has entries and another has there. [proved] If every copy of has row span at most and the retained blocks are separated by at least rows, a column pair is mixed in at most one block, since a row of a block and a row of a lower block form a copy of span larger than .
Proposition 14 (lock family). [proved] Let be even, , . Columns, from left to right: columns for each , columns for each , then , , . Block : rows , , above rows , . Below : for each , rows equal to , and for each , rows equal to . Then every copy of has both rows in ; has exactly mixed column pairs and the rows below have none; and .
Proof. Two rows not both in share either all the columns of the lower one or only , which is the last column of the lower one. In the mixed pairs are and . Let be -free; for let be the number of changes in and in its rows below, and likewise for . If loses , either one of its rows below is untouched, and then must lose its columns , or all of them changed: . Likewise if loses . If and both keep , each of the columns must be added to or removed from : . So for every pair one of the two is at least $(k + 1)/2; this holds for all or for all .
[computed] Exact distance for : , that is each time, against for the quantity . The family does not contradict a short-span estimate for (its distance is of the order of its side); it shows, as grows, that the cost of a block is not controlled by its mixed pairs alone; the lower bound comes from the compatibility of with the rows below it.
Matrices of row span one
The row span of a copy is, up to the factor , the height of a submatrix considered by Alon and Ben-Eliezer [1]; their question about copies of large height concerns a pattern over four symbols and is different from the statements below. For the identity, Lupini [3] shows that any removal exponent is at least 3; for the family of the next section gives .
Say that a matrix has row span at most if every copy of uses two rows at distance at most . Rows are written from top to bottom, is the set of columns of index larger than and its complement. We write when a row placed above a row forms no copy with it, that is, when is a final segment of .
Lemma 15 (counting). [proved] In a matrix of row span one, every pair of columns carries at most one copy; an matrix of row span one has at most copies. For row span at most , every pair of columns carries at most copies.
Proof. If rows and , , both carry a copy on columns , then is impossible (row would both contain and miss ), and gives a copy between rows and . For span : let be the first row with pattern on lying above a row with pattern , and the last row with pattern lying below a row with pattern ; every copy has its top row in and its bottom row in .
Corollary 16. [proved] If satisfies “ implies at least copies”, then every matrix of row span one satisfies . Conversely, a family of matrices of row span one with would rule out a polynomial removal lemma for .
Proposition 17 (a single copy at linear distance). [proved] Let . Take four blocks of columns, followed by three columns . Rows, from top to bottom: copies of ; ; ; then copies of each of , , , . This matrix, with rows and columns, contains exactly one copy of , and . Consequently any exponent in a polynomial removal lemma for satisfies .
Proof. Two rows with disjoint supports, or the upper one containing the lower one, or whose only common column is the last column of the lower row, form no copy; this covers all pairs except , whose only common column is and where has only above . Suppose at most entries are changed and the result is -free. In each of the five groups of equal rows one row is untouched, and in each block one column is untouched in all rows. Let be the modified rows. Since and an untouched row lies below, ; likewise , , . The pair has the common column and , hence . Then an untouched row above gives a copy on , a contradiction. Appending all-zero columns gives a square matrix of side with the same single copy and the same distance (a zero column belongs to no copy, and a submatrix of a -free matrix is -free). With one copy and , the inequality for all such forces . □
[computed] For blocks and repetitions of size : one copy, and exact distance . The proposition is consistent with a bound of the form , where is the least number of entries meeting all copies (here , and trivially).
Lemma 18 (splice). [proved] Let be sets of columns and a cut such that is empty or has its last element in . Put . If and , then .
Proof. If misses , then , and the elements of above its least element belong to , hence to . Otherwise let be the least element of . All of above lies in , in particular the last element of , which is in ; so all of above lies in , and . Thus all of above lies in . □
Theorem 19 (two safe moves, bottom-up). [proved] Let have row span one. Say that the state holds if every pair of rows with satisfies , and every adjacent pair with does too. In the state put , and consider:
(G1) for a row and a column , delete from every row of the vertical closure , the smallest set such that , , and imply ;
(G2) for a cut such that and is empty or has its last element in , replace by .
Both moves preserve . Hence, starting from and treating the adjacent pairs from bottom to top, applying moves (G1), (G2) to the pair until it forms no copy (which (G1) alone always achieves), one obtains a -free matrix; is at most the number of entries changed.
Proof. (G1) creates no copy in any matrix: a new copy on rows and columns would have its zero entry among the deleted ones, so and , with kept and , ; then and was deleted from . (G2) changes row only. For , both and are -related to by , every final segment is, and the set of rows with is closed under union and intersection (Lemma 13); so . For , and , and the hypothesis on gives . Lemma 18 applies. The pairs and are not part of . Once the pair forms no copy, holds. Finally, let be the least column of having a column of to its right; (G1) applied to and decreases the number of copies of the pair. □
[computed] Random moves on 222 026 matrices of row span one (sides 4 to 10; 584 501 moves (G1) and 97 260 moves (G2)): the state is never violated and the output is always -free. The file verif_portee1.py repeats this test and checks Lemmas 15 and 18 and Proposition 17.
[open] A bound for all matrices of row span one. By Corollary 16 it is necessary for a polynomial removal lemma for .
A span-one family at distance
Throughout this section a conflict is a pair of adjacent rows carrying a copy of . Fix integers and , and let range over .
Columns, from left to right: groups ( columns each); then groups ( columns each); then, for : the groups ( columns each, ), followed, for , by the block made of the single columns , a group of columns, and the single columns . Let be the set of all columns to the right of , and the set of all columns to the right of .
Rows, from top to bottom. For : for , first rows , then for the two rows
once this is done for all (the rows attached to a pair form the bouquet ; bouquets are ordered lexicographically), for each , rows . At the bottom: for each , rows , then for each , rows . Call this matrix ; it has rows and columns.
Proposition 20. [proved] In every pair of rows is -free except the adjacent pairs , each of which carries exactly one copy, namely on columns . Hence has row span one and exactly copies of .
Proof. By Lemma 1, a row above a row forms a -free pair if and only if is a final segment of . If with a final segment of the column set and to the left of , then is a final segment of , so the pair is -free as soon as , or contains every element of to the right of . The rows , , have this form with , and with .
(A) in bouquet , in a later bouquet . The head of meets no such . The head of meets only if , , and then ; it meets only in , when , , , and the elements of to the right of lie in . The head of meets only in , when , , and the elements of to the right of lie in ; it meets in two cases: if , , then ; if , , the least common element lies in and all elements of to its right for , , , belong to .
(B) Same bouquet. , ; for , and the three other intersections equal : all final segments. Finally and the only element of to the right of is : exactly one copy.
(C) in bouquet , , . If , . If , is , enlarged to if and by if .
(D) , below. For in a bouquet with , the head meets only in , and the elements of to its right lie in . Moreover for and for . (E) . For in a bouquet or , is itself (if ) or of the form . (F) . is itself, or , or empty. Rows of type and are pairwise disjoint or equal.
Lemma 21 (rectangles). [proved] Let be rectangles in a grid, and let be the number of with . Then
Proof. Choose successively consisting of cells, no two in a common row or column, disjoint from the earlier . This is possible: the cells already chosen inside come from at most rectangles, each contributing a matching; in the complete bipartite graph with matchings removed, every vertex of the smaller side keeps at least neighbours; so any vertices of the smaller side satisfy Hall’s condition and can be matched.
Theorem 22. [proved] Every -free matrix differs from in at least entries.
Proof. Let be -free and the set of entries where . For each conflict , with rows , and columns , one of the four entries of the copy has changed; fix one. This gives a type, and with it a class of conflicts, a group of blocking rows, a target column , a row , a group of link columns and, for each earlier conflict of the class, a bonus entry:
| type | changed entry | class | blocking rows | bonus entry for | ||
| A | varies | |||||
| K | varies | |||||
| R | varies | |||||
| V | varies |
Let be the set of blocking rows of with , , the set of with , , and , a rectangle of the block (blocking rows) .
(i) . For , , if then rows and columns carry a copy in : for type A, for K, for R, for V. (In the blocking rows and the row contain , which lies to the left of ; the blocking rows contain for types A, K, R and do not contain it for type V.)
(ii) Bonus. Let precede in the same class and type, with . Then the bonus entry of for lies in . For types A, K, R there is , so ; the column is to the left of and ; if then is a copy. For type V there is , so and ; if then is a copy.
(iii) Distinct entries. Assign to : the changed entry of its copy; the entries , ; the entries , ; and its bonus entries lying in . No entry is assigned to two conflicts: entries in a row or are assigned to the conflict of that row only, except the bonus entries of type V, which lie in the column of the conflict receiving them and outside the columns used by the conflict of their row; entries in blocking rows lie in the column or of the conflict receiving them. The blocks are pairwise disjoint and disjoint from all these entries.
(iv) Count. Fix a type and a class and list its conflicts of that type in order. By (ii), receives at least bonus entries, being the number of earlier rectangles meeting . By (i) and Lemma 21, the block contains at least entries of . The number of entries of counted is thus at least
Summing over types and classes gives .
Proposition 23. [proved] For all and , replacing every row by yields a -free matrix; hence the distance of to -freeness is at most . With Theorem 22: for this distance equals ; in particular , a square matrix of side with copies of on disjoint pairs of adjacent rows, is at distance exactly .
Proof. with , and we use the principle and the cases of the proof of Proposition 20. Pairs without a row of type are unchanged. In the same bouquet, is a final segment of , , and for the intersections of with and equal . If lies in an earlier bouquet and , then and the head of meets as in case (A). If and lies in a later bouquet , then meets and as in case (A), and in addition meets () in ; this is then the least common element, and the elements of to its right lie in . For or nothing changes, since belongs to none of these rows outside . For , is if , empty if , and , together with when , if . Finally for . The cost is per conflict.
Corollary 24. [proved] For matrices of row span one, the distance to -freeness is not bounded by , where is the sum over adjacent pairs of rows of the distance of the pair: for , . With copies at distance , any removal exponent for is at least .
[computed] Exact distances obtained with a constraint solver (optimality proved) agree with the formula for ; for the two bounds differ and the solver gives for . The ancillary script verif_cube.py (plain Python) rebuilds for six sizes up to side 882 and checks Proposition 20, the entries used in the proof of Theorem 22, and the repair of Proposition 23. 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 are confined to one row and the classes of type 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 -free, of cost (number of conflicts). [open] Whether holds for span-one matrices with conflicts carrying one copy each; the family above gives .
Open questions
[open] Does 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 [4, 6, 5] for larger patterns and the positive result [3] for the identity, and nothing on .
[open] Extend Theorem 4 to two interleaved -free parts, or to interleaved staircase classes with a bound polynomial in .
[open] Extend Theorem 10 to three classes.
[open] Prove for matrices of row span one.
[open] Close the gap between the orders and for two -free intervals with .
Ancillary files. Three plain Python scripts, with fixed parameters and no external module: verif_corner_note.py (Lemmas 3 and 8, Theorems 4 and 10, and the families of Propositions 7, 8 and 14, on random and small instances), verif_portee1.py (the section on row span one) and verif_cube.py (the family ). The first two print their messages in French. They test the statements on finitely many instances and are not part of the proofs.
Acknowledgement. This note was prepared with the assistance of Claude (Anthropic).
References
References
- [1]N. Alon, O. Ben-Eliezer, Efficient removal lemmas for matrices, Order 37 (2020), 83–101; arXiv:1609.04235.
- [2]L. Gishboliner, A. Shapira, Polynomial property testing, arXiv:2508.16878.arxiv.org/abs/2508.16878
- [3]M. Lupini, Polynomial removal for the ordered two-by-two identity matrix, preprint, Zenodo 23618367, 2 November 2026.DOI
- [4]OpenAI, Polynomial removal fails for ordered binary matrices, preprint, 25 September 2026.DOI
- [5]R. Shea, a 3×3 obstruction to polynomial removal for ordered binary matrices, public repository shea256/ordered-binary-matrix-removal, October 2026.
- [6]Z. Wang, A four-by-four obstruction to polynomial removal for ordered binary matrices, arXiv:2610.15370.arxiv.org/abs/2610.15370