OctoInformBeta

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

§4.2 (proof of Proposition 4.3): base case, Steps 1 to 3: The base case on at most 128 points and the lemmas of the step from h−127h - 127 points to hh points

Base case and inductive steps of the missing-class bound.

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 source gives an exponential lower bound on the number of states needed to complement a two-way nondeterministic finite automaton (2NFA), and this item belongs to its Section 4, An exponential bound for order-reversing images. The item’s claims concern a monoid seen in two ways: through binary relations on a finite set HH of hh points, and through boundary diagrams on mm labels, which record how a 2NFA with mm states can enter and leave a block of its tape.

The item is the induction on hh that proves Proposition 4.3 of the source, which bounds a count of classes of diagrams from below by the loss bound of hh. The loss bound of a natural number hh is the power of two D(h)=2⌊(h−2)/127⌋,D(h) = 2^{\lfloor (h-2)/127 \rfloor},(1)✦ with exponent 00 for h<2h < 2. The induction has a base case for h≤128h \le 128 and a step from h−127h - 127 points to hh points in three parts, and the library states the base case and the ten lemmas of the step as eleven separate claims.

The Relation Monoid

The relation monoid ℛH\mathcal{R}_H of a set HH is the monoid of all binary relations on HH 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, with the identity relation IHI_H as unit.✦ The restricted identity of a subset FF of HH is the relation on HH IF={(x,x):x∈F},I_F = \{(x,x) : x \in F\},(2)✦ and the permutation unit of a permutation π\pi of HH is its graph, as an element of ℛH\mathcal{R}_H: Γπ={(x,π(x)):x∈H}.\Gamma_\pi = \{(x, \pi(x)) : x \in H\}.(3)✦

The reflexive transitive closure of a relation QQ on a set XX is the relation Q*=⋃n≥0Qn,Q^* = \bigcup_{n \ge 0} Q^n,(4)✦ with Q0Q^0 the identity relation on XX.

Boundary Diagrams

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^+, 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 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}(5)✦

Edge inclusion is the relation ⊑\sqsubseteq on 𝒯m\mathcal{T}_m with 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 corner of a diagram ee is the set of diagrams zz in 𝒯m\mathcal{T}_m with ez=ze=zez = ze = z.✦ The nesting order is the relation ⊴\trianglelefteq on 𝒯m\mathcal{T}_m with d⊴ed \trianglelefteq e when dd and ee are idempotent and de=ed=dde = ed = d.✦

Recurrent and Missing Classes

For a sign σ∈{+,−}\sigma \in \{+, -\}, the through relation TaσT^\sigma_a of a diagram aa is the relation on the labels given by FaF_a for σ=+\sigma = + and by BaB_a for σ=−\sigma = -.✦ The loop closure Λeσ\Lambda^\sigma_e and the recurrence relation ρeσ\rho^\sigma_e of a diagram ee at σ\sigma are the relations on the labels Λe+=(LeRe)*,Λe−=(ReLe)*,ρeσ=ΛeσTeσΛeσ.\Lambda^+_e = (L_e R_e)^*, \qquad \Lambda^-_e = (R_e L_e)^*, \qquad \rho^\sigma_e = \Lambda^\sigma_e \, T^\sigma_e \, \Lambda^\sigma_e.(6)

A signed recurrent class of a diagram ee is a pair (σ,C)(\sigma, C) of a sign σ\sigma and a set CC of labels for which some label xx with (x,x)∈ρeσ(x,x) \in \rho^\sigma_e has C={y:(x,y)∈ρeσ and (y,x)∈ρeσ}.C = \{\, y : (x,y) \in \rho^\sigma_e \text{ and } (y,x) \in \rho^\sigma_e \,\}.(7)✦ The set of signed recurrent classes of ee is 𝒞e\mathcal{C}_e.

For diagrams ee and zz and a sign σ\sigma, the surviving relation of zz relative to ee at σ\sigma is ΛeσTzσΛeσ\Lambda^\sigma_e T^\sigma_z \Lambda^\sigma_e, the through relation of zz closed on both sides by the loop closure of ee.✦ The set ℳe(z)\mathcal{M}_e(z) of classes of ee missing at zz holds the classes on which the surviving relation has no loop: ℳe(z)={(σ,C)∈𝒞e:(x,x)∉ΛeσTzσΛeσ for every x∈C}.\mathcal{M}_e(z) = \{\, (\sigma, C) \in \mathcal{C}_e : (x,x) \notin \Lambda^\sigma_e T^\sigma_z \Lambda^\sigma_e \text{ for every } x \in C \,\}.(8)✦

The Claim

Theorem 1. Let AA be a monoid, HH a set, φ:A→ℛH\varphi\colon A \to \mathcal{R}_H a monoid homomorphism and ι:A→𝒯m\iota\colon A \to \mathcal{T}_m a map with ι(ab)=ι(a)ι(b)\iota(ab) = \iota(a)\,\iota(b) for all a,b∈Aa, b \in A.

