# Congruences of regular variants of finite full transformation semigroups

###### Abstract

Let $\mathcal{T}_{X}$ be the full transformation monoid over a finite set $X$,
and fix some $a\in\mathcal{T}_{X}$ of rank $r$. The variant
$\mathcal{T}_{X}^{a}$ has underlying set $\mathcal{T}_{X}$, and operation
$f\star g=fag$. We study the congruences of the subsemigroup
$P=\operatorname{Reg}(\mathcal{T}_{X}^{a})$ consisting of all regular elements
of $\mathcal{T}_{X}^{a}$, and the lattice $\operatorname{\sf Cong}(P)$ of all
such congruences. Our main structure theorem ultimately decomposes
$\operatorname{\sf Cong}(P)$ as a specific subdirect product of
$\operatorname{\sf Cong}(\mathcal{T}_{r})$ and the full equivalence relation
lattices of certain combinatorial systems of subsets and partitions. We use
this to give an explicit classification of the congruences themselves, and we
also give a formula for the height of the lattice.

_Keywords_ : Congruence, congruence lattice, full transformation semigroup,
variant, subdirect product.

MSC (2020): 20M20, 20M10, 08A30.

Igor Dolinka,111Department of Mathematics and Informatics, University of Novi
Sad, Trg Dositeja Obradovića 4, 21101 Novi Sad, Serbia. Email:
<EMAIL_ADDRESS>James East,222Centre for Research in Mathematics and Data
Science, Western Sydney University, Locked Bag 1797, Penrith NSW 2751,
Australia. Email<EMAIL_ADDRESS>Nik Ruškuc333Mathematical
Institute, School of Mathematics and Statistics, University of St Andrews, St
Andrews, Fife KY16 9SS, UK. Email<EMAIL_ADDRESS>
###### Contents

  1. 1 Introduction
  2. 2 Preliminaries
    1. 2.1 Green’s relations
    2. 2.2 Congruences
    3. 2.3 Finite transformation semigroups and their congruences
    4. 2.4 Variants of finite transformation semigroups
    5. 2.5 Direct and subdirect products
  3. 3 The statement of the main result
  4. 4 Auxiliary results
    1. 4.1 Restrictions and lifts
    2. 4.2 Interactions between congruences and the $\widehat{\mathrel{\mathscr{H}}}^{P}$-relation
  5. 5 A subdirect decomposition of $\operatorname{\sf Cong}(P)$
  6. 6 A direct decomposition of the interval $[\Delta_{P},\kappa]$
  7. 7 The intervals $[\Delta_{P},\rho]$ and $[\Delta_{P},\lambda]$ as subdirect products of full lattices of equivalence relations
    1. 7.1 The interval ${[}\Delta_{P},\rho{]}$
    2. 7.2 The interval ${[}\Delta_{P},\lambda{]}$
  8. 8 Classification of congruences
  9. 9 Application: the height of the lattice $\operatorname{\sf Cong}(P)$
  10. 10 Concluding remarks

##  1 Introduction

In the 1950s, Mal’cev classified the congruences of transformation monoids
[27] and matrix monoids [28]. These two papers initiated a new line of
research in semigroup theory and were followed by a steady stream of papers,
treating partial transformation monoids [31], symmetric inverse monoids [24]
and many others. More recent articles in this area have moved in other
directions, including diagram monoids [13] and direct products of (linear)
transformation monoids [2].

The paper [15] provides a unified framework for understanding the congruences
of many of the above monoids, as well as associated categories and their
ideals; it also contains a fuller discussion of the history of the topic, and
an extensive bibliography. The monoids and categories amenable to analysis via
the tools of [15] share a number of structural features: they are regular and
stable; their ideals form a chain of order type $\leq\omega$; and they satisfy
certain _separation properties_ related to Green’s equivalences.

The current article takes yet another direction in the congruence
classification program, this time moving towards _semigroup variants_. The
first studies of variants were by Hickey [19, 20], building on older ideas of
Lyapin [25] and Magill [26], which were eventually unified categorically [11,
12]. Given a semigroup $S$, and a fixed element $a\in S$, a new _sandwich
operation_ ${\star}$ is defined by $x\star y=xay$ for $x,y\in S$. This is
associative, and the resulting semigroup $S^{a}=(S,{\star})$ is the _variant_
of $S$ with respect to $a$.

The structure of a variant can be much more complex than that of the original
semigroup. For example, consider the _full transformation monoid_
$\mathcal{T}_{4}$, which consists of all self maps of $\\{1,2,3,4\\}$ under
composition. Figure 2 (left) shows the egg-box diagram of $\mathcal{T}_{4}$,
while Figure 1 shows the variant $\mathcal{T}_{4}^{a}$, where
$a=\big{(}\begin{smallmatrix}1&2&3&4\\\ 1&2&3&3\end{smallmatrix}\big{)}$. (An
egg-box diagram is a standard semigroup-theoretic visualisation tool; see for
example [7].) As these figures indicate, $\mathcal{T}_{4}$ has a chain of
ideals, whereas $\mathcal{T}_{4}^{a}$ has an intricate ideal structure.

Figure 1: Egg-box diagram of $\mathcal{T}_{4}^{a}$, where
$a=\leavevmode\hbox{\set@color$\left(\begin{smallmatrix}1&2&3&4\\\
1&2&3&3\end{smallmatrix}\right)$}$.

Figure 2: Left to right: egg-box diagrams of $\mathcal{T}_{4}$,
$\operatorname{Reg}(\mathcal{T}_{4}^{a})$ and $\mathcal{T}_{3}$, where
$a=\leavevmode\hbox{\set@color$\left(\begin{smallmatrix}1&2&3&4\\\
1&2&3&3\end{smallmatrix}\right)$}$.

Since $\mathcal{T}_{4}$ is regular, it follows from [22, Proposition 5] that
the set $\operatorname{Reg}(\mathcal{T}_{4}^{a})$ of regular elements of
$\mathcal{T}_{4}^{a}$ is a subsemigroup. The egg-box diagram of
$\operatorname{Reg}(\mathcal{T}_{4}^{a})$ is shown in Figure 2 (middle), from
which we can see that its ideals once again form a chain. Less obvious, but
still visible in the diagram, is that
$\operatorname{Reg}(\mathcal{T}_{4}^{a})$ is some kind of ‘inflation’ of the
(ordinary) full transformation semigroup $\mathcal{T}_{3}$, which is pictured
in Figure 2 (right). Note that $\mathcal{T}_{3}$ appears here because the
sandwich element $a\in\mathcal{T}_{4}$ has rank (image size) $3$. This
phenomenon was explored at length in the paper [8], which systematically
studied variants of finite full transformation semigroups and their regular
subsemigroups. The ‘inflation’ was explained there in terms of certain ‘hat
relations’ extending Green’s equivalences, and a natural surmorphism
$\operatorname{Reg}(\mathcal{T}_{4}^{a})\to\mathcal{T}_{3}$.

One of the striking consequences of Mal’cev’s classification [27] is that the
congruences of a finite full transformation monoid $\mathcal{T}_{n}$ form a
chain. As explained in [15], this is (very roughly speaking) a consequence of
the normal subgroup lattices of the symmetric groups $\mathcal{S}_{r}$ ($1\leq
r\leq n$) being chains, and $\mathcal{T}_{n}$ having the ‘separation
properties’ mentioned above. We will not need to introduce the latter here,
because the variants $\operatorname{Reg}(\mathcal{T}_{n}^{a})$ turn out not to
satisfy them, and this route is not available to us. But it is perhaps worth
remarking that, as shown in [3], the easiest way to verify the properties for
$\mathcal{T}_{n}$ is to check that its egg-box diagram has a certain
combinatorial property, namely that distinct rows/columns in a non-minimal
$\mathrel{\mathscr{D}}$-class have distinct patterns of group and non-group
$\mathrel{\mathscr{H}}$-classes, as represented in egg-box diagrams by grey
and white cells, respectively. Examining Figure 2, one can check that this is
indeed the case for $\mathcal{T}_{4}$, but clearly not for
$\operatorname{Reg}(\mathcal{T}_{4}^{a})$.

Since the general techniques developed in [15] do not apply to the finite
regular variants $\operatorname{Reg}(\mathcal{T}_{n}^{a})$, a new approach is
required. Furthermore, there is no reason to expect that the congruence
lattice $\operatorname{\sf Cong}(\operatorname{Reg}(\mathcal{T}_{n}^{a}))$
should be a chain, and this can be verified computationally. For example, the
Semigroups package for GAP [17, 29] shows that the congruences of
$\operatorname{Reg}(\mathcal{T}_{4}^{a})$, with $a$ as above, form the lattice
shown in Figure 3. There are $271$ congruences, and the lattice is clearly not
a chain; by contrast, the lattices $\operatorname{\sf Cong}(\mathcal{T}_{3})$
and $\operatorname{\sf Cong}(\mathcal{T}_{4})$ are chains of length $7$ and
$11$, respectively. Nevertheless, certain structural features of the lattice
$\operatorname{\sf Cong}(\operatorname{Reg}(\mathcal{T}_{4}^{a}))$ are visible
in the diagram. Indeed, the kernel $\kappa$ of the above surmorphism
$\operatorname{Reg}(\mathcal{T}_{4}^{a})\to\mathcal{T}_{3}$ corresponds in
Figure 3 to the solid red vertex, and hence one can see the interval
$[\Delta,\kappa]$, as all vertices between it and the solid blue vertex which
represents the trivial congruence $\Delta$. There are a number of further
intervals in $\operatorname{\sf
Cong}(\operatorname{Reg}(\mathcal{T}_{4}^{a}))$, isomorphic to subintervals of
$[\Delta,\kappa]$, which are bounded by pairs of hollow red and blue vertices,
and the entire lattice is a disjoint union of these intervals.

The preceeding observation is formalised in the first part of our main result,
Theorem 3.2(i), which identifies the congruence lattice of a finite regular
variant $\operatorname{Reg}(\mathcal{T}_{X}^{a})$ as a specific subdirect
product of $\operatorname{\sf Cong}(\mathcal{T}_{r})$ and $[\Delta,\kappa]$,
where $r=\operatorname{rank}(a)$ and $\kappa$ is the kernel of an analogous
surmorphism ${\operatorname{Reg}(\mathcal{T}_{X}^{a})\to\mathcal{T}_{r}}$. The
lattice $\operatorname{\sf Cong}(\mathcal{T}_{r})$ is well understood, thanks
to Mal’cev [27], and the remaining parts of Theorem 3.2 describe the structure
of the interval $[\Delta,\kappa]$. First, we have the direct product
decomposition ${[\Delta,\kappa]=[\Delta,\lambda]\times[\Delta,\rho]}$, for
certain congruences $\lambda,\rho\subseteq\kappa$ (Theorem 3.2(ii)).
Ultimately, the intervals $[\Delta,\lambda]$ and $[\Delta,\rho]$ are shown to
be subdirect products of families of full equivalence relation lattices over
natural combinatorial systems of subsets and partitions (Theorem 3.2(iii) and
(iv)).

The paper is organised as follows. After giving preliminaries in Section 2, we
state our main result in Section 3. We then pause to record some auxiliary
lemmas in Section 4, before giving the proofs of the various parts of the main
result in Sections 5–7. The information gathered during this process will then
be combined in Section 8 to give a classification of the congruences
themselves. As an application of our structure theorem, we give a formula for
the height of the congruence lattice in Section 9. The paper concludes in
Section 10 with a discussion of directions for future work.

### Acknowledgements

This work is supported by the following grants: F-121 of the Serbian Academy
of Sciences and Arts; Future Fellowship FT190100632 of the Australian Research
Council; EP/S020616/1 and EP/V003224/1 of the Engineering and Physical
Sciences Research Council. The first author is also partially supported by the
Ministry of Science, Technological Development, and Innovations of the
Republic of Serbia.

Figure 3: The congruence lattice of $\operatorname{Reg}(\mathcal{T}_{4}^{a})$,
where $a=\leavevmode\hbox{\set@color$\left(\begin{smallmatrix}1&2&3&4\\\
1&2&3&3\end{smallmatrix}\right)$}$; cf. Figures 4 and 5.

##  2 Preliminaries

In this section we establish notation and gather some basic background facts
concerning semigroups. Unless otherwise indicated, proofs of the various
assertions can be found in a standard text such as [7] or [21]. We also review
some results concerning congruences from [13, 15] and variants of finite full
transformation semigroups from [8]; see also [16, Chapter 13].

###  2.1 Green’s relations

Let $S$ be a semigroup. We write $S^{1}$ for the _monoid completion_ of $S$.
Specifically, $S^{1}=S$ if $S$ happens to be a monoid; otherwise
$S^{1}=S\cup\\{1\\}$, where $1$ is a symbol not belonging to $S$, acting as an
adjoined identity element. Define preorders $\leq_{\mathrel{\mathscr{L}}}$,
$\leq_{\mathrel{\mathscr{R}}}$ and $\leq_{\mathrel{\mathscr{J}}}$, for $x,y\in
S$, by

$x\leq_{\mathrel{\mathscr{L}}}y\ \Leftrightarrow\ x\in S^{1}y,\qquad
x\leq_{\mathrel{\mathscr{R}}}y\ \Leftrightarrow\ x\in
yS^{1}\qquad\text{and}\qquad x\mathrel{\mathscr{J}}y\ \Leftrightarrow\ x\in
S^{1}yS^{1}.$

These induce equivalences
${\mathrel{\mathscr{L}}}={\leq_{\mathrel{\mathscr{L}}}}\cap{\geq_{\mathrel{\mathscr{L}}}}$,
${\mathrel{\mathscr{R}}}={\leq_{\mathrel{\mathscr{R}}}}\cap{\geq_{\mathrel{\mathscr{R}}}}$
and
${\mathrel{\mathscr{J}}}={\leq_{\mathrel{\mathscr{J}}}}\cap{\geq_{\mathrel{\mathscr{J}}}}$.
Note that ${x\mathrel{\mathscr{L}}y\ \Leftrightarrow\ S^{1}x=S^{1}y}$, with
similar statements holding for $\mathrel{\mathscr{R}}$ and
$\mathrel{\mathscr{J}}$. We also have the equivalences
${\mathrel{\mathscr{H}}}={\mathrel{\mathscr{L}}}\cap{\mathrel{\mathscr{R}}}$
and
${\mathrel{\mathscr{D}}}={\mathrel{\mathscr{L}}}\vee{\mathrel{\mathscr{R}}}$,
where the latter denotes the join of $\mathrel{\mathscr{L}}$ and
$\mathrel{\mathscr{R}}$ in the lattice $\mathfrak{Eq}(S)$ of all equivalences
on $S$, i.e. $\mathrel{\mathscr{D}}$ is the transitive closure of the union
${\mathrel{\mathscr{L}}}\cup{\mathrel{\mathscr{R}}}$. It turns out that in
fact
${\mathrel{\mathscr{D}}}={\mathrel{\mathscr{L}}}\circ{\mathrel{\mathscr{R}}}={\mathrel{\mathscr{R}}}\circ{\mathrel{\mathscr{L}}}$.
If $S$ is finite, then ${\mathrel{\mathscr{D}}}={\mathrel{\mathscr{J}}}$. The
$\mathrel{\mathscr{H}}$-class of any idempotent is a group; all group
$\mathrel{\mathscr{H}}$-classes contained in a common
$\mathrel{\mathscr{D}}$-class are isomorphic.

If $\mathrel{\mathscr{K}}$ denotes any of $\mathrel{\mathscr{L}}$,
$\mathrel{\mathscr{R}}$, $\mathrel{\mathscr{J}}$, $\mathrel{\mathscr{H}}$ or
$\mathrel{\mathscr{D}}$, we denote by $K_{x}$ the
$\mathrel{\mathscr{K}}$-class of $x$ in $S$. The set
$S/{\mathrel{\mathscr{J}}}=\\{J_{x}:x\in S\\}$ of all
$\mathrel{\mathscr{J}}$-classes is partially ordered by

$J_{x}\leq J_{y}\ \Leftrightarrow\
x\leq_{\mathrel{\mathscr{J}}}y\qquad\text{for $x,y\in S$.}$ (2.1)

The above relations are collectively referred to as _Green’s relations_ , and
were introduced in [18]. The next two results are well known, and appear for
example as Lemma 2.2.1 and Proposition 2.3.7 in [21].

######  Lemma 2.2 (Green’s Lemma).

Let $x$ and $y$ be $\mathrel{\mathscr{R}}$-related elements of a semigroup
$S$, so that $y=xs$ and $x=yt$ for some $s,t\in S^{1}$. Then the maps

$L_{x}\to L_{y}:u\mapsto us\qquad\text{and}\qquad L_{y}\to L_{x}:v\mapsto vt$

are mutually inverse $\mathrel{\mathscr{R}}$-preserving bijections. Moreover,
these restrict to mutually inverse bijections

$H_{x}\to H_{y}:u\mapsto us\qquad\text{and}\qquad H_{y}\to H_{x}:v\mapsto vt.$

Lemma 2.2 has a left-right dual, which will also be referred to as Green’s
Lemma.

######  Lemma 2.2.

If $x$ and $y$ are elements of a semigroup $S$, then $xy\in R_{x}\cap L_{y}$
if and only if $L_{x}\cap R_{y}$ contains an idempotent. ∎

An element $x\in S$ is _regular_ if $x\in xSx$. We denote by
$\operatorname{Reg}(S)$ the set of all regular elements, but note that this
need not be a subsemigroup. If $x$ is regular, then
$D_{x}\subseteq\operatorname{Reg}(S)$. We say that $S$ itself is _regular_ if
$S=\operatorname{Reg}(S)$. If $x$ is regular, then there exist idempotents
$e,f\in E(S)$ with $e\mathrel{\mathscr{L}}x\mathrel{\mathscr{R}}f$, and we
then have $xe=x=fx$.

A $\mathrel{\mathscr{J}}$-class $J$ of $S$ is _stable_ if

$x\mathrel{\mathscr{J}}ax\ \Rightarrow\
x\mathrel{\mathscr{L}}ax\qquad\text{and}\qquad x\mathrel{\mathscr{J}}xa\
\Rightarrow\ x\mathrel{\mathscr{R}}xa\qquad\text{for all $x\in J$ and $a\in
S$.}$

A stable $\mathrel{\mathscr{J}}$-class is in fact a
$\mathrel{\mathscr{D}}$-class [23, Proposition 2.3.9]. We say that $S$ itself
is _stable_ if every $\mathrel{\mathscr{J}}$-class is stable. All finite
semigroups are stable [30, Theorem A.2.4].

###  2.2 Congruences

An equivalence $\sigma$ on a semigroup $S$ is a _left congruence_ if it is
_left compatible_ , meaning that

$(x,y)\in\sigma\ \Rightarrow\ (ax,ay)\in\sigma\qquad\text{for all $a,x,y\in
S$.}$

_Right compatibility_ and _right congruences_ are defined dually. Note for
example that $\mathrel{\mathscr{L}}$ is a right congruence, and
$\mathrel{\mathscr{R}}$ a left congruence. An equivalence $\sigma$ on $S$ is a
_congruence_ if it is both left and right compatible, which is equivalent to
$\sigma$ satisfying

$(a,b),(x,y)\in\sigma\ \Rightarrow\ (ax,by)\in\sigma\qquad\text{for all
$a,b,x,y\in S$.}$

The set $\operatorname{\sf Cong}(S)$ of all congruences of $S$ is a lattice
under inclusion, called the _congruence lattice_ of $S$, and is a sublattice
of $\mathfrak{Eq}(S)$. In particular, the meet and join of congruences
$\sigma,\tau\in\operatorname{\sf Cong}(S)$ are the same as in
$\mathfrak{Eq}(S)$, so $\sigma\wedge\tau=\sigma\cap\tau$, while
$\sigma\vee\tau$ is the least equivalence containing $\sigma\cup\tau$. The
bottom and top elements of $\operatorname{\sf Cong}(S)$ are the trivial and
universal relations:

$\Delta_{S}=\\{(x,x):x\in X\\}\qquad\text{and}\qquad\nabla_{S}=S\times S.$

A (possibly empty) subset $I\subseteq S$ is an _ideal_ if $SI\cup IS\subseteq
I$. Any such $I$ determines the _Rees congruence_

$R_{I}=\nabla_{I}\cup\Delta_{S}=\\{(x,y)\in S\times S:x=y\text{ or }x,y\in
I\\}.$

Note that $R_{\varnothing}=\Delta_{S}$ and $R_{S}=\nabla_{S}$.

