GAP (HyperCells) - Chapter 1: Introduction

HyperCells is a package that allows constructing primitive cells and supercells of hyperbolic lattices based on triangle groups and quotients with normal subgroups. An introduction to the underlying concepts can be found in the following preprint

If you use this package, please cite at least one of the above references in addition to the package itself:

More information on how to cite, including BibTeX entries, can be found in the Readme file of the package repository given above.

1.1 Example

In this section, some basic examples illustrating the use are shown. For more details, please refer to the documentation of the individual types, operators, and functions.

A typical workflow starts by setting up the (proper) triangle group, here we choose \(\Delta^+(2,8,8)\):

gap> tg := ProperTriangleGroup( [ 2, 8, 8 ] );
ProperTriangleGroup(2, 8, 8)

The returned object is of category ProperTriangleGroup (see 2.1). Next, we specify a unit cell of the lattice in terms of the quotient of \(\Delta^+\) with a translation group \(\Gamma\triangleleft\Delta^+\). For that we can query the included database based on the work of Marston Conder [Con07]:

gap> ListTGQuotients( [ 2, 8, 8 ] );
[ [ 2, 6 ], [ 3, 10 ], [ 3, 11 ], [ 5, 12 ], [ 5, 13 ], [ 9, 19 ], ... ]

which allows us to select one of them, here the one denoted by T2.6, where 2 is the genus of the surface on which the quotient group acts, and 6 the position in the list of all quotients with the same genus.

gap> q := TGQuotient( [ 2, 6 ] );
TGQuotient([ 2, 6 ], [ 2, 8, 8 ], 8, 2, Action reflexible [m,n],
    [ x^2, x * y * z, x * z * y, y^3 * z^-1 ])

as an object of category TGQuotient (see 2.3). Alternatively, we can access the first entry appearing for \(\Delta^+(2,8,8)\) using

gap> q := TGQuotient( 1, [ 2, 8, 8 ] );
TGQuotient([ 2, 6 ], [ 2, 8, 8 ], 8, 2, Action reflexible [m,n],
    [ x^2, x * y * z, x * z * y, y^3 * z^-1 ])

Once we have the triangle group and the TGQuotient object, we can obtain the quotient group \(G^+\cong\Delta^+/\Gamma\)

gap> G := TGQuotientGroup( tg, q );
<fp group on the generators [ x, y, z ]>

gap> TGTranslationGroup( tg, q );
TranslationGroup( < g1, g2, g3, g4 | g4*g3*g2*g1*g2^-1*g4^-1*g1^-1*g3^-1 > )

The next step is to construct the graph representing primitive cell. This graph corresponds to a triangular tessellation of the compactified cell and is stored as an object of category TGCellGraph (see 3.7). In addition to the triangle group and quotient, we also need to specify the vertex at which the cell should be centered (here we choose 3 corresponding to the \(z\) vertex of the fundamental Schwarz triangle):

gap> cg := TGCellGraph( tg, q, 3 : simplify := 5 );
TGCellGraph(
    TGCell( ProperTriangleGroup(2, 8, 8), [ x^2, x*y*z, x*z*y, y^3*z^-1 ] ),
    center = 3,
    vertices = [ [ 1, 1 ], [ 1, 2 ], [ 1, 3 ], [ 1, 4 ], [ 2, 1 ], [ 3, 1 ] ],
    edges = [ [ 1, 6, 1, <identity ...> ], ..., [ 6, 5, 8, g1^-1*g2*g3^-1 ] ],
    faces = [ [ [ 3, 1 ], [ 2, 1 ], [ 14, -1 ], [ 6, -1 ] ], ... ],
    boundary = [ [ <identity ...>, <identity ...>, 2, 1, 0, g1 ], ... ]
)

The option simplify specifies the maximum wordlength that should be checked for simplifying expressions in terms of the translation generators g1, g2, etc. The default value is 0 which means that no simplification is performed. While the graph itself represents the compactified cell, potential translations associated with the edges crossing from one copy of the cell to another are stored as well. See 3.7 for more details the format of the vertices, edges, faces, and the boundary.

