1 Introduction
Presentations involving generators and relations may be viewed from different standpoints, depending on the algebraic context, with sometimes surprising outcomes and connections. A example of this would be Garside’s early discovery [Reference Garside13] that the (positive) braid monoid embeds in the braid group, using monoid and group presentations, involving identical (Coxeter type A) relations that avoid inverses of letters from the underlying alphabet. Quite spectacularly, Paris [Reference Paris27], relying on results of Crisp [Reference Crisp and Cossey6], generalised Garside’s result to show that all Artin monoids embed into Artin groups, now using Coxeter relations of any type, where again the relations in the respective monoid and group presentations are identical and only involve positive words (with alternating letters) that avoid formal inverses. In different directions, Baumslag [Reference Baumslag3] studied groups defined by one positive relator and showed that they are residually solvable, and, recently, Isherwood and Williams [Reference Isherwood and Williams18] investigated the Tits alternative for cyclically presented groups with positive relators of length four (and see also [Reference Edjvet and Williams12, Reference Mohamed and Williams25] for cyclically presented groups with positive relators of length three). The presentation
$$ \begin{align} \langle a, b\mid ab=1\rangle \end{align} $$
involves a positive relator of length two and yields an infinite cyclic group, as a group presentation, and clearly remains unchanged, as a group, by considering its cyclically presented counterpart
$\langle a, b\mid ab=ba=1\rangle $
. However, as a monoid presentation, (1-1) produces the bicyclic monoid, which does not embed in a group and is, in fact, a well-studied bisimple inverse semigroup that satisfies the celebrated semigroup identity
$$ \begin{align} xy^2xxyxy^2x=xy^2xyxxy^2x \end{align} $$
due to Adjan [Reference Adjan1]. Note also in [Reference Adjan1] (see reference [Reference Adjan2] with detailed proofs), Adjan introduced the class of finitely generated special monoids given by presentations whose right-hand sides are empty words, and established that if a special monoid satisfies a nontrivial identity, then it is a group or isomorphic to a bicyclic monoid or free monogenic monoid
$\langle a, b\mid b=1\rangle $
. It follows from a result of Scheiblich [Reference Scheiblich31] that the bicyclic monoid and the free monogenic inverse semigroup satisfy the same identities (see [Reference Shneerson and Easdown33, Proposition 2.1]). This fact opens up possible connections with presentations of inverse semigroups with zero, and is exploited in [Reference Shneerson and Easdown33, Sections 3 and 5], where the authors demonstrate that all finitely presented Rees quotients of free inverse semigroups have polynomial growth if and only if they satisfy a single, but complicated, semigroup identity closely related to Adjan’s identity (1-2). (In fact, as demonstrated in Theorem 6.7 below, if, in addition to having polynomial growth, the relators are all positive words, everything simplifies and the identity (1-2) alone suffices.) By contrast, Izhakian and Margolis [Reference Izhakian and Margolis19] prove that the monoid of
$2\times 2$
tropical matrices satisfies an identity closely related to (1-2), but twice as long, and its submonoid of upper triangular matrices satisfies (1-2). Moreover, Daviaud et al. [Reference Daviaud, Johnson and Kambites7] prove that the identities that hold in the monoid of
$2\times 2$
upper triangular tropical matrices are exactly the same as those that hold in the bicyclic monoid. Another variation is given by Kubat and Okninski [Reference Kubat and Okninski20], who prove that the plactic monoid of rank three, associated in a natural way with generalisations of the bicyclic monoid, satisfies a very long identity closely related to (1-2).
In 1996, the authors [Reference Shneerson and Easdown33] initiated the study of asymptotic behaviour of the class of finitely presented Rees quotients of free inverse semigroups. They showed that all semigroups from that class have polynomial or exponential growth and proved that the type of growth is algorithmically recognisable, giving a precise inverse semigroup analogue of a classical result due to Ufnarovsky [Reference Ufnarovsky36, Reference Ufnarovsky, Kostrikin and Shafarevich37] and Gilman [Reference Gilman14] in the study of finitely presented associative monomial algebras, using the de Bruijn graph of a presentation [Reference de Bruijn8]. From the point of view of inverse semigroups with zero, it is natural to replace
$1$
by
$0$
in (1-1) and then consider
$$ \begin{align} \mathrm{Inv}\langle a, b\mid ab=0\rangle \end{align} $$
regarded as a presentation of an inverse semigroup with zero (and denoted by
$S_3$
in the following below). By contrast with the bicyclic monoid, the inverse semigroup defined by (1-3) satisfies no nontrivial semigroup identity, because it is easily seen to contain a nonmonogenic free subsemigroup (see for example [Reference Easdown and Shneerson10, Section 1]). However, the authors prove (see [Reference Easdown and Shneerson10, Theorem 3.8] and Theorem 2.1 below) that this inverse semigroup is the unique principal Rees quotient of a free inverse semigroup that is not trivial or monogenic with zero and satisfies a nontrivial identity in signature with involution.
Our main goal in this paper is to give a complete description of Rees quotients of free inverse semigroups given by positive relators that satisfy nontrivial identities, including identities in signature with involution. It turns out, though this is not obvious, that all such inverse semigroups are finitely presented in the class of all inverse semigroups, so that we can use our methods to investigate connections with growth and look for complete syntactic descriptions of their presentations. Theorem 6.7 below is the main result concerning inverse semigroups from our class that satisfy a nontrivial semigroup identity. Theorem 7.10 below is the main result concerning inverse semigroups from our class that satisfy a nontrivial identity in signature with involution, but which do not satisfy a nontrivial semigroup identity. This final result relies upon, and may be regarded as, a development of the authors’ work in [Reference Easdown and Shneerson10].
This paper is organised as follows. Section 2 includes preliminaries, setting up the notation for presentations of Rees quotients of free inverse semigroups, which defines a general class
${\frak C}$
of inverse semigroups with zero. The subclass
${\frak P}$
, consisting of semigroups given by presentations where all relators are positive words over the underlying alphabet, is the focus of attention for Sections 4–7. In Section 3, which may be of independent interest, we develop a sufficient condition that guarantees that a subset of a free inverse subsemigroup, consisting of reduced words, freely generates an inverse subsemigroup, relying on Reilly’s criterion [Reference Reilly28, Reference Reilly29]. In Section 4, we provide details, including illustrations of Ufnarovsky graphs, of several inverse semigroups with zero that play important roles in the theorems of later sections. In Section 5, which is short, we make a major reduction, by showing that inverse semigroups with zero from the class
${\frak P}$
that satisfy nontrivial identities in signature with involution must be generated by at most two elements. In Section 6, we give several characterisations of inverse semigroups with zero from the class
${\frak P}$
that satisfy a nontrivial semigroup identity. This includes a syntactic description involving only two finitely presented semigroups, using three and four relators, respectively, and both of which have polynomial growth. In Section 7, the final section, we give characterisations and syntactic descriptions of all inverse semigroups with zero from the class
${\frak P}$
that satisfy a nontrivial identity in signature with involution, but which do not satisfy any nontrivial semigroup identity. All semigroups that arise are finitely presented, have exponential growth and fall within two main classes, the first of which can involve presentations with arbitrarily many relators, and another infinite class with at most four relators, but of arbitrary length. In the latter class, pairs of relators appear, reminiscent of Coxeter relations, which involve words and their reversals that alternate between two letters.
2 Preliminaries
We assume familiarity with definitions and elementary results from the theory of semigroups, which may be found in any of [Reference Clifford and Preston4, Reference Higgins15, Reference Howie17] or [Reference Lawson21]. Throughout, let A be a nonempty alphabet and put
$$ \begin{align*} B=A\cup A^{-1}, \end{align*} $$
where the elements of
$A^{-1}$
are formal inverses of corresponding elements of A and vice versa (so A and
$A^{-1}$
are disjoint and any a in A may also be denoted by
$(a^{-1})^{-1}$
). If v is a word over B, then we denote the reduced form of v by
$\overline {v}$
. Let I be an indexing set and suppose that
$c_i\in B^+$
for each
$i\in I$
. Consider the inverse semigroup S with zero given by the following presentation:
$$ \begin{align*} S=\mathrm{Inv}\langle\,A\mid c_i=0\ \mathrm{for}\ i\in I\,\rangle. \end{align*} $$
In this paper, we only consider presentations within the class of inverse semigroups with zero and abbreviate the notation slightly to write
$$ \begin{align} S=\langle\,A\mid c_i=0\ \mathrm{for}\ i\in I\,\rangle. \end{align} $$
The words
$c_i$
are called (zero) relators. Observe that S may be regarded as (isomorphic to) the Rees quotient of the free inverse semigroup
$FI_A$
generated by A with respect to the ideal generated by the relators. Elements of
$FI_A$
may be identified with Munn trees [Reference Munn26], represented by words over B that label traversals from initial to terminal vertices. Hence, if v is a word over B that is nonzero in S, then
$v=e\overline {v}$
for some nonzero idempotent e, so that
$\overline v$
is the empty word if
$v=e$
, and
$\overline {v}$
is nonzero in S if
$v\not =e$
. We say that a word u divides a word v if there are (possibly empty) words s and t such that
$u=svt$
in
$FI_A$
, which is equivalent to the word tree
$T(u)$
of u being a subtree of the word tree
$T(v)$
of v. Denote by
${\frak C}$
the class of all inverse semigroups with zero given by presentations of type (2-1).
In the case where both A and I are finite and nonempty, say
$I=\{1,\ldots , L\}$
, where L is a positive integer, then (2-1) may be written as a finite presentation:
$$ \begin{align} S=\langle\,A\mid c_i=0\ \mathrm{for}\ i=1,\ldots, L\,\rangle. \end{align} $$
It could be noted that the simplest nontrivial example of (2-2) would be
$ {\langle \,a\mid a^2=0\,\rangle } $
, which defines the five-element Brandt inverse semigroup. The class of finitely presented inverse semigroups with zero defined by presentations (2-2) may now be formally referred to as
${\frak M}_{FI}$
, and has been the subject of investigations, from the point of view of growth and identities, in previous articles by the authors [Reference Easdown and Shneerson10, Reference Easdown and Shneerson11, Reference Shneerson and Easdown33–Reference Shneerson and Easdown35]. In particular, the reader is referred to [Reference Shneerson and Easdown35, Section 2] for a comprehensive summary of terminology, notation and past results relied upon in this paper.
We say that the inverse semigroup S with zero is given by a positive presentation if the relators in (2-1) are all words over A (that is, avoiding letters from
$A^{-1}$
). The class of all such semigroups, given by positive presentations, is denoted by
${\frak P}$
. We say that a presentation of a semigroup from class
${\frak P}$
is irredundant if none of the generators is a relator and no relator is a factor of any of the others. In Section 4, we focus on some particular examples from
${\frak P}$
that play critical roles in the results in Sections 6 and 7. One of them is the inverse semigroup with zero given by the presentation
$$ \begin{align*} S_3=\langle a, b\mid ab=0\rangle \end{align*} $$
mentioned in Section 1. The following theorem then becomes a slight adjustment of [Reference Easdown and Shneerson10, Theorems 3.7 and 3.8], noting that in presentations of classical algebras, such as groups, associative rings, semigroups or monoids, if a generating set is infinite but the number of relations is finite, then there is always a free subalgebra on two generators (so that, in the case of an inverse semigroup presentation, no nontrivial identity in signature with involution can be satisfied).
Theorem 2.1. The inverse semigroup with zero
$$ \begin{align*} S_3=\langle a, b\mid ab=0\rangle \end{align*} $$
is the unique semigroup, up to isomorphism, from the class
${\frak C}$
(so, in particular, also from the class
${\frak P}$
) that has exactly one relator, is not trivial and not monogenic with zero, and satisfies a nontrivial identity in signature with involution, in fact, the following identity:
$$ \begin{align*} PQ=QP, \end{align*} $$
where
$$ \begin{align*} P=P(x,y)=[yx^2y,x^{-1}y^{-2}x^{-1}]\quad\text{and}\quad Q=Q(x,y)=[y^{-1}x^2y^{-1},x^{-1}y^2x^{-1}]. \end{align*} $$
3 Free generation of inverse subsemigroups
In this section (Proposition 3.2 below), we provide a sufficient condition for a subset of a free inverse semigroup to become a free generating set, namely that all elements of the subset be reduced words such that the length of each word exceeds the sum of the lengths of a largest prefix and a largest suffix shared by this word with other words in the set. This condition is applied in two cases below (Lemmas 5.1 and 7.9), as stepping stones towards developing our main theorems in Sections 6 and 7.
We first recall Reilly’s criterion [Reference Reilly28, Theorem 2.2], [Reference Reilly29] for identifying free generating sets in inverse semigroups.
If K is a subset of an inverse semigroup S, then K is a set of free generators for the inverse subsemigroup K generates if and only if
$K\cap K^{-1}$
is empty, and if
$y\in K\cup K^{-1}$
and
$yy^{-1}$
is annihilated by a product of idempotents of the form
$w_1w_1^{-1}\cdots w_nw_n^{-1}$
, where
$w_1,\ldots , w_n$
are reduced words with respect to the alphabet K, then y is the first letter of
$w_j$
for some j.
In the previous statement, consider the case where
$S=FI_A$
happens to be a free inverse semigroup with respect to some alphabet A. Suppose y is a reduced word over A such that
$yy^{-1}$
is annihilated by a product of idempotents. Then, y labels some geodesic path from the initial vertex of the Munn tree of that product of idempotents to some vertex, which lies in the Munn tree of one of the idempotents. However, this unique geodesic path must appear also in that particular Munn tree, since it contains the initial vertex of the Munn tree of the product of idempotents. Hence,
$yy^{-1}$
is in fact annihilated by just one of the idempotents used to form the product. We therefore have the following simplification of Reilly’s criterion in this special case.
If K is a subset of a free inverse semigroup
$FI_A$
with respect to some alphabet A, such that all elements of K are reduced, then K is a set of free generators for the inverse subsemigroup K generates if and only if
$K\cap K^{-1}$
is empty, and if
$y\in K\cup K^{-1}$
and
$yy^{-1}$
is annihilated by an idempotent
$ww^{-1}$
, where w is some reduced word with respect to the alphabet K, then y is the first letter of w.
The following terminology adapted from [Reference Easdown and Shneerson11, Section 3] is used in the proof of Proposition 3.2 below. If w is a word over B, then we say w has the whisker property if the word tree
$T(w)$
contains an underlying chain
${\mathcal C}$
of vertices such that: (i) each leaf vertex of
${\mathcal C}$
is a leaf of
$T(w)$
; (ii) each leaf of
$T(w)$
that is not a leaf of
${\mathcal C}$
is connected to
${\mathcal C}$
by a chain of edges; (iii) degrees of vertices of
$T(w)$
are only allowed to be
$1$
,
$2$
or
$3$
; and (iv) vertices of degree
$3$
only occur on
${\mathcal C}$
. These connecting chains are called whiskers and are themselves word trees of reduced words.
In Figure 1, the thick line is intended to represent the underlying chain
${\mathcal C}$
and the thin lines represent the whiskers. Whiskers may be of varying length. The definition includes the possibility that
$T(w)$
coincides with the chain
${\mathcal C}$
, in which case, there are no whiskers. This would occur, for example, if w is a reduced word.
Word tree with whisker property.
Example 3.1. Let
$A=\{a,b,c\}$
and consider the following words over B:
$$ \begin{align*} u=a^2b^3,\quad u_1=b^{-2}c^4,\quad u_2=c^{-2}a^2,\quad u_3=a^{-1}b^3. \end{align*} $$
Put
$$ \begin{align*} w=uu_1u_2u_3=a^2b(b^2b^{-2})c^2(c^2c^{-2})a(aa^{-1})b^3. \end{align*} $$
Then, the word tree
$T(w)$
has the whisker property (see Figure 2), with an underlying chain
${\mathcal C}$
traversed by the reduced part of w, which is the word
$a^2bc^2ab^3$
, and three whiskers traversed by
$b^2$
,
$c^2$
and a, respectively. It is straightforward to check that condition (3-1) in the statement of Proposition 3.2 below is satisfied by
${X=\{u, u_1, u_2, u_3\}}$
, so, in fact, X freely generates a free inverse subsemigroup of
$FI_A$
.
Word tree of
$w=uu_1u_2u_3$
.
We now provide the following sufficient condition for free generation of subsets of free inverse semigroups, which becomes routine to check in our applications below (Lemmas 5.1 and 7.9 below).
Proposition 3.2. Let
$FI_A$
be the free inverse semigroup over an alphabet A. Let X be a nonempty subset of
$FI_A$
consisting of reduced words such that
$X\cap X^{-1}$
is empty. For each
$x\in X\cup X^{-1}$
, let
$m_x$
be the maximum length of any prefix of x that x has in common with any other element of
$X\cup X^{-1}$
, and let
$M_x$
be the maximum length of any suffix of x that x has in common with any other element of
$X\cup X^{-1}$
. Suppose that the following condition holds:
$$ \begin{align} m_x+M_x< \ell(x)\quad \text{ for all } x\in X\text{, where } \ell(x) \text{ is the number of letters in } x. \end{align} $$
Then, X is a free generating set for the inverse subsemigroup generated by X.
Proof. Put
$Y=X\cup X^{-1}$
, which is a disjoint union by assumption. For each
$x\in Y$
, denote by
$x\varphi $
the prefix of x obtained by deleting from x the suffix of length
$M_x$
. Observe, by (3-1), first, that
$$ \begin{align} x\text{ is not a prefix of } y\quad \text{ for all distinct } x,y\in Y, \end{align} $$
and, second, that
$$ \begin{align} x\varphi \text{ is not a prefix of } y\varphi\quad\text{ for all distinct } x,y\in Y. \end{align} $$
For any
$x,y\in Y$
, such that
$y\not =x^{-1}$
, denote by
$P(x,y)$
the length of the largest prefix of y in common with
$x^{-1}$
. Hence, by (3-1),
$$ \begin{align*} P(x,y)\le m_y<\ell(y)-M_y. \end{align*} $$
Let
$u,u_1,\ldots ,u_n\in Y$
and suppose that
$w=uu_1\cdots u_n$
is a reduced word with respect to Y. We show that the word tree of w has the whisker property (as explained above), such that an initial segment of the underlying chain
${\mathcal C}$
is the word tree of
$u\varphi $
. This is certainly true if
$n=0$
, because the word tree of a reduced word is a chain, so we may assume
$n\ge 1$
. Note that
$u^{-1}$
and
$u_1$
are different words, because w is reduced with respect to Y. Hence, by (3-2), we have that
$u^{-1}$
is not a prefix of
$u_1$
. Put
$e_1=\ell (u)$
and
$$ \begin{align*} d_1=\ell(u)-P(u_1,u). \end{align*} $$
Then,
$d_1$
is positive and the initial vertex of the Munn tree of
$uu_1$
must be a leaf. Note that
$d_1=\ell (u)$
if and only if
$uu_1$
is reduced. Now put
$$ \begin{align*} e_2=\ell(u_1)-P(u_1,u), \end{align*} $$
which is positive by condition (3-1). Observe that the word tree
$T(u)$
is a chain of length
$e_1$
and
$T(uu_1)$
is a word tree with the whisker property, having an underlying chain of length
$d_1+e_2$
, with at most one whisker, of length
$P(u_1,u)$
, when
$P(u_1,u)$
is positive, attached to the chain at the node located
$d_1$
edges from the initial vertex (see Figure 3).
Word tree of
$uu_1$
.
This is the start of an inductive process. If
$n=1$
, then we have finished, so suppose that
$n\ge 2$
. Put
$u_0=u$
. For
$2\le i\le n$
, put
$$ \begin{align*} d_i=\ell(u_{i-1})-P(u_{i-1},u_{i-2})-P(u_i,u_{i-1}) \end{align*} $$
and, for
$2\le i \le n+1$
, put
$$ \begin{align*} e_i= \ell(u_{i-1})-P(u_{i-1},u_{i-2}), \end{align*} $$
noting that this extends the definition of
$e_2$
, and both
$d_i$
and
$e_i$
are positive, by condition (3-1). Note also that, for
$1\le i\le n$
,
$$ \begin{align*} e_i= d_i+P(u_i,u_{i-1}), \end{align*} $$
and
$e_i = d_i$
if and only if the word
$u_{i-1}u_i$
is reduced with respect to A. Suppose, as inductive hypothesis, that
$1\le k<n$
and the word tree
$T(uu_1\cdots u_k)$
has the whisker property with an underlying chain
${\mathcal C}_k$
of length
$$ \begin{align*} d_1+\cdots+d_{k}+e_{k+1} \end{align*} $$
with at most k whiskers, being the number of elements i such that
$1\le i\le k$
and
$u_{i-1}u_i$
is reducible with respect to A. All whiskers of lengths amongst the positive values of
$$ \begin{align*} P(u_1, u_0), P(u_2,u_1), \ldots, P(u_k,u_{k-1}) \end{align*} $$
are attached to the nodes located
$$ \begin{align*} d_1, d_1+d_2, \ldots, d_1+\cdots+d_k \end{align*} $$
edges, respectively, from the initial vertex of
${\mathcal C}_k$
. Observe that
$u_k^{-1}$
cannot be a prefix of
$u_{k+1}$
, by (3-2), since
$u_k^{-1}$
and
$u_{k+1}$
are different words, as w is reduced with respect to Y. We modify the chain
${\mathcal C}_k$
by removing edges corresponding to the suffix of
$u_k$
of length
$P(u_{k+1},u_k)$
and then adding edges corresponding to the suffix of
$u_{k+1}$
obtained by deleting its prefix (in common with
$u_k^{-1}$
) of length
$P(u_{k+1},u_k)$
. This produces a new chain
${\mathcal C}_{k+1}$
of length
$$ \begin{align*} d_1+\cdots+d_{k}+d_{k+1}+e_{k+2}. \end{align*} $$
We can now reinstate the edges corresponding to the common prefix of
$u_k^{-1}$
and
$u_{k+1}$
to add a whisker to the tree of length
$P(u_{k+1},u_k)$
, in the case where this length is positive. This completes the construction of the word tree of
$T(uu_1\cdots u_ku_{k+1})$
, which again has the whisker property, and establishes the inductive step. Figure 4 illustrates the final outcome of this construction. In the illustration, the whiskers are drawn with varying lengths, though, of course, whiskers could have the same lengths, and whiskers do not exist at nodes where the concatenation of consecutive words yields a reduced word.
Word tree of
$w=uu_1\cdots u_n$
.
This shows that the word tree of
$w=uu_1\cdots u_n$
has the whisker property. The initial segment of the underlying chain, up to and including the node to which the first whisker is attached, or the entire chain if there are no whiskers, becomes the Munn tree of a reduced word for which
$u\varphi $
is a prefix, with the initial vertex being the initial vertex of the underlying chain. Suppose now that
$y\in Y$
and
$yy^{-1}$
is annihilated by an idempotent
$ww^{-1}$
, where
$w=uu_1\cdots u_n$
is a reduced word with respect to the alphabet Y. We want to show that
$y=u$
. Suppose to the contrary that
$y\not =u$
and denote by
$$ \begin{align*} (T,\alpha,\alpha)=\big(T(w),\alpha(w),\alpha(w)\big) \end{align*} $$
the Munn tree of
$ww^{-1}$
(where the initial and terminal vertices coincide). By what we proved, T has the whisker property with respect to an underlying chain, where
$\alpha $
is the initial vertex of this chain, and the initial segment of this chain, up to and including the vertex where the first whisker is attached, or the entire chain if there are no whiskers, extends (and possibly equals) the Munn tree of
$u\varphi $
. Denote by
$(T',\alpha , \alpha )$
the Munn tree of the idempotent (
$u\varphi )(u\varphi )^{-1}$
, which typically would use just a fragment of the underlying chain of T. Since
$yy^{-1}$
is annihilated by w, we have that
$y\varphi $
labels some unique path in T emanating from
$\alpha $
. Hence, either (i) this path exhausts
$T'$
, so that
$u\varphi $
is a prefix for
$y\varphi $
, or (ii)
$y\varphi $
labels a path that terminates inside
$T'$
, so that
$y\varphi $
is a prefix of
$u\varphi $
. Both cases (i) and (ii) contradict (3-3), since y and u are different words. Hence, in fact,
$y=u$
, so that Reilly’s criterion is satisfied, and X becomes a free generating set for the inverse subsemigroup of
$FI_A$
that it generates. This completes the proof of the proposition.
Condition (3-1) is equivalent to condition (N2) in the definition of a Nielsen basis [Reference Lyndon and Schupp23, Ch. 1], so we have immediately the following.
Corollary 3.3. Let
$F(A)$
be the free group over a finite alphabet A. Let X be a finite subset of
$F(A)$
consisting of reduced words. If X is a Nielsen basis, then X freely generates an inverse subsemigroup of the free inverse semigroup
$FI_A$
.
Another related sufficient condition for a finite subset X of reduced words over a finite alphabet
$A\cup A^{-1}$
to be a basis for a free inverse subsemigroup
$\mathrm {Inv}\langle X\rangle $
of
$FI_A$
was found by Margolis and Meakin [Reference Margolis and Meakin24, remark following Theorem 3.6], who considered closed finitely generated inverse subsemigroups. We also mention their example [Reference Margolis and Meakin24, page 88], the set
$X=\{ab, ac, bc\}$
, which freely generates a free inverse subsemigroup over the alphabet
$\{a,b,c\}$
. Since X does not satisfy condition (3-1), this condition is not necessary in general for free generation of an inverse subsemigroup.
4 Examples
In this section, we provide details, including the graphs, of particular inverse semigroups with zero, namely
$S_1$
,
$S_2$
,
$S_3$
,
$S_4$
and
$S_8(1)$
, which play key roles in the two main results of this paper (Theorems 6.7 and 7.10 below). We first recall, from [Reference Easdown and Shneerson11, Section 2], the definition of the Ufnarovsky graph
$\,\Gamma _S$
of a semigroup S given by an irredundant presentation of the form (2-2). Put
$$ \begin{align*} d+1 = \mathrm{\max}\{\,\ell(c)\,\vert\, c \mathrm{\ is\ a\ reduced\ word\ } {\mathcal J}\mathrm{-equivalent\ to\ some\ relator}\,\}. \end{align*} $$
By irredundancy,
$d\ge 1$
. Vertices of
$\Gamma _S$
are defined to be reduced words of length d that are nonzero in S. If
$v_1$
and
$v_2$
are vertices, then a directed edge from
$v_1$
to
$v_2$
is defined if there exist letters
$g,h \in B$
such that
$v_1g$
is a reduced word that is nonzero in S and
$v_1g = hv_2$
. The letter g may be regarded as a label for this edge. Paths in
$\Gamma _S$
may then be labelled by reduced words that are nonzero in S. If
$vu = u^\prime v^\prime $
is any nonzero reduced word where v and
$v^\prime $
have length d, then u labels a path in
$\Gamma _S$
emanating from v and terminating at
$v^\prime $
.
Example 4.1. The following inverse semigroups play a critical role in describing and characterising semigroups in the class
${\frak P}$
that satisfy a nontrivial semigroup identity (Theorem 6.7 below):
$$ \begin{align*} S_1=\langle a,b\mid a^2=b^2=ab=0\rangle\quad\mathrm{and}\quad S_2=\langle a,b\mid a^2=b^2=ab=ba=0\rangle. \end{align*} $$
They are both homomorphic images of the following semigroups:
$$ \begin{align*} S_3=\langle a,b\mid ab=0\rangle\quad\mathrm{and}\quad S_4=\langle a,b\mid a^2=b^2=0\rangle, \end{align*} $$
which, in turn, play a critical role in describing semigroups from
${\frak P}$
that do not satisfy a nontrivial semigroup identity, but satisfy a nontrivial identity in signature with involution (Theorem 7.10 below). It could be noted that the presentation for
$S_2$
would reduce to the three element null semigroup if the presentation were interpreted within the class of all semigroups with zero.
The inverse semigroup
$S_1$
has the Ufnarovsky graph in Figure 5, leading to a detailed analysis in [Reference Easdown and Shneerson11, Example 2.2].
Ufnarovsky graph of
$S_1$
.
We record now some properties of
$S_1$
and canonical forms for its elements, which may be of independent interest and is used later to prove that
$S_1$
satisfies Adjan’s identity (1-2) (see Theorem 6.6 below). In what follows, put
$A=\{a,b\}$
and
${B=A\cup A^{-1}}$
. The relators
$a^2$
,
$b^2$
and
$ab$
severely restrict degrees of vertices of word trees of nonzero elements of
$S_1$
. Degrees can only be one or two, so that word trees become chains. Hence a traversal of any given Munn tree can be achieved by moving from the initial vertex to the nearest leaf and back to the initial vertex, and then along the geodesic (which could be empty if the element is idempotent) to the terminal vertex, and then to the other leaf and back to the terminal vertex. The forms of reduced words that are nonzero can be deduced from the graph in Figure 5. Nonzero reduced words label paths that may oscillate back and forth, using the cycle formed by
$a^{-1}$
and b, or using the cycle formed by a and
$b^{-1}$
, with at most one possible transition from the first cycle to the second. This proves the following lemma, with two general forms, depending on whether
$ba$
is a divisor.
Lemma 4.2. If u is a nonzero element of
$S_1$
, then
$$ \begin{align} u^{\pm1}=s^{-1}sztt^{-1} \end{align} $$
for some (possibly empty) words s, z, t over the alphabet B such that
$szt$
is reduced and has one of the following two forms:
$$ \begin{align} szt=a^{-\delta}(ba^{-1})^\gamma b^{\varepsilon} \end{align} $$
for some
$\gamma \ge 0$
and
$\delta ,\varepsilon \in \{0,1\}$
, such that
$\delta +\gamma +\varepsilon>0$
, occurring when
$ba$
is not a divisor of u, or
$$ \begin{align} szt=a^{-\delta}(ba^{-1})^\alpha ba(b^{-1}a)^\beta b^{-\varepsilon} \end{align} $$
for some
$\alpha ,\beta \ge 0$
and
$\delta ,\varepsilon \in \{0,1\}$
, occurring when
$ba$
is a divisor of u.
We can now describe elements of
$S_1$
that are reduced and whose squares are nonzero. Note that if a reduced word w is not cyclically reduced, then the word tree of
$w^2$
would have a vertex of degree greater than two, so would become zero in
$S_1$
.
Lemma 4.3. Let w be a nonempty reduced word such that
$w^2$
is nonzero in
$S_1$
. Then,
$$ \begin{align} w=(ab^{-1})^\gamma\quad\text{or}\quad w=(a^{-1}b)^\gamma \end{align} $$
for some nonzero integer
$\gamma $
.
Proof. Suppose first that
$ba$
divides w. Without loss of generality (interchanging w and
$w^{-1}$
if necessary), we may suppose that w has the form given by (4-3) for some
$\alpha ,\beta \ge 0$
and
$\delta ,\varepsilon \in \{0,1\}$
:
$$ \begin{align*} w=a^{-\delta}(ba^{-1})^\alpha ba(b^{-1}a)^\beta b^{-\varepsilon}. \end{align*} $$
If
$\delta =\varepsilon =1$
or
$\delta =\varepsilon =0$
, then the word
$w^2$
is reduced with
$b^{-1}a^{-1}$
or
$ab$
, respectively, as a subword, so becomes zero in
$S_1$
, which is a contradiction. Hence,
$\delta =1$
and
$\varepsilon =0$
, or
$\delta =0$
and
$\varepsilon =1$
. However, then, w is not cyclically reduced, so
$w^2$
becomes zero in
$S_1$
, by the observation preceding the statement of this lemma, which again is a contradiction. This proves that
$ba$
does not divide w. Hence, w has the form given by the right-hand side of (4-2) for some
$\gamma , \delta , \varepsilon $
. However, w cannot begin and end with the same letter, since
$w^2$
is nonzero, and it follows that w has one of the forms (4-4) for some nonzero integer
$\gamma $
, completing the proof of the lemma.
The general descriptions given by the previous two lemmas, in the case where
$ba$
is not a divisor, lead naturally to the following subsemigroups of
$S_1\backslash \{0\}$
: put
$$ \begin{align*} L_1&=\{(ab^{-1})^{-\alpha}b^\varepsilon b^{-\varepsilon} (ab^{-1})^{\alpha+\beta+\gamma}a^{\delta}a^{-\delta}(ab^{-1})^{-\gamma}\mid\alpha,\beta,\gamma \ge 0, \varepsilon,\delta\in\{0,1\},\\ &\quad\varepsilon+\delta+\alpha+\beta+\gamma>0\} \end{align*} $$
and
$$ \begin{align*} L_2&=\{(a^{-1}b)^{-\alpha}b^{-\varepsilon} b^{\varepsilon} (a^{-1}b)^{\alpha+\beta+\gamma}a^{-\delta}a^{\delta}(a^{-1}b)^{-\gamma}\mid \alpha,\beta,\gamma \ge 0,\varepsilon,\delta\in\{0,1\},\\ &\quad\varepsilon+\delta+\alpha+\beta+\gamma>0\}, \end{align*} $$
and put
$$ \begin{align*} I_1=L_1\cup L_1^{-1}\quad\text{and}\quad I_2=L_2\cup L_2^{-1}. \end{align*} $$
The underlying word trees of elements of
$I_1$
and
$I_2$
are chains. It follows by inspection, since the multiplication of Munn trees simplifies, that both
$I_1$
and
$I_2$
are closed under multiplication and inversion, so become inverse subsemigroups of
$S_1\backslash \{0\}$
. The reduced forms of elements of
$I_1$
and
$I_2$
are integer powers of
$ab^{-1}$
and
$a^{-1}b$
, respectively.
Lemma 4.4. The following statements hold.
-
(i) The subsets
$I_1$
and
$I_2$
become isomorphic inverse subsemigroups of
$S_1$
and embed in the free monogenic inverse semigroup. -
(ii) If u is an element of
$S_1$
such that
$u^2$
is nonzero (which includes the case where u is a nonzero idempotent) and the word
$ba$
does not divide u, then
$u\in I_1$
or
$u\in I_2$
. -
(iii) If
$u\in I_1$
and
$v\in I_2$
such that at least one of u or v is not idempotent, then either
$uv=0$
in
$S_1$
or
$vu=0$
in
$S_1$
.
Proof. Part (i) follows because the mapping
$a\mapsto a^{-1}$
and
$b\mapsto b^{-1}$
induces an isomorphism between
$I_1$
and
$I_2$
, and the mapping
$a\mapsto x$
and
$b\mapsto x^{-1}$
induces an embedding from
$I_1$
and
$I_2$
, respectively, into
$FI_{x}$
, the free monogenic inverse semigroup generated by x. Part (ii) follows by inspection, using Lemmas 4.2 and 4.3, noting that z is the empty word in (4-1) and (4-2) when u is idempotent. To verify part (iii), suppose without loss of generality that
$u\in L_1$
is not idempotent, so that
$\overline {u}=(ab^{-1})^\lambda $
is a nonempty word for some
$\lambda>0$
, and
$v\in I_2$
, so that v begins with
$a^{-1}$
or
$b^{-1}$
(including the case where v is idempotent). In both cases,
$\overline {u}v=0$
in
$S_1$
, so that
$uv=0$
in
$S_1$
(since
$u=e\overline {u}$
for some idempotent e). This suffices to verify part (iii), completing the proof of the lemma.
Remark 4.5. By part (i) of Lemma 4.4,
$I_1$
and
$I_2$
embed in the free monogenic inverse semigroup, so that they satisfy Adjan’s identity (1-2), by [Reference Scheiblich31] and [Reference Shneerson and Easdown33, Proposition 2.1]. Later, we prove that
$S_1$
, in its entirety, also satisfies Adjan’s identity (see Theorem 6.6 below).
By adding the relator
$ba$
to the presentation for
$S_1$
, we get the inverse semigroup
$S_2$
, whose simplified graph is shown in Figure 6.
Ufnarovsky graph of
$S_2$
.
By contrast, the graphs of
$S_3$
and
$S_4$
are depicted in Figures 7 and 8, respectively.
Ufnarovsky graph of
$S_3$
.
Ufnarovsky graph of
$S_4$
.
The semigroups
$S_3$
and
$S_4$
clearly have exponential growth, as their graphs contain vertices in different cycles. There are many ways of seeing that
$S_2$
has polynomial growth. This follows from the fact that
$S_1$
has polynomial growth, explained from several different points of view in [Reference Easdown and Shneerson11], and the fact that
$S_2$
is a homomorphic image of
$S_1$
. The language of nonzero reduced words in
$S_2$
can be read from the graph and is
$$ \begin{align*} (1\cup a)(b^{-1}a)^*(1\cup b^{-1})\cup(1\cup a)(b^{-1}a)^*(1\cup b^{-1}). \end{align*} $$
The Gelfand–Kirillov dimension of
$S_1$
was calculated in [Reference Easdown and Shneerson11, Example 2.3] to be four. In the case of
$S_2$
, the language of nonzero reduced words has Gelfand–Kirillov dimension one (because of the isolated cycles), and the calculation (which is an adaptation of the technique used in [Reference Shneerson32]) involving word trees that are chains is the same, associating with every reduced word of length m some subset that consists of a quadratic function in m distinct nonzero elements of the semigroup
$S_2$
. It follows that the Gelfand–Kirillov dimension of
$S_2$
is three.
Observe further that
$S_2$
is a terminal object in the subclass of
${\frak P}$
, in the sense that
$S_2$
has no proper homomorphic images involving positive relators other than inverse semigroups that are trivial or the five-element Brandt inverse semigroup
$\langle a\mid a^2=0\rangle $
.
Example 4.6. By contrast with
$S_1$
and
$S_2$
, the following inverse semigroup has exponential growth, and plays a central role in describing and characterising semigroups in the class
${\frak P}$
that satisfy an identity in signature with involution:
$$ \begin{align*} S_{\Pi}=\langle a,b\mid a^2=b^2=aba=bab=0\rangle \end{align*} $$
(see Proposition 7.8 and Theorem 7.10 below, where
$S_{\Pi }=S_8(1)$
), with the graph depicted in Figure 9. It is clear that
$S_{\Pi }$
has exponential growth because there are vertices in the graph contained in different cycles. Observe that
$S_{\Pi }$
also lies on a boundary, in the sense that it has no proper homomorphic images having exponential growth within the class of semigroups in
${\frak P}$
. Any proper homomorphic image of
$S_{\Pi }$
obtained by adding positive relators is either trivial or isomorphic to the inverse monogenic semigroup
$\langle a\mid a^2=0\rangle $
,
$S_1$
or
$S_2$
, described above.
Ufnarovsky graph of
$S_{\Pi }$
.
5 Reduction to at most two generators
In this short section, we show that inverse semigroups with zero from the class
${\frak P}$
that satisfy some nontrivial identity in signature with involution (which, of course, includes those members of the class satisfying some nontrivial semigroup identity) have presentations involving at most two generators. This major reduction relies on the following lemma, which is an application of Proposition 3.2 and which, in turn, relies on Reilly’s criterion [Reference Reilly28].
Lemma 5.1. Let A be an alphabet containing three distinct letters a, b and c, and let T be the inverse subsemigroup of
$FI_A$
generated by
$$ \begin{align*} u=a^{-1}bc^{-1}a\quad\text{and}\quad v=c^{-1}ba^{-1}c. \end{align*} $$
Then:
-
(a) T is freely generated by u and v;
-
(b) the only reduced words over the alphabet
$\{a,b,c\}$
that divide elements of T in
$FI_A$
, and which are positive with respect to
$\{a,b,c\}$
, are the letters a, b and c.
Proof. Consider the alphabet
$Y=\{u,v\}$
. Observe, by inspection, that for all
${y\in Y\cup Y^{-1}}$
, we have
$\ell (y)=4$
and
$m_y=M_y=1$
, so that
$$ \begin{align*} m_y+M_y=2<\ell(y)=4, \end{align*} $$
so that (3-1) is satisfied. By Proposition 3.2, condition (a) holds. By inspection of word trees of elements of T, condition (b) holds, completing the proof of the lemma.
Theorem 5.2. Consider an inverse semigroup with zero
$$ \begin{align*}S=\langle \,A\mid c_i=0\ \text{for}\ i \in I\, \rangle\end{align*} $$
from the class
${\frak P}$
such that
$c_i\not \in A$
for all
$i\in I$
. If S does not contain a nonmonogenic free inverse subsemigroup, then
$|A|\le 2$
. In particular, if S satisfies a nontrivial identity in signature with involution, then
$|A|$
cannot be larger than two.
Proof. Suppose that S does not contain a nonmonogenic free inverse subsemigroup and that
$|A|\ge 3$
, so that A contains distinct letters a, b and c. Let T be the inverse subsemigroup of
$FI_A$
generated by
$a^{-1}bc^{-1}a$
and
$c^{-1}ba^{-1}c$
. By Lemma 5.1, T is a free nonmonogenic inverse semigroup. If no element of T is zero in S, then S contains a free nonmonogenic inverse subsemigroup, which is a contradiction. Hence, at least one element of T is divided by a positive relator
$c_i$
for some
$i\in I$
. By Lemma 5.1,
$c_i$
equals one of a, b or c, so that
$c_i\in A$
, producing another contradiction, which completes the proof.
6 Semigroup identities and polynomial growth
We begin this section with some preparatory lemmas, leading to a proof that
$S_1$
(and hence also its homomorphic image
$S_2$
) satisfies Adjan’s identity for the bicyclic monoid [Reference Adjan1]. This result then becomes a stepping stone to providing a cascade of characterisations, and a complete syntactic description, of semigroups from the class
${\frak P}$
that satisfy a nontrivial semigroup identity (Theorem 6.7 below).
Lemma 6.1. Let w be a nonempty reduced word such that
$w^2$
is nonzero in
$S_1$
. Put
$$ \begin{align*}u=baa^{-1} w b^{-1}ba.\end{align*} $$
Then,
$u=0$
in
$S_1$
.
Proof. By Lemma 4.3,
$w=(a^{-1}b)^\gamma $
,
$(b^{-1}a)^\gamma $
,
$(ab^{-1})^\gamma $
or
$(ba^{-1})^\gamma $
for some
$\gamma>0$
. Considering each possibility in turn, by inspection, u is divisible by
$a^{-2}$
,
$a^2$
,
$b^{-2}$
or
$b^2$
, respectively. In each case,
$u=0$
in
$S_1$
, completing the proof of the lemma.
Lemma 6.2. Let w be a nonempty reduced word such that
$w^2$
is nonzero in
$S_1$
. Put
$u=zwz^{-1}$
, where
$$ \begin{align} z=ba(b^{-1}a)^\beta b^{-\varepsilon} \end{align} $$
for some
$\beta \ge 0$
and
$\varepsilon \in \{0,1\}$
. Then,
$u=0$
in
$S_1$
.
Proof. By Lemma 4.3,
$w=(a^{-1}b)^\gamma $
,
$(b^{-1}a)^\gamma $
,
$(ab^{-1})^\gamma $
or
$(ba^{-1})^\gamma $
for some
$\gamma>0$
. Consider the case where
$\varepsilon =0$
. Suppose first that
$w=(a^{-1}b)^\gamma $
. Then,
$$ \begin{align*} u=ba(b^{-1}a)^\beta (a^{-1}b)^\gamma (a^{-1}b)^\beta a^{-1}b^{-1} \end{align*} $$
is divisible by
$$ \begin{align*} ba(a^{-1}b)^\gamma a^{-1}b^{-1}=baa^{-1}b(a^{-1}b)^{\gamma-1} a^{-1}b^{-1}, \end{align*} $$
noting that powers of
$b^{-1}a$
commute with powers of
$a^{-1}b$
in the free group, which in turn is divisible by
$b^2$
. If, second,
$w=(b^{-1}a)^\gamma $
, then, by a similar calculation, u is divisible by
$b^{-2}$
. If, third,
$w=(ab^{-1})^\gamma $
, then
$$ \begin{align*} u=ba(b^{-1}a)^\beta (ab^{-1})^\gamma (a^{-1}b)^\beta a^{-1}b^{-1} \end{align*} $$
is divisible by
$a^2$
. If, fourth,
$w=(ba^{-1})^\gamma $
, then, similarly, u is divisible by
$a^{-2}$
. In all subcases,
$u=0$
in
$S_1$
. Consider now the case where
$\varepsilon =1$
. If, first,
$w=(a^{-1}b)^\gamma $
, then
$$ \begin{align*} u=ba(b^{-1}a)^\beta b^{-1} (a^{-1}b)^\gamma b(a^{-1}b)^\beta a^{-1}b^{-1} \end{align*} $$
is divisible by
$b^2$
. If, second,
$w=(b^{-1}a)^\gamma $
, then, similarly, u is divided by
$b^{-2}$
. If, third,
$w=(ab^{-1})^\gamma $
, then
$$ \begin{align*} u=ba(b^{-1}a)^\beta b^{-1} (ab^{-1})^\gamma b(a^{-1}b)^\beta a^{-1}b^{-1}=ba(b^{-1}a)^{\beta+\gamma} b^{-1}b(a^{-1}b)^\beta a^{-1}b^{-1}, \end{align*} $$
which is divided by
$$ \begin{align*} ba(b^{-1}a)^{\beta+\gamma}(a^{-1}b)^\beta a^{-1}b^{-1}, \end{align*} $$
which in turn is divided by
$b^{-2}$
. If, fourth,
$w=(ba^{-1})^\gamma $
, then, similarly, u is divided by
$b^2$
. In all subcases, again,
$u=0$
in
$S_1$
, completing the proof of the lemma.
Lemma 6.3. Let w be a nonempty reduced word such that
$w^2$
is nonzero in
$S_1$
. Put
$u=z^{-1}wz$
, where
$$ \begin{align} z=a^{-\delta}(ba^{-1})^\alpha ba \end{align} $$
for some
$\alpha \ge 0$
and
$\delta \in \{0,1\}$
. Then,
$u=0$
in
$S_1$
.
Proof. This follows from Lemma 6.2 by applying the automorphism of
$S_1$
induced by the mapping
$a\mapsto b^{-1}$
and
$b\mapsto a^{-1}$
.
Lemma 6.4. Suppose that v is a nonzero idempotent in
$S_1$
divided by
$ba$
, and that w is a nonempty reduced word such that
$w^2$
is nonzero in
$S_1$
. Then,
$ vwv=0 $
in
$S_1$
.
Proof. Because
$\overline {w}$
is a nonempty reduced word such that
$\overline {w}^2$
is nonzero in
$S_1$
, the Munn tree of v has the same initial and terminal vertices. By (4-1) and (4-3) of Lemma 4.2, where z is empty, the word tree of v is a chain traversed by some reduced word u of the form
$$ \begin{align} u=a^{-\delta}(ba^{-1})^\alpha ba(b^{-1}a)^{\beta}b^{-\varepsilon}, \end{align} $$
where
$\alpha ,\beta \ge 0$
and
$\delta ,\varepsilon \in \{0,1\}$
, and there exist reduced words s and t such that
$u=st$
and
$$ \begin{align*} v=s^{-1}stt^{-1}. \end{align*} $$
Suppose first that s ends with b and t begins with a, so that
$s=s_0b$
and
$t=at_0$
for some words
$s_0$
and
$t_0$
. Then,
$$ \begin{align*} vwv=b^{-1}s_0^{-1}s^{}_0bat^{}_0t_0^{-1}a^{-1}wb^{-1}s_0^{-1}s^{}_0bat^{}_0t_0^{-1}a^{-1} \end{align*} $$
is divided by
$baa^{-1}wb^{-1}ba$
, which is zero in
$S_1$
, by Lemma 6.1, so that
$vwv$
is zero in
$S_1$
. Suppose next that
$ba$
is a subword of s, so that
$s=s_0bas_1$
for some words
$s_0$
and
$s_1$
. Then,
$$ \begin{align*} vwv=s_1^{-1}a^{-1}b^{-1}s_0^{-1}s^{}_0bas^{}_1tt^{-1}ws_1^{-1}a^{-1}b^{-1}s_0^{-1}s^{}_0bas^{}_1tt^{-1} \end{align*} $$
is divided by
$$ \begin{align*} zwz^{-1}=bas^{}_1ws^{-1}_1a^{-1}b^{-1}, \end{align*} $$
where
$z=bas_1$
. However, from the description of u in (6-3),
$$ \begin{align*} z=ba(b^{-1}a)^\beta b^{-\varepsilon} \end{align*} $$
for some
$\beta \ge 0$
and
$\varepsilon \in \{0,1\}$
, which is (6-1). By Lemma 6.2,
$zwz^{-1}=0$
in
$S_1$
, whence
$vwv=0$
in
$S_1$
. Suppose finally that
$ba$
is a subword of t. By a similar argument, based now on (6-2) and Lemma 6.3, we have again that
$vwv=0$
in
$S_1$
, completing the proof of the lemma.
Lemma 6.5. Suppose that v is a nonempty word such that v is not idempotent in
$S_1$
and
$ba$
divides v in
$S_1$
. Then,
$ v^2=0 $
in
$S_1$
.
Proof. Without loss of generality, by (4-1) and (4-3) of Lemma 4.2,
$$ \begin{align*} v=s^{-1}sztt^{-1}, \end{align*} $$
where
$$ \begin{align} szt=a^{-\delta}(ba^{-1})^\alpha ba(b^{-1}a)^\beta b^{-\varepsilon} \end{align} $$
for some
$\alpha ,\beta \ge 0$
and
$\delta ,\varepsilon \in \{0,1\}$
. Then,
$ z=\overline {v} $
, which is nonempty, since v is not idempotent. If
$z^2=0$
in
$S_1$
, then
$v^2=0$
also and we are done. Suppose henceforth that
$z^2$
is not zero in
$S_1$
. By Lemma 4.3,
$$ \begin{align*} z=(a^{-1}b)^\gamma\quad\text{or}\quad z=(ab^{-1})^\gamma \end{align*} $$
for some nonzero integer
$\gamma $
. Consider first that
$z=(a^{-1}b)^\gamma $
. If
$\gamma $
is positive, then, by (6-4),
$$ \begin{align*} t=(a^{-1}b)^\mu a(b^{-1}a)^\beta b^{-\varepsilon} \end{align*} $$
for some
$\mu \ge 0$
, so that
$v^2$
is divided by
$$ \begin{align*} t^{-1}zt=b^{\varepsilon}(a^{-1}b)^\beta a^{-1}(a^{-1}b)^{-\mu}(a^{-1}b)^\gamma(a^{-1}b)^\mu a(b^{-1}a)^\beta b^{-\varepsilon}, \end{align*} $$
which, in turn, is divided by
$$ \begin{align*} a^{-1}(a^{-1}b)^\gamma=a^{-2}b(a^{-1}b)^{\gamma-1}, \end{align*} $$
which is zero in
$S_1$
. If
$\gamma $
is negative, then
$z=(b^{-1}a)^{-\gamma }$
and, by (6-4),
$$ \begin{align*} s=a^{-\delta}(ba^{-1})^\alpha ba(b^{-1}a)^\mu \end{align*} $$
for some
$\mu \ge 0$
, so that
$v^2$
is divided by
$$ \begin{align*} szs^{-1}=a^{-\delta}(ba^{-1})^\alpha ba(b^{-1}a)^\mu (b^{-1}a)^{-\gamma}(b^{-1}a)^{-\mu} a^{-1}b^{-1}(ab^{-1})^\alpha a^\delta, \end{align*} $$
which, in turn, is divided by
$$ \begin{align*} (b^{-1}a)^{-\gamma}a^{-1}b^{-1}=(b^{-1}a)^{-\gamma-1}b^{-1}aa^{-1}b^{-1}, \end{align*} $$
which, in turn, is divided by
$b^{-2}$
, which is zero in
$S_1$
. Suppose now that
$z=(ab^{-1})^\gamma $
. Interchanging a and b, and reversing the order of multiplication, identical calculations show that
$v^2$
is divided by a word that evaluates to zero in
$S_1$
. In all cases,
$v^2=0$
in
$S_1$
, completing the proof of the lemma.
We can now use these lemmas and results from Section 4 to prove that
$S_1$
in its entirety satisfies Adjan’s identity (1-2).
Theorem 6.6. The inverse semigroup with zero
$$ \begin{align*} S_1=\langle a, b\mid a^2=b^2=ab=0\rangle \end{align*} $$
satisfies Adjan’s identity:
$$ \begin{align} xy^2xxyxy^2x=xy^2xyxxy^2x. \end{align} $$
Proof. Let
$u, v\in S_1$
. If
$u^2$
,
$v^2$
,
$uv$
,
$vu$
or
$vuv$
evaluate to zero in
$S_1$
, or if
$u^2=u$
in
$S_1$
, then (6-5) holds trivially when u and v are substituted for x and y, respectively. Henceforth, we may suppose that
$u^2$
,
$v^2$
,
$uv$
,
$vu$
and
$vuv$
are nonzero in
$S_1$
and u is not idempotent. Therefore,
$\overline {u}$
is a nonempty reduced word such that, also,
$\overline {u}^2$
and
$v\overline {u}v$
are nonzero in
$S_1$
. By Lemma 6.5,
$ba$
does not divide u, so that
$u\in I_1$
or
$u\in I_2$
, by part (ii) of Lemma 4.4. If v is idempotent, then
$ba$
does not divide v, by Lemma 6.4, since
$v\overline {u}v$
is nonzero in
$S_1$
. If v is not idempotent, then
$ba$
does not divide v, by Lemma 6.5, since
$v^2$
is nonzero in
$S_1$
. In both cases,
$v\in I_1$
or
$v\in I_2$
by part (ii) of Lemma 4.4. By part (iii) of Lemma 4.4, since neither
$uv$
nor
$vu$
are zero in
$S_1$
, either
$u,v\in I_1$
or
$u,v\in I_2$
. However,
$I_1$
and
$I_2$
satisfy Adjan’s identity (1-2), by Remark 4.5, so that (6-5) holds when u and v are substituted for x and y, respectively. This completes the proof of the theorem.
In the main result of this section, we give equivalent conditions for inverse semigroups from
${\frak P}$
to satisfy some nontrivial semigroup identity.
Theorem 6.7. Consider an inverse semigroup with zero
$$ \begin{align*}S=\langle \,A\mid c_i=0\ \text{for}\ i \in I\, \rangle\end{align*} $$
from the class
${\frak P}$
. Then, the following conditions are equivalent:
-
(a) S satisfies a nontrivial semigroup identity;
-
(b) S satisfies Adjan’s identity for the bicyclic monoid;
-
(c) S does not contain a nonmonogenic free subsemigroup;
-
(d) S is finitely presented and has polynomial growth;
-
(e) S is trivial, a monogenic inverse semigroup with zero or isomorphic to
$$ \begin{align*} S_1=\langle a,b\mid a^2=b^2=ab=0\rangle\quad\text{or}\quad S_2=\langle a,b\mid a^2=b^2=ab=ba=0\rangle. \end{align*} $$
Proof. If S is trivial or a monogenic inverse semigroup with zero, then S is a homomorphic image of the free monogenic inverse semigroup, which satisfies Adjan’s identity (6-5). If
$S=S_2$
, then S is a homomorphic image of
$S_1$
. By Theorem 6.6,
$S_1$
satisfies (6-5). Thus, in all cases, if S is trivial, a monogenic inverse semigroup with zero, or isomorphic to
$S_1$
or
$S_2$
, then S satisfies (6-5). Thus, condition (e) implies condition (b). Clearly, condition (b) implies condition (a), and condition (a) implies condition (c).
We now prove that condition (c) implies condition (e). Suppose that S does not contain a nonmonogenic free subsemigroup, and that S is not trivial and not a monogenic inverse semigroup with zero. We show that S is isomorphic to
$S_1$
or
$S_2$
. In particular,
$|A|\ge 2$
. If
$c_i\in A$
for some
$i\in I$
, then we may remove
$c_i$
from A and all relators containing
$c_i$
, without changing S up to isomorphism. Hence, there is no loss of generality in assuming that
$c_i\not \in A$
for all
$i\in I$
. Certainly, S does not contain a nonmonogenic free inverse subsemigroup, so, by Theorem 5.2,
$|A|\le 2$
, whence
$|A|=2$
. We may suppose that
$A=\{a,b\}$
.
Let U be the subsemigroup of
$FI_A$
generated by
$u_1=a^2b^{-1}$
and
$u_2=ab^{-1}$
. Because
$u_1$
and
$u_2$
do not commute in the free group over A, they freely generate a free subsemigroup of
$FI_A$
. Hence, some element of U must be zero in S. At the same time, all iterated products involving
$u_1$
and
$u_2$
are reduced words over B, whose Munn trees are chains. By inspection of these trees, we conclude that the only positive words dividing elements of U in
$FI_A$
are a, b and
$a^2$
. Since a and b are not relators, we conclude that
$a^2$
must be a relator. By a similar argument,
$b^2$
must also be a relator.
Let V be the subsemigroup of
$FI_A$
generated by
$v_1=ab^{-1}aba^{-1}b$
and
$v_2=ab^{-1}$
. As above,
$v_1$
and
$v_2$
freely generate a free subsemigroup of
$FI_A$
, so some element of V must be zero in S. Similarly, all iterated products involving
$v_1$
and
$v_2$
are reduced words, whose Munn trees are chains. By inspection of these trees, we conclude that
$ab$
or
$ba$
must be a relator. In either case, S must be a homomorphic image of
$S_1$
. Also, for any positive word over A that is not a of b, its subwords of length two form a subset of
$\{a^2, b^2, ab, ba\}$
. Hence, all homomorphic images of
$S_1$
defined by positive presentations are isomorphic to
$S_1$
or
$S_2$
. This completes the proof that condition (c) implies condition (e).
If condition (e) holds, then clearly S is finitely presented, and, in each case, S has polynomial growth, in particular, because
$S_1$
has polynomial growth, by [Reference Easdown and Shneerson11, Example 2.3], so that condition (d) holds. That condition (d) implies condition (c) follows from [Reference Shneerson and Easdown33, Theorem 1], and the proof of the theorem is complete.
7 Identities in signature with involution and exponential growth
In this final section, we provide a sequence of lemmas and propositions leading to two main theorems. Theorem 7.3 exhibits a nontrivial identity in signature with involution for the inverse semigroup
$S_4$
. (A nontrivial identity in signature with involution for the inverse semigroup
$S_3$
had already been found in [Reference Easdown and Shneerson10], documented above in Theorem 2.1.) Propositions 7.4 and 7.8 give complete syntactic descriptions of proper homomorphic images of
$S_3$
and
$S_4$
, respectively. The final result, Theorem 7.10 below, gives characterisations of inverse semigroups from
${\frak P}$
that satisfy a nontrivial identity in signature with involution but satisfy no nontrivial semigroup identity.
The next two lemmas refer to the inverse semigroup with zero
$$ \begin{align*} S_4=\langle a, b\mid a^2=b^2=0\rangle, \end{align*} $$
and are used to find a nontrivial identity in signature with involution satisfied by
$S_4$
(see Theorem 7.3 below). Put
$A=\{a,b\}$
and
$B=A\cup A^{-1}$
. Because of the relations
$a^2=b^2=0$
, nonempty reduced words w over
$A\cup A^{-1}$
that are nonzero in
$S_4$
must have the form
$$ \begin{align} w=a^{\varepsilon_1}b^{\delta_1}a^{\varepsilon_2}b^{\delta_2}\cdots a^{\varepsilon_k}b^{\delta_k} \end{align} $$
for some positive integer k and integers
$\varepsilon _1, \delta _1,\ldots , \varepsilon _k, \delta _k$
, which are all
$\pm 1$
, except for
$\varepsilon _1$
and
$\delta _k$
, which may be
$0$
or
$\pm 1$
.
Lemma 7.1. Let
$w\in S_4$
be a nonempty reduced word over B that is nonzero in
$S_4$
. Then, each of the following conditions implies that
$w^2=0$
in
$S_4$
:
-
(a)
$w=c$
or
$cw'c$
for some letter
$c\in B$
and reduced word
$w'$
(possibly empty) over B; -
(b) w is reduced but not cyclically reduced;
-
(c) w has odd length.
Proof. Sufficiency of condition (a) is clear because
$a^2=b^2=0$
in
$S_4$
. Suppose that w is a reduced but not cyclically reduced word that is nonzero in
$S_4$
and let
$\widehat {w}$
denote its reduced part. By (7-1), the length of w must be odd, which implies also that the length of
$\widehat {w}$
is odd. By the form of (7-1) applied to
$\widehat {w}$
, it follows that
$\widehat {w}$
starts and finishes with the same letter, so that
$(\widehat {w})^2=0$
in
$S_4$
, by the sufficiency of condition (a). Since
$(\widehat {w})^2$
divides
$w^2$
in
$FI_A$
, it follows that
$w^2=0$
in
$S_4$
. This proves sufficiency of condition (b) and simultaneously sufficiency of condition (c).
Lemma 7.2. Let u and v be nonempty reduced words over B such that u, v and
$uv$
are nonzero in
$S_4$
. Suppose that the word
$uv$
is not reduced. Then, either
$v^{-1}$
is a suffix for u or
$u^{-1}$
is a prefix for v. In particular, if u and v have the same length, then
$u = v^{-1}$
.
Proof. We have that
$u=z_1t$
and
$v=t^{-1}z_2$
for some reduced words
$z_1$
,
$z_2$
, t, where t is nonempty and
$z_1z_2$
is reduced. The lemma is proved by showing that either
$z_1$
or
$z_2$
is empty. Suppose to the contrary that both
$z_1$
and
$z_2$
are nonempty. Applying the form (7-1) to each of u and v, using the fact that t is nonempty, we deduce that the terminal letter of
$z_1$
coincides with the initial letter of
$z_2$
. Then,
$a^2$
or
$b^2$
divides
$z_1z_2$
, which in turn divides
$uv$
in
$FI_A$
. However, then
$uv=0$
in
$S_4$
, which contradicts our hypothesis. Hence, at least one of the words
$z_1$
,
$z_2$
must be empty, and the lemma is proved.
We can now prove the following theorem, which becomes one of the main steps in finding a complete description (Theorem 7.10 below) of semigroups from
${\frak P}$
that satisfy a nontrivial identity in signature with involution, but which do not have polynomial growth.
Theorem 7.3. The inverse semigroup with zero given by the presentation
$$ \begin{align*} S_4=\langle a, b\mid a^2=b^2=0\rangle \end{align*} $$
satisfies the following identity in signature with involution:
$$ \begin{align*} x\,[x,y]^2\,y^{-1}=x\,[x,y]\,y^{-1}, \end{align*} $$
or equivalently,
$$ \begin{align} x^2yx^{-1}y^{-1}xyx^{-1}y^{-2}=x^2yx^{-1}y^{-2}. \end{align} $$
Proof. Consider any
$x,y\in S_4$
. We may suppose that all of
$x^2$
,
$y^2$
,
$xy$
and
$x^{-1}y^{-1}$
are nonzero in
$S_4$
, for otherwise, (7-2) holds trivially. By Lemma 7.1, both
$\overline {x}$
and
$\overline {y}$
have even length greater than or equal to two, and, by (7-1), consecutive letters in each word alternate between the alphabets
$\{a^{\pm 1}\}$
and
$\{b^{\pm 1}\}$
. Put
$$ \begin{align*} u=\overline{xy}=\overline{\overline{x}\,\overline{y}}\quad\mathrm{and}\quad v=\overline{x^{-1}y^{-1}}=\overline{\overline{x^{-1}}\,\overline{y^{-1}}}. \end{align*} $$
Because of the alternation of the alphabets and even lengths, either
$\overline {x}\,\overline {y}$
is reduced, in which case
$\overline {y}\,\overline {x}$
is also reduced and
$$ \begin{align*} \ell(u)=\ell(\overline{x})+\ell(\overline{y})=\ell(v), \end{align*} $$
or
$\overline {x}\,\overline {y}$
is not reduced, in which case
$\overline {y}\,\overline {x}$
is also not reduced and, by Lemma 7.2,
$$ \begin{align*} \ell(u)=|\ell(\overline{x})-\ell(\overline{y})|=\ell(v). \end{align*} $$
In either case,
$\ell (u)=\ell (v)$
. If
$\overline {xyx^{-1}y^{-1}}$
is zero in S, then (7-2) holds trivially. Hence, we may suppose that
$$ \begin{align*} \overline{uv}=\overline{xyx^{-1}y^{-1}} \end{align*} $$
is nonzero in
$S_4$
. However, then
$uv$
is nonzero and not reduced, so that
$u=v^{-1}$
, by Lemma 7.2. Hence,
$$ \begin{align*} \overline{[x,y]}=\overline{xyx^{-1}y^{-1}}=\overline{uv}=1 \end{align*} $$
in the free group. This shows that
$[x,y]$
is idempotent in
$S_4$
, and (7-2) holds, completing the proof of the theorem.
We now develop some notation and apparatus that enables us to describe, in a compact way (see Proposition 7.4 below), all homomorphic images of the semigroup
$S_3$
. Let n be a positive integer and suppose that
$$ \begin{align*} \mathbf{x}=(x_1,x_2,\ldots, x_n)\quad\mathrm{and}\quad \mathbf{y}=(y_1,y_2,\ldots, y_n) \end{align*} $$
are finite sequences of nonnegative integers such that
$\mathbf {x}$
is decreasing,
$\mathbf {y}$
is increasing and at least one entry is nonzero. Define
$$ \begin{align} S_{\mathbf{x},\mathbf{y}}=\langle a,b\mid ab=b^{x_1}a^{y_1}=\cdots=b^{x_n}a^{y_n}=0\rangle, \end{align} $$
which is a member of our class
${\frak P}$
and a homomorphic image of the inverse semigroup
$\langle a, b\mid ab=0\rangle $
. For example, if
$\mathbf {x}=(4,3,2,1,0)$
and
$\mathbf {y}=(0,1,2,3,4)$
, then
$$ \begin{align*} S_{\mathbf{x},\mathbf{y}}=\langle a,b\mid ab=b^4=b^3a=b^2a^2=ba^3=a^4=0\rangle. \end{align*} $$
The notion of irredundancy of an arbitrary inverse semigroup presentation of the form (2-1) is given in [Reference Shneerson and Easdown35, Section 2], and, in our context (as defined above in §2), a presentation is irredundant if none of the generators are relators and no relator is a factor of any of the others. Observe, by inspection (see (7-4), (7-5) and (7-6) below), that the presentation (7-3) violates irredundancy if and only if a or b is a relator, which occurs if and only if
$x_1=1$
and
$y_1=0$
, or
$x_n=0$
and
$y_n=1$
, that is,
$$ \begin{align*} (\mathbf{x},\mathbf{y}) \in \{ ((1),(0) ), ((0),(1) ), ((k,0), (0,1) ), ((1,0),(0,k) ) \mid k\ge 1 \}. \end{align*} $$
In particular, the presentation (7-3) is irredundant if
$n\ge 3$
. To decongest the notation slightly, in the case where
$n=1$
, we can write
$$ \begin{align*} S_{i.j}=S_{(i),(\kern1.4pt j)}. \end{align*} $$
Note that
$S_{0,0}$
is not defined and
$$ \begin{align*} S_{1,1}=\langle a,b\mid ab=ba=0\rangle. \end{align*} $$
Observe that
$S_{1,1}$
is a homomorphic image of
$S_{\mathbf {x},\mathbf {y}}$
for any positive integer n if and only if
$\mathbf {x}$
and
$\mathbf {y}$
are sequences of positive integers. Further,
$S_{1,1}$
has exponential growth, by [Reference Easdown and Shneerson11, Theorem 5.2], and is a terminal object in the subclass of
${\frak P}$
consisting of semigroups where none of the generators are nilpotent, in the sense that
$S_{1,1}$
is unchanged upon adding further positive relators that avoid
$a^2$
and
$b^2$
. Observe further that, in general, if
$\overline {\mathbf {s}}$
is the sequence obtained by reversing a finite sequence
$\mathbf {s}$
, then
$$ \begin{align*} S_{\overline{\mathbf{y}},\overline{\mathbf{x}}}\cong S_{\mathbf{x},\mathbf{y}}, \end{align*} $$
under the isomorphism induced by mapping a to
$b^{-1}$
and b to
$a^{-1}$
.
Most of the time, the finitely presented inverse semigroup
$S_{\mathbf {x},\mathbf {y}}$
has exponential growth (see Lemma 7.4 below), but there are some exceptions:
$$ \begin{align} S_{1,0}=\langle a,b\mid ab=b=0\rangle=\langle a\rangle\cup\{0\}\cong S_{0,1} \end{align} $$
is free monogenic with zero,
$$ \begin{align} S_{(1,0),(0,1)}=\langle a, b\mid ab=b=a=0\rangle=\{0\} \end{align} $$
is trivial,
$$ \begin{align} S_{(1,0),(0,k)}=\langle a,b\mid ab=b=a^k=0\rangle=\langle a\mid a^k=0\rangle\cong S_{(k,0),(0,1)} \end{align} $$
is monogenic with zero, for any integer
$k\ge 2$
,
$$ \begin{align} S_{(2,0),(0,2)}=\langle a,b\mid ab=b^2=a^2=0\rangle \end{align} $$
has polynomial growth (see [Reference Easdown and Shneerson11, Example 2.3]), and
$$ \begin{align} S_{(2,1,0),(0,1,2)}=\langle a,b\mid ab=b^2=ba=a^2=0\rangle \end{align} $$
also has polynomial growth, being a homomorphic image of
$S_{(2,0),(0,2)}$
. By contrast,
$$ \begin{align} S_{(3,0),(0,2)}=\langle a,b\mid ab=b^3=a^2=0\rangle\cong S_{(2,0),(0,3)} \end{align} $$
and
$$ \begin{align} S_{(1,0),(1,2)}=\langle a,b\mid ab=ba=a^2=0\rangle\cong S_{(2,1),(0,1)} \end{align} $$
have exponential growth, by [Reference Easdown and Shneerson11, Theorem 6.1]. Consider, also,
$$ \begin{align} S_{(3,1,0),(0,1,2)}=\langle a,b\mid ab=b^3=ba=a^2=0\rangle\cong S_{(2,1,0),(0,1,3)} \end{align} $$
and
$$ \begin{align} S_{(3,2,1,0),(0,1,2,3)}=\langle a,b\mid ab=b^3=b^2a=ba^2=a^3=0\rangle. \end{align} $$
Both of these have exponential growth. One can see this, for example, by observing that the subsemigroup T of
$FI_{\{a,b\}}$
generated by
$a^{-1}b$
and
$a^{-1}b^2$
is free (see [Reference Easdown and Shneerson11, Lemma 3.1]), no element of which is divided by any of the relators in (7-11) or (7-12), so that T embeds in both semigroups. Put
$$ \begin{align} \begin{aligned} {\mathcal L}&=\{((0),(0)),((1),(0)),((0),(1)),((k,0),(0,1)),((1,0),(0,k)),\\ &\quad((2,0),(0,2)),((2,1,0),(0,1,2))\mid k\ge 1\}. \end{aligned} \end{align} $$
Now, we can fully describe elements of
${\frak P}$
that are homomorphic images of
${\langle a, b\mid ab=0\rangle} $
and identify those that have exponential growth.
Proposition 7.4. Let S be a semigroup from the class
${\frak P}$
given by an inverse semigroup presentation
$$ \begin{align*} \langle a,b\mid c_i=0\ \text{for}\ i\in I\rangle \end{align*} $$
such that
$ab$
is zero in S. Then, S is finitely presented in the class of inverse semigroups and is isomorphic to one of the following finitely presented Rees quotients of free inverse semigroups over the alphabet
$\{a,b\}$
:
$$ \begin{align*} S_3=\langle a,b\mid ab=0\rangle\quad\text{or}\quad S_{\mathbf{x},\mathbf{y}}\ \text{given by (7-3)} \end{align*} $$
for some finite decreasing sequence
$\mathbf {x}$
and some increasing sequence
$\mathbf {y }$
of nonnegative integers of the same length such that at least one entry is nonzero. Further, S has exponential growth if and only if S is isomorphic to
$S_3$
or
$S_{\mathbf {x},\mathbf {y}}$
for some
$(\mathbf {x},\mathbf {y})\not \in {\mathcal L}$
, where
${\mathcal L}$
is given by (7-13).
Remark 7.5. It should be noted, for a general reason, that the semigroup over the alphabet
$A=\{a,b\}$
given by positive relators, one of which is
$ab$
, must be finitely presented. Here, the language of all words over A that avoid
$ab$
is
$b^*a^*$
, and every ascending chain of ideals in the free semigroup
$A^+$
, starting from the principal ideal generated by
$ab$
, stabilises in a finite number of steps (see König’s lemma, [Reference Rozenberg and Salomaa30, Corollary 2.4]). Our goal here, however, is to give a syntactic description of all possible ascending chains, distinguishing the cases of polynomial and exponential growth that arise when we consider inverse semigroup presentations.
Proof Proof of Proposition 7.4.
The first part of this proof is direct and elementary, and may be regarded as a proof of the two-dimensional case of the well-known Dickson lemma [Reference Dickson9] (see Remark 7.6 below). An alternative proof, using Higman’s lemma [Reference Higman16], is also given below in Remark 7.7. Suppose that S is a proper homomorphic image of
$S_3$
, so must contain at least one positive word w that avoids
$ab$
as a subword and evaluates to zero. We may choose w to be of the form
$$ \begin{align*} w=b^{x_1}a^{y_1}=0 \end{align*} $$
for some nonnegative integers
$x_1$
and
$y_1$
such that
$x_1+y_1>0$
and
$y_1$
is as small as possible. However, then, having fixed
$y_1$
, we may suppose that
$x_1$
is as small as possible (since any word with larger exponent of b would evaluate to zero as a consequence). Hence, S is a homomorphic image of
$$ \begin{align*} S_{x_1,y_1}=\langle a,b\mid ab=b^{x_1}a^{y_1}=0\rangle. \end{align*} $$
If the image is not proper, then
$S=S_{\mathbf {x},\mathbf {y}}$
, where
$\mathbf {x}=(x_1)$
and
$\mathbf {y}=(y_1)$
so that S is given by (7-3), in an instance where
$n=1$
. Note that at least one of
$x_1$
or
$y_1$
is positive.
Suppose then that S is a proper image of
$S_{x_1,y_1}$
, so S must contain at least one positive word w that evaluates to zero and avoids
$ab$
and
$b^{x_1}a^{y_1}$
, so that
$$ \begin{align*} w'=b^{x_2}a^{y_2}=0 \end{align*} $$
for some nonnegative integers
$x_2$
and
$y_2$
such that
$x_2+y_2>0$
and
$y_2$
is as small as possible. Then, having fixed
$y_2$
, we may suppose that
$x_2$
is as small as possible. By minimality of
$y_1$
, however,
$y_2\ge y_1$
. Since
$b^{x_1}a^{y_1}$
does not divide
$w'$
, we have that
${x_2< x_1}$
. If
$y_2=y_1$
, then we have a contradiction, by the minimality of
$x_1$
. Hence,
$y_2>y_1$
and S is a homomorphic image of
$S_{\mathbf {x},\mathbf {y}}$
, where
$\mathbf {x}=(x_1,x_2)$
and
$\mathbf {y}=(y_1,y_2)$
. If the image is not proper, then
$S=S_{\mathbf {x},\mathbf {y}}$
is given by (7-3), in an instance where
$n=2$
.
We may suppose then that S is a proper homomorphic image of this
$S_{\mathbf {x},\mathbf {y}}$
, and we move to the next step in an inductive process.
Suppose, more generally, that
$n\ge 2$
and S is a proper homomorphic image of
$S_{\mathbf {x},\mathbf {y}}$
for some decreasing sequence
$\mathbf { x}=(x_1,\ldots , x_n)$
and increasing sequence
$\mathbf {y}=(y_1,\ldots , y_n)$
of nonnegative integers. In particular,
$x_1$
and
$y_n$
are positive. We may assume, as part of this inductive hypothesis, that, for
$2\le i\le n$
, we have chosen
$y_i$
to be the smallest nonnegative integer such that
$b^{x_i}a^{y_i}$
evaluates to zero in S, for some
$x_i<x_{i-1}$
, and that for this
$y_i$
, we have chosen
$x_i$
as small as possible. Because S is a proper homomorphic image, S must contain at least one positive word
$w"$
that evaluates to zero but avoids each of
$ab$
,
$b^{x_1}a^{y_1}, \ldots , b^{x_n}a^{y_n}$
, so that
$$ \begin{align*} w"=b^{x_{n+1}}a^{y_{n+1}}=0 \end{align*} $$
for some nonnegative integers
$x_{n+1}$
and
$y_{n+1}$
such that
$x_{n+1}+y_{n+1}>0$
and
$y_{n+1}$
is as small as possible. Then, having fixed
$y_{n+1}$
, we may suppose that
$x_{n+1}$
is as small as possible. Since
$b^{x_n}a^{y_n}$
does not divide
$w"$
, we have that either
$x_{n+1}< x_n$
or
$y_{n+1}< y_n$
. Suppose that
$x_{n+1}\ge x_n$
, so
$y_{n+1}<y_n$
. By minimality of
$y_1$
, however,
$y_{n+1}\ge y_1$
. Hence, there is a least integer i such that
$2\le i\le n$
and
$$ \begin{align*} y_{i-1}\le y_{n+1}<y_i. \end{align*} $$
If, also,
$x_{i-1}\le x_{n+1}$
, then the word
$b^{x_{i-1}}a^{y_{i-1}}$
divides
$w"$
, which is a contradiction. Hence,
$x_{n+1}<x_{i-1}$
. However, this now contradicts the conditions for the minimality of
$y_i$
(as part of the inductive hypothesis). This proves that
$x_{n+1}<x_n$
. If
$y_{n+1} \le y_n$
, then we contradict either the minimality of
$y_n$
(if
$y_{n+1}<y_n$
) or the minimality of
$x_n$
(if
$y_{n+1}=y_n$
). Hence,
$y_{n+1}> y_n$
. Now, put
$$ \begin{align*} \mathbf{x}'=(x_1,\ldots, x_n,x_{n+1})\quad\mathrm{and}\quad \mathbf{y}'=(y_1,\ldots, y_n, y_{n+1}). \end{align*} $$
We have that S is a homomorphic image of
$S_{\mathbf {x}',\mathbf {y}'}$
, establishing the inductive step.
This inductive process however must terminate after a finite number of steps because the first sequence is decreasing with nonnegative entries. This shows that S is finitely presented and S is given by (7-3) for some positive integer n, some decreasing sequence
$\mathbf {x}$
and some increasing sequence
$\mathbf {y}$
, such that at least one of the entries is positive.
Suppose that S is isomorphic to
$S_3$
or to
$S_{\mathbf {x},\mathbf {y}}$
for
$(\mathbf {x},\mathbf {y})\not \in {\mathcal L}$
. As noted in observations preceding this proposition, all of these are defined by irredundant presentations, in the sense of [Reference Shneerson and Easdown35, Section 2]. Observe that
$S_3$
is defined by one relator and
$S_{\mathbf {x},\mathbf {y}}$
is defined by two relators if
$\mathbf {x}$
and
$\mathbf {y}$
are sequences of length
$1$
, so have exponential growth, by [Reference Easdown and Shneerson11, Theorem 5.2]. If
$\mathbf {x}$
and
$\mathbf {y}$
are sequences of length
$2$
, then, because
$(\mathbf {x},\mathbf {y})\not \in {\mathcal L}$
, it follows that
$S_{\mathbf {x},\mathbf {y}}$
has
$S_{(3,0),(0,2)}$
or
$S_{(2,1),(0,1)}$
as a homomorphic image, so has exponential growth (explained above following (7-9) and (7-10)). If
$\mathbf {x}$
and
$\mathbf {y}$
are sequences of length
$3$
, then, because
$(\mathbf {x},\mathbf {y})\not \in {\mathcal L}$
, it follows that
$S_{\mathbf {x},\mathbf {y}}$
has
$S_{(3,1,0),(0,1,2)}$
as a homomorphic image, so has exponential growth (explained above following (7-11)). Suppose finally that
$\mathbf {x}$
and
$\mathbf {y}$
are sequences of length
$n\ge 4$
. Then,
$S_{\mathbf {x},\mathbf {y}}$
has
$S_{(3,2,1,0),(0,1,2,3)}$
as a homomorphic image, so has exponential growth (explained above following (7-12)). In all cases, S has exponential growth.
Finally, by observations above relating to (7-4), (7-5), (7-6), (7-7) and (7-8), if
$(\mathbf { x},\mathbf {y})\in {\mathcal L}$
, then
$S_{\mathbf {x},\mathbf {y}}$
has polynomial growth. This completes the proof of the proposition.
Remark 7.6. The proof of the first part of Proposition 7.4 regarding the finiteness of the presentation of S follows quickly from a classical lemma of Dickson [Reference Dickson9], which says that the partially ordered set
$( {\mathbb N}^m, \le )$
has no infinite antichains. Indeed, let
$$ \begin{align} S=\langle a,b\mid ab=0,b^{x_i}a^{y_i}=0 \ (i=1, 2, \ldots)\rangle \end{align} $$
be any positive presentation of S. Then, the relation
$b^{x_j}a^{y_j}=0$
can be deduced from the relation
$b^{x_i}a^{y_i}=0$
if and only if
$(x_i, y_i)\le (x_j,y_j)$
in
$({\mathbb N}^2,\le )$
. Thus, the relation
$b^{x_j}a^{y_j}$
occurs in an irredundant presentation of S if and only if
$(x_i, y_i)$
is a minimal element, with respect to the partial order, of the subset of ordered pairs
$(x,y)$
such that
$b^xa^y=0$
in S. By Dickson’s lemma, we immediately deduce that the irredundant presentation of S equivalent to (7-14) must be finite. The first part of the proof of Proposition 7.4, in fact, becomes a proof of Dickson’s lemma for
$m=2$
.
Remark 7.7. An alternative proof of the first part of Proposition 7.4 is related to a result of Higman [Reference Higman16]. Consider the free monoid
$A^*$
with respect to a finite nonempty set A. For
$u,v\in A^*$
, say that u embeds in v, and write
$u\le _e v$
if u can be obtained from v by cancelling some letters. Then,
$u\le _e v$
means that if
$u=u_1u_2\cdots u_n$
has a letter by letter factorisation over A, then
$$ \begin{align*} v=v_1u_1v_2u_2\cdots v_nu_nv_{n+1} \end{align*} $$
holds in
$A^*$
for some words
$v_1, \ldots , v_{n+1}$
. In modern parlance, u is called a scattered subword of v. If
$(E,\le )$
is a partially ordered set and
$X\subseteq E$
, then the set
$$ \begin{align*} \overline{X}=\{y\in E\mid (\text{there exists } x\in X)\ x\le y\} \end{align*} $$
is called the closure of X (or ideal generated by X). It is easy to see that
$(A^*,\le _e)$
is a partially ordered set that does not have infinite descending chains. This is called the division ordering on
$A^*$
. One of the corollaries of Higman’s theorem [Reference Higman16], proved for abstract algebras and applied to division orderings, is that for any infinite sequence of words
$\{u_n\}_{n=1}^\infty $
over a finite alphabet A, one can find two indices i and j such that
$i<j$
and
$u_i\le _e u_j$
. A short proof of this result, which we refer to as Higman’s lemma, was found by Conway [Reference Conway5, pages 52–53] (and see [Reference Lothaire22] also for more details and comments). In particular, Higman’s lemma shows that for any nonempty subset H of
$A^*$
, the partially ordered set
$(H,\le _e)$
has a finite number of minimal elements and every ideal is finitely generated. Denote the set of all minimal elements of
$(H,\le _e)$
by
$\mathrm {\min }(H)$
. Thus,
$\mathrm {\min }(H)$
is a finite nonempty set whose closure is H. We apply these observations in the context of the presentation (7-14) of S, using
$A=\{a,b\}$
and
$$ \begin{align*} H=\{b^\alpha a^\beta\mid b^\alpha a^\beta=0\text{ in } S\}. \end{align*} $$
A relation
$U\equiv (b^{x_j}a^{y_j}=0)$
can be deduced from a relation
$V\equiv ( b^{x_i}a^{y_i}=0)$
, in the class of all semigroups with zero (as well as in the class of all inverse semigroups with zero), if and only if
$x_i\le x_j$
and
$y_i\le y_j$
, in which case V can be obtained from U by deleting
$x_j-x_i$
occurrences of the letter b and
$y_j-y_i$
occurrences of the letter a, that is,
$b^{x_i}a^{y_i}\le _e b^{x_j}a^{y_j}$
. This means that
$\overline {H}=\overline {\mathrm {\min }\,H}=H$
and relators in the irredundant presentation of S equivalent to (7-14) are precisely elements of the set
$\mathrm {\min }(H)\cup \{ab\}$
. Now, suppose that the irredundant presentation of S consists of n relators, so that we may suppose
$$ \begin{align} S=\langle a,b\mid ab=0, b^{x_i}a^{y_i}=0 \ (i=1, 2, \ldots, n)\rangle, \end{align} $$
where all relators are pairwise incomparable in
$(A^*,\le _e)$
. Then,
$i\not = j$
implies that
$x_i\not =x_j$
and
$y_i\not =y_j$
. Also,
$x_i>x_j$
implies
$y_i< y_j$
. Without loss of generality, then, we may suppose in (7-15) that
$x_1>x_2>\cdots >x_n$
and
$y_n<y_{n-1}<\cdots <y_1$
, so that the finite sequence
$\mathbf {x}=(x_1, \ldots , x_n)$
is decreasing whilst the sequence
$\mathbf {y}=(y_1,\ldots , y_n)$
is increasing, and we have recovered the presentation (7-3), completing this alternative proof of the first part of Proposition 7.4.
The next proposition gives a complete description of proper homomorphic images of the inverse semigroup
$S_4$
. It is notable that cascades of examples occur (semigroups
$S_6(i)$
and
$S_8(i)$
for
$i \ge 1$
, in the statement of the proposition below), where relators occur with equations resembling Coxeter relations.
Proposition 7.8. Let S be a semigroup from the class
${\frak P}$
that is a proper homomorphic image of the inverse semigroup
$$ \begin{align*}S_4=\langle a,b\mid a^2=b^2=0\rangle.\end{align*} $$
Then, S is finitely presented and either trivial, monogenic with zero, or isomorphic to
$$ \begin{align*} S_5(i)=\langle a, b\mid a^2=b^2=(ab)^i=0\rangle, \end{align*} $$
$$ \begin{align*} S_6(i)=\langle a, b\mid a^2=b^2=(ab)^i=(ba)^i=0\rangle, \end{align*} $$
$$ \begin{align*} S_7(i)=\langle a, b\mid a^2=b^2=(ab)^ia=0\rangle\quad \text{or} \end{align*} $$
$$ \begin{align*} S_8(i)=\langle a, b\mid a^2=b^2=(ab)^ia=(ba)^ib=0\rangle \end{align*} $$
for some integer
$i\ge 1$
. Then, S has exponential growth in all cases, except when S is trivial or monogenic with zero, or when S is isomorphic to
$S_5(1)$
or
$S_6(1)$
, in which case S has polynomial growth.
Proof. First, note that there must be some positive word w over the alphabet
$\{a,b\}$
that is zero in S but is not divisible by
$a^2$
or
$b^2$
. We may assume that w is as short as possible. If
$w=a$
or
$w=b$
, then S must be trivial or monogenic with zero.
Suppose that w is not equal to a or b. Then, w must be one of
$$ \begin{align*} (ab)^i,(ba)^i,(ab)^ia,(ba)^ia \end{align*} $$
for some positive integer i. Suppose first that
$w=(ab)^i$
. Then, S is a homomorphic image of
$S_5(i)$
. If this image is proper, then there must be another positive word
$w'$
that evaluates to zero in S, has length at least
$2i$
, but is not divisible by
$a^2$
,
$b^2$
or
$(ab)^i$
. The only such word is
$$ \begin{align*} w'=(ba)^i \end{align*} $$
so that S is a homomorphic image of
$S_6(i)$
. However, all words of length greater than
$2i$
that are not divisible by
$a^2$
or
$b^2$
are divisible by w or
$w'$
, so that S must be isomorphic to
$S_6(i)$
.
If
$w=(ba)^i$
, then, interchanging the roles of a and b, we again conclude that S is isomorphic to
$S_5(i)$
or
$S_6(i)$
.
By a similar argument, if
$w=(ab)^ia$
or
$w=(ba)^ib$
, then S is isomorphic to
$S_7(i)$
or
$S_8(i)$
.
Observe that
$S_5(1)$
has polynomial growth, by [Reference Easdown and Shneerson11, Theorem 6.1], Hence,
$S_6(1)$
, being a homomorphic image, also has polynomial growth.
Note that
$$ \begin{align*}S_8(1)=\langle a,b\mid a^2=b^2=aba=bab=0\rangle\end{align*} $$
is a homomorphic image of
$S_5(i)$
,
$S_6(i)$
,
$S_7(\kern1.4pt j)$
and
$S_8(\kern1.4pt j)$
for all
$i\ge 2$
and
$j\ge 1$
. However, it is easy to see that the words
$ba^{-1}$
and
$b^{-1}aba^{-1}$
generate a free subsemigroup of
$FI_{\{a,b\}}$
, no element of which is divisible by
$a^2$
,
$b^2$
,
$aba$
or
$bab$
, so that
$S_8(1)$
contains a nonmonogenic free subsemigroup. Hence,
$S_8(1)$
has exponential growth. Hence,
$S_5(i)$
,
$S_6(i)$
,
$S_7(\kern1.4pt j)$
and
$S_8(\kern1.4pt j)$
have exponential growth for all
$i\ge 2$
and
$j\ge 1$
, completing the proof of the proposition.
The following lemma is our second application of Proposition 3.2, and is used in Theorem 7.10 below to severely limit the possibilities of inverse semigroups with zero from
${\frak P}$
that can satisfy a nontrivial identity in signature with involution.
Lemma 7.9. Let A be an alphabet containing two distinct letters a and b, and let T be the inverse subsemigroup of
$FI_A$
generated by
$$ \begin{align*} u=ab^{-1}a^2b^{-1}a\quad\text{and}\quad v=ba^{-1}ba^{-1}.\end{align*} $$
Then:
-
(a) T is freely generated by u and v;
-
(b) the only positive reduced words over A that divide elements of T in
$FI_A$
are a, b,
$a^2$
,
$ab$
and
$ba$
.
Proof. Consider the alphabet
$Y=\{u,v\}$
. Observe, by inspection, that
$$ \begin{align*} m_u=M_v=m_{v^{-1}}=M_{v^{-1}}=3 \end{align*} $$
and
$$ \begin{align*} M_u=m_v=m_{u^{-1}}=M_{v^{-1}}=0, \end{align*} $$
whilst
$$ \begin{align*} \ell(u)=\ell(u^{-1})=6\qquad \ell(v)=\ell(v^{-1})=4, \end{align*} $$
from which it is immediate that the set Y satisfies condition (3-1). Then, by Proposition 3.2, condition (a) of the lemma holds. By inspection of word trees of elements of T, condition (b) holds, completing the proof of the lemma.
In the final result, we give a complete description of inverse semigroups from
${\frak P}$
that satisfy some nontrivial identity in signature with involution, but which do not satisfy a semigroup identity. Such semigroups are all finitely presented and have exponential growth. The descriptions rely crucially on the inverse semigroup
$S_3$
, which has a central role in the results of [Reference Easdown and Shneerson10] and whose homomorphic images are listed in Proposition 7.4, and on the inverse semigroup
$S_4$
, whose homomorphic images are listed in Proposition 7.8. Some details regarding both
$S_3$
and
$S_4$
, including the graphs associated with their presentations, are given above in Example 4.1.
Theorem 7.10. Consider an inverse semigroup with zero
$$ \begin{align*}S=\langle \,A\mid c_i=0\ \text{for}\ i \in I\, \rangle\end{align*} $$
from the class
${\frak P}$
. Suppose that S does not satisfy a nontrivial semigroup identity. Then, the following conditions are equivalent:
-
(a) S satisfies a nontrivial identity in signature with involution;
-
(b) S does not contain a nonmonogenic free inverse subsemigroup;
-
(c) S is finitely presented and is isomorphic to
$$ \begin{align*} S_3=\langle a,b\mid ab=0\rangle, \end{align*} $$
for some integer
$$ \begin{align*} S_{\mathbf{x},\mathbf{y}}=\langle a,b\mid ab=b^{x_1}a^{y_1}=\cdots = b^{x_n}a^{y_n}=0\rangle \end{align*} $$
$n\ge 1$
, some finite decreasing sequence
$\mathbf {x}$
and some increasing sequence
$\mathbf {y}$
of nonnegative integers of the same length, such that
$(\mathbf {x},\mathbf {y})$
is not in the list
${\mathcal L}$
of exceptions (7-13), or S is isomorphic to
$$ \begin{align*} S_4=\langle a,b\mid a^2=b^2=0\rangle, \end{align*} $$
$$ \begin{align*} S_5(i)=\langle a,b\mid a^2=b^2=(ab)^i=0\rangle\quad\textit{or} \end{align*} $$
for some integer
$$ \begin{align*} S_6(i)=\langle a,b\mid a^2=b^2=(ab)^i=(ba)^i=0\rangle \end{align*} $$
$i\ge 2$
, or
$$ \begin{align*} S_7(\kern1.4pt j)=\langle a,b\mid a^2=b^2=(ab)^ja=0\rangle\quad\textit{or} \end{align*} $$
for some integer
$$ \begin{align*} S_8(\kern1.4pt j)=\langle a,b\mid a^2=b^2=(ab)^ja=(ba)^jb=0\rangle \end{align*} $$
$j\ge 1$
.
If S satisfies any (and hence all) of these conditions, then S is finitely presented and has exponential growth.
Proof. We show that condition (c) implies condition (a). If S is isomorphic to
$S_3$
or
$S_4$
, then S satisfies a nontrivial identity in signature with involution, by Theorems 2.1 and 7.3, respectively. Observe that each
$S_{\mathbf {x},\mathbf {y}}$
is a homomorphic image of
$S_3$
, and each
$S_5(i)$
,
$S_6(i)$
,
$S_7(\kern1.4pt j)$
and
$S_8(\kern1.4pt j)$
is a homomorphic image of
$S_4$
. Hence, if S is isomorphic to any of the semigroups listed in condition (c), then S satisfies a nontrivial identity in signature with involution. Thus, condition (c) implies condition (a). Clearly, condition (a) implies condition (b).
It remains to prove that condition (b) implies condition (c). Suppose that S does not contain any nonmonogenic free inverse subsemigroup. Certainly,
$|A|\ge 2$
. As before, there is no loss of generality in assuming that no relator belongs to the alphabet A. By Theorem 5.2,
$|A|=2$
, so that we may assume
$A=\{a,b\}$
.
Let T be the inverse subsemigroup of
$FI_A$
generated by
$ab^{-1}a^2b^{-1}a$
and
$ba^{-1}ba^{-1}$
. By Lemma 7.9, T is a free nonmonogenic subsemigroup, and only a, b,
$a^2$
,
$ab$
and
$ba$
can be words over the positive alphabet A that are divisors of elements of T in
$FI_A$
. Hence, some element of T must be zero in S. Since a and b are not relators, we conclude that
$a^2$
,
$ab$
or
$ba$
must be a relator.
If
$a^2$
is not a relator, then
$ab$
or
$ba$
is a relator, so that S is a homomorphic image of
$S_3$
. In this case, by Proposition 7.4, S is isomorphic to
$S_3$
or
$S_{\mathbf {x},\mathbf {y}}$
for some
$\mathbf {x}$
and
$\mathbf {y}$
such that
$(\mathbf {x},\mathbf {y})\not \in {\mathcal L}$
.
By symmetry, the same conclusion follows if
$b^2$
is not a relator.
The remaining case is that
$a^2$
and
$b^2$
are both relators, and then S must be a homomorphic image of
$S_4$
, so that, by Proposition 7.8, S is isomorphic to
$S_4$
,
$S_5(i)$
,
$S_6(i)$
,
$S_7(\kern1.4pt j)$
or
$S_8(\kern1.4pt j)$
for some
$i\ge 2$
or
$j\ge 1$
. This completes the proof that condition (b) implies condition (c).
If S satisfies any (and hence all) of these conditions, then, in particular, S is finitely presented and, by hypothesis, does not satisfy a nontrivial semigroup identity, so that S cannot have polynomial growth, by Theorem 6.7, whence S has exponential growth, by [Reference Shneerson and Easdown33, Corollary 1]. This completes the proof of the theorem.
Acknowledgement
The authors are very grateful to the School of Mathematics and Statistics at the University of Sydney where the second author was a visiting researcher in June 2022.