Ideals can be combined with group $\mathrel{\mathscr{H}}$-classes to create
another family of congruences as follows. Let $I$ be an ideal of $S$. As $I$
is a union of $\mathrel{\mathscr{J}}$-classes, so too is $S\setminus I$.
Suppose $J$ is a $\mathrel{\mathscr{J}}$-class that is minimal in the poset
$(S\setminus I)/{\mathrel{\mathscr{J}}}$ under the $\leq$ order defined in
(2.1). Suppose also that $J$ is regular and stable, so that in fact $J$ is a
$\mathrel{\mathscr{D}}$-class. Let $G$ be a group
$\mathrel{\mathscr{H}}$-class contained in $J$, and let $N\unlhd G$ be a
normal subgroup. The relation

$\nu_{N}=S^{1}(N\times N)S^{1}\cap(J\times J)=\big{\\{}(axb,ayb):x,y\in N,\
a,b\in S^{1},\ axb,ayb\in J\big{\\}}$

is an equivalence on $J$, and $\nu_{N}\subseteq{\mathrel{\mathscr{H}}}$ [13,
Lemma 3.17]. Moreover, the relation

$R_{I,N}=\nabla_{I}\cup\nu_{N}\cup\Delta_{S}$ (2.3)

is a congruence of $S$ [13, Proposition 3.23]. As explained in [15, Remark
2.11], the set of congruences $\\{R_{I,N}:N\unlhd G\\}$ forms a sublattice of
$\operatorname{\sf Cong}(S)$ isomorphic to the normal subgroup lattice of $G$.
In the case that $N=\\{1\\}$ is the trivial (normal) subgroup, $R_{I,N}$ is
just the Rees congruence $R_{I}$. It was shown in [13, Lemma 3.16] that the
$\nu_{N}$ relations are independent of the choice of group
$\mathrel{\mathscr{H}}$-class, in the sense that for any two such groups
$G_{1},G_{2}\subseteq J$, and for any normal subgroup $N_{1}\unlhd G_{1}$, we
have $\nu_{N_{1}}=\nu_{N_{2}}$ for some $N_{2}\unlhd G_{2}$.

######  Lemma 2.4.

Let $D$ be a stable regular $\mathrel{\mathscr{J}}$-class of a semigroup $S$
(so that $D$ is in fact a $\mathrel{\mathscr{D}}$-class), and let
$\sigma\in\operatorname{\sf Cong}(S)$. Fix a group
$\mathrel{\mathscr{H}}$-class $G\subseteq D$, and let $e$ be the identity of
$G$. Then

$\sigma\cap{\mathrel{\mathscr{H}}}{\restriction}_{D}=\nu_{N}\qquad\text{where}\qquad
N=\\{g\in G:e\mathrel{\sigma}g\\}.$

###### Proof.

Let $I$ be the union of all the $\mathrel{\mathscr{J}}$-classes below $D$, so
that $I$ is a (possibly empty) ideal of $S$, and consider the congruence
$\tau=\sigma\cap R_{I,G}\in\operatorname{\sf Cong}(S)$. Since

$R_{I,G}=\nabla_{I}\cup\nu_{G}\cup\Delta_{S}=\nabla_{I}\cup{\mathrel{\mathscr{H}}}{\restriction}_{D}\cup\Delta_{S},$

we have

$\tau=\sigma{\restriction}_{I}\cup(\sigma\cap{\mathrel{\mathscr{H}}}{\restriction}_{D})\cup\Delta_{S}.$
(2.5)

In particular,
$\tau{\restriction}_{D}=\sigma\cap{\mathrel{\mathscr{H}}}{\restriction}_{D}\subseteq{\mathrel{\mathscr{H}}}$,
so it follows from [15, Lemma 2.8] that

$\tau{\restriction}_{D}=\nu_{N^{\prime}},\qquad\text{where}\qquad
N^{\prime}=\\{g\in G:e\mathrel{\tau}g\\}.$

We have already observed that
$\tau{\restriction}_{D}=\sigma\cap{\mathrel{\mathscr{H}}}{\restriction}_{D}$,
so it follows that
$\sigma\cap{\mathrel{\mathscr{H}}}{\restriction}_{D}=\nu_{N^{\prime}}$. To
complete the proof, it remains to show that $N^{\prime}=N$, i.e. that
$(e,g)\in\tau\ \Leftrightarrow\ (e,g)\in\sigma$ for all $g\in G$. But for any
such $g$, we have

$\displaystyle(e,g)\in\tau$ $\displaystyle\ \Leftrightarrow\
(e,g)\in\sigma\cap{\mathrel{\mathscr{H}}}{\restriction}_{D}$ by (2.5), as
$e,g\in D$ $\displaystyle\ \Leftrightarrow\ (e,g)\in\sigma$
$\displaystyle\text{since $(e,g)\in{\mathrel{\mathscr{H}}}$ (as $e,g\in
G$).}\qed$

###  2.3 Finite transformation semigroups and their congruences

Fix a finite set $X$ of size $n$, and let $\mathcal{T}_{X}$ be the _full
transformation semigroup_ over $X$, i.e. the semigroup of all mappings $X\to
X$ under composition. Green’s preorders on $\mathcal{T}_{X}$ are determined by
images, kernels and ranks. These parameters are defined, for
$f\in\mathcal{T}_{X}$, by

$\operatorname{im}(f)=\\{xf:x\in X\\},\quad\ker(f)=\\{(x,y)\in X\times
X:xf=yf\\}\quad\text{and}\quad\operatorname{rank}(f)=|{\operatorname{im}(f)}|=|X/\ker(f)|.$

For $f,g\in\mathcal{T}_{X}$ we have

$\displaystyle f\leq_{\mathrel{\mathscr{L}}}g$ $\displaystyle\
\Leftrightarrow\ \operatorname{im}(f)\subseteq\operatorname{im}(g),$
$\displaystyle f\leq_{\mathrel{\mathscr{R}}}g$ $\displaystyle\
\Leftrightarrow\ \ker(f)\supseteq\ker(g),$ $\displaystyle
f\leq_{\mathrel{\mathscr{J}}}g$ $\displaystyle\ \Leftrightarrow\
\operatorname{rank}(f)\leq\operatorname{rank}(g),$ $\displaystyle
f\mathrel{\mathscr{L}}g$ $\displaystyle\ \Leftrightarrow\
\operatorname{im}(f)=\operatorname{im}(g),$ $\displaystyle
f\mathrel{\mathscr{R}}g$ $\displaystyle\ \Leftrightarrow\ \ker(f)=\ker(g),$
$\displaystyle f\mathrel{\mathscr{J}}g$ $\displaystyle\ \Leftrightarrow\
\operatorname{rank}(f)=\operatorname{rank}(g).$

The ${\mathrel{\mathscr{J}}}={\mathrel{\mathscr{D}}}$-classes and non-empty
ideals of $\mathcal{T}_{X}$ are the sets

$D_{r}=\\{f\in\mathcal{T}_{X}:\operatorname{rank}(f)=r\\}\qquad\text{and}\qquad
I_{r}=\\{f\in\mathcal{T}_{X}:\operatorname{rank}(f)\leq r\\}\qquad\text{for
$1\leq r\leq n$,}$

and they form chains, $D_{1}<\cdots<D_{n}$ and $I_{1}\subset\cdots\subset
I_{n}=\mathcal{T}_{n}$. The top $\mathrel{\mathscr{D}}$-class $D_{n}$ is equal
to the symmetric group $\mathcal{S}_{X}$. Group
$\mathrel{\mathscr{H}}$-classes in $D_{r}$ are isomorphic to
$\mathcal{S}_{r}$. In particular, we can identify $\mathcal{S}_{r}$ with any
such group $\mathrel{\mathscr{H}}$-class, and we can then speak of the
congruences $R_{I_{r-1},N}$, for any $1\leq r\leq n$, and any
$N\unlhd\mathcal{S}_{r}$. For $r=1$ we interpret $I_{0}=\varnothing$; as
$\mathcal{S}_{1}$ is the trivial group, the only such congruence arising for
$r=1$ is $R_{I_{0},\mathcal{S}_{1}}=\Delta_{\mathcal{T}_{X}}$. The following
major result by Mal’cev initiated research into congruence lattices of
important concrete semigroups, and is one of the key ingredients on which the
present work is built:

######  Theorem 2.6 (Mal’cev [27]).

If $X$ is a finite set of size $n$, then the congruence lattice of
$\mathcal{T}_{X}$ is a chain:

$\operatorname{\sf
Cong}(\mathcal{T}_{X})=\\{\nabla_{\mathcal{T}_{X}}\\}\cup\\{R_{I_{r-1},N}:1\leq
r\leq n,\ N\unlhd\mathcal{S}_{r}\\}.$

###  2.4 Variants of finite transformation semigroups

Again we fix a finite set $X$. We also fix a transformation
$a\in\mathcal{T}_{X}$, and let ${\star}$ be the _sandwich operation_ on
$\mathcal{T}_{X}$ defined by

$f\star g=fag\qquad\text{for $f,g\in\mathcal{T}_{X}$.}$

Then $\mathcal{T}_{X}^{a}=(\mathcal{T}_{X},{\star})$ is the _variant_ of $S$
with respect to $a$. Since there exists a permutation $p\in\mathcal{S}_{X}$
such that $ap$ is an idempotent, and since the map

$\mathcal{T}_{X}^{a}\to\mathcal{T}_{X}^{ap}:f\mapsto p^{-1}f$ (2.7)

is an isomorphism, we may assume without loss of generality that $a$ is itself
an idempotent. We will adopt this set-up throughout the paper. Any statement
that is made with that assumption can readily be translated into the case of
an arbitrary sandwich element using the isomorphism (2.7). Using standard
tabular notation for transformations, we will write

$a=\big{(}\begin{smallmatrix}A_{1}&\cdots&A_{r}\\\
a_{1}&\cdots&a_{r}\end{smallmatrix}\big{)},\quad\text{so}\quad\operatorname{rank}(a)=r,\quad\operatorname{im}(a)=\\{a_{1},\ldots,a_{r}\\}\quad\text{and}\quad
X/\ker(a)=\\{A_{1},\ldots,A_{r}\\}.$ (2.8)

Since $a$ is an idempotent, we have $a_{i}\in A_{i}$ for all $i$. We now
outline some results concerning $\mathcal{T}_{X}^{a}$ and certain important
subsemigroups; proofs of the assertions can be found in [8, 11, 12].

The set of all regular elements of $\mathcal{T}_{X}^{a}$ is a subsemigroup,
and we denote it by

$P=\operatorname{Reg}(\mathcal{T}_{X}^{a}).$

Many characterisations of $P$ were given in [8], the most useful for our
purposes being

$P=\\{f\in\mathcal{T}_{X}:\operatorname{rank}(afa)=\operatorname{rank}(f)\\}.$

Since $\operatorname{rank}(afa)\leq\operatorname{rank}(a)=r$ for any
$f\in\mathcal{T}_{X}$, the elements of $P$ have rank at most $r$. The set

$T=a\mathcal{T}_{X}a=a\star\mathcal{T}_{X}\star
a=\\{afa:f\in\mathcal{T}_{X}\\}$

is a subsemigroup of both $\mathcal{T}_{X}$ and $\mathcal{T}_{X}^{a}$
($fg=f\star g$ for $f,g\in T$), and $T\cong\mathcal{T}_{r}$, where we recall
that $r=\operatorname{rank}(a)$. Since $afa=f$ for all $f\in T$, certainly
$\operatorname{rank}(afa)=\operatorname{rank}(f)$ for all such $f$, and so
$T\subseteq P$. It also follows that $T=aPa=a\star P\star a$, and that we have
a retraction

$\phi:P\to T:f\mapsto\overline{f}=afa.$ (2.9)

That is, $\overline{f\star
g}=\overline{f}\star\overline{g}(=\overline{f}\overline{g})$ for all $f,g\in
P$, and $\overline{h}=h$ for all $h\in T$.

Our results and proofs often involve the interplay between $P$ and $T$ via
$\phi$. We will distinguish between standard semigroup theoretic notation as
applied to $P$ or $T$ by using appropriate superscripts. Thus, for example, if
$\mathrel{\mathscr{K}}$ is any of Green’s equivalences
$\mathrel{\mathscr{L}}$, $\mathrel{\mathscr{R}}$, $\mathrel{\mathscr{J}}$,
$\mathrel{\mathscr{H}}$ or $\mathrel{\mathscr{D}}$, we will write
$\mathrel{\mathscr{K}}^{P}$ and $\mathrel{\mathscr{K}}^{T}$ for
$\mathrel{\mathscr{K}}$ on $P$ and $T$, respectively. These relations have
exactly the same characterisation as in $\mathcal{T}_{X}$. Namely, if $S$ is
either $P$ or $T$, then for any $f,g\in S$ we have

$f\mathrel{\mathscr{L}}^{S}g\ \Leftrightarrow\
\operatorname{im}(f)=\operatorname{im}(g),\quad f\mathrel{\mathscr{R}}^{S}g\
\Leftrightarrow\ \ker(f)=\ker(g)\quad\text{and}\quad
f\mathrel{\mathscr{D}}^{S}g\ \Leftrightarrow\
\operatorname{rank}(f)=\operatorname{rank}(g).$

Regarding the $\mathrel{\mathscr{K}}$-classes, we have $K_{f}^{T}\subseteq
K_{f}^{P}$ for any $f\in T(\subseteq P)$, and this inclusion is typically
strict. We do note, however, that $H_{f}^{T}=H_{f}^{P}$ for any $f\in T$,
although $P$ typically has more $\mathrel{\mathscr{H}}$-classes than $T$. The
${\mathrel{\mathscr{D}}^{S}}(={\mathrel{\mathscr{J}}^{S}})$-classes and non-
empty ideals of $S$ (still denoting either $P$ or $T$) are the sets

$D_{q}^{S}=\\{f\in S:\operatorname{rank}(f)=q\\}\qquad\text{and}\qquad
I_{q}^{S}=\\{f\in S:\operatorname{rank}(f)\leq q\\}\qquad\text{for $1\leq
q\leq r$.}$

These are ordered by $D_{1}^{S}<\cdots<D_{r}^{S}$ and
$I_{1}^{S}\subset\cdots\subset I_{r}^{S}=S$. We also define
$I_{0}^{S}=\varnothing$.

An important role will be played by the preimages under $\phi$ of Green’s
relations on $T$:

${\mathchoice{\accentset{\displaystyle\text{\smash{\raisebox{-5.59721pt}{$\widehatsym$}}}}{\mathrel{\mathscr{K}}}}{\accentset{\textstyle\text{\smash{\raisebox{-5.59721pt}{$\widehatsym$}}}}{\mathrel{\mathscr{K}}}}{\accentset{\scriptstyle\text{\smash{\raisebox{-3.91806pt}{$\widehatsym$}}}}{\mathrel{\mathscr{K}}}}{\accentset{\scriptscriptstyle\text{\smash{\raisebox{-2.7986pt}{$\widehatsym$}}}}{\mathrel{\mathscr{K}}}}^{P}}={\mathrel{\mathscr{K}}^{T}}\phi^{-1}=\\{(f,g)\in
P\times P:(\overline{f},\overline{g})\in{\mathrel{\mathscr{K}}^{T}}\\}.$

We write
$\mathchoice{\accentset{\displaystyle\text{\smash{\raisebox{-5.59721pt}{$\widehatsym$}}}}{K}}{\accentset{\textstyle\text{\smash{\raisebox{-5.59721pt}{$\widehatsym$}}}}{K}}{\accentset{\scriptstyle\text{\smash{\raisebox{-3.91806pt}{$\widehatsym$}}}}{K}}{\accentset{\scriptscriptstyle\text{\smash{\raisebox{-2.7986pt}{$\widehatsym$}}}}{K}}_{f}^{P}$
for the
$\mathchoice{\accentset{\displaystyle\text{\smash{\raisebox{-5.59721pt}{$\widehatsym$}}}}{\mathrel{\mathscr{K}}}}{\accentset{\textstyle\text{\smash{\raisebox{-5.59721pt}{$\widehatsym$}}}}{\mathrel{\mathscr{K}}}}{\accentset{\scriptstyle\text{\smash{\raisebox{-3.91806pt}{$\widehatsym$}}}}{\mathrel{\mathscr{K}}}}{\accentset{\scriptscriptstyle\text{\smash{\raisebox{-2.7986pt}{$\widehatsym$}}}}{\mathrel{\mathscr{K}}}}^{P}$-class
of $f$ in $P$. Note that
$\mathrel{\mathchoice{\accentset{\displaystyle\text{\smash{\raisebox{-5.59721pt}{$\widehatsym$}}}}{\mathscr{L}}}{\accentset{\textstyle\text{\smash{\raisebox{-5.59721pt}{$\widehatsym$}}}}{\mathscr{L}}}{\accentset{\scriptstyle\text{\smash{\raisebox{-3.91806pt}{$\widehatsym$}}}}{\mathscr{L}}}{\accentset{\scriptscriptstyle\text{\smash{\raisebox{-2.7986pt}{$\widehatsym$}}}}{\mathscr{L}}}}^{P}$
is a right congruence of $P$, being a pre-image of the right congruence
$\mathrel{\mathscr{L}}^{T}$; likewise,
$\mathrel{\mathchoice{\accentset{\displaystyle\text{\smash{\raisebox{-5.59721pt}{$\widehatsym$}}}}{\mathscr{R}}}{\accentset{\textstyle\text{\smash{\raisebox{-5.59721pt}{$\widehatsym$}}}}{\mathscr{R}}}{\accentset{\scriptstyle\text{\smash{\raisebox{-3.91806pt}{$\widehatsym$}}}}{\mathscr{R}}}{\accentset{\scriptscriptstyle\text{\smash{\raisebox{-2.7986pt}{$\widehatsym$}}}}{\mathscr{R}}}}^{P}$
is a left congruence. It follows from [11, Lemma 3.11] that
${\mathrel{\mathscr{K}}^{P}}\subseteq{\mathrel{\mathchoice{\accentset{\displaystyle\text{\smash{\raisebox{-5.59721pt}{$\widehatsym$}}}}{\mathscr{K}}}{\accentset{\textstyle\text{\smash{\raisebox{-5.59721pt}{$\widehatsym$}}}}{\mathscr{K}}}{\accentset{\scriptstyle\text{\smash{\raisebox{-3.91806pt}{$\widehatsym$}}}}{\mathscr{K}}}{\accentset{\scriptscriptstyle\text{\smash{\raisebox{-2.7986pt}{$\widehatsym$}}}}{\mathscr{K}}}}^{P}}\subseteq{\mathrel{\mathchoice{\accentset{\displaystyle\text{\smash{\raisebox{-5.59721pt}{$\widehatsym$}}}}{\mathscr{D}}}{\accentset{\textstyle\text{\smash{\raisebox{-5.59721pt}{$\widehatsym$}}}}{\mathscr{D}}}{\accentset{\scriptstyle\text{\smash{\raisebox{-3.91806pt}{$\widehatsym$}}}}{\mathscr{D}}}{\accentset{\scriptscriptstyle\text{\smash{\raisebox{-2.7986pt}{$\widehatsym$}}}}{\mathscr{D}}}}^{P}}={\mathrel{\mathscr{D}}^{P}}$
for ${\mathrel{\mathscr{K}}}={\mathrel{\mathscr{L}}}$, $\mathrel{\mathscr{R}}$
or $\mathrel{\mathscr{H}}$, and of course then
${\mathrel{\mathchoice{\accentset{\displaystyle\text{\smash{\raisebox{-5.59721pt}{$\widehatsym$}}}}{\mathscr{J}}}{\accentset{\textstyle\text{\smash{\raisebox{-5.59721pt}{$\widehatsym$}}}}{\mathscr{J}}}{\accentset{\scriptstyle\text{\smash{\raisebox{-3.91806pt}{$\widehatsym$}}}}{\mathscr{J}}}{\accentset{\scriptscriptstyle\text{\smash{\raisebox{-2.7986pt}{$\widehatsym$}}}}{\mathscr{J}}}}^{P}}={\mathrel{\mathscr{J}}^{P}}={\mathrel{\mathscr{D}}^{P}}={\mathrel{\mathchoice{\accentset{\displaystyle\text{\smash{\raisebox{-5.59721pt}{$\widehatsym$}}}}{\mathscr{D}}}{\accentset{\textstyle\text{\smash{\raisebox{-5.59721pt}{$\widehatsym$}}}}{\mathscr{D}}}{\accentset{\scriptstyle\text{\smash{\raisebox{-3.91806pt}{$\widehatsym$}}}}{\mathscr{D}}}{\accentset{\scriptscriptstyle\text{\smash{\raisebox{-2.7986pt}{$\widehatsym$}}}}{\mathscr{D}}}}^{P}}$,
as $P$ is finite. The next result gathers some facts from [11, Theorem 3.14].
For the statement, recall that a _rectangular band_ is (isomorphic to) a
semigroup of the form $L\times R$ with product
$(l_{1},r_{1})(l_{2},r_{2})=(l_{1},r_{2})$, and a _rectangular group_ is
(isomorphic to) a direct product of a rectangular band and a group.

