Quasi Fuchsian Toolbox
Chris King
For help/queries, email

This toolbox contains a series of Matlab functions a Mac OS viewing application and C routines capable of portyraying such sets on any GCC capable OS.

1. Matlab Toolbox Functions

2. OS independent C-scripts

3. DFS Viewer for Mac OS

The key depiction funcions are depthfirst.m in Matlab, depthfirst.c in GCC and DFS Viewer application for Mac OS.

1. Matlab Toolbox Functions

function outfl=depthfirst (A,B,ep,levmax,scal,sav,spec,siz,iterate,tab,fsn) Generates a limit set portrait using the DFS algorithm

An extended beta version function outfl=depthfirstcom(A,B,ep,levmax,scal,sav,spec,siz,iterate,tcomm,typ,fsn) allows for more varied normalizations than grandma and uses the value of the commutator, rather than tab for ease of computation and input. A variable offs is included in the plotting routine which can be adjusted if a custom normalization is explored using typ. Many of these do not work with DFS so use qFstochastic in the first instance.

Examples:

Standard discrete group limit sets
depthfirst(2,2,0.001,1000,1,0);     %Standard Apollonian gasket spec = 0
depthfirst(2,2,0.001,1000,1,0,1);     %Apollonian gasket with spec = 1 closing gaps at the sides
depthfirst(1.87+0.1i,1.87-0.1i,0.001,1000,1/2.8,0,0,1100,3);    % Colours the limit set by the 3rd iterate
depthfirst(1.87+0.1i,1.87-0.1i,0.01,1000,1/2.8,0,1); %Spec = 1 Uses special words to avoid cutting off necks

Non-free group examples with relations (aba-1b-1)2 = I
depthfirst(1.924781-0.047529i,2,0.005,1000,2,1,2,1100,-2,1.9248-1.4617i);
depthfirst(1.9247306-0.0449408i, 1.91+0.2i,0.005,3000,1/6,1,2,1100,-2, 1.8569-1.2426i);
depthfirst(2,2,0.005,1000,2,2,2,1100,2.0000-1.4142i); or depthfirst(2,2,0.005,1000,2,2,2,1100,-2,nonfree(2,2,0,0));

Special words example with aaB parabolic.
the function speacialwords can be reprogrammed to handle examples like
the double cusps where longer expressions like 2/5, where aaaBaaB, is parabolic
depthfirst2b(2+i,3,0.005,3000,1,2,4)

Function parameters
A,B are traces of the Mobius transforms generating a, b, a-1, b-1
ep=epsilon in the tree search using commutator attracting fixed pts
levmax is the maximum depth of the tree search (10000 if set to 0)
scal is the scaling factor for depicting the image
sav = 1, 3 saves the file as a png. If sav >= 2 we also have a program timer
sa v = -1 test mode - exits on completion outfl = 1 or on reaching levmax outfl = 0
the timer reports tabs(1-4) as the numbers cycle through branches
you can either produce a black line plot or a coloured image
iterate = -2 plot n > 0 colour image by n-th iterate, -1 by final level, 0 black
spec = 0 standard method
spec = 1 special words used also on fixed pts of a, b, a-1, b-1
this refines whorls with necks and when A = 2 and B = 2 closes the gasket gaps
spec = 2, 3 as 0, 1 but for non-free groups using automatic group table.
If the positive grandma root is to be chosen add 4 to spec.
FSA is used to remove null words when (aba-1b-1)2 = I
spec=4 special words included from the subfunction specialwords()
siz is the image size default 1100 x 1100
if you add a tenth parameter tab you can generate non-free limit sets
tab is the trace of ab used in the advanced grandma algorithm
to test full exploration of the tree, uncomment 102-107, with levmax = 4
fsn allows for a custom FSA file from the FSA folder to be used.

Other options in the listing comments can be amended e.g. to provide an escape if the DFS algorithm goes into degenerate or chaotic behaviour.

function batchlimsets(n,eps,sav,levmax) Plots a sequence of limit sets for rational p/n p = 1:n
n is the number of the batch e.g. 61 for all the rational p/61 cusp sets eps, sav, levmax as above.

function [p0,q0,p1,q1]=fareyadd(s) Finds the two rational fractions p/q determined by a set of left and right passes on the Farey tree.
e.g. [p0,q0,p1,q1]=fareyadd([0 0 0 0 0 0 1 0 0 0 0 0 0 1 0 0 0 0 0 0 1]); gives 63/433 55/378

function [p,q]=fareyfrac(s) Finds the single fraction that is the descendent of these two e.g. 118/811=(63+55)/(433+378)

function s=fareyseq(p,q) Does the reverse step the sequence of Farey movs arriving a given fraction
e.g. fareyseq(118,811) gives [0 0 0 0 0 0 1 0 0 0 0 0 0 1 0 0 0 0 0 0 1].

