notebooks/intro.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<a name=\"top\"></a>*“Computing with semigroups in GAP”* by [Wilf Wilson](http://wilf.me)<br />\n",
    "*“[GAP in Algebraic Research](https://lbfm-rwth.github.io/gap-in-algebraic-research-2018/)” summer school*<br />\n",
    "19<sup>th</sup> to 22<sup>nd</sup> November 2018<br />\n",
    "https://github.com/wilfwilson/semigroups-in-algebraic-research\n",
    "([Link to Binder](https://mybinder.org/v2/gh/wilfwilson/semigroups-in-algebraic-research/master))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Computing with semigroups in GAP"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## What is a semigroup?"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "A *semigroup* is simply a set with an associative binary operation."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "What is associativity? As I'm sure you know, a binary operation $\\ast$ on a set $S$ is *associative* if:\n",
    "\n",
    "$$(x \\ast y) \\ast z = x \\ast (y \\ast z)$$\n",
    "\n",
    "for all elements $x, y, z \\in S$."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "GAP itself contains long-standing support for semigroups; this is extended by several packages, which I will talk about later. In this notebook, I will focus on some of the functionality that is built into GAP."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "According to GAP, what is a semigroup?"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "<Filter \"(IsMagma and IsAssociative)\">"
      ]
     },
     "execution_count": 1,
     "metadata": {
      "text/plain": ""
     },
     "output_type": "execute_result"
    }
   ],
   "source": [
    "IsSemigroup;"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Okay, we know what associativity is... but what is a magma? A *magma* is a set with any old binary operation accessible via `*`. So it makes sense that, in GAP, a semigroup in is an associative magma."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "What other ‘properties’ does a semigroup inherently have, in GAP?"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Implies:\n",
      "   IsListOrCollection\n",
      "   IsCollection\n",
      "   IsDuplicateFree\n",
      "   IsExtLElement\n",
      "   CategoryCollections(IsExtLElement)\n",
      "   IsExtRElement\n",
      "   CategoryCollections(IsExtRElement)\n",
      "   CategoryCollections(IsMultiplicativeElement)\n",
      "   IsGeneralizedDomain\n",
      "   IsMagma\n",
      "   IsAssociative\n",
      "   IsGeneratorsOfSemigroup\n",
      "\n",
      "\n",
      "May imply with:\n",
      "+IsMagmaWithOne\n",
      "   IsMonoidAsSemigroup\n",
      "\n",
      "+IsMagmaWithInverses\n",
      "   IsSimpleSemigroup\n",
      "   IsRegularSemigroup\n",
      "   IsInverseSemigroup\n",
      "   IsCompletelyRegularSemigroup\n",
      "   IsGroupAsSemigroup\n",
      "   IsMonoidAsSemigroup\n",
      "   IsOrthodoxSemigroup\n",
      "   IsBlockGroup\n",
      "   IsLeftSimple\n",
      "   IsRightSimple\n",
      "   IsSemigroupWithCommutingIdempotents\n",
      "\n",
      "+IsNonTrivial\n",
      "+IsFinite\n",
      "+IsExtLSet\n",
      "+IsAssociativeLOpDProd\n",
      "+IsAssociativeLOpEProd\n",
      "+IsDistributiveLOpDSum\n",
      "+IsDistributiveLOpESum\n",
      "+IsTrivialLOpEOne\n",
      "+IsLeftActedOnByRing\n",
      "+IsLeftActedOnByDivisionRing\n",
      "+IsMagmaWithOne\n",
      "+IsMagmaWithInversesIfNonzero\n",
      "+IsNearAdditiveMagma\n",
      "+IsNearAdditiveGroup\n",
      "+IsAdditivelyCommutative\n",
      "+IsLDistributive\n",
      "+IsRDistributive\n",
      "+IsEuclideanRing\n",
      "   IsCommutative\n",
      "   IsCommutativeSemigroup\n",
      "   IsMonoidAsSemigroup\n",
      "   IsBlockGroup\n",
      "   IsSemigroupWithCommutingIdempotents\n",
      "\n",
      "+IsWholeFamily\n",
      "+CategoryCollections(IsReesMatrixSemigroupElement)\n",
      "   IsReesMatrixSemigroup\n",
      "\n",
      "+IsWholeFamily\n",
      "+CategoryCollections(IsReesZeroMatrixSemigroupElement)\n",
      "   IsReesZeroMatrixSemigroup\n",
      "\n",
      "+IsTrivial\n",
      "   IsCommutative\n",
      "   IsSimpleSemigroup\n",
      "   IsRegularSemigroup\n",
      "   IsInverseSemigroup\n",
      "   IsCommutativeSemigroup\n",
      "   IsCompletelyRegularSemigroup\n",
      "   IsCompletelySimpleSemigroup\n",
      "   IsGroupAsSemigroup\n",
      "   IsLeftZeroSemigroup\n",
      "   IsNilpotentSemigroup\n",
      "   IsOrthodoxSemigroup\n",
      "   IsRightZeroSemigroup\n",
      "   IsZeroSemigroup\n",
      "   IsBlockGroup\n",
      "   IsLeftSimple\n",
      "   IsRightSimple\n",
      "   IsSemigroupWithCommutingIdempotents\n",
      "\n",
      "+CategoryCollections(IsTransformation)\n",
      "   IsFinite\n",
      "\n",
      "+CategoryCollections(IsPartialPerm)\n",
      "   IsFinite\n",
      "   IsBlockGroup\n",
      "   IsSemigroupWithCommutingIdempotents\n",
      "\n",
      "+CategoryCollections(IsBipartition)\n",
      "   IsFinite\n",
      "\n",
      "+CategoryCollections(IsPBR)\n",
      "   IsFinite\n",
      "\n",
      "+CategoryCollections(IsTropicalMatrix)\n",
      "+CategoryCollections(IsTropicalMaxPlusMatrix)\n",
      "   IsFinite\n",
      "\n",
      "+CategoryCollections(IsTropicalMatrix)\n",
      "+CategoryCollections(IsTropicalMinPlusMatrix)\n",
      "   IsFinite\n",
      "\n",
      "+CategoryCollections(IsNTPMatrix)\n",
      "   IsFinite\n",
      "\n",
      "+CategoryCollections(IsBooleanMat)\n",
      "   IsFinite\n",
      "\n",
      "+CategoryCollections(IsMatrixOverFiniteField)\n",
      "   IsComponentObjectRep\n",
      "   IsFinite\n",
      "   CanComputeSize\n",
      "   IsEnumerableSemigroupRep\n",
      "   IsActingSemigroupWithFixedDegreeMultiplication\n",
      "\n",
      "+IsCommutative\n",
      "   IsCommutativeSemigroup\n",
      "   IsBlockGroup\n",
      "   IsSemigroupWithCommutingIdempotents\n",
      "\n",
      "+IsGeneratorsOfEnumerableSemigroup\n",
      "   IsComponentObjectRep\n",
      "   IsEnumerableSemigroupRep\n",
      "\n",
      "+IsFinite\n",
      "+IsWholeFamily\n",
      "+CategoryCollections(IsElementOfFpSemigroup)\n",
      "   IsComponentObjectRep\n",
      "   IsEnumerableSemigroupRep\n",
      "\n",
      "+CategoryCollections(IsReesMatrixSemigroupElement)\n",
      "+IsGeneratorsOfEnumerableSemigroup\n",
      "   IsComponentObjectRep\n",
      "   IsEnumerableSemigroupRep\n",
      "\n",
      "+CategoryCollections(IsReesZeroMatrixSemigroupElement)\n",
      "+IsGeneratorsOfEnumerableSemigroup\n",
      "   IsComponentObjectRep\n",
      "   IsEnumerableSemigroupRep\n",
      "\n",
      "+IsLeftActedOnBySuperset\n",
      "+IsRightActedOnBySuperset\n",
      "   IsSemigroupIdeal\n",
      "\n",
      "+CategoryCollections(IsFreeBandElement)\n",
      "   IsFinite\n",
      "\n"
     ]
    }
   ],
   "source": [
    "ShowImpliedFilters(IsSemigroup);"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Okay then, what is a group, according to GAP?"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {
    "scrolled": true
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "<Filter \"(IsMagmaWithInverses and IsAssociative)\">"
      ]
     },
     "execution_count": 3,
     "metadata": {
      "text/plain": ""
     },
     "output_type": "execute_result"
    }
   ],
   "source": [
    "IsGroup;"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Great! But we need to be careful...**\n",
    "\n",
    "This is a slightly technical definition. Basically, what it means is that, according to GAP, a magma $G$ satisfies `IsGroup` if it is mathematically a group, **and moreover**, if $x \\in G$, then `x^0` gives the identity of $G$, and `x^-1` gives the group-theoretic inverse of the element $x$ in $G$.\n",
    "\n",
    "In other words, a group satisfies `IsGroup` if you can calculate the identity and inverse of an element without doing *any* calculations in the group."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Perhaps counter-intuitively, this means that a semigroup in GAP might mathematically define a group, but **not** satisfy `IsGroup`, if it does not support the function `^0` or `^-1`.\n",
    "\n",
    "Let's see an example of a semigroup that is mathematically a group, but does not satisfy `IsGroup`. It is a semigroup consisting of a single non-invertible $2 \\times 2$ matrix over $\\mathbb{F}_{2}$."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[ [ Z(2)^0, Z(2)^0 ], [ 0*Z(2), 0*Z(2) ] ]"
      ]
     },
     "execution_count": 4,
     "metadata": {
      "text/plain": ""
     },
     "output_type": "execute_result"
    },
    {
     "data": {
      "text/plain": [
       "<commutative semigroup with 1 generator>"
      ]
     },
     "execution_count": 5,
     "metadata": {
      "text/plain": ""
     },
     "output_type": "execute_result"
    }
   ],
   "source": [
    "x := [[1, 1], [0, 0]] * One(GF(2));\n",
    "S := Semigroup(x);"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "true"
      ]
     },
     "execution_count": 6,
     "metadata": {
      "text/plain": ""
     },
     "output_type": "execute_result"
    }
   ],
   "source": [
    "IsTrivial(S);"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Since $S$ is semigroup with only one element, it therefore defines a group (the trivial group). But since `^-1` does not work for its element, it does not satisfy `IsGroup`:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "false"
      ]
     },
     "execution_count": 7,
     "metadata": {
      "text/plain": ""
     },
     "output_type": "execute_result"
    },
    {
     "data": {
      "text/plain": [
       "fail"
      ]
     },
     "execution_count": 8,
     "metadata": {
      "text/plain": ""
     },
     "output_type": "execute_result"
    }
   ],
   "source": [
    "IsGroup(S);\n",
    "x ^ -1;"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "*This should not be an issue in this mini-course.*"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Let's look at some of what is implied by `IsGroup`:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Implies:\n",
      "   IsListOrCollection\n",
      "   IsCollection\n",
      "   IsDuplicateFree\n",
      "   IsExtLElement\n",
      "   CategoryCollections(IsExtLElement)\n",
      "   IsExtRElement\n",
      "   CategoryCollections(IsExtRElement)\n",
      "   CategoryCollections(IsMultiplicativeElement)\n",
      "   CategoryCollections(IsMultiplicativeElementWithOne)\n",
      "   CategoryCollections(IsMultiplicativeElementWithInverse)\n",
      "   IsGeneralizedDomain\n",
      "   IsMagma\n",
      "   IsMagmaWithOne\n",
      "   IsMagmaWithInversesIfNonzero\n",
      "   IsMagmaWithInverses\n",
      "   IsAssociative\n",
      "   HasMultiplicativeNeutralElement\n",
      "   IsGeneratorsOfSemigroup\n",
      "   IsSimpleSemigroup\n",
      "   IsRegularSemigroup\n",
      "   IsInverseSemigroup\n",
      "   IsCompletelyRegularSemigroup\n",
      "   IsGroupAsSemigroup\n",
      "   IsMonoidAsSemigroup\n",
      "   IsOrthodoxSemigroup\n",
      "   IsBlockGroup\n",
      "   IsLeftSimple\n",
      "   IsRightSimple\n",
      "   IsSemigroupWithCommutingIdempotents\n",
      "\n",
      "\n",
      "May imply with:\n",
      "+IsFinite\n",
      "   IsComponentObjectRep\n",
      "   CategoryCollections(IsFiniteOrderElement)\n",
      "   IsCompletelySimpleSemigroup\n",
      "   IsFinitelyGeneratedGroup\n",
      "   IsSubsetLocallyFiniteGroup\n",
      "   HasIsInfiniteAbelianizationGroup\n",
      "   IsEnumerableSemigroupRep\n",
      "\n",
      "+IsTrivial\n",
      "   IsComponentObjectRep\n",
      "   CategoryCollections(IsFiniteOrderElement)\n",
      "   IsCommutative\n",
      "   IsCommutativeSemigroup\n",
      "   IsCompletelySimpleSemigroup\n",
      "   IsLeftZeroSemigroup\n",
      "   IsNilpotentSemigroup\n",
      "   IsRightZeroSemigroup\n",
      "   IsZeroSemigroup\n",
      "   IsCyclic\n",
      "   IsElementaryAbelian\n",
      "   IsFinitelyGeneratedGroup\n",
      "   IsSubsetLocallyFiniteGroup\n",
      "   IsPGroup\n",
      "   IsPowerfulPGroup\n",
      "   IsNilpotentGroup\n",
      "   IsPerfectGroup\n",
      "   IsSupersolvableGroup\n",
      "   IsMonomialGroup\n",
      "   IsSolvableGroup\n",
      "   IsPolycyclicGroup\n",
      "   HasIsInfiniteAbelianizationGroup\n",
      "   IsEnumerableSemigroupRep\n",
      "\n",
      "+IsCyclic\n",
      "   IsCommutative\n",
      "   IsCommutativeSemigroup\n",
      "   IsNilpotentGroup\n",
      "   IsSupersolvableGroup\n",
      "   IsSolvableGroup\n",
      "\n",
      "+IsElementaryAbelian\n",
      "   IsCommutative\n",
      "   IsCommutativeSemigroup\n",
      "   IsPGroup\n",
      "   IsNilpotentGroup\n",
      "   IsSupersolvableGroup\n",
      "   IsSolvableGroup\n",
      "\n",
      "+IsCommutative\n",
      "   IsCommutativeSemigroup\n",
      "   IsNilpotentGroup\n",
      "   IsSupersolvableGroup\n",
      "   IsSolvableGroup\n",
      "\n",
      "+CategoryCollections(((IsWord and IsAssociativeElement) and (IsWord and IsMult\\\n",
      "iplicativeElementWithInverse)))\n",
      "   IsSubgroupFgGroup\n",
      "   IsSubgroupFpGroup\n",
      "\n",
      "+IsFinite\n",
      "+CategoryCollections(IsMultiplicativeElementWithInverseByPolycyclicCollector)\n",
      "   IsComponentObjectRep\n",
      "   CanEasilyCompareElements\n",
      "   CanEasilySortElements\n",
      "   CanComputeSize\n",
      "   CategoryCollections(IsFiniteOrderElement)\n",
      "   IsCompletelySimpleSemigroup\n",
      "   IsFinitelyGeneratedGroup\n",
      "   IsSubsetLocallyFiniteGroup\n",
      "   CanComputeSizeAnySubgroup\n",
      "   KnowsHowToDecompose\n",
      "   IsSolvableGroup\n",
      "   IsPolycyclicGroup\n",
      "   HasIsInfiniteAbelianizationGroup\n",
      "   CanEasilyComputePcgs\n",
      "   CanComputeFittingFree\n",
      "   IsEnumerableSemigroupRep\n",
      "\n",
      "+CategoryCollections(IsMultiplicativeElementWithInverseByPolycyclicCollector)\n",
      "   IsComponentObjectRep\n",
      "   IsFinite\n",
      "   CanEasilyCompareElements\n",
      "   CanEasilySortElements\n",
      "   CanComputeSize\n",
      "   CategoryCollections(IsFiniteOrderElement)\n",
      "   IsCompletelySimpleSemigroup\n",
      "   IsFinitelyGeneratedGroup\n",
      "   IsSubsetLocallyFiniteGroup\n",
      "   CanComputeSizeAnySubgroup\n",
      "   KnowsHowToDecompose\n",
      "   IsSolvableGroup\n",
      "   IsPolycyclicGroup\n",
      "   HasIsInfiniteAbelianizationGroup\n",
      "   CanEasilyComputePcgs\n",
      "   CanComputeFittingFree\n",
      "   IsEnumerableSemigroupRep\n",
      "\n",
      "+IsFinite\n",
      "+CategoryCollections(IsPerm)\n",
      "   IsComponentObjectRep\n",
      "   CanEasilyCompareElements\n",
      "   CanEasilySortElements\n",
      "   CanComputeSize\n",
      "   IsCompletelySimpleSemigroup\n",
      "   IsFinitelyGeneratedGroup\n",
      "   CanEasilyTestMembership\n",
      "   CanComputeSizeAnySubgroup\n",
      "   KnowsHowToDecompose\n",
      "   HasIsInfiniteAbelianizationGroup\n",
      "   CanComputeFittingFree\n",
      "   IsEnumerableSemigroupRep\n",
      "\n",
      "+CategoryCollections(IsPerm)\n",
      "   IsComponentObjectRep\n",
      "   IsFinite\n",
      "   CanEasilyCompareElements\n",
      "   CanEasilySortElements\n",
      "   CanComputeSize\n",
      "   IsCompletelySimpleSemigroup\n",
      "   IsFinitelyGeneratedGroup\n",
      "   CanEasilyTestMembership\n",
      "   CanComputeSizeAnySubgroup\n",
      "   KnowsHowToDecompose\n",
      "   HasIsInfiniteAbelianizationGroup\n",
      "   CanComputeFittingFree\n",
      "   IsEnumerableSemigroupRep\n",
      "\n",
      "+CategoryCollections(IsElementOfFpGroup)\n",
      "   IsSubgroupFgGroup\n",
      "   IsSubgroupFpGroup\n",
      "\n",
      "+CategoryCollections((IsWord and IsAssociativeElement))\n",
      "   IsSubgroupFgGroup\n",
      "   IsSubgroupFpGroup\n",
      "\n",
      "+IsFinite\n",
      "+CategoryCollections(CategoryCollections(CategoryCollections(IsNearAdditiveEle\\\n",
      "mentWithInverse)))\n",
      "+CategoryCollections(CategoryCollections(CategoryCollections(IsAdditiveElement\\\n",
      ")))\n",
      "+CategoryCollections(CategoryCollections(CategoryCollections(IsMultiplicativeE\\\n",
      "lement)))\n",
      "   IsComponentObjectRep\n",
      "   CanComputeSize\n",
      "   CategoryCollections(IsFiniteOrderElement)\n",
      "   IsCompletelySimpleSemigroup\n",
      "   IsFinitelyGeneratedGroup\n",
      "   IsSubsetLocallyFiniteGroup\n",
      "   CanEasilyTestMembership\n",
      "   CanComputeSizeAnySubgroup\n",
      "   HasIsInfiniteAbelianizationGroup\n",
      "   IsHandledByNiceMonomorphism\n",
      "   IsEnumerableSemigroupRep\n",
      "\n",
      "+CategoryCollections(CategoryCollections(CategoryCollections(IsNearAdditiveEle\\\n",
      "mentWithInverse)))\n",
      "+CategoryCollections(CategoryCollections(CategoryCollections(IsAdditiveElement\\\n",
      ")))\n",
      "+CategoryCollections(CategoryCollections(CategoryCollections(IsMultiplicativeE\\\n",
      "lement)))\n",
      "+CategoryCollections(CategoryCollections(CategoryCollections(IsFFE)))\n",
      "   IsSubsetLocallyFiniteGroup\n",
      "\n",
      "+CategoryCollections(IsFFE)\n",
      "   CanComputeSize\n",
      "   IsCommutative\n",
      "   IsCommutativeSemigroup\n",
      "   IsCyclic\n",
      "   IsSubsetLocallyFiniteGroup\n",
      "   CanEasilyTestMembership\n",
      "   CanEasilyComputeWithIndependentGensAbelianGroup\n",
      "   CanComputeSizeAnySubgroup\n",
      "   IsNilpotentGroup\n",
      "   IsSupersolvableGroup\n",
      "   IsSolvableGroup\n",
      "   IsAdditivelyCommutative\n",
      "   IsHandledByNiceMonomorphism\n",
      "\n",
      "+HasFamilyPcgs\n",
      "   CanComputeSize\n",
      "   CanComputeSizeAnySubgroup\n",
      "   IsSolvableGroup\n",
      "   CanEasilyComputePcgs\n",
      "\n",
      "+CategoryCollections(IsPerm)\n",
      "+IsCommutative\n",
      "   IsComponentObjectRep\n",
      "   IsFinite\n",
      "   CanEasilyCompareElements\n",
      "   CanEasilySortElements\n",
      "   CanComputeSize\n",
      "   IsCommutativeSemigroup\n",
      "   IsCompletelySimpleSemigroup\n",
      "   IsFinitelyGeneratedGroup\n",
      "   CanEasilyTestMembership\n",
      "   CanEasilyComputeWithIndependentGensAbelianGroup\n",
      "   CanComputeSizeAnySubgroup\n",
      "   KnowsHowToDecompose\n",
      "   IsNilpotentGroup\n",
      "   IsSupersolvableGroup\n",
      "   IsMonomialGroup\n",
      "   IsSolvableGroup\n",
      "   IsPolycyclicGroup\n",
      "   HasIsInfiniteAbelianizationGroup\n",
      "   CanEasilyComputePcgs\n",
      "   CanComputeFittingFree\n",
      "   IsEnumerableSemigroupRep\n",
      "\n",
      "+CategoryCollections(IsPerm)\n",
      "+IsRegular\n",
      "   IsComponentObjectRep\n",
      "   IsFinite\n",
      "   CanEasilyCompareElements\n",
      "   CanEasilySortElements\n",
      "   CanComputeSize\n",
      "   IsCompletelySimpleSemigroup\n",
      "   IsFinitelyGeneratedGroup\n",
      "   CanEasilyTestMembership\n",
      "   CanComputeSizeAnySubgroup\n",
      "   KnowsHowToDecompose\n",
      "   HasIsInfiniteAbelianizationGroup\n",
      "   IsTransitive\n",
      "   IsSemiRegular\n",
      "   CanComputeFittingFree\n",
      "   IsEnumerableSemigroupRep\n",
      "\n",
      "+CategoryCollections(IsPerm)\n",
      "+IsTransitive\n",
      "+IsSemiRegular\n",
      "   IsComponentObjectRep\n",
      "   IsFinite\n",
      "   CanEasilyCompareElements\n",
      "   CanEasilySortElements\n",
      "   CanComputeSize\n",
      "   IsCompletelySimpleSemigroup\n",
      "   IsFinitelyGeneratedGroup\n",
      "   CanEasilyTestMembership\n",
      "   CanComputeSizeAnySubgroup\n",
      "   KnowsHowToDecompose\n",
      "   HasIsInfiniteAbelianizationGroup\n",
      "   IsRegular\n",
      "   CanComputeFittingFree\n",
      "   IsEnumerableSemigroupRep\n",
      "\n",
      "+IsNonTrivial\n",
      "+CategoryCollections(((IsWord and IsAssociativeElement) and (IsWord and IsMult\\\n",
      "iplicativeElementWithInverse)))\n",
      "   IsInfiniteAbelianizationGroup\n",
      "   IsSubgroupFgGroup\n",
      "   IsSubgroupFpGroup\n",
      "\n",
      "+IsTrivial\n",
      "+CategoryCollections(((IsWord and IsAssociativeElement) and (IsWord and IsMult\\\n",
      "iplicativeElementWithInverse)))\n",
      "   IsComponentObjectRep\n",
      "   CategoryCollections(IsFiniteOrderElement)\n",
      "   IsCommutative\n",
      "   IsCommutativeSemigroup\n",
      "   IsCompletelySimpleSemigroup\n",
      "   IsLeftZeroSemigroup\n",
      "   IsNilpotentSemigroup\n",
      "   IsRightZeroSemigroup\n",
      "   IsZeroSemigroup\n",
      "   IsCyclic\n",
      "   IsElementaryAbelian\n",
      "   IsFinitelyGeneratedGroup\n",
      "   IsSubsetLocallyFiniteGroup\n",
      "   IsPGroup\n",
      "   IsPowerfulPGroup\n",
      "   IsNilpotentGroup\n",
      "   IsPerfectGroup\n",
      "   IsSupersolvableGroup\n",
      "   IsMonomialGroup\n",
      "   IsSolvableGroup\n",
      "   IsPolycyclicGroup\n",
      "   HasIsInfiniteAbelianizationGroup\n",
      "   IsSubgroupFgGroup\n",
      "   IsSubgroupFpGroup\n",
      "   IsEnumerableSemigroupRep\n",
      "\n"
     ]
    }
   ],
   "source": [
    "ShowImpliedFilters(IsGroup);"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Therefore, mathematically and in GAP, everything that satisfies `IsGroup` also satisfies `IsSemigroup`. That's a relief, at least."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Mathematically, perhaps the “easiest” semigroup to define is the empty semigroup, $\\varnothing$. This is also our first example of a semigroup that is not a group. But for technical reasons, this is a difficult semigroup to handle computationally! \n",
    "\n",
    "In this mini-course, we will ignore the empty semigroup, and avoid creating it."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Constructing semigroups from multiplication tables"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "One of the most basic ways of constructing a finite semigroup in GAP is by specifying its multiplication table.\n",
    "\n",
    "If a semigroup has $n$ elements, then we can name the elements with the numbers $\\{1, \\ldots, n\\}$ (i.e. we can enumerate them). The multiplication table is then a list `mult` of $n$ lists of length $n$, where `mult[i][j]` stores the value of $i \\ast j$ in the semigroup."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "For example, the following multiplication table defines a semigroup with four elements.\n",
    "$$\n",
    "\\begin{array}{l|rrrr}\n",
    "  \\ast & 1 & 2 & 3 & 4 \\\\\n",
    "  \\hline\n",
    "  1 & 1 & 2 & 3 & 4 \\\\\n",
    "  2 & 2 & 1 & 3 & 4 \\\\\n",
    "  3 & 3 & 4 & 3 & 4 \\\\\n",
    "  4 & 4 & 3 & 3 & 4\n",
    "\\end{array}\n",
    "$$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**How do we check that this magma is associative?** It's certainly not immediately obvious! We'll ignore that for now."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "In a Cayley tables for a group, every row and every column contains each element of the group exactly once: the multiplication table gives a Latin square.\n",
    "\n",
    "This is not the case for semigroups in general.\n",
    "\n",
    "Here, $2$ occurs twice in the second row, and $4$ is the only entry in the first column. Therefore the semigroup is **definitely** not a group. (We're still taking it on faith that it defines a semigroup)."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Let's create this table in GAP, as a list-of-lists:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {},
   "outputs": [],
   "source": [
    "mult := [\n",
    "[1, 2, 3, 4],\n",
    "[2, 1, 3, 4],\n",
    "[3, 4, 3, 4],\n",
    "[4, 3, 3, 4]\n",
    "];;"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[ [  1,  2,  3,  4 ],\n",
      "  [  2,  1,  3,  4 ],\n",
      "  [  3,  4,  3,  4 ],\n",
      "  [  4,  3,  3,  4 ] ]\n"
     ]
    }
   ],
   "source": [
    "Display(mult);"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We can create a semigroup object (to which we can apply semigroup-related methods in GAP) from a multiplication table by using the command `SemigroupByMultiplicationTable`."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "<semigroup of size 4, with 4 generators>"
      ]
     },
     "execution_count": 12,
     "metadata": {
      "text/plain": ""
     },
     "output_type": "execute_result"
    }
   ],
   "source": [
    "S := SemigroupByMultiplicationTable(mult);"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "4"
      ]
     },
     "execution_count": 13,
     "metadata": {
      "text/plain": ""
     },
     "output_type": "execute_result"
    }
   ],
   "source": [
    "Size(S);"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "*Note that `SemigroupByMultiplicationTable` incorporates a test for associativity: if we give it a multiplication table that does not define an associative magma, then GAP returns `fail`...*"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "fail"
      ]
     },
     "execution_count": 14,
     "metadata": {
      "text/plain": ""
     },
     "output_type": "execute_result"
    }
   ],
   "source": [
    "SemigroupByMultiplicationTable([[1, 1], [2, 1]]);"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Let's introduce some other semigroup-theoretic notions"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Back to our previous semigroup $S$, with $4$ elements. The fact that the first row and column of the multiplication table give the same entries as their labels indicates that $1$ is an *identity element* for the semigroup that it defines. In other words, this multiplication table defines a *monoid* that is not a group.\n",
    "\n",
    "**Not every semigroup contains an identity element!**"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "metadata": {},
   "outputs": [],
   "source": [
    "identity := MultiplicativeNeutralElement(S);;"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 16,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "true"
      ]
     },
     "execution_count": 16,
     "metadata": {
      "text/plain": ""
     },
     "output_type": "execute_result"
    }
   ],
   "source": [
    "ForAll(S, s -> identity * s = s and s * identity = s);"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "A semigroup $S$ is *commutative* if, for all $x, y \\in S$, $xy = yx$. A commutative group is more commonly called *abelian*, but we don't use this name for semigroups."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 17,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "false"
      ]
     },
     "execution_count": 17,
     "metadata": {
      "text/plain": ""
     },
     "output_type": "execute_result"
    }
   ],
   "source": [
    "IsCommutative(S);"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "An element $x$ of a semigroup is *idempotent* if $x^2 = x$.\n",
    "\n",
    "A group contains exactly one idempotent (its identity element). A finite semigroup contains at least one idempotent. For some semigroups, every element is an idempotent (such a semigroup is called a *band*); and it is possible to have any number of idempotents in between."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "3 of the 4 elements in our semigroup $S$ are idempotent:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 18,
   "metadata": {
    "scrolled": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "3"
      ]
     },
     "execution_count": 18,
     "metadata": {
      "text/plain": ""
     },
     "output_type": "execute_result"
    }
   ],
   "source": [
    "Number(S, s -> s ^ 2 = s);"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Or, using the built-in GAP function `IsIdempotent`:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 19,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "3"
      ]
     },
     "execution_count": 19,
     "metadata": {
      "text/plain": ""
     },
     "output_type": "execute_result"
    }
   ],
   "source": [
    "Number(S, IsIdempotent);"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "A semigroup $S$ is *regular* if, for all $x \\in S$, there exists $y \\in S$ such that $x = xyx$. Every group is regular: set $y = x^{-1}$."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 20,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "true"
      ]
     },
     "execution_count": 20,
     "metadata": {
      "text/plain": ""
     },
     "output_type": "execute_result"
    }
   ],
   "source": [
    "IsRegularSemigroup(S);"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "A semigroup $S$ is *inverse* if, for all $x \\in S$, there exists a **unique** $y \\in S$ such that $x = xyx$ and $y = yxy$. This unique element $y$ is often written as $x^{-1}$.\n",
    "\n",
    "**Note that `x * x^-1` does not necessary give you the identity element – in fact, an inverse semigroup does not even need to possess an identity!**"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 21,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "false"
      ]
     },
     "execution_count": 21,
     "metadata": {
      "text/plain": ""
     },
     "output_type": "execute_result"
    }
   ],
   "source": [
    "IsInverseSemigroup(S);"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Roughly, to give you a bit of intuition**:\n",
    "\n",
    "* Groups capture structure-perserving bijections on a structure (automorphisms/symmetries);\n",
    "* Inverse semigroups capture structure-preserving bijections between substructures of a structure (partial automorphisms/symmetries);\n",
    "* Semigroups in general capture arbitrary structure-preserving functions on a structure (endomorphisms).\n",
    "\n",
    "**For instance, if the structure is a group $G$:**\n",
    "\n",
    "* We use a group to capture the automorphisms of $G$;\n",
    "* We could use an inverse subsemigroup to capture the isomorphisms between subgroups of $G$;\n",
    "* We could use a semigroup to capture the homomorphisms from $G$ to itself."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Downsides of multiplication tables"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We almost never use multiplication tables:\n",
    "\n",
    "* They are tedious and very fiddly to type into a computer.\n",
    "* They use a lot of memory: roughly $n^2 * log_{2}n$ bits. This can get too big very easily.\n",
    "* It takes time to verify that a multiplication table describes an associative operation.\n",
    "* For practical reasons, it is only possible to create finite semigroups this way!"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Constructing semigroups by generators"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "By using a generating set, you can often specify a semigroup $S$ by using many fewer elements than $S$ contains in total."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "For basically any algorithm, the complexity is given in terms of the number of generators of the semigroup (amongst other things). **The smaller the generating set, the better**."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "A lot of effort goes into describing ”small” generating sets of semigroups. A group $G$ requires at most $\\log_{2}|G|$ generators; a semigroup $S$ may require $|S|$ generators."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**What kind of generators do we use in GAP?**"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Abstract: finitely-presented semigroups"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "You can create finitely-generated free semigroups and quotients by finitely generated congruences (finitely-presented semigroups) in GAP, similarly to finitely-presented groups, but I will not talk about them further."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 22,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "<infinite semigroup with 2 generators>"
      ]
     },
     "execution_count": 22,
     "metadata": {
      "text/plain": ""
     },
     "output_type": "execute_result"
    }
   ],
   "source": [
    "F := FreeSemigroup(\"a\", \"b\");"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 24,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "<object>"
      ]
     },
     "execution_count": 23,
     "metadata": {
      "text/plain": ""
     },
     "output_type": "execute_result"
    },
    {
     "data": {
      "text/plain": [
       "<object>"
      ]
     },
     "execution_count": 24,
     "metadata": {
      "text/plain": ""
     },
     "output_type": "execute_result"
    }
   ],
   "source": [
    "a := F.1; b := F.2;"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 25,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "<semigroup with 2 generators>"
      ]
     },
     "execution_count": 25,
     "metadata": {
      "text/plain": ""
     },
     "output_type": "execute_result"
    }
   ],
   "source": [
    "S := F / [[a ^ 3, b ^ 2], [a * b * a, b ^ 2 * a]];"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 26,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "15"
      ]
     },
     "execution_count": 26,
     "metadata": {
      "text/plain": ""
     },
     "output_type": "execute_result"
    }
   ],
   "source": [
    "Size(S);"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "See the `kbmag` package for GAP by Derek Holt for additional functionality for fp-semigroups and monoids:\n",
    "\n",
    "https://gap-packages.github.io/kbmag"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Transformation semigroups"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Permutations are to groups as transformations are to semigroups."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "A *permutation* of degree $n$ is a bijective function from $\\{1, \\ldots, n\\}$ to itself (i.e. an *automorphism* of $\\{1, \\ldots, n\\}$).\n",
    "\n",
    "A *transformation* of degree $n$ is any old function from $\\{1, \\ldots, n\\}$ to itself (i.e. an *endomorphism* of $\\{1, \\ldots, n\\}$)."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Possibly you were first introduced to permutations via two-line notation. The following is one way of writing the permutation of degree $4$ that reverses the order of $\\{1, 2, 3, 4\\}$:"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "$$\n",
    "\\begin{pmatrix}\n",
    "  1 & 2 & 3 & 4 \\\\\n",
    "  4 & 3 & 2 & 1\n",
    "\\end{pmatrix}\n",
    "$$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "It means that 1 maps to 4, 2 maps to 3, 3 maps to 2, and 4 maps to 1. \n",
    "\n",
    "If we remove the restriction that the bottom line contains each number in $\\{1, \\ldots, n\\}$ exactly once, then we get the transformations. For example:"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "$$\n",
    "x = \\begin{pmatrix}\n",
    "  1 & 2 & 3 & 4 & 5 \\\\\n",
    "  3 & 3 & 3 & 3 & 3\n",
    "\\end{pmatrix}\n",
    "$$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "is the constant transformation of degree $5$ with image $3$, and"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "$$\n",
    "y = \\begin{pmatrix}\n",
    "  1 & 2 & 3 & 4 & 5 \\\\\n",
    "  1 & 2 & 1 & 4 & 1\n",
    "\\end{pmatrix}\n",
    "$$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "is the transformation of degree $5$ corresponding to $x \\mapsto \\textrm{gcd}(x, 4)$."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We can create a transformation in GAP by listing its bottom line when it is written in two-line notation:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 27,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "Transformation( [ 3, 3, 3, 3, 3 ] )"
      ]
     },
     "execution_count": 27,
     "metadata": {
      "text/plain": ""
     },
     "output_type": "execute_result"
    }
   ],
   "source": [
    "x := Transformation([3, 3, 3, 3, 3]);"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 28,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "Transformation( [ 1, 2, 1, 4, 1 ] )"
      ]
     },
     "execution_count": 28,
     "metadata": {
      "text/plain": ""
     },
     "output_type": "execute_result"
    }
   ],
   "source": [
    "y := Transformation([1, 2, 1, 4, 1]);"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "As with permutations, you can compose transformations, and this composition is associative. (We compose from left to right in GAP). Therefore you can make semigroups of transformations.\n",
    "\n",
    "You can make transformation semigroups in GAP by using the command `Semigroup`:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 29,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "<transformation semigroup of degree 5 with 2 generators>"
      ]
     },
     "execution_count": 29,
     "metadata": {
      "text/plain": ""
     },
     "output_type": "execute_result"
    }
   ],
   "source": [
    "S := Semigroup(x, y);"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 30,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "3"
      ]
     },
     "execution_count": 30,
     "metadata": {
      "text/plain": ""
     },
     "output_type": "execute_result"
    }
   ],
   "source": [
    "Size(S);"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 31,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[ Transformation( [ 1, 1, 1, 1, 1 ] ) ]"
      ]
     },
     "execution_count": 31,
     "metadata": {
      "text/plain": ""
     },
     "output_type": "execute_result"
    }
   ],
   "source": [
    "Difference(S, [x, y]);"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "So here, our generators `x` and `y` only generate one additional element."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Brief detour"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "In fact, you can use the command `Semigroup` to create a semigroup out of almost any set of elements for which there is an associative operation defined via the function `*`. For instance: matrices in GAP, binary relations, general mappings (with equal `Source` and `Range`)..."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Specifically, your list of generators must satisfy `IsGeneratorsOfSemigroup`."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 32,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[ <object>, <object> ]"
      ]
     },
     "execution_count": 32,
     "metadata": {
      "text/plain": ""
     },
     "output_type": "execute_result"
    }
   ],
   "source": [
    "relations := [\n",
    "BinaryRelationOnPoints([[1, 3], [2], [3]]),\n",
    "BinaryRelationOnPoints([[2], [2], [1, 3]])\n",
    "];"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 33,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "true"
      ]
     },
     "execution_count": 33,
     "metadata": {
      "text/plain": ""
     },
     "output_type": "execute_result"
    }
   ],
   "source": [
    "IsGeneratorsOfSemigroup(relations);"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 34,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "<semigroup with 2 generators>"
      ]
     },
     "execution_count": 34,
     "metadata": {
      "text/plain": ""
     },
     "output_type": "execute_result"
    }
   ],
   "source": [
    "T := Semigroup(relations);"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 35,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "5"
      ]
     },
     "execution_count": 35,
     "metadata": {
      "text/plain": ""
     },
     "output_type": "execute_result"
    }
   ],
   "source": [
    "Size(T);"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Let's randomly generate some transformation semigroups"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "You can use the GAP function `RandomTransformation(deg)` to create a random transformation of degree `deg`. By calling this repeatedly, we can create a “random” generating set, and hence, a “random” semigroup."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 36,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "function( deg, k ) ... end"
      ]
     },
     "execution_count": 36,
     "metadata": {
      "text/plain": ""
     },
     "output_type": "execute_result"
    }
   ],
   "source": [
    "random_trans_semigroup := function(deg, k)\n",
    "    local gens;\n",
    "    gens := List([1 .. k], i -> RandomTransformation(deg));\n",
    "    return Semigroup(gens);\n",
    "end;"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 37,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "<transformation semigroup of degree 6 with 4 generators>"
      ]
     },
     "execution_count": 37,
     "metadata": {
      "text/plain": ""
     },
     "output_type": "execute_result"
    }
   ],
   "source": [
    "S := random_trans_semigroup(6, 4);"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 38,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "3699"
      ]
     },
     "execution_count": 38,
     "metadata": {
      "text/plain": ""
     },
     "output_type": "execute_result"
    }
   ],
   "source": [
    "Size(S);"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 39,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "<transformation semigroup of degree 8 with 2 generators>"
      ]
     },
     "execution_count": 39,
     "metadata": {
      "text/plain": ""
     },
     "output_type": "execute_result"
    }
   ],
   "source": [
    "T := random_trans_semigroup(8, 2);"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 40,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "458"
      ]
     },
     "execution_count": 40,
     "metadata": {
      "text/plain": ""
     },
     "output_type": "execute_result"
    }
   ],
   "source": [
    "Size(T);"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### The full transformation semigroup/monoid"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The semigroup (indeed, it's a monoid) of all transformations of degree $n$, with the operation of composition of functions, is called the *full transformation semigroup (or monoid) of degree $n$*, written $T_{n}$. You can use both `FullTransformationSemigroup` and `FullTransformationMonoid` to do create it in GAP."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 41,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "<full transformation monoid of degree 5>"
      ]
     },
     "execution_count": 41,
     "metadata": {
      "text/plain": ""
     },
     "output_type": "execute_result"
    }
   ],
   "source": [
    "S := FullTransformationSemigroup(5);"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 42,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "<full transformation monoid of degree 6>"
      ]
     },
     "execution_count": 42,
     "metadata": {
      "text/plain": ""
     },
     "output_type": "execute_result"
    }
   ],
   "source": [
    "S := FullTransformationMonoid(6);"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Analogue of Cayley's theorem for semigroups"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Cayley's theorem for groups:** every group $G$ embeds into $S_{|G|}$.\n",
    "\n",
    "Idea (right regular action): we associate a number to each $g \\in G$. Then, for each $g \\in G$, the permutation in $S_{|G|}$ corresponding to $g$ is the one that maps $x$ to $x * g$, for all $x \\in G$.\n",
    "\n",
    "**For semigroups:** every semigroup $S$ embeds into $T_{|S| + 1}$.\n",
    "\n",
    "Idea: we associate a number to each $s \\in S$. Then, for each $s \\in S$, the transformation in $T_{|S| + 1}$ corresponding to $s$ is the one that maps $x$ to $x * s$, for all $x \\in S$, **and it maps a new element $\\Omega$ to $s$**."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "If GAP has no better ideas, then it uses this idea when you call `IsomorphismTransformationSemigroup` for a finite semigroup.\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 43,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "<semigroup of size 2, with 2 generators>"
      ]
     },
     "execution_count": 43,
     "metadata": {
      "text/plain": ""
     },
     "output_type": "execute_result"
    }
   ],
   "source": [
    "S := SemigroupByMultiplicationTable([[1, 1], [2, 2]]);"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 44,
   "metadata": {},
   "outputs": [],
   "source": [
    "iso := IsomorphismTransformationSemigroup(S);;"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 45,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "<transformation semigroup of size 2, degree 3 with 2 generators>"
      ]
     },
     "execution_count": 45,
     "metadata": {
      "text/plain": ""
     },
     "output_type": "execute_result"
    }
   ],
   "source": [
    "T := Range(iso);"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Being able to find small degree transformation representations of semigroups would be really nice! But it's difficult.** Some of the exercises will be related to this topic."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Semigroups of partial permutations (or partial perms)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Permutations are to groups as partial permutations are to inverse semigroups."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "A *partial permutation* of degree $n$ is any **injective, partial** function from $\\{1, \\ldots, n\\}$ to itself (i.e. any partial automorphism of $\\{1, \\ldots, n\\}$.\n",
    "\n",
    "When written in two-line notation, the bottom line should contain no repeats, but not every space needs to be completed. We use a dash \"–\" in this notation to indicate that the image of a point is undefined. For example:"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "$$\n",
    "x = \\begin{pmatrix}\n",
    "  1 & 2 & 3 & 4 & 5 \\\\\n",
    "  5 & - & 1 & 2 & -\n",
    "\\end{pmatrix}\n",
    "$$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "is the partial permutation mapping $1 \\to 5$, and $3 \\to 1$, and $4 \\to 2$, and where $2$ and $5$ are not in the domain."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "You can create a partial perm in GAP in two ways: firstly, by listing the bottom line; using the integer `0` to denote 'undefined':"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 46,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[3,1,5][4,2]"
      ]
     },
     "execution_count": 46,
     "metadata": {
      "text/plain": ""
     },
     "output_type": "execute_result"
    }
   ],
   "source": [
    "x1 := PartialPerm([5, 0, 1, 2, 0]);"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Secondly, you can create a partial perm in GAP by listing the domain (in ascending order), and then listing, in order, in the image of each point in the domain:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 47,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[3,1,5][4,2]"
      ]
     },
     "execution_count": 47,
     "metadata": {
      "text/plain": ""
     },
     "output_type": "execute_result"
    }
   ],
   "source": [
    "x2 := PartialPerm([1, 3, 4], [5, 1, 2]);"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 48,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "true"
      ]
     },
     "execution_count": 48,
     "metadata": {
      "text/plain": ""
     },
     "output_type": "execute_result"
    }
   ],
   "source": [
    "x1 = x2;"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### The symmetric inverse semigroup/monoid"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The semigroup of all partial perms of degree $n$ is called the symmetric inverse semigroup (or monoid)."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 49,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "<symmetric inverse monoid of degree 4>"
      ]
     },
     "execution_count": 49,
     "metadata": {
      "text/plain": ""
     },
     "output_type": "execute_result"
    }
   ],
   "source": [
    "S := SymmetricInverseSemigroup(4);"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 50,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "true"
      ]
     },
     "execution_count": 50,
     "metadata": {
      "text/plain": ""
     },
     "output_type": "execute_result"
    }
   ],
   "source": [
    "IsInverseSemigroup(S);"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 51,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "<symmetric inverse monoid of degree 5>"
      ]
     },
     "execution_count": 51,
     "metadata": {
      "text/plain": ""
     },
     "output_type": "execute_result"
    }
   ],
   "source": [
    "T := SymmetricInverseMonoid(5);"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 52,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "true"
      ]
     },
     "execution_count": 52,
     "metadata": {
      "text/plain": ""
     },
     "output_type": "execute_result"
    }
   ],
   "source": [
    "IsInverseSemigroup(T);"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 53,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "1546"
      ]
     },
     "execution_count": 53,
     "metadata": {
      "text/plain": ""
     },
     "output_type": "execute_result"
    }
   ],
   "source": [
    "Size(T);"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "There is an analogue of Cayley's theorem which states that every inverse semigroup $S$ is isomorphic to an inverse subsemigroup of the symmetric inverse monoid of degree $|S|$.\n",
    "\n",
    "So: all inverse semigroups can be represented as semigroups of partial perms. The inverse in the semigroup is the obvious inverse of the function:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 54,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[2,4][5,1,3]"
      ]
     },
     "execution_count": 54,
     "metadata": {
      "text/plain": ""
     },
     "output_type": "execute_result"
    }
   ],
   "source": [
    "x1 ^ -1;"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 55,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[2,4][5,1,3]"
      ]
     },
     "execution_count": 55,
     "metadata": {
      "text/plain": ""
     },
     "output_type": "execute_result"
    }
   ],
   "source": [
    "x2 ^ -1;"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "However, it is also possible to create semigroups of partial permutations that are *not* inverse:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 56,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "<commutative partial perm semigroup of rank 4 with 1 generator>"
      ]
     },
     "execution_count": 56,
     "metadata": {
      "text/plain": ""
     },
     "output_type": "execute_result"
    }
   ],
   "source": [
    "S := Semigroup(PartialPerm([2, 4, 0, 1, 3]));"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 57,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "false"
      ]
     },
     "execution_count": 57,
     "metadata": {
      "text/plain": ""
     },
     "output_type": "execute_result"
    }
   ],
   "source": [
    "IsInverseSemigroup(S);"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Exercises"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Multiplication tables"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "1. For each $n \\in \\mathbb{N}$, how many binary operations are there on a set of $n$ elements? Equivalently, how many $n \\times n$ multiplication tables are there?"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "2. Construct all $3 \\times 3$ multiplication tables in GAP, where each multiplication table is a list of $3$ lists of length $3$, whose entries are from $\\{1, 2, 3\\}$. If you don't want to do this, use the following code:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 60,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "function( n ) ... end"
      ]
     },
     "execution_count": 58,
     "metadata": {
      "text/plain": ""
     },
     "output_type": "execute_result"
    },
    {
     "data": {
      "text/plain": [
       "19683"
      ]
     },
     "execution_count": 60,
     "metadata": {
      "text/plain": ""
     },
     "output_type": "execute_result"
    }
   ],
   "source": [
    "all_tables := function(n)\n",
    "  local table, tables, iter, choice;\n",
    "  tables := [];\n",
    "  iter := IteratorOfTuples([1 .. n], n * n);\n",
    "  for choice in iter do\n",
    "    table := List([0, 1 .. n - 1],\n",
    "                  i -> choice{[(n * i) + 1 .. (n * (i + 1))]});\n",
    "    Add(tables, table);\n",
    "  od;\n",
    "  return tables;\n",
    "end;\n",
    "all_tables_3 := all_tables(3);;\n",
    "Length(all_tables_3);"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "3. How many define semigroups?"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "4. How many define commutative semigroups?"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "5. How many define monoids?"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "6. How many define bands? (A band is a semigroup in which every element is idempotent.)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "7. How many define regular semigroups?"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Transformation and partial perm semigroups"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "1. How many elements does the full transformation monoid of degree $n$ contain? Equivalently, how many transformations are there of degree $n$?"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "2. How many elements does the symmetric inverse monoid of degree $n$ contain? Equivalently, how many partial permutations are there of degree $n$?"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "3. When doing the analogue of Cayley's theorem for semigroups, why did we need to invent this new element $\\Omega$?  What if we just did the same thing as for groups?\n",
    "\n",
    "    * Write a function `f` which takes a multiplication table `tab` and an element `s` in the semigroup, and returns a transformation such that `f(tab, s)` maps $x$ to $x * s$ (i.e. `x` is mapped to `tab[x][s]`), for all $x \\in S$.\n",
    "\n",
    "    * Find some semigroups with three elements (using the multiplication tables from above) where this function is **not** injective, and therefore not an isomorphism."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "4. Write a function that takes a multiplication table defining a semigroup $S$, and returns a transformation semigroup that is isomorphic to $S$, using the analogue of Cayley's theorem."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "5. Write a function that takes a `SemigroupByMultiplicationTable`, called `S`, and returns an *isomorphism* to a transformation semigroup `T`, using `MagmaHomomorphismByFunctionsNC`. To do this, the first argument to `MagmaHomomorphismByFunctionsNC` should be `S`, the second should be `T`, and the third argument should be a GAP function that takes an element of `S` to its corresponding element of `T`. (If you really want to over-achieve, look at the GAP code for `MagmaIsomorphismByFunctionsNC` and use that)."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "GAP 4",
   "language": "gap",
   "name": "gap-4"
  },
  "language_info": {
   "codemirror_mode": "gap",
   "file_extension": ".g",
   "mimetype": "text/x-gap",
   "name": "GAP 4",
   "nbconvert_exporter": "",
   "pygments_lexer": "gap",
   "version": "4.dev"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}