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