25
$\begingroup$

Earlier this year it was asked on MO, "Are there only countably many compact topological manifolds?" Thanks to Cheeger and Kister, the answer is yes. On the other hand, Manolescu recently debunked the triangulation conjecture. A natural follow-up question asks if there is some other way to enumerate topological n-manifolds, in the sense of creating a Turing machine that will eventually output an example from every homeomorphism class of topological manifolds, given enough time.

Of course, for $n \leq 3$, TOP = PL, so I'm really interested in the cases $n\geq 4$. It's entirely possible that the answer still depends on $n$, so you can interpret the question with either $n$ fixed or variable.

If the answer is no, is it known how hard the problem of enumerating manifolds is? Is it harder than the halting problem?

Edit in response to comments below: I do not mean to jump the gun. To even have a hope that the answer to the question is yes, one would have to have some finitely computable description of topological manifolds. As BjørnKjos-Hanssen indicates in comments, this might take the form of some sequence of approximations. If a direct answer to my question seems out of reach, I would be happy with an answer explaining what is and isn't known. (I also removed the madness about reference to Turing degrees above.)

$\endgroup$
21
  • 5
    $\begingroup$ This is not immediately clear to me, especially considering their proof is by contradiction. $\endgroup$
    – Eric S.
    Oct 23, 2015 at 9:14
  • 5
    $\begingroup$ Turing machines output numbers or strings, not manifolds, so you first need to label your manifolds somehow to make this precise. The answer will of course depend on how you do this (say you give the compact topological manifolds the labels $2,4,6,8,\ldots$; then I could sell you a Turing machine that lists them). $\endgroup$ Oct 23, 2015 at 14:53
  • 4
    $\begingroup$ @Christian, the whole point is I don't know how to create an algorithm that eventually labels all $n$-manifolds. If I did, I would already have the answer to this question. But yes, the output of this Turing machine is supposed to be a string which somehow encodes a manifold. For example, if I asked about PL $4$-manifolds, the Turing machine could just output some binary description of all admissible triangulations of 4-manifolds. $\endgroup$
    – Eric S.
    Oct 23, 2015 at 18:18
  • 10
    $\begingroup$ @Eric S. : I believe that Christian Remling's point is that before you even think about computability, a more fundamental question is whether there is even a way to describe a compact topological manifold using a finite number of bits. And the question of what constitutes a reasonable description is a question that you have to answer before anyone else can answer the computability question, or else there is nothing to stop someone from saying that the number 1 is a description of some compact manifold, the number 2 is a description of some other compact manifold, etc. $\endgroup$ Oct 23, 2015 at 22:02
  • 5
    $\begingroup$ I suppose an in-between possibility exists: You could possibly be able to enumerate all topological manifolds (in a matter similar to @BjørnKjos-Hanssen's suggestion, or as the index of a description of a computable topological space), but your enumeration contains homeomorphic duplicates of each manifold type, and moreover, it is impossible to find an enumeration containing only one representative of each homeomorphism class. $\endgroup$
    – Jason Rute
    Oct 24, 2015 at 2:32

2 Answers 2

10
$\begingroup$

In a note of Freedman and Zuddas, they show that this is true for dimensions $\geq 4$.

In the "Background" section of the paper, they describe the solution in the higher dimensional case using surgery theory, but without any references.

Then they proceed to describe the 4-dimensional case. Here they use the fact that the complement of a point in a 4-manifold is smoothable. Hence one can describe a triangulation of a finite part of the complement of a point, together with a certificate of a 3-sphere tamely embedded.

It's frustrating that they don't give any references for the higher-dimensional case.

$\endgroup$
3
  • $\begingroup$ Yes, assuming the higher dimensional case works as they describe, this does seem to answer my question. Also, I haven't been on MO much lately, and hadn't updated my profile since moving to Illinois. It would be a pretty long walk to Station Q now. $\endgroup$
    – Eric S.
    Jul 16, 2020 at 17:04
  • $\begingroup$ Maybe someone else on MO knows some references. $\endgroup$
    – Eric S.
    Jul 16, 2020 at 17:06
  • $\begingroup$ Ah, I forgot you had moved. In any case, I also had forgotten that Mike had asked this question on MO a couple of years ago (someone should have pointed out the relation to your question at the time). mathoverflow.net/q/292525/1345 It appears that the paper resulted from that posting (Zuddas gave an answer). So someone on MO knows the answer, but Mike uses the site intermittently (and usually creates a new profile each time, which the moderators then have to merge). mathoverflow.net/users/58457/michael-freedman mathoverflow.net/users/122296/michael-freedman $\endgroup$
    – Ian Agol
    Jul 16, 2020 at 17:16
1
$\begingroup$

At the risk of getting on everyone's nerves (and special apologies to the OP), I would still maintain that the question in this form is too vague.

If I understand the suggestions in the comments correctly, they amount to something like this: interpret the output of a Turing machine as a sequence of points (possibly empty or finite) $x_0,x_1,x_2,\ldots\in\mathbb Q^{2n+1}$. Now we can ask: for what $e$ will TM number $e$ output a sequence of points whose closure in $\mathbb R^{2n+1}$ is an (embedded) manifold of the desired type? (This is certainly not exactly what Bjorn suggested, but it feels close enough.)

However, if we formalize like this, then part of the problem immediately disappears because any such set is non-recursive by Rice's theorem and this doesn't feel very satisfying because it had nothing to do with manifolds. (Admittedly, we could still ask about other properties of my set of $e$'s.)

$\endgroup$
3
  • 7
    $\begingroup$ It seems to me that the whole point of the question is that the OP doesn't presume to know what sort of formalisation might work. Sure, that makes the question vague, but it's still a reasonable mathematical question. Often in mathematics, we know that some definition doesn't go the job we want, and wonder if there's another one which does. $\endgroup$
    – HJRW
    Oct 24, 2015 at 15:57
  • $\begingroup$ If you think about the classification of 2-manifolds (spheres and Klein bottles with varying numbers of handles), it is definitely computable. $\endgroup$ Oct 24, 2015 at 16:49
  • 1
    $\begingroup$ HJRW sums the situation up well. If I were to propose a specific model in my question, I run the risk of getting answers about the infeasibility of that model. What I really want is either positive evidence, or a broader discussion of why no feasible model or definition is likely to exist. $\endgroup$
    – Eric S.
    Oct 24, 2015 at 18:10

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.