Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Computable analysis · PowerSeries · fd889115 k1

Definition
liuyao_ca_fd889115_k1_Analysis_PowerSeries

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

ca-fd889115-k1

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

Definition code
import Definitions.Def_liuyao_ca_fd889115_k1_Analysis_ComplexInterval

set_option autoImplicit true

/-!
# Power series over rational complex numbers

The elementary power-series algorithms are developed once for complex numbers.
Real functions are then obtained by restricting to the real axis.
-/

namespace ComputableAnalysis

namespace QComplex

def normBound (z : QComplex) : Rat := qabs z.re + qabs z.im

def inDisk (z : QComplex) (R : Rat) : Prop := normBound z < R

def pow (z : QComplex) : Nat -> QComplex
  | 0 => one
  | n + 1 => mul z (pow z n)

def divRat (z : QComplex) (q : Rat) : QComplex :=
  { re := z.re / q, im := z.im / q }

end QComplex

def factorial : Nat -> Nat
  | 0 => 1
  | n + 1 => (n + 1) * factorial n

def factorialRat (n : Nat) : Rat := (factorial n : Rat)

def seriesFuel (eps : QPos) : Nat := eps.val.den + 8

namespace FormalPowerSeries

/-- Rational coefficient stream for `sum c_n z^n`. -/
abbrev Coeffs := Nat -> Rat

def altSign (k : Nat) : Rat := if k % 2 = 0 then 1 else -1

/-- Algebraic coefficient shift of a rational power-series stream.

This records the coefficients which would be the linear Taylor coefficients
of a differentiated function.  It is deliberately defined before any
convergence, remainder estimate, or interval-analytic derivative claim. -/
def coefficientShift (c : Coeffs) : Coeffs :=
  fun n => ((n + 1 : Nat) : Rat) * c (n + 1)

/-- Compatibility name for the coefficient-shift operation used by older
finite algebra.  New declarations should prefer `coefficientShift`: an
analytic derivative is introduced only after a quantitative remainder
certificate. -/
def derivative (c : Coeffs) : Coeffs := coefficientShift c

def neg (c : Coeffs) : Coeffs :=
  fun n => -c n

def add (c d : Coeffs) : Coeffs :=
  fun n => c n + d n

def scaleRat (r : Rat) (c : Coeffs) : Coeffs :=
  fun n => r * c n

/-- A checked algebraic coefficient-shift relation. -/
def HasCoefficientShift (F f : Coeffs) : Prop :=
  coefficientShift F = f

/-- Compatibility name for the former formal-derivative predicate. -/
def HasFormalDerivative (F f : Coeffs) : Prop :=
  derivative F = f

/-- Coefficient stream generated by the definite-integral step
`F(x) = F(0) + integral_0^x dF(t) dt`.

This is not an indefinite integral object: the constant term is specified, and
the coefficients are the formal result of integrating over the concrete
interval from `0` to `x`. -/
def coeffsFromDerivativeAtZero (F0 : Rat) (dF : Coeffs) : Coeffs
  | 0 => F0
  | n + 1 => dF n / (((n + 1 : Nat) : Rat))

def monomialCoeff (k : Nat) : Coeffs :=
  fun n => if n = k then 1 else 0

def monomialShiftedCoeff (k : Nat) : Coeffs :=
  fun n => if n = k + 1 then 1 / (((k + 1 : Nat) : Rat)) else 0

/-!
The arctangent facts here are intentionally only the formal coefficient
calculus.

mathlib analogue: the analytic theorem is `Real.hasSum_arctan` and related
power-series/Taylor facts.  Here we keep the finite algebra separate from
convergence and from the geometric branch relation: the theorem below says
that differentiating the odd arctangent monomial coefficients recovers the
geometric-series coefficients for `1/(1+x^2)`.
-/

def atanOddCoeff (k : Nat) : Rat :=
  altSign k / (((2 * k + 1 : Nat) : Rat))

/-- Coefficients of the geometric series for `1/(1+x^2)`:
`1 - x^2 + x^4 - ...`. -/
def oneOverOnePlusSquareCoeff : Coeffs :=
  fun n => if n % 2 = 0 then altSign (n / 2) else 0

/-- Taylor coefficients for the arctangent series generated from
`atan' = 1/(1+x^2)` and `atan(0)=0`.

This definition is intentionally recurrence-shaped: the coefficient of
`x^(n+1)` is the coefficient of `x^n` in `1/(1+x^2)`, divided by `n+1`.
That mirrors the iterated-FTC construction, while staying purely algebraic at
the formal coefficient level. -/
def atanTaylorCoeff : Coeffs :=
  coeffsFromDerivativeAtZero 0 oneOverOnePlusSquareCoeff

def expCoeff : Coeffs :=
  fun n => 1 / factorialRat n

mutual

/-- Sine coefficients, defined by the differential system `sin' = cos`. -/
def sinCoeff : Coeffs
  | 0 => 0
  | n + 1 => cosCoeff n / (((n + 1 : Nat) : Rat))

/-- Cosine coefficients, defined by the differential system `cos' = -sin`. -/
def cosCoeff : Coeffs
  | 0 => 1
  | n + 1 => -sinCoeff n / (((n + 1 : Nat) : Rat))

end

mutual

/-- Hyperbolic sine coefficients, defined by `sinh' = cosh`. -/
def sinhCoeff : Coeffs
  | 0 => 0
  | n + 1 => coshCoeff n / (((n + 1 : Nat) : Rat))

/-- Hyperbolic cosine coefficients, defined by `cosh' = sinh`. -/
def coshCoeff : Coeffs
  | 0 => 1
  | n + 1 => sinhCoeff n / (((n + 1 : Nat) : Rat))

end

theorem factorialRat_succ (n : Nat) :
    factorialRat (n + 1) = ((n + 1 : Nat) : Rat) * factorialRat n := by
  simp [factorialRat, factorial]

theorem factorial_ne_zero : forall n : Nat, factorial n ≠ 0
  | 0 => by simp [factorial]
  | n + 1 => by
      simp [factorial]
      exact Nat.mul_ne_zero (Nat.succ_ne_zero n) (factorial_ne_zero n)

theorem natCast_succ_ne_zero (n : Nat) :
    (((n + 1 : Nat) : Rat) ≠ 0) := by
  exact Rat.ne_of_gt ((Rat.natCast_pos).2 (by omega : 0 < n + 1))

theorem mul_div_cancel_left {a b : Rat} (ha : a ≠ 0) :
    a * (b / a) = b := by
  rw [Rat.div_def]
  calc
    a * (b * a⁻¹) = b * (a * a⁻¹) := by
      grind [Rat.mul_assoc, Rat.mul_comm]
    _ = b * 1 := by
      rw [Rat.mul_inv_cancel a ha]
    _ = b := by
      rw [Rat.mul_one]

theorem coeffsFromDerivativeAtZero_hasFormalDerivative (F0 : Rat) (dF : Coeffs) :
    HasFormalDerivative (coeffsFromDerivativeAtZero F0 dF) dF := by
  unfold HasFormalDerivative
  funext n
  dsimp [derivative, coefficientShift, coeffsFromDerivativeAtZero]
  exact mul_div_cancel_left (natCast_succ_ne_zero n)

/-- A formal primitive is uniquely determined by its constant coefficient and
its coefficient-wise derivative.  This is the coefficient-level analogue of
recovering a primitive from one initial value; it is finite rational algebra,
not an appeal to a completed function space. -/
theorem coeffsFromDerivativeAtZero_eq_of_hasFormalDerivative
    {F dF : Coeffs} (hF : HasFormalDerivative F dF) :
    coeffsFromDerivativeAtZero (F 0) dF = F := by
  unfold HasFormalDerivative derivative coefficientShift at hF
  funext n
  cases n with
  | zero => rfl
  | succ n =>
      dsimp [coeffsFromDerivativeAtZero]
      rw [← congrFun hF n, Rat.div_def]
      have hne : (((n + 1 : Nat) : Rat)) ≠ 0 := natCast_succ_ne_zero n
      grind [Rat.mul_assoc, Rat.mul_comm, Rat.mul_inv_cancel _ hne]

theorem derivative_neg (c : Coeffs) :
    derivative (neg c) = neg (derivative c) := by
  funext n
  dsimp [derivative, coefficientShift, neg]
  rw [Rat.mul_neg]

theorem neg_neg (c : Coeffs) :
    neg (neg c) = c := by
  funext n
  dsimp [neg]
  exact Rat.neg_neg (c n)

theorem derivative_add (c d : Coeffs) :
    derivative (add c d) = add (derivative c) (derivative d) := by
  funext n
  dsimp [derivative, coefficientShift, add]
  rw [Rat.mul_add]

theorem derivative_scaleRat (r : Rat) (c : Coeffs) :
    derivative (scaleRat r c) = scaleRat r (derivative c) := by
  funext n
  dsimp [derivative, coefficientShift, scaleRat]
  grind [Rat.mul_assoc, Rat.mul_comm]

theorem HasFormalDerivative.add {F f G g : Coeffs}
    (hF : HasFormalDerivative F f) (hG : HasFormalDerivative G g) :
    HasFormalDerivative (add F G) (add f g) := by
  unfold HasFormalDerivative at *
  rw [derivative_add, hF, hG]

theorem HasFormalDerivative.scaleRat (r : Rat) {F f : Coeffs}
    (hF : HasFormalDerivative F f) :
    HasFormalDerivative (scaleRat r F) (scaleRat r f) := by
  unfold HasFormalDerivative at *
  rw [derivative_scaleRat, hF]

theorem monomialShiftedCoeff_derivative (k : Nat) :
    HasFormalDerivative (monomialShiftedCoeff k) (monomialCoeff k) := by
  unfold HasFormalDerivative
  funext n
  dsimp [derivative, coefficientShift, monomialShiftedCoeff, monomialCoeff]
  by_cases hn : n = k
  · subst n
    simp
    have hk : ((k : Rat) + 1) ≠ 0 := by
      exact Rat.ne_of_gt (by grind : (0 : Rat) < (k : Rat) + 1)
    exact mul_div_cancel_left hk
  · simp [hn]

/-- Formal arctangent coefficient calculus:
`d/dx ((-1)^k x^(2k+1)/(2k+1)) = (-1)^k x^(2k)`.

This is the term-level brick needed before proving that the arctangent
power-series algorithm agrees with the integral of `1/(1+x^2)`. -/
theorem atanOddCoeff_derivative_term (k : Nat) :
    (((2 * k + 1 : Nat) : Rat)) * atanOddCoeff k = altSign k := by
  unfold atanOddCoeff
  exact mul_div_cancel_left (natCast_succ_ne_zero (2 * k))

/-- The arctangent Taylor coefficient stream differentiates to the geometric
coefficient stream for `1/(1+x^2)`.

This is the formal-series part of the preferred Taylor route:
FTC gives `atan x = atan 0 + integral_0^x 1/(1+t^2) dt`, and repeated FTC on
the geometric-series coefficients gives the odd arctangent coefficients. -/
theorem atanTaylorCoeff_hasFormalDerivative :
    HasFormalDerivative atanTaylorCoeff oneOverOnePlusSquareCoeff :=
  coeffsFromDerivativeAtZero_hasFormalDerivative 0 oneOverOnePlusSquareCoeff

theorem atanTaylorCoeff_zero :
    atanTaylorCoeff 0 = 0 := rfl

