# Computing homotopy groups of X such that pi_1(X) has solvable word problem

The paper

E. H. Brown, Jr., Finite computability of Postnikov complexes, Ann. of Math. (2) 65 (1957), 1-20.

proves that if $X$ is a finite simply-connected simplicial complex, then there is an effective algorithm to compute $\pi_k(X)$ for all $k$.

Question : What is known when $X$ is not simply connected?

Of course, this will depend on $\pi_1(X)$, so the more precise question is to fix a finitely presentable group $G$ and to ask whether the homotopy groups $\pi_k(X)$ for $k \geq 2$ are computable for a finite simplicial complex $X$ such that $\pi_1(X) \cong G$. Probably we should also fix a presentation for $G$ and also fix an explicit isomorphism $\pi_1(X) \stackrel{\cong}{\longrightarrow} G$; this gets around the fact that the isomorphism problem is not solvable.

In the best case, one would also be able to compute the action of $\pi_1(X)$ on the higher homotopy groups.

I would expect that the answer is no'' if $G$ is sufficiently terrible; for instance, if $G$ does not have a solvable word problem. However, it seems reasonable that if $G$ is nice enough (eg has solvable word and maybe conjugacy problem) then the problem is solvable.

-
This is probably missing the point, but of course if $\pi_1(X)$ is finite, the universal cover of $X$ is a finite simply connected simplicial complex with the same higher homotopy groups as $X$; now invoke Brown's result. –  Craig Westerland Jan 2 '13 at 0:36
@Craig Westerland : Of course, the real interest is in infinite fundamental groups. And things can definitely be more complicated; for instance, the groups need not be finitely generated (eg $\pi_2(S^1 \vee S^2)$). –  Martin Jan 2 '13 at 0:43
@Yves Cornulier : I'm not sure if they are all finitely generated as modules over $π_1$ (I seem to remember reading a counterexample to this once, but I don't remember it right now). I agree that it is a little unclear, but the question is about what is known, so it seems best to leave it be. –  Martin Jan 2 '13 at 1:22
" Probably we should also fix a presentation for G and also fix an explicit isomorphism $\pi_1⁢(X)\stackrel{\cong}{\to}G$; this gets around the fact that the isomorphism problem is not solvable." You don't need to do this. A naive enumeration will find such an isomorphism, since one exists. The difficulty in the isomorphism problem is to prove that two groups are not isomorphic. –  HJRW Jan 2 '13 at 8:05
Not sure what it would mean to compute $\pi_2$ of a presentation complex for Stallings' group: jstor.org/stable/2373106?origin=crossref –  Ian Agol Jan 2 '13 at 18:41

There are a number of questions arising from this question.

Firstly, what can one really explicitly compute or calculate by the methods given by E.H. Brown?

Secondly, we should also try to compute $\pi_n, n \geq 2$ as a module over $\pi_1$, as the example of $S^n \vee S^1$ shows. However even seeing $\pi_2 X$ as a $\pi_1(X)$-module still gives only a pale shadow of the $2$-type.

Thirdly, the emphasis on computing in EH Brown's paper is via the Postnikov system, which has problems. Saunders Mac Lane remarked to me in 1972 that it would seem impractical to try to compute the homotopy $2$-type of a union since you would first have to compute $\pi_2$ as a module over $\pi_1$; and then somehow describe the $k$-invariant of the union in terms of the $k$-invariants of the individual pieces. Each step, apart from the computation of $\pi_1$ by the theorem of Seifert-van Kampen, seems pretty difficult. Also one can presumably specify a cocycle, but how does one specify a cohomology class?

A different approach was taken by Higgins and me in a paper published in the Proc. LMS (1978), available here as [31], and which follows the lead of J.H.C. Whitehead in his paper Combinatorial Homotopy II, and his paper with Mac Lane On the $3$-type of a complex" , Proc. Nat. Acad. Sci. U.S.A. 36 (1950) 41--48, which we now call $2$-type. They describe the $2$-type of a connected complex $K$ (with base point) in terms of the crossed module $(\pi_2(K, K^1) \to \pi_1(K^1))$, which we write as $\Pi_2(K)$.

Now suppose that $K$ is the union of subcomplexes $L,M$ with intersection $N$. Our generalisation of the Seifert-van Kampen Theorem to dimension $2$ implies that the following diagram:

$$\matrix{\Pi_2(N)&\to & \Pi_2(M) \cr \downarrow && \downarrow\cr \Pi_2(L) & \to & \Pi_2(K) }$$ is a pushout of crossed modules.

This gives a complete determination of $\Pi_2(K)$ which, using also the notion of free crossed module, can be translated into terms of presentations of crossed modules. In some cases this also yields finite calculations of the pushout.

