Collatz orbits, statistically — parity vectors, drift, Tao

Parent: orbit · Prereq: ergodic-theory-of-orbits, symbolic-dynamics

The dynamics-side view of collatz. Everything provable about $3n+1$ to date is statistical — and the obstruction is precisely the "almost every vs. every" wall of ergodic-theory-of-orbits.

Throughout, use the shortcut map on $\mathbb{Z}$:

$$T(n) = \begin{cases} n/2 & n \text{ even} \\ (3n+1)/2 & n \text{ odd} \end{cases}$$

(each odd step is followed by at least one halving, so folding one in loses nothing).

Parity vectors: the symbolic coding

The parity vector of $n$ is $v_k(n) = \big(n \bmod 2,\ T(n) \bmod 2,\ \dots,\ T^{k-1}(n) \bmod 2\big) \in \{0,1\}^k$ — the itinerary of the orbit through even/odd, i.e. a symbolic coding (symbolic-dynamics).

Terras (1976)

$v_k(n)$ depends only on $n \bmod 2^k$, and the map $n \bmod 2^k \mapsto v_k(n)$ is a bijection $\mathbb{Z}/2^k \to \{0,1\}^k$. First $k$ parities ↔ residue mod $2^k$, exactly.

So over a full residue class the first $k$ parity bits behave like $k$ fair coin flips — the randomness heuristic below is a theorem about finite prefixes. Terras' consequence: the set of $n$ whose orbit drops below $n$ has natural density 1.

The drift computation (why everyone believes the conjecture)

Along an orbit, $\log T(n) - \log n \approx \log\tfrac{3}{2}$ on odd steps, $\log\tfrac{1}{2}$ on even steps. If parities are fair coins (Terras licenses this for typical prefixes), the expected change per step is

$$\mathbb{E}[\Delta \log n] = \tfrac{1}{2}\log\tfrac{3}{2} + \tfrac{1}{2}\log\tfrac{1}{2} = \tfrac{1}{2}\log\tfrac{3}{4} \approx -0.1438 < 0.$$

Typical orbits are random walks on the log scale with downward drift — geometric decay at rate $\left(\tfrac{3}{4}\right)^{1/2}$ per step, hence typical total stopping time $\approx \tfrac{2}{\log(4/3)} \ln n \approx 6.95 \ln n$, matching computation. The same arithmetic convicts the cousins: for $5n+1$ the drift is $\tfrac{1}{2}\log\tfrac{5}{4} > 0$ (conjectured divergent almost everywhere), and $3n-1$ has genuine nontrivial cycles, e.g. $5 \to 7 \to 10 \to 5$ under its shortcut map. The believed picture is fragile in the coefficients — nothing about "$3n+1$ reaches 1" is generic in the family.

Why drift is not a proof: negative expected drift bounds typical behavior; the conjecture is universally quantified. A measure-zero set of adversarial parity sequences is fully compatible with everything above — and by Conway, in the wider family such adversarial behavior is not just possible but undecidable to rule out.

The 2-adic completion: where the dynamics is trivial

Extend $T$ to the 2-adic integers $\mathbb{Z}_2$ (where "mod $2^k$ for all $k$" is the whole topology). Taking parity vectors to infinity, Terras' bijections assemble into a map $\Phi: \mathbb{Z}_2 \to \{0,1\}^{\mathbb{N}}$ which is a measure-preserving homeomorphism conjugating $T$ to the full 2-shift (Lagarias 1985). On $\mathbb{Z}_2$, Collatz is the coin-flip shift: ergodic, entropy $\log 2$, completely understood.

The conjecture is about $\mathbb{N} \subset \mathbb{Z}_2$ — a measure-zero subset. The ergodic machine answers every "almost every 2-adic point" question and is constitutionally silent about this particular null set. (Same fine print as the rationals under the doubling map, raised to a research problem.)

Best unconditional results

• Tao (2019): for any $f: \mathbb{N} \to \mathbb{R}$ with $f(n) \to \infty$, almost all $n$ (in logarithmic density) satisfy $\min_k T^k(n) < f(n)$. "Almost all orbits attain almost bounded values" — proved by transporting the problem to an explicit random model and running a martingale/first-moment argument; the strongest form of the drift heuristic that survives contact with proof.
• Krasikov–Lagarias (2003): at least $x^{0.84}$ of the integers below $x$ reach 1.
• Verification: all $n \le 2^{68}$ reach 1 (Barina 2020).
• Cycles: via the continued-fraction expansion of $\log_2 3$, Eliahou (1993) showed any nontrivial cycle has length at least $17{,}087{,}915$ (given the then-current verification height; the bound scales with it).

The scoreboard after ~90 years: density-1 statements, measure statements, finite verification — every success is a relaxation of the original $\forall$, and the original $\forall$ has not moved.