Markov's theorem and algorithmically non-recognizable combinatorial manifolds

M. A. Shtan'ko

Izvestiya. Mathematics , Tome 68 (2004) no. 1, pp. 205-221.

Résumé

We prove the theorem of Markov on the existence of an algorithmically non-recognizable combinatorial $n$-dimensional manifold for every $n\geqslant 4$. We construct for the first time a concrete manifold which is algorithmically non-recognizable. A strengthened form of Markov's theorem is proved using the combinatorial methods of regular neighbourhoods and handle theory. The proofs coincide for all $n\geqslant 4$. We use Borisov's group [8] with insoluble word problem. It has two generators and twelve relations. The use of this group forms the base for proving the strengthened form of Markov's theorem. (The author is indebted to S. I. Adian for this idea.)

Bibliographie

[1] Markov A. A., “Insolubility of the problem of homeomorphy”, Proc. Intern. Congress of Math, Cambrige Univ. Press, Cambrige, 1960, 300–306 | MR

[2] Markov A. A., “Nerazreshimost problemy gomeomorfii”, DAN SSSR, 121:2 (1958), 218–220 | Zbl

[3] Markov A. A., “Nerazreshimost problemy gomeomorfii”, UMN, 13:4 (1958), 213–216

[4] Zeifert G., Trelfall V., Topologiya, GONTI, M., 1938

[5] Boone W. W., Haken W., Poenaru V., “On recursively usolvable problems in topology and their classification”, Contrib. to Math. Logic, North-Holland. Publ. Comp., Amsterdam, 1968, 37–74 | MR

[6] Milnor J., “A procedure for killing homotopy groups of differentiable manifolds”, Proc. Symp. Pure Math., 1961, no. 3, 39–55 | MR | Zbl

[7] Novikov S. P., “Gomotopicheski ekvivalentnye gladkie mnogoobraziya, I”, Izv. AN SSSR. Ser. matem., 28:2 (1964), 365–474 | MR

[8] Borisov V. V., “Prostye primery grupp s nerazreshimoi problemoi tozhdestva”, Matem. zametki, 6 (1969), 521–532 | MR | Zbl

[9] Adyan S. I., “Algoritmicheskaya nerazreshimost problem raspoznavaniya nekotorykh svoistv grupp”, DAN SSSR, 103:4 (1955), 533–535 | MR | Zbl

[10] Adyan S. I., “Nerazreshimost nekotorykh algoritmicheskikh problem teorii grupp”, Tr. MMO, 6, URSS, M., 1957, 231–298 | MR | Zbl

[11] Adyan S. I., Durnev I. G., “Algoritmicheskie problemy dlya grupp i polugrupp”, UMN, 55:2 (2000), 3–94 | MR | Zbl

[12] Rabin M. O., “Recursive unsolvability of group theoretic problems”, Ann. Math., 67 (1958), 172–194 | DOI | MR | Zbl

[13] Freedman M. H., “The Topology of four-dimensional manifolds”, J. Diff. Geom., 17 (1982), 357–453 | MR | Zbl

[14] Siebenmann L. C., “La Conjecture de Poincare Topologique en dimension 4”, Seminare Bourbaki, no. 588, 1981/82

[15] Freedman M. H., Quinn F. S., Topology of 4-manifolds, Princeton Math. Series, 39, Princ. Univ. Press, Princeton–N. J., 1990 | MR | Zbl

[16] Rurk K. P., Sanderson B. Dzh., Vvedenie v kusochno lineinuyu topologiyu, Mir, M., 1974 | MR

[17] Khu S.-Ts., Teoriya gomotopii, Mir, M., 1974

[18] Khilton P., Uaili S., Teoriya gomologii. Vvedenie v algebraicheskuyu topologiyu, Mir, M., 1966

[19] Griffits F. A., Morgan D. B., Ratsionalnaya teoriya gomotopii i differentsialnye formy, Nauka, M., 1990 | MR

[20] Whitehead J. H. C., “Simplicial spaces nuclei and $m$-groups”, Proc. Lond. Math., 45 (1939), 243–327 | DOI | Zbl

[21] Lickorich W. B. R., Siebenmann L. C., “Regular neighbourhoods and the stable range”, Trans. AMS, 139 (1969), 207–230 | DOI | MR

[22] Higman G., Neumann B. H., Neumann H., “Embedding theorem for groups”, J. Lond. Math. Soc., 24 (1949), 247–254 | DOI | MR

[23] Miller C. F. III, “Algorithms and Classification in Combinatorial Group Theory”, Math. Sci. Res. Pub., 23, Springer, N.Y., 1992, 1–59 | MR

[24] Fomenko A. T., Differentsialnaya geometriya i topologiya. Dopolnitelnye glavy, Izhevskaya respublikanskaya tipografiya, Izhevsk, 1999

[25] Volodin N. A., Fomenko A. T., “Mnogoobraziya, uzly, algoritmy”, Tr. seminara po vektornomu i tenzornomu analizu, 1978, no. 18, 94–128 | MR | Zbl

[26] Leksin V. P, Chernavskii A. V., “Neraspoznavaemost mnogoobrazii. K teoreme S. P. Novikova o neraspoznavaemosti sfery $\mathbb S^n$ pri $n\geq5$”, Dokl. RAN, 391:4 (2003), 453–455 | MR | Zbl