# On the Complexity of Inverse Semigroup Conjugacy

Trevor Jack  NOVAMATH – Center for Mathematics and Applications
Faculdade de Ciências e Tecnologia
Universidade Nova de Lisboa
2829-516 Caparica, Portugal<EMAIL_ADDRESS>
###### Abstract.

We investigate the computational complexity of various decision problems
related to conjugacy in finite inverse semigroups. We describe polynomial-time
algorithms for checking if two elements in such a semigroup are $\sim_{p}$
conjugate and whether an inverse monoid is factorizable. We describe a
connection between checking $\sim_{i}$ conjugacy and checking membership in
inverse semigroups. We prove that $\sim_{o}$ and $\sim_{c}$ are partition
covering for any countable set and that $\sim_{p}$, $\sim_{p^{*}}$, and
$\sim_{tr}$ are partition covering for any finite set. We prove that checking
for nilpotency, $\mathrel{\mathcal{R}}$-triviality, and central idempotents in
partial bijection semigroups are $\mathsf{NL}$-complete problems and we extend
several complexity results for partial bijection semigroups to inverse
semigroups.

###### Key words and phrases:

inverse semigroups, conjugacy, algorithms, computational complexity,
$\mathsf{NL}$-completeness, $\mathsf{AC}^{0}$, idempotents.

###### 2010 Mathematics Subject Classification:

Primary: 20M18; Secondary 68Q25

This work was partially supported by the Fundação para a Ciência e a
Tecnologia (Portuguese Foundation for Science and Technology) through the
projects UIDB/00297/2020 (Centro de Matemática e Aplicações) and PTDC/MAT-
PUR/31174/2017.

##  1\. Introduction

Conjugacy classes are important tools for analyzing group structure and
significant work has been done to define an equivalence relation for
semigroups that coincides with group conjugacy when the semigroup is a group.
It turns out there are manys ways to define such an equivalence relation. In
[3], the authors analyze four ways of defining conjugacy for semigroups and
this paper will begin with a brief review of these types of conjugacy. This
paper will then build upon results from [2] related to conjugacy in inverse
semigroups, with a particular focus on determining the computational
complexity of decision problems involving conjugacy in finite inverse
semigroups.

We will also recite several results from [9] related to decision problems for
partial bijection semigroups and then extend those results to decision
problems for inverse semigroups. Relatedly, this paper will give several
hardness results left open in [9]. Finally, this paper will answer Open
Problem 6.10 from [3].

##  2\. Preliminaries

An element $s\in S$ is _idempotent_ if $ss=s$ and we denote the set of
idempotents in $S$ as $E(S)$. Every finite semigroup $S$ has an _idempotent
power_ $\omega\in\mathbb{N}$ such that $s^{\omega}\in E(S)$ for every $s\in
S$. If $S$ is a monoid, define $S^{1}:=S$. Otherwise, let $1$ be a new element
satisfying $1s=s1=s$ for each $s\in S$ and define $S^{1}:=S\cup\\{1\\}$. We
call an element $u\in S^{1}$ a _unit_ iff there exists $u^{-1}\in S$
satisfying $uu^{-1}=u^{-1}u=1$. The set of units of $S$ forms a subgroup,
denoted $U(S)$. A monoid $S$ is called _factorizable_ if $S=U(S)E(S)$. We
shall also refer to an element as factorizable if it is the product of a unit
and an idempotent.

For a semigroup $S$, two elements $a,b\in S$ are said to be
$\mathrel{\mathcal{R}}$-related ($\mathrel{\mathcal{L}}$-related), denoted
$a\mathrel{\mathcal{R}}b$ ($a\mathrel{\mathcal{L}}b$), iff $aS^{1}=bS^{1}$
($S^{1}a=S^{1}b$). The elements are $\mathrel{\mathcal{H}}$-related, denoted
$a\mathrel{\mathcal{H}}b$ iff $a\mathrel{\mathcal{R}}b$ and
$a\mathrel{\mathcal{L}}b$. For
$\mathrel{\mathcal{I}}\in\\{\mathrel{\mathcal{R}},\mathrel{\mathcal{L}},\mathrel{\mathcal{H}}\\}$,
a semigroup $S$ is _$\mathrel{\mathcal{I}}$ -trivial_ iff for every $s,t\in
S$, $s\mathrel{\mathcal{I}}t$ implies $s=t$.

A semigroup element $0\in S$ is a _left (right) zero_ if $0a=0$ ($a0=0$) for
each $a\in S$. If a semigroup has a left zero and a right zero, then they are
equal and we call this the zero element of the semigroup. A semigroup with a
zero element is _$n$ -nilpotent_ if the composition of any $n$ elements of the
semigroup yields the zero element. A semigroup is _nilpotent_ if it is
$n$-nilpotent for some $n\in\mathbb{N}$.

The _full transformation semigroup_ over $[n]:=\\{1,\dots,n\\}$, denoted
$T_{n}$, is the set of all mappings $f\colon[n]\to[n]$, together with function
composition. Subsemigroups of the full transformation semigroup are often also
referred to as _transformation semigroups_. The _full partial bijection
semigroup_ over $[n]$, denoted $I_{n}$, is the set of all bijections defined
on subsets of $[n]$, together with function composition. Subsemigroups $S\leq
I_{n}$ are called _partial bijection semigroups_. Let $\mathrm{dom}(a)$ denote
the domain of $a\in I_{n}$. Let $[n]a$ denote the range of $a$.

For $s\in S$, we define $t\in S$ to be an _inverse_ of $s$ iff $sts=s$ and
$tst=t$. A semigroup is an _inverse semigroup_ if each of its elements has a
unique invere. Every finite inverse semigroup can be embedded into some
$I_{n}$ [6, Th 5.1.7]. Every element $s\in I_{n}$ can be characterized by the
orbits of its action on $[n]$, which can be subdivided into two types.

A _cycle of length k_ is an ordered subset of $[n]$ denoted
$(x_{1},\dots,x_{k})$ such that $x_{i}s=x_{i+1}$ for $1\leq i<k$ and
$x_{k}s=x_{1}$. Let $\Delta_{s}^{k}$ be the set of all cycles of length $k$,
$\Delta_{s}$ be the set of all cycles, and
$\Delta_{s}^{>1}:=\Delta\setminus\Delta_{s}^{1}$. A _chain of length k_ is an
ordered set denoted $[x_{1},\dots,x_{k}]$ such that $x_{i}s=x_{i+1}$ for
$1\leq i<k$ and $x_{k}\not\in\mathrm{dom}(s)$. Let $\Theta_{s}^{k}$ be the set
of all chains of length $k$, $\Theta_{s}$ be the set of all chains, and
$\Theta_{s}^{>1}:=\Theta\setminus\Theta_{s}^{1}$. Note that, by this
convention, $\Theta_{s}^{1}:=\\{\\{x\\}:x\not\in\mathrm{dom}(s)\\}$

We now present several approaches for generalizing group conjugacy to
semigroups. Each of the following equivalence relations coincide with group
conjugacy when the semigroup is a group.

If $S$ is a monoid, we can define conjugacy in terms of units.

$a\sim_{u}b\Leftrightarrow uau^{-1}=b\text{ and }u^{-1}bu=a\text{ for some
}u\in U(S)$

We can define conjugacy in more general contexts if we avoid referring to the
unary inverse operator. Note that two group elements $a,b\in G$ are conjugate
iff there exists $g\in G$ such that $ag=gb$. This suggests the following
conjugacy relation over elements $a,b\in S$.

$a\sim_{o}b\Leftrightarrow ag=gb\text{ and }bh=ha\text{ for some }g,h\in S$

This is an equivalence relation, but it suffers the unfortunate drawback of
being the universal equivalence relation for any semigroup that has a _zero
element_ , $0$, satisfying $0s=s0=0$ for every $s\in S$.

To avoid this drawback, the authors in [1] restricted the set from which $g$
and $h$ can be chosen. For a semigroup $S$ with zero element $0$ and any
nonzero $a\in S\setminus\\{0\\}$, define $\mathbb{P}(a):=\\{g\in S:(ma)g\neq
0\text{ for any }ma\in S^{1}a\setminus\\{0\\}\\}$. If $S$ has no zero element,
define $\mathbb{P}(a):=S$. Define
$\mathbb{P}^{1}(a):=\mathbb{P}(a)\cup\\{1\\}$ with $1$ being the identity
element of $S^{1}$. We now define $\sim_{c}$ in a similar fashion as
$\sim_{o}$:

$a\sim_{c}b\Leftrightarrow ag=gb\text{ and }bh=ha\text{ for some
}g\in\mathbb{P}^{1}(a)\text{ and some }h\in\mathbb{P}^{1}(b)$

The next notion is motivated by the fact that $a,b\in G$ are conjugate iff
there exist $g,h\in G$ such that $a=gh$ and $b=hg$:

$a\sim_{p}b\Leftrightarrow a=uv\text{ and }b=vu\text{ for some }u,v\in S$

In general, this relation is not transitive, so we denote the transitive
closure of this relation as $\sim_{p^{*}}$. For finite monoids, we define the
following notion of conjugacy, which is motivated by the representation theory
of semigroups [8]. We say $a\sim_{tr}b$ iff there are mutually inverse $g,h\in
S$ such that: $hg=a^{\omega}$, $gh=b^{\omega}$, and
$ga^{\omega+1}h=b^{\omega+1}$.

For inverse semigroups, we define a more general version of $\sim_{u}$.

$a\sim_{i}b\Leftrightarrow sas^{-1}=b\text{ and }s^{-1}bs=a\text{ for some
}s\in S$

For finite inverse semigroups, it is known that $\sim_{c}\,=\,\sim_{i}$ [3,
Cor 2.15] [2, Prop 2.11] and that the remaining conjugacy relations are
ordered by inclusion as follows:

$\sim_{u}\,\subseteq\,\sim_{i}\,\subseteq\,\sim_{p}\,\subseteq\,\sim_{p^{*}}\,\subseteq\,\sim_{tr}\,\subseteq\,\sim_{o}\,\text{\cite[cite]{[\@@bibref{}{AK:FN}{}{},
Fig 1.1]}},$

This paper will be investigating the computational complexity of decision
problems in which we are given a set of partial bijections
$\\{a_{1},\dots,a_{k}\\}$ and asked to check some property of the generated
inverse semigroup. Note that each partial bijection has a unique inverse and,
for any composition of partial bijections $s_{1}\cdots s_{k}$, its unique
inverse is $s_{k}^{-1}\cdots s_{1}^{-1}$. So, the inverse semigroup generated
by $a_{1},\dots,a_{k}$ is the partial bijection semigroup generated by
$a_{1},\dots,a_{k},a_{1}^{-1},\dots,a_{k}^{-1}$, which we denote as $\langle
a_{1},\dots,a_{k},a_{1}^{-1},\dots,a_{k}^{-1}\rangle$.

Our analysis will reference complexity classes from the following hierarchy:

$\mathsf{AC}^{0}\subseteq\mathsf{L}\subseteq\mathsf{NL}\subseteq\mathsf{P}\subseteq\mathsf{PSPACE}\subseteq\mathsf{EXPTIME}.$

$\mathsf{AC}^{0}$ is the class of sets decidable by unbounded fan-in Boolean
circuits of constant depth. Equivalently, $\mathsf{AC}^{0}$ is the class of
first-order definable properties [7]. Hence, it includes all decision problems
in which we are given generators $a_{1},\dots,a_{k}\in I_{n}$ and asked to
check a property that can be characterized by a first-order formula quantified
over the points $[n]$ and the generators $\\{a_{1},\dots,a_{k}\\}$. Note that
we are not allowed to quantify over all generated elements of the semigroup.
$\mathsf{L}$ ($\mathsf{NL}$) is the class of sets decidable by a deterministic
(nondeterministic) Turing machine using at most logarithmic space.
$\mathsf{P}$ ($\mathsf{PSPACE}$) consist of sets that are decidable by a
deterministic Turing machine in polynomial time (space). We refer the reader
to [11] for further background on computational complexity and to [4] and [6]
for further background on semigroup theory.

##  3\. First-Order Definable Properties for Inverse Semigroups

Since every finite inverse semigroup is isomorphic to a finite partial
bijection semigroup, problems for the former cannot be harder than they are
for the latter. The following problems are discussed in [9], where relevant
definitions for these results can be found. In particular, the complexity
class $\mathsf{AC}^{0}$ corresponds to properties that can be characterized by
first-order formulas quantified over points $[n]$ and generators
$a_{1},\dots,a_{k}\in I_{n}$. Combining results from [5] and [9], we obtain
the following.

######  Corollary 3.1.

Checking if a finite inverse semigroup given by generators in $I_{n}$:

  1. (1)

is commutative is in $\mathsf{AC}^{0}$ by [5, Thm 3.2],

  2. (2)

is a semilattice is in $\mathsf{AC}^{0}$ by [5, Thm 3.3],

  3. (3)

is a group is in $\mathsf{AC}^{0}$ by [5, Thm 3.5],

  4. (4)

has a left identity is in $\mathsf{AC}^{0}$ by [9, Thm 3.2],

  5. (5)

has a right identity is in $\mathsf{AC}^{0}$ by [9, Thm 3.3],

  6. (6)

is completely regular is in $\mathsf{AC}^{0}$ by [9, Thm 3.5], and

  7. (7)

is Clifford is in $\mathsf{AC}^{0}$ by [9, Cor 3.6].

We now consider four problems that are known to be $\mathsf{NL}$-complete for
transformation semigroups, but are much simpler for inverse semigroups. The
input for each of the problems are generators for a semigroup. The respective
outputs for the four problems are whether the generated semigroup: (1) is
nilpotent, (2) is $\mathrel{\mathcal{R}}$-trivial, (3) has central
idempotents, and (4) has a zero element.

That the first three problems are $\mathsf{NL}$-complete for transformation
semigroups is essentially a consequence of [5, Lem 4.9] and [5, Lem 4.12]. We
now adapt the proofs of those lemmas to prove that the first three problems
remain $\mathsf{NL}$-complete even for partial bijection semigroups. We shall
be reducing from the $\mathsf{NL}$-complete problem of checking if a directed
graph is acyclic.

######  Lemma 3.2.

There exists a logspace transducer which, given a directed graph $G=(V,E)$,
produces a partial bijection semigroup $S\leq I_{V}$ with the following
properties:

  1. (1)

If the graph is acyclic, then every square in $S$ is the zero element.

  2. (2)

If the graph is not acyclic, then the semigroup is not
$\mathrel{\mathcal{R}}$-trivial and there exists an idempotent that is not
central.

###### Proof.

For each edge $(u,v)\in E$, define a partial bijection $a_{(u,v)}$ such that
$\mathrm{dom}(a_{(u,v)})=\\{u\\}$ and $ua_{(u,v)}=v$. If $G$ is acyclic, then
for any $s=a_{(u_{1},v_{1})}\cdots a_{(u_{m},v_{m})}$, either $u_{1}\neq
v_{m}$ or $v_{\ell}\neq u_{\ell+1}$ for some $\ell\in[m-1]$. In either case,
$s^{2}$ has empty domain. If $G$ contains a cycle $v_{0},\dots,v_{\ell}$ with
$(v_{i-1},v_{i})\in E$ for all $i\in[\ell]$ and with $v_{0}=v_{\ell}$, then
the element $s=a_{(v_{0},v_{1})}\cdots a_{(v_{\ell-1},v_{\ell})}$ is the
identity on $v_{0}$ and is undefined on all other points. Therefore, $s$ is
idempotent. Note that $a_{(v_{0},v_{1})}s$ is the zero element but
$sa_{(v_{0},v_{1})}$ is not, which means that $s$ is not central. Moreover,
$s\mathrel{\mathcal{R}}sa_{(v_{0},v_{1})}$ and, since the graph has no self-
loops, $s\neq sa_{(v_{0},v_{1})}$. Thus $S$ is not
$\mathrel{\mathcal{R}}$-trivial. ∎

######  Theorem 3.3.

Given generators for a partial bijection semigroup $S$, each of the following
problems is $\mathsf{NL}$-complete:

  1. (1)

checking if $S$ is nilpotent;

  2. (2)

checking if $S$ is $\mathrel{\mathcal{R}}$-trivial; and

  3. (3)

checking if every idempotent in $S$ is central.

###### Proof.

