%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%
%A TeX
%%
%% This file contains the Handout 'Computing the Size of a Semigroup'.
%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\documentclass[12pt]{amsart}
%% packages. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\usepackage{euler} \renewcommand{\baselinestretch}{1.143}
%\usepackage[T1]{fontenc}
%% top matter. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\title{Computing the size of a semigroup}
\author{G\"otz Pfeiffer}
\address{University College Galway, Ireland}
\email{Goetz.Pfeiffer@UCG.ie}
%% page size. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\advance\oddsidemargin -0.1\textwidth
\evensidemargin\oddsidemargin
\textwidth=1.2\textwidth
\advance\headheight 3pt
%% have 'slanted' instead of 'italics'. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\let\itdefault\sldefault
%% Theorem like environments. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\newtheorem{Thm}{Theorem}
\newtheorem{Cor}[Thm]{Corollary}
%% macros. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\newcommand{\id}{\mathop{\mathsf{id}}\nolimits}
\newcommand{\img}{\mathop{\mathsf{img}}}
\renewcommand{\ker}{\mathop{\mathsf{ker}}}
\newcommand{\Stab}{\mathop{\mathsf{Stab}}\nolimits}
\newcommand{\GAP}{\textsf{GAP}}
\newcommand{\MONOID}{\textsf{MONOID}}
\renewcommand{\O}{\mathfrak{O}}
\newcommand{\R}{\mathfrak{R}}
\newcommand{\rest}{\big|} % restriction
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{document}
\begin{abstract}
This is a report on the recently released package \textsf{MONOID} of
\textsf{GAP}~\cite{Sch95} programs dealing with (finite) transformation
monoids and their structure. An algorithm is described that given a list
$A$ of transformations on $n$ points determines the $R$ classes of the
monoid $M$ generated by $A$ and from that the size of $M$.
This is part of joint work with Steve Linton, Edmund Robertson and Nik
Ruskuc.
\end{abstract}
\maketitle
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{Introduction.}
There are powerful methods for investigating the structure of permutation
groups. The motivation for developing \textsf{MONOID} was to find similar
methods for transformation monoids, where surprisingly little seems to be
known.
Transformation monoids occur naturally, e.g, in the theory of finite state
machines and regular languages, and (in parallel to permutation groups) as
the result of enumerating finitely presented monoids, e.g.\ with Todd-Coxeter
methods. This establishes a demand for an algorithmic description of these
objects.
Permutation group algorithms not only form the model for the algorithms
described here. It turns out that a transformation monoid can be partitioned
into sets each of which is parameterized by a permutation group. Therefore
the existing methods for permutation groups can be incorporated into the
investigation of transformation monoids. This fact is illustrated by the
following formula for the size of a transformation monoid $M$. We have
\begin{equation} \label{eq:sum}
|M| = \sum_{s\in S} |\R(s)|\ |\img R_s|\ |G_R(s)|
\end{equation}
where $S\subseteq M$ is a set of suitable representatives, $\R(s)$ is the set
of $R$ classes of $M$ which give rise to the same list of image sets as the
$R$ class $R_s$ of $s$, further $\img R_s$ is the list of all image sets
occurring in $R_s$ and $G_R(s)$ is a permutation group on $\img s$. A
precise definition of $G_R(s)$, $\img$ and the concept of $R$ classes is
given below.
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{Actions.}
A monoid $M$ acts on a set $X$ via the map $(x, m) \mapsto x \cdot m\colon X
\times M \to X$ if $x \cdot 1 = x$ and $x \cdot (m_1 m_2) = (x \cdot m_1)
\cdot m_2$ for all $x \in X$ and all $m_1, m_2 \in M$.
The orbit of $x \in X$ under $M$ is the set $\{x \cdot m \mid m \in M\}$.
Note that these orbits do not form a partition of $X$. This is only true for
strong orbits, where the strong orbit of $x$ under $M$ is the set
\[
\{ x \cdot m \mid m \in M,
\mbox{\ there is an $m' \in M$ such that $x m m' = x$} \}.
\]
Let $n > 0$ and let $I = \{1, \dots, n\}$. A transformation of degree $n$ is
a map $f \colon I \to I$. The set $T_n = \{f \colon I \to I\}$ of all
transformations of degree $n$ is called the full transformation monoid of
degree $n$. We write $M \leq T_n$ and call $M$ a transformation monoid of
degree $n$ if $M$ is a submonoid of $T_n$.
Let $M \leq T_n$. Then, for example, $M$ acts
\begin{enumerate}\renewcommand{\labelenumi}{(\roman{enumi})}
\item naturally on $I = \{1, \dots, n\}$;
\item on $2^I = \{ J \subseteq I\}$, where for $m \in M$ and $J
\subseteq I$ we have $J \cdot m = \{j \cdot m \mid j \in J\}$; and
\item on $M$ by right multiplication.
\end{enumerate}
The orbit of $m \in M$ under $M$ is the right ideal $mM$ in $M$. An element
$s \in M$ lies in the strong orbit of $m$ if and only if $sM = mM$. The
strong orbit of $m \in M$ is called the $R$ class of $m$ in $M$ and denoted
by $R_m$.
Let $\img \colon M \to 2^I$ be the map that associates to each $m \in M$ its
image, i.e., $\img m = \{i \cdot m \mid i \in I\}$. Then, $\img m = I \cdot
m$ and it follows that $\img$ is a homomorphism of $M$-sets, since $\img (m_1
\cdot m_2) = I \cdot m_1 \cdot m_2 = (\img m_1) \cdot m_2$. In particular,
$\img$ maps (strong) orbits to (strong) orbits.
Denote, for $A \subseteq M$, by $\img A = \{\img a \mid a \in A\} \subseteq
2^I$ the list of all image sets occurring in $A$. We then draw the following
conclusion from the fact that $R_m$ is a strong orbit.
\begin{Thm}
Let $m \in M$. The set $\img R_m \subseteq 2^I$ is a strong orbit under
the action of $M$.
\end{Thm}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{Groups.}
Let $J \subseteq I$ and define the stabilizer of $J$ in $M$ as $\Stab_M(J) =
\{m \in M \mid J \cdot m = J\}$. Then every $m \in \Stab_M(J)$ induces a
permutation $m\rest_J$ of $J$. Let
\[
G(J) = \{m \rest_J \mid m \in \Stab_M(J) \} \leq S_n
\]
be the corresponding permutation group, regarded as a group of permutations
of $I$.
Suppose $M = \left$ for some $A \subseteq T_n$. Generators for the
group $G(J)$ are constructed from $A$ by a Schreier method as follows. Let
$\O \subseteq 2^I$ be the strong orbit of $J \subseteq I$ under the action of
$M$. For each $K \in \O$ there are elements $m_K, m_K' \in M$ such that $J
m_K = K$ and $K m_K' = J$. Let $m \in M$ such that $K m \in \O$. Then $m_K
m m_{Km}' \in \Stab(J)$. We have $G(J) = \left**$ where
\begin{equation} \label{eq:schreier}
B = \{ (m_K a m_{K \cdot a}')\rest_J \mid K \in \O,\ a \in A,\
K \cdot a \in \O\}.
\end{equation}
Moreover, $G(K) \cong G(J)$ for each $K \in \O$.
We associate the permutation group $G_R(s) = G(\img s)$ to every element $s
\in M$ and call $G_R(s)$ the generalized Sch\"utzenberger group of $s$ in
$M$. Note that, for any $s \in T_n$ there is an element $u \in T_n$ such
that $(us)\rest_{\img s} = \id$. This element can be used to turn an
environment of $s$ into a group isomorphic to $G_R(s)$.
\begin{Thm}
Let $s \in M \leq T_n$ and let $u \in T_n$ such that $(us)\rest_{\img s} =
\id$. Let
\[
P = \{t \in R_s \mid \img t = \img s\}.
\]
Then $P$, with multiplication defined by $x * y = x u y$, is a group with
identity $s$, and is isomorphic to the right generalized Sch\"utzenberger
group $G_R(s)$ of $s$. The isomorphism is given by the mutually inverse
maps $t \mapsto (u t)\rest_{\img s}\colon P \to G_R(s)$ and $g \mapsto s
\cdot g \colon G_R(s) \to P$.
\end{Thm}
The last result suggests for the $R$ class $R_s$ of $s$ a data structure
consisting of the representative $s$, the group $G_R(s)$, the list $\img R_s$
of image sets and the transformations $m_K, m_K'$ for $K \in \img R_s$. This
data structure is provided by constructing the strong orbit $\img R_s$ of
$\img s$ together with the multipliers $m_K, m_K'$, and the set Schreier
generators for $G_R(s)$ as in (\ref{eq:schreier}). Note that the
computations here take place locally, i.e., without prior knowledge of all
$R$ classes of $M$, or even the $R$ class of $s$ in $M$.
Given these data one can quickly compute the Size of, the Elements of, and
Membership in the $R$ class of $s$ (and using the latter: Equality of $R$
classes).
As for the size of $R_s$, in analogy to the Orbit Theorem, we have
\begin{Cor}
Let $s \in M$. Then, $|R_s| = |\img R_s|\ |G_R(s)|$.
\end{Cor}
As for the elements of $R_s$, note that $P = s \cdot G_R(s)$. This can be
translated via the $m_K$ to give all elements of $R_s$.
As for the membership in $R_s$, note that for any $t \in T_n$ we have $t \in
P$ if and only if $\ker t = \ker s$, $\img t = \img s$, and $(ut)\rest_{\img
s} \in G_R(s)$. If images are translated by means of the $m_K'$ this
extends to a membership test for all of $R_s$.
Now $M$ acts from the left (!) on its $R$ classes via $m \cdot R_s = R_{ms}$
for $m, s \in M$. So we can determine the list of all $R$ classes of $M$ (or
rather the data structures representing them) as the orbit of the class $R_1$
of the identity.
This allows us to compute $|M|$ as the sum of the sizes of its $R$ classes.
Formula~\ref{eq:sum} follows from the fact that $|R_s|$ depends only on
$\img R_s \subseteq 2^I$.
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{Conclusion.}
The notion of $R$ classes, together with classes of type $L$, $D$ and $H$,
was introduced by Green in~\cite{Green51}. The $L$ class $L_m$ of $m \in M$
consists of all elements which generate the same left ideal $Mm$ in $M$. A
``dual'' approach can be used from the left in terms of kernels of
transformations and $L$ classes. Care has to be taken since kernels do not
give immediate rise to permutation groups. We can then associate a
permutation group $G_L(s)$ to every $s \in M$. This leads to data structure
for $L$ classes, similar to the one for $R$ classes in that it allows quickly
to determine the Size of, the Elements of, and the Membership in the $L$
class of $s$.
All elements in the $D$ class $D_m$ generate the same (two sided) ideal $MmM$
in $M$. A method to determine $|M|$ in terms of the $D$ class structure of
$M$ is described in \cite{LaMc90}. This method, however, does not completely
avoid listing all elements of $D$ classes and does not take advantage of
permutation group methods.
The $H$ class $H_m$ is the intersection $L_m \cap R_m$. In~\cite{sc57}
and~\cite{sc58}, a ``Sch\"utzenberger'' group with remarkable properties is
associated to every $H$ class. In our terminology the Sch\"utzenberger group
of the $H$ class of $s \in M$ is isomorphic to the group $G_L(s) \cap
G_R(s)$.
With {\MONOID}\footnote{The {\MONOID} package is available via anonymous
\texttt{ftp} from {\GAP}'s \texttt{ftp} servers and from
\texttt{ftp://schmidt.ucg.ie/pub/goetz/gap/monoid-2.0.tgz}} the complete
Green class structure of $M$ can be determined and all Sch\"utzenberger
groups can be calculated. The theory behind this is described in more detail
in \cite{LPRR1}, the algorithms in {\MONOID} are developed in \cite{LPRR2}.
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%\bibliography{monoids}
%\bibliographystyle{amsplain}
\providecommand{\bysame}{\leavevmode\hbox to3em{\hrulefill}\thinspace}
\begin{thebibliography}{1}
\bibitem{Green51}
J.~A. Green, \emph{On the structure of semigroups}, Ann. Math. \textbf{54}
(1951), 163--172.
\bibitem{LaMc90}
G.~Lallement and R.~McFadden, \emph{On the determination of {Green}'s relations
in finite transformation semigroups}, J. Symbolic Computation \textbf{10}
(1990), 481--489.
\bibitem{LPRR2}
S.~A. Linton, G.~Pfeiffer, E.~F. Robertson, and N.~Ru{\v s}kuc, \emph{Computing
transformation semigroups}, in preparation.
\bibitem{LPRR1}
\bysame, \emph{Groups and actions in transformation semigroups}, Math. Z.
(1997), to appear.
\bibitem{Sch95}
M.~Sch{\"o}nert et~al., \emph{{GAP} -- {Groups}, {Algorithms}, and
{Programming}}, Lehrstuhl D f{\"u}r Mathematik, Rheinisch Westf{\"a}lische
Technische Hoch\-schule, Aachen, Germany, fifth ed., 1995.
\bibitem{sc57}
M.~P. Sch{\"u}tzenberger, \emph{{$D$}-repr{\'e}sentation des demi-groupes}, C.
R. Acad. Sci. Paris \textbf{244} (1957), 1994--1996.
\bibitem{sc58}
\bysame, \emph{Sur la repr{\'e}sentation monomiale des demi-groupes}, C. R.
Acad. Sci. Paris \textbf{246} (1958), 865--867.
\end{thebibliography}
\end{document}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%
%E Emacs . . . . . . . . . . . . . . . . . . . . . . emacs local variables.
%%
%% Local Variables:
%% mode: latex
%% fill-column: 77
%% End:
%%
**