Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Computable analysis · LipschitzQuadrature · fd889115 k1

Definition
liuyao_ca_fd889115_k1_Analysis_LipschitzQuadrature

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

ca-fd889115-k1

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

Definition code
import Definitions.Def_liuyao_ca_fd889115_k1_Analysis_FTCRealProduct
import Definitions.Def_liuyao_ca_fd889115_k1_Analysis_LipschitzIntegralBounds
import Definitions.Def_liuyao_ca_fd889115_k1_Analysis_BoundsQuadrature
import Definitions.Def_liuyao_ca_fd889115_k1_Analysis_IntegralLaws
import Definitions.Def_liuyao_ca_fd889115_k1_Analysis_IntegralValueBounds

set_option autoImplicit true

/-! An executable proper integral for a supplied sampler and justified
Lipschitz evidence. This is one sufficient construction route; it imposes no
integrand class on other integral constructions. -/
namespace ComputableAnalysis.LipschitzQuadrature
open ComputableCoefficient RealApproximationOrder RawLimit Integral
set_option maxHeartbeats 600000

structure Data (f : Rat → Value) (a b : Rat) where
  ordered : a≤b
  constant : Rat
  nonnegative : 0≤constant
  lipschitz : LipschitzIntegralBounds.Lipschitz f a b constant

/-- The executable quadrature certificate on the integer-first dyadic grid. -/
def Data.dyadic {f : Rat → Value} {a b : Rat} (D : Data f a b) :
    BoundsQuadrature.DyadicData (LipschitzIntegralBounds.onInterval f a b) :=
  LipschitzIntegralBounds.dyadicData f a b D.constant D.ordered D.lipschitz D.nonnegative

def Data.tests {f : Rat → Value} {a b : Rat} (D : Data f a b) (n : Nat) :
    Bounds (LipschitzIntegralBounds.onInterval f a b) :=
  D.dyadic.tests n

theorem Data.tests_shrink {f : Rat → Value} {a b : Rat} (D : Data f a b) :
    ShrinksToZero (fun n => (D.tests n).upperSum-(D.tests n).lowerSum) :=
  D.dyadic.shrinks

def Data.integral {f : Rat → Value} {a b : Rat} (D : Data f a b) : RealCompute :=
  if a=b then RealCompute.ofRat 0 else
    D.dyadic.integral

private theorem zero_sums (f : Rat → Value) (a : Rat)
    (B : Bounds (LipschitzIntegralBounds.onInterval f a a)) : B.lowerSum=0 ∧ B.upperSum=0 := by
  have point (k : Nat) (hk : k≤B.partition.pieces) : B.partition.point k=a := by
    have H := B.partition.point_in_bounds hk
    change a≤B.partition.point k ∧ B.partition.point k≤a at H
    grind only
  have zero (w : Nat → Rat) :
      rectangleSum (fun k => (B.partition.point (k+1)-B.partition.point k)*w k) B.partition.pieces=0 := by
    have H : rectangleSum (fun k => (B.partition.point (k+1)-B.partition.point k)*w k) B.partition.pieces=
        rectangleSum (fun _ => 0) B.partition.pieces := by
      apply rectangleSum_congr
      intro k hk
      rw [point k (by omega),point (k+1) (by omega),Rat.sub_self,Rat.zero_mul]
    rw [H,rectangleSum_zero]
  exact ⟨zero B.lower,zero B.upper⟩

theorem Data.hasIntegral {f : Rat → Value} {a b : Rat} (D : Data f a b) :
    HasIntegral (LipschitzIntegralBounds.onInterval f a b) D.integral := by
  by_cases h : a=b
  · subst b
    simp only [Data.integral]
    refine ⟨RealCompute.ofRat_valid 0,?_,LipschitzIntegralBounds.tight f a a D.constant D.ordered D.lipschitz D.nonnegative⟩
    intro B n
    have H := zero_sums f a B
    change B.lowerSum≤0 ∧ 0≤B.upperSum
    rw [H.1,H.2]
    exact ⟨Rat.le_refl,Rat.le_refl⟩
  · simp only [Data.integral,if_neg h]
    exact D.dyadic.hasIntegral

def Data.value {f : Rat → Value} {a b : Rat} (D : Data f a b) : Value :=
  parameter D.integral D.hasIntegral.valid

theorem Data.identify {f : Rat → Value} {a b : Rat} (D : Data f a b) {I : RealCompute}
    (hI : HasIntegral (LipschitzIntegralBounds.onInterval f a b) I) : D.integral.Equiv I :=
  D.hasIntegral.unique hI

def Data.restrict {f : Rat → Value} {a b : Rat} (D : Data f a b)
    (u v : Rat) (hu : a≤u) (huv : u≤v) (hv : v≤b) : Data f u v where
  ordered := huv
  constant := D.constant
  nonnegative := D.nonnegative
  lipschitz x y hx hxy hy := D.lipschitz x y (Rat.le_trans hu hx) hxy (Rat.le_trans hy hv)

def Data.add {f g : Rat → Value} {a b : Rat} (D : Data f a b) (E : Data g a b) :
    Data (fun t => Value.add (f t) (g t)) a b where
  ordered := D.ordered
  constant := D.constant+E.constant
  nonnegative := Rat.add_nonneg D.nonnegative E.nonnegative
  lipschitz := by
    intro u v hu huv hv
    have H := (D.lipschitz u v hu huv hv).add (E.lipschitz u v hu huv hv)
    have he : D.constant*(v-u)+E.constant*(v-u)=(D.constant+E.constant)*(v-u) := by grind only
    rw [he] at H
    apply H.congr
    apply arithmetic_identity; intro s; simp only [Value.add,sub]; grind only

