OctoInformBeta

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

§2.3 (setting): recurrent classes, corners and missing sets: At most 2m2m signed classes, and for zz in the corner, the loops of a class survive at all its labels or at none

Recurrent classes of an idempotent diagram and its missing sets.

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 can cross a block of its tape many times in one run, entering the block on the left or on the right and leaving it on either side. Boundary diagrams record such crossings. A boundary diagram aa on mm labels is a quadruple (Fa,Ba,La,Ra)(F_a, B_a, L_a, R_a) 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^+, entering on the left and leaving on the right; the backward relation Ba⊆D−×D−B_a \subseteq D^- \times D^-, entering on the right and leaving on the left; the left relation La⊆D+×D−L_a \subseteq D^+ \times D^-, entering and leaving on the left; and the right relation Ra⊆D−×D+R_a \subseteq D^- \times D^+, entering and leaving on the right.✦ The left and right relations are the returns of aa, and the set of boundary diagrams on mm labels is 𝒯m\mathcal{T}_m.

Relations compose in path order: (u,w)∈PQ(u, w) \in PQ when (u,v)∈P(u, v) \in P and (v,w)∈Q(v, w) \in Q for some vv. The reflexive transitive closure of a relation PP on a set XX is the relation 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)✦ where IXI_X is the identity relation on XX.

The product abab of two boundary diagrams aa and bb on mm labels 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_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}(2)✦ A diagram ee is idempotent when ee=eee = e.

Fix an idempotent diagram ee. Through paths of ee, joined by the returns that bounce back and forth at the junction of two copies of ee, can come back to the label they started from, and the labels on such loops fall into classes, one family for each sign, ++ or −-, according to the copy D+D^+ or D−D^- in which the labels lie. The classes are counted, and those that go missing when ee is replaced by a diagram zz with ez=zez = z and ze=zze = z are singled out.

Loop Closures and Recurrent Classes

Write ss for a sign, and DsD^s for the copy of the label set carrying it. The through relation TasT_a^s of sign ss of a diagram aa is its forward relation for s=+s = + and its backward relation for s=−s = -.✦

Closing up the returns at the junction of two copies of a diagram ee gives its loop closures: the loop closure KesK_e^s of sign ss is the relation on DsD^s given by Ke+=(LeRe)*,Ke−=(ReLe)*.K_e^+ = (L_eR_e)^*, \qquad K_e^- = (R_eL_e)^*.(3)✦ The recurrence relation PesP_e^s of sign ss of ee is the relation on DsD^s made of a through step of ee with a loop closure on either side: Pes=KesTesKes.P_e^s = K_e^s \, T_e^s \, K_e^s.(4)✦

A signed recurrent class of ee is a pair (s,C)(s, C) of a sign ss and the set CC of labels joined by PesP_e^s in both directions to a label xx with (x,x)∈Pes(x, x) \in P_e^s.✦ The set of signed recurrent classes of ee is 𝒞e={(s,C):(x,x)∈Pes and C={y:(x,y)∈Pes,(y,x)∈Pes} for some label x}.\mathcal{C}_e = \bigl\{(s, C) : (x, x) \in P_e^s \text{ and } C = \{y : (x, y) \in P_e^s,\ (y, x) \in P_e^s\} \text{ for some label } x\bigr\}.(5)✦

Corners and Missing Classes

The corner of a diagram ee is the set of diagrams z∈𝒯mz \in \mathcal{T}_m with ez=zez = z and ze=zze = z.✦ The surviving through relation of sign ss of a diagram zz relative to ee is the relation Ues(z)U_e^s(z) on DsD^s formed as PesP_e^s is, with the through relation of zz in place of that of ee: Ues(z)=KesTzsKes.U_e^s(z) = K_e^s \, T_z^s \, K_e^s.(6)✦

The loop of sign ss at a label xx survives in zz when (x,x)∈Ues(z)(x, x) \in U_e^s(z). The missing set of zz relative to ee is the set ℳe(z)⊆𝒞e\mathcal{M}_e(z) \subseteq \mathcal{C}_e of the signed recurrent classes of ee at none of whose labels the loop survives: ℳe(z)={(s,C)∈𝒞e:(x,x)∉Ues(z) for every x∈C}.\mathcal{M}_e(z) = \{(s, C) \in \mathcal{C}_e : (x, x) \notin U_e^s(z) \text{ for every } x \in C\}.(7)✦

The Claim

Theorem 1. Let ee and zz be boundary diagrams on mm labels and let ss be a sign. If ee is idempotent, then TesKesTes=TesT_e^s K_e^s T_e^s = T_e^s(8)✦ and PesPes=Pes.P_e^s P_e^s = P_e^s.(9)✦ Whether or not ee is idempotent, |𝒞e|≤2m.|\mathcal{C}_e| \le 2m.(10)✦ If zz lies in the corner of ee, then Le⊆LzandRe⊆Rz,L_e \subseteq L_z \quad\text{and}\quad R_e \subseteq R_z,(11)✦ TesKesTzs⊆TzsandTzsKesTes⊆TzsT_e^s K_e^s T_z^s \subseteq T_z^s \quad\text{and}\quad T_z^s K_e^s T_e^s \subseteq T_z^s(12)✦ and PesUes(z)⊆Ues(z)andUes(z)Pes⊆Ues(z).P_e^s \, U_e^s(z) \subseteq U_e^s(z) \quad\text{and}\quad U_e^s(z) \, P_e^s \subseteq U_e^s(z).(13)✦ If ee is idempotent and zz lies in the corner of ee, then for every signed recurrent class (s,C)(s, C) of ee and all labels xx and yy in CC, (x,x)∈Ues(z)⇔(y,y)∈Ues(z)(x, x) \in U_e^s(z) \iff (y, y) \in U_e^s(z)(14)✦ and (s,C)∉ℳe(z)⇔(x,x)∈Ues(z).(s, C) \notin \mathcal{M}_e(z) \iff (x, x) \in U_e^s(z).(15)✦

In the paper, the result reads: for an idempotent ee, Ke+=(LeRe)*K_e^+ = (L_eR_e)^* and Ke−=(ReLe)*K_e^- = (R_eL_e)^*, Pe+=Ke+FeKe+P_e^+ = K_e^+F_eK_e^+ and Pe−=Ke−BeKe−P_e^- = K_e^-B_eK_e^-, FeKeFe=FeF_eK_eF_e = F_e and Pe2=PeP_e^2 = P_e, the recurrent classes 𝒞e\mathcal{C}_e of both signs number at most 2m2m, the corner is e𝒯me={z:ez=ze=z}e\mathcal{T}_me = \{z : ez = ze = z\}, Ue(z)=KeFzKeU_e(z) = K_eF_zK_e, the corner identities Le⊆LzL_e \subseteq L_z and Re⊆RzR_e \subseteq R_z hold together with absorption, and the missing set ℳe(z)\mathcal{M}_e(z) is well-defined on classes, where KeK_e, PeP_e and UeU_e stand for KesK_e^s, PesP_e^s and UesU_e^s with the sign dropped.

Each identity above holds for both signs, absorption is (12) together with (13), and the well-definedness of ℳe(z)\mathcal{M}_e(z) on classes is (14) together with (15).

What Is Checked

The claim is stated over boundary diagrams on mm labels and their product, idempotence and the corner of a diagram, the through relations TasT_a^s, the loop closures KesK_e^s with the reflexive transitive closure behind them, the recurrence relations PesP_e^s, the signed recurrent classes 𝒞e\mathcal{C}_e, the surviving through relations Ues(z)U_e^s(z) and the missing set ℳe(z)\mathcal{M}_e(z).