Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Computable analysis · FiniteApproximateIdentity · fd889115 k1

Definition
liuyao_ca_fd889115_k1_Analysis_FiniteApproximateIdentity

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

ca-fd889115-k1

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

Definition code
import Definitions.Def_liuyao_ca_fd889115_k1_Analysis_Basic

set_option autoImplicit true

/-!
# Finite approximate identities

This module isolates the finite algebra behind an approximate identity.  A
kernel is a finite list of rational sample points with nonnegative rational
weights of total mass one.  Its action is therefore an executable rational
weighted sum.

No integral, topology, completed real number, or limiting assertion occurs
here.  A later quadrature construction can use this theorem after proving
that its finite weights have mass one and are concentrated in a region where
the sampled function has a stated rational modulus.
-/

namespace ComputableAnalysis

/-- One rational sample point and its rational quadrature weight. -/
structure WeightedPoint where
  point : Rat
  weight : Rat
deriving DecidableEq, Repr

namespace WeightedPoint

/-- Total mass of a finite weighted sample. -/
def totalWeight : List WeightedPoint -> Rat
  | [] => 0
  | sample :: rest => sample.weight + totalWeight rest

/-- The literal finite weighted action on a rational-valued function. -/
def action (samples : List WeightedPoint) (f : Rat -> Rat) : Rat :=
  match samples with
  | [] => 0
  | sample :: rest => sample.weight * f sample.point + action rest f

theorem action_append (left right : List WeightedPoint) (f : Rat -> Rat) :
    action (left ++ right) f = action left f + action right f := by
  induction left with
  | nil =>
      change action right f = 0 + action right f
      grind
  | cons sample rest ih =>
      simp only [List.cons_append, action]
      rw [ih]
      grind [Rat.add_assoc]

theorem action_const (samples : List WeightedPoint) (constant : Rat) :
    action samples (fun _ => constant) = constant * totalWeight samples := by
  induction samples with
  | nil =>
      change (0 : Rat) = constant * 0
      grind
  | cons sample rest ih =>
      simp only [action, totalWeight]
      rw [ih]
      grind [Rat.mul_add, Rat.add_mul, Rat.mul_comm]

theorem action_add (samples : List WeightedPoint) (f g : Rat -> Rat) :
    action samples (fun x => f x + g x) = action samples f + action samples g := by
  induction samples with
  | nil =>
      change (0 : Rat) = 0 + 0
      grind
  | cons sample rest ih =>
      simp only [action]
      rw [ih]
      grind [Rat.mul_add, Rat.add_assoc, Rat.add_comm]

theorem action_scale (samples : List WeightedPoint)
    (factor : Rat) (f : Rat -> Rat) :
    action samples (fun x => factor * f x) = factor * action samples f := by
  induction samples with
  | nil =>
      change (0 : Rat) = factor * 0
      grind
  | cons sample rest ih =>
      simp only [action]
      rw [ih]
      grind [Rat.mul_add, Rat.mul_assoc, Rat.mul_comm]

/-- The same action, centered at a prescribed rational value. -/
def centeredAction (samples : List WeightedPoint)
    (f : Rat -> Rat) (center : Rat) : Rat :=
  match samples with
  | [] => 0
  | sample :: rest =>
      sample.weight * (f sample.point - center) +
        centeredAction rest f center

theorem totalWeight_append (left right : List WeightedPoint) :
    totalWeight (left ++ right) = totalWeight left + totalWeight right := by
  induction left with
  | nil =>
      change totalWeight right = 0 + totalWeight right
      grind
  | cons sample rest ih =>
      simp only [List.cons_append, totalWeight]
      rw [ih]
      grind

theorem centeredAction_append (left right : List WeightedPoint)
    (f : Rat -> Rat) (center : Rat) :
    centeredAction (left ++ right) f center =
      centeredAction left f center + centeredAction right f center := by
  induction left with
  | nil =>
      change centeredAction right f center =
        0 + centeredAction right f center
      grind
  | cons sample rest ih =>
      simp only [List.cons_append, centeredAction]
      rw [ih]
      grind

theorem action_eq_center_mul_totalWeight_add_centeredAction
    (samples : List WeightedPoint) (f : Rat -> Rat) (center : Rat) :
    action samples f = center * totalWeight samples +
      centeredAction samples f center := by
  induction samples with
  | nil =>
      change (0 : Rat) = center * 0 + 0
      grind
  | cons sample rest ih =>
      simp only [action, totalWeight, centeredAction]
      rw [ih]
      grind [Rat.mul_add, Rat.add_mul, Rat.sub_eq_add_neg,
        Rat.mul_assoc, Rat.mul_comm]