Notice that this result gives in principle" a determination of $$\pi_2(K)= Ker (\pi_2(K,K^1) \to \pi_1(K^1))$$ as a $\pi_1(K)$-module, but it not so obvious how to give explicit computations. Thus this method is the reverse of the traditional method, which proposes to compute first $\pi_2$ and then the $2$-type!

The properties of the pairs of complexes $(X,X^1)$ for $X=L,M,N$ that are required for this pushout are that the individual spaces are connected and non empty, and that $\pi_1(X^1) \to \pi_1(X)$ is surjective: we then say that $(X,X^1)$ is {\it connected}. Part of the theorem is that then the union $(K,K^1)$ is also connected.

Note that the result involves in general nonabelian groups, and so is not available through traditional tools of algebraic topology; current proofs involve some form of $2$-dimensional homotopy groupoids.

These results would seem to be relevant to work in geometric group theory. Full details of the above results and their applications are given in Part I of the book titled in part Nonabelian algebraic topology, which also shows how parts of these methods extend to higher dimensions. Algebraic models of homotopy type in higher dimensions do allow some explicit computations, involving so called cat$^n$-groups, and crossed $n$-cubes of groups, but do not easily give a handle on the general computability of homotopy groups.

-
Ronnie - could you explain what you mean by 'this result gives "in principle" a determination of $\pi_1(K)$'? What sort of determination? –  HJRW Jan 7 '13 at 12:49
Of course that should be $\pi_2$. –  HJRW Jan 7 '13 at 15:35

I'm confident that hypotheses on the decision-theoretic properties of $\pi_1$ won't allow you to compute $\pi_2$. Below, I'll outline a construction that goes in this direction. Unfortunately, it doesn't quite answer the question as stated, though it might be possible to make it do so with some more work. Perhaps there's another construction that does the job.

(The details of the following---specifically, how to make sure that $H_3(H_n)$ is infinite dimensional---were explained to me by Martin Bridson.)

Theorem: There exists a recursive sequence of finite presentations for groups $G_n$ and a recursive sequence of finite subsets $S_n\subseteq G_n$ such that:

1. the word problem is uniformly solvable in the $G_n$;
2. the subgroup $H_n=\langle S_n\rangle$ is finitely presentable;
3. the set of indices $n$ such that $\pi_2$ of a presentation complex for $H_n$ is finitely generated as an $H_n$-module is recursively enumerable but not recursive.

In particular, although the word problem is uniformly solvable in the $H_n$, there is no algorithm to compute $\pi_2$ of a presentation complex for $H_n$.

Remarks:

1. This doesn't quite answer the question, because the algorithm does not compute presentation complexes for $H_n$. Indeed, Bridson and I showed that this can't be done in general. More on this below.
2. The groups $G_n$ can be made very nice indeed, using work of Haglund and Wise: they can be made $\mathbb{Z}$-linear, for instance.

Sketch proof: Take a sequence of groups $Q_n$ such that:

1. the set of $n$ such that $Q_n\cong 1$ is recursively enumerable but not recursive;
2. each $Q_n$ is of type $F_3$ (ie there exist Eilenberg--Mac Lane spaces with finite 3-skeleta); and
3. $H_4(Q_n;\mathbb{Q})$ is infinite-dimensional whenever $Q_n\ncong 1$.

Apply the Rips Construction to get a short exact sequence

$1\to K_n\to\Gamma_n\stackrel{q_n}{\to} Q_n\to 1$

with $\Gamma_n$ satisfying the C'(1/6) small cancellation condition (in particular, $\Gamma_n$ is 2-dimensional) and $K_n$ finitely generated. Let $G_n=\Gamma_n\times\Gamma_n$ and let $H_n$ be the fibre product

$H_n=\lbrace (\gamma_1,\gamma_2)\mid q_n(\gamma_1)=q_n(\gamma_2)\rbrace$ .

All this can be done algorithmically. The $H_n$ are finitely presentable by the 1-2-3 Theorem of Baumslag, Bridson, Miller and Short. It remains to prove that $\pi_2$ of a presentation complex for $H_n$ is infinitely generated if and only if $Q_n\ncong 1$.

If $Q_n$ is trivial then $H_n= G_n$, which has a finite, four-dimensional Eilenberg--Mac Lane space. In particular, the boundary maps of the 3-cells generate $\pi_2$ of the 2-skeleton.

If $Q_n$ is non-trivial then $H_4(Q_n)$ is infinite-dimensional and, by a spectral sequence argument along the lines of Proposition 6.2 of this paper of Bridson--Reid, it follows that $H_3(H_n)$ is also infinite dimensional. It follows that $\pi_2$ of any presentation complex for $H_n$ is infinitely generated as an $H_n$-module. QED

Final remarks:

To answer the question in the title, you need to be able to compute a presentation complex for $H_n$. This, in turn, requires the input presentations' for the groups $Q_n$ to come equipped $\pi_2$-generators. This is a rather delicate issue, perilously close to hard open problems like the triviality problem for aspherical presentations.

