1

Both cohomology and homotopy groups capture global topological information of a manifold $X$. It is interesting to ask if they can be computed from local data. A triangulation $T$ is a natural presentation of a manifold.

The cohomology by definition can be computed from $T$. However, the problem seems much harder for homotopy groups. In fact, humans struggle even for the simplest case $X=S^n$, at least for $\pi_{k>n}(X)$.

Hope is not lost, as we know the answer to $k \leq n$ for spheres. Therefore my question:

Question: Given a triangulated (compact) manifold $X$ of dimension $n$, is there an algorithm that computes $\pi_{k \leq n}(X)$ (up to isomorphism, or in the form of generators and relations)?

Student
  • 5,018
  • Your question is a little imprecise: how do you want the output (e.g., generators and relations)? Certainly somethings around this problem are undecidable so I suspect the answer to your question (once it is made more precise) will be no – Sam Hopkins Apr 18 '22 at 01:06
  • See e.g. https://mathoverflow.net/questions/304481/algorithm-for-computing-fundamental-group-of-simplicial-complexes – Sam Hopkins Apr 18 '22 at 01:20
  • 3
    Another previous MO question you may be interested in: https://mathoverflow.net/questions/31004/computational-complexity-of-computing-homotopy-groups-of-spheres – Sam Hopkins Apr 18 '22 at 01:21
  • Thanks for pointing out the nuance. I have edited accordingly. I was excited about that MO question too, but it seems that the answer there wasn't so clear.. – Student Apr 18 '22 at 01:26
  • Note that for $k\ge 2$ for a closed manifold the $\pi_k$ is abelian, but however can fail to be finitely generated. So, it is unclear what would be meant by "outputting a presentation in terms of generators and relations". – YCor Apr 18 '22 at 08:45
  • @YCor Even when it isn't finitely generated, is it true that we can always describe the generators and relations with an inductive or closed formula? - To others, I've added the "compactness" assumption; that should make them at least finitely generated.. – Student Apr 18 '22 at 09:51
  • It can still fail to be finitely generated if the manifold is compact, as ycor suggests. The problem is the fundamental group. The higher homotopy groups are those of the universal cover. – Thomas Rot Apr 18 '22 at 09:57
  • Oops, saw your first and not your second. I'll remove it. – Lee Mosher Apr 18 '22 at 21:49

2 Answers2

3

Being a manifold or the dimension restriction $k\leq n$ doesn't matter, the following applies to finite simplicial complexes in general:

As others have explained, if the fundamental group is not finite, the higher homotopy groups might be infinitely generated, so in that case even the format of the answer is unclear. Also, it is known that deciding whether a group given by a finite presentation (the simplicial complex gives you such a presentation for $\pi_1$) is actually finite is not possible algorithmically (the halting problem can be reduced to this problem, so if this is problem would admit an algorithmic solution, the halting problem would, too). This problem arises even if you restrict attention to manifolds: Any finite presentation of a group can be turned into an explicit manifold of dimension $4$ or greater via handlebodies.

However, there are algorithms that will produce the list of elements in finite time if $\pi_1$ happens to be finite (and simply never terminate otherwise). From this, it is possible to produce a finite simplicial complex describing the universal cover. For simply-connected finite simplicial complexes, the problem of computing any given homotopy group is known to be be algorithmic, in fact, there exist actual implementations. (I do think they scale pretty badly with degree though).

EDIT: For the $\pi_1$ statement, let me give you an easy but horribly inefficient algorithm. For a finitely presented group $G$, and a finite group $H$ given by a multiplication table, a map $G\to H$ can be specified by finite data: Pick an image for each generator, such that the relations are satisfied. Conversely, a map $H\to G$ can be described by choosing for each element of $H$ a word in the generators of $G$, and for each pair of elements $h_1,h_2\in H$, a finite sequence of rewritings using the relations of $G$, identifying the word associated to $h_1h_2$ with the product of words associated to $h_1,h_2$. For two such maps, a proof witnessing that the composite $G\to H\to G$ is the identity can similarly be specified in a finite amount of data: For each generator, a finite sequence of rewrites identifying it with its image. Similarly for the other composite. So a proof identifying a finitely presented group with a concrete finite group $H$ can be given as a finite bundle of data, now just enumerate all such bundles by size until you found one.

