Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Computable analysis · FTC · fd889115 k1

Definition
liuyao_ca_fd889115_k1_Analysis_FTC

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

ca-fd889115-k1

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

Definition code
import Definitions.Def_liuyao_ca_fd889115_k1_Analysis_Differential
import Definitions.Def_liuyao_ca_fd889115_k1_Analysis_Basic

set_option autoImplicit true

/-!
# Effective fundamental theorem of calculus

This file contains numerical comparison and stabilization lemmas for existing
FTC algorithms. The mathematical law for an arbitrary supplied integral is
`Integral.HasIntegral.ftc` in `IntegralFTC`. Numerical validity and an
endpoint comparison alone do not establish `Integral.HasIntegral`.
-/

namespace ComputableAnalysis

namespace FTC

theorem one_div_den_succ_le_of_pos {q : Rat} (hq : 0 < q) :
    1 / (((q.den + 1 : Nat) : Rat)) <= q := by
  let d : Rat := ((q.den + 1 : Nat) : Rat)
  have hdpos : 0 < d := by
    dsimp [d]
    exact (Rat.natCast_pos).2 (Nat.succ_pos q.den)
  have hnumpos : 0 < q.num := rat_num_pos_of_pos hq
  have hnumgeInt : (1 : Int) <= q.num := by omega
  have hnumge : (1 : Rat) <= (q.num : Rat) := by
    exact_mod_cast hnumgeInt
  have hqd :
      q * d = (q.num : Rat) + q := by
    dsimp [d]
    have hden := rat_den_mul_self q
    grind [Rat.mul_add, Rat.mul_assoc, Rat.mul_comm]
  have hqd_ge_one : 1 <= q * d := by
    rw [hqd]
    grind [Rat.le_of_lt hq]
  apply Rat.le_of_mul_le_mul_right (c := d)
  · calc
      (1 / d) * d = 1 := by
        rw [Rat.div_def]
        have hdne : d ≠ 0 := Rat.ne_of_gt hdpos
        grind [Rat.mul_assoc, Rat.mul_comm, Rat.mul_inv_cancel]
      _ <= q * d := hqd_ge_one
  · exact hdpos

theorem one_div_nat_antitone {n m : Nat}
    (hn : 0 < n) (hm : 0 < m) (hnm : n <= m) :
    (1 / (m : Rat)) <= 1 / (n : Rat) := by
  apply Rat.le_of_mul_le_mul_right (c := (n : Rat) * (m : Rat))
  · calc
      (1 / (m : Rat)) * ((n : Rat) * (m : Rat)) = (n : Rat) := by
        have hmne : (m : Rat) ≠ 0 :=
          Rat.ne_of_gt ((Rat.natCast_pos).2 hm)
        grind [Rat.div_def, Rat.mul_assoc, Rat.mul_comm, Rat.mul_inv_cancel]
      _ <= (m : Rat) := by
        exact_mod_cast hnm
      _ = (1 / (n : Rat)) * ((n : Rat) * (m : Rat)) := by
        have hnne : (n : Rat) ≠ 0 :=
          Rat.ne_of_gt ((Rat.natCast_pos).2 hn)
        grind [Rat.div_def, Rat.mul_assoc, Rat.mul_comm, Rat.mul_inv_cancel]
  · exact Rat.mul_pos ((Rat.natCast_pos).2 hn) ((Rat.natCast_pos).2 hm)

def requestedPrecision (n : Nat) : QPos :=
  if hn : n = 0 then
    { val := 1, property := by decide +kernel }
  else
    { val := (1 / (n : Rat)), property := one_div_nat_pos (Nat.pos_of_ne_zero hn) }

theorem requestedPrecision_positive (n : Nat) :
    0 < (requestedPrecision n).val := by
  by_cases hn : n = 0
  · simp [requestedPrecision, hn]
    decide +kernel
  · simp [requestedPrecision, hn]
    exact one_div_nat_pos (Nat.pos_of_ne_zero hn)

theorem requestedPrecision_le_one (n : Nat) :
    (requestedPrecision n).val <= 1 := by
  by_cases hn : n = 0
  · simp [requestedPrecision, hn]
  · rw [requestedPrecision, dif_neg hn]
    change 1 / (n : Rat) <= 1
    have h := one_div_nat_antitone (n := 1) (m := n)
      (by decide +kernel) (Nat.pos_of_ne_zero hn)
      (Nat.one_le_iff_ne_zero.mpr hn)
    calc
      1 / (n : Rat) <= 1 / (1 : Rat) := h
      _ = 1 := by decide +kernel

