# A tree of predicted outputs

*Written by Claude Opus 5.5 (Anthropic), October 2026. Self-checked by the writing AI. Public domain (CC0).*

We keep the standing data of [Minimal invariant sets and diametral sequences](minimal-invariant-sets-and-diametral-sequences.md) and the point \(x\), the families \(\mathcal G\supseteq\mathcal H_m\) and the points \(b_j=R_j(x)\) of [Resolvents and an anchor point](resolvents-and-an-anchor-point.md). This lesson builds one infinite tree [OpenAI-K, Section 4]. Every node \(v\) carries a map \(G_v\in\mathcal G\), the point \(y_v=G_v(x)\), a positive weight, and, away from the root, a functional \(f_v\) of norm at most \(1\). The tree defines a nonlinear "evaluation": given points at the nodes of one level, each parent applies its map to the weighted average of its children's points, up to the root. In the lesson [Kirk's problem](kirks-problem.md), the points at the bottom level are replaced one at a time by a common point, and the functional \(f_v\) has to detect the resulting change of the root output when the block of leaves below \(v\) switches. The difficulty is that \(f_v\) must be chosen before the weights of \(v\) and its siblings are known. It is chosen to work for a whole compact family of *predicted* root outputs, parametrized by the possible weights (Section 2).

We use: Lemmas 3.1 and 3.3 of the first lesson; from the second lesson, Lemma 2.1, (2.2), Lemma 6.1 and Lemma 6.2; Lemma 1.2 of the first lesson (limits along \(\mathcal U\)) and Mazur's theorem.

## 1. Evaluation on an ordered tree

An *ordered tree* here has a root \(r\) and levels \(L_0=\{r\},L_1,L_2,\dots\), each finite and nonempty. Every node has a finite nonempty ordered list of children in the next level, and \(L_{k+1}\) is ordered by listing the children of the nodes of \(L_k\) in the order of their parents. Write \(\hat v\) for the parent of \(v\), \(p\prec v\) when \(p\) is a proper ancestor of \(v\), and \(p\preceq v\) when \(p\prec v\) or \(p=v\). For \(v\in L_k\) and \(N\ge k\), the set \(B_N(v)=\{s\in L_N:v\preceq s\}\) is a consecutive block of \(L_N\).

Each node \(v\) carries a map \(G_v\in\mathcal G\) and the point \(y_v=G_v(x)\in K\), with \(G_r=\mathrm{Id}\) and \(y_r=x\). Each nonroot node carries a weight \(\alpha_v>0\), and the weights of the children of every node sum to \(1\). The *path weights* are \(W_r=1\) and \(W_v=W_{\hat v}\alpha_v\).

If points \(H_v\in K\) are given at the children of a node \(u\), its *output* is
\[
\begin{aligned}
&H_u\\
&\quad =G_u\Bigl(\sum_{\hat v=u}\alpha_vH_v\Bigr)\in K.
\end{aligned}\tag{1.1}
\]
For points \((H_v)_{v\in L_k}\) prescribed on one level, let \(\Phi_k((H_v)_{v\in L_k})\) be the root output obtained by applying (1.1) at all levels above \(L_k\); the maps of the nodes of \(L_k\) are not applied. So \(\Phi_0(H_r)=H_r\).

**Lemma 1.1.** (a) \(\sum_{v\in L_k}W_v=1\), and \(\sum_{s\in B_N(v)}W_s=W_v\).

