{-# OPTIONS --safe --cubical-compatible --guardedness --exact-split --double-check #-}
module Real.Interval.Sqrt.Located where
open import Data.Nat using (ℕ; _⊔_) renaming (_≤_ to _≤ℕ_; _*_ to _ℕ*_)
open import Data.Nat.Properties as Nat using (m≤m⊔n; m≤n⊔m)
open import Data.Product using (Σ; _×_; _,_; proj₁; proj₂)
open import Data.Rational using (ℚ; 0ℚ; _+_; _-_; _*_; _<_; _≤_)
open import Data.Rational.Base using (-_)
open import Data.Rational.Properties using
(≤-trans; <⇒≤; ≤-<-trans; <-≤-trans; <-trans; +-mono-<-≤; +-comm; ≮⇒≥; <-cmp)
open import Data.Sum.Base using (_⊎_; inj₁; inj₂; [_,_])
open import Relation.Binary.Definitions using (tri<; tri≈; tri>)
open import Relation.Binary.PropositionalEquality using (_≡_; sym; subst; subst₂)
open import Relation.Nullary.Negation using (¬_)
open import Real.Interval using (RealI; embedℚ; δ)
open import Real.IntervalEquiv using (node; l; u; width; l-mono; u-mono)
open import Real.Interval.Arith using (0ℝ)
open import Real.Interval.Continuity using (0<embedℚ; embedℚ-mono)
open import Real.Interval.Embed using (embedℚ-*)
open import Real.Interval.Equiv using (_≈ℝ_; ≈ℝ-sym)
open import Real.Interval.Mul using (_*ℝ_)
open import Real.Interval.Mul.Laws using (*ℝ-zeroˡ)
open import Real.Interval.Mul.Order using (u-prod-corner; u-nonNeg; δ-below)
open import Real.Interval.Node using (l-dyadic)
open import Real.Interval.Order using (_<ℝ_)
open import Real.Interval.OrderComplete.Base using
(Subset; Upper; Occupied; Located; _≤ℝ_; a+d≡b)
open import Real.Interval.OrderLe using (≤ℝ-refl; <⇒≤ℝ; <-≤ℝ-trans)
open import Real.Interval.OrderLaws using (≈-<-resp; width-below-strict)
open import Real.Interval.Sqrt.Bounds using
(sq-widen; decide-below; l-layer-≤; sq-<; sub-pos; sub-lt-swap
; sq-gap-pos)
module _ (y : RealI) (0<y : 0ℝ <ℝ y) where
P : Subset
P x = (0ℝ ≤ℝ x) × (x *ℝ x <ℝ y)
P-0 : P 0ℝ
P-0 = ≤ℝ-refl , ≈-<-resp (≈ℝ-sym (*ℝ-zeroˡ 0ℝ)) 0<y
embed-below-zero : (p : ℚ) → p < 0ℚ → embedℚ p <ℝ 0ℝ
embed-below-zero p p<0 = embedℚ-mono p 0ℚ p<0
occupied-below : (p : ℚ) (k : ℕ) → 0ℚ ≤ p → p * p < l y k
→ Occupied P p
occupied-below p k 0≤p pp<ly =
let
r , p<r , rr<ly = sq-widen p (l y k) 0≤p pp<ly
0<r : 0ℚ < r
0<r = ≤-<-trans 0≤p p<r
0≤x : 0ℝ ≤ℝ embedℚ r
0≤x = <⇒≤ℝ (0<embedℚ r 0<r)
x-sq≈ : embedℚ r *ℝ embedℚ r ≈ℝ embedℚ (r * r)
x-sq≈ = ≈ℝ-sym (embedℚ-* r r)
rr<y : embedℚ (r * r) <ℝ y
rr<y = <-≤ℝ-trans (embedℚ-mono (r * r) (l y k) rr<ly) (l-layer-≤ y k)
sq<y : embedℚ r *ℝ embedℚ r <ℝ y
sq<y = ≈-<-resp (≈ℝ-sym x-sq≈) rr<y
p<x : embedℚ p <ℝ embedℚ r
p<x = embedℚ-mono p r p<r
in
embedℚ r , (0≤x , sq<y) , p<x
upper-above : (p q : ℚ) (k : ℕ) → 0ℚ ≤ p → p < q
→ width y k < q * q - p * p
→ ¬ (p * p < l y k) → Upper P q
upper-above p q k 0≤p p<q wk<gap ¬lt x (x≥0 , xx<y) =
let
0<q : 0ℚ < q
0<q = ≤-<-trans 0≤p p<q
lyk≤pp : l y k ≤ p * p
lyk≤pp = ≮⇒≥ ¬lt
m : ℕ
m = proj₁ xx<y
uxxm<lym : u (x *ℝ x) m < l y m
uxxm<lym = proj₂ xx<y
K : ℕ
K = k ⊔ m
k≤K : k ≤ℕ K
k≤K = m≤m⊔n k m
m≤K : m ≤ℕ K
m≤K = m≤n⊔m k m
l+w≡u : l y k + width y k ≡ u y k
l+w≡u = a+d≡b (l y k) (u y k)
lwk<pp+gap : l y k + width y k < p * p + (q * q - p * p)
lwk<pp+gap =
subst₂ _<_
(+-comm (width y k) (l y k))
(+-comm (q * q - p * p) (p * p))
(+-mono-<-≤ wk<gap lyk≤pp)
pp+gap≡q2 : p * p + (q * q - p * p) ≡ q * q
pp+gap≡q2 = a+d≡b (p * p) (q * q)
uyk<q2 : u y k < q * q
uyk<q2 =
subst (λ z → z < q * q) l+w≡u
(subst (λ z → l y k + width y k < z) pp+gap≡q2 lwk<pp+gap)
lyK≤uyK : l y K ≤ u y K
lyK≤uyK = <⇒≤ (RealI.lo (node y K))
uyK≤uyk : u y K ≤ u y k
uyK≤uyk = u-mono y k≤K
lyK<q2 : l y K < q * q
lyK<q2 = ≤-<-trans lyK≤uyK (≤-<-trans uyK≤uyk uyk<q2)
u2K²≤uxxK : u x (2 ℕ* K) * u x (2 ℕ* K) ≤ u (x *ℝ x) K
u2K²≤uxxK = u-prod-corner x x K
uxxK≤uxxm : u (x *ℝ x) K ≤ u (x *ℝ x) m
uxxK≤uxxm = u-mono (x *ℝ x) m≤K
lym≤lyK : l y m ≤ l y K
lym≤lyK = l-mono y m≤K
u2K²<lym : u x (2 ℕ* K) * u x (2 ℕ* K) < l y m
u2K²<lym = ≤-<-trans (≤-trans u2K²≤uxxK uxxK≤uxxm) uxxm<lym
u2K²<lyK : u x (2 ℕ* K) * u x (2 ℕ* K) < l y K
u2K²<lyK = <-≤-trans u2K²<lym lym≤lyK
0≤u2K : 0ℚ ≤ u x (2 ℕ* K)
0≤u2K = u-nonNeg x x≥0 (2 ℕ* K)
u2K²<q2 : u x (2 ℕ* K) * u x (2 ℕ* K) < q * q
u2K²<q2 = <-trans u2K²<lyK lyK<q2
gap>0 : 0ℚ < q - u x (2 ℕ* K)
gap>0 = sq-gap-pos (u x (2 ℕ* K)) q 0≤u2K 0<q u2K²<q2
probe : Σ ℕ (λ N → 2 ℕ* K ≤ℕ N × δ N < q - u x (2 ℕ* K))
probe = δ-below (q - u x (2 ℕ* K)) gap>0 (2 ℕ* K)
N : ℕ
N = proj₁ probe
2K≤N : 2 ℕ* K ≤ℕ N
2K≤N = proj₁ (proj₂ probe)
δN<gap : δ N < q - u x (2 ℕ* K)
δN<gap = proj₂ (proj₂ probe)
uxN≤u2K : u x N ≤ u x (2 ℕ* K)
uxN≤u2K = u-mono x 2K≤N
u2K<-dN+q : u x (2 ℕ* K) < - δ N + q
u2K<-dN+q = sub-lt-swap (u x (2 ℕ* K)) (δ N) q δN<gap
uxN<-dN+q : u x N < - δ N + q
uxN<-dN+q = ≤-<-trans uxN≤u2K u2K<-dN+q
in
N , subst (λ z → u x N < z) (sym (l-dyadic q N)) uxN<-dN+q
upper-case : (p q : ℚ) → p < q → 0ℚ ≤ p → Occupied P p ⊎ Upper P q
upper-case p q p<q 0≤p =
let
pp<qq : p * p < q * q
pp<qq = sq-< p q 0≤p p<q
gap>0 : 0ℚ < q * q - p * p
gap>0 = sub-pos (p * p) (q * q) pp<qq
probe : Σ ℕ (λ j → 0 ≤ℕ j × width y j < q * q - p * p)
probe = width-below-strict y (q * q - p * p) 0 gap>0
k : ℕ
k = proj₁ probe
wk<gap : width y k < q * q - p * p
wk<gap = proj₂ (proj₂ probe)
branch : (p * p < l y k) ⊎ (¬ (p * p < l y k))
→ Occupied P p ⊎ Upper P q
branch =
[ (λ lt → inj₁ (occupied-below p k 0≤p lt))
, (λ ¬lt → inj₂ (upper-above p q k 0≤p p<q wk<gap ¬lt))
]
in
branch (decide-below y k p)
located : Located P
located p q p<q with <-cmp p 0ℚ
... | tri< p<0 _ _ = inj₁ (0ℝ , P-0 , embed-below-zero p p<0)
... | tri≈ ¬p<0 _ _ = upper-case p q p<q (≮⇒≥ ¬p<0)
... | tri> ¬p<0 _ _ = upper-case p q p<q (≮⇒≥ ¬p<0)