src/HOL/Probability/SeriesPlus.thy

Branches.overlapping: proper treatment of stop_range that overlaps with end;
Markup_Tree.select: allow singularity in parent range specification;

theory SeriesPlus
  imports Complex_Main Nat_Bijection
begin

text{*From the Hurd/Coble measure theory development, translated by Lawrence Paulson.*}

lemma choice2: "(!!x. \<exists>y z. Q x y z) ==> \<exists>f g. \<forall>x. Q x (f x) (g x)"
  by metis

lemma range_subsetD: "range f \<subseteq> B \<Longrightarrow> f i \<in> B"
  by blast


lemma suminf_2dimen:
  fixes f:: "nat * nat \<Rightarrow> real"
  assumes f_nneg: "!!m n. 0 \<le> f(m,n)"
      and fsums: "!!m. (\<lambda>n. f (m,n)) sums (g m)"
      and sumg: "summable g"
  shows "(f o prod_decode) sums suminf g"
proof (simp add: sums_def)
  {
    fix x
    have "0 \<le> f x"
      by (cases x) (simp add: f_nneg) 
  } note [iff]  = this
  have g_nneg: "!!m. 0 \<le> g m"
    proof -
      fix m
      have "0 \<le> suminf (\<lambda>n. f (m,n))"
        by (rule suminf_0_le, simp add: f_nneg, metis fsums sums_iff)
      thus "0 \<le> g m" using fsums [of m] 
        by (auto simp add: sums_iff) 
    qed
  show "(\<lambda>n. \<Sum>x = 0..<n. f (prod_decode x)) ----> suminf g"
  proof (rule increasing_LIMSEQ, simp add: f_nneg)
    fix n
    def i \<equiv> "Max (Domain (prod_decode ` {0..<n}))"
    def j \<equiv> "Max (Range (prod_decode ` {0..<n}))"
    have ij: "prod_decode ` {0..<n} \<subseteq> ({0..i} \<times> {0..j})" 
      by (force simp add: i_def j_def 
                intro: finite_imageI Max_ge finite_Domain finite_Range)  
    have "(\<Sum>x = 0..<n. f (prod_decode x)) = setsum f (prod_decode ` {0..<n})" 
      using setsum_reindex [of prod_decode "{0..<n}" f] 
      by (simp add: o_def)
         (metis inj_prod_decode inj_prod_decode)
    also have "... \<le> setsum f ({0..i} \<times> {0..j})"
      by (rule setsum_mono2) (auto simp add: ij) 
    also have "... = setsum (\<lambda>m. setsum (\<lambda>n. f (m,n)) {0..j}) {0..<Suc i}"
      by (metis atLeast0AtMost atLeast0LessThan lessThan_Suc_atMost
                setsum_cartesian_product split_eta) 
    also have "... \<le> setsum g {0..<Suc i}" 
      proof (rule setsum_mono, simp add: less_Suc_eq_le) 
        fix m
        assume m: "m \<le> i"
        thus " (\<Sum>n = 0..j. f (m, n)) \<le> g m" using fsums [of m]
          by (auto simp add: sums_iff) 
           (metis atLeastLessThanSuc_atLeastAtMost f_nneg series_pos_le f_nneg) 
      qed
    finally have  "(\<Sum>x = 0..<n. f (prod_decode x)) \<le> setsum g {0..<Suc i}" .
    also have "... \<le> suminf g" 
      by (rule series_pos_le [OF sumg]) (simp add: g_nneg) 
    finally show "(\<Sum>x = 0..<n. f (prod_decode x)) \<le> suminf g" .
  next
    fix e :: real
    assume e: "0 < e"
    with summable_sums [OF sumg]
    obtain N where "\<bar>setsum g {0..<N} - suminf g\<bar> < e/2" and nz: "N>0"
      by (simp add: sums_def LIMSEQ_iff_nz dist_real_def)
         (metis e half_gt_zero le_refl that)
    hence gless: "suminf g < setsum g {0..<N} + e/2" using series_pos_le [OF sumg]
      by (simp add: g_nneg)
    { fix m
      assume m: "m<N"
      hence enneg: "0 < e / (2 * real N)" using e
        by (simp add: zero_less_divide_iff) 
      hence  "\<exists>j. \<bar>(\<Sum>n = 0..<j. f (m, n)) - g m\<bar> < e/(2 * real N)"
        using fsums [of m] m
        by (force simp add: sums_def LIMSEQ_def dist_real_def)
      hence "\<exists>j. g m < setsum (\<lambda>n. f (m,n)) {0..<j} + e/(2 * real N)" 
        using fsums [of m]
        by (auto simp add: sums_iff) 
           (metis abs_diff_less_iff add_less_cancel_right eq_diff_eq') 
    }
    hence "\<exists>jj. \<forall>m. m<N \<longrightarrow> g m < (\<Sum>n = 0..<jj m. f (m, n)) + e/(2 * real N)"
      by (force intro: choice) 
    then obtain jj where jj:
          "!!m. m<N \<Longrightarrow> g m < (\<Sum>n = 0..<jj m. f (m, n)) + e/(2 * real N)"
      by auto
    def IJ \<equiv> "SIGMA i : {0..<N}. {0..<jj i}"
    have "setsum g {0..<N} <
             (\<Sum>m = 0..<N. (\<Sum>n = 0..<jj m. f (m, n)) + e/(2 * real N))"
      by (auto simp add: nz jj intro: setsum_strict_mono) 
    also have "... = (\<Sum>m = 0..<N. \<Sum>n = 0..<jj m. f (m, n)) + e/2" using nz
      by (auto simp add: setsum_addf real_of_nat_def) 
    also have "... = setsum f IJ + e/2" 
      by (simp add: IJ_def setsum_Sigma) 
    finally have "setsum g {0..<N} < setsum f IJ + e/2" .
    hence glessf: "suminf g < setsum f IJ + e" using gless 
      by auto
    have finite_IJ: "finite IJ"
      by (simp add: IJ_def) 
    def NIJ \<equiv> "Max (prod_decode -` IJ)"
    have IJsb: "IJ \<subseteq> prod_decode ` {0..NIJ}"
      proof (auto simp add: NIJ_def)
        fix i j
        assume ij:"(i,j) \<in> IJ"
        hence "(i,j) = prod_decode (prod_encode (i,j))"
          by simp
        thus "(i,j) \<in> prod_decode ` {0..Max (prod_decode -` IJ)}"
          by (rule image_eqI) 
             (simp add: ij finite_vimageI [OF finite_IJ inj_prod_decode])
      qed
    have "setsum f IJ \<le> setsum f (prod_decode `{0..NIJ})"
      by (rule setsum_mono2) (auto simp add: IJsb) 
    also have "... = (\<Sum>k = 0..NIJ. f (prod_decode k))"
      by (simp add: setsum_reindex inj_prod_decode)
    also have "... = (\<Sum>k = 0..<Suc NIJ. f (prod_decode k))"
      by (metis atLeast0AtMost atLeast0LessThan lessThan_Suc_atMost)
    finally have "setsum f IJ \<le> (\<Sum>k = 0..<Suc NIJ. f (prod_decode k))" .
    thus "\<exists>n. suminf g \<le> (\<Sum>x = 0..<n. f (prod_decode x)) + e" using glessf
      by (metis add_right_mono local.glessf not_leE order_le_less_trans less_asym)
  qed
qed

end