Title: 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\geq 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\geq 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\geq 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)$.