OctoInformBeta

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

§3 (setting): nesting: Boundary diagrams dd and ee are nested, d⊴ed \trianglelefteq e, when both are idempotent and de=ed=dde = ed = d

Nesting of idempotent diagrams is reflexive and transitive.

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 working on a factor of its input may cross the factor from left to right, cross it from right to left, or enter it and turn back to the side it came from. A boundary diagram records such crossings between mm labels on each side of a block, and blocks placed side by side multiply. The item is an order on the idempotent diagrams that compares them through this product alone, much as an idempotent dd of a finite monoid MM is compared with an idempotent ee by asking whether dd lies in the corner eMeeMe.

Diagrams and Their Product

Relations compose in path order: (x,z)∈PQ(x, z) \in PQ when (x,y)∈P(x, y) \in P and (y,z)∈Q(y, z) \in Q for some yy, and IXI_X is the identity relation on a set XX. The reflexive transitive closure P*P^* of a relation PP on XX is the relation on XX given by P*=⋃k≥0Pk,P0=IX,Pk+1=PkP.P^* = \bigcup_{k \ge 0} P^k, \qquad P^0 = I_X, \quad P^{k+1} = P^k P.(1)✦

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, Fa⊆D+×D+,Ba⊆D−×D−,La⊆D+×D−,Ra⊆D−×D+,F_a \subseteq D^+ \times D^+, \quad B_a \subseteq D^- \times D^-, \quad L_a \subseteq D^+ \times D^-, \quad R_a \subseteq D^- \times D^+,(2)✦ the forward relation, whose edges enter on the left and exit on the right, the backward relation, whose edges enter on the right and exit on the left, the left relation, whose edges enter and exit on the left, and the right relation, 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 boundary diagrams a,b∈𝒯ma, b \in \mathcal{T}_m is the boundary diagram obtained by gluing aa to the left of bb, with relations 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}(3)✦ A boundary diagram ee is idempotent when ee=eee = e.

The Claim

Definition 1. Let mm be a natural number. Nesting is the relation on 𝒯m\mathcal{T}_m in which a diagram dd is nested in a diagram ee, written d⊴ed \trianglelefteq e, when dd and ee are idempotent and de=danded=d.de = d \qquad \text{and} \qquad ed = d.(4)✦ Nesting is reflexive on idempotents: if e∈𝒯me \in \mathcal{T}_m is idempotent, then e⊴e.e \trianglelefteq e.(5)✦ Nesting is transitive: if d,e,f∈𝒯md, e, f \in \mathcal{T}_m satisfy d⊴ed \trianglelefteq e and e⊴fe \trianglelefteq f, then d⊴f.d \trianglelefteq f.(6)✦

In the paper, the result reads: for idempotent diagrams dd and ee, d⊴ed \trianglelefteq e if and only if de=ed=dde = ed = d, and ⊴\trianglelefteq is a partial order, distinct from the componentwise edge inclusion ⊑\sqsubseteq of diagrams.

What Is Checked

The claim is stated over the boundary diagrams (2) on mm labels, their product (3), built with the reflexive transitive closure (1), and the nesting relation (4).