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 :-)

  • $\begingroup$ It seems to me in the limit you do not want A but the set of its multiples; or a different letter altogether if you want to define natural denity in general. $\endgroup$
    – user9072
    Feb 28, 2013 at 15:00
  • $\begingroup$ @quid You are right, I fix it, thanks. $\endgroup$
    – user21706
    Feb 28, 2013 at 16:12

2 Answers 2


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.


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$.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.