Green's Open Problem 44

References:

• [Gr24] Ben Green's 100 Open Problems
• [Er80] Erdős, Paul. "A survey of problems in combinatorial number theory." Annals of Discrete Mathematics 6 (1980): 89-115.

theorem Green44.green_44 : sorry ↔ ∀ (N : ℕ) (p : Fin 1000 → ℕ) (A : (i : Fin 1000) → Finset (ZMod (p i))), have remaining := {x ∈ Finset.Icc 1 N | ∀ (i : Fin 1000), ↑x ∉ A i}; (∀ (i : Fin 1000), Nat.Prime (p i)) → StrictMono p → p 999 ^ 10 < N ^ 9 → (∀ (i : Fin 1000), (A i).card = p i / 2) → 10 * remaining.card ≤ N

Sieve $[N]$ by removing half the residue classes mod $p_i$, for primes $2 \leqslant p_1 < p_2 < \dots < p_{1000} < N^{9/10}$. Does the remaining set have size at most $\frac{1}{10} N$?

We interpret "half the residue classes" as $\lfloor p_i / 2 \rfloor$.

theorem Green44.green_44.variants.less_than_sqrt (N : ℕ) (p : Fin 1000 → ℕ) (A : (i : Fin 1000) → Finset (ZMod (p i))) : have remaining := {x ∈ Finset.Icc 1 N | ∀ (i : Fin 1000), ↑x ∉ A i}; (∀ (i : Fin 1000), Nat.Prime (p i)) → StrictMono p → p 999 ^ 2 < N → (∀ (i : Fin 1000), (A i).card = p i / 2) → 10 * remaining.card ≤ N

The answer is affirmative if the primes are all less than $N^{1/2}$, by the large sieve. [Gr24]