Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Computable analysis · FiniteBisectionIteration · fd889115 k1

Definition
liuyao_ca_fd889115_k1_Analysis_FiniteBisectionIteration

by liuyao · Nov 15, 2026 · Mathlib 0df444a (Lean v4.33.1)

ca-fd889115-k1

Private dependency for the Distribution Theory mission. Module ComputableAnalysis/FiniteBisectionIteration.lean from the frozen computable-analysis foundation with kernel-checked rational decision proofs.

Definition code
import Definitions.Def_liuyao_ca_fd889115_k1_Analysis_FiniteBisection

set_option autoImplicit true

/-!
# Finite rational bisection iterations

This module iterates the exact rational bisection step.  All invariants are
finite certificates: the interval remains rational, the sign bracket is
preserved, and the width is known exactly at every finite stage.  No zero
existence or completeness principle is used.
-/

namespace ComputableAnalysis

open QInterval

/-- Apply `monotoneBisectionStep` exactly `n` times. -/
def monotoneBisectionIterate (f : Rat -> Rat) : Nat -> QInterval -> QInterval
  | 0, I => I
  | n + 1, I => monotoneBisectionStep f (monotoneBisectionIterate f n I)

theorem monotoneBisectionIterate_ordered {f : Rat -> Rat} {I : QInterval}
    (hI : I.lo ≤ I.hi) (n : Nat) :
    (monotoneBisectionIterate f n I).lo ≤
      (monotoneBisectionIterate f n I).hi := by
  induction n generalizing I with
  | zero => exact hI
  | succ n ih =>
      exact monotoneBisectionStep_ordered (ih hI)

theorem monotoneBisectionIterate_subinterval {f : Rat -> Rat} {I : QInterval}
    (hI : I.lo ≤ I.hi) (n : Nat) :
    (monotoneBisectionIterate f n I).lo ≥ I.lo /\
      (monotoneBisectionIterate f n I).hi ≤ I.hi := by
  induction n generalizing I with
  | zero => exact ⟨Rat.le_refl, Rat.le_refl⟩
  | succ n ih =>
      have hJ := ih hI
      have hJord := monotoneBisectionIterate_ordered (f := f) hI n
      have hstep := monotoneBisectionStep_subinterval (f := f) hJord
      exact ⟨Rat.le_trans hJ.1 hstep.1, Rat.le_trans hstep.2 hJ.2⟩

theorem monotoneBisectionIterate_preserves_bracket
    {f : Rat -> Rat} {I : QInterval}
    (hI : I.lo ≤ I.hi)
    (hf : ∀ ⦃x y : Rat⦄, x ≤ y -> f x ≤ f y)
    (hlo : f I.lo ≤ 0) (hhi : 0 ≤ f I.hi) (n : Nat) :
    f (monotoneBisectionIterate f n I).lo ≤ 0 /\
      0 ≤ f (monotoneBisectionIterate f n I).hi := by
  induction n generalizing I with
  | zero => exact ⟨hlo, hhi⟩
  | succ n ih =>
      have hJ := ih hI hlo hhi
      exact monotoneBisectionStep_preserves_bracket
        (monotoneBisectionIterate_ordered hI n) hf hJ.1 hJ.2

/-! Iterated target bracketing for the constructive inverse interface. -/

def monotoneTargetBisectionIterate (f : Rat -> Rat) (y : Rat) :
    Nat -> QInterval -> QInterval
  | 0, I => I
  | n + 1, I =>
      monotoneTargetBisectionStep f y (monotoneTargetBisectionIterate f y n I)

theorem monotoneTargetBisectionIterate_ordered
    {f : Rat -> Rat} {I : QInterval} (y : Rat)
    (hI : I.lo ≤ I.hi) (n : Nat) :
    (monotoneTargetBisectionIterate f y n I).lo ≤
      (monotoneTargetBisectionIterate f y n I).hi := by
  induction n generalizing I with
  | zero => exact hI
  | succ n ih =>
      have hprev := ih hI
      have hm := (monotoneTargetBisectionIterate f y n I).midpoint_mem hprev
      by_cases hmid : y ≤ f (monotoneTargetBisectionIterate f y n I).midpoint
      · simp [monotoneTargetBisectionIterate, monotoneTargetBisectionStep,
          hmid, hm.1]
      · simp [monotoneTargetBisectionIterate, monotoneTargetBisectionStep,
          hmid, hm.2]

