Low Dimensional Topology

April 23, 2013

When are two hyperbolic 3-manifolds homeomorphic?

Filed under: 3-manifolds,Computation and experiment,Hyperbolic geometry — Henry Wilton @ 7:46 am

A preprint of Lins and Lins appeared on the arXiv today, posing a challenge [LL].  In this post, I’m going to discuss that challenge, and describe a recent algorithm of Scott–Short [SS] which may point towards an answer.

The Lins–Lins challenge

The theory of 3-manifolds is now very advanced, and we can even say in a certain sense that we understand ‘all’ 3-manifolds (as I discussed in an earlier post).  But that understanding is very theoretical; the Lins–Lins challenge is to put this theory into practice.

They ask: ‘Are the two closed, hyperbolic 3-manifolds given by Dehn surgery on the following two framed links homeomorphic?’

Lins-Lins manifolds

(I’ve taken the liberty of copying the diagrams from their paper.)

The two manifolds are both hyperbolic, and calculations have been unable to distinguish their volumes or Witten–Reshetiken–Turaev invariants, up to many decimal places.  On the other hand, Lins–Lins’s techniques for finding homeomorphisms have also failed.  They (rather optimistically, in my opinion) bet that the failure of their techniques indicates that these manifolds really aren’t homeomorphic, and challenge the broader 3-manifold and combinatorial group theory communities to resolve the question.

They also note that, by Mostow Rigidity, we may equivalently try to determine whether or not the fundamental groups are isomorphic. They helpfully provide presentations.

Lins-Lins groups

(Again, I’ve copied this straight from their paper.)

There are some obvious things that one might attempt and which they don’t mention, such as computing the homology of the small-index subgroups of these groups.  Presumably they forgot to mention this, but it might be worth a try if anyone has any spare time.

(Added: This was a good idea! Nathan Dunfield did exactly this (see the comments below) and found that $G_1$ has a subgroup of index six with infinite abelianization, whereas $G_2$ does not. Readers are also referred to Nathan’s comments on the usefulness of SnapPea for this sort of problem.)

Regardless of the difficulty of this specific question, their broader complaint is valid.  Although we know that the homeomorphism problem for hyperbolic 3-manifolds (and, more generally, for all 3-manifolds) is solvable in theory by a remarkable algorithm of Sela, it has never been practical to even think about implementing that algorithm [S].

Aside: Sela’s algorithm

Sela’s algorithm is a tour de force; it solves the isomorphism problem for all ‘rigid’ torsion-free word-hyperbolic groups and, in fact, with rather more work, for all word-hyperbolic groups [DGu] and even all toral relatively hyperbolic groups [DGr].  But this very generality makes it daunting to think about implementing in practice.  One of the bounds is obtained from a classic Sela-style argument by contradiction on a limiting R-tree, so we get no control over this term. To add to the difficulty, the proof reduces the calculation to a set of equations and inequations over a non-abelian free group, which can be solved by Makanin’s algorithm [Mak]. Implementing Makanin’s algorithm is itself a highly non-trivial task.

The Scott–Short algorithm

I want to spend the rest of this post describing a remarkable recent observation of Scott–Short, which deserves to be much better known [SS].  They have a described a completely new solution to the homeomorphism problem for hyperbolic 3-manifolds, which relies solely on the geometry of hyperbolic 3-space. Their algorithm is technically much simpler than Sela’s, and huge credit must go to them for finding a better way of doing things.

Although I don’t for a moment think that their algorithm would be efficient as it stands, its simplicity and geometric nature bring the problem within reach.  Anyone with a working knowledge of hyperbolic geometry can understand it, which means that anyone can think about ways to improve it. Also, it has the huge advantage that it reduces the problem to calculations over the complex numbers,  rather than free groups.

Suppose we are given closed, orientable, hyperbolic manifolds $M_1$ and $M_2$ that we want to identify or distinguish. The starting point for Scott–Short is an algorithm of Manning (originally described by Casson) [Man], which constructs a fundamental domain $P_i$ in hyperbolic 3-space, together with side-pairing isometries $\{g_k^{(i)}\}$, for the manifold $M_i$. By Mostow Rigidity, we need to determine whether or not the subgroups

$G_i=\langle g_k^{(i)}\rangle \subseteq P⁢S⁢L_2⁢(\mathbb{C})$

are conjugate.

In practice, the fundamental domain and the side pairings are the sort of information that one usually already has about a given hyperbolic 3-manifold, so one shouldn’t need to implement Manning’s algorithm.  Perhaps an expert can tell me whether or not Snappea provides this information?  (It’s fine to go through non-exact computations like Snappea. If a candidate isomorphism is found, it’s easy to confirm whether or not it’s genuine; likewise, non-exact estimates are fine to compute the bounds we would need for a proof of non-isomorphism.)

Deciding whether or not two finite subsets of $PSL_2(\mathbb{C})$ are conjugate is just a matter of solving a system of equations over $\mathbb{C}$, which is relatively straightforward.  The difficulty arises because, even if $G_1$ and $G_2$ are isomorphic, the generating sets we have been given may be very different. Therefore, a priori, wenhave infinitely many different possible conjugacies to check.

Scott and Short use the geometry of the fundamental domains $P_i$ to reduce this to a finite number.  They define the n-star of $P_i$ to be the union of the translates of $P_i$ by the elements of word length at most n in $G_i$.  That is, in the tiling of hyperbolic 3-space by copies of $P_i$ it’s the set of tiles that are at most n steps away from $P_i$ itself.

They observe that, for any r, we can compute an n so that the metric ball of radius r around $P_1$ is contained in the n-star of $P_2$.  Since

$g_k^{(1)}⁢P_1\subseteq B⁢(P_1,\mathrm{diam}⁢P_1)$

for any k, it follows that we can compute an n so that the $g_k^{(1)}$ are all contained in the ball of diameter n in the word metric on $G_2$. We can then do the same thing the other way round, which reduces the problem to a finite computation as advertised, and we are done!

I recommend the Scott–Short paper, which is very readable.  It seems likely to me that an improvement of their algorithm, although it would no doubt be very slow on worst-case input, might well be effective enough to resolve questions like the Lins–Lins challenge. So I’ll finish with a challenge of my own.

Challenge:  Try to implement the Scott–Short algorithm!  Find ways to improve it!

Bibliography

[DGr] Dahmani, Groves, ‘The isomorphism problem for toral relatively hyperbolic groups’, Publ. Math. Inst. Hautes Études Sci. No. 107 (2008), 211–290.

[DGu] Dahmani, Guirardel, ‘The isomorphism problem for all hyperbolic groups’, Geom. Funct. Anal. 21 (2011), no. 2, 223–300.

[LL] Lins, Lins, ‘A challenge to 3-manifold topologists and group algebraists’, arXiv:1304.5964v1

[Mak] Makanin, ‘Decidability of universal and positive theories of a free group,’ (English translation) Mathematics of the USSR-Izvestiya 25 (1985), 75–88; original: Izvestiya Akademii Nauk SSSR, Seriya Matematicheskaya 48 (1984), 735–749.

