betaFeedback

WorksMathematics

The monoid of orientation preserving mappings on a chain

Abstract

We introduce new kinds of regular monoids of transformations consisting of mappings which preserve or reverse the orientation of a finite cycle.

Introduction and preliminary concepts

For standard terms in semigroup theory see, for example, [1], [2], [9]. Let XX denote the set {1,2,…,n}\{1,2,\ldots,n\} considered with the standard ordering. Let TnT_n denote the full transformation semigroup on XX, that is the semigroup of all mappings α:X→X\alpha:X\to X under composition. We shall denote composition simply by juxtaposition and shall adopt a right mapping convention; thus if α,β∈Tn\alpha,\beta\in T_n the symbol αβ\alpha\beta denotes the mapping in TnT_n obtained by performing first α\alpha and then β\beta. The range and the set of fixed points of α∈Tn\alpha\in T_n will be denoted by XαX\alpha and F(α)F(\alpha), respectively. The order of XαX\alpha will be called the rank of α\alpha. We shall denote by SnS_n the symmetric group on XX. In this paper we frequently use the cyclic group ZnZ_n with generator a=(12⋯n)a=(12\cdots n). We shall denote by C(n,q)C(n,q) the number of qq-combinations of an nn-set. We shall denote by Y⋅ZY\cdot Z the set product {yz:y∈Y,z∈Z}\{yz:y\in Y,z\in Z\}. We shall call α\alpha an order-preserving mapping if i≤ji\leq j implies iα≤jαi\alpha\leq j\alpha (i,j∈X)(i,j\in X) and let OnO_n denote the submonoid of TnT_n consisting of all order-preserving mappings on XX. The subsemigroup generated by a non-empty subset TT of a semigroup SS is denoted by ⟨T⟩\langle T\rangle. We will denote by E=E(S)E=E(S) the set of idempotents of SS. The set of inverses of y∈Sy\in S is denoted by V(y)V(y).

Various special subsemigroups of TnT_n 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 TnT_n containing OnO_n which will be denoted by OPnOP_n and its elements will be called orientation-preserving mappings. Also, we introduce a subsemigroup Pn=OPn∪ORnP_n=OP_n\cup OR_n of TnT_n, where ORnOR_n denotes the collection of all orientation-reversing mappings.

In Section 2 we introduce the monoid OPnOP_n and show that any element of OPnOP_n can be written as a product of a power of aa followed by an order-preserving mapping. We also show that every kernel class of α∈OPn\alpha\in OP_n is convex. In Section 3 we show that OPnOP_n is a regular semigroup, and we also characterise Green’s relations on OPnOP_n. In Section 4 we consider the subsemigroups of OPnOP_n conjugate with respect to ZnZ_n. From this we obtain a description of the core of OPnOP_n. In Section 5 we show that PnP_n is a regular semigroup and also give some its properties derived from the results about OPnOP_n.

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 nn (or modulo tt where tt is the number of elements of any sequence). A (finite) sequence from a chain A=(a1,a2,…,at)A=(a_1,a_2,\ldots,a_t) 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 ii such that ai>ai+1a_i > a_{i+1}. We say that A=(a1,a2,…,at)A = (a_1,a_2,\ldots,a_t) is anti-cyclic or has anti-clockwise orientation if there exists no more than one subscript ii such that ai<ai+1a_i < a_{i+1}. For example (1,1,2,5,1,1,1)(1,1,2,5,1,1,1) is cyclic, (1,1,1,5,2,1,1)(1,1,1,5,2,1,1) is anti-cyclic whilst (1,1,1,5,1,1,1)(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)A = (a_1,a_2,\ldots,a_t) is cyclic if and only if there exists i∈{0,…,t−1}i \in\{0,\ldots,t-1\} such that

ai+1≤⋯≤at≤a1≤⋯≤aia_{i+1} \le\cdots\le a_t \le a_1 \le\cdots\le a_i

and ii is unique unless the sequence is constant (where we adopt the convention that ≤a1≤⋯≤ai\le a_1 \le\cdots\le a_i is vacuous if i=0i = 0).

The following lemma is immediate by inspection using the remark above:

Lemma 1.1. Let AA be any cyclic [anti-cyclic] sequence. Then AA is anti-cyclic [cyclic] if and only if AA has no more than two distinct values.

If A=(a1,a2,…,at)A = (a_1,a_2,\ldots,a_t) is any sequence then we denote by ArA^r the sequence (at,at−1,…,a1)(a_t,a_{t-1},\ldots,a_1), called the reversed sequence of AA.

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)A = (a_1,a_2,\ldots,a_t) be any sequence from XX. Then AA is cyclic [anti-cyclic] if and only if ArA^r is anti-cyclic [cyclic].

Lemma 1.3. If (a1,a2,…,at)(a_1,a_2,\ldots,a_t) is cyclic [anti-cyclic] then so is

(a) the subsequence (ai1,ai2,…,air)(a_{i_1},a_{i_2},\ldots,a_{i_r}) (i1<i2<⋯<iri_1 < i_2 < \cdots< i_r);

(b) (aj,aj+1,…,at,a1,…,aj−1)(a_j,a_{j+1},\ldots,a_t,a_1,\ldots,a_{j-1}) for all 1≤j≤t1 \le j \le t.

Let k∈{0,1,…,n−1}k \in\{0,1,\ldots,n-1\}. Define a total order ≤k\le_k on XX by

k+1≤kk+2≤k⋯≤kn≤k1≤k⋯≤kkk+1 \le_k k+2 \le_k \cdots\le_k n \le_k 1 \le_k \cdots\le_k k

(where it is understood that ≤k1≤k⋯≤kk\le_k 1 \le_k \cdots\le_k k is vacuous if k=0k = 0). We write i<kji <_k j if i≤kji \le_k j and i≠ji \ne j. Note that i≤kji \le_k j if and only if i−k≤j−ki-k \le j-k.

We say that A=(a1,a2,…,at)A = (a_1,a_2,\ldots,a_t) is cyclic [anti-cyclic] with respect to ≤k\le_k if there exists no more than one subscript ii such that ai+1<kaia_{i+1} <_k a_i [a_i <_k a_{i+1}]. Clearly AA is cyclic with respect to ≤k\le_k if and only if there exists j∈{0,…,t−1}j \in\{0,\ldots,t-1\} such that aj+1≤k⋯≤kat≤ka1≤k⋯≤kaja_{j+1} \le_k \cdots\le_k a_t \le_k a_1 \le_k \cdots\le_k a_j.

Lemma 1.4. Let A=(a1,a2,…,at)A = (a_1,a_2,\ldots,a_t) be any sequence of elements from XX. Then the following are equivalent:

(a) AA is cyclic with respect to ≤0=≤\le_0 = \le.

(b) AA is cyclic with respect to ≤k\le_k for some kk.

(c) AA is cyclic with respect to ≤k\le_k for all kk.

Proof. Clearly we only need to prove that (b) implies (c). Suppose that (b) holds so that AA is cyclic with respect to ≤k\le_k for some kk. Then, for some jj,

k+1≤kaj+1≤k⋯≤kat≤ka1≤k⋯≤kaj≤kk.k+1 \le_k a_{j+1} \le_k \cdots\le_k a_t \le_k a_1 \le_k \cdots\le_k a_j \le_k k.

Either k+2≤kaj+1k+2 \le_k a_{j+1}, in which case

aj+1≤k+1⋯≤k+1at≤k+1a1≤k+1⋯≤k+1aj,a_{j+1} \le_{k+1} \cdots\le_{k+1} a_t \le_{k+1} a_1 \le_{k+1} \cdots\le_{k+1} a_j,

or k+1=aj+1=⋯=aj+s<kk+2≤kaj+s+1≤k⋯≤kajk+1=a_{j+1}=\cdots=a_{j+s}<_{k} k+2\le_{k}a_{j+s+1}\le_{k}\cdots\le_{k}a_j for some s∈{1,…,t}s\in\{1,\ldots,t\}, in which case

aj+s+1≤k+1⋯≤k+1aj≤k+1⋯≤k+1aj+s.a_{j+s+1}\le_{k+1}\cdots\le_{k+1}a_j\le_{k+1}\cdots\le_{k+1}a_{j+s}.

In either case AA is cyclic with respect to ≤k+1\le_{k+1}, and then (c) follows by induction. □

The monoid OPnOP_n

Let α∈Tn\alpha\in T_n. We say that α\alpha is an orientation-preserving mapping on XX if the sequence (1α,2α,…,nα)(1\alpha,2\alpha,\ldots,n\alpha) is cyclic. We note, by Lemma 1.4, that this sequence is then cyclic with respect to ≤k\le_k for all 0≤k≤n−10\le k\le n-1. The collection of all orientation-preserving mappings on XX will be denoted by OPnOP_n.

Lemma 2.1. Let α∈OPn\alpha\in OP_n and let (b1,…,bt)(b_1,\ldots,b_t) be a cyclic sequence of members of XX. Then the sequence (b1α,…,btα)(b_1\alpha,\ldots,b_t\alpha) is also cyclic.

Proof. We have, for some i∈{0,…,t−1}i\in\{0,\ldots,t-1\}

bi+1≤bi+2≤⋯≤bt≤b1≤⋯≤bi.b_{i+1}\le b_{i+2}\le\cdots\le b_t\le b_1\le\cdots\le b_i.

and, for some j∈{0,…,n−1}j\in\{0,\ldots,n-1\},

(j+1)α≤(j+2)α≤⋯≤nα≤1α≤⋯≤jα.(j+1)\alpha\le(j+2)\alpha\le\cdots\le n\alpha\le1\alpha\le\cdots\le j\alpha.

In particular α\alpha preserves ≤\le on {j+1,…,n}\{j+1,\ldots,n\} and on {1,…,j}\{1,\ldots,j\}. Thus if bi+1∈{j+1,…,n}b_{i+1}\in\{j+1,\ldots,n\} or bi∈{1,…,j}b_i\in\{1,\ldots,j\} then certainly