theorem monotoneTargetBisectionIterate_subinterval
    {f : Rat -> Rat} {I : QInterval} (y : Rat)
    (hI : I.lo ≤ I.hi) (n : Nat) :
    (monotoneTargetBisectionIterate f y n I).lo ≥ I.lo /\
      (monotoneTargetBisectionIterate f y n I).hi ≤ I.hi := by
  induction n generalizing I with
  | zero => exact ⟨Rat.le_refl, Rat.le_refl⟩
  | succ n ih =>
      have hprev := ih hI
      have hprevOrd := monotoneTargetBisectionIterate_ordered
        (f := f) y hI n
      have hstep := monotoneTargetBisectionStep_subinterval (f := f) y hprevOrd
      exact ⟨Rat.le_trans hprev.1 hstep.1,
        Rat.le_trans hstep.2 hprev.2⟩

theorem monotoneTargetBisectionIterate_add
    {f : Rat -> Rat} (y : Rat) (m n : Nat) (I : QInterval) :
    monotoneTargetBisectionIterate f y (m + n) I =
      monotoneTargetBisectionIterate f y n
        (monotoneTargetBisectionIterate f y m I) := by
  induction n with
  | zero => simp [monotoneTargetBisectionIterate]
  | succ n ih =>
      simp only [monotoneTargetBisectionIterate]
      exact congrArg (monotoneTargetBisectionStep f y) ih

theorem monotoneTargetBisectionIterate_later_subinterval
    {f : Rat -> Rat} {I : QInterval} (y : Rat)
    (hI : I.lo ≤ I.hi) {m n : Nat} (hmn : m ≤ n) :
    (monotoneTargetBisectionIterate f y n I).lo ≥
        (monotoneTargetBisectionIterate f y m I).lo /\
      (monotoneTargetBisectionIterate f y n I).hi ≤
        (monotoneTargetBisectionIterate f y m I).hi := by
  obtain ⟨k, rfl⟩ := Nat.exists_eq_add_of_le hmn
  rw [monotoneTargetBisectionIterate_add]
  exact monotoneTargetBisectionIterate_subinterval y
    (monotoneTargetBisectionIterate_ordered (f := f) y hI m) k

theorem monotoneTargetBisectionIterate_width
    {f : Rat -> Rat} {I : QInterval} (y : Rat) (n : Nat) :
    (monotoneTargetBisectionIterate f y n I).width =
      I.width / (2 ^ n : Rat) := by
  induction n with
  | zero =>
      simp only [monotoneTargetBisectionIterate, QInterval.width, Rat.div_def]
      have hinv : (1 : Rat)⁻¹ = 1 := by
        have h := Rat.mul_inv_cancel (1 : Rat) (by decide)
        simpa using h
      rw [Rat.pow_zero, hinv, Rat.mul_one]
  | succ n ih =>
      rw [monotoneTargetBisectionIterate,
        monotoneTargetBisectionStep_width, ih]
      rw [Rat.pow_succ]
      grind [Rat.div_def, Rat.mul_assoc, Rat.mul_comm]

theorem monotoneTargetBisectionIterate_width_pos
    {f : Rat -> Rat} {I : QInterval} (y : Rat) (n : Nat)
    (hwidth : 0 < I.width) :
    0 < (monotoneTargetBisectionIterate f y n I).width := by
  rw [monotoneTargetBisectionIterate_width]
  rw [Rat.div_def]
  exact Rat.mul_pos hwidth
    ((Rat.inv_pos).2 (Rat.pow_pos (by decide +kernel)))

theorem monotoneTargetBisectionIterate_width_le_of_power_budget
    {f : Rat -> Rat} {I : QInterval} {y eps : Rat} {n : Nat}
    (hbudget : I.width <= eps * (2 ^ n : Rat)) :
    (monotoneTargetBisectionIterate f y n I).width <= eps := by
  rw [monotoneTargetBisectionIterate_width]
  rw [Rat.div_def]
  have hpow : 0 < (2 ^ n : Rat) := by
    exact Rat.pow_pos (by decide +kernel)
  have hpow0 : (2 ^ n : Rat) ≠ 0 := Rat.ne_of_gt hpow
  have hinv : 0 <= (2 ^ n : Rat)⁻¹ :=
    Rat.le_of_lt ((Rat.inv_pos).2 hpow)
  calc
    I.width * (2 ^ n : Rat)⁻¹ <=
        (eps * (2 ^ n : Rat)) * (2 ^ n : Rat)⁻¹ :=
      Rat.mul_le_mul_of_nonneg_right hbudget hinv
    _ = eps := by
      rw [Rat.mul_assoc, Rat.mul_inv_cancel _ hpow0, Rat.mul_one]