/-- A finite weighted sum inherits a common pointwise error bound. -/
theorem qabs_centeredAction_le
    (samples : List WeightedPoint) (f : Rat -> Rat)
    (center error : Rat)
    (weights_nonnegative :
      forall sample, sample ∈ samples -> 0 <= sample.weight)
    (local_error :
      forall sample, sample ∈ samples ->
        qabs (f sample.point - center) <= error) :
    qabs (centeredAction samples f center) <=
      error * totalWeight samples := by
  induction samples with
  | nil => simp [centeredAction, totalWeight, qabs]
  | cons sample rest ih =>
      have hweight : 0 <= sample.weight :=
        weights_nonnegative sample (by simp)
      have hlocal : qabs (f sample.point - center) <= error :=
        local_error sample (by simp)
      have hrestWeights :
          forall item, item ∈ rest -> 0 <= item.weight := by
        intro item hitem
        exact weights_nonnegative item (by simp [hitem])
      have hrestLocal :
          forall item, item ∈ rest ->
            qabs (f item.point - center) <= error := by
        intro item hitem
        exact local_error item (by simp [hitem])
      have htail := ih hrestWeights hrestLocal
      calc
        qabs (centeredAction (sample :: rest) f center) =
            qabs (sample.weight * (f sample.point - center) +
              centeredAction rest f center) := by rfl
        _ <= qabs (sample.weight * (f sample.point - center)) +
              qabs (centeredAction rest f center) :=
            qabs_add_le _ _
        _ = sample.weight * qabs (f sample.point - center) +
              qabs (centeredAction rest f center) := by
            rw [qabs_mul, qabs_eq_self_of_nonneg hweight]
        _ <= sample.weight * error +
              error * totalWeight rest :=
            rat_add_le_add
              (Rat.mul_le_mul_of_nonneg_left hlocal hweight) htail
        _ = error * totalWeight (sample :: rest) := by
            simp only [totalWeight]
            grind [Rat.mul_add, Rat.add_mul, Rat.mul_comm]

/-- Split a finite weighted action into a well-controlled central part and a
separately controlled tail.  This is the finite rational estimate needed by
Gaussian quadrature: the central samples use a local modulus, while distant
samples are charged against their explicit tail mass. -/
theorem qabs_centeredAction_append_le
    (central tail : List WeightedPoint) (f : Rat -> Rat)
    (center centralError tailError : Rat)
    (central_weights_nonnegative :
      forall sample, sample ∈ central -> 0 <= sample.weight)
    (tail_weights_nonnegative :
      forall sample, sample ∈ tail -> 0 <= sample.weight)
    (central_error :
      forall sample, sample ∈ central ->
        qabs (f sample.point - center) <= centralError)
    (tail_error :
      forall sample, sample ∈ tail ->
        qabs (f sample.point - center) <= tailError) :
    qabs (centeredAction (central ++ tail) f center) <=
      centralError * totalWeight central +
        tailError * totalWeight tail := by
  rw [centeredAction_append]
  exact Rat.le_trans (qabs_add_le _ _)
    (rat_add_le_add
      (qabs_centeredAction_le central f center centralError
        central_weights_nonnegative central_error)
      (qabs_centeredAction_le tail f center tailError
        tail_weights_nonnegative tail_error))

/-- Multiply every weight by the same rational factor, leaving sample points
unchanged. -/
def scaleWeights (factor : Rat) : List WeightedPoint -> List WeightedPoint
  | [] => []
  | sample :: rest =>
      { point := sample.point, weight := factor * sample.weight } ::
        scaleWeights factor rest

theorem totalWeight_scaleWeights (factor : Rat)
    (samples : List WeightedPoint) :
    totalWeight (scaleWeights factor samples) =
      factor * totalWeight samples := by
  induction samples with
  | nil => simp [scaleWeights, totalWeight]
  | cons sample rest ih =>
      simp only [scaleWeights, totalWeight]
      rw [ih]
      grind [Rat.mul_add]

theorem action_scaleWeights (factor : Rat)
    (samples : List WeightedPoint) (f : Rat -> Rat) :
    action (scaleWeights factor samples) f = factor * action samples f := by
  induction samples with
  | nil => simp [scaleWeights, action]
  | cons sample rest ih =>
      simp only [scaleWeights, action]
      rw [ih]
      grind [Rat.mul_add, Rat.mul_assoc]

theorem scaleWeights_nonnegative
    (factor : Rat) (factor_nonnegative : 0 <= factor)
    (samples : List WeightedPoint)
    (weights_nonnegative :
      forall sample, sample ∈ samples -> 0 <= sample.weight) :
    forall sample, sample ∈ scaleWeights factor samples ->
      0 <= sample.weight := by
  induction samples with
  | nil =>
      intro sample hsample
      simp [scaleWeights] at hsample
  | cons head rest ih =>
      intro sample hsample
      simp only [scaleWeights, List.mem_cons] at hsample
      rcases hsample with hsample | hsample
      · rw [hsample]
        exact Rat.mul_nonneg factor_nonnegative
          (weights_nonnegative head (by simp))
      · apply ih
        · intro item hitem
          exact weights_nonnegative item (by simp [hitem])
        · exact hsample

