OctoInformBeta

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

Lemma 4.1 [Minimal idempotent corners]: For a homomorphism θ\theta from a finite semigroup AA onto MM, every idempotent qq of MM has a minimal lift dd, and θ(dAd)=qMq\theta(dAd)=qMq

Corners at minimal idempotent lifts in finite semigroups reflect units.

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

Let AA be a finite semigroup and θ\theta a homomorphism from AA onto a monoid MM, a map with θ(xy)=θ(x)θ(y)\theta(xy)=\theta(x)\theta(y) for all x,y∈Ax,y\in A. The transition semigroup of a one-way nondeterministic automaton with state set HH is such an AA: its elements are the relations r(w)r(w) of the nonempty input words ww, with (p,p′)∈r(w)(p,p')\in r(w) when some run on ww leads from pp to p′p', and it lies in the monoid ℛH\mathcal R_H of 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.

For an idempotent qq of MM, one asks how much of the corner qMqqMq, the elements of MM that qq fixes on both sides, is already seen in the corner dAddAd of AA at an idempotent dd with θ(d)=q\theta(d)=q: whether θ\theta maps dAddAd onto qMqqMq, and whether an element of dAddAd that θ\theta sends to a unit of qMqqMq, an element with an inverse in qMqqMq, is a unit of dAddAd. Nesting is the order on the idempotents of AA in which e⊴de\trianglelefteq d when ed=de=eed=de=e, and one takes dd minimal for it among the idempotents dd with θ(d)=q\theta(d)=q.

Corners and Minimal Lifts

For an idempotent ee of a semigroup SS, the corner of SS at ee is the subset eSe={x∈S:ex=x=xe}eSe=\{x\in S : ex=x=xe\}(1) of SS, a monoid under the product of SS with identity ee. A unit of eSeeSe is an element xx of eSeeSe with xy=yx=exy=yx=e for some y∈eSey\in eSe; the units form the group (eSe)×(eSe)^{\times}, as the units of a monoid MM form the group M×M^{\times}.

Let θ:A→M\theta\colon A\to M be a homomorphism of semigroups, and let d∈Ad\in A and q∈Mq\in M be idempotents with θ(d)=q\theta(d)=q. The corner restriction map of θ\theta at dd is the map θ|dAd:dAd→qMq,x↦θ(x).\theta|_{dAd}\colon dAd\to qMq,\qquad x\mapsto\theta(x).(2)✦

An idempotent lift of an idempotent qq of MM is an idempotent dd of AA with θ(d)=q\theta(d)=q. A minimal idempotent lift of qq is an idempotent lift dd of qq such that every idempotent lift of qq nested in dd equals dd: e2=e,θ(e)=q,e⊴d⇒e=dfor every e∈A.e^2=e,\quad \theta(e)=q,\quad e\trianglelefteq d\quad\Longrightarrow\quad e=d \qquad\text{for every } e\in A.(3)

The Claim

Theorem 1. Let AA and MM be semigroups and θ:A→M\theta\colon A\to M a homomorphism. If AA is finite and θ\theta is onto, then for every idempotent qq of MM there is a d∈Ad\in A with $$d^2=d,\qquad \theta(d)=q,\qquad d\ \text{minimal in the sense of \eqref{eq:minimal}}.$$(4)✦ If θ\theta is onto and d∈Ad\in A and q∈Mq\in M are idempotents with θ(d)=q\theta(d)=q, then θ(dAd)=qMq.\theta(dAd)=qMq.(5)✦ If AA is finite and dd is a minimal idempotent lift of an idempotent qq of MM, then {x∈dAd:θ(x)∈(qMq)×}⊆(dAd)×.\{x\in dAd : \theta(x)\in(qMq)^{\times}\}\subseteq(dAd)^{\times}.(6)✦ If AA is finite, MM is a monoid with identity 11 and θ\theta is onto, then there is an idempotent dd of AA with θ(d)=1,θ(dAd)=M,M×⊆θ((dAd)×).\theta(d)=1,\qquad \theta(dAd)=M,\qquad M^{\times}\subseteq\theta\bigl((dAd)^{\times}\bigr).(7)✦

In the paper, the result reads: for a finite semigroup AA, a monoid MM and a surjective homomorphism θ:A→M\theta\colon A\to M, every idempotent qq of MM has an idempotent lift dd that is minimal under ⊴\trianglelefteq among such lifts; for every such minimal dd, restriction gives a unital surjection dAd→qMqdAd\to qMq; every element of dAddAd whose image is a unit of qMqqMq is a unit of dAddAd; and in particular every unit of qMqqMq has a unit lift, a unit of dAddAd that θ\theta sends to it.

The item’s unit lifts are stated for MM itself, the corner at its identity, as (7), and for a corner qMqqMq through (5) and (6) at a minimal idempotent lift of qq.

What Is Checked

The claim is stated over a semigroup AA, finite in (4), (6) and (7), a homomorphism θ\theta from AA to a semigroup MM, a monoid in (7), the corners (1) of AA and MM at idempotents dd and qq with θ(d)=q\theta(d)=q, the corner restriction map (2) between them, and minimal idempotent lifts (3).

Of the corner restriction map the library proves that it takes its values in qMqqMq and is a homomorphism of monoids: it preserves products and sends the identity dd of dAddAd to the identity qq of qMqqMq.