Horseshoe Utilities

This page contains some programs related to the paper The forcing relation for horseshoe braid types, by André de Carvalho and Toby Hall. The programs are:
 

• prefix: Gives the symbolic prefix corresponding to a rational between 0 and 1/2
• parse: Parses a periodic orbit of the horseshoe into its prefix and decoration
• predec: Constructs horseshoe orbits with given prefix and decoration, if compatible
• qw: Gives the supremum of the heights compatible with a given decoration
• top: Finds the topological train track type corresponding to a given decoration
• checkconj: Looks for counterexamples to Conjecture 1 in the paper

The programs are not very robust, and are liable to crash if they're given meaningless data.
 

To install the programs, download the files  hs.tar  (242K) and  install (148 bytes) into a common (and otherwise empty) directory, and then type sh install. If all goes well, a subdirectory called hs will be created, containing the six executables. Please let me know if there are any problems with this. Alternatively, if you have a PC you can download hs.zip (503K), which contains DOS executables.

prefix

parse

predec

These are the four periodic orbits with height 2/7 and decoration 101 (they all have the same braid type). If the height is equal to the supremum compatible with the decoration, there may be fewer than four orbits of the given height and decoration:

predec 1/3 1001
1001110010

If the height is greater than this supremum, there are no horseshoe orbits with the given height and decoration:

predec 2/5 1001
Prefix and decoration incompatible

To decide what the supremum is, use the qw program

Use 'e' and '*' to denote the empty and length -1 decorations respectively:

predec 2/7 e
1001100100
1001100101
1001100110
1001100111
predec 2/5 *
1011010
1011011
 
 

qw

qw 1001
1/3
qw 1011
2/5
qw e
1/3
qw *
1/2

top

top 1
1 2 2 3 4 * 4 5 5 3 1
1 -> 1 2 2 3
2 -> 4
3 -> 5 5 3
4 -> 1
5 -> 2
 
 

This is the topological train track type of the decoration 1, in the notation described in section 3.3 of the paper. For convenience, a * is placed at the end of the "final" edge (the one which maps over the initial edge).

The program is based on the assumption that conjecture 1 is correct. It works as follows: first qw is calculated for the given decoration, and then the orbit P_{1/n}^w is constructed, where n is least such that 1/n<qw. The train track solver is run on this orbit, and the result converted to a topological train track type. Please note the following:

• Since a train track has to be calculated, the program may take some time to run for longer decorations.
• As explained in the paper, there is not a unique train track in a given isotopy class. The program does all it can to ensure that all vertices of valence n>=3 correspond to n-pronged singularities of the invariant foliations of the pseudo-Anosov in the isotopy class, but it may fail in some instances: this will result in the topological train track having spurious edges and vertices. Fortunately this failure is easy to detect using Euler characteristic considerations, and the program will report it with suitable apologies. This doesn't happen for any decorations of length 8 or less.
• To get the topological train track type of the homoclinic orbit P_0^w (as shown in Table 1 in the paper), prefix the image of edge 1 with whatever symbols are necessary to make it an initial subword of the string describing the track. For example:

 

top 11
1 2 2 3 3 4 * 4 5 5 1
1 -> 2 2 3 3
2 -> 4
3 -> 5
4 -> 1
5 -> 2

The homoclinic orbit has 1 -> 1 2 2 3 3.

checkconj

The command checkconj verb mindec maxdec minden maxden, where all the parameters are non-negative integers, considers all horseshoe orbits whose decoration w has length between mindec and maxdec (inclusive), and whose height q<qw has denominator between minden and maxden (inclusive). It calculates a train track for each orbit, and checks the following:

1. That each orbit is of pseudo-Anosov type
2. That all orbits with a given decoration w have the same topological train track type
3. That for each w, the entropy of the orbits P_q^w decreases as q increases
4. That for each w and each q<qw, the two orbits P_q^w with 0 and 1 before the decoration have the same entropy

The program reports any violations of these conditions as they are found, and at its termination reports if no violations were found. Since it can take several hours to run when long decorations are considered, the verb parameter allows you to specify what additional information will be displayed: this can give reassurance that something is happening. The options are:

verb = 0: No intermediate output
verb = 1: Outputs Length n when it starts to consider decorations of length n
verb = 2: Also outputs Decoration w when it starts to consider the decoration w
verb = 3: Also outputs the code of each orbit, and its height, as it is considered
verb = 4: Also outputs the growth rate and the topological train track type (in the format produced by top) of each orbit
verb = 5: Also writes each decoration w to standard error as it is considered. On our machine, this means we get to see this progress information on the screen when we redirect program output to a file.

Thus, for example, checkconj 5 3 3 3 10 > l3.txt runs through all orbits with decorations of length 3 and height with denominator between 3 and 10. It writes each of the 8 decorations to standard error as it considers them, and puts verbose output in the file l3.txt . A total of 156 train tracks are calculated by this command.

If any violations are detected, the output messages are preceded by !! - this makes it easy to track them down in large output files.

We have used this program to check all orbits with decorations of length 8 or less, and heights with denominator less than or equal to 10. A total of 15566 orbits fit these criteria. We would be grateful to hear from anyone with a fast enough machine and enough time on their hands to extend the range of these checks.

Please note the following:

• A report of a potential counterexample should not be taken as meaning that there is definitely a counterexample. As described under top above, the program is not always successful in eliminating all spurious vertices and edges from a topological train track: this is more likely to be a problem with checkconj than with top, since top has the freedom to adjust the height in an attempt to get a better answer. As with top, the program reports if any spurious topological train track types are detected using Euler characteristic considerations. Regrettably, such orbits must be considered by hand. Up to decorations of length 8, this problem arises for exactly two orbits, namely those with codes 10010110101010 and 10010110111010. The correct topological train track types can be determined fairly easily in these two cases (in fact the two orbits have the same braid type), and can be shown to agree with those of other orbits with the same decorations. A rather more unlikely possibility is that floating point error could cause the program to report that entropies aren't decreasing with increasing height, or that the two orbits with the same height and decoration have distinct entropies. Such cases could be checked using the second author's train track program, with increased tolerance and precision parameters. This program can be downloaded  here
• When extending the range of heights to be considered, you should make sure the new denominator range overlaps with the range you have previously tested: otherwise, it's possible that a particular decoration has two types of topological train track, one for low denominators and one for high denominators. For example, if you've run checkconj 5 3 3 3 10 and want to extend the range of denominators considered up to 20, you should run checkconj 5 3 3 10 20 rather than checkconj 5 3 3 11 20.
• If anyone wants to fiddle around with the code, I apologise for its quality. It's a combination of very old, quite old, and recent routines.