theorem scaleWeights_preserves_point_bound
    (factor : Rat) (samples : List WeightedPoint) (bound : Rat)
    (points_bounded :
      forall sample, sample ∈ samples -> qabs sample.point <= bound) :
    forall sample, sample ∈ scaleWeights factor samples ->
      qabs sample.point <= bound := by
  induction samples with
  | nil =>
      intro sample hsample
      simp [scaleWeights] at hsample
  | cons head rest ih =>
      intro sample hsample
      simp only [scaleWeights, List.mem_cons] at hsample
      rcases hsample with hsample | hsample
      · rw [hsample]
        exact points_bounded head (by simp)
      · apply ih
        · intro item hitem
          exact points_bounded item (by simp [hitem])
        · exact hsample

end WeightedPoint

/-! ## Stability of aligned finite quadrature rules -/

/-- One source sample paired with one target sample.  A finite list of these
pairs is an explicit coupling between two quadrature rules; no matching or
choice principle is hidden in the comparison. -/
structure WeightedPointCoupling where
  source : WeightedPoint
  target : WeightedPoint
deriving DecidableEq, Repr

namespace WeightedPointCoupling

/-- Source weighted action of a finite coupling. -/
def sourceAction : List WeightedPointCoupling -> (Rat -> Rat) -> Rat
  | [], _ => 0
  | pair :: rest, f =>
      pair.source.weight * f pair.source.point + sourceAction rest f

/-- Target weighted action of a finite coupling. -/
def targetAction : List WeightedPointCoupling -> (Rat -> Rat) -> Rat
  | [], _ => 0
  | pair :: rest, f =>
      pair.target.weight * f pair.target.point + targetAction rest f

/-- Total source mass in the coupling. -/
def sourceTotalWeight : List WeightedPointCoupling -> Rat
  | [] => 0
  | pair :: rest => pair.source.weight + sourceTotalWeight rest

/-- Total absolute discrepancy between paired source and target weights. -/
def weightDiscrepancy : List WeightedPointCoupling -> Rat
  | [] => 0
  | pair :: rest =>
      qabs (pair.target.weight - pair.source.weight) +
        weightDiscrepancy rest

/-- Source sample list extracted from an explicit coupling. -/
def sourceSamples (pairs : List WeightedPointCoupling) : List WeightedPoint :=
  pairs.map (fun pair => pair.source)

/-- Target sample list extracted from an explicit coupling. -/
def targetSamples (pairs : List WeightedPointCoupling) : List WeightedPoint :=
  pairs.map (fun pair => pair.target)

theorem sourceAction_eq_action (pairs : List WeightedPointCoupling)
    (f : Rat -> Rat) :
    sourceAction pairs f = WeightedPoint.action (sourceSamples pairs) f := by
  induction pairs with
  | nil => rfl
  | cons pair rest ih => simp [sourceAction, sourceSamples, ih,
      WeightedPoint.action]

theorem targetAction_eq_action (pairs : List WeightedPointCoupling)
    (f : Rat -> Rat) :
    targetAction pairs f = WeightedPoint.action (targetSamples pairs) f := by
  induction pairs with
  | nil => rfl
  | cons pair rest ih => simp [targetAction, targetSamples, ih,
      WeightedPoint.action]

theorem sourceTotalWeight_eq_totalWeight
    (pairs : List WeightedPointCoupling) :
    sourceTotalWeight pairs =
      WeightedPoint.totalWeight (sourceSamples pairs) := by
  induction pairs with
  | nil => rfl
  | cons pair rest ih => simp [sourceTotalWeight, sourceSamples, ih,
      WeightedPoint.totalWeight]

