Natural density of a set of positive integers not in certain congruence classes

Question

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

Answer 1

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.

Answer 2

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