######  Lemma 2.10.

Let $f\in P$.

  1. (i)

The restriction $\phi{\restriction}_{H_{f}^{P}}$ is a bijection $H_{f}^{P}\to
H_{\overline{f}}^{T}$.

  2. (ii)

If $H_{\overline{f}}^{T}$ is a group, then
$\mathchoice{\accentset{\displaystyle\text{\smash{\raisebox{-5.59721pt}{$\widehatsym$}}}}{H}}{\accentset{\textstyle\text{\smash{\raisebox{-5.59721pt}{$\widehatsym$}}}}{H}}{\accentset{\scriptstyle\text{\smash{\raisebox{-3.91806pt}{$\widehatsym$}}}}{H}}{\accentset{\scriptscriptstyle\text{\smash{\raisebox{-2.7986pt}{$\widehatsym$}}}}{H}}_{f}^{P}$
is a rectangular group, and in particular a union of group
$\mathrel{\mathscr{H}}^{P}$-classes.

  3. (iii)

If $H_{\overline{f}}^{T}$ is not a group, then
$\mathchoice{\accentset{\displaystyle\text{\smash{\raisebox{-5.59721pt}{$\widehatsym$}}}}{H}}{\accentset{\textstyle\text{\smash{\raisebox{-5.59721pt}{$\widehatsym$}}}}{H}}{\accentset{\scriptstyle\text{\smash{\raisebox{-3.91806pt}{$\widehatsym$}}}}{H}}{\accentset{\scriptscriptstyle\text{\smash{\raisebox{-2.7986pt}{$\widehatsym$}}}}{H}}_{f}^{P}$
is a union of non-group $\mathrel{\mathscr{H}}^{P}$-classes. ∎

###  2.5 Direct and subdirect products

Our main result will describe the congruence lattice $\operatorname{\sf
Cong}(P)$ as successively decomposed into direct and subdirect products of
smaller lattices. Here we introduce terminology and notation for these
products. What follows is presented in the context of lattices, but is in fact
completely general and applies to any algebraic structures.

Let $L_{i}$ ($i\in I$) be a collection of lattices. The _direct product_
$\prod_{i\in I}L_{i}$ is the lattice with underlying set consisting of all
$I$-tuples $(a_{i})_{i\in I}=(a_{i})$, with each $a_{i}\in L_{i}$, and with
component-wise meet and join operations $(a_{i})\wedge(b_{i})=(a_{i}\wedge
b_{i})$ and $(a_{i})\vee(b_{i})=(a_{i}\vee b_{i})$. For every $j\in I$, the
projection $\pi_{j}:\prod_{i\in I}L_{i}\rightarrow L_{j}$ is a lattice
surmorphism. A sublattice $L\leq\prod_{i\in I}L_{i}$ is said to be a
_subdirect product_ of the $L_{i}$ if $\pi_{i}(L)=L_{i}$ for all $i\in I$. A
_subdirect embedding_ is an injective morphism $L\rightarrow\prod_{i\in
I}L_{i}$ whose image is a subdirect product.

We now review the well-known criteria for the existence of a direct
decomposition in the case of two factors, or a subdirect decomposition for any
number of factors.

######  Proposition 2.11 (see [4, Theorem II.7.5]).

Let $L$ be a lattice, and let $\phi_{i}:L\rightarrow L_{i}$ $(i=1,2)$ be two
lattice surmorphisms. If $\ker(\phi_{1})\cap\ker(\phi_{2})=\Delta_{L}$ and
$\ker(\phi_{1})\circ\ker(\phi_{2})=\nabla_{L}$ then $L\cong L_{1}\times L_{2}$
via $a\mapsto(\phi_{1}(a),\phi_{2}(a))$. ∎

######  Proposition 2.12 (see [4, Lemma II.8.2]).

Let $L$ be a lattice, and let $\phi_{i}:L\rightarrow L_{i}$ $(i\in I)$ be
lattice surmorphisms. If $\bigcap_{i\in I}\ker(\phi_{i})=\Delta_{L}$ then the
mapping $a\mapsto(\phi_{i}(a))$ is a subdirect embedding of $L$ into
$\prod_{i\in I}L_{i}$. ∎

##  3 The statement of the main result

The main result of this paper is a detailed structural description of the
congruence lattice of the regular part of a variant of a finite full
transformation monoid. This description is in several stages. The purpose of
this section is to give full statements for each of the stages, and, in the
process, fix the concepts and notation that will be used subsequently. To
begin with:

  * •

$P$ will denote the semigroup $\operatorname{Reg}(\mathcal{T}_{X}^{a})$, i.e.
the regular part of the variant $\mathcal{T}_{X}^{a}$ of the full
transformation monoid on a finite set $X$, with respect to the sandwich
element $a=\big{(}\begin{smallmatrix}A_{1}&\cdots&A_{r}\\\
a_{1}&\cdots&a_{r}\end{smallmatrix}\big{)}\in\mathcal{T}_{X}$, which we assume
is an idempotent.

  * •

$\phi$ is the retraction $f\mapsto\overline{f}=afa$ from (2.9),
$T\cong\mathcal{T}_{r}$ is its image, and $\kappa$ its kernel:

$\kappa=\ker(\phi)=\\{(f,g)\in P\times P:\overline{f}=\overline{g}\\}.$

  * •

We additionally define $\lambda=\kappa\cap{\mathrel{\mathscr{L}}^{P}}$ and
$\rho=\kappa\cap{\mathrel{\mathscr{R}}^{P}}$.

  * •

For congruences $\xi\in\operatorname{\sf Cong}(\mathcal{T}_{r})$ and
$\theta\in[\Delta_{P},\kappa](\subseteq\operatorname{\sf Cong}(P))$, we define

$\operatorname{rank}(\xi)=\max\\{q:R_{I_{q}^{\mathcal{T}_{r}}}\subseteq\xi\\}\qquad\text{and}\qquad\operatorname{rank}(\theta)=\max\\{q:\kappa\cap
R_{I_{q}^{P}}\subseteq\theta\\}.$ (3.1)

At this point, we have sufficient notation for the first two parts of our main
theorem. For the remaining two parts we need to do a bit more work.

For a positive integer $k$ we write $[k]=\\{1,\ldots,k\\}$. Consider a non-
empty subset ${\varnothing\not=I\subseteq[r]}$, where we recall that
$r=\operatorname{rank}(a)$. Let $\mathcal{C}_{I}$ be the set of all cross-
sections of $\\{A_{i}:i\in I\\}$; thus an element of $\mathcal{C}_{I}$ has the
form $C=\\{c_{i}:i\in I\\}$ with each $c_{i}\in A_{i}$. For $\varnothing\neq
J\subseteq I\subseteq[r]$ and $C\in\mathcal{C}_{I}$ as above, define
$C{\restriction}_{J}=\\{c_{j}:j\in J\\}$. For a relation $\psi$ on
$\mathcal{C}_{I}$ define
$\psi{\restriction}_{J}=\big{\\{}(C{\restriction}_{J},C^{\prime}{\restriction}_{J}):(C,C^{\prime})\in\psi\big{\\}}$,
which is a relation on $\mathcal{C}_{J}$.

A _partition_ of a set $Z$ is a set of non-empty, pairwise-disjoint subsets of
$Z$ (called blocks), which cover $Z$. If the blocks of a partition
$\mathbf{I}$ are all contained in blocks of another partition $\mathbf{J}$ (of
the same set), we say that $\mathbf{I}$ _refines_ $\mathbf{J}$, and write
$\mathbf{J}\preceq\mathbf{I}$. For a positive integer $k$, we denote the
_trivial partition_ of $[k]$ by $[[k]]=\big{\\{}\\{i\\}:i\in[k]\big{\\}}$.
Clearly, $\mathbf{I}\preceq[[k]]$ for every partition $\mathbf{I}$ of $[k]$.

Now consider a partition $\mathbf{I}$ of $[r]$. Let $\mathcal{P}_{\mathbf{I}}$
be the set of all partitions of $[n]$ of the form
$\mathbf{P}=\\{P_{I}:I\in\mathbf{I}\\}$ such that
$P_{I}\cap\operatorname{im}(a)=\\{a_{i}:i\in I\\}$ for each $I\in\mathbf{I}$.
For partitions $\mathbf{J}\preceq\mathbf{I}\preceq[[r]]$, and
$\mathbf{P}\in\mathcal{P}_{\mathbf{I}}$ as above, define
$\mathbf{P}{\restriction}_{\mathbf{J}}\in\mathcal{P}_{\mathbf{J}}$ to be the
partition $\\{Q_{J}:J\in\mathbf{J}\\}$, where
$Q_{J}=\bigcup\\{P_{I}:I\in\mathbf{I},\ I\subseteq J\\}$ for each
$J\in\mathbf{J}$. For a relation $\psi$ on $\mathcal{P}_{\mathbf{I}}$ define
$\psi{\restriction}_{\mathbf{J}}=\big{\\{}(\mathbf{P}{\restriction}_{\mathbf{J}},\mathbf{P}^{\prime}{\restriction}_{\mathbf{J}}):(\mathbf{P},\mathbf{P}^{\prime})\in\psi\big{\\}}$,
which is a relation on $\mathcal{P}_{\mathbf{J}}$.

Here then is our main result. As per our convention introduced in Subsection
2.4, it is formulated in terms of an idempotent sandwich element. There is no
loss of generality, due to the isomorphism (2.7).

######  Theorem 3.2.

Let $X$ be a finite set, let $a\in\mathcal{T}_{X}$ be an idempotent of rank
$r\geq 2$, and let $P=\operatorname{Reg}(\mathcal{T}_{X}^{a})$.

  1. (i)

The lattice $\operatorname{\sf Cong}(P)$ subdirectly embeds into
$\operatorname{\sf Cong}(\mathcal{T}_{r})\times[\Delta_{P},\kappa]$, with
image

$\big{\\{}(\xi,\theta)\in\operatorname{\sf
Cong}(\mathcal{T}_{r})\times[\Delta_{P},\kappa]:\operatorname{rank}(\xi)\leq\operatorname{rank}(\theta)\big{\\}}.$

  2. (ii)

The interval $[\Delta_{P},\kappa]$ is isomorphic to the direct product
$[\Delta_{P},\lambda]\times[\Delta_{P},\rho]$.

  3. (iii)

The interval $[\Delta_{P},\rho]$ subdirectly embeds into the direct product
$\prod_{\varnothing\neq I\subseteq[r]}\mathfrak{Eq}(\mathcal{C}_{I})$ of full
lattices of equivalence relations on the sets $\mathcal{C}_{I}$, with image

$\Big{\\{}(\psi_{I})\in\prod_{\varnothing\neq
I\subseteq[r]}\mathfrak{Eq}(\mathcal{C}_{I}):\psi_{I}{\restriction}_{J}\subseteq\psi_{J}\text{
for all }\varnothing\neq J\subseteq I\subseteq[r]\Big{\\}}.$

  4. (iv)

The interval $[\Delta_{P},\lambda]$ subdirectly embeds into the direct product
$\prod_{\mathbf{I}\preceq[[r]]}\mathfrak{Eq}(\mathcal{P}_{\mathbf{I}})$ of
full lattices of equivalence relations on the sets $\mathcal{P}_{\mathbf{I}}$,
with image

$\Big{\\{}(\psi_{\mathbf{I}})\in\prod_{\mathbf{I}\preceq[[r]]}\mathfrak{Eq}(\mathcal{P}_{\mathbf{I}}):\psi_{\mathbf{I}}{\restriction}_{\mathbf{J}}\subseteq\psi_{\mathbf{J}}\text{
for all }\mathbf{J}\preceq\mathbf{I}\preceq[[r]]\Big{\\}}.$

######  Remark 3.3.

The $r=1$ case was excluded from Theorem 3.2, but it is easy to understand the
semigroup $P=\operatorname{Reg}(\mathcal{T}_{X}^{a})$ and its congruence
lattice in this case. Indeed, here $P=D_{1}$ is a right zero semigroup, and
hence every equivalence is a congruence, meaning that $\operatorname{\sf
Cong}(P)=\mathfrak{Eq}(P)$. We also have $T=\\{a\\}$, and so
$\kappa=\nabla_{P}$, $\lambda={\mathrel{\mathscr{L}}^{P}}=\Delta_{P}$ and
$\rho={\mathrel{\mathscr{R}}^{P}}=\nabla_{P}$. Parts (ii)–(iv) of the theorem
are then trivial. Regarding part (i), $\operatorname{\sf Cong}(P)$ is of
course isomorphic to $\operatorname{\sf
Cong}(\mathcal{T}_{1})\times[\Delta_{P},\kappa]$, as $\mathcal{T}_{1}$ is
trivial and $[\Delta_{P},\kappa]=[\Delta_{P},\nabla_{P}]=\operatorname{\sf
Cong}(P)$. However, there is a slight discrepancy in the stated image of the
embedding when $r=1$, as the unique congruence of $\mathcal{T}_{1}$ (i.e.
$\Delta_{\mathcal{T}_{1}}=\nabla_{\mathcal{T}_{1}}$) has rank $1$, while the
non-universal congruences in $[\Delta_{P},\kappa](=\operatorname{\sf
Cong}(P))$ have rank $0$. This ‘problem’ could be fixed by introducing the
convention that $\operatorname{rank}(\Delta_{\mathcal{T}_{1}})=0$.

The four parts of Theorem 3.2 will be proved as Theorems 5.2, 6.1, 7.2 and
7.11. In fact, each of these results provides additional information, in the
form of an explicit expression for the (sub)direct embedding in question. En
route to proving them, we will gather enough information to deduce an explicit
classification of the congruences of $P$, which will be given in Theorem 8.1.

##  4 Auxiliary results

The proofs of the four parts of Theorem 3.2 will be given in Sections 5–7. To
keep those sections focussed on their main objectives, this section gathers
some technical observations that will be subsequently used. They concern the
relationship between congruences on $P$ and on $T$ (Subsection 4.1), as well
as a couple of technical properties of congruences containing
$\mathrel{\mathchoice{\accentset{\displaystyle\text{\smash{\raisebox{-5.59721pt}{$\widehatsym$}}}}{\mathscr{H}}}{\accentset{\textstyle\text{\smash{\raisebox{-5.59721pt}{$\widehatsym$}}}}{\mathscr{H}}}{\accentset{\scriptstyle\text{\smash{\raisebox{-3.91806pt}{$\widehatsym$}}}}{\mathscr{H}}}{\accentset{\scriptscriptstyle\text{\smash{\raisebox{-2.7986pt}{$\widehatsym$}}}}{\mathscr{H}}}}^{P}$-related
pairs (Subsection 4.2).

###  4.1 Restrictions and lifts

Given that $T$ is both a subsemigroup of $P$ and a homomorphic image (via
$\phi$) of $P$, any congruence $\sigma\in\operatorname{\sf Cong}(P)$ induces
the restriction to $T$ and the image in $T$:

$\sigma{\restriction}_{T}=\sigma\cap(T\times T)=\\{(f,g)\in\sigma:f,g\in
T\\}\qquad\text{and}\qquad\overline{\sigma}=\\{(\overline{f},\overline{g}):(f,g)\in\sigma\\}.$

Conversely, given a congruence $\xi$ on $T$, we can ‘lift’ it to the
congruence $\xi^{\sharp}$ on $P$ generated by $\xi$. The next lemma
establishes some important connections between these constructions. The first
part will be used frequently without explicit reference.

######  Lemma 4.1.

  1. (i)

For any $\sigma\in\operatorname{\sf Cong}(P)$, we have
$\sigma{\restriction}_{T}=\overline{\sigma}$.

  2. (ii)

For any $\xi\in\operatorname{\sf Cong}(T)$, we have
$\xi=\xi^{\sharp}{\restriction}_{T}$.

###### Proof.

(i). If $(f,g)\in\sigma{\restriction}_{T}$, then $(f,g)\in\sigma$ and $f,g\in
T$, and hence $(f,g)=(\overline{f},\overline{g})\in\overline{\sigma}$. Thus
$\sigma{\restriction}_{T}\subseteq\overline{\sigma}$. For the reverse
inclusion, consider $(\overline{f},\overline{g})\in\overline{\sigma}$, with
$(f,g)\in\sigma$. Then certainly $\overline{f},\overline{g}\in T$, and we also
have $(\overline{f},\overline{g})=(afa,aga)=(a\star f\star a,a\star g\star
a)\in\sigma$, so $(\overline{f},\overline{g})\in\sigma{\restriction}_{T}$.

(ii). This can be proved by noting that $T=a\star P\star a$ is a local monoid
of $P$, and that local monoids have the congruence extension property.
Alternatively, it also follows from Lemma 4.2 below. ∎

Further to part (ii) of the previous lemma, at times we will actually need to
know the exact form that a congruence $\xi^{\sharp}$ takes, depending on the
form of $\xi$ as specified in Theorem 2.6. We now establish the notation for
doing this.

For any $1\leq q\leq r$, group $\mathrel{\mathscr{H}}$-classes in the
$\mathrel{\mathscr{D}}$-classes $D_{q}^{P}(\subseteq P)$ and
$D_{q}^{T}(\subseteq T)$ are isomorphic to $\mathcal{S}_{q}$. Thus, each
normal subgroup $N\unlhd\mathcal{S}_{q}$ gives rise to a congruence on both
$P$ and $T$, as in (2.3). We compress the notation for these congruences as
follows:

$R_{N}^{S}=R_{I_{q-1}^{S},N}=\nabla_{I_{q-1}^{S}}\cup\nu_{N}^{S}\cup\Delta_{S}\qquad\text{where
$S$ stands for either $P$ or $T$.}$

Since $T\leq P$, we have $R_{N}^{T}\subseteq R_{N}^{P}$. More specifically,
one can easily verify that

$R_{N}^{P}{\restriction}_{T}=R_{N}^{T}\qquad\text{for any $1\leq q\leq r$ and
$N\unlhd\mathcal{S}_{q}$.}$

Since $T\cong\mathcal{T}_{r}$, Theorem 2.6 gives

$\operatorname{\sf Cong}(T)=\\{\nabla_{T}\\}\cup\\{R_{N}^{T}:1\leq q\leq r,\
N\unlhd\mathcal{S}_{q}\\}.$

We also abbreviate the notation for the Rees congruences on $P$ and $T$:

$R_{q}^{S}=R_{I_{q}^{S}}=\nabla_{I_{q}^{S}}\cup\Delta_{S}\qquad\text{for each
$0\leq q\leq r$, where again $S$ stands for either $P$ or $T$.}$

Note that $R_{0}^{S}=\Delta_{S}$ and $R_{r}^{S}=\nabla_{S}$. For $0\leq q<r$,
we have $R_{q}^{S}=R_{\\{\operatorname{id}_{q+1}\\}}^{S}$.

######  Lemma 4.2.

If $r\geq 2$, then $\nabla_{T}^{\sharp}=\nabla_{P}$, and
$(R_{N}^{T})^{\sharp}=R_{N}^{P}$ for all $1\leq q\leq r$ and
$N\unlhd\mathcal{S}_{q}$.

###### Proof.

We first prove that

$(R_{q}^{T})^{\sharp}=R_{q}^{P}\qquad\text{for all }0\leq q\leq r,$ (4.3)

and we note that this includes $\nabla_{T}^{\sharp}=\nabla_{P}$. Letting
$\tau=(R_{q}^{T})^{\sharp}$, it is clear that $\tau\subseteq R_{q}^{P}$, so it
remains to show that $R_{q}^{P}\subseteq\tau$. When $q=0$, both relations are
$\Delta_{P}$, so we now assume that $q\geq 1$. Note that
$R_{q}^{T}(\subseteq\tau)$ contains a pair from $D_{q}^{T}\times
D_{1}^{T}(\subseteq D_{q}^{P}\times D_{1}^{P})$. Since $P\star D_{q}^{P}\star
P=I_{q}^{P}$ and $P\star D_{1}^{P}\star P=D_{1}^{P}$, it suffices to show that
all elements of $D_{1}^{P}$ are $\tau$-related; this reasoning is used, and
explained in more detail, in [15, Lemma 2.4]. Now,

