/- Released under the Apache License 2.0; see adjacent LICENSE. Modified adaptation of OpenAI math, revision adc7f1241b42e322a6451854ab7e4b4c146bf78a: OAI/NumberTheory/TwoPoint/Bounds/SieveEulerTruncation.lean and OAI/NumberTheory/TotientAsymptotic/IntervalSieveDenominator.lean. The two finite Euler lemmas are adapted to the local namespace. The generic BoundingSieve denominator/odds/log-cutoff bridge and actual manuscript specialization below are modifications for the existing pinned environment. No foreign project imports or toolchain configuration are adopted. -/ import SelbergFinite import Mathlib.Algebra.BigOperators.Ring.Finset import Mathlib.Algebra.BigOperators.Group.Finset.Powerset import Mathlib.Analysis.SpecialFunctions.Log.Basic namespace SelbergEuler /-! A finite Euler product retains at least half its mass below a cutoff whenever its logarithmic moment is at most half that cutoff. -/ noncomputable section open Finset open scoped Classical lemma sieve_euler_log_moment {ι : Type*} (S : Finset ι) (g ℓ : ι → ℝ) (hg : ∀ p ∈ S, 0 ≤ g p) : (∑ T ∈ S.powerset, (∏ p ∈ T, g p) * (∑ p ∈ T, ℓ p)) = (∏ p ∈ S, (1 + g p)) * (∑ p ∈ S, g p / (1 + g p) * ℓ p) := by classical induction S using Finset.induction_on with | empty => simp | @insert a S ha ih => have hga : 0 ≤ g a := hg a (mem_insert_self _ _) have hgS : ∀ p ∈ S, 0 ≤ g p := fun p hp => hg p (mem_insert_of_mem hp) have hne : 1 + g a ≠ 0 := by positivity have hn (T : Finset ι) (hT : T ∈ S.powerset) : a ∉ T := fun h => ha ((mem_powerset.mp hT) h) have hins : (∑ T ∈ S.powerset, (∏ p ∈ insert a T, g p) * (∑ p ∈ insert a T, ℓ p)) = g a * ℓ a * (∏ p ∈ S, (1 + g p)) + g a * ((∏ p ∈ S, (1 + g p)) * (∑ p ∈ S, g p / (1 + g p) * ℓ p)) := by calc _ = ∑ T ∈ S.powerset, (g a * ℓ a * (∏ p ∈ T, g p) + g a * ((∏ p ∈ T, g p) * (∑ p ∈ T, ℓ p))) := by apply sum_congr rfl intro T hT rw [prod_insert (hn T hT), sum_insert (hn T hT)] ring _ = _ := by rw [sum_add_distrib, ← mul_sum, ← mul_sum, ← prod_one_add, ih hgS] rw [sum_powerset_insert ha, hins, ih hgS, prod_insert ha, sum_insert ha] field_simp ring lemma sieve_euler_truncation {ι : Type*} (S : Finset ι) (g ℓ : ι → ℝ) (hg : ∀ p ∈ S, 0 ≤ g p) (hℓ : ∀ p ∈ S, 0 ≤ ℓ p) {L : ℝ} (hL : 0 < L) (hmean : (∑ p ∈ S, g p / (1 + g p) * ℓ p) ≤ L / 2) : (∏ p ∈ S, (1 + g p)) / 2 ≤ ∑ T ∈ S.powerset with (∑ p ∈ T, ℓ p) ≤ L, ∏ p ∈ T, g p := by classical let Z := ∏ p ∈ S, (1 + g p) have hZ : 0 ≤ Z := prod_nonneg (fun p hp => by linarith [hg p hp]) have hweight (T : Finset ι) (hT : T ∈ S.powerset) : 0 ≤ ∏ p ∈ T, g p := prod_nonneg (fun p hp => hg p (mem_powerset.mp hT hp)) have hcost (T : Finset ι) (hT : T ∈ S.powerset) : 0 ≤ ∑ p ∈ T, ℓ p := sum_nonneg (fun p hp => hℓ p (mem_powerset.mp hT hp)) have htail : L * (∑ T ∈ S.powerset with ¬ (∑ p ∈ T, ℓ p) ≤ L, ∏ p ∈ T, g p) ≤ ∑ T ∈ S.powerset, (∏ p ∈ T, g p) * (∑ p ∈ T, ℓ p) := by rw [sum_filter, mul_sum] apply sum_le_sum intro T hT split_ifs with h · simpa using mul_nonneg (hweight T hT) (hcost T hT) · simpa only [mul_comm] using mul_le_mul_of_nonneg_left (le_of_lt (lt_of_not_ge h)) (hweight T hT) rw [sieve_euler_log_moment S g ℓ hg] at htail have hm := mul_le_mul_of_nonneg_left hmean hZ have htotal := sum_filter_add_sum_filter_not S.powerset (fun T => (∑ p ∈ T, ℓ p) ≤ L) (fun T => ∏ p ∈ T, g p) rw [← prod_one_add] at htotal dsimp [Z] at hZ hm nlinarith open BoundingSieve /-- Local Euler odds of the actual sieve density, not the manuscript function g. -/ def odds (s : BoundingSieve) (p : ℕ) : ℝ := s.nu p / (1 - s.nu p) theorem one_add_odds (s : BoundingSieve) (p : ℕ) (hp : p ∈ s.prodPrimes.primeFactors) : 1 + odds s p = (1 - s.nu p)⁻¹ := by have hn : 1 - s.nu p ≠ 0 := by have h := s.nu_lt_one_of_prime p (Nat.prime_of_mem_primeFactors hp) (Nat.dvd_of_mem_primeFactors hp) linarith unfold odds field_simp ring theorem odds_nonneg (s : BoundingSieve) (p : ℕ) (hp : p ∈ s.prodPrimes.primeFactors) : 0 ≤ odds s p := by exact div_nonneg (s.nu_pos_of_prime p (Nat.prime_of_mem_primeFactors hp) (Nat.dvd_of_mem_primeFactors hp)).le (sub_pos.mpr (s.nu_lt_one_of_prime p (Nat.prime_of_mem_primeFactors hp) (Nat.dvd_of_mem_primeFactors hp))).le theorem odds_moment (s : BoundingSieve) (p : ℕ) (hp : p ∈ s.prodPrimes.primeFactors) : odds s p / (1 + odds s p) = s.nu p := by rw [one_add_odds s p hp] have hn : 1 - s.nu p ≠ 0 := by have h := s.nu_lt_one_of_prime p (Nat.prime_of_mem_primeFactors hp) (Nat.dvd_of_mem_primeFactors hp) linarith unfold odds field_simp /-- Squarefree prime-subset products have the exact required Selberg term. -/ theorem selbergTerms_prod (s : BoundingSieve) (T : Finset ℕ) (hT : T ⊆ s.prodPrimes.primeFactors) : s.selbergTerms (∏ p ∈ T, p) = ∏ p ∈ T, odds s p := by rw [s.selbergTerms_isMultiplicative.map_prod_of_prime T (fun p hp => Nat.prime_of_mem_primeFactors (hT hp))] apply prod_congr rfl intro p hp rw [s.selbergTerms_apply, (Nat.prime_of_mem_primeFactors (hT hp)).primeFactors] simp only [prod_singleton] rfl /-- The current denominator is exactly the squarefree prime-subset sum. -/ theorem denominator_powerset (s : BoundingSieve) (L : ℝ) : SelbergFinite.denominator s L = ∑ T ∈ s.prodPrimes.primeFactors.powerset, if ((∏ p ∈ T, p : ℕ) : ℝ) ^ 2 ≤ L then ∏ p ∈ T, odds s p else 0 := by classical unfold SelbergFinite.denominator rw [← Nat.divisors_filter_squarefree_of_squarefree s.prodPrimes_squarefree, Nat.sum_divisors_filter_squarefree s.prodPrimes_ne_zero, Nat.factors_eq] simp only [List.toFinset_coe, Finset.prod_val] apply sum_congr rfl intro T hT change (if ((∏ p ∈ T, p : ℕ) : ℝ) ^ 2 ≤ L then s.selbergTerms (∏ p ∈ T, p) else 0) = _ rw [selbergTerms_prod s T (mem_powerset.mp hT)] /-- Exact squared-level/log-cost equivalence, including the empty prime subset. -/ theorem squared_cutoff_iff_log (T : Finset ℕ) (hT : ∀ p ∈ T, Nat.Prime p) (L : ℝ) (hL : 0 < L) : ((∏ p ∈ T, p : ℕ) : ℝ) ^ 2 ≤ L ↔ (∑ p ∈ T, Real.log (p : ℝ)) ≤ Real.log L / 2 := by have hpos : (0 : ℝ) < (∏ p ∈ T, p : ℕ) := by exact_mod_cast prod_pos (fun p hp => (hT p hp).pos) have hlog : Real.log ((∏ p ∈ T, p : ℕ) : ℝ) = ∑ p ∈ T, Real.log (p : ℝ) := by rw [Nat.cast_prod, Real.log_prod (fun p hp => by exact_mod_cast (hT p hp).ne_zero)] rw [← Real.log_le_log_iff (sq_pos_of_pos hpos) hL, Real.log_pow, hlog] norm_num constructor <;> intro h <;> linarith theorem denominator_log_powerset (s : BoundingSieve) (L : ℝ) (hL : 0 < L) : SelbergFinite.denominator s L = ∑ T ∈ s.prodPrimes.primeFactors.powerset with (∑ p ∈ (T : Finset ℕ), Real.log (p : ℝ)) ≤ Real.log L / 2, ∏ p ∈ T, odds s p := by rw [denominator_powerset, sum_filter] apply sum_congr rfl intro T hT exact if_congr (squared_cutoff_iff_log T (fun p hp => Nat.prime_of_mem_primeFactors (mem_powerset.mp hT hp)) L hL) rfl rfl theorem euler_product (s : BoundingSieve) : (∏ p ∈ s.prodPrimes.primeFactors, (1 + odds s p)) = (∏ p ∈ s.prodPrimes.primeFactors, (1 - s.nu p))⁻¹ := by rw [← prod_inv_distrib] apply prod_congr rfl intro p hp exact one_add_odds s p hp /-- Conditional finite denominator lower bound; the prime-log moment is explicit. -/ theorem denominator_lower (s : BoundingSieve) (L : ℝ) (hL : 1 < L) (hmean : (∑ p ∈ s.prodPrimes.primeFactors, s.nu p * Real.log (p : ℝ)) ≤ Real.log L / 4) : (∏ p ∈ s.prodPrimes.primeFactors, (1 - s.nu p))⁻¹ / 2 ≤ SelbergFinite.denominator s L := by have hlogL : 0 < Real.log L := Real.log_pos hL have hl : 0 < Real.log L / 2 := by positivity have hm : (∑ p ∈ s.prodPrimes.primeFactors, odds s p / (1 + odds s p) * Real.log (p : ℝ)) ≤ (Real.log L / 2) / 2 := by calc _ = ∑ p ∈ s.prodPrimes.primeFactors, s.nu p * Real.log (p : ℝ) := by apply sum_congr rfl intro p hp rw [odds_moment s p hp] _ ≤ _ := by convert hmean using 1; ring have hh := sieve_euler_truncation s.prodPrimes.primeFactors (odds s) (fun p => Real.log (p : ℝ)) (odds_nonneg s) (fun p hp => Real.log_nonneg (by exact_mod_cast (Nat.prime_of_mem_primeFactors hp).one_lt.le)) hl hm rw [euler_product] at hh rw [denominator_log_powerset s L (by linarith)] exact hh /-- Specialization to literal equation (15), with the real sqrt(y) prime cutoff. -/ theorem actual_denominator_lower (X : ℕ) (y z0 z1 L : ℝ) (hz0 : 3 < z0) (hL : 1 < L) (hmean : (∑ p ∈ ManuscriptResidues.paperPrimes y, ActualBoundingSieve.density (ManuscriptResidues.omegaSet z0 z1) p * Real.log (p : ℝ)) ≤ Real.log L / 4) : (∏ p ∈ ManuscriptResidues.paperPrimes y, (1 - ActualBoundingSieve.density (ManuscriptResidues.omegaSet z0 z1) p))⁻¹ / 2 ≤ SelbergFinite.denominator (ActualBoundingSieve.sieve X y z0 z1 hz0) L := by have hp : (ActualBoundingSieve.sieve X y z0 z1 hz0).prodPrimes.primeFactors = ManuscriptResidues.paperPrimes y := by change (∏ p ∈ ManuscriptResidues.paperPrimes y, p).primeFactors = _ exact Nat.primeFactors_prod (ManuscriptResidues.paperPrimeFamily y) have hm : (∑ p ∈ (ActualBoundingSieve.sieve X y z0 z1 hz0).prodPrimes.primeFactors, (ActualBoundingSieve.sieve X y z0 z1 hz0).nu p * Real.log (p : ℝ)) ≤ Real.log L / 4 := by rw [hp] exact hmean have hh := denominator_lower (ActualBoundingSieve.sieve X y z0 z1 hz0) L hL hm rw [hp] at hh exact hh end end SelbergEuler #print axioms SelbergEuler.sieve_euler_log_moment #print axioms SelbergEuler.sieve_euler_truncation #print axioms SelbergEuler.odds #print axioms SelbergEuler.one_add_odds #print axioms SelbergEuler.odds_nonneg #print axioms SelbergEuler.odds_moment #print axioms SelbergEuler.selbergTerms_prod #print axioms SelbergEuler.denominator_powerset #print axioms SelbergEuler.squared_cutoff_iff_log #print axioms SelbergEuler.denominator_log_powerset #print axioms SelbergEuler.euler_product #print axioms SelbergEuler.denominator_lower #print axioms SelbergEuler.actual_denominator_lower