The main features of the library can be summarized in three points: it provides a complete set of semigroups up to isomorphism and anti-isomorphism of sizes up to 8; it carries a vast amount of precomputed information about these semigroups; and there is an identification function which takes a semigroup with at most 8 elements and returns a map to the equivalent one from the library.
These features lead to different ways of using the library. It is impossible to describe - or even to anticipate - all possible types of usage. Most problems will admit multiple solutions. We find it difficult to predict which will be most effective. The examples in this chapter should give an idea of the differences in the various functions and help you to find an alternative if a computation uses more time or memory than you have available.
Let us go step by step through some ways to use the library showing which tools are provided.
At first one could want to search through the stored semigroups for one or all semigroups with a certain property. Going through all the semigroups can take a long time. Just to create all the 1.8 billion semigroups as objects in GAP takes around a day on a modern PC. Doing a simple test on all the semigroups in the library might take another day. Performing complicated tests easily takes weeks. To avoid this, many properties of the semigroups were precomputed. Semigroups with or without a precomputed property can be accessed as quickly as simply creating the same number of semigroups. (Note that timings of two calls to the same command may vary and, of course, heavily depend on your machine.)
gap> # obtain a list of all semigroups with 6 elements gap> AllSmallSemigroups(6);; gap> time; 2636 gap> # obtain a list of all commutative semigroups with 7 elements gap> AllSmallSemigroups(7, IsCommutative, true);; gap> time; 2957 gap> # compare the numbers of semigroups in the two lists gap> NrSmallSemigroups(6); NrSmallSemigroups(7, IsCommutative, true); 15973 17291
(In all the examples in this section the info messages which are given by default when data is loaded are turned off via SetInfoLevel(InfoSmallSemi,0).)
We provide three commands that can be used if one is interested in all semigroups with some properties. These are AllSmallSemigroups (4.5-1), EnumeratorOfSmallSemigroups (4.5-2), and IteratorOfSmallSemigroups (4.5-9). Which one is best to use depends a lot on the situation. Here we attempt to provide some insight about the essential differences.
We start with examples using only precomputed information. In this case there is essentially no advantage of calling an iterator instead of an enumerator. Thus only AllSmallSemigroups (4.5-1) and EnumeratorOfSmallSemigroups (4.5-2) will be considered.
We first compare the memory usage and the setup time. Assume we are interested in the commutative semigroups with at most 7 elements.
gap> list := AllSmallSemigroups([1 .. 7], IsCommutativeSemigroup, true);; gap> time; # the time needed will always depend on your machine 3180 gap> enum := EnumeratorOfSmallSemigroups([1 .. 7], IsCommutativeSemigroup, true); <enumerator of semigroups of sizes [ 1 .. 7 ]> gap> time; 8
The enumerator stores the information, which semigroups it contains, but only creates the semigroups when asked for them explicitly.
gap> # now the semigroups have to be created ... gap> for sg in enum do > # do nothing, the semigroup will be created anyway > od; gap> time; 3428 gap> # ... and again if you want to look through them another time ... gap> for sg in enum do od; gap> time; 3437 gap> # ... not so for the list of semigroups though gap> for sg in list do od; gap> time; 4
There are several reasons why one would nevertheless prefer an enumerator, one is the smaller need for memory. While the number of semigroups in this example is rather moderate (compared with all the semigroups in the library) the difference is remarkable:
gap> nr := Length(enum); 17291 gap> MemoryUsage(enum); 70507 gap> MemoryUsage(list); # this will take a while .. . 19089280 gap> # ... but you can get a close approximation much faster gap> sg := OneSmallSemigroup(7, IsCommutativeSemigroup, true); <small semigroup of size 7> gap> nr * MemoryUsage(sg); 19020100
As said before the advantage of the enumerator comes from the fact that the members of it are created anew every time they are called. This means on the other hand that information that is computed is not stored.
gap> IsZeroSemigroup(list[3]); # a semigroup from the list .. . false gap> KnownPropertiesOfObject(list[3]); # .. . can store new information [ "IsEmpty", "IsTrivial", "IsNonTrivial", "IsFinite", "IsDuplicateFree", "IsAssociative", "IsCommutativeSemigroup", "IsZeroSemigroup" ] gap> IsZeroSemigroup(enum[3]); # semigroups in the enumerator .. . false gap> KnownPropertiesOfObject(enum[3]); # .. . are created anew in every call [ "IsEmpty", "IsTrivial", "IsNonTrivial", "IsFinite", "IsDuplicateFree", "IsAssociative", "IsCommutativeSemigroup" ] gap> # but if it turns out this is the semigroup you want to analyse, just do gap> sg := enum[3];
Observe that in the last example the semigroup from the enumerator knew about the property that was used to create the enumerator. The enumerator stores this knowledge and passes it on whenever a member is called.
Another reason to prefer an enumerator is that one might only be interested in some of the elements it contains. This could become clear after analysing some of the elements and then there is no time wasted in creating all semigroups in the enumerator. Or possibly creating the enumerator involving precomputed properties was just the first step. As described in Section 4.5 enumerators themselves can be given as argument to get to a more restricted class of semigroups. This leads us to the next part of this section.
We now come to examples dealing with properties that are not precomputed - including user defined functions. This makes IteratorOfSmallSemigroups (4.5-9) interesting again. Assume you want to work with bands (IsBand (4.2-5)) of order 8 having 1 Green's \(D\)-class (see Reference: Green's Relations). You might feel tempted to implement a function testing a semigroup for this combination of properties.
gap> isFascinatingSemigroup := function(sgrp) local dclasses; dclasses := GreensDClasses(sgrp); return IsBand(sgrp) and Length(dclasses) = 1; end;
But then the precomputed property IsBand (4.2-5) is hidden inside your function and a call like AllSmallSemigroups(8,isFascinatingSemigroup,true) would take days to complete.
The following finds the same semigroups more efficiently:
gap> list := AllSmallSemigroups(8, IsBand, true, > x -> Size(GreensDClasses(x)), 1); [ <small semigroup of size 8>, <small semigroup of size 8> ] gap> time; 49211 gap> enum := EnumeratorOfSmallSemigroups(8, IsBand, true, > x -> Size(GreensDClasses(x)), 1); <enumerator of semigroups of size 8> gap> time; 48723
Observe that the enumerator lost its advantage of returning the answer faster because not all properties are precomputed. Thus all bands have to be constructed to test their number of \(D\)-classes. As the number of such semigroups is small, AllSmallSemigroups (4.5-1) is the better choice in this example - remember that the semigroups from the enumerator have to be recreated in every call. Often one does not have this kind of knowledge beforehand. Even for a large number of semigroups the enumerator still has the advantage of using far less memory as it stores only the IDs of the semigroups. Before explaining more about this let us for a moment go back to the semigroups from the previous example. It turns out they are the 2 non-equivalent rectangular bands (IsRectangularBand (4.2-22)) with 8 elements.
gap> ForAll(list, IsRectangularBand); true
As a last example in this subsection we look at semigroups from the library that are not nilpotent. As there are quite some of these we will first try an enumerator. The obvious call seems to be
gap> enum1 := EnumeratorOfSmallSemigroups([1 .. 7], IsNilpotentSemigroup, false); <enumerator of semigroups of sizes [ 2, 3, 4, 5, 6, 7 ]> gap> time; 103403
However, we would like to include the semigroups of order 8 as well. As IsNilpotentSemigroup (4.2-20) is not a precomputed property in the current version of Smallsemi this would take a long time. Here, additional knowledge, about the way the semigroups are stored in the library, is helpful. The description of NilpotencyDegree (4.2-34) contains information on the IDs of all 3-nilpotent semigroups of order 8. We can create an enumerator without those semigroups doing the following:
gap> # all 8 element semigroups that are not 3-nilpotent gap> enum2 := EnumeratorOfSmallSemigroupsByIds([8], [[1 .. 11433106]]); <enumerator of semigroups of size 8>
Out of this enumerator the subclass of not nilpotent semigroups can be extracted.
gap> enum3 := EnumeratorOfSmallSemigroups(enum2, IsNilpotentSemigroup, false); gap> # This still takes quite a while though gap> time; 1931140
You can avoid the waiting time at setup by using an iterator instead of an enumerator. An iterator does not know how many elements it contains, one can always just access the next element - if such exists - and one cannot go back. (Making copies of an iterator can help to circumvent this problem.) On the other hand one could in the above example start investigating the first couple of elements right away.
gap> iter := IteratorOfSmallSemigroups(enum2, IsNilpotentSemigroup, false); gap> for i in [1 .. 100000] do > NextIterator(iter); > od; gap> time; 30785
But even if you know you want to inspect all the semigroups having a property which is not precomputed, an iterator has the advantage that it does not create the semigroups before you can actually work with them. To create an enumerator all semigroups in question will be created and - as said before - every element is created anew when it is accessed. An iterator on the other hand creates the semigroups in question one-by-one and returns the next one having the property. This makes a big difference if the number of semigroups one is interested in is big like in the example of not nilpotent semigroups of size 8. In the former example with the rectangular bands it would not play a role and the disadvantages of an iterator would prevail.
As you can see the number of semigroups you are interested in is even more important in the case of user defined functions than it was in the previous section about precomputed properties. Sometimes you might have a rough idea about the numbers - or even a very good one - to base your choice on. Otherwise the best approach seems to consist of two steps. First, create an enumerator involving all precomputed properties (try to find as many implied properties as possible). Then work with an iterator, call the semigroups one-by-one and store them in a separate list if you think you might want to look at them again at a later stage.
When using enumerators and iterators of semigroups of order 8 there are some limitations. In a 32-bit system the number of semigroups of order 8 exceeds the maximal length of a list in GAP. The following will work in a 64-bit system, but not on a 32-bit system.
gap> EnumeratorOfSmallSemigroups(8);
In all other cases there is currently no difference between 32-bit and 64-bit systems. Hence the following will fail in any case.
gap> EnumeratorOfSmallSemigroups(8, IsCommutativeSemigroup, false);
Note though that an enumerator of semigroups of order 8 can be created if one of the required properties is precomputed and takes true as value. This fact was used in the previous subsection, when creating the enumerator of all bands of order 8 having 1 Green's \(D\)-class.
One could try to circumvent the described problem by using a iterator. The command
gap> iter := IteratorOfSmallSemigroups(8, IsCommutativeSemigroup, false); <iterator of semigroups of size 8>
will succeed. But running through the elements in the iterator can take a long time since the precomputed information is not utilized. A better idea in the current version of Smallsemi is to divide the enumerator into smaller pieces by restricting the range of IDs considered at once to at most \(2^{28}-1\) (the maximal length of a list in a 32-bit GAP) or possibly by a smaller value, depending on the amount of memory you have available. For example start with
gap> enum1 := EnumeratorOfSmallSemigroupsByIds([8], [[1 .. 2 ^ 24 - 1]]); <enumerator of semigroups of size 8> gap> enum2 := EnumeratorOfSmallSemigroups(enum1, IsCommutativeSemigroup, false); <enumerator of semigroups of size 8>
Thanks go to Michal Stolorz for the idea of circumventing the current performance issue for enumerators of small semigroups of order 8 by splitting it in the described way.
The data in Smallsemi is as a big catalogue of all structural types of semigroups with at most 8 elements making it possible to refer to the types by their catalogue number, that is by their ID. With IdSmallSemigroup (4.1-6) one can find the ID of the structural type of a particular semigroup with at most 8 elements.
gap> t1 := RandomTransformation(3); Transformation( [ 1, 3, 1 ] ) gap> t2 := RandomTransformation(3); Transformation( [ 1, 2, 3 ] ) gap> sgrp := SemigroupByGenerators([t1, t2]); <semigroup with 2 generators> gap> Size(sgrp); 3 gap> IdSmallSemigroup(sgrp); [ 3, 8 ]
Moreover, one can draw conclusions about a semigroup of size at most 8 using the precomputed information about the equivalent semigroup from the library. The precomputed properties are all invariant under isomorphism and anti-isomorphism. This is most useful in the case where there is no method in GAP to decide the property in the original representation of the semigroup.
gap> # use the semigroup from the previous example gap> IsCommutative(sgrp); # no need to use the library for this true gap> # for the following there exists no method for a trans- gap> # formation semigroup; access the precomputed information instead gap> IsMultSemigroupOfNearRing(SmallSemigroup([3, 8])); false
EquivalenceSmallSemigroup (4.1-7) even provides an isomorphism or anti-isomorphism to a semigroup from the library. This means one can map elements between the semigroups. Remember that an isomorphism is returned whenever one exists. This allows to distinguish between structure types up to isomorphism. Note though, that no information about subsets - like the set of idempotents or a generating set - is precomputed for semigroups in the library. If an operation has a method for the semigroup in the original representation, it is usually more sensible to simply call this.
gap> t1 := RandomTransformation(3); Transformation( [ 2, 2, 1 ] ) gap> t2 := RandomTransformation(3); Transformation( [ 2, 1, 1 ] ) gap> sgrp := Semigroup(t1, t2); <semigroup with 2 generators> gap> Size(sgrp); 6 gap> map := EquivalenceSmallSemigroup(sgrp); MappingByFunction( <semigroup with 2 generators>, <small semigroup of size 6>, function( x ) ... end ) gap> RespectsMultiplication(map); # verify that this is an anti-isomorphism false gap> MinimalGeneratingSet(Range(map)); [ s2, s4 ] gap> PreImage(map, last); # get a minimal generating set of < sgrp > [ Transformation( [ 1, 1, 2 ] ), Transformation( [ 2, 1, 1 ] ) ] gap> Idempotents(Range(map)); [ s1, s3, s5 ] gap> PreImage(map, last); # in the same way you can get the idempotents .. . [ Transformation( [ 1, 1, 1 ] ), Transformation( [ 1, 2, 2 ] ), Transformation( [ 2, 2, 2 ] ) ] gap> Idempotents(sgrp); # ... but this can be done directly instead [ Transformation( [ 1, 1, 1 ] ), Transformation( [ 1, 2, 2 ] ), Transformation( [ 2, 2, 2 ] ) ]
If for a certain application you are interested in the semigroups up to isomorphism you can still use the IDs from Smallsemi. Simply mark the ID with \(*\), or however else you denote the dual of a semigroup, to refer to the semigroup being anti-isomorphic to the one in the library having the same ID. For all semigroups IsSelfDualSemigroup (4.2-25) is precomputed. This will help to decide whether a semigroup and its dual are actually non-isomorphic.
generated by GAPDoc2HTML