/- Released under Apache-2.0; see adjacent LICENSE. Finite higher-prime-power tail cover and actual prime-log-sum bridge. No PNT, Chebyshev import, analytical hypothesis or prime-supply estimate. -/ import PrimePsiBounds namespace PrimePowerTail noncomputable section open scoped BigOperators open Finset open PrimeFactorial (primePsi) open ArithmeticFunction (vonMangoldt) def primeThetaNat (N : ℕ) : ℝ := ∑ n ∈ (range (N + 1)).filter Nat.Prime, Real.log (n : ℝ) def tailSet (N : ℕ) : Finset ℕ := (range (N + 1)).filter (fun n => ¬ n.Prime ∧ IsPrimePow n) def sqrtCap (N : ℕ) : ℕ := ⌊Real.sqrt (N : ℝ)⌋₊ def exponentCap (N : ℕ) : ℕ := ⌊Real.log (N : ℝ) / Real.log 2⌋₊ def primeBases (N : ℕ) : Finset ℕ := (Icc 1 (sqrtCap N)).filter Nat.Prime def tailPairs (N : ℕ) : Finset (ℕ × ℕ) := (primeBases N) ×ˢ Icc 2 (exponentCap N) theorem primeThetaNat_eq_theta (N : ℕ) : primeThetaNat N = PrimeLog.theta (N : ℝ) := by unfold primeThetaNat rw [PrimeLog.theta_eq_sum_Icc] apply sum_congr ?_ (fun _ _ => rfl) ext n simp [mem_filter, mem_range, mem_Icc, Nat.lt_succ_iff] theorem primePsi_sub_theta_eq_tail (N : ℕ) : primePsi N - primeThetaNat N = ∑ n ∈ tailSet N, vonMangoldt n := by unfold primePsi primeThetaNat tailSet rw [sum_filter, ← sum_sub_distrib, sum_filter] apply sum_congr rfl intro n hn by_cases hp : n.Prime · simp [hp, ArithmeticFunction.vonMangoldt_apply_prime hp] · by_cases hpow : IsPrimePow n · simp [hp, hpow] · simp [hp, hpow, ArithmeticFunction.vonMangoldt_eq_zero_iff.mpr hpow] theorem log_two_pos : 0 < Real.log (2 : ℝ) := by linarith [FactorialWheel.log_two_lower] theorem tail_representation (N n : ℕ) (hN : 2 ≤ N) (hn : n ∈ tailSet N) : ∃ p k : ℕ, p.Prime ∧ 2 ≤ k ∧ p ≤ sqrtCap N ∧ k ≤ exponentCap N ∧ p ^ k = n := by rcases mem_filter.mp hn with ⟨hnr, hnprime, hnpow⟩ have hnN : n ≤ N := by have := mem_range.mp hnr; omega rcases (isPrimePow_nat_iff n).mp hnpow with ⟨p, k, hp, hk, hpk⟩ have hk2 : 2 ≤ k := by by_contra h have hk1 : k = 1 := by omega have hnp : n = p := by simpa [hk1] using hpk.symm exact hnprime (hnp ▸ hp) have hp2 : 2 ≤ p := hp.two_le have hp0 : (0 : ℝ) < p := by exact_mod_cast hp.pos have hN0 : (0 : ℝ) < N := by exact_mod_cast (show 0 < N by omega) have hlogN : 0 ≤ Real.log (N : ℝ) := Real.log_nonneg (by exact_mod_cast (show 1 ≤ N by omega)) have hpowN : p ^ k ≤ N := by omega have hsq : p ^ 2 ≤ N := (Nat.pow_le_pow_right (by omega : 1 ≤ p) hk2).trans hpowN have hsqR : (p : ℝ)^2 ≤ (N : ℝ) := by exact_mod_cast hsq have hsqrt : (p : ℝ) ≤ Real.sqrt (N : ℝ) := by have := Real.sq_sqrt (show (0 : ℝ) ≤ N by positivity) have := Real.sqrt_nonneg (N : ℝ) nlinarith have hpCap : p ≤ sqrtCap N := (Nat.le_floor_iff (Real.sqrt_nonneg (N : ℝ))).mpr hsqrt have hlogp : Real.log (2 : ℝ) ≤ Real.log (p : ℝ) := Real.log_le_log (by norm_num) (by exact_mod_cast hp2) have hlogpow : (k : ℝ) * Real.log (p : ℝ) ≤ Real.log (N : ℝ) := by have hc : ((p ^ k : ℕ) : ℝ) ≤ (N : ℝ) := by exact_mod_cast hpowN have h := Real.log_le_log (show (0 : ℝ) < ((p ^ k : ℕ) : ℝ) by positivity) hc simpa only [Nat.cast_pow, Real.log_pow] using h have hklog : (k : ℝ) * Real.log 2 ≤ Real.log (N : ℝ) := (mul_le_mul_of_nonneg_left hlogp (by positivity)).trans hlogpow have hkCap : k ≤ exponentCap N := by apply (Nat.le_floor_iff (div_nonneg hlogN log_two_pos.le)).mpr exact (le_div_iff₀ log_two_pos).mpr hklog exact ⟨p, k, hp, hk2, hpCap, hkCap, hpk⟩ theorem tail_image_cover (N : ℕ) (hN : 2 ≤ N) : tailSet N ⊆ (tailPairs N).image (fun q => q.1 ^ q.2) := by intro n hn rcases tail_representation N n hN hn with ⟨p, k, hp, hk2, hpCap, hkCap, hpk⟩ apply mem_image.mpr refine ⟨(p, k), ?_, hpk⟩ apply mem_product.mpr constructor · exact mem_filter.mpr ⟨mem_Icc.mpr ⟨hp.one_lt.le, hpCap⟩, hp⟩ · exact mem_Icc.mpr ⟨hk2, hkCap⟩ theorem tail_card_le (N : ℕ) (hN : 2 ≤ N) : (tailSet N).card ≤ sqrtCap N * exponentCap N := by have hb : (primeBases N).card ≤ sqrtCap N := by calc _ ≤ (Icc 1 (sqrtCap N)).card := card_le_card (filter_subset _ _) _ = _ := by simp have hk : (Icc 2 (exponentCap N)).card ≤ exponentCap N := by simp only [Nat.card_Icc] omega calc _ ≤ ((tailPairs N).image (fun q => q.1 ^ q.2)).card := card_le_card (tail_image_cover N hN) _ ≤ (tailPairs N).card := card_image_le _ = (primeBases N).card * (Icc 2 (exponentCap N)).card := card_product _ _ _ ≤ _ := Nat.mul_le_mul hb hk theorem exponentCap_le_twice_log (N : ℕ) (hN : 2 ≤ N) : (exponentCap N : ℝ) ≤ 2 * Real.log (N : ℝ) := by have hlogN : 0 ≤ Real.log (N : ℝ) := Real.log_nonneg (by exact_mod_cast (show 1 ≤ N by omega)) have hf : (exponentCap N : ℝ) ≤ Real.log (N : ℝ) / Real.log 2 := Nat.floor_le (div_nonneg hlogN log_two_pos.le) have hratio : Real.log (N : ℝ) / Real.log 2 ≤ 2 * Real.log (N : ℝ) := by apply (div_le_iff₀ log_two_pos).2 have hm := mul_le_mul_of_nonneg_left FactorialWheel.log_two_lower hlogN nlinarith exact hf.trans hratio theorem tail_card_real_le (N : ℕ) (hN : 2 ≤ N) : ((tailSet N).card : ℝ) ≤ 2 * Real.sqrt (N : ℝ) * Real.log (N : ℝ) := by have hc : ((tailSet N).card : ℝ) ≤ (sqrtCap N : ℝ) * exponentCap N := by exact_mod_cast tail_card_le N hN have hs : (sqrtCap N : ℝ) ≤ Real.sqrt (N : ℝ) := Nat.floor_le (Real.sqrt_nonneg _) have hk := exponentCap_le_twice_log N hN have hm := mul_le_mul hs hk (by positivity : (0 : ℝ) ≤ exponentCap N) (Real.sqrt_nonneg _) nlinarith theorem primePsi_theta_tail_bound (N : ℕ) (hN : 2 ≤ N) : 0 ≤ primePsi N - primeThetaNat N ∧ primePsi N - primeThetaNat N ≤ 2 * Real.sqrt (N : ℝ) * (Real.log (N : ℝ))^2 := by rw [primePsi_sub_theta_eq_tail] constructor · exact sum_nonneg (fun n _ => ArithmeticFunction.vonMangoldt_nonneg) · have hlogN : 0 ≤ Real.log (N : ℝ) := Real.log_nonneg (by exact_mod_cast (show 1 ≤ N by omega)) calc _ ≤ ∑ n ∈ tailSet N, Real.log (N : ℝ) := by apply sum_le_sum intro n hn have hnN : n ≤ N := by have := mem_range.mp (mem_filter.mp hn).1; omega have hn0 : (0 : ℝ) < n := by rcases tail_representation N n hN hn with ⟨p, k, hp, hk, hpc, hkc, rfl⟩ have hp0 : 0 < p := hp.pos positivity exact ArithmeticFunction.vonMangoldt_le_log.trans (Real.log_le_log hn0 (by exact_mod_cast hnN)) _ = ((tailSet N).card : ℝ) * Real.log (N : ℝ) := by simp _ ≤ (2 * Real.sqrt (N : ℝ) * Real.log (N : ℝ)) * Real.log (N : ℝ) := mul_le_mul_of_nonneg_right (tail_card_real_le N hN) hlogN _ = _ := by ring theorem actual_theta_tail_bound (N : ℕ) (hN : 2 ≤ N) : 0 ≤ primePsi N - PrimeLog.theta (N : ℝ) ∧ primePsi N - PrimeLog.theta (N : ℝ) ≤ 2 * Real.sqrt (N : ℝ) * (Real.log (N : ℝ))^2 := by rw [← primeThetaNat_eq_theta] exact primePsi_theta_tail_bound N hN end end PrimePowerTail #print axioms PrimePowerTail.primeThetaNat #print axioms PrimePowerTail.tailSet #print axioms PrimePowerTail.sqrtCap #print axioms PrimePowerTail.exponentCap #print axioms PrimePowerTail.primeBases #print axioms PrimePowerTail.tailPairs #print axioms PrimePowerTail.primeThetaNat_eq_theta #print axioms PrimePowerTail.primePsi_sub_theta_eq_tail #print axioms PrimePowerTail.log_two_pos #print axioms PrimePowerTail.tail_representation #print axioms PrimePowerTail.tail_image_cover #print axioms PrimePowerTail.tail_card_le #print axioms PrimePowerTail.exponentCap_le_twice_log #print axioms PrimePowerTail.tail_card_real_le #print axioms PrimePowerTail.primePsi_theta_tail_bound #print axioms PrimePowerTail.actual_theta_tail_bound