124 lemma one_not_primepow [simp]: "\<not>primepow 1" |
124 lemma one_not_primepow [simp]: "\<not>primepow 1" |
125 by (auto simp: primepow_def prime_power_not_one) |
125 by (auto simp: primepow_def prime_power_not_one) |
126 |
126 |
127 lemma primepow_not_unit [simp]: "primepow p \<Longrightarrow> \<not>is_unit p" |
127 lemma primepow_not_unit [simp]: "primepow p \<Longrightarrow> \<not>is_unit p" |
128 by (auto simp: primepow_def is_unit_power_iff) |
128 by (auto simp: primepow_def is_unit_power_iff) |
|
129 |
|
130 lemma not_primepow_Suc_0_nat [simp]: "\<not>primepow (Suc 0)" |
|
131 using primepow_gt_Suc_0[of "Suc 0"] by auto |
|
132 |
|
133 lemma primepow_gt_0_nat: "primepow n \<Longrightarrow> n > (0::nat)" |
|
134 using primepow_gt_Suc_0[of n] by simp |
129 |
135 |
130 lemma unit_factor_primepow: "primepow p \<Longrightarrow> unit_factor p = 1" |
136 lemma unit_factor_primepow: "primepow p \<Longrightarrow> unit_factor p = 1" |
131 by (auto simp: primepow_def unit_factor_power) |
137 by (auto simp: primepow_def unit_factor_power) |
132 |
138 |
133 lemma aprimedivisor_primepow: |
139 lemma aprimedivisor_primepow: |
202 then obtain q k where *: "k > 0" "prime q" "p = q ^ k" by (auto simp: primepow_def) |
208 then obtain q k where *: "k > 0" "prime q" "p = q ^ k" by (auto simp: primepow_def) |
203 with \<open>n > 0\<close> show "primepow (p ^ n)" |
209 with \<open>n > 0\<close> show "primepow (p ^ n)" |
204 by (auto simp: primepow_def power_mult intro!: exI[of _ q] exI[of _ "k * n"]) |
210 by (auto simp: primepow_def power_mult intro!: exI[of _ q] exI[of _ "k * n"]) |
205 qed |
211 qed |
206 |
212 |
|
213 lemma primepow_power_iff_nat: |
|
214 "p > 0 \<Longrightarrow> primepow (p ^ n) \<longleftrightarrow> primepow (p :: nat) \<and> n > 0" |
|
215 by (rule primepow_power_iff) (simp_all add: unit_factor_nat_def) |
|
216 |
207 lemma primepow_prime [simp]: "prime n \<Longrightarrow> primepow n" |
217 lemma primepow_prime [simp]: "prime n \<Longrightarrow> primepow n" |
208 by (auto simp: primepow_def intro!: exI[of _ n] exI[of _ "1::nat"]) |
218 by (auto simp: primepow_def intro!: exI[of _ n] exI[of _ "1::nat"]) |
209 |
219 |
210 lemma primepow_prime_power [simp]: |
220 lemma primepow_prime_power [simp]: |
211 "prime (p :: 'a :: factorial_semiring) \<Longrightarrow> primepow (p ^ n) \<longleftrightarrow> n > 0" |
221 "prime (p :: 'a :: factorial_semiring) \<Longrightarrow> primepow (p ^ n) \<longleftrightarrow> n > 0" |
212 by (subst primepow_power_iff) auto |
222 by (subst primepow_power_iff) auto |
|
223 |
|
224 lemma aprimedivisor_vimage: |
|
225 assumes "prime (p :: 'a :: factorial_semiring)" |
|
226 shows "aprimedivisor -` {p} \<inter> primepow_factors n = {p ^ k |k. k > 0 \<and> p ^ k dvd n}" |
|
227 proof safe |
|
228 fix q assume q: "q \<in> primepow_factors n" |
|
229 hence q': "q \<noteq> 0" "q \<noteq> 1" by (auto simp: primepow_def primepow_factors_def prime_power_not_one) |
|
230 let ?n = "multiplicity (aprimedivisor q) q" |
|
231 from q q' have "q = aprimedivisor q ^ ?n \<and> ?n > 0 \<and> aprimedivisor q ^ ?n dvd n" |
|
232 by (auto simp: primepow_decompose primepow_factors_def prime_multiplicity_gt_zero_iff |
|
233 prime_aprimedivisor' prime_imp_prime_elem aprimedivisor_dvd') |
|
234 thus "\<exists>k. q = aprimedivisor q ^ k \<and> k > 0 \<and> aprimedivisor q ^ k dvd n" .. |
|
235 next |
|
236 fix k :: nat assume k: "p ^ k dvd n" "k > 0" |
|
237 with assms show "p ^ k \<in> aprimedivisor -` {p}" |
|
238 by (auto simp: aprimedivisor_prime_power) |
|
239 with assms k show "p ^ k \<in> primepow_factors n" |
|
240 by (auto simp: primepow_factors_def primepow_def aprimedivisor_prime_power intro: Suc_leI) |
|
241 qed |
|
242 |
|
243 lemma aprimedivisor_nat: |
|
244 assumes "n \<noteq> (Suc 0::nat)" |
|
245 shows "prime (aprimedivisor n)" "aprimedivisor n dvd n" |
|
246 proof - |
|
247 from assms have "\<exists>p. prime p \<and> p dvd n" by (intro prime_factor_nat) auto |
|
248 from someI_ex[OF this, folded aprimedivisor_def] |
|
249 show "prime (aprimedivisor n)" "aprimedivisor n dvd n" by blast+ |
|
250 qed |
|
251 |
|
252 lemma aprimedivisor_gt_Suc_0: |
|
253 assumes "n \<noteq> Suc 0" |
|
254 shows "aprimedivisor n > Suc 0" |
|
255 proof - |
|
256 from assms have "prime (aprimedivisor n)" by (rule aprimedivisor_nat) |
|
257 thus "aprimedivisor n > Suc 0" by (simp add: prime_nat_iff) |
|
258 qed |
|
259 |
|
260 lemma aprimedivisor_le_nat: |
|
261 assumes "n > Suc 0" |
|
262 shows "aprimedivisor n \<le> n" |
|
263 proof - |
|
264 from assms have "aprimedivisor n dvd n" by (intro aprimedivisor_nat) simp_all |
|
265 with assms show "aprimedivisor n \<le> n" |
|
266 by (intro dvd_imp_le) simp_all |
|
267 qed |
213 |
268 |
214 lemma bij_betw_primepows: |
269 lemma bij_betw_primepows: |
215 "bij_betw (\<lambda>(p,k). p ^ Suc k :: 'a :: factorial_semiring) |
270 "bij_betw (\<lambda>(p,k). p ^ Suc k :: 'a :: factorial_semiring) |
216 (Collect prime \<times> UNIV) (Collect primepow)" |
271 (Collect prime \<times> UNIV) (Collect primepow)" |
217 proof (rule bij_betwI [where ?g = "(\<lambda>n. (aprimedivisor n, multiplicity (aprimedivisor n) n - 1))"], |
272 proof (rule bij_betwI [where ?g = "(\<lambda>n. (aprimedivisor n, multiplicity (aprimedivisor n) n - 1))"], |
258 assumes "primepow (n :: 'a :: factorial_semiring)" |
313 assumes "primepow (n :: 'a :: factorial_semiring)" |
259 shows "primepow (aprimedivisor n * n)" |
314 shows "primepow (aprimedivisor n * n)" |
260 by (subst (2) primepow_decompose[OF assms, symmetric], subst power_Suc [symmetric], |
315 by (subst (2) primepow_decompose[OF assms, symmetric], subst power_Suc [symmetric], |
261 subst primepow_prime_power) |
316 subst primepow_prime_power) |
262 (insert assms, auto intro!: prime_aprimedivisor' dest: primepow_gt_Suc_0) |
317 (insert assms, auto intro!: prime_aprimedivisor' dest: primepow_gt_Suc_0) |
263 |
318 |
264 lemma aprimedivisor_vimage: |
|
265 assumes "prime (p :: 'a :: factorial_semiring)" |
|
266 shows "aprimedivisor -` {p} \<inter> primepow_factors n = {p ^ k |k. k > 0 \<and> p ^ k dvd n}" |
|
267 proof safe |
|
268 fix q assume q: "q \<in> primepow_factors n" |
|
269 hence q': "q \<noteq> 0" "q \<noteq> 1" by (auto simp: primepow_def primepow_factors_def prime_power_not_one) |
|
270 let ?n = "multiplicity (aprimedivisor q) q" |
|
271 from q q' have "q = aprimedivisor q ^ ?n \<and> ?n > 0 \<and> aprimedivisor q ^ ?n dvd n" |
|
272 using prime_aprimedivisor'[of q] aprimedivisor_dvd'[of q] |
|
273 by (subst primepow_decompose [symmetric]) |
|
274 (auto simp: primepow_factors_def multiplicity_gt_zero_iff unit_factor_primepow |
|
275 intro: dvd_trans[OF multiplicity_dvd]) |
|
276 thus "\<exists>k. q = aprimedivisor q ^ k \<and> k > 0 \<and> aprimedivisor q ^ k dvd n" .. |
|
277 next |
|
278 fix k :: nat assume k: "p ^ k dvd n" "k > 0" |
|
279 with assms show "p ^ k \<in> aprimedivisor -` {p}" |
|
280 by (auto simp: aprimedivisor_prime_power) |
|
281 with assms k show "p ^ k \<in> primepow_factors n" |
|
282 by (auto simp: primepow_factors_def primepow_def aprimedivisor_prime_power intro: Suc_leI) |
|
283 qed |
|
284 |
|
285 lemma primepow_factors_altdef: |
319 lemma primepow_factors_altdef: |
286 fixes x :: "'a :: factorial_semiring" |
320 fixes x :: "'a :: factorial_semiring" |
287 assumes "x \<noteq> 0" |
321 assumes "x \<noteq> 0" |
288 shows "primepow_factors x = {p ^ k |p k. p \<in> prime_factors x \<and> k \<in> {0<.. multiplicity p x}}" |
322 shows "primepow_factors x = {p ^ k |p k. p \<in> prime_factors x \<and> k \<in> {0<.. multiplicity p x}}" |
289 proof (intro equalityI subsetI) |
323 proof (intro equalityI subsetI) |
304 hence "finite ((\<lambda>(p,k). p ^ k) ` \<dots>)" (is "finite ?A") by (rule finite_imageI) |
338 hence "finite ((\<lambda>(p,k). p ^ k) ` \<dots>)" (is "finite ?A") by (rule finite_imageI) |
305 also have "?A = primepow_factors x" |
339 also have "?A = primepow_factors x" |
306 using assms by (subst primepow_factors_altdef) fast+ |
340 using assms by (subst primepow_factors_altdef) fast+ |
307 finally show ?thesis . |
341 finally show ?thesis . |
308 qed |
342 qed |
|
343 |
|
344 lemma aprimedivisor_primepow_factors_conv_prime_factorization: |
|
345 assumes [simp]: "n \<noteq> (0 :: 'a :: factorial_semiring)" |
|
346 shows "image_mset aprimedivisor (mset_set (primepow_factors n)) = prime_factorization n" |
|
347 (is "?lhs = ?rhs") |
|
348 proof (intro multiset_eqI) |
|
349 fix p :: 'a |
|
350 show "count ?lhs p = count ?rhs p" |
|
351 proof (cases "prime p") |
|
352 case False |
|
353 have "p \<notin># image_mset aprimedivisor (mset_set (primepow_factors n))" |
|
354 proof |
|
355 assume "p \<in># image_mset aprimedivisor (mset_set (primepow_factors n))" |
|
356 then obtain q where "p = aprimedivisor q" "q \<in> primepow_factors n" |
|
357 by (auto simp: finite_primepow_factors) |
|
358 with False prime_aprimedivisor'[of q] have "q = 0 \<or> is_unit q" by auto |
|
359 with \<open>q \<in> primepow_factors n\<close> show False by (auto simp: primepow_factors_def primepow_def) |
|
360 qed |
|
361 hence "count ?lhs p = 0" by (simp only: Multiset.not_in_iff) |
|
362 with False show ?thesis by (simp add: count_prime_factorization) |
|
363 next |
|
364 case True |
|
365 hence p: "p \<noteq> 0" "\<not>is_unit p" by auto |
|
366 have "count ?lhs p = card (aprimedivisor -` {p} \<inter> primepow_factors n)" |
|
367 by (simp add: count_image_mset finite_primepow_factors) |
|
368 also have "aprimedivisor -` {p} \<inter> primepow_factors n = {p^k |k. k > 0 \<and> p ^ k dvd n}" |
|
369 using True by (rule aprimedivisor_vimage) |
|
370 also from True have "\<dots> = (\<lambda>k. p ^ k) ` {0<..multiplicity p n}" |
|
371 by (subst power_dvd_iff_le_multiplicity) auto |
|
372 also from p True have "card \<dots> = multiplicity p n" |
|
373 by (subst card_image) (auto intro!: inj_onI dest: prime_power_inj) |
|
374 also from True have "\<dots> = count (prime_factorization n) p" |
|
375 by (simp add: count_prime_factorization) |
|
376 finally show ?thesis . |
|
377 qed |
|
378 qed |
|
379 |
|
380 lemma prime_elem_aprimedivisor_nat: "d > Suc 0 \<Longrightarrow> prime_elem (aprimedivisor d)" |
|
381 using prime_aprimedivisor'[of d] by simp |
|
382 |
|
383 lemma aprimedivisor_gt_0_nat [simp]: "d > Suc 0 \<Longrightarrow> aprimedivisor d > 0" |
|
384 using prime_aprimedivisor'[of d] by (simp add: prime_gt_0_nat) |
|
385 |
|
386 lemma aprimedivisor_gt_Suc_0_nat [simp]: "d > Suc 0 \<Longrightarrow> aprimedivisor d > Suc 0" |
|
387 using prime_aprimedivisor'[of d] by (simp add: prime_gt_Suc_0_nat) |
|
388 |
|
389 lemma aprimedivisor_not_Suc_0_nat [simp]: "d > Suc 0 \<Longrightarrow> aprimedivisor d \<noteq> Suc 0" |
|
390 using aprimedivisor_gt_Suc_0[of d] by (intro notI) auto |
|
391 |
|
392 lemma multiplicity_aprimedivisor_gt_0_nat [simp]: |
|
393 "d > Suc 0 \<Longrightarrow> multiplicity (aprimedivisor d) d > 0" |
|
394 by (subst multiplicity_gt_zero_iff) (auto intro: aprimedivisor_dvd') |
|
395 |
|
396 lemma primepowI: |
|
397 "prime p \<Longrightarrow> k > 0 \<Longrightarrow> p ^ k = n \<Longrightarrow> primepow n \<and> aprimedivisor n = p" |
|
398 unfolding primepow_def by (auto simp: aprimedivisor_prime_power) |
|
399 |
|
400 lemma not_primepowI: |
|
401 assumes "prime p" "prime q" "p \<noteq> q" "p dvd n" "q dvd n" |
|
402 shows "\<not>primepow n" |
|
403 using assms by (auto simp: primepow_def dest!: prime_dvd_power[rotated] dest: primes_dvd_imp_eq) |
|
404 |
|
405 lemma sum_prime_factorization_conv_sum_primepow_factors: |
|
406 assumes "n \<noteq> 0" |
|
407 shows "(\<Sum>q\<in>primepow_factors n. f (aprimedivisor q)) = (\<Sum>p\<in>#prime_factorization n. f p)" |
|
408 proof - |
|
409 from assms have "prime_factorization n = image_mset aprimedivisor (mset_set (primepow_factors n))" |
|
410 by (rule aprimedivisor_primepow_factors_conv_prime_factorization [symmetric]) |
|
411 also have "(\<Sum>p\<in>#\<dots>. f p) = (\<Sum>q\<in>primepow_factors n. f (aprimedivisor q))" |
|
412 by (simp add: image_mset.compositionality sum_unfold_sum_mset o_def) |
|
413 finally show ?thesis .. |
|
414 qed |
|
415 |
|
416 lemma multiplicity_aprimedivisor_Suc_0_iff: |
|
417 assumes "primepow (n :: 'a :: factorial_semiring)" |
|
418 shows "multiplicity (aprimedivisor n) n = Suc 0 \<longleftrightarrow> prime n" |
|
419 by (subst (3) primepow_decompose [OF assms, symmetric]) |
|
420 (insert assms, auto simp add: prime_power_iff intro!: prime_aprimedivisor') |
309 |
421 |
310 |
422 |
311 definition mangoldt :: "nat \<Rightarrow> 'a :: real_algebra_1" where |
423 definition mangoldt :: "nat \<Rightarrow> 'a :: real_algebra_1" where |
312 "mangoldt n = (if primepow n then of_real (ln (real (aprimedivisor n))) else 0)" |
424 "mangoldt n = (if primepow n then of_real (ln (real (aprimedivisor n))) else 0)" |
313 |
425 |
340 also have "\<dots> = (\<Prod>x\<in>prime_factors n. x ^ multiplicity x n)" |
452 also have "\<dots> = (\<Prod>x\<in>prime_factors n. x ^ multiplicity x n)" |
341 by (intro prod.cong refl) (simp add: prod_constant) |
453 by (intro prod.cong refl) (simp add: prod_constant) |
342 also have "\<dots> = n" using assms by (intro prime_factorization_nat [symmetric]) simp |
454 also have "\<dots> = n" using assms by (intro prime_factorization_nat [symmetric]) simp |
343 finally show ?thesis . |
455 finally show ?thesis . |
344 qed |
456 qed |
345 |
457 |
|
458 lemma mangoldt_primepow: |
|
459 "prime p \<Longrightarrow> mangoldt (p ^ k) = (if k > 0 then of_real (ln (real p)) else 0)" |
|
460 by (simp add: mangoldt_def aprimedivisor_prime_power) |
|
461 |
|
462 lemma mangoldt_primepow' [simp]: "prime p \<Longrightarrow> k > 0 \<Longrightarrow> mangoldt (p ^ k) = of_real (ln (real p))" |
|
463 by (subst mangoldt_primepow) auto |
|
464 |
|
465 lemma mangoldt_prime [simp]: "prime p \<Longrightarrow> mangoldt p = of_real (ln (real p))" |
|
466 using mangoldt_primepow[of p 1] by simp |
|
467 |
|
468 lemma mangoldt_nonneg: "0 \<le> (mangoldt d :: real)" |
|
469 using aprimedivisor_gt_Suc_0_nat[of d] |
|
470 by (auto simp: mangoldt_def of_nat_le_iff[of 1 x for x, unfolded of_nat_1] Suc_le_eq |
|
471 intro!: ln_ge_zero dest: primepow_gt_Suc_0) |
|
472 |
|
473 lemma norm_mangoldt [simp]: |
|
474 "norm (mangoldt n :: 'a :: real_normed_algebra_1) = mangoldt n" |
|
475 proof (cases "primepow n") |
|
476 case True |
|
477 hence "prime (aprimedivisor n)" |
|
478 by (intro prime_aprimedivisor') |
|
479 (auto simp: primepow_def prime_gt_0_nat) |
|
480 hence "aprimedivisor n > 1" by (simp add: prime_gt_Suc_0_nat) |
|
481 with True show ?thesis by (auto simp: mangoldt_def abs_if) |
|
482 qed (auto simp: mangoldt_def) |
|
483 |
|
484 lemma abs_mangoldt [simp]: "abs (mangoldt n :: real) = mangoldt n" |
|
485 using norm_mangoldt[of n, where ?'a = real, unfolded real_norm_def] . |
|
486 |
|
487 lemma mangoldt_le: |
|
488 assumes "n > 0" |
|
489 shows "mangoldt n \<le> ln n" |
|
490 proof (cases "primepow n") |
|
491 case True |
|
492 from True have "prime (aprimedivisor n)" |
|
493 by (intro prime_aprimedivisor') |
|
494 (auto simp: primepow_def prime_gt_0_nat) |
|
495 hence gt_1: "aprimedivisor n > 1" by (simp add: prime_gt_Suc_0_nat) |
|
496 from True have "mangoldt n = ln (aprimedivisor n)" |
|
497 by (simp add: mangoldt_def) |
|
498 also have "\<dots> \<le> ln n" using True gt_1 |
|
499 by (subst ln_le_cancel_iff) (auto intro!: Nat.gr0I dvd_imp_le aprimedivisor_dvd') |
|
500 finally show ?thesis . |
|
501 qed (insert assms, auto simp: mangoldt_def) |
|
502 |
346 end |
503 end |