18

Hi, is there an algorithm that determines if a given simplicial complex is a.) a manifold b.) a smooth manifold c.) homotopy equivalent to a manifold d.) a real algebraic variety

?

Ryan Budney
  • 43,013
Markus Ulke
  • 939
  • 7
  • 13
  • 2
    There is not really a big difference between (b) and (d) since every compact differentiable manifold is a real algebraic variety as cited in http://www.aimsciences.org/journals/pdfs.jsp?paperID=2431&mode=full [a result due to Nash and Tognoli] – Lennart Meier Jul 27 '11 at 14:10
  • 4
    All finite simplicial complexes have the homotopy-type of manifolds, provided you allow the manifolds to have boundary. The proof is given by embedding the simplicial complex in a suitably high-dimensional manifold (say Euclidean space) and then taking a smooth regular neighbourhood of the complex. The regular neighbourhood has the same homotopy-type and it's a smooth manifold. – Ryan Budney Jul 27 '11 at 17:10
  • Any manifold with boundary has the homotopy type of a manifold without boundary, so you don't need that requirement... – Dylan Wilson Feb 15 '13 at 16:39

3 Answers3

14

A simplicial complex is a manifold if the links of all vertices are simplicial spheres. Recognizing the $n$-sphere is easy for $n=1, 2$, tractable for $n=3$ (the Rubinstein-Thompson algorithm and refinements thereof. I believe it is still exponential time), and undecidable for $n\geq 5$ by a result of Novikov -- see http://www.inf.ethz.ch/personal/wagneru/Manuscripts/e4hard.pdf and references therein. Don't know about $n=4.$

As for "real algebraic variety", every manifold is homotopy equivalent to a real algebraic variety (this is Nash's famous theorem), and every manifold of dimension less than 10 is homeomorphic to a real algebraic variety (see http://www.ams.org/journals/bull/1977-83-02/S0002-9904-1977-14307-3/S0002-9904-1977-14307-3.pdf), so in those dimensions your last question collapses to your first question.

EDIT As pointed out by @Lennart Meier in his comment, in fact, every smooth manifold is homeomorphic to a real algebraic variety.

Igor Rivin
  • 95,560
  • thanks, however not every algebraic variety is a manifold (figure 8) and not every semi algebraic set is a variety

    Could you give a hint to: A simplicial complex is a manifold if the links of all vertices are simplicial spheres.

     – Markus Ulke Jul 27 '11 at 14:46
  • 2
    @unknown, hint: the star is the cone on the link. Also problematic is that not every manifold is PL: there are triangulated manifolds with links that are not spheres. – Autumn Kent Jul 27 '11 at 14:52
  • You should check out Rourke and Sanderson's PL topology book... You should also check out this question: http://mathoverflow.net/questions/7492/algebraic-varieties-which-are-topological-manifolds – Igor Rivin Jul 27 '11 at 14:52
  • 4
    Hey Igor, I'm voting this down because not every manifold of dimension 10 is homeomorphic to a real algebraic variety, for example a simply-connected 4-manifold with $E_8$ intersection form: http://en.wikipedia.org/wiki/4-manifold

    Also, as Richard points out, there are manifolds which have a simplicial structure with links of vertices not spheres (like the double suspension of a homology 3-sphere). So although you are correct in saying that if the links of vertices are spheres, it is a manifold, this does not imply that there is no algorithm to tell if it is a manifold.

     – Ian Agol Jul 28 '11 at 00:50
  • 3
    As Richard Kent says, this is the criterion for a PL manifold. There is a known weaker condition for it to be a topological manifold. Something like: the links of vertices are simply connected spaces with the homology of the sphere. (2) Undecidability is about the word problem. n=4 should be decidable because the problem is the links, which are 3-manifolds, which have decidable groups. – Ben Wieland Jul 28 '11 at 03:21
  • @Ben: yes, I meant that the links were 4-dimensional. Presumably what is undecidable is whether the link is simply-connected, so despite Agol's grousing, my undecidability statement is actually correct. – Igor Rivin Jul 28 '11 at 03:41
  • Sorry, I misread. Still, the answer is that recognizing the 4-sphere is undecidable. I think that the standard construction of a 4-manifold with given fundamental group is indistinguishable from the 4-sphere if the group is not distinguishable from trivial. – Ben Wieland Jul 28 '11 at 03:51
  • At least when the standard method is applied to an undecidable group with a balanced presentation. I wonder why Novikov said n=5? Maybe because he didn't have Freedman's theorem and was worried about exotic S^4? – Ben Wieland Jul 28 '11 at 04:03
  • Since there are serious disagreements on factual matters regarding several parts of the answer (see the comments) I suggest that the answer be edited (by Igor or by somebody else) so that it does not contain false or misleading statements. – Gil Kalai Jul 28 '11 at 14:51
  • 1
    @Gil: I don't disagree that the question should be edited (I just need to get around to it), but I don't think there are disagreements, just some confusion about what "manifold" means. I implicitly assumed "PL manifold", but this is obviously not a universal assumption. – Igor Rivin Jul 28 '11 at 22:33
  • @Igor: in dimension 3, Schleimer showed that a variant of the Rubinstein-Thompson algorithm belongs to NP:

    http://www.warwick.ac.uk/~masgar/Maths/np.pdf

    So it's no worse than exponential time; whether it's better hinges on the usual open problems in complexity theory...

     – Dave Futer Jul 29 '11 at 21:09
  • Indeed there is a distinction between being a PL sphere/manifold and being homehomorphic to a sphere/manifold. For the question if a simplicial complex is homehomorphic to a manifold perhaps you can start with an example (a homology sphere) where it is undecidable if the complex is a sphere and then takes a single suspension. I weakly suspect (but dont know for sure) that unlike the case of double suspensions the single suspension will be a manifold (equiv. a sphere) iff the original complex is a sphere. – Gil Kalai Jul 30 '11 at 15:38
5

There is the idea of a simplicial manifold, which works by checking that the complex is pure (all facets of the same dimension) and that each codimension 1 face is included in the correct number of facets.

Beyond this answer to your question a), I believe b) and d) to be potentially really difficult. It would seem to me that almost no simplicial complexes are in themselves smooth (unless you give an explicit embedding, in which case you need to check smoothness for each face separately, or something like that), but that all simplicial manifolds can be deformed into a smooth manifold.

