Almost all orbits of the Collatz map attain almost bounded value

You need to know: Set {\mathbb N} of positive integers, logarithm, limits.

Background: The Collatz map \text{Col}: {\mathbb N}\to {\mathbb N} is defined by (i) \text{Col}(n)=3n+1 when n is odd and (ii) \text{Col}(n) = n/2 when n is even. For any n\in{\mathbb N}, let \text{Col}^k(n) denote the k-th iterate of \text{Col}, let \text{Col}^{\mathbb N}(n)=\{n, \text{Col}(n), \text{Col}^2(n), \dots\} be the Collatz orbit, and let \text{Col}_{\text{min}}(n) = \inf\limits_{k \in {\mathbb N}} \text{Col}^k(n)  denote the minimal element of the Collatz orbit \text{Col}^{\mathbb N}(n).

We say that subset A\subseteq {\mathbb N} has logarithmic density 1, if \lim\limits_{x\to \infty}\left(\frac{1}{\log x}\sum\limits_{k\in A, k\leq x}\frac{1}{k}\right)=1. We say that a property P holds for almost all n \in {\mathbb N} (in the sense of logarithmic density) if the subset of {\mathbb N} for which P holds has logarithmic density 1.

The Theorem: On 8th September 2019, Terence Tao submitted to arxiv a paper in which he proved that for any function f: {\mathbb N} \to {\mathbb N} such that \lim\limits_{n\to \infty} f(n)=+\infty, one has \text{Col}_{\text{min}}(n) < f(n) for almost all n \in {\mathbb N} (in the sense of logarithmic density).

Short context: The famous Collatz conjecture predicts that \text{Col}_{\text{min}}(n)=1 for all n\in{\mathbb N}, but it remains well beyond reach of the current methods. As a partial progress, Terras proved in 1976 that \text{Col}_{\text{min}}(n)<n for almost all n. In 1979, Allouche improved this to \text{Col}_{\text{min}}(n)<n^\theta for almost all n, for any fixed constant \theta>0.869. In 1994, Korec proved the same result for any \theta>\frac{\log 3}{\log 4}=0.792.... The Theorem implies that one can take any \theta>0, and, more generally, \text{Col}_{\text{min}}(n)<f(n) for almost all n and any function f going to infinity with n. For example, one can take f(n)=\log\log\log\log n.

Links: Free arxiv version of the original paper is here.

Go to the list of all theorems

One thought on “Almost all orbits of the Collatz map attain almost bounded value

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s