2 Preliminaries

For an alphabet A, we will denote the free monoid over A by $A^\ast $ . It consists of all words over A, including the empty word $\epsilon =\epsilon _A$ . Since throughout words will play a somewhat ambivalent role of elements in a free monoid, as well as those in a monoid defined by a presentation, we will denote equality of words in $A^\ast $ by $u\equiv v$ .

A monoid presentation is a pair ${\operatorname {Mon}\bigl \langle {A}\:|\:{R} \bigr \rangle }$ , where A is an alphabet and $R\subseteq A^\ast \times A^\ast $ is a set of pairs of words. This presentation defines the monoid $A^\ast /\rho $ , where $\rho $ is the congruence on $A^\ast $ generated by R. We will write $M={\operatorname {Mon}\bigl \langle {A}\:|\:{R} \bigr \rangle }$ . A typical relation $(u,v)\in R$ is usually written $u=v$ , and we extend this to pairs in $\rho $ . Thus, in the context of the monoid defined by a presentation, $u=v$ means that u and v, interpreted as products of generators, represent the same element of M. The monoid M is a natural homomorphic image of the free monoid $A^\ast $ via the mapping $w\mapsto w/\rho $ , called the natural homomorphism. The group of units $U(M)$ of a monoid M consists of all elements $x\in M$ which are (two-sided) invertible, that is for which there exists $y\in M$ , such that $xy=yx=1_M$ . A presentation ${\operatorname {Mon}\bigl \langle {A}\:|\:{R} \bigr \rangle }$ is called special if every defining relation has the form $u=1$ . The word u in such a relation is often called a relator. A one-relator monoid is a monoid defined by a single relator, that is $M={\operatorname {Mon}\bigl \langle {A}\:|\:{u=1} \bigr \rangle }$ .

For an alphabet A, let $A^{-1}=\{ a^{-1}\::\: a\in A\}$ be another alphabet disjoint from A and in 1-1 correspondence with A. Further, let $\overline {A}=A\cup A^{-1}$ , and extend the bijection $a\mapsto a^{-1}$ first to $\overline {A}$ by $(a^{-1})^{-1}\equiv a$ , and then entire $\overline {A}^\ast $ by $(a_1^{\epsilon _1}a_2^{\epsilon _2}\dots a_n^{\epsilon _n})^{-1} =a_n^{-\epsilon _1}\dots a_2^{-\epsilon _2}a_1^{-\epsilon _1}$ for $a_i\in A$ , $\epsilon _i=\pm 1$ . The free group $F_A$ over A consists of all reduced words from $\overline {A}^\ast $ , that is words containing no subword of the form $aa^{-1}$ with $a\in \overline {A}$ , under multiplication $u\cdot v=\operatorname {\mathrm {red}}(uv)$ . Here, $\operatorname {\mathrm {red}}(u)$ denotes the free reduction of u, that is the result of successively deleting all pairs $aa^{-1}$ in u. It is well known that the order of performing these deletions is inconsequential. Sometimes we will write $\operatorname {\mathrm {red}}_A$ for $\operatorname {\mathrm {red}}$ when we want to work with free reductions over different alphabets. We will also extend the use of $\operatorname {\mathrm {red}}$ to apply to sets of words: $\operatorname {\mathrm {red}}(W)=\{ \operatorname {\mathrm {red}}(w)\::\: w\in W\}$ .

A group presentation is a pair ${\operatorname {Gp}\bigl \langle {A}\:|\:{R} \bigr \rangle }$ , where A is an alphabet and $R\subseteq \overline {A}^\ast \times \{1\}$ . The group defined by presentation is $G={\operatorname {Gp}\bigl \langle {A}\:|\:{R} \bigr \rangle }={\operatorname {Mon}\bigl \langle {\overline {A}}\:|\:{R,\ aa^{-1}=a^{-1}a=1\ (a\in A)} \bigr \rangle }$ . Alternatively, G can be viewed as the quotient $F_A/N$ , where N is the normal subgroup of $F_A$ generated by all u, where $(u,1)\in R$ . Again, G is a homomorphic image of $F_A$ via the natural homomorphism $w\mapsto wN$ .

The free inverse monoid over a set A will be denoted by $FI_A$ . It can be viewed as the monoid

$$\begin{align*}{\operatorname{Mon}\bigl\langle {\overline{A}}\:|\:{uu^{-1}u=u,\ uu^{-1}vv^{-1}=vv^{-1}uu^{-1}\ (u,v\in\overline{A}^\ast)} \bigr\rangle}. \end{align*}$$

An inverse monoid presentation is a pair ${\operatorname {Inv}\bigl \langle {A}\:|\:{R} \bigr \rangle }$ , where $R\subseteq \overline {A}^\ast \times \overline {A}^\ast $ . It defines the quotient $FI_A/\rho $ , where $\rho $ is the congruence generated by R, which is once again a natural homomorphic image of $FI_A$ via $w\mapsto w/\rho $ . If all the relations in R are of the form $u=1$ , we say that ${\operatorname {Inv}\bigl \langle {A}\:|\:{R} \bigr \rangle }$ is a special inverse monoid. A special inverse monoid ${\operatorname {Inv}\bigl \langle {A}\:|\:{u=1} \bigr \rangle }$ with a single relator is called a one-relator inverse monoid.

Every inverse monoid has a (unique) maximal group homomorphic image. For the free inverse monoid $FI_A$ , this is the free group $F_A$ , while for a monoid ${\operatorname {Inv}\bigl \langle {A}\:|\:{R} \bigr \rangle }$ , it is the group ${\operatorname {Gp}\bigl \langle {A}\:|\:{R} \bigr \rangle }$ defined by the same presentation.

For a monoid (respectively, inverse monoid or group) M and a subset $X\subseteq M$ , we will denote the submonoid (respectively, inverse submonoid, subgroup) that X generates by ${\operatorname {Mon}\bigl \langle {X} \bigr \rangle }$ (respectively, ${\operatorname {Inv}\bigl \langle {X} \bigr \rangle }$ , ${\operatorname {Gp}\bigl \langle {X} \bigr \rangle }$ ).

For a word $w \in A^{*}$ , we use $\operatorname {\mathrm {pref}}(w)$ to denote the set of all prefixes of w, and $\operatorname {\mathrm {suff}}(w)$ to denote the set of suffixes.

Let $X = \{x_1, x_2, \ldots , x_n\}$ be an alphabet. We often use the notation $w(x_1, \ldots , x_n)$ to denote a word from $\overline {X}^{*}$ where we want to stress the fact that each letter of this word belongs to X or to $X^{-1}$ . Given such a word $w(x_1, \ldots , x_n)$ and given a sequence of words $p_1, \ldots , p_n$ from $\overline {Y}^{*}$ , we use $w(p_1, \ldots , p_n)$ to denote the word from $\overline {Y}^{*}$ obtained by replacing each letter $x_i^\epsilon $ ( $\epsilon =\pm 1$ ) in the word $w(x_1, \ldots , x_n)$ by the word $p_i^\epsilon $ .

The following concept is of pivotal importance for the material in this paper:

Definition 2.1. Let M be the inverse monoid defined by the presentation

$$\begin{align*}{\operatorname{Inv}\bigl\langle {A}\:|\:{r_i = 1\ (i \in I)} \bigr\rangle}. \end{align*}$$

A set of invertible pieces (or often we just say a set of pieces) for this presentation is a collection of words $p_1, \ldots , p_k \in \overline {A}^{*}$ which are invertible in M and satisfy ${r_i \in {\operatorname {Mon}\bigl \langle {p_1, \ldots , p_k} \bigr \rangle } \leq \overline {A}^{*}}$ for all $i \in \{1,2,\ldots , n\}$ . A factorisation of the relators $r_i$ with respect to the pieces $p_1, \ldots , p_k$ is a collection of words $r_i^{\prime }$ $(i = 1, \ldots , n)$ over k letters, such that

$$\begin{align*}r_i \equiv r_i^{\prime}(p_1, \ldots, p_k) \ (i = 1, \ldots, n). \end{align*}$$

For $i \in I$ by the decomposition into minimal invertible pieces, we mean the unique factorisation

$$\begin{align*}r_{i}\equiv r_{i 1}r_{i 2}\ldots r_{i k_i} \end{align*}$$

with the property that each $r_{i j}$ is a nonempty word in $\overline {A}^{*}$ which represents an invertible element of M and which has no proper nonempty invertible prefixes.

The following facts about cancellation in an inverse semigroup will also be used throughout the paper. They are well known and easy to prove (see [Reference Gray6, Lemma 3.1, Corollary 3.2]):

3 Makanin-style presentation theorems for special inverse monoids

As discussed in the Introduction, given a special inverse monoid $M\kern1.2pt{=}\kern1.2pt{\operatorname {Inv}\bigl \langle {A}\:|\:{r_i\kern1.2pt{=}\kern1.2pt1\kern1pt (i\kern1.2pt{\in}\kern1.2pt I)} \bigr \rangle }$ , and decomposition of each $r_i$ into invertible minimal pieces, one may ask whether turning distinct pieces into distinct letters yields a presentation for the group of units of M, as it does in the monoid case. It is easy to see that this is not true in general. Consider for instance, the one-relator inverse monoid

$$\begin{align*}M={\operatorname{Inv}\bigl\langle {a,b,c}\:|\:{abc^2b^{-1}abc^3b^{-1}abc^2b^{-1}a=1} \bigr\rangle}. \end{align*}$$

We claim that the minimal invertible pieces are a, $bc^2b^{-1}$ , $bc^{3}b^{-1}$ .

To see that these three words are invertible in M, we can argue as follows. First, note that since a is both a prefix and suffix of the defining relator, it follows that a is both left and right invertible, and hence is invertible. Multiplying the defining relator on the left and right by the inverse of a then implies that $bc^2b^{-1}abc^3b^{-1}abc^2b^{-1}$ is invertible. Since this invertible word has $bc^2b^{-1}$ both as a prefix and as a suffix, it follows that $bc^2b^{-1}$ is invertible. Finally, multiplying on the left and right by the inverse of $bc^2b^{-1}$ and then the inverse of a, we deduce that $bc^3b^{-1}$ is invertible. A more general form of reasoning like this to obtain invertible pieces, called the Adjan overlap algorithm, will be discussed in Section 4. On the other hand, M is not a group, and b is not invertible, because of the homomorphism $M\rightarrow B$ onto the bicyclic monoid $B = {\operatorname {Inv}\bigl \langle {b}\:|\:{bb^{-1}=1} \bigr \rangle }$ given by $a,c\mapsto 1$ , $b\mapsto b$ . Since b is not invertible but $bc^2b^{-1}$ is, it follows that $bc$ is not invertible. Similarly, $bc^2$ and $bc^3$ are not invertible. Therefore, a, $bc^2b^{-1}$ , $bc^{3}b^{-1}$ are indeed the minimal invertible pieces, as claimed.

Replacing these pieces by letters $x,y,z$ , respectively, yields the presentation

$$\begin{align*}G={\operatorname{Gp}\bigl\langle {x,y,z}\:|\:{xyxzxyx=1} \bigr\rangle} \cong F_{x,y}. \end{align*}$$

In the monoid M, we have

$$\begin{align*}bcb^{-1}=(bc^3b^{-1})(bc^2b^{-1})^{-1}, \end{align*}$$

so the elements a and $t=bcb^{-1}$ form a generating set for the group of units $U=U(M)$ of M. These generators satisfy the relation $xt^2xt^3xt^2x=1$ . Since U is not free with respect to $\{x,t\}$ and G is free of rank $2$ , it follows that $U\not \cong G$ . In fact, U is defined by the presentation ${\operatorname {Gp}\bigl \langle {x,t}\:|\:{xt^2xt^3xt^2x=1} \bigr \rangle }$ . This will follow from the more general results we will prove below (see Corollary 3.13). A key feature of this example is that $\{a,bc^2b^{-1},bc^3b^{-1}\}$ is not a basis for ${\operatorname {Gp}\bigl \langle {a,bc^2b^{-1},bc^3b^{-1}} \bigr \rangle }\leq F_{a,b,c}$ . We now prove a result that gives an approach to studying groups of units of special inverse monoids which deals with this obstacle.

Theorem 3.1. Let $M= {\operatorname {Inv}\bigl \langle {A}\:|\:{r_i=1 \; (i \in I)} \bigr \rangle }$ be a special inverse monoid, let ${r_{i}\equiv r_{i 1}r_{i 2}\ldots r_{i k_i} }$ be a factorisation into invertible pieces for $i\in I$ , and let H be the subgroup of the free group $F_A$ generated by all the pieces $r_{ij} \; ( i\in I, 1\leq j\leq k_{i} ) $ . Fix an isomorphism $\phi :F_Y \rightarrow H$ , and set

$$\begin{align*}K = {\operatorname{Gp}\bigl\langle {Y}\:|\:{ \phi^{-1}(r_{i 1}) \phi^{-1}(r_{i 2}) \ldots \phi^{-1}(r_{i k_i}) = 1 \; (i \in I) } \bigr\rangle}. \end{align*}$$

If $\phi $ induces an embedding of the group $ K$ into the group ${\operatorname {Gp}\bigl \langle {A}\:|\:{r_i=1 \; (i \in I)} \bigr \rangle }$ defined by the same presentation as M, then $\phi $ induces an isomorphism between K and the subgroup of the monoid M generated by the pieces.

Proof. We begin working towards the diagram shown in Figure 1. Start from the free monoid $\overline {A}^\ast =(A\cup A^{-1})^\ast $ . The monoid $M={\operatorname {Inv}\bigl \langle {A}\:|\:{r_i=1 \; (i \in I)} \bigr \rangle }$ is a natural homomorphic image of it, and we denote by $\pi _M : \overline {A}^\ast \rightarrow M$ the natural epimorphism.

Figure 1 Monoids, groups and homomorphisms in the proof of Theorem 3.1. Throughout, indexing is understood as follows: $i\in I$ , $1\leq j\leq k_i$ , $l\in L$ .

Let $F_A$ denote the free group on A. Recall that we regard $F_A$ as consisting of freely reduced words over A, and so $F_A\subseteq \overline {A}^\ast $ . However, note that this inclusion is not a homomorphism. The group $F_A$ is a homomorphic image of $\overline {A}^\ast $ , via the free reduction homomorphism $\operatorname {\mathrm {red}}:\overline {A}^\ast \rightarrow F_A$ . The group $G={\operatorname {Gp}\bigl \langle {A}\:|\:{r_i=1 \; (i \in I)} \bigr \rangle }$ is a natural homomorphic image of $F_A$ via $\pi _G:F_A\rightarrow G$ . Since G is also an inverse monoid, and since M is defined by $r_i=1$ , $i\in I$ , it follows that there exists an epimorphism $\psi :M\rightarrow G$ , such that

