#### by Rob Kirby

In the mid 1950s
A. A. Markov
proved
[e6]
that there could
be no algorithm to distinguish all pairs of closed, compact, smooth
4-manifolds. His proof started with the fact that there is no algorithm
to decide whether a finitely presented group __\( G \)__ is trivial, a fact using
ideas of
Gödel
and proved by
P. S. Novikov
[e1],
[e2]
and
W. W. Boone
[e5]
(also see
[e8]
and
[e9]).

Markov’s proof is in Russian, and not too widely known in the West. Marty
Scharlemann mentioned to me a few years ago that, as a graduate student in the
early 70s, he had wanted to understand Markov’s proof but knew no Russian.
So he looked up the paper in *Mathematical Reviews* and found
the account of the proof there unconvincing,
which led him to work out what he
thought Markov’s argument must have been. Together we mined his memory and
sorted out the proof which is exposited here. To the best of my knowledge
this simple proof is not written up elsewhere (but see
([e10], p. 149)
where the proof is given as an exercise with help from earlier exercises but
contains no hint as to adding __\( g \)__ extra 2-handles; also see
[e11]).

__\( X \)__belonging to a collection

__\( C \)__of manifolds is said to be

*recognizable*if there exists an algorithm which can decide whether or not any manifold

__\( Y \)__in

__\( C \)__is diffeomorphic to

__\( X \)__.

__\[ X^4 = \mathop{\#}\nolimits^k S^2 \times S^2 \]__for some

__\( k > 0 \)__is not recognizable in the collection

__\( C \)__of all smooth, compact, closed 4-manifolds.

__\( G \)__, we can construct a smooth 5-manifold

__\( Y^5_G \)__such that

__\[ \pi_1 (Y_G) = \pi_1(\partial Y_G) = G \]__and

__\( Y_G \)__has no handles of index

__\( > 2 \)__.

*Proof.*
Suppose __\( G \)__ has __\( g \)__ generators __\( g_1 \)__, …, __\( g_g \)__ and __\( r \)__ relations
__\( r_1 \)__, …, __\( r_r \)__. We can construct a 5-manifold __\( Y^5_G \)__ by adding
__\( g \)__ 1-handles to __\( B^5 \)__ (obtaining __\( \mathop{\#}\nolimits^g (S^1 \times B^4) \)__) and then adding
__\( r \)__ 2-handles according to
the relations __\( r_1 \)__, …, __\( r_r \)__. Because the attaching circles lie in
a 4-manifold, these isotopy classes are determined by their homotopy classes
in __\( \mathop{\#}\nolimits^g S^1 \times S^3 \)__ which in turn are determined by the relations.

However a 2-handle __\( B^2 \times B^3 \)__ is attached by an embedding of __\( S^1
\times B^3 \)__ and given the embedding of __\( S^1 \times 0 \)__; there are then two
ways to extend that embedding since
__\[
\pi_1(\mathrm{SO}(3)) = \mathbb{Z}/2.
\]__
For example for the unknot in __\( \partial B^5 \)__, the two framings give __\( S^2
\times B^3 \)__ and the nontrivial __\( B^3 \)__ bundle over __\( S^2 \)__, namely __\( S^2
\mathbin{\tilde{\times}} B^3 \)__. Let __\( Y_G \)__ be defined by any one choice of framings
of the 2-handles.

Two different presentations of __\( G \)__ differ by Tietze moves,
but these moves correspond to the birth or death of a
1-2 handle pair
and to handle slides, and these do not change the 5-manifold __\( Y_G \)__.

The map induced by inclusion,
__\[
\pi_1 (\partial Y_G) \to \pi_1(Y_G),
\]__
is an isomorphism. It is an epimorphism because any loop in __\( Y_G \)__ can
be pushed off the 2-complex
spine of __\( Y_G \)__ and thus into __\( \partial Y_G \)__.
It is a monomorphism for the same reason; if a loop in __\( \partial Y_G \)__
is homotopically trivial in __\( Y_G \)__, then that 2-disk can also be pushed
off the spine and into __\( \partial Y_G \)__.
◻

Now define __\( Y_g \)__ to be __\( Y_G \)__ with __\( g \)__ trivial 2-handles (attached to the
unlink in a small 4-ball in __\( \partial B^5 \)__ which avoids
all other attaching maps, and with the framing on the attaching
circle that gives __\( B^2 \times B^3 \)__ ). Note that
__\[
Y_g = Y_G \mathop{\#}\nolimits^g S^2 \times B^3.
\]__

The proof of the theorem will follow from the next lemma.

__\( G \)__is trivial if and only if

__\[ \partial Y_g = \mathop{\#}\nolimits^r S^2 \times S^2. \]__

*Proof.*
The *if* part follows from
__\[
G = \pi_1(Y_g) = \pi_1 (Y_G) = \pi_1 (\partial Y_G) = 0.
\]__

For the *only if* part, note that
__\[
\pi_1(\partial Y_G) = G =0.
\]__
Then the attaching circles of the __\( g \)__ trivial 2-handles can
be homotoped and thus isotoped in __\( \partial Y_G \)__, to geometrically cancel
the __\( g \)__ 1-handles. (Note that we cannot do this with the original __\( r \)__ 2-handles
because they do not lie in a simply connected 4-manifold, but rather in a
connected sum of products __\( S^1 \times S^3 \)__, whereas
the extra __\( r \)__ 2-handles may
be thought of as
being added to __\( \partial Y_G \)__.) Do the cancellation, and what
remains of __\( Y_g \)__ is an unlink of __\( r \)__ components to
which are attached __\( r \)__ 2-handles, so that __\( Y_g \)__ is
diffeomorphic to __\( \mathop{\#}\nolimits^r S^2 \times B^3 \)__ with boundary __\( \mathop{\#}\nolimits^r S^2 \times S^2 \)__
or the twisted case. However, going back to original __\( r \)__ 2-handles,
we could have chosen their framings so that we avoid the twisted case.
◻

The proof of the Theorem now follows because given a finitely
presented group __\( G \)__, construct
__\( \partial Y_G \)__.
If we had an algorithm to recognize __\( \partial Y_G \)__ as a connected sum
of __\( S^2 \times S^2 \)__s, then we
would
have an algorithm to decide whether __\( G \)__ is the trivial group.

It is still an open question as to whether the 4-sphere is
recognizable, that is,
if there is an algorithm which in finite time will
decide whether a homology 4-sphere __\( H \)__ is diffeomorphic to __\( S^4 \)__.
Possibly the description of __\( H \)__ as a trisection determined by a
diffeomorphism of a 3-dimensional handlebody will lead to such an
algorithm.

Note that there is no algorithm to recognize the __\( n \)__-sphere for __\( n\geq 5 \)__.
Kervaire
[e7]
showed that if a finitely presented
group __\( G \)__ is
superperfect, that is, if
__\[
H^1(G) = H^2(G) =0,
\]__
then it is the
fundamental group of a homology __\( n \)__-sphere __\( H \)__, __\( n > 4 \)__. If the
__\( n \)__-sphere can be recognized, then __\( H = S^n \)__
if and only if __\( \pi_1(H) = 1 \)__ (by
the Poincaré theorem). However the class of
superperfect groups, by the Adjan–Rabin theorem
[e3]
[e4], cannot have an algorithm to recognize the trivial group.