2
$\begingroup$

Let $\mathcal{A}$ be a nonempty set of pairwise coprime positive integers, and for each $a \in \mathcal{A}$ let $\Omega_a \subsetneq \{0, \ldots, a - 1\}$ be a set of residues modulo $a$. Furthermore, put $$\mathcal{S} := \{n \in \mathbf{N} : (n \bmod a) \notin \Omega_a, \;\forall a \in \mathcal{A}\}.$$ An easy application of the Chinese Remainder Theorem shows that $$\underline{\mathbf{d}}(\mathcal{S}) \geq \prod_{a \in \mathcal{A}} \left(1 - \frac{\#\Omega_a}{a}\right),$$ where $\underline{\mathbf{d}}$ denotes the lower asymptotic density. In particular, if $$\sum_{a \in \mathcal{A}} \frac{\#\Omega_a}{a} < +\infty$$ then the infinite product converges and $\mathcal{S}$ has positive asymptotic density. (Actually, the asymptotic density of $\mathcal{S}$ exists and it is equal to the infinite product, but this is irrelevant for my question.)

My question is: What if we drop the hypothesis that the elements of $\mathcal{A}$ are pairwise coprime? Are there results that guarantee that $\mathcal{S}$ has a positive lower asymptotic density? Have these kind of sieves been studied?

Of course, if the elements of $\mathcal{A}$ are not pairwise coprime then (without additional hypotheses) $\underline{\mathbf{d}}(\mathcal{S})$ can be $0$, just consider: $\mathcal{A} = \{2, 4\}$, $\Omega_2 = \{0\}$, $\Omega_4 = \{1, 3\}$.

Thank you for any suggestion.

$\endgroup$
2
$\begingroup$

This paper by I Ruzsa (On the small sieve. II. Sifting by composite numbers. J. Number Theory 14 (1982), no. 2, 260–268.) gives considerable limitations to the type of lower bound that you want: If $H(x,K)$ is the maximum number of integers $n \leq x$, not divisible by integers $a \in A$. Here the maximum is taken over sets of integers $A$, not containing $1$ and with $\sum_i \frac{1}{a_i} \leq K$. Then $H(x,K)$ can be quite small. Let $K>1$, then $H(x,K)$ is about $x^{e^{1-K}}$, more precisely: $\lim_{x \rightarrow \infty} \log H(x,K)/\log x=e^{1-K}$. Moreover, for $K=1$ one has: $\frac{c_1 x}{\log x} < H(x,1)< \frac{x}{(\log x)^{c_2}}$.

In other words, already the case of $\Omega_a=\{0\}$ makes problems. If you still want a lower density bound you need to avoid the case above...

$\endgroup$
  • $\begingroup$ The paper is interesting, but the maximum $H(x, k)$ is taken for fixed $x$, so I do not think it has some implication on my question. If I got it right the last upper bound means that for any $x$ there exists $A_x$ (depending on $x$) such that $1 \notin A_x$, $\sum_{a \in A_x} a^{-1} \leq 1$, and the number of positive integers $n \leq x$ which are not divisible by any $a \in A_x$ is less than $x / (\log x)^{c_2}$. However, I am looking for results which are uniform in $x$. $\endgroup$ – user40023 Feb 7 '17 at 17:55

Your Answer

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