diff fd9b864..649cede ordered_binary_polynomial_removal_v2.txt
diff --git a/ordered_binary_polynomial_removal_v2.txt b/ordered_binary_polynomial_removal_v2.txt
index e69de29..ece509a 100644
--- a/ordered_binary_polynomial_removal_v2.txt
+++ b/ordered_binary_polynomial_removal_v2.txt
@@ -0,0 +1,707 @@
+==============================================================================
+ORDERED BINARY POLYNOMIAL REMOVAL FAILS
+A complete, self-contained account for a motivated high-school reader
+==============================================================================
+
+This note proves one clean fact and explains every ingredient. The fact is
+that "removal" for ordered binary matrices has no polynomial bound. We do
+this by building one fixed 66-by-66 pattern and, for every depth h, one huge
+n-by-n 0/1 matrix that is far from avoiding the pattern yet contains very
+few copies of it.
+
+Nothing is assumed beyond: a matrix is a rectangular grid of numbers, here
+0 or 1. If you know what a submatrix and an increasing sequence of indices
+are, you can follow all of it.
+
+Every time a proof uses a step, the step is stated first and then used. If
+you only want the idea first, read Section 0.
+
+==============================================================================
+0. THE INTUITION IN ONE PAGE
+==============================================================================
+
+A "pattern" H is a small fixed 0/1 matrix. A "copy" of H inside a big 0/1
+matrix A is a choice of rows r_1 < r_2 < ... < r_k and columns
+c_1 < c_2 < ... < c_k so that the little grid A(r_i, c_j) equals H(i, j)
+for every i, j. Copies care about zeros as well as ones, and the row and
+column orders matter separately.
+
+Write N_H(A) for the number of such copies. Write dist_H(A) for the
+smallest fraction of entries you must flip to make A have zero copies.
+
+The "polynomial removal conjecture" said, roughly: whenever a matrix is
+"far" from pattern-free, it must contain "many" copies, in fact at least a
+constant times eps^C times n^(2k). That is the natural quantitative form of
+a qualitative statement that far always implies some copies.
+
+We build H and a family A_h so that:
+
+ (distance) every way to flip fewer than m^2 entries still leaves a copy,
+ so dist_H(A_h) >= 1/d_h^2, which is "far";
+
+ (copies) A_h has at most m * n^(2k-2) copies, a vanishing fraction of
+ the n^(2k) it "should" have.
+
+Here m = 2^h grows with h and d_h is a slowly growing constant (about 386h).
+The distance stays large while the copy count stays tiny. That kills every
+polynomial bound. The same matrix also defeats a natural "pick q random rows
+and q random columns" sampler: it needs q growing exponentially in
+epsilon^(-1/2).
+
+The mechanical reason copies are so rare: all copies are pinned to a single
+special part of the matrix, a "leaf diagonal" of exactly m cells. The reason
+removal is still hard: flipping those m cells destroys the old copies but
+creates new ones, and a much larger number of flips is needed to wipe out
+all copies at once. Section 7 makes this precise.
+
+==============================================================================
+1. DEFINITIONS
+==============================================================================
+
+Fix integers k, n >= 1. A binary matrix has every entry in {0, 1}.
+
+DEFINITION 1.1 (ordered copy). Let H be a binary k-by-k matrix and A a
+binary n-by-n matrix. An ordered copy of H in A is a pair of index lists
+ r_1 < r_2 < ... < r_k (rows of A)
+ c_1 < c_2 < ... < c_k (columns of A)
+such that for every i, j in {1,...,k}:
+ A(r_i, c_j) = H(i, j).
+The two lists are chosen independently. A copy matches every zero and every
+one of H. Write N_H(A) for the number of ordered copies, and call A
+H-free if N_H(A) = 0.
+
+DEFINITION 1.2 (distance). The normalized distance from H-freeness is
+ dist_H(A) = (1/n^2) * min { |{(r,c) : A(r,c) != B(r,c)}| }
+where the minimum is over all binary n-by-n H-free matrices B. It is the
+smallest fraction of cells you must change (in either direction) to reach a
+matrix with no copies. For 0 < eps < 1 we say A is eps-far from H-free when
+dist_H(A) >= eps.
+
+A five-line worked example. Take the 2-by-2 pattern
+ P = [ 1 0 ]
+ [ 1 1 ]
+and the 3-by-3 matrix
+ A = [ 1 0 0 ]
+ [ 1 1 0 ]
+ [ 0 1 1 ].
+The only ordered copies of P in A are rows 1,2 with columns 1,2, and rows
+2,3 with columns 2,3, so N_P(A) = 2. Every other choice fails on some
+required entry: for example rows 1,2 with columns 1,3 need A(2,3) = 1 but
+A(2,3) = 0, and rows 1,3 with columns 1,2 need A(3,1) = 1 but A(3,1) = 0.
+
+==============================================================================
+2. THE CONJECTURE WE DISPROVE
+==============================================================================
+
+CONJECTURE 2.1 (polynomial ordered binary matrix removal). For every fixed
+binary k-by-k matrix H there exist constants c_H > 0 and C_H > 0 such that,
+for every integer n >= 1, every 0 < eps < 1 and every binary n-by-n matrix A,
+ N_H(A) >= c_H * eps^(C_H) * n^(2k) whenever dist_H(A) >= eps.
+
+The exponent 2k is the number of coordinates in a copy: k rows plus k
+columns, so n^(2k) is the largest possible number of copies. The conjecture
+says a positive fraction of that maximum survives whenever A is far from
+H-free, with only polynomial loss in eps.
+
+Alon and Ben-Eliezer posed it (Problem 1.4 of their 2020 paper) for finite
+families of binary matrices; the single-matrix case appears as Conjecture 4.5
+in the first arXiv version of Gishboliner-Shapira's survey. We refute the
+single-matrix case, with one fixed 66-by-66 H, which is the strongest kind of
+counterexample.
+
+==============================================================================
+3. MAIN THEOREM
+==============================================================================
+
+THEOREM 3.1. There is a fixed binary 66-by-66 matrix H with the following
+property. For every integer h >= 1 set
+ n_h = (386h + 2) * 2^h, eps_h = (386h + 2)^(-2).
+There is a binary n_h-by-n_h matrix A_h such that
+ dist_H(A_h) >= eps_h,
+ N_H(A_h) / n_h^(132) <= eps_h * 2^(-h).
+Consequently no positive constants c, C give N_H >= c * eps^C * n^(132)
+whenever dist_H >= eps, so Conjecture 2.1 is false.
+
+The exponent 132 is 2k with k = 66. The notation (386h + 2) will show up as
+d_h; it counts one coordinate (row or column) in units of a block of size m.
+Section 8 derives the "consequently" from the two displayed inequalities.
+
+==============================================================================
+4. THE FIXED PATTERN H
+==============================================================================
+
+We build H from a 64-by-64 "anchor" S and a 2-by-2 "body" P.
+
+4.1 The anchor S.
+
+Let s = 64. For an integer a with 0 <= a < 32 and a coordinate b with
+1 <= b <= 5, define the b-th bit of a (most significant first):
+ eta_b(a) = floor( a / 2^(5-b) ) mod 2.
+Then (eta_1(a), ..., eta_5(a)) is exactly the 5-bit binary expansion of a,
+so as a ranges over 0..31 these are the 32 distinct binary words of length 5,
+in lexicographic order.
+
+Define the 64-by-64 binary matrix S by its entries S(u,v) for 1 <= u,v <= 64:
+ if 33 <= u <= 64 and 60 <= v <= 64:
+ S(u,v) = eta_{v-59}( u - 33 )
+ otherwise:
+ S(u,v) = 1 if u != v, and 0 if u = v.
+
+So S is the "complement of the identity": all ones except zeros on the
+diagonal. The exception is the rectangle of rows 33..64 and columns 60..64
+(32 rows, 5 columns), where each row u holds the 5-bit expansion of u-33.
+Notice rows 33..64 look at columns 60..64 and show all 32 five-bit words.
+
+4.2 The body P and the standard vectors.
+
+ P = [ 1 0 ]
+ [ 1 1 ]
+
+Let e_1, e_2 be the first two standard basis vectors of R^64: e_1 is the
+column with 1 in position 1 and 0 elsewhere; e_2 has 1 in position 2.
+
+4.3 The pattern H.
+
+The pattern is the 66-by-66 matrix assembled in blocks:
+ H = [ S e_1 e_2 ]
+ [ e_1^T 1 0 ]
+ [ e_2^T 1 1 ]
+where ^T denotes transpose. Concretely, the top-left 64-by-64 block is S.
+Column 65 of H is e_1 (a 1 in row 1, zeros elsewhere) over rows 1..64.
+Column 66 is e_2 (a 1 in row 2, zeros elsewhere) over rows 1..64.
+Row 65 is e_1^T over columns 1..64, then the entries 1, 0.
+Row 66 is e_2^T over columns 1..64, then the entries 1, 1.
+The lower-right 2-by-2 corner of H is exactly P. Set k = s + 2 = 66.
+
+Two tiny facts about P that drive everything. For bits a, b in {0,1}:
+
+ the 2x2 matrix [[1,a],[1,b]] equals P exactly when (a,b) = (0,1),
+ so it avoids P exactly when b <= a;
+
+ the 2x2 matrix [[a,b],[1,1]] equals P exactly when (a,b) = (1,0),
+ so it avoids P exactly when a <= b.
+
+In words: in the first shape, a 0 in the bottom-right forces a 0 in the
+top-right, and a 1 in the top-right forces a 1 in the bottom-right. In the
+second shape, a 0 top-right forces a 0 top-left, and a 1 top-left forces a 1
+top-right. These two "propagation rules" are the whole engine.
+
+==============================================================================
+5. THE HOST MATRIX A_h
+==============================================================================
+
+Fix h >= 1 and m = 2^h. We describe the row set and column set (each of the
+same size n = d_h * m), their order, and then every entry.
+
+5.1 Tree blocks.
+
+Take a full binary tree of depth h. Depth i (0 <= i <= h) has 2^i nodes
+p = 0, 1, ..., 2^i - 1, and node p has children 2p and 2p+1.
+
+For 0 <= i < h, each node p at depth i is given two disjoint row blocks
+R_i^-(p), R_i^+(p) and two disjoint column blocks C_i^-(p), C_i^+(p),
+each of size m / 2^i.
+At depth h each node p has one row block and one column block, each of size
+m / 2^h = 1. We give each of them both names:
+ R_h^-(p) = R_h^+(p), C_h^-(p) = C_h^+(p).
+Apart from these forced equalities, all row blocks are pairwise disjoint, and
+all column blocks are pairwise disjoint. Positions in these blocks are called
+variable positions.
+
+Write R_i^sigma = union over p of R_i^sigma(p), and C_i^sigma likewise, for
+sigma in {-,+}. Each such set has size m. For 1 <= i <= h and d in {0,1},
+let R_{i,d}^sigma be the same union but only over nodes p with p = d mod 2,
+and similarly C_{i,d}^sigma.
+
+Also add a dummy row block R_* and a dummy column block C_*, each of size m.
+
+5.2 The order of rows and columns.
+
+Order variable rows recursively. At an internal node (depth < h) place, in
+this order: its minus block, then the subtrees of child 0 and child 1, then
+its plus block. At a leaf place its single block once.
+Order variable columns by the same recursion but with the signs reversed:
+plus block first, then the two subtrees, then the minus block.
+Finally place R_* after all variable rows, and C_* before all variable
+columns. Inside every block use any fixed order.
+
+For two disjoint blocks X, Y write X < Y when every position of X precedes
+every position of Y. Let pi(p) = floor(p/2) be the parent of p. The recursive
+orders give, for 1 <= i <= h, nodes p and q at depth i and nodes a and b at
+depth i-1:
+ R_i^+(p) < R_{i-1}^+(a) if and only if pi(p) <= a,
+ R_{i-1}^-(a) < R_i^-(p) if and only if pi(p) >= a,
+ C_{i-1}^+(b) < C_i^+(q) if and only if pi(q) >= b,
+ C_i^-(q) < C_{i-1}^-(b) if and only if pi(q) <= b.
+Why: the subtrees rooted at depth i-1 sit consecutively in increasing node
+order, and a child block lies between the two blocks of its own parent
+(including when the child is a leaf). Comparing the parent index with a or b
+gives the four comparisons.
+
+5.3 Modes.
+
+A "mode" is one of 6h labels. Each mode names two row sets R_1(t), R_2(t)
+and two column sets C_1(t), C_2(t). For 1 <= i <= h and d in {0,1}:
+
+ mode t R_1(t) R_2(t) C_1(t) C_2(t)
+ -------------------------------------------------------------------
+ V_i^+ R_i^+ R_{i-1}^+ C_* C_{i-1}^+
+ V_i^- R_{i-1}^- R_i^- C_* C_{i-1}^-
+ W_{i,d}^+ R_{i,d}^+ R_* C_{i-1}^+ C_{i,d}^+
+ W_{i,d}^- R_{i,d}^- R_* C_{i,d}^- C_{i-1}^-
+
+The V modes pair consecutive row levels using a dummy column; the W modes
+pair consecutive column levels using a dummy row and fix a child parity.
+For every t the two row sets are disjoint and the two column sets are
+disjoint. An "ordered body in mode t" uses rows r_1 < r_2 with r_j in
+R_j(t) and columns c_1 < c_2 with c_j in C_j(t).
+
+Order the modes by increasing i; at depth i use the order
+ V_i^+, V_i^-, W_{i,0}^+, W_{i,1}^+, W_{i,0}^-, W_{i,1}^-.
+
+Before all variable and dummy positions on each axis, place one anchor block
+per mode, in the mode order. The row block of mode t is split into s = 64
+successive groups Rhat_t(u), 1 <= u <= s, and its column block is split into
+s successive groups Chat_t(v), 1 <= v <= s. Each group has size m. Positions
+in these groups are anchor positions; all others are non-anchor positions.
+
+5.4 How many positions on each axis.
+
+There are 6h modes and s = 64 groups per mode on each axis, so 6 h s = 384h
+anchor groups. The variable positions form 2h+1 disjoint groups of size m
+(two signs at each depth 0..h-1, and one shared leaf group). Add the dummy
+block: 2h+1+1 = 2h+2 groups of size m. Hence the number of positions on
+either axis is
+ n = d_h * m, d_h = 384h + 2h + 2 = 386h + 2.
+Identify each ordered axis with {1, ..., n}.
+
+5.5 Every entry of A_h.
+
+Define the binary matrix A_h by these rules; together they assign every cell.
+
+RULE 1 (anchor to anchor). Between an anchor group Rhat_t(u) and an anchor
+group Chat_{t'}(v): put S(u,v) if t = t', and 0 if t != t'.
+
+RULE 2 (non-anchor to anchor). Let r be a non-anchor row. Against the s
+anchor column groups of a mode t, r shows the vector e_j^T (a 1 in position j,
+zeros elsewhere) if r belongs to R_j(t), and the all-zero vector if r belongs
+to neither R_1(t) nor R_2(t). Symmetrically, a non-anchor column c shows e_j
+against the anchor row groups of mode t if c belongs to C_j(t), and zero if
+it belongs to neither. Disjointness of the two role sets makes this
+unambiguous.
+
+RULE 3 (non-anchor to non-anchor). Between non-anchor positions put 1
+whenever the row or the column is dummy. Between two variable positions use
+the following table (indices p, q are node indices; pi(p) = floor(p/2)),
+and put 0 in every case not listed:
+
+ row block column block depth range value
+ ----------------------------------------------------------------
+ R_i^+(p) C_i^+(q) 0 <= i <= h [p <= q]
+ R_i^-(p) C_i^-(q) 0 <= i < h [p < q]
+ R_i^+(p) C_{i-1}^+(q) 1 <= i <= h [pi(p) <= q]
+ R_i^-(p) C_{i-1}^-(q) 1 <= i <= h [pi(p) < q]
+
+Here [P] is 1 when statement P is true and 0 otherwise. Every displayed
+value is constant on the given pair of blocks. The table is consistent:
+the first line has 0 <= i <= h and the second 0 <= i < h, so they never
+describe the same pair of blocks (the minus and plus blocks are distinct
+for i < h, and the second line stops before the shared leaves). At the
+leaves only the first line applies, giving A(r,c) = [p <= q] for leaf blocks
+of indices p, q. In particular the leaf diagonal cell, where a leaf row and
+the matching leaf column meet, is 1.
+
+==============================================================================
+6. DISTANCE: FEWER THAN m^2 FLIPS CANNOT KILL ALL COPIES
+==============================================================================
+
+We state and prove the distance bound directly.
+
+PROPOSITION 6.1. Let h >= 1, m = 2^h, A = A_h of order n = d_h m. Every
+binary n-by-n H-free matrix differs from A in at least m^2 entries. Hence
+ dist_H(A_h) >= m^2 / n^2 = 1 / d_h^2 = eps_h.
+
+The strategy, in words. Suppose B is A with fewer than m^2 entries flipped.
+We must show B still contains H. We pick one path down the tree on each axis
+(the same leaf index z on both axes), one position in each level block on
+that path, and one position in every anchor and dummy group, at random. The
+chance that the random selection touches any flipped cell is at most
+|E|/m^2 < 1, so some selection avoids all flips wherever it matters. On that
+selection, the anchors are intact, so each mode's body is a 2-by-2 window
+into B. If B avoided P in every mode, the top-left and bottom-left "minus"
+values would be forced to be constant down the whole path, contradicting the
+two different root values at the shared leaf. Hence some mode shows P and,
+with intact anchors, that is a full copy of H.
+
+PROOF OF PROPOSITION 6.1. Fix any binary matrix B differing from A on a set
+E of M < m^2 cells. We find a copy of H in B.
+
+Step 1 (random selection that avoids E). On each axis partition the
+positions into classes: the anchor groups, the dummy group, the variable
+classes of each sign at levels 0..h-1, and the single shared leaf class.
+Every class has size m.
+
+Choose z uniformly in {0, ..., m-1}, and put
+ a_i = floor( z / 2^(h-i) ), 0 <= i <= h.
+Then a_i is the ancestor at depth i of leaf z, and floor(a_i/2) = a_{i-1}.
+Choose
+ x_i^sigma uniformly in R_i^sigma(a_i),
+ y_i^sigma uniformly in C_i^sigma(a_i),
+for sigma in {-,+}, using one shared choice at the leaf:
+ x_h^+ = x_h^-, y_h^+ = y_h^-.
+Also choose one uniform position in every anchor group and in each dummy
+group; call the dummy choices x_* and y_*. Conditional on z, all choices in
+different classes are independent, including choices on opposite axes.
+
+Each variable choice is uniform on its size-m class: a fixed node at depth i
+is picked with probability 2^(-i), and its block has size m/2^i, so every
+position in that class is picked with probability 1/m. An anchor or dummy
+choice is independent of every choice on the opposite axis. Consequently,
+for every cell (r,c) having at least one anchor or dummy coordinate, or
+having both coordinates at the root level, the probability that both r and c
+are selected is exactly 1/m^2. There is exactly one choice per size-m class,
+so each cell is counted once. Summing over the cells of E of these types:
+ Pr( some selected cell of these types lies in E ) <= |E|/m^2 < 1.
+Therefore some selection avoids all such cells. Fix one. Then every
+selected anchor and dummy incidence, and the selected root entries, agree in
+A and B. Flips at other cells are simply ignored.
+
+Step 2 (what a mode forbids). For each mode t, its selected anchor positions
+form the matrix S inside B, because those anchor cells were not flipped.
+Those anchors precede all selected non-anchor positions, and their entries to
+the selected positions in R_j(t) and C_j(t) are the prescribed vectors e_j,
+also unchanged. Hence any ordered pair of selected rows in R_1(t), R_2(t)
+and ordered pair of selected columns in C_1(t), C_2(t) whose B-entries form
+ P = [ 1 0 ]
+ [ 1 1 ]
+completes these anchors to a copy of H. Suppose B were H-free; then this body
+P could never occur, for any mode.
+
+Step 3 (propagating the root values). The unchanged root entries give
+ B(x_0^+, y_0^+) = 1, B(x_0^-, y_0^-) = 0.
+We claim this holds at every level of the path:
+ B(x_i^+, y_i^+) = 1 and B(x_i^-, y_i^-) = 0 for 0 <= i <= h.
+Assume it holds at level i-1, for some 1 <= i <= h. Work one mode at a time;
+all four chosen pairs are in their designated sets and in the required order
+because the chosen nodes are parent and child.
+
+Mode V_i^+. Rows x_i^+, x_{i-1}^+; columns y_*, y_{i-1}^+. The dummy column
+gives a left column of ones, and the bottom-right is the plus diagonal entry
+at level i-1, which is 1. So the body is
+ [ 1 B(x_i^+, y_{i-1}^+) ]
+ [ 1 1 ].
+Avoiding P forces the top-right to be 1. Hence B(x_i^+, y_{i-1}^+) = 1.
+
+Mode V_i^-. Rows x_{i-1}^-, x_i^-; columns y_*, y_{i-1}^-. The top-right is
+the minus diagonal entry at level i-1, which is 0; the other three entries
+are 1 except the bottom-right, which is the value we want to pin. The body is
+ [ 1 0 ]
+ [ 1 B(x_i^-, y_{i-1}^-) ].
+Avoiding P forces the bottom-right to be 0. Hence B(x_i^-, y_{i-1}^-) = 0.
+
+Mode W_{i,d}^+, with d = a_i mod 2. Rows x_i^+, x_*; columns y_{i-1}^+,
+y_i^+. The top-left is B(x_i^+, y_{i-1}^+), which the V_i^+ step just forced
+to be 1. The dummy row supplies the bottom-left and bottom-right ones. The
+body is
+ [ 1 B(x_i^+, y_i^+) ]
+ [ 1 1 ].
+Avoiding P forces B(x_i^+, y_i^+) = 1.
+
+Mode W_{i,d}^-. Rows x_i^-, x_*; columns y_i^-, y_{i-1}^-. The top-right is
+B(x_i^-, y_{i-1}^-), just forced to be 0. The body is
+ [ B(x_i^-, y_i^-) 0 ]
+ [ 1 1 ].
+Avoiding P forces B(x_i^-, y_i^-) = 0.
+
+This proves the claim at every level. At level h the row and column
+positions were chosen equal across signs: x_h^+ = x_h^-, y_h^+ = y_h^-.
+So the two equalities read B(same cell) = 1 and B(same cell) = 0, impossible.
+Therefore B has a copy of H, contradicting H-freeness. Every B with fewer
+than m^2 flips contains H, so the distance is at least m^2/n^2 = 1/d_h^2.
+END PROOF.
+
+==============================================================================
+7. COPY COUNT: ALL COPIES LAND ON A LEAF DIAGONAL
+==============================================================================
+
+Now we count copies in the UNEDITED matrix A_h. The result is that every
+copy is pinned to one special cell on the leaf diagonal, and there are only
+m such cells.
+
+LEMMA 7.1 (anchor properties). The rows of S are pairwise distinct, and so
+are its columns. Every column has at most one zero among rows 1..32, and
+every row has at most one zero among columns 1..32. Each row has at least 58
+ones; each column has at least 48 ones. The rows 33..64 restricted to columns
+60..64 are exactly the 32 distinct binary words of length 5.
+
+PROOF. The replacement in the definition of S does not touch rows 1..32 or
+columns 1..59. In columns 1..59, each of rows 1..59 has its own distinguishing
+zero, while rows 60..64 are all ones there; those five rows differ in the
+replacement block. So rows are distinct and each has at least 58 ones. Each
+of the first 59 columns has exactly one zero, in its own row; the last five
+columns are distinct among themselves because they are distinct coordinates
+on the list of all 5-bit words, and each has exactly 16 zeros (all in the
+replacement block), so they differ from every earlier column and have 48
+ones. END PROOF.
+
+LEMMA 7.2 (mode incidences). A variable position on either axis belongs to
+designated sets of at most four modes. Consequently, against any collection
+containing at most one representative of each anchor group on the opposite
+axis, a variable position has at most four entries equal to 1.
+
+PROOF. A non-leaf row in R_i^sigma(p) can be in V_i^sigma, V_{i+1}^sigma,
+or W_{i,d}^sigma with d = p mod 2 (dropping levels outside 1..h); that is at
+most three. A leaf row can be in V_h^+, V_h^-, W_{h,d}^+, W_{h,d}^-, at most
+four. A non-leaf column in C_i^sigma(p) can be in V_{i+1}^sigma,
+W_{i+1,0}^sigma, W_{i+1,1}^sigma, W_{i,d}^sigma; a leaf column only in
+W_{h,d}^+ and W_{h,d}^-. For each participating mode the entries to its
+anchor groups form one unit vector, giving the second claim. END PROOF.
+
+LEMMA 7.3 (no five non-anchor columns are shattered). For any five distinct
+non-anchor columns of A_h, the non-anchor rows do not realize all 32 binary
+words on those columns.
+
+PROOF. If one of the five columns is the dummy column, its entry is 1 in
+every non-anchor row, so we cannot see a word with a 0 in that slot; done.
+Otherwise all five columns are variable. Group them by their class C_i^sigma,
+counting the shared leaf class once. Within a class order the chosen columns
+by node index (any order inside a node block). The entry rules show that in
+each class where a variable row is nonzero, its ones form a suffix. A
+non-leaf row is nonzero in at most two classes (its own level and sign, and
+the preceding level of the same sign); a leaf row in at most three (the leaf
+class and both signs at level h-1). A class with a selected columns has at
+most a distinct nonempty suffixes; over all classes there are at most five
+such suffixes total. A variable-row trace is a union of at most three of them,
+giving at most sum_{j=0..3} C(5,j) = 26 possible traces, and the dummy rows
+add at most one more. So at most 27 < 32 words appear. END PROOF.
+
+LEMMA 7.4 (anchor rigidity). Every ordered copy of S in A_h uses the row and
+column anchor groups of a single mode t. On each axis it uses exactly one
+position from each of that mode's 64 groups, in the prescribed order.
+
+PROOF. Two positions inside one anchor group have identical entries in all
+of A_h, so a copy uses at most one position per anchor group (else it would
+need the two to differ somewhere, which they do not, and the row or column
+of S would repeat). The same argument gives at most one dummy position per
+axis.
+
+Suppose at most 32 selected rows and at most 32 selected columns are anchors.
+Because anchors precede all non-anchors, the last 32 selected rows and the
+last 5 selected columns are non-anchor. By Lemma 7.1 those 5 columns realize
+all 32 five-bit words on the 32 row positions, contradicting Lemma 7.3.
+Therefore at least one axis has more than 32 anchor positions.
+
+Case A: more than 32 selected rows are anchors. Then in particular the first
+32 selected rows are anchors. No selected column can be variable:
+Lemma 7.2 would give at most four ones among these rows, but each column of S
+has at least 31 ones among the first 32 rows. So at least 63 selected
+columns are anchors, since at most one selected column is dummy. Any two
+selected anchor columns share a 1 among the first 32 selected rows (each has
+at most one zero there), so they must belong to the same mode: entries
+between anchor groups of different modes are 0. Call that mode t. Every
+selected anchor row is also of mode t: an anchor row of another mode would be
+zero on the at least 63 selected anchor columns, hence would have at most one
+1 in the whole copy, contradicting the density in Lemma 7.1. A selected dummy
+column is now impossible: against the selected anchor rows of mode t it has
+at most one 1, again contradicting the density of the first 32 rows of S. So
+all selected columns are anchors of mode t, and any non-anchor row has at
+most one 1 against them, so all selected rows are anchors of t.
+
+Case B: more than 32 selected columns are anchors. The same argument with
+the axes interchanged works, because everything used afterwards is symmetric:
+entries between distinct modes are 0, the first 32 rows and columns of S each
+contain at most one zero in the relevant restriction, all rows and columns of
+S have more than one 1, and Lemma 7.2 holds on both axes.
+
+There are 64 selected positions on each axis and exactly 64 anchor groups in
+mode t. No group is repeated, so every group is used, in construction order.
+END PROOF.
+
+COROLLARY 7.5 (the two body roles). In every ordered copy of H in A_h, the
+first 64 rows and columns are anchor representatives of one mode t. Its two
+body rows lie respectively in R_1(t) and R_2(t); its two body columns lie
+respectively in C_1(t) and C_2(t).
+
+PROOF. Apply Lemma 7.4 to the copy's S-prefix. The two body rows must show
+e_1^T and e_2^T against these anchor columns. An anchor row of another mode
+shows the zero vector, and an anchor row of mode t shows a row of S, which has
+more than one 1; so neither body row is an anchor. By the definition of the
+entries from non-anchor rows to anchor groups, the vector e_j^T occurs exactly
+on R_j(t), for j = 1, 2, and the two sets are disjoint. The column argument
+is identical. END PROOF.
+
+PROPOSITION 7.6 (copy count). For every h >= 1, every ordered copy of H in
+A_h maps pattern entry (s+1, s+1) into the leaf diagonal
+ L_h = union over p in 0..m-1 of R_h^+(p) x C_h^+(p).
+In particular |L_h| = m, and
+ N_H(A_h) <= m * n^(2k - 2),
+ N_H(A_h) / n^(2k) <= 2^(-h) / d_h^2.
+
+PROOF. By Corollary 7.5 the last two rows and columns of a copy lie in the
+prescribed body sets of a single mode. Their four entries must form P. We
+check the four kinds of mode, using the tree order comparisons of Section 5.2
+and the entry table of Section 5.5; write pi(p) = floor(p/2).
+
+Mode V_i^+. Let p be the child-level row index, a the parent-level row index,
+b the parent-level column index. The row order gives pi(p) <= a. The P
+bottom-right entry 1 gives a <= b, so pi(p) <= b, which forces the top-right
+entry to be 1, contradicting P's 0 there.
+
+Mode V_i^-. Same names at the same levels. The row order gives pi(p) >= a,
+the P top-right entry 0 gives a >= b, so pi(p) >= b, forcing the bottom-right
+entry to be 0, contradicting P's 1 there.
+
+Mode W_{i,d}^+. Let p, q be the child-level row and column indices, b the
+parent-level column index. The column order gives b <= pi(q); the P top-left
+entry 1 gives pi(p) <= b. Since p = q = d mod 2, that forces p <= q, so the
+top-right entry is 1, contradicting P.
+
+Mode W_{i,d}^-. The column order gives pi(q) <= b; the P top-right entry 0
+gives pi(p) >= b. The common parity makes p >= q. If i < h, the top-left
+entry is [p < q] = 0, impossible. If i = h, the top-left entry is [p <= q]
+(leaf blocks are shared), which can be 1 only when p = q. Then the top-left
+entry of the body, namely pattern entry (s+1, s+1), lies in L_h.
+
+Each leaf block has size m / 2^h = 1, so L_h has exactly m cells. For each
+such cell, fixing its row image and column image uses one row index and one
+column index of H; there are at most n^(k-1) ways to choose the other row
+indices and at most n^(k-1) ways for the other column indices, and the
+increasing order and prescribed entries can only reduce these counts. So
+N_H(A_h) <= m * n^(2k-2). Dividing by n^(2k) gives the second inequality
+since n = d_h m and m = 2^h. END PROOF.
+
+REMARK 7.7 (hitting is not the same as repairing). Flip the m cells of L_h
+from 1 to 0: that destroys every original copy. But it creates new ones.
+Fix a leaf index p and put d = p mod 2. In mode W_{h,d}^+ choose the leaf row
+in R_h^+(p) and any dummy row; choose, in this order, a column in
+C_{h-1}^+(pi(p)) and the leaf column in C_h^+(p). These rows and columns are
+in the required order, and their body is now
+ [ 1 0 ]
+ [ 1 1 ],
+because the upper-left is the unchanged parent-to-child entry (which is 1),
+the upper-right is the changed leaf diagonal (now 0), and the lower entries
+are dummy incidences (1). Choosing one position from every anchor group of
+this mode completes a new copy of H, since all anchor entries and signatures
+are unchanged. So deleting every original copy is not the same as a repair.
+
+==============================================================================
+8. ASSEMBLING THE MAIN THEOREM
+==============================================================================
+
+PROOF OF THEOREM 3.1. For each integer h >= 1 set d_h = 386h + 2,
+epsilon_h = d_h^(-2), n_h = d_h * 2^h, and let A_h be the matrix of
+Section 5. Proposition 6.1 says every H-free binary matrix differs from A_h
+in at least m^2 = epsilon_h * n_h^2 entries, so dist_H(A_h) >= epsilon_h.
+Proposition 7.6 says N_H(A_h) / n_h^(132) <= epsilon_h * 2^(-h). Both claims
+of Theorem 3.1 hold.
+
+Now fix arbitrary real c, C > 0. As h grows,
+ N_H(A_h) / ( epsilon_h^C * n_h^(132) )
+ <= epsilon_h * 2^(-h) / epsilon_h^C
+ = epsilon_h^(1 - C) * 2^(-h)
+ = (386h + 2)^(2C - 2) * 2^(-h),
+which tends to 0 because the first factor is a fixed power of h and the
+second decays exponentially. Choose h with that quantity < c. Then
+0 < epsilon_h < 1, A_h is epsilon_h-far from H-free, and
+N_H(A_h) < c * epsilon_h^C * n_h^(132). This violates the conjectured bound
+for every c, C, so Conjecture 2.1 is false for this single H. END PROOF.
+
+==============================================================================
+9. THE SAMPLING CONSEQUENCE
+==============================================================================
+
+A natural tester picks q rows and q columns at random and rejects only if the
+little q-by-q submatrix contains H. For this family of matrices that tester
+needs q growing faster than any polynomial in 1/epsilon.
+
+COROLLARY 9.1 (canonical row-column sampling). Fix h >= 1 and an integer
+0 <= q <= n_h. Choose a uniformly random q-element row set R and,
+independently, a uniformly random q-element column set C. Reject only if the
+induced submatrix A_h[R, C] (with inherited orders) contains an ordered copy
+of H. Then
+ Pr(reject) <= epsilon_h * 2^(-h) * q^2,
+and this probability is 0 when q < 66. For every fixed rho in (0, 1],
+achieving rejection probability at least rho requires
+ q >= sqrt(rho) * epsilon_h^(-1/2) * 2^(h/2),
+hence q >= exp( Omega( epsilon_h^(-1/2) ) ) along the sequence epsilon_h as
+h tends to infinity. Here q is the sample size on each axis; the sampled
+submatrix has q^2 entries.
+
+PROOF. By Proposition 7.6 every copy of H in A_h uses a cell of L_h, and
+|L_h| = 2^h. For a fixed cell (r,c), independence gives
+Pr((r,c) in R x C) = (q / n_h)^2. Rejection implies R x C meets L_h, so the
+union bound gives
+ Pr(reject) <= 2^h * (q / n_h)^2 = 2^h * q^2 / (d_h^2 * 4^h)
+ = q^2 / (d_h^2 * 2^h) = epsilon_h * 2^(-h) * q^2.
+If q < 66 no sampled submatrix can even contain the 66-by-66 H, so rejection
+is 0. Rearranging Pr(reject) >= rho gives the lower bound on q, and
+epsilon_h^(-1/2) = 386h + 2 makes it grow essentially like 2^(h/2) times h,
+i.e. exp(Omega(eps^(-1/2))). END PROOF.
+
+==============================================================================
+10. WHERE THIS SITS: HISTORY AND CONTEXT
+==============================================================================
+
+Alon, Fischer and Newman raised the ordered-matrix question after proving
+that fixed forbidden families are testable with a polynomial number of queries
+when row and column order is ignored (SIAM J. Comput. 2007, Section 7).
+
+Alon and Ben-Eliezer gave the qualitative polynomial removal lemma for
+ordered graphs and matrices and then asked for the quantitative polynomial
+version for fixed finite families (Order 2020, Problem 1.4). The single-matrix
+version appears explicitly as Conjecture 4.5 in the first arXiv version of the
+survey by Gishboliner and Shapira (2025). Theorem 3.1 resolves it negatively
+for a single square pattern.
+
+Alon, Ben-Eliezer and Fischer proved qualitative ordered matrix removal
+(FOCS 2017, Theorem 1.8 of the full version): a positive copy-density bound
+holds for every fixed positive distance. Our work concerns how that bound
+grows as the distance shrinks. Polynomial bounds are known when the family is
+closed under row permutations (and, by transposition, column permutations):
+Alon-Ben-Eliezer, Theorem 1.5. The induced removal classification for ordered
+graphs (Gishboliner-Tomon 2022, Theorem 1.1) is a different model, with one
+vertex order and symmetric adjacency.
+
+Nonpolynomial lower bounds were known before for ternary hosts: Fischer and
+Rozenberg built one for a fixed two-symbol 2-by-2 pattern with row and column
+order ignored (2007), and Alon-Ben-Eliezer give a related ternary
+progression-free-set construction (2020, Section 5.1). Those use a third
+symbol in the host. Ours uses only 0 and 1.
+
+A relevant positive result is Alon-Ben-Eliezer Theorem 1.2: if many
+entry-disjoint copies exist, a small cell set meets all copies when copy
+density is small. That lemma lets one "hit" copies, but (Remark 7.7) does not
+let one repair them, because new copies can appear. Our numbers make the gap
+explicit: all original copies meet a set of m cells, while any binary repair
+must change at least m^2 cells.
+
+PROOF ROADMAP OF THE WHOLE PAPER (a final overview).
+
+1. Pattern. S is the complement-of-identity 64-by-64 matrix with a 32-by-5
+ block replaced by all five-bit words. H is S bordered by the vectors e_1,
+ e_2 and the 2-by-2 body P.
+
+2. Anchors. The rows and columns are grouped into anchor blocks (one per
+ mode), variable tree blocks, and a dummy block. Entries are fixed so that
+ any copy of H must first copy S inside a single mode's anchor blocks.
+
+3. Pinning (Section 7). A density/shattering argument forces the copy's
+ anchor part into one mode; the body roles are then forced; the four mode
+ checks force the body's top-left cell to be a diagonal leaf cell, of which
+ there are only m.
+
+4. Distance (Section 6). Choose a random path and one representative per
+ block. Fewer than m^2 flips avoid the selection with positive probability.
+ If the matrix were H-free, the two propagation rules would drive a 1 and a
+ 0 down the path to the same shared leaf cell, a contradiction.
+
+5. Conclusion (Section 8). Few copies (at most m n^(2k-2)) plus large
+ distance (at least 1/d_h^2) contradict any N_H >= c eps^C n^(2k) bound.
+
+6. Sampling (Section 9). Copies are concentrated on m leaf-diagonal cells,
+ so a q-by-q sample catches one with probability at most eps 2^(-h) q^2;
+ beating any fixed rho forces q = exp(Omega(eps^(-1/2))).
+
+==============================================================================
+END
+==============================================================================