OctoInformBeta

OpenAI preprint, September 2026 · §4. An exponential bound for order-reversing images · §4

§4 (proof of Theorem 2.1): The loss bound D(|H|)D(|H|) is at most 2m2m for finite HH and diagrams on mm labels, with four facts on idempotents and corners

Order-reversing homomorphisms from diagrams onto all relations need 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

A nondeterministic automaton with state set HH sends each word to the relation on HH of pairs of states joined by a run on it, and concatenation of words becomes the path-order product of relations, 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. The relation monoid ℛH\mathcal{R}_H of a set HH is the monoid of all binary relations on HH under this product, with the identity relation IHI_H as its unit.✦

The head of a two-way automaton can enter a block of tape from either side and leave it through either side, so what a block does is described by a boundary diagram rather than by a relation. The question is how many labels it takes for a set of boundary diagrams, closed under the product of diagrams defined below, to map onto all of ℛH\mathcal{R}_H multiplicatively and so that adding edges to a diagram can only shrink its image. The library answers it with a lower bound on the number mm of labels in terms of |H||H|, and states beside it four facts on idempotents and corners.

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 set of labels: the forward relation Fa⊆D+×D+F_a \subseteq D^+ \times D^+, from entry on the left to exit on the right; the backward relation Ba⊆D−×D−B_a \subseteq D^- \times D^-, from entry on the right to exit on the left; the left relation La⊆D+×D−L_a \subseteq D^+ \times D^-, from entry on the left back to exit on the left; and the right relation Ra⊆D−×D+R_a \subseteq D^- \times D^+, from entry on the right back to exit on the right.✦ The set of boundary diagrams on mm labels is 𝒯m\mathcal{T}_m.

For a relation QQ on a set XX, the reflexive transitive closure Q*Q^* is the relation on XX joining xx to yy when a chain of steps in QQ, possibly empty, leads from xx to yy.✦ The product abab of diagrams 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_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 identity diagram 1m∈𝒯m1_m \in \mathcal{T}_m is the diagram with forward relation ID+I_{D^+}, backward relation ID−I_{D^-}, and empty left and right relations.✦

Edge inclusion ⊑\sqsubseteq is the order on 𝒯m\mathcal{T}_m in 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.✦

The loss bound D(h)D(h) of a natural number hh is the number D(h)=2⌊(h−2)/127⌋.D(h) = 2^{\lfloor (h-2)/127 \rfloor}.(2)✦

Idempotents and Corners

Theorem 1. Let AA be a finite monoid and a∈Aa \in A. Then there is an integer k≥1k \ge 1 for which aka^k is idempotent: (ak)2=ak.(a^k)^2 = a^k.(3)✦

Theorem 2. Let AA be a finite semigroup, MM a monoid, and θ:A→M\theta \colon A \to M a surjective map with θ(ab)=θ(a)θ(b)\theta(ab) = \theta(a)\theta(b) for all a,b∈Aa, b \in A. Then there are an idempotent dd of AA and a monoid homomorphism ψ\psi from the corner dAddAd, a monoid with identity dd, to MM such that ψ(dAd)=M,ψ(w)=θ(w)for all w∈dAd,M×⊆ψ((dAd)×),\psi(dAd) = M, \qquad \psi(w) = \theta(w) \quad \text{for all } w \in dAd, \qquad M^{\times} \subseteq \psi\bigl((dAd)^{\times}\bigr),(4)✦ where M×M^{\times} and (dAd)×(dAd)^{\times} are the groups of units.

Theorem 3. Let HH be a set and x,y∈Hx, y \in H. Then the relation IH∪{(x,y)}I_H \cup \{(x, y)\} is an idempotent of ℛH\mathcal{R}_H: (IH∪{(x,y)})2=IH∪{(x,y)}.\bigl(I_H \cup \{(x, y)\}\bigr)^2 = I_H \cup \{(x, y)\}.(5)✦

The corner of a diagram e∈𝒯me \in \mathcal{T}_m is the set Cor⁡(e)\operatorname{Cor}(e) of diagrams that ee leaves unchanged on either side: Cor⁡(e)={z∈𝒯m:ez=z and ze=z}.\operatorname{Cor}(e) = \{\, z \in \mathcal{T}_m : ez = z \text{ and } ze = z \,\}.(6)✦

Theorem 4. Let AA be a monoid with identity 11, and let ι:A→𝒯m\iota \colon A \to \mathcal{T}_m be a map with ι(ab)=ι(a)ι(b)\iota(ab) = \iota(a)\iota(b) for all a,b∈Aa, b \in A. Then every a∈Aa \in A satisfies ι(a)∈Cor⁡(ι(1)).\iota(a) \in \operatorname{Cor}\bigl(\iota(1)\bigr).(7)✦

The Claim

Theorem 5. Let m≥1m \ge 1, let HH be a finite set with |H|≥2|H| \ge 2, and let S⊆𝒯mS \subseteq \mathcal{T}_m be a set of diagrams that contains 1m1_m and is closed under the product. Let φ:S→ℛH\varphi \colon S \to \mathcal{R}_H be a surjective map that is multiplicative, φ(ab)=φ(a)φ(b)\varphi(ab) = \varphi(a)\varphi(b) for all a,b∈Sa, b \in S, and order-reversing, φ(b)⊆φ(a)\varphi(b) \subseteq \varphi(a) for all a,b∈Sa, b \in S with a⊑ba \sqsubseteq b. Then D(|H|)≤2m.D(|H|) \le 2m.(8)✦

What Is Checked

The bound (8) is stated over the boundary diagrams on mm labels with their product (1), the identity diagram 1m1_m and edge inclusion ⊑\sqsubseteq, over the relation monoid ℛH\mathcal{R}_H of a finite set HH, and over the loss bound (2); the facts (3) and (4) are stated over every finite monoid and every finite semigroup. About the relations and the diagrams themselves, the library states (5) in ℛH\mathcal{R}_H and (7) on the corner (6) of a diagram.