theorem atanTaylorCoeff_odd (k : Nat) :
    atanTaylorCoeff (2 * k + 1) = atanOddCoeff k := by
  unfold atanTaylorCoeff coeffsFromDerivativeAtZero oneOverOnePlusSquareCoeff atanOddCoeff
  change ((if (2 * k) % 2 = 0 then altSign ((2 * k) / 2) else 0) /
      (((2 * k) + 1 : Nat) : Rat)) =
    altSign k / (((2 * k + 1 : Nat) : Rat))
  have hmod : (2 * k) % 2 = 0 := by omega
  have hdiv : (2 * k) / 2 = k := by omega
  simp [hmod, hdiv]

theorem atanTaylorCoeff_even_succ (k : Nat) :
    atanTaylorCoeff (2 * k + 2) = 0 := by
  rw [show 2 * k + 2 = (2 * k + 1) + 1 by omega]
  unfold atanTaylorCoeff coeffsFromDerivativeAtZero oneOverOnePlusSquareCoeff
  change ((if (2 * k + 1) % 2 = 0 then altSign ((2 * k + 1) / 2) else 0) /
      (((2 * k + 1) + 1 : Nat) : Rat)) = 0
  have hmod : ¬(2 * k + 1) % 2 = 0 := by omega
  rw [if_neg hmod]
  rw [Rat.div_def]
  simp

/-- The formal derivative of the exponential coefficient stream is itself.

This is the power-series-specific algebraic fact behind the future theorem
that the boxed algorithm `exp.ps` has derivative `exp.ps`. -/
theorem expCoeff_derivative :
    derivative expCoeff = expCoeff := by
  funext n
  dsimp [derivative, coefficientShift, expCoeff]
  rw [factorialRat_succ n]
  have hn : (((n + 1 : Nat) : Rat) ≠ 0) := natCast_succ_ne_zero n
  have hf : factorialRat n ≠ 0 := by
    unfold factorialRat
    exact_mod_cast factorial_ne_zero n
  rw [Rat.div_def, Rat.div_def]
  rw [Rat.one_mul, Rat.one_mul]
  grind [Rat.mul_assoc, Rat.mul_comm]

theorem expCoeff_second_derivative :
    derivative (derivative expCoeff) = expCoeff := by
  rw [expCoeff_derivative, expCoeff_derivative]

/-- The formal derivative of the sine coefficient stream is cosine. -/
theorem sinCoeff_derivative :
    derivative sinCoeff = cosCoeff := by
  funext n
  dsimp [derivative, coefficientShift]
  rw [sinCoeff]
  exact mul_div_cancel_left (natCast_succ_ne_zero n)

/-- The formal derivative of the cosine coefficient stream is negative sine. -/
theorem cosCoeff_derivative :
    derivative cosCoeff = neg sinCoeff := by
  funext n
  dsimp [derivative, coefficientShift, neg]
  rw [cosCoeff]
  exact mul_div_cancel_left (natCast_succ_ne_zero n)

theorem sinCoeff_second_derivative :
    derivative (derivative sinCoeff) = neg sinCoeff := by
  rw [sinCoeff_derivative, cosCoeff_derivative]

theorem cosCoeff_second_derivative :
    derivative (derivative cosCoeff) = neg cosCoeff := by
  rw [cosCoeff_derivative, derivative_neg, sinCoeff_derivative]

/-- The formal derivative of the hyperbolic sine coefficient stream is
hyperbolic cosine. -/
theorem sinhCoeff_derivative :
    derivative sinhCoeff = coshCoeff := by
  funext n
  dsimp [derivative, coefficientShift]
  rw [sinhCoeff]
  exact mul_div_cancel_left (natCast_succ_ne_zero n)

/-- The formal derivative of the hyperbolic cosine coefficient stream is
hyperbolic sine. -/
theorem coshCoeff_derivative :
    derivative coshCoeff = sinhCoeff := by
  funext n
  dsimp [derivative, coefficientShift]
  rw [coshCoeff]
  exact mul_div_cancel_left (natCast_succ_ne_zero n)

theorem sinhCoeff_second_derivative :
    derivative (derivative sinhCoeff) = sinhCoeff := by
  rw [sinhCoeff_derivative, coshCoeff_derivative]

theorem coshCoeff_second_derivative :
    derivative (derivative coshCoeff) = coshCoeff := by
  rw [coshCoeff_derivative, sinhCoeff_derivative]

/-- First-year calculus table entry: the formal derivative of `exp` is `exp`. -/
theorem expCoeff_hasFormalDerivative :
    HasFormalDerivative expCoeff expCoeff :=
  expCoeff_derivative

/-- First-year calculus table entry: the formal derivative of `sin` is `cos`. -/
theorem sinCoeff_hasFormalDerivative :
    HasFormalDerivative sinCoeff cosCoeff :=
  sinCoeff_derivative

/-- First-year calculus table entry: the formal derivative of `-cos` is `sin`. -/
theorem neg_cosCoeff_hasFormalDerivative :
    HasFormalDerivative (neg cosCoeff) sinCoeff := by
  unfold HasFormalDerivative
  rw [derivative_neg, cosCoeff_derivative, neg_neg]

/-- First-year calculus table entry: the formal derivative of `cosh` is `sinh`. -/
theorem coshCoeff_hasFormalDerivative :
    HasFormalDerivative coshCoeff sinhCoeff :=
  coshCoeff_derivative

/-- First-year calculus table entry: the formal derivative of `sinh` is `cosh`. -/
theorem sinhCoeff_hasFormalDerivative :
    HasFormalDerivative sinhCoeff coshCoeff :=
  sinhCoeff_derivative

/-- Primary coefficient-shift names for the finite series algebra.

The formal-derivative declarations above remain stable compatibility API; the
following aliases are the names used by new finite Taylor constructions. -/
theorem coefficientShift_neg (c : Coeffs) :
    coefficientShift (neg c) = neg (coefficientShift c) :=
  derivative_neg c

theorem coefficientShift_add (c d : Coeffs) :
    coefficientShift (add c d) =
      add (coefficientShift c) (coefficientShift d) :=
  derivative_add c d

theorem coefficientShift_scaleRat (r : Rat) (c : Coeffs) :
    coefficientShift (scaleRat r c) = scaleRat r (coefficientShift c) :=
  derivative_scaleRat r c

theorem hasCoefficientShift_add {F f G g : Coeffs}
    (hF : HasCoefficientShift F f) (hG : HasCoefficientShift G g) :
    HasCoefficientShift (add F G) (add f g) := by
  change HasFormalDerivative F f at hF
  change HasFormalDerivative G g at hG
  change HasFormalDerivative (add F G) (add f g)
  exact HasFormalDerivative.add hF hG

theorem hasCoefficientShift_scaleRat (r : Rat) {F f : Coeffs}
    (hF : HasCoefficientShift F f) :
    HasCoefficientShift (scaleRat r F) (scaleRat r f) := by
  change HasFormalDerivative F f at hF
  change HasFormalDerivative (scaleRat r F) (scaleRat r f)
  exact HasFormalDerivative.scaleRat r hF

theorem monomialShiftedCoeff_hasCoefficientShift (k : Nat) :
    HasCoefficientShift (monomialShiftedCoeff k) (monomialCoeff k) :=
  monomialShiftedCoeff_derivative k

theorem expCoeff_hasCoefficientShift :
    HasCoefficientShift expCoeff expCoeff :=
  expCoeff_derivative

theorem sinCoeff_hasCoefficientShift :
    HasCoefficientShift sinCoeff cosCoeff :=
  sinCoeff_derivative

theorem neg_cosCoeff_hasCoefficientShift :
    HasCoefficientShift (neg cosCoeff) sinCoeff :=
  neg_cosCoeff_hasFormalDerivative

theorem coshCoeff_hasCoefficientShift :
    HasCoefficientShift coshCoeff sinhCoeff :=
  coshCoeff_derivative

theorem sinhCoeff_hasCoefficientShift :
    HasCoefficientShift sinhCoeff coshCoeff :=
  sinhCoeff_derivative

/-!
## Finite sine-series integration

These identities are deliberately finite.  They form the algebraic core of
the later computable FTC route: no infinite sum, completed real, or limit is
used.  A remainder certificate can subsequently replace the finite Taylor
polynomials by the project’s `RealCompute` sine evaluator.
-/

def sineTaylorTerm (x : Rat) (k : Nat) : Rat :=
  altSign k * x ^ (2 * k + 1) / factorialRat (2 * k + 1)

def cosineTaylorTerm (x : Rat) (k : Nat) : Rat :=
  altSign k * x ^ (2 * k) / factorialRat (2 * k)

def sineTaylorPartial (x : Rat) : Nat -> Rat
  | 0 => 0
  | n + 1 => sineTaylorPartial x n + sineTaylorTerm x n

def cosineTaylorPartial (x : Rat) : Nat -> Rat
  | 0 => 0
  | n + 1 => cosineTaylorPartial x n + cosineTaylorTerm x n

def sineTaylorIntegralPartial (x : Rat) : Nat -> Rat
  | 0 => 0
  | n + 1 =>
      sineTaylorIntegralPartial x n +
        altSign n * x ^ (2 * n + 2) / factorialRat (2 * n + 2)

theorem factorialRat_add_two (n : Nat) :
    factorialRat (2 * n + 2) =
      (((2 * n + 2 : Nat) : Rat) * ((2 * n + 1 : Nat) : Rat)) *
        factorialRat (2 * n) := by
  rw [show 2 * n + 2 = (2 * n + 1) + 1 by omega,
    show 2 * n + 1 = (2 * n) + 1 by omega,
    factorialRat_succ, factorialRat_succ]
  grind [Rat.mul_assoc, Rat.mul_comm]

theorem sineTaylorIntegralPartial_eq_one_sub_cosineTaylorPartial_succ
    (x : Rat) :
    forall n,
      sineTaylorIntegralPartial x n =
        1 - cosineTaylorPartial x (n + 1) := by
  intro n
  induction n with
  | zero =>
      simp [sineTaylorIntegralPartial, cosineTaylorPartial,
        cosineTaylorTerm, altSign, factorialRat, factorial]
      decide +kernel
  | succ n ih =>
      rw [sineTaylorIntegralPartial, cosineTaylorPartial, ih]
      have hfact := factorialRat_add_two n
      have hsign : altSign n = -altSign (n + 1) := by
        unfold altSign
        split <;> split <;> simp_all <;> omega
      rw [hfact, hsign]
      simp only [cosineTaylorTerm]
      rw [show 2 * (n + 1) = 2 * n + 2 by omega]
      grind [Rat.div_def, Rat.mul_assoc, Rat.mul_comm,
        Rat.sub_eq_add_neg, Rat.add_assoc, Rat.add_comm]

end FormalPowerSeries

namespace RationalMajorant

/-- Data used to justify a power-series computation at a point: after `start`,
the coefficient/input terms are dominated by a geometric sequence. -/
structure GeometricCertificate where
  scale : Rat
  ratio : Rat
  start : Nat
  scale_nonneg : 0 <= scale
  ratio_nonneg : 0 <= ratio
  ratio_small : ratio <= (1 : Rat) / 2

def geomTailPartial (C r : Rat) (N : Nat) : Nat -> Rat
  | 0 => 0
  | k + 1 => geomTailPartial C r N k + C * r ^ (N + k)

def geomTailBound (C r : Rat) (N : Nat) : Rat :=
  2 * C * r ^ N

theorem two_mul_half : (2 : Rat) * (1 / 2 : Rat) = 1 := by
  rw [Rat.div_def]
  rw [Rat.one_mul]
  rw [Rat.mul_inv_cancel]
  exact Rat.ne_of_gt ((Rat.natCast_pos).2 (by omega : 0 < (2 : Nat)))

