OctoInformBeta

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

Theorem 2.1 [Order-reversing image bound]: A multiplicative surjection from diagrams on mm labels to relations on hβ‰₯2h \ge 2 points reversing edge inclusion forces 2mβ‰₯2⌊(hβˆ’2)/127βŒ‹2m \ge 2^{\lfloor (h-2)/127 \rfloor}

Order-reversing homomorphisms from diagrams onto relations need exponentially many labels.

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

The head of a two-way automaton crosses a block of tape cells along paths that enter through one end of the block and leave through one end, possibly the same one. A boundary diagram on mm labels records such crossings, with mm labels for each direction of travel. Gluing two blocks side by side multiplies their diagrams, and a path through the glued block may pass back and forth between the two parts any number of times before it leaves.

The item compares these diagrams with the monoid β„›H\mathcal{R}_H of binary relations on a finite set HH of hh points, under the path-order product, in which (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 with identity IHI_H.

Diagrams and the Loss Bound

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^+, the backward relation BaβŠ†Dβˆ’Γ—Dβˆ’B_a \subseteq D^- \times D^-, the left relation LaβŠ†D+Γ—Dβˆ’L_a \subseteq D^+ \times D^- and the right relation RaβŠ†Dβˆ’Γ—D+R_a \subseteq D^- \times D^+.✦ The pairs in these relations are the edges of aa, its crossings: an edge of FaF_a enters on the left and exits on the right, one of BaB_a enters on the right and exits on the left, one of LaL_a enters and exits on the left, and one of RaR_a enters and exits on the right. The set of boundary diagrams on mm labels is 𝒯m\mathcal{T}_m.

The reflexive transitive closure of a relation PP on a set XX is the relation P*=⋃kβ‰₯0PkP^* = \bigcup_{k \ge 0} P^k on XX, where P0=IXP^0 = I_X and Pk+1=PkPP^{k+1} = P^k P.✦

The product abab of diagrams aa and bb in 𝒯m\mathcal{T}_m, which glues aa to the left of bb, is the diagram in 𝒯m\mathcal{T}_m with relations, composed in path order, Fab=Fa(LbRa)*Fb,Lab=LaβˆͺFa(LbRa)*LbBa,Bab=Bb(RaLb)*Ba,Rab=RbβˆͺBbRa(LbRa)*Fb.\begin{aligned} F_{ab} &= F_a (L_b R_a)^* F_b, & L_{ab} &= L_a \cup F_a (L_b R_a)^* L_b B_a, \\ B_{ab} &= B_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 identity diagram 1m1_m is the diagram in 𝒯m\mathcal{T}_m with forward relation ID+I_{D^+}, backward relation IDβˆ’I_{D^-} and empty left and right relations.✦

Edge inclusion is the relation βŠ‘\sqsubseteq on 𝒯m\mathcal{T}_m under which aβŠ‘ba \sqsubseteq b when each of the four relations of aa is contained in the corresponding relation of bb.✦

The loss bound of a natural number hβ‰₯2h \ge 2 is D(h)=2⌊(hβˆ’2)/127βŒ‹.D(h) = 2^{\lfloor (h-2)/127 \rfloor}.(2)✦

The Claim

Theorem 1. Let mβ‰₯1m \ge 1, and let HH be a finite set with |H|β‰₯2|H| \ge 2. Let SS be a set of diagrams in 𝒯m\mathcal{T}_m that contains 1m1_m and is closed under the product, and let Ο†:Sβ†’β„›H\varphi \colon S \to \mathcal{R}_H be a surjective map with Ο†(ab)=Ο†(a)Ο†(b)\varphi(ab) = \varphi(a)\varphi(b) for all a,b∈Sa, b \in S and with Ο†(b)βŠ†Ο†(a)\varphi(b) \subseteq \varphi(a) whenever a,b∈Sa, b \in S and aβŠ‘ba \sqsubseteq b. Then D(|H|)≀2m.D(|H|) \le 2m.(3)✦ In particular, when H={0,1,…,hβˆ’1}H = \{0, 1, \dots, h-1\} for some hβ‰₯2h \ge 2, D(h)≀2m.D(h) \le 2m.(4)✦

In the paper, the result reads: if mβ‰₯1m \ge 1, HH is a finite set with h=|H|β‰₯2h = |H| \ge 2, S0S_0 is a submonoid of 𝒯m\mathcal{T}_m and a surjective multiplicative map Ο†0:S0β†’β„›H\varphi_0 \colon S_0 \to \mathcal{R}_H, which need not preserve identities, satisfies Ο†0(w)βŠ†Ο†0(z)\varphi_0(w) \subseteq \varphi_0(z) whenever zβŠ‘wz \sqsubseteq w, then 2mβ‰₯2⌊(hβˆ’2)/127βŒ‹2m \ge 2^{\lfloor (h-2)/127 \rfloor}.

What Is Checked

The claims (3) and (4) are stated over boundary diagrams on mm labels, their product (1) with the reflexive transitive closure in it, the identity diagram 1m1_m, edge inclusion βŠ‘\sqsubseteq, the monoid β„›H\mathcal{R}_H of relations on a finite set, and the loss bound (2).