Theory Dirichlet_Series

(*
    File:      Dirichlet_Series.thy
    Author:    Manuel Eberl, TU München
*)
section ‹Formal Dirichlet series›
theory Dirichlet_Series
imports 
  Complex_Main
  Dirichlet_Product
  Multiplicative_Function
  "HOL-Computational_Algebra.Computational_Algebra"
  "HOL-Number_Theory.Number_Theory"
  "HOL-Library.FuncSet"
begin

text ‹
  A formal Dirichlet series
    \[A(s) = \sum_{n=1}^\infty \frac{a_n}{n^s}\]
  is represented its coefficient sequence starting from 1. For simplicity, we represent this
  in Isabelle with a function of type @{typ "nat  'a"} whose value for $n$ is the $n+1$-th 
  coefficient.
›  
typedef 'a fds = "UNIV :: (nat  'a) set"
  by simp

setup_lifting type_definition_fds

lift_definition fds_nth :: "'a fds  nat  'a :: zero" is
  "λf::nat  'a. case_nat 0 f" .
    
lift_definition fds :: "(nat  'a)  'a fds" is
  "λf. f  Suc" .
    
lemma fds_nth_fds: "fds_nth (fds f) n = (if n = 0 then 0 else f n)"
  by transfer (simp split: nat.splits)
    
lemma fds_nth_fds': "f 0 = 0  fds_nth (fds f) = f"
  by (simp add: fun_eq_iff fds_nth_fds)
    
lemma fds_nth_0 [simp]: "fds_nth f 0 = 0"
  by transfer simp
    
lemma fds_nth_fds_pos [simp]: "n > 0  fds_nth (fds f) n = f n"
  by transfer (simp split: nat.splits)
    
lemma fds_fds_nth [simp]: "fds (fds_nth f) = f"
  by transfer (simp add: fun_eq_iff split: nat.splits)
    
lemma fds_eq_fds_iff:
  "fds f = fds g  (n>0. f n = g n)"
proof transfer
  fix f g :: "nat  'a"
  have "(f  Suc = g  Suc)  (n. f (Suc n) = g (Suc n))" by (auto simp: fun_eq_iff)
  also have "  (n>0. f n = g n)"
  proof safe
    fix n :: nat assume "n. f (Suc n) = g (Suc n)" "n > 0"
    thus "f n = g n" by (cases n) auto
  qed auto
  finally show "(f  Suc = g  Suc) = (n>0. f n = g n)" .
qed

lemma fds_eq_fds_iff': "f 0 = g 0  fds f = fds g  f = g"
proof safe
  assume "f 0 = g 0" "fds f = fds g"
  hence "f n = g n" for n by (cases n) (auto simp: fds_eq_fds_iff)
  thus "f = g" by (simp add: fun_eq_iff)
qed

lemma fds_eqI [intro?]:
  assumes "(n. n > 0  fds_nth f n = fds_nth g n)"
  shows   "f = g"
proof -
  from assms have "fds_nth f n = fds_nth g n" if "n > 0" for n 
    by (cases n) (simp_all add: fun_eq_iff)
  hence "fds (fds_nth f) = fds (fds_nth g)" by (subst fds_eq_fds_iff) auto
  thus ?thesis by simp
qed
  
lemma fds_cong [cong]: "(n. n > 0  f n = (g n :: 'a :: zero))  fds f = fds g"
  by (rule fds_eqI) simp

lemma fds_eq_iff: "f = g  (n>0. fds_nth f n = fds_nth g n)"
  by (auto intro: fds_eqI)

lemma dirichlet_prod_fds_nth_fds_left [simp]:
  "dirichlet_prod (fds_nth (fds f)) g = dirichlet_prod f g"
  by (simp add: fds_nth_fds)
  
lemma dirichlet_prod_fds_nth_fds_right [simp]:
  "dirichlet_prod f (fds_nth (fds g)) = dirichlet_prod f g"
  by (simp add: fds_nth_fds)


definition fds_const :: "'a :: zero  'a fds" where
  "fds_const c = fds (λn. if n = 1 then c else 0)"
  
abbreviation fds_ind where "fds_ind P  fds (ind P)"


bundle fds_syntax
begin
  
notation fds_nth (infixl "$" 75)
notation fds (binder "χ" 10)
notation dirichlet_prod (infixl "" 70)
 
end

instantiation fds :: (zero) zero
begin
definition zero_fds :: "'a fds" where "zero_fds = fds (λ_. 0)"
instance ..
end

instantiation fds :: ("{zero,one}") one
begin
definition one_fds :: "'a fds" where "one_fds = fds (λn. if n = 1 then 1 else 0)"
instance ..
end

instantiation fds :: ("{plus,zero}") plus
begin
definition plus_fds :: "'a fds  'a fds  'a fds" 
  where "plus_fds f g = fds (λn. fds_nth f n + fds_nth g n)"
instance ..
end

instantiation fds :: (semiring_0) times
begin
definition times_fds :: "'a fds  'a fds  'a fds" 
  where "times_fds f g = fds (dirichlet_prod (fds_nth f) (fds_nth g))"
instance ..
end
  
instantiation fds :: ("{uminus,zero}") uminus
begin
definition uminus_fds :: "'a fds  'a fds"
  where "uminus_fds f = fds (λn. -fds_nth f n)"
instance ..
end
  
instantiation fds :: ("{minus,zero}") minus
begin
definition minus_fds :: "'a fds  'a fds  'a fds"
  where "minus_fds f g = fds (λn. fds_nth f n - fds_nth g n)"
instance ..
end


subsection ‹General properties›
  
lemma fds_nth_zero [simp]: "fds_nth 0 = (λ_. 0)"
  by (simp add: zero_fds_def fds_nth_fds fun_eq_iff)  

lemma fds_nth_one: "fds_nth 1 = (λn. if n = 1 then 1 else 0)"
  by (simp add: one_fds_def fds_nth_fds fun_eq_iff)

lemma fds_nth_one_Suc_0 [simp]: "fds_nth 1 (Suc 0) = 1"
  by (simp add: fds_nth_one)
    
lemma fds_nth_one_not_Suc_0 [simp]: "n  Suc 0  fds_nth 1 n = 0"
  by (simp add: fds_nth_one)
    
lemma fds_nth_plus [simp]: 
  "fds_nth (f + g) = (λn. fds_nth f n + fds_nth g n :: 'a :: monoid_add)"
  by (simp add: plus_fds_def fds_nth_fds fun_eq_iff)

lemma fds_nth_minus [simp]: 
  "fds_nth (f - g) = (λn. fds_nth f n - fds_nth g n :: 'a :: {cancel_comm_monoid_add})"
  by (simp add: minus_fds_def fds_nth_fds fun_eq_iff)

lemma fds_nth_uminus [simp]: "fds_nth (-g) = (λn. - fds_nth g n :: 'a :: group_add)"
  by (simp add: uminus_fds_def fds_nth_fds fun_eq_iff)

lemma fds_nth_mult: "fds_nth (f * g) = dirichlet_prod (fds_nth f) (fds_nth g)"
  by (simp add: times_fds_def fds_nth_fds dirichlet_prod_def fun_eq_iff)

lemma fds_nth_mult_const_left [simp]: "fds_nth (fds_const c * f) n = c * fds_nth f n"
  by (cases "n = 0") (simp_all add: fds_nth_mult fds_const_def)

lemma fds_nth_mult_const_right [simp]: "fds_nth (f * fds_const c) n = fds_nth f n * c"
  by (cases "n = 0") (simp_all add: fds_nth_mult fds_const_def)


instance fds :: ("{semigroup_add, zero}") semigroup_add
  by standard (simp_all add: fds_eq_iff algebra_simps plus_fds_def)

instance fds :: ("{ab_semigroup_add, zero}") ab_semigroup_add
  by standard (simp_all add: fds_eq_iff algebra_simps plus_fds_def)

instance fds :: ("{cancel_semigroup_add, zero}") cancel_semigroup_add
  by standard (simp_all add: fds_eq_iff algebra_simps plus_fds_def)
    
instance fds :: ("{cancel_ab_semigroup_add, zero}") cancel_ab_semigroup_add
  by standard (simp_all add: fds_eq_iff algebra_simps plus_fds_def minus_fds_def)
  
instance fds :: (monoid_add) monoid_add
  by standard (simp_all add: fds_eq_iff algebra_simps)

instance fds :: (comm_monoid_add) comm_monoid_add
  by standard (simp_all add: fds_eq_iff algebra_simps)

instance fds :: (cancel_comm_monoid_add) cancel_comm_monoid_add
  by standard (simp_all add: fds_eq_iff algebra_simps)

instance fds :: (group_add) group_add
  by standard (simp_all add: fds_eq_iff algebra_simps minus_fds_def)