bi+1α≤bi+2α≤⋯≤btα≤b1α≤⋯≤biαb_{i+1}\alpha\le b_{i+2}\alpha\le\cdots\le b_t\alpha\le b_1\alpha\le\cdots\le b_i\alpha

and we have finished. Suppose then that bi+1<j+1b_{i+1}<j+1 and bi>jb_i>j. Then, for some rr, either

i+1<r≤t,bi+1,…,br−1∈{1,…,j},i+1<r\le t,\qquad b_{i+1},\ldots,b_{r-1}\in\{1,\ldots,j\},

or

1≤r≤i,bi+1,…,bt,b1,…,br−1∈{1,…,j},br,…,bi∈{j+1,…,n}.1\le r\le i,\qquad b_{i+1},\ldots,b_t,b_1,\ldots,b_{r-1}\in\{1,\ldots,j\},\qquad b_r,\ldots,b_i\in\{j+1,\ldots,n\}.

In either case

brα≤⋯≤btα≤b1α≤⋯≤br−1α,b_r\alpha\le\cdots\le b_t\alpha\le b_1\alpha\le\cdots\le b_{r-1}\alpha,

as required. □

As a corollary we immediately obtain the following result:

Theorem 2.2. OPnOP_n is a submonoid of TnT_n containing OnO_n.

The following is immediate from the definitions of order-preserving mapping on XX and cyclic sequence:

Proposition 2.3. For non-constant α∈OPn\alpha\in OP_n, α\alpha is an order-preserving mapping if and only if 1α<nα1\alpha<n\alpha.

We may regard the members of XX as being placed clockwise around the circumference of a circle so that the integer ii lies between i−1i-1 and i+1i+1 (reduced modulo nn). Any sequence of 3 distinct members, i,j,ki,j,k, of XX then defines either a clockwise orientation or an anti-clockwise orientation of the circle according as (i,j,k)(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 XX, and follows immediately from Lemmas 2.1 and 1.2,

Proposition 2.4. Let α∈OPn\alpha\in OP_n and (i,j,k)(i,j,k) be any triple of 3 distinct members of XX. If the entries are distinct, then the triple (iα,jα,kα)(i\alpha,j\alpha,k\alpha) defines the same orientation as (i,j,k)(i,j,k).

An interval [i,k][i,k] for i,k∈Xi,k \in X may be expressed clockwise by [i,k]={i,i+1,…,k−1,k}[i,k]=\{i,i+1,\ldots,k-1,k\} or anti-clockwise by [i,k]={i,i−1,…,k+1,k}[i,k]=\{i,i-1,\ldots,k+1,k\}. Henceforth, all intervals are expressed clockwise.

A set K⊆XK \subseteq X is convex if KK has the form [i,i+t][i,i+t], for some i∈Xi \in X and 0≤t≤n−10 \leq t \leq n-1. If α∈OPn\alpha\in OP_n, let us call the subsets xα−1x\alpha^{-1} (x∈Xαx \in X\alpha) of XX the kernel classes of α\alpha; they are the classes of equivalence relation

Πα={(x,y)∈X×X:xα=yα}.\Pi_\alpha=\{(x,y)\in X\times X:x\alpha=y\alpha\}.

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⁡α\ker\alpha for the set of kernel classes of α\alpha. It is easy to show that every kernel class of α∈On\alpha\in O_n is convex; indeed they are intervals of XX. Later, we prove more generally that if α∈OPn\alpha\in OP_n, then every kernel class of α\alpha is convex also.

The nn-cycle a=(12⋯n)a=(12\cdots n) lies in OPnOP_n as the sequence of images of the ordered set XX under aa, (2,…,n,1)(2,\ldots,n,1), is cyclic.

We consider S=⟨On∪{a}⟩S=\langle O_n\cup\{a\}\rangle, and let g∈Ong\in O_n. Clearly, if gg is constant, then arg=g∈Ona^r g=g\in O_n, for all 0≤r≤n−10\leq r\leq n-1. We claim that, if gg is not a constant mapping, then arg∉Ona^r g\notin O_n, for all 1≤r≤n−11\leq r\leq n-1. Suppose that gg is not constant. Since gg is an order-preserving mapping it follows that i=1g<ng=ji=1g<ng=j. Now n−r<n−r+1n-r<n-r+1 but (n−r)arg=ng=j>i=1g=(n−r+1)arg(n-r)a^r g=ng=j>i=1g=(n-r+1)a^r g, showing that arg∉Ona^r g\notin O_n. Hence the next result follows:

Lemma 2.5. Let g∈Ong\in O_n. Then arg∈Ona^r g\in O_n, (1≤r≤n−1)(1\leq r\leq n-1), if and only if gg is constant.

Next we give an interesting factorization of OPnOP_n and we show that any orientation-preserving mapping is a product of a power of aa followed by an order-preserving mapping.

Theorem 2.6. Each α∈OPn\alpha\in OP_n has a factorization α=arf\alpha=a^r f (0≤r≤n−1, f∈On)(0\leq r\leq n-1,\ f\in O_n) which is unique unless α\alpha is constant. In particular OPn=SOP_n=S.

Proof. Let α∈OPn\alpha\in OP_n. We claim that α=arf\alpha=a^r f for some f∈Onf\in O_n and 0≤r≤n−10\leq r\leq n-1. If α\alpha is a constant mapping then we take f=αf=\alpha and rr arbitrary. Suppose that α\alpha is not a constant mapping. Then there exists i∈Xi\in X such that iα>(i+1)αi\alpha>(i+1)\alpha and we have that

min⁡1≤j≤njα=(i+1)α≤⋯≤nα≤1α≤⋯≤iα=max⁡1≤j≤njα.\min_{1\leq j\leq n}j\alpha=(i+1)\alpha\leq\cdots\leq n\alpha\leq1\alpha\leq\cdots\leq i\alpha=\max_{1\leq j\leq n}j\alpha.

We define ff by xf=(x+i)αxf=(x+i)\alpha for x∈Xx\in X. Then ff lies in OnO_n as 1f=(1+i)α≤2f=(2+i)α≤⋯≤nf=(n+i)α=iα1f=(1+i)\alpha\leq2f=(2+i)\alpha\leq\cdots\leq nf=(n+i)\alpha=i\alpha. Put r=n−ir=n-i. Then j(arf)=(j+r)f=(j+r+i)α=(j+n)α=jαj(a^r f)=(j+r)f=(j+r+i)\alpha=(j+n)\alpha=j\alpha, 1≤j≤n1\leq j\leq n. Next suppose α\alpha is not constant and α=akf=alg\alpha=a^k f=a^l g, (0≤k,l≤n−1)(0\leq k,l\leq n-1), f,g∈Onf,g\in O_n. Then f=al−kgf=a^{l-k}g, so that, by Lemma 2.5, l−k=0l-k=0, since gg is not constant, whence l=kl=k and f=gf=g.

Now, using the known cardinalities of OnO_n (see for example [7]) and ZnZ_n, we obtain the following result:

Corollary 2.7. ∣S∣=∣OPn∣=nC(2n−1,n−1)−n(n−1)|S|=|OP_n|=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),|S|=|Z_n|(|O_n|-n)+n=n|O_n|-n^2+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\alpha\in OP_n and KK be any kernel class of α\alpha. Then KK is convex.

Proof. Let α∈OPn\alpha\in OP_n. Then, for some ii,

(i+1)α≤⋯≤nα≤1α≤⋯≤iα.(i+1)\alpha\le\cdots\le n\alpha\le1\alpha\le\cdots\le i\alpha.

Thus if jα=kαj\alpha= k\alpha for some j≤i<kj \le i < k then jα=(j+1)α=⋯=(k−1)α=kαj\alpha= (j+1)\alpha= \cdots= (k-1)\alpha= k\alpha, which is sufficient to prove that the kernel classes are convex.

In [7] Howie showed that ∣E(On)∣=F2n|E(O_n)| = F_{2n}, the 2n2nth Fibonacci number, through solution of a certain difference equation. The next lemma gives another proof of this.

Lemma 2.9. Let FnF_n be the nnth Fibonacci number. Then, for all n≥1n \ge1,

(i)∣E(On)∣=F2n;(ii)∣E(OPn)∣=n+∑k=1n−1k2F2(n−k).\begin{aligned} (i)\quad|E(O_n)| &= F_{2n}; \qquad(ii)\quad|E(OP_n)| = n + \sum_{k=1}^{n-1} k^2 F_{2(n-k)}. \end{aligned}

Proof. (i) Let en=∣E(On)∣e_n = |E(O_n)|. Let e∈E(On+1)e \in E(O_{n+1}). We consider two cases:

Xe⊆XXe \subseteq X: In this case e∣X∈E(On)e|_X \in E(O_n). Now ne≤(n+1)ene \le(n+1)e, as ee is order-preserving, and (n+1)e≤n(n+1)e \le n as Xe⊆XXe \subseteq X. Applying the order-preserving mapping ee to the latter inequality gives (n+1)e2≤ne(n+1)e^2 \le ne, and since e2=ee^2=e this says (n+1)e≤ne(n+1)e \le ne. Therefore (n+1)e=ne(n+1)e = ne and so ∣{e∈E(On+1):Xe⊆X}∣=en|\{e \in E(O_{n+1}): Xe \subseteq X\}| = e_n.

Xe⊈XXe \not\subseteq X: Let ii be least such ie=(n+1)ie=(n+1). Then je=n+1je=n+1, for all j≥ij \ge i. In general je≤i−1je \le i-1, for all j≤i−1j \le i-1 and so (i−1)e≤i−1(i-1)e \le i-1. Hence, ∣{e∈E(On+1):i least such that ie=(n+1)}∣=ei−1|\{e \in E(O_{n+1}): i\text{ least such that }ie=(n+1)\}| = e_{i-1}. Summing over all values of ii and adding the previous case yields the recurrence

