OctoInformBeta

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

Lemma 4.4: A common mode and one position from each group under the separate host orders

Anchor copies have prescribed representatives.

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 occurrence of a binary anchor matches its zeros as well as its ones, with independently increasing row and column selections. In the host considered here, those selections may range over anchor positions, tree variables and dummy positions.

Write [q]={0,…,q−1}[q]=\{0,\ldots,q-1\}. The anchor SS is the binary matrix on [64]2[64]^2 defined in (2); its binary digit function η\eta is given by (1) for nonnegative integers a,ba,b. η(a,b)=𝟏{⌊a2max⁡{5−b,0}⌋≡1(mod⁡2)}.\eta(a,b)=\mathbf{1}\!\left\{ \left\lfloor\frac{a}{2^{\max\{5-b,0\}}}\right\rfloor\equiv1\pmod2 \right\}.(1)✦ 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,\\ \mathbf{1}\{u\ne v\},&\text{otherwise}. \end{cases}(2)✦

Fix a nonnegative height hh. Put m=2hm=2^h, dh=386h+2d_h=386h+2 and nh=dhmn_h=d_hm.✦ The mode set MhM_h, variable set VhV_h and host position set XhX_h are the finite sets in (3), where DhD_h is a disjoint copy of [m][m]. An anchor position (t,u,x)(t,u,x) has mode tt, group uu and offset xx. Mh=[6h],Vh=[2h+1]×[m],Dh=[m],Xh=(Mh×[64]×[m])⊔(Vh⊔Dh).\begin{gathered} M_h=[6h],\qquad V_h=[2h+1]\times[m],\qquad D_h=[m],\\ X_h=(M_h\times[64]\times[m])\sqcup(V_h\sqcup D_h). \end{gathered}(3)

For a variable v=(c,x)∈Vhv=(c,x)\in V_h, its depth d(v)d(v), positive sign σ(v)\sigma(v) and tree node index ν(v)\nu(v) are defined by (4). For a depth ii and a sign ss, the signed level class VisV_i^s is the subset of VhV_h specified in (5); the signs have distinct internal classes and share the leaf class. d(v)=⌊c/2⌋,σ(v)=𝟏{c≡0(mod⁡2)},ν(v)=⌊x2h−d(v)⌋.d(v)=\lfloor c/2\rfloor,\qquad \sigma(v)=\mathbf{1}\{c\equiv0\pmod2\},\qquad \nu(v)=\left\lfloor\frac{x}{2^{h-d(v)}}\right\rfloor.(4) Vis={v∈Vh:d(v)=i,i=h or σ(v)=s},s∈{0,1}.V_i^s=\{v\in V_h:d(v)=i,\quad i=h\text{ or }\sigma(v)=s\}, \qquad s\in\{0,1\}.(5)✦

A mode t∈Mht\in M_h has type q(t)=tmod⁡6q(t)=t\bmod6 and level L(t)=⌊t/6⌋+1L(t)=\lfloor t/6\rfloor+1. The row roles Rt0,Rt1R_t^0,R_t^1 and column roles Ct0,Ct1C_t^0,C_t^1 of a mode t∈Mht\in M_h are the subsets of Vh⊔DhV_h\sqcup D_h given in (6). Here q=q(t)q=q(t), L=L(t)L=L(t) and e=qmod⁡2e=q\bmod2. The parity subclass Vis,e={v∈Vis:ν(v)≡e(mod⁡2)}V_i^{s,e}=\{v\in V_i^s:\nu(v)\equiv e\pmod2\} is the subset of the signed level class VisV_i^s whose variables have node index of parity ee. qRt0Rt1Ct0Ct10VL1VL−11DhVL−111VL−10VL0DhVL−102,3VL1,eDhVL−11VL1,e4,5VL0,eDhVL0,eVL−10\begin{array}{c|cc|cc} q&R_t^0&R_t^1&C_t^0&C_t^1\\ \hline 0&V_L^1&V_{L-1}^1&D_h&V_{L-1}^1\\ 1&V_{L-1}^0&V_L^0&D_h&V_{L-1}^0\\ 2,3&V_L^{1,e}&D_h&V_{L-1}^1&V_L^{1,e}\\ 4,5&V_L^{0,e}&D_h&V_L^{0,e}&V_{L-1}^0 \end{array}(6)