The cell graph can be exported using the Export (3.7-13) operation, see 8.1 for more details on the produced file format to import it using other software.

With the cell graph at hand, we can derive a model graph, such as a tessellation graph, i.e., the nearest-neighbor graph of the \(\{8,8\}\) tessellation of the hyperbolic plane restricted to the primitive cell:

gap> model := TessellationModelGraph( cg, true : simplify := 0 );
TGCellModelGraph(
    TGCell( ProperTriangleGroup(2, 8, 8), [ x^2, x*y*z, x*z*y, y^3*z^-1 ] ),
    center = 3,
    type = [ "TESS", [ 8, 8 ], [ "VEF", [ [ 3 ], [ 1 ], [ 2 ] ] ] ],
    vertices = [ [ 3, 1 ] ],
    edges = [ [ 1, 1, [ 1, [ 1, 1, 5 ] ], g1 ], [ 1, 1, [ 1, [ 2, 4, 8 ] ], g4 ],
        [ 1, 1, [ 1, [ 3, 2, 6 ] ], g2 ], [ 1, 1, [ 1, [ 4, 3, 7 ] ], g3 ] ],
    faces = [ [ [ 1, -1 ], [ 2, -1 ], [ 4, 1 ], [ 3, -1 ], [ 1, 1 ], [ 2, 1 ],
        [ 4, -1 ], [ 3, 1 ] ] ]
)

The result is an object of category TGCellModelGraph (see 4.1), which can be exported using the Export (4.4-1) operation, producing a file in the format described in 8.2.

