#  On groups of units of special and
one-relator inverse monoids

ROBERT D. GRAY<EMAIL_ADDRESS>School of Mathematics, University of
East Anglia, Norwich NR4 7TJ, England, UK  and  NIK RUŠKUC  nik.ruskuc@st-
andrews.ac.uk School of Mathematics and Statistics, University of St Andrews,
St Andrews KY16 9SS, Scotland, UK.

###### Abstract.

We investigate the groups of units of one-relator and special inverse monoids.
These are inverse monoids which are defined by presentations where all the
defining relations are of the form $r=1$. We develop new approaches for
finding presentations for the group of units of a special inverse monoid, and
apply these methods to give conditions under which the group admits a
presentation with the same number of defining relations as the monoid. In
particular our results give sufficient conditions for the group of units of a
one-relator inverse monoid to be a one-relator group. When these conditions
are satisfied these results give inverse semigroup theoretic analogues of
classical results of Adjan for one-relator monoids, and Makanin for special
monoids. In contrast, we show that in general these classical results to not
hold for one-relator and special inverse monoids. In particular, we show that
there exists a one-relator special inverse monoid whose group of units is not
a one-relator group (with respect to any generating set), and we show that
there exists a finitely presented special inverse monoid whose group of units
is not finitely presented. We also apply these results to establish a close
connection between the question of finite presentability of the groups of
units of special one-relator inverse monoids, and the open problem of whether
all one-relator groups are coherent. In addition, we give a new approach via
regular languages for computing invertible pieces of relators in special
inverse monoids. We prove that this algorithm outperforms the classical Adjan
overlap algorithm when applied to special inverse monoids, in the sense that
it discovers more invertible pieces of relators.

###### Key words and phrases:

One-relator monoid, one-relator group, inverse monoid, special inverse monoid,
units, right units, coherence.
This research of R. D. Gray was supported by the EPSRC grant EP/N033353/1
“Special inverse monoids: subgroups, structure, geometry, rewriting systems
and the word problem”.

###### 2010 Mathematics Subject Classification:

Primary 20F05; Secondary 20M18, 20M05

##  1\. Introduction and summary of results

The purpose of this paper is to undertake a systematic investigation into the
groups of units of one-relator and special inverse monoids. Throughout there
is a particular emphasis on comparing and contrasting these groups with groups
of units of special monoids, after the work of Adjan, Makanin, Lallement and
Zhang, as well as with one-relator groups themselves; see [1, 12, 18, 28].

The word problem for semigroups defined by a single relation is one of the
oldest, most famous and most elementary to state open problems in the broad
area of combinatorial algebra. It asks whether for every monoid of the form
$M=\operatorname{Mon}\bigl{\langle}A\>|\>u=v\bigr{\rangle}$, i.e. defined by
generators $A$ and a single defining relation $u=v$, there is an algorithm
which for any two words $w_{1},w_{2}\in A^{\ast}$ decides whether or not
$w_{1}=w_{2}$ in $M$. In a seminal paper on the subject [1], Adjan proves,
among other things, the following:

  1. (A1)

The word problem is soluble for every _one-relator_ special monoid, i.e.
monoid defined by $M=\operatorname{Mon}\bigl{\langle}A\>|\>r=1\bigr{\rangle}$.

  2. (A2)

The word problem is soluble for every monoid of the form
$M=\operatorname{Mon}\bigl{\langle}A\>|\>u=v\bigr{\rangle}$, where $u,v$ are
non-empty words whose first letters are distinct and last letters are
distinct.

  3. (A3)

If the word problem is soluble for all monoids of the form
$M=\operatorname{Mon}\bigl{\langle}A\>|\>au=av\bigr{\rangle}$ where $a\in A$,
and the final letters of $u$ and $v$ are distinct, then the word problem for
_all_ one relation monoids is soluble.

Adjan’s proof of (A1) and some subsequent developments are of particular
relevance for our work, and we outline them here. The key feature is a focus
on the group of units. Specifically, suppose $r$ is decomposed as $r\equiv
r_{1}\dots r_{k}$, where $r_{i}$ are non-empty and invertible and of shortest
possible length subject to this requirement; we will call such $r_{i}$ the
_minimal invertible pieces_ of $r$. Then the following holds:

######  Theorem 1.1 (Adjan [1]).

If $M=\operatorname{Mon}\bigl{\langle}A\>|\>r=1\bigr{\rangle}$, and if
$r=r_{1}\dots r_{k}$ is the decomposition into minimal invertible pieces, then
the group of units $U=U(M)$ of $M$ is generated by $\\{r_{1},\dots,r_{k}\\}$.
Furthermore, if $B$ is an alphabet in one-one correspondence
$r_{i}\mapsto\overline{r}_{i}$ with the set $\\{r_{1},\dots,r_{k}\\}$, then
the group presentation
$\operatorname{Gp}\bigl{\langle}B\>|\>\overline{r}_{1}\dots\overline{r}_{n}=1\bigr{\rangle}$
defines $U$ with respect to this generating set.

It follows then that the group of units of $M$ is a one-relator group, and
hence has a soluble word problem by a classical result of Magnus; see [16,
17]. It can be shown that the submonoid of right units $R$ of $M$ is the free
product of $U$ and a free monoid of finite rank, and hence it is also finitely
presented and has a soluble word problem. A further normal form theorem can be
proved that reduces the word problem for the entire monoid $M$ to those of $U$
and $R$, and thus $M$ has a soluble word problem too.

Makanin [18] generalises this approach to special monoids, i.e. monoids
defined by presentations of the form
$M=\operatorname{Mon}\bigl{\langle}A\>|\>r_{i}=1\ (i\in I)\bigr{\rangle}$.
This time we decompose each $r_{i}$ into minimal invertible pieces
$r_{i}\equiv r_{i1}\dots r_{ik_{i}}$. Furthermore, we assign to each piece
$r_{ij}$ a new letter $\overline{r}_{ij}$, but this time in such a way that
$\overline{r}_{ij}=\overline{r}_{lm}$ whenever $r_{ij}=r_{lm}$ _in the monoid_
$M$. Collecting these new letters into the alphabet $B$ we have:

######  Theorem 1.2 (Makanin [18]).

The group of units of $M=\operatorname{Mon}\bigl{\langle}A\>|\>r_{i}=1\ (i\in
I)\bigr{\rangle}$ is generated by the set $\\{r_{ij}\>:\>i\in I,\ 1\leq j\leq
k_{i}\\}$, and, in terms of these generators, is defined by the presentation
$\operatorname{Gp}\bigl{\langle}B\>|\>\overline{r}_{i1}\dots\overline{r}_{ik_{i}}=1\
(i\in I)\bigr{\rangle}$.

It follows that the group of units of a special monoid can be defined by a
presentation with no more defining relations than the original presentation
for $M$.

A key property of the decompositions into minimal invertible pieces is that
they do not overlap with each other. This in fact yields an algorithm for
computing the decomposition into minimal invertible pieces for one-relator
monoids; see Lallement [12]. The algorithm proceeds by finding the overlaps of
$r$ with itself, forming certain cyclic conjugates of $r$, and then repeating
this process. This algorithm also makes sense in the context of special
monoids too, and it computes some decomposition of the relators into
invertible pieces. It turns out, however, that these pieces need not be
minimal in general (see Example 4.2). All the results surveyed above were
revisited and simplified by Zhang [28, 29] using the methodology of string
rewriting systems.

In a separate strand, the 1990s and early 2000s saw a dynamic development of
the theory of presentations for inverse monoids. The catalyst for this was
Stephen’s discovery [24] of an algorithmic procedure, akin to the Todd–Coxeter
algorithm from combinatorial group theory, which computes the so called
Schützenberger graph of an inverse monoid
$M=\operatorname{Inv}\bigl{\langle}A\>|\>R\bigr{\rangle}$ based at an
arbitrary word $w\in\overline{A}^{\ast}$. Linking this development with (A3),
Ivanov, Margolis and Meakin [11] showed that if all one-relator inverse
monoids $\operatorname{Inv}\bigl{\langle}A\>|\>r=1\bigr{\rangle}$, where $r$
is a reduced word, have soluble word problems then this would imply the same
for the monoids of the form
$M=\operatorname{Mon}\bigl{\langle}A\>|\>au=av\bigr{\rangle}$, and hence for
all one-relation monoids. Relating to this, it was recently shown in [5] that,
in general, not every one-relator inverse monoid
$\operatorname{Inv}\bigl{\langle}A\>|\>r=1\bigr{\rangle}$ has soluble word
problem. However the question of solubility of the word problem in the case
that $r$ is a reduced word is still open. In their paper [11] Ivanov, Margolis
and Meakin also essentially proved the generation part of the analogue of
Theorem 1.2 for special inverse monoids:

######  Theorem 1.3 (Ivanov, Margolis, Meakin [11, Proposition 4.2]).

Suppose

$M=\operatorname{Inv}\bigl{\langle}A\>|\>r_{i}=1\ (i\in I)\bigr{\rangle}$

is a special inverse monoid, and that each relator $r_{i}$ is decomposed into
minimal invertible pieces $r_{i}\equiv r_{i1}\dots r_{ik_{i}}$. Then the set
$\\{r_{ij}\>:\>i\in I,\ 1\leq j\leq k_{i}\\}$ generates the group of units of
$M$.

###### Proof.

The authors state their theorem under the assumption that all $r_{i}$ are
cyclically reduced words. However, on inspection, this condition is not used
in the proof, and hence their proof in fact establishes the theorem as stated
here. ∎

However, there has been no further development along the Adjan/Makanin/Zhang
lines, toward establishing presentation properties of the group of units. In
fact, partly to hint at the difficulties that such an attempt would entail,
Margolis, Meakin and Stephen [20] introduce the following specific one-relator
monoid

$\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},$

