Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Computable analysis · LipschitzRealExtension · fd889115 k1

Definition
liuyao_ca_fd889115_k1_Analysis_LipschitzRealExtension

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

ca-fd889115-k1

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

Definition code
import Definitions.Def_liuyao_ca_fd889115_k1_Analysis_ParametrizedContinuity

set_option autoImplicit true

/-! Derived real evaluation of a rational-input function. Finite-prefix
intersections cover whole input intervals; no real branch/equality test is
used. Periodic rational samplers yield periodic represented-real extensions. -/
namespace ComputableAnalysis.LipschitzRealExtension
open RawLimit BracketDerivative
set_option maxHeartbeats 2000000

def Lipschitz (f : Rat → RealCompute) (L : Rat) : Prop :=
  ∀ u v, (RealCompute.ofRat (-L*qabs (v-u))).Le (f v-f u) ∧
    (f v-f u).Le (RealCompute.ofRat (L*qabs (v-u)))

theorem translated_enclosure {x y : RealCompute} (hx : x.Valid) (hy : y.Valid)
    (D : Rat) (h : (RealCompute.ofRat (-D)).Le (y-x) ∧ (y-x).Le (RealCompute.ofRat D)) (n : Nat) :
    InInterval y {lo:=(x.compute n).lo-D,hi:=(x.compute n).hi+D} := by
  constructor
  · intro i j
    let k := max n j
    have hh := h.1 0 k
    have hn := hx.2.1 n k (Nat.le_max_left _ _)
    have hj := hy.2.1 j k (Nat.le_max_right _ _)
    change -D≤(y.compute k).hi-(x.compute k).lo at hh
    change (x.compute n).lo-D≤(y.compute j).hi
    grind only
  · intro i j
    let k := max n i
    have hh := h.2 k 0
    have hn := hx.2.1 n k (Nat.le_max_left _ _)
    have hi := hy.2.1 i k (Nat.le_max_right _ _)
    change (y.compute k).lo-(x.compute k).hi≤D at hh
    change (y.compute i).lo≤(x.compute n).hi+D
    grind only

def box (f : Rat → RealCompute) (L : Rat) (x : RealCompute) (n : Nat) : QInterval :=
  QInterval.expand ((f (x.compute n).lo).compute n) (L*(x.compute n).width)

def interval (f : Rat → RealCompute) (L : Rat) (x : RealCompute) : Nat → QInterval
  | 0 => box f L x 0
  | n+1 => QInterval.intersection (interval f L x n) (box f L x (n+1))

def extend (f : Rat → RealCompute) (L : Rat) (x : RealCompute) : RealCompute where
  compute := interval f L x

theorem box_covers {f : Rat → RealCompute} {L : Rat} (hf : ∀ q, (f q).Valid)
    (hL : 0≤L) (lip : Lipschitz f L) {x : RealCompute} (n : Nat) {r : Rat}
    (hr : (x.compute n).lo≤r ∧ r≤(x.compute n).hi) : InInterval (f r) (box f L x n) := by
  have h := translated_enclosure (hf (x.compute n).lo) (hf r)
    (L*qabs (r-(x.compute n).lo)) (by simpa only [Rat.neg_mul] using lip (x.compute n).lo r) n
  have hm := Rat.mul_le_mul_of_nonneg_left (show qabs (r-(x.compute n).lo)≤(x.compute n).width by
    rw [qabs_eq_self_of_nonneg (show 0≤r-(x.compute n).lo by grind only)]
    unfold QInterval.width
    grind only) hL
  constructor
  · intro i j
    have hh := h.1 i j
    change ((f (x.compute n).lo).compute n).lo-L*(x.compute n).width≤((f r).compute j).hi
    change ((f (x.compute n).lo).compute n).lo-L*qabs (r-(x.compute n).lo)≤((f r).compute j).hi at hh
    grind only
  · intro i j
    have hh := h.2 i j
    change ((f r).compute i).lo≤((f (x.compute n).lo).compute n).hi+L*(x.compute n).width
    change ((f r).compute i).lo≤((f (x.compute n).lo).compute n).hi+L*qabs (r-(x.compute n).lo) at hh
    grind only