theorem requestedPrecision_antitone {n m : Nat} (hnm : n <= m) :
    (requestedPrecision m).val <= (requestedPrecision n).val := by
  by_cases hn : n = 0
  · simp [requestedPrecision, hn]
    exact requestedPrecision_le_one m
  · have hnpos : 0 < n := Nat.pos_of_ne_zero hn
    have hmpos : 0 < m := Nat.lt_of_lt_of_le hnpos hnm
    have h := one_div_nat_antitone hnpos hmpos hnm
    simpa [requestedPrecision, hn, Nat.ne_of_gt hmpos] using h

def riemannComputeOfEffectiveFTC
    {F dF : RealFunRaw} {a b : Rat}
    (h : EffectiveFTC F dF a b) : Nat -> QInterval :=
  fun n =>
    let eps := requestedPrecision n
    riemannLeftInterval dF a b
      (h.chooseN eps)
      (h.chooseEvalPrecision eps)

def endpointComputeOfEffectiveFTC
    {F dF : RealFunRaw} {a b : Rat}
    (h : EffectiveFTC F dF a b) : Nat -> QInterval :=
  fun n =>
    let eps := requestedPrecision n
    endpointDifferenceInterval F a b (h.chooseEvalPrecision eps)

def riemannRawOfEffectiveFTC
    {F dF : RealFunRaw} {a b : Rat}
    (h : EffectiveFTC F dF a b) : RealCompute where
  compute := riemannComputeOfEffectiveFTC h

def endpointRawOfEffectiveFTC
    {F dF : RealFunRaw} {a b : Rat}
    (h : EffectiveFTC F dF a b) : RealCompute where
  compute := endpointComputeOfEffectiveFTC h

/-- Agreement between a scheduled endpoint-difference algorithm and the
canonical endpoint-difference raw real.

An `EffectiveFTC` chooses an endpoint evaluation precision as part of its
finite schedule.  To turn the scheduled FTC bridge into the canonical
endpoint formula `F(b)-F(a)`, we separately prove that the scheduled endpoint
raw real is a valid representative of the canonical endpoint-difference
algorithm. -/
structure EndpointScheduleAgreement
    (F : RealFunRaw) (a b : Rat) (scheduledEndpoint : RealCompute) where
  endpoint_valid :
    RealCompute.ValidCompute (endpointDifferenceCompute F a b)
  scheduled_valid : scheduledEndpoint.Valid
  equivalent :
    scheduledEndpoint.Equiv
      (endpointDifferenceRaw F a b endpoint_valid)

namespace EndpointScheduleAgreement

theorem endpoint_raw_valid
    {F : RealFunRaw} {a b : Rat} {scheduledEndpoint : RealCompute}
    (h : EndpointScheduleAgreement F a b scheduledEndpoint) :
    (endpointDifferenceRaw F a b h.endpoint_valid).Valid := by
  simpa [endpointDifferenceRaw, RealCompute.Valid] using h.endpoint_valid

end EndpointScheduleAgreement

/-- Build endpoint-schedule agreement for an `EffectiveFTC` when its endpoint
precision choices are a cofinal monotone stage schedule for the canonical
endpoint-difference raw real. -/
theorem endpointScheduleAgreement_of_effectiveFTC_stageSchedule
    {F dF : RealFunRaw} {a b : Rat}
    (h : EffectiveFTC F dF a b)
    (hendpoint : RealCompute.ValidCompute (endpointDifferenceCompute F a b))
    (sigma : RealCompute.StageSchedule)
    (hsigma :
      forall n, h.chooseEvalPrecision (requestedPrecision n) = sigma.stage n) :
    EndpointScheduleAgreement F a b (endpointRawOfEffectiveFTC h) := by
  let endpoint : RealCompute := endpointDifferenceRaw F a b hendpoint
  have hendpointValid : endpoint.Valid := by
    simpa [endpoint, endpointDifferenceRaw, RealCompute.Valid] using hendpoint
  refine
    { endpoint_valid := hendpoint
      scheduled_valid := ?_
      equivalent := ?_ }
  · have hsched := RealCompute.schedule_valid endpoint hendpointValid sigma
    have hcompute :
        endpointComputeOfEffectiveFTC h =
          fun n => endpointDifferenceCompute F a b (sigma.stage n) := by
      funext n
      simp [endpointComputeOfEffectiveFTC, endpointDifferenceCompute, hsigma]
    simpa [endpointRawOfEffectiveFTC, RealCompute.Valid, RealCompute.schedule,
      endpoint, endpointDifferenceRaw, endpointDifferenceCompute,
      hcompute] using hsched
  · intro n
    have hall := RealCompute.allStagesOverlap_refl endpoint hendpointValid
      (sigma.stage n) n
    have hover := (RealCompute.compareAt_overlap_iff endpoint endpoint
      (sigma.stage n) n).1 hall
    apply (RealCompute.compareAt_overlap_iff
      (endpointRawOfEffectiveFTC h)
      (endpointDifferenceRaw F a b hendpoint) n n).2
    simpa [endpointRawOfEffectiveFTC, endpointComputeOfEffectiveFTC,
      endpoint, endpointDifferenceRaw, endpointDifferenceCompute,
      endpointDifferenceInterval, hsigma] using hover

