The Setting
The distance under consideration counts arbitrary binary changes, including changes from to . For an integer , write . A binary matrix of order is a function , with the natural orders on both index sets.✦
The anchor is the binary matrix of order in (1). Here the binary digit is the indicator that is odd.✦ (1)✦ The forbidden matrix has order and is defined by (2). Its first body index is , corresponding to paper index . (2)✦
An increasing index map is a strictly increasing function.✦ An ordered copy of in a binary matrix is a pair of independently chosen increasing row and column maps such that for every , including entries of equal to zero.✦ The ordered copy count of a binary matrix is the number of ordered copies of in , and is -free when .✦
For binary matrices and of the same order, the Hamming distance is the number of cells where and differ.✦ For a binary matrix of order , the minimum repair size is the smallest number of entries that must change to obtain an -free binary matrix, and the normalized removal distance is this number divided by , as in (3). (3)
The Ordered Host
Fix and the parameters in (4). (4) A variable position is a pair .✦ For a variable position , the depth is the integer , the sign is for even and for odd , and the node index is the integer . For , the signed level class consists of the positions of depth whose sign is when .✦ Both signs use the same leaf class . Write ✦ and for .
A constraint mode is an integer .✦ For a constraint mode , the level is and the type is . An anchor position is a triple .✦ The host position set is the disjoint union , where is a separate copy of of dummy positions.✦
The row roles and column roles are subsets of given by (5); no anchor position has a role. For , set . The first two types are vertical modes, and the other types are horizontal modes. (5)
The variable matrix is defined in (6). In that display, , and , with corresponding notation for . (6)✦ The raw host is the matrix in (7). (7)✦
Variable rows and columns have separate traversal orders. For of depth , put and . The subtree entry key , subtree exit key and leaf key are the ordered five-tuples in (8). (8) The variable row order and variable column order compare the keys and of (9) lexicographically.✦ (9)✦ The host row order puts the anchor positions first, then the variable positions, then the dummy positions.✦ The host column order puts the anchor positions first, then the dummy positions, then the variable positions.✦ Anchors are ordered lexicographically by , and dummies by their coordinate. Let and be the respective row and column enumerations.
For bijections , the reindexed host is the binary matrix of order obtained from by (10). The ordered host uses the separate enumerations just specified. (10)✦
Guarded Paths
For a binary matrix , a body at rows and columns is a selected array equal to in that displayed order.✦ Given paths and , and dummy positions , , the four ordered edge rectangles are defined in (11). A mode body in a binary matrix is a body on at least one of the four ordered edge rectangles .✦ (11)
An anchor frame in a matrix of order consists of increasing maps .✦ For an ordered rectangle , let and be its sets of two selected row and column positions. The anchor and signature cell set is defined in (12). (12)✦ A guarded path selection in is a choice of row paths , column paths and dummy positions , all in , together with four anchor frames for every . For a guarded path selection in , the core cells , edge guard cells and finite guard set are the cell sets defined in (13). (13)
A selected anchor frame of mode has rows and columns for , with both selections increasing.✦ For , the common seed frame of mode is the selected anchor frame with and for all .✦
The sampled selection uses three independent uniform seeds . For , its node and offset mixing and signed sampled variable positions are given by (14). The sampled coordinate belongs to . (14) Writing for dummy position , the sampled paths and dummies are given by (15) for . For , the paths retain their value at . (15) For , set and . The four sampled frames are specified in (16); the first two use vertical modes, and the last two use horizontal modes with the parity bit . (16) Denote this selection by .
The sampling order conditions for row and column enumerations require every common seed anchor frame to be increasing and to precede every nonanchor position on its respective axis. They also require variables to precede dummies on the row axis and dummies to precede variables on the column axis, with the path directions in (17) for every seed choice and . (17)
The Claim
Theorem 1. Let , and let be the ordered host in (10). For every -free binary matrix of order , the repair bound is (18). (18)✦ More generally, let be positive integers and let be a binary matrix of order . Suppose every -free binary matrix of that order differs from in at least entries. The normalized bound is (19). (19)✦
In the paper, the result reads: for , , and , every -free binary matrix of order differs from in at least entries, and consequently is -far from being -free, with .
What Is Checked
The repair statement is over the separately enumerated host and arbitrary binary -free matrices on the same ordered indices. The host position set has cardinality .✦ Both traversal keys in (9) are injective✦, and the host enumerations satisfy the sampling order conditions (17).✦
Theorem 2. Let , and sample uniformly from . For each fixed cell , the cellwise guard bound is (20). (20)✦
The propagation statements concern any nonnegative height , any binary matrix and paths with the boundary conditions in (21). (21)
Theorem 3. Assume the boundary conditions (21). If no mode body occurs at any edge , the propagation statement is (22). (22)✦ Under the boundary conditions (21), suppose the two row paths share their last position, , and the two column paths share theirs, . The mode body conclusion is (23). (23)✦