PRH | Aux | 4.3.6 • Introduction to Lyapunov and a Toy Collatz–Like Certificate
Abstract
This note introduces a minimal, self-contained illustration of the Lyapunov method through a discrete “toy–Collatz” system that mirrors the structure of the Collatz descent proof. We first recall the Lyapunov principle—constructing a potential function (V) that decreases along every trajectory—and show how a simple logistic recurrence admits such a function explicitly. We then build a two–residue integer map whose potential$$V(n)=\log n+\phi(n\bmod 2^k)$$and finite residue inequalities replicate the Collatz certificate’s logic: each step may raise $\log n$ but lowers (V) through a residue–dependent correction. The parameters $\rho$ and $\delta$ serve distinct roles—$\rho$ as a blur or uncertainty budget, and $\delta>0$ as a strict safety margin—together guaranteeing a per-step drop of at least $\delta+\rho-\varepsilon(n)$. This finite, periodic construction exemplifies how a bounded Lyapunov potential on residues can enforce global descent in an infinite process.
Full text
Introduction to Lyapunov and a Toy Collatz–Like Certificate Aleksandar Periˇsi´c October 2025 Introduction to Lyapunov 1. Lyapunov idea in a nutshell ALyapunov function is a scalar quantity that measures how far a system’s state is from equilibrium, and that always decreases (or stays constant) along the system’s evolution. If one can find such a function V(x) satisfying V(xt+1)−V(xt)≤0, then the trajectory can never escape to infinity or diverge—it must stay within a bounded set, often converging to equilibrium. A classical discrete example. Consider the simple difference equation xt+1 =r xt(1 −xt), the logistic map with parameter 0 < r < 2. The fixed point x∗ = 0 is globally stable when r < 1. Take V(x)=x2. Then V(xt+1)−V(xt)=(rxt(1 −xt))2−x2 t=x2 t(r(1 −xt))2−1. For 0 < r < 1 and xt∈ (0 , 1), the bracketed term is negative, hence V ( xt+1 ) < V ( xt ). This simple quadratic V acts as a Lyapunov function: it certifies contraction toward x = 0 without ever solving the recurrence explicitly. Lyapunov logic. In general, the idea is to build a “potential” V that descends along trajectories even when the raw variable (like xt or nt ) occasionally moves up. The Collatz analysis follows the same pattern—except the potential now lives on log n plus a residue correction. 1
Toy–Collatz–Like Certificate 2. A toy Lyapunov certificate (same shape as the Collatz proof) Goal. Exhibit a tiny, fully explicit system on odd integers that uses the same Lyapunov template V(n) = log n+ϕnmod 2k, and the same residue inequalities to guarantee a per–step drop of V —just like in the Collatz certificate. 1. The toy map (“half-accelerated Collatz” at modulus 4). Work only on the odd integers Nodd. Define T(n) = 3n+ 1 4, n ≡1 (mod 4) (force ν2(3n+ 1) = 2), 3n+ 1 2, n ≡3 (mod 4) (force ν2(3n+ 1) = 1). This is integer-valued and maps odd → odd. The residue set is S = { 1 , 3 } (mod 4). The induced residue successor is F2(1) = 1, F2(3) = 1, since 3 ·1 + 1 = 4 7→ 1 and 3 ·3 + 1 = 10 7→ 5≡1 (mod 4). 2. One–step log change and the classwise weight. For odd n , write the exact one–step change (natural log) ∆ log n:= log T(n)−log n= log 3 −ν2(3n+ 1) log 2 | {z } a(r(n)) + log1 + 1 3n | {z } ε(n) , with r(n):=nmod 4. Here a(1) = log3 4≈ −0.28768, a(3) = log3 2≈+0.40547, ε(n) = log1 + 1 3n. 3. Lyapunov template and residue inequalities. Define V(n) := log n+ϕr(n), r(n)∈ {1,3}. Given parameters δ > 0 (margin) and ρ≥ 0 (blur budget; here we take ρ = 0), we seek ϕ:S→Rsuch that, for each residue r∈S, a(r)+ρ+ϕ F2(r)≤ϕ(r)−δ. (1) Feasible choice. Let δ=1 4and pick ϕ(1) = 0, ϕ(3) = a(3) + δ≈0.40547 + 0.25 = 0.65547. Check (1): r=1: a(1) + ϕ(1) ≤ϕ(1) −δ⇐⇒ a(1) ≤ −δ, true since −0.28768 ≤ −0.25; r=3: a(3) + ϕ(1) ≤ϕ(3) −δ⇐⇒ a(3) ≤(a(3) + δ)−δ, holds at equality. 4. Pointwise drift (identical shape to the Collatz certificate). 2
Lemma 1 (Per–step drop for V).For all odd n, VT(n)−V(n)≤ −δ+ε(n). In particular, if n≥3, then ε(n)≤log(10/9) ≈0.10536 and VT(n)−V(n)≤ −0.25 + 0.10536 = −0.14464 <0. Proof. Compute V(T(n)) −V(n) = a(r(n))+ε(n)+ϕF2(r(n))−ϕr(n). By (1) with ρ = 0, ϕ ( F2 ( r )) −ϕ ( r ) ≤ −a ( r ) −δ . Substituting the residue inequality gives V(T(n)) −V(n)≤ −δ+ε(n),where 0 < ε(n) = log 1 + 1 3n<log4 3. Hence Vstrictly decreases whenever ε(n)< δ. Because ϕ lives on a finite set S , it is bounded. Hence V ( n ) = log n + (bounded) , so a persistent per–step decrease of V forces the values of n to drop below any fixed threshold after finitely many steps (the standard Lyapunov conclusion). 5. Tiny numeric check. Take n = 11 ≡ 3 ( mod 4). Then T (11) = (33 + 1) / 2 = 17 and ∆ log n=a(3) + ε(11) ≈0.40547 + log(1 + 1/33) ≈0.43599 (>0). But the ϕ-jump is ϕ(1) −ϕ(3) = 0 −0.65547 = −0.65547, so V(T(11)) −V(11) ≈0.43599 −0.65547 = −0.21948 <0, exactly as guaranteed by the lemma. 6. Why this mirrors the Collatz certificate. •Same template V= log n+ϕ(residue mod 2k) with finite ϕ. •Same residue inequalities that make each reweighted edge strictly negative. • Same phenomenon: log n may go up on a step, but ϕ drops enough so V still goes down. •No averaging is used in the proof; everything is pointwise and finite. Remark 1 (Richer toy at modulus 8).One can similarly set k = 3 and define a fixed valuation t(r)by t(r) = 2, r ≡1 (mod 8), 1, r ≡3,7 (mod 8), 3, r ≡5 (mod 8), T(n) := 3n+ 1 2t(nmod 8) . Solving the four residue inequalities for ϕ and a margin δ > 0proceeds verbatim, giving the same Lyapunov drop. 3
References [1] A. M. Lyapunov, The General Problem of the Stability of Motion, Kharkov Mathematical Society, 1892. (English translation in Int. J. Control, 55(3):531–534, 1992.) [2] H. K. Khalil, Nonlinear Systems, 3rd ed., Prentice Hall, 2002. [3] J. P. LaSalle, “Stability theory for ordinary differential equations,” J. Diff. Eq. 4 (1961), 57–65. [4] S. Elaydi, An Introduction to Difference Equations, 3rd ed., Springer, 2005. [5] J. C. Lagarias, “The 3 x + 1 problem: An overview,” in The Ultimate Challenge: The 3 x + 1 Problem, A. M. Schechter, ed., AMS, Providence, 2010, pp. 3–29. [6] R. Terras, “A stopping time problem on the positive integers,” Acta Arithmetica 30 (1976), 241–252. [7] J. Cohen, “On the 3x+ 1 problem,” Coll. Math. Soc. J´anos Bolyai, 2 (1971), 33–55. 4