Each of these problems are in $\mathsf{NL}$ since they are in $\mathsf{NL}$
for transformation semigroups [5]. For $\mathsf{NL}$-hardness, we argue that
Lemma 3.2 reduces the problem of directed graph acyclicity to checking any of
the three aforementioned properties. If the graph is acyclic, then by Lemma
3.2, $s^{2}=0$ for every $s\in S$ and $E(S)=\\{0\\}$. Since $S$ is finite, $S$
is nilpotent. Since every nilpotent semigroup is
$\mathrel{\mathcal{R}}$-trivial, then $S$ is $\mathrel{\mathcal{R}}$-trivial.
Since the zero element is central, all of the idempotents in $S$ are central.
Conversely, if the graph is not acyclic, then by Lemma 3.2, $S$ is not
$\mathrel{\mathcal{R}}$-trivial and $S$ has some non-central idempotent $e$.
Since the zero element is central, $e^{d}=e\neq 0$ for every $d\in\mathbb{N}$
and $S$ is not nilpotent. ∎

Although the first three problems remain $\mathsf{NL}$-complete for partial
bijection semigroups, checking zero membership can be solved in deterministic
logspace. For a set of partial bijections $A=\\{a_{1},\dots,a_{k}\\}\subseteq
I_{n}$, define the _t_ ransformation graph $\Gamma(A,[n+1])$ to have vertices
$[n+1]$ and undirected edges as follows: (1) $(p,q)\in[n]^{2}$ if either
$pa_{i}=q$ or $qa_{i}=p$ for some $i\in[k]$ and (2) $(p,n+1)$ if
$p\in[n]\setminus\mathrm{dom}(a_{i})$ for some $i\in[k]$.

######  Lemma 3.4.

Let $A:=\\{a_{1},\dots,a_{k}\\}\subseteq I_{n}$ and let $S$ be the partial
bijection semigroup generated by the elements of $A$. Then $S$ has a zero
element iff the only connected component of $\Gamma(A,[n+1])$ containing more
than one vertex is the component containing $n+1$.

###### Proof.

$\Rightarrow$: Let $0=a_{i_{1}}\cdots a_{i_{m}}$ be the zero element of $S$.
We claim that the only connected component of $\Gamma(A,[n+1])$ that contains
more than one vertex is the connected component containing $n+1$. Pick any
edge $(p,q)\in[n]^{2}$ in the graph of $\Gamma(A,[n+1])$ such that $p\neq q$.
Let $a\in\\{a_{1},\dots,a_{k}\\}$ be the generator such that, WLOG, $pa=q$. If
$q\in\mathrm{dom}(0)$, $q0=pa0=p0$ contradicting that $0$ is a partial
bijection. Therefore, $q\not\in\mathrm{dom}(0)$, which means there exists
$\ell\in[m]$ such that $qa_{i_{1}}\cdots
a_{i_{\ell-1}}\not\in\mathrm{dom}(a_{i_{\ell}})$. That is, $q$ is connected to
$n+1$ in $\Gamma(A,[n+1])$.

$\Leftarrow$: Let $\\{x_{1},\dots,x_{m}\\}\subseteq[n+1]$ be the connected
component containing $n+1$ and assume every other connected component has
exactly one vertex. We first claim that for every point $x$ in the connected
component of $n+1$, there exists $s\in S$ such that $x\not\in\mathrm{dom}(s)$.
Let $(x,y_{1}),(y_{1},y_{2}),\dots,(y_{m},n+1)$ be a path from $x$ to $n+1$.
Then there exist generators $a_{i_{1}},\dots,a_{i_{m+1}}$ such that
$xa_{i_{1}}\cdots a_{i_{m}}=y_{m}$ and
$y_{m}\not\in\mathrm{dom}(a_{i_{m+1}})$. Thus,
$x\not\in\mathrm{dom}(a_{i_{1}}\cdots a_{i_{m+1}})$.

Let $s\in S$ be such that $|\\{x_{1},\dots,x_{m}\\}\cap\mathrm{dom}(s)|$ is of
minimal size and suppose for the sake of contradiction that some point
$x_{i}\in\\{x_{1},\dots,x_{m}\\}\cap\mathrm{dom}(s)$. Then because
$\\{x_{1},\dots,x_{m}\\}$ is a connected component,
$x_{i}s\in\\{x_{1},\dots,x_{m}\\}$. By the claim proved above, there exists
$s_{i}\in S$ such that $x_{i}s\not\in\mathrm{dom}(s_{i})$. But then
$|\\{x_{1},\dots,x_{m}\\}\cap\mathrm{dom}(s)|>|\\{x_{1},\dots,x_{m}\\}\cap\mathrm{dom}(ss_{i})|$,
contradicting the choice of $s$. Thus,
$\\{x_{1},\dots,x_{m}\\}\cap\mathrm{dom}(s)=\emptyset$. We now want to prove
that this $s$ is the zero element for $S$. Note that in a partial bijection
semigroup, any right zero is also a left zero, so it is enough to show that
$s$ is a right zero.

Since $\\{x_{1},\dots,x_{m}\\}$ is a connected component,
$x_{i}a_{j}\in\\{x_{1},\dots,x_{m}\\}$ for each $i\in[m]$ and each $j\in[k]$.
Thus, $x_{i}\not\in\mathrm{dom}(a_{j}0)$. Now consider any
$x\not\in\\{x_{1},\dots,x_{m}\\}$. Because it is not connected to any other
point, it is fixed by every generator, so $xa_{i}0=x0$. ∎

######  Theorem 3.5.

Given generators $a_{1},\dots,a_{k}\in I_{n}$, there is a deterministic
logspace algorithm for checking if the generated partial bijection semigroup
has a zero.

###### Proof.

By Lemma 3.4, we need only check that every connected component of
$\Gamma(\\{a_{1},\dots,a_{k}\\},[n+1])$ contains exactly one vertex except
perhaps the component containing $n+1$. We can do this by checking that each
vertex $x\in[n]$ and each edge $(a,b)$ satisfies the following expression: if
$x=a$ and $x\neq b$, then $x$ is connected to $n+1$. We only need $3\log(n)$
space to store $x$, $a$, and $b$. We only need logarithmic space to run
Reingold’s algorithm to check if $x$ is connected to $n+1$ [12]. ∎

We now consider these problems in the context of inverse semigroups. Since
inverse semigroups are regular and the only regular nilpotent semigroup is the
trivial semigroup, checking nilpotency for inverse semigroups is trivial. For
two elements of an inverse semigroup $a,b\in S$: (1) $a\mathrel{\mathcal{R}}b$
iff $\mathrm{dom}(a)=\mathrm{dom}(b)$ and (2) $a\mathrel{\mathcal{L}}b$ iff
$[n]a=[n]b$ [6, Prop 5.1.2]. This immediately yields the following results.

######  Theorem 3.6.

Given generators $a_{1},\dots,a_{k}\in I_{n}$ and
$\mathrel{\mathcal{I}}\,\in\\{\mathrel{\mathcal{R}},\mathrel{\mathcal{L}},\mathrel{\mathcal{H}}\\}$,
checking whether $a_{1}\mathrel{\mathcal{I}}a_{2}$ in the generated inverse
semigroup is in $\mathsf{AC}^{0}$.

Furthermore, every $\mathrel{\mathcal{R}}$-($\mathrel{\mathcal{L}}$-)class in
a regular semigroup has an idempotent, so a regular semigroup is
$\mathrel{\mathcal{R}}$-($\mathrel{\mathcal{L}}$-)trivial iff each of its
elements is idempotent. The idempotents in inverse semigroups commute, so an
inverse semigroup is $\mathrel{\mathcal{R}}$-($\mathrel{\mathcal{L}}$-)trivial
iff it is a semilattice, which places the problem in $\mathsf{AC}^{0}$ by Cor
3.1.

######  Corollary 3.7.

Given generators $a_{1},\dots,a_{k}\in I_{n}$, checking if the generated
inverse semigroup is $\mathrel{\mathcal{R}}$-trivial or
$\mathrel{\mathcal{L}}$-trivial are both in $\mathsf{AC}^{0}$.

######  Lemma 3.8.

Let $S$ be the inverse semigroup generated by $a_{1},\dots,a_{k}\in I_{n}$.
Then all of the idempotents of $S$ are central iff $S$ is completely regular.

###### Proof.

