Theory Infinite_Sum

(*
  Title:    HOL/Analysis/Infinite_Sum.thy
  Author:   Dominique Unruh, University of Tartu
            Manuel Eberl, University of Innsbruck

  A theory of sums over possibly infinite sets.
*)

section ‹Infinite sums›
latex‹\label{section:Infinite_Sum}›

text ‹In this theory, we introduce the definition of infinite sums, i.e., sums ranging over an
infinite, potentially uncountable index set with no particular ordering.
(This is different from series. Those are sums indexed by natural numbers,
and the order of the index set matters.)

Our definition is quite standard: $s:=\sum_{x\in A} f(x)$ is the limit of finite sums $s_F:=\sum_{x\in F} f(x)$ for increasing $F$.
That is, $s$ is the limit of the net $s_F$ where $F$ are finite subsets of $A$ ordered by inclusion.
We believe that this is the standard definition for such sums.
See, e.g., Definition 4.11 in cite"conway2013course".
This definition is quite general: it is well-defined whenever $f$ takes values in some
commutative monoid endowed with a Hausdorff topology.
(Examples are reals, complex numbers, normed vector spaces, and more.)›

theory Infinite_Sum
  imports
    Elementary_Topology
    "HOL-Library.Extended_Nonnegative_Real"
    "HOL-Library.Complex_Order"
begin

subsection ‹Definition and syntax›

definition HAS_SUM :: ('a  'b :: {comm_monoid_add, topological_space})  'a set  'b  bool 
    where has_sum_def: HAS_SUM f A x  (sum f  x) (finite_subsets_at_top A)

abbreviation has_sum (infixr "has'_sum" 46) where
  "(f has_sum S) A  HAS_SUM f A S"

definition summable_on :: "('a  'b::{comm_monoid_add, topological_space})  'a set  bool" (infixr "summable'_on" 46) where
  "f summable_on A  (x. (f has_sum x) A)"

definition infsum :: "('a  'b::{comm_monoid_add,t2_space})  'a set  'b" where
  "infsum f A = (if f summable_on A then Lim (finite_subsets_at_top A) (sum f) else 0)"

abbreviation abs_summable_on :: "('a  'b::real_normed_vector)  'a set  bool" (infixr "abs'_summable'_on" 46) where
  "f abs_summable_on A  (λx. norm (f x)) summable_on A"

syntax (ASCII)
  "_infsum" :: "pttrn  'a set  'b  'b::topological_comm_monoid_add"  ("(3INFSUM (_/:_)./ _)" [0, 51, 10] 10)
syntax
  "_infsum" :: "pttrn  'a set  'b  'b::topological_comm_monoid_add"  ("(2(_/_)./ _)" [0, 51, 10] 10)
translations ― ‹Beware of argument permutation!›
  "iA. b"  "CONST infsum (λi. b) A"

syntax (ASCII)
  "_univinfsum" :: "pttrn  'a  'a"  ("(3INFSUM _./ _)" [0, 10] 10)
syntax
  "_univinfsum" :: "pttrn  'a  'a"  ("(2_./ _)" [0, 10] 10)
translations
  "x. t"  "CONST infsum (λx. t) (CONST UNIV)"

syntax (ASCII)
  "_qinfsum" :: "pttrn  bool  'a  'a"  ("(3INFSUM _ |/ _./ _)" [0, 0, 10] 10)
syntax
  "_qinfsum" :: "pttrn  bool  'a  'a"  ("(2_ | (_)./ _)" [0, 0, 10] 10)
translations
  "x|P. t" => "CONST infsum (λx. t) {x. P}"

print_translation let
  fun sum_tr' [Abs (x, Tx, t), Const (@{const_syntax Collect}, _) $ Abs (y, Ty, P)] =
        if x <> y then raise Match
        else
          let
            val x' = Syntax_Trans.mark_bound_body (x, Tx);
            val t' = subst_bound (x', t);
            val P' = subst_bound (x', P);
          in
            Syntax.const @{syntax_const "_qinfsum"} $ Syntax_Trans.mark_bound_abs (x, Tx) $ P' $ t'
          end
    | sum_tr' _ = raise Match;
