Natural density of a set of positive integers not in certain congruence classes Hi everybody.
In "M. B. Nathanson - Elementary Methods in Number Theory" is shown (Theorem 7.14) that if $A$ is a set of positive integers such that $\sum_{a \in A} 1 / a$ converges then the set of multiples of $A$ has a natural density (a set of positive integers $S$ has a natural density if exists $\lim_{x \to \infty} |S \cap [1,x]| / x$).
Equivalently, the set of positive integers $n$ such that $a \nmid n$ for all $a \in A$ has a natural density. 
I'm looking for a generalization of this kind:
Let $M$ be a set of positive integers and $N_m \subseteq \mathbb{Z} / m \mathbb{Z}$ for all $m \in M$. If [some conditions on $|N_m| / m$, maybe that $\sum_{m \in M} |N_m| / m$ converges] then the set of positive integers $n$ such that $n \not \equiv r \mod m$ for all $m \in M$ and $r \in N_m$ has a natural density.
Thank you for any reference :-)
 A: Here is an amplification of @Greg Martin's answer. 
Let $S$ be any set whose upper density and lower density differ. Let the upper and lower densities be $\alpha$ and $\beta$ respectively. Write $S(N)$ for $|S\cap[1,N]|$. Let $a_1 < a_2 < \ldots $ be the increasing enumeration of $S^c$. Let $\delta<\alpha-\beta$.
Let $m_1 < m_2 < \ldots$ be a sequence satisfying the following:


*

* $m_i>a_i$;

* $\sum_{i=1}^\infty 1/m_i \lt \delta $;

* $S(m_i)/m_i\to\alpha$.


Set $N_{m_i}=\{a_i\}$. Let $\tilde S$ be the set of integers $n$ such that $n\bmod m_i\not\in N_{m_i}$ for each $i$. Clearly $\tilde S\subset S$, so that the lower density of $\tilde S$ is at most $\beta$. On the other hand 
$$
(S\setminus\tilde S) \cap [1,m_j] \subset \left(\bigcup_{i < j} (a_i+m_i\mathbb N)\cap [1,m_j]\right),
$$
where $\mathbb N$ is the set of strictly positive integers.
Hence we see that $(S\setminus\tilde S) \cap [1,m_j]$ has at most $m_j(1/m_1+\ldots+1/m_{j-1}) < \delta 
m_j$ elements. So $\limsup_{j\to\infty}\tilde S(m_j)/m_j \gt \alpha-\delta > \beta $, and $\tilde S$ does not have a density.
A: Such a generalization would probably be false. Choose any infinite set $M$ of positive integers, however sparse you want, so that $\sum_{m\in M} 1/m$ definitely converges. Now choose the first $N_m$ to be $\{1\}$, the second $N_m$ to be $\{2\}$, and so on. Then every single positive integer is congruent to one of the targeted residue classes.
For example, take $m_k = 3^{4^k}$ and set $M = \{ m_1,m_2,\dots \}$ and $N_{m_k} = \{k\}$; then every $k\equiv k\pmod{m_k}$, and so the set of "surviving" positive integers is empty.
I just realized that this doesn't exactly answer your question, since the empty set does have a natural density! But this construction does show, I think, that the spirit of your conjecture isn't right - you won't just get a happy sieved set in general, depending on the specific choice of the $N_m$.
