Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Computable analysis · RealReciprocal · fd889115 k1

Definition
liuyao_ca_fd889115_k1_Analysis_RealReciprocal

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

ca-fd889115-k1

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

Definition code
import Definitions.Def_liuyao_ca_fd889115_k1_Analysis_PositiveReciprocal
import Definitions.Def_liuyao_ca_fd889115_k1_Analysis_Numbers

set_option autoImplicit true

/-! A signed reciprocal on the genuine nonzero domain. The first separated
input interval is found by executable search; proof-only existence establishes
termination. No sign test or equality decision on real values is performed. -/
namespace ComputableAnalysis.CertifiedReciprocal

set_option maxHeartbeats 1000000
set_option maxRecDepth 4096

private def next (p : Nat → Prop) (m n : Nat) : Prop := m=n+1 ∧ ¬p n

private theorem accessible (p : Nat → Prop) (d n : Nat) (h : p (n+d)) :
    Acc (next p) n := by
  induction d generalizing n with
  | zero =>
    apply Acc.intro
    intro m hm
    exact False.elim (hm.2 (by simpa using h))
  | succ d ih =>
    apply Acc.intro
    intro m hm
    rcases hm with ⟨rfl,_⟩
    apply ih
    simpa [Nat.add_assoc,Nat.add_comm,Nat.add_left_comm] using h