-

@HW: I actually wrote $\pi_2(K)$! The explicit determination of this kernel was long a problem for me, and a start on a solution (for finite $\pi_1 K$) is given in the paper with Razak Salleh Free crossed crossed resolutions of groups and presentations of modules of identities among relations', LMS J. Comp. and Math. 2 (1999) 28-61. These methods are developed by Graham Ellis to give a GAP package HAP.

The idea is to construct inductively with a contracting homotopy a universal cover of a prospective $K(G,1)$. One starts with a tree in a Cayley graph, which gives a retraction of the 1-skeleton of a prospective cover. A detailed explanation is in the big book already cited, p. 341ff. See also Graham's paper in J. Symbolic Comp. 38 (2004) 1077--1118.

Also p. 139 of the same book gives some calculations of some finite $\pi_2$ of mapping cones which are obtained by first calculating the $2$-type as a (finite) crossed module and then determining the kernel, all using GAP.

-
Sorry, I meant $\pi_2$, of course. So you actually have an algorithm you can run on a computer? That's very nice! For what classes of groups does it work? –  HJRW Jan 7 '13 at 15:23
Chris Wensley and I looked at the problem of determinihng/computing induced crossed modules, and published 3 papers on this, 2 in TAC and also Computation and homotopical applications of induced crossed modules', J. Symbolic Computation 35 (2003) 59--72, reproduced in the book. I am hoping that you guys in geometric group theory can apply some of the crossed module ideas to some of your problems! Contact Chris for info on the GAP program XMOD. –  Ronnie Brown Jan 7 '13 at 15:54
I'll add that the proof of the 2-d Seifert-van Kampen theorem is not so hard but does use some not so well known ideas, quite new in 1978. In the 1980s I heard Stefan Holz, a research student at Biulefeld, give a 1 hour exposition. However you won't find the theorem mentioned in any text on topology (or group theory) except mine! –  Ronnie Brown Jan 7 '13 at 18:33
Ronnie, I still don't understand what the theorem actually is, in an algorithmic sense. Does your process always terminate? (Surely not!) If so, when does it work? –  HJRW Jan 8 '13 at 11:21
Henry: I don't understand the last question! The theorem as stated determines the 2-type of a union! One can ask: how does one compute a pushout of crossed modules? This is described in detail in Proc. London Math. Soc. (3) 36 (1978) 193-212. Some explicit examples are described in Brown and Wensley `On finite induced crossed modules and the homotopy 2-type of mapping cones'', Theory and Applications of Categories 1(3) (1995) 54-71. which includes a finiteness theorem for induced crossed modules. –  Ronnie Brown Jan 8 '13 at 22:30

I'll make this another answer as it tries to be explicit in answer to Henry Wilton's comments and questions.

Certainly the pushout statement given shows how $\Pi_2 K$ is determined by the $\Pi_2$ of $L,M,N$ when $K=L \cup M$, $N= L \cap M$. This is clearly directly analogous to the usual Seifert-van Kampen Theorem, and like that, has some connectivity conditions, as stated.

A useful case is when $L^1 = M^1$ and so $=K^1$ (not necessarily the $1$-skeleta). Then the theorem implies that $$\Pi_2 K\cong \Pi_2 L \circ \Pi_2 M$$ the coproduct in the category of crossed $\pi_1 K^1$-modules. This has a rather explicit description given in the paper Topology 23 (1984) 337-345., where the top group is a factor group of a semidirect product of the top groups of the parts. Some cases of explicit descriptions of $\pi_2 K$ are given there.

Another useful case is when $N=N^1, M=M^1$. Then the pushout, $\Pi_2K$ is called the crossed module induced from the crossed module $\Pi_2 L$ by the morphism of fundamental groups $\pi_1 N^1 \to \pi_1 M^1$. My papers with Chris Wensley are about explicit calculations of this, including that of $\pi_2 K$. One result is that if all else is finite, then the induced crossed module is finite. One example given in the paper in J. Symbolic Comp is to take the crossed module induced from the normal inclusion $C_3 \to S_3$ by the inclusion $S_3 \to S_4$. The answer is a crossed module $SL(2,3) \to S_4$ with kernel $C_2$. Using classifying spaces one gets a result on a mapping cone.

That is, we compute this $\pi_2 K \cong C_2$ by computing the $2$-type as a crossed module of finite nonabelian groups.

Hope that helps.

-
Ronnie - thanks for this. I feel like we're talking at cross purposes here. You keep talking about computations and determinations (which are very nice!), but I want to know about algorithms (which is what the original question asked about). But this is getting out of hand - let's leave it for now. –  HJRW Jan 10 '13 at 10:48
Agreed to leave it. Of course computations, especially computer computations, require algorithms, in this case group theory methods in GAP adapted by Chris Wennsley for crossed modules. –  Ronnie Brown Jan 11 '13 at 11:37