/-- Static-dyadic endpoint-schedule agreement is the same endpoint schedule
agreement after forgetting to `EffectiveFTC`. -/
theorem endpointScheduleAgreement_of_staticDyadicEffectiveFTC_stageSchedule
    {F dF : RealFunRaw} {a b : Rat}
    (h : StaticDyadicEffectiveFTC F dF a b)
    (hendpoint : RealCompute.ValidCompute (endpointDifferenceCompute F a b))
    (sigma : RealCompute.StageSchedule)
    (hsigma :
      forall n, h.chooseEvalPrecision (requestedPrecision n) = sigma.stage n) :
    EndpointScheduleAgreement F a b
      (endpointRawOfEffectiveFTC h.toEffectiveFTC) :=
  endpointScheduleAgreement_of_effectiveFTC_stageSchedule
    h.toEffectiveFTC hendpoint sigma hsigma

/-- Build endpoint-schedule agreement for a derivative-bound FTC certificate
when its endpoint precision choices are a cofinal monotone stage schedule for
the canonical endpoint-difference raw real. -/
theorem endpointScheduleAgreement_of_derivativeBoundFTC_stageSchedule
    {F dF : RealFunRaw} {a b : Rat}
    (h : DerivativeBoundFTC F dF a b)
    (hendpoint : RealCompute.ValidCompute (endpointDifferenceCompute F a b))
    (sigma : RealCompute.StageSchedule)
    (hsigma :
      forall n, h.chooseEndpointPrecision (precisionAtStage n) = sigma.stage n) :
    EndpointScheduleAgreement F a b h.endpointRaw := by
  let endpoint : RealCompute := endpointDifferenceRaw F a b hendpoint
  have hendpointValid : endpoint.Valid := by
    simpa [endpoint, endpointDifferenceRaw, RealCompute.Valid] using hendpoint
  refine
    { endpoint_valid := hendpoint
      scheduled_valid := ?_
      equivalent := ?_ }
  · have hsched := RealCompute.schedule_valid endpoint hendpointValid sigma
    have hcompute :
        h.endpointCompute =
          fun n => endpointDifferenceCompute F a b (sigma.stage n) := by
      funext n
      simp [DerivativeBoundFTC.endpointCompute,
        DerivativeBoundFTC.endpointInterval, endpointDifferenceCompute, hsigma]
    simpa [DerivativeBoundFTC.endpointRaw, RealCompute.Valid, RealCompute.schedule,
      endpoint, endpointDifferenceRaw, endpointDifferenceCompute,
      hcompute] using hsched
  · intro n
    have hall := RealCompute.allStagesOverlap_refl endpoint hendpointValid
      (sigma.stage n) n
    have hover := (RealCompute.compareAt_overlap_iff endpoint endpoint
      (sigma.stage n) n).1 hall
    apply (RealCompute.compareAt_overlap_iff
      h.endpointRaw
      (endpointDifferenceRaw F a b hendpoint) n n).2
    simpa [DerivativeBoundFTC.endpointRaw, DerivativeBoundFTC.endpointCompute,
      DerivativeBoundFTC.endpointInterval, endpoint, endpointDifferenceRaw,
      endpointDifferenceCompute, endpointDifferenceInterval, hsigma] using hover

/-- Candidate-derivative endpoint-schedule agreement, by conversion to the
derivative-bound FTC certificate. -/
theorem endpointScheduleAgreement_of_candidateDerivativeFTC_stageSchedule
    {F dF : RealFunRaw} {a b : Rat}
    (h : CandidateDerivativeFTC F dF a b)
    (hendpoint : RealCompute.ValidCompute (endpointDifferenceCompute F a b))
    (sigma : RealCompute.StageSchedule)
    (hsigma :
      forall n,
        h.toDerivativeBoundFTC.chooseEndpointPrecision (precisionAtStage n) =
          sigma.stage n) :
    EndpointScheduleAgreement F a b h.toDerivativeBoundFTC.endpointRaw :=
  endpointScheduleAgreement_of_derivativeBoundFTC_stageSchedule
    h.toDerivativeBoundFTC hendpoint sigma hsigma

