# Computational complexity of computing homotopy groups of spheres

At various times I've heard the statement that computing the group structure of $\pi_k S^n$ is algorithmic. But I've never come across a reference claiming this.

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.

Are there any families for which there are better algorithms, say for the stable homotopy groups of spheres? or $\pi_k S^2$ ?

edit: I asked Francis Sergeraert a few questions related to his project. Apparently it's still an open question as to whether or not there is an exponential run-time algorithm to compute $\pi_k S^2$.

• The classic paper is E H Brown's "Finite Computability of Postnikov Complexes" annals of Mathematics (2) 65 (1957) pp 1-20. He shows, among other things, that the homotopy groups of a simply connected finite simplicial complex are finitely computable. No-one has ever considered the method practical to implement. Jul 8, 2010 at 8:18
• @Mike-Doherty: relevant piece of background reading: this set of slides by Francis Sergeraert which contains an excerpt of E.H.Brown's paper, which in particular shows that not even the author themselves considered the method practical (back in the days). Aug 3, 2017 at 15:53
• Relevant piece of background information, related to Mike-Doherty's comment: this lecture by Francis Sergeraert. Slides in English, the talk itself is clear spoken French. Aug 3, 2017 at 17:42

Francis Sergeraert 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 computed in about 30 seconds. In a 2002 paper, they mention other algorithms by Rolf Schön and by Justin Smith, not implemented at that time.

• "seems capable" sounds a little odd to me. Does that mean it's not an algorithm, more of a heuristic that hasn't broken so far? Jul 9, 2010 at 2:44
• Sorry for the bad phrasing. It is definitely presented as an algorithm, computing for instance the Serre spectral sequence of a fibration if base and fiber are "spaces whith effective homology" (in which case the total spaces also is). The differentials and the final extensions are also calculated (for instance $\pi_6(S^3)=\mathbb{Z}/12$ and not $mathbb{Z}/2+mathbb{Z}/6$, a case which eluded Serre in his thesis). But I haven't gone through all details, nor used Kenzo, hence my reservations. See ams.org/mathscinet-getitem?mr=2262083 for the most recent published account.
– BS.
Jul 9, 2010 at 10:07
• Have these algorithms ever succeeded in computing any new homotopy groups of spheres? Dec 11, 2013 at 12:39
• @MarkGrant: I don’t think it’s been used to find any completely new material, but Kenzo has been used to correct an error in a previously “known” computation of some homotopy groups in the literature. I will try to find the reference. Update. Here is the source: they showed that $\pi_4(\Sigma K(A_4,1)) \simeq \mathbb{Z}/12$, where it had previously-published work had claimed it as $\mathbb{Z}/4$. Dec 11, 2013 at 15:42
• Just to add structure to the information on this page: to the comment below the OP were recently added two links to relevant material due to Francis Sergeraert. Aug 3, 2017 at 17:45

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.

• Of course this is not for spheres, as rational homotopy groups of spheres has a very easy algorithm. Oct 4, 2019 at 22:31

Here's a very useless 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.)

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 non-abelian chain complex of free groups. Its "homology," by a result of Kan, computes $\pi_*(S^n)$.

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.

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!

• I am left wondering how algorithmic the method described above actually is. Specifically, Kan states in his article A combinatorial definition of homotopy groups that the groups $N_k(X)$ need not be finitely generated. So it would seem this method is probably not effective/algorithmic in general. Is this assessment correct? If so, does the method somehow still give rise to an algorithm for computing the homotopy groups of spheres? Feb 5, 2013 at 7:58
• I went through that paper, but I don't think it can be converted into an algorithm. Even if you use the Nielsson-Schreier tools for computing basis of free groups, still you end up with some kind of word problems in general (to compute the "non-commutative homology"). Nov 16, 2016 at 12:39

Weinberger's Computers, rigidity, and moduli: the large-scale fractal geometry of Riemannian moduli space 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 Sullivan's "Infinitesimal computations in topology." Pub. Math. IHÉS, 47 269 (1977), Griffiths and Morgan's Rational Homotopy Theory and Differential Forms, Halperin's "Lectures on minimal models." Mém. Soc. Math. France, Sér. 2, 9-10 1 (1983), and Dwyer's "Tame Homotopy Theory." Topology 18 321 (1979).

The practical upshot of these later references seems to be the calculation of $\pi_k(S^n) \otimes \mathbb{Q}$, or in the case of tame homotopy theory the analogous object involving a finite number of primes (which number increases with dimension).

• But all the interesting information is lost between $\pi_k(S^n)$ and $\pi_k(S^n)\otimes\mathbb{Q}$. Jul 8, 2010 at 19:30
• Good point. But I think inverting a finite number of primes saves some interesting information. Jul 8, 2010 at 20:15

There is the paper of R. V. Mikhailov and J. Wu, http://arxiv.org/abs/1108.3055. 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.

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.

• There is no general algorithm to compute the center of a finitely presentable group. May 9, 2012 at 3:25
• That is what I figured, but know I know. Thanks. May 9, 2012 at 16:33

This is a bit aside from the question at hand, but I think it's worth making the observation. Consider the function of two variables: $$(X,n) \mapsto \pi_n X.$$ As a function of $$n$$, the computational complexity is believed (for general $$X$$) to grow exponentially. But for fixed $$n$$, as a function of simply-connected $$X$$ (measured in terms of, say, number of simplices), the growth of the computational complexity is polynomial.

(In fact, I'd guess that you could even specify the degree of the polynomial to be something like $$n/c$$ where $$c$$ is the connectivity of the $$X$$s. I don't know if anyone has made that precise.)

So if you want to get in the game of making algorithms to compute homotopy groups, don't bother with high-dimensional spheres: it's a waste of effort. Instead, compute low-dimensional homotopy groups of large spaces. (This is basically what the "effective homotopy program" of Sergeraert, Rubio, Romero, and others, does.)

• When you say "the computation complexity is believed" what do you mean? Who believes this? May 6, 2020 at 4:15
• Well, by "exponential", I really just mean "worse than polynomial". And I believe it! The usual evidence which people cite is the Anick paper mentioned in another answer (though it is not directly relevant). We do know that $X\mapsto \pi_k X$ has a polynomial time solution for fixed $k$ for instance in arxiv.org/abs/1211.3093, and therefore in particular if $X=S^n$. May 6, 2020 at 17:02
• Thanks for the clarification, and reference. May 6, 2020 at 17:57