MathOverflow will be down for maintenance for approximately 3 hours, starting Monday evening (06/24/2013) at approximately 9:00 PM Eastern time (UTC-4).
11

6

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

flag
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 2010 at 12:45
The former, according to Gil's link. – Steve Huntsman Mar 17 2010 at 12:47
It's a sum of multiplicative functions so should be amenable to using Dirichlet series. – Victor Miller Mar 17 2010 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 2010 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 2010 at 10:38
show 5 more comments

3 Answers

11

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

link|flag
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 2010 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 2010 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 2010 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 2010 at 16:15
("\alpha" should be "a") – David Hansen Mar 18 2010 at 16:16
show 2 more comments
10

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

link|flag
Nice answer! I wishes I knew more about Selberg Delange method. – Gil Kalai Mar 17 2010 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 2010 at 20:53
9

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

link|flag
1 
 That's a nice formula, but Gil asked about the sum of 1/(n d(n)). – Michael Lugo Mar 17 2010 at 15:48
5 
 Partial summation. – David Hansen Mar 17 2010 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 2010 at 18:06
1 
 Does Ramanujan give a proof or just the formula? – François G. Dorais♦ Mar 17 2010 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 2010 at 18:50
show 1 more comment

Your Answer

Get an OpenID
or

Not the answer you're looking for? Browse other questions tagged or ask your own question.