Iteration of functions and contractibility of acyclic 2-complexes

Ian J. Leary^{∗}

October 2, 2019

Abstract

We show that there can be no algorithm to decide whether infinite recursively described acyclic aspherical 2-complexes are contractible. We construct such a complex that is contractible if and only if the Collatz conjecture holds.

1 Introduction

The existence of an algorithm to determine which finite 2-dimensional simplicial complexes are contractible is a well-known open problem. There are good algorithms to compute the homology of a finite complex, and so the problem quickly reduces to the case of acyclic complexes, i.e., those having the same homology as a point. This problem can be stated as a problem about finite presentations of groups: is there an algorithm to decide which finite balanced presentations of perfect groups are trivial? The problem is stated in this form as problem (FP1) in [1]. A presentation is balanced if it has the same numbers of generators and relators. The conditions that the group be perfect and that the presentation be balanced are equivalent to the corresponding 2-complex being acyclic.

If a finite presentation presents the trivial group, then a systematic search will eventually find a proof of this fact. Thus there is a partial algorithm that will verify that a finite simplicial complex (of any dimension) is contractible, but that will fail to halt in general.

In general there is no algorithm to decide whether a finite presentation describes the trivial group. This implies that there can be no algorithm to decide whether a finite 2-dimensional simplicial complex is simply-connected. However, this does not imply that there can be no algorithm to decide whether a finite 2-complex is contractible, because all known families of problematic group presentations have many more relators than generators. The corresponding presentation 2-complexes cannot be contractible because they have non-trivial second homology.

∗Partially supported by a Research Fellowship from the Leverhulme Trust. This work was started at MSRI, Berkeley, where research is supported by the National Science Foundation under Grant No. DMS-1440140.

We have nothing to say about this well-known problem, but instead we consider an infinite analogue. In contrast to the finite case, there is no algorithm for computing the homology of recursively described infinite complexes. For example, it has been known since the work of Collatz in the 1930’s that it is difficult to decide such questions as whether a recursively described graph is connected [5]. (We will also justify this assertion in Theorem 11 below.) For this reason we consider only acyclic complexes. Here is our main result.

Theorem 1. There is no algorithm to decide whether an infinite, recursively described, aspherical, acyclic, presentation 2-complex is contractible.

Moreover, there is no partial algorithm to find all the contractible complexes in this class, and there is no partial algorithm to find all the non-contractible complexes.

Usually decidability results in group theory rely on the existence of a non-recursive, recursively enumerable set. Instead we rely on the dynamics of functions on the set ℕ_{+} of strictly positive integers. We associate a 2-complex P (f) to each f : ℕ_{+} → ℕ_{+} whose contractibility is controlled by the orbits of f. For such a function f, define a group presentation P(f) in which both the generators and relators are indexed by ℕ_{+}:

P(f) := ⟨a_{i}, i ∈ ℕ_{+} : a_{f(i)}^{−1}a_{i}a_{f(i)} = a_{i}^{2} ⟩.

Now let P (f) be the presentation 2-complex associated to P(f).

Lemma 2. For each f, the 2-complex P (f) is both acyclic and aspherical. The following are equivalent.

• P (f) is contractible;

• P(f) presents the trivial group;

• every forward orbit of f is eventually periodic of period at most 3.

There is a striking corollary concerning the Collatz function. Recall that the Collatz or hailstone function C : ℕ_{+} → ℕ_{+} is defined by

C(n) = \begin{cases}3n + 1 & for n odd, \\ n/2 & for n even. \end{cases}

The Collatz conjecture states that every forward orbit of C contains 1.

Corollary 3. P (C) is contractible if and only if the Collatz conjecture holds.

This corollary follows easily from Lemma 2. The proof of Theorem 1 depends also on a result of Kurtz and Simon concerning the decidability of properties of functions [4].

2 Proofs

The presentation 2-complex associated to a group presentation is a CW-complex with one 0-cell, with 1-cells in bijective correspondence with the generators, and 2-cells in bijective correspondence with the relators. We shall assume that each relator is a cyclically reduced word in the generators. The 1-skeleton of the 2-complex is a rose, whose fundamental group is naturally identified with the free group on the set of generators in the given presentation. An element of this group describes a based homotopy class of maps from the circle to the 1-skeleton. The relator corresponding to a 2-cell is used in this way to describe its attaching map. For details see [3, p. 50]. A presentation 2-complex is acyclic if it has the same homology as a point, and is aspherical if its universal covering space is contractible, or equivalently if it is an Eilenberg-Mac Lane space for the group presented. Some authors use the term ‘aspherical presentation’ for a more general situtation that arises when some of the relators are proper powers [6]; this will not concern us.

