In this chapter we outline how the semigroups in the library were found, exactly what semigroups are available, how they are stored, and how further information regarding the properties of these semigroups is handled.
This section describes which semigroups are contained in the library and how they were determined.
The purpose of the library is to provide one semigroup of every `structural type'. The semigroups are represented by their multiplication table. Usually, say, for groups, `structural type' means 'up to isomorphism' which corresponds to relabelling the elements. Roughly speaking, transposing the multiplicationable of a semigroup does not alter its important structure features either. More precisely, the usual description of the structure of a semigroup using Green's relations is invariant under these operations. So, we consider two semigroups to be of the same structure if they are isomorphic or anti-isomorphic. We will refer to semigroups that are isomorphic or anti-isomorphic as equivalent. The vast number of non-equivalent semigroups with small numbers of elements (see Table 1.) limits us to providing the semigroups with at most 8 elements.
The problem of constructing semigroups up to isomorphism and anti-isomorphism has been considered by many authors. For very small orders, that is 1 to 5, all the semigroups up to isomorphism and anti-isomorphism were computed by hand [THA+55] and [Tam54]. The first instance of the use of computers to find all semigroups up to isomorphism and anti-isomorphism is described in Forsythe [For55]. Subsequently, the number of semigroups with 6 elements was found by Plemmons [Ple67], with 7 elements by Jürgensen and Wick [JW77], with 8 by Satoh, Yama and Tokizawa [SYT94], and with 9 by Distler, Kelsey, and Mitchell in 2008. Even if the authors could store their results they had no means to make them publicly available. Plemmons, for example, explicitly states that he had all multiplication tables for semigroups of size 6 on magnetic tape. Jürgensen and Wick back in 1977 did not store the semigroups of size 7 because of their large number. The tables for semigroups with 8 elements use up several gigabytes of disk space (while the compressed library files in Smallsemi need only 22 MB).
Trying to recreate the results from the existing literature, it quickly becomes obvious that even some 15 years later, with considerably more computing power available, the task of obtaining all semigroups with 8 elements is still by no means trivial. Our technique was to find all associative multiplication tables up to isomorphism and anti-isomorphism using a combination of GAP and the Constraint Satisfaction Problem (CSP) solver Minion [GJM06]. More specific details on the search will be available in a later version of Smallsemi.
As discussed in the previous section, we store data relating to the multiplication table of one representative of every class of equivalent semigroups with 1 to 8 elements.
The tables for semigroups with 2 to 7 elements are stored in the files data2.gl.gz to data7.gl.gz in the directory data/data2to7.
For semigroups of size 8 the data is contained in the directories data/data8-3nil and data/data8. The former contains the data relating to 3-nilpotent semigroups (see NilpotencyDegree (4.2-34)) and the latter the data for all the remaining semigroups of size 8.
The tables of non-3-nilpotent semigroups are partitioned into files 8diag<entries in the diagonal>.gl.gz with respect to their diagonals. For example, 8diag12345678.gl.gz contains tables for all the bands of order 8.
Any 3-nilpotent semigroup has a unique minimal generating set containing those elements that do not appear in the table. We only require the subtable with entries corresponding to the product of two generators, as all other products are zero. Thus if \(m\) is the number of generators, we retain information regarding the entries of an \(m \times m\) table. However, we do not store all the tables in this case. The \(m \times m\) tables can be sorted into ranges and then the first table and the number of tables in the range are stored. For every diagonal there is a file diag<entries in the diagonal>.gl.gz containing the first tables of each range and a separate file named diag<entries in the diagonal>pos.gl.gz containing the lengths of these ranges.
| class | file names | data size | - gzipped | compression factor |
| sizes 2-7 | data<size>.gl |
39 MB | 680 KB | 58 |
| size 8, not 3-nilpotent | 8diag<diagonal>.gl |
613 MB | 10 MB | 61 |
| size 8, 3-nilpotent | diag<diagonal>.gl |
974 MB | 11 MB | 89 |
All together the GAP library files take just under 22 MB of disk space after compression while allowing fast recovering of the data. The compression rates demonstrated in the table above were achieved using gzip with the highest possible compression (-9 switch) as well as careful analysis and intensive testing of how best to structure the data in the files.
The semigroups in the library satisfying certain standard properties have been identified and this information is stored in the files info1.g.gz to info8.g.gz. To find out what properties have been considered see PrecomputedSmallSemisInfo (4.5-15).
generated by GAPDoc2HTML