OctoInformBeta

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

§2 (setting): tree positions, modes and the independent axis orders: Six modes at each positive depth select two row roles and two column roles

Tree positions with separate axis orders.

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 matrix construction specifies a carrier for both axes and a separate order on each axis. Here the variable positions follow a complete binary tree, while anchor positions and dummy positions supply the other blocks of the matrix.

Fix a nonnegative integer hh, put m=2hm=2^h and s=64s=64, and, for every nonnegative integer qq, write [q]={0,…,q−1}[q]=\{0,\ldots,q-1\}, with [0]=⌀[0]=\varnothing. All coordinates start at zero.

The Claim

Definition 1 (Tree positions and axis orders). The set of modes ℳh\mathcal M_h is the finite ordered set in (1). ℳh=[6h].\mathcal M_h=[6h].(1)✦ A mode tt has level ℓ(t)=⌊t/6⌋+1\ell(t)=\lfloor t/6\rfloor+1 and type r(t)=tmod⁡6r(t)=t\bmod6. At each level, types 0,1,2,3,4,50,1,2,3,4,5 are called V+,V−,W0+,W1+,W0−,W1−V^+,V^-,W_0^+,W_1^+,W_0^-,W_1^-, respectively.

A variable position is a pair v=(a,z)v=(a,z) in the set 𝒱h\mathcal V_h of (2); aa is its class and zz its coordinate. 𝒱h=[2h+1]×[m].\mathcal V_h=[2h+1]\times[m].(2) The sign σ(v)\sigma(v) of a variable position v=(a,z)v=(a,z) in 𝒱h\mathcal V_h is ++ when aa is even and −- when aa is odd. The depth dep⁡(v)\operatorname{dep}(v) and node index ν(v)\nu(v) of a variable position vv in 𝒱h\mathcal V_h are the nonnegative integers defined by (3) and (4). dep⁡(a,z)=⌊a2⌋.\operatorname{dep}(a,z)=\left\lfloor\frac a2\right\rfloor.(3)✦ ν(v)=⌊z2h−dep⁡(v)⌋.\nu(v)=\left\lfloor\frac{z}{2^{h-\operatorname{dep}(v)}}\right\rfloor.(4)✦ For a nonnegative integer ii and a sign σ∈{+,−}\sigma\in\{+,-\}, the signed level LiσL_i^\sigma is the subset of variable positions specified in (5). Liσ={v∈𝒱h:dep⁡(v)=i,i=horσ(v)=σ}.L_i^\sigma= \{v\in\mathcal V_h:\operatorname{dep}(v)=i,\quad i=h\ \text{or}\ \sigma(v)=\sigma\}.(5)✦ For a nonnegative integer ii, a sign σ∈{+,−}\sigma\in\{+,-\} and d∈{0,1}d\in\{0,1\}, the parity class Li,dσL_{i,d}^\sigma of the signed level LiσL_i^\sigma is the subset Li,dσ={v∈Liσ:ν(v)mod⁡2=d}L_{i,d}^\sigma=\{v\in L_i^\sigma:\nu(v)\bmod2=d\}.

The anchor set 𝒜h\mathcal A_h is the set of triples consisting of a mode, an anchor group and a coordinate, as in (6). 𝒜h=ℳh×[s]×[m].\mathcal A_h=\mathcal M_h\times[s]\times[m].(6) The dummy positions form a separate copy 𝒟h\mathcal D_h of [m][m]. The matrix carrier Ωh\Omega_h is the disjoint union in (7). Ωh=𝒜h⊔𝒱h⊔𝒟h.\Omega_h=\mathcal A_h\sqcup\mathcal V_h\sqcup\mathcal D_h.(7)✦ The matrix size nhn_h is the cardinality of the carrier Ωh\Omega_h, given by (8). |Ωh|=nh:=(386h+2)2h.|\Omega_h|=n_h:=(386h+2)2^h.(8)✦

