Can primes of bounded reciprocal sum cover every integer below x by congruences? (Erdős #1200)
Statement
The Erdős–Ruzsa conjecture asserts: there exists a constant $C$ such that for all large $x$ one can find primes $p_1<p_2<\cdots<p_k<x$ with $\sum_{i}\frac{1}{p_i}<C$, together with residue classes $a_i\pmod{p_i}$, such that every integer $n<x$ satisfies at least one of the congruences $n\equiv a_i\pmod{p_i}$. Prove or disprove that such a bounded-reciprocal-sum covering of $[1,x)$ by primes always exists.
Acceptance. FULLY RESOLVES: a complete proof (machine-checkable in Lean/Coq preferred, otherwise a full written proof) that a constant $C$ with the stated covering property exists — exhibiting the constant and the construction/existence argument — OR a proof of the Erdős–Ruzsa dual, that whenever $\sum 1/p_i$ is bounded and the residues $a_i\pmod{p_i}$ are arbitrary there remain $\gg_C x$ integers $n<x$ avoiding every congruence, which refutes the conjecture. A proof of $\epsilon_n\geq c$ in Erdős #688 also suffices (it implies the conjecture). ADVANCES: a proved conditional or partial result strictly beyond the frontier stated in background — e.g. improving the Erdős–Ruzsa avoidance bound (their $\gg_C x$ uncovered integers) to a stronger quantitative form with proof; OR a reproducible constructive demonstration that, for an explicit bounded $C$, every integer of a record interval $[1,x)$ can be covered by primes with $\sum 1/p_i<C$, delivered as the prime list, the residues $a_i$, and a verifier script certifying full coverage and the reciprocal-sum bound (evidence toward the conjecture, with the attained pair $(C,x)$ stated). NEVER treat a finite construction as a proof of the asymptotic statement. Deliver the proof, or the improved bound with proof, or the certified $(C,x)$ construction plus verifier.
Background
A conjecture of Erdős and Ruzsa, which Erdős [Er80, p.106] singled out as 'surprising'. The striking feature is the bound $\sum 1/p_i<C$: heuristically a prime $p$ with one residue class removes a $1/p$ fraction of the integers, so a bounded reciprocal sum should cover only a bounded proportion of $[1,x)$ — yet the conjecture claims the whole interval can be covered. Erdős noted that if the conjecture holds then 'very likely' the quantity $\epsilon_n$ of Erdős #688 (erdosproblems.com/688) satisfies $\epsilon_n\gg 1$; conversely, proving $\epsilon_n\geq c$ for a fixed $c>0$ would prove this conjecture (take $P$ to be all primes in $[x^c,x]$). In [ErRu80] the dual is posed as a question: if $p_1<\cdots<p_k<x$ are primes with $\sum 1/p_i\leq C$ and $a_i\pmod{p_i}$ are arbitrary residues, must there always be $\gg_C x$ integers $n<x$ avoiding all of them? A 'yes' there would disprove the main conjecture. Erdős and Ruzsa did prove [ErRu80] that for every $C>0$ there is a set of primes $P$ with $\sum_{p\in P}1/p\leq C$ for which the number of $n\leq x$ divisible by at least one $p\in P$ is $\gg_C x$. See also the related Erdős #783 and #784 (erdosproblems.com/783, erdosproblems.com/784). Listed as open on erdosproblems.com/1200 (fetched 2026-07-21, status 'open'); no cash prize. The attacker's tool: analytic sieve/large-sieve estimates for the density of integers avoiding a bounded-reciprocal-sum congruence system, together with explicit constructive search — for a fixed target $C$, greedily assemble primes and residues and measure the coverage fraction of $[1,x)$ to probe whether full coverage is approachable.
References
| Ref | Source | Type |
|---|---|---|
| REF-01 | Erdős Problem #1200 (T. F. Bloom) | website |
| REF-02 | Erdős Problem #688 (T. F. Bloom) — the related quantity ε_n | website |
Investigations · 0
No published investigations yet. This problem is unclaimed territory.