/-- Curvature endpoint-schedule agreement, by conversion to the
derivative-bound FTC certificate. -/
theorem endpointScheduleAgreement_of_curvatureFTC_stageSchedule
    {F dF : RealFunRaw} {a b : Rat}
    (h : CurvatureFTCCertificate F dF a b)
    (hendpoint : RealCompute.ValidCompute (endpointDifferenceCompute F a b))
    (sigma : RealCompute.StageSchedule)
    (hsigma :
      forall n,
        h.toDerivativeBoundFTC.chooseEndpointPrecision (precisionAtStage n) =
          sigma.stage n) :
    EndpointScheduleAgreement F a b h.toDerivativeBoundFTC.endpointRaw :=
  endpointScheduleAgreement_of_derivativeBoundFTC_stageSchedule
    h.toDerivativeBoundFTC hendpoint sigma hsigma

/-- Convex endpoint-schedule agreement, by conversion to the derivative-bound
FTC certificate. -/
theorem endpointScheduleAgreement_of_convexFTC_stageSchedule
    {F dF : RealFunRaw} {a b : Rat}
    (h : ConvexFTCCertificate F dF a b)
    (hendpoint : RealCompute.ValidCompute (endpointDifferenceCompute F a b))
    (sigma : RealCompute.StageSchedule)
    (hsigma :
      forall n,
        h.toDerivativeBoundFTC.chooseEndpointPrecision (precisionAtStage n) =
          sigma.stage n) :
    EndpointScheduleAgreement F a b h.toDerivativeBoundFTC.endpointRaw :=
  endpointScheduleAgreement_of_derivativeBoundFTC_stageSchedule
    h.toDerivativeBoundFTC hendpoint sigma hsigma

/-- Concave endpoint-schedule agreement, by conversion to the derivative-bound
FTC certificate. -/
theorem endpointScheduleAgreement_of_concaveFTC_stageSchedule
    {F dF : RealFunRaw} {a b : Rat}
    (h : ConcaveFTCCertificate F dF a b)
    (hendpoint : RealCompute.ValidCompute (endpointDifferenceCompute F a b))
    (sigma : RealCompute.StageSchedule)
    (hsigma :
      forall n,
        h.toDerivativeBoundFTC.chooseEndpointPrecision (precisionAtStage n) =
          sigma.stage n) :
    EndpointScheduleAgreement F a b h.toDerivativeBoundFTC.endpointRaw :=
  endpointScheduleAgreement_of_derivativeBoundFTC_stageSchedule
    h.toDerivativeBoundFTC hendpoint sigma hsigma

def integralPlanOfEffectiveFTC
    {F dF : RealFunRaw} {a b : Rat}
    (h : EffectiveFTC F dF a b) : Nat -> Integral.Plan :=
  fun n =>
    let eps := requestedPrecision n
    { subdivisions := h.chooseN eps,
      evalPrecision := h.chooseEvalPrecision eps }

def integralPlanOfStaticDyadicEffectiveFTC
    {F dF : RealFunRaw} {a b : Rat}
    (h : StaticDyadicEffectiveFTC F dF a b) : Nat -> Integral.Plan :=
  fun n =>
    let eps := requestedPrecision n
    { subdivisions := Integral.staticDyadicSubdivisions (h.chooseStage eps),
      evalPrecision := h.chooseEvalPrecision eps }

theorem integralPlanOfStaticDyadicEffectiveFTC_eq_toEffectiveFTC
    {F dF : RealFunRaw} {a b : Rat}
    (h : StaticDyadicEffectiveFTC F dF a b) :
    integralPlanOfStaticDyadicEffectiveFTC h =
      integralPlanOfEffectiveFTC h.toEffectiveFTC := by
  funext n
  simp [integralPlanOfStaticDyadicEffectiveFTC, integralPlanOfEffectiveFTC,
    StaticDyadicEffectiveFTC.toEffectiveFTC]

theorem riemannComputeOfEffectiveFTC_eq_integralPlan
    {F dF : RealFunRaw} {a b : Rat}
    (h : EffectiveFTC F dF a b) (n : Nat) :
    riemannComputeOfEffectiveFTC h n =
      riemannLeftInterval dF a b
        ((integralPlanOfEffectiveFTC h n).subdivisions)
        ((integralPlanOfEffectiveFTC h n).evalPrecision) := by
  simp [riemannComputeOfEffectiveFTC, integralPlanOfEffectiveFTC]

