Computing simplicial representatives of homotopy group elements
Uli Wagner (Institute of Science and Technology Austria)
MSRI: Simons Auditorium
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 π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 π1(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 Sd 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