/-- Finite quadrature stability under simultaneous perturbation of weights
and sample points.  The first term pays for changing weights, using a bound on
target values.  The second pays for transporting source points to target
points, using the original nonnegative mass. -/
theorem qabs_targetAction_sub_sourceAction_le
    (pairs : List WeightedPointCoupling) (sourceFunction targetFunction : Rat -> Rat)
    (valueBound pointError : Rat)
    (source_weights_nonnegative : forall pair, pair ∈ pairs ->
      0 <= pair.source.weight)
    (target_values_bounded : forall pair, pair ∈ pairs ->
      qabs (targetFunction pair.target.point) <= valueBound)
    (point_transport_error : forall pair, pair ∈ pairs ->
      qabs (targetFunction pair.target.point -
        sourceFunction pair.source.point) <= pointError) :
    qabs (targetAction pairs targetFunction -
      sourceAction pairs sourceFunction) <=
        valueBound * weightDiscrepancy pairs +
          pointError * sourceTotalWeight pairs := by
  induction pairs with
  | nil =>
      change qabs (0 - 0) <= valueBound * 0 + pointError * 0
      grind [qabs]
  | cons pair rest ih =>
      have hsourceWeight : 0 <= pair.source.weight :=
        source_weights_nonnegative pair (by simp)
      have htargetValue :
          qabs (targetFunction pair.target.point) <= valueBound :=
        target_values_bounded pair (by simp)
      have hpointError :
          qabs (targetFunction pair.target.point -
            sourceFunction pair.source.point) <= pointError :=
        point_transport_error pair (by simp)
      have hrestSourceWeights : forall item, item ∈ rest ->
          0 <= item.source.weight := by
        intro item hitem
        exact source_weights_nonnegative item (by simp [hitem])
      have hrestTargetValues : forall item, item ∈ rest ->
          qabs (targetFunction item.target.point) <= valueBound := by
        intro item hitem
        exact target_values_bounded item (by simp [hitem])
      have hrestPointError : forall item, item ∈ rest ->
          qabs (targetFunction item.target.point -
            sourceFunction item.source.point) <= pointError := by
        intro item hitem
        exact point_transport_error item (by simp [hitem])
      have htail := ih hrestSourceWeights hrestTargetValues hrestPointError
      have hweightTerm :
          qabs ((pair.target.weight - pair.source.weight) *
              targetFunction pair.target.point) <=
            qabs (pair.target.weight - pair.source.weight) * valueBound := by
        rw [qabs_mul]
        exact Rat.mul_le_mul_of_nonneg_left htargetValue
          (qabs_nonneg _)
      have hpointTerm :
          qabs (pair.source.weight *
              (targetFunction pair.target.point -
                sourceFunction pair.source.point)) <=
            pair.source.weight * pointError := by
        rw [qabs_mul, qabs_eq_self_of_nonneg hsourceWeight]
        exact Rat.mul_le_mul_of_nonneg_left hpointError hsourceWeight
      have hhead :
          qabs ((pair.target.weight - pair.source.weight) *
              targetFunction pair.target.point +
            pair.source.weight *
              (targetFunction pair.target.point -
                sourceFunction pair.source.point)) <=
            qabs (pair.target.weight - pair.source.weight) * valueBound +
              pair.source.weight * pointError :=
        Rat.le_trans (qabs_add_le _ _)
          (rat_add_le_add hweightTerm hpointTerm)
      have hrearrange :
          targetAction (pair :: rest) targetFunction -
              sourceAction (pair :: rest) sourceFunction =
            ((pair.target.weight - pair.source.weight) *
                targetFunction pair.target.point +
              pair.source.weight *
                (targetFunction pair.target.point -
                  sourceFunction pair.source.point)) +
              (targetAction rest targetFunction -
                sourceAction rest sourceFunction) := by
        simp only [targetAction, sourceAction]
        grind [Rat.mul_add, Rat.add_mul, Rat.sub_eq_add_neg,
          Rat.mul_assoc, Rat.mul_comm]
      rw [hrearrange]
      calc
        qabs
            (((pair.target.weight - pair.source.weight) *
                targetFunction pair.target.point +
              pair.source.weight *
                (targetFunction pair.target.point -
                  sourceFunction pair.source.point)) +
              (targetAction rest targetFunction -
                sourceAction rest sourceFunction)) <=
            qabs ((pair.target.weight - pair.source.weight) *
                targetFunction pair.target.point +
              pair.source.weight *
                (targetFunction pair.target.point -
                  sourceFunction pair.source.point)) +
              qabs (targetAction rest targetFunction -
                sourceAction rest sourceFunction) := qabs_add_le _ _
        _ <=
            (qabs (pair.target.weight - pair.source.weight) * valueBound +
              pair.source.weight * pointError) +
              (valueBound * weightDiscrepancy rest +
                pointError * sourceTotalWeight rest) :=
          rat_add_le_add hhead htail
        _ = valueBound * weightDiscrepancy (pair :: rest) +
              pointError * sourceTotalWeight (pair :: rest) := by
          simp only [weightDiscrepancy, sourceTotalWeight]
          grind [Rat.mul_add, Rat.add_mul, Rat.mul_comm, Rat.mul_assoc]

