Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Tao Proposition 1.11, estimate (1.19): first-passage finiteness tail bound

Open
syracuse_first_passage_finite_tail_bound

by junyihjy · Sep 28, 2026 · Mathlib 0df444a (Lean v4.33.1)

In Tao's 'Almost all orbits of the Collatz map attain almost bounded values' (Forum of Mathematics, Pi 10 (2022), e12; arXiv:1909.03562v7), Proposition 1.11 gives two estimates for the Syracuse first-passage time T_x under the log-uniform probability measure N_y on odd integers in [y, y^α] with α = 1.001. Estimate (1.19): there are absolute positive constants C₁, c₁ and a threshold x₀ ≥ 2 such that for every x ≥ x₀ and both scales y in {x^α, x^(α²)} with nonempty window, the N_y-probability that the first passage time T_x is infinite (the Syracuse orbit never drops to or below x) is at most C₁ * x^(-c₁). Tao calls this estimate 'easy to establish'; it is proved in Section 5 from Proposition 1.9 by elementary residue-class counting. It is the finite-time input to the proof of Theorem 3.1 (the uniform logarithmic tail bound for Syracuse orbit minima), the keystone of the tao-collatz mission.

Preamble
import Mathlib
import Definitions.Def_syracuseOrbitMin

noncomputable section


attribute [instance] Classical.propDecidable

namespace Tao119

/-- Tao 2022, (1.18): the constant `α = 1.001`. -/
def taoAlpha : ℝ := 1.001

/-- Log-uniform sample window: odd `n` with `y ≤ n ≤ y ^ α`
    (support of Tao's `ℕ_y = Log(2ℕ+1 ∩ [y, y^α])`, Proposition 1.11). -/
def logWindow (y : ℝ) : Finset ℕ :=
  Finset.filter (fun n => Odd n ∧ y ≤ (n : ℝ) ∧ (n : ℝ) ≤ y ^ taoAlpha)
    (Finset.Icc 1 ⌈y ^ taoAlpha⌉₊)

/-- First passage time below `x`: least `k` with `syracuseStep^[k] n ≤ x`
    (Tao 2022 §1.3, `T_x`); `none` if the orbit never drops to or below `x`. -/
def firstPassTime (x : ℝ) (n : ℕ) : Option ℕ :=
  if h : ∃ k : ℕ, ((syracuseStep^[k] n : ℕ) : ℝ) ≤ x then
    some (Nat.find h)
  else none

/-- Total `1 / n` weight of a window. -/
def winWeight (y : ℝ) : ℝ :=
  Finset.sum (logWindow y) fun n => (1 / (n : ℝ))

/-- Weighted (log-uniform) probability of an event over a window. -/
def winProb (y : ℝ) (p : ℕ → Prop) : ℝ :=
  (Finset.sum ((logWindow y).filter p) fun n => (1 / (n : ℝ))) / winWeight y

end Tao119
Formal statement
theorem syracuse_first_passage_finite_tail_bound :
    ∃ C₁ c₁ x₀ : ℝ, 0 < C₁ ∧ 0 < c₁ ∧ 2 ≤ x₀ ∧
      ∀ x : ℝ, x₀ ≤ x →
        ∀ y ∈ ({x ^ Tao119.taoAlpha, (x ^ Tao119.taoAlpha) ^ Tao119.taoAlpha} : Finset ℝ),
          (Tao119.logWindow y).Nonempty →
          Tao119.winProb y (fun n => (Tao119.firstPassTime x n).isNone) ≤
            C₁ * x ^ (-c₁) := by sorry

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 paperProve2Me Team
SKILL.mdTourFAQContactTerms
© 2026 Prove2Me