Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Computable analysis · EulerLegacySeries · fd889115 k1

Definition
liuyao_ca_fd889115_k1_Analysis_EulerLegacySeries

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

ca-fd889115-k1

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

Definition code
import Definitions.Def_liuyao_ca_fd889115_k1_Analysis_EulerSeriesIdentity
import Definitions.Def_liuyao_ca_fd889115_k1_Analysis_Exp

set_option autoImplicit true

/-! Exact comparison with the existing adaptive factorial-tail evaluator.
Only its finite loop is used; no legacy analytic certificate is assumed. -/
namespace ComputableAnalysis.EulerLegacySeries
open EulerSeriesFinite EulerSeriesIdentity EulerPowerLimit EulerReal
open RationalMajorant ComputableCoefficient RealApproximationOrder RawLimit
set_option maxHeartbeats 2500000

private def powerSeriesLoopStep (x : Rat) (s : Rat × Rat)
    (k : Nat) : Rat × Rat :=
  (s.1 + s.2, s.2 * x / ((k : Rat) + 1))

private def powerSeriesLoopPairFrom (x : Rat) (xs : List Nat)
    (sum term : Rat) : Rat × Rat :=
  Id.run do
    let mut sum : Rat := sum
    let mut term : Rat := term
    for k in xs do
      sum := sum + term
      term := term * x / ((k + 1 : Nat) : Rat)
    return (sum, term)

private def powerSeriesLoopPair (x : Rat) (xs : List Nat) :
    Rat × Rat :=
  powerSeriesLoopPairFrom x xs 0 1

private theorem powerSeriesLoopPairFrom_eq_foldl
    (x : Rat) (xs : List Nat) (sum term : Rat) :
    powerSeriesLoopPairFrom x xs sum term =
      xs.foldl (powerSeriesLoopStep x) (sum, term) := by
  induction xs generalizing sum term with
  | nil => rfl
  | cons k ks ih =>
      calc
        powerSeriesLoopPairFrom x (k :: ks) sum term =
            powerSeriesLoopPairFrom x ks
              (sum + term) (term * x / ((k : Rat) + 1)) := by
          simp [powerSeriesLoopPairFrom]
        _ = ks.foldl (powerSeriesLoopStep x)
            (sum + term, term * x / ((k : Rat) + 1)) := by
          exact ih (sum + term) (term * x / ((k : Rat) + 1))
        _ = (k :: ks).foldl (powerSeriesLoopStep x) (sum, term) := by
          rfl

private theorem powerSeriesLoopPair_eq_foldl
    (x : Rat) (xs : List Nat) :
    powerSeriesLoopPair x xs =
      xs.foldl (powerSeriesLoopStep x) (0, 1) := by
  unfold powerSeriesLoopPair
  exact powerSeriesLoopPairFrom_eq_foldl x xs 0 1

private def powerSeriesState (x : Rat) (N : Nat) : Rat × Rat :=
  (List.range N).foldl (powerSeriesLoopStep x) (0, 1)

private theorem powerSeriesState_succ (x : Rat) (N : Nat) :
    powerSeriesState x (N + 1) =
      powerSeriesLoopStep x (powerSeriesState x N) N := by
  unfold powerSeriesState
  rw [List.range_succ, List.foldl_append]
  rfl


theorem term_succ (q : Rat) (k : Nat) : term q (k+1)=term q k*q/((k+1:Nat):Rat) := by
  simp only [term,FormalPowerSeries.factorialRat_succ,Rat.pow_succ,Rat.div_def,Rat.inv_mul_rev]
  grind only

theorem state_term (q : Rat) (k : Nat) : (powerSeriesState q k).2=term q k := by
  induction k with
  | zero => change 1=q^0/factorialRat 0; simp only [Rat.pow_zero,factorialRat,factorial]; decide +kernel
  | succ k ih =>
    rw [powerSeriesState_succ]
    simp only [powerSeriesLoopStep,term_succ,ih]
    congr 1
    rw [Rat.natCast_add]
    rfl