private def searchFrom (p : Nat → Prop) [DecidablePred p] (n : Nat)
    (h : Acc (next p) n) : {k // p k} :=
  Acc.rec (motive := fun _ _ => {k // p k})
    (fun n _ recurse => if hn : p n then ⟨n,hn⟩ else recurse (n+1) ⟨rfl,hn⟩) h

private theorem searchFrom_le (p : Nat → Prop) [DecidablePred p] (n : Nat)
    (h : Acc (next p) n) (m : Nat) (hnm : n ≤ m) (hm : p m) :
    (searchFrom p n h).val ≤ m := by
  induction h generalizing m with
  | intro n children ih =>
    dsimp [searchFrom]
    split
    · exact hnm
    · apply ih (n+1) ⟨rfl,‹¬p n›⟩ m
      · by_cases h : n=m
        · subst m; contradiction
        · omega
      · exact hm

private theorem searchAccessible (p : Nat → Prop) (h : ∃ n,p n) : Acc (next p) 0 := by
  obtain ⟨n,hn⟩ := h
  exact accessible p n 0 (by simpa using hn)

private def first (p : Nat → Prop) [DecidablePred p] (h : ∃ n,p n) : {n // p n} :=
  searchFrom p 0 (searchAccessible p h)

private theorem first_le (p : Nat → Prop) [DecidablePred p] (h : ∃ n,p n)
    (m : Nat) (hm : p m) : (first p h).val ≤ m :=
  searchFrom_le p 0 (searchAccessible p h) m (Nat.zero_le m) hm

private theorem first_agrees (p q : Nat → Prop) [DecidablePred p] [DecidablePred q]
    (hp : ∃ n,p n) (hq : ∃ n,q n)
    (h : ∀ j,j ≤ (first p hp).val → (p j ↔ q j)) :
    (first p hp).val = (first q hq).val := by
  have hqle := first_le q hq _ ((h _ (Nat.le_refl _)).mp (first p hp).property)
  have hple := first_le p hp _ ((h _ hqle).mpr (first q hq).property)
  exact Nat.le_antisymm hple hqle

def Nonzero (x : RealCompute) : Prop := ¬x.Equiv (RealCompute.ofRat 0)

def Separated (x : RealCompute) (n : Nat) : Prop :=
  0 < (x.compute n).lo ∨ (x.compute n).hi < 0

instance (x : RealCompute) : DecidablePred (Separated x) := fun n => inferInstanceAs
  (Decidable (0 < (x.compute n).lo ∨ (x.compute n).hi < 0))

theorem nonzero_of_separated (x : RealCompute) (n : Nat) (h : Separated x n) : Nonzero x := by
  intro heq
  have ho := (RealCompute.compareAt_overlap_iff _ _ n n).mp (heq n)
  change (x.compute n).lo ≤ 0 ∧ 0 ≤ (x.compute n).hi at ho
  dsimp [Separated] at h
  grind

theorem exists_separated (x : RealCompute) (h : Nonzero x) : ∃ n,Separated x n := by
  by_cases hex : ∃ n,Separated x n
  · exact hex
  · exfalso
    apply h
    apply RealCompute.sameStageOverlap_equiv
    intro n
    apply (RealCompute.compareAt_overlap_iff _ _ n n).mpr
    have hn : ¬Separated x n := fun hn => hex ⟨n,hn⟩
    change (x.compute n).lo ≤ 0 ∧ 0 ≤ (x.compute n).hi
    dsimp [Separated] at hn
    grind

def pivot (x : RealCompute) (h : Nonzero x) : Nat := (first (Separated x) (exists_separated x h)).val

theorem pivot_spec (x : RealCompute) (h : Nonzero x) : Separated x (pivot x h) :=
  (first (Separated x) (exists_separated x h)).property

theorem pivot_congr {x z : RealCompute} (hx : Nonzero x) (hz : Nonzero z)
    (h : ∀ j,j ≤ pivot x hx → x.compute j=z.compute j) : pivot x hx=pivot z hz := by
  apply first_agrees
  intro j hj
  change (0 < (x.compute j).lo ∨ (x.compute j).hi < 0) ↔
    (0 < (z.compute j).lo ∨ (z.compute j).hi < 0)
  rw [h j hj]

def reciprocal (x : RealCompute) (h : Nonzero x) : RealCompute :=
  if 0 < (x.compute (pivot x h)).lo then
    x.positiveReciprocal (x.compute (pivot x h)).lo
  else
    -((-x).positiveReciprocal (-(x.compute (pivot x h)).hi))

theorem reciprocal_valid (x : RealCompute) (hx : x.Valid) (hnz : Nonzero x) :
    (reciprocal x hnz).Valid := by
  have hp := pivot_spec x hnz
  unfold reciprocal
  split
  · apply RealCompute.positiveReciprocal_valid x _ hx ‹_›
    intro n
    exact RealCompute.le_refl x hx (pivot x hnz) n
  · apply RealCompute.neg_valid
    apply RealCompute.positiveReciprocal_valid (-x) _ (RealCompute.neg_valid hx)
    · dsimp [Separated] at hp
      grind
    · intro n
      have hle := RealCompute.le_refl x hx n (pivot x hnz)
      change -(x.compute (pivot x hnz)).hi ≤ -(x.compute n).lo
      grind

private theorem inv_antitone_pos {a b : Rat} (ha : 0 < a) (hab : a ≤ b) : b⁻¹ ≤ a⁻¹ := by
  have hb : 0 < b := by grind
  have ia := Rat.le_of_lt (Rat.inv_pos.mpr ha)
  have ib := Rat.le_of_lt (Rat.inv_pos.mpr hb)
  have hm := Rat.mul_le_mul_of_nonneg_left hab (Rat.mul_nonneg ia ib)
  have ca := Rat.mul_inv_cancel a (by grind : a≠0)
  have cb := Rat.mul_inv_cancel b (by grind : b≠0)
  have ea : a⁻¹*b⁻¹*a=b⁻¹ := by
    calc
      _ = (a*a⁻¹)*b⁻¹ := by grind
      _ = b⁻¹ := by rw [ca,Rat.one_mul]
  have eb : a⁻¹*b⁻¹*b=a⁻¹ := by
    calc
      _ = (b*b⁻¹)*a⁻¹ := by grind
      _ = a⁻¹ := by rw [cb,Rat.one_mul]
  simpa only [ea,eb] using hm

private theorem positive_congr (x z : RealCompute) (hx : x.Valid) (hz : z.Valid)
    (a b : Rat) (ha : 0<a) (hb : 0<b)
    (hax : ∀n,a ≤ (x.compute n).hi) (hbz : ∀n,b ≤ (z.compute n).hi)
    (heq : x.Equiv z) : (x.positiveReciprocal a).Equiv (z.positiveReciprocal b) := by
  have hxz := RealCompute.le_of_equiv hx hz heq
  have hzx := RealCompute.le_of_equiv hz hx (RealCompute.equiv_symm heq)
  have haz := RealCompute.le_trans hx (show (RealCompute.ofRat a).Le x from fun _ n => hax n) hxz
  have hbx := RealCompute.le_trans hz (show (RealCompute.ofRat b).Le z from fun _ n => hbz n) hzx
  apply RealCompute.sameStageOverlap_equiv
  intro n
  apply (RealCompute.compareAt_overlap_iff _ _ n n).mpr
  rw [RealCompute.positiveReciprocal_compute x a ha n,RealCompute.positiveReciprocal_compute z b hb n]
  have hxzn := hxz n n
  have hzxn := hzx n n
  have hazn := haz 0 n
  have hbxn := hbx 0 n
  change a ≤ (z.compute n).hi at hazn
  change b ≤ (x.compute n).hi at hbxn
  have hla : 0 < maxRat2 (x.compute n).lo a := by dsimp [maxRat2]; split <;> grind
  have hlb : 0 < maxRat2 (z.compute n).lo b := by dsimp [maxRat2]; split <;> grind
  have hba : maxRat2 (z.compute n).lo b ≤ (x.compute n).hi := by
    dsimp [maxRat2]; split <;> grind
  have hab : maxRat2 (x.compute n).lo a ≤ (z.compute n).hi := by
    dsimp [maxRat2]; split <;> grind
  exact ⟨by simpa [Rat.div_def] using inv_antitone_pos hlb hba,
    by simpa [Rat.div_def] using inv_antitone_pos hla hab⟩

/-- Positive reciprocal computations agree across valid equivalent names and
different certified positive lower bounds. -/
theorem positiveReciprocal_congr (x z : RealCompute) (hx : x.Valid) (hz : z.Valid)
    (a b : Rat) (ha : 0<a) (hb : 0<b)
    (hax : ∀ n,a≤(x.compute n).hi) (hbz : ∀ n,b≤(z.compute n).hi)
    (heq : x.Equiv z) : (x.positiveReciprocal a).Equiv (z.positiveReciprocal b) :=
  positive_congr x z hx hz a b ha hb hax hbz heq

theorem reciprocal_congr (x z : RealCompute) (hx : x.Valid) (hz : z.Valid)
    (hnx : Nonzero x) (hnz : Nonzero z) (heq : x.Equiv z) :
    (reciprocal x hnx).Equiv (reciprocal z hnz) := by
  have hp := pivot_spec x hnx
  have hq := pivot_spec z hnz
  have hxz := RealCompute.le_of_equiv hx hz heq
  have hzx := RealCompute.le_of_equiv hz hx (RealCompute.equiv_symm heq)
  unfold reciprocal
  split <;> split
  · apply positive_congr x z hx hz _ _ ‹_› ‹_›
    · intro n; exact RealCompute.le_refl x hx (pivot x hnx) n
    · intro n; exact RealCompute.le_refl z hz (pivot z hnz) n
    · exact heq
  · have h := hxz (pivot x hnx) (pivot z hnz)
    dsimp [Separated] at hq
    grind
  · have h := hzx (pivot z hnz) (pivot x hnx)
    dsimp [Separated] at hp
    grind
  · apply RealCompute.neg_equiv
    apply positive_congr (-x) (-z) (RealCompute.neg_valid hx) (RealCompute.neg_valid hz)
      _ _ (by dsimp [Separated] at hp; grind) (by dsimp [Separated] at hq; grind)
    · intro n
      have h := RealCompute.le_refl x hx n (pivot x hnx)
      change -(x.compute (pivot x hnx)).hi ≤ -(x.compute n).lo
      grind
    · intro n
      have h := RealCompute.le_refl z hz n (pivot z hnz)
      change -(z.compute (pivot z hnz)).hi ≤ -(z.compute n).lo
      grind
    · exact RealCompute.neg_equiv heq

private def reciprocalBox (P I : QInterval) : QInterval :=
  if 0 < P.lo then ⟨1/I.hi,1/maxRat2 I.lo P.lo⟩
  else ⟨-(1/maxRat2 (-I.hi) (-P.hi)),-(1/(-I.lo))⟩

theorem reciprocal_compute (x : RealCompute) (h : Nonzero x) (n : Nat) :
    (reciprocal x h).compute n = reciprocalBox (x.compute (pivot x h)) (x.compute n) := by
  have hp := pivot_spec x h
  unfold reciprocal reciprocalBox
  split
  · rw [RealCompute.positiveReciprocal_compute x _ ‹_› n]
  · have hlo : 0 < -(x.compute (pivot x h)).hi := by dsimp [Separated] at hp; grind
    change (⟨-(((-x).positiveReciprocal _).compute n).hi,
      -(((-x).positiveReciprocal _).compute n).lo⟩ : QInterval) = _
    rw [RealCompute.positiveReciprocal_compute (-x) _ hlo n]
    rfl

/-- A reciprocal output interval uses a finite prefix of its denominator name. -/
theorem reciprocal_compute_congr (x z : RealCompute) (hx : Nonzero x) (hz : Nonzero z) (n : Nat)
    (h : ∀ j,j ≤ max (pivot x hx) n → x.compute j=z.compute j) :
    (reciprocal x hx).compute n = (reciprocal z hz).compute n := by
  have hp := pivot_congr hx hz (fun j hj => h j (Nat.le_trans hj (Nat.le_max_left _ _)))
  rw [reciprocal_compute x hx n,reciprocal_compute z hz n,← hp,
    h _ (Nat.le_max_left _ _),h _ (Nat.le_max_right _ _)]

theorem mul_reciprocal (x : RealCompute) (hx : x.Valid) (hnz : Nonzero x) :
    (x*reciprocal x hnz).Equiv (RealCompute.ofRat 1) := by
  have hp := pivot_spec x hnz
  have hr := reciprocal_valid x hx hnz
  apply RealCompute.sameStageOverlap_equiv
  intro n
  apply (RealCompute.compareAt_overlap_iff _ _ n n).mpr
  have ho := RealCompute.interval_order_of_valid x hx n
  have hro := RealCompute.interval_order_of_valid _ hr n
  change (QBox.mulRealInterval (x.compute n).lo (x.compute n).hi
    ((reciprocal x hnz).compute n).lo ((reciprocal x hnz).compute n).hi).Overlaps ⟨1,1⟩
  rw [reciprocal_compute] at hro ⊢
  dsimp [reciprocalBox] at hro ⊢
  by_cases hsign : 0 < (x.compute (pivot x hnz)).lo
  · simp only [if_pos hsign] at hro ⊢
    have hbound := RealCompute.le_refl x hx (pivot x hnz) n
    have hn : (x.compute n).hi ≠ 0 := by grind
    have hc := Rat.mul_inv_cancel (x.compute n).hi hn
    have hc' := QBox.mulRealInterval_contains ho Rat.le_refl Rat.le_refl hro
    change (QBox.mulRealInterval (x.compute n).lo (x.compute n).hi
      (1/(x.compute n).hi) (1/maxRat2 (x.compute n).lo (x.compute (pivot x hnz)).lo)).Overlaps
      ⟨1,1⟩
    simpa only [QInterval.Overlaps,Rat.div_def,Rat.one_mul,hc] using hc'
  · simp only [if_neg hsign] at hro ⊢
    have hbound := RealCompute.le_refl x hx n (pivot x hnz)
    have hn : -(x.compute n).lo ≠ 0 := by dsimp [Separated] at hp; grind
    have hc := Rat.mul_inv_cancel (-(x.compute n).lo) hn
    have hc' := QBox.mulRealInterval_contains Rat.le_refl ho hro Rat.le_refl
    change (QBox.mulRealInterval (x.compute n).lo (x.compute n).hi
      (-(1/maxRat2 (-(x.compute n).hi) (-(x.compute (pivot x hnz)).hi)))
      (-(1/(-(x.compute n).lo)))).Overlaps ⟨1,1⟩
    have hprod : (x.compute n).lo * (-(1/(-(x.compute n).lo))) = 1 := by
      dsimp [Rat.div_def]; grind
    simpa only [hprod,QInterval.Overlaps] using hc'

end ComputableAnalysis.CertifiedReciprocal

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