(1) $$ \begin{align} \psi\pi_M=\pi_G\operatorname{\mathrm{red}}. \end{align} $$

Next, let

$$\begin{align*}H={\operatorname{Gp}\bigl\langle {\{ \operatorname{\mathrm{red}}(r_{ij}) \::\: i\in I,\ 1\leq j\leq k_i\} } \bigr\rangle}\leq F_A, \end{align*}$$

and let

$$\begin{align*}\widetilde{H}=\pi_G(H)\leq G. \end{align*}$$

As a subgroup of a free group, H itself must be free, that is $H\cong F_Y$ for some alphabet $Y=\{ y_l\::\: l\in L\}$ as in the statement, with an isomorphism

(2) $$ \begin{align} \phi:F_Y\rightarrow H,\ y_l\mapsto s_l\ (l\in L). \end{align} $$

Since $\operatorname {\mathrm {red}}(r_{ij})\in H$ , there exist $r_{ij}^\prime \in F_Y$ , such that

(3) $$ \begin{align} \phi (r_{ij}^\prime)\equiv\operatorname{\mathrm{red}}(r_{ij})\ (i\in I,\ 1\leq j\leq k_i). \end{align} $$

Let

(4) $$ \begin{align} r_i^\prime \equiv \operatorname{\mathrm{red}}_Y (r_{i1}^\prime r_{i2}^\prime\dots r_{ik_i}^\prime)\in F_Y\subseteq \overline{Y}^\ast, \end{align} $$

where $\operatorname {\mathrm {red}}_Y$ stands for the free reduction over the alphabet Y (and is not shown in the diagram). Let

(5) $$ \begin{align} K={\operatorname{Gp}\bigl\langle {Y}\:|\:{r_i^\prime =1\; (i\in I)} \bigr\rangle} ={\operatorname{Gp}\bigl\langle {Y}\:|\:{ \phi^{-1}(r_{i 1}) \phi^{-1}(r_{i 2}) \ldots \phi^{-1}(r_{i k_i}) = 1 \; (i \in I) } \bigr\rangle} , \end{align} $$

with the natural epimorphism $\pi _K : F_Y\rightarrow K$ .

Next, we claim that the generators $\{\pi _G(s_l)\::\: l\in L\}$ of $\widetilde {H}$ satisfy the relations $r_i^\prime =1$ , $i\in I$ . Indeed

$$ \begin{align*} \pi_G\phi (r_i^\prime) &= \pi_G\phi \operatorname{\mathrm{red}}_Y (r_{i1}^\prime\dots r_{ik_i}^\prime) && \text{(by (4))} \\ &=\pi_G( \phi (r_{1i}^\prime)\dots \phi (r_{ik_i}^\prime)) && (\phi \text{ is a homomorphism}) \\ &=\pi_G(\operatorname{\mathrm{red}}(r_{i1})\dots\operatorname{\mathrm{red}}(r_{ik_i})) && \text{(by (3))} \\ &=\pi_G\operatorname{\mathrm{red}}(r_{i1}\dots r_{ik_i}) && (\operatorname{\mathrm{red}} \text{ is a homomorphism}) \\ &=\pi_G\operatorname{\mathrm{red}}(r)=1 .&& \end{align*} $$

Therefore, there exists an epimorphism

(6) $$ \begin{align} \zeta:K\rightarrow \overline{H},\ \pi_K(y_l)\mapsto \pi_G(s_l)\ (l\in L). \end{align} $$

To complete the set-up, we turn our attention to the subgroup U of M generated by $\{ \pi _M(r_{ij})\::\: i\in I,\ 1\leq j\leq k_i\}$ .

We claim that

(7) $$ \begin{align} \pi_M(s_l)\in U \quad \text{for all } l\in L. \end{align} $$

Since $s_l\in H={\operatorname {Gp}\bigl \langle {\{ \operatorname {\mathrm {red}}(r_{ij})\: :\: i\in I,\ 1\leq i\leq k_i\} } \bigr \rangle }$ , it follows that

$$\begin{align*}s_l\equiv\operatorname{\mathrm{red}}(\operatorname{\mathrm{red}}(r_{i_1j_1})^{\epsilon_1}\dots \operatorname{\mathrm{red}}(r_{i_m j_m})^{\epsilon_m})\equiv \operatorname{\mathrm{red}}(r_{i_1 j_1}^{\epsilon_1}\dots r_{i_m j_m}^{\epsilon_m}). \end{align*}$$

But all $\pi _M(r_{ij})$ are invertible in M by assumption, and so

$$ \begin{align*} U&\ni \pi_M(r_{i_1 j_1})^{\epsilon_1}\dots \pi_M(r_{i_m j_m})^{\epsilon_m} &&\\ &=\pi_M (r_{i_1 j_1}^{\epsilon_1}\dots r_{i_m}^{\epsilon_m j_m} ) && (\pi_M \text{ is a homomorphism})\\ &=\pi_M(\operatorname{\mathrm{red}}(r_{i_1 j_1}^{\epsilon_1}\dots r_{i_m j_m}^{\epsilon_m})) && \text{(by Lemma 2.2(iii))}\\ &=\pi_M(s_l), \end{align*} $$

as required.

Next, we claim that U is actually generated by $\{ \pi _M(s_l)\::\: l\in L\}$ . This is proved by a very similar argument to the one in the previous paragraph, starting from the fact that $\{s_l\::\: l\in L\}$ is a generating set for H, expressing the generators $\operatorname {\mathrm {red}}(r_{ij})$ in terms of the $s_l$ , and using (7). Furthermore, the generators $\{ \pi _M(s_l)\::\: l\in L\}$ satisfy the relations $r_i^\prime =1$ . Indeed

$$ \begin{align*} \pi_M\phi(r_i^\prime) &= \pi_M\phi\operatorname{\mathrm{red}}_Y(r_{i1}^\prime\dots r_{ik_i}^\prime) && \text{(by (4))}\\ &= \pi_M(\phi(r_{i1}^\prime)\dots \phi(r_{ik_i}^\prime)) && (\phi \text{ is a homomorphism})\\ &=\pi_M(\operatorname{\mathrm{red}}(r_{i1})\dots \operatorname{\mathrm{red}}(r_{ik_i})) && \text{(by (3))} \\ &= \pi_M\operatorname{\mathrm{red}}(r_{i1})\dots \pi_M\operatorname{\mathrm{red}}(r_{ik_i}) && (\pi_M \text{ is a homomorphism})\\ &=\pi_M(r_{i1})\dots \pi_M(r_{ik_i}) && \text{(by Lemma 2.2(iii))} \\ &=\pi_M(r_{i1}\dots r_{ik_i}) && (\pi_M \text{ is a homomorphism}) \\ &=\pi_M(r)=1. \end{align*} $$

Therefore, there exists an epimorphism

(8) $$ \begin{align} \eta : K\rightarrow U,\ \pi_K(y_l)\mapsto \pi_M(s_l)\ (l\in L). \end{align} $$

With the foregoing set-up, the assertion of our theorem can be stated as follows:

If $\zeta $ is an isomorphism between K and $\widetilde {H}$ , then $\eta $ is an isomorphism between K and U.

This is now actually easy to prove: it is sufficient to show that $\eta $ and $\zeta ^{-1}\psi {\!\restriction }_U$ are mutually inverse homomorphisms. To do so, in turn, it is sufficient to verify that their two compositions act as the identity on the generating sets of U and K, respectively. Indeed, we have:

$$ \begin{align*} \eta\zeta^{-1}\psi{\!\restriction}_U\pi_M(s_l) &= \eta\zeta^{-1}\pi_G\operatorname{\mathrm{red}} (s_l) && \text{(by (1))}\\ &=\eta\zeta^{-1}\pi_G(s_l) && (s_l \text{ is reduced}) \\ &=\eta\pi_K(y_l) && \text{(by (6))} \\ &=\pi_M(s_l) && \text{(by (8))}, \end{align*} $$

and

$$ \begin{align*} \zeta^{-1}\psi{\!\restriction}_U\eta\pi_K(y_l) &= \zeta^{-1} \psi \pi_M(s_l) && \text{(by (8))} \\ &=\zeta^{-1}\pi_G\operatorname{\mathrm{red}}(s_l) && \text{(by (1))} \\ &=\zeta^{-1}\pi_G(s_l) && (s_l \text{ is reduced}) \\ &=\pi_K(y_l) && \text{(by (6))}, \end{align*} $$

completing the proof of the theorem.

It is reasonable to ask whether if one translates the presentation for K given in Theorem 3.1 back into the alphabet A, the resulting presentation defines M. The following theorem shows that this indeed is the case when the pieces are reduced words.

Theorem 3.2. Let $M= {\operatorname {Inv}\bigl \langle {A}\:|\:{r_i=1 \; (i \in I)} \bigr \rangle }$ be a special inverse monoid, let ${r_{i}\equiv r_{i 1}r_{i 2}\ldots r_{i k_i} }$ be a factorisation into invertible pieces for $i\in I$ and suppose that all pieces are reduced words. Let $\phi $ be an epimorphism from some free group $F_Y$ onto the subgroup of $F_A$ generated by the pieces, and for every piece $r_{ij}$ , pick a preimage $r_{ij}^\prime \in F_Y$ under $\phi $ . Finally, let $\pi :\overline {Y}^{*} \rightarrow \overline {A}^{*}$ be the homomorphism extending $x \mapsto \phi (x)$ $(x \in \overline {X})$ . Then

(9) $$ \begin{align} M={\operatorname{Inv}\bigl\langle {A}\:|\:{r_i=1\ (i \in I)} \bigr\rangle} ={\operatorname{Inv}\bigl\langle {A }\:|\:{\pi(r_{i 1}^\prime) \ldots \pi(r_{i k_i}^\prime)=1 \ (i \in I)} \bigr\rangle} \end{align} $$

and $\{ \pi (y): y \in \overline {Y} \}$ is a set of invertible pieces for ${\operatorname {Inv}\bigl \langle {A }\:|\:{\pi (r_{i 1}^\prime ) \ldots \pi (r_{i k_i}^\prime )=1 \; (i \in I)} \bigr \rangle }$ which generates the same subgroup of M as the original pieces $\{ r_{i j} \::\: i \in I,\ 1 \leq j \leq k_i\}$ .

Proof. Denoting by $\operatorname {\mathrm {red}}_A$ the free reduction over the alphabet A, we have

$$\begin{align*}\operatorname{\mathrm{red}}_A\pi(w)\equiv \phi(w) \quad \text{for all } w\in \overline{Y}^\ast, \end{align*}$$

and, in particular,

(10) $$ \begin{align} \operatorname{\mathrm{red}}_A\pi(r_{ij}^\prime)\equiv r_{ij} \quad (i\in I,\ 1\leq j\leq k_i) \end{align} $$

because all $r_{ij}$ are reduced.

Now, we show that all the relations $\pi (r_{i 1}^\prime ) \ldots \pi (r_{i k_i}^\prime )=1$ hold in the monoid M. Indeed, denoting by $\pi _M:\overline {A}^\ast \rightarrow M$ the natural epimorphism, we have

$$ \begin{align*} \pi_M(\pi(r_{i1}^\prime)\dots \pi(r_{ik_i}^\prime)) &= \pi_M(\operatorname{\mathrm{red}}_A\pi(r_{i1}^\prime)\dots \operatorname{\mathrm{red}}_A\pi(r_{ik_i}^\prime)) && \text{(by Lemma 2.2(iii))}\\ &=\pi_M(r_{i1}\dots r_{ik_i}) && \text{(by (10))}\\ &=\pi_M(r_i)=1_M.&& \end{align*} $$

Furthermore, these relations imply the original ones. To see this, let $M^\prime $ be the monoid defined by ${\operatorname {Inv}\bigl \langle {A }\:|\:{\pi (r_{i 1}^\prime ) \ldots \pi (r_{i k_i}^\prime )=1 \; (i \in I)} \bigr \rangle }$ , and let $\pi _{M^\prime }:\overline {A}^\ast \rightarrow M^\prime $ be the associated natural epimorphism, and then

$$ \begin{align*} 1_{M^\prime} &= \pi_{M^\prime} (\pi(r_{i1}^\prime)\dots\pi(r_{ik_i}^\prime)) &&\\ &=\pi_{M^\prime}(\operatorname{\mathrm{red}}_A\pi(r_{i1}^\prime)\dots\operatorname{\mathrm{red}}_A\pi(r_{ik_i}^\prime)) && \text{(by Lemma 2.2(iii))} \\ &=\pi_{M^\prime}(r_{i1}\dots r_{ik_i}) && \text{(by (10))} \\ &=\pi_{M^\prime}(r_i). && \end{align*} $$

This proves (9).

To prove that each $\pi (y)$ is invertible in M, note that by the assumptions of the theorem, $\phi (y)$ belongs to the subgroup of the free group $F_A$ generated by $\{ r_{ij}\::\: i\in I,\ 1\leq j\leq k_i\}$ , and that $\pi (y)\equiv \phi (y)$ . Hence, we can write

(11) $$ \begin{align} \pi(y)\equiv \operatorname{\mathrm{red}}_A(r_{i_1j_1}\dots r_{i_kj_k}). \end{align} $$

Since all $r_{ij}$ are units in M, by Lemma 2.2(iii), we have

(12) $$ \begin{align} \pi_M(r_{i_1j_1}\dots r_{i_kj_k})=\pi_M\operatorname{\mathrm{red}}_A(r_{i_1j_1}\dots r_{i_kj_k}). \end{align} $$

Combining (11) and (12), we obtain:

$$\begin{align*}\pi_M\pi(y) = \pi_M \operatorname{\mathrm{red}}_A(r_{i_1j_1}\dots r_{i_kj_k})=\pi_M(r_{i_1j_1}\dots r_{i_kj_k}) = \pi_M(r_{i_1j_1})\dots \pi_M(r_{i_kj_k}), \end{align*}$$

which is clearly a unit.

