Computing simplicial representatives of homotopy group elements

Abstract

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$. %The first such algorithm was given by Brown, and more recently, Čadek et al. However, these algorithms come with a caveat: They compute the isomorphism type of ${\pi }_d(X)$, $d\ge 2$ as an \emph{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 $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 $size(X)$.