OctoInformBeta

OpenAI preprint, September 2026 · §2. A fixed pattern and its tree matrices

§2 (setting): all entries of the host A_h: Role signatures specify the mixed blocks, with dummy ones and a level-dependent kernel on the remaining entries

The host couples anchors to tree levels.

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 for ordered binary matrix removal has anchor, variable and dummy positions. Anchor positions distinguish the constraint modes, while variable positions belong to signed levels of a binary tree. Rows and columns use the same set of positions, with their enumerations chosen separately.

Fix a nonnegative integer hh and put m=2hm=2^h. The set of modes is Mh={0,…,6h−1}M_h=\{0,\ldots,6h-1\}.✦ An anchor position (t,u,a)∈𝒜h(t,u,a)\in\mathcal A_h is a triple consisting of a mode t∈Mht\in M_h, an anchor index u∈{0,…,63}u\in\{0,\ldots,63\} and a copy index a∈{0,…,m−1}a\in\{0,\ldots,m-1\}. A variable position (a,b)∈𝒱h(a,b)\in\mathcal V_h is a pair consisting of a class index a∈{0,…,2h}a\in\{0,\ldots,2h\} and a copy index b∈{0,…,m−1}b\in\{0,\ldots,m-1\}. The dummy position set 𝒟h\mathcal D_h is a separate copy of {0,…,m−1}\{0,\ldots,m-1\}. These sets and their disjoint union XhX_h are 𝒜h=Mh×{0,…,63}×{0,…,m−1},𝒱h={0,…,2h}×{0,…,m−1},𝒟h={0,…,m−1},Xh=𝒜h⊔𝒱h⊔𝒟h.\begin{aligned} \mathcal A_h&=M_h\times\{0,\ldots,63\}\times\{0,\ldots,m-1\},\\ \mathcal V_h&=\{0,\ldots,2h\}\times\{0,\ldots,m-1\},\qquad \mathcal D_h=\{0,\ldots,m-1\},\\ X_h&=\mathcal A_h\sqcup\mathcal V_h\sqcup\mathcal D_h. \end{aligned}(1)