Achim Krause
  • 8,624
  • 1
    For algorithms, note that these seem to available now also in Sage (via the linked Kenzo program): https://www.mdpi.com/2227-7390/9/7/722 --- while they scale badly, it seems that we are now at a point, where they can provide non-trivial (and sometimes unknown) computations in reasonable time. – Lennart Meier Nov 28 '22 at 06:50
  • Thanks for the answer! It may be too much to ask, but could you please point out the algorithm taht produce the list of elements if $\pi_1$ is finite? Also, roughly how does the actual implementation work (in case $\pi_1 = 0$)? On the official page of Kenzo, it points to Xavier's thesis, which is written in pure French (which I don't read). Also, in what sense are the higher groups computed (e.g. as finite presentations?)? – Student Dec 03 '22 at 14:03
  • 1
    Actually, French doesn't seem too different from English, which allowed me to locate the magic. The key to the implementation is given in section 6.3: Assume $X$ is $(n-1)$-connected (and "effective" and "reduced", for computation reasons), where $n \geq 2$. It creates other "effective" and "reduced" spaces $E, E', E'', \ldots, E^{(n)}, \ldots$ from the information of $X$. Finally, it claims that $\pi_{n+k}(X) \simeq H_{n+k}(E^{(k-1)})$! And since homology is easier it's done. Could someone fill in the details of why the homologies of such $E$'s are equivalent of higher homotopy groups of $X$? – Student Dec 03 '22 at 14:23
  • 1
    It's just Hurewicz. More precisely, the $E^{(n)} $ are constructed by killing lower homotopy groups of $X$ without changing the higher ones, and once you're $n-1$-connected $\pi_n$ and $H_n$ agree by Hurewicz. Minus the constructive/effective description of the spaces, this is precisely Serre's method. – Achim Krause Dec 03 '22 at 17:27
  • I added an inefficient algorithm for the claim about finitely presented finite groups. – Achim Krause Dec 03 '22 at 18:25
  • (by the way, I reverted your edit: the Halting problem can be reduced to the word problem for finitely presented groups. So if the word problem could be solved algorithmically, the Halting problem could be, too. The other direction holds as well, of course, but that's not what we use here. Decidable problems can also be reduced to the halting problem.) – Achim Krause Dec 03 '22 at 18:29
  • Thank you @AchimKrause! I understand the Serre's method is basic in algebraic topology, but please forgive me asking a detailed question (involving if such construction can be made functorial) in a separated thread. – Student Dec 03 '22 at 23:39
  • 1
    @AchimKrause Note that the undecidability of the finiteness problem is distinct from the word problem, the former being a consequence of the Adian-Rabin theorem (it is also a consequence of the weaker form of the Adian-Rabin theorem proved by Adian some years before he proved the full one). – Carl-Fredrik Nyberg Brodda Dec 04 '22 at 08:49
  • @AchimKrause I just realized that, by your argument, all $\pi_{k}(S^n)$ is computable in finite time! For some reason my impression suggests that we still don't know most homotopy groups of spheres. Is that really the case? Or do people expect more than the isomorphism types of higher homotopy groups of spheres? – Student Dec 04 '22 at 19:22
  • @Student Well, a lot of open problems are computable in finite time, but that isn't always useful. For example, whether the Riemann hypothesis is true or not is computable in finite time (either the machine that always says "yes" computes it, or the machine that always says "no" computes it; we just don't know which one is right). I suspect (without being an expert on the subject!) that though the order of $\pi_k(S^n)$ is computable in finite time for e.g. $k=1241$ and $n=175$, this doesn't give anything unless one knows e.g. a presentation of $\pi_k(S^n)$ to apply concrete algorithms to!... – Carl-Fredrik Nyberg Brodda Dec 04 '22 at 19:36
  • (contd.) ... and concrete presentations of $\pi_k(S^n)$ are, as pointed out in the last line of the answer before the edit, quite tricky to compute. – Carl-Fredrik Nyberg Brodda Dec 04 '22 at 19:38
  • @Carl-FredrikNybergBrodda: But being tricky to compute is a different kind of problem from being unknown (as is the case for the truth of the Riemann hypothesis). Perhaps the distribution of the primes is a better analogy, since we can in principle compute as many primes as we like, but nevertheless many questions about their distribution (of which RH is one) remain open. – HJRW Dec 05 '22 at 09:28
  • @HJRW Certainly! My comment was just a response to the apprehension that Student seemed to have -- namely that being "computable in finite time" should be synonymous with "problem solved"; they seemed to be leaning towards that their impression "that we still don't know most homotopy groups of spheres" was flawed due to the computability of them, when it is not (for my trivial reasons, and your comment deepens this much further). – Carl-Fredrik Nyberg Brodda Dec 05 '22 at 10:07
  • 1
    @Carl-FredrikNybergBrodda: We're on the same page! But since these issues are subtle, I wanted to point out that "RH is true" is not really a great example of the phenomenon under discussion. Distinguishing "unknown", "undecidable" and "computationally intractable" is exactly the kind of difficulty that people new to these considerations have difficulty with. – HJRW Dec 05 '22 at 10:14