Base case. Suppose order reversal holds: ι(b)⊑ι(b′)\iota(b) \sqsubseteq \iota(b') implies φ(b′)⊆φ(b)\varphi(b') \subseteq \varphi(b) for all b,b′∈Ab, b' \in A. If HH has at most 128 points and an element aa of AA has φ(a)=IH∪{(x,y)}\varphi(a) = I_H \cup \{(x,y)\} for points x≠yx \ne y of HH, then D(|H|)≤|ℳι(1)(ι(a))|.D(|H|) \le \lvert \mathcal{M}_{\iota(1)}(\iota(a)) \rvert.(9)✦

Conjugation. For every unit pp of AA and every a∈Aa \in A, |ℳι(1)(ι(pap−1))|≤2|ℳι(1)(ι(a))|.\lvert \mathcal{M}_{\iota(1)}(\iota(p a p^{-1})) \rvert \le 2\,\lvert \mathcal{M}_{\iota(1)}(\iota(a)) \rvert.(10)✦

Moving the edge. Suppose every permutation π\pi of HH has a unit pp of AA with φ(p)=Γπ\varphi(p) = \Gamma_\pi. If aa is an idempotent of AA with φ(a)=IH∪{(x,y)}\varphi(a) = I_H \cup \{(x,y)\} for points x≠yx \ne y of HH, and u≠vu \ne v are points of HH, then some idempotent ss of AA has φ(s)=IH∪{(u,v)},|ℳι(1)(ι(s))|≤2|ℳι(1)(ι(a))|.\varphi(s) = I_H \cup \{(u,v)\}, \qquad \lvert \mathcal{M}_{\iota(1)}(\iota(s)) \rvert \le 2\,\lvert \mathcal{M}_{\iota(1)}(\iota(a)) \rvert.(11)✦

Hub and families. If HH is finite with at least 129 points, there are a point zz of HH, the hub, and two families u1,…,u64u_1, \dots, u_{64} and v1,…,v64v_1, \dots, v_{64}, each of 64 distinct points of HH, with ui≠vj,ui≠z,vj≠z(1≤i,j≤64).u_i \ne v_j, \qquad u_i \ne z, \qquad v_j \ne z \qquad (1 \le i, j \le 64).(12)✦

Removing the hub. For points uu, vv, zz of HH with u≠zu \ne z and v≠zv \ne z, IH\{z}(IH∪{(u,z)})(IH∪{(z,v)})IH\{z}=IH\{z}∪{(u,v)}.I_{H \setminus \{z\}} \bigl(I_H \cup \{(u,z)\}\bigr) \bigl(I_H \cup \{(z,v)\}\bigr) I_{H \setminus \{z\}} = I_{H \setminus \{z\}} \cup \{(u,v)\}.(13)✦

Common budget. Let b0b_0 be an idempotent of AA, tt and cc natural numbers, and s1,…,st,s1′,…,st′s_1, \dots, s_t, s'_1, \dots, s'_t elements of AA with |ℳι(1)(ι(s))|≤2c\lvert \mathcal{M}_{\iota(1)}(\iota(s)) \rvert \le 2c for each ss among them. Then there is a set J0⊆𝒞ι(b0)J_0 \subseteq \mathcal{C}_{\iota(b_0)} of at most 8tc8tc classes, a common budget for all the elements b0sisj′b0b_0 s_i s'_j b_0, with ℳι(b0)(ι(b0sisj′b0))⊆J0(1≤i,j≤t).\mathcal{M}_{\iota(b_0)}\bigl(\iota(b_0 s_i s'_j b_0)\bigr) \subseteq J_0 \qquad (1 \le i, j \le t).(14)✦

Nested chain. Let AA be finite, b0b_0 an idempotent of AA, kk a natural number, JJ a set of pairs of a sign and a set of labels, and g0,g1,…g_0, g_1, \dots elements of AA such that, for each j<kj < k, ι(gj)\iota(g_j) lies in the corner of ι(b0)\iota(b_0) and ℳι(b0)(ι(gj))⊆J\mathcal{M}_{\iota(b_0)}(\iota(g_j)) \subseteq J. Then b0b_0 extends to a sequence of idempotents b0,b1,b2,…b_0, b_1, b_2, \dots of AA in which, for every jj, bj+1b_{j+1} is a positive power of bjgjbjb_j g_j b_j and ι(bj+1)⊴ι(bj)\iota(b_{j+1}) \trianglelefteq \iota(b_j), with ℳι(b0)(ι(bj))⊆J\mathcal{M}_{\iota(b_0)}(\iota(b_j)) \subseteq J for j≤kj \le k and ∑j=0k−1|ℳι(bj)(ι(bj+1))|≤2|J|.\sum_{j=0}^{k-1} \lvert \mathcal{M}_{\iota(b_j)}(\iota(b_{j+1})) \rvert \le 2\,\lvert J \rvert.(15)✦

