| 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. |