Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Computable analysis · ComplexExponentialLift · fd889115 k1

Definition
liuyao_ca_fd889115_k1_Analysis_ComplexExponentialLift

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

ca-fd889115-k1

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

Definition code
import Definitions.Def_liuyao_ca_fd889115_k1_Analysis_ComplexPowerCalculus

set_option autoImplicit true

/-!
# Exponential of a bounded represented complex number

This module lifts the rational-complex Taylor evaluator to nested rational
box representations.  At stage `n` it evaluates a finite Taylor prefix at
the center of the input's `n`th box.  A single rational radius budgets both
the movement of that center and the remaining factorial tail; finite-prefix
intersection then produces a valid `ComplexCompute`.
-/

namespace ComputableAnalysis
namespace ComplexExponentialLift

open ComplexExponentialApproximation

namespace QBox

/-- If one ordered rational complex box is nested in another, the distance
between their centers is bounded by the outer coordinate widths. -/
theorem center_sub_center_normBound_le_width_add_height_of_nested
    {outer inner : QBox} (hOuter : outer.Ordered)
    (hInner : inner.Ordered) (hNested : inner.NestedIn outer) :
    QComplex.normBound (QComplex.sub outer.center inner.center) <=
      outer.width + outer.height := by
  have hOuterCenter := QBox.center_mem hOuter
  have hInnerCenter0 := QBox.center_mem hInner
  have hInnerCenter :
      outer.lo <= inner.center /\ inner.center <= outer.hi :=
    ⟨QComplex.le_trans hNested.1 hInnerCenter0.1,
      QComplex.le_trans hInnerCenter0.2 hNested.2⟩
  have hre : qabs (outer.center.re - inner.center.re) <= outer.width :=
    qabs_sub_le_of_common_bounds hOuterCenter.1.1 hOuterCenter.2.1
      hInnerCenter.1.1 hInnerCenter.2.1
  have him : qabs (outer.center.im - inner.center.im) <= outer.height :=
    qabs_sub_le_of_common_bounds hOuterCenter.1.2 hOuterCenter.2.2
      hInnerCenter.1.2 hInnerCenter.2.2
  simpa only [QComplex.normBound, QComplex.sub, QComplex.add, QComplex.neg,
    Rat.sub_eq_add_neg] using rat_add_le_add hre him

end QBox

/-- A represented complex input together with one rational norm ball
containing every sampled center. -/
structure BoundedInput (C : Rat) where
  raw : ComplexCompute
  valid : raw.Valid
  radius_nonneg : 0 <= C
  center_normBound : forall n : Nat,
    QComplex.normBound (raw.compute n).center <= C

namespace BoundedInput

def ofQComplex (z : QComplex) (C : Rat) (hC : 0 <= C)
    (hz : QComplex.normBound z <= C) : BoundedInput C where
  raw := ComplexCompute.ofQComplex z
  valid := ComplexCompute.ofQComplex_valid z
  radius_nonneg := hC
  center_normBound := by
    intro n
    have hcenter : ((ComplexCompute.ofQComplex z).compute n).center = z := by
      cases z
      simp only [ComplexCompute.ofQComplex, QBox.center]
      congr 1 <;>
        rw [Rat.div_def] <;>
        grind [Rat.add_mul, Rat.mul_assoc, Rat.mul_comm,
          Rat.mul_inv_cancel]
    rw [hcenter]
    exact hz

theorem ofQComplex_center (z : QComplex) (C : Rat) (hC : 0 <= C)
    (hz : QComplex.normBound z <= C) (n : Nat) :
    ((ofQComplex z C hC hz).raw.compute n).center = z := by
  cases z
  simp only [ofQComplex, ComplexCompute.ofQComplex, QBox.center]
  congr 1 <;>
    rw [Rat.div_def] <;>
    grind [Rat.add_mul, Rat.mul_assoc, Rat.mul_comm,
      Rat.mul_inv_cancel]

theorem center_sub_normBound_le_width_add_height
    {C : Rat} (A : BoundedInput C) (k n : Nat) (hkn : k <= n) :
    QComplex.normBound
        (QComplex.sub (A.raw.compute n).center
          (A.raw.compute k).center) <=
      (A.raw.compute k).width + (A.raw.compute k).height := by
  have hkordered := ComplexCompute.valid_ordered A.valid k
  have hnordered := ComplexCompute.valid_ordered A.valid n
  have hkcenter := QBox.center_mem hkordered
  have hncenter0 := QBox.center_mem hnordered
  have hnest := ComplexCompute.valid_nestedIn A.valid hkn
  have hncenter :
      (A.raw.compute k).lo <= (A.raw.compute n).center /\
        (A.raw.compute n).center <= (A.raw.compute k).hi :=
    ⟨QComplex.le_trans hnest.1 hncenter0.1,
      QComplex.le_trans hncenter0.2 hnest.2⟩
  have hre :
      qabs ((A.raw.compute n).center.re -
          (A.raw.compute k).center.re) <=
        (A.raw.compute k).hi.re - (A.raw.compute k).lo.re :=
    qabs_sub_le_of_common_bounds hncenter.1.1 hncenter.2.1
      hkcenter.1.1 hkcenter.2.1
  have him :
      qabs ((A.raw.compute n).center.im -
          (A.raw.compute k).center.im) <=
        (A.raw.compute k).hi.im - (A.raw.compute k).lo.im :=
    qabs_sub_le_of_common_bounds hncenter.1.2 hncenter.2.2
      hkcenter.1.2 hkcenter.2.2
  simpa only [QComplex.normBound, QComplex.sub, QComplex.add, QComplex.neg,
    QBox.width, QBox.height, Rat.sub_eq_add_neg] using rat_add_le_add hre him

