OctoInformBeta

OpenAI preprint, September 2026 · §2. Path diagrams and missing recurrent classes · §2

Lemma 2.5 [Rectangles of through edges]: Each recurrent class gives one; it survives in a nested zz unless the class is missing, so ℳe(z)=∅\mathcal{M}_e(z)=\emptyset gives e⊑ze\sqsubseteq z

Through edges of an idempotent diagram ee come in rectangles.

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 block of its tape enters and leaves the block through its two boundaries, possibly many times. A boundary diagram records such crossings as edges between labels at the two boundaries, and gluing two blocks side by side multiplies their diagrams. For an idempotent diagram ee, the question is how the edges that cross ee from one boundary to the other are grouped by the labels at which such crossings recur, and which of these edges a diagram zz in the corner of ee must keep.

Diagrams and Their Product

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 aa and bb is the diagram obtained by gluing aa to the left of bb. With relations composed in path order, and with P*=⋃k≥0PkP^* = \bigcup_{k \ge 0} P^k the reflexive transitive closure of a relation PP, where P0P^0 is the identity, its relations are 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)✦

The corner of a diagram ee is the set of diagrams zz nested in ee, written z⊴ez \trianglelefteq e: those with ez=zez = z and ze=zze = z.✦

Edge inclusion is the relation ⊑\sqsubseteq on 𝒯m\mathcal{T}_m under which a⊑ba \sqsubseteq b when Fa⊆FbF_a \subseteq F_b, Ba⊆BbB_a \subseteq B_b, La⊆LbL_a \subseteq L_b and Ra⊆RbR_a \subseteq R_b.✦

Recurrent Classes and Rectangles

A sign σ\sigma is one of ++ and −-, and DσD^\sigma is the corresponding copy of the label set. The through relation TaσT_a^\sigma of a diagram aa at a sign σ\sigma is the relation on DσD^\sigma of its through edges in the direction of σ\sigma: Ta+=FaT_a^+ = F_a and Ta−=BaT_a^- = B_a.✦ The loop closure KeσK_e^\sigma of a diagram ee at σ\sigma is the relation on DσD^\sigma that closes up the alternating returns at a boundary: Ke+=(LeRe)*K_e^+ = (L_e R_e)^* and Ke−=(ReLe)*K_e^- = (R_e L_e)^*.✦ The recurrence relation QeσQ_e^\sigma of ee at σ\sigma, and the surviving relation Ueσ(z)U_e^\sigma(z) of a second diagram zz relative to ee at σ\sigma, are the relations on DσD^\sigma Qeσ=KeσTeσKeσ,Ueσ(z)=KeσTzσKeσ.Q_e^\sigma = K_e^\sigma T_e^\sigma K_e^\sigma, \qquad U_e^\sigma(z) = K_e^\sigma T_z^\sigma K_e^\sigma.(2)

A label xx is recurrent for ee at σ\sigma when (x,x)∈Qeσ(x,x) \in Q_e^\sigma. The set 𝒞e\mathcal{C}_e of signed recurrent classes of ee consists of the pairs (σ,C)(\sigma, C) of a sign σ\sigma and a set CC of labels such that, for some label xx recurrent at σ\sigma, C={y:(x,y)∈Qeσ and (y,x)∈Qeσ}.C = \{\, y : (x,y) \in Q_e^\sigma \text{ and } (y,x) \in Q_e^\sigma \,\}.(3)✦ The set ℳe(z)⊆𝒞e\mathcal{M}_e(z) \subseteq \mathcal{C}_e of classes missing after ee is replaced by a diagram zz consists of the classes (σ,C)(\sigma, C) of ee such that no label x∈Cx \in C has (x,x)∈Ueσ(z)(x,x) \in U_e^\sigma(z).✦

The rectangle of ee at a sign σ\sigma and a label pp is the relation Aeσ(p)×Beσ(p)A_e^\sigma(p) \times B_e^\sigma(p) on DσD^\sigma, where Aeσ(p)={u:(u,p)∈TeσKeσ},Beσ(p)={v:(p,v)∈KeσTeσ}.A_e^\sigma(p) = \{\, u : (u,p) \in T_e^\sigma K_e^\sigma \,\}, \qquad B_e^\sigma(p) = \{\, v : (p,v) \in K_e^\sigma T_e^\sigma \,\}.(4)✦

The Claim

Theorem 1. Let ee be a diagram on mm labels and σ\sigma a sign.

  1. If ee is idempotent, then for every label pp Aeσ(p)×Beσ(p)⊆Teσ.A_e^\sigma(p) \times B_e^\sigma(p) \subseteq T_e^\sigma.(5)✦

  2. If ee is idempotent and pp and qq are labels with (p,q)(p,q) and (q,p)(q,p) in QeσQ_e^\sigma, then Aeσ(p)×Beσ(p)=Aeσ(q)×Beσ(q).A_e^\sigma(p) \times B_e^\sigma(p) = A_e^\sigma(q) \times B_e^\sigma(q).(6)✦

  3. If ee is idempotent, then Teσ⊆⋃p:(p,p)∈QeσAeσ(p)×Beσ(p).T_e^\sigma \subseteq \bigcup_{p \,:\, (p,p) \in Q_e^\sigma} A_e^\sigma(p) \times B_e^\sigma(p).(7)✦

  4. If zz is a diagram nested in ee and pp is a label with (p,p)∈Ueσ(z)(p,p) \in U_e^\sigma(z), then Aeσ(p)×Beσ(p)⊆Tzσ.A_e^\sigma(p) \times B_e^\sigma(p) \subseteq T_z^\sigma.(8)✦

  5. If ee is idempotent and zz is a diagram nested in ee with ℳe(z)=∅\mathcal{M}_e(z) = \emptyset, then e⊑z.e \sqsubseteq z.(9)✦

In the paper, the result reads: for idempotent ee and zz in the corner e𝒯mee\mathcal{T}_me of ee, the rectangle AC×BC={u:(u,p)∈FeKe+}×{v:(p,v)∈Ke+Fe}A_C \times B_C = \{u : (u,p) \in F_e K_e^+\} \times \{v : (p,v) \in K_e^+ F_e\} of a positive class (+,C)(+, C) and a label p∈Cp \in C is independent of pp and contained in FeF_e, these rectangles cover FeF_e, the rectangle of a class (+,C)∉ℳe(z)(+, C) \notin \mathcal{M}_e(z) lies in FzF_z, reflected statements hold for negative classes, and in particular ℳe(z)=∅\mathcal{M}_e(z) = \emptyset implies e⊑ze \sqsubseteq z. The box indexes rectangles by labels rather than by classes.

What Is Checked

The claims (5) through (9) are stated over boundary diagrams on mm labels, their product (1) with the reflexive transitive closure it uses, the corner of a diagram, edge inclusion, the through relations and loop closures, the recurrence and surviving relations (2), the signed recurrent classes (3), the missing classes and the rectangles (4).