function [a,b]=grandma(ta,tb,posroot,opt,tab) Generates the generators a, b from the traces ta, tb.
Posroot allows the choice of either qquare root in the calculation
opt = 0 is the standard not requiring tab opt = 1 gives Jorgensen's recipe
opt = 2 uses the grandfather identity and tab in the' four alarm' version

There are also several other normalizations included including symmetric with variants, polar, and canonical that are used in the beta extended versions of qFstochasticom and depthfirstcom.

function [e,tt]=tracepq(p,q,opt,prt) Finds the trace for a rational limit set with Tb=2
opt = 0 f = 2 root, opt = 1 f = -2 root, non free opt = 2 f = 2 root, opt = 3 f = -2 root
e.g. [e,tt]=tracepq(5,7,0,1); will list the roots in e and sorted in tt
In this case the key solution is e(1) which we can confirm by calling depthfirst(e(1),2,0.001,1000,1,0);

function [v,i]=tracepqr(p,q,opt,val,ep)
Does the same for a higher fraction using a closely related Farey precursor as hint val generated by tracepq

e.g.v=tracepqr(1597,2584,0,1.61691788-1.29437374i,1e-8) using the values of tracepq for 233/377

function f=recursean(opt,stps) and function [s,a]=recurscoeffs(stps,opt) are routines which enable the polynomial representations of μ(1/n) and aN = 1 to be represented and the roots found to investigate elliptic limit sets.

function pltmuscol51(opt) Plots all roots forming the Maskit slice up to n = 51
opt=0 usual free version 2 non-free
Requires mus.mat and mus0.mat generated by slicec for trace values to find all roots up to a given n using tracepq.

function M=qFstochastic(A,B,scope,rpts,siz,scal,opt,sav,tab,M) Performs a randomly iterated approximation to any limit set.

An extended beta version function [M comm tab a b]=qFstochasticom(A,B,scope,rpts,siz,scal,opt,sav,tcomm,typ,offs,M) is also provided which has been used to generate the more advanced images in figs 26c-e, which is also easier to use as it takes tcom as input rather than having to calculate tab for each case. It also allows a variety of experimental normalizations and prvides for these requiring an offset to be protrayed.

The program generates a limit set from random iterations of the generators using commutators and related starting points. Its value lies in its ability to form a very approximate representation of just about any limit set at all including chaoic and non-free examples. It initially starts from 4 fixed points of the limit set plus 30 points selected from the period 4 orbit aba^-1b^-1 repeating, which helpsa little to picture the Jordan curve features of quasi-Fuchsian sets.

Examples
qFstochastic(2,2,10,10,1100,1,0,2); %Apollonian gasket
qFstochastic(2,2,10,10,1100,2,1,2); %As above using the Jorgensen parametrization
Non-parabolic commutators using 3 params
qFstochastic(2,2,10,10,1100,1,2,2,2.1-2i);
Recalculating using an existing matrix
M=qFstochastic(1.91+0.05*1i,1.91+0.05*1i,10,1,1100,1/28,0,2,2-2i,M);

Parameters
A,B are two traces used to generate a conjugacy class of matrices a,b
scope runs 10*scope^2 pseudorandom sequences scope times
rpts adds multiple repeats of the random process
siz (default=1100) is the image size
scal (default=1) scales the image
opt=0 gives standard view, 1 Jorgensen view
3 gives Maskit parametrization. Requires trace of b to be 2
2 gives the double alarm 3 parameters in normal view r this requires tab to be set e.g. using nonfree()
To get the opposite grandma root add 4 to opt
sav=1,3 saves the matrix, and a png file sav>=2 does clf first
tab is an entry for the trace of a*b for option 3
M is a re-input of the output matrix to add further points. If using M as an input parameter you need to include tab=2-2i in the previous parameter for a normal 2-parameter example as the default trace for parabolic commutators.

function tab=nonfree(A,B,opt,scal,tcomm) Generates the trace Tab for a non-free group and allows arbitrary TabAB if tcomm is set to a value.
e.g. tab=nonfree(2,2,0,1/3) % Non-free gasket.
e.g. tab=nonfree(2,2,0,3/2,-1)

function qFmaskit(u,v,K,M,opt,resol,cycs) Does an elementary iteration to define a Maskit parametrized limit set
u,v real and imaginary parameter 1 parameter 2=2
K, M sigmoid division curve slope and exponent
opt=odd draw dividing curve to define iterations
resol gives images resolution cycs no of iterations
e.g. qFmaskit(1.95,0.07,0.2,1.5,1)
e.g. qFmaskit(1.74,0.24,0.28,2.5,1)
e.g. qFmaskit(1.68,0.34,0.2,3.5,1,1000,100)
e.g. qFmaskit(1.6915,5/9+0.0255,0.105,6.2,0,1000,1000)

quasi3d A simple script to make a three dimensional limit set viewable in 3D

2. C Scripts

