/- Copyright (c) 2023 Arend Mellendijk. All rights reserved. Released under Apache 2.0 license as described in the file LICENSE. Author: Arend Mellendijk Finite Mobius and diagonalization proofs adapted from pinned PNT+ Selberg/AuxResults, revision 2667e414c38e5a5dc9aa1946f16f13001e5cd3ed. The direct inverse-sum coefficient definition and actual-manuscript composition use current pinned Mathlib. -/ import ActualBoundingSieve namespace SelbergFinite noncomputable section open scoped BigOperators ArithmeticFunction.Moebius open Finset Nat ArithmeticFunction BoundingSieve /-- Squarefree upper-divisor Mobius inversion, with no analytic premise. -/ theorem moebius_upper_divisor (l m : ℕ) (hm : Squarefree m) : (∑ d ∈ m.divisors, if l ∣ d then (μ d : ℤ) else 0) = if l = m then (μ l : ℤ) else 0 := by have hm_pos : 0 < m := Nat.pos_of_ne_zero hm.ne_zero revert hm revert m apply (ArithmeticFunction.sum_eq_iff_sum_smul_moebius_eq_on {n | Squarefree n} (fun _ _ => Squarefree.squarefree_of_dvd)).mpr intro m hm_pos hm rw [sum_divisorsAntidiagonal' (f := fun x y => μ x • if l = y then μ l else 0)] by_cases hl : l ∣ m · rw [ite_eq_left hl, sum_eq_single l] · have hmul : m / l * l = m := Nat.div_mul_cancel hl rw [ite_eq_left rfl, smul_eq_mul, ← isMultiplicative_moebius.map_mul_of_coprime, hmul] apply coprime_of_squarefree_mul rw [hmul] exact hm · intro d _ hdl rw [ite_eq_right hdl.symm, smul_zero] · intro h rw [mem_divisors] at h exact (h ⟨hl, (Nat.ne_of_lt hm_pos).symm⟩).elim · rw [ite_eq_right hl, sum_eq_zero] intro d hd rw [ite_eq_right, smul_zero] by_contra h rw [← h] at hd exact hl (dvd_of_mem_divisors hd) theorem moebius_interval_divisors {P : ℕ} (hP : Squarefree P) (l m : ℕ) (hm : m ∣ P) : (∑ d ∈ P.divisors, if l ∣ d ∧ d ∣ m then (μ d : ℝ) else 0) = if l = m then (μ l : ℝ) else 0 := by have h : (∑ d ∈ P.divisors, if l ∣ d ∧ d ∣ m then (μ d : ℤ) else 0) = if l = m then (μ l : ℤ) else 0 := by rw [← moebius_upper_divisor l m (Squarefree.squarefree_of_dvd hm hP), ← Nat.divisors_filter_dvd_of_dvd hP.ne_zero hm, sum_filter] apply sum_congr rfl intro d _ by_cases hdm : d ∣ m <;> by_cases hld : l ∣ d <;> simp [hdm, hld] exact_mod_cast h /-- Exact current-library denominator, with its squared real level convention. -/ def denominator (s : BoundingSieve) (L : ℝ) : ℝ := ∑ d ∈ s.prodPrimes.divisors, if (d : ℝ) ^ 2 ≤ L then s.selbergTerms d else 0 theorem denominator_pos (s : BoundingSieve) (L : ℝ) (hL : 1 ≤ L) : 0 < denominator s L := by unfold denominator rw [← sum_filter] apply sum_pos · intro d hd exact s.selbergTerms_pos (dvd_of_mem_divisors (mem_filter.mp hd).1) · refine ⟨1, mem_filter.mpr ⟨one_mem_divisors.mpr s.prodPrimes_ne_zero, ?_⟩⟩ simpa using hL /-- Direct finite Mobius-inverse coefficients; all target identities are derived below. -/ def coefficients (s : BoundingSieve) (L : ℝ) (d : ℕ) : ℝ := (s.nu d)⁻¹ * (denominator s L)⁻¹ * (μ d : ℝ) * ∑ k ∈ s.prodPrimes.divisors, if d ∣ k ∧ (k : ℝ) ^ 2 ≤ L then s.selbergTerms k else 0 theorem coefficients_zero_not_dvd (s : BoundingSieve) (L : ℝ) (d : ℕ) (hd : ¬ d ∣ s.prodPrimes) : coefficients s L d = 0 := by unfold coefficients have hz : (∑ k ∈ s.prodPrimes.divisors, if d ∣ k ∧ (k : ℝ) ^ 2 ≤ L then s.selbergTerms k else 0) = 0 := by apply sum_eq_zero intro k hk apply ite_eq_right intro h exact hd (h.1.trans (dvd_of_mem_divisors hk)) rw [hz, mul_zero] /-- The constructed inverse coefficients have the genuine square-root level support. -/ theorem coefficients_zero_above_level (s : BoundingSieve) (L : ℝ) (d : ℕ) (hd : ¬ (d : ℝ) ^ 2 ≤ L) : coefficients s L d = 0 := by unfold coefficients have hz : (∑ k ∈ s.prodPrimes.divisors, if d ∣ k ∧ (k : ℝ) ^ 2 ≤ L then s.selbergTerms k else 0) = 0 := by apply sum_eq_zero intro k hk apply ite_eq_right intro h have hdk : (d : ℝ) ≤ k := by exact_mod_cast Nat.le_of_dvd (Nat.pos_of_mem_divisors hk) h.1 have hsq : (d : ℝ) ^ 2 ≤ (k : ℝ) ^ 2 := by gcongr exact hd (hsq.trans h.2) rw [hz, mul_zero] theorem coefficients_nu (s : BoundingSieve) (L : ℝ) (d : ℕ) : s.nu d * coefficients s L d = (denominator s L)⁻¹ * (μ d : ℝ) * ∑ k ∈ s.prodPrimes.divisors, if d ∣ k ∧ (k : ℝ) ^ 2 ≤ L then s.selbergTerms k else 0 := by by_cases hd : d ∣ s.prodPrimes · unfold coefficients have hn := s.nu_ne_zero hd field_simp · rw [coefficients_zero_not_dvd s L d hd, mul_zero] have hz : (∑ k ∈ s.prodPrimes.divisors, if d ∣ k ∧ (k : ℝ) ^ 2 ≤ L then s.selbergTerms k else 0) = 0 := by apply sum_eq_zero intro k hk apply ite_eq_right intro h exact hd (h.1.trans (dvd_of_mem_divisors hk)) rw [hz, mul_zero] theorem coefficients_one (s : BoundingSieve) (L : ℝ) (hL : 1 ≤ L) : coefficients s L 1 = 1 := by unfold coefficients simp only [s.nu_mult.map_one, inv_one, one_mul, moebius_apply_one, Int.cast_one, mul_one, one_dvd, true_and] change (denominator s L)⁻¹ * denominator s L = 1 exact inv_mul_cancel₀ (denominator_pos s L hL).ne' /-- Exact diagonalized transform of the constructed coefficients. -/ theorem coefficients_diagonal (s : BoundingSieve) (L : ℝ) (l : ℕ) (hl : l ∈ s.prodPrimes.divisors) : (∑ d ∈ s.prodPrimes.divisors, if l ∣ d then s.nu d * coefficients s L d else 0) = if (l : ℝ) ^ 2 ≤ L then s.selbergTerms l * (μ l : ℝ) * (denominator s L)⁻¹ else 0 := by calc _ = ∑ d ∈ s.prodPrimes.divisors, ∑ k ∈ s.prodPrimes.divisors, if l ∣ d ∧ d ∣ k ∧ (k : ℝ) ^ 2 ≤ L then s.selbergTerms k * (denominator s L)⁻¹ * (μ d : ℝ) else 0 := by apply sum_congr rfl intro d _ rw [coefficients_nu, ← boole_mul, mul_sum, mul_sum] apply sum_congr rfl intro k _ rw [mul_ite_zero, ite_zero_mul_ite_zero] apply if_ctx_congr Iff.rfl _ (fun _ => rfl) intro _ ring _ = ∑ k ∈ s.prodPrimes.divisors, if (k : ℝ) ^ 2 ≤ L then (∑ d ∈ s.prodPrimes.divisors, if l ∣ d ∧ d ∣ k then (μ d : ℝ) else 0) * s.selbergTerms k * (denominator s L)⁻¹ else 0 := by rw [sum_comm] apply sum_congr rfl intro k _ symm rw [← boole_mul, sum_mul, sum_mul, mul_sum] apply sum_congr rfl intro d _ rw [ite_zero_mul, ite_zero_mul, ite_zero_mul, one_mul, ← ite_and] apply if_ctx_congr (by tauto) _ (fun _ => rfl) intro _ ring _ = _ := by rw [← sum_ite_eq_of_mem' s.prodPrimes.divisors l (fun k => if (k : ℝ) ^ 2 ≤ L then s.selbergTerms k * (μ k : ℝ) * (denominator s L)⁻¹ else 0) hl] apply sum_congr rfl intro k hk rw [moebius_interval_divisors s.prodPrimes_squarefree l k (dvd_of_mem_divisors hk), ← ite_and, ite_zero_mul, ite_zero_mul, ← ite_and] apply if_ctx_congr (by tauto) _ (fun _ => rfl) intro h rw [h.1] ring theorem optimized_main (s : BoundingSieve) (L : ℝ) (hL : 1 ≤ L) : s.mainSum (lambdaSquared (coefficients s L)) = (denominator s L)⁻¹ := by rw [mainSum_lambdaSquared_eq_sum_mul_sum_sq] calc _ = ∑ l ∈ s.prodPrimes.divisors, if (l : ℝ) ^ 2 ≤ L then s.selbergTerms l * ((denominator s L)⁻¹) ^ 2 else 0 := by apply sum_congr rfl intro l hl rw [coefficients_diagonal s L l hl, ite_pow, zero_pow two_ne_zero, mul_ite_zero] apply if_congr Iff.rfl _ rfl have hg := (s.selbergTerms_pos (dvd_of_mem_divisors hl)).ne' have hm : (μ l : ℝ) ^ 2 = 1 := by exact_mod_cast moebius_sq_eq_one_of_squarefree (s.squarefree_of_mem_divisors_prodPrimes hl) calc _ = (s.selbergTerms l)⁻¹ * s.selbergTerms l * s.selbergTerms l * (μ l : ℝ) ^ 2 * ((denominator s L)⁻¹) ^ 2 := by ring _ = _ := by rw [hm, inv_mul_cancel₀ hg]; ring _ = denominator s L * ((denominator s L)⁻¹) ^ 2 := by rw [denominator, sum_mul] apply sum_congr rfl intro l _ split_ifs <;> ring _ = (denominator s L)⁻¹ := by have h := (denominator_pos s L hL).ne' field_simp theorem optimized_upper (s : BoundingSieve) (L : ℝ) (hL : 1 ≤ L) : s.siftedSum ≤ s.totalMass / denominator s L + s.errSum (lambdaSquared (coefficients s L)) := by have h := s.siftedSum_le_mainSum_errSum_of_upperMoebius _ (upperMoebius_lambdaSquared _ (coefficients_one s L hL)) rw [optimized_main s L hL] at h simpa only [div_eq_mul_inv] using h /-- Concrete manuscript optimized finite inequality; error remains an explicit finite sum. -/ theorem actual_optimized_upper (X : ℕ) (y z0 z1 L : ℝ) (hz0 : 3 < z0) (hL : 1 ≤ L) : (SieveInterface.survivorCount X y z0 z1 : ℝ) ≤ (X : ℝ) / denominator (ActualBoundingSieve.sieve X y z0 z1 hz0) L + ∑ d ∈ (ActualBoundingSieve.sieve X y z0 z1 hz0).prodPrimes.divisors, |lambdaSquared (coefficients (ActualBoundingSieve.sieve X y z0 z1 hz0) L) d| * (DivisorMoments.localG (ManuscriptResidues.omegaSet z0 z1) d : ℝ) := by let s := ActualBoundingSieve.sieve X y z0 z1 hz0 have h := optimized_upper s L hL rw [ActualBoundingSieve.sieve_sifted_survivors] at h apply h.trans apply _root_.add_le_add le_rfl unfold BoundingSieve.errSum apply sum_le_sum intro d hd apply mul_le_mul_of_nonneg_left · exact ActualBoundingSieve.sieve_rem_bound X y z0 z1 hz0 d (dvd_of_mem_divisors hd) · exact abs_nonneg _ #print axioms moebius_upper_divisor #print axioms moebius_interval_divisors #print axioms denominator #print axioms denominator_pos #print axioms coefficients #print axioms coefficients_zero_not_dvd #print axioms coefficients_zero_above_level #print axioms coefficients_nu #print axioms coefficients_one #print axioms coefficients_diagonal #print axioms optimized_main #print axioms optimized_upper #print axioms actual_optimized_upper end end SelbergFinite