def Data.scale {f : Rat → Value} {a b : Rat} (D : Data f a b) (c : Rat) :
    Data (fun t => RealApproximationOrder.scale c (f t)) a b where
  ordered := D.ordered
  constant := qabs c*D.constant
  nonnegative := Rat.mul_nonneg (qabs_nonneg c) D.nonnegative
  lipschitz := by
    intro u v hu huv hv
    have H := FTCRealCalculus.scale_small (D.lipschitz u v hu huv hv) c
    have he : qabs c*(D.constant*(v-u))=(qabs c*D.constant)*(v-u) := by grind only
    rw [he] at H
    apply H.congr
    apply arithmetic_identity; intro s; simp only [RealApproximationOrder.scale,sub]; grind only

def Data.neg {f : Rat → Value} {a b : Rat} (D : Data f a b) : Data (fun t => Value.neg (f t)) a b where
  ordered := D.ordered
  constant := D.constant
  nonnegative := D.nonnegative
  lipschitz := by
    intro u v hu huv hv
    apply (D.lipschitz u v hu huv hv).neg.congr
    apply arithmetic_identity; intro s; simp only [Value.neg,sub]; grind only

def Data.subtract {f g : Rat → Value} {a b : Rat} (D : Data f a b) (E : Data g a b) :
    Data (fun t => sub (f t) (g t)) a b where
  ordered := D.ordered
  constant := D.constant+E.constant
  nonnegative := Rat.add_nonneg D.nonnegative E.nonnegative
  lipschitz := by
    intro u v hu huv hv
    have H := (D.lipschitz u v hu huv hv).add (E.lipschitz u v hu huv hv).neg
    have he : D.constant*(v-u)+E.constant*(v-u)=(D.constant+E.constant)*(v-u) := by grind only
    rw [he] at H
    apply H.congr
    apply arithmetic_identity; intro s; simp only [Value.add,Value.neg,sub]; grind only

theorem Data.small {f : Rat → Value} {a b : Rat} (D : Data f a b) (B : Rat)
    (hB : ∀ t,a≤t → t≤b → Small (f t) B) : Small D.value ((b-a)*B) := by
  have hl := D.hasIntegral.lower_bound (-B) (fun t ht n => (hB t ht.1 ht.2).1 0 n)
  have hu := D.hasIntegral.upper_bound B (fun t ht n => (hB t ht.1 ht.2).2 n 0)
  constructor
  · intro i j
    have h := hl 0 j
    change (b-a)*(-B)≤(D.integral.compute j).hi at h
    change -((b-a)*B)≤(D.integral.compute j).hi
    grind only
  · exact hu

/-- The algorithmic choices disappear from the public integral law. -/
theorem Data.add_identity {f g : Rat → Value} {a b : Rat} (D : Data f a b) (E : Data g a b) :
    (D.add E).integral.Equiv (D.integral+E.integral) :=
  D.hasIntegral.add_identity E.hasIntegral (D.add E).hasIntegral rfl rfl rfl rfl
    (by intro t _ _ _; exact RealCompute.equiv_refl _ (Value.add (f t) (g t)).real.valid)

def Data.mul {f g : Rat → Value} {a b : Rat} (D : Data f a b) (E : Data g a b)
    (B C : Rat) (hB : 0≤B) (hC : 0≤C)
    (bf : ∀ t,a≤t → t≤b → Small (f t) B)
    (bg : ∀ t,a≤t → t≤b → Small (g t) C) : Data (fun t => Value.mul (f t) (g t)) a b where
  ordered := D.ordered
  constant := D.constant*C+B*E.constant
  nonnegative := Rat.add_nonneg (Rat.mul_nonneg D.nonnegative hC) (Rat.mul_nonneg hB E.nonnegative)
  lipschitz := FTCRealCalculus.product_lipschitz f g a b D.constant E.constant B C D.lipschitz E.lipschitz bf bg

theorem Data.congr {f g : Rat → Value} {a b : Rat} (D : Data f a b) (E : Data g a b)
    (he : ∀ t,a≤t → t≤b → (f t).real.preferred.Equiv (g t).real.preferred) : D.integral.Equiv E.integral :=
  (D.hasIntegral.congrFunction (G := LipschitzIntegralBounds.onInterval g a b) ⟨rfl,rfl,fun t ht _ => he t ht.1 ht.2⟩).unique E.hasIntegral

theorem Data.scale_identity {f : Rat → Value} {a b : Rat} (D : Data f a b) (c : Rat) :
    (D.scale c).integral.Equiv (RealCompute.scaleRat c D.integral) :=
  D.hasIntegral.scaleRat_identity (D.scale c).hasIntegral c ⟨rfl,rfl,by
    intro t _ _
    exact RealCompute.equiv_refl _ (RealApproximationOrder.scale c (f t)).real.valid⟩