/-- Exact-weight specialization: when paired weights agree, only transport of
sample points contributes to the quadrature error. -/
theorem qabs_targetAction_sub_sourceAction_le_of_weights_eq
    (pairs : List WeightedPointCoupling) (sourceFunction targetFunction : Rat -> Rat)
    (pointError : Rat)
    (source_weights_nonnegative : forall pair, pair ∈ pairs ->
      0 <= pair.source.weight)
    (weights_eq : forall pair, pair ∈ pairs ->
      pair.target.weight = pair.source.weight)
    (point_transport_error : forall pair, pair ∈ pairs ->
      qabs (targetFunction pair.target.point -
        sourceFunction pair.source.point) <= pointError) :
    qabs (targetAction pairs targetFunction -
      sourceAction pairs sourceFunction) <=
        pointError * sourceTotalWeight pairs := by
  induction pairs with
  | nil =>
      change qabs (0 - 0) <= pointError * 0
      grind [qabs]
  | cons pair rest ih =>
      have hsourceWeight : 0 <= pair.source.weight :=
        source_weights_nonnegative pair (by simp)
      have hweight : pair.target.weight = pair.source.weight :=
        weights_eq pair (by simp)
      have hpointError :
          qabs (targetFunction pair.target.point -
            sourceFunction pair.source.point) <= pointError :=
        point_transport_error pair (by simp)
      have htail := ih
        (fun item hitem => source_weights_nonnegative item (by simp [hitem]))
        (fun item hitem => weights_eq item (by simp [hitem]))
        (fun item hitem => point_transport_error item (by simp [hitem]))
      have hhead :
          qabs (pair.source.weight *
            (targetFunction pair.target.point -
              sourceFunction pair.source.point)) <=
            pair.source.weight * pointError := by
        rw [qabs_mul, qabs_eq_self_of_nonneg hsourceWeight]
        exact Rat.mul_le_mul_of_nonneg_left hpointError hsourceWeight
      have hrearrange :
          targetAction (pair :: rest) targetFunction -
              sourceAction (pair :: rest) sourceFunction =
            pair.source.weight *
                (targetFunction pair.target.point -
                  sourceFunction pair.source.point) +
              (targetAction rest targetFunction -
                sourceAction rest sourceFunction) := by
        simp only [targetAction, sourceAction]
        rw [hweight]
        grind [Rat.mul_add, Rat.add_mul, Rat.sub_eq_add_neg,
          Rat.mul_assoc, Rat.mul_comm]
      rw [hrearrange]
      exact Rat.le_trans (qabs_add_le _ _)
        (Rat.le_trans (rat_add_le_add hhead htail) (by
          simp only [sourceTotalWeight]
          grind [Rat.mul_add, Rat.add_mul, Rat.mul_comm]))

/-- The same stability estimate stated through the public finite weighted
action on the two sample lists extracted from the coupling. -/
theorem qabs_action_targetSamples_sub_action_sourceSamples_le
    (pairs : List WeightedPointCoupling) (sourceFunction targetFunction : Rat -> Rat)
    (valueBound pointError : Rat)
    (source_weights_nonnegative : forall pair, pair ∈ pairs ->
      0 <= pair.source.weight)
    (target_values_bounded : forall pair, pair ∈ pairs ->
      qabs (targetFunction pair.target.point) <= valueBound)
    (point_transport_error : forall pair, pair ∈ pairs ->
      qabs (targetFunction pair.target.point -
        sourceFunction pair.source.point) <= pointError) :
    qabs (WeightedPoint.action (targetSamples pairs) targetFunction -
      WeightedPoint.action (sourceSamples pairs) sourceFunction) <=
        valueBound * weightDiscrepancy pairs +
          pointError * WeightedPoint.totalWeight (sourceSamples pairs) := by
  rw [← targetAction_eq_action, ← sourceAction_eq_action,
    ← sourceTotalWeight_eq_totalWeight]
  exact qabs_targetAction_sub_sourceAction_le pairs
    sourceFunction targetFunction valueBound pointError
    source_weights_nonnegative target_values_bounded point_transport_error

/-- Public-action form of exact-weight point transport. -/
theorem qabs_action_targetSamples_sub_action_sourceSamples_le_of_weights_eq
    (pairs : List WeightedPointCoupling) (sourceFunction targetFunction : Rat -> Rat)
    (pointError : Rat)
    (source_weights_nonnegative : forall pair, pair ∈ pairs ->
      0 <= pair.source.weight)
    (weights_eq : forall pair, pair ∈ pairs ->
      pair.target.weight = pair.source.weight)
    (point_transport_error : forall pair, pair ∈ pairs ->
      qabs (targetFunction pair.target.point -
        sourceFunction pair.source.point) <= pointError) :
    qabs (WeightedPoint.action (targetSamples pairs) targetFunction -
      WeightedPoint.action (sourceSamples pairs) sourceFunction) <=
        pointError * WeightedPoint.totalWeight (sourceSamples pairs) := by
  rw [← targetAction_eq_action, ← sourceAction_eq_action,
    ← sourceTotalWeight_eq_totalWeight]
  exact qabs_targetAction_sub_sourceAction_le_of_weights_eq pairs
    sourceFunction targetFunction pointError source_weights_nonnegative
    weights_eq point_transport_error

end WeightedPointCoupling

