Computing simplicial representatives of homotopy group elements. (English) Zbl 1430.55014

Summary: A central problem of algebraic topology is to understand the homotopy groups \(\pi _d(X)\) of a topological space \(X\). For the computational version of the problem, it is well known that there is no algorithm to decide whether the fundamental group \(\pi _1(X)\) of a given finite simplicial complex \(X\) is trivial. On the other hand, there are several algorithms that, given a finite simplicial complex \(X\) that is simply connected (i.e., with \(\pi _1(X)\) trivial), compute the higher homotopy group \(\pi _d(X)\) for any given \(d\ge 2\). However, these algorithms come with a caveat: They compute the isomorphism type of \(\pi _d(X), d\ge 2\) as an abstract finitely generated abelian group given by generators and relations, but they work with very implicit representations of the elements of \(\pi _d(X)\). Converting elements of this abstract group into explicit geometric maps from the \(d\)-dimensional sphere \(S^d\) to \(X\) has been one of the main unsolved problems in the emerging field of computational homotopy theory. Here we present an algorithm that, given a simply connected space \(X\), computes \(\pi _d(X)\) and represents its elements as simplicial maps from a suitable triangulation of the \(d\)-sphere \(S^d\) to \(X\). For fixed \(d\), the algorithm runs in time exponential in \(\text{size}(X)\), the number of simplices of \(X\). Moreover, we prove that this is optimal: For every fixed \(d\ge 2\), we construct a family of simply connected spaces \(X\) such that for any simplicial map representing a generator of \(\pi _d(X)\), the size of the triangulation of \(S^d\) on which the map is defined, is exponential in \(\text{size}(X)\).


55U10 Simplicial sets and complexes in algebraic topology
55Q05 Homotopy groups, general; sets of homotopy classes
68W30 Symbolic computation and algebraic computation


Full Text: DOI arXiv