/-- Finite geometric tails with ratio at most `1/2` are bounded by twice
the first omitted majorant term.  This is the rational-only convergence
estimate that later powers `exp`, `sin`, and `cos` certificates. -/
theorem geometric_tail_bound_valid {C r : Rat} {N k : Nat}
    (hC : 0 <= C) (hr0 : 0 <= r) (hrHalf : r <= (1 : Rat) / 2) :
    geomTailPartial C r N k + 2 * C * r ^ (N + k) <= geomTailBound C r N := by
  induction k with
  | zero =>
      simp [geomTailPartial, geomTailBound]
      rw [Rat.zero_add]
      exact Rat.le_refl
  | succ k ih =>
      rw [geomTailPartial]
      have hpowNonneg : 0 <= r ^ (N + k) := Rat.pow_nonneg hr0
      have htermNonneg : 0 <= C * r ^ (N + k) := Rat.mul_nonneg hC hpowNonneg
      have h2pos : (0 : Rat) < 2 := (Rat.natCast_pos).2 (by omega : 0 < (2 : Nat))
      have h2nonneg : 0 <= (2 : Rat) := Rat.le_of_lt h2pos
      have h2rLe : (2 : Rat) * r <= 1 := by
        have hle0 : (2 : Rat) * r <= 2 * (1 / 2 : Rat) :=
          Rat.mul_le_mul_of_nonneg_left hrHalf h2nonneg
        rw [two_mul_half] at hle0
        exact hle0
      have hnext : 2 * C * r ^ (N + (k + 1)) <= C * r ^ (N + k) := by
        rw [show N + (k + 1) = N + k + 1 by omega]
        rw [Rat.pow_succ]
        calc
          2 * C * (r ^ (N + k) * r) = (C * r ^ (N + k)) * (2 * r) := by
            grind [Rat.mul_assoc, Rat.mul_comm]
          _ <= (C * r ^ (N + k)) * 1 :=
            Rat.mul_le_mul_of_nonneg_left h2rLe htermNonneg
          _ = C * r ^ (N + k) := by
            rw [Rat.mul_one]
      calc
        geomTailPartial C r N k + C * r ^ (N + k) + 2 * C * r ^ (N + (k + 1))
            <= geomTailPartial C r N k + C * r ^ (N + k) + C * r ^ (N + k) := by
              rw [Rat.add_le_add_left]
              exact hnext
        _ = geomTailPartial C r N k + 2 * C * r ^ (N + k) := by
          grind [Rat.mul_assoc, Rat.add_assoc]
        _ <= geomTailBound C r N := ih

theorem geometric_tail_partial_bound {C r : Rat} {N k : Nat}
    (hC : 0 <= C) (hr0 : 0 <= r) (hrHalf : r <= (1 : Rat) / 2) :
    geomTailPartial C r N k <= geomTailBound C r N := by
  have hpowNonneg : 0 <= r ^ (N + k) := Rat.pow_nonneg hr0
  have htermNonneg : 0 <= 2 * C * r ^ (N + k) := by
    have h2nonneg : 0 <= (2 : Rat) :=
      Rat.le_of_lt ((Rat.natCast_pos).2 (by omega : 0 < (2 : Nat)))
    exact Rat.mul_nonneg (Rat.mul_nonneg h2nonneg hC) hpowNonneg
  exact Rat.le_trans
    (show geomTailPartial C r N k <= geomTailPartial C r N k + 2 * C * r ^ (N + k) by
      have h := (Rat.add_le_add_left (a := 0) (b := 2 * C * r ^ (N + k))
        (c := geomTailPartial C r N k)).mpr htermNonneg
      rw [Rat.add_zero] at h
      exact h)
    (geometric_tail_bound_valid hC hr0 hrHalf)

theorem certificate_tail_bound (cert : GeometricCertificate) (k : Nat) :
    geomTailPartial cert.scale cert.ratio cert.start k <=
      geomTailBound cert.scale cert.ratio cert.start :=
  geometric_tail_partial_bound cert.scale_nonneg cert.ratio_nonneg cert.ratio_small

/-- The nonnegative magnitude of the `n`th factorial-series term with
coefficient bound `C`.  This is the scalar majorant for the ordered-simplex
terms in a Peano--Baker series, as well as for exponential-type power series. -/
def factorialTailTerm (C : Rat) (n : Nat) : Rat :=
  C ^ n / factorialRat n

/-- A finite prefix of the factorial tail starting with the `N`th term.  This
is deliberately a finite rational sum; the following theorem supplies its
uniform tail enclosure. -/
def factorialTailPartial (C : Rat) (N : Nat) : Nat -> Rat
  | 0 => 0
  | k + 1 => factorialTailPartial C N k + factorialTailTerm C (N + k)

/- Splitting a finite factorial prefix after any prescribed number of terms
is an exact rational identity.  This is the finite bookkeeping lemma behind
uniform bounds for parameter-sensitive power-series prefixes. -/
theorem factorialTailPartial_add (C : Rat) (N a b : Nat) :
    factorialTailPartial C N (a + b) =
      factorialTailPartial C N a + factorialTailPartial C (N + a) b := by
  induction b with
  | zero =>
      rw [Nat.add_zero, factorialTailPartial]
      grind [Rat.add_zero]
  | succ b ih =>
      rw [show a + (b + 1) = (a + b) + 1 by omega]
      rw [factorialTailPartial, ih, factorialTailPartial]
      have hindex : N + (a + b) = N + a + b := by omega
      rw [hindex]
      grind [Rat.add_assoc]

theorem factorialRat_pos (n : Nat) : 0 < factorialRat n := by
  unfold factorialRat
  exact_mod_cast (show 0 < factorial n from by
    induction n with
    | zero => simp [factorial]
    | succ n ih =>
      simp only [factorial]
      exact Nat.mul_pos (Nat.succ_pos n) ih)

theorem factorialTailTerm_nonneg {C : Rat} (hC : 0 <= C) (n : Nat) :
    0 <= factorialTailTerm C n := by
  unfold factorialTailTerm
  rw [Rat.div_def]
  exact Rat.mul_nonneg (Rat.pow_nonneg hC)
    (Rat.le_of_lt ((Rat.inv_pos).2 (factorialRat_pos n)))

/- A finite factorial prefix with nonnegative coefficient bound grows with
its number of terms.  This is a statement about finite rational sums only. -/
theorem factorialTailPartial_mono {C : Rat} (hC : 0 <= C) (N : Nat) :
    forall k m : Nat, k <= m ->
      factorialTailPartial C N k <= factorialTailPartial C N m
  | k, 0, hkm => by
      have hk : k = 0 := by omega
      subst k
      exact Rat.le_refl
  | k, m + 1, hkm => by
      by_cases hlast : k = m + 1
      · subst k
        exact Rat.le_refl
      · have hkm' : k <= m := by omega
        have ih := factorialTailPartial_mono hC N k m hkm'
        calc
          factorialTailPartial C N k <= factorialTailPartial C N m := ih
          _ <= factorialTailPartial C N (m + 1) := by
            rw [factorialTailPartial]
            have hterm := factorialTailTerm_nonneg hC (N + m)
            grind [Rat.sub_eq_add_neg]

/-- The finite factorial majorant is monotone in its nonnegative coefficient
bound.  This is the elementary uniformity fact used when a power-series
algorithm receives a rational parameter only through a certified enclosing
interval. -/
theorem factorialTailTerm_mono {C D : Rat}
    (hC : 0 <= C) (hCD : C <= D) (n : Nat) :
    factorialTailTerm C n <= factorialTailTerm D n := by
  have hD : 0 <= D := Rat.le_trans hC hCD
  have hpow : C ^ n <= D ^ n := by
    induction n with
    | zero => simp
    | succ n ih =>
        rw [Rat.pow_succ, Rat.pow_succ]
        calc
          C ^ n * C <= D ^ n * C :=
            Rat.mul_le_mul_of_nonneg_right ih hC
          _ <= D ^ n * D :=
            Rat.mul_le_mul_of_nonneg_left hCD (Rat.pow_nonneg hD)
  unfold factorialTailTerm
  rw [Rat.div_def, Rat.div_def]
  exact Rat.mul_le_mul_of_nonneg_right hpow
    (Rat.le_of_lt ((Rat.inv_pos).2 (factorialRat_pos n)))

/-- Successive factorial terms differ by the expected rational ratio. -/
theorem factorialTailTerm_succ (C : Rat) (n : Nat) :
    factorialTailTerm C (n + 1) =
      factorialTailTerm C n * (C / ((n + 1 : Nat) : Rat)) := by
  unfold factorialTailTerm
  rw [Rat.pow_succ, FormalPowerSeries.factorialRat_succ]
  rw [Rat.div_def, Rat.div_def, Rat.div_def, Rat.inv_mul_rev]
  grind [Rat.mul_assoc, Rat.mul_comm]

theorem factorialTailTerm_succ_le_half {C : Rat} (hC : 0 <= C) (n : Nat)
    (hratio : C / ((n + 1 : Nat) : Rat) <= (1 : Rat) / 2) :
    factorialTailTerm C (n + 1) <= factorialTailTerm C n * ((1 : Rat) / 2) := by
  rw [factorialTailTerm_succ]
  exact Rat.mul_le_mul_of_nonneg_left hratio (factorialTailTerm_nonneg hC n)

/-- Once the first omitted factorial term has denominator at least twice its
coefficient bound, every later term has ratio at most one half. -/
theorem factorialTailRatio_le_half_from_start (C : Rat) (N k : Nat)
    (hstart : C <= (((N + 1 : Nat) : Rat) / 2)) :
    C / ((N + k + 1 : Nat) : Rat) <= (1 : Rat) / 2 := by
  let D : Rat := ((N + k + 1 : Nat) : Rat)
  have hDpos : 0 < D := by
    dsimp [D]
    exact_mod_cast (show 0 < N + k + 1 by omega)
  have hDne : D ≠ 0 := Rat.ne_of_gt hDpos
  have hND : (((N + 1 : Nat) : Rat)) <= D := by
    dsimp [D]
    exact_mod_cast (show N + 1 <= N + k + 1 by omega)
  have hhalfNonneg : (0 : Rat) <= 1 / 2 := by decide +kernel
  have hhalf := Rat.mul_le_mul_of_nonneg_left hND hhalfNonneg
  have hscaled : (((N + 1 : Nat) : Rat) / 2) <= D / 2 := by
    simpa [Rat.div_def, Rat.mul_assoc, Rat.mul_comm] using hhalf
  apply Rat.le_of_mul_le_mul_right (c := D)
  · calc
      (C / D) * D = C := by
        rw [Rat.div_def]
        calc
          C * D⁻¹ * D = C * (D⁻¹ * D) := by grind [Rat.mul_assoc]
          _ = C * 1 := by rw [Rat.inv_mul_cancel D hDne]
          _ = C := by rw [Rat.mul_one]
      _ <= D / 2 := Rat.le_trans hstart hscaled
      _ = ((1 : Rat) / 2) * D := by
        rw [Rat.div_def]
        grind [Rat.mul_assoc, Rat.mul_comm]
  · exact hDpos

/-- A computable start for the factorial tail.  It depends only on the
rational numerator of `C`, so it introduces no ceiling operation over a
completed real line. -/
def factorialTailStart (C : Rat) : Nat :=
  2 * C.num.natAbs + 1

