{-# OPTIONS --safe --cubical-compatible --guardedness --exact-split --double-check #-}
module Real.Interval.Series.Bounds where
open import Data.Nat using (ℕ; zero; suc) renaming (_+_ to _+ℕ_)
open import Data.Nat.Properties using (+-identityʳ; +-suc)
open import Data.Rational using (ℚ; 0ℚ; 1ℚ; _+_; _*_; _≤_)
open import Data.Rational.Properties as ℚP using
(+-assoc; +-identityˡ; +-mono-≤; +-monoʳ-≤; ≤-refl; ≤-trans; *-comm
; *-distribˡ-+; *-identityʳ; *-zeroʳ)
open import Relation.Binary.PropositionalEquality using
(_≡_; refl; sym; trans; cong; cong₂; subst; module ≡-Reasoning)
open ≡-Reasoning
open import Real using (2ℚ; half; 0≤embed)
open import Real.IntervalEquiv using (recipPow2)
open import Real.Interval using (RealI)
open import Real.Interval.Arith using (0ℝ; _+ℝ_)
open import Real.Interval.ArithLaws using (+ℝ-comm; +ℝ-assoc; +ℝ-identityʳ)
open import Real.Interval.Equiv using (_≈ℝ_; ≈ℝ-refl; ≈ℝ-sym; ≈ℝ-trans)
open import Real.Interval.Kit using
(recipPow2-mul; 0≤recipPow2; *-mono-≤-nonNeg; add-self; two-half)
open import Real.Interval.Mul.Order using (+ℝ-cong)
open import Real.Interval.OrderLe using (≤ℝ-refl; ≤ℝ-resp-≈)
open import Real.Interval.OrderComplete.Base using (_≤ℝ_; ≤ℝ-trans)
open import Real.Interval.Series.Core using (sum; x≤x+y)
tail : (ℕ → RealI) → ℕ → ℕ → RealI
tail f n zero = 0ℝ
tail f n (suc d) = tail f n d +ℝ f (n +ℕ d)
sum-split : (f : ℕ → RealI) (n d : ℕ)
→ sum f (n +ℕ d) ≈ℝ sum f n +ℝ tail f n d
sum-split f n zero =
subst (λ k → sum f k ≈ℝ sum f n +ℝ 0ℝ) (sym (+-identityʳ n))
(≈ℝ-sym (+ℝ-identityʳ (sum f n)))
sum-split f n (suc d) =
subst (λ k → sum f k ≈ℝ sum f n +ℝ tail f n (suc d))
(sym (+-suc n d))
(≈ℝ-trans (+ℝ-cong (sum-split f n d) ≈ℝ-refl)
(+ℝ-assoc (sum f n) (tail f n d) (f (n +ℕ d))))
tail-nonNeg : (f : ℕ → RealI) (0≤f : ∀ n → 0ℝ ≤ℝ f n) (n d : ℕ)
→ 0ℝ ≤ℝ tail f n d
tail-nonNeg f 0≤f n zero = ≤ℝ-refl
tail-nonNeg f 0≤f n (suc d) =
≤ℝ-trans (0≤f (n +ℕ d))
(≤ℝ-resp-≈ ≈ℝ-refl (+ℝ-comm (f (n +ℕ d)) (tail f n d))
(x≤x+y (f (n +ℕ d)) (tail f n d) (tail-nonNeg f 0≤f n d)))
geom : ℕ → ℚ
geom zero = 0ℚ
geom (suc n) = geom n + recipPow2 n
recipPow2-1 : recipPow2 1 ≡ half
recipPow2-1 = refl
recipPow2-0 : recipPow2 0 ≡ 1ℚ
recipPow2-0 = refl
recipPow2-suc : (n : ℕ) → recipPow2 (suc n) ≡ recipPow2 n * half
recipPow2-suc n =
trans (subst (λ k → recipPow2 k ≡ recipPow2 n * recipPow2 1)
(trans (+-suc n zero) (cong suc (+-identityʳ n)))
(recipPow2-mul n 1))
(cong (recipPow2 n *_) recipPow2-1)
two-mul : (r : ℚ) → 2ℚ * (r * half) ≡ r
two-mul r = trans (sym (add-self (r * half))) (two-half r)
two-mul-add : (r : ℚ) → 2ℚ * r ≡ r + r
two-mul-add r = sym (add-self r)
geom-closed : (n : ℕ) → geom n + 2ℚ * recipPow2 n ≡ 2ℚ
geom-closed zero = begin
0ℚ + 2ℚ * recipPow2 0 ≡⟨ cong (λ z → 0ℚ + 2ℚ * z) recipPow2-0 ⟩
0ℚ + 2ℚ * 1ℚ ≡⟨ cong (0ℚ +_) (*-identityʳ 2ℚ) ⟩
0ℚ + 2ℚ ≡⟨ +-identityˡ 2ℚ ⟩
2ℚ ∎
geom-closed (suc n) = begin
geom (suc n) + 2ℚ * recipPow2 (suc n)
≡⟨ cong (λ z → (geom n + recipPow2 n) + 2ℚ * z) (recipPow2-suc n) ⟩
(geom n + recipPow2 n) + 2ℚ * (recipPow2 n * half)
≡⟨ cong (λ z → (geom n + recipPow2 n) + z) (two-mul (recipPow2 n)) ⟩
(geom n + recipPow2 n) + recipPow2 n
≡⟨ +-assoc (geom n) (recipPow2 n) (recipPow2 n) ⟩
geom n + (recipPow2 n + recipPow2 n)
≡⟨ cong (geom n +_) (sym (two-mul-add (recipPow2 n))) ⟩
geom n + 2ℚ * recipPow2 n
≡⟨ geom-closed n ⟩
2ℚ ∎
geom-shift : (n d : ℕ) → geom (n +ℕ d) ≡ geom n + recipPow2 n * geom d
geom-shift n zero = begin
geom (n +ℕ zero) ≡⟨ cong geom (+-identityʳ n) ⟩
geom n ≡⟨ sym (ℚP.+-identityʳ (geom n)) ⟩
geom n + 0ℚ ≡⟨ cong (geom n +_) (sym (*-zeroʳ (recipPow2 n))) ⟩
geom n + recipPow2 n * 0ℚ ∎
geom-shift n (suc d) = begin
geom (n +ℕ suc d)
≡⟨ cong geom (+-suc n d) ⟩
geom (n +ℕ d) + recipPow2 (n +ℕ d)
≡⟨ cong₂ _+_ (geom-shift n d) (recipPow2-mul n d) ⟩
(geom n + recipPow2 n * geom d) + (recipPow2 n * recipPow2 d)
≡⟨ +-assoc (geom n) (recipPow2 n * geom d) (recipPow2 n * recipPow2 d) ⟩
geom n + (recipPow2 n * geom d + recipPow2 n * recipPow2 d)
≡⟨ cong (geom n +_) (sym (*-distribˡ-+ (recipPow2 n) (geom d) (recipPow2 d))) ⟩
geom n + recipPow2 n * (geom d + recipPow2 d)
≡⟨ refl ⟩
geom n + recipPow2 n * geom (suc d)
∎
0≤2ℚ : 0ℚ ≤ 2ℚ
0≤2ℚ = 0≤embed 2
two-nonNeg : (n : ℕ) → 0ℚ ≤ 2ℚ * recipPow2 n
two-nonNeg n =
≤-trans (subst (λ z → 0ℚ ≤ z) (sym (*-zeroʳ 2ℚ)) (≤-refl {0ℚ}))
(*-mono-≤-nonNeg {a = 2ℚ} {a' = 2ℚ} {b = 0ℚ} {b' = recipPow2 n}
0≤2ℚ ≤-refl (≤-refl {0ℚ}) (0≤recipPow2 n))
geom-nonNeg : (n : ℕ) → 0ℚ ≤ geom n
geom-nonNeg zero = ≤-refl
geom-nonNeg (suc n) = +-mono-≤ (geom-nonNeg n) (0≤recipPow2 n)
le-self-add : {p q : ℚ} → 0ℚ ≤ q → p ≤ p + q
le-self-add {p} {q} 0≤q =
subst (λ z → z ≤ p + q) (ℚP.+-identityʳ p) (+-monoʳ-≤ p 0≤q)
geom-le : (n : ℕ) → geom n ≤ 2ℚ
geom-le n =
subst (λ z → geom n ≤ z) (geom-closed n) (le-self-add (two-nonNeg n))
geom-scaled-le : (n d : ℕ) → recipPow2 n * geom d ≤ 2ℚ * recipPow2 n
geom-scaled-le n d =
subst (λ z → recipPow2 n * geom d ≤ z) (*-comm (recipPow2 n) 2ℚ)
(*-mono-≤-nonNeg {a = recipPow2 n} {a' = recipPow2 n} {b = geom d} {b' = 2ℚ}
(0≤recipPow2 n) ≤-refl (geom-nonNeg d) (geom-le d))
geom-suffix-le : (n d : ℕ) → geom (n +ℕ d) ≤ geom n + 2ℚ * recipPow2 n
geom-suffix-le n d =
subst (λ z → z ≤ geom n + 2ℚ * recipPow2 n) (sym (geom-shift n d))
(+-monoʳ-≤ (geom n) (geom-scaled-le n d))