theorem state_center (q : Rat) (k : Nat) : (powerSeriesState q k).1=factorialPrefix q k := by
  induction k with
  | zero => rfl
  | succ k ih => rw [powerSeriesState_succ]; simp only [powerSeriesLoopStep,ih,state_term,factorialPrefix]

theorem adaptive_compute (q : Rat) (n : Nat) :
    (expPowerSeries q).compute n=
      {lo := factorialPrefix q (expPowerSeriesTerms q n)-
        qabs (term q (expPowerSeriesTerms q n))/(1-expPowerSeriesTailRatioBound q n),
       hi := factorialPrefix q (expPowerSeriesTerms q n)+
        qabs (term q (expPowerSeriesTerms q n))/(1-expPowerSeriesTailRatioBound q n)} := by
  have H : expPowerSeriesPartialAndTailBound q n=
      ((powerSeriesState q (expPowerSeriesTerms q n)).1,
        qabs (powerSeriesState q (expPowerSeriesTerms q n)).2/(1-expPowerSeriesTailRatioBound q n)) := by
    change ((powerSeriesLoopPair q (List.range (expPowerSeriesTerms q n))).1,
      qabs (powerSeriesLoopPair q (List.range (expPowerSeriesTerms q n))).2/(1-expPowerSeriesTailRatioBound q n))=_
    rw [powerSeriesLoopPair_eq_foldl]
    rfl
  simp only [expPowerSeries,H,state_center,state_term]

theorem ratio_properties (q : Rat) (n : Nat) :
    0≤expPowerSeriesTailRatioBound q n ∧ expPowerSeriesTailRatioBound q n≤1/2 := by
  have HQ := qabs_le_numNatAbs_succ q
  have HT : 2*(q.num.natAbs+1)≤expPowerSeriesTerms q n+1 := by unfold expPowerSeriesTerms; omega
  have HTr : 2*((q.num.natAbs+1:Nat):Rat)≤((expPowerSeriesTerms q n+1:Nat):Rat) := by exact_mod_cast HT
  have HD : 0<((expPowerSeriesTerms q n+1:Nat):Rat) := Rat.natCast_pos.mpr (Nat.succ_pos _)
  have HI := Rat.inv_pos.mpr HD
  have HC := Rat.mul_inv_cancel ((expPowerSeriesTerms q n+1:Nat):Rat) (Rat.ne_of_gt HD)
  have H := Rat.mul_le_mul_of_nonneg_right HTr (Rat.le_of_lt HI)
  have Hq := Rat.mul_le_mul_of_nonneg_right HQ (Rat.le_of_lt HI)
  exact ⟨Rat.mul_nonneg (qabs_nonneg q) (Rat.le_of_lt HI),by dsimp [expPowerSeriesTailRatioBound]; grind only [Rat.div_def]⟩

def center (q : Rat) (n : Nat) : Rat := factorialPrefix q (expPowerSeriesTerms q n)
def radius (q : Rat) (n : Nat) : Rat :=
  qabs (term q (expPowerSeriesTerms q n))/(1-expPowerSeriesTailRatioBound q n)

theorem compute_eq (q : Rat) (n : Nat) :
    (expPowerSeries q).compute n={lo := center q n-radius q n,hi := center q n+radius q n} := adaptive_compute q n

theorem radius_nonnegative (q : Rat) (n : Nat) : 0≤radius q n := by
  have H := (ratio_properties q n).2
  exact Rat.mul_nonneg (qabs_nonneg _) (Rat.le_of_lt (Rat.inv_pos.mpr (by grind only)))

theorem terms_succ (q : Rat) (n : Nat) : expPowerSeriesTerms q (n+1)=expPowerSeriesTerms q n+1 := by
  unfold expPowerSeriesTerms; omega