en+1=en+(en+en−1+⋯+e1+1),e_{n+1}=e_n+(e_n+e_{n-1}+\cdots+e_1+1),

from which the result follows by induction.

(ii) Now let en=∣E(OPn)∣e_n=|E(OP_n)|. We prove that the numbers of idempotents ee in OPnOP_n with ∣e−1∣=k|e^{-1}|=k, (1≤k≤n−1)(1\le k\le n-1) is k2F2(n−k)k^2F_{2(n-k)}, from which the result will follow. We build such an idempotent e∈E(OPn)e\in E(OP_n) as follows:

There are kk choices for the convex set 1e−11e^{-1}: {n−k+2,n−k+3,…,1}\{n-k+2,n-k+3,\ldots,1\}, {n−k+3,n−k+4,…,1,2},…,{1,2,…,k}\{n-k+3,n-k+4,\ldots,1,2\},\ldots,\{1,2,\ldots,k\}. Once 1e−11e^{-1} is chosen, there are kk choices for 1e1e. Suppose that 1e−1={t,t+1,…,n,1,2,…,s}1e^{-1}=\{t,t+1,\ldots,n,1,2,\ldots,s\} say, (s=k+t−n−1)(s=k+t-n-1). Put 1e−1=K1e^{-1}=K. Then e∣X∖Ke|_{X\setminus K} is an idempotent on the chain C={s+1,s+2,…,t−1}C=\{s+1,s+2,\ldots,t-1\}, ∣C∣=n−k|C|=n-k. By (i) it follows that ee can be extended from e∣Ke|_K to an idempotent in OPnOP_n, in F2(n−k)F_{2(n-k)} ways. Multiplying the number of choices in each of the 3 stages of the construction of ee gives the number of possibilities as kkF2(n−k)=k2F2(n−k)kkF_{2(n-k)}=k^2F_{2(n-k)}, as required.

Theorem 2.10

Theorem 2.10. For all n≥1n \ge1, ∣E(OPn)∣=F2n−1+F2n+1−(n2−n+2)|E(OP_n)|=F_{2n-1}+F_{2n+1}-(n^2-n+2).

Proof. We use the fact that for all n≥0n\ge0, F0+F2+⋯+F2n=F2n+1−1F_0+F_2+\cdots+F_{2n}=F_{2n+1}-1 and F1+F3+⋯+F2n+1=F2n+2F_1+F_3+\cdots+F_{2n+1}=F_{2n+2}, each of which can be proved readily by induction. Let en=∣E(OPn)∣e_n=|E(OP_n)|. We seek to simplify the formula given by the previous lemma. First note that ∑k=0n−1F2(n−k)=∑k=1nF2k=F2n+1−1\sum_{k=0}^{n-1}F_{2(n-k)}=\sum_{k=1}^{n}F_{2k}=F_{2n+1}-1 and

∑k=1n−1kF2(n−k)=∑j=1n−1∑k=jn−1F2(n−k)=∑j=1n−1(F2+F4+⋯+F2(n−j))=∑j=1n−1(F2(n−j)+1−1)=F3+F5+⋯+F2n−1−(n−1)=F2n−n.\begin{aligned} \sum_{k=1}^{n-1}kF_{2(n-k)} &=\sum_{j=1}^{n-1}\sum_{k=j}^{n-1}F_{2(n-k)} =\sum_{j=1}^{n-1}(F_2+F_4+\cdots+F_{2(n-j)})\\ &=\sum_{j=1}^{n-1}(F_{2(n-j)+1}-1) =F_3+F_5+\cdots+F_{2n-1}-(n-1)\\ &=F_{2n}-n. \end{aligned}

Also we have

en+1−en=(n+1)−n+∑k=1nk2F2(n+1−k)−∑k=1n−1k2F2(n−k)=1+∑k=1nk2F2(n−(k−1))−∑k=1n−1k2F2(n−k)=1+∑k=0n−1(k+1)2F2(n−k)−∑k=0n−1k2F2(n−k)=1+∑k=0n−1F2(n−k)+2∑k=1n−1kF2(n−k)=1+(F2n+1−1)+2(F2n−n)=F2n+F2n+2−2n\begin{aligned} e_{n+1}-e_n &= (n+1)-n+\sum_{k=1}^{n} k^2F_{2(n+1-k)}-\sum_{k=1}^{n-1} k^2F_{2(n-k)}\\ &=1+\sum_{k=1}^{n} k^2F_{2(n-(k-1))}-\sum_{k=1}^{n-1} k^2F_{2(n-k)}\\ &=1+\sum_{k=0}^{n-1}(k+1)^2F_{2(n-k)}-\sum_{k=0}^{n-1}k^2F_{2(n-k)}\\ &=1+\sum_{k=0}^{n-1}F_{2(n-k)}+2\sum_{k=1}^{n-1}kF_{2(n-k)}\\ &=1+(F_{2n+1}-1)+2(F_{2n}-n)\\ &=F_{2n}+F_{2n+2}-2n \end{aligned}

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(12n(n+1))=2(F2n+1−1)+F2n+2−n(n+1)=F2n+1+F2n+3−(n2+n+2),\begin{aligned} e_{n+1}&=e_n+(F_{2n}+F_{2n+2})-2n=\cdots=\\ &=e_1+(F_2+F_4)+(F_4+F_6)+\cdots+(F_{2n-2}+F_{2n})+(F_{2n}+F_{2n+2})\\ &\quad-2(n+(n-1)+(n-2)+\cdots+1)\\ &=2(F_2+F_4+\cdots+F_{2n})+F_{2n+2}-2\left(\frac{1}{2}n(n+1)\right)\\ &=2(F_{2n+1}-1)+F_{2n+2}-n(n+1)\\ &=F_{2n+1}+F_{2n+3}-(n^2+n+2), \end{aligned}

or en=F2n−1+F2n+1−(n2−n+2)e_n=F_{2n-1}+F_{2n+1}-(n^2-n+2), as required. □\square

Next we describe On⋅ZnO_n\cdot Z_n and show that On⋅Zn≠OPnO_n\cdot Z_n\ne OP_n.

Proposition 2.11. On⋅Zn={α∈OPn:1α≠nα}∪{α∈OPn:∣Xα∣=1}O_n\cdot Z_n=\{\alpha\in OP_n:1\alpha\ne n\alpha\}\cup\{\alpha\in OP_n:|X\alpha|=1\}.

Proof. Let α∈On⋅Zn\alpha\in O_n\cdot Z_n be such that α\alpha is not a constant mapping. Let α=fam\alpha=f a^m for some f∈Onf\in O_n and 0≤m≤n−10\le m\le n-1. Then 1f≠nf1f\ne nf for otherwise α\alpha would be constant, whence 1α≠nα1\alpha\ne n\alpha.

Conversely, let α∈OPn\alpha\in OP_n. If α\alpha is a constant mapping then α∈On\alpha\in O_n and α=αa0∈On⋅Zn\alpha=\alpha a^0\in O_n\cdot Z_n. Now suppose that 1α≠nα1\alpha\ne n\alpha. We claim that α=fam\alpha=f a^m for some f∈Onf\in O_n and 0≤m≤n−10\le m\le n-1. If nα>1αn\alpha>1\alpha then, by Proposition 2.3, α\alpha is an order-preserving mapping and so α=αa0\alpha=\alpha a^0 is a required factorization. Suppose that nα<1αn\alpha<1\alpha and write 1α=k1\alpha=k. Put m=n−k+1m=n-k+1. Then we define the mapping ff as follows:

xf=xα+m(x∈X).xf=x\alpha+m\qquad(x\in X).

Let b∈Xb\in X. Hence b(fa−m)=(bf)a−m=bf−m=(bα+m)−m=bαb(fa^{-m})=(bf)a^{-m}=bf-m=(b\alpha+m)-m=b\alpha and so fa−m=αfa^{-m}=\alpha, which implies that f=αam∈OPnf=\alpha a^m\in OP_n. It remains to prove that f∈Onf\in O_n. Now 1f=11f=1 as 1f=k+m=11f=k+m=1, nf=nα+m≠k+mnf=n\alpha+m\ne k+m, as nα≠1α=kn\alpha\ne1\alpha=k. Hence 1f<nf1f<nf, f∈OPnf\in OP_n, and so f∈Onf\in O_n, by Proposition 2.3. □\square

From this result and the fact that OPn=Zn⋅OnOP_n=Z_n\cdot O_n we can conclude that

On⋅(Zn⋅On)=On⋅(OPn)=OPnO_n\cdot(Z_n\cdot O_n)=O_n\cdot(OP_n)=OP_n

and so (On⋅Zn)2=OPn(O_n\cdot Z_n)^2=OP_n.

Some properties of OPnOP_n

It is well known that OnO_n is a regular semigroup. We can deduce from this that OPnOP_n is a regular semigroup.

Let α=akf∈OPn\alpha= a^k f \in OP_n for some f∈Onf \in O_n and some kk (0≤k≤n−10 \leq k \leq n - 1). It is routine to check that f′an−k∈V(akf)f'a^{n-k} \in V(a^k f), where f′∈V(f)f' \in V(f) in OnO_n, though in Section 4 we show that not all inverses of akfa^k f are of this form. The next result follows from this together with Theorem 2.6.

Theorem 3.1. OPnOP_n is a regular semigroup.

Remark. Since OPnOP_n is regular, we have that ROPn=RTn∩(OPn×OPn)\mathcal{R}^{OP_n} = \mathcal{R}^{T_n} \cap(OP_n \times OP_n), LOPn=LTn∩(OPn×OPn)\mathcal{L}^{OP_n} = \mathcal{L}^{T_n} \cap(OP_n \times OP_n), HOPn=HTn∩(OPn×OPn)\mathcal{H}^{OP_n} = \mathcal{H}^{T_n} \cap(OP_n \times OP_n), that is, for α,β∈OPn\alpha,\beta\in OP_n, αRβ⟺ker⁡α=ker⁡β\alpha\mathcal{R}\beta\Longleftrightarrow\ker\alpha= \ker\beta, αLβ⟺Xα=Xβ\alpha\mathcal{L}\beta\Longleftrightarrow X\alpha= X\beta, αHβ⟺Xα=Xβ\alpha\mathcal{H}\beta\Longleftrightarrow X\alpha= X\beta and ker⁡α=ker⁡β\ker\alpha= \ker\beta, and since OPnOP_n is a finite semigroup we have that DOPn=JOPn\mathcal{D}^{OP_n} = \mathcal{J}^{OP_n}.

