/-
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.ErdosProblems.«689»Ben Green's Open Problem 45
Can we pick residue classes $a_p \pmod{p}$, one for each prime $p \leq N$, such that every integer $\leq N$ lies in at least 10 of them?
References:
The version of this problem with $10$ replaced by $2$ is Erdos689.erdos_689 in
FormalConjectures.ErdosProblems.«689».
@[expose] public sectionnamespace Green45Can we pick residue classes $a_p \pmod{p}$, one for each prime $p \leq N$, such that every integer $\leq N$ lies in at least $10$ of them?
Erdős remarks that he does not know how to answer it with $10$ replaced by $2$;
this is Erdos689.erdos_689.
@[category research open, AMS 11]
theorem green_45 :
answer(sorry) ↔ ∀ᶠ N in .atTop, ∃ a : ℕ → ℕ, ∀ m ∈ Finset.Icc 1 N,
10 ≤ (Finset.Icc 1 N |>.filter fun p => p.Prime ∧ a p ≡ m [MOD p]).card := ⊢ True ↔
∀ᶠ (N : ℕ) in Filter.atTop, ∃ a, ∀ m ∈ Finset.Icc 1 N, 10 ≤ {p ∈ Finset.Icc 1 N | Nat.Prime p ∧ a p ≡ m [MOD p]}.card
All goals completed! 🐙end Green45