$D_{1}^{P}=\\{c_{x}:x\in X\\}\qquad\text{and}\qquad
D_{1}^{T}=\\{c_{x}:x\in\operatorname{im}(a)\\},$

where we write $c_{x}:X\to X$ for the constant map with image $\\{x\\}$. Since
$\nabla_{I_{q}^{T}}\subseteq R_{q}^{T}$ and $q\geq 1$, the elements of
$D_{1}^{T}$ are all $\tau$-related. Now let $x\in X$. Recall that
$a=\big{(}\begin{smallmatrix}A_{1}&A_{2}&\cdots&A_{r}\\\
a_{1}&a_{2}&\cdots&a_{r}\end{smallmatrix}\big{)}$, and without loss of
generality assume that $x\in A_{1}$. Keeping in mind $r\geq 2$, we can
complete the proof of (4.3) by showing that $c_{x}\mathrel{\tau}c_{a_{2}}$. To
do so, let $b=\big{(}\begin{smallmatrix}A_{1}&A_{2}&\cdots&A_{r}\\\
x&a_{2}&\cdots&a_{r}\end{smallmatrix}\big{)}$. Since $a=aba$, it follows that
$\operatorname{rank}(aba)=r=\operatorname{rank}(b)$, and so $b\in P$. But from
$(c_{a_{1}},c_{a_{2}})\in\tau$, it follows that
$(c_{x},c_{a_{2}})=(c_{a_{1}}\star b,c_{a_{2}}\star b)\in\tau$, completing the
proof of (4.3).

Now fix some $1\leq q\leq r$ and $N\unlhd\mathcal{S}_{q}$, and write
$\sigma=(R_{N}^{T})^{\sharp}$. It is clear that

$\sigma\subseteq R_{N}^{P}=\nabla_{I_{q-1}^{P}}\cup\nu_{N}^{P}\cup\Delta_{P},$
(4.4)

and we need to show that $R_{N}^{P}\subseteq\sigma$. From (4.4) we have

$\sigma=\sigma{\restriction}_{I_{q-1}^{P}}\cup\sigma{\restriction}_{D_{q}^{P}}\cup\Delta_{P},$
(4.5)

We will complete the proof by showing that

$\sigma\supseteq\nabla_{I_{q-1}^{P}}\qquad\text{and}\qquad\sigma\supseteq\nu_{N}^{P}.$

The first follows from (4.3), as
$\sigma=(R_{N}^{T})^{\sharp}\supseteq(R_{q-1}^{T})^{\sharp}=R_{q-1}^{P}\supseteq\nabla_{I_{q-1}^{P}}$.
For the second, we first observe from (4.4) and (4.5) that
$\sigma{\restriction}_{D_{q}^{P}}\subseteq\nu_{N}^{P}\subseteq{\mathrel{\mathscr{H}}^{P}}{\restriction}_{D_{q}^{P}}$.
Since $D_{q}^{P}$ is stable and regular, it follows from Lemma 2.4, writing
$e$ for any idempotent in $D_{q}^{T}(\subseteq D_{q}^{P})$, that

$\sigma{\restriction}_{D_{q}^{P}}=\sigma\cap{{\mathrel{\mathscr{H}}^{P}}{\restriction}_{D_{q}^{P}}}=\nu_{N^{\prime}}^{P},\qquad\text{where}\qquad
N^{\prime}=\\{g\in H_{e}^{P}:(e,g)\in\sigma\\}.$

As explained just before Lemma 2.4, we can also assume that $N\subseteq
H_{e}^{P}(=H_{e}^{T})$. Now, for any $g\in N$ we have
$(e,g)\in\nu_{N}^{T}\subseteq R_{N}^{T}\subseteq\sigma$, so that $g\in
N^{\prime}$. This shows that $N\subseteq N^{\prime}$, and so
$\nu_{N}^{P}\subseteq\nu_{N^{\prime}}^{P}\subseteq\sigma$, completing the
proof. ∎

The equality $\nabla_{T}^{\sharp}=\nabla_{P}$ in Lemma 4.2 does not hold for
$r=1$. Indeed, when $r=1$ we have $\nabla_{T}=\Delta_{T}$ (cf. Remark 3.3), so
that $\nabla_{T}^{\sharp}=\Delta_{P}\not=\nabla_{P}$ (unless $|X|=1$). The
$(R_{N}^{T})^{\sharp}=R_{N}^{P}$ part of the lemma does hold for $r=1$, but
simply says $\Delta_{T}^{\sharp}=\Delta_{P}$.

###  4.2 Interactions between congruences and the
$\widehat{\mathrel{\mathscr{H}}}^{P}$-relation

######  Lemma 4.6.

Let $\sigma\in\operatorname{\sf Cong}(P)$, and suppose
$(f,g)\in\sigma\cap{\mathrel{\mathchoice{\accentset{\displaystyle\text{\smash{\raisebox{-5.59721pt}{$\widehatsym$}}}}{\mathscr{H}}}{\accentset{\textstyle\text{\smash{\raisebox{-5.59721pt}{$\widehatsym$}}}}{\mathscr{H}}}{\accentset{\scriptstyle\text{\smash{\raisebox{-3.91806pt}{$\widehatsym$}}}}{\mathscr{H}}}{\accentset{\scriptscriptstyle\text{\smash{\raisebox{-2.7986pt}{$\widehatsym$}}}}{\mathscr{H}}}}^{P}}$.
Then for any idempotent $e\in L_{f}^{P}$ we have $(f,g\star e)\in\sigma$ and
$g\star e\in L_{f}^{P}\cap R_{g}^{P}$.

###### Proof.

From $e\in L_{f}^{P}$ and $f\mathrel{\sigma}g$, we have $f=f\star
e\mathrel{\sigma}g\star e$. We also note that

$g\mathrel{\mathchoice{\accentset{\displaystyle\text{\smash{\raisebox{-5.59721pt}{$\widehatsym$}}}}{\mathscr{H}}}{\accentset{\textstyle\text{\smash{\raisebox{-5.59721pt}{$\widehatsym$}}}}{\mathscr{H}}}{\accentset{\scriptstyle\text{\smash{\raisebox{-3.91806pt}{$\widehatsym$}}}}{\mathscr{H}}}{\accentset{\scriptscriptstyle\text{\smash{\raisebox{-2.7986pt}{$\widehatsym$}}}}{\mathscr{H}}}}^{P}f\mathrel{\mathscr{L}}^{P}e\
\Rightarrow\
g\mathrel{\mathchoice{\accentset{\displaystyle\text{\smash{\raisebox{-5.59721pt}{$\widehatsym$}}}}{\mathscr{L}}}{\accentset{\textstyle\text{\smash{\raisebox{-5.59721pt}{$\widehatsym$}}}}{\mathscr{L}}}{\accentset{\scriptstyle\text{\smash{\raisebox{-3.91806pt}{$\widehatsym$}}}}{\mathscr{L}}}{\accentset{\scriptscriptstyle\text{\smash{\raisebox{-2.7986pt}{$\widehatsym$}}}}{\mathscr{L}}}}^{P}e\
\Rightarrow\ \overline{g}\mathrel{\mathscr{L}}^{T}\overline{e}\ \Rightarrow\
\overline{g}=\overline{g}\star\overline{e}=\overline{g\star e}\ \Rightarrow\
g\mathrel{\mathchoice{\accentset{\displaystyle\text{\smash{\raisebox{-5.59721pt}{$\widehatsym$}}}}{\mathscr{H}}}{\accentset{\textstyle\text{\smash{\raisebox{-5.59721pt}{$\widehatsym$}}}}{\mathscr{H}}}{\accentset{\scriptstyle\text{\smash{\raisebox{-3.91806pt}{$\widehatsym$}}}}{\mathscr{H}}}{\accentset{\scriptscriptstyle\text{\smash{\raisebox{-2.7986pt}{$\widehatsym$}}}}{\mathscr{H}}}}^{P}g\star
e\ \Rightarrow\ g\mathrel{\mathscr{D}}^{P}g\star e.$

It follows from stability that $g\mathrel{\mathscr{R}}^{P}g\star e$. Since
$e\mathrel{\mathscr{L}}^{P}f\mathrel{\mathchoice{\accentset{\displaystyle\text{\smash{\raisebox{-5.59721pt}{$\widehatsym$}}}}{\mathscr{H}}}{\accentset{\textstyle\text{\smash{\raisebox{-5.59721pt}{$\widehatsym$}}}}{\mathscr{H}}}{\accentset{\scriptstyle\text{\smash{\raisebox{-3.91806pt}{$\widehatsym$}}}}{\mathscr{H}}}{\accentset{\scriptscriptstyle\text{\smash{\raisebox{-2.7986pt}{$\widehatsym$}}}}{\mathscr{H}}}}^{P}g\mathrel{\mathscr{D}}^{P}g\star
e$, it follows that $g\star e\mathrel{\mathscr{D}}^{P}e$, and this time
stability gives $g\star
e\mathrel{\mathscr{L}}^{P}e\mathrel{\mathscr{L}}^{P}f$. The last two
conclusions give $g\star e\in R_{g}^{P}\cap L_{f}^{P}$.∎

######  Lemma 4.7.

Let $\sigma\in\operatorname{\sf Cong}(P)$, and suppose $\sigma\cap(H\times
H^{\prime})\not=\varnothing$ for a pair of $\mathrel{\mathscr{H}}^{P}$-classes
$H$ and $H^{\prime}$ contained in a common
$\mathrel{\mathchoice{\accentset{\displaystyle\text{\smash{\raisebox{-5.59721pt}{$\widehatsym$}}}}{\mathscr{H}}}{\accentset{\textstyle\text{\smash{\raisebox{-5.59721pt}{$\widehatsym$}}}}{\mathscr{H}}}{\accentset{\scriptstyle\text{\smash{\raisebox{-3.91806pt}{$\widehatsym$}}}}{\mathscr{H}}}{\accentset{\scriptscriptstyle\text{\smash{\raisebox{-2.7986pt}{$\widehatsym$}}}}{\mathscr{H}}}}^{P}$-class.
Then for every $h\in H$, we have $(h,h^{\prime})\in\sigma$, where $h^{\prime}$
is the unique element of $H^{\prime}$ with
$\overline{h}^{\prime}=\overline{h}$.

###### Proof.

Fix some $(f,g)\in\sigma\cap(H\times H^{\prime})$, and note that $H=H_{f}^{P}$
and $H^{\prime}=H_{g}^{P}$. Let $e$ be any idempotent in $L_{f}^{P}$. Lemma
4.6 tells us that $g\star e$ is in $L_{f}^{P}\cap R_{g}^{P}$ and is
$\sigma$-related to both $f$ and $g$. It therefore suffices to prove the
current lemma in the case that $f$ and $g$ are $\mathrel{\mathscr{R}}^{P}$\-
or $\mathrel{\mathscr{L}}^{P}$-related. We assume that
$f\mathrel{\mathscr{R}}^{P}g$, with the other case being dual.

We distinguish two cases, depending on whether
$\widehat{H}_{f}^{P}=\widehat{H}_{g}^{P}$ is a rectangular group or not.

Case 1. Suppose first that $\widehat{H}_{f}^{P}=\widehat{H}_{g}^{P}$ is a
rectangular group. Let $e$ and $e^{\prime}$ denote the idempotents in
$H_{f}^{P}$ and $H_{g}^{P}$ respectively. Raising $(f,g)\in\sigma$ to an
appropriately large power yields $(e,e^{\prime})\in\sigma$. Since these
idempotents are
$\mathrel{\mathchoice{\accentset{\displaystyle\text{\smash{\raisebox{-5.59721pt}{$\widehatsym$}}}}{\mathscr{H}}}{\accentset{\textstyle\text{\smash{\raisebox{-5.59721pt}{$\widehatsym$}}}}{\mathscr{H}}}{\accentset{\scriptstyle\text{\smash{\raisebox{-3.91806pt}{$\widehatsym$}}}}{\mathscr{H}}}{\accentset{\scriptscriptstyle\text{\smash{\raisebox{-2.7986pt}{$\widehatsym$}}}}{\mathscr{H}}}}^{P}$-related,
we also have $\overline{e}=\overline{e}^{\prime}$. Since $h=h\star e$, it
follows from Green’s Lemma that the element $h^{\prime}=h\star e^{\prime}$
belongs to $H_{e^{\prime}}^{P}=H_{g}^{P}$. We also have
$(h,h^{\prime})=(h\star e,h\star e^{\prime})\in\sigma$, and
$\overline{h}=\overline{h}\star\overline{e}=\overline{h}\star\overline{e}^{\prime}=\overline{h}^{\prime}$.

Case 2. Now suppose $\widehat{H}_{f}^{P}=\widehat{H}_{g}^{P}$ is not a
rectangular group. Choose any $f^{\prime}\in L_{f}^{P}$ whose
$\mathrel{\mathchoice{\accentset{\displaystyle\text{\smash{\raisebox{-5.59721pt}{$\widehatsym$}}}}{\mathscr{H}}}{\accentset{\textstyle\text{\smash{\raisebox{-5.59721pt}{$\widehatsym$}}}}{\mathscr{H}}}{\accentset{\scriptstyle\text{\smash{\raisebox{-3.91806pt}{$\widehatsym$}}}}{\mathscr{H}}}{\accentset{\scriptscriptstyle\text{\smash{\raisebox{-2.7986pt}{$\widehatsym$}}}}{\mathscr{H}}}}^{P}$-class
is a rectangular group, and pick any $b,c\in P$ such that $b\star
f=f^{\prime}$ and $c\star f^{\prime}=f$. By Green’s Lemma the maps

$R_{f}^{P}\to R_{f^{\prime}}^{P}:u\mapsto b\star u\qquad\text{and}\qquad
R_{f^{\prime}}^{P}\to R_{f}^{P}:v\mapsto c\star v$

are mutually inverse $\mathrel{\mathscr{L}}^{P}$-preserving bijections. In
particular, the element $g^{\prime}=b\star g$ is
$\mathrel{\mathscr{R}}^{P}$-related to $f^{\prime}$, and we have
$(f^{\prime},g^{\prime})=(b\star f,b\star g)\in\sigma$ and
$g^{\prime}\mathrel{\mathscr{L}}^{P}g\mathrel{\mathchoice{\accentset{\displaystyle\text{\smash{\raisebox{-5.59721pt}{$\widehatsym$}}}}{\mathscr{L}}}{\accentset{\textstyle\text{\smash{\raisebox{-5.59721pt}{$\widehatsym$}}}}{\mathscr{L}}}{\accentset{\scriptstyle\text{\smash{\raisebox{-3.91806pt}{$\widehatsym$}}}}{\mathscr{L}}}{\accentset{\scriptscriptstyle\text{\smash{\raisebox{-2.7986pt}{$\widehatsym$}}}}{\mathscr{L}}}}^{P}f\mathrel{\mathscr{L}}^{P}f^{\prime}$,
which together with $g^{\prime}\mathrel{\mathscr{R}}^{P}f^{\prime}$ implies
$(f^{\prime},g^{\prime})\in{\mathrel{\mathchoice{\accentset{\displaystyle\text{\smash{\raisebox{-5.59721pt}{$\widehatsym$}}}}{\mathscr{H}}}{\accentset{\textstyle\text{\smash{\raisebox{-5.59721pt}{$\widehatsym$}}}}{\mathscr{H}}}{\accentset{\scriptstyle\text{\smash{\raisebox{-3.91806pt}{$\widehatsym$}}}}{\mathscr{H}}}{\accentset{\scriptscriptstyle\text{\smash{\raisebox{-2.7986pt}{$\widehatsym$}}}}{\mathscr{H}}}}^{P}}$.
Case 1 therefore applies, and tells us that the element $d=b\star h\in
H_{f^{\prime}}^{P}$ is $\sigma$-related to the unique element $d^{\prime}\in
H_{g^{\prime}}^{P}$ with $\overline{d}=\overline{d}^{\prime}$. Now set
$h^{\prime}=c\star d^{\prime}$, noting that this belongs to $H_{g}^{P}$. We
then have $(h,h^{\prime})=(c\star d,c\star d^{\prime})\in\sigma$, and
$\overline{h}=\overline{c}\star\overline{d}=\overline{c}\star\overline{d}^{\prime}=\overline{h}^{\prime}$.
∎

##  5 A subdirect decomposition of $\operatorname{\sf Cong}(P)$

In this section we prove part (i) of Theorem 3.2, which is subsumed in the
following. Here we recall that $T\cong\mathcal{T}_{r}$, and analogously to the
rank parameters in (3.1) we write

$\operatorname{rank}(\xi)=\max\\{q:R_{q}^{T}\subseteq\xi\\}\qquad\text{for
$\xi\in\operatorname{\sf Cong}(T)$.}$ (5.1)

######  Theorem 5.2.

For $r\geq 2$, the mapping

$\operatorname{\sf Cong}(P)\rightarrow\operatorname{\sf
Cong}(T)\times[\Delta_{P},\kappa]:\sigma\mapsto(\sigma{\restriction}_{T},\sigma\cap\kappa)$

is a subdirect embedding of lattices, with image

$\big{\\{}(\xi,\theta)\in\operatorname{\sf
Cong}(T)\times[\Delta_{P},\kappa]:\operatorname{rank}(\xi)\leq\operatorname{rank}(\theta)\big{\\}}.$

###### Proof.

Since $T$ is a subsemigroup of $P$, and $\kappa$ a congruence of $P$, we have
two well-defined mappings

$\Xi:\operatorname{\sf Cong}(P)\to\operatorname{\sf
Cong}(T):\sigma\mapsto\sigma{\restriction}_{T}\qquad\text{and}\qquad\Theta:\operatorname{\sf
Cong}(P)\to[\Delta_{P},\kappa]:\sigma\mapsto\sigma\cap\kappa.$ (5.3)

By Proposition 2.12, we can show that these induce the stated subdirect
embedding by showing that:

  * •

$\Xi$ and $\Theta$ are lattice surmorphisms (Lemma 5.11), and

  * •

$\ker(\Xi)\cap\ker(\Theta)=\Delta_{\operatorname{\sf Cong}(P)}$ (Corollary
5.7).

Lemmas 5.8, 5.9 and 5.10 combine to show that the image of the embedding is as
stated. ∎

We now set off towards establishing these lemmas, beginning with the following
key observation. Throughout this section we assume that $r\geq 2$, even though
many of the results and proofs are valid (albeit trivial) for $r=1$.

######  Proposition 5.4.

For any $\sigma\in\operatorname{\sf Cong}(P)$ we have
$\sigma=\Xi(\sigma)^{\sharp}\vee\Theta(\sigma)$.

###### Proof.

Throughout the proof we write
$\xi=\Xi(\sigma)^{\sharp}=\sigma{\restriction}_{T}^{\sharp}$ and
$\theta=\Theta(\sigma)=\sigma\cap\kappa$. Since $\xi,\theta\subseteq\sigma$,
we of course have $\xi\vee\theta\subseteq\sigma$. For the reverse inclusion,
fix some $(f,g)\in\sigma$. We must show that $(f,g)\in\xi\vee\theta$. Since
$\sigma{\restriction}_{T}\in\operatorname{\sf Cong}(T)$, we have

$\sigma{\restriction}_{T}=\nabla_{T}\qquad\text{or}\qquad\sigma{\restriction}_{T}=R_{N}^{T}=\nabla_{I_{q-1}^{T}}\cup\nu_{N}^{T}\cup\Delta_{T}\qquad\text{for
some $1\leq q\leq r$, and some $N\unlhd\mathcal{S}_{q}$.}$ (5.5)

In the first case, we have $\xi=\nabla_{T}^{\sharp}=\nabla_{P}$ by Lemma 4.2,
so certainly $(f,g)\in\xi\vee\theta$. For the rest of the proof, we assume
that $\sigma{\restriction}_{T}=R_{N}^{T}$, as in (5.5), so that
$\xi=R_{N}^{P}$ by Lemma 4.2. We now split the proof into cases, according to
whether the pair $(\overline{f},\overline{g})\in\sigma{\restriction}_{T}$
belongs to $\Delta_{T}$, $\nabla_{I_{q-1}^{T}}$ or $\nu_{N}^{T}$; cf. (5.5).

