betaFeedback

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 MM, D(M)D(M) is the minimum number of entry changes (in either direction) producing a PP-free matrix.

Lemma 1. [proved] A matrix is PP-free if and only if, for all rows x<yx < y, the set x∩yx \cap y is a final segment of yy (every column of yy to the right of a common column is common). Equivalently: for every column cc, the rows containing cc, read from top to bottom and restricted to the columns to the right of cc, are decreasing for inclusion.

Proof. A copy is a pair of rows x<yx < y containing cc together with a column d>cd > c in yy and not in xx.

□\Box

Definition 2. For rows x<yx < y, d(x,y)d(x,y) is the minimum number of columns whose deletion makes the pair PP-free.

Lemma 3 (cut formula). [proved] For rows x<yx<y with a common columns,

d(x,y)=min⁡Π(#{common columns≤Π}+#{columns of y not in x, to the right of Π})d(x,y)=\min_{\Pi}\left(\#\{\text{common columns}\leq\Pi\}+\#\{\text{columns of }y\text{ not in }x,\text{ to the right of }\Pi\}\right)

the minimum being over cut positions Π\Pi. Moreover the set of common columns differs from the set of the last aa ones of yy in at most 2d(x,y)2d(x,y) columns.

Proof. The copies of the pair are the edges of the bipartite graph joining a common column cc to a column d>cd>c of y∖xy\setminus x; d(x,y)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∖xy\setminus x right of Π\Pi. For an optimal cut, let ee and hh be the two numbers. To the right of Π\Pi, yy has a−ea-e common columns and hh others. If h≤eh\leq e, the last aa ones of yy are these a−e+ha-e+h columns and e−he-h more, and the symmetric difference has at most 2e2e elements. If h>eh>e, the last aa ones of yy all lie to the right of Π\Pi and the difference has at most 2h2h elements.

[computed] Both assertions were checked on 300 000300\,000 random pairs of rows.

Gluing consecutive intervals

Theorem 4 (gluing mm intervals). [proved] Let MM have nn rows and WW columns, the columns being partitioned into mm consecutive intervals I1,…,ImI_1,\ldots,I_m such that each restriction M∣IjM|_{I_j} is PP-free. Suppose d(x,y)≤Kd(x,y)\leq K for all pairs of rows, with K≥1K\geq1, and put s=⌈2KW⌉s=\lceil2\sqrt{KW}\rceil. Then MM can be made PP-free by deleting fewer than 3ms3ms ones in each row. In particular

D(M)<3mns≤6mnKW+3mn.D(M)<3mns\leq6mn\sqrt{KW}+3mn.

Proof. If K>WK>W then s>2Ws>2W and deleting all ones costs at most W<sW<s per row; so assume K≤WK\leq W. For a finite set EE of columns let tr⁡(E)\operatorname{tr}(E) be EE without its ss largest elements. Say that rows x<yx<y are linked through IiI_i if tr⁡(x∩Ii)∩tr⁡(y∩Ii)≠∅\operatorname{tr}(x\cap I_i)\cap\operatorname{tr}(y\cap I_i)\ne\varnothing. Since M∣IiM|_{I_i} is PP-free, the common columns in IiI_i form a final segment of y∩Iiy\cap I_i; a common column that is not among the last ss of y∩Iiy\cap I_i therefore forces more than ss common columns in IiI_i. Let Anc⁡<j(y)\operatorname{Anc}_{<j}(y) be the set of rows reached from yy by going up through links of indices <j<j, step by step. Define

Qy(j)=(y∩Ij)∩⋂z∈Anc⁡<j(y)(z∩Ij),Ny∩Ij=tr⁡(Qy(j)).Q_y^{(j)}=(y\cap I_j)\cap\bigcap_{z\in\operatorname{Anc}_{<j}(y)}(z\cap I_j),\qquad N_y\cap I_j=\operatorname{tr}(Q_y^{(j)}).

NN is PP-free. Inside IjI_j: for zz above yy, (y∩Ij)∖z(y\cap I_j)\setminus z is an initial segment of y∩Ijy\cap I_j, so Qy(j)Q_y^{(j)} is y∩Ijy\cap I_j minus an initial segment. Removing initial segments keeps PP-freeness: if d<d′d<d' are kept in yy and dd is kept in xx, then d′∈xd'\in x (final segment) and d′d' is to the right of dd, hence kept in xx. Removing the last ss ones of every row also keeps PP-freeness: if c<dc<d with cc common, dd kept in yy and removed from xx, then yy has at least ss ones after dd, all in xx, so dd is not among the last ss ones of xx. Across intervals: if x<yx<y share a column of IiI_i in NN, they are linked through IiI_i, because tr⁡(Q)⊆tr⁡(E)\operatorname{tr}(Q)\subseteq\operatorname{tr}(E) whenever Q⊆EQ\subseteq E. For j>ij>i this gives Anc⁡<j(y)⊇{x}∪Anc⁡<j(x)\operatorname{Anc}_{<j}(y)\supseteq\{x\}\cup\operatorname{Anc}_{<j}(x), hence Qy(j)⊆Qx(j)Q_y^{(j)}\subseteq Q_x^{(j)} and tr⁡(Qy(j))⊆tr⁡(Qx(j))\operatorname{tr}(Q_y^{(j)})\subseteq\operatorname{tr}(Q_x^{(j)}) (an element with ss successors in Qy(j)Q_y^{(j)} has ss successors in Qx(j)Q_x^{(j)}). So no copy has its common column in IiI_i and its other column in IjI_j.

Cost in IjI_j. At most ss for tr⁡\operatorname{tr}, plus max⁡z∣(y∩Ij)∖z∣\max_z |(y\cap I_j)\setminus z| over z∈Anc⁡<j(y)z\in\operatorname{Anc}_{<j}(y) (the sets are nested initial segments). Let a<j(x,y)a_{<j}(x,y) be the number of common columns to the left of IjI_j and pj(x,y)p_j(x,y) the number of columns of y∩Ijy\cap I_j not in xx. Every column left of IjI_j precedes every column of IjI_j, so min⁡(a<j,pj)≤d≤K\min(a_{<j},p_j)\leq d\leq K. Fix a path of links y=z0>z1>⋯>zH=zy=z_0>z_1>\cdots>z_H=z. Extract u0=z0u_0=z_0 and, while ui=ztu_i=z_t with t<Ht<H, let ui+1=zt′u_{i+1}=z_{t'} where t′>tt'>t is the largest index with a<j(zt′,zt)>Ka_{<j}(z_{t'},z_t)>K; it exists since a<j(zt+1,zt)>s≥Ka_{<j}(z_{t+1},z_t)>s\geq K. We reach uh=zu_h=z, and each hop has pj≤Kp_j\leq K, so ∣(y∩Ij)∖z∣≤hK|(y\cap I_j)\setminus z|\leq hK.

For 0≤i≤h−20\leq i\leq h-2 let SiS_i be the set of the last s+1s+1 ones of ui+1u_{i+1} in the interval of its next link on the path. If i′≥i+2i'\geq i+2 then ui′+1u_{i'+1} is higher on the path than ui+2u_{i+2}, so a<j(ui′+1,ui+1)≤Ka_{<j}(u_{i'+1},u_{i+1})\leq K by the

choice of ui+2u_{i+2}, and ∣Si∩Si′∣≤K|S_i \cap S_{i'}| \le K. Put q=⌊s/K⌋q=\lfloor s/K\rfloor; since W≥KW \ge K we have s≥2Ks \ge2K and q≥s/(2K)q \ge s/(2K). If ⌊h/2⌋≥q\lfloor h/2\rfloor\ge q, the sets S0,S2,…,S2q−2S_0,S_2,\ldots,S_{2q-2} have a union of size at least

∑t=0q−1(s+1−tK)>qs−Kq22≥qs2≥s24K≥W,\sum_{t=0}^{q-1}(s+1-tK) > qs-\frac{Kq^2}{2} \ge\frac{qs}{2} \ge\frac{s^2}{4K} \ge W,

which is impossible. Hence h≤2q−1h \le2q-1 and hK<2shK < 2s. Altogether fewer than ms+2(m−1)s<3msms+2(m-1)s < 3ms deletions per row.

[computed] The construction was programmed. On 741 891 random matrices with 2 to 5 PP-free intervals the output is always PP-free; the parameter ss being drawn at random, in the 17 492 cases with s≥2Ks \ge2K and s2≥4KWs^2 \ge4KW the cost bounds hold.

Remark 5. The counting step uses neither PP-freeness nor the shape of the rows. [proved] In any matrix with WW columns, if z0>⋯>zHz_0>\cdots>z_H are rows such that consecutive ones share more than ss columns, with s≥2Ks \ge2K and s2≥4KWs^2 \ge4KW, one can go from z0z_0 to zHz_H in fewer than 2s/K2s/K hops along the sequence, each hop joining two rows that share more than KK 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 nn rows and WW columns, the classes form RR maximal runs of consecutive columns and d≤Kd \le K for all pairs of rows, with K≥1K \ge1, then D<3Rn⌈2KW⌉D < 3Rn\lceil2\sqrt{KW}\rceil.

Two families limiting the gluing bounds

Proposition 7 (chain family). [proved] Let n0≥2n_0 \ge2, h≥1h \ge1. Columns, from left to right: blocks Qn0,…,Q1,Q0Q_{n_0},\ldots,Q_1,Q_0 of hh columns each (part A), then columns en0,…,e2e_{n_0},\ldots,e_2 (part B). The rows are r1,…,rn0r_1,\ldots,r_{n_0} from top to bottom, and rir_i consists of QiQ_i, Qi−1Q_{i-1} and the columns eje_j with j≤ij \le i. Then M∣AM|_A and M∣BM|_B are PP-free, the matrix is a staircase matrix with n0+2n_0+2 classes, d≤1d \le1 for all pairs, and every PP-free matrix differs from it in at least min⁡(h/2,(n0−1)/2)\min(h/2,(n_0-1)/2) entries of some row.

Proof. Rows ri,rjr_i,r_j with j≥i+2j \ge i+2 share no column of AA, and ri∩Br_i \cap B is a final segment of rj∩Br_j \cap B. For j=i+1j=i+1 the common columns in AA are those of QiQ_i, a final segment of ri+1∩Ar_{i+1}\cap A, and the only later column of ri+1r_{i+1} missing from rir_i is ei+1e_{i+1}. Suppose a PP-free matrix changes at most tt entries per row with 2t<h2t<h. The modified rows ri′,ri+1′r'_i,r'_{i+1} keep a common column in QiQ_i, to the left of all of BB, so every column of BB in ri+1′r'_{i+1} is in ri′r'_i. Hence the columns of BB in rn0′r'_{n_0}, at least n0−1−tn_0-1-t of them, are in r1′r'_1, which has at most tt: t≥(n0−1)/2t \ge(n_0-1)/2.

[computed] Exact values for (n0,h)=(3,2),(5,4),(7,6),(9,8)(n_0,h)=(3,2),(5,4),(7,6),(9,8): the minimum number of changes in the most modified row is 1, 2, 3, 4, and D=2,6,12,18D=2,6,12,18. Consequently (take h≥n0−1h \ge n_0-1, so that K=1K=1 and m=n0+2m=n_0+2) a per-row bound of the form g(m)Kg(m)K for staircase matrices with mm classes requires g(m)≥(m−3)/2g(m)\ge(m-3)/2, and the per-row bound of order KW\sqrt{KW} in Theorem 4 cannot be replaced by CKCK.

Proposition 8 (sliding windows). [proved] Let L≥16L \ge16 be even and n≥5L3/2n \ge5L^{3/2}. Rows are numbered 0,…,n−10,\ldots,n-1. Part A has n−1+Ln-1+L columns and row ii contains the LL consecutive columns n−1−i,…,n−1−i+L−1n-1-i,\ldots,n-1-i+L-1. Part B, to the right of A, consists of the columns e1,…,en−1e_1,\ldots,e_{n-1} in this order, with T=⌊(n−1)/(L−1)⌋T=\lfloor(n-1)/(L-1)\rfloor, and row ii contains ete_t for t≤⌊i/(L−1)⌋t \le\lfloor i/(L-1)\rfloor. Then M∣AM|_A and M∣BM|_B are PP-free, d≤1d \le1 for all pairs, and D≥nL/80D \ge n\sqrt{L}/80.

Proof. For i<ji<j the common columns in AA are the last L−(j−i)L-(j-i) columns of the window of jj (none if j−i≥L)andj-i\ge L) andr_i\cap B$ is a final segment of rj∩Br_j\cap B; a copy has its common column in AA and its other column among the at most one ete_t of rj∖rir_j\setminus r_i when j−i≤L−1.Letj-i\le L-1. LetN$ be PP-free. If two rows of NN share a column in the zone of AA, every column of BB of the lower one is in the upper one. Call a row bad if NN changes at least L/4L/4 of its entries in the zone of AA. Two good rows at distance at most L/2L/2 keep a common column in AA. Fix a block of S=4⌈L3/2⌉S = 4\lceil L^{3/2}\rceil consecutive rows. If it contains L/2L/2 consecutive bad rows, or more than S/2S/2 bad rows, it carries at least L2/8L^2/8 changes. Otherwise consecutive good rows are at distance at most L/2L/2, the BB-parts of the r≥S/2≥2L3/2r \ge S/2 \ge2L^{3/2} good rows decrease from top to bottom in NN, and for an index tt whose first row t(L−1)t(L-1) lies in the block the column ete_t needs at least min⁡(ut,vt)\min(u_t,v_t) changes, where ut,vtu_t,v_t count the good rows before and from that row. Between the good rows of ranks ⌈r/4⌉\lceil r/4\rceil and ⌊3r/4⌋\lfloor3r/4\rfloor there are at least r/2−2r/2-2 rows, hence at least r/2−2L−1−1≥r4L\frac{r/2-2}{L-1}-1 \ge\frac{r}{4L} indices tt, each with min⁡(ut,vt)≥r/4\min(u_t,v_t) \ge r/4: at least r2/(16L)≥L2/4r^2/(16L) \ge L^2/4 changes. Each block thus carries at least L2/8L^2/8 changes and there are at least n/(2S)≥n/(10L3/2)n/(2S) \ge n/(10L^{3/2}) disjoint blocks. □\square

So no bound D≤CKND \le CKN (NN the larger side) holds for two PP-free parts, even for intervals. When n=5L3/2n = 5L^{3/2} this family has d≤1d \le1, fewer than 3n3n columns and D≥n4/3/137D \ge n^{4/3}/137, against an upper bound of order n3/2n^{3/2} from Theorem 4.

Staircase matrices

For a staircase matrix with classes S1,…,SmS_1,\ldots,S_m, row xx is described by its starts xj∈Sj∪{∞}x_j \in S_j \cup\{\infty\}: it contains the columns of SjS_j at or after xjx_j.

Lemma 9 (threshold criterion). [proved] For a row xx and classes i≠ji \ne j with xi<xjx_i < x_j, let Δxij\Delta_x^{ij} be the last column of SjS_j strictly between xix_i and xjx_j if there is one, and −∞-\infty otherwise; put Δxij=−∞\Delta_x^{ij} = -\infty when xi≥xjx_i \ge x_j. The matrix is PP-free if and only if, for every row yy and every pair of classes {i,j}\{i,j\}, max⁡(yi,yj)\max(y_i,y_j) exceeds Δxij\Delta_x^{ij} and Δxji\Delta_x^{ji} for all rows $x<y.

Proof. A copy uses two columns of different classes, with common column c≥max⁡(xi,yi)c \ge\max(x_i,y_i) in SiS_i and other column d∈Sjd \in S_j, yj≤d<xjy_j \le d < x_j, c<dc < d. If xi<xjx_i < x_j and max⁡(yi,yj)≤Δxij\max(y_i,y_j) \le\Delta_x^{ij}, then c=max⁡(xi,yi)c = \max(x_i,y_i) and d=Δxijd = \Delta_x^{ij} form a copy. Conversely a copy gives xi≤c<d<xjx_i \le c < d < x_j, so d≤Δxijd \le\Delta_x^{ij}, and yi≤c<dy_i \le c < d, yj≤dy_j \le d. □\square

[computed] Compared with the direct test on 60 000 staircase matrices with 2 to 5 classes: no disagreement.

Theorem 10 (two classes). [proved] Let MM be a staircase matrix with two classes and d≤Kd \le K for all pairs of rows, with K≥1K \ge1. Then MM can be made PP-free by changing at most 4K4K entries in each row.

Proof. An empty row forms no copy and is left unchanged. For a nonempty row xx let ex<λxe_x < \lambda_x be its starts (with λx=∞\lambda_x = \infty if xx meets only one class), ExE_x, LxL_x their classes, GxG_x the set of columns of LxL_x strictly between exe_x and λx\lambda_x, and Δx=max⁡Gx\Delta_x = \max G_x. By Lemma 9 the matrix is PP-free iff λy>max⁡x<yΔx\lambda_y > \max_{x<y}\Delta_x for all yy.

Step 1 (each row separately). If ∣Gx∣≤K|G_x| \le K, lower λx\lambda_x to the first column of LxL_x after exe_x. Otherwise lower λx\lambda_x to the KK-th largest column of GxG_x and let θx\theta_x be the (K+1)(K+1)-th largest; if [ex,θx)[e_x,\theta_x) contains at most KK columns of ExE_x, raise exe_x to the first column of ExE_x after θx\theta_x. Cost at most 2K2K. Afterwards a row either has no column between its starts, or is heavy: it has filled its KK top gap columns, its level is θx\theta_x, and [ex,θx)[e_x,\theta_x) contains more than KK columns of ExE_x.

Fact 1. Let xx be heavy and yy an original row below xx whose start in LxL_x is at most θx\theta_x. The column θx\theta_x and the KK filled columns belong to yy and not to the original row xx, and every common column of ExE_x before θx\theta_x is to their left; so there are at most KK such common columns. Hence yy starts after exe_x in ExE_x and has at most KK columns of ExE_x before θx\theta_x.

Step 2 (top to bottom). Let Θ\Theta be the largest Δ\Delta among the final rows above yy, attained by a row xx, and (i,j)=(Ex,Lx)(i,j)=(E_x,L_x). If both starts of yy after Step 1 are at most Θ\Theta: if the original start of yy in class jj is at most Θ\Theta, raise the start of yy in class ii to the first column of that class after Θ\Theta; otherwise raise the start in class jj to the first column of that class after Θ\Theta. Fact 2. A row modified in Step 2 has one start at most Θ\Theta and the other equal to the first column of its class after Θ\Theta; its gap columns are at most Θ\Theta, 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 KK columns of its class. In the first case Fact 1 gives at most KK columns of class ii between the original start of yy and Θ\Theta, so at most 2K2K deletions. In the second case the start in class jj was above Θ\Theta originally and was lowered by at most KK columns: at most KK 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 PP-free and no row exceeds 4K4K (maximum observed 2K2K). [open] The same statement for m≥3m \ge3 interleaved classes with a bound g(m)Kg(m)K per row; by Proposition 7, g(m)≥(m−3)/2g(m) \ge(m-3)/2.

Theorem 11 (pivot reduction). [proved] Let MM be an n×nn \times n matrix with d(x,y)≤kd(x,y) \le k for all pairs of rows and let s≥1s \ge1 be an integer. There is a staircase matrix NN with m≤n/sm \le n/s classes such that ∣M△N∣≤n2k/s+ns|M \mathbin{\triangle} N| \le n^2 k/s + ns and dN(x,y)≤(2m+1)kd_N(x,y) \le(2m+1)k for all pairs of rows.

Proof. Process the rows from bottom to top, keeping a set of classified columns. For the row ww, let SS be the set of its ones in unclassified columns. If ∣S∣≥s|S| \ge s, ww becomes a pivot and SS a new class: every row xx above ww is replaced, on the columns of SS, by the nearest final segment of SS. Otherwise the ones of ww in SS are erased. When ww becomes a pivot, the entries of the columns of SS in the rows above ww are still those of MM; since ww is identically 1 on SS, turning xx into a final segment of SS costs exactly the number of columns of SS to delete to make the pair (x,w)(x,w) PP-free on SS, at most kk. There are at most n/sn/s pivots, hence at most n2k/sn^2k/s changes, and the erasures cost less than ss 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 x<yx<y; delete the columns of a minimum set for the pair in MM and those where xx or yy was modified by a rounding: at most k+2mkk+2mk columns. On the remaining columns NN differs from MM only by erasures. An erasure in yy creates no copy of the pair. An erasure of the entry (x,c)(x,c) happens when cc is unclassified at the time of xx; then the row yy, processed earlier, is zero at cc in NN. So every copy of the pair in NN on these columns is a copy in MM.

Corollary 12. [proved, conditional] Suppose there are constants C>0C>0 and a≥0a \ge0 such that every n×nn \times n staircase matrix with mm classes and d≤Kd \le K for all pairs satisfies D≤Cman3/2KD \le C m^a n^{3/2}\sqrt{K}. Then every n×nn \times n matrix with d≤κnd \le\kappa n for all pairs of rows, 0<κ≤10<\kappa\le1, satisfies D≤C′κ1/(2a+3)n2D \le C'\kappa^{1/(2a+3)}n^2.

Proof. If κn<1\kappa n<1 the matrix is PP-free. Otherwise let m=⌈κ−1/(2a+3)⌉≤nm=\lceil\kappa^{-1/(2a+3)}\rceil\le n and apply Theorem 11 with s=⌈n/m⌉s=\lceil n/m\rceil; the matrix obtained has at most mm classes, cost at most κn2+2n2/m\kappa n^2+2n^2/m and pair distances at most (2m+1)κn(2m+1)\kappa n. The hypothesis adds Cman3/2(2m+1)κn≤2Cma+1/2κ n2C m^a n^{3/2}\sqrt{(2m+1)\kappa n}\le2C m^{a+1/2}\sqrt{\kappa}\,n^2.

By Theorem 4 the hypothesis of the corollary holds, with a=1a=1, 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 PP is not treated in this note.

The row-block method does not transfer directly

Lupini [3] proved polynomial removal for the ordered 2×22 \times2 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 mm rows with QQ mixed pairs at cost at most 2m2Q2m\sqrt{2Q} by rows that are lattice polynomials of the rows of the block, which preserves compatibility between blocks. Write x R yx\,R\,y if the row xx placed above the row yy forms no copy of PP.

Lemma 13. [proved] For fixed yy, {x:xRy}\{x : x R y\} is closed under coordinatewise minimum and maximum. For fixed xx, {y:xRy}\{y : x R y\} is closed under coordinatewise minimum and under passing to a smaller row, but not under maximum.

Proof. For fixed yy the condition is xc≤xdx_c \le x_d for all c<dc < d with yc=yd=1y_c = y_d = 1. For fixed xx it is “ycy_c and ydy_d are not both 1” for all c<dc < d with (xc,xd)=(1,0)(x_c, x_d) = (1, 0); with x=(1,0)x = (1, 0) the rows (1,0)(1, 0) and (0,1)(0, 1) qualify and their maximum does not.

Say that a column pair c<dc < d is mixed in a block if some row of the block has entries (1,0)(1, 0) and another has (1,1)(1, 1) there. [proved] If every copy of PP has row span at most hh and the retained blocks are separated by at least hh rows, a column pair is mixed in at most one block, since a row (1,0)(1, 0) of a block and a row (1,1)(1, 1) of a lower block form a copy of span larger than hh.

Proposition 14 (lock family). [proved] Let mm be even, k≥1k \ge1, r≥kr \ge k. Columns, from left to right: kk columns bi1,…,bikb_i^1,\ldots,b_i^k for each i≤m/2i \le m/2, kk columns aj1,…,ajka_j^1,\ldots,a_j^k for each j≤m/2j \le m/2, then cc, dd, e1,…,eke_1,\ldots,e_k. Block BB: rows xi={bi1,…,bik,c}x_i = \{b_i^1,\ldots,b_i^k,c\}, i≤m/2i \le m/2, above rows yj={aj1,…,ajk,c,d,e1,…,ek}y_j = \{a_j^1,\ldots,a_j^k,c,d,e_1,\ldots,e_k\}, j≤m/2j \le m/2. Below BB: for each ii, rr rows equal to {bi1,…,bik,c}\{b_i^1,\ldots,b_i^k,c\}, and for each jj, rr rows equal to {aj1,…,ajk,c}\{a_j^1,\ldots,a_j^k,c\}. Then every copy of PP has both rows in BB; BB has exactly k+1k + 1 mixed column pairs and the rows below BB have none; and D≥m(k+1)/4D \ge m(k + 1)/4.

Proof. Two rows not both in BB share either all the columns of the lower one or only cc, which is the last column of the lower one. In BB the mixed pairs are (c,d)(c,d) and (c,et)(c,e_t). Let NN be PP-free; for i≤m/2i \le m/2 let γ(i)\gamma(i) be the number of changes in xix_i and in its rr rows below, and γ′(j)\gamma'(j) likewise for yjy_j. If xix_i loses cc, either one of its rr rows below is untouched, and then xix_i must lose its kk columns bb, or all of them changed: γ(i)≥k+1\gamma(i) \ge k + 1. Likewise if yjy_j loses cc. If xix_i and yjy_j both keep cc, each of the k+1k + 1 columns d,e1,…,ekd,e_1,\ldots,e_k must be added to xix_i or removed from yjy_j: γ(i)+γ′(j)≥k+1\gamma(i) + \gamma'(j) \ge k + 1. So for every pair (i,j)(i,j) one of the two is at least $(k + 1)/2; this holds for all ii or for all jj.

[computed] Exact distance for (m,k,r)=(4,2,2),(4,3,3),(6,3,3),(6,4,4),(4,6,6)(m,k,r) = (4,2,2), (4,3,3), (6,3,3), (6,4,4), (4,6,6): 6,8,12,15,146, 8, 12, 15, 14, that is m(k+1)/2m(k + 1)/2 each time, against mk+1m\sqrt{k + 1} for the quantity mQm\sqrt{Q}. The family does not contradict a short-span estimate for PP (its distance is of the order of its side); it shows, as kk grows, that the cost of a block is not controlled by its mixed pairs alone; the lower bound comes from the compatibility of BB with the rows below it.

Matrices of row span one

The row span of a copy is, up to the factor nn, the height of a 2×22 \times2 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 2×22 \times2 identity, Lupini [3] shows that any removal exponent is at least 3; for PP the family of the next section gives 9/29/2.

Say that a matrix has row span at most hh if every copy of PP uses two rows at distance at most hh. Rows are written x1,…,xnx_1,\ldots,x_n from top to bottom, FΠF_\Pi is the set of columns of index larger than Π\Pi and Π\Pi its complement. We write xRyx R y when a row xx placed above a row yy forms no copy with it, that is, when x∩yx \cap y is a final segment of yy.

Lemma 15 (counting). [proved] In a matrix of row span one, every pair of columns carries at most one copy; an n×nn \times n matrix of row span one has at most (n2)\binom{n}{2} copies. For row span at most hh, every pair of columns carries at most h2h^2 copies.

Proof. If rows (i,i+1)(i,i+1) and (j,j+1)(j,j+1), j>ij > i, both carry a copy on columns c<dc < d, then j=i+1j = i + 1 is impossible (row i+1i+1 would both contain and miss dd), and j≥i+2j \ge i + 2 gives a copy between rows ii and j+1j + 1. For span hh: let i0i_0 be the first row with pattern (1,0)(1,0) on (c,d)(c,d) lying above a row with pattern (1,1)(1,1), and j1j_1 the last row with pattern (1,1)(1,1) lying below a row with pattern (1,0)(1,0); every copy has its top row in [j1−h,j1)[j_1-h,j_1) and its bottom row in (i0,i0+h](i_0,i_0+h].

Corollary 16. [proved] If PP satisfies “D≥εn2D \ge\varepsilon n^2 implies at least cεCn4c\varepsilon^C n^4 copies”, then every n×nn \times n matrix of row span one satisfies D≤C′n2−2/CD \le C'n^{2-2/C}. Conversely, a family of matrices of row span one with D≥n2−o(1)D \ge n^{2-o(1)} would rule out a polynomial removal lemma for PP.

Proposition 17 (a single copy at linear distance). [proved] Let m≥0m \ge0. Take four blocks b,b′′,a,a′′b,b'',a,a'' of m+1m+1 columns, followed by three columns c<t<dc<t<d. Rows, from top to bottom: m+1m+1 copies of {t}\{t\}; x=b∪b′′∪{c,t}x=b\cup b''\cup\{c,t\}; y=a∪a′′∪{c,d}y=a\cup a''\cup\{c,d\}; then m+1m+1 copies of each of b∪{c}b\cup\{c\}, b′′∪{t}b''\cup\{t\}, a∪{c}a\cup\{c\}, a′′∪{d}a''\cup\{d\}. This matrix, with 5m+75m+7 rows and 4m+74m+7 columns, contains exactly one copy of PP, and D≥m+1D \ge m+1. Consequently any exponent CC in a polynomial removal lemma for PP satisfies C≥4C \ge4.

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 (x,y)(x,y), whose only common column is cc and where yy has only dd above cc. Suppose at most mm entries are changed and the result is PP-free. In each of the five groups of m+1m+1 equal rows one row is untouched, and in each block one column β,β′′,α,α′′\beta,\beta'',\alpha,\alpha'' is untouched in all rows. Let x′,y′x',y' be the modified rows. Since β∈x′\beta\in x' and an untouched row b∪{c}b\cup\{c\} lies below, c∈x′c \in x'; likewise t∈x′t \in x', c∈y′c \in y', d∈y′d \in y'. The pair (x′,y′)(x',y') has the common column cc and d∈y′d \in y', hence d∈x′d \in x'. Then an untouched row {t}\{t\} above x′x' gives a copy on (t,d)(t,d), a contradiction. Appending mm all-zero columns gives a square matrix of side n=5m+7n=5m+7 with the same single copy and the same distance (a zero column belongs to no copy, and a submatrix of a PP-free matrix is PP-free). With one copy and ε≥1/(7n)\varepsilon\ge1/(7n), the inequality 1≥cεCn41 \ge c\varepsilon^C n^4 for all such nn forces C≥4C \ge4. □

[computed] For blocks and repetitions of size 1,…,51,\ldots,5: one copy, and exact distance 2,…,62,\ldots,6. The proposition is consistent with a bound of the form D≤CnτD \le Cn\sqrt{\tau}, where τ\tau is the least number of entries meeting all copies (here τ=1\tau=1, and D≤nD \le n trivially).

Lemma 18 (splice). [proved] Let u,x,yu,x,y be sets of columns and Π\Pi a cut such that x∩IΠx\cap I_\Pi is empty or has its last element in yy. Put s=(x∩IΠ)∪(y∩FΠ)s=(x\cap I_\Pi)\cup(y\cap F_\Pi). If u R xu\,R\,x and u R yu\,R\,y, then u R su\,R\,s.

Proof. If uu misses x∩IΠx\cap I_\Pi, then u∩s=u∩y∩FΠu\cap s=u\cap y\cap F_\Pi, and the elements of ss above its least element belong to yy, hence to uu. Otherwise let tt be the least element of u∩x∩IΠu\cap x\cap I_\Pi. All of xx above tt lies in uu, in particular the last element c∗c^* of x∩IΠx\cap I_\Pi, which is in yy; so all of yy above c∗c^* lies in uu, and y∩FΠ⊆uy\cap F_\Pi\subseteq u. Thus all of ss above tt lies in uu. □

Theorem 19 (two safe moves, bottom-up). [proved] Let MM have row span one. Say that the state J(a)\mathcal{J}(a) holds if every pair of rows (t,s)(t,s) with s≥t+2s\ge t+2 satisfies xt R xsx_t\,R\,x_s, and every adjacent pair (t,t+1)(t,t+1) with t≥a+1t\ge a+1 does too. In the state J(a)\mathcal{J}(a) put U=xaU=x_a, W=xa+1W=x_{a+1} and consider:

(G1) for a row r∈{a,a+1}r\in\{a,a+1\} and a column yy, delete yy from every row of the vertical closure Cl⁡(r,y)\operatorname{Cl}(r,y), the smallest set S∋rS\ni r such that t∈St\in S, s>ts>t, y∈xsy\in x_s and xt∩xs∩Iy−1≠∅x_t\cap x_s\cap I_{y-1}\ne\varnothing imply s∈Ss\in S;

(G2) for a cut Π\Pi such that U∩FΠ⊆WU\cap F_\Pi\subseteq W and U∩IΠU\cap I_\Pi is empty or has its last element in WW, replace UU by U∪(W∩FΠ)U\cup(W\cap F_\Pi).

Both moves preserve J(a)\mathcal{J}(a). Hence, starting from MM and treating the adjacent pairs from bottom to top, applying moves (G1), (G2) to the pair (a,a+1)(a,a+1) until it forms no copy (which (G1) alone always achieves), one obtains a PP-free matrix; DD is at most the number of entries changed.

Proof. (G1) creates no copy in any matrix: a new copy on rows t<st<s and columns z<y′z<y' would have its zero entry (t,y′)(t,y') among the deleted ones, so y′=yy'=y and t∈St\in S, with y∈xsy\in x_s kept and z∈xt∩xsz\in x_t\cap x_s, z<yz<y; then s∈Ss\in S and yy was deleted from xsx_s. (G2) changes row aa only. For s≥a+2s\ge a+2, both UU and WW are RR-related to xsx_s by J(a)\mathcal{J}(a), every final segment FΠF_\Pi is, and the set of rows xx with x R xsx\,R\,x_s is closed under union and intersection (Lemma 13); so U∪(W∩FΠ) R xsU\cup(W\cap F_\Pi)\,R\,x_s. For t≤a−2t\le a-2, xt R Ux_t\,R\,U and xt R Wx_t\,R\,W, and the hypothesis on Π\Pi gives U∪(W∩FΠ)=(U∩IΠ)∪(W∩FΠ)U\cup(W\cap F_\Pi)=(U\cap I_\Pi)\cup(W\cap F_\Pi). Lemma 18 applies. The pairs (a−1,a)(a-1,a) and (a,a+1)(a,a+1) are not part of J(a)\mathcal{J}(a). Once the pair (a,a+1)(a,a+1) forms no copy, J(a−1)\mathcal{J}(a-1) holds. Finally, let cc be the least column of U∩WU\cap W having a column of W∖UW\setminus U to its right; (G1) applied to r=a+1r=a+1 and y=cy=c 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 J\mathcal{J} is never violated and the output is always PP-free. The file verif_portee1.py repeats this test and checks Lemmas 15 and 18 and Proposition 17.

[open] A bound D≤Cn2−αD \le Cn^{2-\alpha} for all matrices of row span one. By Corollary 16 it is necessary for a polynomial removal lemma for PP.

A span-one family at distance n4/3n^{4/3}

Throughout this section a conflict is a pair of adjacent rows carrying a copy of PP. Fix integers q≥2q \ge2 and s,p≥1s,p \ge1, and let i,j,li,j,l range over {0,…,q−1}\{0,\ldots,q-1\}.

Columns, from left to right: groups ξi,l\xi_{i,l} (pp columns each); then groups λj,l\lambda_{j,l} (pp columns each); then, for i=0,…,q−1i=0,\ldots,q-1: the groups μi,l\mu_{i,l} (pp columns each, l=0,…,q−1l=0,\ldots,q-1), followed, for j=0,…,q−1j=0,\ldots,q-1, by the block Blij\mathrm{Bl}_{ij} made of the single columns cij0,…,cij,q−1c_{ij0},\ldots,c_{ij,q-1}, a group BijB_{ij} of pp columns, and the single columns eij0,…,eij,q−1e_{ij0},\ldots,e_{ij,q-1}. Let QijQ_{ij} be the set of all columns to the right of Blij\mathrm{Bl}_{ij}, and FiF_i the set of all columns to the right of Bli,q−1\mathrm{Bl}_{i,q-1}.

Rows, from top to bottom. For i=0,…,q−1i=0,\ldots,q-1: for j=0,…,q−1j=0,\ldots,q-1, first ss rows Vij=Bij∪QijV_{ij}=B_{ij}\cup Q_{ij}, then for l=0,…,q−1l=0,\ldots,q-1 the two rows

Uijl=ξi,l∪{cij′l:j′≤j}∪Bij∪Qij,Wijl=λj,l∪{ci′jl:i′<i}∪μi,l∪{eij′l:j′<j}∪{cijl,eijl}∪Qij;\begin{aligned} U_{ijl} &= \xi_{i,l}\cup\{c_{ij'l}:j'\le j\}\cup B_{ij}\cup Q_{ij},\\ W_{ijl} &= \lambda_{j,l}\cup\{c_{i'jl}:i'<i\}\cup\mu_{i,l}\cup\{e_{ij'l}:j'<j\}\cup\{c_{ijl},e_{ijl}\}\cup Q_{ij}; \end{aligned}

once this is done for all jj (the rows attached to a pair (i,j)(i,j) form the bouquet (i,j)(i,j); bouquets are ordered lexicographically), for each ll, ss rows Ki,l=ξi,l∪{cijl}j∪FiK_{i,l}=\xi_{i,l}\cup\{c_{ijl}\}_j\cup F_i. At the bottom: for each (j,l)(j,l), ss rows Jj,l=λj,l∪{cijl}iJ_{j,l}=\lambda_{j,l}\cup\{c_{ijl}\}_i, then for each (i,l)(i,l), ss rows Ri,l=μi,l∪{eijl}jR_{i,l}=\mu_{i,l}\cup\{e_{ijl}\}_j. Call this matrix M(q,s,p)M(q,s,p); it has 2q3+4q2s2q^3+4q^2s rows and 2q3+4q2p2q^3+4q^2p columns.

Proposition 20. [proved] In M(q,s,p)M(q,s,p) every pair of rows is PP-free except the q3q^3 adjacent pairs (Uijl,Wijl)(U_{ijl},W_{ijl}), each of which carries exactly one copy, namely on columns (cijl,eijl)(c_{ijl},e_{ijl}). Hence M(q,s,p)M(q,s,p) has row span one and exactly q3q^3 copies of PP.

Proof. By Lemma 1, a row xx above a row yy forms a PP-free pair if and only if x∩yx\cap y is a final segment of yy. If x=H∪Fx=H\cup F with FF a final segment of the column set and HH to the left of FF, then y∩Fy\cap F is a final segment of yy, so the pair is PP-free as soon as H∩y=∅H\cap y=\varnothing, or xx contains every element of yy to the right of min⁡(H∩y)\min(H\cap y). The rows VijV_{ij}, UijlU_{ijl}, WijlW_{ijl} have this form with F=QijF=Q_{ij}, and Ki,lK_{i,l} with F=FiF=F_i.

(A) xx in bouquet (i,j)(i,j), yy in a later bouquet (a,b)(a,b). The head BijB_{ij} of VijV_{ij} meets no such yy. The head of Uijl′U_{ijl'} meets UablU_{abl} only if a=ia=i, l′=ll'=l, and then Uijl⊇UiblU_{ijl}\supseteq U_{ibl}; it meets WablW_{abl} only in ciblc_{ibl}, when l′=ll'=l, a>ia>i, b≤jb\le j, and the elements of WablW_{abl} to the right of ciblc_{ibl} lie in Fi⊆QijF_i\subseteq Q_{ij}. The head of Wijl′W_{ijl'} meets UablU_{abl} only in cijlc_{ijl}, when a=ia=i, l′=ll'=l, and the elements of UiblU_{ibl} to the right of cijlc_{ijl} lie in QijQ_{ij}; it meets WablW_{abl} in two cases: if b=jb=j, l′=ll'=l, then Wijl⊇WajlW_{ijl}\supseteq W_{ajl}; if a=ia=i, l′=ll'=l, the least common element lies in μi,l\mu_{i,l} and all elements of WiblW_{ibl} to its right (μi,l,eib′l(\mu_{i,l},e_{ib'l} for b′<bb'<b, ciblc_{ibl}, eible_{ibl}, Qib)Q_{ib}) belong to WijlW_{ijl}.

(B) Same bouquet. Vij∩Uijl=Bij∪QijV_{ij}\cap U_{ijl}=B_{ij}\cup Q_{ij}, Vij∩Wijl=QijV_{ij}\cap W_{ijl}=Q_{ij}; for l<l′l<l', Uijl∩Uijl′=Bij∪QijU_{ijl}\cap U_{ijl'}=B_{ij}\cup Q_{ij} and the three other intersections equal QijQ_{ij}: all final segments. Finally Uijl∩Wijl={cijl}∪QijU_{ijl}\cap W_{ijl}=\{c_{ijl}\}\cup Q_{ij} and the only element of Wijl∖UijlW_{ijl}\setminus U_{ijl} to the right of cijlc_{ijl} is eijle_{ijl}: exactly one copy.

(C) xx in bouquet (i,j)(i,j), y=Ka,ly=K_{a,l}, a≥ia\ge i. If a>ia>i, x∩y=y∖ξa,lx\cap y=y\setminus\xi_{a,l}. If a=ia=i, x∩yx\cap y is {cibl}b>j∪Fi\{c_{ibl}\}_{b>j}\cup F_i, enlarged to yy if x=Uijlx=U_{ijl} and by cijlc_{ijl} if x=Wijlx=W_{ijl}.

(D) x=Ki,lx=K_{i,l}, yy below. For yy in a bouquet (a,b)(a,b) with a>ia>i, the head ξi,l∪{cibl}b\xi_{i,l}\cup\{c_{ibl}\}_b meets only WablW_{abl} in ciblc_{ibl}, and the elements of WablW_{abl} to its right lie in FiF_i. Moreover Ki,l∩Ka,l′=Ka,l′∖ξa,l′K_{i,l}\cap K_{a,l'}=K_{a,l'}\setminus\xi_{a,l'} for a>ia>i and Ki,l∩Ki,l′=FiK_{i,l}\cap K_{i,l'}=F_i for l≠l′l\ne l'. (E) y=Jb,ly = J_{b,l}. For xx in a bouquet or x=Ki,l′x = K_{i,l'}, x∩yx \cap y is yy itself (if x=Wiblx = W_{i b l}) or of the form {cabl:a≥a0}\{c_{a b l} : a \ge a_0\}. (F) y=Ra,ly = R_{a,l}. x∩yx \cap y is yy itself, or {eabl:b>j}\{e_{a b l} : b > j\}, or empty. Rows of type JJ and RR are pairwise disjoint or equal.

Lemma 21 (rectangles). [proved] Let R1,…,RmR_1,\ldots,R_m be rectangles Rt=Zt×ΛtR_t = Z_t \times\Lambda_t in a grid, and let ϵt\epsilon_t be the number of t′<tt' < t with Rt′∩Rt≠∅R_{t'} \cap R_t \ne\varnothing. Then

∣⋃tRt∣≥∑t(min⁡(∣Zt∣,∣Λt∣)−ϵt)+.\left|\bigcup_t R_t\right| \ge\sum_t \left(\min(|Z_t|,|\Lambda_t|)-\epsilon_t\right)^+.

Proof. Choose successively Dt⊆RtD_t \subseteq R_t consisting of (min⁡(∣Zt∣,∣Λt∣)−ϵt)+\left(\min(|Z_t|,|\Lambda_t|)-\epsilon_t\right)^+ cells, no two in a common row or column, disjoint from the earlier Dt′D_{t'}. This is possible: the cells already chosen inside RtR_t come from at most ϵt\epsilon_t rectangles, each contributing a matching; in the complete bipartite graph Zt×ΛtZ_t \times\Lambda_t with ϵt\epsilon_t matchings removed, every vertex of the smaller side keeps at least max⁡(∣Zt∣,∣Λt∣)−ϵt≥min⁡(∣Zt∣,∣Λt∣)−ϵt\max(|Z_t|,|\Lambda_t|)-\epsilon_t \ge\min(|Z_t|,|\Lambda_t|)-\epsilon_t neighbours; so any min⁡(∣Zt∣,∣Λt∣)−ϵt\min(|Z_t|,|\Lambda_t|)-\epsilon_t vertices of the smaller side satisfy Hall’s condition and can be matched.

Theorem 22. [proved] Every PP-free matrix differs from M(q,s,p)M(q,s,p) in at least q3(1+min⁡(s,p))q^3(1+\min(s,p)) entries.

Proof. Let NN be PP-free and Δ\Delta the set of entries where N≠MN \ne M. For each conflict k=(i,j,l)k=(i,j,l), with rows U=UijlU=U_{ijl}, W=WijlW=W_{ijl} and columns c=cijl<e=eijlc=c_{ijl}<e=e_{ijl}, one of the four entries of the copy has changed; fix one. This gives kk a type, and with it a class of qq conflicts, a group of ss blocking rows, a target column y∈{c,e}y \in\{c,e\}, a row x∈{U,W}x \in\{U,W\}, a group GG of pp link columns and, for each earlier conflict k′′k'' of the class, a bonus entry:

typechanged entryclassblocking rowsyyGGbonus entry for k′′k''
AN(W,c)=0N(W,c)=0ii variesJj,lJ_{j,l}ccλj,l\lambda_{j,l}(W,ci′′jl),i′′<i(W,c_{i''jl}), i''<i
KN(U,c)=0N(U,c)=0jj variesKi,lK_{i,l}ccξi,l\xi_{i,l}(U,cij′′l),j′′<j(U,c_{ij''l}), j''<j
RN(W,e)=0N(W,e)=0jj variesRi,lR_{i,l}eeμi,l\mu_{i,l}(W,eij′′l),j′′<j(W,e_{ij''l}), j''<j
VN(U,e)=1N(U,e)=1ll variesVijV_{ij}eeBijB_{ij}(Uijl′′,e),l′′<l(U_{ijl''},e), l''<l

Let ZkZ_k be the set of blocking rows zz of kk with (z,y)∉Δ(z,y) \notin\Delta, ak=s−∣Zk∣a_k=s-|Z_k|, Λk\Lambda_k the set of g∈Gg \in G with (x,g)∉Δ(x,g) \notin\Delta, bk=p−∣Λk∣b_k=p-|\Lambda_k|, and Rk=Zk×ΛkR_k=Z_k \times\Lambda_k, a rectangle of the block (blocking rows) ×G\times G.

(i) Rk⊆ΔR_k \subseteq\Delta. For z∈Zkz \in Z_k, g∈Λkg \in\Lambda_k, if (z,g)∉Δ(z,g) \notin\Delta then rows x,zx,z and columns g<yg<y carry a copy in NN: (W,z;g,c)(W,z;g,c) for type A, (U,z;g,c)(U,z;g,c) for K, (W,z;g,e)(W,z;g,e) for R, (z,U;g,e)(z,U;g,e) for V. (In MM the blocking rows and the row xx contain GG, which lies to the left of yy; the blocking rows contain yy for types A, K, R and do not contain it for type V.)

(ii) Bonus. Let k′′k'' precede kk in the same class and type, with Rk′′∩Rk≠∅R_{k''} \cap R_k \ne\varnothing. Then the bonus entry of kk for k′′k'' lies in Δ\Delta. For types A, K, R there is z∈Zk′′∩Zkz \in Z_{k''} \cap Z_k, so N(z,y′′)=N(z,y)=1N(z,y'')=N(z,y)=1; the column y′′y'' is to the left of yy and M(x,y′′)=1M(x,y'')=1; if N(x,y′′)=1N(x,y'')=1 then (x,z;y′′,y)(x,z;y'',y) is a copy. For type V there is g∈Λk′′∩Λkg \in\Lambda_{k''} \cap\Lambda_k, so N(Uij′′l,g)=N(U,g)=1N(U_{ij''l},g)=N(U,g)=1 and N(U,e)=1N(U,e)=1; if N(Uij′′l,e)=0N(U_{ij''l},e)=0 then (Uij′′l,U;g,e)(U_{ij''l},U;g,e) is a copy.

(iii) Distinct entries. Assign to kk: the changed entry of its copy; the aka_k entries (z,y)(z,y), z∉Zkz \notin Z_k; the bkb_k entries (x,g)(x,g), g∉Λkg \notin\Lambda_k; and its bonus entries lying in Δ\Delta. No entry is assigned to two conflicts: entries in a row UU or WW are assigned to the conflict of that row only, except the bonus entries of type V, which lie in the column ee of the conflict receiving them and outside the columns used by the conflict of their row; entries in blocking rows lie in the column cc or ee 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), kk receives at least ϵk\epsilon_k bonus entries, ϵk\epsilon_k being the number of earlier rectangles meeting RkR_k. By (i) and Lemma 21, the block contains at least ∑k(min⁡(s−ak,p−bk)−ϵk)+\sum_k\left(\min(s-a_k,p-b_k)-\epsilon_k\right)^+ entries of Δ\Delta. The number of entries of Δ\Delta counted is thus at least

∑k(1+ak+bk+ϵk+(min⁡(s−ak,p−bk)−ϵk)+)≥∑k(1+min⁡(s+bk,p+ak))≥∑k(1+min⁡(s,p)).\sum_k \left(1+a_k+b_k+\epsilon_k+\left(\min(s-a_k,p-b_k)-\epsilon_k\right)^+\right) \ge\sum_k \left(1+\min(s+b_k,p+a_k)\right) \ge\sum_k \left(1+\min(s,p)\right).

Summing over types and classes gives ∣Δ∣≥q3(1+min⁡(s,p))|\Delta| \ge q^3(1+\min(s,p)).

Proposition 23. [proved] For all q≥2q \ge2 and s,p≥1s,p \ge1, replacing every row UijlU_{ijl} by Uijl′=(Uijl∖Bij)∪{eijl}U'_{ijl}=(U_{ijl}\setminus B_{ij})\cup\{e_{ijl}\} yields a PP-free matrix; hence the distance of M(q,s,p)M(q,s,p) to PP-freeness is at most q3(p+1)q^3(p+1). With Theorem 22: for p≤sp\le s this distance equals q3(p+1)q^3(p+1); in particular M(q,q,q)M(q,q,q), a square matrix of side n=6q3n=6q^3 with n/6n/6 copies of PP on disjoint pairs of adjacent rows, is at distance exactly q4+q3=(n/6)4/3+n/6q^4+q^3=(n/6)^{4/3}+n/6.

Proof. Uijl′=H′∪QijU'_{ijl}=H'\cup Q_{ij} with H′=ξi,l∪{cij′}j′≤j∪{eijl}H'=\xi_{i,l}\cup\{c_{ij'}\}_{j'\le j}\cup\{e_{ijl}\}, and we use the principle and the cases of the proof of Proposition 20. Pairs without a row of type UU are unchanged. In the same bouquet, Uijl′∩Wijl={cijl,eijl}∪QijU'_{ijl}\cap W_{ijl}=\{c_{ijl},e_{ijl}\}\cup Q_{ij} is a final segment of WijlW_{ijl}, Vij∩Uijl′=QijV_{ij}\cap U'_{ijl}=Q_{ij}, and for l≠l′l\ne l' the intersections of Uijl′U'_{ijl} with Uijl′′U'_{ijl'} and Wijl′W_{ijl'} equal QijQ_{ij}. If xx lies in an earlier bouquet and y=Uabl′y=U'_{abl}, then x⊇Qij∋eablx\supseteq Q_{ij}\ni e_{abl} and the head of xx meets yy as in case (A). If x=Uijl′x=U'_{ijl} and yy lies in a later bouquet (a,b)(a,b), then H′H' meets Uabl′′U'_{abl'} and Wabl′W_{abl'} as in case (A), and in addition meets WiblW_{ibl} (b>jb>j) in eijle_{ijl}; this is then the least common element, and the elements of WiblW_{ibl} to its right lie in QijQ_{ij}. For y=Ka,l′y=K_{a,l'} or Jb,l′J_{b,l'} nothing changes, since eijle_{ijl} belongs to none of these rows outside FiF_i. For y=Ra,l′y=R_{a,l'}, x∩yx\cap y is yy if a>ia>i, empty if a<ia<i, and {eibl′:b>j}\{e_{ibl'}:b>j\}, together with eijle_{ijl} when l′=ll'=l, if a=ia=i. Finally Ki,l′∩Uabl′=Uabl′∖ξa,lK_{i,l'}\cap U'_{abl}=U'_{abl}\setminus\xi_{a,l} for a>ia>i. The cost is p+1p+1 per conflict.

