{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Semigroups in GAP\n",
    "\n",
    "**Website**: http://cloud.gap-system.org"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# The Semigroups package\n",
    "The semigroups package needs to be loaded for the current worksheet."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "true"
     ]
    }
   ],
   "source": [
    "LoadPackage(\"semigroups\");"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Transformations\n",
    "\n",
    "Transformations are to semigroups as permutations are to groups.\n",
    "\n",
    "Mathematically, permutations are transformations, but in GAP they are not."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Transformation( [ 4, 1, 1, 5, 3, 3 ] )"
     ]
    }
   ],
   "source": [
    "f := Transformation([4, 1, 1, 5, 3, 3]);"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Transformation( [ 4, 5, 1, 2, 1, 4 ] )"
     ]
    }
   ],
   "source": [
    "g := Transformation([4, 5, 1, 2, 1, 4]);"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Transformation( [ 2, 4, 4, 1, 1, 1 ] )"
     ]
    }
   ],
   "source": [
    "f * g;"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "false"
     ]
    }
   ],
   "source": [
    "f * g = g * f;"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Transformation( [ 8, 8, 2, 3, 5, 5, 8, 4, 1, 8 ] )"
     ]
    }
   ],
   "source": [
    "x := RandomTransformation(10);"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Transformation( [ 1, 9, 7, 5, 3, 3, 7, 7, 5, 4 ] )"
     ]
    }
   ],
   "source": [
    "y := RandomTransformation(10);"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Transformation( [ 7, 9, 4, 5, 1, 10, 7, 1, 8, 5 ] )"
     ]
    }
   ],
   "source": [
    "z := RandomTransformation(10);"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "false"
     ]
    }
   ],
   "source": [
    "x * y = y * x; # commutativity"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "false"
     ]
    }
   ],
   "source": [
    "z * z = z; # idempotent?"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Composition of functions is associative..."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "true"
     ]
    }
   ],
   "source": [
    "(x * y) * z = x * (y * z); # associativity"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "... and so you can make semigroups out of transformations"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "<transformation semigroup of degree 10 with 3 generators>"
     ]
    }
   ],
   "source": [
    "S := Semigroup(x, y, z);"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "16831"
     ]
    }
   ],
   "source": [
    "Size(S);"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Transformation( [ 2, 3, 1 ] )"
     ]
    }
   ],
   "source": [
    "t := Transformation([2, 3, 1]);"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "(1,2,3)"
     ]
    }
   ],
   "source": [
    "p := AsPermutation(t);"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 16,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "false"
     ]
    }
   ],
   "source": [
    "p = t;"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 17,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "fail"
     ]
    }
   ],
   "source": [
    "AsPermutation(f);"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 18,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Transformation( [ 3, 1, 2 ] )"
     ]
    }
   ],
   "source": [
    "t * p;"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Permutations and transformations can be multiplied together, but you cannot create a semigroup with both elements."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 19,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Error, Usage: Semigroup(<gen>,...), Semigroup(<gens>), Semigroup(<D>),\r\n"
     ]
    }
   ],
   "source": [
    "Semigroup(t, p);"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# IsGroup vs IsMonoid vs IsSemigroup"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Something created as a semigroup may not satisfy `IsGroup` even if it is mathematically a group. We use `IsGroupAsSemigroup` to check for this.\n",
    "\n",
    "There are similar problems with `IsMonoid`. This the analogous property is `IsMonoidAsSemigroup`."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 20,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[ [ Z(5), Z(5)^2 ], [ Z(5)^3, Z(5)^2 ] ]"
     ]
    }
   ],
   "source": [
    "M := [ [ Z(5), Z(5)^2 ], [ Z(5)^3, Z(5)^2 ] ];"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 21,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "true"
     ]
    }
   ],
   "source": [
    "M in GL(2, 5);"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "** A group is also a monoid and a semigroup. **"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 22,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "<group with 1 generators>"
     ]
    }
   ],
   "source": [
    "G := Group(M);"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 23,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "true"
     ]
    }
   ],
   "source": [
    "IsSemigroup(G);"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 24,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "true"
     ]
    }
   ],
   "source": [
    "IsMonoid(G);"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 25,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "true"
     ]
    }
   ],
   "source": [
    "IsGroup(G);"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "** A semigroup is not (usually) a monoid or a group in GAP -- even if it is mathematically. **\n",
    "\n",
    "The category depends on how the object was created."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 26,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "<commutative semigroup with 1 generator>"
     ]
    }
   ],
   "source": [
    "S := Semigroup(M);"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 27,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "true"
     ]
    }
   ],
   "source": [
    "IsSemigroup(S);"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 28,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "false"
     ]
    }
   ],
   "source": [
    "IsMonoid(S);"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 29,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "true"
     ]
    }
   ],
   "source": [
    "IsMonoidAsSemigroup(S);"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 30,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "false"
     ]
    }
   ],
   "source": [
    "IsGroup(S);"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 31,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "true"
     ]
    }
   ],
   "source": [
    "IsGroupAsSemigroup(S);"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 32,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "true"
     ]
    }
   ],
   "source": [
    "G = S;"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "For an object in `IsGroup`, GAP needs to know that it can invert any element independently, and it needs how to do it.\n",
    "\n",
    "For a permutation, there is only ever one inverse, and it is easy to calculate.\n",
    "\n",
    "A transformation does not necessarily have an inverse, and so GAP needs to consider the whole semigroup to know how to invert an element in a group of transformations. So transformation groups are usually not in the category `IsGroup`, except..."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 33,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "true"
     ]
    }
   ],
   "source": [
    "IsGroup(FullTransformationSemigroup(1));"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Multiplication tables"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 34,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[ [ 1, 2, 3, 4 ], [ 2, 1, 3, 4 ], [ 3, 4, 3, 4 ], [ 4, 3, 3, 4 ] ]"
     ]
    }
   ],
   "source": [
    "A := [\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": 35,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "<semigroup of size 4, with 4 generators>"
     ]
    }
   ],
   "source": [
    "S := SemigroupByMultiplicationTable(A);"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 36,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "<full transformation monoid of degree 2>"
     ]
    }
   ],
   "source": [
    "T := FullTransformationSemigroup(2);"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 37,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "true"
     ]
    }
   ],
   "source": [
    "IsIsomorphicSemigroup(S, T);"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Creating standard examples"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 38,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "<full transformation monoid of degree 10>"
     ]
    }
   ],
   "source": [
    "S := FullTransformationSemigroup(10);"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 39,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Transformation( [ 2, 3, 4, 5, 6, 7, 8, 9, 1, 1 ] )"
     ]
    }
   ],
   "source": [
    "x := PseudoRandom(S);"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 40,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "<symmetric inverse monoid of degree 8>"
     ]
    }
   ],
   "source": [
    "I := SymmetricInverseSemigroup(8);"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 41,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[3,5,7](2,4,6,8)"
     ]
    }
   ],
   "source": [
    "x := PseudoRandom(I);"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 42,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "PartialPerm( [ 2, 3, 4, 5, 6, 8 ], [ 4, 5, 6, 7, 8, 2 ] )\r\n"
     ]
    }
   ],
   "source": [
    "Print(x);"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 43,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "<regular bipartition monoid of degree 4 with 4 generators>"
     ]
    }
   ],
   "source": [
    "P := PartitionMonoid(4);"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 44,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "<bipartition: [ 1, 2, -1, -2, -3 ], [ 3, -4 ], [ 4 ]>"
     ]
    }
   ],
   "source": [
    "x := PseudoRandom(P);"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 45,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Bipartition( [ [ 1, 2, -1, -2, -3 ], [ 3, -4 ], [ 4 ] ] )\r\n"
     ]
    }
   ],
   "source": [
    "Print(x);"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 46,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "<regular monoid of size 625, with 3 generators>"
     ]
    }
   ],
   "source": [
    "M := FullMatrixSemigroup(2, 5);"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 47,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "<matrix over GF(5) of degree 2>"
     ]
    }
   ],
   "source": [
    "x := PseudoRandom(GroupOfUnits(M));"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 48,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "NewMatrixOverFiniteField(IsPlistMatrixOverFiniteFieldRep, GF(5), 2, [ [ Z(5)^3, Z(5) ], [ Z(5)^2, 0*Z(5) ] ])\r\n"
     ]
    }
   ],
   "source": [
    "Print(x);"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 49,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "true"
     ]
    }
   ],
   "source": [
    "AsMatrix(x) in GL(2, 5);"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 50,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "false"
     ]
    }
   ],
   "source": [
    "IsSubsemigroup(M, GL(2, 5));"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 51,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[ [ Z(5)^3, Z(5)^0 ], [ 0*Z(5), Z(5) ] ]"
     ]
    }
   ],
   "source": [
    "x := Random(GL(2, 5));"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 52,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "true"
     ]
    }
   ],
   "source": [
    "NewMatrixOverFiniteField(IsPlistMatrixOverFiniteFieldRep, GF(5), 2, x) in M;"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Finitely presented semigroups"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 53,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "<infinite semigroup with 2 generators>"
     ]
    }
   ],
   "source": [
    "F := FreeSemigroup(\"x\", \"y\");"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 54,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "false"
     ]
    }
   ],
   "source": [
    "IsFinite(F);"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 55,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "<object>"
     ]
    }
   ],
   "source": [
    "x := F.1;"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 56,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "<object>"
     ]
    }
   ],
   "source": [
    "y := F.2;"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Relation 1**: x \\* y = y \\* x"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 57,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[ x*y, y*x ]"
     ]
    }
   ],
   "source": [
    "rel1 := [ x * y, y * x ];"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Relation 2**: x ^ 3 = x ^ 2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 58,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[ x^3, x^2 ]"
     ]
    }
   ],
   "source": [
    "rel2 := [ x ^ 3, x ^ 2 ];"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Relation 3**: y ^ 2 = y"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 59,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[ y^2, y ]"
     ]
    }
   ],
   "source": [
    "rel3 := [y ^ 2, y ];"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 60,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "<semigroup with 2 generators>"
     ]
    }
   ],
   "source": [
    "S := F / [rel1, rel2, rel3];"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 61,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "5"
     ]
    }
   ],
   "source": [
    "Size(S);"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 62,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[ x, y, x^2, x*y, x^2*y ]"
     ]
    }
   ],
   "source": [
    "Elements(S);"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 63,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "<semigroup with 2 generators>"
     ]
    }
   ],
   "source": [
    "T := F / [rel2, rel3];"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 64,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stderr",
     "output_type": "stream",
     "text": []
    }
   ],
   "source": [
    "# IsFinite(T);"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "collapsed": true
   },
   "source": [
    "# Exhaustive enumeration"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 65,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "<object>"
     ]
    }
   ],
   "source": [
    "enumerate_semigroup := function(gens)\n",
    "  local elts, x, g;\n",
    "\n",
    "  elts := ShallowCopy(gens);\n",
    "  for x in elts do\n",
    "    for g in gens do\n",
    "      if not x * g in elts then\n",
    "        Add(elts, x * g);\n",
    "      fi;\n",
    "    od;\n",
    "  od;\n",
    "  return elts;\n",
    "end;"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 66,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "665"
     ]
    }
   ],
   "source": [
    "Length(enumerate_semigroup([f, g]));"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 67,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "665"
     ]
    }
   ],
   "source": [
    "Size(Semigroup(f, g));"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Create the right Cayley graph during enumeration..."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 68,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "true"
     ]
    }
   ],
   "source": [
    "LoadPackage(\"digraphs\");"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 69,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "<object>"
     ]
    }
   ],
   "source": [
    "enumerate_with_graph := function(gens)\n",
    "  local elts, graph, adjacencies, pos, x, g, prod;\n",
    "\n",
    "  elts := ShallowCopy(gens);\n",
    "  graph := [];\n",
    "  for x in elts do\n",
    "    adjacencies := [];\n",
    "    for g in gens do\n",
    "      prod := x * g;\n",
    "      pos := Position(elts, prod);\n",
    "      if pos = fail then\n",
    "        Add(elts, prod);\n",
    "        Add(adjacencies, Length(elts));\n",
    "      else\n",
    "        Add(adjacencies, pos);\n",
    "      fi;\n",
    "    od;\n",
    "    Add(graph, adjacencies);\n",
    "  od;\n",
    "  return Digraph(graph);\n",
    "end;"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 70,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "<multidigraph with 4 vertices, 8 edges>"
     ]
    }
   ],
   "source": [
    "gr := enumerate_with_graph([Transformation([1, 1, 3]), Transformation([1, 2, 2])]);"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 71,
   "metadata": {
    "collapsed": false,
    "scrolled": true
   },
   "outputs": [
    {
     "data": {
      "image/svg+xml": [
       "<?xml version=\"1.0\" encoding=\"UTF-8\" standalone=\"no\"?>\n",
       "<!DOCTYPE svg PUBLIC \"-//W3C//DTD SVG 1.1//EN\"\n",
       " \"http://www.w3.org/Graphics/SVG/1.1/DTD/svg11.dtd\">\n",
       "<!-- Generated by graphviz version 2.38.0 (20140413.2041)\n",
       " -->\n",
       "<!-- Title: hgn Pages: 1 -->\n",
       "<svg width=\"134pt\" height=\"188pt\"\n",
       " viewBox=\"0.00 0.00 134.00 188.00\" xmlns=\"http://www.w3.org/2000/svg\" xmlns:xlink=\"http://www.w3.org/1999/xlink\">\n",
       "<g id=\"graph0\" class=\"graph\" transform=\"scale(1 1) rotate(0) translate(4 184)\">\n",
       "<title>hgn</title>\n",
       "<polygon fill=\"white\" stroke=\"none\" points=\"-4,4 -4,-184 130,-184 130,4 -4,4\"/>\n",
       "<!-- 1 -->\n",
       "<g id=\"node1\" class=\"node\"><title>1</title>\n",
       "<ellipse fill=\"none\" stroke=\"black\" cx=\"18\" cy=\"-162\" rx=\"18\" ry=\"18\"/>\n",
       "<text text-anchor=\"middle\" x=\"18\" y=\"-158.3\" font-family=\"Times,serif\" font-size=\"14.00\">1</text>\n",
       "</g>\n",
       "<!-- 1&#45;&gt;1 -->\n",
       "<g id=\"edge1\" class=\"edge\"><title>1&#45;&gt;1</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M32.0417,-173.756C42.9126,-178.153 54,-174.234 54,-162 54,-153.589 48.7595,-149.108 41.9516,-148.558\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"41.3132,-145.116 32.0417,-150.244 42.4871,-152.017 41.3132,-145.116\"/>\n",
       "</g>\n",
       "<!-- 3 -->\n",
       "<g id=\"node3\" class=\"node\"><title>3</title>\n",
       "<ellipse fill=\"none\" stroke=\"black\" cx=\"18\" cy=\"-90\" rx=\"18\" ry=\"18\"/>\n",
       "<text text-anchor=\"middle\" x=\"18\" y=\"-86.3\" font-family=\"Times,serif\" font-size=\"14.00\">3</text>\n",
       "</g>\n",
       "<!-- 1&#45;&gt;3 -->\n",
       "<g id=\"edge2\" class=\"edge\"><title>1&#45;&gt;3</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M18,-143.697C18,-135.983 18,-126.712 18,-118.112\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"21.5001,-118.104 18,-108.104 14.5001,-118.104 21.5001,-118.104\"/>\n",
       "</g>\n",
       "<!-- 2 -->\n",
       "<g id=\"node2\" class=\"node\"><title>2</title>\n",
       "<ellipse fill=\"none\" stroke=\"black\" cx=\"90\" cy=\"-90\" rx=\"18\" ry=\"18\"/>\n",
       "<text text-anchor=\"middle\" x=\"90\" y=\"-86.3\" font-family=\"Times,serif\" font-size=\"14.00\">2</text>\n",
       "</g>\n",
       "<!-- 2&#45;&gt;2 -->\n",
       "<g id=\"edge4\" class=\"edge\"><title>2&#45;&gt;2</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M104.042,-101.756C114.913,-106.153 126,-102.234 126,-90 126,-81.5889 120.759,-77.1081 113.952,-76.5578\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"113.313,-73.116 104.042,-78.2435 114.487,-80.0169 113.313,-73.116\"/>\n",
       "</g>\n",
       "<!-- 4 -->\n",
       "<g id=\"node4\" class=\"node\"><title>4</title>\n",
       "<ellipse fill=\"none\" stroke=\"black\" cx=\"54\" cy=\"-18\" rx=\"18\" ry=\"18\"/>\n",
       "<text text-anchor=\"middle\" x=\"54\" y=\"-14.3\" font-family=\"Times,serif\" font-size=\"14.00\">4</text>\n",
       "</g>\n",
       "<!-- 2&#45;&gt;4 -->\n",
       "<g id=\"edge3\" class=\"edge\"><title>2&#45;&gt;4</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M82.0104,-73.4647C77.4895,-64.674 71.7331,-53.4811 66.6161,-43.5314\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"69.6533,-41.784 61.9672,-34.4918 63.4283,-44.9855 69.6533,-41.784\"/>\n",
       "</g>\n",
       "<!-- 3&#45;&gt;3 -->\n",
       "<g id=\"edge6\" class=\"edge\"><title>3&#45;&gt;3</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M32.0417,-101.756C42.9126,-106.153 54,-102.234 54,-90 54,-81.5889 48.7595,-77.1081 41.9516,-76.5578\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"41.3132,-73.116 32.0417,-78.2435 42.4871,-80.0169 41.3132,-73.116\"/>\n",
       "</g>\n",
       "<!-- 3&#45;&gt;4 -->\n",
       "<g id=\"edge5\" class=\"edge\"><title>3&#45;&gt;4</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M25.9896,-73.4647C30.5105,-64.674 36.2669,-53.4811 41.3839,-43.5314\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"44.5717,-44.9855 46.0328,-34.4918 38.3467,-41.784 44.5717,-44.9855\"/>\n",
       "</g>\n",
       "<!-- 4&#45;&gt;4 -->\n",
       "<g id=\"edge7\" class=\"edge\"><title>4&#45;&gt;4</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M71.0373,-24.3792C80.8579,-25.6811 90,-23.5547 90,-18 90,-14.5283 86.4289,-12.3958 81.3529,-11.6025\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"81.031,-8.10295 71.0373,-11.6208 81.0435,-15.1029 81.031,-8.10295\"/>\n",
       "</g>\n",
       "<!-- 4&#45;&gt;4 -->\n",
       "<g id=\"edge8\" class=\"edge\"><title>4&#45;&gt;4</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M69.2026,-27.8012C87.1122,-34.978 108,-31.7109 108,-18 108,-6.75275 93.9444,-2.53331 79.007,-5.34169\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"77.824,-2.04077 69.2026,-8.19882 79.7825,-8.76123 77.824,-2.04077\"/>\n",
       "</g>\n",
       "</g>\n",
       "</svg>\n"
      ]
     },
     "metadata": {
      "image/svg+xml": {
       "height": 500,
       "width": 500
      }
     },
     "output_type": "display_data"
    },
    {
     "name": "stdout",
     "output_type": "stream",
     "text": []
    }
   ],
   "source": [
    "JUPYTER_DotSplash(DotDigraph(gr));"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Testing commutativity\n",
    "\n",
    "Commutativity is a nice simple property to check for.\n",
    "\n",
    "A semigroup is commutative if x * y = y * x for all x, y."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "collapsed": true
   },
   "source": [
    "## Version 1\n",
    "Check all elements for commutativity, as per the definition."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 72,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "<object>"
     ]
    }
   ],
   "source": [
    "is_commutative_1 := function(S)\n",
    "  local x, y;\n",
    "\n",
    "  for x in S do\n",
    "    for y in S do\n",
    "      if not x * y = y * x then\n",
    "        return false;\n",
    "      fi;\n",
    "    od;\n",
    "  od;\n",
    "  return true;\n",
    "end;"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 73,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "<full transformation monoid of degree 4>"
     ]
    }
   ],
   "source": [
    "S := FullTransformationSemigroup(4);;"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 74,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "false"
     ]
    }
   ],
   "source": [
    "is_commutative_1(S);"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 75,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "false"
     ]
    }
   ],
   "source": [
    "IsCommutative(S);"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 76,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "<partial perm semigroup of rank 9 with 9 generators>"
     ]
    }
   ],
   "source": [
    "S := Semigroup([\n",
    "  PartialPerm([1, 2, 3, 4, 5, 6, 8, 9], [1, 2, 3, 4, 5, 6, 8, 9]), \n",
    "  PartialPerm([1, 3, 4, 5, 6, 7, 8, 9], [1, 3, 4, 5, 6, 7, 8, 9]), \n",
    "  PartialPerm([1, 2, 4, 5, 6, 7, 8, 9], [1, 2, 4, 5, 6, 7, 8, 9]), \n",
    "  PartialPerm([1, 2, 3, 4, 6, 7, 8, 9], [1, 2, 3, 4, 6, 7, 8, 9]), \n",
    "  PartialPerm([1, 2, 3, 4, 5, 6, 7, 8], [1, 2, 3, 4, 5, 6, 7, 8]), \n",
    "  PartialPerm([1, 2, 3, 4, 5, 7, 8, 9], [1, 2, 3, 4, 5, 7, 8, 9]), \n",
    "  PartialPerm([1, 2, 3, 4, 5, 6, 7, 9], [1, 2, 3, 4, 5, 6, 7, 9]), \n",
    "  PartialPerm([2, 3, 4, 5, 6, 7, 8, 9], [2, 3, 4, 5, 6, 7, 8, 9]), \n",
    "  PartialPerm([1, 2, 3, 5, 6, 7, 8, 9], [1, 2, 3, 5, 6, 7, 8, 9])]);"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 77,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "true"
     ]
    }
   ],
   "source": [
    "is_commutative_1(S)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 78,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "15272"
     ]
    }
   ],
   "source": [
    "time;"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 79,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "true"
     ]
    }
   ],
   "source": [
    "IsCommutative(S);"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 80,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "0"
     ]
    }
   ],
   "source": [
    "time;"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Version 2\n",
    "Check all generators"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 81,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "<object>"
     ]
    }
   ],
   "source": [
    "is_commutative_2 := function(S)\n",
    "  local gens, x, y;\n",
    "\n",
    "  gens := GeneratorsOfSemigroup(S);\n",
    "  for x in gens do\n",
    "    for y in gens do\n",
    "      if not x * y = y * x then\n",
    "        return false;\n",
    "      fi;\n",
    "    od;\n",
    "  od;\n",
    "  return true;\n",
    "end;"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 82,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "true"
     ]
    }
   ],
   "source": [
    "is_commutative_2(S);"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 83,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "0"
     ]
    }
   ],
   "source": [
    "time;"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### What is the problem with this function?"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Version 3\n",
    "Don't repeat work!"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 84,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "<object>"
     ]
    }
   ],
   "source": [
    "is_commutative_3 := function(S)\n",
    "  local pair;\n",
    "\n",
    "  for pair in Combinations(GeneratorsOfSemigroup(S), 2) do\n",
    "    if not pair[1] * pair[2] = pair[2] * pair[1] then\n",
    "      return false;\n",
    "    fi;\n",
    "  od;\n",
    "  return true;\n",
    "end;"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 85,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "true"
     ]
    }
   ],
   "source": [
    "is_commutative_3(S);"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Task for the keen: re-implement the above algorithm using `IteratorOfCombinations`."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Counting idempotents\n",
    "\n",
    "An idempotent is an element where x ^ 2 = x"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Version 1\n",
    "Check every element for idempotency."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 86,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "<object>"
     ]
    }
   ],
   "source": [
    "nr_idempotents_1 := S -> Number(S, IsIdempotent);"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 87,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "<symmetric inverse monoid of degree 7>"
     ]
    }
   ],
   "source": [
    "S := SymmetricInverseSemigroup(7);"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 88,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "128"
     ]
    }
   ],
   "source": [
    "nr_idempotents_1(S);"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 89,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "1788"
     ]
    }
   ],
   "source": [
    "time;"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 90,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "128"
     ]
    }
   ],
   "source": [
    "NrIdempotents(S);"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 91,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "4"
     ]
    }
   ],
   "source": [
    "time;"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Version 2\n",
    "In any semigroup, the number of idempotents is the number of maximal subgroups."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 92,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "<object>"
     ]
    }
   ],
   "source": [
    "nr_idempotents_2 := S -> Number(GreensHClasses(S), IsGroupHClass);"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 93,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "<symmetric inverse monoid of degree 7>"
     ]
    }
   ],
   "source": [
    "S := SymmetricInverseSemigroup(7);"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 94,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "128"
     ]
    }
   ],
   "source": [
    "nr_idempotents_2(S);"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 95,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "88"
     ]
    }
   ],
   "source": [
    "time;"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Version 3: inverse semigroups\n",
    "In an inverse semigroup, `NrIdempotents` = `NrRClasses`."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 96,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "<Attribute \"NrRClasses\">"
     ]
    }
   ],
   "source": [
    "nr_idempotents_inverse := NrRClasses;"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 97,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "<symmetric inverse monoid of degree 7>"
     ]
    }
   ],
   "source": [
    "S := SymmetricInverseSemigroup(7);"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 98,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "128"
     ]
    }
   ],
   "source": [
    "nr_idempotents_inverse(S);"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 99,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "4"
     ]
    }
   ],
   "source": [
    "time;"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Version 4: bands\n",
    "In a band, every element is idempotent. So `NrIdempotents` = `Size`."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 100,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "<Attribute \"Size\">"
     ]
    }
   ],
   "source": [
    "nr_idempotents_band := Size;"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 101,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "<semigroup with 4 generators>"
     ]
    }
   ],
   "source": [
    "S := FreeBand(4);"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 102,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "332380"
     ]
    }
   ],
   "source": [
    "nr_idempotents_band(S);"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 103,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "0"
     ]
    }
   ],
   "source": [
    "time;"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 104,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "<semigroup with 4 generators>"
     ]
    }
   ],
   "source": [
    "S := FreeBand(4);"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 105,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "332380"
     ]
    }
   ],
   "source": [
    "NrIdempotents(S);"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 106,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "73728"
     ]
    }
   ],
   "source": [
    "time;"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 107,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": []
    }
   ],
   "source": [
    "InstallMethod(NrIdempotents, \"for a band\", [IsBand], Size);"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 108,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "<semigroup with 4 generators>"
     ]
    }
   ],
   "source": [
    "S := FreeBand(4);"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 109,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": []
    }
   ],
   "source": [
    "SetIsBand(S, true);"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 110,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "332380"
     ]
    }
   ],
   "source": [
    "NrIdempotents(S);"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 111,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "0"
     ]
    }
   ],
   "source": [
    "time;"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "GAP",
   "language": "gap",
   "name": "gap"
  },
  "language_info": {
   "codemirror_mode": "gap",
   "file_extension": ".g",
   "mimetype": "text/x-gap",
   "name": "gap"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 0
}