There is an algorithm to pass from presentation 2-complexes as described above to homotopy equivalent simplicial complexes. Each 2-cell corresponding to a relator of length n should be viewed as an n-gon; the second barycentric subdivision of the polygonal cell complex obtained in this way is a simplicial complex. Each petal of the original 1-skeleton rose is triangulated as the boundary of a square, and the 2-cell corresponding to a relator of length n is built from 12n triangles.

Conversely, if K is a connected 2-dimensional simplicial complex and T is a maximal tree in K, the quotient space K/T is naturally a CW-complex with one 0-cell, and so it may be viewed as a presentation complex, with generators corresponding to the edges of K −T and relators corresponding to the 2-simplices of K. This process too is algorithmic, given K and T, but when K is infinite there may be no algorithm to find a maximal tree T.

The discussion in the two paragraphs above leads to the following proposition and a corollary to our main theorem.

Proposition 4. The existence of an algorithm to decide contractibility for finite presentation 2-complexes is equivalent to the existence of an algorithm to decide contractibility for finite 2-dimensional simplicial complexes.

Proof. As discussed above, there is an algorithm to pass from a finite presentation 2complex to a homotopy-equivalent finite 2-dimensional simplicial complex. Conversely, there is an algorithm to find a maximal tree T inside a finite 2-dimensional simplicial complex K, and K/T is a finite presentation 2-complex homotopy equivalent to K.

Corollary 5. For the class of recursively defined acyclic aspherical 2-dimensional simplicial complexes, there is no partial algorithm to find all contractible complexes in the class, and no partial algorithm to find all non-contractible complexes.

Proof. Since there is an algorithmic way to pass from a recursively described presentation 2-complex to a recursively defined 2-dimensional simplicial complex, a partial algorithm of the type mentioned in the statement of the corollary would contradict Theorem 1.

Two infinite families of finite group presentations will play a role in our proofs, the families B(n) and H(n) given below. As above, we use the notation B(n) and H(n) for the corresponding presentation 2-complexes.

B(n) := ⟨a_{1}, …, a_{n+1} : a_{i}^{a_{i+1}} = a_{i}^{2}⟩
H(n) := ⟨a_{i}, i ∈ ℤ/n : a_{i}^{a_{i+1}} = a_{i}^{2}⟩

To establish properties of B(n), H(n) and of the complexes P (f), we will use two well-known propositions.

Proposition 6. Let X, Y and Z be Eilenberg-Mac Lane spaces for the groups H, K and L respectively, and let i : Z → X and j : Z → Y be based maps such that the induced maps on fundamental groups are injective: i_{∗} : L → H and j_{∗} : L → K.

1. The double mapping cylinder or homotopy colimit

(X ⊔ Z × I ⊔ Y)/(z, 0) = i(z), (z, 1) = j(z)

is an Eilenberg-Mac Lane space for the free product with amalgamation H ∗_{L} K = ⟨H, K: i_{∗}(l) = j_{∗}(l)^{−1} l ∈ L⟩.

2. If moreover X = Y so that K = H, then the homotopy colimit of the smaller diagram with two arrows and just two spaces, X ⊔Z ×I)/(z, 0) = i(z), (z, 1) = j(z), is an Eilenberg-Mac Lane space for the HNN-extension H∗_{L} = ⟨H, t: ti_{∗}(l)t^{−1} = j_{∗}(l)∀l ∈ L⟩.

Proof. Both assertions are special cases of a theorem concerning arbitrary graphs of groups; see for example [3, 1.B.11] although note that the directed graph used in [3, 1.B] is the barycentric subdivision (with edges oriented from the larger edge midpoint to the vertex) of the graph usually used to index a graph of groups.

Proposition 7. With hypotheses as in part (1) of Proposition 6, if in addition the maps i : Z → X and j : Z → Y are isomorphisms from Z to subcomplexes of X and Y, then the coproduct X ⊔ Y/i(z) = j(z) is also an Eilenberg-Mac Lane space for H ∗_{L} K.

Proof. The inclusion of a subcomplex in a CW-complex is a cofibration, and hence the pair (X, i(Z)) is homotopy equivalent to the pair (M_{i}, Z), where M_{i} denotes the mapping cylinder of i : Z → X and similarly (X, j(Z)) is homotopy equivalent to the pair (M_{j}, Z). The claim follows.

