← All problems

Erdős Problem #486 — Logarithmic density of survivor sets

65 years old · traced to

Let N={1,2,…}\mathbb N=\{1,2,\ldots\}, let A⊆NA\subseteq\mathbb N, and, for each n∈An\in A, let XnX_n be an arbitrary subset of the residue ring Z/nZ\mathbb Z/n\mathbb Z. Define the survivor set by

B={m∈N:m mod n∉Xn for every n∈A with n<m}.B=\{m\in\mathbb N: m\bmod n\notin X_n\text{ for every }n\in A\text{ with }n<m\}.

Thus a congruence condition modulo nn excludes integers in the selected residue classes only after the strict activation threshold m>nm>n. Must every such choice of AA and (Xn)n∈A(X_n)_{n\in A} give BB a logarithmic density; that is, does the limit

lim⁡x→∞1log⁡x∑m∈B\m<x1m\lim_{x\to\infty}\frac{1}{\log x}\sum_{\substack{m\in B\m<x}}\frac1m

exist? Erdős Problems #486

Background

This question belongs to the theory of congruence sieves and primitive sets. Its classical divisibility model takes Xn={0}X_n=\{0\}, so integers are removed when divisible by an earlier selected modulus. Davenport and Erdős established a logarithmic-density theorem for the corresponding set of multiples, and their 1951 paper gave an elementary proof. Erdős recorded the broader question in his work on primitive sets. Erdős Problems #486 Davenport and Erdős (1951), On sequences of positive integers

Logarithmic density is the natural target here partly because ordinary density can fail even in the divisibility model: Besicovitch produced examples without natural density. The question also extends the one-residue-per-modulus case, allowing each modulus to exclude an arbitrary collection of residue classes. Related truncated-sieve work studies one selected residue class at each of a strictly increasing sequence of moduli, but uses its own activation convention and does not by itself settle this more general question. Erdős Problems #486 Davenport and Erdős (1951), On sequences of positive integers Chojecki (2026), Truncated Congruence Sieves and Erdős Problem 25

References

Progress summary

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.