Retained points. If HH is finite, UU and VV are disjoint subsets of HH with 64 points each, zz is a point of HH outside U∪VU \cup V, x∈Ux \in U and y∈Vy \in V, then some subset FF of HH has |F|=|H|−127,z∉F,F∩U={x},F∩V={y}.\lvert F \rvert = \lvert H \rvert - 127, \qquad z \notin F, \qquad F \cap U = \{x\}, \qquad F \cap V = \{y\}.(16)✦

Smaller instance. Let AA be finite and φ\varphi surjective. Let bb be an idempotent of AA and b′b' an element with bb′=b′b=b′bb' = b'b = b', and let FF be a subset of HH and xx, yy points of FF with IFφ(b)IF=IFI_F\,\varphi(b)\,I_F = I_F and IFφ(b′)IF=IF∪{(x,y)}I_F\,\varphi(b')\,I_F = I_F \cup \{(x,y)\}. Then there are an idempotent dd of the corner bAbbAb and a monoid homomorphism ψ\psi from the corner monoid dAddAd, with identity dd, onto ℛF\mathcal{R}_F such that ψ(w)\psi(w) is the restriction of φ(w)\varphi(w) to FF for every w∈dAdw \in dAd, every permutation π\pi of FF has a unit pp of dAddAd with ψ(p)=Γπ\psi(p) = \Gamma_\pi, and some idempotent vv of dAddAd has ψ(v)=IF∪{(x,y)},|ℳι(d)(ι(v))|≤2|ℳι(b)(ι(b′))|.\psi(v) = I_F \cup \{(x,y)\}, \qquad \lvert \mathcal{M}_{\iota(d)}(\iota(v)) \rvert \le 2\,\lvert \mathcal{M}_{\iota(b)}(\iota(b')) \rvert.(17)✦

Missing classes in context. Let ee, dd, pp, qq, zz be diagrams in 𝒯m\mathcal{T}_m with ee and dd idempotent, (pe)q=d(pe)q = d, zz in the corner of ee and (pz)q(pz)q in the corner of dd. Then |ℳd((pz)q)|≤2|ℳe(z)|.\lvert \mathcal{M}_d\bigl((pz)q\bigr) \rvert \le 2\,\lvert \mathcal{M}_e(z) \rvert.(18)✦

Amplification. Let h≥129h \ge 129 and cc be natural numbers, and δ1,…,δ4096\delta_1, \dots, \delta_{4096} natural numbers with δ1+…+δ4096≤1024c\delta_1 + \dots + \delta_{4096} \le 1024\,c and D(h−127)≤2δjD(h - 127) \le 2\delta_j for every jj. Then D(h)≤c.D(h) \le c.(19)✦

In the paper, the result reads, with t=64t = 64, h=|H|h = \lvert H \rvert and c=|ℳι(1)(ι(a))|c = \lvert \mathcal{M}_{\iota(1)}(\iota(a)) \rvert: in the base case, for h≤2th \le 2t, an empty missing set would give ι(1)⊑ι(a)\iota(1) \sqsubseteq \iota(a) and contradict order reversal; in Step 1, conjugates sis_i and sj′s'_j cost at most 2c2c each, the cost of an element being the number of its missing classes, and the sandwiches gij=b0sisj′b0g_{ij} = b_0 s_i s'_j b_0 have φ(gij)=P0∪{(ui,vj)}\varphi(g_{ij}) = P_0 \cup \{(u_i, v_j)\}, for a fixed relation P0P_0, and a common budget J0J_0 with |J0|≤8tc\lvert J_0 \rvert \le 8tc; in Step 2, the nested chain bℓb_\ell, whose ℓ\ell-th step costs δℓ\delta_\ell, has total cost ∑ℓδℓ≤16tc\sum_\ell \delta_\ell \le 16tc; and in Step 3, each step of the chain restricts to a smaller instance on h−2t+1h - 2t + 1 points, so that 2δℓ≥D(h−127)2\delta_\ell \ge D(h - 127) and c≥(t/32)D(h−127)=D(h)c \ge (t/32)\,D(h - 127) = D(h).

What Is Checked

The claims are stated over the relation monoid ℛH\mathcal{R}_H with its restricted identities (2) and permutation units (3), over the boundary diagrams of 𝒯m\mathcal{T}_m with their product (5), built with the closure (4), edge inclusion, corners and nesting, over the recurrent classes (7) of the relations (6) and the missing classes (8), and over the loss bound (1). The monoid AA and its maps enter (9), (10), (11), (14), (15) and (17); (18) concerns diagrams alone, (12), (13) and (16) points and subsets of HH, and (19) natural numbers.

The library proves that the permutation unit Γπ\Gamma_\pi of a permutation π\pi of HH is a unit of ℛH\mathcal{R}_H, with inverse Γπ−1\Gamma_{\pi^{-1}}.✦