What did Tao prove in the paper "Almost All Orbits of the Collatz Map Attain Almost Bounded Values''?

Question

Last year, Terence Tao published a paper entitled "Almost All Orbits of the Collatz Map Attain Almost Bounded Values" (via arXiv).

In layperson's terms, could somebody please explain what this means?

In particular,

1. "Almost All" — Does that mean with the possible exception of finitely many?

2. "Orbit" — Does that include or exclude cycles?

3. "Almost Bounded Values" — What is meant by the term almost bounded?

Simply stated, does this mean that the Collatz conjecture is true for "almost all" positive integers?

I am not trying to understand Tao's proof, merely what he proved.

Thank you.

Answer 1

Q1: No, it's slightly weaker than that. As described in the blog post, "almost all" means in the sense of logarithmic density, which is a somewhat technical concept that roughly means that the set of counterexamples has "probability zero." Formally it means the set of counterexamples is a set $A \subseteq \mathbb{N}$ such that

$$\lim_{n \to \infty} \frac{\sum_{a \in A, a \le n} \frac{1}{a}}{\log n} = 0.$$

Any finite set has logarithmic density $0$ but some infinite sets also do, such as the squares and the primes.

Q2: The orbit of an integer $N$ under the Collatz map $\text{Col}$ is the entire sequence $\{ N, \text{Col}(N), \text{Col}^2(N), \dots \}$, so yes, it includes cycles if $N$ ends up in a cycle.

Q3: As described in the blog post, "almost bounded" is unfortunately a somewhat technical concept again. It means that if $f : \mathbb{N} \to \mathbb{R}$ is any function such that $\lim_{n \to \infty} f(n) = \infty$ then the smallest number $\text{Col}_{\text{min}}(N)$ in the Collatz orbit of $N$ satisfies $\text{Col}_{\text{min}}(N) \le f(N)$ for "almost all" $N$ (where "almost all" means in the sense of logarithmic density). If we could take $f(n) = 1$ (or any other small constant) and this were true for all $N$ then this would be equivalent to the Collatz conjecture; what Tao shows is that we can take $f$ to grow arbitrarily slowly to infinity, so for example we can take $f(N) = \log \log \log \log N$ (for $N$ large enough that this is defined). We can even take a function growing as slowly as the inverse Ackermann function, a function that famously grows so slowly that for all practical purposes it is at most $5$.

Q4:

Simply stated, does this mean that the Collatz conjecture is true for "almost all" positive integers?

No. The second "almost" is important; Tao shows it's "almost" true for "almost all" positive integers, where both "almost"s have distinct and technical meanings.