/-- Executable finite probability data: nonnegative rational weights with
exact rational total mass one. -/
structure FiniteProbabilityKernel where
  samples : List WeightedPoint
  weights_nonnegative :
    forall sample, sample ∈ samples -> 0 <= sample.weight
  totalWeight_eq_one : WeightedPoint.totalWeight samples = 1

namespace FiniteProbabilityKernel

def action (kernel : FiniteProbabilityKernel) (f : Rat -> Rat) : Rat :=
  WeightedPoint.action kernel.samples f

/-- Finite approximate-identity theorem in its most direct form.  If every
sample seen by the normalized positive kernel is within `error` of `center`,
then the kernel action is within the same error. -/
theorem action_approximates_center
    (kernel : FiniteProbabilityKernel) (f : Rat -> Rat)
    (center error : Rat)
    (local_error :
      forall sample, sample ∈ kernel.samples ->
        qabs (f sample.point - center) <= error) :
    qabs (kernel.action f - center) <= error := by
  have hcentered := WeightedPoint.qabs_centeredAction_le
    kernel.samples f center error
    kernel.weights_nonnegative local_error
  have haction := WeightedPoint.action_eq_center_mul_totalWeight_add_centeredAction
    kernel.samples f center
  rw [kernel.totalWeight_eq_one] at haction hcentered
  have heq :
      kernel.action f - center =
        WeightedPoint.centeredAction kernel.samples f center := by
    unfold action
    rw [haction]
    grind
  rw [heq]
  simpa using hcentered

/-- Radius/Lipschitz specialization.  This is the reusable concentration
estimate used by finite quadrature approximations to a Gaussian delta family.
-/
theorem action_approximates_value_at_zero
    (kernel : FiniteProbabilityKernel) (f : Rat -> Rat)
    (lipschitz radius : Rat)
    (lipschitz_nonnegative : 0 <= lipschitz)
    (support_radius :
      forall sample, sample ∈ kernel.samples ->
        qabs sample.point <= radius)
    (lipschitz_at_zero :
      forall sample, sample ∈ kernel.samples ->
        qabs (f sample.point - f 0) <=
          lipschitz * qabs sample.point) :
    qabs (kernel.action f - f 0) <= lipschitz * radius := by
  apply kernel.action_approximates_center f (f 0) (lipschitz * radius)
  intro sample hsample
  exact Rat.le_trans (lipschitz_at_zero sample hsample)
    (Rat.mul_le_mul_of_nonneg_left
      (support_radius sample hsample) lipschitz_nonnegative)

/-- Central/tail form of the finite approximate-identity estimate.  Unlike a
single global error bound, this records the small mass of distant samples
explicitly and is therefore the useful shape for a truncated Gaussian. -/
theorem action_approximates_center_of_split
    (kernel : FiniteProbabilityKernel) (f : Rat -> Rat)
    (center centralError tailError : Rat)
    (central tail : List WeightedPoint)
    (split : kernel.samples = central ++ tail)
    (central_error :
      forall sample, sample ∈ central ->
        qabs (f sample.point - center) <= centralError)
    (tail_error :
      forall sample, sample ∈ tail ->
        qabs (f sample.point - center) <= tailError) :
    qabs (kernel.action f - center) <=
      centralError * WeightedPoint.totalWeight central +
        tailError * WeightedPoint.totalWeight tail := by
  have hcentralWeights :
      forall sample, sample ∈ central -> 0 <= sample.weight := by
    intro sample hsample
    apply kernel.weights_nonnegative sample
    rw [split]
    exact List.mem_append_left tail hsample
  have htailWeights :
      forall sample, sample ∈ tail -> 0 <= sample.weight := by
    intro sample hsample
    apply kernel.weights_nonnegative sample
    rw [split]
    exact List.mem_append_right central hsample
  have haction := WeightedPoint.action_eq_center_mul_totalWeight_add_centeredAction
    kernel.samples f center
  rw [kernel.totalWeight_eq_one] at haction
  have heq :
      kernel.action f - center =
        WeightedPoint.centeredAction kernel.samples f center := by
    unfold action
    rw [haction]
    grind
  rw [heq, split]
  exact WeightedPoint.qabs_centeredAction_append_le
    central tail f center centralError tailError
    hcentralWeights htailWeights central_error tail_error

end FiniteProbabilityKernel

/-- Unnormalized finite positive kernel data.  This is the input shape of a
rational quadrature rule before division by its computed total mass. -/
structure FinitePositiveKernelData where
  samples : List WeightedPoint
  weights_nonnegative :
    forall sample, sample ∈ samples -> 0 <= sample.weight
  totalWeight_positive : 0 < WeightedPoint.totalWeight samples

namespace FinitePositiveKernelData