Case 1. If $(\overline{f},\overline{g})\in\Delta_{T}$, then
$\overline{f}=\overline{g}$, i.e. $(f,g)\in\kappa$. But then
$(f,g)\in\sigma\cap\kappa=\theta\subseteq\xi\vee\theta$.

Case 2. If $(\overline{f},\overline{g})\in\nabla_{I_{q-1}^{T}}$, then
$\operatorname{rank}(f)=\operatorname{rank}(\overline{f})\leq q-1$, and
similarly $\operatorname{rank}(g)\leq q-1$. But then

$(f,g)\in\nabla_{I_{q-1}^{P}}\subseteq R_{N}^{P}=\xi\subseteq\xi\vee\theta.$

Case 3. Finally, suppose $(\overline{f},\overline{g})\in\nu_{N}^{T}$. Since
$\nu_{N}^{T}\subseteq{\mathrel{\mathscr{H}}^{T}}$, it follows that
$\overline{f}\mathrel{\mathscr{H}}^{T}\overline{g}$, i.e. that
$f\mathrel{\mathchoice{\accentset{\displaystyle\text{\smash{\raisebox{-5.59721pt}{$\widehatsym$}}}}{\mathscr{H}}}{\accentset{\textstyle\text{\smash{\raisebox{-5.59721pt}{$\widehatsym$}}}}{\mathscr{H}}}{\accentset{\scriptstyle\text{\smash{\raisebox{-3.91806pt}{$\widehatsym$}}}}{\mathscr{H}}}{\accentset{\scriptscriptstyle\text{\smash{\raisebox{-2.7986pt}{$\widehatsym$}}}}{\mathscr{H}}}}^{P}g$.
By Lemma 4.7 (with $H=H_{f}^{P}$, $H^{\prime}=H_{g}^{P}$ and $h=f$), we have
$(f,f^{\prime})\in\sigma$, where $f^{\prime}$ is the unique element of
$H_{g}^{P}$ with $\overline{f}=\overline{f}^{\prime}$. But this means that in
fact $(f,f^{\prime})\in\sigma\cap\kappa=\theta$. We also have
$(f^{\prime},g)\in\sigma$ by transitivity, and we have
$(f^{\prime},g)\in{\mathrel{\mathscr{H}}^{P}}$ (as $f^{\prime}\in H_{g}^{P}$).
Since
$(\overline{f}^{\prime},\overline{g})=(\overline{f},\overline{g})\in\nu_{N}^{T}$,
it follows that $(f^{\prime},g)\in\nu_{N}^{P}\subseteq R_{N}^{P}=\xi$. But
then $f\mathrel{\theta}f^{\prime}\mathrel{\xi}g$, so that
$(f,g)\in\xi\vee\theta$. ∎

######  Remark 5.6.

Examining the final line of the three cases above, we showed that in fact the
pair $(f,g)\in\sigma$ belongs to $\theta\circ\xi$. Thus, any congruence
$\sigma\in\operatorname{\sf Cong}(P)$ satisfies
$\sigma=\Xi(\sigma)^{\sharp}\circ\Theta(\sigma)=\Theta(\sigma)\circ\Xi(\sigma)^{\sharp}$.

Proposition 5.4 has the following immediate consequence.

######  Corollary 5.7.

$\ker(\Xi)\cap\ker(\Theta)=\Delta_{\operatorname{\sf Cong}(P)}$. ∎

We now bring in the rank parameters associated to congruences from
$\operatorname{\sf Cong}(T)$ and $[\Delta_{P},\kappa]$, defined in (3.1) and
(5.1).

######  Lemma 5.8.

If $\sigma\in\operatorname{\sf Cong}(P)$, then with $\xi=\Xi(\sigma)$ and
$\theta=\Theta(\sigma)$ we have
$\operatorname{rank}(\xi)\leq\operatorname{rank}(\theta)$.

###### Proof.

Write $q=\operatorname{rank}(\xi)$. By Lemma 4.2 we have
$R_{q}^{P}=(R_{q}^{T})^{\sharp}\subseteq\xi^{\sharp}\subseteq\sigma$. It then
follows that $\kappa\cap R_{q}^{P}\subseteq\kappa\cap\sigma=\theta$, which
gives $\operatorname{rank}(\theta)\geq q=\operatorname{rank}(\xi)$. ∎

Our next goal is to establish a converse of Lemma 5.8. Namely, we will show
that if $\xi\in\operatorname{\sf Cong}(T)$ and $\theta\in[\Delta_{P},\kappa]$
satisfy $\operatorname{rank}(\xi)\leq\operatorname{rank}(\theta)$, then with
$\sigma=\xi^{\sharp}\vee\theta\in\operatorname{\sf Cong}(P)$ we have
$\xi=\Xi(\sigma)$ and $\theta=\Theta(\sigma)$. We prove the claims regarding
$\xi$ and $\theta$ in the following two lemmas; for the first, we do not in
fact need the assumption
$\operatorname{rank}(\xi)\leq\operatorname{rank}(\theta)$:

######  Lemma 5.9.

If $\xi\in\operatorname{\sf Cong}(T)$ and $\theta\in[\Delta_{P},\kappa]$, then
with $\sigma=\xi^{\sharp}\vee\theta$ we have $\xi=\Xi(\sigma)$.

###### Proof.

Recall that $\Xi(\sigma)=\sigma{\restriction}_{T}$. Certainly
$\xi\subseteq\sigma{\restriction}_{T}$. For the reverse inclusion, suppose
$(f,g)\in\sigma{\restriction}_{T}$; we must show that $(f,g)\in\xi$. By
assumption we have $f,g\in T$ and $(f,g)\in\sigma=\xi^{\sharp}\vee\theta$. It
follows that there is a sequence $f=f_{0}\to f_{1}\to\cdots\to f_{k}=g$, where
each $(f_{i},f_{i+1})\in\xi^{\sharp}\cup\theta$. Since $f,g\in T$, we have
$f=\overline{f}=\overline{f}_{0}$ and $g=\overline{g}=\overline{f}_{k}$, so we
can complete the proof that $(f,g)\in\xi$ by showing that
$(\overline{f}_{i},\overline{f}_{i+1})\in\xi$ for each $0\leq i<k$. But for
any such $i$, we have

$(\overline{f}_{i},\overline{f}_{i+1})=(a\star f_{i}\star a,a\star
f_{i+1}\star a)\in\xi^{\sharp}\cup\theta,$

as $\xi^{\sharp}$ and $\theta$ are both compatible. In fact, since
$\overline{f}_{i},\overline{f}_{i+1}\in T$, we have

$(\overline{f}_{i},\overline{f}_{i+1})\in\xi^{\sharp}{\restriction}_{T}\cup\theta{\restriction}_{T}=\xi\cup\Delta_{T}=\xi,$

where we used Lemma 4.1(ii) and
$\theta{\restriction}_{T}\subseteq\kappa{\restriction}_{T}=\Delta_{T}$ in the
second step. ∎

######  Lemma 5.10.

If $\xi\in\operatorname{\sf Cong}(T)$ and $\theta\in[\Delta_{P},\kappa]$
satisfy $\operatorname{rank}(\xi)\leq\operatorname{rank}(\theta)$, then with
$\sigma=\xi^{\sharp}\vee\theta$ we have $\theta=\Theta(\sigma)$.

###### Proof.

Recall that $\Theta(\sigma)=\sigma\cap\kappa$. For the duration of the proof
we write $q=\operatorname{rank}(\xi)\leq\operatorname{rank}(\theta)$. Since
$\theta\subseteq\sigma$ and $\theta\subseteq\kappa$, we certainly have
$\theta\subseteq\sigma\cap\kappa$, so we are left to establish the reverse
containment. This is trivial in the case $q=r$, as then
$\operatorname{rank}(\theta)=r$, and so
$\theta=\kappa\supseteq\sigma\cap\kappa$. Thus, for the rest of the proof we
assume that $q<r$, and we fix some $(f,g)\in\sigma\cap\kappa$; we must show
that $(f,g)\in\theta$.

Since $\operatorname{rank}(\xi)=q<r$, we have $\xi=R_{N}^{T}$ for some
$N\unlhd\mathcal{S}_{q+1}$. Since
$(\overline{f},\overline{g})\in\sigma{\restriction}_{T}=\Xi(\sigma)=\xi$ (by
Lemma 5.9), it follows from the form of $\xi=R_{N}^{T}$ that either
$\overline{f},\overline{g}\in I_{q}^{T}$ or else
$\overline{f},\overline{g}\not\in I_{q}^{T}$, and in the latter case we have
$\operatorname{rank}(\overline{f})=\operatorname{rank}(\overline{g})$ and
$\overline{f}\mathrel{\mathscr{H}}^{T}\overline{g}$. Since
$\operatorname{rank}(f)=\operatorname{rank}(\overline{f})$ and
$\operatorname{rank}(g)=\operatorname{rank}(\overline{g})$, it follows that
either $f,g\in I_{q}^{P}$ or else $f,g\not\in I_{q}^{P}$, and in the latter
case we have $\operatorname{rank}(f)=\operatorname{rank}(g)$ and
${f\mathrel{\mathchoice{\accentset{\displaystyle\text{\smash{\raisebox{-5.59721pt}{$\widehatsym$}}}}{\mathscr{H}}}{\accentset{\textstyle\text{\smash{\raisebox{-5.59721pt}{$\widehatsym$}}}}{\mathscr{H}}}{\accentset{\scriptstyle\text{\smash{\raisebox{-3.91806pt}{$\widehatsym$}}}}{\mathscr{H}}}{\accentset{\scriptscriptstyle\text{\smash{\raisebox{-2.7986pt}{$\widehatsym$}}}}{\mathscr{H}}}}^{P}g}$.

Case 1. Suppose first that $f,g\in I_{q}^{P}$. Together with the fact that
$(f,g)\in\kappa$, it follows that

$(f,g)\in\kappa\cap R_{q}^{P}\subseteq\theta,$

where in the last step we used the fact that $\operatorname{rank}(\theta)\geq
q$.

Case 2. Now suppose $f,g\not\in I_{q}^{P}$, and let
$p=\operatorname{rank}(f)=\operatorname{rank}(g)$. Since
$(f,g)\in\sigma=\xi^{\sharp}\vee\theta$, there is a sequence $f=f_{0}\to
f_{1}\to\cdots\to f_{k}=g$, where each
$(f_{i},f_{i+1})\in\xi^{\sharp}\cup\theta$. Now consider the sequence of
$\overline{f}_{i}$ maps:
$\overline{f}=\overline{f}_{0}\to\overline{f}_{1}\to\cdots\to\overline{f}_{k}=\overline{g}$.
For each $i$ we have
$(f,f_{i})\in(\xi^{\sharp}\cup\theta)^{\sharp}=\xi^{\sharp}\vee\theta=\sigma$,
so $(\overline{f},\overline{f}_{i})\in\sigma{\restriction}_{T}=\xi=R_{N}^{T}$
by Lemma 5.9. Since
${\operatorname{rank}(\overline{f})=\operatorname{rank}(f)=p>q=\operatorname{rank}(\xi)}$,
we have $p=\operatorname{rank}(\overline{f}_{i})=\operatorname{rank}(f_{i})$
for all $i$. We also have
$\overline{f}\mathrel{\mathscr{H}}^{T}\overline{f}_{i}$, and hence
$f\mathrel{\mathchoice{\accentset{\displaystyle\text{\smash{\raisebox{-5.59721pt}{$\widehatsym$}}}}{\mathscr{H}}}{\accentset{\textstyle\text{\smash{\raisebox{-5.59721pt}{$\widehatsym$}}}}{\mathscr{H}}}{\accentset{\scriptstyle\text{\smash{\raisebox{-3.91806pt}{$\widehatsym$}}}}{\mathscr{H}}}{\accentset{\scriptscriptstyle\text{\smash{\raisebox{-2.7986pt}{$\widehatsym$}}}}{\mathscr{H}}}}^{P}f_{i}$
for all $i$.

For each $0\leq i\leq k$, let $h_{i}$ be the unique element of $H_{f_{i}}^{P}$
such that $\overline{h}_{i}=\overline{f}$. Since $\overline{f}=\overline{g}$
(as $(f,g)\in\kappa$), we have $h_{0}=f_{0}=f$ and $h_{k}=f_{k}=g$, so it
suffices to show that $(h_{i},h_{i+1})\in\theta$ for all $0\leq i<k$. This
follows from Lemma 4.7 in the case that $(f_{i},f_{i+1})\in\theta$. Keeping
$(f_{i},f_{i+1})\in\xi^{\sharp}\cup\theta$ in mind, it remains to consider the
case in which $(f_{i},f_{i+1})\in\xi^{\sharp}=R_{N}^{P}$. Since
$\operatorname{rank}(f_{i})=\operatorname{rank}(f_{i+1})=p>q$, it follows from
the form of $\xi^{\sharp}=R_{N}^{P}$ that
$f_{i}\mathrel{\mathscr{H}}^{P}f_{i+1}$, i.e. that
$H_{f_{i}}^{P}=H_{f_{i+1}}^{P}$. It follows that $h_{i}=h_{i+1}$ in this case,
so certainly $(h_{i},h_{i+1})\in\theta$. ∎

Here is the final missing piece of the proof of Theorem 5.2.

######  Lemma 5.11.

$\Xi$ and $\Theta$ are lattice surmorphisms.

###### Proof.

Surjectivity of $\Xi$ follows from Lemma 4.1(ii), which says that
$\Xi(\xi^{\sharp})=\xi$ for all $\xi\in\operatorname{\sf Cong}(T)$.
Surjectivity of $\Theta$ follows from the fact that $\Theta(\theta)=\theta$
for all $\theta\in[\Delta_{P},\kappa](\subseteq\operatorname{\sf Cong}(P))$.

It remains to show that both maps are lattice morphisms. To do so, let
$\sigma_{1},\sigma_{2}\in\operatorname{\sf Cong}(P)$, and write
$\xi_{i}=\Xi(\sigma_{i})$ and $\theta_{i}=\Theta(\sigma_{i})$ for $i=1,2$. We
need to show that

  1.   2. (i)

$\Xi(\sigma_{1}\cap\sigma_{2})=\xi_{1}\cap\xi_{2}$,

  3. (ii)

$\Xi(\sigma_{1}\vee\sigma_{2})=\xi_{1}\vee\xi_{2}$,

  4. (iii)

$\Theta(\sigma_{1}\cap\sigma_{2})=\theta_{1}\cap\theta_{2}$,

  5. (iv)

$\Theta(\sigma_{1}\vee\sigma_{2})=\theta_{1}\vee\theta_{2}$.

Items (i) and (iii) follow quickly from the fact that $\Xi$ and $\Theta$ are
defined in terms of intersections, namely
$\Xi(\sigma)=\sigma{\restriction}_{T}=\sigma\cap(T\times T)$ and
$\Theta(\sigma)=\sigma\cap\kappa$.

For (ii) and (iv), we may assume without loss of generality that
$\xi_{1}\subseteq\xi_{2}$, as $\operatorname{\sf Cong}(T)$ is a chain. Since
then $\xi_{1}^{\sharp}\subseteq\xi_{2}^{\sharp}$, it follows that
$\xi_{1}^{\sharp}\vee\xi_{2}^{\sharp}=\xi_{2}^{\sharp}=(\xi_{1}\vee\xi_{2})^{\sharp}$.
Combining this with Proposition 5.4 gives

$\sigma_{1}\vee\sigma_{2}=(\xi_{1}^{\sharp}\vee\theta_{1})\vee(\xi_{2}^{\sharp}\vee\theta_{2})=(\xi_{1}\vee\xi_{2})^{\sharp}\vee(\theta_{1}\vee\theta_{2}),$
(5.12)

with $\xi_{1}\vee\xi_{2}\in\operatorname{\sf Cong}(T)$ and
$\theta_{1}\vee\theta_{2}\in[\Delta_{P},\kappa]$. Item (ii) now follows
immediately from Lemma 5.9. Next we note that

$\displaystyle\operatorname{rank}(\xi_{1}\vee\xi_{2})$
$\displaystyle=\operatorname{rank}(\xi_{2})$ as $\xi_{1}\subseteq\xi_{2}$
$\displaystyle\leq\operatorname{rank}(\theta_{2})$ by Lemma 5.8
$\displaystyle\leq\operatorname{rank}(\theta_{1}\vee\theta_{2})$ by
definition, as $\theta_{2}\subseteq\theta_{1}\vee\theta_{2}$.

Item (iv) now follows from (5.12) and Lemma 5.10 ∎

######  Remark 5.13.

One can use Theorem 5.2 to give a schematic diagram of the lattice
$\operatorname{\sf Cong}(P)$. First, we identify this lattice with its image
in $\operatorname{\sf Cong}(T)\times[\Delta_{P},\kappa]$, which we will denote
by $\Lambda$. We then break up $\Lambda$ into what we will call _layers_. Each
such layer is a sublattice consisting of all pairs with a fixed first
coordinate:

$\Lambda_{\xi}=\\{(\xi,\theta):\theta\in[\Delta_{P},\kappa],\
\operatorname{rank}(\theta)\geq q\\}\qquad\text{for $\xi\in\operatorname{\sf
Cong}(T)$ with $q=\operatorname{rank}(\xi)$}.$

Note that for such $\xi$ we have

$\Lambda_{\xi}\cong[\kappa_{q},\kappa],\qquad\text{where}\qquad\kappa_{q}=\kappa\cap
R_{q}^{P}.$

These layers are then stacked on top of each other in the order

$\Lambda_{\Delta_{T}}<\Lambda_{R_{1}}<\Lambda_{R_{\mathcal{S}_{2}}}<\Lambda_{R_{2}}<\cdots<\Lambda_{\nabla_{T}}.$

The stacking of two consecutive layers $\Lambda_{\xi_{1}}<\Lambda_{\xi_{2}}$
is such that every element $(\xi_{2},\theta)$ of $\Lambda_{\xi_{2}}$ covers
the corresponding element $(\xi_{1},\theta)$ of $\Lambda_{\xi_{1}}$. This is
illustrated in Figure 4, in the case $r=3$.

Note that Figure 3 shows a special case of this, when $X=\\{1,2,3,4\\}$, and
$a=\big{(}\begin{smallmatrix}1&2&3&4\\\ 1&2&3&3\end{smallmatrix}\big{)}$. The
red and blue vertices are included in both figures to show the matching of
certain congruences of $\mathcal{T}_{X}^{a}$ (in Figure 3) with their
corresponding pairs from $\operatorname{\sf Cong}(T)\times[\Delta_{P},\kappa]$
(in Figure 4). Specifically, the blue and red vertices in Figure 3 correspond
to the bottom and top elements of the layers, i.e. to the congruences
$\xi^{\sharp}\vee\kappa_{q}$ and $\xi^{\sharp}\vee\kappa$, respectively, where
$q=\operatorname{rank}(\xi)$. See also Remark 7.12 and Figure 5.

$\kappa=\kappa_{3}$$\kappa_{2}$$\kappa_{1}$$\Delta_{P}=\kappa_{0}$$(\Delta_{T},\kappa)$$(R_{1},\kappa)$$(R_{\mathcal{S}_{2}},\kappa)$$(R_{2},\kappa)$$(R_{\mathcal{A}_{3}},\kappa)$$(R_{\mathcal{S}_{3}},\kappa)$${(\nabla_{T},\kappa)}$$(\Delta_{P},\kappa_{0})$$(R_{1},\kappa_{1})$$(R_{\mathcal{S}_{2}},\kappa_{1})$$(R_{2},\kappa_{2})$$(R_{\mathcal{A}_{3}},\kappa_{2})$${(R_{\mathcal{S}_{3}},\kappa_{2})}$$(\Delta_{P},\kappa_{1})$${(R_{\mathcal{S}_{2}},\kappa_{2})}$

Figure 4: Structure of the lattice $\operatorname{\sf Cong}(P)$ when
$\operatorname{rank}(a)=3$, as discussed in Remark 5.13. The left-hand side
represents the interval $[\Delta_{P},\kappa]$, and its distingushed
congruences $\kappa_{q}=\kappa\cap R_{q}^{P}$. The right-hand side indicates
the stacking of layers.

##  6 A direct decomposition of the interval $[\Delta_{P},\kappa]$

We have now decomposed $\operatorname{\sf Cong}(P)$ as a subdirect product of
$\operatorname{\sf Cong}(\mathcal{T}_{r})$ and the interval
$[\Delta_{P},\kappa]$ in $\operatorname{\sf Cong}(P)$. The lattice
$\operatorname{\sf Cong}(\mathcal{T}_{r})$ is well understood, thanks to
Theorem 2.6, so we now turn to the task of understanding the interval
$\mathfrak{K}=[\Delta_{P},\kappa]$, thereby proving Theorem 3.2(ii):