$\Rightarrow$: Since $ss^{-1}$ is idempotent and $ss^{-1}s=s$, then
$sss^{-1}=s$. Thus, $s$ permutes its image and generates a subgroup.

$\Leftarrow$: The proof of [9, Thm 3.5] demonstrates that a partial bijection
semigroup is completely regular iff
$\mathrm{dom}(s_{1}s_{2})=\mathrm{dom}(s_{1})\cap\mathrm{dom}(s_{2})$ for
every $s_{1},s_{2}\in S$. Thus, for any idempotent $e\in S$,
$\mathrm{dom}(es)=\mathrm{dom}(se)$. Since $e$ fixes its domain and range,
$es=se$. ∎

######  Theorem 3.9.

Given generators $a_{1},\dots,a_{k}\in I_{n}$, checking whether every
idempotent in the generated inverse semigroup is central is in
$\mathsf{AC}^{0}$.

###### Proof.

This follows immediately from Corollary 3.1 and Lemma 3.8. ∎

##  4\. Decision Problems Involving Conjugacy

The preceding results have immediate applications to results from [2] and [3].

######  Corollary 4.1.

Given generators $a_{1},\dots,a_{k}\in T_{n}$, let $S$ be the generated
transformation semigroup. Both of the following problems are in
$\mathsf{AC}^{0}$: (a) checking if $\sim_{o}$ is the identity relation on $S$
and (b) checking if $\sim_{p^{*}}$ is the identity relation on $S$.

###### Proof.

First recall that the problems of checking if a transformation semigroup is
commutative or if it is a group are both in $\mathsf{AC}^{0}$ by [5, Thm 3.2]
and [5, Thm 3.5]. By [3, Cor 5.8], $\sim_{o}$ is the identity relation iff $S$
is a commutative group. By [3, Thm 5.4], $\sim_{p}$ is the identity relation
iff $S$ is commutative. Of course, $\sim_{p}$ is the identity relation iff its
transitive closure is. ∎

######  Corollary 4.2.

Given generators $a_{1},\dots,a_{k}\in I_{n}$, the problem of checking if
$\sim_{i}$ is the identity relation for the generated inverse semigroup $S$ is
in $\mathsf{AC}^{0}$.

###### Proof.

By [2, Thm 5.9], $\sim_{i}$ is the identity relation iff $S$ is commutative
and checking if $S$ is commutative is in $\mathsf{AC}^{0}$ by [5, Thm 3.2]. ∎

######  Corollary 4.3.

Given generators $a_{1},\dots,a_{k}\in T_{n}$, checking if $\sim_{tr}$ is the
identity relation on the generated semigroup is in $\mathsf{NL}$. For partial
bijection semigroups, this problem is in $\mathsf{AC}^{0}$.

###### Proof.

By [3, Thm 5.5], $\sim_{tr}$ is the identity relation iff the generated
semigroup is commutative and completely regular. The latter condition can be
checked in $\mathsf{NL}$ by [5, Thm 5.6]. For partial bijection semigroups,
this condition can be checked in $\mathsf{AC}^{0}$ by [9, Thm 3.5]. ∎

We know that for any two elements $a,b\in I_{n}$, $a\sim_{i}b$ in $I_{n}$ iff
$a$ and $b$ have the same cycle-chain type [2, Thm 2.10]. Similarly,
$a\sim_{p^{*}}b$ iff $a\sim_{tr}b$ iff $a$ and $b$ have the same cycle type
[10, Thm 10]. The authors in [10, Lemma 14] prove that $a\sim_{p}b$ iff (1)
$|\Delta_{a}^{k}|=|\Delta_{b}^{k}|$ for each $k\in[n]$ and (2) there exists a
partial bijection between their chains satisfying several conditions. We now
prove a modified version of those conditions to obtain a polynomial-time
algorithm to check if $a\sim_{p}b$.

For any $a,b\in I_{n}$, let $\phi:\Theta_{a}^{>1}\hookrightarrow\Theta_{b}$
and $\psi:\Theta_{b}^{>1}\hookrightarrow\Theta_{a}$. We call $(\phi,\psi)$ a
_satisfying pair_ if $|\theta|\leq|\phi(\theta)|+1$ and
$|\theta^{\prime}|\leq|\psi(\theta^{\prime})|+1$ for every
$\theta\in\Theta_{a}^{>1}$ and every $\theta^{\prime}\in\Theta^{>1}$. The pair
is an _inversive satisfying pair_ if, additionally, $\phi\circ\psi$ and
$\psi\circ\phi$ are both idempotent.

######  Lemma 4.4.

For any $a,b\in I_{n}$, the following are equivalent:

  1. (1)

$a\sim_{p}b$ in $I_{n}$;

  2. (2)

$|\Delta_{a}^{k}|=|\Delta_{b}^{k}|$ for each $k\in[n]$ and there exists a
satisfying pair; and

  3. (3)

$|\Delta_{a}^{k}|=|\Delta_{b}^{k}|$ for each $k\in[n]$ and there exists an
inversive satisfying pair.

###### Proof.

$(1)\Rightarrow(2)$: Let $a=uv$ and $b=vu$ for some $u,v\in I_{n}$. Pick any
$1\leq k\leq n$ and any $(x_{1}\,\dots\,x_{k})\in\Delta_{a}^{k}$. Then
$x_{k}uvu=x_{1}u$ and, for each $i<k$, $x_{i}uvu=x_{i+1}u$. That is,
$(x_{1}u\,\dots\,x_{k}u)\in\Delta_{b}^{k}$. Because $u$ is a partial
bijection, we know that for any other
$(y_{1}\,\dots\,y_{k})\in\Delta_{a}^{k}$, $(x_{1}u\,\dots\,x_{n}u)$ and
$(y_{1}u\,\dots\,y_{k}u)$ are distinct cycles of $b$. Thus, $u$ can be
considered an injective map from $\Delta_{a}^{k}$ to $\Delta_{b}^{k}$.
Symmetrically, $v$ is an injective map from $\Delta_{b}^{k}$ to
$\Delta_{a}^{k}$, so $|\Delta_{a}^{k}|=|\Delta_{b}^{k}|$.

Pick any $1<k\leq n$ and any $[x_{1}\,\dots\,x_{k}]\in\Theta_{a}^{k}$. Then
for each $1\leq i<k-1$, $x_{i}uvu=x_{i+1}u$. Because
$x_{k}\not\in\mathrm{dom}(a)$, then $x_{k}\not\in\mathrm{dom}(u)$ or
$x_{k}u\not\in\mathrm{dom}(vu)$. Thus, $u$ induces a map
$\phi:\Theta_{a}^{>1}\rightarrow\Theta_{b}$ such that for each
$\theta\in\mathrm{dom}(\phi)$, $|\theta|\leq|\phi(\theta)|+1$. Symmetrically,
$v$ induces a map $\psi:\Theta_{b}^{>1}\rightarrow\Theta_{a}$ such that for
each $\theta\in\mathrm{dom}(\psi)$, $|\theta|\leq|\psi(\theta)|+1$. That these
maps are injective follows from $u$ and $v$ being partial bijections.

$(2)\Rightarrow(3)$: Let $\phi$ and $\psi$ be a satisfying pair. We prove by
induction on the size of $|\Theta_{a}^{>1}|+|\Theta_{b}^{>1}|$ that the
existence of a satisfying pair implies existence of an inversive satisfying
pair. If either $\Theta_{a}^{>1}$ or $\Theta_{b}^{>1}$ is empty, then any
satisfying pair will already be an inversive satisfying pair since the
compositions will have empty domain. Suppose an inversive pair $(\phi,\psi)$
exists for $a$ and $b$. Pick a maximal length chain
$\theta_{a}\in\Theta_{a}^{>1}$ and a maximal length chain
$\theta_{b}\in\Theta_{b}^{>1}$. We want $\phi(\theta_{a})=\theta_{b}$ and
$\psi(\theta_{b})=\theta_{a}$. If this is not already true, we will redefine
$\phi$ and $\psi$ in such a way that $(\phi,\psi)$ remains a satisfying pair.

