computing homotopy type

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

Such an algorithm would imply a solution to the word problem! — Fernando Muro, Feb 08 '11 at 18:10
The following answer may be relevant: http://mathoverflow.net/questions/51091/computing-homotopies/132321#132321 . 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 '16 at 18:15

Ryan Budney · Answer 1 · 2011-02-08T19:27:29.987

4

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.

edited Feb 08 '11 at 19:27

answered Feb 08 '11 at 19:07

Ryan Budney

43,013

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 00: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 00: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 04: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
Traditionally the word "homotopy equivalent" does not apply to paths. If you mean "homotopic" then you'd need the sphere to have dimension $n \geq 2$ for it to be true. You could allow $n=1$ if your homotopy does not fix endpoints but from your original question you appear to rule that out. Perhaps this is a terminology issue -- increasingly you seem to be using non-standard terminology. – Ryan Budney Feb 11 '11 at 16:18
Sorry for the term "equivalent", I mean "homotopic". Is the space of homotopy classes from a manifold to a sphere a group at all? How would an algorithm that determines, whether a map from a manifold to sphere (not vice versa) i trivial, imply the "word problem" solution? Thanks, Peter – Peter Franek Feb 22 '11 at 11:31
You're being extremely imprecise, Peter. Presumably you do not mean "space of maps" but perhaps "homotopy-classes of maps"? If you want any object of this form to be a group you have to specify a multiplication -- what kind of multiplication do you want to use? I'm not aware of any general group structure on these kinds of objects. see: http://en.wikipedia.org/wiki/Cohomotopy_group – Ryan Budney Feb 26 '11 at 17:50
Well, what you are saying (if I got it) is, that for a particular map from a circle to a topological space, you can not algorithmically determine, whether it is trivial (if the map is given by a finite set of data, such as simplicial map between simplicial complexes or so). Do you think that if the "second" space is not arbitrary, but a sphere and the "first space" is not a circle but a more arbitrary space, it does not change/simplify the situation? Thanks a lot for all the answers. – Peter Franek Mar 08 '11 at 12:54
2

If the target space is a sphere and the domain space a finite CW-complex then this is a totally reasonable problem. If the target space is a circle then this reduces to a computation in 1-dimensional cohomology, which is an algorithmic problem. If the target space is a higher-dimensional sphere then it's also a managable problem but could potentially require a fair bit of work. – Ryan Budney Mar 08 '11 at 15:54

computing homotopy type

1 Answers1