Searching for a Decreasing Function in the Collatz Conjecture
This paper investigates whether a Lyapunov-style function can be found that decreases along Collatz trajectories, and concludes that no such function is established here: the work is a structured research programme, not a proof. Starting from the failed candidate F(n) = n, the logarithmic potential F(n) = log₂ n reveals an average downward drift once the process is compressed to odd integers; residue classes modulo powers of 2 then explain how many divisions by 2 follow each odd step, and a residue-dependent correction on classes modulo a power of 2 turns part of the problem into an optimisation problem. The aim is to show how an elementary-looking problem becomes a serious investigation spanning dynamical systems, probability, number theory, optimisation and computation.
1 · The conjecture as a dynamical system
The map T halves an even integer and sends an odd one to 3n + 1, and the conjecture asserts that some number of repeated applications of T sends it to 1, for every positive integer n. The trajectory of 13 runs 13 → 40 → 20 → 10 → 5 → 16 → 8 → 4 → 2 → 1, while 27 climbs dramatically before descending. Viewed as a dynamical system on the positive integers, each starting value generates an orbit {n, T(n), T²(n), …} and the claim is that every orbit enters the cycle 1 → 4 → 2 → 1 — so the conjecture can fail in exactly two ways: another cycle that does not contain 1, or an orbit that never enters a cycle and grows without bound.
2 · Two naive potentials, and why each fails
The standard strategy is to find a quantity that decreases: if F(T(n)) < F(n) for every n > 1 and F is bounded below in a suitable sense, infinite descent becomes impossible. The obvious candidate F(n) = n fails immediately, since 3 → 10 makes F(10) > F(3), so any successful potential must tolerate temporary increases. The logarithmic candidate F(n) = log₂ n is better, because multiplication becomes addition: an even step costs exactly −1 while an odd step gains about log₂ 3 ≈ 1.585. Neither decreases at every step, but the imbalance is now small enough that grouping steps can change the verdict.
3 · The accelerated map and the role of v₂
If n is odd then 3n + 1 is even, so we may divide by 2 repeatedly until the next odd integer appears. Writing v₂(m) for the exponent of 2 in the factorisation of m — for 40 = 2³·5, v₂(40) = 3 — the accelerated map U compresses a whole run into a single step, turning 13 → 40 → 20 → 10 → 5 into 13 → 5 → 1. With k = v₂(3n + 1) the ratio U(n)/n is approximately 3 divided by 2 to the power k, so logarithmic size changes by roughly log₂ 3 − k: only k = 1 produces growth, and every k ≥ 2 shrinks. Modular arithmetic predicts k in advance — n ≡ 1 (mod 4) forces k ≥ 2, while n ≡ 3 (mod 4) gives k = 1.
4 · A residue-dependent potential
Rather than treat every integer identically, assign a correction according to its residue class modulo a power of 2. With r = 4 there are only sixteen residue classes, so instead of searching over an arbitrary function on infinitely many integers we search for sixteen parameters g(0), g(1), …, g(15) — turning part of the problem into an optimisation problem. Every Collatz transition then contributes a single linear inequality in the g-values: an even transition n → n/2 gives g((n/2) mod 16) − g(n mod 16) < 1, an odd transition gives another. Thousands or millions of such inequalities can be generated and tested for joint feasibility by linear programming. If the system is infeasible we learn a concrete limitation of the model; if feasible over a large range we have an interesting candidate, though still not a proof.
5 · Why an average drift is not a proof
Heuristically the average value of k = v₂(3n + 1) is about 2, so the expected change per compressed step is log₂ 3 − 2 ≈ −0.415: a downward drift. But average behaviour is not the behaviour of every trajectory — an average can be negative while an exceptional orbit behaves completely differently, and the conjecture is precisely the claim that no such exceptional trajectory exists. Checking n = 1, 2, …, 10⁸ (and the verification has been pushed far beyond this range) establishes only the tested range, and Tao's theorem that almost all orbits attain almost bounded values is a partial result, not a proof. Computation is therefore used here differently: to discover structure that might eventually support one.
6 · The research programme
Three experiments structure the investigation: A tests the ordinary logarithmic potential and records the first and most extreme increases; B asks, for odd n, how often R(n) = U(n)/n falls below 1 rather than above it; C searches for g such that F(n) = log₂ n + g(n mod 16) satisfies F(U(n)) < F(n) for as many n as possible. Richer potentials could combine several pieces of arithmetic information so that temporary increases are compensated by decreases in the correction terms. A proof would still have to show that F falls along every relevant orbit and rule out nontrivial cycles, escaping trajectories, and exceptional residue patterns — the obstacle is not finding a candidate, but making it global.