Iteration of functions and contractibility of acyclic 2-complexes

DOI10.5565/PUBLMAT6512110MaRDI QIDQ2232007zbMATH OpenFDO

Authors Ian J. Leary

Publication date 1 October 2021

Published in Publicacions Matemàtiques (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1910.00931

zbMATH Keywords

2-complexes\(3x+1\) problemCollatz functioncontractibilityiteration

Mathematics Subject Classification ID

Undecidability and degrees of sets of sentences (03D35) Special sequences and polynomials (11B83) Word problems, other decision problems, connections with logic and automata (group-theoretic aspects) (20F10) Topological methods in group theory (57M07)

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.

Review text

In this article, the author obtains an interesting connection between the theory of 2-dimensional complexes and the famous \(3x+1\) problem. Let \( \mathbb{N}\) be the set of positive natural numbers and \(f:\mathbb{N} \rightarrow \mathbb{N}\) be a function defined by \(f(x)=3x+1\) when \(x\) is odd, and \(f(x)=x/2\) when \(x\) is even. The Collatz conjecture states that every orbit of \(f\) contains \(1.\) A result of \textit{S. A. Kurtz} and \textit{J. Simon} [Lect. Notes Comput. Sci. 4484, 542--553 (2007; Zbl 1198.03043)] implies that there can be no algorithm to decide whether the Collatz conjecture is true or not. Let \(\mathcal{P}(f)=\langle a_{i},i\in \mathbb{N} :a_{f(i)}^{-1}a_{i}a_{f(i)}=a_{i}^{2}\rangle \) and \(P(f)\) be the presentation 2-complex. The author proves that \(P(f)\) is contractible if and only if the Collatz conjecture holds. Since \(P(f)\) is aspherical and acyclic, there can be no algorithm to decide whether an infinite, recursively described, aspherical, acyclic presentation 2-complex is contractible.

Recommendations

• Two undecidable variants of Collatz's problems
• The Undecidability of the Generalized Collatz Problem
• scientific article; zbMATH DE number 5885061
• scientific article; zbMATH DE number 569741
• Deciding contractibility of a non-simple curve on the boundary of a 3-manifold

Cites work

• A Finitely Generated Infinite Simple Group
• Combinatorial group theory.
• scientific article; zbMATH DE number 1819874 (Why is no real title available?)
• scientific article; zbMATH DE number 3526785 (Why is no real title available?)
• scientific article; zbMATH DE number 2103273 (Why is no real title available?)
• The ultimate challenge. The \(3x+1\) problem
• The Undecidability of the Generalized Collatz Problem

Cited in

(3)

• Examples of \(\mathbb{Z}\)-acyclic and contractible vertex-homogeneous simplicial complexes
• Paths in primal spaces and the Collatz conjecture
• The Undecidability of the Generalized Collatz Problem

This page was built for publication: Iteration of functions and contractibility of acyclic 2-complexes

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2232007)