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}$:

(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

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.