OctoInformBeta

OpenAI preprint, September 2026 · §3. Distance under arbitrary binary changes

Proposition 3.1: For height h≥1h\ge1 and m=2hm=2^h, every repair avoiding the fixed pattern HH changes at least m2m^2 entries

The ordered host resists binary repair.

Hover over a blue or green term in the text, or a node in the graph, to find it in the other. Select it to read its declaration both in Lean and in words.

The Setting

The distance under consideration counts arbitrary binary changes, including changes from 00 to 11. For an integer q≥0q\ge0, write [q]={0,…,q−1}[q]=\{0,\ldots,q-1\}. A binary matrix of order nn is a function [n]×[n]→{0,1}[n]\times[n]\to\{0,1\}, with the natural orders on both index sets.✦

The anchor SS is the binary matrix of order s=64s=64 in (1). Here the binary digit η(a,b)\eta(a,b) is the indicator that ⌊a/2max⁡{5−b,0}⌋\lfloor a/2^{\max\{5-b,0\}}\rfloor is odd.✦ Suv={η(u−32,v−58),32≤u≤63,59≤v≤63,𝟏u≠v,otherwise.S_{uv}=\begin{cases} \eta(u-32,v-58),&32\le u\le63,\quad59\le v\le63,\\ \mathbf1_{u\ne v},&\text{otherwise}. \end{cases}(1)✦ The forbidden matrix HH has order k=66k=66 and is defined by (2). Its first body index is 6464, corresponding to paper index 6565. H=(SEE𝖳P),Euj=𝟏u=j(u∈[s],j∈[2]),P=(1011).H=\begin{pmatrix}S&E\\E^{\mathsf T}&P\end{pmatrix}, \qquad E_{uj}=\mathbf1_{u=j}\quad(u\in[s],\ j\in[2]), \qquad P=\begin{pmatrix}1&0\\1&1\end{pmatrix}.(2)✦

An increasing index map f:[k]→[n]f:[k]\to[n] is a strictly increasing function.✦ An ordered copy of HH in a binary matrix BB is a pair (f,g)(f,g) of independently chosen increasing row and column maps such that Bf(a),g(b)=HabB_{f(a),g(b)}=H_{ab} for every a,b∈[k]a,b\in[k], including entries of HH equal to zero.✦ The ordered copy count NH(B)N_H(B) of a binary matrix BB is the number of ordered copies of HH in BB, and BB is HH-free when NH(B)=0N_H(B)=0.✦

For binary matrices AA and BB of the same order, the Hamming distance dHam(A,B)d_{\mathrm{Ham}}(A,B) is the number of cells where AA and BB differ.✦ For a binary matrix AA of order n>0n>0, the minimum repair size eH(A)e_H(A) is the smallest number of entries that must change to obtain an HH-free binary matrix, and the normalized removal distance dist⁡H(A)\operatorname{dist}_H(A) is this number divided by n2n^2, as in (3). dHam(A,B)=|{(r,c)∈[n]2:Arc≠Brc}|,eH(A)=minB:[n]2→{0,1}NH(B)=0dHam(A,B),dist⁡H(A)=eH(A)n2.\begin{aligned} d_{\mathrm{Ham}}(A,B)&=|\{(r,c)\in[n]^2:A_{rc}\ne B_{rc}\}|,\\ e_H(A)&=\min_{\substack{B:[n]^2\to\{0,1\}\\N_H(B)=0}} d_{\mathrm{Ham}}(A,B),\\ \operatorname{dist}_H(A)&=\frac{e_H(A)}{n^2}. \end{aligned}(3)

The Ordered Host

Fix h≥1h\ge1 and the parameters in (4). m=2h,dh=386h+2,nh=dhm,ϵh=dh−2.m=2^h,\qquad d_h=386h+2,\qquad n_h=d_hm,\qquad \epsilon_h=d_h^{-2}.(4) A variable position is a pair x=(c,a)∈Vh=[2h+1]×[m]x=(c,a)\in V_h=[2h+1]\times[m].✦ For a variable position x=(c,a)∈Vhx=(c,a)\in V_h, the depth δ(x)\delta(x) is the integer ⌊c/2⌋\lfloor c/2\rfloor, the sign σ(x)\sigma(x) is ++ for even cc and −- for odd cc, and the node index p(x)p(x) is the integer ⌊a/2h−δ(x)⌋\lfloor a/2^{h-\delta(x)}\rfloor. For 0≤i≤h0\le i\le h, the signed level class Li±L_i^\pm consists of the positions of depth ii whose sign is ±\pm when i<hi<h.✦ Both signs use the same leaf class Lh+=Lh−L_h^+=L_h^-. Write bi=2h−ib_i=2^{h-i}✦ and Li,β±={x∈Li±:p(x)≡β(mod⁡2)}L_{i,\beta}^\pm=\{x\in L_i^\pm:p(x)\equiv\beta\pmod2\} for β∈{0,1}\beta\in\{0,1\}.

A constraint mode is an integer t∈[6h]t\in[6h].✦ For a constraint mode t∈[6h]t\in[6h], the level ii is ⌊t/6⌋+1\lfloor t/6\rfloor+1 and the type qq is tmod⁡6t\bmod6. An anchor position is a triple (t,u,a)∈[6h]×[s]×[m](t,u,a)\in[6h]\times[s]\times[m].✦ The host position set is the disjoint union Xh=([6h]×[s]×[m])⊔Vh⊔DhX_h=([6h]\times[s]\times[m])\sqcup V_h\sqcup D_h, where DhD_h is a separate copy of [m][m] of dummy positions.✦

The row roles Rt0,Rt1R_t^0,R_t^1 and column roles Ct0,Ct1C_t^0,C_t^1 are subsets of Vh⊔DhV_h\sqcup D_h given by (5); no anchor position has a role. For 2≤j<s2\le j<s, set Rtj=Ctj=⌀R_t^j=C_t^j=\varnothing. The first two types are vertical modes, and the other types are horizontal modes. qRt0Rt1Ct0Ct10Li+Li−1+DhLi−1+1Li−1−Li−DhLi−1−2+βLi,β+DhLi−1+Li,β+4+βLi,β−DhLi,β−Li−1−(β∈{0,1}).\begin{array}{c|cccc} q&R_t^0&R_t^1&C_t^0&C_t^1\\ \hline 0&L_i^+&L_{i-1}^+&D_h&L_{i-1}^+\\ 1&L_{i-1}^-&L_i^-&D_h&L_{i-1}^-\\ 2+\beta&L_{i,\beta}^+&D_h&L_{i-1}^+&L_{i,\beta}^+\\ 4+\beta&L_{i,\beta}^-&D_h&L_{i,\beta}^-&L_{i-1}^- \end{array} \qquad(\beta\in\{0,1\}).(5)

The variable matrix vh:Vh×Vh→{0,1}v_h:V_h\times V_h\to\{0,1\} is defined in (6). In that display, δr=δ(r)\delta_r=\delta(r), pr=p(r)p_r=p(r) and σr=σ(r)\sigma_r=\sigma(r), with corresponding notation for cc. vh(r,c)={𝟏pr≤pc,δr=δc=h,𝟏pr≤pc,δr=δc<h,σr=σc=+,𝟏pr<pc,δr=δc<h,σr=σc=−,𝟏⌊pr/2⌋≤pc,δr=δc+1,δc<h,σc=+,δr=horσr=σc,𝟏⌊pr/2⌋<pc,δr=δc+1,δc<h,σc=−,δr=horσr=σc,0,otherwise.v_h(r,c)=\begin{cases} \mathbf1_{p_r\le p_c},&\delta_r=\delta_c=h,\\ \mathbf1_{p_r\le p_c},&\delta_r=\delta_c<h,\quad\sigma_r=\sigma_c=+,\\ \mathbf1_{p_r<p_c},&\delta_r=\delta_c<h,\quad\sigma_r=\sigma_c=-,\\ \mathbf1_{\lfloor p_r/2\rfloor\le p_c},& \substack{\delta_r=\delta_c+1,\ \delta_c<h,\ \sigma_c=+,\\ \delta_r=h\ \text{or}\ \sigma_r=\sigma_c},\\ \mathbf1_{\lfloor p_r/2\rfloor<p_c},& \substack{\delta_r=\delta_c+1,\ \delta_c<h,\ \sigma_c=-,\\ \delta_r=h\ \text{or}\ \sigma_r=\sigma_c},\\ 0,&\text{otherwise}. \end{cases}(6)✦ The raw host Gh:Xh×Xh→{0,1}G_h:X_h\times X_h\to\{0,1\} is the matrix in (7). Gh((t,u,a),(t′,v,b))=𝟏t=t′Suv,Gh((t,u,a),c)=𝟏c∈Ctu(c∈Vh⊔Dh),Gh(r,(t,v,b))=𝟏r∈Rtv(r∈Vh⊔Dh),Gh(r,c)=vh(r,c)(r,c∈Vh),Gh(r,c)=1(r,c∈Vh⊔Dh,{r,c}∩Dh≠⌀).\begin{aligned} G_h((t,u,a),(t',v,b))&=\mathbf1_{t=t'}S_{uv},\\ G_h((t,u,a),c)&=\mathbf1_{c\in C_t^u} &&(c\in V_h\sqcup D_h),\\ G_h(r,(t,v,b))&=\mathbf1_{r\in R_t^v} &&(r\in V_h\sqcup D_h),\\ G_h(r,c)&=v_h(r,c)&&(r,c\in V_h),\\ G_h(r,c)&=1&&(r,c\in V_h\sqcup D_h,\ \{r,c\}\cap D_h\ne\varnothing). \end{aligned}(7)✦

Variable rows and columns have separate traversal orders. For x=(c,a)x=(c,a) of depth i<hi<h, put j=p(x)j=p(x) and b=bib=b_i. The subtree entry key E(x)E(x), subtree exit key T(x)T(x) and leaf key U(a)U(a) are the ordered five-tuples in (8). E(x)=(2jb,1,i,c,a),T(x)=(2(j+1)b,0,h−i,c,a),U(a)=(2a+1,2,0,2h,a).E(x)=(2jb,1,i,c,a),\qquad T(x)=(2(j+1)b,0,h-i,c,a),\qquad U(a)=(2a+1,2,0,2h,a).(8) The variable row order and variable column order compare the keys KrK_r and KcK_c of (9) lexicographically.✦ xKr(x)Kc(x)c=2hU(a)U(a)c<2h,c oddE(x)T(x)c<2h,c evenT(x)E(x)\begin{array}{c|cc} x&K_r(x)&K_c(x)\\ \hline c=2h&U(a)&U(a)\\ c<2h,\ c\text{ odd}&E(x)&T(x)\\ c<2h,\ c\text{ even}&T(x)&E(x) \end{array}(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 (t,u,a)(t,u,a), and dummies by their coordinate. Let ρh:Xh→[nh]\rho_h:X_h\to[n_h] and κh:Xh→[nh]\kappa_h:X_h\to[n_h] be the respective row and column enumerations.

For bijections ρ,κ:Xh→[n]\rho,\kappa:X_h\to[n], the reindexed host Aρ,κA_{\rho,\kappa} is the binary matrix of order nn obtained from GhG_h by (10). The ordered host uses the separate enumerations just specified. Aρ,κ(r,c)=Gh(ρ−1(r),κ−1(c)),Ah=Aρh,κh.A_{\rho,\kappa}(r,c)=G_h(\rho^{-1}(r),\kappa^{-1}(c)), \qquad A_h=A_{\rho_h,\kappa_h}.(10)✦

Guarded Paths

For a binary matrix B:R×C→{0,1}B:R\times C\to\{0,1\}, a body at rows r0,r1r_0,r_1 and columns c0,c1c_0,c_1 is a selected array equal to PP in that displayed order.✦ Given paths xi+,xi−∈Rx_i^+,x_i^-\in R and yi+,yi−∈Cy_i^+,y_i^-\in C, and dummy positions xd∈Rx_d\in R, yd∈Cy_d\in C, the four ordered edge rectangles Qi,jQ_{i,j} are defined in (11). A mode body ℳi(B)\mathcal M_i(B) in a binary matrix BB is a body on at least one of the four ordered edge rectangles Qi,1,…,Qi,4Q_{i,1},\ldots,Q_{i,4}.✦ Qi,1=(xi+1+,xi+;yd,yi+),Qi,2=(xi−,xi+1−;yd,yi−),Qi,3=(xi+1+,xd;yi+,yi+1+),Qi,4=(xi+1−,xd;yi+1−,yi−).\begin{aligned} Q_{i,1}&=(x_{i+1}^+,x_i^+;y_d,y_i^+),& Q_{i,2}&=(x_i^-,x_{i+1}^-;y_d,y_i^-),\\ Q_{i,3}&=(x_{i+1}^+,x_d;y_i^+,y_{i+1}^+),& Q_{i,4}&=(x_{i+1}^-,x_d;y_{i+1}^-,y_i^-). \end{aligned}(11)

An anchor frame F=(f,g)F=(f,g) in a matrix of order nn consists of increasing maps f,g:[s]→[n]f,g:[s]\to[n].✦ For an ordered rectangle QQ, let R(Q)R(Q) and C(Q)C(Q) be its sets of two selected row and column positions. The anchor and signature cell set 𝒞(F,Q)\mathcal C(F,Q) is defined in (12). 𝒞(F,Q)=(im⁡f×im⁡g)∪(R(Q)×im⁡g)∪(im⁡f×C(Q)).\mathcal C(F,Q)= (\operatorname{im}f\times\operatorname{im}g) \cup(R(Q)\times\operatorname{im}g) \cup(\operatorname{im}f\times C(Q)).(12)✦ A guarded path selection 𝒮\mathcal S in [n][n] is a choice of row paths xi+,xi−x_i^+,x_i^-, column paths yi+,yi−y_i^+,y_i^- and dummy positions xd,ydx_d,y_d, all in [n][n], together with four anchor frames Fi,1,…,Fi,4F_{i,1},\ldots,F_{i,4} for every i≥0i\ge0. For a guarded path selection 𝒮\mathcal S in [n][n], the core cells Ch(𝒮)C_h(\mathcal S), edge guard cells Ei(𝒮)E_i(\mathcal S) and finite guard set Γh(𝒮)\Gamma_h(\mathcal S) are the cell sets defined in (13). Ch(𝒮)={(x0+,y0+),(x0−,y0−)}∪⋃i=0h{(xi+,yd),(xi−,yd),(xd,yi+),(xd,yi−)},Ei(𝒮)=⋃j=14𝒞(Fi,j,Qi,j),Γh(𝒮)=Ch(𝒮)∪⋃i=0h−1Ei(𝒮).\begin{aligned} C_h(\mathcal S)&=\{(x_0^+,y_0^+),(x_0^-,y_0^-)\}\\ &\quad\cup\bigcup_{i=0}^h \{(x_i^+,y_d),(x_i^-,y_d),(x_d,y_i^+),(x_d,y_i^-)\},\\ E_i(\mathcal S)&=\bigcup_{j=1}^4\mathcal C(F_{i,j},Q_{i,j}),\\ \Gamma_h(\mathcal S)&=C_h(\mathcal S)\cup\bigcup_{i=0}^{h-1}E_i(\mathcal S). \end{aligned}(13)

A selected anchor frame of mode tt has rows ρh(t,j,aj)\rho_h(t,j,a_j) and columns κh(t,j,bj)\kappa_h(t,j,b_j) for j∈[s]j\in[s], with both selections increasing.✦ For u,v∈[m]u,v\in[m], the common seed frame Ft(u,v)F_t(u,v) of mode tt is the selected anchor frame with aj=ua_j=u and bj=vb_j=v for all jj.✦

The sampled selection uses three independent uniform seeds (z,u,v)∈[m]3(z,u,v)\in[m]^3. For 0≤i≤h0\le i\le h, its node and offset mixing and signed sampled variable positions are given by (14). The sampled coordinate belongs to [m][m]. μb(z,u)=b⌊z/b⌋+(umod⁡b),ci+=2i,ci−={2i+1,i<h,2h,i=h,si±(z,u)=(ci±,μbi(z,u))∈Vh.\begin{aligned} \mu_b(z,u)&=b\lfloor z/b\rfloor+(u\bmod b),\\ c_i^+&=2i,\qquad c_i^-=\begin{cases}2i+1,&i<h,\\2h,&i=h,\end{cases}\\ s_i^\pm(z,u)&=(c_i^\pm,\mu_{b_i}(z,u))\in V_h. \end{aligned}(14) Writing D(a)D(a) for dummy position aa, the sampled paths and dummies are given by (15) for 0≤i≤h0\le i\le h. For i>hi>h, the paths retain their value at hh. xi±=ρh(si±(z,u)),yi±=κh(si±(z,v)),xd=ρh(D(u)),yd=κh(D(v)).x_i^\pm=\rho_h(s_i^\pm(z,u)),\qquad y_i^\pm=\kappa_h(s_i^\pm(z,v)),\qquad x_d=\rho_h(D(u)),\qquad y_d=\kappa_h(D(v)).(15) For i≥0i\ge0, set e=imod⁡he=i\bmod h and β=⌊z/be+1⌋mod⁡2\beta=\lfloor z/b_{e+1}\rfloor\bmod2. 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 β\beta. Fi,1=F6e(u,v),Fi,2=F6e+1(u,v),Fi,3=F6e+2+β(u,v),Fi,4=F6e+4+β(u,v).F_{i,1}=F_{6e}(u,v),\quad F_{i,2}=F_{6e+1}(u,v),\quad F_{i,3}=F_{6e+2+\beta}(u,v),\quad F_{i,4}=F_{6e+4+\beta}(u,v).(16) Denote this selection by 𝒮h(z,u,v)\mathcal S_h(z,u,v).

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 i<hi<h. xi+1+<xi+,xi−<xi+1−,yi+<yi+1+,yi+1−<yi−.x_{i+1}^+<x_i^+,\qquad x_i^-<x_{i+1}^-,\qquad y_i^+<y_{i+1}^+,\qquad y_{i+1}^-<y_i^-.(17)

The Claim

Theorem 1. Let h≥1h\ge1, and let AhA_h be the ordered host in (10). For every HH-free binary matrix BB of order nhn_h, the repair bound is (18). m2≤dHam(Ah,B).m^2\le d_{\mathrm{Ham}}(A_h,B).(18)✦ More generally, let d,md,m be positive integers and let AA be a binary matrix of order dmdm. Suppose every HH-free binary matrix of that order differs from AA in at least m2m^2 entries. The normalized bound is (19). 1d2≤dist⁡H(A).\frac1{d^2}\le\operatorname{dist}_H(A).(19)✦

In the paper, the result reads: for h≥1h\ge1, m=2hm=2^h, dh=386h+2d_h=386h+2 and nh=dhmn_h=d_hm, every HH-free binary matrix of order nhn_h differs from AhA_h in at least m2m^2 entries, and consequently AhA_h is ϵh\epsilon_h-far from being HH-free, with ϵh=dh−2\epsilon_h=d_h^{-2}.

What Is Checked

The repair statement is over the separately enumerated host AhA_h and arbitrary binary HH-free matrices on the same ordered indices. The host position set has cardinality nhn_h.✦ Both traversal keys in (9) are injective✦, and the host enumerations satisfy the sampling order conditions (17).✦

Theorem 2. Let h≥1h\ge1, and sample 𝒮h(z,u,v)\mathcal S_h(z,u,v) uniformly from [m]3[m]^3. For each fixed cell (r,c)∈[nh]2(r,c)\in[n_h]^2, the cellwise guard bound is (20). ℙ(z,u,v)∈[m]3((r,c)∈Γh(𝒮h(z,u,v)))≤1m2.\mathbb P_{(z,u,v)\in[m]^3} \bigl((r,c)\in\Gamma_h(\mathcal S_h(z,u,v))\bigr)\le\frac1{m^2}.(20)✦

The propagation statements concern any nonnegative height hh, any binary matrix B:R×C→{0,1}B:R\times C\to\{0,1\} and paths with the boundary conditions in (21). B(x0+,y0+)=1,B(x0−,y0−)=0,B(xi+,yd)=B(xi−,yd)=1(0≤i≤h),B(xd,yi+)=B(xd,yi−)=1(0≤i≤h).\begin{aligned} B(x_0^+,y_0^+)&=1,&B(x_0^-,y_0^-)&=0,\\ B(x_i^+,y_d)&=B(x_i^-,y_d)=1 &&(0\le i\le h),\\ B(x_d,y_i^+)&=B(x_d,y_i^-)=1 &&(0\le i\le h). \end{aligned}(21)

Theorem 3. Assume the boundary conditions (21). If no mode body occurs at any edge i<hi<h, the propagation statement is (22). B(xi+,yi+)=1,B(xi−,yi−)=0(0≤i≤h).B(x_i^+,y_i^+)=1,\qquad B(x_i^-,y_i^-)=0 \qquad(0\le i\le h).(22)✦ Under the boundary conditions (21), suppose the two row paths share their last position, xh+=xh−x_h^+=x_h^-, and the two column paths share theirs, yh+=yh−y_h^+=y_h^-. The mode body conclusion is (23). There exists i<h such that ℳi(B).\text{There exists }i<h\text{ such that }\mathcal M_i(B).(23)✦