theorem ratio_antitone (q : Rat) (n : Nat) :
    expPowerSeriesTailRatioBound q (n+1)≤expPowerSeriesTailRatioBound q n := by
  unfold expPowerSeriesTailRatioBound
  rw [terms_succ]
  apply Rat.mul_le_mul_of_nonneg_left _ (qabs_nonneg q)
  apply EulerFinite.inv_antitone
  · exact Rat.natCast_pos.mpr (Nat.succ_pos _)
  · exact_mod_cast (show expPowerSeriesTerms q n+1≤expPowerSeriesTerms q n+1+1 by omega)

theorem abs_term_succ (q : Rat) (k : Nat) :
    qabs (term q (k+1))=qabs (term q k)*(qabs q/((k+1:Nat):Rat)) := by
  rw [term_succ,Rat.div_def,qabs_mul,qabs_mul]
  rw [qabs_eq_self_of_nonneg (Rat.le_of_lt (Rat.inv_pos.mpr (Rat.natCast_pos.mpr (Nat.succ_pos k))))]
  grind only [Rat.div_def]

theorem radius_step (q : Rat) (n : Nat) :
    radius q (n+1)+qabs (term q (expPowerSeriesTerms q n))≤radius q n := by
  have HR := ratio_antitone q n
  have ⟨hr0,hr⟩ := ratio_properties q n
  have hs := (ratio_properties q (n+1)).2
  have HD : 0<1-expPowerSeriesTailRatioBound q n := by grind only
  have HD' : 0<1-expPowerSeriesTailRatioBound q (n+1) := by grind only
  have HI := EulerFinite.inv_antitone HD (by grind only :
    1-expPowerSeriesTailRatioBound q n≤1-expPowerSeriesTailRatioBound q (n+1))
  have HA := qabs_nonneg (term q (expPowerSeriesTerms q n))
  have HP := Rat.mul_nonneg HA hr0
  have H := Rat.mul_le_mul_of_nonneg_left HI HP
  have HC := Rat.mul_inv_cancel (1-expPowerSeriesTailRatioBound q n) (Rat.ne_of_gt HD)
  have HCscaled := congrArg (fun v : Rat => qabs (term q (expPowerSeriesTerms q n))*v) HC
  unfold radius
  rw [terms_succ,abs_term_succ]
  change qabs (term q (expPowerSeriesTerms q n))*expPowerSeriesTailRatioBound q n/
    (1-expPowerSeriesTailRatioBound q (n+1))+qabs (term q (expPowerSeriesTerms q n))≤_
  grind only [Rat.div_def]

theorem adaptive_nested (q : Rat) {n m : Nat} (hnm : n≤m) :
    ((expPowerSeries q).compute n).lo≤((expPowerSeries q).compute m).lo ∧
    ((expPowerSeries q).compute m).hi≤((expPowerSeries q).compute n).hi := by
  induction hnm with
  | refl => exact ⟨Rat.le_refl,Rat.le_refl⟩
  | @step m hnm ih =>
    have H := radius_step q m
    have HL := neg_qabs_le_self (term q (expPowerSeriesTerms q m))
    have HU := self_le_qabs (term q (expPowerSeriesTerms q m))
    have HC : center q (m+1)=center q m+term q (expPowerSeriesTerms q m) := by
      unfold center; rw [terms_succ,factorialPrefix]
    rw [compute_eq q n,compute_eq q m] at ih
    rw [compute_eq q n,compute_eq q (m+1)]
    simp only at ih ⊢
    constructor <;> grind only

theorem abs_stage_geometric (q : Rat) (n : Nat) :
    qabs (term q (expPowerSeriesTerms q n))≤qabs (term q (expPowerSeriesTerms q 0))*((1:Rat)/2)^n := by
  induction n with
  | zero => simp only [Rat.pow_zero,Rat.mul_one,Rat.le_refl]
  | succ n ih =>
    rw [terms_succ,abs_term_succ]
    have H := Rat.mul_le_mul_of_nonneg_left (ratio_properties q n).2 (qabs_nonneg (term q (expPowerSeriesTerms q n)))
    have H' := Rat.mul_le_mul_of_nonneg_right ih (by decide +kernel : (0:Rat)≤1/2)
    rw [Rat.pow_succ]
    exact Rat.le_trans H (by grind only)