Corollary 8. The presentation 2-complex B(n) for B(n) is aspherical, and each of the generators a_{i} represents an element of its fundamental group, π_{1}(B(n)) of infinite order. The presentation obtained by adding the relation a_{n+1} = 1 to B(n) presents the trivial group. The subgroup of π_{1}(B(n)) generated by a_{1} and a_{n+1} is free of rank two provided that n ≥ 2.

Proof. The group presented by B(1) is the Baumslag-Solitar group BS(1, 2), which is an HNN-extension of the infinite cyclic group ⟨a_{1}⟩ with stable letter a_{2}. The asphericity claim for n = 1 follows from part (2) of Proposition 6. Given the relation a_{2} = 1, the relator in B(1) reduces to a_{1} = a_{1}^{2}, which immediately implies a_{1} = 1. This completes the proof when n = 1.

All of the claims except that final one are proved by induction using Proposition 7, since a complex isomorphic to B(n + 1) can be obtained by identifying the circle labelled a_{n+1} in B(n) with the circle labelled a_{1} in a second copy of B(1).

The final claim follows, because the subgroup ⟨a_{1}, a_{n+2}⟩ acts freely on the Bass-Serre tree coming from the above decomposition of π_{1}(B(n + 1)).

Corollary 9. The presentation 2-complex H(n) for H(n) is aspherical for all n, and is contractible if and only if n ≤ 3. For n ≥ 4, each a_{i} generates an infinite cyclic subgroup of π_{1}(H(n)).

Proof. It is well-known (and can be checked readily with a computer algebra package) that H(n) presents the trivial group for n ≤ 3. For n ≥ 4, the complex H(n) can be obtained from a copy of B(n − 2) and a copy of B(2) by identifying the 2-petalled rose labelled by a_{1} and a_{n−1} inside B(n − 2) with the 2-petalled rose labelled by a_{3} and a_{1} respectively inside B(2). The remaining claims concerning H(n) now follow from Proposition 7 and Corollary 8.

We are now ready to start the proof of Lemma 2.

Proof. It is immediate that each P (f) is acyclic, and so we concentrate on the homotopy groups.

First, consider the case of the function f(i) := i + 1. case, the 2-cells labelled 1, …, n and the 1-cells labelled 1, …, n+1 form a subcomplex isomorphic to B(n), and the whole complex is the ascending union of these subcomplexes. It follows that in this case P (f) is aspherical as claimed. To see that P (f) is not contractible, let r : ℕ_{+} → ℤ/4 be the map defined by r(i) := [i] := i + 4ℤ. This induces a cellular map P (f) → H(4) which is surjective on fundamental groups. Since the subgroup ⟨a_{r(i)}⟩ is infinite, so is the subgroup ⟨a_{i}⟩ of the group presented by P(f).

Now we move on to the general case. We fix a function f : ℕ_{+} → ℕ_{+}, and so we write P instead of P(f) and P in place of P (f), and prove the claim by induction on certain subcomplexes of P. The boundary of the 2-cell labelled by i ∈ ℕ_{+} meets only the 1-cells a_{i}, a_{f(i)} and the 0-cell. Hence if S ⊆ ℕ_{+} is any subset such that f(S) ⊆ S, the cells indexed by S (together with the 0-cell) form a subcomplex of P. Denote this subcomplex by P (S). For each i ∈ ℕ_{+}, write F (i) for the forward orbit of i: F (i) := {f^{n}(i) : n ≥ 0}, and note that f(F (i)) ⊆ F (i).

As an inductive hypothesis, suppose that we have an f-closed subset S ⊆ ℕ_{+} so that P (S) is aspherical, P (S) is contractible if and only if every forward orbit of f|_{S} is eventually periodic of period at most 3, and that for each i ∈ S, the subgroup of π_{1}(P (S)) generated by a_{i} is either infinite or trivial, and is trivial iff the forward orbit F (i) is eventually periodic of period at most 3.