private theorem rat_le_num_natAbs_succ (q : Rat) :
    q <= (((q.num.natAbs : Nat) : Rat) + 1) := by
  by_cases hqpos : 0 < q
  · have hdenpos : 0 < ((q.den : Nat) : Rat) := by
      exact (Rat.natCast_pos).2 (Nat.pos_of_ne_zero q.den_nz)
    apply Rat.le_of_mul_le_mul_right (c := ((q.den : Nat) : Rat))
    · rw [Rat.mul_comm q ((q.den : Nat) : Rat), rat_den_mul_self]
      have hnumpos : 0 < q.num := rat_num_pos_of_pos hqpos
      have hnum_nonneg : 0 <= q.num := Int.le_of_lt hnumpos
      have hcast : (((q.num.natAbs : Nat) : Rat)) = (q.num : Rat) := by
        exact_mod_cast (Int.natAbs_of_nonneg hnum_nonneg)
      calc
        (q.num : Rat) = ((q.num.natAbs : Nat) : Rat) := by rw [hcast]
        _ <= (((q.num.natAbs : Nat) : Rat) + 1) := by
          exact_mod_cast (Nat.le_succ q.num.natAbs)
        _ <= (((q.num.natAbs : Nat) : Rat) + 1) *
            ((q.den : Nat) : Rat) := by
          exact_mod_cast (Nat.le_mul_of_pos_right (q.num.natAbs + 1)
            (Nat.pos_of_ne_zero q.den_nz))
    · exact hdenpos
  · have hqnonpos : q <= 0 := by grind
    have hzero : (0 : Rat) <= (((q.num.natAbs : Nat) : Rat) + 1) := by
      exact_mod_cast (Nat.zero_le (q.num.natAbs + 1))
    exact Rat.le_trans hqnonpos hzero

theorem factorialTailStart_satisfies (C : Rat) :
    C <= (((factorialTailStart C + 1 : Nat) : Rat) / 2) := by
  have h := rat_le_num_natAbs_succ C
  unfold factorialTailStart
  have htwopos : (0 : Rat) < 2 := by decide +kernel
  have htwone : (2 : Rat) ≠ 0 := Rat.ne_of_gt htwopos
  apply Rat.le_of_mul_le_mul_right (c := (2 : Rat))
  · calc
      C * 2 <= (((C.num.natAbs : Nat) : Rat) + 1) * 2 :=
        Rat.mul_le_mul_of_nonneg_right h (Rat.le_of_lt htwopos)
      _ = ((2 * C.num.natAbs + 1 + 1 : Nat) : Rat) := by
        exact_mod_cast
          (show (C.num.natAbs + 1) * 2 = 2 * C.num.natAbs + 1 + 1 by omega)
      _ = (((2 * C.num.natAbs + 1 + 1 : Nat) : Rat) / 2) * 2 := by
        rw [Rat.div_def]
        grind [Rat.mul_assoc, Rat.mul_comm, Rat.mul_inv_cancel]
  · exact htwopos

/-- The sufficient ratio condition remains true after any number of terms. -/
theorem factorialTailStart_mono (C : Rat) (N k : Nat)
    (hstart : C <= (((N + 1 : Nat) : Rat) / 2)) :
    C <= (((N + k + 1 : Nat) : Rat) / 2) := by
  have hND : (((N + 1 : Nat) : Rat)) <= ((N + k + 1 : Nat) : Rat) := by
    exact_mod_cast (show N + 1 <= N + k + 1 by omega)
  have hhalfNonneg : (0 : Rat) <= 1 / 2 := by decide +kernel
  have h := Rat.mul_le_mul_of_nonneg_left hND hhalfNonneg
  have hscaled : (((N + 1 : Nat) : Rat) / 2) <=
      ((N + k + 1 : Nat) : Rat) / 2 := by
    simpa [Rat.div_def, Rat.mul_assoc, Rat.mul_comm] using h
  exact Rat.le_trans hstart hscaled

/-- Each factorial term after a certified start is dominated by a concrete
geometric term of ratio one half. -/
theorem factorialTailTerm_le_geometric_from_start {C : Rat} {N : Nat}
    (hC : 0 <= C) (hstart : C <= (((N + 1 : Nat) : Rat) / 2)) :
    forall k, factorialTailTerm C (N + k) <=
      factorialTailTerm C N * ((1 : Rat) / 2) ^ k
  | 0 => by simp
  | k + 1 => by
      rw [show N + (k + 1) = N + k + 1 by omega]
      have hstep := factorialTailTerm_succ_le_half hC (N + k)
        (factorialTailRatio_le_half_from_start C N k hstart)
      calc
        factorialTailTerm C (N + k + 1) <=
            factorialTailTerm C (N + k) * ((1 : Rat) / 2) := hstep
        _ <= (factorialTailTerm C N * ((1 : Rat) / 2) ^ k) * ((1 : Rat) / 2) :=
          Rat.mul_le_mul_of_nonneg_right
            (factorialTailTerm_le_geometric_from_start hC hstart k)
            (by decide +kernel : (0 : Rat) <= 1 / 2)
        _ = factorialTailTerm C N * ((1 : Rat) / 2) ^ (k + 1) := by
          rw [Rat.pow_succ]
          grind [Rat.mul_assoc]

/-- Every finite prefix of a factorial tail is bounded by twice its first
omitted term.  Because this is proved for arbitrary prefix length, it is the
finite certificate needed to enclose an infinite Peano--Baker tail. -/
theorem factorialTailPartial_bound {C : Rat} {N : Nat}
    (hC : 0 <= C) (hstart : C <= (((N + 1 : Nat) : Rat) / 2)) (k : Nat) :
    factorialTailPartial C N k <= 2 * factorialTailTerm C N := by
  calc
    factorialTailPartial C N k <=
        geomTailPartial (factorialTailTerm C N) ((1 : Rat) / 2) 0 k := by
      induction k with
      | zero => rfl
      | succ k ih =>
        rw [factorialTailPartial, geomTailPartial]
        have hterm := factorialTailTerm_le_geometric_from_start hC hstart k
        grind
    _ <= geomTailBound (factorialTailTerm C N) ((1 : Rat) / 2) 0 :=
      geometric_tail_partial_bound (factorialTailTerm_nonneg hC N)
        (by decide +kernel) (by decide +kernel)
    _ = 2 * factorialTailTerm C N := by simp [geomTailBound]

/-- A shifted factorial tail has an explicit geometric decay budget. -/
theorem factorialTailPartial_shifted_bound {C : Rat} {N : Nat}
    (hC : 0 <= C) (hstart : C <= (((N + 1 : Nat) : Rat) / 2)) (k m : Nat) :
    factorialTailPartial C (N + k) m <=
      2 * factorialTailTerm C N * ((1 : Rat) / 2) ^ k := by
  calc
    factorialTailPartial C (N + k) m <=
        2 * factorialTailTerm C (N + k) :=
      factorialTailPartial_bound hC (factorialTailStart_mono C N k hstart) m
    _ <= 2 * (factorialTailTerm C N * ((1 : Rat) / 2) ^ k) :=
      Rat.mul_le_mul_of_nonneg_left
        (factorialTailTerm_le_geometric_from_start hC hstart k)
        (by decide +kernel : (0 : Rat) <= 2)
    _ = 2 * factorialTailTerm C N * ((1 : Rat) / 2) ^ k := by
      grind [Rat.mul_assoc]

/-- The explicit stage used to turn a rational geometric bound of ratio
one half into a requested positive rational tolerance.  Its two factors are
the numerator bound for the initial radius and the denominator bound for the
tolerance; no archimedean principle over completed reals is involved. -/
def halfDecayShift (bound : Rat) (eps : QPos) : Nat :=
  (bound.num.natAbs + 1) * (eps.val.den + 1)

/-- The half-decay selector is at least the tolerance's denominator scale.
This lower bound is useful when a later proof needs the selected finite
prefix to dominate an independently chosen output stage. -/
theorem halfDecayShift_ge_denominator (bound : Rat) (eps : QPos) :
    eps.val.den + 1 <= halfDecayShift bound eps := by
  unfold halfDecayShift
  exact Nat.le_mul_of_pos_left _ (Nat.succ_pos _)

private theorem one_div_antitone_of_pos {a b : Rat}
    (ha : 0 < a) (hab : a <= b) :
    1 / b <= 1 / a := by
  have hb : 0 < b := by grind
  have hane : a ≠ 0 := Rat.ne_of_gt ha
  have hbne : b ≠ 0 := Rat.ne_of_gt hb
  have habpos : 0 < a * b := Rat.mul_pos ha hb
  apply Rat.le_of_mul_le_mul_right (c := a * b)
  · calc
      (1 / b) * (a * b) = a := by
        rw [Rat.div_def]
        have hcancel : b * b⁻¹ = 1 := Rat.mul_inv_cancel b hbne
        grind [Rat.mul_assoc, Rat.mul_comm]
      _ <= b := hab
      _ = (1 / a) * (a * b) := by
        rw [Rat.div_def]
        have hcancel : a * a⁻¹ = 1 := Rat.mul_inv_cancel a hane
        grind [Rat.mul_assoc, Rat.mul_comm]
  · exact habpos

private theorem nat_succ_le_two_pow (n : Nat) : n + 1 <= 2 ^ n := by
  induction n with
  | zero => decide
  | succ n ih =>
      calc
        n + 1 + 1 <= 2 * (n + 1) := by omega
        _ <= 2 * (2 ^ n) := Nat.mul_le_mul_left 2 ih
        _ = 2 ^ (n + 1) := by
          rw [Nat.pow_succ]
          omega

/-- The rational half-power and reciprocal dyadic schedules coincide exactly.
This connects an executable natural precision budget with a geometric
majorant, without an appeal to an ambient limit. -/
theorem half_pow_eq_one_div_nat_two_pow (n : Nat) :
    ((1 : Rat) / 2) ^ n = 1 / (((2 ^ n : Nat) : Rat)) := by
  induction n with
  | zero => decide +kernel
  | succ n ih =>
      rw [Rat.pow_succ, ih, Nat.pow_succ, Rat.natCast_mul]
      rw [Rat.div_def, Rat.div_def, Rat.div_def, Rat.one_mul]
      grind [Rat.mul_assoc, Rat.mul_comm, Rat.mul_inv_cancel]

/-- The ratio-one-half geometric factor is below the ordinary reciprocal
denominator schedule.  This connects the factorial tail to the project's
existing epsilon--denominator convention. -/
theorem half_pow_le_one_div_succ (n : Nat) :
    ((1 : Rat) / 2) ^ n <= 1 / (((n + 1 : Nat) : Rat)) := by
  rw [half_pow_eq_one_div_nat_two_pow]
  have hpowpos : 0 < (((2 ^ n : Nat) : Rat)) := by
    exact (Rat.natCast_pos).2 (Nat.pow_pos (by omega : 0 < 2))
  have hcast : (((n + 1 : Nat) : Rat)) <= ((2 ^ n : Nat) : Rat) := by
    exact_mod_cast nat_succ_le_two_pow n
  exact one_div_antitone_of_pos
    ((Rat.natCast_pos).2 (Nat.succ_pos n)) hcast