######  Theorem 6.1.

The mapping

$[\Delta_{P},\kappa]\to[\Delta_{P},\lambda]\times[\Delta_{P},\rho]:\theta\mapsto(\theta\cap\lambda,\theta\cap\rho)$

is a lattice isomorphism.

###### Proof.

We apply Proposition 2.11, for which we need to verify the following:

  * •

$\lambda,\rho\in\operatorname{\sf Cong}(P)$ (Lemma 6.2), so that
$[\Delta_{P},\lambda]$ and $[\Delta_{P},\rho]$ are well-defined intervals in
$\operatorname{\sf Cong}(P)$.

  * •

The mappings
$\Phi_{\lambda}:\mathfrak{K}\rightarrow[\Delta_{P},\lambda]:\theta\mapsto\theta\cap\lambda$
and
$\Phi_{\rho}:\mathfrak{K}\rightarrow[\Delta_{P},\rho]:\theta\mapsto\theta\cap\rho$
are lattice surmorphisms (Lemma 6.3).

  * •

$\ker(\Phi_{\lambda})\cap\ker(\Phi_{\rho})=\Delta_{\mathfrak{K}}$ (Corollary
6.6).

  * •

$\ker(\Phi_{\lambda})\circ\ker(\Phi_{\rho})=\nabla_{\mathfrak{K}}$ (Lemma
6.7). ∎

######  Lemma 6.2.

The relations $\lambda$ and $\rho$ are congruences on $P$.

###### Proof.

We prove the statement for $\rho$, the one for $\lambda$ being dual. Since
$\kappa$ is a congruence and $\mathrel{\mathscr{R}}^{P}$ a left congruence, it
follows that $\rho=\kappa\cap{\mathrel{\mathscr{R}}}^{P}$ is a left
congruence. To prove that $\rho$ is right compatible, suppose $(f,g)\in\rho$
and $b\in P$. Since $\rho\subseteq\kappa$ it follows that
$\overline{f}=\overline{g}$, i.e. $afa=aga$. Since
$(f,g)\in{\mathrel{\mathscr{R}}^{P}}$, we can fix an idempotent $e$ in the
$\mathrel{\mathscr{R}}^{P}$-class $R_{f}^{P}=R_{g}^{P}$, and we have $f=e\star
f$ and $g=e\star g$. But then

$f\star b=e\star f\star b=e(afa)b=e(aga)b=e\star g\star b=g\star b,$

and certainly $(f\star b,g\star b)\in\rho$, as required. ∎

######  Lemma 6.3.

$\Phi_{\lambda}$ and $\Phi_{\rho}$ are lattice surmorphisms.

###### Proof.

We prove the statement for $\Phi_{\lambda}$, and the one for $\Phi_{\rho}$ is
dual. That $\Phi_{\lambda}$ is well defined follows from Lemma 6.2, and that
it is surjective from the fact that it acts as the identity mapping on its
image, $[\Delta_{P},\lambda]$. That $\Phi_{\lambda}$ respects $\cap$ is
immediate from the definition:

$\Phi_{\lambda}(\theta_{1}\cap\theta_{2})=\theta_{1}\cap\theta_{2}\cap\lambda=(\theta_{1}\cap\lambda)\cap(\theta_{2}\cap\lambda)=\Phi_{\lambda}(\theta_{1})\cap\Phi_{\lambda}(\theta_{2})\qquad\text{for
$\theta_{1},\theta_{2}\in[\Delta_{P},\kappa]$.}$

To prove that it also respects $\vee$, we need to verify that

$(\theta_{1}\vee\theta_{2})\cap\lambda=(\theta_{1}\cap\lambda)\vee(\theta_{2}\cap\lambda)\qquad\text{for
all $\theta_{1},\theta_{2}\in[\Delta_{P},\kappa]$.}$

The reverse inclusion is obvious. For the direct inclusion, let
$(f,g)\in(\theta_{1}\vee\theta_{2})\cap\lambda$. This means that
$(f,g)\in\lambda$ and there is a sequence $f=f_{0}\to f_{1}\to\dots\to
f_{k}=g$ such that each ${(f_{i},f_{i+1})\in\theta_{1}\cup\theta_{2}}$. Let
$e$ be any idempotent in $L_{f}=L_{g}$. Since
$(f,f_{i})\in\theta_{1}\vee\theta_{2}\subseteq\kappa\subseteq{\mathrel{\mathchoice{\accentset{\displaystyle\text{\smash{\raisebox{-5.59721pt}{$\widehatsym$}}}}{\mathscr{H}}}{\accentset{\textstyle\text{\smash{\raisebox{-5.59721pt}{$\widehatsym$}}}}{\mathscr{H}}}{\accentset{\scriptstyle\text{\smash{\raisebox{-3.91806pt}{$\widehatsym$}}}}{\mathscr{H}}}{\accentset{\scriptscriptstyle\text{\smash{\raisebox{-2.7986pt}{$\widehatsym$}}}}{\mathscr{H}}}}^{P}}$,
Lemma 4.6 applies and tells us that all $f_{i}\star e$ are
$\mathrel{\mathscr{L}}^{P}$-related (to $f$), and we have ${(f_{i}\star
e,f_{i+1}\star e)\in\theta_{1}\cup\theta_{2}}$ for $0\leq i<k$. Hence
$(f_{i}\star e,f_{i+1}\star
e)\in(\theta_{1}\cap\lambda)\cup(\theta_{2}\cap\lambda)$ for all such $i$, and
therefore

$(f,g)=(f\star e,g\star e)=(f_{0}\star e,f_{k}\star
e)\in(\theta_{1}\cap\lambda)\vee(\theta_{2}\cap\lambda).\qed$

######  Lemma 6.4.

For every $\theta\in\mathfrak{K}$ we have
$\theta=\Phi_{\lambda}(\theta)\vee\Phi_{\rho}(\theta)$.

###### Proof.

For the direct inclusion (the reverse is obvious), let $(f,g)\in\theta$, and
fix some idempotent $e\in L_{f}^{P}$. By Lemma 4.6, the element $h=g\star e$
belongs to $L_{f}^{P}\cap R_{g}^{P}$, and is $\theta$-related to both $f$ and
$g$. In particular, $(f,h)\in\theta\cap\lambda=\Phi_{\lambda}(\theta)$ and
$(h,g)\in\theta\cap\rho=\Phi_{\rho}(\theta)$, and so
$(f,g)\in\Phi_{\lambda}(\theta)\vee\Phi_{\rho}(\theta)$. ∎

######  Remark 6.5.

As with Remark 5.6, the above proof shows that
$\theta=\Phi_{\lambda}(\theta)\circ\Phi_{\rho}(\theta)=\Phi_{\rho}(\theta)\circ\Phi_{\lambda}(\theta)$
for any $\theta\in\mathfrak{K}$. As a special case,
$\kappa=\lambda\circ\rho=\rho\circ\lambda$.

######  Corollary 6.6.

$\ker(\Phi_{\lambda})\cap\ker(\Phi_{\rho})=\Delta_{\mathfrak{K}}$. ∎

######  Lemma 6.7.

$\ker(\Phi_{\lambda})\circ\ker(\Phi_{\rho})=\nabla_{\mathfrak{K}}$.

###### Proof.

Let $\theta_{1},\theta_{2}\in\mathfrak{K}$ be arbitrary. Define
$\theta=(\theta_{1}\cap\lambda)\vee(\theta_{2}\cap\rho)$. Since
$\Phi_{\lambda}$ is a lattice morphism (Lemma 6.3), we have

$\Phi_{\lambda}(\theta)=\Phi_{\lambda}(\theta_{1}\cap\lambda)\vee\Phi_{\lambda}(\theta_{2}\cap\rho)=(\theta_{1}\cap\lambda\cap\lambda)\vee(\theta_{2}\cap\rho\cap\lambda)=(\theta_{1}\cap\lambda)\vee\Delta_{P}=\theta_{1}\cap\lambda=\Phi_{\lambda}(\theta_{1}),$

and hence $(\theta_{1},\theta)\in\ker(\Phi_{\lambda})$. Dually,
$(\theta,\theta_{2})\in\ker(\Phi_{\rho})$, and so
$(\theta_{1},\theta_{2})\in\ker(\Phi_{\lambda})\circ\ker(\Phi_{\rho})$. ∎

##  7 The intervals $[\Delta_{P},\rho]$ and $[\Delta_{P},\lambda]$ as
subdirect products of full lattices of equivalence relations

We have just seen that the interval $[\Delta_{P},\kappa]$ in
$\operatorname{\sf Cong}(P)$ decomposes as a direct product of
$[\Delta_{P},\lambda]$ and $[\Delta_{P},\rho]$, so we now turn our attention
to these two intervals. We treat them in essentially the same way, modulo some
differing technicalities. In the first subsection we give the full details for
the interval $[\Delta_{P},\rho]$, and in the second we indicate how to adapt
this for $[\Delta_{P},\lambda]$.

###  7.1 The interval $[\Delta_{P},\rho]$

In what follows, we use the notation of Section 3, including the set
$\mathcal{C}_{I}$ of cross-sections of $\\{A_{i}:i\in I\\}$, for
$\varnothing\not=I\subseteq[r]$. Every $\mathrel{\mathscr{L}}^{P}$-class of
$P$ takes the form $L_{C}=\\{f\in P:\operatorname{im}(f)=C\\}$ where
$C\in\mathcal{C}_{I}$ for some $I$. For a fixed $I$, the union
$\bigcup_{C\in\mathcal{C}_{I}}L_{C}$ is an
$\mathrel{\mathchoice{\accentset{\displaystyle\text{\smash{\raisebox{-5.59721pt}{$\widehatsym$}}}}{\mathscr{L}}}{\accentset{\textstyle\text{\smash{\raisebox{-5.59721pt}{$\widehatsym$}}}}{\mathscr{L}}}{\accentset{\scriptstyle\text{\smash{\raisebox{-3.91806pt}{$\widehatsym$}}}}{\mathscr{L}}}{\accentset{\scriptscriptstyle\text{\smash{\raisebox{-2.7986pt}{$\widehatsym$}}}}{\mathscr{L}}}}^{P}$-class
of $P$, and all
$\mathrel{\mathchoice{\accentset{\displaystyle\text{\smash{\raisebox{-5.59721pt}{$\widehatsym$}}}}{\mathscr{L}}}{\accentset{\textstyle\text{\smash{\raisebox{-5.59721pt}{$\widehatsym$}}}}{\mathscr{L}}}{\accentset{\scriptstyle\text{\smash{\raisebox{-3.91806pt}{$\widehatsym$}}}}{\mathscr{L}}}{\accentset{\scriptscriptstyle\text{\smash{\raisebox{-2.7986pt}{$\widehatsym$}}}}{\mathscr{L}}}}^{P}$-classes
have this form for some $I$. For $\theta\in\mathfrak{R}$ define

$\Psi_{I}(\theta)=\big{\\{}(C,C^{\prime})\in\mathcal{C}_{I}\times\mathcal{C}_{I}:\theta\cap(L_{C}\times
L_{C^{\prime}})\neq\varnothing\big{\\}}.$ (7.1)

######  Theorem 7.2.

The mapping

$[\Delta_{P},\rho]\rightarrow\prod_{\varnothing\neq
I\subseteq[r]}\mathfrak{Eq}(\mathcal{C}_{I}):\theta\mapsto(\Psi_{I}(\theta))$

is a subdirect embedding of lattices, with image

$\Big{\\{}(\psi_{I})\in\prod_{\varnothing\neq
I\subseteq[r]}\mathfrak{Eq}(\mathcal{C}_{I}):\psi_{I}{\restriction}_{J}\subseteq\psi_{J}\text{
for all }\varnothing\neq J\subseteq I\subseteq[r]\Big{\\}}.$

###### Proof.

For the first assertion we apply Proposition 2.12, for which we need to
establish that:

  * •

each $\Psi_{I}$ is a well defined mapping
$\mathfrak{R}\rightarrow\mathfrak{Eq}(\mathcal{C}_{I})$ (Lemma 7.4);

  * •

each $\Psi_{I}$ is surjective (Lemma 7.10);

  * •

each $\Psi_{I}$ is a lattice morphism (Lemma 7.5);

  * •

$\bigcap_{I\subseteq[r]}\ker(\Psi_{I})=\Delta_{\mathfrak{R}}$ (Corollary 7.7).

We prove that the image of the embedding is as stated in Lemmas 7.8 and 7.9. ∎

The first lemma establishes an equivalent, ostensibly stronger condition for
membership of $\Psi_{I}(\theta)$.

######  Lemma 7.3.

Let $\varnothing\neq I\subseteq[r]$ and $C,C^{\prime}\in\mathcal{C}_{I}$. For
each $f\in L_{C}$, there is a unique element $f^{\prime}\in L_{C^{\prime}}$
such that $(f,f^{\prime})\in\rho$. Furthermore, for any
$\theta\in\mathfrak{R}$, we have

$\theta\cap(L_{C}\times
L_{C^{\prime}})\not=\varnothing\qquad\Leftrightarrow\qquad(f,f^{\prime})\in\theta\text{
for all }f\in L_{C}.$

###### Proof.

For the first assertion, consider arbitrary elements $f\in L_{C}$ and
$f^{\prime}\in L_{C^{\prime}}$. From the definition of
$\rho=\kappa\cap{\mathrel{\mathscr{R}}^{P}}$ we have

$(f,f^{\prime})\in\rho\ \Leftrightarrow\ (f,f^{\prime})\in\kappa\text{ and
}f^{\prime}\in R_{f}^{P}\cap L_{C^{\prime}}.$

The set $R_{f}^{P}\cap L_{C^{\prime}}$ is an $\mathrel{\mathscr{H}}^{P}$-class
contained in the
$\mathrel{\mathchoice{\accentset{\displaystyle\text{\smash{\raisebox{-5.59721pt}{$\widehatsym$}}}}{\mathscr{H}}}{\accentset{\textstyle\text{\smash{\raisebox{-5.59721pt}{$\widehatsym$}}}}{\mathscr{H}}}{\accentset{\scriptstyle\text{\smash{\raisebox{-3.91806pt}{$\widehatsym$}}}}{\mathscr{H}}}{\accentset{\scriptscriptstyle\text{\smash{\raisebox{-2.7986pt}{$\widehatsym$}}}}{\mathscr{H}}}}^{P}$-class
of $f$. Both the existence and uniqueness of $f^{\prime}$ now follow from
$\kappa=\ker(\phi)$ and the fact that $\phi$ is bijective between any
$\mathrel{\mathscr{H}}^{P}$-class of $P$ and the corresponding
$\mathrel{\mathscr{H}}^{T}$-class of $T$.

For the second assertion, the reverse implication ($\Leftarrow$) is obvious.
For the direct implication ($\Rightarrow$) suppose
$(g,h)\in\theta\cap(L_{C}\times L_{C^{\prime}})$, and let $f\in
L_{C}=L_{g}^{P}$ be arbitrary. Let $b\in P$ be such that $b\star g=f$. By
Green’s Lemma we have $b\star h\in L_{C^{\prime}}$, and $(f,b\star h)=(b\star
g,b\star h)\in\theta$ since $\theta$ is a congruence. From
$\theta\subseteq\rho$ and $b\star h\in L_{C^{\prime}}$, it follows from the
first assertion that $b\star h=f^{\prime}$, and hence
$(f,f^{\prime})\in\theta$. ∎

######  Lemma 7.4.

Each $\Psi_{I}$ is a well-defined mapping
$\mathfrak{R}\rightarrow\mathfrak{Eq}(\mathcal{C}_{I})$, i.e. for every
$\theta\in\mathfrak{R}$ the relation $\Psi_{I}(\theta)$ is an equivalence on
$\mathcal{C}_{I}$.

###### Proof.

Reflexivity and symmetry follow directly from the definition (7.1) of
$\Psi_{I}$, and the same properties for $\theta$. For transitivity, assume
that $(C,C^{\prime}),(C^{\prime},C^{\prime\prime})\in\Psi_{I}(\theta)$. This
means that $\theta\cap(L_{C}\times L_{C^{\prime}})$ and
$\theta\cap(L_{C^{\prime}}\times L_{C^{\prime\prime}})$ are both non-empty.
Let $f\in L_{C}$. By Lemma 7.3, applied twice, there exists a unique
$f^{\prime}\in L_{C^{\prime}}$ with $(f,f^{\prime})\in\theta$, and then a
unique $f^{\prime\prime}\in L_{C^{\prime\prime}}$ with
$(f^{\prime},f^{\prime\prime})\in\theta$. Transitivity of $\theta$ gives
$(f,f^{\prime\prime})\in\theta$, and hence
$(C,C^{\prime\prime})\in\Psi_{I}(\theta)$. ∎

######  Lemma 7.5.

Each $\Psi_{I}$ is a lattice morphism.

###### Proof.

Let $\theta_{1},\theta_{2}\in\mathfrak{R}$. We need to show that

  1.   2. (i)

$\Psi_{I}(\theta_{1}\cap\theta_{2})=\Psi_{I}(\theta_{1})\cap\Psi_{I}(\theta_{2})$,
and

  3. (ii)

$\Psi_{I}(\theta_{1}\vee\theta_{2})=\Psi_{I}(\theta_{1})\vee\Psi_{I}(\theta_{2})$.

From (7.1) it is clear that $\Psi_{I}$ is monotone. Hence,
$\Psi_{I}(\theta_{1}\cap\theta_{2})\subseteq\Psi_{I}(\theta_{i})\subseteq\Psi_{I}(\theta_{1}\vee\theta_{2})$
for $i=1,2$. This implies the direct inclusion in (i) and the reverse
inclusion in (ii).

For the reverse inclusion in (i), suppose
$(C,C^{\prime})\in\Psi_{I}(\theta_{1})\cap\Psi_{I}(\theta_{2})$, so that
${\theta_{i}\cap(L_{C}\times L_{C^{\prime}})\neq\varnothing}$ for $i=1,2$. Let
$f\in L_{C}$ be arbitrary, and let $f^{\prime}\in L_{C^{\prime}}$ be as in
Lemma 7.3. Then this lemma gives $(f,f^{\prime})\in\theta_{i}\cap(L_{C}\times
L_{C^{\prime}})$ for $i=1,2$, and so
$(C,C^{\prime})\in\Psi_{I}(\theta_{1}\cap\theta_{2})$

For the direct inclusion in (ii), suppose
$(C,C^{\prime})\in\Psi_{I}(\theta_{1}\vee\theta_{2})$, so that
${(\theta_{1}\vee\theta_{2})\cap(L_{C}\times L_{C^{\prime}})\neq\varnothing}$.
Fix some $(f,g)\in(\theta_{1}\vee\theta_{2})\cap(L_{C}\times L_{C^{\prime}})$.
So there is a sequence ${f=f_{0}\to f_{1}\to\dots\to f_{k}=g}$, with each
$(f_{i},f_{i+1})\in\theta_{1}\cup\theta_{2}$. Since $f_{0},f_{1},\dots,f_{k}$
are all
$\mathrel{\mathchoice{\accentset{\displaystyle\text{\smash{\raisebox{-5.59721pt}{$\widehatsym$}}}}{\mathscr{L}}}{\accentset{\textstyle\text{\smash{\raisebox{-5.59721pt}{$\widehatsym$}}}}{\mathscr{L}}}{\accentset{\scriptstyle\text{\smash{\raisebox{-3.91806pt}{$\widehatsym$}}}}{\mathscr{L}}}{\accentset{\scriptscriptstyle\text{\smash{\raisebox{-2.7986pt}{$\widehatsym$}}}}{\mathscr{L}}}}^{P}$-related
(as
$\theta_{1},\theta_{2}\subseteq\kappa\subseteq{\mathrel{\mathchoice{\accentset{\displaystyle\text{\smash{\raisebox{-5.59721pt}{$\widehatsym$}}}}{\mathscr{H}}}{\accentset{\textstyle\text{\smash{\raisebox{-5.59721pt}{$\widehatsym$}}}}{\mathscr{H}}}{\accentset{\scriptstyle\text{\smash{\raisebox{-3.91806pt}{$\widehatsym$}}}}{\mathscr{H}}}{\accentset{\scriptscriptstyle\text{\smash{\raisebox{-2.7986pt}{$\widehatsym$}}}}{\mathscr{H}}}}^{P}}$),
it follows that each $f_{i}\in L_{C_{i}}$ for some $C_{i}\in\mathcal{C}_{I}$.
But then each $(\theta_{1}\cup\theta_{2})\cap(L_{C_{i}}\times
L_{C_{i+1}})\neq\varnothing$, and so each
${(C_{i},C_{i+1})\in\Psi_{I}(\theta_{1})\cup\Psi_{I}(\theta_{2})}$. It follows
that
$(C,C^{\prime})=(C_{0},C_{k})\in\Psi_{I}(\theta_{1})\vee\Psi_{I}(\theta_{2})$.
∎

