OctoInformBeta

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

Proposition 4.3 [Cost of one added pair]: For an order-reversing surjection onto ℛH\mathcal{R}_H lifting permutations to units, an idempotent sent to IH∪{(x,y)}I_H\cup\{(x,y)\} loses at least D(h)D(h) recurrent classes

One pair added to the identity costs exponentially many classes.

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 working on a block of its tape enters the block at one border and leaves it at one border: it crosses from left to right or from right to left, or it turns back at the left border or at the right one. 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, one for each of these kinds of edge: Fa⊆D+×D+,Ba⊆D−×D−,La⊆D+×D−,Ra⊆D−×D+.F_a \subseteq D^{+} \times D^{+}, \qquad B_a \subseteq D^{-} \times D^{-}, \qquad L_a \subseteq D^{+} \times D^{-}, \qquad R_a \subseteq D^{-} \times D^{+}.(1)✦ The edges of the forward relation FaF_a enter on the left and exit on the right, those of the backward relation BaB_a enter on the right and exit on the left, and those of the left relation LaL_a and of the right relation RaR_a enter and exit on the left and on the right respectively.

The boundary diagrams on mm labels form the set 𝒯m\mathcal{T}_m, which carries a product: the product abab of two diagrams is the diagram of the block obtained by placing a block of diagram aa next to a block of diagram bb. Edge inclusion ⊑\sqsubseteq is the relation on 𝒯m\mathcal{T}_m that holds, a⊑ba \sqsubseteq b, when each of the four relations of aa is contained in the corresponding relation of bb.✦

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 PQ={(x,z):(x,y)∈P and (y,z)∈Q for some y∈H},PQ = \{(x, z) : (x, y) \in P \text{ and } (y, z) \in Q \text{ for some } y \in H\},(2)✦ with the identity relation IHI_H as its unit. The graph of a permutation σ\sigma of HH is the relation Γσ={(x,σ(x)):x∈H}\Gamma_\sigma = \{(x, \sigma(x)) : x \in H\} in ℛH\mathcal{R}_H.

Take a finite monoid with a multiplicative map into 𝒯m\mathcal{T}_m, under which its identity goes to a diagram ee, and a homomorphism from it onto ℛH\mathcal{R}_H, for a finite set HH of h≥2h \ge 2 elements, that reverses edge inclusion. The question is how many of the recurrent classes of ee, defined below, an idempotent of the monoid must lose when its image in ℛH\mathcal{R}_H is IHI_H with one pair (x,y)(x, y), x≠yx \neq y, added.

Recurrent and Missing Classes

A sign ss is ++ or −-, and at a sign ss the through relation of a diagram aa is the relation TasT^{s}_a on DsD^{s} with Ta+=FaT^{+}_a = F_a and Ta−=BaT^{-}_a = B_a.✦ The reflexive transitive closure of a relation PP on a set XX is the relation on XX 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.(3)✦ The loop closure of a diagram ee at ss is the relation Λes\Lambda^{s}_e on DsD^{s} that closes up the returns at the borders: Λe+=(LeRe)*,Λe−=(ReLe)*.\Lambda^{+}_e = (L_e R_e)^{*}, \qquad \Lambda^{-}_e = (R_e L_e)^{*}.(4)✦

The recurrence relation of ee at ss is the relation on DsD^{s} Qes=ΛesTesΛes,Q^{s}_e = \Lambda^{s}_e \, T^{s}_e \, \Lambda^{s}_e,(5)✦ and the set 𝒞e\mathcal{C}_e of signed recurrent classes of ee is the set of pairs of a sign and a set of labels 𝒞e={(s,C):C={y:(x,y)∈Qes,(y,x)∈Qes} for some x with (x,x)∈Qes}.\mathcal{C}_e = \bigl\{(s, C) : C = \{y : (x, y) \in Q^{s}_e,\ (y, x) \in Q^{s}_e\} \text{ for some } x \text{ with } (x, x) \in Q^{s}_e\bigr\}.(6)✦

For a second diagram zz on mm labels, the surviving relation of zz relative to ee at ss is the relation on DsD^{s} Ues(z)=ΛesTzsΛes,U^{s}_e(z) = \Lambda^{s}_e \, T^{s}_z \, \Lambda^{s}_e,(7)✦ and the set ℳe(z)\mathcal{M}_e(z) of classes missing after ee is replaced by zz is the set of recurrent classes of ee none of whose labels lies on a loop of Ues(z)U^{s}_e(z): ℳ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^{s}_e(z) \text{ for every } x \in C\}.(8)✦

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}.(9)✦

The Claim

Theorem 1. Let AA be a finite monoid, mm a natural number and ι\iota a map from AA to 𝒯m\mathcal{T}_m with ι(uv)=ι(u)ι(v)\iota(uv) = \iota(u)\,\iota(v) for all u,v∈Au, v \in A, and let e=ι(1)e = \iota(1). Let HH be a finite set with h≥2h \ge 2 elements and φ\varphi a monoid homomorphism from AA onto ℛH\mathcal{R}_H that reverses edge inclusion, in that φ(v)⊆φ(u)\varphi(v) \subseteq \varphi(u) whenever ι(u)⊑ι(v)\iota(u) \sqsubseteq \iota(v), and under which every permutation σ\sigma of HH has a unit lift, a unit pp of AA with φ(p)=Γσ\varphi(p) = \Gamma_\sigma. If aa is an idempotent of AA with φ(a)=IH∪{(x,y)}\varphi(a) = I_H \cup \{(x, y)\} for distinct x,y∈Hx, y \in H, then |ℳe(ι(a))|≥D(h).|\mathcal{M}_e(\iota(a))| \ge D(h).(10)✦

In the paper, the result reads: for m≥1m \ge 1, an idempotent e∈𝒯me \in \mathcal{T}_m, a submonoid SS of e𝒯mee\mathcal{T}_m e with identity ee, a finite set HH with h≥2h \ge 2 elements and a unital surjective order-reversing homomorphism φ:S→ℛH\varphi \colon S \to \mathcal{R}_H such that every permutation of HH has a lift that is a unit of SS, every idempotent a∈Sa \in S with φ(a)=IH∪{(x,y)}\varphi(a) = I_H \cup \{(x, y)\} for distinct x,yx, y has |ℳe(a)|≥D(h)|\mathcal{M}_e(a)| \ge D(h).

The paper’s statement is the theorem with A=SA = S and ι\iota the inclusion of SS in 𝒯m\mathcal{T}_m.

What Is Checked

The claim (10) is stated over the boundary diagrams of 𝒯m\mathcal{T}_m with their edge inclusion, the through relations, loop closures, recurrence relations and surviving relations of diagrams, built with the reflexive transitive closure, the recurrent classes 𝒞e\mathcal{C}_e and the missing classes ℳe(z)\mathcal{M}_e(z), the relation monoid ℛH\mathcal{R}_H with the graphs Γσ\Gamma_\sigma of permutations of HH, and the loss bound D(h)D(h).

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