OctoInformBeta

OpenAI preprint, September 2026 · §3. A loss budget for nested idempotents · §3

Proposition 3.3 [Chain bound]: Along nested idempotent diagrams b0,…,bkb_0, \dots, b_k, recurrent classes lost step by step total at most 2|J|2|J| when JJ holds the losses from b0b_0

A chain of nested idempotents loses at most twice its budget.

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

A boundary diagram describes a block of a two-way computation by its passages: each edge enters the block at a label on one side and leaves it at a label on the same side or the other. Gluing blocks side by side multiplies diagrams, and an idempotent diagram ee is a block that is unchanged when doubled. The forward or backward traversals of ee, closed up by its returns at the boundary, carry labels around cycles, and the labels on a common cycle form the recurrent classes of ee.

When ee is replaced by an idempotent dd nested in it, some classes of ee may lose every cycle through their labels; these are the classes missing at dd. The question is how many classes a chain of idempotents b0,b1,…,bkb_0, b_1, \dots, b_k, each nested in the one before, can lose in total, step by step, when everything lost from the top b0b_0 lies in one set JJ. A second statement treats a single step: how the classes lost from ee to dd compare with the classes of ee and of dd that a given set of labels, each carrying a sign, leaves unprotected.

Boundary Diagrams

Relations compose in path order: (x,z)∈QQ′(x,z) \in QQ' when (x,y)∈Q(x,y) \in Q and (y,z)∈Q′(y,z) \in Q' for some yy. The reflexive transitive closure of a relation QQ on a set XX is the relation Q*=⋃n≥0QnQ^* = \bigcup_{n \ge 0} Q^n on XX, where Q0=IXQ^0 = I_X is the identity relation on XX and Qn+1=QnQQ^{n+1} = Q^n Q.✦

A sign σ\sigma is ++ or −-, and D+D^+ and D−D^- are two copies of a set of mm labels. A boundary diagram aa on mm labels is a quadruple of relations: the forward relation Fa⊆D+×D+F_a \subseteq D^+ \times D^+, whose edges enter on the left and exit on the right; the backward relation Ba⊆D−×D−B_a \subseteq D^- \times D^-, whose edges enter on the right and exit on the left; the left relation La⊆D+×D−L_a \subseteq D^+ \times D^-, whose edges enter and exit on the left; and the right relation Ra⊆D−×D+R_a \subseteq D^- \times D^+, whose edges enter and exit on the right.✦ The set of boundary diagrams on mm labels is 𝒯m\mathcal{T}_m.

The product abab of diagrams a,b∈𝒯ma, b \in \mathcal{T}_m is the diagram obtained by gluing aa to the left of bb: Fab=Fa(LbRa)*Fb,Bab=Bb(RaLb)*Ba,Lab=La∪Fa(LbRa)*LbBa,Rab=Rb∪BbRa(LbRa)*Fb.\begin{aligned} F_{ab} &= F_a (L_b R_a)^* F_b, & B_{ab} &= B_b (R_a L_b)^* B_a, \\ L_{ab} &= L_a \cup F_a (L_b R_a)^* L_b B_a, & R_{ab} &= R_b \cup B_b R_a (L_b R_a)^* F_b. \end{aligned}(1)✦ A diagram ee is idempotent when ee=eee = e. The corner of a diagram e∈𝒯me \in \mathcal{T}_m is the set of diagrams z∈𝒯mz \in \mathcal{T}_m with ez=zez = z and ze=zze = z.✦ The nesting order ⊴\trianglelefteq is the relation on 𝒯m\mathcal{T}_m in which d⊴ed \trianglelefteq e when dd and ee are idempotents and de=ed=dde = ed = d.✦

Recurrent, Missing and Unprotected Classes

The through relation TaσT^\sigma_a of a diagram a∈𝒯ma \in \mathcal{T}_m at a sign σ\sigma is the relation on DσD^\sigma of its traversals in the direction of σ\sigma: Ta+=FaT^+_a = F_a and Ta−=BaT^-_a = B_a.✦ The loop closure Λeσ\Lambda^\sigma_e of a diagram e∈𝒯me \in \mathcal{T}_m at a sign σ\sigma is the relation on DσD^\sigma that closes up the alternating returns of ee at the boundary: Λe+=(LeRe)*\Lambda^+_e = (L_e R_e)^* and Λe−=(ReLe)*\Lambda^-_e = (R_e L_e)^*.✦ The recurrence relation of ee at σ\sigma is the relation on DσD^\sigma ρeσ=ΛeσTeσΛeσ.\rho^\sigma_e = \Lambda^\sigma_e \, T^\sigma_e \, \Lambda^\sigma_e .(2)✦

