/-
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.
-/
module
public import FormalConjecturesUtil
public import FormalConjectures.GreensOpenProblems.«46»Erdős Problem 687
References:
Ben Green's Open Problem 46:
the same question; see Green46 in FormalConjectures.GreensOpenProblems.«46».
OEIS A058989: the values $Y(p_n)$, where $p_n$ is the $n$-th prime.
OEIS A048670: Jacobsthal's function of $\prod_{p \leq p_n} p$, which is $Y(p_n) + 1$.
[Er79d] Erdős, P., Some unconventional problems in number theory. Acta Math. Acad. Sci. Hungar. 33 (1979), 71-80.
[Er80] Erdős, Paul, A survey of problems in combinatorial number theory. Ann. Discrete Math. 6 (1980), 89-115.
[Er96b] Erdős, Paul, Some problems I presented or planned to present in my short talk. Analytic number theory, Vol. 1 (Allerton Park, IL, 1995), Progr. Math. 138 (1996), 333-335.
[Iw78] Iwaniec, Henryk, On the problem of Jacobsthal. Demonstratio Math. 11 (1978), 225-232. doi:10.1515/dema-1978-0121
[MaPo90] Maier, Helmut and Pomerance, Carl, Unusually large gaps between consecutive primes. Trans. Amer. Math. Soc. 322 (1990), 201-237.
[FGKMT18] Ford, Kevin and Green, Ben and Konyagin, Sergei and Maynard, James and Tao, Terence, Long gaps between primes. J. Amer. Math. Soc. 31 (2018), 65-105. arXiv:1412.5029
[OAI26a] OpenAI, A quadratic bound for Jacobsthal's function. OpenAI Math Release preprint (2026). https://github.com/openai/math/blob/adc7f1241b42e322a6451854ab7e4b4c146bf78a/preprints/A-quadratic-bound-for-Jacobsthals-function-September-25-2026/paper.pdf
@[expose] public sectionopen Filternamespace Erdos687
Y x is $Y(x)$, the maximal $y$ such that there is a choice of congruence classes $a_p$, one
for each prime $p \leq x$, such that every integer in $[1, y]$ is congruent to at least one of
the $a_p \pmod{p}$. The covering condition is Green46.IsCoveredByResidues x y.
We take $x$ to be a natural number, since $Y(x)$ only depends on $\lfloor x \rfloor$. The set of
such $y$ contains $0$ and is bounded by $\prod_{p \leq x} p$
(Erdos687.lt_primorial_of_isCoveredByResidues), so sSup is its maximum. $Y(x) = 0$ for
$x < 2$.
noncomputable def Y (x : ℕ) : ℕ :=
sSup {y : ℕ | Green46.IsCoveredByResidues x y}
Green46.maxY is Y cast to ℝ.
@[category test, AMS 11]
theorem maxY_eq_Y (x : ℕ) : Green46.maxY x = Y x := rflIf $[1, y]$ is covered by classes $a_p \pmod{p}$, $p \leq x$, then $y < \prod_{p \leq x} p$: by the Chinese remainder theorem some integer in $[1, \prod_{p \leq x} p]$ lies in none of the classes.
x:ℕy:ℕa:ℕ → ℕha:∀ m ∈ Finset.Icc 1 y, ∃ p ≤ x, Nat.Prime p ∧ m ≡ a p [MOD p]hy:primorial x ≤ yt:Finset ℕ := Finset.filter Nat.Prime (Finset.range (x + 1))hs:∀ p ∈ t, (fun p ↦ p) p ≠ 0pp:(↑t).Pairwise (Function.onFun Nat.Coprime fun p ↦ p)k:{ k // ∀ i ∈ t, k ≡ a i + 1 [MOD i] } := Nat.chineseRemainderOfFinset (fun p ↦ a p + 1) (fun p ↦ p) t hs pphk:↑k < primorial xm:ℕhm1:1 ≤ mhmP:m ≤ primorial xhmk:∀ p ∈ t, m ≡ ↑k [MOD p]p:ℕhpx:p ≤ xhp:Nat.Prime phpm:m ≡ a p [MOD p]hpt:p ∈ th1:a p ≡ a p + 1 [MOD p]hd:p ∣ 1⊢ False
exact hp.not_dvd_one hd All goals completed! 🐙With the single prime $2$, one class covers $1$ but no class covers both $1$ and $2$, so $Y(2) = 1$.
@[category test, AMS 11]
theorem Y_two : Y 2 = 1 := by ⊢ Y 2 = 1
have h1 : Green46.IsCoveredByResidues 2 1 := by
refine ⟨fun _ ↦ 1, fun m hm ↦ ⟨2, le_rfl, Nat.prime_two, ?_⟩⟩ m:ℕhm:m ∈ Finset.Icc 1 1⊢ m ≡ (fun x ↦ 1) 2 [MOD 2] h1:Green46.IsCoveredByResidues 2 1⊢ Y 2 = 1
have := Finset.mem_Icc.1 hm m:ℕhm:m ∈ Finset.Icc 1 1this:1 ≤ m ∧ m ≤ 1⊢ m ≡ (fun x ↦ 1) 2 [MOD 2] h1:Green46.IsCoveredByResidues 2 1⊢ Y 2 = 1
show m % 2 = 1 % 2 m:ℕhm:m ∈ Finset.Icc 1 1this:1 ≤ m ∧ m ≤ 1⊢ m % 2 = 1 % 2 h1:Green46.IsCoveredByResidues 2 1⊢ Y 2 = 1
omega h1:Green46.IsCoveredByResidues 2 1⊢ Y 2 = 1 h1:Green46.IsCoveredByResidues 2 1⊢ Y 2 = 1
have h2 : ∀ y, Green46.IsCoveredByResidues 2 y → y ≤ 1 := by
rintro y ⟨a, ha⟩ h1:Green46.IsCoveredByResidues 2 1y:ℕa:ℕ → ℕha:∀ m ∈ Finset.Icc 1 y, ∃ p ≤ 2, Nat.Prime p ∧ m ≡ a p [MOD p]⊢ y ≤ 1 h1:Green46.IsCoveredByResidues 2 1h2:∀ (y : ℕ), Green46.IsCoveredByResidues 2 y → y ≤ 1⊢ Y 2 = 1
by_contra hy h1:Green46.IsCoveredByResidues 2 1y:ℕa:ℕ → ℕha:∀ m ∈ Finset.Icc 1 y, ∃ p ≤ 2, Nat.Prime p ∧ m ≡ a p [MOD p]hy:¬y ≤ 1⊢ False h1:Green46.IsCoveredByResidues 2 1h2:∀ (y : ℕ), Green46.IsCoveredByResidues 2 y → y ≤ 1⊢ Y 2 = 1
obtain ⟨p, hp2, hp, hp1⟩ := ha 1 (Finset.mem_Icc.2 ⟨le_rfl, by h1:Green46.IsCoveredByResidues 2 1y:ℕa:ℕ → ℕha:∀ m ∈ Finset.Icc 1 y, ∃ p ≤ 2, Nat.Prime p ∧ m ≡ a p [MOD p]hy:¬y ≤ 1⊢ 1 ≤ y h1:Green46.IsCoveredByResidues 2 1y:ℕa:ℕ → ℕha:∀ m ∈ Finset.Icc 1 y, ∃ p ≤ 2, Nat.Prime p ∧ m ≡ a p [MOD p]hy:¬y ≤ 1p:ℕhp2:p ≤ 2hp:Nat.Prime php1:1 ≡ a p [MOD p]⊢ False h1:Green46.IsCoveredByResidues 2 1h2:∀ (y : ℕ), Green46.IsCoveredByResidues 2 y → y ≤ 1⊢ Y 2 = 1 omega All goals completed! 🐙 h1:Green46.IsCoveredByResidues 2 1y:ℕa:ℕ → ℕha:∀ m ∈ Finset.Icc 1 y, ∃ p ≤ 2, Nat.Prime p ∧ m ≡ a p [MOD p]hy:¬y ≤ 1p:ℕhp2:p ≤ 2hp:Nat.Prime php1:1 ≡ a p [MOD p]⊢ False h1:Green46.IsCoveredByResidues 2 1h2:∀ (y : ℕ), Green46.IsCoveredByResidues 2 y → y ≤ 1⊢ Y 2 = 1⟩) h1:Green46.IsCoveredByResidues 2 1y:ℕa:ℕ → ℕha:∀ m ∈ Finset.Icc 1 y, ∃ p ≤ 2, Nat.Prime p ∧ m ≡ a p [MOD p]hy:¬y ≤ 1p:ℕhp2:p ≤ 2hp:Nat.Prime php1:1 ≡ a p [MOD p]⊢ False h1:Green46.IsCoveredByResidues 2 1h2:∀ (y : ℕ), Green46.IsCoveredByResidues 2 y → y ≤ 1⊢ Y 2 = 1
obtain ⟨q, hq2, hq, hq1⟩ := ha 2 (Finset.mem_Icc.2 ⟨by h1:Green46.IsCoveredByResidues 2 1y:ℕa:ℕ → ℕha:∀ m ∈ Finset.Icc 1 y, ∃ p ≤ 2, Nat.Prime p ∧ m ≡ a p [MOD p]hy:¬y ≤ 1p:ℕhp2:p ≤ 2hp:Nat.Prime php1:1 ≡ a p [MOD p]⊢ 1 ≤ 2 h1:Green46.IsCoveredByResidues 2 1y:ℕa:ℕ → ℕha:∀ m ∈ Finset.Icc 1 y, ∃ p ≤ 2, Nat.Prime p ∧ m ≡ a p [MOD p]hy:¬y ≤ 1p:ℕhp2:p ≤ 2hp:Nat.Prime php1:1 ≡ a p [MOD p]q:ℕhq2:q ≤ 2hq:Nat.Prime qhq1:2 ≡ a q [MOD q]⊢ False h1:Green46.IsCoveredByResidues 2 1h2:∀ (y : ℕ), Green46.IsCoveredByResidues 2 y → y ≤ 1⊢ Y 2 = 1 omega All goals completed! 🐙 h1:Green46.IsCoveredByResidues 2 1y:ℕa:ℕ → ℕha:∀ m ∈ Finset.Icc 1 y, ∃ p ≤ 2, Nat.Prime p ∧ m ≡ a p [MOD p]hy:¬y ≤ 1p:ℕhp2:p ≤ 2hp:Nat.Prime php1:1 ≡ a p [MOD p]q:ℕhq2:q ≤ 2hq:Nat.Prime qhq1:2 ≡ a q [MOD q]⊢ False h1:Green46.IsCoveredByResidues 2 1h2:∀ (y : ℕ), Green46.IsCoveredByResidues 2 y → y ≤ 1⊢ Y 2 = 1, by h1:Green46.IsCoveredByResidues 2 1y:ℕa:ℕ → ℕha:∀ m ∈ Finset.Icc 1 y, ∃ p ≤ 2, Nat.Prime p ∧ m ≡ a p [MOD p]hy:¬y ≤ 1p:ℕhp2:p ≤ 2hp:Nat.Prime php1:1 ≡ a p [MOD p]⊢ 2 ≤ y h1:Green46.IsCoveredByResidues 2 1y:ℕa:ℕ → ℕha:∀ m ∈ Finset.Icc 1 y, ∃ p ≤ 2, Nat.Prime p ∧ m ≡ a p [MOD p]hy:¬y ≤ 1p:ℕhp2:p ≤ 2hp:Nat.Prime php1:1 ≡ a p [MOD p]q:ℕhq2:q ≤ 2hq:Nat.Prime qhq1:2 ≡ a q [MOD q]⊢ False h1:Green46.IsCoveredByResidues 2 1h2:∀ (y : ℕ), Green46.IsCoveredByResidues 2 y → y ≤ 1⊢ Y 2 = 1 omega All goals completed! 🐙 h1:Green46.IsCoveredByResidues 2 1y:ℕa:ℕ → ℕha:∀ m ∈ Finset.Icc 1 y, ∃ p ≤ 2, Nat.Prime p ∧ m ≡ a p [MOD p]hy:¬y ≤ 1p:ℕhp2:p ≤ 2hp:Nat.Prime php1:1 ≡ a p [MOD p]q:ℕhq2:q ≤ 2hq:Nat.Prime qhq1:2 ≡ a q [MOD q]⊢ False h1:Green46.IsCoveredByResidues 2 1h2:∀ (y : ℕ), Green46.IsCoveredByResidues 2 y → y ≤ 1⊢ Y 2 = 1⟩) h1:Green46.IsCoveredByResidues 2 1y:ℕa:ℕ → ℕha:∀ m ∈ Finset.Icc 1 y, ∃ p ≤ 2, Nat.Prime p ∧ m ≡ a p [MOD p]hy:¬y ≤ 1p:ℕhp2:p ≤ 2hp:Nat.Prime php1:1 ≡ a p [MOD p]q:ℕhq2:q ≤ 2hq:Nat.Prime qhq1:2 ≡ a q [MOD q]⊢ False h1:Green46.IsCoveredByResidues 2 1h2:∀ (y : ℕ), Green46.IsCoveredByResidues 2 y → y ≤ 1⊢ Y 2 = 1
rw [le_antisymm hp2 hp.two_le h1:Green46.IsCoveredByResidues 2 1y:ℕa:ℕ → ℕha:∀ m ∈ Finset.Icc 1 y, ∃ p ≤ 2, Nat.Prime p ∧ m ≡ a p [MOD p]hy:¬y ≤ 1p:ℕhp2:p ≤ 2hp:Nat.Prime php1:1 ≡ a 2 [MOD 2]q:ℕhq2:q ≤ 2hq:Nat.Prime qhq1:2 ≡ a q [MOD q]⊢ False h1:Green46.IsCoveredByResidues 2 1y:ℕa:ℕ → ℕha:∀ m ∈ Finset.Icc 1 y, ∃ p ≤ 2, Nat.Prime p ∧ m ≡ a p [MOD p]hy:¬y ≤ 1p:ℕhp2:p ≤ 2hp:Nat.Prime php1:1 ≡ a 2 [MOD 2]q:ℕhq2:q ≤ 2hq:Nat.Prime qhq1:2 ≡ a q [MOD q]⊢ False h1:Green46.IsCoveredByResidues 2 1h2:∀ (y : ℕ), Green46.IsCoveredByResidues 2 y → y ≤ 1⊢ Y 2 = 1] at hp1 h1:Green46.IsCoveredByResidues 2 1y:ℕa:ℕ → ℕha:∀ m ∈ Finset.Icc 1 y, ∃ p ≤ 2, Nat.Prime p ∧ m ≡ a p [MOD p]hy:¬y ≤ 1p:ℕhp2:p ≤ 2hp:Nat.Prime php1:1 ≡ a 2 [MOD 2]q:ℕhq2:q ≤ 2hq:Nat.Prime qhq1:2 ≡ a q [MOD q]⊢ False h1:Green46.IsCoveredByResidues 2 1h2:∀ (y : ℕ), Green46.IsCoveredByResidues 2 y → y ≤ 1⊢ Y 2 = 1
rw [le_antisymm hq2 hq.two_le h1:Green46.IsCoveredByResidues 2 1y:ℕa:ℕ → ℕha:∀ m ∈ Finset.Icc 1 y, ∃ p ≤ 2, Nat.Prime p ∧ m ≡ a p [MOD p]hy:¬y ≤ 1p:ℕhp2:p ≤ 2hp:Nat.Prime php1:1 ≡ a 2 [MOD 2]q:ℕhq2:q ≤ 2hq:Nat.Prime qhq1:2 ≡ a 2 [MOD 2]⊢ False h1:Green46.IsCoveredByResidues 2 1y:ℕa:ℕ → ℕha:∀ m ∈ Finset.Icc 1 y, ∃ p ≤ 2, Nat.Prime p ∧ m ≡ a p [MOD p]hy:¬y ≤ 1p:ℕhp2:p ≤ 2hp:Nat.Prime php1:1 ≡ a 2 [MOD 2]q:ℕhq2:q ≤ 2hq:Nat.Prime qhq1:2 ≡ a 2 [MOD 2]⊢ False h1:Green46.IsCoveredByResidues 2 1h2:∀ (y : ℕ), Green46.IsCoveredByResidues 2 y → y ≤ 1⊢ Y 2 = 1] at hq1 h1:Green46.IsCoveredByResidues 2 1y:ℕa:ℕ → ℕha:∀ m ∈ Finset.Icc 1 y, ∃ p ≤ 2, Nat.Prime p ∧ m ≡ a p [MOD p]hy:¬y ≤ 1p:ℕhp2:p ≤ 2hp:Nat.Prime php1:1 ≡ a 2 [MOD 2]q:ℕhq2:q ≤ 2hq:Nat.Prime qhq1:2 ≡ a 2 [MOD 2]⊢ False h1:Green46.IsCoveredByResidues 2 1h2:∀ (y : ℕ), Green46.IsCoveredByResidues 2 y → y ≤ 1⊢ Y 2 = 1
exact absurd (hp1.trans hq1.symm) (by h1:Green46.IsCoveredByResidues 2 1y:ℕa:ℕ → ℕha:∀ m ∈ Finset.Icc 1 y, ∃ p ≤ 2, Nat.Prime p ∧ m ≡ a p [MOD p]hy:¬y ≤ 1p:ℕhp2:p ≤ 2hp:Nat.Prime php1:1 ≡ a 2 [MOD 2]q:ℕhq2:q ≤ 2hq:Nat.Prime qhq1:2 ≡ a 2 [MOD 2]⊢ ¬1 ≡ 2 [MOD 2] h1:Green46.IsCoveredByResidues 2 1h2:∀ (y : ℕ), Green46.IsCoveredByResidues 2 y → y ≤ 1⊢ Y 2 = 1 decide All goals completed! 🐙 h1:Green46.IsCoveredByResidues 2 1h2:∀ (y : ℕ), Green46.IsCoveredByResidues 2 y → y ≤ 1⊢ Y 2 = 1) h1:Green46.IsCoveredByResidues 2 1h2:∀ (y : ℕ), Green46.IsCoveredByResidues 2 y → y ≤ 1⊢ Y 2 = 1
rw [Y h1:Green46.IsCoveredByResidues 2 1h2:∀ (y : ℕ), Green46.IsCoveredByResidues 2 y → y ≤ 1⊢ sSup {y | Green46.IsCoveredByResidues 2 y} = 1 h1:Green46.IsCoveredByResidues 2 1h2:∀ (y : ℕ), Green46.IsCoveredByResidues 2 y → y ≤ 1⊢ sSup {y | Green46.IsCoveredByResidues 2 y} = 1] h1:Green46.IsCoveredByResidues 2 1h2:∀ (y : ℕ), Green46.IsCoveredByResidues 2 y → y ≤ 1⊢ sSup {y | Green46.IsCoveredByResidues 2 y} = 1
exact IsGreatest.csSup_eq ⟨h1, h2⟩ All goals completed! 🐙The classes $1 \pmod 2$ and $2 \pmod 3$ cover $1, 2, 3$, but no choice of classes modulo $2$ and $3$ covers $1, 2, 3, 4$, so $Y(3) = 3$.
@[category test, AMS 11]
theorem Y_three : Y 3 = 3 := by ⊢ Y 3 = 3
have h1 : Green46.IsCoveredByResidues 3 3 := by
refine ⟨fun p ↦ if p = 2 then 1 else 2, fun m hm ↦ ?_⟩ m:ℕhm:m ∈ Finset.Icc 1 3⊢ ∃ p ≤ 3, Nat.Prime p ∧ m ≡ (fun p ↦ if p = 2 then 1 else 2) p [MOD p] h1:Green46.IsCoveredByResidues 3 3⊢ Y 3 = 3
obtain ⟨hm1, hm3⟩ := Finset.mem_Icc.1 hm m:ℕhm:m ∈ Finset.Icc 1 3hm1:1 ≤ mhm3:m ≤ 3⊢ ∃ p ≤ 3, Nat.Prime p ∧ m ≡ (fun p ↦ if p = 2 then 1 else 2) p [MOD p] h1:Green46.IsCoveredByResidues 3 3⊢ Y 3 = 3
interval_cases m «1» m:ℕhm:1 ∈ Finset.Icc 1 3hm1:1 ≤ 1hm3:1 ≤ 3⊢ ∃ p ≤ 3, Nat.Prime p ∧ 1 ≡ (fun p ↦ if p = 2 then 1 else 2) p [MOD p]«2» m:ℕhm:2 ∈ Finset.Icc 1 3hm1:1 ≤ 2hm3:2 ≤ 3⊢ ∃ p ≤ 3, Nat.Prime p ∧ 2 ≡ (fun p ↦ if p = 2 then 1 else 2) p [MOD p]«3» m:ℕhm:3 ∈ Finset.Icc 1 3hm1:1 ≤ 3hm3:3 ≤ 3⊢ ∃ p ≤ 3, Nat.Prime p ∧ 3 ≡ (fun p ↦ if p = 2 then 1 else 2) p [MOD p] h1:Green46.IsCoveredByResidues 3 3⊢ Y 3 = 3
· «1» m:ℕhm:1 ∈ Finset.Icc 1 3hm1:1 ≤ 1hm3:1 ≤ 3⊢ ∃ p ≤ 3, Nat.Prime p ∧ 1 ≡ (fun p ↦ if p = 2 then 1 else 2) p [MOD p] h1:Green46.IsCoveredByResidues 3 3⊢ Y 3 = 3 exact ⟨2, by m:ℕhm:1 ∈ Finset.Icc 1 3hm1:1 ≤ 1hm3:1 ≤ 3⊢ 2 ≤ 3 h1:Green46.IsCoveredByResidues 3 3⊢ Y 3 = 3 norm_num All goals completed! 🐙 h1:Green46.IsCoveredByResidues 3 3⊢ Y 3 = 3, Nat.prime_two, by m:ℕhm:1 ∈ Finset.Icc 1 3hm1:1 ≤ 1hm3:1 ≤ 3⊢ 1 ≡ (fun p ↦ if p = 2 then 1 else 2) 2 [MOD 2] h1:Green46.IsCoveredByResidues 3 3⊢ Y 3 = 3 decide All goals completed! 🐙 h1:Green46.IsCoveredByResidues 3 3⊢ Y 3 = 3⟩
· «2» m:ℕhm:2 ∈ Finset.Icc 1 3hm1:1 ≤ 2hm3:2 ≤ 3⊢ ∃ p ≤ 3, Nat.Prime p ∧ 2 ≡ (fun p ↦ if p = 2 then 1 else 2) p [MOD p] h1:Green46.IsCoveredByResidues 3 3⊢ Y 3 = 3 exact ⟨3, le_rfl, Nat.prime_three, by m:ℕhm:2 ∈ Finset.Icc 1 3hm1:1 ≤ 2hm3:2 ≤ 3⊢ 2 ≡ (fun p ↦ if p = 2 then 1 else 2) 3 [MOD 3] h1:Green46.IsCoveredByResidues 3 3⊢ Y 3 = 3 decide All goals completed! 🐙 h1:Green46.IsCoveredByResidues 3 3⊢ Y 3 = 3⟩
· «3» m:ℕhm:3 ∈ Finset.Icc 1 3hm1:1 ≤ 3hm3:3 ≤ 3⊢ ∃ p ≤ 3, Nat.Prime p ∧ 3 ≡ (fun p ↦ if p = 2 then 1 else 2) p [MOD p] h1:Green46.IsCoveredByResidues 3 3⊢ Y 3 = 3 exact ⟨2, by m:ℕhm:3 ∈ Finset.Icc 1 3hm1:1 ≤ 3hm3:3 ≤ 3⊢ 2 ≤ 3 h1:Green46.IsCoveredByResidues 3 3⊢ Y 3 = 3 norm_num All goals completed! 🐙 h1:Green46.IsCoveredByResidues 3 3⊢ Y 3 = 3, Nat.prime_two, by m:ℕhm:3 ∈ Finset.Icc 1 3hm1:1 ≤ 3hm3:3 ≤ 3⊢ 3 ≡ (fun p ↦ if p = 2 then 1 else 2) 2 [MOD 2] h1:Green46.IsCoveredByResidues 3 3⊢ Y 3 = 3 decide All goals completed! 🐙 h1:Green46.IsCoveredByResidues 3 3⊢ Y 3 = 3⟩ h1:Green46.IsCoveredByResidues 3 3⊢ Y 3 = 3
have h2 : ∀ y, Green46.IsCoveredByResidues 3 y → y ≤ 3 := by
rintro y ⟨a, ha⟩ h1:Green46.IsCoveredByResidues 3 3y:ℕa:ℕ → ℕha:∀ m ∈ Finset.Icc 1 y, ∃ p ≤ 3, Nat.Prime p ∧ m ≡ a p [MOD p]⊢ y ≤ 3 h1:Green46.IsCoveredByResidues 3 3h2:∀ (y : ℕ), Green46.IsCoveredByResidues 3 y → y ≤ 3⊢ Y 3 = 3
by_contra hy h1:Green46.IsCoveredByResidues 3 3y:ℕa:ℕ → ℕha:∀ m ∈ Finset.Icc 1 y, ∃ p ≤ 3, Nat.Prime p ∧ m ≡ a p [MOD p]hy:¬y ≤ 3⊢ False h1:Green46.IsCoveredByResidues 3 3h2:∀ (y : ℕ), Green46.IsCoveredByResidues 3 y → y ≤ 3⊢ Y 3 = 3
have key : ∀ m, 1 ≤ m → m ≤ 4 → m % 2 = a 2 % 2 ∨ m % 3 = a 3 % 3 := by ⊢ Y 3 = 3 h1:Green46.IsCoveredByResidues 3 3y:ℕa:ℕ → ℕha:∀ m ∈ Finset.Icc 1 y, ∃ p ≤ 3, Nat.Prime p ∧ m ≡ a p [MOD p]hy:¬y ≤ 3key:∀ (m : ℕ), 1 ≤ m → m ≤ 4 → m % 2 = a 2 % 2 ∨ m % 3 = a 3 % 3⊢ False h1:Green46.IsCoveredByResidues 3 3h2:∀ (y : ℕ), Green46.IsCoveredByResidues 3 y → y ≤ 3⊢ Y 3 = 3
intro m hm1 hm4 h1:Green46.IsCoveredByResidues 3 3y:ℕa:ℕ → ℕha:∀ m ∈ Finset.Icc 1 y, ∃ p ≤ 3, Nat.Prime p ∧ m ≡ a p [MOD p]hy:¬y ≤ 3m:ℕhm1:1 ≤ mhm4:m ≤ 4⊢ m % 2 = a 2 % 2 ∨ m % 3 = a 3 % 3 h1:Green46.IsCoveredByResidues 3 3y:ℕa:ℕ → ℕha:∀ m ∈ Finset.Icc 1 y, ∃ p ≤ 3, Nat.Prime p ∧ m ≡ a p [MOD p]hy:¬y ≤ 3key:∀ (m : ℕ), 1 ≤ m → m ≤ 4 → m % 2 = a 2 % 2 ∨ m % 3 = a 3 % 3⊢ False h1:Green46.IsCoveredByResidues 3 3h2:∀ (y : ℕ), Green46.IsCoveredByResidues 3 y → y ≤ 3⊢ Y 3 = 3
obtain ⟨p, hp3, hp, hpm⟩ := ha m (Finset.mem_Icc.2 ⟨hm1, by h1:Green46.IsCoveredByResidues 3 3y:ℕa:ℕ → ℕha:∀ m ∈ Finset.Icc 1 y, ∃ p ≤ 3, Nat.Prime p ∧ m ≡ a p [MOD p]hy:¬y ≤ 3m:ℕhm1:1 ≤ mhm4:m ≤ 4⊢ m ≤ y h1:Green46.IsCoveredByResidues 3 3y:ℕa:ℕ → ℕha:∀ m ∈ Finset.Icc 1 y, ∃ p ≤ 3, Nat.Prime p ∧ m ≡ a p [MOD p]hy:¬y ≤ 3m:ℕhm1:1 ≤ mhm4:m ≤ 4p:ℕhp3:p ≤ 3hp:Nat.Prime phpm:m ≡ a p [MOD p]⊢ m % 2 = a 2 % 2 ∨ m % 3 = a 3 % 3 h1:Green46.IsCoveredByResidues 3 3y:ℕa:ℕ → ℕha:∀ m ∈ Finset.Icc 1 y, ∃ p ≤ 3, Nat.Prime p ∧ m ≡ a p [MOD p]hy:¬y ≤ 3key:∀ (m : ℕ), 1 ≤ m → m ≤ 4 → m % 2 = a 2 % 2 ∨ m % 3 = a 3 % 3⊢ False h1:Green46.IsCoveredByResidues 3 3h2:∀ (y : ℕ), Green46.IsCoveredByResidues 3 y → y ≤ 3⊢ Y 3 = 3 omega All goals completed! 🐙 h1:Green46.IsCoveredByResidues 3 3y:ℕa:ℕ → ℕha:∀ m ∈ Finset.Icc 1 y, ∃ p ≤ 3, Nat.Prime p ∧ m ≡ a p [MOD p]hy:¬y ≤ 3m:ℕhm1:1 ≤ mhm4:m ≤ 4p:ℕhp3:p ≤ 3hp:Nat.Prime phpm:m ≡ a p [MOD p]⊢ m % 2 = a 2 % 2 ∨ m % 3 = a 3 % 3 h1:Green46.IsCoveredByResidues 3 3y:ℕa:ℕ → ℕha:∀ m ∈ Finset.Icc 1 y, ∃ p ≤ 3, Nat.Prime p ∧ m ≡ a p [MOD p]hy:¬y ≤ 3key:∀ (m : ℕ), 1 ≤ m → m ≤ 4 → m % 2 = a 2 % 2 ∨ m % 3 = a 3 % 3⊢ False h1:Green46.IsCoveredByResidues 3 3h2:∀ (y : ℕ), Green46.IsCoveredByResidues 3 y → y ≤ 3⊢ Y 3 = 3⟩) h1:Green46.IsCoveredByResidues 3 3y:ℕa:ℕ → ℕha:∀ m ∈ Finset.Icc 1 y, ∃ p ≤ 3, Nat.Prime p ∧ m ≡ a p [MOD p]hy:¬y ≤ 3m:ℕhm1:1 ≤ mhm4:m ≤ 4p:ℕhp3:p ≤ 3hp:Nat.Prime phpm:m ≡ a p [MOD p]⊢ m % 2 = a 2 % 2 ∨ m % 3 = a 3 % 3 h1:Green46.IsCoveredByResidues 3 3y:ℕa:ℕ → ℕha:∀ m ∈ Finset.Icc 1 y, ∃ p ≤ 3, Nat.Prime p ∧ m ≡ a p [MOD p]hy:¬y ≤ 3key:∀ (m : ℕ), 1 ≤ m → m ≤ 4 → m % 2 = a 2 % 2 ∨ m % 3 = a 3 % 3⊢ False h1:Green46.IsCoveredByResidues 3 3h2:∀ (y : ℕ), Green46.IsCoveredByResidues 3 y → y ≤ 3⊢ Y 3 = 3
interval_cases p «0» h1:Green46.IsCoveredByResidues 3 3y:ℕa:ℕ → ℕha:∀ m ∈ Finset.Icc 1 y, ∃ p ≤ 3, Nat.Prime p ∧ m ≡ a p [MOD p]hy:¬y ≤ 3m:ℕhm1:1 ≤ mhm4:m ≤ 4p:ℕhp3:0 ≤ 3hp:Nat.Prime 0hpm:m ≡ a 0 [MOD 0]⊢ m % 2 = a 2 % 2 ∨ m % 3 = a 3 % 3«1» h1:Green46.IsCoveredByResidues 3 3y:ℕa:ℕ → ℕha:∀ m ∈ Finset.Icc 1 y, ∃ p ≤ 3, Nat.Prime p ∧ m ≡ a p [MOD p]hy:¬y ≤ 3m:ℕhm1:1 ≤ mhm4:m ≤ 4p:ℕhp3:1 ≤ 3hp:Nat.Prime 1hpm:m ≡ a 1 [MOD 1]⊢ m % 2 = a 2 % 2 ∨ m % 3 = a 3 % 3«2» h1:Green46.IsCoveredByResidues 3 3y:ℕa:ℕ → ℕha:∀ m ∈ Finset.Icc 1 y, ∃ p ≤ 3, Nat.Prime p ∧ m ≡ a p [MOD p]hy:¬y ≤ 3m:ℕhm1:1 ≤ mhm4:m ≤ 4p:ℕhp3:2 ≤ 3hp:Nat.Prime 2hpm:m ≡ a 2 [MOD 2]⊢ m % 2 = a 2 % 2 ∨ m % 3 = a 3 % 3«3» h1:Green46.IsCoveredByResidues 3 3y:ℕa:ℕ → ℕha:∀ m ∈ Finset.Icc 1 y, ∃ p ≤ 3, Nat.Prime p ∧ m ≡ a p [MOD p]hy:¬y ≤ 3m:ℕhm1:1 ≤ mhm4:m ≤ 4p:ℕhp3:3 ≤ 3hp:Nat.Prime 3hpm:m ≡ a 3 [MOD 3]⊢ m % 2 = a 2 % 2 ∨ m % 3 = a 3 % 3 h1:Green46.IsCoveredByResidues 3 3y:ℕa:ℕ → ℕha:∀ m ∈ Finset.Icc 1 y, ∃ p ≤ 3, Nat.Prime p ∧ m ≡ a p [MOD p]hy:¬y ≤ 3key:∀ (m : ℕ), 1 ≤ m → m ≤ 4 → m % 2 = a 2 % 2 ∨ m % 3 = a 3 % 3⊢ False h1:Green46.IsCoveredByResidues 3 3h2:∀ (y : ℕ), Green46.IsCoveredByResidues 3 y → y ≤ 3⊢ Y 3 = 3
· «0» h1:Green46.IsCoveredByResidues 3 3y:ℕa:ℕ → ℕha:∀ m ∈ Finset.Icc 1 y, ∃ p ≤ 3, Nat.Prime p ∧ m ≡ a p [MOD p]hy:¬y ≤ 3m:ℕhm1:1 ≤ mhm4:m ≤ 4p:ℕhp3:0 ≤ 3hp:Nat.Prime 0hpm:m ≡ a 0 [MOD 0]⊢ m % 2 = a 2 % 2 ∨ m % 3 = a 3 % 3 h1:Green46.IsCoveredByResidues 3 3y:ℕa:ℕ → ℕha:∀ m ∈ Finset.Icc 1 y, ∃ p ≤ 3, Nat.Prime p ∧ m ≡ a p [MOD p]hy:¬y ≤ 3key:∀ (m : ℕ), 1 ≤ m → m ≤ 4 → m % 2 = a 2 % 2 ∨ m % 3 = a 3 % 3⊢ False h1:Green46.IsCoveredByResidues 3 3h2:∀ (y : ℕ), Green46.IsCoveredByResidues 3 y → y ≤ 3⊢ Y 3 = 3 exact absurd hp (by h1:Green46.IsCoveredByResidues 3 3y:ℕa:ℕ → ℕha:∀ m ∈ Finset.Icc 1 y, ∃ p ≤ 3, Nat.Prime p ∧ m ≡ a p [MOD p]hy:¬y ≤ 3m:ℕhm1:1 ≤ mhm4:m ≤ 4p:ℕhp3:0 ≤ 3hp:Nat.Prime 0hpm:m ≡ a 0 [MOD 0]⊢ ¬Nat.Prime 0 h1:Green46.IsCoveredByResidues 3 3y:ℕa:ℕ → ℕha:∀ m ∈ Finset.Icc 1 y, ∃ p ≤ 3, Nat.Prime p ∧ m ≡ a p [MOD p]hy:¬y ≤ 3key:∀ (m : ℕ), 1 ≤ m → m ≤ 4 → m % 2 = a 2 % 2 ∨ m % 3 = a 3 % 3⊢ False h1:Green46.IsCoveredByResidues 3 3h2:∀ (y : ℕ), Green46.IsCoveredByResidues 3 y → y ≤ 3⊢ Y 3 = 3 decide All goals completed! 🐙 h1:Green46.IsCoveredByResidues 3 3y:ℕa:ℕ → ℕha:∀ m ∈ Finset.Icc 1 y, ∃ p ≤ 3, Nat.Prime p ∧ m ≡ a p [MOD p]hy:¬y ≤ 3key:∀ (m : ℕ), 1 ≤ m → m ≤ 4 → m % 2 = a 2 % 2 ∨ m % 3 = a 3 % 3⊢ False h1:Green46.IsCoveredByResidues 3 3h2:∀ (y : ℕ), Green46.IsCoveredByResidues 3 y → y ≤ 3⊢ Y 3 = 3)
· «1» h1:Green46.IsCoveredByResidues 3 3y:ℕa:ℕ → ℕha:∀ m ∈ Finset.Icc 1 y, ∃ p ≤ 3, Nat.Prime p ∧ m ≡ a p [MOD p]hy:¬y ≤ 3m:ℕhm1:1 ≤ mhm4:m ≤ 4p:ℕhp3:1 ≤ 3hp:Nat.Prime 1hpm:m ≡ a 1 [MOD 1]⊢ m % 2 = a 2 % 2 ∨ m % 3 = a 3 % 3 h1:Green46.IsCoveredByResidues 3 3y:ℕa:ℕ → ℕha:∀ m ∈ Finset.Icc 1 y, ∃ p ≤ 3, Nat.Prime p ∧ m ≡ a p [MOD p]hy:¬y ≤ 3key:∀ (m : ℕ), 1 ≤ m → m ≤ 4 → m % 2 = a 2 % 2 ∨ m % 3 = a 3 % 3⊢ False h1:Green46.IsCoveredByResidues 3 3h2:∀ (y : ℕ), Green46.IsCoveredByResidues 3 y → y ≤ 3⊢ Y 3 = 3 exact absurd hp (by h1:Green46.IsCoveredByResidues 3 3y:ℕa:ℕ → ℕha:∀ m ∈ Finset.Icc 1 y, ∃ p ≤ 3, Nat.Prime p ∧ m ≡ a p [MOD p]hy:¬y ≤ 3m:ℕhm1:1 ≤ mhm4:m ≤ 4p:ℕhp3:1 ≤ 3hp:Nat.Prime 1hpm:m ≡ a 1 [MOD 1]⊢ ¬Nat.Prime 1 h1:Green46.IsCoveredByResidues 3 3y:ℕa:ℕ → ℕha:∀ m ∈ Finset.Icc 1 y, ∃ p ≤ 3, Nat.Prime p ∧ m ≡ a p [MOD p]hy:¬y ≤ 3key:∀ (m : ℕ), 1 ≤ m → m ≤ 4 → m % 2 = a 2 % 2 ∨ m % 3 = a 3 % 3⊢ False h1:Green46.IsCoveredByResidues 3 3h2:∀ (y : ℕ), Green46.IsCoveredByResidues 3 y → y ≤ 3⊢ Y 3 = 3 decide All goals completed! 🐙 h1:Green46.IsCoveredByResidues 3 3y:ℕa:ℕ → ℕha:∀ m ∈ Finset.Icc 1 y, ∃ p ≤ 3, Nat.Prime p ∧ m ≡ a p [MOD p]hy:¬y ≤ 3key:∀ (m : ℕ), 1 ≤ m → m ≤ 4 → m % 2 = a 2 % 2 ∨ m % 3 = a 3 % 3⊢ False h1:Green46.IsCoveredByResidues 3 3h2:∀ (y : ℕ), Green46.IsCoveredByResidues 3 y → y ≤ 3⊢ Y 3 = 3)
· «2» h1:Green46.IsCoveredByResidues 3 3y:ℕa:ℕ → ℕha:∀ m ∈ Finset.Icc 1 y, ∃ p ≤ 3, Nat.Prime p ∧ m ≡ a p [MOD p]hy:¬y ≤ 3m:ℕhm1:1 ≤ mhm4:m ≤ 4p:ℕhp3:2 ≤ 3hp:Nat.Prime 2hpm:m ≡ a 2 [MOD 2]⊢ m % 2 = a 2 % 2 ∨ m % 3 = a 3 % 3 h1:Green46.IsCoveredByResidues 3 3y:ℕa:ℕ → ℕha:∀ m ∈ Finset.Icc 1 y, ∃ p ≤ 3, Nat.Prime p ∧ m ≡ a p [MOD p]hy:¬y ≤ 3key:∀ (m : ℕ), 1 ≤ m → m ≤ 4 → m % 2 = a 2 % 2 ∨ m % 3 = a 3 % 3⊢ False h1:Green46.IsCoveredByResidues 3 3h2:∀ (y : ℕ), Green46.IsCoveredByResidues 3 y → y ≤ 3⊢ Y 3 = 3 exact Or.inl hpm All goals completed! 🐙 h1:Green46.IsCoveredByResidues 3 3y:ℕa:ℕ → ℕha:∀ m ∈ Finset.Icc 1 y, ∃ p ≤ 3, Nat.Prime p ∧ m ≡ a p [MOD p]hy:¬y ≤ 3key:∀ (m : ℕ), 1 ≤ m → m ≤ 4 → m % 2 = a 2 % 2 ∨ m % 3 = a 3 % 3⊢ False h1:Green46.IsCoveredByResidues 3 3h2:∀ (y : ℕ), Green46.IsCoveredByResidues 3 y → y ≤ 3⊢ Y 3 = 3
· «3» h1:Green46.IsCoveredByResidues 3 3y:ℕa:ℕ → ℕha:∀ m ∈ Finset.Icc 1 y, ∃ p ≤ 3, Nat.Prime p ∧ m ≡ a p [MOD p]hy:¬y ≤ 3m:ℕhm1:1 ≤ mhm4:m ≤ 4p:ℕhp3:3 ≤ 3hp:Nat.Prime 3hpm:m ≡ a 3 [MOD 3]⊢ m % 2 = a 2 % 2 ∨ m % 3 = a 3 % 3 h1:Green46.IsCoveredByResidues 3 3y:ℕa:ℕ → ℕha:∀ m ∈ Finset.Icc 1 y, ∃ p ≤ 3, Nat.Prime p ∧ m ≡ a p [MOD p]hy:¬y ≤ 3key:∀ (m : ℕ), 1 ≤ m → m ≤ 4 → m % 2 = a 2 % 2 ∨ m % 3 = a 3 % 3⊢ False h1:Green46.IsCoveredByResidues 3 3h2:∀ (y : ℕ), Green46.IsCoveredByResidues 3 y → y ≤ 3⊢ Y 3 = 3 exact Or.inr hpm h1:Green46.IsCoveredByResidues 3 3y:ℕa:ℕ → ℕha:∀ m ∈ Finset.Icc 1 y, ∃ p ≤ 3, Nat.Prime p ∧ m ≡ a p [MOD p]hy:¬y ≤ 3key:∀ (m : ℕ), 1 ≤ m → m ≤ 4 → m % 2 = a 2 % 2 ∨ m % 3 = a 3 % 3⊢ False h1:Green46.IsCoveredByResidues 3 3h2:∀ (y : ℕ), Green46.IsCoveredByResidues 3 y → y ≤ 3⊢ Y 3 = 3 h1:Green46.IsCoveredByResidues 3 3y:ℕa:ℕ → ℕha:∀ m ∈ Finset.Icc 1 y, ∃ p ≤ 3, Nat.Prime p ∧ m ≡ a p [MOD p]hy:¬y ≤ 3key:∀ (m : ℕ), 1 ≤ m → m ≤ 4 → m % 2 = a 2 % 2 ∨ m % 3 = a 3 % 3⊢ False h1:Green46.IsCoveredByResidues 3 3h2:∀ (y : ℕ), Green46.IsCoveredByResidues 3 y → y ≤ 3⊢ Y 3 = 3
have k1 := key 1 le_rfl (by h1:Green46.IsCoveredByResidues 3 3y:ℕa:ℕ → ℕha:∀ m ∈ Finset.Icc 1 y, ∃ p ≤ 3, Nat.Prime p ∧ m ≡ a p [MOD p]hy:¬y ≤ 3key:∀ (m : ℕ), 1 ≤ m → m ≤ 4 → m % 2 = a 2 % 2 ∨ m % 3 = a 3 % 3⊢ 1 ≤ 4 h1:Green46.IsCoveredByResidues 3 3y:ℕa:ℕ → ℕha:∀ m ∈ Finset.Icc 1 y, ∃ p ≤ 3, Nat.Prime p ∧ m ≡ a p [MOD p]hy:¬y ≤ 3key:∀ (m : ℕ), 1 ≤ m → m ≤ 4 → m % 2 = a 2 % 2 ∨ m % 3 = a 3 % 3k1:1 % 2 = a 2 % 2 ∨ 1 % 3 = a 3 % 3⊢ False h1:Green46.IsCoveredByResidues 3 3h2:∀ (y : ℕ), Green46.IsCoveredByResidues 3 y → y ≤ 3⊢ Y 3 = 3 norm_num All goals completed! 🐙 h1:Green46.IsCoveredByResidues 3 3y:ℕa:ℕ → ℕha:∀ m ∈ Finset.Icc 1 y, ∃ p ≤ 3, Nat.Prime p ∧ m ≡ a p [MOD p]hy:¬y ≤ 3key:∀ (m : ℕ), 1 ≤ m → m ≤ 4 → m % 2 = a 2 % 2 ∨ m % 3 = a 3 % 3k1:1 % 2 = a 2 % 2 ∨ 1 % 3 = a 3 % 3⊢ False h1:Green46.IsCoveredByResidues 3 3h2:∀ (y : ℕ), Green46.IsCoveredByResidues 3 y → y ≤ 3⊢ Y 3 = 3) h1:Green46.IsCoveredByResidues 3 3y:ℕa:ℕ → ℕha:∀ m ∈ Finset.Icc 1 y, ∃ p ≤ 3, Nat.Prime p ∧ m ≡ a p [MOD p]hy:¬y ≤ 3key:∀ (m : ℕ), 1 ≤ m → m ≤ 4 → m % 2 = a 2 % 2 ∨ m % 3 = a 3 % 3k1:1 % 2 = a 2 % 2 ∨ 1 % 3 = a 3 % 3⊢ False h1:Green46.IsCoveredByResidues 3 3h2:∀ (y : ℕ), Green46.IsCoveredByResidues 3 y → y ≤ 3⊢ Y 3 = 3
have k2 := key 2 (by h1:Green46.IsCoveredByResidues 3 3y:ℕa:ℕ → ℕha:∀ m ∈ Finset.Icc 1 y, ∃ p ≤ 3, Nat.Prime p ∧ m ≡ a p [MOD p]hy:¬y ≤ 3key:∀ (m : ℕ), 1 ≤ m → m ≤ 4 → m % 2 = a 2 % 2 ∨ m % 3 = a 3 % 3k1:1 % 2 = a 2 % 2 ∨ 1 % 3 = a 3 % 3⊢ 1 ≤ 2 h1:Green46.IsCoveredByResidues 3 3y:ℕa:ℕ → ℕha:∀ m ∈ Finset.Icc 1 y, ∃ p ≤ 3, Nat.Prime p ∧ m ≡ a p [MOD p]hy:¬y ≤ 3key:∀ (m : ℕ), 1 ≤ m → m ≤ 4 → m % 2 = a 2 % 2 ∨ m % 3 = a 3 % 3k1:1 % 2 = a 2 % 2 ∨ 1 % 3 = a 3 % 3k2:2 % 2 = a 2 % 2 ∨ 2 % 3 = a 3 % 3⊢ False h1:Green46.IsCoveredByResidues 3 3h2:∀ (y : ℕ), Green46.IsCoveredByResidues 3 y → y ≤ 3⊢ Y 3 = 3 norm_num All goals completed! 🐙 h1:Green46.IsCoveredByResidues 3 3y:ℕa:ℕ → ℕha:∀ m ∈ Finset.Icc 1 y, ∃ p ≤ 3, Nat.Prime p ∧ m ≡ a p [MOD p]hy:¬y ≤ 3key:∀ (m : ℕ), 1 ≤ m → m ≤ 4 → m % 2 = a 2 % 2 ∨ m % 3 = a 3 % 3k1:1 % 2 = a 2 % 2 ∨ 1 % 3 = a 3 % 3k2:2 % 2 = a 2 % 2 ∨ 2 % 3 = a 3 % 3⊢ False h1:Green46.IsCoveredByResidues 3 3h2:∀ (y : ℕ), Green46.IsCoveredByResidues 3 y → y ≤ 3⊢ Y 3 = 3) (by h1:Green46.IsCoveredByResidues 3 3y:ℕa:ℕ → ℕha:∀ m ∈ Finset.Icc 1 y, ∃ p ≤ 3, Nat.Prime p ∧ m ≡ a p [MOD p]hy:¬y ≤ 3key:∀ (m : ℕ), 1 ≤ m → m ≤ 4 → m % 2 = a 2 % 2 ∨ m % 3 = a 3 % 3k1:1 % 2 = a 2 % 2 ∨ 1 % 3 = a 3 % 3⊢ 2 ≤ 4 h1:Green46.IsCoveredByResidues 3 3y:ℕa:ℕ → ℕha:∀ m ∈ Finset.Icc 1 y, ∃ p ≤ 3, Nat.Prime p ∧ m ≡ a p [MOD p]hy:¬y ≤ 3key:∀ (m : ℕ), 1 ≤ m → m ≤ 4 → m % 2 = a 2 % 2 ∨ m % 3 = a 3 % 3k1:1 % 2 = a 2 % 2 ∨ 1 % 3 = a 3 % 3k2:2 % 2 = a 2 % 2 ∨ 2 % 3 = a 3 % 3⊢ False h1:Green46.IsCoveredByResidues 3 3h2:∀ (y : ℕ), Green46.IsCoveredByResidues 3 y → y ≤ 3⊢ Y 3 = 3 norm_num All goals completed! 🐙 h1:Green46.IsCoveredByResidues 3 3y:ℕa:ℕ → ℕha:∀ m ∈ Finset.Icc 1 y, ∃ p ≤ 3, Nat.Prime p ∧ m ≡ a p [MOD p]hy:¬y ≤ 3key:∀ (m : ℕ), 1 ≤ m → m ≤ 4 → m % 2 = a 2 % 2 ∨ m % 3 = a 3 % 3k1:1 % 2 = a 2 % 2 ∨ 1 % 3 = a 3 % 3k2:2 % 2 = a 2 % 2 ∨ 2 % 3 = a 3 % 3⊢ False h1:Green46.IsCoveredByResidues 3 3h2:∀ (y : ℕ), Green46.IsCoveredByResidues 3 y → y ≤ 3⊢ Y 3 = 3) h1:Green46.IsCoveredByResidues 3 3y:ℕa:ℕ → ℕha:∀ m ∈ Finset.Icc 1 y, ∃ p ≤ 3, Nat.Prime p ∧ m ≡ a p [MOD p]hy:¬y ≤ 3key:∀ (m : ℕ), 1 ≤ m → m ≤ 4 → m % 2 = a 2 % 2 ∨ m % 3 = a 3 % 3k1:1 % 2 = a 2 % 2 ∨ 1 % 3 = a 3 % 3k2:2 % 2 = a 2 % 2 ∨ 2 % 3 = a 3 % 3⊢ False h1:Green46.IsCoveredByResidues 3 3h2:∀ (y : ℕ), Green46.IsCoveredByResidues 3 y → y ≤ 3⊢ Y 3 = 3
have k3 := key 3 (by h1:Green46.IsCoveredByResidues 3 3y:ℕa:ℕ → ℕha:∀ m ∈ Finset.Icc 1 y, ∃ p ≤ 3, Nat.Prime p ∧ m ≡ a p [MOD p]hy:¬y ≤ 3key:∀ (m : ℕ), 1 ≤ m → m ≤ 4 → m % 2 = a 2 % 2 ∨ m % 3 = a 3 % 3k1:1 % 2 = a 2 % 2 ∨ 1 % 3 = a 3 % 3k2:2 % 2 = a 2 % 2 ∨ 2 % 3 = a 3 % 3⊢ 1 ≤ 3 h1:Green46.IsCoveredByResidues 3 3y:ℕa:ℕ → ℕha:∀ m ∈ Finset.Icc 1 y, ∃ p ≤ 3, Nat.Prime p ∧ m ≡ a p [MOD p]hy:¬y ≤ 3key:∀ (m : ℕ), 1 ≤ m → m ≤ 4 → m % 2 = a 2 % 2 ∨ m % 3 = a 3 % 3k1:1 % 2 = a 2 % 2 ∨ 1 % 3 = a 3 % 3k2:2 % 2 = a 2 % 2 ∨ 2 % 3 = a 3 % 3k3:3 % 2 = a 2 % 2 ∨ 3 % 3 = a 3 % 3⊢ False h1:Green46.IsCoveredByResidues 3 3h2:∀ (y : ℕ), Green46.IsCoveredByResidues 3 y → y ≤ 3⊢ Y 3 = 3 norm_num All goals completed! 🐙 h1:Green46.IsCoveredByResidues 3 3y:ℕa:ℕ → ℕha:∀ m ∈ Finset.Icc 1 y, ∃ p ≤ 3, Nat.Prime p ∧ m ≡ a p [MOD p]hy:¬y ≤ 3key:∀ (m : ℕ), 1 ≤ m → m ≤ 4 → m % 2 = a 2 % 2 ∨ m % 3 = a 3 % 3k1:1 % 2 = a 2 % 2 ∨ 1 % 3 = a 3 % 3k2:2 % 2 = a 2 % 2 ∨ 2 % 3 = a 3 % 3k3:3 % 2 = a 2 % 2 ∨ 3 % 3 = a 3 % 3⊢ False h1:Green46.IsCoveredByResidues 3 3h2:∀ (y : ℕ), Green46.IsCoveredByResidues 3 y → y ≤ 3⊢ Y 3 = 3) (by h1:Green46.IsCoveredByResidues 3 3y:ℕa:ℕ → ℕha:∀ m ∈ Finset.Icc 1 y, ∃ p ≤ 3, Nat.Prime p ∧ m ≡ a p [MOD p]hy:¬y ≤ 3key:∀ (m : ℕ), 1 ≤ m → m ≤ 4 → m % 2 = a 2 % 2 ∨ m % 3 = a 3 % 3k1:1 % 2 = a 2 % 2 ∨ 1 % 3 = a 3 % 3k2:2 % 2 = a 2 % 2 ∨ 2 % 3 = a 3 % 3⊢ 3 ≤ 4 h1:Green46.IsCoveredByResidues 3 3y:ℕa:ℕ → ℕha:∀ m ∈ Finset.Icc 1 y, ∃ p ≤ 3, Nat.Prime p ∧ m ≡ a p [MOD p]hy:¬y ≤ 3key:∀ (m : ℕ), 1 ≤ m → m ≤ 4 → m % 2 = a 2 % 2 ∨ m % 3 = a 3 % 3k1:1 % 2 = a 2 % 2 ∨ 1 % 3 = a 3 % 3k2:2 % 2 = a 2 % 2 ∨ 2 % 3 = a 3 % 3k3:3 % 2 = a 2 % 2 ∨ 3 % 3 = a 3 % 3⊢ False h1:Green46.IsCoveredByResidues 3 3h2:∀ (y : ℕ), Green46.IsCoveredByResidues 3 y → y ≤ 3⊢ Y 3 = 3 norm_num All goals completed! 🐙 h1:Green46.IsCoveredByResidues 3 3y:ℕa:ℕ → ℕha:∀ m ∈ Finset.Icc 1 y, ∃ p ≤ 3, Nat.Prime p ∧ m ≡ a p [MOD p]hy:¬y ≤ 3key:∀ (m : ℕ), 1 ≤ m → m ≤ 4 → m % 2 = a 2 % 2 ∨ m % 3 = a 3 % 3k1:1 % 2 = a 2 % 2 ∨ 1 % 3 = a 3 % 3k2:2 % 2 = a 2 % 2 ∨ 2 % 3 = a 3 % 3k3:3 % 2 = a 2 % 2 ∨ 3 % 3 = a 3 % 3⊢ False h1:Green46.IsCoveredByResidues 3 3h2:∀ (y : ℕ), Green46.IsCoveredByResidues 3 y → y ≤ 3⊢ Y 3 = 3) h1:Green46.IsCoveredByResidues 3 3y:ℕa:ℕ → ℕha:∀ m ∈ Finset.Icc 1 y, ∃ p ≤ 3, Nat.Prime p ∧ m ≡ a p [MOD p]hy:¬y ≤ 3key:∀ (m : ℕ), 1 ≤ m → m ≤ 4 → m % 2 = a 2 % 2 ∨ m % 3 = a 3 % 3k1:1 % 2 = a 2 % 2 ∨ 1 % 3 = a 3 % 3k2:2 % 2 = a 2 % 2 ∨ 2 % 3 = a 3 % 3k3:3 % 2 = a 2 % 2 ∨ 3 % 3 = a 3 % 3⊢ False h1:Green46.IsCoveredByResidues 3 3h2:∀ (y : ℕ), Green46.IsCoveredByResidues 3 y → y ≤ 3⊢ Y 3 = 3
have k4 := key 4 (by h1:Green46.IsCoveredByResidues 3 3y:ℕa:ℕ → ℕha:∀ m ∈ Finset.Icc 1 y, ∃ p ≤ 3, Nat.Prime p ∧ m ≡ a p [MOD p]hy:¬y ≤ 3key:∀ (m : ℕ), 1 ≤ m → m ≤ 4 → m % 2 = a 2 % 2 ∨ m % 3 = a 3 % 3k1:1 % 2 = a 2 % 2 ∨ 1 % 3 = a 3 % 3k2:2 % 2 = a 2 % 2 ∨ 2 % 3 = a 3 % 3k3:3 % 2 = a 2 % 2 ∨ 3 % 3 = a 3 % 3⊢ 1 ≤ 4 h1:Green46.IsCoveredByResidues 3 3y:ℕa:ℕ → ℕha:∀ m ∈ Finset.Icc 1 y, ∃ p ≤ 3, Nat.Prime p ∧ m ≡ a p [MOD p]hy:¬y ≤ 3key:∀ (m : ℕ), 1 ≤ m → m ≤ 4 → m % 2 = a 2 % 2 ∨ m % 3 = a 3 % 3k1:1 % 2 = a 2 % 2 ∨ 1 % 3 = a 3 % 3k2:2 % 2 = a 2 % 2 ∨ 2 % 3 = a 3 % 3k3:3 % 2 = a 2 % 2 ∨ 3 % 3 = a 3 % 3k4:4 % 2 = a 2 % 2 ∨ 4 % 3 = a 3 % 3⊢ False h1:Green46.IsCoveredByResidues 3 3h2:∀ (y : ℕ), Green46.IsCoveredByResidues 3 y → y ≤ 3⊢ Y 3 = 3 norm_num All goals completed! 🐙 h1:Green46.IsCoveredByResidues 3 3y:ℕa:ℕ → ℕha:∀ m ∈ Finset.Icc 1 y, ∃ p ≤ 3, Nat.Prime p ∧ m ≡ a p [MOD p]hy:¬y ≤ 3key:∀ (m : ℕ), 1 ≤ m → m ≤ 4 → m % 2 = a 2 % 2 ∨ m % 3 = a 3 % 3k1:1 % 2 = a 2 % 2 ∨ 1 % 3 = a 3 % 3k2:2 % 2 = a 2 % 2 ∨ 2 % 3 = a 3 % 3k3:3 % 2 = a 2 % 2 ∨ 3 % 3 = a 3 % 3k4:4 % 2 = a 2 % 2 ∨ 4 % 3 = a 3 % 3⊢ False h1:Green46.IsCoveredByResidues 3 3h2:∀ (y : ℕ), Green46.IsCoveredByResidues 3 y → y ≤ 3⊢ Y 3 = 3) le_rfl h1:Green46.IsCoveredByResidues 3 3y:ℕa:ℕ → ℕha:∀ m ∈ Finset.Icc 1 y, ∃ p ≤ 3, Nat.Prime p ∧ m ≡ a p [MOD p]hy:¬y ≤ 3key:∀ (m : ℕ), 1 ≤ m → m ≤ 4 → m % 2 = a 2 % 2 ∨ m % 3 = a 3 % 3k1:1 % 2 = a 2 % 2 ∨ 1 % 3 = a 3 % 3k2:2 % 2 = a 2 % 2 ∨ 2 % 3 = a 3 % 3k3:3 % 2 = a 2 % 2 ∨ 3 % 3 = a 3 % 3k4:4 % 2 = a 2 % 2 ∨ 4 % 3 = a 3 % 3⊢ False h1:Green46.IsCoveredByResidues 3 3h2:∀ (y : ℕ), Green46.IsCoveredByResidues 3 y → y ≤ 3⊢ Y 3 = 3
omega h1:Green46.IsCoveredByResidues 3 3h2:∀ (y : ℕ), Green46.IsCoveredByResidues 3 y → y ≤ 3⊢ Y 3 = 3 h1:Green46.IsCoveredByResidues 3 3h2:∀ (y : ℕ), Green46.IsCoveredByResidues 3 y → y ≤ 3⊢ Y 3 = 3
rw [Y h1:Green46.IsCoveredByResidues 3 3h2:∀ (y : ℕ), Green46.IsCoveredByResidues 3 y → y ≤ 3⊢ sSup {y | Green46.IsCoveredByResidues 3 y} = 3 h1:Green46.IsCoveredByResidues 3 3h2:∀ (y : ℕ), Green46.IsCoveredByResidues 3 y → y ≤ 3⊢ sSup {y | Green46.IsCoveredByResidues 3 y} = 3] h1:Green46.IsCoveredByResidues 3 3h2:∀ (y : ℕ), Green46.IsCoveredByResidues 3 y → y ≤ 3⊢ sSup {y | Green46.IsCoveredByResidues 3 y} = 3
exact IsGreatest.csSup_eq ⟨h1, h2⟩ All goals completed! 🐙def erdos_687.parts.i.answer : ℕ → ℝ := sorryLet $Y(x)$ be the maximal $y$ such that there exists a choice of congruence classes $a_p$ for all primes $p\leq x$ such that every integer in $[1,y]$ is congruent to at least one of the $a_p\pmod{p}$. Give good estimates for $Y(x)$.
We formalise this as determining $Y(x)$ up to constant factors.
@[category research open, question value, AMS 11]
theorem erdos_687.parts.i :
(fun x : ℕ ↦ (Y x : ℝ)) =Θ[atTop] erdos_687.parts.i.answer := by ⊢ (fun x ↦ ↑(Y x)) =Θ[atTop] i.answer
sorry All goals completed! 🐙In particular, can one prove that $Y(x)=o(x^2)$?
Yes: an internal OpenAI model proved $h(k) \ll k^2$ for Jacobsthal's function $h$ [OAI26a]
(see Erdos970.erdos_970). Since $Y(x) + 1$ is Jacobsthal's function of $\prod_{p \leq x} p$,
which has $\pi(x) \ll x/\log x$ prime factors, this gives $Y(x) \ll x^2/(\log x)^2$.
The linked Lean proof is by 30k30, from the bound of [OAI26a].
@[category research solved, question, AMS 11, formal_proof using lean4 at
"https://github.com/30k30/scholia/blob/b072c89c3edac06521868e32cc15b2bc91bd8533/erdos-687/glue/JacobsthalTo687.lean#L325"]
theorem erdos_687.parts.ii :
(fun x : ℕ ↦ (Y x : ℝ)) =o[atTop] (fun x : ℕ ↦ (x : ℝ) ^ 2) := by ⊢ (fun x ↦ ↑(Y x)) =o[atTop] fun x ↦ ↑x ^ 2
sorry All goals completed! 🐙Or, even stronger, can one prove that $Y(x)\ll x^{1+o(1)}$?
We read $Y(x)\ll x^{1+o(1)}$ as $Y(x) = O(x^{1+\varepsilon})$ for every fixed $\varepsilon > 0$.
@[category research open, question, AMS 11]
theorem erdos_687.parts.iii :
∀ ε > (0 : ℝ), (fun x : ℕ ↦ (Y x : ℝ)) =O[atTop] (fun x : ℕ ↦ (x : ℝ) ^ (1 + ε)) := by ⊢ ∀ ε > 0, (fun x ↦ ↑(Y x)) =O[atTop] fun x ↦ ↑x ^ (1 + ε)
sorry All goals completed! 🐙Iwaniec's upper bound for Jacobsthal's function [Iw78] gives $Y(x) \ll x^2$.
@[category research solved, AMS 11]
theorem erdos_687.variants.iwaniec :
(fun x : ℕ ↦ (Y x : ℝ)) =O[atTop] (fun x : ℕ ↦ (x : ℝ) ^ 2) := by ⊢ (fun x ↦ ↑(Y x)) =O[atTop] fun x ↦ ↑x ^ 2
sorry All goals completed! 🐙Ford, Green, Konyagin, Maynard and Tao [FGKMT18] proved $$Y(x) \gg \frac{x \log x \log\log\log x}{\log\log x}.$$
@[category research solved, AMS 11]
theorem erdos_687.variants.fgkmt :
(fun x : ℕ ↦ (x : ℝ) * Real.log x * Real.log (Real.log (Real.log x)) /
Real.log (Real.log x)) =O[atTop] (fun x : ℕ ↦ (Y x : ℝ)) := by ⊢ (fun x ↦ ↑x * Real.log ↑x * Real.log (Real.log (Real.log ↑x)) / Real.log (Real.log ↑x)) =O[atTop] fun x ↦ ↑(Y x)
sorry All goals completed! 🐙Maier and Pomerance [MaPo90] conjectured that $Y(x) \ll x(\log x)^{2+o(1)}$ (in this form it is stated in [FGKMT18]).
We read this as $Y(x) = O(x(\log x)^{2+\varepsilon})$ for every fixed $\varepsilon > 0$.
@[category research open, AMS 11]
theorem erdos_687.variants.maier_pomerance :
∀ ε > (0 : ℝ), (fun x : ℕ ↦ (Y x : ℝ)) =O[atTop]
(fun x : ℕ ↦ (x : ℝ) * Real.log x ^ (2 + ε)) := by ⊢ ∀ ε > 0, (fun x ↦ ↑(Y x)) =O[atTop] fun x ↦ ↑x * Real.log ↑x ^ (2 + ε)
sorry All goals completed! 🐙end Erdos687