Finally, since each relator $\pi (r_{i 1}^\prime ) \ldots \pi (r_{i k_i}^\prime )$ is clearly a product of the $\pi (y)$ , it follows that $\{ \pi (y)\::\: y\in \overline {Y}\}$ is indeed a set of pieces for the presentation ${\operatorname {Inv}\bigl \langle {A }\:|\:{\pi (r_{i 1}^\prime ) \ldots \pi (r_{i k_i}^\prime )=1 \; (i \in I)} \bigr \rangle }$ .

We note that the assumption that the pieces are reduced is necessary in Theorem 3.2. Indeed, in the monoid ${\operatorname {Inv}\bigl \langle {x,y}\:|\:{xx^{-1}yy^{-1}xx^{-1}=1} \bigr \rangle }$ , the minimal invertible pieces are $xx^{-1}$ and $yy^{-1}$ . In $F_{x,y}$ , they generate the trivial subgroup. However, the original monoid is not isomorphic to the free inverse monoid ${\operatorname {Inv}\bigl \langle {x,y}\:|\: \bigr \rangle }$ .

Motivated by Theorem 3.1, we introduce the following concept:

Definition 3.6. A finite set of words $w_1, \ldots , w_k \in \overline {A}^{*}$ is free for substitution in a group presentation

$$\begin{align*}{\operatorname{Gp}\bigl\langle {x_1,\dots,x_k}\:|\:{r_i(x_1, \ldots, x_k) = 1\ (i\in I)} \bigr\rangle} \end{align*}$$

if the subgroup of

$$\begin{align*}{\operatorname{Gp}\bigl\langle {A}\:|\:{r_i(w_1, \ldots, w_k)=1\ (i\in I)} \bigr\rangle} \end{align*}$$

generated by $w_1, \ldots , w_k$ is isomorphic to ${\operatorname {Gp}\bigl \langle {x_1,\dots ,x_k}\:|\:{r_i(x_1, \ldots , x_k) = 1\ (i\in I)} \bigr \rangle }$ via the map $x_i \mapsto w_i$ .

Corollary 3.7. Let A be an alphabet, and suppose that $r_1,\dots , r_k\in \overline {A}^\ast $ are such that the free group $H={\operatorname {Gp}\bigl \langle {r_1,\dots ,r_k} \bigr \rangle }\leq F_A$ has a basis which is free for substitution into any one-relator presentation. Then the group U of units of any one-relator inverse monoid ${M={\operatorname {Inv}\bigl \langle {A}\:|\:{r=1} \bigr \rangle }}$ , where the minimal invertible pieces of r are precisely $ r_1,\dots , r_k$ , is again a one-relator group. Specifically, if $\{ p_1,\dots , p_n\}$ is a basis for H, if each $r_j$ is expressed in terms of this basis as $r_j=r_j^\prime (p_1,\dots ,p_n)$ , where $r_j^\prime \in \overline {\{x_1,\dots ,x_n\}}^\ast $ , and if $r=r^\prime (r_1,\dots , r_k)$ , then U is defined by

$$\begin{align*}U={\operatorname{Gp}\bigl\langle {x_1,\dots,x_n}\:|\:{r^\prime(r_1^\prime,\dots,r_k^\prime)=1} \bigr\rangle}. \end{align*}$$

It is therefore of interest to investigate sets that are free for substitutions into one-relator presentations, or indeed, into arbitrary presentations. For instance, we can prove the following:

Theorem 3.8. Let A be an alphabet, let $p_1, \ldots , p_n \in F_A$ and denote by $A_i$ the set of letters of A that occur in $p_i$ . If

$$\begin{align*}A_i \not\subseteq \bigcup_{j \neq i}{A_j} \quad \text{for all } i = 1, \ldots, n ,\end{align*}$$

then $\{p_1,\dots , p_n\}$ is free for substitutions into any one-relator presentation.

The following two lemmas will be used in the proof:

Proof. The subgroup of $G_1$ generated by $A\setminus \{ a_1,a_2\}$ is free on that set by Freiheitsatz [Reference Magnus, Karrass and Solitar19, Theorem 4.10], since the letter $a_1$ occurs in $r_1$ . Likewise, writing $G_2={\operatorname {Gp}\bigl \langle {A^\prime \setminus \{a_1^\prime \}}\:|\:{r_2^\prime =1} \bigr \rangle }$ over a disjoint copy of A, the subgroup generated by $A^\prime \setminus \{a_1^\prime ,a_2^\prime \}$ is free. So we can form the free product with amalgamation

$$\begin{align*}{\operatorname{Gp}\bigl\langle {(A\setminus\{ a_2\})\cup (A^\prime\setminus\{ a_1^\prime\})}\:|\:{ r_1=1,\ r_2^\prime=1,\ a=a^\prime\ (a\in A\setminus\{a_1,a_2\})} \bigr\rangle} \end{align*}$$

into which $G_1$ and $G_2$ will embed naturally. Now perform Tietze transformations [Reference Magnus, Karrass and Solitar19, Section 1.5] to remove the generators $a^\prime $ with $a\in A\setminus \{a_1,a_2\}$ , rename $a_2^\prime $ into $a_2$ and we obtain ${\operatorname {Gp}\bigl \langle {A}\:|\:{r_1=1,\ r_2=1} \bigr \rangle }=G$ .

Lemma 3.10. Let A and $X = \{ x_1, \ldots , x_n \}$ be two alphabets, and let $r = r(x_1, \ldots , x_n) \in F_X$ be a cyclically reduced word in which all of the letters $x_1, \ldots , x_n$ appear. Further, let $p_1, \ldots , p_n \in F_A$ , and denote by $A_i$ the set of letters of A that appear in $p_i$ . Suppose that

$$\begin{align*}A_i \not\subseteq \bigcup_{j \neq i}{A_j} \quad \text{for all } i = 1, \ldots, n, \end{align*}$$

with $a_i\in A_i \setminus \bigcup _{j \neq i}{A_j}$ . Then each of the letters $a_i$ $(i = 1, \ldots , n)$ appears in any cyclic reduction of the word $r(p_1, \ldots , p_n)$ .

Proof. Since r is cyclically reduced, and since we are concerned with cyclically reduced forms of $r(p_1,\dots ,p_n)$ , we may without loss of generality assume that r has the form

$$\begin{align*}r\equiv x_{i_1}^{\alpha_1} x_{i_2}^{\alpha_2}\dots x_{i_k}^{\alpha_k} ,\end{align*}$$

where $ i_j\in \{1,\dots ,n\}$ and $ \alpha _j\in \mathbb {Z}$ for $ j=1,\dots , k$ , and

$$\begin{align*}i_1\neq i_2\neq i_3\dots \neq i_k\neq i_1. \end{align*}$$

Consider the word

$$\begin{align*}r(p_1,\dots, p_n)\equiv p_{i_1}^{\alpha_1} p_{i_2}^{\alpha_2}\dots p_{i_k}^{\alpha_k}, \end{align*}$$

and inside it, for every $j=1,\dots , k$ , consider all the occurrences of the letter $a_{i_j}$ appearing in the reduced word $\operatorname {\mathrm {red}}(p_{i_j}^{\alpha _j})$ . Notice that there must be at least one such occurrence, since $p_{i_j}$ is reduced, and hence, the set of letters appearing in $p_{i_j}$ is the same as the set of letters appearing in $\operatorname {\mathrm {red}}(p_{i_j}^{\alpha _j})$ . We claim that none of these occurrences are cancelled in the process of free reduction of $r(p_1,\dots , p_n)$ .

To see this, suppose, to the contrary, that two occurrences of some $a_i$ cancel each other. Let those two occurrences appear in $p_{i_l}^{\alpha _l}$ and $p_{i_m}^{\alpha _m}$ , where $i=i_l=i_m$ and $l\leq m$ . Furthermore, choose i, l and m so that $m-l$ is as small as possible. By assumption, the occurrence of $a_i$ in $p_{i_l}$ is not cancelled when reducing to $\operatorname {\mathrm {red}}(p_{i_l}^{\alpha _l})$ , and hence, we cannot have $m=l$ . Also, since $i_{l+1}\neq i_l$ , the word $p_{i_{l+1}}$ contains no occurrences of $a_i=a_{i_l}$ , and so $m\neq l+1$ . Therefore, we must have $m\geq l+2$ . But now, in order for the two occurrences of $a_i$ in $p_{i_l}^{\alpha _l}$ and $p_{i_m}^{\alpha _m}$ to cancel each other, any occurrence of $a_{i_{l+1}}$ in $p_{i_{l+1}}^{\alpha _{l+1}}$ must also be cancelled. Since there are no occurrences of $a_{i_{l+1}}$ in $p_{i_l}^{\alpha _l}$ , it follows that these occurrences must cancel within $p_{i_{l+1}}^{\alpha _{l+1}}\dots p_{i_m}^{\alpha _m}$ , and this contradicts the minimality of $m-l$ . This proves the claim that no two occurrences of some $a_i$ within some $p_{i_l}^{\alpha _l}$ and $p_{i_m}^{\alpha _m}$ ( $i_l=i_m=i$ ) cancel each other in the process of free reduction of $r(p_1,\dots ,p_n)$ .

Now suppose that a cancellation of some $a_{i_l}$ appearing in some $p_{i_l}^{\alpha _l}$ can happen during the cyclic reduction of $r(p_1,\dots ,p_n)$ . Then this occurrence of $a_{i_l}$ would be cancelled during the free reduction of at least one of the words

$$\begin{align*}p_{i_l}^{\alpha_l} \dots p_{i_{k}}^{\alpha_{k}} p_{i_{1}}^{\alpha_{1}}\dots p_{i_{l-1}}^{\alpha_{l-1}} \quad\text{or}\quad p_{i_{l+1}}^{\alpha_{l+1}}\dots p_{i_{k}}^{\alpha_{k}} p_{i_{1}}^{\alpha_{1}}\dots p_{i_l}^{\alpha_l}. \end{align*}$$

However, the words

$$\begin{align*}x_{i_l}^{\alpha_l} \dots x_{i_{k}}^{\alpha_{k}} x_{i_{1}}^{\alpha_{1}}\dots x_{i_{l-1}}^{\alpha_{l-1}} \quad\text{and}\quad x_{i_{l+1}}^{\alpha_{l+1}}\dots x_{i_{k}}^{\alpha_{k}} x_{i_{1}}^{\alpha_{1}}\dots x_{i_l}^{\alpha_l} \end{align*}$$

satisfy the original assumptions made about r, and hence, such cancellation cannot take place by the argument from the previous paragraph. This completes the proof of the lemma.

Proof of Theorem 3.8

Let $X=\{ x_1,\dots , x_n\}$ . Suppose $p_1,\dots , p_n\in \overline {A}^\ast $ , and let $A_i$ be the set of letters appearing in $p_i$ . For every $i=1,\dots , n$ , pick $a_i\in A_i\setminus \bigcup _{j\neq i} A_j$ . We need to show that for every $r\in \overline {X}^\ast $ , the subgroup of

(13) $$ \begin{align} G={\operatorname{Gp}\bigl\langle {A}\:|\:{r(p_1,\dots, p_n)=1} \bigr\rangle} \end{align} $$

generated by $p_1,\dots , p_n$ is naturally isomorphic to ${\operatorname {Gp}\bigl \langle {X}\:|\:{r=1} \bigr \rangle }$ . Clearly, we may assume without loss of generality that r is cyclically reduced. We will prove the assertion by induction on the length of the word $r(p_1,\dots ,p_n)$ . If $|r(p_1,\dots ,p_n)|=0$ , Lemma 3.10 gives $|r|=0$ , and the assertion is obvious. It is also obvious when $|p_i|=1$ for all $i=1,\dots ,n$ . So, suppose that some $p_i$ has length greater than $1$ . Without loss, we may assume $|p_n|>1$ . In the presentation (13) for G, introduce a new generator $x_n$ satisfying $x_n=p_n$ , to obtain:

(14) $$ \begin{align} G&={\operatorname{Gp}\bigl\langle {A,x_n}\:|\:{p_nx_n^{-1}=1,\ r(p_1,\dots,p_{n-1},x_n)=1} \bigr\rangle} \end{align} $$

(15) $$ \begin{align} &={\operatorname{Gp}\bigl\langle {A,x_n}\:|\:{p_nx_n^{-1}=1,\ \overline{r}=1} \bigr\rangle} , \qquad\qquad\qquad\end{align} $$

where $\overline {r}$ denotes a cyclically reduced form of $r(p_1,\dots ,p_{n-1},x_n)$ . We claim that presentation (15) satisfies the assumptions of Lemma 3.9. Indeed:

• • The word $p_nx_n^{-1}$ is cyclically reduced because $p_n$ is a reduced word over $\overline {A}$ and $x_n\not \in \overline {A}$ .

• • The word $\overline {r}$ is cyclically reduced by assumption.

• • The letter $a_n$ appears in $p_n$ and in none of $p_1,\dots ,p_{n-1}$ ; hence, $a_n$ will appear in $p_nx_n^{-1}$ but not in $r(p_1,\dots ,p_{n-1},x_n)$ , and hence, not in $\overline {r}$ either.

• • The letter $a_1$ appears in $p_1$ , but not in any other $p_2,\dots ,p_n$ ; hence, it will appear in $r(p_1,\dots ,p_{n-1},x_n)$ by Lemma 3.10, but not in $p_nx_n^{-1}$ .

By Lemma 3.9, the group

(16) $$ \begin{align} {\operatorname{Gp}\bigl\langle {A\setminus\{a_n\},x_n}\:|\:{\overline{r}=1} \bigr\rangle}={\operatorname{Gp}\bigl\langle {A\setminus\{a_n\},x_n}\:|\:{ r(p_1,\dots,p_{n-1},x_n)} \bigr\rangle} \end{align} $$

embeds naturally into G, as defined by (15). Note that $|r(p_1,\dots ,p_{n-1},x_n)|<|r(p_1,\dots ,p_n)|$ because $|p_n|\geq 2$ . Furthermore, note that the words $p_1,\dots ,p_{n-1},x_n$ satisfy all the original assumptions about $p_1,\dots , p_n$ – they are reduced, and each contains a letter not appearing in any of the others. Therefore, the inductive hypothesis applies, and the subgroup of the group (16) generated by $p_1,\dots , p_{n-1},x_n$ is naturally isomorphic to ${\operatorname {Gp}\bigl \langle {X}\:|\:{r=1} \bigr \rangle }$ . But, inside G, this subgroup coincides with the subgroup generated by $p_1,\dots ,p_n$ , and the theorem is proved.

We can generalise the above condition a bit further:

Proof. We may reorder $p_1,\dots , p_n$ so that $p_1,\dots , p_m$ satisfy Condition (i) and $p_{m+1},\dots p_n$ satisfy Condition (ii) for some $1\leq m\leq n$ . For $i=1,\dots ,n$ , let $c_i=\mu (p_i)$ so that ${C=\{c_1,\dots ,c_n\}}$ , and let $x_1,\dots , x_n,d_{m+1},\dots , d_n$ be new letters, not in A.

We need to prove that for every word $r=r(x_1,\dots ,x_n)$ over $\overline {\{x_1,\dots ,x_n\}}$ , the subgroup of

(17) $$ \begin{align} {\operatorname{Gp}\bigl\langle {A}\:|\:{r(p_1,\dots,p_n)=1} \bigr\rangle} \end{align} $$

generated by $p_1,\dots ,p_n$ is naturally isomorphic to ${\operatorname {Gp}\bigl \langle {X}\:|\:{r=1} \bigr \rangle }$ , where $X = \{x_1, \ldots , x_n \}$ . To begin with, by Theorem 3.8, the subgroup of

$$\begin{align*}{\operatorname{Gp}\bigl\langle {B,c_1,\dots,c_m,d_{m+1},\dots, d_n}\:|\:{r(p_1,\dots,p_m,d_{m+1},\dots, d_n)=1} \bigr\rangle} \end{align*}$$

generated by $p_1,\dots ,p_m,d_{m+1},\dots , d_n$ is naturally isomorphic to ${\operatorname {Gp}\bigl \langle {X}\:|\:{r=1} \bigr \rangle }$ . We treat this as the inductive anchor for the claim that for every $k=0,\dots , n-m$ , the subgroup of

(18) $$ \begin{align} {\operatorname{Gp}\bigl\langle {B,c_1,\dots,c_{m+k},d_{m+k+1},\dots, d_n}\:|\:{ r(p_1,\dots, p_{m+k},d_{m+k+1},\dots, d_n)=1} \bigr\rangle} \end{align} $$

generated by $p_1,\dots ,p_{m+k},d_{m+k+1},\dots , d_n$ is naturally isomorphic to ${\operatorname {Gp}\bigl \langle {X}\:|\:{r=1} \bigr \rangle }$ . Suppose the claim is true for some k, and we prove it for $k+1$ . First, we write $p_{m+k+1}\equiv qc_{m+k+1}r$ , where $q,r\in \overline {B\cup \{c_1,\dots , c_{m+k}\}}^\ast $ , because of Condition (ii). Then, we introduce a new generator $c_{m+k+1}$ into (18), via the relation $c_{m+k+1}=q^{-1}d_{m+k+1} r^{-1}$ . Then, we use this relation to eliminate the generator $d_{m+k+1}$ via $d_{m+k+1}=qc_{m+k+1}r=p_{m+k+1}$ . Thus, we obtain the presentation

$$\begin{align*}{\operatorname{Gp}\bigl\langle {B,c_1,\dots,c_{m+k},c_{m+k+1},d_{m+k+2},\dots, d_n}\:|\:{ r(p_1,\dots, p_{m+k},p_{m+k+1},d_{m+k+2},\dots, d_n)=1} \bigr\rangle} \end{align*}$$

which defines a group naturally isomorphic to the group defined by (18). The subgroup of this group generated by $p_1,\dots ,p_{m+k+1},d_{m+k+2},\dots ,d_n$ is isomorphic to the subgroup of (18) generated by $p_1,\dots ,p_{m+k},d_{m+k+1},\dots ,d_n$ , which, in turn, is isomorphic to ${\operatorname {Gp}\bigl \langle {X}\:|\:{r=1} \bigr \rangle }$ by induction. This completes the inductive proof. Putting $k=n-m$ , we obtain that the subgroup of (17) generated by $p_1,\dots ,p_n$ is naturally isomorphic to ${\operatorname {Gp}\bigl \langle {X}\:|\:{r=1} \bigr \rangle }$ , and this completes the proof of the theorem.

Corollary 3.13. Let $M = {\operatorname {Inv}\bigl \langle {A}\:|\:{r=1} \bigr \rangle }$ , and let $r \equiv r_1 \ldots r_k$ be the factorisation of r into minimal invertible pieces. If there is a basis $p_1, \ldots , p_n$ of ${\operatorname {Gp}\bigl \langle {r_1, \ldots , r_k} \bigr \rangle }\leq F_A$ satisfying the condition in the statement of Theorem 3.11, then the group of units of M is a one-relator group. Specifically, expressing each $r_j=r_j^\prime (p_1,\dots , p_n)$ in $F_A$ , where $r_j^\prime \in \overline {\{x_1,\dots ,x_n\}}^\ast $ , the group of units of M is defined by

$$\begin{align*}{\operatorname{Gp}\bigl\langle {x_1,\dots,x_n}\:|\:{r_1^\prime \dots r_k^\prime=1} \bigr\rangle}. \end{align*}$$

As a special case of Theorem 3.11, we see that any sets $\{p_1,\dots ,p_n\}\subseteq F_A$ of the following types are free for substitutions into any one-relator presentations:

1. (F1) $p_i$ s are powers of distinct generators from A (this is Corollary 4.10.2 in [Reference Magnus, Karrass and Solitar19]);

2. (F2) $p_i$ s are words over disjoint subalphabets of A;

3. (F3) for each $p_i$ , there exists a letter $a_i\in A$ which appears in $p_i$ precisely once, and does not appear in any $p_j$ with $j<i$ .

We do not know whether the assumptions in Theorems 3.8 or 3.11 actually imply that the sets in question are free for substitutions in any presentations. However, this is the case for the above-listed special instances, as we shall see in the next theorem. At this point, it is very natural to wonder whether for a set of pieces to be free for substitutions, it might suffice just to assume that the set of words is Nielsen reduced (see [Reference Lyndon and Schupp18, page 6]). We will see later in Section 5.2 that the answer to this question is no (see Proposition 5.1).

Proof. (F1) is a special case of (F2), so there is no need to prove it separately. Suppose that (F2) is satisfied. We need to prove that for any group $G={\operatorname {Gp}\bigl \langle {X}\:|\:{r_i=1\ (i\in I)} \bigr \rangle }$ , with $X=\{x_1,\dots ,x_n\}$ , it naturally embeds into

(19) $$ \begin{align} {\operatorname{Gp}\bigl\langle {A}\:|\:{r_i(p_1,\dots,p_n)=1\ (i\in I)} \bigr\rangle}. \end{align} $$

To this end, for $k=1,\dots ,n$ , let $A_k\subseteq A$ be the set of letters that appear in $p_i$ , let ${A^\prime =A\setminus (A_1\cup \dots \cup A_n)}$ and let

$$\begin{align*}G_k={\operatorname{Gp}\bigl\langle {A_1,\dots,A_{k-1},A^\prime,x_k,\dots, x_n}\:|\:{ r_i( p_1,\dots,p_{k-1},x_k,\dots,x_n)=1\ (i\in I )} \bigr\rangle}. \end{align*}$$

We claim that for all $k=1,\dots ,n-1$ , the group $G_k$ embeds naturally into $G_{k+1}$ via

$$ \begin{align*} a &\mapsto a &\hspace{-50pt}& (a\in A_1\cup\dots\cup A_{k-1}\cup A^\prime),\\ x_k&\mapsto p_k, &\hspace{-63pt}&\\ x_j&\mapsto x_j &\hspace{-63pt}&(j=k+1,\dots,n). \end{align*} $$

Once the claim is proved, composing all these embeddings together with the obvious embedding of ${\operatorname {Gp}\bigl \langle {X}\:|\:{r_i=1\ (i\in I)} \bigr \rangle }$ into

$$\begin{align*}G_1={\operatorname{Gp}\bigl\langle {A^\prime,x_1,\dots,x_n}\:|\:{r_i(x_1,\dots,x_n)=1\ (i\in I)} \bigr\rangle} ={\operatorname{Gp}\bigl\langle {X}\:|\:{r_i=1\ (i\in I)} \bigr\rangle}\ast F_{A^\prime} \end{align*}$$

gives the desired embedding of ${\operatorname {Gp}\bigl \langle {X}\:|\:{r_i=1\ (i\in I)} \bigr \rangle }$ into (19).

To prove the claim, let m be the order of $x_k$ in $G_k$ if this is finite, and otherwise let $m=0$ . Note that by [Reference Magnus, Karrass and Solitar19, Corollary 4.4.11], the element $p_k$ in the group ${\operatorname {Gp}\bigl \langle {A_k}\:|\:{p_k^m=1} \bigr \rangle }$ has finite order if and only if $m>0$ , and that in this case, the order is precisely m. It follows that we can form the free product with amalgamation of the group $G_k$ with the group ${\operatorname {Gp}\bigl \langle {A_k}\:|\:{p_k^m=1} \bigr \rangle }$ , amalgamating the subgroup ${\operatorname {Gp}\bigl \langle {x_k} \bigr \rangle }$ of the former with ${\operatorname {Gp}\bigl \langle {p_k} \bigr \rangle }$ of the latter. This group naturally embeds $G_k$ and has the presentation

$$\begin{align*}{\operatorname{Gp}\bigl\langle {A_1,\dots,A_k,A^\prime,x_k,\dots,x_n}\:|\:{ r_i(p_1,\dots,p_{k-1},x_k,\dots,x_n)=1\ (i\in I),\ p_k^m=1,\ x_k=p_k} \bigr\rangle}. \end{align*}$$

Eliminate $x_k$ using the last relation in this presentation, to obtain

$$\begin{align*}{\operatorname{Gp}\bigl\langle {A_1,\dots,A_k,A^\prime,x_{k+1},\dots,x_n}\:|\:{ r_i(p_1,\dots,p_{k-1},p_k,\dots,x_n)=1\ (i\in I),\ p_k^m=1} \bigr\rangle}. \end{align*}$$

Notice that the specified mapping is certainly a homomorphism, and hence, $p_k^m$ is a consequence of the relations $r_i(p_1,\dots ,p_k,x_{k+1},\dots ,x_n)=1$ ( $i\in I$ ). Eliminating it yields the presentation for $G_{k+1}$ and proves the claim, and hence this case of the theorem.

Suppose now that (F3) holds. Write

$$\begin{align*}p_j\equiv p_j^\prime a_j^{\epsilon_j}p_j^{\prime\prime},\quad j=1,\dots,n, \end{align*}$$

and let $A^\prime =A\setminus \{a_1,\dots ,a_n\}$ . Let $X=\{x_1,\dots ,x_n\}$ and consider arbitrary $r_i=r_i(x_1,\dots , x_n)\in \overline {X}^\ast $ ( $i\in I$ ). We need to show that the group

(20) $$ \begin{align} {\operatorname{Gp}\bigl\langle {X}\:|\:{r_i(x_1,\dots,x_n)=1\ (i\in I)} \bigr\rangle} \end{align} $$

naturally embeds into

(21) $$ \begin{align} {\operatorname{Gp}\bigl\langle {A}\:|\:{r_i(p_1,\dots,p_n)=1\ (i\in I)} \bigr\rangle}. \end{align} $$

It is clear that (20) embeds into

(22) $$ \begin{align} {\operatorname{Gp}\bigl\langle {A^\prime,X}\:|\:{r_i(x_1,\dots,x_n)=1\ (i\in I)} \bigr\rangle} = {\operatorname{Gp}\bigl\langle {X}\:|\:{r_i(x_1,\dots,x_n)=1\ (i\in I)} \bigr\rangle}\ast F_{A^\prime}. \end{align} $$

By assumption, $p_j^\prime ,p_j^{\prime \prime }\in \overline {A^\prime }^\ast $ , so in (22), we can introduce redundant generators $a_1,\dots ,a_n$ as follows:

$$ \begin{align*} &{\operatorname{Gp}\bigl\langle {A^\prime,a_1,\dots,a_n,X}\:|\:{r_i(x_1,\dots,x_n)=1\ (i\in I),\ a_j^{\epsilon_j}=(p_j^\prime)^{-1}x_j(p_j^{\prime\prime})^{-1}\ (j=1,\dots,n)} \bigr\rangle}\\ =\ & {\operatorname{Gp}\bigl\langle {A,X}\:|\:{r_i(x_1,\dots,x_n)\ (i\in I),\ x_j=p_j\ (j=1,\dots,n)} \bigr\rangle}. \end{align*} $$

Eliminating the $x_j$ from the last presentation yields the group (21), showing that it is isomorphic to (22), and thus naturally embedding (20), as required.

Corollary 3.15. Let $M = {\operatorname {Inv}\bigl \langle {A}\:|\:{r_i=1\ (i\in I)} \bigr \rangle }$ be any special inverse monoid, and let $r_i \equiv r_{i1} \ldots r_{ik_i}$ be the factorisation of $r_i$ into minimal invertible pieces. If there is a basis $p_1, \ldots , p_n$ of ${\operatorname {Gp}\bigl \langle {\{ r_{ij}\::\: i\in I,\ 1\leq j\leq k_i\}} \bigr \rangle } \leq F_A$ satisfying any of (F1), (F2) or (F3), then the group of units U of M can be defined by a presentation with generators A and $|I|$ many defining relations. Specifically, if each $r_{ij}$ is written as $r_{ij}=r_{ij}^\prime (p_1,\dots ,p_n)$ , where $r_{ij}^\prime \in \overline {\{x_1,\dots ,x_n\}}^\ast $ , then U is defined by

$$\begin{align*}U={\operatorname{Gp}\bigl\langle {x_1,\dots,x_n}\:|\:{r_{i1}^\prime\dots r_{ik_i}^\prime=1\ (i\in I)} \bigr\rangle}. \end{align*}$$

4 An approach to computing pieces via regular languages

There already is in the literature an algorithm for computing a decomposition into invertible pieces. It was originally introduced by Adjan [Reference Adjan1], and modified by Zhang [Reference Zhang30]. It was designed for the setting of special monoid presentations, rather than inverse monoid presentations, but in fact remains valid for the latter as well.