theorem integral_compute_eq_riemannComputeOfEffectiveFTC
    {F dF : RealFunRaw} {a b : Rat}
    (h : EffectiveFTC F dF a b)
    (c : Integral.SampleConstruction dF a b)
    (hplan : c.plan = integralPlanOfEffectiveFTC h) :
    (Integral.sampleValue dF a b c).compute =
      riemannComputeOfEffectiveFTC h := by
  funext n
  simp [Integral.sampleValue, Integral.Certificate.realCompute,
    Integral.Raw.toRealCompute, Integral.Raw.compute, Integral.algorithm,
    riemannComputeOfEffectiveFTC, integralPlanOfEffectiveFTC, hplan]

theorem integral_valid_of_construction
    {f : RealFunRaw} {a b : Rat}
    (c : Integral.SampleConstruction f a b) :
    (Integral.sampleValue f a b c).Valid := by
  have hv := c.certificate.valid
  change RealCompute.ValidCompute (Integral.algorithm f a b c.plan).compute at hv
  exact hv

/-- General effective FTC, in computable-real form.

An `EffectiveFTC` certificate already says that, for every rational precision,
some finite Riemann sum for `dF` is close to the endpoint difference
`F(b)-F(a)`.  This theorem packages that certificate as equivalence of two
raw real algorithms: the scheduled Riemann sums and the scheduled endpoint
differences overlap at every requested stage. -/
theorem effectiveFTC_equiv_endpoint
    {F dF : RealFunRaw} {a b : Rat}
    (h : EffectiveFTC F dF a b) :
    (riemannRawOfEffectiveFTC h).Equiv (endpointRawOfEffectiveFTC h) := by
  apply RealCompute.sameStageOverlap_equiv
  intro n
  have hgood := h.good (requestedPrecision n)
  exact (RealCompute.compareAt_overlap_iff
    (riemannRawOfEffectiveFTC h) (endpointRawOfEffectiveFTC h) n n).2 hgood.1

/-! A scheduled FTC need not produce nested boxes at its public stage index.
The following adapter makes the finite Riemann computation into a valid raw
real by prefix-stabilizing it against the canonical endpoint difference. -/

theorem effectiveFTC_riemannRaw_equiv_endpointDifference_of_endpointAgreement
    {F dF : RealFunRaw} {a b : Rat}
    (h : EffectiveFTC F dF a b)
    (hriemann : (riemannRawOfEffectiveFTC h).Valid)
    (agreement : EndpointScheduleAgreement F a b
      (endpointRawOfEffectiveFTC h)) :
    (riemannRawOfEffectiveFTC h).Equiv
      (endpointDifferenceRaw F a b agreement.endpoint_valid) := by
  exact RealCompute.equiv_trans hriemann agreement.scheduled_valid
    (by simpa [endpointDifferenceRaw, RealCompute.Valid] using agreement.endpoint_valid)
    (effectiveFTC_equiv_endpoint h) agreement.equivalent

def effectiveFTCStabilizedRaw
    {F dF : RealFunRaw} {a b : Rat}
    (h : EffectiveFTC F dF a b)
    (radius : Nat -> Rat) : RealCompute :=
  RealCompute.prefixStabilize (riemannRawOfEffectiveFTC h) radius

theorem effectiveFTCStabilizedRaw_valid
    {F dF : RealFunRaw} {a b : Rat}
    (h : EffectiveFTC F dF a b)
    (hriemann : (riemannRawOfEffectiveFTC h).Valid)
    (agreement : EndpointScheduleAgreement F a b
      (endpointRawOfEffectiveFTC h))
    (radius : Nat -> Rat)
    (hwidth : RealCompute.WidthsShrinkToZero
      (riemannRawOfEffectiveFTC h).compute)
    (hradius : forall n,
      ((endpointDifferenceRaw F a b agreement.endpoint_valid).compute n).width
        <= radius n)
    (hradius_shrinks : ShrinksToZero radius) :
    (effectiveFTCStabilizedRaw h radius).Valid := by
  unfold effectiveFTCStabilizedRaw
  apply RealCompute.prefixStabilize_valid
    (candidate := riemannRawOfEffectiveFTC h)
    (anchor := endpointDifferenceRaw F a b agreement.endpoint_valid)
    (radius := radius)
  · exact hwidth
  · simpa [endpointDifferenceRaw, RealCompute.Valid] using agreement.endpoint_valid
  · exact effectiveFTC_riemannRaw_equiv_endpointDifference_of_endpointAgreement
      h hriemann agreement
  · exact hradius
  · exact hradius_shrinks

