OctoInformBeta

OpenAI preprint, September 2026 · §3. Separated index windows

§3 (setting): the finite ordered tree, parameter budgets, and windows: Routing budgets and recursive spans accompany an explicit preorder construction

Separated index windows for ordered trees.

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

Finite ordered trees organize integer windows into descendant blocks. A window attached to an edge is a finite interval of integer indices, and the order of the children determines a depth-first preorder of the edges.

Fix nonnegative integers MM and dd. The child alphabet 𝒞M\mathcal C_M for a tree with MM nondefault children is the finite set in (1); MM is the default choice, and the indices less than MM are the nondefault choices: 𝒞M={0,1,…,M}.\mathcal C_M=\{0,1,\ldots,M\}.(1)✦ The set 𝒱M,d\mathcal V_{M,d} of decision nodes is the set of paths over 𝒞M\mathcal C_M of length less than dd, as in (2); the empty path is the root: 𝒱M,d=⋃k=0d−1𝒞Mk.\mathcal V_{M,d}=\bigcup_{k=0}^{d-1}\mathcal C_M^k.(2)✦ The set ℒM,d\mathcal L_{M,d} of terminal paths is the set of paths over 𝒞M\mathcal C_M of length exactly dd, as specified by (3): ℒM,d=𝒞Md.\mathcal L_{M,d}=\mathcal C_M^d.(3)✦ The total number of children is q=M+1q=M+1; the window construction below uses qq as its branching parameter.

For a general nonnegative integer qq, write Aq={0,…,q−1}A_q=\{0,\ldots,q-1\}. An edge of the complete ordered tree of depth dd is a nonempty path PP over AqA_q with |P|≤d|P|\le d.✦ Its height h(P)h(P) is given in (4): ℰq,d=⋃k=1dAqk,h(P)=d+1−|P|(P∈ℰq,d).\mathcal E_{q,d}=\bigcup_{k=1}^{d}A_q^k, \qquad h(P)=d+1-|P|\quad(P\in\mathcal E_{q,d}).(4) Write P≼QP\preceq Q when PP is a prefix of QQ, and P≺QP\prec Q for a proper prefix. The notation PiPi appends a child ii to PP, and PjTPjT appends jj followed by a path TT.

Fix nonnegative integers gg and R0R_0. A separated window system is a sequence of nonnegative integer lengths (λh)(\lambda_h) and nonnegative integer endpoints aP,bP,bP*a_P,b_P,b_P^* satisfying (5); the conditions involving paths apply whenever the displayed edge paths belong to ℰq,d\mathcal E_{q,d}: λh(P)≥max⁡{1,R0},aP≥3,bP+1=aP+λh(P),bP+g<aQ(P≺Q),bPi+g<aPjT(i<j),bP≤bQ≤bP*(P≼Q),bP*+1≤aP+2λh(P).\begin{aligned} \lambda_{h(P)}&\ge\max\{1,R_0\}, & a_P&\ge3,\\ b_P+1&=a_P+\lambda_{h(P)},\\ b_P+g&<a_Q &&(P\prec Q),\\ b_{Pi}+g&<a_{PjT} &&(i<j),\\ b_P&\le b_Q\le b_P^* &&(P\preceq Q),\\ b_P^*+1&\le a_P+2\lambda_{h(P)}. \end{aligned}(5)✦ The edge window WPW_P is the integer interval in (6): WP={n∈ℕ:aP≤n≤bP}.W_P=\{n\in\mathbb N:a_P\le n\le b_P\}.(6)✦ The global index set ℐ\mathcal I is the union in (7): ℐ=⋃P∈ℰq,dWP.\mathcal I=\bigcup_{P\in\mathcal E_{q,d}}W_P.(7)✦

Recursive Spans

