GAP (semigroups) - Chapter 1: The Semigroups package

This is the manual for the Semigroups package version 2.8.0. Semigroups 2.8.0 is a distant descendant of the Monoid package for GAP 3 by Goetz Pfeiffer, Steve A. Linton, Edmund F. Robertson, and Nik Ruskuc; and the Monoid package for GAP 4 by J. D. Mitchell.

Many of the operations, methods, properties, and functions described in this manual only apply to semigroups of transformations, partial permutations, bipartitions, subsemigroups of regular Rees 0-matrix semigroups over groups, semigroups of matrices over finite fields, free inverse semigroups, and free bands. For the sake of brevity, we have opted to say semigroup to describe the aforementioned classes of semigroups.

Semigroups 2.8.0 contains more efficient methods than those available in the GAP library (and in many cases more efficient than any other software) for creating semigroups and ideals, calculating their Green's structure, size, elements, group of units, minimal ideal, and testing membership, finding the inverses of a regular element, and factorizing elements over the generators, and many more; see Chapters 2, 3, and 4. There are also methods for testing if a semigroup satisfies a particular property, such as if it is regular, simple, inverse, completely regular, and a variety of further properties; see Chapter 4. The theory behind the main algorithms in Semigroups will be described in a forthcoming article.

It is harder for Semigroups to compute Green's \(\mathscr{L}\)- and \(\mathscr{H}\)-classes of a transformation semigroup. The methods used to compute with Green's \(\mathscr{R}\)- and \(\mathscr{D}\)-classes are the most efficient in Semigroups. Thus, if you are computing with a transformation semigroup, wherever possible, it is advisable to use the commands relating to Green's \(\mathscr{R}\)- or \(\mathscr{D}\)-classes rather than those relating to Green's \(\mathscr{L}\)- or \(\mathscr{H}\)-classes. No such difficulties are present when computing with semigroups of partial permutations, bipartitions, subsemigroups of a regular Rees 0-matrix semigroup over a group, or semigroups of matrices over a finite field.

The methods in Semigroups allow the computation of individual Green's classes without computing the entire data structure of the underlying semigroup; see GreensRClassOfElementNC (4.2-3). It is also possible to compute the \(\mathscr{R}\)-classes, the number of elements and test membership in a semigroup without computing all the elements; see, for example, GreensRClasses (4.3-1), RClassReps (4.3-4), IteratorOfRClassReps (4.3-2), IteratorOfRClasses (4.3-3), or NrRClasses (4.4-6). This may be useful if you want to study a very large semigroup where computing all the elements of the semigroup is not feasible.

There are methods for finding: congruences of certain types of semigroups (based on Section 3.5 in [How95]), the normalizer of a semigroup in a permutation group (as given in [ABMN10]), the maximal subsemigroups of a finite semigroup (based on [GGR68]), smaller degree partial permutation representations (based on [Sch92]) and the character table of an inverse semigroup. There are functions for producing pictures of the Green's structure of a semigroup, and for drawing bipartitions; see Sections 4.8 and 5.8.

Several standard examples of semigroups are provided see Section 2.5. Semigroups also provides functions to read and write collections of transformations, partial permutations, and bipartitions to a file; see ReadGenerators (1.6-2) and WriteGenerators (1.6-3).

Details of how to create and manipulate semigroups of bipartitions can be found in Chapter 5.

Details of how to create and manipulate semigroups of matrices over a finite field can be found in Chapter 7.

There are also functions in Semigroups to define and manipulate free inverse semigroups and their elements; this part of the package was written by Julius Jonušas; see Chapter 6 and Section 5.10 in [How95] for more details.

Semigroups contains functions synonymous to some of those defined in the GAP library but, for the sake of convenience, they have abbreviated names; further details can be found at the appropriate points in the later chapters of this manual.

Semigroups contains different methods for some GAP library functions, and so you might notice that GAP behaves differently when Semigroups is loaded. For more details about semigroups in GAP or Green's relations in particular, see Reference: Semigroups or Reference: Green's Relations.

The Semigroups package is written GAP code and requires the Orb and IO packages. The Orb package is used to efficiently compute components of actions, which underpin many of the features of Semigroups. The IO package is used to read and write transformations, partial permutations, and bipartitions to a file.

The Grape package must be loaded for the operation SmallestMultiplicationTable (9.1-2) to work, and it must be fully compiled for the following functions to work:

If Grape is not available or is not compiled, then Semigroups can be used as normal with the exception that the functions above will not work.

The genss package is used in one version of the function Normalizer (4.5-23) but nowhere else in Semigroups. If genss is not available, then Semigroups can be used as normal with the exception that this function will not work.

If you find a bug or an issue with the package, then report this using the issue tracker.

1.2 Installing the Semigroups package

In this section we give a brief description of how to start using Semigroups.

It is assumed that you have a working copy of GAP with version number 4.8.3 or higher. The most up-to-date version of GAP and instructions on how to install it can be obtained from the main GAP webpage http://www.gap-system.org.

The following is a summary of the steps that should lead to a successful installation of Semigroups:

Presuming that the above steps can be completed successfully you will be running the Semigroups package!

If you want to check that the package is working correctly, you should run some of the tests described in Section 1.4.

1.3 Compiling the documentation

To compile the documentation use SemigroupsMakeDoc (1.3-1). If you want to use the help system, it is essential that you compile the documentation.

1.3-1 SemigroupsMakeDoc

‣ SemigroupsMakeDoc( ) ( function )

This function should be called with no argument to compile the Semigroups documentation.

1.4 Testing the installation

In this section we describe how to test that Semigroups is working as intended. To test that Semigroups is installed correctly use SemigroupsTestInstall (1.4-1) or for more extensive tests use SemigroupsTestAll (1.4-3). Please note that it will take a few seconds for SemigroupsTestInstall (1.4-1) to finish and it may take several minutes for SemigroupsTestAll (1.4-3) to finish.

If something goes wrong, then please review the instructions in Section 1.2 and ensure that Semigroups has been properly installed. If you continue having problems, please use the issue tracker to report the issues you are having.

1.4-1 SemigroupsTestInstall

‣ SemigroupsTestInstall( ) ( function )

This function should be called with no argument to test your installation of Semigroups is working correctly. These tests should take no more than a fraction of a second to complete. To more comprehensively test that Semigroups is installed correctly use SemigroupsTestAll (1.4-3).

1.4-2 SemigroupsTestManualExamples

‣ SemigroupsTestManualExamples( ) ( function )

This function should be called with no argument to test the examples in the Semigroups manual. These tests should take no more than a few minutes to complete. To more comprehensively test that Semigroups is installed correctly use SemigroupsTestAll (1.4-3). See also SemigroupsTestInstall (1.4-1).

1.4-3 SemigroupsTestAll

‣ SemigroupsTestAll( ) ( function )

This function should be called with no argument to comprehensively test that Semigroups is working correctly. These tests should take no more than a few minutes to complete. To quickly test that Semigroups is installed correctly use SemigroupsTestInstall (1.4-1).

1.5 More information during a computation

1.5-1 InfoSemigroups

‣ InfoSemigroups ( info class )

InfoSemigroups is the info class of the Semigroups package. The info level is initially set to 0 and no info messages are displayed. We recommend that you set the level to 1 so that basic info messages are displayed. To increase the amount of information displayed during a computation increase the info level to 2 or 3. To stop all info messages from being displayed, set the info level to 0. See also Reference: Info Functions and SetInfoLevel (Reference: SetInfoLevel).

1.6 Reading and writing elements to a file

The functions ReadGenerators (1.6-2) and WriteGenerators (1.6-3) can be used to read or write transformations, partial permutations, and bipartitions to a file.

1.6-1 SemigroupsDir

‣ SemigroupsDir( ) ( function )

This function returns the absolute path to the Semigroups package directory as a string. The same result can be obtained typing:

PackageInfo("semigroups")[1]!.InstallationPath;

1.6-2 ReadGenerators

‣ ReadGenerators( filename[, nr] ) ( function )

If filename is the name of a file created using WriteGenerators (1.6-3), then ReadGenerators returns the contents of this file as a list of lists of transformations, partial permutations, or bipartitions.

If the optional second argument nr is present, then ReadGenerators returns the elements stored in the nrth line of filename.

gap> file:=Concatenation(SemigroupsDir(), "/tst/test.gz");;
gap> ReadGenerators(file, 1378);
[ Transformation( [ 1, 2, 2 ] ), IdentityTransformation, 
  Transformation( [ 1, 2, 3, 4, 5, 7, 7 ] ), 
  Transformation( [ 1, 3, 2, 4, 7, 6, 7 ] ), 
  Transformation( [ 4, 2, 1, 1, 6, 5 ] ), 
  Transformation( [ 4, 3, 2, 1, 6, 7, 7 ] ), 
  Transformation( [ 4, 4, 5, 7, 6, 1, 1 ] ), 
  Transformation( [ 7, 6, 6, 1, 2, 4, 4 ] ), 
  Transformation( [ 7, 7, 5, 4, 3, 1, 1 ] ) ]

1.6-3 WriteGenerators

‣ WriteGenerators( filename, list[, append] ) ( function )

This function provides a method for writing transformations, partial permutations, and bipartitions to a file, that uses a relatively small amount of disk space. The resulting file can be further compressed using gzip or xz.

The argument list should be a list of elements, a semigroup, or a list of lists of elements, or semigroups. The types of elements and semigroups supported are: transformations, partial permutations, and bipartitions.

The argument filename should be a string containing the name of a file where the entries in list will be written or an IO package file object.

If the optional third argument append is given and equals "w", then the previous content of the file is deleted. If the optional third argument is "a" or is not present, then list is appended to the file. This function returns true if everything went well or fail if something went wrong.

WriteGenerators appends a line to the file filename for every entry in list. If any element of list is a semigroup, then the generators of that semigroup are written to filename.

The first character of the appended line indicates which type of element is contained in that line, the second character m is the number of characters in the degree of the elements to be written, the next m characters are the degree n of the elements to be written, and the internal representation of the elements themselves are written in blocks of m*n in the remainder of the line. For example, the transformations:

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

t210 2 2 6 7 2 6 9 9 1 1 5 3 8 1 9 9 410 510 6

1.6-4 IteratorFromGeneratorsFile

‣ IteratorFromGeneratorsFile( filename ) ( function )

If filename is a string containing the name of a file created using WriteGenerators (1.6-3), then IteratorFromGeneratorsFile returns an iterator iter such that NextIterator(iter) returns the next collection of generators stored in the file filename.

This function is a convenient way of, for example, looping over a collection of generators in a file without loading every object in the file into memory. This might be useful if the file contains more information than there is available memory.

1 The Semigroups package

1.1 Introduction

1.2 Installing the Semigroups package