theorem radius_le_twice (q : Rat) (n : Nat) :
    radius q n≤2*qabs (term q (expPowerSeriesTerms q n)) := by
  have HR := (ratio_properties q n).2
  have HD : 0<1-expPowerSeriesTailRatioBound q n := by grind only
  have H := EulerFinite.inv_antitone (by decide +kernel : (0:Rat)<1/2)
    (show (1:Rat)/2≤1-expPowerSeriesTailRatioBound q n by grind only)
  have H' := Rat.mul_le_mul_of_nonneg_left H (qabs_nonneg (term q (expPowerSeriesTerms q n)))
  change qabs (term q (expPowerSeriesTerms q n))*(1-expPowerSeriesTailRatioBound q n)⁻¹≤_
  have Htwo : ((1:Rat)/2)⁻¹=2 := by decide +kernel
  rw [Htwo] at H'
  grind only

/-- Kernel-checked validity for the original adaptive series evaluator,
independent of the older native-decision analytic certificate. -/
theorem adaptive_valid (q : Rat) : (expPowerSeries q).Valid := by
  have ordered (n : Nat) : ((expPowerSeries q).compute n).lo≤((expPowerSeries q).compute n).hi := by
    rw [compute_eq]; simp only; have H := radius_nonnegative q n; grind only
  refine ⟨?_,?_,?_⟩
  · intro n; change 0≤_ - _; have H := ordered n; grind only
  · intro n m hnm
    have H := adaptive_nested q hnm
    exact ⟨H.1,ordered m,H.2⟩
  · apply shrinksToZero_of_ratOverSuccBound (C := 4*qabs (term q (expPowerSeriesTerms q 0)))
    intro n
    have H := radius_le_twice q n
    have G := abs_stage_geometric q n
    have T := Rat.mul_le_mul_of_nonneg_left (half_pow_le_one_div_succ n)
      (qabs_nonneg (term q (expPowerSeriesTerms q 0)))
    rw [compute_eq]
    unfold QInterval.width
    dsimp only
    grind only [Rat.div_def]

theorem finite_rational (q : Rat) (k : Nat) :
    (finiteValue (parameter (RealCompute.ofRat q) (RealCompute.ofRat_valid q)) k).real.preferred.Equiv
      (RealCompute.ofRat (factorialPrefix q k)) := by
  apply Value.equiv_of_samples _ (Value.rational (factorialPrefix q k)) 0
  intro m hm s hs
  have HQ := hs (RealCompute.Certified.ofRaw (RealCompute.ofRat q) (RealCompute.ofRat_valid q))
  change q≤(parameter (RealCompute.ofRat q) (RealCompute.ofRat_valid q)).sample s ∧
    (parameter (RealCompute.ofRat q) (RealCompute.ofRat_valid q)).sample s≤q at HQ
  have H : (parameter (RealCompute.ofRat q) (RealCompute.ofRat_valid q)).sample s=q := Rat.le_antisymm HQ.2 HQ.1
  simp only [partial_sample,H,Value.rational]

theorem prefixes_tend_to_euler (q : Rat) :
    TendsTo (fun k => RealCompute.ofRat (factorialPrefix q k)) (sample q) :=
  congr_sequence (exponential_hasSum (x := RealCompute.ofRat q) (RealCompute.ofRat_valid q)) (fun _ => RealCompute.ofRat_valid _)
    (finite_rational q)

