OctoInformBeta

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

Lemma 2.6 [Transport]: For idempotents ee and d=uevd = uev, at most 2|J|2|J| classes cover ℳd(uzv)\mathcal{M}_d(uzv) for all z⊴ez \trianglelefteq e with ℳe(z)⊆J⊆𝒞e\mathcal{M}_e(z) \subseteq J \subseteq \mathcal{C}_e

Missing recurrent classes pass through a context at most doubled.

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

Cut the tape of a two-way automaton around a factor. A run segment inside the factor enters across one of its two boundaries and leaves across one, and the rest of the tape sees the factor only through which crossings such segments join. A boundary diagram on mm labels keeps this record on two copies D+D^+ and D−D^- of an mm-element label set, with a label in D+D^+ for a crossing to the right and a label in D−D^- for a crossing to the left; the diagrams of two adjacent factors multiply by gluing.

Fix an idempotent diagram ee. Its signed recurrent classes, defined below, are sets of labels that its recurrence relation, also defined below, ties into loops, and replacing ee by a diagram zz of its corner, the set of diagrams nested in ee, can lose every loop of a class, which is then missing at zz. Put ee in a context: diagrams uu and vv with uev=duev = d idempotent as well, so that replacing ee by zz turns dd into uzvuzv. The question is how the classes of dd missing at uzvuzv are controlled by those of ee missing at zz, uniformly in zz. For a set JJ of classes of ee, the theorem below answers it by a set of at most 2|J|2|J| classes of dd, and it also gives a containment in, and a size bound for, an explicit set of classes of dd marked by JJ, defined below.

Diagrams and Recurrent Classes

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.

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 the reflexive transitive closure of a relation PP on a set XX is P*=⋃k≥0PkP^* = \bigcup_{k \ge 0} P^k, with P0=IXP^0 = I_X the identity relation on XX. The product abab of 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_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)✦

A diagram ee is idempotent when ee=eee = e. A diagram zz is nested in ee, written z⊴ez \trianglelefteq e, when ez=z=zeez = z = ze, and the corner of ee is the set of diagrams nested in ee, written e𝒯mee\mathcal{T}_m e when ee is idempotent.✦

A sign σ\sigma is ++ or −-, and −σ-\sigma is the opposite sign. At a sign σ\sigma, the through relation TaσT^\sigma_a of a diagram aa is its traversal in the direction of σ\sigma✦, and its loop closure Λaσ\Lambda^\sigma_a closes up the alternating returns at a boundary; both are relations on DσD^\sigma: 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 QeσQ^\sigma_e of ee and the surviving relation Ueσ(z)U^\sigma_e(z) of a diagram zz relative to ee place the loop closure of ee on both sides of a through relation: Qeσ=ΛeσTeσΛeσ,Ueσ(z)=ΛeσTzσΛeσ.Q^\sigma_e = \Lambda^\sigma_e\, T^\sigma_e\, \Lambda^\sigma_e, \qquad U^\sigma_e(z) = \Lambda^\sigma_e\, T^\sigma_z\, \Lambda^\sigma_e.(3)

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 for which some label xx with (x,x)∈Qeσ(x,x) \in Q^\sigma_e has C={y:(x,y)∈Qeσ and (y,x)∈Qeσ}C = \{y : (x,y) \in Q^\sigma_e \text{ and } (y,x) \in Q^\sigma_e\}. For a diagram zz, the set ℳe(z)\mathcal{M}_e(z) of classes of ee missing at zz holds the classes whose loops are all lost when ee is replaced by zz: ℳe(z)={(σ,C)∈𝒞e:(x,x)∉Ueσ(z) for every x∈C}.\mathcal{M}_e(z) = \{(\sigma, C) \in \mathcal{C}_e : (x,x) \notin U^\sigma_e(z) \text{ for every } x \in C\}.(4)✦

The Marked Classes

Fix diagrams ee, dd, uu and vv in 𝒯m\mathcal{T}_m. A port is a pair (s,x)(s,x) of a sign and a label. The port relation PeP_e of ee relates the port (s,x)(s,x) to the port (t,y)(t,y) when (x,y)(x,y) lies in LeL_e, FeF_e, BeB_e or ReR_e according as (s,t)(s,t) is (−,−)(-,-), (−,+)(-,+), (+,−)(+,-) or (+,+)(+,+): it reads ee as one relation from entry ports to exit ports, with the negative ports on its left boundary and the positive ones on its right.✦

For relations RR and LL on the labels, the bounce relation β(R,L)\beta(R,L) on ports keeps the sign and moves the label by LL at a positive port and by RR at a negative one.✦ Write β=β(Ru,Lv)\beta = \beta(R_u, L_v); a step of β\beta is a return into ee off vv on the right of ee or off uu on the left of ee.