theorem covers {f : Rat → RealCompute} {L : Rat} (hf : ∀ q, (f q).Valid)
    (hL : 0≤L) (lip : Lipschitz f L) {x : RealCompute} (hx : x.Valid) (n : Nat) {r : Rat}
    (hr : (x.compute n).lo≤r ∧ r≤(x.compute n).hi) : InInterval (f r) (interval f L x n) := by
  induction n with
  | zero => exact box_covers hf hL lip 0 hr
  | succ n ih =>
    have nest := hx.2.1 n (n+1) (by omega)
    have hp := ih ⟨Rat.le_trans nest.1 hr.1,Rat.le_trans hr.2 nest.2.2⟩
    have hb := box_covers hf hL lip (n+1) hr
    constructor
    · intro i j
      have h1 := hp.1 i j
      have h2 := hb.1 i j
      change (interval f L x n).lo≤((f r).compute j).hi at h1
      change (box f L x (n+1)).lo≤((f r).compute j).hi at h2
      change max (interval f L x n).lo (box f L x (n+1)).lo≤((f r).compute j).hi
      grind
    · intro i j
      have h1 := hp.2 i j
      have h2 := hb.2 i j
      change ((f r).compute i).lo≤(interval f L x n).hi at h1
      change ((f r).compute i).lo≤(box f L x (n+1)).hi at h2
      change ((f r).compute i).lo≤min (interval f L x n).hi (box f L x (n+1)).hi
      grind

private theorem current_contains (f : Rat → RealCompute) (L : Rat) (x : RealCompute) (n : Nat) :
    (box f L x n).ContainsInterval (interval f L x n) := by
  cases n with
  | zero => exact ⟨Rat.le_refl,Rat.le_refl⟩
  | succ n => exact QInterval.intersection_contained_right _ _

theorem valid {f : Rat → RealCompute} {L : Rat} (hf : ∀ q, (f q).Valid)
    (hL : 0≤L) (lip : Lipschitz f L) (w : Nat → Rat) (hw : ShrinksToZero w)
    (widths : ∀ q n, ((f q).compute n).width≤w n) {x : RealCompute} (hx : x.Valid) :
    (extend f L x).Valid := by
  have ordered (n : Nat) : (interval f L x n).lo≤(interval f L x n).hi := by
    have ho := RealCompute.interval_order_of_valid _ hx n
    have hc := covers hf hL lip hx n ⟨Rat.le_refl,ho⟩
    exact RealCompute.le_trans (x := RealCompute.ofRat (interval f L x n).lo)
      (z := RealCompute.ofRat (interval f L x n).hi) (hf (x.compute n).lo) hc.1 hc.2 0 0
  refine ⟨fun n => by
    change 0≤(interval f L x n).hi-(interval f L x n).lo
    have := ordered n
    grind only,?_,?_⟩
  · intro n m hnm
    change (interval f L x n).lo≤(interval f L x m).lo ∧
      (interval f L x m).lo≤(interval f L x m).hi ∧ (interval f L x m).hi≤(interval f L x n).hi
    induction hnm with
    | refl => exact ⟨Rat.le_refl,ordered n,Rat.le_refl⟩
    | @step m hnm ih =>
      have hs := QInterval.intersection_contained_left (interval f L x m) (box f L x (m+1))
      exact ⟨Rat.le_trans ih.1 hs.1,ordered (m+1),Rat.le_trans hs.2 ih.2.2⟩
  · intro eps
    let small : QPos := ⟨eps.val/(4*(L+1)),by
      rw [Rat.div_def]
      exact Rat.mul_pos eps.property (Rat.inv_pos.mpr (by grind only))⟩
    obtain ⟨N,hN⟩ := hx.2.2 small
    obtain ⟨M,hM⟩ := hw ⟨eps.val/2,by have := eps.property; grind only⟩
    refine ⟨max N M,fun n hn => ?_⟩
    have hi := hN n (by omega)
    have hs := hM n (by omega)
    have hc := current_contains f L x n
    have hfwidth := widths (x.compute n).lo n
    have hm := Rat.mul_le_mul_of_nonneg_left hi (show 0≤2*L by grind only)
    have he : small.val*(4*(L+1))=eps.val := by
      dsimp [small]
      exact Rat.div_mul_cancel (by grind only : 4*(L+1)≠0)
    have hp := small.property
    have hb : 2*L*small.val≤eps.val/2 := by grind only
    have hm' := Rat.le_trans hm hb
    change w n≤eps.val/2 at hs
    unfold QInterval.ContainsInterval box QInterval.expand QInterval.width at hc
    dsimp only at hc
    unfold QInterval.width at hfwidth
    unfold QInterval.width at hm'
    change (interval f L x n).hi-(interval f L x n).lo≤eps.val
    grind only