/-- The explicit geometric shift makes any nonnegative rational radius with
ratio one half no larger than the requested positive rational epsilon. -/
theorem halfDecayShift_spec {bound : Rat} (hbound : 0 <= bound)
    (eps : QPos) :
    bound * ((1 : Rat) / 2) ^ halfDecayShift bound eps <= eps.val := by
  let B : Nat := bound.num.natAbs + 1
  let D : Nat := eps.val.den + 1
  let shift : Nat := B * D
  have hboundNat : bound <= (B : Rat) := by
    dsimp [B]
    rw [Rat.natCast_add]
    exact rat_le_num_natAbs_succ bound
  have hBpos : 0 < (B : Rat) := by
    dsimp [B]
    exact (Rat.natCast_pos).2 (Nat.succ_pos _)
  have hDpos : 0 < (D : Rat) := by
    dsimp [D]
    exact (Rat.natCast_pos).2 (Nat.succ_pos _)
  have hshiftDenPos : 0 < ((shift + 1 : Nat) : Rat) := by
    exact (Rat.natCast_pos).2 (Nat.succ_pos _)
  have hgeometric : ((1 : Rat) / 2) ^ shift <=
      1 / (((shift + 1 : Nat) : Rat)) :=
    half_pow_le_one_div_succ shift
  have hrecipNonneg : 0 <= 1 / (((shift + 1 : Nat) : Rat)) := by
    rw [Rat.div_def, Rat.one_mul]
    exact Rat.le_of_lt ((Rat.inv_pos).2 hshiftDenPos)
  have hboundOver : bound * (1 / (((shift + 1 : Nat) : Rat))) <=
      (B : Rat) * (1 / (((shift + 1 : Nat) : Rat))) :=
    Rat.mul_le_mul_of_nonneg_right hboundNat hrecipNonneg
  have hBD : ((B : Rat) * (D : Rat)) <= ((shift + 1 : Nat) : Rat) := by
    dsimp [shift]
    rw [← Rat.natCast_mul]
    exact_mod_cast (Nat.le_succ (B * D))
  have hratio : (B : Rat) * (1 / (((shift + 1 : Nat) : Rat))) <=
      1 / (D : Rat) := by
    apply Rat.le_of_mul_le_mul_right (c := (D : Rat) * ((shift + 1 : Nat) : Rat))
    · calc
        ((B : Rat) * (1 / (((shift + 1 : Nat) : Rat))) *
            ((D : Rat) * ((shift + 1 : Nat) : Rat)) =
            (B : Rat) * (D : Rat)) := by
              rw [Rat.div_def]
              have hne : ((shift + 1 : Nat) : Rat) ≠ 0 :=
                Rat.ne_of_gt hshiftDenPos
              grind [Rat.mul_assoc, Rat.mul_comm, Rat.mul_inv_cancel]
        _ <= ((shift + 1 : Nat) : Rat) := hBD
        _ = (1 / (D : Rat)) * ((D : Rat) * ((shift + 1 : Nat) : Rat)) := by
              rw [Rat.div_def]
              have hne : (D : Rat) ≠ 0 := Rat.ne_of_gt hDpos
              grind [Rat.mul_assoc, Rat.mul_comm, Rat.mul_inv_cancel]
    · exact Rat.mul_pos hDpos hshiftDenPos
  have heps : 1 / (D : Rat) <= eps.val := by
    dsimp [D]
    exact one_div_den_succ_le_of_pos eps.property
  have hshift : halfDecayShift bound eps = shift := rfl
  rw [hshift]
  exact Rat.le_trans
    (Rat.le_trans (Rat.mul_le_mul_of_nonneg_left hgeometric hbound) hboundOver)
    (Rat.le_trans hratio heps)

/-- A natural stage large enough to make a nonnegative rational
`bound / (stage + 1)` smaller than a requested positive rational tolerance. -/
def natRateStage (bound : Rat) (eps : QPos) : Nat :=
  (bound.num.natAbs + 1) * (eps.val.den + 1)

/-- The denominator schedule controls every later inverse-linear stage. -/
theorem natRateStage_spec_of_le {bound : Rat} (_hbound : 0 <= bound)
    (eps : QPos) {stage : Nat} (hstage : natRateStage bound eps <= stage) :
    bound / (((stage + 1 : Nat) : Rat)) <= eps.val := by
  let C : Nat := bound.num.natAbs + 1
  let D : Nat := eps.val.den + 1
  let A : Rat := ((stage + 1 : Nat) : Rat)
  let B : Rat := (D : Rat)
  have hboundC : bound <= (C : Rat) := by
    dsimp [C]
    rw [Rat.natCast_add]
    exact rat_le_num_natAbs_succ bound
  have hApos : 0 < A := by
    dsimp [A]
    exact (Rat.natCast_pos).2 (Nat.succ_pos stage)
  have hBpos : 0 < B := by
    dsimp [B, D]
    exact (Rat.natCast_pos).2 (Nat.succ_pos eps.val.den)
  have hAinv0 : 0 <= A⁻¹ := Rat.le_of_lt ((Rat.inv_pos).2 hApos)
  have hfirst : bound / A <= (C : Rat) / A := by
    rw [Rat.div_def, Rat.div_def]
    exact Rat.mul_le_mul_of_nonneg_right hboundC hAinv0
  have hCA : (C : Rat) / A <= 1 / B := by
    have hAne : A ≠ 0 := Rat.ne_of_gt hApos
    have hBne : B ≠ 0 := Rat.ne_of_gt hBpos
    have hABpos : 0 < A * B := Rat.mul_pos hApos hBpos
    have hCD : C * D <= stage + 1 := by
      have hCD0 : C * D <= stage := by
        simpa [C, D, natRateStage] using hstage
      omega
    have hscaled : (C : Rat) * B <= A := by
      dsimp [A, B]
      exact_mod_cast hCD
    apply Rat.le_of_mul_le_mul_right (c := A * B)
    · calc
        ((C : Rat) / A) * (A * B) = (C : Rat) * B := by
          rw [Rat.div_def]
          have hcancel : A * A⁻¹ = 1 := Rat.mul_inv_cancel A hAne
          grind [Rat.mul_assoc, Rat.mul_comm]
        _ <= A := hscaled
        _ = (1 / B) * (A * B) := by
          rw [Rat.div_def]
          have hcancel : B * B⁻¹ = 1 := Rat.mul_inv_cancel B hBne
          grind [Rat.mul_assoc, Rat.mul_comm]
    · exact hABpos
  have hB : 1 / B <= eps.val := by
    dsimp [B, D]
    exact one_div_den_succ_le_of_pos eps.property
  change bound / A <= eps.val
  exact Rat.le_trans hfirst (Rat.le_trans hCA hB)

/-- A dyadic half-decay budget remains valid at every later natural stage. -/
theorem halfDecayShift_spec_of_le {bound : Rat} (hbound : 0 <= bound)
    (eps : QPos) {stage : Nat}
    (hstage : halfDecayShift bound eps <= stage) :
    bound * ((1 : Rat) / 2) ^ stage <= eps.val := by
  obtain ⟨d, hd⟩ := Nat.exists_eq_add_of_le hstage
  have hpow : ((1 : Rat) / 2) ^ stage <=
      ((1 : Rat) / 2) ^ halfDecayShift bound eps := by
    subst stage
    induction d with
    | zero => exact Rat.le_refl
    | succ d ih =>
        rw [show halfDecayShift bound eps + (d + 1) =
          (halfDecayShift bound eps + d) + 1 by omega, Rat.pow_succ]
        calc
          ((1 : Rat) / 2) ^ (halfDecayShift bound eps + d) *
              ((1 : Rat) / 2) <=
              ((1 : Rat) / 2) ^ (halfDecayShift bound eps + d) * 1 :=
            Rat.mul_le_mul_of_nonneg_left (by decide +kernel)
              (Rat.pow_nonneg (by decide +kernel))
          _ = ((1 : Rat) / 2) ^ (halfDecayShift bound eps + d) := by
            rw [Rat.mul_one]
          _ <= ((1 : Rat) / 2) ^ halfDecayShift bound eps := ih (by omega)
  exact Rat.le_trans (Rat.mul_le_mul_of_nonneg_left hpow hbound)
    (halfDecayShift_spec hbound eps)

/-- Half of a positive rational tolerance, packaged for schedule
composition. -/
def halfTolerance (eps : QPos) : QPos :=
  { val := eps.val / 2
    property := by
      rw [Rat.div_def]
      exact Rat.mul_pos eps.property ((Rat.inv_pos).2 (by decide +kernel)) }

/-- One executable stage synchronizing an inverse-linear rate and a dyadic
geometric rate. -/
def mixedNatGeometricStage (natBound geomBound : Rat) (eps : QPos) : Nat :=
  Nat.max
    (natRateStage natBound (halfTolerance eps))
    (halfDecayShift geomBound (halfTolerance eps))

/-- At every stage beyond the synchronized stage, the sum of the two
nonnegative rate budgets is below the requested tolerance. -/
theorem mixedNatGeometricStage_spec_of_le
    {natBound geomBound : Rat} (hnat : 0 <= natBound)
    (hgeom : 0 <= geomBound) (eps : QPos) {stage : Nat}
    (hstage : mixedNatGeometricStage natBound geomBound eps <= stage) :
    natBound /
          ((((stage + 1 : Nat) : Rat))) +
        geomBound * ((1 : Rat) / 2) ^ stage <=
      eps.val := by
  let half := halfTolerance eps
  have hnatStage : natRateStage natBound half <= stage := by
    exact Nat.le_trans (Nat.le_max_left _ _) hstage
  have hgeomStage : halfDecayShift geomBound half <= stage := by
    exact Nat.le_trans (Nat.le_max_right _ _) hstage
  have hnatBound := natRateStage_spec_of_le hnat half hnatStage
  have hgeomBound := halfDecayShift_spec_of_le hgeom half hgeomStage
  calc
    natBound / ((((stage + 1 : Nat) : Rat))) +
        geomBound * ((1 : Rat) / 2) ^ stage <= half.val + half.val :=
      rat_add_le_add hnatBound hgeomBound
    _ = eps.val := by
      dsimp [half, halfTolerance]
      grind

/-- At the synchronized stage itself, the mixed rate is below the requested
tolerance. -/
theorem mixedNatGeometricStage_spec
    {natBound geomBound : Rat} (hnat : 0 <= natBound)
    (hgeom : 0 <= geomBound) (eps : QPos) :
    natBound /
          ((((mixedNatGeometricStage natBound geomBound eps) + 1 : Nat) : Rat)) +
        geomBound * ((1 : Rat) / 2) ^
          mixedNatGeometricStage natBound geomBound eps <=
      eps.val :=
  mixedNatGeometricStage_spec_of_le hnat hgeom eps (Nat.le_refl _)

/-- A dyadic reciprocal step selected from a nonnegative rational error
coefficient. -/
def dyadicStepPrecision (bound : Rat) (eps : QPos) : Nat :=
  2 ^ halfDecayShift bound eps

/-- A step below the selected reciprocal dyadic spends at most the requested
rational error budget. -/
theorem dyadicStepPrecision_spec {bound : Rat} (hbound : 0 <= bound)
    (eps : QPos) {h : Rat}
    (hsmall : qabs h <= 1 / ((dyadicStepPrecision bound eps : Nat) : Rat)) :
    qabs h * bound <= eps.val := by
  let shift := halfDecayShift bound eps
  have hsmall' : qabs h <= 1 / (((2 ^ shift : Nat) : Rat)) := by
    simpa [dyadicStepPrecision, shift] using hsmall
  have hscaled : qabs h * bound <=
      1 / (((2 ^ shift : Nat) : Rat)) * bound :=
    Rat.mul_le_mul_of_nonneg_right hsmall' hbound
  calc
    qabs h * bound <= 1 / (((2 ^ shift : Nat) : Rat)) * bound := hscaled
    _ = bound * ((1 : Rat) / 2) ^ shift := by
      rw [half_pow_eq_one_div_nat_two_pow]
      grind [Rat.mul_comm]
    _ <= eps.val := halfDecayShift_spec hbound eps

