Computable analysis · PowerSeries · fd889115 k1
Definitionliuyao_ca_fd889115_k1_Analysis_PowerSeriesca-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