worksheet.tex

\documentclass{article}
\usepackage{geometry}[a4paper, left=20mm, top=20mm]
\usepackage{microtype}
\usepackage{authblk}
\usepackage{enumitem}
\usepackage{amsmath}
\usepackage{tikz}
\tikzstyle{vertex}=[circle, draw=black, fill=black, inner sep=0pt,
minimum size=4pt]
\usepackage{hyperref}
\hypersetup{
  colorlinks=true,
  urlcolor=magenta,
}
\usepackage{mathrsfs}

\title{\texttt{Semigroups} --- Zero to Hero --- Worksheet}

\author[1]{James Mitchell}
\author[2]{Reinis Cirpons}
\author[1]{Joseph Edwards}
\author[1]{Finn Smith}

\affil[1]{University of St Andrews}
\affil[2]{Nantes Université, École Centrale Nantes, CNRS, Inria,
LS2N, UMR 6004, France}

\date{May 2026}

\begin{document}
\maketitle

If you've never used GAP before you might want to look at:

\url{https://carpentries-incubator.github.io/gap-lesson/}

before attempting any of the problems on this sheet.

This worksheet contains some exercises to be completed in \texttt{GAP} with the
use of the \texttt{Semigroups} package as part of the GAP workshop session of
NBSAN 40. The problems have been written in a deliberately terse way to
encourage attendees to experiment with the package and explore its associated
manual:
\url{https://semigroups.github.io/Semigroups/doc/chap0_mj.html}.

As well as inspecting the package manual, please also feel free to ask questions
to James, Reinis or Joe!
% TODO add Murray if Murray is going to be there too.

\begin{enumerate}
  \item Let $J_n$ denote the Jones monoid of degree $n$, and
    \[
      \input{tikz/jones-element.tikz}
    \]
    be a bipartition of degree 14.
    \begin{enumerate}
      \item Find a collection of bipartitions $\{x_1, x_2, \dots,
        x_j\}$ such that the tensor product $x_1 \otimes x_2 \otimes
        \dots \otimes x_j$ is equal to $x$. What is the largest
        possible value of $j$? For the definition of the tensor product, see the
        documentation of the function \texttt{TensorBipartition}.
      \item How many elements does $J_{14}$ contain?
      \item How many idempotent elements does $J_{14}$ contain?
      \item How many idempotent elements does the Green's
        $\mathscr{D}$-class of $x$ in $J_{14}$ contain?
      \item How many idempotent elements $e$, for which $7$ is in the
        domain of $e$, does the Green's $\mathscr{D}$-class of $x$ in
        $J_{14}$ contain?
      \item How many irreducible idempotent elements $\hat{e}$, for
        which $7$ is in the domain of $\hat{e}$, does the Green's
        $\mathscr{D}$-class of $x$ in $J_{14}$ contain?
    \end{enumerate}

  \item
    Recall that the commuting graph of a semigroup  $S$ is the graph with nodes
    the elements of $S$ and an edge $(x, y)$ if $xy = yx$ holds.
    Let $T_n$ be the full transformation monoid on $n \leq 5$ points. Show that
    the clique numbers of the commuting graph of $T_n$ are $2 ^ {n - 1}$.

  \item
    Let $S$ be the monoid defined by the presentation
    \[
      \langle a, b, c, d, e, f, g \mid abcd = a^3ea^2, ef= dg\rangle.
    \]
    \begin{enumerate}
      \item
        Show that $S$ is infinite.
      \item
        Create a homomorphism from the free semigroup $\{a, b, c, d,
        e, f, g\}^+$ to $S$.
      \item
        Partition the first $1000$ elements of $\{a, b, c, d, e, f, g\}^+$ so
        that words belong to the same part if and only if they represent the
        same element of $S$.
    \end{enumerate}

  \item
    Is the monoid defined by the presentation
    \[
      \langle x_2, \ldots, x_n\mid x_i^2 = (x_ix_j) ^3 =
      (x_ix_jx_k)^4 = 1\quad i, j, k \text{ distinct}\rangle
    \]
    the symmetric group for $n\geq 2$?

  \item
    Determine which of the relations in the presentation are redundant and
    which are not:
    \begin{align*}
      \langle a, b \mid &\
      a^4=1,  b^2= b,
      ba^3ba= a^2(ab)^2,  (ba^2)^2= (a^2b)^2 ,  (ba)^2a^2= aba^3b,
      a(ab)^4= (ab)^4
      \rangle.
    \end{align*}
    What is the minimal set of the relations in this presentation that
    define the same monoid?
    % TODO add citation

  \item
    Let $S$ be the Catalan monoid of degree $3$.
    \begin{enumerate}
      \item
        Draw the egg-box diagram of $S$.
      \item
        Draw the left and right Cayley graphs of $S$.
      \item
        Show that $S$ has two non-trivial non-universal non-Rees congruences.
      \item
        Show that the lattice of left and right congruences of $S$
        are isomorphic.
      \item
        What are the maximal subsemigroups of $S$? Show that none of
        the maximal subsemigroup is isomorphic to any of the others.
    \end{enumerate}

  \item
    Let $S$ be the dual of the full transformation monoid on 5
    points. Find a transformation representation of $S$ on $32$ points.
    \begin{enumerate}
      \item
        Draw the egg-box diagram of $S$.
      \item
        Draw the left and right Cayley graphs of $S$.
      \item
        Show that $S$ has two non-trivial non-universal non-Rees congruences.
      \item
        Show that the lattice of left and right congruences of $S$
        are isomorphic.
    \end{enumerate}

  \item
    %Recall that a left translation of a semigroup $S$ is a function
    % $\lambda \colon S \to S$ such that
    %$\lambda(x\cdot y) = \lambda(x)\cdot y$ for all $x, y \in S$; a
    % right translation of $S$ is a
    %function $\rho \colon S \to S$ such that $(x\cdot y)\rho = x
    % \cdot (y)\rho $ for all $x, y \in S$.
    %A bitranslation of $S$ is a pair $(\lambda, \rho)$ where
    % $\lambda$ is a left translation and
    %$\rho$ is a right translation, such that $x\cdot \lambda(y) =
    % (x)\rho \cdot y$ for all $x, y \in S$.
    The translational hull $\Omega(S)$ of a semigroup $S$ is the set
    of all bitranslations $(\lambda, \rho)$
    under componentwise composition. Any element $s$ of $S$ induces
    an inner bitranslation $(\lambda_s, \rho_s)$ of $S$, where
    $\lambda_s(x) = sx$ and $\rho_s(x) = xs$ for all $x \in S$.
    This gives a homomorphism $\pi_S$ from $S$ to $\Omega(S)$. If
    this is injective, then $S$ is \emph{weakly reductive}.
    Restricting the bitranslations to an ideal $I$ of $S$ gives a
    homomorphism $\pi_{S|I}$ from $S$ to $\Omega(I)$.
    If $I$ is weakly reductive, then $I$ is densely embedded in $S$
    if and only if $\pi_{S|I}$ is an isomorphism.

    \begin{enumerate}
      \item
        Determine the size of $\Omega(I)$ for each ideal $I$ of $J_7$
        (the Jones monoid of degree 7).
      \item
        Which of the ideals of $J_7$ are weakly reductive?
      \item
        Which of the ideals of $J_7$ are densely embedded in $J_7$?
      \item
        One such $\Omega(I)$ is gigantic, and so is certainly not
        being enumerated. Using \\ \verb|KnownTruePropertiesOfObject|,
        conjecture how the size is being calculated.

    \end{enumerate}

\end{enumerate}
\end{document}

% TODO add the atlas example