/- Released under Apache-2.0; see adjacent LICENSE. Exact equation13 X=m+2, Z=z1, and u=log(X)/log(Z). This module proves finite/quantitative range prerequisites only, never a smooth-number estimate. Original local dependencies and pinned Mathlib definitions remain unchanged. -/ import ReserveBudget namespace SmoothParameters noncomputable section open ManuscriptParameters def X (y A : ℝ) : ℕ := m y (chooseB A) + 2 def Z (y A : ℝ) : ℝ := z1 y A def u (y A : ℝ) : ℝ := Real.log (X y A : ℝ) / Real.log (Z y A) def threshold (A B : ℝ) : ℝ := max (ManuscriptParameters.threshold A) (Real.exp (max (256 * B) ((1024 * A ^ 3) ^ 2))) theorem smoothSet_eq (N : ℕ) (z : ℝ) (hz : 0 ≤ z) : EarlyCover.smoothSet N z = Nat.smoothNumbersUpTo N (⌊z⌋₊ + 1) := by classical ext n rw [EarlyCover.smoothSet, Finset.mem_filter, Finset.mem_Ioc, Nat.mem_smoothNumbersUpTo] have he : EarlyCover.Smooth z n ↔ n ∈ Nat.smoothNumbers (⌊z⌋₊ + 1) := by rw [Nat.mem_smoothNumbers'] unfold EarlyCover.Smooth constructor · intro h p hp hd exact Nat.lt_succ_of_le ((Nat.le_floor_iff hz).mpr (h p hp hd)) · intro h p hp hd exact (Nat.le_floor_iff hz).mp (Nat.le_of_lt_succ (h p hp hd)) constructor · rintro ⟨⟨hn, hN⟩, hs⟩ exact ⟨hN, he.mp hs⟩ · rintro ⟨hN, hs⟩ exact ⟨⟨Nat.pos_of_ne_zero (Nat.ne_zero_of_mem_smoothNumbers hs), hN⟩, he.mpr hs⟩ theorem Psi_eq (N : ℕ) (z : ℝ) (hz : 0 ≤ z) : EarlyCover.Psi N z = (Nat.smoothNumbersUpTo N (⌊z⌋₊ + 1)).card := by rw [EarlyCover.Psi, smoothSet_eq N z hz] theorem log_le_two_sqrt (t : ℝ) (ht : 0 < t) : Real.log t ≤ 2 * Real.sqrt t := by have hs : 0 < Real.sqrt t := Real.sqrt_pos.mpr ht have h := Real.log_le_sub_one_of_pos hs rw [Real.log_sqrt ht.le] at h linarith theorem threshold_facts (y A B : ℝ) (hA : 4 ≤ A) (hB : 1 ≤ B) (hy : threshold A B ≤ y) : ManuscriptParameters.threshold A ≤ y ∧ 256 * B ≤ L y ∧ (1024 * A ^ 3) ^ 2 ≤ L y := by have hm : Real.exp (max (256 * B) ((1024 * A ^ 3) ^ 2)) ≤ y := (le_max_right _ _).trans hy have hh := Real.log_le_log (Real.exp_pos _) hm rw [Real.log_exp] at hh exact ⟨(le_max_left _ _).trans hy, (le_max_left _ _).trans hh, (le_max_right _ _).trans hh⟩ /-- Both floor inequalities are used; the original additive2 is essential to the lower bound. -/ theorem mass_bounds (y A B : ℝ) (hA : 4 ≤ A) (hB : 1 ≤ B) (hy : threshold A B ≤ y) : y ≤ ((m y B + 2 : ℕ) : ℝ) ∧ ((m y B + 2 : ℕ) : ℝ) ≤ 2 * y * (L y) ^ 3 := by have ht := threshold_facts y A B hA hB hy have hf := large_facts y A hA ht.1 have hY := hf.1 have hL : 0 < L y := by linarith [hf.2.1] have hT : 0 < L2 y := by linarith [hf.2.2.1] have hR : 0 < L3 y := by linarith [hf.2.2.2.1] have hB0 : 0 < B := by linarith let q := y / B * (L y) ^ 3 * (L3 y) ^ 2 / (L2 y) ^ 4 have hq0 : 0 ≤ q := by dsimp [q]; positivity have hq : (L2 y) ^ 4 ≤ 64 * L y := by have hh := quartic_le_exp (L2 y) hT.le simpa only [L2, Real.exp_log hL] using (show (L2 y) ^ 4 ≤ 64 * Real.exp (L2 y) by linarith) have hR2 : (1 / 4 : ℝ) ≤ (L3 y) ^ 2 := by nlinarith [hf.2.2.2.1] have hL2 : 256 * B ≤ (L y) ^ 2 := by have hh := mul_nonneg (sub_nonneg.mpr ht.2.1) (show 0 ≤ L y + 256 * B by positivity) nlinarith [sq_nonneg B] have hratio : 1 ≤ (L y) ^ 3 * (L3 y) ^ 2 / (B * (L2 y) ^ 4) := by apply (le_div_iff₀ (mul_pos hB0 (pow_pos hT 4))).mpr have hh := mul_le_mul_of_nonneg_left hR2 (pow_nonneg hL.le 3) have hh2 := mul_nonneg (sub_nonneg.mpr hL2) hL.le have hh3 := mul_nonneg (sub_nonneg.mpr hq) hB0.le nlinarith have hq_ge : y ≤ q := by calc y = y * 1 := (mul_one y).symm _ ≤ y * ((L y) ^ 3 * (L3 y) ^ 2 / (B * (L2 y) ^ 4)) := mul_le_mul_of_nonneg_left hratio hY.le _ = q := by dsimp [q]; ring have hlo : q < (m y B : ℝ) + 1 := by exact Nat.lt_floor_add_one q have hRle : L3 y ≤ L2 y := by change Real.log (L2 y) ≤ L2 y linarith [Real.log_le_sub_one_of_pos hT] have hR2T : (L3 y) ^ 2 ≤ (L2 y) ^ 2 := by nlinarith [mul_nonneg (sub_nonneg.mpr hRle) (add_nonneg hR.le hT.le)] have ht2 : 1 ≤ (L2 y) ^ 2 := by nlinarith [hf.2.2.1] have ht4 : (L2 y) ^ 2 ≤ (L2 y) ^ 4 := by nlinarith [mul_nonneg (sq_nonneg (L2 y)) (sub_nonneg.mpr ht2)] have hfrac : (L3 y) ^ 2 / (B * (L2 y) ^ 4) ≤ 1 := by apply (div_le_iff₀ (mul_pos hB0 (pow_pos hT 4))).mpr nlinarith [mul_nonneg (sub_nonneg.mpr hB) (pow_nonneg hT.le 4)] have hm : (m y B : ℝ) ≤ y * (L y) ^ 3 := by apply (Nat.floor_le hq0).trans calc q = (y * (L y) ^ 3) * ((L3 y) ^ 2 / (B * (L2 y) ^ 4)) := by dsimp [q]; ring _ ≤ (y * (L y) ^ 3) * 1 := mul_le_mul_of_nonneg_left hfrac (by positivity) _ = _ := mul_one _ have hpow : 1 ≤ (L y) ^ 3 := by nlinarith [mul_nonneg (show 0 ≤ L y - 1 by linarith [hf.2.1]) (sq_nonneg (L y))] constructor <;> simp only [Nat.cast_add, Nat.cast_ofNat] <;> nlinarith [hf.2.2.2.2] theorem log_mass_bounds (y A B : ℝ) (hA : 4 ≤ A) (hB : 1 ≤ B) (hy : threshold A B ≤ y) : L y ≤ Real.log ((m y B + 2 : ℕ) : ℝ) ∧ Real.log ((m y B + 2 : ℕ) : ℝ) ≤ L y + 3 * L2 y + Real.log 2 := by have ht := threshold_facts y A B hA hB hy have hf := large_facts y A hA ht.1 have hL : 0 < L y := by linarith [hf.2.1] have hm := mass_bounds y A B hA hB hy have hn : 0 < ((m y B + 2 : ℕ) : ℝ) := by positivity refine ⟨Real.log_le_log hf.1 hm.1, ?_⟩ have hh := Real.log_le_log hn hm.2 rw [Real.log_mul (mul_ne_zero (by norm_num : (2 : ℝ) ≠ 0) hf.1.ne') (by positivity : (L y) ^ 3 ≠ 0), Real.log_mul (by norm_num : (2 : ℝ) ≠ 0) hf.1.ne', Real.log_pow] at hh change _ ≤ Real.log 2 + L y + 3 * L2 y at hh linarith theorem chosen_B_ge_one (A : ℝ) : 1 ≤ chooseB A := by have hC : 0 ≤ RealBand.survivorConstant := by unfold RealBand.survivorConstant RealBand.productConstant RealBand.ordinaryConstant SieveParameters.uniformConstant positivity unfold chooseB have hh : 0 ≤ 6 * RealBand.survivorConstant * A ^ 4 := by positivity linarith theorem actual_Psi_eq (y A : ℝ) : EarlyCover.Psi (X y A) (Z y A) = (Nat.smoothNumbersUpTo (X y A) (⌊Z y A⌋₊ + 1)).card := Psi_eq _ _ (Real.exp_nonneg _) theorem u_identity (y A : ℝ) (hA : 4 ≤ A) (hy : threshold A (chooseB A) ≤ y) : u y A = (Real.log (X y A : ℝ) / L y) * (A * L2 y / L3 y) := by have ht := threshold_facts y A (chooseB A) hA (chosen_B_ge_one A) hy have hf := large_facts y A hA ht.1 have hL : 0 < L y := by linarith [hf.2.1] have hT : 0 < L2 y := by linarith [hf.2.2.1] have hR : 0 < L3 y := by linarith [hf.2.2.2.1] have hA0 : 0 < A := by linarith unfold u Z z1 rw [Real.log_exp] field_simp [hL.ne', hT.ne', hR.ne', hA0.ne'] /-- Quantitative logX/L control, with a positive denominator and an explicit error. -/ theorem log_ratio_bounds (y A : ℝ) (hA : 4 ≤ A) (hy : threshold A (chooseB A) ≤ y) : 1 ≤ Real.log (X y A : ℝ) / L y ∧ Real.log (X y A : ℝ) / L y ≤ 1 + 7 / Real.sqrt (L y) ∧ Real.log (X y A : ℝ) / L y ≤ 2 := by have ht := threshold_facts y A (chooseB A) hA (chosen_B_ge_one A) hy have hf := large_facts y A hA ht.1 have hL : 0 < L y := by linarith [hf.2.1] have hs : 0 < Real.sqrt (L y) := Real.sqrt_pos.mpr hL have hs48 : 48 ≤ Real.sqrt (L y) := by nlinarith [Real.sq_sqrt hL.le, Real.sqrt_nonneg (L y), hf.2.1] have hb := log_mass_bounds y A (chooseB A) hA (chosen_B_ge_one A) hy change L y ≤ Real.log (X y A : ℝ) ∧ Real.log (X y A : ℝ) ≤ L y + 3 * L2 y + Real.log 2 at hb have hl2 : L2 y ≤ 2 * Real.sqrt (L y) := log_le_two_sqrt (L y) hL have hlog2 : Real.log 2 ≤ 1 := by have h := Real.log_le_sub_one_of_pos (by norm_num : (0 : ℝ) < 2) norm_num at h ⊢; exact h have herror : 3 * L2 y + Real.log 2 ≤ 7 * Real.sqrt (L y) := by linarith have hupper : Real.log (X y A : ℝ) / L y ≤ 1 + 7 / Real.sqrt (L y) := by apply (div_le_iff₀ hL).mpr have he : (1 + 7 / Real.sqrt (L y)) * L y = L y + 7 * Real.sqrt (L y) := by field_simp [hs.ne']; nlinarith [Real.sq_sqrt hL.le] rw [he]; linarith [hb.2] refine ⟨(le_div_iff₀ hL).mpr (by simpa using hb.1), hupper, ?_⟩ have hseven : 7 / Real.sqrt (L y) ≤ 1 := (div_le_iff₀ hs).mpr (by linarith) linarith /-- The original growing-u input range is derived, not added as a hypothesis. -/ theorem u_range (y A : ℝ) (hA : 4 ≤ A) (hy : threshold A (chooseB A) ≤ y) : 1 ≤ u y A ∧ u y A ≤ Real.sqrt (Z y A) := by have ht := threshold_facts y A (chooseB A) hA (chosen_B_ge_one A) hy have hf := large_facts y A hA ht.1 have hA0 : 0 < A := by linarith have hL : 0 < L y := by linarith [hf.2.1] have hT : 0 < L2 y := by linarith [hf.2.2.1] have hR : 0 < L3 y := by linarith [hf.2.2.2.1] have hs : 0 < Real.sqrt (L y) := Real.sqrt_pos.mpr hL have hl2 : L2 y ≤ 2 * Real.sqrt (L y) := log_le_two_sqrt (L y) hL have hRle : L3 y ≤ L2 y := by change Real.log (L2 y) ≤ L2 y linarith [Real.log_le_sub_one_of_pos hT] have hr := log_ratio_bounds y A hA hy have hbase : 1 ≤ A * L2 y / L3 y := by apply (le_div_iff₀ hR).mpr nlinarith [mul_nonneg (show 0 ≤ A - 1 by linarith) hT.le] have hlow : 1 ≤ u y A := by rw [u_identity y A hA hy] nlinarith [mul_nonneg (sub_nonneg.mpr hr.1) (show 0 ≤ A * L2 y / L3 y by positivity)] have hup : u y A ≤ 4 * A * L2 y := by rw [u_identity y A hA hy] have hh : A * L2 y / L3 y ≤ 2 * A * L2 y := by apply (div_le_iff₀ hR).mpr nlinarith [mul_nonneg (mul_nonneg hA0.le hT.le) (sub_nonneg.mpr hf.2.2.2.1)] have hp := mul_le_mul_of_nonneg_right hr.2.2 (show 0 ≤ A * L2 y / L3 y by positivity) linarith have hlogZ : Real.sqrt (L y) / (4 * A) ≤ Real.log (Z y A) := by unfold Z z1; rw [Real.log_exp] apply (div_le_div_iff₀ (show 0 < 4 * A by positivity) (show 0 < A * L2 y by positivity)).mpr have hsq : Real.sqrt (L y) * L2 y ≤ 2 * L y := by nlinarith [mul_nonneg hs.le (sub_nonneg.mpr hl2), Real.sq_sqrt hL.le] have hp := mul_nonneg hL.le (sub_nonneg.mpr hf.2.2.2.1) nlinarith [mul_nonneg hA0.le (show 0 ≤ 2 * L y - Real.sqrt (L y) * L2 y by linarith)] have hzpos : 0 < Z y A := Real.exp_pos _ have hlogpos : 0 < Real.log (Z y A) := (div_pos hs (show 0 < 4 * A by positivity)).trans_le hlogZ have hexp := Real.quadratic_le_exp_of_nonneg (show 0 ≤ Real.log (Z y A) / 2 by positivity) have hsZ : Real.sqrt (Z y A) = Real.exp (Real.log (Z y A) / 2) := by rw [← Real.log_sqrt hzpos.le, Real.exp_log (Real.sqrt_pos.mpr hzpos)] have hquad : L y / (128 * A ^ 2) ≤ Real.sqrt (Z y A) := by rw [hsZ] have hsq : (Real.sqrt (L y) / (4 * A)) ^ 2 ≤ (Real.log (Z y A)) ^ 2 := by nlinarith [mul_nonneg (sub_nonneg.mpr hlogZ) (show 0 ≤ Real.log (Z y A) + Real.sqrt (L y) / (4 * A) by positivity)] have hid : (Real.sqrt (L y) / (4 * A)) ^ 2 / 8 = L y / (128 * A ^ 2) := by rw [div_pow, Real.sq_sqrt hL.le]; ring rw [← hid]; nlinarith have hsbig : 1024 * A ^ 3 ≤ Real.sqrt (L y) := by nlinarith [Real.sq_sqrt hL.le, Real.sqrt_nonneg (L y), ht.2.2] have hpoly : 4 * A * L2 y ≤ L y / (128 * A ^ 2) := by apply (le_div_iff₀ (show 0 < 128 * A ^ 2 by positivity)).mpr have hp := mul_nonneg hs.le (sub_nonneg.mpr hsbig) have hp2 := mul_nonneg (show 0 ≤ 512 * A ^ 3 by positivity) (sub_nonneg.mpr hl2) nlinarith [Real.sq_sqrt hL.le] exact ⟨hlow, hup.trans (hpoly.trans hquad)⟩ theorem eventual_log_ratio (A : ℝ) (hA : 4 ≤ A) (ε : ℝ) (hε : 0 < ε) : ∃ Y : ℝ, 0 < Y ∧ ∀ y : ℝ, Y ≤ y → |Real.log (X y A : ℝ) / L y - 1| ≤ ε := by let Y := max (threshold A (chooseB A)) (Real.exp ((7 / ε) ^ 2)) refine ⟨Y, (Real.exp_pos _).trans_le (le_max_right _ _), ?_⟩ intro y hy have ht : threshold A (chooseB A) ≤ y := (le_max_left _ _).trans hy have hb := log_ratio_bounds y A hA ht have hf := large_facts y A hA ((le_max_left _ _).trans ht) have hL : 0 < L y := by linarith [hf.2.1] have hs : 0 < Real.sqrt (L y) := Real.sqrt_pos.mpr hL have he : Real.exp ((7 / ε) ^ 2) ≤ y := (le_max_right _ _).trans hy have hl := Real.log_le_log (Real.exp_pos _) he rw [Real.log_exp] at hl change (7 / ε) ^ 2 ≤ L y at hl have hsq : 7 / ε ≤ Real.sqrt (L y) := by nlinarith [Real.sq_sqrt hL.le, Real.sqrt_nonneg (L y), div_pos (by norm_num : (0 : ℝ) < 7) hε] have hh : 7 / Real.sqrt (L y) ≤ ε := by apply (div_le_iff₀ hs).mpr have hm := (div_le_iff₀ hε).mp hsq nlinarith rw [abs_of_nonneg (by linarith [hb.1])] linarith [hb.2.1] /-- Quantitative growing-u lower bound, on the same exact equation13 objects. -/ theorem sqrt_loglog_le_u (y A : ℝ) (hA : 4 ≤ A) (hy : threshold A (chooseB A) ≤ y) : Real.sqrt (L2 y) ≤ u y A := by have ht := threshold_facts y A (chooseB A) hA (chosen_B_ge_one A) hy have hf := large_facts y A hA ht.1 have hT : 0 < L2 y := by linarith [hf.2.2.1] have hR : 0 < L3 y := by linarith [hf.2.2.2.1] have hs : 0 < Real.sqrt (L2 y) := Real.sqrt_pos.mpr hT have hlog : L3 y ≤ 2 * Real.sqrt (L2 y) := log_le_two_sqrt (L2 y) hT have hbase : Real.sqrt (L2 y) ≤ A * L2 y / L3 y := by apply (le_div_iff₀ hR).mpr have hh := mul_nonneg hs.le (sub_nonneg.mpr hlog) have ha := mul_nonneg (show 0 ≤ A - 2 by linarith) hT.le nlinarith [Real.sq_sqrt hT.le] rw [u_identity y A hA hy] have hr := log_ratio_bounds y A hA hy nlinarith [mul_nonneg (sub_nonneg.mpr hr.1) (show 0 ≤ A * L2 y / L3 y by positivity)] theorem eventual_u_growth (A : ℝ) (hA : 4 ≤ A) (R : ℝ) : ∃ Y : ℝ, 0 < Y ∧ ∀ y : ℝ, Y ≤ y → R ≤ u y A := by let Y := max (threshold A (chooseB A)) (Real.exp (Real.exp ((max 1 R) ^ 2))) refine ⟨Y, (Real.exp_pos _).trans_le (le_max_right _ _), ?_⟩ intro y hy have ht : threshold A (chooseB A) ≤ y := (le_max_left _ _).trans hy have he : Real.exp (Real.exp ((max 1 R) ^ 2)) ≤ y := (le_max_right _ _).trans hy have hl := Real.log_le_log (Real.exp_pos _) he rw [Real.log_exp] at hl have hl2 := Real.log_le_log (Real.exp_pos _) hl rw [Real.log_exp] at hl2 change (max 1 R) ^ 2 ≤ L2 y at hl2 have hf := large_facts y A hA ((le_max_left _ _).trans ht) have hT : 0 < L2 y := by linarith [hf.2.2.1] have hs : max 1 R ≤ Real.sqrt (L2 y) := by nlinarith [Real.sq_sqrt hT.le, Real.sqrt_nonneg (L2 y), le_max_left (1 : ℝ) R] exact (le_max_right _ _).trans (hs.trans (sqrt_loglog_le_u y A hA ht)) theorem eventual_Z_growth (A : ℝ) (hA : 4 ≤ A) (R : ℝ) : ∃ Y : ℝ, 0 < Y ∧ ∀ y : ℝ, Y ≤ y → R ≤ Z y A := by let Y := max (threshold A (chooseB A)) (Real.exp (max 1 R)) refine ⟨Y, (Real.exp_pos _).trans_le (le_max_right _ _), ?_⟩ intro y hy have ht : threshold A (chooseB A) ≤ y := (le_max_left _ _).trans hy have hp : ManuscriptParameters.threshold A ≤ y := (le_max_left _ _).trans ht have he : Real.exp (max 1 R) ≤ y := (le_max_right _ _).trans hy have hl := Real.log_le_log (Real.exp_pos _) he rw [Real.log_exp] at hl exact (le_max_right _ _).trans (hl.trans ((z0_ge_L y A hA hp).trans (z0_lt_z1 y A hA hp).le)) theorem eventual_u_range (A : ℝ) (hA : 4 ≤ A) : ∃ Y : ℝ, 0 < Y ∧ ∀ y : ℝ, Y ≤ y → 1 ≤ u y A ∧ u y A ≤ Real.sqrt (Z y A) := by refine ⟨threshold A (chooseB A), (Real.exp_pos _).trans_le (le_max_right _ _), ?_⟩ intro y hy exact u_range y A hA hy end end SmoothParameters #print axioms SmoothParameters.X #print axioms SmoothParameters.Z #print axioms SmoothParameters.u #print axioms SmoothParameters.threshold #print axioms SmoothParameters.smoothSet_eq #print axioms SmoothParameters.Psi_eq #print axioms SmoothParameters.log_le_two_sqrt #print axioms SmoothParameters.threshold_facts #print axioms SmoothParameters.mass_bounds #print axioms SmoothParameters.log_mass_bounds #print axioms SmoothParameters.chosen_B_ge_one #print axioms SmoothParameters.actual_Psi_eq #print axioms SmoothParameters.u_identity #print axioms SmoothParameters.log_ratio_bounds #print axioms SmoothParameters.u_range #print axioms SmoothParameters.eventual_log_ratio #print axioms SmoothParameters.sqrt_loglog_le_u #print axioms SmoothParameters.eventual_u_growth #print axioms SmoothParameters.eventual_Z_growth #print axioms SmoothParameters.eventual_u_range