theorem Data.neg_identity {f : Rat → Value} {a b : Rat} (D : Data f a b) :
    D.neg.integral.Equiv (-D.integral) := by
  have H := (D.scale (-1)).congr D.neg (by
    intro t _ _
    apply arithmetic_identity; intro s; simp only [RealApproximationOrder.scale,Value.neg]; grind only)
  have S := D.scale_identity (-1)
  have C : (RealCompute.scaleRat (-1) D.integral).Equiv (-D.integral) := by
    apply arithmetic_identity (RealApproximationOrder.scale (-1) D.value) (Value.neg D.value)
    intro s; simp only [RealApproximationOrder.scale,Value.neg]; grind only
  exact RealCompute.equiv_trans D.neg.hasIntegral.valid (D.scale (-1)).hasIntegral.valid
    (RealCompute.neg_valid D.hasIntegral.valid) (RealCompute.equiv_symm H)
    (RealCompute.equiv_trans (D.scale (-1)).hasIntegral.valid (RealCompute.scaleRat_valid D.hasIntegral.valid)
      (RealCompute.neg_valid D.hasIntegral.valid) S C)

theorem Data.subtract_identity {f g : Rat → Value} {a b : Rat} (D : Data f a b) (E : Data g a b) :
    (D.subtract E).integral.Equiv (D.integral-E.integral) := by
  have H := (D.add E.neg).congr (D.subtract E) (by
    intro t _ _
    apply arithmetic_identity; intro s; simp only [Value.add,Value.neg,sub]; grind only)
  have S := (D.add_identity E.neg)
  have A := RealCompute.add_equiv D.hasIntegral.valid D.hasIntegral.valid E.neg.hasIntegral.valid
    (RealCompute.neg_valid E.hasIntegral.valid) (RealCompute.equiv_refl _ D.hasIntegral.valid) E.neg_identity
  have C : (D.integral+(-E.integral)).Equiv (D.integral-E.integral) := by
    apply arithmetic_identity (Value.add D.value (Value.neg E.value)) (sub D.value E.value)
    intro s; simp only [Value.add,Value.neg,sub]; grind only
  exact RealCompute.equiv_trans (D.subtract E).hasIntegral.valid (D.add E.neg).hasIntegral.valid
    (RealCompute.sub_valid D.hasIntegral.valid E.hasIntegral.valid) (RealCompute.equiv_symm H)
    (RealCompute.equiv_trans (D.add E.neg).hasIntegral.valid (RealCompute.add_valid D.hasIntegral.valid E.neg.hasIntegral.valid)
      (RealCompute.sub_valid D.hasIntegral.valid E.hasIntegral.valid) S
      (RealCompute.equiv_trans (RealCompute.add_valid D.hasIntegral.valid E.neg.hasIntegral.valid)
        (RealCompute.add_valid D.hasIntegral.valid (RealCompute.neg_valid E.hasIntegral.valid))
        (RealCompute.sub_valid D.hasIntegral.valid E.hasIntegral.valid) A C))

theorem Data.difference_small {f g : Rat → Value} {a b : Rat} (D : Data f a b) (E : Data g a b)
    (B : Rat) (hb : ∀ t,a≤t → t≤b → Small (sub (f t) (g t)) B) :
    Small (sub D.value E.value) ((b-a)*B) :=
  ((D.subtract E).small B hb).congr (D.subtract_identity E)

/-- Interval additivity for independently computed compact quadratures. -/
theorem Data.append {f : Rat → Value} {a b c : Rat}
    (D : Data f a b) (E : Data f b c) (F : Data f a c) :
    F.integral.Equiv (D.integral+E.integral) := by
  let G := LipschitzIntegralBounds.onInterval f a c
  have hD : HasIntegral (G.restrict a b Rat.le_refl D.ordered E.ordered) D.integral :=
    D.hasIntegral.congrFunction (G := G.restrict a b Rat.le_refl D.ordered E.ordered)
      ⟨rfl,rfl,by intro t _ _ n; exact (RealCompute.equiv_refl (f t).real.preferred (f t).real.valid) n⟩
  have hE : HasIntegral (G.restrict b c D.ordered E.ordered Rat.le_refl) E.integral :=
    E.hasIntegral.congrFunction (G := G.restrict b c D.ordered E.ordered Rat.le_refl)
      ⟨rfl,rfl,by intro t _ _ n; exact (RealCompute.equiv_refl (f t).real.preferred (f t).real.valid) n⟩
  exact HasIntegral.append_identity (F := G) b D.ordered E.ordered hD hE F.hasIntegral