/-- A limit of values eventually in a closed rational interval is in that
interval. This uses only the existing represented limit and exact order. -/
theorem limit_in_interval {u : Nat → RealCompute} {x : RealCompute} (h : TendsTo u x) (I : QInterval)
    (hb : ∃ N, ∀ n, N≤n → InInterval (u n) I) : InInterval x I := by
  obtain ⟨K,hK⟩ := hb
  constructor
  · intro i j
    by_cases H : I.lo≤(x.compute j).hi
    · exact H
    have HP : 0<(I.lo-(x.compute j).hi)/2 := by grind only
    obtain ⟨N,hN⟩ := h.2.2 j ⟨_,HP⟩
    let n := max N K
    have HU := RealCompute.le_trans (h.2.1 n) (hK n (by dsimp [n]; omega)).1 (hN n (by dsimp [n]; omega)).2 0 0
    change I.lo≤(x.compute j).hi+(I.lo-(x.compute j).hi)/2 at HU
    grind only
  · intro i j
    by_cases H : (x.compute i).lo≤I.hi
    · exact H
    have HP : 0<((x.compute i).lo-I.hi)/2 := by grind only
    obtain ⟨N,hN⟩ := h.2.2 i ⟨_,HP⟩
    let n := max N K
    have HL := RealCompute.le_trans (h.2.1 n) (hN n (by dsimp [n]; omega)).1 (hK n (by dsimp [n]; omega)).2 0 0
    change (x.compute i).lo-((x.compute i).lo-I.hi)/2≤I.hi at HL
    grind only

theorem adaptive_contains_euler (q : Rat) (i : Nat) :
    InInterval (sample q) ((expPowerSeries q).compute i) := by
  apply limit_in_interval (prefixes_tend_to_euler q)
  refine ⟨expPowerSeriesTerms q i,fun k hk => ?_⟩
  let j := k-expPowerSeriesTerms q 0
  have Hterms : expPowerSeriesTerms q j=k := by dsimp [j,expPowerSeriesTerms] at *; omega
  have Hij : i≤j := by dsimp [j,expPowerSeriesTerms] at *; omega
  have HN := adaptive_nested q Hij
  have HR := radius_nonnegative q j
  rw [compute_eq q j] at HN
  have HC : center q j=factorialPrefix q k := by unfold center; rw [Hterms]
  rw [HC] at HN
  change ((expPowerSeries q).compute i).lo≤factorialPrefix q k-radius q j ∧
    factorialPrefix q k+radius q j≤((expPowerSeries q).compute i).hi at HN
  constructor
  · intro n m
    change ((expPowerSeries q).compute i).lo≤factorialPrefix q k
    grind only
  · intro n m
    change factorialPrefix q k≤((expPowerSeries q).compute i).hi
    grind only

/-- The original adaptive power-series program agrees with the ODE Euler
program at every rational input, with both actual programs proved valid. -/
theorem adaptive_equiv_euler (q : Rat) : (expPowerSeries q).Equiv (sample q) := by
  intro n
  apply (RealCompute.compareAt_overlap_iff _ _ n n).mpr
  have H := adaptive_contains_euler q n
  exact ⟨H.1 0 n,H.2 n 0⟩

/-- The represented factorial-prefix extension is an extension of the
existing primary rational power-series sampler. -/
theorem seriesAt_rational (q : Rat) :
    (seriesAt (RealCompute.ofRat q) (RealCompute.ofRat_valid q)).Equiv (expPowerSeries q) :=
  RealCompute.equiv_trans (seriesAt_valid (x := RealCompute.ofRat q) (RealCompute.ofRat_valid q)) (sample_valid q) (adaptive_valid q)
    (seriesAt_equiv_euler (x := RealCompute.ofRat q) (RealCompute.ofRat_valid q)) (RealCompute.equiv_symm (adaptive_equiv_euler q))

/-- The old display wrapper is not a valid general exponential name. This
counterexample is why the full power-limit theorem uses justified errors. -/
theorem legacy_euler_candidate_not_valid : ¬(expEuler 2).Valid := by
  intro H
  have HS := (H.2.1 0 1 (by decide)).2.2
  have HB : ¬((expEuler 2).compute 1).hi≤((expEuler 2).compute 0).hi := by decide +kernel
  exact HB HS

end ComputableAnalysis.EulerLegacySeries

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