Let $\eta_{a}:=\phi(\theta_{a})$ and $\eta_{b}:=\psi(\theta_{b})$. If there
exists $\theta_{a}^{\prime}\in\Theta_{a}^{>1}$ such that
$\phi(\theta_{a}^{\prime})=\theta_{b}$, define $\phi(\theta_{a}):=\theta_{b}$
and $\phi(\theta_{a}^{\prime}):=\eta_{a}$. Since $\theta_{a}$ is of maximal
length, $|\theta_{a}^{\prime}|\leq|\theta_{a}|$. Since $(\phi,\psi)$ is a
satisfying pair, $|\theta_{a}|\leq|\eta_{a}|+1$. Since $\theta_{b}$ is of
maximal length, $|\theta_{a}|\leq|\eta_{a}|+1\leq|\theta_{b}|+1$. If there is
no $\theta_{a}^{\prime}\in\Theta_{a}^{>1}$ such that
$\phi(\theta_{a}^{\prime})=\theta_{b}$, simply define
$\phi(\theta_{a}):=\theta_{b}$. Likewise, if there exists
$\theta_{b}^{\prime}\in\Theta_{b}^{>1}$ such that
$\psi(\theta_{b}^{\prime})=\theta_{a}$, then swap the images of
$\psi(\theta_{b})$ and $\psi(\theta_{b}^{\prime})$. If no such
$\theta_{b}^{\prime}$ exists, simply define $\psi(\theta_{b}):=\theta_{a}$. We
now have a satisfying pair $(\phi,\psi)$ such that
$\phi(\theta_{a})=\theta_{b}$ and $\psi(\theta_{b})=\theta_{a}$.

Let $a^{\prime}$ be equal to $a$ restricted to $[n]\setminus\theta_{a}$ and
$b^{\prime}$ be equal to $b$ restricted to $[n]\setminus\theta_{b}$.
Restricting $\phi$ to $\Theta_{a}^{>1}\setminus\\{\theta_{a}\\}$ and $\psi$ to
$\Theta_{b}^{>1}\setminus\\{\theta_{b}\\}$ yields a satisfying pair for
$a^{\prime}$ and $b^{\prime}$. By the induction hypothesis, there exists an
inversive satisfying pair $(\phi^{\prime},\psi^{\prime})$ for $a^{\prime}$ and
$b^{\prime}$. Extend these maps by defining
$\phi^{\prime}(\theta_{a}):=\theta_{b}$ and $\psi(\theta_{b}):=\theta_{a}$.
Now $(\phi^{\prime},\psi^{\prime})$ is an inversive satisfying pair for $a$
and $b$.

$(3)\Rightarrow(1)$: We will use the conditions on the cycles and the
inversive satisfying pair $(\phi,\psi)$ to construct $u$ and $v$ such that
$a=uv$ and $b=vu$. For any $1\leq k\leq n$, the cycle condition ensures that
we can define a bijection $f:\Delta_{a}^{k}\rightarrow\Delta_{b}^{k}$. For
each $(x_{1}\dots x_{k})\in\Delta_{a}^{k}$, define $u$ such that
$f((x_{1}\dots x_{k}))=(x_{1}u\dots x_{k}u)$. Although there are $k$ ways to
define $u$ in this way, any of them will suffice. For each of these $k$
options, we can define $v$ such that $x_{k}uv=x_{1}$ and $x_{i}uv=x_{i+1}$ for
each $1\leq i<k$. Then $(x_{1}\dots x_{k})\in\Delta_{uv}^{k}$ and
$f((x_{1}\dots x_{k}))\in\Delta_{vu}^{k}$. That is, $\Delta_{a}=\Delta_{uv}$
and $\Delta_{b}=\Delta_{vu}$.

We will use the inversive satisfying pair $(\phi,\psi)$ to continue
constructing $u$ and $v$ by the following algorithm.

Step 1. Define $C$ to be the chains in the disjoint union of $\Theta_{a}^{>1}$
and $\Theta_{b}^{>1}$.

Step 2. Pick a maximal length chain $\theta\in C$.

Step 3(u). Suppose $\theta=[x_{1}\dots x_{k}]\in\Theta_{a}^{>1}$. If
$|\phi(\theta)|=|\theta|$, define $u$ so that $\phi(\theta)=[x_{1}u\dots
x_{k}u]$. If $|\phi(\theta)|=|\theta|-1$, let $x_{k}u$ be undefined. Define
$v$ to satisfy $x_{i}uv=x_{i+1}$ for each $1\leq i<k$.

Step 3(v). If $\theta\in\Theta_{b}^{>1}$, execute Step 3(u) with $u$ and $v$
transposed and replacing $\phi$ with $\psi$.

Step 4. Remove $\theta$ from $C$. If Step 3(u) (3(v), resp.) was just
executed, let $C:=C\setminus\\{\phi(\theta)\\}$ ($\\{\psi(\theta)\\}$, resp.).
If $C$ is not empty, return to Step 2.

We first claim that the two cases considered in Step 3(u) are the only
possible cases. Certainly, the claim is true if $|\phi(\theta)|=1$, so we need
only consider when $\phi(\theta)\in C$ at the start of the algorithm. Because
$(\phi,\psi)$ is a satisfying pair, we know $|\theta|\leq|\phi(\theta)|+1$. If
we prove that $\theta$ is picked in Step 3(u) only if $\phi(\theta)$ is
removed from $C$ in Step 4 of that same iteration of the algorithm, then the
maximality of $\theta$ finishes the proof of our claim.

Suppose $\phi(\theta)$ is removed from $C$ in Step 4 of the $m^{th}$ iteration
of the algorithm. If Step 3(u) was invoked in the $m^{th}$ iteration, then the
injectivity of $\phi$ ensures that $\theta$ was picked during this iteration.
If Step 3(v) was invoked in the $m^{th}$ iteration, then $(\phi,\psi)$ being
an inversive satisfying pair ensures that $\psi(\phi(\theta))=\theta$ will
also be removed so that $\theta$ will not be picked in a subsequent iteration
of Step 3(u).

We now verify that $\Theta_{uv}^{k}=\Theta_{a}^{k}$ and
$\Theta_{vu}^{k}=\Theta_{b}^{k}$ for each $1<k\leq n$, which completes the
proof. The only way $uv$ is defined on a chain $\theta\in\Theta_{uv}^{k}$ is
if Step 2 picked $\theta$ from $\Theta_{a}^{k}$ or $\psi^{-1}(\theta)$ from
$\Theta_{b}^{>1}$. In either case, $\theta\in\Theta_{a}^{k}$. For converse
containment, pick any $\theta=[x_{1},\dots,x_{k}]\in\Theta_{a}^{k}$ and note
that, in order to be removed from $C$ in Step 4, either $\theta$ is picked in
Step 2 or $\theta=\psi(\theta^{\prime})$ for some
$\theta^{\prime}\in\Theta_{b}^{>1}$ picked in Step 2. If $\theta$ is picked,
Step 3(u) defines $x_{i}uv=x_{i+1}$ for each $1\leq i<k$ and leaves $x_{k}uv$
undefined. Thus, $\theta\in\Theta_{uv}^{k}$.

If $\theta$ is not picked, there exists a
$\theta^{\prime}=[y_{1},\dots,y_{\ell}]\in\Theta_{b}^{>1}$ such that
$\theta=\psi(\theta^{\prime})$ and $\ell=k$ or $\ell=k+1$. Step 3(v) defines
$y_{i}v=x_{i}$ and $y_{i}vu=y_{i+1}$ for $i\in[\ell-1]$. Consequently,
$x_{i}uv=y_{i}vuv=y_{i+1}v=x_{i+1}$ for each $i\in[\ell-1]$. If $\ell=k$,
$y_{k}v=x_{k}$, but $x_{k}u$ is left undefined. If $\ell=k+1$, then Step 3(v)
omits $y_{k+1}$ from the domain of $v$. Thus, $y_{k}vu\not\in\mathrm{dom}(v)$
and $x_{k}\not\in\mathrm{dom}(uv)$. Hence, $\theta\in\Theta_{uv}^{k}$ and
$\Theta_{uv}^{k}=\Theta_{a}^{k}$. By analogous argument,
$\Theta_{vu}^{k}=\Theta_{b}^{k}$. ∎

######  Theorem 4.5.

Given $a,b\in I_{n}$, there exist polynomial time algorithms to check each of
the following in $I_{n}$: $a\sim_{i}b$, $a\sim_{p}b$, $a\sim_{p^{*}}b$, and
$a\sim_{tr}b$.

