import Mathlib /-! # The Gap Reformulation: `G₂(p#) < p'² − 2` gives a twin prime pair in the zone `(p, p'²)` Job #26 (formalize). `research/ZONE-POSTULATE.md` §3 states this as a PROVEN reduction. Its hypothesis `G₂(p#) < p'² − 2` is OPEN for large `p`. Proving the implication proves nothing about the hypothesis. **Reformulation, stated first.** The note's edge slot is the pair `(p# − 1, p# + 1)` (§3: "p# ± 1 are both coprime to p#"), i.e. the twin slot `r = P − 1` with `r + 2 = P + 1 ≡ 1 (mod P)`. It is not the slot `r = 1`, which is a twin slot only when `gcd(3, P) = 1`, and that fails for `p ≥ 3`. Reading forward from the edge slot `P − 1`, the next twin slot `t ≥ 0` satisfies `t + 1 ≤ G₂`. * `IsTwinSlot P r`: `r` and `r + 2` are coprime to `P`. `slots P` is the set of twin slots in `[0, P)`. * `gapAfter P s`: the least `d ∈ [1, P]` with `(s + d) mod P` a twin slot, capped at `P`. `G2 P` is the maximum of `gapAfter P s` over `s ∈ slots P`. * The cyclic convention: `gapAfter_eq_of_consecutive` shows that the gap from a slot to the next larger slot is their difference. `gapAfter_eq_wrap` shows that the gap from the largest slot is the wrap-around gap `(least slot) + P − (largest slot)`. * `IsNextPrime p q`: `q` is the least prime above `p`. Such a `q` exists by `exists_isNextPrime`. * `twin_in_zone` (for `3 ≤ p`) and `gap_reformulation` (for `2 ≤ p`): if `G2 (primorial p) < q² − 2` then some `r` has `p < r`, `r + 2 < q²`, and `r`, `r + 2` both prime. * `gap_reformulation_fails_at_one`: at `p = 1` (`q = 2`) the hypothesis holds and the conclusion fails, so a lower bound on `p` is needed. `p` itself need not be prime. -/ open Finset namespace ZoneGap /-- `r` is a twin slot mod `P`: both `r` and `r + 2` are coprime to `P`. -/ abbrev IsTwinSlot (P r : ℕ) : Prop := Nat.Coprime r P ∧ Nat.Coprime (r + 2) P /-- The twin slots in `[0, P)`. -/ def slots (P : ℕ) : Finset ℕ := (range P).filter (IsTwinSlot P) /-- The cyclic gap from `s` to the next twin slot: the least `d ≥ 1` with `(s + d) mod P` a twin slot, capped at `P`. For a slot `s < P` the cap is itself a step, since `(s + P) mod P = s`. -/ def gapAfter (P s : ℕ) : ℕ := Nat.find (⟨P, Or.inl rfl⟩ : ∃ d, d = P ∨ (1 ≤ d ∧ IsTwinSlot P ((s + d) % P))) /-- `G₂(P)`: the largest cyclic gap between consecutive twin slots, a maximum over the finite set `slots P`. -/ def G2 (P : ℕ) : ℕ := (slots P).sup (gapAfter P) section gap variable {P s : ℕ} lemma gapAfter_spec (P s : ℕ) : gapAfter P s = P ∨ (1 ≤ gapAfter P s ∧ IsTwinSlot P ((s + gapAfter P s) % P)) := by unfold gapAfter exact Nat.find_spec (⟨P, Or.inl rfl⟩ : ∃ d, d = P ∨ (1 ≤ d ∧ IsTwinSlot P ((s + d) % P))) lemma gapAfter_le (P s : ℕ) : gapAfter P s ≤ P := by unfold gapAfter exact Nat.find_min' _ (Or.inl rfl) lemma one_le_gapAfter (hP : 1 ≤ P) (s : ℕ) : 1 ≤ gapAfter P s := by rcases gapAfter_spec P s with h | h · omega · exact h.1 lemma gapAfter_min (P s : ℕ) {d : ℕ} (hd : 1 ≤ d) (hlt : d < gapAfter P s) : ¬ IsTwinSlot P ((s + d) % P) := by unfold gapAfter at hlt have := Nat.find_min _ hlt exact fun h => this (Or.inr ⟨hd, h⟩) lemma gapAfter_slot (hs : IsTwinSlot P s) (hsP : s < P) : IsTwinSlot P ((s + gapAfter P s) % P) := by rcases gapAfter_spec P s with h | h · rw [h, Nat.add_mod_right, Nat.mod_eq_of_lt hsP] exact hs · exact h.2 lemma G2_le (P : ℕ) : G2 P ≤ P := Finset.sup_le fun s _ => gapAfter_le P s /-- Cyclic convention, interior: from `s` to the next larger slot `t` (no slot strictly between), the gap is `t − s`. -/ theorem gapAfter_eq_of_consecutive {t : ℕ} (ht : t ∈ slots P) (hst : s < t) (hnone : ∀ u ∈ slots P, ¬ (s < u ∧ u < t)) : gapAfter P s = t - s := by simp only [slots, Finset.mem_filter, Finset.mem_range] at ht unfold gapAfter rw [Nat.find_eq_iff] refine ⟨Or.inr ⟨by omega, ?_⟩, ?_⟩ · rw [show s + (t - s) = t by omega, Nat.mod_eq_of_lt ht.1] exact ht.2 · intro n hn h rcases h with h | ⟨_, h2⟩ · omega · rw [Nat.mod_eq_of_lt (by omega : s + n < P)] at h2 exact hnone (s + n) (by simp only [slots, Finset.mem_filter, Finset.mem_range]; exact ⟨by omega, h2⟩) ⟨by omega, by omega⟩ /-- Cyclic convention, wrap-around: from the largest slot `s`, the gap is `m + P − s` to the least slot `m`. -/ theorem gapAfter_eq_wrap {m : ℕ} (hs : s ∈ slots P) (hm : m ∈ slots P) (hmax : ∀ u ∈ slots P, u ≤ s) (hmin : ∀ u ∈ slots P, m ≤ u) : gapAfter P s = m + P - s := by have hms : m ≤ s := hmax m hm have hs' := hs have hm' := hm simp only [slots, Finset.mem_filter, Finset.mem_range] at hs' hm' unfold gapAfter rw [Nat.find_eq_iff] refine ⟨Or.inr ⟨by omega, ?_⟩, ?_⟩ · rw [show s + (m + P - s) = m + P by omega, Nat.add_mod_right, Nat.mod_eq_of_lt hm'.1] exact hm'.2 · intro n hn h rcases h with h | ⟨_, h2⟩ · omega · by_cases hsn : s + n < P · rw [Nat.mod_eq_of_lt hsn] at h2 have := hmax (s + n) (by simp only [slots, Finset.mem_filter, Finset.mem_range]; exact ⟨hsn, h2⟩) omega · rw [show s + n = (s + n - P) + P by omega, Nat.add_mod_right, Nat.mod_eq_of_lt (by omega : s + n - P < P)] at h2 have := hmin (s + n - P) (by simp only [slots, Finset.mem_filter, Finset.mem_range]; exact ⟨by omega, h2⟩) omega end gap /-- `q` is the next prime after `p`. -/ def IsNextPrime (p q : ℕ) : Prop := q.Prime ∧ p < q ∧ ∀ ℓ : ℕ, ℓ.Prime → p < ℓ → q ≤ ℓ theorem exists_isNextPrime (p : ℕ) : ∃ q, IsNextPrime p q := by classical have h := Nat.exists_infinite_primes (p + 1) refine ⟨Nat.find h, (Nat.find_spec h).2, (Nat.find_spec h).1, fun ℓ hℓ hpℓ => Nat.find_min' h ⟨hpℓ, hℓ⟩⟩ /-- Facts (i) and (ii): every prime factor of an `n ≥ 2` coprime to `p#` is at least `p'`. -/ lemma le_minFac {p q n : ℕ} (hq : IsNextPrime p q) (hn : 2 ≤ n) (hc : Nat.Coprime n (primorial p)) : q ≤ n.minFac := by have hmf : n.minFac.Prime := Nat.minFac_prime (by omega) apply hq.2.2 _ hmf by_contra hle have hdvd : n.minFac ∣ primorial p := hmf.dvd_primorial_iff.2 (not_lt.mp hle) have h1 : Nat.Coprime n.minFac (primorial p) := Nat.Coprime.coprime_dvd_left (Nat.minFac_dvd n) hc exact hmf.one_lt.ne' (h1.eq_one_of_dvd hdvd) /-- A hole `n ≥ 2` of `T_p` below `p'²` exceeds `p` and is prime. -/ lemma prime_of_coprime_primorial {p q n : ℕ} (hq : IsNextPrime p q) (hn : 2 ≤ n) (hc : Nat.Coprime n (primorial p)) (hlt : n < q ^ 2) : p < n ∧ n.Prime := by have hmin := le_minFac hq hn hc refine ⟨lt_of_lt_of_le hq.2.1 (hmin.trans (Nat.minFac_le (by omega))), ?_⟩ by_contra hnp have h1 := Nat.minFac_sq_le_self (by omega : 0 < n) hnp have h2 : q ^ 2 ≤ n.minFac ^ 2 := Nat.pow_le_pow_left hmin 2 omega /-- The Gap Reformulation for `p ≥ 3`, read forward from the edge slot `p# − 1`. -/ theorem twin_in_zone {p q : ℕ} (hp : 3 ≤ p) (hq : IsNextPrime p q) (hG : G2 (primorial p) < q ^ 2 - 2) : ∃ r, p < r ∧ r + 2 < q ^ 2 ∧ r.Prime ∧ (r + 2).Prime := by obtain ⟨P, hPdef⟩ : ∃ P, P = primorial p := ⟨_, rfl⟩ rw [← hPdef] at hG have h3 : 3 ∣ P := hPdef ▸ Nat.prime_three.dvd_primorial_iff.2 hp have hP3 : 3 ≤ P := Nat.le_of_dvd (hPdef ▸ primorial_pos p) h3 have hedge : P - 1 ∈ slots P := by simp only [slots, Finset.mem_filter, Finset.mem_range] refine ⟨by omega, (Nat.coprime_self_sub_left (by omega)).2 (Nat.coprime_one_left P), ?_⟩ rw [show P - 1 + 2 = 1 + P by omega] exact Nat.coprime_add_self_left.2 (Nat.coprime_one_left P) have hedge' := hedge simp only [slots, Finset.mem_filter, Finset.mem_range] at hedge' obtain ⟨g, hg⟩ : ∃ g, g = gapAfter P (P - 1) := ⟨_, rfl⟩ have hg1 : 1 ≤ g := hg ▸ one_le_gapAfter (by omega) _ have hgP : g ≤ P := hg ▸ gapAfter_le _ _ have hgG : g ≤ G2 P := hg ▸ Finset.le_sup hedge have hslot := gapAfter_slot hedge'.2 hedge'.1 rw [← hg, show P - 1 + g = (g - 1) + P by omega, Nat.add_mod_right, Nat.mod_eq_of_lt (by omega)] at hslot obtain ⟨hc1, hc2⟩ := hslot have hr0 : g - 1 ≠ 0 := by intro h rw [h, Nat.coprime_zero_left] at hc1 omega have hr1 : g - 1 ≠ 1 := by intro h rw [h] at hc2 have := Nat.Coprime.eq_one_of_dvd hc2 h3 omega rw [hPdef] at hc1 hc2 have hA := prime_of_coprime_primorial hq (by omega) hc1 (by omega) have hB := prime_of_coprime_primorial hq (by omega) hc2 (by omega) exact ⟨g - 1, hA.1, by omega, hA.2, hB.2⟩ /-- The Gap Reformulation for every `p ≥ 2`; at `p = 2` the pair (3, 5) lies in the zone `(2, p'²)`. -/ theorem gap_reformulation {p q : ℕ} (hp : 2 ≤ p) (hq : IsNextPrime p q) (hG : G2 (primorial p) < q ^ 2 - 2) : ∃ r, p < r ∧ r + 2 < q ^ 2 ∧ r.Prime ∧ (r + 2).Prime := by rcases Nat.lt_or_ge p 3 with h | h · have hp2 : p = 2 := by omega subst hp2 have hq3 : 3 ≤ q := hq.2.1 have : 9 ≤ q ^ 2 := by nlinarith exact ⟨3, by norm_num, by omega, Nat.prime_three, by norm_num⟩ · exact twin_in_zone h hq hG /-- The lower bound on `p` is needed: at `p = 1`, `q = 2`, the hypothesis holds and no pair fits in `(1, 4)`. -/ theorem gap_reformulation_fails_at_one : IsNextPrime 1 2 ∧ G2 (primorial 1) < 2 ^ 2 - 2 ∧ ¬ ∃ r, 1 < r ∧ r + 2 < 2 ^ 2 ∧ r.Prime ∧ (r + 2).Prime := by refine ⟨⟨Nat.prime_two, by norm_num, fun ℓ hℓ _ => hℓ.two_le⟩, ?_, ?_⟩ · have := G2_le (primorial 1) rw [primorial_one] at this ⊢ omega · rintro ⟨r, h1, h2, -, -⟩ omega end ZoneGap