import LeanEq4.Cover /-! # Equation (4): `G2(P) ≥ g(P)` Two proofs. * `eq4_gap`, for every natural `P`: a one-class gap is a run of integers not coprime to `P`; none of them is admissible; so the run lies inside a two-class gap at least as long. * `eq4_cover`, for a product of distinct primes: the manuscript's own route. Take a one-class cover of `1, ..., g(P) - 1`, embed it as a two-class cover (`OneClassCover.toTwo`), and read off `g(P) ≤ G2(P)` from the two-class cover identity. `eq4` and `eq4_primorial` state the result for the functions `jac` and `G2`. -/ namespace LeanEq4 /-- Equation (4), relational form, for every natural `P`: if `g` is the largest gap between integers coprime to `P` and `G` the largest gap between admissible integers, then `g ≤ G`. -/ theorem eq4_gap {P g G : Nat} (hg : IsLargestGap (Coprime1 P) g) (hG : IsLargestGap (Admissible P) G) : g ≤ G := by obtain ⟨c, hc⟩ := hg.1 have hP : 0 < P := by refine Nat.pos_of_ne_zero fun h0 => ?_ subst h0 exact no_gap_coprime1_zero hc obtain ⟨hpos, _, _, hmid⟩ := hc obtain ⟨c', L, hL, hg'⟩ := (periodic_admissible hP).gap_of_run (s := c) (m := g - 1) fun i h1 h2 => not_admissible_of_not_coprime1 (hmid (c + i) (by omega) (by omega)) have := hG.2 c' L hg' omega /-- The largest one-class and two-class gaps exist for `P > 0`, and equation (4) holds between them. -/ theorem eq4_exists {P : Nat} (hP : 0 < P) : ∃ g G, IsLargestGap (Coprime1 P) g ∧ IsLargestGap (Admissible P) G ∧ g ≤ G := by obtain ⟨g, hg⟩ := (periodic_coprime1 hP).exists_largest obtain ⟨G, hG⟩ := (periodic_admissible hP).exists_largest exact ⟨g, G, hg, hG, eq4_gap hg hG⟩ /-- Equation (4) for the functions: `g(P) ≤ G2(P)` for every `P > 0`. -/ theorem eq4 {P : Nat} (hP : 0 < P) : jac P ≤ G2 P := eq4_gap (jac_spec hP) (G2_spec hP) /-- Equation (4) by the manuscript's argument, for the product of a list of distinct primes: embed the one-class cover of `1, ..., g(P) - 1` as a two-class cover. -/ theorem eq4_cover {ps : List Nat} (hpr : ∀ p, p ∈ ps → IsPrime p) (hnd : ps.Nodup) : jac ps.prod ≤ G2 ps.prod := by have hpos : 0 < jac ps.prod := by obtain ⟨c, hc⟩ := (jac_spec (prod_pos hpr)).1 exact hc.1 have h1 : OneClassCover ps (jac ps.prod - 1) := (oneCover_iff hpr hnd _).mpr (by omega) have h2 := (twoCover_iff hpr hnd _).mp h1.toTwo omega /-! ## The primorial `P(y)` -/ theorem primesUpTo_prime : ∀ y p, p ∈ primesUpTo y → IsPrime p | 0, _, h => absurd h List.not_mem_nil | y + 1, p, h => by unfold primesUpTo at h by_cases hy : IsPrime (y + 1) · rw [ite_eq_left hy] at h rcases List.mem_cons.mp h with h | h · exact h ▸ hy · exact primesUpTo_prime y p h · rw [ite_eq_right hy] at h exact primesUpTo_prime y p h theorem primesUpTo_le : ∀ y p, p ∈ primesUpTo y → p ≤ y | 0, _, h => absurd h List.not_mem_nil | y + 1, p, h => by unfold primesUpTo at h by_cases hy : IsPrime (y + 1) · rw [ite_eq_left hy] at h rcases List.mem_cons.mp h with h | h · omega · have := primesUpTo_le y p h; omega · rw [ite_eq_right hy] at h have := primesUpTo_le y p h; omega theorem primesUpTo_nodup : ∀ y, (primesUpTo y).Nodup | 0 => List.nodup_nil | y + 1 => by unfold primesUpTo by_cases hy : IsPrime (y + 1) · rw [ite_eq_left hy] exact List.nodup_cons.mpr ⟨fun h => by have := primesUpTo_le y _ h; omega, primesUpTo_nodup y⟩ · rw [ite_eq_right hy] exact primesUpTo_nodup y theorem primesUpTo_prod : ∀ y, (primesUpTo y).prod = primorial y | 0 => rfl | y + 1 => by unfold primesUpTo primorial by_cases hy : IsPrime (y + 1) · rw [ite_eq_left hy, ite_eq_left hy, List.prod_cons, primesUpTo_prod y] · rw [ite_eq_right hy, ite_eq_right hy, primesUpTo_prod y] theorem primorial_pos (y : Nat) : 0 < primorial y := by rw [← primesUpTo_prod] exact prod_pos (primesUpTo_prime y) /-- Equation (4) at the primorial: `G2(P(y)) ≥ g(P(y))` for every `y`. -/ theorem eq4_primorial (y : Nat) : jac (primorial y) ≤ G2 (primorial y) := by rw [← primesUpTo_prod] exact eq4_cover (primesUpTo_prime y) (primesUpTo_nodup y) /-- The embedding at the primorial, in cover form: a one-class cover of `1, ..., m` by the primes `p ≤ y` is a two-class cover, so `m + 1 ≤ G2(P(y))`. -/ theorem eq4_primorial_cover (y m : Nat) (h : OneClassCover (primesUpTo y) m) : m + 1 ≤ G2 (primorial y) := by rw [← primesUpTo_prod] exact (twoCover_iff (primesUpTo_prime y) (primesUpTo_nodup y) m).mp h.toTwo end LeanEq4