/- Released under Apache 2.0; see adjacent LICENSE. New explicit finite cutoff/level arithmetic for the unchanged manuscript sieve. Imports only frozen EulerRatio and its credited dependencies. The equation(1) main-goal definition is a specification, not a theorem or an assumed input. -/ import EulerRatio namespace SieveParameters noncomputable section open scoped BigOperators open Finset Nat ManuscriptResidues def k : ℝ := 512 * Real.log 4 def threshold : ℝ := Real.exp (4096 * Real.log 4) def cutoff (y : ℝ) : ℕ := ⌊Real.exp (Real.log y / k)⌋₊ def level (y : ℝ) : ℝ := Real.exp (Real.log y / 16) def uniformExponent : ℝ := 20 * Real.log 4 * k + 80 * Real.log 4 def uniformConstant : ℝ := 2 * Real.exp uniformExponent theorem log_four_lower : (3 : ℝ) / 4 ≤ Real.log 4 := by have h := Real.one_sub_inv_le_log_of_pos (show (0 : ℝ) < 4 by norm_num) norm_num at h ⊢ exact h theorem k_pos : 0 < k := by unfold k; positivity /-- The real lower bound excludes negative y; log(y) alone would not do so. -/ theorem large_y_facts (y : ℝ) (hy : threshold ≤ y) : 0 < y ∧ 4096 * Real.log 4 ≤ Real.log y ∧ 3072 ≤ Real.log y ∧ 4 ≤ y := by have hp : 0 < y := (Real.exp_pos _).trans_le hy have ht : 4096 * Real.log 4 ≤ Real.log y := by have hh := Real.log_le_log (Real.exp_pos _) hy simpa only [threshold, Real.log_exp] using hh have hT : 3072 ≤ Real.log y := by nlinarith [log_four_lower] have h4 : 4 ≤ y := by have hh := Real.add_one_le_exp (4096 * Real.log 4) change Real.exp (4096 * Real.log 4) ≤ y at hy nlinarith [log_four_lower] exact ⟨hp, ht, hT, h4⟩ /-- Exact floor logarithm bounds for the selected natural cutoff. -/ theorem cutoff_log_bounds (y : ℝ) (hy : threshold ≤ y) : 2 ≤ cutoff y ∧ Real.log y / (2 * k) ≤ Real.log (cutoff y : ℝ) ∧ Real.log (cutoff y : ℝ) ≤ Real.log y / k := by have hY := large_y_facts y hy have hk := k_pos let t : ℝ := Real.log y / k have ht8 : 8 ≤ t := by apply (le_div_iff₀ hk).mpr change 8 * (512 * Real.log 4) ≤ Real.log y nlinarith [hY.2.1] have he2 : (2 : ℝ) ≤ Real.exp t := by linarith [Real.add_one_le_exp t] have hN : 2 ≤ cutoff y := (Nat.le_floor_iff (Real.exp_nonneg t)).mpr he2 have hNpos : (0 : ℝ) < cutoff y := by exact_mod_cast (show 0 < cutoff y by omega) have hfloor : Real.exp t / 2 ≤ (cutoff y : ℝ) := by have hh := Nat.lt_floor_add_one (Real.exp t) change Real.exp t < (cutoff y : ℝ) + 1 at hh linarith have hlow := Real.log_le_log (div_pos (Real.exp_pos t) (by norm_num : (0 : ℝ) < 2)) hfloor rw [Real.log_div (Real.exp_pos t).ne' (by norm_num : (2 : ℝ) ≠ 0), Real.log_exp] at hlow have hl2 : Real.log (2 : ℝ) ≤ 1 := by have hh := Real.log_le_sub_one_of_pos (show (0 : ℝ) < 2 by norm_num) norm_num at hh exact hh have hhalf : Real.log y / (2 * k) = t / 2 := by dsimp [t]; ring have hlower : Real.log y / (2 * k) ≤ Real.log (cutoff y : ℝ) := by rw [hhalf] linarith have hupper := Real.log_le_log hNpos (Nat.floor_le (Real.exp_nonneg t)) rw [Real.log_exp] at hupper exact ⟨hN, hlower, hupper⟩ /-- The explicit selected level satisfies the already-proved denominator scale. -/ theorem level_scale (y : ℝ) (hy : threshold ≤ y) : 1 < level y ∧ 16 * Real.log 4 * (2 + Real.log (cutoff y : ℝ)) ≤ Real.log (level y) := by have hY := large_y_facts y hy have hb := cutoff_log_bounds y hy have hl4 : 0 < Real.log 4 := Real.log_pos (by norm_num) have hlevel : 1 < level y := by unfold level simpa using (Real.exp_lt_exp.mpr (show (0 : ℝ) < Real.log y / 16 by linarith [hY.2.2.1])) refine ⟨hlevel, ?_⟩ have hsum : 2 + Real.log (cutoff y : ℝ) ≤ 2 + Real.log y / k := by linarith [hb.2.2] have hm := mul_le_mul_of_nonneg_left hsum (show 0 ≤ 16 * Real.log 4 by positivity) have he : 16 * Real.log 4 * (2 + Real.log y / k) = 32 * Real.log 4 + Real.log y / 32 := by unfold k field_simp ring rw [he] at hm rw [level, Real.log_exp] nlinarith [hY.2.1] /-- Actual square-root cutoff/floor comparison, without replacing the prime family. -/ theorem log_cutoff_bound (y : ℝ) (hy : threshold ≤ y) : Real.log (max 2 ⌊Real.sqrt y⌋₊ : ℕ) ≤ Real.log y / 2 := by have hY := large_y_facts y hy have hs : 2 ≤ Real.sqrt y := by nlinarith [Real.sqrt_nonneg y, Real.sq_sqrt hY.1.le, hY.2.2.2] have hz : ((max 2 ⌊Real.sqrt y⌋₊ : ℕ) : ℝ) ≤ Real.sqrt y := by rw [Nat.cast_max] exact max_le (by simpa using hs) (Nat.floor_le (Real.sqrt_nonneg y)) have hz0 : (0 : ℝ) < (max 2 ⌊Real.sqrt y⌋₊ : ℕ) := by exact_mod_cast (lt_of_lt_of_le (by norm_num : 0 < (2 : ℕ)) (le_max_left _ _)) have hh := Real.log_le_log hz0 hz simpa only [Real.log_sqrt hY.1.le] using hh /-- Uniform bound after the exact cutoff choice; no variable factor is called constant. -/ theorem ratio_exponent_le (y : ℝ) (hy : threshold ≤ y) : EulerRatio.ratioExponent y (cutoff y) ≤ uniformExponent := by have hY := large_y_facts y hy have hb := cutoff_log_bounds y hy have hk := k_pos have hl4 : 0 < Real.log 4 := Real.log_pos (by norm_num) have hNlog : 0 < Real.log (cutoff y : ℝ) := Real.log_pos (by exact_mod_cast (show 1 < cutoff y by omega)) have hTk : k ≤ Real.log y := by unfold k; nlinarith [hY.2.1] have hdiv : 1 ≤ Real.log y / k := (le_div_iff₀ hk).mpr (by simpa using hTk) have hB : 0 ≤ uniformExponent := by unfold uniformExponent; positivity unfold EulerRatio.ratioExponent apply (div_le_iff₀ hNlog).mpr calc _ ≤ 20 * Real.log 4 * (2 + Real.log y / 2) := by gcongr exact log_cutoff_bound y hy _ = 10 * Real.log 4 * Real.log y + 40 * Real.log 4 := by ring _ ≤ 10 * Real.log 4 * Real.log y + 40 * Real.log 4 * (Real.log y / k) := by exact _root_.add_le_add le_rfl (by simpa only [mul_one] using mul_le_mul_of_nonneg_left hdiv (show 0 ≤ 40 * Real.log 4 by positivity)) _ = uniformExponent * (Real.log y / (2 * k)) := by unfold uniformExponent field_simp ring _ ≤ uniformExponent * Real.log (cutoff y : ℝ) := mul_le_mul_of_nonneg_left hb.2.1 hB theorem actual_uniform_ratio (y z0 z1 : ℝ) (hy : threshold ≤ y) (hz0 : 3 < z0) : SieveCoarse.restrictedV y z0 z1 (cutoff y) / EulerRatio.fullV y z0 z1 ≤ Real.exp uniformExponent := (EulerRatio.actual_ratio_le_exp y z0 z1 hz0 (cutoff y) (cutoff_log_bounds y hy).1).trans (Real.exp_le_exp.mpr (ratio_exponent_le y hy)) /-- An elementary exponential lower bound gives an absolute small error budget. -/ theorem error_budget_T (T : ℝ) (hT : 3072 ≤ T) : 4 * (Real.exp (T / 16)) ^ 5 ≤ Real.exp T / (12 * T) := by have ht0 : 0 ≤ T := by linarith have hquad := Real.quadratic_le_exp_of_nonneg (show 0 ≤ 11 * T / 16 by positivity) have hprod : 0 ≤ T * (T - 3072) := mul_nonneg ht0 (sub_nonneg.mpr hT) have h48 : 48 * T ≤ Real.exp (11 * T / 16) := by nlinarith have he : (Real.exp (T / 16)) ^ 5 = Real.exp (5 * T / 16) := by rw [← Real.exp_nat_mul] congr 1 norm_num <;> ring rw [he] apply (le_div_iff₀ (show 0 < 12 * T by linarith)).mpr calc _ = 48 * T * Real.exp (5 * T / 16) := by ring _ ≤ Real.exp (11 * T / 16) * Real.exp (5 * T / 16) := mul_le_mul_of_nonneg_right h48 (Real.exp_nonneg _) _ = Real.exp T := by rw [← Real.exp_add]; congr 1; ring theorem actual_error_budget (y : ℝ) (hy : threshold ≤ y) : 4 * level y ^ 5 ≤ y / (12 * Real.log y) := by have hY := large_y_facts y hy simpa only [level, Real.exp_log hY.1] using error_budget_T (Real.log y) hY.2.2.1 /-- Quantitatively useful finite full-product estimate with an actual uniform constant. -/ theorem actual_uniform_survivor (X : ℕ) (y z0 z1 : ℝ) (hy : threshold ≤ y) (hz0 : 3 < z0) : (SieveInterface.survivorCount X y z0 z1 : ℝ) ≤ uniformConstant * (X : ℝ) * EulerRatio.fullV y z0 z1 + y / (12 * Real.log y) := by have hs := level_scale y hy apply (EulerRatio.actual_survivor_full_bound X y z0 z1 (level y) hz0 (cutoff y) (cutoff_log_bounds y hy).1 hs.1 hs.2).trans apply _root_.add_le_add · calc _ ≤ 2 * (X : ℝ) * Real.exp uniformExponent * EulerRatio.fullV y z0 z1 := by gcongr · exact (EulerRatio.fullV_pos y z0 z1 hz0).le · exact ratio_exponent_le y hy _ = _ := by unfold uniformConstant; ring · exact actual_error_budget y hy /-- Full covering prime family in equation(1), distinct from auxiliary sqrt(y). -/ def mainPrimes (y : ℝ) : Finset ℕ := primeCutoff y theorem mem_mainPrimes (y : ℝ) (hy : 0 ≤ y) (p : ℕ) : p ∈ mainPrimes y ↔ p.Prime ∧ (p : ℝ) ≤ y := mem_primeCutoff y hy p /-- Literal natural-log shape in manuscript equation(1). -/ def mainShape (y : ℝ) : ℝ := y * (Real.log y) ^ 3 * (Real.log (Real.log (Real.log y))) ^ 2 / (Real.log (Real.log y)) ^ 4 /-- Exact eventual equation(1) specification. NOT a proved theorem or analytic input. -/ def ManuscriptMainGoal : Prop := ∃ c : ℝ, 0 < c ∧ ∃ y0 : ℝ, ∀ y : ℝ, y0 ≤ y → c * mainShape y ≤ (KKFiniteCoreDraft.G2 (mainPrimes y) : ℝ) end end SieveParameters #print axioms SieveParameters.k #print axioms SieveParameters.threshold #print axioms SieveParameters.cutoff #print axioms SieveParameters.level #print axioms SieveParameters.uniformExponent #print axioms SieveParameters.uniformConstant #print axioms SieveParameters.log_four_lower #print axioms SieveParameters.k_pos #print axioms SieveParameters.large_y_facts #print axioms SieveParameters.cutoff_log_bounds #print axioms SieveParameters.level_scale #print axioms SieveParameters.log_cutoff_bound #print axioms SieveParameters.ratio_exponent_le #print axioms SieveParameters.actual_uniform_ratio #print axioms SieveParameters.error_budget_T #print axioms SieveParameters.actual_error_budget #print axioms SieveParameters.actual_uniform_survivor #print axioms SieveParameters.mainPrimes #print axioms SieveParameters.mem_mainPrimes #print axioms SieveParameters.mainShape #print axioms SieveParameters.ManuscriptMainGoal