Computational complexity of computing homotopy groups of spheres - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-23T10:20:43Z http://mathoverflow.net/feeds/question/31004 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/31004/computational-complexity-of-computing-homotopy-groups-of-spheres Computational complexity of computing homotopy groups of spheres Ryan Budney 2010-07-08T07:37:55Z 2012-05-09T03:16:23Z <p>At various times I've heard the statement that computing the group structure of $\pi_k S^n$ is <em>algorithmic</em>. But I've never come across a reference claiming this. </p> <p>Is there a precise algorithm written down anywhere in the literature? Is there one in folklore, and if so what are the run-time estimates? Presumably they're pretty bad since nobody seems to ever mention them. </p> <p>Are there any families for which there are better algorithms, say for the stable homotopy groups of spheres? or $\pi_k S^2$ ? </p> http://mathoverflow.net/questions/31004/computational-complexity-of-computing-homotopy-groups-of-spheres/31033#31033 Answer by Steve Huntsman for Computational complexity of computing homotopy groups of spheres Steve Huntsman 2010-07-08T12:21:43Z 2010-07-08T12:29:32Z <p>Weinberger's <em><a href="http://books.google.com/books?hl=en&amp;lr=&amp;id=CtvmQiuOKSEC" rel="nofollow">Computers, rigidity, and moduli: the large-scale fractal geometry of Riemannian moduli space</a></em> contains several apparently useful references on pages 93-4, in the notes section of the chapter on designer homology spheres (which you may also find of interest). Weinberger mentions "the algorithmic nature of simply connected homotopy theory" and cites the paper of Brown that Mike mentioned before going on to cite <a href="http://www.numdam.org/item?id=PMIHES_1977__47__269_0" rel="nofollow">Sullivan's "Infinitesimal computations in topology." <em>Pub. Math. IHÉS</em>, <strong>47</strong> 269 (1977)</a>, Griffiths and Morgan's <em><a href="http://books.google.com/books?id=J13vAAAAMAAJ" rel="nofollow">Rational Homotopy Theory and Differential Forms</a></em>, <a href="http://www.numdam.org/numdam-bin/fitem?id=MSMF_1983_2_9-10__1_0" rel="nofollow">Halperin's "Lectures on minimal models." <em>Mém. Soc. Math. France, Sér. 2</em>, <strong>9-10</strong> 1 (1983)</a>, and <a href="http://www.ams.org/mathscinet-getitem?mr=81a%3A55020" rel="nofollow">Dwyer's "Tame Homotopy Theory." <em>Topology</em> <strong>18</strong> 321 (1979)</a>. </p> <p>The practical upshot of these later references seems to be <a href="http://books.google.com/books?id=_lyvEYswFDoC&amp;pg=PA210" rel="nofollow">the calculation of $\pi_k(S^n) \otimes \mathbb{Q}$</a>, or in the case of tame homotopy theory the analogous object involving a finite number of primes (which number increases with dimension).</p> http://mathoverflow.net/questions/31004/computational-complexity-of-computing-homotopy-groups-of-spheres/31042#31042 Answer by BS for Computational complexity of computing homotopy groups of spheres BS 2010-07-08T13:42:20Z 2010-07-08T13:42:20Z <p><a href="http://www-fourier.ujf-grenoble.fr/~sergerar/" rel="nofollow">Francis Sergeraert</a> and his coworkers have implemented his effective algebraic topology theory in a program named Kenzo. It seems capable of computing any $\pi_n(S^k)$ (in fact homotopy groups of any simply connected finite CW complex), although I don't know how far it is feasible. For instance $\pi_6 S^3$ is <a href="http://www-fourier.ujf-grenoble.fr/~sergerar/Papers/Genova-1.txt" rel="nofollow">computed</a> in about 30 seconds. In a 2002 <a href="http://www-fourier.ujf-grenoble.fr/~sergerar/Papers/Constructive-AT.pdf" rel="nofollow">paper</a>, they mention other algorithms by Rolf Schön and by Justin Smith, not implemented at that time.</p> http://mathoverflow.net/questions/31004/computational-complexity-of-computing-homotopy-groups-of-spheres/96367#96367 Answer by Igor Rivin for Computational complexity of computing homotopy groups of spheres Igor Rivin 2012-05-08T20:07:09Z 2012-05-08T20:07:09Z <p>It is shown by D. J. Anick in The computation of rational homotopy groups is #℘-hard. Computers in geometry and topology, Proc. Conf., Chicago/Ill. 1986, Lect. Notes Pure Appl. Math. 114, 1–56, 1989. that, well, the computation of rational homotopy groups is #p-hard.</p> http://mathoverflow.net/questions/31004/computational-complexity-of-computing-homotopy-groups-of-spheres/96385#96385 Answer by Sean Tilson for Computational complexity of computing homotopy groups of spheres Sean Tilson 2012-05-08T22:17:58Z 2012-05-08T22:17:58Z <p>There is the paper of R. V. Mikhailov and J. Wu, <a href="http://arxiv.org/abs/1108.3055" rel="nofollow">http://arxiv.org/abs/1108.3055</a>. They construct a group whose center is an unstable homotopy group of either a sphere or a Moore space. So now it seems we could apply our algorithmic understanding of computing centers of groups, which might not be much or might be a lot, to unstable homotopy groups.</p> <p>I would imagine this would be easier to work into an algorithm, perhaps this has already been done. However, I am always unsure about these things, sometimes the word problem is hiding in the shadows.</p> http://mathoverflow.net/questions/31004/computational-complexity-of-computing-homotopy-groups-of-spheres/96397#96397 Answer by John Klein for Computational complexity of computing homotopy groups of spheres John Klein 2012-05-09T01:32:11Z 2012-05-09T03:16:23Z <p>Here's a very <em>useless</em> algorithm due to Kan: Let $G(S^n)$ be the simplicial group that is Kan loop group of the $n$-sphere. In each simplicial degree, it is a free group. (This simplicial group has the homotopy type of the based loop space of $S^n$, so its homotopy groups compute the homotopy groups of $S^n$ shifted by one degree.)</p> <p>For each simplicial degree $k$ define $N_k(S^n) \subset G_k(S^n)$ to be the intersection of the kernels of all but the last face maps $d_i: G_k(S^n) \to G_{k-1}(S^n)$. Then the last face map is a homomorphism $d_k: N_k(S^n) \to N_{k-1}(S^n)$. Moreover, the simplicial identities show $d_kd_{k+1}$ has constant value $1$, so we get a <em>non-abelian chain complex</em> of free groups. Its "homology," by a result of Kan, computes $\pi_*(S^n)$.</p> <p>To get an algorithm for computing this homology, recall that the proof of the Nielsen-Schrier theorem gives a system of generators for the subgroup of any free group. So we obtain a system of generators for $N_k(S^n)$ as well as a system of generators for the image of $d_{k+1}$. So in principle we obtain a method for computing the homotopy groups of spheres.</p> <p>In Kan's paper, $\pi_3(S^2)$ is computed in this way, and it takes several pages––so it's not a very good algorithm! </p>