###### Proof.

For $\sim_{c}$, $\sim_{p^{*}}$, and $\sim_{tr}$, we need only enumerate the
cycles and chains. Certainly this can be done in linear time simply by
tracking how $a$ and $b$ act on $[n]$. To check $\sim_{p}$, again we check
that the cycles match and then we run Algorithm 1 to check whether there
exists an inversive satisfying pair.

_Correctness:_ If Algorithm 1 accepts, the pairings it chooses for the chains
in $\Theta_{a}$ and $\Theta_{b}$ will yield an inversive satisfying pair. For
each iteration of lines 10-16 (17-22, resp.), define
$\phi(\theta)=\theta^{\prime}$ ($\psi(\theta)=\theta^{\prime}$, resp.). If
$|\theta^{\prime}|>1$, define $\psi(\theta^{\prime})=\theta$
($\phi(\theta^{\prime})=\theta$, resp.). Lines 10-12 and 17-19 ensure that
$\phi$ and $\psi$ have correct domain and range. Lines 13-16 and 20-23 ensure
that $(\phi,\psi)$ is an inversive satisfying pair.

We prove the other direction by induction on the size of
$C=\Theta_{a}^{>1}\sqcup\Theta_{b}^{>1}$. Certainly, the algorithm accepts if
$|C|=0$. Assume that whenever $|C|\leq n$, the existence of an inversive
satisfying pair implies the algorithm accepts. Suppose there exists an
inversive satisfying pair $(\phi,\psi)$ for $a,b\in I_{n}$ with corresponding
$|C|=n+1$. WLOG, let $\theta\in\Theta_{a}$ and $\theta^{\prime}$ be the first
chains chosen by the algorithm in lines 9 and 13. Since $(\phi,\psi)$ is a
satisfying pair, $\phi(\theta)\in(C\cap\Theta_{b})\cup B$ and
$\theta\leq|\phi(\theta)|+1$. Since the algorithm picks a maximal
$\theta^{\prime}$, then $|\theta|\leq|\phi(\theta)|+1\leq|\theta^{\prime}|+1$.
The algorithm then removes $\theta$ and $\theta^{\prime}$ from their
respective sets so that $C$ now has chains from elements $a^{\prime}$ and
$b^{\prime}$ obtained by restricting $a$ to $[n]\setminus\theta$ and $b$ to
$[n]\setminus\theta^{\prime}$. We now show that an inversive satisfying pair
exists for $a^{\prime}$ and $b^{\prime}$ and thus, by inductive hypothesis,
the algorithm accepts.

If $\phi(\theta)=\theta^{\prime}$, then $(\phi,\psi)$ restricted to $C$ will
be an inversive satisfying pair. If $\phi(\theta)\neq\theta^{\prime}$, we
consider two cases. If there is no $\eta\in\Theta_{a}^{>1}$ such that
$\phi(\eta)=\theta^{\prime}$, then because $(\phi,\psi)$ is an inversive
satisfying pair, $|\theta^{\prime}|=1$ and $(\phi,\psi)$ restricted to $C$
will be an inversive satisfying pair. If there exists $\eta\in\Theta_{a}^{>1}$
such that $\phi(\eta)=\theta^{\prime}$, then redefine
$\phi(\eta):=\phi(\theta)$ and $\psi(\phi(\theta)):=\eta$. Since $\theta$ is
maximal and $(\phi,\psi)$ was a satisfying pair,
$|\eta|\leq|\theta|\leq|\phi(\theta)|+1=|\phi(\eta)|+1$. Likewise, since
$\theta^{\prime}$ is also maximal,
$|\phi(\theta)|\leq|\theta^{\prime}|\leq|\psi(\theta^{\prime})|+1=|\eta|+1$.
So, $(\phi,\psi)$ restricted to $C$ is now an inversive satisfying pair.

_Runtime:_ As previously noted, Line 1 will execute in linear time. The size
of $C$ is at most $n$. Each complete iteration of the while loop removes
either one or two chains from $C$. Each iteration picks maximal elements in
linear time. Thus, the algorithm accepts or rejects in polynomial time. ∎

Algorithm 1 $\mathsf{P}$ algorithm to check if $a\sim_{p}b$ in $I_{n}$

1:$a,b\in I_{n}$

2:Is $a\sim_{p}b$ in $I_{n}$?

3:Enumerate the cycles of $a$ and $b$: $\Delta_{a}$ and $\Delta_{b}$

4:for $k\in[n]$ do

5: if $|\Delta_{a}^{k}|\neq|\Delta_{b}^{k}|$ then reject

6: end if

7:end for

8:Enumerate the chains of $a$ and $b$: $\Theta_{a}$ and $\Theta_{b}$

9:Let $C$ be the disjoint union of $\Theta_{a}^{>1}$ and $\Theta_{b}^{>1}$

10:while $C$ is nonempty do

11: Pick a maximal length $\theta\in C$

12: if $\theta\in\Theta_{a}$ then

13: if $(C\cap\Theta_{b})\cup\Theta_{b}^{1}$ is empty then reject

14: end if

15: Pick a maximal length
$\theta^{\prime}\in(C\cap\Theta_{b})\cup\Theta_{b}^{1}$

16: if $|\theta|>|\theta^{\prime}|+1$ then reject

17: end if

18: Remove $\theta$ from $C$ and $\theta^{\prime}$ from $C\cup\Theta_{b}^{1}$

19: else

20: if $(C\cap\Theta_{a})\cup\Theta_{a}^{1}$ is empty then reject

21: end if

22: Pick a maximal length
$\theta^{\prime}\in(C\cap\Theta_{a})\cup\Theta_{a}^{1}$

23: if $|\theta|>|\theta^{\prime}|+1$ then reject

24: end if

25: Remove $\theta$ from $C$ and $\theta^{\prime}$ from $C\cup\Theta_{a}^{1}$

26: end if

27:end while

28:accept

For an inverse monoid $S$, [2, Cor 4.2] proves that ${\sim_{u}}={\sim_{i}}$
iff $S$ is factorizable. Thus, we are interested in the complexity of the
following problem.

Factorizable

  * •

Input: $a_{1},\dots,a_{k}\in I_{n}$.

  * •

Problem: Is $\langle a_{1},\dots,a_{k},a_{1}^{-1},\dots,a_{k}^{-1},1\rangle$
factorizable?

######  Theorem 4.6.

Factorizable is in $\mathsf{P}$.

###### Proof.

Let $S$ be an inverse monoid and suppose $s,t\in S$ factor as $s=ue$ and
$t=vf$ for units $u$ and $v$ and idempotents $e$ and $f$. Then
$st=uevf=uevv^{-1}vf$. Since idempotents commute, $st=uvv^{-1}evf$. Since
$v^{-1}ev$ is idempotent and the composition of idempotents is an idempotent,
$st$ is also factorizable. Thus, an inverse semigroup given by generators is
factorizable iff each generator is factorizable. Consequently, it is
sufficient to describe a polynomial-time algorithm to check if a generator is
factorizable.

Suppose that $a=ue$ for a unit $u$ and an idempotent $e$. Then $xa=xue$ for
each $x\in\mathrm{dom}(a)$ and $xu\in\mathrm{dom}(e)$. Since idempotents fix
their domain, then $xa=xu$ for each $x\in\mathrm{dom}(a)$. Conversely, if
$xu=xa$ for every $x\in\mathrm{dom}(a)$, then $xua^{-1}a=xaa^{-1}a=xa$. Thus,
we can further restrict our attention on whether we can produce a unit $u$
that agrees with $a$ on its domain.

Because $U(S)$ is the topmost $\mathrel{\mathcal{J}}$-class, $S\setminus U(S)$
is an ideal and, consequently, each unit of $S$ is generated by
$U(S)\cap\\{a_{1},\dots,a_{k}\\}$. We can adapt Sims’ stabilizer chain
algorithm for testing membership in groups. Because we only care how $u$ acts
on $\mathrm{dom}(a)$, we use $\mathrm{dom}(a)$ as our base set and employ
Sim’s algorithm to produce a strong generating set (SGS) for the following
stabilizer chain. Let $A_{0}=\emptyset$, $A_{i+1}=A_{i}\cup\\{x\\}$ for some
$x\in\mathrm{dom}(a)\setminus A_{i}$, $S_{i}=\operatorname{Stab}(A_{i})\leq
U(S)$, and $S_{\ell}=\operatorname{Stab}(\mathrm{dom}(a))$ for
$\ell=|\mathrm{dom}(a)|$. A unit $u$ that agrees with $a$ on its domain will
exist iff sifting $a$ yields coset representatives $r_{i}\in S_{i}$ for each
$S_{i+1}$ such that $xa=xr_{1}\cdots r_{\ell}$ for each $x\in\mathrm{dom}(a)$.
Since each representative can be generated from the SGS in polynomial time and
since the SGS can be enumerated in polynomial time, we can check if $a$ is
factorizable in polynomial time. ∎

