Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

For a positive integer k, let d(k) be the number of divisors of k. So d(1)=1, d(p) =2 if p is a prime, d(6)=4, and d(12)=6.

What is the precise asymptotics of SUM_{k=1}^n 1/(kd(k))

Background:

1) This came up on the side in the polymath5 project.

2) There, Tim Gowers wrote: If nobody knows the answer, maybe that’s one for Mathoverflow, where I imagine a few minutes would be enough.

3) Asked: 14:17 Jerusalem time. (The first accurate answer: 17:44 Jerusalem time.)

4) Looking only at primes or only at integers with a typical number of divisors suggested a loglogn behavior, but looking at semiprimes indicates the sum is larger. I dont know how much larger.

5) I couldn't find an asnwer on the web. If there is an easy way searching for an answer that I missed this will be interesting too.

Follow up:

Great answers!! thanks. What about the sum

$\sum_{k=1}^n 1/(kd^2(k))$ ?

share|improve this question
    
SUM_{k=1}^n 1/kd(k) ... Does that mean $\sum_{k=1}^n 1/(k d(k))$ or $\sum_{k=1}^n d(k)/k$ ? –  Gerald Edgar Mar 17 '10 at 12:45
    
The former, according to Gil's link. –  Steve Huntsman Mar 17 '10 at 12:47
    
It's a sum of multiplicative functions so should be amenable to using Dirichlet series. –  Victor Miller Mar 17 '10 at 13:01
2  
The correct guess is C*(log N)^(1/2). Look-up the Selberg-Delange method. (The point is that sum(z^w(n), n <= X) ~ C*(log X)^(z-1) and (1/2)^w(n) is essentially the same as 1/d(n), so by partial summation we get sum(1/kd(k),k <= X) ~ C*(log X)^(1/2-1+1)) –  maks Mar 17 '10 at 15:43
2  
Re: the followup. If the hypotheses of the Delange (or Raikov) Tauberian theorem are satisfied, then $\sum_n 1/(n d(n)^2)$ should be $\sim C (\log x)^{1/4}$, since if $p$ is prime, $d(p) = 2$. –  Victor Miller Mar 18 '10 at 10:38
show 5 more comments

3 Answers

up vote 11 down vote accepted

The idea (from the Selberg-Delange) method to doing this problem is the following steps:

1) Let $F(s) = \sum_{n\ge 1} \frac{1}{n^s d(n)} = \prod_{p} \left(1 + \sum_{k=1}^{\infty} \frac{1}{(k+1) p^{ks}} \right)$. The latter is by multiplicativity of $d(n)$.

2) If we look, instead at $G(s) = \prod_p \left( 1 + \frac{1}{2 p^s} \right)$ we can see that $F(s)/G(s)$ has a non-zero limit as $s \rightarrow 1$ from above. $G(s)$ corresponds in our original sum to restricting $n$ to be square-free.

3) $G(s)^2$ almost looks like $\zeta(s)$. Show that $G(s)^2/\zeta(s)$ also has a non-zero limit at $s \rightarrow 1$.

4) You then use some Tauberian theorems to show that since $H_n \sim \log n$ (which is the sum associated with $\zeta(s)$ then the corresponding sum for $G(s)$ (i.e. over the square-free $n$) is $\sim to \sqrt{\log n}$.

share|improve this answer
    
I might be wrong, but I believe this idea predates Selberg and Delange by almost half a century. This was done already in 1908 by Landau to find the number of numbers represented by a sum of two squares. But since Selberg-Delange has been mentioned quite a few times in this post, I am doubting myself. –  Dror Speiser Mar 17 '10 at 20:52
    
@Dror: Yes, I was reminded of the Landau result you quoted too. I think what Delange did was to give a Tauberian theorem that was strong enough to deduce things like the following: $F(s) = \sum_n \frac{a_n}{n^s}$. and $F(s)^r/\zeta(s)$ has a non-zero limit when $s \rightarrow 1$, for some integer $r$ then $sum_{n \le x} a_n \sim C (\log x)^{1/r}$ for some non-zero $C$. Ramanujan's paper only announces the results. It doesn't have any proofs. –  Victor Miller Mar 17 '10 at 21:40
1  
The Tauberian theorem you mention was actually proved by Raikov: "Generalisation of a theorem of Ikehara–Landau (in Russian). Mat. Sbornik, 45 (1938)". If I am not mistaken, the Selberg-Delange method is more about getting a better error term (dating 1947?). Of course the particular instance of Landau was also proved and can be found in: "Über die Einteilung der positiven ganzen Zahlen in vier Klassen nach der Mindeszahl der zu ihrer additiven Zusammensetzung erforderlichen Quadrate." Arch. Math. Phys. 13, 305-312, 1908. –  Dror Speiser Mar 17 '10 at 21:52
1  
Suppose $D(s)$ is a Dirichlet series with multiplicative coefficients. If $D(s)=\zeta(s)^{a}F(s)$ where $a$ is rational and $F(s)$ is an Euler product which converges without zeros or poles in $\mathrm{Re}(s)> \delta$ for some $\delta < 1$, then you do NOT need a Tauberian theorem to study partial sums of the coefficients of $D(s)$. It is enough to apply a usual contour integration argument, but instead of shifting the whole contour you deform it around the singularity at $s=1$. The partial sums end up being $~c(\alpha)X(\log{X})^{a-1}$ where I forget $c(a)$ (it is simple). –  David Hansen Mar 18 '10 at 16:15
    
("\alpha" should be "a") –  David Hansen Mar 18 '10 at 16:16
show 2 more comments

The correct asymptotic is $C \cdot (\log N)^{1/2}$. (c.f Selberg-Delange method).

share|improve this answer
    
Nice answer! I wishes I knew more about Selberg Delange method. –  Gil Kalai Mar 17 '10 at 18:34
    
The main contribution to the sum will come from the integers n <= N, with (1/2)loglog N + O((loglog N)^(1/2 + epsilon)) prime factors. This is again a consequence of... the Selberg-Delange method. –  maks Mar 17 '10 at 20:53
add comment

(edited)

The answer can be extracted from a paper of Ramanujan, "Some formulae in the analytic theory of numbers", no. 17 in his collected papers. There he gives, among other things, the formula

$\sum_{n\leq X} \frac{1}{d(n)} \sim \frac{X}{\sqrt{\log{X}}}\pi^{-\frac{1}{2}}\prod_{p}\sqrt{p^2-p}\log{\frac{p}{p-1}}$.

The answer to the original question can be extracted from this by partial summation.

As for the "follow-up", the answer is $\sum_{n \leq X} \frac{1}{n d(n)^2} \sim C (\log{X})^\frac{1}{4}$. Again, Selberg-Delange...

share|improve this answer
1  
That's a nice formula, but Gil asked about the sum of 1/(n d(n)). –  Michael Lugo Mar 17 '10 at 15:48
5  
Partial summation. –  David Hansen Mar 17 '10 at 15:52
3  
Even though it is very elementary, I think you should write the above comment in the actual answer. The way it is currently written is just annoying. –  Dror Speiser Mar 17 '10 at 18:06
1  
Does Ramanujan give a proof or just the formula? –  François G. Dorais Mar 17 '10 at 18:25
8  
A remark for those who, like me, were confused: $\sqrt{p^2-p} = p (1-1/(2p)+O(1/p^2))$ and $\log (p/(p-1)) = 1/p + 1/(2 p^2) + O(1/p^3)$ so the factors in the product are $1+O(1/p^2)$ and the product converges. –  David Speyer Mar 17 '10 at 18:50
show 1 more comment

Your Answer

 
discard

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.