3
$\begingroup$

Let $$D_2(n) =\sum_{pq\leq n} 1,$$ and $$F_2(n) =\sum_{pq\leq n} \frac{1}{pq}$$ where $p,q$ are primes. Similarly define $$D_k(n) =\sum_{p_1\cdots p_k\leq n} 1,$$ and $$F_k(n) =\sum_{p_1\cdots p_k\leq n} \frac{1}{p_1\cdots p_k}.$$

I believe my calculations showing $$F_2(n)\sim \frac{(\log\log n)^2}{2}$$ and $$D_2(n)\sim \frac{n \log\log n}{\log n}$$ are correct (I used PNT and Mertens theorems).

What about larger $k$?

Is it possible to allow $k$ to grow very slowly and still get an estimate?

$\endgroup$
1
  • 1
    $\begingroup$ Actually the answer that was posted here (and now deleted), brief though it was, did answer your question. The Selberg-Delange method gives asymptotics for $D_k(n)$ in a wide range of $k$, and partial summation gives the other sum. Look this up in a Tenenbaum's book, or Montgomery-Vaughan. $\endgroup$
    – Lucia
    Commented Dec 2, 2016 at 5:19

2 Answers 2

7
$\begingroup$

For any fixed $k \geq 1$, one has $$D_k(n) \sim \frac{x}{\log x} \frac{(\log \log x)^{k-1}}{(k-1)!}.$$ This was originally proved by Landau in 1909 using induction of $k$.

For $k \ll \log \log x$, see Theorem 4 of chapter 6 of Tenenbaum's book "Introduction to analytic and probabilistic number theory." This is the Selberg-Delange method.

One can get decent upper bounds uniformly in $k$ with elementary methods, see for instance page 4 of these notes.

There is a nice heuristic: note the above assymptotic suggests a Poisson distribution with parameter $\log \log x$. One can view the events $\{ p | m\}_{p}$ as weakly dependent events with probability of success about $1/p$. So by general principles of probability (section 4.7 of Sheldon Ross' book) suggest that the probability of $k$ successes is modeled by a Poisson distribution. The shift in the index $k$ comes from the fact that every integer has at least one prime factor.

$\endgroup$
1
$\begingroup$

Define the function $F^*(n)=\underset{p_1\dots p_k\leq n}{\sum_{p_, \ldots, p_k}}\frac{1}{p_1\dots p_k}$. Then we have for each fixed $k$ the asymptotics $F_k^*(n)\sim(\log\log n)^k$. To see this note the obvious upper and lower bounds $$ \left(\sum_{p\leq n^{1/k}}\frac{1}{p}\right)^k\leq F_k(n)\leq \left(\sum_{p\leq n}\frac{1}{p}\right)^k, $$ and use the asymptotics $\sum_{p\leq n}\frac{1}{p}\sim\log\log n$.

To deduce an asymptotics for $F_k(n)$, note first that summands in $F_k^*$ corresponding to tuples which are not pairwise different are negligible, in fact, using a variation of the upper bound above we see that this contribution is $\mathcal{O}((\log\log n)^{k-1})$. If the primes are pairwise different, then the corresponding summand occurs $k!$-times in $F_k^*$ and only once in $F_k$, thus $F_k(n)\sim\frac{1}{k!}(\log\log n)^k$, confirming your computation.

As $k$ grows, we use the bound $\sum_{p\leq n}\frac{1}{p}=\log\log n +\mathcal{O}(1)$, thus $F_k^*(n)=(\log\log n)^k+\mathcal{O}(k(\log\log n)^{k-1})$. Deleting tuples which contain the same prime multiple times gets more complicated. A crude estimate would be $B_k(\log\log n)^{k-1}<k^k(\log\log k)^{k-1}$, where $B_k$ denotes Bell numbers. In this way you get a uniform bound almost up to $k=\log\log\log n$. If you need better estimates, you would have to consider partitions more carefully, which is doable, but some work.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .