Finite bands are finitely related

Abstract

We prove that every finite idempotent semigroup (band) is finitely related, which means that the clone of its term operations (i.e. operations induced by words) is determined by finitely many relations. This solves an open problem posed by Mayr (Semigroup Forum 86:613–633, 2013).

1 Introduction

Let $\mathbf {A}=(A,\mathcal {F})$ be an algebra, where $\mathcal {F}$ is a family of finitary operations on the set A. As is well known, any term $\mathsf {t}(x_1,\ldots ,x_n)$ (of the same similarity type as $\mathbf {A}$) induces, by interpretation in $\mathbf {A}$, an operation $\mathsf {t}^\mathbf {A}:A^n\rightarrow A$. Operations obtained in this way are the term operations of $\mathbf {A}$, and the collection of all term operations of this algebra is denoted by $\mathrm {Clo}(\mathbf {A})$ and called the clone of $\mathbf {A}$.

For an n-ary operation f on a set X ($f:X^n\rightarrow X$) and a k-ary relation $\rho$ on the same set ($\rho \subseteq X^k$) we say that f preserves $\rho$ if for any $\overline{a}_1,\ldots ,\overline{a}_k\in X^n$ (where $\overline{a}_i=(a_{i,1},\ldots ,a_{i,n})$ for $1\le i\le k$) such that $(a_{1,j},\ldots ,a_{k,j})\in \rho$ for all $1\le j\le n$ we have $(f(\overline{a}_1),\ldots ,f(\overline{a}_k))\in \rho$; in other words, either $\rho =\varnothing$ or $\rho$ is a subalgebra of the kth direct power of the algebra (X, f). For a family $\mathcal {R}$ of (finitary) relations on X we denote by $\mathrm {Pol}(\mathcal {R})$ the set of all operations on X preserving all relations from $\mathcal {R}$ – these are the polymorphisms of the relational structure $(X,\mathcal {R})$. Conversely, if $\mathcal {O}$ is a family of operations on X, the set of all relations preserved by all operations from $\mathcal {O}$ is denoted by $\mathrm {Inv}(\mathcal {O})$. A foundational result in clone theory tells us that, for finite $\mathbf {A}$, $\mathrm {Clo}(\mathbf {A})= \mathrm {Pol}(\mathrm {Inv}(\mathcal {F}))$, and in this sense the clone of $\mathbf {A}$ is determined by the collection of relations $\mathrm {Inv}(\mathcal {F})$: an operation on A arises from a term if and only if it preserves all the relations that are preserved by $\mathcal {F}$.

The set of relations $\mathrm {Inv}(\mathcal {F})$ is always infinite. However, it may happen that there is in fact a finite subset $\mathcal {R}\subseteq \mathrm {Inv}(\mathcal {F})$ such that $\mathrm {Clo}(\mathbf {A})= \mathrm {Pol}(\mathcal {R})$, so that the clone of $\mathbf {A}$ is determined by a finite set of relations (which then can be reduced to a single relation). In such a case we say that the algebra $\mathbf {A}$ is finitely related.

Finitely related algebras recently received a lot of attention in universal algebra [8] and its applications in computer science because of their link, exhibited e.g. by [2, 5], to other key algebraic properties pertinent to the algebraic approach in studying the computation complexity of constraint satisfaction problems (CSP) [7]. See also [1, 3, 4, 16] for some recent developments and important results regarding finitely related general algebras. For example, a major result of Aichinger et al. [2] implies that any finite algebra having a Mal’cev term operation (including all finite groups and rings) is finitely related, a consequence of which is that there are only countably many Mal’cev clones on any finite set.

Concerning the study of finitely related (finite) semigroups, the seminal paper is the one of Davey et al. [9], where it was shown (among other things) that finite semigroups that are either commutative or nilpotent enjoy the finitely related property. This paper was followed by an extensive study of Mayr [17], who exhibited the first example of a non-finitely related finite semigroup (not too surprisingly, this was the ‘infamous’ six-element Brandt monoid $B_2^1$, which seems to behave badly with respect to almost any conceivable equational property of semigroup varieties). Also, Mayr proved that any finite regular band (an idempotent semigroup satisfying the identity $xyxzx\approx xyzx$) is finitely related. The question of whether all finite bands are finitely related is left as an open problem (Problem 6.3); the same question is mentioned following Problem 7.2 in [15]. It is exactly this problem that we aim to address in the present paper; namely, we prove the following main result.

Theorem 1.1

Let S be a finite idempotent semigroup. Then S is finitely related.

Here is the brief outline of the paper. The next, preliminary section is divided into three parts. First, we are going to invoke few criteria (from [9, 17]) for a finite algebra to be finitely related. Along the way, we are going to introduce a handy concept of an n-scheme of terms, and specialise all these concepts to semigroups and words, respectively. Then we are going to review the lattice of all varieties of bands (idempotent semigroups) and proceed to a full effective description of their equational theories. Finally, we complete the second section by some auxiliary results that will be used in the proof of the previous theorem, presented in the third section. This proof uses induction on the ‘height’ of the variety that S generates in the lattice of all band varieties, depicted in Fig. 1, taking the mentioned result on regular bands as the induction basis. We first resolve the case when S generates one of the irreducible varieties in that lattice (Theorem 3.1) and then demonstrate how to derive Theorem 1.1 in its full generality from the irreducible case (Theorem 3.2).

Fig. 1

The lattice of all varieties of bands

2 Preliminaries

2.1 Term schemes and criteria for finitely related finite algebras

Let $f:A^n\rightarrow A$ be an n-ary operation on the set A. For $i,j\in \mathbf {n}=\{1,\ldots ,n\}$, $i<j$, we define an operation $f_{ij}:A^n\rightarrow A$ (sometimes called an identification minor of f) by

$$\begin{aligned} f_{ij}(x_1,\ldots ,x_n) = f(x_1,\ldots ,x_{i-1},x_j,x_{i+1},\ldots ,x_j,\ldots ,x_n); \end{aligned}$$

in other words, $f_{ij}$ is obtained from f by identifying the variable $x_i$ with $x_j$. Similarly, if $\mathsf {t}=\mathsf {t}(x_1,\ldots ,x_n)$ is a term of a given similarity type, then by $\mathsf {t}^{(ij)}$ we denote the term obtained from $\mathsf {t}$ by replacing each occurrence of $x_i$ in it by $x_j$; furthermore, by convention we define $\mathsf {t}^{(ji)}$ to be $\mathsf {t}^{(ij)}$.

As usual, we say that an operation $f:A^n\rightarrow A$ depends on its ith variable $x_i$, $i\in \mathbf {n}$, if there exist $a_1,\ldots ,a_{i-1},a_{i+1},\ldots ,a_n,b,c\in A$ such that

$$\begin{aligned} f(a_1,\ldots ,a_{i-1},b,a_{i+1},\ldots ,a_n) \ne f(a_1,\ldots ,a_{i-1},c,a_{i+1},\ldots ,a_n). \end{aligned}$$

For example, the identification minor $f_{ij}$ does not depend on $x_i$. In turn, as another example, the ith projection operation fails to depend on any of its variables but $x_i$.

Now let $\mathcal {V}$ be a variety and assume

$$\begin{aligned} \mathcal {S}=\{\mathsf {t}_{ij}:\ 1\le i<j\le n\} \end{aligned}$$

is a family of terms over $X_n=\{x_1,\ldots ,x_n\}$ of the similarity type of $\mathcal {V}$ satisfying the following conditions:

• (D) For each $\mathbf {A}\in \mathcal {V}$, the term operation $\mathsf {t}_{ij}^{\mathbf {A}}(x_1,\ldots ,x_n)$ does not depend on the variable $x_i$.

• (C1) For any four distinct $1\le i,j,p,q\le m$ such that $i<j$ and $p<q$, $\mathcal {V}$ satisfies the identity

  $$\begin{aligned} \mathsf {t}_{ij}^{(pq)} \approx \mathsf {t}_{pq}^{(ij)}. \end{aligned}$$