which has since come to be known as the O’Hare monoid. It is defined by a
single, positive relator $r$ (and hence, in particular, it is $E$-unitary).
The relator has no overlaps with itself, so the Adjan overlap algorithm would
terminate instantly, and return $r$ as a single invertible piece of itself.
However, using van Kampen diagrams and Stephen’s procedure, Margolis and
Meakin succeed in showing that $r$ in fact has a finer decomposition, namely

$r\equiv abcd\cdot acd\cdot ad\cdot abbcd\cdot acd.$

They provide no further information about the group of units.

Motivated by the developments described above, in this paper we investigate
the extent to which the Adjan/Makanin/Zhang results for groups of units, and
monoids of right units, of one-relator and special monoids are also valid for
one-relator and special inverse monoids. In particular, we consider the
question of whether the group of units of a one-relator inverse monoid is a
one-relator group. In the positive direction, in Section 3 we prove the
following general sufficient condition for this to be the case:

######  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_{i1}r_{i2}\ldots r_{ik_{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

$K=\operatorname{Gp}\bigl{\langle}Y\>|\>\phi^{-1}(r_{i1})\iota^{-1}(r_{i2})\ldots\phi^{-1}(r_{ik_{i}})=1\;(i\in
I)\bigr{\rangle}.$

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.

We note that this result is valid for special inverse monoids in general, and
that it enables one to reduce the original question to a question purely
referring to the corresponding groups and their subgroups. In particular, our
questions concerning one-relator inverse monoids are reduced to questions
about subgroups of one-relator groups. We therefore go on to prove a number of
results in which we identify situations where the conditions of the theorem
are met. As a consequence, in Section 5 we exhibit several families of one-
relator inverse monoids whose groups of units are all one-relator. In
particular, we are able to prove that the group of units of the O’Hare monoid
$\mathcal{O}$ is the free group of rank $2$.

It is natural to ask whether the assumptions of Theorem 3.1 are perhaps always
satisfied, or at least always in the case of one-relator presentations. The
answer to this is negative, and in order to show this we give a general
construction in Section 6 which we then apply in Section 7 to demonstrate the
following:

  * •

There exists a one-relator special inverse monoid whose group of units is not
one-relator (with respect to any generating set).

  * •

There exists a finitely presented special inverse monoid whose group of units
is not finitely presented.

  * •

There exists a one-relator special inverse monoid with finitely presented
group of units, and finitely generated but non-finitely presented submonoid of
right units.

  * •

There exists a one-relator special inverse monoid whose submonoid of right
units is not a free product of the groups of units and a free monoid (this
follows from the previous point).

Also, using these results, at the end of Section 7 we will present several
results which show the close relationship between the question of finite
presentability of the groups of units units of special one-relator inverse
monoids, and an open problem of Baumslag [2, page 76] which asks whether every
one-relator group is coherent. In particular we show that the problem of
proving coherence of all one-relator groups is equivalent to the problem of
showing that the group of units of an $E$-unitary one-relator special inverse
monoid is always finitely presented.

Throughout the paper, the decompositions of relators into invertible pieces
play a pivotal role, and we discuss them in their own right in Section 4. We
show that, unlike the situation in one-relator monoids, for general special
monoids there is no algorithm to compute the decomposition into minimal
invertible pieces. The existence of such an algorithm for one-relator special
inverse monoids remains open. However, we present an algorithm which does
compute a decomposition into invertible pieces. The decomposition computed by
this algorithm is always at least as fine as that computed by the Adjan
overlap algorithm, and, in fact, in all the examples known to us in the one-
relator case, including the O’Hare monoid $\mathcal{O}$, it computes the
decomposition into minimal invertible pieces.