As for c), it seems to reconnect to the criterion for a), but it is not clear to me whether algorithmics exist.

You might want to check out the work by Benjamin Burton.

Mikael Vejdemo-Johansson
  • 2,517
  • 2
    This is usually called a pseudomanifold. It is so much weaker a condition than manifold that I must call this answer wrong. – Ben Wieland Jul 28 '11 at 03:09
  • Novik and Swartz have introduced the notion of a homology manifold, which is much closer to an actual manifold than a pseudo-manifold is, and is an algorithmically checkable condition. See http://www.math.washington.edu/~novik/publications/Gorenstein.pdf For dimension $\leq 3$, a homology manifold is a manifold; in dimension $4$, it is a manifold except for finitely many singularities which are cones on homology $3$-spheres. See their paper for lots more. – David E Speyer Jul 28 '11 at 11:52
  • The term "homology manifold" goes back at least to the 50s, although the term "generalized manifold" was more popular for decades. – Ben Wieland Jul 28 '11 at 16:32
4

(b) When does a PL manifold have a smooth structure?

I believe that this is computable. Smoothing theory, closely related to the Hirsch-Smale immersion theory (an h-principle), identifies the set of smooth structures on a PL manifold with the set vector bundles that are reasonable candidates for the tangent bundle in the sense that they are reductions of structure group of the PL tangent bundle. The theory of principal bundles reduces to homotopy theory. The set of homotopy classes of maps from a finite complex to a finite complex with abelian fundamental group and the induced maps between such sets are computable, but it is rarely implemented.

Ben Wieland
  • 8,667
  • This answer suggests that there is an algorithm to tell if a PL manifold has a smoth structure. However, telling if a simplicial complex is e.g. a PL sphere is known to be undecidable in high dimensions. – Gil Kalai Jul 28 '11 at 14:47