/- Released under Apache-2.0; see adjacent LICENSE. Explicit natural prime-power sum bounds from the proved factorial wheel. No analytical or prime-supply hypotheses. -/ import PrimeFactorial namespace PrimePsiBounds noncomputable section open scoped BigOperators open Finset open PrimeFactorial (primePsi) open FactorialWheel (a T) open ArithmeticFunction (vonMangoldt) def L (N : ℕ) : ℝ := 1 + Real.log ((N : ℝ) + 1) theorem L_ge_one (N : ℕ) : 1 ≤ L N := by have hlog : 0 ≤ Real.log ((N : ℝ) + 1) := Real.log_nonneg (by have := Nat.cast_nonneg (α := ℝ) N; linarith) unfold L linarith theorem coefficient_nonneg : 0 ≤ a := by linarith [FactorialWheel.a_lower] theorem T_bounds (N : ℕ) : a * N - 5 * L N ≤ T (N : ℝ) ∧ T (N : ℝ) ≤ a * N + 5 * L N := by have h := abs_le.mp (FactorialWheel.T_error (N : ℝ) (by positivity)) change -(5 * L N) ≤ T (N : ℝ) - a * N ∧ T (N : ℝ) - a * N ≤ 5 * L N at h constructor <;> linarith [h.1, h.2] theorem primePsi_lower (N : ℕ) : a * N - 5 * L N ≤ primePsi N := by exact (T_bounds N).1.trans (PrimeFactorial.T_nonneg_le_primePsi N).2 theorem primePsi_le_count_log (N : ℕ) : primePsi N ≤ (N : ℝ) * Real.log ((N : ℝ) + 1) := by unfold primePsi rw [sum_range_succ'] have hz : vonMangoldt 0 = 0 := by simp simp only [hz, add_zero, zero_add] calc _ ≤ ∑ n ∈ range N, Real.log ((N : ℝ) + 1) := by apply sum_le_sum intro n hn have hnN : n < N := mem_range.mp hn have hp : (0 : ℝ) < ((n + 1 : ℕ) : ℝ) := by positivity have hle : ((n + 1 : ℕ) : ℝ) ≤ (N : ℝ) + 1 := by exact_mod_cast (show n + 1 ≤ N + 1 by omega) exact ArithmeticFunction.vonMangoldt_le_log.trans (Real.log_le_log hp hle) _ = _ := by simp theorem sixth_log_drop (N : ℕ) (hN : 6 ≤ N) : L (N / 6) + 1 ≤ L N := by have hnat : 3 * (N / 6 + 1) ≤ N + 1 := by omega have hreal : (3 : ℝ) * ((N / 6 : ℕ) + 1 : ℝ) ≤ (N : ℝ) + 1 := by exact_mod_cast hnat have hp : (0 : ℝ) < ((N / 6 : ℕ) : ℝ) + 1 := by positivity have hlog := Real.log_le_log (show (0 : ℝ) < 3 * (((N / 6 : ℕ) : ℝ) + 1) by positivity) hreal rw [Real.log_mul (by norm_num : (3 : ℝ) ≠ 0) hp.ne'] at hlog unfold L linarith [FactorialWheel.log_three_lower] theorem sixth_square_drop (N : ℕ) (hN : 6 ≤ N) : L N ≤ (L N)^2 - (L (N / 6))^2 := by have hd := sixth_log_drop N hN have hM := L_ge_one (N / 6) have hN1 := L_ge_one N have hm := mul_nonneg (show 0 ≤ L N - L (N / 6) - 1 by linarith) (show 0 ≤ L N + L (N / 6) by linarith) nlinarith theorem primePsi_upper (N : ℕ) : primePsi N ≤ (6 / 5 : ℝ) * a * N + 5 * (L N)^2 := by induction N using Nat.strong_induction_on with | h N ih => by_cases hN : N < 6 · have hc := primePsi_le_count_log N have hN5 : (N : ℝ) ≤ 5 := by exact_mod_cast (show N ≤ 5 by omega) have hlog : 0 ≤ Real.log ((N : ℝ) + 1) := Real.log_nonneg (by have := Nat.cast_nonneg (α := ℝ) N; linarith) have ha := coefficient_nonneg have hmain : 0 ≤ (6 / 5 : ℝ) * a * N := by positivity unfold L have hm := mul_le_mul_of_nonneg_right hN5 hlog nlinarith · have hN6 : 6 ≤ N := by omega have hlt : N / 6 < N := Nat.div_lt_self (by omega) (by norm_num) have hprev := ih (N / 6) hlt have hrec := PrimeFactorial.primePsi_sub_sixth_le_T N have hT := (T_bounds N).2 have hdrop := sixth_square_drop N hN6 have hnat : 6 * (N / 6) ≤ N := by omega have hreal : (6 : ℝ) * (N / 6 : ℕ) ≤ (N : ℝ) := by exact_mod_cast hnat have hm := mul_le_mul_of_nonneg_left hreal coefficient_nonneg have hcoef : (6 / 5 : ℝ) * a * (N / 6 : ℕ) ≤ (1 / 5 : ℝ) * a * N := by nlinarith nlinarith theorem primePsi_two_sided (N : ℕ) : a * N - 5 * L N ≤ primePsi N ∧ primePsi N ≤ (6 / 5 : ℝ) * a * N + 5 * (L N)^2 := ⟨primePsi_lower N, primePsi_upper N⟩ end end PrimePsiBounds #print axioms PrimePsiBounds.L #print axioms PrimePsiBounds.L_ge_one #print axioms PrimePsiBounds.coefficient_nonneg #print axioms PrimePsiBounds.T_bounds #print axioms PrimePsiBounds.primePsi_lower #print axioms PrimePsiBounds.primePsi_le_count_log #print axioms PrimePsiBounds.sixth_log_drop #print axioms PrimePsiBounds.sixth_square_drop #print axioms PrimePsiBounds.primePsi_upper #print axioms PrimePsiBounds.primePsi_two_sided