##  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, i.e. 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, i.e.
$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}$, i.e. words containing no subword
of the form $aa^{-1}$ with $a\in\overline{A}$, under multiplication $u\cdot
v=\operatorname{red}(uv)$. Here $\operatorname{red}(u)$ denotes the _free
reduction_ of $u$, i.e. 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{red}_{A}$
for $\operatorname{red}$ when we want to work with free reductions over
different alphabets. We will also extend the use of $\operatorname{red}$ to
apply to sets of words:
$\operatorname{red}(W)=\\{\operatorname{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

$\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}.$

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 (resp. inverse submonoid,
subgroup) that $X$ generates by
$\operatorname{Mon}\bigl{\langle}X\bigr{\rangle}$ (resp.
$\operatorname{Inv}\bigl{\langle}X\bigr{\rangle}$,
$\operatorname{Gp}\bigl{\langle}X\bigr{\rangle}$).

For a word $w\in A^{*}$ we use $\operatorname{pref}(w)$ to denote the set of
all prefixes of $w$, and $\operatorname{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

$\operatorname{Inv}\bigl{\langle}A\>|\>r_{i}=1\ (i\in I)\bigr{\rangle}.$

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

$r_{i}\equiv r_{i}^{\prime}(p_{1},\ldots,p_{k})\ (i=1,\ldots,n).$

For $i\in I$ by the _decomposition into minimal invertible pieces_ we mean the
unique factorisation

$r_{i}\equiv r_{i1}r_{i2}\ldots r_{ik_{i}}$

with the property that each $r_{ij}$ is a non-empty word in $\overline{A}^{*}$
which represents an invertible element of $M$ and which has no proper non-
empty 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 [5,
Lemma 3.1, Corollary 3.2]:

######  Lemma 2.2.

The following hold for any inverse monoid $M$:

  1. (i)

If $s,x\in M$ are such that $sx$ is right invertible then $sxx^{-1}=s$.

  2. (ii)

If $s,t,x\in M$ are such that $sxx^{-1}t$ is right invertible then
$sxx^{-1}t=st$.

  3. (iii)

If $M=\operatorname{Inv}\bigl{\langle}A\bigr{\rangle}$ and
$w\in\overline{A}^{\ast}$ represents a right invertible element in $M$ then
$w=\operatorname{red}(w)$ in $M$.

##  3\. Makanin-style presentation theorems for special inverse monoids

As discussed in the introduction, given a special inverse monoid
$M=\operatorname{Inv}\bigl{\langle}A\>|\>r_{i}=1\ (i\in 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

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

The minimal invertible pieces are $a$, $bc^{2}b^{-1}$, $bc^{3}b^{-1}$. Indeed,
the words $a$, $bc^{2}b^{-1}$ and $bc^{3}b^{-1}$ are clearly invertible in
$M$. 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^{2}b^{-1}$
is, it follows that $bc$ is not invertible. Similarly, $bc^{2}$ and $bc^{3}$
are not invertible. Replacing these pieces by letters $x,y,z$ respectively
yields the presentation
$\operatorname{Gp}\bigl{\langle}x,y,z\>|\>xyxzxyx=1\bigr{\rangle}=F_{x,y}$. In
the monoid $M$ we have

$bcb^{-1}=(bc^{3}b^{-1})(bc^{2}b^{-1})^{-1},$

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^{2}xt^{3}xt^{2}x=1$. Since $U$ is not free with respect to $\\{x,t\\}$ and
$G$ is free of rank $2$ it follows that $U\not\cong M$. In fact, $U$ is
defined by the presentation
$\operatorname{Gp}\bigl{\langle}x,t\>|\>xt^{2}xt^{3}xt^{2}x=1\bigr{\rangle}$.
This will follow from the more general results we will prove below (see
Corollary 3.12). A key feature of this example is that
$\\{a,bc^{2}b^{-1},bc^{3}b^{-1}\\}$ is not a basis for
$\operatorname{Gp}\bigl{\langle}a,bc^{2}b^{-1},bc^{3}b^{-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_{i1}r_{i2}\ldots r_{ik_{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

$K=\operatorname{Gp}\bigl{\langle}Y\>|\>\phi^{-1}(r_{i1})\iota^{-1}(r_{i2})\ldots\phi^{-1}(r_{ik_{i}})=1\;(i\in
I)\bigr{\rangle}.$

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.

${\overline{A}^{\ast}}$${F_{A}}$${\begin{array}[]{c}H=\operatorname{Gp}\bigl{\langle}\operatorname{red}(r_{ij})\bigr{\rangle}\\\
=\operatorname{Gp}\bigl{\langle}s_{l}\bigr{\rangle}\end{array}}$${F_{Y}}$${\begin{array}[]{cc}M\\\
=\operatorname{Inv}\bigl{\langle}A\>|\>r_{i}=1\bigr{\rangle}\end{array}}$${\begin{array}[]{c}G\\\
=\operatorname{Gp}\bigl{\langle}A\>|\>r_{i}=1\bigr{\rangle}\end{array}}$${\widetilde{H}}$${\begin{array}[]{c}K\\\
=\operatorname{Gp}\bigl{\langle}Y\>|\>r_{i}^{\prime}=1\bigr{\rangle}\end{array}}$${\begin{array}[]{c}U\\\
=\operatorname{Inv}\bigl{\langle}\pi_{M}(r_{ij})\bigr{\rangle}\\\
=\operatorname{Inv}\bigl{\langle}\pi_{M}(s_{l})\bigr{\rangle}\end{array}}$$\scriptstyle{\operatorname{red}}$$\scriptstyle{\pi_{M}}$$\scriptstyle{\pi_{G}}$$\scriptstyle{\supseteq}$$\scriptstyle{\supseteq}$$\scriptstyle{\pi_{G}\\!\restriction_{H}}$$\scriptstyle{\pi_{K}}$$\scriptstyle{\phi}$$\scriptstyle{\psi}$$\scriptstyle{\supseteq}$$\scriptstyle{\zeta}$$\scriptstyle{\eta}$

$\scriptstyle\subseteq$

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$.

###### 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.

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{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

$\psi\pi_{M}=\pi_{G}\operatorname{red}.$ (1)

Next, let

$H=\operatorname{Gp}\bigl{\langle}\\{\operatorname{red}(r_{ij})\>:\>i\in I,\
1\leq j\leq k_{i}\\}\bigr{\rangle}\leq F_{A},$

and let

$\widetilde{H}=\pi_{G}(H)\leq G.$

As a subgroup of a free group, $H$ itself must be free, i.e. $H\cong F_{Y}$
for some alphabet $Y=\\{y_{l}\>:\>l\in L\\}$ as in the statement, with an
isomorphism

$\phi:F_{Y}\rightarrow H,\ y_{l}\mapsto s_{l}\ (l\in L).$ (2)

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

$\phi(r_{ij}^{\prime})\equiv\operatorname{red}(r_{ij})\ (i\in I,\ 1\leq j\leq
k_{i}).$ (3)

Let

$r_{i}^{\prime}\equiv\operatorname{red}_{Y}(r_{i1}^{\prime}r_{i2}^{\prime}\dots
r_{ik_{i}}^{\prime})\in F_{Y}\subseteq\overline{Y}^{\ast},$ (4)

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

$K=\operatorname{Gp}\bigl{\langle}Y\>|\>r_{i}^{\prime}=1\;(i\in
I)\bigr{\rangle}=\operatorname{Gp}\bigl{\langle}Y\>|\>\phi^{-1}(r_{i1})\phi^{-1}(r_{i2})\ldots\phi^{-1}(r_{ik_{i}})=1\;(i\in
I)\bigr{\rangle},$ (5)

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

$\displaystyle\pi_{G}\phi(r_{i}^{\prime})$
$\displaystyle=\pi_{G}\phi\operatorname{red}_{Y}(r_{i1}^{\prime}\dots
r_{ik_{i}}^{\prime})$ (by (4))
$\displaystyle=\pi_{G}(\phi(r_{1i}^{\prime})\dots\phi(r_{ik_{i}}^{\prime}))$
($\phi$ is a homomorphism)
$\displaystyle=\pi_{G}(\operatorname{red}(r_{i1})\dots\operatorname{red}(r_{ik_{i}}))$
(by (3)) $\displaystyle=\pi_{G}\operatorname{red}(r_{i1}\dots r_{ik_{i}})$
($\operatorname{red}$ is a homomorphism)
$\displaystyle=\pi_{G}\operatorname{red}(r)=1.$

Therefore, there exists an epimorphism

$\zeta:K\rightarrow\overline{H},\ \pi_{K}(y_{l})\mapsto\pi_{G}(s_{l})\ (l\in
L).$ (6)

To complete the set-up, we turn our attention to the group of units $U$ of
$M$. We know from Lemma 1.3 that it is generated by
$\\{\pi_{M}(r_{ij})\>:\>i\in I,\ 1\leq j\leq k_{i}\\}$. We claim that

$\pi_{M}(s_{l})\in U\quad\text{for all }l\in L.$ (7)

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

$s_{l}\equiv\operatorname{red}(\operatorname{red}(r_{i_{1}j_{1}})^{\epsilon_{1}}\dots\operatorname{red}(r_{i_{m}j_{m}})^{\epsilon_{m}})\equiv\operatorname{red}(r_{i_{1}j_{1}}^{\epsilon_{1}}\dots
r_{i_{m}j_{m}}^{\epsilon_{m}}).$

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

$\displaystyle U$
$\displaystyle\ni\pi_{M}(r_{i_{1}j_{1}})^{\epsilon_{1}}\dots\pi_{M}(r_{i_{m}j_{m}})^{\epsilon_{m}}$
$\displaystyle=\pi_{M}(r_{i_{1}j_{1}}^{\epsilon_{1}}\dots
r_{i_{m}}^{\epsilon_{m}j_{m}})$ ($\pi_{M}$ is a homomorphism)
$\displaystyle=\pi_{M}(\operatorname{red}(r_{i_{1}j_{1}}^{\epsilon_{1}}\dots
r_{i_{m}j_{m}}^{\epsilon_{m}}))$ (by Lemma 2.2(iii))
$\displaystyle=\pi_{M}(s_{l}),$

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{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

$\displaystyle\pi_{M}\phi(r_{i}^{\prime})$
$\displaystyle=\pi_{M}\phi\operatorname{red}_{Y}(r_{i1}^{\prime}\dots
r_{ik_{i}}^{\prime})$ (by (4))
$\displaystyle=\pi_{M}(\phi(r_{i1}^{\prime})\dots\phi(r_{ik_{i}}^{\prime}))$
($\phi$ is a homomorphism)
$\displaystyle=\pi_{M}(\operatorname{red}(r_{i1})\dots\operatorname{red}(r_{ik_{i}}))$
(by (3))
$\displaystyle=\pi_{M}\operatorname{red}(r_{i1})\dots\pi_{M}\operatorname{red}(r_{ik_{i}})$
($\pi_{M}$ is a homomorphism)
$\displaystyle=\pi_{M}(r_{i1})\dots\pi_{M}(r_{ik_{i}})$ (by Lemma 2.2(iii))
$\displaystyle=\pi_{M}(r_{i1}\dots r_{ik_{i}})$ ($\pi_{M}$ is a homomorphism)
$\displaystyle=\pi_{M}(r)=1.$

Therefore, there exists an epimorphism

$\eta:K\rightarrow U,\ \pi_{K}(y_{l})\mapsto\pi_{M}(s_{l})\ (l\in L).$ (8)

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:

$\displaystyle\eta\zeta^{-1}\psi\\!\restriction_{U}\pi_{M}(s_{l})$
$\displaystyle=\eta\zeta^{-1}\pi_{G}\operatorname{red}(s_{l})$ (by (1))
$\displaystyle=\eta\zeta^{-1}\pi_{G}(s_{l})$ ($s_{l}$ is reduced)
$\displaystyle=\eta\pi_{K}(y_{l})$ (by (6)) $\displaystyle=\pi_{M}(s_{l})$
$\displaystyle\text{(by \eqref{eq13})},$

and

$\displaystyle\zeta^{-1}\psi\\!\restriction_{U}\eta\pi_{K}(y_{l})$
$\displaystyle=\zeta^{-1}\psi\pi_{M}(s_{l})$ (by (8))
$\displaystyle=\zeta^{-1}\pi_{G}\operatorname{red}(s_{l})$ (by (1))
$\displaystyle=\zeta^{-1}\pi_{G}(s_{l})$ ($s_{l}$ is reduced)
$\displaystyle=\pi_{K}(y_{l})$ $\displaystyle\text{(by \eqref{eq4})},$

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_{i1}r_{i2}\ldots r_{ik_{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 pre-image $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

$M=\operatorname{Inv}\bigl{\langle}A\>|\>r_{i}=1\ (i\in
I)\bigr{\rangle}=\operatorname{Inv}\bigl{\langle}A\>|\>\pi(r_{i1}^{\prime})\ldots\pi(r_{ik_{i}}^{\prime})=1\
(i\in I)\bigr{\rangle}$ (9)

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

###### Proof.

Denoting by $\operatorname{red}_{A}$ the free reduction over the alphabet $A$,
we have

$\operatorname{red}_{A}\pi(w)\equiv\phi(w)\quad\text{for all
}w\in\overline{Y}^{\ast},$

and, in particular,

$\operatorname{red}_{A}\pi(r_{ij}^{\prime})\equiv r_{ij}\quad(i\in I,\ 1\leq
j\leq k_{i})$ (10)

because all $r_{ij}$ are reduced.

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

$\displaystyle\pi_{M}(\pi(r_{i1}^{\prime})\dots\pi(r_{ik_{i}}^{\prime}))$
$\displaystyle=\pi_{M}(\operatorname{red}_{A}\pi(r_{i1}^{\prime})\dots\operatorname{red}_{A}\pi(r_{ik_{i}}^{\prime}))$
(by Lemma Lemma 2.2(iii)) $\displaystyle=\pi_{M}(r_{i1}\dots r_{ik_{i}})$ (by
(10)) $\displaystyle=\pi_{M}(r_{i})=1_{M}.$

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_{i1}^{\prime})\ldots\pi(r_{ik_{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

$\displaystyle 1_{M^{\prime}}$
$\displaystyle=\pi_{M^{\prime}}(\pi(r_{i1}^{\prime})\dots\pi(r_{ik_{i}}^{\prime}))$
$\displaystyle=\pi_{M^{\prime}}(\operatorname{red}_{A}\pi(r_{i1}^{\prime})\dots\operatorname{red}_{A}\pi(r_{ik_{i}}^{\prime}))$
(by Lemma 2.2(iii)) $\displaystyle=\pi_{M^{\prime}}(r_{i1}\dots r_{ik_{i}})$
(by (10)) $\displaystyle=\pi_{M^{\prime}}(r_{i}).$

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

$\pi(y)\equiv\operatorname{red}_{A}(r_{i_{1}j_{1}}\dots r_{i_{k}j_{k}}).$ (11)

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

$\pi_{M}(r_{i_{1}j_{1}}\dots
r_{i_{k}j_{k}})=\pi_{M}\operatorname{red}_{A}(r_{i_{1}j_{1}}\dots
r_{i_{k}j_{k}}).$ (12)

Combining (11) and (12) we obtain:

$\pi_{M}\pi(y)=\pi_{M}\operatorname{red}_{A}(r_{i_{1}j_{1}}\dots
r_{i_{k}j_{k}})=\pi_{M}(r_{i_{1}j_{1}}\dots
r_{i_{k}j_{k}})=\pi_{M}(r_{i_{1}j_{1}})\dots\pi_{M}(r_{i_{k}j_{k}}),$

which is clearly a unit.

Finally, since each relator
$\pi(r_{i1}^{\prime})\ldots\pi(r_{ik_{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_{i1}^{\prime})\ldots\pi(r_{ik_{i}}^{\prime})=1\;(i\in
I)\bigr{\rangle}$. ∎

######  Remark 3.3.

In the statement of Theorem 3.2, some $\pi(y)$ may actually not occur in
$\pi(r_{i1}^{\prime})\ldots\pi(r_{ik_{i}}^{\prime})$. Also, we note that the
assumptions in Theorem 3.2 can be weakened a little further: instead of the
original pieces being reduced, one could require that $r_{ij}$ can be obtained
from $\pi(r_{ij}^{\prime})$ by using reductions.

######  Remark 3.4.

The statement of Theorem 3.2 is technical. Expressed in a slightly less
technical way it tells us that given
$M=\operatorname{Inv}\bigl{\langle}A\>|\>r_{i}=1\;(i\in I)\bigr{\rangle}$,
then for any basis $B\subseteq F_{A}$ of the subgroup of $F_{A}$ generated by
the minimal invertible pieces of the relators of this presentation, there is a
presentation $\operatorname{Inv}\bigl{\langle}A\>|\>s_{i}=1\;(i\in
I)\bigr{\rangle}$ for $M$ for which $B$ is a set of invertible pieces and also
generates the group of units of $M$. As we shall see below, changing the
presentation for $M$ in this way will often be a useful first step when
analysing examples.

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.5.

A finite set of words $w_{1},\ldots,w_{k}\in\overline{A}^{*}$ is _free for
substitution in a group presentation_

$\operatorname{Gp}\bigl{\langle}x_{1},\dots,x_{k}\>|\>r_{i}(x_{1},\ldots,x_{k})=1\
(i\in I)\bigr{\rangle}$

if the subgroup of

$\operatorname{Gp}\bigl{\langle}A\>|\>r_{i}(w_{1},\ldots,w_{k})=1\ (i\in
I)\bigr{\rangle}$

generated by $w_{1},\ldots,w_{k}$ is isomorphic to
$\operatorname{Gp}\bigl{\langle}X\>|\>r_{i}(x_{1},\ldots,x_{k})=1\ (i\in
I)\bigr{\rangle}$ via the map $x_{i}\mapsto w_{i}$.

######  Corollary 3.6.

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

$U=\operatorname{Gp}\bigl{\langle}x_{1},\dots,x_{n}\>|\>r^{\prime}(r_{1}^{\prime},\dots,r_{k}^{\prime})=1\bigr{\rangle}.$

###### Proof.

This follows immediately from Definition 3.5 and Theorem 3.1. ∎

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.7.

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

$A_{i}\not\subseteq\bigcup_{j\neq i}{A_{j}}\quad\text{for all }i=1,\ldots,n$

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:

######  Lemma 3.8.

If $G=\operatorname{Gp}\bigl{\langle}A\>|\>r_{1}=1,r_{2}=1\bigr{\rangle}$
where each $r_{i}$ is cyclically reduced and contains a letter $a_{i}$ not
contained by the other $r_{j}$, then the one-relator groups
$G_{1}=\operatorname{Gp}\bigl{\langle}A\setminus\\{a_{2}\\}\>|\>r_{1}=1\bigr{\rangle}$
and
$G_{2}=\operatorname{Gp}\bigl{\langle}A\setminus\\{a_{1}\\}\>|\>r_{2}=1\bigr{\rangle}$
both embed naturally into $G$.

###### Proof.

The subgroup of $G_{1}$ generated by $A\setminus\\{a_{1},a_{2}\\}$ is free on
that set by Freiheitsatz, 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

$\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}$

into which $G_{1}$ and $G_{2}$ will embed naturally. Now perform Tietze
transformations 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.9.

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

$A_{i}\not\subseteq\bigcup_{j\neq i}{A_{j}}\quad\text{for all }i=1,\ldots,n,$

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

$r\equiv x_{i_{1}}^{\alpha_{1}}x_{i_{2}}^{\alpha_{2}}\dots
x_{i_{k}}^{\alpha_{k}}$

where $i_{j}\in\\{1,\dots,n\\}$ and $\alpha_{j}\in\mathbb{Z}$ for
$j=1,\dots,k$, and

$i_{1}\neq i_{2}\neq i_{3}\dots\neq i_{k}\neq i_{1}.$

Consider the word

$r(p_{1},\dots,p_{n})\equiv p_{i_{1}}^{\alpha_{1}}p_{i_{2}}^{\alpha_{2}}\dots
p_{i_{k}}^{\alpha_{k}},$

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{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{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{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

$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}}.$

However, the words

$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}}$

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.7.

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

$G=\operatorname{Gp}\bigl{\langle}A\>|\>r(p_{1},\dots,p_{n})=1\bigr{\rangle}$
(13)

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.9 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}$:

$\displaystyle G$
$\displaystyle=\operatorname{Gp}\bigl{\langle}A,x_{n}\>|\>p_{n}x_{n}^{-1}=1,\
r(p_{1},\dots,p_{n-1},x_{n})=1\bigr{\rangle}$ (14)
$\displaystyle=\operatorname{Gp}\bigl{\langle}A,x_{n}\>|\>p_{n}x_{n}^{-1}=1,\
\overline{r}=1\bigr{\rangle},$ (15)

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

  * •

The word $p_{n}x_{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_{n}x_{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.9, but not in $p_{n}x_{n}^{-1}$.

By Lemma 3.8, the group

$\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}$
(16)

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:

######  Theorem 3.10.

Let $A=B\cup C$ where $B$ and $C$ are disjoint alphabets, and let
$p_{1},\dots,p_{n}\subseteq F_{A}$. Denoting by $c(p_{i})$ the set of letters
from $C$ that appear in $p_{i}$, suppose that there is a bijection
$\mu:\\{p_{1},\dots,p_{n}\\}\rightarrow C$ such that at least one of the
following two conditions holds for every $i=1,\dots,n$:

  1. (i)

$c(p_{i})=\\{\mu(p_{i})\\}$; or

  2. (ii)

$\mu(p_{i})$ occurs precisely once in $p_{i}$ and

$c(p_{i})\setminus\bigcup_{1\leq j\leq i-1}c(p_{j})=\\{\mu(p_{i})\\}.$

Then $p_{1},\dots,p_{m}$ are free for substitutions into arbitrary one-relator
presentations.

######  Remark 3.11.

Theorem 3.7 is indeed a special case of Theorem 3.10, corresponding to the
case where condition (i) is satisfied for every $i=1,\dots,n$.

###### Proof.

We may reorder $p_{1},\dots,p_{n}$ so that $p_{1},\dots,p_{m}$ satisfy (i) and
$p_{m+1},\dots p_{n}$ satisfy (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

$\operatorname{Gp}\bigl{\langle}A\>|\>r(p_{1},\dots,p_{n})=1\bigr{\rangle}$
(17)

generated by $p_{1},\dots,p_{n}$ is naturally isomorphic to
$\operatorname{Gp}\bigl{\langle}X\>|\>r=1\bigr{\rangle}$. To begin with, by
Theorem 3.7, the subgroup of

$\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}$

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

$\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}$
(18)

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 (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

$\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}$

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.12.

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.10 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

$\operatorname{Gp}\bigl{\langle}x_{1},\dots,x_{n}\>|\>r_{1}^{\prime}\dots
r_{k}^{\prime}=1\bigr{\rangle}.$

###### Proof.

This follows immediately from Theorem 3.10 and Corollary 3.6. ∎

As a special case of Theorem 3.10 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 [17]);

  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.10 or 3.7 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.

######  Theorem 3.13.

If $p_{1},\dots,p_{n}\in F_{A}$ satisfy any of (F1), (F2) or (F3) then
$\\{p_{1},\dots,p_{n}\\}$ is free for substitution into any presentation.

###### 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

$\operatorname{Gp}\bigl{\langle}A\>|\>r_{i}(p_{1},\dots,p_{n})=1\ (i\in
I)\bigr{\rangle}.$ (19)

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

$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}.$

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

$\displaystyle a$ $\displaystyle\mapsto a$ $\displaystyle(a\in
A_{1}\cup\dots\cup A_{k-1}\cup A^{\prime}),$ $\displaystyle x_{k}$
$\displaystyle\mapsto p_{k},$ $\displaystyle x_{j}$ $\displaystyle\mapsto
x_{j}$ $\displaystyle(j=k+1,\dots,n).$

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

$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}}$

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 [17, 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

$\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}.$

Eliminate $x_{k}$ using the last relation in this presentation, to obtain

$\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}.$

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

$p_{j}\equiv p_{j}^{\prime}a_{j}^{\epsilon_{j}}p_{j}^{\prime\prime},\quad
j=1,\dots,n,$

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

$\operatorname{Gp}\bigl{\langle}X\>|\>r_{i}(x_{1},\dots,x_{n})=1\ (i\in
I)\bigr{\rangle}$ (20)

naturally embeds into

$\operatorname{Gp}\bigl{\langle}A\>|\>r_{i}(p_{1},\dots,p_{n})=1\ (i\in
I)\bigr{\rangle}.$ (21)

It is clear that (20) embeds into

$\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}}.$ (22)

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:

$\displaystyle\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}$ $\displaystyle=$
$\displaystyle\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}.$

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.14.

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

$U=\operatorname{Gp}\bigl{\langle}x_{1},\dots,x_{n}\>|\>r_{i1}^{\prime}\dots
r_{ik_{i}}^{\prime}=1\ (i\in I)\bigr{\rangle}.$

###### Proof.

This analogous to Corollary 3.12. ∎

##  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, and modified by
Zhang. 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 [12], 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 [1] 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

  1. ($\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 non-empty (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 [12, 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 [12, p372] (with a
small correction we have made to a typo in (i) on [12, p372]).

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{pref}(u)$ and
$v\not\in\operatorname{suff}(u)$ for all $v\in W_{i}\setminus\\{u\\}$;

  2. (ii)

there exist $v,v^{\prime}\in X^{*}$ not both equal to $\epsilon$ such that
$uv\in W_{i}$ and $v^{\prime}u\in W_{i}$;

  3. (iii)

there exist $v,v^{\prime}\in X^{*}$ with $v\neq\epsilon$ such that $uv\in
W_{i}$ and $vv^{\prime}\in W_{i}$;

  4. (iv)

there exist $v,v^{\prime}\in X$ with $v^{\prime}\neq\epsilon$ such that
$v^{\prime}u\in W_{i}$ and $vv^{\prime}\in W_{i}$.

It may be shown that there is a number $n$ such that $W_{n}=W_{n^{\prime}}$
for all $n^{\prime}\geq n$ i.e. this process eventually stabilises. Then
$B(R)=W_{n}$ is a biprefix code that freely generates $B(R)$; see [12, 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 [1].

######  Theorem 4.1 (Adjan [1, Chapter III, Theorem 7]).

For any one-relator special monoid
$\operatorname{Mon}\bigl{\langle}A\>|\>r=1\bigr{\rangle}$ the Adjan algorithm
computes the decomposition of $r$ into minimal invertible pieces. More
precisely, the biprefix code $B(\\{r\\})$ computed by the Adjan algorithm is
equal to the set of minimal invertible pieces of the relator $r$. Hence there
is an algorithm that takes any special one-relator monoid as input, and
computes a one-relator presentation which is isomorphic to the group of units
of the monoid.

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

######  Example 4.2.

Consider the monoid presentation

$\operatorname{Mon}\bigl{\langle}a,b,c,d\>|\>ab=1,cabd=1,cdd=1\bigr{\rangle}$

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 [21] that the problem of whether a finitely presented
special monoid is a group is undecidable. From this is 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, Meakin and Stephen in [20]. As already
mentioned above, in that paper the following example is introduced

$\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},$

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,
Meakin and Stephen [20], using van Kampen diagrams and Stephen’s procedure,
succeed in showing that $r$ in fact has a finer decomposition, namely

$r\equiv abcd\cdot acd\cdot ad\cdot abbcd\cdot acd.$

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 will have the following properties

  1. (i)

it correctly computes the minimal invertible pieces of the O’Hare example, and

  2. (ii)

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

$\Sigma=\bigcup_{i\in
I}(\operatorname{pref}(r_{i})\cup\operatorname{pref}(r_{i}^{-1}))\subseteq\overline{A}^{*}.$

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

$r_{i}\equiv r_{i1}r_{i2}\ldots r_{i{k_{i}}}$ (23)

such that for every proper prefix $p$ of $r_{i}$ we have

$\mathrm{red}(p^{-1})\in V\Leftrightarrow p\equiv r_{i1}r_{i2}\ldots r_{ij}\
\mbox{for some}\ j\in\\{1,\ldots,k_{i}\\}.$ (24)

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$.

######  Lemma 4.3.

For each $i\in I$, the factorisation (23), (24) is a decomposition into
invertible pieces.

###### Proof.

We need to prove that each $r_{ij}$ represents an invertible element of $M$.
This is equivalent to each prefix $p_{ij}\equiv r_{i1}r_{i2}\dots r_{ij}$
being invertible, and we proceed to prove this latter assertion. Since every
word in $\Sigma$ clearly represents a right invertible element of $M$ it
follows that every word in $\Sigma^{*}$ represents a right invertible element
of $M$. Applying Lemma 2.2(iii) it follows that every word in $V$ represents a
right invertible element of $M$. Since $p_{ij}$ represents a right invertible
element of $M$ it follows from Lemma 2.2(iii) that
$p_{ij}=\operatorname{red}(p_{ij})$ in $M$. The word $p_{ij}^{-1}$ represents
a left invertible element of $M$, and hence
$p_{ij}^{-1}=\operatorname{red}(p_{ij}^{-1})$ also holds in $M$ by an obvious
dual of Lemma 2.2(iii). By (24) we have $\operatorname{red}(p_{ij}^{-1})\in
V$, implying that $p_{ij}^{-1}$ represents a right invertible element of $M$,
and therefore $p_{ij}$ represents an invertible element of $M$, as required. ∎

Note that this lemma does not claim that (23), (24) 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 decidable submonoid
membership problem; see [13].

######  Lemma 4.4.

There is an algorithm which takes any finite inverse monoid presentation
$\operatorname{Inv}\bigl{\langle}A\>|\>r_{i}=1\;(i\in I)\bigr{\rangle}$ and
any word $w\in\overline{A}^{*}$, and decides whether $\mathrm{red}(w)\in V$.
Therefore there is an algorithm which takes any finite inverse monoid
presentation $\operatorname{Inv}\bigl{\langle}A\>|\>r_{i}=1\;(i\in
I)\bigr{\rangle}$ and computes the decomposition into invertible pieces given
by (23), (24) for all relators $r_{i}$ in the presentation.

###### Proof.

By definition the set $V$ is a finitely generated submonoid of the free group
$F_{A}$, and the word $\operatorname{red}(w)$ is an element of the free group
$F_{A}$. Hence Benois’ Theorem can be applied to decide whether or not
$\operatorname{red}(w)\in V$. The second assertion in the statement of the
lemma is then immediate. ∎

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.

######  Theorem 4.5.

Let $M=\operatorname{Inv}\bigl{\langle}A\>|\>r_{i}=1(i\in I)\bigr{\rangle}$.
Then for all $i\in I$ the decomposition of $r_{i}$ into pieces computed by the
Benois algorithm is a refinement of the decomposition computed by 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$ i.e. $\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

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

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$.

######  Remark 4.6.

Although we do not need it here, it may be shown that
$\overrightarrow{\Sigma^{*}}$ is a regular language, i.e. there is a finite
state automaton $\mathcal{A}$ such that the language $L(\mathcal{A})$
recognised by the automaton is $L(\mathcal{A})=\overrightarrow{\Sigma^{*}}$.
The proof of this can be found in [13]. The idea is to use an automaton
saturation procedure. We begin with a finite state automaton $\mathcal{B}$
with $L(\mathcal{B})=\Sigma^{*}$ and then add $\epsilon$ transitions wherever
we can read $xx^{-1}$, and repeat this process until no more $\epsilon$
transitions need to be added. Note that given reduced word $u$ we can check if
$u\in V$ by testing whether $u\in L(\mathcal{A})$.

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

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

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{red}(p^{-1})\in\overrightarrow{\Sigma^{*}}$.

######  Lemma 4.7.

Let $p$ be a prefix of the relator $r_{i}$ where $i\in I$. If
$p\in\mathcal{U}$ then $p$ is an invertible prefix of $r_{i}$ computed by the
Benois algorithm.

###### Proof.

Since $p\in\mathcal{U}$ it follows by definition of $\mathcal{U}$ that
$p^{-1}\in\overrightarrow{\Sigma^{*}}$. It follows that

$\operatorname{red}(p^{-1})\in\overrightarrow{\Sigma^{*}}=\operatorname{red}(\Sigma^{*})=V,$

since by definition the set $\overrightarrow{\Sigma^{*}}$ is closed under the
operation of partial free reduction of words. It follows from the definition
of the Benois algorithm that $p$ is an invertible piece of $r_{i}$ computed by
the Benois algorithm. ∎

######  Remark 4.8.

It is important to note that we are _not_ claiming that $\mathcal{U}$ contains
_all_ the invertible prefixes of relators computed by the Benois algorithm.

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

######  Lemma 4.9.

Let $\gamma,\delta\in\overline{A}^{*}$ with $\gamma\rightarrow\delta$. Then
for any decomposition $\delta\equiv\delta_{1}\delta_{2}$ there exists a
decomposition $\gamma\equiv\gamma_{1}\gamma_{2}$ such that
$\gamma_{1}\rightarrow^{*}\delta_{1}$ and
$\gamma_{2}\rightarrow^{*}\delta_{2}$.

###### Proof.

Since $\gamma\rightarrow\delta$ we can write
$\gamma\equiv\gamma^{\prime}xx^{-1}\gamma^{\prime\prime}$ where
$\delta\equiv\gamma^{\prime}\gamma^{\prime\prime}$ and $x\in\overline{A}$.

Now we have
$\delta_{1}\delta_{2}\equiv\delta\equiv\gamma^{\prime}\gamma^{\prime\prime}$.
Then $\gamma^{\prime}$ is a prefix of $\delta_{1}$, or else
$\gamma^{\prime\prime}$ is a suffix of $\delta_{2}$. We consider the former
case, and the latter is dealt with analogously. Write
$\delta_{1}\equiv\gamma^{\prime}\mu$. So
$\gamma^{\prime}\gamma^{\prime\prime}\equiv\delta\equiv\delta_{1}\delta_{2}\equiv\gamma^{\prime}\mu\delta_{2}$.
Hence $\gamma^{\prime\prime}\equiv\mu\delta_{2}$ and so
$\gamma\equiv\gamma^{\prime}xx^{-1}\mu\delta_{2}$. So if we set
$\gamma_{1}\equiv\gamma^{\prime}xx^{-1}\mu$ and $\gamma_{2}\equiv\delta_{2}$
then $\gamma\equiv\gamma_{1}\gamma_{2}$ and
$\gamma_{1}\rightarrow^{*}\gamma^{\prime}\mu\equiv\delta_{1}$ and
$\gamma_{2}\rightarrow^{*}\delta_{2}$, as required. ∎

######  Corollary 4.10.

Let $\gamma,\delta\in\overline{A}^{*}$ with $\gamma\rightarrow^{*}\delta$.
Then for any decomposition $\delta\equiv\delta_{1}\delta_{2}$ there exists a
decomposition $\gamma\equiv\gamma_{1}\gamma_{2}$ such that
$\gamma_{1}\rightarrow^{*}\delta_{1}$ and
$\gamma_{2}\rightarrow^{*}\delta_{2}$.

###### Proof.

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

$\gamma\equiv w_{0}\rightarrow w_{1}\rightarrow\ldots\rightarrow
w_{k}\equiv\delta.$

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

$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}.$

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.

######  Lemma 4.11.

The set $\overrightarrow{\Sigma^{*}}$ is prefix closed i.e. for any words
$\alpha,\beta\in\overline{A}^{*}$ if $\alpha\in\overrightarrow{\Sigma^{*}}$
and $\beta$ is a prefix of $\alpha$ then
$\beta\in\overrightarrow{\Sigma^{*}}$.

###### Proof.

Let $\beta$ be a prefix of $\alpha$. Write $\alpha\equiv\beta\beta^{\prime}$.
Since $\alpha\in\overrightarrow{\Sigma^{*}}$ there exists a word
$\gamma\in\Sigma^{*}$ such that
$\gamma\rightarrow^{*}\alpha\equiv\beta\beta^{\prime}$. It follows from
Corollary 4.10 that there exists a decomposition
$\gamma\equiv\gamma_{1}\gamma_{2}$ with $\gamma_{1}\rightarrow^{*}\beta$ and
$\gamma_{2}\rightarrow^{*}\beta^{\prime}$. Since $\gamma\in\Sigma^{*}$ and
$\gamma_{1}$ is a prefix of $\gamma$ it follows that
$\gamma_{1}\in\Sigma^{*}$. Since $\gamma_{1}\in\Sigma^{*}$ and
$\gamma_{1}\rightarrow^{*}\beta$ it follows that
$\beta\in\overrightarrow{\Sigma^{*}}$. ∎

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

######  Lemma 4.12.

The set $\overrightarrow{\Sigma^{*}}$ is closed under products i.e. if
$\alpha\in\overrightarrow{\Sigma^{*}}$ and
$\beta\in\overrightarrow{\Sigma^{*}}$ then
$\alpha\beta\in\overrightarrow{\Sigma^{*}}$.

###### Proof.

Let $\alpha_{0},\beta_{0}\in\Sigma^{*}$ such that
$\alpha_{0}\rightarrow^{*}\alpha$ and $\beta_{0}\rightarrow^{*}\beta$. It
follows that $\alpha_{0}\beta_{0}\in\Sigma^{*}$ with
$\alpha_{0}\beta_{0}\rightarrow\alpha\beta$ hence
$\alpha\beta\in\overrightarrow{\Sigma^{*}}$. ∎

######  Lemma 4.13.

$r_{i}\in\mathcal{U}$ for all $i\in I$.

###### Proof.

By definition of $\Sigma$ both $r_{i}\in\Sigma$ and $r_{i}^{-1}\in\Sigma$.
Since $\Sigma$ is a subset of $\overrightarrow{\Sigma^{*}}$ it the follows
from the definition of $\mathcal{U}$ that $r_{i}\in\mathcal{U}$. ∎

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

######  Lemma 4.14.

The set $\mathcal{U}$ is closed under inverses i.e. if $\alpha\in\mathcal{U}$
then $\alpha^{-1}\in\mathcal{U}$.

######  Lemma 4.15.

The set $\mathcal{U}$ is closed under products i.e. if $\alpha\in\mathcal{U}$
and $\beta\in\mathcal{U}$ then $\alpha\beta\in\mathcal{U}$.

###### Proof.

Since $\mathcal{U}$ is closed under inverses by Lemma 4.14 it follows that
$\alpha,\alpha^{-1},\beta,\beta^{-1}\in\overrightarrow{\Sigma^{*}}$. But
$\overrightarrow{\Sigma^{*}}$ is closed under products by Lemma 4.12, hence
$\alpha\beta\in\overrightarrow{\Sigma^{*}}$ and
$(\alpha\beta)^{-1}\equiv\beta^{-1}\alpha^{-1}\in\overrightarrow{\Sigma^{*}}$
hence $\alpha\beta\in\mathcal{U}$ by definition of $\mathcal{U}$. ∎

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

######  Lemma 4.16.

The set $\mathcal{U}$ is closed under partial free reductions i.e. if
$\alpha\in\mathcal{U}$ and $\alpha\rightarrow^{*}\beta$ then
$\beta\in\mathcal{U}$.

###### Proof.

Since $\alpha\in\mathcal{U}$ it follows from the definition of $\mathcal{U}$
that $\alpha\in\overrightarrow{\Sigma^{*}}$ and
$\alpha^{-1}\in\overrightarrow{\Sigma^{*}}$. Since
$\alpha\rightarrow^{*}\beta$ it follows from the definition of
$\rightarrow^{*}$ that $\alpha^{-1}\rightarrow^{*}\beta^{-1}$. Hence
$\beta\in\overrightarrow{\Sigma^{*}}$ and
$\beta^{-1}\in\overrightarrow{\Sigma^{*}}$. Since
$\beta\in\overrightarrow{\Sigma^{*}}$ and
$\beta^{-1}\in\overrightarrow{\Sigma^{*}}$ it follows from the definition of
$\mathcal{U}$ that $\beta\in\mathcal{U}$ ∎

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.

######  Lemma 4.17.

The set $\mathcal{U}$ is closed under the Adjan overlap algorithm i.e. for all
words $\alpha,\beta,\gamma\in\overline{A}^{*}$, if $\alpha\beta\in\mathcal{U}$
and $\beta\gamma\in\mathcal{U}$ then
$\\{\alpha,\beta,\gamma\\}\subseteq\mathcal{U}$. In other words, the submonoid
$\mathcal{U}$ of $\overline{A}^{*}$ has property ($\mathcal{A}$).

###### Proof.

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

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

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.

###### Proof of Theorem 4.5.

Let $p$ be some prefix of some relator $r_{i}$, with $i\in I$. Write
$r_{i}\equiv pq$. Suppose $p$ is an invertible prefix of $r_{i}$ computed by
the Adjan algorithm. By definition of the Adjan algorithm, this means that $p$
belongs to the submonoid $U(R)$ of $\overline{A}^{*}$ generated by the finite
biprefix code $B(R)$ computed by the Adjan algorithm, where
$R=\\{r_{i}\>:\>i\in I\\}$. Since $r_{i}\in\mathcal{U}$ for all $i\in I$ by
Lemma 4.13 and $\mathcal{U}$ is closed under the Adjan algorithm by Lemma
4.17, it follows that $\mathcal{U}$ is a submonoid of $\overline{A}^{*}$ with
$R\subseteq\mathcal{U}$ and $\mathcal{U}$ has property ($\mathcal{A}$). By
definition $U(R)$ is the smallest submonoid of $\overline{A}^{*}$ such that
$R\subseteq U(R)$ and $U(R)$ satisfies ($\mathcal{A}$). Hence it follows that
$U(R)\subseteq\mathcal{U}$. Since $p$ belongs to $U(R)$ by assumption, it
follows that $p$ also belongs to $\mathcal{U}$. But then by Lemma 4.7, since
$p\in\mathcal{U}$ it follows that $p$ is an invertible prefix of a relator
(specifically of the relator $r_{i}$) computed by the Benois algorithm. ∎

######  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

$\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}$

######  Definition 4.19.

We call a set $W\subseteq\overline{A}^{*}$ _$i$ -overlap free_ if $W\cup
W^{-1}$ is overlap free.

######  Remark 4.20.

It is not clear (and possibly not true in general) that the set of Benois
pieces is $i$-overlap free. However, it is a consequence of the results above
that if all the relators $r_{i}\;(i\in I)$ are reduced words then the Benois
pieces are all $i$-overlap free. To see this, suppose that $p$ is a prefix of
$r_{i}$ with $p\in V$ and $\operatorname{red}(p^{-1})\in V$ (i.e. $p$ is
computed by the Benois algorithm). Since $p$ is a reduced word, it follows
that $p^{-1}$ is also reduced, so $p^{-1}\equiv\operatorname{red}(p^{-1})\in
V$. So we have both $p\in V$ and $p^{-1}\in V$ where
$V=\operatorname{red}(\Sigma^{*})\subseteq\overrightarrow{\Sigma^{*}}$. since
$p\in\overrightarrow{\Sigma^{*}}$ and $p^{-1}\in\overrightarrow{\Sigma^{*}}$
it follows from the definition of $\mathcal{U}$ that $p\in\mathcal{U}$. It
then follows by Lemma 4.17 that when all the relators $r_{i}$ are reduced
words, all the pieces of relators computed by the Benois algorithm also belong
to the set $\mathcal{U}$. But then since $\mathcal{U}$ is closed under taking
inverses by Lemma 4.14 it follows from Lemma 4.17 that the set pieces computed
of the relators by the Benois algorithm is $i$-overlap free.

######  Example 4.21.

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

$\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}.$

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

$r\equiv abcd\cdot acd\cdot ad\cdot abbcd\cdot acd.$

For notational convenience we set

$\alpha\equiv abcd,\;\beta\equiv acd,\;\gamma\equiv ad,\;\delta\equiv abbcd.$

Using the same notation as above, we have

$\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}\\},$

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

