An approximation of the Collatz map and a lower bound for the average total stopping time

Abstract

Define the map $\mathsf{T}$ on the positive integers by $\mathsf{T}(m)=\frac{m}{2}$ if $m$ is even and by $\mathsf{T}(m)=\frac{3m+1}{2}$ if $m$ is odd. Results of Terras and Everett imply that, given any $\epsilon >0$, almost all $m\in {\mathbb{Z}}^{+}$ (in the sense of natural density) fulfill $(\frac{\sqrt{3}}{2}{)}^k{m}^{1-\epsilon }\le {\mathsf{T}}^k(m)\le (\frac{\sqrt{3}}{2}{)}^k{m}^{1+\epsilon }$ simultaneously for all $0\le k\le \alpha \log m$ with $\alpha =(\log 2{)}^{-1}\approx 1.443$. We extend this result to $\alpha =2(\log \frac{4}{3}{)}^{-1}\approx 6.952$, which is the maximally possible value. Set ${\mathsf{T}}_{\min }(m):={\min }_{n\in \mathbb{N}}{\mathsf{T}}^n(m)$. As an immediate consequence, one has ${\mathsf{T}}_{\min }(m)\le {\mathsf{T}}^{\lfloor 2(\log \frac{4}{3}{)}^{-1}\log m\rfloor }(m)\le m^{\epsilon }$ for almost all $m\in {\mathbb{Z}}^{+}$ for any given $\epsilon >0$. Previously, Korec has shown that ${\mathsf{T}}_{\min }(m)\le m^{\epsilon }$ for almost all $m\in {\mathbb{Z}}^{+}$ if $\epsilon >\frac{\log 3}{\log 4}$, and recently Tao proved that ${\mathsf{T}}_{\min }(m)\le f(m)$ for almost all $m\in {\mathbb{Z}}^{+}$ (in the sense of logarithmic density) for all functions $f$ diverging to $\infty$. Denote by $\tau (m)$ the minimal $n\in \mathbb{N}$ for which ${\mathsf{T}}^n(m)=1$ if there exists such an $n$ and set $\tau (m)=\infty$ otherwise. As another application, we show that ${\mathrm{liminf}}_{x\to \infty }\frac{1}{x\log x}{\sum }_{m=1}^{\lfloor x\rfloor }\tau (m)\ge 2(\log \frac{4}{3}{)}^{-1}$, partially answering a question of Crandall and Shanks. Under the assumption that the Collatz Conjecture is true in the strong sense that $\tau (m)$ is in $O(\log m)$, we show that ${\lim }_{x\to \infty }\frac{1}{x\log x}{\sum }_{m=1}^{\lfloor x\rfloor }\tau (m)=2(\log \frac{4}{3}{)}^{-1}$.

New version with changes of exposition of results. An outline of proof of main result added. Approximation result for Syracuse map added. Further references added