OctoInformBeta

OpenAI preprint, September 2026 · §4. Copies are confined to the leaf diagonal

Proposition 4.6: Ordered copies in the canonical host have a common row and column leaf at their first body entry

Body corners lie on the leaf diagonal.

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

An ordered induced copy chooses its rows and columns independently, preserving their orders and matching every entry, including zeros.✦ The distinguished cell here is the first entry of the two by two body attached to a fixed anchor.

Write [a]={0,…,a−1}[a]=\{0,\ldots,a-1\} for a nonnegative integer aa. A binary matrix AA of order nn is a function from [n]×[n][n]\times[n] to {0,1}\{0,1\}.✦ The anchor SS is the binary matrix of order s=64s=64 defined in (1), where 𝟏E\mathbf1_E denotes the indicator of a condition EE and η(a,b)\eta(a,b) is the binary digit specified there. η(a,b)=𝟏⌊a/2max⁡{5−b,0}⌋ is odd,S(u,v)={η(u−32,v−58),32≤u≤63,59≤v≤63,𝟏u≠v,otherwise.\begin{aligned} \eta(a,b)&=\mathbf1_{\lfloor a/2^{\max\{5-b,0\}}\rfloor\text{ is odd}},\\ S(u,v)&= \begin{cases} \eta(u-32,v-58),&32\le u\le63,\quad59\le v\le63,\\ \mathbf1_{u\ne v},&\text{otherwise}. \end{cases} \end{aligned}(1)

The fixed pattern HH is the binary matrix of order k=66k=66 with anchor SS, body PP, and the two attachment blocks given in (2); the matrix EE has row set [64][64] and column set [2][2]. H=(SEE𝖳P),E(u,j)=𝟏u=j,P=(1011).H=\begin{pmatrix}S&E\\E^{\mathsf T}&P\end{pmatrix}, \qquad E(u,j)=\mathbf1_{u=j}, \qquad P=\begin{pmatrix}1&0\\1&1\end{pmatrix}.(2)✦ Its first body index is 6464, corresponding to index 6565 in the paper.

An increasing index map f:[k]→[n]f:[k]\longrightarrow[n] is a strictly increasing function.✦ For a binary matrix AA of order nn, an ordered copy (f,g)(f,g) of HH in AA is a pair of strictly increasing maps from [k][k] to [n][n] satisfying the condition in (3); NH(A)N_H(A) is the number of these copies. 𝒞H(A)={(f,g):f,g:[66]→[n] strictly increasing,A(f(i),g(j))=H(i,j) for all i,j},NH(A)=|𝒞H(A)|.\mathcal C_H(A)= \{(f,g):f,g:[66]\longrightarrow[n]\text{ strictly increasing},\ A(f(i),g(j))=H(i,j)\text{ for all }i,j\}, \qquad N_H(A)=|\mathcal C_H(A)|.(3)

The Host and Its Orders

For ordered sets M,V,OM,V,O, a frame position xx is an element of the disjoint union of M×[64]×OM\times[64]\times O, VV and OO, called an anchor triple, a variable or a dummy, respectively.✦ Anchor triples have lexicographic order, first by mode, then group, then offset.✦ The row frame order places variables after anchors and dummies last✦; the column frame order places dummies after anchors and variables last.✦ The row coordinate map sends each frame position to the corresponding element of the ordered disjoint union of anchors, variables and dummies, and the column coordinate map sends each frame position to the corresponding element of the ordered disjoint union of anchors, dummies and variables; the frame orders are inherited from these maps.

For height h≥0h\ge0, put m=2hm=2^h, dh=386h+2d_h=386h+2 and nh=dhmn_h=d_hm.✦ The modes are the indices t∈[6h]t\in[6h]✦, and the variable positions are pairs x=(c,q)x=(c,q) in Vh=[2h+1]×[m]V_h=[2h+1]\times[m]. The host position set XhX_h is the frame with these modes, these variables and dummy set Dh=[m]D_h=[m].✦ A mode’s type κ(t)\kappa(t) and level λ(t)\lambda(t), and a variable’s depth δ(x)\delta(x) and node ν(x)\nu(x), are defined by (4). κ(t)=tmod⁡6,λ(t)=⌊t/6⌋+1,δ(c,q)=⌊c/2⌋,ν(c,q)=⌊q2h−δ(c,q)⌋.\kappa(t)=t\bmod6,\qquad \lambda(t)=\lfloor t/6\rfloor+1, \qquad \delta(c,q)=\lfloor c/2\rfloor, \qquad \nu(c,q)=\left\lfloor\frac{q}{2^{h-\delta(c,q)}}\right\rfloor.(4) The sign σ(c,q)\sigma(c,q) is positive for even cc and negative for odd cc.✦ For a level ii, a sign σ∈{+,−}\sigma\in\{+,-\} and a parity e∈{0,1}e\in\{0,1\}, the signed level class ViσV_i^\sigma is the subset of VhV_h consisting of variables at depth ii with sign σ\sigma, with no sign restriction when i=hi=h, and Viσ,eV_i^{\sigma,e} is the subset of ViσV_i^\sigma consisting of variables with node parity ee, as specified in (5). Viσ={x∈Vh:δ(x)=i,i=h or σ(x)=σ},Viσ,e={x∈Viσ:ν(x)mod⁡2=e}.V_i^\sigma=\{x\in V_h:\delta(x)=i,\quad i=h\text{ or }\sigma(x)=\sigma\}, \qquad V_i^{\sigma,e}=\{x\in V_i^\sigma:\nu(x)\bmod2=e\}.(5) The shared leaf ℓh(z)\ell_h(z), for z∈[m]z\in[m], is the variable position (2h,z)(2h,z) viewed as a host position.✦

A tree order coordinate KK is a tuple of five natural numbers, compared lexicographically in the written order.✦ For axis a=0a=0 on rows and a=1a=1 on columns, the tree traversal key KaK_a is defined by (6), with x=(c,q)x=(c,q), d=δ(x)d=\delta(x), b=2h−db=2^{h-d} and j=ν(x)j=\nu(x). Its cases are the leaf, subtree entry and subtree exit keys, respectively. Ka(c,q)={(2q+1,2,0,2h,q),c=2h,(2jb,1,d,c,q),c<2h,cmod⁡2=1−a,(2(j+1)b,0,h−d,c,q),otherwise.K_a(c,q)= \begin{cases} (2q+1,2,0,2h,q),&c=2h,\\ (2jb,1,d,c,q),&c<2h,\quad c\bmod2=1-a,\\ (2(j+1)b,0,h-d,c,q),&\text{otherwise}. \end{cases}(6)✦ The variable position order on each axis is the order inherited from its traversal key.✦ Let er:Xh→[nh]e_r:X_h\longrightarrow[n_h] and ec:Xh→[nh]e_c:X_h\longrightarrow[n_h] be the increasing row and column enumerations, respectively, chosen separately.

The row roles ℛt,0,ℛt,1\mathcal R_{t,0},\mathcal R_{t,1} and column roles 𝒞t,0,𝒞t,1\mathcal C_{t,0},\mathcal C_{t,1} are the subsets of nonanchor positions in (7), where L=λ(t)L=\lambda(t) and e=κ(t)mod⁡2e=\kappa(t)\bmod2. κ(t)ℛt,0ℛt,1𝒞t,0𝒞t,10VL+VL−1+DhVL−1+1VL−1−VL−DhVL−1−2,3VL+,eDhVL−1+VL+,e4,5VL−,eDhVL−,eVL−1−\begin{array}{c|cccc} \kappa(t)&\mathcal R_{t,0}&\mathcal R_{t,1}&\mathcal C_{t,0}&\mathcal C_{t,1}\\ \hline 0&V_L^+&V_{L-1}^+&D_h&V_{L-1}^+\\ 1&V_{L-1}^-&V_L^-&D_h&V_{L-1}^-\\ 2,3&V_L^{+,e}&D_h&V_{L-1}^+&V_L^{+,e}\\ 4,5&V_L^{-,e}&D_h&V_L^{-,e}&V_{L-1}^- \end{array}(7)

Write u≼+vu\preccurlyeq_+v for u≤vu\le v and u≼−vu\preccurlyeq_-v for u<vu<v. For variable positions x,y∈Vhx,y\in V_h, the variable matrix entry Th(x,y)T_h(x,y) is the binary value in (8); here dx=δ(x)d_x=\delta(x) and dy=δ(y)d_y=\delta(y). Th(x,y)={𝟏ν(x)≼σ(y)ν(y),dx=dy,dx=h or σ(x)=σ(y),𝟏⌊ν(x)/2⌋≼σ(y)ν(y),dx=dy+1,dy<h,dx=h or σ(x)=σ(y),0,otherwise.T_h(x,y)= \begin{cases} \mathbf1_{\nu(x)\preccurlyeq_{\sigma(y)}\nu(y)}, &d_x=d_y,\quad d_x=h\text{ or }\sigma(x)=\sigma(y),\\ \mathbf1_{\lfloor\nu(x)/2\rfloor\preccurlyeq_{\sigma(y)}\nu(y)}, &d_x=d_y+1,\quad d_y<h,\quad d_x=h\text{ or }\sigma(x)=\sigma(y),\\ 0,&\text{otherwise}. \end{cases}(8)✦

The raw host matrix WhW_h is the binary function on Xh×XhX_h\times X_h given in (9). In its second and third cases xx and yy are nonanchor positions, and the role indicator is zero for group indices outside {0,1}\{0,1\}. Wh((t,u,q),(t′,v,q′))=𝟏t=t′S(u,v),Wh((t,u,q),y)=𝟏u<2,y∈𝒞t,u,Wh(x,(t,v,q))=𝟏v<2,x∈ℛt,v,Wh(x,y)=Th(x,y)(x,y∈Vh),Wh(x,y)=1(x,y nonanchor, at least one dummy).\begin{aligned} W_h((t,u,q),(t',v,q'))&=\mathbf1_{t=t'}S(u,v),\\ W_h((t,u,q),y)&=\mathbf1_{u<2,\ y\in\mathcal C_{t,u}},\\ W_h(x,(t,v,q))&=\mathbf1_{v<2,\ x\in\mathcal R_{t,v}},\\ W_h(x,y)&=T_h(x,y)\quad(x,y\in V_h),\\ W_h(x,y)&=1\quad(x,y\text{ nonanchor, at least one dummy}). \end{aligned}(9)✦ The enumerated host AhA_h is the binary matrix defined by (10). The sets Rh+(p)R_h^+(p) and Ch+(p)C_h^+(p) denote its singleton row and column leaf classes. Ah(i,j)=Wh(er−1(i),ec−1(j)),Rh+(p)={er(ℓh(p))},Ch+(p)={ec(ℓh(p))}(p∈[m]).A_h(i,j)=W_h(e_r^{-1}(i),e_c^{-1}(j)),\qquad R_h^+(p)=\{e_r(\ell_h(p))\},\qquad C_h^+(p)=\{e_c(\ell_h(p))\}\quad(p\in[m]).(10)✦

The Claim

Theorem 1. Let hh be a nonnegative integer. Let r,c:[66]→Xhr,c:[66]\longrightarrow X_h be strictly increasing in the row and column orders, respectively, and suppose that Wh(r(i),c(j))=H(i,j)W_h(r(i),c(j))=H(i,j) for every i,j∈[66]i,j\in[66]. Their first body positions satisfy (11). There exists z∈[m] such that r(64)=ℓh(z)andc(64)=ℓh(z).\text{There exists }z\in[m]\text{ such that } r(64)=\ell_h(z)\quad\text{and}\quad c(64)=\ell_h(z).(11)✦ For the enumerated host AhA_h, the copy count and its normalized density satisfy (12) and (13), respectively. NH(Ah)≤2hnh130.N_H(A_h)\le 2^h n_h^{130}.(12)✦ NH(Ah)nh132≤2−hdh2.\frac{N_H(A_h)}{n_h^{132}}\le\frac{2^{-h}}{d_h^2}.(13)✦ More generally, let AA be a binary matrix of order nn, and let L⊆[n]×[n]L\subseteq[n]\times[n] contain (f(64),g(64))(f(64),g(64)) for every (f,g)∈𝒞H(A)(f,g)\in\mathcal C_H(A). Then (14) holds. NH(A)≤|L|n130.N_H(A)\le |L|n^{130}.(14)✦

In the paper, the result reads: for every integer h≥1h\ge1, each ordered copy of HH in AhA_h maps the entry (s+1,s+1)(s+1,s+1) into Lh=⋃0≤p<mRh+(p)×Ch+(p)L_h=\bigcup_{0\le p<m}R_h^+(p)\times C_h^+(p), and |Lh|=m|L_h|=m, NH(Ah)≤mnh2k−2N_H(A_h)\le mn_h^{2k-2} and NH(Ah)/nh2k≤2−h/dh2N_H(A_h)/n_h^{2k}\le2^{-h}/d_h^2.

What Is Checked

The confinement statement and canonical bounds are stated over the raw host on XhX_h with its separate row and column orders and increasing enumerations; the bound (14) is stated over every binary matrix and every cell set satisfying its body entry condition. The host position count and the injectivity of either traversal key are the assertions in (15). |Xh|=nh,Ka(x)=Ka(y)⇒x=y(a∈{0,1},x,y∈Vh).|X_h|=n_h,\qquad K_a(x)=K_a(y)\ \Longrightarrow\ x=y \quad(a\in\{0,1\},\ x,y\in V_h).(15)