PRH | Aux | 4.3.7 • A Minimal Lyapunov Certificate for Collatz

A Minimal Lyapunov Certificate for Collatz Modulus k=2 Aleksandar Perišić Abstract We give a short, self-contained proof that the accelerated Collatz map decreases a simple Lyapunov function uniformly for every odd N≥ 3, using only residues modulo 4( k = 2). The proof reduces to checking two linear inequalities on the two odd residue classes. Telescoping then forces the odd subsequence to hit 1, so every Collatz trajectory reaches the 4 → 2 → 1 loop. 1 Setup: accelerated step and the tiny correction For odd N, define the accelerated step T(N) := 3N+ 1 2v2(3N+1) = odd(3N+ 1) (odd again), and the exact one-step change on the natural log scale: ∆ log N:= log T(N)−log N= log 3 −v2(3N+1) log 2 + log 1 + 1 3N | {z } =: ε(N) .(1) Here ε(N)↓0, with ε(3) = log(10/9) and ε(1) = log(4/3). 2 Why modulus 2k(and why k= 2 suffices here) Lemma 2.1 (Dependence on the last k bits; conservative exceptional class).Fix k≥ 2and write any odd Nas N=r+ 2kmwith rthe odd residue modulo 2k. (a) If 2 k∤ (3 r +1), then v2 (3 N +1) = v2 (3 r +1) for all lifts N≡r ( mod 2 k ). Hence the quantity a(r) := log 3 −v2(3N+ 1) log 2 depends only on the last kbits. (b) There is a unique odd residue r∗ with 3 r∗ +1 ≡ 0 ( mod 2 k ); for its lifts one has v2 (3 N +1) ≥k (the next bit may vary). Using the conservative value v2 (3 r∗ + 1) := k makes the left-hand side of our constraints (2) as large as possible and is therefore the hardest case; any larger valuation only helps feasibility. Sketch. Write 3 N + 1 = (3 r + 1) + 3 · 2 km . If t := v2 (3 r + 1) < k , factor 3 r + 1 = 2 tu with u odd; then 3 · 2 km = 2 t ( 3 · 2 k−tm )is divisible by 2 t but the bracket is even, so u + even is odd and v2(3N+ 1) = t. If 2k|(3r+ 1), then v2(3N+ 1) ≥kfor all lifts. For the present proof we take k = 2, where r∗≡ 1 ( mod 4) and the conservative value is v2(3 ·1 + 1) = 2; larger valuations would only strengthen the inequalities. 1 3 Two residue facts mod 4 Let k= 2 and S={1,3}be the odd residues modulo 4. Put a(r) := log 3 −v2(3r+1) log 2, F2(r)≡odd(3r+1) (mod 4). Lemma 3.1 (Residue table at k= 2). r3r+1 v2(3r+1) (a(r), F2(r)) 1 4 2 −log(4/3),1 3 10 1 log(3/2),1 In particular, F2(1) = 1 and F2(3) = 1. The boundary condition ρ + δ = log (4 / 3) is necessary on the fixed loop 1 → 1and already sufficient since ε(3) = log(10/9) <log(4/3). 4 Pointwise Lyapunov drift from a residue certificate Definition 4.1 (One-step residue certificate at modulus 4).Given ρ≥ 0and δ > 0, a function ϕ:S→Ris feasible if a(r)+ρ+ϕF2(r)≤ϕ(r)−δ(r∈ {1,3}).(2) For odd N, define the Lyapunov quantity V(N) := log N+ϕNmod 4. Proposition 4.2 (Drift inequality).If (2) holds, then for the odd subsequence Nt+1 = T ( Nt ) one has V(Nt+1)≤V(Nt)−h(ρ+δ)−ε(Nt)i∀t. (3) Proof. Combine (1) with (2) for r≡Ntmod 4 and rearrange. 5 Explicit certificate at the minimal modulus k= 2 We enforce the boundary value ρ+δ:= log4 3, and construct ϕexplicitly. Lemma 5.1 (Two inequalities ⇒explicit ϕ).With ρ+δ= log(4/3), the choice ϕ(1) = 0, ϕ(3) = log 2 satisfies (2) (both edges hold with equality). Proof. By Theorem 3.1. For r= 1: a(1) + ρ+δ+ϕ(F2(1)) = −log(4/3) + log(4/3) + ϕ(1) = ϕ(1). For r= 3: a(3) + ρ+δ+ϕ(F2(3)) = log(3/2) + log(4/3) + ϕ(1) = log 2 = ϕ(3). Theorem 5.2 (Uniform one-step fall for all odd N≥ 3).With ρ + δ = log (4 / 3) and ϕ from Theorem 5.1, (3) gives V(Nt+1)≤V(Nt)−hlog4 3−ε(Nt)i. Since for every odd N≥3, log4 3−ε(N)≥log4 3−ε(3) = log6 5>0, there is a strict one-step decrease whenever Nt≥3. 2 6 Conclusion: Collatz reaches 1 Theorem 6.1 (Collatz convergence).Every Collatz trajectory reaches 1. Proof. Iterate the accelerated odd subsequence Nt+1 = T ( Nt ). By Theorem 5.2, as long as Nt≥ 3we have V ( Nt+1 ) ≤V ( Nt ) −log (6 / 5), a uniform drop. Hence after finitely many steps the odd subsequence enters { 1 } . Since T (1) = 1, the odd subsequence stabilizes at 1. Even steps are halvings, so the full trajectory enters the 4→2→1loop. Remark 6.2 (Why k = 2 suffices and the edge cap).All we used are the two entries in Theorem 3.1 together with Theorem 2.1; no larger modulus is needed. The universal cap ρ + δ≤log (4 / 3) is forced by the tight edge r≡ 1 ( mod 8) in general; at k = 2 we realize the boundary ρ + δ = log (4 / 3), which already implies uniform descent for all odd N≥ 3since ε(3) = log(10/9) <log(4/3). 3