Is there an algorithm to determine if a triangulated 4-manifold is combinatorially equivalent to the 4-sphere?

Importance: High ✭✭✭
Author(s): Novikov
Subject: Topology
Keywords: 4-sphere
algorithm
Recomm. for undergrads: no
Posted by: rybu
on: November 7th, 2009

\begin{problem} Is there an algorithm which takes as input a triangulated 4-manifold, and determines whether or not this manifold is combinatorially equivalent to the 4-sphere? \end{problem}

A 4-manifold triangulation admits a unique smoothing up to diffeomorphism, so this problem is equivalent to asking for an algorithm to determine if a 4-manifold is diffeomorphic to the 4-sphere (with standard differentiable structure). "Combinatorial equivalence" refers to the ability to pass from one triangulation to another via a sequence of Pachner moves.

Rubinstein has an algorithm to determine if a triangulated 3-manifold is combinatorially equivalent to the 3-sphere. A consequence of his algorithm is that there is an algorithm to determine if a 4-dimensional simplicial complex is a 4-manifold triangulation.

It's known that no algorithms exist to determine if a triangulated 4-manifold has a trivial fundamental group, as there is a procedure to construct a compact 4-manifold with any finitely presented fundamental group.

In dimensions 5 and higher, Novikov proved that there is no algorithm to decide whether a given triangulated $n$-manifold is combinatorially equivalent to the $n$-sphere is undecidable [N, CL]. Also, it is undecidable whether a given triangulated 4-manifold is combinatorially equivalent to a connect sum of 14 copies of $S^2 \times S^2$.

Bibliography

[CL] Chernavsky, A. V, and Leskine, V. P., Unrecognizability of manifolds, Annals of Pure and Applied Logic 141 (2006) 325--335.

[N] Novikov, P.S., On the algorithSSSR 85 (5) (19552) 709--712 (in Russian). Algorithmic unsolvability of the problem of identity, Dokl. Akad. Nauk SSSR 85 (5) (1952) 709--712 (in Russian).

[T] Thompson, A. Thin position and the recognition problem for $S^3$. MRL (1994).


* indicates original appearance(s) of problem.