MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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.


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

share|cite|improve this question
up vote 4 down vote accepted

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

share|cite|improve this answer
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}}}. $$

share|cite|improve this answer
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).

share|cite|improve this answer

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.