/-- Positive affine substitution for independently computed integrals.
The argument transports the source rectangle tests with their exact lengths. -/
theorem Data.affine_identity {f g : Rat → Value} {a b u v c s : Rat}
    (F : Data f a b) (G : Data g u v) (hs : 0 < s)
    (hu : u = c + s * a) (hv : v = c + s * b)
    (h : ∀ t, a ≤ t → t ≤ b → (f t).real.preferred.Equiv (g (c + s * t)).real.preferred) :
    G.integral.Equiv (RealCompute.scaleRat s F.integral) := by
  let transport (B : Bounds (LipschitzIntegralBounds.onInterval f a b)) :
      Bounds (LipschitzIntegralBounds.onInterval g u v) := by
    let P := B.partition
    let Q : RationalPartition u v :=
      { pieces := P.pieces
        positive := P.positive
        point := fun k => c + s * P.point k
        left_endpoint := by rw [P.left_endpoint]; exact hu.symm
        right_endpoint := by rw [P.right_endpoint]; exact hv.symm
        monotone := by
          intro i j hij hj
          have hmul := Rat.mul_le_mul_of_nonneg_left (P.monotone i j hij hj) (Rat.le_of_lt hs)
          grind only }
    have hinv := Rat.mul_inv_cancel s (Rat.ne_of_gt hs)
    have invpos := Rat.le_of_lt (Rat.inv_pos.mpr hs)
    have preimage (k : Nat) (hk : k < P.pieces) (x : Rat)
        (hx : (Q.cell k hk).contains x) : (P.cell k hk).contains ((x - c) / s) := by
      change c + s * P.point k ≤ x ∧ x ≤ c + s * P.point (k+1) at hx
      have hl := Rat.mul_le_mul_of_nonneg_right hx.1 invpos
      have hr := Rat.mul_le_mul_of_nonneg_right hx.2 invpos
      have he (t : Rat) : (c + s * t) * s⁻¹ = c * s⁻¹ + t := by grind only
      rw [he] at hl hr
      change P.point k ≤ (x-c)/s ∧ (x-c)/s ≤ P.point (k+1)
      constructor <;> grind only [Rat.div_def]
    have eqAt (k : Nat) (hk : k < P.pieces) (x : Rat)
        (hx : (P.cell k hk).contains ((x - c) / s)) :
        (f ((x - c) / s)).real.preferred.Equiv (g x).real.preferred := by
      have hh := (P.cell k hk).contains_inDomain hx
      have he : c + s * ((x - c) / s) = x := by grind only [Rat.div_def]
      simpa only [he] using h ((x - c) / s) hh.1 hh.2
    exact
      { partition := Q
        lower := B.lower
        upper := B.upper
        lower_le := by
          intro k hk x hx n
          have ht := preimage k hk x hx
          have he := RealCompute.le_of_equiv (f ((x-c)/s)).real.valid (g x).real.valid (eqAt k hk x ht)
          have hb : (RealCompute.ofRat (B.lower k)).Le (f ((x-c)/s)).real.preferred :=
            fun _ j => B.lower_le k hk _ ht j
          exact RealCompute.le_trans (f ((x-c)/s)).real.valid hb he 0 n
        upper_ge := by
          intro k hk x hx n
          have ht := preimage k hk x hx
          have he := RealCompute.le_of_equiv (g x).real.valid (f ((x-c)/s)).real.valid
            (RealCompute.equiv_symm (eqAt k hk x ht))
          have hb : (f ((x-c)/s)).real.preferred.Le (RealCompute.ofRat (B.upper k)) :=
            fun j _ => B.upper_ge k hk _ ht j
          exact RealCompute.le_trans (f ((x-c)/s)).real.valid he hb n 0 }
  have sums (B : Bounds (LipschitzIntegralBounds.onInterval f a b)) :
      (transport B).lowerSum = s * B.lowerSum ∧ (transport B).upperSum = s * B.upperSum := by
    have sum (w : Nat → Rat) :
        rectangleSum (fun k => ((c + s * B.partition.point (k+1)) -
          (c + s * B.partition.point k)) * w k) B.partition.pieces =
        s * rectangleSum (fun k => (B.partition.point (k+1) - B.partition.point k) * w k)
          B.partition.pieces := by
      rw [Rat.mul_comm, ← rectangleSum_scale]
      apply rectangleSum_congr
      intro k _
      grind only
    exact ⟨sum B.lower, sum B.upper⟩
  let J := RealCompute.scaleRat s F.integral
  have encloses (B : Bounds (LipschitzIntegralBounds.onInterval f a b)) (n : Nat) :
      (transport B).lowerSum ≤ (J.compute n).hi ∧ (J.compute n).lo ≤ (transport B).upperSum := by
    obtain ⟨hl, hr⟩ := F.hasIntegral.bounds B n
    rw [(sums B).1, (sums B).2]
    change _ ≤ (RealCompute.scaleRatCompute s F.integral n).hi ∧
      (RealCompute.scaleRatCompute s F.integral n).lo ≤ _
    simp only [RealCompute.scaleRatCompute, if_pos (Rat.le_of_lt hs)]
    exact ⟨Rat.mul_le_mul_of_nonneg_left hl (Rat.le_of_lt hs),
      Rat.mul_le_mul_of_nonneg_left hr (Rat.le_of_lt hs)⟩
  apply equiv_of_bounds G.hasIntegral.tight G.hasIntegral.bounds
  intro A n
  have cross (B : Bounds (LipschitzIntegralBounds.onInterval f a b)) :
      A.lowerSum ≤ (J.compute n).hi + ((transport B).upperSum - (transport B).lowerSum) ∧
      (J.compute n).lo ≤ A.upperSum + ((transport B).upperSum - (transport B).lowerSum) := by
    have hl := Bounds.lowerSum_le_upperSum A (transport B)
    have hr := Bounds.lowerSum_le_upperSum (transport B) A
    obtain ⟨hJ₁, hJ₂⟩ := encloses B n
    constructor <;> grind only
  have arbitrarily (eps : QPos) : ∃ B : Bounds (LipschitzIntegralBounds.onInterval f a b),
      (transport B).upperSum - (transport B).lowerSum ≤ eps.val := by
    have hp : 0 < eps.val / s := Rat.mul_pos eps.property (Rat.inv_pos.mpr hs)
    obtain ⟨B, hB⟩ := F.hasIntegral.tight ⟨_, hp⟩
    have hh := Rat.mul_le_mul_of_nonneg_right hB (Rat.le_of_lt hs)
    change (B.upperSum - B.lowerSum) * s ≤ (eps.val / s) * s at hh
    rw [Rat.div_mul_cancel (Rat.ne_of_gt hs)] at hh
    exact ⟨B, by rw [(sums B).1, (sums B).2]; grind only⟩
  constructor
  · by_cases hn : A.lowerSum ≤ (J.compute n).hi
    · exact hn
    exfalso
    obtain ⟨B, hb⟩ := arbitrarily ⟨(A.lowerSum - (J.compute n).hi) / 2, by grind only⟩
    have := (cross B).1
    change _ ≤ (A.lowerSum - (J.compute n).hi) / 2 at hb
    grind only
  · by_cases hn : (J.compute n).lo ≤ A.upperSum
    · exact hn
    exfalso
    obtain ⟨B, hb⟩ := arbitrarily ⟨((J.compute n).lo - A.upperSum) / 2, by grind only⟩
    have := (cross B).2
    change _ ≤ ((J.compute n).lo - A.upperSum) / 2 at hb
    grind only

