| 1 |
(* |
| 2 |
Copyright © 2006-2008 Russell O’Connor |
| 3 |
Copyright © 2020 Vincent Semeria |
| 4 |
|
| 5 |
Permission is hereby granted, free of charge, to any person obtaining a copy of |
| 6 |
this proof and associated documentation files (the "Proof"), to deal in |
| 7 |
the Proof without restriction, including without limitation the rights to |
| 8 |
use, copy, modify, merge, publish, distribute, sublicense, and/or sell copies of |
| 9 |
the Proof, and to permit persons to whom the Proof is furnished to do so, |
| 10 |
subject to the following conditions: |
| 11 |
|
| 12 |
The above copyright notice and this permission notice shall be included in all |
| 13 |
copies or substantial portions of the Proof. |
| 14 |
|
| 15 |
THE PROOF IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR |
| 16 |
IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, FITNESS |
| 17 |
FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR |
| 18 |
COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER |
| 19 |
IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN |
| 20 |
CONNECTION WITH THE PROOF OR THE USE OR OTHER DEALINGS IN THE PROOF. |
| 21 |
*) |
| 22 |
|
| 23 |
From Coq Require Import ZArith. |
| 24 |
Require Import CoRN.algebra.RSetoid. |
| 25 |
Require Import CoRN.model.totalorder.QposMinMax. |
| 26 |
Require Import CoRN.model.metric2.Qmetric. |
| 27 |
Require Import CoRN.metric2.Limit. |
| 28 |
From Coq Require Import Qabs. |
| 29 |
From Coq Require Import Arith. |
| 30 |
From Coq Require Import Qpower. |
| 31 |
Require Import CoRN.reals.fast.LazyNat. |
| 32 |
From Coq Require Import Ring. |
| 33 |
Require Import MathClasses.interfaces.abstract_algebra MathClasses.theory.streams. |
| 34 |
Require Export MathClasses.theory.series. |
| 35 |
Require Import MathClasses.interfaces.abstract_algebra MathClasses.theory.streams. |
| 36 |
|
| 37 |
Opaque Qabs. |
| 38 |
Local Open Scope Q_scope. |
| 39 |
|
| 40 |
(** |
| 41 |
** Specific results for streams on [Q] |
| 42 |
*) |
| 43 |
|
| 44 |
(** [everyOther] preserves limits. *) |
| 45 |
Lemma everyOther_nbz : forall (s : Stream Q) (e : QposInf), |
| 46 |
(NearBy 0 e s) -> NearBy 0 e (everyOther s). |
| 47 |
Proof. |
| 48 |
cofix everyOther_nbz. |
| 49 |
intros [s [b r]] x [H [_ Hs]]. |
| 50 |
constructor;[|apply everyOther_nbz];assumption. |
| 51 |
Qed. |
| 52 |
|
| 53 |
#[global] |
| 54 |
Instance everyOther_zl `{Hx : !Limit s 0} : Limit (everyOther s) 0. |
| 55 |
Proof. |
| 56 |
intros e. |
| 57 |
assert (H:=Hx e). clear Hx. |
| 58 |
revert s H. |
| 59 |
fix everyOther_zl 2. |
| 60 |
intros x [H|H]. |
| 61 |
left. |
| 62 |
apply everyOther_nbz. |
| 63 |
assumption. |
| 64 |
case (H tt);[intros X |intros X]. |
| 65 |
right; left. |
| 66 |
clear - x X. |
| 67 |
abstract ( destruct x as [a [b x]]; destruct X; apply everyOther_nbz; assumption). |
| 68 |
right; intros _. |
| 69 |
apply everyOther_zl. |
| 70 |
apply X. |
| 71 |
constructor. |
| 72 |
Defined. |
| 73 |
|
| 74 |
(** [mult_Streams] preserves convergeing to 0. *) |
| 75 |
Lemma mult_Streams_nbz : forall {s1 s2 : Stream Q} {x : QposInf}, |
| 76 |
(NearBy 0 x s1) |
| 77 |
-> forall {y : QposInf}, NearBy 0 y s2 |
| 78 |
-> NearBy 0 (x*y) (mult_Streams s1 s2). |
| 79 |
Proof. |
| 80 |
unfold NearBy. |
| 81 |
cofix mult_Streams_nbz. |
| 82 |
intros s1 s2 x [Ha0 Hs1] y [Hb0 Hs2]. |
| 83 |
constructor. |
| 84 |
2: apply (mult_Streams_nbz (CoqStreams.tl s1) (CoqStreams.tl s2)); assumption. |
| 85 |
destruct x as [x|];[|constructor]. |
| 86 |
destruct y as [y|];[|constructor]. |
| 87 |
simpl. |
| 88 |
unfold Qball. |
| 89 |
unfold QAbsSmall. |
| 90 |
setoid_replace ((CoqStreams.hd s1 * CoqStreams.hd s2)%mc - 0)%Q |
| 91 |
with ((CoqStreams.hd s1 - 0) * (CoqStreams.hd s2 - 0)). |
| 92 |
apply Qmult_AbsSmall; assumption. |
| 93 |
ring_simplify. reflexivity. |
| 94 |
Qed. |
| 95 |
|
| 96 |
(* The multiplication of a bounded stream b by a stream a |
| 97 |
converging to 0 converges to 0. *) |
| 98 |
Lemma mult_Streams_zl : forall (a b : Stream Q), |
| 99 |
(Limit a 0) -> forall (x:Qpos), NearBy 0 x b -> |
| 100 |
Limit (mult_Streams a b) 0. |
| 101 |
Proof. |
| 102 |
intros a b Ha x Hb e. |
| 103 |
assert (H:=Ha (e * (Qpos_inv x))%QposInf). |
| 104 |
generalize b Hb. |
| 105 |
clear b Hb. |
| 106 |
induction H; intros b Hb. |
| 107 |
left. |
| 108 |
abstract ( destruct e as [e|];[|apply ForAll_True]; |
| 109 |
assert (Heq:proj1_sig e== proj1_sig ((e*Qpos_inv x)*x)%Qpos);[ |
| 110 |
simpl; field; apply Qpos_nonzero |
| 111 |
|rewrite -> (NearBy_comp _ _ (ball_refl _ 0 (Qle_refl 0)) _ _ Heq ); |
| 112 |
apply (mult_Streams_nbz H Hb)] ). |
| 113 |
right. |
| 114 |
simpl. |
| 115 |
rename H0 into IHExists. |
| 116 |
intros. |
| 117 |
apply (IHExists tt). |
| 118 |
apply Limit_tl; assumption. |
| 119 |
destruct Hb; assumption. |
| 120 |
Defined. |
| 121 |
|
| 122 |
(** |
| 123 |
*** [StreamBounds] |
| 124 |
[StreamBounds] says that one stream pointwise bounds the absolute value |
| 125 |
of the other. *) |
| 126 |
Definition StreamBounds (a b : Stream Q) |
| 127 |
:= ForAll (fun (x:Stream (Q*Q)) => let (a,b):=(CoqStreams.hd x) in QAbsSmall a b) |
| 128 |
(zipWith pair a b). |
| 129 |
|
| 130 |
(** If the bounding stream goes to 0, so does the bounded stream. *) |
| 131 |
Lemma Stream_Bound_nbz : forall a b e, (StreamBounds a b) -> NearBy 0 e a -> NearBy 0 e b. |
| 132 |
Proof. |
| 133 |
cofix Stream_Bound_nbz. |
| 134 |
intros a b e Hb Ha. |
| 135 |
constructor. |
| 136 |
destruct Hb as [[Hb1 Hb2] _]. |
| 137 |
destruct e as [e|];[|constructor]. |
| 138 |
destruct Ha as [[Ha1 Ha2] _]. |
| 139 |
simpl in *. |
| 140 |
split. |
| 141 |
apply Qle_trans with (-(CoqStreams.hd a -0)). |
| 142 |
apply Qopp_le_compat. |
| 143 |
assumption. |
| 144 |
ring_simplify. |
| 145 |
assumption. |
| 146 |
apply Qle_trans with (CoqStreams.hd a - 0). |
| 147 |
ring_simplify. |
| 148 |
assumption. |
| 149 |
assumption. |
| 150 |
eapply Stream_Bound_nbz. |
| 151 |
destruct Hb as [_ Hb]. |
| 152 |
change (StreamBounds (CoqStreams.tl a) (CoqStreams.tl b)) in Hb. |
| 153 |
apply Hb. |
| 154 |
destruct Ha as [_ Ha]. |
| 155 |
assumption. |
| 156 |
Qed. |
| 157 |
|
| 158 |
Lemma Stream_Bound_zl : forall a b, (StreamBounds a b) -> Limit a 0 -> Limit b 0. |
| 159 |
Proof. |
| 160 |
intros a b H Ha e. |
| 161 |
assert (Ha':=(Ha e)); clear Ha. |
| 162 |
generalize b H; clear b H. |
| 163 |
induction Ha'; intros b Hb. |
| 164 |
left. |
| 165 |
apply Stream_Bound_nbz with x; assumption. |
| 166 |
right. |
| 167 |
rename H0 into IHHa'. |
| 168 |
intros _. |
| 169 |
apply (IHHa' tt). |
| 170 |
destruct Hb; assumption. |
| 171 |
Defined. |
| 172 |
|
| 173 |
Section Qpowers. |
| 174 |
Variable a : Q. |
| 175 |
|
| 176 |
Hypothesis Ha : 0 <= a <= 1. |
| 177 |
|
| 178 |
(** It is decreasing and nonnegative when a is between 0 and 1. *) |
| 179 |
Lemma powers_help_dnn : forall x, (0 <= x) -> DecreasingNonNegative (powers_help a x). |
| 180 |
Proof. |
| 181 |
intros x Hx. |
| 182 |
destruct Ha as [Ha0 Ha1]. |
| 183 |
generalize x Hx; clear x Hx. |
| 184 |
cofix powers_help_dnn. |
| 185 |
intros b Hb. |
| 186 |
constructor. |
| 187 |
simpl. |
| 188 |
split. |
| 189 |
rewrite <- (Qmult_0_l a). apply Qmult_le_compat_r; assumption. |
| 190 |
rewrite Qmult_comm. |
| 191 |
rewrite <- (Qmult_1_l b) at 2. |
| 192 |
apply Qmult_le_compat_r. exact Ha1. exact Hb. |
| 193 |
apply powers_help_dnn. |
| 194 |
rewrite <- (Qmult_0_l a). apply Qmult_le_compat_r; assumption. |
| 195 |
Qed. |
| 196 |
|
| 197 |
Lemma powers_dnn : DecreasingNonNegative (powers a). |
| 198 |
Proof. |
| 199 |
apply powers_help_dnn. |
| 200 |
discriminate. |
| 201 |
Qed. |
| 202 |
|
| 203 |
Lemma powers_help_nbz : forall x, |
| 204 |
0 <= x <= 1 -> NearBy 0 (Qpos2QposInf (1#1)) (powers_help a x). |
| 205 |
Proof. |
| 206 |
cofix powers_help_nbz. |
| 207 |
intros b [Hb0 Hb1]. |
| 208 |
destruct Ha as [Ha0 Ha1]. |
| 209 |
constructor. |
| 210 |
simpl. |
| 211 |
unfold Qball. |
| 212 |
unfold QAbsSmall. setoid_replace (b-0)%Q with b. |
| 213 |
2: unfold Qminus; apply Qplus_0_r. |
| 214 |
split;simpl. |
| 215 |
apply Qle_trans with 0;[discriminate|assumption]. |
| 216 |
assumption. |
| 217 |
simpl. |
| 218 |
apply powers_help_nbz. |
| 219 |
split. |
| 220 |
rewrite <- (Qmult_0_l a). apply Qmult_le_compat_r; assumption. |
| 221 |
apply (Qle_trans _ (1*a)). |
| 222 |
apply Qmult_le_compat_r; assumption. |
| 223 |
rewrite Qmult_1_l. exact Ha1. |
| 224 |
Qed. |
| 225 |
|
| 226 |
Lemma powers_nbz : NearBy 0 (Qpos2QposInf (1#1)) (powers a). |
| 227 |
Proof. |
| 228 |
apply powers_help_nbz. |
| 229 |
split; discriminate. |
| 230 |
Qed. |
| 231 |
End Qpowers. |
| 232 |
|
| 233 |
|
| 234 |
(** |
| 235 |
*** [ppositives] |
| 236 |
The stream of postive numbers (as positive). |
| 237 |
|
| 238 |
We do not use [positives] because [positive] does not form a semiring. |
| 239 |
*) |
| 240 |
CoFixpoint ppositives_help (n:positive) : Stream positive := |
| 241 |
Cons n (ppositives_help (Pos.succ n)). |
| 242 |
|
| 243 |
Definition ppositives := ppositives_help 1. |
| 244 |
|
| 245 |
Lemma Str_nth_ppositives : forall n, Str_nth n ppositives ≡ P_of_succ_nat n. |
| 246 |
Proof. |
| 247 |
intros n. |
| 248 |
unfold ppositives. |
| 249 |
apply nat_of_P_inj. |
| 250 |
rewrite nat_of_P_o_P_of_succ_nat_eq_succ. |
| 251 |
change (S n) with ((nat_of_P 1) + n)%nat. |
| 252 |
generalize 1%positive. |
| 253 |
induction n. |
| 254 |
intros c. |
| 255 |
rewrite Nat.add_comm. |
| 256 |
reflexivity. |
| 257 |
intros c. |
| 258 |
unfold Str_nth in *. |
| 259 |
simpl. |
| 260 |
rewrite IHn. |
| 261 |
rewrite nat_of_P_succ_morphism. |
| 262 |
apply plus_n_Sm. |
| 263 |
Qed. |
| 264 |
|
| 265 |
Lemma Str_nth_ppositives' n |
| 266 |
: inject_Z (Zpos (Str_nth n ppositives)) = Str_nth n positives. |
| 267 |
Proof. |
| 268 |
rewrite Str_nth_ppositives, Str_nth_positives. |
| 269 |
rewrite Z.P_of_succ_nat_Zplus. |
| 270 |
rewrite <-(naturals.to_semiring_unique (Basics.compose inject_Z Z_of_nat)). |
| 271 |
unfold Basics.compose. |
| 272 |
rewrite <-(rings.preserves_1 (f:=inject_Z)). |
| 273 |
rewrite <-rings.preserves_plus. |
| 274 |
now rewrite commutativity. |
| 275 |
Qed. |
| 276 |
|
| 277 |
(** |
| 278 |
*** [Qrecip_positives] |
| 279 |
The stream of 1/n. |
| 280 |
*) |
| 281 |
Definition Qrecip_positives := CoqStreams.map (fun x => 1#x) ppositives. |
| 282 |
|
| 283 |
Lemma Str_nth_Qrecip_positives : forall n, Str_nth n Qrecip_positives = 1#(P_of_succ_nat n). |
| 284 |
Proof. |
| 285 |
intros n. |
| 286 |
unfold Qrecip_positives. |
| 287 |
rewrite Str_nth_map. |
| 288 |
rewrite Str_nth_ppositives. |
| 289 |
reflexivity. |
| 290 |
Qed. |
| 291 |
|
| 292 |
Lemma Str_nth_Qrecip_positives' n : Str_nth n Qrecip_positives = / Str_nth n positives. |
| 293 |
Proof. |
| 294 |
unfold Qrecip_positives. |
| 295 |
rewrite Str_nth_map. |
| 296 |
rewrite Qmake_Qdiv. |
| 297 |
rewrite Str_nth_ppositives'. |
| 298 |
apply (left_identity (/ Str_nth n positives)). |
| 299 |
Qed. |
| 300 |
|
| 301 |
(** The limit of [recip_positives] is 0. *) |
| 302 |
Lemma Qrecip_positives_help_nbz : forall (x: Qpos) (q:positive), |
| 303 |
(Zpos (Qden (proj1_sig x)) <= Zpos q)%Z |
| 304 |
-> NearBy 0 (Qpos2QposInf x) (CoqStreams.map (fun x => 1#x) (ppositives_help q)). |
| 305 |
Proof. |
| 306 |
assert (∀ (q n d : positive), |
| 307 |
(Zpos d <= Zpos q)%Z |
| 308 |
→ NearBy 0 (Qpos2QposInf (n # d)) (CoqStreams.map (λ x : positive, 1 # x) (ppositives_help q))). |
| 309 |
{ cofix Qrecip_positives_help_nbz. |
| 310 |
intros q n d Hpq. |
| 311 |
constructor. |
| 312 |
- simpl. |
| 313 |
unfold Qball, QAbsSmall, Qminus. |
| 314 |
rewrite Qplus_0_r. |
| 315 |
split. discriminate. |
| 316 |
change (1*Zpos d <= Zpos n*Zpos q)%Z. |
| 317 |
apply Zmult_le_compat. |
| 318 |
apply Pos.le_1_l. exact Hpq. |
| 319 |
discriminate. discriminate. |
| 320 |
- apply Qrecip_positives_help_nbz. |
| 321 |
clear Qrecip_positives_help_nbz. |
| 322 |
rewrite Zpos_succ_morphism. |
| 323 |
apply (Z.le_trans _ _ _ Hpq). |
| 324 |
apply Z.le_succ_diag_r. } |
| 325 |
intros. destruct x as [[n d] xpos]. |
| 326 |
destruct n as [|n|n]. inversion xpos. 2: inversion xpos. |
| 327 |
apply H. exact H0. |
| 328 |
Qed. |
| 329 |
|
| 330 |
(* Make a lazy list of LazyFurthers. *) |
| 331 |
Fixpoint Qrecip_positives_help_Exists P (n:LazyNat) (p:positive) |
| 332 |
(H : LazyExists P (CoqStreams.map (fun x => (1#x)) (ppositives_help (Pplus_LazyNat p n)))) { struct n } |
| 333 |
: LazyExists P (CoqStreams.map (fun x => (1#x)) (ppositives_help p)). |
| 334 |
Proof. |
| 335 |
destruct n. |
| 336 |
- exact H. |
| 337 |
- apply LazyFurther. |
| 338 |
exact (fun _ => Qrecip_positives_help_Exists P (l tt) (Pos.succ p) H). |
| 339 |
Defined. |
| 340 |
|
| 341 |
Lemma Qrecip_positives_nbz : forall (n : Z) (d : positive) (U : 0 < n # d), |
| 342 |
NearBy 0 (Qpos2QposInf (exist _ (n # d) U)) |
| 343 |
(map (λ x : positive, 1 # x) |
| 344 |
(ppositives_help (Pplus_LazyNat 1 (LazyPred (LazyNat_of_P d))))). |
| 345 |
Proof. |
| 346 |
intros. |
| 347 |
apply Qrecip_positives_help_nbz. |
| 348 |
induction d using Pind;[simpl;auto with *|]. |
| 349 |
autorewrite with UnLazyNat in *. |
| 350 |
rewrite nat_of_P_succ_morphism; assert (H:=lt_O_nat_of_P d); |
| 351 |
destruct (nat_of_P d);[exfalso;auto with *|]; simpl in *; |
| 352 |
replace (Pplus_LazyNat 2 (LazifyNat n0)) with (Pos.succ (Pplus_LazyNat 1 (LazifyNat n0)));[ |
| 353 |
repeat rewrite Zpos_succ_morphism; auto with * |]; clear -n0; |
| 354 |
change 2%positive with (Pos.succ 1); generalize 1%positive; |
| 355 |
induction n0;intros p;[reflexivity|]; simpl in *; rewrite IHn0; reflexivity. |
| 356 |
Qed. |
| 357 |
|
| 358 |
#[global] |
| 359 |
Instance Qrecip_positives_zl : Limit Qrecip_positives 0. |
| 360 |
intros [[[n d] U] | ]; [| left; apply ForAll_True]. |
| 361 |
unfold Qrecip_positives. |
| 362 |
unfold ppositives. |
| 363 |
apply Qrecip_positives_help_Exists with (LazyPred (LazyNat_of_P d)). |
| 364 |
left. apply Qrecip_positives_nbz. |
| 365 |
Defined. |
| 366 |
|
| 367 |
(** [recip_positives] is [DecreasingNonNegative]. *) |
| 368 |
#[global] |
| 369 |
Instance Qrecip_positives_dnn : DecreasingNonNegative Qrecip_positives. |
| 370 |
Proof. |
| 371 |
unfold Qrecip_positives. |
| 372 |
unfold ppositives. |
| 373 |
generalize (1%positive) at 2. |
| 374 |
cofix Qrecip_positives_dnn. |
| 375 |
intros p. |
| 376 |
constructor. |
| 377 |
simpl. |
| 378 |
split. |
| 379 |
discriminate. |
| 380 |
change (Zpos p <= Zpos (Pos.succ p))%Z. |
| 381 |
repeat rewrite Zpos_succ_morphism. |
| 382 |
auto with *. |
| 383 |
simpl. |
| 384 |
apply Qrecip_positives_dnn. |
| 385 |
Qed. |
| 386 |
|
| 387 |
(** |
| 388 |
*** [pfactorials] |
| 389 |
The stream of factorials as positives. |
| 390 |
|
| 391 |
Again, we do not use [factorials] because [positive] does not form a semiring. |
| 392 |
*) |
| 393 |
CoFixpoint pfactorials_help (n c:positive) : Stream positive := |
| 394 |
Cons c (pfactorials_help (Pos.succ n) (n*c)). |
| 395 |
|
| 396 |
Definition pfactorials := pfactorials_help 1 1. |
| 397 |
|
| 398 |
Lemma Str_nth_pfactorials : forall n, nat_of_P (Str_nth n pfactorials) ≡ fact n. |
| 399 |
Proof. |
| 400 |
unfold pfactorials. |
| 401 |
intros n. |
| 402 |
pose (ONE:=1%positive). |
| 403 |
replace (fact n) with ((nat_of_P 1)*fact (pred (nat_of_P ONE) + n))%nat by (simpl;auto). |
| 404 |
replace (nat_of_P (Str_nth n (pfactorials_help 1 1))) |
| 405 |
with ((fact (pred (nat_of_P ONE)))*(nat_of_P (Str_nth n (pfactorials_help ONE 1))))%nat by (simpl; auto with * ). |
| 406 |
change (pfactorials_help 1 1) with (pfactorials_help ONE 1). |
| 407 |
generalize ONE. |
| 408 |
generalize 1%positive. |
| 409 |
unfold ONE; clear ONE. |
| 410 |
induction n. |
| 411 |
intros a b. |
| 412 |
unfold Str_nth. |
| 413 |
simpl. |
| 414 |
rewrite Nat.add_comm. |
| 415 |
now rewrite Nat.mul_comm. |
| 416 |
intros a b. |
| 417 |
unfold Str_nth in *. |
| 418 |
simpl. |
| 419 |
assert (X:=IHn (b*a)%positive (Pos.succ b)). |
| 420 |
clear IHn. |
| 421 |
rewrite nat_of_P_succ_morphism in X. |
| 422 |
rewrite <- plus_n_Sm. |
| 423 |
assert (forall (n m:nat), eq (Z_of_nat n) (Z_of_nat m) -> eq n m). |
| 424 |
{ intros i j H. intuition. } |
| 425 |
apply H. clear H. |
| 426 |
apply Zmult_reg_l with (Z.of_nat (nat_of_P b)); |
| 427 |
[rewrite positive_nat_Z; auto with *|]. |
| 428 |
do 2 rewrite <- (inj_mult (nat_of_P b)). |
| 429 |
apply inj_eq. |
| 430 |
rewrite (Nat.mul_assoc (nat_of_P b) (nat_of_P a)). |
| 431 |
rewrite <- Pos2Nat.inj_mul. |
| 432 |
rewrite <- pred_Sn in X. |
| 433 |
change (S (pred (nat_of_P b) + n))%nat with (S (pred (nat_of_P b)) + n)%nat. |
| 434 |
assert (Z:S (pred (nat_of_P b)) = nat_of_P b). |
| 435 |
{ apply (Nat.lt_succ_pred 0). apply Pos2Nat.is_pos. } |
| 436 |
rewrite Z. |
| 437 |
rewrite <- X. |
| 438 |
replace (fact (nat_of_P b)) with (fact (S (pred (nat_of_P b)))) by congruence. |
| 439 |
change (fact (S (pred (nat_of_P b)))) with ((S (pred (nat_of_P b)))*(fact (pred (nat_of_P b))))%nat. |
| 440 |
rewrite Z. |
| 441 |
ring. |
| 442 |
Qed. |
| 443 |
|
| 444 |
Lemma Str_nth_pfactorials' n |
| 445 |
: inject_Z (Zpos (Str_nth n pfactorials)) = Str_nth n factorials. |
| 446 |
Proof. |
| 447 |
rewrite Str_nth_factorials. |
| 448 |
rewrite <-Str_nth_pfactorials. |
| 449 |
rewrite <-(naturals.to_semiring_unique (Basics.compose inject_Z Z_of_nat)). |
| 450 |
unfold Basics.compose. |
| 451 |
rewrite positive_nat_Z. reflexivity. |
| 452 |
Qed. |
| 453 |
|
| 454 |
(** |
| 455 |
*** [Qrecip_factorials] |
| 456 |
The stream of 1/n!. |
| 457 |
**) |
| 458 |
Definition Qrecip_factorials := CoqStreams.map (fun x => 1#x) pfactorials. |
| 459 |
|
| 460 |
Lemma Str_nth_Qrecip_factorials : forall n, (Str_nth n Qrecip_factorials) = 1#(P_of_succ_nat (pred (fact n))). |
| 461 |
Proof. |
| 462 |
intros n. |
| 463 |
unfold Qrecip_factorials. |
| 464 |
rewrite Str_nth_map. |
| 465 |
rewrite <- Str_nth_pfactorials. |
| 466 |
unfold equiv, stdlib_rationals.Q_eq, Qeq. simpl. |
| 467 |
apply f_equal. |
| 468 |
transitivity (Pos.of_nat (Pos.to_nat (Str_nth n pfactorials))). |
| 469 |
2: apply Pos2Nat.id. |
| 470 |
destruct (Pos.to_nat (Str_nth n pfactorials)) eqn:des. |
| 471 |
2: apply Pos.of_nat_succ. |
| 472 |
exfalso. pose proof (Pos2Nat.is_pos (Str_nth n pfactorials)). |
| 473 |
rewrite des in H. inversion H. |
| 474 |
Qed. |
| 475 |
|
| 476 |
Lemma Str_nth_Qrecip_factorials' n : Str_nth n Qrecip_factorials = / Str_nth n factorials. |
| 477 |
Proof. |
| 478 |
unfold Qrecip_factorials. |
| 479 |
rewrite Str_nth_map. |
| 480 |
rewrite Qmake_Qdiv. |
| 481 |
rewrite Str_nth_pfactorials'. |
| 482 |
now apply (left_identity (/ Str_nth n factorials)). |
| 483 |
Qed. |
| 484 |
|
| 485 |
(** [Qrecip_factorials] is [DecreasingNonNegative]. *) |
| 486 |
#[global] |
| 487 |
Instance Qrecip_factorials_dnn : DecreasingNonNegative Qrecip_factorials. |
| 488 |
Proof. |
| 489 |
unfold Qrecip_factorials. |
| 490 |
unfold pfactorials. |
| 491 |
generalize (1%positive) at 3. generalize (1%positive) at 2. |
| 492 |
cofix Qrecip_factorials_dnn. |
| 493 |
intros a b. |
| 494 |
constructor. |
| 495 |
simpl. |
| 496 |
split. |
| 497 |
discriminate. |
| 498 |
apply (Z.mul_le_mono_nonneg_r 1 (Zpos a) (Zpos b)). |
| 499 |
discriminate. apply Pos.le_1_l. |
| 500 |
simpl. |
| 501 |
apply Qrecip_factorials_dnn. |
| 502 |
Qed. |
| 503 |
|
| 504 |
(** The limit of [Qrecip_factorial] is 0. *) |
| 505 |
Lemma Qrecip_factorial_bounded |
| 506 |
: StreamBounds Qrecip_positives (CoqStreams.tl Qrecip_factorials). |
| 507 |
Proof. |
| 508 |
unfold Qrecip_positives, Qrecip_factorials, ppositives, pfactorials. |
| 509 |
cut (forall (p q:positive), StreamBounds (CoqStreams.map (fun x : positive => 1 # x) (ppositives_help p)) |
| 510 |
(CoqStreams.tl (CoqStreams.map (fun x : positive => 1 # x) (pfactorials_help p q)))). |
| 511 |
intros H. |
| 512 |
apply (H 1%positive 1%positive). |
| 513 |
auto with *. |
| 514 |
cofix Qrecip_factorial_bounded. |
| 515 |
constructor. |
| 516 |
simpl. |
| 517 |
split. |
| 518 |
discriminate. |
| 519 |
change (Zpos p <= Zpos p * Zpos q)%Z. |
| 520 |
rewrite Z.mul_comm. |
| 521 |
apply (Z.mul_le_mono_nonneg_r 1 (Zpos q) (Zpos p)). |
| 522 |
discriminate. apply Pos.le_1_l. |
| 523 |
simpl in *. |
| 524 |
apply Qrecip_factorial_bounded. |
| 525 |
Qed. |
| 526 |
|
| 527 |
#[global] |
| 528 |
Instance Qrecip_factorials_zl : Limit Qrecip_factorials 0. |
| 529 |
Proof. |
| 530 |
intros e. |
| 531 |
right. |
| 532 |
intros _. |
| 533 |
apply (Stream_Bound_zl _ _ Qrecip_factorial_bounded). |
| 534 |
apply Qrecip_positives_zl. |
| 535 |
Defined. |
| 536 |
|
| 537 |
Section StreamGenerators. |
| 538 |
(* Strictly speaking those are generators of streams with a state X, |
| 539 |
or stream co-algebras, rather than actual streams. Instead of using |
| 540 |
corecursion to produce actual coinductive streams, we directly call |
| 541 |
the generator functions. |
| 542 |
|
| 543 |
The type Stream Y is isomorphic the type nat -> Y. We use the former |
| 544 |
to compute series such as exp x = sum_k x^k / k! |
| 545 |
because the (k+1)-th term is quickly computed from the k-th term, |
| 546 |
rather than recomputing the power and the factorial from 0 for each k. *) |
| 547 |
|
| 548 |
Variable X : Type. |
| 549 |
Variable f : X -> X. |
| 550 |
|
| 551 |
Fixpoint iterate (p : positive) (x : X) : X := |
| 552 |
match p with |
| 553 |
| xI q => iterate q (iterate q (f x)) |
| 554 |
| xO q => iterate q (iterate q x) |
| 555 |
| xH => f x |
| 556 |
end. |
| 557 |
|
| 558 |
Lemma iterate_one : forall x:X, |
| 559 |
iterate 1 x ≡ f x. |
| 560 |
Proof. |
| 561 |
reflexivity. |
| 562 |
Qed. |
| 563 |
|
| 564 |
Lemma iterate_shift : forall (p:positive) (x : X), |
| 565 |
f (iterate p x) ≡ iterate p (f x). |
| 566 |
Proof. |
| 567 |
induction p. |
| 568 |
- intro x. simpl. |
| 569 |
rewrite IHp, IHp. reflexivity. |
| 570 |
- intro x. simpl. |
| 571 |
rewrite IHp, IHp. reflexivity. |
| 572 |
- reflexivity. |
| 573 |
Qed. |
| 574 |
|
| 575 |
Lemma iterate_succ : forall (p:positive) (x : X), |
| 576 |
iterate (Pos.succ p) x ≡ f (iterate p x). |
| 577 |
Proof. |
| 578 |
induction p. |
| 579 |
- intro x. simpl. |
| 580 |
rewrite IHp. f_equal. |
| 581 |
rewrite IHp. f_equal. |
| 582 |
rewrite iterate_shift. reflexivity. |
| 583 |
- intro x. simpl. |
| 584 |
rewrite iterate_shift, iterate_shift. |
| 585 |
reflexivity. |
| 586 |
- reflexivity. |
| 587 |
Qed. |
| 588 |
|
| 589 |
Lemma iterate_add : forall (p q:positive) (x : X), |
| 590 |
iterate (p+q)%positive x ≡ iterate p (iterate q x). |
| 591 |
Proof. |
| 592 |
apply (Pos.peano_ind |
| 593 |
(fun p => forall (q : positive) (x : X), |
| 594 |
iterate (p + q) x ≡ iterate p (iterate q x))). |
| 595 |
- intros. rewrite Pos.add_1_l, iterate_succ. reflexivity. |
| 596 |
- intros. rewrite iterate_succ. |
| 597 |
rewrite <- Pos.add_1_l, <- Pos.add_assoc, Pos.add_1_l. |
| 598 |
rewrite iterate_succ, H. reflexivity. |
| 599 |
Qed. |
| 600 |
|
| 601 |
Variable stop : X -> bool. |
| 602 |
|
| 603 |
(* iterate_stop p x = iterate q x, where q = p or q < p and |
| 604 |
q is the lowest index such as stop (iterate q) = true. |
| 605 |
Testing whether the recursive iterate_stop stops regrettably |
| 606 |
adds a logarithmic useless number of stop tests. |
| 607 |
This could be improved by returning a pair X*bool to indicate |
| 608 |
that the iteration stopped. We could also try using a LazyNat fuel. *) |
| 609 |
Fixpoint iterate_stop (p : positive) (x : X) : X := |
| 610 |
match p with |
| 611 |
| xI q => (* p = 2q+1 *) |
| 612 |
let g := f x in |
| 613 |
if stop g then g else |
| 614 |
let h := iterate_stop q g in |
| 615 |
if stop h then h else iterate_stop q h |
| 616 |
| xO q => let g := iterate_stop q x in |
| 617 |
if stop g then g else iterate_stop q g |
| 618 |
| xH => f x |
| 619 |
end. |
| 620 |
|
| 621 |
(* The q below is even unique. Because it is either p or |
| 622 |
the first index where iterate stops. *) |
| 623 |
Lemma iterate_stop_correct : forall (p:positive) (x:X), |
| 624 |
exists q:positive, |
| 625 |
iterate_stop p x ≡ iterate q x |
| 626 |
/\ (forall r, Pos.lt r q -> stop (iterate r x) ≡ false) |
| 627 |
/\ (p ≡ q |
| 628 |
\/ (Pos.lt q p /\ stop (iterate q x) ≡ true)). |
| 629 |
Proof. |
| 630 |
induction p. |
| 631 |
- intro x. simpl. |
| 632 |
destruct (stop (f x)) eqn:des1. |
| 633 |
exists xH. split. reflexivity. |
| 634 |
split. intros. exfalso; exact (Pos.nlt_1_r r H). |
| 635 |
right. split. rewrite Pos.xI_succ_xO. |
| 636 |
apply Pos.lt_1_succ. |
| 637 |
exact des1. |
| 638 |
destruct (stop (iterate_stop p (f x))) eqn:des. |
| 639 |
+ (* Stopped at p+1 by the stop predicate, |
| 640 |
prove that value is the same at 2p+1. *) |
| 641 |
specialize (IHp (f x)) as [q [itereq [H H0]]]. |
| 642 |
exists (Pos.succ q). split. |
| 643 |
rewrite itereq, iterate_succ, iterate_shift. |
| 644 |
reflexivity. split. |
| 645 |
apply (Pos.peano_case |
| 646 |
(fun r => (r < Pos.succ q)%positive → stop (iterate r x) ≡ false)). |
| 647 |
intros. exact des1. intros. |
| 648 |
rewrite iterate_succ, iterate_shift. apply H. |
| 649 |
apply Pos.succ_lt_mono in H1. |
| 650 |
exact H1. right. |
| 651 |
split. rewrite Pos.xI_succ_xO. |
| 652 |
rewrite <- Pos.succ_lt_mono. |
| 653 |
destruct H0. rewrite H0. |
| 654 |
rewrite <- Pos.add_diag. apply Pos.lt_add_r. |
| 655 |
apply (Pos.lt_trans _ p). apply H0. |
| 656 |
rewrite <- Pos.add_diag. apply Pos.lt_add_r. |
| 657 |
rewrite iterate_succ, iterate_shift, <- itereq. exact des. |
| 658 |
+ pose proof (IHp (f x)) as [q [itereq [H H0]]]. |
| 659 |
destruct H0. |
| 660 |
2: exfalso; destruct H0; rewrite <- itereq, des in H1; discriminate. |
| 661 |
subst q. |
| 662 |
specialize (IHp (iterate_stop p (f x))) as [q [qeq [H0 H1]]]. |
| 663 |
exists (Pos.succ q+p)%positive. split. |
| 664 |
rewrite qeq. |
| 665 |
rewrite <- Pos.add_1_r, <- Pos.add_assoc, iterate_add. |
| 666 |
apply f_equal. |
| 667 |
rewrite Pos.add_1_l, itereq, iterate_succ, iterate_shift. |
| 668 |
reflexivity. split. |
| 669 |
apply (Pos.peano_case |
| 670 |
(fun r => (r < Pos.succ q+p)%positive → stop (iterate r x) ≡ false)). |
| 671 |
intros. exact des1. |
| 672 |
intros r H2. |
| 673 |
rewrite iterate_succ, iterate_shift. |
| 674 |
destruct (Pos.lt_total r p). |
| 675 |
apply H, H3. |
| 676 |
destruct H3. rewrite H3. |
| 677 |
rewrite <- itereq. exact des. |
| 678 |
rewrite <- (Pplus_minus r p). |
| 679 |
2: apply Pos.lt_gt, H3. |
| 680 |
rewrite Pos.add_comm, iterate_add, <- itereq. |
| 681 |
apply (H0 (r-p)%positive). |
| 682 |
rewrite <- (Pos.add_1_l q), <- Pos.add_assoc, Pos.add_1_l in H2. |
| 683 |
apply Pos.succ_lt_mono in H2. |
| 684 |
rewrite <- (Pplus_minus r p) in H2. |
| 685 |
2: apply Pos.lt_gt, H3. |
| 686 |
rewrite Pos.add_comm in H2. |
| 687 |
apply Pos.add_lt_mono_r in H2. exact H2. |
| 688 |
destruct H1. left. rewrite H1. |
| 689 |
rewrite Pos.xI_succ_xO. |
| 690 |
rewrite <- (Pos.add_1_l q), <- Pos.add_assoc, Pos.add_1_l. |
| 691 |
rewrite Pos.add_diag. reflexivity. |
| 692 |
right. split. rewrite Pos.xI_succ_xO. |
| 693 |
rewrite <- Pos.add_1_l, <- Pos.add_assoc, Pos.add_1_l. |
| 694 |
rewrite <- Pos.succ_lt_mono, <- Pos.add_diag. |
| 695 |
apply Pos.add_lt_mono_r, H1. |
| 696 |
rewrite <- Pos.add_1_r, <- Pos.add_assoc, iterate_add. |
| 697 |
rewrite Pos.add_1_l, iterate_succ, iterate_shift. |
| 698 |
rewrite <- itereq. apply H1. |
| 699 |
- intro x. simpl. |
| 700 |
destruct (stop (iterate_stop p x)) eqn:des. |
| 701 |
+ (* Stopped at p by the stop predicate, |
| 702 |
prove that value is the same at 2p. *) |
| 703 |
specialize (IHp x) as [q [itereq [H H0]]]. |
| 704 |
exists q. split. exact itereq. split. |
| 705 |
intros. apply H, H1. right. |
| 706 |
split. destruct H0. |
| 707 |
rewrite H0. rewrite <- Pos.add_diag. apply Pos.lt_add_r. |
| 708 |
apply (Pos.lt_trans _ p). apply H0. |
| 709 |
rewrite <- Pos.add_diag. apply Pos.lt_add_r. |
| 710 |
rewrite <- itereq. exact des. |
| 711 |
+ pose proof (IHp x) as [q [itereq [H H0]]]. |
| 712 |
destruct H0. |
| 713 |
2: exfalso; destruct H0; rewrite <- itereq, des in H1; discriminate. |
| 714 |
subst q. |
| 715 |
specialize (IHp (iterate_stop p x)) as [q [qeq [H0 H1]]]. |
| 716 |
exists (q+p)%positive. split. |
| 717 |
rewrite qeq, iterate_add. |
| 718 |
apply f_equal. exact itereq. |
| 719 |
split. intros. |
| 720 |
destruct (Pos.lt_total r p). |
| 721 |
apply H, H3. destruct H3. rewrite H3. clear H3 H2 r. |
| 722 |
rewrite <- itereq. exact des. |
| 723 |
rewrite <- (Pplus_minus r p). |
| 724 |
2: apply Pos.lt_gt, H3. |
| 725 |
rewrite Pos.add_comm, iterate_add, <- itereq. |
| 726 |
apply (H0 (r-p)%positive). |
| 727 |
rewrite <- (Pplus_minus r p) in H2. |
| 728 |
2: apply Pos.lt_gt, H3. |
| 729 |
rewrite Pos.add_comm in H2. |
| 730 |
apply Pos.add_lt_mono_r in H2. |
| 731 |
exact H2. |
| 732 |
destruct H1. left. rewrite H1. |
| 733 |
rewrite Pos.add_diag. reflexivity. |
| 734 |
right. split. |
| 735 |
rewrite <- Pos.add_diag. |
| 736 |
apply Pos.add_lt_mono_r, H1. |
| 737 |
rewrite iterate_add, <- itereq. apply H1. |
| 738 |
- intro x. exists xH. split. reflexivity. |
| 739 |
split. intros. exfalso; exact (Pos.nlt_1_r r H). |
| 740 |
left. reflexivity. |
| 741 |
Qed. |
| 742 |
|
| 743 |
Lemma iterate_stop_one : forall (x : X), |
| 744 |
iterate_stop 1 x ≡ f x. |
| 745 |
Proof. |
| 746 |
reflexivity. |
| 747 |
Qed. |
| 748 |
|
| 749 |
Lemma iterate_stop_indep : forall (p q : positive) (x : X), |
| 750 |
stop (iterate p x) ≡ true |
| 751 |
-> stop (iterate q x) ≡ true |
| 752 |
-> iterate_stop p x ≡ iterate_stop q x. |
| 753 |
Proof. |
| 754 |
intros. |
| 755 |
pose proof (iterate_stop_correct p x) as [r [rpeq [H1 H2]]]. |
| 756 |
assert (stop (iterate r x) ≡ true) as rstop. |
| 757 |
{ destruct H2. rewrite <- H2. exact H. apply H2. } |
| 758 |
rewrite rpeq. clear H2 rpeq H p. |
| 759 |
pose proof (iterate_stop_correct q x) as [s [sqeq [H H2]]]. |
| 760 |
assert (stop (iterate s x) ≡ true) as sstop. |
| 761 |
{ destruct H2. rewrite <- H2. exact H0. apply H2. } |
| 762 |
rewrite sqeq. clear H2 sqeq H0 q. |
| 763 |
destruct (Pos.lt_total r s). |
| 764 |
- exfalso. specialize (H r H0). |
| 765 |
rewrite H in rstop. discriminate. |
| 766 |
- destruct H0. rewrite H0. reflexivity. |
| 767 |
exfalso. specialize (H1 s H0). |
| 768 |
rewrite H1 in sstop. discriminate. |
| 769 |
Qed. |
| 770 |
|
| 771 |
Lemma iterate_stop_unique : forall (p q : positive) (x : X), |
| 772 |
stop (iterate p x) ≡ true |
| 773 |
-> stop (iterate q x) ≡ true |
| 774 |
-> (forall i:positive, Pos.lt i q -> stop (iterate i x) ≡ false) |
| 775 |
-> iterate_stop p x ≡ iterate q x. |
| 776 |
Proof. |
| 777 |
intros. |
| 778 |
pose proof (iterate_stop_correct p x) as [r [rpeq [H2 H3]]]. |
| 779 |
rewrite rpeq. replace r with q. reflexivity. |
| 780 |
destruct (Pos.lt_total q r). |
| 781 |
- exfalso. specialize (H2 q H4). rewrite H0 in H2. discriminate. |
| 782 |
- destruct H4. exact H4. exfalso. |
| 783 |
destruct H3. |
| 784 |
+ subst r. |
| 785 |
specialize (H1 p H4). rewrite H in H1. discriminate. |
| 786 |
+ destruct H3. specialize (H1 r H4). |
| 787 |
rewrite H1 in H5. discriminate. |
| 788 |
Qed. |
| 789 |
|
| 790 |
Definition CRstream_opp (X:Type) (f : X*Q->X*Q) (xq : X*Q) : X*Q |
| 791 |
:= let (x,q) := xq in |
| 792 |
let (y,r) := f (x,-q) in |
| 793 |
(y,-r). |
| 794 |
|
| 795 |
End StreamGenerators. |
| 796 |
|
| 797 |
Lemma CRstream_opp_pth : forall (X:Type) (f : X*Q->X*Q) (xq : X*Q) (p : positive), |
| 798 |
let (y,r) := iterate _ f p xq in |
| 799 |
let (z,s) := iterate _ (CRstream_opp X f) p (let (x,q):=xq in (x,-q)) in |
| 800 |
y ≡ z /\ s ≡ -r. |
| 801 |
Proof. |
| 802 |
intros X f xq. |
| 803 |
apply Pos.peano_ind. |
| 804 |
- simpl. destruct xq as [x q]. |
| 805 |
unfold CRstream_opp. |
| 806 |
replace (--q) with q. destruct (f (x,q)). |
| 807 |
split; reflexivity. |
| 808 |
destruct q. unfold Qopp; simpl. |
| 809 |
rewrite Z.opp_involutive. reflexivity. |
| 810 |
- intros IHp H. |
| 811 |
rewrite CRstreams.iterate_succ, CRstreams.iterate_succ. |
| 812 |
destruct (iterate _ f IHp xq), |
| 813 |
(iterate _ (CRstream_opp X f) IHp |
| 814 |
(let (x0, q0) := xq in (x0, - q0))). |
| 815 |
unfold CRstream_opp. destruct H. subst q0. subst x0. |
| 816 |
replace (--q) with q. destruct (f (x,q)). |
| 817 |
split; reflexivity. |
| 818 |
destruct q. unfold Qopp; simpl. |
| 819 |
rewrite Z.opp_involutive. reflexivity. |
| 820 |
Qed. |