13
$\begingroup$

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 are the precise asymptotics of $\sum_{k=1}^n 1/(k d(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 $\log\log n$ behavior, but looking at semiprimes indicates the sum is larger. I don't know how much larger.

5) I couldn't find an answer 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))$ ?

$\endgroup$
10
  • $\begingroup$ 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$ ? $\endgroup$ Mar 17, 2010 at 12:45
  • $\begingroup$ The former, according to Gil's link. $\endgroup$ Mar 17, 2010 at 12:47
  • $\begingroup$ It's a sum of multiplicative functions so should be amenable to using Dirichlet series. $\endgroup$ Mar 17, 2010 at 13:01
  • 2
    $\begingroup$ 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)) $\endgroup$
    – maks
    Mar 17, 2010 at 15:43
  • 2
    $\begingroup$ 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$. $\endgroup$ Mar 18, 2010 at 10:38

3 Answers 3

14
$\begingroup$

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

$\endgroup$
7
  • $\begingroup$ 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. $\endgroup$ Mar 17, 2010 at 20:52
  • $\begingroup$ @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. $\endgroup$ Mar 17, 2010 at 21:40
  • 1
    $\begingroup$ 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. $\endgroup$ Mar 17, 2010 at 21:52
  • 1
    $\begingroup$ 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). $\endgroup$ Mar 18, 2010 at 16:15
  • $\begingroup$ ("\alpha" should be "a") $\endgroup$ Mar 18, 2010 at 16:16
11
$\begingroup$

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

$\endgroup$
2
  • 1
    $\begingroup$ Nice answer! I wishes I knew more about Selberg Delange method. $\endgroup$
    – Gil Kalai
    Mar 17, 2010 at 18:34
  • $\begingroup$ 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. $\endgroup$
    – maks
    Mar 17, 2010 at 20:53
10
$\begingroup$

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

$\endgroup$
6
  • 1
    $\begingroup$ That's a nice formula, but Gil asked about the sum of 1/(n d(n)). $\endgroup$ Mar 17, 2010 at 15:48
  • 6
    $\begingroup$ Partial summation. $\endgroup$ Mar 17, 2010 at 15:52
  • 3
    $\begingroup$ 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. $\endgroup$ Mar 17, 2010 at 18:06
  • 2
    $\begingroup$ Does Ramanujan give a proof or just the formula? $\endgroup$ Mar 17, 2010 at 18:25
  • 8
    $\begingroup$ 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. $\endgroup$ Mar 17, 2010 at 18:50

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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