theorem congr {f : Rat → RealCompute} {L : Rat} (hf : ∀ q, (f q).Valid)
    (hL : 0≤L) (lip : Lipschitz f L) {x y : RealCompute}
    (hx : x.Valid) (hy : y.Valid) (he : x.Equiv y) : (extend f L x).Equiv (extend f L y) := by
  intro n
  have ho := (RealCompute.compareAt_overlap_iff _ _ n n).mp (he n)
  unfold QInterval.Overlaps at ho
  have hxo := RealCompute.interval_order_of_valid _ hx n
  have hyo := RealCompute.interval_order_of_valid _ hy n
  let r := max (x.compute n).lo (y.compute n).lo
  have hrx : (x.compute n).lo≤r ∧ r≤(x.compute n).hi := by dsimp [r]; grind
  have hry : (y.compute n).lo≤r ∧ r≤(y.compute n).hi := by dsimp [r]; grind
  have hc := covers hf hL lip hx n hrx
  have hd := covers hf hL lip hy n hry
  apply (RealCompute.compareAt_overlap_iff _ _ n n).mpr
  exact ⟨RealCompute.le_trans (hf r) hc.1 hd.2 0 0,RealCompute.le_trans (hf r) hd.1 hc.2 0 0⟩

theorem rational_agreement {f : Rat → RealCompute} {L : Rat} (hf : ∀ q, (f q).Valid)
    (hL : 0≤L) (lip : Lipschitz f L) (q : Rat) : (extend f L (RealCompute.ofRat q)).Equiv (f q) := by
  intro n
  exact (RealCompute.compareAt_overlap_iff _ _ n n).mpr
    ⟨(covers hf hL lip (x := RealCompute.ofRat q) (RealCompute.ofRat_valid q) n ⟨Rat.le_refl,Rat.le_refl⟩).1 0 n,
     (covers hf hL lip (x := RealCompute.ofRat q) (RealCompute.ofRat_valid q) n ⟨Rat.le_refl,Rat.le_refl⟩).2 n 0⟩

theorem period_compute (f : Rat → RealCompute) (L T : Rat)
    (period : ∀ q, f (q+T)=f q) (x : RealCompute) (n : Nat) :
    (extend f L (x+RealCompute.ofRat T)).compute n=(extend f L x).compute n := by
  have box_eq (n : Nat) : box f L (x+RealCompute.ofRat T) n=box f L x n := by
    unfold box
    change QInterval.expand ((f ((x.compute n).lo+T)).compute n)
      (L*(((x.compute n).hi+T)-((x.compute n).lo+T)))=_
    rw [period]
    have he : ((x.compute n).hi+T)-((x.compute n).lo+T)=(x.compute n).width := by
      unfold QInterval.width
      grind only
    rw [he]
  change interval f L (x+RealCompute.ofRat T) n=interval f L x n
  induction n with
  | zero => exact box_eq 0
  | succ n ih => simp only [interval,ih,box_eq]

end ComputableAnalysis.LipschitzRealExtension

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