depthfirst.c   Is designed to make the limit sets accessible for rapid computation on any platform. It is a C-script which performs all the functions of the Matlab function depthfirst.m, which will work freely on any GCC capable platform, including Windows, MacOS, and Linux. It is thus provided as a totally versatile machine-independent route to rapidly generate all the limit sets generated in the Matlab routines. It is approximately 100 times faster than interpreted Matlab and produces a .ppm graphics file of the limit set which can be converted to .png with freely available software.

A variant of this script depthfirstFSA.c is also provided with preset finite state automata to explore the limit sets depicted in fig 26b.

It is designed as a script which has its parameters typed in and is then compiled as a machine code exec using any GCC compiler.
(1)  The script can be edited in any text editor such as Text Edit for Mac or Notepad for Windows.
(2)  To run the script from Mac terminal or any command line tool on Windows or Linux put it in a folder, cd to the folder and input:
        gcc -o depthf depthfirst.c -lm && ./depthf

      To run the same compiled version again type ./depthf
(3) To generate a compact .png version of the .ppm image output file, first make a copy of the .ppm file and call it e.g. "test.ppm"
      Then if you are on a Mac, using High Siera+ you can open it or for earlier OSs use the following command in Terminal: sips -s format png test.ppm --out test.png
      Equivalent (free) converters can be found for Windows or Linux, including Image Magick which has free downloads for each OS.
      There are also many free online converters.

The critical parameters are in the first few lines, as variables used by the script:
double _Complex ta=(csqrt(11)-I)/2, tb=2; // Capital I is used in the place of Matlab i or 1i - e.g 3+4I and complex functional expressions can be used as shown.
int spec=0, altroot=0; //spec=2 non-free group altroot sets which square root for tab
int neck=0;   //to aid drawing large whorls with narrow necks using midpoint
int iterate=-1;   // 0 gives black, n>0 gives the nth iterate -1 gives last iterate (lev)
const int levmax=1000,siz=1100,rangeopt=0;   //range opt sets escape options on range overflow
//1 gives escape 2 gives branch break. For doubly degenerate examples rangeopt = 2 for time efficiency
double ep=0.0001, scal=1;
double _Complex tab;

tracepqr.c Is a script to enable non-Matlab users to find traces for rational examples using an approximate value as a starting point.
It operates in the same way as tracepqr.m and has the same kind of input as above.
double _Complex val=1.92643349-0.02738420i;
int p=143,q=1561,opt=0;
double ep=1e-8;

This corresponds closely to tracepqr.m as demonstrated in the enclosed listing tracepqrtest.
>> v=tracepqr(377,610,0,1.61691788-1.29437374i,1e-8) ;
OK 5 0.000000000065 1.616896678757 -1.294302653720i
Elapsed time is 0.044285 seconds.

double _Complex val=1.61691788-1.29437374i;
int p=377,q=610,opt=0;
MyMac$ gcc -o tracepqr tracepqr.c -lm && ./tracepqr
OK 4 0.000000000065 1.616896678693 -1.294302653724

fareyadd.c is a simple C-script to do Farey addition, as in the above Matlab function.

Three fast C-scripts to generate limit set collections for n = 21, n = 61 and non-free n = 29 used to generate the moving gifs in the web page are also included.

 

3. The MacOS "DFS Viewer" application

The DFS Viewer which is developed directly from the C-script enables the same parameters to be input directly into the graphic interface, and a portrait rapidly generated for viewing, allowing for iterate colouring, standard and non-free examples, setting the levmax for depth and the epsilon for resolution, the specs for avoiding cutting necks, the escape option for degenerate and chaotic groups which may strand the DFS algorithm, a timer to strictly limit the process to a number of seconds, as well as seeking the alternate root in grandma's algorithm if required e.g. in the non-free case.

The Mac app DFS Viewer has a variety of controls to aid successful viewing, most of which are also included as parameters in the C script and Matlab versions:

Ta and Tb set the real and imaginary parts of the two matrix traces, levmax sets an upper limit in the depth search tree, epsilon gives the fineness of the limit set resolution relative to the overall scale used to expand or shrink the image. The timer interrupts the process after a fixed time in seconds the next time it hits levmax, to exit the process if the trace values are super-critical. If only a part of the limit set draws, you need to set the timer for a longer period. Set timer to 0 if you want a high resolution image you know has good traces. Non-free chooses the non-free case discussed below. Necks performs the additional midpoint checks to deal with large narrow-necked fronds as in fig 4, Escape turns on an escape routine if the process begins to go unstable or chaotic. If super-critical values are input the app will then attempt to detect runaway and exit displaying the chaotic iteration up to this point. but can also disrupt depiction of large limit sets. Iterate, if set to a non-zero value n, colours each pixel by the n-th iterate of the four generators – a, b, a-1, b-1. Set to 0 it gives a black and white image, and set to -1 it gives the final level iterate for each pixel. Alt chooses the alternative square root for Tab, which sometimes differs between the Matlab and C versions. If you find you are getting different effectsfor a given set of trace parameters, try choosing alt root, and/or reversing the signs of the real or imaginary parts of the traces.