[Man] Manning,  ‘Algorithmic detection and description of hyperbolic structures on closed 3-manifolds with solvable word problem’, Geom. Topol. 6 (2002), 1–25

[SS] Scott, Short, ‘The homeomorphism problem for closed 3-manifolds’, arXiv:1211.0264v1

[S] Sela, ‘The isomorphism problem for hyperbolic groups. I’, Ann. of Math. (2) 141 (1995), no. 2, 217–283.

About these ads

56 Comments »

  1. The presentations they give on the second page seem to come from distinct groups: the first has no subgroups of index 5 and the second does.

    That seems too easy, though, so maybe I made a mistake in entering them, or maybe there’s a typo in [LL]. Below is my GAP code.

    The reason I didn’t work directly from the surgery presentation within SnapPy (which is surely more reliable) is that I didn’t want to have figure out how the blackboard framing relates to the standard one.

    F1 := FreeGroup(“a”, “b”, “c”, “d”, “e”, “f”, “g”, “h”, “i”);
    a := F1.1; b := F1.2; c := F1.3; d := F1.4; e := F1.5; f := F1.6; g := F1.7; h := F1.8; i := F1.9;
    rels1 := [e*f*(f*a)^(-1), d*a*(a*e)^(-1), b*g*(g*a)^(-1), d*b*(b*c)^(-1),
    c*h*(h*b)^(-1), i*c*(c*h)^(-1), f*e*(e*i)^(-1), f*d*(d*g)^(-1),
    g*i*(i*h)^(-1), g^(-1)*h^(-1)*b^(-1)*a*f, d^(-1)*i^(-1)*c^(-1)*e];
    G1 := SimplifiedFpGroup(F1/rels1);

    F2 := FreeGroup(“j”, “k”, “l”, “m”, “n”, “o”, “p”, “q”, “r”);
    j := F2.1; k := F2.2; l := F2.3; m := F2.4; n := F2.5; o := F2.6; p := F2.7; q := F2.8; r := F2.9;
    rels2 := [o*m*(m*j)^(-1), r*j*(j*p)^(-1), (n*p)*(p*o)^(-1), q*l*(l*p)^(-1), (l*q)*(q*k)^(-1),
    q*n*(n*r)^(-1), j*r*(r*k)^(-1), l*o*(o*m)^-1, m*k*(k*n)^-1, r*q^(-1)*o*k*p*m, l^(-1)*n*j];
    G2 := SimplifiedFpGroup(F2/rels2);

    Print( Length(LowIndexSubgroupsFpGroup(G1, 5)), ” “, Length(LowIndexSubgroupsFpGroup(G2, 5)));

    Comment by Nathan Dunfield — April 23, 2013 @ 10:26 am | Reply

    • Hi Nathan, well done for doing this! I haven’t yet had time to check for typos. Just to be clear, when I run your GAP code, I seem to get one subgroup of index 5 for G1 and two for G2. I also get that G1 has one subgroup of index 6 whereas G2 has five.

      Comment by Henry Wilton — April 23, 2013 @ 10:49 am | Reply

      • Henry, GAP’s convention is that the LowIndexSubFpGp(G, n) function returns all subgroups of index *at most* n. For example:

        gap> List(LowIndexSubgroupsFpGroup(G2, 6), H -> Index(G2, H));
        [ 1, 6, 5, 6, 6 ]

        The trivial subgroup is included, which is why in my example coded it finds one subgroup for G1 and two for G2.

        Comment by Nathan Dunfield — April 23, 2013 @ 11:58 am

      • Ah, right… my GAP is a little rusty. Thanks, Nathan.

        Comment by Henry Wilton — April 23, 2013 @ 12:12 pm

  2. I should say that, in my experience, using (properties of) low-index subgroups is an excellent way to rigorously tell reasonably sized hyperbolic manifolds apart.

    Comment by Nathan Dunfield — April 23, 2013 @ 10:29 am | Reply

    • I did think it was odd that they didn’t mention this technique in their paper. I suppose the next step, after checking for typos, is to check their presentations with Snappea. (I’ve never used Snappea in anger, so I’ll definitely leave this to someone else.) In any case, as I hope I make clear, I think that there are good reasons to be interested in Scott and Short’s algorithm, independently of the Lins–Lins example(s).

      Comment by Henry Wilton — April 23, 2013 @ 10:52 am | Reply

      • I wrote the authors of [LL] as to what the volume of the manifold is. That should make it easy to convert from blackboard framing to homological framing, the latter of which is what’s used by SnapPea.

        Initially, I thought they used homological framing which also resulted in distinct manifolds with the same volume, thought the particular subgroup check was different.

        Comment by Nathan Dunfield — April 23, 2013 @ 12:05 pm

  3. Some more general comments:

    For hyperbolic manifolds of this size SnapPea can effectively decide whether two are homeomorphic, see here for details

    http://projecteuclid.org/euclid.em/1048515809

    Even ignoring round-off error, which hasn’t been analyzed, I’m not sure the algorithm used in the cusped case is guaranteed to terminate, much less work. However, it always does so for examples of this size.

    In general, when SnapPea says two manifolds are homeomorphic, it means that it has found combinatorially isomorphic triangulations of the input manifolds, and so that direction is rigorous. If instead it reports that they are not homeomorphic then you have to take this with a grain of salt. (For example there are potential numerical issues that would result in “identifying” the wrong triangulation as the Epstein-Penter one.) However, I have always found it very easy to certify that manifolds manifolds are distinct by looking at their first few finite-index subgroups and their properties.

    Comment by Nathan Dunfield — April 23, 2013 @ 12:21 pm | Reply

  4. So it seems the presentation for the first group G1 in [LL] is messed up; In particular, the three relations in the last row of the left part of Figure 2 are backwards. With this corrected, both groups have subgroups of index 5. However, all is not lost: G1 has an index 6 subgroup with infinite abelianization whereas G2 does not.

    Comment by Nathan Dunfield — April 23, 2013 @ 9:25 pm | Reply

  5. I managed to dust off my GAP installation and replicate Nathan’s result. Apparently, the Lins–Lins challenge wasn’t so hard after all. Still, I hope that readers will still be encouraged to take a look at the Scott–Short algorithm. I think it’s a great development.

    Comment by Henry Wilton — April 24, 2013 @ 9:41 am | Reply

    • For those interested, here is the updated sample code. Only rels1 differs from Nathan’s original post, and Lins-Lins’ revision posted today is consistent with Nathan’s comments.

      F1 := FreeGroup(“a”, “b”, “c”, “d”, “e”, “f”, “g”, “h”, “i”);

      a := F1.1; b := F1.2; c := F1.3; d := F1.4; e := F1.5; f := F1.6; g := F1.7; h := F1.8; i := F1.9;

      rels1:= [e*f*(f*a)^(-1),d*a*(a*e)^(-1), b*g*(g*a)^(-1), d*b*(b*c)^(-1),
      c*h*(h*b)^(-1), i*c*(c*h)^(-1),i*e*(e*f)^(-1),g*d*(d*f)^(-1),h*i*(i*g)^(-1), g^(-1)*h^(-1)*b^(-1)*a*f, d^(-1)*i^(-1)*c^(-1)*e];

      G1 := SimplifiedFpGroup(F1/rels1);

      F2 := FreeGroup(“j”, “k”, “l”, “m”, “n”, “o”, “p”, “q”, “r”);

      j := F2.1; k := F2.2; l := F2.3; m := F2.4; n := F2.5; o := F2.6; p := F2.7; q := F2.8; r := F2.9;

      rels2 := [o*m*(m*j)^(-1), r*j*(j*p)^(-1), (n*p)*(p*o)^(-1), q*l*(l*p)^(-1), (l*q)*(q*k)^(-1),
      q*n*(n*r)^(-1), j*r*(r*k)^(-1), l*o*(o*m)^-1, m*k*(k*n)^-1, r*q^(-1)*o*k*p*m, l^(-1)*n*j];

      G2 := SimplifiedFpGroup(F2/rels2);

      L1 := LowIndexSubgroupsFpGroup(G1, 6);
      L2 := LowIndexSubgroupsFpGroup(G2, 6);

      List(L1, H -> [Index(G1, H), AbelianInvariants(H)]);
      #OUTPUT from GAP:
      #[ [ 1, [ ] ], [ 6, [ 0, 2, 4 ] ], [ 5, [ 3, 3 ] ], [ 6, [ 0 ] ], [ 6, [ 0, 2, 4 ] ] ]
      List(L2, H -> [Index(G2, H), AbelianInvariants(H)]);
      # OUTPUT from GAP:
      #[ [ 1, [ ] ], [ 6, [ 2, 3 ] ], [ 5, [ 3, 3 ] ], [ 6, [ 2, 3, 4, 16 ] ], [ 6, [ 2, 3, 4, 16 ] ] ]

      As Nathan points out the homologies of the index 6 covers distinguish the manifolds in question. (Also, if copying and pasting this code into gap check that the ” symbol copies as an ASCII character.)

      Comment by Neil Hoffman — April 26, 2013 @ 4:48 am | Reply

      • Thanks, Neil!

        As Neil mentions, Lins–Lins have posted an updated preprint with a second pair of manifolds to distinguish. The same technique seem to work, in the same way. They interpret this as a vindication of an algorithm described in Gems, Computers, and Attractors for 3-Manifolds by S. Lins (World Scientific, 1995).

        For the record, here’s my GAP code.

        F3 := FreeGroup(“a”, “b”, “c”, “d”, “e”, “f”, “g”, “h”, “i”);
        a := F3.1; b := F3.2; c := F3.3; d := F3.4; e := F3.5; f := F3.6; g := F3.7; h := F3.8; i := F3.9;

        rels3:= [ (f*a)^(-1)*e*f , d*a*(a*e)^(-1), b*g*(g*a)^(-1) , d*b*(b*c)^(-1), c*h*(h*b)^(-1) , i*c*(c*h)^(-1), i*e*(e*f)^(-1), g*d*(d*f)^(-1) , h*i*(i*g)^(-1), g^(-1)*h^(-1)*b^(-1)*a*f, d^(-1)*i^(-1)*c^(-1)*e];

        G3 := SimplifiedFpGroup(F3/rels3);

        F4 := FreeGroup(“j”, “k”, “l”, “m”, “n”, “o”, “p”, “q”, “r”);
        j := F4.1; k := F4.2; l := F4.3; m := F4.4; n := F4.5; o := F4.6; p := F4.7; q := F4.8; r := F4.9;

        rels4 := [ o*m*(m*j)^(-1), r*j*(j*p)^(-1), n*p*(p*o)^(-1), q*l*(l*p)^(-1), l*q*(q*k)^(-1), q*n*(n*r)^(-1), j*r*(r*k)^(-1), l*o*(o*m)^(-1), m*k*(k*n)^(-1), r*q^(-1)*o*k*p*m, l^(-1)*n*j];

        G4 := SimplifiedFpGroup(F4/rels4);

        L3 := LowIndexSubgroupsFpGroup(G3, 6);
