OctoInformBeta

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

Proposition 5.1 [A finite witness]: A vector in BYB_Y, the unit ball of the closed difference span, is detected simultaneously along a branch at every finite depth

Switching trees admit finite witnesses.

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

Continuous linear functionals attached to a tree impose simultaneous conditions on a single vector along a branch. Leaf switching supplies the finite differences to which these functionals are applied.

Let XX be a real Banach space, let XwX_w denote its weakly topologized copy, and let ι:X→Xw\iota:X\to X_w be the canonical identification. All norm and nonexpansiveness conditions use the original ambient norm and its induced dual norm. For C⊂XC\subset X, its weak carrier Cw=ι(C)C_w=\iota(C) has the induced topology; weak compactness of CC means compactness of CwC_w in XwX_w.

Minimal invariant data (K,T)(K,T) consist of a nonempty, norm-closed, bounded, convex, norm-separable, weakly compact subset K⊂XK\subset X and a fixed-point-free nonexpansive map T:K→KT:K\to K, with KK minimal among its nonempty norm-closed convex invariant subsets.✦ A subset s⊂Xs\subset X is invariant relative to KK when T(s∩K)⊂sT(s\cap K)\subset s.✦ The closed difference span YY and its whole closed unit ball BYB_Y, viewed as subsets of XX, are given by (1), with norm closure and the original ambient norm: Y=span⁡ℝ(K−K)¯,BY={d∈Y:∥d∥≤1}.Y=\overline{\operatorname{span}_{\mathbb R}(K-K)}, \qquad B_Y=\{d\in Y:\|d\|\le1\}.(1) Normalized minimal invariant data (K,T,z)(K,T,z) consist of minimal invariant data (K,T)(K,T) with diam⁡K=1\operatorname{diam}K=1, a sequence zz, written (zh)h≥0(z_h)_{h\ge0}, with norm-dense range in KK, metrizability of KwK_w, and weak compactness of BYB_Y.✦

For an anchor a∈Ka\in K and 0≤t≤10\le t\le1, the anchored averaging map St,a:K→KS_{t,a}:K\to K is defined in (2). The weighted resolvent ℛt(a)\mathcal R_t(a) is the unique fixed point of the anchored averaging map St,aS_{t,a} for an anchor a∈Ka\in K and t>0t>0 in the parameter range of (2). The discrete resolvent RnR_n and terminal resolvent sequence bj(x)b_j(x), for x∈Kx\in K, have the indices in (2): St,a(v)=ta+(1−t)T(v),ℛt(a)=St,a(ℛt(a))(0<t≤1),Rn=ℛ1/n(n≥1),bj(x)=Rj+1(x)(j≥0).\begin{gathered} S_{t,a}(v)=ta+(1-t)T(v),\qquad \mathcal R_t(a)=S_{t,a}(\mathcal R_t(a))\quad(0<t\le1),\\ R_n=\mathcal R_{1/n}\quad(n\ge1),\qquad b_j(x)=R_{j+1}(x)\quad(j\ge0). \end{gathered}(2) The generated maps form the least family of selfmaps of KK containing the identity and the RnR_n, and closed under composition and binary convex combinations.✦ For selfmaps g,h:K→Kg,h:K\to K, their convex combination with coefficients a,b≥0a,b\ge0 and a+b=1a+b=1 is the map u↦ag(u)+bh(u)u\mapsto ag(u)+bh(u).✦

Tree Evaluations

An ordered rooted tree 𝒯\mathcal T is a sequence of finite levels Lk={0,…,mk−1}L_k=\{0,\ldots,m_k-1\} with mk>0m_k>0 and m0=1m_0=1, together with nondecreasing surjective parent maps pk:Lk+1→Lkp_k:L_{k+1}\to L_k.✦ Its root is r=0∈L0r=0\in L_0.✦ The ancestor aik(v)∈Lia_i^k(v)\in L_i of v∈Lkv\in L_k, for i≤ki\le k, is obtained by successive parent maps, with akk(v)=va_k^k(v)=v.✦ Positive-level nodes retain their depth; for a natural number NN, the finite nonroot truncation is 𝒱N={(i,v):1≤i≤N,v∈Li}\mathcal V_N=\{(i,v):1\le i\le N,\ v\in L_i\}.

