notebooks/smallsemi.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "*“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": [
    "# The `Smallsemi` package\n",
    "http://www-groups.mcs.st-andrews.ac.uk/~jamesm/smallsemi.php\n",
    "\n",
    "**Authors**: Andreas Distler, James D. Mitchell"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "> The Smallsemi package is a data library of semigroups of small size. It provides all semigroups with at most 8 elements as well as various information about these objects."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Semigroups are considered to be equivalent if they are either *isomorphic* or *anti-isomorphic*.\n",
    "\n",
    "* Isomorphism: bijective homomorphism $(xy)\\phi \\mapsto x\\phi y\\phi$\n",
    "* Anti-isomorphism: bijective anti-homomorphism $(xy)\\phi \\mapsto y\\phi x\\phi$ (order reversed)\n",
    "\n",
    "Inversion of a group is an anti-isomorphism."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Let's load the package**"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "true"
      ]
     },
     "execution_count": 1,
     "metadata": {
      "text/plain": ""
     },
     "output_type": "execute_result"
    }
   ],
   "source": [
    "LoadPackage(\"smallsemi\");"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "For now, let's turn off the (useful) extra information that Smallsemi provides:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [],
   "source": [
    "SetInfoLevel(InfoSmallsemi, 0);"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### How many semigroups does Smallsemi contain?"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We use the function `NrSmallSemigroups`."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "# semigroups of order 1: 1\n",
      "# semigroups of order 2: 4\n",
      "# semigroups of order 3: 18\n",
      "# semigroups of order 4: 126\n",
      "# semigroups of order 5: 1160\n",
      "# semigroups of order 6: 15973\n",
      "# semigroups of order 7: 836021\n",
      "# semigroups of order 8: 1843120128\n"
     ]
    }
   ],
   "source": [
    "for i in [1 .. 8] do\n",
    "    Print(\"# semigroups of order \", i, \": \");\n",
    "    Print(NrSmallSemigroups(i), \"\\n\");\n",
    "od;"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "From the `Smallsemi` website:"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "> The reason that semigroups of higher orders are not included is the huge number of such objects."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Orders that are not contained in the smallsemi library:"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "`# semigroups of order 9:  52 989 400 714 478`\n",
    "<br />\n",
    "https://doi.org/10.1007/s00233-013-9504-9"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "`# semigroups of order 10: 12 418 001 077 381 302 684`\n",
    "<br />\n",
    "http://dx.doi.org/10.1007/978-3-642-33558-7_63"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "`# semigroups of order 11... unknown!`"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### What are some of the basic features of `Smallsemi`?"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Very similar to the `SmallGrp` library/package."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Constructing semigroups from the library by ID:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "<semigroup of size 2, with 2 generators>"
      ]
     },
     "execution_count": 4,
     "metadata": {
      "text/plain": ""
     },
     "output_type": "execute_result"
    }
   ],
   "source": [
    "S := SmallSemigroup(2, 4);"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "<semigroup of size 5, with 5 generators>"
      ]
     },
     "execution_count": 5,
     "metadata": {
      "text/plain": ""
     },
     "output_type": "execute_result"
    }
   ],
   "source": [
    "S := SmallSemigroup(5, 1000);"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "<semigroup of size 7, with 7 generators>"
      ]
     },
     "execution_count": 6,
     "metadata": {
      "text/plain": ""
     },
     "output_type": "execute_result"
    }
   ],
   "source": [
    "S := SmallSemigroup(7, 502301);"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[ 7, 502301 ]"
      ]
     },
     "execution_count": 7,
     "metadata": {
      "text/plain": ""
     },
     "output_type": "execute_result"
    }
   ],
   "source": [
    "IdSmallSemigroup(S);"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "<semigroup of size 6, with 6 generators>"
      ]
     },
     "execution_count": 8,
     "metadata": {
      "text/plain": ""
     },
     "output_type": "execute_result"
    },
    {
     "data": {
      "text/plain": [
       "[ 6, 5685 ]"
      ]
     },
     "execution_count": 9,
     "metadata": {
      "text/plain": ""
     },
     "output_type": "execute_result"
    }
   ],
   "source": [
    "S := RandomSmallSemigroup([5, 6]); IdSmallSemigroup(S);"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Much information about semigroups from the `Smallsemi` package is pre-computed, including:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[ \"Size\", \"RepresentativeSmallest\", \"Enumerator\", \"EnumeratorSorted\", \"AsList\", \"AsSSortedList\", \"GeneratorsOfDomain\", \"GeneratorsOfMagma\", \"MultiplicationTable\", \"IdSmallSemigroup\" ]"
      ]
     },
     "execution_count": 10,
     "metadata": {
      "text/plain": ""
     },
     "output_type": "execute_result"
    }
   ],
   "source": [
    "KnownAttributesOfObject(S);"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "In fact, the precise information that is pre-computed is available in the global variable list called `PrecomputedSmallSemisInfo`:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[ \"Is2GeneratedSemigroup\", \"Is3GeneratedSemigroup\", \"Is4GeneratedSemigroup\", \n",
      "  \"Is5GeneratedSemigroup\", \"Is6GeneratedSemigroup\", \"Is7GeneratedSemigroup\", \n",
      "  \"Is8GeneratedSemigroup\", \"IsBand\", \"IsCommutative\", \n",
      "  \"IsCompletelyRegularSemigroup\", \"IsFullTransformationSemigroupCopy\", \n",
      "  \"IsGroupAsSemigroup\", \"IsIdempotentGenerated\", \"IsInverseSemigroup\", \n",
      "  \"IsMonogenicSemigroup\", \"IsMonoidAsSemigroup\", \"IsMultSemigroupOfNearRing\", \n",
      "  \"IsRegularSemigroup\", \"IsSelfDualSemigroup\", \n",
      "  \"IsSemigroupWithoutClosedIdempotents\", \"IsSimpleSemigroup\", \n",
      "  \"IsSingularSemigroupCopy\", \"IsZeroSemigroup\", \"IsZeroSimpleSemigroup\" ]\n"
     ]
    }
   ],
   "source": [
    "Display(PrecomputedSmallSemisInfo[6]);"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Semigroups in `Smallsemi` are essentially stored by their multiplication tables."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[ [  1,  1,  1,  1,  1,  1 ],\n",
      "  [  1,  1,  1,  3,  1,  1 ],\n",
      "  [  1,  1,  1,  1,  1,  1 ],\n",
      "  [  1,  3,  1,  2,  1,  1 ],\n",
      "  [  5,  5,  5,  5,  5,  5 ],\n",
      "  [  6,  6,  6,  6,  6,  6 ] ]\n"
     ]
    }
   ],
   "source": [
    "Display(MultiplicationTable(S));"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Counting or selecting certain semigroups from the library\n",
    "\n",
    "This is particularly quick when filtering by precomputed data."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "19833"
      ]
     },
     "execution_count": 13,
     "metadata": {
      "text/plain": ""
     },
     "output_type": "execute_result"
    }
   ],
   "source": [
    "nr_comm := NrSmallSemigroups([1 .. 7], IsCommutative, true);"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "833470"
      ]
     },
     "execution_count": 14,
     "metadata": {
      "text/plain": ""
     },
     "output_type": "execute_result"
    }
   ],
   "source": [
    "nr_non_comm := NrSmallSemigroups([1 .. 7], IsCommutative, false);"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "true"
      ]
     },
     "execution_count": 15,
     "metadata": {
      "text/plain": ""
     },
     "output_type": "execute_result"
    }
   ],
   "source": [
    "nr_comm + nr_non_comm = NrSmallSemigroups([1 .. 7]);"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 16,
   "metadata": {},
   "outputs": [],
   "source": [
    "semigps := AllSmallSemigroups([3, 4],\n",
    "                              IsBand, true,\n",
    "                              MultiplicativeZero, fail);;"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 17,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "19"
      ]
     },
     "execution_count": 17,
     "metadata": {
      "text/plain": ""
     },
     "output_type": "execute_result"
    }
   ],
   "source": [
    "Length(semigps);"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 18,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "fail"
      ]
     },
     "execution_count": 18,
     "metadata": {
      "text/plain": ""
     },
     "output_type": "execute_result"
    }
   ],
   "source": [
    "S := OneSmallSemigroup([1 .. 7],\n",
    "                       IsBand, true,\n",
    "                       MultiplicativeZero, fail,\n",
    "                       IsCommutativeSemigroup, true);"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 19,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "<0-simple semigroup of size 5, with 5 generators>"
      ]
     },
     "execution_count": 19,
     "metadata": {
      "text/plain": ""
     },
     "output_type": "execute_result"
    }
   ],
   "source": [
    "S := OneSmallSemigroup([1 .. 8],\n",
    "IsZeroSimpleSemigroup, true,\n",
    "IsCompletelyRegularSemigroup, false);"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Recognising small semigroups"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 20,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "<full transformation monoid of degree 2>"
      ]
     },
     "execution_count": 20,
     "metadata": {
      "text/plain": ""
     },
     "output_type": "execute_result"
    }
   ],
   "source": [
    "S := FullTransformationMonoid(2);"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 21,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[ 4, 96 ]"
      ]
     },
     "execution_count": 21,
     "metadata": {
      "text/plain": ""
     },
     "output_type": "execute_result"
    }
   ],
   "source": [
    "IdSmallSemigroup(S);"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 22,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "<symmetric inverse monoid of degree 2>"
      ]
     },
     "execution_count": 22,
     "metadata": {
      "text/plain": ""
     },
     "output_type": "execute_result"
    }
   ],
   "source": [
    "S := SymmetricInverseMonoid(2);"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 23,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[ 7, 715832 ]"
      ]
     },
     "execution_count": 23,
     "metadata": {
      "text/plain": ""
     },
     "output_type": "execute_result"
    }
   ],
   "source": [
    "IdSmallSemigroup(S);"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 24,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "<non-regular semigroup with 6 generators>"
      ]
     },
     "execution_count": 24,
     "metadata": {
      "text/plain": ""
     },
     "output_type": "execute_result"
    }
   ],
   "source": [
    "S := ReesZeroMatrixSemigroup(SymmetricGroup(2), [[(1, 2), 0, ()]]);"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 25,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[ 7, 696865 ]"
      ]
     },
     "execution_count": 25,
     "metadata": {
      "text/plain": ""
     },
     "output_type": "execute_result"
    }
   ],
   "source": [
    "IdSmallSemigroup(S);"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 26,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "<object>"
      ]
     },
     "execution_count": 26,
     "metadata": {
      "text/plain": ""
     },
     "output_type": "execute_result"
    }
   ],
   "source": [
    "map := EquivalenceSmallSemigroup(S);"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 27,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "<semigroup of size 7, with 7 generators>"
      ]
     },
     "execution_count": 27,
     "metadata": {
      "text/plain": ""
     },
     "output_type": "execute_result"
    }
   ],
   "source": [
    "Range(map);"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 28,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "true"
      ]
     },
     "execution_count": 28,
     "metadata": {
      "text/plain": ""
     },
     "output_type": "execute_result"
    }
   ],
   "source": [
    "Range(map) = SmallSemigroup(IdSmallSemigroup(S));"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### 3-nilpotent semigroups\n",
    "\n",
    "* A semigroup $S$ is *nilpotent* (`IsNilpotentSemigroup`) if it has a multiplicative zero $0$, and there exists an $n \\in \\mathbb{N}$ such that every product of length $n$ in $S$ is equal to $0$.\n",
    "* The *nilpotency degree* (`NilpotencyDegree`) of a nilpotent semigroup is the least $n \\in \\mathbb{N}$ with the above property.\n",
    "* A semigroup is *n-nilpotent* if it is nilpotent with nilpotency degree $n$."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Let us count 3-nilpotent semigroups**"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 29,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[ 0, 0, 1, 8, 84, 2660 ]"
      ]
     },
     "execution_count": 29,
     "metadata": {
      "text/plain": ""
     },
     "output_type": "execute_result"
    }
   ],
   "source": [
    "List([1 .. 6], n -> NrSmallSemigroups(n,\n",
    "                        IsNilpotentSemigroup, true,\n",
    "                        NilpotencyDegree, 3));"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "In fact, a formula for the number of 3-nilpotent semigroups of order $n$, for any $n$, is known! It is available as `Nr3NilpotentSemigroups`."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Let us compare the number of 3-nilpotent semigroups to the number of all semigroups:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 30,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[ 0.0555556, 0.0634921, 0.0724138, 0.166531, 0.729404, 0.993797 ]"
      ]
     },
     "execution_count": 30,
     "metadata": {
      "text/plain": ""
     },
     "output_type": "execute_result"
    }
   ],
   "source": [
    "List([3 .. 8], n -> Float(Nr3NilpotentSemigroups(n) / NrSmallSemigroups(n)));"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "And for order 9:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 31,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "0.999563"
      ]
     },
     "execution_count": 31,
     "metadata": {
      "text/plain": ""
     },
     "output_type": "execute_result"
    }
   ],
   "source": [
    "Float(Nr3NilpotentSemigroups(9) / 52989400714478);"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "And for order 10:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 32,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "0.999942"
      ]
     },
     "execution_count": 32,
     "metadata": {
      "text/plain": ""
     },
     "output_type": "execute_result"
    }
   ],
   "source": [
    "Float(Nr3NilpotentSemigroups(10) / 12418001077381302684);"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**It is widely believed, but not proven, that this ratio tends to 1 as n tends to infinity.**"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Exercises for `Smallsemi`"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Counting small semigroups"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "1. For each $n \\in \\{1, \\ldots, 8\\}$, how many simple semigroups are there of order $n$?\n",
    "1. For each $n \\in \\{1, \\ldots, 8\\}$, how many zero simple semigroups are there of order $n$?\n",
    "1. For which $n \\in \\{1, \\ldots, 8\\}$ does there exist a rectangular band of order $n$ with an even number of `GreensRClasses`?"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Enumerating transformation semigroups of degree $2$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "4. How many transformation semigroups are there of degree 2?\n",
    "    * Equivalently, how many non-empty subsemigroups are there of `FullTransformationMonoid(2);`?\n",
    "    * Hint: use all non-empty subsets as generators, or repeatedly use the `MaximalSubsemigroups` method.\n",
    "* How many transformation semigroups are there of degree 2, up to isomorphism and anti-isomorphism?\n",
    "    * Hint: use `IdSmallGroup`."
   ]
  },
  {
   "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
}