L4 := LowIndexSubgroupsFpGroup(G4, 6);

        List(L3, H -> [Index(G3, H), AbelianInvariants(H)]);
        # GAP OUTPUT: [ [ 1, [ ] ], [ 6, [ 0, 2, 4 ] ], [ 5, [ 3, 3 ] ], [ 6, [ 0 ] ], [ 6, [ 0, 2, 4 ] ] ]

        List(L4, H -> [Index(G4, H), AbelianInvariants(H)]);
        # GAP OUTPUT: [ [ 1, [ ] ], [ 6, [ 2, 3 ] ], [ 5, [ 3, 3 ] ], [ 6, [ 2, 3, 4, 16 ] ], [ 6, [ 2, 3, 4, 16 ] ] ]

        Comment by Henry Wilton — April 26, 2013 @ 7:20 am

  6. Do Lins and Lins read this blog? At least there’s now the third version of their note on the arxiv, with no reference to the fact that their initial question has been answered.

    Comment by Stefan Friedl — April 30, 2013 @ 3:18 pm | Reply

    • I don’t know if they read it; certainly I contacted them directly with the info I posted here and they wrote back with the second challenge problem.

      Comment by Nathan Dunfield — April 30, 2013 @ 7:47 pm | Reply

  7. This is Sóstenes.

    The discussion was based on old versions of the Challenge paper
    which had an incorrect presentation for the fundamental groups.
    I am very sorry about that.
    Please see the correct presentations on version 4 of the same article.
    The two pairs of 3-manifolds are, as we suspect, distinct.
    Craig Hodgson showed this by comparing the lengths of the smallest
    geodesics using SnapPy. It curious that the manifolds have the same volume.

    Briefly we will complement this paper with some more
    tough pairs of 3-manifolds.

    Comment by Sóstenes Lins — May 8, 2013 @ 9:25 am | Reply

  8. P.S. I only saw this blog 15 minutes ago. That is because I did not warn
    people before about the incorrections in my manually computed presentations. Once more, I am sorry. I still would like to know whether
    GAP computations distinguish the pairs.

    Comment by Sóstenes Lins — May 8, 2013 @ 9:33 am | Reply

  9. Hi, this is Sostenes,
    Few days ago the Challenge paper v4 was put in the arXiv. The first two pairs of 3-manifolds, were,
    as we suspected, distinct. This was found by Craig Hodgson using the length of the smallest
    geodesics and by Nathan Dunfield by covering homology methods. The Challenge remains
    in Fig. 5 of [LL]. Among the 8 manifolds there are pairs of isomorphic ones. Find them and,
    please, report the time it takes to find isomorphic triangulations (problaby with SnapPy).

    Comment by Sostenes Lins — May 9, 2013 @ 7:45 am | Reply

    • Many thanks for your replies, Sóstenes.

      I’m still somewhat confused about the status of your ‘challenges’. I took the first two challenges (to distinguish the pairs of manifolds in version 2 of your preprint) to really be a request for techniques to distinguish pairs of 3-manifolds. That request has been successfully answered, in two different ways! (By ‘covering homology methods’, as you call them, and by Craig Hodgson’s computation of geodesic lengths – I’d like to hear more about the latter!)

      Even if there were mistakes in the original presentations, it seems to me that the onus is now on you to try these techniques before issuing further ‘challenges’. (Unless a reader feels inclined to do the computation for themselves? Please do leave a comment if you do! I personally have done enough fiddling around with GAP for this month.)

      I’m also confused by the nature of the wider challenge you issued in Figure 5 of version 3. Presumably you’ve already tried running your ‘gems’ algorithm on these manifolds, and so have some guess as to which are homeomorphic and which aren’t. If so, then it seems to me that the candid thing to do would be to include that information in your preprint.

      Comment by Henry Wilton — May 9, 2013 @ 9:14 am | Reply

      • I know the ones which are homeomorphic. Isomorphic gems were found for them using BLINK
        in Lauro’ s 2007-Thesis. I just want to see if other softwares can find isomorphic triangulations and in how much time. BLINK is available but it is not documented yet. You can see the details in
        the projects of laurolins in Github. I will give BLINK’s answers in the next version (5) of the challenge [LL]. At least 4 of them are solved to BLINK’s advantage: when it fails to find isomorphic gems
        now thanks to feedback from the Challenge we have invariants to distinguish them. In this version I will give also the status of the 13 doubts left open in Lauro’ s Thesis
        Most of all we hope to have help to improve BLINK’ s interfaces and put some new more algorithms on it making it a complement of SnapPy, GAP, Sage, etc. Lauro is basically unavailable these days
        working in AT&T. But I think he can answer some questions related to download and running BLINK.

        Comment by Sostenes Lins — May 9, 2013 @ 10:02 am

    • By the way, in case you haven’t been there before, Mathoverflow would have been a great venue for your questions.

      Comment by Henry Wilton — May 9, 2013 @ 9:17 am | Reply

    • Hi Sostenes,

      I did this, using SnapPy, for the manifolds in class 9_126 from your arxiv preprint. These manifolds all have hyperbolic volume 7.36429600733.

      The results were instantaneous. Here they are:

      In [34]: for n in range(5):
      for m in range(n+1,5):
      A = class9126[n]
      B = class9126[m]
      print A, B,
      try:
      print A.is_isometric_to(B)
      except RuntimeError:
      print ‘unknown’

      U1466(0,1)(-1,1) U1563(3,1)(0,1) unknown
      U1466(0,1)(-1,1) U1738(0,1)(-1,1) True
      U1466(0,1)(-1,1) U2233(-1,1)(0,1) True
      U1466(0,1)(-1,1) U2125(-1,1)(0,1) True
      U1563(3,1)(0,1) U1738(0,1)(-1,1) unknown
      U1563(3,1)(0,1) U2233(-1,1)(0,1) unknown
      U1563(3,1)(0,1) U2125(-1,1)(0,1) unknown
      U1738(0,1)(-1,1) U2233(-1,1)(0,1) True
      U1738(0,1)(-1,1) U2125(-1,1)(0,1) True
      U2233(-1,1)(0,1) U2125(-1,1)(0,1) True

      In other words, U1466, U1738, U2233, and U2125 all have isomorphic triangulations.

      To distinguish them, we can use 6 fold covers, as for the other examples in the preprint. Here is the computation:
      In [36]: for M in class9126:
      print M, [C.homology() for C in M.covers(6)]

      U1466(0,1)(-1,1) [Z/2 + Z/4 + Z, Z, Z/2 + Z/4 + Z]
      U1563(3,1)(0,1) [Z/2 + Z/4 + Z/48, Z/2 + Z/4 + Z/48, Z/6]
      U1738(0,1)(-1,1) [Z/2 + Z/4 + Z, Z, Z/2 + Z/4 + Z]
      U2233(-1,1)(0,1) [Z/2 + Z/4 + Z, Z, Z/2 + Z/4 + Z]
      U2125(-1,1)(0,1) [Z/2 + Z/4 + Z, Z, Z/2 + Z/4 + Z]

      This shows that U1563 is not homeomorphic to the others. For this computation there was a tiny pause before printing out the result. Maybe half a second.

      It took a lot longer to draw the links in SnapPy’s link editor! (Probably 10 minutes — I am a slow drawer.)

      Best,

      Marc

      Comment by Marc Culler — May 9, 2013 @ 9:17 am | Reply

      • The algorithm used in the SnapPea kernel (and hence in SnapPy) for computing the length spectrum of a hyperbolic manifold is due to Craig and Jeff. The reference is C. Hodgson and J. Weeks, “Symmetries, isometries and length spectra of closed hyperbolic 3-manifolds”, Experimental Mathematics 3 (1994) 261-274. The SnapPea kernel has an option “full_rigor” which, if set to True, guarantees that it will find all geodesics of length below a specified cutoff. (Unfortunately we did not provide access to that option in SnapPy — an oversight which will be remedied immediately.) A drawback of this method is that it requires computation of a Dirichlet domain, which is numerically fairly unstable. So it is only practical for small manifolds. Sostenes’ examples are well within the range where this works, however.

        – Marc

        Comment by Marc Culler — May 9, 2013 @ 9:51 am

      • Thank you for your answer Marc,
        You are right U[1563] is distinct from the other four. We also know that the other four are
        homeomorphic because BLINK found isomorphic gems for them. This is in BLINK system which supported Lauro’ s 2007-Thesis. I just want to see if other softwares can find isomorphic triangulations and in how much time. BLINK is available but it is not documented yet and in particular I myself cannot run it to its full functionality. You can see the details in
        the projects of laurolins in Github. I will give BLINK’s answers in the next version (5) of the challenge [LL]. At least 4 of them are solved to BLINK’s advantage: when it fails to find isomorphic gems
        now thanks to feedback from the Challenge we have invariants to distinguish them. In this version 5 I will give also the status of the 13 doubts left open in Lauro’ s Thesis
        Most of all we hope to have help to improve BLINK’ s interfaces and put some new more algorithms on it making it a complement of SnapPy, GAP, Sage, etc. Lauro is basically unavailable these days
        working in AT&T. But I think he can answer some questions related to download and running BLINK.

        Comment by Sostenes Lins — May 9, 2013 @ 10:11 am

      • So your answer is that SnapPy can find isomorphic triangulations for the four homeomorphic manifolds in the blink of an eye.

        Comment by Marc Culler — May 9, 2013 @ 10:20 am

  10. One aspect of the various tuples of challenge manifolds is that they have the same volume, at least as computed by Snappea. Does anyone have a geometric explanation (for any pair of them) of why this is so? Obvious things to look for would be common finite coverings or mutations, or some combination of these. Perhaps there is something intrinsic to the Lins-Lins construction that is producing such examples.

    Comment by Daniel Ruberman — May 9, 2013 @ 10:08 am | Reply

    • Dear Daniel,
      There is a very exciting fact which happens with the T-catalogue of 3-manifolds induced by
      3-connected blinks in Appendix C of Lauro’ s 2007-Thesis (on the arXviv — see [LL] for reference): The manifolds in the T-class (T for three-connected) are induced only by singletons by pairs and by quartets of blinks. I find that this merits an explanation. Another thing that blows my mind about
      our approach is that 3-manifolds are equivalent to subtle classes of plane graphs with an edge bipartition: a class of blinks. What can be simpler than a blink? And yet is capable of encompass
      all the mystery of 3-manifolds.
      Thank you for your comments.
      Sóstenes

      Comment by Sostenes Lins — May 9, 2013 @ 10:21 am | Reply

    • John Berge pointed out to me that the four homeomorphic closed manifolds U1466, U1738, U2233, and U2866 (which I accidentally misnamed as U2125) are all presented as Dehn fillings of the same framed link. That is, there are framing-preserving homeomorphisms between the link complements. (In some cases, the homeomorphism interchanges the boundary tori.) John checked this with his program Heegaard. I confirmed it with SnapPy. It is not so surprising that one gets the same manifold by doing the same filling on the same cusped manifold. It is a more interesting question why that manifold has the same volume as the other one. However, when you look at tables of hyperbolic volumes it is very common to find many manifolds with the same volume. I believe that in many of these cases the manifolds have scissor-congruent Dirichlet domains.

      Comment by Marc Culler — May 14, 2013 @ 9:27 am | Reply

  11. How can G1 have a subgroup with infinite abelization and G2 don’t if both are homology spheres (according with S. Lins 1st version) ? How this can be understood in terms of cobordism and also Heegard decomposition ?

    Comment by Celso — May 14, 2013 @ 9:30 am | Reply

    • When M is a manifold and N is a finite-sheeted covering space, it’s quite common for the betti numbers of N to be larger than the betti numbers of M. (A standard argument with the transfer map shows that they’re never smaller – see Hatcher’s book on algebraic topology for details.) In fact, we now know that this always happens when M is a hyperbolic 3-manifold, by work of Agol, Wise and Kahn–Markovic, already discussed extensively on this blog.

      Comment by Henry Wilton — May 14, 2013 @ 9:43 am | Reply

      • Hi Henry. This discussion is rather stimulating though am I not an expertise on the topic. I would like to understand Nathan strategy. As far as I could understand what he has done was to find finite index normal subgroups of pi_1(G1) and compute the abelianization, what is equivalent to look at the finite covers of G1 and their H_1. (right ?) I am impressed with all this computer aid ! John Berge post is amazing.

        Comment by Celso — May 15, 2013 @ 6:59 am

      • Yes, that is precisely Nathan’s strategy (except the subgroups he’s looking at are not actually normal).

        Comment by Henry Wilton — May 15, 2013 @ 7:20 am

    • Refer to version 4 of the first challenge. The previous versions have mistakes in the presentations. In fact we only need the drawing of the blackboard framed link which
      completely defines the closed 3-manifold, hence its fundamental group.

      Comment by Sóstenes Lins — May 15, 2013 @ 10:06 am | Reply

  12. Just for the record.

    Let LU[xxxx] denoted the link surgered to obtain U[xxxx] in the preceding discussion. Then Heegaard shows LU[2125] and LU[3089] are both tunnel-number-one links with at least two unknotting tunnels, and the exteriors of LU[2125] and LU[3089] are homeomorphic. Furthermore, there is a homeomorphism of LU[2125] with LU[3089] which carries the framings of LU[2125] to the framing of LU[3089]. Hence the filled manifolds U[2125] and U[3089] are obviously homeomorphic.

    Some details, and a few relevant presentations:

    1) U[2125] = U[3089] The two dual  Heegaard presentations of these closed manifolds.

    A) L = 74 < AAABaBAABabAbaabABaBAABaBAbaabAbaBAABaB, AABaBAbABaBAABabAbaabABBBBAbaabAbaB >
    B) L = 74 < AAABabAbaBAABabABaBAbaabABaBAbaBAABabAbaB, AABabABBBBAbaBAABabAbaBAbABabAbaB >

    2) Exterior LU[2125] = Exterior LU[3089]
    A) Tunnel 1: L = 80 < AAABBAAABabbaaabABBAAABBAbaaabbaBAAABBAbaaabbaaabABBAAABabbaaabbaBAAABBAbaaabbaB >
    B) Tunnel 2: L = 84 < AAABabABBAbaaabABBAbaBAAABabbaBAAABabABBAbaaabABabbaBAAABabbaBAbaaabABBAbaaabABabbaB >

    3) Framings with respect to the first unknotting tunnel of length L = 80.

    L = 81 < AAABabbaBabABBAbABabbaBabbaBAbABBAbaBabbaB, ABBAbABBBAbABBAbaBabbaBAbABBAbABabbaBab >

    (Note that the conjugacy classes represented by these relators are “geometric”, which means there exist pairwise disjoint simple closed curves on the boundary of a handlebody H of genus two, which realized these relators, and furthermore, the realizations are unique, up to homeomorphism. Also note that each presentation has minimal length under automorphisms of F(A,B), and, as usual, X = x^{-1}. Finally, L = n means the presentations contains a total of n letters.)

    Comment by John Berge — May 15, 2013 @ 3:16 am | Reply

    • For future reference, to make John’s comment appear correctly I replaced the angle brackets with &lt; and &gt;.

      Comment by Henry Wilton — May 16, 2013 @ 7:30 am | Reply

  13. This is Sóstenes.

    I have posted a second paper the arXiv with some tough challenges (11 of them). If solved these challenges would complete the topological classification of the blackboard framed (which in particular have integer framings: the framing of a component is the sum of the signs of its self-crossings) of the alternating links up to 16 crossings.

    On the contrary of the first challenge paper I have received almost no feedback. Except for the
    first 2 of the 11, which were solved in accordance to BLINK, the other 9 challenges (at least the
    proof that some pairs in the HG8QI-classes are non-homeomorphic are, apparently untouched.
    In trying to use SnapPy via Sage to find low index covering we did not have success.

    Should I take from this that we have arrived to the current technological limit in completely solved these 9 remaining challenges? I am preparing another version of the tougher challenge paper where I inform,in the drawings, all the framings, making easy for people to directly import the challenges into SnapPy (I already posted an appendix with the SnapPy format for the links to be imported to snapPy).

    A few days ago I posted a new paper in the arXiv showing that closed oriented 3-manifolds
    are in 1-1 correspondence with some subtle equivalence class of plane graphs with an arbitrary
    bipartition of its edges (blinks).

    Finally, by next Monday May 27, a joint paper with L. Lins will appear on the arXiv with an indexation of all 3-manifolds by number of edges (crrespond to crossings in the KFL’s) in their inducing blinks. Currently our limit is up to k= 9 edges. But the method generalizes for k=10, 11, …., until the technological limit. This work is a consequence of the first challenge paper:
    after posting it on the arXiv people feedback unveil the mystery of the last 6-year old two doubts.
    This is an example of scientific collaboration at its best. We seek the truth, independently of
    who and how it was obtained!

    I would love to receive comments on the status of the tougher challenges and on these two new
    papers.

    Thank you in advance for your feedback on these matters.

    Sóstenes

    Comment by Sostenes Lins — May 24, 2013 @ 4:17 am | Reply

    • I don’t think you should ‘take from this that we have arrived to the current technological limit in completely solved these 9 remaining challenges’. You write:

      ‘On the contrary of the first challenge paper I have received almost no feedback.’

      Could you clarify whether by ‘the first challenge paper’ you mean arXiv:1304.5964 (which was literally the first) or arXiv:1305.2617 (the one that contains eleven ‘challenges’)?

      Nathan’s, Craig’s and Marc’s contributions exhibit a comprehensive set of methods to attack these problems, all widely used and in the public domain.

      You write that ‘In trying to use SnapPy via Sage to find low index covering we did not have success’ but you don’t give precise details of what you tried.

      My guess is that you haven’t had more feedback for three reasons: (i) people are confused by the large number of arXiv postings containing duplicate problems; (ii) people think that Nathan, Craig and Marc’s techniques answer your question; and (iii) people are unsure what you have tried.

      If you really want more feedback, I would repeat my suggestion that you ask a precisely worded question on Mathoverflow.

      Comment by Henry Wilton — May 28, 2013 @ 6:09 am | Reply

  14. Thank you Henry,
    We will try our best with SnapPy/Sage/GAP trying to solve those doubts before asking more questions.
    The first challenge concerned two classes of manifolds with the same WRT-invariant and the same homology.
    These two classes were the only doubts that we have on the class of 3-manifolds induced by blackboard framed
    links up to 9 edges. This challenge was solved according to my bet, based on the theory of gems to find homeomorphisms,
    implemented in BLINK. The second tougher challenge consisted in solving 11 classes of 3-manifolds induced by monochromatic
    3-conected blinks up to 16 vertices (corresponding to blackboard frame links). With this new set of manifolds with 14, 15, 16 edges
    in their inucing blinks, things become more difficult for SnapPy/Sage/GAP. We found solutions for the 2 first ones. The third 15_19
    is reluctant to be treated by these softwares. At any rate, I think it is not the last word on the issue if a program take a lot
    of time and fails to get an answer or finds one by luck.
    After all the whole topological situation is completely encoded by a very small combinatorial object: a plane graph with 16 edges
    (the blinks of these examples are monochromatic). I firmly believe that in the future we will get better invariants than the current
    ones that many times are not going to work (this is clear to me, just take a harder example with more edges).
    This was my motivation to post the challenges. I will follow your suggestion and will learn
    how to put a question on Mathoverflow, when I have a precisely formulated one.

    Comment by Sostenes Lins — May 28, 2013 @ 11:21 am | Reply

    • Thanks for this, Sostenes. Have you tried using SnapPy to find the homeomorphisms that BLINK finds? It seems to me that the really interesting question is ‘What can BLINK do that SnapPy can’t?’

      Comment by Henry Wilton — May 28, 2013 @ 3:30 pm | Reply

      • The answer is easy: to find the WRT-invariants. and classify the blinks by them leaving very few
        doubts. I do not think SnapPy finds WRT-invariants . Am I wrong?

        Comment by Sostenes Lins — May 28, 2013 @ 3:41 pm

      • If WRT refers to Witten-Turaev-Viro invariants, you can compute them in Regina and also in Matveev’s Manifold Recogniser software. Regina and SnapPy are easily integrated as they both run in Python — also, much of the SnapPy kernel is integrated into Regina’s C++ source code.

        Comment by Ryan Budney — May 29, 2013 @ 2:22 am

      • Sostenes, I suppose what I really meant to ask was: ‘Do you know a pair of 3-manifolds M,N, such that BLINK can efficiently show that M and N are homeomorphic but SnapPy can’t?’

        Comment by Henry Wilton — May 29, 2013 @ 6:00 am

      • Also, it is intriguing that (if I understand correctly) blinks seem to give a natural enumeration of all hyperbolic 3-manifolds. The only proof that I know that the set of hyperbolic 3-manifolds is recursively enumerable uses Jason Manning’s beautiful algorithm for finding hyperbolic structures on 3-manifolds.

        Comment by Henry Wilton — May 29, 2013 @ 6:02 am

    • Sóstenes, I don’t know what you tried, but I did not have any particular trouble classifying the four manifolds in your family 15_19 last night. First I checked the volumes of the four links. The link complements for T122 and T188 both have volume 32.1904446… while those for T148 and T208 have volume 31.8897187… . Next I asked SnapPy to look for isometries between the pairs with the same volume. It quickly found framing-preserving homeomorphisms between the link complements in both pairs. So that shows that the closed manifold T122 is homeomorphic to T188, and T148 is homeomorphic to T208. Next I did the Dehn fillings, and noted that the volumes of the filled manifolds T122 and T148 were the same, namely 27.670218369…. To distinguish them, I asked SnapPy to find their 6-fold covers. This was taking a while, as one would expect with manifolds that large, so I went to bed. When I got up this morning SnapPy had found that T122 has 213 6-fold covers, one of which has first betti number 8. On the other hand, T148 has only 211 6-fold covers and the highest betti number that occurs is 7. That shows that the two closed manifolds are not homeomorphic. This family appears to behave very similarly to the others, except that the manifolds are larger. The same tools work fine to classify them, although it is true that the manifolds are approaching the size where computing the covering spaces becomes unpleasantly slow.

      Comment by Marc Culler — May 29, 2013 @ 7:13 am | Reply

      • Thank you Henry, for your question. I will investigate an answer for it with it with Cristiana. But I think
        I need to have feedback of all 11 classes of manifolds of the toughere challenge. So,
        this will take smetime.

        Thank you for your report on 15_19, Marc. I think that we are not operating properly the SnapPy.
        We will go back with your guidance on 15_19 (which you solved as BLINK predicted).

        But we start agreeing in one point. Conceptually it is easy for BLINK to find bigger and bigger examples in the same HGuQI-classes, and yet small blinks say of 20 edges. My point is that no other combination of the available software can produce these examples.
        Which of course will certainly be intractable by the current invariants. The whole point is
        that maybe 3-manifold seeing as a class of plane graphs (that I recently put in the zrXiv) will produce, in the future, better invariants. To check this point we need good small tough examples, which, as it seems only BLINK can produce. As I told before, BLINK is part of a Wiki open source code which needs to be improved. It will be a shame if we let this robust piece of software to dye.

        Last but not least BLINK is the only software that I know which draws blackboard framed links and blinks in a very adequate automatic way and presents the loops, the curls and the pendant edges in a unifolrm blin way. Its nice unambiguous drawings have no parallel in presenting the blackboard framed links in a grid minimizing the number of right angle bents.

        I am sending you both the updated version of our census paper. I do not think other
        current mathematical theory can do what we achieved with this paper: a no missing
        no duplicate census of closed, oriented, connected, and prime 3-manifold induced by blinks up to k edges. Trusting, as I do, in the robustness of Lauro’s implementation, I have no doubt in the correctness of this census. It will provide a unified language to talk and display about small 3-manifolds. There are still a lot of mysteries on them. Take into account, that every such 3-manifold
        will eventually appear once.

        Comment by Sostenes Lins — May 29, 2013 @ 9:23 am

  15. Henry, Marc,

    Relative Henry’ s quesgtion below I have a concrete suggestion.

    ” Sostenes, I suppose what I really meant to ask was: ‘Do you know a pair of 3-manifolds M,N, such that BLINK can efficiently show that M and N are homeomorphic but SnapPy can’t? ”

    If you look in Lauro’s thesis (in the arXiv) the HG12QI-classes are, (with the exceptions of 9_126 and 9_199 (which breaks into two, homeomorphic classes of 3-manifolds. This was found by BLINK and frozen forever in its data base. This means that we have encoded the homeomorphisms by paths in a graph whose vertices are gems and whose edges are TSrho-moves between them. The path
    is printable at request. In the census manifold induced by a k-edge blink appear. In principle
    we can make a film connecting the shape of the spaces modifies and agree. I have in gems
    a nice substitute for the Dirichlet domain, irrespective of if the manifold is geometric or not.
    They are polytopes whose faces are regular polygons with the same side bent to assemble itself.
    Instead of identifying faces we identify pairs of vertices. It seems that always everything is
    embeddable in R^3. Those are the shapes (which I call Mathematical Sculptures) that I discovered in
    1989 and which could be made in a film transforming one into the other by small deformation
    corresponding to the TS-moves. The Dirichlet domains can be more beautiful than the sculptures,
    but these are also nice and less frustrating. The whole description is in R^3.

    Given that BLINK solved the homeomorphism problem in U_9 and in the process
    constructed the sometimes large HG12QI-classes,
    I think the onus is on SnapPy to reproduce the BLINK (now complete) topological classification
    of U_9 and of T_16. Using the HG12QI-classes, since it seems, by itself not to be able to
    find them, due to the fact that, by itself it does not compute the WRT-invariants.

    There will be hundreds of thousand of tests to be made.
    BLINK data base uses more than 76000 gems. If the results disagree
    I bet on BLINK. But I hope, sincerely, that it agrees. Another thing to try is the speed of which
    these homeomorphisms can be found in the two softwares in optimized versions of the
    very distinct algorithms. My intention is not to compete with SnapPy, but to complement it with
    BLINK. You have to concede that we have something different (and in opinion complementary).
    Due to the fundamental difference in objectives, it would be very difficult to have
    SnapPy producing the topological classification BLINK produces.

    By the way, if you want I can send you a copy of Lauro’ s thesis. The one in the arXiv cut some
    pages at the bottom.

    Hoping to hear from you,
    Sostenes

    Comment by Sostenes Lins — May 29, 2013 @ 7:56 pm | Reply

    • “I think the onus is on SnapPy to reproduce the BLINK …”

      Sóstenes, I couldn’t disagree more.

      SnapPy is a tool for studying hyperbolic 3-manifolds. It is available to anyone who wants to use it. It can be useful for tabulating links and closed manifolds. In fact, the SnapPea kernel has been used in a number of tabulation projects by a number of people, including, in various combinations, Mark Bell, Pat Callahan, Abhijit Champanernaker, Nathan Dunfield, Stavros Garoufalidis, Matthias Goerner, Martin Hildebrand, Craig Hodgsen, Jim Hoste, Ilya Kofman, Eric Patterson, Saul Schleimer, Morwen Thistlethwaite, Jeff Weeks and others. I think it has been amply demonstrated on this blog that SnapPy would be useful for your tabulation project as well. When it is feasible, and we think it will be useful, we try to incorporate the data produced by such projects as part of SnapPy’s database of manifolds. You are more than welcome to use SnapPy in your project, and If you would like for us to include your BLINK tabulation in SnapPy, we can discuss that in private.

      But it is beyond ridiculous to state that “the onus is on SnapPy to reproduce” anything, including the BLINK tabulation. And if you feel there are hundreds of thousands of tests to be made, then I suggest that you get started making them.

      – Marc

      Comment by Marc Culler — May 30, 2013 @ 9:12 pm | Reply

  16. Just for the record,

    My enumeration of 3-manifolds by blinks get every closed, oriented, connected and prime 3-manifolds
    including the ones which have a uniform geometry or not. So all the hyperbolic such 3-manifolds will eventually appear. A question for you that I have is this: is there a nice algorithm to filter the non-hyperbolic ones? How difficult is to prove that such a 3-manifold given by a BFL is or is not hyperbolic?

    Comment by Sostenes Lins — May 29, 2013 @ 8:09 pm | Reply

    • So my statement above was incorrect – you have an enumeration of (closed, oriented, connected) prime 3-manifolds, not hyperbolic ones. Thanks for the clarification.

      Comment by Henry Wilton — May 30, 2013 @ 10:46 am | Reply

  17. Sostenes, there is an algorithm to find incompressible surfaces in Regina. It can be a slow computation and the speed depends quite heavily on the input triangulation. It can be used to filter-out non-hyperbolic manifolds. But it’s frequently quite fast — for example the Haken algorithm is implemented effectively in Regina. If you specify the manifold via a surgery, that is easy enough to triangulate and give to Regina.

    Frequently there’s very easy heuristics to deal with non-hyperbolic manifolds — for example, SnapPy will often see aspects of non-hyperbolizable manifolds when it gives solutions with negatively oriented tetrahedra.

    Comment by Ryan Budney — May 30, 2013 @ 10:28 am | Reply

    • Presumably Regina can filter out manifolds with immersed, incompressible tori. How does it recognize elliptic manifolds?

      Comment by Henry Wilton — May 30, 2013 @ 10:56 am | Reply

    • I don’t remember the precise statement of the theorem. I believe it’s either in Jaco and Rubinstein’s 0-efficiency paper or in the follow-on “an algorithm to recognise small seifert fibred spaces”. Something like if you have a 0-efficient triangulation of a small Seifert fibred manifold (over S^2 with three singular fibers) then the triangulation is minimal and built from layered solid tori in a prescribed way. That’s the best I can do without a lot of digging, apologies! And of course, you use the algorithm to replace your original triangulation with a 0-efficient one…

      Comment by Ryan Budney — May 30, 2013 @ 11:16 am | Reply

      • Thanks Ryan – that’s more than enough detail! Anyway, I was being silly above when I suggested that I only knew how to rigorously enumerate hyperbolic 3-manifolds using Manning’s algorithm. Of course one can take the complementary route, as you suggest – use normal surface theory to find essential tori (plus deal with the other atoroidal manifolds somehow) and the remaining 3-manifolds are hyperbolic, by geometrization.

        Comment by Henry Wilton — May 31, 2013 @ 4:56 am

  18. Marc’s words:
    “But it is beyond ridiculous to state that “the onus is on SnapPy to reproduce” anything, including the BLINK tabulation. And if you feel there are hundreds of thousands of tests to be made, then I suggest that you get started making them.¨

    I was surprise and did not understand what seemed to me an over reaction of Marc on my last comments. The reason, I realize later, is that we were talking about two different issues.

    First let me say of my great admiration for the program SnapPy. To the list of people that he brings forth having computational projects on 3-manifolds which were helped by SnapPy he should append our names. By using SnapPy the complete topological classification of U9 was completed. And that of T16 is under its way.

    Marc’s words:
    “I think it has been amply demonstrated on this blog that SnapPy would be useful for your tabulation project as well. When it is feasible, and we think it will be useful, we try to incorporate the data produced by such projects as part of SnapPy’s database of manifolds. You are more than welcome to use SnapPy in your project, and If you would like for us to include your BLINK tabulation in SnapPy, we can discuss that in private.”

    I rush to say that I couldn’t agree more with you Marc and that I happily accept all the 3 invitations contained in the above paragraph. I also want to thank you for being so helpful in guiding Cristiana to install SnapPy in our machines.

    Now for removal of the misunderstanding. There are two types of onuses at stake. I will classify them as psychological and epistemological onuses. In the first case I completely agree with Marc in his reaction. The point is that I meant, and this was not clear, the epistemological.

    To make my point clear I abstract the situation in order to take distance form the emotional aspects of the discussion.

    Suppose we have a system X operating on an infinite set O
    which needs to be partitioned into equivalence classes.
    X has partial solution for the two problems on a pair (o,o’) of members of O: sometimes it can prove that o and o’ are equivalent, sometimes it can show that they are not equivalent.
    Sometimes it fails: the pair (o,o’) remains in doubt.

    Now we have another system, named Y, operating on a subset U of O which does the following on the same equivalence classes as X restricted to U. First U is formed by larger and larger finite sets U’ so that at a fixed instant in time Y has achieved the following conditions: for any given pair in (u,u’) in U’, either Y produces a proof that u,u’ are equivalent or else it shows that they are not equivalent. Proof here has the following formal connotation: it is an output, that other systems, including X, can consult to convince itself that Y is right about (u,u’).

    Those are my grounding setting premisses. Now it follows, almost by definition that for each pair (u,u’) declared equivalent by Y, X has the epistemological onus of checking whether it also can prove them to be equivalent. And if it fails to do so on any single pair, this means under the ground rules that X is not complete and that, in the name of truth, can profit from the situation by including some aspects of Y in its internal design.

    Note that this does not mean that the developers of X must stop doing what they are doing to reproduce Y’s computations. Of course, the psicological onus is on the developers of Y, to do the work and so prove that Y is not subsumed by X. Particularizing to our situation, I was not suggesting to the SnapPy developers ought to check the hundreds of thousands of examples that should be tested into X. This work is to be performed by the developers of Y. Only they have the incentive to do it. I will seek help for doing, have no doubt about this.

    I devised this ideal test when I was challenged by Henry Wilton to produce with BLINK something that SnapPy could not produce. The problem is that I did not explain myself explicitly and this resulted in this misunderstanding. Let us move on and collaborate in the name of progress of the science we all love: the mysterious 3-manifolds.

    The internal algorithms for proving homeomorphisms of BLINK and of SnapPy are based on different techniques and on the different types of triangulations. I think, in the name of truth, that it is an interesting project to find more about these differences and include both algorithms in the same package, if we find it to be worth. On this matter I have the feeling that they are the algorithms are incomparable (none is stronger than the other) and so, the integration will be an advance.

    Comment by Sostenes Lins — June 1, 2013 @ 4:53 am | Reply

  19. SnapPy already has a very substantial and well-recorded history of checks of the type you are asking of it, Sostenes. Although these are not direct comparisons with your software. For example, SnapPy has been used to compute the symmetry groups of knots and links in the knot tables — this uses its technique to compute all the hyperbolic isometries between two cusped hyperbolic manifolds. In this regard it has been compared to several other techniques, like the Bonahon-Siebenmann arborescent link technique (this was done by Sakuma, in comparison with Weeks’s work).

    So although I doubt anyone would assert SnapPy is flawless or that it attempts to do everything well, it’s probably one of the most looked-over pieces of software in low-dimensional topology, and has withstood many tests, as many people have used it for many different purposes.

    I’m not sure to what extent topologists use SnapPy to solve the homeomorphism problem. I think it’s more often used to study properties of particular manifolds. For a long time my primary interest in SnapPy was its ability to compute isometry groups. I use it fairly systematically now in a partial-algorithm for computing the geometric decomposition of manifolds — a solution to the homeomorphism problem is not enough for my purposes. The manifolds that come up in my application typically have connect-sum and JSJ-decompositions, so SnapPy is just a step in a procedure to find the geometric “name” of the manifold.

    Comment by Ryan Budney — June 1, 2013 @ 2:28 pm | Reply

    • Dear Ryan,
      I hope that it is cIear that am not trying to find flaws in SnapPy. I think is a genuine scientific question to test its isomorphic triangulation algorithm with mine which is based in TS-moves. This last one has been very strong in proving when two gems
      induce the same 3-manifold.

      After Perelman I am very interested in seeing whether we can find polynomial algorithms to describe the structure of the 3-manifolds solely from the combinatorics of the gem. I think, given our current knowledge, this became a feasible project for closed 3-manifolds.The issue is that the structure appears at the level of decomposing the gem. I have a lot to learn from you
      in the topic.

      Comment by Sostenes Lins — June 1, 2013 @ 4:21 pm | Reply

  20. I think there’s some good reasons to hope for fast algorithms for many 3-manifold theory problems, for example Marc Lackenby’s recent paper on the unknot recognition problem would be one. But there’s also plenty of heuristically fast procedures that seem to work more often than you’d imagine (see for example Ben Burton’s papers).

    My feeling is single triangulations or gems is not the right setting. Much like how solutions to the gluing equations for hyperbolic structures depend on the precise triangulation you use, a combinatorial Ricci flow would probably have to live on a space of triangulations of the manifold.

    Comment by Ryan Budney — June 1, 2013 @ 6:11 pm | Reply


RSS feed for comments on this post. TrackBack URI

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

The Rubric Theme. Blog at WordPress.com.

Follow

Get every new post delivered to your Inbox.

Join 210 other followers

%d bloggers like this: