Theory Dirichlet_Series
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
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]: "(∑x∈A. fds (f x)) = fds (λn. ∑x∈A. 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 (∏x∈A. f x) n =
(∑d | d ∈ extensional A ∧ prod d A = n. ∏x∈A. 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 (∏x∈insert 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) * (∏x∈A. 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) * (∏x∈A. 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.
(∏x∈insert 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 "(∏xa∈A. fds_nth (f xa) (if xa = x then fst (fst z) else snd z xa)) =
(∏x∈A. 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) = (∏x∈A. 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 (∑x∈A. f x) = (∑x∈A. fds_shift a (f x))"
by (induction A rule: infinite_finite_induct) simp_all
lemma fds_shift_prod [simp]: "fds_shift a (∏x∈A. f x) = (∏x∈A. 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 = {rs∈A. ¬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" "(∑x∈A. l' x) = l"
shows "fds_ln l (∏x∈A. f x) = (∑x∈A. fds_ln (l' x) (f x))"
proof -
have "fds_ln (∑x∈A. l' x) (∏x∈A. f x) = (∑x∈A. 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 (∑x∈A. f x) = (∑x∈A. 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 (∏x∈A. f x) = (∏x∈A. 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,