OctoInformBeta

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

Lemma 3.2 [Containment of recurrent classes]: For idempotent diagrams d⊴ed \trianglelefteq e, each class of dd contains a class of ee not missing from dd, or two distinct classes of ee

Recurrent classes of a nested idempotent contain outer classes.

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 run of a two-way automaton meets a factor of its input in four ways: it crosses the factor from left to right or from right to left, or it enters and leaves on the same side. Boundary diagrams record these passages as relations on labels and multiply by gluing side by side, as the relations r(w)r(w) of a one-way automaton, the path-order product of the relations of the letters of a word ww, multiply along the word. Each diagram has recurrent classes, sets of labels that its passages join into loops, each class signed by the direction of travel. The item takes two idempotent diagrams dd and ee, with dd nested in ee, and asks which classes of ee lie inside each class of dd, given the classes of ee that go missing when ee is replaced by dd.

Boundary Diagrams

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. The reflexive transitive closure P*P^* of a relation PP on a set XX is the union of its powers PkP^k, k≥0k \ge 0, where P0=IXP^0 = I_X is the identity relation on XX.✦

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 boundary 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_bR_a)^* F_b, & B_{ab} &= B_b (R_aL_b)^* B_a,\\ L_{ab} &= L_a \cup F_a (L_bR_a)^* L_b B_a, & R_{ab} &= R_b \cup B_b R_a (L_bR_a)^* F_b. \end{aligned}(1)✦ An idempotent diagram is a diagram e∈𝒯me \in \mathcal{T}_m with 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; a diagram dd in the corner of ee is nested in ee, written d⊴ed \trianglelefteq e.✦

Recurrent and Missing Classes

A sign σ\sigma is ++ or −-, and DσD^\sigma is the copy of the labels it names. 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.✦ The loop closure Λaσ\Lambda^\sigma_a of aa at σ\sigma is the relation on DσD^\sigma that closes up the alternating left and right returns at a boundary: Ta+=Fa,Ta−=Ba,Λa+=(LaRa)*,Λa−=(RaLa)*.T^+_a = F_a, \quad T^-_a = B_a, \qquad \Lambda^+_a = (L_aR_a)^*, \quad \Lambda^-_a = (R_aL_a)^*.(2)✦

The recurrence relation ρeσ\rho^\sigma_e of a diagram e∈𝒯me \in \mathcal{T}_m at a sign σ\sigma is the relation on DσD^\sigma obtained by closing the through relation of ee with its loop closure on both sides: ρeσ=ΛeσTeσΛeσ.\rho^\sigma_e = \Lambda^\sigma_e \, T^\sigma_e \, \Lambda^\sigma_e.(3)✦ The set 𝒞e\mathcal{C}_e of signed recurrent classes of ee is the set of pairs of a sign and a set of labels given by 𝒞e={(σ,C):C={y:(x,y)∈ρeσ and (y,x)∈ρeσ} for some label x with (x,x)∈ρeσ}.\mathcal{C}_e = \bigl\{ (\sigma, C) : C = \{ y : (x,y) \in \rho^\sigma_e \text{ and } (y,x) \in \rho^\sigma_e \} \text{ for some label } x \text{ with } (x,x) \in \rho^\sigma_e \bigr\}.(4)✦

The surviving relation Ueσ(z)U^\sigma_e(z) of a diagram z∈𝒯mz \in \mathcal{T}_m relative to ee at a sign σ\sigma is the relation on DσD^\sigma obtained by placing the loop closure of ee on both sides of the through relation of zz.✦ The set ℳe(z)\mathcal{M}_e(z) of classes of ee missing from zz is the set of signed recurrent classes of ee whose loops are all lost when ee is replaced by zz: Ueσ(z)=ΛeσTzσΛeσ,ℳe(z)={(σ,C)∈𝒞e:(x,x)∉Ueσ(z) for every x∈C}.U^\sigma_e(z) = \Lambda^\sigma_e \, T^\sigma_z \, \Lambda^\sigma_e, \qquad \mathcal{M}_e(z) = \{ (\sigma, C) \in \mathcal{C}_e : (x,x) \notin U^\sigma_e(z) \text{ for every } x \in C \}.(5)✦

The Claim

Theorem 1 (Containment of recurrent classes). Let ee and dd be idempotent boundary diagrams on mm labels with d⊴ed \trianglelefteq e, and let (σ,C)∈𝒞d(\sigma, C) \in \mathcal{C}_d be a signed recurrent class of dd. Then at least one of the following holds: C′⊆C for some (σ,C′)∈𝒞e\ℳe(d);C1⊆C and C2⊆C for some (σ,C1),(σ,C2)∈𝒞e with C1≠C2.\begin{aligned} &C' \subseteq C \text{ for some } (\sigma, C') \in \mathcal{C}_e \setminus \mathcal{M}_e(d);\\ &C_1 \subseteq C \text{ and } C_2 \subseteq C \text{ for some } (\sigma, C_1), (\sigma, C_2) \in \mathcal{C}_e \text{ with } C_1 \neq C_2. \end{aligned}(6)✦

In the paper, the result reads: for idempotents d⊴ed \trianglelefteq e, every class of 𝒞d\mathcal{C}_d contains either a whole class of 𝒞e\ℳe(d)\mathcal{C}_e \setminus \mathcal{M}_e(d) or two distinct whole classes of 𝒞e\mathcal{C}_e, all classes involved having the same sign.

What Is Checked

The claim (6) is stated over boundary diagrams on mm labels, their product (1) and the corner of a diagram, the through relation and the loop closure (2), the recurrence relation (3) and the signed recurrent classes (4) it defines, and the surviving relation and the classes missing from a diagram (5).