{-# OPTIONS --safe --cubical-compatible --guardedness --exact-split --double-check #-}
module Real.Interval.OrderComplete.Bisect where
open import Data.Nat using (ℕ; zero; suc; z≤n)
open import Data.Product using (Σ; _,_; proj₁; proj₂; _×_)
open import Data.Sum using (_⊎_; inj₁; inj₂)
open import Function using (_∘_)
open import Data.Rational using
(ℚ; 0ℚ; 1ℚ; _+_; _-_; _*_; _<_; _≤_; NonNegative; positive)
open import Data.Rational.Base using (-_; nonNegative)
open import Data.Rational.Properties using
(≤-refl; ≤-reflexive; ≤-trans; ≤-<-trans; <-≤-trans; <-trans; <⇒≤; +-mono-≤
; +-monoʳ-<; +-comm; +-assoc; *-assoc; *-identityʳ; *-distribˡ-+; +-identityˡ
; +-identityʳ; pos⇒nonNeg; *-monoˡ-<-pos; neg-distrib-+; *-monoʳ-≤-nonNeg
; *-monoˡ-≤-nonNeg; +-monoˡ-≤; +-monoʳ-≤; ≮⇒≥)
renaming (+-inverseʳ to +-invʳ)
open import Relation.Binary.PropositionalEquality using
(_≡_; cong; cong₂; sym; trans; subst; module ≡-Reasoning)
open ≡-Reasoning
open import Real using (embed; half; 0<embed)
open import Real.Interval using (RealI; δ; δ-half; δ-pos; sub-cancel)
open import Real.IntervalEquiv using (l; u; u-mono; width; recipPow2)
open import Real.Interval.OrderLaws using (width-below-strict)
open import Real.Interval.Node using (u-dyadic; l-dyadic)
open import Real.Interval.Kit using (0<half; 0≤half; half+half≡1)
open import Real.Interval.Order renaming (<-trans to <-transR)
open import Real.Interval.Rational using (pos-diff)
open import Real.Interval.OrderComplete.Base using
(_≤ℝ_; a+d≡b; x<x+; emb<; δ-dec; Subset; Upper; Occupied; Located; Bracket
; mkB; quarter; 0<quarter; qq≡h; 3/4; cube≤half; recipPow2-step)
open import Real.Interval.Reasoning using (begin≤_; _≈⟨_⟩_; _≤⟨_⟩_; _≤∎)
private
instance
half-nn : NonNegative half
half-nn = nonNegative 0≤half
d-half-pair : ∀ (d : ℚ) → d * half + d * half ≡ d
d-half-pair d =
begin
d * half + d * half
≡⟨ sym (*-distribˡ-+ d half half) ⟩
d * (half + half)
≡⟨ cong (d *_) half+half≡1 ⟩
d * 1ℚ
≡⟨ *-identityʳ d ⟩
d
∎
d-quarter-pair : ∀ (d : ℚ) → d * quarter + d * quarter ≡ d * half
d-quarter-pair d =
begin
d * quarter + d * quarter
≡⟨ sym (*-distribˡ-+ d quarter quarter) ⟩
d * (quarter + quarter)
≡⟨ cong (d *_) qq≡h ⟩
d * half
∎
d-3/4 : ∀ (d : ℚ) → d * 3/4 ≡ d * half + d * quarter
d-3/4 d = *-distribˡ-+ d half quarter
d-minus-half : ∀ (d : ℚ) → d - d * half ≡ d * half
d-minus-half d =
begin
d - d * half
≡⟨ cong (_- d * half) (sym (d-half-pair d)) ⟩
(d * half + d * half) - d * half
≡⟨ +-assoc (d * half) (d * half) (- (d * half)) ⟩
d * half + (d * half - d * half)
≡⟨ cong (d * half +_) (+-invʳ (d * half)) ⟩
d * half + 0ℚ
≡⟨ +-identityʳ (d * half) ⟩
d * half
∎
d-half-pos : ∀ (d : ℚ) → 0ℚ < d → 0ℚ < d * half
d-half-pos d 0<d = *-monoˡ-<-pos half {{positive 0<half}} 0<d
d-quarter-pos : ∀ (d : ℚ) → 0ℚ < d → 0ℚ < d * quarter
d-quarter-pos d 0<d = *-monoˡ-<-pos quarter {{positive 0<quarter}} 0<d
bracket-b-eq : ∀ (a b : ℚ) →
b ≡ ((a + (b - a) * half) + (b - a) * quarter) + (b - a) * quarter
bracket-b-eq a b =
begin
b
≡⟨ sym (a+d≡b a b) ⟩
a + (b - a)
≡⟨ cong (a +_) (sym (d-half-pair (b - a))) ⟩
a + ((b - a) * half + (b - a) * half)
≡⟨ sym (+-assoc a ((b - a) * half) ((b - a) * half)) ⟩
(a + (b - a) * half) + (b - a) * half
≡⟨ cong ((a + (b - a) * half) +_) (sym (d-quarter-pair (b - a))) ⟩
(a + (b - a) * half) + ((b - a) * quarter + (b - a) * quarter)
≡⟨ sym (+-assoc (a + (b - a) * half)
((b - a) * quarter) ((b - a) * quarter)) ⟩
((a + (b - a) * half) + (b - a) * quarter) + (b - a) * quarter
∎
bracket-bm-eq : ∀ (a b : ℚ) →
b - (a + (b - a) * half) ≡ (b - a) * half
bracket-bm-eq a b =
begin
b - (a + (b - a) * half)
≡⟨ cong (λ z → z - (a + (b - a) * half)) (sym (a+d≡b a b)) ⟩
(a + (b - a)) - (a + (b - a) * half)
≡⟨ cong₂ _-_ (+-comm a (b - a)) (+-comm a ((b - a) * half)) ⟩
((b - a) + a) - ((b - a) * half + a)
≡⟨ sub-cancel (b - a) ((b - a) * half) a ⟩
(b - a) - (b - a) * half
≡⟨ d-minus-half (b - a) ⟩
(b - a) * half
∎
bracket-ra-eq : ∀ (a b : ℚ) →
((a + (b - a) * half) + (b - a) * quarter) - a ≡
(b - a) * half + (b - a) * quarter
bracket-ra-eq a b =
begin
((a + (b - a) * half) + (b - a) * quarter) - a
≡⟨ cong (_- a) (+-assoc a ((b - a) * half) ((b - a) * quarter)) ⟩
(a + ((b - a) * half + (b - a) * quarter)) - a
≡⟨ +-assoc a (((b - a) * half) + ((b - a) * quarter)) (- a) ⟩
a + (((b - a) * half + (b - a) * quarter) - a)
≡⟨ a+d≡b a ((b - a) * half + (b - a) * quarter) ⟩
(b - a) * half + (b - a) * quarter
∎
bracket-case1 : ∀ (a b : ℚ) → a < b →
b - (a + (b - a) * half) ≤ (b - a) * 3/4
bracket-case1 a b a<b =
subst (λ z → z ≤ (b - a) * 3/4) (sym (bracket-bm-eq a b))
(subst (λ z → (b - a) * half ≤ z) (sym (d-3/4 (b - a)))
(<⇒≤ (x<x+ ((b - a) * half)
(d-quarter-pos (b - a) (pos-diff a b a<b)))))
bracket-case2 : ∀ (a b : ℚ) → a < b →
((a + (b - a) * half) + (b - a) * quarter) - a ≤ (b - a) * 3/4
bracket-case2 a b a<b =
subst (λ z → z ≤ (b - a) * 3/4) (sym (bracket-ra-eq a b))
(≤-reflexive (sym (d-3/4 (b - a))))
d-cube-assoc : ∀ (d : ℚ) →
(((d * 3/4) * 3/4) * 3/4) ≡ d * ((3/4 * 3/4) * 3/4)
d-cube-assoc d =
begin
(((d * 3/4) * 3/4) * 3/4)
≡⟨ *-assoc (d * 3/4) 3/4 3/4 ⟩
(d * 3/4) * (3/4 * 3/4)
≡⟨ *-assoc d 3/4 (3/4 * 3/4) ⟩
d * (3/4 * (3/4 * 3/4))
≡⟨ cong (λ x → d * x) (sym (*-assoc 3/4 3/4 3/4)) ⟩
d * ((3/4 * 3/4) * 3/4)
∎
d-cube≤half : ∀ (d : ℚ) → 0ℚ ≤ d →
d * ((3/4 * 3/4) * 3/4) ≤ d * half
d-cube≤half d 0≤d =
*-monoˡ-≤-nonNeg d {{nonNegative 0≤d}} cube≤half
module _ {P : Subset} where
bw : Bracket P → ℚ
bw (mkB a b _ _ _) = b - a
bw-pos : ∀ (br : Bracket P) → 0ℚ < bw br
bw-pos br = pos-diff (Bracket.a br) (Bracket.b br) (Bracket.a<b br)
bw-nn : ∀ (br : Bracket P) → 0ℚ ≤ bw br
bw-nn br = <⇒≤ (bw-pos br)
step₁-case :
(a b : ℚ) (a<b : a < b)
(m r : ℚ) (a<m : a < m) (m<r : m < r) (r<b : r < b)
(occ : Occupied P a) (upper : Upper P b)
(b-m-bound : b - m ≤ (b - a) * 3/4)
(r-a-bound : r - a ≤ (b - a) * 3/4)
(s : Occupied P m ⊎ Upper P r) →
Σ (Bracket P) λ br' →
(bw br' ≤ (b - a) * 3/4)
× (a ≤ Bracket.a br')
× (Bracket.b br' ≤ b)
step₁-case a b a<b m r a<m m<r r<b occ upper b-m-bound r-a-bound
(inj₁ (x , px , m<x)) =
(mkB m b (<-trans m<r r<b) (x , px , m<x) upper)
, b-m-bound
, <⇒≤ a<m
, ≤-refl
step₁-case a b a<b m r a<m m<r r<b occ upper b-m-bound r-a-bound
(inj₂ all<r) =
(mkB a r (<-trans a<m m<r) occ all<r)
, r-a-bound
, ≤-refl
, <⇒≤ r<b
module _ {P : Subset} (loc : Located P) where
step₁-core : (br : Bracket P) →
Σ (Bracket P) λ br' →
(bw br' ≤ bw br * 3/4)
× (Bracket.a br ≤ Bracket.a br')
× (Bracket.b br' ≤ Bracket.b br)
step₁-core (mkB a b a<b occ upper) =
let
d = b - a
d>0 = pos-diff a b a<b
hd = d * half
qd = d * quarter
hd>0 = d-half-pos d d>0
qd>0 = d-quarter-pos d d>0
m = a + hd
r = m + qd
a<m = x<x+ a hd>0
m<r = x<x+ m qd>0
r<b = subst (λ z → r < z) (sym (bracket-b-eq a b)) (x<x+ r qd>0)
in
step₁-case a b a<b m r a<m m<r r<b occ upper
(bracket-case1 a b a<b)
(bracket-case2 a b a<b)
(loc m r m<r)
step₁ : Bracket P → Bracket P
step₁ br = proj₁ (step₁-core br)
step₁-shrink : (br : Bracket P) → bw (step₁ br) ≤ bw br * 3/4
step₁-shrink = proj₁ ∘ proj₂ ∘ step₁-core
step₁-a≤a : (br : Bracket P) → Bracket.a br ≤ Bracket.a (step₁ br)
step₁-a≤a = proj₁ ∘ proj₂ ∘ proj₂ ∘ step₁-core
step₁-b≤b : (br : Bracket P) → Bracket.b (step₁ br) ≤ Bracket.b br
step₁-b≤b = proj₂ ∘ proj₂ ∘ proj₂ ∘ step₁-core
step₂ : Bracket P → Bracket P
step₂ br = step₁ (step₁ br)
0<3/4 : 0ℚ < 3/4
0<3/4 = <-trans 0<half (x<x+ half 0<quarter)
private
instance nn3/4 : NonNegative 3/4
nn3/4 = pos⇒nonNeg 3/4 {{positive 0<3/4}}
mul3/4 : ∀ {x y} → x ≤ y → x * 3/4 ≤ y * 3/4
mul3/4 = *-monoʳ-≤-nonNeg 3/4
abstract
step₃ : Bracket P → Bracket P
step₃ br = step₁ (step₁ (step₁ br))
step₃-a≤a : (br : Bracket P) → Bracket.a br ≤ Bracket.a (step₃ br)
step₃-a≤a br =
begin≤
Bracket.a br
≤⟨ step₁-a≤a br ⟩
Bracket.a (step₁ br)
≤⟨ step₁-a≤a (step₁ br) ⟩
Bracket.a (step₁ (step₁ br))
≤⟨ step₁-a≤a (step₁ (step₁ br)) ⟩
Bracket.a (step₁ (step₁ (step₁ br)))
≤∎
step₃-b≤b : (br : Bracket P) → Bracket.b (step₃ br) ≤ Bracket.b br
step₃-b≤b br =
begin≤
Bracket.b (step₁ (step₁ (step₁ br)))
≤⟨ step₁-b≤b (step₁ (step₁ br)) ⟩
Bracket.b (step₁ (step₁ br))
≤⟨ step₁-b≤b (step₁ br) ⟩
Bracket.b (step₁ br)
≤⟨ step₁-b≤b br ⟩
Bracket.b br
≤∎
step₃-shrink : (br : Bracket P) → bw (step₃ br) ≤ bw br * half
step₃-shrink br =
begin≤
bw (step₁ (step₁ (step₁ br)))
≤⟨ step₁-shrink (step₁ (step₁ br)) ⟩
bw (step₁ (step₁ br)) * 3/4
≤⟨ mul3/4 (step₁-shrink (step₁ br)) ⟩
(bw (step₁ br) * 3/4) * 3/4
≤⟨ mul3/4 (mul3/4 (step₁-shrink br)) ⟩
((bw br * 3/4) * 3/4) * 3/4
≈⟨ d-cube-assoc (bw br) ⟩
bw br * ((3/4 * 3/4) * 3/4)
≤⟨ d-cube≤half (bw br) (bw-nn br) ⟩
bw br * half
≤∎
record CStep (br0 : Bracket P) (j : ℕ) : Set where
field
cbr : Bracket P
cw≤ : bw cbr ≤ bw br0 * recipPow2 j
cstep : ∀ {br0 j} (s : CStep br0 j) → CStep br0 (suc j)
cstep {br0} {j} (record { cbr = br ; cw≤ = w≤ }) =
record
{ cbr = step₃ br
; cw≤ = begin≤
bw (step₃ br)
≤⟨ step₃-shrink br ⟩
bw br * half
≤⟨ *-monoʳ-≤-nonNeg half w≤ ⟩
(bw br0 * recipPow2 j) * half
≈⟨ *-assoc (bw br0) (recipPow2 j) half ⟩
bw br0 * (recipPow2 j * half)
≈⟨ cong ((bw br0) *_) (recipPow2-step j) ⟩
bw br0 * recipPow2 (suc j)
≤∎
}
csteps : (br0 : Bracket P) (j : ℕ) → CStep br0 j
csteps br0 zero = record { cbr = br0
; cw≤ = ≤-reflexive (sym (*-identityʳ (bw br0))) }
csteps br0 (suc j) = cstep (csteps br0 j)
cbr-seq : (br0 : Bracket P) (j : ℕ) → Bracket P
cbr-seq br0 j = CStep.cbr (csteps br0 j)
cwb : ∀ br0 j → bw (cbr-seq br0 j) ≤ bw br0 * recipPow2 j
cwb br0 j = CStep.cw≤ (csteps br0 j)
module _ {P : Subset} where
initBracket : (x₀ : RealI) → P x₀
→ (u₀ : RealI) → ((x : RealI) → P x → x ≤ℝ u₀)
→ Bracket P
initBracket x₀ px₀ u₀ isUpper =
let
0<1ℚ = 0<embed 0
lx = l x₀ 0
uu = u u₀ 0
not-u0<x0 = isUpper x₀ px₀
lx≤uu = ≮⇒≥ (λ uu<lx → not-u0<x0 (0 , uu<lx))
a = lx - 1ℚ
b = uu + 1ℚ
a+1≡lx = begin
a + 1ℚ
≡⟨ +-comm a 1ℚ ⟩
1ℚ + a
≡⟨ a+d≡b 1ℚ lx ⟩
lx
∎
a<lx = subst (a <_) a+1≡lx (x<x+ a 0<1ℚ)
uu<b = x<x+ uu 0<1ℚ
a<b = <-trans a<lx (≤-<-trans lx≤uu uu<b)
uEa≡ = trans (u-dyadic a 0) (+-comm (δ 0) a)
a+half+half≡lx = begin
a + half + half
≡⟨ +-assoc a half half ⟩
a + (half + half)
≡⟨ cong (a +_) half+half≡1 ⟩
a + 1ℚ
≡⟨ a+1≡lx ⟩
lx
∎
a+half<lx = subst (λ z → a + half < z) a+half+half≡lx
(x<x+ (a + half) 0<half)
occ = x₀ , px₀ , (0 , subst (λ z → z < lx) (sym uEa≡) a+half<lx)
upper = λ x px →
let
sel = width-below-strict x half 1 (0<half)
n = proj₁ sel
n≥1 = proj₁ (proj₂ sel)
w<half = proj₂ (proj₂ sel)
δ1≤half = subst (δ 1 ≤_) (δ-half 0)
(<⇒≤ (x<x+ (δ 1) (δ-pos 1)))
δn≤half = ≤-trans (δ-dec 1 n n≥1) δ1≤half
lxn = l x n
¬uun<lxn = λ uun<lxn → isUpper x px (n , uun<lxn)
lxn≤uun = ≮⇒≥ ¬uun<lxn
uun≤uu = u-mono u₀ {0} {n} z≤n
ux≡ = sym (a+d≡b lxn (u x n))
half+δn≤1 = subst (λ z → half + δ n ≤ z) half+half≡1
(+-monoʳ-≤ half δn≤half)
simpl = begin
(half + δ n) + (- δ n)
≡⟨ +-assoc half (δ n) (- δ n) ⟩
half + (δ n + (- δ n))
≡⟨ cong (half +_) (+-invʳ (δ n)) ⟩
half + 0ℚ
≡⟨ +-identityʳ half ⟩
half
∎
half≤1-δn = subst (λ z → z ≤ 1ℚ - δ n) simpl
(+-mono-≤ half+δn≤1 (≤-refl {(- δ n)}))
ux≤ = subst (λ z → z ≤ uu + width x n) (sym ux≡)
(≤-trans (+-monoˡ-≤ (width x n) lxn≤uun)
(+-monoˡ-≤ (width x n) uun≤uu))
w-strict = +-monoʳ-< uu (<-≤-trans w<half half≤1-δn)
lEb≡ = trans (l-dyadic b n) (+-comm (- δ n) b)
b-δ≡ = +-assoc uu 1ℚ (- δ n)
final = subst (λ z → u x n < z) (sym lEb≡)
(≤-<-trans ux≤
(subst (λ z → uu + width x n < z) (sym b-δ≡) w-strict))
in
n , final
in
mkB a b a<b occ upper
widenBracket : Bracket P → Bracket P
widenBracket br =
let open Bracket br
two = embed 2
a' = a - two
b' = b + two
0<two = 0<embed 1
negA' = begin
(- a')
≡⟨⟩
- (a - two)
≡⟨ neg-distrib-+ a (- two) ⟩
(- a) + two
∎
diff≡ = begin
a + (- a')
≡⟨ cong (a +_) negA' ⟩
a + ((- a) + two)
≡⟨ sym (+-assoc a (- a) two) ⟩
(a + (- a)) + two
≡⟨ cong (_+ two) (+-invʳ a) ⟩
0ℚ + two
≡⟨ +-identityˡ two ⟩
two
∎
a'<a = subst (λ z → a' < z) (a+d≡b a' a)
(subst (λ z → a' < a' + z) (sym diff≡) (x<x+ a' 0<two))
b<b' = x<x+ b 0<two
a'<b' = <-trans a'<a (≤-<-trans (<⇒≤ a<b) b<b')
x = proj₁ occ
px = proj₁ (proj₂ occ)
a<x = proj₂ (proj₂ occ)
a'<x = <-transR (emb< a'<a) a<x
occ' = x , px , a'<x
x<b = upper
b<b'R = emb< b<b'
upper' = λ y py → <-transR (x<b y py) b<b'R
in mkB a' b' a'<b' occ' upper'