%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%
%A  TeX                                               <Goetz.Pfeiffer@UCG.ie>
%%
%%  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<A\right>$ 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<B\right>$ 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: 
%%