A signed recurrent class of a diagram ee is a pair (σ,C)(\sigma, C) of a sign and a set of labels such that, for some label xx with (x,x)∈ρeσ(x,x) \in \rho^\sigma_e, C={y:(x,y)∈ρeσ and (y,x)∈ρeσ};C = \{\, y : (x,y) \in \rho^\sigma_e \text{ and } (y,x) \in \rho^\sigma_e \,\};(3)✦ the signed recurrent classes of ee form the set 𝒞e\mathcal{C}_e.

For diagrams e,z∈𝒯me, z \in \mathcal{T}_m, the surviving through relation of zz relative to ee at σ\sigma is the relation ΛeσTzσΛeσ\Lambda^\sigma_e T^\sigma_z \Lambda^\sigma_e on DσD^\sigma✦, and a loop of it at a label xx is a pair (x,x)(x,x) in it. The set ℳe(z)\mathcal{M}_e(z) of classes missing from ee at zz is the set of classes of ee none of whose labels carries a loop of the surviving through relation at the class’s sign: ℳe(z)={(σ,C)∈𝒞e:(x,x)∉ΛeσTzσΛeσ for every x∈C}.\mathcal{M}_e(z) = \{\, (\sigma, C) \in \mathcal{C}_e : (x,x) \notin \Lambda^\sigma_e T^\sigma_z \Lambda^\sigma_e \text{ for every } x \in C \,\}.(4)✦

A signed label is a pair (σ,x)(\sigma, x) of a sign and a label. For a diagram e∈𝒯me \in \mathcal{T}_m and a set PP of signed labels, the set 𝒰e(P)\mathcal{U}_e(P) of classes of ee unprotected by PP is the set of classes of ee none of whose labels lies in PP with the class’s sign: 𝒰e(P)={(σ,C)∈𝒞e:(σ,x)∉P for every x∈C}.\mathcal{U}_e(P) = \{\, (\sigma, C) \in \mathcal{C}_e : (\sigma, x) \notin P \text{ for every } x \in C \,\}.(5)✦

The Claim

Theorem 1. (i) Let b0,…,bkb_0, \dots, b_k be idempotent boundary diagrams on mm labels with bj+1⊴bjb_{j+1} \trianglelefteq b_j for 0≤j<k0 \le j < k, and let JJ be a set of pairs of a sign and a set of labels that contains ℳb0(bj)\mathcal{M}_{b_0}(b_j) for 0≤j≤k0 \le j \le k. Then ∑j=1k|ℳbj−1(bj)|≤2|J|.\sum_{j=1}^{k} \bigl|\mathcal{M}_{b_{j-1}}(b_j)\bigr| \le 2|J| .(6)✦

(ii) Let ee be an idempotent boundary diagram on mm labels, dd an idempotent in the corner of ee, and PP a set of signed labels such that every class missing from ee at dd is unprotected by PP. Then 2|𝒰d(P)|+|ℳe(d)|≤2|𝒰e(P)|.2\,|\mathcal{U}_d(P)| + |\mathcal{M}_e(d)| \le 2\,|\mathcal{U}_e(P)| .(7)✦

In the paper, the result reads: if b0,…,bkb_0, \dots, b_k are idempotents with bj⊴bj−1b_j \trianglelefteq b_{j-1} and J0⊆𝒞b0J_0 \subseteq \mathcal{C}_{b_0} is a single set with ℳb0(bj)⊆J0\mathcal{M}_{b_0}(b_j) \subseteq J_0 for 0≤j≤k0 \le j \le k, then ∑j=1k|ℳbj−1(bj)|≤2|J0|\sum_{j=1}^{k} |\mathcal{M}_{b_{j-1}}(b_j)| \le 2|J_0|.

What Is Checked

Both inequalities are stated over boundary diagrams on mm labels under the product (1), with idempotents, the corner of an idempotent and the nesting order, and over the sets ℳe(z)\mathcal{M}_e(z) and 𝒰e(P)\mathcal{U}_e(P) of missing and unprotected classes (4) and (5), cut out of the signed recurrent classes (3) of the recurrence relation (2).