$\operatorname{red}(\;\beta(\alpha\beta\gamma\delta\beta)^{-1}(\alpha\beta\gamma)\;)\equiv\delta^{-1}$

and

$\operatorname{red}(\beta^{-1}\alpha\delta^{-1})\equiv\alpha^{-1}.$

Then we have:

$\displaystyle\alpha^{-1}$
$\displaystyle\equiv\operatorname{red}(\beta^{-1}\alpha\delta^{-1})\equiv\operatorname{red}(\;\beta^{-1}\cdot\alpha\beta\cdot(\alpha\beta\gamma\delta\beta)^{-1}\cdot(\alpha\beta\gamma)\;)\in
V$ $\displaystyle(\alpha\beta)^{-1}$
$\displaystyle\equiv\beta^{-1}\alpha^{-1}\equiv\operatorname{red}(\;\beta^{-1}\beta^{-1}\alpha\delta^{-1}\;)\equiv\operatorname{red}(\;\beta^{-1}\cdot\beta^{-1}\cdot\alpha\beta\cdot(\alpha\beta\gamma\delta\beta)^{-1}\cdot(\alpha\beta\gamma)\;)\in
V$ $\displaystyle(\alpha\beta\gamma)^{-1}$
$\displaystyle\equiv\operatorname{red}((\delta\beta)(\alpha\beta\gamma\delta\beta)^{-1})\equiv\operatorname{red}((\alpha\beta^{-1}\alpha)\beta(\alpha\beta\gamma\delta\beta)^{-1})$
$\displaystyle\equiv\operatorname{red}(\alpha\cdot\beta^{-1}\cdot\alpha\beta\cdot(\alpha\beta\gamma\delta\beta)^{-1})\in
V$ $\displaystyle(\alpha\beta\gamma\delta)^{-1}$
$\displaystyle=\operatorname{red}(\beta(\alpha\beta\gamma\delta\beta)^{-1})=\operatorname{red}(\alpha\delta^{-1}\alpha(\alpha\beta\gamma\delta\beta)^{-1})$
$\displaystyle=\operatorname{red}((\alpha\beta)\cdot(\delta\beta)^{-1}\cdot\alpha\cdot(\alpha\beta\gamma\delta\beta)^{-1})\in
V.$

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 non-empty 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, e.g. 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

