# The structure of END($\mathcal{T}_{n}$)

Victoria Gould  University of York<EMAIL_ADDRESS>,  Ambroise Grau
University of York<EMAIL_ADDRESS>and  Marianne Johnson  University
of Manchester<EMAIL_ADDRESS>
###### Abstract.

The full transformation semigroups $\mathcal{T}_{n}$, where $n\in\mathbb{N}$,
consisting of all maps from a set of cardinality $n$ to itself, are arguably
the most important family of finite semigroups. This article investigates the
endomorphism monoid $\mathrm{End}(\mathcal{T}_{n})$ of $\mathcal{T}_{n}$. The
determination of the elements of $\mathrm{End}(\mathcal{T}_{n})$ is due Schein
and Teclezghi. Surprisingly, the algebraic structure of
$\mathrm{End}(\mathcal{T}_{n})$ has not been further explored. We describe
Green’s relations and extended Green’s relations on
$\mathrm{End}(\mathcal{T}_{n})$, and the generalised regularity properties of
these monoids. In particular, we prove that
$\mathop{\mathscr{H}}=\mathop{\mathscr{L}}\subseteq\mathop{\mathscr{R}}=\mathop{\mathscr{D}}=\mathop{\mathscr{J}}$
(with equality if and only if $n=1$); the idempotents of
$\mathrm{End}(\mathcal{T}_{n})$ form a band (which is equal to
$\mathrm{End}(\mathcal{T}_{n})$ if and only if $n=1$) and also the regular
elements of $\mathrm{End}(\mathcal{T}_{n})$ form a subsemigroup (which is
equal to $\mathrm{End}(\mathcal{T}_{n})$ if and only if $n\leq 2$). Further,
the regular elements of $\mathrm{End}(\mathcal{T}_{n})$ are precisely the
idempotents together with all endomorphisms of rank greater than $3$. We also
provide a presentation for $\mathrm{End}(\mathcal{T}_{n})$ with respect to a
minimal generating set.

###### Key words and phrases:

Full transformation semigroup; endomorphisms; ideals; presentations

###### 2020 Mathematics Subject Classification:

Primary: 20M05, 20M10, 20M20

##  1\. Introduction

The full transformation semigroup $\mathcal{T}_{n}$ on a finite set
$\\{1,\ldots,n\\}$ is an important object in algebra. It is therefore natural
to study its endomorphism monoid $\mathrm{End}(\mathcal{T}_{n})$. The elements
of $\mathrm{End}(\mathcal{T}_{n})$ were described by Schein and Teclezghi
[21], and we use this description as the starting point for our investigation
of the algebraic structure and properties of $\mathrm{End}(\mathcal{T}_{n})$.
Our initial task is to partition $\mathrm{End}(\mathcal{T}_{n})$ in several
ways, depending on the rank of an element (the cardinality of its image) and
type of an element (a quality of the image that determines the behaviour of
the element in products). This partitioning is then made use of throughout the
text.

One of the first questions to ask about a monoid $S$ is whether it is regular,
that is, for any $a\in S$ there is a $b\in S$ such that $a=aba$. Regularity is
intimately connected with the position and nature of the idempotents in the
monoid, where $e\in S$ is idempotent if $e=e^{2}$. We show that for $n\geq 3$
the monoid $\mathrm{End}(\mathcal{T}_{n})$ is not regular. On the other hand
the set of idempotents of $\mathrm{End}(\mathcal{T}_{n})$ is very special in
that it is a band, that is, a semigroup of idempotents. Moreover it is a
special kind of band, namely a left regular band.

We next investigate minimal generating sets of
$\mathrm{End}(\mathcal{T}_{n})$, and provide a presentation for
$\mathrm{End}(\mathcal{T}_{n})$ in terms of these generators.

A major tool used in understanding monoids is that of Green’s relations
$\mathop{\mathscr{R}},\mathop{\mathscr{L}},\mathop{\mathscr{H}},\mathop{\mathscr{D}}$
and $\mathop{\mathscr{J}}$, which measure mutual divisibility properties
between elements by considering the principal (one-sided) ideals that they
generate. Specifically, for elements $a,b$ of a monoid $S$ we have
$a\mathop{\mathscr{R}}b$ if and only if $aS=bS$; this is equivalent to $a=bs$
and $b=at$ for some $s,t\in S$. The relation $\mathop{\mathscr{L}}$ is defined
dually, and $\mathop{\mathscr{J}}$ is defined by $a\mathop{\mathscr{J}}b$ if
and only if $SaS=SbS$. Finally,
$\mathop{\mathscr{H}}=\mathop{\mathscr{R}}\wedge\mathop{\mathscr{L}}=\mathop{\mathscr{R}}\cap\mathop{\mathscr{L}}$
and
$\mathop{\mathscr{D}}=\mathop{\mathscr{R}}\vee\mathop{\mathscr{L}}=\mathop{\mathscr{R}}\circ\mathop{\mathscr{L}}$
with $\mathop{\mathscr{D}}=\mathop{\mathscr{J}}$ for a finite semigroup; the
latter two assertions are theorems - see, for example, [11]. We characterise
Green’s relations on $\mathrm{End}(\mathcal{T}_{n})$. In particular, we show
that
$\mathop{\mathscr{H}}=\mathop{\mathscr{L}}\subseteq\mathop{\mathscr{R}}=\mathop{\mathscr{D}}=\mathop{\mathscr{J}}$,
and for $n\neq 4$ the relation $\mathop{\mathscr{L}}$ is trivial outside of
the group of units. We then use the description of $\mathop{\mathscr{J}}$ to
fully determine the ideals of $\mathrm{End}(\mathcal{T}_{n})$.

Green’s relations provide an alternative characterisation of regularity,
specifically, a monoid is regular if every $\mathop{\mathscr{R}}$-class (or,
equivalently, every $\mathop{\mathscr{L}}$-class) contains an idempotent. We
have commented that $\mathrm{End}(\mathcal{T}_{n})$ is not regular, however,
we show that it satisfies the weaker property of being left abundant, where a
monoid is left abundant if every class of the extended Green’s relation
$\mathop{\mathscr{R}^{*}}$ contains an idempotent. This follows from the fact
that the relation $\mathop{\mathscr{R}^{*}}$ on $\mathcal{E}_{n}$ precisely
captures the relation of having the same rank. We postpone giving the
definitions of the extended Green’s relations
$\mathop{\mathscr{R}^{*}},\mathop{\mathscr{L}^{*}},\mathop{\mathscr{H}^{*}},\mathop{\mathscr{D}^{*}}$
and $\mathop{\mathscr{J}^{*}}$ until later in the text, but suffice to say
here they are relations of mutual cancellativity. They first arose in the work
of Pastijn [19] and McAlister [17]. As observed in [6], it follows from [12]
that a monoid is left abundant precisely when every monogenic right act is
projective. We determine the $*$-relations
$\mathop{\mathscr{R}^{*}},\mathop{\mathscr{L}^{*}},\mathop{\mathscr{H}^{*}},\mathop{\mathscr{D}^{*}}$
and $\mathop{\mathscr{J}^{*}}$ on $\mathrm{End}(\mathcal{T}_{n})$, from which
we observe that $\mathrm{End}(\mathcal{T}_{n})$ does not satisfy the dual
property of being right abundant. To complete the picture of the extended
Green’s relations we consider the $\sim$-relations
$\mathop{\widetilde{\mathscr{R}}},\mathop{\widetilde{\mathscr{L}}},\mathop{\widetilde{\mathscr{H}}},\mathop{\widetilde{\mathscr{D}}}$
and $\mathop{\widetilde{\mathscr{J}}}$ which extend the corresponding
$*$-relations. They are formulated using idempotent left identities: again, we
postpone their definition until later. The $\sim$-relations first appear in
[5] and have subsequently proved to be useful in a number of ways. For
example, they are inherent in the characterisation of left restriction
semigroups [10] and in determining varieties containing quasi-varieties of
abundant semigroups.

The main focus of our work will be on the general behaviour of
$\mathrm{End}(\mathcal{T}_{n})$ which emerges for $n\geq 5$. The cases $n\leq
4$ exhibit several degenerate or exceptional behaviours: for instance, it is
immediate that $\mathrm{End}(\mathcal{T}_{1})=\mathrm{Aut}(\mathcal{T}_{1})$
is the trivial group, and we will see that $\mathrm{End}(\mathcal{T}_{4})$ is
unique in that it contains endomorphisms of rank $7$.

The structure of the paper is as follows. In Section 2 we remind the reader of
the description of the elements of $\mathcal{E}_{n}$ from [21]. We prove
several fundamental results concerning the non-automorphisms in
$\mathrm{End}(\mathcal{T}_{n})$ and give the partitions promised above.
Sections 3–6 consider the structure of $\mathrm{End}(\mathcal{T}_{n})$ for
$n\geq 5$: in Section 3 we describe some properties of the idempotents and
determine the regular elements; in Section 4 we provide a minimal generating
set and describe a presentation for $\mathrm{End}(\mathcal{T}_{n})$ in terms
of these generators; in Section 5 we give a description of Green’s relations
and use this to determine the ideal structure of
$\mathrm{End}(\mathcal{T}_{n})$; we consider the extended Green’s relations on
$\mathrm{End}(\mathcal{T}_{n})$ in Section 6. To complete the picture, in
Section 7, we analyse the structure of $\mathrm{End}(\mathcal{T}_{n})$ for
$n\leq 4$. Finally, in Section 8, we indicate how the ideas in this article
could be developed and extended.

Notation and conventions: Throughout the paper we write
$\mathcal{S}_{n}\subseteq\mathcal{T}_{n}$ to denote the symmetric group and
$\mathcal{A}_{n}\subseteq\mathcal{S}_{n}$ the alternating group, that is, the
subgroup of $\mathcal{S}_{n}$ of all even permutations. By a slight abuse of
notation, we suppress the dependence on $n$ and write simply $\mathrm{id}$ to
denote the identity element of $\mathcal{T}_{n}$. For an element
$g\in\mathcal{S}_{n}$, and $s\in\mathcal{T}_{n}$, we denote by $s^{g}$ the
product $g^{-1}sg$. For $1\leq i\neq j\leq n$ we also write $(i\,j)$ for the
transposition swapping $i$ and $j$ in $\mathcal{S}_{n}$, and $c_{i}$ for the
constant map with image $i$ in $\mathcal{T}_{n}$. For $n\neq 4$, the
alternating group is the only non-trivial proper normal subgroup of
$\mathcal{S}_{n}$, whilst for $n=4$ there is one additional normal subgroup
$\mathcal{K}=\\{\mathrm{id},(1\,2)(3\,4),(1\,3)(2\,4),(1\,4)(2\,3)\\}$. A
straightforward calculation reveals that for any $t\in\mathcal{S}_{4}$ there
is a unique element of $\mathcal{K}t$ which fixes $4$. To facilitate
readability, we take the convention that elements of $\mathcal{T}_{n}$ will be
written using Roman letters, while endomorphisms of $\mathcal{T}_{n}$ will be
written using Greek letters. We will also use the short-hand notation
$\mathcal{E}_{n}=\mathrm{End}(\mathcal{T}_{n})$ and
$\mathcal{G}_{n}=\mathrm{Aut}(\mathcal{T}_{n})$ for the endomorphism monoid
and automorphism group of $\mathcal{T}_{n}$. The identity element of
$\mathcal{E}_{n}$ (and hence also $\mathcal{G}_{n}$) is the trivial
automorphism, which will be denoted by $\varepsilon$ (again, suppressing the
dependence on $n$ where convenient).

We attempt to keep the exposition as self-contained as possible, but refer the
reader to [11] for further details of semigroup notions we employ.

##  2\. Singular endomorphisms

In this section we record several useful properties of the endomorphisms in
$\mathcal{E}_{n}\setminus\mathcal{G}_{n}$ of $\mathrm{End}(\mathcal{T}_{n})$,
which we refer to as singular endomorphisms. We begin by recalling the
characterisation of the semigroup endomorphisms of $\mathcal{T}_{n}$ (that is,
endomorphisms preserving the binary operation, but not necessarily the
identity) due to Schein and Teclezghi [21].

######  Theorem 2.1 ([21]).

Let $g\in\mathcal{S}_{n}$ and $t,e\in\mathcal{T}_{n}$ and define maps
$\psi_{g}$ and $\phi_{t,e}$ for any $s\in\mathcal{T}_{n}$ by:

$s\psi_{g}=s^{g}\quad\text{and}\quad s\phi_{t,e}=\begin{cases}t&\mbox{if
}s\in\mathcal{S}_{n}\setminus\mathcal{A}_{n},\\\ t^{2}&\mbox{if
}s\in\mathcal{A}_{n},\\\ e&\mbox{if
}s\in\mathcal{T}_{n}\setminus\mathcal{S}_{n}.\end{cases}$

Then the automorphisms and endomorphisms of $\mathcal{T}_{n}$ are described as
follows.

  1. (1)

$\mathcal{G}_{n}=\\{\psi_{g}:g\in\mathcal{S}_{n}\\}$.

  2. (2)

For $n\neq 4$,

$\mathcal{E}_{n}=\mathcal{G}_{n}\cup\\{\phi_{t,e}:t,e\in\mathcal{T}_{n},\,t^{3}=t,\;te=et=e^{2}=e\\}.$

  3. (3)

For $n=4$

$\mathcal{E}_{4}=\mathcal{G}_{4}\cup\\{\phi_{t,e}:t,e\in\mathcal{T}_{4},\,t^{3}=t,\;te=et=e^{2}=e\\}\cup\\{\sigma^{g}:g\in\mathcal{S}_{4}\\},$

where $s\sigma=c_{4}$ if $s\in\mathcal{T}_{4}\setminus\mathcal{S}_{4}$ and
$s\sigma=p_{s}$ if $s\in\mathcal{S}_{4}$, where $p_{s}$ denotes the unique
element in the coset of $\mathcal{K}s$ which fixes $4$, and for all
$s\in\mathcal{T}_{4}$ and all $g\in\mathcal{S}_{4}$
$s\sigma^{g}=(s\sigma)^{g}$.

We remark that in the case $n=4$ in Theorem 2.1 there is no bias towards 4;
any apparent bias is dealt with by the process of conjugation. Note also that
$\sigma=\sigma^{\mathrm{id}}$ and $\psi_{\mathrm{id}}=\varepsilon$.

It is easy to see that for any $g,h\in\mathcal{S}_{n}$ we have that
$\psi_{g}\psi_{h}=\psi_{gh}$. Further if $\psi_{g}=\psi_{h}$ then an easy
computation gives that for any $i\in\\{1,\ldots,n\\}$ we have that
$c_{ig}=c_{i}\psi_{g}=c_{i}\psi_{h}=c_{ih}$, so that $ig=ih$ and, since $i$
was arbitrary, $g=h$. It follows that $\mathcal{G}_{n}$ is isomorphic to the
symmetric group $\mathcal{S}_{n}$. For $\alpha\in\mathcal{E}_{n}$ we write
$\mathrm{im\,}\alpha$ to denote the image of $\alpha$, and define the rank of
$\alpha$ to be the cardinality of $\mathrm{im\,}\alpha$. Clearly the image of
each automorphism $\psi_{g}$ is the whole of $\mathcal{T}_{n}$, and hence has
rank $\lvert\mathcal{T}_{n}\rvert=n^{n}$. The remaining endomorphisms, that
is, the singular endomorphisms, have rank strictly less than $n^{n}$. From the
above theorem the rank of each singular endomorphism is either $1,2,3,$ or
$7$. For, the image of each endomorphism of the form $\phi_{t,e}$ is the set
$\left\\{t,t^{2},e\right\\}$, which can have up to three distinct elements. In
the case where $n=4$ an easy computation gives that
$\mathrm{im\,}\sigma^{g}=\\{t^{g}:t\in\mathcal{S}_{4},4t=4\\}\cup\\{c_{4g}\\},$
has precisely $7$ elements.

###  2.1. Endomorphisms of rank at most 3

In order to encapsulate the conditions of the elements $t$ and $e$ so that
$\phi_{t,e}$ is an endomorphism, we let

$U_{n}=\left\\{t\in\mathcal{T}_{n}\mid t^{3}=t\text{ with }te=et=e^{2}=e\text{
for some }e\in\mathcal{T}_{n}\right\\}.$

We say that $(t,e)$ form a _permissible pair_ , if
$\phi_{t,e}\in\mathcal{E}_{n}$, and we denote by $P_{n}$ the set of all
permissible pairs, that is,

$P_{n}=\left\\{(t,e)\mid t\in U_{n},\,te=et=e^{2}=e\right\\}.$

Before considering the endomorphisms in $\mathcal{E}_{n}$ further, we give
some important properties of the sets $U_{n}$ and $P_{n}$.

######  Lemma 2.2.

The set $U_{n}$ consists of all elements $t=t^{3}$ satisfying $kt=k$ for at
least one $1\leq k\leq n$. Moreover, for $t\in U_{n}$ the number of
permissible pairs with first component equal to $t$ is

$\sum_{r=1}^{|J|}\binom{|J|}{r}r^{|I|+|J|-r}$

where $J=\\{k:kt=k\\}$ and $I$ is maximal such that $t$ restricts to a fixed
point free permutation on $I\cup It$.

###### Proof.

Let $t\in U_{n}$. By definition we have $t^{3}=t$. Note that if there exists
$e\in\mathcal{T}_{n}$ such that $et=e$, then then for all
$k\in\\{1,\ldots,n\\}$ we must have $ket=ke$, giving that all elements in the
image of $e$ are fixed by $t$. Conversely, suppose that $t^{3}=t$ and $kt=k$.
Then it is easy to see that $c_{k}t=tc_{k}=c_{k}=c_{k}^{2}$, and hence $t\in
U_{n}$.

Note that if $t\in\mathcal{T}_{n}$ satisfies $t^{3}=t$ then for all
$k\in\\{1,\ldots,n\\}$ there exist $i_{k},j_{k}$ such that $kt=j_{k}$,
$kt^{2}=j_{k}t=i_{k}$ and $kt^{3}=i_{k}t=j_{k}t^{2}=kt$. If $j_{k}=k$ then
also $i_{k}=k$. It follows that $J=\\{k:i_{k}=j_{k}=k\\}$, $K=\\{k:k\neq
j_{k}=i_{k}\\}$, $L=\\{k:k=i_{k}\neq j_{k}\\}$ and $M=\\{k:k\neq j_{k}\neq
i_{k}\neq k\\}$, partition the domain $\\{1,\cdots,n\\}$ of $t$. It is clear
from these definitions that $t$ restricts to the identity on $J$, $Kt\subseteq
J$ and $Mt\subseteq L$. Moreover, $L$ is maximal such that $t$ restricts to a
fixed-point free permutation of order $2$ on $L$; let us partition $L=I\cup
It$.

The general picture to have in mind is as follows. For each transformation
$t\in\mathcal{T}_{n}$ satisfying $t^{3}=t$, we may partition the domain of $t$
as:

