src/HOL/Multivariate_Analysis/Summation.thy
changeset 63040 eb4ddd18d635
parent 62381 a6479cb85944
equal deleted inserted replaced
63039:1a20fd9cf281 63040:eb4ddd18d635
   140   have "0 = limsup (\<lambda>n. 0)" by (simp add: Limsup_const)
   140   have "0 = limsup (\<lambda>n. 0)" by (simp add: Limsup_const)
   141   also have "... \<le> l" unfolding l_def by (intro Limsup_mono) (simp_all add: real_root_ge_zero)
   141   also have "... \<le> l" unfolding l_def by (intro Limsup_mono) (simp_all add: real_root_ge_zero)
   142   finally have "l \<ge> 0" by simp
   142   finally have "l \<ge> 0" by simp
   143   with l obtain l' where l': "l = ereal l'" by (cases l) simp_all
   143   with l obtain l' where l': "l = ereal l'" by (cases l) simp_all
   144 
   144 
   145   def c \<equiv> "(1 - l') / 2"
   145   define c where "c = (1 - l') / 2"
   146   from l and \<open>l \<ge> 0\<close> have c: "l + c > l" "l' + c \<ge> 0" "l' + c < 1" unfolding c_def 
   146   from l and \<open>l \<ge> 0\<close> have c: "l + c > l" "l' + c \<ge> 0" "l' + c < 1" unfolding c_def 
   147     by (simp_all add: field_simps l')
   147     by (simp_all add: field_simps l')
   148   have "\<forall>C>l. eventually (\<lambda>n. ereal (root n (norm (f n))) < C) sequentially"
   148   have "\<forall>C>l. eventually (\<lambda>n. ereal (root n (norm (f n))) < C) sequentially"
   149     by (subst Limsup_le_iff[symmetric]) (simp add: l_def)
   149     by (subst Limsup_le_iff[symmetric]) (simp add: l_def)
   150   with c have "eventually (\<lambda>n. ereal (root n (norm (f n))) < l + ereal c) sequentially" by simp
   150   with c have "eventually (\<lambda>n. ereal (root n (norm (f n))) < l + ereal c) sequentially" by simp
   174 
   174 
   175   have "0 = limsup (\<lambda>n. 0)" by (simp add: Limsup_const)
   175   have "0 = limsup (\<lambda>n. 0)" by (simp add: Limsup_const)
   176   also have "... \<le> l" unfolding l_def by (intro Limsup_mono) (simp_all add: real_root_ge_zero)
   176   also have "... \<le> l" unfolding l_def by (intro Limsup_mono) (simp_all add: real_root_ge_zero)
   177   finally have l_nonneg: "l \<ge> 0" by simp
   177   finally have l_nonneg: "l \<ge> 0" by simp
   178 
   178 
   179   def c \<equiv> "if l = \<infinity> then 2 else 1 + (real_of_ereal l - 1) / 2"
   179   define c where "c = (if l = \<infinity> then 2 else 1 + (real_of_ereal l - 1) / 2)"
   180   from l l_nonneg consider "l = \<infinity>" | "\<exists>l'. l = ereal l'" by (cases l) simp_all
   180   from l l_nonneg consider "l = \<infinity>" | "\<exists>l'. l = ereal l'" by (cases l) simp_all
   181   hence c: "c > 1 \<and> ereal c < l" by cases (insert l, auto simp: c_def field_simps)
   181   hence c: "c > 1 \<and> ereal c < l" by cases (insert l, auto simp: c_def field_simps)
   182 
   182 
   183   have unbounded: "\<not>bdd_above {n. root n (norm (f n)) > c}"
   183   have unbounded: "\<not>bdd_above {n. root n (norm (f n)) > c}"
   184   proof
   184   proof
   191     hence "l \<le> c" unfolding l_def by (intro Limsup_bounded) simp_all
   191     hence "l \<le> c" unfolding l_def by (intro Limsup_bounded) simp_all
   192     with c show False by auto
   192     with c show False by auto
   193   qed
   193   qed
   194   
   194   
   195   from bounded obtain K where K: "K > 0" "\<And>n. norm (f n) \<le> K" using BseqE by blast
   195   from bounded obtain K where K: "K > 0" "\<And>n. norm (f n) \<le> K" using BseqE by blast
   196   def n \<equiv> "nat \<lceil>log c K\<rceil>"
   196   define n where "n = nat \<lceil>log c K\<rceil>"
   197   from unbounded have "\<exists>m>n. c < root m (norm (f m))" unfolding bdd_above_def
   197   from unbounded have "\<exists>m>n. c < root m (norm (f m))" unfolding bdd_above_def
   198     by (auto simp: not_le)
   198     by (auto simp: not_le)
   199   then guess m by (elim exE conjE) note m = this
   199   then guess m by (elim exE conjE) note m = this
   200   from c K have "K = c powr log c K" by (simp add: powr_def log_def)
   200   from c K have "K = c powr log c K" by (simp add: powr_def log_def)
   201   also from c have "c powr log c K \<le> c powr real n" unfolding n_def
   201   also from c have "c powr log c K \<le> c powr real n" unfolding n_def
   251 lemma condensation_test:
   251 lemma condensation_test:
   252   assumes mono: "\<And>m. 0 < m \<Longrightarrow> f (Suc m) \<le> f m"
   252   assumes mono: "\<And>m. 0 < m \<Longrightarrow> f (Suc m) \<le> f m"
   253   assumes nonneg: "\<And>n. f n \<ge> 0"
   253   assumes nonneg: "\<And>n. f n \<ge> 0"
   254   shows "summable f \<longleftrightarrow> summable (\<lambda>n. 2^n * f (2^n))"
   254   shows "summable f \<longleftrightarrow> summable (\<lambda>n. 2^n * f (2^n))"
   255 proof -
   255 proof -
   256   def f' \<equiv> "\<lambda>n. if n = 0 then 0 else f n"
   256   define f' where "f' n = (if n = 0 then 0 else f n)" for n
   257   from mono have mono': "decseq (\<lambda>n. f (Suc n))" by (intro decseq_SucI) simp
   257   from mono have mono': "decseq (\<lambda>n. f (Suc n))" by (intro decseq_SucI) simp
   258   hence mono': "f n \<le> f m" if "m \<le> n" "m > 0" for m n 
   258   hence mono': "f n \<le> f m" if "m \<le> n" "m > 0" for m n 
   259     using that decseqD[OF mono', of "m - 1" "n - 1"] by simp
   259     using that decseqD[OF mono', of "m - 1" "n - 1"] by simp
   260   
   260   
   261   have "(\<lambda>n. f (Suc n)) = (\<lambda>n. f' (Suc n))" by (intro ext) (simp add: f'_def)
   261   have "(\<lambda>n. f (Suc n)) = (\<lambda>n. f' (Suc n))" by (intro ext) (simp add: f'_def)
   400   defines "l \<equiv> liminf (\<lambda>n. ereal (p n * f n / f (Suc n) - p (Suc n)))"
   400   defines "l \<equiv> liminf (\<lambda>n. ereal (p n * f n / f (Suc n) - p (Suc n)))"
   401   assumes l: "l > 0"
   401   assumes l: "l > 0"
   402   shows   "summable f"
   402   shows   "summable f"
   403   unfolding summable_iff_convergent'
   403   unfolding summable_iff_convergent'
   404 proof -
   404 proof -
   405   def r \<equiv> "(if l = \<infinity> then 1 else real_of_ereal l / 2)"
   405   define r where "r = (if l = \<infinity> then 1 else real_of_ereal l / 2)"
   406   from l have "r > 0 \<and> of_real r < l" by (cases l) (simp_all add: r_def)
   406   from l have "r > 0 \<and> of_real r < l" by (cases l) (simp_all add: r_def)
   407   hence r: "r > 0" "of_real r < l" by simp_all
   407   hence r: "r > 0" "of_real r < l" by simp_all
   408   hence "eventually (\<lambda>n. p n * f n / f (Suc n) - p (Suc n) > r) sequentially"
   408   hence "eventually (\<lambda>n. p n * f n / f (Suc n) - p (Suc n) > r) sequentially"
   409     unfolding l_def by (force dest: less_LiminfD)
   409     unfolding l_def by (force dest: less_LiminfD)
   410   moreover from pos_f have "eventually (\<lambda>n. f (Suc n) > 0) sequentially" 
   410   moreover from pos_f have "eventually (\<lambda>n. f (Suc n) > 0) sequentially" 
   418 
   418 
   419   let ?c = "(norm (\<Sum>k\<le>m. r * f k) + p m * f m) / r"
   419   let ?c = "(norm (\<Sum>k\<le>m. r * f k) + p m * f m) / r"
   420   have "Bseq (\<lambda>n. (\<Sum>k\<le>n + Suc m. f k))"
   420   have "Bseq (\<lambda>n. (\<Sum>k\<le>n + Suc m. f k))"
   421   proof (rule BseqI')
   421   proof (rule BseqI')
   422     fix k :: nat
   422     fix k :: nat
   423     def n \<equiv> "k + Suc m"
   423     define n where "n = k + Suc m"
   424     have n: "n > m" by (simp add: n_def)
   424     have n: "n > m" by (simp add: n_def)
   425 
   425 
   426     from r have "r * norm (\<Sum>k\<le>n. f k) = norm (\<Sum>k\<le>n. r * f k)"
   426     from r have "r * norm (\<Sum>k\<le>n. f k) = norm (\<Sum>k\<le>n. r * f k)"
   427       by (simp add: setsum_right_distrib[symmetric] abs_mult)
   427       by (simp add: setsum_right_distrib[symmetric] abs_mult)
   428     also from n have "{..n} = {..m} \<union> {Suc m..n}" by auto
   428     also from n have "{..n} = {..m} \<union> {Suc m..n}" by auto
   586 lemma abs_summable_in_conv_radius:
   586 lemma abs_summable_in_conv_radius:
   587   fixes f :: "nat \<Rightarrow> 'a :: {banach, real_normed_div_algebra}"
   587   fixes f :: "nat \<Rightarrow> 'a :: {banach, real_normed_div_algebra}"
   588   assumes "ereal (norm z) < conv_radius f"
   588   assumes "ereal (norm z) < conv_radius f"
   589   shows   "summable (\<lambda>n. norm (f n * z ^ n))"
   589   shows   "summable (\<lambda>n. norm (f n * z ^ n))"
   590 proof (rule root_test_convergence')
   590 proof (rule root_test_convergence')
   591   def l \<equiv> "limsup (\<lambda>n. ereal (root n (norm (f n))))"
   591   define l where "l = limsup (\<lambda>n. ereal (root n (norm (f n))))"
   592   have "0 = limsup (\<lambda>n. 0)" by (simp add: Limsup_const)
   592   have "0 = limsup (\<lambda>n. 0)" by (simp add: Limsup_const)
   593   also have "... \<le> l" unfolding l_def by (intro Limsup_mono) (simp_all add: real_root_ge_zero)
   593   also have "... \<le> l" unfolding l_def by (intro Limsup_mono) (simp_all add: real_root_ge_zero)
   594   finally have l_nonneg: "l \<ge> 0" .
   594   finally have l_nonneg: "l \<ge> 0" .
   595 
   595 
   596   have "limsup (\<lambda>n. root n (norm (f n * z^n))) = l * ereal (norm z)" unfolding l_def
   596   have "limsup (\<lambda>n. root n (norm (f n * z^n))) = l * ereal (norm z)" unfolding l_def
   624 lemma not_summable_outside_conv_radius:
   624 lemma not_summable_outside_conv_radius:
   625   fixes f :: "nat \<Rightarrow> 'a :: {banach, real_normed_div_algebra}"
   625   fixes f :: "nat \<Rightarrow> 'a :: {banach, real_normed_div_algebra}"
   626   assumes "ereal (norm z) > conv_radius f"
   626   assumes "ereal (norm z) > conv_radius f"
   627   shows   "\<not>summable (\<lambda>n. f n * z ^ n)"
   627   shows   "\<not>summable (\<lambda>n. f n * z ^ n)"
   628 proof (rule root_test_divergence)
   628 proof (rule root_test_divergence)
   629   def l \<equiv> "limsup (\<lambda>n. ereal (root n (norm (f n))))"
   629   define l where "l = limsup (\<lambda>n. ereal (root n (norm (f n))))"
   630   have "0 = limsup (\<lambda>n. 0)" by (simp add: Limsup_const)
   630   have "0 = limsup (\<lambda>n. 0)" by (simp add: Limsup_const)
   631   also have "... \<le> l" unfolding l_def by (intro Limsup_mono) (simp_all add: real_root_ge_zero)
   631   also have "... \<le> l" unfolding l_def by (intro Limsup_mono) (simp_all add: real_root_ge_zero)
   632   finally have l_nonneg: "l \<ge> 0" .
   632   finally have l_nonneg: "l \<ge> 0" .
   633   from assms have l_nz: "l \<noteq> 0" unfolding conv_radius_def l_def by auto
   633   from assms have l_nz: "l \<noteq> 0" unfolding conv_radius_def l_def by auto
   634 
   634 
   674 proof (rule linorder_cases[of "conv_radius f" R])
   674 proof (rule linorder_cases[of "conv_radius f" R])
   675   assume R: "conv_radius f < R"
   675   assume R: "conv_radius f < R"
   676   with conv_radius_nonneg[of f] obtain conv_radius' 
   676   with conv_radius_nonneg[of f] obtain conv_radius' 
   677     where [simp]: "conv_radius f = ereal conv_radius'"
   677     where [simp]: "conv_radius f = ereal conv_radius'"
   678     by (cases "conv_radius f") simp_all
   678     by (cases "conv_radius f") simp_all
   679   def r \<equiv> "if R = \<infinity> then conv_radius' + 1 else (real_of_ereal R + conv_radius') / 2"
   679   define r where "r = (if R = \<infinity> then conv_radius' + 1 else (real_of_ereal R + conv_radius') / 2)"
   680   from R conv_radius_nonneg[of f] have "0 < r \<and> ereal r < R \<and> ereal r > conv_radius f" 
   680   from R conv_radius_nonneg[of f] have "0 < r \<and> ereal r < R \<and> ereal r > conv_radius f" 
   681     unfolding r_def by (cases R) (auto simp: r_def field_simps)
   681     unfolding r_def by (cases R) (auto simp: r_def field_simps)
   682   with assms(1)[of r] obtain z where "norm z > conv_radius f" "summable (\<lambda>n. f n * z^n)" by auto
   682   with assms(1)[of r] obtain z where "norm z > conv_radius f" "summable (\<lambda>n. f n * z^n)" by auto
   683   with not_summable_outside_conv_radius[of f z] show ?thesis by simp
   683   with not_summable_outside_conv_radius[of f z] show ?thesis by simp
   684 qed simp_all
   684 qed simp_all
   699   assumes "\<And>r. 0 < r \<Longrightarrow> ereal r > R \<Longrightarrow> \<exists>z. norm z = r \<and> \<not>summable (\<lambda>n. norm (f n * z^n))"
   699   assumes "\<And>r. 0 < r \<Longrightarrow> ereal r > R \<Longrightarrow> \<exists>z. norm z = r \<and> \<not>summable (\<lambda>n. norm (f n * z^n))"
   700   shows   "conv_radius f \<le> R"
   700   shows   "conv_radius f \<le> R"
   701 proof (rule linorder_cases[of "conv_radius f" R])
   701 proof (rule linorder_cases[of "conv_radius f" R])
   702   assume R: "conv_radius f > R"
   702   assume R: "conv_radius f > R"
   703   from R assms(1) obtain R' where R': "R = ereal R'" by (cases R) simp_all
   703   from R assms(1) obtain R' where R': "R = ereal R'" by (cases R) simp_all
   704   def r \<equiv> "if conv_radius f = \<infinity> then R' + 1 else (R' + real_of_ereal (conv_radius f)) / 2"
   704   define r where
       
   705     "r = (if conv_radius f = \<infinity> then R' + 1 else (R' + real_of_ereal (conv_radius f)) / 2)"
   705   from R conv_radius_nonneg[of f] have "r > R \<and> r < conv_radius f" unfolding r_def
   706   from R conv_radius_nonneg[of f] have "r > R \<and> r < conv_radius f" unfolding r_def
   706     by (cases "conv_radius f") (auto simp: r_def field_simps R')
   707     by (cases "conv_radius f") (auto simp: r_def field_simps R')
   707   with assms(1) assms(2)[of r] R' 
   708   with assms(1) assms(2)[of r] R' 
   708     obtain z where "norm z < conv_radius f" "\<not>summable (\<lambda>n. norm (f n * z^n))" by auto
   709     obtain z where "norm z < conv_radius f" "\<not>summable (\<lambda>n. norm (f n * z^n))" by auto
   709   with abs_summable_in_conv_radius[of z f] show ?thesis by auto
   710   with abs_summable_in_conv_radius[of z f] show ?thesis by auto
   747   assumes "\<And>z. z \<noteq> 0 \<Longrightarrow> \<not>summable (\<lambda>n. f n * z^n)"
   748   assumes "\<And>z. z \<noteq> 0 \<Longrightarrow> \<not>summable (\<lambda>n. f n * z^n)"
   748   shows   "conv_radius f = 0"
   749   shows   "conv_radius f = 0"
   749 proof (rule ccontr)
   750 proof (rule ccontr)
   750   assume "conv_radius f \<noteq> 0"
   751   assume "conv_radius f \<noteq> 0"
   751   with conv_radius_nonneg[of f] have pos: "conv_radius f > 0" by simp
   752   with conv_radius_nonneg[of f] have pos: "conv_radius f > 0" by simp
   752   def r \<equiv> "if conv_radius f = \<infinity> then 1 else real_of_ereal (conv_radius f) / 2"
   753   define r where "r = (if conv_radius f = \<infinity> then 1 else real_of_ereal (conv_radius f) / 2)"
   753   from pos have r: "ereal r > 0 \<and> ereal r < conv_radius f" 
   754   from pos have r: "ereal r > 0 \<and> ereal r < conv_radius f" 
   754     by (cases "conv_radius f") (simp_all add: r_def)
   755     by (cases "conv_radius f") (simp_all add: r_def)
   755   hence "summable (\<lambda>n. f n * of_real r ^ n)" by (intro summable_in_conv_radius) simp
   756   hence "summable (\<lambda>n. f n * of_real r ^ n)" by (intro summable_in_conv_radius) simp
   756   moreover from r and assms[of "of_real r"] have "\<not>summable (\<lambda>n. f n * of_real r ^ n)" by simp
   757   moreover from r and assms[of "of_real r"] have "\<not>summable (\<lambda>n. f n * of_real r ^ n)" by simp
   757   ultimately show False by contradiction
   758   ultimately show False by contradiction