Using the factorization of OPnOP_n given by Theorem 2.6 we can see easily the following result relating the L\mathcal{L}-classes of OPnOP_n and OnO_n:

Lemma 3.2. Let α=akf\alpha= a^k f and β=amg\beta= a^m g for some 0≤k,m≤n−10 \leq k,m \leq n - 1 and f,g∈Onf,g \in O_n. Then αLβ\alpha\mathcal{L}\beta in OPnOP_n if and only if fLgf\mathcal{L}g in OnO_n.

However with R\mathcal{R}-classes the implication holds in neither direction for n>2n > 2. For example, let f=(123223)f = \begin{pmatrix}1&2&3\\2&2&3\end{pmatrix} and g=(123113)g = \begin{pmatrix}1&2&3\\1&1&3\end{pmatrix}. Then ker⁡f=ker⁡g\ker f = \ker g. However α=a2f=(123322)\alpha= a^2f = \begin{pmatrix}1&2&3\\3&2&2\end{pmatrix}, β=ag=(123131)\beta= ag = \begin{pmatrix}1&2&3\\1&3&1\end{pmatrix} and ker⁡α≠ker⁡β\ker\alpha\ne\ker\beta.

Next, with f=(123112)f = \begin{pmatrix}1&2&3\\1&1&2\end{pmatrix}, g=(123133)∈O3g = \begin{pmatrix}1&2&3\\1&3&3\end{pmatrix} \in O_3, let α=af=(123121)\alpha= af = \begin{pmatrix}1&2&3\\1&2&1\end{pmatrix} and β=a2g=(123313)\beta= a^2g = \begin{pmatrix}1&2&3\\3&1&3\end{pmatrix}. Then ker⁡α=ker⁡β\ker\alpha= \ker\beta, but ker⁡f≠ker⁡g\ker f \ne\ker g.

Let α,β∈OPn\alpha,\beta\in OP_n. We have that αRβ\alpha\mathcal{R}\beta if and only if ker⁡α=ker⁡β\ker\alpha= \ker\beta, and kernel classes are convex, so there is a one-to-one correspondence between R\mathcal{R}-classes of rank tt, (t≥2t \geq2), and choices of a tt-set from XX as follows: write the given tt-set as {a1,a2,…,at}\{a_1,a_2,\ldots,a_t\} with a1<a2<⋯<ata_1 < a_2 < \cdots< a_t; the kernel classes of the corresponding R\mathcal{R}-class are then {a1,a1+1,…,a2−1},{a2,a2+1,…,a3−1},…,{at,at+1,…,a1−1}\{a_1,a_1+1,\ldots,a_2-1\},\{a_2,a_2+1,\ldots,a_3-1\},\ldots,\{a_t,a_t+1,\ldots,a_1-1\}; the aia_i are called the initial points of the corresponding kernel class; conversely, the common set of initial points of the kernel classes of an R\mathcal{R}-class of OPnOP_n yields a tt-set of XX, and these two operations are mutually inverse.

We have αLβ\alpha\mathcal{L}\beta if and only if Xα=XβX\alpha= X\beta, so L\mathcal{L}-classes also correspond to choices of a tt-set from XX, where t=∣Xα∣t = |X\alpha|. Hence for t≥2t \geq2 an H\mathcal{H}-class HH of OPnOP_n can be coded as a choice of an ordered pair of tt-sets (K,R)(K,R) from XX where K={a1,…,at}K = \{a_1,\ldots,a_t\} is the common tt-set of the initial points of the kernel classes of the corresponding R\mathcal{R}-class and R={r1,…,rt}R = \{r_1,\ldots,r_t\} (r1<r2<⋯<rtr_1 < r_2 < \cdots< r_t) is the common range of all mappings in the corresponding L\mathcal{L}-class.

Let α∈H\alpha\in H with aiα=r1a_i\alpha= r_1, say. By Lemma 1.3 (b),

(ai,ai+1,…,at,a1,…,ai−1)(a_i,a_{i+1},\ldots,a_t,a_1,\ldots,a_{i-1})

is cyclic, and since α∈OPn\alpha\in OP_n we have from Lemma 2.1 that the same is true of (aiα,ai+1α,…,ai−1α)(a_i\alpha,a_{i+1}\alpha,\ldots,a_{i-1}\alpha). However, aiα=r1=min⁡Xαa_i\alpha= r_1 = \min X\alpha, and since the aja_j form a transversal of the kernel classes of α\alpha we obtain:

aiα<ai+1α<⋯<atα<a1α<⋯<ai−1α.a_i\alpha< a_{i+1}\alpha< \cdots< a_t\alpha< a_1\alpha< \cdots< a_{i-1}\alpha.

Hence aiα=r1a_i\alpha= r_1, ai+1α=r2,…,ai−1α=rta_{i+1}\alpha= r_2,\ldots,a_{i-1}\alpha= r_t and so α∈H\alpha\in H is defined by the pair of tt-sets (K,R)(K,R) together with the choice of ii such that aiα=r1a_i\alpha= r_1.

Conversely, for a given pair (K,R)(K,R) and a given choice of ii we can construct α∈H\alpha\in H as follows: write the kernel classes of α\alpha as K1,K2,…,KtK_1,K_2,\ldots,K_t where aja_j is the initial point of KjK_j. Define α\alpha by Kjα=rj−i+1K_j\alpha=r_{j-i+1}. In summary we have:

Theorem 3.3. For t≥2t \ge2 there is a one-to-one correspondence Φ\Phi between the set of triples (K,R,i)(K,R,i) where KK and RR are ordered tt-sets of XX and 1≤i≤t1 \le i \le t and {α∈OPn:∣Xα∣=t}\{\alpha\in\mathrm{OP}_n : |X\alpha|=t\} whereby (K,R,i)↦α(K,R,i) \mapsto\alpha, where each aj∈Ka_j \in K is an initial point of a kernel class of α\alpha and ajα=rj−i+1a_j\alpha=r_{j-i+1}. Moreover Hα={Φ(K,R,i):i=1,…,t}H_\alpha=\{\Phi(K,R,i):i=1,\ldots,t\}, so ∣Hα∣=t|H_\alpha|=t.

Suppose α,β∈OPn\alpha,\beta\in\mathrm{OP}_n with ∣Xα∣=∣Xβ∣=t|X\alpha|=|X\beta|=t say. Let KK be the set of initial points of the kernel classes of α\alpha and let R=XβR=X\beta. Let γ\gamma be any member of the H\mathcal{H}-class determined by the pair (K,R)(K,R). Then αRγLβ\alpha\mathcal{R}\gamma\mathcal{L}\beta, so αDOPnβ\alpha\mathcal{D}_{\mathrm{OP}_n}\beta. Conversely, if αDOPnβ\alpha\mathcal{D}_{\mathrm{OP}_n}\beta, then αDTnβ\alpha\mathcal{D}_{T_n}\beta whence ∣Xα∣=∣Xβ∣|X\alpha|=|X\beta|. Hence the next result follows:

Proposition 3.4. Let α,β∈OPn\alpha,\beta\in\mathrm{OP}_n. Then αDOPnβ\alpha\mathcal{D}_{\mathrm{OP}_n}\beta if and only if ∣Xα∣=∣Xβ∣|X\alpha|=|X\beta|.

Next we give an alternative way of finding the order of OPn\mathrm{OP}_n. Let α∈OPn\alpha\in\mathrm{OP}_n be such that ∣Xα∣=t|X\alpha|=t for some 1≤t≤n1 \le t \le n. Let DtD_t denote the D\mathcal{D}-class containing α\alpha. By Proposition 3.4 we have Dt={β∈OPn:∣Xβ∣=t}D_t=\{\beta\in\mathrm{OP}_n:|X\beta|=t\}. Hence, if t=1t=1 we have nn constants mappings. By Theorem 3.3, β\beta is determined by the pair (Kβ,Xβ)(K_\beta,X\beta), where KβK_\beta is the tt-set of initial points of the kernel classes of β\beta, together with the choice of ii such that aiβ=r1a_i\beta=r_1 (ai∈Kβa_i \in K_\beta). Then for t≥2t \ge2 we have C(n,t)C(n,t) possibilities for KβK_\beta, C(n,t)C(n,t) choices for XβX\beta, and tt choices for ii. Hence the order of DtD_t (t≥2t \ge2) is given by

∣Dt∣=tC(n,t)C(n,t).|D_t|=tC(n,t)C(n,t).

Hence the order of OPn\mathrm{OP}_n is given by

∣OPn∣=n+∑t=2ntC2(n,t).|\mathrm{OP}_n|=n+\sum_{t=2}^{n}tC^2(n,t).

Note that ∑t=1nC(n−1,t−1)C(n,t)=∑t=1nC(n−1,n−t)C(n,t)\sum_{t=1}^{n}C(n-1,t-1)C(n,t)=\sum_{t=1}^{n}C(n-1,n-t)C(n,t) is the coefficient of xnx^n in the expansion of (1+x)n−1(1+x)n=(1+x)2n−1(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)\sum_{t=1}^{n}C(n-1,t-1)C(n,t)=C(2n-1,n), and this leads to ∑t=1ntC2(n,t)=nC(2n−1,n−1)\sum_{t=1}^{n}tC^2(n,t)=nC(2n-1,n-1); thus we can recover Corollary 2.7:

∣OPn∣=n+nC(2n−1,n−1)−n2.|\mathrm{OP}_n|=n+nC(2n-1,n-1)-n^2.

Next we give a description of the H\mathcal{H}-classes of α∈OPn\alpha\in\mathrm{OP}_n. Let α∈E(OPn)\alpha\in E(\mathrm{OP}_n) and take K1,K2,…,KtK_1,K_2,\ldots,K_t; r1,r2,…,rtr_1,r_2,\ldots,r_t and ii as before. Since α∈E(OPn)\alpha\in E(\mathrm{OP}_n) the {rj}\{r_j\} form a transversal of the kernel classes, and so

rj−i+1∈Kj,j=1,2,…,t.(1)r_{j-i+1}\in K_j,\qquad j=1,2,\ldots,t. \tag*{(1)}

Let β=Φ(K,R,i−1)\beta=\Phi(K,R,i-1). Hence,

Kjβ=ajβ=rj−(i−1)+1=rj−i+2,j=1,2,…,t.K_j\beta=a_j\beta=r_{j-(i-1)+1}=r_{j-i+2},\qquad j=1,2,\ldots,t.

Next we show by induction on pp that ai−1βp=rpa_{i-1}\beta^p=r_p for all p=1,2,…,tp=1,2,\ldots,t. For p=1p=1, we have that ai−1β=ri−1−i+2=r1a_{i-1}\beta=r_{i-1-i+2}=r_1. For p≥2p \ge2,

ai−1βp=(ai−1βp−1)β=rp−1β.a_{i-1}\beta^p=(a_{i-1}\beta^{p-1})\beta=r_{p-1}\beta.

Put j−i+1=p−1j-i+1=p-1 in (1); we get j=p+i−2j=p+i-2. Hence

ai−1βp=rp−1β=Kp+i−2β=rp+i−2−i+2=rp.a_{i-1}\beta^p=r_{p-1}\beta=K_{p+i-2}\beta=r_{p+i-2-i+2}=r_p.

It follows that ∣⟨β⟩∣≥t|\langle\beta\rangle|\ge t. Since β∈Hα\beta\in H_\alpha and ∣Hα∣=t|H_\alpha|=t we see that ⟨β⟩=Hα\langle\beta\rangle=H_\alpha. Hence the next result follows:

Lemma 3.5. Let α∈E(OPn)\alpha\in E(\mathrm{OP}_n). Let HαH_\alpha be the H\mathcal{H}-class containing α\alpha. Then Hα=⟨β⟩H_\alpha=\langle\beta\rangle and ∣Hα∣=∣Xα∣|H_\alpha|=|X\alpha|.

Corollary 3.6. The maximal subgroups of the D\mathcal{D}-class DtD_t of OPnOP_n are cyclic of order tt. In particular, every subgroup of OPnOP_n is cyclic.

Conjugate subsemigroups of OnO_n

In this section we study some properties of subsemigroups of OnO_n conjugate with respect to ZnZ_n, and their links with the semigroup OPnOP_n. Let

Onk={a−kfak:f∈On},(0≤k≤n−1),O_n^k=\{a^{-k}fa^k:f\in O_n\},\qquad(0\leq k\leq n-1),

where a=(12⋯n)a=(12\cdots n) is the fixed generator of ZnZ_n.

Let α=amf∈OPn\alpha=a^mf\in OP_n for some f∈Onf\in O_n and some 0≤m≤n−10\leq m\leq n-1. For each kk, (0≤k≤n−1)(0\leq k\leq n-1), consider the mapping φk:On⟶OPn\varphi_k:O_n\longrightarrow OP_n whereby hφk=a−khakh\varphi_k=a^{-k}ha^k, (h∈On)(h\in O_n). Let us write hak=a−khakha^k=a^{-k}ha^k. It is easy to verify that φk\varphi_k is an injective morphism with image OnkO_n^k.

Lemma 4.1. OnkO_n^k is a submonoid of OPnOP_n and φk\varphi_k is an isomorphism between OnO_n and OnkO_n^k.

Proof. This is an immediate consequence of the general fact that conjugation by a unit is always a semigroup isomorphism.

Proposition 4.2. OnkO_n^k is the monoid of all order-preserving mappings on XX with respect to ≤k\leq_k.

Proof. Let hh be any element of OnkO_n^k. Hence h=a−kfakh=a^{-k}fa^k for some f∈Onf\in O_n. Let i,j∈Xi,j\in X such that i≤kji\leq_k j. Hence i−k≤j−ki-k\leq j-k, so ia−kf=(i−k)f≤(j−k)f=ja−kfia^{-k}f=(i-k)f\leq(j-k)f=ja^{-k}f since ff is order-preserving, and so ih=(i−k)f+k≤k(j−k)f+k=jhih=(i-k)f+k\leq_k(j-k)f+k=jh.

Conversely let gg be any order-preserving mapping on the chain (X,≤k)(X,\leq_k). Put f=akga−kf=a^kga^{-k}. By similar reasoning f∈Onf\in O_n, so g=a−kfak∈Onkg=a^{-k}fa^k\in O_n^k, and the proposition is proved.

Let TT be any semigroup. Following standard terminology if E=E(T)E=E(T) is the set of idempotents of TT, then ⟨E⟩\langle E\rangle is called the core of TT, and TT is said to be a semiband if TT equals its own core.

We will denote by GbSG_b^S the G\mathcal{G}-class in SS containing bb where G\mathcal{G} is any Green’s relations, SS is any semigroup and bb is an element in SS. We shall show that ∣E(RfOn)∣=∣E(RαOPn)∣|E(R_f^{O_n})|=|E(R_\alpha^{OP_n})|. First, we need the following result in order to show that φk\varphi_k restricted to E(RfOn)E(R_f^{O_n}) is a bijection onto E(Ra−kfakOPn)E(R_{a^{-k}fa^k}^{OP_n}).

Lemma 4.3. Let g∈Ong\in O_n, e∈E(OPn)e\in E(OP_n) such that eROPnge\mathcal{R}^{OP_n}g. Then e∈One\in O_n and eROnge\mathcal{R}^{O_n}g.

Proof. Observe that ker⁡e=ker⁡g\ker e=\ker g, which is a convex partition of the chain XX. Let i,ji,j be any two elements on XX such that i≤ji\leq j. If i,ji,j are in the same kernel class then ie=jeie=je. Otherwise, i∈Ki=xe−1i\in K_i=xe^{-1} and j∈Kj=ye−1j\in K_j=ye^{-1}, for some distinct x,y∈Xex,y\in Xe. Since ee is an idempotent x∈Kix\in K_i, y∈Kjy\in K_j and since the kernel classes form a convex partition of XX, then x≤yx\leq y, as required. The last assertion is immediate since OnO_n is a regular subsemigroup of OPnOP_n.

Lemma 4.4. φk\varphi_k restricted to E(RfOn)E(R_f^{O_n}) is a bijection onto E(Ra−kfakOPn)E(R_{a^{-k}fa^k}^{OP_n}).

Proof. Certainly φk\varphi_k maps the first set injectively into the second. As for surjectivity, take e∈E(Ra−kfakOPn)e\in E(R_{a^{-k}fa^k}^{OP_n}). Then ea−kφk=ee^{a^{-k}}\varphi_k=e, and ea−k∈E(OPn)e^{a^{-k}}\in E(OP_n). Now ea−kRa−kfakOPneRakOPn(a−kfak)=fakRnOPnfe^{a^{-k}}R^{OP_n}_{a^{-k}fa^k}eR^{OP_n}_{a^k}(a^{-k}fa^k)=fa^kR^{OP_n}_nf. But then ea−k∈One^{a^{-k}}\in O_n and ea−kROnfe^{a^{-k}}R^{O_n}f by Lemma 4.3, proving surjectivity.

From this result we can now conclude with:

Theorem 4.5. Let α=akf∈OPn\alpha=a^kf\in OP_n for some f∈Onf\in O_n and some 0≤k≤n−10\leq k\leq n-1. Then ∣E(RfOn)∣=∣E(RαOPn)∣|E(R_f^{O_n})|=|E(R_\alpha^{OP_n})|.

Proof. The result follows from Lemma 4.4, since αROPnαa−k=akfa−k\alpha R^{OP_n}\alpha a^{-k}=a^kfa^{-k}.

Next we see that, in general, ∣E(LfOn)∣≤∣E(LamfOPn)∣|E(L_f^{O_n})| \leq|E(L_{a_m^f}^{OP_n})|, since we have LfOn⊆LamfOPn=LamfOPnL_f^{O_n} \subseteq L_{a_m^f}^{OP_n} = L_{a_m^f}^{OP_n}. However we show that the containment is strict for n≥3n \geq3. It is sufficient to observe this for n=3n=3. Take α∈OP3\alpha\in OP_3 defined by α=a0f\alpha=a^0f, (f∈O3f \in O_3) where f=(123122)f=\begin{pmatrix}1&2&3\\1&2&2\end{pmatrix}. Consider the mapping β=(123121)∉O3\beta=\begin{pmatrix}1&2&3\\1&2&1\end{pmatrix}\notin O_3. Clearly β∈E(LαOP3)\beta\in E(L_\alpha^{OP_3}) yet β∉E(LfO3)\beta\notin E(L_f^{O_3}).

Let VS(α)V^S(\alpha) be denote the set V(α)V(\alpha) in the semigroup SS. In general we have that ∣VS(α)∣=∣E(LαS)∣∣E(RαS)∣|V^S(\alpha)|=|E(L_\alpha^S)||E(R_\alpha^S)|. In our case, from the results above, we have

∣VOn(f)∣=∣E(LfOn)∣∣E(RfOn)∣<∣E(LamfOPn)∣∣E(RamfOPn)∣=∣VOPn(amf)∣|V^{O_n}(f)|=|E(L_f^{O_n})||E(R_f^{O_n})|<|E(L_{a_m^f}^{OP_n})||E(R_{a_m^f}^{OP_n})|=|V^{OP_n}(a^m f)|

