Are hyperbolic $n$-manifolds recursively enumerable?

Question

Fixing a dimension $n \ge 4$, is the class of closed hyperbolic $n$-manifolds recursively enumerable?

Since hyperbolic manifolds are triangulable I can reformulate this in the following more explicit way: say $M_1, \ldots, M_m,\ldots$ is an enumeration of all triangulations of $n$-manifolds. Is there a Turing machine which outputs a sequence $i_1, \ldots, i_m, \ldots$ such that each $M_{i_k}$ is hyperbolic, every hyperbolic $n$-manifold occurs as one of the $M_{i_k}$ and no two of them are homeomorphic to each other?

This problem reduces to that of deciding whether a triangulated manifold is hyperbolic, since the homeomorphism problem for hyperbolic manifolds is decidable. This is well-known to be possible when $n$ is $2$ or $3$ but i haven't found any references for $n \ge 4$.

Added later: ~~actually it seems that it is not possible to list all triangulations of manifolds in dimensions $6$ and higher. The question still makes sense for n=4, 5.~~ While it may not be possible to get a complete list of all triangulation of all smooth manifolds it is possible (as outlined by HJRW in the comments) to get a list of triangulations which include all smooth manifolds at least once. So the question makes sense for all dimensions again.

You could compute the fundamental group, then the isolated points of the $\mathrm{SO}_0(n,1)$ character variety. You can then probably check completeness using the developing map and your triangulation. Each should be a "finite" check, though it will take thousands of years to do the first handful... — Toffee, Jan 05 '22 at 13:38
@Toffee: You seem to be suggesting that the Casson--Manning algorithm in 3 dimensions (https://arxiv.org/abs/math/0102154) also works in higher dimensions. That may well be true, but probably requires more than a couple of lines of justification! — HJRW, Jan 05 '22 at 14:44
I'm curious about the added dimension restriction. Is this a theorem? It sounds like a plausible obstruction in the topological category, but since hyperbolic manifolds are in particular smooth and hence have a unique PL structure, it doesn't seem like it should be a problem. — HJRW, Jan 05 '22 at 14:50
@HJRW Indeed! I did not include the word "probably" lightly. A lot of what Manning does with the Margulis Lemma etc. is pretty general though, with endgame Poincaré polyhedron (which is what I had in mind as how one checks completeness using the developing map). Maybe the diciest step is some $(n-1)$-sphere recognition in the links over vertices? As you mentioned, it's PL, so maybe okay, but you hit on precisely why I stuck to comment rather than answer. ;) — Toffee, Jan 05 '22 at 15:07
@HJRW The theorem i found right after asking the question states that in dimensions 5 and higher it is not possible to decide whether or not a triangulation is homeomorphic to the sphere, eg. https://arxiv.org/pdf/1405.3848.pdf. On the other hand i think that given a n-simplicial complex you can glue the faces of a (n+1)-tetrahedron to get a Delta-complex with one vertex whose link is your n-complex (or at least do something close enough, there might be an orientation issue here), so manifold recognition would imply sphere recognition. — Jean Raimbault, Jan 05 '22 at 15:08
@Toffee Thanks for the comment, this seems to be a good road towards an answer. Regarding the algebro-geometric part the main difference between the 3-dimensional and the higher-dimensional cases seems to be that in the latter one needs to compute with real algebraic varieties rather than complex, does that induce any new problem? (I'll have to read Manning's paper in some detail before i can comment on the geometric part) — Jean Raimbault, Jan 05 '22 at 15:13
@JeanRaimbault: Sphere recognition is indeed undecidable, but there is a semi-algorithm to certify that a triangulation of a manifold is a sphere: just compute homology and check that the fundamental group is trivial. So I think it is still possible to list triangulations of manifolds. The undecidable bit is to certify that the manifold you’re looking at isn’t simply connected. — HJRW, Jan 05 '22 at 15:17
@HJRW I agree there is a semi-algorithm to recognise the sphere, but doesn't that give you a semi-algorithm only for manifold recognition as well? — Jean Raimbault, Jan 05 '22 at 15:42
I'd guess that using arithmeticity, one can enumerate locally symmetric spaces (in the suggested way: output 1 triangulation per isometry/homeomorphism type) modeled on $\mathrm{SL}_n(\mathbf{R})$ for any given $n$. This seems quite orthogonal to the problem of recognizing whether a simplicial complex is a manifold or some particular kind of manifold. — YCor, Jan 05 '22 at 15:58
@JeanRaimbault I think you can use the $\mathrm{SO}(n+1)(\mathbb{C})$ character variety if you want to avoid AG over $\mathbb{R}$. Tensor with $\mathbb{C}$ (in the Lie algebra cohomology of the rep, i.e., the Zariski tangent space of the point) should say you still get an isolated point there. The real locus is now the reps into all real forms, so you need to check which points in the algebraic set give $\mathrm{SO}_0(n,1)$ representations, but we're just after primitive recursive, not practical, so I think it's fine. — Toffee, Jan 05 '22 at 16:01
@YCor But then you avoid all non-arithmetic ones, of which there are plenty if you are looking at hyperbolic manifolds — Jean Raimbault, Jan 05 '22 at 16:12
@Toffee is it true that an isolated point in the $\mathbb R$-points remains isolated in the $\mathbb C$-points? This would imply local rigidity for the embedding $\Gamma \to SO(n+1)(\mathbb C)$ for a lattice $\Gamma \le SO(n, 1)$, which i'm not sure is known (or even true). — Jean Raimbault, Jan 05 '22 at 16:15
@JeanRaimbault: Right. But you claimed that “it is not possible to list all triangulations of manifolds”, and producing a list is a semi-algorithm! I’m really only trying to point out that your impossibility claim doesn’t follow from the result in the paper you cited. To be clear, there are certainly difficulties here relating to the differences between triangulations, smooth structures and PL structures, but I think it is possible to list a sequence of triangulations of topological manifolds that will at least include all the smooth ones. — HJRW, Jan 05 '22 at 16:35
@HJRW You're right, i was too pessimistic and i mistook the fact that the "naîve" way to build a list cannot work with the claim that you cannot build it at all. Do you have any ideas regarding the way to build such a list? — Jean Raimbault, Jan 05 '22 at 16:45
@JeanRaimbault I think local rigidity in $\mathrm{SL}_{n+1}(\mathbb{C})$ is open, even $\mathbb{R}$, but $H^1(\rho, \mathfrak{so}(n+1)(\mathbb{C})) \cong H^1(\rho, \mathfrak{so}(n,1) \otimes \mathbb{C}) \cong H^1(\rho, \mathfrak{so}(n,1)) \otimes \mathbb{C} \cong {0}$. The dimension of the Zariski tangent space is an upper bound for the dimension of the component. — Toffee, Jan 05 '22 at 16:48
@Toffee Thanks, i did not realise that infinitesimal rigidity in ambient group implies local rigidity in complexification as your argument shows. — Jean Raimbault, Jan 05 '22 at 16:51
@JeanRaimbault: I have something fairly naive in mind too! Assume we have such a list in dimension $n-1$. Then, in particular, we can list some triangulations of spheres in dimension $n-1$, as discussed above (invoking, among other things, the Poincaré conjecture). Now, in dimension $n$, list all finite simplicial complexes $K$, and for each such $K$ in parallel check to see if every link is on our list of $(n-1)$-dimensional spheres…. — HJRW, Jan 05 '22 at 16:57
… Output $K$ if every link is on the list. Inducting on $n$, the result is some list of triangulations of $n$-dimensional manifolds. I think it’s big enough to include all the smooth ones. — HJRW, Jan 05 '22 at 16:58
@JeanRaimbault It's a cute observation I didn't realize for a long time until I saw it in a (quite excellent) mathscinet review by Bill Goldman (MR2800692). — Toffee, Jan 05 '22 at 17:04
@HJRW OK, so this works depending on the claim that there is an explicit small list of triangulations of the sphere such that every smooth manifold admits a triangulation with all links in the list. That claim looks perfectly reasonable and even provable without much effort, so thank you for all the clarifications! i'll edit the question to reflect this. — Jean Raimbault, Jan 05 '22 at 17:05
@JeanRaimbault I know that in this setting there are non-arithmetic ones. I just mean that the non-decidability of recognizability of spheres in higher dimension is not a convincing reason to expect a negative answer for your own question (unless I miss something). — YCor, Jan 05 '22 at 17:54
@HJRW For triangulations of bounded valence, see this answer. https://mathoverflow.net/a/379618/1345 I’m pretty sure that one can use this to give an algorithm. Let’s say we want to build all hyperbolic manifolds in dimension n > 3. We can triangulate with small geodesic simplices. Suppose one has such a triangulation, then one can wiggle the vertices so that all the coordinates are algebraic numbers. Thus such triangulations can be recursively enumerated. Now use Sela’s algorithm for example to eliminate repeats. — Ian Agol, Jun 07 '22 at 19:08

score 6 · Accepted Answer · answered Jun 08 '22 at 20:41

The class of closed hyperbolic manifolds is recursively enumerable. I’ll describe a terrible algorithm which nevertheless gives an enumeration.

A couple of basic facts: a hyperbolic $n$-manifold $M$ admits a triangulation by geodesic simplices, and the representation of the fundamental group into $PO(n,1)$ may be conjugated to have matrices with algebraic entries. The former follows from taking a dirichlet domain and subdividing, the latter from Mostow rigidity.

By taking the preimage of the triangulation in $\mathbb{H}^n$ (realized eg as one sheet of a hyperboloid in $\mathbb{R}^{n,1}$), we have a triangulation of $\mathbb{H}^n$ invariant under the action of $\pi_1(M)$ acting by algebraic matrices. We now perturb the vertices of the triangulation equivariantly to be points with algebraic coordinates (this is why we use simplices rather than more complicated polyhedra, since they are stable under small perturbations).

We may recover $M$ from a finite amount of this information: choose one simplex from each orbit, and for each pair of faces that are glued together, there will be a matrix in $PO(n,1)$ with algebraic entries gluing the faces together by an isometry.

Conversely, if we have a collection of simplices in $\mathbb{H}^n$ with algebraic coordinates, and the faces are paired by isometries, then we may check that they give rise to an $n$-manifold using the Poincaré polyhedron theorem. For each codimension two face of the simplices, we check that the angles about the faces sum to $2\pi$. This is possible since all of the coordinates of the vertices are algebraic. What I have in mind here is a version of Poincaré’s theorem due to Seifert; see Rob Riley’s paper.

To enumerate hyperbolic n-manifolds, recursively enumerate simplices in $\mathbb{H}^n$ with algebraic coordinates, together with pairings between the faces. Throw out the ones that don’t satisfy Poincaré’s theorem. Then throw out repeats eg by using Sela’s algorithm to eliminate manifolds with the same fundamental group.

(Let me know if you’d like more details on any aspect of this algorithm, I realize it’s very sketchy. )

That's a pretty clear sketch (though hardly practical, as you mention). It seems clear that one can enumerate algebraic points on an affine quadric, and Riley's paper gives a good degree of detail regarding verification of Poincaré's hypotheses. — Jean Raimbault, Jun 09 '22 at 11:53
@JeanRaimbault Attempting a practical implementation, there are many things one could try to improve. For example, enumerate triangulations first like you suggested. Even though the sphere recognition (and hence manifold recognition) problem is not solvable, the space of hyperbolic manifold metrics on a simplicial complex ought to be semialgebraic, and hence computable. Thus one could search through pseudomanifold triangulations first and try to find a hyperbolic manifold structure. Also the finite volume case should be algorithmic too. — Ian Agol, Jun 10 '22 at 00:49

Are hyperbolic $n$-manifolds recursively enumerable?

1 Answers1