OctoInformBeta

OpenAI preprint, September 2026 · §5. Switching leaves and completing the proof

§5 (proof of Proposition 5.1): one terminal and the block estimate: Simultaneous detectors and subtree error bounds for a tree of nonexpansive maps

One terminal controls every finite switching block.

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

Switching a consecutive block of leaves changes the root output of a tree of nonexpansive maps. The question is how a continuous linear functional detects that change when every switched leaf is replaced by the same resolvent point.

Let XX be a real Banach space. A minimal invariant set for a selfmap T:K→KT:K\to K is a nonempty, norm-closed, bounded, convex, norm-separable, weakly compact subset KK of XX such that TT is nonexpansive, has no fixed point, and every nonempty norm-closed convex subset s⊆Ks\subseteq K with T(s)⊆sT(s)\subseteq s equals KK.✦ All norms are the original ambient norm. Normalized minimal invariant data consist of a minimal invariant set KK for a selfmap T:K→KT:K\to K, with diam⁡K=1\operatorname{diam}K=1, and a sequence (zi)i≥0(z_i)_{i\ge0} dense in KK for the norm topology. Write XwX_{\mathrm w} for the weakly topologized copy of XX and KwK_{\mathrm w} for its subset corresponding to KK; weak compactness means compactness in the weak topology. Assume KwK_{\mathrm w} is metrizable and the whole closed unit ball of the closed difference span of KK is weakly compact. Y=span⁡ℝ(K−K)¯,BY={u∈Y:∥u∥≤1}⊆X.Y=\overline{\operatorname{span}_{\mathbb R}(K-K)},\qquad B_Y=\{u\in Y:\|u\|\le1\}\subseteq X.(1) A subset ss of XX is invariant under TT if TT sends every point of s∩Ks\cap K into ss. The closed difference span YY of KK is the norm closure in XX of the real linear span of all differences of two points of KK.

For an anchor a∈Ka\in K and 0≤t≤10\le t\le1, the anchored averaging map St,aS_{t,a} is the selfmap in (2); for t>0t>0, its unique fixed point is the weighted resolvent ℛt(a)\mathcal R_t(a). The discrete resolvent RnR_n uses the positive integer index nn, whereas the terminal sequence (bj)j≥0(b_j)_{j\ge0} uses an anchor x∈Kx\in K and starts at zero. St,a(u)=ta+(1−t)T(u),Rn(a)=ℛ1/n(a)(n≥1),bj=Rj+1(x).S_{t,a}(u)=ta+(1-t)T(u),\qquad R_n(a)=\mathcal R_{1/n}(a)\quad(n\ge1),\qquad b_j=R_{j+1}(x).(2) The generated maps are the least family of selfmaps of KK containing the identity and every RnR_n, closed under composition and convex mixing: for maps F,GF,G in the family and a,b≥0a,b\ge0 with a+b=1a+b=1, their mixture sends uu to aF(u)+bG(u)aF(u)+bG(u).✦

An ordered rooted tree 𝒯\mathcal T has finite levels 𝒯k={0,…,mk−1}\mathcal T_k=\{0,\ldots,m_k-1\} with mk>0m_k>0 and m0=1m_0=1, and nondecreasing surjective parent maps between successive levels.✦ Its root is r=0r=0 at level zero.✦ A node vv at a positive level retains its depth |v||v| together with its index✦; the truncation through depth NN consists of those with 1≤|v|≤N1\le|v|\le N.✦ A weighted ordered tree 𝒯\mathcal T is an ordered rooted tree with a positive edge weight wcw_c for each child cc, such that the weights sum to one over the children of every parent.✦ The root path weight πv\pi_v of a node vv of the weighted ordered tree is the product of the edge weights along the path from rr to that node, as in (3). πr=1,πc=πparent⁡(c)wc.\pi_r=1,\qquad \pi_c=\pi_{\operatorname{parent}(c)}w_c.(3)✦

