/- Copyright (c) 2023 Arend Mellendijk. All rights reserved. Released under Apache 2.0 license as described in the file LICENSE. Author: Arend Mellendijk Lambda-square support and lcm-pair norm arguments adapted from pinned PNT+ Basic/Selberg, revision 2667e414c38e5a5dc9aa1946f16f13001e5cd3ed. The coarse inverse-density coefficient bound and actual g-bound/composition are derived against current pinned Mathlib. -/ import SelbergFinite import Mathlib.Algebra.Order.Antidiag.Nat namespace SelbergError noncomputable section open scoped BigOperators ArithmeticFunction.Moebius ArithmeticFunction.omega open Finset Nat ArithmeticFunction BoundingSieve SelbergFinite private theorem pair_zero_of_order (s : BoundingSieve) (L : ℝ) (n a b : ℕ) (hn : ¬ (n : ℝ) ≤ L) (heq : n = a.lcm b) (hab : a ≤ b) : coefficients s L a * coefficients s L b = 0 := by have hb : ¬ (b : ℝ) ^ 2 ≤ L := by intro h apply hn apply le_trans _ h have hlcm : a.lcm b ≤ a * b := Nat.div_le_self _ _ have hmul : a * b ≤ b ^ 2 := by simpa [pow_two] using Nat.mul_le_mul_right b hab exact_mod_cast (heq ▸ hlcm.trans hmul) rw [coefficients_zero_above_level s L b hb, mul_zero] /-- Actual lambda-square support d≤L follows from proved coefficient squared support. -/ theorem lambda_zero_above_level (s : BoundingSieve) (L : ℝ) (n : ℕ) (hn : ¬ (n : ℝ) ≤ L) : lambdaSquared (coefficients s L) n = 0 := by unfold lambdaSquared apply sum_eq_zero intro a _ apply sum_eq_zero intro b _ split_ifs with h · rcases Nat.le_or_le a b with hab | hba · exact pair_zero_of_order s L n a b hn h hab · rw [mul_comm] exact pair_zero_of_order s L n b a hn (Nat.lcm_comm a b ▸ h) hba · rfl /-- A coarse coefficient estimate that needs no assumed norm bound. -/ theorem coefficient_abs_le_inv_density (s : BoundingSieve) (L : ℝ) (hL : 1 ≤ L) (d : ℕ) (hd : d ∣ s.prodPrimes) : |coefficients s L d| ≤ (s.nu d)⁻¹ := by let A : ℝ := ∑ k ∈ s.prodPrimes.divisors, if d ∣ k ∧ (k : ℝ) ^ 2 ≤ L then s.selbergTerms k else 0 have hA : 0 ≤ A := by apply sum_nonneg intro k hk split_ifs · exact (s.selbergTerms_pos (dvd_of_mem_divisors hk)).le · exact le_rfl have hAS : A ≤ denominator s L := by apply sum_le_sum intro k hk by_cases hcut : (k : ℝ) ^ 2 ≤ L · by_cases hdk : d ∣ k · simp only [hcut, hdk, and_self, ite_true] exact le_rfl · simp only [hcut, hdk, false_and, ite_false, ite_true] exact (s.selbergTerms_pos (dvd_of_mem_divisors hk)).le · simp only [hcut, and_false, ite_false] exact le_rfl have hS := denominator_pos s L hL have hn := s.nu_pos_of_dvd_prodPrimes hd have hr : 0 ≤ A / denominator s L := div_nonneg hA hS.le have hr1 : A / denominator s L ≤ 1 := (div_le_one hS).mpr hAS have hmu : |(μ d : ℝ)| ≤ 1 := by exact_mod_cast (abs_moebius_le_one (n := d)) have heq : |coefficients s L d| = (s.nu d)⁻¹ * (A / denominator s L) * |(μ d : ℝ)| := by unfold coefficients change |(s.nu d)⁻¹ * (denominator s L)⁻¹ * (μ d : ℝ) * A| = _ rw [abs_mul, abs_mul, abs_mul, abs_of_nonneg (inv_nonneg.mpr hn.le), abs_of_nonneg (inv_nonneg.mpr hS.le), abs_of_nonneg hA] ring rw [heq] calc _ ≤ (s.nu d)⁻¹ * 1 * 1 := by apply mul_le_mul (mul_le_mul_of_nonneg_left hr1 (inv_nonneg.mpr hn.le)) hmu · exact abs_nonneg _ · simpa only [mul_one] using (inv_nonneg.mpr hn.le) _ = _ := by ring /-- Actual residue cardinality product is positive and ≤4^ω on every supported divisor. -/ theorem actual_g_bounds (X : ℕ) (y z0 z1 : ℝ) (hz0 : 3 < z0) (d : ℕ) (hd : d ∣ (ActualBoundingSieve.sieve X y z0 z1 hz0).prodPrimes) : 1 ≤ DivisorMoments.localG (ManuscriptResidues.omegaSet z0 z1) d ∧ DivisorMoments.localG (ManuscriptResidues.omegaSet z0 z1) d ≤ 4 ^ ω d := by have hd0 := DivisorMoments.divisor_nonzero _ (ManuscriptResidues.paperPrimeFamily y) d hd have hcard : d.primeFactors.card = ω d := by simp only [cardDistinctFactors_apply, Nat.primeFactors, List.card_toFinset] rw [DivisorMoments.localG, ite_eq_right hd0] constructor · exact Finset.one_le_prod (fun p hp => (ManuscriptResidues.omega_bounds z0 z1 hz0 p (Nat.prime_of_mem_primeFactors hp)).1) · calc _ ≤ ∏ _p ∈ d.primeFactors, 4 := Finset.prod_le_prod (fun p hp => (ManuscriptResidues.omega_bounds z0 z1 hz0 p (Nat.prime_of_mem_primeFactors hp)).2.1) _ = 4 ^ ω d := by rw [prod_const, hcard] /-- The actual inverse density has the coarse but unconditional-on-level upper bound d. -/ theorem actual_inverse_density_le (X : ℕ) (y z0 z1 : ℝ) (hz0 : 3 < z0) (d : ℕ) (hd : d ∣ (ActualBoundingSieve.sieve X y z0 z1 hz0).prodPrimes) : ((ActualBoundingSieve.sieve X y z0 z1 hz0).nu d)⁻¹ ≤ (d : ℝ) := by change ((DivisorMoments.localG (ManuscriptResidues.omegaSet z0 z1) d : ℝ) / d)⁻¹ ≤ _ rw [inv_div] have hg : (1 : ℝ) ≤ DivisorMoments.localG (ManuscriptResidues.omegaSet z0 z1) d := by exact_mod_cast (actual_g_bounds X y z0 z1 hz0 d hd).1 apply (div_le_iff₀ (by linarith : (0 : ℝ) < DivisorMoments.localG (ManuscriptResidues.omegaSet z0 z1) d)).mpr have hdR : (0 : ℝ) ≤ d := Nat.cast_nonneg d nlinarith theorem actual_coefficient_abs_le (X : ℕ) (y z0 z1 L : ℝ) (hz0 : 3 < z0) (hL : 1 ≤ L) (d : ℕ) : |coefficients (ActualBoundingSieve.sieve X y z0 z1 hz0) L d| ≤ (d : ℝ) := by by_cases hd : d ∣ (ActualBoundingSieve.sieve X y z0 z1 hz0).prodPrimes · exact (coefficient_abs_le_inv_density _ L hL d hd).trans (actual_inverse_density_le X y z0 z1 hz0 d hd) · rw [coefficients_zero_not_dvd _ L d hd, abs_zero] exact Nat.cast_nonneg d /-- Exact squarefree lcm-pair counting gives a coarse d²·3^ω bound. -/ theorem lambda_abs_le_square_omega (w : ℕ → ℝ) (hw : ∀ d : ℕ, |w d| ≤ (d : ℝ)) (n : ℕ) (hn : Squarefree n) : |lambdaSquared w n| ≤ (n : ℝ) ^ 2 * (3 : ℝ) ^ ω n := by let f : ℕ → ℕ → ℝ := fun a b => if n = a.lcm b then (n : ℝ) ^ 2 else 0 unfold lambdaSquared calc _ ≤ ∑ a ∈ n.divisors, |∑ b ∈ n.divisors, if n = a.lcm b then w a * w b else 0| := abs_sum_le_sum_abs _ _ _ ≤ ∑ a ∈ n.divisors, ∑ b ∈ n.divisors, |if n = a.lcm b then w a * w b else 0| := by apply sum_le_sum intro a _ exact abs_sum_le_sum_abs _ _ _ ≤ ∑ a ∈ n.divisors, ∑ b ∈ n.divisors, f a b := by apply sum_le_sum intro a ha apply sum_le_sum intro b hb by_cases heq : n = a.lcm b · change |if n = a.lcm b then w a * w b else 0| ≤ (if n = a.lcm b then (n : ℝ) ^ 2 else 0) rw [ite_eq_left heq, ite_eq_left heq, abs_mul] calc _ ≤ (a : ℝ) * b := mul_le_mul (hw a) (hw b) (abs_nonneg _) (Nat.cast_nonneg a) _ ≤ (n : ℝ) * n := by gcongr · exact_mod_cast Nat.divisor_le ha · exact_mod_cast Nat.divisor_le hb _ = _ := by ring · change |if n = a.lcm b then w a * w b else 0| ≤ (if n = a.lcm b then (n : ℝ) ^ 2 else 0) rw [ite_eq_right heq, abs_zero, ite_eq_right heq] _ = (n : ℝ) ^ 2 * ((n.divisors ×ˢ n.divisors).filter (fun p : ℕ × ℕ => n = p.1.lcm p.2)).card := by rw [← sum_product'] change _ = _ simp only [f] rw [← sum_filter, sum_const, nsmul_eq_mul] ring _ = _ := by have hc := Nat.card_pair_lcm_eq hn have hc' : ((n.divisors ×ˢ n.divisors).filter (fun p : ℕ × ℕ => n = p.1.lcm p.2)).card = 3 ^ ω n := by simpa only [eq_comm] using hc rw [hc', Nat.cast_pow, Nat.cast_ofNat] /-- Explicit actual error tradeoff: an extra d² compared with the sharper standard norm route. -/ theorem actual_upper_coarse_error (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, if (d : ℝ) ≤ L then (d : ℝ) ^ 2 * (12 : ℝ) ^ ω d else 0 := by let s := ActualBoundingSieve.sieve X y z0 z1 hz0 apply (actual_optimized_upper X y z0 z1 L hz0 hL).trans apply _root_.add_le_add le_rfl apply sum_le_sum intro d hd by_cases hcut : (d : ℝ) ≤ L · rw [ite_eq_left hcut] have hw := lambda_abs_le_square_omega (coefficients s L) (actual_coefficient_abs_le X y z0 z1 L hz0 hL) d (s.squarefree_of_mem_divisors_prodPrimes hd) have hg : (DivisorMoments.localG (ManuscriptResidues.omegaSet z0 z1) d : ℝ) ≤ (4 : ℝ) ^ ω d := by exact_mod_cast (actual_g_bounds X y z0 z1 hz0 d (dvd_of_mem_divisors hd)).2 calc _ ≤ ((d : ℝ) ^ 2 * (3 : ℝ) ^ ω d) * (4 : ℝ) ^ ω d := mul_le_mul hw hg (Nat.cast_nonneg _) (by positivity) _ = _ := by rw [mul_assoc, ← mul_pow]; norm_num · rw [lambda_zero_above_level s L d hcut, abs_zero, zero_mul, ite_eq_right hcut] #print axioms lambda_zero_above_level #print axioms coefficient_abs_le_inv_density #print axioms actual_g_bounds #print axioms actual_inverse_density_le #print axioms actual_coefficient_abs_le #print axioms lambda_abs_le_square_omega #print axioms actual_upper_coarse_error end end SelbergError