664 unfolding sum_distrib_left by (simp add:algebra_simps) |
664 unfolding sum_distrib_left by (simp add:algebra_simps) |
665 finally have "contour_integral g ff = c * (\<Sum>p\<in>pz. w p * h p * of_int (zorder f p))" . |
665 finally have "contour_integral g ff = c * (\<Sum>p\<in>pz. w p * h p * of_int (zorder f p))" . |
666 then show ?thesis unfolding ff_def c_def w_def by simp |
666 then show ?thesis unfolding ff_def c_def w_def by simp |
667 qed |
667 qed |
668 |
668 |
|
669 |
|
670 subsection \<open>Coefficient asymptotics for generating functions\<close> |
|
671 |
|
672 text \<open> |
|
673 For a formal power series that has a meromorphic continuation on some disc in the |
|
674 context plane, we can use the Residue Theorem to extract precise asymptotic information |
|
675 from the residues at the poles. This can be used to derive the asymptotic behaviour |
|
676 of the coefficients (\<open>a\<^sub>n \<sim> \<dots>\<close>). If the function is meromorphic on the entire |
|
677 complex plane, one can even derive a full asymptotic expansion. |
|
678 |
|
679 We will first show the relationship between the coefficients and the sum over the residues |
|
680 with an explicit remainder term (the contour integral along the circle used in the |
|
681 Residue theorem). |
|
682 \<close> |
|
683 theorem |
|
684 fixes f :: "complex \<Rightarrow> complex" and n :: nat and r :: real |
|
685 defines "g \<equiv> (\<lambda>w. f w / w ^ Suc n)" and "\<gamma> \<equiv> circlepath 0 r" |
|
686 assumes "open A" "connected A" "cball 0 r \<subseteq> A" "r > 0" |
|
687 assumes "f holomorphic_on A - S" "S \<subseteq> ball 0 r" "finite S" "0 \<notin> S" |
|
688 shows fps_coeff_conv_residues: |
|
689 "(deriv ^^ n) f 0 / fact n = |
|
690 contour_integral \<gamma> g / (2 * pi * \<i>) - (\<Sum>z\<in>S. residue g z)" (is ?thesis1) |
|
691 and fps_coeff_residues_bound: |
|
692 "(\<And>z. norm z = r \<Longrightarrow> z \<notin> k \<Longrightarrow> norm (f z) \<le> C) \<Longrightarrow> C \<ge> 0 \<Longrightarrow> finite k \<Longrightarrow> |
|
693 norm ((deriv ^^ n) f 0 / fact n + (\<Sum>z\<in>S. residue g z)) \<le> C / r ^ n" |
|
694 proof - |
|
695 have holo: "g holomorphic_on A - insert 0 S" |
|
696 unfolding g_def using assms by (auto intro!: holomorphic_intros) |
|
697 have "contour_integral \<gamma> g = 2 * pi * \<i> * (\<Sum>z\<in>insert 0 S. winding_number \<gamma> z * residue g z)" |
|
698 proof (rule Residue_theorem) |
|
699 show "g holomorphic_on A - insert 0 S" by fact |
|
700 from assms show "\<forall>z. z \<notin> A \<longrightarrow> winding_number \<gamma> z = 0" |
|
701 unfolding \<gamma>_def by (intro allI impI winding_number_zero_outside[of _ "cball 0 r"]) auto |
|
702 qed (insert assms, auto simp: \<gamma>_def) |
|
703 also have "winding_number \<gamma> z = 1" if "z \<in> insert 0 S" for z |
|
704 unfolding \<gamma>_def using assms that by (intro winding_number_circlepath) auto |
|
705 hence "(\<Sum>z\<in>insert 0 S. winding_number \<gamma> z * residue g z) = (\<Sum>z\<in>insert 0 S. residue g z)" |
|
706 by (intro sum.cong) simp_all |
|
707 also have "\<dots> = residue g 0 + (\<Sum>z\<in>S. residue g z)" |
|
708 using \<open>0 \<notin> S\<close> and \<open>finite S\<close> by (subst sum.insert) auto |
|
709 also from \<open>r > 0\<close> have "0 \<in> cball 0 r" by simp |
|
710 with assms have "0 \<in> A - S" by blast |
|
711 with assms have "residue g 0 = (deriv ^^ n) f 0 / fact n" |
|
712 unfolding g_def by (subst residue_holomorphic_over_power'[of "A - S"]) |
|
713 (auto simp: finite_imp_closed) |
|
714 finally show ?thesis1 |
|
715 by (simp add: field_simps) |
|
716 |
|
717 assume C: "\<And>z. norm z = r \<Longrightarrow> z \<notin> k \<Longrightarrow> norm (f z) \<le> C" "C \<ge> 0" and k: "finite k" |
|
718 have "(deriv ^^ n) f 0 / fact n + (\<Sum>z\<in>S. residue g z) = contour_integral \<gamma> g / (2 * pi * \<i>)" |
|
719 using \<open>?thesis1\<close> by (simp add: algebra_simps) |
|
720 also have "norm \<dots> = norm (contour_integral \<gamma> g) / (2 * pi)" |
|
721 by (simp add: norm_divide norm_mult) |
|
722 also have "norm (contour_integral \<gamma> g) \<le> C / r ^ Suc n * (2 * pi * r)" |
|
723 proof (rule has_contour_integral_bound_circlepath_strong) |
|
724 from \<open>open A\<close> and \<open>finite S\<close> have "open (A - insert 0 S)" |
|
725 by (blast intro: finite_imp_closed) |
|
726 with assms show "(g has_contour_integral contour_integral \<gamma> g) (circlepath 0 r)" |
|
727 unfolding \<gamma>_def |
|
728 by (intro has_contour_integral_integral contour_integrable_holomorphic_simple [OF holo]) auto |
|
729 next |
|
730 fix z assume z: "norm (z - 0) = r" "z \<notin> k" |
|
731 hence "norm (g z) = norm (f z) / r ^ Suc n" |
|
732 by (simp add: norm_divide g_def norm_mult norm_power) |
|
733 also have "\<dots> \<le> C / r ^ Suc n" |
|
734 using k and \<open>r > 0\<close> and z by (intro divide_right_mono C zero_le_power) auto |
|
735 finally show "norm (g z) \<le> C / r ^ Suc n" . |
|
736 qed (insert C(2) k \<open>r > 0\<close>, auto) |
|
737 also from \<open>r > 0\<close> have "C / r ^ Suc n * (2 * pi * r) / (2 * pi) = C / r ^ n" |
|
738 by simp |
|
739 finally show "norm ((deriv ^^ n) f 0 / fact n + (\<Sum>z\<in>S. residue g z)) \<le> \<dots>" |
|
740 by - (simp_all add: divide_right_mono) |
|
741 qed |
|
742 |
|
743 text \<open> |
|
744 Since the circle is fixed, we can get an upper bound on the values of the generating |
|
745 function on the circle and therefore show that the integral is $O(r^{-n})$. |
|
746 \<close> |
|
747 corollary fps_coeff_residues_bigo: |
|
748 fixes f :: "complex \<Rightarrow> complex" and r :: real |
|
749 assumes "open A" "connected A" "cball 0 r \<subseteq> A" "r > 0" |
|
750 assumes "f holomorphic_on A - S" "S \<subseteq> ball 0 r" "finite S" "0 \<notin> S" |
|
751 assumes g: "eventually (\<lambda>n. g n = -(\<Sum>z\<in>S. residue (\<lambda>z. f z / z ^ Suc n) z)) sequentially" |
|
752 (is "eventually (\<lambda>n. _ = -?g' n) _") |
|
753 shows "(\<lambda>n. (deriv ^^ n) f 0 / fact n - g n) \<in> O(\<lambda>n. 1 / r ^ n)" (is "(\<lambda>n. ?c n - _) \<in> O(_)") |
|
754 proof - |
|
755 from assms have "compact (f ` sphere 0 r)" |
|
756 by (intro compact_continuous_image holomorphic_on_imp_continuous_on |
|
757 holomorphic_on_subset[OF \<open>f holomorphic_on A - S\<close>]) auto |
|
758 hence "bounded (f ` sphere 0 r)" by (rule compact_imp_bounded) |
|
759 then obtain C where C: "\<And>z. z \<in> sphere 0 r \<Longrightarrow> norm (f z) \<le> C" |
|
760 by (auto simp: bounded_iff sphere_def) |
|
761 have "0 \<le> norm (f (of_real r))" by simp |
|
762 also from C[of "of_real r"] and \<open>r > 0\<close> have "\<dots> \<le> C" by simp |
|
763 finally have C_nonneg: "C \<ge> 0" . |
|
764 |
|
765 have "(\<lambda>n. ?c n + ?g' n) \<in> O(\<lambda>n. of_real (1 / r ^ n))" |
|
766 proof (intro bigoI[of _ C] always_eventually allI ) |
|
767 fix n :: nat |
|
768 from assms and C and C_nonneg have "norm (?c n + ?g' n) \<le> C / r ^ n" |
|
769 by (intro fps_coeff_residues_bound[where A = A and k = "{}"]) auto |
|
770 also have "\<dots> = C * norm (complex_of_real (1 / r ^ n))" |
|
771 using \<open>r > 0\<close> by (simp add: norm_divide norm_power) |
|
772 finally show "norm (?c n + ?g' n) \<le> \<dots>" . |
|
773 qed |
|
774 also have "?this \<longleftrightarrow> (\<lambda>n. ?c n - g n) \<in> O(\<lambda>n. of_real (1 / r ^ n))" |
|
775 by (intro landau_o.big.in_cong eventually_mono[OF g]) simp_all |
|
776 finally show ?thesis . |
|
777 qed |
|
778 |
|
779 corollary fps_coeff_residues_bigo': |
|
780 fixes f :: "complex \<Rightarrow> complex" and r :: real |
|
781 assumes exp: "f has_fps_expansion F" |
|
782 assumes "open A" "connected A" "cball 0 r \<subseteq> A" "r > 0" |
|
783 assumes "f holomorphic_on A - S" "S \<subseteq> ball 0 r" "finite S" "0 \<notin> S" |
|
784 assumes "eventually (\<lambda>n. g n = -(\<Sum>z\<in>S. residue (\<lambda>z. f z / z ^ Suc n) z)) sequentially" |
|
785 (is "eventually (\<lambda>n. _ = -?g' n) _") |
|
786 shows "(\<lambda>n. fps_nth F n - g n) \<in> O(\<lambda>n. 1 / r ^ n)" (is "(\<lambda>n. ?c n - _) \<in> O(_)") |
|
787 proof - |
|
788 have "fps_nth F = (\<lambda>n. (deriv ^^ n) f 0 / fact n)" |
|
789 using fps_nth_fps_expansion[OF exp] by (intro ext) simp_all |
|
790 with fps_coeff_residues_bigo[OF assms(2-)] show ?thesis by simp |
|
791 qed |
|
792 |
669 subsection \<open>Rouche's theorem \<close> |
793 subsection \<open>Rouche's theorem \<close> |
670 |
794 |
671 theorem Rouche_theorem: |
795 theorem Rouche_theorem: |
672 fixes f g::"complex \<Rightarrow> complex" and s:: "complex set" |
796 fixes f g::"complex \<Rightarrow> complex" and s:: "complex set" |
673 defines "fg\<equiv>(\<lambda>p. f p + g p)" |
797 defines "fg\<equiv>(\<lambda>p. f p + g p)" |