Almost all orbits of the Collatz map attain almost bounded values

Abstract

Define the \emph{Collatz map} $\mathrm{Col}:\mathbb{N}+1\to \mathbb{N}+1$ on the positive integers $\mathbb{N}+1=\{1,2,3,\dots \}$ by setting $\mathrm{Col}(N)$ equal to $3N+1$ when $N$ is odd and $N/2$ when $N$ is even, and let ${\mathrm{Col}}_{\min }(N):={\inf }_{n\in \mathbb{N}}{\mathrm{Col}}^n(N)$ denote the minimal element of the Collatz orbit $N,\mathrm{Col}(N),{\mathrm{Col}}^2(N),\dots$. The infamous \emph{Collatz conjecture} asserts that ${\mathrm{Col}}_{\min }(N)=1$ for all $N\in \mathbb{N}+1$. Previously, it was shown by Korec that for any $\hat{I}¸>\frac{\log 3}{\log 4}\approx 0.7924$, one has ${\mathrm{Col}}_{\min }(N)\le N^{\hat{I}}¸$ for almost all $N\in \mathbb{N}+1$ (in the sense of natural density). In this paper we show that for \emph{any} function $f:\mathbb{N}+1\to \mathbb{R}$ with ${\lim }_{N\to \infty }f(N)=+\infty$, one has ${\mathrm{Col}}_{\min }(N)\le f(N)$ for almost all $N\in \mathbb{N}+1$ (in the sense of logarithmic density). Our proof proceeds by establishing an approximate transport property for a certain first passage random variable associated with the Collatz iteration (or more precisely, the closely related Syracuse iteration), which in turn follows from estimation of the characteristic function of a certain skew random walk on a $3$-adic cyclic group at high frequencies. This estimation is achieved by studying how a certain two-dimensional renewal process interacts with a union of triangles associated to a given frequency.

58 pages, 4 figures. Two more minor typos corrected, and one medium typo (affecting the statement of Lemma 7.9) corrected

Topics & keywords