/-- The factorial-tail majorant comes with an executable epsilon modulus:
after this shift, every finite prefix of the remaining tail is within the
requested tolerance. -/
theorem factorialTailPartial_shifted_le_eps {C : Rat} (hC : 0 <= C)
    (eps : QPos) (terms : Nat) :
    factorialTailPartial C
      (factorialTailStart C +
        halfDecayShift (2 * factorialTailTerm C (factorialTailStart C)) eps)
      terms <= eps.val := by
  let bound : Rat := 2 * factorialTailTerm C (factorialTailStart C)
  have hbound : 0 <= bound := by
    dsimp [bound]
    exact Rat.mul_nonneg (by decide +kernel)
      (factorialTailTerm_nonneg hC _)
  calc
    factorialTailPartial C
        (factorialTailStart C + halfDecayShift bound eps) terms <=
        bound * ((1 : Rat) / 2) ^ halfDecayShift bound eps := by
          dsimp [bound]
          exact factorialTailPartial_shifted_bound hC
            (factorialTailStart_satisfies C)
            (halfDecayShift (2 * factorialTailTerm C (factorialTailStart C)) eps)
            terms
    _ <= eps.val := halfDecayShift_spec hbound eps

/-- The fully computable version of the factorial-prefix bound. -/
theorem factorialTailPartial_bound_at_start {C : Rat} (hC : 0 <= C) (k : Nat) :
    factorialTailPartial C (factorialTailStart C) k <=
      2 * factorialTailTerm C (factorialTailStart C) :=
  factorialTailPartial_bound hC (factorialTailStart_satisfies C) k

/-- A finite rational bound for every prefix of the nonnegative factorial
series at coefficient radius `C`.  It consists of the literal block before
the computable geometric-tail start and twice the first omitted term. -/
def factorialSeriesFiniteBound (C : Rat) : Rat :=
  factorialTailPartial C 0 (factorialTailStart C) +
    2 * factorialTailTerm C (factorialTailStart C)

theorem factorialSeriesFiniteBound_nonneg {C : Rat} (hC : 0 <= C) :
    0 <= factorialSeriesFiniteBound C := by
  unfold factorialSeriesFiniteBound
  have hpartial : 0 <= factorialTailPartial C 0 (factorialTailStart C) := by
    have hzero : factorialTailPartial C 0 0 = 0 := rfl
    rw [← hzero]
    exact factorialTailPartial_mono hC 0 0 (factorialTailStart C)
      (Nat.zero_le _)
  exact Rat.add_nonneg hpartial
    (Rat.mul_nonneg (by decide +kernel)
      (factorialTailTerm_nonneg hC _))

/-- Every finite factorial prefix from zero is bounded by the same explicit
rational initial-block-plus-tail certificate. -/
theorem factorialTailPartial_zero_le_finiteBound
    {C : Rat} (hC : 0 <= C) (n : Nat) :
    factorialTailPartial C 0 n <= factorialSeriesFiniteBound C := by
  let N := factorialTailStart C
  by_cases hn : n <= N
  · have hprefix := factorialTailPartial_mono hC 0 n N hn
    unfold factorialSeriesFiniteBound
    exact Rat.le_trans hprefix (by
      have htail : 0 <= 2 * factorialTailTerm C N :=
        Rat.mul_nonneg (by decide +kernel)
          (factorialTailTerm_nonneg hC _)
      grind)
  · have hNn : N <= n := by omega
    have hadd : N + (n - N) = n := Nat.add_sub_of_le hNn
    have htail := factorialTailPartial_bound_at_start hC (n - N)
    unfold factorialSeriesFiniteBound
    rw [← hadd, factorialTailPartial_add]
    exact rat_add_le_add (Rat.le_refl) (by simpa [N] using htail)

/-- Every shifted finite block of a nonnegative factorial series is bounded
by the same explicit whole-series certificate. -/
theorem factorialTailPartial_le_finiteBound
    {C : Rat} (hC : 0 <= C) (N n : Nat) :
    factorialTailPartial C N n <= factorialSeriesFiniteBound C := by
  have htotal := factorialTailPartial_zero_le_finiteBound hC (N + n)
  have hsplit := factorialTailPartial_add C 0 N n
  have hprefix : 0 <= factorialTailPartial C 0 N := by
    have hzero : factorialTailPartial C 0 0 = 0 := rfl
    rw [← hzero]
    exact factorialTailPartial_mono hC 0 0 N (Nat.zero_le _)
  rw [hsplit] at htotal
  exact Rat.le_trans (by grind) htotal

/- The finite prefixes of the factorial series at coefficient bound 2
are all below 8.  The first five terms total 7; the remaining finite
tail is bounded by 8/15.  This deliberately coarse uniform constant is
useful for a represented input ranging over [-2,2]. -/
theorem factorialTailPartial_two_le_eight (k : Nat) :
    factorialTailPartial 2 0 k <= 8 := by
  by_cases hk : k <= 5
  · calc
      factorialTailPartial 2 0 k <= factorialTailPartial 2 0 5 :=
        factorialTailPartial_mono (by decide +kernel) 0 k 5 hk
      _ <= 8 := by decide +kernel
  · have hfive : 5 <= k := by omega
    obtain ⟨d, hd⟩ := Nat.exists_eq_add_of_le hfive
    rw [hd, factorialTailPartial_add]
    have htail := factorialTailPartial_bound_at_start (C := (2 : Rat))
      (by decide +kernel) d
    have htail' : factorialTailPartial 2 5 d <= (8 : Rat) / 15 := by
      have hstart : factorialTailStart (2 : Rat) = 5 := by decide +kernel
      rw [hstart] at htail
      calc
        factorialTailPartial 2 5 d <= 2 * factorialTailTerm 2 5 := htail
        _ = (8 : Rat) / 15 := by decide +kernel
    calc
      factorialTailPartial 2 0 5 + factorialTailPartial 2 (0 + 5) d <=
          7 + (8 : Rat) / 15 := by
            apply rat_add_le_add
            · decide +kernel
            · simpa using htail'
      _ <= 8 := by decide +kernel

/- Absolute value commutes with every natural rational power. -/
theorem qabs_pow_eq_pow_qabs (x : Rat) : forall n : Nat,
    qabs (x ^ n) = qabs x ^ n
  | 0 => by
      have hzero : qabs (1 : Rat) = 1 := by
        rw [qabs_eq_self_of_nonneg (by decide +kernel)]
      simpa using hzero
  | n + 1 => by
      rw [Rat.pow_succ, qabs_mul, qabs_pow_eq_pow_qabs, Rat.pow_succ]

/- A rational power is bounded by the corresponding power of any
nonnegative absolute-value bound. -/
theorem qabs_pow_le_pow {x B : Rat} (hB : 0 <= B)
    (hx : qabs x <= B) (n : Nat) :
    qabs (x ^ n) <= B ^ n := by
  rw [qabs_pow_eq_pow_qabs]
  induction n with
  | zero => simp
  | succ n ih =>
      rw [Rat.pow_succ, Rat.pow_succ]
      calc
        qabs x ^ n * qabs x <= B ^ n * qabs x :=
          Rat.mul_le_mul_of_nonneg_right ih (qabs_nonneg x)
        _ <= B ^ n * B :=
          Rat.mul_le_mul_of_nonneg_left hx (Rat.pow_nonneg hB)

/-! A factorial majorant for the individual sine terms on the bounded input
range used by the `sin (pi*x)` half-period. -/

theorem sineTaylorTerm_qabs_le_factorialTailTerm
    {x : Rat} (hx : qabs x <= 2) (k : Nat) :
    qabs (FormalPowerSeries.sineTaylorTerm x k) <=
      factorialTailTerm 2 (2 * k + 1) := by
  unfold FormalPowerSeries.sineTaylorTerm factorialTailTerm
  rw [Rat.div_def, qabs_mul, qabs_mul]
  have hsign : qabs (FormalPowerSeries.altSign k) = 1 := by
    unfold FormalPowerSeries.altSign
    split <;> decide +kernel
  rw [hsign]
  have hpow : qabs (x ^ (2 * k + 1)) <=
      (2 : Rat) ^ (2 * k + 1) :=
    qabs_pow_le_pow (by decide +kernel) hx _
  have hfactor : 0 <= (factorialRat (2 * k + 1))⁻¹ := by
    exact Rat.le_of_lt ((Rat.inv_pos).2 (factorialRat_pos _))
  have hqfactor : qabs (factorialRat (2 * k + 1))⁻¹ =
      (factorialRat (2 * k + 1))⁻¹ :=
    qabs_eq_self_of_nonneg hfactor
  rw [hqfactor]
  simpa [Rat.div_def] using
    (Rat.mul_le_mul_of_nonneg_right hpow hfactor)

def sineTaylorTailPartial (x : Rat) (N : Nat) : Nat -> Rat
  | 0 => 0
  | k + 1 =>
      sineTaylorTailPartial x N k +
        FormalPowerSeries.sineTaylorTerm x (N + k)

theorem sineTaylorTailPartial_qabs_le_factorialTailPartial
    {x : Rat} (hx : qabs x <= 2) (N k : Nat) :
    qabs (sineTaylorTailPartial x N k) <=
      factorialTailPartial 2 (2 * N + 1) (2 * k) := by
  induction k with
  | zero =>
      simp [sineTaylorTailPartial, factorialTailPartial]
      decide +kernel
  | succ k ih =>
      rw [sineTaylorTailPartial]
      have hterm := sineTaylorTerm_qabs_le_factorialTailTerm hx (N + k)
      rw [show 2 * (N + k) + 1 = (2 * N + 1) + 2 * k by omega] at hterm
      rw [show 2 * (k + 1) = 2 * k + 2 by omega,
        factorialTailPartial]
      have hnonneg :
          0 <= factorialTailTerm 2 ((2 * N + 1) + (2 * k + 1)) :=
        factorialTailTerm_nonneg (by decide +kernel) _
      calc
        qabs (sineTaylorTailPartial x N k +
            FormalPowerSeries.sineTaylorTerm x (N + k)) <=
            qabs (sineTaylorTailPartial x N k) +
              qabs (FormalPowerSeries.sineTaylorTerm x (N + k)) :=
          qabs_add_le _ _
        _ <= factorialTailPartial 2 (2 * N + 1) (2 * k) +
              factorialTailTerm 2 ((2 * N + 1) + 2 * k) :=
          rat_add_le_add ih hterm
        _ <= factorialTailPartial 2 (2 * N + 1) (2 * k) +
              factorialTailTerm 2 ((2 * N + 1) + 2 * k) +
                factorialTailTerm 2 ((2 * N + 1) + (2 * k + 1)) := by
          grind [Rat.add_assoc]
        _ = factorialTailPartial 2 (2 * N + 1) (2 * k + 2) := by
          rw [factorialTailPartial, factorialTailPartial]

