8
$\begingroup$

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)$?

$\endgroup$
5
  • $\begingroup$ @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. $\endgroup$ Sep 11, 2016 at 22:11
  • 6
    $\begingroup$ 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. $\endgroup$
    – YCor
    Sep 11, 2016 at 22:11
  • 2
    $\begingroup$ @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$. $\endgroup$
    – Rbega
    Sep 12, 2016 at 13:58
  • $\begingroup$ @ThomasRot think of a dumbbell. Many loops go to a closed geodesic under the gradient flow of energy. $\endgroup$ Sep 13, 2016 at 12:57
  • $\begingroup$ @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. $\endgroup$
    – Thomas Rot
    Sep 13, 2016 at 13:42

1 Answer 1

8
$\begingroup$

I am assuming that you have a complex with finite 2-dimensional skeleton. There is a silly algorithm for contracting loops which is even linear in the combinatorial length of the loop.

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$).

$\endgroup$
13
  • $\begingroup$ Thank you. Can you comment please why is it linear in the length of the loop? I'm not well familiar with combinatorial maps but my feeling is that thee might be quite a lot of them.. $\endgroup$ Sep 12, 2016 at 13:12
  • $\begingroup$ @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$). $\endgroup$ Sep 13, 2016 at 2:56
  • $\begingroup$ I see, this makes sense if the space is fixed. I assumed it is a part of the input. $\endgroup$ Sep 13, 2016 at 4:48
  • 1
    $\begingroup$ @studiosus -- The set of simply connected (finite, 2-dimensional) simplicial complexes is recursively enumerable. Your answer provides a semi-algorithm that certifies if a loop is contractible. Applied to a generating set for the fundamental group of the 1-skeleton, this gives a semi-algorithm that certifies if a complex is simply connected. Now apply this to a recursive list of all finite 2-complexes. $\endgroup$
    – HJRW
    Sep 13, 2016 at 8:30
  • 3
    $\begingroup$ @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? $\endgroup$
    – HJRW
    Sep 13, 2016 at 8:33

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.