instance fds :: (ab_group_add) ab_group_add
  by standard (simp_all add: fds_eq_iff algebra_simps)

instance fds :: (semiring_0) semiring_0
proof
  fix f g h :: "'a fds"
  show "(f + g) * h = f * h + g * h"
    by (simp add: fds_eq_iff fds_nth_mult dirichlet_prod_def algebra_simps sum.distrib)
next
  fix f g h :: "'a fds"
  show "f * g * h = f * (g * h)" 
    by (intro fds_eqI) (simp add: fds_nth_mult dirichlet_prod_assoc)
qed (simp_all add: fds_eq_iff fds_nth_mult dirichlet_prod_def algebra_simps sum.distrib)
  
instance fds :: (comm_semiring_0) comm_semiring_0
proof
  fix f g :: "'a fds"
  show "f * g = g * f"
    by (simp add: fds_eq_iff fds_nth_mult dirichlet_prod_commutes)
qed (simp_all add: fds_eq_iff fds_nth_mult dirichlet_prod_def algebra_simps sum.distrib)

instance fds :: (semiring_0_cancel) semiring_0_cancel
  by standard (simp_all add: fds_eq_iff fds_nth_one fds_nth_mult)

instance fds :: (comm_semiring_0_cancel) comm_semiring_0_cancel ..

instance fds :: (semiring_1) semiring_1
  by standard (simp_all add: fds_eq_iff fds_nth_one fds_nth_mult)
    
instance fds :: (comm_semiring_1) comm_semiring_1
  by standard (simp_all add: fds_eq_iff fds_nth_one fds_nth_mult)

instance fds :: (semiring_1_cancel) semiring_1_cancel .. 
instance fds :: (ring) ring ..
instance fds :: (ring_1) ring_1 ..
instance fds :: (comm_ring) comm_ring ..

