/- Released under Apache-2.0; see adjacent LICENSE. Literal first-two-band covering sets and finite smooth-number counting. No smooth-number asymptotic, prime supply, or main theorem is assumed. -/ import ManuscriptParameters namespace EarlyCover noncomputable section open ManuscriptResidues /-- Primes below the reserved band, with the original real upper cutoff y. -/ def earlyPrimes (y : ℝ) : Finset ℕ := (primeCutoff y).filter (fun p => (p : ℝ) < y / 2) def reservedPrimes (y : ℝ) : Finset ℕ := (primeCutoff y).filter (fun p => y / 2 ≤ (p : ℝ)) def choice (z0 z1 : ℝ) (p : ℕ) : ℕ := if middleBand z0 z1 p then 1 else 0 /-- Actual covering pair {a_p,a_p−2}, not the auxiliary four-class set. -/ def coverSet (z0 z1 : ℝ) (p : ℕ) : Finset (ZMod p) := {(choice z0 z1 p : ZMod p), (choice z0 z1 p : ZMod p) - 2} def EarlyUncovered (y z0 z1 : ℝ) (i : ℕ) : Prop := ∀ p ∈ earlyPrimes y, (i : ZMod p) ∉ coverSet z0 z1 p def uncoveredSet (m : ℕ) (y z0 z1 : ℝ) : Finset ℕ := by classical exact (Finset.Ioc 0 m).filter (EarlyUncovered y z0 z1) def R (m : ℕ) (y z0 z1 : ℝ) : ℕ := (uncoveredSet m y z0 z1).card /-- Actual finite smoothness: every prime divisor satisfies the real cutoff. -/ def Smooth (Z : ℝ) (n : ℕ) : Prop := ∀ p : ℕ, Nat.Prime p → p ∣ n → (p : ℝ) ≤ Z def smoothSet (X : ℕ) (Z : ℝ) : Finset ℕ := by classical exact (Finset.Ioc 0 X).filter (Smooth Z) def Psi (X : ℕ) (Z : ℝ) : ℕ := (smoothSet X Z).card theorem mem_earlyPrimes (y : ℝ) (hy : 0 ≤ y) (p : ℕ) : p ∈ earlyPrimes y ↔ Nat.Prime p ∧ (p : ℝ) < y / 2 := by simp only [earlyPrimes, Finset.mem_filter, mem_primeCutoff y hy] constructor · rintro ⟨⟨hp, _⟩, hlt⟩; exact ⟨hp, hlt⟩ · rintro ⟨hp, hlt⟩; exact ⟨⟨hp, by linarith⟩, hlt⟩ theorem prime_partition (y : ℝ) : earlyPrimes y ∪ reservedPrimes y = primeCutoff y ∧ Disjoint (earlyPrimes y) (reservedPrimes y) := by constructor · ext p by_cases h : (p : ℝ) < y / 2 · simp [earlyPrimes, reservedPrimes, h, not_le_of_gt h] · simp [earlyPrimes, reservedPrimes, h, le_of_not_gt h] · apply Finset.disjoint_left.mpr intro p hp hq have hp := (Finset.mem_filter.mp hp).2 have hq := (Finset.mem_filter.mp hq).2 linarith theorem coverSet_eq (z0 z1 : ℝ) (p : ℕ) : coverSet z0 z1 p = if middleBand z0 z1 p then {1, -1} else {0, -2} := by unfold coverSet choice split_ifs <;> norm_num /-- The literal modular covering pair agrees with the original Nat.ModEq encoding. -/ theorem coveredAt_iff (S : Finset ℕ) (z0 z1 : ℝ) (i : ℕ) : KKFiniteCoreDraft.CoveredAt S (choice z0 z1) i ↔ ∃ p ∈ S, (i : ZMod p) ∈ coverSet z0 z1 p := by simp only [KKFiniteCoreDraft.CoveredAt, coverSet, Finset.mem_insert, Finset.mem_singleton] apply exists_congr intro p apply and_congr_right intro _ rw [← ZMod.natCast_eq_natCast_iff, ← ZMod.natCast_eq_natCast_iff] simp only [Nat.cast_add, Nat.cast_ofNat] rw [eq_sub_iff_add_eq] theorem uncovered_eq_core (m : ℕ) (y z0 z1 : ℝ) : uncoveredSet m y z0 z1 = KKFiniteCoreDraft.uncovered (earlyPrimes y) (choice z0 z1) m := by classical ext i have hU : ¬ KKFiniteCoreDraft.CoveredAt (earlyPrimes y) (choice z0 z1) i ↔ EarlyUncovered y z0 z1 i := by rw [coveredAt_iff] constructor · intro h p hp hi; exact h ⟨p, hp, hi⟩ · intro h ⟨p, hp, hi⟩; exact h p hp hi simp only [uncoveredSet, KKFiniteCoreDraft.uncovered, Finset.mem_filter, Finset.mem_Ioc, Finset.mem_Icc] rw [hU] constructor · rintro ⟨⟨h0, hm⟩, hu⟩; exact ⟨⟨by omega, hm⟩, hu⟩ · rintro ⟨⟨h0, hm⟩, hu⟩; exact ⟨⟨by omega, hm⟩, hu⟩ /-- Divisibility of either linear form gives membership in the basic covering pair. -/ theorem basic_mem_iff (i p : ℕ) : (i : ZMod p) ∈ ({0, -2} : Finset (ZMod p)) ↔ p ∣ i ∨ p ∣ (i + 2) := by simp only [Finset.mem_insert, Finset.mem_singleton] rw [ZMod.natCast_eq_zero_iff] have hh : ((i : ZMod p) = -2) ↔ p ∣ (i + 2) := by rw [← ZMod.natCast_eq_zero_iff, Nat.cast_add, Nat.cast_ofNat] exact eq_neg_iff_add_eq_zero exact or_congr Iff.rfl hh /-- Every prime divisor of either form is above z0 if the early choices do not cover i. -/ theorem factor_gt_z0 (y z0 z1 : ℝ) (i k p : ℕ) (hy : 0 < y) (hz : z0 < y / 2) (hu : EarlyUncovered y z0 z1 i) (hk : k = i ∨ k = i + 2) (hp : Nat.Prime p) (hpk : p ∣ k) : z0 < (p : ℝ) := by by_contra hn have hpz : (p : ℝ) ≤ z0 := le_of_not_gt hn have hpe : p ∈ earlyPrimes y := (mem_earlyPrimes y hy.le p).mpr ⟨hp, hpz.trans_lt hz⟩ have hb : ¬ middleBand z0 z1 p := by intro h; linarith [h.1] apply hu p hpe rw [coverSet_eq, ite_eq_right hb, basic_mem_iff] rcases hk with rfl | rfl · exact Or.inl hpk · exact Or.inr hpk /-- A prime divisor larger than z1 must be reserved or above the global y cutoff. -/ theorem large_factor_ge_half (y z0 z1 : ℝ) (i k q : ℕ) (hy : 0 < y) (hu : EarlyUncovered y z0 z1 i) (hk : k = i ∨ k = i + 2) (hq : Nat.Prime q) (hqk : q ∣ k) (hz1 : z1 < (q : ℝ)) : y / 2 ≤ (q : ℝ) := by by_contra hn have hqe : q ∈ earlyPrimes y := (mem_earlyPrimes y hy.le q).mpr ⟨hq, lt_of_not_ge hn⟩ have hb : ¬ middleBand z0 z1 q := by intro h; linarith [h.2] apply hu q hqe rw [coverSet_eq, ite_eq_right hb, basic_mem_iff] rcases hk with rfl | rfl · exact Or.inl hqk · exact Or.inr hqk /-- Failure of the auxiliary sieve supplies a divisor of one form; middle extra hits cover already. -/ theorem auxiliary_failure_factor (y z0 z1 : ℝ) (i : ℕ) (hy : 0 < y) (hs : Real.sqrt y < y / 2) (hu : EarlyUncovered y z0 z1 i) (hn : ¬ ∀ p ∈ paperPrimes y, (i : ZMod p) ∉ paperSet z0 z1 p) : ∃ p ∈ paperPrimes y, p ∣ i ∨ p ∣ (i + 2) := by classical push_neg at hn obtain ⟨p, hp, hi⟩ := hn have hpp := (mem_paperPrimes y p).mp hp have hpe : p ∈ earlyPrimes y := (mem_earlyPrimes y hy.le p).mpr ⟨hpp.1, hpp.2.trans_lt hs⟩ refine ⟨p, hp, (basic_mem_iff i p).mp ?_⟩ by_cases hb : middleBand z0 z1 p · have hnot := hu p hpe rw [coverSet_eq, ite_eq_left hb] at hnot simp only [paperSet, ite_eq_left hb, Finset.mem_insert, Finset.mem_singleton] at hi simp only [Finset.mem_insert, Finset.mem_singleton, not_or] at hnot rcases hi with hi | hi | hi | hi · simp [hi] · simp [hi] · exact False.elim (hnot.1 hi) · exact False.elim (hnot.2 hi) · simpa only [paperSet, ite_eq_right hb] using hi /-- Distinct prime factors give a finite contradiction, without a largest-factor or Psi estimate. -/ theorem smooth_of_small_factor (m i k p : ℕ) (y z0 z1 : ℝ) (hy : 0 < y) (hz : z0 < y / 2) (hs : Real.sqrt y < y / 2) (hco : 2 * ((m + 2 : ℕ) : ℝ) / y ≤ z0) (hi : 0 < i ∧ i ≤ m) (hu : EarlyUncovered y z0 z1 i) (hk : k = i ∨ k = i + 2) (hp : Nat.Prime p) (hpS : (p : ℝ) ≤ Real.sqrt y) (hpk : p ∣ k) : Smooth z1 k := by intro q hq hqk by_contra hn have hqz : z1 < (q : ℝ) := lt_of_not_ge hn have hqh := large_factor_ge_half y z0 z1 i k q hy hu hk hq hqk hqz have hpz := factor_gt_z0 y z0 z1 i k p hy hz hu hk hp hpk have hpqR : (p : ℝ) < q := hpS.trans_lt (hs.trans_le hqh) have hpq : p ≠ q := by intro he; subst q; exact (lt_irrefl _ hpqR) have hpqk : p * q ∣ k := ((Nat.coprime_primes hp hq).mpr hpq).mul_dvd_of_dvd_of_dvd hpk hqk have hk0 : 0 < k := by rcases hk with rfl | rfl <;> omega have hkm : k ≤ m + 2 := by rcases hk with rfl | rfl <;> omega have hpqle : (p : ℝ) * q ≤ (m + 2 : ℕ) := by exact_mod_cast (Nat.le_of_dvd hk0 hpqk).trans hkm have hcoprod : 2 * ((m + 2 : ℕ) : ℝ) ≤ z0 * y := (div_le_iff₀ hy).mp hco have hpR : 0 < (p : ℝ) := by exact_mod_cast hp.pos have h1 := mul_lt_mul_of_pos_right hpz hy have h2 := mul_le_mul_of_nonneg_left hqh hpR.le nlinarith /-- Literal Proposition3, including its original small branch. The derived classification is stronger. -/ theorem proposition3 (m i : ℕ) (y z0 z1 : ℝ) (hy : 0 < y) (hz : z0 < y / 2) (hs : Real.sqrt y < y / 2) (hco : 2 * ((m + 2 : ℕ) : ℝ) / y ≤ z0) (hi : 0 < i ∧ i ≤ m) (hu : EarlyUncovered y z0 z1 i) : (i : ℝ) ≤ Real.sqrt y + 2 ∨ Smooth z1 i ∨ Smooth z1 (i + 2) ∨ (∀ p ∈ paperPrimes y, (i : ZMod p) ∉ paperSet z0 z1 p) := by classical by_cases ha : ∀ p ∈ paperPrimes y, (i : ZMod p) ∉ paperSet z0 z1 p · exact Or.inr (Or.inr (Or.inr ha)) obtain ⟨p, hp, hpk⟩ := auxiliary_failure_factor y z0 z1 i hy hs hu ha have hpp := (mem_paperPrimes y p).mp hp rcases hpk with hpk | hpk · exact Or.inr (Or.inl (smooth_of_small_factor m i i p y z0 z1 hy hz hs hco hi hu (Or.inl rfl) hpp.1 hpp.2 hpk)) · exact Or.inr (Or.inr (Or.inl (smooth_of_small_factor m i (i+2) p y z0 z1 hy hz hs hco hi hu (Or.inr rfl) hpp.1 hpp.2 hpk))) /-- Equation17 as an exact finite cardinal inequality; overlap is only counted upwards. -/ theorem uncovered_count (m : ℕ) (y z0 z1 : ℝ) (hy : 0 < y) (hz : z0 < y / 2) (hs : Real.sqrt y < y / 2) (hco : 2 * ((m + 2 : ℕ) : ℝ) / y ≤ z0) : R m y z0 z1 ≤ SieveInterface.survivorCount m y z0 z1 + ⌊Real.sqrt y + 2⌋₊ + 2 * Psi (m + 2) z1 := by classical let I : Finset ℕ := Finset.Ioc 0 m let A : Finset ℕ := I.filter (fun i => ∀ p ∈ paperPrimes y, (i : ZMod p) ∉ paperSet z0 z1 p) let B : Finset ℕ := I.filter (Smooth z1) let C : Finset ℕ := I.filter (fun i => Smooth z1 (i+2)) let D : Finset ℕ := I.filter (fun (i : ℕ) => (i : ℝ) ≤ Real.sqrt y + 2) have hsub : uncoveredSet m y z0 z1 ⊆ D ∪ (B ∪ (C ∪ A)) := by intro i hi obtain ⟨hiI, hu⟩ := Finset.mem_filter.mp hi have hprop := proposition3 m i y z0 z1 hy hz hs hco (Finset.mem_Ioc.mp hiI) hu simp only [D, B, C, A, Finset.mem_union, Finset.mem_filter] rcases hprop with h | h | h | h · exact Or.inl ⟨hiI,h⟩ · exact Or.inr (Or.inl ⟨hiI,h⟩) · exact Or.inr (Or.inr (Or.inl ⟨hiI,h⟩)) · exact Or.inr (Or.inr (Or.inr ⟨hiI,h⟩)) have hA : A.card = SieveInterface.survivorCount m y z0 z1 := rfl have hD : D.card ≤ ⌊Real.sqrt y + 2⌋₊ := by have hd : D ⊆ Finset.Ioc 0 ⌊Real.sqrt y + 2⌋₊ := by intro i hi obtain ⟨hiI, hsmall⟩ := Finset.mem_filter.mp hi refine Finset.mem_Ioc.mpr ⟨(Finset.mem_Ioc.mp hiI).1, ?_⟩ exact (Nat.le_floor_iff (by positivity : 0 ≤ Real.sqrt y + 2)).mpr hsmall simpa using Finset.card_le_card hd have hB : B.card ≤ Psi (m+2) z1 := by change B.card ≤ (smoothSet (m+2) z1).card apply Finset.card_le_card intro i hi obtain ⟨hiI, hiS⟩ := Finset.mem_filter.mp hi exact Finset.mem_filter.mpr ⟨Finset.mem_Ioc.mpr ⟨(Finset.mem_Ioc.mp hiI).1, by have := (Finset.mem_Ioc.mp hiI).2; omega⟩, hiS⟩ have hC : C.card ≤ Psi (m+2) z1 := by change C.card ≤ (smoothSet (m+2) z1).card apply Finset.card_le_card_of_injOn (fun i : ℕ => i+2) · intro i hi change i+2 ∈ smoothSet (m+2) z1 obtain ⟨hiI, hiS⟩ := Finset.mem_filter.mp hi exact Finset.mem_filter.mpr ⟨Finset.mem_Ioc.mpr ⟨by omega, by have := (Finset.mem_Ioc.mp hiI).2; omega⟩, hiS⟩ · intro i hi j hj hij exact Nat.add_right_cancel hij have hc := Finset.card_le_card hsub have hu1 := Finset.card_union_le D (B ∪ (C ∪ A)) have hu2 := Finset.card_union_le B (C ∪ A) have hu3 := Finset.card_union_le C A change (uncoveredSet m y z0 z1).card ≤ _ omega /-- The exact equation13 choices discharge every geometric premise of count17. -/ theorem parameter_uncovered_count (y A : ℝ) (hA : 4 ≤ A) (hy : ManuscriptParameters.threshold A ≤ y) : R (ManuscriptParameters.m y (ManuscriptParameters.chooseB A)) y (ManuscriptParameters.z0 y A) (ManuscriptParameters.z1 y A) ≤ SieveInterface.survivorCount (ManuscriptParameters.m y (ManuscriptParameters.chooseB A)) y (ManuscriptParameters.z0 y A) (ManuscriptParameters.z1 y A) + ⌊Real.sqrt y + 2⌋₊ + 2 * Psi (ManuscriptParameters.m y (ManuscriptParameters.chooseB A) + 2) (ManuscriptParameters.z1 y A) := by have hf := ManuscriptParameters.large_facts y A hA hy have hB := (ManuscriptParameters.chosen_B_budget y A hA hy).1 have hg := ManuscriptParameters.geometry y A _ hA hB hy exact uncovered_count _ _ _ _ hf.1 (hg.2.1.trans (hg.2.2.1.trans hg.2.2.2.1)) hg.2.2.2.1 hg.2.2.2.2 end end EarlyCover #print axioms EarlyCover.earlyPrimes #print axioms EarlyCover.reservedPrimes #print axioms EarlyCover.choice #print axioms EarlyCover.coverSet #print axioms EarlyCover.EarlyUncovered #print axioms EarlyCover.uncoveredSet #print axioms EarlyCover.R #print axioms EarlyCover.Smooth #print axioms EarlyCover.smoothSet #print axioms EarlyCover.Psi #print axioms EarlyCover.mem_earlyPrimes #print axioms EarlyCover.prime_partition #print axioms EarlyCover.coverSet_eq #print axioms EarlyCover.coveredAt_iff #print axioms EarlyCover.uncovered_eq_core #print axioms EarlyCover.basic_mem_iff #print axioms EarlyCover.factor_gt_z0 #print axioms EarlyCover.large_factor_ge_half #print axioms EarlyCover.auxiliary_failure_factor #print axioms EarlyCover.smooth_of_small_factor #print axioms EarlyCover.proposition3 #print axioms EarlyCover.uncovered_count #print axioms EarlyCover.parameter_uncovered_count