The recurrent rectangle of ee at a label pp and a sign σ\sigma is the relation on labels Recteσ(p)={x:(x,p)∈TeσΛeσ}×{y:(p,y)∈ΛeσTeσ}.\mathrm{Rect}^\sigma_e(p) = \{x : (x,p) \in T^\sigma_e \Lambda^\sigma_e\} \times \{y : (p,y) \in \Lambda^\sigma_e T^\sigma_e\}.(5) The class rectangle KcK_c of a pair c=(σ,C)c = (\sigma, C) of a sign and a set of labels relates the port (−σ,x)(-\sigma, x) to the port (σ,y)(\sigma, y) when (x,y)∈Recteσ(p)(x,y) \in \mathrm{Rect}^\sigma_e(p) for some p∈Cp \in C.✦

At a sign σ\sigma, the context entry relation EσE^\sigma, from labels to ports, and the context exit relation XσX^\sigma, from ports to labels, pass through the loop closure of dd and a traversal of uu or vv: E+={(x,(−,y)):(x,y)∈Λd+Fu},E−={(x,(+,y)):(x,y)∈Λd−Bv},X+={((+,y),x):(y,x)∈FvΛd+},X−={((−,y),x):(y,x)∈BuΛd−}.\begin{aligned} E^+ &= \{(x, (-,y)) : (x,y) \in \Lambda^+_d F_u\}, & E^- &= \{(x, (+,y)) : (x,y) \in \Lambda^-_d B_v\},\\ X^+ &= \{((+,y), x) : (y,x) \in F_v \Lambda^+_d\}, & X^- &= \{((-,y), x) : (y,x) \in B_u \Lambda^-_d\}. \end{aligned}(6) The class influence relation Γcσ\Gamma^\sigma_c of a pair cc at σ\sigma is the relation on labels following a path from the context through cc and back, with any number of returns off uu and vv on either side of cc: Γcσ=Eσ(Peβ)*Kc(βPe)*Xσ.\Gamma^\sigma_c = E^\sigma\, (P_e\beta)^*\, K_c\, (\beta P_e)^*\, X^\sigma.(7)✦

The set Jˆ\widehat J of classes of dd marked by a set JJ of pairs of a sign and a set of labels consists of the classes (σ,D)(\sigma, D) of dd with a label on a loop of the class influence relation at σ\sigma of some pair of JJ: Jˆ={(σ,D)∈𝒞d:(x,x)∈Γcσ for some c∈J and some x∈D}.\widehat J = \{(\sigma, D) \in \mathcal{C}_d : (x,x) \in \Gamma^\sigma_c \text{ for some } c \in J \text{ and some } x \in D\}.(8)✦

The Claim

Theorem 1. Let ee and dd be idempotent diagrams in 𝒯m\mathcal{T}_m, and let uu and vv be diagrams with uev=duev = d.

(i) For every set J⊆𝒞eJ \subseteq \mathcal{C}_e there is a set J′⊆𝒞dJ' \subseteq \mathcal{C}_d with |J′|≤2|J||J'| \le 2|J| such that every z∈e𝒯mez \in e\mathcal{T}_m e with ℳe(z)⊆J\mathcal{M}_e(z) \subseteq J and uzv∈d𝒯mduzv \in d\mathcal{T}_m d satisfies ℳd(uzv)⊆J′.\mathcal{M}_d(uzv) \subseteq J'.(9)✦

(ii) For every set JJ of pairs of a sign and a set of labels, every z∈e𝒯mez \in e\mathcal{T}_m e with ℳe(z)⊆J\mathcal{M}_e(z) \subseteq J satisfies ℳd(uzv)⊆Jˆ.\mathcal{M}_d(uzv) \subseteq \widehat J.(10)✦

(iii) For every set J⊆𝒞eJ \subseteq \mathcal{C}_e, |Jˆ|≤2|J|.|\widehat J| \le 2|J|.(11)✦

In the paper, the result reads: for idempotents ee and dd and diagrams uu and vv with uev=duev = d, every J⊆𝒞eJ \subseteq \mathcal{C}_e has a single J′⊆𝒞dJ' \subseteq \mathcal{C}_d with |J′|≤2|J||J'| \le 2|J| such that ℳd(uzv)⊆J′\mathcal{M}_d(uzv) \subseteq J' for every z∈e𝒯mez \in e\mathcal{T}_m e with ℳe(z)⊆J\mathcal{M}_e(z) \subseteq J and uzv∈d𝒯mduzv \in d\mathcal{T}_m d.

What Is Checked

The claim is stated over boundary diagrams on mm labels with the gluing product (1), the idempotents and corners of that product, the recurrent classes and the missing classes (4) built from the relations (3), and the marked classes (8) built from the class influence relations (7).