Thurston

The program does computations of the space P(n; 3, 3, 3, 3), i.e, given 2*n equilateral triangles, the space of all different Tetrahedras that can be formed by gluing them together. This was written as part of my Master’s thesis in Mathematics titled “Triangulations of the Sphere after William P. Thurston” at Techniche Universität Berlin.

Requirements

To compile the code in a Unix/Linux environment, you can use make. The program needs Boost C++ libraries and GNU MPFR.

Files

1. matrix.hpp: contains the data structure to represent the 2x2 matrix.
2. algorithms.hpp: contains the implementation of `fundTransform`, an algorithm that takes a 2x2 integer matrix and transforms it using the operators S and T, in such a way that the resulting matrix’s represenation in Complex plane will lie on the standard fundamental domain of PSL_2(Z).

   genSpace: this is the main algorithm discussed in the thesis. The algorithm runs the fundTransform algorithm on a finite set of matrices, which can be proven to generate an exhaustive list of matrices corresponding to P(n; 3, 3, 3, 3).

   genPoints: this runs the fundTransform algorithm on ‘random’ matrices of determinant $2n$. Given a large enough sample size, in practice, the algorithm seems to exhaust the space P(n; 3, 3, 3, 3).

3. main.cpp. parses the command line arguments and calls the required function. The program currently implements the main algorithm from the thesis (algorithm 2.) If you need to run the Monte-Carlo style algorithm (slower and crude), then change the calls in this file, see comments inside the main function.

R Scripts for visualization

Some R scripts are included to help visualize the output of the C++ program. These scripts can be found under the folder: r-scr.

The file poincare.R provides a small R library that can help plot the Poincare Upper half space. This requires the R package named “plotrix”. This can be installed by using the command install.packages("plotrix")

The file 246.R provides the code to visualize the space of P(246; 3, 3, 3, 3). This requires the poincare.R library.

Example: To see this visualization, inside the r-scr directory do the following:

R
> source("246.R")

Execution

After running make, the binary will be generated inside the bin folder

>./thurston --help
Allowed options:
  --help                      produce help message
  -t [ --triangles ] arg (=6) The number of triangles/2
  -w [ --writefile ]          Writes to file n.txt inside the out folder, where
                              2*n is the number of triangles

Example:

> ./thurston -t 16
Number of triangles: 32
[1, 0], [0, 8] z:(4,6.9282)
[1, 1], [0, 8] z:(4,2.3094)
[1, 2], [0, 8] z:(2.85714,0.989743)
[1, 3], [0, 8] z:(2.15385,0.532939)
[1, 4], [0, 8] z:(1.71429,0.329914)
[1, 5], [0, 8] z:(1.41935,0.22349)
[1, 6], [0, 8] z:(1.2093,0.161121)
[1, 7], [0, 8] z:(1.05263,0.121547)
[2, 0], [0, 4] z:(1,1.73205)
[2, 1], [0, 4] z:(1.14286,0.989743)
[2, 2], [0, 4] z:(1,0.57735)
[2, 3], [0, 4] z:(0.842105,0.364642)
[4, 0], [0, 2] z:(0.25,0.433013)
[4, 1], [0, 2] z:(0.285714,0.329914)
[8, 0], [0, 1] z:(0.0625,0.108253)

After transformation, there are 15 elements 
[1, 0], [-4, 8] z:(0,6.9282)
[1, 1], [-4, 4] z:(-1.15875e-16,2.3094)
[1, 2], [-3, 2] z:(-0.142857,0.989743)
[2, -2], [1, 3] z:(-0.5,1.73205)
[2, 0], [-3, 4] z:(-0.5,1.73205)
[1, -3], [3, -1] z:(0.142857,0.989743)
[1, -2], [4, 0] z:(0,2.3094)
[1, -1], [4, 4] z:(3.47626e-16,6.9282)
[2, 0], [-2, 4] z:(0,1.73205)
[2, 1], [-2, 3] z:(0.142857,0.989743)
[2, -2], [2, 2] z:(8.69064e-17,1.73205)
[-2, 1], [0, -4] z:(1.15875e-16,2.3094)
[0, -2], [4, -2] z:(-8.69064e-17,1.73205)
[0, -2], [4, -3] z:(0.5,1.73205)
[0, -1], [8, -4] z:(-3.47626e-16,6.9282)

After removing duplicates, there are 5 elements.
[1, 2], [-3, 2] z:(-0.142857,0.989743)
[2, 0], [-2, 4] z:(0,1.73205)
[2, -2], [1, 3] z:(-0.5,1.73205)
[1, 1], [-4, 4] z:(-1.15875e-16,2.3094)
[1, 0], [-4, 8] z:(0,6.9282)

The notation “[a b], [c, d]” denotes a 2x2 matrix with first row [a, b] and second row [c, d]. The complex number next to it represents the point in the upper half plane of the complex plane corresponding to the matrix.

Developer notes

The program can be compiled in debug mode by using `make debug.` This will verify some asserts, mostly invariants when the program is executing.