/- The finite difference of two rational powers has an explicit
Lipschitz bound on any symmetric rational box of radius at least one.
The proof is a direct finite recurrence, with no completed-real mean-value
theorem. -/
theorem qabs_pow_sub_le_lipschitz {x y B : Rat}
    (hB0 : 0 <= B) (hBone : 1 <= B)
    (hx : qabs x <= B) (hy : qabs y <= B) (n : Nat) :
    qabs (x ^ n - y ^ n) <=
      qabs (x - y) * (n : Rat) * B ^ n := by
  induction n with
  | zero =>
      have hdiff : x ^ 0 - y ^ 0 = (0 : Rat) := by
        rw [Rat.pow_zero, Rat.pow_zero]
        decide +kernel
      rw [hdiff, qabs_eq_self_of_nonneg (by decide +kernel)]
      change (0 : Rat) <= qabs (x - y) * (0 : Rat) * B ^ 0
      rw [Rat.mul_zero, Rat.zero_mul]
      exact Rat.le_refl
  | succ n ih =>
      have hyPow := qabs_pow_le_pow hB0 hy n
      have hdelta : 0 <= qabs (x - y) := qabs_nonneg _
      have hpow0 : 0 <= B ^ n := Rat.pow_nonneg hB0
      have hleft0 : 0 <= qabs (x - y) * (n : Rat) * B ^ n := by
        exact Rat.mul_nonneg (Rat.mul_nonneg hdelta
          (by exact_mod_cast Nat.zero_le n)) hpow0
      have hright0 : 0 <= B ^ n * qabs (x - y) :=
        Rat.mul_nonneg hpow0 hdelta
      have hdecompose :
          x ^ (n + 1) - y ^ (n + 1) =
            (x ^ n - y ^ n) * x + y ^ n * (x - y) := by
        rw [Rat.pow_succ, Rat.pow_succ]
        grind [Rat.sub_eq_add_neg, Rat.mul_add, Rat.add_mul, Rat.mul_assoc,
          Rat.mul_comm]
      rw [hdecompose]
      calc
        qabs ((x ^ n - y ^ n) * x + y ^ n * (x - y)) <=
            qabs ((x ^ n - y ^ n) * x) + qabs (y ^ n * (x - y)) :=
          qabs_add_le _ _
        _ = qabs (x ^ n - y ^ n) * qabs x +
              qabs (y ^ n) * qabs (x - y) := by
            rw [qabs_mul, qabs_mul]
        _ <= (qabs (x - y) * (n : Rat) * B ^ n) * B +
              B ^ n * qabs (x - y) :=
          rat_add_le_add
            (Rat.le_trans
              (Rat.mul_le_mul_of_nonneg_right ih (qabs_nonneg x))
              (Rat.mul_le_mul_of_nonneg_left hx hleft0))
            (Rat.mul_le_mul_of_nonneg_right hyPow hdelta)
        _ <= (qabs (x - y) * (n : Rat) * B ^ n) * B +
              (B ^ n * qabs (x - y)) * B :=
          rat_add_le_add Rat.le_refl
            (by
              calc
                B ^ n * qabs (x - y) = (B ^ n * qabs (x - y)) * 1 := by
                  rw [Rat.mul_one]
                _ <= (B ^ n * qabs (x - y)) * B :=
                  Rat.mul_le_mul_of_nonneg_left hBone hright0)
        _ = qabs (x - y) * ((n + 1 : Nat) : Rat) * B ^ (n + 1) := by
          rw [Rat.pow_succ]
          grind [Rat.mul_add, Rat.mul_assoc, Rat.mul_comm]

/- Dividing the (n+1)-st power difference by its factorial leaves the
shifted factorial majorant which will be summed in a rotation-prefix
Lipschitz certificate. -/
theorem qabs_power_div_factorial_sub_le_two {x y : Rat}
    (hx : qabs x <= 2) (hy : qabs y <= 2) (n : Nat) :
    qabs (x ^ (n + 1) / factorialRat (n + 1) -
      y ^ (n + 1) / factorialRat (n + 1)) <=
      qabs (x - y) * 2 * factorialTailTerm 2 n := by
  have hpow := qabs_pow_sub_le_lipschitz
    (x := x) (y := y) (B := (2 : Rat))
    (by decide +kernel) (by decide +kernel) hx hy (n + 1)
  have hfacpos : 0 < factorialRat (n + 1) := factorialRat_pos _
  have hinv : 0 <= (factorialRat (n + 1))⁻¹ :=
    Rat.le_of_lt ((Rat.inv_pos).2 hfacpos)
  have hrewrite :
      x ^ (n + 1) / factorialRat (n + 1) -
          y ^ (n + 1) / factorialRat (n + 1) =
        (x ^ (n + 1) - y ^ (n + 1)) * (factorialRat (n + 1))⁻¹ := by
    rw [Rat.div_def, Rat.div_def]
    grind [Rat.sub_eq_add_neg, Rat.mul_add, Rat.add_mul, Rat.mul_assoc,
      Rat.mul_comm]
  rw [hrewrite, qabs_mul, qabs_eq_self_of_nonneg hinv]
  calc
    qabs (x ^ (n + 1) - y ^ (n + 1)) *
        (factorialRat (n + 1))⁻¹ <=
        (qabs (x - y) * ((n + 1 : Nat) : Rat) * 2 ^ (n + 1)) *
          (factorialRat (n + 1))⁻¹ :=
      Rat.mul_le_mul_of_nonneg_right hpow hinv
    _ = qabs (x - y) * 2 * factorialTailTerm 2 n := by
      have hnpos : 0 < ((n + 1 : Nat) : Rat) := by
        exact (Rat.natCast_pos).2 (Nat.succ_pos n)
      have hcancel : ((n + 1 : Nat) : Rat) *
          ((n + 1 : Nat) : Rat)⁻¹ = 1 :=
        Rat.mul_inv_cancel _ (Rat.ne_of_gt hnpos)
      unfold factorialTailTerm
      rw [Rat.pow_succ, FormalPowerSeries.factorialRat_succ, Rat.div_def,
        Rat.inv_mul_rev]
      grind [Rat.mul_assoc, Rat.mul_comm]

end RationalMajorant

/-!
## Finite polynomial secants

The analytic power-series derivative theorem ultimately reduces to finite
polynomial difference quotients plus a separately certified tail.  This small
namespace records that rational algebra directly.  It deliberately does not
invoke a mean-value theorem or a completed real line.
-/

namespace FinitePolynomial

/-- The exact finite secant recurrence for the monomial `x^n`.

At successor degree it peels off the factor `x + h`; when `h` is nonzero,
`powerSecant x h n` is literally `((x+h)^n - x^n) / h`. -/
def powerSecant (x h : Rat) : Nat -> Rat
  | 0 => 0
  | n + 1 => (x + h) ^ n + x * powerSecant x h n

/-- The derivative polynomial associated with `x^n`, in recurrence form.
Keeping the zero case explicit avoids a predecessor convention at degree zero. -/
def powerDerivative (x : Rat) : Nat -> Rat
  | 0 => 0
  | n + 1 => x ^ n + x * powerDerivative x n

/-- A recursively accumulated error coefficient for the finite secant.
For inputs bounded by `C`, the error is at most this coefficient times the
absolute step. -/
def powerSecantErrorBound (C : Rat) : Nat -> Rat
  | 0 => 0
  | n + 1 => (n : Rat) * C ^ n + C * powerSecantErrorBound C n

/-- The recurrence is the exact rational difference quotient of a monomial. -/
theorem powerSecant_eq_differenceQuotient (x h : Rat) (hh : h ≠ 0) :
    forall n : Nat,
      ((x + h) ^ n - x ^ n) / h = powerSecant x h n
  | 0 => by
      simp only [Rat.pow_zero, powerSecant]
      rw [Rat.sub_self]
      rw [Rat.div_def]
      exact Rat.zero_mul _
  | n + 1 => by
      rw [Rat.pow_succ, Rat.pow_succ, powerSecant,
        ← powerSecant_eq_differenceQuotient x h hh n, Rat.div_def]
      have hcancel : h * h⁻¹ = 1 := Rat.mul_inv_cancel h hh
      grind [Rat.sub_eq_add_neg, Rat.mul_add, Rat.add_mul, Rat.mul_assoc,
        Rat.add_assoc, Rat.add_comm, Rat.mul_comm]

