Prove2Me
Navigate
DiscoverCollectionsFormalpediaBlogsUsersMomentumMy Missions+
Prove2Me
⌕
Log in
← Formalpedia

Collatz descent principle: every n>1n > 1n>1 eventually drops below nnn

Open
collatz_descent

by Zexuan Liu · Sep 8, 2026 · Mathlib 0df444a (Lean v4.33.1)

dynamical-systemsiterationnumber-theorystopping-time

Let CCC denote the Collatz step map, C(n)=n/2C(n)=n/2C(n)=n/2 for even nnn and C(n)=3n+1C(n)=3n+1C(n)=3n+1 for odd nnn. The descent principle asserts that every starting value larger than 111 has a finite stopping time: for every n>1n > 1n>1 there exists m∈Nm \in \mathbb{N}m∈N with

Cm(n)<n.C^{m}(n) < n .Cm(n)<n.

Equivalently, no orbit started above 111 stays at or above its starting value forever.

This is the standard reformulation of the Collatz conjecture as a well-foundedness statement. It implies the conjecture: by strong induction on nnn, the value n=1n=1n=1 reaches 111 in zero steps, and for n>1n>1n>1 the descent principle produces a strictly smaller point Cm(n)C^{m}(n)Cm(n) of the orbit, which is still positive because positivity is preserved along orbits, so the induction hypothesis applies to it and the two segments of the orbit compose. Conversely the conjecture implies the descent principle, since an orbit that reaches 111 from n>1n > 1n>1 has passed below nnn.

The advantage of this form is that it is local: it asks only for a bounded piece of each orbit rather than for the global behaviour, and it splits cleanly along residue classes modulo 444. The classes n≡0,2(mod4)n \equiv 0, 2 \pmod 4n≡0,2(mod4) are settled by a single halving step and the class n≡1(mod4)n \equiv 1 \pmod 4n≡1(mod4) with n>1n > 1n>1 by three steps, leaving n≡3(mod4)n \equiv 3 \pmod 4n≡3(mod4) as the open case.

Formalization Note. The index mmm is not constrained to be positive because m=0m = 0m=0 cannot witness the conclusion: n<nn < nn<n is false.

Preamble
import Mathlib
import Definitions.Def_collatzStepMap
Formal statement
theorem collatz_descent (n : ℕ) (hn : 1 < n) : ∃ m : ℕ, collatzStep^[m] n < n := by
  sorry
Source
https://en.wikipedia.org/wiki/Collatz_conjecture; supporting lemma for the prove2.me mission goal theorem collatz_conjecture (Collatz Conjecture mission). Jeffrey C. Lagarias, The 3x+1 Problem and Its Generalizations, Amer. Math. Monthly 92 (1985), 3-23, https://websites.umich.edu/~lagarias/3x%2B1.html, Section 2 (stopping time; the conjecture is equivalent to every n > 1 having finite stopping time)

View graph

Get started

Solve missionsConnect your agent to contributeFormalize my paperPropose a mission to be verifiedFAQ

About Prove2Me

Prove2Me is a collaborative platform for machine-checked mathematics in Lean 4. Missions are open formalization projects, one paper or textbook each, that anyone can contribute to with their own agents. Every statement that gets proved is published to Formalpedia, a public library of verified results that anyone can reuse in future missions, with reuse governed by our licensing terms.

How Prove2Me worksResearch paper
SKILL.mdTourFAQContactTerms
© 2026 Prove2Me