# Idempotent Elements of the Endomorphism Semiring of a Finite Chain

Authors: Ivan Trendafilov; Dimitrinka Vladeva
Journal: ISRN Algebra
 (2013)

---

## Abstract

Idempotents yield much insight in the structure of finite semigroups and semirings. In this article, we obtain some results on (multiplicatively) idempotents of the endomorphism
semiring of a finite chain. We prove that the set of all idempotents with certain fixed points is a semiring and find its order. We further show that this semiring is an ideal in a well-known semiring. The construction of an equivalence relation such that any equivalence class contains just one idempotent is proposed. In our main result we prove that such an equivalence class is a semiring and find its order. We prove that the set of all idempotents with certain jump points is a semiring.


---

## Body

## 1. Introduction

The idempotents play an essential role in the theory of finite semigroups and semirings. It is well known that in a finite semigroup some power of each element is an idempotent, so the idempotents can be taken to be like a generating system of the semigroup or the semiring. For deep results, using idempotents in the representation theory of finite semigroups, we refer the reader to [1, 2].Let us briefly survey the contents of our paper. After the preliminaries, in Section3 we show some facts about the fixed points of idempotent endomorphisms. The central result here is Theorem 9 where we prove that the set of all idempotents with s fixed points k1,…,ks, 1≤s≤n-1, is a semiring of order ∏m=1s-1‍(km+1-km). Moreover, this semiring is an ideal of the semiring of all endomorphisms having at least k1,…,ks as fixed points. In the next section we consider an equivalence relation on some finite semigroup S such that for any x,y∈S follows x~y if and only if xk=ym=e, where k,m∈N and e is an idempotent of S. Then we consider the equivalence classes of semigroup S=(ℰ^𝒞n,·) which is, see [3], one subsemigroup of 𝒫𝒯n. Here we investigate the so-called jump points of the endomorphism and prove that between any two fixed points ki and ki+1 of an endomorphism, where ki+1≠ki, there is a unique jump point.The main result of the paper is Theorem19 where we prove that such an equivalence class is a semiring of order
(1)Ck1,1(∏i=1ℓ-1‍CtiCsi)Cn-1-kℓ,mℓ,
where Cp is the pth Catalan number.In the last section of the paper we consider idempotent endomorphisms with arbitrary fixed points but with certain jump points. Here we prove that the set of idempotent endomorphisms with identical jump points is a semiring.


## 2. Preliminaries

We consider some basic definitions and facts concerning finite semigroups and that can be found in any of [1, 2, 4, 5]. As the terminology for semirings is not completely standardized, we say what our conventions are.An algebraR=(R,+,·) with two binary operations + and  ·  on R is called a semiring if(i)
(R,+) is a commutative semigroup,(ii)
(R,·) is a semigroup,(iii)
both distributive laws holdx·(y+z)=x·y+x·z and (x+y)·z=x·z+y·z for any x,y,z∈R.LetR=(R,+,·) be a semiring. If a neutral element 0 of semigroup (R,+) exists and it satisfies 0·x=x·0=0 for all x∈R, then it is called zero. If a neutral element 1 of semigroup (R,·) exists, it is called identity element.For a semilatticeℳ the set ℰℳ of the endomorphisms of ℳ is a semiring with respect to the addition and multiplication defined by(i)
h=f+g  when  h(x)=f(x)∨g(x)  for  all  x∈ℳ,(ii)
h=f·g  when  h(x)=f(g(x))  for  all  x∈ℳ.This semiring is called theendomorphism semiring of ℳ. In this paper all semilattices are finite chains. Following [6, 7], we fix a finite chain 𝒞n=({0,1,…,n-1},∨) and denote the endomorphism semiring of this chain with ℰ^𝒞n. We do not assume that α(0)=0 for arbitrary α∈ℰ^𝒞n. So, there is not a zero in endomorphism semiring ℰ^𝒞n. Subsemiring ℰ𝒞n=ℰ𝒞n0 of ℰ^𝒞n consisting of all endomorphisms α with property α(0)=0 has zero and is considered in [6–8].Ifα∈ℰ^𝒞n such that f(k)=ik for any k∈𝒞n we denote α as an ordered n-tuple ≀i0,i1,i2,…,in-1≀. Note that mappings will be composed accordingly, although we will usually give preference to writing mappings on the right, so that α·β means “first α, then β.” The identity i=≀0,1,…,n-1≀ and all constant endomorphisms κi=≀i,…,i≀ are obviously (multiplicatively) idempotents.An elementa∈𝒞n satisfying α(a)=a is called a fixed point of the endomorphism α. Any α∈ℰ^𝒞n has at most n fixed points, and only identity i has just n fixed points.For other properties of the endomorphism semiring we refer the reader to [3, 6–8].In the following sections we use some terms from [4] having in mind that in [3] we show that some subsemigroups of the partial transformation semigroup are indeed endomorphism semirings.


## 3. Idempotent Endomorphisms and Their Fixed Points

