Introduction and preliminary concepts
For standard terms in semigroup theory see, for example, [1], [2], [9]. Let X denote the set {1,2,…,n} considered with the standard ordering. Let Tn denote the full transformation semigroup on X, that is the semigroup of all mappings α:X→X under composition. We shall denote composition simply by juxtaposition and shall adopt a right mapping convention; thus if α,β∈Tn the symbol αβ denotes the mapping in Tn obtained by performing first α and then β. The range and the set of fixed points of α∈Tn will be denoted by Xα and F(α), respectively. The order of Xα will be called the rank of α. We shall denote by Sn the symmetric group on X. In this paper we frequently use the cyclic group Zn with generator a=(12⋯n). We shall denote by C(n,q) the number of q-combinations of an n-set. We shall denote by Y⋅Z the set product {yz:y∈Y,z∈Z}. We shall call α an order-preserving mapping if i≤j implies iα≤jα (i,j∈X) and let On denote the submonoid of Tn consisting of all order-preserving mappings on X. The subsemigroup generated by a non-empty subset T of a semigroup S is denoted by ⟨T⟩. We will denote by E=E(S) the set of idempotents of S. The set of inverses of y∈S is denoted by V(y).
Various special subsemigroups of Tn have been studied by many authors; see for example, [3], [4], [5], [6], [7], [8], [11]. The purpose of this paper is to introduce a new subsemigroup of Tn containing On which will be denoted by OPn and its elements will be called orientation-preserving mappings. Also, we introduce a subsemigroup Pn=OPn∪ORn of Tn, where ORn denotes the collection of all orientation-reversing mappings.
In Section 2 we introduce the monoid OPn and show that any element of OPn can be written as a product of a power of a followed by an order-preserving mapping. We also show that every kernel class of α∈OPn is convex. In Section 3 we show that OPn is a regular semigroup, and we also characterise Green’s relations on OPn. In Section 4 we consider the subsemigroups of OPn conjugate with respect to Zn. From this we obtain a description of the core of OPn. In Section 5 we show that Pn is a regular semigroup and also give some its properties derived from the results about OPn.
First we need some definitions and results concerning sequences of elements from a chain. In this paper it will always be clear from context when additions are taken modulo n (or modulo t where t is the number of elements of any sequence). A (finite) sequence from a chain A=(a1,a2,…,at) is cyclic or has clockwise orientation if there exists no more than
2010 Mathematics Subject Classification. 20M20.
Key words and phrases. orientation-preserving mappings, transformation semigroups, regular semigroups, Green’s relations, idempotents, core.
This is a transcription of the article published in Semigroup Forum 58 (1999), 190–206 (received May 13, 1996; communicated by John M. Howie). Minor typographical corrections have been made in this version. one subscript i such that ai>ai+1. We say that A=(a1,a2,…,at) is anti-cyclic or has anti-clockwise orientation if there exists no more than one subscript i such that ai<ai+1. For example (1,1,2,5,1,1,1) is cyclic, (1,1,1,5,2,1,1) is anti-cyclic whilst (1,1,1,5,1,1,1) is both cyclic and anti-cyclic.
For any result concerning cyclic sequences there is a dual result for anti-cyclic sequences obtained by reversing the direction of all inequalities. We shall not prove these results in the sequel but consider them to be implicitly proved once the results on cyclic sequences are established.
Remark. Note that a sequence A=(a1,a2,…,at) is cyclic if and only if there exists i∈{0,…,t−1} such that
ai+1≤⋯≤at≤a1≤⋯≤ai
and i is unique unless the sequence is constant (where we adopt the convention that ≤a1≤⋯≤ai is vacuous if i=0).
The following lemma is immediate by inspection using the remark above:
Lemma 1.1. Let A be any cyclic [anti-cyclic] sequence. Then A is anti-cyclic [cyclic] if and only if A has no more than two distinct values.
If A=(a1,a2,…,at) is any sequence then we denote by Ar the sequence (at,at−1,…,a1), called the reversed sequence of A.
We have three more results about cyclic [anti-cyclic] sequences, the first two of which are obvious.
Lemma 1.2. Let A=(a1,a2,…,at) be any sequence from X. Then A is cyclic [anti-cyclic] if and only if Ar is anti-cyclic [cyclic].
Lemma 1.3. If (a1,a2,…,at) is cyclic [anti-cyclic] then so is
(a) the subsequence (ai1,ai2,…,air) (i1<i2<⋯<ir);
(b) (aj,aj+1,…,at,a1,…,aj−1) for all 1≤j≤t.
Let k∈{0,1,…,n−1}. Define a total order ≤k on X by
k+1≤kk+2≤k⋯≤kn≤k1≤k⋯≤kk
(where it is understood that ≤k1≤k⋯≤kk is vacuous if k=0). We write i<kj if i≤kj and i=j. Note that i≤kj if and only if i−k≤j−k.
We say that A=(a1,a2,…,at) is cyclic [anti-cyclic] with respect to ≤k if there exists no more than one subscript i such that ai+1<kai [a_i <_k a_{i+1}]. Clearly A is cyclic with respect to ≤k if and only if there exists j∈{0,…,t−1} such that aj+1≤k⋯≤kat≤ka1≤k⋯≤kaj.
Lemma 1.4. Let A=(a1,a2,…,at) be any sequence of elements from X. Then the following are equivalent:
(a) A is cyclic with respect to ≤0=≤.
(b) A is cyclic with respect to ≤k for some k.
(c) A is cyclic with respect to ≤k for all k.
Proof. Clearly we only need to prove that (b) implies (c). Suppose that (b) holds so that A is cyclic with respect to ≤k for some k. Then, for some j,
k+1≤kaj+1≤k⋯≤kat≤ka1≤k⋯≤kaj≤kk.
Either k+2≤kaj+1, in which case
aj+1≤k+1⋯≤k+1at≤k+1a1≤k+1⋯≤k+1aj,
or k+1=aj+1=⋯=aj+s<kk+2≤kaj+s+1≤k⋯≤kaj for some s∈{1,…,t}, in which case
aj+s+1≤k+1⋯≤k+1aj≤k+1⋯≤k+1aj+s.
In either case A is cyclic with respect to ≤k+1, and then (c) follows by induction. □
The monoid OPn
Let α∈Tn. We say that α is an orientation-preserving mapping on X if the sequence (1α,2α,…,nα) is cyclic. We note, by Lemma 1.4, that this sequence is then cyclic with respect to ≤k for all 0≤k≤n−1. The collection of all orientation-preserving mappings on X will be denoted by OPn.
Lemma 2.1. Let α∈OPn and let (b1,…,bt) be a cyclic sequence of members of X. Then the sequence (b1α,…,btα) is also cyclic.
Proof. We have, for some i∈{0,…,t−1}
bi+1≤bi+2≤⋯≤bt≤b1≤⋯≤bi.
and, for some j∈{0,…,n−1},
(j+1)α≤(j+2)α≤⋯≤nα≤1α≤⋯≤jα.
In particular α preserves ≤ on {j+1,…,n} and on {1,…,j}. Thus if bi+1∈{j+1,…,n} or bi∈{1,…,j} then certainly
bi+1α≤bi+2α≤⋯≤btα≤b1α≤⋯≤biα
and we have finished. Suppose then that bi+1<j+1 and bi>j. Then, for some r, either
i+1<r≤t,bi+1,…,br−1∈{1,…,j},
or
1≤r≤i,bi+1,…,bt,b1,…,br−1∈{1,…,j},br,…,bi∈{j+1,…,n}.
In either case
brα≤⋯≤btα≤b1α≤⋯≤br−1α,
as required. □
As a corollary we immediately obtain the following result:
Theorem 2.2. OPn is a submonoid of Tn containing On.
The following is immediate from the definitions of order-preserving mapping on X and cyclic sequence:
Proposition 2.3. For non-constant α∈OPn, α is an order-preserving mapping if and only if 1α<nα.
We may regard the members of X as being placed clockwise around the circumference of a circle so that the integer i lies between i−1 and i+1 (reduced modulo n). Any sequence of 3 distinct members, i,j,k, of X then defines either a clockwise orientation or an anti-clockwise orientation of the circle according as (i,j,k) is cyclic or anti-cyclic. The following lemma give a relation between an orientation-preserving mapping and triples of 3 distinct members of X, and follows immediately from Lemmas 2.1 and 1.2,
Proposition 2.4. Let α∈OPn and (i,j,k) be any triple of 3 distinct members of X. If the entries are distinct, then the triple (iα,jα,kα) defines the same orientation as (i,j,k).
An interval [i,k] for i,k∈X may be expressed clockwise by [i,k]={i,i+1,…,k−1,k} or anti-clockwise by [i,k]={i,i−1,…,k+1,k}. Henceforth, all intervals are expressed clockwise.
A set K⊆X is convex if K has the form [i,i+t], for some i∈X and 0≤t≤n−1. If α∈OPn, let us call the subsets xα−1 (x∈Xα) of X the kernel classes of α; they are the classes of equivalence relation
Πα={(x,y)∈X×X:xα=yα}.
Following Howie [7], we shall say that a kernel class is trivial if it consists of a single element, and we use the notation kerα for the set of kernel classes of α. It is easy to show that every kernel class of α∈On is convex; indeed they are intervals of X. Later, we prove more generally that if α∈OPn, then every kernel class of α is convex also.
The n-cycle a=(12⋯n) lies in OPn as the sequence of images of the ordered set X under a, (2,…,n,1), is cyclic.
We consider S=⟨On∪{a}⟩, and let g∈On. Clearly, if g is constant, then arg=g∈On, for all 0≤r≤n−1. We claim that, if g is not a constant mapping, then arg∈/On, for all 1≤r≤n−1. Suppose that g is not constant. Since g is an order-preserving mapping it follows that i=1g<ng=j. Now n−r<n−r+1 but (n−r)arg=ng=j>i=1g=(n−r+1)arg, showing that arg∈/On. Hence the next result follows:
Lemma 2.5. Let g∈On. Then arg∈On, (1≤r≤n−1), if and only if g is constant.
Next we give an interesting factorization of OPn and we show that any orientation-preserving mapping is a product of a power of a followed by an order-preserving mapping.
Theorem 2.6. Each α∈OPn has a factorization α=arf (0≤r≤n−1, f∈On) which is unique unless α is constant. In particular OPn=S.
Proof. Let α∈OPn. We claim that α=arf for some f∈On and 0≤r≤n−1. If α is a constant mapping then we take f=α and r arbitrary. Suppose that α is not a constant mapping. Then there exists i∈X such that iα>(i+1)α and we have that
1≤j≤nminjα=(i+1)α≤⋯≤nα≤1α≤⋯≤iα=1≤j≤nmaxjα. We define f by xf=(x+i)α for x∈X. Then f lies in On as 1f=(1+i)α≤2f=(2+i)α≤⋯≤nf=(n+i)α=iα. Put r=n−i. Then j(arf)=(j+r)f=(j+r+i)α=(j+n)α=jα, 1≤j≤n. Next suppose α is not constant and α=akf=alg, (0≤k,l≤n−1), f,g∈On. Then f=al−kg, so that, by Lemma 2.5, l−k=0, since g is not constant, whence l=k and f=g.
Now, using the known cardinalities of On (see for example [7]) and Zn, we obtain the following result:
Corollary 2.7. ∣S∣=∣OPn∣=nC(2n−1,n−1)−n(n−1).
Proof. By above,
∣S∣=∣Zn∣(∣On∣−n)+n=n∣On∣−n2+n=nC(2n−1,n−1)−n(n−1), as required.
Next we show that the kernel classes of orientation-preserving mappings are necessarily convex.
Lemma 2.8 (Convexity Lemma). Let α∈OPn and K be any kernel class of α. Then K is convex.
Proof. Let α∈OPn. Then, for some i,
(i+1)α≤⋯≤nα≤1α≤⋯≤iα.
Thus if jα=kα for some j≤i<k then jα=(j+1)α=⋯=(k−1)α=kα, which is sufficient to prove that the kernel classes are convex.
In [7] Howie showed that ∣E(On)∣=F2n, the 2nth Fibonacci number, through solution of a certain difference equation. The next lemma gives another proof of this.
Lemma 2.9. Let Fn be the nth Fibonacci number. Then, for all n≥1,
(i)∣E(On)∣=F2n;(ii)∣E(OPn)∣=n+k=1∑n−1k2F2(n−k).
Proof. (i) Let en=∣E(On)∣. Let e∈E(On+1). We consider two cases:
Xe⊆X: In this case e∣X∈E(On). Now ne≤(n+1)e, as e is order-preserving, and (n+1)e≤n as Xe⊆X. Applying the order-preserving mapping e to the latter inequality gives (n+1)e2≤ne, and since e2=e this says (n+1)e≤ne. Therefore (n+1)e=ne and so ∣{e∈E(On+1):Xe⊆X}∣=en.
Xe⊆X: Let i be least such ie=(n+1). Then je=n+1, for all j≥i. In general je≤i−1, for all j≤i−1 and so (i−1)e≤i−1. Hence, ∣{e∈E(On+1):i least such that ie=(n+1)}∣=ei−1. Summing over all values of i and adding the previous case yields the recurrence
en+1=en+(en+en−1+⋯+e1+1),
from which the result follows by induction.
(ii) Now let en=∣E(OPn)∣. We prove that the numbers of idempotents e in OPn with ∣e−1∣=k, (1≤k≤n−1) is k2F2(n−k), from which the result will follow. We build such an idempotent e∈E(OPn) as follows:
There are k choices for the convex set 1e−1: {n−k+2,n−k+3,…,1}, {n−k+3,n−k+4,…,1,2},…,{1,2,…,k}. Once 1e−1 is chosen, there are k choices for 1e. Suppose that 1e−1={t,t+1,…,n,1,2,…,s} say, (s=k+t−n−1). Put 1e−1=K. Then e∣X∖K is an idempotent on the chain C={s+1,s+2,…,t−1}, ∣C∣=n−k. By (i) it follows that e can be extended from e∣K to an idempotent in OPn, in F2(n−k) ways. Multiplying the number of choices in each of the 3 stages of the construction of e gives the number of possibilities as kkF2(n−k)=k2F2(n−k), as required.
Theorem 2.10
Theorem 2.10. For all n≥1, ∣E(OPn)∣=F2n−1+F2n+1−(n2−n+2).
Proof. We use the fact that for all n≥0, F0+F2+⋯+F2n=F2n+1−1 and F1+F3+⋯+F2n+1=F2n+2, each of which can be proved readily by induction. Let en=∣E(OPn)∣. We seek to simplify the formula given by the previous lemma. First note that ∑k=0n−1F2(n−k)=∑k=1nF2k=F2n+1−1 and
k=1∑n−1kF2(n−k)=j=1∑n−1k=j∑n−1F2(n−k)=j=1∑n−1(F2+F4+⋯+F2(n−j))=j=1∑n−1(F2(n−j)+1−1)=F3+F5+⋯+F2n−1−(n−1)=F2n−n.
Also we have
en+1−en=(n+1)−n+k=1∑nk2F2(n+1−k)−k=1∑n−1k2F2(n−k)=1+k=1∑nk2F2(n−(k−1))−k=1∑n−1k2F2(n−k)=1+k=0∑n−1(k+1)2F2(n−k)−k=0∑n−1k2F2(n−k)=1+k=0∑n−1F2(n−k)+2k=1∑n−1kF2(n−k)=1+(F2n+1−1)+2(F2n−n)=F2n+F2n+2−2n
and so
en+1=en+(F2n+F2n+2)−2n=⋯==e1+(F2+F4)+(F4+F6)+⋯+(F2n−2+F2n)+(F2n+F2n+2)−2(n+(n−1)+(n−2)+⋯+1)=2(F2+F4+⋯+F2n)+F2n+2−2(21n(n+1))=2(F2n+1−1)+F2n+2−n(n+1)=F2n+1+F2n+3−(n2+n+2),
or en=F2n−1+F2n+1−(n2−n+2), as required. □
Next we describe On⋅Zn and show that On⋅Zn=OPn.
Proposition 2.11. On⋅Zn={α∈OPn:1α=nα}∪{α∈OPn:∣Xα∣=1}.
Proof. Let α∈On⋅Zn be such that α is not a constant mapping. Let α=fam for some f∈On and 0≤m≤n−1. Then 1f=nf for otherwise α would be constant, whence 1α=nα.
Conversely, let α∈OPn. If α is a constant mapping then α∈On and α=αa0∈On⋅Zn. Now suppose that 1α=nα. We claim that α=fam for some f∈On and 0≤m≤n−1. If nα>1α then, by Proposition 2.3, α is an order-preserving mapping and so α=αa0 is a required factorization. Suppose that nα<1α and write 1α=k. Put m=n−k+1. Then we define the mapping f as follows:
xf=xα+m(x∈X). Let b∈X. Hence b(fa−m)=(bf)a−m=bf−m=(bα+m)−m=bα and so fa−m=α, which implies that f=αam∈OPn. It remains to prove that f∈On. Now 1f=1 as 1f=k+m=1, nf=nα+m=k+m, as nα=1α=k. Hence 1f<nf, f∈OPn, and so f∈On, by Proposition 2.3. □
From this result and the fact that OPn=Zn⋅On we can conclude that
On⋅(Zn⋅On)=On⋅(OPn)=OPn and so (On⋅Zn)2=OPn.
Some properties of OPn
It is well known that On is a regular semigroup. We can deduce from this that OPn is a regular semigroup.
Let α=akf∈OPn for some f∈On and some k (0≤k≤n−1). It is routine to check that f′an−k∈V(akf), where f′∈V(f) in On, though in Section 4 we show that not all inverses of akf are of this form. The next result follows from this together with Theorem 2.6.
Theorem 3.1. OPn is a regular semigroup.
Remark. Since OPn is regular, we have that ROPn=RTn∩(OPn×OPn), LOPn=LTn∩(OPn×OPn), HOPn=HTn∩(OPn×OPn), that is, for α,β∈OPn, αRβ⟺kerα=kerβ, αLβ⟺Xα=Xβ, αHβ⟺Xα=Xβ and kerα=kerβ, and since OPn is a finite semigroup we have that DOPn=JOPn.
Using the factorization of OPn given by Theorem 2.6 we can see easily the following result relating the L-classes of OPn and On:
Lemma 3.2. Let α=akf and β=amg for some 0≤k,m≤n−1 and f,g∈On. Then αLβ in OPn if and only if fLg in On.
However with R-classes the implication holds in neither direction for n>2. For example, let f=(122233) and g=(112133). Then kerf=kerg. However α=a2f=(132232), β=ag=(112331) and kerα=kerβ.
Next, with f=(112132), g=(112333)∈O3, let α=af=(112231) and β=a2g=(132133). Then kerα=kerβ, but kerf=kerg.
Let α,β∈OPn. We have that αRβ if and only if kerα=kerβ, and kernel classes are convex, so there is a one-to-one correspondence between R-classes of rank t, (t≥2), and choices of a t-set from X as follows: write the given t-set as {a1,a2,…,at} with a1<a2<⋯<at; the kernel classes of the corresponding R-class are then {a1,a1+1,…,a2−1},{a2,a2+1,…,a3−1},…,{at,at+1,…,a1−1}; the ai are called the initial points of the corresponding kernel class; conversely, the common set of initial points of the kernel classes of an R-class of OPn yields a t-set of X, and these two operations are mutually inverse.
We have αLβ if and only if Xα=Xβ, so L-classes also correspond to choices of a t-set from X, where t=∣Xα∣. Hence for t≥2 an H-class H of OPn can be coded as a choice of an ordered pair of t-sets (K,R) from X where K={a1,…,at} is the common t-set of the initial points of the kernel classes of the corresponding R-class and R={r1,…,rt} (r1<r2<⋯<rt) is the common range of all mappings in the corresponding L-class.
Let α∈H with aiα=r1, say. By Lemma 1.3 (b),
(ai,ai+1,…,at,a1,…,ai−1)
is cyclic, and since α∈OPn we have from Lemma 2.1 that the same is true of (aiα,ai+1α,…,ai−1α). However, aiα=r1=minXα, and since the aj form a transversal of the kernel classes of α we obtain:
aiα<ai+1α<⋯<atα<a1α<⋯<ai−1α.
Hence aiα=r1, ai+1α=r2,…,ai−1α=rt and so α∈H is defined by the pair of t-sets (K,R) together with the choice of i such that aiα=r1.
Conversely, for a given pair (K,R) and a given choice of i we can construct α∈H as follows: write the kernel classes of α as K1,K2,…,Kt where aj is the initial point of Kj. Define α by Kjα=rj−i+1. In summary we have:
Theorem 3.3. For t≥2 there is a one-to-one correspondence Φ between the set of triples (K,R,i) where K and R are ordered t-sets of X and 1≤i≤t and {α∈OPn:∣Xα∣=t} whereby (K,R,i)↦α, where each aj∈K is an initial point of a kernel class of α and ajα=rj−i+1. Moreover Hα={Φ(K,R,i):i=1,…,t}, so ∣Hα∣=t.
Suppose α,β∈OPn with ∣Xα∣=∣Xβ∣=t say. Let K be the set of initial points of the kernel classes of α and let R=Xβ. Let γ be any member of the H-class determined by the pair (K,R). Then αRγLβ, so αDOPnβ. Conversely, if αDOPnβ, then αDTnβ whence ∣Xα∣=∣Xβ∣. Hence the next result follows:
Proposition 3.4. Let α,β∈OPn. Then αDOPnβ if and only if ∣Xα∣=∣Xβ∣.
Next we give an alternative way of finding the order of OPn. Let α∈OPn be such that ∣Xα∣=t for some 1≤t≤n. Let Dt denote the D-class containing α. By Proposition 3.4 we have Dt={β∈OPn:∣Xβ∣=t}. Hence, if t=1 we have n constants mappings. By Theorem 3.3, β is determined by the pair (Kβ,Xβ), where Kβ is the t-set of initial points of the kernel classes of β, together with the choice of i such that aiβ=r1 (ai∈Kβ). Then for t≥2 we have C(n,t) possibilities for Kβ, C(n,t) choices for Xβ, and t choices for i. Hence the order of Dt (t≥2) is given by
∣Dt∣=tC(n,t)C(n,t).
Hence the order of OPn is given by
∣OPn∣=n+t=2∑ntC2(n,t).
Note that ∑t=1nC(n−1,t−1)C(n,t)=∑t=1nC(n−1,n−t)C(n,t) is the coefficient of xn in the expansion of (1+x)n−1(1+x)n=(1+x)2n−1. Hence ∑t=1nC(n−1,t−1)C(n,t)=C(2n−1,n), and this leads to ∑t=1ntC2(n,t)=nC(2n−1,n−1); thus we can recover Corollary 2.7:
∣OPn∣=n+nC(2n−1,n−1)−n2.
Next we give a description of the H-classes of α∈OPn. Let α∈E(OPn) and take K1,K2,…,Kt; r1,r2,…,rt and i as before. Since α∈E(OPn) the {rj} form a transversal of the kernel classes, and so
rj−i+1∈Kj,j=1,2,…,t.(1)
Let β=Φ(K,R,i−1). Hence,
Kjβ=ajβ=rj−(i−1)+1=rj−i+2,j=1,2,…,t.
Next we show by induction on p that ai−1βp=rp for all p=1,2,…,t. For p=1, we have that ai−1β=ri−1−i+2=r1. For p≥2,
ai−1βp=(ai−1βp−1)β=rp−1β.
Put j−i+1=p−1 in (1); we get j=p+i−2. Hence
ai−1βp=rp−1β=Kp+i−2β=rp+i−2−i+2=rp.
It follows that ∣⟨β⟩∣≥t. Since β∈Hα and ∣Hα∣=t we see that ⟨β⟩=Hα. Hence the next result follows:
Lemma 3.5. Let α∈E(OPn). Let Hα be the H-class containing α. Then Hα=⟨β⟩ and ∣Hα∣=∣Xα∣.
Corollary 3.6. The maximal subgroups of the D-class Dt of OPn are cyclic of order t. In particular, every subgroup of OPn is cyclic.
Conjugate subsemigroups of On
In this section we study some properties of subsemigroups of On conjugate with respect to Zn, and their links with the semigroup OPn. Let
Onk={a−kfak:f∈On},(0≤k≤n−1),
where a=(12⋯n) is the fixed generator of Zn.
Let α=amf∈OPn for some f∈On and some 0≤m≤n−1. For each k, (0≤k≤n−1), consider the mapping φk:On⟶OPn whereby hφk=a−khak, (h∈On). Let us write hak=a−khak. It is easy to verify that φk is an injective morphism with image Onk.
Lemma 4.1. Onk is a submonoid of OPn and φk is an isomorphism between On and Onk.
Proof. This is an immediate consequence of the general fact that conjugation by a unit is always a semigroup isomorphism.
Proposition 4.2. Onk is the monoid of all order-preserving mappings on X with respect to ≤k.
Proof. Let h be any element of Onk. Hence h=a−kfak for some f∈On. Let i,j∈X such that i≤kj. Hence i−k≤j−k, so ia−kf=(i−k)f≤(j−k)f=ja−kf since f is order-preserving, and so ih=(i−k)f+k≤k(j−k)f+k=jh.
Conversely let g be any order-preserving mapping on the chain (X,≤k). Put f=akga−k. By similar reasoning f∈On, so g=a−kfak∈Onk, and the proposition is proved.
Let T be any semigroup. Following standard terminology if E=E(T) is the set of idempotents of T, then ⟨E⟩ is called the core of T, and T is said to be a semiband if T equals its own core.
We will denote by GbS the G-class in S containing b where G is any Green’s relations, S is any semigroup and b is an element in S. We shall show that ∣E(RfOn)∣=∣E(RαOPn)∣. First, we need the following result in order to show that φk restricted to E(RfOn) is a bijection onto E(Ra−kfakOPn).
Lemma 4.3. Let g∈On, e∈E(OPn) such that eROPng. Then e∈On and eROng.
Proof. Observe that kere=kerg, which is a convex partition of the chain X. Let i,j be any two elements on X such that i≤j. If i,j are in the same kernel class then ie=je. Otherwise, i∈Ki=xe−1 and j∈Kj=ye−1, for some distinct x,y∈Xe. Since e is an idempotent x∈Ki, y∈Kj and since the kernel classes form a convex partition of X, then x≤y, as required. The last assertion is immediate since On is a regular subsemigroup of OPn.
Lemma 4.4. φk restricted to E(RfOn) is a bijection onto E(Ra−kfakOPn).
Proof. Certainly φk maps the first set injectively into the second. As for surjectivity, take e∈E(Ra−kfakOPn). Then ea−kφk=e, and ea−k∈E(OPn). Now ea−kRa−kfakOPneRakOPn(a−kfak)=fakRnOPnf. But then ea−k∈On and ea−kROnf by Lemma 4.3, proving surjectivity.
From this result we can now conclude with:
Theorem 4.5. Let α=akf∈OPn for some f∈On and some 0≤k≤n−1. Then ∣E(RfOn)∣=∣E(RαOPn)∣.
Proof. The result follows from Lemma 4.4, since αROPnαa−k=akfa−k.
Next we see that, in general, ∣E(LfOn)∣≤∣E(LamfOPn)∣, since we have LfOn⊆LamfOPn=LamfOPn. However we show that the containment is strict for n≥3. It is sufficient to observe this for n=3. Take α∈OP3 defined by α=a0f, (f∈O3) where f=(112232). Consider the mapping β=(112231)∈/O3. Clearly β∈E(LαOP3) yet β∈/E(LfO3).
Let VS(α) be denote the set V(α) in the semigroup S. In general we have that ∣VS(α)∣=∣E(LαS)∣∣E(RαS)∣. In our case, from the results above, we have
∣VOn(f)∣=∣E(LfOn)∣∣E(RfOn)∣<∣E(LamfOPn)∣∣E(RamfOPn)∣=∣VOPn(amf)∣
and so we can conclude that not all inverses of amf are of the form f′an−m where f′∈VOn(f).
It has long been known that the subsemigroup of all singular mappings of Tn is a semiband [6], and it has been proved that On is also idempotent-generated [7]. Our next task is to find the core of OPn. First we prove,
Lemma 4.6. Every α∈On has a fixed point.
Proof. Let α∈On and A={x∈X:x≤xα}. Note that 1∈A and so A is nonempty. Let a=maxA. Hence a≤aα as a∈A, and aα≤(aα)α as α∈On. Thus aα∈A and so aα≤a by the maximality of a. Therefore a=aα as required. □
Let U=⋃k=0n−1Onk and consider a−kfak where f∈On and 0≤k≤n−1. Now x∈X is a fixed point of a−kfak if and only if (x−k)f=x−k which is equivalent to saying that x−k is a fixed point of f. Thus we have the next result:
Lemma 4.7. Let α=a−kfak where f∈On and 0≤k≤n−1. Then x∈F(α) if and only if x−k∈F(f). In particular, if α∈U then F(α)=∅. □
As has often been observed each α∈Tn can be pictured as a digraph on n vertices with ij an arc of α if iα=j. Each connected component of such a digraph is functional, meaning that it consists of a unique cycle, together with a number of trees rooted around the points of the cycle. Each component C of the digraph of α∈Tn has a cycle K(C) defined by the property that x∈C is in K(C) if and only if there exists p>0 such that xαp=x.
Lemma 4.8. Let α∈OPn. Then the digraph of α cannot have a non-trivial cycle and a fixed point.
Proof. Suppose that α has a fixed point x. Suppose α has a cycle C with ∣C∣=p≥2. Let ≤ denote ≤x−1: note that x is the minimum of (X,≤x−1). We claim that there exists i∈C such that i<iα. Suppose not: then for each i∈C we have:
i>iα>iα2>⋯>iαp−1>iαp=i,
which is a contradiction and so there is such an i. Since α∈OPn and x∈F(α), we obtain (x,i,iα),(x,iα,iα2),…,(x,iαj,iαj+1) are cyclic. If for j≥0 we had iαj>iαj+1 we have iαj+1<x, which is a contradiction. Therefore iαj<iαj+1, for all j; whence i<iα<⋯<iαp−1<iαp=i, which is a contradiction. Hence the digraph of α cannot have a proper cycle and a fixed point. □
Theorem 4.9. Let α∈OPn. Then the digraph of α cannot have two cycles of different length.
Proof. Suppose α has a t-cycle Ct and an r-cycle Cr with t<r. Consider αt∈OPn. Each point of Ct is fixed by αt and so F(αt)=∅. However, for x∈Cr, xαt=x, but x is a point in a cycle of αt since xαtr=x(αr)t=x, which contradicts Lemma 4.8. □
Lemma 4.10. Let α∈OPn. If F(α)=∅ then the digraph of α is a forest and each component C associated with a fixed point of α is an interval.
Proof. If F(α)=∅, then by Lemma 4.8 the digraph of α cannot have a non-trivial cycle. Thus each component has a trivial cycle and so the digraph of α is a forest. Now let C be a component with C=C(x), x the fixed point in C. Take k sufficiently large so that C(x)={y∈X:yαk=x}. Then C(x)=x(αk)−1; αk∈OPn and so x(αk)−1 is an interval by the Convexity Lemma. □
Lemma 4.11. Let α∈OPn such that F(α)=∅. Let C be any component of α. Then Cα⊆C, there exist i,j∈X such that C=[i,j], and α restricted to C is an order-preserving with respect to ≤i−1.
Proof. It follows immediately from the definition of component that Cα⊆C, and from Lemma 4.10 that α restricted to C has a fixed point x. Suppose first that C=X. Then C=[x,x−1]. Suppose that a≤x−1b. If bα=x then x=xα=aα=bα, by the Convexity Lemma. If x<x−1bα then (x,aα,bα) is cyclic, by Lemma 2.1, so x≤x−1aα≤x−1bα. This proves that α is order-preserving with respect to ≤x−1.
Suppose now that C=X and choose any z∈X∖C. Observe, by definition of component, that zα∈/C. By Lemma 4.10, C=[i,j] for some i,j∈X. In particular note that j<i−1z and j<i−1zα. Let y∈C. If y≤i−1x then (y,x,z) is cyclic, so (yα,x,zα) is cyclic, by Lemma 2.1, so yα≤i−1x. Similarly if x≤i−1y then x≤i−1yα. Now suppose that a,b∈C and a<i−1b. If a≤i−1x≤i−1b then, from above, aα≤i−1x≤i−1bα. If a,b≤i−1x then (a,b,x) is cyclic so that (aα,bα,x) is cyclic and, from above, aα,bα≤i−1x. If aα=x then aα=xα and so aα=bα=x by the Convexity Lemma. Otherwise aα<i−1x, bα≤i−1x, and so by cyclicity, aα≤i−1bα. Similarly, if x≤i−1a,b then aα≤i−1bα, completing the proof that α∣C is order-preserving with respect to ≤i−1. □
Corollary 4.12. Let α∈OPn such that F(α)=∅. Then α∈U.
Proof. Let C be any component of α, so C=[i,j] for some i,j and α∣C:C⟶C is order-preserving with respect to ≤i−1, by Lemma 4.11. Let D be any other component (if it exists). Then, by Lemma 4.11 again, D=[k,l] for some k,l and α∣D:D⟶D is order-preserving with respect to ≤k−1. But
≤i−1∩(D×D)=≤k−1∩(D×D), since i∈/D and D is an interval, so that α∣D is order-preserving with respect to ≤i−1. Thus α is order-preserving with respect to ≤i−1, so lies in U. □
The previous lemmas and the description of the fixed points of a−kfak in terms of those of f now yield the next result:
Theorem 4.13. U={α∈OPn:F(α)=∅}.
Proof. If α∈U then F(α)=∅ by Lemma 4.7. The converse follows from Corollary 4.12. □
U does not contain a=(12⋯n) nor its non-idempotent powers. Moreover there are elements in OPn∖Zn which are not in U either. For example, let α=(12243442)∈OP4. We have α∈/Z4 as α is not a power of a=(1234), the fixed generator of Z4; however F(α)=∅.
Corollary 4.14. E(OPn)⊆U.
Proof. If α∈E(OPn) then F(α)=∅, and so by Theorem 4.13, α∈U. □
From this result, if α∈⟨E⟩ then α∈⟨U⟩. However On is a semiband [7] which implies that Onk is a semiband for all k=0,1,…,n−1 by Lemma 4.1. Let α∈U, so that there exists k (0≤k≤n−1) such that α∈Onk. Since Onk is a semiband, then α is a product of elements in E(Onk) and hence α is a product of elements in E(OPn). Therefore α∈⟨E⟩. Thus ⟨U⟩⊆⟨E⟩ as U⊆⟨E⟩. Hence the next result follows:
Corollary 4.15. Let E=E(OPn) and U=⋃k=0n−1Onk. Then ⟨E⟩=⟨U⟩.
Next we describe ⟨U⟩, the idempotent-generated subsemigroup of OPn.
Lemma 4.16. Let α∈OPn. Then αap∈U for some p (0≤p≤n−1).
Proof. Let α∈OPn. Using Theorem 2.6, α=amg for some 0≤m≤n−1 and g∈On. Then
αan−m=amgan−m=a−(n−m)gan−m∈Onn−m⊆U.
Lemma 4.17. Let R⊆X. Then the mapping f whereby:
xf={xaxif x∈Rif x∈/R is in OPn. Moreover if R is a proper subset, f∈U.
Proof. Note that for any i such that 1≤i≤n−1, we have (i−1)f≤i≤if; therefore 1f≤2f≤⋯≤(n−1)f. Now nf=n or nf=1; in the first case 1f≤2f≤⋯≤(n−1)f≤nf and f∈On; in the second case nf≤1f≤2f≤⋯≤(n−1)f and f∈OPn. In either case f∈OPn. Now if R is a proper subset then F(f)=∅ as F(f)=X∖R and so by Theorem 4.13, f∈U.
Lemma 4.18. Suppose that u∈⟨U⟩, u=1. Then ua∈⟨U⟩.
Proof. Note that the identity mapping is the only member of U of full rank as U=⋃m=0n−1a−mOnam and the identity mapping is the only member of On of full rank. Hence Xu=X. Take R=Xu in Lemma 4.17. We claim that ua=uf, from which the result follows from Lemma 4.17. Clearly f∣Xu=a∣Xu. Let x be any element of X. Then we have that x(ua)=(xu)a=(xu)f=x(uf) and so ua=uf.
Finally we have a description of the core of OPn.
Theorem 4.19. ⟨U⟩=⟨E(OPn)⟩=(OPn∖Zn)∪{1X}.
Proof. Let α∈(OPn∖Zn)∪{1X}. Clearly 1X∈⟨U⟩. Suppose α=1X. By Lemma 4.16, there exists p such that αap∈⟨U⟩, and clearly αap=1X. Take m such that p+m≡0(modn). Using Lemma 4.18 we therefore obtain α=αap+m=αapam∈⟨U⟩.
Conversely, U, and so ⟨U⟩, contains no members of OPn of rank n (except 1X), and so contains no other mappings of full rank; in particular
Zn∩⟨U⟩={1X}, as required.
Consequently the core of OPn is ⟨U⟩ and we can conclude that OPn is not a semiband, although, like Tn, the submonoid of singular mappings of OPn is idempotent-generated. There are mappings in the core of OPn without fixed point; for example the mapping exhibited before Corollary 4.14. Note that the digraph of that mapping has one component. For an example whose digraph has two components, take α=(132435425363)∈OP6. We have α∈/U as F(α)=∅ but α∈⟨U⟩.
Orientation-reversing mappings
Let α∈Tn. We say that α is an orientation-reversing mapping on X if the sequence (1α,2α,…,nα) is anti-cyclic. The collection of all orientation-reversing mappings on X will be denoted by ORn.
Let γ be the reflection whereby i↦n+1−i (i∈X). Note that γ is an involution on X. Also, γ∈ORn as (1γ,2γ,…,nγ)=(n,n−1,…,1) is anti-cyclic.
Let Γr [resp. Γl]: Tn⟶Tn be defined by α↦αγ [resp. α↦γα] (α∈Tn). The following result is easily proved.
Lemma 5.1. Γr,Γl are involutions on Tn which map OPn onto ORn and ORn onto OPn.
Corollary 5.2. OPn⋅ORn=ORn⋅OPn=ORn and
(ORn)2=(OPn)2=OPn.
Let Pn be denote the collection of all mappings in OPn∪ORn. By Corollary 5.2, we have that:
Theorem 5.3. Pn=OPn∪ORn is a submonoid of Tn.
From Lemma 1.1 we obtain the following
Lemma 5.4. OPn∩ORn={α∈OPn:∣Xα∣≤2}.
From this we can conclude that
Theorem 5.5. ∣Pn∣=2∣OPn∣−n−2C2(n,2).
Proof. Note that ∣Pn∣=∣OPn∣+∣ORn∣−∣OPn∩ORn∣. From Lemma 5.4 and the discussion following Proposition 3.4, ∣OPn∩ORn∣=n+2C2(n,2) and since ∣OPn∣=∣ORn∣ the result follows.
Remark. A simple calculation now yields
∣Pn∣=n!(n−1)!(2n)!−2n(n3−2n2+5n−2)
and this gives Pn=Tn for n≤3. This may be a reason why many interesting counterexamples of semigroups of transformations require 4 base points.
Let β∈ORn and write β as αγ where α∈OPn. It is routine to check that γα′∈V(αγ) in Pn, where α′∈V(α) in OPn. (Conversely, given β′∈V(β) in Pn then it is straightforward to check that β′=α′γ for some α′∈V(α) in OPn.) Hence the next result follows:
Theorem 5.6. Pn is a regular monoid.
Consequently, from this result the usual description of Green’s relations L, R and H applies again. (See Remark that follows Theorem 3.1.)
Lemma 5.7. Let α,β∈Pn. Then αDPnβ if and only if ∣Xα∣=∣Xβ∣.
Proof. If αDPnβ, then αDTnβ whence ∣Xα∣=∣Xβ∣.
Conversely, suppose that ∣Xα∣=∣Xβ∣. If α,β∈OPn then αDOPnβ by Proposition 3.4. If α,β∈ORn then ∣Xαγ∣=∣Xβγ∣, so that, by Proposition 3.4,
αRPnαγDOPnβγRPnβ, so certainly αDPnβ. Similarly, if only one of α,β lies in OPn, say without loss of generality α∈OPn, β∈ORn, then αDOPnβγRPnβ. In each case αDPnβ.
Lemma 5.8. Let α∈Pn be such that ∣Xα∣=t for some 3≤t≤n. Let Hα be the H-class containing α. Then ∣Hα∣=2t.
Proof. Let α∈Pn be such that ∣Xα∣=t for some 1≤t≤n. Let DtPn denote the D-class containing α. By the previous lemma, DtPn={β∈Pn:∣Xβ∣=t}. By Lemma 5.4, for t≤2 we have DtPn∩OPn=DtPn∩ORn. For t≥3, DtPn=(DtPn∩OPn)∪(DtPn∩ORn). (The union is disjoint.) Since Γr restricted to DtPn∩OPn is a bijection onto DtPn∩ORn then ∣DtPn∩OPn∣=∣DtPn∩ORn∣. Since DtPn∩OPn=DtOPn then ∣DtPn∣=2∣DtOPn∣. In Pn, DtPn has the same number of R-, L-classes as DtOPn and so the number of H-classes in DtPn is equal the number of H-classes in DtOPn. Since all H-classes within the one D-class have the same cardinality, then the order of every H-class in DtPn is twice the order of every H-class in DtOPn, whence the result follows from Corollary 3.6. □
Theorem 5.9. For t≥3 the maximal subgroups of DtPn are dihedral groups of order 2t.
Proof. Recall that the dihedral group Dn of degree n is a subgroup of Sn (n≥3) of order 2n and generators x and y (x,y∈Dn) satisfying the following conditions: xn=1X, y2=1X, xk=1X if 0<k<n and yx=x−1y; conversely any group satisfying these conditions is isomorphic to Dn. (See, for example, [10].)
Let α∈E(Pn) be such that ∣Xα∣=t for some t. Take K1,K2,…,Kt as the kernel classes of α and r1,r2,…,rt as the range of α as before such that Kjα=rj, j=1,2,…,t. Next we describe the maximal subgroups of DtPn and we show that they are dihedral groups of order 2t with generators δ and β (δ,β∈Pn) satisfying βt=α, δ2=α, βk=α if 0<k<t and δβ=β−1δ, where β−1 is the group inverse of β in Hα. For this consider the mapping δ defined as follows:
Kjδ=rt−j+1,j=1,2,…,t. Clearly Xδ=Xα and kerδ=kerα. Moreover δ∈ORn as the sequence (rt,rt−1,…,r1) is anti-cyclic. Also, consider the mapping β whereby
Kjβ=rj+1,j=1,2,…,t. Note that β is the mapping used in the proof of Lemma 3.5 and β∈OPn, βt=α, βk=α if 0<k<t. Also for all j=1,2,…,t we have
Kjδ2=rt−j+1δ=rt−(t−j+1)+1=rj, and so δ2=α. Now the group inverse of β in Hα is β−1 defined by Kjβ−1=rj−1, j=1,2,…,t. Finally, (Kjβ−1)δ=rj−1δ=rt−(j−1)+1. On the other hand we obtain
(Kjδ)β=rt−j+1β=r(t−j+1)+1 and so δβ=β−1δ. □
Acknowledgements
The first author gratefully acknowledges support from the Foundation Calouste Gulbenkian and the University of Trás-os-Montes e Alto Douro. Also, we would like to acknowledge a number of helpful detailed improvements suggested by the referee.
References
Departamento de Matemática, Universidade de Trás-os-Montes e Alto Douro, Quinta de Prados, 5000 Vila Real, Portugal
Email address: [email protected]
Department of Mathematics, University of Essex, Wivenhoe Park, Colchester CO4 3SQ, U.K.
Email address: [email protected]