/-- Exact rational normalization by the finite computed total mass. -/
def normalized (data : FinitePositiveKernelData) : FiniteProbabilityKernel where
  samples := WeightedPoint.scaleWeights
    (WeightedPoint.totalWeight data.samples)⁻¹ data.samples
  weights_nonnegative := WeightedPoint.scaleWeights_nonnegative
    (WeightedPoint.totalWeight data.samples)⁻¹
    (Rat.le_of_lt ((Rat.inv_pos).2 data.totalWeight_positive))
    data.samples data.weights_nonnegative
  totalWeight_eq_one := by
    rw [WeightedPoint.totalWeight_scaleWeights]
    have hnonzero : WeightedPoint.totalWeight data.samples ≠ 0 :=
      Rat.ne_of_gt data.totalWeight_positive
    grind [Rat.mul_comm, Rat.mul_inv_cancel _ hnonzero]

theorem normalized_action (data : FinitePositiveKernelData)
    (f : Rat -> Rat) :
    data.normalized.action f =
      (WeightedPoint.totalWeight data.samples)⁻¹ *
        WeightedPoint.action data.samples f := by
  unfold normalized FiniteProbabilityKernel.action
  exact WeightedPoint.action_scaleWeights _ _ _

theorem normalized_support
    (data : FinitePositiveKernelData) (bound : Rat)
    (points_bounded : forall sample, sample ∈ data.samples ->
      qabs sample.point <= bound) :
    forall sample, sample ∈ data.normalized.samples ->
      qabs sample.point <= bound :=
  WeightedPoint.scaleWeights_preserves_point_bound _ _ _ points_bounded

end FinitePositiveKernelData

/-- A fully scheduled finite approximate identity.  The schedule is part of
the data: asking for a positive rational radius returns a stage whose finite
kernel is supported inside that radius. -/
structure FiniteApproximateIdentity where
  kernel : Nat -> FiniteProbabilityKernel
  radius : Nat -> Rat
  radius_nonnegative : forall stage, 0 <= radius stage
  support_radius : forall stage sample,
    sample ∈ (kernel stage).samples -> qabs sample.point <= radius stage
  schedule : Rat -> Nat
  schedule_spec : forall requested,
    0 < requested -> radius (schedule requested) <= requested

namespace FiniteApproximateIdentity

/-- Explicit convergence rate on a rational Lipschitz probe. -/
theorem action_rate
    (family : FiniteApproximateIdentity) (f : Rat -> Rat)
    (lipschitz requestedError : Rat)
    (lipschitz_positive : 0 < lipschitz)
    (requestedError_positive : 0 < requestedError)
    (lipschitz_at_zero : forall sample,
      sample ∈ (family.kernel
        (family.schedule (requestedError / lipschitz))).samples ->
        qabs (f sample.point - f 0) <=
          lipschitz * qabs sample.point) :
    qabs ((family.kernel
      (family.schedule (requestedError / lipschitz))).action f - f 0) <=
        requestedError := by
  have hlipschitzNonnegative : 0 <= lipschitz := Rat.le_of_lt lipschitz_positive
  have hlipschitzNonzero : lipschitz ≠ 0 := Rat.ne_of_gt lipschitz_positive
  have hrequested : 0 < requestedError / lipschitz := by
    rw [Rat.div_def]
    exact Rat.mul_pos requestedError_positive
      ((Rat.inv_pos).2 lipschitz_positive)
  let stage := family.schedule (requestedError / lipschitz)
  have hradius := family.schedule_spec
    (requestedError / lipschitz) hrequested
  have hfinite := (family.kernel stage).action_approximates_value_at_zero
    f lipschitz (family.radius stage) hlipschitzNonnegative
    (family.support_radius stage)
    lipschitz_at_zero
  have hscaled :
      lipschitz * family.radius stage <= requestedError := by
    calc
      lipschitz * family.radius stage <=
          lipschitz * (requestedError / lipschitz) :=
        Rat.mul_le_mul_of_nonneg_left hradius hlipschitzNonnegative
      _ = requestedError := by
        rw [Rat.div_def]
        grind [Rat.mul_assoc, Rat.mul_comm,
          Rat.mul_inv_cancel _ hlipschitzNonzero]
  exact Rat.le_trans hfinite hscaled

end FiniteApproximateIdentity

/-! ## A concrete shrinking two-point family -/

/-- The positive rational radius `1/(stage+1)`. -/
def reciprocalStageRadius (stage : Nat) : Rat :=
  1 / (((stage + 1 : Nat) : Rat))

theorem reciprocalStageRadius_positive (stage : Nat) :
    0 < reciprocalStageRadius stage := by
  unfold reciprocalStageRadius
  rw [Rat.div_def, Rat.one_mul]
  exact (Rat.inv_pos).2
    ((Rat.natCast_pos).2 (Nat.succ_pos stage))