/-- The Taylor degree sampled at a represented-input stage. -/
def terms (C : Rat) (stage : Nat) : Nat :=
  RationalMajorant.factorialTailStart C + stage

/-- Direct point-valued Taylor candidates at moving rational centers. -/
def candidate {C : Rat} (A : BoundedInput C) : ComplexCompute where
  compute := fun stage => QBox.point
    (expPrefix (A.raw.compute stage).center (terms C stage))

@[simp] theorem candidate_center {C : Rat} (A : BoundedInput C)
    (stage : Nat) :
    ((candidate A).compute stage).center =
      expPrefix (A.raw.compute stage).center (terms C stage) := by
  let z := expPrefix (A.raw.compute stage).center (terms C stage)
  change (QBox.point z).center = z
  cases z
  simp only [QBox.point, QBox.center]
  congr 1 <;>
        rw [Rat.div_def] <;>
        grind [Rat.add_mul, Rat.mul_assoc, Rat.mul_comm,
          Rat.mul_inv_cancel]

/-- Every moving Taylor candidate has a computable norm bound depending
only on the declared input ball.  The deliberately coarse `1` covers both
the empty prefix and the constant term; the remaining displacement from
zero is controlled by the common derivative majorant. -/
theorem candidate_center_normBound_le
    {C : Rat} (A : BoundedInput C) (stage : Nat) :
    QComplex.normBound ((candidate A).compute stage).center <=
      1 + derivativeMajorant C * C := by
  let z := (A.raw.compute stage).center
  let p := expPrefix z (terms C stage)
  let p0 := expPrefix QComplex.zero (terms C stage)
  have hzeroNorm : QComplex.normBound QComplex.zero <= C := by
    rw [QComplex.normBound_zero]
    exact A.radius_nonneg
  have hdiff := expPrefix_difference_normBound_le_uniform
    A.radius_nonneg (A.center_normBound stage) hzeroNorm (terms C stage)
  have hzdist : QComplex.normBound (QComplex.sub z QComplex.zero) <= C := by
    have hsub : QComplex.sub z QComplex.zero = z := by
      cases z
      simp [QComplex.sub, QComplex.add, QComplex.neg, QComplex.zero]
      constructor <;> grind
    rw [hsub]
    exact A.center_normBound stage
  have hdiff' : QComplex.normBound (QComplex.sub p p0) <=
      derivativeMajorant C * C :=
    Rat.le_trans (by simpa [p, p0, z] using hdiff)
      (Rat.mul_le_mul_of_nonneg_left hzdist
        (derivativeMajorant_nonneg A.radius_nonneg))
  have hp0 : QComplex.normBound p0 <= 1 := by
    have hterm : forall k : Nat,
        term QComplex.zero (k + 1) = QComplex.zero := by
      intro k
      simp [term, ComplexSeries.expTerm, QComplex.pow, QComplex.divRat,
        QComplex.mul, QComplex.zero]
      constructor <;> grind [Rat.div_def]
    have hprefix : forall k : Nat,
        expPrefix QComplex.zero (k + 1) = QComplex.one := by
      intro k
      induction k with
      | zero => decide +kernel
      | succ k ih =>
          rw [expPrefix_succ, ih, hterm]
          decide +kernel
    dsimp [p0]
    cases hterms : terms C stage with
    | zero => decide +kernel
    | succ k =>
        rw [hprefix k]
        decide +kernel
  have hsplit : p = QComplex.add (QComplex.sub p p0) p0 := by
    cases p
    cases p0
    simp [QComplex.add, QComplex.sub, QComplex.neg]
    constructor <;> grind
  rw [candidate_center]
  change QComplex.normBound p <= _
  rw [hsplit]
  exact Rat.le_trans (QComplex.normBound_add_le _ _)
    (by have := rat_add_le_add hdiff' hp0; grind)

/-- Finite input stability for two moving Taylor candidates.  No equivalence
between the represented inputs is required: a supplied rational distance
between their current centers is transported by the explicit prefix
derivative majorant. -/
theorem candidate_center_sub_normBound_le
    {C delta : Rat} (A B : BoundedInput C) (stage : Nat)
    (hdelta : QComplex.normBound
      (QComplex.sub (A.raw.compute stage).center
        (B.raw.compute stage).center) <= delta) :
    QComplex.normBound
      (QComplex.sub ((candidate A).compute stage).center
        ((candidate B).compute stage).center) <=
      derivativeMajorant C * delta := by
  have hprefix := expPrefix_difference_normBound_le_uniform
    A.radius_nonneg (A.center_normBound stage) (B.center_normBound stage)
    (terms C stage)
  have hmajorant : 0 <= derivativeMajorant C :=
    derivativeMajorant_nonneg A.radius_nonneg
  exact Rat.le_trans (by
    simpa only [candidate_center] using hprefix)
    (Rat.mul_le_mul_of_nonneg_left hdelta hmajorant)

/-- A positive Lipschitz coefficient.  The added one avoids a special case
when the exponential-prefix derivative majorant is zero. -/
def inputCoefficient (C : Rat) : Rat := derivativeMajorant C + 1

theorem inputCoefficient_pos {C : Rat} (hC : 0 <= C) :
    0 < inputCoefficient C := by
  have hmajorant := derivativeMajorant_nonneg hC
  unfold inputCoefficient
  grind

/-- The joint input-motion and Taylor-tail budget. -/
def radius {C : Rat} (A : BoundedInput C) (stage : Nat) : Rat :=
  inputCoefficient C *
      ((A.raw.compute stage).width + (A.raw.compute stage).height) +
    stageRadius C stage

theorem candidate_ordered {C : Rat} (A : BoundedInput C) (stage : Nat) :
    ((candidate A).compute stage).Ordered :=
  QComplex.le_refl _

theorem candidate_widths_shrink {C : Rat} (A : BoundedInput C) :
    ComplexCompute.WidthsShrinkToZero (candidate A).compute := by
  intro eps
  refine ⟨0, ?_⟩
  intro stage _
  constructor <;>
    simpa [candidate, QBox.point, QBox.width, QBox.height,
      Rat.sub_self] using (Rat.le_of_lt eps.property)

private theorem add_difference_tail (x y tail : QComplex) :
    QComplex.add y
      (QComplex.add (QComplex.sub x (QComplex.add y tail)) tail) = x := by
  cases x
  cases y
  cases tail
  simp [QComplex.add, QComplex.sub, QComplex.neg]
  constructor <;> grind [Rat.sub_eq_add_neg, Rat.add_assoc, Rat.add_comm]

theorem candidate_future_contained_expand
    {C : Rat} (A : BoundedInput C) (k n : Nat) (hkn : k <= n) :
    ((candidate A).compute n).NestedIn
      (QBox.expand ((candidate A).compute k) (radius A k)) := by
  let extra := n - k
  have hterms : terms C n = terms C k + extra := by
    dsimp [terms, extra]
    omega
  let zn := (A.raw.compute n).center
  let zk := (A.raw.compute k).center
  let tail := tailPartial zk (terms C k) extra
  let movingError := QComplex.sub
    (expPrefix zn (terms C n)) (expPrefix zk (terms C n))
  let error := QComplex.add movingError tail
  have hprefixK :
      expPrefix zk (terms C n) =
        QComplex.add (expPrefix zk (terms C k)) tail := by
    rw [hterms]
    exact expPrefix_add zk (terms C k) extra
  have hvalue :
      expPrefix zn (terms C n) =
        QComplex.add (expPrefix zk (terms C k)) error := by
    dsimp [error, movingError]
    rw [hprefixK]
    exact (add_difference_tail
      (expPrefix zn (terms C n)) (expPrefix zk (terms C k)) tail).symm
  have hcenter := center_sub_normBound_le_width_add_height A k n hkn
  have hmoving : QComplex.normBound movingError <=
      derivativeMajorant C *
        ((A.raw.compute k).width + (A.raw.compute k).height) := by
    dsimp [movingError, zn, zk]
    exact Rat.le_trans
      (expPrefix_difference_normBound_le_uniform A.radius_nonneg
        (A.center_normBound n) (A.center_normBound k) (terms C n))
      (Rat.mul_le_mul_of_nonneg_left hcenter
        (derivativeMajorant_nonneg A.radius_nonneg))
  have htail0 := tailPartial_normBound_le A.radius_nonneg
    (A.center_normBound k) (terms C k) extra
  have htail1 := RationalMajorant.factorialTailPartial_bound
    A.radius_nonneg
    (RationalMajorant.factorialTailStart_mono C
      (RationalMajorant.factorialTailStart C) k
      (RationalMajorant.factorialTailStart_satisfies C)) extra
  have htail : QComplex.normBound tail <= stageRadius C k := by
    exact Rat.le_trans htail0 (by
      simpa [tail, terms, stageRadius] using htail1)
  have hsum0 :
      0 <= (A.raw.compute k).width + (A.raw.compute k).height :=
    Rat.add_nonneg (A.valid.1 k).1 (A.valid.1 k).2
  have hcoefficient :
      derivativeMajorant C <= inputCoefficient C := by
    unfold inputCoefficient
    grind
  have herror : QComplex.normBound error <= radius A k := by
    calc
      QComplex.normBound error <=
          QComplex.normBound movingError + QComplex.normBound tail :=
        QComplex.normBound_add_le _ _
      _ <= derivativeMajorant C *
            ((A.raw.compute k).width + (A.raw.compute k).height) +
          stageRadius C k := rat_add_le_add hmoving htail
      _ <= inputCoefficient C *
            ((A.raw.compute k).width + (A.raw.compute k).height) +
          stageRadius C k :=
        rat_add_le_add
          (Rat.mul_le_mul_of_nonneg_right hcoefficient hsum0) Rat.le_refl
      _ = radius A k := rfl
  change (QBox.point (expPrefix zn (terms C n))).NestedIn
    (QBox.expand (QBox.point (expPrefix zk (terms C k))) (radius A k))
  rw [hvalue]
  exact point_add_error_nested_expand _ _ herror

theorem radius_shrinks {C : Rat} (A : BoundedInput C) :
    ShrinksToZero (radius A) := by
  intro eps
  let K := inputCoefficient C
  have hK : 0 < K := inputCoefficient_pos A.radius_nonneg
  let inputEps : QPos :=
    ⟨eps.val / (4 * K), by
      rw [Rat.div_def]
      exact Rat.mul_pos eps.property ((Rat.inv_pos).2
        (Rat.mul_pos (by decide +kernel) hK))⟩
  let tailEps : QPos :=
    ⟨eps.val / 2, by
      rw [Rat.div_def]
      exact Rat.mul_pos eps.property
        ((Rat.inv_pos).2 (by decide +kernel))⟩
  obtain ⟨Ni, hNi⟩ := A.valid.2.2 inputEps
  obtain ⟨Nt, hNt⟩ := stageRadius_shrinks A.radius_nonneg tailEps
  refine ⟨Nat.max Ni Nt, ?_⟩
  intro n hn
  have hni : Ni <= n := Nat.le_trans (Nat.le_max_left _ _) hn
  have hnt : Nt <= n := Nat.le_trans (Nat.le_max_right _ _) hn
  have hwidths := hNi n hni
  have htail := hNt n hnt
  have hsum :
      (A.raw.compute n).width + (A.raw.compute n).height <=
        2 * inputEps.val := by
    exact Rat.le_trans (rat_add_le_add hwidths.1 hwidths.2) (by
      grind)
  have hK0 : 0 <= K := Rat.le_of_lt hK
  have hinput :
      K * ((A.raw.compute n).width + (A.raw.compute n).height) <=
        eps.val / 2 := by
    calc
      K * ((A.raw.compute n).width + (A.raw.compute n).height) <=
      K * (2 * inputEps.val) :=
        Rat.mul_le_mul_of_nonneg_left hsum hK0
      _ = eps.val / 2 := by
        dsimp [inputEps, K]
        rw [Rat.div_def, Rat.div_def]
        have h4K : (4 : Rat) * inputCoefficient C ≠ 0 :=
          Rat.ne_of_gt (Rat.mul_pos (by decide +kernel)
            (inputCoefficient_pos A.radius_nonneg))
        grind [Rat.mul_add, Rat.add_mul, Rat.mul_assoc, Rat.mul_comm,
          Rat.mul_inv_cancel ((4 : Rat) * inputCoefficient C) h4K,
          Rat.mul_inv_cancel 2 (by decide +kernel : (2 : Rat) ≠ 0)]
  unfold radius
  dsimp [K] at hinput
  exact Rat.le_trans (rat_add_le_add hinput htail) (by
    rw [Rat.div_def]
    grind [Rat.mul_add, Rat.add_assoc, Rat.add_comm,
      Rat.mul_assoc, Rat.mul_comm, Rat.mul_inv_cancel])

/-- Exponential of a bounded represented complex number, computed by finite
Taylor prefixes and finite rational-box intersections. -/
def exponential {C : Rat} (A : BoundedInput C) : ComplexCompute :=
  ComplexCompute.cauchyStabilize (candidate A) (radius A)

theorem exponential_valid {C : Rat} (A : BoundedInput C) :
    (exponential A).Valid := by
  unfold exponential
  exact ComplexCompute.cauchyStabilize_valid
    (candidate_ordered A) (candidate_widths_shrink A)
    (candidate_future_contained_expand A) (radius_shrinks A)

/-- The stabilized represented exponential retains its current exact moving
Taylor candidate. -/
theorem exponential_contains_current_candidate
    {C : Rat} (A : BoundedInput C) (stage : Nat) :
    ((candidate A).compute stage).NestedIn
      ((exponential A).compute stage) := by
  unfold exponential
  exact ComplexCompute.cauchyStabilize_contains_current
    (candidate_future_contained_expand A) stage

/-- The stabilized exponential center differs from its retained exact Taylor
candidate by at most the two coordinate widths of the stabilized box. -/
theorem exponential_center_sub_candidate_center_normBound_le
    {C : Rat} (A : BoundedInput C) (stage : Nat) :
    QComplex.normBound
      (QComplex.sub ((exponential A).compute stage).center
        ((candidate A).compute stage).center) <=
      ((exponential A).compute stage).width +
        ((exponential A).compute stage).height :=
  QBox.center_sub_center_normBound_le_width_add_height_of_nested
    (ComplexCompute.valid_ordered (exponential_valid A) stage)
    (candidate_ordered A stage)
    (exponential_contains_current_candidate A stage)

private theorem normBound_sub_comm (z w : QComplex) :
    QComplex.normBound (QComplex.sub z w) =
      QComplex.normBound (QComplex.sub w z) := by
  cases z with
  | mk zr zi =>
    cases w with
    | mk wr wi =>
      have hre : zr + -wr = -(wr + -zr) := by grind
      have him : zi + -wi = -(wi + -zi) := by grind
      simp only [QComplex.normBound, QComplex.sub, QComplex.add, QComplex.neg]
      rw [hre, him, qabs_neg, qabs_neg]

/-- Stability of the actual stabilized exponential centers for two nearby
finite inputs.  The bound separates the two runtime output widths from the
Taylor-prefix response to the supplied input-center distance. -/
theorem exponential_center_sub_center_normBound_le
    {C delta : Rat} (A B : BoundedInput C) (stage : Nat)
    (hdelta : QComplex.normBound
      (QComplex.sub (A.raw.compute stage).center
        (B.raw.compute stage).center) <= delta) :
    QComplex.normBound
      (QComplex.sub ((exponential A).compute stage).center
        ((exponential B).compute stage).center) <=
      (((exponential A).compute stage).width +
          ((exponential A).compute stage).height) +
        derivativeMajorant C * delta +
      (((exponential B).compute stage).width +
        ((exponential B).compute stage).height) := by
  let ea := ((exponential A).compute stage).center
  let ca := ((candidate A).compute stage).center
  let cb := ((candidate B).compute stage).center
  let eb := ((exponential B).compute stage).center
  have hidentity : QComplex.sub ea eb =
      QComplex.add (QComplex.add (QComplex.sub ea ca)
        (QComplex.sub ca cb)) (QComplex.sub cb eb) := by
    cases ea
    cases ca
    cases cb
    cases eb
    simp only [QComplex.sub, QComplex.add, QComplex.neg]
    congr 1 <;> grind
  have hA := exponential_center_sub_candidate_center_normBound_le A stage
  have hCandidates := candidate_center_sub_normBound_le A B stage hdelta
  have hB0 := exponential_center_sub_candidate_center_normBound_le B stage
  have hB : QComplex.normBound (QComplex.sub cb eb) <=
      ((exponential B).compute stage).width +
        ((exponential B).compute stage).height := by
    rw [normBound_sub_comm]
    exact hB0
  have hleft :
      QComplex.normBound
          (QComplex.add (QComplex.sub ea ca) (QComplex.sub ca cb)) <=
        (((exponential A).compute stage).width +
            ((exponential A).compute stage).height) +
          derivativeMajorant C * delta :=
    Rat.le_trans
      (QComplex.normBound_add_le (QComplex.sub ea ca)
        (QComplex.sub ca cb))
      (rat_add_le_add hA hCandidates)
  rw [hidentity]
  exact Rat.le_trans
    (QComplex.normBound_add_le
      (QComplex.add (QComplex.sub ea ca) (QComplex.sub ca cb))
      (QComplex.sub cb eb))
    (rat_add_le_add hleft hB)

/-! ## Independence of the chosen bounded representative -/

def variation {C : Rat} (A : BoundedInput C) (stage : Nat) : Rat :=
  (A.raw.compute stage).width + (A.raw.compute stage).height

theorem variation_nonneg {C : Rat} (A : BoundedInput C) (stage : Nat) :
    0 <= variation A stage :=
  Rat.add_nonneg (A.valid.1 stage).1 (A.valid.1 stage).2

theorem variation_antitone {C : Rat} (A : BoundedInput C)
    (k n : Nat) (hkn : k <= n) : variation A n <= variation A k := by
  have hnest := ComplexCompute.valid_nestedIn A.valid hkn
  have hwh := QBox.width_height_le_of_nested hnest
  exact rat_add_le_add hwh.1 hwh.2

theorem center_sub_normBound_le_variation_add_of_equiv
    {C : Rat} (A B : BoundedInput C) (hAB : A.raw.Equiv B.raw)
    (m n : Nat) :
    QComplex.normBound
        (QComplex.sub (A.raw.compute m).center
          (B.raw.compute n).center) <=
      variation A m + variation B n := by
  have hAo := ComplexCompute.valid_ordered A.valid m
  have hBo := ComplexCompute.valid_ordered B.valid n
  have hAc := QBox.center_mem hAo
  have hBc := QBox.center_mem hBo
  have hover := (ComplexCompute.compareAt_overlap_iff A.raw B.raw m n).1
    (ComplexCompute.allStagesOverlap_of_equiv A.valid B.valid hAB m n)
  simp only [QComplex.le_def] at hAc hBc
  unfold QBox.Overlaps at hover
  simp only [QComplex.le_def] at hover
  have hre :
      qabs ((A.raw.compute m).center.re -
          (B.raw.compute n).center.re) <=
        (A.raw.compute m).width + (B.raw.compute n).width := by
    apply qabs_le_of_neg_le_le
    · have hupper :
          (B.raw.compute n).center.re - (A.raw.compute m).center.re <=
            (B.raw.compute n).hi.re - (A.raw.compute m).lo.re := by
        grind [Rat.sub_eq_add_neg]
      have hbound :
          (B.raw.compute n).hi.re - (A.raw.compute m).lo.re <=
            (A.raw.compute m).width + (B.raw.compute n).width := by
        unfold QBox.width
        grind [QBox.Overlaps, QComplex.le_def, Rat.sub_eq_add_neg]
      have := Rat.le_trans hupper hbound
      grind [Rat.sub_eq_add_neg]
    · have hupper :
          (A.raw.compute m).center.re - (B.raw.compute n).center.re <=
            (A.raw.compute m).hi.re - (B.raw.compute n).lo.re := by
        grind [Rat.sub_eq_add_neg]
      have hbound :
          (A.raw.compute m).hi.re - (B.raw.compute n).lo.re <=
            (A.raw.compute m).width + (B.raw.compute n).width := by
        unfold QBox.width
        grind [QBox.Overlaps, QComplex.le_def, Rat.sub_eq_add_neg]
      exact Rat.le_trans hupper hbound
  have him :
      qabs ((A.raw.compute m).center.im -
          (B.raw.compute n).center.im) <=
        (A.raw.compute m).height + (B.raw.compute n).height := by
    apply qabs_le_of_neg_le_le
    · have hupper :
          (B.raw.compute n).center.im - (A.raw.compute m).center.im <=
            (B.raw.compute n).hi.im - (A.raw.compute m).lo.im := by
        grind [Rat.sub_eq_add_neg]
      have hbound :
          (B.raw.compute n).hi.im - (A.raw.compute m).lo.im <=
            (A.raw.compute m).height + (B.raw.compute n).height := by
        unfold QBox.height
        grind [QBox.Overlaps, QComplex.le_def, Rat.sub_eq_add_neg]
      have := Rat.le_trans hupper hbound
      grind [Rat.sub_eq_add_neg]
    · have hupper :
          (A.raw.compute m).center.im - (B.raw.compute n).center.im <=
            (A.raw.compute m).hi.im - (B.raw.compute n).lo.im := by
        grind [Rat.sub_eq_add_neg]
      have hbound :
          (A.raw.compute m).hi.im - (B.raw.compute n).lo.im <=
            (A.raw.compute m).height + (B.raw.compute n).height := by
        unfold QBox.height
        grind [QBox.Overlaps, QComplex.le_def, Rat.sub_eq_add_neg]
      exact Rat.le_trans hupper hbound
  have hadd := rat_add_le_add hre him
  simpa only [QComplex.normBound, QComplex.sub, QComplex.add, QComplex.neg,
    Rat.sub_eq_add_neg, variation] using (Rat.le_trans hadd (by grind))

/-- Symmetric radius used to compare two equivalent bounded inputs. -/
def crossRadius {C : Rat} (A B : BoundedInput C) (stage : Nat) : Rat :=
  inputCoefficient C * (variation A stage + variation B stage) +
    stageRadius C stage

theorem radius_le_crossRadius {C : Rat} (A B : BoundedInput C)
    (stage : Nat) : radius A stage <= crossRadius A B stage := by
  have hK := Rat.le_of_lt (inputCoefficient_pos A.radius_nonneg)
  have hB := variation_nonneg B stage
  unfold radius crossRadius
  change inputCoefficient C * variation A stage + stageRadius C stage <=
    inputCoefficient C * (variation A stage + variation B stage) +
      stageRadius C stage
  exact rat_add_le_add
    (Rat.mul_le_mul_of_nonneg_left (by grind) hK) Rat.le_refl

theorem crossRadius_shrinks {C : Rat} (A B : BoundedInput C) :
    ShrinksToZero (crossRadius A B) := by
  intro eps
  let K := inputCoefficient C
  have hK : 0 < K := inputCoefficient_pos A.radius_nonneg
  let inputEps : QPos :=
    ⟨eps.val / (8 * K), by
      rw [Rat.div_def]
      exact Rat.mul_pos eps.property ((Rat.inv_pos).2
        (Rat.mul_pos (by decide +kernel) hK))⟩
  let tailEps : QPos :=
    ⟨eps.val / 2, by
      rw [Rat.div_def]
      exact Rat.mul_pos eps.property
        ((Rat.inv_pos).2 (by decide +kernel))⟩
  obtain ⟨NA, hNA⟩ := A.valid.2.2 inputEps
  obtain ⟨NB, hNB⟩ := B.valid.2.2 inputEps
  obtain ⟨Nt, hNt⟩ := stageRadius_shrinks A.radius_nonneg tailEps
  refine ⟨Nat.max (Nat.max NA NB) Nt, ?_⟩
  intro n hn
  have hnAB : Nat.max NA NB <= n :=
    Nat.le_trans (Nat.le_max_left _ _) hn
  have hnA : NA <= n := Nat.le_trans (Nat.le_max_left _ _) hnAB
  have hnB : NB <= n := Nat.le_trans (Nat.le_max_right _ _) hnAB
  have hnt : Nt <= n := Nat.le_trans (Nat.le_max_right _ _) hn
  have hA := hNA n hnA
  have hB := hNB n hnB
  have ht := hNt n hnt
  have hvariations :
      variation A n + variation B n <= 4 * inputEps.val := by
    unfold variation
    have := rat_add_le_add (rat_add_le_add hA.1 hA.2)
      (rat_add_le_add hB.1 hB.2)
    exact Rat.le_trans this (by grind)
  have hinput :
      K * (variation A n + variation B n) <= eps.val / 2 := by
    calc
      K * (variation A n + variation B n) <= K * (4 * inputEps.val) :=
        Rat.mul_le_mul_of_nonneg_left hvariations (Rat.le_of_lt hK)
      _ = eps.val / 2 := by
        dsimp [inputEps, K]
        rw [Rat.div_def, Rat.div_def]
        have h8K : (8 : Rat) * inputCoefficient C ≠ 0 :=
          Rat.ne_of_gt (Rat.mul_pos (by decide +kernel)
            (inputCoefficient_pos A.radius_nonneg))
        grind [Rat.mul_add, Rat.add_mul, Rat.mul_assoc, Rat.mul_comm,
          Rat.mul_inv_cancel ((8 : Rat) * inputCoefficient C) h8K,
          Rat.mul_inv_cancel 2 (by decide +kernel : (2 : Rat) ≠ 0)]
  unfold crossRadius
  dsimp [K] at hinput
  exact Rat.le_trans (rat_add_le_add hinput ht) (by
    rw [Rat.div_def]
    grind [Rat.mul_add, Rat.add_assoc, Rat.add_comm,
      Rat.mul_assoc, Rat.mul_comm, Rat.mul_inv_cancel])

theorem candidate_future_contained_cross_expand_of_equiv
    {C : Rat} (A B : BoundedInput C) (hAB : A.raw.Equiv B.raw)
    (k n : Nat) (hkn : k <= n) :
    ((candidate A).compute n).NestedIn
      (QBox.expand ((candidate B).compute k) (crossRadius A B k)) := by
  let extra := n - k
  have hterms : terms C n = terms C k + extra := by
    dsimp [terms, extra]
    omega
  let za := (A.raw.compute n).center
  let zb := (B.raw.compute k).center
  let tail := tailPartial zb (terms C k) extra
  let movingError := QComplex.sub
    (expPrefix za (terms C n)) (expPrefix zb (terms C n))
  let error := QComplex.add movingError tail
  have hprefixB :
      expPrefix zb (terms C n) =
        QComplex.add (expPrefix zb (terms C k)) tail := by
    rw [hterms]
    exact expPrefix_add zb (terms C k) extra
  have hvalue :
      expPrefix za (terms C n) =
        QComplex.add (expPrefix zb (terms C k)) error := by
    dsimp [error, movingError]
    rw [hprefixB]
    exact (add_difference_tail
      (expPrefix za (terms C n)) (expPrefix zb (terms C k)) tail).symm
  have hcenter0 :=
    center_sub_normBound_le_variation_add_of_equiv A B hAB n k
  have hcenter : QComplex.normBound (QComplex.sub za zb) <=
      variation A k + variation B k := by
    exact Rat.le_trans hcenter0
      (rat_add_le_add (variation_antitone A k n hkn) Rat.le_refl)
  have hmoving : QComplex.normBound movingError <=
      derivativeMajorant C * (variation A k + variation B k) := by
    dsimp [movingError, za, zb]
    exact Rat.le_trans
      (expPrefix_difference_normBound_le_uniform A.radius_nonneg
        (A.center_normBound n) (B.center_normBound k) (terms C n))
      (Rat.mul_le_mul_of_nonneg_left hcenter
        (derivativeMajorant_nonneg A.radius_nonneg))
  have htail0 := tailPartial_normBound_le A.radius_nonneg
    (B.center_normBound k) (terms C k) extra
  have htail1 := RationalMajorant.factorialTailPartial_bound
    A.radius_nonneg
    (RationalMajorant.factorialTailStart_mono C
      (RationalMajorant.factorialTailStart C) k
      (RationalMajorant.factorialTailStart_satisfies C)) extra
  have htail : QComplex.normBound tail <= stageRadius C k := by
    exact Rat.le_trans htail0 (by
      simpa [tail, terms, stageRadius] using htail1)
  have hvar0 : 0 <= variation A k + variation B k :=
    Rat.add_nonneg (variation_nonneg A k) (variation_nonneg B k)
  have hcoefficient : derivativeMajorant C <= inputCoefficient C := by
    unfold inputCoefficient
    grind
  have herror : QComplex.normBound error <= crossRadius A B k := by
    calc
      QComplex.normBound error <=
          QComplex.normBound movingError + QComplex.normBound tail :=
        QComplex.normBound_add_le _ _
      _ <= derivativeMajorant C * (variation A k + variation B k) +
          stageRadius C k := rat_add_le_add hmoving htail
      _ <= inputCoefficient C * (variation A k + variation B k) +
          stageRadius C k := rat_add_le_add
            (Rat.mul_le_mul_of_nonneg_right hcoefficient hvar0) Rat.le_refl
      _ = crossRadius A B k := rfl
  change (QBox.point (expPrefix za (terms C n))).NestedIn
    (QBox.expand (QBox.point (expPrefix zb (terms C k)))
      (crossRadius A B k))
  rw [hvalue]
  exact point_add_error_nested_expand _ _ herror

def crossExponential {C : Rat} (A B : BoundedInput C) : ComplexCompute :=
  ComplexCompute.cauchyStabilize (candidate A) (crossRadius A B)

theorem crossExponential_valid {C : Rat} (A B : BoundedInput C) :
    (crossExponential A B).Valid := by
  unfold crossExponential
  apply ComplexCompute.cauchyStabilize_valid
  · exact candidate_ordered A
  · exact candidate_widths_shrink A
  · intro k n hkn
    apply QBox.nested_trans (candidate_future_contained_expand A k n hkn)
    exact QBox.expand_mono_radius _ (radius_le_crossRadius A B k)
  · exact crossRadius_shrinks A B

theorem exponential_equiv_crossExponential
    {C : Rat} (A B : BoundedInput C) :
    (exponential A).Equiv (crossExponential A B) := by
  unfold exponential crossExponential
  apply ComplexCompute.cauchyStabilize_equiv_of_common_candidate
  · exact candidate_ordered A
  · exact candidate_future_contained_expand A
  · intro k n hkn
    apply QBox.nested_trans (candidate_future_contained_expand A k n hkn)
    exact QBox.expand_mono_radius _ (radius_le_crossRadius A B k)

theorem crossRadius_comm {C : Rat} (A B : BoundedInput C) (n : Nat) :
    crossRadius A B n = crossRadius B A n := by
  simp [crossRadius, Rat.add_comm]

theorem crossExponential_equiv_of_input_equiv
    {C : Rat} (A B : BoundedInput C) (hAB : A.raw.Equiv B.raw) :
    (crossExponential A B).Equiv (crossExponential B A) := by
  intro n
  apply (ComplexCompute.compareAt_overlap_iff
    (crossExponential A B) (crossExponential B A) n n).2
  have hleft : ((candidate A).compute n).NestedIn
      ((crossExponential A B).compute n) := by
    unfold crossExponential
    apply ComplexCompute.cauchyStabilize_contains_external
      (external := fun m => (candidate A).compute m)
    intro k m hkm
    apply QBox.nested_trans (candidate_future_contained_expand A k m hkm)
    exact QBox.expand_mono_radius _ (radius_le_crossRadius A B k)
    exact Nat.le_refl n
  have hright : ((candidate A).compute n).NestedIn
      ((crossExponential B A).compute n) := by
    unfold crossExponential
    apply ComplexCompute.cauchyStabilize_contains_external
      (external := fun m => (candidate A).compute m)
    intro k m hkm
    simpa [crossRadius_comm] using
      candidate_future_contained_cross_expand_of_equiv A B hAB k m hkm
    exact Nat.le_refl n
  exact ⟨
    QComplex.le_trans hleft.1
      (QComplex.le_trans (candidate_ordered A n) hright.2),
    QComplex.le_trans hright.1
      (QComplex.le_trans (candidate_ordered A n) hleft.2)⟩

/-- The bounded represented exponential respects equivalence of its input
box computations. -/
theorem exponential_equiv_of_input_equiv
    {C : Rat} (A B : BoundedInput C) (hAB : A.raw.Equiv B.raw) :
    (exponential A).Equiv (exponential B) := by
  exact ComplexCompute.equiv_trans
    (exponential_valid A) (crossExponential_valid A B) (exponential_valid B)
    (exponential_equiv_crossExponential A B)
    (ComplexCompute.equiv_trans
      (crossExponential_valid A B) (crossExponential_valid B A)
      (exponential_valid B)
      (crossExponential_equiv_of_input_equiv A B hAB)
      (ComplexCompute.equiv_symm (exponential_equiv_crossExponential B A)))

theorem exponential_ofQComplex_compute_eq
    (z : QComplex) (C : Rat) (hC : 0 <= C)
    (hz : QComplex.normBound z <= C) (n : Nat) :
    (exponential (ofQComplex z C hC hz)).compute n =
      (exponentialRawAt z C).compute n := by
  let A := ofQComplex z C hC hz
  have hcand : forall stage,
      (candidate A).compute stage = (directCandidate z C).compute stage := by
    intro stage
    simp only [candidate, directCandidate, terms]
    rw [show (A.raw.compute stage).center = z by
      exact ofQComplex_center z C hC hz stage]
  have hradius : forall stage, radius A stage = stageRadius C stage := by
    intro stage
    unfold radius
    have hwidth : (A.raw.compute stage).width = 0 := by
      simp only [A, ofQComplex, ComplexCompute.ofQComplex, QBox.width]
      grind
    have hheight : (A.raw.compute stage).height = 0 := by
      simp only [A, ofQComplex, ComplexCompute.ofQComplex, QBox.height]
      grind
    rw [hwidth, hheight, Rat.zero_add, Rat.mul_zero, Rat.zero_add]
  unfold exponential exponentialRawAt ComplexCompute.cauchyStabilize
  change ComplexCompute.cauchyStabilizeCompute
      (candidate A).compute (radius A) n =
    ComplexCompute.cauchyStabilizeCompute
      (directCandidate z C).compute (stageRadius C) n
  induction n with
  | zero => simp [ComplexCompute.cauchyStabilizeCompute, hcand, hradius]
  | succ n ih =>
      rw [ComplexCompute.cauchyStabilizeCompute,
        ComplexCompute.cauchyStabilizeCompute, ih, hcand, hradius]

/-- On exact rational-complex inputs, the represented-input lift agrees with
the original rational-point exponential construction. -/
theorem exponential_ofQComplex_equiv_exponentialRawAt
    (z : QComplex) (C : Rat) (hC : 0 <= C)
    (hz : QComplex.normBound z <= C) :
    (exponential (ofQComplex z C hC hz)).Equiv (exponentialRawAt z C) := by
  intro n
  have href := (ComplexCompute.equiv_refl (exponentialRawAt z C)
    (exponentialRawAt_valid hC hz)) n
  unfold ComplexCompute.compareAt at href ⊢
  rw [exponential_ofQComplex_compute_eq z C hC hz n]
  exact href

end BoundedInput
end ComplexExponentialLift
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