/-- Integrate the derivative along the straight segment from zero to `x`.
This computes the divided difference even when the segment has length zero. -/
private def Data.segmentData {d : Rat → Value} {a b : Rat} (D : Data d a b)
    (x : Rat) (hx : a ≤ x ∧ x ≤ b) (h0 : a ≤ 0 ∧ 0 ≤ b) : Data (fun t => d (x * t)) 0 1 where
  ordered := by decide
  constant := D.constant * qabs x
  nonnegative := Rat.mul_nonneg D.nonnegative (qabs_nonneg x)
  lipschitz := by
    intro u v hu huv hv
    have inside (t : Rat) (ht : 0 ≤ t) (ht' : t ≤ 1) : a ≤ x * t ∧ x * t ≤ b := by
      by_cases h : 0 ≤ x
      · have h₁ := Rat.mul_nonneg h ht
        have h₂ := Rat.mul_le_mul_of_nonneg_left ht' h
        constructor <;> grind only
      · have h₁ := Rat.mul_nonneg (show 0 ≤ -x by grind only) ht
        have h₂ := Rat.mul_le_mul_of_nonneg_left ht' (show 0 ≤ -x by grind only)
        constructor <;> grind only
    have iu := inside u hu (by grind only)
    have iv := inside v (by grind only) hv
    by_cases h : 0 ≤ x
    · have h' := Rat.mul_le_mul_of_nonneg_left huv h
      have H := D.lipschitz _ _ iu.1 h' iv.2
      simpa only [qabs_eq_self_of_nonneg h, show x * v - x * u = x * (v - u) by grind only,
        Rat.mul_assoc] using H
    · have hx' : x ≤ 0 := by grind only
      have h' := Rat.mul_le_mul_of_nonneg_left huv (show 0 ≤ -x by grind only)
      have H := (D.lipschitz _ _ iv.1 (show x * v ≤ x * u by grind only) iu.2).neg
      rw [show D.constant * (x * u - x * v) = D.constant * qabs x * (v-u) by
        rw [qabs_eq_neg_of_nonpos hx']; grind only] at H
      exact H.congr (arithmetic_identity _ _ (by
        intro s
        simp only [Value.neg, sub]
        grind only))

/-- The normalized average of the derivative from zero to `x`.
For negative `x` the parameter traverses the segment in increasing order. -/
def Data.ftcQuotient {d : Rat → Value} {a b : Rat} (D : Data d a b)
    (x : Rat) (hx : a ≤ x ∧ x ≤ b) (h0 : a ≤ 0 ∧ 0 ≤ b) :
    Data (fun t => d (if 0 ≤ x then x * t else x * (1 - t))) 0 1 where
  ordered := by decide
  constant := D.constant * qabs x
  nonnegative := Rat.mul_nonneg D.nonnegative (qabs_nonneg x)
  lipschitz := by
    intro u v hu huv hv
    let E := D.segmentData x hx h0
    by_cases hp : 0 ≤ x
    · have H := E.lipschitz u v hu huv hv
      change Small (sub (d (x * v)) (d (x * u))) (D.constant * qabs x * (v-u)) at H
      simpa only [if_pos hp] using H
    · have H := (E.lipschitz (1-v) (1-u) (by grind only) (by grind only) (by grind only)).neg
      rw [show (1-u)-(1-v)=v-u by grind only] at H
      simp only [if_neg hp]
      exact H.congr (arithmetic_identity _ _ (by
        intro s
        simp only [Value.neg, sub]
        grind only))

theorem Data.ftcQuotient_zero {d : Rat → Value} {a b : Rat} (D : Data d a b)
    (h0 : a ≤ 0 ∧ 0 ≤ b) :
    (D.ftcQuotient 0 h0 h0).integral.Equiv (d 0).real.preferred := by
  let Q := D.ftcQuotient 0 h0 h0
  have h := Integral.constant_hasIntegral (d 0).real.preferred (d 0).real.valid 0 1 Q.ordered
  have hh := Q.identify (h.congrFunction
    (G := LipschitzIntegralBounds.onInterval (fun t => d (if 0 ≤ (0 : Rat) then 0*t else 0*(1-t))) 0 1)
    ⟨rfl, rfl, fun t _ _ => by
      change (d 0).real.preferred.Equiv (d (if 0 ≤ (0 : Rat) then 0*t else 0*(1-t))).real.preferred
      rw [if_pos (Rat.le_refl : (0 : Rat) ≤ 0), Rat.zero_mul]
      exact RealCompute.equiv_refl _ (d 0).real.valid⟩)
  have he : (RealApproximationOrder.scale ((1 : Rat) - 0) (d 0)).real.preferred.Equiv (d 0).real.preferred := by
    apply arithmetic_identity
    intro s
    simp only [RealApproximationOrder.scale]
    grind only
  exact RealCompute.equiv_trans Q.hasIntegral.valid h.valid (d 0).real.valid hh he

/-- The FTC identifies the integral quotient with the increment after
multiplication by `x`, for positive, negative and zero arguments. -/
theorem Data.ftcQuotient_identity {f d : Rat → Value} {a b : Rat}
    (D : Data d a b) (S : FTCRealCalculus.Step f d a b) (x : Rat)
    (hx : a ≤ x ∧ x ≤ b) (h0 : a ≤ 0 ∧ 0 ≤ b) :
    (RealApproximationOrder.scale x (D.ftcQuotient x hx h0).value).real.preferred.Equiv (sub (f x) (f 0)).real.preferred := by
  let Q := D.ftcQuotient x hx h0
  by_cases hp : 0 < x
  · let F := D.restrict 0 x h0.1 (Rat.le_of_lt hp) hx.2
    have h := Q.affine_identity F (c := 0) hp (by grind only) (by grind only) (fun t _ _ => by
      rw [Rat.zero_add, if_pos (Rat.le_of_lt hp)]
      exact RealCompute.equiv_refl _ (d (x*t)).real.valid)
    exact RealCompute.equiv_trans (RealApproximationOrder.scale x Q.value).real.valid F.hasIntegral.valid
      (sub (f x) (f 0)).real.valid (RealCompute.equiv_symm h)
      ((S.restrict 0 x h0.1 hx.2).ftc F.hasIntegral)
  · by_cases hn : x < 0
    · let F := D.restrict x 0 hx.1 (Rat.le_of_lt hn) h0.2
      have h := Q.affine_identity F (c := x) (s := -x) (by grind only)
        (by grind only) (by grind only) (fun t _ _ => by
          simp only [if_neg (show ¬ 0 ≤ x by grind only),
            show x * (1-t) = x + -x*t by grind only]
          exact RealCompute.equiv_refl _ (d (x + -x*t)).real.valid)
      have h' := (S.restrict x 0 hx.1 h0.2).ftc F.hasIntegral
      have he : (RealApproximationOrder.scale (-x) Q.value).real.preferred.Equiv (sub (f 0) (f x)).real.preferred :=
        RealCompute.equiv_trans (RealApproximationOrder.scale (-x) Q.value).real.valid F.hasIntegral.valid
          (sub (f 0) (f x)).real.valid (RealCompute.equiv_symm h) h'
      have hneg := RealCompute.neg_equiv he
      have hl : (RealApproximationOrder.scale x Q.value).real.preferred.Equiv (Value.neg (RealApproximationOrder.scale (-x) Q.value)).real.preferred := by
        apply arithmetic_identity
        intro s
        simp only [RealApproximationOrder.scale, Value.neg]
        grind only
      have hr : (Value.neg (sub (f 0) (f x))).real.preferred.Equiv (sub (f x) (f 0)).real.preferred := by
        apply arithmetic_identity
        intro s
        simp only [sub, Value.neg]
        grind only
      exact RealCompute.equiv_trans (RealApproximationOrder.scale x Q.value).real.valid (Value.neg (RealApproximationOrder.scale (-x) Q.value)).real.valid
        (sub (f x) (f 0)).real.valid hl
        (RealCompute.equiv_trans (Value.neg (RealApproximationOrder.scale (-x) Q.value)).real.valid
          (Value.neg (sub (f 0) (f x))).real.valid (sub (f x) (f 0)).real.valid hneg hr)
    · have he : x = 0 := by grind only
      subst x
      apply arithmetic_identity
      intro s
      simp only [RealApproximationOrder.scale, sub, Rat.zero_mul, Rat.sub_self]

/-- The quotient approaches the supplied derivative at zero with an
explicit error, on either side of zero. -/
theorem Data.ftcQuotient_error {d : Rat → Value} {a b : Rat} (D : Data d a b)
    (x : Rat) (hx : a ≤ x ∧ x ≤ b) (h0 : a ≤ 0 ∧ 0 ≤ b) :
    Small (sub (D.ftcQuotient x hx h0).value (d 0)) (D.constant * qabs x) := by
  let Q := D.ftcQuotient x hx h0
  have H (t : Rat) (ht : 0 ≤ t) (ht' : t ≤ 1) :
      Small (sub (d (if 0 ≤ x then x*t else x*(1-t))) (d 0)) (D.constant * qabs x) := by
    by_cases hp : 0 ≤ x
    · rw [if_pos hp, qabs_eq_self_of_nonneg hp]
      have hl := Rat.mul_nonneg hp ht
      have hr := Rat.mul_le_mul_of_nonneg_left ht' hp
      have hd := D.lipschitz 0 (x*t) h0.1 hl (by grind only)
      apply hd.mono
      exact Rat.mul_le_mul_of_nonneg_left (by grind only) D.nonnegative
    · have hn : x ≤ 0 := by grind only
      have hl := Rat.mul_nonneg (show 0 ≤ -x by grind only) (show 0 ≤ 1-t by grind only)
      have hr := Rat.mul_le_mul_of_nonneg_left (show 1-t ≤ 1 by grind only) (show 0 ≤ -x by grind only)
      rw [if_neg hp, qabs_eq_neg_of_nonpos hn]
      have hd := (D.lipschitz (x*(1-t)) 0 (by grind only) (by grind only) h0.2).neg
      apply (hd.mono (Rat.mul_le_mul_of_nonneg_left (show 0-x*(1-t) ≤ -x by grind only)
        D.nonnegative)).congr
      apply arithmetic_identity
      intro s
      simp only [sub, Value.neg]
      grind only
  have he := D.ftcQuotient_zero h0
  have hh := Q.difference_small (D.ftcQuotient 0 h0 h0) (D.constant * qabs x) (by
    intro t ht hu
    change Small (sub (d (if 0 ≤ x then x*t else x*(1-t)))
      (d (if 0 ≤ (0 : Rat) then 0*t else 0*(1-t)))) _
    rw [if_pos (Rat.le_refl : (0 : Rat) ≤ 0), Rat.zero_mul]
    exact H t ht hu)
  have h := hh.congr (y := sub Q.value (d 0))
    (RealCompute.sub_equiv Q.hasIntegral.valid Q.hasIntegral.valid
    (D.ftcQuotient 0 h0 h0).hasIntegral.valid (d 0).real.valid
    (RealCompute.equiv_refl _ Q.hasIntegral.valid) he)
  rwa [show (1 : Rat) - 0 = 1 by grind only, Rat.one_mul] at h

/-- Melrose's division step for a normalized profile. The input profile
can be the Gaussian once its finite FTC evidence is supplied. -/
theorem Data.ftcQuotient_decomposition {f g d : Rat → Value} {a b : Rat}
    (D : Data d a b)
    (S : FTCRealCalculus.Step (fun t => sub (f t) (Value.mul (f 0) (g t))) d a b)
    (x : Rat) (hx : a ≤ x ∧ x ≤ b) (h0 : a ≤ 0 ∧ 0 ≤ b)
    (hg : (g 0).real.preferred.Equiv (RealCompute.ofRat 1)) :
    (Value.add (Value.mul (f 0) (g x))
      (RealApproximationOrder.scale x (D.ftcQuotient x hx h0).value)).real.preferred.Equiv
      (f x).real.preferred := by
  let w := fun t => sub (f t) (Value.mul (f 0) (g t))
  let Q := RealApproximationOrder.scale x (D.ftcQuotient x hx h0).value
  let G := Value.mul (f 0) (g x)
  have hzero : (w 0).real.preferred.Equiv (RealCompute.ofRat 0) := by
    have hp := RealCompute.mul_equiv (y' := RealCompute.ofRat 1) (f 0).real.valid (f 0).real.valid (g 0).real.valid
      (RealCompute.ofRat_valid 1) (RealCompute.equiv_refl _ (f 0).real.valid) hg
    have he : (Value.mul (f 0) (Value.rational 1)).real.preferred.Equiv (f 0).real.preferred :=
      arithmetic_identity _ _ (by intro s; simp only [Value.mul, Value.rational, Rat.mul_one])
    have hp' := RealCompute.equiv_trans (Value.mul (f 0) (g 0)).real.valid
      (Value.mul (f 0) (Value.rational 1)).real.valid (f 0).real.valid hp he
    exact RealCompute.equiv_trans (w 0).real.valid (sub (f 0) (f 0)).real.valid (RealCompute.ofRat_valid 0)
      (RealCompute.sub_equiv (f 0).real.valid (f 0).real.valid (Value.mul (f 0) (g 0)).real.valid
        (f 0).real.valid (RealCompute.equiv_refl _ (f 0).real.valid) hp')
      (RealCompute.sub_self_equiv_zero (f 0).real.valid)
  have h := D.ftcQuotient_identity S x hx h0
  have hs := RealCompute.sub_equiv (y' := RealCompute.ofRat 0) (w x).real.valid (w x).real.valid (w 0).real.valid
    (RealCompute.ofRat_valid 0) (RealCompute.equiv_refl _ (w x).real.valid) hzero
  have hr : (Value.add G (sub (w x) (Value.rational 0))).real.preferred.Equiv (f x).real.preferred := by
    apply arithmetic_identity
    intro s
    simp only [w, G, Value.add, Value.rational, sub]
    grind only
  refine RealCompute.equiv_trans (Value.add G Q).real.valid
    (Value.add G (sub (w x) (Value.rational 0))).real.valid (f x).real.valid ?_ hr
  apply RealCompute.add_equiv G.real.valid G.real.valid Q.real.valid
    (sub (w x) (Value.rational 0)).real.valid (RealCompute.equiv_refl _ G.real.valid)
  exact RealCompute.equiv_trans Q.real.valid (sub (w x) (w 0)).real.valid
    (sub (w x) (Value.rational 0)).real.valid h hs


/-- Division gains one power of decay away from zero. The quotient itself
continues to be computed by the normalized derivative integral. -/
theorem Data.ftcQuotient_decay {w d : Rat → Value} {a b : Rat}
    (D : Data d a b) (S : FTCRealCalculus.Step w d a b)
    (x : Rat) (hx : a ≤ x ∧ x ≤ b) (h0 : a ≤ 0 ∧ 0 ≤ b)
    (hz : (w 0).real.preferred.Equiv (RealCompute.ofRat 0)) (hne : x ≠ 0)
    (B : Rat) (hw : Small (w x) B) :
    Small (D.ftcQuotient x hx h0).value (B / qabs x) := by
  let Q := (D.ftcQuotient x hx h0).value
  have he := D.ftcQuotient_identity S x hx h0
  have hs : (sub (w x) (w 0)).real.preferred.Equiv (w x).real.preferred := by
    have h := RealCompute.sub_equiv (y' := RealCompute.ofRat 0) (w x).real.valid (w x).real.valid
      (w 0).real.valid (RealCompute.ofRat_valid 0) (RealCompute.equiv_refl _ (w x).real.valid) hz
    exact RealCompute.equiv_trans (sub (w x) (w 0)).real.valid
      (sub (w x) (Value.rational 0)).real.valid (w x).real.valid h
      (arithmetic_identity _ _ (by intro s; simp only [sub, Value.rational]; grind only))
  have h := hw.congr (y := RealApproximationOrder.scale x Q)
    (RealCompute.equiv_symm (RealCompute.equiv_trans (RealApproximationOrder.scale x Q).real.valid
      (sub (w x) (w 0)).real.valid (w x).real.valid he hs))
  have hi : qabs x⁻¹ = (qabs x)⁻¹ := by
    have hm := Rat.inv_mul_cancel x hne
    have hq := congrArg qabs hm
    rw [qabs_mul, show qabs (1 : Rat) = 1 by decide +kernel] at hq
    have hne' : qabs x ≠ 0 := by
      intro hh
      rw [hh, Rat.mul_zero] at hq
      exact (by decide : (0 : Rat) ≠ 1) hq
    calc
      _ = qabs x⁻¹ * (qabs x * (qabs x)⁻¹) := by rw [Rat.mul_inv_cancel _ hne', Rat.mul_one]
      _ = _ := by rw [← Rat.mul_assoc, hq, Rat.one_mul]
  have H := FTCRealCalculus.scale_small h x⁻¹
  rw [hi, show (qabs x)⁻¹ * B = B / qabs x by grind only [Rat.div_def]] at H
  exact H.congr (arithmetic_identity _ Q (by
    intro s
    simp only [RealApproximationOrder.scale]
    rw [← Rat.mul_assoc, Rat.inv_mul_cancel x hne, Rat.one_mul]))


/-- A power of the unit-interval coordinate, used in the derivatives of the
FTC quotient. The Lipschitz constant is the exponent. -/
def unitPowerData (j : Nat) : Data (fun t => Value.rational (t^j)) 0 1 where
  ordered := by decide
  constant := j
  nonnegative := Rat.natCast_nonneg
  lipschitz := by
    have power (u v : Rat) (hu : 0 ≤ u) (huv : u ≤ v) (hv : v ≤ 1) :
        ∀ n : Nat, 0 ≤ v^n-u^n ∧ v^n-u^n ≤ (n : Rat)*(v-u) := by
      have hu₁ : u ≤ 1 := Rat.le_trans huv hv
      have hv₀ : 0 ≤ v := Rat.le_trans hu huv
      have unit (n : Nat) : u^n ≤ 1 := by
        induction n with
        | zero => rw [Rat.pow_zero]; exact Rat.le_refl
        | succ n ih =>
          rw [Rat.pow_succ]
          exact Rat.le_trans (Rat.mul_le_mul_of_nonneg_right ih hu) (by simpa only [Rat.one_mul] using hu₁)
      intro n
      induction n with
      | zero => simp only [Rat.pow_zero]; grind only
      | succ n ih =>
        have h₁ := Rat.mul_le_mul_of_nonneg_right ih.2 hv₀
        have h₂ := Rat.mul_le_mul_of_nonneg_left hv
          (Rat.mul_nonneg (show (0 : Rat) ≤ (n : Rat) from Rat.natCast_nonneg) (show 0 ≤ v-u by grind only))
        have h₃ := Rat.mul_le_mul_of_nonneg_right (unit n) (show 0 ≤ v-u by grind only)
        have h₄ := Rat.mul_nonneg ih.1 hv₀
        have h₅ := Rat.mul_nonneg (Rat.pow_nonneg hu : 0 ≤ u^n) (show 0 ≤ v-u by grind only)
        rw [Rat.pow_succ, Rat.pow_succ, Rat.natCast_add]
        have he : v^n*v-u^n*u = (v^n-u^n)*v + u^n*(v-u) := by grind only
        rw [he]
        constructor <;> grind only
    intro u v hu huv hv
    have h := power u v hu huv hv j
    apply ((FTCRealCalculus.rational_small (v^j-u^j)).mono
      (by rw [qabs_eq_self_of_nonneg h.1]; exact h.2)).congr
    exact arithmetic_identity _ _ (fun _ => rfl)

theorem unitPower_small (j : Nat) (t : Rat) (ht : 0 ≤ t) (ht' : t ≤ 1) :
    Small (Value.rational (t^j)) 1 := by
  apply (FTCRealCalculus.rational_small (t^j)).mono
  rw [qabs_eq_self_of_nonneg (Rat.pow_nonneg ht)]
  induction j with
  | zero => rw [Rat.pow_zero]; exact Rat.le_refl
  | succ j ih =>
    rw [Rat.pow_succ]
    exact Rat.le_trans (Rat.mul_le_mul_of_nonneg_right ih ht) (by simpa only [Rat.one_mul] using ht')

end ComputableAnalysis.LipschitzQuadrature

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