This chapter provides an overview of the background material, and provides documentation for the main functions and data structures of the MAPCLASS package.
Let G be a finite group, and let sigma = (sigma_1,...,sigma_2g+r) (for natural numbers g and r) be a tuple of elements of G satisifying the relation
g r
----- -----
| | | |
| |[sigma_i, sigma_{g+1}]| |sigma_{2g+i} = 1
| | | |
i=1 i=1
If we associate the elements of the tuple sigma with the standard generators of the fundamental group of a compact connected surface (genus g, r punctures), then the mapping class group acts on the fundamental group generators inducing an action on the set of tuples. The mapping class orbit is then the orbit under this action. Note that we take these orbits up to conjugation. Often we are only concerned with tuples which generate the group G, such tuples are said to be generating
The package can be used to compute the mapping class orbits for given G and a set of conjugacy classes (C_1,...,C_r) (although the programs expect a tuple of class representatives). We call the tuple (g;C_1,...,C_r) the signature. The package is an extension of the Braid package for GAP
The following are the principal ways for calculating the mapping class orbits for a given signature and group. We require our groups to be permutation groups, and the tuple in question to have length at least two.
> AllMCOrbits( group, genus, tuple ) | ( function ) |
This function calculates the orbit for the given group, genus and tuple. This function is a wrapper for the function AllMCOrbitsCore (1.2-2), and so can make use of GAP's OptionsStack. The options are described in more detail in the documentation for AllMCOrbitsCore (1.2-2)
> AllMCOrbitsCore( group, genus, tuple, partition, constant ) | ( function ) |
This function calculates the orbit for the given group, genus and tuple, with the r branch points partitioned as in partition. It uses the given constant to determine how many of the tuples it want to account for before exiting. This function also make use of GAP's OptionsStack if one desires to alter the algorithm runs. The following options and their defaults are given below.
| Option Name | Default Value |
InitialSizeCutOff |
128 |
MaximumWeight |
40 |
MinimumWeight |
20 |
InitialWeight |
20 |
BumpUp |
7 |
KnockDown |
7 |
InitialNumberOfRandomTuples |
20 |
InitialCutOffValue |
0 |
HashLength |
5000 |
SaveOrbit |
False |
The majority of the options are uninteresting and only subtly alter the running of the routine.The options InitialSizeCutOff, MaximumWeight, MinimumWeight, InitialWeight,BumpUp, KnockDown, are the options controlling how the code handles the subgroup weighting discussed in the algorithm overview. The option InitialNumberOfRandomTuples decides how many tuples the routine collects before trying to see if they are in some pre-existing orbit. The option InitialCutOffValue decides at what point we stop searching for new orbits - if only large orbits are of interest then this can be set larger to ignore smaller orbits. Finally the option SaveOrbit which is by default False can be set to the name of a directory in which you want to save orbits. This option then saves the orbits to files in the folder with "_name". So for example if you wish to save your orbits into the file _example then you would run AllMCOrbits(group, genus, tuple: SaveOrbit:="example");. The orbits are then saved in orbits which are named numerically. Following on from the above example then the first orbit will be saved as "example/0".
> GeneratingMCOrbits( group, genus, tuple ) | ( function ) |
This calculates the orbits for the given arguments. Unlike the AllMCOrbits (1.2-1) function, GeneratingMCOrbits calculates only those orbits whose tuples generate the whole of our original group.
> GeneratingMCOrbitsCore( group, genus, tuple, partition, constant ) | ( function ) |
This calculates the orbits for the given arguments. Unlike the AllMCOrbits (1.2-1) function, GeneratingMCOrbitsCore calculates only those orbits whose tuples generate the whole of our original group. As with AllMCOrbitsCore (1.2-2), the argument partition must be a partition of the conjugacy classes represented in list form. We also have access to the full value of the options stack as in AllMCOrbitsCore (1.2-2).
> MappingClassOrbit( group, genus, principaltuple, partition, tuple ) | ( function ) |
Returns: an orbit record for an orbit containing tuple or returns fail
Calculates the orbit of the tuple with respect to the given group, principaltuple and genus.
> PrepareMinTree( principaltuple, group, ourR, genus ) | ( function ) |
Returns: a record with two keys MinimizationTree and MinimumSet. If record is the returned record then record.MinimizationTree is the list encoding the tree used to help minimize tuples.The list record.MinimumSet is a list of minimal elements which is also used to speed up tuple minimization.
> MinimizeTuple( tuple, minimizationTree, minimumSet, numberOfGenerators ) | ( function ) |
Returns: the minimal tuple in the same orbit of tuple.
Take the minimisation data provided by PrepareMinTree (1.2-6) and minimizes the given tuple.
> EasyMinimizeTuple( group, genus, tuple ) | ( function ) |
Returns: the minimal tuple in the same orbit as tuple.
> IsInOrbit( orbit, tuple ) | ( function ) |
Returns: True if the tuple lies in the orbit.
> FindTupleInOrbit( orbit, tuple ) | ( function ) |
Returns: the index of tuple in orbit.TupleTable if in the orbit. If the tuple is not in orbit returns fail.
> IsEqualOrbit( orbit1, orbit2 ) | ( function ) |
Returns: true if the two orbits are equal else returns fail.
> SelectTuple( orbit, index ) | ( function ) |
Returns: the tuple orbit.TupleTable[index].tuple.
> NumberGeneratingTuples( group, partition, tuple, genus ) | ( function ) |
Returns: the total number of possible generating tuples for the group and tuple.
> TotalNumberTuples( group, tuple, genus ) | ( function ) |
Returns: the total number of tuples we have to account for.
> CalculateTuplePartition( group, tuple ) | ( function ) |
Returns: A partition of ${1,\ldots, r}$ where $r$ is the length of the tuple.
The function returns a partition of ${1,\ldots, r}$ such that i and j lie in the same block if and only if the elements tuple[i] and tuple[j] are member of the same conjugacy class. The program currently requires that the elements of the tuple be ordered such that if tuple[i] and tuple[j] are in the same conjugacy class with i le j then so istuple[k] for all i le k le j.
> RestoreOrbitFromFile( n, name[, path] ) | ( function ) |
Returns: the n-th orbit record from the project with project "name"
By default the function searches the current working directory for the saved project folder and searches inside this for the n-th orbit. If no such orbit exists it returns fail. If an optional argument path is provided then it searches this path for a folder with the name specified (note that path expects a Directory object). If an orbit exists then it is returned as a record as outlined in the data structure section.
> SaveOrbitToFile( orbit, n, name ) | ( function ) |
Saves the orbit to filename "n" in the directory '_name'. The directory must already exist.
Many of the above functions require or return key data structures which we aim to document.
Many of the functions return or expect an orbit "object". This object is in fact record with the following values:
PrincipalFiniteGroup - the finite group
OurG - genus
OurR - length of our primary tuple
OurN - number of points on which our group acts
NumberOfGenerators - 2 OurG+ OurR
OurFreeGroup - a free group on NumberOfGenerators letters
AbsGens - generators for OurFreeGroup
OurAlpha - generators of OurFreeGroupcorresponding to the alpha_i type loops in the fundamental group ( the first g elements of AbsGens)
OurBeta - elements of OurFreeGroup corresponding to beta type loops
OurGamma - generators of OurFreeGroup corresponding to the loops around branch points
TupleTable - a table containing all the tuples in the orbit
HashLength
Hash
PrimeCode
OurAction
ActionOnOrbit
MinimizationTree- minimization structure
MinimumSet- minimizaton structure
The tuple table is a list. Each element of the list is a record with the names, tuple and next. If orbit is an orbit object then orbit.TupleTable[n].tuple returns the tuple at index n of the tuple table.
We demonstate how one might use the package.
gap> group:=AlternatingGroup(5);
Alt( [ 1 .. 5 ] )
gap> tuple:=[ (1,2)(3,4), (1,2)(3,4), (1,2)(3,4) ]
[ (1,2)(3,4), (1,2)(3,4), (1,2)(3,4) ]
gap> orbits:=AllMCOrbits(group,1,tuple);;
Total Number of Tuples: 189120
Collecting 20 random tuples... done
Cleaning done; 20 random tuples remaining
Orbit 1:
Length=3072
Generating Tuple =[ (1,2,4,5,3), (1,4,5,2,3), (1,2)(4,5),
(1,4)(2,3), (2,5)(3,4) ]
Generated subgroup size=60
Centralizer size=1
4800 tuples remaining
Cleaning current orbit...
Cleaning a list of 20 tuples
Random Tuples Remaining: 0
Cleaning done; 0 random tuples remaining
Collecting 20 random tuples... done
Cleaning orbit 1
Cleaning a list of 20 tuples
Random Tuples Remaining: 0
Cleaning done; 0 random tuples remaining
Collecting 40 random tuples... done
Cleaning orbit 1
Cleaning a list of 40 tuples
Random Tuples Remaining: 3
Cleaning done; 3 random tuples remaining
Orbit 2:
Length=32
Generating Tuple =[ (1,4)(2,3), (1,2)(3,4), (1,4)(2,3), (1,2)(3,4),
(1,3)(2,4) ]
Generated subgroup size=4
Centralizer size=4
4320 tuples remaining
Cleaning current orbit...
Cleaning a list of 3 tuples
Random Tuples Remaining: 2
Cleaning done; 2 random tuples remaining
Orbit 3:
Length=72
Generating Tuple =[ (1,5,2), (1,3,2), (1,2)(3,5), (1,3)(2,5),
(1,3)(2,5) ]
Generated subgroup size=12
Centralizer size=1
0 tuples remaining
Cleaning current orbit...
Cleaning a list of 2 tuples
Random Tuples Remaining: 0
Cleaning done; 0 random tuples remaining
gap> # Check we have as many orbits as it says...
gap> Length(orbits);
3
gap> # Inspect the first orbit..
gap> orb1:=orbits[1];;
gap> # How long is orb1?
gap> Length(orb1.TupleTable);
3072
gap> # Select element 42 ...
gap> SelectTuple(orb1, 42);
[ (1,3,4), (1,5,3,2,4), (1,5)(2,4), (1,2)(3,5), (2,3)(4,5) ]
gap> # Save the orbit to a file...
gap> SaveOrbitToFile(orb1, 1, "test");
gap> #If the folder doesn't exist we get an error..
gap> SaveOrbitToFile(orb1, 1, "foo");
AppendTo: cannot open '_foo/1' for output at
CallFuncList( APPEND_TO, arg );
gap> #
gap> # Now we try find generating orbits
gap> group:=SymmetricGroup(5);
Sym( [ 1 .. 5 ] )
gap> # And we will save them using the `SaveOrbit` option
gap> GeneratingMCOrbits(group,1,tuple : SaveOrbit:="example");;
Total Number of Tuples: 607680
Collecting 20 generating tuples .. done
Cleaning done; 20 random tuples remaining
Orbit 1:
Length=5064
Generating Tuple =[ (1,3,2,5), (2,4,3), (1,4)(3,5), (1,3)(2,5),
(1,4)(3,5) ]
Generated subgroup size=120
Saving orbit to file _example/0
Centralizer size=1
0 tuples remaining
Cleaning current orbit...
Cleaning a list of 20 tuples
Random Tuples Remaining: 0
Cleaning done; 0 random tuples remaining
gap> generatingorbits:=last;;
gap> # How many generating orbits are there?
gap> Length(generatingorbits);
1
gap> # Is this orbit equal to the other one we found earlier
gap> IsEqualOrbit(orb1, generatingorbits[1]);
fail
gap> # We can reload the orbits...
gap> orb2:=RestoreOrbitFromFile(0, "example");;
gap> Length(orb2.TupleTable);
5064
|
generated by GAPDoc2HTML