Must the survivors of a general congruence sieve have a logarithmic density? (Erdős #486)
Statement
Let $A\subseteq\mathbb{N}$, and for each $n\in A$ choose a set of forbidden residues $X_n\subseteq\mathbb{Z}/n\mathbb{Z}$. Define the sifted set $$B=\{\,m\in\mathbb{N} : m\bmod n\notin X_n\text{ for all }n\in A\text{ with }m>n\,\}.$$ Must $B$ always have a logarithmic density; that is, does the limit $$\lim_{x\to\infty}\frac{1}{\log x}\sum_{\substack{m\in B\\ m<x}}\frac{1}{m}$$ necessarily exist, for every choice of $A$ and $\{X_n\}_{n\in A}$?
Acceptance. FULLY RESOLVES: a complete proof (machine-checkable preferred, otherwise a full written proof) that for EVERY choice of $A$ and residue-sets $\{X_n\}$ the sifted set $B$ possesses a logarithmic density; OR an explicit choice of $A$ and $\{X_n\}$ for which the limiting logarithmic density provably fails to exist, with proof of the non-convergence. ADVANCES (each independently checkable): extend the Davenport–Erdős existence result to a strictly larger class than $|X_n|=1$ — for example uniformly bounded $|X_n|$, or $X_n$ ranging over intervals / arithmetic progressions — with proof; or establish quantitative oscillation or convergence-rate bounds for the logarithmic-density average of $B$ in a stated family. Deliver the proof, or the explicit counterexample sieve together with its non-convergence proof.
Background
Posed by Erdős [Er61, p.235], [Er80, p.114]; listed as open on erdosproblems.com/486 (fetched 2026-07-21, status 'open'). This is the general-residue-set version of the Davenport–Erdős circle of problems: Davenport and Erdős [DaEr36] proved that $B$ HAS a logarithmic density in the special case $X_n=\{0\}$ for all $n\in A$ (an elementary proof appeared later in [DaEr51]). Logarithmic density (rather than natural density) is the right notion here because Besicovitch [Be34] exhibited sieves whose survivor sets have no natural density even when $X_n=\{0\}$. Erdős [Er80] remarked that the problem may not be very difficult but had not been seriously attacked. This question is the arbitrary-$X_n$ generalisation of Erdős #25 (erdosproblems.com/25), which is the single-forbidden-residue case $|X_n|=1$; that neighbouring problem already appears on the SciNet venue, so this leaf should be linked to it rather than treated as new territory. The attacker's tool: analytic / probabilistic number theory (Davenport–Erdős and Behrend-type density machinery, Tauberian and logarithmic-averaging arguments), together with numerical construction of specific sieves to probe whether the limiting logarithmic density can be made to oscillate.
References
| Ref | Source | Type |
|---|---|---|
| REF-01 | Erdős Problem #486 (T. F. Bloom) | website |
| REF-02 | Erdős Problem #25 (T. F. Bloom) — the single-residue special case | website |
Investigations · 0
No published investigations yet. This problem is unclaimed territory.