OctoInformBeta

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

Lemma 4.2: Row and column bounds for selections with distinct mode and group labels

Sparse anchor incidence at variable positions.

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

Variable rows and columns interact with the anchor part of the host matrix through the two body roles of each constraint mode. Lemma 4.2 concerns the number of these roles available to a single variable position and the resulting anchor incidences.

For a nonnegative integer hh, put m=2hm=2^h and write [q]={0,…,q−1}[q]=\{0,\ldots,q-1\}, with [0]=⌀[0]=\varnothing. A mode tt is an element of Th=[6h]T_h=[6h]; its level L(t)L(t) and type κ(t)\kappa(t) are the integers in (1). L(t)=⌊t6⌋+1,κ(t)=tmod⁡6.L(t)=\left\lfloor\frac{t}{6}\right\rfloor+1, \qquad \kappa(t)=t\bmod 6.(1) An anchor position is a triple (t,u,b)∈Ah=Th×[64]×[m](t,u,b)\in A_h=T_h\times[64]\times[m], where uu is its anchor group and bb its offset.✦ A variable position is a pair x=(a,b)∈Vh=[2h+1]×[m]x=(a,b)\in V_h=[2h+1]\times[m].✦ The tree depth d(x)d(x), positive sign σ(x)\sigma(x) and tree node index q(x)q(x) of a variable position x=(a,b)∈Vhx=(a,b)\in V_h are the integers specified in (2). d(x)=⌊a2⌋,σ(x)=𝟏{a is even},q(x)=⌊b2h−d(x)⌋.d(x)=\left\lfloor\frac a2\right\rfloor, \qquad \sigma(x)=\mathbf1_{\{a\text{ is even}\}}, \qquad q(x)=\left\lfloor\frac{b}{2^{h-d(x)}}\right\rfloor.(2) For each tree depth ii and sign e∈{0,1}e\in\{0,1\}, the signed level class VieV_i^e is the subset of VhV_h specified in (3); the two signs distinguish the internal classes and share the leaf class. Vie={x∈Vh:d(x)=i,i=h or σ(x)=e},e∈{0,1}.V_i^e=\{x\in V_h:d(x)=i,\ i=h\text{ or }\sigma(x)=e\}, \qquad e\in\{0,1\}.(3)✦ A host position zz is an element of the disjoint union Xh=Ah⊔Vh⊔DhX_h=A_h\sqcup V_h\sqcup D_h, where DhD_h is a separate copy of [m][m] consisting of dummy positions.✦

Roles and Host Entries

For a mode t∈Tht\in T_h and j∈{0,1}j\in\{0,1\}, the row role Rt,jR_{t,j} and column role Ct,jC_{t,j} are the subsets of XhX_h whose variable parts are specified in (4), which contain no anchor positions, and which contain a dummy position exactly when, respectively, κ(t)≥2\kappa(t)\ge2 and j=1j=1, or κ(t)<2\kappa(t)<2 and j=0j=0. Here L=L(t)L=L(t) and Et={x∈Vh:q(x)≡κ(t)(mod⁡2)}E_t=\{x\in V_h:q(x)\equiv\kappa(t)\pmod 2\}. κ(t)Rt,0∩VhRt,1∩VhCt,0∩VhCt,1∩Vh0VL1VL−11⌀VL−111VL−10VL0⌀VL−102,3VL1∩Et⌀VL−11VL1∩Et4,5VL0∩Et⌀VL0∩EtVL−10\begin{array}{c|cc|cc} \kappa(t)&R_{t,0}\cap V_h&R_{t,1}\cap V_h &C_{t,0}\cap V_h&C_{t,1}\cap V_h\\ \hline 0&V_L^1&V_{L-1}^1&\varnothing&V_{L-1}^1\\ 1&V_{L-1}^0&V_L^0&\varnothing&V_{L-1}^0\\ 2,3&V_L^1\cap E_t&\varnothing&V_{L-1}^1&V_L^1\cap E_t\\ 4,5&V_L^0\cap E_t&\varnothing&V_L^0\cap E_t&V_{L-1}^0 \end{array}(4)