Finally, the model graph defined on the primitive cell can be extended to a supercell, i.e., a cell specified by a translation subgroup \(\Gamma'\triangleleft\Gamma\) of the original translation group \(\Gamma\). Here, we consider the one given by the quotient T3.11 and first construct the symmetric cell (but without simplifying the translation generators):

gap> sc := TGCellSymmetric( tg, TGQuotient( [ 3, 11 ] ), 3 );
TGCell( ProperTriangleGroup(2, 8, 8), [ x^2, x*y*z, x*z*y, y^-8 ] )

gap> scmodel := TGSuperCellModelGraph( model, sc : simplify := 0 );
TGSuperCellModelGraph(
    primitive cell = TGCell( ProperTriangleGroup(2, 8, 8),
        [ x^2, x*y*z, x*z*y, y^3*z^-1 ] ),
    supercell = TGCell( ProperTriangleGroup(2, 8, 8),
        [ x^2, x*y*z, x*z*y, y^-8 ] ),
    cell embedding = TGCellEmbedding(
        primitive cell = TGCellTranslationGroup( < g1, g2, g3, g4 |
            g2*g1^-1*g4^-1*g3*g2^-1*g1*g4*g3^-1 > ),
        supercell = TGCellTranslationGroup( < g1, g2, g3, g4, g5, g6 |
            g6*g4*g2*g1*g3*g5*g3^-1*g2^-1*g6^-1*g5^-1*g1^-1*g4^-1 > ),
        transversal = [ <identity ...>, (x^-1*y^-1)^4*x^-1 ],
        embedding = [ g1, g2, g3, g4, g5, g6 ] -> [ g1^-1*g4^-1, ... ]
    ),
    center = 3,
    type = [ "TESS", [ 8, 8 ], [ "VEF", [ [ 3 ], [ 1 ], [ 2 ] ] ] ],
    vertices = [ [ 3, 1, 1 ], [ 3, 1, 2 ] ],
    edges = [ [ 1, 2, [ 1, 1, [ 1, [ 1, 1, 5 ] ] ], <identity ...> ], ... ],
    faces = [ ]
)

which is returned as an object of category TGSuperCellModelGraph (see 5.1) and can be exported using the Export (5.5-1) operation, producing a file in the format described in 8.3.

1.2 Simplify extension (optional)

The HyperCells package has an integrated word simplification procedure for a selection of functions. Two methods are available: a default brute-force method, and a method based on the Knuth-Bendix completion algorithm. The latter can only be used provided the kbmag package (verion 1.5.10+) is available.

The default configuration of the kbmag package allows HyperCells to simplify words in groups with a maximal number of generators of 127. However, this limit can manually be extended up to 65535. The corresponding adjustments are laid out in a README file in the kbmag package and can be found in the folder containing GAP: “…/gap/gap-< version >/pkg/kbmag/standalone”, with the following instructions:

NEW in Version 2.3: It is now possible to use kbmag with more than the
previous default number of 127 generators. To use up to 65535 generators,
before making the package, edit the file "defs.h" in the lib directory,
and change the two lines:

#define MAXGEN MAXCHAR /* maximum number of generators */
typedef char gen; /* for generators of monoids and groups */

to

#define MAXGEN MAXUSHORT /* maximum number of generators */
typedef unsigned short gen; /* for generators of monoids and groups */

Once these changes are made, kbmag needs to be recompiled. This can be done in the terminal, where in the kbmag directory one needs to execute the command make clean and afterwards make.

If these changes are not made while using the Knuth-Bendix completion algorithm based simplification and unit cells compactified on Rieman surfaces with genus exceeding 63 are used, the procedure will not be excecuted and a warning will be printed in GAP:

#WARNING: maximal number of genartors have been exceeded; non-simplified words 
will be used. Please follow the instructions in the chapter Introduction section
Simplify extension (optional) in the HyperCells reference manual.

Let us look at an example, provided kbmag is installed. We can apply the Knuth-Bendix method by using the option simplifyMethod specifying the method of simplification, which we can set to "KnuthBendix" (the default is "BruteForce"):

gap> scmodel := TGSuperCellModelGraph( model, sc : simplify := 4*3, 
>       simplifyMethod := "KnuthBendix");
#WARNING: system is not confluent, so reductions may not be to normal form.
TGSuperCellModelGraph(
    primitive cell = TGCell( ProperTriangleGroup(2, 8, 8),
        [ x^2, x*y*z, x*z*y, y^3*z^-1 ] ),
    supercell = TGCell( ProperTriangleGroup(2, 8, 8),
        [ x^2, x*y*z, x*z*y, y^-8 ] ),
    cell embedding = TGCellEmbedding(
        primitive cell = TGCellTranslationGroup( < g1, g2, g3, g4 |
            g2*g1^-1*g4^-1*g3*g2^-1*g1*g4*g3^-1 > ),
        supercell = TGCellTranslationGroup( < g1, g2, g3, g4, g5, g6 |
            g6*g4*g2*g1*g3*g5*g3^-1*g2^-1*g6^-1*g5^-1*g1^-1*g4^-1 > ),
        transversal = [ <identity ...>, (x^-1*y^-1)^4*x^-1 ],
        embedding = [ g1, g2, g3, g4, g5, g6 ] -> [ g1^-1*g4^-1, ... ]
    ),
    center = 3,
    type = [ "TESS", [ 8, 8 ], [ "VEF", [ [ 3 ], [ 1 ], [ 2 ] ] ] ],
    vertices = [ [ 3, 1, 1 ], [ 3, 1, 2 ] ],
    edges = [ [ 1, 2, [ 1, 1, [ 1, [ 1, 1, 5 ] ] ], <identity ...> ], ... ],
    faces = [ ]
)

where we have set the option simplify to twice the number of generators (or four times the genus) in the associated translation group. A set of equations, denoted as rewriting rules, will be constructed in the Knuth-Bendix method. In contrast to the brute-force method, the meaning of the option simplify is slightly adjusted. simplify now specifies the maximal length of those rewriting rules. Specifically, the left- and right- hand sides are maximally simplify and 2*(simplify + 1) long, respectively. If simplify is smaller than twice the number of generators in the associated translation group, simplify will default back to twice the number of generators, instead.

Note that in general, the system will not be confluent, i.e., the simplification might not yield the optimal solution. Nontheless, the application of the Knuth-Bendix method will still be able to simplify some words, however, shorter words might be available.

1 Introduction

1.1 Example

1.2 Simplify extension (optional)