theorem reciprocalStageRadius_le_one (stage : Nat) :
    reciprocalStageRadius stage <= 1 := by
  have hden : (1 : Rat) <= ((stage + 1 : Nat) : Rat) := by
    change ((1 : Nat) : Rat) <= ((stage + 1 : Nat) : Rat)
    exact (Rat.natCast_le_natCast).2
      (Nat.succ_le_succ (Nat.zero_le stage))
  have hdenPos : (0 : Rat) < ((stage + 1 : Nat) : Rat) := by
    exact (Rat.natCast_pos).2 (Nat.succ_pos stage)
  have hdenNe : (((stage + 1 : Nat) : Rat)) ≠ 0 := Rat.ne_of_gt hdenPos
  unfold reciprocalStageRadius
  apply Rat.le_of_mul_le_mul_right (c := ((stage + 1 : Nat) : Rat))
  · calc
      (1 / (((stage + 1 : Nat) : Rat))) * (((stage + 1 : Nat) : Rat)) = 1 := by
        rw [Rat.div_def]
        grind [Rat.mul_assoc, Rat.mul_comm, Rat.mul_inv_cancel]
      _ <= ((stage + 1 : Nat) : Rat) := hden
      _ = 1 * ((stage + 1 : Nat) : Rat) := by grind
  · exact hdenPos

/-- Equal mass at the two rational points `-1/(stage+1)` and
`1/(stage+1)`. -/
def symmetricTwoPointKernel (stage : Nat) : FiniteProbabilityKernel where
  samples :=
    [ { point := -reciprocalStageRadius stage, weight := 1 / 2 },
      { point := reciprocalStageRadius stage, weight := 1 / 2 } ]
  weights_nonnegative := by
    intro sample hsample
    simp only [List.mem_cons, List.not_mem_nil, or_false] at hsample
    rcases hsample with hsample | hsample
    · rw [hsample]
      change (0 : Rat) <= 1 / 2
      decide +kernel
    · rw [hsample]
      change (0 : Rat) <= 1 / 2
      decide +kernel
  totalWeight_eq_one := by
    simp [WeightedPoint.totalWeight]
    decide +kernel

theorem symmetricTwoPointKernel_action
    (stage : Nat) (f : Rat -> Rat) :
    (symmetricTwoPointKernel stage).action f =
      (f (-reciprocalStageRadius stage) +
        f (reciprocalStageRadius stage)) / 2 := by
  unfold symmetricTwoPointKernel FiniteProbabilityKernel.action
  simp only [WeightedPoint.action]
  grind [Rat.div_def, Rat.mul_add, Rat.add_mul, Rat.mul_comm,
    Rat.mul_assoc]

theorem symmetricTwoPointKernel_support
    (stage : Nat) (sample : WeightedPoint)
    (hsample : sample ∈ (symmetricTwoPointKernel stage).samples) :
    qabs sample.point <= reciprocalStageRadius stage := by
  have hradius : 0 <= reciprocalStageRadius stage :=
    Rat.le_of_lt (reciprocalStageRadius_positive stage)
  simp only [symmetricTwoPointKernel, List.mem_cons,
    List.not_mem_nil, or_false] at hsample
  rcases hsample with hsample | hsample
  ·
    rw [hsample]
    rw [qabs_neg, qabs_eq_self_of_nonneg hradius]
    exact Rat.le_refl
  ·
    rw [hsample]
    rw [qabs_eq_self_of_nonneg hradius]
    exact Rat.le_refl

/-- A completely executable approximate identity with denominator-based
schedule.  It is a regression model for concentration estimates, not a claim
that these two weights are Gaussian quadrature. -/
def symmetricTwoPointApproximateIdentity : FiniteApproximateIdentity where
  kernel := symmetricTwoPointKernel
  radius := reciprocalStageRadius
  radius_nonnegative := fun stage =>
    Rat.le_of_lt (reciprocalStageRadius_positive stage)
  support_radius := symmetricTwoPointKernel_support
  schedule := fun requested => requested.den
  schedule_spec := by
    intro requested hrequested
    exact one_div_den_succ_le_of_pos hrequested

theorem symmetricTwoPointApproximateIdentity_action_rate
    (f : Rat -> Rat) (lipschitz requestedError : Rat)
    (lipschitz_positive : 0 < lipschitz)
    (requestedError_positive : 0 < requestedError)
    (lipschitz_at_zero : forall x : Rat,
      qabs (f x - f 0) <= lipschitz * qabs x) :
    qabs
      ((symmetricTwoPointKernel
        ((requestedError / lipschitz).den)).action f - f 0) <=
          requestedError := by
  exact symmetricTwoPointApproximateIdentity.action_rate
    f lipschitz requestedError lipschitz_positive requestedError_positive
    (fun sample _ => lipschitz_at_zero sample.point)

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