The set of all idempotents (or idempotent elements) of semiringℰ^𝒞n is not a semiring namely; endomorphisms α=≀0,0,2≀ and β=≀0,1,1≀ are the idempotents of semiring ℰ^𝒞3 but αβ=≀0,0,1≀ is not an idempotent. The following several facts are well known or are consequences of well-known facts.Proposition 1.
The endomorphismα∈ℰ^𝒞n is an idempotent if and only if for any k∈𝒞n, which is not a fixed point of α, image α(k) is a fixed point of α.Note that in [9] maps αk are considered such that αk(x)=k for all x∈ℳ, where ℳ is not necessarily a finite semilattice. These maps are called constant endomorphisms.For anyα∈ℰ^𝒞n with one fixed point the cardinality of set Im(α) is an arbitrary number from 2 to n-1. Indeed, for α=≀n-2,n-1,…,n-1≀ with unique fixed point n-1 we have |Im(α)|=2 and for β=≀1,2,…,n-2,n-1,n-1≀ with the same unique fixed point, |Im(β)|=n-1. So, the following consequence of Proposition 1 is important.Corollary 2.
An endomorphism with only one fixed point is an idempotent if and only if it is a constant.More generally follows Corollary3.Corollary 3.
An endomorphismα∈ℰ^𝒞n with s fixed points k1,…,ks, 1≤s≤n-1, is an idempotent if and only if Im(α)={k1,…,ks}.Letα∈ℰ^𝒞n have just n-1 fixed points. Then α≠i and n-1≤|Im(α)|<n. So, |Im(α)|=n-1 and from Corollary 3 follows.Corollary 4.
Every endomorphismα∈ℰ^𝒞n with n-1 fixed points is an idempotent.Letα∈ℰ^𝒞n have just n-2 fixed points. Let α(k)≠k and α(ℓ)≠ℓ, where k,ℓ∈𝒞n. If we assume that k and ℓ are not consecutive, then α(k)=k-1 or α(k)=k+1. Similarly, α(ℓ)=ℓ-1 or α(ℓ)=ℓ+1. Since k-1, k+1, ℓ-1, and ℓ+1 are fixed points, from Proposition 1 it follows that α is an idempotent. Let us assume that ℓ=k+1. If (1)
α(k)=k-1,α(k+1)=k-1,(2)
α(k)=k-1,α(k+1)=k+2,(3)
α(k)=k+2,α(k+1)=k+2,then it easily follows thatα is an idempotent. Let us assume that α(k)=k+1 and α(k+1)=k+2. Then from Proposition 1 it follows that α is not an idempotent endomorphism. But it is clear that α2(k)=k+2=α3(k) and α2(k+1)=k+2=α3(k+1).Thus we prove the following.Corollary 5.
Every endomorphismα∈ℰ^𝒞n with n-2 fixed points is either an idempotent or α3=α2.By similar reasonings, we may prove the following more general fact.Corollary 6.
Letα∈ℰ^𝒞n have s fixed points k1,…,ks, where [(n+1)/2]≤s≤n-1 and all other two points k and ℓ, k<ℓ, are not consecutive; that is k≠ki, ℓ≠ki, where i=1,…,s, and ℓ≠k+1. Then α is an idempotent.Letα∈ℰ^𝒞n have just two fixed points k and ℓ, where k<ℓ. From Corollary 3 it follows that
(2)α=≀k,…,k,ik+1,…,iℓ-1,ℓ,…,ℓ≀,
where images is, s=k+1,…,ℓ-1, are equal either to k or to ℓ.Thus the endomorphisms of such type are(3)α0=≀k,…,k↑k,…,k,ℓ↑ℓ,…,ℓ≀⋯αℓ-k-2=≀k,…,k↑k,k,ℓ…,ℓ↑ℓ,…ℓ≀αℓ-k-1=≀k,…,k↑k,ℓ…,ℓ↑ℓ,…,ℓ≀.
For these maps we have
(4)α0<⋯<αl-k-2<αl-k-1.
Hence αi+αj=αj+αi=αj, where j≥i. It is easy to see that αi·αj=αi for all i,j∈{0,…l-k-2}. So, we prove the following.Proposition 7.
The set of idempotent endomorphisms with two fixed pointsk and ℓ, k<ℓ, is a semiring of order  l-k.Example 8.
The idempotent endomorphisms of semiringℰ^𝒞7 with fixed points 1 and 5 are
(5)φ1=≀1111155≀,φ2=≀1111555≀,φ3=≀1115555≀,φ4=≀1155555≀.
The semiring consisting of these maps has the following addition and multiplication tables:
(6)+φ1φ2φ3φ4φ1φ1φ2φ3φ4φ2φ2φ2φ3φ4φ3φ3φ3φ3φ4φ4φ4φ4φ4φ4·φ1φ2φ3φ4φ1φ1φ1φ1φ1φ2φ2φ2φ2φ2φ3φ3φ3φ3φ3φ4φ4φ4φ4φ4Theorem 9.
The subset ofℰ^𝒞n,  n≥3, of all idempotent endomorphisms with s fixed points k1,…,ks, 1≤s≤n-1, is a semiring of order ∏m=1s-1‍(km+1-km).Proof.
Letk1 be the least fixed point of idempotent endomorphism α. If k<k1, then α(k)≤k1. We assume that α(k)=j<k1. Then α(j)=j is a contradiction to the minimal choice of k1. Hence α(k)=k1, that is in the first k1+1 positions of the ordered n-tuple which represent endomorphism α occurs only k1.
Letks be the biggest fixed point of idempotent endomorphism α. If k>ks, then α(k)≥ks. We assume that α(k)=j>ks.
Now followsα(j)=j which is a contradiction to the maximal choice of ks. Hence α(k)=ks, that is the last n-ks positions of the ordered n-tuple which represent endomorphism α occurs only ks.
We denote bypkm, where 1≤m≤s, the number of coordinates in the ordered n-tuple which represents endomorphism α equal to km. For pkm it follows
(7)k1+1≤pk1≤k21≤pk2≤k3-k2⋮1≤pkm≤km+1-km⋮n-ks≤pks≤n-ks-1-1.
So every idempotent endomorphism withs fixed points k1,…,ks has the following type:
(8)α=≀k1,…,k1︸pk1,k2,…,k2︸pk2,…,ks,…,ks︸pks≀.
Let another endomorphismβ have the same type:
(9)β=≀k1,…,k1︸pk1′,k2,…,k2︸pk2′,…,ks,…,ks︸pks′≀.
Since(α+β)(ki)=α(ki)+β(ki)=ki+ki=ki, where i=1,…,s, it follows that α+β has the type of α and β.
For theseα and β it follows that α·β=α. (So, the multiplication of idempotent endomorphisms with fixed points  k1,…,ks is like the multiplication of constant endomorphisms—every idempotent is a right identity).
Thus we prove that the set of all idempotent endomorphisms withs fixed points k1,…,ks, 1≤s≤n-1, is a semiring.
From the inequalities of numberspkm, where 1≤m≤s, it follows that all possibilities to have km  in  n-tuple are km+1-km.
The order of this semiring is equal to the product of all possibilities for the fixed pointskm, where 1≤m≤s. This number is equal to product ∏m=1s-1‍(km+1-km), and the proof is completed.The semiring of the idempotent endomorphisms ofℰ^𝒞n with s fixed points k1,…,ks is denoted by ℐ𝒟(k1,…,ks). Since the semiring of all the endomorphisms with fixed points k1,…,ks is ⋂r=1s‍ℰ𝒞n(kr), it follows that ℐ𝒟(k1,…,ks) is a subsemiring of ⋂r=1s‍ℰ𝒞n(kr).Remark 10.
(a) From Theorem9 semiring ℐ𝒟(0,…,k-1,k+1,…,n-1) has two elements: idempotent endomorphisms k+=≀0,…,k-1,k+1,k+1,…n-1≀ and k-=≀0,…,k-1,k-1,k+1,…n-1≀. This semiring has the following addition and multiplication tables:
(10)+k-k+k-k-k+k+k+k+·k-k+k-k-k-k+k+k+
(b) The product of endomorphisms from different semiringsℐ𝒟(k1,…,ks) is not, in general, an idempotent. Indeed, in semiring ℰ^𝒞8 for
(11)α=≀11555555≀∈ℐ𝒟(1,5),g=≀22255555≀∈ℐ𝒟(2,5)
it follows that α·β=≀22555555≀, but this endomorphism is not an idempotent.
(c) The sum of two idempotent endomorphisms such that the fixed points of the first one are part of the fixed points of another endomorphism is not surely an idempotent. For instance,≀0033≀+≀0223≀=≀0233≀.Corollary 11.
Letn≥3 and k1,…,ks∈𝒞n, where s=1,…,n-2. Semiring ℐ𝒟(k1,…,ks) is an ideal of ⋂r=1s‍ℰ𝒞n(kr).Proof.
Using Theorem9, it will be enough to show that ℐ𝒟(k1,…,ks) is closed under the left and right multiplications by elements of ⋂r=1s‍ℰ𝒞n(kr).
Let(12)α=≀k1,…,k1︸pk1,k2,…,k2︸pk2,…,ks,…,ks︸pks≀∈ℐ𝒟(k1,…,ks),β=≀i0,i1,…,ik1-1,k1,ik1+1,…,ik2-1,k2,…,ks≀∈⋂r=1s‍ℰ𝒞n(kr).
Hence α·β=α.
Now we calculate(13)β·α=≀i0,i1,…,ik1-1,k1,ik1+1,…,ik2-1,k2,…,ks≀·≀k1,…,k1,k2,…,k2,…,ks,…,ks≀.
Sinceis≤k1, where s=0,…,k1-1, then α(is)≤α(k1)=k1, and from the proof of Theorem 9 it follows that α(is)=k1.
Sincek1≤ik1+1≤⋯≤ik2-1≤k2, it follows  that
(14)k1=α(k1)≤α(ik1+1)≤⋯≤α(ik2-1)≤α(k2)=k2.
But endomorphismα maps all the elements between k1 and k2 either in k1, or in k2. Then α(ik1+1),…,α(ik2-1) are either k1, or k2. We use such arguments for the next elements of Im(β) which are between the other fixed points. Thus
(15)β·α=γ=≀k1,…,k1︸pk1′,k2,…,k2︸pk2′,…,ks,…,ks︸pks′≀∈ℐ𝒟(k1,…,ks).


