| 1 |
(* |
| 2 |
Copyright © 2008 Russell O’Connor |
| 3 |
|
| 4 |
Permission is hereby granted, free of charge, to any person obtaining a copy of |
| 5 |
this proof and associated documentation files (the "Proof"), to deal in |
| 6 |
the Proof without restriction, including without limitation the rights to |
| 7 |
use, copy, modify, merge, publish, distribute, sublicense, and/or sell copies of |
| 8 |
the Proof, and to permit persons to whom the Proof is furnished to do so, |
| 9 |
subject to the following conditions: |
| 10 |
|
| 11 |
The above copyright notice and this permission notice shall be included in all |
| 12 |
copies or substantial portions of the Proof. |
| 13 |
|
| 14 |
THE PROOF IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR |
| 15 |
IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, FITNESS |
| 16 |
FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR |
| 17 |
COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER |
| 18 |
IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN |
| 19 |
CONNECTION WITH THE PROOF OR THE USE OR OTHER DEALINGS IN THE PROOF. |
| 20 |
*) |
| 21 |
From Coq Require Import ZArith Qround. |
| 22 |
Require Import CoRN.metric2.Metric. |
| 23 |
Require Import CoRN.metric2.ProductMetric. |
| 24 |
Require Import CoRN.metric2.UniformContinuity. |
| 25 |
Require Export CoRN.reals.fast.RasterizeQ. |
| 26 |
Require Import CoRN.reals.fast.Interval. |
| 27 |
Require Export CoRN.metric2.Graph. |
| 28 |
Require Import CoRN.model.totalorder.QMinMax. |
| 29 |
Require Export CoRN.model.totalorder.QposMinMax. |
| 30 |
|
| 31 |
(** |
| 32 |
* Plotting |
| 33 |
Plotting a uniformly continuous function on a finite interval consists |
| 34 |
of producing the graph of a function as a compact set, approximating that |
| 35 |
graph, and finally rasterizing that approximation. |
| 36 |
|
| 37 |
A range for the plot must be provided. We choose to clamp the plotted |
| 38 |
function so that it lies inside the specified range. Thus we plot |
| 39 |
[compose (clip b t) f] rather than [f]. |
| 40 |
|
| 41 |
Afterwards we will plot more general located subsets of the plane: |
| 42 |
- Each blank pixels is correct, meaning there are no points of the subset |
| 43 |
inside the rectangular regions it represents. In other words, filled |
| 44 |
pixels cover the subset. |
| 45 |
- Each filled pixel means there exists a point of the subset inside its |
| 46 |
rectangular region, or inside one of the adjacent pixels. Thus when we |
| 47 |
zoom in the filled pixels, we will see more structure. |
| 48 |
- The pixels overlap, meaning each edge belongs to the 2 pixels that |
| 49 |
touch it, and each corner belongs to the 4 pixels that touch it. |
| 50 |
|
| 51 |
*) |
| 52 |
|
| 53 |
Local Open Scope uc_scope. |
| 54 |
|
| 55 |
Section PlotPath. |
| 56 |
Variable (from to:Q). |
| 57 |
Hypothesis Hfromto:from<=to. |
| 58 |
|
| 59 |
Variable (l r:Q). |
| 60 |
Hypothesis Hlr : l < r. |
| 61 |
|
| 62 |
Variable (b t:Q). |
| 63 |
Hypothesis Hbt : b < t. |
| 64 |
|
| 65 |
Variable n : positive. |
| 66 |
|
| 67 |
Let w := r - l. |
| 68 |
Let h := t - b. |
| 69 |
|
| 70 |
Lemma wpos : 0 < w. |
| 71 |
Proof. |
| 72 |
apply Qlt_minus_iff in Hlr. exact Hlr. |
| 73 |
Qed. |
| 74 |
|
| 75 |
Lemma hpos : 0 < h. |
| 76 |
Proof. |
| 77 |
apply Qlt_minus_iff in Hbt. exact Hbt. |
| 78 |
Qed. |
| 79 |
|
| 80 |
(* Compute the number of pixels on the Y-axis to make square pixels. *) |
| 81 |
Let m : positive := Z.to_pos (Qceiling ((t-b) * inject_Z (Z.pos n) / (r-l))). |
| 82 |
|
| 83 |
(** |
| 84 |
Half the error in the Plot example, since we need to approximate twice. |
| 85 |
*) |
| 86 |
Let err := Qpos_max ((1 # 8 * n) * (exist _ _ wpos)) |
| 87 |
((1 # 8 * m) * (exist _ _ hpos)). |
| 88 |
|
| 89 |
Variable path:Q_as_MetricSpace --> Complete Q2. |
| 90 |
|
| 91 |
(** The actual plot function. |
| 92 |
The approximation of PathImage make a list (Complete Q2), ie a list |
| 93 |
of points in the real plane. Those points still need to be approximated |
| 94 |
by rational numbers, which map approximate does. *) |
| 95 |
Definition PlotPath : positive * positive * Q * sparse_raster n m |
| 96 |
:= (n, m, 2#1, |
| 97 |
sparse_raster_data n m |
| 98 |
(map |
| 99 |
(fun x : Z => |
| 100 |
rasterize2 n m t l b r |
| 101 |
((let (approximate, _) := |
| 102 |
path |
| 103 |
(from + |
| 104 |
(to - from) * (2 * x + 1 # 1) / |
| 105 |
(2 * |
| 106 |
Z.pos |
| 107 |
(Z.to_pos |
| 108 |
(Qceiling |
| 109 |
((to - from) / |
| 110 |
(inject_Z 2 * |
| 111 |
proj1_sig (FinEnum_map_modulus (1 # 1) (mu path) err))))) |
| 112 |
# 1)) in |
| 113 |
approximate) err)) |
| 114 |
(iterateN_succ 0 |
| 115 |
(Z.to_pos |
| 116 |
(Qceiling |
| 117 |
((to - from) / |
| 118 |
(inject_Z 2 * proj1_sig (FinEnum_map_modulus (1 # 1) (mu path) err)))))))). |
| 119 |
|
| 120 |
Definition PlotPath_slow : positive * positive * Q * sparse_raster n m |
| 121 |
:= (n, m, 2#1, |
| 122 |
RasterizeQ2 |
| 123 |
(map (fun x : Q_as_MetricSpace => approximate (path x) err) |
| 124 |
(approximate (CompactIntervalQ Hfromto) |
| 125 |
(FinEnum_map_modulus (1 # 1) (mu path) err))) |
| 126 |
n m t l b r). |
| 127 |
|
| 128 |
Lemma PlotPath_correct : eq PlotPath PlotPath_slow. |
| 129 |
Proof. |
| 130 |
unfold PlotPath, PlotPath_slow, RasterizeQ2. |
| 131 |
rewrite map_map. |
| 132 |
unfold CompactIntervalQ, approximate. |
| 133 |
unfold CompactIntervalQ_raw, UniformPartition. |
| 134 |
rewrite map_map. |
| 135 |
reflexivity. |
| 136 |
Qed. |
| 137 |
|
| 138 |
End PlotPath. |
| 139 |
|
| 140 |
|
| 141 |
Lemma plFEQ : PrelengthSpace (FinEnum Q_as_MetricSpace). |
| 142 |
Proof. |
| 143 |
apply FinEnum_prelength. |
| 144 |
apply locatedQ. |
| 145 |
apply QPrelengthSpace. |
| 146 |
Qed. |
| 147 |
|
| 148 |
|
| 149 |
Section Plot. |
| 150 |
|
| 151 |
Variable (l b:Q). |
| 152 |
Variable w h:Qpos. |
| 153 |
|
| 154 |
Let r:=l+proj1_sig w. |
| 155 |
Let t:=b+proj1_sig h. |
| 156 |
|
| 157 |
Let clip := uc_compose (boundBelow b) (boundAbove t). |
| 158 |
|
| 159 |
Variable f : Q_as_MetricSpace --> CR. |
| 160 |
|
| 161 |
Lemma lrle : l <= r. |
| 162 |
Proof. |
| 163 |
rewrite <- (Qplus_0_r l). |
| 164 |
unfold r. apply Qplus_le_r, Qpos_nonneg. |
| 165 |
Qed. |
| 166 |
|
| 167 |
Definition graphQ f : Compact Q2 |
| 168 |
:= CompactGraph_b f plFEQ (CompactIntervalQ lrle). |
| 169 |
|
| 170 |
Lemma graphQ_bonus : forall e x y, |
| 171 |
In (x, y) (approximate (graphQ (uc_compose clip f)) e) |
| 172 |
-> l <= x <= r /\ b <= y <= t. |
| 173 |
Proof. |
| 174 |
intros [e|] x y;[|intros; contradiction]. |
| 175 |
simpl. |
| 176 |
unfold Cjoin_raw. |
| 177 |
Opaque CompactIntervalQ. |
| 178 |
simpl. |
| 179 |
unfold FinCompact_raw. |
| 180 |
rewrite map_map. |
| 181 |
rewrite -> in_map_iff. |
| 182 |
unfold graphPoint_b_raw; simpl. |
| 183 |
unfold Couple_raw; simpl. |
| 184 |
intros [z [Hz0 Hz1]]. |
| 185 |
inversion Hz0. |
| 186 |
subst x. subst y. |
| 187 |
clear Hz0. |
| 188 |
split. |
| 189 |
eapply CompactIntervalQ_bonus_correct. |
| 190 |
apply Hz1. |
| 191 |
split. apply Qmax_ub_l. |
| 192 |
apply Qmax_lub. |
| 193 |
rewrite <- (Qplus_0_r b). |
| 194 |
unfold t. apply Qplus_le_r, Qpos_nonneg. |
| 195 |
apply Qmin_lb_l. |
| 196 |
Qed. |
| 197 |
|
| 198 |
Variable n m : positive. (* Number of horizontal and vertical pixels *) |
| 199 |
|
| 200 |
Let err := Qpos_max ((1 # 4 * n) * w) |
| 201 |
((1 # 4 * m) * h). |
| 202 |
|
| 203 |
(** [PlotQ] is the function that computes the pixels. *) |
| 204 |
Definition PlotQ : sparse_raster n m |
| 205 |
:= RasterizeQ2 (approximate (graphQ (uc_compose clip f)) err) n m t l b r. |
| 206 |
|
| 207 |
Local Open Scope raster. |
| 208 |
|
| 209 |
(** The resulting plot is close to the graph of [f] *) |
| 210 |
Theorem Plot_correct : |
| 211 |
@ball (Compact Q2) |
| 212 |
(proj1_sig (err + Qpos_max ((1 # 2 * n) * w) ((1 # 2 * m) * h))%Qpos) |
| 213 |
(graphQ (uc_compose clip f)) |
| 214 |
(Cunit (CentersOfPixels (PixelizeQ2 PlotQ) (l,t) (r,b))). |
| 215 |
Proof. |
| 216 |
apply ball_triangle with (Cunit (approximate (graphQ (uc_compose clip f)) err)). |
| 217 |
apply ball_approx_r. |
| 218 |
unfold Compact. |
| 219 |
rewrite -> ball_Cunit. |
| 220 |
apply ball_sym. |
| 221 |
split. apply Qpos_nonneg. |
| 222 |
apply RasterizeQ2_correct. |
| 223 |
intros. |
| 224 |
destruct (InStrengthen H) as [[zx xy] [Hz0 [Hz1 Hz2]]]. |
| 225 |
simpl in Hz1, Hz2. |
| 226 |
apply Qball_0 in Hz1. |
| 227 |
apply Qball_0 in Hz2. |
| 228 |
rewrite -> Hz1, Hz2. |
| 229 |
eapply graphQ_bonus. |
| 230 |
apply Hz0. |
| 231 |
Qed. |
| 232 |
|
| 233 |
End Plot. |
| 234 |
|
| 235 |
(** Some nice notation for the graph of f. *) |
| 236 |
Notation "'graphCR' f [ l '..' r ]" := |
| 237 |
(graphQ l r (refl_equal _) f) (f at level 0) : raster. |
| 238 |
|
| 239 |
(* |
| 240 |
(* Some graph examples *) |
| 241 |
Local Open Scope raster. (* enables pretty printing of rasters *) |
| 242 |
Definition id_raster : raster _ _ |
| 243 |
:= PlotQ 0 1 eq_refl 0 1 eq_refl (@Cunit Q_as_MetricSpace) 30 30. |
| 244 |
Compute id_raster. |
| 245 |
|
| 246 |
Require Import CoRN.reals.fast.CRexp. |
| 247 |
Definition exp_raster |
| 248 |
:= PlotQ (-2) 1 eq_refl 0 3 eq_refl (exp_bound_uc 3) 30 30. |
| 249 |
Compute exp_raster. |
| 250 |
*) |
| 251 |
|
| 252 |
(* Difficult to make tail-recursive, because the current vector |
| 253 |
has no clear size to declare. Vector.map is not tail-recursive either. *) |
| 254 |
Fixpoint PlotLine (A : CR*CR -> Prop) (i:nat) |
| 255 |
(r step:Q) (y : CR) (d e:Q) (ltde : d < e) |
| 256 |
(loc : LocatedSubset (ProductMS CR CR) A) |
| 257 |
{ struct i } |
| 258 |
: list bool := |
| 259 |
match i with |
| 260 |
| O => nil |
| 261 |
| S p => |
| 262 |
cons (let xi := inject_Q_CR (r - inject_Z (Z.of_nat i) * step)%Q in |
| 263 |
if loc d e (xi,y) ltde then false else true) |
| 264 |
(PlotLine A p r step y d e ltde loc) |
| 265 |
end. |
| 266 |
|
| 267 |
Fixpoint PlotSubset_fix (A : CR*CR -> Prop) (n j:nat) |
| 268 |
(b r stepX stepY:Q) (d e:Q) (ltde : d < e) |
| 269 |
(loc : LocatedSubset (ProductMS CR CR) A) |
| 270 |
{ struct j } |
| 271 |
: list (list bool) := |
| 272 |
match j with |
| 273 |
| O => nil |
| 274 |
| S p => let yj := inject_Q_CR (b + inject_Z (Z.of_nat j) * stepY)%Q in |
| 275 |
cons (PlotLine A n r stepX yj d e ltde loc) |
| 276 |
(PlotSubset_fix A n p b r stepX stepY d e ltde loc) |
| 277 |
end. |
| 278 |
|
| 279 |
Definition PlotRadius (n m : positive) (t l b r : Q) : Q |
| 280 |
:= Qmax ((r-l) * (1#n))%Q |
| 281 |
((t-b) * (1#m))%Q. |
| 282 |
|
| 283 |
Lemma PlotRadiusInc |
| 284 |
: forall n m t l b r, |
| 285 |
l < r -> (1#2) * PlotRadius n m t l b r < PlotRadius n m t l b r. |
| 286 |
Proof. |
| 287 |
intros. rewrite <- (Qmult_1_l (PlotRadius n m t l b r)) at 2. |
| 288 |
apply Qmult_lt_r. |
| 289 |
2: reflexivity. apply (Qlt_le_trans _ ((r-l) * (1#n))%Q). |
| 290 |
apply Qlt_minus_iff in H. |
| 291 |
apply (Qpos_ispos (exist _ _ H * (1 # n))). |
| 292 |
apply Qmax_ub_l. |
| 293 |
Qed. |
| 294 |
|
| 295 |
Definition PlotSubset {A : CR*CR -> Prop} (n m : positive) (t l b r : Q) |
| 296 |
(ltlr : l < r) (loc : LocatedSubset (ProductMS CR CR) A) |
| 297 |
: raster n m |
| 298 |
:= let stepX := ((r-l) * (1#n))%Q in |
| 299 |
let stepY := ((t-b) * (1#m))%Q in |
| 300 |
(* A pixel is a square ball and its radius it half its side. *) |
| 301 |
raster_data |
| 302 |
_ _ |
| 303 |
(PlotSubset_fix A (Pos.to_nat n) (Pos.to_nat m) (b-(1#2)*stepY) (r+(1#2)*stepX) |
| 304 |
stepX stepY _ _ |
| 305 |
(PlotRadiusInc n m t l b r ltlr) loc). |
| 306 |
|
| 307 |
(* |
| 308 |
Definition PlotDiagLocated := (PlotSubset |
| 309 |
10 10 (1#1) (0#1) (0#1) (1#1) eq_refl |
| 310 |
(undistrib_Located (CompactIsLocated |
| 311 |
_ (graphQ 0 1 eq_refl (@Cunit Q_as_MetricSpace)) |
| 312 |
(ProductMS_located locatedQ locatedQ)))). |
| 313 |
Local Open Scope raster. (* enables pretty printing of rasters *) |
| 314 |
Time Eval vm_compute in PlotDiagLocated. |
| 315 |
*) |
| 316 |
|
| 317 |
|
| 318 |
(* The blank pixels have no points of the subset, in other words |
| 319 |
the filled pixels cover the subset. *) |
| 320 |
Lemma PlotLine_blank |
| 321 |
: forall (A : CR*CR -> Prop) (n i:nat) (ltni : (n < i)%nat) |
| 322 |
(r step:Q) (x y z : CR) (d e:Q) (ltde : d < e) |
| 323 |
(loc : LocatedSubset (ProductMS CR CR) A), |
| 324 |
ball d x (inject_Q_CR (r - inject_Z (Z.of_nat (i-n)) * step)%Q) |
| 325 |
-> ball d y z |
| 326 |
-> nth n (PlotLine A i r step y d e ltde loc) false = false |
| 327 |
-> ~A (x,z). |
| 328 |
Proof. |
| 329 |
induction n. |
| 330 |
- intros. intro abs. |
| 331 |
destruct i. exfalso; inversion ltni. |
| 332 |
simpl in H1. |
| 333 |
destruct (loc d e |
| 334 |
(@pair (@RegularFunction Q Qball) (@RegularFunction Q Qball) |
| 335 |
(inject_Q_CR |
| 336 |
(Qminus r (Qmult (inject_Z (Zpos (Pos.of_succ_nat i))) step))) y) |
| 337 |
ltde). |
| 338 |
2: discriminate. clear H1. |
| 339 |
specialize (n (x,z) abs). |
| 340 |
contradict n. split. |
| 341 |
+ unfold fst. |
| 342 |
apply ball_sym. |
| 343 |
exact H. |
| 344 |
+ exact H0. |
| 345 |
- intros. intro abs. |
| 346 |
destruct i. inversion ltni. simpl in H1. |
| 347 |
revert abs. |
| 348 |
refine (IHn i (proj2 (Nat.succ_lt_mono n i) ltni) r step x y z d e |
| 349 |
ltde loc _ H0 H1). |
| 350 |
replace (i-n)%nat with (S i - S n)%nat by reflexivity. |
| 351 |
exact H. |
| 352 |
Qed. |
| 353 |
|
| 354 |
Lemma PlotSubset_fix_blank |
| 355 |
: forall (A : CR*CR -> Prop) (x y : CR) (i j n m:nat) |
| 356 |
(ltin : (i < n)%nat) (ltjm : (j < m)%nat) |
| 357 |
(b r stepX stepY:Q) (d e:Q) (ltde : d < e) |
| 358 |
(loc : LocatedSubset (ProductMS CR CR) A), |
| 359 |
ball d x (inject_Q_CR (r - inject_Z (Z.of_nat (n-i)) * stepX)%Q) |
| 360 |
-> ball d y (inject_Q_CR (b + inject_Z (Z.of_nat (m-j)) * stepY)%Q) |
| 361 |
-> nth i |
| 362 |
(nth j (PlotSubset_fix A n m b r stepX stepY |
| 363 |
d e ltde loc) |
| 364 |
nil) |
| 365 |
false = false |
| 366 |
-> ~A (x,y). |
| 367 |
Proof. |
| 368 |
induction j. |
| 369 |
- intros. intro abs. |
| 370 |
destruct m. exfalso; inversion ltjm. |
| 371 |
simpl in H1. |
| 372 |
refine (PlotLine_blank |
| 373 |
A i n ltin r stepX x |
| 374 |
(' (b + inject_Z (Z.pos (Pos.of_succ_nat m)) * stepY)%Q)%CR |
| 375 |
y d e ltde loc H _ H1 abs). |
| 376 |
apply ball_sym. |
| 377 |
exact H0. |
| 378 |
- intros. intro abs. |
| 379 |
destruct m. inversion ltjm. |
| 380 |
simpl in H1. |
| 381 |
apply (IHj n m ltin (proj2 (Nat.succ_lt_mono j m) ltjm) b r stepX stepY |
| 382 |
d e ltde loc H H0 H1 abs). |
| 383 |
Qed. |
| 384 |
|
| 385 |
Lemma PlotSubset_blank |
| 386 |
: forall {A : CR*CR -> Prop} (i j : nat) (n m : positive) (t l b r : Q) (x y : CR) |
| 387 |
(ltin : (i < Pos.to_nat n)%nat) (ltjm : (j < Pos.to_nat m)%nat) (ltlr : l < r) |
| 388 |
(loc : LocatedSubset (ProductMS CR CR) A), |
| 389 |
RasterIndex (PlotSubset n m t l b r ltlr loc) j i = false |
| 390 |
-> let stepX := ((r-l) * (1#n))%Q in |
| 391 |
let stepY := ((t-b) * (1#m))%Q in |
| 392 |
ball ((1#2)*(Qmax stepX stepY)) x |
| 393 |
(inject_Q_CR (l + (inject_Z (Z.of_nat i) + (1#2)) * stepX)%Q) |
| 394 |
-> ball ((1#2)*(Qmax stepX stepY)) y |
| 395 |
(inject_Q_CR (t - (inject_Z (Z.of_nat j) + (1#2)) * stepY)%Q) |
| 396 |
-> ~A (x,y). |
| 397 |
Proof. |
| 398 |
intros. |
| 399 |
setoid_replace (l + (inject_Z (Z.of_nat i)+(1#2)) * stepX)%Q |
| 400 |
with ((r + (1#2)*stepX) - inject_Z (Z.of_nat (Pos.to_nat n - i)) * stepX)%Q |
| 401 |
in H0. |
| 402 |
setoid_replace (t - (inject_Z (Z.of_nat j) + (1#2)) * stepY)%Q |
| 403 |
with ((b-(1#2)*stepY) + inject_Z (Z.of_nat (Pos.to_nat m - j)) * stepY)%Q |
| 404 |
in H1. |
| 405 |
exact (PlotSubset_fix_blank |
| 406 |
A x y i j (Pos.to_nat n) (Pos.to_nat m) ltin ltjm |
| 407 |
_ _ stepX stepY |
| 408 |
((1#2)*(Qmax stepX stepY)) |
| 409 |
(Qmax stepX stepY) |
| 410 |
(PlotRadiusInc n m t l b r ltlr) loc |
| 411 |
H0 H1 H). |
| 412 |
- unfold canonical_names.equiv, stdlib_rationals.Q_eq. |
| 413 |
rewrite Nat2Z.inj_sub. |
| 414 |
unfold Zminus. rewrite Q.Zplus_Qplus, inject_Z_opp. |
| 415 |
rewrite <- (Qplus_inj_r _ _ ((inject_Z (Z.of_nat j)+(1#2)) * stepY)). |
| 416 |
ring_simplify. |
| 417 |
rewrite positive_nat_Z. |
| 418 |
unfold stepY. |
| 419 |
rewrite <- Qmult_assoc. |
| 420 |
setoid_replace ((1 # m) * inject_Z (Z.pos m)) with 1%Q by reflexivity. |
| 421 |
rewrite Qmult_1_r. ring. |
| 422 |
apply (Nat.le_trans _ (S j)). |
| 423 |
apply le_S, Nat.le_refl. exact ltjm. |
| 424 |
- unfold canonical_names.equiv, stdlib_rationals.Q_eq. |
| 425 |
rewrite Nat2Z.inj_sub. |
| 426 |
unfold Zminus. rewrite Q.Zplus_Qplus, inject_Z_opp. |
| 427 |
rewrite positive_nat_Z. |
| 428 |
rewrite <- (Qplus_inj_r _ _ (stepX * inject_Z (Z.pos n) |
| 429 |
-inject_Z (Z.of_nat i) * stepX |
| 430 |
- (1#2)*stepX)). |
| 431 |
ring_simplify. |
| 432 |
unfold stepX. |
| 433 |
rewrite <- Qmult_assoc. |
| 434 |
setoid_replace ((1 # n) * inject_Z (Z.pos n)) with 1%Q by reflexivity. |
| 435 |
rewrite Qmult_1_r. ring. |
| 436 |
apply (Nat.le_trans _ (S i)). |
| 437 |
apply le_S, Nat.le_refl. exact ltin. |
| 438 |
Qed. |