Write a≼1ba\preceq_1 b for a≤ba\le b and a≼0ba\preceq_0 b for a<ba<b. The variable matrix WhW_h is the binary matrix on Vh2V_h^2 defined by (7). Wh(v,w)={𝟏{ν(v)≼σ(w)ν(w)},d(v)=d(w),d(v)=h or σ(v)=σ(w),𝟏{⌊ν(v)/2⌋≼σ(w)ν(w)},d(v)=d(w)+1,d(w)<h,d(v)=h or σ(v)=σ(w),0,otherwise.W_h(v,w)=\begin{cases} \mathbf{1}\{\nu(v)\preceq_{\sigma(w)}\nu(w)\}, &\begin{array}{l}d(v)=d(w),\\d(v)=h\text{ or }\sigma(v)=\sigma(w),\end{array}\\[2pt] \mathbf{1}\{\lfloor\nu(v)/2\rfloor\preceq_{\sigma(w)}\nu(w)\}, &\begin{array}{l}d(v)=d(w)+1,\quad d(w)<h,\\ d(v)=h\text{ or }\sigma(v)=\sigma(w),\end{array}\\[2pt] 0,&\text{otherwise}. \end{cases}(7)✦

The raw host BhB_h is the binary matrix on Xh2X_h^2 specified by (8), with Nh=Vh⊔DhN_h=V_h\sqcup D_h. Bh((t,u,x),(t′,v,y))=𝟏{t=t′}Suv,Bh((t,u,x),z)=∑j=01𝟏{u=j}𝟏{z∈Ctj}(z∈Nh),Bh(z,(t,v,y))=∑j=01𝟏{v=j}𝟏{z∈Rtj}(z∈Nh),Bh(v,w)=Wh(v,w)(v,w∈Vh),Bh(z,z′)=1(z,z′∈Nh,{z,z′}∩Dh≠⌀).\begin{aligned} B_h((t,u,x),(t',v,y))&=\mathbf{1}\{t=t'\}S_{uv},\\ B_h((t,u,x),z)&=\sum_{j=0}^1\mathbf{1}\{u=j\}\mathbf{1}\{z\in C_t^j\} &&(z\in N_h),\\ B_h(z,(t,v,y))&=\sum_{j=0}^1\mathbf{1}\{v=j\}\mathbf{1}\{z\in R_t^j\} &&(z\in N_h),\\ B_h(v,w)&=W_h(v,w)&&(v,w\in V_h),\\ B_h(z,z')&=1&&(z,z'\in N_h,\ \{z,z'\}\cap D_h\ne\varnothing). \end{aligned}(8)✦

The Two Orders

An anchor frame XX on ordered mode, variable and offset sets M,V,OM,V,O is the disjoint union (M×[64]×O)⊔(V⊔O)(M\times[64]\times O)\sqcup(V\sqcup O).✦ Its anchor coordinates are ordered lexicographically by mode, group and offset.✦ The row coordinate map places these triples first, followed by the variable coordinates and then dummy offsets✦; the column coordinate map places the dummy offsets before the variable coordinates.✦ The frame’s row and column orders compare the respective coordinates.

The variable row and column orders use tree traversal coordinates in ℕ5\mathbb{N}^5 with lexicographic order. For depth dd, remaining height rr, block width bb, node jj, class cc and offset xx, the entry and exit keys EE and TT, and the leaf key FhF_h, are the tuples in (9). E(d,b,j,c,x)=(2jb,1,d,c,x),T(r,b,j,c,x)=(2(j+1)b,0,r,c,x),Fh(x)=(2x+1,2,0,2h,x).\begin{aligned} E(d,b,j,c,x)&=(2jb,1,d,c,x),\\ T(r,b,j,c,x)&=(2(j+1)b,0,r,c,x),\\ F_h(x)&=(2x+1,2,0,2h,x). \end{aligned}(9)

The traversal key Ka(v)K_a(v) of a variable vv for axis selector a∈{0,1}a\in\{0,1\} is the tuple defined by (10), where v=(c,x)v=(c,x), d=d(v)d=d(v), b=2h−db=2^{h-d} and j=ν(v)j=\nu(v). The variable position order compares these keys, with a=0a=0 for rows and a=1a=1 for columns.✦ Ka(v)={Fh(x),c=2h,E(d,b,j,c,x),c<2h,cmod⁡2=1−a,T(h−d,b,j,c,x),otherwise.K_a(v)=\begin{cases} F_h(x),&c=2h,\\ E(d,b,j,c,x),&c<2h,\quad c\bmod2=1-a,\\ T(h-d,b,j,c,x),&\text{otherwise}. \end{cases}(10)✦

The host row order is the frame row order using the variable row order✦; the host column order uses the variable column order.✦

The row enumeration er:Xh→[nh]e_r:X_h\to[n_h] and column enumeration ec:Xh→[nh]e_c:X_h\to[n_h] are the increasing bijections for their respective host orders. Write AhA_h for the host matrix with these row and column enumerations. An ordered copy of SS consists of maps r,c:[64]→Xhr,c:[64]\to X_h such that er∘re_r\circ r and ec∘ce_c\circ c are strictly increasing and Bh(ri,cj)=SijB_h(r_i,c_j)=S_{ij} for every i,j∈[64]i,j\in[64].

An anchor copy is pinned if its selected positions are (t,i,ai)(t,i,a_i) on rows and (t,j,bj)(t,j,b_j) on columns for one mode tt and offsets ai,bj∈[m]a_i,b_j\in[m]. For a nonnegative integer nn and bijections α,β:Xh→[n]\alpha,\beta:X_h\to[n], write Pin⁡h(α,β)\operatorname{Pin}_h(\alpha,\beta) when every copy of SS whose row selections increase under α\alpha and whose column selections increase under β\beta is pinned.✦

The Claim

Theorem 1. Let h≥0h\ge0, and let r,c:[64]→Xhr,c:[64]\to X_h select an ordered copy of SS in AhA_h. There are a mode t∈Mht\in M_h and functions a,b:[64]→[m]a,b:[64]\to[m] satisfying (11): ri=(t,i,ai)(i∈[64]),cj=(t,j,bj)(j∈[64]).r_i=(t,i,a_i)\quad(i\in[64]),\qquad c_j=(t,j,b_j)\quad(j\in[64]).(11)✦ Pin⁡h(er,ec).\operatorname{Pin}_h(e_r,e_c).(12)✦

In the paper, the result reads: every ordered copy of SS in AhA_h uses the row and column anchor groups of a single mode tt, with exactly one position from each of its 6464 groups on each axis, in their prescribed order.

What Is Checked

The assertions (11) and (12) are stated for the raw host BhB_h on XhX_h, with its separately ordered and enumerated rows and columns and entrywise copies of the anchor SS.

The host position count is (13), and the traversal keys distinguish variable positions on each axis as in (14). |Xh|=(386h+2)2h=nh.|X_h|=(386h+2)2^h=n_h.(13)✦ Ka(v)=Ka(w)⇒v=w(a∈{0,1},v,w∈Vh).K_a(v)=K_a(w)\ \Longrightarrow\ v=w \qquad(a\in\{0,1\},\ v,w\in V_h).(14)✦