private theorem nat_succ_le_two_pow (n : Nat) :
    n + 1 <= 2 ^ n := by
  induction n with
  | zero => omega
  | succ n ih =>
      rw [Nat.pow_succ]
      omega

theorem monotoneTargetBisectionIterate_width_le_one_div_succ
    {f : Rat -> Rat} {I : QInterval} (y : Rat) (n : Nat)
    (hwidth : I.width <= 1) :
    (monotoneTargetBisectionIterate f y n I).width <=
      1 / (((n + 1 : Nat) : Rat)) := by
  rw [monotoneTargetBisectionIterate_width]
  let A : Rat := ((n + 1 : Nat) : Rat)
  let B : Rat := (2 ^ n : Rat)
  have hApos : 0 < A := by
    dsimp [A]
    exact (Rat.natCast_pos).2 (Nat.succ_pos n)
  have hBpos : 0 < B := by
    dsimp [B]
    exact Rat.pow_pos (by decide +kernel)
  have hAne : A ≠ 0 := Rat.ne_of_gt hApos
  have hBne : B ≠ 0 := Rat.ne_of_gt hBpos
  have hAB : A <= B := by
    dsimp [A, B]
    exact_mod_cast nat_succ_le_two_pow n
  apply Rat.le_of_mul_le_mul_right (c := A * B)
  · calc
      (I.width / B) * (A * B) = I.width * A := by
        rw [Rat.div_def]
        have hcancel : B⁻¹ * B = 1 := Rat.inv_mul_cancel B hBne
        grind [Rat.mul_assoc, Rat.mul_comm]
      _ <= 1 * A := Rat.mul_le_mul_of_nonneg_right hwidth
        (Rat.le_of_lt hApos)
      _ = A := by rw [Rat.one_mul]
      _ <= B := hAB
      _ = (1 / A) * (A * B) := by
        rw [Rat.div_def]
        have hcancel : A * A⁻¹ = 1 := Rat.mul_inv_cancel A hAne
        grind [Rat.mul_assoc, Rat.mul_comm]
  · exact Rat.mul_pos hApos hBpos

theorem monotoneTargetBisectionIterate_reaches_of_positive_tolerance
    {f : Rat -> Rat} {I : QInterval} (y : Rat)
    (hwidth : I.width <= 1) (eps : QPos) :
    (monotoneTargetBisectionIterate f y eps.val.den I).width <= eps.val := by
  calc
    (monotoneTargetBisectionIterate f y eps.val.den I).width <=
        1 / (((eps.val.den + 1 : Nat) : Rat)) :=
      monotoneTargetBisectionIterate_width_le_one_div_succ y
        eps.val.den hwidth
    _ <= eps.val := one_div_den_succ_le_of_pos eps.property

theorem monotoneBisectionIterate_preserves_target_bracket
    {f : Rat -> Rat} {I : QInterval} (y : Rat)
    (hI : I.lo ≤ I.hi)
    (hlo : f I.lo ≤ y) (hhi : y ≤ f I.hi) (n : Nat) :
    f (monotoneTargetBisectionIterate f y n I).lo ≤ y /\
      y ≤ f (monotoneTargetBisectionIterate f y n I).hi := by
  induction n generalizing I with
  | zero => exact ⟨hlo, hhi⟩
  | succ n ih =>
      have hJ := ih hI hlo hhi
      have hJord := monotoneTargetBisectionIterate_ordered (f := f) y hI n
      exact monotoneBisectionStep_preserves_target_bracket y hJord hJ.1 hJ.2

/-! A single finite certificate packages the invariants needed by an inverse
search client.  It records no limiting point: the output is still the exact
rational interval produced after the requested finite number of steps. -/
theorem monotoneTargetBisectionIterate_certificate
    {f : Rat -> Rat} {I : QInterval} (y : Rat)
    (hI : I.lo ≤ I.hi)
    (hlo : f I.lo ≤ y) (hhi : y ≤ f I.hi) (n : Nat) :
    (monotoneTargetBisectionIterate f y n I).lo ≤
        (monotoneTargetBisectionIterate f y n I).hi /\
      (f (monotoneTargetBisectionIterate f y n I).lo ≤ y /\
        y ≤ f (monotoneTargetBisectionIterate f y n I).hi) /\
      ((monotoneTargetBisectionIterate f y n I).lo ≥ I.lo /\
        (monotoneTargetBisectionIterate f y n I).hi ≤ I.hi) /\
      (monotoneTargetBisectionIterate f y n I).width =
        I.width / (2 ^ n : Rat) := by
  refine ⟨monotoneTargetBisectionIterate_ordered y hI n, ?_, ?_,
    monotoneTargetBisectionIterate_width y n⟩
  · exact monotoneBisectionIterate_preserves_target_bracket y hI hlo hhi n
  · exact monotoneTargetBisectionIterate_subinterval y hI n