$M=\operatorname{Inv}\bigl{\langle}a,b,c\>|\>a(bc^{2}b^{-1})a(bc^{3}b^{-1})a(bc^{2}b^{-1})a=1\bigr{\rangle}.$

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

$\operatorname{Gp}\bigl{\langle}x,y,z\>|\>xyxzxyx=1\bigr{\rangle}=F_{x,y}$

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

$a(bc^{2}b^{-1})a(bc^{3}b^{-1})a(bc^{2}b^{-1})a$

as

$a(bcb^{-1})^{2}a(bcb^{-1})^{3}a(bcb^{-1})^{2}a$

and then by Corollary 3.12 we can conclude that the group of units of $M$ is
the one relator group with presentation

$\operatorname{Gp}\bigl{\langle}x,t\>|\>xt^{2}xt^{3}xt^{2}x=1\bigr{\rangle}.$

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

$\operatorname{Inv}\bigl{\langle}a,b,c,d\>|\>abcdacdadabbcdacd=1\bigr{\rangle}=\operatorname{Inv}\bigl{\langle}a,b,c,d\>|\>r=1\bigr{\rangle}.$

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, Meakin and Stephen [20] proved that the decomposition into
minimal invertible pieces of this defining relator is

$r\equiv abcd\cdot acd\cdot ad\cdot abbcd\cdot acd.$

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