Let i be the least element of ℕ_{+} − S. There are two main cases to consider. If F (i) ∩ S = ∅, then P (F (i) ∪ S) = P (F (i)) ∨ P (S), the 1-point union of P (F (i)) and P (S), and π_{1}(P (F (i) ∪ S) is just the free product π_{1}(P (F (i))) ∗ π_{1}(P (S)). Thus our inductive hypothesis will hold for F (i) ∪ S provided that we can show that it holds for F (i). This splits into three further subcases. If F (i) is infinite, then P (F (i)) is isomorphic to the complex discussed in the first paragraph, and the claims hold. If f is periodic of period n when restricted to F (i), then P (F (i)) is isomorphic to the complex H(n), and the inductive hypotheses hold by Corollary 9. If neither of these cases holds, we take an intermediate step between S and S ∪ F (i). Pick the least n > 0 so that there exists m > n with f^{m}(i) = f^{n}(i), and let j := f^{n}(i). We have that f is periodic on F (j) and F (j) ∩ S = ∅, so by the cases already covered, we deduce that the inductive hypotheses hold for S′ := S ∪ F (j). Note also that F (i) ∩ S′ = F (j) ≠ ∅, so getting from S′ to S′ ∪ F (i) = S ∪ F (i) reduces to the other main case.

If F (i) ∩ S ≠ ∅, let n be minimal so that f^{n}(i) ∈ S. In this case, P (F (i) ∪ S) is isomorphic to the union of P (S) and the subspace X consisting of the 0-cell the 1-cells labelled by {i, f(i), …, f^{n}(i)} and the 2-cells labelled by {i, f(i), …, f^{n−1}(i)}, which is isomorphic to B(n). The intersection of these is the circle labelled by f^{n}(i). If the forward orbit of i is eventually periodic of period at most 3, then so is the forward orbit of f^{n}(i), and so the circle labelled by f^{n}(i) is contractible in P (S), and attaching a copy of B(n) to this circle does not change the homotopy type, so P (F (i) ∪ S) is homotopy equivalent to P (S). If on the other hand the forward orbit of i is infinite, or eventually periodic of period greater than 3, then the circle labelled by f^{n}(i) represents an element of infinite order in the fundamental groups of both P (S) and X ≅ B(n). The inductive hypothesis passes to P (S ∪ F (i)) = P (S) ∪_{f^{n}(i)} X.

Next we prove Corollary 3.

Proof. By Lemma 2, it suffices to show that any forward orbit of the Collatz function C that does not eventually join the periodic orbit 1, 4, 2, … is either infinite or has eventual period greater than 3. So let n_{1}, n_{2} …, n_{l}, … be a periodic orbit of period l, and choose the starting point so that n_{1} < n_{i} for 2 ≤ i ≤ l. This implies that n_{1} is odd, and that n_{2} = C(n_{1}) = 3n_{1} +1. Since 3n_{1} +1 > 2n_{1}, we see that C(n_{2}) > n_{1} and so l > 2. If l = 3, it must be that C(C(n_{2})) = n_{1}, and hence 3n_{1} + 1 = 4n_{1}, which implies that n_{1} = 1.

A generalized Collatz function is a function g : ℕ_{+} → ℕ_{+} such that there exists an integer m > 0 and rationals a_{i}, b_{i} for 0 ≤ i < m so that whenever x is congruent to i modulo m, g(x) = a_{i}x + b_{i}. In particular, the function C can be written in this way for m = 2, a_{0} = 1/2, b_{0} = 0, a_{1} = 3, b_{1} = 1. To prove Theorem 1, we quote a theorem of Kurtz and Simon [4], that strengthens a well known result due to Conway [2, 5]. They define GCP to be the problem of deciding, for each generalized Collatz function g, whether every forward orbit of g contains 1. They show [4, thrm. 3] that GCP is Π_{2}^{0}-complete; and hence in particular there can be no partial algorithm that can identify either the generalized Collatz functions that satisfy GCP or the ones that do not.

Given a function f : ℕ_{+} → ℕ_{+}, we define a new function f̂: ℕ_{+} → ℕ_{+} as follows. Firstly, let ϕ : ℕ_{+} → ℕ_{+} × ℤ/4 be the function ϕ(n) = (⌊(n + 3)/4⌋, [n]), where as before we use [n] to denote the class n + 4ℤ ∈ ℤ/4, and ⌊q⌋ is the greatest integer less than or equal to q. Note that ϕ is a bijection and that both ϕ and ϕ^{−1} are easily computable. Now define f̃: ℕ_{+} × ℤ/4 → ℕ_{+} × ℤ/4 by

f̃(m, [i]) := \begin{cases}(f(m), [i + 1]) & for m ≠ 1 \\ (1, [i]) & for m = 1 \end{cases} .

Finally, define f̂:= ϕ^{−1} ∘ f̃∘ ϕ.

Lemma 10. The following are equivalent, for any function f : ℕ_{+} → ℕ_{+}.

• Every forward orbit of f contains 1;

• Every forward orbit of f̂ is eventually periodic of period at most 3.

Proof. Since ϕ is a bijection, the dynamics of f̂ and f̃ are identical. It is clear that for any i, x, the forward orbit of (x, [i]) under f̃ will be eventually constant (i.e., eventually periodic of period 1) if the forward orbit of x under f contains 1. Similarly, if the forward orbit of x under f does not contain 1, then for each n ≥ 0 we see that f̃^{n}(x, [i]) = (f^{n}(x), [i + n]), and so the forward orbit of (x, [i]) will be either infinite or eventually periodic of period divisible by 4.

We are now ready to prove Theorem 1.

Proof. Let g be an arbitrary generalized Collatz function, and consider the question of whether P (ĝ) is contractible. By Lemma 2, this is equivalent to the question of whether every forward orbit of ĝ is eventually periodic of period at most three. By Lemma 10, this is equivalent to the question of whether every forward orbit of g contains 1. But Kurtz and Simon showed that this question is Π_{2}^{0}-complete, which implies the claim.

3 Closing remarks

Similar but simpler techniques can be used to prove undecidability results for the homology of infinite complexes, and we give two example below.

Theorem 11. There is no algorithm to decide whether a recursively described graph is connected. Moreover, there is no partial algorithm to find the connected ones, and no partial algorithm to find the disconnected ones.

Proof. For a function f : ℕ_{+} → ℕ_{+}, define a graph Γ(f) with vertex and edge set indexed by ℕ_{+}, where the vertices of the edge e_{i} are v_{i+1} and v_{f(i+1)}. This graph is connected if and only if every forward orbit of f contains 1.

By the Kurtz-Simon theorem, the question of whether the graph Γ(g) is contractible, for g any generalized Collatz function, is Π_{2}^{0}-complete, which implies the claim.

A similar argument applies to the computation of the first homology of recursively described 2-complexes, because the group with presentation Q(f) given by

Q(f) := ⟨a_{i}, i ∈ ℕ_{+} : a_{1} = 1, a_{i+1} = a_{f(i+1)}⟩

is free, and is trivial if and only if every forward orbit of f contains 1.

The top homology group (i.e., H_{1} for graphs or H_{2} for 2-complexes) is different however:

Proposition 12. For each n, there is a partial algorithm that identifies the recursively described n-dimensional complexes with non-zero nth homology group.

Proof. Fix an integer parameter m > 0. Now compute the boundaries of the first m of the n-cells, expressed as formal sums of n − 1-cells. Use standard techniques of linear algebra to decide whether these m elements are linearly dependent; if so then H_{n} ≠ 0. If not, increase m and repeat.

The functions that we have considered are ofcourse far simpler than arbitrary recursive functions. If g is either a generalized Collatz function or g = f̂ for some generalized Collatz function f, then the sets g^{−1}(i) are of bounded size and can be easily computed. From this one sees that the cellular cochain complexes for P (g), Q(g) and Γ(g) are also recursively described, where Q(g) denotes the presentation 2-complex for Q(g). The argument used in Proposition 12, when applied H^{0}(Γ(g)) for any g for which the cochain complex for Γ(g) is recursively described, gives that there is a partial algorithm that will identify when Γ(g) has a finite connected component.

References

[1] G. Baumslag, A. G. Myasnikov and V. Shpilrain, Open problems in combinatorial group theory, Second edition, Combinatorial and geometric group theory (New York 2000/Hoboken NJ, 2001) 1–38, Contemp. Math. 296, Amer. Math. Soc., Providence, RI (2002).

[2] J. H. Conway, Unpredictable iterations, Proceedings of the Number Theory Conference (Univ. Colo., 1972), 49–52., Univ. Colorado, Boulder, Colo., (1972). This item is reprinted with editorial comments as 219–221 of [5].

[3] A. Hatcher, Algebraic Topology, Cambridge University Press, Cambridge (2002).

[4] S. A. Kurtz and J. Simon, The undecidability of the generalized Collatz problem, Theory and applications of models of computation, 542–553, Lecture Notes in Comput. Sci. 4484, Springer, Berlin (2007).

[5] J. C. Lagarias (editor), The Ultimate Challenge: the 3x + 1 Problem, Amer. Math. Soc., Providence, RI, (2010).

[6] R. C. Lyndon and P. E. Schupp, Combinatorial Group Theory, Classics in Mathematics, Springer-Verlag, Berlin (2001).

Author’s address:

   i.j.leary@soton.ac.uk

School of Mathematical Sciences,

University of Southampton,

Southampton,

SO17 1BJ