# Density of a set of integers

EDIT: this question of mine has received little attention, perhaps in part because it was stated in a too general and complicated way. So let me give it a second chance:

Fix an integer $r \geq 0$. Let $E_r(x)$ be the number of square free integers less than $x$ having exactly $r$ prime factors $p$ congruent to $2 \pmod{3}$ (and an arbitrary number of other prime factors). What is the order of magnitude of $E_r(x)$ when $x$ goes to $\infty$ ?

When $r=0$, one has $E_0(x) \asymp x/\log^{1/2}(x)$ (see below). Even when $r=1$, I don't know the answer, or a lower bound for $E_1(x)$ that is better than this one for $E_0(x)$. Thanks for any idea or reference pointing to a method that can be used to solve this question.

ORIGINAL POST FOLLOWS:

I begin by quoting a theorem found in Serre's paper "divisibilité de certaines functions arithmétiques", with a proof attributed to Raikov, Winter, Delange (theorème 2.4 - I have slightly changed and simplified the statement, as the $E$ here is the complement $E'$ of $E$ in Serre's paper.).

Let $E$ be a set of integers satisfying the following condition :

(MM) For $n,m$ relatively prime integers, $nm \in E$ if and only if $n \in E$ and $m \in E$,

Let $P$ be the set of primes that are in $E$. Assume that $P$ has analytic density $\alpha > 0$. Let $E(x)$ the number of elements of $E$ less than $x$. Then when $x$ goes to infinity, $$E(x) \sim c x /\log^\{1-\alpha}(x)$$ for some constant $c>0$.

Example: Let $P$ be a set of primes of density $\alpha>0$, $E$ the set of square-free integers whose prime factors are all in $P$. Then $E$ satisfies the hypothesis (MM). So does $F=$ the set of all integer who's prime factors are all in $P$. Both satisfies the conclusion of the theorem, though with a different constant $c$.

Now let $P,E$ be as above, and let $r \geq 0$ be an integer. Let $E_r$ be the set of integers that are products of an element of $E$ and exactly $r$ distinct prime not in $P$. My question is:

What is an order of magnitude of $E_r(x)$ ?

The case $r=0$ is the theorem above, and I suppose the answer for $r>0$ does only depend on $P$, not on $E$, as for $r=0$. But in case it is not true, or in case that helps, the case of interest for me is the case where $E$ is as in the example. So if I may reformulate my question in this special case: if $P$ is a set of prime of density $\alpha>0$, and $E$ is the set of square-free integers which are product of $r$ primes not in $P$ and arbitrary number of primes in $P$, what is the order of magnitude of $E_r(x)$?

A word on my motivation, which turns around the beautiful aforementioned paper of Serre. Consider for example the modular form $\Delta$, modulo $3$. if $E$ is the set of $n$ such that the $n$-th coefficient of that form is non-zero, that is such that $3 \nmid \tau(n)$, then $E$ satisfies (MM), $P$ is the set of primes congruent to $1$ modulo $3$, and $E(x) \sim cx log^{1/2}(x)$. This is in Serre, as $\Delta$ is an eigenform. Noe consider $\Delta^2$ modulo $3$ which is not an eigenform, and let $F$ the set of $n$-th coefficient of that form is non-zero. Then it is easy to see that $F$ contains $E_1$ (and I think, is not too much bigger than $E_1$).

-

Here's an attempt to say something about your nice question. It surely follows from Igor Rivin's nice sketch and the Math Overflow question he linked to. Fix $r$. The quantity $E_r(x)$ in the edited question satisfies

$$E_r(x)\gg \sum_{\substack{m \leq x \\ \omega(m)=r\\ \mu(m)^2=1\\p|m \Rightarrow p \equiv 2 \bmod 3}}\sum_{\substack{n \leq x/m\\ \mu(n)^2=1\\p|n \Rightarrow p\equiv 1 \bmod 3}}1.$$

The inner sum in the above, by what you wrote about $E_0(x)$, satisfies

$$\sum_{\substack{n \leq x/m\\ \mu(n)^2=1\\p|n \Rightarrow p\equiv 1 \bmod 3}}1 \gg \frac{x}{m(\log x)^{1/2}}.$$

By induction on $r$, say, and using $\sum_{\substack{p \leq x\\p \equiv 2 \bmod 3}}\frac{1}{p}\gg \log\log x$, one has

$$\sum_{\substack{m \leq x \\ \omega(m)=r\\ \mu(m)^2=1\\p|m \Rightarrow p \equiv 2 \bmod 3}}\frac{1}{m}\gg (\log\log x)^r.$$

So one has $$E_r(x) \gg \frac{x(\log\log x)^r}{(\log x)^{1/2}}$$ where the implied constant depends on $r$.

-
Thanks a lot : this is what I expected but was not able to prove. –  Joël Apr 22 '12 at 20:04
You're most welcome. For the general case, one seems to need estimates for $\sum_{\substack{p \leq x\\p \in \mathbb{P}\setminus P}}\frac{1}{p}$. Perhaps that involves some generalizations of Mertens' theorem? –  user22202 Apr 23 '12 at 0:16

I just wanted to add, we also have a similar upper bound which combined with unknown(google)'s answer shows that

$$E_{r}(x)\asymp\frac{x\left(\log\log x\right)^{r}}{\left(\log x\right)^{\frac{1}{2}}}.$$

The above is almost certainly an asymptotic, and we can likely derive the explicit constant, but that would require a lot of calculation.

Upper bound: Let $\mathcal{A}=\left\{ n\in\mathbb{N}:\ p|n\Rightarrow p\equiv2\ (3)\right\}$ and let $\mathcal{B}=\left\{ n\in\mathbb{N}:\ p|n\Rightarrow p\equiv1\ (3)\right\}.$ Then

$$E_{r}(x)=\sum_{\begin{array}{c} n\leq x\\ n\in\mathcal{A}\\ \mu^{2}(n)=1,\omega(n)=r \end{array}}\sum_{\begin{array}{c} m\leq\frac{x}{n}\\ m\in\mathcal{B}\\ \mu(m)^{2}=1 \end{array}}1.$$

We then have the upper bound

$$E_{r}(x)\ll\sum_{\begin{array}{c} n\leq x\\ \omega(n)=r \end{array}}\sum_{\begin{array}{c} m\leq\frac{x}{n}\\ m\in\mathcal{B} \end{array}}1.$$

Carefully managing the sums, oone can then show that this is

$$\ll\frac{x}{\sqrt{\log x}}\sum_{\begin{array}{c} n\leq x\\ \omega(n)=r \end{array}}\frac{1}{n}\ll\frac{x\left(\log\log x\right)^{r}}{\left(\log x\right)^{\frac{1}{2}}}.$$

-
Thanks, Eric, for adding this. –  user22202 Apr 23 '12 at 23:36

This is a sketch, but I would think the details are reasonably routine:

1. First you compute the density of the set $F_r$ of numbers having exactly $r$ prime factors equal to $2$ mod $3$ and NO other factors. The computation should be completely parallel to the computation of density of $r$-almost primes, which is discussed at length, for example, in this question. (or google for more references). call the resulting density $\delta(r);$ for primes the density is $1/\log x$

2. Since you already know the result for $r=0$ ($f(x) = x/(\log^{1/2} x)$), you simply compute the integral $\int_1^N \lfloor f(N/x)\rfloor d \delta(x).$

(it seems clear that the result for $k$-almost primes in at least the original Landau form can be derived in exactly this fashion).

-