instance fds :: (semiring_no_zero_divisors) semiring_no_zero_divisors
proof
  fix f g :: "'a fds"
  assume "f  0" "g  0"
  hence ex: "m>0. fds_nth f m  0" "n>0. fds_nth g n  0"
    by (auto simp: fds_eq_iff)
  define m where "m = (LEAST m. m > 0  fds_nth f m  0)"
  define n where "n = (LEAST n. n > 0  fds_nth g n  0)"
  from ex[THEN LeastI_ex, folded m_def n_def]
    have mn: "m > 0" "fds_nth f m  0" "n > 0" "fds_nth g n  0" by auto

  have *: "m  m'" if "m' > 0" "fds_nth f m'  0" for m' 
    using conjI[OF that] unfolding m_def by (rule Least_le)
  have m': "fds_nth f m' = 0" if "m'  {0<..<m}"  for m' using that *[of m'] by auto
      
  have *: "n  n'" if "n' > 0" "fds_nth g n'  0" for n' 
    using conjI[OF that] unfolding n_def by (rule Least_le)
  have n': "fds_nth g n' = 0" if "n'  {0<..<n}"  for n' using that *[of n'] by auto
    
  have "fds_nth (f * g) (m * n) = 
          (d | d dvd m * n. fds_nth f d * fds_nth g (m * n div d))"
    by (simp add: fds_nth_mult dirichlet_prod_def)
  also have " = (d | d dvd m * n. if d = m then fds_nth f m * fds_nth g n else 0)"
  proof (intro sum.cong refl, goal_cases)
    case (1 d)
    thus ?case
    proof (cases "d  m")
      case True
      with mn(1,3) 1 show ?thesis by (auto elim!: dvdE simp: m' n' split: if_splits)
    next
      case False
      from 1 obtain k where k: "m * n = d * k" by (auto elim!: dvdE)
      with mn(1,3) have [simp]: "k > 0" by (auto intro!: Nat.gr0I)
      from False mn(3) have "m * n < d * n" by (intro mult_strict_right_mono) auto
      also note k
      finally have "k < n" by (subst (asm) mult_less_cancel1) auto
      with mn(1,3) and 1 and False show ?thesis
        by (auto simp: k m' n' split: if_splits)
    qed
  qed
  also have " = fds_nth f m * fds_nth g n" using mn(1,3) by (subst sum.delta) auto
  also have "  0" using mn by auto
  finally show "f * g  0" by auto
qed

(* TODO: instance fds :: (semiring_no_zero_divisors_cancel) semiring_no_zero_divisors_cancel
   Maybe using Bell series and cancellation on FPSs *) 

instance fds :: (ring_no_zero_divisors) ring_no_zero_divisors ..
instance fds :: (idom) idom ..

instantiation fds :: (real_vector) real_vector
begin

definition scaleR_fds :: "real  'a fds  'a fds" where
  "scaleR_fds c f = fds (λn. c *R fds_nth f n)"
  
lemma fds_nth_scaleR [simp]: "fds_nth (c *R f) = (λn. c *R fds_nth f n)"
  by (simp add: scaleR_fds_def fun_eq_iff fds_nth_fds)

instance by standard (simp_all add: fds_eq_iff algebra_simps)

end
  
instance fds :: (real_algebra) real_algebra
  by standard (simp_all add: fds_eq_iff algebra_simps fds_nth_mult
                             dirichlet_prod_def scaleR_sum_right)

instance fds :: (real_algebra_1) real_algebra_1 ..

lemma fds_nth_sum [simp]: "fds_nth (sum f A) n = sum (λx. fds_nth (f x) n) A"
  by (induction A rule: infinite_finite_induct) auto

lemma sum_fds [simp]: "(xA. fds (f x)) = fds (λn. xA. f x n)"
  by (rule fds_eqI) simp_all

lemma fds_nth_const: "fds_nth (fds_const c) = (λn. if n = 1 then c else 0)"
  by (simp add: fds_const_def fds_nth_fds fun_eq_iff)
    
lemma fds_nth_const_Suc_0 [simp]: "fds_nth (fds_const c) (Suc 0) = c"
  by (simp add: fds_nth_const)
    
lemma fds_nth_const_not_Suc_0 [simp]: "n  1  fds_nth (fds_const c) n = 0"
  by (simp add: fds_nth_const)

lemma fds_const_zero [simp]: "fds_const 0 = 0"
  by (simp add: fds_eq_iff fds_nth_const)

lemma fds_const_one [simp]: "fds_const 1 = 1"
  by (simp add: fds_eq_iff fds_nth_const fds_nth_one)

lemma fds_const_add [simp]: "fds_const (a + b :: 'a :: monoid_add) = fds_const a + fds_const b"
  by (simp add: fds_eq_iff fds_nth_const)
    
lemma fds_const_minus [simp]: 
  "fds_const (a - b :: 'a :: cancel_comm_monoid_add) = fds_const a - fds_const b"
  by (simp add: fds_eq_iff fds_nth_const)
    
lemma fds_const_uminus [simp]: 
  "fds_const (- b :: 'a :: ab_group_add) = - fds_const b"
  by (simp add: fds_eq_iff fds_nth_const)
    
lemma fds_const_mult [simp]: 
  "fds_const (a * b :: 'a :: semiring_0) = fds_const a * fds_const b"
  by (simp add: fds_eq_iff fds_nth_const fds_nth_mult)
    
lemma fds_const_of_nat [simp]: "fds_const (of_nat c) = of_nat c"
  by (induction c) (simp_all)

lemma fds_const_of_int [simp]: "fds_const (of_int c) = of_int c"
  by (cases c) simp_all

lemma fds_const_of_real [simp]: "fds_const (of_real c) = of_real c"
  by (simp add: of_real_def fds_eq_iff fds_const_def fds_nth_one)


instantiation fds :: ("{inverse, comm_ring_1}") inverse
begin

definition inverse_fds :: "'a fds  'a fds" where
  "inverse_fds f = fds (λn. dirichlet_inverse (fds_nth f) (inverse (fds_nth f 1)) n)"

definition divide_fds :: "'a fds  'a fds  'a fds" where
  "divide_fds f g = f * inverse g"

instance ..

end

lemma numeral_fds: "numeral n = fds_const (numeral n)"
proof -
  have "numeral n = (of_nat (numeral n) :: 'a fds)" by simp
  also have " = fds_const (of_nat (numeral n))" by (rule fds_const_of_nat [symmetric])
  also have "of_nat (numeral n) = (numeral n :: 'a)" by simp
  finally show ?thesis .
qed

lemma fds_ind_False [simp]: "fds_ind (λ_. False) = 0"
  by (rule fds_eqI) simp

lemma fds_commutes: 
  assumes "m n. m > 0  n > 0  fds_nth f m * fds_nth g n = fds_nth g n * fds_nth f m"
  shows   "f * g = g * f"
  by (intro fds_eqI, unfold fds_nth_mult, subst dirichlet_prod_def, 
      subst dirichlet_prod_altdef1, intro sum.cong refl assms) (auto elim: dvdE)

lemma fds_nth_mult_Suc_0 [simp]: 
  "fds_nth (f * g) (Suc 0) = fds_nth f (Suc 0) * fds_nth g (Suc 0)"
  by (simp add: fds_nth_mult)
  
lemma fds_nth_inverse: 
  "fds_nth (inverse f) = dirichlet_inverse (fds_nth f) (inverse (fds_nth f 1))"
  by (simp add: inverse_fds_def fds_nth_fds fun_eq_iff)

lemma inverse_fds_nonunit:
  "fds_nth f 1 = (0 :: 'a :: field)  inverse f = 0"
  by (auto simp: fds_eq_iff fds_nth_inverse dirichlet_inverse_noninvertible)

lemma inverse_0_fds [simp]: "inverse (0 :: 'a :: field fds) = 0"
  by (simp add: inverse_fds_def fds_eq_iff dirichlet_inverse.simps)

lemma fds_left_inverse: 
  "fds_nth f 1  (0 :: 'a :: field)  inverse f * f = 1"
  by (auto simp: fds_eq_iff fds_nth_mult fds_nth_inverse dirichlet_prod_inverse' fds_nth_one)

lemma fds_right_inverse: 
  "fds_nth f 1  (0 :: 'a :: field)  f * inverse f = 1"
  by (auto simp: fds_eq_iff fds_nth_mult fds_nth_inverse dirichlet_prod_inverse fds_nth_one)
    
lemma fds_left_inverse_unique:
  assumes "f * g = (1 :: 'a :: field fds)"
  shows   "f = inverse g"
proof -
  have "fds_nth (f * g) 1 = 1" by (subst assms) simp
  hence "fds_nth g 1  0" by auto
  hence "(f - inverse g) * g = 0" 
    unfolding ring_distribs by (subst fds_left_inverse) (simp_all add: assms)
  moreover from assms have "g  0" by auto
  ultimately show "f = inverse g" by simp
qed
  
lemma fds_right_inverse_unique:
  assumes "f * g = (1 :: 'a :: field fds)"
  shows   "g = inverse f"
  using fds_left_inverse_unique[of g f] assms by (simp add: mult.commute)

lemma inverse_1_fds [simp]: "inverse (1 :: 'a :: field fds) = 1"
  by (rule fds_left_inverse_unique [symmetric]) simp

lemma inverse_const_fds [simp]: 
  "inverse (fds_const c :: 'a :: field fds) = fds_const (inverse c)"
proof (cases "c = 0")
  case False
  thus ?thesis 
    by (intro fds_right_inverse_unique[symmetric])
       (auto simp del: fds_const_mult simp: fds_const_mult [symmetric])
qed auto

lemma inverse_mult_fds: "inverse (f * g :: 'a :: field fds) = inverse f * inverse g"
proof (cases "fds_nth (f * g) (Suc 0) = 0")
  case False
  hence "(f * inverse f) * (g * inverse g) = 1" by (subst (1 2) fds_right_inverse) auto
  thus ?thesis by (intro fds_right_inverse_unique [symmetric]) (simp_all add: mult_ac)
qed (auto simp: inverse_fds_nonunit)


definition fds_zeta :: "'a :: one fds" 
  where "fds_zeta = fds (λ_. 1)"
    
lemma fds_zeta_altdef: "fds_zeta = fds (λn. if n = 0 then 0 else 1)"
  by (rule fds_eqI) (simp add: fds_zeta_def)
    
lemma fds_nth_zeta: "fds_nth fds_zeta = (λn. if n = 0 then 0 else 1)"
  by (simp add: fds_zeta_def fun_eq_iff)

lemma fds_nth_zeta_pos [simp]: "n > 0  fds_nth fds_zeta n = 1"
  by (simp add: fds_nth_zeta) 

lemma fds_zeta_commutes: "fds_zeta * (f :: 'a :: semiring_1 fds) = f * fds_zeta"
  by (intro fds_commutes) simp_all

lemma fds_ind_True [simp]: "fds_ind (λ_. True) = fds_zeta"
  by (rule fds_eqI) simp

lemma finite_extensional_prod_nat: 
  assumes "finite A" "b > 0"
  shows   "finite {d  extensional A. prod d A = (b :: nat)}"
proof (rule finite_subset)
  from assms(1) show "finite (PiE A (λ_. {..b}))" by (rule finite_PiE) auto
  {
    fix d :: "'a  nat" and x :: 'a assume *: "x  A" "prod d A = b"
    with prod_dvd_prod_subset[of A "{x}" d] assms have "d x dvd b" by auto
    with assms have "d x  b" by (auto dest: dvd_imp_le)
  }
  thus "{d  extensional A. prod d A = (b :: nat)}  "
    by (auto simp: extensional_def)
qed

text ‹
  The $n$-th coefficient of a product of Dirichlet series can be determined by 
  summing over all products of $k_i$-th coefficients of the series such that the 
  product of the $k_i$ is $n$.
›
lemma fds_nth_prod:
  assumes "finite A" "A  {}" "n > 0"
  shows   "fds_nth (xA. f x) n = 
             (d | d  extensional A  prod d A = n. xA. fds_nth (f x) (d x))"
using assms
proof (induction arbitrary: n rule: finite_ne_induct)
  case (singleton x n)
  have "{d  extensional {x}. d x = n} = {λy. if y = x then n else undefined}"
    by (auto simp: extensional_def)
  thus ?case by simp
next
  case (insert x A n)
  let ?f = "λd. ((d x, n div d x), d(x := undefined))"
  let ?g = "λ(z,d). d(x := fst z)"
  from insert have "fds_nth (xinsert x A. f x) n = 
           (z | fst z * snd z = n. d | d  extensional A  prod d A = snd z. 
              fds_nth (f x) (fst z) * (xA. fds_nth (f x) (d x)))"
    by (simp add: fds_nth_mult dirichlet_prod_altdef2 sum_distrib_left case_prod_unfold)
  also have " = ((z,d)(SIGMA x:{z. fst z * snd z = n}. {d  extensional A. prod d A = snd x}).
                      fds_nth (f x) (fst z) * (xA. fds_nth (f x) (d x)))"
    using finite_divisors_nat'[of n] and insert.hyps and n > 0
    by (intro sum.Sigma finite_extensional_prod_nat ballI)  (auto simp: case_prod_unfold)
  also have " = (d | d  extensional (insert x A)  prod d (insert x A) = n.
                      (xinsert x A. fds_nth (f x) (d x)))"
  proof (rule sum.reindex_bij_witness [of _ ?f ?g], goal_cases)
    case (1 z)
    thus ?case using insert.hyps insert.prems by (auto simp: extensional_def)
  next
    case (2 z)
    thus ?case using insert.hyps insert.prems 
      by (auto simp: extensional_def sum.delta intro!: prod.cong)
  next
    case (4 z)
    thus ?case using insert.hyps insert.prems by (auto  intro!: prod.cong)
  next
    case (5 z)
    with insert.hyps insert.prems 
      have "(xaA. fds_nth (f xa) (if xa = x then fst (fst z) else snd z xa)) =
              (xA. fds_nth (f x) (snd z x))" by (intro prod.cong) auto
    with 5 insert.hyps insert.prems show ?case by (simp add: case_prod_unfold)
  qed auto
  finally show ?case .
qed

lemma fds_nth_power_Suc_0 [simp]: "fds_nth (f ^ n) (Suc 0) = fds_nth f (Suc 0) ^ n"
  by (induction n) simp_all

lemma fds_nth_prod_Suc_0 [simp]: "fds_nth (prod f A) (Suc 0) = (xA. fds_nth (f x) (Suc 0))"
  by (induction A rule: infinite_finite_induct) simp_all

lemma fds_nth_power_eq_0:
  assumes "n < 2 ^ k" "fds_nth f 1 = 0"
  shows   "fds_nth (f ^ k) n = 0"
  using assms(1)
proof (induction k arbitrary: n)
  case 0
  thus ?case by (simp add: one_fds_def)
next
  case (Suc k n)
  have "fds_nth (f ^ Suc k) n = dirichlet_prod (fds_nth (f ^ k)) (fds_nth f) n"
    by (subst power_Suc2) (simp add: fds_nth_mult dirichlet_prod_commutes)
  also have " = 0" unfolding dirichlet_prod_def
  proof (intro sum.neutral ballI)
    fix d assume d: "d  {d. d dvd n}"
    show "fds_nth (f ^ k) d * fds_nth f (n div d) = 0"
    proof (cases "d < 2 ^ k")
      case True
      thus ?thesis using Suc.IH[of d] by simp
    next
      case False
      hence "(n div d) * 2 ^ k  (n div d) * d" by (intro mult_left_mono) auto
      also from d have "(n div d) * d = n" by simp
      also from Suc have "n < 2 * 2 ^ k" by simp
      finally have "n div d  1" by simp
      with assms(2) show ?thesis by (cases "n div d") simp_all
    qed
  qed
  finally show ?case .
qed


subsection ‹Shifting the argument›

class nat_power = semiring_1 +
  fixes nat_power :: "nat  'a  'a"
  assumes nat_power_0_left [simp]:  "x  0  nat_power 0 x = 0"
  assumes nat_power_0_right [simp]: "n > 0  nat_power n 0 = 1"
  assumes nat_power_1_left [simp]:  "nat_power (Suc 0) x = 1"
  assumes nat_power_1_right [simp]: "nat_power n 1 = of_nat n"
  assumes nat_power_add:            "n > 0  nat_power n (a + b) = nat_power n a * nat_power n b"
  assumes nat_power_mult_distrib:   
    "m > 0  n > 0  nat_power (m * n) a = nat_power m a * nat_power n a"
  assumes nat_power_power:
    "n > 0  nat_power n (a * of_nat m) = nat_power n a ^ m"
begin

lemma nat_power_of_nat [simp]: "m > 0  nat_power m (of_nat n) = of_nat (m ^ n)"
  by (induction n) (simp_all add: nat_power_add)

lemma nat_power_power_left: "m > 0  nat_power (m ^ k) n = nat_power m n ^ k"
  by (induction k) (simp_all add: nat_power_mult_distrib)

end

class nat_power_field = nat_power + field +
  assumes nat_power_nonzero [simp]: "n > 0  nat_power n z  0"
begin

lemma nat_power_diff: "n > 0  nat_power n (a - b) = nat_power n a / nat_power n b"  
  using nat_power_add[of n "a - b" b] by (simp add: divide_simps)

end

instantiation nat :: nat_power
begin
definition [simp]: "nat_power_nat a b = (a ^ b :: nat)"
instance by standard (simp_all add: power_add power_mult_distrib power_mult)
end

instantiation real :: nat_power_field
begin
definition [simp]: "nat_power_real a b = (real a powr b)"
instance proof
  fix n m :: nat and a :: real assume "n > 0"
  thus "nat_power n (a * real m) = nat_power n a ^ m"
    by (simp add: powr_def exp_of_nat_mult [symmetric])
qed (simp_all add: powr_add powr_mult)
end

text ‹
  The following operation corresponds to shifting the argument of a Dirichlet series, i.\,e.\ 
  subtracting a constant from it. In effect, this turns the series
    \[A(s) = \sum_{n=1}^\infty \frac{a_n}{n^s}\]
  into the series
    \[A(s - c) = \sum_{n=1}^\infty \frac{n^c \cdot a_n}{n^s}\ .\]
›
definition fds_shift :: "'a :: nat_power  'a fds  'a fds" where
  "fds_shift c f = fds (λn. fds_nth f n * nat_power n c)"

lemma fds_nth_shift [simp]: "fds_nth (fds_shift c f) n = fds_nth f n * nat_power n c"
  by (simp add: fds_shift_def fds_nth_fds)

lemma fds_shift_shift [simp]: "fds_shift c (fds_shift c' f) = fds_shift (c' + c) f"
  by (rule fds_eqI) (simp add: nat_power_add mult_ac)

lemma fds_shift_zero [simp]: "fds_shift c 0 = 0"
  by (rule fds_eqI) simp

lemma fds_shift_1 [simp]: "fds_shift a 1 = 1"
  by (rule fds_eqI) (simp add: fds_shift_def one_fds_def)

lemma fds_shift_const [simp]: "fds_shift a (fds_const c) = fds_const c"
  by (rule fds_eqI) (simp add: fds_shift_def fds_const_def)

lemma fds_shift_add [simp]: 
  fixes f g :: "'a :: {monoid_add, nat_power} fds"
  shows "fds_shift c (f + g) = fds_shift c f + fds_shift c g"
  by (rule fds_eqI) (simp add: algebra_simps)

lemma fds_shift_minus [simp]: 
  fixes f g :: "'a :: {comm_semiring_1_cancel, nat_power} fds"
  shows "fds_shift c (f - g) = fds_shift c f - fds_shift c g"
  by (rule fds_eqI) (simp add: algebra_simps)    

lemma fds_shift_uminus [simp]: 
  fixes f :: "'a :: {ring, nat_power} fds"
  shows "fds_shift c (-f) = -fds_shift c f"
  by (rule fds_eqI) (simp add: algebra_simps)

lemma fds_shift_mult [simp]:
  fixes f g :: "'a :: {comm_semiring, nat_power} fds"
  shows "fds_shift c (f * g) = fds_shift c f * fds_shift c g"
  by (rule fds_eqI) 
     (auto simp: algebra_simps fds_nth_mult dirichlet_prod_altdef2 
        sum_distrib_left sum_distrib_right nat_power_mult_distrib intro!: sum.cong)

lemma fds_shift_power [simp]:
  fixes f :: "'a :: {comm_semiring, nat_power} fds"
  shows "fds_shift c (f ^ n) = fds_shift c f ^ n"
  by (induction n) simp_all

lemma fds_shift_by_0 [simp]: "fds_shift 0 f = f"
  by (simp add: fds_shift_def)

lemma fds_shift_inverse [simp]: 
  "fds_shift (a :: 'a :: {field, nat_power}) (inverse f) = inverse (fds_shift a f)"
proof (cases "fds_nth f 1 = 0")
  case False
  have "fds_shift a f * fds_shift a (inverse f) = fds_shift a (f * inverse f)" 
    by simp
  also from False have "f * inverse f = 1" by (intro fds_right_inverse)
  finally have "fds_shift a f * fds_shift a (inverse f) = 1" by simp
  thus ?thesis by (rule fds_right_inverse_unique)
qed (auto simp: inverse_fds_nonunit)

lemma fds_shift_divide [simp]: 
  "fds_shift (a :: 'a :: {field, nat_power}) (f / g) = fds_shift a f / fds_shift a g"
  by (simp add: divide_fds_def)

lemma fds_shift_sum [simp]: "fds_shift a (xA. f x) = (xA. fds_shift a (f x))"
  by (induction A rule: infinite_finite_induct) simp_all

lemma fds_shift_prod [simp]: "fds_shift a (xA. f x) = (xA. fds_shift a (f x))"
  by (induction A rule: infinite_finite_induct) simp_all


subsection ‹Scaling the argument›

text ‹
  The following operation corresponds to scaling the argument of a Dirichlet series with 
  a natural number, i.\,e.\ turning the series
    \[A(s) = \sum_{n=1}^\infty \frac{a_n}{n^s}\]
  into the series
    \[A(ks) = \sum_{n=1}^\infty \frac{a_n}{\left(n^k\right)^2}\ .\]
›
definition fds_scale :: "nat  ('a :: zero) fds  'a fds" where
  "fds_scale c f =
     fds (λn. if n > 0  is_nth_power c n then fds_nth f (nth_root_nat c n) else 0)"

lemma fds_scale_0 [simp]: "fds_scale 0 f = 0"
  by (auto simp: fds_scale_def fds_eq_iff)  

lemma fds_scale_1 [simp]: "fds_scale 1 f = f"
  by (auto simp: fds_scale_def fds_eq_iff)
    
lemma fds_nth_scale_power [simp]:
  "c > 0  fds_nth (fds_scale c f) (n ^ c) = fds_nth f n"
  by (simp add: fds_scale_def fds_nth_fds)
    
lemma fds_nth_scale_nonpower [simp]:
  "¬is_nth_power c n   fds_nth (fds_scale c f) n = 0"
  by (simp add: fds_scale_def fds_nth_fds)

lemma fds_nth_scale:
  "fds_nth (fds_scale c f) n = 
     (if n > 0  is_nth_power c n then fds_nth f (nth_root_nat c n) else 0)"
  by (cases "c = 0") (auto simp: is_nth_power_def)

lemma fds_scale_const [simp]: "c > 0  fds_scale c (fds_const c') = fds_const c'"
  by (rule fds_eqI) (auto simp: fds_nth_scale fds_nth_const elim!: is_nth_powerE)

lemma fds_scale_zero [simp]: "fds_scale c 0 = 0"
  by (rule fds_eqI) (simp add: fds_nth_scale)

lemma fds_scale_one [simp]: "c > 0  fds_scale c 1 = 1"
  by (simp only: fds_const_one [symmetric] fds_scale_const)

lemma fds_scale_of_nat [simp]: "c > 0  fds_scale c (of_nat n) = of_nat n"
  by (simp only: fds_const_of_nat [symmetric] fds_scale_const)

lemma fds_scale_of_int [simp]: "c > 0  fds_scale c (of_int n) = of_int n"
  by (simp only: fds_const_of_int [symmetric] fds_scale_const)

lemma fds_scale_numeral [simp]: "c > 0  fds_scale c (numeral n) = numeral n"
  using fds_scale_of_nat[of c "numeral n"] by (simp del: fds_scale_of_nat)

lemma fds_scale_scale: "fds_scale c (fds_scale c' f) = fds_scale (c * c') f"
proof (cases "c = 0  c' = 0")
  case False
  hence cc': "c > 0" "c' > 0" by auto
  show ?thesis
  proof (rule fds_eqI, goal_cases)
    case (1 n)
    show ?case
    proof (cases "is_nth_power (c * c') n")
      case False
      with cc' 1 have "fds_nth (fds_scale c (fds_scale c' f)) n = 0"
        by (auto simp: fds_nth_scale is_nth_power_def power_mult [symmetric] mult.commute)
      with False cc' show ?thesis by simp
    next
      case True
      from True obtain n' where [simp]: "n = n' ^ (c' * c)" 
        by (auto elim: is_nth_powerE simp: mult.commute)
      with cc' have "fds_nth (fds_scale (c * c') f) n = fds_nth f n'"
        by (simp add: mult.commute)
      also have " = fds_nth (fds_scale c (fds_scale c' f)) n"
        using cc' by (simp add: power_mult)
      finally show ?thesis ..
    qed
  qed