theorem effectiveFTCStabilizedRaw_equiv_endpointDifference
    {F dF : RealFunRaw} {a b : Rat}
    (h : EffectiveFTC F dF a b)
    (hriemann : (riemannRawOfEffectiveFTC h).Valid)
    (agreement : EndpointScheduleAgreement F a b
      (endpointRawOfEffectiveFTC h))
    (radius : Nat -> Rat)
    (hradius : forall n,
      ((endpointDifferenceRaw F a b agreement.endpoint_valid).compute n).width
        <= radius n) :
    (effectiveFTCStabilizedRaw h radius).Equiv
      (endpointDifferenceRaw F a b agreement.endpoint_valid) := by
  unfold effectiveFTCStabilizedRaw
  apply RealCompute.prefixStabilize_equiv_anchor
    (candidate := riemannRawOfEffectiveFTC h)
    (anchor := endpointDifferenceRaw F a b agreement.endpoint_valid)
    (radius := radius)
  · simpa [endpointDifferenceRaw, RealCompute.Valid] using agreement.endpoint_valid
  · exact effectiveFTC_riemannRaw_equiv_endpointDifference_of_endpointAgreement
      h hriemann agreement
  · exact hradius

/-- FTC bridge for a chosen integral construction.

If the integral construction uses exactly the Riemann-sum plan supplied by an
`EffectiveFTC` certificate, then the constructed integral is equivalent to the
scheduled endpoint-difference raw algorithm from that certificate.  This is the
main reusable form for later equivalence proofs: the analytic work is isolated
in the `EffectiveFTC` certificate, while the integral side only has to expose
the same finite-stage schedule. -/
theorem effectiveFTC_integral_equiv_scheduledEndpoint
    {F dF : RealFunRaw} {a b : Rat}
    (h : EffectiveFTC F dF a b)
    (c : Integral.SampleConstruction dF a b)
    (hplan : c.plan = integralPlanOfEffectiveFTC h) :
    (Integral.sampleValue dF a b c).Equiv (endpointRawOfEffectiveFTC h) := by
  apply RealCompute.sameStageOverlap_equiv
  intro n
  have hgood := h.good (requestedPrecision n)
  apply (RealCompute.compareAt_overlap_iff
    (Integral.sampleValue dF a b c) (endpointRawOfEffectiveFTC h) n n).2
  rw [integral_compute_eq_riemannComputeOfEffectiveFTC h c hplan]
  exact hgood.1

/-- Static-dyadic effective FTC, in computable-real form. -/
theorem staticDyadicEffectiveFTC_equiv_endpoint
    {F dF : RealFunRaw} {a b : Rat}
    (h : StaticDyadicEffectiveFTC F dF a b) :
    (riemannRawOfEffectiveFTC h.toEffectiveFTC).Equiv
      (endpointRawOfEffectiveFTC h.toEffectiveFTC) :=
  effectiveFTC_equiv_endpoint h.toEffectiveFTC

/-- FTC bridge for a construction using the static dyadic schedule. -/
theorem staticDyadicEffectiveFTC_integral_equiv_scheduledEndpoint
    {F dF : RealFunRaw} {a b : Rat}
    (h : StaticDyadicEffectiveFTC F dF a b)
    (c : Integral.SampleConstruction dF a b)
    (hplan : c.plan = integralPlanOfStaticDyadicEffectiveFTC h) :
    (Integral.sampleValue dF a b c).Equiv
      (endpointRawOfEffectiveFTC h.toEffectiveFTC) := by
  apply effectiveFTC_integral_equiv_scheduledEndpoint h.toEffectiveFTC c
  rw [← integralPlanOfStaticDyadicEffectiveFTC_eq_toEffectiveFTC h]
  exact hplan

/-- Transport the scheduled FTC bridge to the canonical endpoint-difference
algorithm when that endpoint schedule has separately been proved equivalent to
the canonical endpoint computation.

This theorem is intentionally split from `effectiveFTC_integral_equiv_scheduledEndpoint`:
cofinality or monotonicity of the endpoint precision schedule is representation
specific, so later files can prove it in the form most convenient for the
function `F`. -/
theorem effectiveFTC_definiteIntegralEqualsEndpoint
    {F dF : RealFunRaw} {a b : Rat}
    (h : EffectiveFTC F dF a b)
    (c : Integral.SampleConstruction dF a b)
    (hendpoint : RealCompute.ValidCompute (endpointDifferenceCompute F a b))
    (hplan : c.plan = integralPlanOfEffectiveFTC h)
    (hscheduledEndpoint : (endpointRawOfEffectiveFTC h).Valid)
    (hendpoint_equiv :
      (endpointRawOfEffectiveFTC h).Equiv
        (endpointDifferenceRaw F a b hendpoint)) :
    CandidateEqualsEndpointDifference F dF a b c hendpoint := by
  exact RealCompute.equiv_trans
    (integral_valid_of_construction c)
    hscheduledEndpoint
    hendpoint
    (effectiveFTC_integral_equiv_scheduledEndpoint h c hplan)
    hendpoint_equiv

