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

Filakovský, Marek; Franek, Peter; Wagner, Uli; Zhechev, Stephan

J. Appl. Comput. Topol. 2, No. 3-4, 177-231 (2018).

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)\).

MSC:

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

Keywords:

computational homotopy theory; effective Hurewicz theorem; Whitehead tower

Software:

fKenzo

References:

[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)