Undecidability of contractibility

In the last post, we discussed Voevodsky’s homotopy type theory. One of the important notions is whether a space is contractible, this being the base case for the inductive definition of homotopy levels. It turns out that the algorithmic undecidability of whether a finite simplicial complex is contractible appears not to have been discussed much, the result instead buried in Appendix A of an arXiv paper. The strongest version of the result is:

• It is undecidable to determine whether a finite 4-dimensional simplicial complex is contractible or not.

An analogous result about fundamental groups, also worth mentioning, can be proved immediately from the undecidability of the word problem in groups:

• It is undecidable to determine whether a finite 2-dimensional simplicial complex is simply-connected or not.

(Proof: we can consider the presentation complex of any finitely-presented group G, where we take a single point, together with a loop for every generator, and a disc for every relator. This has fundamental group isomorphic to G. After two successive applications of barycentric subdivision, we obtain an abstract simplicial complex homotopy-equivalent to the original presentation complex.)

Clearly, the ‘2’ in the second theorem cannot be lowered; a 1-dimensional simplicial complex is a graph, and it is easy to verify whether or not it is a tree (equivalent to both contractibility and simply-connectedness). I believe it is unknown as to whether the ‘4’ in the first theorem can be lowered to 3 or even 2.

This entry was posted in Uncategorized. Bookmark the permalink.

One Response to Undecidability of contractibility

1. Sam Shepherd says:

That first result is an interesting one that I haven’t heard before. I don’t think the second result follows directly from the undecidability of the word problem, but rather follows from the fact that there is no uniform algorithm to decide if a finitely presented group is trivial – although the two are related by 4.3 in Maurice Chiodo’s course notes here https://www.dpmms.cam.ac.uk/~mcc56/teaching/2016-17/Part%20III%20Decision%20problems%20in%20group%20theory%202016-17/Course%20notes/Part%20III%20Decision%20Problems%20in%20Group%20Theory%20notes%202016-17%20v4%20FINAL.pdf