/- Released under Apache-2.0; see adjacent LICENSE. Literal real dyadic reserved-prime cardinality from the finite factorial wheel. Explicit error threshold; no PNT or assumed prime supply. -/ import PrimePowerTail namespace PrimeReserveBudget noncomputable section open scoped BigOperators open Finset open FactorialWheel (a) open PrimeFactorial (primePsi) open PrimePowerTail (primeThetaNat) def Lplus (y : ℝ) : ℝ := 1 + Real.log (y + 1) def supplyThreshold : ℝ := max ((300000 : ℝ)^4) (Real.exp 1) def dyadicPrimes (y : ℝ) : Finset ℕ := (Ioc ⌊y / 2⌋₊ ⌊y⌋₊).filter Nat.Prime theorem a_le_two : a ≤ 2 := by have h2 := Real.log_le_sub_one_of_pos (by norm_num : (0 : ℝ) < 2) have h3 := Real.log_le_sub_one_of_pos (by norm_num : (0 : ℝ) < 3) have h5 := Real.log_le_sub_one_of_pos (by norm_num : (0 : ℝ) < 5) unfold FactorialWheel.a linarith theorem scalar_error_absorption (y : ℝ) (hy : (300000 : ℝ)^4 ≤ y) (hlog : 1 ≤ Real.log y) : a + 5 * Lplus y + 5 * (Lplus y)^2 + 2 * Real.sqrt y * (Real.log y)^2 ≤ y / 90 := by have hypos : 0 < y := lt_of_lt_of_le (by norm_num : (0 : ℝ) < 300000^4) hy have hy1 : 1 ≤ y := by nlinarith [hy] let S := Real.sqrt (Real.sqrt y) have hS0 : 0 ≤ S := Real.sqrt_nonneg _ have hS2 : S^2 = Real.sqrt y := Real.sq_sqrt (Real.sqrt_nonneg y) have hSy : S^4 = y := by calc _ = (S^2)^2 := by ring _ = (Real.sqrt y)^2 := by rw [hS2] _ = y := Real.sq_sqrt hypos.le have hroot : (300000 : ℝ)^2 ≤ Real.sqrt y := by have hs := Real.sqrt_nonneg y have hs2 := Real.sq_sqrt hypos.le nlinarith [hy] have hS : 300000 ≤ S := by nlinarith have hS1 : 1 ≤ S := by linarith have hSpos : 0 < S := by linarith have hr0 : 0 ≤ Real.sqrt S := Real.sqrt_nonneg _ have hr2 : (Real.sqrt S)^2 = S := Real.sq_sqrt hS0 have hrS : Real.sqrt S ≤ S := by nlinarith have hlogS : Real.log S = Real.log y / 4 := by dsimp [S] rw [Real.log_sqrt (Real.sqrt_nonneg y), Real.log_sqrt hypos.le] ring have hl : Real.log y ≤ 8 * Real.sqrt S := by have ht := SmoothParameters.log_le_two_sqrt S hSpos linarith have hl0 : 0 ≤ Real.log y := by linarith have hl2 : (Real.log y)^2 ≤ 64 * S := by have hm := mul_nonneg (show 0 ≤ 8 * Real.sqrt S - Real.log y by linarith) (show 0 ≤ 8 * Real.sqrt S + Real.log y by positivity) nlinarith have hl2upper := Real.log_le_sub_one_of_pos (by norm_num : (0 : ℝ) < 2) have hplus : Lplus y ≤ Real.log y + 2 := by have hh := Real.log_le_log (show 0 < y + 1 by linarith) (show y + 1 ≤ 2 * y by linarith) rw [Real.log_mul (by norm_num : (2 : ℝ) ≠ 0) hypos.ne'] at hh unfold Lplus linarith have hplus0 : 0 ≤ Lplus y := by have hh := Real.log_nonneg (show 1 ≤ y + 1 by linarith) unfold Lplus linarith have hplusS : Lplus y ≤ 10 * S := by linarith have hpluslog : Lplus y ≤ 3 * Real.log y := by linarith have hplus2 : (Lplus y)^2 ≤ 576 * S := by have hm := mul_nonneg (show 0 ≤ 3 * Real.log y - Lplus y by linarith) (show 0 ≤ 3 * Real.log y + Lplus y by positivity) nlinarith have ht : 2 * Real.sqrt y * (Real.log y)^2 ≤ 128 * S^3 := by have hm := mul_le_mul_of_nonneg_left hl2 (show 0 ≤ 2 * S^2 by positivity) rw [← hS2] nlinarith have haS : a ≤ 2 * S := by linarith [a_le_two] have hlin : a + 5 * Lplus y + 5 * (Lplus y)^2 ≤ 2932 * S := by linarith have hScube : S ≤ S^3 := by simpa using pow_le_pow_right₀ hS1 (by norm_num : (1 : ℕ) ≤ 3) have hE : a + 5 * Lplus y + 5 * (Lplus y)^2 + 2 * Real.sqrt y * (Real.log y)^2 ≤ 3060 * S^3 := by nlinarith have hm := mul_le_mul_of_nonneg_right (show (275400 : ℝ) ≤ S by linarith) (show 0 ≤ S^3 by positivity) have hfinal : 3060 * S^3 ≤ y / 90 := by nlinarith [hSy] exact hE.trans hfinal theorem theta_floor (y : ℝ) : PrimeLog.theta (⌊y⌋₊ : ℝ) = PrimeLog.theta y := by simp [PrimeLog.theta] theorem theta_dyadic_lower (y : ℝ) (hy : 4 ≤ y) : (2 * a / 5) * y - (a + 5 * Lplus y + 5 * (Lplus y)^2 + 2 * Real.sqrt y * (Real.log y)^2) ≤ PrimeLog.theta y - PrimeLog.theta (y / 2) := by let N := ⌊y⌋₊ let M := ⌊y / 2⌋₊ have hy0 : 0 ≤ y := by linarith have hN : 2 ≤ N := (Nat.le_floor_iff hy0).mpr (by norm_num; linarith) have hM : 2 ≤ M := (Nat.le_floor_iff (show 0 ≤ y / 2 by linarith)).mpr (by norm_num; linarith) have hNcast : (N : ℝ) ≤ y := Nat.floor_le hy0 have hMcast : (M : ℝ) ≤ y / 2 := Nat.floor_le (by linarith) have hNlow : y - 1 ≤ (N : ℝ) := by have := Nat.lt_floor_add_one y; dsimp [N]; linarith have hLplus : 0 ≤ Lplus y := by have := Real.log_nonneg (show 1 ≤ y + 1 by linarith) unfold Lplus; linarith have hLN : PrimePsiBounds.L N ≤ Lplus y := by have hh := Real.log_le_log (show (0 : ℝ) < (N : ℝ) + 1 by positivity) (show (N : ℝ) + 1 ≤ y + 1 by linarith) unfold PrimePsiBounds.L Lplus linarith have hLM : PrimePsiBounds.L M ≤ Lplus y := by have hh := Real.log_le_log (show (0 : ℝ) < (M : ℝ) + 1 by positivity) (show (M : ℝ) + 1 ≤ y + 1 by linarith) unfold PrimePsiBounds.L Lplus linarith have hLM2 : (PrimePsiBounds.L M)^2 ≤ (Lplus y)^2 := by have hm := mul_nonneg (show 0 ≤ Lplus y - PrimePsiBounds.L M by linarith) (show 0 ≤ Lplus y + PrimePsiBounds.L M by linarith [PrimePsiBounds.L_ge_one M]) nlinarith have hNpos : (0 : ℝ) < N := by exact_mod_cast (show 0 < N by omega) have hlogN0 : 0 ≤ Real.log (N : ℝ) := Real.log_nonneg (by exact_mod_cast (show 1 ≤ N by omega)) have hlogy0 : 0 ≤ Real.log y := Real.log_nonneg (by linarith) have hlogN := Real.log_le_log hNpos hNcast have hlogN2 : (Real.log (N : ℝ))^2 ≤ (Real.log y)^2 := by have hm := mul_nonneg (show 0 ≤ Real.log y - Real.log (N : ℝ) by linarith) (show 0 ≤ Real.log y + Real.log (N : ℝ) by linarith) nlinarith have htailmono : 2 * Real.sqrt (N : ℝ) * (Real.log (N : ℝ))^2 ≤ 2 * Real.sqrt y * (Real.log y)^2 := by have hm := mul_le_mul (Real.sqrt_le_sqrt hNcast) hlogN2 (sq_nonneg _) (Real.sqrt_nonneg y) nlinarith have ha := PrimePsiBounds.coefficient_nonneg have hmainN := mul_le_mul_of_nonneg_left hNlow ha have hmainM := mul_le_mul_of_nonneg_left hMcast (show 0 ≤ (6 / 5 : ℝ) * a by positivity) have hlow := PrimePsiBounds.primePsi_lower N have hupp := PrimePsiBounds.primePsi_upper M have htailN := (PrimePowerTail.actual_theta_tail_bound N hN).2 have htailM := (PrimePowerTail.actual_theta_tail_bound M hM).1 have htN : PrimeLog.theta (N : ℝ) = PrimeLog.theta y := theta_floor y have htM : PrimeLog.theta (M : ℝ) = PrimeLog.theta (y / 2) := theta_floor (y / 2) rw [htN] at htailN rw [htM] at htailM nlinarith theorem theta_dyadic_budget (y : ℝ) (hy : supplyThreshold ≤ y) : y / 3 ≤ PrimeLog.theta y - PrimeLog.theta (y / 2) := by have hbig : (300000 : ℝ)^4 ≤ y := (le_max_left _ _).trans hy have hexp : Real.exp 1 ≤ y := (le_max_right _ _).trans hy have hypos : 0 < y := (Real.exp_pos 1).trans_le hexp have hlog : 1 ≤ Real.log y := by have hh := Real.log_le_log (Real.exp_pos 1) hexp simpa using hh have hy4 : 4 ≤ y := by nlinarith [hbig] have hbound := theta_dyadic_lower y hy4 have herr := scalar_error_absorption y hbig hlog have hmargin := mul_le_mul_of_nonneg_right FactorialWheel.a_margin.2 hypos.le nlinarith theorem theta_difference_eq_sum (y : ℝ) (hy : 0 ≤ y) : PrimeLog.theta y - PrimeLog.theta (y / 2) = ∑ p ∈ dyadicPrimes y, Real.log (p : ℝ) := by have hMN : ⌊y / 2⌋₊ ≤ ⌊y⌋₊ := by apply (Nat.le_floor_iff hy).mpr exact (Nat.floor_le (show 0 ≤ y / 2 by linarith)).trans (by linarith) have hu : ((range (⌊y / 2⌋₊ + 1)).filter Nat.Prime) ∪ dyadicPrimes y = (range (⌊y⌋₊ + 1)).filter Nat.Prime := by ext p by_cases hp : p.Prime · simp only [dyadicPrimes, mem_union, mem_filter, mem_range, mem_Ioc, hp, and_true] omega · simp [dyadicPrimes, hp] have hd : Disjoint ((range (⌊y / 2⌋₊ + 1)).filter Nat.Prime) (dyadicPrimes y) := by apply disjoint_left.mpr intro p hp hq have hp := (mem_filter.mp hp).1 have hq := (mem_filter.mp hq).1 simp only [mem_range] at hp simp only [mem_Ioc] at hq omega have he := (sum_union (f := fun p : ℕ => Real.log (p : ℝ)) hd).symm rw [hu] at he change primeThetaNat ⌊y / 2⌋₊ + (∑ p ∈ dyadicPrimes y, Real.log (p : ℝ)) = primeThetaNat ⌊y⌋₊ at he rw [PrimePowerTail.primeThetaNat_eq_theta, PrimePowerTail.primeThetaNat_eq_theta, theta_floor, theta_floor] at he linarith theorem dyadicPrimes_subset_reserved (y : ℝ) (hy : 0 ≤ y) : dyadicPrimes y ⊆ EarlyCover.reservedPrimes y := by intro p hp rcases mem_filter.mp hp with ⟨hinterval, hprime⟩ rcases mem_Ioc.mp hinterval with ⟨hlo, hhi⟩ have hupper : (p : ℝ) ≤ y := (show (p : ℝ) ≤ (⌊y⌋₊ : ℝ) by exact_mod_cast hhi).trans (Nat.floor_le hy) have hplow : (⌊y / 2⌋₊ : ℝ) + 1 ≤ p := by exact_mod_cast (show ⌊y / 2⌋₊ + 1 ≤ p by omega) have hlower : y / 2 ≤ (p : ℝ) := by have := Nat.lt_floor_add_one (y / 2); linarith exact mem_filter.mpr ⟨(ManuscriptResidues.mem_primeCutoff y hy p).mpr ⟨hprime, hupper⟩, hlower⟩ theorem theta_difference_le_reserved_log (y : ℝ) (hy : 1 ≤ y) : PrimeLog.theta y - PrimeLog.theta (y / 2) ≤ ((EarlyCover.reservedPrimes y).card : ℝ) * Real.log y := by have hy0 : 0 ≤ y := by linarith have hlog : 0 ≤ Real.log y := Real.log_nonneg hy rw [theta_difference_eq_sum y hy0] calc _ ≤ ∑ p ∈ dyadicPrimes y, Real.log y := by apply sum_le_sum intro p hp have hr := dyadicPrimes_subset_reserved y hy0 hp have hc := (ManuscriptResidues.mem_primeCutoff y hy0 p).mp (mem_filter.mp hr).1 exact Real.log_le_log (by exact_mod_cast hc.1.pos) hc.2 _ = ((dyadicPrimes y).card : ℝ) * Real.log y := by simp _ ≤ _ := mul_le_mul_of_nonneg_right (by exact_mod_cast card_le_card (dyadicPrimes_subset_reserved y hy0)) hlog theorem actual_reserved_supply (y : ℝ) (hy : supplyThreshold ≤ y) : y / (3 * Real.log y) ≤ ((EarlyCover.reservedPrimes y).card : ℝ) := by have hexp : Real.exp 1 ≤ y := (le_max_right _ _).trans hy have hypos : 0 < y := (Real.exp_pos 1).trans_le hexp have hlog : 1 ≤ Real.log y := by have hh := Real.log_le_log (Real.exp_pos 1) hexp simpa using hh have hy1 : 1 ≤ y := by have hh : 1 < Real.exp 1 := by simpa using (Real.exp_lt_exp.mpr (show (0 : ℝ) < 1 by norm_num)) linarith have hl := theta_dyadic_budget y hy have hu := theta_difference_le_reserved_log y hy1 apply (div_le_iff₀ (show 0 < 3 * Real.log y by positivity)).2 nlinarith theorem eventual_actual_reserved_supply : ∃ Y : ℝ, 0 < Y ∧ ∀ y : ℝ, Y ≤ y → y / (3 * Real.log y) ≤ ((EarlyCover.reservedPrimes y).card : ℝ) := by refine ⟨supplyThreshold, ?_, actual_reserved_supply⟩ exact (Real.exp_pos 1).trans_le (le_max_right _ _) end end PrimeReserveBudget #print axioms PrimeReserveBudget.Lplus #print axioms PrimeReserveBudget.supplyThreshold #print axioms PrimeReserveBudget.dyadicPrimes #print axioms PrimeReserveBudget.a_le_two #print axioms PrimeReserveBudget.scalar_error_absorption #print axioms PrimeReserveBudget.theta_floor #print axioms PrimeReserveBudget.theta_dyadic_lower #print axioms PrimeReserveBudget.theta_dyadic_budget #print axioms PrimeReserveBudget.theta_difference_eq_sum #print axioms PrimeReserveBudget.dyadicPrimes_subset_reserved #print axioms PrimeReserveBudget.theta_difference_le_reserved_log #print axioms PrimeReserveBudget.actual_reserved_supply #print axioms PrimeReserveBudget.eventual_actual_reserved_supply