This directory contains data and software to accompany our paper: The Virtual Haken Conjecture: Experiments and Examples, which is available at the arXiv: by Nathan Dunfield and Bill Thurston This directory contains: 1) The GAP code that was used for our computations. These are the files *.gap in this directory. GAP itself can be obtained at . GAP runs under Unix, MacOS, or Windows. Some parts need our stand-alone C programs (provided) and only work under Unix. 2) The manifold data on which the statistics are based. These files are designed to be accessed with the GAP code, but they are also human-readable. The format of these files is described at the top of the file mfld_base.gap. file: manifolds/final.gap has the 10,986 manifolds of the Hodgson-Weeks census. Each comes with a presentation of the fundamental group and a homomorphism to S_n whose kernel has positive betti number. file: manifolds/simple1000.gap has the data about simple covers of degree < 33,000 of 1000 manifolds. These are the manifolds used in the section "Simple Covers". files: manifolds/cusped.gap "rest.gap" contains the closed manifolds in the Hodgson-Weeks omitted from "final.gap". The file "cusped.gap" contains all the orientable cusped manifolds from the SnapPea census. 3) Some statistics extracted from the simple cover data are in the directory "simple_stats", as well as the Python code for generating them. The rest of this document describes the GAP code. First, a word of warning. The code was written under the assumption that we would be the only users. As such, it is not well documented. Moreover, some parts are redundant and others are deprecated and this is not always clearly marked. Moreover some of it (e.g. alternating_reps.gap) will not work because files that it needs are not included in this distribution. Also, some bits related to computing homology require external C programs to be compiled (this will only work under Unix). That having been said, it (hopefully) will still be of some use to others. For more about it's basic capabilities, skip ahead to the sample session below. The main files are: mfld_base.gap Describes the basic manifold data format, code for loading/saving manifolds, and loads all the rest of the code. rigour.gap Contains the code for searching for a cover with positive betti number. The searching is done for positive Z/31991 betti number, but this file also contains code for checking the betti number rigorously. Note: If you make extensive use of the LowIndex search routines, you should compile the GAP library "grpfp.gi". In our experience, this will better than half the running time. quick_rank.gap GAP is quite slow at computing the rank of matrix over a finite field. For this reason, we wrote little C program to do this. This program is my_mat/quick_rank.c Compile it with e.g. "gcc -O2 -o quick_rank quick_rank.c". You will need to do this if you want to use the function "RankMatModP", or anything that uses it (including most of the cover search functions in rigour.gap). If you want to use the simple p-adic method described in the section "Computing the rank over Q", you also need to compile the function NTL/rank.cc. For this you'll need the NTL library . findchars.gap Code used for selecting the subgroup U described in the section "Techniques for computing homology". Actually, we use a family of U rather than a single one as this is more efficient. search.gap Older code for finding covers with positive betti number. Most of it has been superseding by what's in rigour.gap. Also contains the code for extracting the simple group data. The remaining files (fox.gap, group_lib.gap, reps.gap, alternating_reps.gap) are either helper code or, in the case of alternating_reps.gap, non-functional. ------------------------------------------------------------------------ Sample Session: # Load the software. Note the ";;" on the second line is important, # otherwise GAP will print 11,000+ manifolds to your screen! gap> Read("mfld_base.gap"); gap> FM := LoadManifolds("final.gap");; # Look at a manifold gap> FM[1]; rec( Name := "m003(-3,1)", Volume := "0.942707", Homology := [ 5, 5 ], KnownPosBettiCover := true, GoodCover := [ "PSL2", 19 ], Reason := "AbelianInvariants", Group := function( ) ... end, KnownWeakPosBettiCover := true, GoodCoverImage := [ ( 2,12,11, 5, 7,20, 8, 4,13)( 3, 6,10,15,16, 9,19,17,14) , ( 1, 7,14,16, 5, 2, 3, 6, 9)( 4,10,18,12,20, 8,19,15,11) ], Degree := 20, Rank := 2, GoodCoverImageU := [ ( 2,11,12, 6,13, 9, 7,17,14,19,10, 5, 8,16,18, 4,15, 3, 20), ( 3,15, 9)( 4,16,10)( 5,17,11)( 6,18,12)( 7,19,13)( 8,20,14), ( 3,19,17,15,13,11, 9, 7, 5)( 4,20,18,16,14,12,10, 8, 6) ] ) # Can also pull up a manifold by name gap> M := GetManifold(FM, "m007(3,1)"); rec( Name := "m007(3,1)", Volume := "1.014942", Homology := [ 3, 6 ], KnownPosBettiCover := true, GoodCover := [ "p-group", [ 3, 2 ] ], Reason := "AbelianInvariants", Group := function( ) ... end, KnownWeakPosBettiCover := true, GoodCoverImage := [ (1,4,7)(2,5,8)(3,6,9), (4,6,5)(7,8,9) ], GoodCoverImageU := [ (1,7,5)(2,8,6)(3,9,4) ], Degree := 9, Rank := 2 ) # Here's it's fundamental group gap> G := M.Group(); gap> GeneratorsOfGroup(G); [ a, b ] gap> RelatorsOfFpGroup(G); [ a^2*b^2*a^-1*b^-1*a^-1*b^2, a*b^-1*a*b^-1*a*b*a^3*b ] # Here's how to look for covers with positive betti number. # IMPORTANT NOTE: For this to work you need to compile # the add on program my_mat/quick_rank.c as describe above # in the description of the file quick_rank.gap # Select 4 test manifolds to play with. gap> TestM := FM{[1..4]};; # Need to clear the data about the covers we found or else the search # routines will just ignore the manifolds, thinking (correctly) that # there's nothing to do. gap> for M in TestM do ClearCoverData(M); od; gap> TestM; [ rec( Name := "m003(-3,1)", Volume := "0.942707", Homology := [ 5, 5 ], KnownPosBettiCover := false, GoodCover := false, Reason := false, Group := function( ) ... end, KnownWeakPosBettiCover := false, GoodCoverImage := [ ], Degree := false, Rank := false ), ... GoodCoverImage := [ ], Degree := false, Rank := false ) ] # First let's try abelian covers. gap> for M in TestM do SearchForAbelianCover(M); od; m003(-3,1) # Prints manifold name, but no further m003(-2,3) # output because none of these have positive m007(3,1) # betti number. m003(-4,3) # Now, let's check subgroups of index at most 6 (and the largest # normal subgroups contained in them). gap> for M in TestM do SearchForLowIndexCover(M,6); od; ... m007(3,1) [ 1, 2, 3, 3, 3, 3, 5, 6, 6, 6, 6 ] # Indices of subgroups [ 1, 2, 3, 3, 3, 3, 6, 6, 6, 6, 10 ] # Size of max. normal subgp contained # in initial subgroup 4 subgroups of index # Info on subgroups of size 10 quotient [ 1, 2, 5, 10 ] # used to chosing U to test for Reduced to indices [ 5, 2 ] # that group. ... # Turns out the subgroups of index 7 and 8 don't find anything, either, # so let's look at index 9. (Note: For n > 6, SearchForLowIndexCover(M,n) # checks only those subgroups on index _exactly_ n not index <= n. ) gap> for M in TestM do SearchForLowIndexCover(M,9); od; ... m007(3,1) [ 9, 9, 9, 9, 9 ] [ 9, 27, 27, 27, 27 ] 6 subgroups of index [ 1, 3, 3, 3, 3, 9 ] Reduced to indices [ 3, 3, 3, 3 ] 11 subgroups of index [ 1, 3, 3, 3, 3, 9, 9, 9, 9, 9, 27 ] Reduced to indices [ 9, 3, 3, 3 ] Success at index 9 ... # So we found a good cover for m007(3,1). Let's look at it gap> TestM[3]; rec( Name := "m007(3,1)", Volume := "1.014942", Homology := [ 3, 6 ], KnownPosBettiCover := false, GoodCover := [ "LowIndex", 9 ], Reason := false, Group := function( ) ... end, KnownWeakPosBettiCover := true, GoodCoverImage := [ (2,3,5)(4,7,6), (1,2,4)(3,6,8)(5,7,9) ], Degree := 9, Rank := false, GoodCoverImageU := [ (1,5,4)(2,6,8)(3,7,9) ] ) # All the search functions only look for a cover with positive finite # field betti number. That's why KnownWeakPosBettiCover := true but # KnownPosBettiCover := false. We can check this cover rigorously # using GAP's built in Abelian Invariants function gap> CheckHomologyWithAbelianInvariants(TestM[3]); m007(3,1) [ "LowIndex", 9 ] 9 9 2 27 # No error reported means the Q betti num is > 0. # 9 is the degree of the cover, i.e. [Q : U]. # 2 is the rank of the homology of the cover, and # 27 is the order of the quotient Q. # Let's attack the rest, looking at PSL(2,p) covers gap> for M in TestM do SearchForPSL2Cover(M, 13); od; ... m003(-2,3) looking for quotient of order 1092 16 subgroups of index [ 1, 14, 28, 42, 78, 84, 91, 91, 156, 182, 182, 182, 273, 364, 546, 1092 ] Reduced to indices [ 84, 78 ] Success at index 14 ... # GAP has a build in library of perfect groups of order < 10^6 # Lets try some of them gap> idents := Filtered(SizeNumbersPerfectGroups(), x -> x[1] < 1000 ); [ [ 60, 1 ], [ 120, 1 ], [ 168, 1 ], [ 336, 1 ], [ 360, 1 ], [ 504, 1 ], [ 660, 1 ], [ 720, 1 ], [ 960, 1 ], [ 960, 2 ], [ 1080, 1 ], [ 1092, 1 ] ] # Which groups are these? (Note: the IsPermGroup isn't important # here, but other times it can be crucial because many of GAP's # algorithms are efficient only for Permutation Groups) gap> List(idents, i -> PerfectGroup(IsPermGroup, i)); [ A5, A5 2^1, L3(2), L3(2) 2^1 = SL(2,7), A6, L2(8), L2(11), A6 2^1, A5 2^4, A5 2^4' ] # Now let's use these: gap> for ind in idents do > for M in TestM do > SearchForPerfectCover(M, ind); > od; > od; m003(-3,1) looking for quotient of order 60 ... m003(-3,1) looking for quotient of order 168 15 subgroups of index [ 1, 7, 7, 8, 14, 14, 21, 24, 28, 42, 42, 42, 56, 84, 168 ] Reduced to indices [ 42 ] m003(-4,3) looking for quotient of order 168 m003(-3,1) looking for quotient of order 336 19 subgroups of index [ 1, 7, 7, 8, 14, 14, 16, 21, 24, 28, 42, 42, 42, 48, 56, 84, 112, 168, 336 ] Reduced to indices [ 112 ] Success at index 48 m003(-4,3) looking for quotient of order 336 ... m003(-4,3) looking for quotient of order 960 # Let's see how we're doing: gap> Length(ManifoldsAlmostDone(TestM)); # Almost done means except 3 # for checking the betti num # over Q # Just this guy left: gap> ManifoldsNotAlmostDone(TestM); [ rec( Name := "m003(-4,3)", Volume := "1.263709", Homology := [ 5, 5 ], KnownPosBettiCover := false, GoodCover := false, Reason := false, Group := function( ) ... end, KnownWeakPosBettiCover := false, GoodCoverImage := [ ], Degree := false, Rank := false ) ] # Lets try another PSL2 cover gap> for M in TestM do SearchForPSL2Cover(M, 16); od; m003(-4,3) looking for quotient of order 4080 21 subgroups of index [ 1, 17, 51, 68, 85, 120, 136, 240, 255, 272, 340, 408, 510, 680, 816, 1020, 1020, 1020, 1360, 2040, 4080 ] Reduced to indices [ 240, 17 ] Success at index 51 # Now lets finish off and check the homology rigorously gap> for M in TestM do CheckHomologyWithAbelianInvariants(M); od; m003(-3,1) [ "Perfect", [ 336, 1 ], "L3(2) 2^1 = SL(2,7)" ] 48 48 4 336 m003(-2,3) [ "PSL2", 13 ] 14 14 1 1092 m003(-4,3) [ "PSL2", 16 ] 51 51 2 4080 # Now we're done! gap> ManifoldsWithoutPosBettiCovers(TestM); [ ] # Of course, none what we've done uses that these are 3-manifold # groups, so here's how we can apply this to an arbitrary group. # # First lets create some groups gap> F := FreeGroup("a", "b"); gap> a := F.1;; b := F.2;; gap> G1 := F/[a^2, b^3, (a*b)^7]; gap> G2 := F/[a^2, b^5, (a*b)^5]; # Now lets create manifolds from them gap> M1 := CreateManifoldFromGroup("(2,3,7)", G1); rec( Name := "(2,3,7)", Homology := [ ], Group := function( ) ... end, KnownPosBettiCover := false, KnownWeakPosBettiCover := false, GoodCover := false, GoodCoverImage := [ ], Reason := false, Degree := 0, Rank := 0 ) gap> M2 := CreateManifoldFromGroup("(2,5,5)", G2);; gap> NewM := [M1, M2];; # First, save these manifolds for future use SaveManifolds("tri_gps", NewM); # Now lets show they have virtual positive betti number, by looking at # all the PSL(2, q) covers where q is a prime power < 16 gap> for p in Filtered([5..15], IsPrimePowerInt) do > for M in NewM do > SearchForPSL2Cover(M, p); > od; > od; (2,3,7) looking for quotient of order 60 (2,5,5) looking for quotient of order 60 9 subgroups of index [ 1, 5, 6, 10, 12, 15, 20, 30, 60 ] Reduced to indices [ 12, 5 ] Success at index 5 (2,3,7) looking for quotient of order 168 15 subgroups of index [ 1, 7, 7, 8, 14, 14, 21, 24, 28, 42, 42, 42, 56, 84, 168 ] Reduced to indices [ 42 ] Success at index 42 # Check the homology, just in case you don't believe that triangle # orbifolds are finitely covered by surfaces... ;-) gap> for M in NewM do CheckHomologyWithAbelianInvariants(M); od; (2,3,7) [ "PSL2", 7 ] 42 42 2 168 (2,5,5) [ "PSL2", 5 ] 5 5 2 60 # Save the manifolds again, and go home. SaveManifolds("tri_gps", NewM); # End of sample session. # # Comments: There are several more Search* functions --- see # rigour.gap for more. # Snapshot of date: Tue Sep 17 17:14:07 EDT 2002