/- Released under Apache-2.0; see adjacent LICENSE. Exact finite factorial/von Mangoldt wheel identities and comparisons. The distinct primePsi counts prime powers with logarithmic weights, not smooth integers. -/ import FactorialWheel import Mathlib.NumberTheory.ArithmeticFunction.VonMangoldt namespace PrimeFactorial noncomputable section open scoped BigOperators open Finset open ArithmeticFunction (vonMangoldt) /-- Weighted sum of positive prime powers, distinct from EarlyCover.Psi. -/ def primePsi (N : ℕ) : ℝ := ∑ n ∈ range (N + 1), vonMangoldt n def weighted (N : ℕ) : ℝ := ∑ n ∈ range (N + 1), vonMangoldt n * (N / n : ℕ) theorem weighted_extend (M N : ℕ) (hMN : M ≤ N) : weighted M = ∑ n ∈ range (N + 1), vonMangoldt n * (M / n : ℕ) := by unfold weighted apply sum_subset (range_mono (by omega)) intro n hn hnm have hlt : M < n := by simp only [mem_range] at hn hnm; omega simp [Nat.div_eq_of_lt hlt] theorem divisors_eq_filter (N : ℕ) : (range (N + 2)).filter (fun n => n ∣ N + 1) = (N + 1).divisors := by ext n simp only [mem_filter, mem_range, Nat.mem_divisors] constructor · intro h; exact ⟨h.2, by omega⟩ · intro h exact ⟨by have := Nat.le_of_dvd (show 0 < N + 1 by omega) h.1; omega, h.1⟩ theorem weighted_succ (N : ℕ) : weighted (N + 1) = weighted N + Real.log ((N + 1 : ℕ) : ℝ) := by rw [weighted_extend N (N + 1) (by omega)] unfold weighted have he : ∀ n : ℕ, vonMangoldt n * ((N + 1) / n : ℕ) = vonMangoldt n * (N / n : ℕ) + if n ∣ N + 1 then vonMangoldt n else 0 := by intro n rw [Nat.succ_div, Nat.cast_add] split_ifs <;> simp <;> ring simp_rw [he] rw [sum_add_distrib, ← sum_filter, divisors_eq_filter, ArithmeticFunction.vonMangoldt_sum] theorem log_factorial_weighted (N : ℕ) : Real.log ((N.factorial : ℕ) : ℝ) = ∑ n ∈ range (N + 1), vonMangoldt n * (N / n : ℕ) := by change Real.log ((N.factorial : ℕ) : ℝ) = weighted N induction N with | zero => simp [weighted] | succ N ih => rw [FactorialLogBounds.log_factorial_succ, weighted_succ, ih]; ring theorem F_nat_div (N d : ℕ) : FactorialWheel.F ((N : ℝ) / d) = Real.log (((N / d).factorial : ℕ) : ℝ) := by have hfloor : ⌊(N : ℝ) / d⌋₊ = N / d := by by_cases hd0 : d = 0 · subst d; simp have hd : 0 < d := Nat.pos_of_ne_zero hd0 have hdR : (0 : ℝ) < d := by exact_mod_cast hd apply (Nat.floor_eq_iff (show (0 : ℝ) ≤ (N : ℝ) / d by positivity)).2 constructor · apply (le_div_iff₀ hdR).2 exact_mod_cast Nat.div_mul_le_self N d · apply (div_lt_iff₀ hdR).2 exact_mod_cast (Nat.div_lt_iff_lt_mul hd).1 (Nat.lt_succ_self (N / d)) simp [FactorialWheel.F, hfloor] theorem factorial_weighted_extend (N d : ℕ) : Real.log (((N / d).factorial : ℕ) : ℝ) = ∑ n ∈ range (N + 1), vonMangoldt n * ((N / n) / d : ℕ) := by rw [log_factorial_weighted] change weighted (N / d) = _ rw [weighted_extend (N / d) N (Nat.div_le_self N d)] apply sum_congr rfl intro n hn rw [Nat.div_div_eq_div_mul, Nat.div_div_eq_div_mul, Nat.mul_comm d n] theorem T_eq_weighted_wheel (N : ℕ) : FactorialWheel.T (N : ℝ) = ∑ n ∈ range (N + 1), vonMangoldt n * (FactorialWheel.wheel (N / n) : ℝ) := by unfold FactorialWheel.T have hF : FactorialWheel.F (N : ℝ) = Real.log ((N.factorial : ℕ) : ℝ) := by simp [FactorialWheel.F] rw [hF] rw [show (2 : ℝ) = (2 : ℕ) by norm_num, F_nat_div, show (3 : ℝ) = (3 : ℕ) by norm_num, F_nat_div, show (5 : ℝ) = (5 : ℕ) by norm_num, F_nat_div, show (30 : ℝ) = (30 : ℕ) by norm_num, F_nat_div] rw [log_factorial_weighted, factorial_weighted_extend, factorial_weighted_extend, factorial_weighted_extend, factorial_weighted_extend] rw [← sum_sub_distrib, ← sum_sub_distrib, ← sum_sub_distrib, ← sum_add_distrib] apply sum_congr rfl intro n hn simp only [FactorialWheel.wheel, Int.cast_add, Int.cast_sub, Int.cast_natCast] ring theorem wheel_real_bounds (n : ℕ) : (0 : ℝ) ≤ (FactorialWheel.wheel n : ℝ) ∧ (FactorialWheel.wheel n : ℝ) ≤ 1 := by rcases FactorialWheel.wheel_zero_or_one n with h | h <;> rw [h] <;> norm_num theorem T_nonneg_le_primePsi (N : ℕ) : 0 ≤ FactorialWheel.T (N : ℝ) ∧ FactorialWheel.T (N : ℝ) ≤ primePsi N := by rw [T_eq_weighted_wheel] constructor · exact sum_nonneg (fun n _ => mul_nonneg ArithmeticFunction.vonMangoldt_nonneg (wheel_real_bounds _).1) · unfold primePsi apply sum_le_sum intro n hn simpa using mul_le_mul_of_nonneg_left (wheel_real_bounds (N / n)).2 (ArithmeticFunction.vonMangoldt_nonneg (n := n)) theorem wheel_one_strip (N n : ℕ) (hlo : N / 6 < n) (hhi : n ≤ N) : FactorialWheel.wheel (N / n) = 1 := by have hn : 0 < n := by omega apply FactorialWheel.wheel_one · exact (Nat.le_div_iff_mul_le hn).2 (by simpa using hhi) · apply (Nat.div_lt_iff_lt_mul hn).2 have := (Nat.div_lt_iff_lt_mul (by norm_num : 0 < 6)).1 hlo simpa [Nat.mul_comm] using this theorem primePsi_strip (N : ℕ) : primePsi N - primePsi (N / 6) = ∑ n ∈ Ioc (N / 6) N, vonMangoldt n := by unfold primePsi have hu : range (N / 6 + 1) ∪ Ioc (N / 6) N = range (N + 1) := by ext n simp only [mem_union, mem_range, mem_Ioc] have := Nat.div_le_self N 6 omega have hd : Disjoint (range (N / 6 + 1)) (Ioc (N / 6) N) := by apply disjoint_left.mpr intro n hn hm simp only [mem_range] at hn simp only [mem_Ioc] at hm omega have he := sum_union (f := fun n => vonMangoldt n) hd rw [hu] at he linarith theorem primePsi_sub_sixth_le_T (N : ℕ) : primePsi N - primePsi (N / 6) ≤ FactorialWheel.T (N : ℝ) := by rw [primePsi_strip, T_eq_weighted_wheel] have hs : Ioc (N / 6) N ⊆ range (N + 1) := by intro n hn simp only [mem_Ioc] at hn simp only [mem_range] omega calc _ = ∑ n ∈ Ioc (N / 6) N, vonMangoldt n * (FactorialWheel.wheel (N / n) : ℝ) := by apply sum_congr rfl intro n hn simp only [mem_Ioc] at hn rw [wheel_one_strip N n hn.1 hn.2] simp _ ≤ _ := sum_le_sum_of_subset_of_nonneg hs (fun n _ _ => mul_nonneg ArithmeticFunction.vonMangoldt_nonneg (wheel_real_bounds _).1) end end PrimeFactorial #print axioms PrimeFactorial.primePsi #print axioms PrimeFactorial.weighted #print axioms PrimeFactorial.weighted_extend #print axioms PrimeFactorial.divisors_eq_filter #print axioms PrimeFactorial.weighted_succ #print axioms PrimeFactorial.log_factorial_weighted #print axioms PrimeFactorial.F_nat_div #print axioms PrimeFactorial.factorial_weighted_extend #print axioms PrimeFactorial.T_eq_weighted_wheel #print axioms PrimeFactorial.wheel_real_bounds #print axioms PrimeFactorial.T_nonneg_le_primePsi #print axioms PrimeFactorial.wheel_one_strip #print axioms PrimeFactorial.primePsi_strip #print axioms PrimeFactorial.primePsi_sub_sixth_le_T