OctoInformBeta

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

Lemma 4.3: For any five selected nonanchor columns, allowing repetitions

Nonanchor traces omit a five-bit word.

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 host matrix has an anchor part and a nonanchor part in both its row and column index sets. The nonanchor part consists of signed tree levels and a dummy class. Fix a nonnegative integer hh, put m=2hm=2^h, and write [q]={0,…,q−1}[q]=\{0,\ldots,q-1\}. All position indices start at zero.

A constraint mode tt is an element of Mh=[6h]M_h=[6h].✦ Its mode type κ(t)\kappa(t) and mode level L(t)L(t) are given by (1); there are six types at each edge level. κ(t)=tmod⁡6,L(t)=⌊t6⌋+1.\kappa(t)=t\bmod 6, \qquad L(t)=\left\lfloor\frac{t}{6}\right\rfloor+1.(1)

A variable position x=(a,b)x=(a,b) is an element of Vh=[2h+1]×[m]V_h=[2h+1]\times[m], where aa is its class index and bb its offset.✦ Its tree depth d(x)d(x), positive sign σ(x)\sigma(x) and tree node index ν(x)\nu(x) are defined by (2). Here and below 𝟏E\mathbf1_E is 11 when the condition EE holds and 00 otherwise. d(x)=⌊a2⌋,σ(x)=𝟏a≡0(mod⁡2),ν(x)=⌊b2h−d(x)⌋.d(x)=\left\lfloor\frac{a}{2}\right\rfloor, \qquad \sigma(x)=\mathbf1_{a\equiv0\pmod2}, \qquad \nu(x)=\left\lfloor\frac{b}{2^{h-d(x)}}\right\rfloor.(2)

An anchor position (t,u,b)(t,u,b) in Bh=Mh×[64]×[m]B_h=M_h\times[64]\times[m] is a triple recording its mode tt, anchor group uu and offset bb.✦ The dummy class Dh=[m]D_h=[m] is a set of dummy positions disjoint from VhV_h. The nonanchor position set NhN_h and full host position set XhX_h are the disjoint unions in (3). Nh=Vh⊔Dh,Xh=Bh⊔Nh.N_h=V_h\sqcup D_h, \qquad X_h=B_h\sqcup N_h.(3)

The Host Entries

For a tree depth ii and ε,p∈{0,1}\varepsilon,p\in\{0,1\}, the signed level ViεV_i^\varepsilon is the set of variable positions of depth ii whose sign is ε\varepsilon, except that both signs include the whole leaf level.✦ The parity subclass Viε,pV_i^{\varepsilon,p} of the signed level ViεV_i^\varepsilon is the set of positions in that level whose tree node index has parity pp. These sets are defined in (4), for ε,p∈{0,1}\varepsilon,p\in\{0,1\}. Viε={x∈Vh:d(x)=i,i=horσ(x)=ε},Viε,p={x∈Viε:ν(x)≡p(mod⁡2)}.\begin{aligned} V_i^\varepsilon &=\{x\in V_h:d(x)=i,\ i=h\ \text{or}\ \sigma(x)=\varepsilon\},\\ V_i^{\varepsilon,p} &=\{x\in V_i^\varepsilon:\nu(x)\equiv p\pmod2\}. \end{aligned}(4)

For a mode tt, the row role Rj(t)R_j(t) and column role Cj(t)C_j(t) are subsets of XhX_h specifying the positions assigned to body index j∈{0,1}j\in\{0,1\}. They contain no anchor positions. With L=L(t)L=L(t), their definitions are the six rows of (5), indexed by κ(t)\kappa(t). κ(t)R0(t)R1(t)C0(t)C1(t)0VL1VL−11DhVL−111VL−10VL0DhVL−102VL1,0DhVL−11VL1,03VL1,1DhVL−11VL1,14VL0,0DhVL0,0VL−105VL0,1DhVL0,1VL−10\begin{array}{c|cccc} \kappa(t)&R_0(t)&R_1(t)&C_0(t)&C_1(t)\\ \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&V_L^{1,0}&D_h&V_{L-1}^1&V_L^{1,0}\\ 3&V_L^{1,1}&D_h&V_{L-1}^1&V_L^{1,1}\\ 4&V_L^{0,0}&D_h&V_L^{0,0}&V_{L-1}^0\\ 5&V_L^{0,1}&D_h&V_L^{0,1}&V_{L-1}^0 \end{array}(5)