and so we can conclude that not all inverses of amfa^m f are of the form f′an−mf'a^{n-m} where f′∈VOn(f)f' \in V^{O_n}(f).

It has long been known that the subsemigroup of all singular mappings of TnT_n is a semiband [6], and it has been proved that OnO_n is also idempotent-generated [7]. Our next task is to find the core of OPnOP_n. First we prove,

Lemma 4.6. Every α∈On\alpha\in O_n has a fixed point.

Proof. Let α∈On\alpha\in O_n and A={x∈X:x≤xα}A=\{x\in X:x\leq x\alpha\}. Note that 1∈A1\in A and so AA is nonempty. Let a=max⁡Aa=\max A. Hence a≤aαa\leq a\alpha as a∈Aa\in A, and aα≤(aα)αa\alpha\leq(a\alpha)\alpha as α∈On\alpha\in O_n. Thus aα∈Aa\alpha\in A and so aα≤aa\alpha\leq a by the maximality of aa. Therefore a=aαa=a\alpha as required. □\square

Let U=⋃k=0n−1OnkU=\bigcup_{k=0}^{n-1}O_n^k and consider a−kfaka^{-k}fa^k where f∈Onf\in O_n and 0≤k≤n−10\leq k\leq n-1. Now x∈Xx\in X is a fixed point of a−kfaka^{-k}fa^k if and only if (x−k)f=x−k(x-k)f=x-k which is equivalent to saying that x−kx-k is a fixed point of ff. Thus we have the next result:

Lemma 4.7. Let α=a−kfak\alpha=a^{-k}fa^k where f∈Onf\in O_n and 0≤k≤n−10\leq k\leq n-1. Then x∈F(α)x\in F(\alpha) if and only if x−k∈F(f)x-k\in F(f). In particular, if α∈U\alpha\in U then F(α)≠∅F(\alpha)\ne\varnothing. □\square

As has often been observed each α∈Tn\alpha\in T_n can be pictured as a digraph on nn vertices with ijij an arc of α\alpha if iα=ji\alpha=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 CC of the digraph of α∈Tn\alpha\in T_n has a cycle K(C)K(C) defined by the property that x∈Cx\in C is in K(C)K(C) if and only if there exists p>0p>0 such that xαp=xx\alpha^p=x.

Lemma 4.8. Let α∈OPn\alpha\in OP_n. Then the digraph of α\alpha cannot have a non-trivial cycle and a fixed point.

Proof. Suppose that α\alpha has a fixed point xx. Suppose α\alpha has a cycle CC with ∣C∣=p≥2|C|=p\geq2. Let ≤\leq denote ≤x−1\leq_{x-1}: note that xx is the minimum of (X,≤x−1)(X,\leq_{x-1}). We claim that there exists i∈Ci\in C such that i<iαi<i\alpha. Suppose not: then for each i∈Ci\in C we have:

i>iα>iα2>⋯>iαp−1>iαp=i,i>i\alpha>i\alpha^2>\cdots>i\alpha^{p-1}>i\alpha^p=i,

which is a contradiction and so there is such an ii. Since α∈OPn\alpha\in OP_n and x∈F(α)x\in F(\alpha), we obtain (x,i,iα),(x,iα,iα2),…,(x,iαj,iαj+1)(x,i,i\alpha),(x,i\alpha,i\alpha^2),\ldots,(x,i\alpha^j,i\alpha^{j+1}) are cyclic. If for j≥0j\geq0 we had iαj>iαj+1i\alpha^j>i\alpha^{j+1} we have iαj+1<xi\alpha^{j+1}<x, which is a contradiction. Therefore iαj<iαj+1i\alpha^j<i\alpha^{j+1}, for all jj; whence i<iα<⋯<iαp−1<iαp=ii<i\alpha<\cdots<i\alpha^{p-1}<i\alpha^p=i, which is a contradiction. Hence the digraph of α\alpha cannot have a proper cycle and a fixed point. □\square

Theorem 4.9. Let α∈OPn\alpha\in OP_n. Then the digraph of α\alpha cannot have two cycles of different length.

Proof. Suppose α\alpha has a tt-cycle CtC_t and an rr-cycle CrC_r with t<rt<r. Consider αt∈OPn\alpha^t\in OP_n. Each point of CtC_t is fixed by αt\alpha^t and so F(αt)≠∅F(\alpha^t)\ne\varnothing. However, for x∈Crx\in C_r, xαt≠xx\alpha^t\ne x, but xx is a point in a cycle of αt\alpha^t since xαtr=x(αr)t=xx\alpha^{tr}=x(\alpha^r)^t=x, which contradicts Lemma 4.8. □\square

Lemma 4.10. Let α∈OPn\alpha\in OP_n. If F(α)≠∅F(\alpha) \ne\varnothing then the digraph of α\alpha is a forest and each component CC associated with a fixed point of α\alpha is an interval.

Proof. If F(α)≠∅F(\alpha) \ne\varnothing, then by Lemma 4.8 the digraph of α\alpha cannot have a non-trivial cycle. Thus each component has a trivial cycle and so the digraph of α\alpha is a forest. Now let CC be a component with C=C(x)C=C(x), xx the fixed point in CC. Take kk sufficiently large so that C(x)={y∈X:yαk=x}C(x)=\{y \in X : y\alpha^k=x\}. Then C(x)=x(αk)−1C(x)=x(\alpha^k)^{-1}; αk∈OPn\alpha^k \in OP_n and so x(αk)−1x(\alpha^k)^{-1} is an interval by the Convexity Lemma. □\square

Lemma 4.11. Let α∈OPn\alpha\in OP_n such that F(α)≠∅F(\alpha) \ne\varnothing. Let CC be any component of α\alpha. Then Cα⊆CC\alpha\subseteq C, there exist i,j∈Xi,j \in X such that C=[i,j]C=[i,j], and α\alpha restricted to CC is an order-preserving with respect to ≤i−1\le_{i-1}.

Proof. It follows immediately from the definition of component that Cα⊆CC\alpha\subseteq C, and from Lemma 4.10 that α\alpha restricted to CC has a fixed point xx. Suppose first that C=XC=X. Then C=[x,x−1]C=[x,x-1]. Suppose that a≤x−1ba \le_{x-1} b. If bα=xb\alpha=x then x=xα=aα=bαx=x\alpha=a\alpha=b\alpha, by the Convexity Lemma. If x<x−1bαx <_{x-1} b\alpha then (x,aα,bα)(x,a\alpha,b\alpha) is cyclic, by Lemma 2.1, so x≤x−1aα≤x−1bαx \le_{x-1} a\alpha\le_{x-1} b\alpha. This proves that α\alpha is order-preserving with respect to ≤x−1\le_{x-1}.

Suppose now that C≠XC \ne X and choose any z∈X∖Cz \in X \setminus C. Observe, by definition of component, that zα∉Cz\alpha\notin C. By Lemma 4.10, C=[i,j]C=[i,j] for some i,j∈Xi,j \in X. In particular note that j<i−1zj <_{i-1} z and j<i−1zαj <_{i-1} z\alpha. Let y∈Cy \in C. If y≤i−1xy \le_{i-1} x then (y,x,z)(y,x,z) is cyclic, so (yα,x,zα)(y\alpha,x,z\alpha) is cyclic, by Lemma 2.1, so yα≤i−1xy\alpha\le_{i-1} x. Similarly if x≤i−1yx \le_{i-1} y then x≤i−1yαx \le_{i-1} y\alpha. Now suppose that a,b∈Ca,b \in C and a<i−1ba <_{i-1} b. If a≤i−1x≤i−1ba \le_{i-1} x \le_{i-1} b then, from above, aα≤i−1x≤i−1bαa\alpha\le_{i-1} x \le_{i-1} b\alpha. If a,b≤i−1xa,b \le_{i-1} x then (a,b,x)(a,b,x) is cyclic so that (aα,bα,x)(a\alpha,b\alpha,x) is cyclic and, from above, aα,bα≤i−1xa\alpha,b\alpha\le_{i-1} x. If aα=xa\alpha=x then aα=xαa\alpha=x\alpha and so aα=bα=xa\alpha=b\alpha=x by the Convexity Lemma. Otherwise aα<i−1xa\alpha<_{i-1} x, bα≤i−1xb\alpha\le_{i-1} x, and so by cyclicity, aα≤i−1bαa\alpha\le_{i-1} b\alpha. Similarly, if x≤i−1a,bx \le_{i-1} a,b then aα≤i−1bαa\alpha\le_{i-1} b\alpha, completing the proof that α∣C\alpha|_C is order-preserving with respect to ≤i−1\le_{i-1}. □\square

Corollary 4.12. Let α∈OPn\alpha\in OP_n such that F(α)≠∅F(\alpha) \ne\varnothing. Then α∈U\alpha\in U.

Proof. Let CC be any component of α\alpha, so C=[i,j]C=[i,j] for some i,ji,j and α∣C:C⟶C\alpha|_C:C \longrightarrow C is order-preserving with respect to ≤i−1\le_{i-1}, by Lemma 4.11. Let DD be any other component (if it exists). Then, by Lemma 4.11 again, D=[k,l]D=[k,l] for some k,lk,l and α∣D:D⟶D\alpha|_D:D \longrightarrow D is order-preserving with respect to ≤k−1\le_{k-1}. But

≤i−1∩(D×D)=≤k−1∩(D×D),\le_{i-1} \cap(D \times D)=\le_{k-1} \cap(D \times D),

since i∉Di \notin D and DD is an interval, so that α∣D\alpha|_D is order-preserving with respect to ≤i−1\le_{i-1}. Thus α\alpha is order-preserving with respect to ≤i−1\le_{i-1}, so lies in UU. □\square

The previous lemmas and the description of the fixed points of a−kfaka^{-k}fa^k in terms of those of ff now yield the next result:

Theorem 4.13. U={α∈OPn:F(α)≠∅}U=\{\alpha\in OP_n:F(\alpha) \ne\varnothing\}.