## 4. Roots of Idempotent Endomorphisms

Let(S,·) be a finite semigroup. It is well known, see [10], that for any x∈S there is a positive integer k=k(x) such that ak is an idempotent element of S.Now we consider the following relation: for anyx,y∈S we define
(16)x~y⟺∃k,m∈N,xk=ym=e,
where e is an idempotent element of S.Obviously, the relation~ is reflexive and symmetric.Letx~y and y~z. Then xk=ym=e1 and yr=zs=e2 where e1 and e2 are idempotents. Now it follows that (ym)r=e1r=e1 and (yr)m=e2m=e2; thus e1=e2. Hence xk=zs=e1; that is, x~z. So, we prove that ~ is an equivalence relation on S.Note that two different idempotents belong to different equivalence classes modulo~. If e is an idempotent, the elements of the equivalence class containing e are called roots of idempotente.The following natural question arises:are there any finite noncommutative semigroups such that the equivalence classes (modulo the previous relation) are semigroups?Of course, we must avoid trivial examples of commutative semigroups, nilpotent semigroups, and others.To answer the previous question, we consider the semigroup(ℰ^𝒞n,·) and the already defined equivalence relation.Letα∈ℰ^𝒞n. Element j∈𝒞n is called a jump point of α if j≠0, and one of the following conditions holds:(1)
α(j-1)≤j-1 and α(j)>j,(2)
α(j-1)<j-1 and α(j)≥j.There are endomorphisms without jump points, namely, identityi and constant endomorphisms κk=≀kk⋯k≀, k=0,1,…,n-1. For k,ℓ∈𝒞n, k<ℓ endomorphism
(17)αj(i)={k,i≤j-1,ℓ,i≥j
has no jump points if j>ℓ. The endomorphisms k+ and k-, see Remark 10, have jump points: k and k+1 are jump points of k+ and k-, respectively.Theorem 12.
Letα∈ℰ^𝒞n, n≥3, be an endomorphism with s fixed points k1,…,ks, 1≤s≤n-2. Let for some i, i=1,…,s-1, fixed points ki and ki+1 be non consecutive; that is, ki+1≠ki+1. Then there is a unique jump point ji of α such that ki+1≤ji≤ki+1.Proof.
Forki+1 there are two possibilities:(1)
α(ki+1)>ki+1, then ji=ki+1 is the searched jump point of α, or(2)
α(ki+1)<ki+1.
Letα(ki+m)<ki+m for any m=1,2,…,ℓ-1. If α(ki+ℓ)≥ki+ℓ, then ji=ki+ℓ is the searched jump point of α.
We assume thatα(ki+m)<ki+m for all m=1,2,…,ki+1-ki-1. Now α(ki+1-1)<ki+1-1. But α(ki+1)=ki+1, so, ji=ki+1 is the searched jump point of α.
Suppose thatj and j∘ are two jump points of α such that ki+1≤j≤ki+1 and ki+1≤j∘≤ki+1. Let j<j∘. Now α(j)>j. Let m∈𝒞n, and j≤m<j∘ is the maximal element such that α(m)>m. Then α(m+1)<m+1, and it follows that α(m)≥m+1>α(m+1) which is a contradiction. By the same arguments we show that j∘<j is impossible. So j=j∘ is the unique jump point of α such that ki+1≤j≤ki+1.Letk1 be the least fixed point of endomorphism α and i∈𝒞n, i<k1. If we suppose that α(i)<i, using α(0)>0, it follows that for some maximal element m, where 0≤m<i, we have α(m)>m and then α(m+1)<m+1, which is impossible. So, for every i<k1 it follows that α(i)>i. Similarly for every i>ks, where ks is the biggest fixed point of α, it follows that α(i)<i. So, we prove the following.Corollary 13.
Every endomorphismα∈ℰ^𝒞n, n≥3, with just ℓ fixed points k1,…,kℓ, which are not consecutive, that is, ki+1≠ki+1 for i=1,…,ℓ-1, has just ℓ-1 jump points ji such that ki+1≤ji≤ki+1.Remark 14.
From Theorem9 it follows that the number of idempotents with fixed points k1,…,ks is a semiring of order ∏i=1s-1‍(ki+1-ki). But if two fixed points ki and ki+1 are consecutive, the difference ki+1-ki is equal to 1, and they do not appear in the product. So, the order of the semiring is equal to ∏i=1ℓ-1‍(ki+1-ki), where k1,…,kℓ are (after suitable renumbering) non consecutive fixed points. But for any i the difference ki+1-ki is just the number of possible jump points ji,t=ki+t, where t=1,…,ki+1-ki. So, for given fixed points k1,…,ks the order of semiring of idempotents is equal to the number of all ℓ-1-tuples (j1,t1,j2,t2,…,jℓ-1,tℓ-1), where ji,ti=ki+ti for ti=1,…,ki+1-ki and i=1,…,ℓ-1. Hence, any ℓ-1-tuple (j1,t1,…,jℓ-1,tℓ-1) defines just one idempotent from the semiring considered.
To describe precisely all the fixed points of an arbitrary endomorphismα∈ℰ^𝒞n we will use new indices. Let first fixed point of α be k1,1 and let some fixed points after k1,1 be consecutive; that is, k1,2,…,k1,m1 are fixed points such that k1,i+1-k1,i=1 where i=1,…,m1-1. Let the next fixed point be k2,1 such that k2,1-k1,m1>1. So we construct the first pair of two fixed points which are not consecutive. Let the following fixed points be k2,2,…,k2,m2 such that k2,i+1-k2,i=1 where i=1,…,m2-1. The next fixed point is k3,1 and k3,1-k2,m2>1. Let the last pair of two non consecutive fixed points be kℓ-1,mℓ-1 and kℓ,1. Then the last fixed points are kℓ,2,…kℓ,mℓ such that kℓ,i+1-kℓ,i=1 where i=1,…,mℓ-1. So, we construct a partition of a set of fixed points of α such that we can distinguish the fixed points which are not consecutive.
Letji,ti be the jump points of α such that ji,ti=ki,mi+ti, where ti=1,…,ki+1,1-ki,mi and i=1,…,ℓ-1.
An endomorphismα with fixed points k1,1,…,kℓ,mℓ and jump points ji,ti from the previous definitions is called a endomorphism of type(18)[k1,1,…,k1,m1,j1,t1,k2,1,…,kℓ-1,mℓ-1,jℓ-1,tℓ-1,kℓ,1,…,kℓ,mℓ].
Let us consider endomorphismε of this type such that(i)
ε(x)=k1,1 for any 0≤x≤k1,1,(ii)
ε(x)=ki,mi for any ki,mi≤x≤ji,ti-1, where i=1,…,ℓ-1,(iii)
ε(x)=ki+1,1 for any ji,ti≤x≤ki+1,1, where i=1,…,ℓ-1,(iv)
ε(x)=kℓ,mℓ for any kℓ,mℓ≤x≤n-1.Now it is easy to show that this endomorphism is an idempotent.Letε- be another idempotent of the same type. Then from the reasonings just before  Corollary 13 it follows that(i)
ε-(x)=k1,1 for any 0≤x≤k1,1,(ii)
ε-(x)=kℓ,mℓ for any kℓ,mℓ≤x≤n-1.Sinceε- is an idempotent, we conclude that for some x, where ki,mi≤x≤ki+1,1, it follows either ε-(x)=ki,mi, or ε-(x)=ki+1,1. By using that  ε-  is of type (18) it follows that ε-(x)=ε(x) for all x, where ki,mi≤x≤ki+1,1 and i=1,…,ℓ-1. Hence, there is only one idempotent of the given type (18). This endomorphism is
(19)ε=≀k1,1,…,k1,1↑k1,1,…,k1,m1↑k1,m1,…,k1,m1,k2,1↑j1,t1,…,kℓ-1,mℓ-1,kℓ,1↑jℓ-1,tℓ-1,…,kℓ,mℓ↑kℓ,mℓ,…,kℓ,mℓ≀.Lemma 15.
Letε∈ℰ^𝒞n be an idempotent endomorphism. If α∈ℰ^𝒞n is a root of ε, then both endomorphisms α and ε have the same fixed points.Proof.
Letk be a fixed point of ε. If α(k)<k, then α2(k)≤α(k)<k, and by the same arguments αm(k)<k for arbitrary natural number m, but this is a contradiction to αm=ε for some m∈N. Analogously, assuming that α(k)>k, we obtain a contradiction to equality αm=ε. Hence α(k)=k.
Letk be a fixed point of α. Since it is a fixed point of αm for arbitrary natural m, it follows that it is a fixed point of ε.Lemma 16.
Letε∈ℰ^𝒞n be an idempotent endomorphism. If α∈ℰ^𝒞n is a root of ε, then both endomorphisms α and ε have the same jump points.Proof.
Letj be a jump point of ε and ε(j-1)≤j-1, ε(j)>j. If we assume that α(j-1)>j-1, then αm(j-1)>j-1 for arbitrary natural m which is a contradiction to αm=ε for some m∈N.
Analogously, if we assume thatα(j)≤j, it follows that αm(j)≤j for arbitrary natural m which is also a contradiction. Hence j is a jump point of α such that α(j-1)≤j-1 and α(j)>j. From similar reasonings, it follows that if j is a jump point of ε such that ε(j-1)<j-1 and ε(j)≥j for every endomorphism α, which is a root of ε, we have that j is a jump point of α, α(j-1)<j-1, and α(j)≥j.
Letj be a jump point of α such that α(j-1)≤j-1 and α(j)>j. Then for arbitrary natural m it follows αm(j-1)≤j-1 and αm(j)>j. So, j is a jump point of ε, ε(j-1)≤j-1 and ε(j)>j. Analogously, α(j-1)<j-1 and α(j)≥j imply αm(j-1)<j-1 and αm(j)≥j for every natural number m, so j is a jump point of ε, ε(j-1)<j-1 and ε(j)≥j.Immediately from Lemmas15 and 16 follows Proposition 17.Proposition 17.
All the endomorphisms of one equivalence class modulo~ are of the same type.Let the idempotent endomorphismε from (19) be an element of equivalence class E. Then E is called an equivalence class of type (18).Lemma 18.
LetE be an equivalence class of type (18). Then any α∈E satisfies the following conditions:(A)
α(x)>x, where 0≤x<k1,1, j1,t1≤x<k2,1, j2,t2≤x<k3,1, …, or jℓ-1,tℓ-1≤x<kℓ,1;(B)
α(x)<x, where k1,m1<x<j1,t1, k2,m2<x<j2,t2, …, kℓ-1,mℓ-1<x<jℓ-1,tℓ-1, or kℓ,mℓ<x≤n-1.Proof.
We assume that for somex such that
(20)0≤x<k1,1,orj1,t1≤x<k2,1,orj2,t2≤x<k3,1,…,orjℓ-1,tℓ-1≤x<kℓ,1
it follows that α(x)≤x. Then α2(x)≤α(x)≤x and by induction αm(x)≤x for arbitrary natural m. It is a contradiction to the assumption that αm=ε for some natural m, where ε has the form (19). Thus we prove that α(x)>x.
Analogously, we assume that for somex such that
(21)k1,m1<x<j1,t1,ork2,m2<x<j2,t2,…,orkℓ-1,mℓ-1<x<jℓ-1,tℓ-1,orkℓ,mℓ<x≤n-1
it follows α(x)≥x. Then by induction αm(x)≥x for arbitrary natural m. This contradicts the assumption that αm=ε for some natural m, where ε has the form (19). Thus we prove that α(x)<x.Note that if two endomorphisms have the same fixed points but different jump points, their product can posses a new fixed point. For instance, endomorphismsα=≀2,2,2,4,5,5,5≀~ε1=≀2,2,2,5,5,5,5≀ and β=≀2,2,2,2,3,5,5≀~ε2=≀2,2,2,2,2,5,5≀ have fixed points 2 and 5 but α·β=≀2,2,2,3,5,5,5≀ and β·α=≀2,2,2,2,4,5,5≀ have new fixed points 3 and 4, respectively.Let us remind that the jump points, which we use in (18), are defined by equality ji,ti=ki,mi+ti. So it follows that ji,ti-ki,mi=ti. Now we denote ki+1,1-ji,ti=si. The indices ti and si will be used in the next theorem.Theorem 19.
Every equivalence class modulo~ of type (18) is a subsemiring of ℰ^𝒞n, n≥2. The order of this semiring is
(22)Ck1,1(∏i=1ℓ-1‍CtiCsi)Cn-1-kℓ,mℓ,
where Cp is the pth Catalan number.Proof. Let E be an equivalence class of type (18) and α,β∈E. Using Lemma 18 it follows that(A)
α(x)>x and β(x)>x, where 0≤x<k1,1, j1,t1≤x<k2,1, j2,t2≤x<k3,1,…, or jℓ-1,tℓ-1≤x<kℓ,1. Then (α+β)(x)=α(x)∨β(x)>x∨x=x and (α·β)(x)=β(α(x))≥β(x)>x.(B)
α(x)<x and β(x)<x, where k1,m1<x<j1,t1, k2,m2<x<j2,t2, …, or kℓ-1,mℓ-1<x<jℓ-1,tℓ-1, or kℓ,mℓ<x≤n-1. Then (α+β)(x)=α(x)∨β(x)<x∨x=x and (α·β)(x)=β(α(x))≤β(x)<x.Thus we prove that equivalence classE is a subsemiring of ℰ^𝒞n.For the second part of the proof of the theorem we needed two combinatorial lemmas.Lemma 20.
The number of the orderedp-tuples (i0,…,ip-1), where (1)
ir∈{0,…,p-1} for r=0,…,p-1,(2)
ir≤ir+1 for r=0,…,p-1,(3)
ir<r for r=1,…,p-1,is thepth Catalan number Cp=(1/p)(2p-1p-1).The proof of this lemma is a part of the proof of Proposition 3.4 of [7]. This result (using the so-called Dyck paths) and many other applications of Catalan numbers can be found in [11].Lemma 21.
The number of the orderedp-tuples (i0,…,ip-1), where (1)
ir∈{1,…,p} for r=0,…,p-1, ip=p,(2)
ir≤ir+1 for r=0,…,p-1,(3)
ir>r for r=0,…,p-1is thepth Catalan number Cp=(1/p)(2p-1p-1).Proof of Lemma21.
Let(i0,…,ip-1) be the ordered p-tuple. Since ir>r for any r=0,…,p-1, follows that p=ip≥ip-1>p-1; that is, ip-1=p. Instead of the p-tuple (i0,…,ip-1) we consider the p-tuple (j0,…,jp-1), where jm=p-ip-m-1, m=0,…,p-1. Then jm<m and jm≤jm+1. From Lemma 20 it follows that the number of all k-tuples of this kind is Ck.
Now we continue the proof of the theorem.
For all the intervals considered in part (A) (from the beginning of this proof) we apply Lemma21. Then, for all the intervals considered in part (B) we apply Lemma 20. Hence we find that the number of the endomorphisms in the equivalence class modulo ~ of type (1) is Ck1,1(∏i=1ℓ-1‍CtiCsi)Cn-1-kℓ,mℓ.Remark 22.
The equivalence relation~ is not a congruence on ℰ^𝒞n. For n=8 we consider the endomorphisms
(23)α=≀2,2,2,2,2,6,7,7≀~ε1=≀2,2,2,2,2,7,7,7≀,β=≀2,2,2,2,3,7,7,7≀~ε1=≀2,2,2,2,2,7,7,7≀,γ=≀1,1,1,3,3,4,5,6≀~ε2=≀1,1,1,3,3,3,3,3≀.
Now we compute α·γ=≀1,1,1,1,1,5,6,6≀ and β·γ=≀1,1,1,1,3,6,6,6≀. So, it follows that α~β, but α·γ≁β·γ.


## 5. The Crucial Role of Jump Points

Here we consider the idempotent endomorphisms with arbitrary fixed points but we assume that each endomorphism hasj1,…,jr for jump points.Two jump pointsjs and js+1 of the idempotent ε are called consecutive if js+1=js+1. First, let us answer the question: are there any consecutive jump points of the idempotent endomorphism?Yes, for instance,ε=≀1,1,1,3,5,5≀∈ℰ^𝒞6 is an idempotent and jump points 3 and 4 are consecutive. Note that 3 is also a fixed point of ε. So, we modify the question: If the first jump point is not a fixed point, is it possible fort the next point to be a jump point?The answer is negative. Indeed, ifε is an idempotent and ε(j)=k>j, then from Proposition 1 it follows that ε(k)=k, and, since j+1≤k, we have ε(j+1)≤k. So, j+1 is not a jump point of ε.Lemma 23.
Letε be an idempotent and js and let js+1 be non consecutive jump points of ε. Then in interval [js,js+1-1] one of the following holds:(1)
ε is a constant endomorphism.(2)
ε is an identity.(3)
ε is an identity in interval [js,k] and a constant endomorphism in interval [k,js+1-1].(4)
ε is a constant endomorphism in interval [js,k], and an identity in interval [k,js+1-1].(5)
ε is a constant endomorphism in interval [js,k], an identity in interval [k,ℓ] and a constant endomorphism in interval [ℓ,js+1-1].Proof.
Letε(js)=js. Since js+1 is not a jump point, there are two possibilities: ε(js+1)=js or ε(js+1)=js+1. In the first case the equality ε(js+2)=js+1 is impossible; see Proposition 1. So, either ε(js+2)≥js+2 and js+2 is the next jump point or ε(js+2)=js. From these reasonings, it follows that ε is a constant endomorphism in interval [js,js+1-1]. When ε(js+1)=js+1 for point js+2, there are three possibilities. If ε(js+2)>js+2, then js+2 is the next jump point and ε is an identity in the interval between the considered jump points. If ε(js+2)=js+1, by the previous reasonings, we find that ε is an identity in interval [js,js+1] and a constant endomorphism in the second interval. Let ε(js+2)=js+2. Now if for any k≤js+1-1, it follows that ε(js+k)=js+k. Then ε is an identity in the whole interval. If for some k we have ε(js+k+1)=ε(js+k)=js+k, then ε is an identity in interval [js,k] and a constant endomorphism in interval [k,js+1-1].
Letε(js)=k>js. Since ε is an idempotent, it follows that ε(k)=k; that is ε is a constant endomorphism in interval [js,k]. If ε(k+1)=k then ε is a constant endomorphism in the whole interval. Let ε(k+1)=k+1, and for any ℓ, where ℓ=k+1,…,js+1-1, we have ε(ℓ)=ℓ. So, ε is a constant endomorphism in interval [js,k] and an identity in interval [k,js+1-1]. In the end, if there is some ℓ, ℓ=k+1,…,js+1-1, such that ε(ℓ+1)=ε(ℓ)=ℓ, then ε is a constant endomorphism in interval [js,k], an identity in interval [k,ℓ], and a constant endomorphism in interval [ℓ,js+1-1].It is straightforward to show that if one of the conditions (1)–(5) of Lemma23 holds for endomorphism ε, then ε is an idempotent.From Lemma23 it follows that the graph of the arbitrary idempotent endomorphism has the shape displayed on Figure 1. Note that each of the three segments of this graph can have length zero.Figure 1Letjs and js+1 be consecutive jump points of the idempotent ε. Then the graph of ε is a particular case of those displayed in Figure 1 containing one point (js,ε(js)), where ε(js)=js.Lemma 24.
Letε and ε- be idempotent endomorphisms of ℰ^𝒞n with the same jump points j1,…,jr. Then ε+ε- is also an idempotent endomorphism with the same jump points.Proof.
First we will prove thatj1,…,jr are jump points of endomorphism ε+ε-. Let j be any common jump point of ε and ε-. If j is also a fixed point of ε and ε-, that is, both idempotents satisfied the inequalities ε(j-1)<j-1 and ε(j)≥j, ε-(j-1)<j-1 and ε-(j)≥j, then (ε+ε-)(j-1)<j-1 and (ε+ε-)(j)≥j. When for ε it follows that ε(j-1)≤j-1 and ε(j)>j or for ε- it follows that ε-(j-1)≤j-1 and ε-(j)>j, then (ε+ε-)(j-1)≤j-1 and (ε+ε-)(j)>j.
Now we will prove that sumε+ε- is an idempotent endomorphism. Let us, like in Lemma 23, fix two nonconsecutive jump points js and js+1 of idempotents ε and ε- and the interval [js,js+1-1].
When the idempotentε satisfies some the of conditions (1)–(5) of Lemma 23, we denote this by ε(1),…,ε(5).
Whenε satisfies (1) and ε- satisfies (5), we denote this by ε(1)&ε-(5). Let, in this case, ε be equal to constant C in interval [js,js+1-1], and ε- is consecutively equal to constant k, identity i, and constant ℓ. If C≤k or C≥ℓ, then ε+ε-=C. If k<C<ℓ, then ε+ε- satisfy condition (5). This reasoning we denote by ε(1)&ε-(5)⇒(ε+ε-)(1)  or  (ε+ε-)(5).
The verification of all fifteen possibilities is easy:(24)ε(1)&ε-(1)⟹(ε+ε-)(1),ε(1)&ε-(2)⟹(ε+ε-)(1)or(ε+ε-)(2)or(ε+ε-)(4),ε(1)&ε-(3)⟹(ε+ε-)(1)or(ε+ε-)(3)or(ε+ε-)(5),ε(1)&ε-(4)⟹(ε+ε-)(1)or(ε+ε-)(4)or(ε+ε-)(5),ε(1)&ε-(5)⟹(ε+ε-)(1)or(ε+ε-)(5),ε(2)&ε-(2)⟹(ε+ε-)(2),ε(2)&ε-(3)⟹(ε+ε-)(2),ε(2)&ε-(4)⟹(ε+ε-)(4),ε(2)&ε-(5)⟹(ε+ε-)(4),ε(3)&ε-(3)⟹(ε+ε-)(3),ε(3)&ε-(4)⟹(ε+ε-)(4),ε(3)&ε-(5)⟹(ε+ε-)(5),ε(4)&ε-(4)⟹(ε+ε-)(4),ε(4)&ε-(5)⟹(ε+ε-)(4),ε(5)&ε-(5)⟹(ε+ε-)(5).
Thus we prove that the sum of two idempotent endomorphisms in interval[js,js+1-1] is also an idempotent in this interval. So, it follows that ε+ε- is an idempotent endomorphism in interval [j1,jr]. For 0≤x<j1 each of idempotents ε and ε- satisfies one of conditions (1)–(5) of Lemma 23. So, from the previous reasonings it follows that sum ε+ε- is an idempotent endomorphism in [0,j1-1]. In a similar way we show that ε+ε- is an idempotent endomorphism in [jr,n-1]. Hence, ε+ε- is an idempotent endomorphism in the whole chain 𝒞n.Lemma 25.
Letε and ε- be idempotent endomorphisms of ℰ^𝒞n with the same jump points j1,…,jr. Then ε·ε- is also an idempotent endomorphism with the same jump points.Proof.
First we will prove thatj1,…,jr are the jump points of endomorphism ε·ε-. Let j be any common jump point of ε and ε-. Let j be also a fixed point of ε or of ε-; that is, ε(j-1)<j-1 and ε(j)≥j or ε-(j-1)<j-1 and ε-(j)≥j. Then it follows that in all cases (ε·ε-)(j-1)=ε-(ε(j-1))<j-1 and (ε·ε-)(j)=ε-(ε(j))≥j. Let j be not a fixed point of both idempotents; that is, ε(j-1)≤j-1 and ε(j)>j and also ε-(j-1)≤j-1 and ε-(j)>j. At last, we obtain that (ε·ε-)(j-1)=ε-(ε(j-1))≤ε-(j-1)≤ε(j-1) and (ε·ε-)(j)=ε-(ε(j-1))>ε-(j-1)>ε(j-1).
Now we will prove thatε·ε- is an idempotent endomorphism. Like in the proof of the previous lemma, we fix two nonconsecutive jump points js and js+1 of idempotents ε and ε- and interval [js,js+1-1].
Using the notations from the proof of Lemma24 we easily verify all twenty-five possibilities:
(25)ε(1)·ε-(1)=ε(1),ε(1)·ε-(2)=ε(1),ε(1)&ε-(3)⟹(ε·ε-)(1),ε(1)&ε-(4)⟹(ε·ε-)(1),ε(1)&ε-(5)⟹(ε·ε-)(1),ε(2)·ε-(1)=ε-(1),ε(2)·ε-(2)=ε-(2),ε(2)·ε-(3)=ε-(3),ε(2)·ε-(4)=ε-(4),ε(2)·ε-(5)=ε-(5),ε(3)·ε-(1)=ε-(1),ε(3)·ε-(2)=ε(3),ε(3)&ε-(3)⟹(ε·ε-)(3),ε(3)&ε-(4)⟹(ε·ε-)(1)or(ε·ε-)(5),ε(3)&ε-(5)⟹(ε·ε-)(1)or(ε·ε-)(5),ε(4)·ε-(1)=ε-(1),ε(4)·ε-(2)=ε(4),ε(4)&ε-(3)⟹(ε·ε-)(1)or(ε·ε-)(5),ε(4)&ε-(4)⟹(ε·ε-)(4),ε(4)&ε-(5)⟹(ε·ε-)(1)or(ε·ε-)(5),ε(5)·ε-(1)=ε-(1),ε(5)·ε-(2)=ε(5),ε(5)&ε-(3)⟹(ε·ε-)(1)or(ε·ε-)(5),ε(5)&ε-(4)⟹(ε·ε-)(1)or(ε·ε-)(5),ε(5)&ε-(5)⟹(ε·ε-)(1)or(ε·ε-)(5).
Thus we prove that the product of both idempotent endomorphisms in interval[js,js+1-1] is also an idempotent in this interval. It easily implies that ε·ε- is an idempotent endomorphism in the whole interval [j1,jr]. In interval [0,j1-1] each one of  the idempotents ε and ε- satisfies one of the conditions (1)–(5), of Lemma 23. So, from the previous reasonings it follows that the product ε·ε- is an idempotent endomorphism in [0,j1-1]. In a similar way we show that ε·ε- is an idempotent endomorphism in [jr,n-1]. Hence, ε·ε- is an idempotent endomorphism in the whole 𝒞n.Immediately from Lemmas24 and 25  follows Theorem 26.Theorem 26.
The set of the idempotent endomorphisms ofℰ^𝒞n with the same jump points is a subsemiring of ℰ^𝒞n.From Lemmas24 and 25, and Figure 1 it is easy to prove the following.Proposition 27.
The set of the idempotent endomorphisms ofℰ^𝒞n without jump points is a subsemiring of ℰ^𝒞n of order (n+12).



---

*Source: 120231-2013-02-26.xml*