For variable positions x,y∈Vhx,y\in V_h, the variable matrix entry Qh(x,y)Q_h(x,y) is the binary value in (6). For integer node indices a,ba,b, the two thresholds used there are T1(a,b)=𝟏a≤bT_1(a,b)=\mathbf1_{a\le b} and T0(a,b)=𝟏a<bT_0(a,b)=\mathbf1_{a<b}. Qh(x,y)={T1(ν(x),ν(y)),d(x)=d(y)=h,Tσ(x)(ν(x),ν(y)),d(x)=d(y)<h,σ(x)=σ(y),Tσ(y)(⌊ν(x)/2⌋,ν(y)),d(x)=d(y)+1,d(y)<h,d(x)=horσ(x)=σ(y),0,otherwise.Q_h(x,y)= \begin{cases} T_1(\nu(x),\nu(y)),&d(x)=d(y)=h,\\ T_{\sigma(x)}(\nu(x),\nu(y)), &d(x)=d(y)<h,\ \sigma(x)=\sigma(y),\\ T_{\sigma(y)}(\lfloor\nu(x)/2\rfloor,\nu(y)), &\begin{gathered} d(x)=d(y)+1,\ d(y)<h,\\ d(x)=h\ \text{or}\ \sigma(x)=\sigma(y), \end{gathered}\\ 0,&\text{otherwise}. \end{cases}(6)✦

The binary digit η(a,b)\eta(a,b), for nonnegative integers a,ba,b, and the 64×6464\times64 anchor matrix SS are defined by (7). The exceptional rectangle of SS has row indices 3232 through 6363 and column indices 5959 through 6363. η(a,b)=𝟏⌊a/2max⁡{5−b,0}⌋odd,Suv={η(u−32,v−58),u≥32,v≥59,𝟏u≠v,otherwise,u,v∈[64].\begin{aligned} \eta(a,b) &=\mathbf1_{\lfloor a/2^{\max\{5-b,0\}}\rfloor\ \mathrm{odd}},\\ S_{uv} &=\begin{cases} \eta(u-32,v-58),&u\ge32,\ v\ge59,\\ \mathbf1_{u\ne v},&\text{otherwise}, \end{cases} \qquad u,v\in[64]. \end{aligned}(7)

The raw host matrix Ah:Xh×Xh→{0,1}A_h:X_h\times X_h\to\{0,1\} is the binary matrix whose entries are specified in (8). In the first three lines the displayed triples are anchor positions; in the second and third lines c,r∈Nhc,r\in N_h, respectively. The last line applies when at least one of the two nonanchor positions is a dummy. Ah((t,u,b),(t′,v,b′))=𝟏t=t′Suv,Ah((t,u,b),c)=𝟏(u=0∧c∈C0(t))∨(u=1∧c∈C1(t)),Ah(r,(t,v,b))=𝟏(v=0∧r∈R0(t))∨(v=1∧r∈R1(t)),Ah(x,y)=Qh(x,y)(x,y∈Vh),Ah(r,c)=1(r,c∈Nh,r∈Dhorc∈Dh).\begin{aligned} A_h((t,u,b),(t',v,b'))&=\mathbf1_{t=t'}S_{uv},\\ A_h((t,u,b),c) &=\mathbf1_{(u=0\,\land\,c\in C_0(t))\,\lor\, (u=1\,\land\,c\in C_1(t))},\\ A_h(r,(t,v,b)) &=\mathbf1_{(v=0\,\land\,r\in R_0(t))\,\lor\, (v=1\,\land\,r\in R_1(t))},\\ A_h(x,y)&=Q_h(x,y)\qquad(x,y\in V_h),\\ A_h(r,c)&=1\qquad(r,c\in N_h,\ r\in D_h\ \text{or}\ c\in D_h). \end{aligned}(8)✦

For a column selection 𝒄=(ci)i∈[5]\mathbf c=(c_i)_{i\in[5]} in NhN_h, repetitions are allowed. The nonanchor word map W𝒄W_{\mathbf c} of a column selection 𝒄=(ci)i∈[5]\mathbf c=(c_i)_{i\in[5]} in NhN_h is the map from NhN_h to {0,1}[5]\{0,1\}^{[5]} that sends each nonanchor row to its five-bit trace in the raw host matrix AhA_h: W𝒄:Nh→{0,1}[5],W𝒄(r)=(Ah(r,ci))i∈[5].W_{\mathbf c}:N_h\longrightarrow\{0,1\}^{[5]}, \qquad W_{\mathbf c}(r)=\bigl(A_h(r,c_i)\bigr)_{i\in[5]}.(9)

The Claim

Theorem 1. Let hh be a nonnegative integer. For every selection 𝒄∈Nh[5]\mathbf c\in N_h^{[5]}, the word map in (9) satisfies ∃w∈{0,1}[5]\W𝒄(Nh).\exists w\in\{0,1\}^{[5]}\setminus W_{\mathbf c}(N_h).(10)✦ For a selection 𝒄∈Xh[5]\mathbf c\in X_h^{[5]} with ci∈Nhc_i\in N_h for every i∈[5]i\in[5], ∃w∈{0,1}[5]∀r∈Nh,(Ah(r,ci))i∈[5]≠w.\exists w\in\{0,1\}^{[5]}\quad \forall r\in N_h,\qquad \bigl(A_h(r,c_i)\bigr)_{i\in[5]}\ne w.(11)✦

In the paper, the result reads: for any five distinct nonanchor columns of AhA_h, the nonanchor rows do not realize all 3232 binary words on those columns.

What Is Checked

The claims (10) and (11) are stated over the raw host matrix (8) at every nonnegative height, with rows in NhN_h and five selected nonanchor columns.