We now consider the following problems.

Membership in Inverse Semigroups

  * •

Input: $a_{1},\dots,a_{k},b\in I_{n}$.

  * •

Problem: Is $b\in\langle
a_{1},\dots,a_{k},a_{1}^{-1},\dots,a_{k}^{-1}\rangle$?

Idempotent Membership in Inverse Semigroups

  * •

Input: $a_{1},\dots,a_{k},b\in I_{n}$ with $b^{2}=b$.

  * •

Problem: Is $b\in\langle
a_{1},\dots,a_{k},a_{1}^{-1},\dots,a_{k}^{-1}\rangle$?

Subsemigroup $i$-Conjugacy

  * •

Input: $a_{1},\dots,a_{k}\in I_{n}$.

  * •

Problem: Is $a_{1}\sim_{i}a_{2}$ in $\langle
a_{1},\dots,a_{k},a_{1}^{-1},\dots,a_{k}^{-1}\rangle$?

It is known that Membership in Inverse Semigroups can by reduced in polynomial
time to Idempotent Membership in Inverse Semigroups [9, Thm 4.3]. We now
demonstrate a connection between all three of these problems.

Let $S=\langle a_{1},\dots,a_{k}\rangle\leq I_{n}$ be an inverse semigroup and
let $I_{A}$ be the semigroup of partial bijective maps on the set
$A:=[n]\times[n+1]$. For each $s\in S$, define $\bar{s}$ to be the element in
$I_{A}$ satisfying the following: $(x,y)\bar{s}=(xs,y)$. Pick an $h\in I_{n}$
and define $a,b\in I_{A}$ as follows:

$\displaystyle(x,y)a$ $\displaystyle=(x,y+1),\text{ if }y\leq x\text{ and
}x\in dom(h^{-1})$ $\displaystyle(x,y)b$ $\displaystyle=(x,y+1),\text{ if
}y\leq xh\text{ and }x\in dom(h)$

Define
$\bar{S}=\langle\bar{a}_{1},\dots,\bar{a}_{k},a,b,a^{-1},b^{-1}\rangle$.

######  Proposition 4.7.

$h\in S$ iff both $hh^{-1}\in S$ and $a\sim_{i}b$ in $\bar{S}$.

###### Proof.

$\Rightarrow$: First note that $a$ and $b$ are central, so $a\sim_{i}b$ in
$\bar{S}$ iff there exists
$\bar{g}\in\langle\bar{a}_{1},\dots,\bar{a}_{k}\rangle$ such that
$\bar{g}b\bar{g}^{-1}=a$ and $\bar{g}^{-1}a\bar{g}=b$.

Certainly if $h\in S$, then $hh^{-1}\in S$. We claim that
$\bar{h}a\bar{h}^{-1}=b$ and $\bar{h}^{-1}b\bar{h}=a$. Pick any $(x,y)$ with
$y\leq xh$ and $x\in dom(h)$. Then,

$\displaystyle(x,y)\bar{h}a\bar{h}^{-1}$ $\displaystyle=(xh,y)a\bar{h}^{-1}$
$\displaystyle=(xh,y+1)\bar{h}^{-1}$ $\displaystyle=(x,y+1)$
$\displaystyle=(x,y)b$

Pick any $(x,y)$ with $y\leq x$ and $x\in dom(h^{-1})$. Then,

$\displaystyle(x,y)\bar{h}^{-1}b\bar{h}$ $\displaystyle=(xh^{-1},y)b\bar{h}$
$\displaystyle=(xh^{-1},y+1)\bar{h}$ $\displaystyle=(x,y+1)$
$\displaystyle=(x,y)a$

$\Leftarrow$: Let $\bar{g}\in\bar{S}$ satisfy $\bar{g}a\bar{g}^{-1}=b$ and
$\bar{g}^{-1}b\bar{g}=a$. Pick any $x\in dom(h)$ and note that
$(x,xh+1)=(x,xh)b=(x,xh)\bar{g}a\bar{g}^{-1}=(xg,xh)a\bar{g}^{-1}$. Thus,
$xh\leq xg$ and $xg\in dom(h^{-1})$ for every $x\in dom(h)$.

We now prove by induction that for every $x\in\mathrm{dom}(h)$, $xg\leq xh$
and thus $xg=xh$. Order $\mathrm{dom}(h^{-1})=\\{x_{1}h,\dots,x_{\ell}h\\}$ so
that $x_{i}h<x_{j}h$ for every $i<j$. Since
$x_{\ell}g\in\mathrm{dom}(h^{-1})$, then $x_{\ell}g\leq x_{\ell}h$ and thus
$x_{\ell}g=x_{\ell}h$. Assume $x_{i}g=x_{i}h$ for every $i>j$. Then
$x_{j}g\in\\{x_{1}h,\dots,x_{j}h\\}$. Then $x_{j}g\leq x_{j}h$ and we have
that $xg=xh$ for every $x\in dom(h)$. Consequently, $h=hh^{-1}g\in S$. ∎

In summary, we know these problems are in $\mathsf{PSPACE}$, but whether this
bound is tight is an open question. We know that idempotent membership is a
$\mathsf{PSPACE}$-complete problem for partial bijection semigroups [9, Thm
4.1]. The following example indicates that checking idempotent membership in
inverse semigroups and $i$-conjugacy may also be hard.

######  Example 4.8.

Towers of Hanoi as an inverse semigroup.

The Towers of Hanoi puzzle starts with a tower of $n$ distinctly sized disks
on one of three pegs and the challenge is to move the tower to another peg
subject to two rules: only one disk may be moved at a time and each disk can
only rest on top of a larger disk. The following encodes this puzzle as an
inverse semigroup in such a way that the idempotent whose membership is being
tested corresponds to moving the disks from one peg to another. Consequently,
the minimum number of compositions to generate the idempotent will be
exponential in the number of generators and points.

The set of points $\\{1\\}\cup\\{(x,y):x\in[3],y\in[n]\\}$ represents $3n$
disk-positions for $n$ disks and an additional point to ensure the disks are
moved. For each $i\in[n]$, the generator $a_{i}$, ($b_{i}$, $c_{i}$)
corresponds to moving the $i^{th}$ disk from the first (first, second) peg to
the second (third, third) peg. These generators fix the point $1$. The
idempotents $d$ ($e$) fix only the points $\\{(1,y):y\in[n]\\}$
($\\{(2,y):y\in[n]\\})$.

$(x,y)a_{i}=\begin{cases}(2,i)&\text{if }x=1\text{ and }y=i\\\ (x,y)&\text{if
}x=3\text{ or }y>i\end{cases}$ $(x,y)b_{i}=\begin{cases}(3,i)&\text{if
}x=1\text{ and }y=i\\\ (x,y)&\text{if }x=2\text{ or }y>i\end{cases}$
$(x,y)c_{i}=\begin{cases}(3,i)&\text{if }x=2\text{ and }y=i\\\ (x,y)&\text{if
}x=1\text{ or }y>i\end{cases}$

Let $S$ be the inverse semigroup generated by the aforementioned generators
and $d$. Consider whether $e\in S$. Only $d$ excludes the point $1$, so
$e=s_{1}ds_{2}$ for some $s_{1},s_{2}\in S$. Note that $d$ and $e$ have
equally sized domains, so $s_{1}$ maps $\mathrm{dom}(e)$ to $\mathrm{dom}(d)$.
The puzzle arises from the domain limitations for the $a,b,c$ elements. Note
that each excludes disk-positions for disks of equal or lower size on the
source peg and the target peg. To preserve $(2,1)\in\mathrm{dom}(e)$, the
first generator for $s_{1}$ must be either $a_{1}^{-1}$ (to move top disk from
peg 2 to peg 1) or $c_{1}$ (to move top disk from peg 2 to peg 3) . Likewise,
each successive generator corresponds to choices for moving disks. Thus, $e$
can only be generated by properly moving the disks, requiring $2^{n}-1$
compositions. If we include $e$ in the semigroup, our construction shows that
$d\sim_{i}e$ only by way of an exponentially long composition of $a,b,c$
elements.