• (C2) For any three $1\le i<j<k\le n$, $\mathcal {V}$ satisfies the identities

  $$\begin{aligned} \mathsf {t}_{ij}^{(jk)} \approx \mathsf {t}_{jk}^{(ik)} \approx \mathsf {t}_{ik}^{(jk)}. \end{aligned}$$

The condition (D) is called dependency, while (C1) and (C2) are the consistency conditions; the family $\mathcal {S}$ is called an n-scheme of terms for $\mathcal {V}$. Bearing in mind Definition 2.3 and Notation 2.7 from [9] it is an easy exercise to see that this is just equivalent to the notion of an $(n,n-1)$-scheme introduced in that paper.

Similarly, it is very easy to see that the following holds.

Lemma 2.1

Let $\mathcal {V}$ be an arbitrary variety and $\mathsf {t}(x_1,\ldots ,x_n)$ a term of the same similarity type as $\mathcal {V}$. The family of all identification minors of $\mathsf {t}$,

$$\begin{aligned} \left\{ \mathsf {t}^{(ij)}:\ 1\le i<j\le n\right\} , \end{aligned}$$

is an n-scheme of terms for $\mathcal {V}$.

Again following [9], we say that an n-scheme $\mathcal {S}=\{\mathsf {t}_{ij}:\ 1\le i<j\le m\}$ for $\mathcal {V}$ comes from the term $\mathsf {t}$ if $\mathcal {S}$ is $\mathcal {V}$-equivalent to the family of all identification minors of $\mathsf {t}$ in the sense that $\mathcal {V}$ satisfies the identities

$$\begin{aligned} \mathsf {t}_{ij} \approx \mathsf {t}^{(ij)} \end{aligned}$$

for all $1\le i<j\le n$.

The following characterisation is part of Theorem 2.9 from [9], see also [14, 17,18,19].

Theorem 2.2

Let $\mathbf {A}$ be a finite algebra, and let $\mathcal {V}$ be the variety generated by $\mathbf {A}$. The following are equivalent:

• (1) $\mathbf {A}$ is finitely related.

• (2) There exists $n_0\ge |A|$ such that for all $n>n_0$, every n-scheme of terms for $\mathcal {V}$ comes from a term.

• (3) There exists $n_0\ge |A|$ such that for all $n>n_0$, an operation $f:A^n\rightarrow A$ is a term operation of $\mathbf {A}$ whenever all minors $f_{ij}$ ($i,j\in \mathbf {n}$, $i<j$) are term operations of $\mathbf {A}$.

Here we immediately invoke Remark 2.12 from [9] which provides an argument that in checking if a finite algebra $\mathbf {A}$ satisfies condition (3) above, it can be assumed that the operation $f:A^n\rightarrow A$ is essential, i.e. that it depends on all of its variables. Therefore, we will effectively use the previous theorem in the form where the condition (3) is replaced by

(3’):

There exists $n_0\ge |A|$ such that for all $n>n_0$, an operation $f:A^n\rightarrow A$ depending on all of its variables is a term operation of $\mathbf {A}$ whenever all minors $f_{ij}$ ($i,j\in \mathbf {n}$, $i<j$) are term operations of $\mathbf {A}$.

Notice that for semigroups and semigroup varieties all definitions and results mentioned above remain valid when we replace terms by words (i.e. elements of the free semigroup $X_n^+$), term operations by operations induced by words, etc., even though, strictly speaking, words are not terms. However, it is true that every term operation on a semigroup is induced by a word and vice versa. Therefore, it is meaningful to define the notion of an n-scheme of words for a semigroup variety, and the ‘semigroup version’ of Theorem 2.2 holds as well: a finite semigroup S is finitely related if and only if every n-scheme of words for the variety generated by S comes from a single word (provided n is large enough) if and only if the condition (3’) holds with respect to operations induced by words. It was proved in [17] that this is the case when S is a regular band, that is, a finite idempotent semigroup satisfying $xyxzx\approx xyzx$. The aim of this paper is to extend this to all finite bands in an inductive manner, taking the result of [17] as a basis of the induction. Hence, in the next subsection we need to gather some basic information about varieties of bands and few auxiliary results describing their equational theories.

2.2 Varieties of bands and their equational theories

The variety of all bands will be denoted by $\mathcal {B}$. It is known that any semigroup variety containing $\mathcal {B}$ (including $\mathcal {B}$ itself) is not generated by a finite semigroup [20], while every proper subvariety of $\mathcal {B}$ is finitely generated (see [6, 10, 11]).

In what follows, we adopt the notation of [13] for certain operators acting on words; we briefly recall it for completeness. For a word $\mathsf {w}$ over a (finite) alphabet X, let $c(\mathsf {w})$ denote the content of $\mathsf {w}$, the set of all letters occurring in $\mathsf {w}$. Further, let $s(\mathsf {w})$ denote the longest prefix of $\mathsf {w}$ containing all but one of the letters from $c(\mathsf {w})$ (so that $|c(s(\mathsf {w}))|=|c(\mathsf {w})|-1$ and $s(\mathsf {w})$ is maximal with this property), while $\sigma (\mathsf {w})$ is the last letter to occur in $\mathsf {w}$ from the left (implying that $s(\mathsf {w})\sigma (\mathsf {w})$ is the shortest prefix of $\mathsf {w}$ with the same content as $\mathsf {w}$). Dually, let $e(\mathsf {w})$ be the longest suffix of $\mathsf {w}$ containing all but one of the letters from $c(\mathsf {w})$, and let $\varepsilon (\mathsf {w})$ be the last letter in $\mathsf {w}$ to occur from the right.

Define an operator b on words by induction on the size of their content such that $b(\varnothing )=\varnothing$ (here $\varnothing$ stands for the empty word) and

$$\begin{aligned} b(\mathsf {w}) = bs(\mathsf {w})\sigma (\mathsf {w})\varepsilon (\mathsf {w})be(\mathsf {w}) \end{aligned}$$

(note the concatenation of word operators, where $bs(\mathsf {w})$ means $b(s(\mathsf {w}))$, etc.).

Theorem 2.3

(cf. Lemma 2.7 and Theorem 2.9 of [12]) Let X be an alphabet and $\mathsf {u},\mathsf {v}\in X^+$. Then $\mathsf {u}\approx \mathsf {v}$ holds in $\mathcal {B}$ if and only if $b(\mathsf {u})=b(\mathsf {v})$. In particular, for any word $\mathsf {w}$ we have that the identity

$$\begin{aligned} \mathsf {w}\approx s(\mathsf {w})\sigma (\mathsf {w})\varepsilon (\mathsf {w})e(\mathsf {w}) \end{aligned}$$

holds in any band.

This immediately implies the following well-known fact (recorded, e.g., as Corollary 2.3 in [13]).

Corollary 2.4

Let $\mathsf {u},\mathsf {v},\mathsf {w}$ be words such that $c(\mathsf {v})\subseteq c(\mathsf {u})=c(\mathsf {w})$. Then the identity $\mathsf {u}\mathsf {v}\mathsf {w}\approx \mathsf {u}\mathsf {w}$ holds in $\mathcal {B}$.

Proof

Under the given conditions, $s(\mathsf {u}\mathsf {v}\mathsf {w})=s(\mathsf {u})=s(\mathsf {u}\mathsf {w})$ and $\sigma (\mathsf {u}\mathsf {v}\mathsf {w})=\sigma (\mathsf {u})=\sigma (\mathsf {u}\mathsf {w})$, and, dually, $e(\mathsf {u}\mathsf {v}\mathsf {w})=e(\mathsf {w})=e(\mathsf {u}\mathsf {w})$ and $\varepsilon (\mathsf {u}\mathsf {v}\mathsf {w})=\varepsilon (\mathsf {w})=\varepsilon (\mathsf {u}\mathsf {w})$, so the result follows by Theorem 2.3. $\square$

The description of the lattice $\mathscr {L}(\mathcal {B})$ of all subvarieties of $\mathcal {B}$ is today still considered as one of the most glaring success stories of the theory of semigroup varieties; it was achieved independently by Biryukov [6], Fennemore [10], and Gerhard [11], whereas a more ‘economical’ and coherent treatment of the subject was given later in [13]. Figure  1 provides a diagram of this lattice: here $\mathcal {SL}$, $\mathcal {LZ}$ and $\mathcal {RZ}$ are respectively the varieties of semilattices, left zero and right zero bands.