Proof. If α∈U\alpha\in U then F(α)≠∅F(\alpha) \ne\varnothing by Lemma 4.7. The converse follows from Corollary 4.12. □\square

UU does not contain a=(12⋯n)a=(12\cdots n) nor its non-idempotent powers. Moreover there are elements in OPn∖ZnOP_n \setminus\mathbb{Z}_n which are not in UU either. For example, let α=(12342442)∈OP4\alpha=\begin{pmatrix}1&2&3&4\\2&4&4&2\end{pmatrix}\in OP_4. We have α∉Z4\alpha\notin\mathbb{Z}_4 as α\alpha is not a power of a=(1234)a=(1234), the fixed generator of Z4\mathbb{Z}_4; however F(α)=∅F(\alpha)=\varnothing.

Corollary 4.14. E(OPn)⊆UE(OP_n)\subseteq U.

Proof. If α∈E(OPn)\alpha\in E(OP_n) then F(α)≠∅F(\alpha) \ne\varnothing, and so by Theorem 4.13, α∈U\alpha\in U. □\square

From this result, if α∈⟨E⟩\alpha\in\langle E\rangle then α∈⟨U⟩\alpha\in\langle U\rangle. However OnO_n is a semiband [7] which implies that OnkO_n^k is a semiband for all k=0,1,…,n−1k=0,1,\ldots,n-1 by Lemma 4.1. Let α∈U\alpha\in U, so that there exists kk (0≤k≤n−10 \le k \le n-1) such that α∈Onk\alpha\in O_n^k. Since OnkO_n^k is a semiband, then α\alpha is a product of elements in E(Onk)E(O_n^k) and hence α\alpha is a product of elements in E(OPn)E(OP_n). Therefore α∈⟨E⟩\alpha\in\langle E\rangle. Thus ⟨U⟩⊆⟨E⟩\langle U\rangle\subseteq\langle E\rangle as U⊆⟨E⟩U \subseteq\langle E\rangle. Hence the next result follows:

Corollary 4.15. Let E=E(OPn)E=E(OP_n) and U=⋃k=0n−1OnkU=\bigcup_{k=0}^{n-1}O_n^k. Then ⟨E⟩=⟨U⟩\langle E\rangle=\langle U\rangle.

Next we describe ⟨U⟩\langle U\rangle, the idempotent-generated subsemigroup of OPnOP_n.

Lemma 4.16. Let α∈OPn\alpha\in OP_n. Then αap∈U\alpha a^p \in U for some pp (0≤p≤n−10 \le p \le n-1).

Proof. Let α∈OPn\alpha\in OP_n. Using Theorem 2.6, α=amg\alpha=a^m g for some 0≤m≤n−10 \le m \le n-1 and g∈Ong \in O_n. Then

αan−m=amgan−m=a−(n−m)gan−m∈Onn−m⊆U.\alpha a^{n-m}=a^mga^{n-m}=a^{-(n-m)}ga^{n-m}\in O_n^{n-m}\subseteq U.

Lemma 4.17. Let R⊆XR \subseteq X. Then the mapping ff whereby:

xf={xaif x∈Rxif x∉Rxf= \begin{cases} xa & \text{if }x\in R\\ x & \text{if }x\notin R \end{cases}

is in OPnOP_n. Moreover if RR is a proper subset, f∈Uf\in U.

Proof. Note that for any ii such that 1≤i≤n−11\le i\le n-1, we have (i−1)f≤i≤if(i-1)f\le i\le if; therefore 1f≤2f≤⋯≤(n−1)f1f\le2f\le\cdots\le(n-1)f. Now nf=nnf=n or nf=1nf=1; in the first case 1f≤2f≤⋯≤(n−1)f≤nf1f\le2f\le\cdots\le(n-1)f\le nf and f∈Onf\in O_n; in the second case nf≤1f≤2f≤⋯≤(n−1)fnf\le1f\le2f\le\cdots\le(n-1)f and f∈OPnf\in OP_n. In either case f∈OPnf\in OP_n. Now if RR is a proper subset then F(f)≠∅F(f)\ne\varnothing as F(f)=X∖RF(f)=X\setminus R and so by Theorem 4.13, f∈Uf\in U.

Lemma 4.18. Suppose that u∈⟨U⟩u\in\langle U\rangle, u≠1u\ne1. Then ua∈⟨U⟩ua\in\langle U\rangle.

Proof. Note that the identity mapping is the only member of UU of full rank as U=⋃m=0n−1a−mOnamU=\bigcup_{m=0}^{n-1}a^{-m}O_na^m and the identity mapping is the only member of OnO_n of full rank. Hence Xu≠XXu\ne X. Take R=XuR=Xu in Lemma 4.17. We claim that ua=ufua=uf, from which the result follows from Lemma 4.17. Clearly f∣Xu=a∣Xuf|_{Xu}=a|_{Xu}. Let xx be any element of XX. Then we have that x(ua)=(xu)a=(xu)f=x(uf)x(ua)=(xu)a=(xu)f=x(uf) and so ua=ufua=uf.

Finally we have a description of the core of OPnOP_n.

Theorem 4.19. ⟨U⟩=⟨E(OPn)⟩=(OPn∖Zn)∪{1X}\langle U\rangle=\langle E(OP_n)\rangle=(OP_n\setminus Z_n)\cup\{1_X\}.

Proof. Let α∈(OPn∖Zn)∪{1X}\alpha\in(OP_n\setminus Z_n)\cup\{1_X\}. Clearly 1X∈⟨U⟩1_X\in\langle U\rangle. Suppose α≠1X\alpha\ne1_X. By Lemma 4.16, there exists pp such that αap∈⟨U⟩\alpha a^p\in\langle U\rangle, and clearly αap≠1X\alpha a^p\ne1_X. Take mm such that p+m≡0(modn)p+m\equiv0\pmod n. Using Lemma 4.18 we therefore obtain α=αap+m=αapam∈⟨U⟩\alpha=\alpha a^{p+m}=\alpha a^pa^m\in\langle U\rangle.

Conversely, UU, and so ⟨U⟩\langle U\rangle, contains no members of OPnOP_n of rank nn (except 1X1_X), and so contains no other mappings of full rank; in particular

Zn∩⟨U⟩={1X},Z_n\cap\langle U\rangle=\{1_X\},

as required.

Consequently the core of OPnOP_n is ⟨U⟩\langle U\rangle and we can conclude that OPnOP_n is not a semiband, although, like TnT_n, the submonoid of singular mappings of OPnOP_n is idempotent-generated. There are mappings in the core of OPnOP_n 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 α=(123456345233)∈OP6\alpha=\begin{pmatrix}1&2&3&4&5&6\\3&4&5&2&3&3\end{pmatrix}\in OP_6. We have α∉U\alpha\notin U as F(α)=∅F(\alpha)=\varnothing but α∈⟨U⟩\alpha\in\langle U\rangle.

Orientation-reversing mappings

Let α∈Tn\alpha\in T_n. We say that α\alpha is an orientation-reversing mapping on XX if the sequence (1α,2α,…,nα)(1\alpha,2\alpha,\ldots,n\alpha) is anti-cyclic. The collection of all orientation-reversing mappings on XX will be denoted by ORnOR_n.

Let γ\gamma be the reflection whereby i↦n+1−ii \mapsto n+1-i (i∈Xi \in X). Note that γ\gamma is an involution on XX. Also, γ∈ORn\gamma\in OR_n as (1γ,2γ,…,nγ)=(n,n−1,…,1)(1\gamma,2\gamma,\ldots,n\gamma)=(n,n-1,\ldots,1) is anti-cyclic.

Let Γr\Gamma_r [resp. Γl\Gamma_l]: Tn⟶TnT_n \longrightarrow T_n be defined by α↦αγ\alpha\mapsto\alpha\gamma [resp. α↦γα\alpha\mapsto\gamma\alpha] (α∈Tn\alpha\in T_n). The following result is easily proved.

Lemma 5.1. Γr,Γl\Gamma_r,\Gamma_l are involutions on TnT_n which map OPnOP_n onto ORnOR_n and ORnOR_n onto OPnOP_n.

Corollary 5.2. OPn⋅ORn=ORn⋅OPn=ORnOP_n \cdot OR_n=OR_n \cdot OP_n=OR_n and

(ORn)2=(OPn)2=OPn.(OR_n)^2=(OP_n)^2=OP_n.

Let PnP_n be denote the collection of all mappings in OPn∪ORnOP_n \cup OR_n. By Corollary 5.2, we have that:

Theorem 5.3. Pn=OPn∪ORnP_n=OP_n \cup OR_n is a submonoid of TnT_n.

From Lemma 1.1 we obtain the following

Lemma 5.4. OPn∩ORn={α∈OPn:∣Xα∣≤2}OP_n \cap OR_n=\{\alpha\in OP_n:|X\alpha| \le2\}.

From this we can conclude that

Theorem 5.5. ∣Pn∣=2∣OPn∣−n−2C2(n,2)|P_n|=2|OP_n|-n-2C^2(n,2).

Proof. Note that ∣Pn∣=∣OPn∣+∣ORn∣−∣OPn∩ORn∣|P_n|=|OP_n|+|OR_n|-|OP_n \cap OR_n|. From Lemma 5.4 and the discussion following Proposition 3.4, ∣OPn∩ORn∣=n+2C2(n,2)|OP_n \cap OR_n|=n+2C^2(n,2) and since ∣OPn∣=∣ORn∣|OP_n|=|OR_n| the result follows.

Remark. A simple calculation now yields

∣Pn∣=(2n)!n!(n−1)!−n2(n3−2n2+5n−2)|P_n|=\frac{(2n)!}{n!(n-1)!}-\frac{n}{2}(n^3-2n^2+5n-2)

and this gives Pn=TnP_n=T_n for n≤3n \le3. This may be a reason why many interesting counterexamples of semigroups of transformations require 4 base points.

Let β∈ORn\beta\in OR_n and write β\beta as αγ\alpha\gamma where α∈OPn\alpha\in OP_n. It is routine to check that γα′∈V(αγ)\gamma\alpha' \in V(\alpha\gamma) in PnP_n, where α′∈V(α)\alpha' \in V(\alpha) in OPnOP_n. (Conversely, given β′∈V(β)\beta' \in V(\beta) in PnP_n then it is straightforward to check that β′=α′γ\beta'=\alpha'\gamma for some α′∈V(α)\alpha' \in V(\alpha) in OPnOP_n.) Hence the next result follows:

Theorem 5.6. PnP_n is a regular monoid.

Consequently, from this result the usual description of Green’s relations L\mathcal{L}, R\mathcal{R} and H\mathcal{H} applies again. (See Remark that follows Theorem 3.1.)

Lemma 5.7. Let α,β∈Pn\alpha,\beta\in P_n. Then αDPnβ\alpha D^{P_n}\beta if and only if ∣Xα∣=∣Xβ∣|X\alpha|=|X\beta|.

Proof. If αDPnβ\alpha D^{P_n}\beta, then αDTnβ\alpha D^{T_n}\beta whence ∣Xα∣=∣Xβ∣|X\alpha|=|X\beta|.

Conversely, suppose that ∣Xα∣=∣Xβ∣|X\alpha|=|X\beta|. If α,β∈OPn\alpha,\beta\in OP_n then αDOPnβ\alpha D^{OP_n}\beta by Proposition 3.4. If α,β∈ORn\alpha,\beta\in OR_n then ∣Xαγ∣=∣Xβγ∣|X\alpha\gamma|=|X\beta\gamma|, so that, by Proposition 3.4,

αRPnαγDOPnβγRPnβ,\alpha R^{P_n}\alpha\gamma D^{OP_n}\beta\gamma R^{P_n}\beta,

so certainly αDPnβ\alpha D^{P_n}\beta. Similarly, if only one of α,β\alpha,\beta lies in OPnOP_n, say without loss of generality α∈OPn\alpha\in OP_n, β∈ORn\beta\in OR_n, then αDOPnβγRPnβ\alpha D^{OP_n}\beta\gamma R^{P_n}\beta. In each case αDPnβ\alpha D^{P_n}\beta.

Lemma 5.8. Let α∈Pn\alpha\in P_n be such that ∣Xα∣=t|X\alpha| = t for some 3≤t≤n3 \le t \le n. Let HαH_\alpha be the H\mathcal{H}-class containing α\alpha. Then ∣Hα∣=2t|H_\alpha| = 2t.

Proof. Let α∈Pn\alpha\in P_n be such that ∣Xα∣=t|X\alpha| = t for some 1≤t≤n1 \le t \le n. Let DtPnD_t^{P_n} denote the D\mathcal{D}-class containing α\alpha. By the previous lemma, DtPn={β∈Pn:∣Xβ∣=t}D_t^{P_n} = \{\beta\in P_n : |X\beta| = t\}. By Lemma 5.4, for t≤2t \le2 we have DtPn∩OPn=DtPn∩ORnD_t^{P_n} \cap OP_n = D_t^{P_n} \cap OR_n. For t≥3t \ge3, DtPn=(DtPn∩OPn)∪(DtPn∩ORn)D_t^{P_n} = (D_t^{P_n} \cap OP_n) \cup(D_t^{P_n} \cap OR_n). (The union is disjoint.) Since Γr\Gamma_r restricted to DtPn∩OPnD_t^{P_n} \cap OP_n is a bijection onto DtPn∩ORnD_t^{P_n} \cap OR_n then ∣DtPn∩OPn∣=∣DtPn∩ORn∣|D_t^{P_n} \cap OP_n| = |D_t^{P_n} \cap OR_n|. Since DtPn∩OPn=DtOPnD_t^{P_n} \cap OP_n = D_t^{OP_n} then ∣DtPn∣=2∣DtOPn∣|D_t^{P_n}| = 2|D_t^{OP_n}|. In PnP_n, DtPnD_t^{P_n} has the same number of R\mathcal{R}-, L\mathcal{L}-classes as DtOPnD_t^{OP_n} and so the number of H\mathcal{H}-classes in DtPnD_t^{P_n} is equal the number of H\mathcal{H}-classes in DtOPnD_t^{OP_n}. Since all H\mathcal{H}-classes within the one D\mathcal{D}-class have the same cardinality, then the order of every H\mathcal{H}-class in DtPnD_t^{P_n} is twice the order of every H\mathcal{H}-class in DtOPnD_t^{OP_n}, whence the result follows from Corollary 3.6. □

Theorem 5.9. For t≥3t \ge3 the maximal subgroups of DtPnD_t^{P_n} are dihedral groups of order 2t2t.

Proof. Recall that the dihedral group DnD_n of degree nn is a subgroup of SnS_n (n≥3n \ge3) of order 2n2n and generators xx and yy (x,y∈Dnx,y \in D_n) satisfying the following conditions: xn=1Xx^n = 1_X, y2=1Xy^2 = 1_X, xk≠1Xx^k \ne1_X if 0<k<n0 < k < n and yx=x−1yyx = x^{-1}y; conversely any group satisfying these conditions is isomorphic to DnD_n. (See, for example, [10].)

Let α∈E(Pn)\alpha\in E(P_n) be such that ∣Xα∣=t|X\alpha| = t for some tt. Take K1,K2,…,KtK_1,K_2,\ldots,K_t as the kernel classes of α\alpha and r1,r2,…,rtr_1,r_2,\ldots,r_t as the range of α\alpha as before such that Kjα=rjK_j\alpha= r_j, j=1,2,…,tj = 1,2,\ldots,t. Next we describe the maximal subgroups of DtPnD_t^{P_n} and we show that they are dihedral groups of order 2t2t with generators δ\delta and β\beta (δ,β∈Pn\delta,\beta\in P_n) satisfying βt=α\beta^t = \alpha, δ2=α\delta^2 = \alpha, βk≠α\beta^k \ne\alpha if 0<k<t0 < k < t and δβ=β−1δ\delta\beta= \beta^{-1}\delta, where β−1\beta^{-1} is the group inverse of β\beta in HαH_\alpha. For this consider the mapping δ\delta defined as follows:

Kjδ=rt−j+1,j=1,2,…,t.K_j\delta= r_{t-j+1}, \qquad j = 1,2,\ldots,t.

Clearly Xδ=XαX\delta= X\alpha and ker⁡δ=ker⁡α\ker\delta= \ker\alpha. Moreover δ∈ORn\delta\in OR_n as the sequence (rt,rt−1,…,r1)(r_t,r_{t-1},\ldots,r_1) is anti-cyclic. Also, consider the mapping β\beta whereby

Kjβ=rj+1,j=1,2,…,t.K_j\beta= r_{j+1}, \qquad j = 1,2,\ldots,t.

Note that β\beta is the mapping used in the proof of Lemma 3.5 and β∈OPn\beta\in OP_n, βt=α\beta^t = \alpha, βk≠α\beta^k \ne\alpha if 0<k<t0 < k < t. Also for all j=1,2,…,tj = 1,2,\ldots,t we have

Kjδ2=rt−j+1δ=rt−(t−j+1)+1=rj,K_j\delta^2 = r_{t-j+1}\delta= r_{t-(t-j+1)+1} = r_j,

and so δ2=α\delta^2 = \alpha. Now the group inverse of β\beta in HαH_\alpha is β−1\beta^{-1} defined by Kjβ−1=rj−1K_j\beta^{-1} = r_{j-1}, j=1,2,…,tj = 1,2,\ldots,t. Finally, (Kjβ−1)δ=rj−1δ=rt−(j−1)+1(K_j\beta^{-1})\delta= r_{j-1}\delta= r_{t-(j-1)+1}. On the other hand we obtain

(Kjδ)β=rt−j+1β=r(t−j+1)+1(K_j\delta)\beta= r_{t-j+1}\beta= r_{(t-j+1)+1}

and so δβ=β−1δ\delta\beta= \beta^{-1}\delta. □

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]

References

  1. [1]A. H. Clifford and G. B. Preston, The Algebraic Theory of Semigroups, Math. Surveys of Amer. Math. Society 1 (1961).
  2. [2]P. M. Higgins, Techniques of Semigroup Theory, Oxford Univ. Press (1992).DOI
  3. [3]P. M. Higgins, Combinatorial results for semigroups of order-preserving mappings, Math. Proc. Camb. Phil. Society 113 (1993), 281–296.
  4. [4]P. M. Higgins, Idempotent depth in semigroups of order-preserving mappings, Proc. Royal Soc. Edinburgh 124A (1994), 1045–1058.DOI
  5. [5]P. M. Higgins, Divisors of semigroups of order-preserving mappings on a finite chain, Internat. J. Algebra and Computation 5(6) (1995), 725–742.DOI
  6. [6]J. M. Howie, The subsemigroup generated by idempotents of a full transformation semigroup, J. London Math. Society 41 (1966), 707–716.DOI
  7. [7]J. M. Howie, Products of idempotents in certain semigroups of transformations, Proc. Edinburgh Math. Society (2) 17 (1971), 223–236.DOI
  8. [8]J. M. Howie and B. M. Schein, Products of idempotent order-preserving transformations, J. London Math. Society (2) 7 (1973), 357–366.DOI
  9. [9]J. M. Howie, Fundamentals of Semigroup Theory, Clarendon Press, Oxford (1995).DOI
  10. [10]T. W. Hungerford, Algebra, Graduate Texts in Mathematics 73 (1984).
  11. [11]A. Umar, On the semigroup of order-decreasing finite full transformations, Proc. Royal Soc. Edinburgh Sect. A 120 (1992), 129–142.DOI

Paper details

vlnc:W_22u3jqjd
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
CC BY 4.0
Usage

views · 0

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Mathematics

Not recorded for this paper

View statement
Looking for related papers…
Contents