The \(3x+1\) problem: New lower bounds on nontrivial cycle lengths
type: Item
instance of: scholarly article
title: The \(3x+1\) problem: New lower bounds on nontrivial cycle lengths
zbMATH Open document ID: 0786.11012
DOI: 10.1016/0012-365X(93)90052-U
author: Shalom Eliahou
published in: Discrete Mathematics
publication date: 1993-11-02T00:00:00Z
review text: The ``Collatz''-problem (or ``\(3x+1\)''- or ``Hasse''- or ``Syracuse''- or ``Kakutani''-problem) is to prove that for every \(n\in\mathbb{N}\) there exists a \(k\) with \(T^{(k)}(n)=1\) where the function \(T(n)\) takes odd numbers \(n\) to \((3n+1)/2\) and even numbers \(n\) to \(n/2\). This conjecture has been verified with a computer at least up to \(n=2^{40}\). Given \(n\in\mathbb{N}\), a trajectory of \(n\) is defined as the set of iterates \(\Omega(n):= \{n,T(n), T^{(2)}(n),\dots\}\). A trajectory \(\Omega\) will be called a cycle (of length \(k\)) if \(T^{(k)}(x)=x\) for all \(x\in \Omega\), where \(k= \text{Card }\Omega\). For example, \(\Omega(1)= \{1,2\}\) is a cycle of length 2, called the trivial cycle. Now the ``\(3x+1\)''-conjecture reads as \(1\in\Omega(n)\) for all \(n\in\mathbb{N}\) and implies that \(\Omega(1)\) should be the only cycle of \(T\). Various authors have observed that nontrivial cycles of \(T\) (if any) must be very big. In this paper the author proves that for any nontrivial cycle of \(T\) with \(\text{Min} \Omega>2^{40}\) holds the equation \[ \text{Card }\Omega= 301 994a+ 17 087 915b+ 85 137 581c, \] where \(a\), \(b\), \(c\) are nonnegative numbers, \(b>0\), and \(ac=0\). In particular, the smallest admissible values for \(\text{Card }\Omega\) are 17 087 915, 17 389 909, 17 691 903, and so on. In his proof the author uses classical facts about continued fractions to obtain a sufficient sharp one-sided diophantine approximation of \(\log_ 2(3)\).
Mathematics Subject Classification ID: 11B83
zbMATH DE Number: 417460
zbMATH Keywords: Collatz function
zbMATH Keywords: \(3x+1\)-conjecture
zbMATH Keywords: cycles
zbMATH Keywords: one-sided diophantine approximation of \(\log_ 2(3)\)
zbMATH Keywords: trajectory
Wikidata QID: Q63353519
reviewed by: Helmut Müller
MaRDI profile type: Publication
cites work: On the "3x + 1" Problem
cites work: The 3x + 1 Problem and Its Generalizations
cites work: Continued Fractions without Tears
cites work: The Collatz problem
DBLP publication ID: journals/dm/Eliahou93
Recommended article: Theoretical and computational bounds for m-cycles of the 3n+1-problem
Recommended article: On the nonexistence of $2$-cycles for the $3x+1$ problem
Recommended article: On Schelp's problem for three odd long cycles
Recommended article: The \(3x+1\) problem: a lower bound hypothesis
Recommended article: Cycle Lengths Modulo k in Large 3-connected Cubic Graphs, Advances in Combinatorics
Recommended article: A lower bound in the problem of realization of cycles
Recommended article: Cycles and new bounds for the chromatic number
Recommended article: New length bounds for cycle bases
Recommended article: The set of rational cycles for the 3x+1 problem
description: scientific article; zbMATH DE number 417460