OctoInformBeta

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

Lemma 3.1 [Absorption under nesting]: For boundary diagrams dd nested in ee and either sign, with ee’s through relation absorbed too and ee’s loop closure inside dd’s

A nested diagram’s recurrent relation absorbs the outer diagram’s.

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 two-way automaton reading a block of its tape can cross the block in either direction, or enter it and come back out at the end it came in by. A boundary diagram records how these passages connect labels at the two ends of the block, with one copy of the labels for passages moving right and one for passages moving left, and gluing two blocks side by side multiplies their diagrams.

The item compares two boundary diagrams dd and ee, with dd nested in ee (the product with ee on either side leaves dd unchanged), through two relations on one copy of the labels: the loop closure, which closes up returns at the two ends taken alternately, and the recurrent relation, a crossing preceded and followed by such returns. The question is whether the loop closure of ee lies in that of dd, and whether the recurrent relation of dd absorbs the recurrent relation and the crossings of ee composed with it on either side.

Boundary Diagrams

Relations compose in path order: (x,z)∈UV(x, z) \in UV when (x,y)∈U(x, y) \in U and (y,z)∈V(y, z) \in V for some yy. The reflexive transitive closure of a relation UU on a set XX is the relation U*=⋃k≥0UkU^* = \bigcup_{k \ge 0} U^k on XX, where U0=IXU^0 = I_X is the identity relation on XX and Uk+1=UkUU^{k+1} = U^k U.✦

A boundary diagram aa on mm labels is a quadruple of relations on two copies D+D^+ and D−D^- of an mm-element label set: 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 two 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 d∈𝒯md \in \mathcal{T}_m is nested in a diagram e∈𝒯me \in \mathcal{T}_m, written d⊴ed \trianglelefteq e, when the product with ee on either side leaves dd unchanged: de=ed=d.de = ed = d.(2)✦ The corner of ee is the set of diagrams nested in ee.✦

Relations at a Sign

A sign σ\sigma is ++ or −-. The through relation TaσT_a^{\sigma} 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: the forward relation Ta+=FaT_a^{+} = F_a and the backward relation Ta−=BaT_a^{-} = B_a.✦

The loop closure KaσK_a^{\sigma} of aa at σ\sigma is the relation on DσD^{\sigma} given by Ka+=(LaRa)*,Ka−=(RaLa)*.K_a^{+} = (L_a R_a)^*, \qquad K_a^{-} = (R_a L_a)^*.(3)✦

The recurrent relation PaσP_a^{\sigma} of a diagram a∈𝒯ma \in \mathcal{T}_m at a sign σ\sigma is the relation on DσD^{\sigma} obtained by closing the through relation of aa at σ\sigma with the loop closure of aa at σ\sigma on both sides: Paσ=KaσTaσKaσ.P_a^{\sigma} = K_a^{\sigma} T_a^{\sigma} K_a^{\sigma}.(4)✦

The Claim

Theorem 1. Let dd and ee be boundary diagrams on mm labels with d⊴ed \trianglelefteq e, and let σ\sigma be a sign. Then Keσ⊆Kdσ,K_e^{\sigma} \subseteq K_d^{\sigma},(5)✦ PeσPdσ⊆PdσandPdσPeσ⊆Pdσ,P_e^{\sigma} P_d^{\sigma} \subseteq P_d^{\sigma} \quad\text{and}\quad P_d^{\sigma} P_e^{\sigma} \subseteq P_d^{\sigma},(6)✦ and TeσPdσ⊆PdσandPdσTeσ⊆Pdσ.T_e^{\sigma} P_d^{\sigma} \subseteq P_d^{\sigma} \quad\text{and}\quad P_d^{\sigma} T_e^{\sigma} \subseteq P_d^{\sigma}.(7)✦

In the paper, the result reads: for idempotents d⊴ed \trianglelefteq e and either sign, Ke⊆KdK_e \subseteq K_d, PePd⊆PdP_e P_d \subseteq P_d and PdPe⊆PdP_d P_e \subseteq P_d, and in the positive sign FePd+⊆Pd+F_e P_d^{+} \subseteq P_d^{+} and Pd+Fe⊆Pd+P_d^{+} F_e \subseteq P_d^{+}, with BeB_e in place of FeF_e for the negative sign, KK and PP being written there without their sign.

The statement asks of dd and ee only that d⊴ed \trianglelefteq e, and so covers nested idempotents.

What Is Checked

The claim is stated over boundary diagrams on mm labels, their product (1) with the reflexive transitive closure in it, the nesting (2), and the through relation, the loop closure (3) and the recurrent relation (4) of a diagram at a sign.