Debian Codegraph @

Formal_ineqs/trig/matan.hl

raw
1 (* ========================================================================== *)
2 (* Formal verification of nonlinear inequalities in HOL Light *)
3 (* *)
4 (* Copyright (c) 2014 Alexey Solovyev *)
5 (* *)
6 (* This file is distributed under the terms of the MIT licence *)
7 (* ========================================================================== *)
8
9 (* -------------------------------------------------------------------------- *)
10 (* Formal interval evaluation of functions: matan (theory) *)
11 (* -------------------------------------------------------------------------- *)
12
13 needs "Formal_ineqs/trig/series.hl";;
14
15 module Matan = struct
16
17 open Series;;
18
19 prioritize_real();;
20
21 (* matan *)
22
23 let matan = new_definition `matan x =
24 if (x = &0) then &1
25 else if (x > &0) then atn (sqrt x) / (sqrt x)
26 else (log ((&1 + sqrt( -- x))/(&1 - sqrt( -- x)))) / (&2 * sqrt (-- x))`;;
27
28 (* Auxiliary definitions for matan derivatives *)
29
30 let dmatan = new_definition `dmatan = real_derivative matan`;;
31
32 let ddmatan = new_definition `ddmatan = real_derivative (real_derivative matan)`;;
33
34
35 let log_matan_series = prove(`!x. abs x < &1 /\ ~(x = &0)
36 ==> ((\k. x pow (2 * k) / &(2 * k + 1))
37 real_sums log ((&1 + x) / (&1 - x)) / (&2 * x)) (:num)`,
38 REPEAT STRIP_TAC THEN
39 MATCH_MP_TAC REAL_SUMS_EQ THEN REWRITE_TAC[IN_UNIV] THEN
40 EXISTS_TAC `\k. x pow (2 * k + 1) / &(2 * k + 1) * inv x` THEN
41 CONJ_TAC THENL [
42 X_GEN_TAC `k:num` THEN REWRITE_TAC[REAL_POW_ADD; REAL_POW_1] THEN
43 ONCE_REWRITE_TAC[REAL_ARITH `(a * x) / b * inv x = (x * inv x) * a / b:real`] THEN
44 ASM_SIMP_TAC[REAL_MUL_RINV; REAL_MUL_LID];
45 ALL_TAC
46 ] THEN
47 REWRITE_TAC[real_div; REAL_INV_MUL; REAL_MUL_ASSOC] THEN
48 MATCH_MP_TAC REAL_SERIES_RMUL THEN REWRITE_TAC[GSYM real_div] THEN
49 ABBREV_TAC `f = \x:real. log ((&1 + x) / (&1 - x)) / &2` THEN
50 MP_TAC (SPECL[`f:real->real`; `\x:real. inv (&1 - x pow 2)`; `\i. if EVEN i then &1 else &0`; `(:num)`; `&1`] power_series_integral2) THEN
51 ANTS_TAC THENL [
52 CONJ_TAC THEN X_GEN_TAC `t:real` THEN DISCH_TAC THEN REWRITE_TAC[] THENL [
53 EXPAND_TAC "f" THEN REAL_DIFF_TAC THEN
54 CONJ_TAC THENL [
55 ASM_SIMP_TAC[REAL_ARITH `abs t < &1 ==> ~(&1 - t = &0)`] THEN
56 MATCH_MP_TAC REAL_LT_DIV THEN POP_ASSUM MP_TAC THEN REAL_ARITH_TAC;
57 ALL_TAC
58 ] THEN
59 POP_ASSUM MP_TAC THEN CONV_TAC REAL_FIELD;
60 ALL_TAC
61 ] THEN
62 REWRITE_TAC[COND_RAND; COND_RATOR; REAL_MUL_LZERO; real_sums_image_even; FROM_0] THEN
63 MP_TAC (SPECL[`0`; `t:real pow 2`] REAL_SUMS_GP) THEN
64 ANTS_TAC THENL [
65 REWRITE_TAC[REAL_ABS_MUL; REAL_ABS_POW; REAL_ARITH `abs (-- &1) = &1`; REAL_MUL_LID] THEN
66 ASM_REWRITE_TAC[ABS_SQUARE_LT_1; REAL_ABS_ABS];
67 ALL_TAC
68 ] THEN
69 REWRITE_TAC[real_pow; real_div; REAL_MUL_LID; REAL_POW_POW; FROM_0; MULT_0];
70 ALL_TAC
71 ] THEN
72 DISCH_THEN (MP_TAC o SPEC `x:real`) THEN ASM_REWRITE_TAC[] THEN
73 REWRITE_TAC[COND_RAND; COND_RATOR; REAL_MUL_LZERO; real_sums_image_even; REAL_MUL_LID] THEN
74 SUBGOAL_THEN `f (&0) = &0` (fun th -> REWRITE_TAC[th; REAL_SUB_RZERO]) THENL [
75 EXPAND_TAC "f" THEN REWRITE_TAC[REAL_ADD_RID; REAL_SUB_RZERO; real_div; REAL_MUL_LID; REAL_INV_1; LOG_1; REAL_MUL_LZERO];
76 ALL_TAC
77 ] THEN
78 EXPAND_TAC "f" THEN REWRITE_TAC[]);;
79
80
81 (* matan power series *)
82
83 let matan_power_series = prove(`!x. abs x < &1
84 ==> ((\k. ((-- &1) pow k / &(2 * k + 1)) * x pow k)
85 real_sums matan x) (:num)`,
86 REPEAT STRIP_TAC THEN REWRITE_TAC[matan] THEN
87 ASM_CASES_TAC `x = &0` THEN ASM_REWRITE_TAC[] THENL [
88 ABBREV_TAC `h = \k. -- &1 pow k / &(2 * k + 1) * &0 pow k` THEN
89 SUBGOAL_THEN `h 0 = &1 /\ (!i. 1 <= i ==> h i = &0)` ASSUME_TAC THENL [
90 EXPAND_TAC "h" THEN REWRITE_TAC[REAL_POW_ZERO; real_pow; MULT_0; ADD] THEN
91 CONJ_TAC THENL [ REAL_ARITH_TAC; ALL_TAC ] THEN
92 GEN_TAC THEN COND_CASES_TAC THEN ASM_SIMP_TAC[ARITH_RULE `1 <= i ==> ~(i = 0)`; ARITH_RULE `~(1 <= 0)`; REAL_MUL_RZERO];
93 ALL_TAC
94 ] THEN
95 SUBGOAL_THEN `&1 = &0 + sum(0..1 - 1) h` (fun th -> REWRITE_TAC[th]) THENL [
96 ASM_REWRITE_TAC[SUB_REFL; SUM_SING_NUMSEG; REAL_ADD_LID];
97 ALL_TAC
98 ] THEN
99 REWRITE_TAC[GSYM FROM_0] THEN MATCH_MP_TAC REAL_SUMS_OFFSET_REV THEN
100 REWRITE_TAC[ARITH_RULE `0 < 1`] THEN
101 MATCH_MP_TAC REAL_SUMS_EQ THEN
102 EXISTS_TAC `\i:num. &0` THEN
103 ASM_SIMP_TAC[REAL_SERIES_0; IN_FROM];
104 ALL_TAC
105 ] THEN
106 ASM_CASES_TAC `x > &0` THENL [
107 ASM_REWRITE_TAC[] THEN
108 SUBGOAL_THEN `!y. y > &0 /\ y < &1 ==> ((\k. -- &1 pow k / &(2 * k + 1) * (y pow 2) pow k) real_sums atn y / y) (:num)` MP_TAC THENL [
109 REPEAT STRIP_TAC THEN
110 MATCH_MP_TAC REAL_SUMS_EQ THEN REWRITE_TAC[IN_UNIV] THEN
111 EXISTS_TAC `\k. (-- &1 pow k / &(2 * k + 1) * y pow (2 * k + 1)) * inv y` THEN
112 CONJ_TAC THENL [
113 X_GEN_TAC `k:num` THEN REWRITE_TAC[REAL_POW_ADD; REAL_POW_1; GSYM REAL_MUL_ASSOC; REAL_POW_POW] THEN
114 ASM_SIMP_TAC[REAL_ARITH `y > &0 ==> ~(y = &0)`; REAL_MUL_RINV; REAL_MUL_RID];
115 ALL_TAC
116 ] THEN
117 REWRITE_TAC[real_div] THEN
118 MATCH_MP_TAC REAL_SERIES_RMUL THEN REWRITE_TAC[GSYM real_div] THEN
119 MATCH_MP_TAC atn_series THEN POP_ASSUM MP_TAC THEN POP_ASSUM MP_TAC THEN REAL_ARITH_TAC;
120 ALL_TAC
121 ] THEN
122 DISCH_THEN (MP_TAC o SPEC `sqrt x`) THEN ANTS_TAC THENL [
123 ASM_REWRITE_TAC[real_gt; SQRT_LT_0; REAL_ARITH `&0 < x <=> x > &0`] THEN
124 MATCH_MP_TAC REAL_LT_LSQRT THEN
125 REPEAT (POP_ASSUM MP_TAC) THEN REAL_ARITH_TAC;
126 ALL_TAC
127 ] THEN
128 SUBGOAL_THEN `sqrt x pow 2 = x` (fun th -> REWRITE_TAC[th]) THEN
129 ASM_REWRITE_TAC[SQRT_POW2] THEN POP_ASSUM MP_TAC THEN REAL_ARITH_TAC;
130 ALL_TAC
131 ] THEN
132 ASM_REWRITE_TAC[] THEN
133 MP_TAC (SPEC `sqrt (--x:real)` log_matan_series) THEN ANTS_TAC THENL [
134 ASM_REWRITE_TAC[SQRT_EQ_0; REAL_NEG_EQ_0] THEN
135 ONCE_REWRITE_TAC[REAL_ARITH `&1 = abs(&1)`] THEN REWRITE_TAC[REAL_LT_SQUARE_ABS] THEN
136 REWRITE_TAC[REAL_SQRT_POW_2] THEN REPEAT (POP_ASSUM MP_TAC) THEN REAL_ARITH_TAC;
137 ALL_TAC
138 ] THEN
139 REWRITE_TAC[GSYM REAL_POW_POW; REAL_SQRT_POW_2] THEN
140 ASM_SIMP_TAC[REAL_ARITH `~(x > &0) ==> abs (--x) = --x`] THEN
141 ONCE_REWRITE_TAC[REAL_NEG_MINUS1] THEN
142 REWRITE_TAC[REAL_POW_MUL; REAL_POW_ONE; REAL_MUL_RID; real_div; REAL_MUL_AC]);;
143
144
145 (* matan bounds *)
146
147 let matan_abs1_bound = prove(`!m x. abs x < &1 ==>
148 abs (matan x - sum (0..m) (\k. ((-- &1) pow k / &(2 * k + 1)) * x pow k))
149 <= abs x pow (SUC m) / (&(2 * m + 3) * (&1 - abs x))`,
150 REPEAT STRIP_TAC THEN
151 REWRITE_TAC[real_div; REAL_INV_MUL; REAL_ARITH `a * inv(c) * b = inv(c) * (a * b)`] THEN
152 REWRITE_TAC[GSYM real_div] THEN
153 SUBGOAL_THEN `!f. sum (0..m) f = sum (0..SUC m - 1) f` (fun th -> ONCE_REWRITE_TAC[th]) THENL [
154 REWRITE_TAC[ARITH_RULE `SUC m - 1 = m`];
155 ALL_TAC
156 ] THEN
157 SUBGOAL_THEN `inv (&(2 * m + 3)) = abs ((\k. ((-- &1) pow k / &(2 * k + 1))) (SUC m))` (fun th -> ONCE_REWRITE_TAC[th]) THENL [
158 REWRITE_TAC[real_div; REAL_ABS_MUL; REAL_POW_NEG; REAL_POW_ONE] THEN
159 REWRITE_TAC[COND_RAND; REAL_ARITH `abs (-- &1) = &1`; REAL_ABS_NUM; COND_ID] THEN
160 REWRITE_TAC[REAL_MUL_LID; REAL_ABS_INV; REAL_ABS_NUM; ARITH_RULE `2 * SUC m + 1 = 2 * m + 3`];
161 ALL_TAC
162 ] THEN
163 MP_TAC (SPECL[`\k. -- &1 pow k / &(2 * k + 1)`; `matan x`; `x:real`; `0`; `SUC m`] real_sums_simple_bound2) THEN
164 ASM_REWRITE_TAC[ARITH_RULE `0 < SUC m`] THEN
165 DISCH_THEN MATCH_MP_TAC THEN
166 CONJ_TAC THENL [
167 ASM_SIMP_TAC[matan_power_series; FROM_0];
168 ALL_TAC
169 ] THEN
170 REPEAT STRIP_TAC THEN
171 REWRITE_TAC[real_div; REAL_ABS_MUL; REAL_POW_NEG; REAL_POW_ONE] THEN
172 REWRITE_TAC[COND_RAND; REAL_ARITH `abs (-- &1) = &1`; REAL_ABS_NUM; COND_ID] THEN
173 REWRITE_TAC[REAL_MUL_LID; REAL_ABS_INV; REAL_ABS_NUM; ARITH_RULE `2 * SUC m + 1 = 2 * m + 3`] THEN
174 MATCH_MP_TAC REAL_LE_INV2 THEN
175 REWRITE_TAC[REAL_OF_NUM_LT; REAL_OF_NUM_LE] THEN
176 ARITH_TAC);;
177
178
179 (* matan first derivative *)
180
181 let matan_has_derivative_gt0 = prove(`!x. &0 < x ==>
182 (matan has_real_derivative (inv (&2 * x * (x + &1)) - atn(sqrt(x)) / (&2 * x * sqrt(x))))
183 (atreal x)`,
184 REPEAT STRIP_TAC THEN
185 MATCH_MP_TAC HAS_REAL_DERIVATIVE_TRANSFORM_ATREAL THEN
186 MAP_EVERY EXISTS_TAC [`\x. atn(sqrt(x)) / sqrt(x)`; `x:real`] THEN
187 REPEAT CONJ_TAC THEN ASM_REWRITE_TAC[] THENL [
188 REPEAT STRIP_TAC THEN
189 SUBGOAL_THEN `~(x' = &0) /\ x' > &0` ASSUME_TAC THENL [
190 REPEAT (POP_ASSUM MP_TAC) THEN REAL_ARITH_TAC;
191 ALL_TAC
192 ] THEN
193 ASM_REWRITE_TAC[matan];
194 ALL_TAC
195 ] THEN
196 REAL_DIFF_TAC THEN
197 SUBGOAL_THEN `~(sqrt x = &0)` ASSUME_TAC THENL [
198 ASM_SIMP_TAC[SQRT_EQ_0; REAL_ARITH `&0 < x ==> ~(x = &0)`];
199 ALL_TAC
200 ] THEN
201 ASM_SIMP_TAC[SQRT_POW_2; REAL_ARITH `&0 < x ==> &0 <= x`] THEN
202 REPEAT (POP_ASSUM MP_TAC) THEN
203 CONV_TAC REAL_FIELD);;
204
205
206 let matan_real_derivative_gt0 = prove(`!x. &0 < x ==>
207 real_derivative matan x = inv (&2 * x * (x + &1)) - atn(sqrt(x)) / (&2 * x * sqrt(x))`,
208 REPEAT STRIP_TAC THEN
209 MATCH_MP_TAC HAS_REAL_DERIVATIVE_DERIVATIVE THEN
210 ASM_SIMP_TAC[matan_has_derivative_gt0]);;
211
212
213 let matan_real_derivative_abs1 = prove(`!x. abs x < &1 ==>
214 matan real_differentiable atreal x
215 /\ ((\i. ((-- &1) pow (SUC i) * &(SUC i) / &(2 * i + 3)) * x pow i)
216 real_sums (real_derivative matan x)) (from 0)`,
217 GEN_TAC THEN DISCH_TAC THEN
218 MP_TAC (MATCH_MP power_series_has_derivative2 matan_power_series) THEN
219 STRIP_TAC THEN POP_ASSUM (MP_TAC o SPEC `x:real`) THEN ASM_REWRITE_TAC[] THEN STRIP_TAC THEN
220 CONJ_TAC THENL [
221 REWRITE_TAC[real_differentiable] THEN
222 EXISTS_TAC `(f':real->real) x` THEN ASM_REWRITE_TAC[];
223 ALL_TAC
224 ] THEN
225 SUBGOAL_THEN `real_derivative matan x = f' x` (fun th -> REWRITE_TAC[th]) THENL [
226 MATCH_MP_TAC HAS_REAL_DERIVATIVE_DERIVATIVE THEN ASM_REWRITE_TAC[];
227 ALL_TAC
228 ] THEN
229 REWRITE_TAC[FROM_0; ARITH_RULE `2 * i + 3 = 2 * SUC i + 1`] THEN
230 ONCE_REWRITE_TAC[REAL_ARITH `a * b / c = b * a / c`] THEN
231 ASM_REWRITE_TAC[]);;
232
233
234 let matan_real_derivative_abs1_bound = prove(`!x m. abs x < &1 ==>
235 abs (real_derivative matan x
236 - sum (0..m) (\i. ((-- &1) pow (SUC i) * &(SUC i) / &(2 * i + 3)) * x pow i))
237 <= abs x pow (SUC m) / (&2 * (&1 - abs x))`,
238 REPEAT STRIP_TAC THEN
239 REWRITE_TAC[real_div; REAL_INV_MUL; REAL_ARITH `a * inv(&2) * b = inv(&2) * (a * b)`] THEN
240 REWRITE_TAC[GSYM real_div] THEN
241 SUBGOAL_THEN `!f. sum (0..m) f = sum (0..SUC m - 1) f` (fun th -> ONCE_REWRITE_TAC[th]) THENL [
242 REWRITE_TAC[ARITH_RULE `SUC m - 1 = m`];
243 ALL_TAC
244 ] THEN
245 MATCH_MP_TAC real_sums_simple_bound THEN
246 ASM_REWRITE_TAC[ARITH_RULE `0 < SUC m`] THEN CONJ_TAC THENL [
247 ASM_SIMP_TAC[matan_real_derivative_abs1];
248 ALL_TAC
249 ] THEN
250 REPEAT STRIP_TAC THEN
251 REWRITE_TAC[REAL_ABS_MUL; REAL_POW_NEG; REAL_POW_ONE; COND_RAND; REAL_ABS_DIV] THEN
252 REWRITE_TAC[REAL_ARITH `abs (-- &1) = &1 /\ abs (&1) = &1`; COND_ID; REAL_MUL_LID] THEN
253 SUBGOAL_THEN `&0 < abs (&(2 * i + 3))` ASSUME_TAC THENL [
254 REWRITE_TAC[REAL_ABS_NUM; REAL_OF_NUM_LT] THEN ARITH_TAC;
255 ALL_TAC
256 ] THEN
257 ASM_SIMP_TAC[REAL_LE_LDIV_EQ; REAL_ABS_NUM; GSYM REAL_OF_NUM_ADD; GSYM REAL_OF_NUM_MUL] THEN
258 REWRITE_TAC[REAL_FIELD `inv (&2) * (&2 * a + b) = a + inv(&2) * b`] THEN
259 REWRITE_TAC[ADD1; GSYM REAL_OF_NUM_ADD; REAL_LE_LADD] THEN
260 REAL_ARITH_TAC);;
261
262
263 (* matan second derivative *)
264
265 let matan_has_derivative2_gt0 = prove(`!x. &0 < x ==>
266 ((\x. inv (&2 * x * (x + &1)) - atn(sqrt(x)) / (&2 * x * sqrt(x))) has_real_derivative
267 (&3 / &4) * (atn(sqrt(x)) / (x pow 2 * sqrt(x)))
268 - (&3 / &4) * inv(x pow 2 * (x + &1))
269 - (&1 / &2) * inv(x * (x + &1) pow 2)) (atreal x)`,
270 REPEAT STRIP_TAC THEN
271 MP_TAC (REAL_ARITH `&0 < x ==> ~(x = &0)`) THEN ASM_REWRITE_TAC[] THEN DISCH_TAC THEN
272 REAL_DIFF_TAC THEN
273 SUBGOAL_THEN `~(sqrt x = &0)` ASSUME_TAC THENL [ ASM_SIMP_TAC[SQRT_EQ_0]; ALL_TAC ] THEN
274 ASM_SIMP_TAC[SQRT_POW_2; REAL_ARITH `&0 < x ==> &0 <= x`; REAL_POW_MUL] THEN
275 REPEAT CONJ_TAC THEN ASM_REWRITE_TAC[REAL_ENTIRE] THENL [
276 REPEAT (POP_ASSUM MP_TAC) THEN REAL_ARITH_TAC;
277 REAL_ARITH_TAC;
278 ALL_TAC
279 ] THEN
280 REWRITE_TAC[REAL_ADD_RID; REAL_MUL_LID; REAL_MUL_RID] THEN
281 SUBGOAL_THEN `x * inv (&2 * sqrt x) + sqrt x = (&3 / &2) * x / sqrt x` (fun th -> REWRITE_TAC[th]) THENL [
282 MATCH_MP_TAC REAL_EQ_LCANCEL_IMP THEN EXISTS_TAC `sqrt x` THEN
283 ASM_REWRITE_TAC[REAL_ARITH `s * (x * inv t + s) = s * x * inv t + s pow 2`] THEN
284 ASM_SIMP_TAC[SQRT_POW_2; REAL_ARITH `&0 < x ==> &0 <= x`] THEN
285 REPEAT (POP_ASSUM MP_TAC) THEN CONV_TAC REAL_FIELD;
286 ALL_TAC
287 ] THEN
288 REPEAT (POP_ASSUM MP_TAC) THEN CONV_TAC REAL_FIELD);;
289
290 let matan_second_derivative_gt0 = prove(`!x. &0 < x ==>
291 real_derivative (real_derivative matan) x =
292 (&3 / &4) * (atn(sqrt(x)) / (x pow 2 * sqrt(x)))
293 - (&3 / &4) * inv(x pow 2 * (x + &1))
294 - (&1 / &2) * inv(x * (x + &1) pow 2)`,
295 REPEAT STRIP_TAC THEN
296 MATCH_MP_TAC HAS_REAL_DERIVATIVE_DERIVATIVE THEN
297 MATCH_MP_TAC HAS_REAL_DERIVATIVE_TRANSFORM_ATREAL THEN
298 MAP_EVERY EXISTS_TAC [`\x. inv (&2 * x * (x + &1)) - atn(sqrt(x)) / (&2 * x * sqrt(x))`; `x:real`] THEN
299 REPEAT CONJ_TAC THEN ASM_REWRITE_TAC[] THENL [
300 REPEAT STRIP_TAC THEN
301 SUBGOAL_THEN `&0 < x'` ASSUME_TAC THENL [
302 REPEAT (POP_ASSUM MP_TAC) THEN REAL_ARITH_TAC;
303 ALL_TAC
304 ] THEN
305 ASM_SIMP_TAC[matan_real_derivative_gt0];
306 ALL_TAC
307 ] THEN
308 ASM_SIMP_TAC[matan_has_derivative2_gt0]);;
309
310
311 let matan_second_derivative_abs1 = prove(`!x. abs x < &1 ==>
312 (real_derivative matan) real_differentiable atreal x
313 /\ ((\i. ((-- &1) pow (i + 2) * &((i + 1) * (i + 2)) / &(2 * i + 5)) * x pow i)
314 real_sums (real_derivative (real_derivative matan) x)) (from 0)`,
315 GEN_TAC THEN DISCH_TAC THEN
316 MP_TAC (SPECL[`real_derivative matan`; `\i. -- &1 pow SUC i * &(SUC i) / &(2 * i + 3)`; `&1`] power_series_has_derivative2) THEN
317 ANTS_TAC THENL [
318 REPEAT STRIP_TAC THEN
319 MP_TAC (SPECL[`x':real`] matan_real_derivative_abs1) THEN
320 ASM_SIMP_TAC[FROM_0];
321 ALL_TAC
322 ] THEN
323 STRIP_TAC THEN POP_ASSUM (MP_TAC o SPEC `x:real`) THEN ASM_REWRITE_TAC[] THEN STRIP_TAC THEN
324 CONJ_TAC THENL [
325 REWRITE_TAC[real_differentiable] THEN
326 EXISTS_TAC `(f':real->real) x` THEN ASM_REWRITE_TAC[];
327 ALL_TAC
328 ] THEN
329 SUBGOAL_THEN `real_derivative (real_derivative matan) x = f' x` (fun th -> REWRITE_TAC[th]) THENL [
330 MATCH_MP_TAC HAS_REAL_DERIVATIVE_DERIVATIVE THEN ASM_REWRITE_TAC[];
331 ALL_TAC
332 ] THEN
333 REWRITE_TAC[FROM_0; ARITH_RULE `i + 2 = SUC (SUC i) /\ 2 * i + 5 = 2 * SUC i + 3 /\ i + 1 = SUC i`] THEN
334 REWRITE_TAC[GSYM REAL_OF_NUM_MUL] THEN
335 ONCE_REWRITE_TAC[REAL_ARITH `a * (b * d) / c = b * a * d / c`] THEN
336 ASM_REWRITE_TAC[]);;
337
338
339 let matan_second_derivative_abs1_alt = prove(`!x. abs x < &1 ==>
340 real_derivative (real_derivative matan) x = (&1 - x) / (&4 * (&1 + x) pow 2)
341 + (&3 / &4) * real_infsum (:num) (\i. ((-- &1) pow i / &(2 * i + 5)) * x pow i)
342 /\ real_summable (:num) (\i. ((-- &1) pow i / &(2 * i + 5)) * x pow i)`,
343 GEN_TAC THEN DISCH_TAC THEN
344 FIRST_ASSUM (MP_TAC o MATCH_MP matan_second_derivative_abs1) THEN STRIP_TAC THEN
345 FIRST_ASSUM ((fun th -> REWRITE_TAC[GSYM th; FROM_0]) o MATCH_MP REAL_INFSUM_UNIQUE) THEN
346 SUBGOAL_THEN `!i. -- &1 pow (i + 2) = -- &1 pow i` (fun th -> REWRITE_TAC[th]) THENL [
347 REWRITE_TAC[REAL_POW_ADD; REAL_ARITH `-- &1 pow 2 = &1`; REAL_MUL_RID];
348 ALL_TAC
349 ] THEN
350 ASM_SIMP_TAC[REAL_FIELD `abs x < &1 ==> (&1 - x) / (&4 * (&1 + x) pow 2) = (&1 / &4) * (&1 / (&1 + x)) - (&1 / &2) * (x / (&1 + x) pow 2)`] THEN
351 ABBREV_TAC `f = \i. -- &1 pow i * x pow i` THEN
352 ABBREV_TAC `g = \i. (-- &1 pow i * &i) * x pow i` THEN
353 ABBREV_TAC `h = \i. (-- &1 pow i * (&1 / &(2 * i + 5))) * x pow i` THEN
354 SUBGOAL_THEN `!i. (-- &1 pow i * &((i + 1) * (i + 2)) / &(2 * i + 5)) * x pow i = &1 / &4 * f i + &1 / &2 * g i + &3 / &4 * h i` (fun th -> REWRITE_TAC[th]) THENL [
355 GEN_TAC THEN MAP_EVERY EXPAND_TAC ["f"; "g"; "h"] THEN
356 REWRITE_TAC[GSYM REAL_OF_NUM_MUL; GSYM REAL_OF_NUM_ADD] THEN
357 CONV_TAC REAL_FIELD;
358 ALL_TAC
359 ] THEN
360 SUBGOAL_THEN `!i. -- &1 pow i / &(2 * i + 5) * x pow i = h i` (fun th -> REWRITE_TAC[th]) THENL [
361 EXPAND_TAC "h" THEN REWRITE_TAC[real_div; REAL_MUL_LID];
362 ALL_TAC
363 ] THEN
364 MP_TAC (SPEC `x:real` real_sums_neg_xi) THEN
365 MP_TAC (SPEC `x:real` real_sums_neg_i_xi) THEN
366 ASM_REWRITE_TAC[] THEN DISCH_THEN (LABEL_TAC "a") THEN DISCH_THEN (LABEL_TAC "b") THEN
367 SUBGOAL_THEN `real_summable (:num) f /\ real_summable (:num) g /\ real_summable (:num) h` STRIP_ASSUME_TAC THENL [
368 REPEAT STRIP_TAC THEN REWRITE_TAC[real_summable] THENL [
369 EXISTS_TAC `&1 / (&1 + x)` THEN ASM_REWRITE_TAC[];
370 EXISTS_TAC `--(x / (&1 + x) pow 2)` THEN ASM_REWRITE_TAC[];
371 ALL_TAC
372 ] THEN
373 REWRITE_TAC[GSYM real_summable] THEN EXPAND_TAC "h" THEN
374 MATCH_MP_TAC REAL_SUMMABLE_COMPARISON THEN
375 EXISTS_TAC `\i. abs x pow i` THEN
376 CONJ_TAC THENL [
377 MATCH_MP_TAC REAL_SUMMABLE_GP THEN ASM_REWRITE_TAC[REAL_ABS_ABS];
378 ALL_TAC
379 ] THEN
380 EXISTS_TAC `0` THEN REPEAT STRIP_TAC THEN
381 REWRITE_TAC[REAL_ABS_MUL; abs_neg_one_pow; REAL_ABS_POW; REAL_MUL_LID] THEN
382 ONCE_REWRITE_TAC[REAL_ARITH `a <= b <=> a <= &1 * b`] THEN
383 MATCH_MP_TAC REAL_LE_RMUL THEN
384 CONJ_TAC THENL [ ALL_TAC; MATCH_MP_TAC REAL_POW_LE THEN REAL_ARITH_TAC ] THEN
385 REWRITE_TAC[REAL_ABS_DIV; REAL_ABS_1] THEN
386 REWRITE_TAC[REAL_ARITH `&1 / a <= &1 <=> inv a <= inv (&1)`] THEN
387 MATCH_MP_TAC REAL_LE_INV2 THEN
388 REWRITE_TAC[GSYM REAL_OF_NUM_ADD; GSYM REAL_OF_NUM_MUL] THEN
389 REAL_ARITH_TAC;
390 ALL_TAC
391 ] THEN
392 ASM_SIMP_TAC[REAL_INFSUM_ADD; REAL_SUMMABLE_ADD; REAL_SUMMABLE_LMUL; ETA_AX] THEN
393 ASM_SIMP_TAC[REAL_INFSUM_LMUL] THEN
394 REMOVE_THEN "a" (MP_TAC o MATCH_MP REAL_INFSUM_UNIQUE) THEN
395 REMOVE_THEN "b" (MP_TAC o MATCH_MP REAL_INFSUM_UNIQUE) THEN
396 ASM_SIMP_TAC[] THEN REAL_ARITH_TAC);;
397
398
399
400 (* matan second derivative bound *)
401
402 let matan_d2_bound_ge1_high = prove(`!x. &1 <= x ==>
403 real_derivative (real_derivative matan) x <= #0.65`,
404 REPEAT STRIP_TAC THEN
405 ASM_SIMP_TAC[REAL_ARITH `&1 <= x ==> &0 < x`; matan_second_derivative_gt0] THEN
406 MATCH_MP_TAC REAL_LE_TRANS THEN
407 EXISTS_TAC `(&3 / &4) * atn(sqrt x) / (x pow 2 * sqrt x)` THEN
408 CONJ_TAC THENL [
409 REWRITE_TAC[REAL_ARITH `a - b - c <= a <=> &0 <= b + c`] THEN
410 MATCH_MP_TAC REAL_LE_ADD THEN
411 CONJ_TAC THEN MATCH_MP_TAC REAL_LE_MUL THEN CONJ_TAC THEN TRY REAL_ARITH_TAC THENL [
412 MATCH_MP_TAC REAL_LE_INV THEN MATCH_MP_TAC REAL_LE_MUL THEN
413 REWRITE_TAC[REAL_LE_POW_2] THEN POP_ASSUM MP_TAC THEN REAL_ARITH_TAC;
414 MATCH_MP_TAC REAL_LE_INV THEN MATCH_MP_TAC REAL_LE_MUL THEN
415 REWRITE_TAC[REAL_LE_POW_2] THEN POP_ASSUM MP_TAC THEN REAL_ARITH_TAC;
416 ];
417 ALL_TAC
418 ] THEN
419 ABBREV_TAC `y = sqrt x` THEN
420 SUBGOAL_THEN `x pow 2 * y = y pow 5` (fun th -> REWRITE_TAC[th]) THENL [
421 MP_TAC (SPEC `x:real` SQRT_POW_2) THEN
422 ASM_SIMP_TAC[REAL_ARITH `&1 <= x ==> &0 <= x`] THEN
423 CONV_TAC REAL_RING;
424 ALL_TAC
425 ] THEN
426 ONCE_REWRITE_TAC[REAL_ARITH `#0.65 = (&3 / &4) * (#0.65 * &4 / &3)`] THEN
427 MATCH_MP_TAC REAL_LE_LMUL THEN CONJ_TAC THENL [ REAL_ARITH_TAC; ALL_TAC ] THEN
428 SUBGOAL_THEN `&1 <= y` ASSUME_TAC THENL [
429 EXPAND_TAC "y" THEN MATCH_MP_TAC REAL_LE_RSQRT THEN ASM_REWRITE_TAC[REAL_POW_ONE];
430 ALL_TAC
431 ] THEN
432 MATCH_MP_TAC REAL_LE_TRANS THEN
433 EXISTS_TAC `atn (&1) / (&1 pow 5)` THEN CONJ_TAC THENL [
434 ONCE_REWRITE_TAC[GSYM REAL_LE_NEG2] THEN
435 ABBREV_TAC `f = \y. --(atn y / y pow 5)` THEN
436 SUBGOAL_THEN `!x. --(atn x / x pow 5) = f x` (fun th -> REWRITE_TAC[th]) THENL [
437 EXPAND_TAC "f" THEN REWRITE_TAC[];
438 ALL_TAC
439 ] THEN
440 MATCH_MP_TAC HAS_REAL_DERIVATIVE_INCREASING_IMP THEN
441 EXISTS_TAC `\y. &5 * atn(y) / y pow 6 - inv(y pow 5 * (y pow 2 + &1))` THEN
442 EXISTS_TAC `real_interval [&1, y]` THEN
443 ASM_REWRITE_TAC[IS_REALINTERVAL_INTERVAL; IN_REAL_INTERVAL; REAL_LE_REFL] THEN
444 CONJ_TAC THENL [
445 REPEAT STRIP_TAC THEN
446 MATCH_MP_TAC HAS_REAL_DERIVATIVE_ATREAL_WITHIN THEN
447 EXPAND_TAC "f" THEN REAL_DIFF_TAC THEN
448 ASM_SIMP_TAC[REAL_ARITH `&1 <= x' ==> ~(x' = &0)`; REAL_POW_NZ] THEN
449 REWRITE_TAC[ARITH_RULE `5 - 1 = 4 /\ 5 * 2 = 10`; REAL_POW_POW] THEN
450 SUBGOAL_THEN `!n. ~(x' pow n = &0)` ASSUME_TAC THENL [
451 GEN_TAC THEN MATCH_MP_TAC REAL_POW_NZ THEN
452 UNDISCH_TAC `&1 <= x'` THEN REAL_ARITH_TAC;
453 ALL_TAC
454 ] THEN
455 MATCH_MP_TAC REAL_EQ_RCANCEL_IMP THEN EXISTS_TAC `x' pow 10` THEN
456 ASM_REWRITE_TAC[real_div; GSYM REAL_MUL_LNEG; GSYM REAL_MUL_ASSOC] THEN
457 ASM_SIMP_TAC[REAL_MUL_LINV; REAL_INV_MUL; REAL_INV_POW] THEN
458 REWRITE_TAC[REAL_ARITH `(&5 * a * p6 - ip5 * t) * p10 = &5 * a * (p6 * p10) - (ip5 * p10) * t`] THEN
459 REWRITE_TAC[REAL_FIELD `inv x' pow 6 * x' pow 10 = x' pow 4`] THEN
460 REWRITE_TAC[REAL_FIELD `inv x' pow 5 * x' pow 10 = x' pow 5`] THEN
461 REAL_ARITH_TAC;
462 ALL_TAC
463 ] THEN
464 X_GEN_TAC `t:real` THEN REPEAT STRIP_TAC THEN
465 REWRITE_TAC[REAL_ARITH `&0 <= a - b <=> b <= a`] THEN
466 SUBGOAL_THEN `!n. &0 < t pow n` ASSUME_TAC THENL [
467 GEN_TAC THEN MATCH_MP_TAC REAL_POW_LT THEN
468 ASM_SIMP_TAC[REAL_ARITH `&1 <= t ==> &0 < t`];
469 ALL_TAC
470 ] THEN
471 MATCH_MP_TAC REAL_LE_RCANCEL_IMP THEN
472 EXISTS_TAC `t pow 6` THEN ASM_REWRITE_TAC[] THEN
473 REWRITE_TAC[real_div; REAL_INV_MUL; GSYM REAL_MUL_ASSOC] THEN
474 ASM_SIMP_TAC[REAL_MUL_LINV; REAL_ARITH `&0 < a ==> ~(a = &0)`; REAL_MUL_RID] THEN
475 ONCE_REWRITE_TAC[REAL_ARITH `a * b * c = (a * c) * b:real`] THEN
476 REWRITE_TAC[REAL_FIELD `inv (t pow 5) * t pow 6 = t`] THEN
477 MATCH_MP_TAC REAL_LE_TRANS THEN EXISTS_TAC `&1` THEN CONJ_TAC THENL [
478 SUBGOAL_THEN `&0 < t pow 2 + &1` ASSUME_TAC THENL [
479 MATCH_MP_TAC REAL_LT_ADD THEN REWRITE_TAC[REAL_LT_POW_2] THEN
480 UNDISCH_TAC `&1 <= t` THEN REAL_ARITH_TAC;
481 ALL_TAC
482 ] THEN
483 ASM_SIMP_TAC[REAL_LE_LDIV_EQ; GSYM real_div; REAL_MUL_LID] THEN
484 MATCH_MP_TAC (REAL_ARITH `&1 <= t /\ &0 <= (t - &1) pow 2 ==> t <= t pow 2 + &1`) THEN
485 ASM_REWRITE_TAC[REAL_LE_POW_2];
486 ALL_TAC
487 ] THEN
488 REWRITE_TAC[REAL_ARITH `&1 <= &5 * x <=> (&1 / &5) <= x`] THEN
489 MATCH_MP_TAC REAL_LE_TRANS THEN EXISTS_TAC `pi / &4` THEN
490 CONJ_TAC THENL [ MP_TAC PI_APPROX_32 THEN REAL_ARITH_TAC; ALL_TAC ] THEN
491 ASM_REWRITE_TAC[GSYM ATN_1; ATN_MONO_LE_EQ];
492 ALL_TAC
493 ] THEN
494 REWRITE_TAC[ATN_1] THEN MP_TAC PI_APPROX_32 THEN
495 REAL_ARITH_TAC);;
496
497
498 let matan_d2_bound_ge1_low = prove(`!x. &1 <= x ==>
499 -- #0.65 <= real_derivative (real_derivative matan) x`,
500 REPEAT STRIP_TAC THEN
501 ASM_SIMP_TAC[REAL_ARITH `&1 <= x ==> &0 < x`; matan_second_derivative_gt0] THEN
502 MATCH_MP_TAC REAL_LE_TRANS THEN
503 EXISTS_TAC `-- (&3 / &4) * inv (x pow 2 * (x + &1)) - (&1 / &2) * inv (x * (x + &1) pow 2)` THEN
504 CONJ_TAC THENL [
505 REWRITE_TAC[REAL_ARITH `-- #0.65 <= --(&3 / &4) * a - (&1 / &2) * b <=> &3 * a + &2 * b <= #2.6`] THEN
506 MATCH_MP_TAC REAL_LE_TRANS THEN EXISTS_TAC `&3 * inv(&2) + &2 * inv(&2)` THEN
507 CONJ_TAC THENL [ ALL_TAC; REAL_ARITH_TAC ] THEN
508 MATCH_MP_TAC REAL_LE_ADD2 THEN
509 CONJ_TAC THEN MATCH_MP_TAC REAL_LE_LMUL THEN REWRITE_TAC[REAL_POS] THEN MATCH_MP_TAC REAL_LE_INV2 THEN REWRITE_TAC[REAL_ARITH `&0 < &2`] THEN ONCE_REWRITE_TAC[REAL_ARITH `&2 = &1 * &2`] THEN MATCH_MP_TAC REAL_LE_MUL2 THEN ASM_REWRITE_TAC[REAL_POS] THENL [
510 ASM_SIMP_TAC[REAL_POW_LE_1] THEN POP_ASSUM MP_TAC THEN REAL_ARITH_TAC;
511 ALL_TAC
512 ] THEN
513 ONCE_REWRITE_TAC[REAL_ARITH `&2 = &2 * &1`] THEN REWRITE_TAC[REAL_POW_2] THEN
514 MATCH_MP_TAC REAL_LE_MUL2 THEN POP_ASSUM MP_TAC THEN REAL_ARITH_TAC;
515 ALL_TAC
516 ] THEN
517 REWRITE_TAC[REAL_ARITH `--(&3 / &4) * a - b <= c - (&3 / &4) * a - b <=> &0 <= c`] THEN
518 MATCH_MP_TAC REAL_LE_MUL THEN CONJ_TAC THENL [ REAL_ARITH_TAC; ALL_TAC ] THEN
519 MATCH_MP_TAC REAL_LE_DIV THEN
520 ASM_SIMP_TAC[ATN_POS_LE; SQRT_POS_LE; REAL_ARITH `&1 <= x ==> &0 <= x`] THEN
521 MATCH_MP_TAC REAL_LE_MUL THEN
522 ASM_SIMP_TAC[REAL_LE_POW_2; SQRT_POS_LE; REAL_ARITH `&1 <= x ==> &0 <= x`]);;
523
524
525 let matan_d2_bound_01 = prove(`!x. &0 <= x /\ x < &1 ==>
526 abs (real_derivative (real_derivative matan) x) <= #0.65`,
527 GEN_TAC THEN DISCH_TAC THEN
528 MP_TAC (SPEC `x:real` matan_second_derivative_abs1_alt) THEN ANTS_TAC THENL [
529 POP_ASSUM MP_TAC THEN REAL_ARITH_TAC;
530 ALL_TAC
531 ] THEN
532 STRIP_TAC THEN ASM_REWRITE_TAC[] THEN
533 MATCH_MP_TAC REAL_LE_TRANS THEN EXISTS_TAC `&1 / &4 + &3 / &20` THEN
534 CONJ_TAC THEN TRY REAL_ARITH_TAC THEN
535 ABBREV_TAC `f = (&1 - x) / (&4 * (&1 + x) pow 2)` THEN
536 ABBREV_TAC `r = real_infsum (:num) (\i. -- &1 pow i / &(2 * i + 5) * x pow i)` THEN
537 MATCH_MP_TAC REAL_LE_TRANS THEN EXISTS_TAC `abs f + abs (&3 / &4 * r)` THEN
538 REWRITE_TAC[REAL_ABS_TRIANGLE] THEN
539 MATCH_MP_TAC REAL_LE_ADD2 THEN CONJ_TAC THENL [
540 EXPAND_TAC "f" THEN REWRITE_TAC[REAL_ABS_DIV; REAL_ABS_MUL; REAL_ABS_NUM] THEN
541 SUBGOAL_THEN `&0 < &4 /\ &0 < &4 * abs ((&1 + x) pow 2)` ASSUME_TAC THENL [
542 CONJ_TAC THEN TRY REAL_ARITH_TAC THEN
543 MATCH_MP_TAC REAL_LT_MUL THEN CONJ_TAC THEN TRY REAL_ARITH_TAC THEN
544 MATCH_MP_TAC (REAL_ARITH `&0 < x ==> &0 < abs x`) THEN
545 REWRITE_TAC[REAL_LT_POW_2] THEN
546 UNDISCH_TAC `&0 <= x /\ x < &1` THEN REAL_ARITH_TAC;
547 ALL_TAC
548 ] THEN
549 ASM_SIMP_TAC[RAT_LEMMA4; REAL_MUL_LID] THEN
550 REWRITE_TAC[REAL_MUL_AC] THEN
551 MATCH_MP_TAC REAL_LE_RMUL THEN CONJ_TAC THEN TRY REAL_ARITH_TAC THEN
552 MATCH_MP_TAC REAL_LE_TRANS THEN EXISTS_TAC `&1` THEN
553 UNDISCH_TAC `&0 <= x /\ x < &1` THEN DISCH_THEN (LABEL_TAC "h") THEN
554 CONJ_TAC THENL [ POP_ASSUM MP_TAC THEN REAL_ARITH_TAC; ALL_TAC ] THEN
555 MATCH_MP_TAC (REAL_ARITH `&1 <= a ==> &1 <= abs a`) THEN
556 MATCH_MP_TAC REAL_LSQRT_LE THEN REWRITE_TAC[SQRT_1] THEN
557 POP_ASSUM MP_TAC THEN REAL_ARITH_TAC;
558 ALL_TAC
559 ] THEN
560 REWRITE_TAC[REAL_ABS_MUL; REAL_ARITH `&3 / &20 = abs (&3 / &4) * (&1 / &5)`] THEN
561 MATCH_MP_TAC REAL_LE_LMUL THEN CONJ_TAC THENL [ REAL_ARITH_TAC; ALL_TAC ] THEN
562 EXPAND_TAC "r" THEN
563 SUBGOAL_THEN `&1 / &5 = abs ((\i. -- &1 pow i / &(2 * i + 5) * x pow i) 0)` (fun th -> ONCE_REWRITE_TAC[th]) THENL [
564 REWRITE_TAC[real_pow; MULT_0; ADD; REAL_ABS_DIV; REAL_ABS_NUM; REAL_MUL_RID];
565 ALL_TAC
566 ] THEN
567 PURE_REWRITE_TAC[GSYM FROM_0] THEN
568 MATCH_MP_TAC alt_sign_bound THEN
569 CONJ_TAC THENL [
570 REWRITE_TAC[REAL_ABS_MUL; REAL_ABS_DIV; abs_neg_one_pow; real_div; REAL_MUL_LID] THEN
571 REPEAT STRIP_TAC THENL [
572 MATCH_MP_TAC REAL_LE_MUL2 THEN REWRITE_TAC[REAL_ABS_POS] THEN
573 CONJ_TAC THENL [
574 REWRITE_TAC[REAL_ABS_INV] THEN MATCH_MP_TAC REAL_LE_INV2 THEN
575 REWRITE_TAC[REAL_ABS_NUM; REAL_OF_NUM_LT; REAL_OF_NUM_LE] THEN
576 ARITH_TAC;
577 ALL_TAC
578 ] THEN
579 REWRITE_TAC[GSYM ADD1; real_pow; REAL_ABS_MUL] THEN
580 ONCE_REWRITE_TAC[REAL_ARITH `x * y <= y <=> x * y <= &1 * y`] THEN
581 MATCH_MP_TAC REAL_LE_RMUL THEN REWRITE_TAC[REAL_ABS_POS] THEN
582 UNDISCH_TAC `&0 <= x /\ x < &1` THEN REAL_ARITH_TAC;
583 ALL_TAC
584 ] THEN
585 REWRITE_TAC[REAL_ARITH `((a * b) * c) * (d * e) * f = (a * d) * ((c * f) * b * e)`] THEN
586 REWRITE_TAC[REAL_ARITH `a * b <= &0 <=> &0 <= (-- &1 * a) * b`] THEN
587 REWRITE_TAC[GSYM REAL_POW_ADD; GSYM real_pow] THEN
588 MATCH_MP_TAC REAL_LE_MUL THEN CONJ_TAC THENL [
589 REWRITE_TAC[ARITH_RULE `SUC ((n + 1) + n) = 2 * (n + 1)`] THEN
590 REWRITE_TAC[real_pow; REAL_POW_NEG; EVEN_DOUBLE; REAL_POW_ONE; REAL_LE_01];
591 ALL_TAC
592 ] THEN
593 MATCH_MP_TAC REAL_LE_MUL THEN CONJ_TAC THENL [
594 MATCH_MP_TAC REAL_POW_LE THEN ASM_REWRITE_TAC[];
595 ALL_TAC
596 ] THEN
597 REWRITE_TAC[GSYM REAL_INV_MUL] THEN MATCH_MP_TAC REAL_LE_INV THEN
598 REWRITE_TAC[REAL_OF_NUM_MUL; REAL_OF_NUM_LE; LE_0];
599 ALL_TAC
600 ] THEN
601 ONCE_REWRITE_TAC[GSYM REALLIM_NULL_ABS] THEN
602 REWRITE_TAC[REAL_ABS_MUL; real_div; REAL_ABS_INV; abs_neg_one_pow; REAL_ABS_NUM; REAL_MUL_LID] THEN
603 MATCH_MP_TAC REALLIM_NULL_COMPARISON THEN
604 EXISTS_TAC `\n. inv (&n)` THEN CONJ_TAC THENL [
605 REWRITE_TAC[EVENTUALLY_SEQUENTIALLY] THEN
606 EXISTS_TAC `1` THEN REPEAT STRIP_TAC THEN
607 ONCE_REWRITE_TAC[REAL_ARITH `inv (&n) = inv (&n) * &1`] THEN
608 REWRITE_TAC[REAL_ABS_MUL; REAL_ABS_ABS] THEN
609 MATCH_MP_TAC REAL_LE_MUL2 THEN REWRITE_TAC[REAL_ABS_POS; REAL_ABS_1; REAL_MUL_RID] THEN
610 CONJ_TAC THENL [
611 REWRITE_TAC[REAL_ABS_INV; REAL_ABS_NUM] THEN
612 MATCH_MP_TAC REAL_LE_INV2 THEN
613 REWRITE_TAC[REAL_OF_NUM_LT; REAL_OF_NUM_LE] THEN
614 POP_ASSUM MP_TAC THEN ARITH_TAC;
615 ALL_TAC
616 ] THEN
617 REWRITE_TAC[REAL_ABS_POW] THEN
618 MATCH_MP_TAC REAL_POW_1_LE THEN
619 UNDISCH_TAC `&0 <= x /\ x < &1` THEN REAL_ARITH_TAC;
620 ALL_TAC
621 ] THEN
622 REWRITE_TAC[REALLIM_1_OVER_N]);;
623
624
625 let matan_d2_bound_neg_low = prove(`!x. -- &1 < x /\ x < &0 ==>
626 &0 <= real_derivative (real_derivative matan) x`,
627 GEN_TAC THEN DISCH_THEN (LABEL_TAC "x") THEN
628 MP_TAC (SPEC `x:real` matan_second_derivative_abs1) THEN ANTS_TAC THENL [
629 POP_ASSUM MP_TAC THEN REAL_ARITH_TAC;
630 ALL_TAC
631 ] THEN
632 STRIP_TAC THEN
633 MATCH_MP_TAC REAL_SERIES_POS THEN
634 MAP_EVERY EXISTS_TAC [`\i. (-- &1 pow (i + 2) * &((i + 1) * (i + 2)) / &(2 * i + 5)) * x pow i`; `from 0`] THEN
635 ASM_REWRITE_TAC[] THEN REPEAT STRIP_TAC THEN
636 REWRITE_TAC[REAL_ARITH `(a * b) * x pow i = (a * x pow i) * b`] THEN
637 MATCH_MP_TAC REAL_LE_MUL THEN CONJ_TAC THENL [
638 SUBGOAL_THEN `x pow i = (-- &1) pow i * (--x) pow i` (fun th -> REWRITE_TAC[th]) THENL [
639 REWRITE_TAC[GSYM REAL_POW_MUL; REAL_ARITH `-- &1 * --x = x`];
640 ALL_TAC
641 ] THEN
642 REWRITE_TAC[REAL_MUL_ASSOC; GSYM REAL_POW_ADD; ARITH_RULE `(i + 2) + i = 2 * (i + 1)`] THEN
643 MATCH_MP_TAC REAL_LE_MUL THEN CONJ_TAC THENL [
644 REWRITE_TAC[REAL_POW_NEG; EVEN_DOUBLE; REAL_POW_ONE; REAL_LE_01];
645 ALL_TAC
646 ] THEN
647 MATCH_MP_TAC REAL_POW_LE THEN REMOVE_THEN "x" MP_TAC THEN REAL_ARITH_TAC;
648 ALL_TAC
649 ] THEN
650 MATCH_MP_TAC REAL_LE_DIV THEN REWRITE_TAC[REAL_POS]);;
651
652
653 let matan_d2_bound_neg_high = prove(`!x. -- #0.2 <= x /\ x < &0 ==>
654 real_derivative (real_derivative matan) x <= #0.65`,
655 GEN_TAC THEN DISCH_THEN (LABEL_TAC "x") THEN
656 MATCH_MP_TAC REAL_LE_TRANS THEN EXISTS_TAC `real_derivative (real_derivative matan) (-- #0.2)` THEN
657 CONJ_TAC THENL [
658 MATCH_MP_TAC REAL_SERIES_LE THEN
659 MAP_EVERY EXISTS_TAC [`\i. (-- &1 pow (i + 2) * &((i + 1) * (i + 2)) / &(2 * i + 5)) * x pow i`; `\i. (-- &1 pow (i + 2) * &((i + 1) * (i + 2)) / &(2 * i + 5)) * (-- #0.2) pow i`; `from 0`] THEN
660 ASM_SIMP_TAC[matan_second_derivative_abs1; REAL_ARITH `-- #0.2 <= x /\ x < &0 ==> abs x < &1`; REAL_ARITH `abs (-- #0.2) < &1`] THEN
661 REPEAT STRIP_TAC THEN
662 REWRITE_TAC[REAL_ARITH `(a * b) * x pow i = (a * x pow i) * b`] THEN
663 SUBGOAL_THEN `!y. -- &1 pow (i + 2) * y pow i = (-- y) pow i` (fun th -> REWRITE_TAC[th]) THENL [
664 REWRITE_TAC[REAL_POW_ADD; REAL_ARITH `-- &1 pow 2 = &1`; REAL_MUL_RID] THEN
665 REWRITE_TAC[GSYM REAL_POW_MUL; REAL_ARITH `-- &1 * y = --y`];
666 ALL_TAC
667 ] THEN
668 MATCH_MP_TAC REAL_LE_MUL2 THEN REPEAT STRIP_TAC THENL [
669 MATCH_MP_TAC REAL_POW_LE THEN REMOVE_THEN "x" MP_TAC THEN REAL_ARITH_TAC;
670 MATCH_MP_TAC REAL_POW_LE2 THEN REMOVE_THEN "x" MP_TAC THEN REAL_ARITH_TAC;
671 MATCH_MP_TAC REAL_LE_DIV THEN REWRITE_TAC[REAL_OF_NUM_LE] THEN ARITH_TAC;
672 ALL_TAC
673 ] THEN
674 REWRITE_TAC[REAL_LE_REFL];
675 ALL_TAC
676 ] THEN
677 MP_TAC (SPEC `-- #0.2` matan_second_derivative_abs1_alt) THEN ANTS_TAC THENL [
678 REAL_ARITH_TAC;
679 ALL_TAC
680 ] THEN
681 STRIP_TAC THEN ASM_REWRITE_TAC[] THEN
682 MATCH_MP_TAC (REAL_ARITH `a <= &15 / &32 /\ b <= (&1 / &5 + &1 / &28) ==> a + (&3 / &4) * b <= #0.65`) THEN
683 CONJ_TAC THENL [ REAL_ARITH_TAC; ALL_TAC ] THEN
684 MP_TAC (SPECL[`0`; `1`; `\i. -- &1 pow i / &(2 * i + 5) * -- #0.2 pow i`] real_infsum_offset_alt) THEN
685 ASM_REWRITE_TAC[ARITH_RULE `0 < 1`; FROM_0] THEN
686 DISCH_THEN (fun th -> REWRITE_TAC[th; SUB_REFL; SUM_SING_NUMSEG]) THEN
687 REWRITE_TAC[real_pow; MULT_0; ADD; REAL_MUL_RID; REAL_LE_LADD] THEN
688 MP_TAC (SPECL[`\i. -- &1 pow i / &(2 * i + 5)`; `-- #0.2`; `1`] power_series_simple_bound2) THEN
689 ANTS_TAC THENL [
690 REPEAT STRIP_TAC THEN REWRITE_TAC[] THENL [
691 MATCH_MP_TAC REAL_SUMMABLE_FROM_ELSEWHERE THEN
692 EXISTS_TAC `0` THEN ASM_REWRITE_TAC[FROM_0];
693 REWRITE_TAC[REAL_ABS_MUL; abs_neg_one_pow; real_div; REAL_MUL_LID; REAL_ABS_INV] THEN
694 MATCH_MP_TAC REAL_LE_INV2 THEN REWRITE_TAC[REAL_ABS_NUM] THEN
695 REWRITE_TAC[REAL_OF_NUM_LT; REAL_OF_NUM_LE] THEN ARITH_TAC;
696 ALL_TAC
697 ] THEN
698 REAL_ARITH_TAC;
699 ALL_TAC
700 ] THEN
701 REWRITE_TAC[ARITH_RULE `2 * 1 + 5 = 7`] THEN
702 REAL_ARITH_TAC);;
703
704 (* The main bound result *)
705
706 let matan_d2_bound = prove(`!x. -- #0.2 <= x ==>
707 abs (real_derivative (real_derivative matan) x) <= #0.65`,
708 REPEAT STRIP_TAC THEN
709 ASM_CASES_TAC `x < &0` THENL [
710 MP_TAC (SPEC `x:real` matan_d2_bound_neg_low) THEN
711 MP_TAC (SPEC `x:real` matan_d2_bound_neg_high) THEN
712 REPEAT (POP_ASSUM MP_TAC) THEN REAL_ARITH_TAC;
713 ALL_TAC
714 ] THEN
715 ASM_CASES_TAC `x < &1` THENL [
716 MP_TAC (SPEC `x:real` matan_d2_bound_01) THEN
717 REPEAT (POP_ASSUM MP_TAC) THEN REAL_ARITH_TAC;
718 ALL_TAC
719 ] THEN
720 MP_TAC (SPEC `x:real` matan_d2_bound_ge1_low) THEN
721 MP_TAC (SPEC `x:real` matan_d2_bound_ge1_high) THEN
722 REPEAT (POP_ASSUM MP_TAC) THEN REAL_ARITH_TAC);;
723
724 end;;