The solve programme takes a finite group presentation, constructs an associated 2-dimensional CW-complex, K, and from K determines a set of matching equations that must be satisfied by a track in K. From the matching equations it calculates a finite set of untwisted tracks that form a basis for the solution space to those equations and evaluates the decomposition of the given group determined by each track in the track basis.
The search programme provides a set of tools that may be used to analyze tracks and patterns in the CW-complex K. This includes evaluating the decomposition of an arbitrary track, splitting patterns into tracks, determining whether a given track is twisted or untwisted, or whether it separates K. A full list of the tools provided by the programme is given below.
The two programmes are available as a source distribution using the following link:
Once you have downloaded and extracted the above file go into the decomp-19-2-17 directory it creates and type './build-progs' (but without the quotes) to build the programmes.
The makefiles used by the build-progs script are based on the gcc compiler and are not sophisticated so should work on most systems.
Here is a sample session that builds the programmes, you should see something like this if all goes well:
[bart@strangeways decomp-19-2-17]$ build-progs g++ -Wall -I ./include -I ./include/solve -g -c src/solve.cpp -o solve-objects/solve.o g++ -Wall -I ./include -I ./include/solve -g -c src/solvefns.cpp -o solve-objects/solvefns.o g++ -Wall -I ./include -I ./include/solve -g -c src/commonfns.cpp -o solve-objects/commonfns.o g++ -Wall -I ./include -I ./include/solve -g -c src/decompose.cpp -o solve-objects/decompose.o g++ -Wall -I ./include -I ./include/solve -g -c src/bigint.cpp -o solve-objects/bigint.o g++ -Wall -I ./include -I ./include/solve -g -c src/n_limit.cpp -o solve-objects/n_limit.o g++ -Wall -I ./include -I ./include/solve -g -c src/util.cpp -o solve-objects/util.o g++ -Wall -I ./include -I ./include/solve -g -c src/debug.cpp -o solve-objects/debug.o g++ -o solve ./solve-objects/solve.o ./solve-objects/solvefns.o ./solve-objects/commonfns.o ./solve-objects/decompose.o ./solve-objects/bigint.o ./solve-objects/n_limit.o ./solve-objects/util.o ./solve-objects/debug.o -lstdc++ g++ -Wall -I ./include -I ./include/search -g -c src/search.cpp -o search-objects/search.o g++ -Wall -I ./include -I ./include/search -g -c src/decompose.cpp -o search-objects/decompose.o g++ -Wall -I ./include -I ./include/search -g -c src/searchfns.cpp -o search-objects/searchfns.o g++ -Wall -I ./include -I ./include/search -g -c src/commonfns.cpp -o search-objects/commonfns.o g++ -Wall -I ./include -I ./include/search -g -c src/util.cpp -o search-objects/util.o g++ -Wall -I ./include -I ./include/search -g -c src/debug.cpp -o search-objects/debug.o g++ -o search ./search-objects/search.o ./search-objects/decompose.o ./search-objects/searchfns.o ./search-objects/commonfns.o ./search-objects/util.o ./search-objects/debug.o -lstdc++ [bart@strangeways decomp-19-2-17]$ ls build-progs fig8 higman4 M21 pretzel search-objects torus clean-search free higman4-subgroup Makefile-search rect2333 solve trefoil clean-solve fundamental-solutions.pdf higman4-subgroup2 Makefile-solve rect3333 solve-objects trg cube higman include manif search src trivial [bart@strangeways decomp-19-2-17]$
As well as the programmes solve and search, together with various files and directories used to build them, as shown above the decomp-19-2-17 directory also contains collection of input files for the solve programme. If you are interested in the source code, it is all in the src and include directories.
These programmes were originally written as part of my D.Phil. research, which was completed in 1987. They have been modified and extended over the years but still retain their original functionality as an option. Originally the solve programme calculated extreme fundamental tracks. These are tracks corresponding to the 1-dimensional faces of the pointed polyhedral convex cone that is the non-negative solution space to the matching equations. Extreme fundamental tracks form a generating set over the positive rationals for this cone. In 2009 the option was added to calculate minimal fundamental solutions, which provide a generating set for the cone over the positive integers. Since the algorithm used for determining minimal fundamental solutions is quite complex, some descriptive notes are supplied in the document fundamental-solutions.pdf.
As shown below there are command line options to enable this legacy functionality but they have only been provided for completeness and as a possible aid to the research of others.
In most cases only the solve programme is required. This programme calculates a basis of untwisted tracks for the solution space to matching system of the cellular 2-complex associated with a group presentation. It then calculates the decomposition of the group given by each basis track and discards any that give obvious trivial decompositions.
The programme reports those basis tracks whose decomposition have not been identified as trivial and writes a transcript that includes the decomposition of each of these tracks into an output file.
If it is required to analyse any tracks associated with the group presentation further, the search programme may be used. This begins by reading the basis tracks reported by the solve programme but allows any other pattern to be specified by the user for analysis.
This programme may be run by typing 'solve' at the command line or by specifying a parameter file 'infile' by typing 'solve infile'.
A parameter file must contain the following information, on separate lines as shown.
jobname number of generators number of relators generator 1 generator 2 ... relator1 relator2 ...
The relators must not contain any spaces but may be separated by an arbitrary number of spaces, or a newline.
Here is an example of the input file for the group presentation
< a b c d : -aba-b-b -bcb-c-c -cdc-d-d -dad-a-a >
higman 4 4 a b c d -aba-b-b -bcb-c-c -cdc-d-d -dad-a-a
Represent inverses of generators by preceeding the character with '-' eg -a, and powers by repetition
We also require that:
Requirements 1 to 5 are essential for running the programme correctly.
The full command line syntax of the solve programme is as follows:
Usage: solve [-#[1|2|3]eEFghO] [input_file]
#[1|2|3]: generate debug output of increasing detail
e: calculate extreme fundamental tracks rather than a track basis.
E: do not calculate extreme fundamental solutions.
F: do not calculate fundamental solutions
g: use original Greenberg algorithm
h: show help information
O: do not use the optimzed search for fundamental solutions
The e, E, F, g, and O options are historical and have only been left in the programme for completeness. If the e option is used the programme evaluates the extreme fundamental tracks of the triangular 2-complex, then goes on to evaluate a set of fundamental solutions to the matching system from these tracks. The F option then allows the calculation to stop after the extreme fundamental solutions have been identified and the E option permits the analysis of a group's cell-complex via the debug capabilitiy without any calculation of extreme fundamental solutions. The O and g options influence the algorithms used in the above calculations.
The solve programme produces a file <jobname>.eft file that is used by the search programme, and a <jobname>-solve-output.txt file that contains transcript of the group presentation analaysis.
This program may be run be typing 'search' at the command line and following the instructions given, or the stub of an .eft file may be entered, as in 'search fred', where fred.eft must exist in the current directory (fred.eft created by running 'solve').
Optionally, the switch '-t' may be used to tell the program not to double up twisted tracks and decompose the double track automatically. The -h option simply repeats this information.
The full command line syntax for the search programme is as follows:
Usage: search [-#[1|2|3]th] [infile]
As with the solve programme the
-#[1|2|3]option may be used to generate debug output of increasing detail.
The search programme anayzes the extreme fundamental tracks in the .eft file and then provides the user with the option to access the following menu:
OPTIONS AVAILABLE A. Evaluate the decomposition given by every track in your-jobname.eft B. Evaluate decomposition given by a single track in your-jobname.eft C. Evaluate decomposition given by a collection of tracks in your-jobname.eft D. Add tracks together E. Evaluate decomposition from a given track F. Decide whether a given N-tuple determines a track G. Split a given pattern into component tracks H. Determine whether a pair of patterns are compatible I. Determine the characteristics of a given track J. Determine the characteristics of every track in your-jobname.eft Q. Quit menu
The search programme produces a file <jobname>-search-output.txt that contains a transcript of the output produced by the programme.