The description we now give of the Adjan overlap algorithm follows that given by Lallement in [Reference Lallement14], who was chiefly concerned with one-relator monoids ${\operatorname {Mon}\bigl \langle {A}\:|\:{r=1} \bigr \rangle }$ . Here, we shall explain the natural generalisation of that algorithm to arbitrary finitely presented special monoids ${\operatorname {Mon}\bigl \langle {A}\:|\:{r_i \; (i \in I)} \bigr \rangle }$ . In general, this algorithm will compute a decomposition of the relators into pieces, but these will not in general be the minimal pieces (see Example 4.2 below). However, in the particular case of one-relator monoids ${\operatorname {Mon}\bigl \langle {A}\:|\:{r=1} \bigr \rangle }$ , an important theorem of Adjan [Reference Adjan1] shows that this algorithm does compute the minimal invertible pieces of the defining relator r.

Let $M= {\operatorname {Mon}\bigl \langle {A}\:|\:{r_i=1 \; (i \in I)} \bigr \rangle }$ be a special monoid, and set $R = \{r_i \::\: i \in I\}$ . We say that a submonoid T of the free monoid $A^{*}$ has property $({\mathcal {A}})$ if

• ( ${\mathcal {A}}$ ) For all $\alpha , \beta , \gamma \in A^{*}$ , if $\alpha \beta \in T$ and $\beta \gamma \in T$ then $\{\alpha ,\beta ,\gamma \} \subseteq T$ .

Let $U(R)$ be the smallest submonoid of $A^{*}$ , such that $R \subseteq U(R)$ and $U(R)$ satisfies ( $\mathcal {A}$ ).

To see that the monoid $U(R)$ exists, note that the set of submonoids of $A^{*}$ containing R and satisfying ( ${\mathcal {A}}$ ) is nonempty (since e.g. $A^{*}$ satisfies these properties), and it follows from the definitions that the intersection of any family of submonoids of $A^{*}$ with these properties again gives a submonoid of $A^{*}$ with these properties.

Recall that a subset C of $A^+$ is called a code if C is a set of free generators for the submonoid ${\operatorname {Mon}\bigl \langle {C} \bigr \rangle } \leq A^+$ . A subset C of $A^+$ is said to have the prefix property if $CA^+ \cap C = \varnothing $ . Similarly, we say C has the suffix property if $C \cap A^+C = \varnothing $ . Any subset C of $A^+$ with the prefix property is a code. We call these prefix codes. Similarly, if C has the suffix property, then C is a code called a suffix code. If C is both a prefix and a suffix code, then we call C a biprefix code.

We now make some observations about the set $U(R)$ .

1. (a) Every word $w \in U(R)$ represents and invertible element of the monoid M.

2. (b) $U(R)$ is a free monoid which is freely generated by a finite biprefix code $B(R)$ .

3. (c) There is an algorithm which takes any finite set R of words as input and computes the biprefix code $B(R)$ .

For proofs of these facts, we refer the reader to [Reference Lallement14, Section 1]. The idea behind the proof of (a) is to observe that if $\gamma $ and $\delta $ are words that represent invertible elements of M, then so does their product, and also, if $\alpha \beta $ and $\beta \gamma $ are words that represent invertible elements of M, then the words $\alpha $ , $\beta $ and $\gamma $ all also represent invertible elements of M. The starting point for the algorithm is provided by the members of R, which, being equal to $1$ in M, certainly represent invertible elements. Since $U(R)$ is obtained from R by closing under taking products and under adding triples of words $\alpha , \beta $ and $\gamma $ to ensure condition ( ${\mathcal {A}}$ ), this can be used to prove (a).

Regarding (a), it is important to note that even for one-relator monoids, we are not claiming that every word which represents an invertible element of M necessarily belongs to the set $U(R)$ . Indeed, if one considers the simple example of the bicyclic monoid ${\operatorname {Mon}\bigl \langle {b,c}\:|\:{bc=1} \bigr \rangle }$ , then clearly $U(R) = \{bc\}^{*}$ is the smallest submonoid of $\{b,c\}^{*}$ which contains $\{bc\}$ and has property ( ${\mathcal {A}}$ ). But the word $bbcc$ is equal to $1$ in the bicyclic monoid, so certainly represents an invertible element, while $bbcc \not \in \{bc\}^{*} = U(R)$ .

Even though we do not need it in this paper, for the sake of completeness, we explain here an algorithm which computes the finite biprefix code $B(R)$ that generates the free monoid $U(R)$ . This description follows [Reference Lallement14, page 372] (with a small correction we have made to a typo in (i) on [Reference Lallement14, page 372]).

For $i \in \mathbb {N}$ , we define the set $W_i$ inductively as follows. First, set $W_0 = R = \{r_i \::\: i \in I \}$ . Then, for $i>0$ , we define $W_i$ inductively in the following way. For $u \in A^{*}$ , we have $u \in W_{i+1}$ if and only if one of the following conditions holds:

1. (i) $u \in W_i$ and $v \not \in \operatorname {\mathrm {pref}}(u)$ and $v \not \in \operatorname {\mathrm {suff}}(u)$ for all $v \in W_i \setminus \{ u \}$ ;

2. (ii) there exist $v, v' \in X^{*}$ not both equal to $\epsilon $ , such that $uv \in W_i$ and $v'u \in W_i$ ;

3. (iii) there exist $v, v' \in X^{*}$ with $v \neq \epsilon $ , such that $uv \in W_i$ and $vv' \in W_i$ ;

4. (iv) there exist $v,v' \in X$ with $v' \neq \epsilon $ , such that $v'u \in W_i$ and $vv' \in W_i$ .