Corollary 24. [proved] For matrices of row span one, the distance to PP-freeness is not bounded by C(S+n)C(S+n), where SS is the sum over adjacent pairs of rows of the distance of the pair: for M(q,q,q)M(q,q,q), S=n/6S=n/6. With n/6n/6 copies at distance (n/6)4/3+n/6(n/6)^{4/3}+n/6, any removal exponent for PP is at least 9/29/2.

[computed] Exact distances obtained with a constraint solver (optimality proved) agree with the formula for (q,s,p)=(2,1,1),(2,2,2),(2,3,3),(3,1,1),(3,2,2),(3,3,3),(4,1,1),(2,3,1),(2,3,2),(3,3,1)(q,s,p)=(2,1,1),(2,2,2),(2,3,3),(3,1,1),(3,2,2),(3,3,3),(4,1,1),(2,3,1),(2,3,2),(3,3,1); for p>sp>s the two bounds differ and the solver gives 25,17,62,1725,17,62,17 for (2,2,3),(2,1,3),(3,1,2),(2,1,4)(2,2,3),(2,1,3),(3,1,2),(2,1,4). The ancillary script verif_cube.py (plain Python) rebuilds M(q,s,s)M(q,s,s) 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 KK are confined to one row and the classes of type JJ 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 PP-free, of cost (number of conflicts)×(p+1)\times(p+1). [open] Whether D≤CnmD\le Cn\sqrt{m} holds for span-one matrices with mm conflicts carrying one copy each; the family above gives nm1/3/6nm^{1/3}/6.

