diff --git a/thys/Irrationality_J_Hancl/Irrationality_J_Hancl.thy b/thys/Irrationality_J_Hancl/Irrationality_J_Hancl.thy --- a/thys/Irrationality_J_Hancl/Irrationality_J_Hancl.thy +++ b/thys/Irrationality_J_Hancl/Irrationality_J_Hancl.thy @@ -1,1005 +1,1005 @@ (* File: Irrationality_J_Hancl.thy Authors: Angeliki Koutsoukou-Argyraki and Wenda Li, Computer Laboratory, University of Cambridge, UK. Email: ak2110@cam.ac.uk, wl302@cam.ac.uk *) section \Irrational Rapidly Convergent Series\ theory Irrationality_J_Hancl imports "HOL-Analysis.Analysis" "HOL-Decision_Procs.Approximation" begin -text \This is the formalisation of a proof by J. Hancl, in particular of the proof of his Theorem 3 in +text \This is the formalisation of a proof by J. Hančl, in particular of the proof of his Theorem 3 in the paper: Irrational Rapidly Convergent Series, Rend. Sem. Mat. Univ. Padova, Vol 107 (2002). The statement asserts the irrationality of the sum of a series consisting of rational numbers defined using sequences that fulfill certain properties. Even though the statement is number-theoretic, the proof uses only arguments from introductory Analysis.\ -text \We show the central result (theorem Hancl3) by proof by contradiction, by making use of some of +text \We prove the central result (theorem Hancl3) by contradiction, by making use of some of the auxiliary lemmas. To this end, assuming that the sum is a rational number, for a quantity $\textrm{ALPHA}(n)$ we show that $\textrm{ALPHA}(n) \geq 1$ for all $n \in \mathbb{N}$. After that we show that we can find an $n \in \mathbb{N}$ for which $\textrm{ALPHA}(n) < 1$ which yields a contradiction and we thus conclude that the - sum of the series is a rational number. We finally give an immediate application of theorem Hancl3 + sum of the series is rational. We finally give an immediate application of theorem Hancl3 for a specific series (corollary Hancl3corollary, requiring lemma summable\_ln\_plus) which corresponds to Corollary 2 in the original -paper by J. Hancl. +paper by J. Hančl. \ hide_const floatarith.Max subsection \Misc\ lemma filterlim_sequentially_iff: "filterlim f F1 sequentially \ filterlim (\x. f (x+k)) F1 sequentially" unfolding filterlim_iff by (metis eventually_at_top_linorder eventually_sequentially_seg) lemma filterlim_realpow_sequentially_at_top: "(x::real) > 1 \ filterlim (power x) at_top sequentially" apply (rule LIMSEQ_divide_realpow_zero[THEN filterlim_inverse_at_top,of _ 1,simplified]) by auto lemma filterlim_at_top_powr_real: fixes g::"'b \ real" assumes "filterlim f at_top F" "(g \ g') F" "g'>1" shows "LIM x F. g x powr f x :> at_top" proof - have "LIM x F. ((g' + 1) / 2) powr f x :> at_top" proof (subst filterlim_at_top_gt[of _ _ 1],rule+) - fix Z assume "Z>(1::real)" + fix Z::real assume "Z > 1" have "\\<^sub>F x in F. ln Z / ln ((g' + 1) / 2) \ f x" using assms(1) filterlim_at_top by blast then have "\\<^sub>F x in F. ln Z \ ln (((g' + 1) / 2) powr f x)" proof (eventually_elim) case (elim x) then show ?case using \g'>1\ by (auto simp:ln_powr divide_simps) qed then show "\\<^sub>F x in F. Z \ ((g' + 1) / 2) powr f x" proof (eventually_elim) case (elim x) then show ?case using \1 < Z\ \g'>1\ by auto qed qed moreover have "\\<^sub>F x in F. ((g'+1)/2) powr f x \ g x powr f x" proof - have "\\<^sub>F x in F. g x > (g'+1)/2" apply (rule order_tendstoD[OF assms(2)]) using \g'>1\ by auto moreover have "\\<^sub>F x in F. f x>0" using assms(1) filterlim_at_top_dense by blast ultimately show ?thesis proof eventually_elim case (elim x) then show ?case using \g'>1\ by (auto intro!: powr_mono2) qed qed ultimately show ?thesis using filterlim_at_top_mono by fast qed lemma powrfinitesum: fixes a::real and s::nat assumes "s \ n" shows " (\j=s..(n::nat).(a powr (2^j))) = a powr (\j=s..(n::nat).(2^j)) " using \s \ n\ proof(induct n) case 0 then show ?case by auto next case (Suc n) have ?case when "s\n" using Suc.hyps by (metis Suc.prems add.commute linorder_not_le powr_add prod.nat_ivl_Suc' sum.cl_ivl_Suc that) moreover have ?case when "s=Suc n" proof- have "(\j = s..Suc n. a powr 2 ^ j) =(a powr 2 ^(Suc n)) " using \s=Suc n\ by simp also have "a powr 2 ^ Suc n = a powr sum (power 2) {s..Suc n}" using that by auto ultimately show "(\j = s..Suc n. a powr 2 ^ j) = a powr sum (power 2) {s..Suc n}" using \s\Suc n\ by linarith qed ultimately show ?case using \s\Suc n\ by linarith qed lemma summable_ratio_test_tendsto: fixes f :: "nat \ 'a::banach" assumes "c < 1" and "\n. f n\0" and "(\n. norm (f (Suc n)) / norm (f n)) \ c" shows "summable f" proof - obtain N where N_dist:"\n\N. dist (norm (f (Suc n)) / norm (f n)) c < (1-c)/2" using assms unfolding tendsto_iff eventually_sequentially by (meson diff_gt_0_iff_gt zero_less_divide_iff zero_less_numeral) have "norm (f (Suc n)) / norm (f n) \ (1+c)/2" when "n\N" for n using N_dist[rule_format,OF that] \c<1\ apply (auto simp add:field_simps dist_norm) by argo then have "norm (f (Suc n)) \ (1+c)/2 * norm (f n)" when "n\N" for n using that assms(2)[rule_format, of n] by (auto simp add:divide_simps) moreover have "(1+c)/2 < 1" using \c<1\ by auto ultimately show ?thesis using summable_ratio_test[of _ N f] by blast qed lemma summable_ln_plus: fixes f::"nat \ real" assumes "summable f" "\n. f n>0" shows "summable (\n. ln (1+f n))" proof (rule summable_comparison_test_ev[OF _ assms(1)]) have "ln (1 + f n) > 0" for n by (simp add: assms(2) ln_gt_zero) moreover have "ln (1 + f n) \ f n" for n apply (rule ln_add_one_self_le_self2) using assms(2)[rule_format,of n] by auto ultimately show "\\<^sub>F n in sequentially. norm (ln (1 + f n)) \ f n" by (auto intro!: eventuallyI simp add:less_imp_le) qed lemma suminf_real_offset_le: fixes f :: "nat \ real" assumes f: "\i. 0 \ f i" and "summable f" shows "(\i. f (i + k)) \ suminf f" proof - have "(\n. \i (\i. f (i + k))" using summable_sums[OF \summable f\] by (simp add: assms(2) summable_LIMSEQ summable_ignore_initial_segment) moreover have "(\n. \i (\i. f i)" using summable_sums[OF \summable f\] by (simp add: sums_def atLeast0LessThan f) then have "(\n. \i (\i. f i)" by (rule LIMSEQ_ignore_initial_segment) ultimately show ?thesis proof (rule LIMSEQ_le, safe intro!: exI[of _ k]) fix n assume "k \ n" have "(\ii (\i. i + k)) i)" by simp also have "\ = (\i\(\i. i + k) ` {.. \ sum f {..i sum f {.. n" shows " (\i=s..n. 2^i) < (2^(n+1) :: real) " using assms proof (induct n) case 0 show ?case by auto next case (Suc n) have ?case when "s=n+1" using that by auto moreover have ?case when "s \ n+1" proof - have"(\i=s..(n+1). 2^i ) = (\i=s..n. 2^i ) + (2::real)^(n+1) " using sum.cl_ivl_Suc \s \ Suc n \ by (auto simp add:add.commute) also have "... < (2) ^ (n +1) + (2)^(n+1)" proof - have "s \n" using that \s \ Suc n \ by auto then show ?thesis using Suc.hyps \s \ n\ by linarith qed also have "... = 2^(n+2)" by simp finally show "(\i=s..(Suc n). 2^i )< (2::real)^(Suc n+1)" by auto qed ultimately show ?case by blast qed subsection \Auxiliary lemmas and the main proof\ lemma showpre7: fixes a b ::"nat\int " and q p::int assumes "q>0" and "p>0"and a: "\n. a n>0" and "\n. b n>0" and assumerational:"(\ n. b (n+1) / a (n+1) ) sums (p/q)" shows "q*((\j=1..n. of_int( a j)))*(suminf (\(j::nat). (b (j+n+1)/ a (j+n+1 )))) = ((\j=1..n. of_int( a j)))*(p -q* (\j=1..n. b j / a j)) " proof - define aa where "aa=(\j = 1..n. real_of_int (a j))" define ff where "ff=(\i. real_of_int (b (i+1)) / real_of_int (a (i+1)))" have "(\j. ff (j+n)) = (\n. ff n) - sum ff {..j=1..n. ff (j-1))" proof - have "sum ff {..j=1..n. ff (j-1))" apply (subst sum_bounds_lt_plus1[symmetric]) by simp then show ?thesis unfolding ff_def by auto qed finally have "(\j. ff (j + n)) = p / q - (\j = 1..n. ff (j - 1))" . then have "q*(\j. ff (j + n)) = p - q*(\j = 1..n. ff (j - 1))" using \q>0\ by (auto simp add:field_simps) then have "aa*q*(\j. ff (j + n)) = aa*(p - q*(\j = 1..n. ff (j - 1)))" by auto then show ?thesis unfolding aa_def ff_def by auto qed lemma show7: fixes d::"nat\real" and a b::"nat\int " and q p::int assumes "q \1" and "p \ 1" and a: "\n. a n \ 1" and "\n. b n \ 1" and assumerational:"(\ n. b (n+1) / a (n+1) ) sums (p/q)" shows "q*((\j=1..n. of_int( a j)))*( suminf (\ (j::nat). (b (j+n+1)/ a (j+n+1 )))) \ 1 " (is "?L \ _") proof- define LL where "LL=?L" define aa where "aa=(\j = 1..n. real_of_int (a j))" define ff where "ff=(\i. real_of_int (b (i+1)) / real_of_int (a (i+1)))" have "?L > 0" proof - have "aa > 0" unfolding aa_def using a by (induction n) (simp_all add: int_one_le_iff_zero_less prod_pos) moreover have "(\j. ff (j + n)) > 0" proof (rule suminf_pos) have "summable ff" unfolding ff_def using assumerational using summable_def by blast then show " summable (\j. ff (j + n))" using summable_iff_shift[of ff n] by auto show "\i. 0 < ff (i + n)" unfolding ff_def using a assms(4) int_one_le_iff_zero_less by auto qed ultimately show ?thesis unfolding aa_def ff_def using \q\1\ by auto qed moreover have "?L \ \" proof - have "?L = aa *(p -q* ( \j=1..n. b j / a j))" unfolding aa_def using a assms assumerational int_one_le_iff_zero_less showpre7 by force also have "... = aa * p - q * (\j=1..n. aa * b j / a j)" by (auto simp add:algebra_simps sum_distrib_left) also have "... = prod a {1..n} * p - q * (\j = 1..n. b j * prod a ({1..n} - {j}))" proof - have "(\j=1..n. aa * b j / a j) = (\j=1..n. b j * prod a ({1..n} - {j}))" unfolding of_int_sum proof (rule sum.cong) fix j assume "j \ {1..n}" then have "(\i = 1..n. real_of_int (a i)) = a j * (\i\{1..n} - {j}. real_of_int (a i))" by (meson finite_atLeastAtMost prod.remove) then have "aa / real_of_int (a j) = prod a ({1..n} - {j})" unfolding aa_def using a[rule_format,of j] by (auto simp add:field_simps) then show "aa * b j / a j = b j * prod a ({1..n} - {j})" by (metis mult.commute of_int_mult times_divide_eq_right) qed simp moreover have "aa * p = (\j = 1..n. (a j)) * p" unfolding aa_def by auto ultimately show ?thesis by force qed also have "... \ \" using Ints_of_int by blast finally show ?thesis . qed ultimately show ?thesis apply (fold LL_def) by (metis Ints_cases int_one_le_iff_zero_less not_less of_int_0_less_iff of_int_less_1_iff) qed lemma show8: fixes d ::"nat\real " and a :: "nat\int" and s k::nat assumes "A > 1" and d: "\n. d n> 1" and a:"\n. a n>0" and "s>0" and "convergent_prod d" and assu2: "\n \ s. A / of_int (a n) powr (1 / of_int (2^n)) > (\j. d (n + j))" shows "\n\s. (\j. d (j+n)) < A / (MAX j\{s..n}. of_int (a j) powr (1 / of_int (2 ^ j)))" proof (intro strip) fix n assume "s \ n" define sp where "sp \ (\n. \j. d (j+n))" define ff where "ff \ (\(j::nat). (real_of_int (a j)) powr(1 /of_int (2^j)))" have "sp i \ sp n" when "i\n" for i proof - have "(\j. d (j + i)) = (\ia. d (ia + (n - i) + i)) * (\iaj. d (j + i))" using \convergent_prod d\ convergent_prod_iff_shift[of d i] by simp show "\j. j < n - i \ d (j + i) \ 0" by (metis d not_one_less_zero) qed then have "sp i = sp n * (\jn\i\ by (auto simp:algebra_simps) moreover have "sp i>1" "sp n>1" unfolding sp_def using convergent_prod_iff_shift \convergent_prod d\ d by (auto intro!:less_1_prodinf) moreover have "(\j 1" using d less_imp_le by (auto intro: prod_ge_1) ultimately show ?thesis by auto qed moreover have "\j\s. A / ff j > sp j" unfolding ff_def sp_def using assu2 by (auto simp:algebra_simps) ultimately have "\j. s\j \ j\n \ A / ff j > sp n" by force then show "sp n< A / Max (ff ` {s..n})" by (metis (mono_tags, hide_lams) Max_in \n\s\ atLeastAtMost_iff empty_iff finite_atLeastAtMost finite_imageI imageE image_is_empty order_refl) qed lemma auxiliary1_9: fixes d ::"nat\real" and a::"nat\int " and s m::nat assumes d: "\n. d n> 1" and a: "\n. a n>0" and "s>0" and "n \ m" and " m \ s" and auxifalse_assu: "\n\m. (of_int (a (n+1))) powr(1 /of_int (2^(n+1))) < (d (n+1))* (Max ((\ (j::nat). (of_int (a j)) powr(1 /of_int (2^j))) ` {s..n} ))" shows "(of_int (a (n+1))) powr(1 /of_int (2^(n+1))) < (\j=(m+1)..(n+1). d j) * (Max ((\ (j::nat). (of_int (a j)) powr(1 /of_int (2^j))) ` {s..m}))" proof- define ff where "ff \ \j. real_of_int (a j) powr (1 / of_int (2^j))" have [simp]:"ff j > 0" for j unfolding ff_def by (metis a less_numeral_extra(3) of_int_0_less_iff powr_gt_zero) have ff_asm:"ff (n+1) < d (n+1) * Max (ff ` {s..n})" when "n\m" for n using auxifalse_assu that unfolding ff_def by simp from \n\m\ have Q: "(Max( ff ` {s..n} )) \ (\j=(m+1)..n. d j)* (Max (ff ` {s..m}))" proof(induct n) case 0 then show ?case using \m\s\ by simp next case (Suc n) have ?case when "m=Suc n" using that by auto moreover have ?case when "m\Suc n" proof - have "m \ n" using that Suc(2) by simp then have IH: "Max (ff ` {s..n}) \ prod d {m + 1..n} * Max (ff ` {s..m})" using Suc(1) by linarith have "Max (ff ` {s..Suc n}) = Max (ff ` {s..n} \ {ff (Suc n)})" using Suc.prems assms(5) atLeastAtMostSuc_conv by auto also have "... = max (Max (ff ` {s..n})) (ff (Suc n))" using Suc.prems assms(5) max_def sup_assoc that by auto also have "... \ max (Max (ff ` {s..n})) (d (n+1) * Max (ff ` {s..n}))" using \m \ n\ ff_asm by fastforce also have "... \ Max (ff ` {s..n}) * max 1 (d (n+1))" proof - have "Max (ff ` {s..n}) \ 0" by (metis (mono_tags, hide_lams) Max_in \\j. 0 < ff j\ \m \ n\ assms(5) atLeastAtMost_iff empty_iff finite_atLeastAtMost finite_imageI imageE image_is_empty less_eq_real_def) then show ?thesis using max_mult_distrib_right by (simp add: max_mult_distrib_right mult.commute) qed also have "... = Max (ff ` {s..n}) * d (n+1)" by (metis d max.commute max.strict_order_iff) also have "... \ prod d {m + 1..n} * Max (ff ` {s..m}) * d (n+1)" using IH d[rule_format, of "n+1"] by auto also have "... = prod d {m + 1..n+1} * Max (ff ` {s..m})" using \n\m\ by (simp add:prod.nat_ivl_Suc' algebra_simps) finally show ?case by simp qed ultimately show ?case by blast qed then have "d (n+1) * Max (ff ` {s..n} ) \ (\j=(m+1)..(n+1). d j)* (Max (ff ` {s..m}))" using \m\n\ d[rule_format,of "Suc n"] by (simp add:prod.nat_ivl_Suc') then show ?thesis using ff_asm[of n] \s\m\ \m\n\ unfolding ff_def by auto qed lemma show9: fixes d ::"nat\real " and a :: "nat\int " and s ::nat and A::real assumes "A > 1" and d: "\n. d n> 1" and a: "\n. a n>0" and "s>0" and assu1: "(( \ n. (of_int (a n)) powr(1 /of_int (2^n)))\ A) sequentially " and "convergent_prod d" and 8: "\n\s. prodinf (\j. d( n+j)) < A/(Max ((\(j::nat). (of_int (a j)) powr(1 /of_int (2^j))) ` {s..n})) " shows "\m \s. \n\m. ( (of_int (a (n+1))) powr(1 /of_int (2^(n+1))) \ (d (n+1))* (Max ( ( \ (j::nat). (of_int (a j)) powr(1 /of_int (2^j))) ` {s..n} )))" proof (rule ccontr) define ff where "ff \ (\j. real_of_int (a j) powr (1 / of_int (2^j)))" assume assumptioncontra: " \ (\m \s. \n\m. ff(n+1) \ d(n+1) * Max (ff ` {s..n}))" then obtain t where "t\s" and ttt: "\n\t. ff (n+1) < d (n+1) * Max (ff ` {s..n})" by fastforce define B where "B \ \j. d (t + 1 + j)" have "B>0" unfolding B_def proof (rule less_0_prodinf) show "convergent_prod (\j. d (t + 1 + j))" using convergent_prod_iff_shift[of d "t+1"] \convergent_prod d\ by (auto simp: algebra_simps) show "\i. 0 < d (t + 1 + i)" using d le_less_trans zero_le_one by blast qed have "A \ B * Max ( ff ` {s..t})" proof (rule tendsto_le[of sequentially "\n. (\j=(t+1)..(n+1). d j) * Max ( ff ` {s..t})" _ "\n. ff (n+1)"]) show "(\n. ff (n + 1)) \ A" using assu1[folded ff_def] LIMSEQ_ignore_initial_segment by blast have "(\n. prod d {t + 1..n + 1}) \ B" proof - have "convergent_prod (\j. d (t + 1 + j))" using \convergent_prod d\ convergent_prod_iff_shift[of d "t+1"] by (simp add:algebra_simps) then have "(\n. \i\n. d (t + 1 + i)) \ B" using B_def convergent_prod_LIMSEQ by blast then have "(\n. \i\{0..n}. d (i+(t + 1))) \ B" using atLeast0AtMost by (auto simp:algebra_simps) then have "(\n. prod d {(t + 1)..n + (t + 1)}) \ B" apply (subst (asm) prod.shift_bounds_cl_nat_ivl[symmetric]) by simp from seq_offset_neg[OF this,of "t"] show "(\n. prod d {t + 1..n+1}) \ B" apply (elim Lim_transform) apply (rule LIMSEQ_I) apply (rule exI[where x="t+1"]) by auto qed then show "(\n. prod d {t + 1..n + 1} * Max (ff ` {s..t})) \ B * Max (ff ` {s..t})" by (auto intro:tendsto_eq_intros) have "\\<^sub>F n in sequentially. (ff (n+1)) < (\j=(t+1)..(n+1). d j) * (Max ( ff ` {s..t}))" unfolding eventually_sequentially ff_def using auxiliary1_9[OF d a \s>0\ _ \t\s\ ttt[unfolded ff_def]] by blast then show "\\<^sub>F n in sequentially. (ff (n+1)) \ (\j=(t+1)..(n+1). d j) * (Max ( ff ` {s..t}))" by (eventually_elim,simp) qed simp also have "... \ B * Max ( ff ` {s..t+1})" proof - have "Max (ff ` {s..t}) \ Max (ff ` {s..t + 1})" using \t\s\ by (auto intro: Max_mono) then show ?thesis using \B>0\ by auto qed finally have "A \ B * Max (ff ` {s..t + 1})" unfolding B_def . moreover have "B < A / Max (ff ` {s..t + 1})" using 8[rule_format, of "t+1",folded ff_def B_def] \s\t\ by auto moreover have "Max (ff ` {s..t+1})>0" using \A \ B * Max (ff ` {s..t + 1})\ \B>0\ \A>1\ zero_less_mult_pos [of B "Max (ff ` {s..Suc t})"] by fastforce ultimately show False by (auto simp add:field_simps) qed lemma show10: fixes d ::"nat\real " and a ::"nat\int " and s::nat assumes d [rule_format]: "\n. d n> 1" and a [rule_format]: "\n. a n>0" and " s>0" and 9: "\m \s. \n\m. a (n+1) powr(1 / of_int (2^(n+1))) \ d (n+1) * (Max ((\j. (of_int (a j)) powr(1 /of_int (2^j))) ` {s..n} ))" shows "\m\s. \n\m. d (n+1) powr(2^(n+1)) * (\j=1..n. of_int( a j)) * (1 / (\j=1..s-1. of_int( a j))) \ a (n+1)" proof (intro strip) fix m assume "s \ m" from 9[rule_format,OF this] obtain n where "n\m" and asm_9:"( (of_int (a (n+1))) powr(1 /of_int (2^(n+1))) \ (d (n+1))* (Max ( ( \ (j::nat). (of_int (a j)) powr(1 /of_int (2^j))) ` {s..n} )))" by auto with \s\m\ have "s\n" by auto define M where "M \ \s. MAX j\{s..n}. a j powr (1 / real_of_int (2 ^ j))" have prod: "(\j=1..n. real_of_int (a j)) * (1 / (\j=1..s-1. of_int(a j))) = (\j=s..n. of_int( a j))" proof - define f where "f= (\j. real_of_int( a j))" have "{Suc 0..n}= {Suc 0..s - Suc 0} \ {s..n}" using \n\s\ \s >0\ by auto then have "(\j=1..n. f j) = (\j=1..s-1. f j) * (\j=s..n. f j)" apply (subst prod.union_disjoint[symmetric]) by auto moreover have "(\j=1..s-1. f j) > 0 " by (metis a f_def of_int_0_less_iff prod_pos) then have "(\j=1..s-1. f j) \ 0" by argo ultimately show ?thesis unfolding f_def by auto qed then have "d (n+1) powr 2 ^ (n+1) * (\j = 1..n. of_int (a j)) * (1 / (\j = 1..s - 1. of_int (a j))) = d (n+1) powr 2 ^ (n+1) * (\j = s..n. of_int (a j))" by (metis mult.assoc prod) also have "... \ ((d (n+1))powr(2^(n+1) ) * (\i=s..n. M s powr(2^i)) )" proof (rule mult_left_mono) show "0 \ (d (n + 1)) powr 2 ^ (n + 1)" by auto show "(\j = s..n. real_of_int (a j)) \ (\i = s..n. M s powr 2 ^ i)" proof (intro prod_mono conjI) fix i assume i: "i \ {s..n}" have "a i = (a i powr (1 / real_of_int (2 ^ i))) powr 2 ^ i" unfolding powr_powr by (simp add: a less_eq_real_def) also have "\ \ M s powr(2^i)" unfolding M_def using i by (force intro: powr_mono2) finally show "a i \ M s powr 2 ^ i" . show "\i. i \ {s..n} \ 0 \ real_of_int (a i)" by (meson a less_imp_le of_int_0_le_iff) qed qed also have "... = d(n+1) powr (2^(n+1)) * M s powr (\i=s..n. 2^i)" proof- have "d (n+1) powr (2^(n+1)) \ 1 " by (metis Transcendental.log_one d le_powr_iff zero_le_numeral zero_le_power zero_less_one) moreover have "(\i=s..n. M s powr(2^i)) = M s powr (\i=s..n. 2^i ) " using \s\n\ powrfinitesum by auto ultimately show ?thesis by auto qed also have "... \ d (n + 1) powr 2 ^ (n + 1) * M s powr(2^(n+1))" proof - have "sum (power 2) {s..n} < (2::real) ^ (n + 1)" using factt \s\n\ by auto moreover have "1 \ M s" proof - define S where "S=(\(j::nat). ( of_int( a j) powr(1 /real_of_int (2^j)) )) ` {s..n }" have "finite S" unfolding S_def by auto moreover have "S\{}" unfolding S_def using \s\n\ by auto moreover have "\x\S. x\1" proof- have "a s powr (1 / (2^s)) \ 1" proof (rule ge_one_powr_ge_zero) show "1 \ real_of_int (a s)" by (simp add: a int_one_le_iff_zero_less) qed auto moreover have "of_int( a s) powr(1 /real_of_int (2^s)) \ S" unfolding S_def using \s\n\ by auto ultimately show ?thesis by auto qed ultimately show ?thesis using Max_ge_iff[of S 1] unfolding S_def M_def by blast qed moreover have "0 \ (d (n + 1)) powr 2 ^ (n + 1)" by auto ultimately show ?thesis by (simp add: mult_left_mono powr_mono M_def) qed also have "... = (d (n+1) * M s) powr(2^(n+1))" proof - have "d (n + 1) \ 0" using d[of "n+1"] by argo moreover have "M s \ 0" using \s\n\ by (auto simp: M_def Max_ge_iff) ultimately show ?thesis unfolding M_def using powr_mult by auto qed also have "... \ (real_of_int (a (n + 1)) powr (1 / real_of_int (2 ^ (n + 1)))) powr 2 ^ (n + 1)" proof (rule powr_mono2) have "M s \ 0" using \s\n\ by (auto simp: M_def Max_ge_iff) moreover have "d (n + 1) \0" using d[of "n+1"] by argo ultimately show "0 \ (d (n + 1)) * M s" by auto show "(d (n + 1)) * M s \ real_of_int (a (n + 1)) powr (1 / real_of_int (2 ^ (n + 1)))" using M_def asm_9 by presburger qed simp also have "... = (of_int (a (n+1)))" by (simp add: a less_eq_real_def pos_add_strict powr_powr) finally show "\n\m. d (n + 1) powr 2 ^ (n + 1) * (\j = 1..n. real_of_int (a j)) * (1 / (\j = 1..s - 1. real_of_int (a j))) \ real_of_int (a (n + 1))" using \n\m\ \m\s\ by force qed lemma lasttoshow: fixes d ::"nat\real " and a b ::"nat\int " and q::int and s::nat assumes d: "\n. d n> 1" and a:"\n. a n>0" and "s>0" and "q>0" and "A > 1" and b:"\n. b n>0" and 9: "\m\s. \n\m. ((of_int (a (n+1))) powr(1 /of_int (2^(n+1))) \ (d (n+1))* (Max ((\(j::nat). (of_int (a j)) powr(1 /of_int (2^j))) ` {s..n} )))" and assu3: "filterlim( \ n. (d n)^(2^n)/ b n) at_top sequentially " and 5: "\\<^sub>F n in sequentially. (\j. (b (n + j)) / (a (n + j))) \ 2 * b n / a n" shows "\n. q*((\j=1..n. real_of_int(a j))) * suminf (\(j::nat). (b (j+n+1)/ a (j+n+1)))<1" proof- define as where "as=(\j = 1..s - 1. real_of_int (a j))" obtain n where "n\s" and n_def1:"real_of_int q * as * 2 * real_of_int (b (n + 1)) / d (n + 1) powr 2 ^ (n + 1) < 1" and n_def2:"d (n + 1) powr 2 ^ (n + 1) * (\j = 1..n. real_of_int (a j)) * (1 / as) \ real_of_int (a (n + 1))" and n_def3:"(\j. (b (n+1 + j)) / (a (n+1 + j))) \ 2 * b (n+1) / a (n+1)" proof - have *:"(\n. real_of_int (b n) / d n ^ 2 ^ n) \ 0" using tendsto_inverse_0_at_top[OF assu3] by auto then have "(\n. real_of_int (b n) / d n powr 2 ^ n) \ 0" proof - have "d n ^ 2 ^ n = d n powr (of_nat (2 ^ n))" for n by (metis d le_less_trans powr_realpow zero_le_one) then show ?thesis using * by auto qed from tendsto_mult_right_zero[OF this,of "q * as * 2"] have "(\n. q * as * 2 * b n / d n powr 2 ^ n) \ 0" by auto then have "\\<^sub>F n in sequentially. q * as * 2 * b n / d n powr 2 ^ n < 1" by (elim order_tendstoD) simp then have "\\<^sub>F n in sequentially. q * as * 2 * b n / d n powr 2 ^ n < 1 \ (\j. (b (n + j)) / (a (n + j))) \ 2 * b n / a n" using 5 by eventually_elim auto then obtain N where N_def:"\n\N. q * as * 2 * b n / d n powr 2 ^ n < 1 \ (\j. (b (n + j)) / (a (n + j))) \ 2 * b n / a n" unfolding eventually_sequentially by auto obtain n where "n\s" and "n\N" and n_def:"d (n + 1) powr 2 ^ (n + 1) * (\j = 1..n. of_int (a j)) * (1 / as) \ real_of_int (a (n + 1))" using show10[OF d a \s>0\ 9,folded as_def,rule_format,of "max s N"] by auto with N_def[rule_format, of "n+1"] that[of n] show ?thesis by auto qed define pa where "pa \ (\j = 1..n. real_of_int (a j))" define dn where "dn \ d (n + 1) powr 2 ^ (n + 1)" have [simp]:"dn >0" "as > 0" subgoal unfolding dn_def by (metis d not_le numeral_One powr_gt_zero zero_le_numeral) subgoal unfolding as_def by (simp add: a prod_pos) done have [simp]:"pa>0" unfolding pa_def using a by (simp add: prod_pos) have K: "q* (\j=1..n. real_of_int (a j)) * suminf (\ (j::nat). (b (j+n+1)/ a (j+n+1))) \q* (\j=1..n. real_of_int (a j)) *2* (b (n+1))/(a( n+1))" apply (fold pa_def) using mult_left_mono[OF n_def3,of "real_of_int q * pa"] \n\s\ \pa>0\ \q>0\ by (auto simp add:algebra_simps) also have KK:"... \ 2*q* (\j=1..n. real_of_int (a j)) * (b(n+1))* ((\j=1..s-1. real_of_int( a j))/((d (n+1))powr(2^(n+1)) * (\j=1..n. real_of_int ( a j))))" proof - have " dn * pa * (1 / as) \ real_of_int (a (n + 1))" using n_def2 unfolding dn_def pa_def . then show ?thesis apply (fold pa_def dn_def as_def) using \pa>0\ \q>0\ a[rule_format, of "Suc n"] b[rule_format, of "Suc n"] by (auto simp add: field_simps) qed also have KKK: "... = q * (\j=1..(s-1). real_of_int(a j)) * 2 * b (n+1) / d (n+1) powr 2^(n+1)" apply (fold as_def pa_def dn_def) apply simp using \0 < pa\ by blast also have KKKK: "... < 1" using n_def1 unfolding as_def by simp finally show ?thesis by auto qed lemma fixes d ::"nat\real " and a b ::"nat\int " and A::real assumes "A > 1" and d: "\n. d n> 1" and a: "\n. a n>0" and b:"\n. b n>0" and assu1: "(( \ n. (of_int (a n)) powr(1 /of_int (2^n)))\ A) sequentially " and assu3: "filterlim ( \ n. (d n)^(2^n)/ b n) at_top sequentially" and "convergent_prod d" shows issummable: "summable (\j. b j / a j)" and show5: "\\<^sub>F n in sequentially. (\j. (b (n + j)) / (a (n + j))) \ 2 * b n / a n" proof- define c where "c = (\j. b j / a j)" have c_pos:"c j>0" for j using a b unfolding c_def by simp have c_ratio_tendsto:"(\n. c (n+1) / c n ) \ 0" proof - define nn where "nn \ (\n. (2::int) ^ (Suc n))" define ff where "ff \ (\n. (a n / a (Suc n)) powr(1 /nn n)*(d(Suc n)))" have nn_pos:"nn n>0" and ff_pos:"ff n>0" for n subgoal unfolding nn_def by simp subgoal unfolding ff_def using d[rule_format, of "Suc n"] a[rule_format, of n] a[rule_format, of "Suc n"] by auto done have ff_tendsto:"ff \ 1 / sqrt A" proof - have "(of_int (a n)) powr(1 / (nn n)) = sqrt(of_int (a n) powr(1 /of_int (2^n)))" for n unfolding nn_def using a by (simp add: powr_half_sqrt [symmetric] powr_powr ac_simps) moreover have "(( \ n. sqrt(of_int (a n) powr(1 /of_int (2^n))))\ sqrt A) sequentially " using assu1 tendsto_real_sqrt by blast ultimately have "(( \ n. (of_int (a n)) powr(1 /of_int (nn n)))\ sqrt A) sequentially " by auto from tendsto_divide[OF this assu1[THEN LIMSEQ_ignore_initial_segment[where k=1]]] have "(\n. (a n / a (Suc n)) powr(1 /nn n)) \ 1/sqrt A" using \A>1\ a unfolding nn_def by (auto simp add:powr_divide less_imp_le inverse_eq_divide sqrt_divide_self_eq) moreover have "(\n. d (Suc n))\ 1" apply (rule convergent_prod_imp_LIMSEQ) using convergent_prod_iff_shift[of d 1] \convergent_prod d\ by auto ultimately show ?thesis unfolding ff_def by (auto intro:tendsto_eq_intros) qed have "(\n. (ff n) powr nn n) \ 0" proof - define aa where "aa=(1+1/sqrt A) / 2" have "eventually (\n. ff nA>1\ by (auto simp add:field_simps) moreover have "(\n. aa powr nn n) \ 0" proof - have "(\y. aa ^ (nat \ nn) y) \ 0" apply (rule tendsto_power_zero) subgoal unfolding nn_def comp_def apply (rule filterlim_subseq) by (auto intro:strict_monoI) subgoal unfolding aa_def using \A>1\ by auto done then show ?thesis proof (elim filterlim_mono_eventually) have "aa>0" unfolding aa_def using \A>1\ by (auto simp add:field_simps pos_add_strict) then show " \\<^sub>F x in sequentially. aa ^ (nat \ nn) x = aa powr real_of_int (nn x)" by (auto simp: powr_int order.strict_implies_order[OF nn_pos]) qed auto qed ultimately show ?thesis apply (elim metric_tendsto_imp_tendsto) apply (auto intro!:powr_mono2 elim!:eventually_mono) using nn_pos ff_pos by (meson le_cases not_le)+ qed then have "(\n. (d (Suc n))^(nat (nn n)) * (a n / a (Suc n))) \ 0" proof (elim filterlim_mono_eventually) show "\\<^sub>F x in sequentially. ff x powr (nn x) = d (Suc x) ^ nat (nn x) * (a x / a (Suc x))" apply (rule eventuallyI) subgoal for x unfolding ff_def using a[rule_format,of x] a[rule_format,of "Suc x"] d[rule_format,of "Suc x"] nn_pos[of x] apply (auto simp add:field_simps powr_divide powr_powr powr_mult ) by (simp add: powr_int) done qed auto moreover have "(\n. b (Suc n) / (d (Suc n))^(nat (nn n))) \ 0" using tendsto_inverse_0_at_top[OF assu3,THEN LIMSEQ_ignore_initial_segment[where k=1]] unfolding nn_def by (auto simp add:field_simps nat_mult_distrib nat_power_eq) ultimately have "(\n. b (Suc n) * (a n / a (Suc n))) \ 0" apply - subgoal premises asm using tendsto_mult[OF asm,simplified] apply (elim filterlim_mono_eventually) using d by (auto simp add:algebra_simps,metis (mono_tags, lifting) always_eventually not_one_less_zero) done then have "(\n. (b (Suc n) / b n) * (a n / a (Suc n))) \ 0" apply (elim Lim_transform_bound[rotated]) apply (rule eventuallyI) subgoal for x using a[rule_format, of x] a[rule_format, of "Suc x"] b[rule_format, of x] b[rule_format, of "Suc x"] by (auto simp add:field_simps) done then show ?thesis unfolding c_def by (auto simp add:algebra_simps) qed from c_ratio_tendsto have "(\n. norm (b (Suc n) / a (Suc n)) / norm (b n / a n)) \ 0" unfolding c_def using a b by (force simp add:divide_simps abs_of_pos intro: Lim_transform_eventually) from summable_ratio_test_tendsto[OF _ _ this] a b show "summable c" unfolding c_def by (metis c_def c_pos less_irrefl zero_less_one) have "\\<^sub>F n in sequentially. (\j. c (n + j)) \ 2 * c n" proof - obtain N where N_ratio:"\n\N. c (n + 1) / c n < 1 / 2" proof - have "eventually (\n. c (n+1) / c n < 1/2) sequentially" using c_ratio_tendsto[unfolded tendsto_iff,rule_format, of "1/2",simplified] apply eventually_elim subgoal for n using c_pos[of n] c_pos[of "Suc n"] by auto done then show ?thesis using that unfolding eventually_sequentially by auto qed have "(\j. c (j + n)) \ 2 * c n" when "n\N" for n proof - have "(\j 2*c n * (1 - 1 / 2^(m+1))" for m proof (induct m) case 0 then show ?case using c_pos[of n] by simp next case (Suc m) have "(\ji c n + (\i c (i + n) / 2" for i using N_ratio[rule_format,of "i+n"] \n\N\ c_pos[of "i+n"] by simp then show ?thesis by (auto intro:sum_mono) qed also have "... = c n + (\i c n + c n * (1 - 1 / 2 ^ (m + 1))" using Suc by auto also have "... = 2 * c n * (1 - 1 / 2 ^ (Suc m + 1))" by (auto simp add:field_simps) finally show ?case . qed then have "(\j 2*c n" for m using c_pos[of n] by (smt divide_le_eq_1_pos divide_pos_pos nonzero_mult_div_cancel_left zero_less_power) moreover have "summable (\j. c (j + n))" using \summable c\ by (simp add: summable_iff_shift) ultimately show ?thesis using suminf_le_const[of "\j. c (j+n)" "2*c n"] by auto qed then show ?thesis unfolding eventually_sequentially by (auto simp add:algebra_simps) qed then show "\\<^sub>F n in sequentially. (\j. (b (n + j)) / (a (n + j))) \ 2 * b n / a n" unfolding c_def by simp qed theorem Hancl3: fixes d ::"nat\real" and a b :: "nat\int" assumes "A > 1" and d: "\n. d n > 1" and a: "\n. a n>0" and b: "\n. b n > 0" and "s>0" and assu1: "(\n. (a n) powr(1 / of_int(2^n))) \ A" and assu2: "\n \ s. A / (a n) powr (1 / of_int(2^n)) > (\j. d (n+j))" and assu3: "LIM n sequentially. d n ^ 2 ^ n / b n :> at_top" and "convergent_prod d" shows "(\n. b n / a n) \ \" proof (rule ccontr) assume asm: "\ ((\n. b n / a n) \ \)" have ab_sum: "summable (\j. b j / a j)" using issummable[OF \A>1\ d a b assu1 assu3 \convergent_prod d\] . obtain p q ::int where "q>0" and pq_def: "(\n. b (n+1) / a (n+1)) sums (p/q)" proof - from asm have "(\n. b n / a n) \ \" by auto then have "(\n. b (n+1) / a (n+1)) \ \" apply (subst suminf_minus_initial_segment[OF ab_sum,of 1]) by auto then obtain p' q' ::int where "q'\0" and pq_def: "(\ n. b (n+1) / a (n+1) ) sums (p'/q')" unfolding Rats_eq_int_div_int using summable_ignore_initial_segment[OF ab_sum,of 1,THEN summable_sums] by force define p q where "p \ (if q'<0 then -p' else p')" and "q \ (if q'<0 then -q' else q')" have "p'/q' = p/q" "q>0" using \q'\0\ unfolding p_def q_def by auto then show ?thesis using that[of q p] pq_def by auto qed define ALPHA where "ALPHA = (\n. of_int q * (\j=1..n. of_int(a j)) * (\j. (b (j+n+1)/a (j+n+1))))" have "ALPHA n \ 1" for n proof - have "(\n. b (n+1) / a (n+1)) > 0" proof (rule suminf_pos) show "summable (\n. b (n + 1) / real_of_int (a (n + 1)))" using summable_ignore_initial_segment[OF ab_sum,of 1] by auto show "\n. 0 < b (n + 1) / a (n + 1)" using a b by simp qed then have "p/q > 0" using pq_def sums_unique by force then have "q\1" "p\1" using \q>0\ by (auto simp add:divide_simps) moreover have "\n. 1 \ a n" "\n. 1 \ b n" using a b by (auto simp add: int_one_le_iff_zero_less) ultimately show ?thesis unfolding ALPHA_def using show7[OF _ _ _ _ pq_def] by auto qed moreover have "\n. ALPHA n < 1" unfolding ALPHA_def proof (rule lasttoshow[OF d a \s>0\ \q>0\ \A>1\ b _ assu3]) show "\\<^sub>F n in sequentially. (\j. b (n+j) / a (n+j)) \ (2 * b n) / a n" using show5[OF \A>1\ d a b assu1 assu3 \convergent_prod d\] by simp show "\m\s. \n\m. d (n+1) * (MAX j\{s..n}. a j powr (1 / of_int (2 ^ j))) \ a (n+1) powr (1 / of_int (2 ^ (n+1)))" apply (rule show9[OF \A>1\ d a \s>0\ assu1 \convergent_prod d\]) using show8[OF \A>1\ d a \s>0\ \convergent_prod d\ assu2] by (simp add:algebra_simps) qed ultimately show False using not_le by blast qed corollary Hancl3corollary: fixes A::real and a b :: "nat\int" assumes "A > 1" and a: "\n. a n>0" and b: "\n. b n>0" and assu1: "(\n. (a n) powr(1 / of_int(2^n))) \ A" and asscor2: "\n \ 6. a n powr(1 / of_int (2^n)) * (1 + 4*(2/3)^n) \ A \ b n \ 2 powr (4/3)^(n-1)" shows "(\n. b n / a n) \ \" proof- define d::"nat\real" where "d= (\ n. 1+(2/3)^(n+1))" have dgt1:"\n. 1 < d n " unfolding d_def by auto moreover have "convergent_prod d" unfolding d_def by (simp add: abs_convergent_prod_imp_convergent_prod summable_imp_abs_convergent_prod) moreover have "\n\6. (\j. d (n+j)) < A / a n powr (1 / of_int (2 ^ n))" proof (intro strip) fix n::nat assume "6 \ n" have d_sum:"summable (\j. ln (d j))" unfolding d_def by (auto intro: summable_ln_plus) have "(\j. ln (d (n + j))) < ln (1+4 * (2/3) ^ n)" proof - define c::real where "c = (2/3) ^ n" have "0n\6\ by (metis le_add_diff_inverse power_add) also have "... \ (2/3)^6" by (auto intro:power_le_one) also have "... < 1/8" by (auto simp add:field_simps) finally show "c < 1/8" . qed (simp add:c_def) have "(\j. ln (d (n + j))) \ (\j. (2/3) ^ (n + j + 1))" proof (rule suminf_le) show "\j. ln (d (n + j)) \ (2/3) ^ (n + j + 1)" unfolding d_def by (metis divide_pos_pos less_eq_real_def ln_add_one_self_le_self zero_less_numeral zero_less_power) show "summable (\j. ln (d (n + j)))" using summable_ignore_initial_segment[OF d_sum] by (force simp add: algebra_simps) show "summable (\j. (2 / 3::real) ^ (n + j + 1))" using summable_geometric[THEN summable_ignore_initial_segment,of "2/3" "n+1"] by (auto simp add:algebra_simps) qed also have "... = (\j. (2/3)^(n+1)*(2/3) ^ j)" by (auto simp add:algebra_simps power_add) also have "... = (2/3)^(n+1) * (\j. (2/3) ^ j)" by (force intro!: summable_geometric suminf_mult) also have "... = 2 * c" unfolding c_def by (simp add: suminf_geometric) also have "... < 4 * c - (4 * c)\<^sup>2" using \0 \c<1/8\ by (sos "((((A<0 * A<1) * R<1) + ((A<=0 * R<1) * (R<1/16 * [1]^2))))") also have "... \ ln (1 + 4 * c)" apply (rule ln_one_plus_pos_lower_bound) using \0 \c<1/8\ by auto finally show ?thesis unfolding c_def by simp qed then have "exp (\j. ln (d (n + j))) < 1 + 4 * (2/3) ^ n" by (smt (z3) divide_pos_pos ln_exp ln_ge_iff zero_less_power) moreover have "exp (\j. ln (d (n + j))) = (\j. d (n + j))" proof (subst exp_suminf_prodinf_real [symmetric]) show "\k. 0 \ ln (d (n + k))" using dgt1 by (simp add: less_imp_le) show "abs_convergent_prod (\na. exp (ln (d (n + na))))" proof (subst exp_ln) show "\j. 0 < d (n + j)" using dgt1 le_less_trans zero_le_one by blast show "abs_convergent_prod (\j. d (n + j))" unfolding abs_convergent_prod_def using \convergent_prod d\ by (simp add: dgt1 convergent_prod_iff_shift less_imp_le algebra_simps) qed show "(\j. exp (ln (d (n + j)))) = (\j. d (n + j))" by (meson dgt1 exp_ln not_less not_one_less_zero order_trans) qed ultimately have "(\j. d (n + j)) < 1 + 4 * (2/3) ^ n" by simp also have "... \ A / (a n) powr (1 / of_int (2 ^ n))" proof - have "a n powr (1 / real_of_int (2 ^ n)) > 0" using a[rule_format,of n] by auto then show ?thesis using asscor2[rule_format,OF \6\n\] by (auto simp add:field_simps) qed finally show "(\j. d (n + j)) < A / real_of_int (a n) powr (1 / of_int (2 ^ n))" . qed moreover have "LIM n sequentially. d n ^ 2 ^ n / real_of_int (b n) :> at_top" proof - have "LIM n sequentially. d n ^ 2 ^ n / 2 powr((4/3)^(n-1)) :> at_top" proof - define n1 where "n1 \ (\n. (2::real) * (3/2)^(n-1))" define n2 where "n2 \ (\n. ((4::real)/3)^(n-1))" have "LIM n sequentially. (((1+(8/9)/(n1 n)) powr (n1 n))/2) powr (n2 n) :> at_top" proof (rule filterlim_at_top_powr_real[where g'="exp (8/9) / 2"]) define e1 where "e1 = exp (8/9) / (2::real)" show "e1>1" unfolding e1_def by (approximation 4) show "(\n. ((1+(8/9)/(n1 n)) powr (n1 n))/2) \ e1" proof - have "(\n. (1+(8/9)/(n1 n)) powr (n1 n)) \ exp (8/9)" apply (rule filterlim_compose[OF tendsto_exp_limit_at_top]) unfolding n1_def by (auto intro!: filterlim_tendsto_pos_mult_at_top filterlim_realpow_sequentially_at_top simp:filterlim_sequentially_iff[of "\x. (3 / 2) ^ (x - Suc 0)" _ 1]) then show ?thesis unfolding e1_def by (intro tendsto_intros,auto) qed show "filterlim n2 at_top sequentially" unfolding n2_def apply (subst filterlim_sequentially_iff[of "\n. (4 / 3) ^ (n - 1)" _ 1]) by (auto intro:filterlim_realpow_sequentially_at_top) qed moreover have "\\<^sub>F n in sequentially. (((1+(8/9)/(n1 n)) powr (n1 n))/2) powr (n2 n) = d n ^ 2 ^ n / 2 powr((4/3)^(n-1))" proof (rule eventually_sequentiallyI) fix k::nat assume "k \ 1" have "((1 + 8 / 9 / n1 k) powr n1 k / 2) powr n2 k = (((1 + 8 / 9 / n1 k) powr n1 k) powr n2 k) / 2 powr (4 / 3) ^ (k - 1)" by (simp add: n1_def n2_def powr_divide) also have "... = (1 + 8 / 9 / n1 k) powr (n1 k * n2 k) / 2 powr (4 / 3) ^ (k - 1)" by (simp add: powr_powr) also have "... = (1 + 8 / 9 / n1 k) powr (2 ^ k) / 2 powr (4 / 3) ^ (k - 1)" proof - have "n1 k * n2 k = 2 ^ k" unfolding n1_def n2_def using \k\1\ by (simp add: mult_ac flip:power_mult_distrib power_Suc) then show ?thesis by simp qed also have "... = (1 + 8 / 9 / n1 k) ^ (2 ^ k) / 2 powr (4 / 3) ^ (k - 1)" unfolding n1_def by (smt (verit, best) powr_realpow divide_pos_pos numeral_plus_numeral numeral_plus_one of_nat_numeral of_nat_power semiring_norm(2) zero_less_power) also have "... = d k ^ 2 ^ k / 2 powr (4 / 3) ^ (k - 1)" proof - have **: "8 / 9 / n1 k = (2/3) ^ (k+1)" unfolding n1_def using \k\1\ by (simp add: divide_simps split: nat_diff_split) then show ?thesis unfolding d_def by presburger qed finally show "((1 + 8 / 9 / n1 k) powr n1 k / 2) powr n2 k = d k ^ 2 ^ k / 2 powr (4 / 3) ^ (k - 1)" . qed ultimately show ?thesis using filterlim_cong by fast qed moreover have "\\<^sub>F n in sequentially. d n ^ 2 ^ n / 2 powr((4/3)^(n-1)) \ d n ^ 2 ^ n / real_of_int (b n)" using eventually_sequentiallyI[of 6] by (smt (verit, best) asscor2 b dgt1 frac_le of_int_0_less_iff zero_le_power) ultimately show ?thesis by (auto elim: filterlim_at_top_mono) qed ultimately show ?thesis using Hancl3[OF \A>1\ _ a b _ assu1,of d 6] by force qed end diff --git a/thys/Transcendence_Series_Hancl_Rucki/Transcendence_Series.thy b/thys/Transcendence_Series_Hancl_Rucki/Transcendence_Series.thy --- a/thys/Transcendence_Series_Hancl_Rucki/Transcendence_Series.thy +++ b/thys/Transcendence_Series_Hancl_Rucki/Transcendence_Series.thy @@ -1,1042 +1,1028 @@ (* Title: Transcendence_Series.thy Authors: Angeliki Koutsoukou-Argyraki and Wenda Li, University of Cambridge *) section \The transcendence of certain infinite series\ theory "Transcendence_Series" imports "HOL-Analysis.Multivariate_Analysis" "HOL-Computational_Algebra.Polynomial" Prime_Number_Theorem.Prime_Number_Theorem_Library begin text \ We formalise the proofs of two transcendence criteria by J. Han\v{c}l and P. Rucki that assert the transcendence of the sums of certain infinite series built up by sequences that fulfil certain properties (Theorems 2.1 and 2.2 in \cite{hancl2005}, HanclRucki1 and HanclRucki2 here respectively). Both proofs make use of Roth's celebrated theorem on diophantine approximations to algebraic numbers from 1955 \cite{roth_1955} which we assume and implement within the locale RothsTheorem. -A small mistake was detected in the original proof of Theorem 2.1, and the authors suggested -to us a fix for the problem (in communication by email). +A small mistake was detected in the original proof of Theorem 2.1, and the authors gave us a fix for the problem (by email). Our formalised proof incorporates this correction (see the Remark in the proof of HanclRucki1). \ subsection \Misc\ lemma powr_less_inverse_iff: fixes x y z::real - assumes "x>0""y>0""z>0" + assumes "x>0" "y>0" "z>0" shows "x powr y < z \ x < z powr (inverse y)" proof assume "x powr y < z" from powr_less_mono2[OF _ _ this,of "inverse y"] show "x < z powr inverse y" using assms by (auto simp:powr_powr) next assume *:"x < z powr inverse y" from powr_less_mono2[OF _ _ *,of y] show "x powr y < z" using assms by (auto simp:powr_powr) qed lemma powr_less_inverse_iff': fixes x y z::real - assumes "x>0""y>0""z>0" + assumes "x>0" "y>0" "z>0" shows "z< x powr y \ z powr (inverse y) < x" using powr_less_inverse_iff[symmetric,of _ "inverse y"] assms by auto lemma powr_less_eq_inverse_iff: fixes x y z::real - assumes "x>0""y>0""z>0" + assumes "x>0" "y>0" "z>0" shows "x powr y \ z \ x \ z powr (inverse y)" - by (meson assms(1) assms(2) assms(3) not_less powr_less_inverse_iff') + by (meson assms not_less powr_less_inverse_iff') lemma powr_less_eq_inverse_iff': fixes x y z::real - assumes "x>0""y>0""z>0" - shows "z\ x powr y \ z powr (inverse y) \ x" - by (simp add: assms(1) assms(2) assms(3) powr_less_eq_inverse_iff) + assumes "x>0" "y>0" "z>0" + shows "z \ x powr y \ z powr (inverse y) \ x" + by (simp add: assms powr_less_eq_inverse_iff) lemma tendsto_PInfty_mono: assumes "(ereal o f) \ \" "\\<^sub>F x in sequentially. f x \ g x" shows "(ereal o g) \ \" using assms unfolding comp_def tendsto_PInfty_eq_at_top by (elim filterlim_at_top_mono, simp) lemma limsup_infinity_imp_Inf_many: assumes "limsup f = \" shows "(\ m. (\\<^sub>\i. f i > ereal m))" unfolding INFM_nat proof (clarify,rule ccontr) fix m k assume "\ (\n>k. ereal m < f n)" then have "\n>k. f n \ ereal m" by auto then have "\\<^sub>F n in sequentially. f n \ ereal m" using eventually_at_top_dense by blast then have "limsup f \ ereal m" using Limsup_bounded by auto then show False using assms by simp qed lemma snd_quotient_plus_leq: defines "de\(snd o quotient_of)" shows "de (x+y) \ de x * de y " proof - obtain x1 x2 y1 y2 where xy: "quotient_of x = (x1,x2)" "quotient_of y=(y1,y2)" by (meson surj_pair) have "x2>0" "y2>0" using xy quotient_of_denom_pos by blast+ then show ?thesis unfolding de_def comp_def rat_plus_code xy apply (auto split:prod.split simp:Rat.normalize_def Let_def) by (smt div_by_1 gcd_pos_int int_div_less_self mult_eq_0_iff mult_sign_intros(1)) qed lemma quotient_of_inj: "inj quotient_of" unfolding inj_def by (simp add: quotient_of_inject) lemma infinite_inj_imageE: assumes "infinite A" "inj_on f A" "f ` A \ B" shows "infinite B" using assms inj_on_finite by blast lemma incseq_tendsto_limsup: fixes f::"nat \ 'a::{complete_linorder,linorder_topology}" assumes "incseq f" shows "f \ limsup f" using LIMSEQ_SUP assms convergent_def convergent_ereal tendsto_Limsup trivial_limit_sequentially by blast subsection \Main proofs\ -text \Since the proof of Roths theorem has not been formalized yet, we implement it into a locale - and used it as an assumption.\ +text \Since the proof of Roth's theorem has not been formalized yet, we formalize the statement in a locale + and use it as an assumption.\ locale RothsTheorem = assumes RothsTheorem:"\\ \. algebraic \ \ \ \ \ \ infinite {(p,q). q>0 \ coprime p q \ \\ - of_int p / of_int q\ < 1 / q powr \} \ \ \ 2" theorem (in RothsTheorem) HanclRucki1: fixes a b ::"nat\int" and \ ::real defines "aa\(\n. real_of_int (a n))" and "bb\(\n. real_of_int (b n))" assumes a_pos:"\ k. a k >0" and b_pos:"\ k. b k >0" and "\ >0" and limsup_infy:"limsup (\ k. aa (k+1)/(\i = 0..k. aa i)powr(2+\)*(1/bb (k+1))) = \" and liminf_1:"liminf (\k. aa (k+1) / aa k * bb k / bb (k+1)) > 1" shows "\ algebraic(suminf (\ k. bb k / aa k))" proof - have summable:"summable (\ k. bb k / aa k)" proof (rule ratio_test_convergence) have [simp]:"aa k>0" "bb k>0" for k unfolding aa_def bb_def using a_pos b_pos by auto show "\\<^sub>F n in sequentially. 0 < bb n / aa n" - apply (rule eventuallyI) by auto show "1 < liminf (\n. ereal (bb n / aa n / (bb (Suc n) / aa (Suc n))))" using liminf_1 by (auto simp:algebra_simps) qed have [simp]: "aa k>0" "bb k>0" for k unfolding aa_def bb_def by (auto simp add: a_pos b_pos) have ab_1:"aa k\1" "bb k\1" for k unfolding aa_def bb_def using a_pos b_pos by (auto simp add: int_one_le_iff_zero_less) - define B where "B=liminf (\x. ereal (aa (x + 1) / aa x * bb x / bb (x + 1)))" - define M where "M= (case B of ereal m \ (m+1)/2 | _ \ 2)" + define B where "B \ liminf (\x. ereal (aa (x + 1) / aa x * bb x / bb (x + 1)))" + define M where "M \ (case B of ereal m \ (m+1)/2 | _ \ 2)" have "M > 1" "M < B" using liminf_1 unfolding M_def - apply (fold B_def) - by (cases B,auto)+ + by (auto simp add: M_def B_def split: ereal.split) text \ Remark: In the original proof of Theorem 2.1 in \cite{hancl2005} it was claimed in p.534 that from assumption (3) (i.e. @{thm liminf_1}), we obtain that: $\forall A>1~\exists k_0~ \forall k > k_0~ \frac{1}{A} \frac{b_k}{ a_k} > \frac{ b_{k+1}}{ a_{k+1}} $, however note the counterexample where $a_{k+1}= k (a_1 a_2 ... a_k)^{\lceil 2+ \delta \rceil}$ if k is odd, and $a_{k+1} = 2 a_k$ otherwise, with $b_k =1$ for all $k$. In commmunication by email the authors suggested to replace the claim $\forall A>1~\exists k_0~ \forall k > k_0~ \frac{1}{A} \frac{b_k}{ a_k} > \frac{ b_{k+1}}{ a_{k+1}} $ with $\exists A>1~\exists k_0~ \forall k > k_0~ \frac{1}{A} \frac{b_k}{ a_k} > \frac{ b_{k+1}}{ a_{k+1}} $ which solves the problem and the proof proceeds as in the paper. The witness for $\exists A>1 $ is denoted by $M$ here.\ have bb_aa_event:"\\<^sub>F k in sequentially. (1/M)*(bb k / aa k)> bb(k+1)/ aa (k+1)" using less_LiminfD[OF \M < B\[unfolded B_def],simplified] - apply eventually_elim - using \M > 1\ by (auto simp:divide_simps algebra_simps) + by eventually_elim (use \M > 1\ in \auto simp: field_simps\) have bb_aa_p:"\\<^sub>F k in sequentially. \p. bb(k+p)/ aa (k+p) \ (1/M^p)*(bb k / aa k)" proof - obtain k0 where k0_ineq: "\n\k0. bb (n + 1) / aa (n + 1) < 1 / M * (bb n / aa n)" using bb_aa_event unfolding eventually_sequentially by auto have "bb(k+p)/ aa (k+p) \ (1/M^p)*(bb k / aa k)" when "k\k0" for p k proof (induct p) case 0 then show ?case by auto next case (Suc p) have " bb (k + Suc p) / aa (k + Suc p) < 1 / M * (bb (k+p) / aa (k+p))" using k0_ineq[rule_format,of "k+p"] that by auto also have "... \ 1 / M ^(Suc p) * (bb k / aa k)" using Suc \M>1\ by (auto simp add:field_simps) finally show ?case by auto qed then show ?thesis unfolding eventually_sequentially by auto qed define \ where "\ = suminf (\ k. bb k / aa k)" have \_Inf_many:"\\<^sub>\ k. \\ - (\k = 0..k. bb k / aa k)\ < 1 / prod aa {0..k} powr (2 + \)" proof - - have "\\ - (\i = 0..k. bb i / aa i)\ = \\i. bb (i+(k+1)) / aa (i+(k+1))\" - for k + have "\\ - (\i = 0..k. bb i / aa i)\ = \\i. bb (i+(k+1)) / aa (i+(k+1))\" for k unfolding \_def apply (subst suminf_minus_initial_segment[of _ "k+1",OF summable]) using atLeast0AtMost lessThan_Suc_atMost by auto - + moreover have "\\<^sub>\ k. \\i. bb(i+(k+1))/ aa (i+(k+1))\ < 1 / prod aa {0..k} powr (2 + \)" proof - - define P where "P = (\ i. \p. bb (i + 1 + p) / aa (i + 1 + p) + define P where "P \ (\ i. \p. bb (i + 1 + p) / aa (i + 1 + p) \ 1 / M ^ p * (bb (i + 1) / aa (i + 1)))" - define Q where "Q= (\ i. ereal (M / (M - 1)) + define Q where "Q \ (\ i. ereal (M / (M - 1)) < ereal (aa (i + 1) / prod aa {0..i} powr (2 + \) * (1 / bb (i + 1))))" have "\\<^sub>\ i. P i" using bb_aa_p[THEN sequentially_offset, of 1] cofinite_eq_sequentially unfolding P_def by auto moreover have "\\<^sub>\i. Q i" using limsup_infy[THEN limsup_infinity_imp_Inf_many,rule_format,of "(M / (M -1))"] unfolding Q_def . moreover have "\\i. bb(i+(k+1))/ aa (i+(k+1))\ < 1 / prod aa {0..k} powr (2 + \)" when "P k" "Q k" for k proof - have summable_M:"summable (\i. 1 / M ^ i)" apply (rule summable_ratio_test[of "1/M"]) using \M>1\ by auto have "(\i. bb (i + (k + 1)) / aa (i + (k + 1))) \ 0" apply (rule suminf_nonneg) subgoal using summable_ignore_initial_segment[OF summable,of "k+1"] by auto subgoal by (simp add: less_imp_le) done then have "\\i. bb (i + (k + 1)) / aa (i + (k + 1))\ = (\i. bb (i + (k + 1)) / aa (i + (k + 1)))" by auto also have "... \ (\i. 1 / M ^ i * (bb (k + 1) / aa (k + 1)))" apply (rule suminf_le) subgoal using that(1) unfolding P_def by (auto simp add:algebra_simps) subgoal using summable_ignore_initial_segment[OF summable,of "k+1"] by auto subgoal using summable_mult2[OF summable_M,of " bb (k + 1) / aa (k + 1)"] by auto done also have "... = (bb (k + 1) / aa (k + 1)) * (\i. 1 / M ^ i)" using suminf_mult2[OF summable_M,of " bb (k + 1) / aa (k + 1)"] by (auto simp:algebra_simps) also have "... = (bb (k + 1) / aa (k + 1)) * (\i. (1 / M) ^ i)" using \M>1\ by (auto simp: field_simps) also have "... = (bb (k + 1) / aa (k + 1)) * (M / (M -1))" apply (subst suminf_geometric) using \M>1\ by (auto simp: field_simps) also have "... < (bb (k + 1) / aa (k + 1)) * (aa (k + 1) / prod aa {0..k} powr (2 + \) * (1 / bb (k + 1)))" apply (subst mult_less_cancel_left_pos) using that(2) unfolding Q_def by auto also have "... = 1/ prod aa {0..k} powr (2 + \)" using ab_1[of "Suc k"] by auto finally show ?thesis . qed ultimately show ?thesis by (smt INFM_conjI INFM_mono) qed ultimately show ?thesis by auto qed - define pq where "pq = (\k. quotient_of (\i=0..k. of_int (b i) / of_int (a i)))" - define p q where "p = fst \ pq" and "q = snd \ pq" + define pq where "pq \ (\k. quotient_of (\i=0..k. of_int (b i) / of_int (a i)))" + define p q where "p \ fst \ pq" and "q = snd \ pq" have coprime_pq:"coprime (p k) (q k)" and q_pos:"q k > 0" and pq_sum:"p k / q k = (\i=0..k. b i / a i)" for k proof - have eq: "quotient_of (\i=0..k. of_int (b i) / of_int (a i)) = (p k, q k)" by (simp add: p_def q_def pq_def) from quotient_of_coprime[OF eq] show "coprime (p k) (q k)" . from quotient_of_denom_pos[OF eq] show "q k > 0" . have "(\i=0..k. b i / a i) = of_rat (\i=0..k. of_int (b i) / of_int (a i))" by (simp add: of_rat_sum of_rat_divide) also have "(\i=0..k. rat_of_int (b i) / rat_of_int (a i)) = rat_of_int (p k) / rat_of_int (q k)" using quotient_of_div[OF eq] by simp finally show "p k / q k = (\i=0..k. b i / a i)" by (simp add:of_rat_divide) qed - have \_Inf_many2:"\\<^sub>\ k. \\ - p k / q k\ - < 1 / q k powr (2 + \)" + have \_Inf_many2:"\\<^sub>\ k. \\ - p k / q k\ < 1 / q k powr (2 + \)" using \_Inf_many proof (elim INFM_mono) fix k assume asm:"\\ - (\k = 0..k. bb k / aa k)\ < 1 / prod aa {0..k} powr (2 + \)" have "\\ - real_of_int (p k) / real_of_int (q k)\ = \\ - (\k = 0..k. bb k / aa k)\" using pq_sum unfolding aa_def bb_def by auto also have "... < 1 / prod aa {0..k} powr (2 + \)" using asm by auto also have "... \ 1 / q k powr (2 + \)" proof - have "q k \ prod aa {0..k}" proof (induct k) case 0 then show ?case unfolding q_def pq_def aa_def apply (simp add:rat_divide_code of_int_rat quotient_of_Fract) using ab_1[of 0,unfolded aa_def bb_def] unfolding Let_def normalize_def apply auto by (metis div_by_1 gcd_pos_int less_imp_le less_trans nonneg1_imp_zdiv_pos_iff not_less zdiv_mono2) next case (Suc k) - define de where "de=snd \ quotient_of" + define de where "de \snd \ quotient_of" have "real_of_int (q (Suc k)) = de (\i=0..Suc k. of_int (b i) / of_int (a i))" unfolding q_def pq_def de_def by simp also have "... = de ((\i=0..k. of_int (b i) / of_int (a i)) + of_int (b (Suc k)) / of_int (a (Suc k)))" by simp also have "... \ de (\i=0..k. of_int (b i) / of_int (a i)) * de (of_int (b (Suc k)) / of_int (a (Suc k)))" using snd_quotient_plus_leq[folded de_def] by presburger also have "... = q k * de (of_int (b (Suc k)) / of_int (a (Suc k)))" unfolding q_def pq_def de_def by auto also have "... = q k * snd (Rat.normalize (b (Suc k), a (Suc k)))" by (simp add:rat_divide_code of_int_rat quotient_of_Fract de_def) also have "... \ q k * aa (Suc k)" using ab_1[of "Suc k"] q_pos[of "k"] unfolding normalize_def aa_def bb_def Let_def apply auto by (metis div_by_1 int_one_le_iff_zero_less less_trans nonneg1_imp_zdiv_pos_iff not_less zdiv_mono2 zero_less_one) also have "... \ prod aa {0..k} * aa (Suc k)" using Suc ab_1[of "Suc k"] by auto also have "... = prod aa {0..Suc k}" by (simp add: prod.atLeast0_atMost_Suc) finally show ?case . qed then show ?thesis by (smt \0 < \\ frac_le of_int_0 of_int_le_iff powr_gt_zero powr_mono2 q_pos) qed finally show "\\ - real_of_int (p k) / real_of_int (q k)\ < 1 / real_of_int (q k) powr (2 + \)" . qed - define pqs where "pqs={(p, q). q>0 \ coprime p q + define pqs where "pqs \{(p, q). q>0 \ coprime p q \ \\ - real_of_int p / real_of_int q\ < 1 / q powr (2 + \)}" have \_infinite:"infinite pqs" proof - - define A where "A={k. \\ - (p k) / (q k)\ < 1 / (q k) powr (2 + \)}" + define A where "A \ {k. \\ - (p k) / (q k)\ < 1 / (q k) powr (2 + \)}" have "\\<^sub>\ k. \\ - p k / q k\ < 1 / q k powr (2 + \)" using \_Inf_many2 . then have "infinite A" unfolding Inf_many_def A_def by auto moreover have "inj_on (\k. (p k, q k)) A" proof - - define g where "g=(\i. rat_of_int (b i) / rat_of_int (a i))" - define f where "f=(\k. \i = 0..k. g i)" + define g where "g \ (\i. rat_of_int (b i) / rat_of_int (a i))" + define f where "f \ (\k. \i = 0..k. g i)" have g_pos:"g i>0" for i unfolding g_def by (simp add: a_pos b_pos) have "strict_mono f" unfolding strict_mono_def f_def proof safe fix x y::nat assume "x < y" then have "sum g {0..y} - sum g {0..x} = sum g {x<..y}" apply (subst Groups_Big.sum_diff[symmetric]) by (auto intro:arg_cong2[where f=sum]) also have "... > 0" apply (rule ordered_comm_monoid_add_class.sum_pos) using \x g_pos by auto finally have "sum g {0..y} - sum g {0..x} >0" . then show "sum g {0..x} < sum g {0..y}" by auto qed then have "inj f" using strict_mono_imp_inj_on by auto then have "inj (quotient_of o f)" by (simp add: inj_compose quotient_of_inj) then have "inj (\k. (p k, q k))" unfolding f_def p_def q_def pq_def comp_def apply (fold g_def) by auto then show ?thesis by (auto elim:subset_inj_on) qed moreover have "(\k. (p k, q k)) ` A \ pqs" unfolding A_def pqs_def using coprime_pq q_pos by auto ultimately show ?thesis apply (elim infinite_inj_imageE) by auto qed moreover have "finite pqs" if "\ \ \" proof - obtain m n where \_mn:"\ = (of_int m / of_int n)" and "coprime m n" "n>0" proof - obtain m n where mn:"\\\ = (of_nat m / of_nat n)" "coprime m n" "n\0" using Rats_abs_nat_div_natE[OF \\ \ \\ Rats_abs_nat_div_natE] by metis define m' and n'::int where "m'=(if \ > 0 then nat m else -nat m)" and "n'=nat n" then have "\ = (of_int m' / of_int n')" "coprime m' n'" "n'>0" using mn by auto then show ?thesis using that by auto qed have "pqs \ {(m,n)} \ {x. x \pqs \ - \m\ - 1 \fst x \ fst x \ \m\ + 1 \ 0 snd x < n }" proof (rule subsetI) fix x assume "x \ pqs" - define p q where "p=fst x" and "q=snd x" + define p q where "p \ fst x" and "q=snd x" have "q>0" "coprime p q" and pq_less:"\\ - p / q\ < 1 / q powr (2 + \)" using \x\pqs\ unfolding p_def q_def pqs_def by auto have q_lt_n:"qp \ n\q" proof - have "m * q \ n * p" using that \coprime m n\ \coprime p q\ \q>0\ \n>0\ by (metis eq_rat(1) fst_conv int_one_le_iff_zero_less mult.commute normalize_stable not_one_le_zero quotient_of_Fract snd_conv) then have "1/(n*q) \ \m/n - p/q\" using \q>0\ \n>0\ apply (auto simp:field_simps) by (metis add_diff_cancel_left' diff_diff_eq2 diff_zero less_irrefl not_le of_int_diff of_int_lessD of_int_mult) also have "... < 1 / q powr (2 + \)" using pq_less unfolding \_mn by auto also have "... \ 1 / q ^2" proof - have "real_of_int (q\<^sup>2) = q powr 2" apply (subst powr_numeral) unfolding power2_eq_square using \q>0\ by auto also have "... \ q powr (2 + \)" apply (rule powr_mono) using \q>0\ \\>0\ by auto finally have "real_of_int (q\<^sup>2) \ real_of_int q powr (2 + \)" . moreover have "real_of_int q powr (2 + \) > 0" using \0 < q\ by auto ultimately show ?thesis by (auto simp:field_simps) qed finally have " 1 / (n * q) < 1 / q\<^sup>2" . then show ?thesis using \q>0\ \n>0\ unfolding power2_eq_square by (auto simp:field_simps) qed moreover have "- \m\ - 1 \ p \ p \ \m\ + 1" when "m\p \ n\q" proof - - define qn where "qn=q/n" + define qn where "qn \ q/n" have "0m\p \ n\q\] \q>0\ by auto have "\m/n - p / q\ < 1 / q powr (2 + \)" using pq_less unfolding \_mn by simp then have "\p / q - m/n\ < 1 / q powr (2 + \)" by simp then have " m/n- 1 / q powr (2 + \) < p/q \ p/q < m/n + 1 / q powr (2 + \)" unfolding abs_diff_less_iff by auto then have "qn*m- q / q powr (2 + \) < p \ p < qn*m + q / q powr (2 + \)" unfolding qn_def using \q>0\ by (auto simp:field_simps) moreover have "- \m\ - 1 \ qn*m- q / q powr (2 + \)" proof - have "- \m\ \ qn*m" using \0 \qn<1\ apply (cases "m\0") subgoal apply simp by (meson less_eq_real_def mult_nonneg_nonneg neg_le_0_iff_le of_int_0_le_iff order_trans) subgoal by simp done moreover have "- 1 \ - q / q powr (2 + \)" proof - have "q = q powr 1" using \0 < q\ by auto also have "... \q powr (2 + \)" apply (rule powr_mono) using \q>0\ \\>0\ by auto finally have "q \ q powr (2 + \)" . then show ?thesis using \0 < q\ by auto qed ultimately show ?thesis by auto qed moreover have "qn*m + q / q powr (2 + \) \ \m\ + 1" proof - have "qn*m \ \m\" using \0 \qn<1\ apply (cases "m\0") subgoal by (simp add: mult_left_le_one_le) subgoal by (smt of_int_0_le_iff zero_le_mult_iff) done moreover have "q / q powr (2 + \) \ 1" proof - have "q = q powr 1" using \0 < q\ by auto also have "... \q powr (2 + \)" apply (rule powr_mono) using \q>0\ \\>0\ by auto finally have "q \ q powr (2 + \)" . then show ?thesis using \0 < q\ by auto qed ultimately show ?thesis by auto qed ultimately show ?thesis by auto qed ultimately show "x \ {(m, n)} \ {x \ pqs. - \m\ - 1 \ fst x \ fst x \ \m\ + 1 \ 0 < snd x \ snd x < n}" using \x \ pqs\ \q>0\ unfolding p_def q_def by force qed moreover have "finite {x. x \pqs \ - \m\ - 1 \fst x \ fst x \ \m\ + 1 \ 0 snd x < n }" proof - have "finite ({- \m\ - 1..\m\ +1} \ {0<..pqs \ - \m\ - 1 \fst x \ fst x \ \m\ + 1 \ 0 snd x < n } \ ({- \m\ - 1..\m\ +1} \ {0<.._def) using RothsTheorem[rule_format,of \ "2 + \",folded pqs_def] \\ >0\ by auto qed theorem (in RothsTheorem) HanclRucki2: fixes a b ::"nat\int" and \ \ ::real defines "aa\(\n. real_of_int (a n))" and "bb\(\n. real_of_int (b n))" assumes a_pos:"\ k. a k >0" and b_pos:"\ k. b k >0" and "\ >0" and "\ >0" and limsup_infi:"limsup (\ k.(aa (k+1)/(\i = 0..k. aa i)powr(2+(2/\) + \)) * (1/(bb (k+1)))) = \" and ratio_large:"\ k. ( k \ t \ (( aa(k+1)/bb( k+1)) ) powr(1/(1+\)) \ (( aa k/bb k) powr(1/(1+\)))+1)" shows "\ algebraic(suminf (\ k. bb k /aa k)) " proof- have aa_bb_pos[simp]:"aa k>0" "bb k>0" for k unfolding aa_def bb_def using a_pos b_pos by auto have summable:"summable (\ k. bb k / aa k)" proof - define c0 where "c0\(aa t/bb t) powr(1/(1+\)) - t" have ab_k:"(aa k / bb k) powr(1/(1+\)) \ k + c0" when "k\t" for k using that proof (induct k) case 0 then show ?case unfolding c0_def by simp next case (Suc k) have ?case when "\ t\k" proof - have "t = Suc k" using that Suc.prems by linarith then show ?thesis unfolding c0_def by auto qed moreover have ?case when "t \ k" proof - have "(aa(k+1)/bb(k+1)) powr(1/(1+\)) \ ( aa k/bb k) powr(1/(1+\))+1" using ratio_large[rule_format,OF that] by blast then show ?thesis using Suc(1)[OF that] by simp qed ultimately show ?case by auto qed have "summable (\k. 1 / (k + c0) powr (1+\))" proof - have "c0 + t > 0" unfolding c0_def using aa_bb_pos[of t] by (simp,linarith) then have "summable (\k. 1 / (k + (c0+t)) powr (1+\))" using summable_hurwitz_zeta_real[of "1+\" "c0+t"] apply (subst (asm) powr_minus_divide) using \\>0\ by auto then show ?thesis apply (rule_tac summable_offset[of _ t]) by (auto simp:algebra_simps) qed moreover have "bb k / aa k \ 1 / (k + c0) powr (1+\)" when "k\t" for k proof - have "(aa t / bb t) powr (1 / (1 + \)) > 0" apply simp by (metis \\k. 0 < aa k\ \\k. 0 < bb k\ less_numeral_extra(3)) then have "k + c0 >0" unfolding c0_def using that by linarith then have "aa k / bb k \ (k + c0) powr (1+\)" using ab_k[OF that] apply (subst (asm) powr_less_eq_inverse_iff') using \\ >0\ by auto then have "inverse (aa k / bb k) \ inverse ((k + c0) powr (1+\))" apply (elim le_imp_inverse_le) using \k + c0 >0\ by auto then show ?thesis by (simp add: inverse_eq_divide) qed ultimately show ?thesis apply (elim summable_comparison_test'[where N=t]) using aa_bb_pos by (simp add: less_eq_real_def) qed have 7:"\\<^sub>\ k. 1 / (M powr (\/(1+\)) * (\i = 0..k. aa i) powr(2+ \ * \ / (1+\))) > (bb (k+1) / aa(k+1)) powr (\ / (1+\))" when "M > 0" for M proof - - define tt where "tt= (\i. prod aa {0..i} powr (2 + 2 / \ + \))" + define tt where "tt \ (\i. prod aa {0..i} powr (2 + 2 / \ + \))" have tt_pos:"tt i > 0" for i unfolding tt_def apply(subst powr_gt_zero,induct i) subgoal by (metis aa_bb_pos(1) order_less_irrefl prod_pos) subgoal by (metis \\k. 0 < aa k\ order_less_irrefl prod_pos) done have "\\<^sub>\i. M < (aa (i + 1) / tt i * (1 / bb (i + 1)))" using limsup_infinity_imp_Inf_many[OF limsup_infi,rule_format,of M] unfolding tt_def by auto then have "\\<^sub>\i. 1 / (M * tt i) > (bb (i+1) / aa (i+1))" apply (elim INFM_mono) using \M>0\ tt_pos by (auto simp:divide_simps algebra_simps) then have "\\<^sub>\i. (1 / (M * tt i)) powr (\/(1+\)) > (bb (i+1) / aa (i+1)) powr (\/(1+\))" apply (elim INFM_mono powr_less_mono2[rotated 2]) by (simp_all add: assms(6) pos_add_strict less_eq_real_def) moreover have "tt i powr (\/(1+\)) = prod aa {0..i} powr (2 + \ * \ / (1+\))" for i unfolding tt_def apply (auto simp:powr_powr) using \\>0\ by (simp add:divide_simps,simp add:algebra_simps) ultimately show ?thesis apply (elim INFM_mono) by (smt nonzero_mult_div_cancel_left powr_divide powr_mult powr_one_eq_one that tt_pos zero_less_divide_iff) qed have 8:"\\<^sub>F k in sequentially. \s. (( aa(k+s)/bb( k+s))) \ ((( aa k/bb k) powr(1/(1+\))) +s)powr(1+\)" using eventually_ge_at_top[of t] proof eventually_elim case (elim k) - define ff where "ff=(\k. (aa k / bb k) powr (1 / (1 + \)))" + define ff where "ff \ (\k. (aa k / bb k) powr (1 / (1 + \)))" have 11:"ff k+s \ ff (k+s)" for s proof (induct s) case 0 then show ?case unfolding ff_def by auto next case (Suc s) then have "ff k + Suc s \ ff (k+Suc s)" using ratio_large[rule_format,of "k+s"] \ t \ k\ unfolding ff_def by auto then show ?case by simp qed then have "(ff k+s) powr (1+\) \ ff (k+s) powr (1+\)" for s apply (rule powr_mono2[of "1+\",rotated 2]) unfolding ff_def using \\>0\ by auto then show ?case unfolding ff_def using \\>0\ apply (auto simp add:powr_powr) by (simp add: a_pos aa_def b_pos bb_def le_less) qed have 9: "(\r. 1/((z+real r)powr(1+\))) \ 1/(\ *(z-1) powr \)" "summable (\i. 1/((z+ real i)powr(1+\)))" when "z>1" for z proof - - define f where "f= (\r. 1/((z+ r)powr(1+\)))" + define f where "f \ (\r. 1/((z+ r)powr(1+\)))" have "((\x. f (x - 1)) has_integral ((z-1) powr - \) / \) {0..}" proof - have "((\x. (z-1 + x) powr (- 1 - \)) has_integral ((z-1) powr - \) / \) {0<..}" using powr_has_integral_at_top[of 0 "z-1" "- 1 - \",simplified] \z>1\ \\>0\ by auto then have "((\x. (z-1 + x) powr (- 1 - \)) has_integral ((z-1) powr - \) / \) {0..}" apply (subst (asm) has_integral_closure[symmetric]) by (auto simp add: negligible_convex_frontier) then show ?thesis apply (rule has_integral_cong[THEN iffD1, rotated 1]) unfolding f_def by (smt powr_minus_divide) qed moreover have "\x. 0 \ x \ 0 \ f (x - 1)" unfolding f_def by simp moreover have "\x y. 0 \ x \ x \ y \ f (y - 1) \ f (x - 1)" unfolding f_def by (smt assms(6) frac_le powr_mono2 powr_nonneg_iff that) ultimately have "summable (\i. f (real i))" "(\i. f (real i)) \ (z - 1) powr - \ / \" using decreasing_sum_le_integral[of "\x. f (x-1)" "((z-1) powr - \) / \",simplified] by auto moreover have "(z - 1) powr - \ / \ = 1/(\ *(z-1) powr \)" by (simp add: powr_minus_divide) ultimately show "(\i. f (real i)) \ 1/(\ *(z-1) powr \)" by auto show "summable (\i. f (real i))" using \summable (\i. f (real i))\ . qed have u:"(\k.( aa k / bb k)) \ \" proof - define ff where "ff\(\x. ereal (aa x / bb x))" have "limsup ff = \" proof - - define tt where "tt= (\i. prod aa {0..i} powr (2 + 2 / \ + \))" + define tt where "tt \ (\i. prod aa {0..i} powr (2 + 2 / \ + \))" have "tt i \ 1" for i unfolding tt_def apply (rule ge_one_powr_ge_zero) subgoal apply (rule linordered_nonzero_semiring_class.prod_ge_1) by (simp add: a_pos aa_def int_one_le_iff_zero_less) subgoal by (simp add: \\>0\ \\>0\ less_imp_le) done then have "limsup (\x. (aa (x + 1) / tt x * (1 / bb (x + 1)))) \ limsup (\x. aa (x + 1) / bb (x + 1))" apply (intro Limsup_mono eventuallyI) apply (auto simp add:field_simps order.order_iff_strict) by (metis aa_bb_pos(1) div_by_1 frac_less2 less_irrefl less_numeral_extra(1) not_le) also have "... = limsup (\x. aa x / bb x)" by (subst limsup_shift,simp) finally have "limsup (\x. ereal (aa (x + 1) / tt x * (1 / bb (x + 1)))) \ limsup (\x. ereal (aa x / bb x))" . moreover have "limsup (\x. ereal (aa (x + 1) / tt x * (1 / bb (x + 1)))) = \" using limsup_infi unfolding tt_def by auto ultimately show ?thesis unfolding ff_def using ereal_infty_less_eq2(1) by blast qed then have "limsup (\k. ff (k+t)) = \" by (simp add: limsup_shift_k) moreover have "incseq (\k. ff (k+t))" proof (rule incseq_SucI) fix k::nat define gg where "gg\(\x. (aa x / bb x))" have "(gg (k+t)) powr (1 / (1 + \)) + 1 \ (gg (Suc (k+t))) powr (1 / (1 + \))" using ratio_large[rule_format, of "k+t",simplified] unfolding gg_def by auto then have "(gg (k+t)) powr (1 / (1 + \)) \ (gg (Suc (k+t))) powr (1 / (1 + \))" by auto then have "gg (k+t)\ gg (Suc (k+t))" by (smt aa_bb_pos(1) aa_bb_pos(2) assms(6) divide_pos_pos gg_def powr_less_mono2) then show "ff (k + t) \ ff (Suc k + t)" unfolding gg_def ff_def by auto qed ultimately have "(\k. ff (k+t)) \ \" using incseq_tendsto_limsup by fastforce then show ?thesis unfolding ff_def unfolding tendsto_def apply (subst eventually_sequentially_seg[symmetric,of _ t]) by simp qed define \ where "\ = suminf (\ k. bb k / aa k)" have 10:"\\<^sub>F k in sequentially. \\ - (\k = 0..k. bb k / aa k)\ < 2 / \ * (bb (k+1) / aa (k+1)) powr (\ / (1+\))" using 8[THEN sequentially_offset,of 1] eventually_ge_at_top[of t] u[unfolded tendsto_PInfty,rule_format,THEN sequentially_offset ,of "(2 powr (1/\) / (2 powr (1/\) - 1)) powr (1+\)" 1] proof eventually_elim case (elim k) - define tt where "tt=(aa (k + 1) / bb (k + 1)) powr (1 / (1 + \))" + define tt where "tt \ (aa (k + 1) / bb (k + 1)) powr (1 / (1 + \))" have "tt>1" proof - have "(aa k / bb k) powr (1 / (1 + \)) > 0" by (metis a_pos aa_def b_pos bb_def divide_eq_0_iff less_irrefl of_int_eq_0_iff powr_gt_zero) then show ?thesis using ratio_large[rule_format,OF \k\t\] unfolding tt_def by argo qed have "\\ - (\i = 0..k. bb i / aa i)\ = \\i. bb (i+(k+1)) / aa (i+(k+1))\" unfolding \_def apply (subst suminf_minus_initial_segment[of _ "k+1",OF summable]) using atLeast0AtMost lessThan_Suc_atMost by auto also have "... = (\i. bb (i+(k+1)) / aa (i+(k+1)))" proof - have "(\i. bb (i+(k+1)) / aa (i+(k+1))) > 0" apply (rule suminf_pos) subgoal using summable[THEN summable_ignore_initial_segment,of "k+1"] . subgoal by (simp add: a_pos aa_def b_pos bb_def) done then show ?thesis by auto qed also have "... \ (\i. 1 / (tt + i) powr (1 + \))" proof (rule suminf_le) - define ff where "ff=(\k n. (aa (k+1) / bb (k+1)) powr (1 / (1 + \)) + real n)" + define ff where "ff \ (\k n. (aa (k+1) / bb (k+1)) powr (1 / (1 + \)) + real n)" have "bb (n + (k + 1)) / aa (n + (k + 1)) \ 1 / (ff k n) powr (1 + \)" for n proof - have "ff k n powr (1 + \) \ aa (k + n +1 ) / bb (k + n+1 )" using elim(1)[rule_format,of n] unfolding ff_def by auto moreover have "ff k n powr (1 + \) > 0" unfolding ff_def by (smt elim(2) of_nat_0_le_iff powr_gt_zero ratio_large) ultimately have "1 / ff k n powr (1 + \) \ bb (k + (n + 1)) / aa (k + (n + 1))" apply (drule_tac le_imp_inverse_le) by (auto simp add: inverse_eq_divide) then show ?thesis by (auto simp:algebra_simps) qed then show "\n. bb (n + (k + 1)) / aa (n + (k + 1)) \ 1 / (tt + real n) powr (1 + \)" unfolding ff_def tt_def by auto show "summable (\i. bb (i + (k + 1)) / aa (i + (k + 1)))" using summable[THEN summable_ignore_initial_segment,of "k+1"] . show "summable (\x. 1 / (tt + real x) powr (1 + \))" using 9(2)[OF \tt>1\] . qed also have "... \ 1/(\ *(tt-1) powr \)" using 9[OF \tt>1\] by simp also have "... < 2 / (\ *tt powr \)" proof - have "((2 powr (1/\) / (2 powr (1/\) - 1)) powr (1 + \)) < (aa (k+1) / bb (k+1))" using elim(3) by auto then have "2 powr (1/\) / (2 powr (1/\) - 1) < tt" unfolding tt_def apply (drule_tac powr_less_mono2[rotated 2,where a="1/ (1 + \)"]) using \\>0\ apply (auto simp:powr_powr ) by (subst (asm) powr_one,auto simp add:field_simps) then have " tt < (tt-1) * (2 powr (1/\))" using \\>0\ by (auto simp:divide_simps algebra_simps) then have "tt powr \ < 2 * (tt - 1) powr \" apply (drule_tac powr_less_mono2[rotated 2,where a="\"]) using \\>0\ \tt>1\ by (auto simp:powr_powr powr_mult) then show ?thesis using \\>0\ \tt>1\ by (auto simp:divide_simps) qed also have "... = 2 / \ * (bb (k + 1) / aa (k + 1)) powr (\ / (1 + \))" unfolding tt_def using \\>0\ by (auto simp:powr_powr divide_simps algebra_simps powr_divide less_imp_le) finally show ?case . qed - define pq where "pq = (\k. quotient_of (\i=0..k. of_int (b i) / of_int (a i)))" - define p q where "p = fst \ pq" and "q = snd \ pq" + define pq where "pq \ (\k. quotient_of (\i=0..k. of_int (b i) / of_int (a i)))" + define p q where "p \ fst \ pq" and "q = snd \ pq" have coprime_pq:"coprime (p k) (q k)" and q_pos:"q k > 0" and pq_sum:"p k / q k = (\i=0..k. b i / a i)" for k proof - have eq: "quotient_of (\i=0..k. of_int (b i) / of_int (a i)) = (p k, q k)" by (simp add: p_def q_def pq_def) from quotient_of_coprime[OF eq] show "coprime (p k) (q k)" . from quotient_of_denom_pos[OF eq] show "q k > 0" . have "(\i=0..k. b i / a i) = of_rat (\i=0..k. of_int (b i) / of_int (a i))" by (simp add: of_rat_sum of_rat_divide) also have "(\i=0..k. rat_of_int (b i) / rat_of_int (a i)) = rat_of_int (p k) / rat_of_int (q k)" using quotient_of_div[OF eq] by simp finally show "p k / q k = (\i=0..k. b i / a i)" by (simp add:of_rat_divide) qed have \_Inf_many:"\\<^sub>\ k. \\ - p k / q k\ < 1 / q k powr (2 + \ * \ / (1 + \))" proof - have *:"\\<^sub>\k. (bb (Suc k) / aa (Suc k)) powr (\ / (1 + \)) < \ / (2 * prod aa {0..k} powr (2 + \ * \ / (1 + \)))" using 7[of "(2 / \) powr ((1+\)/ \)"] \\>0\ by (auto simp:powr_powr) have **:"\\<^sub>\k. \\ - (\k = 0..k. bb k / aa k)\ < 2 / \ * (bb (k + 1) / aa (k + 1)) powr (\ / (1 + \))" using 10[unfolded cofinite_eq_sequentially[symmetric]] . from INFM_conjI[OF * **] show ?thesis proof (elim INFM_mono) fix k assume asm:"(bb (Suc k) / aa (Suc k)) powr (\ / (1 + \)) < \ / (2 * prod aa {0..k} powr (2 + \ * \ / (1 + \))) \ \\ - (\k = 0..k. bb k / aa k)\ < 2 / \ * (bb (k + 1) / aa (k + 1)) powr (\ / (1 + \))" have "\\ - real_of_int (p k) / real_of_int (q k)\ = \\ - (\k = 0..k. bb k / aa k)\" using pq_sum unfolding aa_def bb_def by auto also have "... < (2 / \) * (bb (k+1) / aa (k+1)) powr (\ / (1+\))" using asm by auto also have "... < (2 / \) * (\ / (2 * prod aa {0..k} powr (2 + \ * \ / (1 + \))))" apply (rule mult_strict_left_mono) using asm \\>0\ by auto also have "... = 1/ prod aa {0..k} powr (2 + \ * \ / (1 + \))" using \\>0\ by auto also have "... \ 1 / q k powr (2 + \ * \ / (1 + \))" proof - have "q k \ prod aa {0..k}" proof (induct k) case 0 then show ?case unfolding q_def pq_def aa_def apply (simp add:rat_divide_code of_int_rat quotient_of_Fract) using aa_bb_pos[of 0,unfolded aa_def bb_def] unfolding Let_def normalize_def apply auto by (metis div_by_1 less_imp_le less_trans nonneg1_imp_zdiv_pos_iff not_less zdiv_mono2) next case (Suc k) - define de where "de=snd \ quotient_of" + define de where "de \ snd \ quotient_of" have "real_of_int (q (Suc k)) = de (\i=0..Suc k. of_int (b i) / of_int (a i))" unfolding q_def pq_def de_def by simp also have "... = de ((\i=0..k. of_int (b i) / of_int (a i)) + of_int (b (Suc k)) / of_int (a (Suc k)))" by simp also have "... \ de (\i=0..k. of_int (b i) / of_int (a i)) * de (of_int (b (Suc k)) / of_int (a (Suc k)))" using snd_quotient_plus_leq[folded de_def] by presburger also have "... = q k * de (of_int (b (Suc k)) / of_int (a (Suc k)))" unfolding q_def pq_def de_def by auto also have "... = q k * snd (Rat.normalize (b (Suc k), a (Suc k)))" by (simp add:rat_divide_code of_int_rat quotient_of_Fract de_def) also have "... \ q k * aa (Suc k)" using aa_bb_pos[of "Suc k"] q_pos[of "k"] unfolding normalize_def aa_def bb_def Let_def apply auto by (metis div_by_1 int_one_le_iff_zero_less less_trans nonneg1_imp_zdiv_pos_iff not_less zdiv_mono2 zero_less_one) also have "... \ prod aa {0..k} * aa (Suc k)" using Suc aa_bb_pos[of "Suc k"] by auto also have "... = prod aa {0..Suc k}" by (simp add: prod.atLeast0_atMost_Suc) finally show ?case . qed then show ?thesis apply (rule_tac divide_left_mono) apply (rule powr_mono2) using \\>0\ \\>0\ q_pos[of k] apply (auto simp:powr_mult[symmetric]) by (metis aa_bb_pos(1) less_irrefl) qed finally show "\\ - p k / q k\ < 1 / q k powr (2 + \ * \ / (1 + \))" . qed qed - define pqs where "pqs={(p, q). q>0 \ coprime p q \ \\ - real_of_int p / real_of_int q\ + define pqs where "pqs \ {(p, q). q>0 \ coprime p q \ \\ - real_of_int p / real_of_int q\ < 1 / q powr (2 + \ * \ / (1 + \))}" have \_infinite:"infinite pqs" proof - - define A where "A={k. \\ - (p k) / (q k)\ < 1 / (q k) powr (2 + \ * \ / (1 + \))}" + define A where "A \ {k. \\ - (p k) / (q k)\ < 1 / (q k) powr (2 + \ * \ / (1 + \))}" note \_Inf_many then have "infinite A" unfolding Inf_many_def A_def by auto moreover have "inj_on (\k. (p k, q k)) A" proof - - define g where "g=(\i. rat_of_int (b i) / rat_of_int (a i))" - define f where "f=(\k. \i = 0..k. g i)" + define g where "g \ (\i. rat_of_int (b i) / rat_of_int (a i))" + define f where "f \ (\k. \i = 0..k. g i)" have g_pos:"g i>0" for i unfolding g_def by (simp add: a_pos b_pos) have "strict_mono f" unfolding strict_mono_def f_def proof safe fix x y::nat assume "x < y" then have "sum g {0..y} - sum g {0..x} = sum g {x<..y}" apply (subst Groups_Big.sum_diff[symmetric]) by (auto intro:arg_cong2[where f=sum]) also have "... > 0" apply (rule ordered_comm_monoid_add_class.sum_pos) using \x g_pos by auto finally have "sum g {0..y} - sum g {0..x} >0" . then show "sum g {0..x} < sum g {0..y}" by auto qed then have "inj f" using strict_mono_imp_inj_on by auto then have "inj (quotient_of o f)" by (simp add: inj_compose quotient_of_inj) then have "inj (\k. (p k, q k))" unfolding f_def p_def q_def pq_def comp_def apply (fold g_def) by auto then show ?thesis by (auto elim:subset_inj_on) qed moreover have "(\k. (p k, q k)) ` A \ pqs" unfolding A_def pqs_def using coprime_pq q_pos by auto ultimately show ?thesis apply (elim infinite_inj_imageE) by auto qed moreover have "finite pqs" if "\ \ \" proof - obtain m n where \_mn:"\ = (of_int m / of_int n)" and "coprime m n" "n>0" proof - obtain m n where mn:"\\\ = (of_nat m / of_nat n)" "coprime m n" "n\0" using Rats_abs_nat_div_natE[OF \\ \ \\ Rats_abs_nat_div_natE] by metis define m' and n'::int where "m'=(if \ > 0 then nat m else -nat m)" and "n'=nat n" then have "\ = (of_int m' / of_int n')" "coprime m' n'" "n'>0" using mn by auto then show ?thesis using that by auto qed have "pqs \ {(m,n)} \ {x. x \pqs \ - \m\ - 1 \fst x \ fst x \ \m\ + 1 \ 0 snd x < n }" proof (rule subsetI) fix x assume "x \ pqs" - define p q where "p=fst x" and "q=snd x" + define p q where "p \ fst x" and "q=snd x" have "q>0" "coprime p q" and pq_less:"\\ - p / q\ < 1 / q powr (2 + \ * \ / (1 + \))" using \x\pqs\ unfolding p_def q_def pqs_def by auto have q_lt_n:"qp \ n\q" proof - have "m * q \ n * p" using that \coprime m n\ \coprime p q\ \q>0\ \n>0\ by (metis eq_rat(1) fst_conv int_one_le_iff_zero_less mult.commute normalize_stable not_one_le_zero quotient_of_Fract snd_conv) then have "1/(n*q) \ \m/n - p/q\" using \q>0\ \n>0\ apply (auto simp:field_simps) by (metis add_diff_cancel_left' diff_diff_eq2 diff_zero less_irrefl not_le of_int_diff of_int_lessD of_int_mult) also have "... < 1 / q powr (2 + \ * \ / (1 + \))" using pq_less unfolding \_mn by auto also have "... \ 1 / q ^2" proof - have "real_of_int (q\<^sup>2) = q powr 2" apply (subst powr_numeral) unfolding power2_eq_square using \q>0\ by auto also have "... \ q powr (2 + \ * \ / (1 + \))" apply (rule powr_mono) using \q>0\ \\>0\ \\>0\ by auto finally have "real_of_int (q\<^sup>2) \ real_of_int q powr (2 + \ * \ / (1 + \))" . moreover have "real_of_int q powr (2 + \ * \ / (1 + \)) > 0" using \0 < q\ by auto ultimately show ?thesis by (auto simp:field_simps) qed finally have " 1 / (n * q) < 1 / q\<^sup>2" . then show ?thesis using \q>0\ \n>0\ unfolding power2_eq_square by (auto simp:field_simps) qed moreover have "- \m\ - 1 \ p \ p \ \m\ + 1" when "m\p \ n\q" proof - - define qn where "qn=q/n" + define qn where "qn \ q/n" have "0m\p \ n\q\] \q>0\ by auto have "\m/n - p / q\ < 1 / q powr (2 + \ * \ / (1 + \))" using pq_less unfolding \_mn by simp then have "\p / q - m/n\ < 1 / q powr (2 + \ * \ / (1 + \))" by simp then have " m/n- 1 / q powr (2 + \ * \ / (1 + \)) < p/q \ p/q < m/n + 1 / q powr (2 + \ * \ / (1 + \))" unfolding abs_diff_less_iff by auto then have "qn*m- q / q powr (2 + \ * \ / (1 + \)) < p \ p < qn*m + q / q powr (2 + \ * \ / (1 + \))" unfolding qn_def using \q>0\ by (auto simp:field_simps) moreover have "- \m\ - 1 \ qn*m- q / q powr (2 + \ * \ / (1 + \))" proof - have "- \m\ \ qn*m" using \0 \qn<1\ - apply (cases "m\0") - subgoal - apply simp - by (meson less_eq_real_def mult_nonneg_nonneg neg_le_0_iff_le of_int_0_le_iff - order_trans) - subgoal by simp - done + apply (simp add: abs_if) + by (smt (verit, best) mult_nonneg_nonneg of_int_nonneg) moreover have "- 1 \ - q / q powr (2 + \ * \ / (1 + \))" proof - have "q = q powr 1" using \0 < q\ by auto also have "... \q powr (2 + \ * \ / (1 + \))" apply (rule powr_mono) using \q>0\ \\>0\ \\>0\ by auto finally have "q \ q powr (2 + \ * \ / (1 + \))" . then show ?thesis using \0 < q\ by auto qed ultimately show ?thesis by auto qed moreover have "qn*m + q / q powr (2 + \ * \ / (1 + \)) \ \m\ + 1" proof - have "qn*m \ \m\" using \0 \qn<1\ - apply (cases "m\0") - subgoal by (simp add: mult_left_le_one_le) - subgoal by (smt of_int_0_le_iff zero_le_mult_iff) - done + apply (simp add: abs_if mult_left_le_one_le) + by (meson less_eq_real_def mult_pos_neg neg_0_less_iff_less of_int_less_0_iff order_trans) moreover have "q / q powr (2 + \ * \ / (1 + \)) \ 1" proof - have "q = q powr 1" using \0 < q\ by auto also have "... \q powr (2 + \ * \ / (1 + \))" apply (rule powr_mono) using \q>0\ \\>0\ \\>0\ by auto finally have "q \ q powr (2 + \ * \ / (1 + \))" . then show ?thesis using \0 < q\ by auto qed ultimately show ?thesis by auto qed ultimately show ?thesis by auto qed ultimately show "x \ {(m, n)} \ {x \ pqs. - \m\ - 1 \ fst x \ fst x \ \m\ + 1 \ 0 < snd x \ snd x < n}" using \x \ pqs\ \q>0\ unfolding p_def q_def by force qed moreover have "finite {x. x \pqs \ - \m\ - 1 \fst x \ fst x \ \m\ + 1 \ 0 snd x < n }" proof - have "finite ({- \m\ - 1..\m\ +1} \ {0<..pqs \ - \m\ - 1 \fst x \ fst x \ \m\ + 1 \ 0 snd x < n } \ ({- \m\ - 1..\m\ +1} \ {0<.._def) using RothsTheorem[rule_format,of \ "2 + \ * \ / (1 + \)",folded pqs_def] \\ >0\ \\>0\ apply (auto simp:divide_simps ) by (meson mult_le_0_iff not_less) qed subsection\ Acknowledgements\ text\A.K.-A. and W.L. were supported by the ERC Advanced Grant ALEXANDRIA (Project 742178) funded by the European Research Council and led by Professor Lawrence Paulson at the University of Cambridge, UK. Thanks to Iosif Pinelis for his clarification on MathOverflow regarding the summmability of the series in @{thm [source] RothsTheorem.HanclRucki2} @{url "https://mathoverflow.net/questions/323069/why-is-this-series-summable"} and to Manuel Eberl for his helpful comments.\ end \ No newline at end of file