The anchor matrix SS is the binary 64×6464\times64 matrix in (5), using the binary digit η\eta defined there; its row and column indices start at zero. η(a,b)=𝟏{⌊a/2max⁡{5−b,0}⌋ is odd},Suv={η(u−32,v−58),32≤u≤63,59≤v≤63,𝟏{u≠v},otherwise.\begin{aligned} \eta(a,b)&=\mathbf1_{\left\{\left\lfloor a/2^{\max\{5-b,0\}}\right\rfloor\text{ is odd}\right\}},\\ S_{uv}&=\begin{cases} \eta(u-32,v-58),&32\le u\le63,\ 59\le v\le63,\\ \mathbf1_{\{u\ne v\}},&\text{otherwise}. \end{cases} \end{aligned}(5) Write a≼1ba\preceq_1 b for a≤ba\le b and a≼0ba\preceq_0 b for a<ba<b. The variable matrix WW is the binary matrix on Vh×VhV_h\times V_h defined in (6), with dr=d(r)d_r=d(r), qr=q(r)q_r=q(r) and σr=σ(r)\sigma_r=\sigma(r), and similarly for cc. W(r,c)={𝟏{qr≤qc},dr=dc=h,𝟏{qr≼σrqc},dr=dc<h,σr=σc,𝟏{⌊qr/2⌋≼σcqc},dr=dc+1,dc<h,(dr=h or σr=σc),0,otherwise.W(r,c)=\begin{cases} \mathbf1_{\{q_r\le q_c\}},&d_r=d_c=h,\\ \mathbf1_{\{q_r\preceq_{\sigma_r}q_c\}}, &d_r=d_c<h,\ \sigma_r=\sigma_c,\\ \mathbf1_{\{\lfloor q_r/2\rfloor\preceq_{\sigma_c}q_c\}}, &d_r=d_c+1,\ d_c<h,\ (d_r=h\text{ or }\sigma_r=\sigma_c),\\ 0,&\text{otherwise}. \end{cases}(6)✦ The raw host matrix MM is the binary matrix on Xh×XhX_h\times X_h specified by (7), where a=(t,u,b)a=(t,u,b) and a′=(t′,u′,b′)a'=(t',u',b') are anchor positions. M(a,a′)=𝟏{t=t′}Suu′,M(a,c)=𝟏{(u=0 and c∈Ct,0) or (u=1 and c∈Ct,1)},c∈Vh⊔Dh,M(r,a)=𝟏{(u=0 and r∈Rt,0) or (u=1 and r∈Rt,1)},r∈Vh⊔Dh,M(r,c)=W(r,c),r,c∈Vh,M(r,c)=1,r,c∈Vh⊔Dh,r∈Dh or c∈Dh.\begin{aligned} M(a,a')&=\mathbf1_{\{t=t'\}}S_{uu'},\\ M(a,c)&=\mathbf1_{\{(u=0\text{ and }c\in C_{t,0}) \text{ or }(u=1\text{ and }c\in C_{t,1})\}}, &&c\in V_h\sqcup D_h,\\ M(r,a)&=\mathbf1_{\{(u=0\text{ and }r\in R_{t,0}) \text{ or }(u=1\text{ and }r\in R_{t,1})\}}, &&r\in V_h\sqcup D_h,\\ M(r,c)&=W(r,c),&&r,c\in V_h,\\ M(r,c)&=1,&&r,c\in V_h\sqcup D_h,\quad r\in D_h\text{ or }c\in D_h. \end{aligned}(7)✦

The Claim

Theorem 1 (Lemma 4.2). Let hh be a nonnegative integer and v∈Vhv\in V_h. Let Tr,Tc⊆ThT_r,T_c\subseteq T_h be sets of modes such that v∈Rt,0∪Rt,1v\in R_{t,0}\cup R_{t,1} for every t∈Trt\in T_r and v∈Ct,0∪Ct,1v\in C_{t,0}\cup C_{t,1} for every t∈Tct\in T_c. The respective bounds are (8) and (9). |Tr|≤4.|T_r|\le4.(8)✦ |Tc|≤4.|T_c|\le4.(9)✦ Let II be a finite index set and let ai=(ti,ui,bi)∈Aha_i=(t_i,u_i,b_i)\in A_h, for i∈Ii\in I, with i↦(ti,ui)i\mapsto(t_i,u_i) injective. The anchor entry bounds are (10) and (11). |{i∈I:M(v,ai)=1}|≤4.\bigl|\{i\in I:M(v,a_i)=1\}\bigr|\le4.(10)✦ |{i∈I:M(ai,v)=1}|≤4.\bigl|\{i\in I:M(a_i,v)=1\}\bigr|\le4.(11)✦

In the paper, the result reads: a variable position on either axis belongs to designated sets of at most four modes, and consequently has at most four entries equal to one against any collection containing at most one representative of each anchor group on the opposite axis.

What Is Checked

The assertions are stated over the variable positions VhV_h, finite sets of modes and finite families of anchor positions whose mode and group labels are distinct.