$\begin{array}[]{rclc}\\{1,\ldots,n\\}&=&J\cup K\cup L\cup M\mbox{ where }&\\\
J&=&\\{j:jt=jt^{2}=j\\}&\begin{minipage}{113.81102pt}\centering
\leavevmode\hbox to28.73pt{\vbox
to15.21pt{\pgfpicture\makeatletter\hbox{\hskip 5.67825pt\lower-7.60284pt\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{
}\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}{{}}\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{ }{{}{}{{ {}{}}}{ {}{}}
{{}{{}}}{{}{}}{}{{}{}} { }{{{{}}\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@transformcm{1.0}{0.0}{0.0}{1.0}{-2.34525pt}{-2.32541pt}\pgfsys@invoke{
}\hbox{{\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{ }\hbox{{$j$}}
}}\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}} {
{}{}{}}{}\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{ }{ {}{}{}}{}
{{}{{}{}}{}}{{}{{}{}}{}}{{}{}}{{}}
{{}{{}{}}{}}{{{}}{{}}}{{}}{{}{{}{}}{}}{{{}}{{}}}{ {}{}{}}{}{{}}{{{{{}}{
{}{}}{}{}{{}{}}}}}{{}}{}{{{{{{}}{ {}{}}{}{}{{}{}}}}}{}{}{}{}}{}{}{}{}{{}}{}{{
{\pgfsys@beginscope\pgfsys@setlinewidth{0.32pt}\pgfsys@setdash{}{0.0pt}\pgfsys@roundcap\pgfsys@roundjoin{}
{}{}{} {}{}{}
\pgfsys@moveto{-1.19998pt}{1.59998pt}\pgfsys@curveto{-1.09998pt}{0.99998pt}{0.0pt}{0.09999pt}{0.29999pt}{0.0pt}\pgfsys@curveto{0.0pt}{-0.09999pt}{-1.09998pt}{-0.99998pt}{-1.19998pt}{-1.59998pt}\pgfsys@stroke\pgfsys@endscope}}
}{}{}{{}}\pgfsys@moveto{5.87825pt}{1.57495pt}\pgfsys@curveto{19.61989pt}{5.25726pt}{19.61989pt}{-5.25726pt}{7.28848pt}{-1.95284pt}\pgfsys@stroke\pgfsys@invoke{
}{{}{{}}{}{}{{}}{{{}}{{{}}{\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@transformcm{-0.96593}{0.25883}{-0.25883}{-0.96593}{7.28848pt}{-1.95285pt}\pgfsys@invoke{
}\pgfsys@invoke{ \lxSVG@closescope }\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope}}{{}}}}\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{
}{{}{}{{ {}{}}}{ {}{}} {{}{{}}}{{}{}}{}{{}{}} {
}{{{{}}\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@transformcm{1.0}{0.0}{0.0}{1.0}{19.71745pt}{0.0pt}\pgfsys@invoke{
}\hbox{{\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{ }\hbox{}
}}\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope{}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope\hss}}\lxSVG@closescope\endpgfpicture}}\<EMAIL_ADDRESS>K&=&\\{k:kt=kt^{2}\neq k\\}&\begin{minipage}{113.81102pt}\centering
\leavevmode\hbox to74.04pt{\vbox
to13.61pt{\pgfpicture\makeatletter\hbox{\hskip 6.09343pt\lower-6.80522pt\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{
}\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}{{}}\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{ }{{}{}{{ {}{}}}{ {}{}}
{{}{{}}}{{}{}}{}{{}{}} { }{{{{}}\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@transformcm{1.0}{0.0}{0.0}{1.0}{-2.76042pt}{-3.47221pt}\pgfsys@invoke{
}\hbox{{\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{ }\hbox{{$k$}}
}}\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
{{}}\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{ }{{}{}{{ {}{}}}{ {}{}}
{{}{{}}}{{}{}}{}{{}{}} { }{{{{}}\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@transformcm{1.0}{0.0}{0.0}{1.0}{38.11316pt}{-3.47221pt}\pgfsys@invoke{
}\hbox{{\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{ }\hbox{{$kt$}}
}}\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}} {
{}{}{}}{}\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{ }{ {}{}{}}{}{ {}{}{}}
{{{{{}}{ {}{}}{}{}{{}{}}}}}{}{{{{{}}{
{}{}}{}{}{{}{}}}}}{{}}{}{}{}{}{}{{{}{}}}{}{}{}{}{{}}\pgfsys@moveto{6.29343pt}{0.0pt}\pgfsys@lineto{34.12016pt}{0.0pt}\pgfsys@stroke\pgfsys@invoke{
}{{}{{}}{}{}{{}}{{{}}{{{}}{\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@transformcm{1.0}{0.0}{0.0}{1.0}{34.12016pt}{0.0pt}\pgfsys@invoke{
}\pgfsys@invoke{ \lxSVG@closescope }\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope}}{{}}}}\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{
}{{}{}{{ {}{}}}{ {}{}} {{}{{}}}{{}{}}{}{{}{}} {
}{{{{}}\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@transformcm{1.0}{0.0}{0.0}{1.0}{20.43678pt}{0.0pt}\pgfsys@invoke{
}\hbox{{\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{ }\hbox{}
}}\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}} {
{}{}{}}{}\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{ }{ {}{}{}}{}
{{}{{}{}}{}}{{}{{}{}}{}}{{}{}}{{}}
{{}{{}{}}{}}{{{}}{{}}}{{}}{{}{{}{}}{}}{{{}}{{}}}{ {}{}{}}{}{{}}{{{{{}}{
{}{}}{}{}{{}{}}}}}{{}}{}{{{{{{}}{
{}{}}{}{}{{}{}}}}}{}{}{}{}}{}{}{}{}{{}}{}{}{}{}{{}}\pgfsys@moveto{50.77812pt}{2.1697pt}\pgfsys@curveto{64.51976pt}{5.85237pt}{64.51976pt}{-5.85237pt}{52.18834pt}{-2.54762pt}\pgfsys@stroke\pgfsys@invoke{
}{{}{{}}{}{}{{}}{{{}}{{{}}{\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@transformcm{-0.96591}{0.25887}{-0.25887}{-0.96591}{52.18835pt}{-2.54762pt}\pgfsys@invoke{
}\pgfsys@invoke{ \lxSVG@closescope }\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope}}{{}}}}\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{
}{{}{}{{ {}{}}}{ {}{}} {{}{{}}}{{}{}}{}{{}{}} {
}{{{{}}\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@transformcm{1.0}{0.0}{0.0}{1.0}{64.61732pt}{0.0pt}\pgfsys@invoke{
}\hbox{{\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{ }\hbox{}
}}\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope{}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope\hss}}\lxSVG@closescope\endpgfpicture}}\@add@centering\end{minipage}\\\
L&=&\\{l:lt\neq lt^{2}=l\\}&\begin{minipage}{113.81102pt}\centering
\leavevmode\hbox to83.23pt{\vbox
to29.93pt{\pgfpicture\makeatletter\hbox{\hskip
16.38574pt\lower-14.96292pt\hbox to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{
}\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}{{}}\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{ }{{}{}{{ {}{}}}{ {}{}}
{{}{{}}}{{}{}}{}{{}{}} { }{{{{}}\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@transformcm{1.0}{0.0}{0.0}{1.0}{-13.05273pt}{-3.97762pt}\pgfsys@invoke{
}\hbox{{\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{ }\hbox{{$l=lt^{2}$}}
}}\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
{{}}\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{ }{{}{}{{ {}{}}}{ {}{}}
{{}{{}}}{{}{}}{}{{}{}} { }{{{{}}\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@transformcm{1.0}{0.0}{0.0}{1.0}{50.30412pt}{-3.97762pt}\pgfsys@invoke{
}\hbox{{\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{ }\hbox{{$lt\phantom{t^{2}}$}}
}}\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}} {
{}{}{}}{}\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{ } { {}{}{}}{}{
{}{}{}}{ {}{}{}}{{{{}}{{}}{{}}{{}}}{{{{}}{ {}{}}{}{}{{}{}}}}
}{{{{}}{{}}{{}}{{}}{{}}}{{{{}}{ {}{}}{}{}{{}{}}}} }{{}{}}{{}}
{}{}{}{{{}}{{}}{{}}} {{{}}{{}}{{}}}
{}{{}}{}{{}}{}{{}}{}{}{}{}{}{}{}{{}}{}{}{}{}{{}}\pgfsys@moveto{13.00685pt}{-7.51062pt}\pgfsys@curveto{24.76575pt}{-13.54874pt}{35.66249pt}{-13.01175pt}{46.38455pt}{-6.09666pt}\pgfsys@stroke\pgfsys@invoke{
}{{}{{}}{}{}{{}}{{{}}{{{}}{\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@transformcm{0.84038}{0.542}{-0.542}{0.84038}{46.38455pt}{-6.09666pt}\pgfsys@invoke{
}\pgfsys@invoke{ \lxSVG@closescope }\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope}}{{}}}}\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{
}{{}{}{{ {}{}}}{ {}{}} {{}{{}}}{{}{}}{}{{}{}} {
}{{{{}}\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@transformcm{1.0}{0.0}{0.0}{1.0}{30.13283pt}{-11.62991pt}\pgfsys@invoke{
}\hbox{{\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{ }\hbox{}
}}\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}} {
{}{}{}}{}\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{ } { {}{}{}}{}{
{}{}{}}{ {}{}{}}{{{{}}{{}}{{}}{{}}}{{{{}}{ {}{}}{}{}{{}{}}}}
}{{{{}}{{}}{{}}{{}}{{}}}{{{{}}{ {}{}}{}{}{{}{}}}} }{{}{}}{{}}
{}{}{}{{{}}{{}}{{}}} {{{}}{{}}{{}}}
{}{{}}{}{{}}{}{{}}{}{}{}{}{}{}{}{{}}{}{}{}{}{{}}\pgfsys@moveto{46.77112pt}{5.84735pt}\pgfsys@curveto{35.66249pt}{13.01175pt}{24.76575pt}{13.54874pt}{13.41605pt}{7.72073pt}\pgfsys@stroke\pgfsys@invoke{
}{{}{{}}{}{}{{}}{{{}}{{{}}{\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@transformcm{-0.88957}{-0.45679}{0.45679}{-0.88957}{13.41605pt}{7.72073pt}\pgfsys@invoke{
}\pgfsys@invoke{ \lxSVG@closescope }\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope}}{{}}}}\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{
}{{}{}{{ {}{}}}{ {}{}} {{}{{}}}{{}{}}{}{{}{}} {
}{{{{}}\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@transformcm{1.0}{0.0}{0.0}{1.0}{30.13283pt}{11.62991pt}\pgfsys@invoke{
}\hbox{{\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{ }\hbox{}
}}\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope{}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope\hss}}\lxSVG@closescope\endpgfpicture}}\@add@centering\end{minipage}\\\
M&=&\\{m:m\neq mt\neq mt^{2}\neq m\\}&\begin{minipage}{113.81102pt}\centering
\leavevmode\hbox to105.95pt{\vbox
to26.78pt{\pgfpicture\makeatletter\hbox{\hskip 9.66753pt\lower-13.38934pt\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{
}\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}{{}}\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{ }{{}{}{{ {}{}}}{ {}{}}
{{}{{}}}{{}{}}{}{{}{}} { }{{{{}}\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@transformcm{1.0}{0.0}{0.0}{1.0}{-6.33452pt}{-3.0754pt}\pgfsys@invoke{
}\hbox{{\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{ }\hbox{{\phantom{t}$m$}}
}}\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
{{}}\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{ }{{}{}{{ {}{}}}{ {}{}}
{{}{{}}}{{}{}}{}{{}{}} { }{{{{}}\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@transformcm{1.0}{0.0}{0.0}{1.0}{30.79305pt}{-3.0754pt}\pgfsys@invoke{
}\hbox{{\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{ }\hbox{{$mt$}}
}}\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
{{}}\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{ }{{}{}{{ {}{}}}{ {}{}}
{{}{{}}}{{}{}}{}{{}{}} { }{{{{}}\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@transformcm{1.0}{0.0}{0.0}{1.0}{77.76265pt}{-3.97762pt}\pgfsys@invoke{
}\hbox{{\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{ }\hbox{{$mt^{2}$}}
}}\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}} {
{}{}{}}{}\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{ }{ {}{}{}}{}{ {}{}{}}
{{{{{}}{ {}{}}{}{}{{}{}}}}}{}{{{{{}}{
{}{}}{}{}{{}{}}}}}{{}}{}{}{}{}{}{{{}{}}}{}{}{}{}{{}}\pgfsys@moveto{9.86752pt}{0.0pt}\pgfsys@lineto{26.80005pt}{0.0pt}\pgfsys@stroke\pgfsys@invoke{
}{{}{{}}{}{}{{}}{{{}}{{{}}{\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@transformcm{1.0}{0.0}{0.0}{1.0}{26.80005pt}{0.0pt}\pgfsys@invoke{
}\pgfsys@invoke{ \lxSVG@closescope }\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope}}{{}}}}\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{
}{{}{}{{ {}{}}}{ {}{}} {{}{{}}}{{}{}}{}{{}{}} {
}{{{{}}\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@transformcm{1.0}{0.0}{0.0}{1.0}{18.56378pt}{0.0pt}\pgfsys@invoke{
}\hbox{{\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{ }\hbox{}
}}\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}} {
{}{}{}}{}\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{ } { {}{}{}}{}{
{}{}{}}{ {}{}{}}{{{{}}{{}}{{}}{{}}}{{{{}}{ {}{}}{}{}{{}{}}}}
}{{{{}}{{}}{{}}{{}}{{}}}{{{{}}{ {}{}}{}{}{{}{}}}} }{{}{}}{{}}
{}{}{}{{{}}{{}}{{}}} {{{}}{{}}{{}}}
{}{{}}{}{{}}{}{{}}{}{}{}{}{}{}{}{{}}{}{}{}{}{{}}\pgfsys@moveto{46.71729pt}{-5.615pt}\pgfsys@curveto{55.88306pt}{-11.27197pt}{64.74768pt}{-11.53233pt}{73.8247pt}{-6.64124pt}\pgfsys@stroke\pgfsys@invoke{
}{{}{{}}{}{}{{}}{{{}}{{{}}{\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@transformcm{0.88033}{0.47437}{-0.47437}{0.88033}{73.8247pt}{-6.64124pt}\pgfsys@invoke{
}\pgfsys@invoke{ \lxSVG@closescope }\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope}}{{}}}}\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{
}{{}{}{{ {}{}}}{ {}{}} {{}{{}}}{{}{}}{}{{}{}} {
}{{{{}}\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@transformcm{1.0}{0.0}{0.0}{1.0}{60.35489pt}{-10.05634pt}\pgfsys@invoke{
}\hbox{{\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{ }\hbox{}
}}\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}} {
{}{}{}}{}\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{ } { {}{}{}}{}{
{}{}{}}{ {}{}{}}{{{{}}{{}}{{}}{{}}}{{{{}}{ {}{}}{}{}{{}{}}}}
}{{{{}}{{}}{{}}{{}}{{}}}{{{{}}{ {}{}}{}{}{{}{}}}} }{{}{}}{{}}
{}{}{}{{{}}{{}}{{}}} {{{}}{{}}{{}}}
{}{{}}{}{{}}{}{{}}{}{}{}{}{}{}{}{{}}{}{}{}{}{{}}\pgfsys@moveto{74.22964pt}{6.42303pt}\pgfsys@curveto{64.74768pt}{11.53233pt}{55.88306pt}{11.27197pt}{47.10872pt}{5.85658pt}\pgfsys@stroke\pgfsys@invoke{
}{{}{{}}{}{}{{}}{{{}}{{{}}{\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@transformcm{-0.85097}{-0.5252}{0.5252}{-0.85097}{47.10872pt}{5.8566pt}\pgfsys@invoke{
}\pgfsys@invoke{ \lxSVG@closescope }\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope}}{{}}}}\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{
}{{}{}{{ {}{}}}{ {}{}} {{}{{}}}{{}{}}{}{{}{}} {
}{{{{}}\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@transformcm{1.0}{0.0}{0.0}{1.0}{60.35489pt}{10.05634pt}\pgfsys@invoke{
}\hbox{{\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{ }\hbox{}
}}\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope{}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope\hss}}\lxSVG@closescope\endpgfpicture}}\@add@centering\end{minipage}\end{array}$

Noting that $l\in L$ if and only if $lt\in L$, it is clear that $L$ may be
further partitioned into two sets of equal size, $I=\\{i_{1},\ldots,i_{s}\\}$
and $It=\\{i_{1}t,\ldots,i_{s}t\\}$. Thus we may write each $t$ such that
$t^{3}=t$ in the form:

$\displaystyle t=\begin{pmatrix}\cdots j\cdots&\cdots k\cdots&\cdots
i_{r}\cdots&\cdots i_{r}t\cdots&\cdots m\cdots\\\ \cdots j\cdots&\cdots
kt\cdots&\cdots i_{r}t\cdots&\cdots i_{r}\cdots&\cdots
mt\cdots\end{pmatrix}\\!,\mbox{ with }kt\in J\mbox{ and }mt\in I\cup It,$

where here $j$, $k$ and $m$ denote arbitrary elements of the sets $J$, $K$ and
$M$ respectively. We claim that the elements $e$ satisfying $e=e^{2}=te=et$
are precisely those of the form:

$\displaystyle e=\begin{pmatrix}\cdots j\cdots&\cdots k\cdots&\cdots
i_{r}\cdots&\cdots i_{r}t\cdots&\cdots m\cdots\\\ \cdots jf\cdots&\cdots
ktf\cdots&\cdots i_{r}f\cdots&\cdots i_{r}f\cdots&\cdots
mtf^{\prime}\cdots\end{pmatrix}\\!,$

where $f$ is any function $f:J\cup I\rightarrow R$ fixing a non-empty subset
$R\subseteq J$ pointwise, and $f^{\prime}:I\cup It\rightarrow R$ is defined by
$i_{r}tf^{\prime}=i_{r}f^{\prime}=i_{r}f$. (For example, given the
transformation $t=t^{3}=\begin{pmatrix}1&2&3&4&5\\\ 1&3&2&1&2\\\
\end{pmatrix}\\!,$ this description yields that $e=\begin{pmatrix}1&2&3&4&5\\\
1&1&1&1&1\\\ \end{pmatrix}$ is the unique idempotent satisfying $te=et=e$.
Indeed, if $t$ fixes exactly one element then we have no choice but to take
$R=J$, and since this is a singleton set this leaves no choice for the
function $f$.)

Now to prove the claim. If $t\in U_{n}$, then by the first paragraph of the
proof we may assume that $|J|>0$. It is then straightforward to describe the
elements $e$ which satisfy $et=te=e=e^{2}$. The condition that $e$ is
idempotent implies that $e$ fixes each element of its image. Further, if $R$
is a subset of $\\{1,\ldots,n\\}$, then there is a bijection between functions
$f:\\{1,\ldots,n\\}\setminus R\rightarrow R$ and idempotents with image equal
to $R$. Note that (as observed above) the condition $et=e$ implies that the
image of $e$ is contained in $J$. Let $R$ be a non-empty subset of $J$. We
claim that every function $f:(J\setminus R)\cup I\rightarrow R$ extends
uniquely to the whole of $\\{1,\ldots,n\\}$ to give an idempotent
$e\in\mathcal{T}_{n}$ with image $R$ satisfying the constraints $et=te=e$.

We have observed that every idempotent must fix its image. Thus, if $e$ is to
be an idempotent with image $R$ extending $f$, we have no choice on how $e$
must act on $J\cup I$. Now the condition $te=e$ forces $ke=kte$ for all
$k\in\\{1,\ldots,n\\}=J\cup K\cup I\cup It\cup M$. If $k\in K$ then $kt\in J$
and $ke=kte=(kt)f$. If $k\in It$, then $kt\in I$ and the condition $e=te$
forces $ke=kte=(kt)f$. If $k\in M$ then $kt\in I\cup It$ and hence either
$kt\in I$ and $ke=kte=(kt)f$, or $kt\in It$. In the latter case, certainly
$kt^{2}\in I$, so that $kt=kt^{3}=i_{k}t$ for $i_{k}=kt^{2}\in I$, and then
$ke=kte=i_{k}f$. Since the sets $J\cup K\cup I\cup It\cup M$ partition the
domain of $t$, this shows that there is exactly one way to extend $f$ to an
idempotent $e\in\mathcal{T}_{n}$ with image $R$ satisfying $et=te=e$.

For a fixed $t$, the number of idempotents such that $(t,e)\in P_{n}$ is
therefore found by summing the total number of functions $f:(J\setminus R)\cup
I\rightarrow R$ as $R$ ranges over non-empty subsets of $J$. That is, for
$t\in U_{n}$ with partition as given above we have that the number of
idempotents $e$ satisfying $(t,e)\in P_{n}$ is
$\sum_{r=1}^{|J|}\binom{|J|}{r}r^{|I|+|J|-r}$. ∎

We now gather together some routine but useful facts concerning the set
$P_{n}$.

######  Lemma 2.3.

Let $k\in\mathbb{N}$, $t,e\in\mathcal{T}_{n}$ and $g\in\mathcal{S}_{n}$.

  1. (1)

If $t$ is idempotent, then $t\in U_{n}$ and $(t,t)\in P_{n}$.

  2. (2)

If $(t,e)\in P_{n}$ with $t^{2}=e$, then $t=e$.

  3. (3)

We have $t\in\mathcal{S}_{n}\cap U_{n}$ if and only if $t^{2}=\mathrm{id}$.
Consequently, $t\in\mathcal{S}_{n}\cap U_{n}$ is a product of an odd number
[resp. even number] no more than $(n-1)/2$ of disjoint transpositions if
$t\in\mathcal{S}_{n}\setminus\mathcal{A}_{n}$ [resp. if
$t\in\mathcal{A}_{n}$].

  4. (4)

We have $\left(t^{g}\right)^{k}=t^{g}$ if and only if $t^{k}=t$. Additionally,
$t^{g}=\mathrm{id}$ if and only if $t=\mathrm{id}$.

  5. (5)

If $(t,e)\in P_{n}$, then $(t^{g},e^{g})\in P_{n}$.

  6. (6)

If $(t,e)\in P_{n}$ and $e=\mathrm{id}$, then $t=\mathrm{id}$.

  7. (7)

If $(t,e)\in P_{n}$, then $t^{2}$ is idempotent and $(t^{2},e)\in P_{n}$.

  8. (8)

If $(t,e)\in P_{4}$ and $g\in\mathcal{S}_{4}$, then
$(t\sigma^{g},e\sigma^{g})\in P_{4}$.

###### Proof.

  1. (1)

Let $t\in\mathcal{T}_{n}$ be an idempotent. Then clearly $t^{3}=t=t^{2}$, and
hence $(t,t)\in P_{n}$.

  2. (2)

Let $(t,e)\in P_{n}$ be such that $t^{2}=e$. Then we immediately obtain that
$t=t^{3}=tt^{2}=te=e$.

  3. (3)

If $t\in\mathcal{S}_{n}$, from $t^{3}=t$ we get that
$t^{2}=tt^{-1}=\mathrm{id}$, while $t\notin\mathcal{S}_{n}$ directly implies
that $t^{2}\neq\mathrm{id}$. The second part follows from the fact that a
permutation of order $2$ is a product of disjoint transpositions, and that
$t\in U_{n}$ must fix at least one element of $\left\\{1,\dots,n\right\\}$ by
Lemma 2.2.

  4. (4)

If $t^{k}=t$, then we have that
$(t^{g})^{k}=(g^{-1}tg)^{k}=g^{-1}t^{k}g=g^{-1}tg=t^{g}$. Conversely, if
$(t^{g})^{k}=t^{g}$, then we have $g^{-1}t^{k}g=g^{-1}tg$ which immediately
gives us that $t^{k}=t$. Finally, $g^{-1}tg=t^{g}=\mathrm{id}$ if and only if
$t=g\,\mathrm{id}\,g^{-1}=\mathrm{id}$ as required.

  5. (5)

Let $(t,e)\in P_{n}$ and $g\in\mathcal{S}_{n}$. Since $t^{3}=t$, by the
previous argument, we get that $(t^{g})^{3}=t^{g}$. Also,
$t^{g}e^{g}=g^{-1}teg=g^{-1}eg=e^{g}$ and similarly
$e^{g}t^{g}=e^{g}=(e^{g})^{2}$, which shows that $(t^{g},e^{g})\in P_{n}$.

  6. (6)

Let $(t,e)\in P_{n}$ so that $te=e$. Then, if $e=\mathrm{id}$ we get that
$t=t\,\mathrm{id}=\mathrm{id}$, as required.

  7. (7)

Let $(t,e)\in P_{n}$. Then from $t^{3}=t$ we directly obtain that
$(t^{2})^{2}=t^{3}t=t^{2}$ and thus $t^{2}$ is an idempotent and lies in
$U_{n}$ by point (1). Since $te=et=e$, we have that $t^{2}e=t(te)=te=e$, and
similarly $et^{2}=e$. Hence $t^{2}e=et^{2}=e=e^{2}$, which shows that
$(t^{2},e)\in P_{n}$.

  8. (8)

Let $(t,e)\in P_{4}$ and $g\in\mathcal{S}_{4}$. We first show that
$(t\sigma,e\sigma)\in P_{4}$ and then apply (5) (recalling the definition of
$\sigma^{g}$) to obtain the full result. Notice that if
$t,e\in\mathcal{T}_{n}\setminus\mathcal{S}_{n}$, then $t\sigma=e\sigma=c_{4}$,
while if $t=e=\mathrm{id}$, then $t\sigma=e\sigma=\mathrm{id}$, which by part
(1) shows in both cases that $(t\sigma,e\sigma)\in P_{4}$. Otherwise,
$t\in\mathcal{S}_{4}$ and $e\neq\mathrm{id}$, and then $t\sigma=p_{t}$ and
$e\sigma=c_{4}$. Since $\sigma$ is an endomorphism, we get that
$(t\sigma)^{3}=t^{3}\sigma=t\sigma=p_{t}=t\sigma$. Moreover, as
$p_{t}\in\mathcal{S}_{4}$ fixes $4$ by definition, it follows that
$p_{t}c_{4}=c_{4}p_{t}=c_{4}=c_{4}^{2}$ and we thus have
$(t\sigma,e\sigma)=(p_{t},c_{4})\in P_{4}$.∎

We now give some characteristics of the endomorphisms of $\mathcal{T}_{n}$
with rank at most three that will play an important part in the discussions to
come. Elements of the proofs of the following two results given explicitly can
be found scattered throughout the proof of Theorem 2.1 in [21]. They are only
included here for convenience, and to prepare the reader for similar arguments
to come.

We refer in Corollary 2.4 to a semilattice ordering on idempotents, which we
now explain. For any semigroup $S$ we order the idempotents $E=E(S)$ of $S$ by
$e\leq f$ if $ef=fe=e$. This is easily seen to be a partial order. If $Y$ is a
commutative subsemigroup of $E$, then we refer to $Y$ as a semilattice. The
reason for employing this terminology being that the order $\leq$ restricted
to $Y$ is a semilattice ordering in the sense that for any $e,f\in Y$ the
product $ef$ is the meet of $e$ and $f$ under the partial order.

######  Corollary 2.4.

  1. (1)

An endomorphism $\alpha\in\mathcal{E}_{n}$ has rank $1$ if and only if
$\alpha=\phi_{e,e}$ for some $e^{2}=e\in\mathcal{T}_{n}$. There is a one-to-
one correspondence between the endomorphisms of rank $1$ and the one-element
subsemigroups of $\mathcal{T}_{n}$.

  2. (2)

An endomorphism $\alpha\in\mathcal{E}_{n}$ has rank $2$ if and only if
$\alpha=\phi_{t,e}$ for some $(t,e)\in P_{n}$ with $t^{2}=t\neq e$. There is a
one-to-one correspondence between the endomorphisms of rank $2$ and the two-
element semilattices $\left\\{t,e\right\\}\subseteq\mathcal{T}_{n}$ with
$e<t$.

  3. (3)

An endomorphism $\alpha\in\mathcal{E}_{n}$ has rank $3$ if and only if
$\alpha=\phi_{t,e}$ for some $(t,e)\in P_{n}$ with $t\neq t^{2}\neq e$. There
is a one-to one correspondence between the endomorphisms of rank $3$ and the
three-element subsemigroups of $\mathcal{T}_{n}$ consisting of a two-element
subgroup $\left\\{t,t^{2}\right\\}$ having identity element $t^{2}$, together
with an adjoined zero $e$.

  4. (4)

The map $\phi_{t,\mathrm{id}}\in\mathcal{E}_{n}$ if and only if
$t=\mathrm{id}$.

  5. (5)

If $\phi_{u,f}\in\mathcal{E}_{n}$ for some $u,f\in\mathcal{T}_{n}$, then
$\phi_{u^{2},f}$, $\phi_{f,f}$ and $\phi_{{u}^{2},{u}^{2}}$ are also in
$\mathcal{E}_{n}$.

###### Proof.

Let $\alpha\in\mathcal{E}_{n}$ be an element of rank at most three. Thus
$\alpha=\phi_{t,e}$ for some $(t,e)\in P_{n}$ and it follows from the
definition of $\phi_{t,e}$ that
$\mathrm{im\,}\phi_{t,e}=\left\\{t,t^{2},e\right\\}$.

For part (1) it is clear that $\alpha$ has rank $1$ if and only if
$t=t^{2}=e$. In this case, since $e$ is idempotent it is clear that the image
of $\phi_{e,e}$ is the trivial semigroup $\\{e\\}$. Conversely, for each
idempotent $e$ there is a unique endomorphism $\phi_{e,e}$ of rank $1$ with
image $\\{e\\}$.

For part (2), we note that it follows from Lemma 2.3 part (2) that
$\phi_{t,e}$ having rank $2$ is equivalent to the condition that $t=t^{2}\neq
e$ (we have seen in Lemma 2.3 part (2) above that it is not possible to
simultaneously have $t\neq t^{2}$ and $t^{2}=e$, and since $e$ is idempotent
it is also not possible to simultaneously have $t=e$ and $t^{2}\neq t$). In
this case, the image of $\phi_{t,e}$ is $\\{e,t\\}$ and the relations
$e=e^{2}=te=et$ and $t=t^{2}$ yield that this is a two element semilattice
with $e<t$. Conversely, for each pair of distinct comparable idempotents $t,e$
with $t>e$ there is a unique endomorphism $\phi_{t,e}$ of rank $2$ with image
$\\{t,e\\}$. For part (3), it is clear that $\phi_{t,e}$ has rank $3$ if and
only if $t\neq t^{2}\neq e$. In this case $\phi_{t,e}$ has image
$\\{e,t,t^{2}\\}$ and using the fact that $t^{2}$ is idempotent and
$(t^{2},e)\in P_{n}$ by Lemma 2.3 part (7), we obtain that
$\left\\{t,t^{2},e\right\\}$ is a subsemigroup of $\mathcal{T}_{n}$, where the
idempotent $t^{2}$ acts identically on the left and right of $t$, and the
idempotent $e$ acts as a left and right zero on all three elements.
Conversely, for each two-element subgroup $\\{t,t^{2}\\}$ where $t^{2}$ is
idempotent, and each idempotent $e$ such that $\\{t,t^{2},e\\}$ is a group
with a zero $e$ adjoined, we have a unique endomorphism $\phi_{t,e}$ of rank
$3$ with image $\\{t,t^{2},e\\}$. This proves parts (1)–(3). To see that (4)
holds note that for the map $\phi_{t,\mathrm{id}}$ to be in $\mathcal{E}_{n}$,
we require $(t,\mathrm{id})\in P_{n}$, which forces $t=\mathrm{id}$ by (6) of
Lemma 2.3, and then $\phi_{t,\mathrm{id}}=\phi_{\mathrm{id},\mathrm{id}}$.
Finally, for part (5), we know that $\phi_{u,f}\in\mathcal{E}_{n}$ if and only
if $(u,f)\in P_{n}$. But then using parts (7) and (1) of Lemma 2.3 we have
that $u^{2}$ and $f$ are idempotents, and we therefore have that $u^{2},f\in
U_{n}$ as well as $(u^{2},f)\in P_{n}$. Hence $\phi_{u^{2},f}$, $\phi_{f,f}$
and $\phi_{{u}^{2},{u}^{2}}$ satisfy all conditions to be endomorphisms. ∎

The next result is surprising in that singular elements of $\mathcal{E}_{n}$
of rank no greater than 3 (so, all singular elements in the case $n\geq 5$)
are entirely determined by their images. This has significant consequences
later when we consider Green’s relations.

######  Lemma 2.5.

Let $\phi_{t,e},\phi_{u,f}\in\mathcal{E}_{n}$. Then $\phi_{t,e}=\phi_{u,f}$ if
and only if $\mathrm{im\,}\phi_{t,e}=\mathrm{im\,}\phi_{u,f}$ if and only if
$t=u$ and $e=f$. Further, if $n=4$ and $g,h\in\mathcal{S}_{4}$ then
$\sigma^{g}=\sigma^{h}$ if and only if $g=h$.

###### Proof.

Suppose that $\mathrm{im\,}\phi_{t,e}=\mathrm{im\,}\phi_{u,f}$ and consider
the description of the images corresponding to the possible ranks of these
maps as given in Corollary 2.4. Clearly if $\phi_{t,e}$ and $\phi_{u,f}$ have
rank $1$, then $t=e=u=f$. Suppose that they have rank $2$ so that
$\mathrm{im\,}\phi_{t,e}=\left\\{t,e\right\\}$ and
$\mathrm{im\,}\phi_{u,f}=\left\\{u,f\right\\}$ where $t$, $e$, $u$ and $f$ are
all idempotents. Then, since their images are two element semilattices with
$e<t$ and $f<u$, we get that $e=f$ and $t=u$. Finally, if $\phi_{t,e}$ and
$\phi_{u,f}$ have rank $3$, then
$\left\\{t,t^{2},e\right\\}=\left\\{u,u^{2},f\right\\}$ where $t$ and $u$ are
the only non idempotent elements, and $e$ and $f$ are the zeros, respectively,
which together forces $t=u$ and $e=f$. In all cases, we have shown that if
$\mathrm{im\,}\phi_{t,e}=\mathrm{im\,}\phi_{u,f}$ then $t=u$ and $e=f$, and
therefore $\phi_{t,e}=\phi_{u,f}$. This finishes the argument for the first
statement.

If $\sigma^{g}=\sigma^{h}$ in $\mathcal{E}_{4}$, then by consideration of the
images of these maps we find $4g=4h$ and $t^{g}=t^{h}$ for all
$t\in\mathcal{S}_{4}$ that fix $4$. The action on the transpositions $(1\,2)$
and $(1\,3)$ forces $g=h$. The converse direction is clear. ∎

We also describe below the explicit multiplication of elements in
$\mathcal{E}_{n}$ for $n\neq 4$ as this will be a cornerstone of many later
proofs.

######  Corollary 2.6.

Let $g,h\in\mathcal{S}_{n}$ and $(t,e),(u,f)\in P_{n}$. Then we have the
following compositions in $\mathcal{E}_{n}$:

  1. (1)

$\psi_{g}\psi_{h}=\psi_{gh}$;

  2. (2)

$\psi_{g}\phi_{t,e}=\phi_{t,e}$;

  3. (3)

$\phi_{t,e}\psi_{g}=\phi_{t^{g},e^{g}}$; and

  4. (4)

$\phi_{t,e}\phi_{u,f}=\begin{cases}\phi_{u,f}&\mbox{if
$t\in\mathcal{S}_{n}\setminus\mathcal{A}_{n}$ and }e\neq\mathrm{id},\\\
\phi_{u^{2},f}&\mbox{if $t\in\mathcal{A}_{n}$ and }e\neq\mathrm{id},\\\
\phi_{f,f}&\mbox{if $t\in\mathcal{T}_{n}\setminus\mathcal{S}_{n}$ and
}e\neq\mathrm{id},\\\ \phi_{{u}^{2},{u}^{2}}&\mbox{if
}t=e=\mathrm{id}.\end{cases}$

###### Proof.

All of the products are straightforward computations using the definition in
Theorem 2.1; we only detail that for (4). It is nonetheless worth noting that
the map on the right-hand side of product (3) is well-defined and indeed
belongs to $\mathcal{E}_{n}$ by point (5) of Lemma 2.3.

So consider $(t,e),(u,f)\in P_{n}$ so that
$\phi_{t,e},\phi_{u,f}\in\mathcal{E}_{n}$, and let $s\in\mathcal{T}_{n}$.
Then:

$s\phi_{t,e}\phi_{u,f}=\begin{cases}t\phi_{u,f}&\mbox{if
}s\in\mathcal{S}_{n}\setminus\mathcal{A}_{n},\\\ t^{2}\phi_{u,f}&\mbox{if
}s\in\mathcal{A}_{n},\\\ e\phi_{u,f}&\mbox{if
}s\in\mathcal{T}_{n}\setminus\mathcal{S}_{n}.\end{cases}$

Recall from Lemma 2.3 part (6) that if $e=\mathrm{id}$ then we must also have
$t=\mathrm{id}$. Clearly, if $t=e=\mathrm{id}$, then we have that
$t\phi_{u,f}=t^{2}\phi_{u,f}=e\phi_{u,f}=\mathrm{id}\phi_{u,f}=u^{2}$ so that
$\phi_{t,e}\phi_{u,f}=\phi_{{u}^{2},{u}^{2}}$ in this case. Thus in all
remaining cases we may assume that $e\neq\mathrm{id}$ and hence
$e\in\mathcal{T}_{n}\setminus\mathcal{S}_{n}$. If
$t\in\mathcal{T}_{n}\setminus\mathcal{S}_{n}$, then
$t^{2},e\in\mathcal{T}_{n}\setminus\mathcal{S}_{n}$ so that
$t\phi_{u,f}=t^{2}\phi_{u,f}=e\phi_{u,f}=f$. Therefore we get that
$\phi_{t,e}\phi_{u,f}=\phi_{f,f}$ whenever
$t\in\mathcal{T}_{n}\setminus\mathcal{S}_{n}$. If $t\in\mathcal{S}_{n}$, then
$t^{2}=\mathrm{id}$ by Lemma 2.3 part (3), so that
$t^{2}\phi_{u,f}=\mathrm{id}\phi_{u,f}=u^{2}$. In the case where
$t\in\mathcal{A}_{n}$, we get that

$s\phi_{t,e}\phi_{u,f}=\begin{cases}t\phi_{u,f}=u^{2}&\mbox{if
}s\in\mathcal{S}_{n}\setminus\mathcal{A}_{n},\\\
\mathrm{id}\phi_{u,f}=u^{2}&\mbox{if }s\in\mathcal{A}_{n},\\\
e\phi_{u,f}=f&\mbox{if
}s\in\mathcal{T}_{n}\setminus\mathcal{S}_{n},\end{cases}$

which shows that $\phi_{t,e}\phi_{u,f}=\phi_{u^{2},f}$. Otherwise,
$t\in\mathcal{S}_{n}\setminus\mathcal{A}_{n}$ and we obtain

$s\phi_{t,e}\phi_{u,f}=\begin{cases}t\phi_{u,f}=u&\mbox{if
}s\in\mathcal{S}_{n}\setminus\mathcal{A}_{n},\\\
\mathrm{id}\phi_{u,f}=u^{2}&\mbox{if }s\in\mathcal{A}_{n},\\\
e\phi_{u,f}=f&\mbox{if
}s\in\mathcal{T}_{n}\setminus\mathcal{S}_{n},\end{cases}$

so that $\phi_{t,e}\phi_{u,f}=\phi_{u,f}$ in that case. ∎

Notice that for $n\neq 4$ the previous result encapsulates the multiplication
table of $\mathcal{E}_{n}$. In the next section we record the remaining
products in the case $n=4$.

###  2.2. Endomorphisms of rank 7 in $\mathrm{End}(\mathcal{T}_{4})$

Let $D(4)=\\{\sigma^{g}:g\in\mathcal{S}_{4}\\}$ denote the set of all
endomorphisms of rank $7$ in $\mathcal{E}_{4}$. We recall from Theorem 2.1 the
definition of the elements $\sigma^{g}$. We have that
$\mathcal{K}=\\{\mathrm{id},(1\,2)(3\,4),(1\,3)(2\,4),(1\,4)(2\,3)\\}$ is a
normal subgroup of $\mathcal{S}_{4}$ and that each coset $\mathcal{K}s$
contains a unique element that fixes $4$, which we denote by $p_{s}$. Then

$s\sigma^{g}=\begin{cases}p_{s}^{g}&\mbox{if }s\in\mathcal{S}_{4},\\\
c_{4g}&\mbox{if }s\in\mathcal{T}_{4}\setminus\mathcal{S}_{4}.\end{cases}$

Since $\mathcal{K}s=\mathcal{K}p_{s}$ it follows from the definition that for
all $s\in\mathcal{S}_{4}$ we have $p_{s}\sigma^{g}=s\sigma^{g}=p_{s}^{g}$.
Since each of the maps $\sigma^{g}$ is an endomorphism of $\mathcal{T}_{4}$
with the property that $\mathrm{id}$ is mapped to $\mathrm{id}$ (as clearly
$\mathrm{id}=p_{\mathrm{id}}$), it is also easy to see that
$p_{rs}=(rs)\sigma=r\sigma s\sigma=p_{r}p_{s}$, and so
$(p_{s})^{-1}=p_{s^{-1}}$. Morover, we note that
$\\{p_{s}:s\in\mathcal{S}_{4}\\}=\\{h\in\mathcal{S}_{4}:4h=4\\}$ and
$h\sigma=h$ if and only if $4h=4$. These facts will be used without further
comment.

######  Lemma 2.7.

The sets $D(4)$ and $\mathcal{E}_{4}\setminus D(4)$ are subsemigroups of
$\mathcal{E}_{4}$. Moreover, we have the following compositions in
$\mathcal{E}_{4}$:

  1. (1)

$\sigma^{g}\sigma^{h}=\sigma^{p_{g}h}$;

  2. (2)

$\sigma^{g}\psi_{h}=\sigma^{gh}$;

  3. (3)

$\psi_{h}\sigma^{g}=\sigma^{p_{h}g}$;

  4. (4)

$\sigma^{g}\phi_{t,e}=\phi_{t,e}$; and

  5. (5)

$\phi_{t,e}\sigma^{g}=\phi_{t\sigma^{g},e\sigma^{g}}$.

###### Proof.

That $\mathcal{E}_{4}\setminus D(4)$ is a subsemigroup follows from Corollary
2.6. To see that $D(4)$ is a subsemigroup, consider $\sigma^{g},\sigma^{h}\in
D(4)$. Using the fact that $\sigma$ is an endomorphism, for all
$s\in\mathcal{T}_{4}$ we have:

$\displaystyle s\sigma^{g}\sigma^{h}$ $\displaystyle=$
$\displaystyle\begin{cases}(g^{-1}p_{s}g)\sigma^{h}&\mbox{if
}s\in\mathcal{S}_{4}\\\ c_{4g}\sigma^{h}&\mbox{if
}s\in\mathcal{T}_{4}\setminus\mathcal{S}_{4}\end{cases}=\begin{cases}h^{-1}(p_{g^{-1}}p_{s}p_{g})h&\mbox{if
}s\in\mathcal{S}_{4}\\\ c_{4h}&\mbox{if
}s\in\mathcal{T}_{4}\setminus\mathcal{S}_{4}\end{cases},$ $\displaystyle=$
$\displaystyle s\sigma^{p_{g}h},$

where we use the fact that both $p_{s}$ and $p_{g}$ fix $4$ and hence
$p_{s}\sigma=p_{s}$ and $c_{4h}=c_{4p_{g}h}$. This shows that (1) holds, and
hence that $D(4)$ is a subsemigroup.

For all $s\in\mathcal{T}_{4}$ it is clear that
$s\sigma^{g}\psi_{h}=h^{-1}s\sigma^{g}h=s\sigma^{gh}$, and so (2) holds.
Similarly, using the fact that $\sigma$ is an endomorphism
$s\psi_{h}\sigma^{g}=(h^{-1}sh)\sigma^{g}=g^{-1}p_{h}^{-1}s\sigma
p_{h}g=s\sigma^{p_{h}g}$ as given in (3).

For (4) note that for $s\in\mathcal{S}_{4}$ we have that $s\in\mathcal{A}_{4}$
if and only if $p_{s}\in\mathcal{A}_{4}$. It follows that $s\sigma^{g}$ lies
in $\mathcal{S}_{4}\setminus\mathcal{A}_{4}$ (respectively, $\mathcal{A}_{4}$,
$\mathcal{T}_{4}\setminus\mathcal{S}_{4}$) if and only if $s$ lies in
$\mathcal{S}_{4}\setminus\mathcal{A}_{4}$ (respectively, $\mathcal{A}_{4}$,
$\mathcal{T}_{4}\setminus\mathcal{S}_{4}$).

Finally, for all $s\in\mathcal{T}_{4}$ we have

$s\phi_{t,e}\sigma^{g}=\begin{cases}t\sigma^{g}&\mbox{ if
}s\in\mathcal{S}_{4}\setminus\mathcal{A}_{4}\\\ t^{2}\sigma^{g}&\mbox{ if
}s\in\mathcal{A}_{4}\\\ e\sigma^{g}&\mbox{ if
}s\in\mathcal{T}_{4}\setminus\mathcal{S}_{4}.\end{cases}$

Notice that since $\sigma^{g}$ is an endomorphism, we have that
$t^{2}\sigma^{g}=(t\sigma^{g})^{2}$. The result then follows from the fact
that $(t\sigma^{g},e\sigma^{g})\in P_{4}$ by (8) of Lemma 2.3. ∎

###  2.3. A decomposition via rank and type

The monoid $\mathcal{E}_{n}$ can be partitioned in a convenient way by
considering the following subsets of
$\mathcal{E}_{n}\setminus\mathcal{G}_{n}$:

$\displaystyle E_{3}(n)$ $\displaystyle=\\{\phi_{t,e}\in\mathcal{E}_{n}\colon
t\in\mathcal{S}_{n}\setminus\mathcal{A}_{n},e\neq\mathrm{id}\\},$
$\displaystyle A(n)$ $\displaystyle=\left\\{\phi_{t,e}\in\mathcal{E}_{n}\colon
t\in\mathcal{A}_{n},t\neq\mathrm{id}\neq e\right\\},$ $\displaystyle B(n)$
$\displaystyle=\left\\{\phi_{t,e}\in\mathcal{E}_{n}\colon
t\in\mathcal{T}_{n}\setminus\mathcal{S}_{n},t\neq t^{2}\neq
e\neq\mathrm{id}\right\\},$ $\displaystyle E_{2}(n)$
$\displaystyle=\\{\phi_{\mathrm{id},e}\in\mathcal{E}_{n}\colon
e\neq\mathrm{id}\\},$ $\displaystyle C(n)$
$\displaystyle=\left\\{\phi_{t,e}\in\mathcal{E}_{n}\colon
t\in\mathcal{T}_{n}\setminus\mathcal{S}_{n},t=t^{2}\neq
e\neq\mathrm{id}\right\\}\text{ and }$ $\displaystyle E_{1}(n)$
$\displaystyle=\\{\phi_{e,e}\in\mathcal{E}_{n}\\}.$

For $n=4$ we also define $E_{7}(4)=\\{\sigma^{g}:g\in\mathcal{K}\\}\subsetneq
D(4)=\\{\sigma^{g}:g\in\mathcal{S}_{4}\\}$. To reduce notation, when it is
clear from context we will suppress the dependence on $n$ and write simply
$E_{3},A,B,E_{2},C,E_{1},E_{7}$ and $D$. These subsets group together maps
that share similar properties, such as the idempotents of a given rank:

######  Lemma 2.8.

For $k=1,2,3,7$ the set $E_{k}$ consists of all the idempotents of rank $k$ in
$\mathcal{E}_{n}$. The set of idempotents of $\mathcal{E}_{n}$ is therefore

$E(\mathcal{E}_{n})=\begin{cases}\left\\{\varepsilon\right\\}\cup E_{7}\cup
E_{3}\cup E_{2}\cup E_{1}&\mbox{ if }n=4,\\\ \left\\{\varepsilon\right\\}\cup
E_{3}\cup E_{2}\cup E_{1}&\mbox{ otherwise}.\\\ \end{cases}$

###### Proof.

Clearly, the only idempotent element of $\mathcal{G}_{n}$ is $\varepsilon$. It
follows from the multiplication in Corollary 2.6 that
$\alpha=\phi_{t,e}\in\mathcal{E}_{n}$ is idempotent if and only if either (i)
$t$ is odd and $e\neq\mathrm{id}$ (in which case $\alpha\in E_{3}$), or (ii)
$t=t^{2}\neq e$ and $t\in\mathcal{S}_{n}$ (in which case $t=\mathrm{id}$ and
$\alpha\in E_{2}$) or (iii) $t=e$ from the last two cases of 4) in Corollary
2.6 (in which case $\alpha\in E_{1}$). For $n=4$ it follows from Lemma 2.7
that $\sigma^{g}$ is idempotent if and only if $p_{g}=\mathrm{id}$ or, in
other words, if and only if $g\in\mathcal{K}$. ∎

The remaining sets $A,B,C$ (together with $D\setminus E_{7}$ in the case
$n=4$) account for all the non-idempotent singular maps; the reasoning behind
this grouping shall be made apparent shortly.

We remind the reader that a non-empty subset $I$ of a semigroup $S$ is an
_ideal_ (respectively, a _left_ or _right ideal_) if $SI\cup IS\subseteq I$
(respectively, $SI\subseteq I$, or $IS\subseteq I$).

######  Lemma 2.9.

The endomorphism monoid $\mathcal{E}_{n}$ can be written as:

$\mathcal{E}_{n}=\begin{cases}\mathcal{G}_{n}\cup D\cup\left(E_{3}\cup
B\right)\cup\left(E_{2}\cup
C\right)\cup(E_{1}\setminus\\{\phi_{\mathrm{id},\mathrm{id}}\\}\cup\\{\phi_{\mathrm{id},\mathrm{id}}\\})&\mbox{
if }n=4,\\\ \mathcal{G}_{n}\cup\left(E_{3}\cup A\cup
B\right)\cup\left(E_{2}\cup
C\right)\cup(E_{1}\setminus\\{\phi_{\mathrm{id},\mathrm{id}}\\}\cup\\{\phi_{\mathrm{id},\mathrm{id}}\\})&\mbox{
otherwise,}\end{cases}$

where subsets containing endomorphisms of the same rank are bracketed
together. For $n\geq 2$ this union is disjoint and the set
$\mathcal{E}_{n}\setminus\mathcal{G}_{n}$ is an ideal of $\mathcal{E}_{n}$.

###### Proof.

That $\mathcal{E}_{n}$ is the union of the given sets follows from Theorem 2.1
and Corollary 2.4, noting that the constraints of the given sets cover all
eventualities and that the set $A$ is empty in the case of $n=4$. The fact
that the bracketed expressions are the sets of endomorphisms of the same rank
also follows from Corollary 2.4. Each automorphism of $\mathcal{E}_{n}$ has
rank $n^{n}$ and hence the union is disjoint for $n\geq 2$. ∎

As we have seen in Corollary 2.6, there is an important distinction in the
multiplicative behaviour of elements $\phi_{t,e}$ depending on where the
element $t\in\mathcal{T}_{n}$ lies and whether $e=\mathrm{id}$. Since this
will be of great importance to determine Green’s relations and the ideal
structure of $\mathcal{E}_{n}$, we define the type of an endomorphism $\theta$
relative to the type of the underlying transformations associated with
$\theta$.

######  Definition 2.10.

We say that $\theta\in\mathcal{E}_{n}$ is of:

  * •

_group type_ if $\theta\in\mathcal{G}_{n}$;

  * •

_exceptional type_ if $n=4$ and $\theta\in D(4)$;

  * •

_odd type_ if $\theta\in E_{3}(n)$;

  * •

_even type_ if $\theta\in A(n)\cup E_{2}(n)$;

  * •

_non-permutation type_ if $\theta\in B(n)\cup
C(n)\cup\left(E_{1}(n)\setminus\\{\phi_{\mathrm{id},\mathrm{id}}\\}\right)$;

  * •

_trivial type_ if $\theta=\phi_{\mathrm{id},\mathrm{id}}$.

Notice that the partition of $\mathcal{E}_{n}$ given by Lemma 2.9 is therefore
a partition into subsets of elements having the same rank _and_ type.

The notion of type is a good one since this characteristic of a map is stable
under multiplication by automorphisms.

######  Lemma 2.11.

  1. (1)

For any $\phi_{t,e}\in\mathcal{E}_{n}$ and $\psi_{g}\in\mathcal{G}_{n}$ we
have that

$\phi_{t,e},\;\;\psi_{g}\phi_{t,e}=\phi_{t,e}\;\;\mbox{ and
}\;\;\phi_{t,e}\psi_{g}=\phi_{t^{g},e^{g}}$

have the same type.

  2. (2)

For any $\sigma^{h}\in\mathcal{E}_{4}$ and any $\psi_{g}\in\mathcal{G}_{4}$ we
have that

$\sigma^{h},\;\;\psi_{g}\sigma^{h}=\sigma^{p_{g}h}\;\;\mbox{ and
}\;\;\sigma^{h}\psi_{g}=\sigma^{hg}$

have the same (exceptional) type.

  3. (3)

Let $n\neq 4$ and $\gamma\in\mathcal{E}_{n}$. For any $\phi_{t,e}\in X$ where
$X$ is one of $A$, $B$ or $C$, we have $\phi_{t,e}\gamma\in X$ if and only if
$\gamma\in\mathcal{G}_{n}$.

###### Proof.

The proof of $(1)$ and $(2)$ follow immediately from Corollary 2.6 and Lemma
2.7, together with the observation that conjugation in $\mathcal{E}_{n}$
preserves the parity of elements in $\mathcal{S}_{n}$ and the rank of all
elements.

To show that $(3)$ holds, it only remains to show the converse. Let
$\phi_{t,e}$ be in $A$, so that it is of even type and rank $3$. By Corollary
2.6 we have that for any $\phi_{u,f}$ we have that
$\phi_{t,e}\phi_{u,f}=\phi_{u^{2},f}$ has rank at most $2$, so cannot lie in
$A$. Similarly, if $\phi_{t,e}$ is in $B$ or $C$, so that it has non-
permutation type and is of rank $3$ or $2$, then
$\phi_{t,e}\phi_{u,f}=\phi_{f,f}$ has rank $1$, so cannot lie in $B$ or $C$. ∎

######  Definition 2.12.

For $\alpha\in\mathcal{E}_{n}$ we define the orbit of $\alpha$ to be
$\alpha\mathcal{G}_{n}$. It is easy to see that all elements of a given orbit
have the same rank and (by Lemma 2.11) the same type. In view of the
decomposition given in Lemma 2.9 we note that each of the sets
$\mathcal{G}_{n},E_{3},A,B,E_{2},C,E_{1}$ (and $D$ in the case $n=4$) is a
union of orbits. For $\phi_{t,e}\in X$ where $X$ is one of $A$, $B$ or $C$, it
will sometimes be convenient to write $X_{t,e}$ to denote the orbit of
$\phi_{t,e}$, in order to easily recall the rank and type of elements in this
orbit without specific mention of the corresponding properties of $t$ and $e$.

For all $n\geq 5$, being of the same type is equivalent to acting in the same
way by multiplication on the left on the singular part of $\mathcal{E}_{n}$.

######  Lemma 2.13.

Let $n\geq 5$ and let
$\alpha,\beta\in\mathcal{E}_{n}\setminus\mathcal{G}_{n}$. Then $\alpha$ and
$\beta$ are of the same type if and only if $\alpha\gamma=\beta\gamma$ for all
$\gamma\in\mathcal{E}_{n}\setminus\mathcal{G}_{n}$.

###### Proof.

Since $\alpha,\beta,\gamma\in\mathcal{E}_{n}\setminus\mathcal{G}_{n}$, only
(4) in Corollary 2.6 is relevant. It follows immediately from the description
of this multiplication that if $\alpha$ and $\beta$ are of the same type, then
$\alpha\gamma=\beta\gamma$ for all
$\gamma\in\mathcal{E}_{n}\setminus\mathcal{G}_{n}$.

Conversely, suppose $\alpha,\beta\in\mathcal{E}_{n}\setminus\mathcal{G}_{n}$
are such that $\alpha\gamma=\beta\gamma$ for all
$\gamma\in\mathcal{E}_{n}\setminus\mathcal{G}_{n}$. If
$\gamma=\phi_{u,f}\in\mathcal{E}_{n}$ where $u=(2\,3)\neq\mathrm{id}=u^{2}\neq
f=c_{1}\neq u$, then the maps $\phi_{u,f}$, $\phi_{u^{2},f}$, $\phi_{f,f}$ and
$\phi_{{u}^{2},{u}^{2}}$ are all distinct. From this, it is clear that if
$\alpha$ and $\beta$ have different types, then we fall into into a different
case for the multiplication and therefore $\alpha\gamma\neq\beta\gamma$, which
gives us the equivalence. ∎

######  Remark 2.14.

The authors of [21] gave explicit formulae to count the number of
endomorphisms of each rank. Since $\mathcal{G}_{n}$ and $\mathcal{S}_{n}$ are
isomorphic we have $\lvert\mathcal{G}_{n}\rvert=n!$. Meanwhile, it is clear
that for any $e=e^{2}\in\mathcal{E}_{n}$ we have that $(e,e)\in P_{n}$ and if
$e\neq\mathrm{id}$ then also $(\mathrm{id},e)\in P_{n}$. Consequently, $\lvert
E_{1}(n)\rvert=\lvert E_{2}(n)\rvert+1=\lvert\left\\{e\in\mathcal{T}_{n}\colon
e^{2}=e\right\\}\rvert$. We shall not attempt to give formulae for the
cardinality of the remaining sets in our partition of $\mathcal{E}_{n}$, but
it is useful to note that for $n\geq 5$ each set in this partition is non-
empty. We conclude this section by recording examples to demonstrate this
below; some of these examples will be utilised in later proofs.

######  Example 2.15.

Let $n\geq 5$ and let $t,u,p,q,e,f\in\mathcal{T}_{n}$ be defined as follows:

$\displaystyle t=\begin{pmatrix}1&2&3&4&i_{\geq 5}\\\
1&3&2&1&i\end{pmatrix},\quad p=\begin{pmatrix}1&2&3&4&i_{\geq 5}\\\
2&1&4&3&i\end{pmatrix},\quad e=\begin{pmatrix}1&2&3&4&i_{\geq 5}\\\
5&5&5&5&i\end{pmatrix},$ $\displaystyle u=\begin{pmatrix}1&2&3&4&i_{\geq 5}\\\
1&1&1&4&4\end{pmatrix},\quad q=\begin{pmatrix}1&2&3&4&i_{\geq 5}\\\
1&3&2&4&i\end{pmatrix},\quad f=\begin{pmatrix}1&2&3&4&i_{\geq 5}\\\
1&1&1&1&1\end{pmatrix}.$

It is easy to verify that $p,q\in\mathcal{S}_{n}$, $p\in\mathcal{A}_{n}$,
$q\in\mathcal{S}_{n}\setminus\mathcal{A}_{n}$ and
$t,u,e,f\in\mathcal{T}_{n}\setminus\mathcal{S}_{n}$ are such that:

  * •

$e^{2}=e\neq\mathrm{id}\neq f=f^{2}$;

  * •

$p^{2}=\mathrm{id}=q^{2}$, $pe=e=ep$ and $qf=f=fq$ so that $(p,e),(q,f)\in
P_{n}$;

  * •

$t^{3}=t$ and $te=e=et$ so that $(t,e)\in P_{n}$.

  * •

$u^{2}=u$ and $uf=f=fu$ so that $(u,f)\in P_{n}$.

It then follows that the maps
$\phi_{p,e},\phi_{q,f},\phi_{t,e},\phi_{\mathrm{id},f}$ and $\phi_{u,f}$ are
endomorphisms of $\mathcal{T}_{n}$. Moreover, it is clear from definition that
$\phi_{q,f}\in E_{3}(n)$, $\phi_{p,e}\in A(n)$, $\phi_{t,e}\in B(n)$,
$\phi_{\mathrm{id},f}\in E_{2}(n)$, $\phi_{u,f}\in C(n)$, and $\phi_{f,f}\in
E_{1}\setminus\left\\{\phi_{\mathrm{id},\mathrm{id}}\right\\}$.

######  Remark 2.16.

We will make use of the preceding results repeatedly in the following sections
where we describe the regular elements, minimal generating sets (and moreover,
a presentation), Green’s relations, ideal structure and extended Green’s
relations for $\mathcal{E}_{n}$. In order to state our results in their most
general form, it will be convenient to assume that $n\geq 5$; this, of course,
bypasses the case when $n=4$, where the structure of $\mathcal{E}_{4}$ is more
complicated due to the additional maps of rank $7$, as well as some degenerate
behaviour for $n\leq 3$ (where there are in some sense too few maps for the
general behaviour to emerge). We will return to these special cases in Section
7.

##  3\. Idempotents and regularity

Throughout this section we assume that $n\geq 5$. In particular, this means
that the set $\mathcal{E}_{n}\setminus\mathcal{G}_{n}$ of singular
endomorphisms is equal to the set of endomorphisms of rank at most three:

$\mathcal{E}_{n}\setminus\mathcal{G}_{n}=\\{\phi_{t,e}:(t,e)\in
P_{n}\\}=\left\\{\phi_{t,e}\mid t,e\in\mathcal{T}_{n}\mbox{ with
}t^{3}=t\text{ and }te=et=e^{2}=e\right\\}.$

###  3.1. The left action of the endomorphism monoid on the singular part

For $(t,e)\in P_{n}$ the maps $\phi_{t^{2},e}$, $\phi_{e,e}$ and
$\phi_{{t}^{2},{t}^{2}}$ are all closely related to the map $\phi_{t,e}$.
Indeed their images are all contained in that of $\phi_{t,e}$ and by Corollary
2.6 they are all in $\mathcal{E}_{n}\phi_{t,e}$. Lemma 2.13 allows us to
define a notation facilitating this identification.

######  Definition 3.1.

Let $\alpha\in\mathcal{E}_{n}\setminus\mathcal{G}_{n}$. Then we define
$\alpha^{+}$, $\alpha^{-}$ and $\alpha^{0}$ as:

  * •

$\alpha^{+}=\gamma\alpha$ for any
$\gamma\in\mathcal{E}_{n}\setminus\mathcal{G}_{n}$ of even type;

  * •

$\alpha^{-}=\gamma\alpha$ for any
$\gamma\in\mathcal{E}_{n}\setminus\mathcal{G}_{n}$ of non-permutation type;
and

  * •

$\alpha^{0}=\phi_{\mathrm{id},\mathrm{id}}\alpha$ (that is, $\gamma\alpha$ for
$\gamma\in\mathcal{E}_{n}\setminus\mathcal{G}_{n}$ of trivial type).

Additionally, for $X\subseteq\mathcal{E}_{n}\setminus\mathcal{G}_{n}$ and
$\dagger\in\left\\{+,-,0\right\\}$, we define $X^{\dagger}$ to be the set
$\left\\{\alpha^{\dagger}\colon\alpha\in X\right\\}$.

######  Remark 3.2.

Under this definition, we can now see that if
$\alpha\in\mathcal{E}_{n}\setminus\mathcal{G}_{n}$, then
$\gamma\alpha\in\left\\{\alpha,\alpha^{+},\alpha^{-},\alpha^{0}\right\\}$ for
any $\gamma\in\mathcal{E}_{n}$ and thus
$\mathcal{E}_{n}\alpha=\left\\{\alpha,\alpha^{+},\alpha^{-},\alpha^{0}\right\\}$.
Additionally, if we write $\alpha$ as $\phi_{t,e}$, then we have that

$\gamma\alpha=\begin{cases}\alpha=\phi_{t,e}&\mbox{if $\gamma$ has group type
or odd type,}\\\ \alpha^{+}=\phi_{t^{2},e}&\mbox{if $\gamma$ has even
type,}\\\ \alpha^{-}=\phi_{e,e}&\mbox{if $\gamma$ has non-permutation
type,}\\\ \alpha^{0}=\phi_{{t}^{2},{t}^{2}}&\mbox{if $\gamma$ has trivial
type}.\end{cases}$

We now show how each of the sets involved in the decomposition of
$\mathcal{E}_{n}$ behave under the operations mapping $\alpha$ to
$\alpha^{+}$, $\alpha^{-}$ or $\alpha^{0}$.

######  Lemma 3.3.

Let $\alpha\in\mathcal{E}_{n}\setminus\mathcal{G}_{n}$. Then

  1. (1)

$1={\rm rank}(\alpha^{0})={\rm rank}(\alpha^{-})\leq{\rm
rank}(\alpha^{+})\leq{\rm rank}(\alpha)\leq 3$;

  2. (2)

$\alpha^{+}=\alpha$ if and only if ${\rm rank}(\alpha)\leq 2$ if and only if
$\alpha\in E_{2}\cup C\cup E_{1}$;

  3. (3)

$\alpha^{-}=\alpha$ if and only if $\alpha^{0}=\alpha$ if and only if ${\rm
rank}(\alpha)=1$ if and only if $\alpha\in E_{1}$;

  4. (4)

$E_{3}^{+}\cup A^{+}\subseteq E_{2}=E_{2}^{+}$, $B^{+}\subseteq C=C^{+}$, and
$E_{1}^{+}=E_{1}$;

  5. (5)

$E_{3}^{-}\cup A^{-}\cup B^{-}\cup C^{-}\subseteq
E_{1}\setminus\left\\{\phi_{\mathrm{id},\mathrm{id}}\right\\}=E_{2}^{-}$, and
$E_{1}^{-}=E_{1}$;

  6. (6)

$B^{0}\cup C^{0}\subseteq
E_{1}\setminus\left\\{\phi_{\mathrm{id},\mathrm{id}}\right\\}=(E_{1}\setminus\left\\{\phi_{\mathrm{id},\mathrm{id}}\right\\})^{0}$,
and
$A^{0}=E_{3}^{0}=E_{2}^{0}=\left\\{\phi_{\mathrm{id},\mathrm{id}}\right\\}=\left\\{\phi_{\mathrm{id},\mathrm{id}}\right\\}^{0}$.

Consequently, we have $(\mathcal{E}_{n}\setminus\mathcal{G}_{n})^{+}=E_{2}\cup
C\cup E_{1}$. and
$(\mathcal{E}_{n}\setminus\mathcal{G}_{n})^{-}=(\mathcal{E}_{n}\setminus\mathcal{G}_{n})^{0}=E_{1}$.

###### Proof.

Let $\alpha=\phi_{t,e}\in\mathcal{E}_{n}$ for some $(t,e)\in P_{n}$.
Throughout this proof, we use the description of $\alpha^{+}$, $\alpha^{-}$
and $\alpha^{0}$ given in Remark 3.2.

Part (1) follows immediately from Remark 3.2. For part (2), suppose first that
$\alpha=\alpha^{+}$, which means that $\phi_{t,e}=\phi_{t^{2},e}$, so that
$t=t^{2}$ and ${\rm rank}(\alpha)\leq 2$. If $t\in\mathcal{S}_{n}$, this
forces $t=\mathrm{id}$, and thus $\alpha=\phi_{\mathrm{id},e}\in E_{2}$.
Otherwise, $t\in\mathcal{T}_{n}\setminus\mathcal{S}_{n}$ and either $t\neq e$,
which means that $\alpha\in C$, or $t=e$ and then $\alpha=\phi_{e,e}\in
E_{1}$. Conversely, if $\alpha\in E_{2}\cup C\cup E_{1}$, then $t=t^{2}$ from
which we have that $\alpha$ has rank at most $2$ and
$\alpha^{+}=\phi_{t^{2},e}=\phi_{t,e}=\alpha$.

For part (3), if $\alpha=\alpha^{-}$, then we have that
$\phi_{t,e}=\phi_{e,e}$ which forces $t=e$, while if $\alpha=\alpha^{0}$, we
require $\phi_{t,e}=\phi_{{t}^{2},{t}^{2}}$ which implies that $t=t^{2}=e$. In
both cases, this gives us that $\alpha\in E_{1}$, that is, has rank $1$.
Conversely, if $\alpha\in E_{1}$, then $t=t^{2}=e$ and
$\alpha^{-}=\phi_{e,e}=\alpha$ while
$\alpha^{0}=\phi_{{t}^{2},{t}^{2}}=\phi_{e,e}=\alpha$.

For part (4), notice that we have already seen that $E_{2}^{+}=E_{2}$,
$C^{+}=C$ and $E_{1}^{+}=E_{1}$. If $\alpha=\phi_{t,e}\in E_{3}\cup A$ so that
$t\in\mathcal{S}_{n}$, then $\alpha^{+}=\phi_{t^{2},e}=\phi_{\mathrm{id},e}\in
E_{2}$. On the other hand, if $\alpha=\phi_{t,e}\in B$, we have that
$t^{2}\neq e$ and then $\alpha^{+}=\phi_{t^{2},e}\in C$.

Similarly, for part (5) if $\alpha=\phi_{t,e}\in E_{3}\cup A\cup B\cup
E_{2}\cup C$ then $e\neq\mathrm{id}$ and so $\alpha^{-}=\phi_{e,e}\in
E_{1}\setminus\\{\phi_{\mathrm{id},\mathrm{id}}\\}$, whilst for each
idempotent $e\neq\mathrm{id}$ we have that
$\phi_{\mathrm{id},e}^{-}=\phi_{e,e}$ and so
$E_{2}^{-}=E_{1}\setminus\\{\phi_{\mathrm{id},\mathrm{id}}\\}$. The remaining
equality is given by part (3). Likewise, for part (6) if $\alpha=\phi_{t,e}\in
B\cup C\cup E_{1}\setminus\\{\phi_{\mathrm{id},\mathrm{id}}\\}$ then
$t^{2}\neq\mathrm{id}$ and so $\alpha^{0}=\phi_{t^{2},t^{2}}\in
E_{1}\setminus\\{\phi_{\mathrm{id},\mathrm{id}}\\}$, whilst for
$\alpha=\phi_{t,e}\in E_{3}\cup A\cup
E_{2}\cup\\{\phi_{\mathrm{id},\mathrm{id}}\\}$ we have $t^{2}=\mathrm{id}$ and
so $\alpha^{0}=\phi_{\mathrm{id},\mathrm{id}}$. ∎

The inclusions given in the previous lemma, as well as the representation of
the action of the maps $\alpha\mapsto\alpha^{x}$ for
$x\in\left\\{+,-,0\right\\}$ can be seen in Figure 5.1 alongside the depiction
of the $\mathop{\mathscr{J}}$-order of the monoid $\mathcal{E}_{n}$. The
latter will be given explicitly in Proposition 5.5.

###  3.2. Idempotents and regular elements

The set of idempotents of $\mathcal{E}_{n}$, which we denote by
$E=E(\mathcal{E}_{n})$, has very nice properties. In particular, $E$ is a
band. Before stating Proposition 3.4, we give a little semigroup terminology
and background. If we have a semilattice $Y$, then a semigroup $S$ decomposed
into disjoint subsemigroups $S_{i}$, $i\in Y$, is a semilattice $Y$ of the
subsemigroups $S_{i}$ if $S_{i}S_{j}\subseteq S_{i\wedge j}$ for all $i,j\in
I$. It is a fact (see, for example, [11, Theorem 4.4.1]) that any band is a
semilattice $Y$ of rectangular bands $D_{i}$, $i\in I$, where a band is
rectangular if it satisfies the identity $x=xyx$. A right zero (resp. left
identity) for a semigroup $S$ is an element $e$ such that $ae=e$ (resp.
$ea=a$) for all $a\in S$. A semigroup consisting entirely of right zeroes
(equivalently, entirely of left identities) is called a right-zero semigroup;
clearly any such semigroup is a band, in fact, a special kind of rectangular
band. In what follows, we use the term chain for a linearly ordered set (which
is, of course, a semilattice).

######  Proposition 3.4.

  1. (1)

Each element of $E_{3}$ is a left identity of
$\mathcal{E}_{n}\setminus\mathcal{G}_{n}$.

  2. (2)

Each element of $E_{1}$ is a right zero of
$\mathcal{E}_{n}\setminus\mathcal{G}_{n}$.

  3. (3)

The minimal ideal of $\mathcal{E}_{n}$ is $E_{1}$.

  4. (4)

The set of all singular idempotents $E_{3}\cup E_{2}\cup E_{1}$ forms a left
ideal of $\mathcal{E}_{n}$.

  5. (5)

The set of all idempotents $E=\\{\varepsilon\\}\cup E_{3}\cup E_{2}\cup E_{1}$
is a band, and forms a chain of right-zero semigroups.

###### Proof.

Throughout, we bear in mind that $\varepsilon$ is the identity of the monoid
$\mathcal{E}_{n}$.

The fact that elements of $E_{3}$ are left identities for
$\mathcal{E}_{n}\setminus\mathcal{G}_{n}$ is immediate from Corollary 2.6, as
is the fact that elements of $E_{1}$ are right zeroes for
$\mathcal{E}_{n}\setminus\mathcal{G}_{n}$. Consideration of ranks immediately
gives that $E_{1}$ is an ideal of $\mathcal{E}_{n}$. Since $E_{1}$ is a right-
zero semigroup it has no proper ideals, hence is the minimal ideal of
$\mathcal{E}_{n}$. This verifies (1)–(3).

For (4), let $\beta=\phi_{t,e}\in E_{3}\cup E_{2}\cup E_{1}$. Using Remark 3.2
and Corollary 2.6, we know that for any $\alpha\in\mathcal{E}_{n}$ we have
that

$\alpha\beta\in\\{\beta,\beta^{+},\beta^{-},\beta^{0}\\}=\\{\phi_{t,e},\phi_{t^{2},e},\phi_{e,e},\phi_{t^{2},t^{2}}\\}.$

If $\beta\in E_{3}\cup E_{2}$ then $t^{2}=\mathrm{id}$; if $\beta\in E_{1}$
then $t=t^{2}=e$. It follows that $\alpha\beta\in
E\setminus\left\\{\varepsilon\right\\}$ and hence $E_{3}\cup E_{2}\cup E_{1}$
is a left ideal. Moreover, for $\alpha,\beta\in E_{k}$ where $k=1,2,3$ it is
straightforward to check that $\alpha\beta=\beta$ and hence each of these sets
forms a right-zero semigroup and indeed $E$ is a band. The only thing
remaining to check to see that (5) holds is that $E_{2}E_{3}\subseteq E_{2}$,
and this is a now familiar calculation (also inherent in the above). ∎

We have shown that the idempotents of $\mathcal{E}_{n}$ form a left regular
band, that is, a band that satisfies the identity $xyx=yx$.

We now have all the tools necessary to describe the regular elements of
$\mathcal{E}_{n}$. We recall at this point our assumption that $n\geq 5$.

######  Proposition 3.5.

The set of all regular elements of $\mathcal{E}_{n}$ is $\mathcal{G}_{n}\cup
E(\mathcal{E}_{n})$. Furthermore, this is a proper subsemigroup of
$\mathcal{E}_{n}$. In particular, $\mathcal{E}_{n}$ is not regular.

###### Proof.

Clearly if $\alpha\in\mathcal{E}_{n}$ is an automorphism or an idempotent,
then it is a regular element. The fact that $\mathcal{G}_{n}\cup
E(\mathcal{E}_{n})$ forms a (proper) subsemigroup is immediate from Lemma 2.11
and Proposition 3.4.

Conversely, let $\alpha\in\mathcal{E}_{n}\setminus\mathcal{G}_{n}$ be a
regular element of $\mathcal{E}_{n}$ so that $\alpha\gamma\alpha=\alpha$ where
$\gamma\in\mathcal{E}_{n}$. Suppose for contradiction that $\alpha$ is not
idempotent (that is, $\alpha\in A\cup B\cup C$) then it follows from Corollary
2.6 part (2) that $\gamma\in\mathcal{E}_{n}\setminus\mathcal{G}_{n}$. Note
that $\alpha\gamma$ must be an idempotent left identity for $\alpha$ and hence
of the same rank as $\alpha$. If $\alpha\in A\cup B$, then $\alpha$ has rank
$3$; but since $\gamma\in\mathcal{E}_{n}\setminus\mathcal{G}_{n}$ and $\alpha$
has even or non-permutation type, the rank of $\alpha\gamma$ is no greater
than $2$, contradicting that $\alpha\gamma$ has the same rank as $\alpha$.
Similarly, if $\alpha\in C$, then $\alpha$ has rank $2$; but since $\alpha$
has non-permutation type, the rank of $\alpha\gamma$ is $1$. The result
follows. ∎

######  Remark 3.6.

We will see in Section 7 that the only values of $n\in\mathbb{N}$ such that
$\mathcal{E}_{n}$ is regular are $n=1,2$.

##  4\. Generators and presentations

Throughout this section we assume that $n\geq 5$. We demonstrate a minimal set
of generators for $\mathcal{E}_{n}$ and, with respect to this set of
generators, a presentation for $\mathcal{E}_{n}$. Recall that for
$\alpha\in\mathcal{E}_{n}$, the orbit of $\alpha$ is $\alpha\mathcal{G}_{n}$.
All elements of the same orbit have the same rank, and so we shall speak of
orbits of a given rank. We shall say that the orbit of $\alpha$ is essential
if $\alpha$ cannot be generated by elements of strictly greater rank.

######  Remark 4.1.

Clearly the orbit of each rank $3$ element, that is, each element in
$E_{3}\cup A\cup B$, is essential. Meanwhile, there is a unique essential
orbit of rank $1$, namely the orbit of $\phi_{\mathrm{id},\mathrm{id}}$.
Indeed, any $\phi_{e,e}$, where $e\neq\mathrm{id}$ may be decomposed as a
product $\gamma\phi_{\mathrm{id},e}$ where $\gamma\in B$ and
$\phi_{\mathrm{id},e}\in E_{2}$ each have rank greater than $1$, and so the
orbit is not essential. The orbit of $\phi_{\mathrm{id},\mathrm{id}}$ is
simply $\\{\phi_{\mathrm{id},\mathrm{id}}\\}$.

######  Proposition 4.2.

Let $\Sigma\subseteq\mathcal{E}_{n}$. Then $\Sigma$ is a generating set for
$\mathcal{E}_{n}$ if and only if $\Sigma$ contains a generating set for the
group $\mathcal{G}_{n}$ together with at least one element of each essential
orbit. The minimal size of a generating set is therefore
$3+r_{3}(n)+r_{2}(n)$, where $r_{3}(n)$ denotes the number of essential orbits
(equivalently, orbits) of rank $3$ in $\mathcal{E}_{n}$ and $r_{2}(n)$ denotes
the number of essential orbits of rank $2$ in $\mathcal{E}_{n}$.

###### Proof.

Suppose first that $\Sigma$ is a generating set. It follows immediately from
the multiplication given in Corollary 2.6 that $\Sigma$ must contain a
generating set for $\mathcal{G}_{n}$. Clearly $\mathcal{G}_{n}$ forms a single
essential orbit, and $\Sigma$ contains at least one element of this orbit. By
Remark 4.1 we have that $\\{\phi_{\mathrm{id},\mathrm{id}}\\}$ is the unique
essential orbit of rank $1$, and since it is clear from Corollary 2.6 that
$\phi_{\mathrm{id},\mathrm{id}}$ cannot be decomposed into a product of
elements of $\mathcal{E}_{n}\setminus\\{\phi_{\mathrm{id},\mathrm{id}}\\}$ it
follows that any generating set must contain $\phi_{\mathrm{id},\mathrm{id}}$.

Assume that the rank of $\alpha\in\mathcal{E}_{n}$ is $2$ or $3$, and the
orbit of $\alpha$ is essential. Since $\Sigma$ is a generating set we must
have that $\alpha=\theta_{1}\cdots\theta_{m}$ for some $m$ where
$\theta_{i}\in\Sigma$. Since $\alpha$ is singular, it is clear that at least
one of the generators $\theta_{i}$ is singular. Moreover, since elements of
$\mathcal{G}_{n}$ act as left identities on the singular elements, we may
assume without loss of generality that $\theta_{1},\ldots,\theta_{l}$ are all
singular and $\theta_{l+1},\ldots,\theta_{m}\in\mathcal{G}_{n}$. Let
$\gamma=\theta_{1}\cdots\theta_{l-1}$ so that $\gamma\theta_{l}$ is in the
orbit of $\alpha$ and in particular has the same rank as $\alpha$. We aim to
show that the generator $\theta_{l}$ is in the orbit of $\alpha$ too.

If $\alpha$ has rank $3$, then it follows from the facts that
$3=|\mathrm{im\,}\alpha|=|\mathrm{im\,}\gamma\theta_{l}|\leq|\mathrm{im\,}\theta_{l}|\leq
3$ and $\mathrm{im\,}\gamma\theta_{l}\subseteq\theta_{l}$ that
$\mathrm{im\,}\gamma\theta_{l}=\mathrm{im\,}\theta_{l}$ and by Lemma 2.5 we
have $\gamma\theta_{l}=\theta_{l}$.

Suppose now that $\alpha$ and hence $\gamma\theta_{l}$ have rank $2$. If
$\theta_{l}$ has rank $3$ then as $\gamma\theta_{l}$ has rank $2$ we must have
that $\gamma\theta_{l}=\gamma^{\prime}\theta_{l}$ for any representative
$\gamma^{\prime}$ of an essential orbit lying in $A$. But this would
contradict our assumption that the orbit of $\alpha$ is essential. Thus
$\theta_{l}$ has rank $2$ and as above we have $\gamma\theta_{l}=\theta_{l}$.

Conversely, suppose that $\Sigma$ is any set with the given properties. By
Remark 4.1 we have that $\phi_{\mathrm{id},\mathrm{id}}\in\Sigma$. It is clear
that we can generate all elements of $\mathcal{G}_{n}$ (since we have a
generating set for this finite group), and hence also all elements of the
essential orbits (by definition). Since each rank $3$ orbit is essential this
shows that we may generate all elements of rank at least $3$, which in turn
allows us to generate all elements of rank $2$ (each element in a non-
essential orbit by definition being obtained as products of elements of order
greater than $2$). Finally, for each idempotent $e\in\mathcal{T}_{n}$ with
$e\neq\mathrm{id}$ we have that $\phi_{\mathrm{id},e}$ is an endomorphism of
rank $2$, and so for all $\gamma\in B$ of rank $3$ we have that
$\gamma\phi_{\mathrm{id},e}=\phi_{e,e}$, which shows that all elements of rank
$1$ can be generated.

Since $\mathcal{G}_{n}$ is isomorphic to $\mathcal{S}_{n}$ it is clear that a
minimal generating set for $\mathcal{G}_{n}$ has two elements. Since all rank
$3$ orbits are essential, whilst
$\phi_{\mathrm{id},\mathrm{id}}\mathcal{G}_{n}=\\{\phi_{\mathrm{id},\mathrm{id}}\\}$
is the unique rank $1$ essential orbit it then follows that a minimal
generating set has $2+r_{3}(n)+r_{2}(n)+1$ elements. ∎

We now give a sketch of how one might enumerate a minimal generating set for
$\mathcal{E}_{n}$. Clearly this amounts to finding a formula for $r_{2}(n)$
and $r_{3}(n)$. Each singular element corresponds to a pair $(t,e)\in P_{n}$
and hence to a labelled coloured directed graph (one colour denoting the
action of $t$ and one of $e$), with specific properties. Hence, each orbit of
a singular element corresponds to an unlabelled coloured directed graph - and
it must have precisely the following properties:

  * •

There are $n$ unlabelled vertices.

  * •

All edges are coloured either blue (corresponding to the action of $t$ and its
conjugates) or red (corresponding to the action of $e$ and its conjugates).

  * •

There is exactly one red edge and exactly one blue edge leaving each vertex.

  * •

Looking only at the blue edges, recalling the constraint $t^{3}=t$ only, one
can split the graph into components of the following two forms:

    * –

a vertex with a loop, possibly with edges coming into it and

    * –

a two-cycle, possibly with edges coming in to the vertices.

  * •

Looking now at the red edges, recalling the constraints $te=e=et=e^{2}$, the
red edges map all vertices to a subset of the blue-loop-vertices in such a way
that:

    * –

there is a red-loop at each vertex in the subset and

    * –

all vertices of a blue component are mapped by a red edge to the same red-
loop-vertex.

Counting the total number of orbits therefore amounts to counting the number
of (non-isomorphic) unlabelled coloured directed graphs of this kind. Rank $3$
orbits correspond to the graphs containing at least one two-cycle. Rank $2$
orbits correspond to graphs where there is no two-cycle but the red and blue
edges do not completely coincide.

Having found minimal generating sets for $\mathcal{E}_{n}$, we now give a
presentation using those generators. First, we recall some details concerning
presentations for monoids: we must quotient free monoids by congruences.

Let $X$ be an alphabet and denote by $X^{*}$ the free monoid on $X$. The
elements of $X^{*}$ are words over $X$, that is, finite products of elements
of $X$, which may be referred to as letters. We allow the empty product which
we will denote by $1$. Then $X^{*}$ becomes a monoid under concatenation of
words, with $1$ being the identity. A congruence on $X^{*}$ is an equivalence
relation that is compatible with the binary operation: if $\rho$ is such a
congruence then $X^{*}/\rho:=\\{[w]:w\in X^{*}\\}$ becomes a monoid under
$[v][w]=[vw]$ with identity $[1]$. If $R\subseteq X^{*}\times X^{*}$, we
denote by $R^{\sharp}$ the congruence on $X^{*}$ generated by $R$, that is,
the smallest congruence on $X^{*}$ containing $R$. It is easy to see that
$R^{\sharp}$ is the reflexive transitive closure of the set
$\\{(xvy,xwy):x,y\in X^{*},(v,w)\in R\mbox{ or }(w,v)\in R\\}$. We say a
monoid $S$ has _monoid_ _presentation_ $\langle X:R\rangle$ if ${S\cong
X^{*}/R^{\sharp}}$ or, equivalently, if there is an epimorphism
$\theta:X^{*}\to S$ with kernel $R^{\sharp}=\ker\theta$. Here the congruence
$\ker\theta$ is defined by $\ker\theta:=\\{(v,w):v\theta=w\theta\\}$. If
$\theta$ is such an epimorphism, we say $S$ has _presentation $\langle
X:R\rangle$ with respect to $\theta$_. A relation $(w_{1},w_{2})\in R$ will
usually be displayed as an equation: $w_{1}=w_{2}$.

Now let $\Pi\cup\Sigma$ be a (minimal) generating set for $\mathcal{E}_{n}$
consisting of a generating set $\Pi$ for $\mathcal{G}_{n}$ together with a set
$\Sigma$ containing exactly one element $\phi_{t,e}$ of each remaining
essential orbit. We define

$X_{\Pi}=\\{q_{g}:\psi_{g}\in\Pi\\}\mbox{ and
}X_{\Sigma}=\\{p_{t,e}:\phi_{t,e}\in\Sigma\\}.$

We choose and fix a single element of $X_{\Sigma}$ of odd (even, non-
permutation, trivial) type and denote it by $p^{od}$ ($p^{ev},p^{np},p^{tr}$)
(supressing here the subscripts, and where
$p^{tr}=p_{\mathrm{id},\mathrm{id}}$). Note that, by definition,
$p^{od}\theta\in E_{3}$ has rank $3$. Since each rank $3$ orbit is essential,
it is clear that we may also select $p^{ev}$ and $p^{np}$ so that their images
under $\theta$ have rank $3$. With abuse of terminology, we may refer to
$p_{t,e}$ having (odd/even/non-permutation/trivial) type and rank $k$ (where
$k\in\left\\{1,2,3\right\\}$) if $\phi_{t,e}$ does. It follows from Remark 4.1
that $p^{tr}$ is the unique generator of rank $1$.

Let $X=X_{\Pi}\cup X_{\Sigma}$ and $\theta:X^{*}\rightarrow\mathcal{E}_{n}$ be
defined by

$p_{t,e}\theta=\phi_{t,e}\mbox{ and }q_{g}\theta=\psi_{g}.$

Let $R_{\Pi}$ consist of any set of relations that yield $\langle
X_{\Pi}:R_{\Pi}\rangle$ is a presentation of the symmetric group
$\mathcal{S}_{n}$. We do not concern ourselves here with the ‘best’ form of
$R_{\Pi}$, as this is a well-trodden route. We aim to describe a set of
relations $R_{\Pi\cup\Sigma}$ on $X$ that, when taken together with the
relations $R_{\Pi}$, yields a presentation for $\mathcal{E}_{n}$. In what
follows, the underlying assumptions are that $q_{g}$ varies over $X_{\Pi}$ and
$p_{t,e}$ varies over $X_{\Sigma}$. Define $F_{\Pi}(n)$ to be the smallest
number such that any element of $\mathcal{S}_{n}$ has a representation as a
word of length at most $F_{\Pi}(n)$ in the generators $X_{\Pi}$. Let
$R_{\Pi\cup\Sigma}$ consist of the following relations, where $m\leq
F_{\Pi}(n)$:

  * (R1)

$q_{g}p_{t,e}=p_{t,e}$

  * (R2)

$p_{t,e}q_{g_{1}}\ldots q_{g_{m}}=p_{t,e}$ where
$\phi_{t,e}\psi_{g_{1}}\ldots\psi_{g_{m}}=\phi_{t,e}$

  * (R3)

$p_{t_{1},e_{1}}p_{t_{2},e_{2}}q_{g_{1}}\ldots
q_{g_{m}}=p_{u_{1},f_{1}}p_{u_{2},f_{2}}$ where
$\phi_{t_{1},e_{1}}\phi_{t_{2},e_{2}}\psi_{g_{1}}\cdots\psi_{g_{m}}=\phi_{u_{1},f_{1}}\phi_{u_{2},f_{2}}$
does not belong to an essential orbit

  * (R4)

$p_{t,e}p_{u,f}=p_{t^{\prime},e^{\prime}}p_{u,f}$ where $p_{t,e}$ and
$p_{t^{\prime},e^{\prime}}$ have the same type

  * (R5)

$p^{od}p_{t,e}=p_{t,e}$

  * (R6)

$p^{ev}p_{t,e}=p_{t,e}$ where $p_{t,e}$ has rank $2$

  * (R7)

$p^{ev}p^{ev}p_{t,e}=p^{ev}p_{t,e}$

  * (R8)

$p^{np}p^{ev}p_{t,e}=p^{np}p_{t,e}$, $p^{ev}p^{np}p_{t,e}=p^{np}p_{t,e}$ and
$p^{np}p^{np}p_{t,e}=p^{np}p_{t,e}$

  * (R9)

$p^{ev}p^{tr}=p^{tr}$, $p^{np}p^{tr}=p^{tr}$ and $p^{tr}p^{tr}=p^{tr}$

  * (R10)

$p^{tr}p^{np}p_{t,e}=p^{np}p_{t,e}$ and $p^{tr}p_{u,f}=p^{tr}$ where $p_{u,f}$
has odd or even type.

We now let

$R=R_{\Pi}\cup R_{\Pi\cup\Sigma}.$

######  Theorem 4.3.

The monoid $\mathcal{E}_{n}$ has presentation $\langle X:R\rangle$ with
respect to $\theta$.

###### Proof.

The morphism $\theta$ takes $X$ to a set of generators of $\mathcal{E}_{n}$,
so is an epimorphism. Let us denote $R^{\sharp}$ by $\sim$. Corollary 2.6
gives that $\sim~{}\subseteq\ker\theta$; it remains to show the converse.

######  Lemma 4.4.

Let $w\in X^{*}$ and suppose that $w$ contains at least one letter from
$X_{\Sigma}$. Then

$w\sim p_{t,e}q_{g_{1}}\cdots q_{g_{m}}\mbox{ or }w\sim
p_{t_{1},e_{1}}p_{t_{2},e_{2}}q_{g_{1}}\cdots q_{g_{m}}$

for some $p_{t,e},p_{t_{1},e_{1}},p_{t_{2},e_{2}}\in X_{\Sigma}$ and
$q_{g_{1}}\cdots q_{g_{m}}\in X_{\Pi}$, for some $m\geq 0$.

###### Proof.

By (R1) we have that $w\,\sim\,p_{t_{1},e_{1}}\ldots
p_{t_{k},e_{k}}q_{g_{1}}\cdots q_{g_{m}}$ where $m\geq 0$. Either $k=1$, so
that the first case holds. Otherwise, using (R4) and (R5) we have that
$p_{t_{1},e_{1}}\ldots p_{t_{k},e_{k}}\,\sim\,p^{1}\ldots
p^{k-1}p_{t_{k},e_{k}}$ where $p^{i}\in\\{p^{ev},p^{np},p^{tr}\\}$ for $1\leq
i\leq k-1$. Finally, (R7)–(R8) give that the second case holds. ∎

######  Lemma 4.5.

Let $w\in X^{*}$ and suppose that $w$ contains at least one letter from
$X_{\Sigma}$. Then the orbit of $w\theta$ is essential if and only if

$w\sim p_{t,e}q_{g_{1}}\cdots q_{g_{m}}$

for some $p_{t,e}\in X_{\Sigma}$ and $q_{g_{1}}\cdots q_{g_{m}}\in X_{\Pi}$,
for some $m\geq 0$.

###### Proof.

If $w\sim p_{t,e}q_{g_{1}}\cdots q_{g_{m}}$ then it is clear the orbit of
$w\theta$ is essential. Conversely, suppose that the orbit of $w\theta$ is
essential and the second case of Lemma 4.4 holds. Then $w\sim
p_{t_{1},e_{1}}p_{t_{2},e_{2}}q_{h_{1}}\cdots q_{h_{k}}$. We proceed by
examining the rank of $w\theta$ to show that
$p_{t_{1},e_{1}}p_{t_{2},e_{2}}\,\sim\,p_{t,e}$ for some $p_{t,e}$. Note that
it follows from (R4) together with the fact that $p^{od}\theta,p^{ev}\theta$
and $p^{np}\theta$ are assumed to have rank $3$ that we may assume without
loss of generality that either $p_{t_{1},e_{1}}\theta$ has rank $3$ or else
$p_{t_{1},e_{1}}=p^{tr}$.

If the rank of $w\theta$ is $3$, then this forces $\phi_{t_{1},e_{1}}$ to be
of odd type, and $p_{t_{1},e_{1}}p_{t_{2},e_{2}}\,\sim\,p_{t_{2},e_{2}}$.

If the rank of $w\theta$ is $2$, then either $\phi_{t_{1},e_{1}}$ is of odd
type, and we proceed as above. Or, $\phi_{t_{1},e_{1}}$ is of even type and
$\phi_{t_{2},e_{2}}$ has rank $2$ or $3$. If $\phi_{t_{2},e_{2}}$ has rank
$2$, then $\phi_{t_{1},e_{1}}\phi_{t_{2},e_{2}}=\phi_{t_{2},e_{2}}$ and also
by (R4) and (R6) we have $p_{t_{1},e_{1}}p_{t_{2},e_{2}}\sim p_{t_{2},e_{2}}$.
Otherwise, $\phi_{t_{2},e_{2}}$ has rank $3$, and since by assumption
$\phi_{t_{1},e_{1}}$ has rank $3$, this contradicts the fact that $w\theta$
lies in an essential orbit.

If $w\theta$ has rank $1$ we note that, since this orbit is assumed to be
essential and by Remark 4.1 there is a unique essential orbit of rank $1$, we
must have $w\theta=\phi_{\mathrm{id},\mathrm{id}}$. Our aim then is to
demonstrate that $p_{t_{1},e_{1}}p_{t_{2},e_{2}}\sim
p^{tr}=p_{\mathrm{id},\mathrm{id}}$. We shall consider all combinations of
types for elements $p_{t_{1},e_{1}}$ and $p_{t_{2},e_{2}}$, showing that
either $p_{t_{1},e_{1}}p_{t_{2},e_{2}}\sim p^{tr}$ as required, or else
obtaining a contradiction to the fact the orbit of $w\theta$ is essential of
rank $1$ (meaning that such a product does not lie in the unique rank $1$
essential orbit in the first place). If $\phi_{t_{1},e_{1}}$ is of odd type,
then we proceed as in the previous cases. If $\phi_{t_{2},e_{2}}$ is of
trivial type, then $\phi_{t_{1},e_{1}}\phi_{t_{2},e_{2}}=\phi_{t_{2},e_{2}}$
and by (R9) $p_{t_{1},e_{1}}p_{t_{2},e_{2}}\sim p_{t_{2},e_{2}}$. We therefore
assume in what follows that $p_{t_{1},e_{1}}$ is not of odd type, and
$p_{t_{2},e_{2}}$ is not of trivial type. Notice in particular that this means
that $p_{t_{2},e_{2}}$ has rank $2$ or $3$ (since the only essential orbit of
rank $1$ is the unique orbit of trivial type) and $e_{2}$ is therefore not the
identity element (since if $e_{2}=\mathrm{id}$ we require that
$t=\mathrm{id}$, and hence the element has rank $1$). If $\phi_{t_{1},e_{1}}$
is of even type then $\phi_{t_{1},e_{1}}\phi_{t_{2},e_{2}}$ has rank $2$,
contradicting our assumption that $w\theta$ has rank $1$. If
$\phi_{t_{1},e_{1}}$ is of non-permutation type, then
$\phi_{t_{1},e_{1}}\phi_{t_{2},e_{2}}=\phi_{e_{2},e_{2}}\neq\phi_{\mathrm{id},\mathrm{id}}$,
contradicting the fact the orbit of $w\theta$ is essential. Finally we are
left with the case that $\phi_{t_{1},e_{1}}$ has trivial type. Then if
$\phi_{t_{2},e_{2}}$ has odd or even type we find
$\phi_{t_{1},e_{1}}\phi_{t_{2},e_{2}}=\phi_{t_{2}^{2},t_{2}^{2}}=\phi_{\mathrm{id},\mathrm{id}}$,
giving $p_{t_{1},e_{1}}p_{t_{2},e_{2}}\sim p_{id,id}$ by (R10), whilst if
$\phi_{t_{2},e_{2}}$ has non-permutation type we have
$\phi_{t_{1},e_{1}}\phi_{t_{2},e_{2}}=\phi_{t_{2}^{2},t_{2}^{2}}\neq\phi_{\mathrm{id},\mathrm{id}}$
contradicting that the orbit of $w\theta$ is essential. ∎

We proceed with the proof of Theorem 4.3. Let $w_{1},w_{2}\in X^{*}$ and
suppose that $w_{1}\theta=w_{2}\theta=\gamma$.

If the rank of $\gamma$ is $n^{n}$, then all letters of $w_{1}$ and $w_{2}$
lie in $X_{\Pi}$ and $w_{1}\,\sim\,w_{2}$ using the relations in R0.

Suppose now that the rank of $\gamma$ is no greater than $3$, so that each of
$w_{1},w_{2}$ has a letter from $X_{\Sigma}$.

If $w_{1}\sim p_{t,e}q_{g_{1}}\cdots q_{g_{m}}$ as in Lemma 4.4, then $\gamma$
lies in an essential orbit. Then Lemma 4.5 gives that $w_{2}\,\sim
p_{u,f}q_{h_{1}}\cdots q_{h_{k}}$ for some $k\geq 0$. Since we have chosen a
unique generator corresponding to each essential orbit, we must have that
$p_{t,e}=p_{u,f}$. It immediately follows that
$\phi_{t,e}\psi_{g_{1}}\cdots\psi_{g_{m}}=\phi_{t,e}\psi_{h_{1}}\cdots\psi_{h_{k}}$,
giving that
$\phi_{t,e}\psi_{g_{1}}\ldots\psi_{g_{m}}\psi_{h_{k}^{-1}}\ldots\psi_{h_{1}^{-1}}=\phi_{t,e}$.
In $\mathcal{G}_{n}$ we have
$\psi_{g_{1}}\ldots\psi_{g_{m}}\psi_{h_{k}^{-1}}\ldots\psi_{h_{1}^{-1}}=\psi_{d_{1}}\ldots\psi_{d_{\ell}}$
where $\ell\leq n!$, so that using R0 we have $q_{g_{1}}\ldots
q_{g_{m}}q_{h_{k}^{-1}}\ldots q_{h_{1}^{-1}}\,\sim\,q_{d_{1}}\ldots
q_{d_{\ell}}$. Now

$\begin{array}[]{rcll}w_{1}&\sim&p_{t,e}q_{g_{1}}\cdots q_{g_{m}}\\\
&\sim&p_{t,e}q_{g_{1}}\cdots q_{g_{m}}q_{h_{k}^{-1}}\ldots
q_{h_{1}^{-1}}q_{h_{1}}\ldots q_{h_{k}}\\\ &\sim&p_{t,e}q_{d_{1}}\ldots
q_{d_{\ell}}q_{h_{1}}\ldots q_{h_{k}}\\\ &\sim&p_{t,e}q_{h_{1}}\ldots
q_{h_{k}}&\mbox{ using (R2)}\\\ &\sim&w_{2},\end{array}$

as required.

The case where $\gamma$ does not lie in an essential orbit yields that
$w_{1}\sim p_{t_{1},e_{1}}p_{t_{2},e_{2}}q_{g_{1}}\cdots q_{g_{m}}$ and
$w_{2}\sim p_{u_{1},f_{1}}p_{u_{2},f_{2}}q_{h_{1}}\cdots q_{h_{k}}$, where
$\phi_{t_{1},e_{1}}\phi_{t_{2},e_{2}}$ does not lie in an essential orbit. An
argument, similar to that displayed above, this time using (R3), gives that
$w_{1}\,\sim\,w_{2}$ and finishes the proof. ∎

In Section 8 we pose some related questions concerning presentations for
$\mathcal{E}_{n}$ and other related monoids and semigroups.

##  5\. Green’s relations and ideal structure

Throughout this section we again assume that $n\geq 5$ so that the set
$\mathcal{E}_{n}\setminus\mathcal{G}_{n}$ of singular endomorphisms is equal
to the set of all endomorphisms of the form $\phi_{t,e}$ each having rank at
most three. Here we turn our attention to Green’s relations
$\mathop{\mathscr{R}}$, $\mathop{\mathscr{L}}$, $\mathop{\mathscr{D}}$,
$\mathop{\mathscr{H}}$ and $\mathop{\mathscr{J}}$. It is well known that in a
finite monoid, the $\mathop{\mathscr{R}}$-class and the
$\mathop{\mathscr{L}}$-class of the identity coincide, and are hence equal to
the $\mathop{\mathscr{H}}$-class of the identity, which is the group of
invertible elements (see for example [22, Corollary 1.5]). In the case of
$\mathcal{E}_{n}$ is is easy to see this directly, using considerations of
rank.

We first show that the $\mathop{\mathscr{L}}$-classes of $\mathcal{E}_{n}$ are
singletons except for elements of $\mathcal{G}_{n}$, which from the above form
a single $\mathop{\mathscr{L}}$-class.

######  Proposition 5.1.

Let $\alpha,\beta\in\mathcal{E}_{n}$.

  1. (1)

If $\alpha\in\mathcal{E}_{n}\setminus\mathcal{G}_{n}$ then the principal left
ideal generated by $\alpha$ is
$\mathcal{E}_{n}\alpha=\\{\alpha,\alpha^{+},\alpha^{-},\alpha^{0}\\}$.

  2. (2)

$\alpha\mathop{\mathscr{L}}\beta$ if and only if
$\mathrm{im\,}\alpha=\mathrm{im\,}\beta$ if and only if $\alpha=\beta$ or
$\alpha,\beta\in\mathcal{G}_{n}$.

###### Proof.

(1) By Example 2.15 we know that $\mathcal{E}_{n}$ contains an element of each
type, and so Remark 3.2 applies to give that the principal left ideal is
indeed $\mathcal{E}_{n}\alpha=\\{\alpha,\alpha^{+},\alpha^{-},\alpha^{0}\\}$.

(2) Clearly if $\alpha=\beta$, then $\alpha\mathop{\mathscr{L}}\beta$. On the
other hand, if $\alpha,\beta\in\mathcal{G}_{n}$, then as remarked above
$\alpha\mathop{\mathscr{L}}\beta$.

Conversely, suppose that $\alpha\mathop{\mathscr{L}}\beta$, so that
$\alpha=\gamma\beta$ and $\beta=\delta\alpha$ for some
$\gamma,\delta\in\mathcal{E}_{n}$. It follows that
$\mathrm{im\,}\alpha=\mathrm{im\,}\beta$. Clearly if this image is the whole
of $\mathcal{T}_{n}$, then $\alpha,\beta\in\mathcal{G}_{n}$. Otherwise
$\alpha,\beta\in\mathcal{E}_{n}\setminus\mathcal{G}_{n}$, so that
$\alpha=\phi_{t,e}$ and $\beta=\phi_{u,f}$ for some $(t,e),(u,f)\in P_{n}$
which gives us that $\alpha=\beta$ by Lemma 2.5. ∎

######  Remark 5.2.

Recall that if $X$ is one of $A$,$B$ or $C$, then $X$ is the union of orbits
$X_{t,e}$ where $(t,e)\in P_{n}$ is such that $\phi_{t,e}\in X$. Moreover, it
is easy to see that

$\displaystyle\left(X_{t,e}\right)^{+}$
$\displaystyle=\left\\{(\phi_{t^{g},e^{g}})^{+}\colon
g\in\mathcal{S}_{n}\right\\}=\left\\{\phi_{(t^{g})^{2},e^{g}}\colon
g\in\mathcal{S}_{n}\right\\}$
$\displaystyle=\left\\{\phi_{t^{2},e}\psi_{g}\colon
g\in\mathcal{S}_{n}\right\\}=\phi_{t^{2},e}\mathcal{G}_{n}=\phi_{t,e}^{+}\mathcal{G}_{n},$

and we simply write this set as $X_{t,e}^{+}$. Notice that Lemma 3.3 gives
$C_{t,e}^{+}\subseteq C$ whilst $A_{t,e}^{+}\not\subseteq A$ and
$B_{t,e}^{+}\not\subseteq B$.

Proposition 5.1 shows that $\mathop{\mathscr{L}}$ that is surprisingly
restrictive. However, the $\mathop{\mathscr{R}}$-classes of $\mathcal{E}_{n}$
are much larger, as given by the following.

######  Proposition 5.3.

Let $\alpha\in\mathcal{E}_{n}$. The principal right ideal of $\mathcal{E}_{n}$
generated by $\alpha$ is equal to:

$\alpha\mathcal{E}_{n}=\begin{cases}\mathcal{E}_{n}&\mbox{ if
}\alpha\in\mathcal{G}_{n},\\\ \mathcal{E}_{n}\setminus\mathcal{G}_{n}&\mbox{
if }\alpha\in E_{3},\\\ A_{t,e}\cup E_{2}\cup C\cup E_{1}&\mbox{ if
}\alpha=\phi_{t,e}\in A,\\\ E_{2}\cup C\cup E_{1}&\mbox{ if }\alpha\in
E_{2},\\\ B_{t,e}\cup E_{1}&\mbox{ if }\alpha=\phi_{t,e}\in B,\\\ C_{t,e}\cup
E_{1}&\mbox{ if }\alpha=\phi_{t,e}\in C,or\\\ E_{1}&\mbox{ if }\alpha\in
E_{1}.\end{cases}$

Consequently, $\mathcal{G}_{n}$, $E_{3}$, $E_{2}$ and $E_{1}$ each consist of
a single $\mathop{\mathscr{R}}$-class, whilst each remaining
$\mathop{\mathscr{R}}$-class is the orbit of an element in $A$, $B$ or $C$.

###### Proof.

First note that if $\alpha\in\mathcal{G}_{n}$, then
$\alpha\mathcal{E}_{n}=\mathcal{E}_{n}$ while if
$\alpha=\phi_{t,e}\in\mathcal{E}_{n}\setminus\mathcal{G}_{n}$, then by
Corollary 2.6 and Remark 3.2, we have that
$\alpha\mathcal{E}_{n}=\left\\{\phi_{t^{g},e^{g}}\colon
g\in\mathcal{G}_{n}\right\\}\cup\left\\{\gamma^{x}\colon\gamma\in\mathcal{E}_{n}\setminus\mathcal{G}_{n}\right\\}$
where $\gamma^{x}$ is one of $\gamma$, $\gamma^{+}$, $\gamma^{-}$, or
$\gamma^{0}$, depending on the type of $\alpha$. For example, if
$\alpha=\phi_{t,e}\in B$, then
$\alpha\mathcal{E}_{n}=\phi_{t,e}\mathcal{G}_{n}\cup\left\\{\gamma^{-}\colon\gamma\in\mathcal{E}_{n}\setminus\mathcal{G}_{n}\right\\}=B_{t,e}\cup\left\\{\phi_{f,f}\colon
f^{2}=f\in\mathcal{T}_{n}\right\\}=B_{t,e}\cup E_{1}$.

Similar reasoning demonstrates that the principal right ideal generated by
$\alpha$ is as stated in each of the remaining cases. The description of the
$\mathop{\mathscr{R}}$-classes is then immediate. ∎

######  Corollary 5.4.

In $\mathcal{E}_{n}$, we have that
$\mathop{\mathscr{H}}=\mathop{\mathscr{L}}\subseteq\mathop{\mathscr{D}}=\mathop{\mathscr{J}}=\mathop{\mathscr{R}}$.

###### Proof.

From Propositions 5.1 and 5.3, one can directly see that
$\mathop{\mathscr{L}}\subseteq\mathop{\mathscr{R}}$, and therefore
$\mathop{\mathscr{H}}=\mathop{\mathscr{L}}\cap\mathop{\mathscr{R}}=\mathop{\mathscr{L}}$
while
$\mathop{\mathscr{D}}=\mathop{\mathscr{L}}\circ\mathop{\mathscr{R}}=\mathop{\mathscr{L}}\vee\mathop{\mathscr{R}}=\mathop{\mathscr{R}}$.
Additionally, since $\mathcal{E}_{n}$ is finite, we have that
$\mathop{\mathscr{D}}=\mathop{\mathscr{J}}$ (see [11, Proposition II 1.4]). ∎

Corollary 5.4 determines the $\mathop{\mathscr{J}}$-relation, and hence when
two principal ideals coincide. Nevertheless, it is worthwhile recording their
form.

######  Proposition 5.5.

Let $\alpha\in\mathcal{E}_{n}$. Then the principal two-sided ideal generated
by $\alpha$ is

$\mathcal{E}_{n}\alpha\mathcal{E}_{n}=\begin{cases}\mathcal{E}_{n}&\mbox{ if
}\alpha\in\mathcal{G}_{n},\\\ \mathcal{E}_{n}\setminus\mathcal{G}_{n}&\mbox{
if }\alpha\in E_{3},\\\ A_{t,e}\cup E_{2}\cup C\cup E_{1}&\mbox{ if
}\alpha=\phi_{t,e}\in A,\\\ E_{2}\cup C\cup E_{1}&\mbox{ if }\alpha\in
E_{2},\\\ B_{t,e}\cup C_{t^{2},e}\cup E_{1}&\mbox{ if }\alpha=\phi_{t,e}\in
B,\\\ C_{t,e}\cup E_{1}&\mbox{ if }\alpha=\phi_{t,e}\in C,\\\ E_{1}&\mbox{ if
}\alpha\in E_{1}.\\\ \end{cases}$

###### Proof.

We have already given a description of the principal right ideals
$\alpha\mathcal{E}_{n}$ in Proposition 5.3. It is clear that
$\mathcal{E}_{n}\alpha\mathcal{E}_{n}=\alpha\mathcal{E}_{n}$ for all
$\alpha\in\mathcal{G}_{n}$. Suppose then that
$\alpha\in\mathcal{E}_{n}\setminus\mathcal{G}_{n}$. By Corollary 2.6 and
Remark 3.2 the description of the principal two-sided ideals
$\mathcal{E}_{n}\alpha\mathcal{E}_{n}$ can therefore be found by taking the
closure of the principal right ideal $\alpha\mathcal{E}_{n}$ under the
operations $\gamma\mapsto\gamma^{+},\gamma\mapsto\gamma^{-}$ and
$\gamma\mapsto\gamma^{0}$. By Lemma 3.3 we note that each ideal
$\alpha\mathcal{E}_{n}$ is closed under the latter two operations, and if
$\alpha\not\in B$ then it is closed under all three operations, giving
$\mathcal{E}_{n}\alpha\mathcal{E}_{n}=\alpha\mathcal{E}_{n}$. For
$\alpha=\phi_{t^{g},e^{g}}\in B_{t,e}$ we note that
$\alpha^{+}=\phi_{(t^{g})^{2},e^{g}}=\phi_{(t^{2})^{g},e^{g}}\in C_{t^{2},e}$.
∎

In our considerations of Green’s relations thus far, we have not mentioned
that the relations $\mathop{\mathscr{L}},\mathop{\mathscr{R}}$ and
$\mathop{\mathscr{J}}$ are the equivalence relations associated with pre-
orders $\leq_{\mathop{\mathscr{L}}}$, $\leq_{\mathop{\mathscr{R}}}$ and
$\leq_{\mathop{\mathscr{J}}}$, defined by inclusions of left, right and two-
sided ideals, respectively.

As an immediate consequence of the description of all the principal ideals of
$\mathcal{E}_{n}$ we can describe the $\mathop{\mathscr{J}}$-order of elements
in $\mathcal{E}_{n}$ as follows:

######  Corollary 5.6.

Let $\alpha,\beta\in\mathcal{E}_{n}$. Then
$\beta\leq_{\mathop{\mathscr{J}}}\alpha$ if and only if one of the following
holds:

  1. (1)

$\alpha\in\mathcal{G}_{n}$;

  2. (2)

$\alpha\in E_{3}$ and $\beta\in\mathcal{E}_{n}\setminus\mathcal{G}_{n}$;

  3. (3)

$\alpha=\phi_{t,e}\in A$, and $\beta\in A_{t,e}\cup E_{2}\cup C\cup E_{1}$;

  4. (4)

$\alpha\in E_{2}$ and $\beta\in E_{2}\cup C\cup E_{1}$;

  5. (5)

$\alpha=\phi_{t,e}\in B$ and $\beta\in B_{t,e}\cup C_{t^{2},e}\cup E_{1}$;

  6. (6)

$\alpha=\phi_{t,e}\in C$ and $\beta\in C_{t,e}\cup E_{1}$; or

  7. (7)

$\alpha,\beta\in E_{1}$.

Using this, we can now see the structure of the $\mathop{\mathscr{J}}$-order
of $\mathcal{E}_{n}$ as laid out in Figure 5.1, where we have added how the
maps $\alpha\mapsto\alpha^{x}$ for $x\in\left\\{+,-,0\right\\}$ act on the
different components of $\mathcal{E}_{n}$.

Figure 5.1. The $\mathop{\mathscr{J}}$-order of $\mathcal{E}_{n}$ for $n\geq
5$. Each rectangle represents a $\mathop{\mathscr{J}}$-class, whilst the ovals
represent the groupings of elements according to the sets $A,B,C$. Black lines
indicate the $\mathop{\mathscr{J}}$-order, whilst directed lines indicate the
action of the maps $\alpha\mapsto\alpha^{x}$ for $x\in\\{+,-,0\\}$.

From the description of the principal ideals of $\mathcal{E}_{n}$, we can also
give an explicit formulation for each ideal of $\mathcal{E}_{n}$. In order to
do so, we use the notation introduced in Definition 2.12. Notice in particular
that if $Y$ is a union of orbits of elements of $B$, that is,
$Y=\bigcup_{\phi_{t,e}\in
B^{\prime}}\phi_{t,e}\mathcal{G}_{n}=\bigcup_{\phi_{t,e}\in
B^{\prime}}B_{t,e}$ for some $B^{\prime}\subseteq B$, then

$\displaystyle Y^{+}$ $\displaystyle=\bigcup_{\phi_{t,e}\in
B^{\prime}}\left\\{(\phi_{t^{g},e^{g}})^{+}\colon
g\in\mathcal{S}_{n}\right\\}=\bigcup_{\phi_{t,e}\in
B^{\prime}}\left\\{\phi_{t^{2},e}\psi_{g}\colon g\in\mathcal{S}_{n}\right\\}$
$\displaystyle=\bigcup_{\phi_{t,e}\in
B^{\prime}}\phi_{t^{2},e}\mathcal{G}_{n}=\bigcup_{\phi_{t,e}\in
B^{\prime}}C_{t^{2},e}.$

Thus, $Y^{+}\subseteq C$ is again a union of orbits. Since each ideal is a
union of principal ideals, we can call upon Proposition 5.5 to describe the
ideals of $\mathcal{E}_{n}$, as follows.

######  Corollary 5.7.

Any ideal of $\mathcal{E}_{n}$ takes one of the following forms:

  1. (1)

$\mathcal{E}_{n}$ (the only ideal containing automorphisms);

  2. (2)

$\mathcal{E}_{n}\setminus\mathcal{G}_{n}$ (the only proper ideal containing
elements of odd type);

  3. (3)

$X\cup Y\cup E_{2}\cup C\cup E_{1}$ (ideals containing elements of even type,
but no elements of odd type); or

  4. (4)

$Y\cup Y^{+}\cup Z\cup E_{1}$ (ideals containing only elements of trivial or
non-permutation type),

where the sets $X$, $Y$ and $Z$ are (possibly empty) unions of orbits taken
from sets $A,B$ and $C$ respectively.

######  Remark 5.8.

We note that it follows from the multiplication given in Corollary 2.6 that
every singular element squares to an idempotent, and so
$\mathcal{E}_{n}\setminus\mathcal{G}_{n}$ satisfies the identity
$x^{4}=x^{2}$. Moreover, it is easy to see that in
$\mathcal{E}_{n}\setminus\mathcal{G}_{n}$ regular
$\mathop{\mathscr{D}}$-classes are aperiodic subsemigroups (that is, the
subgroups are trivial) and in $\mathcal{E}_{n}$ the regular
$\mathop{\mathscr{D}}$-classes are subsemigroups. Another way of saying this
is that $\mathcal{E}_{n}\setminus\mathcal{G}_{n}$ belongs to the pseudovariety
$\mathbf{DA}$ and $\mathcal{E}_{n}$ to the pseudovariety $\mathbf{DS}$ (see
[20]). Since $\mathcal{T}_{n}$ does not belong to $\mathbf{DS}$ or
$\mathbf{DA}$, this gives one way to see that $\mathcal{T}_{n}$ does not embed
in $\mathcal{E}_{n}$ or $\mathcal{E}_{n}\setminus\mathcal{G}_{n}$ (although
one can also show this more directly). Conversely, $\mathcal{E}_{n}$ does not
embed in $\mathcal{T}_{n}$: this can be seen by a quick counting argument,
since for example the number of idempotents in $\mathcal{E}_{n}$ is equal to
$1+|E_{3}|+|E_{2}|+|E_{1}|$ which exceeds the total number of idempotents
$|E_{1}|$ in $\mathcal{T}_{n}$.

##  6\. Extended Green’s relations and generalised regularity properties

We assume once more that $n\geq 5$ so that, as shown in Proposition 3.5, the
monoid $\mathcal{E}_{n}$ is not regular. In order to better understand the
structure of these endomorphism monoids, we turn to the extended Green’s
relations. We now recall their precise definitions. The original sources for
the ∗-case is [7] and for the ∼-case [5] (see also [14]).

$\displaystyle\alpha\mathop{\mathscr{R}^{*}}\beta\iff$
$\displaystyle\big{(}\gamma\alpha=\delta\alpha\Leftrightarrow\gamma\beta=\delta\beta\quad\forall\gamma,\delta\in\mathcal{E}_{n}\big{)},$
$\displaystyle\alpha\mathop{\mathscr{L}^{*}}\beta\iff$
$\displaystyle\big{(}\alpha\gamma=\alpha\delta\Leftrightarrow\beta\gamma=\beta\delta\quad\forall\gamma,\delta\in\mathcal{E}_{n}\big{)},$
$\displaystyle\alpha\mathop{\widetilde{\mathscr{R}}}\beta\iff$
$\displaystyle\big{(}\eta\alpha=\alpha\Leftrightarrow\eta\beta=\beta\quad\forall\eta=\eta^{2}\in\mathcal{E}_{n}\big{)},$
$\displaystyle\alpha\mathop{\widetilde{\mathscr{L}}}\beta\iff$
$\displaystyle\big{(}\alpha\eta=\alpha\Leftrightarrow\beta\eta=\beta\quad\forall\eta=\eta^{2}\in\mathcal{E}_{n}\big{)},$
$\displaystyle\mathop{\mathscr{H}^{*}}=\mathop{\mathscr{L}^{*}}\wedge\mathop{\mathscr{R}^{*}}=\mathop{\mathscr{L}^{*}}$
$\displaystyle\cap\mathop{\mathscr{R}^{*}},\quad\phantom{and}\quad\mathop{\widetilde{\mathscr{H}}}=\mathop{\widetilde{\mathscr{L}}}\wedge\mathop{\widetilde{\mathscr{R}}}=\mathop{\widetilde{\mathscr{L}}}\cap\mathop{\widetilde{\mathscr{R}}},$
$\displaystyle\mathop{\mathscr{D}^{*}}=\mathop{\mathscr{L}^{*}}$
$\displaystyle\vee\mathop{\mathscr{R}^{*}},\quad\phantom{and}\quad\mathop{\widetilde{\mathscr{D}}}=\mathop{\widetilde{\mathscr{L}}}\vee\mathop{\widetilde{\mathscr{R}}},$
$\displaystyle\alpha\mathop{\mathscr{J}^{*}}$ $\displaystyle\beta\iff
J^{*}(\alpha)=J^{*}(\beta),\quad\text{and}$
$\displaystyle\alpha\mathop{\widetilde{\mathscr{J}}}{}$
$\displaystyle\beta\iff\widetilde{J}(\alpha)=\widetilde{J}(\beta),$

where $J^{*}(\alpha)$ [resp. $\widetilde{J}(\alpha)$] is the smallest ideal
containing $\alpha$ that is saturated by $\mathop{\mathscr{L}^{*}}$ and
$\mathop{\mathscr{R}^{*}}$ [resp. by $\mathop{\widetilde{\mathscr{L}}}$ and
$\mathop{\widetilde{\mathscr{R}}}{}$].

Before proceeding, we make some additional remarks. These relations come with
the appropriate generalisation of the inclusions
$\mathop{\mathscr{H}}\subseteq\mathop{\mathscr{R}},\mathop{\mathscr{L}}\subseteq\mathop{\mathscr{D}}\subseteq\mathop{\mathscr{J}}$.
As for Green’s relations,
$\mathop{\mathscr{R}^{*}},\mathop{\mathscr{L}^{*}},\mathop{\mathscr{J}^{*}},\mathop{\widetilde{\mathscr{R}}},\mathop{\widetilde{\mathscr{L}}}$
and $\mathop{\widetilde{\mathscr{J}}}$ are the equivalence relations
associated with certain preorders; we do not comment further on these. It is
easily seen that
$\mathop{\mathscr{R}}\subseteq\mathop{\mathscr{R}^{*}}\subseteq\mathop{\widetilde{\mathscr{R}}}$
and
$\mathop{\mathscr{L}}\subseteq\mathop{\mathscr{L}^{*}}\subseteq\mathop{\widetilde{\mathscr{L}}}$.
For any regular semigroup $S$ we have
$\mathop{\mathscr{R}}=\mathop{\mathscr{R}^{*}}=\mathop{\widetilde{\mathscr{R}}}$
and
$\mathop{\mathscr{L}}=\mathop{\mathscr{L}^{*}}=\mathop{\widetilde{\mathscr{L}}}$.
In fact, if $a$ and $b$ are any regular elements of a semigroup $S$ and
$a\mathop{\widetilde{\mathscr{R}}}b$, then with $a=axa$ we have that
$ax=(ax)^{2}$, so that $b=axb$; together with the converse we obtain
$a\mathop{\mathscr{R}}b$. A dual statement holds for $\mathop{\mathscr{L}}$
and $\mathop{\widetilde{\mathscr{L}}}$. The converse is not true, as may be
seen by (in an extreme case) considering a cancellative monoid that is not a
group. This gives a hint at the idea that for non-regular semigroups,
decomposing them using ∗-classes or ∼-classes may be useful. It is also worth
remarking that, in general, $\mathop{\mathscr{L}^{*}}$ and
$\mathop{\mathscr{R}^{*}}$ do not commute, so that
$\mathop{\mathscr{D}^{*}}\neq\mathop{\mathscr{L}^{*}}\circ\mathop{\mathscr{R}^{*}}$;
a similar statement holds for $\mathop{\widetilde{\mathscr{L}}}$ and
$\mathop{\widetilde{\mathscr{R}}}$.

Before describing these relations on $\mathcal{E}_{n}$, notice from the above
that $\mathcal{G}_{n}$ is contained in an $\mathop{\mathscr{H}^{*}}$-class and
hence in an $\mathop{\widetilde{\mathscr{H}}}$-class.

######  Lemma 6.1.

The group $\mathcal{G}_{n}$ is an $\mathop{\mathscr{R}^{*}}$-class and an
$\mathop{\widetilde{\mathscr{R}}}$-class of $\mathcal{E}_{n}$.

###### Proof.

Since $\mathcal{G}_{n}$ lies in an $\mathop{\mathscr{R}^{*}}$-class, and that
$\mathop{\mathscr{R}^{*}}\subseteq\mathop{\widetilde{\mathscr{R}}}$, it only
remains to show that if $\beta\notin\mathcal{G}_{n}$ then $\beta$ is not
$\mathop{\widetilde{\mathscr{R}}}$-related to $\varepsilon$. But this is clear
since $\beta=\phi_{t,e}\beta$ for any odd $\phi_{t,e}$, but certainly
$\varepsilon\neq\phi_{t,e}\varepsilon$. ∎

For the description of the other $\mathop{\mathscr{R}^{*}}$-classes we can
show, using the type of maps in $\mathcal{E}_{n}\setminus\mathcal{G}_{n}$,
that it is sufficient to consider idempotents acting on the left in order to
characterise the relation $\mathop{\mathscr{R}^{*}}$ for elements in
$\mathcal{E}_{n}\setminus\mathcal{G}_{n}$.

######  Lemma 6.2.

For any $\alpha,\beta\in\mathcal{E}_{n}$,
$\alpha\mathop{\mathscr{R}^{*}}\beta$ is equivalent to

$\eta\alpha=\zeta\alpha\iff\eta\beta=\zeta\beta\quad\forall\eta,\zeta\in
E(\mathcal{E}_{n}).$

###### Proof.

Suppose first that $\alpha\mathop{\mathscr{R}^{*}}\beta$. By definition we
have that for all $\gamma,\delta\in\mathcal{E}_{n}$ we have
$\gamma\alpha=\delta\alpha$ if and only if $\gamma\beta=\delta\beta$. In
particular, this statement holds for all idempotents
$\gamma,\delta\in\mathcal{E}_{n}$. Conversely, suppose that for all
$\eta,\zeta\in E(\mathcal{E}_{n})$ we have
$\eta\alpha=\zeta\alpha\iff\eta\beta=\zeta\beta.$ If
$\alpha\in\mathcal{G}_{n}$ then it is clear that this condition is satisfied
only if $\beta\in\mathcal{G}_{n}$ (to see this, consider taking
$\eta=\varepsilon$, and $\zeta=\phi_{t,e}\in E_{3}$: their left action will
agree on the singular elements, but will differ on the automorphisms), which
by the previous result gives that $\alpha\mathop{\mathscr{R}^{*}}\beta$ in
this case. Suppose then that
$\alpha,\beta\in\mathcal{E}_{n}\setminus\mathcal{G}_{n}$, and let
$\gamma,\delta\in\mathcal{E}_{n}$ be such that $\gamma\alpha=\delta\alpha$.
Since there is an idempotent of each type, it follows from Lemma 2.13 that
$\eta\alpha=\zeta\alpha$ where $\eta$ is an idempotent of the same type as
$\gamma$ and $\zeta$ is an idempotent of the same type as $\delta$, and hence
$\gamma\beta=\eta\beta=\zeta\beta=\delta\beta$. A dual argument shows that
$\gamma\beta=\delta\beta$ implies $\gamma\alpha=\delta\alpha$, and hence
$\alpha\mathop{\mathscr{R}^{*}}\beta$. ∎

Since $\mathop{\mathscr{R}^{*}}$ and $\mathop{\widetilde{\mathscr{R}}}$ only
depend on idempotents, we start by showing when a map admits a left identity.

######  Lemma 6.3.

Let $\alpha\in\mathcal{E}_{n}$. Then $\eta\alpha=\alpha$ for
$\eta\in\mathcal{E}_{n}$ if and only if one of the following holds:

  1. (1)

$\alpha$ has rank $n^{n}$ and $\eta=\varepsilon$ (equivalently,
$\alpha\in\mathcal{G}_{n}$, and $\eta=\varepsilon$);

  2. (2)

$\alpha$ has rank $3$ and $\eta$ has group or odd type (equivalently,
$\alpha\in E_{3}\cup A\cup B$ and $\eta\in\mathcal{G}_{n}\cup E_{3}$);

  3. (3)

$\alpha$ has rank $2$ and $\eta$ has group, odd, or even type (equivalently,
$\alpha\in E_{2}\cup C$ and $\eta\in\mathcal{G}_{n}\cup E_{3}\cup A\cup
E_{2}$); or

  4. (4)

$\alpha$ has rank $1$ and $\eta\in\mathcal{E}_{n}$ (equivalently, $\alpha\in
E_{1}$ and $\eta\in\mathcal{E}_{n}$) .

In particular, if $\eta$ is an idempotent then, $\eta\alpha=\alpha$ if and
only if $\alpha\leq_{\mathop{\mathscr{J}}}\eta$.

###### Proof.

It is clear that $\varepsilon$ is the only left identity for
$\alpha\in\mathcal{G}_{n}$. Assume now that
$\alpha\in\mathcal{E}_{n}\setminus\mathcal{G}_{n}$. By consideration of rank,
we can immediately determine the idempotent left identities. The result
follows from Corollary 5.6 and Lemma 6.2. ∎

Furthermore, two idempotents $\eta$ and $\zeta$ satisfying
$\eta\alpha=\zeta\alpha$ for a given map $\alpha\in\mathcal{E}_{n}$ must lie
above $\alpha$ in the $\mathop{\mathscr{J}}$ order, or have the same type.
This is formally given by the following.

######  Lemma 6.4.

Let $\alpha=\phi_{t,e}\in\mathcal{E}_{n}\setminus\mathcal{G}_{n}$. Then
$\eta\alpha=\zeta\alpha$ for some $\eta,\zeta\in E(\mathcal{E}_{n})$ if and
only if one of the following happens:

  * •

$\alpha\leq_{\mathop{\mathscr{J}}}\eta$ and
$\alpha\leq_{\mathop{\mathscr{J}}}\zeta$; or

  * •

$\eta$ and $\zeta$ have the same type.

###### Proof.

If $\eta,\zeta\in E(\mathcal{E}_{n})$ are such that
$\alpha\leq_{\mathop{\mathscr{J}}}\eta$ and
$\alpha\leq_{\mathop{\mathscr{J}}}\zeta$, then $\eta\alpha=\alpha$ and
$\zeta\alpha=\alpha$ by Lemma 6.3, which shows that $\eta\alpha=\zeta\alpha$.
Similarly, if $\eta$ and $\zeta$ have the same type, then
$\eta\alpha=\zeta\alpha$ by Lemma 2.13 and the fact that $\varepsilon$ is the
only idempotent of group type.

For the converse, suppose that that $\eta\alpha=\zeta\alpha$. If
$\alpha\leq_{\mathop{\mathscr{J}}}\eta$, then $\eta\alpha=\alpha$ by Lemma
6.3. Therefore $\zeta\alpha=\eta\alpha=\alpha$ so that
$\alpha\leq_{\mathop{\mathscr{J}}}\zeta$, which corresponds to the first case.
Thus, we can now assume that $\alpha\nleq_{\mathop{\mathscr{J}}}\eta$ and
$\alpha\nleq_{\mathop{\mathscr{J}}}\zeta$. In particular, this means that
$\alpha\notin E_{1}$ and so $t\neq e$ and that $\eta,\zeta\in E_{2}\cup
E_{1}$. Assume that $\eta$ is of even type and $\zeta$ is of trivial or non-
permutation type, that is, $\eta\in E_{2}$ and $\zeta\in E_{1}$. Then
$\eta\alpha=\zeta\alpha$ gives

$\phi_{t^{2},e}=\begin{cases}\phi_{{t}^{2},{t}^{2}}&\text{if
}\zeta=\phi_{\mathrm{id},\mathrm{id}},\\\
\phi_{e,e}&\text{otherwise,}\end{cases}$

which shows in either case that $t^{2}=e$, so that $t=e$ by Lemma 2.3 part
(2), a contradiction. A similar contradiction arises when considering $\eta$
of trivial type and $\zeta$ of non-permutation type. Therefore $\eta$ and
$\zeta$ must have the same type. ∎

We can now easily determine the $\mathop{\mathscr{R}^{*}}$ and
$\mathop{\widetilde{\mathscr{R}}}$ relations.

######  Proposition 6.5.

Let $\alpha,\beta\in\mathcal{E}_{n}$. Then the following conditions are
equivalent:

  1. (1)

$\alpha\mathop{\mathscr{R}^{*}}\beta$;

  2. (2)

$\alpha\mathop{\widetilde{\mathscr{R}}}\beta$;

  3. (3)

$\alpha$ and $\beta$ are $\mathop{\mathscr{R}}$-below the same idempotents;

  4. (4)

$\alpha$ and $\beta$ are $\mathop{\mathscr{J}}$-below the same idempotents;

  5. (5)

$\alpha$ and $\beta$ have the same rank.

Consequently, $\mathop{\widetilde{\mathscr{R}}}=\mathop{\mathscr{R}^{*}}$ is a
left congruence and the $\mathop{\mathscr{R}^{*}}$-classes of
$\mathcal{E}_{n}$ are $\mathcal{G}_{n}$, $E_{3}\cup A\cup B$, $E_{2}\cup C$
and $E_{1}$.

###### Proof.

If (1) holds, then so also does (2), since
$\mathop{\mathscr{R}^{*}}\subseteq\mathop{\widetilde{\mathscr{R}}}$. In any
semigroup $S$, if $ea=a$ for some $e,a\in S$, then clearly
$a\leq_{\mathop{\mathscr{R}}}e$. On the other hand, if
$a\leq_{\mathop{\mathscr{R}}}f$ for some idempotent $f\in S$, then from $a=fb$
for $b\in S^{1}$ we obtain $fa=ffb=fb=a$. Applying this to $\mathcal{E}_{n}$
gives that (2) and (3) are equivalent. Examination of Lemma 6.3 now yields
that (3),(4) and (5) are equivalent.

It remains to show that if $\alpha\mathop{\widetilde{\mathscr{R}}}\beta$ then
$\alpha\mathop{\mathscr{R}^{*}}\beta$. Suppose therefore that
$\alpha\mathop{\widetilde{\mathscr{R}}}\beta$ and $\eta\alpha=\zeta\alpha$
where $\eta,\zeta$ are idempotent. Using Lemma 6.4, either
$\alpha\leq_{\mathop{\mathscr{J}}}\eta$ and
$\alpha\leq_{\mathop{\mathscr{J}}}\zeta$ so that the same is true for $\beta$
and $\eta\beta=\beta=\zeta\beta$; or $\eta$ and $\zeta$ have the same type, in
which case certainly $\eta\beta=\zeta\beta$ by Lemma 2.13. Lemma 6.2 finishes
the proof that $\alpha\mathop{\mathscr{R}^{*}}\beta$, that is, (1) holds. That
$\mathop{\widetilde{\mathscr{R}}}$ is a left congruence then follows from the
fact that in any semigroup $S$ the relation $\mathop{\mathscr{R}^{*}}$ is a
left congruence. By point (5) the congruence classes are as given. ∎

We now turn our attention toward the relations $\mathop{\mathscr{L}^{*}}$ and
$\mathop{\widetilde{\mathscr{L}}}$.

######  Proposition 6.6.

The $\mathop{\widetilde{\mathscr{L}}}$-classes of $\mathcal{E}_{n}$ are
$\mathcal{E}_{n}\setminus(E_{3}\cup E_{2}\cup E_{1})$ and all the singletons
$\left\\{\eta\right\\}$ where $\eta=\eta^{2}\neq\varepsilon$.

###### Proof.

In order to show that $\alpha\mathop{\widetilde{\mathscr{L}}}\beta$ for some
$\alpha,\beta\in\mathcal{E}_{n}$, we need to show that they have the same
idempotents as right identities.

If $\alpha\in\mathcal{G}_{n}$ then clearly $\alpha\eta=\alpha$ if and only if
$\eta=\varepsilon$.

If $\alpha\in A$ and $\eta=\phi_{u,f}\in E(\mathcal{E}_{n})$, then by Lemma
3.3 we have that $\alpha\eta=\eta^{+}\neq\alpha$, since $\eta^{+}$ has rank at
most $2$. Thus the only idempotent right identity for $\alpha$ is
$\varepsilon$. A similar argument shows that $\varepsilon$ is the only
idempotent right identity for any element of $B\cup C$.

Turning our attention to the idempotents, we have remarked at the start of
this section that idempotents are $\mathop{\widetilde{\mathscr{L}}}$-related
if and only if they are $\mathop{\mathscr{L}}$-related, and hence by
Proposition 5.1 if and only if they are equal. Since any idempotent is a right
identity for itself, the result follows. ∎

######  Remark 6.7.

Unlike the situation for $\mathop{\mathscr{R}^{*}}$ and
$\mathop{\widetilde{\mathscr{R}}}$, we find that $\mathop{\mathscr{L}^{*}}$ is
a strictly smaller relation than $\mathop{\widetilde{\mathscr{L}}}$. Indeed,
in general, the relation $\mathop{\mathscr{L}^{*}}$ on a semigroup $S$ is
well-known to be a right congruence. However, it is easy to see that
$\mathop{\widetilde{\mathscr{L}}}$ is _not_ a right congruence. Indeed, taking
$\alpha\in A$, $\beta\in B$ and $\phi_{t,e}\in E_{3}$ we find that
$\alpha\mathop{\widetilde{\mathscr{L}}}\beta$ whilst
$\alpha\phi_{t,e}=\phi_{\mathrm{id},\mathrm{id}}$ and
$\beta\phi_{t,e}=\phi_{e,e}$ are distinct idempotents, and hence not
$\mathop{\widetilde{\mathscr{L}}}$-related.

In what follows, for each $(t,e)\in P_{n}$ we write
$\mathrm{Fix}(t,e)=\left\\{g\in\mathcal{S}_{n}\colon t^{g}=t\text{ and
}e^{g}=e\right\\}$. Notice in particular that
$\mathrm{Fix}(\mathrm{id},e)=\mathrm{Fix}(e,e)$ for all $e^{2}=e$ and
$\mathrm{Fix}(\mathrm{id},\mathrm{id})=\mathcal{G}_{n}$. The next lemma is
immediate.

######  Lemma 6.8.

For any $\phi_{t,e}\in\mathcal{E}_{n}\setminus\mathcal{G}_{n}$ and
$\psi_{g}\in\mathcal{G}_{n}$ we have that $\phi_{t,e}\psi_{g}=\phi_{t,e}$ if
and only if $g\in\mathrm{Fix}(t,e)$.

We can now give the description of $\mathop{\mathscr{L}^{*}}$.

######  Proposition 6.9.

Let $\alpha,\beta\in\mathcal{E}_{n}$. Then
$\alpha\mathop{\mathscr{L}^{*}}\beta$ if and only if one of the following
occurs:

  * •

$\alpha,\beta\in\mathcal{G}_{n}$;

  * •

$\alpha,\beta\in E_{3}\cup E_{2}\cup E_{1}$ and $\alpha=\beta$; or

  * •

$\alpha,\beta\in A\cup B\cup C$ are such that $\alpha=\phi_{t,e}$,
$\beta=\phi_{u,f}$ have the same type and
$\mathrm{Fix}(t,e)=\mathrm{Fix}(u,f)$.

###### Proof.

Since
$\mathop{\mathscr{L}}\subseteq\mathop{\mathscr{L}^{*}}\subseteq\mathop{\widetilde{\mathscr{L}}}$,
we have that all elements of $\mathcal{G}_{n}$ are
$\mathop{\mathscr{L}^{*}}$-related, and that idempotents of $\mathcal{E}_{n}$
distinct from $\varepsilon$ form their own
$\mathop{\widetilde{\mathscr{L}}}$-class by Proposition 6.6 and thus they also
form their own $\mathop{\mathscr{L}^{*}}$-class. Therefore, it only remains to
show that elements of $\mathcal{G}_{n}$ cannot be
$\mathop{\mathscr{L}^{*}}$-related to non-regular elements (that is, elements
of $A\cup B\cup C$) and that two non-regular elements are
$\mathop{\mathscr{L}^{*}}$-related if and only if they have the same type and
are fixed by the same automorphisms of $\mathcal{G}_{n}$.

To see first that no elements of $\mathcal{G}_{n}$ can be
$\mathop{\mathscr{L}^{*}}$-related to elements of $A\cup B\cup C$, consider
$\alpha\in\mathcal{G}_{n}$ and $\beta\in A\cup B\cup C$, and let
$t=(1\,2),\,e=c_{3}\in\mathcal{T}_{n}$. Since $t^{2}=\mathrm{id}$ and
$(t,e)\in P_{n}$ we have
$\phi_{t,e},\phi_{\mathrm{id},e},\phi_{e,e}\in\mathcal{E}_{n}$. Clearly
$\alpha\phi_{t,e},\alpha\phi_{\mathrm{id},e}$ and $\alpha\phi_{e,e}$ are all
distinct. If $\beta\in A$, then we have that
$\beta\phi_{t,e}=\phi_{\mathrm{id},e}=\beta\phi_{\mathrm{id},e}$, while if
$\beta\in B\cup C$ we have
$\beta\phi_{t,e}=\phi_{e,e}=\beta\phi_{\mathrm{id},e}$. Therefore elements of
$\mathcal{G}_{n}$ cannot be $\mathop{\mathscr{L}^{*}}$-related to elements of
$A\cup B\cup C$.

From now on, we assume that $\alpha,\beta$ are non-regular (i.e. contained in
$A\cup B\cup C$), and that $\alpha=\phi_{v,k}$ and $\beta=\phi_{u,f}$ for some
$(v,k),(u,f)\in P_{n}$.

Suppose that $\alpha\mathop{\mathscr{L}^{*}}\beta$ and consider the maps
$\phi_{t,e}$, $\phi_{\mathrm{id},e}$ and $\phi_{e,e}$ in $\mathcal{E}_{n}$ as
above. To see that $\alpha$ and $\beta$ must have the same type, notice that
if $\alpha\in A$ and $\beta\in B\cup C$, then
$\alpha\phi_{t,e}=\phi_{\mathrm{id},e}\neq\phi_{e,e}=\alpha\phi_{e,e}$ while
$\beta\phi_{t,e}=\phi_{e,e}=\beta\phi_{e,e}$ which contradicts the fact that
$\alpha\mathop{\mathscr{L}^{*}}\beta$. Thus either $\alpha,\beta\in A$, or
$\alpha,\beta\in B\cup C$ which shows that $\mathop{\mathscr{L}^{*}}$-related
maps must be of the same type. Lemma 6.8 gives that
$\mathrm{Fix}(v,k)=\mathrm{Fix}(u,f)$.

Conversely, assume that $\alpha$ and $\beta$ have the same type and that
$\mathrm{Fix}(v,k)=\mathrm{Fix}(u,f)$. By Lemma 2.13 we have that
$\alpha\eta=\beta\eta$ for all
$\eta\in\mathcal{E}_{n}\setminus\mathcal{G}_{n}$. Suppose now that
$\psi_{g},\psi_{h}$ in $\mathcal{G}_{n}$. If $\alpha\psi_{g}=\alpha\psi_{h}$,
then $\alpha\psi_{gh^{-1}}=\alpha$. It follows that
$gh^{-1}\in\mathrm{Fix}(v,k)=\mathrm{Fix}(u,f)$ and so
$\beta\psi_{g}=\beta\psi_{h}$. Finally, it is easy to see that if $\alpha\in
A\cup B\cup C$, $\gamma\in\mathcal{G}_{n}$ and
$\delta\in\mathcal{E}_{n}\setminus\mathcal{G}_{n}$, then as the rank of
$\alpha\gamma$ is the same as the rank of $\alpha$, but the rank of
$\alpha\delta$ is strictly less than the rank of $\alpha$, we cannot have that
$\alpha\gamma=\alpha\delta$. Using the symmetry in the arguments used above
concludes the proof. ∎

######  Definition 6.10.

A semigroup $S$ is left [right] abundant if every
$\mathop{\mathscr{R}^{*}}$-class [resp. $\mathop{\mathscr{L}^{*}}$-class]
contains an idempotent, while it is left [right] Fountain if every
$\mathop{\widetilde{\mathscr{R}}}$-class [resp.
$\mathop{\widetilde{\mathscr{L}}}$-class] contains an idempotent.

######  Proposition 6.11.

For $n\geq 5$ the semigroup $\mathcal{E}_{n}$ is left abundant (and hence left
Fountain), right Fountain but not right abundant.

###### Proof.

The result follows from Propositions 6.5, 6.6 and 6.9. ∎

######  Proposition 6.12.

The $\mathop{\mathscr{D}^{*}}$-classes of $\mathcal{E}_{n}$ are
$\mathcal{G}_{n}$, $E_{1}$ and $\mathcal{E}_{n}\setminus(\mathcal{G}_{n}\cup
E_{1})$ and further, $\mathop{\mathscr{D}^{*}}=\mathop{\mathscr{J}^{*}}$.

###### Proof.

By Propositions 6.5 and 6.9 we know that the elements of $\mathcal{G}_{n}$
form a single $\mathop{\mathscr{R}^{*}}$-class and a single
$\mathop{\mathscr{L}^{*}}$-class. Thus it follows that $\mathcal{G}_{n}$ is
also a $\mathop{\mathscr{D}^{*}}$-class.

Let $\alpha\in E_{1}$ and supose that
$\alpha\mathop{\mathscr{L}^{*}}\circ\mathop{\mathscr{R}^{*}}\delta$ for some
$\delta\in\mathcal{E}_{n}\setminus\mathcal{G}_{n}$. Then there exists
$\eta\in\mathcal{E}_{n}\setminus\mathcal{G}_{n}$ such that
$\alpha\mathop{\mathscr{L}^{*}}\eta\mathop{\mathscr{R}^{*}}\delta$. By
Proposition 6.9 we find that $\eta=\alpha\in E_{1}$, and by Proposition 6.5 we
see that $\delta\in E_{1}$. It follows from this argument together with the
fact that $E_{1}$ is an $\mathop{\mathscr{R}^{*}}$-class that $E_{1}$ is also
a $\mathop{\mathscr{D}^{*}}$-class.

Suppose then that $\alpha\in\mathcal{E}_{n}\setminus(\mathcal{G}_{n}\cup
E_{1})$ and $\alpha\mathop{\mathscr{D}^{*}}\delta$. It follows from the above
that $\delta\in\mathcal{E}_{n}\setminus(\mathcal{G}_{n}\cup E_{1})$. We aim to
show that if $\alpha,\delta\in\mathcal{E}_{n}\setminus(\mathcal{G}_{n}\cup
E_{1})$ then $\alpha\mathop{\mathscr{D}^{*}}\delta$.

Notice that by our partition of $\mathcal{E}_{n}$ we have that
$\mathcal{E}_{n}\setminus(\mathcal{G}_{n}\cup E_{1})=(E_{3}\cup A\cup