For a variable position v=(a,b)∈𝒱hv=(a,b)\in\mathcal V_h, its depth d(v)d(v), sign σ(v)\sigma(v) and node index ν(v)\nu(v) are d(v)=⌊a2⌋,σ(v)={+,a≡0(mod⁡2),−,a≡1(mod⁡2),ν(v)=⌊b2h−d(v)⌋.d(v)=\left\lfloor\frac a2\right\rfloor,\qquad \sigma(v)=\begin{cases}+,&a\equiv0\pmod2,\\-,&a\equiv1\pmod2,\end{cases} \qquad \nu(v)=\left\lfloor\frac b{2^{h-d(v)}}\right\rfloor.(2) The signed level ViσV_i^\sigma is the subset of variable positions at depth ii with sign σ\sigma, except that both signs include the entire leaf class: Viσ={v∈𝒱h:d(v)=i,i=horσ(v)=σ},Viσ,e={v∈Viσ:ν(v)≡e(mod⁡2)}.V_i^\sigma=\{v\in\mathcal V_h:d(v)=i,\quad i=h\ \text{or}\ \sigma(v)=\sigma\},\qquad V_i^{\sigma,e}=\{v\in V_i^\sigma:\nu(v)\equiv e\pmod2\}.(3)✦ For e∈{0,1}e\in\{0,1\}, the parity class Viσ,eV_i^{\sigma,e} is the subset of ViσV_i^\sigma whose node indices have parity ee.

The level ℓ(t)\ell(t) and type q(t)q(t) of a mode t∈Mht\in M_h are ℓ(t)=⌊t6⌋+1,q(t)=tmod⁡6.\ell(t)=\left\lfloor\frac t6\right\rfloor+1,\qquad q(t)=t\bmod6.(4) The row role ℛj(t)\mathcal R_j(t) and column role 𝒞j(t)\mathcal C_j(t), for j∈{0,1}j\in\{0,1\}, are subsets of XhX_h specified by the following table, using ℓ=ℓ(t)\ell=\ell(t) and q=q(t)q=q(t) from (4): qℛ0(t)ℛ1(t)𝒞0(t)𝒞1(t)0Vℓ+Vℓ−1+𝒟hVℓ−1+1Vℓ−1−Vℓ−𝒟hVℓ−1−2+eVℓ+,e𝒟hVℓ−1+Vℓ+,e4+eVℓ−,e𝒟hVℓ−,eVℓ−1−(e∈{0,1}).\begin{array}{c|cccc} q&\mathcal R_0(t)&\mathcal R_1(t)&\mathcal C_0(t)&\mathcal C_1(t)\\ \hline 0&V_\ell^+&V_{\ell-1}^+&\mathcal D_h&V_{\ell-1}^+\\ 1&V_{\ell-1}^-&V_\ell^-&\mathcal D_h&V_{\ell-1}^-\\ 2+e&V_\ell^{+,e}&\mathcal D_h&V_{\ell-1}^+&V_\ell^{+,e}\\ 4+e&V_\ell^{-,e}&\mathcal D_h&V_\ell^{-,e}&V_{\ell-1}^- \end{array} \qquad(e\in\{0,1\}).(5)

For a condition EE, the indicator 𝟏[E]\mathbf1[E] is one when EE holds and zero otherwise. The binary digit η(a,b)∈{0,1}\eta(a,b)\in\{0,1\}, for nonnegative integers a,ba,b, and the anchor matrix S∈{0,1}64×64S\in\{0,1\}^{64\times64} are defined by η(a,b)=𝟏[⌊a2max⁡{5−b,0}⌋≡1(mod⁡2)],Suv={η(u−32,v−58),32≤u≤63,59≤v≤63,𝟏[u≠v],otherwise,0≤u,v<64.\begin{aligned} \eta(a,b)&=\mathbf1\!\left[ \left\lfloor\frac a{2^{\max\{5-b,0\}}}\right\rfloor\equiv1\pmod2\right],\\ 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}\qquad 0\le u,v<64. \end{aligned}(6)

The Definition

Definition 1. For the positions and roles above, write κ+(p,q)=𝟏[p≤q]\kappa_+(p,q)=\mathbf1[p\le q] and κ−(p,q)=𝟏[p<q]\kappa_-(p,q)=\mathbf1[p<q]. The variable kernel Kh:𝒱h×𝒱h→{0,1}K_h:\mathcal V_h\times\mathcal V_h\to\{0,1\} is given by (7); for r,c∈𝒱hr,c\in\mathcal V_h, abbreviate dr=d(r)d_r=d(r), dc=d(c)d_c=d(c), σr=σ(r)\sigma_r=\sigma(r), σc=σ(c)\sigma_c=\sigma(c), νr=ν(r)\nu_r=\nu(r) and νc=ν(c)\nu_c=\nu(c) as in (2): Kh(r,c)={κ+(νr,νc),dr=dc=h,κσr(νr,νc),dr=dc<h,σr=σc,κσc(⌊νr/2⌋,νc),dr=dc+1,dc<h,dr=horσr=σc,0,otherwise.K_h(r,c)=\begin{cases} \kappa_+(\nu_r,\nu_c),&d_r=d_c=h,\\ \kappa_{\sigma_r}(\nu_r,\nu_c), &d_r=d_c<h,\quad\sigma_r=\sigma_c,\\ \kappa_{\sigma_c}(\lfloor\nu_r/2\rfloor,\nu_c), &\begin{gathered}d_r=d_c+1,\quad d_c<h,\\ d_r=h\ \text{or}\ \sigma_r=\sigma_c, \end{gathered}\\ 0,&\text{otherwise}. \end{cases}(7)✦ The host entry function Bh:Xh×Xh→{0,1}B_h:X_h\times X_h\to\{0,1\} is specified by (8), with SS from (6): Bh((t,u,a),(t′,v,b))=𝟏[t=t′]Suv,Bh((t,u,a),c)=𝟏[∃j∈{0,1}:u=j,c∈𝒞j(t)](c∉𝒜h),Bh(r,(t,v,b))=𝟏[∃j∈{0,1}:v=j,r∈ℛj(t)](r∉𝒜h),Bh(r,c)=Kh(r,c)(r,c∈𝒱h),Bh(r,c)=1(r,c∉𝒜h,{r,c}∩𝒟h≠⌀).\begin{aligned} B_h((t,u,a),(t',v,b))&=\mathbf1[t=t']S_{uv},\\ B_h((t,u,a),c)&=\mathbf1[\exists j\in\{0,1\}:u=j, \ c\in\mathcal C_j(t)] &&(c\notin\mathcal A_h),\\ B_h(r,(t,v,b))&=\mathbf1[\exists j\in\{0,1\}:v=j, \ r\in\mathcal R_j(t)] &&(r\notin\mathcal A_h),\\ B_h(r,c)&=K_h(r,c)&&(r,c\in\mathcal V_h),\\ B_h(r,c)&=1&&(r,c\notin\mathcal A_h, \ \{r,c\}\cap\mathcal D_h\ne\varnothing). \end{aligned}(8)✦ Put n=|Xh|n=|X_h|. For independent bijections er,ec:Xh→{0,…,n−1}e_r,e_c:X_h\to\{0,\ldots,n-1\}, the square host matrix AhA_h is the binary matrix of order nn defined by (Ah)ij=Bh(er−1(i),ec−1(j)),0≤i,j<n.(A_h)_{ij}=B_h(e_r^{-1}(i),e_c^{-1}(j)),\qquad 0\le i,j<n.(9)✦

In the paper, the result reads: anchor groups in the same mode carry SS, while anchor groups in different modes have zero entries; a non-anchor row or column has the unit signature eje_j, whose anchor coordinate jj is one and whose other coordinates are zero, in a mode exactly when it occupies role jj, and the zero signature when it occupies neither role; every non-anchor cell with a dummy coordinate has value one; writing Riσ(p)R_i^\sigma(p) and Ciσ(q)C_i^\sigma(q) for the row and column classes at nodes pp and qq of signed level ii, the nonzero variable cases are Ri+(p)×Ci+(q)R_i^+(p)\times C_i^+(q) with value 𝟏[p≤q]\mathbf1[p\le q] for 0≤i≤h0\le i\le h, Ri−(p)×Ci−(q)R_i^-(p)\times C_i^-(q) with value 𝟏[p<q]\mathbf1[p<q] for 0≤i<h0\le i<h, Ri+(p)×Ci−1+(q)R_i^+(p)\times C_{i-1}^+(q) with value 𝟏[⌊p/2⌋≤q]\mathbf1[\lfloor p/2\rfloor\le q] and Ri−(p)×Ci−1−(q)R_i^-(p)\times C_{i-1}^-(q) with value 𝟏[⌊p/2⌋<q]\mathbf1[\lfloor p/2\rfloor<q], the latter two for 1≤i≤h1\le i\le h; every absent case is zero.

What Is Checked

The definitions (7) and (8) are stated over the positions (1), with the signed levels and mode roles in (3) and (5); (9) is stated for separately chosen row and column bijections.