I am investigating a sieve theory problem concerning the non-emptiness of sets defined by forbidding two residues modulo each prime in a specific set. The setup is as follows:
- Let $s$ be a positive integer.
- Define $R_r$ as the set of primes $q$ satisfying $q \equiv \pm 1 \mod 6$ and $5 \le q \le 6s \pm 1$.
- Define $R_0 = \{1, 2, \ldots, 3s^2 \pm s\}$.
- For each prime $q \in R_r$, choose two distinct residues $e_1(q), e_2(q) \mod q$.
- The sieved set is:
$$ R_0(e_1, e_2) = \left\{ a \in R_0 : a \not\equiv e_1(q) \text{ or } e_2(q) \pmod{q} \ \forall q \in R_r \right\}. $$ Theorem: There exists a minimal $s_0$ such that for all $s \ge s_0$ and any choice of residues $e_1(q), e_2(q)$, the set $R_0(e_1, e_2)$ is non-empty.
Known Results:
- For $s = 7$ (interval length $154$, primes $\{5,7,11,13,17,19,23,29,31,37,41,43\}$), a greedy algorithm (selecting residues that maximize removals) leaves $19$ survivors. Thus, non-emptiness holds.
- For $s = 6$ (interval length $114$, primes $\{5,7,11,13,17,19,23,29,31,37\}$), the same greedy algorithm yields 0 survivors, suggesting non-emptiness fails for some residue choices.
Computational Challenges:
- Exhaustive search for $s = 6$ is infeasible ($\approx 3^{10}$ residue choices).
- The greedy algorithm minimizes survivors locally, but we seek confirmation that it achieves the global minimum (i.e., whether $0$ is attainable).
Theoretical Lower Bound:
A sequential bound $\mathtt{removals} ≤ ⌈2R/q⌉$ gives $17$ survivors for $s = 6$, but this conflicts with the greedy result ($0$). The discrepancy arises because:
$$
\left\lceil \frac{2R}{q} \right\rceil \leq \min\left(2\left\lceil \frac{R}{q}\right\rceil, R\right)
$$
ensures the bound is a safe overestimate of survivors (not a guarantee of non-emptiness).
Questions:
Minimal $s_0$:
- Is $s = 7$ indeed the minimal $s_0$?
- For $s = 6$, does there exist any residue choice that removes all integers in $[1, 114]$? If yes, how can such residues be constructed?
Sieve-Theoretic Tools:
- Are there results (e.g., Brun sieve, Selberg sieve) that provide strict positive lower bounds for $|R_0(e_1, e_2)|$ in this setting?
- Can existing sieves handle the dependence on residue choices?
Algorithmic Verification:
- Beyond the greedy heuristic, is there a computationally feasible method to verify the worst-case for $s = 6$?