3

Collins and Miller proved that it is algorithmically undecidable whether or not $\pi_2(X)$ is trivial, for $X$ a finite 2-complex. As Achim Krause points out, in general $\pi_2(X)$ is only a module over $\pi_1(X)$, and so it's not clear what kind of a description of it you might want. But the Collins--Miller result shows that any such description that works in general won't be good enough to determine whether or not $\pi_2(X)$ is trivial (much as knowing the generators and relations for $\pi_1(X)$ doesn't enable you to decide whether or not $\pi_1(X)$ is trivial).

You might also like to bear the Whitehead asphericity conjecture in mind.

Whitehead's conjecture: If a 2-complex $X$ is aspherical and $Y$ is a subcomplex of $X$, then $Y$ is also aspherical.

This has been open for 81 years, so is often reckoned to be one of the hardest questions in topology.

For finite $X$, the question can be rephrased as:

If $X$ is obtained by attaching a 2-cell to $Y$ and $\pi_2(Y)$ is non-trivial, must $\pi_2(X)$ be non-trivial?

As this makes clear, we don't really understand the effect that attaching a 2-cell can have on $\pi_2$.

HJRW
  • 24,015
  • Wow, good to know. Just to double-check, this issue goes away completely when $\pi_1(X)$ is finite, right (as shown in Achim Krause's answer and the comments below it)? – Student Dec 03 '22 at 23:42
  • That’s correct. There are some other conditions on $\pi_1$ that can also be useful, but I’ll leave them be unless anyone asks. – HJRW Dec 04 '22 at 06:46
  • If you feel that this thread is a good place to expand. Feel free. Personally I am interested in knowing more about it. Besides finiteness, what sort of conditions would allow higher homotopy groups get computed? References to related papers are also appreciated. – Student Dec 04 '22 at 14:10
  • 1
    Ok! There are various results about 2-complexes saying that if $\pi_1(X)$ satisfies various properties and $H_2(X)=0$ then $\pi_2(X)=0$. Of course, Hurewicz gives this when $\pi_1(X)$ is trivial. Cockcroft proved this when $\pi_1(X)$ is free, and Howie generalised it further, to when $\pi_1(X)$ is locally indicable, meaning that every non-trivial finitely generated subgroup has infinite abelianisation. I don’t know any such results when $H_2(X)$ is non-trivial. – HJRW Dec 04 '22 at 17:07