/-- Definite-integral FTC bridge using the packaged endpoint-schedule
agreement. -/
theorem effectiveFTC_definiteIntegralEqualsEndpoint_of_endpointAgreement
    {F dF : RealFunRaw} {a b : Rat}
    (h : EffectiveFTC F dF a b)
    (c : Integral.SampleConstruction dF a b)
    (hplan : c.plan = integralPlanOfEffectiveFTC h)
    (endpoint :
      EndpointScheduleAgreement F a b (endpointRawOfEffectiveFTC h)) :
    CandidateEqualsEndpointDifference
      F dF a b c endpoint.endpoint_valid :=
  effectiveFTC_definiteIntegralEqualsEndpoint
    h c endpoint.endpoint_valid hplan
    endpoint.scheduled_valid endpoint.equivalent

/--
Transport the effective FTC certificate directly from an explicit endpoint
stage schedule to the canonical endpoint-difference computation.

The schedule equality is a finite implementation certificate: at each
requested stage it identifies the precision selected by `h` with the stage
used by `sigma`.  This composes that transport with the existing Riemann-plan
bridge, so callers need not manually unpack an `EndpointScheduleAgreement`.
-/
theorem effectiveFTC_definiteIntegralEqualsEndpoint_of_stageSchedule
    {F dF : RealFunRaw} {a b : Rat}
    (h : EffectiveFTC F dF a b)
    (c : Integral.SampleConstruction dF a b)
    (hendpoint : RealCompute.ValidCompute (endpointDifferenceCompute F a b))
    (hplan : c.plan = integralPlanOfEffectiveFTC h)
    (sigma : RealCompute.StageSchedule)
    (hsigma :
      forall n, h.chooseEvalPrecision (requestedPrecision n) = sigma.stage n) :
    CandidateEqualsEndpointDifference F dF a b c hendpoint := by
  exact effectiveFTC_definiteIntegralEqualsEndpoint_of_endpointAgreement
    h c hplan
    (endpointScheduleAgreement_of_effectiveFTC_stageSchedule
      h hendpoint sigma hsigma)

/-- Static-dyadic specialization of the definite-integral FTC bridge. -/
theorem staticDyadicEffectiveFTC_definiteIntegralEqualsEndpoint
    {F dF : RealFunRaw} {a b : Rat}
    (h : StaticDyadicEffectiveFTC F dF a b)
    (c : Integral.SampleConstruction dF a b)
    (hendpoint : RealCompute.ValidCompute (endpointDifferenceCompute F a b))
    (hplan : c.plan = integralPlanOfStaticDyadicEffectiveFTC h)
    (hscheduledEndpoint : (endpointRawOfEffectiveFTC h.toEffectiveFTC).Valid)
    (hendpoint_equiv :
      (endpointRawOfEffectiveFTC h.toEffectiveFTC).Equiv
        (endpointDifferenceRaw F a b hendpoint)) :
    CandidateEqualsEndpointDifference F dF a b c hendpoint := by
  exact RealCompute.equiv_trans
    (integral_valid_of_construction c)
    hscheduledEndpoint
    hendpoint
    (staticDyadicEffectiveFTC_integral_equiv_scheduledEndpoint h c hplan)
    hendpoint_equiv

/-- Static-dyadic specialization using the packaged endpoint-schedule
agreement. -/
theorem staticDyadicEffectiveFTC_definiteIntegralEqualsEndpoint_of_endpointAgreement
    {F dF : RealFunRaw} {a b : Rat}
    (h : StaticDyadicEffectiveFTC F dF a b)
    (c : Integral.SampleConstruction dF a b)
    (hplan : c.plan = integralPlanOfStaticDyadicEffectiveFTC h)
    (endpoint :
      EndpointScheduleAgreement F a b
        (endpointRawOfEffectiveFTC h.toEffectiveFTC)) :
    CandidateEqualsEndpointDifference
      F dF a b c endpoint.endpoint_valid :=
  staticDyadicEffectiveFTC_definiteIntegralEqualsEndpoint
    h c endpoint.endpoint_valid hplan
    endpoint.scheduled_valid endpoint.equivalent

/-!
## Finite partition endpoint transport

These declarations expose the finite telescoping step at the FTC layer.  A
caller supplies one rational interval box for each cell; the boxes are folded
in `Nat` order and the result is shown to contain the endpoint box for the
whole partition.  The adjacent-interval theorem concatenates two such finite
folds.  No limiting partition, completed real, or completeness principle is
used.
-/