######  Lemma 7.6.

For every $\theta\in\mathfrak{R}$ we have

$\theta=\bigcup_{\varnothing\neq
I\subseteq[r]}\theta_{I},\qquad\text{where}\qquad\theta_{I}=\bigcup_{(C,C^{\prime})\in\Psi_{I}(\theta)}\rho\cap(L_{C}\times
L_{C^{\prime}}).$

###### Proof.

Throughout the proof we write $\theta^{\prime}=\bigcup_{I}\theta_{I}$.

($\subseteq$). Suppose $(f,g)\in\theta$. Since
$(f,g)\in{\mathrel{\mathchoice{\accentset{\displaystyle\text{\smash{\raisebox{-5.59721pt}{$\widehatsym$}}}}{\mathscr{L}}}{\accentset{\textstyle\text{\smash{\raisebox{-5.59721pt}{$\widehatsym$}}}}{\mathscr{L}}}{\accentset{\scriptstyle\text{\smash{\raisebox{-3.91806pt}{$\widehatsym$}}}}{\mathscr{L}}}{\accentset{\scriptscriptstyle\text{\smash{\raisebox{-2.7986pt}{$\widehatsym$}}}}{\mathscr{L}}}}^{P}}$,
it follows that $f\in L_{C}$ and $g\in L_{C^{\prime}}$ for some
$\varnothing\not=I\subseteq[r]$ and some $C,C^{\prime}\in\mathcal{C}_{I}$. So
$(f,g)\in\theta\cap(L_{C}\times L_{C^{\prime}})$, meaning that
$(C,C^{\prime})\in\Psi_{I}(\theta)$, and
$(f,g)\in\theta_{I}\subseteq\theta^{\prime}$.

($\supseteq$). Suppose $(f,g)\in\theta^{\prime}$, say with
$(f,g)\in\theta_{I}$. So $(f,g)\in\rho\cap(L_{C}\times L_{C^{\prime}})$ for
some $(C,C^{\prime})\in\Psi_{I}(\theta)$, and it follows that $g=f^{\prime}$
in the notation of Lemma 7.3. Since $(C,C^{\prime})\in\Psi_{I}(\theta)$ we
have $\theta\cap(L_{C}\times L_{C^{\prime}})\not=\varnothing$, and Lemma 7.3
gives $(f,g)=(f,f^{\prime})\in\theta$. ∎

######  Corollary 7.7.

$\displaystyle\bigcap_{\varnothing\neq
I\subseteq[r]}\ker(\Psi_{I})=\Delta_{\mathfrak{R}}$. ∎

######  Lemma 7.8.

For every $\theta\in\mathfrak{R}$ and all $\varnothing\neq J\subseteq
I\subseteq[r]$ we have
$\Psi_{I}(\theta){\restriction}_{J}\subseteq\Psi_{J}(\theta)$.

###### Proof.

Suppose $(B,B^{\prime})\in\Psi_{I}(\theta){\restriction}_{J}$, so that
$B=C{\restriction}_{J}$ and $B^{\prime}=C^{\prime}{\restriction}_{J}$, for
some ${(C,C^{\prime})\in\Psi_{I}(\theta)}$. Write $C=\\{c_{i}:i\in I\\}$ and
$C^{\prime}=\\{c_{i}^{\prime}:i\in I\\}$, where each $c_{i},c_{i}^{\prime}\in
A_{i}$, and note that then ${B=\\{c_{j}:j\in J\\}}$ and
$B^{\prime}=\\{c_{j}^{\prime}:j\in J\\}$. Since
$(C,C^{\prime})\in\Psi_{I}(\theta)$, there exists
${(f,g)\in\theta\cap(L_{C}\times L_{C^{\prime}})}$, and we note that
$\operatorname{im}(f)=C$ and $\operatorname{im}(g)=C^{\prime}$. Since
$\ker(f)=\ker(g)$, as
$(f,g)\in\theta\subseteq\rho\subseteq{\mathrel{\mathscr{R}}^{P}}$, we can
therefore write $f=\binom{K_{i}}{c_{i}}$ and
$g=\binom{K_{i}}{c_{i\pi}^{\prime}}$ for some permutation
$\pi\in\mathcal{S}_{I}$. In fact, from
$(f,g)\in\theta\subseteq\kappa=\ker(\phi)$ it follows that
$\overline{f}=\overline{g}$, and from this that $\pi=\operatorname{id}_{I}$,
so in fact $g=\binom{K_{i}}{c_{i}^{\prime}}$. For each $j\in J$, let
$j^{\prime}\in I$ be such that $a_{j^{\prime}}\in K_{j}$, and let $b$ be an
arbitrary element of $P$ with $\operatorname{im}(b)=\\{a_{j^{\prime}}:j\in
J\\}$. Then $(b\star f,b\star g)\in\theta$, and we have
$\operatorname{im}(b\star f)=B$ and $\operatorname{im}(b\star g)=B^{\prime}$.
Thus, $(b\star f,b\star g)\in\theta\cap(L_{B}\times L_{B^{\prime}})$, and so
$(B,B^{\prime})\in\Psi_{J}(\theta)$. ∎

######  Lemma 7.9.

Suppose for every $\varnothing\neq I\subseteq[r]$ we have an equivalence
relation $\psi_{I}\in\mathfrak{Eq}(\mathcal{C}_{I})$, and that these relations
additionally satisfy $\psi_{I}{\restriction}_{J}\subseteq\psi_{J}$ for all
$J\subseteq I$. Then the relation

$\theta=\bigcup_{I}\theta_{I},\qquad\text{where}\qquad\theta_{I}=\bigcup_{(C,C^{\prime})\in\psi_{I}}\rho\cap(L_{C}\times
L_{C^{\prime}}),$

belongs to $\mathfrak{R}$, and we have $\Psi_{I}(\theta)=\psi_{I}$ for all
$I$.

###### Proof.

First we prove that $\theta$ is an equivalence relation on $P$, by showing
that each $\theta_{I}$ is an equivalence relation. Reflexivity and symmetry
follow directly from the same properties of the $\psi_{I}$. For transitivity,
suppose $(f_{1},f_{2}),(f_{2},f_{3})\in\theta_{I}$. This certainly means that
$(f_{1},f_{2}),(f_{2},f_{3})\in\rho$, and hence $(f_{1},f_{3})\in\rho$.
Further, writing $C_{i}=\operatorname{im}(f_{i})$ for $i=1,2,3$, we have
$(C_{1},C_{2}),(C_{2},C_{3})\in\psi_{I}$. By transitivity of $\psi_{I}$ we
have $(C_{1},C_{3})\in\psi_{I}$, from which we deduce
$(f_{1},f_{3})\in\theta_{I}$.

Next, we check compatibility. Suppose $(f,g)\in\theta$ and $b\in P$. Then, for
some $I$ and $(C,C^{\prime})\in\psi_{I}$, we have
$(f,g)\in\rho\cap(L_{C}\times L_{C^{\prime}})$, and we write $C=\\{c_{i}:i\in
I\\}$ and $C^{\prime}=\\{c_{i}^{\prime}:i\in I\\}$. As in the proof of Lemma
6.2 we have $f\star b=g\star b$, and hence $(f\star b,g\star b)\in\theta$. It
remains to show that $(b\star f,b\star g)\in\theta$. Certainly $(b\star
f,b\star g)\in\rho$, since $\rho$ is a congruence. As in the proof of Lemma
7.8, we can write $f=\binom{K_{i}}{c_{i}}$ and
$g=\binom{K_{i}}{c_{i}^{\prime}}$. Let $J=\\{j\in I:\operatorname{im}(ba)\cap
K_{j}\neq\varnothing\\}$. Then $\operatorname{im}(b\star f)=\\{c_{j}:j\in
J\\}=C{\restriction}_{J}$ and $\operatorname{im}(b\star
g)=\\{c_{j}^{\prime}:j\in J\\}=C^{\prime}{\restriction}_{J}$. By assumption,
we have
$(C{\restriction}_{J},C^{\prime}{\restriction}_{J})\in\psi_{I}{\restriction}_{J}\subseteq\psi_{J}$,
and so $(b\star f,b\star g)\in\theta_{J}\subseteq\theta$, as required. Thus,
$\theta$ is a congruence, and it is clearly contained in $\rho$, so
$\theta\in\mathfrak{R}$.

Finally, following the definitions of $\Psi_{I}$ and $\theta$, we have

$\Psi_{I}(\theta)=\big{\\{}(C,C^{\prime})\in\mathcal{C}_{I}\times\mathcal{C}_{I}:\theta\cap(L_{C}\times
L_{C^{\prime}})\neq\varnothing\big{\\}}=\psi_{I}.\qed$

######  Lemma 7.10.

Each $\Psi_{I}$ is surjective.

###### Proof.

Suppose $\psi\in\mathfrak{Eq}(\mathcal{C}_{I})$. For each $\varnothing\neq
J\subseteq[r]$, define

$\psi_{J}=\begin{cases}\psi&\text{if }J=I\\\ \nabla_{\mathcal{C}_{J}}&\text{if
}J\subset I\\\ \Delta_{\mathcal{C}_{J}}&\text{otherwise}.\end{cases}$

This family satisfies the conditions of Lemma 7.9, and hence there exists
$\theta\in\mathfrak{R}$ such that $\Psi_{J}(\theta)=\psi_{J}$ for all $J$. In
particular, $\Psi_{I}(\theta)=\psi$, completing the proof. ∎

###  7.2 The interval $[\Delta_{P},\lambda]$

The interval $\mathfrak{L}=[\Delta_{P},\lambda]$ may be treated in an entirely
analogous fashion to $\mathfrak{R}=[\Delta_{P},\rho]$, modulo some differing
technical details regarding the ${\restriction}$ operations. These arise
because where for $\mathfrak{R}$ we needed to work with
$\mathrel{\mathscr{L}}^{P}$-classes contained in a common
$\mathrel{\mathchoice{\accentset{\displaystyle\text{\smash{\raisebox{-5.59721pt}{$\widehatsym$}}}}{\mathscr{L}}}{\accentset{\textstyle\text{\smash{\raisebox{-5.59721pt}{$\widehatsym$}}}}{\mathscr{L}}}{\accentset{\scriptstyle\text{\smash{\raisebox{-3.91806pt}{$\widehatsym$}}}}{\mathscr{L}}}{\accentset{\scriptscriptstyle\text{\smash{\raisebox{-2.7986pt}{$\widehatsym$}}}}{\mathscr{L}}}}^{P}$-class,
now we work with $\mathrel{\mathscr{R}}^{P}$-classes contained in a common
$\mathrel{\mathchoice{\accentset{\displaystyle\text{\smash{\raisebox{-5.59721pt}{$\widehatsym$}}}}{\mathscr{R}}}{\accentset{\textstyle\text{\smash{\raisebox{-5.59721pt}{$\widehatsym$}}}}{\mathscr{R}}}{\accentset{\scriptstyle\text{\smash{\raisebox{-3.91806pt}{$\widehatsym$}}}}{\mathscr{R}}}{\accentset{\scriptscriptstyle\text{\smash{\raisebox{-2.7986pt}{$\widehatsym$}}}}{\mathscr{R}}}}^{P}$-class.
In combinatorial terms, this translates to working with partitions of $[r]$,
as opposed to subsets.

We again use the notation of Section 3, including the sets
$\mathcal{P}_{\mathbf{I}}$ (for $\mathbf{I}\preceq[[r]]$) of all partitions of
$[n]$ of the form $\mathbf{P}=\\{P_{I}:I\in\mathbf{I}\\}$ such that
$P_{I}\cap\operatorname{im}(a)=\\{a_{i}:i\in I\\}$. Every
$\mathrel{\mathscr{R}}^{P}$-class of $P$ is of the form
$R_{\mathbf{P}}=\\{f\in P:X/\ker(f)=\mathbf{P}\\}$ where
$\mathbf{P}\in\mathcal{P}_{\mathbf{I}}$ for some $\mathbf{I}\preceq[[r]]$. For
a fixed $\mathbf{I}$, the union
$\bigcup_{\mathbf{P}\in\mathcal{P}_{\mathbf{I}}}R_{\mathbf{P}}$ is a generic
$\mathrel{\mathchoice{\accentset{\displaystyle\text{\smash{\raisebox{-5.59721pt}{$\widehatsym$}}}}{\mathscr{R}}}{\accentset{\textstyle\text{\smash{\raisebox{-5.59721pt}{$\widehatsym$}}}}{\mathscr{R}}}{\accentset{\scriptstyle\text{\smash{\raisebox{-3.91806pt}{$\widehatsym$}}}}{\mathscr{R}}}{\accentset{\scriptscriptstyle\text{\smash{\raisebox{-2.7986pt}{$\widehatsym$}}}}{\mathscr{R}}}}^{P}$-class
of $P$. For $\theta\in\mathfrak{L}$ define

$\Psi_{\mathbf{I}}(\theta)=\big{\\{}(\mathbf{P},\mathbf{P}^{\prime})\in\mathcal{P}_{\mathbf{I}}\times\mathcal{P}_{\mathbf{I}}:\theta\cap(R_{\mathbf{P}}\times
R_{\mathbf{P}^{\prime}})\neq\varnothing\big{\\}}.$

######  Theorem 7.11.

The mapping

$\Psi:[\Delta_{P},\lambda]\rightarrow\prod_{\mathbf{I}\preceq[[r]]}\mathfrak{Eq}(\mathcal{P}_{\mathbf{I}}):\theta\mapsto(\Psi_{\mathbf{I}}(\theta))$

is a subdirect embedding of lattices, with image

$\Big{\\{}(\psi_{\mathbf{I}})\in\prod_{\mathbf{I}\preceq[[r]]}\mathfrak{Eq}(\mathcal{P}_{\mathbf{I}}):\psi_{\mathbf{I}}{\restriction}_{\mathbf{J}}\subseteq\psi_{\mathbf{J}}\text{
for all }\mathbf{J}\preceq\mathbf{I}\preceq[[r]]\Big{\\}}.$

###### Sketch of proof..

The proof follows exactly the same pattern as that of Theorem 7.2. Each of the
results 7.3–7.10 has a straightforward left-right translation, and the proofs
are also relatively easy modifications; we omit the details. Put together,
they prove the theorem, using Proposition 2.12. ∎

######  Remark 7.12.

As in Remark 5.13, one can use Theorems 7.2 and 7.11 to draw lattice diagrams
for the intervals $[\Delta_{P},\rho]$ and $[\Delta_{P},\lambda]$, by
identifying these with their images under the embeddings from the relevant
theorem. We have done this in the special case that $X=\\{1,2,3,4\\}$ and
${a=\leavevmode\hbox{\set@color$\left(\begin{smallmatrix}1&2&3&4\\\
1&2&3&3\end{smallmatrix}\right)$}\in\mathcal{T}_{X}=\mathcal{T}_{4}}$, by
calculating the $\mathcal{C}_{I}$ and $\mathcal{P}_{\mathbf{I}}$ sets, and the
appropriate systems of equivalences. The (elementary) details of the
calculation are omitted, but the resulting diagrams are shown in Figure 5. Of
course one could then construct a diagram for
$[\Delta_{P},\kappa]\cong[\Delta_{P},\lambda]\times[\Delta_{P},\rho]$. We omit
this step, as $[\Delta_{P},\kappa]$ can be seen in Figure 3 as the interval
bounded by the solid red and blue vertices. Examining the figures, one can
check that this interval has size $90$, while $[\Delta_{P},\rho]$ and
$[\Delta_{P},\lambda]$ have sizes $6$ and $15$, respectively.

Figure 5 also shows the congruences $\lambda_{q}=\lambda\cap R_{q}^{P}$ and
$\rho_{q}=\rho\cap R_{q}^{P}$, for $q=0,1,2,3$. These can be used to construct
the sub-intervals
$[\kappa_{q},\kappa]\cong[\lambda_{q},\lambda]\times[\rho_{q},\rho]$, and
hence the ‘layers’ $\Lambda_{\xi}$ of $\operatorname{\sf Cong}(P)$, discussed
in Remark 5.13; cf. Figures 3 and 4.

$\rho=\rho_{3}$$\rho_{2}$$\rho_{1}$$\Delta_{P}=\rho_{0}$$\lambda=\lambda_{3}$$\lambda_{2}$$\Delta_{P}=\lambda_{0}=\lambda_{1}$

Figure 5: Left and right: the intervals $[\Delta_{P},\rho]$ and
$[\Delta_{P},\lambda]$ in the congruence lattice of
$P=\operatorname{Reg}(\mathcal{T}_{4}^{a})$, where
$a=\leavevmode\hbox{\set@color$\left(\begin{smallmatrix}1&2&3&4\\\
1&2&3&3\end{smallmatrix}\right)$}$; cf. Figure 3.

##  8 Classification of congruences

Our main result, Theorem 3.2, describes the structure of the congruence
lattice of $P=\operatorname{\sf Cong}(\mathcal{T}_{X}^{a})$, by successively
decomposing the lattice via (sub)direct products. The various technical
results proved along the way allow us to give a transparent classification of
the congruences themselves. In order to make the classification succinct, we
introduce some further notation.

A _$\mathcal{C}$ -system_ is a tuple
$\Psi=(\psi_{I})\in\prod_{\varnothing\not=I\subseteq[r]}\mathfrak{Eq}(\mathcal{C}_{I})$
satisfying $\psi_{I}{\restriction}_{J}\subseteq\psi_{J}$ for all
$\varnothing\not=J\subseteq I\subseteq[r]$. Given such a $\mathcal{C}$-system
$\Psi$, Lemma 7.9 tells us that the relation

$\rho(\Psi)=\bigcup_{\varnothing\not=I\subseteq[r]}\rho(\psi_{I}),\qquad\text{where}\qquad\rho(\psi_{I})=\bigcup_{(C,C^{\prime})\in\psi_{I}}\rho\cap(L_{C}\times
L_{C^{\prime}}),$

is a congruence of $P$. We also define the parameter
$\operatorname{rank}(\Psi)=\max\\{q:\psi_{I}=\nabla_{\mathcal{C}_{I}}\text{
whenever $|I|\leq q$}\\}$.

A _$\mathcal{P}$ -system_ is a tuple
$\Psi=(\psi_{\mathbf{I}})\in\prod_{\mathbf{I}\preceq[[r]]}\mathfrak{Eq}(\mathcal{P}_{\mathbf{I}})$
satisfying
$\psi_{\mathbf{I}}{\restriction}_{\mathbf{J}}\subseteq\psi_{\mathbf{J}}$ for
all $\mathbf{J}\preceq\mathbf{I}\preceq[[r]]$. Dually, we have the associated
congruence

$\lambda(\Psi)=\bigcup_{\mathbf{I}\preceq[[r]]}\lambda(\psi_{\mathbf{I}}),\qquad\text{where}\qquad\lambda(\psi_{\mathbf{I}})=\bigcup_{(\mathbf{P},\mathbf{P}^{\prime})\in\psi_{\mathbf{I}}}\lambda\cap(R_{\mathbf{P}}\times
R_{\mathbf{P}^{\prime}}),$

and parameter
$\operatorname{rank}(\Psi)=\max\\{q:\psi_{\mathbf{I}}=\nabla_{\mathcal{P}_{\mathbf{I}}}\text{
whenever $|\mathbf{I}|\leq q$}\\}$.

######  Theorem 8.1.

Let $X$ be a finite set, and let $a\in\mathcal{T}_{X}$ be an idempotent of
rank $r$. Then every non-universal congruence $\sigma$ of
$P=\operatorname{Reg}(\mathcal{T}_{X}^{a})$ has a unique decomposition as

$\sigma=R_{N}^{P}\vee\lambda(\Psi_{1})\vee\rho(\Psi_{2})=R_{N}^{P}\circ\lambda(\Psi_{1})\circ\rho(\Psi_{2}),$

where

  * •

