# Can we algorithmically contract loops in a simply connected space?

It is well-known that the question whether a given connected simplicial complex (or simplicial set) is simply connected, is algorithmically undecidable as it can model the word problem.

Assuming that $X$ is simply connected, is there an algorithmic way how to contract loops?

One way how this can be formalized is as follows. $X$ can be a simply connected simplicial set (with either finitely many nondegenerate simplices in each dimension, or at least with effective homology...) and $\tilde{GX}$ the Kan model of the loop space, such as described here. The loop contraction would than be a map $c: \tilde{GX}_0\to \tilde{GX}_1$ such that $d_0 c(x)=x$ and $d_1 c(x)=1$. Is there any hope to have a general algorithm for evaluating $c(x)$?

• @ThomasRot There should be some obstructions in $\pi_2$ to this. If all loops can be uniformly contracted then presumably all the 2-spheroids (and maybe even higher ones) can be contracted too - after all, a 2-sphere is a circle of loops. – მამუკა ჯიბლაძე Sep 11 '16 at 22:11
• This has been widely studied in 2-complexes associated to finite group presentations (whose 1-skeleta are the Cayley graphs). Keywords: Dehn function, automatic groups, etc. – YCor Sep 11 '16 at 22:11
• @ThomasRot What do you do when there is a local minima for energy? It seems you could only use a gradient flow if you know a lot about the metric you put on $X$. – Rbega Sep 12 '16 at 13:58
• @ThomasRot think of a dumbbell. Many loops go to a closed geodesic under the gradient flow of energy. – Benoît Kloeckner Sep 13 '16 at 12:57
• @BenoîtKloeckner: thanks, after the comment of Rbega I thought of this example as well. I've deleted my other comments as they are not relevant to the discussion. – Thomas Rot Sep 13 '16 at 13:42

Start with defining the "standard presentation" for $\pi_1(X)$, namely, construct a maximal subtree $T\subset X^1$. Generators of $\pi_1(X)$ are represented by edges in $X^1 -T$ connecting vertices of $X$. Let $g_i, i=1,..,n$ be the corresponding loops in $X^1$ (based at a vertex $o\in T$). Since $X$ is simply-connected, there exist combinatorial maps $e_i: D^2\to X$ with boundary maps $\partial e_i=g_i$: You find these by listing all combinatorial maps $D^2\to X$ and examining them one-by-one. Now, each based combinatorial loop $g$ in $(X^1,o)$ is a product of the generators $g_i$ and their inverses: $$g= g^{\pm 1}_{i_1}....g^{\pm 1}_{i_k}$$ This is again completely algorithmic since it amounts to reading off the product of the oriented edges in $X^1-T$ as they appear in $g$. Lastly, you read off the maps $e_i$ (and their pre-composition with suitable reflections in $D^2$) according to the word $$w= g^{\pm 1}_{i_1}....g^{\pm 1}_{i_k}.$$
This gives you a combinatorial map $e: D^2\to X$ with $\partial e$ given by $w$. I will leave you the part dealing with constructing a homotopy between the loops $g$ and $w$ inside of $X^1$ (this essentially amounts to contracting $T$ to $o$ and then cancelling the backtracking in $g$).
• @PeterFranek which part of the answer do you find unclear. If this is the part about the generators $g_i$, then yes, the are infinitely many combinatorial maps but because you need to find only n of them the complexity us constant at this stage (independent of $g$). – Moishe Kohan Sep 13 '16 at 2:56
• @PeterFranek, it's clear that the complexity of any such (semi-)algorithm is going to be very large (uncomputable). Otherwise one obtains an algorithmic solution to the triviality problem for groups, which is known to be undecidable. The moral of this is that, if you want an efficient algorithm, you need to use something more about $X$. For instance, does it admit a nice geometry? – HJRW Sep 13 '16 at 8:33