Consecutive integers coalesce with density one under the Collatz map: a formally verified proof of a conjecture of Gao
- 1Independent Researcher
Abstract
Let C be the Collatz map, C(n) = n/2 for even n and C(n) = 3n+1 for odd n. Following Gao (1993), two consecutive integers n and n+1 coalesce if C^k(n) = C^k(n+1) for some k, with the same number of halvings on both trajectories and without either trajectory passing through 1. Gao computed the normalized count d̄_k of the n < 2^k − 1 for which this happens within k steps, proved that d̄_k is nondecreasing, and conjectured that d̄_k → 1. In the form recorded by Lagarias, the conjecture states that the set of n with C^k(n) = C^k(n+1) for some k ≤ log_2 n has natural density one. We prove both statements, and also that the proportion d(x) of n < x for which n and n+1 coalesce tends to 1; Gao did not know whether this limit exists. The proof follows a pair of trajectories through a Markov chain on states {v, 3^k v + c} driven by fair coin flips, which describes the residue classes modulo 2^t exactly, and shows that the chain is absorbed almost surely. The ingredients are a contraction of the square root of |c|/3^k, a harmonic function for the level k, a clock controlling long runs of equal parity, a window in which the offset returns to a bounded range, a universal absorbing word of length O(log^2(2+|c|)), and a counting argument for repeated trials that never conditions on the future. A short lemma shows that a meeting within log_2 n steps is already a coalescence in Gao's sense. Every step is formalized in Lean 4 with Mathlib, and the final theorems depend only on the axioms propext, Classical.choice and Quot.sound. The results concern coalescence only: they do not show that any integer reaches 1, and the convergence is extremely slow.
Related
- Toward a Formally Verified Optimality Certificate for OGR(29): A SAT-Encoding Methods Note with Small-Case Demos
- Reducing Every Set of 36 Consecutive Integers to Zero by Differences of Squares
- Note on the largest prime factors of consecutive integers
- Counting Admissible Sets of Integers: A Proof of the Erdős--Nicolas--Sárközy Conjecture
- Close Divisors of Typical Integers:The Ford--Green--Koukoulopoulos Conjecture
BibTeX
@misc{duran2026consecutive,
title = {{Consecutive integers coalesce with density one under the Collatz map: a formally verified proof of a conjecture of Gao}},
author = {Omar Javier Said Duran},
howpublished = {Zenodo (CERN European Organization for Nuclear Research)},
year = {2026},
month = sep,
doi = {10.5281/zenodo.23003523},
url = {https://doi.org/10.5281/zenodo.23003523},
note = {CC BY},
}
RIS
TY - UNPB
TI - Consecutive integers coalesce with density one under the Collatz map: a formally verified proof of a conjecture of Gao
AU - Omar Javier Said Duran
PY - 2026
DA - 2026/09/27
PB - Zenodo (CERN European Organization for Nuclear Research)
DO - 10.5281/zenodo.23003523
UR - https://doi.org/10.5281/zenodo.23003523
AB - Let C be the Collatz map, C(n) = n/2 for even n and C(n) = 3n+1 for odd n. Following Gao (1993), two consecutive integers n and n+1 coalesce if C^k(n) = C^k(n+1) for some k, with the same number of halvings on both trajectories and without either trajectory passing through 1. Gao computed the normalized count d̄_k of the n < 2^k − 1 for which this happens within k steps, proved that d̄_k is nondecreasing, and conjectured that d̄_k → 1. In the form recorded by Lagarias, the conjecture states that the set of n with C^k(n) = C^k(n+1) for some k ≤ log_2 n has natural density one. We prove both statements, and also that the proportion d(x) of n < x for which n and n+1 coalesce tends to 1; Gao did not know whether this limit exists. The proof follows a pair of trajectories through a Markov chain on states {v, 3^k v + c} driven by fair coin flips, which describes the residue classes modulo 2^t exactly, and shows that the chain is absorbed almost surely. The ingredients are a contraction of the square root of |c|/3^k, a harmonic function for the level k, a clock controlling long runs of equal parity, a window in which the offset returns to a bounded range, a universal absorbing word of length O(log^2(2+|c|)), and a counting argument for repeated trials that never conditions on the future. A short lemma shows that a meeting within log_2 n steps is already a coalescence in Gao's sense. Every step is formalized in Lean 4 with Mathlib, and the final theorems depend only on the axioms propext, Classical.choice and Quot.sound. The results concern coalescence only: they do not show that any integer reaches 1, and the convergence is extremely slow.
ER -