Computing simplicial representatives of homotopy group elements

A central problem of algebraic topology is to understand the homotopy groups π_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 π₁(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 π₁(X) trivial), compute 
the higher homotopy group π_d(X) for any given d ≥ 2.

However, these algorithms come with a caveat: They compute the isomorphism type of π_d(X), d ≥ 2, as an abstract 

finitely generated abelian group given by generators and relations, but they work with very implicit representations 

of the elements of π_d(X). 

We present an algorithm that, given a simply connected simplicial complex X, computes π_d(X) and represents its elements 

as simplicial maps from a suitable triangulation of the d-sphere to X. For fixed d, the algorithm runs in time singly exponential 

in size(X), the number of simplices of X. 

Moreover, we prove that this is optimal: For every fixed d ≥ 2, we construct a family of simply connected simplicial complexes X 

such that for any simplicial map representing a generator of π_d(X), the size of the triangulation of S^d on which the map is defined is 

exponential in size(X). 

Apart from the intrinsic importance of homotopy groups, we view this as a first step 

towards the more general goal of computing explicit maps with specific topological properties, 

e.g., computing explicit embeddings of simplicial complexes or counterexamples to Tverberg-type

problems, and towards quantitative bounds on the complexity of such maps.

Joint work with Marek Filakovský, Peter Franek, and Stephan Zhechev