[1] Adyan, SI, Algorithmic unsolvability of problems of recognition of certain properties of groups, Dokl. Akad. Nauk SSSR (NS), 103, 533-535, (1955) · Zbl 0065.00901
[2] Anick, D.J.: The computation of rational homotopy groups is #\(\wp \)-hard. In: Proceedings of the Conference on Computers in Geometry and Topology, Chicago/IL, 1986, Lecture Notes in Pure and Application Mathematics, vol. 114, pp. 1-56 (1989)
[3] Barratt, M.: Simplcial and Semisimplicial Complextes. Mimeographed Lecture Notes. Princeton University, Princeton (1956)
[4] Berger, C.: An effective version of the Hurewicz theorem. Theses, Université Joseph-Fourier—Grenoble I, (1991). https://tel.archives-ouvertes.fr/tel-00339314
[5] Berger, C., Un groupoïde simplicial comme modèle de l’espace des chemins, Bull. Soc. Math. Fr., 123, 1-32, (1995) · Zbl 0820.18005
[6] Brown, EH, Finite computability of Postnikov complexes, Ann. Math., 2, 1-20, (1957) · Zbl 0077.16804
[7] Čadek, M., Krcál, M., Matoušek, J., Vokřínek, L., Wagner, U.: Extending continuous maps: polynomiality and undecidability. In: STOC, pp. 595-604 (2013a) · Zbl 1294.68089
[8] Čadek, M.; Krčál, M.; Matoušek, J.; Vokřínek, L.; Wagner, U., Extendability of continuous maps is undecidable, Discrete Comput. Geom., 51, 24-66, (2013) · Zbl 1358.68297
[9] Čadek, M.; Krčál, M.; Matoušek, J.; Sergeraert, F.; Vokřínek, L.; Wagner, U., Computing all maps into a sphere, J. ACM, 61, 17:1-17:44, (2014) · Zbl 1295.68196
[10] Čadek, M.; Krčál, M.; Matoušek, J.; Vokřínek, L.; Wagner, U., Polynomial-time computation of homotopy groups and Postnikov systems in fixed dimension, SIAM J. Comput., 43, 1728-1780, (2014) · Zbl 1320.68099
[11] Čadek, M.; Krčál, M.; Vokřínek, L., Algorithmic solvability of the lifting-extension problem, Discrete Comput. Geom., 57, 1-51, (2017) · Zbl 1373.55018
[12] Edelsbrunner, H., Grayson, D.R.: Edgewise subdivision of a simplex. In: Proceedings of the Fifteenth Annual Symposium on Computational Geometry, SCG ’99, pp. 24-30, New York, NY, USA, 1999. ACM · Zbl 0968.51016
[13] Edelsbrunner, H., Harer, J.L.: Computational Topology. American Mathematical Society, Providence, RI (2010) · Zbl 1193.55001
[14] Ferry, S.; Weinberger, S., Quantitative algebraic topology and lipschitz homotopy, Proc. Natl. Acad. Sci., 110, 19246-19250, (2013) · Zbl 1302.57060
[15] Filakovský, M.: Effective chain complexes for twisted products. Preprint (2012). arXiv:1209.1240
[16] Filakovský, M., Vokřínek, L.: Are two given maps homotopic? An algorithmic viewpoint (2013). Preprint arXiv:1312.2337
[17] Franek, P.; Krčál, M., Robust satisfiability of systems of equations, J. ACM, 62, 26:1-26:19, (2015) · Zbl 1423.68208
[18] Freedman, M.; Krushkal, V., Geometric complexity of embeddings in \({\mathbb{R}}^d\), Geom. Funct. Anal., 24, 1406-1430, (2014) · Zbl 1366.57013
[19] Fritsch, R., Piccinini, R.A.: Cellular Structures in Topology. Cambridge Studies in Advanced Mathematics, vol. 19. Cambridge University Press, Cambridge (1990). https://doi.org/10.1017/CBO9780511983948 · Zbl 0837.55001
[20] Geoghegan, R.: Topological Methods in Group Theory. Graduate Texts in Mathematics. Springer, New York (2007). https://books.google.at/books?id=BwX6gblqV8MC
[21] Goerss, P.G., Jardine, J.F.: Simplicial Homotopy Theory. Birkhäuser, Basel (1999) · Zbl 0949.55001
[22] Gromov, M.: Quantitative homotopy theory. In: Rossi, H. (ed.) Prospects in Mathematics: Invited Talks on the Occasion of the 250th Anniversary of Princeton University, pp. 45-49 (1999) · Zbl 0927.57022
[23] Haefliger, A.: Plongements différentiables dans le domaine stable. Comment. Math. Helv. 37, 155-176 (1962/1963) · Zbl 0186.27302
[24] Hatcher, A.: Algebraic Topology. Cambridge University Press, Cambridge (2001) · Zbl 1044.55001
[25] Heras, J.; Pascual, V.; Rubio, J.; Sergeraert, F., fKenzo: a user interface for computations in algebraic topology, J. Symb. Comput., 46, 685-698, (2011) · Zbl 1211.55002
[26] Jardine, JF, Simplicial approximation, Theory Appl. Categ., 12, 34-72, (2004) · Zbl 1062.55019
[27] Kan, D.: The Hurewicz theorem. In: International Symposium of Algebraic Topology, Autonomous University of Mexico and UNESCO, pp. 225-231 (1958a)
[28] Kan, DM, A combinatorial definition of homotopy groups, Ann. Math., 67, 282-312, (1958) · Zbl 0091.36901
[29] Kannan, R.; Bachem, A., Polynomial algorithms for computing the Smith and Hermite normal forms of an integer matrix, SIAM J. Comput., 8, 499-507, (1981) · Zbl 0446.65015
[30] Kochman, S.O.: Stable Homotopy Groups of Spheres: A Computer-Assisted Approach. Lecture Notes in Mathematics, vol. 1423. Springer, Berlin (1990) · Zbl 0688.55010
[31] Krčál, M.; Matoušek, J.; Sergeraert, F., Polynomial-time homology for simplicial Eilenberg-MacLane spaces, Found. Comput. Math., 13, 935-963, (2013) · Zbl 1295.68201
[32] Mabillard, I., Wagner, U.: Eliminating higher-multiplicity intersections, II. The deleted product criterion in the \(r\)-metastable range. In: Proceedings of the 32nd International Symposium on Computational Geometry (SoCG 2016), pp. 51:1-51:12 (2016) · Zbl 1390.57015
[33] Matoušek, J.: Computing higher homotopy groups is \(W[1]\)-hard. Fund. Inf. (2014). Preprint arXiv:1304.7705
[34] Matoušek, J.; Tancer, M.; Wagner, U., Hardness of embedding simplicial complexes in \({\mathbb{R}}^d\), J. Eur. Math. Soc., 13, 259-295, (2011) · Zbl 1208.68130
[35] Matoušek, J., Sedgwick, E., Tancer, M., Wagner, U.: Embeddability in the 3-sphere is decidable. In: Proceedings of the Thirtieth Annual ACM Symposium on Computational Geometry, SOCG’14, pp. 78-84, New York, NY, USA (2014) · Zbl 1395.68310
[36] Matveev, S.: Algorithmic Topology and Classification of 3-Manifolds. Springer, Berlin (2007) · Zbl 1128.57001
[37] May, J.P.: Simplicial Objects in Algebraic Topology. Chicago Lectures in Mathematics. University of Chicago Press, Chicago (1992). (reprint of the 1967 original) · Zbl 0769.55001
[38] Munkres, J.R.: Elements of Algebraic Topology. Addison-Wesley, Reading, MA (1984) · Zbl 0673.55001
[39] Quillen, D.G.: Homotopical Algebra. Lecture Notes in Mathematics. Springer, Berlin (1967) · Zbl 0168.20903
[40] Rabin, MO, Recursive unsolvability of group theoretic problems, Ann. Math., 2, 172-194, (1958) · Zbl 0079.24802
[41] Ravenel, D.C.: Complex Cobordism and Stable Homotopy Groups of Spheres, 2nd edn. American Mathematical Society, Providence (2004) · Zbl 1073.55001
[42] Real, P., An algorithm computing homotopy groups, Math. Comput. Simul., 42, 461-465, (1996) · Zbl 1037.55502
[43] Romero, A.; Sergeraert, F., Effective homotopy of fibrations, Appl. Algebra Eng. Commun. Comput., 23, 85-100, (2012) · Zbl 1253.55011
[44] Romero, A.; Sergeraert, F., A Bousfield-Kan algorithm for computing the effective homotopy of a space, Found. Comput. Math., 17, 1-32, (2016)
[45] Romero, A.; Rubio, J.; Sergeraert, F., Computing spectral sequences, J. Symb. Comput., 41, 1059-1079, (2006) · Zbl 1132.55008
[46] Rubio, J.; Sergeraert, F., Constructive algebraic topology, Bull. Sci. Math., 126, 389-412, (2002) · Zbl 1007.55019
[47] Rubio, J.; Sergeraert, F., Algebraic models for homotopy types, Homol. Homotopy Appl., 17, 139-160, (2005) · Zbl 1088.55006
[48] Rubio, J., Sergeraert, F.: Constructive homological algebra and applications. Preprint arXiv:1208.3816 (2012)
[49] Schön, R.: Effective Algebraic Topology. Memoirs of the American Mathematical Society. American Mathematical Society, Providence (1991)
[50] Sergeraert, F., The computability problem in algebraic topology, Adv. Math., 104, 1-29, (1994) · Zbl 0823.55011
[51] Smith, J.R.: m-Structures determine integral homotopy type. Preprint arXiv:math/9809151v1 (1998)
[52] Soare, RI, Computability theory and differential geometry, Bull. Symb. Logic, 10, 457-486, (2004) · Zbl 1085.03033
[53] Vokřínek, L., Decidability of the extension problem for maps into odd-dimensional spheres, Discrete Comput. Geom., 57, 1-11, (2017) · Zbl 1362.68281
[54] Weber, C., Plongements de polyèdres dans le domaine metastable, Comment. Math. Helv., 42, 1-27, (1967) · Zbl 0152.22402
[55] Zomorodian, A.J.: Topology for Computing. Cambridge Monographs on Applied and Computational Mathematics, vol. 16. Cambridge University Press, Cambridge (2005)
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.