/-! The tolerance-indexed form is the object an inverse-search client can
consume directly: the stage is chosen from the positive rational budget, and
all finite invariants are returned together with the width bound. -/
theorem monotoneTargetBisectionIterate_tolerance_certificate
    {f : Rat -> Rat} {I : QInterval} (y : Rat)
    (hI : I.lo ≤ I.hi)
    (hlo : f I.lo ≤ y) (hhi : y ≤ f I.hi)
    (hwidth : I.width ≤ 1) (eps : QPos) :
    let J := monotoneTargetBisectionIterate f y eps.val.den I
    J.lo ≤ J.hi /\
      (f J.lo ≤ y /\ y ≤ f J.hi) /\
      (J.lo ≥ I.lo /\ J.hi ≤ I.hi) /\
      J.width ≤ eps.val := by
  let J := monotoneTargetBisectionIterate f y eps.val.den I
  have hcert := monotoneTargetBisectionIterate_certificate
    (f := f) (I := I) y hI hlo hhi eps.val.den
  have hreach := monotoneTargetBisectionIterate_reaches_of_positive_tolerance
    (f := f) (I := I) y hwidth eps
  dsimp [J]
  exact ⟨hcert.1, hcert.2.1, hcert.2.2.1, hreach⟩

theorem monotoneBisectionIterate_width {f : Rat -> Rat} {I : QInterval}
    (n : Nat) :
    (monotoneBisectionIterate f n I).width = I.width / (2 ^ n : Rat) := by
  induction n with
  | zero =>
      simp only [monotoneBisectionIterate, QInterval.width, Rat.div_def]
      have hinv : (1 : Rat)⁻¹ = 1 := by
        have h := Rat.mul_inv_cancel (1 : Rat) (by decide)
        simpa using h
      rw [Rat.pow_zero, hinv, Rat.mul_one]
  | succ n ih =>
      rw [monotoneBisectionIterate, monotoneBisectionStep_width, ih]
      rw [Rat.pow_succ]
      grind [Rat.div_def, Rat.mul_assoc, Rat.mul_comm]

theorem monotoneBisectionIterate_width_pos
    {f : Rat -> Rat} {I : QInterval} (n : Nat)
    (hwidth : 0 < I.width) :
    0 < (monotoneBisectionIterate f n I).width := by
  rw [monotoneBisectionIterate_width]
  rw [Rat.div_def]
  exact Rat.mul_pos hwidth
    ((Rat.inv_pos).2 (Rat.pow_pos (by decide +kernel)))

/-- A supplied rational power budget turns the exact finite width formula into
an executable bisection precision certificate. -/
theorem monotoneBisectionIterate_width_le_of_power_budget
    {f : Rat -> Rat} {I : QInterval} {n : Nat} {eps : Rat}
    (hbudget : I.width <= eps * (2 ^ n : Rat)) :
    (monotoneBisectionIterate f n I).width <= eps := by
  rw [monotoneBisectionIterate_width]
  rw [Rat.div_def]
  have hpow : 0 < (2 ^ n : Rat) := by
    exact Rat.pow_pos (by decide +kernel)
  have hpow0 : (2 ^ n : Rat) ≠ 0 := Rat.ne_of_gt hpow
  have hinv : 0 <= (2 ^ n : Rat)⁻¹ := Rat.le_of_lt ((Rat.inv_pos).2 hpow)
  calc
    I.width * (2 ^ n : Rat)⁻¹ <=
        (eps * (2 ^ n : Rat)) * (2 ^ n : Rat)⁻¹ :=
      Rat.mul_le_mul_of_nonneg_right hbudget hinv
    _ = eps := by
      rw [Rat.mul_assoc, Rat.mul_inv_cancel _ hpow0, Rat.mul_one]

end ComputableAnalysis

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