Celebratio Mathematica

In the mid 1950s A. A. Markov proved [e6] that there could be no al­gorithm to dis­tin­guish all pairs of closed, com­pact, smooth 4-man­i­folds. His proof star­ted with the fact that there is no al­gorithm to de­cide wheth­er a fi­nitely presen­ted group \( G \) is trivi­al, a fact us­ing 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 Rus­si­an, and not too widely known in the West. Marty Schar­le­mann men­tioned to me a few years ago that, as a gradu­ate stu­dent in the early 70s, he had wanted to un­der­stand Markov’s proof but knew no Rus­si­an. So he looked up the pa­per in Math­em­at­ic­al Re­views and found the ac­count of the proof there un­con­vin­cing, which led him to work out what he thought Markov’s ar­gu­ment must have been. To­geth­er we mined his memory and sor­ted out the proof which is ex­pos­ited here. To the best of my know­ledge this simple proof is not writ­ten up else­where (but see ([e10], p. 149) where the proof is giv­en as an ex­er­cise with help from earli­er ex­er­cises but con­tains no hint as to adding \( g \) ex­tra 2-handles; also see [e11]).

Proof.  Sup­pose \( G \) has \( g \) gen­er­at­ors \( g_1 \), …, \( g_g \) and \( r \) re­la­tions \( r_1 \), …, \( r_r \). We can con­struct a 5-man­i­fold \( Y^5_G \) by adding \( g \) 1-handles to \( B^5 \) (ob­tain­ing \( \mathop{\#}\nolimits^g (S^1 \times B^4) \)) and then adding \( r \) 2-handles ac­cord­ing to the re­la­tions \( r_1 \), …, \( r_r \). Be­cause the at­tach­ing circles lie in a 4-man­i­fold, these iso­topy classes are de­term­ined by their ho­mo­topy classes in \( \mathop{\#}\nolimits^g S^1 \times S^3 \) which in turn are de­term­ined by the re­la­tions.

However a 2-handle \( B^2 \times B^3 \) is at­tached by an em­bed­ding of \( S^1 \times B^3 \) and giv­en the em­bed­ding of \( S^1 \times 0 \); there are then two ways to ex­tend that em­bed­ding since \[ \pi_1(\mathrm{SO}(3)) = \mathbb{Z}/2. \] For ex­ample for the un­knot in \( \partial B^5 \), the two fram­ings give \( S^2 \times B^3 \) and the non­trivi­al \( B^3 \) bundle over \( S^2 \), namely \( S^2 \mathbin{\tilde{\times}} B^3 \). Let \( Y_G \) be defined by any one choice of fram­ings of the 2-handles.

Two dif­fer­ent present­a­tions of \( G \) dif­fer by Tiet­ze moves, but these moves cor­res­pond to the birth or death of a 1-2 handle pair and to handle slides, and these do not change the 5-man­i­fold \( Y_G \).

The map in­duced by in­clu­sion, \[ \pi_1 (\partial Y_G) \to \pi_1(Y_G), \] is an iso­morph­ism. It is an epi­morph­ism be­cause any loop in \( Y_G \) can be pushed off the 2-com­plex spine of \( Y_G \) and thus in­to \( \partial Y_G \). It is a mono­morph­ism for the same reas­on; if a loop in \( \partial Y_G \) is ho­mo­top­ic­ally trivi­al in \( Y_G \), then that 2-disk can also be pushed off the spine and in­to \( \partial Y_G \).  ◻

Now define \( Y_g \) to be \( Y_G \) with \( g \) trivi­al 2-handles (at­tached to the un­link in a small 4-ball in \( \partial B^5 \) which avoids all oth­er at­tach­ing maps, and with the fram­ing on the at­tach­ing 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 the­or­em will fol­low from the next lemma.

Proof.  The if part fol­lows 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 at­tach­ing circles of the \( g \) trivi­al 2-handles can be ho­mo­toped and thus iso­toped in \( \partial Y_G \), to geo­met­ric­ally can­cel the \( g \) 1-handles. (Note that we can­not do this with the ori­gin­al \( r \) 2-handles be­cause they do not lie in a simply con­nec­ted 4-man­i­fold, but rather in a con­nec­ted sum of products \( S^1 \times S^3 \), where­as the ex­tra \( r \) 2-handles may be thought of as be­ing ad­ded to \( \partial Y_G \).) Do the can­cel­la­tion, and what re­mains of \( Y_g \) is an un­link of \( r \) com­pon­ents to which are at­tached \( r \) 2-handles, so that \( Y_g \) is dif­feo­morph­ic to \( \mathop{\#}\nolimits^r S^2 \times B^3 \) with bound­ary \( \mathop{\#}\nolimits^r S^2 \times S^2 \) or the twis­ted case. However, go­ing back to ori­gin­al \( r \) 2-handles, we could have chosen their fram­ings so that we avoid the twis­ted case.  ◻

The proof of the The­or­em now fol­lows be­cause giv­en a fi­nitely presen­ted group \( G \), con­struct \( \partial Y_G \). If we had an al­gorithm to re­cog­nize \( \partial Y_G \) as a con­nec­ted sum of \( S^2 \times S^2 \)s, then we would have an al­gorithm to de­cide wheth­er \( G \) is the trivi­al group.

It is still an open ques­tion as to wheth­er the 4-sphere is re­cog­niz­able, that is, if there is an al­gorithm which in fi­nite time will de­cide wheth­er a ho­mo­logy 4-sphere \( H \) is dif­feo­morph­ic to \( S^4 \). Pos­sibly the de­scrip­tion of \( H \) as a tri­sec­tion de­term­ined by a dif­feo­morph­ism of a 3-di­men­sion­al handle­body will lead to such an al­gorithm.

Note that there is no al­gorithm to re­cog­nize the \( n \)-sphere for \( n\geq 5 \). Ker­vaire [e7] showed that if a fi­nitely presen­ted group \( G \) is su­per­per­fect, that is, if \[ H^1(G) = H^2(G) =0, \] then it is the fun­da­ment­al group of a ho­mo­logy \( n \)-sphere \( H \), \( n > 4 \). If the \( n \)-sphere can be re­cog­nized, then \( H = S^n \) if and only if \( \pi_1(H) = 1 \) (by the Poin­caré the­or­em). However the class of su­per­per­fect groups, by the Ad­jan–Ra­bin the­or­em [e3] [e4], can­not have an al­gorithm to re­cog­nize the trivi­al group.