It may be shown that there is a number n, such that $W_n = W_{n'}$ for all $n' \geq n$ that is this process eventually stabilises. Then $B(R) = W_n$ is a biprefix code that freely generates $B(R)$ (see [Reference Lallement14, Theorem 1(i)]). Roughly speaking, the idea behind the above algorithm is that steps (ii)–(iv) are designed to ensure that the set we construct does satisfy property ( ${\mathcal {A}}$ ), while step (i) ensures that the set constructed has the prefix and suffix properties.

Since $B(R)$ is a code which generates the free monoid $U(R)$ , it follows that every word $w \in U(R)$ can be written uniquely as $w \equiv w_1 \ldots w_k$ , where $w_i \in B(R)$ for $1 \leq i \leq k$ . Since $R \subseteq U(R)$ , it follows that, in particular, every relator word $r_i$ with $i \in I$ decomposes uniquely as a product of words from $B(R)$ . We call this the decomposition of relators into invertible pieces determined by the Adjan algorithm. The key result showing the importance of this algorithm is that for special one-relator monoids, this algorithm actually computes the decomposition of the relator into minimal invertible pieces. We have already seen that the presentation determined by these pieces is then a presentation for the group of units of the monoid (see Theorem 1.2). This gives the following result of Adjan [Reference Adjan1].

For arbitrary special monoid presentations, this result is no longer true, as the following example demonstrates.

Example 4.2. Consider the monoid presentation

$$\begin{align*}{\operatorname{Mon}\bigl\langle {a,b,c,d}\:|\:{ab=1, cabd=1, cdd=1} \bigr\rangle} .\end{align*}$$

There are no overlaps, but $d = 1$ is easily seen to be a consequence of the defining relations. In particular, the letter d represents an invertible element. From this it follows that all the letters here are invertible, but this is not something that the Adjan algorithm will discover.

In fact, it is proved in [Reference Narendran, Ó’Dúnlang and Otto23] that the problem of whether a finitely presented special monoid is a group is undecidable. From this, it follows that there is no algorithm which takes finite special monoid presentations as input and computes the minimal invertible pieces of the relator.

It is natural to ask whether there is an algorithm which takes finite one-relator special inverse monoid ${\operatorname {Inv}\bigl \langle {A}\:|\:{r=1} \bigr \rangle }$ as input and computes the minimal invertible pieces of the relator r. This is a question that was considered by Margolis et al. in [Reference Margolis, Meakin and Stephen22]. As already mentioned above, in that paper, the following example is introduced

$$\begin{align*}{\mathcal{O}}={\operatorname{Inv}\bigl\langle {a,b,c,d}\:|\:{abcdacdadabbcdacd = 1} \bigr\rangle} = {\operatorname{Inv}\bigl\langle {a,b,c,d}\:|\:{r = 1} \bigr\rangle}, \end{align*}$$

called the O’Hare monoid. As explained above, one thing that makes this example significant is that the defining relator word clearly has no overlaps with itself, and hence, the Adjan overlap algorithm would terminate instantly, and return r as a single invertible piece of itself. However, Margolis et al. [Reference Margolis, Meakin and Stephen22], using van Kampen diagrams and Stephen’s procedure, succeed in showing that r in fact has a finer decomposition, namely

$$\begin{align*}r\equiv abcd\cdot acd\cdot ad\cdot abbcd\cdot acd. \end{align*}$$

They provide no further information about the group of units of the monoid ${\mathcal {O}}$ .

Our aim now is to give a unit computing algorithm for special inverse monoid presentations, which improves on the Adjan algorithm. Specifically, our new algorithm, which we shall call the Benois algorithm, will have the following properties

1. (1) it correctly computes the minimal invertible pieces of the O’Hare example, and

2. (2) it always computes a refinement of the Adjan algorithm.

These properties mean that every invertible piece that the Adjan algorithm discovers, the Benois algorithm also discovers, and there are examples where the Benois algorithm discovers strictly smaller pieces than the Adjan algorithm does.

Let $M = {\operatorname {Inv}\bigl \langle {A}\:|\:{r_i=1\ (i\in I)} \bigr \rangle }$ be a finitely presented special inverse monoid. Let

$$\begin{align*}\Sigma = \bigcup_{i \in I}(\operatorname{\mathrm{pref}}(r_i) \cup \operatorname{\mathrm{pref}}(r_i^{-1})) \subseteq \overline{A}^{*}. \end{align*}$$

Let $V = \mathrm {red}(\Sigma ^{*}) \subseteq F_A$ . For each $i \in I$ , decompose

(23) $$ \begin{align} r_i \equiv r_{i 1} r_{i 2} \ldots r_{i {k_i}} ,\end{align} $$

such that for every proper prefix p of $r_i$ , we have

(24) $$ \begin{align} \mathrm{red}(p^{-1}) \in V \Leftrightarrow p \equiv r_{i 1} r_{i 2} \ldots r_{i j} \ \mbox{for some} \ j \in \{ 1, \ldots, k_i \}. \end{align} $$

Intuitively, this decomposition is obtained by ‘reading’ $r_i$ from left to right, and ‘marking’ each prefix p with the property that $\mathrm {red}(p^{-1})\in V$ .

Note that this lemma does not claim that (23) is a decomposition into minimal invertible pieces. In fact, it remains an open question whether this is the case.

Next, we turn our attention to the question of whether the above decomposition of the relations into invertible pieces is computable. It is a consequence of a theorem of Benois that the free group $F_A$ has a decidable submonoid membership problem (see [Reference Lohrey15] and the references to Benois’s original work therein).

We shall call the algorithm for computing invertible pieces given in Lemma 4.4 the Benois algorithm.

Our aim is to prove the following result, which explains the relationship between the Benois algorithm and the Adjan algorithm.

We need a few more definitions and lemmas before we can prove Theorem 4.5. For any two words $\alpha , \beta \in \overline {A}^{*}$ , we write $\alpha \rightarrow \beta $ if $\beta $ can be obtained from $\alpha $ by a single application of a rewrite rule $xx^{-1} \rightarrow 1$ or $x^{-1}x \rightarrow 1$ (with $x \in A$ ). Let us write $\rightarrow ^{*}$ for the reflexive transitive closure of $\rightarrow $ that is $\alpha \rightarrow ^{*} \beta $ means that $\beta $ can be obtained from $\alpha $ by a finite (possibly empty) sequence of deletions $xx^{-1} \rightarrow 1$ or $x^{-1}x \rightarrow 1$ . If $\alpha \rightarrow ^{*} \beta $ , we say that $\alpha $ can be partially freely reduced to $\beta $ (partially, since $\beta $ need not be a reduced word).

Define

$$\begin{align*}{\overrightarrow{\Sigma^{*}}} = \{ \beta \in \overline{A}^{*} \::\: \alpha \rightarrow^{*} \beta \; \mbox{for some } \alpha \in \Sigma^{*} \}. \end{align*}$$

So ${\overrightarrow {\Sigma ^{*}}}$ is the closure of the set $\Sigma ^{*}$ under partial free reduction $\rightarrow ^{*}$ .

It follows from Lemma 2.2 that every word in ${\overrightarrow {\Sigma ^{*}}}$ represents a right invertible element of M.

Define ${\mathcal {U}} \subseteq {\overrightarrow {\Sigma ^{*}}}$ in the following way

$$\begin{align*}{\mathcal{U}} = \{ \beta \in {\overrightarrow{\Sigma^{*}}} \::\: \beta^{-1} \in {\overrightarrow{\Sigma^{*}}} \}. \end{align*}$$

Note that every word $u \in {\mathcal {U}}$ represents an invertible element of M.

The important thing to note about the set ${\mathcal {U}}$ is the following: Let p be a prefix of some relator $r_i$ with $i \in I$ . Then, by definition, $p \in \Sigma \subseteq {\overrightarrow {\Sigma ^{*}}}$ . If, in addition, $p \in {\mathcal {U}}$ , then p is an invertible prefix of a relator, and we will prove below that this invertible prefix p will be computed by the Benois algorithm. However, it is very important to note that the converse need not be true since it is possible that $p \in {\overrightarrow {\Sigma ^{*}}}$ , $p^{-1} \not \in {\overrightarrow {\Sigma ^{*}}}$ but $\operatorname {\mathrm {red}}(p^{-1}) \in {\overrightarrow {\Sigma ^{*}}}$ .

Proof. Since $p \in {\mathcal {U}}$ , it follows by definition of ${\mathcal {U}}$ that $p^{-1} \in {\overrightarrow {\Sigma ^{*}}}$ . Hence $\operatorname {\mathrm {red}}(p^{-1}) \in {\overrightarrow {\Sigma ^{*}}}$ , since by definition the set ${\overrightarrow {\Sigma ^{*}}}$ is closed under the operation of partial free reduction of words, and hence

$$\begin{align*}\operatorname{\mathrm{red}}(p^{-1}) \in \operatorname{\mathrm{red}}({\overrightarrow{\Sigma^{*}}}) = \operatorname{\mathrm{red}}(\Sigma^{*}) = V. \end{align*}$$

It follows from the definition of the Benois algorithm that p is an invertible piece of $r_i$ computed by the Benois algorithm.

We will now prove that ${\mathcal {U}}$ does contain all prefixes of relators computed by the Adjan algorithm. Combining this with Lemma 4.7 will prove Theorem 4.5.

Proof. Since $\gamma \rightarrow ^{*} \delta $ , we can write

$$\begin{align*}\gamma \equiv w_0 \rightarrow w_1 \rightarrow \ldots \rightarrow w_k \equiv \delta. \end{align*}$$

We have $w_k \equiv \delta \equiv \delta _1 \delta _2$ . Then applying Lemma 4.9 to $w_i \rightarrow w_{i+1}$ for all i, it follows that each $w_i$ can be decomposed as $w_i \equiv w_i^{\prime } w_i^{\prime \prime }$ and

$$\begin{align*}w_0^{\prime} \rightarrow w_1^{\prime} \rightarrow \ldots \rightarrow w_{k-1}^{\prime} \rightarrow \delta_1 \quad\text{and}\quad w_0^{\prime\prime} \rightarrow w_1^{\prime\prime} \rightarrow \ldots \rightarrow w_{k-1}^{\prime\prime} \rightarrow \delta_2. \end{align*}$$

Setting $\gamma _1 \equiv w_0^{\prime }$ and $\gamma _2 \equiv w_0^{\prime \prime }$ then proves the result.

Note that the set $\Sigma ^{*}$ is clearly prefix closed.

Note that $\Sigma ^{*}$ is closed under products.

The following is immediate from the definition of ${\mathcal {U}}$ .

Note that the set ${\mathcal {U}}$ will not in general be closed under prefixes.

We are now in a position to prove the key lemma that we need to prove our main result relating the Benois algorithm and the Adjan algorithm.

Proof. Since $\alpha \beta , \beta \gamma \in {\mathcal {U}}$ and ${\mathcal {U}}$ is closed under inverses by Lemma 4.14, it follows that

$$\begin{align*}\{\alpha\beta, \; \beta^{-1}\alpha^{-1}, \; \beta\gamma, \; \gamma^{-1}\beta^{-1} \} \subseteq {\mathcal{U}} \subseteq {\overrightarrow{\Sigma^{*}}}. \end{align*}$$

Since ${\overrightarrow {\Sigma ^{*}}}$ is prefix closed by Lemma 4.11, and $\beta ^{-1}\alpha ^{-1}, \beta \gamma \in {\overrightarrow {\Sigma ^{*}}}$ , it follows that $\beta ^{-1}, \beta \in {\overrightarrow {\Sigma ^{*}}}$ , which implies $\beta \in {\mathcal {U}}$ and $\beta ^{-1} \in {\mathcal {U}}$ . Since ${\mathcal {U}}$ is closed for products by Lemma 4.15, and $\beta ^{-1} \in {\mathcal {U}}$ and $\beta \gamma \in {\mathcal {U}}$ , it follows that $\beta ^{-1}\beta \gamma \in {\mathcal {U}}$ , and hence, $\gamma \in {\mathcal {U}}$ since ${\mathcal {U}}$ is closed under partial free reductions by Lemma 4.16.

Also, $\alpha \beta \in {\mathcal {U}}$ and $\beta ^{-1} \in {\mathcal {U}}$ implies $\alpha \beta \beta ^{-1} \in {\mathcal {U}}$ by Lemma 4.15, which thus $\alpha \in {\mathcal {U}}$ by Lemma 4.16.

This completes the proof that $\{\alpha , \beta , \gamma \} \subseteq {\mathcal {U}}$ .

We now have all we need to prove our main result of this section.

Definition 4.18. We call a set of words $W \subseteq X^{*}$ overlap free, if for all $w_1, w_2 \in W$ , we have

$$\begin{align*}\mathrm{pref}(w_1) \cap \mathrm{suff}(w_2) = \begin{cases} \{ \epsilon \} & \mbox{if } w_1 \neq w_2 \\ \{ \epsilon, w_1 \} & \mbox{if } w_1 = w_2. \end{cases} \end{align*}$$

Example 4.21. We now illustrate the Benois algorithm by applying it to the O’Hare monoid

$$\begin{align*}{\mathcal{O}}={\operatorname{Inv}\bigl\langle {a,b,c,d}\:|\:{abcdacdadabbcdacd=1} \bigr\rangle} ={\operatorname{Inv}\bigl\langle {a,b,c,d}\:|\:{r = 1} \bigr\rangle}. \end{align*}$$

We claim that when applied to this example, the Benois algorithm will compute the following decomposition of r into invertible pieces

$$\begin{align*}r\equiv abcd\cdot acd\cdot ad\cdot abbcd\cdot acd. \end{align*}$$

For notational convenience, we set

$$\begin{align*}\alpha \equiv abcd, \; \beta \equiv acd, \; \gamma \equiv ad, \; \delta \equiv abbcd. \end{align*}$$

Using the same notation as above, we have

$$\begin{align*}\Sigma = \mathrm{pref}(r) \cup \mathrm{suff}(r)^{-1} = \{ a, ab, abcd, abcda, \ldots, r \} \cup \{ d^{-1}, (cd)^{-1}, (acd)^{-1}, \ldots, r^{-1} \}, \end{align*}$$

and $V = \mathrm {red}(\Sigma ^{*})$ , which is a subset of $F_A$ . Since r is a positive word, it follows that for every prefix p of r, both p and $p^{-1}$ are reduced words. It follows that the Benois algorithm will compute the set of all prefixes p of r, such that $p^{-1} \in V$ .

Let us now list some of the prefixes p that this algorithm will compute. It is a straightforward calculation to verify that

$$\begin{align*}\operatorname{\mathrm{red}}( \; \beta(\alpha \beta \gamma \delta \beta)^{-1} (\alpha \beta \gamma) \; ) \equiv \delta^{-1} \end{align*}$$

and

$$\begin{align*}\operatorname{\mathrm{red}}(\beta^{-1} \alpha \delta^{-1}) \equiv \alpha^{-1}. \end{align*}$$

Then, we have:

$$ \begin{align*} \alpha^{-1} &\equiv \operatorname{\mathrm{red}}(\beta^{-1} \alpha \delta^{-1} ) \equiv \operatorname{\mathrm{red}}( \; \beta^{-1} \cdot \alpha \beta \cdot (\alpha\beta\gamma\delta\beta)^{-1} \cdot (\alpha\beta\gamma) \; ) \in V \\ (\alpha \beta)^{-1} &\equiv \beta^{-1} \alpha^{-1} \equiv \operatorname{\mathrm{red}}(\; \beta^{-1} \beta^{-1} \alpha \delta^{-1} \;) \equiv \operatorname{\mathrm{red}}(\; \beta^{-1} \cdot \beta^{-1} \cdot \alpha \beta \cdot (\alpha\beta\gamma\delta\beta)^{-1} \cdot (\alpha\beta\gamma) \;) \in V \\ (\alpha \beta \gamma)^{-1} &\equiv \operatorname{\mathrm{red}}( (\delta \beta) (\alpha \beta \gamma \delta \beta)^{-1} ) \equiv \operatorname{\mathrm{red}}( (\alpha \beta^{-1} \alpha) \beta (\alpha \beta \gamma \delta \beta)^{-1} ) \\ &\equiv \operatorname{\mathrm{red}}( \alpha \cdot \beta^{-1} \cdot \alpha \beta \cdot (\alpha \beta \gamma \delta \beta)^{-1} ) \in V \\ (\alpha \beta \gamma \delta)^{-1} &= \operatorname{\mathrm{red}}(\beta (\alpha \beta \gamma \delta \beta)^{-1}) = \operatorname{\mathrm{red}}( \alpha \delta^{-1} \alpha (\alpha \beta \gamma \delta \beta)^{-1} ) \\ &= \operatorname{\mathrm{red}}( (\alpha \beta) \cdot (\delta \beta)^{-1} \cdot \alpha \cdot (\alpha \beta \gamma \delta \beta)^{-1} ) \in V. \end{align*} $$

This proves that the Benois algorithm computes a decomposition which is a refinement of the above decomposition. To show that it is exactly this decomposition that is computed, it may be shown, by appealing to bicyclic monoid homomorphic images of this monoid, that none of the pieces of this decomposition has a proper nonempty invertible prefix. Indeed, if there were a finer decomposition into minimal invertible pieces, then one quickly sees that in all possible cases, this would imply that all the generators are invertible, and so the monoid ${\mathcal {O}}$ would need to be a group. However, ${\mathcal {O}}$ is not a group since the map from $\{a,b,c,d\}^{*}$ onto $\{x,y\}^{*}$ defined by $a \mapsto a$ , $b \mapsto 1$ , $c \mapsto 1$ and $d \mapsto d$ induces a surjective a homomorphism from ${\mathcal {O}}$ onto the bicyclic monoid ${\operatorname {Inv}\bigl \langle {a,d}\:|\:{ad=1} \bigr \rangle }$ .

We leave the details of this as an exercise for the reader.

5 Examples

This section will contain some examples of one-relator groups, and one-relator inverse monoids, to which the results of the previous sections can be applied. We have already seen some applications in Section 3, for example to the case where the pieces $p_i$ are powers of generators from A (see (F1) in Section 3).

We are motivated by the question of whether the group of units of a one-relator inverse monoid is a one-relator group. Recall that at the start of Section 3, we gave the example of the one-relator inverse monoid

$$\begin{align*}M={\operatorname{Inv}\bigl\langle {a,b,c}\:|\:{a (bc^2b^{-1}) a (bc^3b^{-1}) a (bc^2b^{-1}) a=1} \bigr\rangle}, \end{align*}$$

with minimal invertible pieces a, $bc^2b^{-1}$ , and $bc^{3}b^{-1}$ . We observed there that

$$\begin{align*}{\operatorname{Gp}\bigl\langle {x,y,z}\:|\:{xyxzxyx=1} \bigr\rangle}=F_{x,y}\end{align*}$$

is not a presentation for the group of units of the monoid M. A key feature of that example was that $\{a,bc^2b^{-1},bc^3b^{-1}\}$ is not a basis for ${\operatorname {Gp}\bigl \langle {a,bc^2b^{-1},bc^3b^{-1}} \bigr \rangle }\leq F_{a,b,c}$ . On the other hand, $\{a, bcb^{-1} \}$ is a basis for ${\operatorname {Gp}\bigl \langle {a,bc^2b^{-1},bc^3b^{-1}} \bigr \rangle }\leq F_{a,b,c}$ , and this basis satisfies the conditions of Theorem 3.11 (setting $\mu (a)=a$ and $\mu (bcb^{-1})=c$ ). Using this fact, we can express each of the original pieces $\{a,bc^2b^{-1},bc^3b^{-1}\}$ in terms of the basis $\{a, bcb^{-1} \}$ , which rewrites the relator word

$$\begin{align*}a (bc^2b^{-1}) a (bc^3b^{-1}) a (bc^2b^{-1}) a \end{align*}$$

as

$$\begin{align*}a (bcb^{-1})^2 a (bcb^{-1})^3 a (bcb^{-1})^2 a \end{align*}$$

and then by Corollary 3.13, we can conclude that the group of units of M is the one-relator group with presentation

$$\begin{align*}{\operatorname{Gp}\bigl\langle {x,t}\:|\:{xt^2xt^3xt^2x=1} \bigr\rangle}. \end{align*}$$

It is natural to ask whether this approach might be used for other one-relator inverse monoids. As explained in the Introduction, one of the key motivating examples for the work is the O’Hare monoid. We shall now show how the group of units of the O’Hare monoid can indeed be computed using a similar approach to the example above.

5.1 The group of units of the O’Hare monoid

Recall from the Introduction that the O’Hare monoid ${\mathcal {O}}$ is the inverse monoid defined by the following inverse monoid presentation

$$\begin{align*}{\operatorname{Inv}\bigl\langle {a,b,c,d}\:|\:{abcdacdadabbcdacd=1} \bigr\rangle} ={\operatorname{Inv}\bigl\langle {a,b,c,d}\:|\:{r = 1} \bigr\rangle}. \end{align*}$$

As explained in the Introduction, this was one of the main motivating examples which prompted the research presented in this paper. As already mentioned above, Margolis et al. [Reference Margolis, Meakin and Stephen22] proved that the decomposition into minimal invertible pieces of this defining relator is

$$\begin{align*}r\equiv abcd\cdot acd\cdot ad\cdot abbcd\cdot acd. \end{align*}$$

They prove this using van Kampen diagrams and Stephen’s procedure. We gave an alternative proof of this fact in Example 4.21 using the Benois algorithm (see Lemma 4.4). As in Example 4.21, for notational convenience, we set

$$\begin{align*}\alpha \equiv abcd, \; \beta \equiv acd, \; \gamma \equiv ad, \; \delta \equiv abbcd. \end{align*}$$

We shall now show how the results from Section 3 can be applied to prove that the group of units $U({\mathcal {O}})$ of the O’Hare monoid ${\mathcal {O}}$ is the free group of rank $2$ .

This is interesting for two reasons. Firstly, it shows that the groups of units of the O’Hare monoid ${\mathcal {O}}$ is a one-relator group (since every free group is vacuously a one-relator group). Secondly, while the group of units of ${\mathcal {O}}$ is a one-relator group, the group of units is not isomorphic to the group

$$\begin{align*}H = {\operatorname{Gp}\bigl\langle {\alpha, \beta, \gamma, \delta}\:|\:{ \alpha \beta \gamma \delta \beta = 1} \bigr\rangle} , \end{align*}$$

which is the presentation obtained by replacing each minimal invertible piece by a letter in the obvious way. Indeed, in the presentation for H, we can remove the redundant generator $\delta $ , and so H is the free group on $\{\alpha ,\beta ,\gamma \}$ .

This gives another example (in addition to the example discussed at the start of Section 3) showing that Makanin’s theorem for special monoids (Theorem 1.2) does not generalise directly to special inverse monoids. We will construct further examples later in this paper which show just how dramatically Makanin’s theorem fails to generalise to special inverse monoids.

So we are left with the task of proving that the group of units $U({\mathcal {O}})$ of ${\mathcal {O}}$ is a free group of rank $2$ .

The first step will be to write down an alternative one-relator presentation for ${\mathcal {O}}$ which has minimal invertible pieces that satisfy condition (F3) from Section 3.

Since $\alpha $ , $\beta $ , $\gamma $ and $\delta $ all represent invertible elements of the monoid ${\mathcal {O}}$ , it follows that

$$\begin{align*}\delta \alpha^{-1} = abbcd d^{-1} c^{-1} b^{-1} a^{-1}, \end{align*}$$

and

$$\begin{align*}\beta \gamma^{-1} = acd d^{-1} a^{-1} \end{align*}$$

are both invertible in ${\mathcal {O}}$ . Hence, by Lemma 2.2, it follows that these words are equal in ${\mathcal {O}}$ to the words obtained by freely reducing them, namely, the words $aba^{-1}$ and $aca^{-1}$ . This shows that

$$\begin{align*}aba^{-1}, \ aca^{-1} \ \mbox{and} \ ad \end{align*}$$

are all invertible in ${\mathcal {O}}$ . It follows that any product of these words is also invertible in ${\mathcal {O}}$ . In particular, the word

$$\begin{align*}u \equiv (aba^{-1}) (aca^{-1}) (ad) (aca^{-1}) (ad) (ad) (aba^{-1}) (aba^{-1}) (aca^{-1}) (ad) (aca^{-1}) (ad) \end{align*}$$

is invertible in ${\mathcal {O}}$ . Since this word is invertible, it follows from Lemma 2.2 that it is equal in ${\mathcal {O}}$ to the word obtained by freely reducing this word. But it is easy to see that the free reduction of this word gives the defining relator r in the original presentation for ${\mathcal {O}}$ . Hence, $u = r = 1$ holds in the monoid ${\mathcal {O}}$ .

Conversely, let M be the inverse monoid defined by the presentation

$$\begin{align*}{\operatorname{Inv}\bigl\langle {a,b,c,d}\:|\:{u=1} \bigr\rangle} ,\end{align*}$$

where u is the word above. Since u is invertible in M, it follows that $u = \mathrm {red}(u)$ in M. Hence, $u=r$ in M.

Combining these observations, we have proved

$$\begin{align*}{\operatorname{Inv}\bigl\langle {a,b,c,d}\:|\:{r=1} \bigr\rangle} = {\operatorname{Inv}\bigl\langle {a,b,c,d}\:|\:{r=1, u=1} \bigr\rangle} = {\operatorname{Inv}\bigl\langle {a,b,c,d}\:|\:{u=1} \bigr\rangle}. \end{align*}$$

So the O’Hare monoid is defined by the presentation

$$\begin{align*}{\operatorname{Inv}\bigl\langle {a,b,c,d}\:|\:{ (aba^{-1}) (aca^{-1}) (ad) (aca^{-1}) (ad) (ad) (aba^{-1}) (aba^{-1}) (aca^{-1}) (ad) (aca^{-1}) (ad) =1 } \bigr\rangle}. \end{align*}$$

Next, we claim that working with this new presentation for ${\mathcal {O}}$ , the minimal invertible pieces of the defining relator u are $aba^{-1}$ , $aca^{-1}$ and $ad$ . We already proved above that each of these words represents an invertible element of ${\mathcal {O}}$ , so these are certainly invertible pieces of the defining relator u. For minimality, if any of these pieces was not a minimal invertible piece, then in all cases, it would follow that a is invertible. But a is not invertible in ${\mathcal {O}}$ since $ad$ is a minimal invertible piece of r.

We claim that the decomposition of u into minimal invertible pieces in the presentation ${\operatorname {Inv}\bigl \langle {a,b,c,d}\:|\:{u=1} \bigr \rangle }$ satisfies condition (F3) from Section 3. For this, we just need to observe that each piece contains a letter which appears in that piece exactly once, and does not appear in any of the other pieces. Here, we can take b in the piece $aba^{-1}$ , c in the piece $aca^{-1}$ and the letter d in the piece $ad$ .

Since condition (F3) holds, it follows that the hypotheses of Corollary 3.13 are satisfied, and hence, applying this corollary, we conclude that the group of units $U({\mathcal {O}})$ of ${\mathcal {O}}$ is isomorphic to

$$\begin{align*}{\operatorname{Gp}\bigl\langle {x,y,z}\:|\:{xyzyzzxxyzyz=1} \bigr\rangle}. \end{align*}$$

Comparing this with the example at the start of Section 3, what we have proved here is that the situation with the O’Hare monoid is similar. Indeed, the original set of pieces $\{abcd, acd, ad, abbcd \}$ is not a basis for ${\operatorname {Gp}\bigl \langle {abcd, acd, ad, abbcd } \bigr \rangle } \leq F_{a,b,c,d}$ . On the other hand, $\{aba^{-1}, aca^{-1}, ad \}$ is a basis for ${\operatorname {Gp}\bigl \langle {abcd, acd, ad, abbcd } \bigr \rangle }\leq F_{a,b,c,d}$ , and this basis satisfies the conditions of Theorem 3.11 (setting $\mu (aba^{-1})=b$ , $\mu (aca^{-1})=c$ and $\mu (ad)=d$ ). If we rewrite the pieces in the original O’Hare presentation in terms of this basis and then apply Corollary 3.13, we conclude (via the calculations above) that the group of units of ${\mathcal {O}}$ is isomorphic to the one-relator group ${\operatorname {Gp}\bigl \langle {x,y,z}\:|\:{xyzyzzxxyzyz=1} \bigr \rangle }$ .

Now, we have

$$ \begin{align*} {\operatorname{Gp}\bigl\langle {x,y,z}\:|\:{xyzyzzxxyzyz=1} \bigr\rangle} & = {\operatorname{Gp}\bigl\langle {x,y,z,t}\:|\:{xttzxxtt=1, t=yz} \bigr\rangle} \\ & = {\operatorname{Gp}\bigl\langle {x,y,z,t}\:|\:{xttzxxtt=1, y=tz^{-1}} \bigr\rangle} \\ & = {\operatorname{Gp}\bigl\langle {x,z,t}\:|\:{xttzxxtt=1} \bigr\rangle} \cong \mathrm{FG}(x,t). \end{align*} $$

The last isomorphism follows upon removing the redundant generator z in the previous presentation. This completes the proof that the group of units of the O’Hare monoid is a free group of rank $2$ .

Both the O’Hare monoid and the example at the start of Section 3 are examples of one-relator inverse monoids

$$\begin{align*}{\operatorname{Inv}\bigl\langle {A}\:|\:{r=1} \bigr\rangle}, \end{align*}$$

which show that the obvious generalisation of Makanin’s theorem to special one-relator monoids does not hold. However, for both these examples, it was possible to resolve the issue by finding a suitable basis for the subgroup of $F_A$ generated by the pieces of r and then rewriting each of the pieces, and the relator r, in terms of this new basis. In both cases, this gave us a one-relator presentation for the group of units of the inverse monoid in question. Specifically, these examples do not resolve the question of whether the group of units of a special one-relator inverse monoid is a one-relator group. Given these examples, it is natural to ask whether in fact the key property that we need for a set of pieces to be free for substitutions is that they are a basis for the subgroup of $F_A$ that they generate (like in these two examples). The following example which was originally due to Higman shows that this is not the case. Specifically, it shows that the conditions in the theorems in Section 3 cannot be weakened to just insisting that the set of pieces is Nielsen reduced.

5.2 The G. Higman example

This example appears in the following paper of Steve Pride [Reference Pride24], where he attributes the example to Graham Higman. As explained there, if we let

$$\begin{align*}B = {\operatorname{Gp}\bigl\langle {a,b}\:|\:{b^{-1} a^2 b = a^3} \bigr\rangle} ,\end{align*}$$

then the subgroup ${\operatorname {Gp}\bigl \langle {a^4,b} \bigr \rangle } \leq B$ is not free and every presentation of the group ${\operatorname {Gp}\bigl \langle {a^4,b} \bigr \rangle }$ with respect to the generating set $\{a^4, b\}$ requires at least two relators. Note, the group B is the well-known Baumslag-Solitar group $BS(2,3)$ .

This example arose as part of an investigation by Pride of conditions under which subgroups of one-relator groups are again one-relator. One interesting thing in this example is that the two-generated subgroup ${\operatorname {Gp}\bigl \langle {a^4,b} \bigr \rangle }$ of the one-relator group B does not admit a one-relator presentation with respect to the generators $\{a^4, b\}$ (as proved by Higman). On the other hand, the subgroup ${\operatorname {Gp}\bigl \langle {a^4,b} \bigr \rangle }$ is actually a one-relator group. Indeed, it may be shown that ${\operatorname {Gp}\bigl \langle {a^4,b} \bigr \rangle } = B$ , that is, $\{a^4,b\}$ is a generating set for B. To see this, it suffices to observe that in B, we have

$$\begin{align*}a^2 = [a^6] (a^4)^{-1} = [(b^{-1} a^2 b)^2] (a^4)^{-1}= [b^{-1} a^4 b](a^4)^{-1} \in {\operatorname{Gp}\bigl\langle {a^4,b} \bigr\rangle}. \end{align*}$$

But now since $a^2$ and b both belong to ${\operatorname {Gp}\bigl \langle {a^4,b} \bigr \rangle }$ , it follows that $a^3 = b^{-1} a^2 b \in {\operatorname {Gp}\bigl \langle {a^4,b} \bigr \rangle }$ , and finally, since $a^3$ and $a^2$ both belong to ${\operatorname {Gp}\bigl \langle {a^4,b} \bigr \rangle }$ , it follows that $a = (a^3)(a^2)^{-1}$ also belongs to ${\operatorname {Gp}\bigl \langle {a^4,b} \bigr \rangle }$ . Hence, ${\operatorname {Gp}\bigl \langle {a^4,b} \bigr \rangle } = {\operatorname {Gp}\bigl \langle {a,b} \bigr \rangle } = B$ . So this is a concrete example showing that a two-generated one-relator group can admit a one-relator presentation with respect to a generating set of size two, but not admit any one-relator presentation with respect to another generating set of size two. Among other things, this shows how sensitive the property of being one-relator is to the choice of finite generating set for the group.

The following result shows how this example can be adapted to give an example of a Nielsen reduced set which is not free for substitutions into one-relator groups. We shall not need the definition of Nielsen reduced here. The definition can be found in [Reference Lyndon and Schupp18, page 6]. The thing that is relevant for us here is the result (see [Reference Lyndon and Schupp18, Proposition 2.6]) that if $X \subseteq F_A$ is Nielsen reduced, then ${\operatorname {Gp}\bigl \langle {X} \bigr \rangle } \leq F_A$ is free with basis X.

Proposition 5.1. Let $X = \{ ab^{-1}a^2, b, a^{4} \}$ , which is Nielsen reduced a subset of the free group $F_{a,b}$ . Let $\phi : F_{x,y,z} \rightarrow F_{a,b}$ be the unique homomorphism extending

$$\begin{align*}x \mapsto ab^{-1}a^2, \quad y \mapsto b, \quad z \mapsto a^{4}. \end{align*}$$

Set

$$\begin{align*}K = {\operatorname{Gp}\bigl\langle {x,y,z}\:|\:{xyz^{-1}=1} \bigr\rangle} \end{align*}$$

and

$$\begin{align*}G = {\operatorname{Gp}\bigl\langle {a,b}\:|\:{(ab^{-1}a^2)(b)(a^{-4})=1} \bigr\rangle}. \end{align*}$$

Let $\hat {\phi }: K \rightarrow G$ be the homomorphism induced by $\phi $ . Then $\hat {\phi }$ is not injective, and hence is not an isomorphism between K and the subgroup H of G generated by the set $X = \{ ab^{-1}a^2, b, a^{4} \}$ . That is, the Nielsen reduced set $X = \{ ab^{-1}a^2, b, a^{4} \}$ is not free for substitution into the one-relator group ${\operatorname {Gp}\bigl \langle {x,y,z}\:|\:{xyz^{-1}=1} \bigr \rangle }$ via $x \mapsto ab^{-1}a^2, y \mapsto b$ and $z \mapsto a^{4}$ .

Proof. It is a straightforward exercise to check that X is a Nielsen reduced set of reduced words in the free group $F_{a,b}$ , and hence, ${\operatorname {Gp}\bigl \langle {X} \bigr \rangle } \leq F_{a,b}$ is freely generated by X. Certainly, $\phi $ defines a homomorphism since $\phi (xyz^{-1})=1$ in G. Clearly, K is isomorphic to the free group on y and z. In particular, the words $z^2 y$ and $yz^3$ represent distinct elements in the group K. On the other hand

$$\begin{align*}\phi(z^2 y) = \phi(y z^{3}) \end{align*}$$

in G. Indeed, in G, we have $a^2b=ba^3$ , and hence

$$\begin{align*}\phi(z^2y)=a^8b=(a^2)^4b=b(a^3)^4=ba^{12}=\phi(yz^3), \end{align*}$$

as required.

Note that as it stands, the example in Proposition 5.1 does not immediately give a special inverse monoid with interesting properties, since the set $X = \{ ab^{-1}a^2, b, a^{4} \}$ cannot be the set of minimal invertible words in an inverse monoid presentation (since, for instance, $a^4$ invertible implies a is invertible, and hence, $a^4$ is not a minimal invertible piece). Also, in this example, the subgroup generated by the pieces $X = \{ ab^{-1}a^2, b, a^{4} \}$ is in fact a one-relator group since (as explained before the statement of the theorem), but this theorem shows that it does not admit the ‘obvious’ one-relator presentation given by replacing the pieces by letters in the obvious way.

However, this example is the first evidence that there may exist examples of one-relator special inverse monoids with group of units not being a one-relator group. This will be explored further in the next section.

6 A construction

In this section, we shall give a general construction, which will then be used in the next section to give examples of special inverse monoids that exhibit unexpected behaviour in terms of their groups of units.

The construction we give here was used in [Reference Gray6] to give an example of a one-relator special inverse monoid with undecidable word problem. It has also been used in the papers [Reference Gray and Dolinka7] and [Reference Gray, Silva and Szakacs9] to construct counterexamples to questions about the prefix membership problem for one-relator groups, and the word problem for finitely presented inverse monoids with hyperbolic Schützenberger graphs. To make this paper self-contained, we provide full details of the construction here. Also, we use slightly different notational conventions than those used in [Reference Gray6]. Some of the results we need about this construction have already been proved in [Reference Gray6], but there are some other facts about the construction that we need here that are not proved in that paper, so we will provide the necessary proofs.

6.1 The construction

Let $A=\{a_1,\dots ,a_n\}$ be a finite nonempty alphabet. Let $Q = \{ r_i \::\: i \in I \}$ be a subset of $\overline {A}^{*}$ , where I is nonempty, and we assume there is a distinguished symbol $1 \in I$ . Let $W = \{ w_j \::\: j=1,\dots , k \}$ be a finite subset of $\overline {A}^{*}$ . Let t be a symbol not in A.

We define two groups which depend on Q by

(25) $$ \begin{align} \hspace{-15pt}K_Q &= {\operatorname{Gp}\bigl\langle {A}\:|\:{r_i=1 \; (i \in I)} \bigr\rangle}\qquad\qquad \end{align} $$

(26) $$ \begin{align} G_Q &= {\operatorname{Gp}\bigl\langle {A, t}\:|\:{r_i=1 \; (i \in I)} \bigr\rangle} = K_Q \ast F_t. \end{align} $$

Given a list of words $u_1, \ldots , u_m \in \overline {A}^{*}$ , we define

$$\begin{align*}e(u_1, u_2, \ldots, u_m) = u_1 u_1^{-1} u_2 u_2^{-1} \ldots u_m u_m^{-1}, \end{align*}$$

noting that this clearly freely reduces to $1$ in the free group $F_A$ .

We also define two inverse monoids, the first depending on Q, and the second on both Q and W, as follows:

(27) $$ \begin{align} N_Q &= {\operatorname{Inv}\bigl\langle {A}\:|\:{r_i=1 \; (i \in I)} \bigr\rangle}\qquad\qquad\qquad \end{align} $$

(28) $$ \begin{align} M_{Q,W} &= {\operatorname{Inv}\bigl\langle {A, t}\:|\:{fr_1=1, r_i=1 \; (i \in I \setminus \{ 1 \})} \bigr\rangle}, \end{align} $$

where

(29) $$ \begin{align} f = e(a_1, \ldots, a_n, tw_1t^{-1}, \ldots, tw_kt^{-1}, a_1^{-1}, \ldots, a_n^{-1}). \end{align} $$

We make the following observations about the groups and monoids we have just defined:

1. (M1) $K_Q$ is the maximal group image of $N_Q$ , and $G_Q$ is the maximal group image of $M_{Q,W}$ (under the natural homomorphisms).

2. (M2) Presentation (28) for $M_{Q,W}$ is equivalent to

   (30) $$ \begin{align} M_{Q,W}= \operatorname{Inv}\bigl\langle &{A, t}\:|\: r_i=1, \ a_j a_j^{-1} = a_j^{-1} a_j = 1,\\& t w_l t^{-1} t w_l^{-1} t^{-1}= 1 \ (i{\in} I,\ j \in [n],\ l{\in} [k]) \bigr\rangle \nonumber\end{align} $$
   in the sense that two words over $\overline {(A \cup \{t\})}$ are equal modulo the relations of (28) if and only if they are equal modulo the relations (30).

3. (M3) All the generators $a_j \in A$ are invertible in $M_{Q,W}$ , while t and all of the elements $t w_l t^{-1}$ are right invertible in M.

4. (M4) $M_{Q,W}$ maps naturally onto the bicyclic monoid $B={\operatorname {Inv}\bigl \langle {b}\:|\:{bb^{-1}=1} \bigr \rangle }$ via $a_j\mapsto 1$ , $t\mapsto b$ .

5. (M5) t is not invertible in $M_{Q,W}$ .

Indeed, observation (M1) is immediate from the definitions and the general fact that the maximal group image of an inverse monoid defined by a presentation is the group defined by the same presentation. (M2) can be proved using Lemma 2.2. A full proof is given in [Reference Gray6, Lemma 3.3]. (M3) follows from (M2) and the defining relations in the presentation (30). (M4) is immediate from the fact that $M_{Q,W}$ is given by the presentation (30) and then the observation that replacing a by $1$ and t by b in that presentation just leaves the relation $bb^{-1}bb^{-1}=1$ which certainly holds in B. (M5) follows from (M4) since b is not invertible in the bicyclic monoid B, and the image of an invertible element of a monoid under a surjective homomorphism must again be an invertible element.

We will make use of the following general lemma, which follows immediately from the universal properties of free products.

Lemma 6.1. Let G and H be groups. Let M be a submonoid of G and N be a submonoid of H. Then the submonoid of the free product $G \ast H$ generated by $M \cup N$ is isomorphic to $M \ast N$ .

The following lemma is probably well known, but we give a proof for completeness.

Lemma 6.2. Let H be a group. Then the subgroup of the free product $G = H \ast F_t$ generated by $H \cup tHt^{-1}$ is isomorphic to $H \ast H$ .

Proof. Set $\overline {H} = t H t^{-1} \leq G = H * F_t$ . Let L be the subgroup of G generated by $H \cup \overline {H}$ . Now H and $\overline {H}$ are subgroups of L and $H \cap \overline {H} = \varnothing $ by the normal form theorem for elements in free products of groups. Given a reduced sequence $g_1, g_2, \ldots , g_n$ , where the $g_i$ all belong to L and alternate between H and $\overline {H}$ , if $n> 0$ , then it again follows from the normal form theorem in G that $g_1 g_2 \ldots g_n \neq 1$ . Thus, all the conditions of [Reference Lyndon and Schupp18, Lemma 1.7] are satisfied, and we conclude that $L \cong H * \overline {H}$ . Clearly, $H \cong \overline {H}$ since they are conjugate subgroups of G. This completes the proof that $L \cong H * H$ .

We are now in a position to state and prove the main result of this section, which establishes the key properties of the monoid $M_{Q,W}$ that we will need in our applications and examples in the next section.

Theorem 6.3. With the above definitions and notation, the special inverse monoid $M_{Q,W}$ has the following properties.

1. (i) The presentation (28) of $M_{Q,W}$ has the same number of defining relations as the original presentation (25) of $K_Q$ .

2. (ii) The monoid $M_{Q,W}$ is E-unitary.

3. (iii) Let $T_W$ be the submonoid of the group $K_Q$ generated by W. Then the submonoid of right units $R(M_{Q,W})$ of $M_{Q,W}$ is isomorphic to the submonoid of the group $G_Q=K_Q \ast F_t$ generated by $\{ t\} \cup K_Q \cup t T_W t^{-1}$ .

4. (iv) Let $V_{Q,W}$ be the submonoid of $R(M_{Q,W})$ generated by $A \cup A^{-1} \cup tWt^{-1}$ . Then $V_{Q,M}$ is isomorphic to the free product $K_Q \ast T_W$ and the complement of $V_{Q,W}$ in $R(M_{Q,W})$ is an ideal of $R(M_{Q,W})$ .

5. (v) The group of units $U(M_{Q,W})$ of $M_{Q,W}$ is isomorphic to the free product $ K_Q \ast H_{W'}, $ where $H_{W'}$ is the subgroup of $K_Q$ generated by the subset $W'$ of W defined by

   $$\begin{align*}W' = \{ w_l \in W: tw_lt^{-1} \ \mbox{is invertible in} \; M_{Q,W} \}. \end{align*}$$
   In particular, if $W = W^{-1}$ , then $W'=W$ , and so $U(M_{Q,W}) \cong K_Q \ast H_W$ .

6. (vi) If $R(M_{Q,W})$ is finitely presented, then $K_Q$ and $T_W$ are both finitely presented.

Proof. (i) is obvious since they both have $|I|$ defining relations, and (ii) is [Reference Gray6, Theorem 3.8].

(iii) By [Reference Margolis and Meakin21, Lemma 1.5], since $M_{Q,W}$ is E-unitary, it follows that the canonical homomorphism $\theta : M_{Q,W} \rightarrow G_Q=K_Q\ast F_t$ from $M_{Q,W}$ onto its maximal group image (see (M1)) induces an embedding of each $\mathscr {R}$ -class of M into $G_Q$ . In particular, $\theta $ induces an embedding of the right units $R(M_{Q,W})$ into $G_Q$ . By the argument given in the proof of [Reference Ivanov, Margolis and Meakin12, Proposition 4.2], it follows that $R(M_{Q,W})$ is generated by the prefixes of the defining relators in the presentation (30) of $M_{Q,W}$ . Note that in [Reference Ivanov, Margolis and Meakin12, Proposition 4.2], an assumption is made that the defining relators are all cyclically reduced words, but this hypothesis is not used in the proof, and so the statement holds with that assumption removed (cf. Theorem 1.3).

This implies that $R(M_{Q,W})$ is isomorphic to the submonoid of $G_Q$ generated by the prefixes of the defining relators in the presentation (30). We claim that this is equal to the submonoid of $G_Q$ generated by the set

$$\begin{align*}Y = A \cup A^{-1} \cup \{t \} \cup \{ tw_l t^{-1}: l \in [k] \}. \end{align*}$$

Indeed, we have already observed that all these words represent right invertible elements (see (M3)). Furthermore, all the prefixes of relators in (30) are equal in $M_{Q,W}$ to products of those words. This is immediate for the prefixes of $r_i$ , $a_ja_j^{-1}$ , $a_j^{-1}a_j$ , as they are products of generators from A. The proper prefixes of $tw_lt^{-1}$ are products of generators from $A\cup \{t\}$ . Finally, longer prefixes of $tw_lt^{-1}tw_l^{-1}t^{-1}$ are equal in $M_{Q,W}$ to prefixes of $tw_lt^{-1}$ by Lemma 2.2(i). This completes the proof of the claim that $R(M_{Q,W})$ is isomorphic to the submonoid of $G_Q$ generated by Y.

Since the submonoid of $G_Q$ generated by $A \cup A^{-1}$ is $K_Q$ , and the submonoid of $G_Q$ generated by $\{ tw_j t^{-1}: j \in [k] \}$ is $t T_W t^{-1}$ , this completes the proof of (iii).

(iv) As in the previous part, E-unitarity of $M_{Q,W}$ implies that $V_{Q,W}$ is isomorphic to the submonoid of $G_Q$ generated by $K_Q \cup t T_W t^{-1}$ . By Lemma 6.2, the submonoid of $K_Q \ast F_t$ generated by $K_Q \cup t K_Q t^{-1}$ is isomorphic to $K_Q \ast K_Q$ . Combining this fact with Lemma 6.1, we conclude that the submonoid of $K_Q \ast F_t$ generated by $K_Q \cup t T_W t^{-1}$ is isomorphic to $K_Q \ast T_W$ . Hence, we have shown that $V_{Q,W}$ is isomorphic to $K_Q \ast T_W$ .

To see that $R(M_{Q,W}) \setminus V_{Q,W}$ is an ideal in $R(M_{Q,W})$ , it suffices to observe that under the natural epimorphism from $M_{Q,W}$ onto the bicyclic monoid B (see (M4)), the submonoid $R(M_{Q,W})$ is mapped onto $R'=\{ b^i\::\: i\in {\mathbb {N}}_0\}$ , while $R(M_{Q,W}) \setminus V_{Q,W}$ is mapped onto $V'=\{ b^i\::\: i\in {\mathbb {N}}\}$ , and that $V'$ is an ideal of $R'$ . Since the preimage of an ideal, with respect to a surjective homomorphism, is itself an ideal, this completes the proof that the complement of $V_{Q,W}$ in $R(M_{Q,W})$ is an ideal of $R(M_{Q,W})$ .

(v) Observe that $U(M_{Q,W})$ is contained in $R(M_{Q,W})$ and the complement $R(M_{Q,W}) \setminus U(M_{Q,W})$ is an ideal of the monoid $R(M_{Q,W})$ . Also, it follows from the proof of part (iii) that $R(M_{Q,W})$ is the submonoid of $M_{Q,W}$ generated by $\{t\} \cup A \cup A^{-1} \cup tWt^{-1}$ . Since $R(M_{Q,W}) \setminus U(M_{Q,W})$ is an ideal of the monoid $R(M_{Q,W})$ , it follows that

$$\begin{align*}Z=(\{t\} \cup A \cup A^{-1} \cup tWt^{-1}) \cap U(M_{Q,W}) \end{align*}$$

is a monoid generating set for $U(M_{Q,W})$ (this follows from the more general fact [Reference Gray6, Lemma 3.5]). By (M5), t is not invertible in $M_{Q,W}$ and hence $t \not \in Z$ . By (M3), $A \cup A^{-1} \subseteq Z$ . The remaining elements of Z are those from the set $tWt^{-1} \cap U(M_{Q,W})$ which is by definition equal to the set $tW't^{-1}$ , where

$$\begin{align*}W' = \{ w_l \in W: tw_lt^{-1} \ \mbox{is invertible in} \; M_{Q,W} \}. \end{align*}$$

This proves that the group of units $U(M_{Q,W})$ is isomorphic to the submonoid of $R(M_{Q,W})$ generated by

$$\begin{align*}Z = A \cup A^{-1} \cup tW't^{-1}. \end{align*}$$

It follows that the image of $U(M_{Q,W})$ under the isomorphism from (iii) is the submonoid of $G_Q = K_Q\ast F_t$ generated by the image of Z under the isomorphism from (iii). Since the submonoid of $K_Q\ast F_t$ generated by $A \cup A^{-1}$ is $K_Q$ , it follows that the image of $U(M_{Q,W})$ under the isomorphism from (iii) is precisely the submonoid of $K_Q \ast F_t$ generated by $K_Q\cup tW't^{-1}$ . Since $U(M_{Q,W})$ is a group, this must also be equal to the subgroup of $K_Q \ast F_t$ generated by $K_Q\cup tW't^{-1}$ . Under the isomorphism from (iv), this corresponds to $K_Q\ast H_{W'}$ , proving the first assertion. For the second assertion, observe that if $W=W^{-1}$ then $W'=W$ immediately from the presentation (30) for $M_{Q,W}$ .

(vi) If $R(M_{Q,W})$ is finitely presented, then by part (iv), it follows that $V_{Q,W}$ is finitely presented since its complement is an ideal. The fact that finite presentability is inherited by submonoids with ideal complement is well-known, for example, it is a corollary of [Reference Gray and Ruškuc8, Theorem B]. Therefore, $K_Q \ast T_W$ is finitely presented, which implies that $K_Q$ and $T_W$ are both finitely presented, being retracts of $K_Q \ast T_W$ . Here, we have used the fact that any retract of a finitely presented monoid is again finitely presented. This follows from the proof of [Reference Wang and Pride26, Theorem 3.4] (see, in particular, the remark in [Reference Wang and Pride26] immediately after the proof of Theorem 3.4 of that paper).