arXiv:1509.04509v8 [math.GR] 23 Aug 2017

FINITE BANDS ARE FINITELY RELATED
IGOR DOLINKA
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 Peter Mayr in 2013.

1. Introduction
Let A = (A, F ) be an algebra, where F is a family of finitary operations on the
set A. As is well known, any term t(x1 , . . . , xn ) (of the same similarity type as A)
induces, by interpretation in A, an operation tA : An → A. Operations obtained
in this way are the term operations of A, and the collection of all term operations
of this algebra is denoted by Clo(A) and called the clone of A.
For an n-ary operation f on a set X (f : X n → X) and a k-ary relation ρ on
the same set (ρ ⊆ X k ) we say that f preserves ρ if for any a1 , . . . , ak ∈ X n (where
ai = (ai,1 , . . . , ai,n ) for 1 ≤ i ≤ k) such that (a1,j , . . . , ak,j ) ∈ ρ for all 1 ≤ j ≤ n
we have (f (a1 ), . . . , f (ak )) ∈ ρ; in other words, either ρ = ∅ or ρ is a subalgebra of
the kth direct power of the algebra (X, f ). For a family R of (finitary) relations on
X we denote by Pol(R) the set of all operations on X preserving all relations from
R – these are the polymorphisms of the relational structure (X, R). Conversely, if
O is a family of operations on X, the set of all relations preserved by all operations
from O is denoted by Inv(O). A foundational result in clone theory tells us that,
for finite A, Clo(A) = Pol(Inv(F )), and in this sense the clone of A is determined
by the collection of relations Inv(F ): an operation on A arises from a term if and
only if it preserves all the relations that are preserved by F .
The set of relations Inv(F ) is always infinite. However, it may happen that there
is in fact a finite subset R ⊆ Inv(F ) such that Clo(A) = Pol(R), so that the clone
of 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 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
2010 Mathematics Subject Classification. Primary 20M07; Secondary 03C05, 08A40, 20M05.
Key words and phrases. Semigroup; Idempotent semigroup; Band; Finitely related algebra.
This research was supported by the Ministry of Education, Science, and Technological Development of the Republic of Serbia through the grant No.174019.
1

2

IGOR DOLINKA

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 B21 , 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 ≈ 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).
2. Preliminaries
2.1. Term schemes and criteria for finitely related finite algebras. Let
f : An → A be an n-ary operation on the set A. For i, j ∈ n = {1, . . . , n}, i < j,
we define an operation fij : An → A (sometimes called an identification minor of
f ) by
fij (x1 , . . . , xn ) = f (x1 , . . . , xi−1 , xj , xi+1 , . . . , xj , . . . , xn );
in other words, fij is obtained from f by identifying the variable xi with xj . Similarly, if t = t(x1 , . . . , xn ) is a term of a given similarity type, then by t(ij) we denote
the term obtained from t by replacing each occurrence of xi in it by xj ; furthermore,
by convention we define t(ji) to be t(ij) .
As usual, we say that an operation f : An → A depends on its ith variable xi ,
i ∈ n, if there exist a1 , . . . , ai−1 , ai+1 , . . . , an , b, c ∈ A such that
f (a1 , . . . , ai−1 , b, ai+1 , . . . , an ) 6= f (a1 , . . . , ai−1 , c, ai+1 , . . . , an ).
For example, the identification minor fij does not depend on xi . In turn, as another
example, the ith projection operation fails to depend on any of its variables but xi .

FINITE BANDS ARE FINITELY RELATED

3

Now let V be a variety and assume
S = {tij : 1 ≤ i < j ≤ n}
is a family of terms over Xn = {x1 , . . . , xn } of the similarity type of V satisfying
the following conditions:
(D) For each A ∈ V, the term operation tA
ij (x1 , . . . , xn ) does not depend on the
variable xi .
(C1) For any four distinct 1 ≤ i, j, p, q ≤ m such that i < j and p < q, V satisfies
the identity
(pq)
tij ≈ t(ij)
pq .
(C2) For any three 1 ≤ i < j < k ≤ n, V satisfies the identities
(jk)

tij

(ik)

(jk)

≈ tjk ≈ tik .

The condition (D) is called dependency, while (C1) and (C2) are the consistency
conditions; the family S is called an n-scheme of terms for 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 V be an arbitrary variety and t(x1 , . . . , xn ) a term of the same
similarity type as V. The family of all identification minors of t,
{t(ij) : 1 ≤ i < j ≤ n},
is an n-scheme of terms for V.
Again following [9], we say that an n-scheme S = {tij : 1 ≤ i < j ≤ m} for V
comes from the term t if S is V-equivalent to the family of all identification minors
of t in the sense that V satisfies the identities
tij ≈ t(ij)
for all 1 ≤ i < j ≤ n.
The following characterisation is part of Theorem 2.9 from [9], see also [14, 17,
18, 19].
Theorem 2.2. Let A be a finite algebra, and let V be the variety generated by A.
The following are equivalent:
(1) A is finitely related.
(2) There exists n0 ≥ |A| such that for all n > n0 , every n-scheme of terms for
V comes from a term.
(3) There exists n0 ≥ |A| such that for all n > n0 , an operation f : An → A
is a term operation of A whenever all minors fij (i, j ∈ n, i < j) are term
operations of A.
Here we immediately invoke Remark 2.12 from [9] which provides an argument
that in checking if a finite algebra A satisfies condition (3) above, it can be assumed
that the operation f : An → 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 n0 ≥ |A| such that for all n > n0 , an operation f : An → A
depending on all of its variables is a term operation of A whenever all
minors fij (i, j ∈ n, i < j) are term operations of A.

4

IGOR DOLINKA

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 Xn+ ), 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 ≈ 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 B. It is known that any semigroup variety containing B
(including B itself) is not generated by a finite semigroup [20], while every proper
subvariety of 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 w over a (finite) alphabet
X, let c(w) denote the content of w, the set of all letters occurring in w. Further,
let s(w) denote the longest prefix of w containing all but one of the letters from
c(w) (so that |c(s(w))| = |c(w)| − 1 and s(w) is maximal with this property), while
σ(w) is the last letter to occur in w from the left (implying that s(w)σ(w) is the
shortest prefix of w with the same content as w). Dually, let e(w) be the longest
suffix of w containing all but one of the letters from c(w), and let ε(w) be the last
letter in w to occur from the right.
Define an operator b on words by induction on the size of their content such that
b(∅) = ∅ (here ∅ stands for the empty word) and
b(w) = bs(w)σ(w)ε(w)be(w)
(note the concatenation of word operators, where bs(w) means b(s(w)), etc.).
Theorem 2.3 (cf. Lemma 2.7 and Theorem 2.9 of [12]). Let X be an alphabet and
u, v ∈ X + . Then u ≈ v holds in B if and only if b(u) = b(v). In particular, for any
word w we have that the identity
w ≈ s(w)σ(w)ε(w)e(w)
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 u, v, w be words such that c(v) ⊆ c(u) = c(w). Then the identity
uvw ≈ uw holds in B.
Proof. Under the given conditions, s(uvw) = s(u) = s(uw) and σ(uvw) = σ(u) =
σ(uw), and, dually, e(uvw) = e(w) = e(uw) and ε(uvw) = ε(w) = ε(uw), so the
result follows by Theorem 2.3.


FINITE BANDS ARE FINITELY RELATED

5

sB
..
.

..
.

❅s A
❅s
A4 s
4
❅
❅
❅
❅
❅s
❅s
❅
❅
❅
❅
❅s
❅s B
B3 s
3
❅
❅
❅
❅
❅s
❅s
❅
❅
❅
❅
❅s
❅s A
A3 s
3
❅
❅
❅
❅
❅s
❅s
❅
❅
❅
❅
❅s
❅s B = RRB
B2 = LRB s
2
❅
❅
❅
❅
❅s
❅s
s
❅
❅
❅
❅
❅s
❅s A = RZ
A2 = LZ s
2
SL
❅
❅
❅s
T
Figure 1. The lattice of all varieties of bands
The description of the lattice L (B) of all subvarieties of 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 SL, LZ and 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 Am and Bm , m ≥ 2, as well as their duals Am and Bm – any proper
(i.e. finitely generated) band variety not contained in SL ∨ LZ ∨ 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 Am , Bm is finitely related; by left-right duality, this
will extend to Am and Bm , and then we shall show how to use this fact to prove
finite relatedness for any finite band generating a proper subvariety of B. The
varieties LRB and RRB are the varieties of left regular and right regular bands
defined by identities xyx ≈ xy and xyx ≈ 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 Am ,

6

IGOR DOLINKA

Bm 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 Am , Bm , m ≥ 2 (as well as their dual semigroups Am and Bm ),
such that Am generates the variety Am and Bm generates Bm (For example, one
can choose A2 to be the two-element left zero band, B2 to be A2 with an identity
element adjoined, etc. Note that we can choose these bands so that |A2 | < |B2 | <
|A3 | < |B3 | < . . . 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 hm and im for m ≥ 2 and their duals, hm , im , in the sense
that if w denotes the reverse of the word w we have tm (w) = tm (w) for t ∈ {h, i}:
• tm (∅) = ∅ for all m ≥ 2 and t ∈ {h, i};
• h2 (w) is the first letter of w from the left (the head of w);
• i2 (w) is the word obtained from w by retaining only the first occurrence
from the left of each letter (the initial part of w, also defined recursively by
i2 (w) = i2 s(w)σ(w));
• for m ≥ 3 and t ∈ {h, i} we set
tm (w) = tm s(w)σ(w)tm−1 (w).
The key feature of these functions is expressed in the following statement.
Theorem 2.5 ([13]). Let m ≥ 2 and let u, v be two words.
• Am satisfies u ≈ v if and only if hm (u) = hm (v).
• Bm satisfies u ≈ v if and only if im (u) = im (v).
Analogous equivalences hold for the dual varieties Am and Bm and functions hm
and im , respectively.
The next few properties will be used in our proofs.
Lemma 2.6.
(1) Let t ∈ {h, i}. If m ≥ 3 or tm = i2 then stm (w) = tm s(w)
and etm (w) = tm e(w) for any word w.
(2) Let t ∈ {h, i}. If m ≥ 4 or tm = i3 then
btm (w) = b(tm s(w)σ(w)ε(w)tm−1 e(w))
and
btm (w) = b(tm−1 s(w)σ(w)ε(w)tm e(w))
for any word w.
(3) Let t ∈ {h, i, h, i} and let u, v be any words. If m ≥ 2 then btm (u) = btm (v)
implies tm (u) = tm (v).
(4) Let t ∈ {h, i}. If m ≥ 3 then
tm (w) = tm−1 (w)ε(w)tm e(w)
for any word 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 etm (w) = etm (w) = stm (w) = tm s(w) =
tm (e(w)) = tm e(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.


FINITE BANDS ARE FINITELY RELATED

7

Lemma 2.7. Let X ∈ {A, B}. Assume that the variety Xm satisfies the identity
u ≈ v, where |c(u)|, |c(v)| ≥ 2. Then it also satisfies s(u) ≈ s(v).
Proof. Consider first the case when Xm = A2 . Since both u and v contain at least
two letters, we have h2 s(u) = h2 (u) = h2 (v) = h2 s(v), and the lemma follows.
Otherwise, if either Xm = B2 or m ≥ 3, let tm be the corresponding word function
in the sense of Theorem 2.5. By the given conditions we have tm (u) = tm (v), which
in turn implies stm (u) = stm (v). Then Lemma 2.6(1) tells us that tm s(u) = tm s(v)
(since we assumed that tm 6= h2 ). Another application of Theorem 2.5 yields that
Xm satisfies s(u) ≈ s(v).

2.3. Some auxiliary results. As Theorem 2.2 suggests, we will be concerned with
essential operations f : S n → S on a finite (idempotent) semigroup S such that all
of its minors fij 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 → S be an operation
depending on all of its variables such that for any i, j ∈ n, i < j, there is a word
S
wij satisfying fij = wij
.
(1) {wij : 1 ≤ i < j ≤ n} is an n-scheme of words for the semigroup variety
generated by S.
(2) If the variety generated by S contains SL and n ≥ |S| + 4 then c(wij ) =
Xn \ {xi }.
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 xk , k 6= i),
there exist a1 , . . . , ak−1 , ak+1 , . . . , an , b, c ∈ S such that
f (a1 , . . . , ak−1 , b, ak+1 , . . . , an ) 6= f (a1 , . . . , ak−1 , c, ak+1 , . . . , an ).
The pigeonhole principle ensures that there exist p, q ∈ n \ {i, j, k}, p < q, such that
S
depends on xk . However, by
ap = aq . Hence, just as in [17, Lemma 2.6], fpq = wpq
(ij)

(pq)

(1), S satisfies the identity wpq ≈ wij
that wij must contain xk , since k 6= i.

(ij)

(pq)

and so xk ∈ c(wpq ) = c(wij ), ensuring


In the following, n-schemes of words {wij : 1 ≤ i < j ≤ n} over Xn such that
c(wij ) = Xn \ {xi } 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 {wij : 1 ≤ i < j ≤ n} be an essential n-scheme of words for a
semigroup variety V containing B2 (the variety of left regular bands), where n ≥ 5.
Then there exists a unique permutation π of n such that for any i < j,
i2 (wij ) = xα1 · · · xαn−1 ,
where the sequence π (ij) = (α1 , . . . , αn−1 ) is obtained from (1π, . . . , nπ) 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 w then we must have i2 (w) = x1π · · · xnπ .
Proof. By the very definition of an (essential) n-scheme of words for a variety,
any scheme for a variety V is also a scheme for any of its subvarieties, and so

8

IGOR DOLINKA

is the case for the given scheme with respect to B2 . As already discussed, B2 is
generated by the 3-element band B2 (obtained by adjoining an identity element
to the 2-element left zero band), and by Lemma 6.1 of [17], B2 is finitely related
with degree at most 4. By [9, Lemma 2.6], there exists a unique operation f :
B2
for all 1 ≤ i < j ≤ n. To see that f depends
B2n → B2 such that fij = wij
B2
on all of its variables, fix k ∈ n and p, q ∈ n \ {k}, p < q. As fpq = wpq
and
xk ∈ c(wpq ), fpq depends on xk , so there exist a1 , . . . , ak−1 , ak+1 , . . . , an , b, c ∈
B2 such that fpq (a1 , . . . , ak−1 , b, ak+1 , . . . , an ) 6= fpq (a1 , . . . , ak−1 , c, ak+1 , . . . , an ).
This immediately implies that f depends on xk .
Hence, by [17, Lemma 6.1], f is induced by a word w such that c(w) = Xn . Now
it is routine to see that the permutation π ∈ Sn satisfying
i2 (w) = x1π · · · xnπ
meets all the requirements of the lemma. It is unique because if π ′ would be
another permutation with the required properties, then it would follow that the
given scheme (with respect to B2 ) also comes from the word w′ = x1π′ · · · xnπ′ ,
whence the uniqueness of f implies that (w′ )B2 = f . Therefore, B2 satisfies w′ ≈ w,
implying i2 (w′ ) = i2 (w) and so π ′ = π.

For an essential scheme of words satisfying the assumptions of the above lemma,
we will call π 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 ∈ n, and let w ∈ Xn+ be such that c(w) = Xn \ {xk } and
σ(w) = xl . Furthermore, let p, q ∈ n\{l} such that p < q. Then s(w)(pq) = s(w(pq) ).
Proof. We start by writing w in the form
w = s(w)xl u
(pq)

for some word u, implying w
= s(w)(pq) xl u(pq) . If q 6= k then c(w(pq) ) =
(pq)
Xn \{xk , xp } and c(s(w) ) = Xn \{xl , xk , xp }, which immediately gives s(w(pq) ) =
s(w)(pq) . The same conclusion follows if q = k upon noticing that in such a case we
have c(w(pq) ) = Xn \ {xp } and c(s(w)(pq) ) = Xn \ {xl , xp }.

Lemma 2.11. Let n ≥ 5, let S = {wij : 1 ≤ i < j ≤ n} be an essential n-scheme
of words for Xm , where X ∈ {A, B} and either m ≥ 3 or Xm = B2 . Let π be the
associated permutation of S (which exists by Lemma 2.9) and let l = nπ. Then
S ′ = {s(wij ) : 1 ≤ i < j ≤ n, l 6∈ {i, j}}
is an (n − 1)-scheme for Xm over variables Xn \ {xl }.
Proof. Note that if l 6∈ {i, j} then σ(wij ) = xl and so c(s(wij )) = Xn \ {xi , xl }.
Thus (D) holds.
Furthermore, if p < q are such that {p, q} ∩ {i, j, l} = ∅ then by Lemma 2.10 we
(ij)
(pq)
have s(wij )(pq) = s(wij ) and s(wpq )(ij) = s(wpq ). Further the assumption that
(pq)

(ij)

(pq)

(ij)

Xm satisfies wij ≈ wpq implies, by Lemma 2.7, the identity s(wij ) ≈ s(wpq ).
Hence, Xm satisfies s(wij )(pq) ≈ s(wpq )(ij) , and so S ′ satisfies (C1).
Now let i < j < p be such that l 6∈ {i, j, p}. Again, Lemma 2.10 implies
(jp)
(ip)
(jp)
that s(wij )(jp) = s(wij ), s(wjp )(ip) = s(wjp ) and s(wip )(jp) = s(wip ) (the
lemma was applied over the alphabet Xn \ {xi } in the first and the third case,

FINITE BANDS ARE FINITELY RELATED

9

while it was applied over Xn \ {xj } in the second case). Since, by assumption,
(jp)
(ip)
(jp)
Xm satisfies the identities wij ≈ wjp ≈ wip , it also satisfies the identities
(ip)

(jp)

(jp)

s(wij ) ≈ s(wjp ) ≈ s(wip ) by Lemma 2.7. We conclude that Xm satisfies
s(wij )(jp) ≈ s(wjp )(ip) ≈ s(wip )(jp) , hence (C2) holds for S ′ as well.

We are now ready and equipped to present our main arguments.
3. The main proofs
Theorem 3.1. For any m ≥ 2 and T ∈ {A, B}, the bands Tm and Tm are finitely
related.
Proof. We use induction on m. If m = 2, the result already follows from [17,
Theorem 6.2]. Hence fix m ≥ 3 and assume that the statement is true for values of
indices up to m − 1.
We are going to show that Tm is finitely related by verifying condition (3’) in
Theorem 2.2 with n ≥ n0 = max(|Tm | + 4, m + 3). So, under these assumptions,
n
let f : Tm
→ Tm be an operation that depends on all of its variables such that for
all i, j ∈ n, i < j, we have that the operation fij is induced by a word. Let us
Tm
. Since the variety Xm
select words wij ∈ Xn+ , 1 ≤ i < j ≤ n, such that fij = wij
generated by Tm contains SL, Lemma 2.8 tells us that c(wij ) = Xn \ {xi }, so that
S = {wij : 1 ≤ i < j ≤ n} is an essential n-scheme of words for Xm .
Since B2 is contained in Xm and n ≥ m+ 3 > 5, Lemma 2.9 ensures the existence
(and uniqueness) of the associated permutation π of the scheme S. Let us denote
k = (n − 1)π and l = nπ.
Now, since S is an n-scheme of words for Xm , it is also an n-scheme of words for
any of its subvarieties, and thus in particular for Xm−1 . This variety is generated
by the band Tm−1 which is finitely related by the inductive assumption. Hence,
Theorem 2.2 implies that S, considered as a scheme for Xm−1 , comes from a word,
n
say b
u. Equivalently, there is a word operation g : Tm−1 → Tm−1 such that
T

gij = wijm−1 holds for all 1 ≤ i < j ≤ n.
Similarly, by Lemma 2.11, the family of words S ′ = {s(wij ) : 1 ≤ i < j ≤ n, l 6∈
{i, j}} is an (n − 1)-scheme of words for Xm (and thus for Xm−1 ) over the set of
variables Xn \ {xl }. Again, by employing the inductive hypothesis (and bearing
in mind that n − 1 ≥ (m − 1) + 3 and n − 1 ≥ (|Tm | − 1) + 4 ≥ |Tm−1 | + 4), we
find a word e
u such that S ′ comes from e
u; in other words, there is a word operation
n−1
→ Tm−1 with hij = s(wij )Tm−1 for all i < j such that l 6∈ {i, j}.
h : Tm−1
Now define
u,
uxl b
w = s(wk′ l′ )xk e
where k ′ = min(k, l) and l′ = max(k, l). We are going to argue that f = wTm
whence Theorem 2.2 yields that Tm is finitely related.
Claim. If p, q ∈ n, p < q, are such that {p, q} ∩ {k, l} = ∅ then the identity
w(pq) ≈ wpq
holds in Xm (and so in Tm ).
Proof of Claim. We have
(pq)

u(pq) ,
u(pq) xl b
u(pq) = s(wk′ l′ )xk e
u(pq) xl b
w(pq) = (s(wk′ l′ ))(pq) xk e

(3.1)

10

IGOR DOLINKA

where the second equality follows by Lemma 2.10 using c(wk′ l′ ) = Xn \ {xk′ }.
(pq)
(k′ l′ )
Furthermore, by (C1), Xm satisfies wk′ l′ ≈ wpq , so by Lemma 2.7 it also satisfies
(pq)

(k′ l′ )

s(wk′ l′ ) ≈ s(wpq ). Since {p, q}∩{k, l} = ∅, the sequence π (pq) must have the form
(α1 , . . . , αn−3 , k, l) (where the subsequence (α1 , . . . , αn−3 ) is a certain permutation
of n \ {k, l, p}). Therefore, we may highlight the first occurrence from the left of
each letter from c(wpq ) in wpq by writing
wpq = xα1 u1 xα2 · · · xαn−3 un−3 xk un−2 xl v
for some (possibly empty) words u1 , . . . , un−2 , v. This yields
(k′ l′ )

′ ′

′ ′

(k l )
wpq
= xα1 u1 xα2 · · · xαn−3 un−3 xl′ un−2 xl′ v(k l ) ,

implying
′ ′

(k l )
) = xα1 u1 xα2 · · · xαn−3 un−3 = s2 (wpq ).
s(wpq
Bearing in mind (3.1), we deduce that
′ ′

(k l )
u(pq)
u(pq) xl b
u(pq) = s2 (wpq )xk e
u(pq) xl b
)xk e
w(pq) ≈ s(wpq

holds in Xm . By applying Theorem 2.5 and the recursion for tm twice, we get

u(pq)
u(pq) xl b
tm (w(pq) ) = tm s2 (wpq )xk e


u(pq) xl tm−1 s2 (wpq )xk e
u(pq)
u(pq) xl b
= tm s2 (wpq )xk e


= tm s2 (wpq )xk tm−1 s2 (wpq )xk e
u(pq) .
u(pq) xl tm−1 s2 (wpq )xk e
u(pq) xl b

However, by induction assumption on S ′ for Xm−1 we have that Xm−1 satisfies
e
u(pq) ≈ s(wpq ), and by induction assumption on S for Xm−1 we have that Xm−1 satisfies b
u(pq) ≈ wpq . We know that σ(wpq ) = xl , s(wpq ) = xα1 · · · xαn−3 un−3 xk un−2 ,
σs(wpq ) = xk , and s2 (wpq ) = xα1 · · · xαn−3 un−3 . Thus
u(pq) ≈ s2 (wpq )σs(wpq )s(wpq ) ≈ s(wpq )
s2 (wpq )xk e

and consequently

u(pq) ≈ s(wpq )σ(wpq )wpq ≈ wpq
u(pq) xl b
s2 (wpq )xk e

holds in Xm−1 (here we used the idempotent law, upon noticing that s2 (wpq )σs(wpq )
is a prefix of s(wpq ), while s(wpq )σ(wpq ) is a prefix of wpq ). Hence,
tm (w(pq) ) = tm s2 (wpq )xk tm−1 s(wpq )xl tm−1 (wpq )
= tm s(wpq )xl tm−1 (wpq ) = tm (wpq ).
Another application of Theorem 2.5 concludes the proof of the claim that w(pq) ≈
wpq holds in Xm .
n
Let now a = (a1 , . . . , an ) ∈ Tm
be arbitrary. As n ≥ |Tm | + 4 > |Tm | + 3, by the
pigeohole principle there are p, q ∈ n, p < q, such that ap = aq and {p, q} ∩ {k, l} =
∅. Thus
Tm
f (a) = fpq (a) = wpq
(a) = (w(pq) )Tm (a) = (wTm )pq (a) = wTm (a),

where the previous claim was used in the third equality above. Therefore, f = wTm ,
showing that Tm is finitely related.
The result for Tm follows by left-right duality or simply by the observation that
if a finite semigroup S is finitely related, so is its dual semigroup S. (Indeed, if
{uij : 1 ≤ i < j ≤ n} is an n-scheme of words for the variety V generated by S

FINITE BANDS ARE FINITELY RELATED

11

then it is a routine to show that {uij : 1 ≤ i < j ≤ n} is an n-scheme of words
for the variety V generated by S; so, if the latter scheme comes from a word u it
follows immediately that the former one comes from u. Now an appeal to Theorem
2.2 gives the required result.)

Theorem 3.2. For any m ≥ 3, the bands Am × Am , Am × Bm−1 , Bm−1 × Am ,
Bm × Bm , Bm × Am and Am × Bm 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 Tm × Ur is
finitely related, where T, U ∈ {A, B} and r ∈ {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 Tm generates Xm and Ur generates Yr (X , Y ∈ {A, B})
then Yr is always a subvariety of Xm containing Xm−1 . Equivalently, Xm is a
subvariety of Yr+1 containing Yr . Also, B2 can be assumed to be a subvariety of
both Xm and Yr .
So, let n0 = max(|Tm ||Ur | + 4, m + 3) and assume that for some n ≥ n0 , f is an
n-ary term operation of Tm × Ur depending on all of its variables, with the property
that for all 1 ≤ i < j ≤ n, fij is induced by a word wij ∈ Xn+ .
n

n
Claim. There exist operations g : Tm
→ Tm and h : Ur → Ur such that

f ((a1 , b1 ), . . . , (an , bn )) = (g(a1 , . . . , an ), h(b1 , . . . , bn ))
for all a1 , . . . , an ∈ Tm and b1 , . . . , bn ∈ Ur , and, furthermore, for all 1 ≤ i < j ≤ n,
the operations gij and hij are induced by wij on Tm and Ur , respectively.
Proof of Claim. By Lemma 2.8(1), S = {wij : 1 ≤ i < j ≤ n} is an n-scheme
of words for the variety generated by Tm × Ur , and thus for each of the varieties
generated individually by Tm and Ur . Now by [9, Lemma 2.6] there are (unique)
Tm
n-ary operations g and h on Tm and Ur , respectively, such that gij = wij
and
Ur
for all 1 ≤ i < j ≤ n.
hij = wij
As n > |Tm ||Ur |, for arbitrary (a1 , b1 ), . . . , (an , bn ) ∈ Tm × Ur there are p, q ∈ n,
p < q, such that (ap , bp ) = (aq , bq ). Hence,

f ((a1 , b1 ), . . . , (an , bn )) = fpq ((a1 , b1 ), . . . , (an , bn ))
Tm ×Ur
((a1 , b1 ), . . . , (an , bn ))
= wpq


Tm
Ur
(a1 , . . . , an ), wpq
= wpq
(b1 , . . . , bn )

= (gpq (a1 , . . . , an ), hpq (b1 , . . . , bn ))
= (g(a1 , . . . , an ), h(b1 , . . . , bn )).
By the very construction of g and h, the claim follows.
By the choice of n0 and Theorem 3.1 (in fact, by n satisfying the assumptions
in its proof), both g and h are induced by words, say u and v. We claim that f
is induced on Tm × Ur by the word w = uv. We are going to prove that for all
1 ≤ i < j ≤ n, both Tm and Ur satisfy w(ij) ≈ wij . Similarly as in the final part of

12

IGOR DOLINKA

the proof of the previous theorem, this will suffice to establish the theorem, because
then for arbitrary (a1 , b1 ), . . . , (an , bn ) ∈ Tm × Ur the pigeonhole principle provides
p < q with (ap , bp ) = (aq , bq ), so that for c = ((a1 , b1 ), . . . , (an , bn )), a = (a1 , . . . , an )
and b = (b1 , . . . , bn ) we have
Tm
Ur
(a), wpq
(b))
f (c) = fpq (c) = (gpq (a), hpq (b)) = (wpq

= ((w(pq) )Tm (a), (w(pq) )Ur (b))
= (w(pq) )Tm ×Ur (c) = (wTm ×Ur )pq (c) = wTm ×Ur (c),
showing that f = wTm ×Ur .
Let us start by noting that the scheme S is essential (by Lemma 2.8(2)), which
immediately implies c(u) = c(v) = Xn , so s(w) = s(u), σ(w) = σ(u), ε(w) = ε(v)
and e(w) = e(v). This yields s(w(ij) ) = s(u(ij) ) and e(w(ij) ) = e(v(ij) ). Furthermore, i2 (w) = i2 (u), implying i2 (w(ij) ) = i2 (u(ij) ) = i2 (wij ) by Lemma 2.9
because Xm contains B2 . Thus σ(w(ij) ) = σ(u(ij) ) = σ(wij ) and, dually, ε(w(ij) ) =
ε(v(ij) ) = ε(wij ). Also, if tm is the word function corresponding to the variety Xm
(in the sense of Theorem 2.5), then we know, by construction of words u and v,
that Xm satisfies u(ij) ≈ wij — so that tm (u(ij) ) = tm (wij ) — while Yr satisfies
v(ij) ≈ wij . By assumptions made earlier in this proof, the latter identity holds in
Xm−1 , implying tm−1 (v(ij) ) = tm−1 (wij ).
Note that we have h2 (w(ij) ) = h2 (v(ij) ) since e(w) = e(v). So, if Xm = A3 we
deduce, by Lemma 2.6(1),
h3 (w(ij) ) = h3 s(u(ij) )σ(u(ij) )h2 (w(ij) )
= sh3 (u(ij) )σ(u(ij) )h2 (v(ij) )
= sh3 (wij )σ(wij )h2 (wij )
= h3 s(wij )σ(wij )h2 (wij ) = h3 (wij ).
On the other hand, if Xm ∈ {Ak : k ≥ 4} ∪ {Bk : k ≥ 3} then by items (1) and
(2) of Lemma 2.6 we obtain
i
h
btm (w(ij) ) = b tm s(u(ij) )σ(u(ij) )ε(v(ij) )tm−1 e(v(ij) )
h
i
= b stm (u(ij) )σ(u(ij) )ε(v(ij) )etm−1 (v(ij) )


= b stm (wij )σ(wij )ε(wij )etm−1 (wij )


= b tm s(wij )σ(wij )ε(wij )tm−1 e(wij ) = btm (wij ).
But then Lemma 2.6(3) implies that tm (w(ij) ) = tm (wij ), i.e. that Xm (and thus
Tm ) satisfies w(ij) ≈ wij .
The proof that Yr satisfies w(ij) ≈ wij is similar, albeit with slight differences.
Let now tr be the word function corresponding to Yr in the sense of Theorem
2.5. The fact that Xm (and so Yr ) satisfies u(ij) ≈ wij implies tr (u(ij) ) = tr (wij ).
Furthermore, [13, Lemma 3.5] tells us that tr−1 (u(ij) ) = tr−1 (wij ) holds as well,
provided r ≥ 3. In turn, Yr satisfies v(ij) ≈ wij , thus tr (v(ij) ) = tr (wij ).
Now we have three subcases to consider. First, let Yr = B2 (which can happen,
just as the next subcase, only if Xm = A3 ). Since c(u) = c(v) = Xn , we have
i2 (w(ij) ) = i2 (u(ij) v(ij) ) = i2 (v(ij) ). On the other hand, we have already concluded

FINITE BANDS ARE FINITELY RELATED

13

that Yr satisfies v(ij) ≈ wij , so i2 (v(ij) ) = i2 (wij ) yielding i2 (w(ij) ) = i2 (wij ), as
required. Our second subcase is Yr = A3 , when h2 (w(ij) ) = h2 (u(ij) ) because of
s(w) = s(u). By items (1) and (4) of Lemma 2.6 we have:
h3 (w(ij) ) = h2 (w(ij) )ε(v(ij) )h3 e(v(ij) )
= h2 (u(ij) )ε(v(ij) )eh3 (v(ij) )
= h2 (wij )ε(wij )eh3 (wij )
= h2 (wij )ε(wij )h3 e(wij ) = h3 (wij ).
Finally, let Yr ∈ {Ak : k ≥ 4} ∪ {Bk : k ≥ 3}. Then, by invoking parts (1) and
(2) of Lemma 2.6 once again, we deduce
h
i
btr (w(ij) ) = b tr−1 s(u(ij) )σ(u(ij) )ε(v(ij) )tr e(v(ij) )
i
h
= b str−1 (u(ij) )σ(u(ij) )ε(v(ij) )etr (v(ij) )


= b str−1 (wij )σ(wij )ε(wij )etr (wij )


= b tr−1 s(wij )σ(wij )ε(wij )tr e(wij ) = btr (wij ),
whence Lemma 2.6(3) implies that tr (w(ij) ) = tr (wij ).
Hence, both Xm and Yr (with restrictions on m, r as described at the beginning
of the proof) satisfy the identity w(ij) ≈ wij . As remarked earlier, this completes
the proof that f is induced by w and confirms the theorem.

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.
Acknowledgements. The author is grateful to a thorough and perceptive referee
for a handful of comments which significantly improved the paper.
References
[1] E. Aichinger, ‘Constantive Mal’cev clones on finite sets are finitely related’, Proc. Amer.
Math. Soc. 138 (2010), 3501–3507.
[2] E. Aichinger, P. Mayr, and R. McKenzie, ‘On the number of finite algebraic structures’, J.
Eur. Math. Soc. 16 (2014), 1673–1686.
[3] L. Barto, ‘Finitely related algebras in congruence distributive varieties have near unanimity
terms’, Canad. J. Math. 65 (2013), 3–21.
[4] L. Barto, ‘Finitely related algebras in congruence modular varieties have few subpowers’, J.
Eur. Math. Soc. (to appear). Available online at:
http://www.karlin.mff.cuni.cz/∼barto/Articles/ValerioteConjecture.pdf
[5] J. Berman, P. Idziak, P. Marković, R. McKenzie, M. Valeriote, and R. Willard, ‘Varieties
with few subalgebras of powers’ Trans. Amer. Math. Soc. 362 (2010), 1445–1473.
[6] A. P. Biryukov, ‘Varieties of idempotent semigroups’, Algebra i Logika 9 (1970), 255–273 (in
Russian).
[7] A. Bulatov, P. Jeavons, and A. Krokhin, ‘Classifying the complexity of constraints using finite
algebras’, SIAM J. Comput. 34 (2005), 720–742.
[8] S. Burris and H. P. Sankappanavar, A Course in Universal Algebra, Graduate Texts in Mathematics (Springer-Verlag, New York, 1981).
[9] B. A. Davey, M. G. Jackson, J. G. Pitkethly, and Cs. Szabó, ‘Finite degree: algebras in general
and semigroups in particular’, Semigroup Forum 83 (2011), 89–110.
[10] C. F. Fennemore, ‘All varieties of bands. I, II’, Math. Nachr. 48 (1971), 237–252; ibid. 253–
262.

14

IGOR DOLINKA

[11] J. A. Gerhard, ‘The lattice of equational classes of idempotent semigroups’, J. Algebra 15
(1970), 195–224.
[12] J. A. Gerhard and M. Petrich, ‘Free bands and free ∗ -bands’, Glasgow Math. J. 28 (1986),
161–179.
[13] J. A. Gerhard and M. Petrich, ‘Varieties of bands revisited’, Proc. London Math. Soc. (3) 58
(1989), 323–350.
[14] S. V. Jablonskiı̆, ‘The structure of the upper neighbourhood for predicately describable classes
in Pk ’, Dokl. Akad. Nauk SSSR 218 (1974), 304–307 (Russian). English traslation: Sov. Math.
Dokl. 15 (1974), 1353–1356.
[15] M. Jackson (ed.), ‘General Algebra and Its Applications 2013: Problem Session’, Algebra
Univers. 74 (2015), 9–16.
[16] P. Marković, M. Maróti, and R. McKenzie, ‘Finitely related clones and algebras with cube
terms’, Order 29 (2012), 345–359.
[17] P. Mayr, ‘On finitely related semigroups’, Semigroup Forum 86 (2013), 613–633.
[18] B. A. Romov, ‘Local characterizations of Post algebras, I’, Kibernetika 5 (1976), 38–45.
[19] I. G. Rosenberg, Á. Szendrei, ‘Degrees of clones and relations’, Houston J. Math. 9 (1983),
545–580.
[20] O. Sapir, ‘The variety of idempotent semigroups is inherently non-finitely generated’ Semigroup Forum 71 (2005), 140–146.
Department of Mathematics and Informatics, University of Novi Sad, Trg Dositeja
Obradovića 4, 21101 Novi Sad, Serbia
E-mail address: dockie@dmi.uns.ac.rs