$N$ is a normal subgroup of $\mathcal{S}_{q}$ for some $1\leq q\leq r$,

  * •

$\Psi_{1}$ is a $\mathcal{P}$-system, and $\Psi_{2}$ a $\mathcal{C}$-system,
both of rank at least $q-1$.

###### Proof.

The $r=1$ being trivial, we assume that $r\geq 2$. By Proposition 5.4 and
Lemmas 5.8–5.10, we have $\sigma=\xi^{\sharp}\vee\theta$ for unique
$\xi\in\operatorname{\sf Cong}(T)$ and $\theta\in[\Delta_{P},\kappa]$ with
$\operatorname{rank}(\xi)\leq\operatorname{rank}(\theta)$. Since $\sigma$ is
non-universal, we have $\xi=R_{N}^{T}$ for some $1\leq q\leq r$ and
$N\unlhd\mathcal{S}_{q}$, and then $\operatorname{rank}(\xi)=q-1$ and
$\xi^{\sharp}=R_{N}^{P}$ by Lemma 4.2. By Lemma 6.4 and Corollary 6.6 we have
$\theta=\theta_{1}\vee\theta_{2}$ for unique
$\theta_{1}\in[\Delta_{P},\lambda]$ and $\theta_{2}\in[\Delta_{P},\rho]$. By
Lemmas 7.6 and 7.9 we have $\theta_{2}=\rho(\Psi_{2})$ for a unique
$\mathcal{C}$-system $\Psi_{2}$, namely
$\Psi_{2}=(\Psi_{I}(\theta_{2}))_{\varnothing\not=I\subseteq[r]}$. Dually, we
have $\theta_{1}=\lambda(\Psi_{1})$ for a unique $\mathcal{P}$-system
$\Psi_{1}$. We then have
$q-1\leq\operatorname{rank}(\theta)=\min(\operatorname{rank}(\Psi_{1}),\operatorname{rank}(\Psi_{2}))$.
Finally, we note that
$\sigma=\xi^{\sharp}\vee\theta_{1}\vee\theta_{2}=\xi^{\sharp}\circ\theta_{1}\circ\theta_{2}$
because of Remarks 5.6 and 6.5. ∎

##  9 Application: the height of the lattice $\operatorname{\sf Cong}(P)$

The _height_ of a finite lattice $L$, denoted $\operatorname{\sf Ht}(L)$, is
the maximum size of a chain in $L$. Heights of lattices of subgroups,
subsemigroups and semigroup congruences have been treated in [6], [5] and [3],
respectively. Results of [3] include exact values for the heights of
congruence lattices of semigroups satisfying the separation properties
discussed in the introduction, and these do not hold for
$P=\operatorname{Reg}(\mathcal{T}_{X}^{a})$. Nevertheless, we can compute the
height of $\operatorname{\sf Cong}(P)$ by using our (sub)direct decompositions
from Theorem 3.2.

######  Theorem 9.1.

Let $X$ be a finite set of size $n$, and let
$a=\big{(}\begin{smallmatrix}A_{1}&\cdots&A_{r}\\\
a_{1}&\cdots&a_{r}\end{smallmatrix}\big{)}\in\mathcal{T}_{X}$ be a mapping of
rank $r$. Then the congruence lattice of
$P=\operatorname{Reg}(\mathcal{T}_{X}^{a})$ has height

$\operatorname{\sf Ht}(\operatorname{\sf
Cong}(P))=3r+\prod_{q=1}^{r}(|A_{q}|+1)+\sum_{q=1}^{r}S(r,q)q^{n-r}-2^{r}-B(r)-\begin{cases}2&\text{if
$1\leq r\leq 3$,}\\\ 1&\text{if $r\geq 4$.}\end{cases}$

In this result, $B(r)$ stands for the Bell number and $S(r,q)$ the Stirling
number of the second kind. Looking at the formula, we are unaware of a closed
expression for the numbers $\sum_{q=1}^{r}S(r,q)q^{n-r}$, but we note that
they appear as Sequence A108458 on the OEIS [1].

We prove the theorem via a series of lemmas, in which we will repeatedly make
use of the well-known fact that

$\operatorname{\sf Ht}(L_{1}\times L_{2})=\operatorname{\sf
Ht}(L_{1})+\operatorname{\sf Ht}(L_{2})-1\qquad\text{for finite lattices
$L_{1}$ and $L_{2}$.}$ (9.2)

######  Lemma 9.3.

We have $\operatorname{\sf Ht}(\operatorname{\sf Cong}(P))=\operatorname{\sf
Ht}(\operatorname{\sf Cong}(\mathcal{T}_{r}))+\operatorname{\sf
Ht}[\Delta_{P},\kappa]-1$.

###### Proof.

This is trivial for $r=1$ (cf. Remark 3.3). For $r\geq 2$, we identify
$\operatorname{\sf Cong}(P)$ with its image $\Lambda$ under the embedding into
$\operatorname{\sf Cong}(\mathcal{T}_{r})\times[\Delta_{P},\kappa]$ from
Theorem 3.2(i). It then immediately follows that

$\operatorname{\sf Ht}(\operatorname{\sf Cong}(P))\leq\operatorname{\sf
Ht}(\operatorname{\sf
Cong}(\mathcal{T}_{r})\times[\Delta_{P},\kappa])=\operatorname{\sf
Ht}(\operatorname{\sf Cong}(\mathcal{T}_{r}))+\operatorname{\sf
Ht}[\Delta_{P},\kappa]-1.$

It remains to give a chain in $\Lambda$ of the claimed size. For this, we fix
chains

$\Delta_{\mathcal{T}_{r}}=\xi_{1}\subset\xi_{2}\subset\cdots\subset\xi_{k}=\nabla_{\mathcal{T}_{r}}\qquad\text{and}\qquad\Delta_{P}=\theta_{1}\subset\theta_{2}\subset\cdots\subset\theta_{l}=\kappa$

in $\operatorname{\sf Cong}(\mathcal{T}_{r})$ and $[\Delta_{P},\kappa]$,
respectively, of length $k=\operatorname{\sf Ht}(\operatorname{\sf
Cong}(\mathcal{T}_{r}))$ and $l=\operatorname{\sf Ht}[\Delta_{P},\kappa]$. It
is then easy to verify that

$(\Delta_{\mathcal{T}_{r}},\Delta_{P})=(\xi_{1},\theta_{1})<(\xi_{1},\theta_{2})<\cdots<(\xi_{1},\theta_{l})=(\xi_{1},\kappa)<(\xi_{2},\kappa)<\cdots<(\xi_{k},\kappa)=(\nabla_{\mathcal{T}_{r}},\kappa)$

is a chain in $\Lambda$ of the required length $k+l-1$. ∎

It follows from Theorem 2.6 (and the well-known classification of normal
subgroups of symmetric groups) that

$\operatorname{\sf Ht}(\operatorname{\sf
Cong}(\mathcal{T}_{r}))=\begin{cases}3r-2&\text{for $1\leq r\leq 3$,}\\\
3r-1&\text{for $r\geq 4$.}\end{cases}$ (9.4)

We therefore turn to the task of finding an expression for $\operatorname{\sf
Ht}[\Delta_{P},\kappa]$. By Theorem 3.2, we have

$\operatorname{\sf Ht}[\Delta_{P},\kappa]=\operatorname{\sf
Ht}([\Delta_{P},\lambda]\times[\Delta_{P},\rho])=\operatorname{\sf
Ht}[\Delta_{P},\lambda]+\operatorname{\sf Ht}[\Delta_{P},\rho]-1.$ (9.5)

######  Lemma 9.6.

$\operatorname{\sf
Ht}[\Delta_{P},\lambda]=1-B(r)+\sum_{q=1}^{r}S(r,q)q^{n-r}$.

###### Proof.

First we claim that

$\operatorname{\sf Ht}[\Delta_{P},\lambda]=\operatorname{\sf
Ht}\Big{(}\prod_{\mathbf{I}\preceq[[r]]}\mathfrak{Eq}(\mathcal{P}_{\mathbf{I}})\Big{)}.$
(9.7)

The inequality $\leq$ follows from Theorem 3.2(iv). To establish the reverse
inequality, we need to exhibit a chain in $[\Delta_{P},\lambda]$ of size
$\operatorname{\sf
Ht}(\prod_{\mathbf{I}}\mathfrak{Eq}(\mathcal{P}_{\mathbf{I}}))$. We first
observe that (9.2) gives

$\operatorname{\sf
Ht}\Big{(}\prod_{\mathbf{I}}\mathfrak{Eq}(\mathcal{P}_{\mathbf{I}})\Big{)}=\sum_{\mathbf{I}}\operatorname{\sf
Ht}(\mathfrak{Eq}(\mathcal{P}_{\mathbf{I}}))-b+1=\sum_{\mathbf{I}}|\mathcal{P}_{\mathbf{I}}|-b+1,$
(9.8)

where $b$ is the number of partitions $I\preceq[[r]]$, i.e. $b=B(r)$, the Bell
number. We now list all the partitions of $[r]$ as
$\mathbf{I}_{1},\dots,\mathbf{I}_{b}$ extending the refinement partial order
$\preceq$ (i.e. $\mathbf{I}_{i}\preceq\mathbf{I}_{j}\ \Rightarrow\ i\leq j$).
Then, for each $i$, pick a chain in
$\mathfrak{Eq}(\mathcal{P}_{\mathbf{I}_{i}})$ of length
$l_{i}=\operatorname{\sf
Ht}(\mathfrak{Eq}(\mathcal{P}_{\mathbf{I}_{i}}))=|\mathcal{P}_{\mathbf{I}_{i}}|$:

$\Delta=\psi_{i,1}<\psi_{i,2}<\dots<\psi_{i,l_{i}}=\nabla.$

Here $\Delta$ and $\nabla$ stand for $\Delta_{\mathcal{P}_{\mathbf{I}_{i}}}$
and $\nabla_{\mathcal{P}_{\mathbf{I}_{i}}}$, respectively. We can find a copy
of this chain in the image of $[\Delta_{P},\lambda]$ in
$\prod_{\mathbf{I}}\mathfrak{Eq}(\mathcal{P}_{\mathbf{I}})$, as in Theorem
3.2(iv), in the following way, where we continue to omit subscripts from
various $\Delta$s and $\nabla$s:

$\displaystyle(\underbrace{\nabla,\dots,\nabla}_{i-1},\Delta,\Delta,\dots,\Delta)$
$\displaystyle=(\nabla,\dots,\nabla,\psi_{i,1},\Delta,\dots,\Delta)$
$\displaystyle<(\nabla,\dots,\nabla,\psi_{i,2},\Delta,\dots,\Delta)$
$\displaystyle\hskip 5.69054pt\vdots$
$\displaystyle<(\nabla,\dots,\nabla,\psi_{i,l_{i}},\Delta,\dots,\Delta)=(\underbrace{\nabla,\dots,\nabla}_{i},\Delta,\dots,\Delta).$

Concatenating these chains for $i=1,\dots,b$ yields a chain of requisite
length in $[\Delta_{P},\lambda]$, and establishes (9.7).

For a fixed partition $\mathbf{I}\preceq[[r]]$, the set
$\mathcal{P}_{\mathbf{I}}$ consists of all partitions
$\mathbf{P}=\\{P_{I}:I\in\mathbf{I}\\}\preceq[[n]]$ with
${P_{I}\cap\operatorname{im}(a)=\\{a_{i}:i\in I\\}}$. If $|\mathbf{I}|=q$ then
$|\mathcal{P}_{\mathbf{I}}|=q^{n-r}$. As there are $S(r,q)$ partitions of
$[r]$ with $q$ blocks we conclude that

$\sum_{\mathbf{I}}|\mathcal{P}_{\mathbf{I}}|=\sum_{q=1}^{r}S(r,q)q^{n-r}.$
(9.9)

Putting together (9.7), (9.8) and (9.9), and remembering $b=B(r)$, completes
the proof. ∎

######  Lemma 9.10.

$\operatorname{\sf Ht}[\Delta_{P},\rho]=1-2^{r}+\prod_{q=1}^{r}(|A_{q}|+1)$.

###### Proof.

This is analogous to the previous lemma, and we just indicate the main points.
To begin with:

$\displaystyle\operatorname{\sf Ht}[\Delta_{P},\rho]$
$\displaystyle=\operatorname{\sf Ht}\Big{(}\prod_{\varnothing\neq
I\subseteq[r]}\mathfrak{Eq}(\mathcal{C}_{I})\Big{)}$ exactly as in Lemma 9.6
$\displaystyle=\sum_{I}\operatorname{\sf
Ht}(\mathfrak{Eq}(\mathcal{C}_{I}))-2^{r}+2$ as there are $2^{r}-1$ possible
$I$ $\displaystyle=\sum_{I}|\mathcal{C}_{I}|-2^{r}+2.$

The sum here is over all $\varnothing\not=I\subseteq[r]$, and each
$\mathcal{C}_{I}$ consists of all cross-sections of $\\{A_{i}:i\in I\\}$. Thus
$|\mathcal{C}_{I}|=\prod_{i\in I}|A_{i}|$. The proof concludes with the
observation that $\sum_{I}\prod_{i\in I}|A_{i}|=\prod_{q=1}^{r}(|A_{i}|+1)-1$.
∎

Theorem 9.1 now follows by combining Lemmas 9.3, 9.6 and 9.10 with equations
(9.4) and (9.5).

##  10 Concluding remarks

To conclude the paper, we discuss a number of natural directions for further
study.

First, one could try to classify the congruences of the variant
$\mathcal{T}_{X}^{a}$ itself. While this is certainly an appealing problem, it
appears to be very challenging. Indeed, while
$\operatorname{Reg}(\mathcal{T}_{4}^{a})$ has $271$ congruences for
$a=\big{(}\begin{smallmatrix}1&2&3&4\\\
1&2&3&3\end{smallmatrix}\big{)}\in\mathcal{T}_{4}$, GAP calculations show that
there are $21263$ congruences of $\mathcal{T}_{3}^{b}$ for
$b=\big{(}\begin{smallmatrix}1&2&3\\\
1&2&2\end{smallmatrix}\big{)}\in\mathcal{T}_{3}$, and $3137$ _principal_
congruences of $\mathcal{T}_{4}^{a}$, i.e. congruences of the form
$(f,g)^{\sharp}$, generated by the single pair $(f,g)$. Moreover, there even
exist such congruences $(f,g)^{\sharp}$ that do not relate any other non-
trivial pairs; this happens when $af=ag$ and $fa=ga$. In any case,
understanding the entire lattice $\operatorname{\sf
Cong}(\mathcal{T}_{X}^{a})$ does not seem feasible at present.

Another enticing direction is to consider (regular) variants of other natural
families of semigroups whose congruence lattices are already known, e.g.
linear monoids [28, 9], infinite transformation monoids [27, 12] or diagram
monoids [14, 13, 10].

It would also be interesting to examine the extent to which the methods of the
current paper apply to more general semigroup variants, or even to sandwich
semigroups in locally small categories [11, 12]. The main challenge to
overcome here is the fact that Mal’cev’s classification of the congruences of
the underlying semigroup $\mathcal{T}_{X}$ played a pivotal role in a number
of our arguments above.

## References

  * [1] The on-line encyclopedia of integer sequences.  Published electronically at http://oeis.org/.
  * [2] J. Araújo, W. Bentz, and G. M. S. Gomes.  Congruences on direct products of transformation and matrix monoids.  Semigroup Forum, 97(3):384–416, 2018.
  * [3] M. Brookes, J. East, C. Miller, J. D. Mitchell, and N. Ruškuc.  Heights of one- and two-sided congruence lattices of semigroups.  Preprint, 2023, arXiv:2310.08229.
  * [4] S. Burris and H. P. Sankappanavar.  A course in universal algebra, volume 78 of Graduate Texts in Mathematics.  Springer-Verlag, New York-Berlin, 1981.
  * [5] P. J. Cameron, M. Gadouleau, J. D. Mitchell, and Y. Peresse.  Chains of subsemigroups.  Israel J. Math., 220(1):479–508, 2017.
  * [6] P. J. Cameron, R. Solomon, and A. Turull.  Chains of subgroups in symmetric groups.  J. Algebra, 127(2):340–352, 1989.
  * [7] A. H. Clifford and G. B. Preston.  The algebraic theory of semigroups. Vol. II.  Mathematical Surveys, No. 7. American Mathematical Society, Providence, R.I., 1967.
  * [8] I. Dolinka and J. East.  Variants of finite full transformation semigroups.  Internat. J. Algebra Comput., 25(8):1187–1222, 2015.
  * [9] I. Dolinka and J. East.  Semigroups of rectangular matrices under a sandwich operation.  Semigroup Forum, 96(2):253–300, 2018.
  * [10] I. Dolinka, I. Đurđev, and J. East.  Sandwich semigroups in diagram categories.  Internat. J. Algebra Comput., 31(7):1339–1404, 2021.
  * [11] I. Dolinka, I. Đurđev, J. East, P. Honyam, K. Sangkhanan, J. Sanwong, and W. Sommanee.  Sandwich semigroups in locally small categories I: foundations.  Algebra Universalis, 79(3):Art. 75, 35 pp, 2018.
  * [12] I. Dolinka, I. Đurđev, J. East, P. Honyam, K. Sangkhanan, J. Sanwong, and W. Sommanee.  Sandwich semigroups in locally small categories II: transformations.  Algebra Universalis, 79(3):Art. 76, 53 pp, 2018.
  * [13] J. East, J. D. Mitchell, N. Ruškuc, and M. Torpey.  Congruence lattices of finite diagram monoids.  Adv. Math., 333:931–1003, 2018.
  * [14] J. East and N. Ruškuc.  Congruences on infinite partition and partial Brauer monoids.  Mosc. Math. J., 22(2):295–372, 2022.
  * [15] J. East and N. Ruškuc.  Congruence lattices of ideals in categories and (partial) semigroups.  Mem. Amer. Math. Soc., 284(1408):vii+129, 2023.
  * [16] O. Ganyushkin and V. Mazorchuk.  Classical finite transformation semigroups, an introduction, volume 9 of Algebra and Applications.  Springer-Verlag London, Ltd., London, 2009.
  * [17] The GAP Group.  GAP – Groups, Algorithms, and Programming.
  * [18] J. A. Green.  On the structure of semigroups.  Ann. of Math. (2), 54:163–172, 1951.
  * [19] J. B. Hickey.  Semigroups under a sandwich operation.  Proc. Edinburgh Math. Soc. (2), 26(3):371–382, 1983.
  * [20] J. B. Hickey.  On variants of a semigroup.  Bull. Austral. Math. Soc., 34(3):447–459, 1986.
  * [21] J. M. Howie.  Fundamentals of semigroup theory, volume 12 of London Mathematical Society Monographs. New Series.  The Clarendon Press, Oxford University Press, New York, 1995.  Oxford Science Publications.
  * [22] T. A. Khan and M. V. Lawson.  Variants of regular semigroups.  Semigroup Forum, 62(3):358–374, 2001.
  * [23] G. Lallement.  Semigroups and combinatorial applications.  John Wiley & Sons, New York-Chichester-Brisbane, 1979.  Pure and Applied Mathematics, A Wiley-Interscience Publication.
  * [24] A. E. Liber.  On symmetric generalized groups.  Mat. Sbornik N.S., 33(75):531–544, 1953.
  * [25] E. S. Lyapin.  Semigroups _(in Russian)_.  Gosudarstv. Izdat. Fiz.-Mat. Lit., Moscow, 1960.
  * [26] K. D. Magill, Jr.  Semigroup structures for families of functions. I. Some homomorphism theorems.  J. Austral. Math. Soc., 7:81–94, 1967.
  * [27] A. I. Mal’cev.  Symmetric groupoids (Russian).  Mat. Sbornik N.S., 31(73):136–151, 1952.  English translation in Twelve papers in logic and algebra, Amer. Math. Soc. Translations Ser 2 113, AMS, 1979, pp. 235–250.
  * [28] A. I. Mal’cev.  Multiplicative congruences of matrices.  Doklady Akad. Nauk SSSR (N.S.), 90:333–335, 1953.
  * [29] J. D. Mitchell et al.  Semigroups - GAP package.
  * [30] J. Rhodes and B. Steinberg.  The $q$-theory of finite semigroups.  Springer Monographs in Mathematics. Springer, New York, 2009.
  * [31] È. G. Šutov.  Homomorphisms of the semigroup of all partial transformations.  Izv. Vysš. Učebn. Zaved. Matematika, 1961(3 (22)):177–184, 1961.