/-- Fold one supplied rational interval box for every cell of a finite
partition.  The zero interval makes the computation total outside the finite
`List.range` that is actually traversed. -/
def finitePartitionEndpointStageSum
    {a b : Rat} (P : RationalPartition a b)
    (cellBox : (k : Nat) -> k < P.pieces -> QInterval) : QInterval :=
  (List.range P.pieces).foldl
    (fun acc k => QInterval.addInterval acc
      (if hk : k < P.pieces then cellBox k hk else { lo := 0, hi := 0 }))
    { lo := 0, hi := 0 }

/-- A finite cellwise endpoint enclosure telescopes to the endpoint enclosure
of the entire rational partition.  `cell_contains` is the only
function-specific obligation; the assembly itself is a reusable finite
certificate. -/
theorem finitePartitionEndpointStageSum_contains
    {F : RealFunRaw} {a b : Rat}
    (P : RationalPartition a b) (prec : Nat)
    (hF : F.Valid)
    (hdomain : forall i, i <= P.pieces -> F.domain (P.point i))
    (cellBox : (k : Nat) -> k < P.pieces -> QInterval)
    (cell_contains : forall k (hk : k < P.pieces),
      (cellBox k hk).ContainsInterval
        (endpointDifferenceInterval F (P.point k) (P.point (k + 1)) prec)) :
    (finitePartitionEndpointStageSum P cellBox).ContainsInterval
      (endpointDifferenceInterval F a b prec) := by
  have hsum : (finitePartitionEndpointStageSum P cellBox).ContainsInterval
      (P.endpointDifferenceSum F prec) := by
    unfold finitePartitionEndpointStageSum
    apply RationalPartition.addInterval_fold_contains (List.range P.pieces)
      (fun k => if hk : k < P.pieces then cellBox k hk else { lo := 0, hi := 0 })
      (P.endpointDifferenceTerm F prec)
      (QInterval.containsInterval_refl _)
    intro k
    unfold RationalPartition.endpointDifferenceTerm
    split
    · exact cell_contains k _
    · exact QInterval.containsInterval_refl _
  exact hsum.trans (by
    simpa [P.left_endpoint, P.right_endpoint] using
      (RationalPartition.endpointDifferenceSum_contains P F prec hF hdomain))

/-- Concatenate two finite partition folds over adjacent rational intervals.
The added boxes first telescope on `[a,b]` and `[b,c]`, then the shared
endpoint box is handled by the finite adjacent-difference certificate. -/
theorem finitePartitionEndpointStageSum_adjacent_contains
    {F : RealFunRaw} {a b c : Rat}
    (left : RationalPartition a b) (right : RationalPartition b c)
    (prec : Nat) (hF : F.Valid)
    (hleft_domain : forall i, i <= left.pieces -> F.domain (left.point i))
    (hright_domain : forall i, i <= right.pieces -> F.domain (right.point i))
    (leftBox : (k : Nat) -> k < left.pieces -> QInterval)
    (rightBox : (k : Nat) -> k < right.pieces -> QInterval)
    (hleft : forall k (hk : k < left.pieces),
      (leftBox k hk).ContainsInterval
        (endpointDifferenceInterval F (left.point k) (left.point (k + 1)) prec))
    (hright : forall k (hk : k < right.pieces),
      (rightBox k hk).ContainsInterval
        (endpointDifferenceInterval F (right.point k) (right.point (k + 1)) prec)) :
    (QInterval.addInterval
      (finitePartitionEndpointStageSum left leftBox)
      (finitePartitionEndpointStageSum right rightBox)).ContainsInterval
        (endpointDifferenceInterval F a c prec) := by
  have hleft_sum := finitePartitionEndpointStageSum_contains left prec hF
    hleft_domain leftBox hleft
  have hright_sum := finitePartitionEndpointStageSum_contains right prec hF
    hright_domain rightBox hright
  have hleft' : (finitePartitionEndpointStageSum left leftBox).ContainsInterval
      (endpointDifferenceInterval F a b prec) := by
    simpa [left.left_endpoint, left.right_endpoint] using hleft_sum
  have hright' : (finitePartitionEndpointStageSum right rightBox).ContainsInterval
      (endpointDifferenceInterval F b c prec) := by
    simpa [right.left_endpoint, right.right_endpoint] using hright_sum
  have hadd := QInterval.addInterval_contains hleft' hright'
  have hmiddle : 0 <= (F.compute b prec).width := by
    have hb : F.domain b := by
      simpa [left.right_endpoint] using
        (hleft_domain left.pieces (Nat.le_refl left.pieces))
    exact (hF b hb).1 prec
  exact hadd.trans (endpointDifferenceInterval_adjacent_additive_contains
    (F := F) (a := a) (b := b) (c := c) (prec := prec) hmiddle)

end FTC

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