Debian Codegraph @

reals/fast/CRAlternatingSum.v

raw
1 (*
2 Copyright © 2006-2008 Russell O’Connor
3
4 Permission is hereby granted, free of charge, to any person obtaining a copy of
5 this proof and associated documentation files (the "Proof"), to deal in
6 the Proof without restriction, including without limitation the rights to
7 use, copy, modify, merge, publish, distribute, sublicense, and/or sell copies of
8 the Proof, and to permit persons to whom the Proof is furnished to do so,
9 subject to the following conditions:
10
11 The above copyright notice and this permission notice shall be included in all
12 copies or substantial portions of the Proof.
13
14 THE PROOF IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
15 IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, FITNESS
16 FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR
17 COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER
18 IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN
19 CONNECTION WITH THE PROOF OR THE USE OR OTHER DEALINGS IN THE PROOF.
20 *)
21
22 From Coq Require Import ArithRing.
23 From Coq Require Import Bool.
24 From Coq Require Import ZArith.
25 From Coq Require Import Qpower Qabs.
26 Require Import CoRN.algebra.RSetoid.
27 Require Import CoRN.metric2.Metric.
28 Require Import CoRN.metric2.UniformContinuity.
29 Require Export CoRN.reals.fast.CRArith.
30 Require Export CoRN.model.metric2.Qmetric.
31 Require Import CoRN.reals.fast.LazyNat.
32 Require Import CoRN.reals.fast.CRstreams.
33 Require Export CoRN.metric2.Limit.
34 Require Import CoRN.model.totalorder.QposMinMax.
35 Require Import CoRN.classes.Qclasses.
36 Require Import MathClasses.interfaces.abstract_algebra.
37
38 Opaque CR.
39
40 (**
41 ** Computing Alternating Series.
42 Alternating series are particularly nice to sum because each term is also
43 a bound on the error of the partial sum.
44 *)
45
46 Section RationalStreamSum.
47 Variable X : Type.
48
49 (* The current rational value is part of the state. For example a^k/k! is
50 used to produce a^(k+1)/(k+1)! by multiplying by a and dividing
51 by k+1. *)
52 Variable f : X*Q -> X*Q.
53
54 Definition Str_pth (p : positive) (x:X*Q) : Q
55 := snd (CRstreams.iterate _ f p x).
56
57 (* Decreasing and alternating stream. *)
58 Definition Str_alt_decr (x:X*Q) : Prop
59 := forall p : positive,
60 Qabs (Str_pth (Pos.succ p) x) <= Qabs (Str_pth p x)
61 /\ (Str_pth (Pos.succ p) x)*(Str_pth p x) <= 0.
62
63 Lemma Str_alt_decr_tl : forall x p,
64 Str_alt_decr x -> Str_alt_decr (CRstreams.iterate _ f p x).
65 Proof.
66 assert (forall x, Str_alt_decr x -> Str_alt_decr (f x)).
67 { intros x H p.
68 specialize (H (Pos.succ p)).
69 unfold Str_pth.
70 unfold Str_pth in H.
71 rewrite <- iterate_shift, <- iterate_succ.
72 rewrite <- iterate_shift, <- iterate_succ.
73 apply H. }
74 intros x p. revert p x.
75 apply (Pos.peano_ind (fun p => forall (x : X * Q),
76 Str_alt_decr x → Str_alt_decr (CRstreams.iterate (X * Q) f p x))).
77 - intros. simpl. apply H, H0.
78 - intros. rewrite iterate_succ. apply H, H0, H1.
79 Qed.
80
81 Lemma Str_alt_even_step : forall p x,
82 Str_alt_decr x ->
83 0 <= Str_pth p x * Str_pth (p+2) x.
84 Proof.
85 intros. pose proof (H p). pose proof (H (Pos.succ p)).
86 destruct H0, H1.
87 replace (p+2)%positive with (Pos.succ (Pos.succ p)).
88 destruct (Str_pth p x).
89 destruct (Str_pth (Pos.succ p) x).
90 destruct (Str_pth (Pos.succ (Pos.succ p)) x).
91 unfold Qmult, Qle; simpl. rewrite Z.mul_1_r.
92 unfold Qmult, Qle in H2; simpl in H2. rewrite Z.mul_1_r in H2.
93 unfold Qmult, Qle in H3; simpl in H3. rewrite Z.mul_1_r in H3.
94 destruct Qnum, Qnum1; try discriminate.
95 destruct Qnum0.
96 exfalso; apply H1; reflexivity.
97 exfalso; apply H2; reflexivity.
98 exfalso; apply H3; reflexivity.
99 destruct Qnum0.
100 exfalso; apply H1; reflexivity.
101 exfalso; apply H3; reflexivity.
102 exfalso; apply H2; reflexivity.
103 rewrite <- Pos.add_1_r, <- Pos.add_1_r.
104 rewrite <- Pos.add_assoc. reflexivity.
105 Qed.
106
107 Lemma Str_alt_zero : forall p x,
108 Str_alt_decr x ->
109 Str_pth p x == 0 -> Str_pth (Pos.succ p) x == 0.
110 Proof.
111 intros. pose proof (H p) as [H1 _].
112 rewrite H0 in H1.
113 apply Qabs_Qle_condition in H1. destruct H1.
114 apply (Qle_antisym _ _ H2) in H1. exact H1.
115 Qed.
116
117 Lemma Str_alt_neg : forall p x,
118 Str_alt_decr x -> 0 <= snd (f x) -> Str_pth (p~0) x <= 0.
119 Proof.
120 apply (Pos.peano_ind (fun p => forall (x : X * Q),
121 Str_alt_decr x → 0 <= snd (f x) →
122 Str_pth (p~0) x <= 0)).
123 - intros. simpl. specialize (H xH).
124 unfold Str_pth in H. simpl in H. destruct H.
125 destruct (Q_dec (snd (f x)) 0).
126 destruct s.
127 exfalso; exact (Qlt_not_le _ _ q H0).
128 rewrite <- (Qmult_0_l (snd (f x))) in H1.
129 apply Qmult_le_r in H1. exact H1. exact q.
130 rewrite q in H.
131 exact (Qle_trans _ _ _ (Qle_Qabs _) H).
132 - intros. pose proof (Str_alt_even_step (p~0) x H0).
133 specialize (H x H0 H1).
134 replace (p~0+2)%positive with ((Pos.succ p)~0)%positive in H2.
135 apply Qnot_lt_le. intro abs.
136 rewrite <- (Qmult_0_l (Str_pth ((Pos.succ p)~0) x)) in H2.
137 apply Qmult_le_r in H2. 2: exact abs.
138 apply (Qle_antisym _ _ H) in H2. clear H.
139 apply (Str_alt_zero _ _ H0) in H2.
140 apply (Str_alt_zero _ _ H0) in H2.
141 rewrite <- Pos.double_succ in H2.
142 rewrite H2 in abs. exact (Qlt_irrefl 0 abs).
143 rewrite Pos.double_succ.
144 rewrite <- Pos.add_1_r, <- Pos.add_1_r, <- Pos.add_assoc. reflexivity.
145 Qed.
146
147 Lemma Str_alt_pos : forall p x,
148 Str_alt_decr x ->
149 0 <= snd (f x) ->
150 0 <= snd (CRstreams.iterate (X * Q) f p~1 x).
151 Proof.
152 intros.
153 rewrite Pos.xI_succ_xO.
154 pose proof (Str_alt_neg p x H H0).
155 specialize (H (p~0))%positive.
156 unfold Str_pth in H. destruct H.
157 destruct (Q_dec 0 (snd (CRstreams.iterate (X * Q) f p~0 x))).
158 destruct s.
159 exfalso; exact (Qlt_not_le _ _ q H1).
160 apply Qopp_le_compat in H2.
161 change (-0)%Q with 0%Q in H2.
162 setoid_replace (- (snd (CRstreams.iterate (X * Q) f (Pos.succ p~0) x) *
163 snd (CRstreams.iterate (X * Q) f p~0 x)))%Q
164 with ( (snd (CRstreams.iterate (X * Q) f (Pos.succ p~0) x) *
165 -snd (CRstreams.iterate (X * Q) f p~0 x)))%Q in H2
166 by (unfold equiv, Q_eq; ring).
167 rewrite <- (Qmult_0_l (-snd (CRstreams.iterate (X * Q) f p~0 x))) in H2.
168 apply Qmult_le_r in H2. exact H2.
169 rewrite <- (Qplus_0_l (- snd (CRstreams.iterate (X * Q) f p~0 x))).
170 rewrite <- Qlt_minus_iff. exact q.
171 rewrite <- q in H.
172 apply Qabs_Qle_condition in H. apply H.
173 Qed.
174
175 Definition Limit_zero x (cvmod : Qpos -> positive) : Prop
176 := forall q:Qpos, Qabs (Str_pth (cvmod q) x) <= proj1_sig q.
177
178 Lemma Limit_zero_tl : forall x (cvmod : Qpos -> positive) (p : positive),
179 Str_alt_decr x ->
180 Limit_zero x cvmod -> Limit_zero (CRstreams.iterate _ f p x)
181 (fun e => cvmod e - p)%positive.
182 Proof.
183 intros. intro e.
184 unfold Str_pth.
185 rewrite <- iterate_add.
186 assert (forall q:positive,
187 Qabs (snd (CRstreams.iterate (X * Q) f (q+cvmod e) x)) <= ` e).
188 { apply Pos.peano_ind.
189 - intros. rewrite Pos.add_1_l.
190 apply (Qle_trans _ (Qabs (snd (CRstreams.iterate (X * Q) f (cvmod e) x)))).
191 apply H. apply H0.
192 - intros.
193 rewrite <- Pos.add_1_l, <- Pos.add_assoc, Pos.add_1_l.
194 refine (Qle_trans _ _ _ _ H1).
195 apply H. }
196 destruct (Pos.lt_total p (cvmod e)).
197 2: destruct H2.
198 - rewrite Pos.sub_add. apply H0. exact H2.
199 - subst p. rewrite Pos.sub_diag. apply H1.
200 - rewrite Pos.sub_lt. 2: exact H2.
201 replace (1+p)%positive with (1+(p-cvmod e)+cvmod e)%positive.
202 apply H1. rewrite <- Pos.add_assoc.
203 apply f_equal. rewrite Pos.sub_add. reflexivity. exact H2.
204 Qed.
205
206 Definition SumStream x (p : positive) (e : Qpos) : Q
207 := snd (iterate_stop
208 _
209 (fun y:X*Q*Q =>
210 let (z,r) := f (fst y) in
211 (z, r, Qred (r + snd y)))
212 (fun y:X*Q*Q => Qle_bool (Qabs (snd (fst y))) (proj1_sig e))
213 p (x, 0)).
214
215 Lemma SumStream_fst : forall p z,
216 fst (CRstreams.iterate _
217 (fun y:X*Q*Q =>
218 let (z,r) := f (fst y) in
219 (z, r, r + snd y))
220 p z)
221 ≡ CRstreams.iterate _ f p (fst z).
222 Proof.
223 apply (Pos.peano_ind (fun p => forall z : X * Q * Q,
224 fst
225 (CRstreams.iterate (X * Q * Q)
226 (fun y : X * Q * Q => let (z0, r) := f (fst y) in (z0, r, r + snd y)) p z)
227 ≡ CRstreams.iterate (X * Q) f p (fst z))).
228 - intro z. simpl. destruct (f (fst z)); reflexivity.
229 - intros. rewrite iterate_succ, H.
230 rewrite iterate_succ.
231 destruct (f (CRstreams.iterate (X * Q) f p (fst z))). reflexivity.
232 Qed.
233
234 Lemma SumStream_fst_red : forall p z,
235 fst (CRstreams.iterate _
236 (fun y:X*Q*Q =>
237 let (z,r) := f (fst y) in
238 (z, r, Qred (r + snd y)))
239 p z)
240 ≡ CRstreams.iterate _ f p (fst z).
241 Proof.
242 apply (Pos.peano_ind (fun p => forall z : X * Q * Q,
243 fst
244 (CRstreams.iterate (X * Q * Q)
245 (fun y : X * Q * Q => let (z0, r) := f (fst y) in (z0, r, Qred (r + snd y))) p z)
246 ≡ CRstreams.iterate (X * Q) f p (fst z))).
247 - intro z. simpl. destruct (f (fst z)); reflexivity.
248 - intros. rewrite iterate_succ, H.
249 rewrite iterate_succ.
250 destruct (f (CRstreams.iterate (X * Q) f p (fst z))). reflexivity.
251 Qed.
252
253 Lemma SumStream_red : forall (p:positive) z,
254 snd (CRstreams.iterate _
255 (fun y : X * Q * Q => let (z0, r1) := f (fst y) in (z0, r1, Qred (r1 + snd y)))
256 p z)
257 == snd (CRstreams.iterate _
258 (fun y : X * Q * Q => let (z0, r1) := f (fst y) in (z0, r1, r1 + snd y)) p z).
259 Proof.
260 apply (Pos.peano_ind
261 (fun p => forall z, snd (CRstreams.iterate _
262 (fun y : X * Q * Q => let (z0, r1) := f (fst y) in (z0, r1, Qred (r1 + snd y)))
263 p z) == snd (CRstreams.iterate _
264 (fun y : X * Q * Q => let (z0, r1) := f (fst y) in (z0, r1, r1 + snd y)) p z))).
265 - intros. rewrite iterate_one, iterate_one.
266 destruct (f (fst z)). apply Qred_correct.
267 - intros. rewrite iterate_succ, SumStream_fst_red.
268 rewrite iterate_succ, SumStream_fst.
269 destruct (f (CRstreams.iterate (X * Q) f p (fst z))).
270 unfold snd at 1 4.
271 rewrite Qred_correct.
272 rewrite H. reflexivity.
273 Qed.
274
275 Lemma SumStream_init : forall (p:positive) z (r:Q),
276 snd (CRstreams.iterate _
277 (fun y : X * Q * Q => let (z0, r1) := f (fst y) in (z0, r1, r1 + snd y)) p
278 (z, r)) ==
279 r +
280 snd (CRstreams.iterate _
281 (fun y : X * Q * Q => let (z0, r1) := f (fst y) in (z0, r1, r1 + snd y)) p
282 (z, 0)).
283 Proof.
284 apply (Pos.peano_ind (fun p => forall (z : X * Q) (r : Q),
285 snd (CRstreams.iterate (X * Q * Q)
286 (fun y : X * Q * Q => let (z0, r1) := f (fst y) in (z0, r1, r1 + snd y)) p
287 (z, r)) == r + snd
288 (CRstreams.iterate (X * Q * Q)
289 (fun y : X * Q * Q => let (z0, r1) := f (fst y) in (z0, r1, r1 + snd y)) p
290 (z, 0)))).
291 - intros. rewrite iterate_one, iterate_one.
292 unfold fst. destruct (f z). unfold snd.
293 rewrite Qplus_0_r. apply Qplus_comm.
294 - intros. rewrite iterate_succ, SumStream_fst.
295 rewrite iterate_succ, SumStream_fst.
296 change (fst (z,r)) with z.
297 change (fst (z,0)) with z.
298 destruct (f (CRstreams.iterate (X * Q) f p z)).
299 unfold snd at 1 4.
300 rewrite H.
301 rewrite (Qplus_comm q), <- Qplus_assoc.
302 rewrite <- (Qplus_comm q). reflexivity.
303 Qed.
304
305 Lemma SumStream_assoc : forall x (p q : positive),
306 snd (CRstreams.iterate _
307 (fun y : X * Q * Q =>
308 let (z, r0) := f (fst y) in (z, r0, r0 + snd y))
309 (p+q) (x,0))
310 == snd (CRstreams.iterate _
311 (fun y : X * Q * Q =>
312 let (z, r0) := f (fst y) in (z, r0, r0 + snd y))
313 p (x,0))
314 + snd (CRstreams.iterate _
315 (fun y : X * Q * Q =>
316 let (z, r0) := f (fst y) in (z, r0, r0 + snd y))
317 q (CRstreams.iterate _ f p x, 0)).
318 Proof.
319 intros x p. revert p x.
320 apply (Pos.peano_ind (fun p => forall x q,
321 snd (CRstreams.iterate (X * Q * Q)
322 (fun y : X * Q * Q => let (z, r0) := f (fst y) in (z, r0, r0 + snd y))
323 (p + q) (x, 0)) ==
324 snd (CRstreams.iterate (X * Q * Q)
325 (fun y : X * Q * Q => let (z, r0) := f (fst y) in (z, r0, r0 + snd y)) p
326 (x, 0)) +
327 snd
328 (CRstreams.iterate (X * Q * Q)
329 (fun y : X * Q * Q => let (z, r0) := f (fst y) in (z, r0, r0 + snd y)) q
330 (CRstreams.iterate _ f p x, 0)))).
331 - intros x q.
332 rewrite Pos.add_comm, iterate_add.
333 simpl.
334 destruct (f x) as [z r0].
335 rewrite SumStream_init. reflexivity.
336 - intros.
337 rewrite <- Pos.add_1_r, <- Pos.add_assoc, Pos.add_1_l.
338 rewrite H, H. simpl.
339 rewrite <- Qplus_assoc.
340 apply Qplus_comp. reflexivity. clear H.
341 rewrite iterate_add. simpl.
342 rewrite <- iterate_shift.
343 rewrite <- Pos.add_1_r, iterate_add. simpl.
344 destruct (f (CRstreams.iterate (X * Q) f p x)).
345 simpl. rewrite SumStream_init. reflexivity.
346 Qed.
347
348
349 (* Using AltSumF_stop is faster than AltSumF. *)
350 Definition AltSeries_raw x (cvmod : Qpos -> positive) (e : QposInf) : Q
351 := match e with
352 | Qpos2QposInf d => SumStream x (cvmod d) d
353 | QposInfinity => 0
354 end.
355
356 Lemma AltSeries_small_pos_even : forall p x,
357 Str_alt_decr x ->
358 0 <= snd (f x) ->
359 0 <= snd
360 (CRstreams.iterate (X * Q * Q)
361 (fun y : X * Q * Q => let (z, r0) := f (fst y) in (z, r0, r0 + snd y))
362 (p~0) (x, 0)).
363 Proof.
364 (* Sum of positive terms. *)
365 assert (forall x, Str_alt_decr x -> 0 <= snd (f x) ->
366 0 <= snd (CRstreams.iterate (X * Q * Q)
367 (fun y : X * Q * Q => let (z, r0) := f (fst y) in (z, r0, r0 + snd y))
368 (1 + 1) (x, 0))).
369 { intros.
370 pose proof (Str_alt_neg 1 x H H0) as H1.
371 unfold Str_pth in H1. simpl in H1.
372 specialize (H xH).
373 simpl. unfold Str_pth in H. simpl in H.
374 destruct (f x); simpl. simpl in H. unfold snd in H0.
375 destruct (f (x0,q)); simpl. rewrite Qplus_0_r.
376 simpl in H. unfold snd in H1.
377 destruct H.
378 rewrite Qabs_neg in H. 2: exact H1.
379 rewrite Qabs_pos in H. 2: exact H0.
380 apply Qle_minus_iff in H.
381 rewrite Qopp_involutive, Qplus_comm in H. exact H. }
382 apply (Pos.peano_ind (fun p => forall x, Str_alt_decr x -> 0 <= snd (f x) ->
383 0 <= snd (CRstreams.iterate (X * Q * Q)
384 (fun y : X * Q * Q => let (z, r0) := f (fst y) in (z, r0, r0 + snd y))
385 (p~0) (x, 0)))).
386 - intros. exact (H x H0 H1).
387 - intros.
388 rewrite <- Qplus_0_r.
389 rewrite Pos.double_succ, <- Pos.add_1_l, <- Pos.add_1_l.
390 rewrite Pos.add_assoc, SumStream_assoc.
391 apply Qplus_le_compat. exact (H x H1 H2).
392 apply H0. exact (Str_alt_decr_tl x 2 H1).
393 rewrite <- iterate_succ.
394 exact (Str_alt_pos _ x H1 H2).
395 Qed.
396
397 Lemma AltSeries_small_neg_even : forall p x,
398 Str_alt_decr x ->
399 snd (f x) <= 0 ->
400 snd (CRstreams.iterate (X * Q * Q)
401 (fun y : X * Q * Q => let (z, r0) := f (fst y) in (z, r0, r0 + snd y))
402 (p~0) (x, 0)) <= 0.
403 Proof.
404 (* Sum of negative terms. *)
405 assert (forall x, Str_alt_decr x -> snd (f x) <= 0 ->
406 snd (CRstreams.iterate (X * Q * Q)
407 (fun y : X * Q * Q => let (z, r0) := f (fst y) in (z, r0, r0 + snd y))
408 (1 + 1) (x, 0)) <= 0).
409 { intros.
410 specialize (H xH).
411 simpl. unfold Str_pth in H. simpl in H.
412 destruct (f x); simpl. simpl in H. unfold snd in H0.
413 destruct (f (x0,q)); simpl. rewrite Qplus_0_r.
414 simpl in H. destruct H.
415 apply (Qplus_le_l _ _ (-q)).
416 rewrite <- Qplus_assoc, Qplus_opp_r, Qplus_0_r.
417 apply (Qle_trans _ _ _ (Qle_Qabs _)).
418 apply (Qle_trans _ _ _ H).
419 rewrite Qplus_0_l, Qabs_neg.
420 apply Qle_refl. exact H0. }
421 apply (Pos.peano_ind (fun p => forall x, Str_alt_decr x -> snd (f x) <= 0 ->
422 snd (CRstreams.iterate (X * Q * Q)
423 (fun y : X * Q * Q => let (z, r0) := f (fst y) in (z, r0, r0 + snd y))
424 (p~0) (x, 0)) <= 0)).
425 - intros. exact (H x H0 H1).
426 - intros.
427 rewrite <- (Qplus_0_r 0).
428 rewrite Pos.double_succ, <- Pos.add_1_l, <- Pos.add_1_l.
429 rewrite Pos.add_assoc, SumStream_assoc.
430 apply Qplus_le_compat. exact (H x H1 H2).
431 apply H0. exact (Str_alt_decr_tl x 2 H1).
432 simpl. pose proof (Str_alt_even_step 1 x H1).
433 unfold Str_pth in H3. simpl in H3.
434 apply Qnot_lt_le. intro abs.
435 rewrite <- (Qmult_0_l (snd (f (f (f x))))) in H3.
436 apply Qmult_le_r in H3. 2: exact abs.
437 apply (Qle_antisym _ _ H2) in H3. clear H2.
438 apply (Str_alt_zero 1 _ H1) in H3.
439 apply (Str_alt_zero 2 _ H1) in H3.
440 unfold Str_pth in H3. simpl in H3.
441 rewrite H3 in abs. exact (Qlt_irrefl 0 abs).
442 Qed.
443
444 Lemma AltSeries_small_pos : forall x (p : positive),
445 Str_alt_decr x ->
446 0 <= snd (f x) ->
447 0 <= snd (CRstreams.iterate (X * Q * Q)
448 (fun y : X * Q * Q => let (z, r0) := f (fst y) in (z, r0, r0 + snd y))
449 p (x, 0)) <= snd (f x).
450 Proof.
451 (* This truncated sum starts at 0, and oscillates around 0
452 while staying in [-e,e]. *)
453 (* TODO remove induction. *)
454 intros x p. revert p x.
455 apply (Pos.peano_ind (fun p => forall x,
456 Str_alt_decr x ->
457 0 <= snd (f x) ->
458 0 <= snd (CRstreams.iterate (X * Q * Q)
459 (fun y : X * Q * Q => let (z, r0) := f (fst y) in (z, r0, r0 + snd y))
460 p (x, 0)) <= snd (f x))).
461 - intros. simpl. destruct (f x). simpl.
462 rewrite Qplus_0_r. split. exact H0. apply Qle_refl.
463 - intros. destruct p.
464 + split. rewrite Pos.xI_succ_xO, <- Pos.double_succ.
465 exact (AltSeries_small_pos_even _ x H0 H1).
466 rewrite <- Pos.add_1_r.
467 rewrite SumStream_assoc, iterate_one.
468 specialize (H x H0 H1) as [_ H].
469 apply (Qle_trans _ (snd (CRstreams.iterate _
470 (fun y : X * Q * Q => let (z, r0) := f (fst y) in (z, r0, r0 + snd y)) p~1
471 (x, 0)) + 0)).
472 2: rewrite Qplus_0_r; exact H.
473 apply Qplus_le_r. unfold fst.
474 apply (Qle_trans _ (snd (f (CRstreams.iterate (X * Q) f p~1 x)))).
475 destruct (f (CRstreams.iterate (X * Q) f p~1 x)).
476 simpl. rewrite Qplus_0_r. apply Qle_refl.
477 rewrite <- iterate_succ.
478 pose proof (Str_alt_neg (Pos.succ p) x H0 H1).
479 specialize (H0 (p~1)%positive) as [_ H0].
480 unfold Str_pth in H0.
481 exact H2.
482 + split.
483 rewrite <- Pos.add_1_r.
484 rewrite SumStream_assoc, iterate_one.
485 rewrite <- (Qplus_0_r 0).
486 apply Qplus_le_compat.
487 exact (AltSeries_small_pos_even _ x H0 H1).
488 apply (Qle_trans _ (snd (f (CRstreams.iterate (X * Q) f p~0 x)))).
489 rewrite <- iterate_succ, <- Pos.xI_succ_xO.
490 exact (Str_alt_pos _ x H0 H1).
491 unfold fst.
492 destruct (f (CRstreams.iterate (X * Q) f p~0 x)).
493 simpl. rewrite Qplus_0_r. apply Qle_refl.
494 rewrite <- Pos.add_1_l, SumStream_assoc, iterate_one.
495 simpl (fst (x,0)).
496 rewrite <- (Qplus_0_r (snd (f x))).
497 setoid_replace (snd (let (z, r0) := f x in (z, r0, r0 + snd (x, 0))))
498 with (snd (f x))
499 by (destruct (f x); apply Qplus_0_r).
500 apply Qplus_le_r.
501 apply AltSeries_small_neg_even.
502 apply (Str_alt_decr_tl x _ H0).
503 rewrite <- iterate_succ.
504 apply (Str_alt_neg _ x H0 H1).
505 + pose proof (Str_alt_neg 1 x H0 H1) as sndNeg.
506 unfold Str_pth in sndNeg. simpl in sndNeg.
507 specialize (H0 xH).
508 unfold Str_pth in H0. simpl in H0.
509 simpl. destruct (f x). simpl. simpl in H0.
510 unfold snd in H1.
511 destruct (f (x0,q)). simpl. simpl in H0.
512 rewrite Qplus_0_r.
513 destruct H0. rewrite (Qabs_pos q) in H0.
514 2: exact H1. unfold snd in sndNeg.
515 split.
516 rewrite Qabs_neg in H0. 2: exact sndNeg.
517 rewrite Qle_minus_iff, Qopp_involutive, Qplus_comm in H0.
518 exact H0.
519 apply (Qle_trans _ (0 + q)).
520 apply Qplus_le_l. exact sndNeg.
521 rewrite Qplus_0_l. apply Qle_refl.
522 Qed.
523
524 Lemma AltSeries_small : forall x (p : positive),
525 Str_alt_decr x ->
526 Qabs (snd
527 (CRstreams.iterate (X * Q * Q)
528 (fun y : X * Q * Q => let (z, r0) := f (fst y) in (z, r0, r0 + snd y))
529 p (x, 0))) <= Qabs (snd (f x)).
530 Proof.
531 intros. destruct (Qlt_le_dec (snd (f x)) 0).
532 - apply (Pos.peano_case (fun p => Qabs (snd
533 (CRstreams.iterate (X * Q * Q)
534 (fun y : X * Q * Q => let (z, r0) := f (fst y) in (z, r0, r0 + snd y)) p
535 (x, 0))) <= Qabs (snd (f x)))).
536 + simpl. destruct (f x). unfold snd.
537 rewrite Qplus_0_r. apply Qle_refl.
538 + assert (0 <= snd (f (f x))) as sndPos.
539 { specialize (H xH) as [_ H].
540 unfold Str_pth in H. simpl in H.
541 rewrite <- (Qmult_0_l (-snd (f x))) in H.
542 setoid_replace (snd (f (f x)) * snd (f x))%Q
543 with (-snd (f (f x)) * -snd (f x))%Q in H.
544 apply Qmult_le_r in H. apply (Qopp_le_compat _ 0) in H.
545 rewrite Qopp_involutive in H. exact H.
546 apply (Qplus_lt_l _ _ (snd (f x))).
547 ring_simplify. exact q.
548 unfold equiv, Q_eq. simpl. ring. }
549 intro n. rewrite <- Pos.add_1_l, SumStream_assoc, iterate_one.
550 setoid_replace (snd (let (z, r0) := f (fst (x, 0)) in (z, r0, r0 + snd (x, 0))))
551 with (snd (f x))
552 by (simpl; destruct (f x); apply Qplus_0_r).
553 rewrite Qabs_neg, Qabs_neg.
554 apply Qopp_le_compat.
555 rewrite <- (Qplus_0_r (snd (f x))) at 1.
556 apply Qplus_le_r.
557 apply AltSeries_small_pos.
558 exact (Str_alt_decr_tl x _ H).
559 exact sndPos.
560 apply Qlt_le_weak, q.
561 apply (Qle_trans _ (snd (f x) + snd (f (f x)))).
562 apply Qplus_le_r.
563 apply AltSeries_small_pos.
564 exact (Str_alt_decr_tl x 1 H).
565 exact sndPos.
566 specialize (H xH) as [H _].
567 unfold Str_pth in H. simpl in H.
568 rewrite (Qabs_pos _ sndPos) in H.
569 rewrite Qabs_neg in H.
570 apply (Qplus_le_r _ _ (snd (f x))) in H.
571 rewrite Qplus_opp_r in H. exact H.
572 apply Qlt_le_weak, q.
573 - pose proof (AltSeries_small_pos x p H q).
574 rewrite (Qabs_pos (snd (f x)) q).
575 rewrite Qabs_pos. apply H0. apply H0.
576 Qed.
577
578 Lemma AltSeries_further : forall x (p q : positive) (d1 d2 ε1 ε2 : Qpos),
579 Str_alt_decr x
580 -> Qabs (Str_pth p x) <= proj1_sig ε1
581 -> Qabs (Str_pth q x) <= proj1_sig ε2
582 -> proj1_sig d1 <= proj1_sig ε1
583 -> proj1_sig d2 <= proj1_sig ε2
584 -> Qball (proj1_sig ε1 + proj1_sig ε2) (SumStream x p d1) (SumStream x q d2).
585 Proof.
586 (* Because the stopping conditions are satisfied at p and q,
587 those positive bounds are useless and the sums will stop at
588 prior indices where the terms are less than ε1 and ε2. *)
589 intros.
590 unfold SumStream.
591 (* Replace p by its stopping index r. *)
592 pose proof (iterate_stop_correct
593 _
594 (fun y : X * Q * Q => let (z, r) := f (fst y) in (z, r, Qred (r + snd y)))
595 (fun y : X * Q * Q => Qle_bool (Qabs (snd (fst y))) (` d1))
596 p (x,0)) as [r [req [_ H4]]].
597 rewrite req. clear req.
598 assert (Qabs (Str_pth r x) <= proj1_sig ε1) as rstop.
599 { destruct H4. rewrite <- H4. exact H0.
600 destruct H4.
601 rewrite SumStream_fst_red in H5.
602 unfold fst in H5.
603 apply Qle_bool_iff in H5.
604 exact (Qle_trans _ _ _ H5 H2). }
605 clear H4 H2 d1 H0 p.
606 rewrite SumStream_red.
607 (* Replace q by its stopping index s. *)
608 pose proof (iterate_stop_correct
609 _
610 (fun y : X * Q * Q => let (z, r) := f (fst y) in (z, r, Qred (r + snd y)))
611 (fun y : X * Q * Q => Qle_bool (Qabs (snd (fst y))) (` d2))
612 q (x,0)) as [s [seq [_ H2]]].
613 rewrite seq. clear seq.
614 assert (Qabs (Str_pth s x) <= proj1_sig ε2) as sstop.
615 { destruct H2. rewrite <- H0. exact H1.
616 destruct H0.
617 rewrite SumStream_fst_red in H2.
618 unfold fst in H2.
619 apply Qle_bool_iff in H2.
620 exact (Qle_trans _ _ _ H2 H3). }
621 clear H2 H3 d2 H1 q.
622 rewrite SumStream_red.
623 destruct (Pos.lt_total r s).
624 - (* r < s *)
625 unfold Qball.
626 rewrite <- (Pplus_minus s r).
627 2: apply Pos.lt_gt, H0.
628 apply AbsSmall_Qabs.
629 rewrite (SumStream_assoc x r (s-r)).
630 unfold Qminus.
631 assert (forall a b : Q, -(a+b) == -a+-b).
632 { intros. ring. }
633 rewrite H1, Qplus_assoc, Qplus_opp_r, Qplus_0_l.
634 clear H1. rewrite Qabs_opp.
635 refine (Qle_trans _ _ _ (AltSeries_small _ _ _) _).
636 apply Str_alt_decr_tl, H.
637 rewrite <- iterate_succ.
638 destruct (H r).
639 apply (Qle_trans _ _ _ H1).
640 apply (Qle_trans _ (` ε1 + 0)).
641 rewrite Qplus_0_r. exact rstop.
642 apply Qplus_le_r, Qpos_nonneg.
643 - destruct H0. rewrite H0. apply ball_refl, (Qpos_nonneg (ε1 + ε2)).
644 (* Now s < r. *)
645 unfold Qball.
646 rewrite <- (Pplus_minus r s).
647 2: apply Pos.lt_gt, H0.
648 apply AbsSmall_Qabs.
649 rewrite (SumStream_assoc x s (r-s)).
650 rewrite Qplus_comm.
651 unfold Qminus.
652 rewrite <- Qplus_assoc, Qplus_opp_r, Qplus_0_r.
653 refine (Qle_trans _ _ _ (AltSeries_small _ _ _) _).
654 apply Str_alt_decr_tl, H.
655 rewrite <- iterate_succ.
656 destruct (H s).
657 apply (Qle_trans _ _ _ H1).
658 apply (Qle_trans _ (0 + ` ε2)).
659 rewrite Qplus_0_l. exact sstop.
660 apply Qplus_le_l, Qpos_nonneg.
661 Qed.
662
663 Lemma AltSeries_raw_prf : forall x cvmod,
664 Str_alt_decr x -> Limit_zero x cvmod ->
665 is_RegularFunction Qball (AltSeries_raw x cvmod).
666 Proof.
667 intros x cvmod decr lz ε1 ε2.
668 apply AltSeries_further. exact decr.
669 apply lz. apply lz. apply Qle_refl. apply Qle_refl.
670 Qed.
671
672 Definition AltSeries (x:X*Q) cvmod (decr : Str_alt_decr x) lz : CR
673 := Build_RegularFunction (AltSeries_raw_prf x cvmod decr lz).
674
675 Lemma SumStream_shift : forall p x e,
676 ` e < Qabs (snd (f x))
677 -> snd (f x) + SumStream (f x) p e == SumStream x (Pos.succ p) e.
678 Proof.
679 intros. unfold SumStream.
680 pose proof (iterate_stop_correct
681 _
682 (fun y : X * Q * Q => let (z, r) := f (fst y) in (z, r, Qred (r + snd y)))
683 (fun y : X * Q * Q => Qle_bool (Qabs (snd (fst y))) (` e))
684 p (f x,0)) as [s [seq [H0 H1]]].
685 rewrite seq, SumStream_red.
686 pose proof (SumStream_assoc x 1 s) as H2.
687 rewrite iterate_one, iterate_one in H2.
688 setoid_replace (snd (f x))
689 with (snd (let (z, r0) := f (fst (x, 0)) in (z, r0, r0 + snd (x, 0))))
690 by (simpl; destruct (f x); simpl; rewrite Qplus_0_r; reflexivity).
691 rewrite <- H2. clear H2.
692 rewrite Pos.add_1_l.
693 pose proof (iterate_stop_correct
694 _
695 (fun y : X * Q * Q => let (z, r) := f (fst y) in (z, r, Qred (r + snd y)))
696 (fun y : X * Q * Q => Qle_bool (Qabs (snd (fst y))) (` e))
697 (Pos.succ p) (x,0)) as [r [req [H2 H3]]].
698 rewrite req, SumStream_red.
699 clear req seq.
700 assert (r ≢ 1%positive) as rone.
701 { intro abs. clear H2 H0 H1. subst r.
702 destruct H3.
703 pose proof (Pos.lt_1_succ p).
704 rewrite H0 in H1. inversion H1. destruct H0.
705 rewrite SumStream_fst_red in H1.
706 simpl in H1. apply Qle_bool_iff in H1.
707 exact (Qlt_not_le _ _ H H1). }
708 destruct H1 as [finish|stop].
709 - subst s. destruct H3. subst r. reflexivity.
710 exfalso. destruct H1.
711 apply Qle_bool_iff in H3. (* 1 < r by hypothesis. *)
712 rewrite SumStream_fst_red in H3.
713 unfold fst in H3.
714 rewrite <- (Pos.succ_pred r) in H1. 2: exact rone.
715 apply Pos.succ_lt_mono in H1.
716 specialize (H0 (Pos.pred r) H1).
717 rewrite SumStream_fst_red in H0.
718 unfold fst in H0.
719 rewrite <- iterate_shift, <- iterate_succ, Pos.succ_pred in H0.
720 apply Qle_bool_iff in H3.
721 rewrite H0 in H3. discriminate. exact rone.
722 - destruct stop.
723 rewrite SumStream_fst_red in H4. unfold fst in H4.
724 rewrite <- iterate_shift, <- iterate_succ in H4.
725 destruct H3. exfalso. subst r.
726 apply Pos.succ_lt_mono in H1.
727 specialize (H2 (Pos.succ s) H1).
728 rewrite SumStream_fst_red in H2.
729 unfold fst in H2.
730 rewrite H4 in H2. discriminate.
731 destruct (Pos.lt_total r (Pos.succ s)).
732 exfalso.
733 destruct H3.
734 rewrite SumStream_fst_red in H6. unfold fst in H6.
735 rewrite <- (Pos.succ_pred r) in H5. 2: exact rone.
736 apply Pos.succ_lt_mono in H5.
737 specialize (H0 _ H5).
738 rewrite SumStream_fst_red in H0.
739 unfold fst in H0.
740 rewrite <- iterate_shift, <- iterate_succ, Pos.succ_pred in H0.
741 rewrite H0 in H6. discriminate. exact rone.
742 destruct H5.
743 rewrite H5. reflexivity. exfalso.
744 specialize (H2 (Pos.succ s) H5).
745 rewrite SumStream_fst_red in H2.
746 unfold fst in H2. rewrite H4 in H2. discriminate.
747 Qed.
748
749 (* AltSeries makes an infinite sum in the real numbers. *)
750 Lemma AltSeries_shift : forall x cvmod decr lz,
751 (AltSeries x cvmod decr lz
752 == '(snd (f x))
753 + AltSeries (f x) _ (Str_alt_decr_tl x 1 decr)
754 (Limit_zero_tl x cvmod 1 decr lz))%CR.
755 Proof.
756 intros.
757 rewrite -> CRplus_translate.
758 apply regFunEq_equiv, regFunEq_e.
759 intros e.
760 simpl.
761 rewrite <- Pos.pred_sub.
762 destruct (Qlt_le_dec (proj1_sig e) (Qabs (snd (f x)))).
763 - (* The sum recombines after f x. *)
764 rewrite SumStream_shift. 2: exact q.
765 specialize (lz e). revert lz.
766 generalize (cvmod e).
767 apply (Pos.peano_case (fun p => Qabs (Str_pth p x) <= ` e
768 → Qball (` e + ` e) (SumStream x p e) (SumStream x (Pos.succ (Pos.pred p)) e))).
769 + intros. exfalso. unfold Str_pth in H.
770 simpl in H. exact (Qlt_not_le _ _ q H).
771 + intros. rewrite Pos.pred_succ. apply ball_refl.
772 apply (Qpos_nonneg (e+e)).
773 - (* The sum stops at f x. *)
774 unfold SumStream.
775 rewrite (iterate_stop_indep _ _ _ (cvmod e) 1).
776 rewrite (iterate_stop_indep _ _ _ (Pos.pred (cvmod e)) 1).
777 + rewrite iterate_stop_one, iterate_stop_one.
778 unfold fst.
779 setoid_replace (snd (let (z, r) := f x in (z, r, Qred (r + snd (x, 0)))))
780 with (snd (f x))
781 by (destruct (f x); unfold snd; rewrite Qred_correct; apply Qplus_0_r).
782 setoid_replace (snd (let (z, r) := f (f x) in (z, r, Qred (r + snd (x, 0)))))
783 with (snd (f (f x)))
784 by (destruct (f (f x)); unfold snd; rewrite Qred_correct; apply Qplus_0_r).
785 apply AbsSmall_Qabs.
786 rewrite Qabs_Qminus. unfold Qminus.
787 rewrite (Qplus_comm (snd (f x))), <- Qplus_assoc.
788 rewrite Qplus_opp_r, Qplus_0_r.
789 specialize (decr xH) as [decr _].
790 apply (Qle_trans _ _ _ decr).
791 apply (Qle_trans _ (proj1_sig e + 0)).
792 rewrite Qplus_0_r. exact q.
793 apply Qplus_le_r, Qpos_nonneg.
794 + rewrite SumStream_fst_red. unfold fst.
795 apply Qle_bool_iff.
796 rewrite <- iterate_shift, <- iterate_succ.
797 specialize (lz e). revert lz.
798 generalize (cvmod e).
799 apply (Pos.peano_case (fun p => Qabs (Str_pth p x) <= ` e
800 → Qabs (snd (CRstreams.iterate (X * Q) f (Pos.succ (Pos.pred p)) x)) <= ` e)).
801 intros _.
802 simpl. specialize (decr xH) as [decr _].
803 unfold Str_pth in decr. simpl in decr.
804 apply (Qle_trans _ _ _ decr q).
805 intros. rewrite Pos.pred_succ. apply H.
806 + rewrite SumStream_fst_red. unfold fst.
807 simpl. apply Qle_bool_iff.
808 specialize (decr xH) as [decr _].
809 apply (Qle_trans _ _ _ decr).
810 exact q.
811 + rewrite SumStream_fst_red. unfold fst.
812 apply Qle_bool_iff. apply lz.
813 + rewrite SumStream_fst_red. unfold fst.
814 apply Qle_bool_iff. exact q.
815 Qed.
816
817 End RationalStreamSum.
818
819 Lemma Str_alt_decr_pos
820 : forall (X:Type) (f : X*Q->X*Q) x
821 (fdecr : Str_alt_decr X f x) (n:nat),
822 0 <= Str_pth _ f 1 x ->
823 0 <= (-1)^Z.of_nat n * Str_pth X f (Pos.of_nat (S n)) x.
824 Proof.
825 intros X f x fdecr.
826 induction n.
827 - intros. simpl. rewrite Qmult_1_l. exact H.
828 - intro H. specialize (IHn H).
829 specialize (fdecr (Pos.of_nat (S n))).
830 rewrite Nat2Pos.inj_succ. 2: discriminate.
831 destruct (Str_pth X f (Pos.of_nat (S n)) x) as [p q].
832 destruct p as [|p|p].
833 + destruct fdecr.
834 setoid_replace (Qabs (0#q)) with 0%Q in H0 by reflexivity.
835 apply Qabs_Qle_condition in H0. change (-0) with 0 in H0.
836 setoid_replace (Str_pth X f (Pos.succ (Pos.of_nat (S n))) x) with 0%Q.
837 rewrite Qmult_0_r. apply Qle_refl.
838 apply Qle_antisym; apply H0.
839 + destruct fdecr. clear H0.
840 rewrite <- (Qmult_0_l (Z.pos p # q)) in H1.
841 rewrite Qmult_le_r in H1. 2: reflexivity.
842 rewrite <- (Qmult_0_l (Z.pos p # q)) in IHn.
843 rewrite Qmult_le_r in IHn. 2: reflexivity.
844 change (S n) with (1+n)%nat.
845 rewrite (Nat2Z.inj_add 1 n).
846 rewrite Qpower_plus. simpl ((-1)^Z.of_nat 1). rewrite (Qmult_comm (-1)).
847 rewrite <- Qmult_assoc.
848 rewrite Qmult_comm, <- (Qmult_0_l ((-1)^Z.of_nat n)).
849 apply Qmult_le_compat_r. 2: exact IHn.
850 change (S n) with (1+n)%nat in H1.
851 destruct (Str_pth X f (Pos.succ (Pos.of_nat (1+ n))) x).
852 destruct Qnum. apply Z.le_refl.
853 unfold Qle, Z.le in H1. simpl in H1.
854 exfalso; apply H1; reflexivity.
855 discriminate. intro abs. discriminate.
856 + destruct fdecr. clear H0.
857 assert ((Z.neg p # q) == (-1) * (Z.pos p#q)) by reflexivity.
858 rewrite H0, Qmult_assoc in H1. rewrite H0, Qmult_assoc in IHn.
859 rewrite <- (Qmult_0_l (Z.pos p # q)) in H1.
860 rewrite Qmult_le_r in H1. 2: reflexivity.
861 rewrite <- (Qmult_0_l (Z.pos p # q)) in IHn.
862 rewrite Qmult_le_r in IHn. 2: reflexivity.
863 change (S n) with (1+n)%nat.
864 rewrite (Nat2Z.inj_add 1 n).
865 rewrite Qpower_plus. simpl ((-1)^Z.of_nat 1%nat). rewrite (Qmult_comm (-1)).
866 rewrite (Qmult_comm ((-1) ^ Z.of_nat n * -1)).
867 rewrite <- (Qmult_0_l ((-1) ^ Z.of_nat n * -1)).
868 apply Qmult_le_compat_r. 2: exact IHn.
869 change (S n) with (1+n)%nat in H1.
870 destruct (Str_pth X f (Pos.succ (Pos.of_nat (1+ n))) x).
871 destruct Qnum. apply Z.le_refl. discriminate.
872 unfold Qle, Z.le in H1. simpl in H1.
873 exfalso; apply H1; reflexivity.
874 discriminate.
875 Qed.
876
877 Lemma CRstream_opp_decr : forall (X:Type) (f : X*Q->X*Q) x,
878 Str_alt_decr X f x
879 -> Str_alt_decr X (CRstreams.CRstream_opp X f) (let (y, r) := x in (y, - r)).
880 Proof.
881 intros X f x H p. specialize (H p).
882 pose proof (CRstreams.CRstream_opp_pth X f x p).
883 pose proof (CRstreams.CRstream_opp_pth X f x (Pos.succ p)).
884 unfold Str_pth. unfold Str_pth in H.
885 destruct x as [x q].
886 unfold negate, Q_opp.
887 destruct (CRstreams.iterate _ f p (x,q)).
888 destruct (CRstreams.iterate _ f (Pos.succ p) (x,q)).
889 unfold snd in H.
890 destruct (CRstreams.iterate _ (CRstreams.CRstream_opp X f)
891 (Pos.succ p) (x, (-q)%Q)).
892 destruct (CRstreams.iterate _ (CRstreams.CRstream_opp X f) p (x, (-q)%Q)).
893 unfold snd.
894 destruct H1. subst q2. subst x2.
895 destruct H0. subst q3. subst x3.
896 destruct H. split.
897 - rewrite Qabs_opp, Qabs_opp. exact H.
898 - setoid_replace (- q1 * - q0)%Q with (q1*q0)%Q.
899 exact H0. unfold equiv, Q_eq. ring.
900 Qed.
901
902 Lemma CRstream_opp_limit_zero : forall (X:Type) (f : X*Q->X*Q) x cvmod,
903 Limit_zero X f x cvmod
904 -> Limit_zero X (CRstreams.CRstream_opp X f) (let (y, r) := x in (y, - r)) cvmod.
905 Proof.
906 intros. intro e.
907 specialize (H e).
908 pose proof (CRstreams.CRstream_opp_pth X f x (cvmod e)).
909 unfold Str_pth. unfold Str_pth in H.
910 destruct (CRstreams.iterate (X * Q) f (cvmod e) x) as [y r].
911 destruct x as [x q].
912 unfold negate, Q_opp.
913 destruct (CRstreams.iterate (X * Q) (CRstream_opp X f) (cvmod e) (x, (- q)%Q)).
914 unfold snd. unfold snd in H. destruct H0.
915 subst q0. rewrite Qabs_opp. exact H.
916 Qed.
917
918 Lemma SumStream_wd : forall (p:positive)
919 (X Y:Type) (f : X*Q -> X*Q) (g : Y*Q -> Y*Q)
920 (x : X*Q) (y : Y*Q),
921 (forall p:positive, Str_pth _ f p x == Str_pth _ g p y)
922 -> snd (CRstreams.iterate _
923 (fun y : X * Q * Q => let (z0, r1) := f (fst y) in (z0, r1, r1 + snd y)) p
924 (x,0))
925 == snd (CRstreams.iterate _
926 (fun y : Y * Q * Q => let (z0, r1) := g (fst y) in (z0, r1, r1 + snd y)) p
927 (y,0)).
928 Proof.
929 apply (Pos.peano_ind (fun p => forall (X Y:Type) (f : X*Q -> X*Q) (g : Y*Q -> Y*Q)
930 (x : X*Q) (y : Y*Q),
931 (forall p:positive, Str_pth _ f p x == Str_pth _ g p y)
932 -> snd (CRstreams.iterate _
933 (fun y : X * Q * Q => let (z0, r1) := f (fst y) in (z0, r1, r1 + snd y)) p
934 (x,0))
935 == snd (CRstreams.iterate _
936 (fun y : Y * Q * Q => let (z0, r1) := g (fst y) in (z0, r1, r1 + snd y)) p
937 (y,0)))).
938 - intros. simpl. specialize (H xH).
939 unfold Str_pth in H. simpl in H.
940 destruct (f x), (g y). simpl. simpl in H.
941 rewrite H. reflexivity.
942 - intros.
943 pose proof (H0 (Pos.succ p)).
944 unfold Str_pth in H1.
945 rewrite iterate_succ, iterate_succ in H1.
946 rewrite iterate_succ, iterate_succ, SumStream_fst, SumStream_fst.
947 unfold fst.
948 destruct (f (CRstreams.iterate (X * Q) f p x)).
949 unfold snd at 1.
950 destruct (g (CRstreams.iterate (Y * Q) g p y)).
951 unfold snd at 3.
952 specialize (H X Y f g x y H0).
953 rewrite H. simpl in H1.
954 rewrite H1. reflexivity.
955 Qed.
956
957 Lemma AltSeries_wd : forall (X Y:Type) (f : X*Q -> X*Q) (g : Y*Q -> Y*Q)
958 (x : X*Q) (y : Y*Q) cvmod ccvmod
959 (fdecr : Str_alt_decr X f x) (gdecr : Str_alt_decr Y g y)
960 (flz : Limit_zero X f x cvmod) (glz : Limit_zero Y g y ccvmod),
961 (forall p:positive, Str_pth _ f p x == Str_pth _ g p y)
962 -> (forall e, cvmod e ≡ ccvmod e)
963 -> (AltSeries X f x cvmod fdecr flz
964 == AltSeries Y g y ccvmod gdecr glz)%CR.
965 Proof.
966 intros.
967 apply regFunEq_equiv, regFunEq_e. intros e.
968 simpl.
969 setoid_replace (SumStream X f x (cvmod e) e)
970 with (SumStream Y g y (cvmod e) e).
971 rewrite H0.
972 apply ball_refl. apply (Qpos_nonneg (e+e)).
973 unfold SumStream.
974 destruct (iterate_stop_correct
975 _
976 (fun y0 : X * Q * Q => let (z, r) := f (fst y0) in (z, r, Qred (r + snd y0)))
977 (fun y0 : X * Q * Q => Qle_bool (Qabs (snd (fst y0))) (` e))
978 (cvmod e) (x,0)) as [q [qeq [H1 H2]]].
979 rewrite qeq, SumStream_red. clear qeq.
980 destruct (iterate_stop_correct
981 _
982 (fun y0 : Y * Q * Q => let (z, r) := g (fst y0) in (z, r, Qred (r + snd y0)))
983 (fun y0 : Y * Q * Q => Qle_bool (Qabs (snd (fst y0))) (` e))
984 (cvmod e) (y,0)) as [r [req [H3 H4]]].
985 rewrite req, SumStream_red. clear req.
986 destruct H4 as [fuel|predicate].
987 - subst r. destruct H2.
988 + subst q. apply (SumStream_wd _ _ _ _ _ _ _ H).
989 + exfalso. destruct H2.
990 specialize (H3 q H2).
991 rewrite SumStream_fst_red in H3.
992 unfold fst in H3.
993 rewrite SumStream_fst_red in H4.
994 unfold fst in H4.
995 specialize (H q). unfold Str_pth in H.
996 rewrite H in H4.
997 rewrite H4 in H3. discriminate.
998 - destruct predicate.
999 rewrite SumStream_fst_red in H5.
1000 unfold fst in H5.
1001 destruct H2.
1002 + exfalso. subst q.
1003 specialize (H1 r H4).
1004 rewrite SumStream_fst_red in H1.
1005 unfold fst in H1.
1006 specialize (H r). unfold Str_pth in H.
1007 rewrite <- H in H5.
1008 rewrite H5 in H1. discriminate.
1009 + destruct H2.
1010 rewrite SumStream_fst_red in H6. unfold fst in H6.
1011 destruct (Pos.lt_total q r).
1012 exfalso. specialize (H3 q H7).
1013 rewrite SumStream_fst_red in H3; unfold fst in H3.
1014 specialize (H q). unfold Str_pth in H.
1015 rewrite H in H6. rewrite H6 in H3. discriminate.
1016 destruct H7. rewrite H7.
1017 exact (SumStream_wd _ _ _ _ _ _ _ H).
1018 exfalso. specialize (H1 r H7).
1019 rewrite SumStream_fst_red in H1; unfold fst in H1.
1020 specialize (H r). unfold Str_pth in H.
1021 rewrite H in H1. rewrite H1 in H5. discriminate.
1022 Qed.
1023
1024 Lemma sym_sub_add_distr (p q r:positive) : (p-(q+r) ≡ p-q-r)%positive.
1025 Proof.
1026 destruct (Pos.lt_total (q+r) p).
1027 - apply Pos.sub_add_distr, H.
1028 - destruct H. subst p.
1029 rewrite Pos.sub_diag.
1030 rewrite Pos.add_comm, Pos.add_sub.
1031 rewrite Pos.sub_diag. reflexivity.
1032 rewrite Pos.sub_lt. 2: exact H.
1033 rewrite Pos.sub_le. reflexivity.
1034 destruct (Pos.lt_total p q).
1035 + rewrite Pos.sub_lt. apply Pos.le_1_l. exact H0.
1036 + destruct H0. subst q. rewrite Pos.sub_diag. apply Pos.le_1_l.
1037 change (Zpos (p-q) <= Zpos r)%Z.
1038 rewrite Pos2Z.inj_sub. 2: exact H0.
1039 apply (Z.add_le_mono_r _ _ (Zpos q)).
1040 ring_simplify.
1041 rewrite <- Pos2Z.inj_add.
1042 apply Z.lt_le_incl, H.
1043 Qed.
1044
1045 Lemma AltSeries_shift_pth : forall (p:positive) (X : Type) f x cvmod decr lz,
1046 (AltSeries X f x cvmod decr lz
1047 == inject_Q_CR (snd (CRstreams.iterate _
1048 (fun y : (X * Q) * Q =>
1049 let (z0, r1) := f (fst y) in (z0, r1, Qred (r1 + snd y)))
1050 p (x, 0%Q)))
1051 + AltSeries X f (CRstreams.iterate _ f p x)
1052 _ (Str_alt_decr_tl X f x p decr)
1053 (Limit_zero_tl X f x cvmod p decr lz))%CR.
1054 Proof.
1055 apply (Pos.peano_ind (fun p => forall X f x cvmod decr lz,
1056 (AltSeries X f x cvmod decr lz
1057 == inject_Q_CR (snd (CRstreams.iterate _
1058 (fun y : (X * Q) * Q =>
1059 let (z0, r1) := f (fst y) in (z0, r1, Qred (r1 + snd y)))
1060 p (x, 0%Q)))
1061 + AltSeries X f _ _ (Str_alt_decr_tl X f x p decr)
1062 (Limit_zero_tl X f x cvmod p decr lz))%CR)).
1063 - intros. rewrite AltSeries_shift.
1064 apply CRplus_eq_l. rewrite SumStream_red.
1065 rewrite iterate_one. simpl.
1066 destruct (f x). simpl. rewrite Qplus_0_r. reflexivity.
1067 - intros.
1068 setoid_replace (AltSeries X f (CRstreams.iterate (X * Q) f (Pos.succ p) x)
1069 (fun e : Qpos => (cvmod e - Pos.succ p)%positive)
1070 (Str_alt_decr_tl X f x (Pos.succ p) decr)
1071 (Limit_zero_tl X f x cvmod (Pos.succ p) decr lz))
1072 with (AltSeries X f (CRstreams.iterate (X * Q) f p (f x))
1073 _
1074 (Str_alt_decr_tl X f (f x) p (Str_alt_decr_tl X f x 1 decr))
1075 (Limit_zero_tl X f (f x) _ p (Str_alt_decr_tl X f x 1 decr)
1076 (Limit_zero_tl X f x _ 1 decr lz))).
1077 + setoid_replace (inject_Q_CR (snd
1078 (CRstreams.iterate (X * Q * Q)
1079 (fun y : X * Q * Q => let (z0, r1) := f (fst y) in (z0, r1, Qred (r1 + snd y)))
1080 (Pos.succ p) (x, 0))))
1081 with (inject_Q_CR (snd (f x)) + inject_Q_CR (snd
1082 (CRstreams.iterate (X * Q * Q)
1083 (fun y : X * Q * Q =>
1084 let (z0, r1) := f (fst y) in (z0, r1, Qred (r1 + snd y))) p
1085 (f x, 0%Q))))%CR.
1086 rewrite <- CRplus_assoc, <- (H X f (f x)).
1087 rewrite <- AltSeries_shift. reflexivity.
1088 clear H. rewrite SumStream_red, SumStream_red.
1089 rewrite iterate_succ. rewrite SumStream_fst.
1090 simpl.
1091 rewrite CRplus_Qplus.
1092 apply inject_Q_CR_wd.
1093 transitivity (snd (f (CRstreams.iterate (X * Q) f p x) )
1094 + snd (CRstreams.iterate (X * Q * Q)
1095 (fun y : X * Q * Q => let (z1, r0) := f (fst y) in (z1, r0, r0 + snd y)) p
1096 (x, 0))).
1097 destruct (f (CRstreams.iterate (X * Q) f p x)); reflexivity.
1098 pose proof (SumStream_assoc X f x 1 p).
1099 rewrite iterate_one, iterate_one in H.
1100 setoid_replace (snd (let (z, r0) := f (fst (x, 0)) in (z, r0, r0 + snd (x, 0)))%Q)
1101 with (snd (f x))%Q in H.
1102 rewrite <- H. clear H.
1103 rewrite Pos.add_1_l, iterate_succ, SumStream_fst.
1104 unfold fst.
1105 destruct (f (CRstreams.iterate (X * Q) f p x)). simpl.
1106 reflexivity.
1107 simpl. destruct (f x). simpl.
1108 rewrite Qplus_0_r. reflexivity.
1109 + apply AltSeries_wd.
1110 intros. rewrite iterate_succ, iterate_shift.
1111 reflexivity.
1112 intro e. rewrite <- Pos.add_1_l.
1113 rewrite sym_sub_add_distr. reflexivity.
1114 Qed.