MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

I'm trying to construct a computer algorithm that decides, whethear a map is homotopically trivial and came to the following question: Let U by a connected closed hypersurface of dimension n-1 that is a union of a finite number of n-1-dimensional "cubes" in $\mathbb{R}^n$. Let L by the set of vertices of these cubes. Let Z be a finite set in $\mathbb{Z}^m-\lbrace 0\rbrace$, $Z=\lbrace (a_1,\ldots,a_m)\neq(0\ldots 0), |a_i|\leq M, a_i\in\mathbb{Z}\rbrace$. Let as define a graph G such that (1) vertices are maps from $U$ fo $\mathbb{R}^m-\lbrace 0\rbrace$, continuous and linear on each "cube face" ($U$ constists of a finite number of cubes) such that f maps the vertices $L$ to the set Z and (2) two vertices $v_1$ and $v_2$ of this graph are connected by an edge (in the graph), iff the map $t v_1 + (1-t)v_2$, $t\in [0,1]$ is to $\mathbb{R}^m-\lbrace 0 \rbrace$. L and Z are finite, so the graph is finite. The question is: are $v_1$ and $v_2$ in a different homotopy classes (as maps from $U$ to $\mathbb{R}^m-\lbrace 0\rbrace\simeq S^{m-1}$) if and only they are in the same connected component of this graph? In other words: if I can connect two piece-wise linear functions by a homotopy, can I connect them by a finite number of "linear homotopies" such that the vertices L are mapped to Z? Or, does it depend on the constant M? Or could you give me some other advice..? Thanks, Peter

share|cite|improve this question
Such an algorithm would imply a solution to the word problem! – Fernando Muro Feb 8 '11 at 18:10
The following answer may be relevant:… . But 2-dimensional rewriting is probably not algorithmically solvable. On the other hand, J.H.C. Whitehead's ideas on Simple Homotopy Theory (SHT) were thought up in terms of generalising to higher dimensions Tietze transformations in group theory. The notions in SHT of expansions and collapses give possible connections with the combinatorial use of "shellability". – Ronnie Brown Mar 20 at 18:15

As Fernando mentions, the desire to have an algorithm to determine if two maps are homotopic, generally-speaking is impossible to satisfy. This is because some such complexes have unsolvable word problem in their fundamental group presentations. There are (many) complexes that do not have this kind of trouble, but what this means is that any algorithm you write will not work for general complexes.

The answer to your question about replacing homotopies by linear homotopies is yes -- just think through what the Seifert VanKampen theorem says about your 2-complex. The problem is you don't know what linear homotopies to apply as there's too many of them. One of the "killer" linear homotopies is one where you introduce cancelling pairs $gg^{-1}$. You don't know how much longer you need to make a word before you "spot" a relation. That kind of thing.

share|cite|improve this answer
Thank you for your comment. However, I did not intend to compute the homotopy groups or so in general. The algorithm I hope for is much less: to check only for a given particular piece-wise linear map, whether it is homotopically trivial. And if it is trivial, whether in such case there exists a finite path of piecewise linear homotopies between some piece-wise linear maps, using only a finite set of such maps. But probably, even this is too much to hope :-( – Peter Franek Feb 10 '11 at 0:42
Solving the word problem is exactly what you're asking to do. Checking if a map from a circle to a 2-complex is null homotopic is the word problem, just stated in a slightly different (but equivalent) form. So what you're looking to do is algorithmically impossible. You could of course write an algorithm that may fail infrequently, but it's guaranteed that there are examples it will get stuck on. The software such as GAP and Magnus do these kinds of things quite capably. – Ryan Budney Feb 10 '11 at 15:56
Well, my map is not from a sphere to a cell-complex, but from a cell-complex (morover, compact manifold) to the sphere. Does it not change the situation? – Peter Franek Feb 11 '11 at 0:46
If you're interested in knowing whether or not two paths are homotopic, yes, you're dealing with the word problem and algorithmically there are fundamental problems (unless you know you're dealing with particularly special cell complexes but from your description it sounds like you're dealing with completely general complexes). – Ryan Budney Feb 11 '11 at 4:49
Well, any two pathes in a shpere are homotopy equivalent. Does the space of "homotopy classes" from a manifold to the sphere form a "group" at all? Maybe I'm missing something important.. – Peter Franek Feb 11 '11 at 14:13

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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