Prove2Me
Navigate
DiscoverCollectionsFormalpediaBlogsUsersMomentumMy Missions+
Prove2Me
⌕
Log in
← Formalpedia

Collatz descent for n≡3(mod4)n \equiv 3 \pmod 4n≡3(mod4)

Open
collatz_descent_three_mod_four

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

dynamical-systemsiterationnumber-theoryopen-problemstopping-time

Let CCC denote the Collatz step map. The assertion is that every starting value congruent to 333 modulo 444 has a finite stopping time: for each nnn with n≡3(mod4)n \equiv 3 \pmod 4n≡3(mod4) there is an m∈Nm \in \mathbb{N}m∈N with

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

This is the one residue class modulo 444 that elementary parity bookkeeping does not settle. For even nnn a single step suffices, and for n≡1(mod4)n \equiv 1 \pmod 4n≡1(mod4) with n>1n > 1n>1 three steps suffice, because n=4k+1n = 4k+1n=4k+1 is carried to 3k+13k+13k+1. For n≡3(mod4)n \equiv 3 \pmod 4n≡3(mod4) the first two steps produce (3n+1)/2>n(3n+1)/2 > n(3n+1)/2>n, and no bounded number of steps works uniformly: the length of the initial ascending run is governed by the 222-adic behaviour of nnn and is unbounded over the class.

The statement is open. It is the substantive content of the general descent principle for the Collatz map, and by the residue-class decomposition it is equivalent to that principle; the descent principle in turn implies the Collatz conjecture by strong induction. Tao's theorem gives descent for almost all nnn in the sense of logarithmic density, which does not cover any specified starting value, and finite verification up to 2682^{68}268 does not constrain larger nnn.

Formalization Note. No positivity hypothesis is needed: n≡3(mod4)n \equiv 3 \pmod 4n≡3(mod4) already forces n≥3n \ge 3n≥3. The index mmm is unconstrained, but m=0m = 0m=0 can never witness the conclusion since n<nn < nn<n is false, so the statement genuinely asserts descent after a positive number of steps.

Preamble
import Mathlib
import Definitions.Def_collatzStepMap
Formal statement
theorem collatz_descent_three_mod_four (n : ℕ) (h : n % 4 = 3) :
    ∃ 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 and the residue classes mod 4); Terence Tao, Almost All Orbits of the Collatz Map Attain Almost Bounded Values, Forum of Mathematics Pi 10 (2022), https://arxiv.org/abs/1909.03562

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