in [(@{const_syntax infsum}, K sum_tr')] end

subsection ‹General properties›

lemma infsumI:
  fixes f g :: 'a  'b::{comm_monoid_add, t2_space}
  assumes (f has_sum x) A
  shows infsum f A = x
  by (metis assms finite_subsets_at_top_neq_bot infsum_def summable_on_def has_sum_def tendsto_Lim)

lemma infsum_eqI:
  fixes f g :: 'a  'b::{comm_monoid_add, t2_space}
  assumes x = y
  assumes (f has_sum x) A
  assumes (g has_sum y) B
  shows infsum f A = infsum g B
  using assms infsumI by blast

lemma infsum_eqI':
  fixes f g :: 'a  'b::{comm_monoid_add, t2_space}
  assumes x. (f has_sum x) A  (g has_sum x) B
  shows infsum f A = infsum g B
  by (metis assms infsum_def infsum_eqI summable_on_def)

lemma infsum_not_exists:
  fixes f :: 'a  'b::{comm_monoid_add, t2_space}
  assumes ¬ f summable_on A
  shows infsum f A = 0
  by (simp add: assms infsum_def)

lemma summable_iff_has_sum_infsum: "f summable_on A  (f has_sum (infsum f A)) A"
  using infsumI summable_on_def by blast

lemma has_sum_infsum[simp]:
  assumes f summable_on S
  shows (f has_sum (infsum f S)) S
  using assms summable_iff_has_sum_infsum by blast

lemma has_sum_cong_neutral:
  fixes f g :: 'a  'b::{comm_monoid_add, topological_space}
  assumes x. xT-S  g x = 0
  assumes x. xS-T  f x = 0
  assumes x. xST  f x = g x
  shows "(f has_sum x) S  (g has_sum x) T"
proof -
  have eventually P (filtermap (sum f) (finite_subsets_at_top S))
      = eventually P (filtermap (sum g) (finite_subsets_at_top T)) for P
  proof 
    assume eventually P (filtermap (sum f) (finite_subsets_at_top S))
    then obtain F0 where finite F0 and F0  S and F0_P: F. finite F  F  S  F  F0  P (sum f F)
      by (metis (no_types, lifting) eventually_filtermap eventually_finite_subsets_at_top)
    define F0' where F0' = F0  T
    have [simp]: finite F0' F0'  T
      by (simp_all add: F0'_def finite F0)
    have P (sum g F) if finite F F  T F  F0' for F
    proof -
      have P (sum f ((FS)  (F0S)))
        by (intro F0_P) (use F0  S finite F0 that in auto)
      also have sum f ((FS)  (F0S)) = sum g F
        by (intro sum.mono_neutral_cong) (use that finite F0 F0'_def assms in auto)
      finally show ?thesis .
    qed
    with F0'  T finite F0' show eventually P (filtermap (sum g) (finite_subsets_at_top T))
      by (metis (no_types, lifting) eventually_filtermap eventually_finite_subsets_at_top)
  next
    assume eventually P (filtermap (sum g) (finite_subsets_at_top T))
    then obtain F0 where finite F0 and F0  T and F0_P: F. finite F  F  T  F  F0  P (sum g F)
      by (metis (no_types, lifting) eventually_filtermap eventually_finite_subsets_at_top)
    define F0' where F0' = F0  S
    have [simp]: finite F0' F0'  S
      by (simp_all add: F0'_def finite F0)
    have P (sum f F) if finite F F  S F  F0' for F
    proof -
      have P (sum g ((FT)  (F0T)))
        by (intro F0_P) (use F0  T finite F0 that in auto)
      also have sum g ((FT)  (F0T)) = sum f F
        by (intro sum.mono_neutral_cong) (use that finite F0 F0'_def assms in auto)
      finally show ?thesis .
    qed
    with F0'  S finite F0' show eventually P (filtermap (sum f) (finite_subsets_at_top S))
      by (metis (no_types, lifting) eventually_filtermap eventually_finite_subsets_at_top)
  qed

  then have tendsto_x: "(sum f  x) (finite_subsets_at_top S)  (sum g  x) (finite_subsets_at_top T)" for x
    by (simp add: le_filter_def filterlim_def)

  then show ?thesis
    by (simp add: has_sum_def)
qed

lemma summable_on_cong_neutral: 
  fixes f g :: 'a  'b::{comm_monoid_add, topological_space}
  assumes x. xT-S  g x = 0
  assumes x. xS-T  f x = 0
  assumes x. xST  f x = g x
  shows "f summable_on S  g summable_on T"
  using has_sum_cong_neutral[of T S g f, OF assms]
  by (simp add: summable_on_def)

lemma infsum_cong_neutral: 
  fixes f g :: 'a  'b::{comm_monoid_add, t2_space}
  assumes x. xT-S  g x = 0
  assumes x. xS-T  f x = 0
  assumes x. xST  f x = g x
  shows infsum f S = infsum g T
  by (smt (verit, best) assms has_sum_cong_neutral infsum_eqI')

lemma has_sum_cong: 
  assumes "x. xA  f x = g x"
  shows "(f has_sum x) A  (g has_sum x) A"
  using assms by (intro has_sum_cong_neutral) auto

lemma summable_on_cong:
  assumes "x. xA  f x = g x"
  shows "f summable_on A  g summable_on A"
  by (metis assms summable_on_def has_sum_cong)

lemma infsum_cong:
  assumes "x. xA  f x = g x"
  shows "infsum f A = infsum g A"
  using assms infsum_eqI' has_sum_cong by blast

lemma summable_on_cofin_subset:
  fixes f :: "'a  'b::topological_ab_group_add"
  assumes "f summable_on A" and [simp]: "finite F"
  shows "f summable_on (A - F)"
proof -
  from assms(1) obtain x where lim_f: "(sum f  x) (finite_subsets_at_top A)"
    unfolding summable_on_def has_sum_def by auto
  define F' where "F' = FA"
  with assms have "finite F'" and "A-F = A-F'"
    by auto
  have "filtermap ((∪)F') (finite_subsets_at_top (A-F))
       finite_subsets_at_top A"
  proof (rule filter_leI)
    fix P assume "eventually P (finite_subsets_at_top A)"
    then obtain X where [simp]: "finite X" and XA: "X  A" 
      and P: "Y. finite Y  X  Y  Y  A  P Y"
      unfolding eventually_finite_subsets_at_top by auto
    define X' where "X' = X-F"
    hence [simp]: "finite X'" and [simp]: "X'  A-F"
      using XA by auto
    hence "finite Y  X'  Y  Y  A - F  P (F'  Y)" for Y
      using P XA unfolding X'_def using F'_def finite F' by blast
    thus "eventually P (filtermap ((∪) F') (finite_subsets_at_top (A - F)))"
      unfolding eventually_filtermap eventually_finite_subsets_at_top
      by (rule_tac x=X' in exI, simp)
  qed
  with lim_f have "(sum f  x) (filtermap ((∪)F') (finite_subsets_at_top (A-F)))"
    using tendsto_mono by blast
  have "((λG. sum f (F'  G))  x) (finite_subsets_at_top (A - F))"
    if "((sum f  (∪) F')  x) (finite_subsets_at_top (A - F))"
    using that unfolding o_def by auto
  hence "((λG. sum f (F'  G))  x) (finite_subsets_at_top (A-F))"
    using tendsto_compose_filtermap [symmetric]
    by (simp add: (sum f  x) (filtermap ((∪) F') (finite_subsets_at_top (A - F))) 
        tendsto_compose_filtermap)
  have "Y. finite Y  Y  A - F  sum f (F'  Y) = sum f F' + sum f Y"
    by (metis Diff_disjoint Int_Diff A - F = A - F' finite F' inf.orderE sum.union_disjoint)
  hence "F x in finite_subsets_at_top (A - F). sum f (F'  x) = sum f F' + sum f x"
    unfolding eventually_finite_subsets_at_top
    using exI [where x = "{}"]
    by (simp add: P. P {}  x. P x) 
  hence "((λG. sum f F' + sum f G)  x) (finite_subsets_at_top (A-F))"
    using tendsto_cong [THEN iffD1 , rotated]
      ((λG. sum f (F'  G))  x) (finite_subsets_at_top (A - F)) by fastforce
  hence "((λG. sum f F' + sum f G)  sum f F' + (x-sum f F')) (finite_subsets_at_top (A-F))"
    by simp
  hence "(sum f  x - sum f F') (finite_subsets_at_top (A-F))"
    using tendsto_add_const_iff by blast    
  thus "f summable_on (A - F)"
    unfolding summable_on_def has_sum_def by auto
qed

lemma
  fixes f :: "'a  'b::{topological_ab_group_add}"
  assumes (f has_sum b) B and (f has_sum a) A and AB: "A  B"
  shows has_sum_Diff: "(f has_sum (b - a)) (B - A)"
proof -
  have finite_subsets1:
    "finite_subsets_at_top (B - A)  filtermap (λF. F - A) (finite_subsets_at_top B)"
  proof (rule filter_leI)
    fix P assume "eventually P (filtermap (λF. F - A) (finite_subsets_at_top B))"
    then obtain X where "finite X" and "X  B" 
      and P: "finite Y  X  Y  Y  B  P (Y - A)" for Y
      unfolding eventually_filtermap eventually_finite_subsets_at_top by auto

    hence "finite (X-A)" and "X-A  B - A"
      by auto
    moreover have "finite Y  X-A  Y  Y  B - A  P Y" for Y
      using P[where Y="YX"] finite X X  B
      by (metis Diff_subset Int_Diff Un_Diff finite_Un inf.orderE le_sup_iff sup.orderE sup_ge2)
    ultimately show "eventually P (finite_subsets_at_top (B - A))"
      unfolding eventually_finite_subsets_at_top by meson
  qed
  have finite_subsets2: 
    "filtermap (λF. F  A) (finite_subsets_at_top B)  finite_subsets_at_top A"
    apply (rule filter_leI)
      using assms unfolding eventually_filtermap eventually_finite_subsets_at_top
      by (metis Int_subset_iff finite_Int inf_le2 subset_trans)

  from assms(1) have limB: "(sum f  b) (finite_subsets_at_top B)"
    using has_sum_def by auto
  from assms(2) have limA: "(sum f  a) (finite_subsets_at_top A)"
    using has_sum_def by blast
  have "((λF. sum f (FA))  a) (finite_subsets_at_top B)"
  proof (subst asm_rl [of "(λF. sum f (FA)) = sum f  (λF. FA)"])
    show "(λF. sum f (F  A)) = sum f  (λF. F  A)"
      unfolding o_def by auto
    show "((sum f  (λF. F  A))  a) (finite_subsets_at_top B)"
      unfolding o_def 
      using tendsto_compose_filtermap finite_subsets2 limA tendsto_mono
        (λF. sum f (F  A)) = sum f  (λF. F  A) by fastforce
  qed

  with limB have "((λF. sum f F - sum f (FA))  b - a) (finite_subsets_at_top B)"
    using tendsto_diff by blast
  have "sum f X - sum f (X  A) = sum f (X - A)" if "finite X" and "X  B" for X :: "'a set"
    using that by (metis add_diff_cancel_left' sum.Int_Diff)
  hence "F x in finite_subsets_at_top B. sum f x - sum f (x  A) = sum f (x - A)"
    by (rule eventually_finite_subsets_at_top_weakI)  
  hence "((λF. sum f (F-A))  b - a) (finite_subsets_at_top B)"
    using tendsto_cong [THEN iffD1 , rotated]
      ((λF. sum f F - sum f (F  A))  b - a) (finite_subsets_at_top B) by fastforce
  hence "(sum f  b - a) (filtermap (λF. F-A) (finite_subsets_at_top B))"
    by (subst tendsto_compose_filtermap[symmetric], simp add: o_def)
  thus ?thesis
    using finite_subsets1 has_sum_def tendsto_mono by blast
qed


lemma
  fixes f :: "'a  'b::{topological_ab_group_add}"
  assumes "f summable_on B" and "f summable_on A" and "A  B"
  shows summable_on_Diff: "f summable_on (B-A)"
  by (meson assms summable_on_def has_sum_Diff)

lemma
  fixes f :: "'a  'b::{topological_ab_group_add,t2_space}"
  assumes "f summable_on B" and "f summable_on A" and AB: "A  B"
  shows infsum_Diff: "infsum f (B - A) = infsum f B - infsum f A"
  by (metis AB assms has_sum_Diff infsumI summable_on_def)

lemma has_sum_mono_neutral:
  fixes f :: "'a'b::{ordered_comm_monoid_add,linorder_topology}"
  (* Does this really require a linorder topology? (Instead of order topology.) *)
  assumes (f has_sum a) A and "(g has_sum b) B"
  assumes x. x  AB  f x  g x
  assumes x. x  A-B  f x  0
  assumes x. x  B-A  g x  0
  shows "a  b"
proof -
  define f' g' where f' x = (if x  A then f x else 0) and g' x = (if x  B then g x else 0) for x
  have [simp]: f summable_on A g summable_on B
    using assms(1,2) summable_on_def by auto
  have (f' has_sum a) (AB)
    by (smt (verit, best) DiffE IntE Un_iff f'_def assms(1) has_sum_cong_neutral)
  then have f'_lim: (sum f'  a) (finite_subsets_at_top (AB))
    by (meson has_sum_def)
  have (g' has_sum b) (AB)
  by (smt (verit, best) DiffD1 DiffD2 IntE UnCI g'_def assms(2) has_sum_cong_neutral)
  then have g'_lim: (sum g'  b) (finite_subsets_at_top (AB))
    using has_sum_def by blast

  have "X i. X  A  B; i  X  f' i  g' i"
    using assms by (auto simp: f'_def g'_def)
  then have F x in finite_subsets_at_top (A  B). sum f' x  sum g' x
    by (intro eventually_finite_subsets_at_top_weakI sum_mono)
  then show ?thesis
    using f'_lim finite_subsets_at_top_neq_bot g'_lim tendsto_le by blast
qed

lemma infsum_mono_neutral:
  fixes f :: "'a'b::{ordered_comm_monoid_add,linorder_topology}"
  assumes "f summable_on A" and "g summable_on B"
  assumes x. x  AB  f x  g x
  assumes x. x  A-B  f x  0
  assumes x. x  B-A  g x  0
  shows "infsum f A  infsum g B"
  by (smt (verit, best) assms has_sum_infsum has_sum_mono_neutral)

lemma has_sum_mono:
  fixes f :: "'a'b::{ordered_comm_monoid_add,linorder_topology}"
  assumes "(f has_sum x) A" and "(g has_sum y) A"
  assumes x. x  A  f x  g x
  shows "x  y"
  using assms has_sum_mono_neutral by force

lemma infsum_mono:
  fixes f :: "'a'b::{ordered_comm_monoid_add,linorder_topology}"
  assumes "f summable_on A" and "g summable_on A"
  assumes x. x  A  f x  g x
  shows "infsum f A  infsum g A"
  by (meson assms has_sum_infsum has_sum_mono)

lemma has_sum_finite[simp]:
  assumes "finite F"
  shows "(f has_sum (sum f F)) F"
  using assms
  by (auto intro: tendsto_Lim simp: finite_subsets_at_top_finite infsum_def has_sum_def principal_eq_bot_iff)

lemma summable_on_finite[simp]:
  fixes f :: 'a  'b::{comm_monoid_add,topological_space}
  assumes "finite F"
  shows "f summable_on F"
  using assms summable_on_def has_sum_finite by blast

lemma infsum_finite[simp]:
  assumes "finite F"
  shows "infsum f F = sum f F"
  by (simp add: assms infsumI)

lemma has_sum_finite_approximation:
  fixes f :: "'a  'b::{comm_monoid_add,metric_space}"
  assumes "(f has_sum x) A" and "ε > 0"
  shows "F. finite F  F  A  dist (sum f F) x  ε"
proof -
  have "(sum f  x) (finite_subsets_at_top A)"
    by (meson assms(1) has_sum_def)
  hence *: "F F in (finite_subsets_at_top A). dist (sum f F) x < ε"
    using assms(2) by (rule tendstoD)
  thus ?thesis
    unfolding eventually_finite_subsets_at_top by fastforce
qed

lemma infsum_finite_approximation:
  fixes f :: "'a  'b::{comm_monoid_add,metric_space}"
  assumes "f summable_on A" and "ε > 0"
  shows "F. finite F  F  A  dist (sum f F) (infsum f A)  ε"
proof -
  from assms have "(f has_sum (infsum f A)) A"
    by (simp add: summable_iff_has_sum_infsum)
  from this and ε > 0 show ?thesis
    by (rule has_sum_finite_approximation)
qed

lemma abs_summable_summable:
  fixes f :: 'a  'b :: banach
  assumes f abs_summable_on A
  shows f summable_on A
proof -
  from assms obtain L where lim: (sum (λx. norm (f x))  L) (finite_subsets_at_top A)
    unfolding has_sum_def summable_on_def by blast
  then have *: cauchy_filter (filtermap (sum (λx. norm (f x))) (finite_subsets_at_top A))
    by (auto intro!: nhds_imp_cauchy_filter simp: filterlim_def)
  have P. eventually P (finite_subsets_at_top A) 
              (F F'. P F  P F'  dist (sum f F) (sum f F') < e) if e>0 for e
  proof -
    define d P where d = e/4 and P F  finite F  F  A  dist (sum (λx. norm (f x)) F) L < d for F
    then have d > 0
      by (simp add: d_def that)
    have ev_P: eventually P (finite_subsets_at_top A)
      using lim
      by (auto simp add: P_def[abs_def] 0 < d eventually_conj_iff eventually_finite_subsets_at_top_weakI tendsto_iff)
    
    moreover have dist (sum f F1) (sum f F2) < e if P F1 and P F2 for F1 F2
    proof -
      from ev_P
      obtain F' where finite F' and F'  A and P_sup_F': finite F  F  F'  F  A  P F for F
        by atomize_elim (simp add: eventually_finite_subsets_at_top)
      define F where F = F'  F1  F2
      have finite F and F  A
        using F_def P_def[abs_def] that finite F' F'  A by auto
      have dist_F: dist (sum (λx. norm (f x)) F) L < d
        by (metis F_def F  A P_def P_sup_F' finite F le_supE order_refl)

      have dist_F_subset: dist (sum f F) (sum f F') < 2*d if F': F'  F P F' for F'
      proof -
        have dist (sum f F) (sum f F') = norm (sum f (F-F'))
          unfolding dist_norm using finite F F' by (subst sum_diff) auto
        also have   norm (xF-F'. norm (f x))
          by (rule order.trans[OF sum_norm_le[OF order.refl]]) auto
        also have  = dist (xF. norm (f x)) (xF'. norm (f x))
          unfolding dist_norm using finite F F' by (subst sum_diff) auto
        also have  < 2 * d
          using dist_F F' unfolding P_def dist_norm real_norm_def by linarith
        finally show dist (sum f F) (sum f F') < 2*d .
      qed

      have dist (sum f F1) (sum f F2)  dist (sum f F) (sum f F1) + dist (sum f F) (sum f F2)
        by (rule dist_triangle3)
      also have  < 2 * d + 2 * d
        by (intro add_strict_mono dist_F_subset that) (auto simp: F_def)
      also have   e
        by (auto simp: d_def)
      finally show dist (sum f F1) (sum f F2) < e .
    qed
    then show ?thesis
      using ev_P by blast
  qed
  then have cauchy_filter (filtermap (sum f) (finite_subsets_at_top A))
    by (simp add: cauchy_filter_metric_filtermap)
  moreover have "complete (UNIV::'b set)"
    by (meson Cauchy_convergent UNIV_I complete_def convergent_def)
  ultimately obtain L' where (sum f  L') (finite_subsets_at_top A)
    using complete_uniform[where S=UNIV] by (force simp add: filterlim_def)
  then show ?thesis
    using summable_on_def has_sum_def by blast
qed

text ‹The converse of @{thm [source] abs_summable_summable} does not hold:
  Consider the Hilbert space of square-summable sequences.
  Let $e_i$ denote the sequence with 1 in the $i$th position and 0 elsewhere.
  Let $f(i) := e_i/i$ for $i\geq1$. We have term¬ f abs_summable_on UNIV because $\lVert f(i)\rVert=1/i$
  and thus the sum over $\lVert f(i)\rVert$ diverges. On the other hand, we have termf summable_on UNIV;
  the limit is the sequence with $1/i$ in the $i$th position.

  (We have not formalized this separating example here because to the best of our knowledge,
  this Hilbert space has not been formalized in Isabelle/HOL yet.)›

lemma norm_has_sum_bound:
  fixes f :: "'b  'a::real_normed_vector"
    and A :: "'b set"
  assumes "((λx. norm (f x)) has_sum n) A"
  assumes "(f has_sum a) A"
  shows "norm a  n"
proof -
  have "norm a  n + ε" if "ε>0" for ε
  proof-
    have "F. norm (a - sum f F)  ε  finite F  F  A"
      using has_sum_finite_approximation[where A=A and f=f and ε="ε"] assms 0 < ε
      by (metis dist_commute dist_norm)
    then obtain F where "norm (a - sum f F)  ε"
      and "finite F" and "F  A"
      by (simp add: atomize_elim)
    hence "norm a  norm (sum f F) + ε"
      by (metis add.commute diff_add_cancel dual_order.refl norm_triangle_mono)
    also have "  sum (λx. norm (f x)) F + ε"
      using norm_sum by auto
    also have "  n + ε"
    proof (intro add_right_mono [OF has_sum_mono_neutral])
      show "((λx. norm (f x)) has_sum (xF. norm (f x))) F"
        by (simp add: finite F)
    qed (use F  A assms in auto)
    finally show ?thesis 
      by assumption
  qed
  thus ?thesis
    using linordered_field_class.field_le_epsilon by blast
qed

lemma norm_infsum_bound:
  fixes f :: "'b  'a::real_normed_vector"
    and A :: "'b set"
  assumes "f abs_summable_on A"
  shows "norm (infsum f A)  infsum (λx. norm (f x)) A"
proof (cases "f summable_on A")
  case True
  have "((λx. norm (f x)) has_sum (xA. norm (f x))) A"
    by (simp add: assms)
  then show ?thesis
    by (metis True has_sum_infsum norm_has_sum_bound)
next
  case False
  obtain t where t_def: "(sum (λx. norm (f x))  t) (finite_subsets_at_top A)"
    using assms unfolding summable_on_def has_sum_def by blast
  have sumpos: "sum (λx. norm (f x)) X  0"
    for X
    by (simp add: sum_nonneg)
  have tgeq0:"t  0"
  proof(rule ccontr)
    define S::"real set" where "S = {s. s < 0}"
    assume "¬ 0  t"
    hence "t < 0" by simp
    hence "t  S"
      unfolding S_def by blast
    moreover have "open S"
      by (metis S_def lessThan_def open_real_lessThan)
    ultimately have "F X in finite_subsets_at_top A. (xX. norm (f x))  S"
      using t_def unfolding tendsto_def by blast
    hence "X. (xX. norm (f x))  S"
      by (metis (no_types, lifting) eventually_mono filterlim_iff finite_subsets_at_top_neq_bot tendsto_Lim)
    then obtain X where "(xX. norm (f x))  S"
      by blast
    hence "(xX. norm (f x)) < 0"
      unfolding S_def by auto      
    thus False by (simp add: leD sumpos)
  qed
  have "∃!h. (sum (λx. norm (f x))  h) (finite_subsets_at_top A)"
    using t_def finite_subsets_at_top_neq_bot tendsto_unique by blast
  hence "t = (Topological_Spaces.Lim (finite_subsets_at_top A) (sum (λx. norm (f x))))"
    using t_def unfolding Topological_Spaces.Lim_def
    by (metis the_equality)     
  hence "Lim (finite_subsets_at_top A) (sum (λx. norm (f x)))  0"
    using tgeq0 by blast
  thus ?thesis unfolding infsum_def 
    using False by auto
qed

lemma infsum_tendsto:
  assumes f summable_on S
  shows ((λF. sum f F)  infsum f S) (finite_subsets_at_top S)
  using assms has_sum_def has_sum_infsum by blast

lemma has_sum_0: 
  assumes x. xM  f x = 0
  shows (f has_sum 0) M
  by (metis assms finite.intros(1) has_sum_cong has_sum_cong_neutral has_sum_finite sum.neutral_const)

lemma summable_on_0:
  assumes x. xM  f x = 0
  shows f summable_on M
  using assms summable_on_def has_sum_0 by blast

lemma infsum_0:
  assumes x. xM  f x = 0
  shows infsum f M = 0
  by (metis assms finite_subsets_at_top_neq_bot infsum_def has_sum_0 has_sum_def tendsto_Lim)

text ‹Variants of @{thm [source] infsum_0} etc. suitable as simp-rules›
lemma infsum_0_simp[simp]: infsum (λ_. 0) M = 0
  by (simp_all add: infsum_0)

lemma summable_on_0_simp[simp]: (λ_. 0) summable_on M
  by (simp_all add: summable_on_0)

lemma has_sum_0_simp[simp]: ((λ_. 0) has_sum 0) M
  by (simp_all add: has_sum_0)


lemma has_sum_add:
  fixes f g :: "'a  'b::{topological_comm_monoid_add}"
  assumes (f has_sum a) A
  assumes (g has_sum b) A
  shows ((λx. f x + g x) has_sum (a + b)) A
proof -
  from assms have lim_f: (sum f  a)  (finite_subsets_at_top A)
    and lim_g: (sum g  b)  (finite_subsets_at_top A)
    by (simp_all add: has_sum_def)
  then have lim: (sum (λx. f x + g x)  a + b) (finite_subsets_at_top A)
    unfolding sum.distrib by (rule tendsto_add)
  then show ?thesis
    by (simp_all add: has_sum_def)
qed

lemma summable_on_add:
  fixes f g :: "'a  'b::{topological_comm_monoid_add}"
  assumes f summable_on A
  assumes g summable_on A
  shows (λx. f x + g x) summable_on A
  by (metis (full_types) assms summable_on_def has_sum_add)

lemma infsum_add:
  fixes f g :: "'a  'b::{topological_comm_monoid_add, t2_space}"
  assumes f summable_on A
  assumes g summable_on A
  shows infsum (λx. f x + g x) A = infsum f A + infsum g A
proof -
  have ((λx. f x + g x) has_sum (infsum f A + infsum g A)) A
    by (simp add: assms has_sum_add)
  then show ?thesis
    using infsumI by blast
qed


lemma has_sum_Un_disjoint:
  fixes f :: "'a  'b::topological_comm_monoid_add"
  assumes "(f has_sum a) A"
  assumes "(f has_sum b) B"
  assumes disj: "A  B = {}"
  shows (f has_sum (a + b)) (A  B)
proof -
  define fA fB where fA x = (if x  A then f x else 0)
    and fB x = (if x  A then f x else 0) for x
  have fA: (fA has_sum a) (A  B)
    by (smt (verit, ccfv_SIG) DiffD1 DiffD2 UnCI fA_def assms(1) has_sum_cong_neutral inf_sup_absorb)
  have fB: (fB has_sum b) (A  B)
    by (smt (verit, best) DiffD1 DiffD2 IntE Un_iff fB_def assms(2) disj disjoint_iff has_sum_cong_neutral)
  have fAB: f x = fA x + fB x for x
    unfolding fA_def fB_def by simp
  show ?thesis
    unfolding fAB
    using fA fB by (rule has_sum_add)
qed

lemma summable_on_Un_disjoint:
  fixes f :: "'a  'b::topological_comm_monoid_add"
  assumes "f summable_on A"
  assumes "f summable_on B"
  assumes disj: "A  B = {}"
  shows f summable_on (A  B)
  by (meson assms disj summable_on_def has_sum_Un_disjoint)

lemma infsum_Un_disjoint:
  fixes f :: "'a  'b::{topological_comm_monoid_add, t2_space}"
  assumes "f summable_on A"
  assumes "f summable_on B"
  assumes disj: "A  B = {}"
  shows infsum f (A  B) = infsum f A + infsum f B
  by (intro infsumI has_sum_Un_disjoint has_sum_infsum assms)  

lemma norm_summable_imp_has_sum:
  fixes f :: "nat  'a :: banach"
  assumes "summable (λn. norm (f n))" and "f sums S"
  shows   "(f has_sum S) (UNIV :: nat set)"
  unfolding has_sum_def tendsto_iff eventually_finite_subsets_at_top
proof clarsimp
  fix ε::real 
  assume "ε > 0"
  from assms obtain S' where S': "(λn. norm (f n)) sums S'"
    by (auto simp: summable_def)
  with ε > 0 obtain N where N: "n. n  N  ¦S' - (i<n. norm (f i))¦ < ε"
    by (auto simp: tendsto_iff eventually_at_top_linorder sums_def dist_norm abs_minus_commute)
  have "dist (sum f Y) S < ε" if "finite Y" "{..<N}  Y" for Y
  proof -
    from that have "(λn. if n  Y then 0 else f n) sums (S - sum f Y)"
      by (intro sums_If_finite_set'[OF f sums S]) (auto simp: sum_negf)
    hence "S - sum f Y = (n. if n  Y then 0 else f n)"
      by (simp add: sums_iff)
    also have "norm   (n. norm (if n  Y then 0 else f n))"
      by (rule summable_norm[OF summable_comparison_test'[OF assms(1)]]) auto
    also have "  (n. if n < N then 0 else norm (f n))"
      using that by (intro suminf_le summable_comparison_test'[OF assms(1)]) auto
    also have "(λn. if n  {..<N} then 0 else norm (f n)) sums (S' - (i<N. norm (f i)))" 
      by (intro sums_If_finite_set'[OF S']) (auto simp: sum_negf)
    hence "(n. if n < N then 0 else norm (f n)) = S' - (i<N. norm (f i))"
      by (simp add: sums_iff)
    also have "S' - (i<N. norm (f i))  ¦S' - (i<N. norm (f i))¦" by simp
    also have " < ε" by (rule N) auto
    finally show ?thesis by (simp add: dist_norm norm_minus_commute)
  qed
  then show "X. finite X  (Y. finite Y  X  Y  dist (sum f Y) S < ε)"
    by (meson finite_lessThan subset_UNIV)
qed

lemma norm_summable_imp_summable_on:
  fixes f :: "nat  'a :: banach"
  assumes "summable (λn. norm (f n))"
  shows   "f summable_on UNIV"
  using norm_summable_imp_has_sum[OF assms, of "suminf f"] assms
  by (auto simp: sums_iff summable_on_def dest: summable_norm_cancel)

text ‹The following lemma indeed needs a complete space (as formalized by the premise termcomplete UNIV).
  The following two counterexamples show this:
  \begin{itemize}
  \item Consider the real vector space $V$ of sequences with finite support, and with the $\ell_2$-norm (sum of squares).
      Let $e_i$ denote the sequence with a $1$ at position $i$.
      Let $f : \mathbb Z \to V$ be defined as $f(n) := e_{\lvert n\rvert} / n$ (with $f(0) := 0$).
      We have that $\sum_{n\in\mathbb Z} f(n) = 0$ (it even converges absolutely). 
      But $\sum_{n\in\mathbb N} f(n)$ does not exist (it would converge against a sequence with infinite support).
  
  \item Let $f$ be a positive rational valued function such that $\sum_{x\in B} f(x)$ is $\sqrt 2$ and $\sum_{x\in A} f(x)$ is 1 (over the reals, with $A\subseteq B$).
      Then $\sum_{x\in B} f(x)$ does not exist over the rationals. But $\sum_{x\in A} f(x)$ exists.
  \end{itemize}

  The lemma also requires uniform continuity of the addition. And example of a topological group with continuous 
  but not uniformly continuous addition would be the positive reals with the usual multiplication as the addition.
  We do not know whether the lemma would also hold for such topological groups.›

lemma summable_on_subset_aux:
  fixes A B and f :: 'a  'b::{ab_group_add, uniform_space}
  assumes complete (UNIV :: 'b set)
  assumes plus_cont: uniformly_continuous_on UNIV (λ(x::'b,y). x+y)
  assumes f summable_on A
  assumes B  A
  shows f summable_on B
proof -
  let ?filter_fB = filtermap (sum f) (finite_subsets_at_top B)
  from f summable_on A
  obtain S where (sum f  S) (finite_subsets_at_top A) (is (sum f  S) ?filter_A)
    using summable_on_def has_sum_def by blast
  then have cauchy_fA: cauchy_filter (filtermap (sum f) (finite_subsets_at_top A)) (is cauchy_filter ?filter_fA)
    by (auto intro!: nhds_imp_cauchy_filter simp: filterlim_def)

  have cauchy_filter (filtermap (sum f) (finite_subsets_at_top B))
  proof (unfold cauchy_filter_def, rule filter_leI)
    fix E :: ('b×'b)  bool assume eventually E uniformity
    then obtain E' where eventually E' uniformity and E'E'E: E' (x, y)  E' (y, z)  E (x, z) for x y z
      using uniformity_trans by blast
    obtain D where eventually D uniformity and DE: D (x, y)  E' (x+c, y+c) for x y c
      using plus_cont eventually E' uniformity
      unfolding uniformly_continuous_on_uniformity filterlim_def le_filter_def uniformity_prod_def
      by (auto simp: case_prod_beta eventually_filtermap eventually_prod_same uniformity_refl)
    have DE': "E' (x, y)" if "D (x + c, y + c)" for x y c
      using DE[of "x + c" "y + c" "-c"] that by simp

    from eventually D uniformity and cauchy_fA have eventually D (?filter_fA ×F ?filter_fA)
      unfolding cauchy_filter_def le_filter_def by simp
    then obtain P1 P2
      where ev_P1: eventually (λF. P1 (sum f F)) ?filter_A 
        and ev_P2: eventually (λF. P2 (sum f F)) ?filter_A
        and P1P2E: P1 x  P2 y  D (x, y) for x y
      unfolding eventually_prod_filter eventually_filtermap
      by auto
    from ev_P1 obtain F1 where F1: finite F1 F1  A F. FF1  finite F  FA  P1 (sum f F)
      by (metis eventually_finite_subsets_at_top)
    from ev_P2 obtain F2 where F2: finite F2 F2  A F. FF2  finite F  FA  P2 (sum f F)
      by (metis eventually_finite_subsets_at_top)
    define F0 F0A F0B where F0  F1  F2 and F0A  F0 - B and F0B  F0  B
    have [simp]: finite F0  F0  A
      using F1  A F2  A finite F1 finite F2 unfolding F0_def by blast+
 
    have *: "E' (sum f F1', sum f F2')"
      if "F1'F0B" "F2'F0B" "finite F1'" "finite F2'" "F1'B" "F2'B" for F1' F2'
    proof (intro DE'[where c = "sum f F0A"] P1P2E)
      have "P1 (sum f (F1'  F0A))"
        using that assms F1(1,2) F2(1,2) by (intro F1) (auto simp: F0A_def F0B_def F0_def)
      thus "P1 (sum f F1' + sum f F0A)"
        by (subst (asm) sum.union_disjoint) (use that in auto simp: F0A_def)
    next
      have "P2 (sum f (F2'  F0A))"
        using that assms F1(1,2) F2(1,2) by (intro F2) (auto simp: F0A_def F0B_def F0_def)
      thus "P2 (sum f F2' + sum f F0A)"
        by (subst (asm) sum.union_disjoint) (use that in auto simp: F0A_def)      
    qed

    have "eventually (λx. E' (x, sum f F0B)) (filtermap (sum f) (finite_subsets_at_top B))"
     and "eventually (λx. E' (sum f F0B, x)) (filtermap (sum f) (finite_subsets_at_top B))"
        unfolding eventually_filtermap eventually_finite_subsets_at_top
        by (rule exI[of _ F0B]; use * in force simp: F0B_def)+
      then 
    show eventually E (?filter_fB ×F ?filter_fB)
      unfolding eventually_prod_filter
      using E'E'E by blast
  qed

  then obtain x where ?filter_fB  nhds x
    using cauchy_filter_complete_converges[of ?filter_fB UNIV] complete (UNIV :: _)
    by (auto simp: filtermap_bot_iff)
  then have (sum f  x) (finite_subsets_at_top B)
    by (auto simp: filterlim_def)
  then show ?thesis
    by (auto simp: summable_on_def has_sum_def)
qed

text ‹A special case of @{thm [source] summable_on_subset_aux} for Banach spaces with fewer premises.›

lemma summable_on_subset_banach:
  fixes A B and f :: 'a  'b::banach
  assumes f summable_on A
  assumes B  A
  shows f summable_on B
  by (meson Cauchy_convergent UNIV_I assms complete_def convergent_def isUCont_plus summable_on_subset_aux)

lemma has_sum_empty[simp]: (f has_sum 0) {}
  by (meson ex_in_conv has_sum_0)

lemma summable_on_empty[simp]: f summable_on {}
  by auto

lemma infsum_empty[simp]: infsum f {} = 0
  by simp

lemma sum_has_sum:
  fixes f :: "'a  'b::topological_comm_monoid_add"
  assumes finite A
  assumes a. a  A  (f has_sum (s a)) (B a)
  assumes a a'. aA  a'A  aa'  B a  B a' = {}
  shows (f has_sum (sum s A)) (aA. B a)
  using assms 
proof (induction)
  case empty
  then show ?case 
    by simp
next
  case (insert x A)
  have (f has_sum (s x)) (B x)
    by (simp add: insert.prems)
  moreover have IH: (f has_sum (sum s A)) (aA. B a)
    using insert by simp
  ultimately have (f has_sum (s x + sum s A)) (B x  (aA. B a))
    using insert by (intro has_sum_Un_disjoint) auto
  then show ?case
    using insert.hyps by auto
qed


lemma summable_on_finite_union_disjoint:
  fixes f :: "'a  'b::topological_comm_monoid_add"
  assumes finite: finite A
  assumes conv: a. a  A  f summable_on (B a)
  assumes disj: a a'. aA  a'A  aa'  B a  B a' = {}
  shows f summable_on (aA. B a)
  using sum_has_sum [of A f B] assms unfolding summable_on_def by metis

lemma sum_infsum:
  fixes f :: "'a  'b::{topological_comm_monoid_add, t2_space}"
  assumes finite: finite A
  assumes conv: a. a  A  f summable_on (B a)
  assumes disj: a a'. aA  a'A  aa'  B a  B a' = {}
  shows sum (λa. infsum f (B a)) A = infsum f (aA. B a)
  by (metis (no_types, lifting) assms has_sum_infsum infsumI sum_has_sum)

text ‹The lemmas infsum_comm_additive_general› and infsum_comm_additive› (and variants) below both state that the infinite sum commutes with
  a continuous additive function. infsum_comm_additive_general› is stated more for more general type classes
  at the expense of a somewhat less compact formulation of the premises.
  E.g., by avoiding the constant constadditive which introduces an additional sort constraint
  (group instead of monoid). For example, extended reals (typereal, typennreal) are not covered
  by infsum_comm_additive›.›


lemma has_sum_comm_additive_general: 
  fixes f :: 'b :: {comm_monoid_add,topological_space}  'c :: {comm_monoid_add,topological_space}
  assumes f_sum: F. finite F  F  S  sum (f  g) F = f (sum g F)
      ― ‹Not using constadditive because it would add sort constraint classab_group_add
  assumes cont: f x f x
    ― ‹For classt2_space, this is equivalent to isCont f x› by @{thm [source] isCont_def}.›
  assumes infsum: (g has_sum x) S
  shows ((f  g) has_sum (f x)) S 
proof -
  have (sum g  x) (finite_subsets_at_top S)
    using infsum has_sum_def by blast
  then have ((f  sum g)  f x) (finite_subsets_at_top S)
    by (meson cont filterlim_def tendsto_at_iff_tendsto_nhds tendsto_compose_filtermap tendsto_mono)
  then have (sum (f  g)  f x) (finite_subsets_at_top S)
    using tendsto_cong f_sum
    by (simp add: Lim_transform_eventually eventually_finite_subsets_at_top_weakI)
  then show ((f  g) has_sum (f x)) S
    using has_sum_def by blast 
qed

lemma summable_on_comm_additive_general:
  fixes f :: 'b :: {comm_monoid_add,topological_space}  'c :: {comm_monoid_add,topological_space}
  assumes F. finite F  F  S  sum (f  g) F = f (sum g F)
    ― ‹Not using constadditive because it would add sort constraint classab_group_add
  assumes x. (g has_sum x) S  f x f x
    ― ‹For classt2_space, this is equivalent to isCont f x› by @{thm [source] isCont_def}.›
  assumes g summable_on S
  shows (f  g) summable_on S
  by (meson assms summable_on_def has_sum_comm_additive_general has_sum_def infsum_tendsto)

lemma infsum_comm_additive_general:
  fixes f :: 'b :: {comm_monoid_add,t2_space}  'c :: {comm_monoid_add,t2_space}
  assumes f_sum: F. finite F  F  S  sum (f  g) F = f (sum g F)
      ― ‹Not using constadditive because it would add sort constraint classab_group_add
  assumes isCont f (infsum g S)
  assumes g summable_on S
  shows infsum (f  g) S = f (infsum g S)
  using assms
  by (intro infsumI has_sum_comm_additive_general has_sum_infsum) (auto simp: isCont_def)

lemma has_sum_comm_additive: 
  fixes f :: 'b :: {ab_group_add,topological_space}  'c :: {ab_group_add,topological_space}
  assumes additive f
  assumes f x f x
    ― ‹For classt2_space, this is equivalent to isCont f x› by @{thm [source] isCont_def}.›
  assumes infsum: (g has_sum x) S
  shows ((f  g) has_sum (f x)) S
  using assms
  by (intro has_sum_comm_additive_general has_sum_infsum) (auto simp: isCont_def additive.sum) 

lemma summable_on_comm_additive:
  fixes f :: 'b :: {ab_group_add,t2_space}  'c :: {ab_group_add,topological_space}
  assumes additive f
  assumes isCont f (infsum g S)
  assumes g summable_on S
  shows (f  g) summable_on S
  by (meson assms summable_on_def has_sum_comm_additive has_sum_infsum isContD)

lemma infsum_comm_additive:
  fixes f :: 'b :: {ab_group_add,t2_space}  'c :: {ab_group_add,t2_space}
  assumes additive f
  assumes isCont f (infsum g S)
  assumes g summable_on S
  shows infsum (f  g) S = f (infsum g S)
  by (rule infsum_comm_additive_general; auto simp: assms additive.sum)

lemma nonneg_bdd_above_has_sum:
  fixes f :: 'a  'b :: {conditionally_complete_linorder, ordered_comm_monoid_add, linorder_topology}
  assumes x. xA  f x  0
  assumes bdd_above (sum f ` {F. FA  finite F})
  shows (f has_sum (SUP F{F. finite F  FA}. sum f F)) A
proof -
  have (sum f  (SUP F{F. finite F  FA}. sum f F)) (finite_subsets_at_top A)
  proof (rule order_tendstoI)
    fix a assume a < (SUP F{F. finite F  FA}. sum f F)
    then obtain F where a < sum f F and finite F and F  A
      by (metis (mono_tags, lifting) Collect_cong Collect_empty_eq assms(2) empty_subsetI finite.emptyI less_cSUP_iff mem_Collect_eq)
    have "Y. finite Y; F  Y; Y  A  a < sum f Y"
      by (meson DiffE a < sum f F assms(1) less_le_trans subset_iff sum_mono2)
    then show F x in finite_subsets_at_top A. a < sum f x
      by (metis F  A finite F eventually_finite_subsets_at_top)
  next
    fix a assume *: (SUP F{F. finite F  FA}. sum f F) < a
    have "sum f F  (SUP F{F. finite F  FA}. sum f F)" if FA and finite F for F
        by (rule cSUP_upper) (use that assms(2) in auto simp: conj_commute)
    then show F x in finite_subsets_at_top A. sum f x < a
      by (metis (no_types, lifting) "*" eventually_finite_subsets_at_top_weakI order_le_less_trans)
  qed
  then show ?thesis
    using has_sum_def by blast
qed

lemma nonneg_bdd_above_summable_on:
  fixes f :: 'a  'b :: {conditionally_complete_linorder, ordered_comm_monoid_add, linorder_topology}
  assumes x. xA  f x  0
  assumes bdd_above (sum f ` {F. FA  finite F})
  shows f summable_on A
  using assms summable_on_def nonneg_bdd_above_has_sum by blast

lemma nonneg_bdd_above_infsum:
  fixes f :: 'a  'b :: {conditionally_complete_linorder, ordered_comm_monoid_add, linorder_topology}
  assumes x. xA  f x  0
  assumes bdd_above (sum f ` {F. FA  finite F})
  shows infsum f A = (SUP F{F. finite F  FA}. sum f F)
  using assms by (auto intro!: infsumI nonneg_bdd_above_has_sum)

lemma nonneg_has_sum_complete:
  fixes f :: 'a  'b :: {complete_linorder, ordered_comm_monoid_add, linorder_topology}
  assumes x. xA  f x  0
  shows (f has_sum (SUP F{F. finite F  FA}. sum f F)) A
  using assms nonneg_bdd_above_has_sum by blast

lemma nonneg_summable_on_complete:
  fixes f :: 'a  'b :: {complete_linorder, ordered_comm_monoid_add, linorder_topology}
  assumes x. xA  f x  0
  shows f summable_on A
  using assms nonneg_bdd_above_summable_on by blast

lemma nonneg_infsum_complete:
  fixes f :: 'a  'b :: {complete_linorder, ordered_comm_monoid_add, linorder_topology}
  assumes x. xA  f x  0
  shows infsum f A = (SUP F{F. finite F  FA}. sum f F)
  using assms nonneg_bdd_above_infsum by blast

lemma has_sum_nonneg:
  fixes f :: "'a  'b::{ordered_comm_monoid_add,linorder_topology}"
  assumes "(f has_sum a) M"
    and "x. x  M  0  f x"
  shows "a  0"
  by (metis (no_types, lifting) DiffD1 assms empty_iff has_sum_0 has_sum_mono_neutral order_refl)

lemma infsum_nonneg:
  fixes f :: "'a  'b::{ordered_comm_monoid_add,linorder_topology}"
  assumes "x. x  M  0  f x"
  shows "infsum f M  0" (is "?lhs  _")
  by (metis assms has_sum_infsum has_sum_nonneg infsum_not_exists linorder_linear)

lemma has_sum_mono2:
  fixes f :: "'a  'b::{topological_ab_group_add, ordered_comm_monoid_add,linorder_topology}"
  assumes "(f has_sum S) A" "(f has_sum S') B" "A  B"
  assumes "x. x  B - A  f x  0"
  shows   "S  S'"
  by (metis add_0 add_right_mono assms diff_add_cancel has_sum_Diff has_sum_nonneg)

lemma infsum_mono2:
  fixes f :: "'a  'b::{topological_ab_group_add, ordered_comm_monoid_add,linorder_topology}"
  assumes "f summable_on A" "f summable_on B" "A  B"
  assumes "x. x  B - A  f x  0"
  shows   "infsum f A  infsum f B"
  by (rule has_sum_mono2[OF has_sum_infsum has_sum_infsum]) (use assms in auto)

lemma finite_sum_le_has_sum:
  fixes f :: "'a  'b::{topological_ab_group_add, ordered_comm_monoid_add,linorder_topology}"
  assumes "(f has_sum S) A" "finite B" "B  A"
  assumes "x. x  A - B  f x  0"
  shows   "sum f B  S"
  by (meson assms has_sum_finite has_sum_mono2)

lemma finite_sum_le_infsum:
  fixes f :: "'a  'b::{topological_ab_group_add, ordered_comm_monoid_add,linorder_topology}"
  assumes "f summable_on A" "finite B" "B  A"
  assumes "x. x  A - B  f x  0"
  shows   "sum f B  infsum f A"
  by (rule finite_sum_le_has_sum[OF has_sum_infsum]) (use assms in auto)

lemma has_sum_reindex:
  assumes inj_on h A
  shows (g has_sum x) (h ` A)  ((g  h) has_sum x) A
proof -
  have (g has_sum x) (h ` A)  (sum g  x) (finite_subsets_at_top (h ` A))
    by (simp add: has_sum_def)
  also have   ((λF. sum g (h ` F))  x) (finite_subsets_at_top A)
    by (metis assms filterlim_filtermap filtermap_image_finite_subsets_at_top)
  also have   (sum (g  h)  x) (finite_subsets_at_top A)
  proof (intro tendsto_cong eventually_finite_subsets_at_top_weakI sum.reindex)
    show "X. finite X; X  A  inj_on h X"
      using assms subset_inj_on by blast
  qed
  also have   ((g  h) has_sum x) A
    by (simp add: has_sum_def)
  finally show ?thesis .
qed

lemma summable_on_reindex:
  assumes inj_on h A
  shows g summable_on (h ` A)  (g  h) summable_on A
  by (simp add: assms summable_on_def has_sum_reindex)

lemma infsum_reindex:
  assumes inj_on h A
  shows infsum g (h ` A) = infsum (g  h) A
  by (metis assms has_sum_infsum has_sum_reindex infsumI infsum_def)

lemma summable_on_reindex_bij_betw:
  assumes "bij_betw g A B"
  shows   "(λx. f (g x)) summable_on A  f summable_on B"
  by (smt (verit) assms bij_betw_def o_apply summable_on_cong summable_on_reindex) 

lemma infsum_reindex_bij_betw:
  assumes "bij_betw g A B"
  shows   "infsum (λx. f (g x)) A = infsum f B"
  by (metis (mono_tags, lifting) assms bij_betw_def infsum_cong infsum_reindex o_def)

lemma sum_uniformity:
  assumes plus_cont: uniformly_continuous_on UNIV (λ(x::'b::{uniform_space,comm_monoid_add},y). x+y)
  assumes EE: eventually E uniformity
  obtains D where eventually D uniformity 
    and M::'a set. f f' :: 'a  'b. card M  n  (mM. D (f m, f' m))  E (sum f M, sum f' M)
proof (atomize_elim, insert EE, induction n arbitrary: E rule:nat_induct)
  case 0
  then show ?case
    by (metis card_eq_0_iff equals0D le_zero_eq sum.infinite sum.not_neutral_contains_not_neutral uniformity_refl)
next
  case (Suc n)
  from plus_cont[unfolded uniformly_continuous_on_uniformity filterlim_def le_filter_def, rule_format, OF Suc.prems]
  obtain D1 D2 where eventually D1 uniformity and eventually D2 uniformity 
    and D1D2E: D1 (x, y)  D2 (x', y')  E (x + x', y + y') for x y x' y'
    apply atomize_elim
    by (auto simp: eventually_prod_filter case_prod_beta uniformity_prod_def eventually_filtermap)

  from Suc.IH[OF eventually D2 uniformity]
  obtain D3 where eventually D3 uniformity and D3: card M  n  (mM. D3 (f m, f' m))  D2 (sum f M, sum f' M) 
    for M :: 'a set and f f'
    by metis

  define D where D x  D1 x  D3 x for x
  have eventually D uniformity
    using D_def eventually D1 uniformity eventually D3 uniformity eventually_elim2 by blast

  have E (sum f M, sum f' M) 
    if card M  Suc n and DM: mM. D (f m, f' m)
    for M :: 'a set and f f'
  proof (cases card M = 0)
    case True
    then show ?thesis
      by (metis Suc.prems card_eq_0_iff sum.empty sum.infinite uniformity_refl) 
  next
    case False
    with card M  Suc n obtain N x where card N  n and x  N and M = insert x N
      by (metis card_Suc_eq less_Suc_eq_0_disj less_Suc_eq_le)

    from DM have m. mN  D (f m, f' m)
      using M = insert x N by blast
    with D3[OF card N  n]
    have D2_N: D2 (sum f N, sum f' N)
      using D_def by blast

    from DM 
    have D (f x, f' x)
      using M = insert x N by blast
    then have D1 (f x, f' x)
      by (simp add: D_def)

    with D2_N
    have E (f x + sum f N, f' x + sum f' N)
      using D1D2E by presburger

    then show E (sum f M, sum f' M)
      by (metis False M = insert x N x  N card.infinite finite_insert sum.insert)
  qed
  with eventually D uniformity show ?case 
    by auto
qed

lemma has_sum_Sigma:
  fixes A :: "'a set" and B :: "'a  'b set"
    and f :: 'a × 'b  'c::{comm_monoid_add,uniform_space}
  assumes plus_cont: uniformly_continuous_on UNIV (λ(x::'c,y). x+y)
  assumes summableAB: "(f has_sum a) (Sigma A B)"
  assumes summableB: x. xA  ((λy. f (x, y)) has_sum b x) (B x)
  shows "(b has_sum a) A"
proof -
  define F FB FA where F = finite_subsets_at_top (Sigma A B) and FB x = finite_subsets_at_top (B x)
    and FA = finite_subsets_at_top A for x

  from summableB
  have sum_b: (sum (λy. f (x, y))  b x) (FB x) if x  A for x
    using FB_def[abs_def] has_sum_def that by auto
  from summableAB
  have sum_S: (sum f  a) F
    using F_def has_sum_def by blast

  have finite_proj: finite {b| b. (a,b)  H} if finite H for H :: ('a×'b) set and a
    by (metis (no_types, lifting) finite_imageI finite_subset image_eqI mem_Collect_eq snd_conv subsetI that)

  have (sum b  a) FA
  proof (rule tendsto_iff_uniformity[THEN iffD2, rule_format])
    fix E :: ('c × 'c)  bool
    assume eventually E uniformity
    then obtain D where D_uni: eventually D uniformity and DDE': x y z. D (x, y)  D (y, z)  E (x, z)
      by (metis (no_types, lifting) eventually E uniformity uniformity_transE)
    from sum_S obtain G where finite G and G  Sigma A B
      and G_sum: G  H  H  Sigma A B  finite H  D (sum f H, a) for H
      unfolding tendsto_iff_uniformity
      by (metis (mono_tags, lifting) D_uni F_def eventually_finite_subsets_at_top)
    have finite (fst ` G) and fst ` G  A
      using finite G G  Sigma A B by auto
    thm uniformity_prod_def
    define Ga where Ga a = {b. (a,b)  G} for a
    have Ga_fin: finite (Ga a) and Ga_B: Ga a  B a for a
      using finite G G  Sigma A B finite_proj by (auto simp: Ga_def finite_proj)

    have E (sum b M, a) if M  fst ` G and finite M and M  A for M
    proof -
      define FMB where FMB = finite_subsets_at_top (Sigma M B)
      have eventually (λH. D (aM. b a, (a,b)H. f (a,b))) FMB
      proof -
        obtain D' where D'_uni: eventually D' uniformity 
          and card M'  card M  (mM'. D' (g m, g' m))  D (sum g M', sum g' M')
        for M' :: 'a set and g g'
          using sum_uniformity[OF plus_cont eventually D uniformity] by blast
        then have D'_sum_D: (mM. D' (g m, g' m))  D (sum g M, sum g' M) for g g'
          by auto

        obtain Ha where Ha a  Ga a and Ha_fin: finite (Ha a) and Ha_B: Ha a  B a
          and D'_sum_Ha: Ha a  L  L  B a  finite L  D' (b a, sum (λb. f (a,b)) L) if a  A for a L
        proof -
          from sum_b[unfolded tendsto_iff_uniformity, rule_format, OF _ D'_uni[THEN uniformity_sym]]
          obtain Ha0 where finite (Ha0 a) and Ha0 a  B a
            and Ha0 a  L  L  B a  finite L  D' (b a, sum (λb. f (a,b)) L) if a  A for a L
            unfolding FB_def eventually_finite_subsets_at_top unfolding prod.case by metis
          moreover define Ha where Ha a = Ha0 a  Ga a for a
          ultimately show ?thesis
            using that[where Ha=Ha]
            using Ga_fin Ga_B by auto
        qed

        have D (aM. b a, (a,b)H. f (a,b)) if finite H and H  Sigma M B and H  Sigma M Ha for H
        proof -
          define Ha' where Ha' a = {b| b. (a,b)  H} for a
          have [simp]: finite (Ha' a) and [simp]: Ha' a  Ha a and [simp]: Ha' a  B a if a  M for a
            unfolding Ha'_def using finite H H  Sigma M B Sigma M Ha  H that finite_proj by auto
          have Sigma M Ha' = H
            using that by (auto simp: Ha'_def)
          then have *: ((a,b)H. f (a,b)) = (aM. bHa' a. f (a,b))
            by (simp add: finite M sum.Sigma)
          have D' (b a, sum (λb. f (a,b)) (Ha' a)) if a  M for a
            using D'_sum_Ha M  A that by auto
          then have D (aM. b a, aM. sum (λb. f (a,b)) (Ha' a))
            by (rule_tac D'_sum_D, auto)
          with * show ?thesis
            by auto
        qed
        moreover have Sigma M Ha  Sigma M B
          using Ha_B M  A by auto
        ultimately show ?thesis
          unfolding FMB_def eventually_finite_subsets_at_top
          by (metis (no_types, lifting) Ha_fin finite_SigmaI subsetD that(2) that(3))
      qed
      moreover have eventually (λH. D ((a,b)H. f (a,b), a)) FMB
        unfolding FMB_def eventually_finite_subsets_at_top
      proof (rule exI[of _ G], safe)
        fix Y assume Y: "finite Y" "G  Y" "Y  Sigma M B"
        thus "D ((a,b)Y. f (a, b), a)"
          using G_sum[of Y] Y using that(3) by fastforce
      qed (use finite G G  Sigma A B that in auto)
      ultimately have F x in FMB. E (sum b M, a)
        by eventually_elim (use DDE' in auto)
      then show E (sum b M, a)
        using FMB_def by force
    qed
    then show F x in FA. E (sum b x, a)
      using finite (fst ` G) and fst ` G  A
      by (metis (mono_tags, lifting) FA_def eventually_finite_subsets_at_top)
  qed
  then show ?thesis
    by (simp add: FA_def has_sum_def)
qed

lemma summable_on_Sigma:
  fixes A :: "'a set" and B :: "'a  'b set"
    and f :: 'a  'b  'c::{comm_monoid_add, t2_space, uniform_space}
  assumes plus_cont: uniformly_continuous_on UNIV (λ(x::'c,y). x+y)
  assumes summableAB: "(λ(x,y). f x y) summable_on (Sigma A B)"
  assumes summableB: x. xA  (f x) summable_on (B x)
  shows (λx. infsum (f x) (B x)) summable_on A
proof -
  from summableAB obtain a where a: ((λ(x,y). f x y) has_sum a) (Sigma A B)
    using has_sum_infsum by blast
  from summableB have b: x. xA  (f x has_sum infsum (f x) (B x)) (B x)
    by (auto intro!: has_sum_infsum)
  show ?thesis
    using plus_cont a b
    by (smt (verit) has_sum_Sigma[where f=λ(x,y). f x y] has_sum_cong old.prod.case summable_on_def) 
qed

lemma infsum_Sigma:
  fixes A :: "'a set" and B :: "'a  'b set"
    and f :: 'a × 'b  'c::{comm_monoid_add, t2_space, uniform_space}
  assumes plus_cont: uniformly_continuous_on UNIV (λ(x::'c,y). x+y)
  assumes summableAB: "f summable_on (Sigma A B)"
  assumes summableB: x. xA  (λy. f (x, y)) summable_on (B x)
  shows "infsum f (Sigma A B) = infsum (λx. infsum (λy. f (x, y)) (B x)) A"
proof -
  from summableAB have a: (f has_sum infsum f (Sigma A B)) (Sigma A B)
    using has_sum_infsum by blast
  from summableB have b: x. xA  ((λy. f (x, y)) has_sum infsum (λy. f (x, y)) (B x)) (B x)
    by (auto intro!: has_sum_infsum)
  show ?thesis
    using plus_cont a b by (auto intro: infsumI[symmetric] has_sum_Sigma simp: summable_on_def)
qed

lemma infsum_Sigma':
  fixes A :: "'a set" and B :: "'a  'b set"
    and f :: 'a  'b  'c::{comm_monoid_add, t2_space, uniform_space}
  assumes plus_cont: uniformly_continuous_on UNIV (λ(x::'c,y). x+y)
  assumes summableAB: "(λ(x,y). f x y) summable_on (Sigma A B)"
  assumes summableB: x. xA  (f x) summable_on (B x)
  shows infsum (λx. infsum (f x) (B x)) A = infsum (λ(x,y). f x y) (Sigma A B)
  using infsum_Sigma[of λ(x,y). f x y A B]
  using assms by auto

text ‹A special case of @{thm [source] infsum_Sigma} etc. for Banach spaces. It has less premises.›
lemma
  fixes A :: "'a set" and B :: "'a  'b set"
    and f :: 'a  'b  'c::banach
  assumes [simp]: "(λ(x,y). f x y) summable_on (Sigma A B)"
  shows infsum_Sigma'_banach: infsum (λx. infsum (f x) (B x)) A = infsum (λ(x,y). f x y) (Sigma A B) (is ?thesis1)
    and summable_on_Sigma_banach: (λx. infsum (f x) (B x)) summable_on A (is ?thesis2)
proof -
  have fsum: (f x) summable_on (B x) if x  A for x
  proof -
    from assms
    have (λ(x,y). f x y) summable_on (Pair x ` B x)
      by (meson image_subset_iff summable_on_subset_banach mem_Sigma_iff that)
    then have ((λ(x,y). f x y)  Pair x) summable_on (B x)
      by (metis summable_on_reindex inj_on_def prod.inject)
    then show ?thesis
      by (auto simp: o_def)
  qed
  show ?thesis1
    using fsum assms infsum_Sigma' isUCont_plus by blast
  show ?thesis2
    using fsum assms isUCont_plus summable_on_Sigma by blast
qed

lemma infsum_Sigma_banach:
  fixes A :: "'a set" and B :: "'a  'b set"
    and f :: 'a × 'b  'c::banach
  assumes [simp]: "f summable_on (Sigma A B)"
  shows infsum (λx. infsum (λy. f (x,y)) (B x)) A = infsum f (Sigma A B)
  using assms by (simp add: infsum_Sigma'_banach)

lemma infsum_swap:
  fixes A :: "'a set" and B :: "'b set"
  fixes f :: "'a  'b  'c::{comm_monoid_add,t2_space,uniform_space}"
  assumes plus_cont: uniformly_continuous_on UNIV (λ(x::'c,y). x+y)
  assumes (λ(x, y). f x y) summable_on (A × B)
  assumes a. aA  (f a) summable_on B
  assumes b. bB  (λa. f a b) summable_on A
  shows infsum (λx. infsum (λy. f x y) B) A = infsum (λy. infsum (λx. f x y) A) B
proof -
  have "(λ(x, y). f y x)  prod.swap summable_on A × B"
    by (simp add: assms(2) summable_on_cong)
  then have fyx: (λ(x, y). f y x) summable_on (B × A)
    by (metis has_sum_reindex infsum_reindex inj_swap product_swap summable_iff_has_sum_infsum)
  have infsum (λx. infsum (λy. f x y) B) A = infsum (λ(x,y). f x y) (A × B)
    using assms infsum_Sigma' by blast
  also have  = infsum (λ(x,y). f y x) (B × A)
    apply (subst product_swap[symmetric])
    apply (subst infsum_reindex)
    using assms by (auto simp: o_def)
  also have  = infsum (λy. infsum (λx. f x y) A) B
    by (smt (verit) fyx assms(1) assms(4) infsum_Sigma' infsum_cong)
  finally show ?thesis .
qed

lemma infsum_swap_banach:
  fixes A :: "'a set" and B :: "'b set"
  fixes f :: "'a  'b  'c::banach"
  assumes (λ(x, y). f x y) summable_on (A × B)
  shows "infsum (λx. infsum (λy. f x y) B) A = infsum (λy. infsum (λx. f x y) A) B"
proof -
  have §: (λ(x, y). f y x) summable_on (B × A)
    by (metis (mono_tags, lifting) assms case_swap inj_swap o_apply product_swap summable_on_cong summable_on_reindex)
  have infsum (λx. infsum (λy. f x y) B) A = infsum (λ(x,y). f x y) (A × B)
    using assms infsum_Sigma'_banach by blast
  also have  = infsum (λ(x,y). f y x) (B × A)
    apply (subst product_swap[symmetric])
    apply (subst infsum_reindex)
    using assms by (auto simp: o_def)
  also have  = infsum (λy. infsum (λx. f x y) A) B
    by (metis (mono_tags, lifting) § infsum_Sigma'_banach infsum_cong)
  finally show ?thesis .
qed

lemma nonneg_infsum_le_0D:
  fixes f :: "'a  'b::{topological_ab_group_add,ordered_ab_group_add,linorder_topology}"
  assumes "infsum f A  0"
    and abs_sum: "f summable_on A"
    and nneg: "x. x  A  f x  0"
    and "x  A"
  shows "f x = 0"
proof (rule ccontr)
  assume f x  0
  have ex: f summable_on (A-{x})
    by (rule summable_on_cofin_subset) (use assms in auto)
  have pos: infsum f (A - {x})  0
    by (rule infsum_nonneg) (use nneg in auto)

  have [trans]: x  y  y > z  x > z for x y z :: 'b by auto

  have infsum f A = infsum f (A-{x}) + infsum f {x}
    by (subst infsum_Un_disjoint[symmetric]) (use assms ex in auto simp: insert_absorb)
  also have   infsum f {x} (is _  )
    using pos by (rule add_increasing) simp
  also have  = f x (is _ = )
    by (subst infsum_finite) auto
  also have  > 0
    using f x  0 assms(4) nneg by fastforce
  finally show False
    using assms by auto
qed

lemma nonneg_has_sum_le_0D:
  fixes f :: "'a  'b::{topological_ab_group_add,ordered_ab_group_add,linorder_topology}"
  assumes "(f has_sum a) A" a  0
    and "x. x  A  f x  0"
    and "x  A"
  shows "f x = 0"
  by (metis assms infsumI nonneg_infsum_le_0D summable_on_def)

lemma has_sum_cmult_left:
  fixes f :: "'a  'b :: {topological_semigroup_mult, semiring_0}"
  assumes (f has_sum a) A
  shows "((λx. f x * c) has_sum (a * c)) A"
  using assms tendsto_mult_right 
  by (force simp add: has_sum_def sum_distrib_right)

lemma infsum_cmult_left:
  fixes f :: "'a  'b :: {t2_space, topological_semigroup_mult, semiring_0}"
  assumes c  0  f summable_on A
  shows "infsum (λx. f x * c) A = infsum f A * c"
  using assms has_sum_cmult_left infsumI summable_iff_has_sum_infsum by fastforce

lemma summable_on_cmult_left:
  fixes f :: "'a  'b :: {t2_space, topological_semigroup_mult, semiring_0}"
  assumes f summable_on A
  shows "(λx. f x * c) summable_on A"
  using assms summable_on_def has_sum_cmult_left by blast

lemma has_sum_cmult_right:
  fixes f :: "'a  'b :: {topological_semigroup_mult, semiring_0}"
  assumes (f has_sum a) A
  shows "((λx. c * f x) has_sum (c * a)) A"
  using assms tendsto_mult_left 
  by (force simp add: has_sum_def sum_distrib_left)

lemma infsum_cmult_right:
  fixes f :: "'a  'b :: {t2_space, topological_semigroup_mult, semiring_0}"
  assumes c  0  f summable_on A
  shows infsum (λx. c * f x) A = c * infsum f A
  using assms has_sum_cmult_right infsumI summable_iff_has_sum_infsum by fastforce

lemma summable_on_cmult_right:
  fixes f :: "'a  'b :: {t2_space, topological_semigroup_mult, semiring_0}"
  assumes f summable_on A
  shows "(λx. c * f x) summable_on A"
  using assms summable_on_def has_sum_cmult_right by blast

lemma summable_on_cmult_left':
  fixes f :: "'a  'b :: {t2_space, topological_semigroup_mult, division_ring}"
  assumes c  0
  shows "(λx. f x * c) summable_on A  f summable_on A"
proof
  assume f summable_on A
  then show (λx. f x * c) summable_on A
    by (rule summable_on_cmult_left)
next
  assume (λx. f x * c) summable_on A
  then have (λx. f x * c * inverse c) summable_on A
    by (rule summable_on_cmult_left)
  then show f summable_on A
    by (smt (verit, del_insts) assms divide_inverse nonzero_divide_eq_eq summable_on_cong)
qed

lemma summable_on_cmult_right':
  fixes f :: "'a  'b :: {t2_space, topological_semigroup_mult, division_ring}"
  assumes c  0
  shows "(λx. c * f x) summable_on A  f summable_on A"
    by (metis (no_types, lifting) assms left_inverse mult.assoc mult_1 summable_on_cmult_right summable_on_cong)

lemma infsum_cmult_left':
  fixes f :: "'a  'b :: {t2_space, topological_semigroup_mult, division_ring}"
  shows "infsum (λx. f x * c) A = infsum f A * c"
  by (metis (full_types) infsum_cmult_left infsum_not_exists mult_eq_0_iff summable_on_cmult_left')

lemma infsum_cmult_right':
  fixes f :: "'a  'b :: {t2_space,topological_semigroup_mult,division_ring}"
  shows "infsum (λx. c * f x) A = c * infsum f A"
  by (metis (full_types) infsum_cmult_right infsum_not_exists mult_eq_0_iff summable_on_cmult_right')

lemma has_sum_constant[simp]:
  assumes finite F
  shows ((λ_. c) has_sum of_nat (card F) * c) F
  by (metis assms has_sum_finite sum_constant)

lemma infsum_constant[simp]:
  assumes finite F
  shows infsum (λ_. c) F = of_nat (card F) * c
  by (simp add: assms)

lemma infsum_diverge_constant:
  ― ‹This probably does not really need all of classarchimedean_field but Isabelle/HOL
       has no type class such as, e.g., "archimedean ring".›
  fixes c :: 'a::{archimedean_field, comm_monoid_add, linorder_topology, topological_semigroup_mult}
  assumes infinite A and c  0
  shows ¬ (λ_. c) summable_on A
proof (rule notI)
  assume (λ_. c) summable_on A
  then have (λ_. inverse c * c) summable_on A
    by (rule summable_on_cmult_right)
  then have [simp]: (λ_. 1::'a) summable_on A
    using assms by auto
  have infsum (λ_. 1) A  d for d :: 'a
  proof -
    obtain n :: nat where of_nat n  d
      by (meson real_arch_simple)
    from assms
    obtain F where F  A and finite F and card F = n
      by (meson infinite_arbitrarily_large)
    note d  of_nat n
    also have of_nat n = infsum (λ_. 1::'a) F
      by (simp add: card F = n finite F)
    also have   infsum (λ_. 1::'a) A
      apply (rule infsum_mono_neutral)
      using finite F F  A by auto
    finally show ?thesis .
  qed                                                        
  then show False
    by (meson linordered_field_no_ub not_less)
qed

lemma has_sum_constant_archimedean[simp]:
  ― ‹This probably does not really need all of classarchimedean_field but Isabelle/HOL
       has no type class such as, e.g., "archimedean ring".›
  fixes c :: 'a::{archimedean_field, comm_monoid_add, linorder_topology, topological_semigroup_mult}
  shows infsum (λ_. c) A = of_nat (card A) * c
  by (metis infsum_0 infsum_constant infsum_diverge_constant infsum_not_exists sum.infinite sum_constant)

lemma has_sum_uminus:
  fixes f :: 'a  'b::topological_ab_group_add
  shows ((λx. - f x) has_sum a) A  (f has_sum (- a)) A
  by (auto simp add: sum_negf[abs_def] tendsto_minus_cancel_left has_sum_def)

lemma summable_on_uminus:
  fixes f :: 'a  'b::topological_ab_group_add
  shows(λx. - f x) summable_on A  f summable_on A
  by (metis summable_on_def has_sum_uminus verit_minus_simplify(4))

lemma infsum_uminus:
  fixes f :: 'a  'b::{topological_ab_group_add, t2_space}
  shows infsum (λx. - f x) A = - infsum f A
  by (metis (full_types) add.inverse_inverse add.inverse_neutral infsumI infsum_def has_sum_infsum has_sum_uminus)

lemma has_sum_le_finite_sums:
  fixes a :: 'a::{comm_monoid_add,topological_space,linorder_topology}
  assumes (f has_sum a) A
  assumes F. finite F  F  A  sum f F  b
  shows a  b
  by (metis assms eventually_finite_subsets_at_top_weakI finite_subsets_at_top_neq_bot has_sum_def tendsto_upperbound)

lemma infsum_le_finite_sums:
  fixes b :: 'a::{comm_monoid_add,topological_space,linorder_topology}
  assumes f summable_on A
  assumes F. finite F  F  A  sum f F  b
  shows infsum f A  b
  by (meson assms has_sum_infsum has_sum_le_finite_sums)


lemma summable_on_scaleR_left [intro]:
  fixes c :: 'a :: real_normed_vector
  assumes "c  0  f summable_on A"
  shows   "(λx. f x *R c) summable_on A"
proof (cases c = 0)
  case False
  then have "(λy. y *R c)  f summable_on A"
    using assms by (auto simp add: scaleR_left.additive_axioms summable_on_comm_additive)
  then show ?thesis
    by (metis (mono_tags, lifting) comp_apply summable_on_cong)
qed auto


lemma summable_on_scaleR_right [intro]:
  fixes f :: 'a  'b :: real_normed_vector
  assumes "c  0  f summable_on A"
  shows   "(λx. c *R f x) summable_on A"
proof (cases c = 0)
  case False
  then have "(*R) c  f summable_on A"
  using assms by (auto simp add: scaleR_right.additive_axioms summable_on_comm_additive)
  then show ?thesis
    by (metis (mono_tags, lifting) comp_apply summable_on_cong)
qed auto

lemma infsum_scaleR_left:
  fixes c :: 'a :: real_normed_vector
  assumes "c  0  f summable_on A"
  shows   "infsum (λx. f x *R c) A = infsum f A *R c"
proof (cases c = 0)
  case False
  then have "infsum ((λy. y *R c)  f) A = infsum f A *R c"
  using assms by (auto simp add: scaleR_left.additive_axioms infsum_comm_additive)
  then show ?thesis
    by (metis (mono_tags, lifting) comp_apply infsum_cong)
qed auto

lemma infsum_scaleR_right:
  fixes f :: 'a  'b :: real_normed_vector
  shows   "infsum (λx. c *R f x) A = c *R infsum f A"
proof -
  consider (summable) f summable_on A | (c0) c = 0 | (not_summable) ¬ f summable_on A c  0
    by auto
  then show ?thesis
  proof cases
    case summable
    then have "infsum ((*R) c  f) A = c *R infsum f A"
      by (auto simp add: scaleR_right.additive_axioms infsum_comm_additive)
    then show ?thesis
      by (metis (mono_tags, lifting) comp_apply infsum_cong)
  next
    case c0
    then show ?thesis by auto
  next
    case not_summable
    have ¬ (λx. c *R f x) summable_on A
    proof (rule notI)
      assume (λx. c *R f x) summable_on A
      then have (λx. inverse c *R c *R f x) summable_on A
        using summable_on_scaleR_right by blast
      with not_summable show False
        by simp
    qed
    then show ?thesis
      by (simp add: infsum_not_exists not_summable(1)) 
  qed
qed


lemma infsum_Un_Int:
  fixes f :: "'a  'b::{topological_ab_group_add, t2_space}"
  assumes "f summable_on A - B" "f summable_on B - A" f summable_on A  B
  shows   "infsum f (A  B) = infsum f A + infsum f B - infsum f (A  B)"
proof -
  obtain f summable_on A f summable_on B
    using assms by (metis Int_Diff_Un Int_Diff_disjoint inf_commute summable_on_Un_disjoint)
  then have infsum f (A  B) = infsum f A + infsum f (B - A)
    using assms(2) infsum_Un_disjoint by fastforce
  moreover have infsum f (B - A) = infsum f B - infsum f (A  B)
    using assms by (metis Diff_Int2 Un_Int_eq(2) f summable_on B inf_le2 infsum_Diff)
  ultimately show ?thesis
    by auto
qed

lemma inj_combinator':
  assumes "x  F"
  shows inj_on (λ(g, y). g(x := y)) (PiE F B × B x)
proof -
  have "inj_on ((λ(y, g). g(x := y))  prod.swap) (PiE F B × B x)"
    using inj_combinator[of x F B] assms by (intro comp_inj_on) (auto simp: product_swap)
  thus ?thesis
    by (simp add: o_def)
qed

lemma infsum_prod_PiE:
  ― ‹See also infsum_prod_PiE_abs› below with incomparable premises.›
  fixes f :: "'a  'b  'c :: {comm_monoid_mult, topological_semigroup_mult, division_ring, banach}"
  assumes finite: "finite A"
  assumes "x. x  A  f x summable_on B x"
  assumes "(λg. xA. f x (g x)) summable_on (PiE A B)"
  shows   "infsum (λg. xA. f x (g x)) (PiE A B) = (xA. infsum (f x) (B x))"
proof (use finite assms(2-) in induction)
  case empty
  then show ?case 
    by auto
next
  case (insert x F)
  have pi: PiE (insert x F) B = (λ(g,y). g(x:=y)) ` (PiE F B × B x)
    unfolding PiE_insert_eq 
    by (subst swap_product [symmetric]) (simp add: image_image case_prod_unfold)
  have prod: (x'F. f x' ((p(x:=y)) x')) = (x'F. f x' (p x')) for p y
    by (rule prod.cong) (use insert.hyps in auto)
  have inj: inj_on (λ(g, y). g(x := y)) (PiE F B × B x)
    using x  F by (rule inj_combinator')

  have summable1: (λg. xinsert x F. f x (g x)) summable_on PiE (insert x F) B
    using insert.prems(2) .
  also have PiE (insert x F) B = (λ(g,y). g(x:=y)) ` (PiE F B × B x)
    by (simp only: pi)
  also have "(λg. xinsert x F. f x (g x)) summable_on  
               ((λg. xinsert x F. f x (g x))  (λ(g,y). g(x:=y))) summable_on (PiE F B × B x)"
    using inj by (rule summable_on_reindex)
  also have "(zF. f z ((g(x := y)) z)) = (zF. f z (g z))" for g y
    using insert.hyps by (intro prod.cong) auto
  hence "((λg. xinsert x F. f x (g x))  (λ(g,y). g(x:=y))) =
             (λ(p, y). f x y * (x'F. f x' (p x')))"
    using insert.hyps by (auto simp: fun_eq_iff cong: prod.cong_simp)
  finally have summable2: (λ(p, y). f x y * (x'F. f x' (p x'))) summable_on PiE F B × B x .

  then have (λp. yB x. f x y * (x'F. f x' (p x'))) summable_on PiE F B
    by (rule summable_on_Sigma_banach)
  then have (λp. (yB x. f x y) * (x'F. f x' (p x'))) summable_on PiE F B
    by (metis (mono_tags, lifting) infsum_cmult_left' infsum_cong summable_on_cong)
  then have summable3: (λp. (x'F. f x' (p x'))) summable_on PiE F B if (yB x. f x y)  0
    using summable_on_cmult_right' that by blast

  have (gPiE (insert x F) B. xinsert x F. f x (g x))
     = ((p,y)PiE F B × B x. x'insert x F. f x' ((p(x:=y)) x'))
    by (smt (verit, ccfv_SIG) comp_apply infsum_cong infsum_reindex inj pi prod.cong split_def)
  also have  = ((p, y)PiE F B × B x. f x y * (x'F. f x' ((p(x:=y)) x')))
    using insert.hyps by auto
  also have  = ((p, y)PiE F B × B x. f x y * (x'F. f x' (p x')))
    using prod by presburger
  also have  = (pPiE F B. yB x. f x y * (x'F. f x' (p x')))
    using infsum_Sigma'_banach summable2 by force
  also have  = (yB x. f x y) * (pPiE F B. x'F. f x' (p x'))
    by (smt (verit) infsum_cmult_left' infsum_cmult_right' infsum_cong)
  also have  = (xinsert x F. infsum (f x) (B x))
    using insert summable3 by auto
  finally show ?case
    by simp
qed

lemma infsum_prod_PiE_abs:
  ― ‹See also @{thm [source] infsum_prod_PiE} above with incomparable premises.›
  fixes f :: "'a  'b  'c :: {banach, real_normed_div_algebra, comm_semiring_1}"
  assumes finite: "finite A"
  assumes "x. x  A  f x abs_summable_on B x"
  shows   "infsum (λg. xA. f x (g x)) (PiE A B) = (xA. infsum (f x) (B x))"
proof (use finite assms(2) in induction)
  case empty
  then show ?case 
    by auto
next
  case (insert x A)
  
  have pi: PiE (insert x F) B = (λ(g,y). g(x:=y)) ` (PiE F B × B x) for x F and B :: "'a  'b set"
    unfolding PiE_insert_eq 
    by (subst swap_product [symmetric]) (simp add: image_image case_prod_unfold)
  have prod: (x'A. f x' ((p(x:=y)) x')) = (x'A. f x' (p x')) for p y
    by (rule prod.cong) (use insert.hyps in auto)
  have inj: inj_on (λ(g, y). g(x := y)) (PiE A B × B x)
    using x  A by (rule inj_combinator')

  define s where s x = infsum (λy. norm (f x y)) (B x) for x

  have (pP. norm (xF. f x (p x)))  prod s F 
    if P: P  PiE F B and [simp]: finite P finite F 
      and sum: x. x  F  f x abs_summable_on B x for P F
  proof -
    define B' where B' x = {p x| p. pP} for x
    have fin_B'[simp]: finite (B' x) for x
      using that by (auto simp: B'_def)
    have [simp]: finite (PiE F B')
      by (simp add: finite_PiE)
    have [simp]: P  PiE F B'
      using that by (auto simp: B'_def)
    have B'B: B' x  B x if x  F for x
      unfolding B'_def using P that 
      by auto
    have s_bound: (yB' x. norm (f x y))  s x if x  F for x
      by (metis B'B fin_B' finite_sum_le_has_sum has_sum_infsum norm_ge_zero s_def sum that)
    have (pP. norm (xF. f x (p x)))  (pPiE F B'. norm (xF. f x (p x)))
      by (simp add: sum_mono2)
    also have  = (pPiE F B'. xF. norm (f x (p x)))
      by (simp add: prod_norm)
    also have  = (xF. yB' x. norm (f x y))
    proof (use finite F in induction)
      case empty
      then show ?case by simp
    next
      case (insert x F)
      have inj: inj_on (λ(g, y). g(x := y)) (PiE F B' × B' x)
        by (simp add: inj_combinator' insert.hyps)
      then have (pPiE (insert x F) B'. xinsert x F. norm (f x (p x)))
         =  ((p,y)PiE F B' × B' x. x'insert x F. norm (f x' ((p(x := y)) x')))
        by (simp add: pi sum.reindex case_prod_unfold)
      also have  = ((p, y)PiE F B' × B' x. norm (f x y) * (x'F. norm (f x' (p x'))))
        by (smt (verit, del_insts) fun_upd_apply insert.hyps prod.cong prod.insert split_def sum.cong)
      also have  = (yB' x. norm (f x y)) * (pPiE F B'. x'F. norm (f x' (p x')))
        by (simp add: sum_product sum.swap [of _ "PiE F B'"] sum.cartesian_product)
      also have  = (xinsert x F. yB' x. norm (f x y))
        using insert by force
      finally show ?case .
    qed
    also have   (xF. s x)
      using s_bound by (simp add: prod_mono sum_nonneg)
    finally show ?thesis .
  qed
  then have "bdd_above
     (sum (λg. norm (xinsert x A. f x (g x))) ` {F. F  PiE (insert x A) B  finite F})"
    using insert.hyps insert.prems by (intro bdd_aboveI) blast
  then have (λg. xinsert x A. f x (g x)) abs_summable_on PiE (insert x A) B
    using nonneg_bdd_above_summable_on
    by (metis (mono_tags, lifting) Collect_cong norm_ge_zero)
  also have PiE (insert x A) B = (λ(g,y). g(x:=y)) ` (PiE A B × B x)
    by (simp only: pi)
  also have "(λg. xinsert x A. f x (g x)) abs_summable_on  
               ((λg. xinsert x A. f x (g x))  (λ(g,y). g(x:=y))) abs_summable_on (PiE A B × B x)"
    using inj by (subst summable_on_reindex) (auto simp: o_def)
  also have "(zA. f z ((g(x := y)) z)) = (zA. f z (g z))" for g y
    using insert.hyps by (intro prod.cong) auto
  hence "((λg. xinsert x A. f x (g x))  (λ(g,y). g(x:=y))) =
             (λ(p, y). f x y * (x'A. f x' (p x')))"
    using insert.hyps by (auto simp: fun_eq_iff cong: prod.cong_simp)
  finally have summable2: (λ(p, y). f x y * (x'A. f x' (p x'))) abs_summable_on PiE A B × B x .

  have (gPiE (insert x A) B. xinsert x A. f x (g x))
     = ((p,y)PiE A B × B x. x'insert x A. f x' ((p(x:=y)) x'))
    using inj by (simp add: pi infsum_reindex o_def case_prod_unfold)
  also have  = ((p,y)  PiE A B × B x. f x y * (x'A. f x' (p x')))
    using prod insert.hyps by auto
  also have  = (pPiE A B. yB x. f x y * (x'A. f x' (p x')))
    using abs_summable_summable infsum_Sigma'_banach summable2 by fastforce
  also have  = (yB x. f x y) * (pPiE A B. x'A. f x' (p x'))
    by (smt (verit, best) infsum_cmult_left' infsum_cmult_right' infsum_cong)
  finally show ?case
    by (simp add: insert)
qed



subsection ‹Absolute convergence›

lemma abs_summable_countable:
  assumes f abs_summable_on A
  shows countable {xA. f x  0}
proof -
  have fin: finite {xA. norm (f x)  t} if t > 0 for t
  proof (rule ccontr)
    assume *: infinite {x  A. t  norm (f x)}
    have infsum (λx. norm (f x)) A  b for b
    proof -
      obtain b' where b': of_nat b'  b / t
        by (meson real_arch_simple)
      from *
      obtain F where cardF: card F  b' and finite F and F: F  {x  A. t  norm (f x)}
        by (meson finite_if_finite_subsets_card_bdd nle_le)
      have b  of_nat b' * t
        using b' t > 0 by (simp add: field_simps split: if_splits)
      also have   of_nat (card F) * t
        by (simp add: cardF that)
      also have  = sum (λx. t) F
        by simp
      also have   sum (λx. norm (f x)) F
        by (metis (mono_tags, lifting) F in_mono mem_Collect_eq sum_mono)
      also have  = infsum (λx. norm (f x)) F
        using finite F by (rule infsum_finite[symmetric])
      also have   infsum (λx. norm (f x)) A
        by (rule infsum_mono_neutral) (use finite F assms F in auto)
      finally show ?thesis .
    qed
    then show False
      by (meson gt_ex linorder_not_less)
  qed
  have countable (i{1..}. {xA. norm (f x)  1/of_nat i})
    by (rule countable_UN) (use fin in auto intro!: countable_finite)
  also have  = {xA. f x  0}
  proof safe
    fix x assume x: "x  A" "f x  0"
    define i where "i = max 1 (nat (ceiling (1 / norm (f x))))"
    have "i  1"
      by (simp add: i_def)
    moreover have "real i  1 / norm (f x)"
      unfolding i_def by linarith
    hence "1 / real i  norm (f x)" using f x  0
      by (auto simp: divide_simps mult_ac)
    ultimately show "x  (i{1..}. {x  A. 1 / real i  norm (f x)})"
      using x  A by auto
  qed auto
  finally show ?thesis .
qed

(* Logically belongs in the section about reals, but needed as a dependency here *)
lemma summable_on_iff_abs_summable_on_real:
  fixes f :: 'a  real
  shows f summable_on A  f abs_summable_on A
proof (rule iffI)
  assume f summable_on A
  define n Ap An
    where n  λx. norm (f x) and Ap = {xA. f x  0} and An = {xA. f x < 0} for x
  have A: Ap  An = A Ap  An = {}
    by (auto simp: Ap_def An_def)
  from f summable_on A have f summable_on Ap f summable_on An
    using Ap_def An_def summable_on_subset_banach by fastforce+
  then have n summable_on Ap
    by (smt (verit) Ap_def n_def mem_Collect_eq real_norm_def summable_on_cong)
  moreover have n summable_on An
    by (smt (verit, best) f summable_on An  summable_on_uminus An_def n_def summable_on_cong mem_Collect_eq real_norm_def)
  ultimately show n summable_on A
    using A summable_on_Un_disjoint by blast
next
  show f abs_summable_on A  f summable_on A
    using abs_summable_summable by blast
qed

lemma abs_summable_on_Sigma_iff:
  shows   "f abs_summable_on Sigma A B 
             (xA. (λy. f (x, y)) abs_summable_on B x) 
             ((λx. infsum (λy. norm (f (x, y))) (B x)) abs_summable_on A)"
proof (intro iffI conjI ballI)
  assume asm: f abs_summable_on Sigma A B
  then have (λx. infsum (λy. norm (f (x,y))) (B x)) summable_on A
    by (simp add: cond_case_prod_eta summable_on_Sigma_banach)
  then show (λx. yB x. norm (f (x, y))) abs_summable_on A
    using summable_on_iff_abs_summable_on_real by force

  show (λy. f (x, y)) abs_summable_on B x if x  A for x
  proof -
    from asm have f abs_summable_on Pair x ` B x
      by (simp add: image_subset_iff summable_on_subset_banach that)
    then show ?thesis
      by (metis (mono_tags, lifting) o_def inj_on_def summable_on_reindex prod.inject summable_on_cong)
  qed
next
  assume asm: (xA. (λxa. f (x, xa)) abs_summable_on B x) 
    (λx. yB x. norm (f (x, y))) abs_summable_on A
  have (xyF. norm (f xy))  (xA. yB x. norm (f (x, y)))
    if F  Sigma A B and [simp]: finite F for F
  proof -
    have [simp]: (SIGMA x:fst ` F. {y. (x, y)  F}) = F
      by (auto intro!: set_eqI simp add: Domain.DomainI fst_eq_Domain)
    have [simp]: finite {y. (x, y)  F} for x
      by (metis finite F Range.intros finite_Range finite_subset mem_Collect_eq subsetI)
    have (xyF. norm (f xy)) = (xfst ` F. y{y. (x,y)F}. norm (f (x,y)))
      by (simp add: sum.Sigma)
    also have  = (xfst ` F. y{y. (x,y)F}. norm (f (x,y)))
      by auto
    also have   (xfst ` F. yB x. norm (f (x,y)))
      using asm that(1) by (intro infsum_mono infsum_mono_neutral) auto
    also have   (xA. yB x. norm (f (x,y)))
      by (rule infsum_mono_neutral) (use asm that(1) in auto simp add: infsum_nonneg)
    finally show ?thesis .
  qed
  then show f abs_summable_on Sigma A B
    by (intro nonneg_bdd_above_summable_on) (auto simp: bdd_above_def)
qed

lemma abs_summable_on_comparison_test:
  assumes "g abs_summable_on A"
  assumes "x. x  A  norm (f x)  norm (g x)"
  shows   "f abs_summable_on A"
proof (rule nonneg_bdd_above_summable_on)
  show "bdd_above (sum (λx. norm (f x)) ` {F. F  A  finite F})"
  proof (rule bdd_aboveI2)
    fix F assume F: "F  {F. F  A  finite F}"
    have sum (λx. norm (f x)) F  sum (λx. norm (g x)) F
      using assms F by (intro sum_mono) auto
    also have  = infsum (λx. norm (g x)) F
      using F by simp
    also have   infsum (λx. norm (g x)) A
      by (smt (verit) F assms(1) infsum_mono2 mem_Collect_eq norm_ge_zero summable_on_subset_banach)
    finally show "(xF. norm (f x))  (xA. norm (g x))" .
  qed
qed auto

lemma abs_summable_iff_bdd_above:
  fixes f :: 'a  'b::real_normed_vector
  shows f abs_summable_on A  bdd_above (sum (λx. norm (f x)) ` {F. FA  finite F})
proof (rule iffI)
  assume f abs_summable_on A
  show bdd_above (sum (λx. norm (f x)) ` {F. F  A  finite F})
  proof (rule bdd_aboveI2)
    fix F assume F: "F  {F. F  A  finite F}"
    show "(xF. norm (f x))  (xA. norm (f x))"
      by (rule finite_sum_le_infsum) (use f abs_summable_on A F in auto)
  qed
next
  assume bdd_above (sum (λx. norm (f x)) ` {F. FA  finite F})
  then show f abs_summable_on A
    by (simp add: nonneg_bdd_above_summable_on)
qed

lemma abs_summable_product:
  fixes x :: "'a  'b::{real_normed_div_algebra,banach,second_countable_topology}"
  assumes x2_sum: "(λi. (x i) * (x i)) abs_summable_on A"
    and y2_sum: "(λi. (y i) * (y i)) abs_summable_on A"
  shows "(λi. x i * y i) abs_summable_on A"
proof (rule nonneg_bdd_above_summable_on)
  show "bdd_above (sum (λxa. norm (x xa * y xa)) ` {F. F  A  finite F})"
  proof (rule bdd_aboveI2)
    fix F assume F: F  {F. F  A  finite F}
    then have r1: "finite F" and b4: "F  A"
      by auto
  
    have a1: "(iF. norm (x i * x i))  (iA. norm (x i * x i))"
      by (metis (no_types, lifting) b4 infsum_mono2 norm_ge_zero summable_on_subset_banach x2_sum)

    have "norm (x i * y i)  norm (x i * x i) + norm (y i * y i)" for i
      unfolding norm_mult by (smt mult_left_mono mult_nonneg_nonneg mult_right_mono norm_ge_zero)
    hence "(iF. norm (x i * y i))  (iF. norm (x i * x i) + norm (y i * y i))"
      by (simp add: sum_mono)
    also have " = (iF. norm (x i * x i)) + (iF. norm (y i * y i))"
      by (simp add: sum.distrib)
    also have " = (iF. norm (x i * x i)) + (iF. norm (y i * y i))"
      by (simp add: finite F)
    also have "  (iA. norm (x i * x i)) + (iA. norm (y i * y i))"
      using F assms
      by (intro add_mono infsum_mono2) auto
    finally show (xaF. norm (x xa * y xa))  (iA. norm (x i * x i)) + (iA. norm (y i * y i))
      by simp
  qed
qed auto

subsection ‹Extended reals and nats›

lemma summable_on_ennreal[simp]: (f::_  ennreal) summable_on S and summable_on_enat[simp]: (f::_  enat) summable_on S
  by (simp_all add: nonneg_summable_on_complete)

lemma has_sum_superconst_infinite_ennreal:
  fixes f :: 'a  ennreal
  assumes geqb: x. x  S  f x  b
  assumes b: b > 0
  assumes infinite S
  shows "(f has_sum ) S"
proof -
  have (sum f  ) (finite_subsets_at_top S)
  proof (rule order_tendstoI)
    fix y :: ennreal assume y < 
    then have y / b <  y < top
      using b ennreal_divide_eq_top_iff top.not_eq_extremum by force+
    then obtain F where finite F and F  S and cardF: card F > y / b
      using infinite S
      by (metis ennreal_Ex_less_of_nat infinite_arbitrarily_large infinity_ennreal_def)
    moreover have sum f Y > y if finite Y and F  Y and Y  S for Y
    proof -
      have y < b * card F
        by (metis b y < top cardF divide_less_ennreal ennreal_mult_eq_top_iff gr_implies_not_zero mult.commute top.not_eq_extremum)
      also have   b * card Y
        by (meson b card_mono less_imp_le mult_left_mono of_nat_le_iff that)
      also have  = sum (λ_. b) Y
        by (simp add: mult.commute)
      also have   sum f Y
        using geqb by (meson subset_eq sum_mono that(3))
      finally show ?thesis .
    qed
    ultimately show F x in finite_subsets_at_top S. y < sum f x
      unfolding eventually_finite_subsets_at_top by auto
  qed auto
  then show ?thesis
    by (simp add: has_sum_def)
qed

lemma infsum_superconst_infinite_ennreal:
  fixes f :: 'a  ennreal
  assumes x. x  S  f x  b
  assumes b > 0
  assumes infinite S
  shows "infsum f S = "
  using assms infsumI has_sum_superconst_infinite_ennreal by blast

lemma infsum_superconst_infinite_ereal:
  fixes f :: 'a  ereal
  assumes geqb: x. x  S  f x  b
  assumes b: b > 0
  assumes infinite S
  shows "infsum f S = "
proof -
  obtain b' where b': e2ennreal b' = b and b' > 0
    using b by blast
  have "0 < e2ennreal b"
    using b' b
    by (metis dual_order.refl enn2ereal_e2ennreal gr_zeroI order_less_le zero_ennreal.abs_eq)
  hence *: infsum (e2ennreal  f) S = 
    using assms b'
    by (intro infsum_superconst_infinite_ennreal[where b=b']) (auto intro!: e2ennreal_mono)
  have infsum f S = infsum (enn2ereal  (e2ennreal  f)) S
    using geqb b by (intro infsum_cong) (fastforce simp: enn2ereal_e2ennreal)
  also have  = enn2ereal 
    using * by (simp add: infsum_comm_additive_general continuous_at_enn2ereal nonneg_summable_on_complete)
  also have  = 
    by simp
  finally show ?thesis .
qed

lemma has_sum_superconst_infinite_ereal:
  fixes f :: 'a  ereal
  assumes x. x  S  f x  b
  assumes b > 0
  assumes infinite S
  shows "(f has_sum ) S"
  by (metis Infty_neq_0(1) assms infsum_def has_sum_infsum infsum_superconst_infinite_ereal)

lemma infsum_superconst_infinite_enat:
  fixes f :: 'a  enat
  assumes geqb: x. x  S  f x  b
  assumes b: b > 0
  assumes infinite S
  shows "infsum f S = "
proof -
  have ennreal_of_enat (infsum f S) = infsum (ennreal_of_enat  f) S
    by (simp flip: infsum_comm_additive_general)
  also have  = 
    by (metis assms(3) b comp_def ennreal_of_enat_0 ennreal_of_enat_le_iff geqb infsum_superconst_infinite_ennreal leD leI)
  also have  = ennreal_of_enat 
    by simp
  finally show ?thesis
    by (rule ennreal_of_enat_inj[THEN iffD1])
qed

lemma has_sum_superconst_infinite_enat:
  fixes f :: 'a  enat
  assumes x. x  S  f x  b
  assumes b > 0
  assumes infinite S
  shows "(f has_sum ) S"
  by (metis assms i0_lb has_sum_infsum infsum_superconst_infinite_enat nonneg_summable_on_complete)

text ‹This lemma helps to relate a real-valued infsum to a supremum over extended nonnegative reals.›

lemma infsum_nonneg_is_SUPREMUM_ennreal:
  fixes f :: "'a  real"
  assumes summable: "f summable_on A"
    and fnn: "x. xA  f x  0"
  shows "ennreal (infsum f A) = (SUP F{F. finite F  F  A}. (ennreal (sum f F)))"
proof -
  have §: "F. finite F; F  A  sum (ennreal  f) F = ennreal (sum f F)"
    by (metis (mono_tags, lifting) comp_def fnn subsetD sum.cong sum_ennreal)
  then have ennreal (infsum f A) = infsum (ennreal  f) A
    by (simp add: infsum_comm_additive_general local.summable)
  also have  = (SUP F{F. finite F  F  A}. (ennreal (sum f F)))
    by (metis (mono_tags, lifting) § image_cong mem_Collect_eq nonneg_infsum_complete zero_le)
  finally show ?thesis .
qed

text ‹This lemma helps to related a real-valued infsum to a supremum over extended reals.›

lemma infsum_nonneg_is_SUPREMUM_ereal:
  fixes f :: "'a  real"
  assumes summable: "f summable_on A"
    and fnn: "x. xA  f x  0"
  shows "ereal (infsum f A) = (SUP F{F. finite F  F  A}. (ereal (sum f F)))"
proof -
  have "F. finite F; F  A  sum (ereal  f) F = ereal (sum f F)"
    by auto
  then have ereal (infsum f A) = infsum (ereal  f) A
    by (simp add: infsum_comm_additive_general local.summable)
  also have  = (SUP F{F. finite F  F  A}. (ereal (sum f F)))
    by (subst nonneg_infsum_complete) (simp_all add: assms)
  finally show ?thesis .
qed


subsection ‹Real numbers›

text ‹Most lemmas in the general property section already apply to real numbers.
      A few ones that are specific to reals are given here.›

lemma infsum_nonneg_is_SUPREMUM_real:
  fixes f :: "'a  real"
  assumes summable: "f summable_on A"
    and fnn: "x. xA  f x  0"
  shows "infsum f A = (SUP F{F. finite F  F  A}. (sum f F))"
proof -
  have *: "ereal (infsum f A) = (SUP F{F. finite F  F  A}. (ereal (sum f F)))"
    using assms by (rule infsum_nonneg_is_SUPREMUM_ereal)
  also have " = ereal (SUP F{F. finite F  F  A}. (sum f F))"
    by (metis (no_types, lifting) * MInfty_neq_ereal(2) PInfty_neq_ereal(2) SUP_cong abs_eq_infinity_cases ereal_SUP)
  finally show ?thesis by simp
qed


lemma has_sum_nonneg_SUPREMUM_real:
  fixes f :: "'a  real"
  assumes "f summable_on A" and "x. xA  f x  0"
  shows "(f has_sum (SUP F{F. finite F  F  A}. (sum f F))) A"
  by (metis (mono_tags, lifting) assms has_sum_infsum infsum_nonneg_is_SUPREMUM_real)

lemma summable_countable_real:
  fixes f :: 'a  real
  assumes f summable_on A
  shows countable {xA. f x  0}
  using abs_summable_countable assms summable_on_iff_abs_summable_on_real by blast

subsection ‹Complex numbers›

lemma has_sum_cnj_iff[simp]: 
  fixes f :: 'a  complex
  shows ((λx. cnj (f x)) has_sum cnj a) M  (f has_sum a) M
  by (simp add: has_sum_def lim_cnj del: cnj_sum add: cnj_sum[symmetric, abs_def, of f])

lemma summable_on_cnj_iff[simp]:
  "(λi. cnj (f i)) summable_on A  f summable_on A"
  by (metis complex_cnj_cnj summable_on_def has_sum_cnj_iff)

lemma infsum_cnj[simp]: infsum (λx. cnj (f x)) M = cnj (infsum f M)
  by (metis complex_cnj_zero infsumI has_sum_cnj_iff infsum_def summable_on_cnj_iff has_sum_infsum)

lemma has_sum_Re:
  assumes "(f has_sum a) M"
  shows "((λx. Re (f x)) has_sum Re a) M"
  using has_sum_comm_additive[where f=Re]
  using  assms tendsto_Re by (fastforce simp add: o_def additive_def)

lemma infsum_Re:
  assumes "f summable_on M"
  shows "infsum (λx. Re (f x)) M = Re (infsum f M)"
  by (simp add: assms has_sum_Re infsumI)

lemma summable_on_Re: 
  assumes "f summable_on M"
  shows "(λx. Re (f x)) summable_on M"
  by (metis assms has_sum_Re summable_on_def)

lemma has_sum_Im:
  assumes "(f has_sum a) M"
  shows "((λx. Im (f x)) has_sum Im a) M"
  using has_sum_comm_additive[where f=Im]
  using  assms tendsto_Im by (fastforce simp add: o_def additive_def)

lemma infsum_Im: 
  assumes "f summable_on M"
  shows "infsum (λx. Im (f x)) M = Im (infsum f M)"
  by (simp add: assms has_sum_Im infsumI)

lemma summable_on_Im: 
  assumes "f summable_on M"
  shows "(λx. Im (f x)) summable_on M"
  by (metis assms has_sum_Im summable_on_def)

lemma nonneg_infsum_le_0D_complex:
  fixes f :: "'a  complex"
  assumes "infsum f A  0"
    and abs_sum: "f summable_on A"
    and nneg: "x. x  A  f x  0"
    and "x  A"
  shows "f x = 0"
proof -
  have Im (f x) = 0
    using assms(4) less_eq_complex_def nneg by auto
  moreover have Re (f x) = 0
    using assms by (auto simp add: summable_on_Re infsum_Re less_eq_complex_def intro: nonneg_infsum_le_0D[where A=A])
  ultimately show ?thesis
    by (simp add: complex_eqI)
qed

lemma nonneg_has_sum_le_0D_complex:
  fixes f :: "'a  complex"
  assumes "(f has_sum a) A" and a  0
    and "x. x  A  f x  0" and "x  A"
  shows "f x = 0"
  by (metis assms infsumI nonneg_infsum_le_0D_complex summable_on_def)

text ‹The lemma @{thm [source] infsum_mono_neutral} above applies to various linear ordered monoids such as the reals but not to the complex numbers.
      Thus we have a separate corollary for those:›

lemma infsum_mono_neutral_complex:
  fixes f :: "'a  complex"
  assumes [simp]: "f summable_on A"
    and [simp]: "g summable_on B"
  assumes x. x  AB  f x  g x
  assumes x. x  A-B  f x  0
  assumes x. x  B-A  g x  0
  shows infsum f A  infsum g B
proof -
  have infsum (λx. Re (f x)) A  infsum (λx. Re (g x)) B
    by (smt (verit) assms infsum_cong infsum_mono_neutral less_eq_complex_def summable_on_Re zero_complex.simps(1))
  then have Re: Re (infsum f A)  Re (infsum g B)
    by (metis assms(1-2) infsum_Re)
  have infsum (λx. Im (f x)) A = infsum (λx. Im (g x)) B
    by (smt (verit, best) assms(3-5) infsum_cong_neutral less_eq_complex_def zero_complex.simps(2))
  then have Im: Im (infsum f A) = Im (infsum g B)
    by (metis assms(1-2) infsum_Im)
  from Re Im show ?thesis
    by (auto simp: less_eq_complex_def)
qed

lemma infsum_mono_complex:
  ― ‹For typreal, @{thm [source] infsum_mono} can be used. 
      But typcomplex does not have the right typeclass.›
  fixes f g :: "'a  complex"
  assumes f_sum: "f summable_on A" and g_sum: "g summable_on A"
  assumes leq: "x. x  A  f x  g x"
  shows   "infsum f A  infsum g A"
  by (metis DiffE IntD1 f_sum g_sum infsum_mono_neutral_complex leq)


lemma infsum_nonneg_complex:
  fixes f :: "'a  complex"
  assumes "f summable_on M"
    and "x. x  M  0  f x"
  shows "infsum f M  0" (is "?lhs  _")
  by (metis assms infsum_0_simp summable_on_0_simp infsum_mono_complex)

lemma infsum_cmod:
  assumes "f summable_on M"
    and fnn: "x. x  M  0  f x"
  shows "infsum (λx. cmod (f x)) M = cmod (infsum f M)"
proof -
  have complex_of_real (infsum (λx. cmod (f x)) M) = infsum (λx. complex_of_real (cmod (f x))) M
  proof (rule infsum_comm_additive[symmetric, unfolded o_def])
    have "(λz. Re (f z)) summable_on M"
      using assms summable_on_Re by blast
    also have "?this  f abs_summable_on M"
      using fnn by (intro summable_on_cong) (auto simp: less_eq_complex_def cmod_def)
    finally show  .
  qed (auto simp: additive_def)
  also have  = infsum f M
    using fnn cmod_eq_Re complex_is_Real_iff less_eq_complex_def by (force cong: infsum_cong)
  finally show ?thesis
    by (metis abs_of_nonneg infsum_def le_less_trans norm_ge_zero norm_infsum_bound norm_of_real not_le order_refl)
qed


lemma summable_on_iff_abs_summable_on_complex:
  fixes f :: 'a  complex
  shows f summable_on A  f abs_summable_on A
proof (rule iffI)
  assume f summable_on A
  define i r ni nr n where i x = Im (f x) and r x = Re (f x)
    and ni x = norm (i x) and nr x = norm (r x) and n x = norm (f x) for x
  from f summable_on A have i summable_on A
    by (simp add: i_def[abs_def] summable_on_Im)
  then have [simp]: ni summable_on A
    using ni_def[abs_def] summable_on_iff_abs_summable_on_real by force

  from f summable_on A have r summable_on A
    by (simp add: r_def[abs_def] summable_on_Re)
  then have [simp]: nr summable_on A
    by (metis nr_def summable_on_cong summable_on_iff_abs_summable_on_real)

  have n_sum: n x  nr x + ni x for x
    by (simp add: n_def nr_def ni_def r_def i_def cmod_le)

  have *: (λx. nr x + ni x) summable_on A
    by (simp add: summable_on_add)
  have "bdd_above (sum n ` {F. F  A  finite F})"
    apply (rule bdd_aboveI[where M=infsum (λx. nr x + ni x) A])
    using * n_sum by (auto simp flip: infsum_finite simp: ni_def nr_def intro!: infsum_mono_neutral)
  then show n summable_on A
    by (simp add: n_def nonneg_bdd_above_summable_on)
next
  show f abs_summable_on A  f summable_on A
    using abs_summable_summable by blast
qed

lemma summable_countable_complex:
  fixes f :: 'a  complex
  assumes f summable_on A
  shows countable {xA. f x  0}
  using abs_summable_countable assms summable_on_iff_abs_summable_on_complex by blast


(* TODO: figure all this out *)
inductive (in topological_space) convergent_filter :: "'a filter  bool" where
  "F  nhds x  convergent_filter F"

lemma (in topological_space) convergent_filter_iff: "convergent_filter F  (x. F  nhds x)"
  by (auto simp: convergent_filter.simps)

lemma (in uniform_space) cauchy_filter_mono:
  "cauchy_filter F  F'  F  cauchy_filter F'"
  unfolding cauchy_filter_def by (meson dual_order.trans prod_filter_mono)

lemma (in uniform_space) convergent_filter_cauchy: 
  assumes "convergent_filter F"
  shows   "cauchy_filter F"
  using assms cauchy_filter_mono nhds_imp_cauchy_filter[OF order.refl]
  by (auto simp: convergent_filter_iff)

lemma (in topological_space) convergent_filter_bot [simp, intro]: "convergent_filter bot"
  by (simp add: convergent_filter_iff)



class complete_uniform_space = uniform_space +
  assumes cauchy_filter_convergent': "cauchy_filter (F :: 'a filter)  F  bot  convergent_filter F"

lemma (in complete_uniform_space)
  cauchy_filter_convergent: "cauchy_filter (F :: 'a filter)  convergent_filter F"
  using cauchy_filter_convergent'[of F] by (cases "F = bot") auto

lemma (in complete_uniform_space) convergent_filter_iff_cauchy:
  "convergent_filter F  cauchy_filter F"
  using convergent_filter_cauchy cauchy_filter_convergent by blast

definition countably_generated_filter :: "'a filter  bool" where
  "countably_generated_filter F  (U :: nat  'a set. F = (INF (n::nat). principal (U n)))"

lemma countably_generated_filter_has_antimono_basis:
  assumes "countably_generated_filter F"
  obtains B :: "nat  'a set"
  where "antimono B" and "F = (INF n. principal (B n))" and
        "P. eventually P F  (i. xB i. P x)"
proof -
  from assms obtain B where B: "F = (INF (n::nat). principal (B n))"
    unfolding countably_generated_filter_def by blast

  define B' where "B' = (λn. kn. B k)"
  have "antimono B'"
    unfolding decseq_def B'_def by force

  have "(INF n. principal (B' n)) = (INF n. INF k{..n}. principal (B k))"
    unfolding B'_def by (intro INF_cong refl INF_principal_finite [symmetric]) auto
  also have " = (INF (n::nat). principal (B n))"
    apply (intro antisym)
    apply (meson INF_lower INF_mono atMost_iff order_refl)
    apply (meson INF_greatest INF_lower UNIV_I)
    done
  also have " = F"
    by (simp add: B)
  finally have F: "F = (INF n. principal (B' n))" ..

  moreover have "eventually P F  (i. eventually P (principal (B' i)))" for P
    unfolding F using antimono B'
    apply (subst eventually_INF_base)
      apply (auto simp: decseq_def)
    by (meson nat_le_linear)
  ultimately show ?thesis
    using antimono B' that[of B'] unfolding eventually_principal by blast
qed

lemma (in uniform_space) cauchy_filter_iff:
  "cauchy_filter F  (P. eventually P uniformity  (X. eventually (λx. x  X) F  (zX×X. P z)))" 
  unfolding cauchy_filter_def le_filter_def
  apply auto
   apply (smt (z3) eventually_mono eventually_prod_same mem_Collect_eq)
  using eventually_prod_same by blast                            

lemma (in uniform_space) controlled_sequences_convergent_imp_complete_aux_sequence:
  fixes U :: "nat  ('a × 'a) set"
  fixes F :: "'a filter"
  assumes "cauchy_filter F" "F  bot"
  assumes "n. eventually (λz. z  U n) uniformity"
  obtains g G where
    "antimono G" "n. g n  G n"
    "n. eventually (λx. x  G n) F" "n. G n × G n  U n"
proof -
  have "C. eventually (λx. x  C) F  C × C  U n" for n
    using assms(1) assms(3)[of n] unfolding cauchy_filter_iff by blast
  then obtain G where G: "n. eventually (λx. x  G n) F" "n. G n × G n  U n"
    by metis
  define G' where "G' = (λn. kn. G k)"
  have 1: "eventually (λx. x  G' n) F" for n
    using G by (auto simp: G'_def intro: eventually_ball_finite)
  have 2: "G' n × G' n  U n" for n
    using G unfolding G'_def by fast
  have 3: "antimono G'"
    unfolding G'_def decseq_def by force

  have "g. g  G' n" for n
    using 1 assms(2) eventually_happens' by auto
  then obtain g where g: "n. g n  G' n"
    by metis
  from g 1 2 3 that[of G' g] show ?thesis
    by metis
qed

definition lift_filter :: "('a set  'b filter)  'a filter  'b filter" where
  "lift_filter f F = (INF X{X. eventually (λx. x  X) F}. f X)"

lemma lift_filter_top [simp]: "lift_filter g top = g UNIV"
proof -
  have "{X. x::'b. x  X} = {UNIV}"
    by auto
  thus ?thesis
    by (simp add: lift_filter_def)
qed

lemma eventually_lift_filter_iff:
  assumes "mono g"
  shows   "eventually P (lift_filter g F)  (X. eventually (λx. x  X) F  eventually P (g X))"
  unfolding lift_filter_def
proof (subst eventually_INF_base, goal_cases)
  case 1
  thus ?case by (auto intro: exI[of _ UNIV])
next
  case (2 X Y)
  thus ?case
    by (auto intro!: exI[of _ "X  Y"] eventually_conj monoD[OF assms])
qed auto

lemma lift_filter_le:
  assumes "eventually (λx. x  X) F" "g X  F'"
  shows   "lift_filter g F  F'"
  unfolding lift_filter_def
  by (metis INF_lower2 assms mem_Collect_eq)

definition lift_filter' :: "('a set  'b set)  'a filter  'b filter" where
  "lift_filter' f F = lift_filter (principal  f) F"

lemma lift_filter'_top [simp]: "lift_filter' g top = principal (g UNIV)"
  by (simp add: lift_filter'_def)

lemma eventually_lift_filter'_iff:
  assumes "mono g"
  shows   "eventually P (lift_filter' g F)  (X. eventually (λx. x  X) F  (xg X. P x))"
  unfolding lift_filter'_def using assms
  by (subst eventually_lift_filter_iff) (auto simp: mono_def eventually_principal)

lemma lift_filter'_le:
  assumes "eventually (λx. x  X) F" "principal (g X)  F'"
  shows   "lift_filter' g F  F'"
  unfolding lift_filter'_def using assms
  by (intro lift_filter_le[where X = X]) auto


lemma (in uniform_space) comp_uniformity_le_uniformity:
  "lift_filter' (λX. X O X) uniformity  uniformity"
  unfolding le_filter_def
proof safe
  fix P assume P: "eventually P uniformity"
  have [simp]: "mono (λX::('a × 'a) set. X O X)"
    by (intro monoI) auto
  from P obtain P' where P': "eventually P' uniformity " "(x y z. P' (x, y)  P' (y, z)  P (x, z))"
    using uniformity_transE by blast
  show "eventually P (lift_filter' (λX. X O X) uniformity)"
    by (auto simp: eventually_lift_filter'_iff intro!: exI[of _ "{x. P' x}"] P')
qed

lemma (in uniform_space) comp_mem_uniformity_sets:
  assumes "eventually (λz. z  X) uniformity"
  obtains Y where "eventually (λz. z  Y) uniformity" "Y O Y  X"
proof -
  have [simp]: "mono (λX::('a × 'a) set. X O X)"
    by (intro monoI) auto
  have "eventually (λz. z  X) (lift_filter' (λX. X O X) uniformity)"
    using assms comp_uniformity_le_uniformity using filter_leD by blast
  thus ?thesis using that
    by (auto simp: eventually_lift_filter'_iff)
qed

lemma (in uniform_space) le_nhds_of_cauchy_adhp_aux:
  assumes "P. eventually P uniformity  (X. eventually (λy. y  X) F  (zX × X. P z)  (y. P (x, y)  y  X))"
  shows   "F  nhds x"
  unfolding le_filter_def
proof safe
  fix P assume "eventually P (nhds x)"
  hence "F z in uniformity. z  {z. fst z = x  P (snd z)}"
    by (simp add: eventually_nhds_uniformity case_prod_unfold)
  then obtain Y where Y: "F z in uniformity. z  Y" "Y O Y  {z. fst z = x  P (snd z)}"
    using comp_mem_uniformity_sets by blast
  obtain X y where Xy: "eventually (λy. y  X) F" "X×X  Y" "(x, y)  Y" "y  X"
    using assms[OF Y(1)] by blast
  have *: "P x" if "x  X" for x
    using Y(2) Xy(2-4) that unfolding relcomp_unfold by force  
  show "eventually P F"
    by (rule eventually_mono[OF Xy(1)]) (use * in auto)
qed

lemma (in uniform_space) eventually_uniformity_imp_nhds:
  assumes "eventually P uniformity"
  shows   "eventually (λy. P (x, y)) (nhds x)"
  using assms unfolding eventually_nhds_uniformity by (elim eventually_mono) auto

lemma (in uniform_space) controlled_sequences_convergent_imp_complete_aux:
  fixes U :: "nat  ('a × 'a) set"
  assumes gen: "countably_generated_filter (uniformity :: ('a × 'a) filter)"
  assumes U: "n. eventually (λz. z  U n) uniformity"
  assumes conv: "(u :: nat  'a). (N m n. N  m  N  n  (u m, u n)  U N)  convergent u"
  assumes "cauchy_filter F"
  shows   "convergent_filter F"
proof (cases "F = bot")
  case False
  note F = cauchy_filter F F  bot
  from gen obtain B :: "nat  ('a × 'a) set" where B:
    "antimono B" "uniformity = (INF n. principal (B n))"
    "P. eventually P uniformity  (i. xB i. P x)"
    using countably_generated_filter_has_antimono_basis by blast

  have ev_B: "eventually (λz. z  B n) uniformity" for n
    by (subst B(3)) auto
  hence ev_B': "eventually (λz. z  B n  U n) uniformity" for n
    using U by (auto intro: eventually_conj)

  obtain g G where gG: "antimono G" "n. g n  G n"
    "n. eventually (λx. x  G n) F" "n. G n × G n  B n  U n"
    using controlled_sequences_convergent_imp_complete_aux_sequence[of F "λn. B n  U n", OF F ev_B']
    by metis

  have "convergent g"
  proof (rule conv)
    fix N m n :: nat
    assume mn: "N  m" "N  n"
    have "(g m, g n)  G m × G n"
      using gG by auto
    also from mn have "  G N × G N"
      by (intro Sigma_mono gG antimonoD[OF gG(1)])
    also have "  U N"
      using gG by blast
    finally show "(g m, g n)  U N" .
  qed
  then obtain L where G: "g  L"
    unfolding convergent_def by blast

  have "F  nhds L"
  proof (rule le_nhds_of_cauchy_adhp_aux)
    fix P :: "'a × 'a  bool"
    assume P: "eventually P uniformity"
    hence "eventually (λn. xB n. P x) sequentially"
      using antimono B unfolding B(3) eventually_sequentially decseq_def by blast
    moreover have "eventually (λn. P (L, g n)) sequentially"
      using P eventually_compose_filterlim eventually_uniformity_imp_nhds G by blast
    ultimately have "eventually (λn. (xB n. P x)  P (L, g n)) sequentially"
      by eventually_elim auto
    then obtain n where "xB n. P x" "P (L, g n)"
      unfolding eventually_at_top_linorder by blast
    then show "X. (F y in F. y  X)  (zX × X. P z)  (y. P (L, y)  y  X)"
      using gG by blast+
  qed
  thus "convergent_filter F"
    by (auto simp: convergent_filter_iff)
qed auto

theorem (in uniform_space) controlled_sequences_convergent_imp_complete:
  fixes U :: "nat  ('a × 'a) set"
  assumes gen: "countably_generated_filter (uniformity :: ('a × 'a) filter)"
  assumes U: "n. eventually (λz. z  U n) uniformity"
  assumes conv: "(u :: nat  'a). (N m n. N  m  N  n  (u m, u n)  U N)  convergent u"
  shows "class.complete_uniform_space open uniformity"
  by unfold_locales (use assms controlled_sequences_convergent_imp_complete_aux in blast)

lemma filtermap_prod_filter: "filtermap (map_prod f g) (F ×F G) = filtermap f F ×F filtermap g G"
proof (intro antisym)
  show "filtermap (map_prod f g) (F ×F G)  filtermap f F ×F filtermap g G"
    by (auto simp: le_filter_def eventually_filtermap eventually_prod_filter)
next
  show "filtermap f F ×F filtermap g G  filtermap (map_prod f g) (F ×F G)"
    unfolding le_filter_def
  proof safe
    fix P assume P: "eventually P (filtermap (map_prod f g) (F ×F G))"
    then obtain Pf Pg where *: "eventually Pf F" "eventually Pg G" "x. Pf x  (y. Pg y  P (f x, g y))"
      by (auto simp: eventually_filtermap eventually_prod_filter)

    define Pf' where "Pf' = (λx. y. x = f y  Pf y)"
    define Pg' where "Pg' = (λx. y. x = g y  Pg y)"

    from *(1) have "F x in F. Pf' (f x)"
      by eventually_elim (auto simp: Pf'_def)
    moreover from *(2) have "F x in G. Pg' (g x)"
      by eventually_elim (auto simp: Pg'_def)
    moreover have "(x y. Pf' x  Pg' y  P (x, y))"
      using *(3) by (auto simp: Pf'_def Pg'_def)
    ultimately show "eventually P (filtermap f F ×F filtermap g G)"
      unfolding eventually_prod_filter eventually_filtermap
      by blast
  qed
qed
      

lemma (in uniform_space) Cauchy_seq_iff_tendsto:
  "Cauchy f  filterlim (map_prod f f) uniformity (at_top ×F at_top)"
  unfolding Cauchy_uniform cauchy_filter_def filterlim_def filtermap_prod_filter ..

theorem (in uniform_space) controlled_seq_imp_Cauchy_seq:
  fixes U :: "nat  ('a × 'a) set"
  assumes U: "P. eventually P uniformity  (n. xU n. P x)"
  assumes controlled: "N m n. N  m  N  n  (f m, f n)  U N"
  shows   "Cauchy f"
  unfolding Cauchy_seq_iff_tendsto
proof -
  show "filterlim (map_prod f f) uniformity (sequentially ×F sequentially)"
    unfolding filterlim_def le_filter_def
  proof safe
    fix P :: "'a × 'a  bool"
    assume P: "eventually P uniformity"
    from U[OF this] obtain N where "xU N. P x"
      by blast
    then show "eventually P (filtermap (map_prod f f) (sequentially ×F sequentially))"
      unfolding eventually_filtermap eventually_prod_sequentially
      by (metis controlled map_prod_simp)
  qed
qed

lemma (in uniform_space) Cauchy_seq_convergent_imp_complete_aux:
  fixes U :: "nat  ('a × 'a) set"
  assumes gen: "countably_generated_filter (uniformity :: ('a × 'a) filter)"
  assumes conv: "(u :: nat  'a). Cauchy u  convergent u"
  assumes "cauchy_filter F"
  shows   "convergent_filter F"
proof -
  from gen obtain B :: "nat  ('a × 'a) set" where B:
    "antimono B" "uniformity = (INF n. principal (B n))"
    "P. eventually P uniformity  (i. xB i. P x)"
    using countably_generated_filter_has_antimono_basis by blast

  show ?thesis
  proof (rule controlled_sequences_convergent_imp_complete_aux[where U = B])
    show "F z in uniformity. z  B n" for n
      unfolding B(3) by blast
  next
    fix f :: "nat  'a"
    assume f: "N m n. N  m  N  n  (f m, f n)  B N"
    have "Cauchy f" using f B
      by (intro controlled_seq_imp_Cauchy_seq[where U = B]) auto
    with conv show "convergent f"
      by simp
  qed fact+
qed

theorem (in uniform_space) Cauchy_seq_convergent_imp_complete:
  fixes U :: "nat  ('a × 'a) set"
  assumes gen: "countably_generated_filter (uniformity :: ('a × 'a) filter)"
  assumes conv: "(u :: nat  'a). Cauchy u  convergent u"
  shows   "class.complete_uniform_space open uniformity"
  by unfold_locales (use assms Cauchy_seq_convergent_imp_complete_aux in blast)

lemma (in metric_space) countably_generated_uniformity:
  "countably_generated_filter uniformity"
proof -
  have "(INF e{0<..}. principal {(x, y). dist (x::'a) y < e}) =
        (INF nUNIV. principal {(x, y). dist x y < 1 / real (Suc n)})" (is "?F = ?G")
    unfolding uniformity_dist
  proof (intro antisym)
    have "?G = (INF e(λn. 1 / real (Suc n)) ` UNIV. principal {(x, y). dist x y < e})"
      by (simp add: image_image)
    also have "  ?F"
      by (intro INF_superset_mono) auto
    finally show "?F  ?G" .
  next
    show "?G  ?F"
      unfolding le_filter_def
    proof safe
      fix P assume "eventually P ?F"
      then obtain ε where ε: "ε > 0" "eventually P (principal {(x, y). dist x y < ε})"
      proof (subst (asm) eventually_INF_base, goal_cases)
        case (2 ε1 ε2)
        thus ?case
          by (intro bexI[of _ "min ε1 ε2"]) auto
      qed auto
      from ε > 0 obtain n where "1 / real (Suc n) < ε"
        using nat_approx_posE by blast
      then have "eventually P (principal {(x, y). dist x y < 1 / real (Suc n)})"
        using ε(2) by (auto simp: eventually_principal)
      thus "eventually P ?G"
        by (intro eventually_INF1) auto
    qed
  qed
  thus "countably_generated_filter uniformity"
    unfolding countably_generated_filter_def uniformity_dist by fast
qed

subclass (in complete_space) complete_uniform_space
proof (rule Cauchy_seq_convergent_imp_complete)
  show "convergent f" if "Cauchy f" for f
    using Cauchy_convergent that by blast
qed (fact countably_generated_uniformity)

lemma (in complete_uniform_space) complete_UNIV_cuspace [intro]: "complete UNIV"
  unfolding complete_uniform using cauchy_filter_convergent
  by (auto simp: convergent_filter.simps)



lemma norm_infsum_le:
  assumes "(f has_sum S) X"
  assumes "(g has_sum T) X"
  assumes "x. x  X  norm (f x)  g x"
  shows   "norm S  T"
proof (rule tendsto_le)
  show "((λY. norm (xY. f x))  norm S) (finite_subsets_at_top X)"
    using assms(1) unfolding has_sum_def by (intro tendsto_norm)
  show "((λY. xY. g x)  T) (finite_subsets_at_top X)"
    using assms(2) unfolding has_sum_def .
  show "F x in finite_subsets_at_top X. norm (sum f x)  (xx. g x)"
    by (simp add: assms(3) eventually_finite_subsets_at_top_weakI subsetD sum_norm_le)
qed auto

(*
lemma summable_on_Sigma:
  fixes A :: "'a set" and B :: "'a ⇒ 'b set"
    and f :: ‹'a ⇒ 'b ⇒ 'c::{comm_monoid_add, t2_space, uniform_space}›
  assumes plus_cont: ‹uniformly_continuous_on UNIV (λ(x::'c,y). x+y)›
  assumes summableAB: "(λ(x,y). f x y) summable_on (Sigma A B)"
  assumes summableB: ‹⋀x. x∈A ⟹ (f x) summable_on (B x)›
  shows ‹(λx. infsum (f x) (B x)) summable_on A›
*)

lemma has_sum_imp_summable: "(f has_sum S) A  f summable_on A"
  by (auto simp: summable_on_def)

lemma has_sum_reindex_bij_betw:
  assumes "bij_betw g A B"
  shows   "((λx. f (g x)) has_sum S) A = (f has_sum S) B"
proof -
  have "((λx. f (g x)) has_sum S) A  (f has_sum S) (g ` A)"
    by (subst has_sum_reindex) (use assms in auto dest: bij_betw_imp_inj_on simp: o_def)
  then show ?thesis
    using assms bij_betw_imp_surj_on by blast 
qed

lemma has_sum_reindex_bij_witness:
  assumes "a. a  S  i (j a) = a"
  assumes "a. a  S  j a  T"
  assumes "b. b  T  j (i b) = b"
  assumes "b. b  T  i b  S"
  assumes "a. a  S  h (j a) = g a"
  assumes "s = s'"
  shows   "(g has_sum s) S = (h has_sum s') T"
  by (smt (verit, del_insts) assms bij_betwI' has_sum_cong has_sum_reindex_bij_betw)


lemma has_sum_homomorphism:
  assumes "(f has_sum S) A" "h 0 = 0" "a b. h (a + b) = h a + h b" "continuous_on UNIV h"
  shows   "((λx. h (f x)) has_sum (h S)) A"
proof -
  have "sum (h  f) X = h (sum f X)" for X
    by (induction X rule: infinite_finite_induct) (simp_all add: assms)
  hence sum_h: "sum (h  f) = h  sum f"
    by (intro ext) auto
  then have "((h  f) has_sum h S) A"
    using assms
    by (metis UNIV_I continuous_on_def has_sum_comm_additive_general o_apply)
  thus ?thesis
    by (simp add: o_def)
qed

lemma summable_on_homomorphism:
  assumes "f summable_on A" "h 0 = 0" "a b. h (a + b) = h a + h b" "continuous_on UNIV h"
  shows   "(λx. h (f x)) summable_on A"
proof -
  from assms(1) obtain S where "(f has_sum S) A"
    by (auto simp: summable_on_def)
  hence "((λx. h (f x)) has_sum h S) A"
    by (rule has_sum_homomorphism) (use assms in auto)
  thus ?thesis
    by (auto simp: summable_on_def)
qed

lemma infsum_homomorphism_strong:
  fixes h :: "'a :: {t2_space, topological_comm_monoid_add} 
                'b :: {t2_space, topological_comm_monoid_add}"
  assumes "(λx. h (f x)) summable_on A  f summable_on A"
  assumes "h 0 = 0" 
  assumes "S. (f has_sum S) A  ((λx. h (f x)) has_sum (h S)) A"
  shows   "infsum (λx. h (f x)) A = h (infsum f A)"
  by (metis assms has_sum_infsum infsumI infsum_not_exists)

lemma has_sum_bounded_linear:
  assumes "bounded_linear h" and "(f has_sum S) A"
  shows "((λx. h (f x)) has_sum h S) A"
proof -
  interpret bounded_linear h by fact
  from assms(2) show ?thesis
    by (rule has_sum_homomorphism) (auto simp: add intro!: continuous_on)
qed

lemma summable_on_bounded_linear:
  assumes "bounded_linear h" and "f summable_on A"
  shows "(λx. h (f x)) summable_on A"
  by (metis assms has_sum_bounded_linear summable_on_def)

lemma summable_on_bounded_linear_iff:
  assumes "bounded_linear h" and "bounded_linear h'" and "x. h' (h x) = x"
  shows "(λx. h (f x)) summable_on A  f summable_on A"
  by (metis (full_types) assms summable_on_bounded_linear summable_on_cong)

lemma infsum_bounded_linear_strong:
  fixes h :: "'a :: real_normed_vector  'b :: real_normed_vector"
  assumes "(λx. h (f x)) summable_on A  f summable_on A"
  assumes "bounded_linear h"
  shows   "infsum (λx. h (f x)) A = h (infsum f A)"
proof -
  interpret bounded_linear h by fact
  show ?thesis
    by (rule infsum_homomorphism_strong)
       (insert assms, auto intro: add continuous_on has_sum_bounded_linear)
qed

lemma infsum_bounded_linear_strong':
  fixes mult :: "'c :: zero  'a :: real_normed_vector  'b :: real_normed_vector"
  assumes "c  0  (λx. mult c (f x)) summable_on A  f summable_on A"
  assumes "bounded_linear (mult c)"
  assumes [simp]: "x. mult 0 x = 0"
  shows   "infsum (λx. mult c (f x)) A = mult c (infsum f A)"
  by (metis assms infsum_0 infsum_bounded_linear_strong)

lemma has_sum_of_nat: "(f has_sum S) A  ((λx. of_nat (f x)) has_sum of_nat S) A"
  by (erule has_sum_homomorphism) (auto intro!: continuous_intros)

lemma has_sum_of_int: "(f has_sum S) A  ((λx. of_int (f x)) has_sum of_int S) A"
  by (erule has_sum_homomorphism) (auto intro!: continuous_intros)

lemma summable_on_of_nat: "f summable_on A  (λx. of_nat (f x)) summable_on A"
  by (erule summable_on_homomorphism) (auto intro!: continuous_intros)

lemma summable_on_of_int: "f summable_on A  (λx. of_int (f x)) summable_on A"
  by (erule summable_on_homomorphism) (auto intro!: continuous_intros)

lemma summable_on_discrete_iff:
  fixes f :: "'a  'b :: {discrete_topology, topological_comm_monoid_add, cancel_comm_monoid_add}"
  shows "f summable_on A  finite {xA. f x  0}"
proof
  assume *: "finite {xA. f x  0}"
  hence "f summable_on {xA. f x  0}"
    by (rule summable_on_finite)
  then show "f summable_on A"
    by (smt (verit) DiffE mem_Collect_eq summable_on_cong_neutral) 
next
  assume "f summable_on A"
  then obtain S where "(f has_sum S) A"
    by (auto simp: summable_on_def)
  hence "F x in finite_subsets_at_top A. sum f x = S"
    unfolding has_sum_def tendsto_discrete .
  then obtain X where X: "finite X" "X  A" "Y. finite Y  X  Y  Y  A  sum f Y = S"
    unfolding eventually_finite_subsets_at_top by metis
  have "{xA. f x  0}  X"
  proof
    fix x assume x: "x  {xA. f x  0}"
    show "x  X"
    proof (rule ccontr)
      assume [simp]: "x  X"
      have "sum f (insert x X) = S"
        using X x by (intro X) auto
      then have "f x = 0"
        using X by auto
      with x show False
        by auto
    qed
  qed
  thus "finite {xA. f x  0}"
    using X(1) finite_subset by blast
qed

lemma has_sum_imp_sums: "(f has_sum S) (UNIV :: nat set)  f sums S"
  unfolding sums_def has_sum_def by (rule filterlim_compose[OF _ filterlim_lessThan_at_top])

lemma summable_on_imp_summable: "f summable_on (UNIV :: nat set)  summable f"
  unfolding summable_on_def summable_def by (auto dest: has_sum_imp_sums)

lemma summable_on_UNIV_nonneg_real_iff:
  assumes "n. f n  (0 :: real)"
  shows   "f summable_on UNIV  summable f"
  using assms by (auto intro: norm_summable_imp_summable_on summable_on_imp_summable)

lemma summable_on_imp_bounded_partial_sums:
  fixes f :: "_  'a :: {topological_comm_monoid_add, linorder_topology}"
  assumes f: "f summable_on A"
  shows   "C. eventually (λX. sum f X  C) (finite_subsets_at_top A)"
proof -
  from assms obtain S where S: "(sum f  S) (finite_subsets_at_top A)"
    unfolding summable_on_def has_sum_def by blast
  show ?thesis
  proof (cases "C. C > S")
    case True
    then obtain C where C: "C > S"
      by blast
    have "F X in finite_subsets_at_top A. sum f X < C"
      using S C by (rule order_tendstoD(2))
    thus ?thesis
      by (meson eventually_mono nless_le)
  next
    case False thus ?thesis
      by (meson not_eventuallyD not_le_imp_less)
  qed
qed

lemma has_sum_mono':
  fixes S S' :: "'a :: {linorder_topology, ordered_comm_monoid_add, topological_comm_monoid_add}"
  assumes f: "(f has_sum S) A" "(f has_sum S') B" 
     and AB: "A  B" "x. x  B - A  f x  0"
  shows   "S  S'"
  using AB has_sum_mono_neutral[OF f] by fastforce


context
  assumes "SORT_CONSTRAINT('a :: {topological_comm_monoid_add, order_topology,
             ordered_comm_monoid_add, conditionally_complete_linorder})"
begin

text ‹
  Any family of non-negative numbers with bounded partial sums is summable, and the sum
  is simply the supremum of the partial sums.
›
lemma nonneg_bounded_partial_sums_imp_has_sum_SUP:
  assumes nonneg: "x. x  A  f x  (0::'a)"
      and bound:  "eventually (λX. sum f X  C) (finite_subsets_at_top A)"
  shows   "(f has_sum (SUP X{X. X  A  finite X}. sum f X)) A"
proof -
  from bound obtain X0
    where X0: "X0  A" "finite X0" "X. X0  X  X  A  finite X  sum f X  C"
    by (force simp: eventually_finite_subsets_at_top)
  have bound': "sum f X  C" if "X  A" "finite X" for X
  proof -
    have "sum f X  sum f (X  X0)"
      using that X0 assms(1) by (intro sum_mono2) auto
    also have "  C"
      by (simp add: X0 that)
    finally show ?thesis .
  qed
  hence bdd: "bdd_above (sum f ` {X. X  A  finite X})"
    by (auto simp: bdd_above_def)

  show ?thesis unfolding has_sum_def
  proof (rule increasing_tendsto)
    show "F X in finite_subsets_at_top A. sum f X  Sup (sum f ` {X. X  A  finite X})"
      by (intro eventually_finite_subsets_at_top_weakI cSUP_upper[OF _ bdd]) auto
  next
    fix y assume "y < Sup (sum f ` {X. X  A  finite X})"
    then obtain X where X: "X  A" "finite X" "y < sum f X"
      by (subst (asm) less_cSUP_iff[OF _ bdd]) auto
    from X have "eventually (λX'. X  X'  X'  A  finite X') (finite_subsets_at_top A)"
      by (auto simp: eventually_finite_subsets_at_top)
    thus "eventually (λX'. y < sum f X') (finite_subsets_at_top A)"
    proof eventually_elim
      case (elim X')
      note y < sum f X
      also have "sum f X  sum f X'"
        using nonneg elim by (intro sum_mono2) auto
      finally show ?case .
    qed
  qed
qed

lemma nonneg_bounded_partial_sums_imp_summable_on:
  assumes nonneg: "x. x  A  f x  (0::'a)"
      and bound:  "eventually (λX. sum f X  C) (finite_subsets_at_top A)"
  shows   "f summable_on A"
  using nonneg_bounded_partial_sums_imp_has_sum_SUP[OF assms] by (auto simp: summable_on_def)

end

context
  assumes "SORT_CONSTRAINT('a :: {topological_comm_monoid_add, linorder_topology,
             ordered_comm_monoid_add, conditionally_complete_linorder})"
begin

lemma summable_on_comparison_test:
  assumes "f summable_on A" and "x. x  A  g x  f x" and "x. x  A  (0::'a)  g x"
  shows   "g summable_on A"
proof -
  obtain C where C: "F X in finite_subsets_at_top A. sum f X  C"
    using assms(1) summable_on_imp_bounded_partial_sums by blast
  show ?thesis
  proof (rule nonneg_bounded_partial_sums_imp_summable_on)
    show "F X in finite_subsets_at_top A. sum g X  C"
      using C assms 
      unfolding eventually_finite_subsets_at_top
      by (smt (verit, ccfv_SIG) order_trans subsetD sum_mono)
  qed (use assms in auto)
qed

end



lemma summable_on_subset:
  fixes f :: "_  'a :: {uniform_topological_group_add, topological_comm_monoid_add, ab_group_add, complete_uniform_space}"
  assumes "f summable_on A" "B  A"
  shows "f summable_on B"
  by (rule summable_on_subset_aux[OF _ _ assms]) (auto simp: uniformly_continuous_add)

lemma summable_on_union:
  fixes f :: "_  'a :: {uniform_topological_group_add, topological_comm_monoid_add, ab_group_add, complete_uniform_space}"
  assumes "f summable_on A" "f summable_on B"
  shows "f summable_on (A  B)"
proof -
  have "f summable_on (A  (B - A))"
    by (meson Diff_disjoint Diff_subset assms summable_on_Un_disjoint summable_on_subset)
  also have "A  (B - A) = A  B"
    by blast
  finally show ?thesis .
qed

lemma summable_on_insert_iff:
  fixes f :: "_  'a :: {uniform_topological_group_add, topological_comm_monoid_add, ab_group_add, complete_uniform_space}"
  shows "f summable_on insert x A  f summable_on A"
  using summable_on_union[of f A "{x}"] by (auto intro: summable_on_subset)

lemma has_sum_finiteI: "finite A  S = sum f A  (f has_sum S) A"
  by simp

lemma has_sum_insert:
  fixes f :: "'a  'b :: topological_comm_monoid_add"
  assumes "x  A" and "(f has_sum S) A"
  shows   "(f has_sum (f x + S)) (insert x A)"
proof -
  have "(f has_sum (f x + S)) ({x}  A)"
    using assms by (intro has_sum_Un_disjoint) (auto intro: has_sum_finiteI)
  thus ?thesis by simp
qed

lemma infsum_insert:
  fixes f :: "_  'a :: {topological_comm_monoid_add, t2_space}"
  assumes "f summable_on A" "a  A"
  shows   "infsum f (insert a A) = f a + infsum f A"
  by (meson assms has_sum_insert infsumI summable_iff_has_sum_infsum)

lemma has_sum_SigmaD:
  fixes f :: "'b × 'c  'a :: {topological_comm_monoid_add,t3_space}"
  assumes sum1: "(f has_sum S) (Sigma A B)"
  assumes sum2: "x. x  A  ((λy. f (x, y)) has_sum g x) (B x)"
  shows   "(g has_sum S) A"
  unfolding has_sum_def tendsto_def eventually_finite_subsets_at_top
proof (safe, goal_cases)
  case (1 X)
  with nhds_closed[of S X] obtain X'
    where X': "S  X'" "closed X'" "X'  X" "eventually (λy. y  X') (nhds S)" by blast
  from X'(4) obtain X'' where X'': "S  X''" "open X''" "X''  X'"
    by (auto simp: eventually_nhds)
  with sum1 obtain Y :: "('b × 'c) set"
    where Y: "Y  Sigma A B" "finite Y"
             "Z. Y  Z  Z  Sigma A B  finite Z  sum f Z  X''"
    unfolding has_sum_def tendsto_def eventually_finite_subsets_at_top by force
  define Y1 :: "'b set" where "Y1 = fst ` Y"
  from Y have Y1: "Y1  A" by (auto simp: Y1_def)
  define Y2 :: "'b  'c set" where "Y2 = (λx. {y. (x, y)  Y})"
  have Y2: "finite (Y2 x)" "Y2 x  B x" if "x  A" for x
    using that Y(1,2) unfolding Y2_def
    by (force simp: image_iff intro: finite_subset[of _ "snd ` Y"])+

  show ?case
  proof (rule exI[of _ Y1], safe, goal_cases)
    case (3 Z)
    define H where "H = (INF xZ. filtercomap (λp. p x) (finite_subsets_at_top (B x)))"
    
    have "sum g Z  X'"
    proof (rule Lim_in_closed_set)
      show "closed X'" by fact
    next
      show "((λB'. sum (λx. sum (λy. f (x, y)) (B' x)) Z)  sum g Z) H"
        unfolding H_def
      proof (intro tendsto_sum filterlim_INF')
        fix x assume x: "x  Z"
        with 3 have "x  A" by auto
        from sum2[OF this] have "(sum (λy. f (x, y))  g x) (finite_subsets_at_top (B x))"
          by (simp add: has_sum_def)
        thus "((λB'. sum (λy. f (x, y)) (B' x))  g x)
                 (filtercomap (λp. p x) (finite_subsets_at_top (B x)))"
          by (rule filterlim_compose[OF _ filterlim_filtercomap])
      qed auto
    next
      show "F h in H. sum (λx. sum (λy. f (x, y)) (h x)) Z  X'"
        unfolding H_def
      proof (subst eventually_INF_finite[OF finite Z], rule exI, safe)
        fix x assume x: "x  Z"
        hence x': "x  A" using 3 by auto
        show "eventually (λh. finite (h x)  Y2 x  h x  h x  B x)
                (filtercomap (λp. p x) (finite_subsets_at_top (B x)))" using 3 Y2[OF x']
          by (intro eventually_filtercomapI)
             (auto simp: eventually_finite_subsets_at_top intro: exI[of _ "Y2 x"])
      next
        fix h
        assume *: "xZ. finite (h x)  Y2 x  h x  h x  B x"
        hence "sum (λx. sum (λy. f (x, y)) (h x)) Z = sum f (Sigma Z h)"
          using finite Z by (subst sum.Sigma) auto
        also have "  X''"
          using * 3 Y(1,2) by (intro Y; force simp: Y1_def Y2_def)
        also have "X''  X'" by fact
        finally show "sum (λx. sum (λy. f (x, y)) (h x)) Z  X'" .
      qed
    next
      have "H = (INF xSIGMA x:Z. {X. finite X  X  B x}.
                  principal {y. finite (y (fst x))  snd x  y (fst x)  y (fst x)  B (fst x)})"
        unfolding H_def finite_subsets_at_top_def filtercomap_INF filtercomap_principal
        by (simp add: INF_Sigma)
      also have "  bot"
      proof (rule INF_filter_not_bot, subst INF_principal_finite, goal_cases)
        case (2 X)
        define H' where
          "H' = (xX. {y. finite (y (fst x))  snd x  y (fst x)  y (fst x)  B (fst x)})"
        from 2 have "(λx. (y,Y)X. if x = y then Y else {})  H'"
          by (force split: if_splits simp: H'_def)
        hence "H'  {}" by blast
        thus "principal H'  bot" by (simp add: principal_eq_bot_iff)
      qed
      finally show "H  bot" .
    qed
    also have "X'  X" by fact
    finally show "sum g Z  X" .
  qed (insert Y(1,2), auto simp: Y1_def)
qed

lemma has_sum_unique:
  fixes f :: "_  'a :: {topological_comm_monoid_add, t2_space}"
  assumes "(f has_sum x) A" "(f has_sum y) A"
  shows "x = y"
  using assms unfolding has_sum_def using tendsto_unique finite_subsets_at_top_neq_bot by blast

lemma has_sum_SigmaI:
  fixes f :: "_  'a :: {topological_comm_monoid_add, t3_space}"
  assumes f: "x. x  A  ((λy. f (x, y)) has_sum g x) (B x)"
  assumes g: "(g has_sum S) A"
  assumes summable: "f summable_on Sigma A B"
  shows   "(f has_sum S) (Sigma A B)"
  by (metis f g has_sum_SigmaD has_sum_infsum has_sum_unique local.summable)

lemma summable_on_SigmaD1:
  fixes f :: "_  _  'a :: {complete_uniform_space, uniform_topological_group_add, ab_group_add, topological_comm_monoid_add}"
  assumes f: "(λ(x,y). f x y) summable_on Sigma A B"
  assumes x: "x  A"
  shows   "f x summable_on B x"
proof -
  have "(λ(x,y). f x y) summable_on Sigma {x} B"
    using f by (rule summable_on_subset) (use x in auto)
  also have "?this  ((λy. f x y)  snd) summable_on Sigma {x} B"
    by (intro summable_on_cong) auto
  also have "  (λy. f x y) summable_on snd ` Sigma {x} B"
    by (intro summable_on_reindex [symmetric] inj_onI) auto
  also have "snd ` Sigma {x} B = B x"
    by (force simp: Sigma_def)
  finally show ?thesis .
qed

lemma has_sum_swap:
  "(f has_sum S) (A × B)  ((λ(x,y). f (y,x)) has_sum S) (B × A)"
proof -
  have "bij_betw (λ(x,y). (y,x)) (B × A) (A × B)"
    by (rule bij_betwI[of _ _ _ "λ(x,y). (y,x)"]) auto
  from has_sum_reindex_bij_betw[OF this, where f = f] show ?thesis
    by (simp add: case_prod_unfold)
qed


lemma summable_on_swap:
  "f summable_on (A × B)  (λ(x,y). f (y,x)) summable_on (B × A)"
  by (metis has_sum_swap summable_on_def)

lemma has_sum_cmult_right_iff:
  fixes c :: "'a :: {topological_semigroup_mult, field}"
  assumes "c  0"
  shows   "((λx. c * f x) has_sum S) A  (f has_sum (S / c)) A"
  using has_sum_cmult_right[of f A "S/c" c]
        has_sum_cmult_right[of "λx. c * f x" A S "inverse c"] assms
  by (auto simp: field_simps)

lemma has_sum_cmult_left_iff:
  fixes c :: "'a :: {topological_semigroup_mult, field}"
  assumes "c  0"
  shows   "((λx. f x * c) has_sum S) A  (f has_sum (S / c)) A"
  by (smt (verit, best) assms has_sum_cmult_right_iff has_sum_cong mult.commute)

lemma finite_nonzero_values_imp_summable_on:
  assumes "finite {xX. f x  0}"
  shows   "f summable_on X"
  by (smt (verit, del_insts) Diff_iff assms mem_Collect_eq summable_on_cong_neutral summable_on_finite)

lemma summable_on_of_int_iff:
  "(λx::'a. of_int (f x) :: 'b :: real_normed_algebra_1) summable_on A  f summable_on A"
proof
  assume "f summable_on A"
  thus "(λx. of_int (f x)) summable_on A"
    by (rule summable_on_homomorphism) auto
next
  assume "(λx. of_int (f x) :: 'b) summable_on A"
  then obtain S where "((λx. of_int (f x) :: 'b) has_sum S) A"
    by (auto simp: summable_on_def)
  hence "(sum (λx. of_int (f x) :: 'b)  S) (finite_subsets_at_top A)"
    unfolding has_sum_def .
  moreover have "1/2 > (0 :: real)"
    by auto
  ultimately have "eventually (λX. dist (sum (λx. of_int (f x) :: 'b) X) S < 1/2)
                     (finite_subsets_at_top A)"
    unfolding tendsto_iff by blast
  then obtain X where X: "finite X" "X  A"
     "Y. finite Y  X  Y  Y  A  dist (sum (λx. of_int (f x)) Y) S < 1/2"
    unfolding eventually_finite_subsets_at_top by metis

  have "sum f Y = sum f X" if "finite Y" "X  Y" "Y  A" for Y
  proof -
    have "dist (sum (λx. of_int (f x)) X) S < 1/2"
      by (intro X) auto
    moreover have "dist (sum (λx. of_int (f x)) Y) S < 1/2"
      by (intro X that)
    ultimately have "dist (sum (λx. of_int (f x)) X) (sum (λx. of_int (f x) :: 'b) Y) <
                       1/2 + 1/2"
      using dist_triangle_less_add by blast
    thus ?thesis
      by (simp add: dist_norm flip: of_int_sum of_int_diff)
  qed
  then have "{xA. f x  0}  X"
    by (smt (verit) X finite_insert insert_iff mem_Collect_eq subset_eq sum.insert)
  with finite X have "finite {xA. f x  0}"
    using finite_subset by blast
  thus "f summable_on A"
    by (rule finite_nonzero_values_imp_summable_on)
qed

lemma summable_on_of_nat_iff:
  "(λx::'a. of_nat (f x) :: 'b :: real_normed_algebra_1) summable_on A  f summable_on A"
proof
  assume "f summable_on A"
  thus "(λx. of_nat (f x) :: 'b) summable_on A"
    by (rule summable_on_homomorphism) auto
next
  assume "(λx. of_nat (f x) :: 'b) summable_on A"
  hence "(λx. of_int (int (f x)) :: 'b) summable_on A"
    by simp
  also have "?this  (λx. int (f x)) summable_on A"
    by (rule summable_on_of_int_iff)
  also have "  f summable_on A"
    by (simp add: summable_on_discrete_iff)
  finally show "f summable_on A" .
qed

lemma infsum_of_nat:
  "infsum (λx::'a. of_nat (f x) :: 'b :: {real_normed_algebra_1}) A = of_nat (infsum f A)"
  by (metis has_sum_infsum has_sum_of_nat infsumI infsum_def of_nat_0 summable_on_of_nat_iff)

lemma infsum_of_int:
  "infsum (λx::'a. of_int (f x) :: 'b :: {real_normed_algebra_1}) A = of_int (infsum f A)"
  by (metis has_sum_infsum has_sum_of_int infsumI infsum_not_exists of_int_0 summable_on_of_int_iff)


lemma summable_on_SigmaI:
  fixes f :: "_  'a :: {linorder_topology, ordered_comm_monoid_add, topological_comm_monoid_add,
                          conditionally_complete_linorder}"
  assumes f: "x. x  A  ((λy. f (x, y)) has_sum g x) (B x)"
  assumes g: "g summable_on A"
  assumes f_nonneg: "x y. x  A  y  B x  f (x, y)  (0 :: 'a)"
  shows   "f summable_on Sigma A B"
proof -
  have g_nonneg: "g x  0" if "x  A" for x
    using f by (rule has_sum_nonneg) (use f_nonneg that in auto)
  obtain C where C: "eventually (λX. sum g X  C) (finite_subsets_at_top A)"
    using summable_on_imp_bounded_partial_sums[OF g] by blast

  have sum_g_le: "sum g X  C" if X: "finite X" "X  A" for X
  proof -
    from C obtain X' where X':
      "finite X'" "X'  A" "Y. finite Y  X'  Y  Y  A  sum g Y  C"
      unfolding eventually_finite_subsets_at_top by metis
    have "sum g X  sum g (X  X')"
      using X X' by (intro sum_mono2 g_nonneg) auto
    also have "  C"
      using X X'(1,2) by (intro X'(3)) auto
    finally show ?thesis .
  qed

  have "sum f Y  C" if Y: "finite Y" "Y  Sigma A B" for Y
  proof -
    define Y1 and Y2 where "Y1 = fst ` Y" and "Y2 = (λx. snd ` {zY. fst z = x})"
    have Y12: "Y = Sigma Y1 Y2"
      unfolding Y1_def Y2_def by force
    have [intro]: "finite Y1" "x. x  Y1  finite (Y2 x)"
      using Y unfolding Y1_def Y2_def by auto
    have Y12_subset: "Y1  A" "x. Y2 x  B x"
      using Y by (auto simp: Y1_def Y2_def)

    have "sum f Y = sum f (Sigma Y1 Y2)"
      by (simp add: Y12)
    also have " = (xY1. yY2 x. f (x, y))"
      by (subst sum.Sigma) auto
    also have "  (xY1. g x)"
    proof (rule sum_mono)
      fix x assume x: "x  Y1"
      show "(yY2 x. f (x, y))  g x"
      proof (rule has_sum_mono')
        show "((λy. f (x, y)) has_sum (yY2 x. f (x, y))) (Y2 x)"
          using x by (intro has_sum_finite) auto
        show "((λy. f (x, y)) has_sum g x) (B x)"
          by (rule f) (use x Y12_subset in auto)
        show "f (x, y)  0" if "y  B x - Y2 x" for y
          using x that Y12_subset by (intro f_nonneg) auto
      qed (use Y12_subset in auto)
    qed
    also have "  C"
      using Y12_subset by (intro sum_g_le) auto
    finally show ?thesis .
  qed

  hence "F X in finite_subsets_at_top (Sigma A B). sum f X  C"
    unfolding eventually_finite_subsets_at_top by auto
  thus ?thesis
    by (metis SigmaE f_nonneg nonneg_bounded_partial_sums_imp_summable_on)
qed

lemma summable_on_UnionI:
  fixes f :: "_  'a :: {linorder_topology, ordered_comm_monoid_add, topological_comm_monoid_add,
                          conditionally_complete_linorder}"
  assumes f: "x. x  A  (f has_sum g x) (B x)"
  assumes g: "g summable_on A"
  assumes f_nonneg: "x y. x  A  y  B x  f y  (0 :: 'a)"
  assumes disj: "disjoint_family_on B A"
  shows   "f summable_on (xA. B x)"
proof -
  have "f  snd summable_on Sigma A B"
    using assms by (intro summable_on_SigmaI[where g = g]) auto
  also have "?this  f summable_on (snd ` Sigma A B)" using assms
    by (subst summable_on_reindex; force simp: disjoint_family_on_def inj_on_def)
  also have "snd ` (Sigma A B) = (xA. B x)"
    by force
  finally show ?thesis .
qed

lemma summable_on_SigmaD:
  fixes f :: "'a × 'b  'c :: {topological_comm_monoid_add,t3_space}"
  assumes sum1: "f summable_on (Sigma A B)"
  assumes sum2: "x. x  A  (λy. f (x, y)) summable_on (B x)"
  shows   "(λx. infsum (λy. f (x, y)) (B x)) summable_on A"
  using assms unfolding summable_on_def
  by (smt (verit, del_insts) assms has_sum_SigmaD has_sum_cong has_sum_infsum)

lemma summable_on_UnionD:
  fixes f :: "'a  'c :: {topological_comm_monoid_add,t3_space}"
  assumes sum1: "f summable_on (xA. B x)"
  assumes sum2: "x. x  A  f summable_on (B x)"
  assumes disj: "disjoint_family_on B A"
  shows   "(λx. infsum f (B x)) summable_on A"
proof -
  have "(xA. B x) = snd ` Sigma A B"
    by (force simp: Sigma_def)
  with sum1 have "f summable_on (snd ` Sigma A B)"
    by simp
  also have "?this  (f  snd) summable_on (Sigma A B)"
    using disj by (intro summable_on_reindex inj_onI) (force simp: disjoint_family_on_def)
  finally show "(λx. infsum f (B x)) summable_on A"
    using summable_on_SigmaD[of "f  snd" A B] sum2 by simp
qed

lemma summable_on_Union_iff:
  fixes f :: "_  'a :: {linorder_topology, ordered_comm_monoid_add, topological_comm_monoid_add,
                          conditionally_complete_linorder, t3_space}"
  assumes f: "x. x  A  (f has_sum g x) (B x)"
  assumes f_nonneg: "x y. x  A  y  B x  f y  0"
  assumes disj: "disjoint_family_on B A"
  shows   "f summable_on (xA. B x)  g summable_on A"
proof
  assume "g summable_on A"
  thus "f summable_on (xA. B x)"
    using summable_on_UnionI[of A f B g] assms by auto
next
  assume "f summable_on (xA. B x)"
  hence "(λx. infsum f (B x)) summable_on A"
    using assms by (intro summable_on_UnionD) (auto dest: has_sum_imp_summable)
  also have "?this  g summable_on A"
    using assms by (intro summable_on_cong) (auto simp: infsumI)
  finally show "g summable_on A" .
qed

lemma has_sum_Sigma':
  fixes A :: "'a set" and B :: "'a  'b set"
    and f :: 'a × 'b  'c::{comm_monoid_add,uniform_space,uniform_topological_group_add}
  assumes summableAB: "(f has_sum a) (Sigma A B)"
  assumes summableB: x. xA  ((λy. f (x, y)) has_sum (b x)) (B x)
  shows "(b has_sum a) A"
  by (intro has_sum_Sigma[OF _ assms] uniformly_continuous_add)

lemma abs_summable_on_comparison_test':
  assumes "g summable_on A"
  assumes "x. x  A  norm (f x)  g x"
  shows   "(λx. norm (f x)) summable_on A"
proof (rule Infinite_Sum.abs_summable_on_comparison_test)
  have "g summable_on A  (λx. norm (g x)) summable_on A"
    by (metis summable_on_iff_abs_summable_on_real)
  with assms show "(λx. norm (g x)) summable_on A" by blast
qed (use assms in fastforce)

lemma has_sum_geometric_from_1:
  fixes z :: "'a :: {real_normed_field, banach}"
  assumes "norm z < 1"
  shows   "((λn. z ^ n) has_sum (z / (1 - z))) {1..}"
proof -
  have [simp]: "z  1"
    using assms by auto
  have "(λn. z ^ Suc n) sums (1 / (1 - z) - 1)"
    using geometric_sums[of z] assms by (subst sums_Suc_iff) auto
  also have "1 / (1 - z) - 1 = z / (1 - z)"
    by (auto simp: field_simps)
  finally have "(λn. z ^ Suc n) sums (z / (1 - z))" .
  moreover have "summable (λn. norm (z ^ Suc n))"
    using assms
    by (subst summable_Suc_iff) (auto simp: norm_power intro!: summable_geometric)
  ultimately have "((λn. z ^ Suc n) has_sum (z / (1 - z))) UNIV"
    by (intro norm_summable_imp_has_sum)
  also have "?this  ?thesis"
    by (intro has_sum_reindex_bij_witness[of _ "λn. n-1" "λn. n+1"]) auto
  finally show ?thesis .
qed 

lemma has_sum_divide_const:
  fixes f :: "'a  'b :: {topological_semigroup_mult, field, semiring_0}"
  shows "(f has_sum S) A  ((λx. f x / c) has_sum (S / c)) A"
  using has_sum_cmult_right[of f A S "inverse c"] by (simp add: field_simps)

lemma has_sum_uminusI:
  fixes f :: "'a  'b :: {topological_semigroup_mult, ring_1}"
  shows "(f has_sum S) A  ((λx. -f x) has_sum (-S)) A"
  using has_sum_cmult_right[of f A S "-1"] by simp

end