Semigroups in GAP¶

Website: cloud.gap-system.org

The Semigroups package¶

The semigroups package needs to be loaded for the current worksheet.

LoadPackage("semigroups");

true

Transformations¶

Transformations are to semigroups as permutations are to groups.

Mathematically, permutations are transformations, but in GAP they are not.

f := Transformation([4, 1, 1, 5, 3, 3]);

Transformation( [ 4, 1, 1, 5, 3, 3 ] )

g := Transformation([4, 5, 1, 2, 1, 4]);

Transformation( [ 4, 5, 1, 2, 1, 4 ] )

f * g;

Transformation( [ 2, 4, 4, 1, 1, 1 ] )

f * g = g * f;

false

x := RandomTransformation(10);

Transformation( [ 8, 8, 2, 3, 5, 5, 8, 4, 1, 8 ] )

y := RandomTransformation(10);

Transformation( [ 1, 9, 7, 5, 3, 3, 7, 7, 5, 4 ] )

z := RandomTransformation(10);

Transformation( [ 7, 9, 4, 5, 1, 10, 7, 1, 8, 5 ] )

x * y = y * x; # commutativity

false

z * z = z; # idempotent?

false

Composition of functions is associative...

(x * y) * z = x * (y * z); # associativity

true

... and so you can make semigroups out of transformations

S := Semigroup(x, y, z);

<transformation semigroup of degree 10 with 3 generators>

Size(S);

16831

t := Transformation([2, 3, 1]);

Transformation( [ 2, 3, 1 ] )

p := AsPermutation(t);

(1,2,3)

p = t;

false

AsPermutation(f);

fail

t * p;

Transformation( [ 3, 1, 2 ] )

Permutations and transformations can be multiplied together, but you cannot create a semigroup with both elements.

Semigroup(t, p);

Error, Usage: Semigroup(<gen>,...), Semigroup(<gens>), Semigroup(<D>),

IsGroup vs IsMonoid vs IsSemigroup¶

Something created as a semigroup may not satisfy IsGroup even if it is mathematically a group. We use IsGroupAsSemigroup to check for this.

There are similar problems with IsMonoid. This the analogous property is IsMonoidAsSemigroup.

M := [ [ Z(5), Z(5)^2 ], [ Z(5)^3, Z(5)^2 ] ];

[ [ Z(5), Z(5)^2 ], [ Z(5)^3, Z(5)^2 ] ]

M in GL(2, 5);

true

A group is also a monoid and a semigroup.

G := Group(M);

<group with 1 generators>

IsSemigroup(G);

true

IsMonoid(G);

true

IsGroup(G);

true

A semigroup is not (usually) a monoid or a group in GAP -- even if it is mathematically.

The category depends on how the object was created.

S := Semigroup(M);

<commutative semigroup with 1 generator>

IsSemigroup(S);

true

IsMonoid(S);

false

IsMonoidAsSemigroup(S);

true

IsGroup(S);

false

IsGroupAsSemigroup(S);

true

G = S;

true

For an object in IsGroup, GAP needs to know that it can invert any element independently, and it needs how to do it.

For a permutation, there is only ever one inverse, and it is easy to calculate.

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...

IsGroup(FullTransformationSemigroup(1));

true

Multiplication tables¶

A := [
  [1, 2, 3, 4],
  [2, 1, 3, 4],
  [3, 4, 3, 4],
  [4, 3, 3, 4]
];

[ [ 1, 2, 3, 4 ], [ 2, 1, 3, 4 ], [ 3, 4, 3, 4 ], [ 4, 3, 3, 4 ] ]

S := SemigroupByMultiplicationTable(A);

<semigroup of size 4, with 4 generators>

T := FullTransformationSemigroup(2);

<full transformation monoid of degree 2>

IsIsomorphicSemigroup(S, T);

true

Creating standard examples¶

S := FullTransformationSemigroup(10);

<full transformation monoid of degree 10>

x := PseudoRandom(S);

Transformation( [ 2, 3, 4, 5, 6, 7, 8, 9, 1, 1 ] )

I := SymmetricInverseSemigroup(8);

<symmetric inverse monoid of degree 8>

x := PseudoRandom(I);

[3,5,7](2,4,6,8)

Print(x);

PartialPerm( [ 2, 3, 4, 5, 6, 8 ], [ 4, 5, 6, 7, 8, 2 ] )

P := PartitionMonoid(4);

<regular bipartition monoid of degree 4 with 4 generators>

x := PseudoRandom(P);

<bipartition: [ 1, 2, -1, -2, -3 ], [ 3, -4 ], [ 4 ]>

Print(x);

Bipartition( [ [ 1, 2, -1, -2, -3 ], [ 3, -4 ], [ 4 ] ] )

M := FullMatrixSemigroup(2, 5);

<regular monoid of size 625, with 3 generators>

x := PseudoRandom(GroupOfUnits(M));

<matrix over GF(5) of degree 2>

Print(x);

NewMatrixOverFiniteField(IsPlistMatrixOverFiniteFieldRep, GF(5), 2, [ [ Z(5)^3, Z(5) ], [ Z(5)^2, 0*Z(5) ] ])

AsMatrix(x) in GL(2, 5);

true

IsSubsemigroup(M, GL(2, 5));

false

x := Random(GL(2, 5));

[ [ Z(5)^3, Z(5)^0 ], [ 0*Z(5), Z(5) ] ]

NewMatrixOverFiniteField(IsPlistMatrixOverFiniteFieldRep, GF(5), 2, x) in M;

true

Finitely presented semigroups¶

F := FreeSemigroup("x", "y");

<infinite semigroup with 2 generators>

IsFinite(F);

false

x := F.1;

<object>

y := F.2;

<object>

Relation 1: x * y = y * x

rel1 := [ x * y, y * x ];

[ x*y, y*x ]

Relation 2: x ^ 3 = x ^ 2

rel2 := [ x ^ 3, x ^ 2 ];

[ x^3, x^2 ]

Relation 3: y ^ 2 = y

rel3 := [y ^ 2, y ];

[ y^2, y ]

S := F / [rel1, rel2, rel3];

<semigroup with 2 generators>

Size(S);

5

Elements(S);

[ x, y, x^2, x*y, x^2*y ]

T := F / [rel2, rel3];

<semigroup with 2 generators>

# IsFinite(T);

Exhaustive enumeration¶

enumerate_semigroup := function(gens)
  local elts, x, g;

  elts := ShallowCopy(gens);
  for x in elts do
    for g in gens do
      if not x * g in elts then
        Add(elts, x * g);
      fi;
    od;
  od;
  return elts;
end;

<object>

Length(enumerate_semigroup([f, g]));

665

Size(Semigroup(f, g));

665

Create the right Cayley graph during enumeration...¶

LoadPackage("digraphs");

true

enumerate_with_graph := function(gens)
  local elts, graph, adjacencies, pos, x, g, prod;

  elts := ShallowCopy(gens);
  graph := [];
  for x in elts do
    adjacencies := [];
    for g in gens do
      prod := x * g;
      pos := Position(elts, prod);
      if pos = fail then
        Add(elts, prod);
        Add(adjacencies, Length(elts));
      else
        Add(adjacencies, pos);
      fi;
    od;
    Add(graph, adjacencies);
  od;
  return Digraph(graph);
end;

<object>

gr := enumerate_with_graph([Transformation([1, 1, 3]), Transformation([1, 2, 2])]);

<multidigraph with 4 vertices, 8 edges>

JUPYTER_DotSplash(DotDigraph(gr));

Testing commutativity¶

Commutativity is a nice simple property to check for.

A semigroup is commutative if x y = y x for all x, y.

Version 1¶

Check all elements for commutativity, as per the definition.

is_commutative_1 := function(S)
  local x, y;

  for x in S do
    for y in S do
      if not x * y = y * x then
        return false;
      fi;
    od;
  od;
  return true;
end;

<object>

S := FullTransformationSemigroup(4);;

<full transformation monoid of degree 4>

is_commutative_1(S);

false

IsCommutative(S);

false

S := Semigroup([
  PartialPerm([1, 2, 3, 4, 5, 6, 8, 9], [1, 2, 3, 4, 5, 6, 8, 9]), 
  PartialPerm([1, 3, 4, 5, 6, 7, 8, 9], [1, 3, 4, 5, 6, 7, 8, 9]), 
  PartialPerm([1, 2, 4, 5, 6, 7, 8, 9], [1, 2, 4, 5, 6, 7, 8, 9]), 
  PartialPerm([1, 2, 3, 4, 6, 7, 8, 9], [1, 2, 3, 4, 6, 7, 8, 9]), 
  PartialPerm([1, 2, 3, 4, 5, 6, 7, 8], [1, 2, 3, 4, 5, 6, 7, 8]), 
  PartialPerm([1, 2, 3, 4, 5, 7, 8, 9], [1, 2, 3, 4, 5, 7, 8, 9]), 
  PartialPerm([1, 2, 3, 4, 5, 6, 7, 9], [1, 2, 3, 4, 5, 6, 7, 9]), 
  PartialPerm([2, 3, 4, 5, 6, 7, 8, 9], [2, 3, 4, 5, 6, 7, 8, 9]), 
  PartialPerm([1, 2, 3, 5, 6, 7, 8, 9], [1, 2, 3, 5, 6, 7, 8, 9])]);

<partial perm semigroup of rank 9 with 9 generators>

is_commutative_1(S)

true

time;

16312

IsCommutative(S);

true

time;

0

Version 2¶

Check all generators

is_commutative_2 := function(S)
  local gens, x, y;

  gens := GeneratorsOfSemigroup(S);
  for x in gens do
    for y in gens do
      if not x * y = y * x then
        return false;
      fi;
    od;
  od;
  return true;
end;

<object>

is_commutative_2(S);

true

time;

0

What is the problem with this function?¶

Version 3¶

Don't repeat work!

is_commutative_3 := function(S)
  local pair;

  for pair in Combinations(GeneratorsOfSemigroup(S), 2) do
    if not pair[1] * pair[2] = pair[2] * pair[1] then
      return false;
    fi;
  od;
  return true;
end;

<object>

is_commutative_3(S);

true

Task for the keen: re-implement the above algorithm using `IteratorOfCombinations`.¶

Counting idempotents¶

An idempotent is an element where x ^ 2 = x

Version 1¶

Check every element for idempotency.

nr_idempotents_1 := S -> Number(S, IsIdempotent);

<object>

S := SymmetricInverseSemigroup(7);

<symmetric inverse monoid of degree 7>

nr_idempotents_1(S);

128

time;

1912

NrIdempotents(S);

128

time;

4

Version 2¶

In any semigroup, the number of idempotents is the number of maximal subgroups.

nr_idempotents_2 := S -> Number(GreensHClasses(S), IsGroupHClass);

<object>

S := SymmetricInverseSemigroup(7);

<symmetric inverse monoid of degree 7>

nr_idempotents_2(S);

128

time;

88

Version 3: inverse semigroups¶

In an inverse semigroup, NrIdempotents = NrRClasses.

nr_idempotents_inverse := NrRClasses;

<Attribute "NrRClasses">

S := SymmetricInverseSemigroup(7);

<symmetric inverse monoid of degree 7>

nr_idempotents_inverse(S);

128

time;

0

Version 4: bands¶

In a band, every element is idempotent. So NrIdempotents = Size.

nr_idempotents_band := Size;

<Attribute "Size">

S := FreeBand(4);

<semigroup with 4 generators>

nr_idempotents_band(S);

332380

time;

0

S := FreeBand(4);

<semigroup with 4 generators>

NrIdempotents(S);

332380

time;

80336

InstallMethod(NrIdempotents, "for a band", [IsBand], Size);

S := FreeBand(4);

<semigroup with 4 generators>

SetIsBand(S, true);

NrIdempotents(S);

332380

time;

0

Semigroups in GAP¶

The Semigroups package¶

Transformations¶

IsGroup vs IsMonoid vs IsSemigroup¶

Multiplication tables¶

Creating standard examples¶

Finitely presented semigroups¶

Exhaustive enumeration¶

Create the right Cayley graph during enumeration...¶

Testing commutativity¶

Version 1¶

Version 2¶

What is the problem with this function?¶

Version 3¶

Task for the keen: re-implement the above algorithm using IteratorOfCombinations.¶

Counting idempotents¶

Version 1¶

Version 2¶

Version 3: inverse semigroups¶

Version 4: bands¶

Task for the keen: re-implement the above algorithm using `IteratorOfCombinations`.¶