A weighted ordered tree is an ordered rooted tree equipped with a weight wc>0w_c>0 for each child c∈Lk+1c\in L_{k+1}, with the weights over the children of every parent summing to one.✦ The root path weight π(v)\pi(v) of a node vv of a weighted ordered tree is the product of the edge weights from rr to vv, with π(r)=1\pi(r)=1.✦ A tree evaluation EE on a weighted ordered tree with values in a convex set C⊂XC\subset X is a family of nonexpansive selfmaps gv:C→Cg_v:C\to C, one for each node.✦ For p∈Lkp\in L_k and H:Lk+1→CH:L_{k+1}\to C, the weighted child average Cp(H)C_p(H) of HH at pp is the vector in CC given by (3): Cp(H)=∑c∈Lk+1pk(c)=pwcH(c).C_p(H)=\sum_{\substack{c\in L_{k+1}\\p_k(c)=p}}w_cH(c).(3)✦ The cutoff evaluation Ek(H)∈CE_k(H)\in C of H:Lk→CH:L_k\to C repeatedly takes these averages and applies the node maps strictly above level kk; it applies no map at the cutoff itself, and E0(H)=H(r)E_0(H)=H(r).✦

For v∈Liv\in L_i and i≤Ni\le N, the terminal descendants, their first and last members, and their inclusive lower and exclusive upper endpoints are defined by (4): DvN={s∈LN:aiN(s)=v},svfirst=min⁡DvN,svlast=max⁡DvN,lv=svfirst,hv=svlast+1.\begin{gathered} D_v^N=\{s\in L_N:a_i^N(s)=v\},\qquad s_v^{\mathrm{first}}=\min D_v^N,\qquad s_v^{\mathrm{last}}=\max D_v^N,\\ l_v=s_v^{\mathrm{first}},\qquad h_v=s_v^{\mathrm{last}}+1. \end{gathered}(4) Given y:LN→Cy:L_N\to C and b∈Cb\in C, the switched leaf assignment HtH_t is a map from LNL_N to CC that retains yy below the integer cutoff tt and uses bb elsewhere.✦ For switched leaf assignments HtH_t on LNL_N, the evaluated switching root q(t)q(t) is a point of CC, the normalized leaf switch vector dsd_s for a leaf s∈LNs\in L_N is a vector in XX, and the roots qvbeforeq_v^{\mathrm{before}} and qvafterq_v^{\mathrm{after}} are the points of CC before and after switching the descendants of vv, all defined in (5): Ht(s)={y(s),s<t,b,s≥t,q(t)=EN(Ht),ds=π(s)−1(q(s+1)−q(s)),qvbefore=q(hv),qvafter=q(lv).\begin{gathered} H_t(s)=\begin{cases}y(s),&s<t,\\b,&s\ge t,\end{cases} \qquad q(t)=E_N(H_t),\\ d_s=\pi(s)^{-1}\bigl(q(s+1)-q(s)\bigr),\qquad q_v^{\mathrm{before}}=q(h_v),\qquad q_v^{\mathrm{after}}=q(l_v). \end{gathered}(5) For x,b∈Cx,b\in C and v∈Liv\in L_i, the ideal switched cutoff Iix,b,v:Li→CI_i^{x,b,v}:L_i\to C is the assignment in (6): Iix,b,v(u)={gu(x),u<v,b,u≥v.I_i^{x,b,v}(u)= \begin{cases}g_u(x),&u<v,\\b,&u\ge v.\end{cases}(6)✦ The ancestor displacement sum Δv(z)\Delta_v(z), for v∈Liv\in L_i and z∈Cz\in C, is the sum of the displacements of zz under the proper ancestor maps, as in (7): Δv(z)=∑h=0i−1∥gahi(v)(z)−z∥,Δr(z)=0.\Delta_v(z)=\sum_{h=0}^{i-1}\|g_{a_h^i(v)}(z)-z\|, \qquad \Delta_r(z)=0.(7)✦

Switching Tree Data

A candidate ordinal nn is zero-based and counts discarded candidates as well as retained ones. For a candidate ordinal nn and an injective ordinal assignment ℓ\ell on the positive-level nodes, the dyadic budget β(n)\beta(n), the retained budgets eve_v, the cumulative budget minimum MkM_k, and the dyadic tolerance τk\tau_k are the positive real numbers defined in (8): β(n)=2−(n+9),ev=β(ℓ(v)),Mk=min⁡({1}∪{ev:v∈Li,1≤i≤k}),τk=2−(k+1)Mk.\begin{gathered} \beta(n)=2^{-(n+9)},\qquad e_v=\beta(\ell(v)),\\ M_k=\min\bigl(\{1\}\cup \{e_v:v\in L_i,\ 1\le i\le k\}\bigr),\qquad \tau_k=2^{-(k+1)}M_k. \end{gathered}(8)

Switching tree data AA over normalized minimal invariant data consist of a weighted ordered tree with an evaluation on KK by generated maps, with grg_r the identity, an anchor x∈Kx\in K, and an injective ordinal assignment ℓ\ell. They include functionals fv∈X*f_v\in X^* at positive-level nodes, an ultrafilter 𝒰\mathcal U on ℕ\mathbb N extending the cofinite filter, and prediction limits av∈Ka_v\in K, subject to (9). Here p∈Lkp\in L_k, v∈Liv\in L_i with i>0i>0, and the convergence is in XwX_w after evaluation of the root outputs: ∥fv∥≤1,∥Cp(c↦gc(x))−x∥≤τk,Δv(gv(x))≤ev,ι(Ei(Iix,bj(x),v))→𝒰ι(av),fv(gv(x)−av)≥1−ev,fv(gv(x)−zh)≥1−ev(0≤h<i).\begin{gathered} \|f_v\|\le1,\qquad \|C_p(c\mapsto g_c(x))-x\|\le\tau_k,\qquad \Delta_v(g_v(x))\le e_v,\\ \iota\bigl(E_i(I_i^{x,b_j(x),v})\bigr) \longrightarrow_{\mathcal U}\iota(a_v),\\ f_v(g_v(x)-a_v)\ge1-e_v,\qquad f_v(g_v(x)-z_h)\ge1-e_v\quad(0\le h<i). \end{gathered}(9) The zero root detector extension is the family of functionals on all nodes with fr=0f_r=0 and the given functionals at positive-level nodes. For a family fv:Ω→ℝf_v:\Omega\to\mathbb R on a common set Ω\Omega and s∈LNs\in L_N, simultaneous path detection of d∈Ωd\in\Omega is the relation 𝒟f(s,d)\mathcal D_f(s,d) defined in (10): 𝒟f(s,d)⇔faiN(s)(d)≥12for every 1≤i≤N.\mathcal D_f(s,d)\quad\Longleftrightarrow\quad f_{a_i^N(s)}(d)\ge\tfrac12\quad\text{for every }1\le i\le N.(10)✦

The Claim

Theorem 1. Let AA be switching tree data over normalized minimal invariant data (K,T,z)(K,T,z). For every N∈ℕN\in\mathbb N, ∃s∈LN∃d∈BY𝒟f(s,d).\exists s\in L_N\ \exists d\in B_Y\quad\mathcal D_f(s,d).(11)✦

For a general weighted tree evaluation on a convex subset C⊂XC\subset X, let Z⊂XZ\subset X be a real linear subspace containing C−CC-C, and suppose ∥a−c∥≤1\|a-c\|\le1 for all a,c∈Ca,c\in C. Fix N∈ℕN\in\mathbb N, y:LN→Cy:L_N\to C and b∈Cb\in C, continuous linear functionals fv∈X*f_v\in X^* with ∥fv∥≤1\|f_v\|\le1 at every node, and real numbers εv\varepsilon_v for v∈𝒱Nv\in\mathcal V_N. Assume the block detection bounds (12): ∑v∈𝒱Nεv≤1128,π(v)−5εv≤fv(qvbefore−qvafter)(v∈𝒱N).\sum_{v\in\mathcal V_N}\varepsilon_v\le\frac1{128},\qquad \pi(v)-5\varepsilon_v\le f_v\bigl(q_v^{\mathrm{before}}-q_v^{\mathrm{after}}\bigr) \quad(v\in\mathcal V_N).(12) Then a normalized leaf switch vector satisfies ∃s∈LNds∈Z,∥ds∥≤1,𝒟f(s,ds).\exists s\in L_N\quad d_s\in Z,\qquad \|d_s\|\le1,\qquad\mathcal D_f(s,d_s).(13)✦

In the paper, the result reads: for the tree of Proposition 4.1 and every N≥1N\ge1, there are a leaf s∈LNs\in L_N and d∈BYd\in B_Y such that fv(d)≥12f_v(d)\ge\tfrac12 for every nonroot ancestor vv of ss, including ss.

What Is Checked

Assertion (11) is stated over normalized minimal invariant data and switching tree data; (13) is stated over weighted tree evaluations with the subspace and diameter assumptions above and the bounds (12).

The descendant sets in (4) are nonempty at every later level.✦

For 0<t≤10<t\le1, the anchored averaging map in (2) is a strict contraction with factor 1−t1-t✦, and the reciprocal weights satisfy 0<1/n≤10<1/n\le1 for every positive integer nn.