Of particular importance are the two sequences of join- and meet-irreducible varieties $\mathcal {A}_m$ and $\mathcal {B}_m$, $m\ge 2$, as well as their duals $\overline{\mathcal {A}_m}$ and $\overline{\mathcal {B}_m}$ – any proper (i.e. finitely generated) band variety not contained in $\mathcal {SL}\vee \mathcal {LZ}\vee \mathcal {RZ}$ (the ‘bottom cube’) is a join of a pair of these. In fact, we shall first prove that any finite band generating one of the varieties $\mathcal {A}_m$, $\mathcal {B}_m$ is finitely related; by left-right duality, this will extend to $\overline{\mathcal {A}_m}$ and $\overline{\mathcal {B}_m}$, and then we shall show how to use this fact to prove finite relatedness for any finite band generating a proper subvariety of $\mathcal {B}$. The varieties $\mathcal {LRB}$ and $\mathcal {RRB}$ are the varieties of left regular and right regular bands defined by identities $xyx\approx xy$ and $xyx\approx yx$, respectively. Their join is the variety of regular bands that is the subject of Theorem 6.2 of [17]. As we remarked earlier, our approach will be inductive with respect to the chains formed by varieties $\mathcal {A}_m$, $\mathcal {B}_m$ and their duals, with the latter result from [17] serving as a basis of that induction.

For technical convenience in our main argument it will be useful to select and fix finite bands $A_m,B_m$, $m\ge 2$ (as well as their dual semigroups $\overline{A_m}$ and $\overline{B_m}$), such that $A_m$ generates the variety $\mathcal {A}_m$ and $B_m$ generates $\mathcal {B}_m$. (For example, one can choose $A_2$ to be the two-element left zero band, $B_2$ to be $A_2$ with an identity element adjoined, etc. Note that we can choose these bands so that $|A_2|<|B_2|<|A_3|< |B_3|<\ldots$ holds.)

Our main task at this moment is to describe the equational theories of the considered band varieties, following the approach laid out in [13]. To this end, we introduce word functions $h_m$ and $i_m$ for $m\ge 2$ and their duals, $\overline{h}_m,\overline{i}_m$, in the sense that if $\overline{\mathsf {w}}$ denotes the reverse of the word $\mathsf {w}$ we have $\overline{t}_m(\mathsf {w})=\overline{t_m(\overline{\mathsf {w}})}$ for $t\in \{h,i\}$:

• $t_m(\varnothing )=\varnothing$ for all $m\ge 2$ and $t\in \{h,i\}$;

• $h_2(\mathsf {w})$ is the first letter of $\mathsf {w}$ from the left (the head of $\mathsf {w}$);

• $i_2(\mathsf {w})$ is the word obtained from $\mathsf {w}$ by retaining only the first occurrence from the left of each letter (the initial part of $\mathsf {w}$, also defined recursively by $i_2(\mathsf {w})=i_2s(\mathsf {w})\sigma (\mathsf {w})$);

• for $m\ge 3$ and $t\in \{h,i\}$ we set

  $$\begin{aligned} t_m(\mathsf {w}) = t_ms(\mathsf {w})\sigma (\mathsf {w})\overline{t}_{m-1}(\mathsf {w}). \end{aligned}$$

The key feature of these functions is expressed in the following statement.

Theorem 2.5

([13]) Let $m\ge 2$ and let $\mathsf {u},\mathsf {v}$ be two words.

• $\mathcal {A}_m$ satisfies $\mathsf {u}\approx \mathsf {v}$ if and only if $h_m(\mathsf {u})=h_m(\mathsf {v})$.

• $\mathcal {B}_m$ satisfies $\mathsf {u}\approx \mathsf {v}$ if and only if $i_m(\mathsf {u})=i_m(\mathsf {v})$.

Analogous equivalences hold for the dual varieties $\overline{\mathcal {A}_m}$ and $\overline{\mathcal {B}_m}$ and functions $\overline{h}_m$ and $\overline{i}_m$, respectively.

The next few properties will be used in our proofs.

Lemma 2.6

• (1) Let $t\in \{h,i\}$. If $m\ge 3$ or $t_m=i_2$ then $st_m(\mathsf {w})=t_ms(\mathsf {w})$ and $e\overline{t}_m(\mathsf {w})=\overline{t}_me(\mathsf {w})$ for any word $\mathsf {w}$.

• (2) Let $t\in \{h,i\}$. If $m\ge 4$ or $t_m=i_3$ then

  $$\begin{aligned} bt_m(\mathsf {w}) = b(t_ms(\mathsf {w})\sigma (\mathsf {w})\varepsilon (\mathsf {w})\overline{t}_{m-1}e(\mathsf {w})) \end{aligned}$$

  and

  $$\begin{aligned} b\overline{t}_m(\mathsf {w}) = b(t_{m-1}s(\mathsf {w})\sigma (\mathsf {w})\varepsilon (\mathsf {w})\overline{t}_me(\mathsf {w})) \end{aligned}$$

  for any word $\mathsf {w}$.

• (3) Let $t\in \{h,i,\overline{h},\overline{i}\}$ and let $\mathsf {u},\mathsf {v}$ be any words. If $m\ge 2$ then $bt_m(\mathsf {u})=bt_m(\mathsf {v})$ implies $t_m(\mathsf {u})=t_m(\mathsf {v})$.

• (4) Let $t\in \{h,i\}$. If $m\ge 3$ then

  $$\begin{aligned} \overline{t}_m(\mathsf {w}) = t_{m-1}(\mathsf {w})\varepsilon (\mathsf {w})\overline{t}_me(\mathsf {w}) \end{aligned}$$

  for any word $\mathsf {w}$.

Proof

The first part of (1) is just [13, Lemma 3.2(ii)], while the second part is dual to the first one and follows from it, as $e\overline{t}_m(\mathsf {w})=e\overline{t_m(\overline{\mathsf {w}})}=\overline{st_m(\overline{\mathsf {w}})}=\overline{t_ms(\overline{\mathsf {w}})}=\overline{t_m(\overline{e(\mathsf {w})})}= \overline{t}_me(\mathsf {w})$. (2)–(4) are Lemma 3.3(iii), (v), Lemma 4.1 and Lemma 3.3(ii) of [13], respectively, where (2) and (3) are reformulated in terms of the operator b, bearing in mind Theorem 2.3. $\square$

Lemma 2.7

Let $\mathcal {X}\in \{\mathcal {A},\mathcal {B}\}$. Assume that the variety $\mathcal {X}_m$ satisfies the identity $\mathsf {u}\approx \mathsf {v}$, where $|c(\mathsf {u})|,|c(\mathsf {v})|\ge 2$. Then it also satisfies $s(\mathsf {u})\approx s(\mathsf {v})$.

Proof

Consider first the case when $\mathcal {X}_m=\mathcal {A}_2$. Since both $\mathsf {u}$ and $\mathsf {v}$ contain at least two letters, we have $h_2s(\mathsf {u})=h_2(\mathsf {u})=h_2(\mathsf {v})=h_2s(\mathsf {v})$, and the lemma follows. Otherwise, if either $\mathcal {X}_m=\mathcal {B}_2$ or $m\ge 3$, let $t_m$ be the corresponding word function in the sense of Theorem 2.5. By the given conditions we have $t_m(\mathsf {u})=t_m(\mathsf {v})$, which in turn implies $st_m(\mathsf {u})=st_m(\mathsf {v})$. Then Lemma 2.6(1) tells us that $t_ms(\mathsf {u})=t_ms(\mathsf {v})$ (since we assumed that $t_m\ne h_2$). Another application of Theorem 2.5 yields that $\mathcal {X}_m$ satisfies $s(\mathsf {u})\approx s(\mathsf {v})$. $\square$

2.3 Some auxiliary results

As Theorem 2.2 suggests, we will be concerned with essential operations $f:S^n\rightarrow S$ on a finite (idempotent) semigroup S such that all of its minors $f_{ij}$ are induced by words. In the next lemma we are looking at some consequences of such a setting.

Lemma 2.8

Let S be a finite semigroup, and let $f:S^n\rightarrow S$ be an operation depending on all of its variables such that for any $i,j\in \mathbf {n}$, $i<j$, there is a word $\mathsf {w}_{ij}$ satisfying $f_{ij}=\mathsf {w}_{ij}^S$.

• (1) $\{\mathsf {w}_{ij}:\ 1\le i<j\le n\}$ is an n-scheme of words for the semigroup variety generated by S.

• (2) If the variety generated by S contains $\mathcal {SL}$ and $n\ge |S|+\,4$ then $c(\mathsf {w}_{ij})=X_n\setminus \{x_i\}$.

Proof

• (1) Easy, and largely analogous to Lemma 2.1, dealing with minors of operations instead of terms.

• (2) Since f depends on all of its variables (and thus in particular on $x_k$, $k\ne i$), there exist $a_1,\ldots ,a_{k-1},a_{k+1},\ldots ,a_n,b,c\in S$ such that

  $$\begin{aligned} f(a_1,\ldots ,a_{k-1},b,a_{k+1},\ldots ,a_n)\ne f(a_1,\ldots ,a_{k-1},c,a_{k+1},\ldots ,a_n). \end{aligned}$$

  The pigeonhole principle ensures that there exist $p,q\in \mathbf {n}\setminus \{i,j,k\}$, $p<q$, such that $a_p=a_q$. Hence, just as in [17, Lemma 2.6], $f_{pq}=\mathsf {w}_{pq}^S$ depends on $x_k$. However, by (1), S satisfies the identity $\mathsf {w}_{pq}^{(ij)}\approx \mathsf {w}_{ij}^{(pq)}$ and so $x_k\in c(\mathsf {w}_{pq}^{(ij)})=c(\mathsf {w}_{ij}^{(pq)})$, ensuring that $\mathsf {w}_{ij}$ must contain $x_k$, since $k\ne i$. $\square$

In the following, n-schemes of words $\{\mathsf {w}_{ij}:\ 1\le i<j\le n\}$ over $X_n$ such that $c(\mathsf {w}_{ij})=X_n\setminus \{x_i\}$ will be called essential; so, the above result states that essential operations on finite semigroups whose varieties contain nontrivial semilattices with all minors induced by words give rise to essential n-schemes, provided n is large enough.

Lemma 2.9

Let $\{\mathsf {w}_{ij}:\ 1\le i<j\le n\}$ be an essential n-scheme of words for a semigroup variety $\mathcal {V}$ containing $\mathcal {B}_2$ (the variety of left regular bands), where $n\ge 5$. Then there exists a unique permutation $\pi$ of $\mathbf {n}$ such that for any $i<j$,

$$\begin{aligned} i_2(\mathsf {w}_{ij}) = x_{\alpha _1}\cdots x_{\alpha _{n-1}}, \end{aligned}$$

where the sequence $\pi ^{(ij)}=(\alpha _1,\ldots ,\alpha _{n-1})$ is obtained from $(1\pi ,\ldots ,n\pi )$ by replacing i by j and then deleting the right one of the two occurrences of j. Furthermore, if the given essential scheme comes from a word $\mathsf {w}$ then we must have $i_2(\mathsf {w})=x_{1\pi }\cdots x_{n\pi }$.

Proof

By the very definition of an (essential) n-scheme of words for a variety, any scheme for a variety $\mathcal {V}$ is also a scheme for any of its subvarieties, and so is the case for the given scheme with respect to $\mathcal {B}_2$. As already discussed, $\mathcal {B}_2$ is generated by the 3-element band $B_2$ (obtained by adjoining an identity element to the 2-element left zero band), and by Lemma 6.1 of [17], $B_2$ is finitely related with degree at most 4. By [9, Lemma 2.6], there exists a unique operation $f:B_2^n\rightarrow B_2$ such that $f_{ij}=\mathsf {w}_{ij}^{B_2}$ for all $1\le i<j\le n$. To see that f depends on all of its variables, fix $k\in \mathbf {n}$ and $p,q\in \mathbf {n}\setminus \{k\}$, $p<q$. As $f_{pq}=\mathsf {w}_{pq}^{B_2}$ and $x_k\in c(\mathsf {w}_{pq})$, $f_{pq}$ depends on $x_k$, so there exist $a_1,\ldots , a_{k-1},a_{k+1},\ldots ,a_n,b,c\in B_2$ such that $f_{pq}(a_1,\ldots ,a_{k-1},b,a_{k+1},\ldots ,a_n)\ne f_{pq}(a_1,\ldots , a_{k-1},c,a_{k+1},\ldots ,a_n)$. This immediately implies that f depends on $x_k$.

Hence, by [17, Lemma 6.1], f is induced by a word $\mathsf {w}$ such that $c(\mathsf {w})=X_n$. Now it is routine to see that the permutation $\pi \in \mathbb {S}_\mathbf {n}$ satisfying

$$\begin{aligned} i_2(\mathsf {w}) = x_{1\pi }\cdots x_{n\pi } \end{aligned}$$