Open questions

  1. [open] Does PP 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 PP.

  1. [open] Extend Theorem 4 to two interleaved PP-free parts, or to mm interleaved staircase classes with a bound polynomial in mm.

  1. [open] Extend Theorem 10 to three classes.

  1. [open] Prove D≤Cn2−αD\le Cn^{2-\alpha} for matrices of row span one.

  1. [open] Close the gap between the orders n4/3n^{4/3} and n3/2n^{3/2} for two PP-free intervals with K=1K=1.

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 M(q,s,p)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.

Acknowledgement. This note was prepared with the assistance of Claude (Anthropic).

References

References

  1. [1]N. Alon, O. Ben-Eliezer, Efficient removal lemmas for matrices, Order 37 (2020), 83–101; arXiv:1609.04235.
  2. [2]L. Gishboliner, A. Shapira, Polynomial property testing, arXiv:2508.16878.arxiv.org/abs/2508.16878
  3. [3]M. Lupini, Polynomial removal for the ordered two-by-two identity matrix, preprint, Zenodo 23618367, 2 November 2026.DOI
  4. [4]OpenAI, Polynomial removal fails for ordered binary matrices, preprint, 25 September 2026.DOI
  5. [5]R. Shea, a 3×3 obstruction to polynomial removal for ordered binary matrices, public repository shea256/ordered-binary-matrix-removal, October 2026.
  6. [6]Z. Wang, A four-by-four obstruction to polynomial removal for ordered binary matrices, arXiv:2610.15370.arxiv.org/abs/2610.15370

Paper details

vlnc:W_sfuzgzvv
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
CC BY 4.0
Usage

views · 12

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Mathematics

Anthropic Claude Fable

View statement
Looking for related papers…
Contents