A tree evaluation on an ordered weighted tree is a family of nonexpansive selfmaps Fv:K→KF_v:K\to K, indexed by the nodes vv of the tree.✦ For an assignment HH on level d+1d+1, its child average CdHC_dH and its one-level collapse LdHL_dH are defined in (4). For an assignment HH on level NN and a node v∈𝒯kv\in\mathcal T_k, the subtree output 𝒮k,N(H)(v)\mathcal S_{k,N}(H)(v) is the point of KK obtained by the collapses in (4) from level NN to that node✦; EN(H)E_N(H) is the root output.✦ The maps are applied strictly above the cutoff level, whose values are not mapped again. CdH(p)=∑parent⁡(c)=pwcH(c),LdH(p)=Fp(CdH(p)),𝒮k,k(H)=H,𝒮k,N+1(H)=𝒮k,N(LNH),EN(H)=𝒮0,N(H)(r).\begin{gathered} C_dH(p)=\sum_{\operatorname{parent}(c)=p}w_cH(c),\qquad L_dH(p)=F_p(C_dH(p)),\\ \mathcal S_{k,k}(H)=H,\qquad \mathcal S_{k,N+1}(H)=\mathcal S_{k,N}(L_NH),\qquad E_N(H)=\mathcal S_{0,N}(H)(r). \end{gathered}(4)

