Debian Codegraph @

reals/stdlib/ConstructiveDiagonal.v

raw
1 (*
2 Copyright © 2020 Vincent Semeria
3
4 Permission is hereby granted, free of charge, to any person obtaining a copy of this software and associated documentation files (the "Software"), to deal in the Software without restriction, including without limitation the rights to use, copy, modify, merge, publish, distribute, sublicense, and/or sell copies of the Software, and to permit persons to whom the Software is furnished to do so, subject to the following conditions:
5
6 The above copyright notice and this permission notice shall be included in all copies or substantial portions of the Software.
7
8 THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
9 *)
10
11
12 (* The diagonal bijection between nat^2 and nat, as well as convergence
13 results for double series. *)
14
15 From Coq Require Import ZArith.
16 From Coq Require Import QArith.
17 From Coq Require Import PeanoNat.
18 From Coq Require Import ArithRing.
19 From Coq Require Import ConstructiveReals.
20 From Coq Require Import ConstructiveAbs.
21 From Coq Require Import ConstructiveSum.
22 From Coq Require Import ConstructivePower.
23 From Coq Require Import ConstructiveLimits.
24
25 Local Open Scope ConstructiveReals.
26
27
28 (*********************************************************)
29 (** * Auxiliary lemmas *)
30 (*********************************************************)
31
32 (* Those lemmas should probably either be inlined,
33 or go in other libraries *)
34
35 Definition SubSeq : Type
36 := { sub : nat -> nat | forall n p:nat, lt n p -> lt (sub n) (sub p) }.
37
38 Lemma SubSeqAboveId : forall (un : SubSeq) (n : nat),
39 le n (proj1_sig un n).
40 Proof.
41 intros [un inc]. induction n. simpl. apply Nat.le_0_l.
42 simpl. simpl in IHn. specialize (inc n (S n)).
43 unfold lt in inc. apply (Nat.le_trans _ (S (un n))).
44 apply le_n_S. assumption. apply inc. apply Nat.le_refl.
45 Qed.
46
47 (* Inversion of a subsequence *)
48 Fixpoint SubSeqInv (un : SubSeq) (n p : nat) : nat
49 := if Nat.eq_dec (proj1_sig un p) n then p
50 else match p with
51 | O => S n (* not found *)
52 | S k => SubSeqInv un n k
53 end.
54
55 Lemma SubSeqInvFound : forall (un : SubSeq) (n k : nat),
56 (SubSeqInv un n k <= n <-> proj1_sig un (SubSeqInv un n k) = n)%nat.
57 Proof.
58 intros. generalize dependent n. induction k.
59 - simpl. split.
60 + intro. destruct (Nat.eq_dec (proj1_sig un O) n).
61 assumption. exfalso. apply (Nat.lt_nge n (S n)).
62 apply Nat.le_refl. assumption.
63 + intro. destruct (Nat.eq_dec (proj1_sig un O) n). apply Nat.le_0_l.
64 exfalso. pose proof (SubSeqAboveId un n).
65 destruct un. simpl in H. simpl in n0. simpl in H0.
66 apply (Nat.lt_nge (x n) (x (S n))). apply l. apply Nat.le_refl.
67 rewrite H. assumption.
68 - split.
69 + intro. simpl. simpl in H.
70 destruct (Nat.eq_dec (proj1_sig un (S k)) n). assumption.
71 apply IHk. assumption.
72 + simpl. intro. destruct (Nat.eq_dec (proj1_sig un (S k)) n).
73 rewrite <- e. apply SubSeqAboveId. apply IHk. assumption.
74 Qed.
75
76 Lemma SubSeqInvNotFound : forall (un : SubSeq) (n k : nat),
77 SubSeqInv un n k = S n
78 <-> (forall p:nat, le p k -> proj1_sig un p <> n).
79 Proof.
80 intros. generalize dependent n. induction k.
81 - split.
82 + intros. intro absurd. simpl in H. destruct (Nat.eq_dec (proj1_sig un O) n).
83 discriminate. destruct un. simpl in absurd. simpl in n0.
84 inversion H0. subst p. contradiction.
85 + intros. simpl. destruct (Nat.eq_dec (proj1_sig un O) n).
86 exfalso. exact (H O (Nat.le_refl 0) e). reflexivity.
87 - split.
88 + intros. intro absurd. simpl in H.
89 destruct (Nat.eq_dec (proj1_sig un (S k)) n).
90 inversion H. subst k. pose proof (SubSeqAboveId un (S n)).
91 rewrite e in H1. apply (Nat.lt_nge n (S n)). apply Nat.le_refl.
92 assumption. apply Nat.le_succ_r in H0. destruct H0.
93 specialize (IHk n) as [IHk _].
94 specialize (IHk H p H0). contradiction. subst p. contradiction.
95 + intros. simpl. destruct (Nat.eq_dec (proj1_sig un (S k)) n).
96 exfalso. specialize (H (S k) (Nat.le_refl _)). contradiction.
97 apply IHk. intros. apply H. apply (Nat.le_trans _ k). assumption.
98 apply le_S. apply Nat.le_refl.
99 Qed.
100
101 Lemma SubSeqInvInit : forall (un : SubSeq) (n : nat),
102 SubSeqInv un (proj1_sig un O) n = O.
103 Proof.
104 induction n.
105 - simpl. destruct (Nat.eq_dec (proj1_sig un O) (proj1_sig un O)). reflexivity.
106 exfalso. exact (n (eq_refl _)).
107 - simpl. destruct (Nat.eq_dec (proj1_sig un (S n)) (proj1_sig un O)).
108 exfalso. destruct un. simpl in e. apply (Nat.lt_nge (x O) (x (S n))).
109 apply l. apply le_n_S. apply Nat.le_0_l. rewrite e. apply Nat.le_refl.
110 apply IHn.
111 Qed.
112
113 (* Realign the indexes, filling with zeros *)
114 Definition FillSubSeqWithZeros {R : ConstructiveReals}
115 (un : nat -> CRcarrier R) (sub : SubSeq) (n : nat) : CRcarrier R
116 := if Nat.eq_dec (SubSeqInv sub n n) (S n)
117 then 0 else un n.
118
119 Lemma sumLastElem : forall {R : ConstructiveReals} (un : nat -> CRcarrier R) (n : nat),
120 (forall k:nat, lt k n -> un k == 0)
121 -> CRsum un n == un n.
122 Proof.
123 intros. destruct n.
124 - reflexivity.
125 - simpl. rewrite <- (CRplus_0_l (un (S n))). apply CRplus_morph.
126 rewrite (CRsum_eq _ (fun n => 0)). rewrite sum_const.
127 rewrite CRmult_0_l. reflexivity.
128 intros. apply H. apply le_n_S. assumption. apply CRplus_0_l.
129 Qed.
130
131 Lemma FillSubSeqWithZerosInit
132 : forall {R : ConstructiveReals} (un : nat -> CRcarrier R) (sub : SubSeq),
133 CRsum (FillSubSeqWithZeros un sub) (proj1_sig sub O)
134 == un (proj1_sig sub O).
135 Proof.
136 intros R un sub.
137 replace (un (proj1_sig sub O))
138 with ((FillSubSeqWithZeros un sub) (proj1_sig sub O)).
139 - apply sumLastElem. intros. unfold FillSubSeqWithZeros.
140 destruct (Nat.eq_dec (SubSeqInv sub k k) (S k)). reflexivity.
141 exfalso. apply n. clear n. apply SubSeqInvNotFound. intros.
142 intro absurd. destruct p. rewrite absurd in H. exact (Nat.lt_irrefl k H).
143 destruct sub. simpl in absurd, H. apply (Nat.lt_nge (x O) (x (S p))).
144 apply l. apply le_n_S. apply Nat.le_0_l. rewrite absurd. apply le_S in H.
145 apply le_S_n in H. apply H.
146 - unfold FillSubSeqWithZeros.
147 destruct (Nat.eq_dec (SubSeqInv sub (proj1_sig sub O) (proj1_sig sub O)) (S (proj1_sig sub O))).
148 exfalso. pose proof (SubSeqInvNotFound sub (proj1_sig sub O) (proj1_sig sub O)) as [H _].
149 specialize (H e O (Nat.le_0_l _)). apply H. reflexivity. reflexivity.
150 Qed.
151
152 Lemma FillSubSeqWithZerosStep
153 : forall {R : ConstructiveReals} (un : nat -> CRcarrier R) (sub : SubSeq) (n : nat),
154 CRsum (fun k : nat => FillSubSeqWithZeros un sub (S (proj1_sig sub n) + k))
155 (proj1_sig sub (S n) - S (proj1_sig sub n))
156 == un (proj1_sig sub (S n)).
157 Proof.
158 intros.
159 replace (un (proj1_sig sub (S n)))
160 with (FillSubSeqWithZeros un sub (S (proj1_sig sub n)
161 + (proj1_sig sub (S n) - S (proj1_sig sub n)))).
162 - apply (sumLastElem (fun k : nat => FillSubSeqWithZeros un sub (S (proj1_sig sub n) + k))).
163 intros. unfold FillSubSeqWithZeros.
164 destruct (Nat.eq_dec (SubSeqInv sub (S (proj1_sig sub n) + k) (S (proj1_sig sub n) + k))).
165 reflexivity. exfalso. apply n0. clear n0. apply SubSeqInvNotFound. intros.
166 intro absurd. (* sub reaches a number between sub n and sub (S n) *)
167 destruct sub as [sub inc]. simpl in absurd, H0, H.
168 assert (sub p < sub (S n))%nat.
169 { rewrite absurd. apply (Nat.lt_le_trans _ (S (sub n)
170 + (sub (S n) - S (sub n)))).
171 simpl. apply le_n_S. apply Nat.add_lt_mono_l. assumption. rewrite Nat.add_comm.
172 rewrite Nat.sub_add. apply Nat.le_refl. apply inc. apply Nat.le_refl. }
173 destruct (Nat.lt_trichotomy p (S n)).
174 apply Nat.le_succ_r in H2. destruct H2.
175 specialize (inc p n H2). rewrite absurd in inc.
176 apply (Nat.lt_nge (S (sub n + k)) (sub n)). assumption.
177 apply le_S. rewrite <- (Nat.add_0_r (sub n)). rewrite <- Nat.add_assoc.
178 apply Nat.add_le_mono_l. apply Nat.le_0_l. inversion H2. subst p.
179 apply (Nat.lt_nge (sub n) (S (sub n + k))). apply le_n_S.
180 rewrite <- (Nat.add_0_r (sub n)). rewrite <- Nat.add_assoc.
181 apply Nat.add_le_mono_l. apply Nat.le_0_l. rewrite <- absurd. apply Nat.le_refl.
182 destruct H2. subst p. exact (Nat.lt_irrefl (sub (S n)) H1).
183 specialize (inc (S n) p H2). apply (Nat.lt_asymm (sub p) (sub (S n))); assumption.
184 - rewrite Nat.add_comm. rewrite Nat.sub_add.
185 unfold FillSubSeqWithZeros.
186 destruct (Nat.eq_dec (SubSeqInv sub (proj1_sig sub (S n)) (proj1_sig sub (S n))) (S (proj1_sig sub (S n)))).
187 exfalso. pose proof (SubSeqInvNotFound sub (proj1_sig sub (S n)) (proj1_sig sub (S n))) as [H _].
188 specialize (H e (S n) (SubSeqAboveId _ _)). apply H. reflexivity. reflexivity.
189 destruct sub. simpl. apply l. apply Nat.le_refl.
190 Qed.
191
192 (* The same modulus of convergence applies to any subsequence. *)
193 Lemma SubSeqCv : forall {R : ConstructiveReals} (un : nat -> CRcarrier R)
194 (sub : SubSeq) (l : CRcarrier R),
195 CR_cv R un l -> CR_cv R (fun n => un (proj1_sig sub n)) l.
196 Proof.
197 intros. intros p. specialize (H p) as [N cv].
198 exists N. intros. apply cv. apply (Nat.le_trans _ i).
199 assumption. apply SubSeqAboveId.
200 Qed.
201
202 Lemma SubSeriesCv : forall {R : ConstructiveReals} (un : nat -> CRcarrier R)
203 (sub : SubSeq) (s : CRcarrier R),
204 series_cv un s
205 -> (forall n:nat, 0 <= un n)
206 -> { t : CRcarrier R & series_cv (fun n => un (proj1_sig sub n)) t }.
207 Proof.
208 intros.
209 destruct (series_cv_maj (FillSubSeqWithZeros un sub)
210 un s) as [lim [cv _]].
211 - intro n. unfold FillSubSeqWithZeros.
212 destruct (Nat.eq_dec (SubSeqInv sub n n) (S n)).
213 rewrite CRabs_right. apply H0. apply CRle_refl.
214 rewrite CRabs_right. apply CRle_refl. apply H0.
215 - assumption.
216 - exists lim. apply (CR_cv_eq _ (fun n => CRsum (FillSubSeqWithZeros un sub) (proj1_sig sub n))).
217 induction n.
218 + apply FillSubSeqWithZerosInit.
219 + simpl. rewrite <- IHn. clear IHn.
220 destruct (Nat.le_exists_sub (S (proj1_sig sub n)) (proj1_sig sub (S n)))
221 as [p [inf _]].
222 destruct sub. simpl. apply l. apply le_n_S. apply Nat.le_refl.
223 rewrite inf. rewrite Nat.add_comm. rewrite sum_assoc.
224 apply CRplus_morph. reflexivity. rewrite Nat.add_comm. rewrite <- inf.
225 apply eq_sym in inf. apply Nat.add_sub_eq_r in inf.
226 subst p. apply FillSubSeqWithZerosStep.
227 + apply (SubSeqCv _ sub lim cv).
228 Qed.
229
230 (* The points (n,0) are mapped to 0, 1, 3, 6, 10, ... = n(n+1)/2 *)
231 Definition diagPlane (i j : nat) : nat
232 := j + (i+j) * S (i+j)/2.
233
234 Definition diagPlaneInvNext i j : prod nat nat
235 := match i with
236 | O => (* change diag *) pair (S j) O
237 | S k => pair k (S j)
238 end.
239
240 (* Apply n times function f starting at point i j. *)
241 Fixpoint iterateN2Func (n i j : nat) (f : nat -> nat -> prod nat nat)
242 := match n with
243 | O => pair i j
244 | S p => let (k,l) := iterateN2Func p i j f in f k l
245 end.
246
247 Definition diagPlaneInv (n : nat) : prod nat nat
248 := iterateN2Func n O O diagPlaneInvNext.
249
250 Lemma diagPlaneAbsNext : forall n : nat, (S n * (S (S n)) / 2 = n * S n / 2 + S n)%nat.
251 Proof.
252 intro n.
253 assert (S n * S (S n) = n * S n + S n * 2)%nat. ring.
254 rewrite H. rewrite Nat.div_add. ring.
255 intro absurd. inversion absurd.
256 Qed.
257
258 (* g (f ... f 0) = 1 + ... + 1 + g 0 *)
259 Lemma diagPlaneSurject : forall n : nat, let (i,j) := diagPlaneInv n in
260 diagPlane i j = n.
261 Proof.
262 assert (forall i j:nat, let (k, l) := diagPlaneInvNext i j in
263 diagPlane k l = S (diagPlane i j)).
264 { intros. destruct (diagPlaneInvNext i j) as [k l] eqn:des.
265 unfold diagPlane. unfold diagPlaneInvNext in des. destruct i.
266 - inversion des. subst l. subst k. clear des.
267 rewrite Nat.add_0_l. rewrite Nat.add_0_r. rewrite Nat.add_0_l.
268 rewrite diagPlaneAbsNext. ring.
269 - inversion des. subst l. subst k. clear des.
270 assert ((i + S j) = S i + j)%nat. ring. rewrite H.
271 assert (S j + (S i + j) * S (S i + j) / 2
272 = S (j + (S i + j) * S (S i + j) / 2))%nat. ring.
273 rewrite H0. reflexivity. }
274
275 induction n.
276 - reflexivity.
277 - unfold diagPlaneInv. simpl. unfold diagPlaneInv in IHn.
278 destruct (iterateN2Func n 0 0 diagPlaneInvNext) as [i j].
279 rewrite <- IHn. apply H.
280 Qed.
281
282 Lemma diagPlaneInjectBis : forall i j k l : nat,
283 diagPlane i j = diagPlane k l -> (i = k /\ j = l).
284 Proof.
285 intros. unfold diagPlane in H. remember (i + j)%nat as I. remember (k + l)%nat as K.
286 assert (I = K).
287 - destruct (Nat.lt_trichotomy I K).
288 + exfalso. unfold lt in H0. assert ((S I) * S (S I) / 2 <= K * S K / 2)%nat.
289 apply Nat.div_le_mono. intro absurd. inversion absurd.
290 apply Nat.mul_le_mono_nonneg. apply Nat.le_0_l. assumption. apply Nat.le_0_l.
291 apply le_n_S. assumption. rewrite diagPlaneAbsNext in H1.
292 apply (Nat.add_le_mono_l (I * S I / 2 + S I) (K * S K / 2) l) in H1.
293 rewrite <- H in H1. rewrite <- (Nat.add_comm (S I)) in H1.
294 rewrite Nat.add_assoc in H1. apply Nat.le_le_add_le in H1.
295 rewrite HeqI in H1. apply (Nat.nle_succ_diag_l j).
296 apply (Nat.le_trans (S j) (l + S (i + j))). rewrite <- (Nat.add_0_r (S j)).
297 assert (l + S (i + j) = S j + (l + i))%nat. ring. rewrite H2.
298 pose proof (Nat.add_le_mono_l). apply Nat.add_le_mono_l. apply Nat.le_0_l.
299 assumption. apply Nat.le_refl.
300 + destruct H0. assumption. exfalso.
301 unfold lt in H0. assert ((S K) * S (S K) / 2 <= I * S I / 2)%nat.
302 apply Nat.div_le_mono. intro absurd. inversion absurd.
303 apply Nat.mul_le_mono_nonneg. apply Nat.le_0_l. assumption. apply Nat.le_0_l.
304 apply le_n_S. assumption. rewrite diagPlaneAbsNext in H1.
305 apply (Nat.add_le_mono_l (K * S K / 2 + S K) (I * S I / 2) j) in H1.
306 rewrite H in H1. rewrite <- (Nat.add_comm (S K)) in H1.
307 rewrite Nat.add_assoc in H1. apply Nat.le_le_add_le in H1.
308 rewrite HeqK in H1. apply (Nat.nle_succ_diag_l l).
309 apply (Nat.le_trans (S l) (j + S (k + l))). rewrite <- (Nat.add_0_r (S l)).
310 assert (j + S (k + l) = S l + (j + k))%nat. ring. rewrite H2.
311 pose proof Nat.add_le_mono_l. apply Nat.add_le_mono_l. apply Nat.le_0_l.
312 assumption. apply Nat.le_refl.
313 - rewrite <- H0 in H. apply Nat.add_cancel_r in H. subst l. subst K.
314 rewrite H0 in HeqI. apply Nat.add_cancel_r in HeqI. subst k.
315 split; reflexivity.
316 Qed.
317
318 Lemma diagPlaneInject : forall i j : nat, diagPlaneInv (diagPlane i j) = pair i j.
319 Proof.
320 intros. destruct (diagPlaneInv (diagPlane i j)) as [k l] eqn:des.
321 pose proof (diagPlaneSurject (diagPlane i j)). rewrite des in H.
322 apply diagPlaneInjectBis in H. destruct H. subst k. subst l. reflexivity.
323 Qed.
324
325 Definition diagSeq {X : Type} (u : nat -> nat -> X) (p : nat) :=
326 let (n, k) := diagPlaneInv p in u n k.
327
328 Lemma sub_cancel_m : forall n i:nat, (i <= n -> n - (n - i) = i)%nat.
329 Proof.
330 intros. pose proof (Nat.sub_add i n H).
331 apply Nat.add_sub_eq_l in H0. assumption.
332 Qed.
333
334 Lemma diagSumTriangle : forall {R : ConstructiveReals} (u : nat -> nat -> CRcarrier R),
335 forall n : nat, CRsum (diagSeq u) (diagPlane 0 n)
336 == CRsum (fun i => CRsum (u i) (n-i)) n.
337 Proof.
338 induction n.
339 - simpl. unfold diagSeq. reflexivity.
340 - (* The bigger triangle is the smaller one plus the diagonal *)
341 assert (forall i:nat, i <= S n -> diagPlane 0 n + S i = diagPlane (S n - i) i)%nat.
342 { intros. unfold diagPlane. rewrite Nat.add_0_l. rewrite Nat.sub_add.
343 rewrite diagPlaneAbsNext. ring. assumption. }
344 pose proof (H (S n)). rewrite Nat.sub_diag in H0. rewrite <- H0.
345 assert (diagPlane 0 n + S (S n) = S (diagPlane 0 n) + (S n))%nat. ring.
346 rewrite H1. rewrite sum_assoc. rewrite IHn. clear IHn.
347 rewrite (reverse_sum (fun k : nat => diagSeq u (S (diagPlane 0 n) + k))).
348 simpl.
349 (* Remove point S n, 0 *)
350 rewrite Nat.sub_diag. rewrite Nat.add_0_r. simpl.
351 assert (diagSeq u (S (diagPlane 0 n)) = u (S n) O).
352 { pose proof (H O (Nat.le_0_l (S n))). rewrite Nat.sub_0_r in H2.
353 rewrite Nat.add_succ_r in H2. rewrite Nat.add_0_r in H2.
354 rewrite H2. unfold diagSeq. rewrite diagPlaneInject.
355 reflexivity. }
356 rewrite H2. rewrite <- CRplus_assoc. apply CRplus_morph.
357 (* Then rearrange main sum *)
358 rewrite <- sum_plus. apply CRsum_eq. intros.
359 assert (match i with | 0 => S n | S l => n - l end = S (n - i))%nat.
360 { destruct i. rewrite Nat.sub_0_r. reflexivity.
361 rewrite Nat.sub_succ_r. rewrite Nat.succ_pred. reflexivity.
362 apply Nat.sub_gt. assumption. }
363 rewrite H4. simpl.
364 apply CRplus_morph. reflexivity.
365 pose proof (H (S (n - i))). simpl in H5.
366 assert (S (n - i) <= S n)%nat.
367 { apply le_n_S. apply Nat.le_sub_l. }
368 2: reflexivity. 2: apply Nat.le_refl.
369 specialize (H5 H6).
370 rewrite Nat.add_succ_r in H5. rewrite H5.
371 unfold diagSeq. rewrite diagPlaneInject. rewrite sub_cancel_m.
372 reflexivity. assumption.
373 Qed.
374
375 Lemma diagSumMajTriangle : forall {R : ConstructiveReals} (u : nat -> nat -> CRcarrier R),
376 (forall n k : nat, 0 <= u n k)
377 -> forall n : nat, CRsum (diagSeq u) (diagPlane 0 n)
378 <= CRsum (fun i => CRsum (u i) n) n.
379 Proof.
380 (* The triangle is included in the square *)
381 intros. rewrite diagSumTriangle. apply sum_Rle. intros.
382 apply pos_sum_more. intros. apply H. apply Nat.le_sub_l.
383 Qed.
384
385 Lemma diagSumMaj : forall {R : ConstructiveReals} (u : nat -> nat -> CRcarrier R) (A : CRcarrier R),
386 (forall n k : nat, 0 <= u n k)
387 -> (forall n k : nat, CRsum (fun i => CRsum (u i) k) n <= A)
388 -> forall n:nat, CRsum (diagSeq u) n <= A.
389 Proof.
390 (* Finish the triangle and apply previous lemma *)
391 intros. destruct (diagPlaneInv n) as [i j] eqn:desN.
392 apply (CRle_trans _ (CRsum (diagSeq u) (n+i))).
393 - apply pos_sum_more. unfold diagSeq. intros. destruct (diagPlaneInv k).
394 apply H. rewrite <- (Nat.add_0_r n). rewrite <- Nat.add_assoc.
395 apply Nat.add_le_mono_l. rewrite Nat.add_0_l. apply Nat.le_0_l.
396 - assert (diagPlane 0 (i+j) = n + i)%nat.
397 pose proof (diagPlaneSurject n). rewrite desN in H1.
398 unfold diagPlane in H1. unfold diagPlane. rewrite <- H1.
399 simpl. ring. rewrite <- H1.
400 apply (CRle_trans _ (CRsum (fun k => CRsum (u k) (i+j)) (i+j))).
401 apply diagSumMajTriangle. apply H. apply H0.
402 Qed.
403
404 Lemma diagSumMajByLine : forall {R : ConstructiveReals} (u : nat -> nat -> CRcarrier R) (A : CRcarrier R),
405 (forall n k : nat, 0 <= u n k)
406 -> (forall n:nat, CRsum (diagSeq u) n <= A)
407 -> forall n k:nat, CRsum (u n) k <= A.
408 Proof.
409 intros. specialize (H0 (diagPlane 0 (n + k))). rewrite diagSumTriangle in H0.
410 apply (CRle_trans _ (CRsum (fun i : nat => CRsum (u i) (n + k - i)) (n + k))).
411 pose proof (selectOneInSum (fun i : nat => CRsum (u i) (n + k - i)) (n + k) n).
412 simpl in H1. rewrite Nat.add_comm in H1. rewrite Nat.add_sub in H1.
413 rewrite Nat.add_comm in H1. apply H1. rewrite <- (Nat.add_0_r n). rewrite <- Nat.add_assoc.
414 apply Nat.add_le_mono_l. apply Nat.le_0_l. intros. apply cond_pos_sum. intros.
415 apply H. assumption.
416 Qed.
417
418 Lemma powerPositive : forall {R : ConstructiveReals} (n:nat),
419 (0 < CRpow (CR_of_Q R 2) n).
420 Proof.
421 intros. apply CRpow_gt_zero. simpl.
422 apply CR_of_Q_lt. reflexivity.
423 Qed.
424
425 Lemma DiagTriangleShift : forall (p n : nat),
426 let (i, j) := diagPlaneInv p in
427 le (i + j) n -> le p (diagPlane 0 n).
428 Proof.
429 intros. destruct (diagPlaneInv p) as [i j] eqn:des. intros.
430 apply (Nat.le_trans p (diagPlane 0 (i+j))).
431 replace (diagPlane 0 (i + j)) with (p + i)%nat.
432 rewrite <- (Nat.add_0_r p). rewrite <- Nat.add_assoc. apply Nat.add_le_mono_l.
433 apply Nat.le_0_l. pose proof (diagPlaneSurject p).
434 rewrite des in H0. unfold diagPlane in H0. unfold diagPlane.
435 subst p. rewrite Nat.add_0_l. ring. unfold diagPlane. rewrite Nat.add_0_l.
436 rewrite Nat.add_0_l. remember (i + j)%nat. apply Nat.add_le_mono. assumption.
437 apply Nat.div_le_mono. auto. apply Nat.mul_le_mono_nonneg.
438 apply Nat.le_0_l. assumption. apply Nat.le_0_l. apply le_n_S. assumption.
439 Qed.
440
441 Fixpoint DiagTruncateRect {R : ConstructiveReals} (u : nat -> nat -> CRcarrier R)
442 (sumCol : nat -> CRcarrier R)
443 (eps : CRcarrier R)
444 (n : nat)
445 : 0 < eps
446 -> (forall n:nat, series_cv (u n) (sumCol n))
447 -> { p : nat & forall q k:nat,
448 le k n -> le p q -> CRabs _ (CRsum (u k) q - sumCol k)
449 < eps * CRpow (CR_of_Q _ (1#2)) k }.
450 Proof.
451 intros.
452 destruct n.
453 - destruct (CRup_nat (CRinv R eps (inr H))) as [epsN maj].
454 specialize (H0 O (Pos.of_nat epsN)) as [p lim]. exists p. intros.
455 apply CRltEpsilon. inversion H0.
456 subst k. simpl. apply CRltForget. rewrite CRmult_1_r.
457 apply (CRle_lt_trans _ (CR_of_Q R (1 # Pos.of_nat epsN))).
458 apply lim, H1.
459 apply (CRmult_lt_compat_l eps) in maj. 2: exact H.
460 rewrite CRinv_r in maj.
461 apply (CRmult_lt_reg_l (CR_of_Q R (Z.pos (Pos.of_nat epsN) # 1))).
462 apply CR_of_Q_lt. reflexivity.
463 rewrite <- CR_of_Q_mult.
464 setoid_replace ((Z.pos (Pos.of_nat epsN) # 1) * (1 # Pos.of_nat epsN))%Q with 1%Q.
465 rewrite CRmult_comm.
466 apply (CRlt_le_trans _ _ _ maj).
467 apply CRmult_le_compat_l_half. exact H.
468 apply CR_of_Q_le. unfold Qle, Qnum, Qden.
469 do 2 rewrite Z.mul_1_r. destruct epsN. discriminate.
470 apply Pos2Z.pos_le_pos. apply Pos2Nat.inj_le.
471 rewrite SuccNat2Pos.id_succ, Nat2Pos.id. apply Nat.le_refl. discriminate.
472 unfold Qmult, Qeq, Qnum, Qden. do 2 rewrite Z.mul_1_r. reflexivity.
473 - destruct (DiagTruncateRect _ u sumCol eps n H H0) as [pp geo].
474 assert (0 < CRpow (CR_of_Q R (1#2)) (S n)).
475 { apply CRpow_gt_zero. simpl. apply CR_of_Q_lt. reflexivity. }
476 destruct (CRup_nat (CRinv R eps (inr H) * (CRinv R (CRpow (CR_of_Q R (1#2)) (S n))) (inr H1)))
477 as [epsN maj].
478 specialize (H0 (S n) (Pos.of_nat epsN)) as [p lim].
479 exists (p + pp)%nat. intros. apply Nat.le_succ_r in H0.
480 apply CRltEpsilon. destruct H0.
481 + apply CRltForget. apply geo. assumption. apply (Nat.le_trans pp (p + pp)).
482 rewrite <- (Nat.add_0_l pp). rewrite Nat.add_assoc. apply Nat.add_le_mono_r.
483 apply Nat.le_0_l. assumption.
484 + subst k. apply CRltForget.
485 apply (CRle_lt_trans _ (CR_of_Q R (1 # Pos.of_nat epsN))).
486 apply lim. apply (Nat.le_trans p (p + pp)).
487 rewrite <- (Nat.add_0_r p). rewrite <- Nat.add_assoc. apply Nat.add_le_mono_l.
488 apply Nat.le_0_l. assumption.
489 apply (CRmult_lt_compat_l eps) in maj. 2: exact H.
490 rewrite <- CRmult_assoc, CRinv_r, CRmult_1_l in maj.
491 apply (CRmult_lt_compat_l (CRpow (CR_of_Q R (1 # 2)) (S n))) in maj.
492 2: apply CRpow_gt_zero; apply CR_of_Q_lt; reflexivity.
493 rewrite CRinv_r in maj.
494 apply (CRmult_lt_reg_l (CR_of_Q R (Z.pos (Pos.of_nat epsN) # 1))).
495 apply CR_of_Q_lt. reflexivity.
496 rewrite <- CR_of_Q_mult.
497 setoid_replace ((Z.pos (Pos.of_nat epsN) # 1) * (1 # Pos.of_nat epsN))%Q
498 with 1%Q.
499 apply (CRlt_le_trans _ _ _ maj).
500 rewrite CRmult_comm. rewrite <- CRmult_assoc.
501 apply CRmult_le_compat_r. apply CRlt_asym, CRpow_gt_zero.
502 simpl. apply CR_of_Q_lt.
503 reflexivity. rewrite CRmult_comm. apply CRmult_le_compat_r.
504 apply CRlt_asym, H.
505 apply CR_of_Q_le. unfold Qle, Qnum, Qden.
506 do 2 rewrite Z.mul_1_r. destruct epsN. discriminate.
507 apply Pos2Z.pos_le_pos. apply Pos2Nat.inj_le.
508 rewrite SuccNat2Pos.id_succ, Nat2Pos.id. apply Nat.le_refl. discriminate.
509 unfold Qmult, Qeq, Qnum, Qden. do 2 rewrite Z.mul_1_r. reflexivity.
510 Qed.
511
512 Lemma DiagSeqNegTriangle
513 : forall {R : ConstructiveReals} (u : nat -> nat -> CRcarrier R)
514 (n p : nat) (eps sAbs : CRcarrier R),
515 (forall k : nat,
516 le (diagPlane 0 n) k ->
517 (CRabs _ (CRsum (diagSeq (fun i j : nat => CRabs _ (u i j))) k - sAbs) < eps ))
518 -> CRabs _ (CRsum (fun k : nat => CRsum (u (S n + k)%nat) (p - k)) p) < eps * CR_of_Q R 2.
519 Proof.
520 intros.
521 apply (CRle_lt_trans
522 _ (CRsum (fun k : nat => CRabs _ (CRsum (u (S n + k)%nat) (p - k))) p)).
523 apply multiTriangleIneg.
524 apply (CRle_lt_trans
525 _ (CRsum (fun k : nat => CRsum (fun l => CRabs _ (u (S n + k)%nat l)) (p - k)) p)).
526 apply sum_Rle. intros. apply multiTriangleIneg.
527 apply (CRle_lt_trans
528 _ (CRsum (diagSeq (fun i j : nat => CRabs _ (u i j))) (diagPlane 0 (S n + p))
529 - CRsum (diagSeq (fun i j : nat => CRabs _ (u i j))) (diagPlane 0 n))).
530 rewrite (diagSumTriangle _ (S n + p)). rewrite (diagSumTriangle _ n).
531 rewrite sum_assoc. rewrite CRplus_comm.
532 rewrite <- (CRplus_0_r (CRsum
533 (fun k : nat => CRsum (fun l : nat => CRabs _ (u (S n + k)%nat l)) (p - k)) p)).
534 setoid_replace (CRsum (fun k : nat => CRsum (fun j : nat => CRabs _ (u (S n + k)%nat j))
535 (S n + p - (S n + k))) p)
536 with (CRsum (fun k : nat => CRsum (fun l : nat => CRabs _ (u (S n + k)%nat l)) (p - k)) p).
537 unfold CRminus. rewrite CRplus_assoc. apply CRplus_le_compat_l.
538 rewrite CRplus_comm.
539 rewrite <- (CRplus_opp_l (CRsum (fun i : nat => CRsum (fun j : nat => CRabs _ (u i j)) (n - i)) n)).
540 apply CRplus_le_compat_l.
541 apply sum_Rle. intros. apply pos_sum_more. intros. apply CRabs_pos.
542 apply Nat.sub_le_mono_r. simpl. apply le_S.
543 rewrite <- (Nat.add_0_r n). rewrite <- Nat.add_assoc.
544 apply Nat.add_le_mono_l. apply Nat.le_0_l. apply CRsum_eq. intros.
545 replace (S n + p - (S n + i))%nat with (p - i)%nat. reflexivity. simpl.
546 rewrite Nat.sub_add_distr. rewrite Nat.add_comm. rewrite Nat.add_sub. reflexivity.
547 apply (CRle_lt_trans _ _ _ (CRle_abs _)).
548 setoid_replace
549 (CRsum (diagSeq (fun i j : nat => CRabs _ (u i j))) (diagPlane 0 (S n + p)) -
550 CRsum (diagSeq (fun i j : nat => CRabs _ (u i j))) (diagPlane 0 n))
551 with
552 (CRsum (diagSeq (fun i j : nat => CRabs _ (u i j))) (diagPlane 0 (S n + p)) - sAbs
553 + (sAbs - CRsum (diagSeq (fun i j : nat => CRabs _ (u i j))) (diagPlane 0 n))).
554 apply (CRle_lt_trans _ _ _ (CRabs_triang _ _)).
555 rewrite (CR_of_Q_plus R 1 1), CRmult_plus_distr_l, CRmult_1_r.
556 apply CRplus_le_lt_compat. apply CRlt_asym.
557 apply (H (diagPlane 0 (S n + p))).
558 unfold diagPlane. rewrite Nat.add_0_l. rewrite Nat.add_0_l.
559 remember (S n + p)%nat as n0. assert (n <= n0)%nat.
560 subst n0. simpl. apply le_S. rewrite <- (Nat.add_0_r n). rewrite <- Nat.add_assoc.
561 apply Nat.add_le_mono_l. apply Nat.le_0_l.
562 apply Nat.add_le_mono. assumption. apply Nat.div_le_mono. auto.
563 apply Nat.mul_le_mono. assumption. apply le_n_S. assumption.
564 rewrite CRabs_minus_sym. apply H. apply Nat.le_refl.
565 unfold CRminus. rewrite CRplus_assoc. apply CRplus_morph. reflexivity.
566 rewrite <- CRplus_assoc, CRplus_opp_l, CRplus_0_l. reflexivity.
567 Qed.
568
569 Lemma DiagSeqInfiniteSum
570 : forall {R : ConstructiveReals} (u : nat -> nat -> CRcarrier R)
571 (sumCol : nat -> CRcarrier R)
572 (sAbs : CRcarrier R),
573 series_cv (diagSeq (fun i j => CRabs _ (u i j))) sAbs
574 -> (forall n:nat, series_cv (u n) (sumCol n))
575 -> { s : CRcarrier R & (series_cv sumCol s)
576 * (series_cv (diagSeq u) s)
577 * (s <= sAbs) }%type.
578 Proof.
579 intros R u sumCol sAbs H7 H1.
580 assert { s : CRcarrier R & prod (series_cv (diagSeq u) s) (s <= sAbs) } as [s H].
581 { destruct (series_cv_maj (diagSeq u)
582 (diagSeq (fun i j => CRabs _ (u i j)))
583 sAbs) as [s scv].
584 intros. unfold diagSeq. destruct (diagPlaneInv n).
585 apply CRle_refl. exact H7.
586 exists s. exact scv. }
587 exists s. split. split. 2: apply H. 2: apply H. destruct H as [H _].
588 pose proof (Un_cv_nat_real _ _ H7) as H0. clear H7.
589 apply Un_cv_real_nat. intros eps epsPos.
590 (* Take big triangle absolute-close to epsilon *)
591 assert (forall n : nat, (0 <= diagSeq (fun i j : nat => CRabs _ (u i j)) n)) as diagPos.
592 { intro n. unfold diagSeq. destruct (diagPlaneInv n). apply CRabs_pos. }
593 assert (0 < eps * CRpow (CR_of_Q R (1#2)) 3) as eighthEpsPos.
594 { apply CRmult_lt_0_compat. assumption. apply CRpow_gt_zero.
595 simpl. apply CR_of_Q_lt. reflexivity. }
596 destruct (H0 (eps * CRpow (CR_of_Q R (1#2)) 3) eighthEpsPos) as [Nabs H2].
597 pose proof (DiagTriangleShift Nabs) as tShift.
598 destruct (diagPlaneInv Nabs) as [i j] eqn:desNabs.
599 exists (i + j)%nat. intros n nMaj. specialize (tShift n nMaj).
600 setoid_replace eps with (INR 7 * eps * CRpow (CR_of_Q R (1#2)) 3 + eps * CRpow (CR_of_Q R (1#2)) 3).
601 setoid_replace (CRsum sumCol n - s)
602 with (CRsum sumCol n -CRsum (diagSeq u) (diagPlane 0 n)
603 + (CRsum (diagSeq u) (diagPlane 0 n) - s)).
604 apply (CRle_lt_trans _ _ _ (CRabs_triang _ _)).
605 apply CRplus_le_lt_compat.
606 - (* Replace infinite rectangle by finite trapeze, which contains the main triangle. *)
607 apply CRlt_asym.
608 destruct (DiagTruncateRect u sumCol (eps * CRpow (CR_of_Q R (1#2)) 4) n) as [p geo].
609 apply CRmult_lt_0_compat. assumption. apply CRpow_gt_zero.
610 simpl. apply CR_of_Q_lt. reflexivity.
611 intros. apply H1.
612 setoid_replace (CRsum sumCol n - CRsum (diagSeq u) (diagPlane 0 n))
613 with (CRsum sumCol n - CRsum (fun k => (CRsum (u k) (p+(n-k)))) n
614 + (CRsum (fun k => (CRsum (u k) (p+(n-k)))) n
615 - CRsum (diagSeq u) (diagPlane 0 n))).
616 apply (CRle_lt_trans _ _ _ (CRabs_triang _ _)).
617 setoid_replace (INR 7 * eps * CRpow (CR_of_Q R (1 # 2)) 3)
618 with (eps * CRpow (CR_of_Q R (1 # 2)) 3 + INR 6 * eps * CRpow (CR_of_Q R (1 # 2)) 3).
619 apply CRplus_le_lt_compat.
620 + apply CRlt_asym.
621 unfold CRminus.
622 rewrite <- sum_opp, <- sum_plus.
623 (* Majorate by the trapeze, which contains the triangle *)
624 apply (CRle_lt_trans
625 _ (CRsum (fun l : nat => CRabs _ (sumCol l - CRsum (u l) (p+(n-l)))) n)).
626 apply multiTriangleIneg.
627 apply (CRle_lt_trans
628 _ (CRsum (fun k => eps * CRpow (CR_of_Q R (1 # 2)) 4 * CRpow (CR_of_Q R (1 # 2)) k) n)).
629 apply sum_Rle. intros. specialize (geo (p + (n - k))%nat k).
630 apply CRlt_asym.
631 rewrite CRabs_minus_sym. apply geo. exact H3.
632 rewrite <- (Nat.add_0_r p). rewrite <- Nat.add_assoc. apply Nat.add_le_mono_l.
633 apply Nat.le_0_l.
634 rewrite <- (CRsum_eq (fun k : nat => CRpow (CR_of_Q R (1 # 2)) k * (eps * CRpow (CR_of_Q R (1 # 2)) 4))).
635 rewrite sum_scale. rewrite CRmult_comm, CRmult_assoc.
636 apply CRmult_lt_compat_l. assumption.
637 setoid_replace (CRpow (CR_of_Q R (1 # 2)) 3)
638 with (CRpow (CR_of_Q R (1 # 2)) 4 * CR_of_Q R 2).
639 apply CRmult_lt_compat_l. apply CRpow_gt_zero. simpl.
640 apply CR_of_Q_lt. reflexivity.
641 apply GeoHalfBelowTwo.
642 setoid_replace (CRpow (CR_of_Q R (1 # 2)) 4)
643 with (CR_of_Q R (1#2) * CRpow (CR_of_Q R (1 # 2)) 3). 2: reflexivity.
644 rewrite CRmult_comm, <- CRmult_assoc, <- (CR_of_Q_mult _ 2).
645 setoid_replace (2 * (1 # 2))%Q with 1%Q. rewrite CRmult_1_l.
646 reflexivity. reflexivity.
647 intros. apply CRmult_comm.
648 + destruct p.
649 setoid_replace (CRsum (fun k : nat => CRsum (u k) (0 + (n - k))) n)
650 with (CRsum (diagSeq u) (diagPlane 0 n)).
651 unfold CRminus.
652 rewrite CRplus_opp_r. rewrite CRabs_right. 2: apply CRle_refl.
653 apply CRmult_lt_0_compat. apply CRmult_lt_0_compat.
654 apply CR_of_Q_lt. reflexivity.
655 assumption. apply CRpow_gt_zero. simpl.
656 apply CR_of_Q_lt. reflexivity.
657 simpl. rewrite diagSumTriangle. reflexivity.
658 setoid_replace (CRsum (fun k : nat => CRsum (u k) (S p + (n - k))) n)
659 with (CRsum (diagSeq u) (diagPlane 0 (S n+p))
660 - CRsum (fun k : nat => CRsum (u (S n + k)%nat) (p - k)) p).
661 unfold CRminus. rewrite CRplus_comm. rewrite <- CRplus_assoc.
662 setoid_replace (- CRsum (diagSeq u) (diagPlane 0 n) +
663 CRsum (diagSeq u) (diagPlane 0 (S n + p)) +
664 - CRsum (fun k : nat => CRsum (u (S n + k)%nat) (p - k)) p)
665 with (CRsum (diagSeq u) (diagPlane 0 (S n + p))
666 - CRsum (diagSeq u) (diagPlane 0 n)
667 - (CRsum (fun k : nat => CRsum (u (S n + k)%nat) (p - k)) p)).
668 apply (CRle_lt_trans _ _ _ (CRabs_triang _ _)).
669 rewrite CRabs_opp.
670 setoid_replace (INR 6 * eps * CRpow (CR_of_Q R (1 # 2)) 3)
671 with (INR 2 * eps * CRpow (CR_of_Q R (1 # 2)) 3 + INR 4 * eps * CRpow (CR_of_Q R (1 # 2)) 3).
672 apply CRplus_le_lt_compat.
673 setoid_replace (CRsum (diagSeq u) (diagPlane 0 (S n + p))
674 - CRsum (diagSeq u) (diagPlane 0 n))
675 with (CRsum (diagSeq u) (diagPlane 0 (S n + p)) - s
676 + (s - CRsum (diagSeq u) (diagPlane 0 n))).
677 apply (CRle_trans _ _ _ (CRabs_triang _ _)).
678 unfold INR. simpl (Z.of_nat 2 # 1).
679 rewrite (CR_of_Q_plus R 1 1), CRmult_plus_distr_r, CRmult_1_l.
680 rewrite CRmult_plus_distr_r.
681 apply CRplus_le_compat.
682 apply (CRle_trans _ (sAbs - CRsum (fun n0 : nat => CRabs _ (diagSeq u n0))
683 (diagPlane 0 (S n + p)))).
684 apply (series_cv_abs_remainder (diagSeq u)).
685 apply H.
686 apply (series_cv_eq (diagSeq (fun i j : nat => CRabs _ (u i j)))).
687 intros. unfold diagSeq. destruct (diagPlaneInv n0). reflexivity.
688 apply Un_cv_real_nat. apply H0.
689 rewrite <- (CRsum_eq (diagSeq (fun i j : nat => CRabs _ (u i j)))).
690 apply CRlt_asym.
691 apply (CRle_lt_trans _ _ _ (CRle_abs _)).
692 rewrite CRabs_minus_sym.
693 apply H2. pose proof (DiagTriangleShift Nabs (S n +p)). rewrite desNabs in H3.
694 apply H3. apply (Nat.le_trans _ n). assumption. simpl. apply le_S.
695 rewrite <- (Nat.add_0_r n). rewrite <- Nat.add_assoc.
696 apply Nat.add_le_mono_l. apply Nat.le_0_l.
697 intros. unfold diagSeq. destruct (diagPlaneInv i0). reflexivity.
698 rewrite CRabs_minus_sym.
699 apply (CRle_trans _ (sAbs - CRsum (fun n0 : nat => CRabs _ (diagSeq u n0))
700 (diagPlane 0 n))).
701 apply (series_cv_abs_remainder
702 (fun n0 : nat => diagSeq u n0)).
703 assumption.
704 apply (series_cv_eq (diagSeq (fun i j : nat => CRabs _ (u i j)))).
705 intros. unfold diagSeq. destruct (diagPlaneInv n0). reflexivity.
706 apply Un_cv_real_nat. apply H0.
707 rewrite <- (CRsum_eq (diagSeq (fun i j : nat => CRabs _ (u i j)))).
708 apply CRlt_asym.
709 apply (CRle_lt_trans _ _ _ (CRle_abs _)).
710 rewrite CRabs_minus_sym.
711 apply H2. assumption. intros. unfold diagSeq. destruct (diagPlaneInv i0).
712 reflexivity.
713 unfold CRminus. rewrite CRplus_assoc. apply CRplus_morph.
714 reflexivity. rewrite <- CRplus_assoc, CRplus_opp_l, CRplus_0_l. reflexivity.
715 apply (CRlt_trans _ (eps * CRpow (CR_of_Q R (1 # 2)) 3 * CR_of_Q R 2)).
716 apply (DiagSeqNegTriangle _ _ _ _ sAbs). intros. apply H2.
717 apply (Nat.le_trans _ (diagPlane 0 n)); assumption. rewrite <- (CRmult_comm (CR_of_Q R 2)).
718 rewrite CRmult_assoc. apply CRmult_lt_compat_r. apply CRmult_lt_0_compat.
719 assumption. apply CRpow_gt_zero. simpl.
720 apply CR_of_Q_lt. reflexivity.
721 apply CR_of_Q_lt. reflexivity.
722 setoid_replace (@INR R 6) with (@INR R 2 + @INR R 4).
723 do 2 rewrite CRmult_plus_distr_r. reflexivity.
724 unfold INR. rewrite <- CR_of_Q_plus. apply CR_of_Q_morph.
725 rewrite Qinv_plus_distr. reflexivity.
726 apply CRplus_morph. 2: reflexivity.
727 rewrite (diagSumTriangle _ (S n + p)). unfold CRminus.
728 rewrite CRplus_comm. reflexivity.
729 rewrite (diagSumTriangle _ (S n + p)). unfold CRminus.
730 rewrite sum_assoc.
731 rewrite (CRsum_eq (fun k : nat => CRsum (u (S n + k)%nat) (S n + p - (S n + k)))
732 (fun k : nat => CRsum (u (S n + k)%nat) (p - k))).
733 unfold CRminus. rewrite CRplus_assoc, CRplus_opp_r, CRplus_0_r.
734 apply CRsum_eq. intros. replace (S n + p - i0)%nat with (S p + (n - i0))%nat.
735 reflexivity. rewrite Nat.add_sub_assoc. simpl. destruct i0.
736 rewrite Nat.add_comm. reflexivity. rewrite Nat.add_comm. reflexivity. assumption.
737 intros. replace (S n + p - (S n + i0))%nat with (p - i0)%nat. reflexivity.
738 simpl. rewrite Nat.sub_add_distr. rewrite Nat.add_comm. rewrite Nat.add_sub.
739 reflexivity.
740 + setoid_replace (@INR R 7) with (1 + @INR R 6).
741 do 2 rewrite CRmult_plus_distr_r. rewrite CRmult_1_l. reflexivity.
742 unfold INR. rewrite <- CR_of_Q_plus. apply CR_of_Q_morph.
743 rewrite Qinv_plus_distr. reflexivity.
744 + unfold CRminus. rewrite CRplus_assoc. apply CRplus_morph.
745 reflexivity. rewrite <- CRplus_assoc, CRplus_opp_l, CRplus_0_l. reflexivity.
746 - apply (CRle_lt_trans _ (sAbs - CRsum (fun n => CRabs _ (diagSeq u n))
747 (diagPlane 0 n))).
748 apply (series_cv_abs_remainder
749 (fun n0 : nat => diagSeq u n0)).
750 apply H.
751 apply (series_cv_eq (diagSeq (fun i j : nat => CRabs _ (u i j)))).
752 intros. unfold diagSeq. destruct (diagPlaneInv n0). reflexivity.
753 apply Un_cv_real_nat. apply H0.
754 rewrite <- (CRsum_eq (diagSeq (fun i j : nat => CRabs _ (u i j)))).
755 apply (CRle_lt_trans _ _ _ (CRle_abs _)).
756 rewrite CRabs_minus_sym.
757 apply H2. assumption.
758 intros. unfold diagSeq. destruct (diagPlaneInv i0). reflexivity.
759 - unfold CRminus. rewrite CRplus_assoc. apply CRplus_morph.
760 reflexivity. rewrite <- CRplus_assoc, CRplus_opp_l, CRplus_0_l. reflexivity.
761 - setoid_replace (CRpow (CR_of_Q R (1 # 2)) 3) with (CR_of_Q R (1 # 8)).
762 rewrite <- CRmult_plus_distr_r.
763 setoid_replace (INR 7 * eps + eps) with (eps * INR 8).
764 rewrite CRmult_assoc. unfold INR. rewrite <- CR_of_Q_mult.
765 setoid_replace ((Z.of_nat 8 # 1) * (1 # 8))%Q with 1%Q.
766 rewrite CRmult_1_r. reflexivity. reflexivity.
767 setoid_replace (@INR R 8) with (1 + @INR R 7).
768 rewrite CRmult_plus_distr_l, CRmult_1_r, CRplus_comm, CRmult_comm. reflexivity.
769 unfold INR. rewrite <- CR_of_Q_plus.
770 apply CR_of_Q_morph. reflexivity.
771 unfold CRpow. rewrite CRmult_1_r.
772 do 2 rewrite <- CR_of_Q_mult. apply CR_of_Q_morph. reflexivity.
773 Qed.
774
775 Lemma growing_transit : forall {R : ConstructiveReals} (un : nat -> CRcarrier R),
776 (forall n:nat, un n <= un (S n))
777 -> forall n p : nat, le n p -> un n <= un p.
778 Proof.
779 induction p.
780 - intros. inversion H0. apply CRle_refl.
781 - intros. apply Nat.le_succ_r in H0. destruct H0.
782 apply (CRle_trans _ (un p)). apply IHp, H0. apply H.
783 subst n. apply CRle_refl.
784 Qed.
785
786 (* In the positive case, requesting the convergence of Rabs diagSeq
787 would be absurd, as it is the same as the conclusion. *)
788 Lemma DiagSeqInfiniteSumColPos
789 : forall {R : ConstructiveReals} (u : nat -> nat -> CRcarrier R)
790 (sumCol : nat -> CRcarrier R)
791 (s : CRcarrier R),
792 (forall n k:nat, 0 <= u n k)
793 -> (forall n:nat, series_cv (u n) (sumCol n))
794 -> (series_cv sumCol s)
795 -> (series_cv (diagSeq u) s).
796 Proof.
797 intros R u sumCol s uPos cvCol cvSumCol.
798 assert (forall n:nat, CRsum (diagSeq u) n <= s) as belowS.
799 { apply diagSumMaj. assumption. intros n k.
800 apply (CRle_trans _ (CRsum sumCol n)). apply sum_Rle.
801 intros. apply growing_ineq. 2: apply cvCol.
802 intro i. rewrite <- CRplus_0_r. apply CRplus_le_compat.
803 apply CRle_refl. apply uPos.
804 apply growing_ineq. 2: apply cvSumCol.
805 intro i. rewrite <- CRplus_0_r. apply CRplus_le_compat.
806 apply CRle_refl.
807 apply (series_cv_nonneg (u (S i))). apply uPos.
808 apply cvCol. }
809 (* Conversely, show that diagSeq approaches s *)
810 intros n.
811 destruct (cvSumCol (2*n)%positive) as [N H1].
812 assert (0 < CR_of_Q R (1 # 4*n)) as quarterEpsPos.
813 { apply CR_of_Q_lt. reflexivity. }
814 destruct (DiagTruncateRect u sumCol (CR_of_Q R (1 # 4*n)) N quarterEpsPos cvCol)
815 as [p H2].
816 exists (diagPlane 0 (N+p)). intros.
817 (* Go back to the N+p triangle *)
818 rewrite CRabs_minus_sym. rewrite CRabs_right.
819 apply (CRle_trans _ (s - CRsum (diagSeq u) (diagPlane 0 (N + p)))).
820 unfold CRminus. apply CRplus_le_compat_l.
821 apply CRopp_ge_le_contravar. apply growing_transit.
822 - intro k. rewrite <- (CRplus_0_r (CRsum (diagSeq u) k)).
823 simpl. apply CRplus_le_compat_l. unfold diagSeq.
824 destruct (diagPlaneInv (S k)). apply uPos.
825 - apply H.
826 - rewrite diagSumTriangle.
827 (* Truncate to the N trapeze *)
828 apply (CRle_trans _ (s - CRsum (fun i : nat => CRsum (u i) (N + p - i)) N)).
829 unfold CRminus. apply CRplus_le_compat_l.
830 apply CRopp_ge_le_contravar. apply pos_sum_more.
831 intro k. apply cond_pos_sum. apply uPos.
832 rewrite <- (Nat.add_0_r N). rewrite <- Nat.add_assoc. apply Nat.add_le_mono_l.
833 apply Nat.le_0_l.
834 (* Extend to the infinite vertical rectangle *)
835 apply (CRle_trans _ (s - CRsum sumCol N + CR_of_Q R (1#2*n))).
836 specialize (H1 N (Nat.le_refl N)).
837 rewrite CRabs_minus_sym in H1.
838 apply (CRle_trans _ _ _ (CRle_abs _)) in H1.
839 unfold CRminus. rewrite CRplus_assoc. apply CRplus_le_compat_l.
840 apply (CRplus_le_reg_l (CRsum sumCol N)). rewrite <- CRplus_assoc.
841 rewrite CRplus_opp_r. rewrite CRplus_0_l. rewrite <- sum_opp.
842 rewrite <- sum_plus.
843 apply (CRle_trans
844 _ (CRsum (fun k => CR_of_Q R (1#4*n) * CRpow (CR_of_Q R (1#2)) k) N)).
845 apply sum_Rle. intros n0 H0. specialize (H2 (N+p-n0)%nat n0).
846 apply (CRle_trans _ _ _ (CRle_abs _)).
847 pose proof (CRabs_minus_sym (sumCol n0)). unfold CRminus in H3.
848 rewrite H3. clear H3. apply CRlt_asym, H2.
849 exact H0. rewrite Nat.add_comm.
850 rewrite <- Nat.add_sub_assoc. rewrite <- (Nat.add_0_r p).
851 rewrite <- Nat.add_assoc. apply Nat.add_le_mono_l. apply Nat.le_0_l.
852 assumption.
853 rewrite (CRsum_eq _ (fun k : nat => CRpow (CR_of_Q R (1#2)) k * (CR_of_Q R (1# 4*n)))).
854 rewrite sum_scale, CRmult_comm. apply CRlt_asym.
855 apply (CRlt_le_trans _ (CR_of_Q R (1#4*n) * CR_of_Q R 2)).
856 apply CRmult_lt_compat_l.
857 exact quarterEpsPos. apply GeoHalfBelowTwo.
858 rewrite <- CR_of_Q_mult. apply CR_of_Q_le.
859 unfold Qmult, Qle, Qnum, Qden. do 2 rewrite Z.mul_1_l.
860 rewrite <- Pos2Z.inj_mul. rewrite Pos.mul_1_r, Pos.mul_assoc.
861 apply Z.le_refl.
862 intros. apply CRmult_comm.
863 apply (CRplus_le_reg_r (- CR_of_Q R (1#2*n))).
864 rewrite CRplus_assoc.
865 rewrite CRplus_opp_r. rewrite CRplus_0_r.
866 rewrite <- CR_of_Q_opp, <- CR_of_Q_plus.
867 setoid_replace ((1 # n) + - (1 # 2 * n))%Q with (1 # 2*n)%Q.
868 specialize (H1 N (Nat.le_refl N)).
869 apply (CRle_trans _ _ _ (CRle_abs _)).
870 rewrite CRabs_minus_sym. apply H1.
871 rewrite <- (Qplus_inj_r _ _ (1#2*n)).
872 rewrite Qinv_plus_distr. ring_simplify. reflexivity.
873 - rewrite <- (CRplus_opp_r (CRsum (diagSeq u) i)).
874 apply CRplus_le_compat. apply belowS. apply CRle_refl.
875 Qed.
876
877 Lemma Rlt_0_half : forall {R : ConstructiveReals}, 0 < CR_of_Q R (1#2).
878 Proof.
879 intro R. apply CR_of_Q_lt. reflexivity.
880 Qed.
881
882 Fixpoint FindPointInSubdivision (Pn : nat -> nat) (n : nat)
883 : (forall k, Pn k < Pn (S k))%nat
884 -> (Pn O = O)
885 -> { p : nat | (Pn p <= n < Pn (S p))%nat }.
886 Proof.
887 intros. destruct n.
888 - exists O. repeat split. rewrite H0. apply Nat.le_refl.
889 specialize (H O). rewrite H0 in H. apply H.
890 - destruct (FindPointInSubdivision Pn n H H0) as [k kmaj].
891 destruct (le_lt_dec (Pn (S k)) (S n)).
892 + exists (S k). split. apply l. apply (Nat.lt_le_trans _ (S (Pn (S k)))).
893 apply le_n_S. apply kmaj. apply (H (S k)).
894 + exists k. split. 2: apply l. apply (Nat.le_trans _ n).
895 apply kmaj. apply le_S. apply Nat.le_refl.
896 Qed.
897
898 Lemma FindPointInSubdivisionSmallest
899 : forall (Pn : nat -> nat) (Pinc : forall k, lt (Pn k) (Pn (S k)))
900 (Pzero : Pn O = O) (n i : nat),
901 le (Pn i) n
902 -> le i (proj1_sig (FindPointInSubdivision Pn n Pinc Pzero)).
903 Proof.
904 induction i.
905 - intros. apply Nat.le_0_l.
906 - intros. destruct (FindPointInSubdivision Pn n Pinc Pzero) as [r rmaj].
907 simpl in IHi. simpl. assert (i <= r)%nat.
908 apply IHi. apply (Nat.le_trans _ (Pn (S i))). 2: apply H.
909 specialize (Pinc i). apply le_S in Pinc. apply le_S_n in Pinc. apply Pinc.
910 clear IHi. apply le_n_S in H0. apply Nat.le_succ_r in H0.
911 destruct H0. apply H0. exfalso. inversion H0. subst i.
912 apply Nat.le_ngt in H. destruct rmaj. contradiction.
913 Qed.
914
915 Lemma ROpenBallConvex : forall {R : ConstructiveReals} (x r a b c : CRcarrier R),
916 (a <= b /\ b <= c)
917 -> CRabs _ (x - a) <= r
918 -> CRabs _ (x - c) <= r
919 -> CRabs _ (x - b) <= r.
920 Proof.
921 intros. apply CRabs_le. destruct H.
922 apply CRabs_def2 in H0. apply CRabs_def2 in H1. split.
923 - apply (CRle_trans _ (x-c)). apply H1.
924 apply CRplus_le_compat_l. apply CRopp_ge_le_contravar.
925 apply H2.
926 - apply (CRle_trans _ (x-a)). 2: apply H0.
927 apply CRplus_le_compat_l. apply CRopp_ge_le_contravar.
928 apply H.
929 Qed.
930
931
932 (* Positivity is necessary, because 1 - 1 can be summed
933 by blocks of two and make a constant zero sum,
934 whereas individually the sum oscillates between 0 and 1. *)
935 Lemma infinite_sum_assoc
936 : forall {R : ConstructiveReals} (xn : nat -> CRcarrier R)
937 (Pn : nat -> nat) (s : CRcarrier R),
938 (forall n, Pn n < Pn (S n))%nat
939 -> (forall n, 0 <= xn n)
940 -> Pn O = O
941 -> (series_cv (fun n => CRsum (fun k => xn (k+ Pn n)%nat)
942 (Pn (S n) - Pn n - 1)) s)
943 -> series_cv xn s.
944 Proof.
945 intros.
946 assert (forall p q : nat, p <= q -> Pn p <= Pn q)%nat as PnInc.
947 { induction q.
948 - intros. inversion H3. apply Nat.le_refl.
949 - intros. apply Nat.le_succ_r in H3. destruct H3.
950 apply (Nat.le_trans _ (Pn q)). apply IHq. apply H3.
951 apply (Nat.le_trans _ (S (Pn q))). apply le_S. apply Nat.le_refl.
952 apply H. subst p. apply Nat.le_refl. }
953 assert (forall p:nat,
954 CRsum (fun n : nat => CRsum (fun k : nat => xn (k + Pn n))%nat (Pn (S n) - Pn n - 1)) p
955 == CRsum xn (Pn (S p) - 1)) as assocSum.
956 { induction p.
957 - simpl. repeat rewrite H1. rewrite Nat.sub_0_r.
958 rewrite (CRsum_eq _ xn). reflexivity. intros.
959 rewrite Nat.add_0_r. reflexivity.
960 - simpl. rewrite IHp. clear IHp.
961 destruct (Nat.le_exists_sub 1 (Pn (S p))) as [r [H3 _]].
962 specialize (H p). apply (Nat.le_trans _ (S (Pn p))). 2: apply H.
963 apply le_n_S. apply Nat.le_0_l.
964 assert (r+1 = S r)%nat. rewrite Nat.add_comm. reflexivity.
965 rewrite H3. rewrite Nat.add_sub.
966 rewrite (CRsum_eq (fun k : nat => xn (k + (r + 1))%nat) (fun k : nat => xn (S r + k)%nat)).
967 rewrite <- (sum_assoc xn r).
968 replace (S r + (Pn (S (S p)) - (r + 1) - 1))%nat
969 with (Pn (S (S p)) - 1)%nat.
970 reflexivity. rewrite Nat.add_sub_assoc.
971 rewrite <- H4. rewrite Nat.add_comm. rewrite Nat.sub_add.
972 reflexivity. rewrite <- H3. apply (Nat.le_trans _ (S (Pn (S p)))).
973 apply le_S. apply Nat.le_refl. apply H. rewrite <- H3.
974 destruct (Nat.le_exists_sub (S (Pn (S p))) (Pn (S (S p)))).
975 apply H. destruct H5. rewrite H5. simpl.
976 replace (S (Pn (S p))) with (1 + Pn (S p))%nat.
977 rewrite Nat.add_assoc. rewrite Nat.add_sub. 2: reflexivity.
978 rewrite Nat.add_comm. apply le_n_S. apply Nat.le_0_l.
979 intros. rewrite Nat.add_comm. rewrite (Nat.add_comm r). reflexivity. }
980 assert (forall n:nat,
981 (Pn 1 <= n)%nat
982 -> let (p,_) := FindPointInSubdivision Pn n H H1 in
983 (CRsum (fun n : nat => CRsum (fun k : nat => xn (k + Pn n))%nat (Pn (S n) - Pn n - 1)) (p-1)
984 <= CRsum xn n
985 /\ CRsum xn n
986 <= CRsum (fun n : nat => CRsum (fun k : nat => xn (k + Pn n))%nat (Pn (S n) - Pn n - 1)) p)).
987 { intro n. destruct (FindPointInSubdivision Pn n H H1) as [p pmaj].
988 repeat rewrite assocSum. split.
989 apply pos_sum_more. apply H0. destruct p.
990 exfalso. apply Nat.le_ngt in H3. destruct pmaj. contradiction.
991 simpl. rewrite Nat.sub_0_r. apply (Nat.le_trans _ (Pn (S p))).
992 2: apply pmaj. apply Nat.le_sub_l.
993 apply pos_sum_more. apply H0. apply Nat.le_add_le_sub_r.
994 rewrite Nat.add_comm. apply pmaj. }
995 intros n. specialize (H2 n) as [p pmaj].
996 exists (Pn (S p)). intros. specialize (H3 i).
997 pose proof (FindPointInSubdivisionSmallest Pn H H1 i).
998 destruct (FindPointInSubdivision Pn i H H1) as [q qmaj].
999 rewrite CRabs_minus_sym.
1000 assert (S p <= q)%nat.
1001 { apply H4. apply H2. }
1002 apply (ROpenBallConvex
1003 _ _ (CRsum (fun n : nat => CRsum (fun k : nat => xn (k + Pn n)%nat) (Pn (S n) - Pn n - 1)) (q-1))
1004 _ (CRsum (fun n : nat => CRsum (fun k : nat => xn (k + Pn n)%nat) (Pn (S n) - Pn n - 1)) q)).
1005 split; apply H3.
1006 apply (Nat.le_trans _ (Pn (S p))). 2: apply H2.
1007 apply PnInc. apply le_n_S. apply Nat.le_0_l.
1008 apply (Nat.le_trans _ (Pn (S p))). 2: apply H2.
1009 apply PnInc. apply le_n_S. apply Nat.le_0_l.
1010 rewrite CRabs_minus_sym.
1011 apply pmaj. apply Nat.le_add_le_sub_r.
1012 rewrite Nat.add_comm. apply H5.
1013 rewrite CRabs_minus_sym; apply pmaj.
1014 apply (Nat.le_trans _ (S p)).
1015 apply le_S. apply Nat.le_refl. apply H5.
1016 Qed.