meets all the requirements of the lemma. It is unique because if $\pi '$ would be another permutation with the required properties, then it would follow that the given scheme (with respect to $\mathcal {B}_2$) also comes from the word $\mathsf {w}'=x_{1\pi '}\cdots x_{n\pi '}$, whence the uniqueness of f implies that $(\mathsf {w}')^{B_2}=f$. Therefore, $\mathcal {B}_2$ satisfies $\mathsf {w}'\approx \mathsf {w}$, implying $i_2(\mathsf {w}')=i_2(\mathsf {w})$ and so $\pi '=\pi$. $\square$

For an essential scheme of words satisfying the assumptions of the above lemma, we will call $\pi$ the associated permutation of the scheme.

We proceed with a technical lemma before we learn another important property of essential n-schemes of words over irreducible band varieties.

Lemma 2.10

Let $k\in \mathbf {n}$, and let $\mathsf {w}\in X_n^+$ be such that $c(\mathsf {w})=X_n\setminus \{x_k\}$ and $\sigma (\mathsf {w})=x_l$. Furthermore, let $p,q\in \mathbf {n}\setminus \{l\}$ such that $p<q$. Then $s(\mathsf {w})^{(pq)}=s(\mathsf {w}^{(pq)})$.

Proof

We start by writing $\mathsf {w}$ in the form

$$\begin{aligned} \mathsf {w}=s(\mathsf {w})x_l\mathsf {u}\end{aligned}$$

for some word $\mathsf {u}$, implying $\mathsf {w}^{(pq)}=s(\mathsf {w})^{(pq)}x_l\mathsf {u}^{(pq)}$. If $q\ne k$ then $c(\mathsf {w}^{(pq)})=X_n\setminus \{x_k,x_p\}$ and $c(s(\mathsf {w})^{(pq)})=X_n\setminus \{x_l,x_k,x_p\}$, which immediately gives $s(\mathsf {w}^{(pq)})=s(\mathsf {w})^{(pq)}$. The same conclusion follows if $q=k$ upon noticing that in such a case we have $c(\mathsf {w}^{(pq)})=X_n\setminus \{x_p\}$ and $c(s(\mathsf {w})^{(pq)})=X_n\setminus \{x_l,x_p\}$. $\square$

Lemma 2.11

Let $n\ge 5$, let $\mathcal {S}=\{\mathsf {w}_{ij}:\ 1\le i<j\le n\}$ be an essential n-scheme of words for $\mathcal {X}_m$, where $\mathcal {X}\in \{\mathcal {A},\mathcal {B}\}$ and either $m\ge 3$ or $\mathcal {X}_m=\mathcal {B}_2$. Let $\pi$ be the associated permutation of $\mathcal {S}$ (which exists by Lemma 2.9) and let $l=n\pi$. Then

$$\begin{aligned} \mathcal {S}' = \left\{ s(\mathsf {w}_{ij}):\ 1\le i<j\le n,\ l\not \in \{i,j\}\right\} \end{aligned}$$

is an $(n-1)$-scheme for $\mathcal {X}_m$ over variables $X_n\setminus \{x_l\}$.

Proof

Note that if $l\not \in \{i,j\}$ then $\sigma (\mathsf {w}_{ij})=x_l$ and so $c(s(\mathsf {w}_{ij}))=X_n\setminus \{x_i,x_l\}$. Thus (D) holds.

Furthermore, if $p<q$ are such that $\{p,q\}\cap \{i,j,l\}=\varnothing$ then by Lemma 2.10 we have $s(\mathsf {w}_{ij})^{(pq)}=s(\mathsf {w}_{ij}^{(pq)})$ and $s(\mathsf {w}_{pq})^{(ij)}=s(\mathsf {w}_{pq}^{(ij)})$. Further the assumption that $\mathcal {X}_m$ satisfies $\mathsf {w}_{ij}^{(pq)}\approx \mathsf {w}_{pq}^{(ij)}$ implies, by Lemma 2.7, the identity $s(\mathsf {w}_{ij}^{(pq)})\approx s(\mathsf {w}_{pq}^{(ij)})$. Hence, $\mathcal {X}_m$ satisfies $s(\mathsf {w}_{ij})^{(pq)}\approx s(\mathsf {w}_{pq})^{(ij)}$, and so $\mathcal {S}'$ satisfies (C1).

Now let $i<j<p$ be such that $l\not \in \{i,j,p\}$. Again, Lemma 2.10 implies that $s(\mathsf {w}_{ij})^{(jp)}=s(\mathsf {w}_{ij}^{(jp)})$, $s(\mathsf {w}_{jp})^{(ip)}=s(\mathsf {w}_{jp}^{(ip)})$ and $s(\mathsf {w}_{ip})^{(jp)}=s(\mathsf {w}_{ip}^{(jp)})$ (the lemma was applied over the alphabet $X_n\setminus \{x_i\}$ in the first and the third case, while it was applied over $X_n\setminus \{x_j\}$ in the second case). Since, by assumption, $\mathcal {X}_m$ satisfies the identities $\mathsf {w}_{ij}^{(jp)}\approx \mathsf {w}_{jp}^{(ip)}\approx \mathsf {w}_{ip}^{(jp)}$, it also satisfies the identities $s(\mathsf {w}_{ij}^{(jp)})\approx s(\mathsf {w}_{jp}^{(ip)})\approx s(\mathsf {w}_{ip}^{(jp)})$ by Lemma 2.7. We conclude that $\mathcal {X}_m$ satisfies $s(\mathsf {w}_{ij})^{(jp)}\approx s(\mathsf {w}_{jp})^{(ip)}\approx s(\mathsf {w}_{ip})^{(jp)}$, hence (C2) holds for $\mathcal {S}'$ as well. $\square$

We are now ready and equipped to present our main arguments.

3 The main proofs

Theorem 3.1

For any $m\ge 2$ and $T\in \{A,B\}$, the bands $T_m$ and $\overline{T_m}$ are finitely related.

Proof

We use induction on m. If $m=2$, the result already follows from [17, Theorem 6.2]. Hence fix $m\ge 3$ and assume that the statement is true for values of indices up to $m-1$.

We are going to show that $T_m$ is finitely related by verifying condition (3’) in Theorem 2.2 with $n\ge n_0 = \max (|T_m|+4,m+3)$. So, under these assumptions, let $f:T_m^n\rightarrow T_m$ be an operation that depends on all of its variables such that for all $i,j\in \mathbf {n}$, $i<j$, we have that the operation $f_{ij}$ is induced by a word. Let us select words $\mathsf {w}_{ij}\in X_n^+$, $1\le i<j\le n$, such that $f_{ij}=\mathsf {w}_{ij}^{T_m}$. Since the variety $\mathcal {X}_m$ generated by $T_m$ contains $\mathcal {SL}$, Lemma 2.8 tells us that $c(\mathsf {w}_{ij})=X_n\setminus \{x_i\}$, so that $\mathcal {S}=\{\mathsf {w}_{ij}:\ 1\le i<j\le n\}$ is an essential n-scheme of words for $\mathcal {X}_m$.

Since $\mathcal {B}_2$ is contained in $\mathcal {X}_m$ and $n\ge m+3>5$, Lemma 2.9 ensures the existence (and uniqueness) of the associated permutation $\pi$ of the scheme $\mathcal {S}$. Let us denote $k=(n-1)\pi$ and $l=n\pi$.

Now, since $\mathcal {S}$ is an n-scheme of words for $\mathcal {X}_m$, it is also an n-scheme of words for any of its subvarieties, and thus in particular for $\overline{\mathcal {X}_{m-1}}$. This variety is generated by the band $\overline{T_{m-1}}$ which is finitely related by the inductive assumption. Hence, Theorem 2.2 implies that $\mathcal {S}$, considered as a scheme for $\overline{\mathcal {X}_{m-1}}$, comes from a word, say $\widehat{\mathsf {u}}$. Equivalently, there is a word operation $g:\overline{T_{m-1}}^n\rightarrow \overline{T_{m-1}}$ such that $g_{ij}=\mathsf {w}_{ij}^{\overline{T_{m-1}}}$ holds for all $1\le i<j\le n$.

Similarly, by Lemma 2.11, the family of words $\mathcal {S}'=\{s(\mathsf {w}_{ij}):\ 1\le i<j\le n,\ l\not \in \{i,j\}\}$ is an $(n-1)$-scheme of words for $\mathcal {X}_m$ (and thus for $\overline{\mathcal {X}_{m-1}}$) over the set of variables $X_n\setminus \{x_l\}$. Again, by employing the inductive hypothesis (and bearing in mind that $n-1\ge (m-1)+3$ and $n-1\ge (|T_m|-1)+4\ge |\overline{T_{m-1}}|+4$), we find a word $\widetilde{\mathsf {u}}$ such that $\mathcal {S}'$ comes from $\widetilde{\mathsf {u}}$; in other words, there is a word operation $h:\overline{T_{m-1}}^{n-1}\rightarrow \overline{T_{m-1}}$ with $h_{ij}= s(\mathsf {w}_{ij})^{\overline{T_{m-1}}}$ for all $i<j$ such that $l\not \in \{i,j\}$.

Now define

$$\begin{aligned} \mathsf {w}= s(\mathsf {w}_{k'l'})x_k\widetilde{\mathsf {u}}x_l\widehat{\mathsf {u}}, \end{aligned}$$

where $k'=\min (k,l)$ and $l'=\max (k,l)$. We are going to argue that $f=\mathsf {w}^{T_m}$ whence Theorem 2.2 yields that $T_m$ is finitely related. $\square$

Claim

If $p,q\in \mathbf {n}$, $p<q$, are such that $\{p,q\}\cap \{k,l\}=\varnothing$ then the identity

$$\begin{aligned} \mathsf {w}^{(pq)} \approx \mathsf {w}_{pq} \end{aligned}$$

holds in $\mathcal {X}_m$ (and so in $T_m$).

Proof of Claim

We have

$$\begin{aligned} \mathsf {w}^{(pq)} = \left( s\left( \mathsf {w}_{k'l'}\right) \right) ^{(pq)}x_k\widetilde{\mathsf {u}}^{(pq)}x_l\widehat{\mathsf {u}}^{(pq)}=s\left( \mathsf {w}_{k'l'}^{(pq)}\right) x_k\widetilde{\mathsf {u}}^{(pq)}x_l\widehat{\mathsf {u}}^{(pq)}, \end{aligned}$$

(3.1)

where the second equality follows by Lemma 2.10 using $c(\mathsf {w}_{k'l'})=X_n\setminus \{x_{k'}\}$. Furthermore, by (C1), $\mathcal {X}_m$ satisfies $\mathsf {w}_{k'l'}^{(pq)}\approx \mathsf {w}_{pq}^{(k'l')}$, so by Lemma 2.7 it also satisfies $s(\mathsf {w}_{k'l'}^{(pq)})\approx s(\mathsf {w}_{pq}^{(k'l')})$. Since $\{p,q\}\cap \{k,l\}=\varnothing$, the sequence $\pi ^{(pq)}$ must have the form $(\alpha _1,\ldots ,\alpha _{n-3},k,l)$ (where the subsequence $(\alpha _1,\ldots ,\alpha _{n-3})$ is a certain permutation of $\mathbf {n}\setminus \{k,l,p\}$). Therefore, we may highlight the first occurrence from the left of each letter from $c(\mathsf {w}_{pq})$ in $\mathsf {w}_{pq}$ by writing

$$\begin{aligned} \mathsf {w}_{pq}=x_{\alpha _1}\mathsf {u}_1x_{\alpha _2}\cdots x_{\alpha _{n-3}}\mathsf {u}_{n-3}x_k\mathsf {u}_{n-2}x_l\mathsf {v}\end{aligned}$$

for some (possibly empty) words $\mathsf {u}_1,\ldots ,\mathsf {u}_{n-2},\mathsf {v}$. This yields

$$\begin{aligned} \mathsf {w}_{pq}^{(k'l')}=x_{\alpha _1}\mathsf {u}_1x_{\alpha _2}\cdots x_{\alpha _{n-3}}\mathsf {u}_{n-3} x_{l'}\mathsf {u}_{n-2}^{(k'l')}x_{l'}\mathsf {v}^{(k'l')}, \end{aligned}$$

implying

$$\begin{aligned} s(\mathsf {w}_{pq}^{(k'l')})=x_{\alpha _1}\mathsf {u}_1x_{\alpha _2}\cdots x_{\alpha _{n-3}}\mathsf {u}_{n-3}=s^2(\mathsf {w}_{pq}). \end{aligned}$$

Bearing in mind (3.1), we deduce that

$$\begin{aligned} \mathsf {w}^{(pq)} \approx s(\mathsf {w}_{pq}^{(k'l')})x_k\widetilde{\mathsf {u}}^{(pq)}x_l\widehat{\mathsf {u}}^{(pq)} = s^2(\mathsf {w}_{pq})x_k\widetilde{\mathsf {u}}^{(pq)}x_l\widehat{\mathsf {u}}^{(pq)} \end{aligned}$$

holds in $\mathcal {X}_m$. By applying Theorem 2.5 and the recursion for $t_m$ twice, we get

$$\begin{aligned} t_m(\mathsf {w}^{(pq)})&= t_m\bigl (s^2(\mathsf {w}_{pq})x_k\widetilde{\mathsf {u}}^{(pq)}x_l\widehat{\mathsf {u}}^{(pq)}\bigr ) \\&= t_m\bigl (s^2(\mathsf {w}_{pq})x_k\widetilde{\mathsf {u}}^{(pq)}\bigr )x_l\overline{t}_{m-1}\bigl (s^2(\mathsf {w}_{pq})x_k\widetilde{\mathsf {u}}^{(pq)}x_l\widehat{\mathsf {u}}^{(pq)}\bigr )\\&= t_ms^2(\mathsf {w}_{pq})x_k\overline{t}_{m-1}\bigl (s^2(\mathsf {w}_{pq})x_k\widetilde{\mathsf {u}}^{(pq)}\bigr )x_l\overline{t}_{m-1}\bigl (s^2(\mathsf {w}_{pq})x_k\widetilde{\mathsf {u}}^{(pq)}x_l\widehat{\mathsf {u}}^{(pq)}\bigr ). \end{aligned}$$

However, by induction assumption on $\mathcal {S}'$ for $\overline{\mathcal {X}_{m-1}}$ we have that $\overline{\mathcal {X}_{m-1}}$ satisfies $\widetilde{\mathsf {u}}^{(pq)}\approx s(\mathsf {w}_{pq})$, and by induction assumption on $\mathcal {S}$ for $\overline{\mathcal {X}_{m-1}}$ we have that $\overline{\mathcal {X}_{m-1}}$ satisfies $\widehat{\mathsf {u}}^{(pq)}\approx \mathsf {w}_{pq}$. We know that $\sigma (\mathsf {w}_{pq})=x_l$, $s(\mathsf {w}_{pq})= x_{\alpha _1}\cdots x_{\alpha _{n-3}}\mathsf {u}_{n-3}x_k\mathsf {u}_{n-2}$, $\sigma s(\mathsf {w}_{pq})=x_k$, and $s^2(\mathsf {w}_{pq})= x_{\alpha _1}\cdots x_{\alpha _{n-3}}\mathsf {u}_{n-3}$. Thus

$$\begin{aligned} s^2(\mathsf {w}_{pq})x_k\widetilde{\mathsf {u}}^{(pq)} \approx s^2(\mathsf {w}_{pq})\sigma s(\mathsf {w}_{pq})s(\mathsf {w}_{pq}) \approx s(\mathsf {w}_{pq}) \end{aligned}$$

and consequently

$$\begin{aligned} s^2(\mathsf {w}_{pq})x_k\widetilde{\mathsf {u}}^{(pq)}x_l\widehat{\mathsf {u}}^{(pq)} \approx s(\mathsf {w}_{pq})\sigma (\mathsf {w}_{pq})\mathsf {w}_{pq} \approx \mathsf {w}_{pq} \end{aligned}$$

holds in $\overline{\mathcal {X}_{m-1}}$ (here we used the idempotent law, upon noticing that $s^2(\mathsf {w}_{pq})\sigma s(\mathsf {w}_{pq})$ is a prefix of $s(\mathsf {w}_{pq})$, while $s(\mathsf {w}_{pq})\sigma (\mathsf {w}_{pq})$ is a prefix of $\mathsf {w}_{pq}$). Hence,

$$\begin{aligned} t_m(\mathsf {w}^{(pq)})&= t_ms^2(\mathsf {w}_{pq})x_k\overline{t}_{m-1}s(\mathsf {w}_{pq})x_l\overline{t}_{m-1}(\mathsf {w}_{pq}) \\&= t_ms(\mathsf {w}_{pq})x_l\overline{t}_{m-1}(\mathsf {w}_{pq}) = t_m(\mathsf {w}_{pq}). \end{aligned}$$

Another application of Theorem 2.5 concludes the proof of the claim that $\mathsf {w}^{(pq)}\approx \mathsf {w}_{pq}$ holds in $\mathcal {X}_m$.

Let now $\overline{a}=(a_1,\ldots ,a_n)\in T_m^n$ be arbitrary. As $n\ge |T_m|+4>|T_m|+3$, by the pigeohole principle there are $p,q\in \mathbf {n}$, $p<q$, such that $a_p=a_q$ and $\{p,q\}\cap \{k,l\}=\varnothing$. Thus

$$\begin{aligned} f(\overline{a}) = f_{pq}(\overline{a}) = \mathsf {w}_{pq}^{T_m}(\overline{a}) = (\mathsf {w}^{(pq)})^{T_m}(\overline{a}) = (\mathsf {w}^{T_m})_{pq}(\overline{a}) = \mathsf {w}^{T_m}(\overline{a}), \end{aligned}$$

where the previous claim was used in the third equality above. Therefore, $f=\mathsf {w}^{T_m}$, showing that $T_m$ is finitely related.

The result for $\overline{T_m}$ follows by left-right duality or simply by the observation that if a finite semigroup S is finitely related, so is its dual semigroup $\overline{S}$. (Indeed, if $\{\mathsf {u}_{ij}:\ 1\le i<j\le n\}$ is an n-scheme of words for the variety $\overline{\mathcal {V}}$ generated by $\overline{S}$ then it is a routine to show that $\{\overline{\mathsf {u}_{ij}}:\ 1\le i<j\le n\}$ is an n-scheme of words for the variety $\mathcal {V}$ generated by S; so, if the latter scheme comes from a word $\mathsf {u}$ it follows immediately that the former one comes from $\overline{\mathsf {u}}$. Now an appeal to Theorem 2.2 gives the required result.) $\square$

Theorem 3.2

For any $m\ge 3$, the bands $A_m\times \overline{A_m}$, $A_m\times \overline{B_{m-1}}$, $B_{m-1}\times \overline{A_m}$, $B_m\times \overline{B_m}$, $B_m\times \overline{A_m}$ and $A_m\times \overline{B_m}$ are finitely related.

Remark 3.3

Note that this theorem does not follow automatically from the previous one, as it was shown in [9, Example 6.3] that the finitely related property is in general not preserved by direct products.

Proof

Generally, we are going to argue that a finite band of the form $T_m\times \overline{U_r}$ is finitely related, where $T,U\in \{A,B\}$ and $r\in \{m-1,m\}$, with combinations as in the formulation; since the third case is dual to the second and sixth case to the fifth, these two may be safely omitted by our previous left-right duality remarks. Note that with these restrictions if $T_m$ generates $\mathcal {X}_m$ and $\overline{U_r}$ generates $\overline{\mathcal {Y}_r}$ ($\mathcal {X},\mathcal {Y}\in \{\mathcal {A},\mathcal {B}\}$) then $\overline{\mathcal {Y}_r}$ is always a subvariety of $\overline{\mathcal {X}_m}$ containing $\overline{\mathcal {X}_{m-1}}$. Equivalently, $\mathcal {X}_m$ is a subvariety of $\mathcal {Y}_{r+1}$ containing $\mathcal {Y}_r$. Also, $\mathcal {B}_2$ can be assumed to be a subvariety of both $\mathcal {X}_m$ and $\mathcal {Y}_r$.

So, let $n_0=\max (|T_m||U_r|+4,m+3)$ and assume that for some $n\ge n_0$, f is an n-ary term operation of $T_m\times \overline{U_r}$ depending on all of its variables, with the property that for all $1\le i<j\le n$, $f_{ij}$ is induced by a word $\mathsf {w}_{ij}\in X_n^+$. $\square$

Claim

There exist operations $g:T_m^n\rightarrow T_m$ and $h:\overline{U_r}^n\rightarrow \overline{U_r}$ such that

$$\begin{aligned} f((a_1,b_1),\ldots ,(a_n,b_n)) = \left( g(a_1,\ldots ,a_n),h(b_1,\ldots ,b_n)\right) \end{aligned}$$

for all $a_1,\ldots ,a_n\in T_m$ and $b_1,\ldots ,b_n\in \overline{U_r}$, and, furthermore, for all $1\le i<j\le n$, the operations $g_{ij}$ and $h_{ij}$ are induced by $\mathsf {w}_{ij}$ on $T_m$ and $\overline{U_r}$, respectively.

Proof of Claim

By Lemma 2.8(1), $\mathcal {S}=\{\mathsf {w}_{ij}:\ 1\le i<j\le n\}$ is an n-scheme of words for the variety generated by $T_m\times \overline{U_r}$, and thus for each of the varieties generated individually by $T_m$ and $\overline{U_r}$. Now by [9, Lemma 2.6] there are (unique) n-ary operations g and h on $T_m$ and $\overline{U_r}$, respectively, such that $g_{ij}=\mathsf {w}_{ij}^{T_m}$ and $h_{ij}=\mathsf {w}_{ij}^{\overline{U_r}}$ for all $1\le i<j\le n$.

As $n>|T_m||U_r|$, for arbitrary $(a_1,b_1),\ldots ,(a_n,b_n)\in T_m\times \overline{U_r}$ there are $p,q\in \mathbf {n}$, $p<q$, such that $(a_p,b_p)=(a_q,b_q)$. Hence,

$$\begin{aligned} f((a_1,b_1),\ldots ,(a_n,b_n))&= f_{pq}((a_1,b_1),\ldots ,(a_n,b_n)) \\&= \mathsf {w}_{pq}^{T_m\times \overline{U_r}}((a_1,b_1),\ldots ,(a_n,b_n)) \\&= \left( \mathsf {w}_{pq}^{T_m}(a_1,\ldots ,a_n),\mathsf {w}_{pq}^{\overline{U_r}}(b_1,\ldots ,b_n)\right) \\&= (g_{pq}(a_1,\ldots ,a_n), h_{pq}(b_1,\ldots ,b_n)) \\&= (g(a_1,\ldots ,a_n), h(b_1,\ldots ,b_n)). \end{aligned}$$

By the very construction of g and h, the claim follows.

By the choice of $n_0$ and Theorem 3.1 (in fact, by n satisfying the assumptions in its proof), both g and h are induced by words, say $\mathsf {u}$ and $\mathsf {v}$. We claim that f is induced on $T_m\times \overline{U_r}$ by the word $\mathsf {w}=\mathsf {u}\mathsf {v}$. We are going to prove that for all $1\le i<j\le n$, both $T_m$ and $\overline{U_r}$ satisfy $\mathsf {w}^{(ij)}\approx \mathsf {w}_{ij}$. Similarly as in the final part of the proof of the previous theorem, this will suffice to establish the theorem, because then for arbitrary $(a_1,b_1),\ldots ,(a_n,b_n)\in T_m\times \overline{U_r}$ the pigeonhole principle provides $p<q$ with $(a_p,b_p)=(a_q,b_q)$, so that for $\overline{c}=((a_1,b_1),\ldots ,(a_n,b_n))$, $\overline{a}=(a_1,\ldots ,a_n)$ and $\overline{b}=(b_1,\ldots ,b_n)$ we have

$$\begin{aligned} f(\overline{c})&= f_{pq}(\overline{c}) = (g_{pq}(\overline{a}),h_{pq}(\overline{b}))=(\mathsf {w}_{pq}^{T_m}(\overline{a}),\mathsf {w}_{pq}^{\overline{U_r}}(\overline{b}))\\&= ((\mathsf {w}^{(pq)})^{T_m}(\overline{a}),(\mathsf {w}^{(pq)})^{\overline{U_r}}(\overline{b}))\\&=(\mathsf {w}^{(pq)})^{T_m\times \overline{U_r}}(\overline{c}) = (\mathsf {w}^{T_m\times \overline{U_r}})_{pq}(\overline{c})=\mathsf {w}^{T_m\times \overline{U_r}}(\overline{c}), \end{aligned}$$

showing that $f=\mathsf {w}^{T_m\times \overline{U_r}}$.

Let us start by noting that the scheme $\mathcal {S}$ is essential (by Lemma 2.8(2)), which immediately implies $c(\mathsf {u})=c(\mathsf {v})=X_n$, so $s(\mathsf {w})=s(\mathsf {u})$, $\sigma (\mathsf {w})=\sigma (\mathsf {u})$, $\varepsilon (\mathsf {w})=\varepsilon (\mathsf {v})$ and $e(\mathsf {w})=e(\mathsf {v})$. This yields $s(\mathsf {w}^{(ij)})=s(\mathsf {u}^{(ij)})$ and $e(\mathsf {w}^{(ij)})=e(\mathsf {v}^{(ij)})$. Furthermore, $i_2(\mathsf {w})=i_2(\mathsf {u})$, implying $i_2(\mathsf {w}^{(ij)})=i_2(\mathsf {u}^{(ij)})=i_2(\mathsf {w}_{ij})$ by Lemma 2.9 because $\mathcal {X}_m$ contains $\mathcal {B}_2$. Thus $\sigma (\mathsf {w}^{(ij)})=\sigma (\mathsf {u}^{(ij)})=\sigma (\mathsf {w}_{ij})$ and, dually, $\varepsilon (\mathsf {w}^{(ij)})=\varepsilon (\mathsf {v}^{(ij)})=\varepsilon (\mathsf {w}_{ij})$. Also, if $t_m$ is the word function corresponding to the variety $\mathcal {X}_m$ (in the sense of Theorem 2.5), then we know, by construction of words $\mathsf {u}$ and $\mathsf {v}$, that $\mathcal {X}_m$ satisfies $\mathsf {u}^{(ij)}\approx \mathsf {w}_{ij}$ — so that $t_m(\mathsf {u}^{(ij)})=t_m(\mathsf {w}_{ij})$ — while $\overline{\mathcal {Y}_r}$ satisfies $\mathsf {v}^{(ij)}\approx \mathsf {w}_{ij}$. By assumptions made earlier in this proof, the latter identity holds in $\overline{\mathcal {X}_{m-1}}$, implying $\overline{t}_{m-1}(\mathsf {v}^{(ij)})=\overline{t}_{m-1}(\mathsf {w}_{ij})$.

Note that we have $\overline{h}_2(\mathsf {w}^{(ij)})=\overline{h}_2(\mathsf {v}^{(ij)})$ since $e(\mathsf {w})=e(\mathsf {v})$. So, if $\mathcal {X}_m=\mathcal {A}_3$ we deduce, by Lemma 2.6(1),

$$\begin{aligned} h_3(\mathsf {w}^{(ij)})&= h_3s(\mathsf {u}^{(ij)})\sigma (\mathsf {u}^{(ij)})\overline{h}_2(\mathsf {w}^{(ij)})\\&= sh_3(\mathsf {u}^{(ij)})\sigma (\mathsf {u}^{(ij)})\overline{h}_2(\mathsf {v}^{(ij)})\\&= sh_3(\mathsf {w}_{ij})\sigma (\mathsf {w}_{ij})\overline{h}_2(\mathsf {w}_{ij})\\&= h_3s(\mathsf {w}_{ij})\sigma (\mathsf {w}_{ij})\overline{h}_2(\mathsf {w}_{ij})=h_3(\mathsf {w}_{ij}). \end{aligned}$$

On the other hand, if $\mathcal {X}_m\in \{\mathcal {A}_k:\ k\ge 4\}\cup \{\mathcal {B}_k:\ k\ge 3\}$ then by items (1) and (2) of Lemma 2.6 we obtain

$$\begin{aligned} bt_m(\mathsf {w}^{(ij)})&= b\left[ t_ms(\mathsf {u}^{(ij)})\sigma (\mathsf {u}^{(ij)})\varepsilon (\mathsf {v}^{(ij)})\overline{t}_{m-1}e(\mathsf {v}^{(ij)})\right] \\&= b\left[ st_m(\mathsf {u}^{(ij)})\sigma (\mathsf {u}^{(ij)})\varepsilon (\mathsf {v}^{(ij)})e\overline{t}_{m-1}(\mathsf {v}^{(ij)})\right] \\&= b\left[ st_m(\mathsf {w}_{ij})\sigma (\mathsf {w}_{ij})\varepsilon (\mathsf {w}_{ij})e\overline{t}_{m-1}(\mathsf {w}_{ij})\right] \\&= b\left[ t_ms(\mathsf {w}_{ij})\sigma (\mathsf {w}_{ij})\varepsilon (\mathsf {w}_{ij})\overline{t}_{m-1}e(\mathsf {w}_{ij})\right] = bt_m(\mathsf {w}_{ij}). \end{aligned}$$

But then Lemma 2.6(3) implies that $t_m(\mathsf {w}^{(ij)})=t_m(\mathsf {w}_{ij})$, i.e. that $\mathcal {X}_m$ (and thus $T_m$) satisfies $\mathsf {w}^{(ij)}\approx \mathsf {w}_{ij}$.

The proof that $\overline{\mathcal {Y}_r}$ satisfies $\mathsf {w}^{(ij)}\approx \mathsf {w}_{ij}$ is similar, albeit with slight differences. Let now $t_r$ be the word function corresponding to $\mathcal {Y}_r$ in the sense of Theorem 2.5. The fact that $\mathcal {X}_m$ (and so $\mathcal {Y}_r$) satisfies $\mathsf {u}^{(ij)}\approx \mathsf {w}_{ij}$ implies $t_r(\mathsf {u}^{(ij)})=t_r(\mathsf {w}_{ij})$. Furthermore, [13, Lemma 3.5] tells us that $t_{r-1}(\mathsf {u}^{(ij)})=t_{r-1}(\mathsf {w}_{ij})$ holds as well, provided $r\ge 3$. In turn, $\overline{\mathcal {Y}_r}$ satisfies $\mathsf {v}^{(ij)}\approx \mathsf {w}_{ij}$, thus $\overline{t}_r(\mathsf {v}^{(ij)})=\overline{t}_r(\mathsf {w}_{ij})$.

Now we have three subcases to consider. First, let $\overline{\mathcal {Y}_r}=\overline{\mathcal {B}_2}$ (which can happen, just as the next subcase, only if $\mathcal {X}_m=\mathcal {A}_3$). Since $c(\mathsf {u})=c(\mathsf {v})=X_n$, we have $\overline{i}_2(\mathsf {w}^{(ij)})=\overline{i}_2(\mathsf {u}^{(ij)}\mathsf {v}^{(ij)})= \overline{i}_2(\mathsf {v}^{(ij)})$. On the other hand, we have already concluded that $\overline{\mathcal {Y}_r}$ satisfies $\mathsf {v}^{(ij)}\approx \mathsf {w}_{ij}$, so $\overline{i}_2(\mathsf {v}^{(ij)})=\overline{i}_2(\mathsf {w}_{ij})$ yielding $\overline{i}_2(\mathsf {w}^{(ij)})= \overline{i}_2(\mathsf {w}_{ij})$, as required. Our second subcase is $\overline{\mathcal {Y}_r}=\overline{\mathcal {A}_3}$, when $h_2(\mathsf {w}^{(ij)})= h_2(\mathsf {u}^{(ij)})$ because of $s(\mathsf {w})=s(\mathsf {u})$. By items (1) and (4) of Lemma 2.6 we have:

$$\begin{aligned} \overline{h}_3(\mathsf {w}^{(ij)})&= h_2(\mathsf {w}^{(ij)})\varepsilon (\mathsf {v}^{(ij)})\overline{h}_3e(\mathsf {v}^{(ij)})\\&= h_2(\mathsf {u}^{(ij)})\varepsilon (\mathsf {v}^{(ij)})e\overline{h}_3(\mathsf {v}^{(ij)})\\&= h_2(\mathsf {w}_{ij})\varepsilon (\mathsf {w}_{ij})e\overline{h}_3(\mathsf {w}_{ij})\\&= h_2(\mathsf {w}_{ij})\varepsilon (\mathsf {w}_{ij})\overline{h}_3e(\mathsf {w}_{ij})=\overline{h}_3(\mathsf {w}_{ij}). \end{aligned}$$

Finally, let $\overline{\mathcal {Y}_r}\in \{\overline{\mathcal {A}_k}:\ k\ge 4\}\cup \{\overline{\mathcal {B}_k}:\ k\ge 3\}$. Then, by invoking parts (1) and (2) of Lemma 2.6 once again, we deduce

$$\begin{aligned} b\overline{t}_r(\mathsf {w}^{(ij)})&= b\left[ t_{r-1}s(\mathsf {u}^{(ij)})\sigma (\mathsf {u}^{(ij)})\varepsilon (\mathsf {v}^{(ij)})\overline{t}_re(\mathsf {v}^{(ij)})\right] \\&= b\left[ st_{r-1}(\mathsf {u}^{(ij)})\sigma (\mathsf {u}^{(ij)})\varepsilon (\mathsf {v}^{(ij)})e\overline{t}_r(\mathsf {v}^{(ij)})\right] \\&= b\left[ st_{r-1}(\mathsf {w}_{ij})\sigma (\mathsf {w}_{ij})\varepsilon (\mathsf {w}_{ij})e\overline{t}_r(\mathsf {w}_{ij})\right] \\&= b\left[ t_{r-1}s(\mathsf {w}_{ij})\sigma (\mathsf {w}_{ij})\varepsilon (\mathsf {w}_{ij})\overline{t}_re(\mathsf {w}_{ij})\right] = b\overline{t}_r(\mathsf {w}_{ij}), \end{aligned}$$

whence Lemma 2.6(3) implies that $\overline{t}_r(\mathsf {w}^{(ij)})=\overline{t}_r(\mathsf {w}_{ij})$.

Hence, both $\mathcal {X}_m$ and $\overline{\mathcal {Y}_r}$ (with restrictions on m, r as described at the beginning of the proof) satisfy the identity $\mathsf {w}^{(ij)}\approx \mathsf {w}_{ij}$. As remarked earlier, this completes the proof that f is induced by $\mathsf {w}$ and confirms the theorem. $\square$

The proof of Theorem 1.1 is now immediate: if S is a finite band then it generates the same variety as one of the bands covered by [17, Theorem 6.2], Theorem 3.1 and Theorem 3.2. By [9, Theorem 2.11], S is finitely related.