The ancestor of s∈𝒯Ns\in\mathcal T_N at level k≤Nk\le N is denoted by ak,N(s)a_{k,N}(s). The descendants of v∈𝒯kv\in\mathcal T_k at level NN are the nodes with ak,N(s)=va_{k,N}(s)=v.✦ For a node v∈𝒯kv\in\mathcal T_k, the inclusive lower endpoint lvl_v of its descendant block at level NN is the first descendant index, and the exclusive upper endpoint hvh_v is one greater than the last descendant index. For leaf values y:𝒯N→Ky:\mathcal T_N\to K, a point b∈Kb\in K, and a switching index tt, the switched assignment HN,ty,bH_{N,t}^{y,b}, its root ZN,ty,bZ_{N,t}^{y,b}, and the roots before and after switching the descendant block of vv are those in (5). HN,ty,b(s)={ys,s<t,b,s≥t,ZN,ty,b=EN(HN,ty,b),UvN,y,b=ZN,hvy,b,VvN,y,b=ZN,lvy,b.\begin{gathered} H_{N,t}^{y,b}(s)= \begin{cases}y_s,&s<t,\\ b,&s\ge t,\end{cases} \qquad Z_{N,t}^{y,b}=E_N(H_{N,t}^{y,b}),\\ U_v^{N,y,b}=Z_{N,h_v}^{y,b},\qquad V_v^{N,y,b}=Z_{N,l_v}^{y,b}. \end{gathered}(5) For v∈𝒯kv\in\mathcal T_k, the ideal cutoff Iv(x,b)I_v(x,b) is the assignment on level kk that uses the node images Fu(x)F_u(x) before vv and the common residual point bb thereafter; its evaluated prediction is Qv(b)Q_v(b) in (6). Iv(x,b)(u)={Fu(x),u<v,b,u≥v,Qv(b)=Ek(Iv(x,b)).I_v(x,b)(u)=\begin{cases}F_u(x),&u<v,\\ b,&u\ge v,\end{cases} \qquad Q_v(b)=E_k(I_v(x,b)).(6)

Errors and Detectors

For positive budgets eve_v on the positive level nodes, the cumulative minimum mdem_d^e is the minimum of one and all budgets through depth dd, with m0e=1m_0^e=1.✦ The dyadic tolerance τde\tau_d^e is defined in (7). The injective candidate ordinals ℓ(v)\ell(v) determine the retained budgets in the same display. These ordinals start at zero and count discarded candidates as well as retained ones. mde=min⁡({1}∪{ev:1≤|v|≤d}),τde=2−(d+1)mde,ev=2−(ℓ(v)+9).m_d^e=\min\bigl(\{1\}\cup\{e_v:1\le|v|\le d\}\bigr),\qquad \tau_d^e=2^{-(d+1)}m_d^e,\qquad e_v=2^{-(\ell(v)+9)}.(7)

For a node vv and a point z∈Kz\in K, the ancestor displacement Pv(z)P_v(z) is the sum of the displacements of zz under every proper ancestor map, as in (8). The total terminal displacement DM(b)D_M(b) sums the displacements of all maps at depths less than MM.✦ For v∈𝒯kv\in\mathcal T_k and b∈Kb\in K, the descendant level displacement δd(v,b)\delta_d(v,b) is zero when d<kd<k; otherwise it is the sum over the level dd descendants uu of vv of ∥Fu(b)−b∥\|F_u(b)-b\|, each multiplied by its root path weight πu\pi_u. For a node vv and a point b∈Kb\in K, the internal displacement sum 𝒟v,N(b)\mathcal D_{v,N}(b) is the sum of the descendant level displacements δd(v,b)\delta_d(v,b) over 0≤d<N0\le d<N, as in (8). Pv(z)=∑u a proper ancestor of v∥Fu(z)−z∥,DM(b)=∑d=0M−1∑u∈𝒯d∥Fu(b)−b∥,𝒟v,N(b)=∑d=0N−1δd(v,b).\begin{gathered} P_v(z)=\sum_{u\text{ a proper ancestor of }v}\|F_u(z)-z\|,\qquad D_M(b)=\sum_{d=0}^{M-1}\sum_{u\in\mathcal T_d}\|F_u(b)-b\|,\\ \mathcal D_{v,N}(b)=\sum_{d=0}^{N-1}\delta_d(v,b). \end{gathered}(8)

Switching tree data on a normalized minimal invariant set consist of a weighted ordered tree, a tree evaluation by generated maps with Fr=idF_r=\operatorname{id}, an anchor xx, and the candidate ordinals specified in (7), together with the functionals, prediction limits and ultrafilter satisfying (9). Put yv=Fv(x)y_v=F_v(x) and abbreviate md=mdem_d=m_d^e and τd=τde\tau_d=\tau_d^e for the retained budgets. Each positive level node has a functional fv∈X*f_v\in X^* with ∥fv∥≤1\|f_v\|\le1 and a prediction limit av∈Ka_v\in K. There is an ultrafilter 𝒰\mathcal U on ℕ\mathbb N refining the cofinite filter, with the conditions in (9); the weak limit there is taken after the nonlinear root output has been evaluated. Extend eve_v and fvf_v by zero at the root. ∥Cd(y|𝒯d+1)(p)−x∥≤τd,Pv(yv)≤ev,Qv(bj)→𝒰weakav,fv(yv−av)≥1−ev,fv(yv−zi)≥1−ev(0≤i<|v|).\begin{gathered} \|C_d(y|_{\mathcal T_{d+1}})(p)-x\|\le\tau_d,\qquad P_v(y_v)\le e_v,\\ Q_v(b_j)\xrightarrow[\mathcal U]{\mathrm{weak}}a_v,\qquad f_v(y_v-a_v)\ge1-e_v,\qquad f_v(y_v-z_i)\ge1-e_v\quad(0\le i<|v|). \end{gathered}(9)

The Claim

Theorem 1. For an ordered weighted tree and a tree evaluation on a convex set KK, the following estimates hold.

For positive node budgets, v∈𝒯rv\in\mathcal T_r, and 1≤r≤k≤N1\le r\le k\le N, the tolerance tail satisfies (10). ∑d=kN−1τde≤ev.\sum_{d=k}^{N-1}\tau_d^e\le e_v.(10)✦

Let x∈Kx\in K and real tolerances (σd)(\sigma_d) satisfy the child-average bounds (11) through depth NN. ∥Cd((Fc(x))c∈𝒯d+1)(p)−x∥≤σd(0≤d<N,p∈𝒯d).\|C_d((F_c(x))_{c\in\mathcal T_{d+1}})(p)-x\|\le\sigma_d \quad(0\le d<N,\ p\in\mathcal T_d).(11) For k≤Nk\le N, v∈𝒯kv\in\mathcal T_k, and any assignment H:𝒯N→KH:\mathcal T_N\to K with H(s)=Fs(x)H(s)=F_s(x) on the descendants of vv, the untouched subtree estimate is (12). ∥𝒮k,N(H)(v)−Fv(x)∥≤∑d=kN−1σd.\|\mathcal S_{k,N}(H)(v)-F_v(x)\| \le\sum_{d=k}^{N-1}\sigma_d.(12)✦ For every b∈Kb\in K, k≤Nk\le N, and v∈𝒯kv\in\mathcal T_k, the constant subtree estimate is (13). ∥𝒮k,N((b)s∈𝒯N)(v)−b∥≤𝒟v,N(b)πv.\|\mathcal S_{k,N}((b)_{s\in\mathcal T_N})(v)-b\| \le\frac{\mathcal D_{v,N}(b)}{\pi_v}.(13)✦

Suppose diam⁡K≤1\operatorname{diam}K\le1, x,b∈Kx,b\in K, k≤Nk\le N, v∈𝒯kv\in\mathcal T_k, and f∈X*f\in X^* has norm at most one. Assume (11) and, for a real number ee, the bounds in (14). For the leaf assignment ys=Fs(x)y_s=F_s(x), the actual block estimate is (15). ∑d=kN−1σd≤e,Pv(Fv(x))≤e,DN(b)≤e,f(Fv(x)−Qv(b))≥1−2e.\begin{gathered} \sum_{d=k}^{N-1}\sigma_d\le e,\qquad P_v(F_v(x))\le e,\qquad D_N(b)\le e,\\ f(F_v(x)-Q_v(b))\ge1-2e. \end{gathered}(14) f(UvN,y,b−VvN,y,b)≥πv−5e.f(U_v^{N,y,b}-V_v^{N,y,b})\ge\pi_v-5e.(15)✦

For switching tree data and every N≥0N\ge0, there is an index j≥0j\ge0 satisfying (16). fv(yv−Qv(bj))≥1−2ev(1≤|v|≤N),DN+1(bj)≤mN.\begin{gathered} f_v(y_v-Q_v(b_j))\ge1-2e_v\quad(1\le|v|\le N),\\ D_{N+1}(b_j)\le m_N. \end{gathered}(16)✦ For any N,jN,j satisfying (16), the roots for the level NN assignment ys=Fs(x)y_s=F_s(x) satisfy (17) at every node of the nonroot truncation. fv(UvN,y,bj−VvN,y,bj)≥πv−5ev(1≤|v|≤N).f_v(U_v^{N,y,b_j}-V_v^{N,y,b_j})\ge\pi_v-5e_v \quad(1\le|v|\le N).(17)✦

In the paper, the result reads: a single b=bjb=b_j can be chosen so that every nonroot node vv through depth NN satisfies fv(yv−Qv(b))≥1−2evf_v(y_v-Q_v(b))\ge1-2e_v and the sum of all map displacements through depth NN is at most the minimum budget through depth NN; untouched subtrees have error at most ∑d=kN−1τd≤ev\sum_{d=k}^{N-1}\tau_d\le e_v, fully switched subtrees have error at most that common displacement bound, and these give fv(Uv−Vv)≥πv−5evf_v(U_v-V_v)\ge\pi_v-5e_v.

What Is Checked

The common terminal and finite block assertions are stated over switching tree data on normalized minimal invariant sets; the subtree and actual block estimates are stated over arbitrary weighted ordered trees of nonexpansive selfmaps with the displayed hypotheses.

For 0<t≤10<t\le1, the anchored averaging map St,aS_{t,a} is a strict contraction with factor 1−t1-t✦, and positive integer indices satisfy 0<1/n≤10<1/n\le1.

Every node of the ordered rooted tree has a nonempty descendant set at every later level.✦