import LeanEq4.Eq4 /-! # The same gaps over the integers The manuscript defines `G2(P(y))` on the set `T_y = {n ∈ ℤ : gcd(n(n+2), P(y)) = 1}`, negative starts and gaps across a period boundary included. This file states the integer versions of the definitions and proves that, for `P > 0`, the largest integer gap equals the largest natural-number gap, for both survivor sets. So `jac P` and `G2 P` are the integer quantities of the manuscript. -/ namespace LeanEq4 /-- `gcd(n, P) = 1` for an integer `n`. -/ def Coprime1Z (P : Nat) (n : Int) : Prop := Int.gcd n P = 1 /-- `gcd(n(n+2), P) = 1` for an integer `n`. -/ def AdmissibleZ (P : Nat) (n : Int) : Prop := Int.gcd (n * (n + 2)) P = 1 /-- Consecutive members `c` and `c + L` of a set of integers. -/ def IsGapZ (S : Int → Prop) (c : Int) (L : Nat) : Prop := 0 < L ∧ S c ∧ S (c + L) ∧ ∀ m : Int, c < m → m < c + L → ¬ S m /-- The largest gap of a set of integers. -/ def IsLargestGapZ (S : Int → Prop) (G : Nat) : Prop := (∃ c, IsGapZ S c G) ∧ ∀ c L, IsGapZ S c L → L ≤ G /-- A set of integers `SZ` that agrees with `S` on the naturals and has period `P`. -/ structure Lifts (SZ : Int → Prop) (S : Nat → Prop) (P : Nat) : Prop where nat : ∀ n : Nat, SZ n ↔ S n per : ∀ n : Int, SZ (n + P) ↔ SZ n theorem Lifts.add_mul {SZ : Int → Prop} {S : Nat → Prop} {P : Nat} (h : Lifts SZ S P) (n : Int) : ∀ k : Nat, SZ (n + P * k) ↔ SZ n | 0 => by simp | k + 1 => by rw [show n + (P : Int) * ((k + 1 : Nat) : Int) = (n + P * k) + P by push_cast; grind] rw [h.per] exact h.add_mul n k theorem Lifts.gap_iff {SZ : Int → Prop} {S : Nat → Prop} {P : Nat} (h : Lifts SZ S P) (hP : 0 < P) (L : Nat) : (∃ c, IsGapZ SZ c L) ↔ ∃ c, IsGap S c L := by constructor · intro ⟨c, hL, hc, hcL, hmid⟩ -- shift `c` by `P * |c|` to a natural number start let k := c.natAbs have hk : (k : Int) ≤ (P : Int) * k := by have : k ≤ P * k := Nat.le_mul_of_pos_left k hP exact_mod_cast this have hck : 0 ≤ c + (P : Int) * k := by have : -c ≤ (k : Int) := by omega omega let c' := (c + (P : Int) * k).toNat have hc' : (c' : Int) = c + P * k := Int.toNat_of_nonneg hck refine ⟨c', hL, ?_, ?_, ?_⟩ · rw [← h.nat, hc', h.add_mul]; exact hc · rw [← h.nat] have : ((c' + L : Nat) : Int) = (c + L) + P * k := by push_cast; rw [hc']; omega rw [this, h.add_mul]; exact hcL · intro m h1 h2 hm have hm' := (h.nat m).mpr hm have : (m : Int) = (m - P * k) + P * k := by omega rw [this, h.add_mul] at hm' exact hmid _ (by omega) (by omega) hm' · intro ⟨c, hL, hc, hcL, hmid⟩ refine ⟨c, hL, (h.nat c).mpr hc, ?_, ?_⟩ · have := (h.nat (c + L)).mpr hcL push_cast at this; exact this · intro m h1 h2 hm have hm0 : 0 ≤ m := by omega have : ((m.toNat : Nat) : Int) = m := Int.toNat_of_nonneg hm0 rw [← this, h.nat] at hm exact hmid m.toNat (by omega) (by omega) hm theorem Lifts.largest_iff {SZ : Int → Prop} {S : Nat → Prop} {P : Nat} (h : Lifts SZ S P) (hP : 0 < P) (G : Nat) : IsLargestGapZ SZ G ↔ IsLargestGap S G := by constructor · intro ⟨h1, h2⟩ refine ⟨(h.gap_iff hP G).mp h1, fun c L hg => ?_⟩ obtain ⟨c', hc'⟩ := (h.gap_iff hP L).mpr ⟨c, hg⟩ exact h2 c' L hc' · intro ⟨h1, h2⟩ refine ⟨(h.gap_iff hP G).mpr h1, fun c L hg => ?_⟩ obtain ⟨c', hc'⟩ := (h.gap_iff hP L).mp ⟨c, hg⟩ exact h2 c' L hc' theorem coprime1Z_add (P : Nat) (n : Int) : Coprime1Z P (n + P) ↔ Coprime1Z P n := by unfold Coprime1Z rw [show n + (P : Int) = 1 * (P : Int) + n by omega, Int.gcd_mul_right_add_left] theorem admissibleZ_iff (P : Nat) (n : Int) : AdmissibleZ P n ↔ Coprime1Z P n ∧ Coprime1Z P (n + 2) := by unfold AdmissibleZ Coprime1Z Int.gcd rw [Int.natAbs_mul] exact Nat.coprime_mul_iff_left theorem lifts_coprime1 (P : Nat) : Lifts (Coprime1Z P) (Coprime1 P) P := ⟨fun n => by unfold Coprime1Z Coprime1 Int.gcd; simp, coprime1Z_add P⟩ theorem lifts_admissible (P : Nat) : Lifts (AdmissibleZ P) (Admissible P) P := by refine ⟨fun n => ?_, fun n => ?_⟩ · unfold AdmissibleZ Admissible Int.gcd rw [Int.natAbs_mul] simp only [Int.natAbs_natCast] rw [show ((n : Int) + 2).natAbs = n + 2 by omega] · rw [admissibleZ_iff, admissibleZ_iff, coprime1Z_add, show n + (P : Int) + 2 = (n + 2) + P by omega, coprime1Z_add] /-- `jac P` is the largest gap between consecutive integers in `ℤ` coprime to `P`. -/ theorem jac_spec_int {P : Nat} (hP : 0 < P) : IsLargestGapZ (Coprime1Z P) (jac P) := ((lifts_coprime1 P).largest_iff hP _).mpr (jac_spec hP) /-- `G2 P` is the largest gap between consecutive admissible integers in `ℤ`. -/ theorem G2_spec_int {P : Nat} (hP : 0 < P) : IsLargestGapZ (AdmissibleZ P) (G2 P) := ((lifts_admissible P).largest_iff hP _).mpr (G2_spec hP) /-- Equation (4) over the integers, for every `P > 0`: if `g` is the largest gap between consecutive integers coprime to `P` and `G` the largest gap between consecutive integers `n` with `gcd(n(n+2), P) = 1`, then `g ≤ G`. -/ theorem eq4_int {P g G : Nat} (hP : 0 < P) (hg : IsLargestGapZ (Coprime1Z P) g) (hG : IsLargestGapZ (AdmissibleZ P) G) : g ≤ G := eq4_gap (((lifts_coprime1 P).largest_iff hP g).mp hg) (((lifts_admissible P).largest_iff hP G).mp hG) /-- Equation (4) as printed, `G2(P(y)) ≥ g(P(y))`, with both sides the integer largest gaps of the manuscript, for every natural `y`. -/ theorem eq4_manuscript (y g G : Nat) (hg : IsLargestGapZ (Coprime1Z (primorial y)) g) (hG : IsLargestGapZ (AdmissibleZ (primorial y)) G) : g ≤ G := eq4_int (primorial_pos y) hg hG end LeanEq4