qed auto
          
lemma fds_scale_add [simp]: 
  fixes f g :: "'a :: monoid_add fds"
  shows "fds_scale c (f + g) = fds_scale c f + fds_scale c g"
  by (rule fds_eqI) (auto simp: fds_nth_scale)

lemma fds_scale_minus [simp]: 
  fixes f g :: "'a :: {cancel_comm_monoid_add} fds"
  shows "fds_scale c (f - g) = fds_scale c f - fds_scale c g"
  by (rule fds_eqI) (auto simp: fds_nth_scale)

lemma fds_scale_uminus [simp]: 
  fixes f :: "'a :: group_add fds"
  shows "fds_scale c (-f) = -fds_scale c f"
  by (rule fds_eqI) (auto simp: fds_nth_scale)

lemma fds_scale_mult [simp]: 
  fixes f g :: "'a :: semiring_0 fds"
  shows "fds_scale c (f * g) = fds_scale c f * fds_scale c g"
proof (cases "c > 0")
  case True
  show ?thesis
  proof (rule fds_eqI, goal_cases)
    case (1 n)
    show ?case
    proof (cases "is_nth_power c n")
      case False
      have "fds_nth (fds_scale c f * fds_scale c g) n = 
              ((r, d) | r * d = n. fds_nth (fds_scale c f) r * fds_nth (fds_scale c g) d)"
        by (simp add: fds_nth_mult dirichlet_prod_altdef2)
      also from False have " = ((r, d) | r * d = n. 0)"
        by (intro sum.cong refl) (auto simp: fds_nth_scale dest: is_nth_power_mult)
      also from False have " = fds_nth (fds_scale c (f * g)) n" by simp
      finally show ?thesis ..
    next
      case True
      then obtain n' where [simp]: "n = n' ^ c" by (elim is_nth_powerE)
      define h where "h = map_prod (nth_root_nat c) (nth_root_nat c)"
      define i where "i = map_prod (λn::nat. n ^ c) (λn::nat. n ^ c)"
      define A where "A = {(r, d). r * d = n}"
      define S where "S = {rsA. ¬is_nth_power c (fst rs)  ¬is_nth_power c (snd rs)}"

      have "fds_nth (fds_scale c f * fds_scale c g) n = 
              ((r, d) | r * d = n. fds_nth (fds_scale c f) r * fds_nth (fds_scale c g) d)"
        by (simp add: fds_nth_mult dirichlet_prod_altdef2)
      also have " = ((r, d) | r * d = n'. fds_nth f r * fds_nth g d)"
      proof (rule sym, intro sum.reindex_bij_witness_not_neutral[of "{}" S _ h i])
        show "finite S" unfolding S_def A_def
          by (rule finite_subset[OF _ finite_divisors_nat'[of n]]) (insert n > 0, auto)
        show "i (h rd) = rd" if "rd  {(r, d). r * d = n} - S" for rd
          using c > 0 that by (auto elim!: is_nth_powerE simp: S_def i_def h_def A_def)
        show "h rd  {(r,d). r * d = n'} - {}" if "rd  {(r, d). r * d = n} - S" for rd
          using c > 0 that  by (auto elim!: is_nth_powerE 
            simp: S_def i_def h_def A_def power_mult_distrib [symmetric] power_eq_iff_eq_base)
        show "h (i rd) = rd" if "rd  {(r, d). r * d = n'} - {}" for rd
          using that c > 0 by (auto simp: h_def i_def)
        show "i rd  {(r, d). r * d = n} - S" if "rd  {(r,d). r * d = n'} - {}" for rd
          using that c > 0 by (auto simp: i_def S_def power_mult_distrib [symmetric])
        show "(case rd of (r, d)  fds_nth (fds_scale c f) r * fds_nth (fds_scale c g) d) = 0"
          if "rd  S" for rd using that by (auto simp: S_def case_prod_unfold)
      qed (insert c > 0, auto simp: case_prod_unfold i_def)
      also have " = fds_nth (f * g) n'" by (simp add: fds_nth_mult dirichlet_prod_altdef2)
      also from c > 0 have " = fds_nth (fds_scale c (f * g)) n" by simp
      finally show ?thesis ..
    qed
  qed
qed auto

lemma fds_scale_shift: 
  "fds_shift d (fds_scale c f) = fds_scale c (fds_shift (c * d) f)"
proof (cases "c > 0")
  case True
  thus ?thesis
  by (intro fds_eqI) (auto simp: fds_nth_scale power_mult elim!: is_nth_powerE)
qed auto

lemma fds_ind_nth_power: "k > 0  fds_ind (is_nth_power k) = fds_scale k fds_zeta"
  by (rule fds_eqI) (auto simp: ind_def fds_nth_scale elim!: is_nth_powerE)


subsection ‹Formal derivative›

text ‹
  The formal derivative of a series
    \[A(s) = \sum_{n=1}^\infty \frac{a_n}{n^s}\]
  can easily be seen to be
    \[A'(s) = -\sum_{n=1}^\infty \frac{\ln n\cdot a_n}{n^s}\ .\]
›
definition fds_deriv :: "'a :: real_algebra fds  'a fds" where
  "fds_deriv f = fds (λn. - ln (real n) *R fds_nth f n)"

lemma fds_nth_deriv: "fds_nth (fds_deriv f) n = -ln (real n) *R fds_nth f n"
  by (cases "n = 0") (simp_all add: fds_deriv_def)

lemma fds_deriv_const [simp]: "fds_deriv (fds_const c) = 0"
  by (rule fds_eqI) (simp add: fds_nth_deriv fds_nth_const)

lemma fds_deriv_0 [simp]: "fds_deriv 0 = 0"
  by (rule fds_eqI) (simp add: fds_nth_deriv)
    
lemma fds_deriv_1 [simp]: "fds_deriv 1 = 0"
  by (rule fds_eqI) (simp add: fds_nth_deriv fds_nth_one)

lemma fds_deriv_of_nat [simp]: "fds_deriv (of_nat n) = 0"
  by (simp only: fds_const_of_nat [symmetric] fds_deriv_const)
    
lemma fds_deriv_of_int [simp]: "fds_deriv (of_int n) = 0"
  by (simp only: fds_const_of_int [symmetric] fds_deriv_const)
    
lemma fds_deriv_of_real [simp]: "fds_deriv (of_real n) = 0"
  by (simp only: fds_const_of_real [symmetric] fds_deriv_const)

lemma fds_deriv_uminus [simp]: "fds_deriv (-f) = -fds_deriv f"
  by (rule fds_eqI) (simp add: fds_nth_deriv)

lemma fds_deriv_add [simp]: "fds_deriv (f + g) = fds_deriv f + fds_deriv g"
  by (rule fds_eqI) (simp add: fds_nth_deriv algebra_simps)

lemma fds_deriv_minus [simp]: "fds_deriv (f - g) = fds_deriv f - fds_deriv g"
  by (rule fds_eqI) (simp add: fds_nth_deriv algebra_simps)

lemma fds_deriv_times [simp]: 
  "fds_deriv (f * g) = fds_deriv f * g + f * fds_deriv g"
  by (rule fds_eqI) 
     (auto simp add: fds_nth_deriv fds_nth_mult dirichlet_prod_altdef2 scaleR_right.sum 
        algebra_simps sum.distrib [symmetric] ln_mult intro!: sum.cong)

lemma fds_deriv_inverse [simp]:
  fixes f :: "'a :: {real_algebra, field} fds"
  assumes "fds_nth f (Suc 0)  0"
  shows   "fds_deriv (inverse f) = -fds_deriv f / f ^ 2"
proof -
  have "(0 :: 'a fds) = fds_deriv 1" by simp
  also from assms have "(1 :: 'a fds) = inverse f * f" by (simp add: fds_left_inverse)
  also have "fds_deriv  = fds_deriv (inverse f) * f + inverse f * fds_deriv f" by simp
  also have " * inverse f = fds_deriv (inverse f) * (f * inverse f) + 
                                inverse f ^ 2 * fds_deriv f" 
    by (simp add: algebra_simps power2_eq_square)
  also from assms have "f * inverse f = 1" by (simp add: fds_right_inverse)
  finally show ?thesis
    by (simp add: algebra_simps power2_eq_square divide_fds_def inverse_mult_fds add_eq_0_iff)
qed

lemma fds_deriv_shift [simp]: "fds_deriv (fds_shift c f) = fds_shift c (fds_deriv f)"
  by (rule fds_eqI) (simp add: fds_nth_deriv algebra_simps)

lemma fds_deriv_scale: "fds_deriv (fds_scale c f) = of_nat c * fds_scale c (fds_deriv f)"
proof (cases "c > 0")
  case True
  have *: "of_nat a * (b :: 'a) = real a *R b" for a b
    by (induction a) (simp_all add: algebra_simps)
  from True show ?thesis
    by (intro fds_eqI)
       (auto simp: fds_nth_deriv fds_nth_scale is_nth_powerE fds_const_of_nat [symmetric]
                ln_realpow * simp del: fds_const_of_nat elim!: is_nth_powerE)
qed auto

lemma fds_deriv_eq_imp_eq:
  assumes "fds_deriv f = fds_deriv g" "fds_nth f (Suc 0) = fds_nth g (Suc 0)"
  shows   "f = g"
proof (rule fds_eqI)
  fix n :: nat assume n: "n > 0"
  show "fds_nth f n = fds_nth g n"
  proof (cases "n = 1")
    case False
    with n have "n > 1" by auto
    hence "fds_nth f n = -fds_nth (fds_deriv f) n /R ln n"
      by (simp add: fds_deriv_def)
    also note assms(1)
    also from n > 1 have "-fds_nth (fds_deriv g) n /R ln n = fds_nth g n"
      by (simp add: fds_deriv_def)
    finally show ?thesis .
  qed (auto simp: assms)
qed

lemma completely_multiplicative_fds_deriv:
  assumes "completely_multiplicative_function f"
  shows   "fds_deriv (fds f) = -fds (λn. f n * mangoldt n) * fds f"
proof (rule fds_eqI, goal_cases)
  case (1 n)
  interpret completely_multiplicative_function f by fact
  have "fds_nth (-fds (λn. f n * mangoldt n) * fds f) n = 
          -((r, d) | r * d = n. f r * mangoldt r * f d)"
    by (simp add: fds_nth_mult fds_nth_deriv dirichlet_prod_altdef2)
  also have "((r, d) | r * d = n. f r * mangoldt r * f d) =
               ((r, d) | r * d = n. mangoldt r * f n)"
    using 1 by (intro sum.mono_neutral_cong_right refl) 
               (auto simp: mangoldt_def mult mult_ac intro!: finite_divisors_nat' split: if_splits)
  also have " = (r | r dvd n. mangoldt r * f n)" using 1
    by (intro sum.reindex_bij_witness[of _ "λr. (r, n div r)" fst]) auto
  also have " = (r | r dvd n. mangoldt r) * f n" (is "_ = ?S * _")
    by (subst sum_distrib_right [symmetric]) simp
  also have "(r | r dvd n. mangoldt r) = of_real (ln (real n))"
    using 1 by (intro mangoldt_sum) simp
  also have "- (of_real (ln (real n)) * f n) = fds_nth (fds_deriv (fds f)) n"
    using 1 by (simp add: fds_nth_deriv scaleR_conv_of_real)
  finally show ?case ..
qed

lemma completely_multiplicative_fds_deriv':
  "completely_multiplicative_function (fds_nth f) 
     fds_deriv f = - fds (λn. fds_nth f n * mangoldt n) * f"
  using completely_multiplicative_fds_deriv[of "fds_nth f"] by simp
  
lemma fds_deriv_zeta: 
  "fds_deriv fds_zeta = 
     -fds mangoldt * (fds_zeta :: 'a :: {comm_semiring_1,real_algebra_1} fds)"
proof -
  have "completely_multiplicative_function (λn. if n = 0 then 0 else 1)"
    by standard simp_all
  from completely_multiplicative_fds_deriv [OF this, folded fds_zeta_altdef]
    show ?thesis by simp
qed

lemma fds_mangoldt_times_zeta: "fds mangoldt * fds_zeta = fds (λx. of_real (ln (real x)))"
  by (rule fds_eqI) (simp add: fds_nth_mult dirichlet_prod_def mangoldt_sum)
    
lemma fds_deriv_zeta': "fds_deriv fds_zeta = 
    -fds (λx. of_real (ln (real x)):: 'a :: {comm_semiring_1,real_algebra_1})"
  by (simp add: fds_deriv_zeta fds_mangoldt_times_zeta)


subsection ‹Formal integral›

definition fds_integral :: "'a  'a :: real_algebra fds  'a fds" where
  "fds_integral c f = fds (λn. if n = 1 then c else - fds_nth f n /R ln (real n))"

lemma fds_integral_0 [simp]: "fds_integral a 0 = fds_const a"
  by (simp add: fds_integral_def fds_eq_iff)

lemma fds_integral_add: "fds_integral (a + b) (f + g) = fds_integral a f + fds_integral b g"
  by (rule fds_eqI) (auto simp: fds_integral_def scaleR_diff_right)

lemma fds_integral_diff: "fds_integral (a - b) (f - g) = fds_integral a f - fds_integral b g"
  by (rule fds_eqI) (auto simp: fds_integral_def scaleR_diff_right)

lemma fds_integral_minus: "fds_integral (-a) (-f) = -fds_integral a f"
  by (rule fds_eqI) (auto simp: fds_integral_def scaleR_diff_right)

lemma fds_shift_integral: "fds_shift b (fds_integral a f) = fds_integral a (fds_shift b f)"
  by (rule fds_eqI) (simp add: fds_integral_def fds_shift_def)

lemma fds_deriv_fds_integral [simp]: 
    "fds_nth f (Suc 0) = 0  fds_deriv (fds_integral c f) = f"
  by (simp add: fds_deriv_def fds_integral_def fds_eq_iff)

lemma fds_integral_fds_deriv [simp]: "fds_integral (fds_nth f 1) (fds_deriv f) = f"
  by (simp add: fds_deriv_def fds_integral_def fds_eq_iff)


subsection ‹Formal logarithm›

definition fds_ln :: "'a  'a :: {real_normed_field} fds  'a fds" where
  "fds_ln l f = fds_integral l (fds_deriv f / f)"

lemma fds_nth_Suc_0_fds_deriv [simp]: "fds_nth (fds_deriv f) (Suc 0) = 0"
  by (simp add: fds_deriv_def)

lemma fds_deriv_fds_ln [simp]: "fds_deriv (fds_ln l f) = fds_deriv f / f"
  unfolding fds_ln_def by (subst fds_deriv_fds_integral) (simp_all add: divide_fds_def)

lemma fds_nth_Suc_0_fds_ln [simp]: "fds_nth (fds_ln l f) (Suc 0) = l"
  by (simp add: fds_ln_def fds_integral_def)

lemma fds_ln_const [simp]: "fds_ln l (fds_const c) = fds_const l"
  by (rule fds_eqI) (simp add: fds_ln_def fds_integral_def divide_fds_def)

lemma fds_ln_0 [simp]: "fds_ln l 0 = fds_const l"
  by (rule fds_eqI) (simp add: fds_ln_def fds_integral_def divide_fds_def)

lemma fds_ln_1 [simp]: "fds_ln l 1 = fds_const l"
  by (rule fds_eqI) (simp add: fds_ln_def fds_integral_def divide_fds_def)

lemma fds_shift_ln [simp]: "fds_shift a (fds_ln l f) = fds_ln l (fds_shift a f)"
  by (simp add: fds_ln_def fds_shift_integral)

lemma fds_ln_mult:
  assumes "fds_nth f 1  0" "fds_nth g 1  0" "l' + l'' = l"
  shows   "fds_ln l (f * g) = fds_ln l' f + fds_ln l'' g"
proof -
  have "fds_ln l (f * g) = fds_integral (l' + l'') ((fds_deriv f * g + f * fds_deriv g) / (f * g))"
    by (simp add: fds_ln_def assms)
  also have "(fds_deriv f * g + f * fds_deriv g) / (f * g) =
               fds_deriv f / f * (g * inverse g) + fds_deriv g / g * (f * inverse f)"
    by (simp add: divide_fds_def algebra_simps inverse_mult_fds)
  also from assms have "f * inverse f = 1" by (intro fds_right_inverse) auto
  also from assms have "g * inverse g = 1" by (intro fds_right_inverse) auto
  finally show ?thesis by (simp add: fds_integral_add fds_ln_def)
qed

lemma fds_ln_power:
  assumes "fds_nth f 1  0" "l = of_nat n * l'"
  shows   "fds_ln l (f ^ n) = of_nat n * fds_ln l' f"
proof -
  have "fds_ln (of_nat n * l') (f ^ n) = of_nat n * fds_ln l' f"
    using assms(1) by (induction n) (simp_all add: fds_ln_mult algebra_simps)
  with assms show ?thesis by simp
qed

lemma fds_ln_prod:
  assumes "x. x  A  fds_nth (f x) 1  0" "(xA. l' x) = l"
  shows   "fds_ln l (xA. f x) = (xA. fds_ln (l' x) (f x))"
proof -
  have "fds_ln (xA. l' x) (xA. f x) = (xA. fds_ln (l' x) (f x))"
    using assms(1) by (induction A rule: infinite_finite_induct) (simp_all add: fds_ln_mult)
  with assms show ?thesis by simp
qed


subsection ‹Formal exponential›

definition fds_exp :: "'a :: {real_normed_algebra_1,banach} fds  'a fds" where
  "fds_exp f = (let f' = fds (λn. if n = 1 then 0 else fds_nth f n)
                in  fds (λn. exp (fds_nth f 1) * (k. fds_nth (f' ^ k) n /R fact k)))"

lemma fds_nth_exp_Suc_0 [simp]: "fds_nth (fds_exp f) (Suc 0) = exp (fds_nth f 1)"
proof -
  have "fds_nth (fds_exp f) (Suc 0) = exp (fds_nth f 1) * (k. 0 ^ k /R fact k)"
    by (simp add: fds_exp_def)
  also have "(k. (0::'a) ^ k /R fact k) = (k. if k = 0 then 1 else 0)"
    by (intro suminf_cong) (auto simp: power_0_left)
  also have " = 1" using sums_If_finite[of "λk. k = 0" "λ_. 1 :: 'a"]
    by (simp add: sums_iff)
  finally show ?thesis by simp
qed

lemma fds_exp_times_fds_nth_0:
  "fds_const (exp (fds_nth f (Suc 0))) * fds_exp (f - fds_const (fds_nth f (Suc 0))) = fds_exp f"
  by (rule fds_eqI) (simp add: fds_exp_def fds_nth_fds' cong: if_cong)

lemma fds_exp_const [simp]: "fds_exp (fds_const c) = fds_const (exp c)"
proof -
  have "fds_exp (fds_const c) = fds (λn. exp c * (k. fds_nth (fds (λn. 0) ^ k) n /R fact k))"
    by (simp add: fds_exp_def fds_nth_fds' one_fds_def cong: if_cong)
  also have "fds (λ_. 0 :: 'a) = 0" by (simp add: fds_eq_iff)
  also have "(λ(k::nat) (n::nat). fds_nth (0 ^ k) n) = (λk n. if k = 0  n = 1 then 1 else 0)"
    by (intro ext) (auto simp: one_fds_def fds_nth_fds' power_0_left)
  also have "(λn::nat. k. (if k = 0  n = 1 then 1 else (0::'a)) /R fact k) =
               (λn. if n = 1 then (k. (if k = 0 then 1 else 0) /R fact k) else 0)"
    by (intro ext) auto
  also have " = (λn::nat. if n = 1 then (k{0}. (if k = (0::nat) then 1 else 0)) else 0 :: 'a)"
    by (subst suminf_finite[of "{0}"]) auto
  also have "fds (λn. exp c *  n) = fds_const (exp c)"
    by (simp add: fds_const_def fds_eq_iff fds_nth_fds' cong: if_cong)
  finally show ?thesis .
qed

lemma fds_exp_numeral [simp]: "fds_exp (numeral n) = fds_const (exp (numeral n))"
  using fds_exp_const[of "numeral n :: 'a"] by (simp del: fds_exp_const add: numeral_fds)

lemma fds_exp_0 [simp]: "fds_exp 0 = 1"
  using fds_exp_const[of 0] by (simp del: fds_exp_const)

lemma fds_exp_1 [simp]: "fds_exp 1 = fds_const (exp 1)"
  using fds_exp_const[of 1] by (simp del: fds_exp_const)

lemma fds_nth_Suc_0_exp [simp]: "fds_nth (fds_exp f) (Suc 0) = exp (fds_nth f (Suc 0))"
proof -
  have "(k. 0 ^ k /R fact k) = (k{0}. 0 ^ k /R fact k :: 'a)"
    by (intro suminf_finite) (auto simp: power_0_left)
  also have " = 1" by simp
  finally show ?thesis by (simp add: fds_exp_def)
qed


subsection ‹Subseries›

definition fds_subseries :: "(nat  bool)  ('a :: semiring_1) fds  'a fds" where
  "fds_subseries P f = fds (λn. if P n then fds_nth f n else 0)"

lemma fds_nth_subseries:
  "fds_nth (fds_subseries P f) n = (if P n then fds_nth f n else 0)"
  by (simp add: fds_subseries_def fds_nth_fds')

lemma fds_subseries_0 [simp]: "fds_subseries P 0 = 0"
  by (simp add: fds_subseries_def fds_eq_iff)

lemma fds_subseries_1 [simp]: "P 1  fds_subseries P 1 = 1"
  by (simp add: fds_subseries_def fds_eq_iff one_fds_def)

lemma fds_subseries_const [simp]: "P 1  fds_subseries P (fds_const c) = fds_const c"
  by (simp add: fds_subseries_def fds_eq_iff fds_const_def)

lemma fds_subseries_add [simp]: "fds_subseries P (f + g) = fds_subseries P f + fds_subseries P g"
  by (simp add: fds_subseries_def fds_eq_iff plus_fds_def)

lemma fds_subseries_diff [simp]:
  "fds_subseries P (f - g :: 'a :: ring_1 fds) = fds_subseries P f - fds_subseries P g"
  by (simp add: fds_subseries_def fds_eq_iff minus_fds_def)

lemma fds_subseries_minus [simp]:
  "fds_subseries P (-f :: 'a :: ring_1 fds) = - fds_subseries P f"
  by (simp add: fds_subseries_def fds_eq_iff minus_fds_def)

lemma fds_subseries_sum [simp]: "fds_subseries P (xA. f x) = (xA. fds_subseries P (f x))"
  by (induction A rule: infinite_finite_induct) simp_all

lemma fds_subseries_shift [simp]:
  "fds_subseries P (fds_shift c f) = fds_shift c (fds_subseries P f)"
  by (simp add: fds_subseries_def fds_eq_iff)

lemma fds_subseries_deriv [simp]:
  "fds_subseries P (fds_deriv f) = fds_deriv (fds_subseries P f)"
  by (simp add: fds_subseries_def fds_deriv_def fds_eq_iff)

lemma fds_subseries_integral [simp]:
  "P 1  c = 0  fds_subseries P (fds_integral c f) = fds_integral c (fds_subseries P f)"
  by (auto simp: fds_subseries_def fds_integral_def fds_eq_iff)

abbreviation fds_primepow_subseries :: "nat  ('a :: semiring_1) fds  'a fds" where
  "fds_primepow_subseries p f  fds_subseries (λn. prime_factors n  {p}) f"

lemma fds_primepow_subseries_mult [simp]:
  fixes p :: nat
  defines "P  (λn. prime_factors n  {p})"
  shows   "fds_subseries P (f * g) = fds_subseries P f * fds_subseries P g"
proof (rule fds_eqI)
  fix n :: nat
  consider "n = 0" | "P n" "n > 0" | "¬P n" "n > 0" by blast
  thus "fds_nth (fds_subseries P (f * g)) n = fds_nth (fds_subseries P f * fds_subseries P g) n"
  proof cases
    case 2
    have P: "P d" if "d dvd n" for d
    proof -      
      have "prime_factors d  prime_factors n" using that 2
        by (intro dvd_prime_factors) auto
      also have "  {p}" using 2 by (simp add: P_def)
      finally show ?thesis by (simp add: P_def)
    qed
    have P': "P a" "P b" if "n = a * b" for a b
      using P[of a] P[of b] that by auto

    have "fds_nth (fds_subseries P (f * g)) n = dirichlet_prod (fds_nth f) (fds_nth g) n"
      using 2 by (simp add: fds_subseries_def fds_nth_fds' fds_nth_mult)
    also have " = dirichlet_prod (fds_nth (fds_subseries P f)) (fds_nth (fds_subseries P g)) n"
      unfolding dirichlet_prod_altdef2 using 2
      by (intro sum.cong refl) (auto simp: fds_subseries_def fds_nth_fds' dest: P')
    finally show ?thesis by (simp add: fds_nth_mult)
  next
    case 3
    have "¬(P a  P b)" if "n = a * b" for a b
    proof -
      have "prime_factors n = prime_factors (a * b)" by (simp add: that)
      also have " = prime_factors a  prime_factors b"
        using 3 that by (intro prime_factors_product) auto
      finally show ?thesis using 3 by (auto simp: P_def)
    qed
    hence "dirichlet_prod (fds_nth (fds_subseries P f)) (fds_nth (fds_subseries P g)) n = 0"
      unfolding dirichlet_prod_altdef2
      by (intro sum.neutral) (auto simp: fds_subseries_def fds_nth_fds')
    also have " = fds_nth (fds_subseries P (f * g)) n"
      using 3 by (simp add: fds_subseries_def)
    finally show ?thesis by (simp add: fds_nth_mult)
  qed auto
qed

lemma fds_primepow_subseries_power [simp]: 
  "fds_primepow_subseries p (f ^ n) = fds_primepow_subseries p f ^ n"
  by (induction n)  simp_all

lemma fds_primepow_subseries_prod [simp]: 
  "fds_primepow_subseries p (xA. f x) = (xA. fds_primepow_subseries p (f x))"
  by (induction A rule: infinite_finite_induct) simp_all

lemma completely_multiplicative_function_only_pows:
  assumes "completely_multiplicative_function (fds_nth f)"
  shows   "completely_multiplicative_function (fds_nth (fds_primepow_subseries p f))"
proof -
  interpret completely_multiplicative_function "fds_nth f" by fact
  show ?thesis
    by standard (auto simp: fds_nth_subseries prime_factors_product mult)
qed


subsection ‹Truncation›

definition fds_truncate :: "nat  'a ::{zero} fds  'a fds" where
  "fds_truncate m f = fds (λn. if n  m then fds_nth f n else 0)"

lemma fds_nth_truncate: "fds_nth (fds_truncate m f) n = (if n  m then fds_nth f n else 0)"
  by (simp add: fds_truncate_def fds_nth_fds')

lemma fds_truncate_0 [simp]: "fds_truncate 0 f = 0"
  by (simp add: fds_eq_iff fds_nth_truncate)

lemma fds_truncate_zero [simp]: "fds_truncate m 0 = 0"
  by (simp add: fds_truncate_def fds_eq_iff)

lemma fds_truncate_one [simp]: "m > 0  fds_truncate m 1 = 1"
  by (simp add: fds_truncate_def fds_eq_iff)

lemma fds_truncate_const [simp]: "m > 0  fds_truncate m (fds_const c) = fds_const c"
  by (simp add: fds_truncate_def fds_eq_iff)

lemma fds_truncate_truncate [simp]: "fds_truncate m (fds_truncate n f) = fds_truncate (min m n) f"
  by (rule fds_eqI) (simp add: fds_nth_truncate)

lemma fds_truncate_truncate' [simp]: "fds_truncate m (fds_truncate m f) = fds_truncate m f"
  by (rule fds_eqI) (simp add: fds_nth_truncate)

lemma fds_truncate_shift [simp]: "fds_truncate m (fds_shift a f) = fds_shift a (fds_truncate m f)"
  by (simp add: fds_eq_iff fds_nth_truncate)

lemma fds_truncate_add_strong: 
  "fds_truncate m (f + g :: 'a :: monoid_add fds) = fds_truncate m f + fds_truncate m g"
  by (auto simp: fds_eq_iff fds_nth_truncate)

lemma fds_truncate_add:
  "fds_truncate m (fds_truncate m f + fds_truncate m g :: 'a :: monoid_add fds) = 
     fds_truncate m (f + g)"
  by (auto simp: fds_eq_iff fds_nth_truncate)

lemma fds_truncate_mult:
  "fds_truncate m (fds_truncate m f * fds_truncate m g) = fds_truncate m (f * g)" (is "?A = ?B")
proof (intro fds_eqI, goal_cases)
  case (1 n)
  show ?case
  proof (cases "n  m")
    case True
    hence "fds_nth ?B n = dirichlet_prod (fds_nth f) (fds_nth g) n"
      by (simp add: fds_nth_truncate fds_nth_mult)
    also have " = dirichlet_prod (fds_nth (fds_truncate m f)) (fds_nth (fds_truncate m g)) n"
      unfolding dirichlet_prod_def
    proof (intro sum.cong refl, goal_cases)
      case (1 d)
      with n > 0 have "d  m" "n div d  m"
        by (auto dest: dvd_imp_le intro: order.trans[OF _ True])
      thus ?case by (auto simp add: fds_nth_truncate)
    qed
    also have " = fds_nth ?A n" using True by (simp add: fds_nth_truncate fds_nth_mult)
    finally show ?thesis ..
  qed (auto simp: fds_nth_truncate)
qed

lemma fds_truncate_deriv: "fds_truncate m (fds_deriv f) = fds_deriv (fds_truncate m f)"
  by (simp add: fds_eq_iff fds_nth_truncate fds_deriv_def)

lemma fds_truncate_integral: 
  "m > 0  c = 0  fds_truncate m (fds_integral c f) = fds_integral c (fds_truncate m f)"
  by (auto simp: fds_eq_iff fds_nth_truncate fds_integral_def)

lemma fds_truncate_power: "fds_truncate m (fds_truncate m f ^ n) = fds_truncate m (f ^ n)"
proof (cases "m = 0")
  case False
  show ?thesis
  proof (induction n)
    case (Suc n)
    have "fds_truncate m (fds_truncate m f ^ Suc n) =
            fds_truncate m (fds_truncate m f * fds_truncate m f ^ n)" by simp
    also have " = fds_truncate m (fds_truncate m f * fds_truncate m (f ^ n))"
      by (subst fds_truncate_mult [symmetric]) (simp add: Suc)
    also have " = fds_truncate m (f ^ Suc n)"
      by (simp add: fds_truncate_mult)
    finally show ?case .
  qed (simp_all add: fds_truncate_mult)
qed simp_all

lemma dirichlet_inverse_cong_simp:
  assumes "m. m > 0  m  n  f m = f' m" "i = i'" "n = n'"
  shows   "dirichlet_inverse f i n = dirichlet_inverse f' i' n'"
proof -
  have "dirichlet_inverse f i n = dirichlet_inverse f' i n"
  using assms(1)
  proof (induction n rule: dirichlet_inverse_induct) 
    case (gt1 n)
    have *: "dirichlet_inverse f i k = dirichlet_inverse f' i k" if "k dvd n  k < n" for k
      using that by (intro gt1) auto
    have *: "(d | d dvd n  d < n. f (n div d) * dirichlet_inverse f i d) =
               (d | d dvd n  d < n. f' (n div d) * dirichlet_inverse f' i d)"
      by (intro sum.cong refl) (subst gt1.prems, auto elim: dvdE simp: *)
    consider "n = 0" | "n = 1" | "n > 1" by force
    thus ?case
      by cases (insert *, simp_all add: dirichlet_inverse_gt_1 * cong: sum.cong)
  qed auto
  with assms(2,3) show ?thesis by simp
qed

lemma fds_truncate_cong: 
  "(n. m > 0  n > 0  n  m  fds_nth f n = fds_nth f' n) 
   fds_truncate m f = fds_truncate m f'"
  by (rule fds_eqI) (simp add: fds_nth_truncate)

lemma fds_truncate_inverse:
  "fds_truncate m (inverse (fds_truncate m (f :: 'a :: field fds))) = fds_truncate m (inverse f)"
proof (rule fds_truncate_cong, goal_cases)
  case (1 n)
  have *: "dirichlet_inverse (λn. if n  m then fds_nth f n else 0) (inverse (fds_nth f 1)) n =
             dirichlet_inverse (fds_nth f) (inverse (fds_nth f 1)) n" using 1
    by (intro dirichlet_inverse_cong_simp) auto
  show ?case
  proof (cases "fds_nth f 1 = 0")
    case True
    thus ?thesis by (auto simp: inverse_fds_nonunit fds_nth_truncate)
  qed (insert * 1,</