For a mode tt of level i=ℓ(t)i=\ell(t) and type r=r(t)r=r(t), its first and second row roles ℛ0(t),ℛ1(t)⊆Ωh\mathcal R_0(t),\mathcal R_1(t)\subseteq\Omega_h are defined by (9). (ℛ0(t),ℛ1(t))={(Li+,Li−1+),r=0,(Li−1−,Li−),r=1,(Li,rmod⁡2+,𝒟h),2≤r<4,(Li,rmod⁡2−,𝒟h),4≤r<6.\bigl(\mathcal R_0(t),\mathcal R_1(t)\bigr)= \begin{cases} (L_i^+,L_{i-1}^+),&r=0,\\ (L_{i-1}^-,L_i^-),&r=1,\\ (L_{i,r\bmod2}^+,\mathcal D_h),&2\le r<4,\\ (L_{i,r\bmod2}^-,\mathcal D_h),&4\le r<6. \end{cases}(9)✦ For a mode tt of level i=ℓ(t)i=\ell(t) and type r=r(t)r=r(t), the first and second column roles 𝒞0(t),𝒞1(t)⊆Ωh\mathcal C_0(t),\mathcal C_1(t)\subseteq\Omega_h are defined by (10). (𝒞0(t),𝒞1(t))={(𝒟h,Li−1+),r=0,(𝒟h,Li−1−),r=1,(Li−1+,Li,rmod⁡2+),2≤r<4,(Li,rmod⁡2−,Li−1−),4≤r<6.\bigl(\mathcal C_0(t),\mathcal C_1(t)\bigr)= \begin{cases} (\mathcal D_h,L_{i-1}^+),&r=0,\\ (\mathcal D_h,L_{i-1}^-),&r=1,\\ (L_{i-1}^+,L_{i,r\bmod2}^+),&2\le r<4,\\ (L_{i,r\bmod2}^-,L_{i-1}^-),&4\le r<6. \end{cases}(10)✦

A traversal key Kδ(v)K_\delta(v) is a five-tuple of nonnegative integers, compared lexicographically, where δ=0\delta=0 selects the row axis and δ=1\delta=1 the column axis. For v=(a,z)v=(a,z), put i=dep⁡(v)i=\operatorname{dep}(v), b=2h−ib=2^{h-i} and p=ν(v)p=\nu(v); the leaf, subtree entry and subtree exit keys are the cases of (11). Kδ(a,z)={(2z+1,2,0,2h,z),a=2h,(2pb,1,i,a,z),a<2h,amod⁡2=1−δ,(2(p+1)b,0,h−i,a,z),otherwise.K_\delta(a,z)= \begin{cases} (2z+1,2,0,2h,z),&a=2h,\\ (2pb,1,i,a,z),&a<2h,\ a\bmod2=1-\delta,\\ (2(p+1)b,0,h-i,a,z),&\text{otherwise}. \end{cases}(11)✦ The variable order for each axis compares its traversal keys.✦

The anchor order compares mode, group and coordinate lexicographically.✦ Writing A(t,u,z)A(t,u,z) for an anchor in 𝒜h\mathcal A_h and D(z)D(z) for a dummy in 𝒟h\mathcal D_h, the row coordinate map ρ\rho and column coordinate map κ\kappa on Ωh\Omega_h are the maps defined by (12); the leading coordinate orders the blocks, and subsequent coordinates are compared lexicographically. ρ(A(t,u,z))=(0,t,u,z),κ(A(t,u,z))=(0,t,u,z),ρ(v)=(1,K0(v)),κ(v)=(2,K1(v)),ρ(D(z))=(2,z),κ(D(z))=(1,z).\begin{aligned} \rho(A(t,u,z))&=(0,t,u,z),&\kappa(A(t,u,z))&=(0,t,u,z),\\ \rho(v)&=(1,K_0(v)),&\kappa(v)&=(2,K_1(v)),\\ \rho(D(z))&=(2,z),&\kappa(D(z))&=(1,z). \end{aligned}(12) The row order <r<_r on Ωh\Omega_h is defined by (13). x<ry⇔ρ(x)<lexρ(y).x<_r y\quad\Longleftrightarrow\quad\rho(x)<_{\mathrm{lex}}\rho(y).(13)✦ For columns, (14) defines the order <c<_c on Ωh\Omega_h. x<cy⇔κ(x)<lexκ(y).x<_c y\quad\Longleftrightarrow\quad\kappa(x)<_{\mathrm{lex}}\kappa(y).(14)✦ The increasing row enumeration ιr:Ωh→[nh]\iota_r:\Omega_h\to[n_h] is the bijection in (15). ιr(x)=|{y∈Ωh:y<rx}|.\iota_r(x)=|\{y\in\Omega_h:y<_r x\}|.(15)✦ Counting column predecessors gives the increasing bijection ιc:Ωh→[nh]\iota_c:\Omega_h\to[n_h] in (16). ιc(x)=|{y∈Ωh:y<cx}|.\iota_c(x)=|\{y\in\Omega_h:y<_c x\}|.(16)✦

In the paper, the result reads: for h≥1h\ge1 and m=2hm=2^h, each internal node pp at depth i<hi<h has separate row blocks Ri−(p),Ri+(p)R_i^-(p),R_i^+(p) and column blocks Ci−(p),Ci+(p)C_i^-(p),C_i^+(p) of size m/2im/2^i, the two signs share singleton leaf blocks, each axis has a dummy block R*R_* or C*C_* of size mm, the variable row order is minus block, child 00 subtree, child 11 subtree, plus block and the column order reverses the signs, dummy rows follow all variable rows and dummy columns precede all variable columns, the modes at each depth 1≤i≤h1\le i\le h occur in the order Vi+,Vi−,Wi,0+,Wi,1+,Wi,0−,Wi,1−V_i^+,V_i^-,W_{i,0}^+,W_{i,1}^+,W_{i,0}^-,W_{i,1}^- with respective row and column role quadruples (Ri+,Ri−1+,C*,Ci−1+)(R_i^+,R_{i-1}^+,C_*,C_{i-1}^+), (Ri−1−,Ri−,C*,Ci−1−)(R_{i-1}^-,R_i^-,C_*,C_{i-1}^-), (Ri,d+,R*,Ci−1+,Ci,d+)(R_{i,d}^+,R_*,C_{i-1}^+,C_{i,d}^+) and (Ri,d−,R*,Ci,d−,Ci−1−)(R_{i,d}^-,R_*,C_{i,d}^-,C_{i-1}^-) for d=0,1d=0,1, where subscript dd restricts node indices to parity dd, each mode has ss consecutive anchor groups of size mm on each axis placed before every non-anchor position in mode order, the total axis size is nh=(6hs+2h+2)m=(386h+2)2hn_h=(6hs+2h+2)m=(386h+2)2^h, and ordered bodies satisfy the row and column inequalities within their role sets.

What Is Checked

The definitions are stated for every nonnegative integer hh, on the finite carrier Ωh\Omega_h with its separate row and column orders and their increasing enumerations. For either axis, distinct variable positions have distinct traversal keys.✦