Question

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

Answer 1

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.