(b) For outputs \((H_v)\) and \((H'_v)\) prescribed on \(L_k\),
\[
\begin{aligned}
&\bigl\|\Phi_k((H_v))-\Phi_k((H'_v))\bigr\|\\
&\quad \le\sum_{v\in L_k}W_v\|H_v-H'_v\|.
\end{aligned}\tag{1.2}
\]

**Proof.** (a) The weights of the children of \(u\) sum to \(1\), so the path weights of the children of \(u\) sum to \(W_u\); induction on the level. (b) At a node \(u\), since \(G_u\) is nonexpansive, the difference of the outputs is at most \(\sum_{\hat v=u}\alpha_v\|H_v-H'_v\|\). Induction up the tree multiplies the weights along each path. \(\square\)

In particular, changing only the output at \(v\in L_k\) changes the root output by at most \(W_v\) times the change at \(v\), and the root changes by at most the largest change on the level.

## 2. Predicted root outputs

The tree is built level by level, and the nodes of a level \(k\ge1\) are chosen one at a time as *candidates*: parent by parent from left to right, and for each parent in the order of selection. Some candidates are later discarded. When a candidate \(v\) of level \(k\) is about to be chosen, all levels above \(k\) are complete, with their maps and weights. Let \(I_v\) be the list of the candidates of level \(k\) selected before \(v\), retained or discarded; for \(h\in I_v\) we know its point \(y_h\) and its parent \(\hat h\in L_{k-1}\). Let \(\Theta_v\) be the set of families \((\theta_h)_{h\in I_v}\) with \(\theta_h\ge0\) and \(\sum_{h\in I_v,\ \hat h=p}\theta_h\le1\) for every \(p\in L_{k-1}\),
a compact subset of a finite-dimensional space (a single point if \(I_v\) is empty). For \(b\in K\), \(\theta\in\Theta_v\) and \(p\in L_{k-1}\) define \(a_{v,p}(b;\theta)\) and \(Q_v(b;\theta)\) by (2.1):
\[
\begin{aligned}
&a_{v,p}(b;\theta)=b+\sum_{h\in I_v,\ \hat h=p}\theta_h(y_h-b),\\
&Q_v(b;\theta)\\
&\quad=\Phi_{k-1}\Bigl(\bigl(G_p(a_{v,p}(b;\theta))\bigr)_{p\in L_{k-1}}\Bigr).
\end{aligned}
\]
Each \(a_{v,p}(b;\theta)\) is a convex combination of \(b\) and points \(y_h\), so it lies in \(K\). The point \(Q_v(b;\theta)\) is the root output when, below each parent \(p\), the earlier candidates \(h\) have outputs \(y_h\) and weights \(\theta_h\), and all other children of \(p\) have the common output \(b\). It involves only the levels above \(k\), which are complete.

**Lemma 2.1.** \(\|Q_v(b;\theta)-Q_v(b;\eta)\|\le\sum_{h\in I_v}|\theta_h-\eta_h|\) for all \(b\in K\) and \(\theta,\eta\in\Theta_v\).

**Proof.** \(\|a_{v,p}(b;\theta)-a_{v,p}(b;\eta)\|\) is at most \(\sum_{\hat h=p}|\theta_h-\eta_h|\,\|y_h-b\|\), which is at most \(\sum_{\hat h=p}|\theta_h-\eta_h|\), since \(\operatorname{diam}K=1\). Apply the nonexpansive maps \(G_p\) and (1.2), with \(W_p\le1\). \(\square\)

For \(\theta\in\Theta_v\) let
\[
\begin{aligned}
&Z_v(\theta)\\
&\quad =\lim_{j\to\mathcal U}Q_v(b_j;\theta)\quad\text{(weak limit in }K\text{)},\\
&E_v=\{z_1,\dots,z_k\}\cup Z_v(\Theta_v).
\end{aligned}
\]

**Lemma 2.2.** \(\|Z_v(\theta)-Z_v(\eta)\|\le\sum_{h\in I_v}|\theta_h-\eta_h|\). Hence \(Z_v\) is norm continuous and \(E_v\) is a nonempty norm-compact subset of \(K\), determined before \(v\) is chosen.

**Proof.** The weak limit along \(\mathcal U\) of \(Q_v(b_j;\theta)-Q_v(b_j;\eta)\) is \(Z_v(\theta)-Z_v(\eta)\), since for every \(\ell\in X^*\) the real limits along \(\mathcal U\) are additive. The closed ball of radius \(\sum_h|\theta_h-\eta_h|\) about \(0\) is weakly closed and contains all these differences by Lemma 2.1, so it contains the limit. A continuous image of the compact set \(\Theta_v\) is compact. \(\square\)

The weak limit is taken of points already computed; no weak limit is passed through a nonlinear map.

## 3. The construction

**Proposition 3.1.** Under the standing assumptions there is an infinite ordered tree with maps, points and weights as in Section 1, and with numbers \(e_v>0\) and functionals \(f_v\in X^*\), \(\|f_v\|\le1\), at the nonroot nodes, such that:

(a) \(\sum_{v\neq r}e_v\le\frac1{128}\);

(b) with \(\tau_0=\frac12\) and \(\tau_k=2^{-k-1}\min\{e_u:u\in L_1\cup\dots\cup L_k\}\) for \(k\ge1\), every \(u\in L_k\) satisfies
\[
\Bigl\|\sum_{\hat v=u}\alpha_vy_v-x\Bigr\|\le\tau_k;\tag{3.1}
\]
(c) every nonroot node \(v\) satisfies
\[
\begin{aligned}
&\sum_{p\prec v}\|G_p(y_v)-y_v\|\\
&\quad \le e_v,\\
&f_v(y_v-z)\ge1\\
&\quad -e_v\quad(z\in E_v),
\end{aligned}\tag{3.2}
\]
where \(E_v\) is the set of Section 2, formed from the candidates selected before \(v\).

**Proof.** Number all candidate selections in the whole construction \(\ell=1,2,\dots\), discarded candidates included, and give the \(\ell\)-th candidate the number \(e_v=2^{-\ell-8}\) when it is about to be selected. The sum of all these numbers is at most \(2^{-8}\), which gives (a).

Suppose the levels \(L_0,\dots,L_{k-1}\) are complete and \(\tau_{k-1}\) is defined. Treat the parents \(u\in L_{k-1}\) from left to right. For \(u\), run the adaptive selection of Lemma 6.1 of the second lesson with tolerance \(\tau_{k-1}\); its successive choices are the candidates for the children of \(u\). Before each choice we prescribe the precision as follows. Let \(v\) be the next candidate, with its number \(e_v\). Form \(I_v\), \(\Theta_v\), \(Q_v\) and \(E_v\) as in Section 2. By Lemma 3.3 of the first lesson, there is \(\delta_v>0\) such that every \(y\in K\) with \(\|Ty-y\|\le\delta_v\) has \(f\in X^*\), \(\|f\|\le1\), with \(f(y-z)\ge1-e_v\) for all \(z\in E_v\). The ancestors of \(v\) are fixed, so \(C_v=\sum_{p\prec v}c_{G_p}\) is a finite number (Lemma 2.1 of the second lesson, \(c_{\mathrm{Id}}=0\)). Prescribe an integer \(m\) with \(\frac1m<\delta_v\) and \(\frac{C_v}m\le e_v\). The selection then chooses \(G_v\in\mathcal H_m\), and \(y_v=G_v(x)\) satisfies \(\|Ty_v-y_v\|\le\frac1m\) by (2.2) of the second lesson. Hence
\[
\begin{aligned}
&\sum_{p\prec v}\|G_p(y_v)-y_v\|\\
&\quad \le\sum_{p\prec v}c_{G_p}\|Ty_v-y_v\|\le\frac{C_v}m\le e_v,
\end{aligned}
\]
and there is \(f_v\) as in (3.2); choose it.

The selection for \(u\) stops after finitely many candidates with convex coefficients as in (6.1) of the second lesson, with tolerance \(\tau_{k-1}\). Only now are these coefficients fixed. The candidates with coefficient \(0\) are discarded; the others, in their order of selection, are the children of \(u\), and their coefficients are their weights \(\alpha_v\). This gives (3.1) for \(u\). Discarded candidates stay in the lists \(I\) of later candidates, so nothing already chosen changes. When all parents in \(L_{k-1}\) are treated, the level \(L_k\) is complete, finite and nonempty, and \(\tau_k\) is defined. Continuing level by level constructs the tree. \(\square\)

The numbers \(e_v\) are *budgets*: the construction keeps every error committed at \(v\) below \(e_v\), and the budgets are summable.

## 4. Ideal cutoffs

When the level \(L_k\) is complete, every retained \(v\in L_k\) determines \(\theta^v\in\Theta_v\): \(\theta^v_h=\alpha_h\) if the earlier candidate \(h\) was retained, and \(\theta^v_h=0\) if it was discarded. The sums over a parent group are at most \(1\). Write \(h<_kv\) if \(h\) precedes \(v\) in \(L_k\); these are exactly the retained candidates of level \(k\) selected before \(v\). For \(b\in K\) define the *ideal cutoff* outputs on \(L_k\):
\[
\widetilde H^{v,b}_h=\begin{cases}y_h,&h<_kv,\\ b,&h=v\text{ or }v<_kh.\end{cases}
\]

**Lemma 4.1.** \(\Phi_k\bigl((\widetilde H^{v,b}_h)_{h\in L_k}\bigr)=Q_v(b;\theta^v)\).

**Proof.** For \(p\in L_{k-1}\),
\[
\begin{aligned}
&\sum_{\hat h=p}\alpha_h\widetilde H^{v,b}_h=\sum_{\hat h=p,\ h<_kv}\alpha_hy_h\\
&\quad +\Bigl(1-\sum_{\hat h=p,\ h<_kv}\alpha_h\Bigr)b=a_{v,p}(b;\theta^v),
\end{aligned}
\]
because the weights of the children of \(p\) sum to \(1\) and the discarded candidates have \(\theta^v_h=0\). Applying \(G_p\) and then the evaluation above level \(k-1\) gives \(Q_v(b;\theta^v)\). \(\square\)

In a parent group before that of \(v\), every child has its point \(y_h\); in the group of \(v\), the earlier siblings have \(y_h\) and the remaining weight goes to \(b\); in every later group all outputs are \(b\), whatever its children and weights are. This is why the prediction \(Q_v\) could be formed before those later children and their weights existed: the compact set \(E_v\) covers all possible values of the parameter, and the actual one is \(\theta^v\).

## 5. Exercises

**Exercise 5.1** (easy). Show that the order of the children within a parent group and the order of the parent groups are both used in Lemma 4.1, and describe the ideal cutoff when \(v\) is the first node of \(L_k\) and when it is the last.

**Exercise 5.2** (easy). Show that \(\tau_k\le2^{-k-1}e_v\) for every \(v\in L_1\cup\dots\cup L_k\), and that \(\sum_{d\ge k}\tau_d\) is at most \(2^{-k}\) times the least \(e_u\) with \(u\in L_1\cup\dots\cup L_k\).

**Exercise 5.3** (medium). Explain why the functional \(f_v\) cannot simply be chosen after the weights of the siblings of \(v\) are fixed: which property of the adaptive selection would be lost?

## 6. Solutions

**5.1.** The ideal cutoff gives \(y_h\) exactly to the nodes preceding \(v\) in \(L_k\), which are the earlier siblings of \(v\) and all nodes in earlier parent groups. If \(v\) is the first node of \(L_k\), every output is \(b\), and \(Q_v(b;\theta^v)=\Phi_{k-1}((G_p(b))_p)\). If \(v\) is the last, every node before it keeps \(y_h\).

**5.2.** \(\tau_k=2^{-k-1}\min\{e_u\}\le2^{-k-1}e_v\). For \(d\ge k\), the minimum defining \(\tau_d\) is over a larger set, so \(\tau_d\le2^{-d-1}\min_{u\in L_1\cup\dots\cup L_k}e_u\), and \(\sum_{d\ge k}2^{-d-1}=2^{-k}\).

**5.3.** The compact detector (Lemma 3.3 of the first lesson) needs the set \(E\) to fix the precision \(\delta\), and the precision must be imposed when \(y_v\) is chosen; it cannot be increased afterwards. The actual parameter \(\theta^v\), and with it the point \(Z_v(\theta^v)\) that \(f_v\) must detect, depends on weights that are fixed only after \(v\) and its later siblings are chosen. Choosing \(f_v\) later does not help, since \(y_v\) is already fixed. Taking \(E_v\) to contain \(Z_v(\theta)\) for every \(\theta\in\Theta_v\) makes the precision independent of the future weights.

## References

- [OpenAI-K] OpenAI, *Fixed points of nonexpansive maps in reflexive Banach spaces*, OpenAI Math Release preprint, 24 September 2026, Section 4. https://github.com/openai/math/blob/main/preprints/Fixed-Points-of-Nonexpansive-Maps-in-Reflexive-Banach-Spaces-September-24-2026