##  5\. Partition Covering

A conjugacy relation $\sim$ is _partition covering_ for a set $X$ if, for any
partition of $X$, there exists a semigroup with universe $X$ such that the
partition equals the semigroup’s $\sim$-conjugacy classes. Problem 6.10 from
[3] asks whether $\sim_{o}$, $\sim_{p}$, and $\sim_{tr}$ are partition
covering. It is known, through brute force calculation using the GAP package
_Smallsemi_ , that $\sim_{o}$ and $\sim_{p}$ are partition covering for any
$|X|\leq 6$. We now give an affirmative answer to Problem 6.10 for: (1)
$\sim_{o}$ and $\sim_{c}$ with respect to countable sets and (2) $\sim_{p}$,
$\sim_{p}^{*}$, and $\sim_{tr}$ for all finite sets.

######  Theorem 5.1.

The conjugacies $\sim_{o}$ and $\sim_{c}$ are partition covering for any
countable set. The conjugacies $\sim_{p}$, $\sim_{p^{*}}$, and $\sim_{tr}$ are
partition covering for any finite set.

###### Proof.

For any partition of $X$, let $\kappa$ be the number of classes in the
partition and denote the classes as $\\{X_{j}\\}_{0\leq j\leq\kappa-1}$.
Denote the elements of $X_{j}$ as $\\{(i,j)\\}_{i\in|X_{j}|}$. To define a
semigroup whose $o$-conjugacy classes are $\\{X_{j}\\}_{0\leq j\leq\kappa-1}$,
we define the following binary operation on $X$ for finite $\kappa$:
$(a,b)(c,d):=(1,b+d\mod\kappa)$. For countably infinite $\kappa$, define
$(a,b)(c,d):=(1,b+d)$

This operation is closed since $(1,j)\in X_{j}$ for every $0\leq
j\leq\kappa-1$. It is associative since the first component behaves like a
null semigroup while the second component inherits associativity from
addition. We prove that the partition equals the $\sim_{o}$-conjugacy classes
by proving $(a,b)\sim_{o}(c,d)$ iff $b=d$. Suppose there exists $(e,f)\in X$
such that $(a,b)(e,f)=(e,f)(c,d)$. Since $f<\kappa$, $b+f\equiv
f+dmod(\kappa)$ and $b+f=f+d$ each imply $b=d$. Conversely, for any
$(a,b),(c,b)\in X_{b}$, $(a,b)(1,0)=(1,b)=(1,0)(c,b)$. Likewise,
$(1,0)(a,b)=(1,b)=(c,b)(1,0)$. Since the semigroup does not have a zero
element, this construction also proves that $\sim_{c}$ is partition covering
for countable $X$.

We now consider any finite $X$. To define a semigroup whose $p$-conjugacy
classes equal the partition, WLOG let $X_{0}$ be of maximal size and define
the following binary operation on $X$:

$(a,b)(c,d):=\begin{cases}(a,b)&b=d\\\ (a,0)&b\neq d\end{cases}$

Because $X_{0}$ has maximal size, $(a,0)\in X_{0}$ for any $(a,b)\in X$. It is
associative since the first component behaves like a left zero semigroup and
the second component is a semilattice with every non-zero element immediately
above zero. That the second component is commutative also ensures
$(a,b)\sim_{p}(c,d)\Rightarrow b=d$. Conversely, for any $(a,b),(c,b)\in
X_{b}$, $(a,b)=(a,b)(c,b)$ and $(c,b)=(c,b)(a,b)$. Thus, the
$\sim_{p}$-conjugacy classes equal the partition. Since these classes are
disjoint, $\sim_{p}$ is transitive, so $\sim_{p^{*}}$ is also partition
covering.

Finally, we prove that $\sim_{p}\,=\,\sim_{tr}$ for this semigroup. Note that
every element is idempotent, so $x^{\omega+1}=x$ for each $x\in X$. Pick any
$x_{a},x_{b}\in X$ such that there exist mutually inverse $x_{g},x_{h}\in X$
satisfying $x_{g}x_{h}=x_{a}$, $x_{h}x_{g}=x_{b}$, and
$x_{g}x_{a}x_{h}=x_{b}$. Since $x_{g}x_{h}x_{g}=x_{g}$ and
$x_{h}x_{g}x_{h}=x_{h}$, their second components must match. Consequently, the
second components of $x_{a}$ and $x_{b}$ must match. Conversely, every pair
$(a,b),(c,b)\in X_{b}$ are mutually inverse, $(a,b)(c,b)=(a,b)$,
$(c,b)(a,b)=(c,b)$, and $(c,b)(a,b)(a,b)=(c,b)$. Thus, $(a,b)\sim_{tr}(c,b)$.
∎

##  6\. Open Problems

Problem 6.1: Are the following problems $\mathsf{PSPACE}$-complete: (1)
Membership in Inverse Semigroups, (2) Idempotent Membership in Inverse
Semigroups, and (3) Subsemigroup $i$-Conjugacy?

Problem 6.2 Are $\sim_{p}$, $\sim_{p}^{*}$, and $\sim_{tr}$ partition covering
for any countable set? For which sets is $\sim_{c}\cap\sim_{p}$ partition
covering?

##  7\. Acknowledgements

The author would like to thank Alan Cain, António Malheiro, and Peter Mayr for
their valuable comments and contributions.

## References

  * [1] J. Araújo, J. Konieczny, and A. Malheiro.  Conjugation in semigroups.  J. Algebra, 403:93–134, 2014.  doi:10.1016/j.jalgebra.2013.12.025.
  * [2] J. Araújo, M. Kinyon, and J. Konieczny.  Conjugacy in inverse semigroups.  J. Algebra, 533:142–173, 2019.  URL: https://www.sciencedirect.com/science/article/pii/S0021869319302765.  doi:10.1016/j.jalgebra.2019.05.022.
  * [3] J. Araújo, M. Kinyon, J. Konieczny, and A. Malheiro.  Four notions of conjugacy for abstract semigroups.  Proceedings of the Royal Society of Edinburgh: Section A Mathematics, 147(6):1169–1214, 2017.  doi:10.1017/S0308210517000099.
  * [4] A. H. Clifford and G. B. Preston.  The algebraic theory of semigroups. Vol. I.  Mathematical Surveys, No. 7. American Mathematical Society, Providence, R.I., 1961.
  * [5] L. Fleischer and T. Jack.  The complexity of properties of transformation semigroups.  Internat. J. Algebra Comput., 30(3):585–606, 2020.  doi:10.1142/S0218196720500125.
  * [6] J. M. Howie.  Fundamentals of semigroup theory, volume 12 of London Mathematical Society Monographs. New Series.  The Clarendon Press, Oxford University Press, New York, 1995.  Oxford Science Publications.
  * [7] N. Immerman.  Descriptive complexity.  Graduate Texts in Computer Science. Springer-Verlag, New York, 1999.  URL: https://doi-org.stanford.idm.oclc.org/10.1007/978-1-4612-0539-5. doi:10.1007/978-1-4612-0539-5.
  * [8] Z. Izhakian, J. Rhodes, and B. Steinberg.  Representation theory of finite semigroups over semirings.  J. Algebra 336:139–157, 2011.  doi:10.1016/j.jalgebra.2011.02.048
  * [9] T. Jack.  The complexity of properties of partial bijection semigroups.  Submitted July 2021.  URL: https://arxiv.org/abs/2101.00324
  * [10] G. Kudryavtseva and V. Mazorchuk.  On the conjugation in some transformation and Brauer-type semigroups.  Publ. Math. Debrecen, 70(1-2):19–43, 2007.
  * [11] C. H. Papadimitriou,  Computational complexity.  Addison-Wesley Publishing Company, Reading, MA, 1994.
  * [12] O. Reingold.  Undirected connectivity in log-space.  J. ACM, 55(4):Art. 17, 24, 2008.  URL: doi:10.1145/1391289.1391291.