Computable analysis · RepeatedFTC · fd889115 k1
Definitionliuyao_ca_fd889115_k1_Analysis_RepeatedFTCca-fd889115-k1
Private dependency for the Distribution Theory mission. Module ComputableAnalysis/RepeatedFTC.lean from the frozen computable-analysis foundation with kernel-checked rational decision proofs.
Definition code
import Definitions.Def_liuyao_ca_fd889115_k1_Analysis_FTCMonomials
set_option autoImplicit true
/-! Taylor's finite development by repeated definite-integral FTC.
The input is an actual derivative family. Polynomial terms are generated by
integrating the preceding constants/monomials. At each stage the remaining
term is proved to be the integral of the next preceding remainder. -/
namespace ComputableAnalysis.RepeatedFTC
open ComputableCoefficient RealApproximationOrder FTCRealOrder FTCRealCalculus FTCMonomials
set_option maxHeartbeats 800000
/-- Terms produced by successive integrations of the derivative initial values. -/
def polynomial (F : Nat → Rat → Value) : Nat → Nat → Rat → Value
| 0,_,_ => Value.rational 0
| n+1,k,t => Value.add (polynomial F n k t) (scale (term n t) (F (k+n) 0))
def remainder (F : Nat → Rat → Value) (n k : Nat) (t : Rat) : Value :=
sub (F k t) (polynomial F n k t)
private theorem term_degree_zero (t : Rat) : term 0 t=1 := by
unfold term
rw [Rat.pow_zero]
change (1:Rat)/1=1
decide +kernel
theorem polynomial_zero_samples (F : Nat → Rat → Value) (n k : Nat) (s : RealCompute.Certified → Rat) :
(polynomial F (n+1) k 0).sample s=(F k 0).sample s := by
induction n with
| zero =>
simp only [polynomial,Value.add,Value.rational,scale,term_zero_zero,Nat.add_zero]
grind only
| succ n ih =>
change (polynomial F (n+1) k 0).sample s+term (n+1) 0*(F (k+(n+1)) 0).sample s=_
rw [term_zero_succ,Rat.zero_mul,Rat.add_zero,ih]
theorem remainder_zero_samples (F : Nat → Rat → Value) (n k : Nat) (s : RealCompute.Certified → Rat) :
(remainder F (n+1) k 0).sample s=0 := by
simp only [remainder,sub,polynomial_zero_samples,Rat.sub_self]
/-- The next polynomial is obtained by integrating the preceding polynomial
and adding the actual initial derivative value. The FTC step is checked. -/
def polynomial_step (F : Nat → Rat → Value) (B : Rat) (hB : 0≤B)
(bound : ∀ k t, 0≤t → t≤1 → Small (F k t) (B^k)) (n k : Nat) :
Step (polynomial F (n+1) k) (polynomial F n (k+1)) 0 1 := by
induction n generalizing k with
| zero =>
apply (Step.constant (F k 0) 0 1).congr
· intro t
apply arithmetic_identity
intro s
simp only [polynomial,Value.add,Value.rational,scale,term_degree_zero,Nat.add_zero]
grind only
· intro t
exact RealCompute.equiv_refl _ (RealCompute.ofRat_valid 0)
| succ n ih =>
let T := FTCMonomials.coefficient n (F (k+(n+1)) 0) (B^(k+(n+1)))
(Rat.pow_nonneg hB) (bound _ 0 (by decide +kernel) (by decide +kernel))
apply ((ih k).add T).congr
· intro t
exact RealCompute.equiv_refl _ (polynomial F (n+2) k t).real.valid
· intro t
have idx : k+(n+1)=(k+1)+n := by omega
apply arithmetic_identity
intro s
simp only [polynomial,Value.add,scale,idx]
/-- Subtract the terms already generated by integration. Its derivative is
the preceding remainder of the next actual derivative. -/
def remainder_step (F : Nat → Rat → Value)
(steps : ∀ k, Step (F k) (F (k+1)) 0 1) (B : Rat) (hB : 0≤B)
(bound : ∀ k t, 0≤t → t≤1 → Small (F k t) (B^k)) (n k : Nat) :
Step (remainder F (n+1) k) (remainder F n (k+1)) 0 1 :=
(steps k).subtract (polynomial_step F B hB bound n k)
/-- The remainder is a genuine definite integral of the preceding remainder.
This is the repeated-FTC substitution, with the initial endpoint eliminated
by its proved zero value. No integral identity is a record assumption. -/
theorem remainder_hasIntegral (F : Nat → Rat → Value)
(steps : ∀ k, Step (F k) (F (k+1)) 0 1) (B : Rat) (hB : 0≤B)
(bound : ∀ k t, 0≤t → t≤1 → Small (F k t) (B^k)) (n k : Nat)
(t : Rat) (ht : 0≤t) (ht' : t≤1) :
Integral.HasIntegral
(LipschitzIntegralBounds.onInterval (remainder F n (k+1)) 0 t)
(remainder F (n+1) k t).real.preferred := by
have H := ((remainder_step F steps B hB bound n k).restrict 0 t (by decide +kernel) ht').hasIntegral ht
apply H.congr (remainder F (n+1) k t).real.valid
apply arithmetic_identity (sub (remainder F (n+1) k t) (remainder F (n+1) k 0)) (remainder F (n+1) k t)
intro s
simp only [sub,remainder_zero_samples]
grind only
private theorem nonnegative_at_zero {f d : Rat → Value} (S : Step f d 0 1)
(zero : ∀ s, (f 0).sample s=0) (t : Rat) (ht : 0≤t) (ht' : t≤1)
(positive : ∀ u, 0≤u → u≤t → LE (Value.rational 0) (d u)) :
LE (Value.rational 0) (f t) := by
have H := (S.restrict 0 t (by decide +kernel) ht').nonnegative ht positive
apply le_congr H (RealCompute.equiv_refl _ (RealCompute.ofRat_valid 0))
apply arithmetic_identity (sub (f t) (f 0)) (f t)
intro s
simp only [sub,zero]
grind only
private def majorant (n : Nat) (C : Rat) :
Step (fun t => Value.rational (C*term (n+1) t)) (fun t => Value.rational (C*term n t)) 0 1 := by
apply ((FTCMonomials.factorial n).scale C).congr
· intro t
apply arithmetic_identity
intro s
simp only [scale,Value.rational]
· intro t
apply arithmetic_identity
intro s
simp only [scale,Value.rational]
/-- Repeated FTC bounds each successive integral by the integrated preceding
majorant. The factorial is produced by those integrations. -/
theorem remainder_bound (F : Nat → Rat → Value)
(steps : ∀ k, Step (F k) (F (k+1)) 0 1) (B : Rat) (hB : 0≤B)
(bound : ∀ k t, 0≤t → t≤1 → Small (F k t) (B^k)) (n k : Nat)
(t : Rat) (ht : 0≤t) (ht' : t≤1) :
Small (remainder F n k t) (B^(k+n)*term n t) := by
induction n generalizing k t with
| zero =>
simp only [Nat.add_zero,term_degree_zero,Rat.mul_one]
apply (bound k t ht ht').congr
apply arithmetic_identity
intro s
simp only [remainder,polynomial,sub,Value.rational]
grind only
| succ n ih =>
let C := B^(k+n+1)
let S := remainder_step F steps B hB bound n k
let G := majorant n C
have bnd (u : Rat) (hu : 0≤u) (hu' : u≤t) : Small (remainder F n (k+1) u) (C*term n u) := by
have H := ih (k+1) u hu (by grind only)
have idx : k+1+n=k+n+1 := by omega
simpa only [idx] using H
have upper := nonnegative_at_zero (G.subtract S) (by
intro s
simp only [sub,Value.rational,term_zero_succ,remainder_zero_samples,Rat.mul_zero,Rat.sub_self]) t ht ht' (by
intro u hu hu'
have H := (bnd u hu hu').2
intro i j
have h := H j 0
change ((remainder F n (k+1) u).real.preferred.compute j).lo≤C*term n u at h
change 0≤C*term n u-((remainder F n (k+1) u).real.preferred.compute j).lo
grind only)
have lower := nonnegative_at_zero (G.add S) (by
intro s
simp only [Value.add,Value.rational,term_zero_succ,remainder_zero_samples,Rat.mul_zero,Rat.add_zero]) t ht ht' (by
intro u hu hu'
have H := (bnd u hu hu').1
intro i j
have h := H 0 j
change -(C*term n u)≤((remainder F n (k+1) u).real.preferred.compute j).hi at h
change 0≤C*term n u+((remainder F n (k+1) u).real.preferred.compute j).hi
grind only)
have idx : k+(n+1)=k+n+1 := by omega
rw [idx]
constructor
· intro i j
have h := lower 0 j
change 0≤C*term (n+1) t+((remainder F (n+1) k t).real.preferred.compute j).hi at h
change -(C*term (n+1) t)≤_
grind only
· intro i j
have h := upper 0 i
change 0≤C*term (n+1) t-((remainder F (n+1) k t).real.preferred.compute i).lo at h
change _≤C*term (n+1) t
grind only
theorem finite_development (F : Nat → Rat → Value) (n k : Nat) (t : Rat) :
(F k t).real.preferred.Equiv
(Value.add (polynomial F n k t) (remainder F n k t)).real.preferred := by
apply arithmetic_identity
intro s
simp only [Value.add,remainder,sub]
grind only
end ComputableAnalysis.RepeatedFTC