/-- The recurrence agrees with the familiar monomial derivative formula. -/
theorem powerDerivative_succ (x : Rat) (n : Nat) :
    powerDerivative x (n + 1) = ((n + 1 : Nat) : Rat) * x ^ n := by
  induction n with
  | zero =>
      simp [powerDerivative]
      grind
  | succ n ih =>
      rw [show n + 2 = (n + 1) + 1 by omega, powerDerivative,
        ih, Rat.pow_succ]
      have hcast : (((n + 2 : Nat) : Rat)) = (n : Rat) + 2 := by
        exact_mod_cast (by omega : n + 2 = n + 2)
      have hcast' : (((n + 1 : Nat) : Rat)) = (n : Rat) + 1 := by
        exact_mod_cast (by omega : n + 1 = n + 1)
      rw [hcast, hcast']
      grind [Rat.mul_add, Rat.add_mul, Rat.mul_assoc, Rat.mul_comm]

theorem powerSecantErrorBound_nonneg {C : Rat} (hC : 0 <= C) :
    forall n : Nat, 0 <= powerSecantErrorBound C n
  | 0 => by simp [powerSecantErrorBound]
  | n + 1 => by
      rw [powerSecantErrorBound]
      exact Rat.add_nonneg
        (Rat.mul_nonneg
          (by exact_mod_cast Nat.zero_le n)
          (Rat.pow_nonneg hC))
        (Rat.mul_nonneg hC (powerSecantErrorBound_nonneg hC n))

/-- On a rational box of radius `C >= 1`, the finite monomial secant differs
from its derivative polynomial by at most `|h|` times the explicit recursive
coefficient.  This is the quantitative finite-difference estimate needed
before taking any factorial-series tail into account. -/
theorem qabs_powerSecant_sub_powerDerivative_le
    {x h C : Rat} (hC0 : 0 <= C) (hC1 : 1 <= C)
    (hx : qabs x <= C) (hxh : qabs (x + h) <= C) :
    forall n : Nat,
      qabs (powerSecant x h n - powerDerivative x n) <=
        qabs h * powerSecantErrorBound C n
  | 0 => by
      simp only [powerSecant, powerDerivative, powerSecantErrorBound,
        Rat.mul_zero]
      rw [show (0 : Rat) - 0 = 0 by decide +kernel,
        qabs_eq_self_of_nonneg (by decide +kernel)]
      exact Rat.le_refl
  | n + 1 => by
      have hpow := RationalMajorant.qabs_pow_sub_le_lipschitz
        (x := x + h) (y := x) (B := C) hC0 hC1 hxh hx n
      have hstep : qabs ((x + h) - x) = qabs h := by
        have heq : (x + h) - x = h := by
          grind [Rat.sub_eq_add_neg]
        rw [heq]
      rw [hstep] at hpow
      have hbound0 : 0 <= powerSecantErrorBound C n :=
        powerSecantErrorBound_nonneg hC0 n
      have hh0 : 0 <= qabs h := qabs_nonneg _
      have hproduct0 : 0 <= qabs h * powerSecantErrorBound C n :=
        Rat.mul_nonneg hh0 hbound0
      have hrec := qabs_powerSecant_sub_powerDerivative_le
        hC0 hC1 hx hxh n
      have hscaled :
          qabs x * qabs (powerSecant x h n - powerDerivative x n) <=
            C * (qabs h * powerSecantErrorBound C n) := by
        calc
          qabs x * qabs (powerSecant x h n - powerDerivative x n) <=
              qabs x * (qabs h * powerSecantErrorBound C n) :=
            Rat.mul_le_mul_of_nonneg_left hrec (qabs_nonneg x)
          _ <= C * (qabs h * powerSecantErrorBound C n) :=
            Rat.mul_le_mul_of_nonneg_right hx hproduct0
      have hdecompose :
          powerSecant x h (n + 1) - powerDerivative x (n + 1) =
            ((x + h) ^ n - x ^ n) +
              x * (powerSecant x h n - powerDerivative x n) := by
        rw [powerSecant, powerDerivative]
        grind [Rat.sub_eq_add_neg, Rat.mul_add, Rat.add_mul, Rat.add_assoc,
          Rat.add_comm, Rat.mul_assoc, Rat.mul_comm]
      rw [hdecompose]
      calc
        qabs
            ((x + h) ^ n - x ^ n +
              x * (powerSecant x h n - powerDerivative x n)) <=
            qabs ((x + h) ^ n - x ^ n) +
              qabs (x * (powerSecant x h n - powerDerivative x n)) :=
          qabs_add_le _ _
        _ = qabs ((x + h) ^ n - x ^ n) +
              qabs x * qabs (powerSecant x h n - powerDerivative x n) := by
          rw [qabs_mul]
        _ <= qabs h * (n : Rat) * C ^ n +
              C * (qabs h * powerSecantErrorBound C n) :=
          rat_add_le_add hpow hscaled
        _ = qabs h * powerSecantErrorBound C (n + 1) := by
          rw [powerSecantErrorBound]
          grind [Rat.mul_add, Rat.mul_assoc, Rat.mul_comm]

/-- The preceding estimate written directly for the literal rational quotient. -/
theorem qabs_power_differenceQuotient_sub_derivative_le
    {x h C : Rat} (hh : h ≠ 0) (hC0 : 0 <= C) (hC1 : 1 <= C)
    (hx : qabs x <= C) (hxh : qabs (x + h) <= C) (n : Nat) :
    qabs (((x + h) ^ n - x ^ n) / h - powerDerivative x n) <=
      qabs h * powerSecantErrorBound C n := by
  rw [powerSecant_eq_differenceQuotient x h hh n]
  exact qabs_powerSecant_sub_powerDerivative_le hC0 hC1 hx hxh n

/-- The conventional normalized monomial form of the finite secant estimate.
Thus the rational polynomial `x^(n+1)/(n+1)` has derivative `x^n` with an
explicit linear-in-`|h|` error on every supplied bounded box. -/
theorem qabs_normalized_power_differenceQuotient_sub_monomial_le
    {x h C : Rat} (hh : h ≠ 0) (hC0 : 0 <= C) (hC1 : 1 <= C)
    (hx : qabs x <= C) (hxh : qabs (x + h) <= C) (n : Nat) :
    qabs
        ((((x + h) ^ (n + 1) / ((n + 1 : Nat) : Rat)) -
          x ^ (n + 1) / ((n + 1 : Nat) : Rat)) / h - x ^ n) <=
      qabs h * powerSecantErrorBound C (n + 1) := by
  let d : Rat := ((n + 1 : Nat) : Rat)
  have hdpos : 0 < d := by
    dsimp [d]
    exact (Rat.natCast_pos).2 (Nat.succ_pos n)
  have hdne : d ≠ 0 := Rat.ne_of_gt hdpos
  have hdone : (1 : Rat) <= d := by
    dsimp [d]
    exact_mod_cast (Nat.succ_le_succ (Nat.zero_le n))
  have hinv0 : 0 <= d⁻¹ := Rat.le_of_lt ((Rat.inv_pos).2 hdpos)
  have hinvle : d⁻¹ <= 1 := by
    apply Rat.le_of_mul_le_mul_right (c := d)
    · calc
        d⁻¹ * d = 1 := Rat.inv_mul_cancel d hdne
        _ <= 1 * d := by simpa using hdone
    · exact hdpos
  have hraw := qabs_power_differenceQuotient_sub_derivative_le
    (x := x) (h := h) (C := C) hh hC0 hC1 hx hxh (n + 1)
  rw [powerDerivative_succ] at hraw
  have hrewrite :
      ((x + h) ^ (n + 1) / d - x ^ (n + 1) / d) / h - x ^ n =
        (((x + h) ^ (n + 1) - x ^ (n + 1)) / h - d * x ^ n) * d⁻¹ := by
    rw [Rat.div_def, Rat.div_def, Rat.div_def, Rat.div_def]
    have hcancel : d * d⁻¹ = 1 := Rat.mul_inv_cancel d hdne
    grind [Rat.sub_eq_add_neg, Rat.mul_add, Rat.add_mul, Rat.mul_assoc,
      Rat.add_assoc, Rat.add_comm, Rat.mul_comm]
  have hbound0 : 0 <= powerSecantErrorBound C (n + 1) :=
    powerSecantErrorBound_nonneg hC0 _
  have hright0 : 0 <= qabs h * powerSecantErrorBound C (n + 1) :=
    Rat.mul_nonneg (qabs_nonneg _) hbound0
  change qabs
      (((x + h) ^ (n + 1) / d - x ^ (n + 1) / d) / h - x ^ n) <= _
  rw [hrewrite, qabs_mul, qabs_eq_self_of_nonneg hinv0]
  calc
    qabs (((x + h) ^ (n + 1) - x ^ (n + 1)) / h - d * x ^ n) * d⁻¹ <=
        (qabs h * powerSecantErrorBound C (n + 1)) * d⁻¹ :=
      Rat.mul_le_mul_of_nonneg_right hraw hinv0
    _ <= (qabs h * powerSecantErrorBound C (n + 1)) * 1 :=
      Rat.mul_le_mul_of_nonneg_left hinvle hright0
    _ = qabs h * powerSecantErrorBound C (n + 1) := by rw [Rat.mul_one]

end FinitePolynomial

namespace ComplexSeries

def expTerm (z : QComplex) (n : Nat) : QComplex :=
  QComplex.divRat (QComplex.pow z n) (factorialRat n)

def expPartial (z : QComplex) (n : Nat) : QComplex :=
  (List.range n).foldl (fun acc k => QComplex.add acc (expTerm z k)) QComplex.zero

def sinSign (k : Nat) : Rat := if k % 2 = 0 then 1 else -1

def sinTerm (z : QComplex) (k : Nat) : QComplex :=
  QComplex.scaleRat (sinSign k)
    (QComplex.divRat (QComplex.pow z (2 * k + 1)) (factorialRat (2 * k + 1)))

def sinPartial (z : QComplex) (n : Nat) : QComplex :=
  (List.range n).foldl (fun acc k => QComplex.add acc (sinTerm z k)) QComplex.zero

def cosTerm (z : QComplex) (k : Nat) : QComplex :=
  QComplex.scaleRat (sinSign k)
    (QComplex.divRat (QComplex.pow z (2 * k)) (factorialRat (2 * k)))

def cosPartial (z : QComplex) (n : Nat) : QComplex :=
  (List.range n).foldl (fun acc k => QComplex.add acc (cosTerm z k)) QComplex.zero

def errorBox (center : QComplex) (eps : QPos) : QBox :=
  { lo := { re := center.re - eps.val, im := center.im - eps.val },
    hi := { re := center.re + eps.val, im := center.im + eps.val } }

def expBoxAt (z : QComplex) (eps : QPos) : QBox :=
  errorBox (expPartial z (seriesFuel eps)) eps

def sinBoxAt (z : QComplex) (eps : QPos) : QBox :=
  errorBox (sinPartial z (seriesFuel eps)) eps

def cosBoxAt (z : QComplex) (eps : QPos) : QBox :=
  errorBox (cosPartial z (seriesFuel eps)) eps

def expCompute (z : ComplexCompute) : Nat -> QBox :=
  fun n =>
    let eps : 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) }
    expBoxAt ((z.compute n).center) eps

def sinCompute (z : ComplexCompute) : Nat -> QBox :=
  fun n =>
    let eps : 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) }
    sinBoxAt ((z.compute n).center) eps

def cosCompute (z : ComplexCompute) : Nat -> QBox :=
  fun n =>
    let eps : 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) }
    cosBoxAt ((z.compute n).center) eps

def expAt (z : QComplex) : Nat -> QBox :=
  expCompute (ComplexCompute.ofQComplex z)

def sinAt (z : QComplex) : Nat -> QBox :=
  sinCompute (ComplexCompute.ofQComplex z)

def cosAt (z : QComplex) : Nat -> QBox :=
  cosCompute (ComplexCompute.ofQComplex z)

/-- Certification target: the explicit exponential series boxes form a valid
complex raw algorithm.  Proving this requires a rational tail bound and a
nesting argument. -/
def ExpCertified (z : ComplexCompute) : Prop :=
  ComplexCompute.Valid { compute := expCompute z }

/-- Certification target for sine. -/
def SinCertified (z : ComplexCompute) : Prop :=
  ComplexCompute.Valid { compute := sinCompute z }

/-- Certification target for cosine. -/
def CosCertified (z : ComplexCompute) : Prop :=
  ComplexCompute.Valid { compute := cosCompute z }

def ExpTailBound : Prop :=
  forall z eps,
    QBox.Overlaps (expBoxAt z eps) (errorBox (expPartial z (seriesFuel eps + 1)) eps)

def SinTailBound : Prop :=
  forall z eps,
    QBox.Overlaps (sinBoxAt z eps) (errorBox (sinPartial z (seriesFuel eps + 1)) eps)

def CosTailBound : Prop :=
  forall z eps,
    QBox.Overlaps (cosBoxAt z eps) (errorBox (cosPartial z (seriesFuel eps + 1)) eps)

end ComplexSeries

namespace RealSeries

def restrictRealAt (f : QComplex -> Nat -> QBox) (x : Rat) (n : Nat) : QInterval :=
  let B := f (QComplex.ofRat x) n
  { lo := B.lo.re, hi := B.hi.re }

def expCompute (x : Rat) (n : Nat) : QInterval :=
  restrictRealAt ComplexSeries.expAt x n

def sinCompute (x : Rat) (n : Nat) : QInterval :=
  restrictRealAt ComplexSeries.sinAt x n

def cosCompute (x : Rat) (n : Nat) : QInterval :=
  restrictRealAt ComplexSeries.cosAt x n

def expFunRaw : RealFunRaw where
  compute := expCompute

def sinFunRaw : RealFunRaw where
  compute := sinCompute

def cosFunRaw : RealFunRaw where
  compute := cosCompute

def ExpCertified : Prop := expFunRaw.Valid
def SinCertified : Prop := sinFunRaw.Valid
def CosCertified : Prop := cosFunRaw.Valid

def ExpConverges : Prop :=
  ComplexSeries.ExpTailBound /\ ExpCertified

def SinConverges : Prop :=
  ComplexSeries.SinTailBound /\ SinCertified

def CosConverges : Prop :=
  ComplexSeries.CosTailBound /\ CosCertified

end RealSeries

/-- Arctangent from its alternating power series. -/
def arctan (x : Rat) : RealCompute where
  compute := fun n =>
    let y := qabs x
    let state : Rat × Rat := Id.run do
      let mut lo : Rat := 0
      let mut hi : Rat := y
      let mut yPow : Rat := y * y * y
      for i in List.range n do
        let term1 : Rat := yPow / (4 * i + 3)
        yPow := yPow * y * y
        let term2 : Rat := yPow / (4 * i + 5)
        yPow := yPow * y * y
        lo := hi - term1
        hi := lo + term2
      return (lo, hi)
    if 0 <= x then
      { lo := state.1, hi := state.2 }
    else
      { lo := -state.2, hi := -state.1 }

/-- Table-facing name for the arctangent power-series evaluator.

The older proofs keep the shorter name `arctan`; this alias makes explicit that
this construction is the alternating power-series arctangent, distinct from the
geometric and integral arctangent constructions. -/
def arctanSeries (x : Rat) : RealCompute :=
  arctan x

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