The recursive window length rhr_h is the sequence in (8), defined together with the complete tree span σh\sigma_h in (9): r0=R0,rh+1=max⁡{R0,g+σh}(h≥0).r_0=R_0,\qquad r_{h+1}=\max\{R_0,g+\sigma_h\}\quad(h\ge0).(8)✦ σ0=0,σh+1=q(rh+1+{0,h=0,g+σh,h≥1)+(q−1)g.\sigma_0=0,\qquad \sigma_{h+1}=q\left(r_{h+1}+ \begin{cases} 0,&h=0,\\ g+\sigma_h,&h\ge1 \end{cases}\right)+(q-1)g.(9)✦ Here (q−1)g(q-1)g uses natural subtraction when q=0q=0. The child span chc_h, comprising an incoming window and the subtree below it, is defined by (10): ch=rh+1+{0,h=0,g+σh,h≥1.c_h=r_{h+1}+ \begin{cases} 0,&h=0,\\ g+\sigma_h,&h\ge1. \end{cases}(10)✦

Preorder Placement

Depth-first preorder lists each child edge before its descendants, completing the children in increasing order.✦ Let KK be the number of edges, and let P0,…,PK−1P_0,\ldots,P_{K-1} be this list of edges. The edge preorder rank e(Pi)=ie(P_i)=i starts at zero✦; the vertex preorder rank assigns zero to the root and e(P)+1e(P)+1 to a nonempty path PP.✦

The prescribed preorder length list LL and its zero extension ℓ\ell are given in (11): L=(rh(P0),…,rh(PK−1)),ℓi={Li,i<K,0,i≥K.L=(r_{h(P_0)},\ldots,r_{h(P_{K-1})}),\qquad \ell_i=\begin{cases}L_i,&i<K,\\0,&i\ge K.\end{cases}(11) The starting index sis_i and endpoint fif_i at preorder position ii are defined by (12), with subtraction in the natural numbers: s0=3,si+1=si+ℓi+g,fi=si+ℓi−1.s_0=3,\qquad s_{i+1}=s_i+\ell_i+g,\qquad f_i=s_i+\ell_i-1.(12)

The Claim

Theorem 1. Let pp be a real number with 0<p<10<p<1. There are positive integers M,d,RM,d,R meeting the probability budgets in (13), for every natural number r≥Rr\ge R and every natural number n≤1+Mr22r+2n\le1+Mr2^{2r+2}: pM2≥10,(1−2−M)d<p,n(1−p/2)Mr<p.\frac{pM}{2}\ge10,\qquad (1-2^{-M})^d<p,\qquad n(1-p/2)^{Mr}<p.(13)✦ For arbitrary nonnegative integers q,g,R0,hq,g,R_0,h, the recursive child span satisfies (14): ch≤2rh+1.c_h\le2r_{h+1}.(14)✦ For every q≥1q\ge1, R0≥1R_0\ge1 and nonnegative integers d,gd,g, the assignments in (15) define a separated window system: λh=rh,aP=se(P),bP=fe(P),bP*=se(P)+2rh(P)−1(P∈ℰq,d).\lambda_h=r_h,\qquad a_P=s_{e(P)},\qquad b_P=f_{e(P)},\qquad b_P^*=s_{e(P)}+2r_{h(P)}-1 \quad(P\in\mathcal E_{q,d}).(15)✦

In the paper, the result reads: for 0<p<10<p<1, choose q≥2q\ge2 and d≥1d\ge1 with p(q−1)/2≥10p(q-1)/2\ge10 and (1−21−q)d<p(1-2^{1-q})^d<p, take the complete ordered qq-ary tree of depth dd with K=∑ℓ=1dqℓK=\sum_{\ell=1}^d q^\ell edges in preorder, choose g≥1g\ge1 with K22−g<pK2^{2-g}<p and r*≥1r_*\ge1 such that 20qr(1+22r+2)exp⁡(−p(q−1)r/2)<p20qr(1+2^{2r+2})\exp(-p(q-1)r/2)<p for every integer r≥r*r\ge r_*, set σ0=0\sigma_0=0, rh=max⁡{r*,g+σh−1}r_h=\max\{r_*,g+\sigma_{h-1}\} for h≥1h\ge1, σ1=qr1+(q−1)g\sigma_1=qr_1+(q-1)g and σh=q(rh+g+σh−1)+(q−1)g\sigma_h=q(r_h+g+\sigma_{h-1})+(q-1)g for h≥2h\ge2, and place WP={aP,…,bP}W_P=\{a_P,\ldots,b_P\} in preorder starting at 33 with gg unused indices between consecutive windows and ℐ=⋃PWP\mathcal I=\bigcup_P W_P, so that the largest endpoint bˆP\widehat b_P in the child block beginning at an edge PP of height hh satisfies bˆP−aP+1≤2rh\widehat b_P-a_P+1\le2r_h.

What Is Checked

The statements concern finite paths in complete ordered trees, nonnegative integer gaps and thresholds, and real parameters 0<p<10<p<1; the window conditions in (5) apply to valid edges and the specified prefix and sibling pairs.