$\alpha\equiv abcd,\;\beta\equiv acd,\;\gamma\equiv ad,\;\delta\equiv abbcd.$

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

$H=\operatorname{Gp}\bigl{\langle}\alpha,\beta,\gamma,\delta\>|\>\alpha\beta\gamma\delta\beta=1\bigr{\rangle},$

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 two.

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

$\delta\alpha^{-1}=abbcdd^{-1}c^{-1}b^{-1}a^{-1},$

and

$\beta\gamma^{-1}=acdd^{-1}a^{-1}$

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

$aba^{-1},\ aca^{-1}\ \mbox{and}\ ad$

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

$u\equiv(aba^{-1})(aca^{-1})(ad)(aca^{-1})(ad)(ad)(aba^{-1})(aba^{-1})(aca^{-1})(ad)(aca^{-1})(ad)$

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

$\operatorname{Inv}\bigl{\langle}a,b,c,d\>|\>u=1\bigr{\rangle}$

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

$\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}.$

So the O’Hare monoid is defined by the presentation

$\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}.$

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 elements 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.12
are satisfied and hence applying this corollary we conclude that the group of
units $U(\mathcal{O})$ of $\mathcal{O}$ is isomorphic to

$\operatorname{Gp}\bigl{\langle}x,y,z\>|\>xyzyzzxxyzyz=1\bigr{\rangle}.$

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.10 (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.12 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

$\displaystyle\operatorname{Gp}\bigl{\langle}x,y,z\>|\>xyzyzzxxyzyz=1\bigr{\rangle}$
$\displaystyle=$
$\displaystyle\operatorname{Gp}\bigl{\langle}x,y,z,t\>|\>xttzxxtt=1,t=yz\bigr{\rangle}$
$\displaystyle=$
$\displaystyle\operatorname{Gp}\bigl{\langle}x,y,z,t\>|\>xttzxxtt=1,y=tz^{-1}\bigr{\rangle}$
$\displaystyle=$
$\displaystyle\operatorname{Gp}\bigl{\langle}x,z,t\>|\>xttzxxtt=1\bigr{\rangle}\cong\mathrm{FG}(x,t).$

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

$\operatorname{Inv}\bigl{\langle}A\>|\>r=1\bigr{\rangle}$

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 [22] where he
attributes the example to Graham Higman. As explained there, if we let

$B=\operatorname{Gp}\bigl{\langle}a,b\>|\>b^{-1}a^{2}b=a^{3}\bigr{\rangle}$

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

$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}.$

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 $2$-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 [16, page 6]. The thing that is relevant for us
here is the result (see [16, 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

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

Set

$K=\operatorname{Gp}\bigl{\langle}x,y,z\>|\>xyz^{-1}=1\bigr{\rangle}$

and

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

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}A\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

$\phi(z^{2}y)=\phi(yz^{3})$

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

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

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 [5] to give an example of a one-
relator special inverse monoid with undecidable word problem. It has also been
used in the papers [6] and [8] 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 [5]. Some of the results we need about this construction have already been
proved in [5], 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 non-empty alphabet. Let
$Q=\\{r_{i}\>:\>i\in I\\}$ be a subset of $\overline{A}^{*}$, where $I$ is
non-empty 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

$\displaystyle K_{Q}$
$\displaystyle=\operatorname{Gp}\bigl{\langle}A\>|\>r_{i}=1\;(i\in
I)\bigr{\rangle}$ (25) $\displaystyle G_{Q}$
$\displaystyle=\operatorname{Gp}\bigl{\langle}A,t\>|\>r_{i}=1\;(i\in
I)\bigr{\rangle}=K_{Q}\ast F_{t}.$ (26)

Given a list of words $u_{1},\ldots,u_{m}\in\overline{A}^{*}$ we define

$e(u_{1},u_{2},\ldots,u_{m})=u_{1}u_{1}^{-1}u_{2}u_{2}^{-1}\ldots
u_{m}u_{m}^{-1},$

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:

$\displaystyle N_{Q}$
$\displaystyle=\operatorname{Inv}\bigl{\langle}A\>|\>r_{i}=1\;(i\in
I)\bigr{\rangle}$ (27) $\displaystyle M_{Q,W}$
$\displaystyle=\operatorname{Inv}\bigl{\langle}A,t\>|\>fr_{1}=1,r_{i}=1\;(i\in
I\setminus\\{1\\})\bigr{\rangle}$ (28)

where

$f=e(a_{1},\ldots,a_{n},tw_{1}t^{-1},\ldots,tw_{k}t^{-1},a_{1}^{-1},\ldots,a_{n}^{-1}).$
(29)

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

$M_{Q,W}=\operatorname{Inv}\bigl{\langle}A,t\>|\>r_{i}=1\
a_{j}a_{j}^{-1}=a_{j}^{-1}a_{j}=1,\ tw_{l}t^{-1}tw_{l}^{-1}t^{-1}=1\ (i\in I,\
j\in[n],\ l\in[k])\bigr{\rangle}$ (30)

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 $tw_{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 [5, 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}=tHt^{-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 [16, 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 tT_{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^{\prime}}$ where $H_{W^{\prime}}$ is the subgroup of $K_{Q}$
generated by the subset $W^{\prime}$ of $W$ defined by

$W^{\prime}=\\{w_{l}\in W:tw_{l}t^{-1}\ \mbox{is invertible in}\;M_{Q,W}\\}.$

In particular if $W=W^{-1}$ then $W^{\prime}=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 [5,
Theorem 3.8].

(iii) By [19, 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 [11, 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 [11, 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

$Y=A\cup A^{-1}\cup\\{t\\}\cup\\{tw_{l}t^{-1}:l\in[k]\\}.$

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_{j}a_{j}^{-1}$, $a_{j}^{-1}a_{j}$, as they are
products of generators from $A$. The proper prefixes of $tw_{l}t^{-1}$ are
products of generators from $A\cup\\{t\\}$. Finally, longer prefixes of
$tw_{l}t^{-1}tw_{l}^{-1}t^{-1}$ are equal in $M_{Q,W}$ to prefixes of
$tw_{l}t^{-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
$tT_{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
tT_{W}t^{-1}$. By Lemma 6.2 the submonoid of $K_{Q}\ast F_{t}$ generated by
$K_{Q}\cup tK_{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 tT_{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^{\prime}=\\{b^{i}\>:\>i\in\mathbb{N}_{0}\\}$, while $R(M_{Q,W})\setminus
V_{Q,W}$ is mapped onto $V^{\prime}=\\{b^{i}\>:\>i\in\mathbb{N}\\}$, and that
$V^{\prime}$ is an ideal of $R^{\prime}$. 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

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

is a monoid generating set for $U(M_{Q,W})$ (this follows from the more
general fact [5, 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^{\prime}t^{-1}$ where

$W^{\prime}=\\{w_{l}\in W:tw_{l}t^{-1}\ \mbox{is invertible in}\;M_{Q,W}\\}.$

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

$Z=A\cup A^{-1}\cup tW^{\prime}t^{-1}.$

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 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^{\prime}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^{\prime}t^{-1}$. Under the isomorphism from (iv), this
corresponds to $K_{Q}\ast H_{W^{\prime}}$, proving the first assertion. For
the second assertion observe that if $W=W^{-1}$ then $W^{\prime}=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 know e.g. it is a corollary of [7, 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 [25, Theorem 3.4] (see in particular
the remark in [25] immediately after the proof of Theorem 3.4 of that paper).
∎

##  7\. Applications to further examples

The central theme in this article as outlined in Section 1 has been to
investigate the extent to which analogues of the results of
Adjan/Makanin/Zhang for finitely presented special monoids can be proved for
special inverse monoid presentations. Both the example at the start of Section
3 and the O’Hare monoid example considered in Subsection 5.1 show that while
the obvious naïve generalisation to special inverse monoids does not hold, by
an appropriate choice of basis, the hypotheses of Theorem 3.1 are satisfied by
these two examples. In particular in each case their groups of units are one-
relator groups. As explained in Section 1 it is natural to ask whether the
assumptions of Theorem 3.1 are perhaps always satisfied, or at least always in
the case of one-relator presentations. The main results in Section 3 identify
several sufficient conditions under which the assumptions of Theorem 3.1 are
satisfied, see for example the conditions (F1), (F2), and (F3).

In this section we will use the general construction and Theorem 6.3 from the
previous section to prove that in general none of the main results of
Adjan/Makanin/Zhang for special monoids can be extended to special inverse
monoids.

We are also prove a result which shows a close relationship between finite
presentability of the units of special one-relator inverse monoids and the
question of coherence of one-relator groups.

###  7.1. A one-relator special inverse monoid whose group of units if not
one-relator

If we input a one-relator group $K_{Q}$ into the construction from Section 6
then Theorem 6.3(v) shows that the group of units of the one-relator special
inverse monoid $M_{Q,W}$ is isomorphic to the free product of groups
$K_{Q}\ast H_{W}$ where by appropriate choice of $W$ in the construction, the
group $H_{W}^{\prime}$ can be any finitely generated subgroup of $K_{Q}$ that
we please. In particular the set $W$ can be chosen so that the group of units
of the one-relator special inverse monoid $M_{Q,W}$ is isomorphic to
$K_{Q}\ast K_{Q}$.

Since in general the free product $K_{Q}\ast K_{Q}$ of a one-relator group
$K_{Q}$ with itself is not a one-relator group, this can be used to construct
examples of special one-relator inverse monoids whose groups of units are not
one-relator. This leads to the following result.

######  Theorem 7.1.

There exists a one-relator special inverse monoid
$M=\operatorname{Inv}\bigl{\langle}A\>|\>w=1\bigr{\rangle}$ whose group of
units $G$ is not a one-relator group with respect to any finite generating
set. Moreover, $M$ can be chosen to be E-unitary.

###### Proof.

Let $A=\\{a,b,c,d\\}$, let $Q=\\{aba^{-1}b^{-1}cdc^{-1}d^{-1}\\}$ and set
$W=\\{a^{\pm 1},b^{\pm 1},c^{\pm 1},d^{\pm 1}\\}$. Then by Theorem 6.3 (i),
(ii), (v) the monoid $M=M_{Q,W}$ is a one-relator E-unitary special inverse
monoid with group of units $U(M)\cong K\ast K$ where

$K=K_{Q}=\operatorname{Gp}\bigl{\langle}a,b,c,d\>|\>[a,b][c,d]=1\bigr{\rangle}=\operatorname{Gp}\bigl{\langle}a,b,c,d\>|\>aba^{-1}b^{-1}cdc^{-1}d^{-1}=1\bigr{\rangle}.$

Note that $K$ is a torsion-free one-relator group. In fact it is a one-relator
surface group: the fundamental group of a surface of genus $2$. To complete
the proof it now suffices to prove that the free product $K\ast K$ of this
one-relator group with itself is not a one-relator group with respect to any
finite generating set. One way to see this is as follows.

It follows from Lyndon’s Identity Theorem [15], see also [3, page 37, Example
3], that $H_{2}(K)=\mathbb{Z}$, where $H_{2}(K)$ denotes the second homology
group of $K$. Indeed, it follows from Lyndon’s results that if
$G=\operatorname{Gp}\bigl{\langle}X\>|\>s=1\bigr{\rangle}$ is a torsion-free
one relator group, where $s$ is a cyclically reduced word, then

$H_{2}(G)\cong\begin{cases}\mathbb{Z}&\mbox{if }s\in F_{X}^{\prime}\\\
0&\mbox{otherwise,}\end{cases}$

where $F_{X}^{\prime}$ is the derived subgroup of the free group. From
$H_{2}(K)=\mathbb{Z}$ it follows by [26, Corollary 6.2.10] or [10, page 220,
Theorem 14.2] that

$H_{2}(K\ast K)\cong H_{2}(K)\oplus H_{2}(K)\cong\mathbb{Z}\oplus\mathbb{Z}.$

Clearly $K\ast K$ is torsion free, since $K$ is torsion free, and thus by
Lyndon’s result above it follows that $K\ast K$ cannot be a one-relator group
with respect to any generating set. ∎

###  7.2. A one-relator special inverse monoid whose group of units is
finitely presented but the monoid of right units is not finitely presented

An important structural result arising from the work of Adjan/Makanin/Zhang is
that the monoid of right units of a finitely presented special monoid is
isomorphic to a free product of its group of units and a finitely generated
free monoid. The results in this subsection will show that this is far from
being true in the case of special inverse monoids.

Theorem 6.3(vi) tells us that, for that construction, finite presentability of
the right units $R(M_{Q,W})$ of the special inverse monoid $M_{Q,W}$ is
determined by finite presentability of the group $K_{Q}$, and of the submonoid
$T_{W}$ of $K_{Q}$. Since there are examples of finitely generated submonoids
of one-relator groups that are not finitely presented, this leads to the
following result.

######  Theorem 7.2.

There exists a one-relator special inverse monoid
$M=\operatorname{Inv}\bigl{\langle}A\>|\>r=1\bigr{\rangle}$ with the following
properties:

  * •

the group of units $G$ of $M$ is finitely presented, and

  * •

the submonoid of right units $R$ of $M$ is finitely generated but not finitely
presented.

Hence there is no finitely presented monoid $N$ such that $R\cong G\ast N$. In
particular, there is no free monoid $F$ such that $R\cong G\ast F$.
Throughout, $M$ can be chosen to be E-unitary.

###### Proof.

Let $A=\\{a_{1},\ldots,a_{n}\\}$, let $Q=\varnothing$ and let
$W=\\{w_{1},\ldots,w_{k}\\}$ be a finite subset of $A^{*}$ such that the
submonoid of $A^{*}$ generated by $W$ is not finitely presented (e.g. [4,
Example 4.5]). Then we have

$M_{Q,W}=\operatorname{Inv}\bigl{\langle}A,t\>|\>e(a_{1},\ldots,a_{n},tw_{1}t^{-1},\ldots,tw_{k}t^{-1},a_{1}^{-1},\ldots,a_{n}^{-1})=1\bigr{\rangle}.$

The maximal group image of $M_{Q,W}$ is the free group
$G_{Q}=F_{A\cup\\{t\\}}$, and $K_{Q}=F_{A}$. The submonoid $T_{W}$ of $K_{Q}$
generated by $W$ is not finitely presented by choice of $W$, and hence by
Theorem 6.3(vi) the submonoid of right units $R(M_{Q,W})$ is not finitely
presented. The submonoid of right units $R(M_{Q,W})$ is finitely generated by
Theorem 6.3(iii). Since $M_{Q,W}$ is E-unitary and the maximal group image is
free it follows that the group of units of $M_{Q,W}$ is a finitely generated
free group and in particular is finitely presented. Since the group of units
$G$ is finitely presented it follows that for any finitely presented monoid
$N$ the free product $G\ast N$ is also finitely presented. As $R$ is not
finitely presented we conclude that there is no finitely presented monoid $N$
such that $R\cong G\ast N$. For the last statement, if $R\cong G\ast F$ then
since $R$ is finitely generated it would follow that $F$ is finitely generated
and hence finitely presented (since $F$ is free). But since $G$ is finitely
presented this contradicts the fact that $R\cong G\ast F$ is not finitely
presented. ∎

######  Remark 7.3.

If we modify the above construction slightly and instead simply take the
inverse monoid

$\operatorname{Inv}\bigl{\langle}A,t\>|\>e(tw_{1}t^{-1},\ldots,tw_{k}t^{-1})=1\bigr{\rangle}$

then again the right units will not be finitely presented, but the group of
units in this case will be the trivial group. To see the latter statement it
is sufficient to observe that the elements $tw_{l}t^{-1}$ are not invertible
in the submonoid $tT_{W}t^{-1}$ of $G_{Q,W}=F_{A\cup\\{t\\}}$.

######  Remark 7.4.

The easy example
$M=\operatorname{Inv}\bigl{\langle}a,b\>|\>aba^{-1}b^{-1}=1\bigr{\rangle}$
shows that even in cases where the group of units and the monoid of right
units are both finitely presented, it is not the case that the monoid of right
units decomposes as the free product of the groups of units and a free (or
free inverse) monoid. Indeed, in this example it can be shown that the group
of units is trivial, while the submonoid of right units is isomorphic to the
free commutative monoid of rank $2$.

Indeed, since $aba^{-1}b^{-1}$ is cyclically reduced it follows that the
monoid $M$ is E-unitary, hence the submonoid of right units $R$ of $M$ is
isomorphic to the submonoid of the group
$G=\operatorname{Gp}\bigl{\langle}a,b\>|\>aba^{-1}b^{-1}=1\bigr{\rangle}$