Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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

share|improve this question
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. –  quid Feb 28 '13 at 15:00
@quid You are right, I fix it, thanks. –  user21706 Feb 28 '13 at 16:12
add comment

2 Answers

up vote 4 down vote accepted

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.

share|improve this answer
add comment

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

share|improve this answer
add comment

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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